Geometric Performance Analysis of Semaphore Programs

Files
TR Number
TR-93-29
Date
1993-08-01
Journal Title
Journal ISSN
Volume Title
Publisher
Department of Computer Science, Virginia Polytechnic Institute & State University
Abstract

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.

Description
Keywords
Citation