Wisconsin Alumni Research Foundation

Information Technology
Information Technology
Data Flow Execution of Methods in Sequential Programs
WARF: P07057US

Inventors: Gurindar Sohi, Saisanthosh Balakrishnan

The Wisconsin Alumni Research Foundation (WARF) is seeking commercial partners interested in developing an automated method of parallelizing the execution of a sequential computer program for multiple processors.
Overview
To improve the speed of a computer program, computer systems run instructions from a program in parallel, but maintain the effect of running these instructions one after another. Systems with multiple processors can further increase the speed by running instructions in parallel on different processors. However, as more instructions are run in parallel, problems can result when instructions are run before the data they rely on is produced.
The Invention
UW-Madison researchers have developed an automated way to parallelize the execution of a sequential computer program for multiple processors. Programmers usually write computer programs by dividing them into methods, which consist of one or more instructions that collectively perform a specific subtask of the program. Programmers write programs with “calls” to the methods when they need to perform that subtask and continue writing the rest of the program. The instructions in a method can access memory values of the program, and may be provided with some input values, which could be used to specialize the instructions of the method.

In this invention, a trigger is specified for a method when memory and input values are assumed to be available, and the method begins running on a different processor. This trigger usually occurs before the call to that method is reached in the program. Therefore, the method is run in parallel with the program. If the memory and input values have not changed when the method call is reached, results of the instructions in the method are used without running the method again.
Applications
  • Computer systems with multiple processors
Key Benefits
  • Simplifies parallelization of sequential programs
  • Allows the use of standard programming tools in parallelized programs
  • Executes current programs efficiently in multiple processor systems
  • Parallelizes the execution of methods—also called functions or sub-routines—in a program
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

WARF