New Prediction Paradigms for Parallel and Distributed Systems

North Carolina State University, Raleigh NC

Investigators

Abstract

This research aims to expand and redefine the role of prediction-based techniques for parallel and distributed systems. First, we reduce barrier synchronization overhead by predicting the final producer of a value before the barrier. This producer identification allows the consumer to speculatively proceed past the barrier, only waiting on the actual production as needed. Second, we introduce the slipstream paradigm to multiprocessor systems. A redundant version of each parallel thread runs concurrently, its execution reduced by speculatively removing long-latency events, such as shared memory writes. The reduced thread dynamically detects sharing patterns, which are used by the original thread to optimize its coherence and synchronization actions, improving overall performance. Finally, we investigate the use of producer-validated message prediction to reduce traffic in a message-passing environment. Both the producer and the consumer of a message predict its contents, using redundant prediction histories. Since the producer knows the results of the consumer's prediction, it need only send those data that were not correctly predicted. This traffic reduction is significant in environments in which communication is much more costly than computation, such as networked embedded systems. These three avenues of research represent an excursion into new frontiers of prediction-based technology, resulting in parallel systems that scale to new levels of availability and performance.