Preskočiť na hlavný obsah

Príklad paralelného výpočtu v Jave s využitím Fork/Join frameworku

JDK 7 prišlo s novou možnosťou paralelného programovania. Java bola rozšírené o balíček java.util.concurrent v ktorom sa nachádzajú nové triedy ktoré umožňujú jednoduchšie paralelné programovanie nad viac ako jedným (jednovláknovým) jadrom procesora.

Hlavné triedy frameworku Fork/Join ktorý uľahčuje paralelné programovanie sú:

  • ForkJoinTask<V> – abstraktná trieda definujúca úlohu
  • ForkJoinPool – trieda riadiaca vykonávanie úloh typu ForkJoinTask<V>
  • RecursiveAction – podtrieda triedy ForkJoinTask<V> určená pre úlohy nevracajúce hodnoty
  • RecursiveTask<V> – podtrieda triedy ForkJoinTask<V> určená pre úlohy vracajúce hodnoty

Príklad

V príklade bude zotrieďované pole celých čísel troma triediacimi algoritmami (Bubble sort, Selection sort a Insertion sort) so zložitosťou O(n2). Na lepšiu ukážku budú použité len 2 jadrá procesora čím dosiahneme, že jedna z úloh bude musieť čakať na dokončenie inej.

Trieda Main.java:

import java.util.ArrayList;
import java.util.Collection;
import java.util.Random;
import java.util.concurrent.Callable;
import java.util.concurrent.ForkJoinPool;

public class Main {
	public static final int ARRAY_SIZE = 10;

	public static void main (String[] args) {
		// inicializuje pole
		int[] array = new int[ARRAY_SIZE];

		Random random = new Random();

		// naplni pole
		for (int i = 0; i < ARRAY_SIZE; i++) {
			array[i] = random.nextInt(ARRAY_SIZE * 2);
		}

		// Vytvori zoznam radiacich algoritmov
		Collection<Callable<Boolean>> collection = new ArrayList<Callable<Boolean>>();
		collection.add(new BubbleSort(array.clone()));
		collection.add(new InsertionSort(array.clone()));
		collection.add(new SelectionSort(array.clone()));

		// Vytvori pool ktory ma 2 jadra
		ForkJoinPool forkJoinPool = new ForkJoinPool(2);

		// Spusti vsetky vlakna
		forkJoinPool.invokeAll(collection);
	}
}

Trieda BubbleSort.java:

import java.util.Date;
import java.util.concurrent.Callable;

public class BubbleSort implements Callable<Boolean> {
	private int[] array;

	public BubbleSort (int[] array) {
		this.array = array;
	}

	public int[] getArray () {
		return array;
	}

	private void sort () {
		this.log("start");
		for (int i = 0; i < this.array.length; i++) {
			for (int j = 0; j < this.array.length - i - 1; j++) {
				if (this.array[j] < this.array[j+1]) {
					this.log("vymena: " + this.array[j]  + " za " + this.array[j+1]);
					int tmp  = this.array[j];
					this.array[j] = this.array[j+1];
					this.array[j+1] = tmp;
				}
			}
		}
		this.log("koniec");
	}

	private void log (String message) {
		System.out.println(new Date().toString() + " [BubbleSort] " + message);
	}

	@Override
	public Boolean call () {
		this.sort();
		return true;
	}
}

Trieda InsertionSort.java:

import java.util.Date;
import java.util.concurrent.Callable;

public class InsertionSort implements Callable<Boolean> {
	private int[] array;

	public InsertionSort (int[] array) {
		this.array = array;
	}

	public int[] getArray () {
		return array;
	}

	private void sort () {
		this.log("start");
		for (int i = 0; i < this.array.length - 1; i++) {
			int j = i + 1;
			int tmp = this.array[j];
			while (j > 0 && tmp > this.array[j-1]) {
				this.log("pusun prvku " + this.array[j]);
				this.array[j] = this.array[j-1];
				j--;
			}
			this.array[j] = tmp;
		}
		this.log("koniec");
	}

	private void log (String message) {
		System.out.println(new Date().toString() + " [InsertionSort] " + message);
	}

	@Override
	public Boolean call () {
		this.sort();
		return true;
	}
}

Trieda SelectionSort.java:

import java.util.Date;
import java.util.concurrent.Callable;

public class SelectionSort implements Callable<Boolean> {
	private int[] array;

	public SelectionSort (int[] array) {
		this.array = array;
	}

	public int[] getArray () {
		return array;
	}

	private void sort () {
		this.log("start");
		for (int i = 0; i < this.array.length - 1; i++) {
			int maxIndex = i;
			for (int j = i + 1; j < this.array.length; j++) {
				if (this.array[j] > this.array[maxIndex]) maxIndex = j;
			}
			this.log("vymena : " + this.array[i] + " za " + this.array[maxIndex]);
			int tmp = this.array[i];
			this.array[i] = this.array[maxIndex];
			this.array[maxIndex] = tmp;
		}
		this.log("koniec");
	}

	private void log (String message) {
		System.out.println(new Date().toString() + " [SelectionSort] " + message);
	}

	@Override
	public Boolean call () throws Exception {
		this.sort();
		return true;
	}
}

Výstup programu:

Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] start
Sat Oct 15 17:08:36 CEST 2016 [SelectionSort] start
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 0 za 17
Sat Oct 15 17:08:36 CEST 2016 [SelectionSort] vymena : 0 za 18
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 0 za 1
Sat Oct 15 17:08:36 CEST 2016 [SelectionSort] vymena : 17 za 17
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 0 za 13
Sat Oct 15 17:08:36 CEST 2016 [SelectionSort] vymena : 1 za 13
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 0 za 18
Sat Oct 15 17:08:36 CEST 2016 [SelectionSort] vymena : 1 za 7
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 0 za 3
Sat Oct 15 17:08:36 CEST 2016 [SelectionSort] vymena : 0 za 6
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 0 za 7
Sat Oct 15 17:08:36 CEST 2016 [SelectionSort] vymena : 3 za 3
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 0 za 6
Sat Oct 15 17:08:36 CEST 2016 [SelectionSort] vymena : 1 za 3
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 0 za 1
Sat Oct 15 17:08:36 CEST 2016 [SelectionSort] vymena : 0 za 1
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 0 za 3
Sat Oct 15 17:08:36 CEST 2016 [SelectionSort] vymena : 0 za 1
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 1 za 13
Sat Oct 15 17:08:36 CEST 2016 [SelectionSort] koniec
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 1 za 18
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 1 za 3
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] start
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 1 za 7
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 17
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 1 za 6
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 1
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 1 za 3
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 13
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 13 za 18
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 0
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 3 za 7
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 18
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 3 za 6
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 0
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 1 za 3
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] vymena: 17 za 18
Sat Oct 15 17:08:36 CEST 2016 [BubbleSort] koniec
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 1
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 13
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 3
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 0
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 7
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 0
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 1
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 6
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 0
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 1
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 1
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 3
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 0
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] pusun prvku 1
Sat Oct 15 17:08:36 CEST 2016 [InsertionSort] koniec

Komentáre

Zverejnenie komentára

Obľúbené príspevky z tohto blogu

Java - Súčet Listu s objektami BigDecimal

Pri používaní typu BigDecimal som narazil na zaujímavú úlohu a to sčítanie všetkých hodnôt v Liste. Majmä nasledovne definovaný list: List < BigDecimal > listOfBigDecimals = new LinkedList (); 1. spôsob je klasicke preiterovanie celého listu: BigDecimal sum = BigDecimal . ZERO ; for ( BigDecimal number : listOfBigDecimals ) { sum = sum . add ( number ); } 2. spôsobom je využitie stream.reduce() : BigDecimal sum = listOfBigDecimals . stream () . reduce ( BigDecimal . ZERO , BigDecimal :: add ); BONUS: spôsob s použitím reduce() v Kotline : val sum : BigDecimal = listOfBigDecimal . reduce { a , n -> a . add ( n ) }
Zverejnenie komentára
Čítať ďalej

Obnova vymazaných suborov

Mnohokrát som sa stretol s otázkou či je možné obnoviť vymazané súbory na disku, na USB kľúči či na pamäťovej karte. Moja odpoveď je vždy rovnaká: NIE! Áno, ja viem klamať sa nemá ale je to lepšie pre obe strany. Ja sa s tým nemusím hrať a prehľadávať kadejaké staré USB disky a na druhej strane ľudia nie sú sklamaný keď sa mi to nepodarí. Teraz keď vieme, že to ide tak si poďme ukázať jednoduchý spôsob ako sa to dá robiť. Počas ukážky si stiahnem logo softvéru TestDisk ktoré následne vymažem a pokúsim sa ho opäť obnoviť. Použijem na to softvér TestDisk . user@pc:/media/user/USB $ wget http://www.cgsecurity.org/mw/images/Testdisklogo_clear_100.png --2017-02-10 23:03:29-- http://www.cgsecurity.org/mw/images/Testdisklogo_clear_100.png Prevádza sa www.cgsecurity.org (www.cgsecurity.org) na IP adresu... 193.168.50.236 Pripájanie k www.cgsecurity.org (www.cgsecurity.org)|193.168.50.236|:80... pripojené. HTTP požiadavka odoslaná, čakám na odpoveď... 200 OK Dĺžka: 1726 (1,7K) [imag...
Zverejnenie komentára
Čítať ďalej

Formátovanie poznámok pod čiarov v LaTeXe

Najjednoduchšou cestou je použitie hand nastavení z balíčka footmisc . Pre nastavenie odsadenie použijeme voľbu \fotnotemargin nasledovne: \documentclass{article} \usepackage{lipsum} \usepackage[hang]{footmisc} \setlength\footnotemargin{10pt} \begin{document} \null\vfill % iba pre príklad \lipsum*[4]Test\footnote{\lipsum[4]} \end{document} Citované z : http://tex.stackexchange.com/questions/126877/how-can-i-align-a-multiple-line-footnote-text-right-to-the-footnote-mark#126878
Zverejnenie komentára
Čítať ďalej