On the optimal blocking factor for blocked, non-overlapped multiprocessor schedules

This paper addresses the issue of determining the blocked non-overlapped multiprocessor schedule of optimal blocking factor for signal processing programs expressed as synchronous dataflow (SDF) graphs. The main result of this paper is a graph-theoretic characterization of the behavior of the critical path in the precedence graph of blocking factor J as J is increased. We show that the asymptotic behavior is cyclic in the following sense: there exist constants T and ρ such that the critical path in the precedence graph of blocking factor J+ρ has weight given by CP(J+ρ)=CP(J)+pλ ∀J>T (Eq 1) Where λ is the maximum cycle mean in the original graph, and ρ is an integer computable from the graph