Societies are defined by their dependencies - social, economic, governmental, and personal. Data intensive applications focused on relationships across these dependencies are distinct from scientific computations. Further, within the sciences, the processing of relationships represented as graph structures is forming an important subset of scientific computation. The improvement in the performance of relational computations over massive data sets has the potential to change the way we do business or chart scientific discovery in those instances where the limiting factor is the sheer volume and diversity of data, such that the lack of computational throughput for relational computations limits our current ability to aggregate information or discover relationships across the data sets. The information that we extract from such relationships are becoming a central component of the way we operate businesses, pursue research, and manage our day to day lives. The form of these computations (e.g., relational, unstructured, etc.) and massive scale of these data sets introduces new algorithmic, intellectual, and engineering challenges. This research advances new algorithmic and engineering solutions to the problems of the analysis of relationships over massive data sets using advanced, massively parallel architectures. In particular, we address the use of heterogeneous architectures wherein high throughput processors (general purpose graphics processing units (GPGPUs)) are coupled with mainstream homogeneous multicore processors.

The major intellectual outcomes of this program are several and focus on new relational data sets structured as graphs – a dominant data structure in modern relational computation. Graphs are popular data structures for representing social networks, biological networks, transport networks, etc. However, they also create unstructured computations and memory referencing behavior that leads to low performance. First, we performed a comprehensive analysis of these emergent applications to understand their dynamic behaviors in how their computations are structured and how they use memory. The specific behavior is referred to as dynamic parallelism where the magnitude of concurrent computations is time-varying and data dependent.  The resulting insights led to the development of a new computational model for executing these applications and modifications to modern high performance GPGPU accelerators to enable their implementation on commodity heterogeneous processors. Second, the presence of massive data sets stresses the memory system. We focused on the implications of massive data sets and the associated applications on the management of the memory system. The unique properties of these applications led to the formulation of new models for managing memory (consistency models) and efficiently utilizing time-varying parallelism over data sets (synchronization models). Third, we addressed the algorithmic challenges presented by new relational data sets structured as graphs This program developed new algorithms for partitioning such structures on modern high performance parallel machines. At its core is a new approach to partitioning streaming graph data structures across hundreds – thousands of parallel processors, for example machines used in large scale scientific computation. These contributions represent a cross-cutting effort from algorithms, through execution models, to architecture implementations.

The engineering contributions of this program translated the preceding intellectual contributions into open source software artifacts to benefit the larger research and development community and enable further developments. These include i) two new application benchmark suites for graph processing and dynamic parallelism, ii) new simulation models for processor architectures that can support dynamic parallelism, and iii) software for partitioning and processing large scale graph data on modern high performance computing machines.

Collectively, the preceding intellectual and engineering contributions realize advances in the state of the art and provides scaffolding to continue to build on these controbutions.

Last Modified: 12/21/2017
Modified by: Sudhakar Yalamanchili