| The thesis describes an automated system, AutoHiPA (history-based piecewise approximation), that is developed to reduce the setup cost of the proposed HiPA scheme and enhance its ease of use. The system consists of a static analyzer, a profiler, a code generator, an auto-tuner, and a driver. It automatically identifies candidate functions, replaces them with their approximate counterparts, selects scheme variants and their parameters, and tunes them across runs to find the most efficient approximation for a given application.;This thesis makes the following specific contributions. 1. A novel function approximation scheme is introduced and explored, called history-based piecewise approximation (HiPA). This scheme divides the input range of a function into a number of regions, based on the function invocation history, and performs lower-order polynomial approximation in these regions. The initial approach uses polynomials in single variables. HiPA is an efficient software-only scheme that comes in two variants, non-uniform and uniform; their realizations and characteristics are described.;The evaluation of 90 mathematical and scientific functions from the GNU Scientific Library (GSL) [10] shows that HiPA is able to improve the performance of 90% of all functions. For 80% of the functions, the normalized RMS error in the approximated result is very small (0.04 on average) with 7.5x average speedup. For another 10% of the functions, the error is 0.4 with an average speedup of 5x.;The evaluation of five real applications demonstrates the feasibility, practicality, and effectiveness of the HiPA scheme. On average, the speedup for these applications is 2.9x with 0.25% error.;2. AutoHiPA, an automated function approximation system consisting of a static analyzer, a profiler, a code generator, an auto-tuner, and a driver. AutoHiPA automatically identifies and replaces candidate functions with their approximate counterparts, selects scheme variants and their parameters and tunes them across runs to find the best approximation.;3. HiPA++, an advanced history-based piecewise approximation scheme that supports dynamic online training and provides error control knobs. It introduces and employs a novel customized hash-based data structure; it may be of use for other applications. The scheme also harnesses idle cores in a multicore system to expedite and improve function approximation. It is capable of speculatively training and monitoring quality.;The evaluation of HiPA++ shows that the scheme is able to improve approximation leveraging dynamic online training from HiPA's 71.4% to 99.7% for an application from financial domain. For a physics application with high training overhead, it reports an increase of 2.2x in application speedup compared to HiPA's 1.5x, by leveraging available parallelism. (Abstract shortened by ProQuest.). |
