Programming Model and Software System for Exploiting Parallelism in Irregular Programs

Project ID: 1665-AP
Available for licensing

Background

Irregular programs deal with pointer-based data structures like large graphs and trees. It is well known that it is difficult to exploit parallelism in these programs. We have developed a programming model and an associated software system that make it much easier to exploit parallelism in irregular programs on multicore processors.

Invention Description

The programming model provides two constructs called optimistic iterators that programmers use to highlight opportunities for exploiting generalized data-parallelism, a form of parallelism that is ubiquitous in irregular programs. When the program is executed, the associated software system uses speculative parallelism to execute these iterators in parallel. The programming model also permits programmers to specify semantic information about classes in class libraries that is useful for exploiting parallelism.

Benefits

Approach permits irregular applications in object-oriented languages like C++ and Java to be executed in parallel on multicore processors without requiring the entire application to be rewritten in a new language.
Programs can be incrementally modified to use the optimistic set iterators to highlight opportunities for exploiting generalized data parallelism.
Semantic information can be added incrementally to classes when this information is useful for exploiting parallelism.

Market Potential/Applications

The class of programs that can benefit from this programming model and associated software system is very large; for example, mesh generators, which are used extensively in finite-element methods and in graphics; many data-mining applications; and many computational biology applications

Development Stage

Lab/bench prototype

IP Status

One PCT patent application filed

UT Researcher

Keshav Pingali, Ph.D., Computer Sciences, The University of Texas at Austin
Milind Kulkarni, Computer Sciences, The University of Texas at Austin

OTC Contact Information

Jitendra Jain, Licensing Specialist
jjain@otc.utexas.edu
512-471-9055

Web Links

http://portal.acm.org/citation.cfm?id=1250759