Combined scheduling and mapping of digital signal processing algorithms on a VLIW processor

Abstract

A method for scheduling computation operations on a very long instruction word processor to achieve an optimal iteration period for a cyclic algorithm uses a flow graph to aid in scheduling instructions. In the flow graph, each computation operation appears as a separate node, and the edges between nodes represent data dependencies. The flow graph is transformed into machine-readable data for use in an integer linear program. The machine-readable data expresses equations and constraints associated with the optimal iteration period of the algorithm implemented on a processor having a plurality of types of functional units. The equations and constraints comprise an objective function to be minimized, a set of operation precedent constraints, job completion constraints, iteration period constraints and functional unit constraints. The nature of the equations and constraints are modified based upon processor architecture. The minimum iteration period for completion of the computation operations, and the scheduling of nodal operations, is determined by computing an optimal solution to the integer linear program as a solution of its corresponding linear constraints. The computation operations are scheduled according to the optimal solution provided by the integer linear program.

Dependencies are inferred from the claim text.