Implementation of recursive shift-invariant flow graphs in parallel/pipelined processing environments
Chun Pyo Hong · 1992
The objective of the research reported in this thesis is to develop a set of techniques to automatically find rate optimal or near rate optimal implementations in parallel/pipelined processing environments for DSP algorithms that are represented by recursive shift-invariant flow graphs. The parallel/pipelined processing environments are synchronous parallel processing systems that consist of one or more processors where each processor could be internally pipelined. The shift-invariant flow graph is a graphical representation which describes the computational structures of broad class of DSP algorithms at fine-grain level. Since the node execution times in defining flow graphs are deterministic, this research addresses compile time scheduling. The research in this thesis can be divided into three areas. First, an instruction scheduling methodology for a single pipelined processor is presented. In such case, the problem to be addressed is the scheduling of a single instruction stream which controls all of the pipeline stages. The goal of an automatic scheduler in this context is to rearrange the order of instructions such that they are executed with minimum time and no pipeline faults. In other words, sequences of instructions are ordered to minimize the iteration period between successive iteration of defining flow graphs. Second, a new class of multiprocessor system, called Clock-Skewed Parallel Processing system, is proposed. This system provides an elegant solution to interprocessor communication problems multiprocessor system. The interprocessor communication strategy described in this system is a combination of a synchronous multiprocessor architecture, an associated interprocessor communication architecture, and a multiprocessor compiler which considers the interprocessor communication to be a scheduling constraint. This system not only can handle the interprocessor communications very efficiently but also can explicitly incorporate the interprocessor communication time delay into the parallel scheduling model. Third, an instruction scheduling methodology for a multiple pipelined processing system is presented. In this system, since more than one pipelined processor is involved in parallel processing, all the processors must be interconnected in some manner. In such processing environments, the interprocessor communications joins the instruction scheduling as a major problem. This research presents a system scheduler which combines the instruction scheduling methodology for a single pipelined processor and the interprocessor communication strategy in the clock-skewed parallel processing system. This system has a simple interprocessor communication structure which can provide good performance and which results in scheduling constraints that can be reasonably integrated into the searching algorithms of an optimal compiler.