From bbs@floyd.upol.czMon Jan 29 16:27:14 1996
Date: Mon, 29 Jan 1996 16:25:47 +0100
From: BBS Floyd <bbs@floyd.upol.cz>
To: hubicka@limax.paru.cas.cz
Subject: Skolicka #9-paraelni programovani (fwd)

*** Forwarded file follows ***

Posted By: kotelnik (kotelnik) on 'Linux'
Title:     Skolicka #9-paraelni programovani
Date:      Mon Jan  8 13:19:30 1996

Ja vim ze to sem moc nepatri ale paraelni programovani je moc zajimava
vec a ma jistou budoucnost. Proto bych rad ukazal jak neco tak divokyho
jde udelat v lispovi. Slibuju ze uz toho lispareni necham a budu se
venovat necemu pouzitelnejsimu. Ale tohle si proste nemuzu odpustit.
Bude treba aby jste si predem precetli clanek o cm na cool/vzdelani. Je
to o tom jak takovy masivne paraelni pocitac vypada. Ze to rozhodne neni
8 pentii co se hardwarove deli o jeden tok instrukci. Nebo kazde provadi
jeden proces. Ze to ani neni 10 pocitacu navzajem spojenych scsi kabelem
jak to chce udelat linux. Pocitace co tam popisuju maji vykon vetsi nez
1000 mips(to mel prototyp cm-1 z roku 1983). Cm-5 ma  priblizne 1
TFLOPS.  A pritom to vetsinou nejsou zadne salove obludy-cm 1 i cm 2
jsou krychle o strane 1M chlazene vzduchem takze o neco vetsi normalni
pocitac.  Posledni navrzeny prototyp CM-8 by stal neco okolo 10 milionu
dolaru ale mel by stejnou kapacitu jako lidsky mozek a pritom tisickrat
veci vykon.  To by znamenalo ze by ciste teoreticky takovy stroj mohl
myslet jako clovek.  Jinak se takovehle masiny vyuzivaji na realtime ray
tracing, zpracovani dat z kosmu, ruzne zpracovani obrazu, realtime
testovani novych procesoru- umi hardwarove naemulovat pentium(tedy kazdy
tranzistor a drat)  na 10 megahercich. A podobne veci o kterych se nam
ani nezda. Ani komercne to nejsou tak neuspesne pocitace-do roku 1992
jenom modelu cm-2 bylo prodano kolem 80 a roste to! Ja mam pristup na
cm-2 kde delam kratsi programky treba na realtime kompresi dat ziskanych
z kosmu a podobne nesmysly. Kvuli tomu jsem se vlastne naucil lisp.

(budu se tu drzet skvele knizky the connection machine od Hillise
kterou v ceske verzi vydala grada. Kazdemu ji doporucuju)

Takze CM lisp je lisp upraveny tak aby svoji strukturou se co nejvice
podobal hardwaru cm. Jako normalni lisp odpovida normalnimu hardwaru.
Jak pise Hillis:"CmLisp je rozsireni Common Lispu, navrzene pro podporu
paraelnich operaci na pocitaci CM. Ma byt pro pocitac CM tim, cim je
lisp pro seriovy pocitac: vyrazem podstatnych rysu architektury, ktera
vypousti detaily implementace. Cmlisp je abstraktni verzi pocitace CM ve
stejnem smyslu, jako jsou fortran nebo lisp abstraktimi verzemy
konvencniho pocitace" Cm lisp je konzervativni paraelni jazyk. Stejne
jako clos je konzervativni objektovy jazyk-spojuje vyhody
struktorovaneho a objektoveho jazyka narozdil treba od smalltalku. Tak i
cmlisp spojuje vyhody sekvencniho a paraelniho programovani-to vychazi z
toho ze cm je rizena klasickym nadrazenym pocitacem takze cast toho
programu je interpretrovana rovnou na tom pocitaci a cast na cm.  Pro
takovy nekonzervativny jazyk si prostudujte dokumentaci APL nebo FP.  Je
ale zvlastni ze programy v cmlispu se pisou snadneji a jsou vykonejsy
nez programy psane v APL.

Proc lisp?
==========

Byly dva duvody: prvni ze cm byl vyvinut pro cleny komunity umele
inteligence kde vsichni uz lisp znali protoze lisp byl vyvinut pro ne.
Ten druhy dulezitejsi je protoze lisp je rozsiritelny, ma dynamickou
alokaci pameti a je vseobecne dobry pro symbolicke manipulace.  A
existuji programova prostredi pro lisp. Vetsina myslenek je na lispu
nezvyslych a proto byly pozdeji vyvinuty i dalsi jazyky: C* lisp* a
fortran*. Lisp* je uz trochu brutalnejsi rozsireni lispu ktere se
poucilo z nekolika nedostatku cmlispu. A to ze cmlisp pouzival znaky
mimo asci kod-alpha beta a puntik. Ale vzdasade je to to samy pouze
umoznije nektere figly jako pametove indukovane site. Ostatni jazyky
jako C* jsou upravami klasickych jazyku ale nedopadly moc dobre.  Proto
se stejne vesele pouziva lisp.

Xetory
======

Protoze nadrazeny pocitac je ten co provadi program pouze obcas si
nejaka data odhodi do pocitace cm kde snima neco robi je jasne ze je
treba nejaky typ pomoci neho by se dalo do cm ukladat. Kdyz se koukneme
na cm je to vlastne fura procesoru kde kazdy ma vsobe jeden objekt a ty
se muzou navzajem propojovat a shlukovat se do nejakych mnozin. Od toho
byl vytvoren typ xetor. Vsechna data ulozena v xetoru jsou v cm. Takze
se nad nimi daji provedet paraelni operace jako ruct sectete se nebo
najdete mi ahoj. Samozdrejme ze by to slo delat i na normalnim pocitaci
ale bylo by to pomaly. Xetor tedy muze obsahovat mnozinu objektu. Ale
navic umi zaznamenat spoje mezi nima. Xetor se zapisuje takto:

{SKY->BLUE GRASS->GREEN APPLE->RED} 

Takze je tu mnozina prcku ulozenych v cm a xetor udava mezi nima spoje
neboli asociace. Xetor trochu pripomina asociovane pole nebo hasovaci
tabulku. Ma mnozinu indexu-SKY,GRASS,RED ty se rika jako u funkci
definicni obor(domain). Ma take monzinu prvku - obor hodnot(range) a
zobrazeni mezi nimi.

Xetor nema dane poradi prvku
takze se muze vypisovat prehazene. Na pocitaci CM je kazdy prvek ve
zvlastim procesoru a indexem je adresa jineho procesoru. Xetor ma i jine
zapisy:
{A->A 1->1 2->2} je stejne jako {A 1 2}
Take lze psat jako pole:
{0->A 1->B 2->C 3->D} je [A B C D]
Taky tu je konstantni xetor co vsechno zobrazuje do jedne hodnoty
{->2}

Vytvareni, cteni a modifikovani xetoru:
=======================================

Normalne napsat:

(SETQ COLOR-OF '{SKY->BLUE APPLE->RED GRASS->GREEN})
=> {APPLE->RED GRASS->GREEN SKY->BLUE}

Vypisovani xetoru je vzdy nejak usporadano-abecedne,rostouci cisla apod.
Funkci xref muzeme zjistovat hodnoty indecu:

(XREF COLOR-OF `APPLE)  => RED

Stejne muzeme hodnoty nastavovat XSETEM

(XSET `BLUE COLOR-OF `GRASS)

COLOR-OF => {APPLE->RED GRASS->BLUE SKY->BLUE}

XSET nepridava novy index to se dela funkxi XMOD. Protoze xetory jsou
vlastne funkce cmlisp snimi tak umi pracovat treba delat inverzni
xetory.  Ma tedy funkce RANGE co vybere jen indexy,DOMAIN co vybere
prvky a INVERZE co xetor obrati. Taky samozdrejme umi prevadet xetory do
listu, asociovanych listu apod. Dale je umi brat jako sekvence a delat
nad nima bezne operace jako nad polema,alisty,listy a hasovacima
tabulkama tedy treba search a delete. Ty ale probihaji paraelne takze jsou
rychlejsi:
Tabulka casovych zavislosti:
Operace     Vektor  List  Xetor
ELT            1      N     1
LENGTH         1      N     logN
SUBSEQ         1      N     logN
COPY-SEQ       N      N     1
FILL           N      N     1
REMOVE         N      N     1
DELETE         N      N     1
REPLACE        N      N     logN
COUNT          N      N     logN
REVERSE        N      N     logN
POSITION       N      N     1
REDUCE         N      N     logN
SORT           NlogN  NlogN logN*logN
SEARCH         N      N     1
tady vydite ze mimo sortu jsou slozitosti bud 1 nebo logn. Ty co maj 1
jsou jednoduche-proste vsechny prvky udelaji nejakou operaci-treba se
vynuluji u fill.  LogN spociva vtom ze treba kdyz vsechny chceme secist
secteme nejprve vsechny dvojice tim vznikne N/2 vysledku ty po dvojicich
taky secteme.  Tedy jedeme po binarnim strome a cosova slozitost se
rovna hloubka stromu je dvojkovy logaritmus tedy 65536 cisel mame
secteno na 16ti scitanich.  To je fofr co? Trideni je slozitejsi mozna
ho taky popisu.

Jak se takove funkce delaji? verte nebo ne pomoci dvou hloupych
operatoru:

Alfa notace:
============

No a uz zacneme paraelnit. Alfa notace je to co umoznije psat operace co
maji slozitost 1 tedy vsichni udelame to a to. Cmlisp alpha pise jako
recke pismeno a pouziva ji asi jako lisp ' tedy misto aby se psalo
(alpha 1) napise se recka alpha 1. To tu psat nemuzu takze misto neho
budu psat A a kdyz by se to pletlo tak pekne alpha. Alpha se pouziva na
konverzi hodnoty na konstantni xetor tedy A1 je {->1} kdyz je alpha pred
vyrazem vyraz se vyhodnoti a potom se zneho udela konstantni xetor.

A3   => {->3}
A(+ 1 2) => {->3}
A+   => {->+}

Tim se moc paraelizmu neudela a tak je tu figl. Kdyz na miste funkce je
xetor funkce tedy A+ misto + je pri vyhodnocovani paraelne funkce
mapovana na jednotlive indexy xetoru:

(A+ '{a->1 b->2} '{a->3 b->3} provedou se paraelne dva vypocty a vyjde:
      {a->4 b->5}

Jak vidite pomoci alpha notace jsou udelat vsechny funkce tabulky co
maji casovou slozitost 1. Alpha ma zajimave vlastnosti. Da se hodit
pred vyraz: A(+ 1 2) je stejne (A+ A1 A2)

Vzdycky vyjde {->3}. Tohle vytykani nam ale vetsinou blokujou xetory
pred ktery se alpha nepise. Proto lisp ma dalsi znak-puntik co alphu
rusi-stejne jako ` a , u maker. Puntik budu psat jako <>
priklady:
A(+ <>x 1) je (A+ x A1)
Kdyz a je xetor [a b c] a X je [x y z] pak:
(CONS A X) => ([a b c] . [x y z])
A(CONS <>A <>X) => [(a.x) (b.y) (c.z)]

Muzeme ale provedst i ruzny operace na ruznych indexech:

(FUNCALL '[+ - - +] '[1 2 3 4] A1) => [ 2 1 2 5 ]

A to uz je peknej paraelizmus.

Beta redukce
============

Druhy co je treba jsou ty operace co maji casovou slozitost logN. Proste
at se snazite jak chcete pomoci alphy nezjistite pocet prvku.  Beta je
vlastne opak alphy. Alpha vezme jednu vec a udela mnoho kopii.  Beta
vezme moc veci a zkombinuje je. To ma casovou slozitost logN. Pri
redukci se ignoruji indexy:
(B+ `{A->1 B->2 C->3}) => 6
(Band `[T T NIL T]) => NIL

A takhle jde zjistit delka xetoru:
(DEFUN DELKA (x) (B+ A(PROG2 <>X 1))
nebo:
(DEFUN VELIKOST (x) (SQRT (B+ (a* x x))))
(DEFUN VSE-SHODNE (x y) (Band (A= x y))
tedy treba vse-schodne nejpre pomoci alphy udela novy xetor ktery bude
obsahovat true na ntem miste kdyz n.prvek x bude shodny z n.prvkem y.
No a potom uz jenom zbyva zjistit jestli je tam nekde false-tose udela
pomoci bety a and.

Muzeme betu pouzit i na konstrukci nevoho xetoru z oboru hodnot a
 definicniho oboru:

(B `(a->1 b->2) `{a->x b->y}) {x->1 y->2}

To se zda trochu odlisne ale je to to samy hned vysvetlim proc: Beta je
trochu obecnejsi. Ona vlastne beta presne odpovida smerovacum zprav
(stejne jako alpha odpovida procesorum). Pomoci bety toho udelate
opravdu hodne.

Zobecnena beta ma tri parametry: slucovaci funkci a dva xetory.  Beta je
zkombinuje jak jsme uz rikaly. Veme hodnoty prvniho xetoru a udela znich
indexy pro hodnoty druheho xetoru a vrati vznikly xetor tedy vlastne
predratuje spoje. To se provede v jednotkovem case. Slucovaci funkce
rika jak resit kolize-tedy kdyz v prnim xetoru jsou dve nebo vice
stejnych hodnot musi se hodnoty z druheho xetoru nejak zkombinovat. To
dela slucovaci funkce. Kdyz zadnou slucovaci funkci nedate kolize hlasi chybu:
(B '[1 2 5] '[x y z]) => {x->1 y->2 z->5}
(B '[1 2 5] '[x z z]) => error

A se slucovaci funkci:

(B+ '[1 2 5] '[x z z]) => {X->1 Z->5}

Kdybychom chteli secist vsechny prvky xetoru udelame:
(B+ '[1 2 5] '{->3}) => {3->8}
Muzem ale druhy xetor vynechat a potom je vysledek normalni hodnota.  A
je to ta situace co byla popsana na zacatku.
Tady je priklad inverze xetoru:
(DEFUN INVERZE (X)
 (B (DOMAIN X) X))

DEFSTRUCT
=========

Dalsim dulezitym rozsirenim je defstruct co bere parametr :cm a ulozi
potom strukturu do cm misto do vektoru. priklad:

(DEFSTRUCT (PIXEL :CM)
  RED
  GREEN
  BLUE)

Kazdy pixel ma pak svuj vlastni procesor. Tedy misto do vektoru da
strukturu do xetoru.

HLEDANI NEJKRATSI CESTY
=======================
No uz umime dost a tak udelame algoritmus. Je to hledani nejkratsi cesty
v grafu. Mame graf o N uzlech a M spojich mezi nima a dva body A a B a
chceme najit nejkratsi cestu z a do b. Je to strasne jednoduchy
algoritmus.  Prote kazdemu bodu dame jeho vzdalenost-to se udela pomoci
tzv. sireni znacky proste bodu a se da nula. Do vsech bodu spojenych
snim se da 1. Do vsech bodu spojenych z body z 1 co jeste nejsou
uznacene dame 2 a to delame tak dlouho dokud se nedobelhame k B. Hodnota
bodu B je potom delka cesty a kdyz z B postoupime do bodu z hodnotou o
jeno mensi a zni zase o jedno mensi projdeme nejkratsi cestou. Tedy
jakakoliv klesajici posloupnost je nejkratsi cesta. Muzem tento algoritmus
zapsat take takto:

1) ohodnot vrcholy hodnotou +nekonecno
2) ohodnot vrchol A cislem 0
3) Ohodnot kazdy vrchol krome A cislem 1 + minimum ohodnoceni
   jeho sousedu. To opakuj dokud B nebude oznaceno.
4) Skonci. Ohodnoceni vrcholu B je odpovedi.

Nejprve ulozeni grafu v pameti:

(DEFSTRUCT (VERTEX :CM)
  LABEL
  NEIGHBORS)

LABEL je hodnota a NEIGHBORS je xetor z cestama.

A ted algoritmus:

(DEFUN DELKA_CESTY (a b g) 
   A(SETF (LABEL <>g) +INF)   ; provede bod 1 tedy nastavi vsechny labely na
+INF tedy nekonecno
    (SETF (LABEL a) 0 ;bod a na nula
    (LOOP UNTIL (< (LABEL b) +INF) ;opakuj dokud label od becka je +INF
      DO A(SETF (LABEL <>(REMOVE A G)) ;pro vsechny labely v G mimo bodu A
          (1+ (Bmin A(LABEL <>NEIGHBORS <>G)))))) ;najdi minimum a zvec o 1
    (LABEL B)) ;navratova hodnota.

Jak je videt vsechno je napsano dost primocare. Graf g je xetor vertexu.
potom A(NEIGHBORS <>G) je xetor xetoru co uznacuje mnozinu vsech
sousednich uzlu
Jediny co je trochu zmatenejsi je treti radek tedy ten cyklus.  Ten je
proveden k krat. Kde k je delka. Pro graf z 10 na 4 vrcholy a 10 na 6
hranami je k priblizne 3. Cyklud se ukonci a bod b bude neco jinyho nez
+ inf. V tele smycky je kazdy vrchol krome A=to dela to REMOVE A G
tedy vytvori v case 1 novy xetor co uz neobsahuje bod A. Pro vsechny
tyto vrcholy se pomoci alphy provede vyhledani minima-pomoci bety
a zvetseni o jedna. Ohodnoceni bodu a zustane 0 protoze ten se nemeni.
zmateny je tu jenom vyber minima:
(Bmin A(LABEL <>(NEIGHBORS V)))
Sousedi vrcholu V jsou xetor vrcholu a alpha je pouzita pro vyber hodnot
operaci label. Tim vznikne xetor co bude obsahovat ohodnoceni. Ten se
zredukuje pomoci bety(Bmin) a najde se minimum. V programu je to navic
komplikovanejsi tim ze je to aplikovano na xetor vrcholu tedy pomoci
alpha na vsechny vrcholy grafu soucasne.
To je zahul co? ale pritom je to jednoduchy :) Tady je videt jak
v lispu jde psat primocare a strucne i kdyz to vypada strasne.
Ted si zpocitejte kolik radek by to melo v cecku

AKTIVNI DATOVE STRUKTURY
========================
To je hlavni vec se kterou v cm pracujeme. Jako na normalnim pocitaci
mame datove struktory-polem,listy a pracujeme snima mame i na cm
struktury ale praci si delaji samy. Takze mame-li mnozinu dat a chceme
aby neco udelaly udelame nad nima datovou strukturu a ty to reknem.
Zakladni tyto struktury jsou:mnoziny,stromy,grafy,pole,stringy, site
typu motyl. Avzdycky si z prvku nejprve sestavi smravnou strukturu co
odpovida problemu:mnozinu kdyz chceme neco provest z kazdym prvkem-alpha
a xetory. Stromy kdyz chceme redukovat- hledat minimum,scitat apod-beta.
Grafy se hodi ne ruzne neuronove site prace snima byla uz ukazana. Motyl
se hodi na trideni. Problem aktivnich datovych struktur je moc zajimavy.
Vsechny tyto struktory se daji udelat xetorama a tedy da se snima pracovat
v cm lispu. Jsou na to moc zajimavy algoritmy ale neveslo by se to sem.
Vpodstate jakekoliv propojeni bunek se take da reprezentovat pomoci 
xetorovych poli a bety. Treba takovy graf:
      1---2
       \ /
        5
       / \
      3   4
se da udelat:
[1  2  2  3  4 a dale obracene pro dvousmerne cesty5  5  1  5  5 ]
[5  5  1  5  5                                     1  2  2  3  4 ]
A pomoci bety potom muzeme secist vsechny prvky kolem uzlu 
(B+ a b)
kde a je prvni xetor a b je druhy xetor. A je to rychlejsi nez zapis v
predeslem algoritmu. Samozdrejme ze takove xetory jdou velmi rychle nad
daty vytvorit a zase je zrusit-treba nad polem je vytvaret podle adres
to jsou adresove indukovane struktury.  Je to proste svanda.

ZAVER
=====
Jak je videt lisp zase prosel. Nebyly treba skoro zadne upravy-jeden
datovy typ a dva operatory pro praci snim. A lisp je paraelni.
Pridelani neceho takoveho do cecka je utrpeni. Dejme tomu ze jestli je
objekt ulozen normalne nebo v cm staci pridelat parametr promene neco
jako extern tak cm. Vetsi problem je to ze funkce(treba min) se obcas
provadi na ridicim pocitaci a obcas uvnitr cm. A pokazde je treba jiny
kod. Dalsi problem je vlastni prepis alpha a beto notace do cecka.  To
je diky celkem hloupemu ceckarskemu volani funkci skoro nemozne. Taky u
definice funkce se pokazdy musi rict jestli ma byt kompilovana pro cm
nebo ridici pocotac. Dejme tomu ze by cecko melo nejakou funkci beta co
by se volala z dvema xetorama a stejnou funkci alpha potom prepis:
(Bmin A(LABEL <>(NEIGHBORS V)))
by vypadal nejak
beta(min,alpha(labela,v.neighbors))
Ale to by nestacilo muselo by se udelat funkce min co vezme minimum
labela co vezme label z neighborsu takze by tu byly dalsi dve funkce
apod.  Knihovni funkce by musely byt dvakrat-jednou pro ridici a jednou
pro cm.  Proste rozhodne by se to neveslo do 10 radek a byl by to
strasne slozity a neprehledny program. Rozhodne by nebyl o nic
citelnejsi nez ten lispackej. Je prevda ze c* ma nekolik zajimavych
konstrukci ktere jsou ale v cmlispu naprosto zbytecne. Treba
ma shape kterym se daji usporadat paraelni data do n rozmerne mrizky.
shape[20][30][40] s
Deklaruje mrizku. deklarace takove paraelni promene X co bude
mit prvky typu t se dela:
t:s x;
Ale vidite jak je to omezene? chceme dat prvky do stromu a potrebujeme
dalsi jazykovy prostredek a takovych siti je neomezene mnoho! A vsechny
ty site jdou udelat pomoci dvou xetoru!
Kotelnik
   ......a ten nejkotlivejsi......