Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


nqp-dissertation.pdf (1.58 MB)

ETD Abstract Container

Abstract Header

Characterization and Enhancement of Data Locality and Load Balancing for Irregular Applications

Niu, Qingpeng
http://rave.ohiolink.edu/etdc/view?acc_num=osu1420811652

Abstract Details

2015, Doctor of Philosophy, Ohio State University, Computer Science and Engineering.
The rate of improvement in data access costs continues to lag behind the improvement in computational rates. Therefore characterization and enhancement of data locality in applications is extremely important. In addition, load balancing also plays a significant role in parallel application performance. This is particularly challenging for irregular and unstructured applications. In this dissertation, we address both the efficient parallel characterization of data locality characteristics of programs, as well as develop parallel applications with enhanced data locality and load balancing. First, we address the speed of reuse distance analysis by parallelization. Reuse distance can directly predict the cache hit ratio for a fully associative cache and be used in various program optimization techniques like loop tiling, code reordering, cache sharing and cache partitioning to improve locality. Though reuse distance analysis is very useful, it is also costly. We develop the first parallel reuse distance analysis algorithm (Parda). Parda achieves speedup from 13 to 50 on various SPEC CPU2006 benchmarks compared to state-of-art sequential accurate reuse distance analysis algorithm. Second, we utilize reuse distance analysis to construct a locality based performance model to analyze and enhance the performance of two production scientific applications QMCPACK and QWalk. These quantum Monte Carlo (QMC) applications use a very large read-only table to store spline interpolation coefficients, and accesses to the table are generated at random based on the state of the Monte Carlo simulation. Currently QMC applications such as QWalk and QMCPACK replicate this table for every process or node, which limits scalability because increasing the number of processors does not enable larger systems to be run. We present a partitioned global address space (PGAS) approach to transparently managing this data using Global Arrays in a manner that allows the memory of multiple nodes to be aggregated. We develop an automated locality model driven caching system that significantly reduces communication overheads, Third, we design a load balancing strategy to accelerate another irregular application Multi-Level Regularized Markov Clustering(MLR-MCL). By indepth profiling of MLR-MCL, we find that the most time consuming part of MLR-MCL algorithm is Regularized Markov Clustering(R-MCL). Through carefully studying the R-MCL, we propose a effective static load balancing strategy based on memory footprints and indexing optimization eliminating extra memory copy which inherently enhances the data locality. We achieve speedup from 2.40 to 10.43 comparing to original sequential MRL-MCL implementation. Our optimization can be directly applied to general sparse matrix matrix multiplication(SpGEMM). Our optimized version of SpGEMM outperforms the Intel Math Kernel Library (MKL) on Intel CPUs as well as the Intel MIC (Many Integrated Core) processor.
P Sadayappan, Dr (Advisor)
Srinivasan Parthasarathy, Dr (Committee Member)
Rountev Atanas, Dr (Committee Member)
116 p.
Computer Science
Irregular applications; Program Locality; Load balancing; Performance Optimization; Reuse distance; Parallel Algorithm; Generalized sparse matrix-matrix multiplication; SpGEMM;

Recommended Citations

Citations

  • Niu, Q. (2015). Characterization and Enhancement of Data Locality and Load Balancing for Irregular Applications [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1420811652

    APA Style (7th edition)

  • Niu, Qingpeng. Characterization and Enhancement of Data Locality and Load Balancing for Irregular Applications. 2015. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1420811652.

    MLA Style (8th edition)

  • Niu, Qingpeng. "Characterization and Enhancement of Data Locality and Load Balancing for Irregular Applications." Doctoral dissertation, Ohio State University, 2015. http://rave.ohiolink.edu/etdc/view?acc_num=osu1420811652

    Chicago Manual of Style (17th edition)

osu1420811652
616
© 2015, some rights reserved.Creative Commons License Characterization and Enhancement of Data Locality and Load Balancing for Irregular Applications by Qingpeng Niu is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License. Based on a work at etd.ohiolink.edu.
This open access ETD is published by The Ohio State University and OhioLINK.