images/logo.png
SHWB na blogspot  | Uživatel: Nepřihlášen

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:

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()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.

28.07.2019
Přidat názor:
Vyhrazuji si právo libovolný komentář smazat bez udání důvodu. Kritika mi nevadí, ale chci omezit anonymní výkřiky, které nemají s tématem nic společného.
V textu je možné používat HTML tagy a tuto zjednodušenou MarkDown syntaxi
Jméno
Text
Postřehy:
31.07.2019: Arduino 01 - Motivace k elektrotechnice
To jsem se jednou, nechci říct nudil, ale zkrátka jsem narazil na knihy "Porty, bajty, osmibity" a "Hradla, volty, jednočipy" od Martina Malého z produkce sdružení NIC.CZ, které jsou volně dostupné na knihy.nic.cz.
extravaganza.controverso@seznam.cz: Zdravím, krásný a informacemi nabitý blog. Musím pochválit. Plánuji rozjet undergroundový zin, co by se týkal black matalu, ambientu, satanismu, left hand
Poslední diskuse Postřehy
O programování 06 - Návrhové vzory - síla i slabina Javy
P.S. samozrejme "Context" mel byt "Client" .. To jsem jen narazil na nejak divne pojmenovany diagram.. (Context je samozrejme trosku neco jineho...)
...
David | 25.02.2017
O programování 06 - Návrhové vzory - síla i slabina Javy
To k cemu jsi dosel (tedy implementace LooperRunner + ILoopMethod), tak je ta prava Strategy by GoF :) To co je tam dulezite je ze Context (LooperRunner) je oddeleny od Strategy (ILoopMethod),
...
David | 25.02.2017
O programování 03 - Přehlednost funkcionálního zápisu v Java 8
Máš pravdu, to map je tam zbytečné. Odněkud jsem to opsal a nezkontroloval. Tím ovšem trochu padá pointa celého článku.
...
Saha | 14.12.2016
O programování 03 - Přehlednost funkcionálního zápisu v Java 8
Jen takova otazka k tomu druhemu prikladu:
Proc tam tu cast s "map" ktera de facto s prvky toho streamu nic nedela? Nestacilo by
list.stream().reduce(0, Integer::sum);
?
Ja teda moc
...
David P. | 13.12.2016
Paleo na půl - 01 - První tři dny bez mléka
Kvalitní hořké čokolády jsou bez mléka.. :) (a to i ty méně "kvalitní"). Mléko bývá součástí jen těch "sladkých".
...
David | 04.05.2015
Statistiky
Aktualizováno: 15.09.2019
Počet článků/fotek: 1374/13846
(C) Saha - 1990 - 2019 - Verze 1.3.32 - 11.05.2019 - Generated by SHREC 2.216
Veškeré zde uvedené materiály vyjadřují pouze moje soukromé názory (s výjimkou knihy návštěv a diskusí, kam může přispívat kdokoliv), a pokud s nimi někdo nesouhlasí, tak je to jeho problém, nikoliv můj.