Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

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%.

REFERENCES

• 1: Bruce M. Boghosian, Lattice gases and cellular automata, Future Generation Computer Systems, v.16 n.2-3, p.171-185, Dec. 1999 [doi>10.1016/S0167-739X(99)00045-X]
• 2: Bubak, M., Moscinski, J., and Slota, R. 1994. Parallel program for 2D FHP Lattice gas simulation on clusters of workstations. In Proceedings of the 10th Summer School on Computing Techniques in Physics: HPC in Science.
• 3: Cappuccino, G. and Cocorullo, G. 2001. Custom Reconfigurable Computing Machine for High Performance Cellular Automata Processing. TechOnLine Publication.
• 4: Chopard, B. and Droz, M. 1998. Cellular Automata Modeling of Physical Systems. Cambridge University Press.
• 5: Deutsch, A. and Dormann, S. 2004. Cellular Automaton Modeling of Biological Pattern Formation. Birkhauser.
• 6: Dubbeldam, D., Hoekstra, A. G., and Sloot, P. M. A. 2000. Dynamic structure factor in single- and two-species thermal GBL lattice gas. Comput. Phys. Comm. 129, 13--20.
• 7: Gutowitz, H. A. 1990. Cellular Automata. MIT Press.
• 8: Hardy, P., Pommeau, Y., and de Pazzis, O. 1973. Time evolution of a two-dimensional model system. I. Invariant states and time correlation functions. J. Math. Phys. 1, 0, 1746--1759.
• 9: Andrew Ilachinski , Zane, Cellular Automata: A Discrete Universe, World Scientific Publishing Co., Inc., River Edge, NJ, 2001
• 10: Tomoyoshi Kobori , Tsutomu Maruyama , Tsutomu Hoshino, A Cellular Automata System with FPGA, Proceedings of the the 9th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.120-129, April 29-May 02, 2001 [doi>10.1109/FCCM.2001.2]
• 11: Murtaza, S., Hoekstra, A., and Sloot, P. 2007. Performance modeling of 2D Cellular Automata on FPGA. In Proceedings of the 17th International Conference on Field Programmable Logic and Applications. 74--78.
• 12: Rivet, J. P. and Boon, J. P. 2001. Lattice Gas Hydrodynamics. Cambridge University Press.
• 13: Rothman, D. H. and Zaleski, S. 1997. Lattice-Gas Cellular Automata, Simple Models of Complex Hydrodynamics. Cambridge University Press.
• 14: Shand, D., Denning, D., and Chamberlain, R. 2005. Lattice gases - simple models of complex fluid dynamics. White Paper, NT309-0001. www.Nallatatech.com.
• 15: Shaw, P., Cockshott, P., and Barrie, P. 1996. Implementation of lattice gases using FPGAs. J. VLSI Signal Process. 12, 1, 51--66.
• 16: Sloot, P. M. A., Chopard, B., and Hoekstra, A. G. 2004. Cellular automata. In Proceedings of the 6th International Conference on Cellular Automata for Research and Industry (ACRI'04). Springer Verlag.
• 17: Sloot, P. M. A. and Hoekstra, A. G. 2001. Cellular Automata as a Mesoscopic Approach to Model and Simulate Complex Systems. Lecture Notes in Computer Science, vol. 518. Springer Verlag.
• 18: 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.
• 19: 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.
• 20: Sloot, P. M. A., Overeinder, B. J., and Schoneveld, A. 2001. Self-organized criticality in simulated correlated systems. Comput. Phys. Comm. 142, 76--81.
• 21: Succi, S. 2001. The Lattice-Boltzmann Equation. Oxford University Press.
• 22: Toffoli, T. and Margolus, N. 1987. Cellular Automata Machines. MIT Press.
• 23: Wolfram, S. 1994. Cellular Automata and Complexity. Perseus Book Group.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Cellular arrays and automata

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Algorithms, Design, Performance

Keywords:
FPGA-based hardware accelerator, High-performance computing, cellular automata, lattice Boltzman simulations