Traditional serial programs are often described using call graphs or class hierarchies. Parallel programming adds another layer on top of the serial analysis. To diagram, understand and analyze the parallel performance of an Intel® Cilk™ Plus program, you need to distinguish between sections of code that run serially, and sections that may run in parallel.
The term strand describes a serial section of the program. More precisely, the definition of a strand is "any sequence of instructions without any parallel control structures."
According to this definition, a serial program can be made up of many sequential strands as short as a single instruction each, a single strand consisting of the entire program, or any other partitioning. A maximal strand is a strand that is not part of a longer strand, that is, a strand whose start and end points are parallel control structures.
An Intel® Cilk™ Plus program contains two kinds of parallel control structures - spawn and sync. (A parallel loop, such as _Cilk_for, is just a convenient notation for decomposing a problem into spawns and syncs.) The following illustrates 4 strands (1, 2, 3, 4), a spawn (A) and a sync (B). In this figure, only strands (2) and (3) may execute in parallel.
In this diagram, the strands are represented by lines and arcs (edges), while the parallel control structures are represented by the circular nodes (vertices). The strand diagram represents a Directed Acyclic Graph (DAG) that represents the serial/parallel structure of a program.
An Intel® Cilk™ Plus program fragment that reflects the structure in the diagram is as follows:
... do_stuff_1(); // execute strand 1 cilk_spawn func_3(); // spawn strand 3 at A do_stuff_2(); // execute strand 2 cilk_sync; // sync at B do_stuff_4(); // execute strand 4 ...
In an Intel® Cilk™ Plus program, a spawn has exactly one input strand and two output strands. A sync has two or more input strands and exactly one output strand. The following diagram shows a DAG with two spawns (labeled A and B) and one sync (labeled C). In this program, the strands labeled (2) and (3) may execute in parallel, while strands (3), (4), and (5) may execute in parallel.
A DAG represents the serial/parallel structure of the execution of an Intel® Cilk™ Plus program. With different input, the same program may have a different DAG. For example, a spawn may execute conditionally.
Most Intel® Cilk™ Plus programs are strand-invariant, that is, for a given input, every execution of the program generates the same DAG, independent of the number of processors used to run the program. To determine the DAG of a strand-invariant program, it is sufficient to run the program on a single processor. A later section will describe the execution model and explain how work is divided among the number of available processors.