Detectarea fenomenelor Detectarea fenomenelor complexe in automate celulare complexe in automate celulare

sisi paralelismul cu structurile vii paralelismul cu structurile vii

Adrian IftimeDepartamentul de Bioinginerie si Biotehnologie, Inginerie Medicala

si Clinica- Univ. Politehnica Bucuresti -

Etapele temei de dizertatieEtapele temei de dizertatie

1. Crearea uneltelor software pentru dezvoltarea de automate semitotalistice si totalistice

2. Generarea de automate celulare semitotalistice si aprecierea numerica a aparitiei fenomenelor emergente in fiecare generatie

3. Generarea de automate celulare totalistice si repetarea pasilor enumerati anterior

4. Identificarea claselor de fenomene emergente5. Asocierea fenomenelor emergente cu

fenomenele similare din tesuturile vii (atat normale cat si patologice)

Automate celulare: definireAutomate celulare: definire1.1. Matrice de elemente denumite “celule”, cu valori Matrice de elemente denumite “celule”, cu valori

discrete (simplificat, 0 sau 1)discrete (simplificat, 0 sau 1)

1.1. Unidimensionale - a(i)Unidimensionale - a(i)

2.2. Bidimensionale - a(i,j)Bidimensionale - a(i,j)

3.3. Multimensionale - a(i,j,…..,n) (dificil de Multimensionale - a(i,j,…..,n) (dificil de cercetat datorita volumului mare de calcule) cercetat datorita volumului mare de calcule)

2.2. Lege (sau set de legi) de evolutie in timp a setului Lege (sau set de legi) de evolutie in timp a setului de celulede celule

John Conway, 1970

Descrierea unui automat celular 2DDescrierea unui automat celular 2D

Definirea unei vecinatati intr-un Definirea unei vecinatati intr-un automat celular 2Dautomat celular 2D

Vecinate = 9

Vecinate = 5

Automatul celular denumit “Automatul celular denumit “Game of LifeGame of Life” a devenit ” a devenit remarcat prin asemanarea evolutiei sale in timp cu remarcat prin asemanarea evolutiei sale in timp cu

evolutia sistemelor celulare biologiceevolutia sistemelor celulare biologice

Automatul celular denumit “Automatul celular denumit “Game of LifeGame of Life” a devenit ” a devenit remarcat prin asemanarea evolutiei sale in timp cu remarcat prin asemanarea evolutiei sale in timp cu

evolutia sistemelor celulare biologiceevolutia sistemelor celulare biologice

Fenomen evolutiv (“puffers”)

Fenomen repetitiv (“oscilators”)

““Game of LifeGame of Life” este doar un caz particular de automate ” este doar un caz particular de automate celulare. Setul de legi de evolutie poate fi descris in celulare. Setul de legi de evolutie poate fi descris in

mod binar (tabel boolean) si generalizat.mod binar (tabel boolean) si generalizat.

PARAMETRI:    - vecinatate de 5 celule cu conventia de notare: "3" este celula centrala   1  

2 3 4

  5  

Numar total de functii “live or die”:

210 = 1024

(deci 1024 de automate posibile)

Setul de legi de evolutie descris in mod binar este dificil Setul de legi de evolutie descris in mod binar este dificil de urmarit si de implementat. de urmarit si de implementat.

• Pentru un automat cu vecinatate =9, exista 524288 legi, asa ca am scris un program simplu pentru crearea de tabele de legi – ID, tot in Visual C++

• Programul este disponibil pe serverele web create pentru facilitarea colaborarii intre cei doi colabolatori la acest proiect.

• Pentru aceasta, am implementat si folosit sistematic aceeasi conventie de notare, astfel incat atunci cand este descrisa o functie, sa nu fie necesara enumerarea celor 10 posibiltati boolene.

• Conventia de notare pe care am ales-o a fost denumirea functiilor si clasificarea lor in tabel prin convertirea expresiei boolene intr-un numar zecimal, astfel:

1 0 0 0 1 1 0 1 0 1 (descrierea booleana a unui automat celular oarecare)

512 256 128 64 32 16 8 4 2 0 => id = 565

Program pentru vizualizarea automatelor celulare Program pentru vizualizarea automatelor celulare semitotalistice, conceput pentru a putea utiliza semitotalistice, conceput pentru a putea utiliza conventiile expuse anterior, scris in conventiile expuse anterior, scris in Visual C++Visual C++

Program pentru vizualizarea automatelor celulare Program pentru vizualizarea automatelor celulare semitotalistice, conceput pentru a putea utiliza semitotalistice, conceput pentru a putea utiliza conventiile expuse anterior, scris in conventiile expuse anterior, scris in Visual C++Visual C++

Program pentru vizualizarea automatelor celulare Program pentru vizualizarea automatelor celulare semitotalistice, conceput pentru a putea utiliza semitotalistice, conceput pentru a putea utiliza conventiile expuse anterior, scris in conventiile expuse anterior, scris in Visual C++Visual C++

Evaluarea fenomenelor emergente Evaluarea fenomenelor emergente pentru fiecare tip pentru fiecare tip de automatde automat prin urmarirea evolutiei in timp (pentru prin urmarirea evolutiei in timp (pentru

un numar mare de pasi)un numar mare de pasi)

Strat initial (t=0)

Stratri succesive (t=1,2,…n)

Evaluarea fenomenelor emergente Evaluarea fenomenelor emergente pentru fiecare tip pentru fiecare tip de automatde automat prin urmarirea evolutiei in timp (pentru prin urmarirea evolutiei in timp (pentru un numar mare de pasi) – Problemele intampinate:un numar mare de pasi) – Problemele intampinate:

1.Cantitatea mare de RAM necesara (217 Mb alocati numai pentru o matrice 151x151x10000)

2.Cantitatea mare de calculeEvaluarea gradului de organizare al fiecarui strat din cele 10000 trebuie facuta prin calcularea unui parametru numit conventional “haos”, calculat dupa o formula asemenatoare calcului entropiei, prezentata in materialul scris.

3.Calculatoarele folosite (insuficiente)• Athlon 1600Mhz – 256 Mb RAM

• Duron 750 Mhz – 256 Mb RAM

• Pentium III 500 Mhz – 256 Mb RAM

Rezolvarea acestor probleme printr-un al doilea Rezolvarea acestor probleme printr-un al doilea program optimizat creat in program optimizat creat in Visual C++ Visual C++

(chaos5finder2D.exe)(chaos5finder2D.exe)1. Folosirea a doar doua planuri interschimbabile si calcularea “entropiei” in planul activ. Aceasta permite reducerea memoriei RAM folosite pana la 335 Ko RAM

t=2k

t=2k+12. Cantitatea mare de calcule:

• programul permite calcul distribuit pe mai multe calculatoare (intr-o varianta simplificata)

• folosirea a doua thread-uri de executie:

• GUI-thread, care se ocupa de interactiunea cu utilizatorul, thread care merge in prioritate normala

•Worker-thread, care ruleaza in background, in prioritate idle, astfel fiind folosit la maxim timpul de lucru al PCului, fara a deranja pe cel care lucreaza la altceva.

Rezolvarea acestor probleme printr-un al doilea Rezolvarea acestor probleme printr-un al doilea program optimizat creat in program optimizat creat in Visual C++ Visual C++

(chaos5finder2D.exe)(chaos5finder2D.exe)

3. Programul permite configurarea printr-un fisier de configurare human-readable, de tip text

4. Pentru a nu se repeta calcularea zonelor din matrice deja calculate, pentru fiecare functie am realizat jurnalizarea actiunilor realizate de program, intr-un fisier de log-uri.

In cazul unui reset accidental al calculatorului, programul reia calculele de la locul ultimei jurnalizari, castigandu-se astfel timp prin evitarea actiunilor repetitive.

Rezultatele acestei faze a temei de dizertatieRezultatele acestei faze a temei de dizertatie

1. Aprox. 500 Mb fisiere de stari finale ale automatelor celulare semitotalistice cu vecinatate = 5, pentru toate functiile posibile (1024). Acestea au fost obtinute pt doua dimensiuni ale automatelor (21x21, respectiv 151x151).

2. Verificarea validitatii algoritmilor prin implementare independenta, pe platforme diferite de cei doi colaboratori (Adrian Iftime – Visual C++, respectiv Dan Darloman – Matlab). (Rezultatele coincid).

3. Crearea de doua seturi de unelte software pe platforme diferite, ceea ce permite verificarea rezultatelor.

4. Crearea a doua pagini de web pentru facilitarea colaborarii on-line, pe servere web cu latime de banda mare:

Adrian Iftime - http://biofizica.univermed-cdgm.ro/ai

Dan Darloman - http://med.pub.ro/dan/index.htm

exit

Evitarea conditiei de frontiera: transformarea Evitarea conditiei de frontiera: transformarea planului in torplanului in tor