An Experimental Evaluation of List SchedulingKeith D. Cooper, Philip J. Schielke, and Devika SubramanianDepartment of Computer ScienceRice UniversityHouston, Texas, USARice Computer Science Techcnical Report 98-326September 1998An Experimental Evaluation of List Scheduling⋆Keith D. Cooper, Philip J. Schielke, and Devika SubramanianDepartment of Computer Science, Rice University, Houston TexasAbstract. While altering the scope of instruction scheduling has a rich heritage in compiler literature,instruction sched uling algorithms have received little coverage in recent times. The widely held belief isthat greedy heuristic techniques such as list scheduling are “good ” enough for most practical purposes.The evidence supporting this belief is largely anecdotal with a few exceptions.In this paper we examine some hard eviden ce in support of list scheduling. To this end we presenttwo alternative algorithms to list schedu ling that use randomization: randomized backward forward listscheduling, and iterative repair. Using these alternative algorithms we are better able t o examine theconditions und er which list scheduling performs well and po orly. Specifically, we explore the efficacyof list scheduling in light of available parallelism, the list scheduling priority heuristic, and number offunctional units. While the generic list scheduling algorithm does ind eed perform quite well overall,there are imp ortant situations which may warrant the use of alternate algorithms.1 IntroductionInstruction scheduling plays a critical role in determining the performance of compiled code on to day’scomputers. Today’s microprocessors rely on the compiler to hide memory la tencies and to keep functionalunits busy—both are task s for the instruction scheduler. On the microprocessors of tomorrow, the qualityof instruction scheduling may be more important, since these machines will feature longer memory la tenciesand more functional units.Despite the importance of scheduling, we know quite little about the behavior of list scheduling—themost widely used technique for instruction scheduling [1, 3]. This paper pres e nts an experimental evaluationof list scheduling that attempts to answer the following questions:1. I s there room fo r improvement beyond list scheduling? It is widely b e lieved that list scheduling usuallyachieves optimal or near-optimal results [5]; is this the case?2. Will new microprocessor designs change the efficacy of list scheduling? To keep these machines busy,compilers will apply transformations that increase instruction-level parallelism; how will that change thescheduling pr oblems tha t the compiler sees?3. C an we classify scheduling problems so that the compiler can recognize when other scheduling techniquesshould be invoked? If we can discover metrics that predict bad behavior from list scheduling, we candesign compilers that avoid it.To answer these and other questions, this paper examines the strengths and weaknesses of list s cheduling.We develop se veral metrics to classify instances of scheduling problems. We evaluate the performance oflist scheduling against those metrics and compare it against two alternative scheduling algor ithms. Ourexp eriments use both real benchmark codes and randomly-generated sets of basic blocks.The remainder of the paper is o rganized as follows. Section 2 provides background information aboutthe fra mework in which we performed this investigation. Section 3 discusses the list s cheduling algorithm.Section 4 describes improvements to list scheduling and an alternative technique based on iterative repair.Section 5 presents our metrics for classifying instances of the scheduling problem. Sections 6 and 7 presentexp erimental results.2 Experimental SetupOur experiments use components of a resear ch compiler system developed at Rice University. It has front endsfor both C and Fortran; these translate the input code into a linear, low-level intermediate form called iloc.⋆This work h as been supported by DARPA and the USAF Research Laboratory through Award F30602-97-2-298.The individual iloc operations r esemble simple risc machine operations, with register-to-register operationsthat manipulate virtual registers, plus load and store operations. Individual op e rations are grouped togetherinto instructions; an instruction aggregates together all the operations that begin execution in a single cycle.Before scheduling, the compiler applies a series of optimizations to the iloc code. This includes pointeranalysis, dead code e liminatio n, global value numbering, lazy code motion, constant propagation, strengthreduction, register co alescing, dead code elimination, and empty block removal. For the purposes of thispaper, no register allocation was performed; this eliminates interactions between allocation and schedulingand isolates the impact of scheduling.After optimization, the compiler passes the code to the scheduler. Each block is scheduled individually.The first step constructs a data-precedence gra ph (dpg) for the block. The dpg G = (N, E, E′) has a noden ∈ N for each operation. Edges e = (ni, nj) ∈ E represent dependences be tween operations; their directionmatches the flow of values. Edges in E′represent anti-dependences in the code that prevent reordering. Ananti-edge e = (ni, nj) ∈ E′indicates that moving njbefo re niwould change the flow of values because ofa name that niuses and njredefines. The details of the individual schedulers vary; they are described insections 3 and 4 .To evaluate the schedules, we use several variations on a s imple processor model. Each architectureconsists of k identical pipelined functional units. Each functional unit can execute any iloc operation. Forour experiments, we vary k between one and three. Each iloc operation has a latency—the number of cyclesrequired before its results are available. Register values are read in the cycle when the instruction beginsexecution, and results are defined in the last c ycle of its latency. Thus, an operation u can begin executionwhen all operations v |(v, u) ∈ E have completed, and all operations w |(u, w) ∈ E′have already been iss ued.3 The List Scheduling AlgorithmHere we desc ribe our implementation of list scheduling. First, the dpg is built as described in the previoussection. Next, priorities are assigned to each node in the graph. There are several different heuristics thatcan be used to assign priorities. A common and effective
View Full Document
Unlocking...