Simula ion Modelling P ac ice and Theo y 118 (2022) 102519
A ailable online 5 Ma ch 2022
1569-190X/© 2022 The Au ho s. Published by Else ie B.V. This is an open access a icle unde he CC BY license
(h p://c ea i ecommons.o g/licenses/by/4.0/).
Con en s lis s a ailable a ScienceDi ec
Simula ion Modelling P ac ice and Theo y
jou nal homepage: www.else ie .com/loca e/simpa
E icien simula ion execu ion o cellula au oma a on GPU
Daniel Cagigas-Muñiz∗, Fe nando Diaz-del-Rio, Jose Luis Se illano-Ramos,
Jose-Luis Guisado-Liza
Depa men o Compu e A chi ec u e and Technology, Uni e sidad de Se illa, A enida Reina Me cedes s/n, 41012 Se illa, Spain
ARTICLE INFO
Keywo ds:
Cellula au oma a
Pa allel compu ing
Pe o mance op imiza ion
S encil compu a ion
G aphics P ocessing Uni s
ABSTRACT
G aphics P ocessing Uni s (GPUs) can be used as con enien ha dwa e accele a o s o speed up
Cellula Au oma a (CA) simula ions, which a e employed in many scien i ic a eas. Howe e ,
an impo an se o CA ha e pe o mance cons ain s due o GPU memo y bandwid h. Few
s udies ha e ully explo ed how CA implemen a ions can ake ad an age o mode n GPU
a chi ec u es, mainly in he case o in ensi e memo y usage. In his pape , we make a ho ough
s udy o echniques (s encil compu ing amewo k, look-up ables, and packe coding) o
e icien ly implemen CA on GPU, aking in o accoun i s de ailed a chi ec u e. Exhaus i e
expe imen s o alida e hese implemen a ion echniques o a numbe o signi ican memo y-
bounded CA a e pe o med. The CA analysed include he classical Game o Li e, a Fo es Fi e
model, a Cyclic cellula au oma on, and he Wi eWo ld CA. The expe imen al esul s show
ha implemen a ions using he p esen ed echniques can signi ican ly ou pe o m a baseline
s anda d GPU implemen a ion. The bes pe o mance esul s o all known implemen a ions o
memo y bounded CA we e ob ained. Mo eo e , some o he echniques, like look-up ables o
empo al blocking, a e indeed ela i ely easy o implemen o o apply when he ansi ion
ules a e simple. Finally, de ailed desc ip ions and discussions o he indica ed echniques
a e included, which may be use ul o p ac i ione s in e es ed in de eloping high pe o mance
simula ions in e icien languages based on CA on GPU.
1. In oduc ion
Cellula Au oma a (CA) a e ma hema ical models ha e ol e in disc e e ime s eps, composed o elemen s called ‘‘cells’’ ha
change hei s a e a each ime s ep acco ding o some ules, by aking in o accoun he s a e o he neighbou ing cells. CA a e
commonly used in complex and/o dynamic sys em modelling and simula ion, mainly in he ields o physics, biology, and compu e
science [1–4].
A sequen ial implemen a ion o a cellula au oma on using slow in e p e ed languages can be enough in ce ain si ua ions in
which he ou pu ime esponse is no c i ical, he CA model e olu ion ules a e simple, he CA da a a e ela i ely small, and/o
expe imen s do no need o be epea ed many imes. In hese cases, many p ac i ione s jus p o o ype o slow CPU pe o mance
nonpa allel p og amming languages like Py hon, Ma lab, o Oc a e.
Howe e , he e a e many eal-wo ld applica ions o CA simula ion models ha demand a high le el o compu a ional capabili y
because hei CA model is complica ed in e ms o e olu ion ules o da a usage, o eal- ime (o ime-cons ained) applica ions,
o o pa ame ic s udies in which he same expe imen mus be execu ed many imes unde di e en ini ial con igu a ions (in
∗Co esponding au ho .
E-mail add esses: [email p o ec ed] (D. Cagigas-Muñiz), [email p o ec ed] (F. Diaz-del-Rio), [email p o ec ed] (J.L. Se illano-Ramos), [email p o ec ed]
(J.-L. Guisado-Liza ).
h ps://doi.o g/10.1016/j.simpa .2022.102519
Recei ed 8 Janua y 2022; Recei ed in e ised o m 22 Feb ua y 2022; Accep ed 24 Feb ua y 2022
Simula ion Modelling P ac ice and Theo y 118 (2022) 102519
2
D. Cagigas-Muñiz e al.
which case i is c i ical o accele a e e e y indi idual expe imen ). The e o e, hese applica ions o CA equi e he usage o
pa allel compu ing echniques. Examples in ol e scien i ic p oblems as di e se as luid dynamics [5], cance g ow h [6], 3D me al
o ming [7], solidi ica ion in ma e ials science [8], o u ban land use simula ions [9], among many o he s. I is he e o e in e es ing
o analyse some p og amming undamen als on how CA implemen a ions on mode n compu ing pla o ms can be imp o ed when
pe o mance is impo an .
Compu e -based implemen a ions o CA a e inhe en ly pa allel because each cell can be p ocessed independen ly a each ime
s ep. Wi h he a i al in 2007 o p og amming languages o G aphical P ocessing Uni s (GPUs) such as Cuda and la e OpenCL,
he design and implemen a ion o CA expe ienced a new impe us. The in e nal a chi ec u e o GPUs has many mo e compu a ional
uni s (p ocesso s) han a CPU. This ea u e makes GPUs ideal ha dwa e accele a o s o implemen ing CA. The e is much oom
o pe o mance imp o emen , especially o memo y-bounded CA, such as he GoL. Memo y-bounded CA a e cellula au oma a
ha use mo e ime in memo y accesses han in compu ing cell s a es o he nex ime s ep. This means ha he GPU a i hme ic
compu a ional uni s a e no being e icien ly used.
A each ime s ep o CA, cell compu a ions can be pe o med in pa allel by se e al p ocesso s wi hou he need o communica ion
o synch oniza ion among hem. Se e al expe imen al wo ks can be ound in he scien i ic li e a u e abou he pe o mance bene i s
o using GPUs o e CPUs (see Sec ion 2).
The e is, howe e , one p oblem when coding pe o mance-sensi i e algo i hms using GPUs. GPU manu ac u es do no p o ide
access o he machine code. Fo example, in he case o NVIDIA Cuda p og amming language, only Pa allel Th ead Execu ion (PTX)
is p o ided. PTX is a low-le el pa allel h ead execu ion i ual machine and ins uc ion se a chi ec u e (ISA) [10]. Al hough he
syn ax o PTX is simila o ha o an assembly le el p og amming language, he e is no a one o one co espondence be ween a
PTX ins uc ion and a GPU machine code ins uc ion. Mo eo e , GPU’s ins uc ion se a chi ec u e (ISA) and/o ins uc ion encoding
changes om a chi ec u e o a chi ec u e. Ano he impo an ela ed p oblem a e compile s. In he case o NVIDIA and Cuda, he
compile is a ‘black box’ ha applies code op imiza ion. Ne e heless, i is no possible o de e mine whe he compile op imiza ions
a e always app op ia e.
The e o e, he e is no way o knowing exac ly how he high-le el code (Cuda o OpenCL) is ac ually execu ed on he GPU. Only
some gene al guidelines based on he GPU a chi ec u e a e indica ed by manu ac u e s. This makes expe imen a ion, p o iling, and
es ing necessa y o ensu e e ec i e code imp o emen . CA a e no an excep ion despi e i s appa en simplici y.
Ge ing he maximum pe o mance om GPU implemen a ions is no a i ial ask. Knowledge on low le el ha dwa e a chi ec u e
de ails is needed o ake ad an age o mode n GPU ull capabili ies. E en GPU p og amme s do no always squeeze he ull po en ial
o hei ha dwa e. Concu en and/o pa allel p og amming has ob ious ad an ages, bu i is always mo e complex o implemen .
Howe e , as men ioned be o e, high pe o mance is desi ed.
Fo a be e comp ehension o he main bo leneck in ol ed in GPU pe o mance, ou analysis is clea ly ex ensible o highe
dimensional p oblems. None heless, many code op imiza ion echniques desc ibed in his s udy can be ex ended o h ee-dimensional
CA mo e o less di ec ly. Th ee-dimensional CA a e ano he good example o massi e da a s uc u es ha need an e icien GPU
implemen a ion o a be e pe o mance.
The con ibu ions o his pape can be summa ized in h ee poin s:
1. An analysis o which GPU a chi ec u e aspec s in luence mos in he pe o mance o CA implemen a ions.
2. An analysis o di e en new algo i hms and/o echniques o imp o e baseline CA implemen a ions pe o mance on GPUs,
b eaking he cu en GPU pe o mance ba ie o some class o CA.
3. The implemen a ion and alida ion (wi h expe imen al esul s) o he new algo i hms and/o echniques p oposed. As a esul ,
a new highly e icien implemen a ion echnique is p oposed o memo y bandwid h bounded CA.
This a icle is o ganized as ollows. Rela ed wo ks a e discussed in Sec ion 2. A gene ic CA baseline implemen a ion on GPU
is desc ibed in Sec ion 3. Pe o mance issues ela ed o he implemen a ion o CA on GPU a chi ec u es a e analysed in Sec ion 4.
Sec ion 5p esen s new coding echniques o highe pe o mance, which a e based on p e ious analysis. The p oposed echniques
a e es ed using some CA models in Sec ion 6. The expe imen al esul s a e discussed in Sec ion 7. Finally, conclusions and u u e
wo k a e ou lined in Sec ion 8.
2. Rela ed wo ks
The e ha e been some s udies on he applica ion o GPUs o CA in he scien i ic li e a u e. Mos o hem a e ocused on
highligh ing he bene i s o compu ing CA on GPUs e sus CPUs. Examples can be ound in [11,12], and [13]. In hese s udies,
he e is li le discussion abou GPU op imiza ion algo i hms and/o echniques applicable o CA.
In addi ion, hey usually ocus on only one cellula au oma on: he Game o Li e (GoL). GoL was c ea ed by Conway [14] in
1970 and i is he mos e e enced and well-known cellula au oma on. Un o una ely, hese e e ences did no p o ide da a on mo e
(complex) CA models. GoL is conside ed a ’ oy model’ cellula au oma on ha is o en a om eal dynamic models. An excep ion
o his p ac ice can be ound, o example, in [15] whe e lase dynamics is modelled by using a cellula au oma on employing high
pe o mance mul ip ocesso s and GPUs.
Se e al algo i hms and issues ha in luence he CA pe o mance in GPUs we e s udied in [16] using again GoL cellula au oma on
as an example. Issues such as he in luence o sha ed memo y on GPUs and he h ead block size on Cuda we e analysed. In pa icula ,
his wo k did no ind any in luence o he block size on he algo i hms used; hus hese au ho s se always he block size o 32 ×32
h eads. They also es ed an algo i hm called ‘‘mul icell algo i hm’’, in which each GPU h ead p ocesses wo cells. Al hough i can
Simula ion Modelling P ac ice and Theo y 118 (2022) 102519
3
D. Cagigas-Muñiz e al.
Fig. 1. Pseudo code desc ip ion o a gene ic cellula au oma on p og am in GPU.
be bene icial in o he ypes o algo i hms o models, i did no imp o e he esul s o he baseline GoL implemen a ion. This s udy
p o ided se e al in e es ing esul s bu le signi ican oom o u he esea ch o imp o e he CA pe o mance on mode n GPUs.
No solu ions o imp o e he baseline GoL implemen a ion using GPUs we e p o ided.
P e iously, he e we e also some nonspeci ic s udies in [17]. Howe e , some o he esul s and conclusions p o ided we e o ally
opposed o [16]. This is due o he ac ha he au ho s in [17] wo ked wi h old NVIDIA g aphic ca ds (Fe mi a chi ec u e). These
g aphics ca ds we e he i s gene a ion o ull Cuda p og ammable GPUs ha did no ha e any kind o cache memo y in hei
in e nal a chi ec u e. As i will be seen in la e sec ions, his issue is absolu ely c i ical o unde s and he pe o mance o CA on
mode n GPUs.
3. Cellula au oma a model
The ypical bi-dimensional CA (Cellula Au oma a) wo k low on a GPU consis s o i s decla ing wo g ids (a ays) 𝐴and 𝐵in
memo y. The i s g id 𝐴 ep esen s he cu en s a e o he CA and he second g id 𝐵 he s a e a e a ime o compu a ion s ep.
No e ha using only one g id o he cu en and nex s a e would p oduce inco ec alues o GPU execu ion, since a h ead could
modi y a cell s a e be o e he o he h ead has ead his s a e. The con en o 𝐴(cu en s a e) is p e illed wi h he ini ial da a o
he CA on he hos compu e (usually a mul ip ocesso ). Then, i s con en is ans e ed o he GPU memo y. F om ha momen on,
bo h g ids (a ays) a e only accessed in he GPU memo y.
In each ime i e a ion o compu a ion s ep, he g id 𝐵(nex s a e) is calcula ed based on he con en o ma ix 𝐴(cu en s a e).
A he end o he compu a ion s ep, he oles o 𝐴and 𝐵a e exchanged o p epa e he nex ime i e a ion. In p og amming languages
like C/C++, his implies he use o poin e s (𝑝_𝑐𝑢𝑟𝑟𝑒𝑛𝑡_𝑠𝑡𝑎𝑡𝑒,𝑝_𝑛𝑒𝑥𝑡_𝑠𝑡𝑎𝑡𝑒). Cuda and OpenCL a e based on C/C++ because hey a e
p og amming languages ha ocus on code e iciency. Once he las i e a ion o compu a ion s ep has been comple ed, he inal
con en s o he g id con aining he cu en s a e o he CA mus be ans e ed om he GPU (de ice) memo y o he CPU (hos )
memo y. Fig. 1 shows a pseudo-algo i hm ha summa izes a ypical CA implemen a ion on a GPU.
The 𝑐𝑜𝑚𝑝𝑢𝑡𝑒_𝑠𝑡𝑒𝑝 unc ion om Fig. 1 implies he execu ion o a leas one ke nel on he GPU. A ke nel is no hing mo e han
a unc ion execu ed wi hin he GPU. One o he c i ical aspec s o ob aining good pe o mance is minimizing ans e s be ween
he GPU and he hos compu e as hey in ol e memo y la ency. This is why memo y ans e s be ween GPU and CPU a e usually
limi ed o he beginning and he end o he CA simula ion. Fo he same eason, he numbe o i e a ions o compu a ion s eps
pe o med should be ela i ely high o ake ad an age o he pa allel a chi ec u e o he GPU. The use o ela i ely small 𝐴and 𝐵
g ids o da a, he con inuous ans e o in o ma ion be ween he GPU and CPU, and/o a ew ime s eps can esul in an impo an
dec ease o pe o mance.
4. Analysis o CA pe o mance
As s a ed in he In oduc ion, he e is much oom o ime enhancemen in memo y-bounded CA. A p elimina y analysis was
done by us in [18], whe e we show ha he GoL implemen a ions a e a om aking ull ad an age o cu en a chi ec u es using
he oo line model [19]. This model is an excellen ool o de ec ing p omp ly po en ial bo lenecks and pe o mance issues. Going
o wa d, in his sec ion, he wo ac o s ha ha e a majo in luence on he CA pe o mance a e o be analysed in mo e dep h.
Simula ion Modelling P ac ice and Theo y 118 (2022) 102519
4
D. Cagigas-Muñiz e al.
Fig. 2. Compa ison o pe o mance o GPU memo y ypes (global, sha ed and ex u e memo ies) in GoL cellula au oma on and di e en g id sizes. A NVIDIA
GTX 1650 TI GPU (Tu ing a chi ec u e) was used.
4.1. GPU memo y model managemen
The objec i e in his subsec ion is o de e mine which GPU memo y managemen is mo e e ec i e o CA implemen a ion. GPUs
ha e se e al ypes o memo y and i is esponsibili y o he p og amme o de e mine i s managemen . This i s analysis will p o ide
a i s app oach o how CA should be coded.
To do his, se e al CUDA implemen a ions o GoL (Game o Li e) cellula au oma on we e es ed. The e a e only wo s a es
in GoL: dead o ali e. Ali e cells emain ali e i he e a e wo o h ee ali e neighbou cells. Dead cells become ali e wi h h ee
ali e neighbou cells. In any o he case, cells become dead o emain dead. Moo e neighbou hood (up, down, le , igh , and ou
diagonals) is aken in o accoun . The e a e some a ia ions o his cellula au oma on, including e en 3D e sions. The GoL is he
base o much mo e complex CA.
Cuda is he GPU p og amming language used in e e y expe imen and implemen a ion o his pape . I is he na i e p og amming
language o he NVIDIA manu ac u e and i is he p edominan one cu en ly. The concep s explained he e a e pe ec ly alid and
analogous o o he GPU languages such as OpenCL. F om he p og amme ’s poin o iew, cuda allows he use o h ee main ypes
o memo y: egis e s (local memo y), sha ed memo y, and global memo y.
The gene al s a egy o achie ing a good accele a ion/pe o mance in GPUs is o y o a oid access o global memo y as much
as possible. Copying da a om global memo y o sha ed memo y o using ex u es a e al e na i es o a oid many global memo y
accesses. Tex u es a e an addi ional ype o memo y p esen in NVIDIA GPUs ha a e speci ically gea ed owa ds image p ocessing.
Thus, h ee implemen a ions o he GoL based on [20] we e es ed: using global memo y, using sha ed memo y, and using ex u es.
To s udy he e ec o memo y, hese h ee memo y models ha e also been es ed o di e en CA (g id) sizes. The summa y o he
esul s ob ained a e shown in Fig. 2 o a o al o 1000 ime s eps.
The o e all conclusion ha can be d awn om hese i s esul s is ha al hough ex u es a e ideal o p ocessing 2-dimensional
images, hey a e no so ideal o implemen ing bi-dimensional CA. As o he implemen a ion o he GoL using global s. sha ed
memo y a he h ead block le el, heo y indica es ha using sha ed memo y can educe access o global memo y i da a sha ing
among h eads is ca e ully p og ammed. The global memo y da a bus ac s as a bo leneck in case all h eads wan o access i .
Howe e , i is in e es ing o ema k ha GoL expe imen al esul s in Fig. 2 do no con i m his s a emen . Resul s using only global
memo y a e sligh ly wo se han hose o he sha ed memo y case. This e ec is mo e no iceable o la ge (g id) CA.
A de ailed analysis o he CA model (see p e ious Sec ion 3) and he GPU a chi ec u e i sel can p o ide he key o explain his
beha iou . The cellula au oma on g id (da a ma ix) ha has he cu en s a e o he CA only needs o be ead om he global
memo y o each ime/compu a ion s ep. In addi ion, his da a s uc u e is no modi ied du ing he en i e compu a ion s ep. This
da a, like he au oma ic a iables de ined in a h ead block, a e s o ed in cache memo y and in egis e s wi hin a Mul ip ocesso
S eaming (SM). Mo ing da a ha is ead om global memo y o sha ed memo y in a block o h eads c ea es an unnecessa y
o e head because ha in o ma ion is al eady cached ei he in egis e s o in he 1 o 2 cache memo y le el.
W i e memo y access has a simila beha iou . The cell in o ma ion p ocessed by a block o h eads is w i en only once and in
a di e en a ea o he global memo y. The e o e, mo ing he in o ma ion om global memo y o sha ed memo y in each block o
h eads, and hen again o global memo y, does no educe he da a a ic o global memo y. I only gene a es a g ea e o e head
by ha ing o mo e da a unnecessa ily om one ype o memo y o ano he . Cache memo y is again a key componen because i
g oups w i es in blocks wi hou p og amme in e en ion. Sha ed memo y is use ul o gain pe o mance only when h eads in a
block ha e o sha e da a equen ly o e he same memo y a ea (i.e., ead/w i e se e al imes o he same da a in he same ime
s ep), be o e w i ing he esul s o global memo y. This is no he case o he GoL and many CA.
Simula ion Modelling P ac ice and Theo y 118 (2022) 102519
5
D. Cagigas-Muñiz e al.
Fig. 3. Accele a ion ob ained when changing he GoL cellula au oma on cell da a ype om ‘‘in ’’ o ‘‘cha ’’. Fi een independen execu ions ( es s) o each
g id size and da a ype we e pe o med. The mean ime in milliseconds was aken. An NVIDIA GTX 1650 TI g aphics ca d was used. Only he main GoL Cuda
ke nel was measu ed using he NVIDIA P o ile . The main Cuda ke nel un ime is be ween 74% (256 g id size) and 99% (16384 g id size) o he o al p og am
execu ion ime on he GPU.
As a i s conclusion, i can be s a ed ha , ha ing enough in e nal egis e s and a good cache memo y sys em (which is being
imp o ed wi h each new GPU gene a ion), CA implemen a ions end o ead and w i e each cell only once om he global memo y
in each ime/compu a ion s ep. This has also a posi i e aspec : p og amming using only global memo y is easie , and he e o e
Cuda code is cleane . The nega i e e ec o using sha ed memo y when p og amming CA in he absence o cache memo y was also
b ie ly commen ed in [16].
4.2. Cell size
Ano he ac o o s udy in ol es educing cell size. In he expe imen s o Sec ion 4.1, he da a ype ‘‘in ’’ was used o each cell.
Tha means 32 bi s pe cell in memo y. This allows o code up o 232 possible s a es pe cellula au oma on (g id) cell. In he case
o he GoL, only wo s a es pe cell a e possible (li e o dead). The e o e, an 8-bi da a ype ‘‘cha ’’ pe cell is enough o he GoL
cellula au oma on and many CA. This educes memo y usage by 4 imes wi h a consequen dec ease in memo y la ency. The e a e
s udies o GoL on mul ip ocesso s such as [21] in which cells a e encoded wi h a single bi . None heless, apa om he echnical
complexi y, his solu ion is no gene alizable o o he CA. Because Cuda (and OpenCL) is based on C/C++ p og amming language,
i is no possible o use da a ypes smalle han 8 by es (‘‘cha ’’ ype).
The Fig. 3 shows he accele a ion ac o ob ained by changing he cell ype om ‘‘in ’’ o ‘‘cha ’’ in he GoL cellula au oma on.
I can be clea ly seen ha :
1. The accele a ion is e y i egula o small g id sizes: 1% o a 256 ×256 g id size and 41% o a 512 ×512 g id size.
2. Then, he pe o mance imp o emen ends o be cons an o la ge g ids. This is de e mined by memo y bandwid h cons ain s
and GPU unc ional uni s.
The maximum accele a ion ob ained is low in p opo ion o he dec ease in memo y usage. GPUs a e op imized o wo k wi h
32-bi loa ing poin da a, which is he same size as he ‘‘in ’’ da a. Al hough he 8-bi ‘‘cha ’’ da a ype ep esen s a dec ease o
x4 da a in memo y, he maximum pe o mance ob ained is below 20% o la ge g id sizes (see Fig. 3). GPUs ha e unc ional uni s
designed o loa o double da a ypes ha in ol e 32 o 64 bi s espec i ely. The 8 bi cha da a ype is no well sui ed o he GPU
unc ional uni s, and can ha e nega i e e ec s in ela i ely small CA g ids as i can be obse ed in Fig. 3. Ne e heless, in he case
o la ge CA, codi ying each CA cell wi h a smalle da a size a iable educes he o e all da a size and he e o e he pe o mance
should be be e . This gi es a hin o eadd ess memo y accesses by using s anda d and wide a iables, as i will be p esen ed in
Sec ion 5.2.
5. Techniques o un ime-e icien coding o CA
Based on he p e ious wo ks men ioned in Sec ion 2, CA model desc ip ion o Sec ion 3, and he analysis esul s o Sec ion 4,
some echniques o p omo ing CA e icien pe o mance a e p oposed. Some o hese echniques ha e been used be o e, bu no
s udy has been ca ied ou o ex end hem o gene ic CA on GPUs.

Simula ion Modelling P ac ice and Theo y 118 (2022) 102519
6
D. Cagigas-Muñiz e al.
5.1. Look-up ables
An in e es ing pe o mance imp o emen consis s o ying o educe o elimina e selec i e s uc u es (𝑖𝑓 −𝑡ℎ𝑒𝑛 −𝑒𝑙𝑠𝑒). GPUs
execu e he same ins uc ions o all h eads (basic compu a ional uni s) in a wa p o block. This s yle o p og amming, called
single-ins uc ion mul iple- h ead (SIMT), wo ks well when all h eads ake he 𝑖𝑓 −𝑡ℎ𝑒𝑛 pa h a once. O he wise, se e al passes o
he block/wa p execu ion a e equi ed. One pass will be needed o hose h eads ha ollow he 𝑡ℎ𝑒𝑛 pa and ano he pass o
hose ha ollow he 𝑒𝑙𝑠𝑒 pa . These passes a e sequen ial o each o he , hus inc emen ing he execu ion ime [22]. In gene al, he
𝑖𝑓 −𝑡ℎ𝑒𝑛 −𝑒𝑙𝑠𝑒 o 𝑠𝑤𝑖𝑡𝑐ℎ −𝑐𝑎𝑠𝑒 selec i e s uc u es appea na u ally when coding CA ules and i is con enien o supp ess hem.
P og amme s usually do no ake his issue in o accoun when coding CA.
An al e na i e is o use wha i is going o be de ined in his s udy as ‘‘Look-Up Tables’’ (LUTs) [18]. These ables a e da a
s uc u es ha ha e as inpu he cu en s a e o a cell ( ow coo dina es) and he s a e and/o numbe o neighbou ing cells (column
coo dina es). They a e coded as bi-dimensional a ays. Fo ins ance, in he case o he GoL, his in ol es using a ma ix o 2 ows by
9 columns. The ows ep esen he wo possible s a es o a cell (li e o dead) and he columns ep esen he numbe o neighbou ing
li e cells. The con en o his ma ix indica es he s a e a which he cell should change in he nex ime/compu a ion s ep.
LUTs coding and managemen is e y dependen on he cellula au oma on. Ne e heless, in he case o CA wi h in ensi e
memo y usage, he ansi ion ules be ween s a es end o be ela i ely simple (i.e., need low compu a ional esou ces). LUTs can
be simpli ied in his se o CA and a e ela i e easy o code. This issue will be analysed in de ail wi h p ac ical CA in Sec ion 6.
5.2. Packe coding
A plausible solu ion o he limi a ion imposed by he GPU bandwid h is o access memo y only in 𝑓𝑙𝑜𝑎𝑡 o 𝑑𝑜𝑢𝑏𝑙𝑒 da a chunks.
The e o e, each h ead compu es mo e han one cell. In his way, he compu a ional load o each h ead is inc eased. As men ioned
in Sec ion 2, a somewha ela ed bu di e en app oach was analysed and named ‘‘mul icell algo i hm’’ in [16], in which each
h ead (cell) accesses o i s neighbou s sequen ially (see Fig. 4, middle). Howe e , memo y accesses we e done wi hou aking in o
accoun he GPU memo y da a bus a chi ec u e. As a consequence, hese au ho s ob ained sligh ly wo se esul s e en han he GoL
Baseline e sion.
Al hough he o iginal idea was co ec , because he a io o ead accesses pe cell is educed om 9/1 (3 ×3 o a cell) o 12/2
(4 ×3 o wo con iguous cells), he GPU a chi ec u e is s ill no eally used e icien ly. When a h ead p ocesses wo cells o a CA,
i p oduces wo di e en (non-coalesced) access eques s o he memo y (see Fig. 4, middle).
In con as , i is possible o ead/w i e a se o cells packed in jus one memo y access (see Fig. 4, bo om). The e o e, memo y
access eques s can be educed by x2, x4, o mo e.
To de elop his algo i hm, se e al cells mus be codi ied in a ‘‘supe cell’’ whose size is ha o he Func ional Uni bus wid h. In
he case o p og amming languages like C/C++ (and cuda), he maximum da a size a ailable is 64 bi s. The ideal scena io, howe e ,
would be o u ilize e en highe da a sizes.
Fig. 5 shows how o code 8 cells o he same ype in a supe cell o he case o GoL compu a ion. I can be obse ed ha , al hough
8 neighbou ing supe cells mus be ead o calcula e he new s a es o a pa icula supe cell, cen al cells ( ha is, all excep he i s
and he las one) only need o access cells om he uppe and lowe supe cells.
This echnique, which is going o be called ‘‘Packe Coding’’ in his pape , has been sca cely used and o e y speci ic cases.
To he au ho s’ knowledge, he unique deep s udy in he ield o CA is [21] and only mul ip ocesso s we e used. In [21] he GoL
was coded wi h 1 bi pe cell o an CPU implemen a ion. The pe o mance esul s we e ema kable; howe e , as men ioned in
Sec ion 4.2 his solu ion is no ex ensible o e e y CA. Expe imen s using Packe Coding o di e en CAs a e desc ibed in Sec ion 6.
5.3. Tempo al blocking
A hi d app oach o imp o ing CA pe o mance on GPUs is o ake ad an age o he s udies ha ha e been made in s encil
compu ing [23]. S encil compu a ion has been used in many applica ions and anges om simula ion o machine ision, machine
lea ning applica ions, o pa ial di e en ial equa ion (PDE) sol ing. This has led o a g ea deal o esea ch.
A s encil code consis s o upda ing he elemen s o an a ay (2D o 3D) based on a ixed pa e n. These a ay elemen s a e also
o en called cells. The simila i ies wi h CA a e ob ious and GPUs ha e also been used o achie e highe pe o mance [24,25].
Pa o he solu ion o he low CA pe o mance is o imp o e he u iliza ion o he GPU compu e uni s. In s encil compu ing, he
CA g id is usually di ided in o subplanes o he same size (named iles in s encil compu a ion) and each subplane o ile is p ocessed
by a h ead block. A each ime/compu a ion s ep, all iles o he g id a e ully p ocessed.
Going u he , ano he mo e complex echnique o s encil compu a ion is empo al blocking, which enhances he empo al euse
o da a, and hus educes he numbe o da a ans e s om/ o he global GPU memo y. I is based on a ime- iled execu ion, bu
he ope a ions om se e al consecu i e ime s eps a e combined o exploi da a euse in memo y [26].
Howe e , he cell alues ha a e in he edges (ghos o halo zones) depend on o he iles. In he case o GPUs, his means a
dependency be ween h ead blocks. This implies ha in empo al blocking he e mus be pe iodic synch oniza ion be ween h eads.
In Fig. 6 a basic scheme o how empo al blocking could be applied o a CA di ided in o 4 iles is shown. This echnique applied
o 3-dimensional s encils is called 3.5D blocking in [27].
Global memo y bandwid h educ ion is hus achie ed by combining se e al ime/compu a ion s eps o he same ile o be
execu ed consecu i ely. In e media e da a eside in egis e s, sha ed memo y, o cached memo y. The p oblem when using GPUs
Simula ion Modelling P ac ice and Theo y 118 (2022) 102519
7
D. Cagigas-Muñiz e al.
Fig. 4. Memo y access pa e ns compa ison o di e en CA codi ica ions when accessing he No h neighbou s o a wa p o cells (likewise o he es o
neighbou s). F om up o bo om: in a classical implemen a ion looking o he no h cell p o okes a coalesced access o a se o consecu i e by es; on he
con a y, he mul icell coding in oduces non-coalesced accessing (only one ou o wo elemen s in he case o a wo-cell pe h ead implemen a ion); inally,
he no el packe coding ep oduces again coalescing accesses bu o wide elemen sizes.
Fig. 5. Packe coding example: one supe cell codes 8 cells, and 8 supe cells a e needed o compu e a new supe cell in a cellula au oma on using Moo e
neighbou hood.
is ha , unlike CPUs, i s implemen a ion is mo e complica ed han spa ial blocking [28]. Fo example, o e e y GPU, i is
necessa y o calcula e and ensu e ha a h ead block has enough sha ed and local memo y o sa e da a o calcula ing a g oup
o ime/compu a ion s eps. Consequen ly, examples o s encil compu a ion in GPUs and empo al blocking a e a e.
To apply his echnique o CA (especially o he mos complex ones), au oma ic code gene a o s should be used. The wo
en i onmen s ha do his in GPUs e icien ly a e STENCILGEN [29] and AN5D [30]. In addi ion, he AN5D cu en ly has he bes
pe o mance esul s in s encil compu ing and GPUs and i is publicly a ailable o use.
AN5D imp o es he 3.5D blocking algo i hm ob aining he bes pe o mance in s encil compu a ion o bo h single and double
p ecision loa ing poin . Only a 𝑝𝑟𝑎𝑔𝑚𝑎 di ec i e is necessa y o indica e which loop mus be ansla ed in o Cuda code. In AN5D,
he C code ha is ansla ed in o Cuda code mus be composed only o h ee ‘ o ’ loops and a a iable assignmen . I is no
possible o include selec i e s uc u es (i -else) o p e ious ins uc ions ha ha e dependencies on he cell alues. AN5D mus
Simula ion Modelling P ac ice and Theo y 118 (2022) 102519
8
D. Cagigas-Muñiz e al.
Fig. 6. Basic example o o e lapped iling ( empo al blocking) in a GPU.
esol e dependencies a compiling ime. Fo all hese easons, look-up ables (see Sec ion 5.1) mus be used oo. The e o e, he C
sequen ial code mus be codi ied as shown below, so ha AN5D can be compiled o cuda:
...
#p agma scop
o ( in = 0; < TIMESTEPS ; ++)
o ( in i = 1; i < SIZE −1; i ++)
o ( in j = 1; j < SIZE −1; j ++) {
g id [( +1)%2][ i ][ j ] =
lookup_ able [ g id [ %2][ i ][ j ]]
[ ( g id [ %2][i −1][ j ] +
g id [ %2][ i +1][ j ] +
Simula ion Modelling P ac ice and Theo y 118 (2022) 102519
9
D. Cagigas-Muñiz e al.
Table 1
Mean execu ion ime and s anda d de ia ion (le and igh alues be ween pa en hesis in each able cell) o 15 independen uns in milliseconds
o he Game o Li e (GOL) cellula au oma on o di e en GPU implemen a ions: baseline, baseline using a look-up able o code ules, empo al
blocking using AN5D amewo k (wi h de aul op ions), packe coding using 32 bi s pe cell (4 subcells o 8 bi s) and packe coding using 64
bi s pe cell (8 subcells o 8 bi s). Bes case o each algo i hm/ echnique and each g id size is p esen ed in bold.
G id size Baseline Cuda
implemen a ion
Look-up able AN5D
(Tempo al blocking)
32 bi s packe coding
(4 subcells pe cell)
64 bi s packe coding
(8 subcells pe cell)
256 6.2 (0.0) 5.8 (0.0) 25.7 (0.1) 3.7 (0.0) 3.9 (0.0)
512 20.9 (0.4) 20.4 (0.3) 34.9 (0.2) 8.9 (0.0) 10.5 (0.2)
1024 88.5 (9.7) 87.4 (9.7) 82.3 (7.5) 39.6 (0.3) 38.6 (0.8)
2048 325.2 (11.6) 305.0 (0.9) 264.8 (1.8) 128.1 (8.0) 114.9 (9.3)
4096 1299.2 (2.6) 1234.4 (1.2) 1036.0 (8.8) 488.5 (1.5) 436.0 (1.4)
8192 5300.5 (16.6) 5052.2 (16.4) 4228.5 (18.2) 1977.6 (8.6) 1770.2 (10.8)
16384 21303.0 (60.8) 20324.4 (58.6) 17066.8 (71.8) 7960.2 (31.4) 6996.2 (27.2)
g id [ %2][ i ][ j −1] +
g id [ %2][ i ][ j +1] +
g id [ %2][i −1][j −1] +
g id [ %2][i −1][ j +1] +
g id [ %2][ i +1][j −1] +
g id [ %2][ i +1][ j +1]) ] ;
}
#p agma endscop
...
The a iable assignmen inside he h ee loops calcula es he new cell s a e based on neighbou cells. The main da a s uc u e
used should be only a 3 dimensional a ay. Fi s a ay dimension con ains he cu en and new g ids. The g ids swap hei oles in
each ime s ep. Second and hi d a ay dimensions con ain he ows and columns.
6. Expe imen al esul s
In his sec ion, he algo i hms and echniques p oposed be o e a e e i ied expe imen ally. Fou ep esen a i e CA ha ha e been
p oposed in he scien i ic bibliog aphy a e selec ed. Two CA ha e Moo e neighbou hood and wo ha e Von Neuman neighbou hood.
The numbe o s a es anges om 2 o 15. Rules a e di e se and he NVIDIA p o ile indica es memo y bandwid h o e head when
using he s anda d baseline implemen a ion e sion.
In he nex subsec ions, he esul s ob ained o each cellula au oma on a e desc ibed. Fo all expe imen s in his pape , a
NVIDIA GTX 1650 TI g aphics ca d was used in a compu e wi h an AMD Ryzen 5 3600 p ocesso . Linux-Min 20.04 ope a ing
sys em, NVCC 10.1, and GCC 9.3 compile s we e pa o he so wa e con igu a ion. Cuda p og amming language was used o code
CA. E e y es o his a icle was execu ed 15 imes and he a e age and s anda d de ia ion a e p esen ed.
Expe imen s (Cuda implemen a ions) use di e en CA g id sizes. F om 256 ×256 cells o 16384 ×16384 cells. Resul s a e
de ailed in ables ins ead o g aphics o app ecia e he pe o mance di e ences in small g id sizes. The baseline Cuda implemen a ion
esul is always placed a he i s able column. This is he e e ence implemen a ion when compa ing wi h he o he esul s. Only
he CA main Cuda ke nel is measu ed using he NVIDIA P o ile in each case. Ini ial p ocedu es like se ing up he o iginal g id
s a es, a e no aken in o accoun . The main CA ke nel compu es he ime s eps. I ep esen s be ween 72% (256 ×256 g id) and
99% (16384 ×16384 g id) o he o al execu ion ime o he baseline Cuda implemen a ion. Fo all expe imen s, 1024 ime s eps
we e used. The sou ce code o all expe imen s is a ailable a [31].
6.1. Game o li e
The Game o Li e (GoL) cellula au oma on was he i s p oposed cellula au oma on. This simple cellula au oma on is ideal
o make a i s es on he algo i hms and echniques p oposed in he sec ions be o e. In Table 1 he e is a summa y o he esul s
ob ained.
Resul s in Table 1 include GoL Cuda implemen a ion using only LUTs, AN5D amewo k, packe coding o 32 bi s pe cell, and
packe coding o 64 bi s pe cell. The a e age execu ion imes in he baseline and LUTs e sions a e e y simila . The AN5D e sion
has be e execu ion ime bu only o 1024 ×1024 g id size and abo e. In he case o 16384 ×16384 GoL g id ( he bigges g id),
he e is a speed up o 25% when compa ing wi h GoL baseline execu ion ime. Packe coding implemen a ions p esen he bes
esul s: a speed-up abo e 300% is achie ed o he la ges CA. Howe e , he e is almos a 14% ime imp o emen when using he
64 bi packe coding algo i hm (8 subcells pe cell) ins ead o he 32 bi e sion (4 subcells pe cell). The e o e, he nex CA will
use his packe coding e sion.
A K uskal–Wallis es [32] was pe o med o de e mine whe he o no he e was a s a is ically signi ican di e ence be ween
he median un imes o he di e en echniques o algo i hms used. Each echnique o algo i hm was applied o 7 di e en g id
sizes ( om 256 o 16384) as shown in Table 1.
Simula ion Modelling P ac ice and Theo y 118 (2022) 102519
16
D. Cagigas-Muñiz e al.
Re e ences
[1] S.F. Judice, La ice gas cellula au oma a o luid simula ion, in: Encyclopedia o Compu e G aphics and Games, Sp inge In e na ional Publishing, Cham,
2018, pp. 1–8, h p://dx.doi.o g/10.1007/978-3-319-08234-9_184-1.
[2] B. A ca, T. Ghisu, G.A. T un io, GPU-accele a ed mul i-objec i e op imiza ion o uel ea men s o mi iga ing wild i e haza d, J. Compu . Sci. 11 (2015)
258–268, h p://dx.doi.o g/10.1016/j.jocs.2015.08.009.
[3] R. Lubas, J. Was, J. Po zycki, Cellula au oma a as he basis o e ec i e and ealis ic agen -based models o c owd beha io , J. Supe compu . 72 (6)
(2016) 2170–2196, h p://dx.doi.o g/10.1007/s11227-016-1718-7.
[4] J. K oc, F. Jiménez-Mo ales, J.L. Guisado, M.C. Lemos, J. Tkáč, Building e icien compu a ional cellula au oma a models o complex sys ems: backg ound,
applica ions, esul s, so wa e, and pa hologies, Ad . Complex Sys . 22 (05) (2019) 1950013.
[5] K.R. Tubbs, F.T.-C. Tsai, GPU accele a ed la ice Bol zmann model o shallow wa e low and mass anspo , In e na . J. Nume . Me hods Eng g. 86 (3)
(2011) 316–334, h p://dx.doi.o g/10.1002/nme.3066, URL h ps://onlinelib a y.wiley.com/doi/abs/10.1002/nme.3066.
[6] A.G. Salgue o, A.J. Tomeu-Ha dasmal, M.I. Capel, Dynamic load balancing s a egy o pa allel umo g ow h simula ions, J. In eg . Bioin o m. 16 (1)
(2019) 20180066, h p://dx.doi.o g/10.1515/jib-2018-0066.
[7] M. Si ko, K. Banas, L. Madej, Scaling scien i ic cellula au oma a mic os uc u e e olu ion model o s a ic ec ys alliza ion owa d p ac ical indus ial
calcula ions, Ma e ials 14 (2021) (2021) h p://dx.doi.o g/10.3390/ma14154082.
[8] B. Jelinek, M. Esh aghi, S. Felicelli, J.F. Pe e s, La ge-scale pa allel la ice Bol zmann-cellula au oma on model o wo-dimensional dend i ic g ow h,
Compu . Phys. Comm. 185 (3) (2014) 939–947, h p://dx.doi.o g/10.1016/j.cpc.2013.09.013.
[9] C. Xia, H. Wang, A. Zhang, W. Zhang, A high-pe o mance cellula au oma a model o u ban simula ion based on ec o iza ion and pa allel compu ing
echnology, In . J. Geog . In . Sci. 32 (2) (2018) 399–424, h p://dx.doi.o g/10.1080/13658816.2017.1390118.
[10] A. Ke , G. Diamos, S. Yalamanchili, A cha ac e iza ion and analysis o PTX ke nels, in: 2009 IEEE In e na ional Symposium on Wo kload Cha ac e iza ion,
IISWC, 2009, pp. 3–12, h p://dx.doi.o g/10.1109/IISWC.2009.5306801.
[11] M.J. Gibson, E.C. Keedwell, D.A. Sa ić, An in es iga ion o he e icien implemen a ion o cellula au oma a on mul i-co e CPU and GPU ha dwa e, J.
Pa allel Dis ib. Compu . 77 (2015) 11–25, h p://dx.doi.o g/10.1016/j.jpdc.2014.10.011.
[12] S. Rybacki, J. Himmelspach, A. Uh mache , CPU and GPU based simula ion o cellula au oma a - a pe o mance compa ison, in: P oceedings o he 1s
SIMUL, 2009, pp. 62–67.
[13] E. Millán, P. Ma ínez, G. Gil Cos a, M. Piccoli, A. P in is a, C. Bede ian, C. Ga cía Ga ino, E. B inga, in: A. De Gius i (Ed.), Pa allel implemen a ion o a
cellula au oma a in a hyb id CPU/GPU en i onmen , XVIII Cong eso A gen ino de Ciencias de la Compu ación, 2013, pp. 184–193.
[14] E.R. Be lekamp, J.H. Conway, R.K. Guy, Winning Ways o You Ma hema ical Plays, second ed., A K Pe e s/CRC P ess, New Yo k, USA, 2001.
[15] C. Daniel, F. Diaz-del Rio, M. López-To es, F. Jiménez-Mo ales, J.L. Guisado, De eloping e icien disc e e simula ions on mul ico e and GPU a chi ec u es,
Elec onics 9 (2020) 189, h p://dx.doi.o g/10.3390/elec onics9010189.
[16] E. Nicolas, N. Wolo ick, F. Piccoli, C. Ga cia Ga ino, E. B inga, Pe o mance analysis and compa ison o cellula au oma a GPU implemen a ions, Clus e
Compu . 20 (2017) (2017) h p://dx.doi.o g/10.1007/s10586-017-0850-3.
[17] W.-m.W. Hwu, GPU Compu ing Gems Jade Edi ion, i s ed., Mo gan Kau mann Publishe s Inc., San F ancisco, CA, USA, 2011.
[18] F. Diaz-del Rio, D. Cagigas-Muñiz, J.-L. Guisado-Liza , J.-L. Se illano-Ramos, E icien pa allel implemen a ion o cellula au oma a and s encil compu a ions
in cu en p ocesso s, in: P. Nicopoli idis, S. Mis a, L. Yang, B. Zeigle , Z. Ning (Eds.), Ad ances in Compu ing, In o ma ics, Ne wo king and Cybe secu i y
- a Book Hono ing P o . Mohammad S. Obaida ’s Signi ican Scien i ic Con ibu ions, Sp inge -Na u e, 2022, pp. 1–29.
[19] G. O enbeck, R. S einmann, V. Capa os, D.G. Spampina o, M. Püschel, Applying he oo line model, in: 2014 IEEE In e na ional Symposium on Pe o mance
Analysis o Sys ems and So wa e, ISPASS, 2014, pp. 76–85, h p://dx.doi.o g/10.1109/ISPASS.2014.6844463.
[20] A. Simpson, Oak idge leade ship compu ing acili y, URL h ps://gi hub.com/olc /game_o _li e_ u o ials/ ee/mas e /CUDA.
[21] G. Oxman, S. Weiss, Y. Be’e y, Compu a ional me hods o Conway’s game o li e cellula au oma on, J. Compu . Sci. 5 (2013) (2013) h p://dx.doi.o g/
10.1016/j.jocs.2013.07.005.
[22] D.B. Ki k, W.-m.W. Hwu, P og amming Massi ely Pa allel P ocesso s: A Hands-on App oach, Mo gan Kau mann Publishe s, Bu ling on, MA, 2010.
[23] P.S. Rawa , M. Vaidya, A. Sukuma an-Rajam, A. Roun e , L. Pouche , P. Sadayappan, On op imizing complex s encils on GPUs, in: 2019 IEEE In e na ional
Pa allel and Dis ibu ed P ocessing Symposium, IPDPS, 2019, pp. 641–652.
[24] A. Schä e , D. Fey, High pe o mance s encil code algo i hms o GPGPUs, P ocedia Compu . Sci. 4 (2011) 2027–2036, h p://dx.doi.o g/10.1016/j.p ocs.
2011.04.221.
[25] J. Holewinski, L.-N. Pouche , P. Sadayappan, High-pe o mance code gene a ion o s encil compu a ions on GPU a chi ec u es, in: P oceedings o he 26 h
ACM In e na ional Con e ence on Supe compu ing, New Yo k, NY, USA, 2012, pp. 311–320, h p://dx.doi.o g/10.1145/2304576.2304619.
[26] P. Rawa , Op imiza ion o S encil Compu a ions on GPUs (Elec onic Thesis O Disse a ion), Ohio S a e Uni e si y, 2018.
[27] A.D. Nguyen, N. Sa ish, J. Chhugani, C. Kim, P. Dubey, 3.5-D blocking op imiza ion o s encil compu a ions on mode n CPUs and GPUs, in: SC, IEEE,
2010, pp. 1–13.
[28] K. Hou, H. Wang, W.-c. Feng, Gpu-UniCache: Au oma ic code gene a ion o spa ial blocking o s encils on GPUs, in: P oceedings o he Compu ing F on ie s
Con e ence, in: CF’17, Associa ion o Compu ing Machine y, New Yo k, NY, USA, 2017, pp. 107–116, h p://dx.doi.o g/10.1145/3075564.3075583.
[29] P.S. Rawa , M. Vaidya, A. Sukuma an-Rajam, M. Ra ishanka , V. G o e , A. Roun e , L.-N. Pouche , P. Sadayappan, Domain-speci ic op imiza ion and
gene a ion o high-pe o mance GPU code o s encil compu a ions, P oc. IEEE 106 (11) (2018) 1902–1920.
[30] K. Ma sumu a, H. Zohou i, M. Wahib, T. Endo, S. Ma suoka, AN5D: au oma ed s encil amewo k o high-deg ee empo al blocking on GPUs, in:
In e na ional Symposium on Code Gene a ion and Op imiza ion, 2020, pp. 199–211, h p://dx.doi.o g/10.1145/3368826.3377904.
[31] D.C.-M. niz, Cellula au oma a so wa e eposi o y, URL h ps://gi hub.com/dcagigas/GPU-Cellula -Au oma a.
[32] E. Os e ago a, O. Os e ag, J. Ko áč, Me hodology and applica ion o he K uskal-Wallis es , Appl. Mech. Ma e . 611 (2014) 115–120.
[33] D. Rey, M. Neuhäuse , Wilcoxon-signed- ank es , in e na ional encyclopedia o s a is ical science, in: In e na ional Encyclopedia o S a is ical Science,
Sp inge Be lin Heidelbe g, Be lin, Heidelbe g, 2011, pp. 1658–1659, h p://dx.doi.o g/10.1007/978-3-642-04898-2_616.
[34] J.G. F ei e, C.C. DaCama a, Using cellula au oma a o simula e wild i e p opaga ion and o assis in i e managemen , Na . Haza ds Ea h Sys . Sci. 19
(1) (2019) 169–179, h p://dx.doi.o g/10.5194/nhess-19-169-2019, URL h ps://nhess.cope nicus.o g/a icles/19/169/2019/.
[35] Y. Zhao, D. Geng, Simula ion o o es i e occu ence and sp ead based on cellula au oma a model, in: ICAIIS 2021: 2021 2nd In e na ional Con e ence on
A i icial In elligence and In o ma ion Sys ems, Chongqing, China, May 28 - 30, 2021, ACM, 2021, pp. 304:1–304:6, h p://dx.doi.o g/10.1145/3469213.
3471332.
[36] L. Hugo, P. Hugo, P. Thomas, Au oCelle in C++, URL h ps://gi hub.com/hugo lo e /Celula Au oma on.
[37] D. G i ea h, Sel -o ganizing wo-dimensional cellula au oma a: 10 s ill ames, in: Designing Beau y: The A o Cellula Au oma a, Sp inge In e na ional
Publishing, Cham, 2016, pp. 1–12, h p://dx.doi.o g/10.1007/978-3-319-27270-2_1.
[38] K. Kwak, Y. Ba yshniko , E. Co man, Cyclic cellula au oma a: A ool o sel -o ganizing sleep scheduling in senso ne wo ks, in: P oceedings - 2008
In e na ional Con e ence on In o ma ion P ocessing in Senso Ne wo ks, IPSN 2008, 2008, pp. 535–536, h p://dx.doi.o g/10.1109/IPSN.2008.69.
[39] R. González-Ga cía, G. Cas anon, H.E. He nández Figue oa, 2D pho onic c ys al comple e band gap sea ch using a cyclic cellula au oma on e ina ion,
Pho on. Nanos uc .: Fundam. Appl. 12 (2014) (2014) h p://dx.doi.o g/10.1016/j.pho onics.2014.09.003.
[40] V. Gladkikh, A. Nigay, Wi ewo ld++: A cellula au oma on o simula ion o nonplana digi al elec onic ci cui s, Complex Sys ems 27 (2018) (2018).
[41] C. Luo, R. Suda, A pe o mance and ene gy consump ion analy ical model o GPU, in: 2011 IEEE Nin h In e na ional Con e ence on Dependable, Au onomic
and Secu e Compu ing, 2011, pp. 658–665, h p://dx.doi.o g/10.1109/DASC.2011.117.