Schemik goes to open source

26.6.2007 20:38 | Přečteno: 1646× | Programování | | poslední úprava: 27.6.2007 12:25

pred casem tu probehl tradicni flame na tom jaka licence je nejlepsi... je mi to uprime jedno... ale spis jsem si rikal, ze uz jsem dlouho nic "rozumneho" "nevyprodukoval".

nicmene, jelikoz uz pres rok programuju jako diplomku implicitne paralelni implementaci schemu (viz zatim nedokonceny serial) a vzhledem k tomu, ze obhajoba se blizi milovymi kroky... tak uz to zacina byt i pouzitelne. pokud mate tedy zajem -- studujte, kompilujte, uzivejte -- schemik-0.5.0.tar.bz2 (pro ty co by zajimala licence... spravna odpoved zni: "MIT")

update - pro upresneni: implicitne paralelni interpretr se chova jako kazdy jiny interpretr s tim rozdilem, ze dokaze beh kodu rozdelit do vice samostanych vlaken a vratit stejny vysledek (jako normalni interpretr), bez toho aniz by bylo nutne nejak menit kod, resit vlakna, synchronizaci, atp. samozrejme, aby to bylo uzitecne je potreba mit viceprocesorovy pocitac.

Features

• podporuje vsechny zakladni vlastnosti -- tail-cally, makra (vyjma hygienickych), call/cc -- a s temi uz jde delat spousta zabavnych veci, ze kterych byste si nejradsi hodili kabel
• minimalni mnozstvi funkci z R5RS -- dopisovat si je, je proste radost a zabava
• i na viceprocesorovych strojich je to pomalejsi nez vetsina ostatnich implementaci -- cekat na vysledky je proste zabava

Installation

jedine co potrebujete je nejaky hezky SMP stroj, unixovy os s GNU nastroji a trocha znalosti schemu. a hlavne napsat make

Usage

pouzivani je proste jak bulharska stripterka:

spusti repl s danym poctem vlaken:

./schemik -t <pocet-vlaken>

provede prikaz s danym poctem vlaken:

./schemik -t <pocet-vlaken> -c "(display (+ 1 1))"

provede progvram s danym poctem vlaken:

./schemik -t <pocet-vlaken> -s scm/quicksort.scm

Screenshots

screenshoty jsou brane na 2x opteronu 265 (2 jadra kazdy) s 4 GB ram.

30. fibbonacciho cislo v jednom vlakne

time ./schemik -t 0 -q -c "(define (fib x) (if (< x 3) 1 (+ (fib (- x 1)) (fib (- x 2))))) (display (fib 30))"
832040
real    0m2.782s
user    0m2.772s
sys     0m0.012s

30. fibbonacciho cislo s peti vlakny

time ./schemik -t 4 -q -c "(define (fib x) (if (< x 3) 1 (+ (fib (- x 1)) (fib (- x 2))))) (display (fib 30))"
832040
real    0m1.410s
user    0m4.596s
sys     0m0.160s

setrideni 100000 pseudonahodnych cisel quicksortem a jednim vlaknem

time ./schemik -t 0 -s scm/quicksort.scm
real    0m26.475s
user    0m26.418s
sys     0m0.056s

setrideni 100000 pseudonahodnych cisel quicksortem a sesti vlakny

time ./schemik -t 5 -s scm/quicksort.scm
real    0m15.592s
user    0m27.774s
sys     0m2.152s

Documentation

zatim skoro zadna, ale pracuje je se na ni! vzhledem k memu sveraznemu lingvistickemu citeni bude az po korekturach. ;-]

Zustante naladeni!

btw. co jste udeli se svou diplomkou/bakalarkou/dizertaci?        

Anketa

Obrázky

Komentáře

[freshmouse]

Kdybych chápal, o co jde, určitě by se mi to líbilo. takhle máš bod za tu striptérku.

[deda.jabko]

opet je to proste, jak vyse zminena stripterka... (nicmene asi to jeste do clanku doplnim, protoze ten nazev je fakt takovy netrivialni)

implicitne paralelni interpretr se chova jako kazdy jiny interpretr s tim rozdilem, ze dokaze beh kodu rozdelit do vice samostanych vlaken a vratit stejny vysledek (jako normalni interpretr), bez toho aniz by bylo nutne nejak menit kod, resit vlakna, synchronizaci, atp. samozrejme, aby to bylo uzitecne je potreba mit viceprocesorovy pocitac.

[David Watzke]

Zkusil jsem si to, i když na to nemám CPU

$ time ./schemik -t 0 -c "(define (fib x) (if (< x 3) 1 (+ (fib (- x 1)) (fib (- x 2))))) (display (fib 30))"
832040
real    0m3.435s
user    0m3.191s
sys     0m0.047s

$ time ./schemik -t 1 -c "(define (fib x) (if (< x 3) 1 (+ (fib (- x 1)) (fib (- x 2))))) (display (fib 30))"
832040
real    0m3.464s
user    0m3.150s
sys     0m0.056s

$ time ./schemik -t 5 -c "(define (fib x) (if (< x 3) 1 (+ (fib (- x 1)) (fib (- x 2))))) (display (fib 30))"
832040
real    0m3.589s
user    0m3.242s
sys     0m0.082s

A to se vyplatí Každopádně seš těžkej šéf, obdivuju tě.

[deda.jabko]

diky! bohuzel to potrebuje vic procesoru (resp. jader)... ono se to sice rozbehne do vice vlaken, ale jelikoz je ten procesor na to sam... tak ho prepinani mezi temi vlakny jenom zdrzuje :-/

[thingie]

Hm, a jak to zhruba dělá? To je nějaká brutální teorie k tomu, nebo něco celkem normálního?

[deda.jabko]

az budu mit chvilku casu, chtel bych to sem dopsat...

ale moc vyrazna teorie zatim neni. napriklad pri pocitani fibbonacciho cisla (lambda (n) (+ (fib (- n 1)) (fib (- n 2))) to rozlozi na operace +, (fib (- n 1)) a (fib (- n 2))... aby mohl provest soucet zjisti, ze je potreba pocitat (fib (- n 1)) tak jej zacne pocitat... kdyz planovac zjisti, ze se to pocita nejak dlouho podiva se, jestli by neslo neco vypocitat v novem vlakne... a zjisti ze by mezi tim mohl spocitat (fib (- n 2))... tak to spocita...

cele je to reseno pomoci upraveneho zasobnikoveho modelu od doc. vychodila, palacky university ;-], kterym trapil prvaky. (slibil jsem, ze budu uvadet kredity a odkazy na "nase pracoviste" ;-])

...cast jednovlaknoveho vyhodnocovani je popsana tady, popr. v originalni slidech ...krome toho, ze tento model je strasne jednoduchy a pomaly, jde v nem prave velice snadno delit vypocet do vlaken a ovladat jeho prubeh v case... vcetne krasnych veci jake je call/cc

[Tom.š Ze.le.in]

A nemá to problém s funkcema, které mají vedlejší efekty (např. kdyby fib hloupě memoizovalo)? I když ve Scheme vlastně není požadované sekvenční vyhodnocování parametrů funkcí, ale nevím jestli se nepředpokládá atomicita vyhodnocování parametrů... Totéž u níže zmíněného mapu - v CL je v popisu takových funkcí, že musí aplikovat funkci na jednotlivé parametry postupně za sebou, Scheme to nechce?

[Tom.š Ze.le.in]

s/parametry/prvky sekvence/

[deda.jabko]

zajimava otazka.... R5RS o tom rika toto:

Although the order of evaluation is otherwise unspecified, the effect of any concurrent evaluation of the operator and operand expressions is constrained to be consistent with some sequential order of evaluation. The order of evaluation may be chosen differently for each procedure call.

moje implementace vyhodnocuje vsechny vyrazy z leva doprava, jako rada "prumyslovych" interpretru a prekladacu a snazi se vracet stejne vysledky.

ale zastavim se nachvilku u tech side-effectu, protoze s nima je to slozitejsi. jednou z vlastnosti je, ze funkci se side effectem muze provadet hlavni vlakno vypoctu, pokud se objevi nejaky side-effect v pomocnem vlakne je zastaveno (a rozpocitany stav si v budoucnu prebere hlavni vlakno). napr.

(let ((foo (lambda () (display "aaa"))))
  (foo)
  (display "bbb")
  #f)

pokud by napriklad pomocne vlakno chtelo vyhodnotit (display "bbb") ma smulu, protoze nejdriv musi byt vyhodnoceny vsechny vyrazy pred nim.... co kdyby (foo) obsahovalo nejaky dalsi side-effect.

se set! je to jeste slozitejsi.... krome toho, ze ma side-effect, tak nepekne ovlivnuje beh aplikace.

(define global 1)
(let ()
  (foo)
  (set! global 2)
  (+ global (bar)))

pokud by (foo) a (bar) byly pomale funkce mohl by nastat stav, ze by se treba vyhodnotil vyraz (+ global (bar)) driv nez by se provedlo vyhodnoceni (set! global 2) a diky tomu by se vratil chybny vysledek. tento problem resim tak, ze pokud za operaci typu set! jsou nejaka pomocna vlakna s rozpocitanymi vysledky, tak jsou nemilosrdne zahozena a musi pocitat od znovu -- ano je to plýtvani, ale da se tomu vcelku uspesne branit v planovaci, ktery nepovoli spustit paralelni vypocet za operaci set!

jenom jeste doplnim dva bonbonky, ktere me docela prakvapily -- vstupni funkce napr. (readline) a escape funkce z call/cc maji stejne chovani jako funkce se site-effectem... kdo by to cekal? ;-]

[Tom.š Ze.le.in]

Jo, takhle to celkem dává smysl, jen nechápu dělení side effektů na set! a ostatní - read-něco taky může změnit hodnotu peek-char a způsobit špatný výsledek pomocné funkce.

Výstupní fuknce jsou taky IMHO side-efektové:

(labels ((a 'a) (b 'b))
  (foo
    (lambda (print "a: ") (print a))
    (lambda (print "b: ") (print b))))

by asi nemělo vypsat a: b b: a.

Což mi přijde při takovéhle implementaci jako problém, protože pokud přidání ladicích výstupů způsobí změnu dělení na streamy, tak si moc nepoladím...

[deda.jabko]

jak jsem psal vstupne/vystupni funkce se chovaji jako se sideeffect (teda u vystupnich jsem to explicitne nepsal, protoze je to vicemene zjevne ;-])... diky tomu razeni se vsechny operace provedou v pozadovanem poradi...

se set! je to slozitejsi... kdybychom pocitali s tim, ze kazde cteni z heapu musi byt pred pripadnou modifikaci v danem poradi, moc paralelizovat by to neslo -- proto optimisticky predpokladam, ze heap bude vicemene konstanti... a pokud dojde k nejakemu uletu (set!) runtime by se s tim mel umet korektne vyporadat....

s tim ladenim bych tak ani moc strach nemel... cilem (implicitne paralelnich interpretru) je, aby vypocet daval stejne vysledky jako u normalnich interpretru jenom pripadne vyuzil vice vlaken... rozdil nakonec bude jenom ve zpusobu vyhodnocovani (ktere navic ani nejde z programu pozorovat)... a pokud si do programu dopisete ladici informace... pobezi jen pomaleji, ale vysledky budou stejne....

[thingie]

Hm, mozna ted budu trochu mimo, ale umi to nejak ty vysledky kesovat? Takhle udelane fib by tomu (jestli jsem se straslive nespletl) pomohlo, ne?

[Lu-Tze]

Pomohlo. Otázka je, jestli by kešování pomáhalo i při dobře napsaných programech.

Nerozumím tomu, proč autor svou práci prezentuje na takovémhle hnusu. Nebylo by lepší ukazovat přednosti a vlastnosti na skutečně použitelných programech?

[thingie]

No tak je to velmi jednoduchy kousek kodu, tak mi to jako zase tak spatny priklad neprijde, protoze je na tom videt jak to funguje. Ze to je krom toho k nicemu, to zase hned tak nehori. Je tam treba ten quicksort, i kdyz tam to asi pravda bude s kesovanim horsi.

[deda.jabko]

to je otazka... fibonacciho cisla, ac pocitana naprosto hloupym zpusobem, jdou velice hezky paralelizovat a dostat se tak vicemene na dren za vsech okolnosti (planovac, atd.) a uvadim je z toho duvodu jako jeden z referencnich testu.

problem "realnych prikladu" je v tom, ze casto obsahuji moc velke mnozstvi promennych komplikujicich opakovene testy, nebo obsahuji hodne kodu, ktery nejde paralelizovat...

napr. v prikladu s quicksortem se musi nejdriv vypocitat posloupnost pseudonahodnych cisel... coz zabere cas a pokazi "hezky vysledek" paralelizace

nicmene, byl bych moc rad, kdybyste mne navrhl nejake opravdu "pouzitelne priklady"... napiste nejaky napad, poslete zdrojaky... fantazii se meze nekladou..

btw. pokud byste si chtel vic pohrat s vyhodnocovanim... tak napr. v souboru scm/matrix.scm jsou zakladni operace pro ctvercove matice...

[deda.jabko]

kesovani? ja nevim jestli je to spravny pristup, ale vypocet fibonaciha cisla, jde velice snadno prepsat do koncovych volani:

(define (fib-iter a b n)
  (if (= n 0) a
      (fib-iter b (+ a b) (- n 1))))
(define (fib n)
  (fib-iter 0 1 n))

ale tam by se ztratila ta pointa... urcite to potrebuje vetsi intelektualni zatez pro programtora ;-]

[Tom.š Ze.le.in]

A rozkládat to transparentně na procesy běžící na více počítačích na síti to bude časem taky? :)

[deda.jabko]

puvodne to bylo v planu jako pripadny "upgrade", kdyby toho bylo malo...

urcite to neni spatny napad a neco takoveho by se me libilo... jenze... napsat distribuovany heap by byl docela ulet -- stacilo by sdilet jenom pocatecni a aktualni prostredi.... ale co na to takovy garbage collector? ;-]

hlavni problem je ale v tom, ze procesy (natoz tak po siti) maji velkou rezii a nez by u normalnich programu neco spocitaly, uz by to bylo zbytecne... resp. nevyplatilo by se to distribuovat. s tim souvisi, ze by bylo nutne napsat opravdu kvalitni planovac, ktery urcuje, kterou cast distribuovat (aby se to vyplatilo).... coz je docela tezke az nemozne... coz vede na dve reseni

+ hinty prekladaci (tim se ztraci vyhoda implicitniho vyhodnoceni)

+ vhodne algoritmy ... ve kterych planovac pozna co a jak ma paralelizovat (nejlepe - pouzivat na vsechno "map"), ale to uz se pak vyplati pouzit nejaky framework na bazi map-reduce

btw. osobne si myslim, ze tesne vazane systemy budou mit cim dal tim vetsi uplateneni a "problem" ten vykon vyuzit -- dvou jadrove procesory jsou dnes bezne v low-endu, ctyr jadrove nejsou zase takove exotika a kdo chce neco super poridi si ultrasparc t1 (8 jader - kazde 4 vlakna) ... a ted si k tomu predstavte ty programatory s jakym nadsenim se pousteni do vytvareni vlaken a jejich synchronizace pomoci mutexu a podobnych primitiv, aby ukazali ze jejich program je rychly...

[andree]

moja bakalarka bol 3d simulator alla need for speed... Lord knows ze EA by to asi nepredala ani za 50 Kc per kopia

[disorder]

dependency -- libgc-dev

$ time ./schemik -t 0 -s scm/quicksort.scm
./schemik -t 0 -s scm/quicksort.scm  18.74s user 0.04s system 99% cpu 18.948 total

$ time ./schemik -t 1 -s scm/quicksort.scm
./schemik -t 1 -s scm/quicksort.scm  17.85s user 0.12s system 144% cpu 12.471 total

[deda.jabko]

to docela jde... nekdy tomu pomuze dat i vic vlaken, nez je jader... v tomto pripade se evidentne planovac neobtezoval zatizit oba procesory na 100% ;-]

[disorder]

v tomto pripade ani nie, skusal som

$  time ./schemik -t 5 -s scm/quicksort.scm
./schemik -t 5 -s scm/quicksort.scm  19.59s user 0.12s system 136% cpu 14.475 total

$  time ./schemik -t 1 -s scm/quicksort.scm
./schemik -t 1 -s scm/quicksort.scm  17.82s user 0.13s system 134% cpu 13.393 total

[deda.jabko]

hm... docela dobry rozptyl ;-] muzu mit zvedavy dotaz -- jaky mate hardware? dualcore nebo vice procesoru? desktop/server/notebook?

[disorder]

core 2 duo notebook

[disorder]

a je to amd64 etch

[deda.jabko]

:-/ ja mam "jenom" core duo ;-]

nicmene na tech centrinech jsem si vsiml zajimave tendence regulovat teplotu za kazdou cenu -- kdyz se pocita delsi dobu na obou jadrech, zacnou se vypinat nebo zpomalovat, ci co se tam deje a namerit nekolikrat stejne vysledky je docela problem na rozdil treba od servrovych procesoru...

[disorder]

je to mozne, ale mne sa zastavuje teplota az pri 60°C :)

naozaj sa vysledky lisia, ale od teploty to len tak nebude -- toto su vysledky hned po sebe (hodnoty su pri opakovani priblizne rovnake), obe pri rovnakej zaciatocnej teplote. zaujimave :)

./schemik -t 5 -s scm/quicksort.scm 19.83s user 0.16s system 138% cpu 14.417 total ./schemik -t 1 -s scm/quicksort.scm 18.06s user 0.12s system 136% cpu 13.313 total

./schemik -t 1 -s scm/quicksort.scm 17.88s user 0.14s system 135% cpu 13.305 total ./schemik -t 5 -s scm/quicksort.scm 19.21s user 0.16s system 142% cpu 13.552 total

[disorder]

sakra.

./schemik -t 5 -s scm/quicksort.scm  19.83s user 0.16s system 138% cpu 14.417 total
./schemik -t 1 -s scm/quicksort.scm  18.06s user 0.12s system 136% cpu 13.313 total

./schemik -t 1 -s scm/quicksort.scm  17.88s user 0.14s system 135% cpu 13.305 total
./schemik -t 5 -s scm/quicksort.scm  19.21s user 0.16s system 142% cpu 13.552 total

[deda.jabko]

zajimave, je to docela reprodukovatelne, takze v tom bude neco jineho... myslim, ze k takovym vysledkum by se melo pristupovat radne vedecky.... oznacime je tedy za statistickou odchylku ;-]

btw. resit u opakovaneho vypoctu teplotu me ani nenapadlo... ale s postupem casu to bude asi nutnosti... a to jsem se smal sasovi vondrovi, ze mohl v letech 1988-1989 pracovat jako "topič, programátor" ;-]

[kaaja]

O Schemuu nic nevim, ale zajimalo by mne, jak se takovy algoritmus jako vypocet fibonnaciho cisla rozlozi do vice vlaken. Me osobne to zrovna neprijde jako dobre paraelizovatelna uloha.

[deda.jabko]

prave ze ne.... vypocet je zalozen na tom, ze se scitaji rekurzivne dve predchozi cisla... kde vypocet kazdeho cisla trva "strasne" dlouho... ve (+ (fib (- n 1) (fib (- n 2)) kazde cislo si muze pocitat samostatne vlakno aniz by se nejak ovlivnovali....

tento zpusob vypoctu je fakt hloupy a jde bez problemu prepsat do koncovych volani, kde se budou predavat jiz spocitana cisla.... algoritmus to bude pak velice efektivni... ale neparalelizovatelny....

jenom pro zajimavost -- kdyz dam "planovaci" volnou ruku a povolim mu 100 vlaken, aby ukazal jak moc jde uloha paralelizovat, tak u fibonaciho cisla vyuzije skoro vsechny, kdezto u quicksortu ma problemy. (btw paralelizovatelnost ulohy je dana nejen typem algoritmu, ale i vstupnimi hodnotami)

[nooneanymore]

Trošku si rejpnu. Ačkoliv problematice nerozumím a zápisek jsem zběžně prohlédnul, jedno vím jistě: v grafech chybí popisky. Vím, že abclinuxu není vědecký časopis, ale dodržujme štábní kulturu.

[deda.jabko]

souhlasim... jsou to jenom narychlo vygenerovane grafy, pro vysvetleni v predchozim prispevku