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