Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


ucin1171055502.pdf (715.74 KB)

ETD Abstract Container

Abstract Header

Causality Representation and Time Warp Optimizations

Chetlur, Malolan
http://rave.ohiolink.edu/etdc/view?acc_num=ucin1171055502

Abstract Details

2007, PhD, University of Cincinnati, Engineering : Computer Science and Engineering.
Time Warp optimistic protocols are exposed to performance degrading cascading rollbacks. In addition, optimistic simulation has the potential to reach an inconsistent state due to lagging rollbacks, thereby resulting in system failures. These issues are due to short-sighted reactive measures employed during the rollback process. The above mentioned risks can be avoided with the knowledge of causality. This study presents new optimizations that exploit additional knowledge gleaned from causality information in Time Warp simulations. The causality relation among events is captured and disseminated by a logical clock framework and this information is exploited in optimizations. This thesis explores causal dissemination frameworks and optimizations using these frameworks. First, a theoretical logical clock framework named Total Clocks (TC) is presented. This framework captures and disseminates strong causality relation among events in virtual time paradigm. The detailed clock update rules and the properties of TC are established. The utility of this framework is demonstrated with the design of a distributed cancellation technique to avoid cascading and inter-related rollbacks. In addition, a proof of correctness of this cancellation technique is presented. The TC framework is not scalable and therefore, this study address its scalability issues with the design of Plausible Total Clocks (PTC). The PTC is a constant size clock capturing weak causality relation among events and its size is independent of the number of simulation objects. A proactive cancellation mechanism using the PTC framework to detect and avoid cascading rollbacks and a proof of correctness of this technique are presented. In addition, this proactive cancellation mechanism is implemented in the WARPED simulation kernel. Empirical results of this implementation running on 32 processors show a performance improvement between 10% - 15% for simulations exhibiting cascading rollbacks. To further demonstrate the utility of causal dissemination framework, two new Time Warp optimizations exploiting causality are presented. The first optimization is a fossil identification technique that is independent of GVT. A proof of correctness of this new fossil collection technique is presented. The second optimization is a causality based scheduling mechanism and this scheduling mechanism running on 32 processors show a performance improvement between 10% - 15%.
Dr. Philip Wilsey (Advisor)
146 p.
Computer Science
Time Warp; Logical Time; Plausible Clocks

Recommended Citations

Citations

  • Chetlur, M. (2007). Causality Representation and Time Warp Optimizations [Doctoral dissertation, University of Cincinnati]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1171055502

    APA Style (7th edition)

  • Chetlur, Malolan. Causality Representation and Time Warp Optimizations. 2007. University of Cincinnati, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=ucin1171055502.

    MLA Style (8th edition)

  • Chetlur, Malolan. "Causality Representation and Time Warp Optimizations." Doctoral dissertation, University of Cincinnati, 2007. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1171055502

    Chicago Manual of Style (17th edition)

ucin1171055502
413
© 2007, all rights reserved.
This open access ETD is published by University of Cincinnati and OhioLINK.