ERA

Download the full-sized PDF of Methodologies for Many-Input Feedback-Directed OptimizationDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R3DW8K

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Graduate Studies and Research, Faculty of

Collections

This file is in the following collections:

Theses and Dissertations

Methodologies for Many-Input Feedback-Directed Optimization Open Access

Descriptions

Other title
Subject/Keyword
feedback-directed optimization
performance evaluation
clustering
compilers
FDO
Type of item
Thesis
Degree grantor
University of Alberta
Author or creator
Berube, Paul N. J.
Supervisor and department
Jose Nelson Amaral (Computing Science)
Examining committee member and department
Lukasz Kurgan (Electrical and Computing Engineering)
Duane Szafron (Computing Science)
Sandhya Dwarkadas (Computer Science, University of Rochester)
Jose Nelson Amaral (Computing Science)
Department
Department of Computing Science
Specialization

Date accepted
2012-09-28T13:19:28Z
Graduation date
2012-09
Degree
Doctor of Philosophy
Degree level
Doctoral
Abstract
This thesis makes improvement to the process of ahead-of-time feedback-directed optimization (FDO) in compiler design. It examines multiple aspects of FDO from profile collection and representation through to the performance evaluation of FDO code transformations. Two guiding principals knit the four components of the research together. The first principle is a recognition that program behavior frequently depends on the input to the program; the second is that FDO is a predictive modeling technique, and must be designed and evaluated as such. Performance-evaluation methodology can be improved to be sensitive to input-dependent program behavior by using cross-validation with a workload of diverse program inputs. In many cases, expert knowledge can be leveraged to select program workloads that are representative of expected program usage. However, even with expert knowledge, characterizing input similarity and determining both how many inputs and the specific inputs to include in a workload are challenging questions. A compiler-centric clustering approach selects a small, representative, evaluation workload from a large initial collection of program inputs. Previous work has not addressed the problem of representing and utilizing multi-run profiles. An FDO compiler should not simply add, or average, profiles from multiple runs because a profile obtained this way does not provide any information about the variations in program behaviors observed between different inputs. {it Combined Profiling} (CP) merges the profiles from multiple runs into a distribution model that allows code transformations to consider cross-run behavior variations. An FDO-based function inlining transformation is implemented in the LLVM compiler to illustrate the use of combined profiling by a code transformation in a complex compiler and to provide a concrete example of the usage of a rigorous cross-validation evaluation methodology for FDO.
Language
English
DOI
doi:10.7939/R3DW8K
Rights
Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. Where the thesis is converted to, or otherwise made available in digital form, the University of Alberta will advise potential users of the thesis of these terms. The author reserves all other publication and other rights in association with the copyright in the thesis and, except as herein before provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.
Citation for previous publication

File Details

Date Uploaded
Date Modified
2014-04-30T23:16:26.191+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 1424239
Last modified: 2015:10:12 13:37:10-06:00
Filename: berube-phd-thesis-fgsr.pdf
Original checksum: b37804d7434da229f7ef2d2a7a040f2d
Well formed: false
Valid: false
Status message: No document catalog dictionary offset=0
Activity of users you follow
User Activity Date