Table of Contents

Foreword vii

Introduction ix

Processor Design

Design Principle of Massively Parallel Distributed-Memory Multiprocessor Architecture 1
M. Amamiya and T. Kawano

StarT the Next Generation: Integrating Global Caches and Dataflow Architecture 19
B.S. Ang, Arvind, and D. Chiou

Synchronization and Pipeline Design for a Multithreaded Massively Parallel Computer 55
S. Sakai

Superpipelined Dynamic Data-Driven VLSI Processors 75
H. Terada, M. Iwata, S. Miyata, and S. Komori

Language and Programming Issues

Stream Data Types for Signal Processing 87
J.B. Dennis

Multilateral Diagrammatical Specification Environment Based on Data-Driven Paradigm 103
M. Iwata and H. Terada

Coarse-Grain Dataflow Programming of Conventional Parallel Computers 113
R. Jagannathan

Distributed Data Structure in Thread-Based Programming for a Highly Parallel Dataflow Machine EM-4 131
M. Sato, Y. Kodama, S. Sakai, Y. Yamaguchi, and S. Sekiguchi

Programmability and Performance Issues of Multiprocessors on Hard Nonnumeric Problems 143
A. Sohn and J.-L. Gaudiot

Compiling

Exploiting Iteration-Level Parallelism in Dataflow Programs 167
L. Bic, J.M.A. Roy, and M. Nagel

Empirical Study of a Dataflow Language on the CM-5 187
D.E. Culler, S.C. Goldstein, K.E. Schauser, and T. von Eicken

Programming the ADAM Architecture with SISAL 211
S. Mitrovic

Can Dataflow Machines Be Programmed with an Imperative Language? 229
S.F. Wail and D. Abramson

Resource Management and Scheduling

The Token Flow Model 267
J. Buck and E.A. Lee

Distributed Task Management in SISAL 291
M. Haines and A.P.W. Bohm

Load Balancing and Resource Management in the ADAM Machine 307
O.C. Maquelin

Workload Management in Massively Parallel Computers: Some Dataflow Experiences 325
D.F. Snelling and J.R. Gurd

Studies on Optimal Task Granularity and Random Mapping 349
T. Sterling, J. Kuehn, M. Thistle, and T. Anastasio

The Effects of Resource Limitations on Program Parallelism 367
K.B. Theobald, G.R. Gao, and L.J. Hendren

Program Characteristics and Performance Studies

The Dataflow Parallelism of FFT 393
A.P.W. Bohm and R.E. Hiromoto

Locality in the Dataflow Paradigm 405
I. Gottlieb and L. Biran

Locality and Latency in Hybrid Dataflow 417
W.A. Najjar, W.M. Miller, and A.P.W. Bohm

Implementation of Manipulator Control Computation on Conventional and Dataflow Multiprocessor 435
S. Zeng and G.K. Egan

Biography 449

About the Author

Guang R. Gao is a computer scientist and a Professor of Electrical and Computer Engineering at the University of Delaware. Gao is a founder and Chief Scientist of ETI. Lubomir Bic is the author of Advanced Topics in Dataflow Computing and Multithreading, published by Wiley.