Matthew I. Frank |
|
Research OverviewMost of my time for the past several years has been spent working on the Polyflow architecture. Polyflow is a dynamic dataflow machine that runs (and discovers the parallelism in) arbitrary MIPS assembly code “out of the box.” More details about the project are available on the Polyflow page. Parallelization and branch speculationOne of the central things we've learned from Polyflow is the importance of branch speculation to the parallelization process. My students originally included branch speculation in Polyflow as a way of reducing the latency of individual threads. We were surprised to discover that a more important effect came from the ability to break inter-thread data dependences that feed easy-to-predict branches. Data dependences that feed easy-to-predict branches impede conservative parallelization while more coarse-grained parallelism can be discovered if one is able to speculatively avoid waiting for the data dependences that feed easy-to-predict branches. Two of our recent papers investigate this phenomenon from different points of view.
Speculation control and efficient checkpointingWhile designing and tuning Polyflow we learned a number of important things about both speculation control and efficient checkpointing mechanisms. While branch speculation enables parallelism it is important not to speculate blindly. The Polyflow page describes mechanisms we have designed for balancing the risks and benefits of both branch speculation and memory dependence speculation. It turned out that our method of accurately estimating the confidence of a sequence of branch predictions is also applicable to improving the efficiency of traditional superscalar processors. Speculation requires checkpointing, so another thrust of our work has been into mechanisms for efficiently storing speculative state. Our work shows that, given a store-sets like synchronization mechanism, renaming mechanisms are unnecessary in the memory system. While we developed these ideas in the context of Polyflow it has, again, turned out that they have wider applicability, enabling simpler store queues in superscalar processors. Implicitly parallel programmingWe are now trying to incorporate the Polyflow insights, about branch speculation's role in parallelization, into the commercial multicore setting. As part of the Intel/Microsoft Universal Parallel Computing Research Center at Illinois, we have started building the automatic parallelizing compilers, runtime systems and libraries to leverage branch speculation in parallelization for multicores. The target of these new tools is not to support automatic parallelization of “dusty decks,” but rather to support implicitly parallel programming. An implicitly parallel program is a parallelizable algorithm expressed in a sequential programming language. In the October 2007 white paper, System Support for Implicitly Parallel Programming [pdf] I describe how branch speculation and automatic parallelization expand the scope of what can be considered a parallel loop. In a traditional explicitly parallel environment a loop is considered parallel only if has no cross-iteration dependences and a single, integer, induction variable with an invariant bound. In an implicitly parallel system loops can also contain statements with cross-iteration dependences, which the system automatically converts into sequential code that correctly interacts with any parallelizable statements in the loop. Because speculation is supported programmers can throw exceptions out of a loop, handle corner cases, use arbitrarily complex induction variables and exit conditions. More information is available on the implicitly parallel programming page. | |