More Web Proxy on the site http://driver.im/

article

Free access

Analysis of computation-communication issues in dynamic dataflow architectures

Authors:

S. K. Tripathi,

H. JiangAuthors Info & Claims

ACM SIGARCH Computer Architecture News, Volume 17, Issue 3

Pages 325 - 333

https://doi.org/10.1145/74926.74962

Published: 01 April 1989 Publication History

Abstract

This paper presents analytical results of computation-communication issues in dynamic dataflow architectures. The study is based on a generalized architecture which encompasses all the features of the proposed dynamic dataflow architectures. Based on the idea of characterizing dataflow graphs by their average parallelism, a queueing network model of the architecture is developed. Since the queueing network violates properties required for product from solution, a few approximations have been used. These approximations yield a multi-chain closed queueing network in which the population of each chain is related to the average parallelism of the dataflow graph executed in the architecture. Based on the model, we are able to study the effect on the performance of the system due to factors such as scalability, coarse grain vs. fine grain parallelism, degree of decentralized scheduling of dataflow instructions, and locality.

References

[1]

Agrawal. S. C., Metamodelling : A Study of Approximation in Queueing Mod&. Computer System Series, The MIT Press. 1985.

Digital Library

[2]

Arvind and Kathail, V., "A multiple processor dataflow machine that supports generalized pmcedutes". Proc. 8th Ann. Symp. Comput. Arch., May 1981, pp. 291-302.

Digital Library

[3]

Arvind and Culler. D. E. "Dataflow Architectures". MITIu7sITM-294, Laboratory for Computer Science, MF, Feb. 1986.

[4]

Barahona. P. M. C. C. and Gurd. J. R., "Processor Allocation in a Multi-ring Dataflow Machine," Journal of Parallel and Distributed Computing, Vol. 3. 1986, pp. 305327.

Digital Library

[5]

Davis, A. L., and Keller, R. M. "Dataflow program graphs", tEEE Computer, vol. 15, no. 2, Feb. 1982. pp. 26-41.

[6]

Dennis, J. B., "Dataflow Supercomputers", IEEE Computer, vol. 13, no. 11. Nov. 1980. pp. 362-376.

Digital Library

[7]

Dias, D. M., and Jump, J. R., "Analysis and simulation of buffeted delta networks", IEEE Trans. on Comput., vol. C- 30. April 1981, pp. 273-282.

[8]

Duda, A. and Tadeusz. C., "Performance Evaluation of Fork and Join Synchronization Primitives.""" Acta Informatica, Vol. 24, 1987, pp. 525-553.

Digital Library

[9]

Eager, D. L. Zahojan, I. and Lazowska, E. D. "Speedup Versus Efficiency in Parallel Systems." IEEE Trans. on Comput. Vol. C-38, no. 3, March. 1989, pp. 408-423.

Digital Library

[10]

Gaudiot. J. L., and Ercegovac, M. D., "Performance Evaluation of a Simulated Data-Flow Computer with Low Resolution Actors* ", Journal of Parallel and Distributed Computing, Vo1.2. Feb. 1985, pp. 321-351.

Digital Library

[11]

Ghost D., and Bhuyan, L. N., "Analytical Modeling and Architectural Modification of a Dataflow Architecture", 14th Ann. lntl. Symp. Comput. Arch., June 1987.

Digital Library

[12]

Ghost& D., "A Unified Approach to Performance Evaluation of Dataflow and Multiprocessing Architectures," Ph.D Dissertation. The Center for Advanced Comnuter Studies, Univ. of Southwestern Louisiana, 1988. a

[13]

Gostelow, K. P., and Thomas R. E. "Performance of simulated dataflow computer". IEEE Trans. on Comput., vol. c- 29, no. 10, Oct. 1980. pp. 905-919.

Digital Library

[14]

Gun J. R. Watson, I., and Kirkham, C. C., "The Manchester prototype dataflow computer", Commun. Ass. Comput. Mach., vol. 28, Jan. 1985, pp. 34-52.

Digital Library

[15]

Guni. J. R., and Kirkham, C. C., "Dataflow: Achievements and Pmspects". lnformation Processing, North-Holland, 1986, pp. 61-68.

[16]

Heidelberger, P., and Trivedi, K. S., "Analytic Queueing Models for Programs with Internal Concurrency," lEEE Trans. on Comput., vol. C-32, no. 1, Jan. 1983. pp. 73-82.

[17]

Hwang. K. and Briggs. F. A., Parallel Processing and Computer Architecture. McGraw-Hill, New York, Apr. 1984.

[18]

Kruskal. C. P., and Snir. M., ""The performance of multistage interconnection networks for multiprocessors", IEEE Trans. on Comput., vol. c-32, No. 12, Dec. 1983, pp. 1091-1098.

Digital Library

[19]

Lazowska, E.D., Zahojan, J., Graham, S. G. and Sevcik, K. C., Quantitative System Performance : Computer System Analysis using Queueing Network Models. NJ : Ptentice- Hall Inc. 1984.

Digital Library

[20]

Nelson, R., Towsely. D., and Tantawi, A. N. "Performance Analysis of Parallel Processing Systems," IEEE Trans. on Software Engg., Vol. 14. No. 4, April 1988, pp. 532-540.

Digital Library

[21]

Patel. J. H. "Performance of Pmccssor Memory Interconnections for Multiprocessors," IEEE Trans. on Comput., vol. c-30. no. 10, Oct. 1981. pp. 771-780.

[22]

Reiser, M., "A Queueing Network Analysis of Computer Communication Networks with Window Flow Control," IEEE Trans. on Cotnmun., vol. COM-27. No. 8. Aug. 1979. pp. 1199-1209.

[23]

Sauer, C. H. and Chandy, K. M., Computer Systems Performance Modeling. Prentice-Hall, Inc. NJ, 1981.

[24]

Tteleaven, P. C., David, B. R., and Hopkins, P. R., "Data driven and demand driven computer architecture", Computing Surveys. vol. 14, pp. 93-143, Mar. 1982.

Digital Library

Cited By

Heath JSivanesa B(1997)Development, Analysis, and Verification of a Parallel Hybrid Dataflow Computer Architectural Framework and Associated Load-Balancing Strategies and Algorithms via Parallel SimulationSIMULATION10.1177/00375497970690010269:1(7-25)Online publication date: 1-Jul-1997
https://doi.org/10.1177/003754979706900102
Riefers CFeix R(1991)Performance Modeling of a Coarse Grain Dataflow MachineMessung, Modellierung und Bewertung von Rechensystemen10.1007/978-3-642-76934-4_14(196-210)Online publication date: 1991
https://doi.org/10.1007/978-3-642-76934-4_14

Index Terms

Analysis of computation-communication issues in dynamic dataflow architectures

Recommendations

Analysis of computation-communication issues in dynamic dataflow architectures
ISCA '89: Proceedings of the 16th annual international symposium on Computer architecture

This paper presents analytical results of computation-communication issues in dynamic dataflow architectures. The study is based on a generalized architecture which encompasses all the features of the proposed dynamic dataflow architectures. Based on ...
A unified approach to performance evaluation of dataflow and multiprocessing architectures
Dataflow architectures: flexible platforms for neural network simulation
NIPS'89: Proceedings of the 3rd International Conference on Neural Information Processing Systems

Dataflow architectures are general computation engines optimized for the execution of fine-grain parallel algorithms. Neural networks can be simulated on these systems with certain advantages. In this paper, we review dataflow architectures, examine ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGARCH Computer Architecture News

ACM SIGARCH Computer Architecture News Volume 17, Issue 3

Special Issue: Proceedings of the 16th annual international symposium on Computer Architecture

June 1989

400 pages

ISSN:0163-5964

DOI:10.1145/74926

Editor:
Jean-Claude Syre

Issue’s Table of Contents

ISCA '89: Proceedings of the 16th annual international symposium on Computer architecture
April 1989
426 pages
ISBN:0897913191
DOI:10.1145/74925
Chairman:
Jean-Claude Syre

Copyright © 1989 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1989

Published in SIGARCH Volume 17, Issue 3

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
466
Total Downloads

Downloads (Last 12 months)77
Downloads (Last 6 weeks)18

Reflects downloads up to 31 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Heath JSivanesa B(1997)Development, Analysis, and Verification of a Parallel Hybrid Dataflow Computer Architectural Framework and Associated Load-Balancing Strategies and Algorithms via Parallel SimulationSIMULATION10.1177/00375497970690010269:1(7-25)Online publication date: 1-Jul-1997
https://doi.org/10.1177/003754979706900102
Riefers CFeix R(1991)Performance Modeling of a Coarse Grain Dataflow MachineMessung, Modellierung und Bewertung von Rechensystemen10.1007/978-3-642-76934-4_14(196-210)Online publication date: 1991
https://doi.org/10.1007/978-3-642-76934-4_14

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Issue’s Table of Contents