The Concurrent Graph: Basic Technology for Irregular Problems

This paper describes basic programming technology to support irregular applications on scalable concurrent hardware and shows how the technology has been applied to a variety of large-scale industrial application problems. The technology is based on the concept of a concurrent graph library that provides an adaptive collection of light-weight threads that may relocate between computers dynamically. The graph is portable to a wide range of highperformance multicomputers, shared-memory multiprocessors, and networked workstations. For each machine it is optimized to take advantage of the best available underlying communication and synchronization mechanisms. The graph provides a framework for adaptive refinement of computations, automatic load balancing, and interactive, on-the-fly visualization. It has been applied to a variety of large scale irregular applications to provide portable, scalable implementations with substantial code reuse. The applications described in this article typify..