Address Generation of Dataflow Fine-grain Parallel Data-structures on a Distributed-memory Computer

Dataflow-based fine-grain parallel data-structures provide high-level abstraction to easily write programs with potentially high parallelism. In order to show the feasibility of a fine-grain dataflow paradigm, we are now implementing a non-strict dataflow language on off-the-shelf computers, including a distributedmemory parallel machine. The results of preliminary experiments indicate that the inefficiency related to fine-grain parallel arrays in the naive distributedmemory implementation is mainly caused by the address generation for distributed data. To reduce overhead, we introduce a two-level table addressing technique that can efficiently generate addresses. The results of performance evaluation indicate that this technique is useful to improve the performance at a practical level even on off-the-shelf computers. 1. Introduction Parallel programming often requires troublesome execution controls such as scheduling and synchronization of parallel activities. In a procedural-based ..