Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


MS_Thesis_ShashankSingh.pdf (471.25 KB)

ETD Abstract Container

Abstract Header

Scalable Analysis of Large Dynamic Dependence Graphs

Singh, Shashank
http://rave.ohiolink.edu/etdc/view?acc_num=osu1431093345

Abstract Details

2015, Master of Science, Ohio State University, Computer Science and Engineering.
Dynamic analysis is used for analyzing different properties of the runtime execution of a program. It helps in gaining useful insights into program’s behaviour for a given execution. The work in this thesis extends an existing dynamic analysis framework which has been used to develop dynamic analysis tools e.g. a tool to identify vectorization potential of existing programs, a tool responsible for characterizing and assessing the inherent data locality properties of a given computation. This existing framework is based on construction and analysis of the dynamic dependence graph for a given execution. The size of such graphs can easily grow to have millions or billions of nodes, even for simple programs and inputs. This thesis addresses the task of enabling scalable analysis of large dynamic dependence graphs (DDGs). We develop an out-of-core API to handle large DDGs - allowing analysis to run on machines with limited available memory. The existing analysis frameworks has the fundamental limitation that the DDG must be small enough to fit in memory. With the framework’s extension for handling out-of-core DDGs, any future or existing tools built on the framework can make use of this new API, allowing them to scale well with programs having large dynamic dependency graphs. A client of this API can also use the out-of-core functionality to manage other useful metadata (e.g., iteration vectors) needed for the analysis because; usually metadata associated with large graphs will also run into scalability issues. To validate effectiveness and efficiency of our implementation we run simple graph algorithms on dynamic graphs and measure performance. We also re-implement one of the dynamic analysis tool, making use of the new API to verify if this new version of the tool can analyse and handle large input graphs.
Ponnuswamy Sadayappan, Dr (Advisor)
Atanas Rountev, Dr (Committee Member)
50 p.
Computer Science
dynamic analysis, graphs, scalability, llvm

Recommended Citations

Citations

  • Singh, S. (2015). Scalable Analysis of Large Dynamic Dependence Graphs [Master's thesis, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1431093345

    APA Style (7th edition)

  • Singh, Shashank. Scalable Analysis of Large Dynamic Dependence Graphs. 2015. Ohio State University, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1431093345.

    MLA Style (8th edition)

  • Singh, Shashank. "Scalable Analysis of Large Dynamic Dependence Graphs." Master's thesis, Ohio State University, 2015. http://rave.ohiolink.edu/etdc/view?acc_num=osu1431093345

    Chicago Manual of Style (17th edition)

osu1431093345
614
© 2015, all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.