Copyright © 2008 The Institute of Electronics, Information and Communication Engineers
Regular Section -- Papers -- Fundamentals of Software and Theory of Programs |
A Model of Computation for Bit-Level Concurrent Computing and Programming: APEC*
1 The authors are with the Department of Open Information Systems, Toyo University, Kawagoe-shi, 350–8585 Japan. E-mail: t_ajiro{at}bitprog.info; kensei{at}toyonet.toyo.ac.jp
A concurrent model of computation and a language based on the model for bit-level operation are useful for developing asynchronous and concurrent programs compositionally, which frequently use bit-level operations. Some examples are programs for video games, hardware emulation (including virtual machines), and signal processing. However, few models and languages are optimized and oriented to bit-level concurrent computation. We previously developed a visual programming language called A-BITS for bit-level concurrent programming. The language is based on a dataflow-like model that computes using processes that provide serial bit-level operations and FIFO buffers connected to them. It can express bit-level computation naturally and develop compositionally. We then devised a concurrent computation model called APEC (Asynchronous Program Elements Connection) for bit-level concurrent computation. This model enables precise and formal expression of the process of computation, and a notion of primitive program elements for controlling and operating can be expressed synthetically. Specifically, the model is based on a notion of uniform primitive processes, called primitives, that have three terminals and four ordered rules at most, as well as on bidirectional communication using vehicles called carriers. A new notion is that a carrier moving between two terminals can briefly express some kinds of computation such as synchronization and bidirectional communication. The model's properties make it most applicable to bit-level computation compositionally, since the uniform computation elements are enough to develop components that have practical functionality. Through future application of the model, our research may enable further research on a base model of fine-grain parallel computer architecture, since the model is suitable for expressing massive concurrency by a network of primitives.
Key Words: model of computation, visual programming, bidirectional communication,concurrent, bit-level
Manuscript received March 15, 2007. Manuscript revised August 7, 2007.
* This work was partially presented at "The IEEE Symposium on Visual Languages and Human-Centric Computing [VL/HCC '05]" in Dallas, Texas, USA, 20–24 September 2005 [2].
Reference
[1] T. Ajiro and K. Tsuchida, "A visual programming language A-BITS," IEICE Technical Report, SS2003-13, Sept. 2003. [2] T. Ajiro and K. Tsuchida, "A bit-level concurrent visual programming language (A-BITS) and a base computation model (APC) for its development," IEEE Symposium on Visual Languages & Human-Centric Computing, pp.269–271, Sept. 2005. [3] N.C. Shu, Visual Programming, International Thomson Publishing, ISBN 0-442-28014-9, 1988. [4] M. Burnett, "The visual language research bibliography," http://web.engr.oregonstate.edu/burnett/vpl.html [5] D.D. Hils, "Visual languages and computing survey: Data flow visual programming languages," J. Visual Languages and Computing, vol.3, no.1, pp.69–101, March 1992. [6] K. Kuse, M. Sassa, and I. Nakata, "Design and implementation of a stream programming language," IPSJ MAGAZINE, vol.31, no.5, pp.673–685, May 1990. [7] K. Kuse, M. Sassa, and I. Nakata, "On stream programming environment using diagram representations," IPSJ Journal, vol.27, no.12, pp.1249–1253, Dec. 1986. [8] T.J. Smedley, "A high-level visual language for the graphical description of digital circuits," 11th International IEEE Symposium on Visual Languages, pp.77–82, 1995. [9] D.L. Miller-Karlow and E.J. Golin, "vVHDL: A visual hardware description language," Proc. 1992 IEEE Workshop on Visual Languages, pp.133–139, 1992. [10] J.L. Peterson, "Petri nets," ACM Comput. Surv., vol.9, no.3, pp.223–252, Sept. 1977. [11] T. Murata, "Analysis and application of Petri nets," Kindai kagaku sya, ISBN 4-7649-0204-4, 1992. [12] J.A. Sharp, DATA FLOW COMPUTING, Ellis Horwood Limited, ISBN 0-470-20167-3, 1985. [13] R. Jagannathan, "Dataflow models," in Parallel and Distributed Computing Handbook, chapter 8, McGraw-Hill, ISBN 0-07-073020-2, 1996. [14] K.M. Kavi and B.P. Buckles, "A formal definition of data flow graph models," IEEE Trans. Comput., vol.C-35, no.11, pp.940–948, Nov. 1986. [15] G. Kahn, "The semantics of a simple language for parallel programming," Inf. Process., vol.74, pp.471–475, 1974. [16] E.A. Lee and T.M. Parks, "Dataflow process networks," Proc. IEEE, vol.83, no.5, pp.773–801, May 1995. [17] M. Geilen and T. Basten, "Reactive process networks," Proc. 4th ACM International Conference on Embedded Software, pp.137–146, 2004. [18] C. Hewitt, "Viewing control structures as patterns of passing messages," J. Artificial Intelligence, vol.8, no.3, pp.323–364, 1977. [19] J. Baeten, "A brief history of process algebra," Theor. Comput. Sci., vol.335, no.2–3, pp.131–146, May 2005. [20] R. Milner, Communicating and Mobile Systems: the Pi-calculus, Cambridge University Press, ISBN 0-521-65869-1, 1999. [21] C.A.R. Hoare, "Communicating sequential processes," Commun. ACM, vol.21, pp.666–677, 1978. [22] L. Cardelli and A.D. Gordon, "Mobile ambients," Theor. Comput. Sci., vol.240, no.1, pp.177–213, June 2000. [23] K. Compton and S. Hauck, "Reconfigurable computing: A survey of systems and software," ACM Comput. Surv., vol.34, no.2, pp.171–210, June 2002. [24] H. Ito, R. Konishi, H. Nakada, H. Tsuboi, Y. Okuyama, and A. Nagoya, "Dynamically reconfigurable logic LSI: PCA-2," IEICE Trans. Inf. & Syst., vol.E87-D, no.8, pp.2011–2020, Aug. 2004. [25] T. Sugawara, K. Ide, and T. Sato, "Dynamically reconfigurable processor implemented with IPFlex's DAPDNA technology," IEICE Trans. Inf. & Syst., vol.E87-D, no.8, pp.1997–2003, Aug. 2004. [26] B. Tan, R. Yoshimura, T. Matsuoka, and K. Taniguchi, "Dynamically programmable parallel processor (DPPP): A novel reconfigurable architecture with simple program interface," IEICE Trans. Inf. & Syst., vol.E84-D, no.11, pp.1521–1527, Nov. 2001. [27] N. Imlig, T. Shiozawa, R. Konishi, K. Oguri, K. Nagami, H. Ito, M. Inamori, and H. Nakada, "Programmable dataflow computing on PCA," IEICE Trans. Inf. & Syst., vol.E83-A, no.12, pp.2409–2416, Dec. 2000. [28] J. Teifel and R. Manohar, "Asynchronous dataflow FPGA architecture," IEEE Trans. Comput., vol.53, no.11, pp.1376–1392, Nov. 2004.
CiteULike 
Connotea 
Del.icio.us What's this?
This Article 
Abstract
Full Text (PDF)
Alert me when this article is cited
Alert me if a correction is posted
Services
Email this article to a friend
Similar articles in this journal
Alert me to new issues of the journal
Add to My Personal Archive
Download to citation manager
Request Permissions
Google Scholar
Articles by AJIRO, T.
Articles by TSUCHIDA, K.
Search for Related Content
Social Bookmarking
What's this?