Show simple item record

dc.date.accessioned2013-06-19T14:35:40Z
dc.date.available2013-06-19T14:35:40Z
dc.date.issued1995-09-01
dc.identifierhttp://eprints.cs.vt.edu/archive/00000430/en_US
dc.identifier.urihttp://hdl.handle.net/10919/19923
dc.description.abstractA 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.en_US
dc.format.mimetypeapplication/postscripten_US
dc.publisherDepartment of Computer Science, Virginia Polytechnic Institute & State Universityen_US
dc.relation.ispartofHistorical Collection(Till Dec 2001)en_US
dc.titleGeometric Performance Analysis of Periodic Behavior in Detailen_US
dc.typeTechnical reporten_US
dc.identifier.trnumberTR-95-15en_US
dc.type.dcmitypeTexten_US
dc.identifier.sourceurlhttp://eprints.cs.vt.edu/archive/00000430/01/TR-95-15.ps


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record