An Example of Deriving Performance Properties from a Visual Representation of Program Execution.
AbstractThrough geometry, program visualization can yield performance properties. We derive all possible synchronization sequences and durations of blocking and concurrent execution for two process programs from a visualization mapping processes, synchronization, and program execution to Cartesian graph axes, line segments, and paths, respectively. Relationships to Petri nets are drawn.
Introduction
Systems to visualize the execution history collected from a program can help explain what happens
during program execution (e.g., [4, 10, 13, 15]). Visualization systems can lend insight into why a
Supported in part by National Science Foundation grant NCR-9211342.
performance measure, such as program execution time or mean waiting time for a resource, has a
particular value. The answer to "why" helps identify how to change the program to improve the
measure.
But visualization has a use beyond providing images on a computer monitor: one can formally
deduce properties about program execution from a visualization. This was first demonstrated by
Roman and Cox [19], who deduced correctness properties. Roman and Cox illustrate that safety
properties (properties that hold in all computation states, such as invariants) and progress properties
(properties that hold in a particular program state) can be verified by defining a mapping
of program states to a visual representation, and then observing whether the sequence of visual
images corresponding to an execution sequence satisfies a desired property. They discuss the ability
"to render invariant properties of the program state as stable visual patterns and to render
progress properties as evolving visual patterns."
This paper provides a second example, deducing the following performance properties from a
visualization of a class of concurrent programs:
Q1: the sequence of synchronization points where the program blocks,
Q2: the blocking duration at each synchronization point, and
Q3: the duration of concurrent execution between synchronization points.
The class consists of program that meets the following assumptions: A program contains two
processes (A1). A process executes on a dedicated processor (A2). A process only blocks at
synchronization operations (A3). A synchronization operation in a process A is defined in terms
of a code segment C in the other process B: when A reaches the synchronization operation it
will block if and only if B is executing C. Each process is represented as a branchless directed
graph in which vertices represent code segments and edges always represent precedence relations
and may represent synchronization operations (A4). A process will optionally block when moving
from one vertex to another if the edge corresponds to a synchronization operation. The execution
time of the code segment corresponding to each vertex is an independent constant, exclusive of
time spent blocked (A5). Each process has an initial vertex in which the process starts execution
and, optionally, a final vertex in which the process terminates (A6). A process without a final
vertex never terminates.
We argue next that the assumptions are reasonable. Consider the two process assumption
(A1). The initial solutions to some classic parallel programming problems - such as shared
memory mutual exclusion algorithms - were initially solved only for two processes. And one
important performance evaluation tool - queueing networks - started only with the ability to
solve just one kind of queue (M/M/1) in isolation. In principle the analysis presented here can be
extended from two to an arbitrary number of processes; see the conclusions (x7) for a discussion.
Regarding the constant time assumption (A5), Adve and Vernon [5] conclude based on seven
parallel applications that "it appears reasonable to ignore the variability in execution times when
estimating synchronization delays," and that an exponential task time assumption could actually
lead to more severe errors than a constant-time assumption. As for relaxing assumption A2,
multiprogramming has been modeled in past work that uses the visualization underlying our
work, and can be incorporated into the model presented here. The branchless assumption (A4) is
not as restrictive as it might first appear, because loops whose number of iterations is known can
be unrolled to obtain a branchless graph. Our analysis includes non-terminating programs (A6),
because certain long running programs repeatedly execute the same code, such as simulations and
reactive programs (programs that react to external stimuli on an ongoing basis, such as operating
systems).
Our solution method represents program execution by a Timed Progress Graph (TPG). To our
knowledge, TPGs were originally used in Operations Research to find minimum length schedules
for two jobs that share a set of machines [20, pp. 262-263]. However, a good and not necessarily
minimal schedule was found "by eye" rather than by a formal method. Later, a simplified form
of TPG, called an untimed progress graph (UTP), in which each delay in the timed transition
diagram is unity, was used to analyze deadlocks. 1 Carson and Reynolds [7] define a UPG as "a
multidimensional, Cartesian graph in which the progress of each of a set of concurrent processes
is measured along an independent time axis. Each point in the graph represents a set of process
times." Kung, Lipski, Papadimitriou, Soisalon-Soininen, Yannakakis, and Wood [11, 17, 22, 24]
used UPGs to detect deadlocks in lock-based transaction systems. More recently Carson and
Reynolds used UPGs to prove liveness properties in programs with an arbitrary number of
containing P and V operations on semaphores that are unconditionally executed. Our
use of TPGs to analyze program performance properties is novel.
TPGs map the progress of each process to one Cartesian graph axis. Line segments represent
interprocess synchronization. A directed, continuous path that does not cross a segment represents
a particular execution of a program. This path may be found by computational geometric
algorithms to compute line segment intersections and for ray shooting.
The remainder of the paper is organized as follows. First we define TPGs and illustrate their
use on sample programs in x2. The representation of an execution of a program is then formalized
in x3. x4 presents an algorithm to solve the problems listed earlier. We then consider, in x5, a
special class of programs that displays periodic behavior and present an algorithm to solve for the
set of all possible periodic state sequences that can arise during any execution of a program. x6
relates TPGs to Petri Nets. Finally x7 contains conclusions.
Timed Progress Graphs
We first illustrate our approach to solving for quantities Q1 to Q3 from x1 on three programs.
Apparently TPGs were reinvented in the Computer Science field and attributed to Dijkstra [8].
process producer process consumer
X:
while (TRUE) do while (TRUE) do
read X from disk; receive X from consumer;
send X to consumer; write X to disk;
do od

Figure

1: Non-terminating producer/consumer program with one buffer.
Non-terminating Producer/Consumer

Figure

1 contains a producer/consumer program that use one message buffer for interprocess
communication. Thus when the producer sends a message it fills the single buffer and thus must
wait until the consumer executes receive before performing the next send. Figure 2 contains
an equivalent graph representation of the program and satisfies assumptions A1 to A6. The
deterministic execution time of each graph vertex, excluding time spent blocked, is shown in
square braces. Edge conditions B1 and B2 represent blocking that may occur during a send and
receive, respectively. (For simplicity of presentation, we assume that a process blocks at the end
of a send or receive operation; this condition is straightforward to relax.) Recall from A3 that
specifying a synchronization operation requires identifying a code segment C for which a process
may block. Therefore in Fig. 2 conditions B1 and B2 are the following: (B1) The producer never
blocks when it performs the first send; furthermore the producer blocks when it performs the n-th
send (n ? 1) if the consumer has not yet executed the 1-st receive. (B2) The consumer
cannot execute the n-th (n - receive until the producer has executed the n-th send.
Recall that a TPG maps the progress of each process to one Cartesian graph axis; the result for
Fig. 1 is shown in Fig. 3. The sequence of graph vertices that each process passes through is mapped
to a sequence of intervals (denoted by grey lines in Fig. 3(a)) along the corresponding axis. Interval
widths correspond to execution time of vertices. Synchronization between processes is represented
read X from disk;
send X to consumer;
receive X
from
consumer
write X to disk;
receive X from consumer
Producer: Consumer:

Figure

2: Graph model corresponding to Fig. 1. Numbers in square brackets refer to time spent in
each code segment. Labels on each edges denote conditions under which blocking occurs. Thick
circles represent initial vertices; there are no final vertices.
in Fig. 3(b) by horizontal and vertical line segments in the plane placed at appropriate boundaries
of vertex intervals to prohibit a transition into a vertex. The line segments, called constraint
lines, are closed at the end point closest to the origin and open at the other end point. Each line
segment corresponds to a blocking condition in the graph. Consider B1 in Fig. 2. From Fig. 3(a),
the producer makes the first transition from the read.; send.; vertex back to itself at time
4, the second at time 8, and the n-th at time 4n (in the absence of blocking). Similarly, the
consumer completes its first receive at time 1, its second at time 3, its third at time 5, and its n-th
at time 2n \Gamma 1. Therefore, by B1, the producer will block at time 4n (for n ? 1) if the consumer
has completed its 1-st receive, corresponding to points that exceed coordinate
on the axis representing the consumer. Thus the producer will block in any point (x; y) meeting
the following two conditions: corresponding to the vertical
lines in Fig. 3(b). Similarly, by B2, the consumer will block when it tries to complete the n-th
receive (at time the producer has not yet completed the n-th send (at time 4n). Thus
the consumer will block in any point (x; y) meeting the following two conditions:
corresponding to the horizontal lines in Fig. 3(b).
Given an initial point, execution of a program is represented by a point or a directed path in the
1st receive
2nd receive; 1st write
3rd receive; 2nd write
1st
read;
send
2nd
read;
send
3rd
read;
send
(a) Mapping states to a TPG
Producer
Consumer15
(c) Mapping program execution to a TPG
Consumer
(b) Mapping synchronization to a TPG
Consumer15

Figure

3: Representation of one-buffer producer/consumer program (Fig. 2) by a TPG.
plane, called a timed execution trajectory (TET). The initial point is (0,0) if both processes start
simultaneously. A TET is a point only if the initial point represents a deadlocked state. Otherwise
the TET is a path and consists of a possibly infinite sequence of rays that have slope 0, 1, or 1.
The ray has slope 0 (respectively, 1) when the process corresponding to the vertical (respectively,
horizontal) axis is blocked, and slope 1 when both processes are running concurrently. Because
constraint lines represent forbidden state transitions, a TET cannot cross a constraint line. A
finite portion of the TET for the one buffer producer/consumer problem is the thick directed path
in Fig. 3(c). The general method of constructing a TET is given below.
TET construction rule: Given a TPG, a TET is constructed recursively as follows. Let upper
case letters with optional superscripts (i.e., G; G 0 ; G I ) denote graph points. Let a point G denote
the ordered pair of coordinates any two points G and G 0 ,
line segment that is closed at G 0 , open at G 00 , and satisfies G
Rule I: If G lies on some constraint line [G 0 ; G 00 ), then there either (1) will or (2) will not exist
a point G I distinct from G 0 at which [G 0 ; G 00 ) intersects another constraint line instance such that
I . In case (1), the TET rooted at G is a ray with initial point G and final point G I . In
case (2), the TET rooted at G is a ray with initial point G and final point G 00 , followed by a TET
rooted at G 00 .
Rule II: If G lies off a constraint line, then a slope one ray rooted at G either (1) will or (2) will
not intersect a constraint line. In case (1), the TET rooted at G is a slope one ray with initial
point G and final point G 0 , where G 0 is the only point on the ray that lies on a constraint line,
followed by the set of TETs rooted at G 0 . In case (2), the TET rooted at G is an infinite length,
slope one ray rooted at G.
Example 1 Consider the TET portion in Fig. 3(c). Point lies off a constraint line,
and follows Rule II, case (1). Thus the TET is ray [(0; 0); (1; 1)) followed by the TET rooted at
(1,1). Next, lies on horizontal constraint line [(0; 1); (4; 1)). By Rule I case (2), the
second TET ray must be [(1; 1); (4; 1)). Next Rule II case (1) again applies and the third TET
ray must be [G; G 0 ), where This process is continued forever to yield
an infinite length TET. 2
The TET in Fig. 3(c) yields the three performance properties Q1 to Q3 sought in the opening
paragraphs of this paper. The sequence of synchronization points, Q1, corresponds to the sequence
of horizontal and vertical rays arising in a TET. The TET of Fig. 3(c) contains only horizontal
rays, and thus the program never blocks when the producer executes a send. The blocking
duration at each receive, Q2, is the length of each horizontal ray in the TET in Fig. 3(c): 3 time
units for the first receive (because the first horizontal ray is [(1; 1); (4; 1))), and 2 time units for
each subsequence receive. Finally, the duration of concurrent execution between synchronization
points, Q3, is the length of the perpendicular projection of each diagonal ray in the TET on either
axis in Fig. 3(c): 1 time unit from when the program starts until a process first blocks (because
the first diagonal ray is [(0; 1); (1; 1))), and 2 time units after each subsequence receive.
2.2 Program 2: Non-terminating Mutual Exclusion

Figure

4 contains a different form of synchronization than the last program: two database transactions
update the same record (a serially reusable resource) in mutually exclusive fashion using two
semaphores. (Only one is needed, but we use two to illustrate several concepts.) The equivalent
graph model is shown in Fig. 5. Blocking can only occur on the edges out of a vertex representing
a code segment in which a P semaphore operation is performed. The blocking condition is that a
process cannot complete a P operation until the other process is not in the code segment between
completion of a P operation and a V operation on the same semaphore. Such code segments label
edges in Fig. 5 and correspond to C in A4 (x1),
The corresponding TPG in Fig. 6 shows in heavy lines the set of TETs that could arise from
two initial points. Suppose that process 1 runs for 5.5 time units before process 0 starts; this
corresponds to initial point (0,5.5). The TET consists of a single slope one ray of infinite length
by Rule II, case (2). Therefore the processes forever execute without blocking. Now suppose that
process 0 starts execution 2 time units before process 1; there are two possible TETs, both rooted
at initial point (2,0). Both TETs contain as their first ray ([(2; 0); (3; 1))), representing concurrent
execution by both processes for one time unit. The final point of this ray, (3,1), represents
the program state when both processes simultaneous attempt to perform the P(B) semaphore
A,B: semaphore=1;
process 0 process 1
while (TRUE) do while (TRUE) do
input; input;
output; output;
do od

Figure

4: Non-terminating data-base transactions using semaphores and a serially reusable resource

operation. There are two possible outcomes, corresponding to which process first completes P(B).
Thus point (3,1) represents a non-deterministic program state. If process 1 first completes P(B),
then process 0 blocks and the second TET ray is vertical: ([(3; 1); (3; 3))). The TET has a final
point, which is (3,3), representing a deadlock. The deadlock arises because process 1 then attempts
and blocks because process 0 already holds semaphore A. The alternate TET with initial
point (2,0) has as its second ray ([(3; 1); (6; 1))) (in which process 1 blocks for 3 time units). This is
followed by a third ray, with slope one, initial point (6,1), and infinite length. Thus when process
starts 2 time units after process 0, the program either reaches a deadlock or process 0 blocks for
units after which both processes run forever without blocking. Because UPGs have been
used extensively for analysis of deadlocks [7, 11, 17, 22, 24], deadlocks are not considered further
in this paper.
2.3 Program 3: A Terminating Program
Fig. 7, unlike the previous two programs, contains a terminating program. A producer process
reads a disk file whose first record specifies the number of successive records, and sends the records
to the consumer, which then writes the records to another disk file. (To simplify presentation,
input;
output;
Process 0:
input;
output;
Process 1:

Figure

5: Graph model corresponding to Fig. 4.
Process 1
input;
output
input;
output

Figure

Timed progress graph corresponding to Fig. 5.
constant Size=2; A: integer[0.Size];
process producer process consumer
I, NumRecords:
read NumRecords from disk; while (TRUE) do
for I=1 to NumRecords do Y: character;
X:
read X from disk; Y=A[K];
od

Figure

7: Terminating producer/consumer code with shared memory interprocess communication.
the consumer is non-terminating.) We assume that interprocess communication is implemented
through mutually exclusive access to shared memory using an array with Size elements. The
corresponding graph (Fig. 8) is obtained by unrolling the loops in the two processes.
The corresponding TPG (Fig. 9, for NumRecords=6), unlike the preceding TPGs, is bounded
on four sides, not just two (i.e., the left and bottom by the axes). The two additional bounds,
called the right and top bounding lines, with equations
of the producer and consumer, respectively, at times 25 and 31.
Because Fig. 7 combines the synchronization of the preceding two examples, its TPG (Fig.
combines the two forms of constraint lines in the preceding TPG figures. The TETs shown
represent all possible executions when both producer and consumer start simultaneously. Note
that all TETs are of finite length and have a final point (at point (25,31)), because the producer
terminates after sending six records and the consumer blocks forever at P(Full) after receiving
six records.
read
NumRecords
read X;
P(Empty)
[1.5]
Producer:
Consumer:
read X;
P(Empty)
[1.5]
BP1: n-th (for n<=Size) transition never blocks;
n-th (for Size<n<NumRecords) transition blocks if the consumer has not yet executed (n-Size)
transitions of vertex "V(Empty)."
BC1: n-th transition blocks if the producer has not yet executed n-th transition out of vertex
"V(Full)."

Figure

8: Graph model corresponding to Fig. 7. Thick circles denote initial and final vertices.
We learn from the TPG that the first synchronization point encountered is when the consumer
performs P(Full) (point (1,1)). The next synchronization point occurs when the producer and
consumer simultaneously attempt, respectively, the third and second access to the shared buffer
pool (point (11,7)). At this time a race condition occurs. If the producer obtains semaphore
first (and thus the TET contains ray [(11; 7); (12:5; 7))), then for the remainder of execution
the consumer never blocks and the producer will repeatedly synchronize briefly at its P(Empty)
operation. On the other hand, if the consumer obtains semaphore ME first (and thus the TET
contains ray [(11; 7); (11; 8))), then the processes will again encounter a race condition followed
Producer
Consumer
Write Y
Write Y
Write Y
Write Y
Write Y
Write Y

Figure

9: Timed progress graph corresponding to Fig. 8 with NumRecords=6.
by the same two possible outcomes. All TETs contain as part of their final ray [(25; 25); (25; 31)],
which represents the consumer removing the final buffer after the producer has terminated.
2.4 Problem Statement
The preceding examples demonstrate that quantities Q1 to Q3 from x1 can be computed by solving
problem P1 below. P2 is added to illustrate state reachability analysis with TPGs.
P1: Given a TPG, find the set of all possible TETs rooted at some initial point.
P2: Given a TPG, determine if there exists any process starting times that correspond to a point
leading to exactly one TET in which no process ever blocks (e.g., the TET rooted at (0,5.5)
in Fig. 6). Furthermore, if there exists such times, then output an example.
3 Construction of a TET
Before presenting algorithms solving P1 and P2, we formally define a TPG and the rule to construct
all possible TETs. Let R and Z denote, respectively, the non-negative reals and integers.
3.1 Formal Definition of TPG
Definition. A TPG for a graph representation of a program is an ordered pair h ; G C i, where
is a non-empty set of constraint line segments in the positive R 2 plane, and G C is an initial point
in R 2 representing the earliest instance at which both processes have started execution.
For example, consider the TPG in Fig. 3(b). Let   V denote the vertical lines: f(8
Zg. The horizontal lines are   Zg. The
TPG is h  V [   H ; (0; 0)i. For terminating programs,   also contains the right and top bounding
lines (e.g., Fig. 9).
3.2 Transition Function f
To formalize Rules I and II from x2.1 for a TPG h ; G C i, we define below two functions, f
respectively. (The subscript "o" in f o denotes a ray that is orthogonal to the axes, and the "d" in
f d denotes a ray that is diagonal [with slope one].) Defining f o and f d requires some notation. For
any continuous path fl and any point G on fl, we write G 2 fl. For any directed, continuous path
fl, we write fl:i (respectively, fl:f ) to denote the initial (final) point. We assume that fl:i 6= fl:f .
For any two continuous paths fl and fl 0 in R 2 , g. The relation
lies on line or ray L. Line or ray [G; (1; 1)) has slope one and infinite length.
lies on a constraint line instance L and -
G is the smallest of L:f and those points
greater than G at which L intersects another constraint line instance. Formally,
min
i: (1)
lies off a constraint line instance and -
G is the smallest of (1; 1) and the set of
points at which a slope one ray rooted at G intersects a constraint line instance. Formally,
Functions f
maps each point G to a (possibly empty) set of successors f(G) ' R 2 .
A point is nondeterministic iff the transition out of the point is not unique (e.g., (3,1) in Fig. 6),
for example representing states in which both processes simultaneously perform a P operation on
the same semaphore. All other points are deterministic. A point is dead iff there is no transition
out of the point (e.g., (3,3) in Fig. 6), representing states in which both processes are blocked. A
dead point may represent either a program deadlock or program termination.
Definition. A point G is nondeterministic iff jjf (G)jj ? 1 and is dead iff
3.3 Constructing a TET
A TET is a point or a directed continuous path consisting of a sequence of horizontal and diagonal
rays. There may be multiple TETs rooted at the same initial point. The following definition of
TET also provides a rule to construct a TET that formalizes the recursion in Rules I and II of x2.
timed execution trajectory (TET) of a TPG h ; G 0 i rooted at any point G 0 2 R 2 is
either (1) a point G 0 or (2) a directed, continuous path rooted at G 0 . Case (1) holds iff
Case (2) holds iff the path is a ray sequence [G may be
In case (2), n is finite iff f(G n
Example 2 In Fig. 3(c), the first line segment in the TET rooted at initial point G
1)g. This is because (0,0) does
not lie on a constraint line instance and a slope one ray rooted at point (0,0) first intersects a
constraint line instance at point (1,1). Next, f((1; 1)g. Thus, the second
TET line segment is 1). Continuing in this manner yields [(0; 0); (1; 1)),
as the only possible TET.
As a second example, consider G Fig. 6. Then f(G
However, (3,1) is nondeterministic; thus f(G 1 1)g. Continuing like this yields two
possible TETs: [(2; 0); (3; 1)), [(3; 1); (3; 3)) and [(2; 0); (3; 1)), [(3; 1); (6; 1)), [(6; 1); (1; 1)). 2
This section contains algorithms to solve P1 and P2 from x2.4 for terminating programs.
4.1 Computing Function f
Essential to solving P1 and P2 is a method of computing transition function f for a TPG h ; G C i.
By definition, computation of f(G) for any point G in R 2 requires computing either f
lies on a line in  , or f d (G) otherwise. Computation of f o and f d is discussed below.
Computation of f Computation of f line L is straightforward using
relation (1) of x3.2. (1) requires computation of the set of all points of intersection of line (L:i; L:f)
with other lines in  . We precompute fG 0
which then reduces the computation of each evaluation of f o (G) to evaluating the minimization
function in (1). Precomputing this set is equivalent to a well known computational geometric
problem: computing all intersections of a collection of horizontal and vertical lines (e.g., see [21,
Ch. 27]). Thus computation of f o is not considered further.
Computation of f d (G): Recall that f d (G) is the smallest of (1; 1) and each point at which
a slope one ray rooted at G intersects a constraint line instance. The well known problem of ray
shooting with line segments [6, pp. 234-247] can be used to find f d (G): Given a point, a direction,
and a finite set of line segments in a plane, find the first line segment intersected by a ray rooted
at the point with the given direction. The typical ray shooting solution first stores the line
segments in a data structure, so that subsequent queries consisting of a point and a direction can
be answered in sublinear time. Let ShootRay(point P, direction D, set of line L) denote
a ray shooting algorithm whose parameters are a point P ; a direction D (either for a ray
directed away from or toward the axes, respectively); and a set L, containing a finite number of
line segments. The return value is the point of intersection or (1; 1) if the ray does not intersect
a line segment. Formally, f d
4.2 Problem P1: Finding All Possible TETs
Problem P1: Given a TPG h ; Gi, output a representation of all TETs rooted at G.
The definition of TET along with the aforementioned methods to compute f o and f d solve P1.
However, there is one technical problem: f(G) is a set that contains either one (for deterministic
or two (for non-deterministic G) points. If f(G) contains two points, then there are at least
two possible TETs rooted at G. We say "at least two" because if a point on one of the TETs
rooted at G contains a point distinct from G that is nondeterministic, there will be more than
two TETs rooted at G. Therefore a solution to P1 requires calculating a set of TETs.
The proposed algorithm constructs a directed graph. If the set of all possible TETs rooted
at G is simply the point G, then the graph contains one vertex, labeled G. Otherwise the graph
contains one vertex for each ray end point in all possible TETs rooted at G. The graph is colored,
with green representing unexplored vertices and the remaining vertices colored red.
FindAllTETs (for terminating programs): Initialize the graph to contain one vertex representing
G, colored green. The following step is repeated until there are no more green vertices
in the select a green vertex G 0 in the graph; color G 0 red; for each vertex G 00 2 f(G 0 ), add
an arc from G 0 to G 00 and color G 00 green.
Example 3 For Fig. 9, the graph consists of a vertex for point (0,0) with an outgoing arc to a
vertex for point (1,1), an arc from (1,1) to a vertex for (5,1), an arc from (5,1) to (11,7), two
outgoing arcs from (11,7) to (12.5,7) and (11,8), and so on, with all graph paths leading to the
vertex for point (25,31). Only the vertex for (25,31) has no outgoing arc. 2
4.3 Problem P2: Deciding Existence of Non-blocking TETs
We restate P2 using the following definition: a TET is non-blocking if the TET contains no points
representing a state in which a process is blocked. (Geometrically, a diagonal ray rooted at a point
that leads to a non-blocking TET never intersects a constraint line in   and its final point lies on
the top or right bounding line in  .) Problem P2 is equivalent to: Given a constraint line set
from a TPG, determine if there exists an initial point on the x or y axis that leads to exactly one
TET such that the TET is non-blocking. If there is, output the TET.
Algorithm FindFreePoints: Let L be a set containing the lines in   and left := [(0; 0); (0; 1)]
and bottom := [(0; 0); (1; 0)]. Set G to ShootRay(L:f; \Gamma; L). If there exists a line L in   such
that G 2 f left, bottomg and G 0 =ShootRay(L:f; +; L) lies on the top or right bounding line, then
return G; G 0 ; otherwise report "no non-blocking TETs exist."
R
O
Figure

10: TPG containing an infinite number of TETs.
5 Case 2: Non-terminating Programs
The preceding algorithms cannot be used for non-terminating programs for two reasons. First,
a TPG for terminating programs is a rectangle with four finite length sides, while a TPG for
non-terminating programs extends to infinity in the Cartesian quadrant in which both axes are
positive. The unbounded nature of the TPG means that a TET will have infinite length, unless the
execution reaches a deadlock. Second, there may be an infinite set of TETs rooted at a point in
the plane (Fig. 10). This occurs when the program timings are such that in any state represented
by a point on some TET, the program will eventually reach another race condition.
Non-terminating programs whose synchronization is only for mutually exclusive resource access
(e.g., x2.2) permit a simple characterization, because they exhibit periodic behavior. The grey
lines in Fig. 6 partition the plane into a set of equal-size rectangles, in which the location of the
rectangle sides in the plane correspond to initiation of new infinite loop iterations in a process.
Each rectangle is called a quadrant. Formally defining a quadrant requires the notion of process
cycle time. Let r 2 f0; 1g denote one of two processes, and -
denote the other process
(i.e., if vice versa). The cycle time of process r, denoted OE r , is the time
required for process r to pass through each vertex in the infinite loop in its graph representation
once, ignoring the time spent blocked. Thus in Fig. 5 OE
A quadrant is a region f(G g.
The initial quadrant is the quadrant containing the origin.
Example 4 The initial quadrant in Fig. 6 has opposite vertices (0,0) and (11,11). Each quadrant
has opposite vertices
The significance of quadrants is that constraint lines in all quadrants are congruent:
Definition. For any point
G 0 are congruent, denoted G j G 0 , iff line segments are congruent if
their end points are congruent.
The fact that the placement of constraint lines in all quadrants are congruent has two impli-
cations. First, it is sufficient to analyze just one quadrant in the plane to derive the set of all
possible TETs, and this modification of the algorithms from the preceding section follows. Sec-
ond, a TET containing only deterministic points will consist of a transient portion followed by an
infinite number of repetitions of congruent subtrajectories, representing periodic behavior. (See
Theorem 1 in [3].) A repeated subtrajectory is called a limit cycle execution trajectory (LCET).
Example 5 In Fig. 11, OE 3. The TET subpath rooted at point (3; 2) in Fig. 11
consists of an infinite number of repetitions of the following LCET: a horizontal ray of length
2 and a diagonal ray whose projected length on either axis is 3. The transient TET portion is
the subpath with initial point (0,0) and final point (3,2). All instances of the LCET in the TET
are congruent. For example, two instances are [(3; 2); (5; 2)), [(5; 2); (8; 5)) and [(13; 8); (15; 8)),
10)). The two are congruent because the first and second rays of the first subtrajectory
are congruent to the first and second rays of the second subtrajectory, respectively. 2

Figure

Timed progress graph of non-terminating program that uses one semaphore.
LCETs motivate one problem in addition to P1 and P2 (x2.4), solved in this section:
P3: Find the set of all possible LCETs in a TPG that are reachable from some initial point.
Special Case TPG Definition: A TPG for a non-terminating program synchronizing only for
mutually exclusive resource access is an ordered triple h\Phi;  ; G C i specifying process cycle times,
constraint lines in the initial quadrant only, and a point representing the initial program state:
\Phi: an ordered pair of cycle times OE 0 and OE 1 satisfying OE
: a set of constraint line generators, or line segments [W; X) that lie in the initial quadrant, each
corresponding to one edge in the graph model labeled by a non-empty condition. The initial
and final points of generator [W; X) are W and X, respectively. The instances of a generator
are defined to be all lines in the R 2 plane congruent to the generator; formally, all instances
of generators in   is     def
\Lambdag.
an initial point satisfying
lies on
either the x or y axis, within one cycle time of the origin.
The TET construction rules (I and II) and the definition of transition function f given earlier
in x2.1 and x3.2, respectively, apply unaltered to a TPG h\Phi;  ; G C i.
Example 6 Figure 11 illustrates a finite portion of the TPG hfOE
A practical consideration: We henceforth assume that the execution time of each vertex in
a graph representing a program (e.g., the numbers in square brackets in Figs. 2, 5, and 8) is
an integer rather than a real number. Otherwise the computational geometric algorithms to be
presented will not work correctly with finite precision arithmetic (e.g., computation of the mod
operation is subject to roundoff error). The assumption of integer delays is not unreasonable in
practice for software performance evaluation. For example, in measurements from a computer
with a microsecond period clock and all measured times are rational numbers of the form x
Therefore scaling all measurements by the inverse of the clock period (e.g.,
yields the integer quantities required by the proposed algorithms.
5.1 Modified Algorithms to Compute
Computing f Recall from x3.2 that for a point G on a constraint line L, f o (G) is the
smallest point G 0 ? G in the set containing the final point of L and the points of intersection of
L with other constraint lines. Because   in h\Phi;  ; G C i contains only constraint lines in the initial
quadrant, we map G to a congruent point in the initial quadrant (i.e., mod(G)), then compute
as described in x4.1, and finally map each G 0 2 f back to the quadrant
containing G. Formally, we compute f
OE r
g.
Computing f d (G): The method to compute f d (G) given in x4.1 must be modified because a
non-terminating TPG has an infinite number of constraint lines in the plane. Therefore, as we

Figure

12: Illustration of using ShootRay, but only within initial quadrant.
did with f o (G), we compute f d using only the initial quadrant. We use the observation that any
diagonal ray fl in a TET can be partitioned into collinear rays
which the initial points of lie on a quadrant boundary. This fact provides an algorithm
to compute f d for each ray :i to the initial quadrant, compute
right initial quadrant edgesg), and translate G 0 back to fl k 's
quadrant to obtain fl k+1 :i. See [1] for the complete algorithm.
Example 7 In Fig. 11, f d (5; Fig. 12 shows the two ShootRay operations required
to compute f d (G) because ray (5; 2); (8; 5) lies in exactly two quadrants. Here,
5.2 P1: Finding All Possible TETs
Recall problem P1: Given a TPG h\Phi;  ; Gi, output a representation of all TETs rooted at G.
Before stating a solution, two implications of non-terminating programs must be considered: A
TET may have infinite length, and there may be an infinite number of TETs (recall Fig. 10).
For the former case (infinite length TET), the TET must consist of a transient subtrajectory
followed by an infinite number of repetitions of an LCET. Therefore our algorithm will output a
representation of the transient trajectory and the first LCET. For the later case (infinite number
of TETs), we choose an integer value maxNPaths such that if our algorithm finds more than
maxNPaths possible TETs, it assumes that there are an infinite number of TETs and terminates
without further exploration. We now generalize algorithm FindAllTETs (x4.2) to solve P1 for
non-terminating programs.
Algorithm FindAllTETs (for non-terminating programs):
1. Initialize a graph to contain one green vertex labeled by G. Set nPaths=1.
2. Set G vertex. Color G 0 red. Increment nPaths by jjf (G 0 )jj \Gamma 1.
3. For each point G 00 in f(G 0 ), create a vertex labeled by G 00 , and add a directed edge from G 0
to G 00 . If G 00 is congruent to some point P labeling a vertex in the graph path from G to
G 00 , then add an arc from G 00 to P and color vertex G 00 red; otherwise color it green.
4. If the graph contains a green vertex and nPaths- maxNPaths, then go to step 2. Otherwise
output each graph path rooted at G. Label paths containing a cycle as a transient followed
by an LCET; label the remaining paths as a transient only.
Example 8 The graph constructed by FindAllTETs for the TPG of Fig. 11 consists of an edge
from the graph vertex labeled (0,0) to the vertex labeled (2,2), an edge from (2,2) to (5,2), from
(5,2) to (8,5), and from (8,5) back to (5,2). The fact that the graph contains only one path with
one cycle means that if the both processes simultaneously start execution (i.e., the program starts
in the state represented by (0,0)), then it must reach a periodic state sequence in which process 0
blocks for two time units and then both processes run concurrently for three time units. 2
5.3 Problem P2: Deciding Existence of Non-blocking TETs
Recall problem P2: Given \Phi and   from a TPG, determine if there exists an initial point on the
x or y axis that leads to exactly one TET such that the TET is non-blocking. If there is, output
the TET.
Program termination makes only one minor difference from the algorithm given earlier
FreePoints in x 4.3): Change "lies on the top or right bounding line" to "equals (1; 1)", and
"return G; G 0 " to "return G; (1; 1)".
5.4 Problem P3: Find All Possible LCETs
We restate P3 by categorizing LCETs as blocking or non-blocking. A blocking LCET contains
a point representing a state in which some process is blocked. Geometrically, a blocking LCET
contains a horizontal or vertical ray, and a non-blocking LCET consists of a single diagonal ray.
Two TETs are homotopic if they are continuously transformable avoiding the constraint lines
(term due to Lipski and Papadimitriou [11] for paths in UPGs). For example, the TETs rooted at
all points in fG Fig. 6 all consist of one diagonal ray and are homotopic.
Problem P3: Given \Phi and   from a TPG, output one element of each equivalence class of
blocking LCETs, and one element of each set of homotopic LCETs.
Algorithm FindNonBlockingLCETs (finds all non-blocking LCETs): Initialize L as in Find-
FreePoints (x4.3). Set ;. For each L 2   do: if ShootRay(L:f; +;
non-blocking LCETs"; otherwise for each point G
output "[G; G+ (OE is a non-blocking LCET."
Consider next finding all blocking LCETs. The key insight is that a set of TETs that contains
rays that intersect a given constraint line instance, denoted L, also contain a common point that
lies on L: either a dead point, in which case the point is the final point of all the TETs, or L:f . In
the later case, this set must either have the same LCET or reach the same dead state that lies on
another constraint line instance. If they reach a LCET, it is therefore only necessary to consider
the TET rooted at L:f and determine if it contains another point congruent to L:f . Lemma 1
makes this precise.
Lemma 1 The set of all (possibly unreachable) blocking LCETs can be found by finding all L 2
and all
Proof: See Theorems 3 and 4 in [2]. 2
Let i denote the set of LCETs satisfying Lemma 1. We can determine which LCETs in i are
reachable by calculating, for each line L in an LCET in i, ShootRay(L:f; \Gamma; L), where L is the
same line set as in algorithm FindFreePoints. If the return value of ShootRay lies on the bottom
or left edge of the initial quadrant, then the LCET containing L is reachable. Therefore we propose
as a solution to P3 the exhaustive testing of all L and i, evaluating f i (L:f) as described in x5.1.
6 Relation of TPGs to Petri Nets

Figures

13(a) and 13(b) are Petri net [16] representations of Figs. 1 and 4, respectively. The
producer/consumer program in Figure 13(a) is in the Petri Net class called Deterministic Systems
of Synchronizing Processes (DSSP) [18]; the shaded place denotes a buffer shared by the two
processes. The data-base transaction program (Fig. 13(b)), however, is not in class DSSP, because
it violates the rule of a place representing a buffer being the input to at most one process. In
Fig. 13(b) the places representing semaphores as buffers are inputs to both processes. Fig. 13(b)
is a simple (or asymmetric choice) net (i.e., all arc weights are one and if two places share an
output transition then the set of output transitions of one place is either equal to or a subset of
the output transitions of the other place [16, p. 554]). Therefore the class of programs meeting
assumptions A1 through A6 is a DSSP restricted to two linear processes [23] but generalized to
omit the private-buffer assumption (i.e., Definition 2.7(ii) in [18]).
Magott [12] gives an O(N) algorithm to compute minimum cycle time (MCT), or the minimum
time required for a consistent Petri net to return to its initial marking, given deterministic firing
times for nets consisting of a set of N cyclic processes that mutually exclusively share a single
(a)
(b)
output
output
Process 1:
read send
receive write
Process 0:
Process 0:
Process 1:

Figure

13: Petri net representations of Figs. 1 and 4.
resource, and shows that finding MCT in most nets with more complex resource sharing is NP-
hard. Also proved are complexity results for systems of processes with communication by buffers.
Finally, Holliday and Vernon [9] use Petri nets with frequency expressions (i.e., probabilities)
to resolve deterministically which transition fires when a token enables two or more transitions
simultaneously, and analyze a program similar to Fig. 4.
Our TPG solution provides a fourth analysis method of one Petri net class (in addition to cov-
erability trees, matrix-equations, and decomposition techniques) for certain behavioral properties
(i.e., P1 - enumerate all possible transition firing sequences, given an initial marking) and certain
structural properties (i.e., P2 and P3).
Conclusions
We have analyzed two building blocks of interprocess synchronization: mutual exclusion and
asynchronous communication with a finite number of buffers. This paper demonstrates that
properties about the set of all possible executions of certain parallel programs can be exactly
analyzed by solving an equivalent computational geometric problem.
The analysis is limited to two processes. Extension to d processes requires ray shooting in a
d dimensional Cartesian graph with dimensional hyperplanes in a non-simple arrangement
that are bounded in one dimension. To our knowledge, this is an open computational geometric
problem, whose solution would allow solution of problems P1 and P2 for an arbitrary number of
processes. The closest problem solved in d dimensions is ray shooting with unbounded hyperplanes
that form a simple arrangement (e.g., see [14]). One limitation in d dimensions is that a progress
graph represents contention by multiple processes for a resource as a nondeterministic choice of
which process gets the resource, and does not represent different queueing disciplines.
The broader implication of this work is two open questions: Can other program visualizations
be mapped to geometric problems? Can geometry be used to analyze other Petri net classes?

Acknowledgments

D. Allison, L. Heath, D. Kafura, A. Mathur, and S. Tripathi and anonymous referees made suggestions
that improved the manuscript. C. Shaffer helped locate computational geometric algorithms.



--R

Computational geometric performance analysis of limit cycles in timed transition systems.
Geometric performance analysis of semaphore programs.
Geometric performance analysis of periodic behavior.
Visual analysis of parallel and distributed programs in the time
The influence of random delays on parallel execution times.
Intersection and Decomposition Algorithms for Planar Arrangements.
The geometry of semaphore programs.
System deadlocks.
A generalized timed Petri net model for performance analysis.
Visualizing performance debugging.
A fast algorithm for testing for safety and detecting deadlocks in locked transaction systems.
Performance evaluation of systems of cyclic processes with mutual exclusion using Petri nets.
JED: Just an event display.
On vertical ray shooting in hyperplanes.

Petri nets: Properties
Concurrency control by locking.
Deterministic buffer synchronization of sequential systems.
A declarative approach to visualizing concurrent computations.
Operations Research - Methods and Problems
Algorithms in C.
An optimal algorithm for testing for safety and detecting deadlocks in locked transaction system.
Deterministic systems of sequential processes: Theory and tools.
Locking policies: Safety and freedom from deadlock.
--TR
ray shooting;parallel computation;reachability analysis;computational geometry;visualization;mutual exclusion;performance evaluation;timed progress graphs;petri nets