language: en

Empirical Study of a Dataflow Language on the CM-5

David E. Culler Seth Copen Goldstein Klaus Erik Schauser Thorsten von Eicken
Computer Science Division Department of Electrical Engineering and Computer Sciences College of Engineering University of California, Berkeley

Abstract: This paper presents empirical data on the behavior of large dataflow programs on a distributed memory multiprocessor. The programs, written in the dataflow language Id90, are compiled via a Threaded Abstract Machine (TAM) for the CM-5. TAM refines dataflow execution models by addressing critical constraints that modern parallel architectures place on the compilation of general-purpose parallel programming languages. It exposes synchronization, scheduling, and network access so that the compiler can optimize against the cost of these operations. The data presented in this paper evaluates the TAM approach in compiling dataflow languages on stock hardware. We present data on the instruction mix, speedup, scheduling behavior, and locality of large ID90 programs. It is shown that the TAM scheduling hierarchy is able to tolerate long communication latencies, especially when some degree of I-structure locality is present. We investigate how frame allocation strategies, k-bounded loops, and I-structure caching and distribution together affect the overall efficiency. Finally we document some scheduling anomalies.

1 Introduction