Development,Analysis,and Verification of a Parallel Hybrid Dataflow Computer Architectural Framework and Associated Load-Balancing Strategies and Algorithms via Parallel Simulation

Abstract

This paper first presents the requirements for and the architectural framework of a type of real-time parallel dataflow computer architecture, specifically, a Hybrid Data/Command Driven Architecture (HDCA). Application of such an architecture is discussed. Goals, strategies, and algorithms for both static load-balancing and dynamic resource allocation on an HDCA system are presented. A parallel simulation of an HDCA system employing the presented static load-balancing and dynamic resource allocation algorithms is developed and presented. The parallel simulation was executed on a parallel computer system for increased fidelity. Analysis of simulation results for two example applications of the architecture allowed verification of design goals and correct performance of the HDCA architectural framework and associated static load-balancing and dynamic resource allocation strategies and algorithms.

Keywords

Dataflow computer architec tures design verification dynamic load- balancing hybrid dataflow computer architecture run-time resource alloca tion static load-balancing HDCA

Get full access to this article

View all access options for this article.

References

Arvind and Gostelow, K.P. 1982. "The U-interpreter." Computer vol. 15, no. 2, February, pp. 42-49.

Arvind and Kathail, V. 1981. "A multiple processor dataflow machine that supports generalized procedures." Eighth Annual Symposium on Computer Architecture, May, pp. 291-302.

Heath, J.R., et al. 1982. A Dynamic Pipeline Computer Architecture for Data-Driven Systems. Technical Report DASG60-79-C0052, University of Kentucky, Lexington, KY, February.

Gao, G.R. , Hum, H.H.J. , and Monti, J. 1991. "Towards an efficient hybrid dataflow architecture model." Proceedings of Parallel Architectures and Languages, Europe, PARLE'91 , Eindhoven, The Netherlands, June.

Ghosal, D. , Tripathi, S.K. , Bhuyan, L.N. , and Jiang, H. 1989. "Analysis of computation-communication issues in dynamic dataflow architectures." Proceedings of the Sixteenth Annual International Symposium on Computer Architecture , vol.17, June, pp. 325-333.

Gurd, J.R. , Kirkham, C.C. , and Watson, I. 1985. "The Manchester prototype dataflow computer." Communications of ACM vol. 28, no. 1, January, pp. 34-52.

Hunter, F. and Holzner, R. 1989. "Architecture, programming, and performance of the MIT data-flow architecture." Informatik-Spektrum vol. 12, no. 3, pp. 147-157.

Iannuci, R.A. 1988. "Towards a dataflow/Von Neumann hybrid architecture." Proceedings of the Fifteenth Annual International Symposium on Computer Architecture, Honolulu, Hawaii , June, pp.131-140.

Nikhil, R.S. , and Arvind. 1989 . "Can dataflow subsume Von Neumann computing." Proceedings of the Sixteenth Annual International Symposium on Computer Architecture , Israel, pp. 262-272.

10.

Uchida, K. and Temma, T. 1988. "A pipelined dataflow processor architecture based on a variable length token concept." Proceedings of the 1988 International Conference on Parallel Processing, University Park, PA, August, pp. 209-216.

11.

Watson, I. and Gurd, J. 1982. "A practical dataflow computer." Computer vol. 15, no. 2, February, pp. 51-57.

12.

Yura, T. , Shimada, T. , Hiraki, K. , Sekiguchi, S. , and Nishida, K. 1988. "The research and development of a dataflow supercomputer SIGMA-1." Bulletin of the Electrotechnical Laboratory vol. 52, no. 6, pp. 68-87.

13.

Rumbaugh, J. 1977. "A Dataflow multiprocessor." IEEE Trans. on Computers vol. C-26, no. 2, February, pp. 138-146.

14.

Dennis, J.B. 1980. "Data flow supercomputers." Computer vol. 13, no. 11, November, pp 48-56.

15.

Gajski, D.D. , Padua, D.A. , Kuck, D.J. , and Kuhn, R.H. 1982. "A second opinion on data flow—Machines and languages." Computer vol. 15, no. 2, February, pp. 58-69.

16.

Heath, J.R. , Hurt, A.D. , and Broomell , G.D. 1982. "A distributed computer architecture for real-time, data-driven applications." Proceedings of the Third IEEE International Conference on Distributed Computing Systems, October, pp. 630-638.

17.

Srini, V.P. 1986. "An architectural comparison of dataflow systems." Computer vol. 19, no. 3, March, pp. 68-88.

18.

Arvind and Culler, D.E. 1986. "Dataflow architectures." Annual Review of Computer Science no. 1, pp. 225-253.

19.

Sivanesa, B. 1995. Dynamic Resource Allocation in a Data-Driven Reconfigurable Parallel-Pipelined Computer Architecture. Master's Thesis, Department of Electrical Engineering, University of Kentucky, Lexington, KY, May.

20.

Walburg, W.D. 1991. Mapping Processes to Computing Elements for a Dataflow Computer, Master' s Thesis, Department of Electrical Engineering, University of Kentucky, Lexington, KY, August.

21.

Shen, C. , Ramamritham, K. , and Stankovic, J.A. 1993. "Resource reclaiming in multiprocessor real-time systems." IEEE Trans. on Parallel and Distributed Systems vol. 4, no. 4, April, pp. 382-397.

22.

Geist, A. , Beguelin, A. , Dongarra, J. , Jiang, W. , Manchek, R. , and Sunderam, V. 1994. Parallel Virtual Machine: A User's Guide and Tutorial for Networked Parallel Computing Cambridge, MA: The MIT Press.