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           "${out}" "$i" &>/dev/null && echo "don
Zverejnenie komentára
Čítať ďalej

Ako zálohovať všetky Postgre databázy naraz

Už dlhšiu dobu som si lámal hlavu ako zálohovať všetky PostgreSQL databázy v jednom kroku tak aby som to nemusel robiť po jednej. Na internete som našiel jedného chlapíka ktorý práve o tomto blogoval a ukázal tam aj riešenie. Riešením tohto problému je jednoduchý shell skript ktorý zavolá root databázy (zväčša postgres). A tento skript vytvorí z každej databázy súbor s príponou .backup. Shell skript ktorý som spomínal v mojom prípade nazvaný pg-backup-all-db.sh. #!/bin/sh # Posrgres executables CMD_PSQL=/usr/bin/psql CMD_DUMP=/usr/bin/pg_dump # prefix for backup filenames NAME_PREFIX=`date +%F` # directory where to save the database backup NAME_BACKUP_DIR=/srv/www/pgbackup/data # age of the older file to keep (in days) NB_DAYS_TO_KEEP=7 # Start backuping Databases=`$CMD_PSQL -tq -d template1 -c "select datname from pg_database"` echo "Starting backup of all databases..." for current_db in `echo $Databases`  do   if [ "$current_db" != "template0&qu
Zverejnenie komentára
Čítať ďalej

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