We have successfully used the logical time manipulations described here in the Belvedere animation system [7,8,10] which was specifically designed to aid in the debugging of parallel programs for correctness. Here, we demonstrate their more general application to visualizations of domain-specific data. Example 1. Sharks and Fishes [16]. For this example, we use the animation of a program that performs an underwater simulation taken from a paper on the Voyeur animation system [16]. The simulation consists of a 2D world where sharks eat fish that come too close.
Figure: Logically consecutive time steps in the lives of sharks
and fishes. Each process is labeled with its current time.
Initially, the simulation might be configured as in Figure 5a. After a single logical timestep, it might be configured as in Figure 5b where both sharks in the first row have moved into the top middle square and the shark on the right has eaten a fish. Figure 5 displays the logical timesteps for each process; it shows synchronized processes moving together from Step 1 to Step 2. If, however, the processes are not synchronized, the confusing display shown in Figure 6 might be seen. In that figure, some processes are at Step 1 while others have advanced to Step 2. The image is difficult to interpret; sharks in the top row, for example, are not displayed at all because during Step 2 they have moved to processes still displayed at Step 1. The problem is not in the code but in its visualization.
Figure: Actual execution of the sharks and fishes program.
Processes are executing at different time steps concurrently.
Existing animation tools solve this problem by requiring the programmer to explicitly simulate a global or real world time. Each process must output clock ``ticks'' and all of the data produced between successive ticks is displayed at the same time. This simulated time has been called ``phase time'' [13] or ``generation'' time [16] and it works well for SPMD (Single Program Multiple Data) programs where all processes proceed in unison. It does not work well for less regular programs in which processes independently update data at different points in their execution. In these programs, processes that are not involved in an update do not have any way of knowing that time should be advanced. Examples of programs that do not proceed in unison include the dictionary search discussed above and the FIFO queue discussed below.
With our techniques, the user defines abstract events composed of single updates to shark and fish positions on all processes. These abstract events are ordered by precedes and, thus, they are automatically separated to produce the desired animation (as shown in Figure 5).
Example 2. Recursive Matrix Transposition.
In this example, we consider the animation of a program that performs a recursive
matrix transposition as shown in [5]. Starting with the matrix as displayed in
Figure 7, we successively transpose submatrices of
sizes 
, 
and 
. A visualization in
which processes asynchronously update the display as they compute
produces the incomprehensible snapshots of Figure 8.
Figure: Snapshot from of the matrix before transposition.
Using our techniques, abstract events corresponding to the recursion levels are shown in a logically coherent manner as in Figure 9. This enhanced visualization is considerably easier to understand than the original.
Figure: Snapshots from the original animation of the
recursive transposition program.
Figure: Snapshots from the enhanced animation of the
recursive transposition program showing the matrix after the
transposition of 
, 
and 
submatrices.
It should be noted that for this algorithm, where all processes recurse to the same depth, the use of phase time or generation time would also suffice. If, however, the depth of recursion was not uniform as, for example, in a binary search, then only our techniques would produce coherent pictures. In the next example, we demonstrate a program that cannot be successfully animated with phase or generation time alone.
Example 3. Parallel FIFO Queue [4]. Here,
we discuss an animation of a parallel queue
but the scenario is typical of many simulations that model
concurrent, nonatomic updates of data.
Figure 10a shows an empty circular queue. Each trapezoid represents a location in the queue; the head pointer is labeled I and the tail pointer is labeled D. In Figures 10b and c, we use a solid trapezoid below the queue to indicate that an Insert is in progress and a blank trapezoid above the queue to indicate that a Delete is in progress. . Note that Figure 10 shows both an Insert and a Delete in progress at the same location but this does not indicate an error.
Figure: Snapshots from the animation of the parallel queue.
Neither Inserts nor Deletes are atomic. A Delete takes three steps: first it gets the position of the next queue element, then it waits until any Inserts on that location have completed, and then it removes the element. Its start can legitimately overlap with the previous Insert. Figure 10d shows several Inserts and Deletes in progress; shaded queue locations are full. All of these pictures show the queue behaving as expected. But what if there is an error?
Suppose that the wait is omitted during Deletes so that it is possible for them to access the queue before data has been inserted. Figure 11 shows snapshots from the animation of an execution sequence in which this actually occurred. It looks as if the first Insert has completed and the first Delete is still in progress. Why doesn't the error show up?
Figure: Snapshots from the original animation of an
erroneous version of the parallel queue.
The problem is in the timing of the screen updates. In this trace, the Delete accessed the queue first but the sequence of operations that made up the Insert finished before the sequence of operations that made up the Delete. The screen was updated as the sequences completed and, thus, it showed the Insert first, masking the error. Using logical time, however, this anomaly does not occur. Figure 12, for example, shows the same execution trace animated with our techniques. Inserts and Deletes were treated as abstract events and they were ordered logically by the dependencies caused by queue accesses (dependencies resulting from the process waits were ignored). The error is clearly visible.
Figure: Snapshots from the logically ordered animation of
the erroneous version of the parallel
queue.
This scenario is typical of simulations in which different parts of a data structure are concurrently updated by nonatomic operations. Simulated global time is not useful because not all processes participate in each update and, thus, not all processes are aware of the need to advance their clocks. Our techniques allow the user to focus on just those temporal orderings that are relevant to the logical behavior under investigation. They also allow the user to change that focus as different aspects of the behavior come under scrutiny.