Transformation of numerical algorithms for data-flow processing

The application of data-driven principles of execution to several numerically intensive computations is described. The fast Fourier transform, the bitonic sort method, the LU decomposition algorithm and matrix multiplication have been chosen since they are representative of a large class of algorithms and provide good benchmarks for the evaluation of the performance of data-flow systems. First, a high-level data-flow language (SISAL) is used to express the algorithms involved. Then the transformation between the high-level program and the low-level data-flow mechanisms is demonstrated, using general methods of translation applied to a number of high-level program constructs. Particular attention is given to the issue of structure-handling. The MIT tagged-token data-flow architecture has been simulated and provides the basis for a performance analysis of the translation methods.<>