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
 |
Abstract |
|---|
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].