{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:35:12Z","timestamp":1750307712719,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Reconfigurable Technol. Syst."],"published-print":{"date-parts":[[2009,1]]},"abstract":"<jats:p>FPGA-based computation engines have been used as Cellular Automata accelerators in the scientific community for some time now. With the recent availability of more advanced FPGA logic it becomes necessary to better understand the mapping of Cellular Automata to these systems. There are many trade-offs to consider when mapping a Cellular Automata algorithm from an abstract system to the physical implementation using FPGA logic. The trade-offs include both the available FPGA resources and the Cellular Automata algorithm's execution time. The most important aspect is to fully understand the behavior of the specified CA algorithm in terms of its execution times which are either compute bound or I\/O bound. In this article, we present a methodology to categorize a specified CA algorithm as a compute bound or an I\/O bound. We take the methodology further by presenting rigorous analysis for each of the two cases identifying the various parameters that control the mapping process and are defined both by the Cellular Automata algorithm and the given FPGA hardware specifications. This methodology helps to predict the performance of running Cellular Automata algorithms on specific FPGA hardware and to determine optimal values for the various parameters that control the mapping process. The model is validated for both compute and I\/O bound two-dimensional Cellular Automata algorithms. We find that our model predictions are accurate within 7%.<\/jats:p>","DOI":"10.1145\/1462586.1462592","type":"journal-article","created":{"date-parts":[[2009,1,29]],"date-time":"2009-01-29T13:48:36Z","timestamp":1233236916000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Compute Bound and I\/O Bound Cellular Automata Simulations on FPGA Logic"],"prefix":"10.1145","volume":"1","author":[{"given":"S.","family":"Murtaza","sequence":"first","affiliation":[{"name":"University of Amsterdam"}]},{"given":"A. G.","family":"Hoekstra","sequence":"additional","affiliation":[{"name":"University of Amsterdam"}]},{"given":"P. M. A.","family":"Sloot","sequence":"additional","affiliation":[{"name":"University of Amsterdam"}]}],"member":"320","published-online":{"date-parts":[[2009,1]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-739X(99)00045-X"},{"volume-title":"Proceedings of the 10th Summer School on Computing Techniques in Physics: HPC in Science.","author":"Bubak M.","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","unstructured":"Cappuccino G. and Cocorullo G. 2001. Custom Reconfigurable Computing Machine for High Performance Cellular Automata Processing. TechOnLine Publication. Cappuccino G. and Cocorullo G. 2001. Custom Reconfigurable Computing Machine for High Performance Cellular Automata Processing. TechOnLine Publication ."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Chopard B. and Droz M. 1998. Cellular Automata Modeling of Physical Systems. Cambridge University Press. Chopard B. and Droz M. 1998. Cellular Automata Modeling of Physical Systems . Cambridge University Press.","DOI":"10.1017\/CBO9780511549755"},{"key":"e_1_2_1_5_1","unstructured":"Deutsch A. and Dormann S. 2004. Cellular Automaton Modeling of Biological Pattern Formation. Birkhauser. Deutsch A. and Dormann S. 2004. Cellular Automaton Modeling of Biological Pattern Formation . Birkhauser."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0010-4655(00)00088-6"},{"key":"e_1_2_1_7_1","unstructured":"Gutowitz H. A. 1990. Cellular Automata. MIT Press. Gutowitz H. A. 1990. Cellular Automata . MIT Press."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1666248"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/954542"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1058426.1058874"},{"volume-title":"Proceedings of the 17th International Conference on Field Programmable Logic and Applications. 74--78","author":"Murtaza S.","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Rivet J. P. and Boon J. P. 2001. Lattice Gas Hydrodynamics. Cambridge University Press. Rivet J. P. and Boon J. P. 2001. Lattice Gas Hydrodynamics . Cambridge University Press.","DOI":"10.1017\/CBO9780511524707"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Rothman D. H. and Zaleski S. 1997. Lattice-Gas Cellular Automata Simple Models of Complex Hydrodynamics. Cambridge University Press. Rothman D. H. and Zaleski S. 1997. Lattice-Gas Cellular Automata Simple Models of Complex Hydrodynamics . Cambridge University Press.","DOI":"10.1017\/CBO9780511524714"},{"key":"e_1_2_1_14_1","unstructured":"Shand D. Denning D. and Chamberlain R. 2005. Lattice gases - simple models of complex fluid dynamics. White Paper NT309-0001. www.Nallatatech.com. Shand D. Denning D. and Chamberlain R. 2005. Lattice gases - simple models of complex fluid dynamics. White Paper NT309-0001. www.Nallatatech.com."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00936946"},{"volume-title":"Proceedings of the 6th International Conference on Cellular Automata for Research and Industry (ACRI'04)","author":"Sloot P. M. A.","key":"e_1_2_1_16_1"},{"volume":"518","volume-title":"Lecture Notes in Computer Science","author":"Sloot P. M. A.","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","unstructured":"Sloot P. M. A. and Hoekstra A. G. 2007. Modeling dynamic systems with cellular automata. In Handbook of Dynamic System Modeling Ed. Paul A. Fishwick. CRC Press. Sloot P. M. A. and Hoekstra A. G. 2007. Modeling dynamic systems with cellular automata. In Handbook of Dynamic System Modeling Ed. Paul A. Fishwick. CRC Press."},{"key":"e_1_2_1_19_1","unstructured":"Sloot P. M. A. Kaandorp J. A. Hoekstra A. G. and Overeinder B. J. 2001. Distributed cellular automata: Large scale simulation of natural phenomena. In Solutions to Parallel and Distributed Computing Problems Lessons from Biological Sciences. 1--46. Sloot P. M. A. Kaandorp J. A. Hoekstra A. G. and Overeinder B. J. 2001. Distributed cellular automata: Large scale simulation of natural phenomena. In Solutions to Parallel and Distributed Computing Problems Lessons from Biological Sciences . 1--46."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0010-4655(01)00325-3"},{"key":"e_1_2_1_21_1","unstructured":"Succi S. 2001. The Lattice-Boltzmann Equation. Oxford University Press. Succi S. 2001. The Lattice-Boltzmann Equation . Oxford University Press."},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Toffoli T. and Margolus N. 1987. Cellular Automata Machines. MIT Press. Toffoli T. and Margolus N. 1987. Cellular Automata Machines . MIT Press.","DOI":"10.7551\/mitpress\/1763.001.0001"},{"key":"e_1_2_1_23_1","unstructured":"Wolfram S. 1994. Cellular Automata and Complexity. Perseus Book Group. Wolfram S. 1994. Cellular Automata and Complexity . Perseus Book Group."}],"container-title":["ACM Transactions on Reconfigurable Technology and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1462586.1462592","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1462586.1462592","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:30:15Z","timestamp":1750253415000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1462586.1462592"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1145\/1462586.1462592"],"URL":"https:\/\/doi.org\/10.1145\/1462586.1462592","relation":{},"ISSN":["1936-7406","1936-7414"],"issn-type":[{"type":"print","value":"1936-7406"},{"type":"electronic","value":"1936-7414"}],"subject":[],"published":{"date-parts":[[2009,1]]},"assertion":[{"value":"2008-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}