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

Ako previesť .mp3 súbor do .wav v Linuxe

Počas Vianočných sviatkov som skúmal ako previesť pesničky ktoré mám v počítači vo formáte MP3 do formátu audio CD ktorý by bez problémov načítala aj moja postaršia veža. Samozrejme našiel som veľa spôsobov avšak asi najjednoduchším bol veľmi jednoduchý shell skript. Inštalácia je veľmi jednoduchá: # Ubuntu sudo apt-get install mpg123 # Fedora yum install mpg123 Používať tento shell skript sa dá dvoma spôsobmi. Buď budete prevádzať každý MP3 súbor samostatne pomocou tohto príkazu: mpg123 -w vystup.wav vstup.mp3 Alebo využijete jednoduchú funkciu ktorú vložíte do súboru .bashrc v vašom koreňovom adresári. mp3towav(){      [[ $# -eq 0 ]] && { echo "mp3wav mp3file"; exit 1; }      for i in "$@"      do           # create .wav file name           local out="${i%/*}.wav"           [[ -f "$i" ]] && { echo -n "Processing ${i}..."; mpg123 -w ...
Zverejnenie komentára
Čítať ďalej

MathJax: Vkladanie matematických vzorcov na stránku

Asi 2 roky dozadu som tu písal o jazyku MathML. Jedná sa o jazyk z rodiny XML ktorý nám umožňuje vkladať na web matematické vzorce. Tento jazyk má však jednu nevýhodu a to, že aj na zapísanie jednoduchého a relatívne malého vzorca musíme napísať veľa neprehľadných riadkov. Tento problém zdá sa rieši MathJax . MathJax taktiež vkladá do stránky matematické vzorce ale dokáže ich vyrenderovať aj napríklad zo syntaxe ktorú používa LaTeX či AsciiMath a ta je oveľa kratšia a čitateľnejšia ako MathML. Použitie si ukážeme na jednoduchom zápise kvadratickej rovnice a vzorca slúžiaceho na jej výpočet. Ak $a \ne 0$, potom \(ax^2 + bx + c = 0\) má práve 2 korene ktoré vypočítame nasledovne: $$x = {-b \pm \sqrt{b^2-4ac} \over 2a}.$$ Použitie LaTeX-u <!DOCTYPE html> <html> <head> <meta charset="utf-8" /> <title>MathJax LaTeX Test</title> <script type="text/x-mathjax-config"> MathJax.Hub.Config({tex2jax: {in...
Zverejnenie komentára
Čítať ďalej

Ako zrušiť odskok prvého riadku v LaTeXe

Dnes som riešil problém ktorý som si myslel, že nebude žiadnym problémom ale opak bol pravdou. Potreboval som aby mi pri jednoduchom LaTeX -ovom dokumente automaticky neodsadzovalo prvý riadok odstavca. Asi po hodinke hľadania som na to prišiel a naozaj to bolo veľmi jednoduché. Do hlavičky dokumentu stačilo napísať tento riadok: \setlength{\parindent}{0in} Toto však vytvorilo jeden problém s ktorým som nepočítal. Odstavce sú spolu a bez odsadenia prvého riadku čo znamená, že text je dosť neprehľadný. Potreboval som teda vyriešiť ďalší problém a to ako pred alebo za odstavec vložiť nejakú medzeru. Riešenie bolo opäť veľmi jednoduché. \setlength{\parskip}{5mm}
Zverejnenie komentára
Čítať ďalej