Introduction to Algorithms, Third Edition

(logically) in series
. Otherwise, strands
u
and
are
(logically) in parallel
.
We can picture a multithreaded computation as a dag of strands embedded in a
tree of procedure instances. For example, Figure 27.1 shows the tree of procedure
instances for P-F
IB
.6/
without the detailed structure showing strands. Figure 27.2
zooms in on a section of that tree, showing the strands that constitute each proce-
dure. All directed edges connecting strands run either within a procedure or along
undirected edges in the procedure tree.
We can classify the edges of a computation dag to indicate the kind of dependen-
cies between the various strands. A
continuation edge
.u; u
0
/
, drawn horizontally
in Figure 27.2, connects a strand
u
to its successor
u
0
within the same procedure
instance. When a strand
u
spawns a strand
, the dag contains a
spawn edge
.u; /
,
which points downward in the figure.
Call edges
, representing normal procedure
calls, also point downward. Strand
u
spawning strand
differs from
u
calling
in that a spawn induces a horizontal continuation edge from
u
to the strand
u
0
fol-

---

27.1
The basics of dynamic multithreading
779
lowing
u
in its procedure, indicating that
u
0
is free to execute at the same time
as
, whereas a call induces no such edge. When a strand
u
returns to its calling
procedure and
x
is the strand immediately following the next
sync
in the calling
procedure, the computation dag contains