Token Relabeling in a Tagged Token Data-flow Architecture

Abstract

dataflow principles of execution offer an efficient way of scheduling operations in large-scale distributed multicomputer systems. Large data structures are, however, a notorious difficulty and require special handling. The indirect structure access made through a structure memory (e.g., I-structures) has been adopted in some proposed dataflow machines. In this paper, we present a direct structure access approach (the token relabeling scheme) in which all array operations can be performed without the use of any intermediary structure memory. The graph constructs for both approaches are described. Four numerical algorithms including fast Fourier transform, bitonic sort, LU decomposition, and matrix multiplication have been implemented in both approaches. Token relabeling is directly applicable to arrays which are entirely consumed. We have also designed graph constructs which allow partial consumption. The effectiveness and efficiency of this parallel random access construct verify the feasibility and applicability of the token relabeling scheme. A deterministic simulation of Arvind's tagged token dataflow architecture has been undertaken to validate the graph designs and evaluate the performance of the graphs. It is shown bow the direct access graphs present better performance with regard to execution time, speedup, and resource utilization. © 1989 IEEE