Token relabeling in a tagged token data-flow architecture

A direct structure access approach called token relabeling scheme is presented 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 are implemented in both approaches. Token relabeling is directly applicable to arrays which are entirely consumed. Graph constructs which allow partial consumption are also designed. The effectiveness and efficiency of this parallel random access construct verifies the feasibility and applicability of the token relabeling scheme. A deterministic simulation of Arvind and K.P. Gostelow´s tagged-token data-flow architecture (1982) is undertaken to validate the graph designs and evaluate the performance of the graphs. It is shown that the direct access graphs present better performance with regard to execution time, speedup, and resource utilization