Parallel Computer Systems


Posted on 2019-01-21


PAR header image

Instruction level parallelism

The base model for describing instruction-level parallelism is inspired by network planning. In it, sub-tasks are sometimes connected with dependency relations, which are by their nature anti-symmetrical and which leads to creation of oriented (directed) graphs. Elements of such graph are:

  • Nodes - representing sub-tasks
  • Edges - representing sub-task dependencies

When talking about parallelization/optimization of code, first algorithms usually considered chunks of code between conditional branches and joins (colloquially jump-ins and jump-outs) in source code. We will call those pieces of code base blocks and define them as chunks of source code that don't have any jump-ins into the code (except before the first instruction) and no branching (except in the last instruction). Following that, last instruction of a basic block is either conditional jump instruction or is followed by a jump-in into the source code. In an effort to generalize this approach and avoid tying ourselves to the concept of an instruction, we'll also introduce the concept of an operation as the minimal activity that generates a result and is a consequence of an unary or binary operation on some data. Finally, we also need to define dynamic trail of program execution as the sequence of operations during the program execution.

Data dependency graphs and types of data dependencies inside the basic block

The most obvious data dependency is the true data dependency as a relation where some data is the output of one operation and the input of another. Existence of operations dependent in such a way introduces the read-after-write (RAW) data hazard. If we consider an operation to be a RISC instruction, first two cycles will be fetch and decode phases. That allows partial overlap in the cycles between the operations dependent in this way by the mechanism of forwarding, especially if we're using pipelining.

We need to distinguish between direct true data dependency, which implies that the dependent operation directly uses the result of the operation it's dependent on, as opposed to the indirect true data dependency which is the consequence of data dependency relation being transitive.