Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.2k answers


538 users

0 votes

In chapter 3 on parallelizing compilers on slide 18 "Basic Block Scheduling" the scheduling algorithms

  • ASAP
  • ALAP
  • Optimal resource by ILP
  • Linear scheduling
  • List scheduling
  • Force directed scheduling

are classified as time constrained algorithms.

However, in the following subsection "Resource Contrained Schedulung: ILP, Linear, List, Force Direced Scheduling" they are listed in a rousource constrained context. Does this mean only ASAP and ALAP are only time contrained, while the other four scheduling algorithms are both, time AND resouce constrained?

in * TF "Emb. Sys. and Rob." by (150 points)

1 Answer

0 votes
ASAP and ALAP are both scheduling the instructions along the critial path, so that both of these scheduling algorithms are time-constrained, i.e., they minimize the runtime without caring about the required resources.

The ILP scheduling presented in the slides also makes use of the minimal runtime, but schedules the instructions in their mobility intervals so that the number of resources is minimized while keeping the minimal runtime. This means that there can be schedules with fewer resources that require however a longer runtime (typically a single PU can do which requires however as many steps as there are instructions).

The Force Directed Schedule does the same as the ILP scheduler mentioned above, but it is just a heuristic, and therefore does not guarantee an optimal use of the resources with the minimal runtime. It just tries to establish an equal use of the resources on the minimal runtime. Page 39 defines this clearly.

Page 32 explains that linear scheduling is a resource constrained scheduling method that may require more than the minimal runtime achieved by ASAP, ALAP or ILP scheduling, and the same holds for linear scheduling. The examples on the slides also show that more runtime is required for the listed examples.

So, while ASAP/ALAP do not care at all about resources, ILP and Force Directed Scheduling also primarily maintain the minimal runtime, but consider as a secondary goal the reduction of the resources for the minimal runtime. Linear and list scheduling, on the other hand, do not maintain the minimal runtime, and rather reduce the resources as a primary goal.
by (166k points)
Imprint | Privacy Policy