Názory k článku
Programovací jazyk LISP a LISP machines

Jako obvykle pěkný článek, byť netuším zda to ocení lidi bez zájmu o Lisp.

Mezi linky by možná patřilo velmi dobré Evolution of Lisp (třeba http://www.dreamsongs.com/NewFiles/Hopl2.pdf) od Gabriela a Steela (kdo se o Lisp zajímá, jména asi zná). Zaujalo mě tam třeba

the early MIT Lisp Machines in fact did not implement a garbage collector for
quite some years; or rather, even when the garbage collector appeared, users preferred to disable
it. Most of the programming tools (notably the compiler and program text editor) were designed
to avoid consing and to explicitly reclaim temporary data structures whenever possible; given this,
the Lisp Machine address spaces were large enough, and the virtual memory system good enough,
that a user could run for several days or even a few weeks before having to save out the running
“world” to disk and restart it.

Z tištěných věcí Hillsovo Connection Machine vydala Grada dokonce i v češtině (1993), ani mě nepřekvapuje že pak to bylo ve výprodeji za 10,–

No treba se za par let zjisti, ze soucasna technika (zvysovani poctu jader, ohackovana NUMA) mozna neni to prave orechove a jeste se s velkou slavou objevi „nova“ architektura, ktera se bude (nahodou :-) podobat Connection Machine. Napriklad transputery byly zalozeny na podobne myslence a nebylo to ve vysledku tak spatne.

Ono nejde ani tak o HW architekturu, jako programovací paradigmata. Procedurálním, či procedurálně-objěktovým programováním takovou architekturu nikdy nenaprogramujete (alespoň ne efektivně). Pokud by se začaly ve velkém používat funkcionální jazyky, tak by takováhle architektura mohla nabýt rozumného významu.

teoretickeho mozno, ale co prakticky vyznam?

GPGPU to umoznuje, nie?

Klasicka GPU architektura to prave moc neumoznuje, protoze stale pouziva rozdeleni na nekolik CPU a jednu operacni pamet. Rozhrani k pameti je potom uzke misto cele architektury. Muze to dobre fungovat pro 4 nebo s privrenim vsech oci osm jader, ale potom vykonnost dost klesa. Jedinym rozumnym a znamym resenim je „rozbiti“ pameti na mensi casti a prirazeni tech casti procesorum.

No mělo by se na to jít naopak, ne procesor vybavit pamětí, ale paměovou buňku vybavit procesorovou funkcionalitou. Stav paměťové buňky by pak závisel na jejích předchozích stavech. To by pak bylo přirozeně paralelní paradigma.

To je podobne pristupu, ktery se pouzival u transputeru – tam se vlastne jednalo o mikroradic, ktery byl navic vybaven komunikacnim rozhranim a specialnimi instrukcemi pro komunikaci se sousedy. ta komunikace je totiz skutecne hodne dulezita, vice nez vypocetni vykon.

urcity pokrok ale je videt. Sice se vetsina OS i komercnich aplikaci dela v proceduralnich jazycich doplnenych o objekty (C++, Java, C#), ale uz docela velka cast kodu je napsana neproceduralne, napriklad formou SQL dotazu, ktere v sobe (vetsinou) uz zadne sekvence neobsahuji a mohou byt provadeny paralelne. Taktez se hodne kodu presouva z proceduralnich jazyku treba do XML popisu, tam je take paralelnost „skryta“. Ale jinak musim souhlasit, s proceduralnim/ob­jektovym paradigmatem se paralelne programuje strasne tezko, takze sice na jednu stranu jsou programatori odstineni od nekterych low-level veci diky GC, na stranu druhou musi myslet na vlakna, zamky atd.

Duvody jsou vpodstate tri:

1) Velka cast uloh neni moc rozumne paralelizovatelna

2) U vetsiny uloh neni bottleneck CPU, ale IO (pristup k disku)

3) Zamykani resources mezi jednotlivymi ruznymi ulohami (programy) by bylo stejne nutne

1) tak to je otazka, na kterou mozna odpovi docela velky boom v paralelnich systemech postavenych o uroven vyse (=clouds), kde je uzlem nejenom procesor+pamet, ale vlastne cely pocitac, tazke procesor+pamet+dis­k. Spis bych rekl, ze tech neparalelizova­telnych uloh je malo a problem je hlavne v nasem pristupu k programovani a zavislost na stavajicich systemech a technologiich,

2) viz 1

3) urcite, to je samozrejme zapotrebi resit a neni to vubec trivialni, spis naopak – kdyz se tady udela chyba, tak se bud paralelni uloha „serializuje“ (ceka na resource) nebo dojde k nejake nepekne veci (deadlock, starvation)

prave z duvodu 1)2)3) si myslim, ze se v budoucnu budou cloudy programovat mozna v necem podobnem *LISPu (asi to bude mit jinou syntaxi, kdyz dnes leti XML-like jazyky, ale principialne se to asi bude podobat)

Ad 1) Řekl bych, že paralelizovatelných a dobře paralelizovatelných úloh je spíše menšina. Navíc u většiny úloh při paralelizaci přistupuje dosti vysoká cena za paralelizaci.

Nemyslím si, že se ujme to co je vhodné, ale že rozhodne to co bude chtít nejlevnější programátory, pokud se na tyto věci přejde masově. Tedy pokud to dokáže plus mínus naprogramovat student bez praxe, tak je to to co se ujme.

Právě největší překážkou paralelního programování není technika, ale to, že dobrý paralelní algoritmus chce rozmýšlení a tedy kvalitnějšího programátora i dražší výsledek. Navíc chyby ve špatně naprogramovaném paralelním algoritmu se dají špatně opravit, zvláště je-li špatně navržena komunikace mazi paralelními částmi a synchronizace – tedy opět to neudělají nejlevnější programátoři.

Až se ekonomicky zvládne, jak z rychlokvašnými a levnými programátory programovat paralelně, pak teprve to začne. To je IMHO pravý důvod dnešního stavu.

Ono paralelizovat lze prakticky vše, jen se na to musí jít jinak než imperativně. Bohužel, možná je to setrvačností, ale neimperativní myšlení je pro mnoho lidí problém. Na druhou stranu imperativní programování možná bude brzy tak hrozně neefektivní, že vznikne velká poptávka po jiných paradigmatech, což tento stav může změnit.

Tak když mi poradíte, jak zapojit neimperativní programování do řešení diferenciálních rovnic, byl bych povděčen.

Diferenciální rovnice řešit bohužel neumím, ale jsem přesvědčen, že solver psaný například v haskellu by mnohé napověděl.

Neodpustím si narážku na červeného trpaslíka:
Rimr: Ale jaký je rok:
Holy: K tomu potřebuji více údajů.
Rimr: Jako třeba?
Holy: Hodil by se letošní kalendář.

Tady jde o to, jak neimperatinvě zapíšeš to, že po sobš dosadíš asi tak do miliónu vzorečků, kde jeden jasně navazuje na druhý. A bude nabude to jen hraní si pro hraní?

No, obycejne diferencialni rovnice skutecne dobre paralelizovat nejdou, to je pravda. Ale mozna staci podivat se na ten problem z vyssi perspektivy, a pak to muze byt paralelizovatelne lepe. Napr. skutecny problem je, ze se pocita cely soubor ruznych reseni. Tuhle ulohu je uz mozne paralelizovat.

No, já mluvil spíš o parciálních diferenciálních rovnicích. Tam se paralelizovat dá, ale metody výpočtu jednoduše paralelizovatelné jsou bohužel ty nejpomalejší. Pokud se na to kouknu z hlediska praktického použití – dělí se na dvě verze: buď se spočte jedno řešení, které pak analyzuje projektant, nebo je to součást nějakého optimalizačního procesu. Jestli ten paralelizovat jde, nevím (nemám zkušenosti). Jednoduše se daly paralelně řešit lattice gas cellular automata, aly ty mají omezenou použitelnost. Takže zbývají lattice boltzman models, ale použít je na složitější materiály je stále trochu fyzikální magie.

„Ono paralelizovat lze prakticky vše, jen se na to musí jít jinak než imperativně.“

Souhlasím. S tím, že pro řadu algoritmů je nejefektivnější paralelizace na jednom vlákně (tedy neparalizovaně), což je speciální případ paralelizace. :-)

Paralelizovat jde vše, nicméně cena za paralelní zpracování, tedy efektivita bude mnohdy nižší, než v neparalelním. Často je efeftivnější neparalelizovaný algoritmus, než paralelní. A stává se to daleko častěji, než by si zastánci paralelního programování byli ochotni přiznat.

Mimochodem, Vaše předsudky jsou dost vidět i v tom, že pokládáte rovnítko mezi imperativní a paralelně neefektivní.

Tak nějak, přijde mi, že pan Program zatím moc reálných úloh nenaprogramoval (no offense).

Pokud pominu pár úloh pro funkcionální zpracování přímo dělaných, tak většinou je napsání „paralelně“ mnohem složitější ⇒ při stejných nárocích na spolehlivost dražší. A spolehlivost je dnes mnohem větší problém, než rychlost. A když už jde o rychlost, opět je větším problémem přenos dat z disku, než vytížení CPU. Samozřejmě jak kde, u určitých druhů vědeckých výpočtů je to zcela jistě naopak, ale v „business“ sféře si troufnu tvrdit, že je to vpodstatě všude stejné.

Hele, zrovna tohle čtu z postele v SFO Hilton Airport a za dvě hodiny začíná registrace na SF Bay Area Factory 2010 a musím se smát. Funkcionální jazyk pro paralelní programovaní? O Erlangu jste slyšeli? Problémy s row lock v cache SMP architektury? Co takhle immutable data a message passing s kopírováním dat. Tohle paradigma například na http://www.tilera.com/ čipech dává velmi zajímavé výsledky. Jistě, paralelizovat některé úlohy je problém. To bude vždycky stejně tak jako vyřešit některé úlohy vůbec. Ale například v oblasti serverových úloh je zátěž paralelní už ze své podstaty, takže ji stačí neserializovat omylem. Potřebuji obsloužit 1000 uživatelů? Mám 1000 paralelních úloh. Pokud bych i jednotlivé úlohy byl schopen dále paralelizovat, tak je to jen příjemné zlepšení, ale takové vlastnosti mají běžné úlohy naprosto přirozeně, staří je jen vidět. Vždyť svět je paralelní ze své podstaty. Lidská společnost funguje naprosto přirozeně na paralelním principu a pro svoji komunikaci používá message passing. Stačí jen programovat tak jak žijeme a nepoužívat umělé sériové algoritmy, které jsme se učili za posledních 40 let.

Hmmm, servrovým aplikacím věřím. Ale například vědeckotechnické výpočty řadíte do minority, nebo jste takový géniu, že je mu tam paralelizace a message passing jasný? Mně totiž tam přesně přijde přirozené sekvenční zpracování. Napřed spočítám jedno a pak druhé. Mimochodem v té vědecké práci je zrovna příklad velké daně za paralelizaci. Administrativa message pasingu zabere 90% času vědce.

Ano, v serverech (typicky webovych serverech) jsou ty ulohy paralelni z podstaty. A presto poptavka po nejakych extra masivnich paralelnich masinach pro tyto ucely moc neni. Takze problem bude asi jinde ;-)

Zrovna v tomto oboru to vypada no docela dobry kseftiky :-) Ono to opravdu chce definovat paralelni masinu – je to neco jako CM-5 s blikajicimi cervenymi LEDkami vsechno v jedne skrini (uvnitr jsou bezne „komoditni“ procesory) nebo nejaky cloud z milionu „komoditnich“ PCcek? Proste se jen zmenilo chapani slova uzel/node, dneska je to cele PCcko, takze se paralelizuje i ten zminovany pristup na disk.

Erlang je prece taky funkcionalni jazyk ne? Dokonce se snazi o minimalizaci side-efektu, jeste vic nez Lisp.

Tak proti tomu bych se ohradil (vzhledem k tomu, že jsem například vyvýjel pro Standforskou univerzitu), ano z diferenciálních rovnic si toho už moc nepamatuji (nikdy jsem to nepotřeboval). Ale problém je v něčem jiném. Pořád se tady točíte kolem stejné věci. Většina algoritmů je psána v imperativním stylu a většina lidí si to ani neuvědomuje. Vy chápete programování ve stylu: „Teď se udělá tohle, pak tohle…“ To je imperativní přístup a tam se objevují problémy s obtížnou paralelizací a taky spolehlivostí. Funkcionální paradigma je paralelní implicitně, protože tam je jasné, co je na sobě závislé a co se může vypočítat paralelně.
Ještě jednou to zopakuji funkcionální programování se neparalelizuje žádnými příkazy ve stylu vytvoř vlákno, či pragmaty, nebo podobnými věcmi (např. MPI), tak už to těmihle tvrzeními laskavě nevyvracejte.

Nevyvracím Vám, že jsou problémy, které se dají pohodlně zapsat neimperativně. Ale tvrdím, že jsou problémy, které se paralelizují obtížně. Třeba stavba domu. A jsou to bohužel velmi výpočetně nákladné problémy.

Ale ono tech paralelizovatelnych uloh je praveze dost, akorat na soucasnem hardware je nema cenu realizovat. Stejne jako nemelo cenu realizovat paralelni rendering v dobe, kdy graficke karty mely jedno GPU. Dneska s prokladanim apod. to uz neni problem, naopak je to vyzadovano.

Samozrejme souhlas, ze resit na soucasnych jazycich paralelni algoritmy chce lepsiho programatora, ale vsak oni se to budou muset naucit. Kdyz nastoupilo OOP, taky nakonec vsichni presli z proceduralnich jazyku na jejich OO-nasledovniky (i kdyz pri pohledu do kodu to nekterym trvalo dele :-)

A u tech procesu, ktere maji bezet paralelne se to jiz dnes resi treba jiz zminenym cloudem, load-balancingem atd. atd.

Ja programujem v DataFlow jazyku LabVIEW.

A s paralelnym programivanim nie je problem.
Ale samozrejme, ze ked chces poslat data z jedneho „vlakna“ do druheho tak musis pouzit queue alebo semafor.

vyhodou funkcionalnych jazykov, napriklad lispu, alebo haskellu je v tom, ze ak sa dodrzia pomerne jednoduche pravidla, uloha sa stane automaticky paralelizovatelna samotnym runtime-om (ak by pre tuto platformu existovala podpora priamo v HW, tak by paralelizovat ulohu dokazal samotny procesor).

Celou dobu si rikam neprispeju a neprispeju, protoze nic konstruktivniho k veci nemam, ale toto je takova blbost, ze musim. Ne – paralelizovatelnost je vlastnost algoritmu, runtime neruntime, spousta uloh je proste neparalelizova­telnych (oplodnenim 9 matek neziskate dite za mesic)

ok, nepochopili sme sa, tak rozvediem:
nech a(), b(), c(), d(), e() su politicky korektne funkcie, ktore nemenia, ani nezohladnuju globalny kontext.

a nech sa v programe nachadza volanie:

a( b( d() + e()), c( d() – e()))

ked sa to evaluje zvonku dnu, zacne sa pri a, kde sa zisti, ze su 2 argumenty nezavisle na globalnom kontexte, takze az je toho runtime a hardware efektivne schopny*, moze ich evaluaciu vykonat paralelne.

zacne sa paralelna evaluacia volani b a c, kde sa dokonca da optimalizovat tym, ze sa hodnota d a e spocita len raz (v kazdom vlakne len jedna) a hodnota sa potom distribuuje. v takom pripade moze vlakno pre evaluaciu b pocitat trebars d, vlakno pre evaluaciu c zasa e.

naproti tomu a( b( c( d( e())))) sa paralelizovat neda.

* – a tym nemyslim x86 SMP

Na takovyhle reci Seymour Cray odpovidal:

‚If you were plowing a field, which would you rather use?… Two strong oxen or one thousand twenty four chickens?‘

Dokonce i v ty knizce o CM-1 si na konci povzdechnou jaky problemy delala propojovaci sit (nejen fyzicky, ze to bylo mnoho vodicu, ale samotne smerovani a hlavne cekani na zpravy zabralo vic casu nez si na zacatku predstavovali).

Na druhou stranu, vzhledem k tomu ze taktovaci frekvence CPU uz zhruba 8 let stagnuje, vnitrni paralelizaci (pipelining/su­perskalarita/SIM­D) uz taky asi nema cenu zvysovat vic nez 2*, tak to vypada ze se nakonec dockame architektury ‚1024 strong oxen‘.

Nemyslim ale ze se to bude programovat jako CM-1, ktera mela pomerne fine-grained paralelizmus (coz byla dan za velmi jednoduche procesory).

Ja bych tedy bral tech 1024 kurat :-) kdyby se daly stejne spolehlive (v tom je prave problem toho prirovnani, ze to neodpovida skutecnemu „seriovemu“ vs „paralelnimu“ pocitaci).

Pravda je, ze CM-1 a CM-2 byly navrzeny dosti rigidne jako proof of concept jednoduchych neuronu a slozite propojovaci site, takze se to tvurcum trosku vymstilo (mozna nemeli delat 12dimenzionalni krychli ale treba „pouze“ 4D torus). Taky to vychazelo z tehdejsich moznosti, takze porovnavat 25 roku starou CM-2 s dnesnim osmijadrem nesedi uz kvuli zcela odlisne technologii. Ale dokazu si predstavit, ze by se podobnym zpusobem pozapojovalo napriklad 1024 MIPSu s vlastni pameti dejme tomu 16 MB, aby se kopie dat nemusely delat tak casto (ten 1 kB v CM-2 je z dnesniho pohledu uz skoro smesny).

*LIST (StarLisp)

Mam dojem, ze nejakou CM-x (asi 5) meli i v Praze na CVUTu. Je to tak nebo se jedna o urban legend?

To ne. To spíš někdo neznalý zaměnil s clusterem IBM SP2, který na ČVUT je.

Ale taký ATX case à la CM-5 by som bral hneď…

Vzhledem k tomu ze : „Thinking Machines Corporation went bankrupt 1994…“ (http://en.wikipedia.org/wiki/Thinking_Machines) tak nam matrix nehrozi :D.

Pekny pribeh o stvoreni connection machine je zde; http://www.kolej.mff.cuni.cz/~lmotm275/RUZE/11/node9.html#SECTION00090000000000000000

alebo original http://www.longnow.org/essays/richard-feynman-connection-machine/

CM-5 v akci.