CiC (RDDC) Parallelizing Large Scale Graph Problems on the Cloud

University Of Southern California, Los Angeles CA

Investigators

Abstract

This research explores application development and optimizations for cloud platforms by developing: 1) cloud based parallelization for data intensive graph algorithms, 2) a framework for efficient scheduling and execution of applications in a heterogeneous cloud environment, and 3) hierarchical programming abstraction to specify parallelism. The work investigates and adapts wealth of techniques in traditional parallel computing for graph problems based on a performance model of the cloud and explore strategies for scheduling and load balancing applications on the cloud. These include centralized and distributed approaches for scheduling and work stealing and work sharing. Methodologies to evaluate the framework in executing applications that involve data intensive graph computations are being developed. The broader impact of this project includes addressing key challenges in the areas of application mapping and performance optimization. The research makes developing data intensive graph applications across public and private clouds easier. The developed software will be released as free and open source software to the community, making it possible for researchers and engineers in academia and industry to leverage this work and develop applications for the cloud. Graph problems and streaming applications arising in the area of energy informatics are considered to illustrate the techniques.