Geometric Performance Analysis of Periodic Behavior in Detail

A fundamental problem in designing parallel programs that achieve a desired performance goal is the ability to exactly analyze program performance, given a specification of the process synchronization structure and the execution timings of all code segments. This paper presents a novel performance analysis method based on geometry. Given a definition of program state, an execution of a program can be represented by a timed execution sequence (TES). A TES is a sequence of states that the program passes through in an execution, along with the duration of time spent in each state. In some parallel programs, all TESs that can arise in any execution contain a suffix that consists of the repetition of a finite sequence of states, excluding deadlocks and nondeterministic behavior. The repeated sequence is termed the limit cycle execution sequence. This paper derives, for all possible process starting times, a representation of the set of all possible limit cycle execution sequences in which a process blocks. The paper makes two contributions. First, it employs a novel analysis method to derive TESs from a geometric program execution model, using timed progress graphs (TPGs). TPGs represent the progress of each process by an axis in a Cartesian graph; process synchronization by line segments; and a TES by a direct, continuous path that does not cross a segment. Second, it solves for TESs in TPGs not by a computational geometric algorithm, as employed by most solutions in the literature to (untimed) progress graphs, but by an analytic solution.