No Access

Performance Evaluation of a Parallel Decoupled Data Driven Multiprocessor

MITCHELL THORNTON

Department of Computer Science and Engineering, Southern Methodist University, P. O. Box 750122, Dallas, Texas 75275, U. S. A.

Search for more papers by this author

https://doi.org/10.1142/S0129626403001458Cited by:0 (Source: Crossref)

Abstract

The Decoupled Data-Driven (D³) architecture has shown promising results from performance evaluations based upon deterministic simulations. This paper provides performance evaluations of the D³ architecture through the formulation and analysis of a stochastic model. The D³ architecture is a hybrid control/dataflow approach that takes advantage of inherent parallelism present in a program by dynamically scheduling program threads based on data availability and it also takes advantage of locality through the use of conventional processing elements that execute the program threads. The model is validated by comparing the deterministic and stochastic model responses. After model validation, various input parameters are varied such as the number of available processing elements and average threadlength, then the performance of the architecture is evaluated. The stochastic model is based upon a closed queueing network and utilizes the concepts of available parallelism and virtual queues in order to be reduced to a Markovian system. Experiments with varying computation engine threadlengths and communication latencies indicate a high degree of tolerance with respect to exploited parallelism.

Keywords:

References

Arvind and K. P. Gostelow, IEEE Computer 42 (1882). Google Scholar
J. D. Dennis, IEEE Computer, C 29(11), 48 (1980). Google Scholar
R. A. Ianucci , Toward a Dataflow/von Neumann hybrid architecture , Proceedings of the 15th Annual International Symposium on Computer Architecture . Google Scholar
P. Evripidou and J. L. Gaudiot , A Decoupled Graph/Computation Data-Driven Architecture with Variable-Resolution Actors , 1990 International Conference on Parallel Processing . Google Scholar
Evripidou, P., Thornton,M., and Gaudiot, J. L., A Decoupled Data-Driven Machine with Variable-length Thread Support, Tech. Rep. 93-CSE-29, SMU, 1993 . Google Scholar
B. Armstrong and R. Eigenmann, Performance Forecasting: A Methodology for Characterizing Large Computational Applications, Proceedings of the International Conference on Parallel Processing (1998) pp. 518–525. Google Scholar
D. J. Chen and K. M. Kavi, Journal of Information Science and Engineering, (Institute of Information Science) 7(2), 253 (1991). Web of Science, Google Scholar
K. M. Kavi , R. Giorgi and J. Arul , Comparing Execution Performance of Scheduled Dataflow with RISC Processors , Proceedings of the 13th International Symposium of Computer Architecture Parallel and Distributed Computing Conference . Google Scholar
D. Ghosal and L. N. Bhuyan, IEEE Trans., on Comp. 39(5), 615 (1990), DOI: 10.1109/12.53575. Crossref, Web of Science, Google Scholar
Houghton, R. C., Jr., Performance Evaluation of Task Graphs on Parallel Architectures Ph.D. Dissertation, Duke University, Department of Computer Science, 1991 . Google Scholar
E. C. Russell, SIMSCRIPT II.5 Programming language, 4th edn. (CACI Products Company, LaJolla, CA, 1987). Google Scholar