Budoucnost paralelního programování

15.3.2006 12:20 | Přečteno: 3041× | Počítače

K úvaze o paralelním programování mě inspirovala nedávná debata s kamarádem na téma vícejádrových procesorů. Nečekal bych, že někdy začnu na abclinuxu psát blog. Stalo se. Blogy jsou zde navštěvované právě těmi lidmi, kteří mě zajímají a se kterými lze krásně podiskutovat nad některými aspekty výpočetní techniky.

Současná podoba počítačů vznikla někdy v době druhé světové války. Celou koncepci přivedl na svět VonNeuman, taky se mu od té doby říká VonNeumanova architektura. Trochu odlišná je architektura Harwardská, ale v zásadě se od VonNeumanovy nijak neliší. Základním principem obou architektur je sériové programování. Programy zapisujeme shora dolů, procesor louská instrukce jednu za druhou a ani "paralelní" zpracování v moderních procesorech na tom nic nemění. Procesory pouze předžvýkávají několik instrukcí předem, tak aby hlavní výkonná jednotka v procesoru mohla vykonávat instrukce bez větších prodlev - sériově.

Programování od dob druhé světové války udělalo veliký pokrok - assembler, fotran, strukturované programování, objektové programování, událostní programování, programování vláken... nicméně procesory se stále drží zaběhnuté praxe a přebírají se instrukcemi jak babička klokočím na růženci. Nenastává pomalu čas změnit i procesory a konečně použít na přehazování instrukcí bagr?

Údajně nejsou vytvořené metodiky pro paralelní programování a nejsou připravené ani překladače, které umí zaměstnat více procesorů a nejsou ani procesory, který by obsahovaly desítky či stovky jader. První vlaštovky v podobě vícejaderných procesorů slibují, že se v budoucnu začnou objevovat na uživatelských stolech počítače s desítkami či stovkami jader a vývojáři se budou snažit tyto procesory pochopitelně využít co nejlépe.

Asi každý, kdo někdy donesl jednomu člověku do kanceláře nový počítač, musel zaznamenat, jak se najednou všem ostatním okolo skokově zpomalily počítače. Lidé mají na stolech procesory, které devadesát procent doby zahálejí, přitom jejich uživatelé skřípou zubama a skuhrají, jak ten excel zase dneska dlouho startuje. Mají pravdu - pusťte si na nejrychlejším počítači ve svém okolí třeba office (koffice, openoffice, msoffice - dle vlastního výběru a možností) a sledujte, jak pomalu a jedna za druhou se vykreslují ikonky, čudlíky - celé pracovní prostředí. Rychlejší procesor na tom mnoho nezmění, protože si svým prstíkem ukazuje na instrukci, kterou právě zpracovává, a ani dvakrát rychleji není dostatečně rychle.

Procesory většinu doby zahálejí - lidé výkon nepotřebují. Co potřebují, je rychlá odezva.

Programovací techniky jsou pro paralelní programování připravené. Na uživatelském rozhraní složitejšího programu je vidět, jak se vykreslují komponenty jedna za druhou. Přitom jsou jednotlivé komponenty v kódu solidně oddělené a událostní programování přímo vybízí k jejich paralelnímu zpracování. Brání dnes něco tomu, aby každá vybraná metoda běžela na vlastním procesoru? Dovedu si představit, že v programu rozešlu stovce komponent událost expose a stovka komponet (technicky stovka oddělených vláken) se na stovce procesorů zároveň překreslí. Uživatel může mít procesor se sériovým výkonem prvního pentia (více výkonu není potřeba) a navzdory tomu nebude muset čekat na aplikace půl dne. Stačí se jen vzdát myšlenky, že nejvýkonnějších vícejaderných procesorů je škoda na tak podřadnou úlohu, jako je kreslení blbinek na obrazovku.

Je moje představa správná? Může vést rozvoj vícejádrových procesorů k tomuto způsobu programování? Jakým způsobem by se musely změnit dnešní zaběhnuté programovací techniky, aby programy dokázaly využít stovky procesorů zároveň? Musí být paralelní programování výsadou distribuovaných síťových výpočtů a specializovaných strojů, které stejně nic užitečného nedělají (nepočítám-li simulace atomových výbuchů, hledání mimozemšťanů a léků na X chorob)?

Diskutujte. Zajímá mě váš názor.

       

Komentáře

[zde]

> a událostní programování přímo vybízí k jejich paralelnímu zpracování.

Podle mého názoru naopak události vybízejí k sekvenčnímu modelu, resp. jej vynucují. Spoléhají na getmessage/translatemessage/dispatchmessage smyčku, kterou paralelně implementovat nelze.

[Abraxis]

Ne nutne. Jasne, ze tahle smycka muze bezet prakticky jen jedna, ale dokazu si predstavit, ze bude "minimalisticka" - tzn. bude vybirat udalosti, ale jejich casove narocne zpracovani bude predavat nekolika paralelne bezicim procesum.

[Michal Kubeček]

V tom případě ale budete muset řešit otázku návazností, protože v některých případech je potřeba zaručit, že určitá událost bude zpracována až po jiné.

[zde]

To by ovšem dispatchmessage muselo být asynchronní, což ale v žádném reálném gui není. Pro WM_PAINT a obdobné "broadcast" zprávy by to sice implementovat docela snadno šlo, ale jinak asi ne. To že samotný dispatch bere minimum cpu je pravda, ale protože je blokující tak to nepomůže.

[polo]

SMP je rozumne pouzivat pouze tehdy, dosahnemeli distribuci problemu zrychleni, tj dokazemeli rozdelit danou ulohu na takove casti, ze jejich casti na ruznych uzlech se budou pocitat dobu delsi nez je doba potrebna pro predani dat. Coz se domnivam, ze v pripade vykreslovani GUI jentak nedosahneme.

Dalsi problem je se synchronizaci etc, ale tyto veci uz jsou pro paralelni stroje celkem vyresene, vetsinou se resi ruznymi algortimy pro zamikani sekci atp..

Domnivam se ze implementace v zadanem pojeti v dnesnich meritkach by byla nefektivni.

Pekny den.

[Marek 'marx' Grác]

Programovacie techniky na to práve nie sú pripravené. Paralelne dokážeme procesory/počítače využiť hlavne v prípade, že dokážeme rozdeliť úlohu na časti, ktoré dokážeme vykonávať oddelene (napr. rozdelením intervalu). V opačnom prípade máme problémov vyše hlavy. Samozrejme, že ak by sme mali dva procesory/jadrá tak nie je problém, aby na jednom bežalo KDE/GNOME/X a na druhom aplikácie, ale to je 'klasický' prístup.

[zde]

To je jen jedna část problému. Rozdělit algoritmus obvykle jde docela snadno, ovšem jeho zdroje (tj hlavně paměť) už tak dobře dělit nejde.

Programovací techniky na úrovni procesu spoléhají na jednu sdílenou paměť. Jde to částečně vyřešit- samostatná cache u SMP, triky s virtuální pamětí u clusterů apod, ale není to koncepční řešení. Defaultně se stále uvažuje sdílený prostor, kde každý thread může číst a zapisovat co chce, a různými technikami se to cachuje a optimalizuje aby to nějak běželo.

Správně by paralelizace měla být explicitní, tj překladač a OS by vždy měl přehled který kus paměti patří kterému threadu, který je třeba RO a měl by se replikovat, a který je RW a s kterým (hardwarově implementovaným) zámkem je spojen.

[Marek 'marx' Grác]

Medzi problémy vyše hlavy som myslel práve tú pamäť. S tým jediným mám skúsenosti, ono to je vidno pre laika aj na tom ako naposledy hrali ten Doom s obrazom roztiahnutým na nejakých 10 000 pixlov, kde bol vždy jeden komp na dva monitory a malo to nejakých 15-30fps (tuším). A IMHO aj to bol celkom úspech :)

[barney]

v prvom rade na to nie sú pripravení programátori a o pseudoprogramátoroch ani nevravím

[pzad]

Paralelny program sa hodne zle ladi a pripadne chyby v sinchronizacii sa strasne zle hladaju a obcas sa aj velmi divne prejavuju.

[vencour]

V Quantianu je openMossix, clusterKnoppix atd., ale zatim se mi je síťově nepodařilo zprovoznit (a tolik jsem si s tim nehrál). Prostě jsem dva procesory v openMossixView neviděl. Časem se k tomu snad dostanu.

[stativ]

Mozna budu placat blbosti, ale myslim, ze tohle OpenMosix prave bohuzel nepodporuje. OpenMosix se i musi kompilovat bez podpory SMP v jadre.

Pokud to bylo ale mysleno jako ze se pocitace njepropojily pres sit, tak se afaik v openmosixview nezobrazuji procesory ale pocitace. Navic se musi v takovem klikatku propojit 'linkami' aby o sobe vedeli.

[Michal Vyskočil]

Nevím jak ostatní, ale mě v drtivé většině případů zpomaluje disk a paměť. Procesor považuji za úplně poslední věc, která by mě v tomto ohledu trápila.

Ostatně ty to taky sám říkáš:

Procesory většinu doby zahálejí - lidé výkon nepotřebují. Co potřebují, je rychlá odezva.

Ale rychlejší odezvu při startu office nezískáš přidáním dalšího procesoru, který se bude taky většinu času nudit. Ale právě rychlejším diskem/pamětí.

Ad: paralelní zpracování ... nic není tak hezké jak to vypadá. Pro paralelní zpracování se hodí jen některé úlohy. Typickým příkladem je zpracování obrazu, vědecké výpočty. U spousty úloh začne být synchronizační režie tak vysoká, že překryje veškerý zisk z vlastního paralelismu. A to vůbec nemluvím o tom, že paralelní programy bývají náročnější na kódování a vůbec se hůř ladí.

[dad]

[...] jak ten excel zase dneska dlouho startuje. Mají pravdu - pusťte si na nejrychlejším počítači ve svém okolí třeba office (koffice, openoffice, msoffice [...]

u jednoho zakaznika se resila problematika, ze prodejni oddeleni nedokaze vyprodukovat za mesic pozadovany pocet nabidek. Sef dusil zamestnance a ti v ramci workshopu pozadovali v prenesenem slova smyslu "turbopropisky", aby mohli praci stacit.

Podarilo se nam zakaznika presvedcit, ze bude vyhodnejsi nabidky nepsat jako doposud za pomoci predpotopnich nastroju (word, openoffice apod), ale ze by to mel delat za ne pocitac. Naprogramoval se inteligentni nabidkovy system a pocet nabidek vzrost 20 x.

Proto si myslim, ze viceprocesorove systemy nepomohou...

[Miloslav Ponkrác]

Každý, kdo zkusil naprogramovat několik složitějších paralelních aplikací ví, že paralelní programování není žádná sranda.

Zásadní problém je dvojí. První je ten, že vlastní paralelní algoritmus běží v prostředí, které není paralelní. Sdílí se až příliš mnoho věcí. Od paměti počínaje až bůhvíkam konče. Druhý problém je ten, že jen málo problémů lze efektivně řešit paralelně. Naprostá většina algoritmů je maximálně pseudoparalelní, kdy se udělá malý kousek a pak nastává synchronizace s jinými paralelními větvemi a dochází k předávání dat mezi větvemi. To se neobejde bez synchronizačních akcí, které dost často bývají dost náročné a mnohdy pošlou celý výkonnostní i jiný zisk z paralelního algoritmu do kopru.

Problém paralelních algoritmů je cena vývoje, která je mnohem výše, než při obvyklém sériovém programování. Připočtěte si zvýšenou možnost chyb při synchronizaci a v podstatě fakt, že najít chybu v paralelním algoritmu je podstatně obtížnější, než v obyčejném sériovém programu.

Kromě toho dnes již prakticky neexistuje program, který by se částečně paralelně nevykonával. Dnes každý moderní procesor obsahuje několik různých jednotek, které běží dost nezávisle a úkolem kompilátorů je vytvořit takový kód, který umožňuje maximalizovat paralelní běh kódu na daném procesoru. Některé kompilátory, třeba Intel dokonce aktivně vyhledávají v programu kousky, které lze paralelizovat.

Závěr: Problém paralelních algoritmů je více ekonomický, než jiný. Paralelní algoritmy se programují déle (= větší náklady na vývoj), vyžadují kvalitnější programátory (= větší náklady) a problém chyb v paralelních algoritmech má poněkud fatálnější následky (= větší náklady). Problém rychlosti programů a paralelních algoritmů z ekonomické stránky je ve stejné rovině, jako proč se dnesw píší méně efektivní programy, než kdysi. Pokud zaplatíte programátory, udělají vám rychlejší a kvalitnější program i dnes. Pokud zaplatíte programátory, udělají vám i kvalitní paralelní program. Ale protože ekonomika vládne světem, tak se financuje jen to, co je nezbytně nutné a paralelní programování jen málokdy přináší zisk, který ospravedlňuje podstatně vyšší náklady (samozřejmě kromě nekolika specifických oblastí).

[Petr Bravenec]

Dobře. Rozumím tomu. Ekonomické důvody jsou jasné. Ale já zkusím přiblížit svoje představy. V dobách šlapacích počítačů se používal jazyk C a v něm bylo možné definovat některé proměnné jako registrové. Dělalo se to snad proto, aby tehdejší jednoduché překladače netahaly například řídící proměnné v cyklech přes zásobník. Dneska se o to nestaráme a necháváme to na překladačích a spoléháme na to, že registrů je dost. I programování dnes vypadá jinak - typická aplikace je poskládaná z možství objektů se svými vlastnostmi a metodami. Objekty jsou od sebe oddělené a ideálně spolu komunikují pouze prostřednictvím veřejných metod. Každá instance objektu je samostatný element - proč tedy analogicky k registrovým proměnným nedeklarovat některé vybrané objekty jako typ cpu a nesvěřit zpracování takového objektu samostatnému procesoru? Samozřejmě, že jednotlivý procesor většinu času prozahálí - ale ono není účelem zaměstnat všechny procesory na sto procent. Programovat dnes pomocí vláken je nepříjemné a není tlak na vytvoření lepšího prostředí. V momentě, kdy bude k dispozici běžně několik procesorů, vývojáři budou chtít využít potenciálu takových procesorů. Budou volat po zjednodušeném vývojovém prostředí a tlak na jeho vytvoření bude vzrůstat. Se vznikem takových nástrojů se pak samozřejmě razantně sníží i cena vývoje a poptávka po mnohojádrových procesorech může vesele růst.

[Petr Bravenec]

Tedy... ééééé... věštit nechci, vizionářů má IT branže dost, jen by mě zajímala možnost takového vývoje.

[Miloslav Ponkrác]

Já rozumím, ale přesto se domnívám, že skoro všechno je jinak.

Dokonale optimalizující kompilátor označovat proměnné jako register nepotřebuje a slovo register ignoruje, což dnes každý dobrý kompilátor dělá.

Objektové programování je jen jedna z metod programování. I když je jistou dobu v módě, není to jediný způsob.

Pro mě bylo obrovskou zkušeností setkání s realtimovými a simulačními jazyky před cca 20 lety. Studoval jsem technickou kybernetiku - v zásadě teorii řízení systémů a tam jsem se seznámil s jazyky, které dodnes považuji za poklad, mnohá jména už jsem zapomněl. Paralelní a pseudoparalelní programování se tam už tehdy řešilo na sto a jeden způsob a seznamoval jsem se s nejrůznějšími způsoby, jak je zabudovat do jazyků, aby to bylo pro programátora co nejjednodušší. Progamování pomocí vláken je spíše v měnšině, a používá se u jazyků, které v podstatě nedělají nic jiného, než wrapper nad operační systém, jako je třeba C, Java, a další. Jestli chcete poznat skutečná řešení paralelního programování, musíte pryč z mainstreamových programovacích jazyků, ty na to nejsou určeny. Pro začátek doporučuji podívat se na řešení, které nabízí jazyk Ada, ale pozor! Budete překvapen, jak je to odlišné od "běžného pracího prášku", ehm chtěl jsem říci od běžného řešení v mainstreamových programovacích jazycích.

Já stále vzpomínám na technologie a programovací jazyky, které jsem před těmi 20 až 25 lety zkoušel a byly geniální! V podstatě celý dnešní tzv. moderní vývoj sw nedělá nic jiného, než se k nim vrací a postupně se k nim přibližuje. Je to strašná sranda. Třeba za nějakých 50 let se objeví nějaký super hyper moderní styl programování a super programovací jazyk, abych si jenom řekl tak paráda, zase o krůček blíž tomu, co jsem poznal tehdy. Jak říkám, je to opravdu sranda

[Petr Bravenec]

Hmmm. Přiznám se, že s žádným prostředkem pro paralelizaci aplikace jsem se dosud nesetkal. Vždy jen ten dnešní mainstream. Nemohla by ale snadná dostupnost víceprocesorových počítačů udělat mainstream z postupů, které jsou dnes vyložené okrajové a mimo kuriozní situace se nevyužívají?

Registrové proměnné v C jsem používal naposledy na počítačích SMEP a vzpomínal jsem je proto, že v tehdejší době to byl jeden z prostředků, jak usnadnit překladači (vývojovému prostředí) seskládání celé aplikace.

[Miloslav Ponkrác]

Nesetkal jste se tím jednoduše proto, že na nabouchání databázové aplikace, nebo na pár jednoduchých matematických algoritmů to nepotřebujete. A na škole i v běžné praxi se tím pádem běžně nesetkáte s ničím jiným, než s tímto. A je to v pořádku - nástroj se musí vybírat podle toho, co chcete dělat.

Dnešní doba má tu trochu protivnou vlastnost, že vyrábí monokultury. Prostě cokoli, co nemá 80% trhu a na čem se okamžitě nedá zbohatnout, to se zapomíná, nikdo o tom nepíše.

Příliš nevěřím tomu, že by snadná dostupnost víceprocesorových počítačů mohla udělat mainstream z postupů, které jsou dnes na okraji. Proč taky? Dnešní postupy vyhovují, obchodní a ekonomický svět je přijal. Nepotřebujete v zásadě nic jiného.

Spíše očekávám to, že programátoři budou bouchat komponenty jako dnes, jen bude pár komponent, které v sobě mají určité paralelní prvky. Ty naprogramuje speciální firma a 99,999% programátorů nebude ani vědět, že se něco děje paralelně.

Mezi námi, chcete-li se něco zajímavého o programování dozvědět, musíte přestat být "monokulturním programátorem".

[Miloslav Ponkrác]

Registrové proměnné v C jsem používal naposledy na počítačích SMEP a vzpomínal jsem je proto, že v tehdejší době to byl jeden z prostředků, jak usnadnit překladači (vývojovému prostředí) seskládání celé aplikace.

Takže taky máte své zkušenosti. Rád na tu dobu vzpomínám, i když vrátit bych jí nechtěl.

[zde]

Pro mě bylo obrovskou zkušeností setkání s realtimovými a simulačními jazyky před cca 20 lety. Studoval jsem technickou kybernetiku - v zásadě teorii řízení systémů a tam jsem se seznámil s jazyky, které dodnes považuji za poklad, mnohá jména už jsem zapomněl. Paralelní a pseudoparalelní programování se tam už tehdy řešilo na sto a jeden způsob a seznamoval jsem se s nejrůznějšími způsoby, jak je zabudovat do jazyků, aby to bylo pro programátora co nejjednodušší.

INMOS Transputer? Minimalisticky CPU kontext? Hardwarový message passing? Bezelo to na par megahertzech, ale task switch byl hluboko pod mikrosekundu.. Occam? Otazniky a vykricniky? :)

http://en.wikipedia.org/wiki/Transputer

[Věroš]

Dnes se víceprocesorové stroje používají (a využívají) zejména pro relativně nezávislé úlohy - pěknou aplikací jsou webové aplikace, kde jednotlivé požadavky jsou relativně nezávislé a každá běží dlouho samostatně bez závislosti na ostatních a nemusí se synchronizovat.

Časem se v tomto duchu můžeme dočkat třeba toho, že vykreslování ovládacích prvků (widgetů) bude mít na svědomí jedno vlákno a druhé bude řešit aplikační logiku. Konec konců, Windows k něčemu podobnému směřují, každá vlastnost už dnes tam má vlastní vlákno.

--Věroš

[zde]

Šak tohle se v praxi často a relativně bezbolestně distribuuje.. udělá se serverová farma, vepředu požadavky podle IP adres klientů rozhazuje nějaká proxy, nebo rovnou udělají rr dns. Ale normální desktop nebo interaktivní aplikaci (rozuměj s jedním uživatlem) paralelně obsluhovat nejde.