O programování 12 - Paralelní implementace násobení matic v Java - úvod
Poznámka: Tento článek byl (skoro celý) napsán v roce 2017, ale publikovat se mi ho podařilo až o dva roky později. Původně byl napsán pro tehdy aktuální Java 8, teď, v Java 11 už to může být trochu jinak.
Když jsem v předchozích dílech zkoušel různé varianty streamových cyklů, neměl paralelní stream žádný měřitelný přínos. Vysvětloval jsem si to tím, že daný problém se nedal paralelizovat a úvahy o vhodném problému k paralelizaci jsem odložil na později. Chvíli mi totiž trvalo, než jsem našel vhodný problém, nakonec jsem zvolil násobení matic, protože můžu jednotlivé prvky výsledné matice počítat paralelně. Vím, že existují chytřejší způsoby násobení matic než tato naivní implementace s kvadratickou složitostí, ale o to v tomto článku nejde.
Ještě před tím, než jsem začal paralelní násobení matic implementovat, tak jsem si udělal rešerši o tom, co se o paralelních streamech v Java píše na internetu. Před jejich použitím lze najít docela dost varování, jednak kvůli výkonnosti a také proto, že není úplně triviální implementovat paralelní algoritmus korektně a nevhodná implementace může způsobit více škody než užitku. Osobně mi nejvíce vadí to, že nelze omezit počet spouštěných procesů, buď se použije jeden procesor (vlákno) nebo všechny.
Seznam vybraných článků na dané téma je zde:
- Oracle collection Tutorial
- Java parallel streams are bad for your health
- Think twice using Java 8
- Should I always use a parallel stream when possible
- How fast are the Java 8 streams
- Parallel streams Java 8
- Lambdas and streams in Java 8 libraries
Python
Než začnu s implementací násobení matic v Javě, musím přiznat, že jsem před lety absolvoval online kurz Introduction to Data Science na CourseEra a jednou z řešených úloh bylo právě násobení matic v Pythonu s využitím přístupu Map-Reduce. Měl jsem pocit, že celý algoritmus byl na pár řádcích, ale teď vidím, že je to trošku delší, ale proti Javě, jak ještě uvidíme, je to pořád krátký zápis.
mr = MapReduce.MapReduce()
def mapper(record):
matrix = record[0]
i = record[1]
j = record[2]
value = record[3]
if matrix =="a":
for k in range(5):
mr.emit_intermediate((i,k), (j, 0, value))
else:
for k in range(5):
mr.emit_intermediate((k,j), (i, 1, value))
def reducer(key, value):
r1 = [0,0,0,0,0,0]
r2 = [0,0,0,0,0,0]
for item in value:
if (item[1] == 0):
r1[item[0]] = item[2]
else:
r2[item[0]] = item[2]
value = 0
for x in range(5):
value += r1[x] * r2[x]
mr.emit((key[0], key[1], value))
if __name__ == '__main__':
inputdata = open(sys.argv[1])
mr.execute(inputdata, mapper, reducer)
Java - reprezentace matice
Implementace v Javě nebude tak úsporná, protože tento jazyk vede k abstraktnějšímu uvažování. Místo reprezentace matice v hash poli si vytvořím objekt MatrixData a na něm definuji potřebné operace. Uvažuji matici s hodnotami typu int ale kdybych si pohrál s generikami, získal bych obecnou matici.
public class MatrixData {
private final int ROWS;
private final int COLUMNS;
private final int[][] values;
public MatrixData(int m, int n) {
ROWS = m;
COLUMNS = n;
values = new int[ROWS][COLUMNS];
}
Neumožním přistupovat k prvkům matice přímo ale přes metody get() a set(), u kterých si pohlídám rozsah indexů pomocí privátní metody checkIndexes(). Tu ve výpisu neuvádím, pouze kontroluje rozsah indexů a v případě chybného indexu vyhodí MatrixIndexOutOfBoundariesException. Třída MatrixData obsahuje i další metody, např. pro vypsání matice, pro vrácení i-tého řádku a j-tého sloupce a další.
public void set(int i, int j, int value) throws MatrixIndexOutOfBoundariesException {
checkIndexes(i, j);
values[i - 1][j - 1] = value;
}
public int get(int i, int j) throws MatrixIndexOutOfBoundariesException {
checkIndexes(i, j);
return values[i - 1][j - 1];
}
Výsledkem mého snažení je celkem robustní reprezentace matice. Na druhou stranu, už teď mám datovou třídu a dvě výjimky a celý kód je delší, než celý program pro násobení matic v Pythonu a to mám pouze datovou reprezentaci. Ale srovnávám nesrovnatelné, jedná se totiž o odlišný přístup k problematice.
Příště si ukážeme různé varianty násobení matic - naivní implementaci, neparalelní map-reduce a jeho paralelní verzi. Jenom doufám, že to nebude opět za dva roky.
PS: Když jsem začal násobení matic implementovat, kladl jsem si otázku - dostanu se od intuitivní a naivní implementace její paralelizací k Map-Reduce nebo ne? Odpověď ještě nevím úplně přesně ale vypadá to, že ano.
- O programování 01 - Úvod
- O programování 02 - Efektivita funkcionálního přístupu v Java 8
- O programování 03 - Přehlednost funkcionálního zápisu v Java 8
- O programování 04 - Java Microbenchmark Harness
- O programování 05 - Další varianty Javovské implementace foreach
- O programování 06 - Návrhové vzory - síla i slabina Javy
- O programování 07 - Funkce jako argument aneb od factory k lambdě v Javě
- O programování 08 - Jak v Javě předat metodu, která bude mít různé parametry
- O programování 09 - Pokročilé využití streamů a funkcionálního přístupu v Java 8
- O programování 10 - Java a inspirace v Ruby
- O programování 11 - Minimalistické programy a Java