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

research-article

Cache Memories for Data Flow Machines

Author:

Masaru TakesueAuthors Info & Claims

IEEE Transactions on Computers, Volume 41, Issue 6

Pages 677 - 687

https://doi.org/10.1109/12.144620

Published: 01 June 1992 Publication History

Abstract

Cache memories for dataflow machines are presented, and, in particular, four design principles for reducing the working set size of dataflow caches are introduced. They are (1) controlling the number of active state processes, (2) optimizing instruction addresses, (3) using a block-structured operand matching/waiting memory, and (4) making deterministic replacements. Based on these principles, instruction and operand caches are organized. A bypass control is also devised that enables cache block replacement to overlap with normal cache access. Miss ratio and performance of the caches are evaluated on a register transfer level simulator of a dataflow machine. The results show that the instruction cache of 1 k words and the operand cache of 2 k words achieve sufficiently low miss ratios. The bypass control compensates for the bandwidth of a narrow swapping channel to the extent that about eight dataflow processors with the caches can be integrated in an LSI chip.

References

[1]

{1} A. J. Smith, "Cache memories," Comput. Surveys, vol. 14, no. 3, pp. 473-530, Sept. 1982.

Digital Library

[2]

{2} S. A. Thoreson and A. E. Oldehoeft, "Instruction reference patterns in data flow programs," in Proc. ACM Annu. Conf., Oct. 1980, pp. 211-217.

[3]

{3} M. Tokoro, J. R. Jagannathan, and H. Sunahara, "On the working set concept for data-flow machines," in Proc. 10th Annu. Int. Symp. Comput. Architecture, July 1983, pp. 90-97.

[4]

{4} S. A. Thoreson and A. N. Long, "A feasibility study of a memory hierarchy in a data flow environment," in Proc. Int. Conf. Parallel Processing, Aug. 1985, pp. 356-360.

[5]

{5} J. R. Gurd, C. C. Kirkham, and I. Watson, "The Manchester prototype dataflow computer," Commun. ACM, vol. 28, no. 1, pp. 34-52, Jan. 1985.

Digital Library

[6]

{6} M. Amamiya, M. Takesue, R. Hasegawa, and H. Mikami, "Implementation and evaluation of a list-processing oriented data flow machine," in Proc. 13th Annu. Int. Symp. Comput. Architecture, June 1986, pp. 10-19.

Digital Library

[7]

{7} T. Shimada, K. Hiraki, K. Nishida, and S. Sekiguchi, "Evaluation of a prototype data flow processor of the SIGMA-1 for scientific computations," in Proc. 13th Annu. Int. Symp. Comput. Architecture, June 1986, pp. 226-234.

Digital Library

[8]

{8} Arvind and R. S. Nikhil, "Executing a program on the MIT tagged-token dataflow architecture," in Proc. Parallel Architectures and Languages in Europe (PARLE), Springer-Verlag LNCS no. 259, June 1987, pp. 1-29.

[9]

{9} M. Takesue, "A unified resource management and execution control mechanism for data flow machines," in Proc. 14th Annu. Int. Symp. Comput. Architecture, June 1987, pp. 90-97.

Digital Library

[10]

{10} M. Takesue, "A load control mechanism for data flow machines," Systems and Computers in Japan, Scripta Technica, Inc., vol. 19, no. 10, pp. 55-69, Oct. 1988. (This is a translated version of the paper appeared in Trans. IEICE Japan, vol. J70-D, no. 10, pp. 1878-1889, Oct. 1987.)

[11]

{11} M. Takesue, "Design and implementation of LSI chips for list-processing oriented data flow machine," in Proc. Data Flow Workshop, IEICE of Japan, May 1986, pp. 1-7 (in Japanese).

[12]

{12} R. Beuhrer and K. Ekanadham, "Incorporating data flow ideas into von Nuemann processors for parallel execution," IEEE Trans. Comput., vol. C-36, no. 12, pp. 1515-1522, Dec. 1987.

[13]

{13} M. Takesue, "A model for ultra-parallel processing of distributed structured data and a mixflow computer for it," in Proc. Symp. Comput. Architecture, IPS of Japan, May 1988, pp. 115-124 (in Japanese).

[14]

{14} R. A. Iannucci, "Toward a dataflow / Von Neumann hybrid architecture," in Proc. 15th Annu. Int. Symp. Comput. Architecture, May-June 1988, pp. 131-140.

[15]

{15} R. H. Halstead, Jr. and T. Fujita, "MASA: A multithreaded processor architecture for parallel symbolic computing," in Proc. 15th Annu. Int. Symp. Comput. Architecture, May-June 1988, pp. 443-451.

Digital Library

[16]

{16} B. J. Smith, "A pipelined, shared resource MIMD computer," in Proc. Int. Conf. Parallel Processing, Aug. 1978, pp. 6-8.

[17]

{17} D. A. Patterson and C. H. Sequin, "RISC I: A reduced instruction set VLSI computer," in Proc. 8th Annu. Int. Symp. Comput. Architecture, May 1981, pp. 443-457.

[18]

{18} P. Stenstrom, "A survey of cache coherence schemes for multiprocessors," IEEE Comput. Mag., vol. 23, no. 6, pp. 12-24, June 1990.

Digital Library

[19]

{19} M. Takesue, "Dataflow computer extension toward real-time processing," Real-Time Systems: The International Journal of Time-Critical Computing Systems, Kluwer Academic, vol. 1, no. 4, pp. 333-350, Apr. 1990.

[20]

{20} M. Takesue, "A distributed load-balancing system and its application to list processing oriented data flow machine DFM," Systems and Computers in Japan, Scripta Technica, Inc., vol. 19, no. 6, pp. 35-49, June 1988. (This is a translated version of the paper appeared in Trans. IEICE Japan, vol. J70-D, no. 6, pp. 1104-1115, June 1987.)

Cited By

Hurson AKavi KShirazi BLee B(1996)Cache Memories for Dataflow SystemsIEEE Parallel & Distributed Technology: Systems & Technology10.1109/88.5444364:4(50-64)Online publication date: 1-Dec-1996
https://dl.acm.org/doi/10.1109/88.544436
Roh LNajjar WMudge TEbcioğlu K(1995)Design of storage hierarchy in multithreaded architecturesProceedings of the 28th annual international symposium on Microarchitecture10.5555/225160.225203(271-278)Online publication date: 1-Dec-1995
https://dl.acm.org/doi/10.5555/225160.225203
Kavi KHurson APatadia PAbraham EShanmugam P(1995)Design of cache memories for multi-threaded dataflow architectureACM SIGARCH Computer Architecture News10.1145/225830.22443623:2(253-264)Online publication date: 1-May-1995
https://dl.acm.org/doi/10.1145/225830.224436
Show More Cited By

Index Terms

Cache Memories for Data Flow Machines

Recommendations

Simplicity Versus Accuracy in a Model of Cache Coherency Overhead

The important factors building a model of coherency overhead for a single-bus, shared memory multiprocessor are analyzed. Three architectural features are examined: the size of the coherency block, the cache size, and the type of bus operation used to ...
Counter-Based Cache Replacement and Bypassing Algorithms

Recent studies have shown that in highly associative caches, the performance gap between the Least Recently Used (LRU) and the theoretical optimal replacement algorithms is large, motivating the design of alternative replacement algorithms to improve ...
A Model of Workloads and its Use in Miss-Rate Prediction for Fully Associative Caches

A mathematical model for the behavior of programs or workloads is presented and from it is extracted the miss ratio of a finite, fully associative cache (or other first-level memory) using least-recently-used replacement under those workloads. To obtain ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computers

IEEE Transactions on Computers Volume 41, Issue 6

June 1992

132 pages

ISSN:0018-9340

Editor:
Earl Swartzlander
Univ. of Texas at Austin

Issue’s Table of Contents

Copyright © Copyright © 1992 IEEE. All Rights Reserved.

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 June 1992

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hurson AKavi KShirazi BLee B(1996)Cache Memories for Dataflow SystemsIEEE Parallel & Distributed Technology: Systems & Technology10.1109/88.5444364:4(50-64)Online publication date: 1-Dec-1996
https://dl.acm.org/doi/10.1109/88.544436
Roh LNajjar WMudge TEbcioğlu K(1995)Design of storage hierarchy in multithreaded architecturesProceedings of the 28th annual international symposium on Microarchitecture10.5555/225160.225203(271-278)Online publication date: 1-Dec-1995
https://dl.acm.org/doi/10.5555/225160.225203
Kavi KHurson APatadia PAbraham EShanmugam P(1995)Design of cache memories for multi-threaded dataflow architectureACM SIGARCH Computer Architecture News10.1145/225830.22443623:2(253-264)Online publication date: 1-May-1995
https://dl.acm.org/doi/10.1145/225830.224436
Kavi KHurson APatadia PAbraham EShanmugam PPatterson D(1995)Design of cache memories for multi-threaded dataflow architectureProceedings of the 22nd annual international symposium on Computer architecture10.1145/223982.224436(253-264)Online publication date: 1-Jul-1995
https://dl.acm.org/doi/10.1145/223982.224436

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents