Method and apparatus for optimizing cost-based heuristic instruction scheduling
First Claim
1. In a computer system comprising a pipelined processor for executing instructions of programs in a parallel and overlapping manner, and a compiler for compiling and generating said instructions, wherein said compiler has a scheduler for scheduling said instructions for execution on said pipelined processor, and said scheduler schedules said instructions using N weighted cost based heuristics, a method for empirically selecting a set of N weights for said scheduler to weigh said N cost based heuristics, said method comprising the steps of:
- a) generating arbitrarily an initial trial set of N weights, initializing said scheduler with said arbitrarily generated initial trial set of N weights, generating a plurality of benchmark programs, compiling said benchmark programs using said compiler, accumulating scheduling costs determined by said scheduler for said benchmark programs, initializing a lowest accumulated scheduling cost of said benchmark programs to said accumulated scheduling cost, and selecting said initial trial set of N weights as the selected set of N weights for said scheduler;
b) generating sequentially a first plurality of additional trial sets of N weights in a first manner, one trial set of N weights at a time, each of said first plurality of additional trial sets of N weights being generated by systematically varying the immediately preceding trial set of N weights along an orthogonal dimension of a weight space formed by the N weights, one orthogonal dimension at a time, reinitializing said scheduler with each of said additional trial sets of N weights after each of their generations, regenerating said plurality of benchmark programs after each of said reinitializations, recompiling said regenerated benchmark programs using said compiler after each of said regenerations, reaccumulating scheduling costs determined by said scheduler for said benchmark programs during each of said recompilations, comparing each of said reaccumulated scheduling cost with said lowest accumulated scheduling cost to determine whether a new lowest accumulated scheduling cost is found after each of said reaccumulations, terminating said generation of additional trial sets of N weights in said first manner as soon as a new lowest accumulated scheduling cost is found, updating said lowest accumulated scheduling cost to equal the newly found lowest accumulated scheduling cost if a new lowest accumulated scheduling cost is found, and selecting the trial set of N weights that yields the new lowest accumulated scheduling cost over the previously selected set of N weights as the selected set of N weights for said scheduler if a new lowest accumulated scheduling cost is found; and
c) generating sequentially a second plurality of additional trial sets of N weights in a second manner, one additional trial set of N weights at a time, each of said additional trial sets of N weights being generated under said second manner by systematically varying the immediately preceding trial set of N weights along the last orthogonal dimension with the last systematic variation made under said first manner, reinitializing said scheduler with each of said additional trial sets of N weights after each of their generations, regenerating said plurality of benchmark programs after each of said reinitializations, recompiling said regenerated benchmark programs using said compiler after each of said regenerations, reaccumulating scheduling costs determined by said scheduler for said benchmark programs during each of said recompilations, comparing each of said reaccumulated scheduling cost with said lowest accumulated scheduling cost to determine whether a new lowest accumulated scheduling cost is found after each of said reaccumulations, terminating said generation of additional trial sets in said second manner as soon as no new lowest accumulated scheduling cost is found, updating said lowest accumulated scheduling cost to equal the last newly determined lowest accumulated scheduling cost if at least one newly determined lowest accumulated scheduling cost is found, and selecting the last trial set of N weights that yields the last new lowest accumulated scheduling cost over the previously selected set of N weights as the selected set of N weights for said scheduler if at least one newly determined lowest accumulated scheduling cost is found.
0 Assignments
0 Petitions
Accused Products
Abstract
A method and apparatus for optimizing cost-based heuristic instruction scheduling for a pipelined processor is disclosed which has particular application to compile time instruction scheduling after code generation. Instruction scheduling is optimized by determining the optimal weights to be used by an apparatus for cost based heuristic instruction scheduling for a particular pipelined processor. The optimal weights are determined based on the lowest of the lowest costs incurred by different collections of interrelated weight sets. Each collection of interrelated weight sets comprises a randomly generated initial weight set and subsequent interrelated weight sets generated in a predetermined manner. The predetermined manner for generating subsequent weight sets facilitates rapid identification of the optimal weight set for a collection, and thereby rapid identification of the overall optimal weight set for the collections.
-
Citations
20 Claims
-
1. In a computer system comprising a pipelined processor for executing instructions of programs in a parallel and overlapping manner, and a compiler for compiling and generating said instructions, wherein said compiler has a scheduler for scheduling said instructions for execution on said pipelined processor, and said scheduler schedules said instructions using N weighted cost based heuristics, a method for empirically selecting a set of N weights for said scheduler to weigh said N cost based heuristics, said method comprising the steps of:
-
a) generating arbitrarily an initial trial set of N weights, initializing said scheduler with said arbitrarily generated initial trial set of N weights, generating a plurality of benchmark programs, compiling said benchmark programs using said compiler, accumulating scheduling costs determined by said scheduler for said benchmark programs, initializing a lowest accumulated scheduling cost of said benchmark programs to said accumulated scheduling cost, and selecting said initial trial set of N weights as the selected set of N weights for said scheduler; b) generating sequentially a first plurality of additional trial sets of N weights in a first manner, one trial set of N weights at a time, each of said first plurality of additional trial sets of N weights being generated by systematically varying the immediately preceding trial set of N weights along an orthogonal dimension of a weight space formed by the N weights, one orthogonal dimension at a time, reinitializing said scheduler with each of said additional trial sets of N weights after each of their generations, regenerating said plurality of benchmark programs after each of said reinitializations, recompiling said regenerated benchmark programs using said compiler after each of said regenerations, reaccumulating scheduling costs determined by said scheduler for said benchmark programs during each of said recompilations, comparing each of said reaccumulated scheduling cost with said lowest accumulated scheduling cost to determine whether a new lowest accumulated scheduling cost is found after each of said reaccumulations, terminating said generation of additional trial sets of N weights in said first manner as soon as a new lowest accumulated scheduling cost is found, updating said lowest accumulated scheduling cost to equal the newly found lowest accumulated scheduling cost if a new lowest accumulated scheduling cost is found, and selecting the trial set of N weights that yields the new lowest accumulated scheduling cost over the previously selected set of N weights as the selected set of N weights for said scheduler if a new lowest accumulated scheduling cost is found; and c) generating sequentially a second plurality of additional trial sets of N weights in a second manner, one additional trial set of N weights at a time, each of said additional trial sets of N weights being generated under said second manner by systematically varying the immediately preceding trial set of N weights along the last orthogonal dimension with the last systematic variation made under said first manner, reinitializing said scheduler with each of said additional trial sets of N weights after each of their generations, regenerating said plurality of benchmark programs after each of said reinitializations, recompiling said regenerated benchmark programs using said compiler after each of said regenerations, reaccumulating scheduling costs determined by said scheduler for said benchmark programs during each of said recompilations, comparing each of said reaccumulated scheduling cost with said lowest accumulated scheduling cost to determine whether a new lowest accumulated scheduling cost is found after each of said reaccumulations, terminating said generation of additional trial sets in said second manner as soon as no new lowest accumulated scheduling cost is found, updating said lowest accumulated scheduling cost to equal the last newly determined lowest accumulated scheduling cost if at least one newly determined lowest accumulated scheduling cost is found, and selecting the last trial set of N weights that yields the last new lowest accumulated scheduling cost over the previously selected set of N weights as the selected set of N weights for said scheduler if at least one newly determined lowest accumulated scheduling cost is found. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. In a computer system comprising a pipelined processor for executing instructions of programs in a parallel and overlapping manner, and a compiler for compiling and generating said instructions, wherein said compiler has a scheduler for scheduling said instructions for execution on said pipelined processor, and said scheduler schedules said instructions using N weighted cost based heuristics, an apparatus for empirically selecting a set of N weights for said scheduler to weigh said N cost based heuristics, said apparatus comprising:
-
a) first trial weight generation means for generating arbitrarily an initial trial set of N weights; (b) second trial weight generation means coupled to said first trial weight generation means for generating sequentially a first plurality of additional trial sets of N weights by systematically varying the immediately preceding trial set of N weights in a first manner, one trial set of N weights at a time, each of said first plurality of additional trial sets of N weights being generated by systematically varying the immediately preceding trial set of N weights along an orthogonal dimension of a weight space formed by the N weights, one orthogonal dimension at a time; (c) third trial weight generation means coupled to said second trial weight generation means for generating sequentially a second plurality of additional trial sets of N weights by systematically varying the immediately preceding trial set of N weights in a second manner, each of said second plurality of additional trial sets of N weights being generated by systematic varying the immediately preceding trial set of N weights along the last orthogonal dimension with the last systematic variation made under said first manner; d) initialization means coupled to said first, second, and third trial weight generation means and said scheduler for initializing said scheduler with said arbitrarily generated initial trial set of N weights after its generation, and reinitializing said scheduler with each of said first and second plurality of additional trial sets of N weights generated under said first and second manners after each of their generations; e) benchmark generation means coupled to said initialization means and said compiler for generating an identical collection of benchmark programs for compilation by said compiler after said initialization, and each of said reinitializations of said scheduler; f) cost accumulation means coupled to said compiler for accumulating scheduling costs determined by said scheduler for said benchmark programs during each of said compilations of said collection of benchmark programs; g) first update means coupled to said first, second, and third trial weight generation means, and cost accumulation means for initially updating a lowest accumulated scheduling cost to equal the accumulated scheduling cost of said benchmark programs after the compilation in response to said initial trial set of N weights, updating said lowest accumulated scheduling cost to equal a newly found lowest accumulated scheduling cost if a new lowest accumulated scheduling cost is found through the compilations in response to said first plurality of additional trial set of N weights, and updating said lowest accumulated scheduling cost with the last newly found lowest accumulated scheduling cost if at least one new lowest accumulated scheduling cost is found through the compilations in response to said second plurality of additional trial set of N weights; h) first comparison means coupled to said accumulation means and said first update means for comparing the accumulated scheduling cost of said benchmark programs with said lowest accumulated scheduling cost to determine if a new lowest accumulated scheduling cost is found after each of said compilations in response to said first plurality of additional trial set of N weights, and comparing the accumulated scheduling cost of said benchmark programs with said lowest accumulated scheduling cost to determine if no new lowest accumulated scheduling cost is found after each of said compilations in response to said second plurality of additional trial set of N weights; i) first termination means coupled to said second and third trial weight generation means and said first comparison means for terminating said generation of said trial sets of N weights under said first manner by said second trial weight generation means as soon as a new lowest accumulated scheduling cost is found, and terminating said generation of said trial sets of N weights under said second manner by said third trial weight generation means as soon as no new lowest accumulated scheduling cost is found; and j) first selection means coupled to said first, second, and third trial weight generation means, and said first comparison means for selecting said initial trial set of N weights as the selected set of N weights, selecting the trial set of N weights yielding a new lowest accumulated scheduling cost over the previously selected set of N weights as the selected set of N weights while said trial sets of N weights are generated under said first manner, and selecting the last trial set of N weights yield a new lowest accumulated scheduling cost over the previously selected set of N weights as the selected set of N weights while said trial sets of N weights are generated under said second manner. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20)
-
Specification