Show simple item record

dc.contributor.advisor Zwaenepoel, Willy
dc.creatorBubenik, Richard G.
dc.date.accessioned 2009-06-04T00:21:55Z
dc.date.available 2009-06-04T00:21:55Z
dc.date.issued 1990
dc.identifier.urihttps://hdl.handle.net/1911/16322
dc.description.abstract An optimistic computation is a computation that makes guesses about its future behavior, then proceeds with execution based on these guesses before they can be verified. Optimistic computations guess data values before they are produced and guess the control flow of computations before it is known. The performance of optimistic computations is determined by the number of idle resources available for optimistic execution, the percentage of guesses that are correct, the bookkeeping costs of managing optimistic execution, and the overhead of preventing optimistic computations from interfering with their execution environments until the guesses that they are based on are verified. We model computations by their program dependence graphs, then present a series of application-independent transformations on the dependence graphs that convert pessimistic computations into semantically equivalent optimistic computations. We demonstrate the viability of this approach by applying our transformations to the make program, fault tolerance based on message logging and checkpointing, distributed simulation, database concurrency control, and bulk data transfer. Our derived optimistic computations are similar to those presented in the literature, but typically require additional application-dependent transformations to produce viable implementations. We investigate, in detail, the implementation and performance of optimistic make, an optimistic variant of conventional pessimistic make. Optimistic make executes the commands necessary to bring makefile targets up-to-date prior to the time the user types a make request. The side effects produced by these optimistically executed commands are masked using encapsulations until the commands are known to be needed, at which time the side effects are committed to the external world. The side effects of unneeded commands and commands executed with inputs that have changed are discarded. Measured and simulated results from our implementation of optimistic make show a median response time improvement of 1.72 and a mean improvement of 8.28 over pessimistic make.
dc.format.extent 144 p.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.subjectComputer science
dc.title Optimistic computation
dc.type.genre Thesis
dc.type.material Text
thesis.degree.department Computer Science
thesis.degree.discipline Engineering
thesis.degree.grantor Rice University
thesis.degree.level Doctoral
thesis.degree.name Doctor of Philosophy
dc.identifier.citation Bubenik, Richard G.. "Optimistic computation." (1990) Diss., Rice University. https://hdl.handle.net/1911/16322.


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record