Programming Model and Software System for Exploiting Parallelism in Irregular Programs

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 U.S. patent application filed

UT Researcher Keshav Pingali, Sc.D., Computer Sciences, The University of Texas at Austin Milind Kulkarni, Computer Sciences, The University of Texas at Austin

Type of Offer: Licensing



« More Computer Science Patents

---