Optimal automatic periodic multiprocessor compiler for multi-bus networks

The theory and performance of a deterministic, optimal synchronous compiler for multiprocessor systems with a multibus interconnection network are presented. This compiler takes an algorithm described by a flow graph and produces realizations that meet traditional optimality criteria. These realizations are implemented on a multiprocessor system with the minimum number of buses possible. The compiler consists of three elements: flow graph analysis, scheduler, and processor assignment. The processor assignment module is discussed in detail. This module computes the bus communication bound from the schedule produced by the scheduler module. Based on this bound, the processor assignment module rearranges the schedule to use the minimum multibus interconnection network. The experimental study of the performance of this compiler emphasizes several adaptive and nonadaptive digital filters