Geometric Performance Analysis of Semaphore Programs

A key problem in designing parallel programs that achieve a desired performance goal is the ability to analyze exactly program performance, given a specification of the process syncronization structure and the execution timings of all code segments. The problem solved in this paper is to derive, for all possible process starting times, the set of all possible limit cycle execution sequences in which a process blocks. This paper makes two contributions. First, it employs a novel analysis method that derives timed execution sequences from a geometric model of program execution, called timed progress graphs. Second, it solves the timed progress graph not by a computational geometric algorithm, as employed by most solutions in the literature to untimed progress graphs, but by an analytic solution.