Center for Distributed and Grid Computing
The Center for Grid and Distributed Computing (CDGC) works on automatic techniques for enhancing the efficiency and survivability of software systems. The goal is to raise the level of abstraction at which applications programmers write software, while ensuring that there is no substantial loss of efficiency or robustness of applications code. Techniques being investigated range from optimizing and restructuring compilation technology for multicore processors to protocols for fault-tolerant computing systems.
Research at the Center is conducted in collaboration with other ICES centers, the Departments of Computer Science and Electrical and Computer Engineering at The University of Texas at Austin, and with several other universities and national laboratories including Cornell University, the University of Illinois at Urbana-Champaign, the University of Padova in Italy, the University of Delaware and Lawrence Livermore Laboratories. Industrial collaborators include Intel, IBM, and Hewlett-Packard.
Currently, a major research theme in the Center is the exploitation of data-parallelism in "irregular" programs that manipulate complex data structures such as trees and graphs. Data-parallelism in regular programs that manipulate arrays is well understood, and is exploited routinely in parallel programming; for example, if a program multiplies two matrices, the rows of the first matrix can be multiplied by the second matrix in parallel. Data-parallelism in irregular programs is less well understood. Research performed at the Center has shown that irregular data-parallelism manifests itself in work-list based algorithms that perform computations on elements of sorted or unsorted work-lists, and that this parallelism can be exploited using optimistic parallelization techniques.
Examples of such algorithms include Delaunay mesh generation and refinement, data-mining algorithms for clustering, algorithms for maxflow such as the Ford-Fulkerson algorithm and the Goldberg-Tarjan preflow-push, and approximate SAT solvers. The Center is investigating language constructs, compiler technology and runtime systems for exploiting this kind of irregular data-parallelism. Grants from the National Science Foundation, IBM and Intel support this work.