A topological sorting and loop cleansing algorithm for a constrained MIMD compiler of shift-invariant flow graphs

This paper describes the use of topological sorting and loop cleansing techniques in an implementation of a multiprocessor compiler for shift invariant flow graphs. The complier is capable of generating three classes of synchronous MIMD implementations: skewed single instruction multiple data (SSIMD), static-parallel skewed single instruction multiple data (Static-PSSIMD), and parallel skewed single instruction multiple data (PSSIMD). The effect of the topological sorting and loop cleansing algorithm is to dramatically reduce the compilation time required to find an optimal or a best SSIMD implementation, as well as maximally fast, perfectly efficient, and minimum delay PSSIMD and Static-PSSIMD implementations.