A method for assessing the benefits of fine-grain paral lelism in "real" programs is presented. The method is based on parallelism profiles and speedup curves de rived by executing dataflow graphs on an interpreter under progressively more realistic assumptions about processor resources and communication costs. Even using traditional algorithms, the programs exhibit ample parallelism when parallelism is exposed at all levels. The bias introduced by the language ld and the compiler is examined. A method of estimating speedup through analysis of the ideal parallelism profile is developed, avoiding repeated execution of programs. It is shown that fine-grain parallelism can be used to mask large, unpredictable memory latency and synchronization waits in architectures employing dataflow instruction execu tion mechanisms. Finally, the effects of grouping por tions of dataflow programs, and requiring that the oper ators in a group execute on a single processor, are explored.
Get full access to this article
View all access options for this article.
References
1.
Arvind, Culler, D. E., and Ekanadham, K.1988. The price of fine-grain asynchronous parallelism: an analysis of dataflow methods. Paper presented at CONPAR 88, Manchester, U.K., September 12-16.
2.
Arvind, Culler, D. E., Iannucci, R.A., Kathail, V., Pingali, K.K., and Thomas, R.E.1983. The tagged-token dataflow architecture. Technical Report FLA. Cambridge: MIT Laboratory for Computer Science (545 Technology Square, Cambridge, MA 02139).
3.
Arvind and Ekanadham, K.1988. Future scientific programming on parallel machines. In Proc. of the internal. conf. on supercomputing (LNCS 297), edited by T. S. Houstis, C. D. Papatheodorou , and C. Polychronopoulos.New York: Springer-Verlag, pp. 639-686.
4.
Arvind and Iannucci, R.A.1987. Two fundamental issues in multiprocessing. In Proc. of DFVLR—conf. 1987 on parallel processing in science and engineering (LNCS 295), edited by R. Dierstein, D. Müller-Wichards, and H.-M. Wacker. New York: Springer-Verlag , pp. 61-88.
5.
Arvind and Nikhil, R.S.1987. Executing a program on the MIT tagged-token dataflow architecture . In Proc. of the PARLE conf. (LNCS 259), edited by J. W. Bakker, A. J. Nijman , and P. C. Treleaven.New York: Springer-Verlag, pp. 1-29.
6.
Arvind, Nikhil, R.S., and Pingali, K.K.1987a. I-structures: data structures for parallel computing. In Proc. of the graph reduction workshop (LNCS 279), edited by J. H. Fasel and R. M. Keller.New York: Springer-Verlag, pp. 336-369.
7.
Arvind, Nikhil, R. S., and Pingali, K.K.1987b. Id Nouveau reference manual. Part II: Semantics . Cambridge: MIT Laboratory for Computer Science (545 Technology Square, Cambridge, MA 02139).
8.
Charlesworth, A.E.1981. An approach to scientific array processing: the architectural design of the AP-120B/FPS-164 family. Computer14(9):18-27.
9.
Crowley, W.P., Hendrickson, C.P., and Rudy, T.E.1978. The SIMPLE code. UCID 17715. Livermore, Calif.: Lawrence Livermore Laboratory.
10.
Culler, D.E.1988. Effective dataflow execution of scientific programs. Ph.D. thesis (expected), Massachusetts Institute of Technology, Dept. of Electrical Engineering and ComputerScience.
11.
Culler, D.E., and Arvind.1988 . Resource requirements of dataflow programs. In Proc. of the 15th annual internat. symp. on computer architecture. New York: IEEE/ ACM, pp. 141-150.
12.
Dennis, J.B.1974. First version of a data flow procedure language. In Proc. of programming symp. (LNCS 19), edited by G. Goos and J. Hartmanis.New York: Springer-Verlag, pp. 362-376. Revised May 1975: MAC TM61, MIT Laboratory for Computer Science (545 Technology Square, Cambridge, MA 02139).
13.
Fisher, J.A.1983. Very long instruction word architectures and the ELI-512. YALEU/DCS/ RR-253New Haven, Conn.: Yale University, Dept. of Computer Science.
14.
Gaudiot, J.L., and Ercegovac, M.D.1985. Performance evaluation of a simulated dataflow computer with low resolution actors. J. Parallel and Distributed Comput.2(4):207-212.
15.
Hiraki, K., Sekiguchi, S., and Shimada, T.1987. System architecture of a dataflow supercomputer. Technical Report. Electrotechnical Laboratory, Computer Systems Division (1-1-4 Umezono, Sakuramura, Niihari-gun, Ibaraki 305, Japan).
16.
Iannucci, R.A.1988. A dataflow/von Neumann hybrid architecture. Ph.D. thesis, Massachusetts Institute of Technology, Dept. of Electrical Engineering and ComputerScience.
17.
Jordan, H.F.1983. Performance measurement on HEP—a pipelined MIMD computer. In Proc. of the 10th annual internal. symp. on computer architecture. New York: North-Holland , pp. 207-212.
18.
Lamport, L.1974. The parallel execution of DO loops. Comm. ACM17(2):83-93.
19.
Maa, G.K.1987. Code-mapping policies for the TTDA. Master's thesis, Massachusetts Institute of Technology, Dept. of Electrical Engineering and ComputerScience.
20.
Nikhil, R.S.1987a. Id Nouveau reference manual. Part I: Syntax. Cambridge: MIT Laboratory for Computer Science, Computation Structures Group (545 Technology Square, Cambridge, MA 02139).
21.
Nikhil, R.S.1987b. Id World reference manual. Cambridge : MIT Laboratory for Computer Science, Computation Structures Group (545 Technology Square, Cambridge, MA 02139).
22.
Papadopoulos, G.M.1988. Implementation of a general purpose dataflow multiprocessor. Ph.D. thesis, Massachusetts Institute of Technology, Dept. of Electrical Engineering and ComputerScience.
23.
Russell, R.M.1978. The CRAY-1 computer system. Comm. ACM21(1):63-72.
24.
Sarkar, V., and Hennessy, J.1986. Partitioning parallel programs for macro-dataflow . In Proc. of the 1986 ACM conf. on Lisp and functional programming . New York: ACM, pp. 202-211.
25.
Traub, K.R.1986. A compiler for the MIT tagged-token dataflow architecture. LCS TR-370. Cambridge: MIT Laboratory for Computer Science (545 Technology Square, Cambridge, MA 02139).
