Algorithm transformation techniques for concurrent processors

Progress in supercomputing technology has led to two major trends. First, many existing algorithms need to be redesigned for efficient concurrent implementation using supercomputers. Second, a continuous increase will be apparent in the number of application-specific VLSI integrated circuits, which can provide the performance of supercomputers using single chips or chipsets (at the expense of design time for algorithm and architecture development). Both of these approaches require considerable effort in the development of algorithms for specific applications. Four independent algorithm transformation methodologies-program unfolding, retiming, look-ahead algorithms, and index mapping transformations-are reviewed. These transformation techniques exploit the available parallelism in iterative data-flow programs and create additional parallelism if necessary