With the imminent demise of Moore's Law, the importance of parallel computing is only increasing. However, efficient parallel computing with ease of programmability still remains elusive. Shared memory multiprocessors and online Transaction processing systems make it easier on the programmer. Current systems either exclusively use physical time to order transactions, or logical time (e.g., Lamport clocks) and are limited in performance and/or scalability.
We introduce a new concept of time called physi-logical (physiological for ease of pronunciation!) time that combines the strengths of physical and logical time while avoiding their problems. The key advantage of physiological time is that it enables an application to move memory operations (load/stores) forward and backwards in time in order to avoid conflicts. We have designed, implemented and evaluated two time-traveling systems in the form of a new cache coherence protocol Tardis for multi-core CPUs and a new concurrency control algorithm TicToc for on-line transaction processing database systems. Both algorithms are simpler, more scalable, and perform better than existing state-of-the-art implementations. The talk will end with describing how physiological time can be used in a distributed operating environment.
Joint work with Xiangyao Yu, Andy Pavlo and Daniel Sanchez.
The Stanford EE Computer Systems Colloquium (EE380) meets on Wednesdays 4:30-5:45 throughout the academic year. Talks are given before a live audience in Room B03 in the basement of the Gates Computer Science Building on the Stanford Campus. The live talks (and the videos hosted at Stanford and on YouTube) are open to the public.
Srini Devadas is the Webster Professor of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology (MIT). He received his MS and PhD from the University of California, Berkeley in 1986 and 1988, respectively. He joined MIT in 1988 and served as Associate Head of the Department of Electrical Engineering and Computer Science, with responsibility for Computer Science, from 2005 to 2011. Devadas's research interests span Computer-Aided Design (CAD), computer security and computer architecture and he has received significant awards in each discipline including the A. Richard Newton Technical Impact award and the IEEE Computer Society Technical Achievement award. He is a Fellow of IEEE and ACM. He is a MacVicar Faculty Fellow and an Everett Moore Baker teaching award recipient, considered MIT's two highest undergraduate teaching honors.