Soluautomaattisimulointi

Juha Haataja

SOLUAUTOMAATTISIMULOINTI

Diplomityö tehty systeemi- ja operaatiotutkimuksen syventymiskohteessa Työn valvoja professori Raimo P. Hämäläinen

Työn ohjaaja professori Risto Nieminen

Espoo 1.2.1991

Tekijä: Juha Haataja

Työn nimi: Soluautomaattisimulointi

Päivämäärä: 1.2.1991 Sivumäärä: 90

Osasto: Tietotekniikan osasto Professuuri: Mat-2

Matematiikan ja systeemianalyysin laitos Sovellettu matematiikka

Työn valvoja: professori Raimo P. Hämäläinen Työn ohjaaja: professori Risto Nieminen

Soluautomaatit ovat dynaamisia systeemejä, jotka soveltuvat mm. fysikaalisten proses­

sien mallinnukseen ja simulointiin erityisesti massiivisesti rinnakkaisten tietokonearkki­

tehtuurien yhteydessä.

Diplomityössä selvitettiin soluautomaattien teoriaa, tutkittiin niiden ominaisuuksia sekä visualisoitiin niiden käyttäytymistä. Saavutetut tulokset pyrittiin esittämään tiiviissä mutta kuitenkin kattavassa muodossa. Kirjallisen esityksen lisäksi tuotettiin noin viiden minuutin mittainen soluautomaattimalleja havainnollistava tietokoneanimaatio.

Diplomityö tehtiin Tieteellisen laskennan palvelussa (TLP), joka on Valtion tietokone­

keskuksen yhteyteen sijoitettu Suomen kansallinen supertietokonekeskus. Suurin osa työhön liittyvistä ohjelmointityöstä ja simulaatioista on tehty Silicon Graphicsin Iris- grafiikkatyöasemilla. Ohjelmointi on tehty pääosin C-kielellä, ja visualisointiin on käytetty Silicon Graphicsin GL-kirjaston funktioita. Joitakin C-ohjelmia on sovitettu TLP:n Cray- superkoneelle erilaisiin analyysitarkoituksiin. Lisäksi työn yhteydessä on käytetty koemie­

lessä Connection Machine -rinnakkaiskonetta ja sen FORTRAN-kieltä soluautomaattien simuloimiseen.

Työssä havaittiin soluautomaattien tarjoavan mielenkiintoisen ja lupaavan mallinnus- tavan esim. hydrodynamiikassa. Toisaalta soluautomaattitutkimus on sekä teorian että käytännön osalta vielä alkuvaiheissa, vaikka joitakin perustavia tuloksia onkin saatu selvitetyksi. Kiinnostusta soluautomaattitutkimukseen lisää ennen kaikkea rin­

nakkaislaskentaan sopivien mallien kasvava merkitys vaativassa tieteellisessä ja teknil­

lisessä laskennassa.

Sisällysluettelo

1 Alkusanat _____________________________ 1 2 Mitä ovat soluautomaatit?___________________________ 2

2.1 Esimerkki kaksiulotteisesta soluautomaatista ---2 2.2 Soluautomaatin formaali määritelmä__________________________ 3 2.3 Soluautomaatti mallitusvälineenä________ _________________ —3 2.4 Fysikaalisten systeemien mallitus__________________________ _4 2.5 Soluautomaatit laskennallisina systeemeinä_____________________4 2.6 Soluautomaattilaskennan käytännön toteutukset--- 5

3 Soluautomaattitutkimuksen historiaa_________________ 7

3.1 von Neumann ja itseään monistavat koneet_____________________ 7 3.2 Soluautomaattipelien kausi_________________________________ 8

3.3 Hahmontunnistussovellukset____________ 9

3.4 Soluautomaattitutkimuksen murroskausi 1980-luvulla____________ 9

4 Yksiulotteiset soluautomaatit________________________ 11

4.1 Määritelmiä__________ _____________ _____________________11 4.2 Soluautomaattisääntöjen koodinumerot --- 12 4.3 Yksiulotteisten soluautomaattien perusmalleja__________________16 4.4 Soluautomaattien luokittelu__________ _____________________ 16

5 Kaksiulotteiset soluautomaatit_______________________ 20

5.1 Määritelmiä____________________________________________ 20

5.2 Life-peli______________________________ 21

5.3 Rajajoukoista____________________ 23

5.4 Kaksiulotteiset hilakaasut_________________________________ 24

6 Soluautomaatit verrattuina muihin systeemeihin_______26

6.1 Dynaamisten systeemien hierarkia____________________________26 6.2 Dynaamiset hilasysteemit_______ _________________________ 26 6.3 Kaaos dynaamisessa hilasysteemissä________________________ 27

6.4 Dynaamisen systeemin diskretointi___________________________28

7 Soluautomaatit tietojenkäsittelysysteemeinä__________ 31

7.1 Automaattien teoriaa______________________________________31 7.2 Soluautomaattien tilastolliset ominaisuudet_____________________31 7.3 Soluautomaattien algebralliset ominaisuudet____________________ 33

8 Soluautomaattien käyttökohteita____________________ 3 6

8.1 Rinnakkaiskoneet_______________________________________ 36 8.2 Massiivisesti rinnakkaiset koneet___________________________ 36 8.3 Connection Machine______________________________________37 8.4 Soluautomaattien simulointi Connection Machinessa____________ 38 8.5 Soluautomaatit tietokonetekniikassa__________________________ 39

9 Kriittiset ilmiöt___________________________________ 40

9.1 1/f-skaalautuvuus______________ 40

9.2 Kriittisen ilmiön määritelmä ja terminologiaa__________________ 41 9.3 itseorganisoituvat kriittiset ilmiöt _______________________ 42

10 Soluautomaattimalleja______________________________43

10.1 Simulaatioiden toteutus___________________________________ 43

10.2 Simulaatio-ohjelmat_______ 44

10.3 Enemmistösääntö_____ _________________________________ 45 10.4 Hitaan jäähtymisen malli__________________________________ 46 10.5 Q2R-malli________________________ _____________________48 10.6 Neuronimalli__________ _________________________________ 51 10.7 DLA-malli_____________________________________________ 53

10.8 Hiekkakekomalli______ 56

10.9 Metsäpalomalli______ __________________________________ 61

11 Yhteenveto _64

12 Sanasto 66

13 Kirjallisuutta______________________________________68

13.1 Soluautomaatit__________________________________________68 13.2 Matematiikka ja fysiikka__________________________________ 68 13.3 Visualisointi ja tietojenkäsittely_____________________________ 69 13.4 Käsikirjoja ja oppaita_____________________________________69

14 Viiteluettelo 70

16 Kuvaliitteet 77

1 Alkusanat

“Mitä ovat soluautomaatit? Miten ne käyttäytyvät? Mitä niillä tehdään?”

Nämä ovat muutamia niistä kysymyksistä, joihin pyrin tässä työssä vas­

taamaan. Työ on tehty Tieteellisen laskennan palvelussa (TLP) Espoon Ota­

niemessä.

Tämä kirjoitus on toisaalta yleisluontoinen kuvaus soluautomaateista, toisaalta ajan tasalla oleva tutkimus soluautomaattiteorian tilasta. Yleisluon­

toinen osuus oli tyypillinen selvitys- ja kuvaustehtävä; tutkimusosuuteen kuului paljon oma-aloitteista työtä: teorian ja käytännön opettelua, ohjel­

mointia (ja ohjelmoinnin opettelua!), tulosten visualisointia ja analyysiä.

Kiijoituksen painopiste on erityyppisten soluautomaattimallien esittelyssä, mihin liittyy suurin osa tekemästäni ohjelmointityöstä. Lisäksi työn yhtey­

dessä on tehty video, joka havainnollistaa soluautomaattimalleja.

Toivottavasti tästä teoksesta on hyötyä kaikille soluautomaateista kiinnos­

tuneille—mielellään yhtä lailla tiedemiehille kuin maallikoillekin. Ainakin itselleni soluautomaatteihin perehtyminen on tarjonnut ja tarjoaa runsaasti aivotoiminnan virikkeitä.

Kiitokset TLP:n tieteelliselle johtajalle, professori Risto Niemiselle työn oh­

jauksesta ja suuntaamisesta mielenkiintoisille alueille. Työtovereilleni esi­

tän kiitokset kaikenkattavasta avusta, diplomityötä koskevista kommenteista ja ehdotuksista sekä ennen kaikkea inspiroivasta työilmapiiristä.

Otaniemessä 1.2.1991

Juha Haataja

2 Mitä ovat soluautomaatit?

Soluautomaatit (engl, “cellular automata” eli CA, yks. “cellular automa­

ton”) ovat diskreettejä dynaamisia systeemejä, jotka koostuvat joukosta säännölliseksi hilaksi jäljestettyjä soluja. Kaikki solut ovat samanlaisia, ja ne ovat yhteydessä toisiinsa naapurisuhteen perusteella. Solua ja sen naapu­

reita kutsutaan naapuristoksi. Kunkin solun mahdolliset tilat ovat diskreette­

jä; tiloja on tyypillisesti vain muutama. Solun nykyistä tilaa käytetään syöt­

tötietona naapuriston uusia tiloja laskettaessa.

2.1 Esimerkki kaksiulotteisesta soluautomaatista

Kuvassa 2.1 on esitetty eräs kaksiulotteinen soluautomaatti. Soluautomaatti- hila on suorakulmainen ja kullakin solulla on neljä naapuria (ns. “von Neu­

mann -naapuristo”). Muita mahdollisuuksia kaksiulotteisessa tapauksessa olisi lukea naapuristoon mukaan myös diagonaalisesti lähinnä olevat solut (ns. “Mooren naapuristo"), tai käyttää vaikkapa heksagonaalista hilaa.

Soluautomaatin nykyisestä konfiguraatiosta saadaan soluautomaatin seu- raava konfiguraatio päivittämällä kaikkien solujen arvot yhtä aikaa. Päivit­

tämiseen käytetään ns. soluautomaattisääntöä, joka tuottaa kunkin solun uuden tilan solunaapuriston vanhojen tilojen perusteella. Soluautomaatti- sääntö voisi laskea vaikkapa summan solunaapuriston tiloista ja muuttaa

Naapurisoluja

Solunaapuriston keskussolu

Kuva 2.1 Kaksiulotteisen soluautomaatin rakenne. Kullakin solulla on neljä naapuria.

solun arvoa saadun tuloksen perusteella. (Tällaista summaussääntöä kutsu­

taan totalistiseksi.)

2.2 Soluautomaatin formaali määritelmä

Soluautomaatit ovat diskreettejä dynaamisia systeemejä, jotka koostuvat komponenteista (G,Q,V/,t)‘

Soluavaruus G on yleensä säännöllinen hila, esim. Z tai Z2.

Tila-avaruus Q on diskreetti—esim. Z:n osajoukko (0,1}.

Naapuristo V¡ on määritelty samoin kaikille soluavaruuden soluille i e G.

Soluautomaattisääntö / laskee kunkin solun tilan hetkellä r-f-1 solu- naapuriston konfiguraatiosta hetkellä t e {0,1,...} yhtä aikaa soluava­

ruuden kaikille soluille ie G:

*/+1 =/(*/,>••••

..

Xj e Q ja (x7l,..., xjs) e Q5.

(2.1)

2.3 Soluautomaatti mallitusvälineenä

Osittaisdifferentiaaliyhtälöillä kuvattavissa oleva fysikaalinen systeemi on mallitettavissa soluautomaateilla ottamalla käyttöön differenssiesitysmuoto ja diskreetit muuttujat. Erityisesti hydrodynamiikan yhtälöiden (Navier- Stokes ym.) ja kuljetusyhtälöiden (Boltzmann jne.) soluautomaattisimulaa- tioita on tutkittu varsin runsaasti 1980-luvulla [1,2,3].

Soluautomaatin käyttäytyminen voi olla sen yksinkertaisesta rakenteesta huolimatta kaikkea muuta kuin epätriviaalia, erityisesti silloin kun soluauto­

maattisääntö on epälineaarinen. Soluautomaatit ovatkin käyttökelpoinen vaihtoehto tutkittaessa juuri epälineaarisia prosesseja—lisäksi näitä ilmiöitä voi olla erittäin vaikea mallittaa perinteisillä menetelmillä. Epälineaaristen ilmiöiden käyttäytymistä kuvataan muuttamalla prosessi soluautomaatti- simulointiin soveltuviksi diskreeteiksi askeleiksi.

tarjoavat mm. lehtien ja oksastojen rakenteet, eräät kiteytymisilmiöt sekä biologisten populaatioiden kasvaminen. (Fraktaalisia soluautomaatteja ana­

lysoidaan viitteessä [4]. Kiteytymisilmiöitä kuvataan viitteessä [5] s. 305- 312.)

2.4 Fysikaalisten systeemien mallitus

Fysiikan näkökulmasta soluautomaatti voidaan mieltää systeemin diskre- toinniksi ajassa, paikassa ja tila-avaruudessa. Täten soluautomaatti voi kuvata esim. partikkelien törmäyksiä ja vaikkapa energian vaihtoa. Solun tila voi vastata hiukkasen viritysastetta tai energiaa. Erityyppisiä säily­

mislakeja ja symmetrioita voidaan sisällyttää soluautomaattimallin sään­

töihin ja reunaehtoihin [2,5].

Naapurisolujen vuorovaikutuksiin perustuva malli soveltuu oivallisesti monien prosessien kuvaamiseen. Suurta haittaa ei yleensä ole myöskään solujen tilajoukon pienuudesta: soluautomaatin makroskooppinen käyttäy­

tyminen muistuttaa jatkuvia systeemejä, mikäli automaatin koko on tarpeeksi suuri. Fysikaalisille systeemeillehän on usein ominaista, että yksit­

täisen hiukkasen käyttäytymistä ei voida edes mitata tarkasti, mutta makro­

skooppisia ominaisuuksia sen sijaan voidaan havaita ja jopa ennustaa.

Koska systeemin kunkin solun seuraavaan tilaan vaikuttavat vain solu- naapuriston solujen nykyiset tilat, voidaan kaikkien solujen tilat päivittää toisistaan riippumatta samanaikaisesti. Simulaatiot saadaan siis tehokkaiksi erityisesti rinnakkaisuuteen perustuvissa tietokonearkkitehtuureissa.

2.5 Soluautomaatit laskennallisina systeemeinä

Edellä esitettyjen esimerkkien valossa soluautomaatteja voi pitää rinnak­

kaistietokoneina. Soluautomaattien laskentaominaisuuksia onkin tutkittu runsaasti ([2] s. 57-72). On osoitettu, että eräät soluautomaatit kykenevät universaalilaskentaan eli simuloimaan mitä tahansa tietokonetta (tällainen

soiuautomaatti on esim. Life-peli). Joitakin soluautomaatteja voidaan pitää yleiskäyttöisinä tietokoneina—vaikkakin jonkin tavallisen tietokoneen si­

mulointi esim. Life-pelillä onkin epäilemättä ajan haaskausta. Soluautomaa- teille sopivia algoritmeja on etsitty runsaasti, ja onpa soluautomaateista haettu yleismallia rinnakkaislaskennallekin [6].

Ensi näkemältä äärimmäisen yksinkertaisilta vaikuttavat soluautomaatit saattavat siis mallittaa hyvin monimutkaisia ilmiöitä. Soluautomaatin käyt­

täytymisen moninaisuus tarkoittaa usein myös sitä, että soluautomaatin lopputilojen laskemiseen ei ole yleistä “oikopolkua” vaan soluautomaatin evoluutio on simuloitava kokonaisuudessaan. Soluautomaattien tutkimiseen vaikuttaa myös erilaisten soluautomaattisääntöjen suuri lukumäärä (esim.

kaksiulotteisia ulkototalistisia soluautomaattisääntöjä on 0,3 miljoonaa kpl

—ks. kappale 5.1).

Soluautomaattilaskennan käytännön toteutukset

Kiinnostusta soluautomaattimallien käyttöön lisää se, että simulointi voi­

daan tehdä ilman pyöristysvirheitä, koska tila-avaruus on diskreetti. Las­

kenta on myös tehokasta, jos käytetään nopeita bittitason operaatioita.

Tietokoneen muistinkäytössä ei myöskään yleensä tule ongelmia, sillä solu- automaattisäännöt ovat paikallisia ja tarvittavat arvot ovat muistissa lähek­

käin.

Perinteiset peräkkäisarkkitehtuuriin perustuvat tietokoneet ovat soluauto­

maattien simuloinnissa luonnollisesti paljon tehottomampia kuin rinnakkais­

tietokoneet. Varsinkin massiivisesti rinnakkaiset ns. SIMD-arkkitehtuuriin (Single Instruction, Multiple Data) pohjautuvat koneet soveltuvat erinomai­

sesti soluautomaattien laskentaan. Mm. Connection Machine -rinnakkais­

kone perustuu nimenomaan soluautomaattityyppiseen tietojenkäsittelyperi- aatteeseen [6].

Osittaisdifferentiaaliyhtälöiden ratkomista numeerisesti tietokoneessa voi pitää myös soluautomaattilaskentana. Osittaisdifferentiaaliyhtälöhän tyypil­

lisesti diskretoidaan ajassa ja paikassapa lisäksi äärellinen laskentatarkkuus (esim. 32 bittiä) merkitsee myös tila-avaruuden diskretointia. Näin ollen osittaisdifferentiaaliyhtälö on korvattu soluautomaatilla. Tällä soluautomaa-

Yleensä soluautomaattilaskennassa pyritään mahdollisimman yksinkertai­

siin soluihin. Ääritapauksessa soluilla on vain kaksi tilaa (esim. 0 ja 1), jolloin solun tila voidaan kuvata yhdellä bitillä. Tällaisetkin soluautomaatit kykenevät simuloimaan suurta joukkoa ilmiöitä. Kaksiulotteisesta tapauk­

sesta esimerkkejä ovat mm. Ising spin -mallit. Ising-mallissa solun tila kuvaa spinin suuntaa, joka saattaa muuttua tietyllä solunaapuriston tilasta riippuvalla todennäköisyydellä. Sopivista alkuarvoista lähdettäessä Ising- malli hakeutuu tasapainotilaan, joka kuvaa fysikaalisen systeemin termistä tasapainoa [7].

Houkutuksena soluautomaattien käytölle laskentaan on niiden yksinker­

taisuus ja paikallisuus: ne saattavat mahdollistaa prosessointielementtien rakentamisen jopa molekyylitason komponenteista. Tällöin tietokoneet voi­

sivat olla nykyisiin systeemeihin nähden useita kertaluokkia tehokkaampia.

Toteutusongelmana ovat tällaisille järjestelmille tyypilliset kvanttimekaa­

niset epävarmuudet ja muut häiriöt. Toisaalta myös kvanttimekaanisia solu- automaatteja on jossain määrin tutkittu [8,9,10].

Suurta mielenkiintoa on herättänyt mahdollisuus rakentaa soluautomaattien simulointiin erikoistunut erittäin nopea tietokone. Tällaisia koneita on jo olemassakin—mm. Margoluksen ja Toffolin rakentama CAM-6, jonka käyttöä kuvataan viitteessä [11]. CAM-6 on PC:hen liitettävä kortti, joka kykenee simuloimaan kaksiulotteisia soluautomaatteja Cray-superkoneen nopeudella.

Viitteessä [12] on pohdittu tämänhetkisen teknologian rajoja soluautomaat- tikoneen rakentamisessa. Alustavien arvioiden mukaan periaatteessa voitai­

siin rakentaa soluautomaattikone, jonka nopeussuhde Cray-superkoneeseen nähden olisi luokkaa 1# tai enemmän—eli yksi kone vastaisi lähes miljar­

dia Craytä. Tällainen laite mahdollistaisi mm. suurten kolmiulotteisten hila- kaasumallien laskemisen.

von Neumann ja itseään monistavat koneet

Soluautomaattien idean keksivät vuonna 1948 J. von Neumann ja S. Ulam [13]. von Neumann tunnetaan ennen kaikkea perinteisen tietokonearkkiteh­

tuurin kehittäjänä—ns. von Neumann -arkkitehtuurin, jota käytetään nyky­

ään rinnakkaislaskennan mahdollisuuksia kuvattaessa lähes kirosanana, von Neumann kuitenkin tunsi peräkkäisarkkitehtuurin pullonkaulan eli sen ettei tällaisen tietokoneen nopeutta voi rajatta kasvattaa. Tämän vuoksi hän oli kiinnostunut myös rinnakkaislaskennan mahdollisuuksista.

Tietokonearkkitehtuurien lisäksi von Neumann tutki muitakin asioita. Hän pyrki Ulamin kanssa mm. mallittamaan biologista lisääntymistä eli luomaan

“itseään monistavan koneen”. Onkin varsin vaikeaa luoda systeemi, joka kykenee tuottamaan kopioita itsestään biologisten olioiden tapaan, von Neu­

mann ja Ulam käyttivät systeemeistään termiä “cellular spaces” mutta myöhemmin vakiintui käyttöön termi “cellular automata” (CA) eli soluautomaatit (yks. “cellular automaton”).

Vuosina 1952-53 von Neumann sai suunnitelluksi soluautomaatin, joka kykeni universaalilaskentaan ja itsensä kopiointiin. Kyseessä oli kaksi­

ulotteinen soluautomaatti, jonka soluilla oli 29 tilaa. Näillä tiloilla on mahdollista toteuttaa loogiset perusoperaatiot, viestinvälitys sekä rakentei­

den luominen ja tuhoaminen. Alkeellisemmista osasista voidaan edelleen koota korkeamman tason rakenteita, ja lopulta itsensä kopiointiin ja univer­

saalilaskentaan kykenevä soluautomaatti.

Edgar Codd yksinkertaisti ja paransi von Neumannin soluautomaatin raken­

netta vuonna 1965—esimerkiksi tarvittavien tilojen lukumäärä pieneni kah­

deksaan. Mitään suurta käytännön merkitystä von Neumannin ja Coddin soiuautomaateilla ei kuitenkaan ole ollut—on arvioitu, että niiden täydelli­

seen simuloimiseen tarvittaisiin kymmenistätuhansista soluista koostuva so- luautomaattihila ([2] s. 57-72).

tille [14,15]. Viime aikoina on saatu uusia tuloksia myös yksiulotteisten soluautomaattien universaalilaskentaominaisuuksista [16].

3.2 Soluautomaattipelien kausi

von Neumannin ja Ulamin soluautomaateissa keskeistä oli itsensä kopiointi sekä universaalilaskentaominaisuudet. Jatkoa tälle on John Conwayn vuon­

na 1970 keksimä Life-peli, joka on kaksiulotteinen soluautomaatti. Vaikka Lifen soluilla on vain kaksi tilaa, se kykenee universaalilaskentaan.

Life-soluautomaattia voi pitää eräänlaisena yhden pelaajan pelinä. Lifea on tutkittu varsin paljon, ja se lieneekin ainoa yleisesti tunnettu soluautomaatti.

Syynä tähän lienee 1970-luvun alussa Scientific American -lehdessä jul­

kaistu Life-peliä käsittelevä artikkeli [17]. Life jäi kuitenkin jotakuinkin eri­

koistapaukseksi—soluautomaattitutkimus sai yleisesti ottaen 1970-luvulla varsin vähän huomiota.

1980-luvulla on yleinen kiinnostus soluautomaatteihin herännyt uudestaan.

Taustana tähän voi nähdä mikrotietokoneiden vallankumouksen, jonka ansiosta kenellä tahansa on mahdollista hankkia käyttöönsä yleiskäyttöinen, kohtuullisen vaivattomasti ohjelmoitava tietokone. Luonnollisesti suurin vaikutus soluautomaattien popularisointiin on valmisohjelmilla—niitä on nykyisin saatavilla yksinkertaisista Life-pelin simulaattoreista monipuolisiin ohjelmoitaviin “soluautomaattilaboratorioihin” [11].

Ilmeisesti ennen kaikkea soluautomaattien simuloinnin yhdistäminen näyt­

tävään värigrafiikkaan on vaikuttanut kiinnostuksen uudelleen heräämiseen.

Kehittyneet visualisointivälineet taijoavat luonnollisesti myös tieteelliselle tutkimukselle uusia mahdollisuuksia soluautomaattien havainnollistami­

seen.

Soluautomaattien esiintuomisessa on viime aikoina jälleen kunnostautunut Scientific American -lehti, jossa on julkaistu useita erilaisia soiuautomaat­

teja esitteleviä artikkeleita [18,19,20]. Osaltaan tämän voi katsoa kuvasta­

van myös soluautomaattitutkimuksen murrosvaihetta—nyt osataan soveltaa

soluautomaattimalleja moniin erityyppisiin kohteisiin, ja osalla näistä sovelluksista on popularististakin arvoa. Tässä on kuitenkin vaarana soluautomaattien leimautuminen pelkiksi pelisysteemeiksi.

3.3 Hahmontunnistussovellukset

Erityisesti kaksiulotteisia soluautomaatteja on käytetty runsaasti hahmon- tunnistussovelluksissa ja kuvankäsittelyssä. Kuvankäsittelytehtävässä laske­

taan soluautomaateilla tavallisesti vain yksi tai muutama sukupolvi. Lähes­

tymistavalla on etunsa lähinnä siksi, että hyvin yksinkertaisista piireistä voi­

daan rakentaa tiettyä soluautomaattialgoritmia simuloivia systeemejä. Täl­

laiset piirit pystyvät suorittamaan tehokkaasti esim. kuvankäsittelytehtäviä, sillä soluautomaattien laskenta on äärimmäisen hyvin rinnakkaistettavissa.

Siis yksinkertaisistakin komponenteista on rakennettavissa tehokkaita (ja halpoja!) kuvankäsittelijöitä—tietenkin helpoiten johonkin tiettyyn vakioi­

tuun tehtävään.

Erityisesti 1970-luvulla tutkittiin runsaasti soluautomaattien kuvankäsittely- ominaisuuksia [21]. Ns. perseptronit ovat esimerkki soluautomaattityyppi- sestä hahmontunnistimesta [22]. Nykyisin hermoverkoilla ratkotaan monimutkaisiakin hahmontunnistustehtäviä.

3.4 Soluautomaattitutkimuksen murroskausi 1980-luvulla

Alkuaikojen soluautomaattipelit ja 1970-luvun hahmontunnistussovellukset näyttivät loppujen lopuksi johtavan umpikujaan. Jonkinlaisen lähtölau­

kauksen soluautomaattien uudelle tulemiselle voi sanoa tapahtuneen Step­

hen Wolframin ansiosta 1980-luvun alussa.

Wolfram tunnetaan nykyisin parhaiten Mathematica-ohjelmiston kehittä­

jänä, mutta tätä ennen hän tutki mm. soluautomaatteja. Wolfram käytti tutkimuksissaan informaatioteorian, tilastotieteen ja tietojenkäsittelyteorian menetelmiä ja kykeni johtamaan muutamia konkreettisia tuloksia [5].

100 kpl. Tämä soluautomaatti tuottaa fraktaalista rakenteita.

Wolfram havaitsi, että yksiulotteiset soluautomaatit kykenevät hämmäs­

tyttävän monimuotoiseen käyttäytymiseen. Hän tutki systemaattisesti yksi­

ulotteisia soluautomaatteja, joilla oli vain kaksi tilaa ja joiden naapuristo koostui keskussolusta ja sen kummallakin puolella olevasta naapurisolusta.

Tuloksena oli soluautomaattien luokittelu neljään luokkaan: homogeenisiin, jaksollisiin, kaoottisiin ja laskennallisiin soluautomaatteihin. Homogeeniset soluautomaatit päätyvät yhtenäiseen lopputilaan; jaksolliset soluautomaatit tuottavat paikallisia periodisia rakenteita; kaoottiset soluautomaatit tuottavat fraktaalisia (kuva 3.1) ja kaoottisia konfiguraatioita; laskennalliset soluauto­

maatit tuottavat monimutkaisia, mahdollisesti soluhilassa eteneviä rakentei­

ta, jotka voivat kyetä jopa universaalilaskentaan ([5] s. 91-125 ja s. 189- 231).

Mitään perustavaa laatua olevaa teoriaa edes näiden kaikkein yksinker­

taisimpien soluautomaattien käyttäytymisestä ei ole kyetty vieläkään luo­

maan. Wolframin esittämää soluautomaattien luokkajakoa sen sijaan on jonkin verran kyetty formalisoimaan ja selkeyttämään [23,24].

Soluautomaattien teorian ja sovelluksien uusi esiinmarssi johtunee siis siitä, että yksinkertaisimpienkin soluautomaattisysteemien on havaittu sekä aset­

tavan mielenkiintoisia haasteita että tarjoavan monipuolisia ja tehokkaita mahdollisuuksia systeemien mallitukseen.

4 Yksiulotteiset soluautomaatit

4.1 Määritelmiä

Yksiulotteinen soluautomaatti voidaan esittää jonona soluja. Soluja voi olla äärellinen tai ääretön määrä. Todellisesssa systeemissä soluja luonnollisesti on vain äärellisen monta. Solujono voi olla myös järjestetty renkaaksi, jolloin soluautomaatin käyttäytymiseen tulee usein tiettyä solujen lukumää­

rästä riippuvaa periodisuutta.

Seuraavassa merkitään yksiulotteisen soluautomaatin zrnnen solun tilaa ajanhetkellä t notaatiolla x¿‘.

Yksiulotteisen soluautomaatin soluautomaattisääntö/voidaan esittää solu- naapuriston solujen x¡ tilafunktiona seuraavasti:

У — f Гу Í yf X- I

(4.1)

Tässä on oletettu että solut on jäljestetty jonoksi ja kunkin solun naapureita ovat r kpl solun vasemmalla ja oikealla puolella olevaa solua. Jos solu­

automaattisääntö riippuu vain solujen tilojen summasta, sanotaan kyseessä olevan ns. totalistisen säännön (engl. “totalistic rule”). Tällöin sääntö voi­

daan esittää muodossa

□□□□

Naapurisolut

Kuva 4.1 Yksiulotteisen soluautomaatin rakenne. Periodiset reunaehdot.

Jos sääntö riippuu solun naapurisolujen tilojen summasta sekä solun omasta nykyisestä arvosta, on kyse ns. ulkototalistisesta säännöstä (engl. “outer totalistic rule”), joka voidaan esittää muodossa:

Г

(4.3) j=-r.j*0

Luonnollisesti totalistisen ja ulkototalistisen soluautomaatin määritelmät voidaan yleistää useampiulotteisiin tapauksiin. Kannattaa huomata, että to- talistiset soluautomaatit ovat ulkototalististen soluautomaattien osajoukko.

4.2 Soluautomaattisääntöjen koodinumerot

Wolfram otti käyttöön yksiulotteisten soluautomaattisääntöjen kuvaamisen koodinumerolla ([5] s. 91-125). Olkoon soluautomaatin soluilla k erilaista tilaa, jotka merkitään kokonaisluvuilla {0,1,...,£-1}. Tällöin totalistisessa tapauksessa r-säteisen naapuriston soluautomaattifunktion / argumenteiksi saadaan arvoja joukosta {0,...,(2г+1)(Ы)}. Soluautomaattisääntö määrää solun uuden arvon, eli sääntö kuvaa Z:n osajoukon {0,...,(2r+l)(£-l)}

joukolle {0,..., &-1}.

Soluautomaattisääntö voidaan koodata yhdeksi luvuksi, jonka numerot saa­

vat arvoja joukosta {0, ..., ¿-1} ja jonka pituus on (2/4-l)(fc-l)+l. Seu- raavassa tämän totalistisen koodin Ct määritelmä (n on solunaapuriston solujen tila-arvojen summa)

(2r+lX*-l)

Q= X *"/M . (4.4)

Jos soluautomaatti on binäärinen (k=2) eli solut saavat arvoja joukosta {0,1}, voidaan soluautomaattisääntö esittää binäärilukuna. Olkoon kyseessä vaikkapa binäärinen r=l soluautomaatti, jonka soluautomaattifunktio/on seuraava (n on solunaapuriston solujen tila-arvojen summa)

/N = 1, jos n = 1 tai 3, 0, muulloin.

Tällöin totalistiseksi koodiksi Ct saadaan:

(2r+lXt-l) 3

c,= £

= X 2"/M

71=0 71=0

= 23/[3] + ... + 2°/[0] = 23 + 21 = Ют = 10102

Koodin esityksestä binäärilukuna (1010) nähdään esimerkiksi, että kun solunaapuriston tilojen summa = 2, saa solu seuraavalla ajanhetkellä arvon 0 (kolmas numero oikealta).

Jos kyseessä on uiko to tali stinen sääntö, soluautomaatin uusi tila saadaan solunaapurien tilojen summasta sekä solun omasta arvosta. Yksidimensi- oisen ulkototalistisen soluautomaattisäännön koodi Сщ voidaan ilmoittaa muodossa

k-1 2т<Ы)

Cut=I X (4.5)

X=0 71=0

Edellä esimerkkinä käytetty totalistinen ja binäärinen r= 1 soluautomaatti­

sääntö voidaan esittää myös ulkototalistisena sääntönä (x on keskussolun arvo ja n naapuri solujen arvojen summa):

f[x,n\

T, jos x = 1 ja n = 0 tai 2, 1, jos x = 0 ja и = 1, 0, muulloin.

Koodiksi tulee binääriluku 100110 eli desimaalijärjestelmässä luku 38:

Kuva 4.2 Totalistisen k=2, r=l soluautomaalin aikakehitys. Sääntönumero: totalistinen 10, ulko- totalistinen 38, yleinen 150. Satunnainen alkutila, periodiset reunaehdot.

O« = £ £ 22n+xf[x,n] = 25/[l,2] + ...

x=0 л=O

= 25 + 22 + 21 =38io = 1001102

+ 2°/[0,0]

Yleisen yksiulotteisen soluautomaatin koodinumero C voidaan puolestaan laskea kaavasta (merkintä[*,•_, -xr -xi+\ tarkoittaa konfiguraation nume­

roarvoa ¿-kantaisessa lukujärjestelmässä, esim.[llOja on desimaalijäijestel- män luku 6)

C = X k^-rkr'ixitjf[Xi.r,-, v.., xi+r]

<X,X,>r) (4.6)

_ \' b- [xi-r • * Xr • • Xi+Jà /* Г y • y • y • 1 {Xj-л-ч X|'+r)

Edellä esimerkkinä käytetyn soluautomaatin sääntö voidaan esittää muo­

dossa

(/[

,

,

] =/[

,

,

] =/[

,

] =/[

,

] =

,

l/[xi-i,*«>*/+i] = 0 muulloin.

Yleiseksi sääntökoodiksi saadaan

C = X 2lJxi*J f[x¡.ux¡,xM]

{x¡.\,x¡,xm)

= X

x‘

/ [*«-i д.л.+i]

{x,-i,x;,xi+i}

= 24/[1,0,0] + 22 Д0,1,0] + 21/[0,0,1] + 27/[l,l,l ]

=150io = 100101102

Yleisiä yksiulotteisia soluautomaattisääntöjä on kaikkiaan

k1™ (4.7)

kpl, sillä mahdollisia konfiguraatioita on ld2r+1) kpl ja kukin konfiguraatio voi tuottaa yhden ¿:sta tilasta. Täten esim. r= 1, k=2 soluautomaattisääntöjä on 256 kpl. Vastaavasti r=2, k=2 sääntöjä on 4294967296 kpl. Siis r:n suuretessa kasvaa sääntöjen lukumäärä todella nopeasti.

Laillisiksi soluautomaattisäännöiksi (engl. “legal rules”) sanotaan niitä, jot­

ka säilyttävät symmetrian ja nollakonfiguraation:

f[xjv-,Xj]=f[xjs,...,Xj] ja /[0...0 ] = 0, Xj-eQ, (4.8) missä Q on soluautomaatin tilajoukko. Laillisuus eli symmetriaominaisuuk- sien ja nollakonfiguraation säilyttäminen on eräänlainen fysikaalisten säily­

mislakien vastine soluautomaateille. Yleisiä yksiulotteisia laillisia sääntöjä on kaikkiaan

£*r+1(*r+l)/2 - 1 (4.9)

kpl. Siten laillisia r=l, k=2 sääntöjä on 32 kpl.

Tässä yhteydessä kannattaa huomata, että edellä esitellyt koodinumeroiden määritelmät eivät ole yksikäsitteisiä—siis kerrottaessa koodinumero on myös sanottava, mikä on kyseisen soluautomaatin soluympäristö ja tilojen lukumäärä sekä onko kyseessä totalistinen, ulkototalistinen vai yleinen koo­

dinumero.

Kuva 43 Yksiulotteisia r=l, k=2 soluautomaatteja, yleiset koodinumerot 22, 30 ja 110. Simulaa- tioaskeleita on laskettu 50 kpl. Sääntö 22 on laillinen eli se säilyttää nollakonfiguraation ja symmetrian.

4.3 Yksiulotteisten soluautomaattien perusmalleja

Perusmalleiksi (engl. “elementary cellular automata” eli ECA) kutsutaan yksiulotteisessa tapauksessa soluautomaatteja, joiden naapuristo koostuu keskussolusta ja sen kummastakin naapurisolusta, ja joiden soluilla on vain kaksi tilaa. Edellä käyttöön otetun merkintätavan mukaan kysessä ovat siis r= 1, k=2 soluautomaatit. Tällaisten soluautomaattien esittelyä ja analyysiä löytyy ennen kaikkea [5]:sta.

Kuvassa 4.3 on esitetty kolmen yksiulotteisen r=l, k=2 soluautomaatin evoluutio lähdettäessä konfiguraatiosta, jossa on keskellä yksi nollasta poik­

keava solu. Kuvassa 4.4 on erään soluautomaatin evoluutio lähdettäessä satunnaisesta alkutilasta.

Simuloinnit on tehty käyttäen Mathematica-ohjelman mukana tulevaa Cel- lularAutomata-työtilaa. Soluautomaatin aikakehitys on esitetty matriisimuo- dossa, jossa kullakin rivillä esitetty on tietyn aika-askeleen konfiguraatio.

Ylin rivi on alkukonfiguraatio, ja alempana olevat rivit kuvaavat myöhem­

piä konfiguraatioita.

4.4 Soluautomaattien luokittelu

Viitteessä [5] (s. 91-125 ja s. 189-231) esitetään yksiulotteisten soluauto­

maattien jaottelu neljään luokkaan:

1) Homogeeniset soluautomaatit: Evoluutio tuottaa homogeenisen konfi­

guraation. Täten alkutilan kuviot katoavat ajan kuluessa.

Aika

I

Kuva 4.4 Yksiulotteinen г-l, k=2 soluautomaatti. sääntökoodi 22. Soluautomaatin koko on 200 solua, periodiset reunaehdot. Simulaatioaskeleita on laskettu 100 kpl. Satunnainen alkutila.

2) Jaksolliset soluautomaatit: Evoluutio tuottaa stabiileja tai periodisia rakenteita. Alkutilan kuviot kasvavat vain äärellisen kokoiseksi.

3) Kaoottiset soluautomaatit: Evoluutio johtaa kaoottiseen tai fraktaali- seen tilaan. Alkutilan kuviot kasvavat rajatta vakionopeudella.

4) Laskennalliset soluautomaatit: Evoluutio tuottaa monimutkaisia pai­

kallisia rakenteita, jotka kykenevät laskennallisiin operaatioihin ja jopa universaalilaskentaan. Alkutilan kuviot voivat kasvaa tai supistua

ajan kuluessa.

Kuvassa 4.5 on esimerkki kustakin soluautomaattityypistä. Laskut on tehty tätä varten ohjelmoidulla Mathematica-paketilla, joka kykenee simuloimaan mm. yksiulotteisia totalistisia yli kaksi tilaa omaavia soluautomaatteja.

Soluautomaattien käyttäytymistä voi tutkia muuttamalla hiukan solun alkutilaa ja vertaamalla soluautomaattien kehittymistä ajan funktiona. Ku­

vassa 4.6 on edellä esitettyjen soluautomaattien differenssikuvaajat (eli on tulostettu solut jotka muuttuvat kun alkukonfiguraatiossa muutetaan yhden solun arvoa).

Kuvasta 4.6 havaitaan, että homogeenisissa soluautomaateissa eivät paikal­

liset muutokset muuta lopputilaa ja että jaksollisissa soluautomaateissa al­

kutilaan tehty muutos vaikuttaa vain paikallisesti.

Kaoottisissa soluautomaateissa paikallinen muutos leviää systeemiin rajatta ja soluautomaatin lopputilat divergoivat eksponentiaalisesti toisistaan. Tä­

män voi havaita esim. laskemalla alussa tehdyn muutoksen vaikutusta solu- automaatin konfiguraatioiden informaatiosisältöön (esim. entropiaan). Ku­

van 4.6 kolmannessa esimerkissä muutos näyttää liikkuvan tietyllä vakio- nopeudella kumpaankin suuntaan. Muuttuneiden tilojen lukumäärä on ver­

rannollinen t°:aan, missä t on muutoksesta kulunut aika ja a on muutoksen

Kuva 4.5 Yksiulotteisten soluautomaattien neljä luokkaa. Totalistiset r=l, k=3 säännöt (vasemmalta oikealla ja ylhäältä alas): 1302 (homogeeninen), 1005 (jaksollinen), 444 (kaoottinen) ja 792 (laskennallinen). Soluautomaateilla sama satunnainen alkutila.

f

A ^\

Kuva 4.6 Yksiulotteisten soluautomaattien differenssikuvaajat. Totalistiset r=l, k=3 säännöt: 1302, 1005, 444 ja 792. Soluautomaateilla on sama satunnainen alkutila, jossa yhden solun arvoa on muutettu; kuvissa on esitetty solut, joiden aikakehitykseen muutos vaikuttaa.

etenemisnopeus. (Dynaamisten systeemien teoriassa eksponenttia a vastaa ns. Lyapunovin eksponentti. Jos Lyapunovin eksponentti on positiivinen, systeemin sanotaan olevan kaoottinen [25].)

Laskennallisessa soluautomaatissa alkukonfiguraatioon tehty muutos voi vaikuttaa soluautomaatin myöhempään tilaan hyvin monimutkaisella taval­

la. Muutoksen vaikutusta on yleisesti ottaen mahdotonta suoraan ennustaa;

soluautomaatin evoluutio on laskettava läpi kokonaisuudessaan.

Laskennalliset yksiulotteiset soluautomaatit tuottavat usein periodisia solu- hilassa eteneviä rakenteita, solitoneja ([5] s. 333-342 ja 391-394). Osa soli-

Ioneista vaatii tietyn taustakonfiguraation edetäkseen. Tähän liittyen olete­

taan, että osa tällaisista soluautomaateista kykenee universaalilaskentaan—

ongelmana on sopivien rakenteiden löytäminen laskennan toteuttamiseksi.

Tähän mennessä on löydetty universaalilaskentaan kykenevä r=l, k=l solu- automaatti [16].

5 Kaksiulotteiset soluautomaatit

5.1 Määritelmiä

Kaksiulotteisia soluavaruuksia voi olla montaa eri tyyppiä—solut voi jär­

jestää suorakulmaiseksi tai heksagonaaliseksi hilaksi ja naapurisuhteen määrittelyä voi muuttaa mielivaltaisesti. Seuraavassa keskitytään suorakul­

maiseen hilaan ja ns. von Neumannin ja Mooren naapuristoihin (kuva 5.1).

Kuten yksiulotteisessakin tapauksessa, voivat soluautomaattisäännöt olla totalistisia, ulkototalistisia tai täysin yleisiä. Esim. von Neumannin naapu­

ristossa olisi yleisiä binäärisiä soluautomaattisääntöjä 232 eli noin 4 mil­

jardia kpl. Eniten lienee tutkittu ulkototalistisia Moore-naapuriston solu- automaatteja—erilaisia binäärisiä sääntökoodeja on 218 eli noin 0,3 miljoo­

naa kpl. Mm. Life-peli kuuluu tähän ryhmään.

Kaksiulotteisille soluautomaateille voidaan määritellä numerokoodit samalla tavalla kuin yksiulotteisillekin. Seuraavassa määritellään ulkoto- talistisen soluautomaatin koodinumero Cut:

k-1

Cut = II^-/[o,«]

a=0 «

(5.1)

Tässä n on luonnollisesti naapurisolujen tila-arvojen summa ja a on keskus- solun oma entinen arvo. Life-pelin säännöt on määritelty kappaleessa 5.2;

Kuva 5.1 von Neumannin (vas.) ja Mooren naapuristot.

käyttämällä yllä olevaa kaavaa saadaan Lifen ulkototalistiseksi koodinume­

roksi 224! 0.

Vastaavasti voidaan määritellä totalistinen koodinumero Ct. Yleinen koodi- numero C voidaan määritellä, jos solunaapuriston solut asetetaan tiettyyn järjestykseen sääntökoodin laskemista varten. Jatkossa käytetään kuitenkin vain ulkototalistisia koodeja; naapuristona on tavallisesti Mooren solu- naapuristo, jossa erilaisia sääntöjä on edellä esitetyn mukaisesti 0,3 mil­

joonaa kpl. von Neumannin naapuristossa on ulkototalistisia sääntöjä vain 210 eli 1024 kpl. Kannattaa kuitenkin muistaa, että von Neumann-naapu- riston ulkototalistiset soluautomaatit eivät ole Moore-naapuriston ulkotota- lististen soluautomaattien osajoukko.

5.2 Life-peli

Perinteinen esimerkki soluautomaatista on Life [17], joka on ulkototalis- tinen kaksiulotteiseen suorakulmaiseen hilaan rakentuva soluautomaatti.

Lifen soluilla on kaksi tilaa, “elossa” ja “kuollut”. Solunaapuristoon laske­

taan keskussolua lähimpänä olevien neljän solun lisäksi diagonaalisilta suunnilta löytyvät neljä solua (Mooren naapuristo). Soluautomaatti sääntö on yksinkertainen ulkototalistinen summaus sääntö, jossa lasketaan yhteen “elä­

vät” solunaapuriston solut. Sääntö on seuraava:

Jos naapureista on kolme elossa, naapuriston keskelle syntyy uusi solu.

Jos naapureista on kaksi tai kolme elossa, vanha solu säilyy hengissä.

Muussa tapauksessa elossa oleva solu kuolee joko “yksinäisyyteen”

tai “liikakansoitukseen”.

Life kuvaa jossain määrin biologisten populaatioiden kasvuilmiöitä, joten

Naapurisoluja

Solunaapuriston keskussolu

Kuva 52 Ufe-pelin solunaapuriston rakenne. Naapuristoon kuuluu 8 naapurisoilta ja keskussolu.

Kuva 53

Kuva 5.4

Life-pelin eräs satunnainen alkutila sekä konfiguraatiot ajanhetkillä 10 ja 160.

Tyypillinen Life-pelissä esiintyvä liitokone ("glider"). Liitokone etenee 1 +1 solua neljässä askeleessa.

“elämäpeli”-nimitys onkin varsin onnistunut.

Life-peliä on tutkittu paljon, ja on osoitettu että Life kykenee universaalilas- kentaan eli simuloimaan mitä tahansa muuta tietokonetta [26]. Todistus perustuu siihen, että valitsemalla sopivat alkukonfiguraatiot voidaan Life- pelillä mallittaa kaikkia tietokoneen rakentamiseen tarvittavia piirejä.

Soluautomaattien lopputiloja kutsutaan rajajoukoiksi, ja muutamia Lifelle tyypillisiä rajajoukkoihin kuuluvia konfiguraatioita näkyy kuvassa 5.3. Ky­

seessä on esimerkki Life-pelin evoluutiosta lähdettäessä pienestä satun­

naisesta alkukonfiguraatiosta. Lopputila on jaksollinen ja stabiili, mikä on tyypillistä pienestä satunnaisesta alkukonfiguraatiosta lähtevälle Lifelle.

Suuremmissa alkukonfiguraatioissa on monimutkaisempien rakenteiden syntyminen todennäköisempää.

Life-pelistä tunnetaan monia erityyppisiä jaksollisia, soluhilassa eteneviä värähtelijöitä, ns. liitokoneita (engl. “glider”), sekä näistä koottuja moni­

mutkaisempia kokonaisuuksia. Kuvassa 5.4 on esitetty erään tällaisen lii- tokoneen aikakehityksen neljä vaihetta.

Kuva 5.5 Ufe-pelin eräs satunnainen alkutila sekä konfiguraatio ajanhetkellä 342 (kaksi liitokonetta kuvan ulkopuolella).

5.3 Rajajoukoista

Satunnaisesta alkukonfiguraatiosta käynnistetyn Life-pelin lopputilat ovat useimmiten varsin yksinkertaisia. Tyypillisesti jonkin ajan kuluttua alusta syntyy hyvinkin monimutkaisia systeemejä, mutta liitokoneet tai muut hilassa etenevät rakenteet tuhoavat ne ennemmin tai myöhemmin. Lopputila koostuu useimmiten yksinkertaisista, stabiileista, toisistaan erossa olevista rakenteista sekä “vapaiksi” päässeistä liitokoneista, jotka kulkeutuvat pois­

päin alkukonfiguraatiosta.

Rakentamalla Life-pelille sopiva alkukonfiguraatio on kuitenkin mahdol­

lista saada aikaan hyvin monimutkaista käyttäytymistä. Lisäksi Lifelle on ominaista, että alkutilaan tehdyn pienen muutoksen vaikutuksia on yleensä mahdotonta ennakoida muuten kuin simuloimalla soluautomaatin evoluutio askel askeleelta. Tällainen käyttäytyminen on ominaista ei-triviaaleille solu- automaateille. Lifen epälineaarisuutta havainnollistanee esim. lopputilan muuttuminen, kun kuvan 5.3 satunnaista alkutilaa muutetaan yhdellä kulmasolulla—tämä on esitetty kuvassa 5.5.

Viitteessä [27] on osoitettu, että soluautomaatin rajajoukon kaikki ei- triviaalit ominaisuudet (eli ominaisuus on joillakin soluautomaateilla mutta ei kaikilla) ovat algoritmisesti ratkeamattomia. Ei siis ole olemassa yleistä algoritmia, joka kertoisi onko jollakin soluautomaatilla tietty ei-triviaali ominaisuus.

Lifea kiinnostavampia systeemejä fysikaaliselta kannalta ovat tietysti ne, jotka automaattisesti hakeutuvat johonkin “mielenkiintoiseksi” katsottuun

havaittu erittäin monimuotoisia vuorovaikutuksia (viitteen [5] liite).

Mielenkiintoinen soluautomaattien luokka on kriittisiä ilmiöitä mallittavat systeemit ([2] s. 112-115). Ns. itseorganisoituvat kriittiset systeemit ovat tyypillisesti melko pitkälle riippumattomia alkukonfiguraatiosta—ne hakeu­

tuvat itsestään kriittiseen tilaan, olkoot alkutila ja sisäänmenosignaali lähes millaisia tahansa [28,29,30,31].

5.4 Kaksiulotteiset hilakaasut

Hydrodynamiikassa on perinteisesti käytetty liukulukulaskentaa. Neste kuvataan kenttänä, joka toteuttaa halutut osittaisdifferentiaaliyhtälöt. Sopi­

van diskretoinnin jälkeen systeemin tilaa kuvataan tietokoneessa liukulu­

vuilla. Näillä menetelmillä on pitkät perinteet, joten nykyiset supertieto­

koneet ovat erittäin tehokkaita osittaisdifferentiaaliyhtälöden ratkomisessa.

Toisaalta perinteisten algoritmien rinnakkaistus on vasta alkuvaiheissa, eivätkä perinteiset mallitustavat välttämättä anna yhtä hyviä tuloksia kuin täysin rinnakkaiset mallit, esim. hilakaasut [32,12].

Hilakaasumallit ovat soluautomaatteja, joissa tila-avaruuden arvot kuvaavat solussa sijaitsevia hiukkasia. Soluautomaattisäännön tulee toteuttaa joukko säilymislakeja—esim. energian ja liikemäärän säilyminen. Lisäksi voidaan asettaa joukko symmetriaehtoja.

Kuva 5.6 HPP- ja FHP-hilakaasujen soluautomaattihilat. Suorakulmainen HPP-hila on symmetrinen 90°kiertojen suhteen. FHP-mallin kolmiohila on symmetrinen 60° kiertojen suhteen.

Ns. HPP-hilakaasumalli on peräisin vuodelta 1973. Mallin kehittivät Hardy, Pomeau ja de Pazzis. Kyseessä on suorakulmainen kaksiulotteinen soluau- tomaattihila, jonka soluautomaattisääntö on kaksiosainen. Ensimmäisessä vaiheessa lasketaan törmäykset kussakin solussa sijaitsevien hiukkasten välillä. Toisessa vaiheessa hiukkaset kulkeutuvat haluttuihin suuntiin.

HPP-hilakaasumallin ongelmana on mm. se, että malli ei ole isotrooppinen (ks. [5] s. 358-361). Ongelma johtuu lähinnä suorakulmaisen hila-avaruu­

den käytöstä. Jos siirrytään käyttämään kolmiohilaa (kuva 5.6), päästään tästä ongelmasta. Tätä hilakaasumallia kutsutaan FHP-malliksi sen kehittä­

jien (Frish, Hasslacher ja Pomeau) mukaan.

6 Soluautomaatit verrattuina muihin systeemeihin

6.1 Dynaamisten systeemien hierarkia

Taulukossa 6.1 on verrattu erityyppisiä dynaamisia systeemejä keskenään.

Havaitaan, että lähimpänä soluautomaatteja ovat dynaamiset hilasysteemit (engl. “lattice dynamical systems” tai “coupled map lattices”). Soluauto- maateissa tilat ovat diskreettejä, dynaamisissa hilasysteemeissä jatkuvia.

Yleisessä N-ulotteisessa dynaamisessa systeemissä N:n muuttujan väliset riippuvuudet voivat olla millaisia tahansa, ongelmasta riippuen. Jatkossa rajoitutaan käsittelemään translaatio-invariantteja järjestelmiä, ns. avaruu­

dellisia dynaamisia systeemejä (engl. “spatial dynamical systems”). Tämä tarkoittaa lähinnä sitä, että tyydytään paikallisiin symmetrisiin riippuvuus­

suhteisiin.

6.2 Dynaamiset hilasysteemit

Dynaamiset hilasysteemit koostuvat säännöllisen hilan paikallisessa naapu­

ristossa V¡ yhteen kytketyistä iteroiduista kuvauksista

Malli Avaruus Aika Tila-avaruus

Osittaisdifferentiaaliyhtälöt J J J

Iteroidut funktionaaliyhtälöt J D J

Oskillaattoriketjut D J J

Dynaamiset hilasysteemit D D J

Soluautomaatit D D D

J = jatkuva, D = diskreetti

Taul. 6.1 Dynaamisten systeemien luokittelu.

x/+1 = F ^(6.1)

Vektori x* = (x0tjcIt,...jcN_1t') on systeemin tila ajanhetkellä t e {0,1,...} ja hilaelementin indeksi / e {0,1,...,N-1}. Painokertoimet wj kuvaavat hilanaa- purien kytkennän voimakkuutta.

Esimerkki dynaamisesta hilasysteemin paikallisesta funktiosta on logistinen kuvaus F

(6.2)

f(x) = rx(l -x),

missä r jax ovat skalaareja (r on yleensä väliltä [0,4]). Jos yksiulotteisen systeemin naapuristoon kuuluu keskussolu ja sen kumpikin naapuri, voisi kuvaus painokertoimineen olla muotoa

(6.3)

missä e on naapurisolujen “kytkentäkerroin” ja F esim. logistinen kuvaus.

6.3 Kaaos dynaamisessa hilasysteemissä

Kun yhtälön (6.2) r kasvaa, siirtyy logistinen hilasysteemi kaaokseen [33].

Aluksi syntyy selvien rajojen erottamia osasysteemejä, joissa r:n kasvaessa tapahtuu periodin kahdentumista. Lopuksi katoavat kaikki rajatkin ja systeemi suistuu kaaokseen.

Kuvassa 6.1 on esitetty logistisen hilasysteemin bifurkaatiokäyttäytyminen.

Parametria r kasvatettaessa havaitaan aluksi periodin kahdentumisilmiö.

Lopulta suistutaan kaaokseen, jolloin alussa syntyvien jaksollisten saarekkeiden rajat häviävät.

Kuva 6.1 Logistinen dynaaminen hilasysteemi, joka koostuu 50:stä värähtelijästä. Simulaatioaske- leita on laskettu 50; kuviin on tulostettu 8 viimeistä konfiguraatiota. Vaaka-akselilla on esitetty hilasysteemin värähtelijät, pystyakselilla niiden tilat. Parametri e = 0.1 ; r vaihte- lee.

6.4 Dynaamisen systeemin diskretointi

Dynaaminen hilasysteemi voidaan diskretoida soluautomaatiksi. Edellä esitetyn logistisen hilasysteemin diskretointiin sopii yksidimensioinen solu- automaatti. Riippuen e:n ja r:n arvoista saadaan erilaisia soluautomaatti- sääntöjä. Viitteessä [34] on kuvattu erään toisen dynaamisen hilasysteemin diskretointia soluautomaatiksi.

Kuva 6.2 Logistisen hilasysteemin aikakehitys. Systeemin koko N=50, aika-askeleila 50 kpl.

Hilapisteet, joiden arvo ylittää tietyn kynnyksen, on kuvattu mustina, muut valkoisina.

F (x) = x <1 - x) 0.25-

0.IS-

О.05-

Kuva 63 Logistisen kuvauksen eräs diskretointimahdollisuus.

Logistisen hilasysteemin diskretointi sujuu seuraavasti. Aluksi otetaan käyt­

töön diskreetti tilavektori x‘ e Qs (Q on halutuntyyppisen soluautomaatin tila-avaruus ja s tilavektorin pituus). Tämän jälkeen haetaan hilasyseemiä

0.5 36, 126 00100100,01111110

0.75 126 01111110

1.0 90 01011010

T aul 62 Logistista hilasysteemiå vastaavat soluautomaatit.

Kuva 6.4 Soluautomaattisäännöt 36,126ja 90 (r=l, k-2). Satunnaiset alkutilat.

kuvaava soluautomaattisääntö f¿. Tämä voidaan tehdä esim. laskemalla xf+i-.n arvot kaavojen (6.2) ja (6.3) avulla kaikille mahdollisille solunaa- puriston konfiguraatioille (х,„/л/д,+/0 eri e:n arvoilla. Saadut luvut voi­

daan sovittaa soluautomaatin tila-avaruuteen r:n arvoa muuttamalla. Täten saadaan laskettua joukko soluautomaattisääntöjä, jotka voidaan kirjoittaa normaaleiksi paikallisiksi soluautomaattisäännöiksi f¿.

Soluautomaattisääntöjen hakemisen voi automatisoida esim. Mathematican avulla. Taulukossa 6.2 on e:n arvoilla 0, 0.3, 0.5 ja 1.0 saadut k=2, r= 1 soluautomaattisäännöt (r:n arvot väliltä [0.0,6.0]).

Kuvassa 6.4 on esitetty logistista hilasysteemiä vastaavien ei-triviaalien soluautomaattien aikakehitys satunnaisesta alkutilasta. Havaitaan, että jopa näinkin karkea diskretointi tuottaa jossain mielessä “oikeanlaisia” approk­

simaatioita: soluautomaattisääntö 36 tuottaa periodisia paikallisia rakenteita,

“vyöhykkeitä”; soluautomaattisäännöt 126 ja 90 puolestaan tuottavat erita­

soisia fraktaalisia ja kaoottisia rakenteita.

7 Soluautomaatit tietojenkäsittely- systeemeinä

7.1 Automaattien teoriaa

Soluautomaattien evoluution voi tulkita tietojenkäsittelyksi, jossa prosessoi­

daan soluautomaatin alkutilaan sisältyvää informaatiota. Jos kyseessä on kääntyvä soluautomaatti (eli on olemassa soluautomaattisääntö f, joka tuottaa soluautomaattisäännön f konfiguraatiot käänteisessä järjestyksessä lähdettäessä /:n lopputilasta), ei informaation määrä luonnollisesti voi muuttua ([5] s. 232-246; [35]). Toisaalta useat soluautomaatit ovat ei- kääntyviä, ns. itseorganisoituvia (engl. “self-organizing”) systeemejä. Täl­

löin voi myös satunnaisesta alkutilasta lähdettäessä syntyä monimutkaisia järjestyneitä rakenteita.

Soluautomaattien laskennallisia ominaisuuksia on tutkittu mm. viitteissä [16,36,37]. Hyvä johdatus aiheeseen on viitteessä [5] s. 189-231.

Formaalit kielet koostuvat joukosta sanoja, jotka on muodostettu jonosta äärelliseen merkistöön kuuluvia symboleja tiettyjen kielioppisääntöjen avul­

la. Soluautomaatin tila-avaruus Q voidaan siis käsittää tietojenkäsittelysys­

teemin merkistöksi. Merkistöön kuuluvien symbolien jonot muodostavat so­

luautomaatin mahdollisten konfiguraatioiden joukon. Täten soluautomaatin konfiguraatioiden voidaan katsoa vastaavan formaalin kielen sanoja. Solu- automaattien evoluutiota voi verrata esim. L-systeemeihin [38,39].

7.2 Soluautomaattien tilastolliset ominaisuudet

Soluautomaatit ovat tilastollisessa mielessä lähellä mikroskooppisia fysi­

kaalisia systeemejä—ne koostuvat usein suuresta joukosta yksinkertaisia soluja (“hiukkasia” tai “hilapisteitä”), jotka paikallisten vuorovaikutuksien

Soluautomaatit poikkeavat fysikaalisista systeemeistä siinä, että ne eivät tyypillisesti ole kääntyviä: jos tiedetään soluautomaatin nykyinen tila, ei voida aina yksikäsitteisesti päätellä soluautomaatin aikaisempia konfiguraa­

tioita. Toki kääntyviäkin soluautomaatteja voidaan rakentaa ([11], luku 14).

(Soluautomaattien kääntyvyyden on osoitettu olevan algoritmisesti ratkea­

maton ominaisuus viitteessä [27]. Toisaalta yksiulotteisten soluautomaattien kääntyvyysongelma on ratkaistu artikkelissa [35].)

Jos deterministisen soluautomaatin jollakin konfiguraatiolla on useampia mahdollisia aikaisempia konfiguraatioita, tarkoittaa tämä sitä että on ole­

massa jokin muu konfiguraatio, joka voi olla vain alkutila eli se ei synny koskaan soluautomaatin evoluutiossa. Tällaista konfiguraatiota kutsutaan

“Eedenin puutarhaksi”, ja sellaisen olemassaolo on suoraan seurausta solu- automaatin kääntymättömyydestä ja äärellisestä tilajoukosta ([5] s. 57).

Hyvä johdatus soluautomaattien tilastolliseen analyysiin löytyy viitteestä [5] s. 7-50 ja s. 91-125.

Usein käytetty soluautomaatin aikakehityksen mitta on entropia, joka voidaan määritellä soluautomaatin X:n mittaiselle konfiguraatiolohkolle esim. seuraavasti (ns. avaruudellinen joukkoentropia):

= logt (.X 6(Py)| <7Л)

missä k on soluautomaatin tilojen lukumäärä ja todennäköisyydet pj ovat eri konfiguraatioiden esiintymistodennäköisyydet X:n mittaisessa lohkossa.

Funktio в on askelfunktio, jolle pätee (Kp) = 1 jos p > 0 ja 0(0) = 0.

Summalausekkeessa lasketaan itse asiassa soluautomaatin generoimien eri­

laisten X:n mittaisten lohkojen lukumäärä. Jos kaikki k* kpl X:n mittaista lohkoa generoituvat soluautomaatin evoluutiossa, on s(X) = 1.

Toinen yleisesti käytetty tilastollinen suure on ns. avaruudellinen mitta- entropia:

7.3

kx

sß(X) = -±r X Pj lo8*(Pjl Л 7 = 1

(7.2)

Mittaentropia ilmaisee solun keskimääräisen informaatiosisällön, kun ote­

taan huomioon solujen väliset korrelaatiot X:n mittaisiin lohkoihin asti. Jos kaikkien konfiguraatioiden todennäköisyys on yhtä suuri, on s^(X) = 1.

Yhtälöitä (7.1) ja (7.2) vastaavat kaavat voidaan johtaa myös soluautomaa- tin aikakehitykselle. Tällöin tarkastellaan tietyn ajanhetken konfiguraatiosta havaittujen X:n mittaisten lohkojen sijaan X:n mittaisia historioita yhden solun aikakehityksessä.

Yleisesti ottaen ovat soluautomaatin avaruudelliset ja ajalliset entropiat aivan eri asioita. Tutkittaessa soluautomaatin käyttäytymistä täytyykin usein ottaa huomioon sekä ajalliset että paikalliset vuorovaikutukset solujen vä­

lillä.

Soluautomaattien kompleksisuuden analyysiin käytettyjä erityyppisiä mitto­

ja kuvataan artikkeleissa [41] ja [42]. Dynaamisten systeemien entropian laskemista käsitellään viitteessä [43]; esimerkkinä on yksidimensioinen k=2, r=l soluautomaattisäänto 22. Soluautomaatin korrelaatiokäyttäytymistä on analysoitu viitteessä [44].

Soluautomaattien tilastolliseen käyttäytymiseen liittyy mm. ergodisuuden käsite: stokastinen prosessi on ergodinen, mikäli sen stationäärinen jakauma on alkutilasta riippumaton. Tyypillisesti soluautomaatit eivät ole ergodisia.

Tämä tarkoittaa sitä, että alkutilasta riippuen voidaan saavuttaa hyvinkin erilaisia lopputiloja. Universaalilaskentaan pystyvä systeemi ei luonnollises­

ti voikaan olla ergodinen ([5] s. 455-458). Tällainen soluautomaatti ilmen­

tää itseorganisoituvien systeemien kompleksisuuden huippua.

Soluautomaattien algebralliset ominaisuudet

Yksiulotteisia soluautomaatteja voidaan analysoida mm. ottamalla käyttöön ns. karakteristiset polynomit ([5] s. 51-90). Olkoon soluautomaatin koko N ja soluautomaatin solun i arvo ajanhetkellä t olkoon xft). Tällöin karak­

teristinen polynomi on

Additiivisen lähinaapurit huomioon ottavan soluautomaatin aikaevoluutio voidaan laskea kertomalla karakteristinen polynomi dipolynomilla (kahden polynomin osamäärällä)

П(a) = a.\a + ocq + а\ал, (7.4) eli

Х(,+1)(<з) = ОД X«\a) mod (aN - 1 ), (7.5) missä periodiset reunaehdot saadaan aikaan laskemalla dipolynomien ker­

tolasku modulo cF—1.

Esimerkiksi k=2, r=l yleinen soluautomaattisääntö 150 voidaan kuvata lau­

sekkeella

n(ti) = a+ 1 + ал,

missä yhteenlasku lasketaan modulo 2. Seuraavassa lasketaan esimerkkinä tilanne, jossa alkukonfiguraatio on (0,1,0,0,1,1} ja käytössä on periodiset reunaehdot. Tällöin karakteristinen polynomi x(°)(a)on

X(0)(a) = £ xfJ)a‘ = a + я4 + a5,

i = 0

Konfiguraatioksi hetkellä t = 1 saadaan:

X0)(a) = Ща) X(°>(fl)

= (a+ 1 +aA)(a + ai + a5)

= a6 + 2a5 + 2д4 + a3 + a2 + a + 1

= (a6 - l) + (2a5 + 2a4 + a3 + a2 + a + 2)

= a3 + a2 + a

mod (a6 - l)

Koska k=2, voidaan viimeisessä vaiheessa eliminoida termit, joissa on kertojana 2. Lopputulos lasketaan lisäksi modulo a6 - 1. Täten konfiguraa- tioksi hetkellä t = 1 saadaan {0,1,1,1,0,0}. Soluautomaatin evoluutiota voi­

daan siis käsitellä symbolisena laskentana.

Yleisesti ottaen soluautomaattien algebrallinen analyysi onnistuu vain eri­

koistapauksissa: usein soluautomaatin evoluution kompleksisuus on sitä luokkaa, ettei ole olemassa “nopeutussääntöä”, jolla voitaisiin laskea loppu­

tila suoraan alkutilasta. Viitteessä [4] on analysoitu fraktaalisten yksi­

ulotteisten soluautomaattien ominaisuuksia—mm. mahdollisia nopeutus- sääntöjä.

8 Soluautomaattien käyttökohteita

8.1 Rinnakkaiskoneet

Tietokoneiden luokitteluun käytetään yleisesti ns. Flynnin taksonomiaa, vaikka sen käsitteistö onkin jossain määrin vanhentunut [45]. Seuraavassa datavuolla (käskyvuolla) tarkoitetaan jonoa data-alkioita (käskyjä). Tieto­

koneet jaetaan Flynnin taksonomiassa taulukon 8.1 mukaisiin luokkiin.

Rinnakkaislaskennassa mahdollisuuksia ovat siis SIMD ja MIMD -koneet.

MISD on oikeastaan MIMD-koneiden luokka; MISD-koneita on tuskin muualla kuin laboratorioissa (eräät eksoottiset tietokantakoneiden prototyy­

pit ovat sisältäneet tämäntyyppisiä operaatioita).

8.2 Massiivisesti rinnakkaiset koneet

Supertietokoneissa on tyypillisesti pyritty mahdollisimman tehokkaisiin prosessoreihin, joilla on muutaman nanosekunnin kellojakso. Prosessorit tukevat vektorioperaatioita ja rinnakkaisuutta—esim. Crayssä voi useita liukuhihnoja olla käsiteltävänä kerrallaan, jolloin kyetään yhdessä kello- jaksossa tuottamaan useita tuloksia. Superkoneissa tarvitaan myös erittäin

Yksi käskyvuo Monta käskyvuota Yksi datavuo SISD

Perinteinen arkkitehtuuri (von Neumann).

MISD

Useita käskyjä operoi sa­

maa dataa yhtä aikaa.

Monta datavuota SIMD

Vektoriprosessorit, prosessorihilat.

MIMD

Useita prosessoreja, kulla­

kin oma ohjelma ja data.

Гаи/. 8.1 Tietokoneiden luokittelu Flynnin taksonomiassa.

nopeaa muistia—tämä on implementoitu usein joukkona vektorirekisterejä, joihin voidaan kirjoittaa ja joista voidaan lukea tietoa prosessorin kello­

taajuudella.

Massiivisesti rinnakkaiset koneet tavoittelevat suurta laskentanopeutta toisella tavalla. Yhden superprosessorin sijasta käytetään tuhansia halpoja prosessoreita, jollaisen ei tarvitse kyetä kovin ihmeellisiin laskutoimituk­

siin__esim. Connection Machinessa käytetään yhden bitin prosessoreita (ns.

“bit serial” prosessorit). Kun prosessoreita on käytössä tuhansia, saavute­

taan—ainakin teoriassa—perinteisen superkoneen teho.

Vaikka laitteistotasollakin riittää tekemistä tehokkaiden prosessorikonfi- guraatioiden löytämiseksi (esim. sopivan viestintämekanismin kehittäminen prosessorien välille ei ole triviaali tehtävä)—lienee massiivisesti rinnak­

kaisten koneiden suurin ongelma ohjelmistotasolla. Muutamia varsin kor­

kean tason työkaluja on kuitenkin jo saatavilla esim. Connection Machi- neen löytyy rinnakkaistettu FORTRAN.

Mitään joka käyttäjän koneita eivät massiivisesti rinnakkaiset koneet vielä kuitenkaan ole—käyttöjärjestelmiä massiivisesti rinnakkaisille koneille ei juuri ole olemassa, joten yleisesti ottaen koneita käytetään yhteen laskenta-

sovellukseen kerrallaan, useimmiten jonkin edustakoneen avustuksella.

8.3 Connection Machine

Connection Machine (CM) suunniteltiin alunperin tietokantakoneeksi, joka käsittelee semanttisiin verkkoihin talletettua tietoa rinnakkaisesti suurille tietojoukoille voidaan siis tehdä sama operaatio erittäin tehokkaasti. Suori­

tettavia käskyjonoja on kuitenkin vain yksi. Edellä esitetyn Flynnin takso­

nomian mukaan CM on siis SIMD-kone. Tätä voi verrata tavanomaisiin, korkeintaan muutaman kymmenen prosessorin MIMD-rinnakkaiskoneisiin, joissa käsitellään useita käskyjonoja rinnakkaisesti.

CM käsittelee dataa bitti kerrallaan, mikä merkitsee sitä että muistin käyttö on erittäin tehokasta (ei tarvitse jättää käyttämättömiä bittejä esimerkiksi sanarajojen takia kuten ns. sanakoneissa). Täten muuttuvamittaisilla tieto- alkioilla laskeminen sujuu tehokkaasti CM:ssä. Toisaalta esim. 64-bittisen kertolaskun suorittaminen bittiprosessoreissa ei ole tehokasta, koska ne

Ensimmäinen CM-arkkitehtuurin toteutus oli Thinking Machines Corp. - yhtiön CM-1. Tästä edelleen kehitetyssä CM-2 -koneessa on kutakin 32:ta bittiprosessoria kohti yksi Weitekin liukulukuyksikkö. Täten CM-2 kykenee tehokkaaseen laskentaan myös esim. liukulukujen kertolaskussa [46,47].

CM-2:n 65 536 prosessoria kykenevät useaan miljardiin laskutoimitukseen sekunnissa. Kokonaan toinen juttu sitten on, millainen teho käytännön las­

kutehtävissä saavutetaan. Kuitenkin esim. Mobil Oilin tutkijat ovat saavut­

taneet 5.6 miljardin liukulukuoperaation jatkuvan tehon seismisen datan analysointitehtävässä [48].

Yleisesti ottaen Connection Machinen tyyppiset SIMD-koneet soveltuvat hyvin suuria datamääriä sisältävien systeemien simulointiin (eli ns. data- intensiivisiin laskutoimituksiin). Sovelluskohteita löytyy erityisesti lokaa­

listen vuorovaikutusten aiheuttamista ilmiöistä. Tällöin kunkin prosessori- elementin tarvitsee tietää vain lähinaapunstoa simuloivien prosessorien tila.

Nämä tilakyselyt voidaan hoitaa tehokkaasti CM:ssä, jos prosessorihilan konfiguraatio on sopiva. Toisaalta jos näin ei ole, voi laskentanopeus pudota todella alhaiseksi.

Soluautomaattien simulointi Connection Machinessa

CM:n prosessorit on kytketty toisiinsa ns. hyperkuutio-topologian mukai­

sesti. Soluautomaattien simuloinnissa tärkeää on se, voidaanko tarvittava solunaapuristo toteuttaa CM:ssä. Jokaisella soluautomaatin simulointiaske- leella täytyy solunaapuriston solujen tilat välittää soluautomaattisäännön laskemista varten. Jos tämä voidaan hoitaa tehokkaasti—toisin sanoen jos täytyy viestiä vain naapureina olevien prosessointielementtien kesken kyetään soluautomaattia simuloimaan erittäin tehokkaasti. Soluautomaa- teissahan soluautomaattisääntö on sama kaikissa soluissa, joten simulointi onnistuu hyvin SIMD-laskentana [49].

Jos soluautomaatin soluja on enemmän kuin CM:ssa on prosessoreja (CM- 2:ssa korkeintaan 65 536 kpl), voidaan kullekin prosessointielementille antaa laskettavaksi useampi solu.

8.5 Soluautomaatit tietokonetekniikassa

Eräitä yksinkertaisia yksiulotteisia soluautomaatteja voi käyttää satunnais­

lukujen tuottamiseen ([5] s. 247-293). Tämä onnistuu esim. havainnoimalla jonkin solun aikakehitystä. Tilajono voidaan tulkita satunnaisluvuiksi. Yksi­

ulotteisesta n:n mittaisesta soluautomaatista saadaan n kpl tilojen aikaku- vaajia. Jos lähellä toisiaan olevien solujen tilakehityksen korrelaatio ei hait­

taa, voidaan tuottaa rinnakkain n satunnaislukujonoa.

Äärellisen kokoinen soluautomaatti toistaa itsensä lopulta eli on syklinen esim. kaksitilaisen n:n mittaisen yksiulotteisen soluautomaatin syklin mak­

simipituus on 2n — 1. Alkukonfiguraatio ja reunaehdot vaikuttavat myös usein lopputulokseen. Syklin maksimoimiseen tarvitaan toisinaan periodiset reunaehdot, toisinaan riittää nollatilojen käyttö reunaehtoina [50].

Viitteessä [49] kerrotaan soluautomaattien käytöstä superlaskentaan. Artik­

kelissa kuvataan yleistä yksiulotteista (r=l, k=2) soluautomaatti sääntöä (sääntökoodi 30), jonka tilastolliset ominaisuudet läpäisevät useita satun- naisuustestejä. Artikkelin mukaan Connection Machinen tärkein satunnais­

lukugeneraattori on toteutettu tämän soluautomaattisäännön avulla.

Viitteessä [50] on käsitelty soluautomaattityyppisen satunnaislukugene­

raattorin käyttöä tietokonepiirien diagnostiikassa tavanomaisten lineaaristen takaisinkytkentärekisterien (engl. “linear feedback shift register ) sijasta.

Tuloksena on, että sopiva kahdesta yksinkertaisesta soluautomaattisään- nöstä yhdistetty hybridisääntö tuottaa perinteistä menetelmää parempia satunnaislukujonoja. Myöskin piirin toteutus voidaan tehdä perinteistä me­

netelmää yksinkertaisemmin.

9 Kriittiset ilmiöt

9.1 1/f-skaalautuvuus

Luonnosta löytyy suuri joukko ilmiöitä, jotka ovat itsesimilaarisia aika- tai paikkaskaalauksen suhteen. Tyyppiesimerkkejä paikallisesti skaalautuvista systeemeistä ovat vuoristojonot, jokiverkostot ja rantaviivat [51]. Ajallisesti skaalautuvia ovat esim. maanjäristyksistä, pörssikursseista ja auringon­

pilkuista havaitut signaalit. Skaalautuvuus on usein 1/f-tyyppiä, eli signaalin amplitudin tai frekvenssin jakauma noudattaa yhtälöä

(9.1)

missä a~ 1. Tämä tarkoittaa esimerkiksi sitä, että pieniä maanjäristyksiä on erittäin paljon ja suuria vähän. Maanjäristyksien on havaittu olevan skaa­

lautuvia kymmenen dekadin alueella, ja on esitetty arvioita, että skaalau­

tuvuus pätisi vieläkin suuremmalla alueella. Kaikkein isoimpia maanjäris­

tyksiä on kuitenkin joka tapauksessa niin harvassa, että asiaa on vaikea todistaa [52].

Teoreettiselta kannalta 1/f-skaalautuvuus on pulmallista, sillä on vaikea selittää, miksi jokin systeemi käyttäytyy similaarisesti suuresti toisistaan poikkeavilla aika- ja paikkaskaaloilla. Ns. kriittisten ilmiöiden tutkimus on antanut jonkin verran viitteitä ilmiön syntymekanismeista. Viime aikoina on esitetty uusi selitysmalli näille ilmiöille ns. itseorganisoituvan kriittisyyden pohjalta [28,29,30,31,53].

Skaalautuvuuteen liittyy luonnollisesti myös fraktaalisuus [51]. Fraktaali- geometriahan pyrkii tarjoamaan välineet nimenomaan itsesimilaaristen ilmiöiden analysointiin. Toisaalta soluautomaattien aika- ja palkkakehitys on usein fraktaalista (ks. liitekuvat), joten voisi kuvitella, että soluauto-