Patent ID: 6918111

Claim:
In a scheduler having at least one target processor, a method for ordering instructions in a code file having a plurality of instructions, the method comprising: (a) determining dependencies between instructions in said plurality of instructions; (b) creating a directed acyclic graph showing said dependencies in said plurality of instructions, where said directed acyclic graph's nodes each correspond to an instruction from said plurality of instructions; (c) identifying one or more queues, including a first queue; (d) traversing said directed acyclic graph in a dependency-preserving manner; (e) creating a ready set of nodes comprising nodes in said directed acyclic graph having corresponding instructions in a ready state; (f) finishing if there are no nodes having corresponding instructions in a ready state; (g) identifying a threshold level in said first queue, said threshold corresponding to a maximum desirable fullness of said first queue; (h) if said first queue is less full than said threshold, choosing a node in said ready set that corresponds to an instruction that would increase the fullness of said queue, if any such node exists in said ready set; (i) if said first queue is at least as full as said threshold, choosing a node in said ready set that corresponds to an instruction that would decrease the fullness of said queue, if any such node exists in said ready set; (j) if no node is chosen in (h) or (i), heuristically choosing a node in said ready set; (k) removing said chosen node from said directed acyclic graph; (l) modifying said first queue in accordance with said chosen node and its corresponding instruction; (m) modifying the order of instructions in said code file in accordance with said chosen node and its corresponding instruction; and (n) continuing processing at (d).