Stanford Seminar - Time Traveling Hardware and Software Systems

This seminar introduces physiological time, which combines physical and logical time to enable memory operations to move across time and reduce conflicts. It examines the Tardis cache coherence protocol for multicore CPUs and the TicToc concurrency control algorithm for online transaction processing databases.

Syllabus

Introduction.
TECHNOLOGY SCALING.
DIFFERENT KINDS OF PARALLELISM - 1.
DIFFERENT KINDS OF PARALLELISM - 2.
DEPENDENCY DESTROYS PARALLELISM.
DIFFERENT KINDS OF DEPENDENCY.
DEPENDENCE IS ACROSS TIME, BUT WHAT IS TIME?.
WAR DEPENDENCE Initially A = 10.
WHAT IS CORRECTNESS?.
SEQUENTIAL CONSISTENCY.
AVOIDING DEPENDENCY ACROSS THE STACK.
SHARED MEMORY SYSTEMS.
DIRECTORY-BASED COHERENCE.
CACHE COHERENCE SCALABILITY.
LEASE-BASED COHERENCE.
LOGICAL TIMESTAMP.
TWO-CORE EXAMPLE.
STORE A @ CORE O.
LOAD B @ CORE O.
STORE B @ CORE 1.
TWO VERSIONS COEXIST.
LOAD A @ CORE 1.
SUMMARY OF EXAMPLE Directory.
TARDIS PROS AND CONS.
CONCURRENCY CONTROL.
BOTTLENECK 1: TIMESTAMP ALLOCATION.
BOTTLENECK 2: STATIC ASSIGNMENT.
KEY IDEA: DATA DRIVEN TIMESTAMP MANAGEMENT.
TicToc TRANSACTION EXECUTION.
LOAD A FROM T1 2.
COMMIT PHASE OF T1.
FINAL STATE.
PHYSIOLOGICAL TIME ACROSS THE STACK.