On the Optimal Blocking Factor for Blocked, Non-Overlapped Schedules
Praveen K. Murthy, Lee, Edward A · 1994
This paper addresses the problem of determining the optimal blocking factor for blocked, non-overlapped multiprocessor schedules for signal processing programs expressed as synchronous dataflow (SDF) graphs. One approach to determining a multiprocessor schedule for an SDF graph is to determine a schedule for the-unfolded graph of (defined to be the precedence graph of over iterations), where , and repeat that schedule forever. This approach allows us to exploit some of the inter-iteration parallelism that is usually present in the SDF graph. A schedule for the-unfolded graph is called a schedule of blocking factor . It is of interest to determine the value of that will allow schedules of optimal throughput to be constructed. It will be shown that the critical path of the-unfolded graph becomes cyclic as is increased. It will be shown that it is possible to determine this cyclicity by analyzing the critical graph of a matrix that arises in the model that is used. The cyclicity of the cr...