Programming models for speculative and optimistic parallelism based on algorithmic properties
Santosh Pande, Romain E. Cledat · 2011
Whereas earlier generations of computers were resource-scarce, modern multi-core and many-core machines are resource-rich. Historically, software optimizations were geared towards “fitting” the computation inside scarce resources whereas modern multi-core machines face the dual problem of idling resources on the one hand and sequential bottlenecks on the other. The opportunistic computing paradigm, on which this thesis rests, is the idea that the computation (sequential or otherwise) should dynamically scale to occupy idling resources to enhance its speed or quality thereby solving both problems. This thesis focuses specifically on hard to parallelize computations which cannot easily scale to occupy more and more resources. We have observed that traditional data and task parallelism do not allow these types of computations to scale as this type of parallelism is either hard to express (for algorithms that have unstructured memory access patterns for example) or does not exist (for purely sequential computations). We instead propose to exploit the algorithmic properties of a computation to develop programming models that utilizes parallel resources to improve performance or quality for hard to parallelize computations. Specifically, this thesis looks at three distinct algorithmic properties: (i) algorithmic diversity, (ii) the semantic content of data-structures, and (iii) the variable nature of results in certain computations. Our first contribution is the N-way programming model which exploits algorithmic diversity to opportunistically speed-up or improve the quality of a computation. The N-way model is specifically tailored for sequential computations, providing speedup for such computations and thereby providing a solution to the bottleneck expressed in Amdahl's law. The N-way model relies on the fact that for many problems, multiple ways exist to solve them, each potentially differing in their expected completion time, resource requirement or quality of result. An intuitive example of algorithmic diversity is a randomized algorithm: each launch of the algorithm on a given input will behave differently. The N-way model launches multiple competing ways performing the same computation and picking the best one (fastest or best quality) just in time. The more diversity exists in a problem, the greater the speedup or QoR improvement potential is. It is important to note that the amount of diversity in a problem is not dependent on the sequential or parallel nature of the algorithm used to solve the problem; in other words, N-way parallelism is equally applicable to parallel and sequential codes. This thesis also develops ways to minimize the number of ways launched (n) while maximizing the probability of improvement. Indeed, the N-way model can be very wasteful as only one of the ways ends up successfully “committing” its result. The N-way system attempts to solve this problem by developing (i) a statistical learning approach which estimates the benefit of different amounts of speculation and (ii) a mechanism to reclaim unproductive ways to further reduce n during execution of the competing ways. Both these techniques allow N-way to maximize the benefit obtained while minimizing the amount of resources required. Through the use of N-way model, we show very high (super-linear) speedups on hard to parallelize combinatorial problems such as SAT solving. Our second contribution is an extension of the N-way model allowing for additive semantics instead of purely competing semantics: optional additional ways can be used to improve the quality of result in a main thread when they are joined back into it. Indeed, for many applications, particularly in the gaming and multimedia domain, multiple results are “correct” although some are better than others in terms of quality. Additional, quality enhancing ways, can therefore be launched and, if time and resource permits it, their results can be merged back into a main thread. Finally, we present a framework to improve optimistic parallelism by leveraging the semantics of data-structures and algorithmic properties to dynamically predict conflicts and reduce the overhead of optimistic parallelism such as Software Transactional Memories (STMs). Indeed, while optimistic parallelism techniques have been shown to be beneficial in writing parallel versions of hard to parallelize algorithms (such as algorithms relying on sparse and irregular data-structures with hard to discern patterns), the overhead of wrong predictions can be very high. The technique we present allows the programmer to specify semantics information concerning the data-structures with the help of predicates that can guide an optimistic runtime in making the correct decisions to minimize wrong predictions. We further develop a profiling-based approach to automatically determine the symbolic data footprint of a transaction which permits the automatic generation of conflict prediction functions.