Technologies
PDF


WARF: P02186US

Method and Device for Parallel Execution of Computer Software Using a Distilled Program


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.
OVERVIEWTo 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 INVENTIONUW-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.
APPLICATIONS
  • 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
Contact Information
For current licensing status, please contact Emily Bauer at emily@warf.org or 608-960-9842.
The WARF Advantage

Since its founding in 1925 as the patenting and licensing organization for the University of Wisconsin-Madison, WARF has been working with business and industry to transform university research into products that benefit society. WARF intellectual property managers and licensing staff members are leaders in the field of university-based technology transfer. They are familiar with the intricacies of patenting, have worked with researchers in relevant disciplines, understand industries and markets, and have negotiated innovative licensing strategies to meet the individual needs of business clients.