Mario Barbareschi

Salvatore Barone

Alberto Bosio
email: alberto.bosio@ec-lyon.fr

Jie Han

A Genetic-Algorithm-Based Approach to the Design of DCT Hardware Accelerators

Keywords: CCS Concepts:, Hardware → Circuit optimization, Circuits power issues, Switching devices power issues, Application specific integrated circuits, Full-custom circuits, • Applied computing → Multi-criterion optimization and decision-making Code Mutation, Generic Algorithm, Approximate Computing Techniques, Design Space Exploration, JPEG, Discrete Cosine Transform

As modern applications demand an unprecedented level of computational resources, traditional computing system design paradigms are no longer adequate to guarantee significant performance enhancement at an affordable cost. Approximate Computing (AxC) has been introduced as a potential candidate to achieve better computational performances by relaxing non-critical functional system specifications. In this paper, we propose a systematic and high-abstraction-level approach allowing the automatic generation of near Pareto-optimal approximate configurations for a Discrete Cosine Transform (DCT) hardware accelerator. We obtain the approximate variants by using approximate operations, having configurable approximation degree, rather than full-precise ones. We use a genetic searching algorithm to find the appropriate tuning of the approximation degree, leading to optimal trade-offs between accuracy and gains. Finally, to evaluate the actual HW gains, we synthesize non-dominated approximate DCT variants for two different target technologies, namely Field Programmable Gate Arrays (FPGAs) and Application Specific Integrated Circuits (ASICs). Experimental results show that the proposed approach allows performing a meaningful exploration of the design space to find the best trade-offs in a reasonable time. Indeed, compared to the state-of-the-art work on approximate DCT, the proposed approach allows an 18% average energy improvement while providing at the same time image quality improvement.

INTRODUCTION

With the increasingly fast-growing amount of information processed by modern computing systems, energy efficiency has become a stringent requirement. Therefore, design activities are becoming more challenging and traditional techniques seem more and more unsuitable. An increasingly popular solution is the Approximate Computing (AxC) design paradigm. AxC exploits the gap between the high accuracy level provided by a computer system and the moderate accuracy required by a given application to achieve performance gains or energy savings by carefully reducing accuracy.

In this perspective, AxC is most effective when applied to applications dealing with redundant data, end-user perceptual limitations, or error resilient algorithms [START_REF] Vinay | Analysis and Characterization of Inherent Application Resilience for Approximate Computing[END_REF][START_REF] Chippa | Scalable Effort Hardware Design[END_REF][START_REF] Venkataramani | Approximate Computing and the Quest for Computing Efficiency[END_REF].

AxC has raised many design challenges due to the variety of Approximate Computing Techniques (AxCTs) [START_REF] Mittal | A Survey of Techniques for Approximate Computing[END_REF].

Each AxCT can introduce different approximation degrees. This leads to a huge amount of different approximate system configurations. Evaluating the approximation impact on the output quality at the application level is often quite time-consuming and not trivial. Indeed, it is usually achieved through simulations or executions of the whole approximate application [START_REF] Vinay | Analysis and Characterization of Inherent Application Resilience for Approximate Computing[END_REF] to ensure that the quality specifications are met. An additional challenge is related to the lack of a general automation tool and a methodology for the Design Space Exploration (DSE).

One of the main fields of application for AxC is image processing: imperceptible reduction of image quality can lead to important computational resources savings. Most of the research work focuses on the JPEG compression, either considering the algorithms as a whole or its individual computational steps. Concerning the design of hardware accelerators, researchers focused on the approximation of Discrete Cosine Transform (DCT) accelerators, mainly targeting figures of merit such as circuit complexity, delay, area and power dissipation [START_REF] Haider | Inexact Designs for Approximate Low Power Addition by Cell Replacement[END_REF][START_REF] Haider | Approximate DCT Image Compression Using Inexact Computing[END_REF][START_REF] Gupta | Low-Power Digital Signal Processing Using Approximate Adders[END_REF].

Unfortunately, the effect of the different approximation techniques and relative configurations (i.e., approximation degrees) are only analyzed individually and without a supporting methodology.

Conversely, in this work, we assess the impact of approximation -for different approximation degrees -on the DCT computation by performing a fully automated DSE. Starting from the DCT algorithm, we first perform an Abstract Syntax Tree (AST) analysis to gather information on the operations suitable for approximation. Then, we generate parametric approximate versions. Through the approximation parameters, we can tune the approximation degree. Finally, we build a Multi-objective Optimization Problem (MOP) to find the Pareto-optimal values for the aforementioned approximation parameters. To converge towards a Pareto front, we use a Genetic Algorithm (GA). The fitness functions driving the GA are the quality reduction minimization and the gain maximization. To perform the DSE in an acceptable time, we operate at high-abstraction level, by modeling the hardware approximation gains with an estimation function. We measure the quality reduction by evaluating the JPEG execution over a large image dataset. Finally, after the DSE, we synthesize the obtained approximate DCT configurations on both Field Programmable Gate Array (FPGA) and Application Specific Integrated Circuits (ASICs) target technologies and demonstrate the effectiveness of the approach w.r.t. the state of the art.

The remainder of this paper is structured as follows: Section 2 reviews the existing related work; Section 3 provides preliminary technical background, while Section 4 describes in detail the proposed workflow. In order to evaluate the proposed approach, Section 5 describes the experimental setup, reports result and compares our approach with previous studies. Finally, Section 6 draws the conclusions.

Manuscript submitted to ACM

RELATED WORK

The effectiveness of imprecise computation for error-resilient applications has been demonstrated both for software and hardware components implementing inexact algorithms [START_REF] Vinay | Analysis and Characterization of Inherent Application Resilience for Approximate Computing[END_REF][START_REF] Venkataramani | Approximate Computing and the Quest for Computing Efficiency[END_REF]. The use of approximation is sometimes intrinsic, e.g., in digital signal processing, where analog signals are discretized and quantized. In many scenarios, the voluntary introduction of approximation turns out to be beneficial. For instance, the perceptual limitations of human senses can be leveraged to reduce the data precision, thus to reduce the storage requirements [START_REF] Rahimi | Approximate Associative Memristive Memory for Energy-Efficient GPUs[END_REF] or to improve performances of multimedia and signal processing applications [START_REF] Samadi | SAGE: Self-Tuning Approximation for Graphics Engines[END_REF]. Likewise, executing iterative-refinement algorithms with a reduced precision of intermediate computation can improve performances, with little or even no effects on the quality of results [START_REF] Raha | Quality Configurable Reduce-and-Rank for Energy Efficient Approximate Computing[END_REF]. Different AxCTs have been proposed in the scientific literature [START_REF] Mittal | A Survey of Techniques for Approximate Computing[END_REF]. Some examples use bit-width optimization [START_REF] Fang | Floating-Point Bit-Width Optimization for Low-Power Signal Processing Applications[END_REF] and loop-perforation [START_REF] Sidiroglou-Douskos | Managing Performance vs. Accuracy Trade-Offs with Loop Perforation[END_REF].

Employing the AxC full potential requires dealing with several challenges. (i) Approximation error-assessment: since compliance with output quality constraints has to be guaranteed, error-assessment is crucial. The actual error assessment may require the simulation of both exact and approximate applications, which is very costly. Nevertheless, in order to reduce the required effort, an estimation can be obtained by resorting to a representative workload. On the other hand, a different approach, based on Bayesian inference [START_REF] Traiola | Predicting the Impact of Functional Approximation: From Component-to Application-Level[END_REF][START_REF] Traiola | Probabilistic Estimation of the Application-Level Impact of Precision Scaling in Approximate Computing Applications[END_REF], analytical models [START_REF] Castro-Godínez | AxLS: A Framework for Approximate Logic Synthesis Based on Netlist Transformations[END_REF], machine-learning [START_REF] Mrazek | autoAx: An Automatic Design Space Exploration and Circuit Building Methodology Utilizing Libraries of Approximate Components[END_REF], and even neural networks [START_REF] Zervakis | Multi-Level Approximate Accelerator Synthesis Under Voltage Island Constraints[END_REF] have been proposed in order to avoid simulations. (ii) The choice of metrics for error estimation: they may strongly depend on the particular application. Thus, choosing the right metric, or the right combination of metrics, is of major concern, and it is not a trivial task. (iii) Approximate configuration choice: a given application can be approximated in many different ways. Among all the different approximate configurations, choosing those providing the best trade-off between accuracy loss and resource gains is one of the major challenges in AxC.

Indeed, low error and high benefits are conflicting goals.

Concerning hardware design, initial approaches -although not efficient nor scalable -addressed the aforementioned issues by manually identifying approximable sub-parts of a given application. Afterwards, there have been several attempts to define systematic and automated approaches. Ranjan et al. [START_REF] Ranjan | ASLAN: Synthesis of Approximate Sequential Circuits[END_REF], for instance, identify combinational subcircuits -such as arithmetic units -by looking at the Register Transfer Level (RTL) description of the circuit to be approximated, selecting the optimal quality/energy operating-point using stochastic gradient-descent, in order to maximize energy savings. Nepal et al. [START_REF] Nepal | ABACUS: A Technique for Automated Behavioral Synthesis of Approximate Computing Circuits[END_REF] perform AST manipulations to generate several approximate versions of a given circuit, starting from either behavioral or RTL descriptions. The variant providing the optimal trade-off between accuracy and gains is selected by means of a stochastic greedy algorithm.

The synergetic effects of multiple approximation techniques, acting at different levels, have been also investigated in the scientific literature. In [START_REF] Zervakis | Multi-Level Approximate Accelerator Synthesis Under Voltage Island Constraints[END_REF], for instance, the precision-scaling technique is exploited in conjunction with voltagescaling, since the former usually leads to lower circuit delay, paving the way for aggressive voltage scaling, which provides higher impacts on energy savings. However, all the aforementioned approaches either combine multiple design objectives in a single-objective optimization problem or optimize a single parameter while keeping the others fixed. Therefore, the resulting solutions are centered around a few dominant design alternatives and do not cover the whole Pareto front [START_REF] Das | A Closer Look at Drawbacks of Minimizing Weighted Sums of Objectives for Pareto Set Generation in Multicriteria Optimization Problems[END_REF]. Researches in [START_REF] Sekanina | Automated Search-Based Functional Approximation for Digital Circuits[END_REF] addressed the problem by using Cartesian genetic programming to search for Pareto-optimal approximate circuit implementations requiring progressively fewer hardware resources. Unfortunately, such approaches did not focus on complex systems, rather on arithmetic components, such as adders and multipliers, which are used as building blocks for hardware accelerators. Mario Barbareschi, Salvatore Barone, Alberto Bosio, Jie Han, and Marcello Traiola In [START_REF] Mrazek | autoAx: An Automatic Design Space Exploration and Circuit Building Methodology Utilizing Libraries of Approximate Components[END_REF], circuits from a library of approximate components are selected to generate an approximate accelerator for a given application. On the basis of contributions from single components, machine learning techniques are adopted to estimate the overall quality and hardware cost of the accelerator, without requiring simulations and synthesis. A similar approach has been presented in [START_REF] Castro-Godínez | AxLS: A Framework for Approximate Logic Synthesis Based on Netlist Transformations[END_REF]. A set of analytical models of quality and resource requirements are derived for a library of approximate components. Then these are used to estimate resource needed and accuracy of accelerator designed through high-level synthesis of C language description.

In this work, we focus on a complex system, performing image processing. Specifically, we focus on the JPEG compression. In [START_REF] Haider | Approximate DCT Image Compression Using Inexact Computing[END_REF], a framework relying on inexact computing to perform the DCT computation for the JPEG has been proposed. The framework acts on three levels: (i) at the application level, it exploits human insensitivity to high-frequency variation to use a filter and discard high-frequency components; (ii) at the algorithmic level, multiplier-less fast algorithms are employed for the actual DCT computation on integer coefficients; (iii) at hardware level, rather than using a simple truncation for adder circuits, authors used Inexact-Adder Cells (IACs) to compute less significant bits instead of the Full-Adder Cells (FACs). Therefore, firstly, the JPEG quantization step is performed only low-frequency components of an image block; thus the high-frequency filter implementation comes down to simply setting some DCT coefficients to zero. Then, at algorithmic level, since the DCT is the most effort-demanding step in JPEG, fast DCT algorithms have been used [7-10, 14, 28, 29]. Those algorithms reduce the DCT complexity from 𝑂 (𝑁 2 ) to 𝑂 (𝑁 ) and require only integer additions. Finally, at the hardware level, three different IAC families are considered in [START_REF] Haider | Approximate DCT Image Compression Using Inexact Computing[END_REF], i.e., the Approximate Mirror Adder (AMA) [START_REF] Gupta | Low-Power Digital Signal Processing Using Approximate Adders[END_REF], the Approximate XOR-based Adder (AXA) [START_REF] Yang | Approximate XOR/XNOR-Based Adders for Inexact Computing[END_REF] and the IneXact Adder (InXA) [START_REF] Haider | Inexact Designs for Approximate Low Power Addition by Cell Replacement[END_REF]. The framework in [START_REF] Haider | Approximate DCT Image Compression Using Inexact Computing[END_REF] mainly aims at assessing the joint impact of those three levels of approximation. However, it presents two main weaknesses: (i) approximation is introduced by manually tuning the individual approximation parameters and (ii) output quality is assessed over only four images. In this paper, we propose a methodology to overcome the highlighted problems by defining a systematic and automatic approach for approximate hardware design. Fig. 1. The workflow of our approach.

PRELIMINARY TECHNICAL BACKGROUND

Manuscript submitted to ACM

In this Section we discuss the proposed workflow, which is depicted in Figure 1, while providing the required technical background. In particular, we firstly detail the proposed generation process of approximate variants. Secondly, we describe how we perform a DSE to converge towards the Pareto-optimal approximate variants.

Approximate variants generation

Given an algorithm implementation, in order to automatically generate approximate variants while having control on the error, gathering information on the operations suitable for approximation is necessary. We obtain this information through the analysis of the algorithm implementation's AST. Hence, we employ mutators [START_REF] Barbareschi | Automatic Design Space Exploration of Approximate Algorithms for Big Data Applications[END_REF][START_REF] Barbareschi | An Extendible Design Exploration Tool for Supporting Approximate Computing Techniques[END_REF], to make systematic modifications to the AST, producing altered implementations. Mutators are defined as a set of rules to search and modify the AST. The rule definition is generally application-independent and does not require the user to know the algorithm or its specific implementation. In particular, we consider, as an approximation technique, the replacement of exact sums with approximate ones. We produce a mutator that automatically replaces exact sums with the approximate counterparts, without knowing the particular algorithm or its implementation. In this way, we obtain approximate variants of the original algorithm. Moreover, the approximate sums are configurable in their degree of approximation.

The number of variants and the number of configurations grow quickly with the number of operations suitable for approximation. Consider, for instance, an algorithm implementation with 𝑛 approximable operations, each allowing 𝑘 different degrees of approximation: 𝑛 𝑗 different approximate variants can be defined by simultaneously approximating 𝑗 operations, and 𝑘 𝑗 different approximate configurations can be defined for each of the variants. Therefore, the total number of approximate configurations is 𝑛 𝑖=1 𝑘 𝑖 × 𝑛 𝑖 . At this point, the main challenge is to find values for the approximation parameters leading to the Pareto-optimal trade-offs between performance gains and accuracy losses, i.e., to perform a DSE.

Design space exploration

As mentioned in the introduction, we model the DSE as a MOP. Basically, a MOP consists of a set of fitness-functions to minimize/maximize at the same time and a set of constraints to be met, as reported in [START_REF]SIPI Image Database[END_REF],

Γ = {𝛾 𝑖 : 𝐴 → R, 𝑖 = 1 • • • 𝑘 } Ψ = {𝜓 𝑗 : 𝐴 → {0, 1}, 𝑗 = 1 • • • 𝑙 } 𝐴 ⊆ R 𝑛 (1)
where Γ and Ψ are the set of fitness-functions and the set of constraint-functions, respectively. While the functions of the former set assume values in R, or its subset, the constraint functions assume either the value 1 or 0 to indicate that the constraint is or is not met, respectively. Equation (2) describes the set of solutions for [START_REF]SIPI Image Database[END_REF]. For non-trivial MOPs, |𝑋 | > 1, where | • | expresses the size of the set, i.e., the number of elements it contains.

𝑋 = {𝑥 ∈ 𝐴 : 𝛾 𝑖 (𝑥) ≤ 𝛾 𝑖 (𝑥 ′ ), 𝑥 ⊢ 𝜓 𝑗 , 𝑥 ′ ≠ 𝑥, 𝑖 ∈ [1, 𝑘] , 𝑗 ∈ [1, 𝑙]} (2)
Indeed, since different objectives (i.e., fitness functions) often represent conflicting goals, the DSE goal is to seek for a set of equally good solutions being close to the Pareto-front (2). Let us consider two solutions, 𝑥, 𝑦 ∈ 𝑋 : 𝑥 ≠ 𝑦, 𝑥 is said to dominate 𝑦 i.f.f. (3) holds, i.e., 𝑥 shows better or equally good objective values than 𝑦 in all objectives and at least better in one objective. If a solution is not dominated by any others, it is called a Pareto-optimal solution.

𝑥 ≺ 𝑦 ⇐⇒ 𝛾 𝑖 (𝑥) ≤ 𝛾 𝑖 (𝑦) ∀𝑖 ∈ [1, 𝑘] ∧ ∃𝑗 ∈ [1, 𝑘] : 𝛾 𝑗 (𝑥) < 𝛾 𝑗 (𝑦) (3)
Due to the rapid growth of the size of the solution space as the number of decision variables, fitness functions and constraints increases, using exact solving algorithms turns out to be very computation-intensive. Consequently, a variety of heuristics aiming at producing an approximation of the Pareto-front have been proposed in the scientific literature. Some well-known heuristics are hill-climbing, ant-colony [START_REF] Dorigo | Ant Colony Optimization[END_REF] and Evolutionary Algorithms (EAs).

GAs, a subclass of EAs, have been largely used in the literature to find Pareto-fronts for MOPs [START_REF] Deb | A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II[END_REF]. GAs are inspired by and also borrows terminology from the evolutionary theory: mutation, crossover and selection mechanisms cause the extinction of weak and unfit species while strong ones have greater opportunities to survive and pass their genes to future generations. In particular, we resort to Multi-Objective Evolutionary Algorithms (MOEAs). MOEAs operate on a set of individuals, called population, that evolves and, eventually, converges to a set of Pareto-dominant solutions.

Each individual is represented as a chromosome, i.e., a data structure encoding the search space. During the evolution process, new offspring is generated either through or in combination of crossover and mutation [START_REF] Deb | Self-Adaptive Simulated Binary Crossover for Real-Parameter Optimization[END_REF]. A crossover takes two parent chromosomes to produce a new chromosome. Thence, we resort to the Non-dominated Sorted Genetic Algorithm-II (NSGA-II), which is widely employed as a standard approach [START_REF] Deb | A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II[END_REF].

It follows an elitist principle, i.e., the elites of a population are given the opportunity to be carried to the next generation. The evolution process starts from an initial population, which is typically randomly generated or seeded in areas where optimal solutions are likely to be found, and it goes through the following steps.

At the beginning, the NSGA-II builds a random initial population 𝑃 0 of size 𝑁 , and sorts the latter using nondomination sorting, which will be presented below. Thus, each individual is assigned a rank equal to its non-domination level. At the first iteration, usual crossover, mutation and binary tournament selection operator are used to build the 𝑄 0 offspring population. The behavior of the algorithm during a generic i-th iteration is summarized in Figure 2: (i) a combined population Along with convergence to the Pareto-front, it is also desired that am EA maintains a good spread in the obtained set of solutions. In order to preserve diversity, the NSGA-II adopts the crowding distance as a metric for the density of solutions surrounding a particular solution. Such distance is the average distance of two points on either side of the considered solution, along each of the fitness functions. The computation requires sorting the population 𝑀 times, according to each fitness function, in ascending order. Each time the population is sorted, the boundary solutionsi.e., solutions with the smallest and the largest fitness -are assigned an infinite distance, while all other solutions are assigned with a crowding distance equal to the absolute normalized difference of fitness of the two adjacent solutions.

𝑅 𝑖 = 𝑃 𝑖 ∪ 𝑄 𝑖 is
The overall crowding distance is the sum of individual distances corresponding to each fitness function. Using crowded distance, the usual definition of Pareto dominance (3) is slightly modified as in ( 4), where 𝑥 ≈ 𝑦 denotes 𝑥 and 𝑦 do not dominate each other and 𝑑 (•) is the crowding distance of a given solution. The crowded selection operator preserves diversity by promoting solutions located in less crowded areas of the solution space.

𝑥 ≺ 𝑛 𝑦 ⇐⇒ 𝑥 ≺ 𝑦 ∪ (𝑥 ≈ 𝑦 ∧ 𝑑 (𝑥) > 𝑑 (𝑦)) (4)
Modeling a specific optimization problem so that it can be resolved by a MOEA is not trivial and there are no general rules. In our case, as mentioned in Section 3.1, we approximate a number of operations in the DCT algorithm. According to their approximation degree, each of the operations contributes to error and gains differently. On the one hand, it may be easy to analytically define a relationship between the degree of approximation and the corresponding gains, by using properties of the specific approximation. On the other hand, doing the same with the error is not trivial, due to its propagation through the data-flow. Therefore, fitness functions should be defined case by case. Finally, regarding the constraints, identifying acceptable variation ranges for one or more genes or identify an error threshold is generally feasible. For instance, for an n-bits adder, the variation interval of the gene could be {0, 1, • • • , 𝑛} to cover the degree that goes from "no-approximation" to "totally approximate".

Finally, from a technical standpoint, approximate configurations can be represented by using a vector -i.e., a chromosome, in the MOEA context -having as many elements -i.e., genes -as operations. The value of each element represents the approximation degree for the corresponding operation.

Being the goal of the DSE to find the Pareto-optimal approximation degree for all the operations, the NSGA-II provides a suitable tool to perform the exploration of such a large design space, in a reasonable time.

TOWARDS APPROXIMATE DCT

In this section, firstly we discuss the mathematical steps leading to a set of linear equations to compute DCT coefficients using only additions. These equations are general and independent of the particular DCT algorithm. Secondly, we present the approximate DCT variants generation and how we model the DSE as a MOP so that it can be resolved by using the NSGA-II.

Manuscript submitted to ACM

Addition-based computation of DCT coefficients

As we already mentioned, the DCT computation is known to have 𝑂 (𝑁2 ) complexity and requires resource-intensive functional units, such as floating-point arithmetic modules. The algorithm proposed in [START_REF] Loeffler | Practical Fast 1-D DCT Algorithms with 11 Multiplications[END_REF] requires 11 multiplications and 29 additions to compute the one-dimensional eight-point DCT needed by the JPEG compression. It is considered the most efficient exact algorithm, since the lower bound on the number of multiplications required for such DCT computation has been proven to be 11 [START_REF] Feig | On the Multiplicative Complexity of Discrete Cosine Transforms[END_REF]. In order to achieve an additional reduction in resource requirements, authors of [START_REF] Arai | A Fast DCT-SQ Scheme for Images[END_REF] moved parts of the DCT computation to the JPEG quantization step. Furthermore, transformed coefficients can be scaled and rounded such that floating-point operations can be superseded by integer ones: the resulting algorithms are significantly faster, and they find extensive use in practical applications. However, integer multiplication is still complex and resource intensive; thus, many low-complexity multiplier-less algorithms have been proposed [7-10, 14, 28, 29].

As in [START_REF] Arai | A Fast DCT-SQ Scheme for Images[END_REF], all of these algorithms split the DCT computation into two consecutive steps: the first one is referred to as approximate-DCT, which involves only integer operations, while the second step is embedded into the quantization and takes advantages of floating-point operations the latter requires. Moreover, they all avoid computing DCT coefficients separately or iteratively. Instead, they extensively use matrix algebra and its properties. To show how the abovementioned algorithms work, let 𝑋 be an input image tile, which is a 8 × 8 matrix; its two-dimensional DCT transform, from now on simply DCT, is described by the following equation:

𝐹 = 𝐶 • 𝑋 • 𝐶 ′ , (5)
where 𝐶 is referred to as DCT matrix. 𝐶 contains the cosine function values at the needed frequencies. The 𝑋 and the 𝐹 matrices have the same dimensions. The elements in 𝐹 represent the DCT coefficients as the frequency progressively increases: low-frequency components are closer to the top-left corner, while high-frequency ones are placed close to the bottom-right corner. The 𝐶 matrix can be split into two matrices, 𝑇 and 𝐷, as reported in Equation [START_REF] Barbareschi | An Extendible Design Exploration Tool for Supporting Approximate Computing Techniques[END_REF].

𝐹 = 𝐶 • 𝑋 • 𝐶 ′ = 𝐷 • (𝑇 • 𝑋 • 𝑇 ′ ) • 𝐷 (6)
Different algorithms define 𝑇 and 𝐷 in different ways, so the number of computation operations may vary from algorithm to algorithm, as reported in } being typical values. For this reason, resorting to properties of diagonal matrices allows obtaining the following equation:

𝐹 = 𝑇 • 𝑋 • 𝑇 ′ • (𝑑𝑖𝑎𝑔(𝐷) • 𝑑𝑖𝑎𝑔(𝐷) ′ ), (7)
where • is the Hadamard product, i.e., an element-wise multiplication. Thus, the integer null-multiplicative part 𝑇 • 𝑋 •𝑇 ′ can be isolated from floating-point operations required by 𝐷. Afterwards, floating-point operations can be performed outside the DCT, and embedded into the JPEG quantization step, as shown in the following equation.

𝐹 𝑄 = ⌈𝐹 ⊘ 𝑄⌋ = ⌈𝑇 • 𝑋 • 𝑇 ′ • (𝑑𝑖𝑎𝑔(𝐷) • 𝑑𝑖𝑎𝑔(𝐷) ′ ) ⊘ 𝑄⌋ = ⌈𝑇 • 𝑋 • 𝑇 ′ • Q⌋ = ⌈(𝑇 • (𝑇 • 𝑋 ′ ) ′ ) • Q⌋ (8) Q = (𝑑𝑖𝑎𝑔(𝐷) • 𝑑𝑖𝑎𝑔(𝐷) ′ ) ⊘ 𝑄, (9)
where Q in ( 9) is the complete quantization matrix and the ⊘ operator is the Hadamard division, i.e., an element-wise division. From ( 8), it follows 𝐹 = (𝑇 • (𝑇 • 𝑋 ′ ) ′ ), which means that the approximate two-dimensional DCT transform can be computed using the one-dimensional DCT transform twice, reducing the complexity from quadratic to linear.

The only substantial difference between the different multiplier-less DCT algorithms is the 𝑇 matrix. Hence, it is straightforward to derive a set of equations to calculate the one-dimensional DCT coefficients. Equations in [START_REF] Saad Bouguezel | A Fast 8×8 Transform for Image Compression[END_REF], for instance, refers to the BC12 algorithm [START_REF] Bayer | DCT-like Transform for Image Compression Requires 14 Additions Only[END_REF].

𝑓 0 = 𝑥 0 + 𝑥 1 + 𝑥 2 + 𝑥 3 + 𝑥 4 + 𝑥 5 + 𝑥 6 + 𝑥 7 𝑓 1 = 𝑥 0 -𝑥 7 𝑓 2 = 𝑥 0 -𝑥 1 -𝑥 2 + 𝑥 3 + 𝑥 4 -𝑥 5 -𝑥 6 + 𝑥 7 𝑓 3 = 𝑥 4 -𝑥 3 𝑓 4 = 𝑥 0 -𝑥 3 -𝑥 4 + 𝑥 7 𝑓 5 = 𝑥 5 -𝑥 2 𝑓 6 = 𝑥 2 -𝑥 1 + 𝑥 5 -𝑥 6 𝑓 7 = 𝑥 6 -𝑥 1 (10)
Furthermore, some terms -for instance (𝑥 0 + 𝑥 7 ) -are involved in the computation of multiple 𝑓 𝑖 coefficients, which allows to further reduce the amount of operations.

Approximate variants generation and MOP modeling

Once the addition-based equations for the DCT coefficients are defined, simple implementations for the DCT computation algorithm can be derived, such as BAS08 [START_REF] Saad Bouguezel | Low-Complexity 8$\times$ 8 Transform for Image Compression[END_REF], BAS09 [START_REF] Saad Bouguezel | A Fast 8×8 Transform for Image Compression[END_REF], BAS11 [START_REF] Saad Bouguezel | A Low-Complexity Parametric Transform for Image Compression[END_REF], BC12 [START_REF] Bayer | DCT-like Transform for Image Compression Requires 14 Additions Only[END_REF], CB11 [START_REF] Cintra | A DCT Approximation for Image Compression[END_REF], PEA12 [START_REF] Potluri | Multiplier-Free DCT Approximations for RF Multi-Beam Digital Aperture-Array Space Imaging and Directional Sensing[END_REF] and PEA14 [START_REF] Sadhvi Potluri | Improved 8-Point Approximate DCT for Image and Video Compression Requiring Only 14 Additions[END_REF].

Within those, we introduce further approximation by replacing exact sums by configurable approximate ones. Such approximate sums allow setting two parameters, i.e., the Number of Approximate Bits (NAB) and the type of adder hardware cell to use (namely, a classic FAC or an IAC). This was the same approach adopted in [START_REF] Haider | Approximate DCT Image Compression Using Inexact Computing[END_REF]. However, while in [START_REF] Haider | Approximate DCT Image Compression Using Inexact Computing[END_REF] the approximation was manually introduced, we propose to automate the replacement process by considering the AST of the algorithm implementation. Moreover, in [START_REF] Haider | Approximate DCT Image Compression Using Inexact Computing[END_REF], approximation parameters were tuned manually and one at a time, keeping the others at fixed values. Unfortunately, this does not necessarily lead to Pareto-optimal solutions.

Conversely, we propose to find the optimal value for the approximation parameters through an automatic DSE. We model the DSE as a MOP so that it can be resolved by using a MOEA. In the next subsections, we detail the MOP modeling.

Chromosome encoding.

To enable the MOEA to resolve the MOP, each approximate configuration is modeled as a chromosome. Chromosome's genes represent the two aforementioned approximation parameters, i.e., the NAB Manuscript submitted to ACM Mario Barbareschi, Salvatore Barone, Alberto Bosio, Jie Han, and Marcello Traiola value and the type of adder hardware cell to use. Thus, if 𝑁 𝑜𝑝 is the number of addition required, each chromosome is composed of 2 • 𝑁 𝑜𝑝 different genes. Chromosomes are provided with an additional gene representing the approximation degree for the high-frequency filter. Thus, each chromosome is composed of 2 • 𝑁 𝑜𝑝 + 1 genes.

Let us consider an approximate configuration from the population and its corresponding chromosome. Suppose a mutation occurs: depending on the particular gene being altered, a different approximate configuration will be generated.

The latter will differ from the origin one in (i) the number of approximate bits for a certain sum operation, (ii) the adder cell to be used for a certain sum, or (iii) the number of frequencies discarded by the high-frequency filter. Despite the fact that it involves multiple genes and, hence, multiple characteristics of a configuration, the same reasoning also applies to crossover. The NSGA-II selection operator will determine which of the individuals will survive, on the basis of fitness. Fitness functions driving the DSE are detailed in the following sections.

Error fitness-function.

For the MOEA to be able to evaluate the error entailed by the approximations, we need to define and error fitness-function to minimize.

In [START_REF] Haider | Inexact Designs for Approximate Low Power Addition by Cell Replacement[END_REF], the authors computed, through exhaustive simulations, the error-rate for different numbers of erroneous bits, for IAC adders. Unfortunately, this kind of measurements is not suitable for complex algorithms, such as the DCT, as it does not take into account the error propagation. Therefore, we resort to the whole JPEG compression, performed on a representative data set, to estimate the error. Section 5 discusses the experimental setup in more detail.

Regarding error metrics, in [START_REF] Haider | Approximate DCT Image Compression Using Inexact Computing[END_REF] the Maximum Difference (MD), the Average Difference (AD), the Mean Square Error (MSE) and the Peak Signal-to-Noise Ratio (PSNR) have been considered. Unfortunately, since all of them consider single pixels, these metrics turn out to be too sensible to noise [START_REF] Bhawna Rani | Comparison of JPEG and SPIHT Image Compression Algorithms Using Objective Quality Measures[END_REF]. Therefore, they are not particularly suited to evaluate the effectiveness of approximations on image processing algorithms. To overcome this issue, we resort to the Structural SIMilarity (SSIM) [START_REF] Wang | Image Quality Assessment: From Error Visibility to Structural Similarity[END_REF] to evaluate differences among images. Its formal definition is reported in Equation [START_REF] Castro-Godínez | AxLS: A Framework for Approximate Logic Synthesis Based on Netlist Transformations[END_REF], where 𝑋 and 𝑌 are two sets of data (i.e., the images), 𝜇 𝑋 and 𝜇 𝑌 are their mean values, 𝜎 2 𝑋 and 𝜎 2 𝑌 are their variances, 𝜎 𝑋𝑌 is their co-variance, 𝐿 is the value range in which elements of X and Y can vary, and 𝑘 1 and 𝑘 2 are tuning parameters (typically equal to 0.01 and 0.03, respectively). Values of 𝑆𝑆𝐼𝑀 (𝑋, 𝑌 ) span in the range [-1, 1]. Values of 𝑆𝑆𝐼𝑀 (𝑋, 𝑌 ) ≈ 1 mean that 𝑋 and 𝑌 are structurally similar, while values of 𝑆𝑆𝐼𝑀 (𝑋, 𝑌 ) ≈ 0 mean that there is no similarity between the two images. Values smaller than zero are meaningless [START_REF] Wang | DLAU: A Scalable Deep Learning Accelerator Unit on FPGA[END_REF].

𝑆𝑆𝐼𝑀 (𝑋, 𝑌 ) = (2𝜇 𝑥 𝜇 𝑦 + 𝑘 1 ) • (2𝜎 𝑥 𝑦 + 𝐿 • 𝑘 2 ) (𝜇 𝑥 + 𝜇 𝑦 + 𝑘 1 ) • (𝜎 2 𝑥 + 𝜎 2 𝑦 + 𝐿 • 𝑘 2 ) (11)
The effectiveness of image quality assessment increases if [START_REF] Castro-Godínez | AxLS: A Framework for Approximate Logic Synthesis Based on Netlist Transformations[END_REF] is applied locally rather than globally since (i) image statistical features are usually highly spatially non-stationary, (ii) image distortions, which may or may not depend on the local image statistics, may also be space-variant, and (iii) only a local area in the image can be perceived with high resolution by human observers [START_REF] Wang | Image Quality Assessment: From Error Visibility to Structural Similarity[END_REF]. Since, in practice, a single overall quality measure of the entire image is required, the Mean SSIM (MSSIM) from Equation ( 12) is adopted. There, 𝑋 and 𝑌 are the reference and the distorted images, respectively, 𝑥 𝑗 and 𝑦 𝑗 are the image contents at the j-th local window; and 𝑀 is the number of local windows in the image. Typically, the MSSIM index is computed considering 11 × 11 Gaussian weighted circular windows rather than on 8 × 8 square tiles [START_REF] Wang | Image Quality Assessment: From Error Visibility to Structural Similarity[END_REF].

𝑀𝑆𝑆𝐼𝑀 (𝑋, 𝑌 ) = 1 𝑀 𝑀 ∑ 𝑗=1 𝑆𝑆𝐼𝑀 (𝑥 𝑗 , 𝑦 𝑗 ) (12)
Manuscript submitted to ACM As SSIM, the lower the MSSIM index the lower the similarity between X and Y sets; thus, in order to define a suitable fitness-function for the MOEA to minimize error, we adopt the Structural DISSIMilarity (DSSIM) -𝐷𝑆𝑆𝐼𝑀 (𝑋, 𝑌 ) = 1 -𝑀𝑆𝑆𝐼 𝑀 (𝑋, 𝑌 ). In particular, we compute the 𝐷𝑆𝑆𝐼𝑀 between a standard JPEG compressed image 𝑋 and an image 𝑌 which is obtained by using a certain approximate configuration of a given approximate algorithm. Both 𝑋 and 𝑌 originate from the same non-compressed source image. We perform this operation for several images and use the average 𝐷𝑆𝑆𝐼 𝑀 as final error fitness-function.

4.2.3

The reward fitness function. In order to accurately assess resource savings, area, power consumption and maximum clock speed should be measured. Unfortunately, this would require the synthesis and simulation of large hardware designs. Thus, performing a hardware synthesis for each design explored in the DSE is a very time-consuming process.

Therefore, we resort to a gain estimation to drive the DSE. In particular, we estimate the gain (from now on 'reward') from the number of transistors required to implement an inaccurate cell, using the data from [START_REF] Haider | Approximate DCT Image Compression Using Inexact Computing[END_REF]. This constitutes a good predictor for area and power gains, as experimentally evaluated in Subsection 5.2, for both ASIC and FPGA. For convenience, in Table 2 we report, from [START_REF] Haider | Approximate DCT Image Compression Using Inexact Computing[END_REF], the number of transistors required to implement inaccurate cells of the mentioned IACs. Concerning the operating frequency, in this case the approximation does not entail any change, as further explained in Subsection 5.1. Let us detail the reward function. Let 𝑁 𝑜𝑝 be the number of operations required to compute the single-dimensional DCT and let 𝑛𝑎𝑏 𝑖 be the NAB for the i-th addition. We compute the total number of saved transistors as

𝑁 𝑜𝑝 -1 ∑ 𝑖=0 𝑛𝑎𝑏 𝑖 • (𝑇 𝐹𝐴 -𝑇 𝐼𝐴𝑖 ) , (13)
where 𝑇 𝐹𝐴 and 𝑇 𝐼𝐴𝑖 are the number of transistors required by the FAC and the i-th IAC, respectively. Finally, since the number of additions required by each algorithm varies, we use a normalized measure, as reported in the following equation:

𝜌 = 1 2 • 𝑁 𝑏𝑖𝑡𝑠 • 𝑁 𝑜𝑝 • 𝑇 𝐹𝐴 𝑁 𝑜𝑝 -1 ∑ 𝑖=0 𝑛𝑎𝑏 𝑖 • (𝑇 𝐹𝐴 -𝑇 𝐼𝐴𝑖 ) (14)
where 𝑁 𝑏𝑖𝑡𝑠 and 𝑁 𝑜𝑝 are the number of bits on which each of the sums is expressed and the number of sums required for the DCT computation, respectively.

Thanks to the so-defined reward function estimation, we are able to execute the DSE without performing any time-consuming syntheses of the approximate designs explored. This allows us to explore a lot more approximate designs, which would be infeasible otherwise. As a result of the DSE, we obtain the Pareto-optimal approximate designs in terms of accuracy and gains. Hence, we actually synthesize these designs to a particular technology.

EVALUATION AND EXPERIMENTAL RESULT

In this section, we firstly describe the hardware implementation of the DCT algorithm. Secondly, we validate the suitability of the chosen reward fitness function. Thirdly, we show our experimental setup and related result. Finally, we perform a comparison with previous work.

DCT algorithm hardware implementation

In order to be able -at the end of the DSE -to measure the final gains, we encoded all the above-mentioned DCT algorithms in VHDL. Such implementations guarantee high flexibility: they handle the configuration of both the type of adder cells to use for each addition and the number of bits to approximate (NABs). This allows the synthesis of any solution eventually found in the DSE process. VHDL implementations follow Equation ( 8 4; without loss of generality, the schema refers to BC12 [START_REF] Bayer | DCT-like Transform for Image Compression Requires 14 Additions Only[END_REF], since the differences between different algorithms are negligible.

The architecture of the one-dimensional DCT computing block is pipelined, with pipe registers separating the adders needed for the partial-sums computation. The one-dimensional DCT has three clock cycles latency; thus, the whole two-dimensional DCT block is six clock cycles latency. Each of the partial sums is performed using a configurable approximate adder. The scheme of a configurable approximate adder is depicted in Figure 5: it is a ripple-carry adder whose least significant bits are computed by IACs, while the most significant ones are computed by classical FACs. The number of approximate sums, i.e. IACs, is configurable by means of the NAB parameter.

The DCT is computed on 8 × 8 image tiles, each one made of three different color channels. Each element's value spans from 0 to 255. For this reason, each one of the single-dimensional DCT output terms can be expressed, at most, as the sum of eight elements. Therefore, the maximum value for the single-dimensional DCT terms is 8 × 255 = 2040 < 2048 = 2 11 .

As a consequence, the two-dimensional DCT output terms can have a maximum value of 8 × 2040 = 16320 < 16384 = 2 14 .

Manuscript submitted to ACM As a result, 14 bits turn out to be sufficient to represent the DCT frequency coefficients. It is also worth highlighting that replacing FACs with IACs leaves the overall structure unchanged. As anticipated in Subsection 4.2.3, this means that the approximation does not affect the latency nor the operating frequency of the device. Therefore, we can conclude that the maximum frequency of operation depends entirely on the target technology. In order to compute the maximum operating frequency for our hardware designs, we performed a preliminary FPGA and ASIC synthesis, varying NABs and IACs, while targeting a Xilinx Zynq-7020 FPGA and a 65nm Fin Field-Effect Transistor (FinFET) technology.

Preliminary synthesis confirmed our aforementioned observation: approximation does not impact on the operating frequency, which depend only on the target technology. Synthesis tools reported a maximum operating frequency in the 250MHz and 770MHz range for FPGA and ASIC, respectively.

Reward fitness function evaluation

As mentioned in Section 4.2.3, the reward fitness-function described in Equation ( 14) performs an estimation of the approximate designs gains. As the main advantage, such an approach enables an immediate gain estimation, without the need to resort to highly time-consuming circuit syntheses. This paves the way to a much wider exploration, thus to a more thorough DSE.

Despite such an advantage, it is not trivial to reveal the correlation between transistor reduction and FPGA resource savings. In order to validate Equation ( 14) as suitable gain estimator for FPGA, we conducted two preliminary experiments: (i) we synthesized several configurations of approximate adder by varying the IAC to be used and NABs in order to appreciate programmable resources overhead; (ii) we further synthesized several approximate configurations of DCT hardware accelerators on both a Xilinx Zynq-7020 FPGA and 65nm FinFET [START_REF] Huang | Sub 50-Nm FinFET: PMOS[END_REF] technologies. In these experiments, we did not measure the accuracy, since we are only interested in resource savings. As reported in Figure 6, there is an appreciable overhead reduction, in terms of occupied Look-Up Tables (LUTs), for any adder using IAC as NABs increase. Indeed, Boolean minimization process, performed during synthesis, gets more possibilities to reduce the size of circuits in terms of literals, fan-in and number of LUTs since truth tables of IACs are designed to simplify Boolean expressions [START_REF] Haider | Approximate DCT Image Compression Using Inexact Computing[END_REF]. Furthermore, we used different DCT algorithm hardware accelerators from the literature (BAS08 [START_REF] Saad Bouguezel | Low-Complexity 8$\times$ 8 Transform for Image Compression[END_REF], BAS09 [START_REF] Saad Bouguezel | A Fast 8×8 Transform for Image Compression[END_REF], BAS11 [START_REF] Saad Bouguezel | A Low-Complexity Parametric Transform for Image Compression[END_REF], BC12 [START_REF] Bayer | DCT-like Transform for Image Compression Requires 14 Additions Only[END_REF], CB11 [START_REF] Cintra | A DCT Approximation for Image Compression[END_REF], PEA12 [START_REF] Potluri | Multiplier-Free DCT Approximations for RF Multi-Beam Digital Aperture-Array Space Imaging and Directional Sensing[END_REF] and PEA14 [START_REF] Sadhvi Potluri | Improved 8-Point Approximate DCT for Image and Video Compression Requiring Only 14 Additions[END_REF]). For each accelerator, we gradually increased the NABs to observe the corresponding hardware resources trend.

Figures 7 and8 report the amount of LUTs and a comparison between reward estimation given by Equation ( 14) and the actual reward on FPGA, respectively, for each of the considered DCT algorithms. As for the former, an appreciable resource overhead reduction is observable; as for the latter, the actual reward trend is sufficiently close to the predicted one. As one can notice, the predicted reward from Equation ( 14) has the same slope as actual reward trend. Furthermore, the predicted reward is almost a lower bound for the actual reward, which is significantly relevant in order to achieve a fair DSE.

PEA14

Predicted Reward Actual Reward Fig. 8. Expected vs. actual reward for DCT algorithms on FPGA, varying the NABs 0.65%] and [0.82%, 2.44%], respectively for ASIC and for FPGA. Such low values of MAPE reveal that Equation ( 14) is an accurate estimator for the involved reward. Therefore, we concluded that Equation ( 14) is a suitable estimation to forecast approximation gains.

Experimental Setup

In this Section, we describe the experimental setup that we used in order to evaluate our approach. We considered seven different DCT algorithms and ten types of IACs. As for the DCT algorithms, we considered BAS08 [START_REF] Saad Bouguezel | Low-Complexity 8$\times$ 8 Transform for Image Compression[END_REF], BAS09 [START_REF] Saad Bouguezel | A Fast 8×8 Transform for Image Compression[END_REF], the error. The considered data set [START_REF]SIPI Image Database[END_REF], consists of 44 different images, covering a wide set of common features, including among others a flat gray scale, foreground subject with a messy background, and high contrast images.

Experimental Result

In this Section, we report experimental results. Firstly, we discuss the DSE results. Secondly, we discuss both silicon die area and power consumption reductions we achieved for designs resulting from DSE, synthesized on both FPGA and ASIC.

5.4.1 DSE results. Figure 10 reports the Pareto front provided by the MOEA for all the considered algorithms. The reference is, for each algorithm, its non-approximate implementation, depicted as a gold star. It is important to bear in mind that such algorithms are non-exact DCT versions (see Section 4) and that the JPEG implemented with a non-exact DCT algorithm produces lower-quality images compared to its exact version. For this reason, the reported non-approximate solutions exhibit already some error. Their reward value is zero, since they do not use any IACs, so they do not achieve any approximation gain according to Equation 14. As envisioned, the graphs highlight increasing expected rewards as the error increases. Intel i7-3770 CPU running at 3.9 GHz. On that hardware platform, the DSE for each algorithm took about 20 hours to complete. Therefore, thanks to the proposed fitness-function (Equation 14), we only needed few days to complete the exploration for all the algorithms. Indeed, by simply evaluating the proposed fitness-function, we avoided performing a circuit synthesis to compute the reward. In fact, on the same hardware platform, the ASIC synthesis tool requires, on average, of 22 minutes to accomplish a single synthesis, while the FPGA tool needs 30 minutes (17 for synthesis and 13 for technology mapping), on average. Considering that the MOEA configurations had a population of 2000 individuals (i.e., 4000 circuit variants to synthesize at each iteration), performing the first of the seven iterations alone would have required 22 × 4000 = 88000 minutes -i.e., about 60 days -for ASIC technology.

It is worth noting that exhaustive DSE is undoubtedly unfeasible, even in the case evaluating a single solution requires negligible time, since the size of solution spaces ranges between 2.66 × 10 49 ≈ 2 164 and 1.081 × 10 80 ≈ 2 265 .

After the DSE, to correctly evaluate the final gains, we synthesized the obtained approximate configurations to both ASIC and FPGA technologies. Over all the algorithms, the total number of obtained non-dominated approximate configurations to synthesize was 164, i.e., ≈ 24 per each algorithm, on average. For the reader convenience, in the following figures we plotted the experimental result data along with the corresponding first-order interpolation to highlight the trend.

ASIC Synthesis.

We synthesized all the obtained non-dominated approximate configurations to ASIC, by using the 65nm FinFET [START_REF] Huang | Sub 50-Nm FinFET: PMOS[END_REF] technology and the Cadence Genus Synthesis Solution tool. We resorted to the synthesis reports for the silicon die area of the approximate configurations. In Figure 11 consumption, to determine whether the synthesis power report provides a satisfying accuracy, we simulated the whole workload for two algorithms (BAS08 and BAS09) and collected the resulting power consumption. As a result, we realized that the difference between the power consumption resulted from the workload simulation and that estimated by the synthesis tool only differed by 5%, on average. We considered the synthesis report accuracy sufficient, thus in Figure 12 we show the power results from the synthesis report. Kindly note that the scale on the left axis (static power) is different from the scale on the right axis (dynamic power).

Power savings are achieved due to both the reduced area and the lower switching activity that IACs exhibit w.r.t FACs, as also reported in [START_REF] Haider | Approximate DCT Image Compression Using Inexact Computing[END_REF].

It is worth highlighting that the trends shown in Figures 11 and12 are perfectly in line with the trend predicted by our approach (see Figure 10). Indeed, higher reward in Figure 10 corresponds to lower area/power in Figures 11 and12.

For the reader convenience, Table 3 reports a summary of the minimum and maximum area/power savings we achieved during the experimental campaign while targeting ASIC. 5.4.3 FPGA Synthesis. We synthesized all the obtained non-dominated approximate configurations to a Xilinx Zynq-7020 MPSoC. To get a fair estimation of hardware requirements, we used only its embedded FPGA and inhibited Digital Signal Processors (DSPs) usage.

Figure 13 reports synthesis result in terms of number of LUTs for all the considered algorithms. As expected, approximate solutions require less resources than the precise implementation, as highlighted by the decreasing general trend.

In order to correctly evaluate energy savings, we performed a post-synthesis timing simulation, using the Dynamic Power Analysis tool provided by the Xilinx Vivado. In this case, since the synthesis report has a very low confidence level for power consumption estimation, we resorted to a workload simulation for all the solutions the DSE provided, for all the algorithms. In this way, we achieved a high confidence level power estimation.

Figure 14 shows static and dynamic power consumption for all the algorithms.

The static power of the FPGA is largely caused by the fabric of the device and does not directly depend on used resources, while dynamic one is directly linked to the user design, due to the input data pattern and the design internal activity. Being our hardware implementations of approximate DCT characterized by low overhead, i.e., device resources usage falls between 6 and 13%, it is necessary to split power consumption in static and dynamic since the former turned out to be about an order of magnitude greater than the latter one for the target FPGA device. Also in this case, power savings are achieved thanks to both the reduced total area and the logical structure of IACs: FPGA LUTs implementing IACs have a lower switching activity than those implementing FACs, as reported in [START_REF] Haider | Approximate DCT Image Compression Using Inexact Computing[END_REF].

As in the ASIC case, also for FPGA the trends shown in Figures 13 and14 are perfectly in line with the trend predicted by our approach (see Figure 10). Indeed, higher reward in Figure 10 corresponds to lower area in Figures 13.

As done for ASIC, we report a summary of the minimum and maximum area/power savings we achieved during the experimental campaign while targeting FPGA in Table 4.

Visual Test.

Since JPEG belongs to image processing domain, we also provide a visual test: Figure 15 shows, from left to right, the standard JPEG-compressed image of Lena and Baboon, the same images compressed using the exact Manuscript submitted to ACM We analyzed and modeled several algorithms from the literature to compute a fast and lightweight version of the DCT.

For each algorithm, we applied approximation by substituting full-precise adders with several approximate ones from the literature having configurable approximation degree. In this way, we can obtain different approximate configurations of the algorithms, depending on the chosen approximate adders and their approximation degree. Approximate adders introduce inaccuracy in the computation, but also achieve gains in terms of area and power consumption. For each algorithm, we performed a DSE to find the non-dominated approximate designs in terms of trade-off between inaccuracy and gains. We modeled the DSE as a MOP and we used a GA to solve it.

After the DSE, we synthesized the obtained designs by targeting both FPGA and ASIC. To do so, we implemented all the algorithms as re-configurable hardware designs. Finally, we evaluated the actual gains in terms of area and power consumption. Experimental results clearly showed that, with the proposed approach, it is possible to perform a meaningful DSE to find the best trade-offs between output accuracy and resource gains in a reasonable time. Finally, the comparison performed with previous work clearly showed the advantages of the proposed approach.

Fig. 2 .

 2 Fig. 2. The NSGA-II selection strategy.

Fig. 3 .

 3 Fig. 3. RTL block schema for the BC12-2D hardware implementation

Fig. 4 .Fig. 5 .

 45 Fig. 4. RTL block schema for the BC12-1D hardware implementation

Fig. 6 .

 6 Fig. 6. Area requirements of 16 bits adders on FPGA, varying the NABs

Finally, we measured

  the Mean Absolute Percentage Error (MAPE) between the reward values predicted by Equation[START_REF] Cintra | A DCT Approximation for Image Compression[END_REF] and the actual ones from the syntheses, for both FPGA and ASIC. The measured MAPE ranges between [0.33%,

Fig. 7 .

 7 Fig. 7. Area requirements of DCT algorithms on FPGA, varying the NABs

Fig. 10 .

 10 Fig. 10. Pareto-front estimation provided by the MOEA

  , we report the result. Concerning the power

Fig. 11 .

 11 Fig. 11. ASIC silicon die area (𝜇𝑚 2 )

Fig. 12 .

 12 Fig. 12. Power consumption estimation for ASIC (nW)

Fig. 13 .Fig. 14 .

 1314 Fig. 13. FPGA resource requirements

  version of the BC12 algorithm[START_REF] Bayer | DCT-like Transform for Image Compression Requires 14 Additions Only[END_REF] -which exhibit a DSSIM of 0.10, and requires 125473.92 𝜇𝑚 2 and 5691946 𝜇𝑊 when implemented on ASIC, or 5902 LUTs and 107933980 𝜇𝑊 while targeting FPGA -and, finally, the ones compressed with its approximate variant having 0.33 as DSSIM value and 0.22 of reward, which correspond to 8362.64 𝜇𝑚 2 and 352.711𝜇𝑊 saved for ASIC and 1846 LUTs and 94506.744𝜇𝑊 saved for FPGA. As the reader can easily figure out, the quality differences are barely perceivable.

Fig. 16 .

 16 Fig. 15. Visual test

  𝑞}, i.e., the set of individuals 𝑞 which are dominated by 𝑝. Individuals in the highest rank subset of 𝑅 𝑖 , i.e. 𝐹 1 , have 𝑛 𝑝 = 0. Then, for each 𝑝 : 𝑛 𝑝 = 0, each 𝑞 ∈ 𝑆 𝑝 is visited and 𝑛 𝑞 is decremented by one. If the term 𝑛 𝑞 becomes zero, 𝑞 is placed in the second-highest rank subset of 𝑅 𝑖 , i.e. 𝐹 2 . The procedure is iterated until each subset is fully identified.

formed exploiting crossover and mutation, then sorted on the basis of non-domination, and finally split in subsets {𝐹 1 , • • • , 𝐹 𝑚 }; (ii) individuals from the highest rank subsets 𝐹 1 are preserved in the next iteration; if the amount of surviving individuals from 𝐹 1 is less than N, individuals from lower rank subsets 𝐹 2 • • • 𝐹 𝑙 are also preserved, and they survive for the next iteration; (iii) in order to select exactly 𝑁 individuals from 𝑅 𝑖 , individuals from the last non-rejected non-domination subset 𝐹 𝑙 are sorted on the basis of the crowding distance, and selected using the crowded selection operator (4). Manuscript submitted to ACM In order to perform non-domination sorting, for each individual 𝑝 ∈ 𝑃, the NSGA-II computes (i) the non-domination count 𝑛 𝑝 = |𝐷 𝑝 |, 𝐷 𝑝 = {𝑞 ∈ 𝑃 : 𝑞 ≺ 𝑝}, i.e., the amount of individuals 𝑞 which dominate 𝑝, and (ii) the set 𝑆 𝑝 = {𝑞 ∈ 𝑃 : 𝑝 ≺

Table 1 .

 1 Comparison among DCT algorithms in terms of number of operations

	Method	Additions Multiplications Shifts Total operations
	DFT (definition)	432	192	0	624
	FFT	58	6	0	64
	DCT (definition)	56	64	0	120
	Arai algorithm	29	5	0	34
	BAS08 [9]	18	0	2	20
	BAS09 [10]	18	0	0	18
	BAS11 [8] (a=0)	16	0	0	16
	BAS11 [8] (a=1)	18	0	0	18
	BAS11 [8] (a=2)	18	0	2	20
	CB11 [14]	22	0	0	22
	BC12 [7]	14	0	0	14
	PEA12 [29]	24	0	6	30
	PEA14 [28]	14	0	0	14

Table 1 .

 1 Splitting 𝐶 allows integers-only matrix multiplications. Indeed, 𝑇 contains only the values {0, ± 1 multiplication of 𝐷 in (6) still requires floating-point operations. In fact, 𝐷 is a diagonal matrix consisting of values in the [-1, 1] range, with { 1 2 , 1

	√	, 1 √
	2	8

Table 2 .

 2 Transistor count from[START_REF] Haider | Approximate DCT Image Compression Using Inexact Computing[END_REF] for inexact-adder cells

	Cell	Full Adder AMA1 AMA2 AMA3 AMA4 AXA1 AXA2 AXA3 InXA1 InXA2 InXA3
	Transistors	58	20	14	11	14	8	6	8	6	8	6

Table 3 .

 3 Minimum and maximum savings while targeting ASIC

	Algorithm	Area Savings (%) Power Savings (%) min max min max
	BAS08	9	25	5	20
	BAS09	5	15	5	15
	BAS11	5	12	9	13
	BC12	6	27	6	25
	CB11	5	17	3	10
	PEA12	7	17	5	15
	PEA14	5	23	4	18

Table 4 .

 4 Minimum and maximum savings for FPGA synthesized approximate configurations

	Algorithm	LUTs Savings (%)	Dynamic Power Savings (%)
		min	max	min	max
	BAS08	27.5	48.2	0.1	3.4
	BAS09	32.6	42.5	0.3	1.8
	BAS11	30.6	40.4	0	2.5
	BC12	31.1	50.8	0	5.2
	CB11	30.9	42.7	0.5	2.6
	PEA12	31.3	42.7	0.7	4.4
	PEA14	29.2	44.5	0.1	2.8

Manuscript submitted to ACM

, ±1, ±2} and it is orthogonal, i.e. 𝑇 ′ = 𝑇 -1 ⇒ 𝑇𝑇 ′ = 𝑇 ′ 𝑇 = 𝐼 , where 𝐼 is the identity matrix. Note that multiplying by[START_REF]SIPI Image Database[END_REF] 2 or 2 comes down to shifting to the right or to the left, respectively; this, at hardware level, is reduced to simple wiring. This means 𝑇 allows computing the DCT using only additions. Nevertheless, the Manuscript submitted to ACM

ACKNOWLEDGMENTS

Authors would like to thank Andrea Aletto for his technical support during experimental campaigns.

BAS11 [START_REF] Saad Bouguezel | A Low-Complexity Parametric Transform for Image Compression[END_REF], BC12 [START_REF] Bayer | DCT-like Transform for Image Compression Requires 14 Additions Only[END_REF], CB11 [START_REF] Cintra | A DCT Approximation for Image Compression[END_REF], PEA12 [START_REF] Potluri | Multiplier-Free DCT Approximations for RF Multi-Beam Digital Aperture-Array Space Imaging and Directional Sensing[END_REF] and PEA14 [START_REF] Sadhvi Potluri | Improved 8-Point Approximate DCT for Image and Video Compression Requiring Only 14 Additions[END_REF]. As for the IACs families, we considered AMA [START_REF] Gupta | Low-Power Digital Signal Processing Using Approximate Adders[END_REF], AXA [START_REF] Yang | Approximate XOR/XNOR-Based Adders for Inexact Computing[END_REF] and InXA [START_REF] Haider | Inexact Designs for Approximate Low Power Addition by Cell Replacement[END_REF]. The considered DCT algorithms and approximate adders are the same considered by the authors of [START_REF] Haider | Approximate DCT Image Compression Using Inexact Computing[END_REF]. Figure 9 sketches our workflow as a whole: to speed up the simulation process, we modeled each of the abovementioned multiplier-less DCT algorithms by using C/C++ implementations straightly derived from equations [START_REF] Saad Bouguezel | A Low-Complexity Parametric Transform for Image Compression[END_REF] and [START_REF] Saad Bouguezel | A Fast 8×8 Transform for Image Compression[END_REF]. Starting from such implementations, the generation of approximate variants is performed using the Clang-Chimera tool, which is a Clang/LLVM-based C/C++ source-to-source mutation engine part of the IDEA framework [START_REF] Barbareschi | Automatic Design Space Exploration of Approximate Algorithms for Big Data Applications[END_REF][START_REF] Barbareschi | An Extendible Design Exploration Tool for Supporting Approximate Computing Techniques[END_REF].

For each DCT algorithm, the Clang-Chimera tool produces mutated sources which allow configuring, for each of the sums, both the NABs and type of adder cell to use (i.e., either FAC or IAC). Furthermore, as mentioned in subsection 4.2, we modeled the DSE as a MOP. The MOP resolution is performed by using the ParadisEO framework, a template-based evolutionary computation library [START_REF] Liefooghe | ParadisEO-MOEO: A Framework for Evolutionary Multi-Objective Optimization[END_REF]. In order to perform the hardware synthesis, non-dominated solutions from the DSE are employed to configure the VHDL implementation discussed in Section 5.1. Finally, we measure actual gains.

To find a suitable MOEA configuration, we conducted several DSE campaigns with different MOEA parameters. As a result, we deduced two things: (i) to obtain a populous frontier and avoid local sub-optimum, we need to increase the initial population size as much as possible; (ii) to avoid long-run exploration around local sub-optimum, mutations have to take place frequently. Hence, we set our MOEA parameters as follows: initial population equals to 2000 individuals, mutation and crossover probabilities set to 0.7 and 0.9, respectively. We did not set any maximum error threshold. Details on the fitness-functions employed for the DSE have been provided in Section 4.2.2 and Section 4.2.3. As mentioned in Section 4.2.2, we resort to the whole JPEG compression, performed on a representative data set, to estimate Manuscript submitted to ACM

Comparison with previous work

In this subsection, we compare the results obtained with our approach with those obtained in the work in [START_REF] Haider | Approximate DCT Image Compression Using Inexact Computing[END_REF]. Authors of [START_REF] Haider | Approximate DCT Image Compression Using Inexact Computing[END_REF] estimated gains 𝐺 through the following equations:

where 𝑉 𝑖 and 𝑉 𝑒 represent the average energy required to perform an addition, by an inexact N-bits adder and by an exact N-bits adder respectively, 𝑃 𝑖 and 𝑃 𝑒 represent the average energy required by a single IAC and by a full-adder cell, respectively. Values of 𝑃 𝑖 and 𝑃 𝑒 used in [START_REF] Haider | Approximate DCT Image Compression Using Inexact Computing[END_REF] were measured by using the 45nm Complementary Metal-Oxide Semiconductor (CMOS) technology and are reported in Table 5. Such equations have the same goal as Equation ( 14), i.e., predicting the gains achieved thanks to the approximation. While Equations ( 15) and ( 16) take into account the energy consumption parameters of the individual adder cell, Equation ( 14) takes into account only the number of transistors.

In [START_REF] Haider | Approximate DCT Image Compression Using Inexact Computing[END_REF], authors performed a manual exploration. In particular, firstly they tried different IACs and decided to always resort to InXA2 in their experiments, based on its energy delay product. Then, they tried different NAB values for the InXA2 adder and finally set it to 4 for all the experiments (i.e., for all the DCT algorithms). Besides, they used the PSNR metric to measure the JPEG error entailed by the approximate DCT variants. Conversely, we adopted the DSSIM index as error metric -which is more suitable for image processing -and we let the MOEA decide which inaccurate cell to use and how many bits to approximate (i.e., the NAB parameter) for each of the sums. A minor difference concerns the implementation of the adders: while 32-bit adders were considered in [START_REF] Haider | Approximate DCT Image Compression Using Inexact Computing[END_REF], we considered 14-bit adders.

In order to effectively compare the two studies, it is necessary to place them under the same conditions. Thus, we executed the JPEG algorithm on the same four images considered in [START_REF] Haider | Approximate DCT Image Compression Using Inexact Computing[END_REF] -i.e., Lena, Cameraman, Boat and Pepper -by using the approximate DCT variants obtained with our approach and computed the PSNR metric. Hence, we computed energy savings according to Equation ( 15), considering 32-bit adders. Figure 16 shows the obtained results. Concerning both energy consumption and PSNR, our approach allowed a significant improvement for all the considered algorithms compared to the approach adopted in [START_REF] Haider | Approximate DCT Image Compression Using Inexact Computing[END_REF]. In detail, our approach allowed an absolute improvement spanning from 15.69% to 20.15% (average 18.38%) concerning the energy gain and from 5.24 dB to 14.88 dB (average 7.91 dB) concerning the PSNR. Therefore, with our approach we were able to produce higher quality images, i.e., with less error, while consuming less energy. This is the result of the thorough DSE made possible by the proposed approach. Indeed, using a MOEA allows performing a multi-objective optimization more efficiently and automatically. Moreover, not needing to synthesize each approximate variant allows exploring more extensively the design space in a reduced time.

CONCLUSION AND FUTURE WORK

In this manuscript, we presented a novel generic and fully automatic approach for the approximation of DCT hardware accelerators. It enables automatic approximate DCT variant generation and automatic space exploration, by using the GA approach.