Gregory M. Papadopoulos
Abstract
Dataflow architectures tolerate long unpredictable communication delays and support generation and coordination of parallel activities directly in hardware, rather than assuming that program mapping will cause these issues to disappear. However, the proposed mechanisms are complex and introduce new mapping complications. This paper presents a greatly simplified approach to dataflow execution, called the explicit token store (ETS) architecture, and its current realization in Monsoon. The essence of dynamic dataflow execution is captured by a simple transition on state bits associated with storage local to a processor. Low-level storage management is performed by the compiler in assigning nodes to slots in an activation frame, rather than dynamically in hardware. The processor is simple, highly pipelined, and quite general. It may be viewed as a generalization of a fairly primitive von Neumann architecture. Although the addressing capability is restrictive, there is exactly one instruction executed for each action on the dataflow graph. Thus, the machine oriented ETS model provides new understanding of the merits and the real cost of direct execution of dataflow graphs.
- 1 Arvind and D. E. Culler. Managing Resources in a Parallel Machine. In PTOC. of IFIP TC-10 Working Conference on Fifth Generation Computer Architecture, Manchester, England. North-Holland Publishing Company, July 1985. Google Scholar
Digital Library
- 2 Arvind and D. E. Culler. Dataflow Architectures. In Annual Reviews in CompvterScience, volume 1, pages 225-253. Annual Reviews Inc., Palo Alto, CA, 1986. Reprinted in Dataflow and Reduction Architectures, S. S. Thakkar, editor, IEEE Computer Society Press, 1987. Google Scholar
- 3 Arvind, D. E. Culler, and K. Ekanadham. The Price of Asynchronous Parallelism: an Analysis of Dataflow Architectures. In Proc. of CONPAR 88, Univ. of Manchester, September 1988. British Computer Society - Parallel Processing Specialists. (also CSG Memo No. 278, MIT Lab for Computer Science). Google ScholarDigital Library
- 4 Arvind, D. E. Culler, R. A. Iannucci, V. Kathail, K. Pingali, and R. E. Thomas. The Tagged Token Dataflow Architecture. Technical Report FLA memo, MIT Lab for Computer Science, 545 Tech. Sq, Cambridge, MA, August 1983. R.evised October, 1984.Google Scholar
- 5 Arvind, D. E. Culler, and G. K. Maa. Assessing the Benefits of Fine-Grain Parallelism in Dataflow Programs. The Int 'l Journal ofSupercomputer.Applications, 2(3), November 1988.Google Scholar
- 6 Arvind, M. L. Dertouzos, R. S. Nikhil, and G. M. Papadopoulos. PROJECT DATAFLOW, a Parallel Computing System Based on the Monsoon Architecture and the Id Programming Language. Technical Report CSG Memo 285, MIT Lab for Computer Science, 545 Tech. Sq, Cambridge, MA, 1988.Google Scholar
- 7 Arvind and K. Ekanadham. Future Scientific Programming on Parallel Machines. The Journal of Parallel and Distributed Computing, 5(5):460-493, October 1988. Google ScholarDigital Library
- 8 Arvind, S. K. Heller, and R. S. Nikhil. Programming Generality and Parallel Computers. In Proc. of the Fourth Int'l Symp. on Biological and Artificial Intelligence Systems, pages 255-286, Trento, Italy, September 1988. ESCOM (Leider).Google Scholar
- 9 Arvind and R. A. Iannucci. Two Fundamental Issues in Multiprocessing. In Proc. of DFVLR - Conference 1987 on Parallel Processing in Science and Engineering, Bonn-Bad Godesberg, W. Germany, June 1987. Google ScholarDigital Library
- 10 R. G. Babb II, editor. Programming Parallel Processors. Addison-Wesley Pub. Co., Reading, Mass., 1988. Google ScholarDigital Library
- 11 L. Bit. A Process-Oriented Model for Efficient Execution of Dataflow Programs. In PTOC. ofthe 7th Intl Conference on Distribute!d Computing, Berlin, West Germany, September 1987.Google Scholar
- 12 G. Chaitin, M. Auslander, A., Chandra, J. Cocke, M. Hopkins, and P. Markstein. Register Allocation via Coloring. Computer Languages, 6:47-57, 1981.Google ScholarDigital Library
- 13 D. E. Culler. Managing Parallelism and Resources in Scientific Dataflow Programs. PhD Ohesis, MIT Dept. of Electrical Engineering and Computer Science, Cambridge, MA, June 1989. To appear as MIT Lab for Computer Science TR446.Google Scholar
- 14 .I. Darlington and M. Reeve. ALICE - A Multi- Processor Reduction Machine for Parallel Evaluation of Applicative Languages. In Proc. of the 1981 Conference on Functional Programming and Computer Architecture, pages 65-76, 1981. Google ScholarDigital Library
- 15 J. B. Dennis. Data Flow Supercomputers. IEEE Computer, pages 48-56, November 1980.Google ScholarDigital Library
- 16 J. B. Dennis and D. P. Misunas. A Preliminary Architecture for a Basic Dataflow Processor. In hoc. Of the 2nd Annual Symp. on Compute2 Ar- &lecture, page 126. IEEE, January 1975. Google ScholarDigital Library
- 17 J. B. Dennis, J. E. Stoy, and B. Guharoy. VIM: An Experimental Multi-User System Supporting Functional Programming. In Proc. of the 1984 lntl Workshop on High-Level Computer Architecture, pages 1.1-1.9, Los Angeles, CA, May 1984.Google Scholar
- 18 D.D. Gajski, D.A. Padua, David J. Kuck, and R.H. Kuhn. A Second Opinion of Data Flow Machines and Languages. IEEE Computer, 15(2):58- 69, February 1982.Google ScholarDigital Library
- 19 V. G. Grafe, J. E. Hoch, and Davidson G.S. Eps'88: Combining the Best Features of von Neumann and Dataflow Computing. Technical Report SAND88-3128, Sandia National Laboratories, January 1989.Google Scholar
- 20 J. Gurd, CC. Kirkham, and I. Watson. The Manchester Prototype Dataflow Computer. Communications of the Association for Computing Machinery, 28(1):34-52, January 1985. Google ScholarDigital Library
- 21 J. L. Gusatf on, G. R. Montry, and R. E. Benner. Development of Parallel Methods for a 1024 Processor Hypercube. SIAM Journal on Scientific and Statistical Computing, 9(4), July 1988.Google Scholar
- 22 S. K. Heller. Efficient lazy data-structures on a dataflow machine. Technical Report LCS/MIT/TR-438, MIT Lab for Computer Science, 545 Tech. Sq, Cambridge, MA, 1988. (PhD Thesis, Dept. of EECS, MIT).Google Scholar
- 23 R. A. Iannucci. A Dataflow/von Neumann Hybrid Architecture. Technical Report TR-418, MIT Lab for Computer Science, 545 Tech. Sq, Cambridge, MA, May 1988. (PhD Thesis, Dept. of EECS, MIT).Google Scholar
- 24 R. M. Keller and F. C. Lin. Simulated Performance of a Reduction-Based Multiprocessor. IEEE Computer, pages 70-82, July 1984.Google ScholarDigital Library
- 25 R. M. Keller, G. Lindstrom, and S. Patil. A Loosely-Coupled Applicative Multi-Processing System. In Proc. of the National Computer Conference, volume 48, pages 613-622, New York, NY, June 1979.Google Scholar
- 26 R. S. Nikhil and Arvind. Can Dataflow Sub sume von Neumann Computing? In Proc. of the 16th Annual Int'l Symp. on Computer Architecture, Jerusalem, Israel, May 1989. To appear. Google ScholarDigital Library
- 27 G. M. Papadopoulos. Implementation of a General Purpose Dataflow Multiprocessor. Technical Report TR432, MIT Lab for Computer Science, 545 Tech. Sq, Cambridge, MA, September 1988. (PhD Thesis, Dept. of EECS, MIT).Google Scholar
- 28 J. Rumbaugh. A Data Flow Multiprocessor. IEEE Transactions on Computers, C-26(2):138- 146, February 1977.Google ScholarDigital Library
- 29 T. Shimada, K. Hiraki, and K. Nishida. An Architecture of a Data Flow Machine and its Evaluation. In Proc. of CompCon 84, pages 486-490. IEEE, 1984.Google Scholar
- 30 K. R. Traub. A Compiler for the MIT Tagged- Token Dataflow Architecture. Technical Report TR-370, MIT Lab for Computer Science, 545 Tech. Sq, Cambridge, MA, August 1986. (MS Thesis, Dept. of EECS, MIT). Google ScholarDigital Library
- 31 W. Weber and A. Gupta. Exploring the Benefits of Multiple Hardware Contexts in a Multiprocessor Architecture: Preliminary Results. In Proc. of the 1989 Int'l Symp. on Computer Architecture, pages 273-280, Jerusalem, Israel, May 1989. Google ScholarDigital Library
- 32 K. Weng. An Abstract Implementation for a Generalized Data Flow Language. Technical Report MIT/LCS/TR-228, MIT Lab for Computer Science, 545 Tech. Sq, Cambridge, MA, 1979. (PhD Thesis, Dept. of EECS, MIT). Google ScholarDigital Library
Index Terms
- Monsoon: an explicit token-store architecture
Recommendations
Monsoon: an explicit token-store architecture
ISCA '90: Proceedings of the 17th annual international symposium on Computer ArchitectureDataflow architectures tolerate long unpredictable communication delays and support generation and coordination of parallel activities directly in hardware, rather than assuming that program mapping will cause these issues to disappear. However, the ...
An evaluation of speculative instruction execution on simultaneous multithreaded processors
Modern superscalar processors rely heavily on speculative execution for performance. For example, our measurements show that on a 6-issue superscalar, 93% of committed instructions for SPECINT95 are speculative. Without speculation, processor resources ...
Converting thread-level parallelism to instruction-level parallelism via simultaneous multithreading
To achieve high performance, contemporary computer systems rely on two forms of parallelism: instruction-level parallelism (ILP) and thread-level parallelism (TLP). Wide-issue super-scalar processors exploit ILP by executing multiple instructions from a ...
Comments