This paper presents the design of a reconfigurable asynchronous computing element, called the pulsed quad-cell (PQ-cell), for constructing conformal computers. Conformal computers are systems with an exceptional ability to conform to the physical and computational needs of an application. PQ-cells, like cellular automata, are assembled into arrays, communicate with neighboring cells, and are collectively capable of general computation. They operate asynchronously to scale without the limitations of a global clock and to minimize power consumption. Cell operations are stimulated by pulses which travel on different wires to represent 0's and 1's. Cells are individually configured to perform logic, move and store information, and coordinate parallel activity. The PQ-cell design targets a 0.25？ m CMOS technology. Simulations show that a single cell consumes 15.6？pJ per operation when pulsed at 1.3？GHz. Examples of multicell structures include a 98？MHz ring oscillator and a 190？MHz pipeline. 1. Introduction In recent years there has been widespread interest in making things out of very large numbers of very small parts. These parts could be special molecular structures, microfabricated devices, or even living cells. The parts are so small and numerous that new approaches are sought for assembly, programming (defining local interactions to achieve global behavior), dealing with faults, and so on. There are many ideas about what such an ensemble might be useful for. It could be some form of programmable material, “smart matter", swarms of tiny robots, or simply a computer. Related research areas that have computing as a desired outcome include molecular computing [1, 2], biomolecular computing [3], bioinspired computing [4, 5], and amorphous computing [6]. For computer systems with many small parts, the programming models tend to be quite different from what is used in conventional computers. For example, in amorphous systems [7], information essentially diffuses through the system. This is similar to node-to-node “hopping" in wireless sensor networks. In both cases information moves in steps that are much shorter than the dimensions of the system. How to deal with such issues is of interest because it may enable the realization of systems that are superior to today’s programmable systems in important ways. In particular, it would be very useful to be able to perform brain-like tasks with systems that are much smaller and more efficient than what can be expected from today’s computing architectures. Our interest is in nonbiological cellular arrays in which the
References
[1]
J. Lyke, G. Donohoe, and S. Karna, “Reconfigurable cellular array architectures for molecular electronics,” Tech. Rep. AFRL-VS-TR-2001-1039, Air Force Research Laboratory, 2001.
[2]
S. Das, G. Rose, M. Ziegler, C. Picconatto, and J. Ellenbogen, “Architectures and simulations for nanoprocessor systems integrated on the molecular scale,” in Introducing Molecular Electronics, pp. 479–512, Springer, Berlin, 2005.
[3]
L. M. Adleman, “Molecular computation of solutions to combinatorial problems,” Science, vol. 266, no. 5187, pp. 1021–1024, 1994.
[4]
M. Sipper, “Emergence of cellular computing,” Computer, vol. 32, no. 7, pp. 18–26, 1999.
[5]
P.-A. Mudry, F. Vannel, G. Tempesti, and D. Mange, “CONFETTI: a reconfigurable hardware platform for prototyping cellular architectures,” in Proceedings of the 21st International Parallel and Distributed Processing Symposium (IPDPS '07), pp. 1–8, Long Beach, Calif, USA, March 2007.
[6]
H. Abelson, D. Allen, and D. Allen, “Amorphous computing,” Communications of the ACM, vol. 43, no. 5, pp. 74–82, 2000.
[7]
H. Abelson, J. Beal, and G. Sussman, “Amorphous computing,” Tech. Rep. MIT-CSAIL-TR-2007-030, Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, Mass, USA, June, 2007.
[8]
M. J. Pavicic, “Wallpaper computers: thin, flexible, extensible and R2R ready,” in Proceedings of the Flexible Electronics and Displays Conference, pp. 2–5, Phoenix, Ariz, USA, February 2009.
[9]
N. Margolus, “CAM-8: a computer architecture based on cellular automata,” in Pattern Formation and Lattice Gas Automata, pp. 167–187, American Mathematical Society, 1996.
[10]
T. Toffoli, “A pedestrian's introduction to spacetime crystallography,” IBM Journal of Research and Development, vol. 48, no. 1, pp. 13–29, 2004.
[11]
N. J. Macias and P. M. Athanas, “Application of self-configurability for autonomous, highly-localized self-regulation,” in Proceedings of the 2nd NASA/ESA Conference on Adaptive Hardware and Systems (AHS '07), pp. 397–404, Edinburgh, Scotland, July 2007.
[12]
F. Gruau, Y. Lhuillier, P. Reitz, and O. Temam, “BLOB computing,” in Proceedings of the Computing Frontiers Conference (CF '04), pp. 125–139, Ischia, Italy, April 2004.
[13]
L. Chua and T. Roska, Cellular Neural Networks and Visual Computing: Foundations and Applications, Cambridge University Press, New York, NY, USA, 2002.
[14]
M. Hoseini, C. You, and M. J. Pavicic, “A cellular automata ASIC for conformal computing,” in Proceedings of the International Conference on Engineering of Reconfigurable Systems and Algorithms (ERSA '08), pp. 305–306, Las Vegas, Nev, USA, July 2008.
[15]
S. Wolfram, A New Kind of Science, Wolfram Media, Pasadena, Calif, USA, 2002.
[16]
P. Sarkar, “A brief history of cellular automata,” ACM Computing Surveys, vol. 32, no. 1, pp. 80–107, 2000.
[17]
N. Ganguly, B. Sikdar, A. Deutech, G. Canright, and P. Chaudhuri, “A Survey on Cellular Automata,” February 2006, http://www.cs.unibo.it/bison/publications.
[18]
S. Adachi, F. Peper, and J. Lee, “Computation by asynchronously updating cellular automata,” Journal of Statistical Physics, vol. 114, no. 1-2, pp. 261–289, 2004.
[19]
F. Peper, J. Lee, S. Adachi, and S. Mashiko, “Laying out circuits on asynchronous cellular arrays: a step towards feasible nanocomputers?” Nanotechnology, vol. 14, no. 4, pp. 469–485, 2003.
[20]
R. Minnick, “A survey of microcellular tresearch,” Journal of the ACM, vol. 14, no. 2, pp. 203–241, 1967.
[21]
I. E. Sutherland, “Micropipelines,” Communications of the ACM, vol. 32, no. 6, pp. 720–738, 1989.
[22]
C. Wong, A. Martin, and P. Thomas, “An architecture for asynchronous FPGAs,” in Proceedings of the IEEE International Conference on Field-Programmable Technology, pp. 170–177, December 2003.
[23]
J. Teifel and R. Manohar, “An asynchronous dataflow FPGA architecture,” IEEE Transactions on Computers, vol. 53, no. 11, pp. 1376–1392, 2004.
[24]
A. Mahram, M. Najibi, and H. Pedram, “An asynchronous fpga logic cell implementation,” in Proceedings of the 17th ACM Great Lakes Symposium on VLSI, pp. 176–179, Stresa-Lago Maggiore, Italy, March 2007.
[25]
J. Teifel and R. Manohar, “Highly pipelined asynchronous FPGAs,” in Proceedings of the ACM/SIGDA 12th International Symposium on Field-Programmable Gate Arrays, pp. 133–142, Monterey, Calif, USA, February 2004.
