+++++++++++++++++++++++++++++
++++ ++++ +++++++ +++
+++ +++++ +++ +++ +++
+++ ++++++++++ + + + +++
+++ ++++++++++ ++ ++ +++
+++ +++++ +++ +++++++ +++
++++ ++++ +++++++ +++
+++++++++++++++++++++++++++++
The Connection Machine
-=-=-=-=-=-=-=-=-=-=-=-=
Lisp Users: Due to the holiday, there will be no garbage collection on Monday.
Tak tohle je můj historicky první příspěvek do rubriky počítač.
Aby se neřeklo, že si sobecky píšu jenom do svojí. Chtěl bych tu
ukázat, že existují i jiné typy hardwaru, než je PC.
Jedním z nejeexotictějších počítačů vůbec je Connection Machine
(CM) a právě o té bych chtěl něco napsat.
V čem je chyba?
Její tvůrce Daniel Hillis pracoval v laboratoři pro výzkum
umělé inteligence (kde jinde :) a přemýšlel o myslícím stroji.
Z hardwarového hlediska není mozek příliš zajímavý. Jeho neurony
jsou mnohonásobně pomalejší, než tranzistory, protože fungují
chemicky. Jediný parametr, kde náš mozek počítače převyšuje
je množství. Ale pokud vynásobíme počet neuronů v mozku jejich
výkonem a srovnáme to s transistory v počitači, dostaneme už mnohem
příznívější poměr. Dnešní počítače mozek co do výkonu řádově
překonaly. Přesto ale nejsou počítače ani v nejmenším schopné dělat
to, co dělá mozek (zde nemyslím jenom na vlastní myšlení, ale
například i na rozpoznávání obrazu a další věci, které by počítače
umět měly).
Problém je v jejich mizivé efektivitě. V počítači jsou témež
všechny součástky vyrobené ze stejného materiálu - křemíku, ale
pouze mizivé procento křemíku (procesor) dělá něco rozumného. Zbytek
(například paměť) čeká na procesor a procesor zase na paměť. Všechno
čeká vpodstatě na sběrnici. Sběrnice v klasickém neumanovském
počítači je jakési úzké hrdlo (bottleneck), kudy se musí všechno
protlačit.
Masivně paraelní výpočty
Můžeme celkem bez omezení zvyšovat paměť v našem počítači. Tím
se ale situace bude zhoršovat. Poměr křemíku, který vpodstatě nic
nedělá ku křemíku v procesoru bude ještě horší. Naopak dvojnásobné
zvětšení počtů transistorů v procesoru není tak jednoducé -
dostaneme se do mnoha technických nesnází, jako je přehřívání apod.
Takže tím nezískáme dvojnásobné zvýšení výkonu. Přes veškerou naši
snahu jsou počítače vlastně stále méně efektivní. Ani zvyšování
kmitočtu nikam nevede - blížíme se k hranicím vymezeným fyzikálnímy
zákony. A přesto nedosahujeme výkonu mozku, který používá přibližně
1000x pomalejší jednotky.
Jak tedy dál? Jedna cesta je inspirovat se lidkým mozkem
a postavit počítač, který by měl náhražky neuronů pospojované
podobně jako v mozku. Ale tato cesta zatím daleko nedošla. Přesto
se tím můžeme inspirovat a jednlotlivé neurony nahradit procesory.
Pokud chceme řešit nějaký problém, například emulaci elektirckého
obvodu, pospojujeme procesory tak, aby každý procesor emulovat jednu
součástku obvodu a budeme moci emulovat obvod mnohem rychleji, než
na normálním počítači. Na grafiku by se zase hodilo, aby procesory
byly pospojovány do čtvercové síťe. Věci jako foodfill by potom šly
implementovat například:
1) počkej na probuzení
2) obarvi se
3) probuď sousedy
4) usni na věky
5) body 1-4 opakuj do té doby, dokud budou existovat probuzené
procesory
Na to pak nepotřebujeme čas úměrný počtu pixelů ve vyplňované
oblasti, ale úměrný největší vzdálenosti. (tedy na vyplnění 320x200
obrazovky potřebujeme maximálně 520 kroků, klasický počítač
potřebuje 64000 kroků). Tedy takový počítač na 1.6MHZ by byl
stejně rychlý jako pentium na 200. V jiných případech (například
kreslení čar, nebo obdélníku) potřebujeme dokonce jenom jeden krok
(pokud jses uvnitř čtverce, obarvi se) a výkon je tedy z klasickým
počítačem nesrovnatelný.
Problém ale je, že takový počítač by byl příliš jednostraně
zaměřen (i když takové počitače se vyrábí a jmenují se nCube),
například pro simulaci dobravy bychom zase potřebovali zapojení
odpovídajícím jednotlivým křižovatkám ve městě apod.
Záver z toho je, že by bylo ideální, aby se počítač uměl
"pospojovat" sám, tak jak zrovna potřebujeme. A to přávě je CM.
Architectura Connection Machine
Connection machine je tedy masivně paraelní stroj. Zkládá se
z mnoha (například 65000) procesorů. Procesory spolu umí komunikovat
každý z každým. Neexistuje žádná společná paměť (aby se zabránilo
úzkému hrdlu na sběrnici). Každý procesor má svoji vlastní malou
paměť.
Procesory samozřejmě fyzicky nejsou pospojovány každý z každým.
Každý procesor má malý síťový interface a umí směrovat pakety.
Nakonec to funguje asi následovně: procesor vezme data, zabalí je
do balíčku a přídá adresu "dvakrát doleva, pak nahoru" a předá to
procesoru vlevo, ten adresu předěla na "doleva, pak nahoru" atd.
Toto schéma je v klasických CM ještě vylepšeno - procesor například
může data odmítnout, pokud jeho cache je plná, odesílající procesor
tedy zkusí jinou cestu, navíc některé procesory mohou být vadné
- jejich sousedé je objedou. Pokud nějaké dvě buňky spolu často
komunikují, můžou se k sobě přiblížit, aby komunikace byla rychlejší
atd...
Celá CM není samostatný počítač. Je řízena normálním sekvenčním
počítačem a dělá pro něj jakousi intelignetní paměť (počítač do CM
může přistopovat jako do normální paměti, ale navíc ji může vydávat
rozkazy - jako například paměti, paměti, setřiď se! a paměť to udělá
mnohem rychleji, než by to udělal kalsický počítač)
Jsou dva přístupy k tomu, jak generovat instrukce - SIMD (Single
instrukction, multiple data) - počítač generuje jeden tok instrukcí
pro všechny procesory. Podmínky se pak řeší tak, že si jednotlivé
procesory nastaví flag, jestli mají následující instrukce provádět,
nebo ne. Všechny příklady, co jsem tu uvedl byly SIMDové. Druhý
přístup je MIMD (tedy, že každý procesor má vlastní tok instrukcí).
Ten je obecnější, ale jde pomocí SIMDu emulovat. Poslední CM tyto
přístupy kombinují.
Existující CM
První CM byla postavena před deseti lety firmou TMC (Thinking
Machines Corporation). Měla 16 tisíc procesorů, každý se 4KB RAM
taktovaných na 4MHZ. Byla to krychle 1Mx1M a byla chlazená vzduchem.
Měla výkon něco kolem 1000MIPS.
Od té doby firma TMC postavila více než 400 takových počítačů.
Bylo několik serií. Poslední je CM5. Postupem času se ale
od původního návrhu vzdalovala a CM5 je vpodstatě síť pentií každý
s 4MB RAM.
CM mají kromě ohromného výkonu i další výhody. Jedním z nich
je například to, že zvládají vpodstatě libovolné množství vstupů
a výstupů (každý procesor se může starat o nějaký port). Proto je
například používá NASA pro zpracovávání údajů z kosmu, kterých chodí
víc, než bychom byli schopni zaznamenat. CM má ale i mnoho dalších
využití. Dokonce se uvažuje o tom, že by se vyráběla jako přídavná
karta do normálních počítačů. Zde by mohla nahradit grafické
accelerátory (protoře realtime raytracing není pro CM problém)
a další věci). Odhaduje se, že při sériové výrobě by 1MB connection
machine z výkonem 2000mips stál kolem 8000Kč. Poslední důležitá
výhoda je to, že pokud potřebujete dvojnásobný výkon, prostě
přikoupíte nový modul, který připojíte ke staré CM. CM tedy mohou
téměř neomezeně růst.
Programování CM
Programování CM je velmi zajímavé ale také je to hlavní
úskalí CM. Člověk totiž musí zapomenou téměř vše, co se naučil
na sekvenčních počícačích a to se programátorům moc nechce. Proto
radějí stále pracují na klasických strojích.
Je to opravdu nezvyk. Vyhledávání slova ve slovníku například
trvá 1 časovou jednotku (řeknete každému slovu ve slovníku, aby se
porovnalo se vzorem a pokud odpovídá, aby vám dalo větět), třídění
trvá log^2N apod.
Klasická Connection Machine se programuje v Lispu. Z toho důvodu
jsem napsal krátký úvod do Lispu do rubriky programování, jestli
jste ho nečetli, tak teď je ten pravý čas.
Lisp díky sve geniální rozšiřitelnosti se z paraelním
programováním vypořádal docela dobře. Potřebuje pouze dva operátory
navíc β a α a jeden datový typ - xetor.
Xetory
Xetor je datový typ pro CM. Pokud data uložíte do Xetoru, budou
v CM, jinak se uloží do normální paměti nadřazeného počítače. Xetor
přesně odpovídá návrhu CM - je možné do něj uložit množinu objektů
(bez pořadí) a ty navíc nějak pospojovat. Zápis je následující:
{SKY->BLUE GRASS->GREEN APPLE->RED}
Funguje tedy podobně jako asociované pole. Prvky lze rozděkut
do dvou množin (množina indexů (SKY, GRASS, APPLE) a hodnot). Lze
o nich uvažovat také jako o funkcích s definičním oborem a oborem
hodnot.
Z Xetorem lze pracovat jako z každým jiným Lispovým typem,
existují funkce pro vytvoření Xetoru se seznamu a převoz zpět,
vybrání definičního oboru (DOMAIN) a oboru hodnot (RANGE) apod.
Všechny standardní knihovní funkce pro něj fungují. Jejich časové
složitosti jsou následující:
Operace Pole 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
Jak vidíte jsou ve většine případů je rychlejší. Ty logaritmické
časové složitosti vychazejí z jendoduchého postupu. Pokud chceme
například posčítat všechny čísla v Xetoru, můžeme si napřed celý
Xetor rozdělit na dvojice (v jednotkovém čase) a prvky ve dvojicích
sečíst (take v jednotkovém čase) v dalším kole zase sečíst tyto
součty a to opakovat tak dlouho, až zůstane pouze jedno číslo.
K tomu potřebujeme právě logN kroků.
Alfa notace
A teď něco k tomu, jak se tyto základní knihovní funkce napíšou.
Jak jsem už říkal, Lisp byl rozšířen o dva operátory - α a β. Tento
operátor slouží pro převod hodnoty na konstatní Xetor. Konstatní
Xetor je Xetor, který zobrazuje cokoliv na jednu hodnotu {->3}.
Pokud zapíšu nějaký výraz, ten se vyhodnotí a výsledek se uloží do
Xetoru:
α3 => {->3}
α(+ 1 2) => {->3}
α+ => {->+}
Operátor ale umí víc. Pokud funkci zadám jako parametry Xetory,
výpočet se provede paraelně pro každý prvek Xetoru zvlášť.
Například: (α+ '{a->1 b->2} '{a->3 b->3}) provede dva výpočty. Prvky
v Xetorech se sprárují podle indexů a vyjde Xetor {a->4 b->5}
Teď už můžete zapřemýšlet, jak pomocí alfy napsat ty funkce
z tabulky, co mají složitost 1. Pro jednoduchost zápisu se u Alfy
také povoluje umístění před závorku. Tedy α(+ 1 2) je stejné jako
(α+ α1 α2). Vyjde {->3}. V místech kde ale nechete, aby se alfa
dosadila je možné napsat •. Například: α(+ •x 1) je (α+ x α1)
Beta redukce
Popsaný algoritmus pro sečtení všech hodnot alfou nezapíšete.
Od toho je tu Beta. Beta funguje naopak - mnoho hodnot zkombinuje
do jedné. Sečtení se potom zapíše například takto: (5+ '{A->1
B->2 C->3}) => 6. Indexy u Xetoru se ignorují. Například takto lze
zaimplementovat funkci length:
(defun length (x) (β+ α(prog2 •X 1))
Tedy napřed vytvoříme pomocí alfy zobrazení všech indexů
na jedna a potom posčítáme hodnoty.
Betu lze ale zobecnit na tři parametry - funkci a dva xetory.
Potom beta funguje tak, že vezme hodnoty z prvního Xetoru a udělá
z nich indexy pro hodnoty z druhého Xetoru - předrátuje spoje.
To se provede jednotkově. Slučovací funkce potom říka, jak se chovat
v případě kolizí.
Defstruct
Knihovna byla rozšířena pro podporu datových struktur. Pokud
přidáte parametr :cm, struktura se uloží do Xetoru. Například:
(defstruct (pixel :cm)
red
green
blue)
Příklad
Jako příklad uvedu hledání nejkratší cesty. Tento příklad je
z knihy The Connection Machine od Hillise. V čechách ji vydala
Grada (asi jediná její dobrá knížka) a tak doporučuju, abyste si ji
přečetli.
Algoritmus na hledání nejkratší cesty v grafu funguje
jednoduchý. Máme dva uzly, jeden vstupní a druhý výstupní. Ze
vstupního bodu začneme šířit značky. Označíme si všechny sousední,
že je možné se do nich dostat jedním tahem. Potom sousedy těcto
sousedů atd. až k cílovému. Potom každá sestupná posloupnost je
hledaná nejkratší cesta.
1) ohodnoť vrcholy hodnotou +nekonečno
2) ohodnoť vrchol A číslem 0
3) Ohodnoť každý vrchol kromě A číslem 1 + minimum ohodnocení jeho
sousedů. To opakuj dokud B nebude označeno.
4) Konec.
Nejprve uložení grafu v paměti:
(defstruct (vertex :cm)
label
neighbors)
label je hodnota a neighbors je xetor obsahující cesty.
Algoritmus se potom zapíše následovně:
(defun delka_cesty (a b g)
α(setf (label •g) +INF) ; provede bod 1 tedy nastaví vsechny labely na
; +INF - nekonečno
(setf (label a) 0 ;bod a na nula
(loop until (< (label b) +INF)
;opakuj dokud label od b je +INF
do α(setf (label •(remove a g))
;pro všechny labely v G mimo bodu A
(1+ (βmin α(label •neighbors •g))))))
;najdi minimum a přičti 1
(LABEL B)) ;návratová hodnota.
Kolem CM je samozřejmě mnoho dalších zajímavých problémů, ale
už se to sem asi nevejde. I takhle je článek delší, než jsem čekal.
Pokud vás problém zajímá, sežeňte si zmiňovanou knihu, je to opravdu
zajímavé čtení
- HH -
hubicka@freesoft.cz
výheň