Skip to Main Content
Frequently Asked Questions
Submit an ETD
Global Search Box
Need Help?
Keyword Search
Participating Institutions
Advanced Search
School Logo
Files
File List
dissertation-venmugil.pdf (1.33 MB)
ETD Abstract Container
Abstract Header
Techniques for Characterizing the Data Movement Complexity of Computations
Author Info
Elango, Venmugil
ORCID® Identifier
http://orcid.org/0000-0002-7031-9020
Permalink:
http://rave.ohiolink.edu/etdc/view?acc_num=osu1452242436
Abstract Details
Year and Degree
2016, Doctor of Philosophy, Ohio State University, Computer Science and Engineering.
Abstract
The execution cost of a program, both in terms of time and energy, comprises computational cost and data movement cost (e.g., cost of transferring data between CPU and memory devices, between parallel processors, etc.). Technology trends will cause data movement to account for the majority of energy expenditure and execution time on emerging computers. Therefore, computational complexity alone will no longer be a sufficient metric for comparing algorithms, and a fundamental characterization of data movement complexity will be increasingly important. In their seminal work, Hong & Kung proposed the red-blue pebble game to model the data movement complexity of algorithms. Using the pebble game abstraction, Hong & Kung proved tight asymptotic lower bounds for the data movement complexity of several algorithms by reformulating the problem as a graph partitioning problem. In this dissertation, we develop a novel alternate graph min-cut based lower bounding technique. Using our technique, we derive tight lower bounds for different algorithms, with upper bounds matching within a constant factor. Further, we develop a dynamic analysis based automated heuristic for our technique, which enables automatic analysis of arbitrary computations. We provide several use cases for our automated approach. This dissertation also presents a technique, built upon the ideas of Christ et al., to derive asymptotic parametric lower bounds for a sub-class of computations, called affine computations. A static analysis based heuristic to automatically derive parametric lower bounds for affine parts of the computations is also presented. Motivated by the emerging interest in large scale parallel systems with interconnection networks and hierarchical caches with varying bandwidths at different levels, we extend the pebble game model to parallel system architecture to characterize the data movement requirements in large scale parallel computers. We provide interesting insights on architectural bottlenecks that limit the performance of algorithms on these parallel machines. Finally, using data movement complexity analysis, in conjunction with the roofline model for performance bounds, we perform an algorithm-architecture codesign exploration across an architectural design space. We model the maximal achievable performance and energy efficiency of different algorithms for a given VLSI technology, considering different architectural parameters.
Committee
P Sadayappan (Advisor)
Fabrice Rastello (Committee Member)
Atanas Rountev (Committee Member)
Radu Teodorescu (Committee Member)
Pages
186 p.
Subject Headings
Computer Science
Keywords
High-Performance Computing
;
IO complexity
;
Data movement complexity
;
Data access complexity
;
Red-blue pebble game
;
Lower bounds
Recommended Citations
Refworks
EndNote
RIS
Mendeley
Citations
Elango, V. (2016).
Techniques for Characterizing the Data Movement Complexity of Computations
[Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1452242436
APA Style (7th edition)
Elango, Venmugil.
Techniques for Characterizing the Data Movement Complexity of Computations.
2016. Ohio State University, Doctoral dissertation.
OhioLINK Electronic Theses and Dissertations Center
, http://rave.ohiolink.edu/etdc/view?acc_num=osu1452242436.
MLA Style (8th edition)
Elango, Venmugil. "Techniques for Characterizing the Data Movement Complexity of Computations." Doctoral dissertation, Ohio State University, 2016. http://rave.ohiolink.edu/etdc/view?acc_num=osu1452242436
Chicago Manual of Style (17th edition)
Abstract Footer
Document number:
osu1452242436
Download Count:
766
Copyright Info
© 2016, all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.