Approximate Computing at the Algorithmic Level

The complexity of data-oriented applications continually grows. The concept of approximate computing at the algorithm level aims at reducing the processing complexity to reduce the implementation cost. The implementation cost is reduced by decreasing the number of processing operations and memory exchanges. But, by modifying the original algorithm, the application output is modified and the resulting quality is degraded. Different approximate computing techniques acting at the algorithm level have been proposed to reduce the processing complexity of data-oriented applications. These techniques transform the algorithm to enable effective approximation. In the first part of this chapter, the different approaches proposed for approximate computing techniques acting at the algorithm level are presented. Two directions can be considered to reduce the complexity. The first direction is to skip part of the computation by removing some processing. The second direction is based on approximation to replace a part of the computation by a less complex processing. In the second part of this chapter, the High Efficiency Video Coding (HEVC) video codec is considered as a use-case to illustrate the use of the approximate computing techniques at the algorithmic level presented before.