Paraprox: pattern-based approximation for data parallel applications

Approximate computing is an approach where reduced ac-curacy of results is traded off for increased speed, through-put, or both. Loss of accuracy is not permissible in all com-puting domains, but there are a growing number of data-intensive domains where the output of programs need not be perfectly correct to provide useful results or even notice-able differences to the end user. These soft domains include multimedia processing, machine learning, and data mining/-analysis. An important challenge with approximate comput-ing is transparency to insulate both software and hardware developers from the time, cost, and difficulty of using ap-proximation. This paper proposes a software-only system, Paraprox, for realizing transparent approximation of data-parallel programs that operates on commodity hardware systems. Paraprox starts with a data-parallel kernel imple-mented using OpenCL or CUDA and creates a parameter-ized approximate kernel that is tuned at runtime to maximize performance subject to a target output quality (TOQ) that is supplied by the user. Approximate kernels are created by rec-ognizing common computation idioms found in data-parallel programs (e.g., Map, Scatter/Gather, Reduction, Scan, Sten-cil, and Partition) and substituting approximate implementa-tions in their place. Across a set of 13 soft data-parallel ap-plications with at most 10 % quality degradation, Paraprox yields an average performance gain of 2.7x on a NVIDIA GTX 560 GPU and 2.5x on an Intel Core i7 quad-core pro-cessor compared to accurate execution on each platform