Uniparallel Execution and its Uses.

Operating Systems;Multicore and Multiprocessor Systems;Reliability;Deterministic Replay;Data Race Detection;Data Race Survival;Computer Science;Engineering;Computer Science & Engineering

Veeraraghavan, KaushikNoble, Brian D. ;

University of Michigan

关键词: Operating Systems;    Multicore and Multiprocessor Systems;    Reliability;    Deterministic Replay;    Data Race Detection;    Data Race Survival;    Computer Science;    Engineering;    Computer Science & Engineering;   

Others  :  https://deepblue.lib.umich.edu/bitstream/handle/2027.42/89677/kaushikv_1.pdf?sequence=1&isAllowed=y

瑞士|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

We introduce uniparallelism: a new style of execution that allowsmultithreaded applications to benefit from the simplicity ofuniprocessor execution while scaling performance with increasingprocessors.A uniparallel execution consists of a thread-parallel execution, whereeach thread runs on its own processor, and an epoch-parallelexecution, where multiple time intervals (epochs) of the program runconcurrently.The epoch-parallel execution runs all threads of agiven epoch on a single processor; this enables the use of techniquesthat are effective on a uniprocessor.To scale performance withincreasing cores, a thread-parallel execution runs ahead of theepoch-parallel execution and generates speculative checkpoints fromwhich to start future epochs.If these checkpoints match the programstate produced by the epoch-parallel execution at the end of eachepoch, the speculation is committed and output externalized; if theymismatch, recovery can be safely initiated as no speculative state hasbeen externalized.We use uniparallelism to build two novel systems: DoublePlay andFrost.DoublePlay benefits from the efficiency of logging theepoch-parallel execution (as threads in an epoch are constrained to asingle processor, only infrequent thread context-switches need to belogged to recreate the order of shared-memory accesses), allowing itto outperform all prior systems that guarantee deterministic replay oncommodity multiprocessors.While traditional methods detect data races by analyzing the eventsexecuted by a program, Frost introduces a new, substantially fastermethod called outcome-based race detection to detect the effects of adata race by comparing the program state of replicas for divergences.Unlike DoublePlay, which runs a single epoch-parallel execution of theprogram, Frost runs multiple epoch-parallel replicas withcomplementary schedules, which are a set of thread schedules craftedto ensure that replicas diverge only if a data race occurs and to makeit very likely that harmful data races cause divergences.Frostdetects divergences by comparing the outputs and memory states ofreplicas at the end of each epoch.Upon detecting a divergence, Frostanalyzes the replica outcomes to diagnose the data race bug andselects an appropriate recovery strategy that masks the failure.