The Eighteenth International Conference on
Raleigh, North Carolina. September 12-16, 2009.
Opportunistic Computing: A New Paradigm for Scalable Realism on Many-Cores
Romain Cledat and Tushar Kumar
Advisor: Santosh Pande
Georgia Institute of Technology
For a growing number of applications, 'performance' cannot be measured in terms of FLOPS but instead realism is what matters. For example, in a live video encoding application, realism translates to how well the transmitted compressed video reflects the original source. Realism by itself is also not a valid design goal. Indeed, a programmer typically tries to balance the amount of realism obtainable with the time it takes to obtain it. Furthermore, for certain applications with a high level of user-interactivity such as games, the responsiveness of an application is also an important design consideration. Therefore, the design goal for modern applications is to maximize realism under resource and responsiveness constraints. In this work, we meet this goal in two ways. Firstly, we speed-up certain sequential algorithms by exploiting the randomness in them. Indeed, launching multiple instances of such a computation in parallel can lower the expected completion time. Secondly, we utilize scalable semantics to maximize realism under constraints. We present a runtime that can dynamically adjust the complexity of scalable algorithms based on the amount of resources available. We present promising results for both techniques including super-linear speedups.