Apr 5, 2007: Speculative Tasking: A Versatile Primitive to Improve Performance
Filed in: Colloquium
James Tuck, University of Illinois at
Urbana-Champaign
Improving single-thread performance is a major challenge for computer architects. The two main reasons for it are the shift to multi-core architectures, which will no longer emphasize improvements in instruction-level parallelism, and the long memory latencies. A versatile primitive for overcoming these obstacles is Speculative Tasking. With Speculative Tasking, the outcome of a long or risky operation is assumed to be known, thereby allowing the execution of the following code section --- potentially in parallel ---by taking a hardware checkpoint and buffering the speculative state. Later, if it turns out that the assumption was incorrect, the hardware rolls back the whole section to the checkpoint and re-executes it transparently.
In this talk, I will present two uses of Speculative Tasking to overcome the obstacles stated above. The first use is in speculative parallelization, where a sequential application is automatically divided into multiple tasks that are executed in parallel. In particular, I will focus on the experimental POSH compiler for speculative parallelization that I developed. POSH uses code structures such as loops and subroutines, includes a profiler pass that discards ineffective tasks, and directly leverages prefetching in speculative tasks. The second use of Speculative Tasking is in boosting memory-level parallelism (MLP) within a thread. By allowing the processor to speculate past cache misses, many additional cache misses are overlapped. I will focus on a novel memory hierarchy design for this support.
James Tuck is a Ph.D. candidate in the Department of Computer Science at the University of Illinois at Urbana-Champaign (UIUC). His doctoral research has focused on computer architectures and compilation techniques for Speculative Tasking. James has coauthored over ten papers in this area. He received his B.E. summa cum laude in Computer Engineering from Vanderbilt University and his M.S. in Electrical and Computer Engineering from UIUC.
Abstract
Improving single-thread performance is a major challenge for computer architects. The two main reasons for it are the shift to multi-core architectures, which will no longer emphasize improvements in instruction-level parallelism, and the long memory latencies. A versatile primitive for overcoming these obstacles is Speculative Tasking. With Speculative Tasking, the outcome of a long or risky operation is assumed to be known, thereby allowing the execution of the following code section --- potentially in parallel ---by taking a hardware checkpoint and buffering the speculative state. Later, if it turns out that the assumption was incorrect, the hardware rolls back the whole section to the checkpoint and re-executes it transparently.
In this talk, I will present two uses of Speculative Tasking to overcome the obstacles stated above. The first use is in speculative parallelization, where a sequential application is automatically divided into multiple tasks that are executed in parallel. In particular, I will focus on the experimental POSH compiler for speculative parallelization that I developed. POSH uses code structures such as loops and subroutines, includes a profiler pass that discards ineffective tasks, and directly leverages prefetching in speculative tasks. The second use of Speculative Tasking is in boosting memory-level parallelism (MLP) within a thread. By allowing the processor to speculate past cache misses, many additional cache misses are overlapped. I will focus on a novel memory hierarchy design for this support.
Bio
James Tuck is a Ph.D. candidate in the Department of Computer Science at the University of Illinois at Urbana-Champaign (UIUC). His doctoral research has focused on computer architectures and compilation techniques for Speculative Tasking. James has coauthored over ten papers in this area. He received his B.E. summa cum laude in Computer Engineering from Vanderbilt University and his M.S. in Electrical and Computer Engineering from UIUC.