Run-time optimization of adaptive irregular applications

Show full item record

Title: Run-time optimization of adaptive irregular applications
Author: Yu, Hao
Abstract: Compared to traditional compile -time optimization , run -time optimization could o & #64256 ;er signi & #64257 ;cant performance improvements when parallelizing and optimizing adaptive irregular applications , because it performs program analysis and adaptive optimizations during program execution . Run -time techniques can succeed where static techniques fail because they exploit the characteristics of input data , programs' dynamic behaviors , and the underneath execution environment . When optimizing adaptive irregular applications for parallel execution , a common observation is that the effectiveness of the optimizing transformations depends on programs' input data and their dynamic phases . This dissertation presents a set of run -time optimization techniques that match the characteristics of programs' dynamic memory access patterns and the appropriate optimization (parallelization ) transformations . First , we present a general adaptive algorithm selection framework to automatically and adaptively select at run -time the best performing , functionally equivalent algorithm for each of its execution instances . The selection process is based on off -line automatically generated prediction models and characteristics (collected and analyzed dynamically ) of the algorithm's input data , In this dissertation , we specialize this framework for automatic selection of reduction algorithms . In this research , we have identi & #64257 ;ed a small set of machine independent high -level characterization parameters and then we deployed an off -line , systematic experiment process to generate prediction models . These models , in turn , match the parameters to the best optimization transformations for a given machine . The technique has been evaluated thoroughly in terms of applications , platforms , and programs' dynamic behaviors . Speci & #64257 ;cally , for the reduction algorithm selection , the selected performance is within 2 % of optimal performance and on average is 60 % better than "Replicated Buffer ," the default parallel reduction algorithm speci & #64257 ;ed by OpenMP standard . To reduce the overhead of speculative run -time parallelization , we have developed an adaptive run -time parallelization technique that dynamically chooses effcient shadow structures to record a program's dynamic memory access patterns for parallelization . This technique complements the original speculative run -time parallelization technique , the LRPD test , in parallelizing loops with sparse memory accesses . The techniques presented in this dissertation have been implemented in an optimizing research compiler and can be viewed as effective building blocks for comprehensive run -time optimization systems , e .g . , feedback -directed optimization systems and dynamic compilation systems .
URI: http : / /hdl .handle .net /1969 .1 /1285
Date: 2004-11-15


Run-time optimization of adaptive irregular applications. Available electronically from http : / /hdl .handle .net /1969 .1 /1285 .

Files in this item

Files Size Format View
etd-tamu-2004B-CPSC-Yu-2.pdf 675.1Kb application/pdf View/Open

This item appears in the following Collection(s)

Show full item record

Search DSpace

Advanced Search