Wisconsin Alumni Research Foundation

Information Technology
Information Technology
Method and Device for Parallel Execution of Computer Software Using a Distilled Program
WARF: P02186US

Inventors: Gurindar Sohi, Craig Zilles

The Wisconsin Alumni Research Foundation (WARF) is seeking commercial partners interested in developing a sophisticated new model to achieve parallel processing of computer programs through speculation.
To achieve faster processing rates, computational tasks can be divided between several processors, a technique called thread-level parallel processing. However, manual parallelization of programs can be error-prone and costly, and automatic parallelization appears to be intractable for many programs.
The Invention
UW-Madison researchers have developed a sophisticated new model to achieve parallel processing of computer programs through speculation. The technique employs a speculative approximation of an original program, called a distilled program, which makes predictions about control and data flow to break dependencies that would otherwise serialize execution.

More specifically, a computer program is monitored to identify predictable, recurring behaviors, and a simpler, “distilled” version is created by assuming that these behaviors continue to repeat. The distilled version executes faster than the original program, but with no guarantee of accuracy. As the distilled program runs, it forwards starting points and other necessary data to secondary processors, which carry out the portions of the original program corresponding to each checkpoint. As the secondary processors finish their tasks, their state data are used to verify the state data assumptions of the distilled version. If mistakes are found, the speculative execution can be stopped and program execution restarted from the last checkpoint.
  • Parallelization of computer programs
Key Benefits
  • Improves speed and performance of current computer programs by parallelizing their execution
  • Program parallelization does not require programmer intervention.
  • Could allow automatic parallelization of serial computer programs as they are executed [potentially on existing (legacy) executables]
  • Reduces verification complexity by separating portions of software and hardware responsible for correctness from those responsible for performance
  • Uses program optimization and speculation methods derived from standard techniques to create a distilled program that closely matches the original
Additional Information
For More Information About the Inventors
For current licensing status, please contact Emily Bauer at [javascript protected email address] or 608-960-9842