Recently I've accepted a job offer to work on compiler design. To be properly prepared I've decided to review the material. The book that is being used for that is Cooper and Torczon's Engineering a Compiler. That's the one we used in a class. On page 645 there is a definition of a schedule, but I can't figure out what it means

Here is the definition:

Given a dependence graph $D$ for a code fragment, a schedule $S$ maps each node $n\in N$ to a nonnegative integer that denotes the cycle in which it should be issued, assuming that the first operation issues in cycle 1. This provides a clear and concise definition of an instruction, namely, the $i^{th}$ instruction is the set of operations $\{n \space | \space S(n) = i\}$

I can't understand what this is saying. Can someone phrase this in a simpler way?

  • 1
    $\begingroup$ What specifically don't you understand? Notation? Terms? The final conclusion? (Who are the authors of this book?) Anyway, this seems to be related to operation reordering. Their use of the term "instruction" (vs "operation") seems ... interesting. You may want to include both term definitions in the question. $\endgroup$ – Raphael Jul 15 '15 at 5:49
  • 1
    $\begingroup$ @Raphael This distinction between instruction and operation seems common for VLIW, an instruction being what can be issued in a given cycle, an operation being a smaller unit of action (potentially corresponding to a node). The quote is basically just saying that, given dependencies (and latencies as well as structural hazards), operations from a piece of code can be ordered where each cycle an instruction of zero or more operations can be issued, defining an instruction as the collection of all operations that issue in a given cycle. $\endgroup$ – Paul A. Clayton Jul 15 '15 at 13:38
  • $\begingroup$ It's hard to rephrase this without knowing the definitions. Can you clarify what is confusing? $\endgroup$ – Juho Jul 16 '15 at 6:47

I lent my copy of Cooper and Torczon to someone and never got it back, so I can't look up the context. (It's a good book in general (which is why I didn't get it back)).

The definition of instruction here is unusual. It corresponds more closely to what you might expect in a Very Long Instruction Word (VLIW) computer or in horizontal microcode.

In a VLIW machine, each instruction is made up of a small fixed number of independent operations. A typical example would be something like: at most one branch instruction, at most two memory operations, and at most two arithmetic operations. So you'd expect each instruction to be made up of five operations (some of which might be "no-ops"). So there are going to be two constraints here, and the definition of instruction given by Cooper and Torczon has not yet taken into account those constraints. (I suspect that they will start discussing the constraints in the pages just after page 645).

To be more specific: a VLIW instruction is a set of operations that can be executed simultaneously/concurrently. The operations must be (1) independent of each other and (2) the hardware must have sufficient function units to execute all the operations in the set simultaneously.

Cooper and Torczon are probably about to introduce some list scheduling heuristics. In list scheduling you assign a non-negative integer to each operation such that (1) the dependence dag $D$ is "satisfied" (for all directed edges $x \rightarrow y$, $S(x) \lt S(y)$). And (2) the set of operations scheduled on each cycle is feasible given the available hardware. For example, in a greedy list scheduling heuristic you would traverse the dependence DAG in some topological order placing each instruction at the earliest cycle which satisfies both conditions.


I think I understood it.

An instruction $i$ is a set of operations that can execute in cycle $i$. For example, let's say we have the following program (set of operations)


And lets say because of the dependencies mult and div can execute in cycle 1, add and sub can execute in cycle 2, load can execute in cycle 3 and store can execute in cycle 4.

Provided there is enough hardware to execute these operations we get the following:

instruction 1: mult and div
instruction 2: add and sub
instruction 3: load
instruction 4: store


Not the answer you're looking for? Browse other questions tagged or ask your own question.