This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5). The research funded by this award targets the difficult problem of how to debug programs running on large parallel systems. The state of hundreds to hundreds of thousands of parallel tasks that form a single computation are too complicated for a programmer to usefully analyze. This project will develop tools to find similarities between the state of different processes, simplifying the task of the programmer. The challenge in finding these similar tasks is to do it efficiently, without imposing an overhead so hight that the tool is useless. A naive implementation would compare the state of all processors against one another, and would introduce overheads increasing as the square of the number of processors. Our approach will successively refine sets of similar processes, will use key attributes of program behavior (e.g. communication patterns) to perform this grouping. We will also investigate the use these groups of similar processes to allow invariance and statistically based techniques developed for sequential programs (such as value and PC invariance) to be effectively adapted to parallel programs. Because these techniques look for rarely occurring program activities, applying them to disparate processes together will introduce noise into the analysis, severely diminishing their accuracy. The use of our grouping strategy will allow effective parallelization of the techniques, allowing them to be applied with significantly less overhead than when used with sequential applications.
