Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


sampling-dynamic-dependence.pdf (528.74 KB)

ETD Abstract Container

Abstract Header

Sampling of Dynamic Dependence Graphs for Data Locality Analysis

Jhally, Gaganjit Singh
http://orcid.org/0000-0003-2633-6867
http://rave.ohiolink.edu/etdc/view?acc_num=osu1462885420

Abstract Details

2016, Master of Science, Ohio State University, Computer Science and Engineering.
Data locality is a critical factor which affects the execution time of applications today. With major advances being made in reducing the computation time of processors, data movement costs have increasingly become a bottleneck in runtime and energy efficiency of current applications. Existing dynamic analysis tools cannot provide any guidance on whether improvement in data movement costs maybe feasible. Lower and upper bounds on data movement costs can offer a solution to this problem. We put forth an approach to addressing this problem by using lower and upper bounds analysis of arbitrary programs. In this thesis, we will be focusing on the upper bound analysis using an existing framework. The framework has been used to develop tools to assess the data movement costs and help identify changes in execution schedule to increase the performance of an application. The framework achieves this by generating and analyzing a computational directed acyclic graph(CDAGs) for an execution. The size of these graphs can go up to billions of nodes. This thesis highlights how a sampling technique applied to the CDAG can reduce the time taken to analyze a real world application. The second part of the thesis is motivated in part by the existing difficulty in automating the time tiling of nested loops. Current strategy involves skewing the time loop to improve cache hits. Our strategy was developed to make use of fine grained parallelism offered by OpenMP tasks, and to subsequently utilize it to execute multiple tiles across time loop iterations, and utilize the speedup due to inherent data locality across time tiles.
P Sadayappan, Dr (Advisor)
Atanas Rountev, Dr (Committee Member)
36 p.
Computer Science
Data movement costs, cache miss cost, time tiling technique, sampling, dynamic analysis

Recommended Citations

Citations

  • Jhally, G. S. (2016). Sampling of Dynamic Dependence Graphs for Data Locality Analysis [Master's thesis, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1462885420

    APA Style (7th edition)

  • Jhally, Gaganjit. Sampling of Dynamic Dependence Graphs for Data Locality Analysis. 2016. Ohio State University, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1462885420.

    MLA Style (8th edition)

  • Jhally, Gaganjit. "Sampling of Dynamic Dependence Graphs for Data Locality Analysis." Master's thesis, Ohio State University, 2016. http://rave.ohiolink.edu/etdc/view?acc_num=osu1462885420

    Chicago Manual of Style (17th edition)

osu1462885420
352
© 2016, some rights reserved.Creative Commons License Sampling of Dynamic Dependence Graphs for Data Locality Analysis by Gaganjit Singh Jhally 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.