×

Efficient parallel simulations of asynchronous cellular arrays. (English) Zbl 0654.68057

An asynchronous cellular array (ACA) evolves in continuous time and all the state transitions at different cells occur asynchronously, at unpredictable random times. This paper provides answers to two basic questions related to ACAs: (1) how to specify the asynchrony accurately, and (2) how to carry out the parallel simulations for the specified asynchrony. Simple algorithms are presented which can be implemented on general purpose asynchronous parallel computers. The speed of such implementations depends on both the speed of individual processing elements (PEs) and the efficiency of the communication system. To assure the reproducibility of the simulated results, each PE needs to have its own reproducible pseudo-random sequence generator. The speed-up predictions are compared with the experimental results and they appear to be accurate. The problem of proving that efficiency tends to a positive limit when the number of PEs increases to infinity is one of the challenging mathematical problems generated by the described approach.
Reviewer: N.N.Necula

MSC:

68Q80 Cellular automata (computational aspects)
65C10 Random number generation in numerical analysis
68U20 Simulation (MSC2010)
65Y05 Parallel numerical computation
PDFBibTeX XMLCite