The objective of this RUI project is to design ``smarter` algorithms that avoid memory access conflicts without significant slowdown of an algorithm's performance. In particular, this research focuses on designing such algorithms (especially for graph problems), studying their characteristics, developing methodologies, and evaluating the gains from removal of concurrent memory access. The methods studied which, when carefully employed by a parallel algorithm, avoid concurrent memory access. Methods, which have been shown to be effective on parallel graph algorithms and which are also being investigated, include: (1) pseudotree contraction, a set of rules that allows a pseudotree to be contracted to a rooted star in logarithmic time without concurrent-writing access; (2) edge-list augmentation, a procedure that runs in constant time without any concurrent memory access; (3) growth-control scheduling, a method of balancing the work performed by clusters of processors so that the total amount of time needed to finish a job is minimized.
