NEAT: A Framework for Automated Exploration of Floating Point Approximations

While there has been a substantial amount of effort aimed towards finding new forms of approximation [69, 63, 56, 36, 70, 37, 50, 1, 17, 80, 25, 61, 65], there is a lack of solutions that helps the user to both develop their own approximation methods, and then specifying the approximation level to enforce for a single application.

Hardware approximation computes inexactly in return for reduced energy, area, or time [49, 14]. Approximate multipliers [81, 44, 46] and adders [20, 84] are widely advocated for energy-efficient computing. State-of-the-art neural network training platforms offer 16 bit floating point hardware systems that provide up to 4x performance gain comparing to traditional 32 bit systems [29]. Recent proposals promote putting many different approximate units or customized accelerators on a single core [31]. Thus, it is beneficial to include multiple FPUs on a chip for higher energy efficiency[22] but this requires tedious hand-tuning. Therefore, the challenge is how to figure out which FPU to use in each part of the program. This is the challenge that motivates NEAT.

Languages support approximation allowing the specification of variants for key functionality and formal analysis of their effects [3, 9, 55]. Approximation Knobs provide a way to lend performance and energy gains to existing power knobs[43]. Quora is a quality programmable processor where the notion of quality is codified in the instruction set of the processor [73]. Another example of user-defined approximation is Green, which is a system that allows programmers to supply approximate versions of loops and while-blocks that terminate early [4]. On the contrary to these programming language techniques, our proposal lets users easily—through our programmable substitution rules—examine and change the accuracy of FLOPs, giving them more control over the floating point computations in a program.

Performing precision tuning at fine grain is available through software libraries. EnerJ proposes to declare approximate data via type qualifiers[65]. MPFR adds to its arbitrary-precision representation the support for rounding modes, exceptions and special values as defined in the IEEE 754 standard[30]. FlexFloat reduces floating point emulation time by providing a C/C++ interface for supporting multiple FP formats. These techniques require source code instrumentation (changing $float$ and $double$ variables definition to custom parameters) or intending to yield more precise computation (for instance floating points numbers with more than 128 bits). NEAT focuses on energy efficiency by reducing precision while only requiring the program binary.

Convolutional Neural Networks (CNNs) include a significant amount of floating point computation in the training and inference stages. A large body of research has been focused towards CNN precision scaling[64, 72, 62, 32, 15, 33]. For example, WAGE quantizes weights to 2 bits while activation, errors, and gradient are 8 bits respectively[79]. FLEXpoint presents a new format with 16 bits mantissa to train CNNs with full precision[45]. Another piece of research demonstrates the successful training with 8-16 bits floating point numbers with full accuracy[77]. Other, tangentially related approaches create networks with early exit points [75, 76], but those are not related to the problem of changing numerical precision. Prior approaches either change the training architecture or apply a coarse-grain precision level for all layers. Differently, NEAT generates precision tuning analysis at different granularities by offering WP and CIP solutions without modifying the application internal structure or exhaustive precision exploration.

While prior work mainly develops mechanisms that enable approximation to provide energy and runtime savings at different domains, they do not help users make more informed decisions about approximation. These techniques mostly are not flexible about how much, where, and when to approximate, and only provide discrete approximation knobs which leads to more conservative design choices. NEAT does not propose new mechanisms but helps users answer the questions above.

Current inexact functional units in addition to approximate software libraries create an opportunity to exploit quality-energy tradeoffs. While an FPU accounts for 2-5% area on the chip, the floating point instructions consume significantly more energy compared to other classes of instructions such as integer, memory, and control[54, 5]. Figure 1 illustrates the energy per instruction (EPI) results for different classes of instructions of 64-bit 32nm processor. With random operands, a 64-bit floating point add consumes 400 pJ, and a division operation could go as high as 680 pJ. For a 32-bit versions, the energy consumption is 350 and 420 pJ respectively.

As expected with regards to the type of operations, executing the floating point instructions emerges as a major contributor to the total energy consumption. Recent empirical studies have shown up to 50% of the energy consumed in a core and memory is related to floating point instructions[54]. Thus, exploiting reduced bitwidth at instruction level (bit truncation) to generate Floating Point Implementations (FPI) could facilitate higher energy efficiency. Another useful insight from Figure 1 is the relationship between computation and memory accesses. For example, three add operations consume the same amount of energy as a ldx instruction. Hence, looking from an energy efficiency point of view, reducing the memory traffic could be as efficient as optimizing the floating point arithmetic operations[54].

A body of literature has focused on providing tool supports that allow users to define several approximations for different components of the application [66, 17, 60, 25, 37, 63, 56, 36]. Petabricks provides language extensions that expose tradeoffs between time and accuracy to the compiler[3]. The compiler then runs dynamic autotuning to generate optimized elements to achieve the target accuracy. However, autotuners need to be determined on a per-application basis by the user. OpenTuner provides fully-customizable configuration representation and ensembles of search techniques to find an optimal solution[2]. Both autotuning techniques are supposed to help programmers but Petabricks requires a separate language and both require users to implement all alternatives before the search can be conducted. NEAT also helps users deal with approximation, but instead of requiring users to implement all possible alternatives, they simply describe programmable rules that are then used to automatically generate the alternatives.

Hence, there is a need for a generic framework that provides multiple precision levels, accommodates custom user-defined floating point implementation, and does not require code refactoring. NEAT provides such a solution. NEAT generates insightful information for precision tuning at function level for floating point programs.

User inputs of NEAT includes: a user application to instrument, a precision level as the optimization target, the desired FP arithmetic implementations, and a set of FPI to function mappings (programmable placement rules).

NEAT receives the binary of the program and instruments the floating point instructions. Unlike other precision tuning tools, NEAT does not require the source code of the program. Then, NEAT expects the optimization target which can be either single or double precision. There are two reasons behind including optimization objective. First, for most of the programs, the same precision level is held across the code base for the data structures and the functions. Second, if we consider both $float$ and $double$ FLOPs to optimize, the configuration space of FPIs combinations would explode excessively.

Next, users specify multiple FPIs for any individual arithmetic instruction such as addition, subtraction, multiplication, and division for each operand. At last, NEAT expects a mapping between the candidate code sections and the FPIs to calculate each FLOP in a program. By default, NEAT enforces the FPIs at the function level, meaning all FLOPs executed within a specific function will be using the same customized FPI. Any function that has at least one FLOP can be considered as a candidate for approximation.

The NEAT dynamic instrumentation tool was written in C++ using the Intel Pin instrumentation system [51]. NEAT performs run-time instrumentation to facilitate the analysis and replacement of floating-point arithmetic operations during the execution of compiled C and C++ binaries.

There are five outputs from this tool: the output from the user application, a trace of the operands and result of every FLOP executed by the program, the estimated FPU energy of FLOPs in the execution of the program, the estimated energy of off-chip memory accesses of the program, and the number of FLOPs executed per function in the program.

The trace of the FLOPs executed by the instrumented application is written to a file while the application is running. If FPIs are supplied to NEAT by the user, the result of each operation will be printed after the operation is calculated with the chosen FPI. The operands and result of each operation are printed as hexadecimal numbers so that there is no confusion in rounding the floating-point values.

NEAT reports total energy consumed in FPU by using energy per instruction (EPI) of different classes floating-point operations. We extracted the energy model of $fadd$, $fmul$ and $fdiv$ for single and double precision operations provided in related work [54].

To this end, NEAT counts the number of bits manipulated in the operands and results of every FLOP in the instrumented program. Modifying the bit width in the exponent and sign of a floating-point number changes the accuracy significantly where the quality of output becomes unacceptable. Hence, NEAT only focuses on mantissa bits. NEAT counts the number of zeroes in the binary representation of the floating-point number, starting with the least significant bit, and then subtracts it from available mantissa bits in the floating type (24/53 bits in single/double precision respectively) to calculate the number of manipulated bits. NEAT uses the EPI models and the number of manipulated bits per FLOP to estimate the total floating-point energy consumed in the FPU.

NEAT also records the total number of bits used in FLOPs in the execution of the program is output to a file after the termination of the application. Unlike the FPU energy estimation, this metric can be used as a platform-independent way to evaluate the approximate amount of power used by FLOPs when instrumenting a program.

Currently, the memory accounts for more than 25% of energy spent in a large scale system. While on average, each single precision FLOP takes 400 pJ to execute, a byte read from memory consumes 1.5 nJ [8]. Accordingly, NEAT counts the total number of bits transmitted to/from memory and then estimates the total memory access energy of the instrumented program [53]. This allows NEAT to yield a better energy estimation of the program in a real system.

NEAT generates in-detail statistics about the floating point instructions in the program. Users might operate NEAT to profile the application before performing precision tuning to first, decide whether NEAT is useful to their application and second, what type of FPIs, which functions, and how to map them.

In general, NEAT is a tool used at program design time. NEAT allows users to evaluate many points on the accuracy/energy tradeoff curve without having to implement all possible alternatives. After profiling with NEAT, users can then select a point and implement it with confidence that it will provide the desired behavior.

Future work would explore additional machione learning techniques to configure the floating point usage differently for different functions in the program [19, 58, 59, 39]. Another promising line of work is using a runtime system to dynamically tune floating point usage to maintain either energy or accracy constraints in a changing workload [41, 57, 40, 27, 52, 34, 26, 28, 78, 38, 6], or possibly implementing this control scheme in hardware [67, 83, 68].

We evaluate NEAT by exploring the tradeoff spaces of the placement rules for a variety of benchmarks. Table II lists the applications from Parsec 3.0 [7] and Rodinia 3.1 [13] suites with the configuration space size (default precision optimization target) and training and test inputs for each benchmark. These benchmarks cover domains from finance to image processing.

To create FPIs, we use bit truncation. For the single precision floating point numbers ($float$ type in C), we have 24 different FPIs corresponding to the mantissa bits. Similarly, we created 53 FPIs for the double precision floating point numbers. For the whole-program approach, the size of the tradeoff space is the total number of possible FPIs which are 24 and 53 points. For the per-function approaches, we consider the top 10 functions with most FLOPs to enforce the FP rules, so each of the top 10 functions may use a different FPI.

In each experiment, at most 400 configurations in the tradeoff space (less than $6^{-12}$ of all possible configurations) have been evaluated through NEAT’s genetic algorithm.

NEAT can be used to analyze the type, distribution, and the intensity of the FLOPs in a program. Figure 4 depicts the ratio of single and double precision FLOPs for each benchmark.

Most of the benchmarks hold the same precision level across the source for correctness and portability. For example, Bodytrack, Heartwall, and Kmeans are all implemented with $float$ type while Canneal is mainly using $double$. However, for some benchmarks such as Ferret, Particlefilter, and Srad due to including external libraries, there is a mixture of both precision levels. In this case, users might choose the optimization target to be enforced. Specifying the right target opens up further opportunities for additional energy savings.

NEAT provides the FPU energy estimation consumed by the FLOPs. We compare two rules: whole program (WP) and currently-in-progress (CIP). As a reminder, WP uses one floating point implementation through the entirety of the program, while CIP is free to choose a separate implementation for each of the top 10 functions (by FLOP count) in the program. For Particlefilter, we set the optimization target to double precision as most of the FLOPs are $double$. For the rest of the benchmarks, we apply the single precision optimization.

We consider the top 10 FLOP intensive functions for the CIP placement. Although, one might ask how much of the FLOPs are included in the top 10 functions. For all benchmarks, at least 98% FLOPs were coming from the top 10 functions, thus NEAT covers almost all of the FLOPs in the program.

Figure 5 illustrates the lower convex hull of normalized FPU energy and the error rate (also referred to as accuracy loss). The error rate metric is the relative error of a configuration comparing against the highest quality configuration (baseline) where no approximation happens. The horizontal axis is the error rate while the Noramlized Energy Consumption (NEC) to the baseline is shown vertically (on the y-axis). The lower the curve is, the more efficient configuration is found which means higher energy efficiency. Since users generally do not care about extremely inaccurate outputs, only error rates less than 20% is shown in the subfigures. The results show that f we assign multiple FPIs at the function level, NEAT will retrieve more energy efficient configurations that are not explorable if we use single FPI for the whole program. This result further demonstrates NEAT’s value in design space exploration.

With a minimal error in final output of the benchmark, NEAT reduces the FPU energy up to 60%. For some applications such as Blackscholes, Fluidanimate, and Particlefilter the FPU energy savings are more considerable. These benchmarks have less than 10 FLOP intensive functions. Therefore first, CIP covers all the FLOPs in the program. Second, since the tradeoff space is relatively smaller, NSGA-II searches a larger portion of the tradeoff space in the same exploration time.

For Fluidanimate and Ferret benchmarks, there are only three and two configurations where the WP outperforms the CIP. The reason is that NEAT’s genetic algorithm fails to explore those specific configurations as it is a heuristic algorithm. The same pattern can be seen for the Radar benchmark as well where the CIP does not dominate the whole-program approach.

The Heartwall benchmark has only two FLOP functions where they are very sensitive to the bit width adjustment and any modification leads to more than 20% error. Consequently, NEAT is not able to decrease FPU energy to less than 71% of the baseline with reasonable error rate. The opposite scenario happens for the Particlefilter application where the major FLOP functions do not impact the quality of output considerably, hence NEAT aggressively reduces the FPU energy without causing much error.

For a more detailed comparison, we re-illustrate a quantized representation of the previous plot. Figure 6 displays how the FPU energy savings enhance as the tolerated error threshold increases. Higher bars indicate more energy savings. By harmonic mean, applying the CIP versus WP approach results in 7%, 12%, and 13% more energy savings at 1%,5%, and 10% error rate, respectively.

The steeper slope in the lower convex hull curves in subplots of Figure 5 translates into higher bars in Figure 6 as the error threshold increases. The Blackscholes and Particlefilter benchmarks demonstrate such behavior. On the contrary, by increasing the error threshold in Particlefilter and Radar applications, the FPU energy savings do not inflate similarly.

From these graphs, we draw two conclusions. First, specifying the FPIs placement at a finer granularity results in more efficient FPI to function mappings. In other words, per-function rules use less energy with the same error comparing to use a single FPI for the whole application. This type of insight is really only achievable with the an automated system like NEAT. Second, if higher error rates are allowed, NEAT achieves higher efficiency of FPU energy. Thus, NEAT can navigate the whole tradeoffs space and give users a range of options depending on tolerable error rate.

Main memory (DRAM) consumes as much as half of the total system power in a computer today, due to the increasing demand for memory capacity and bandwidth [53]. Hence, reducing the memory traffic directly derives into substantial energy savings. NEAT estimates the memory energy with accounting only accesses to/from an off-chip memory by keeping track of memory operations such as MOVSS and MOVSD. Figure 7 depicts memory accesses energy for a range of error rates for both whole-program (WP) and per-function (CIP) approaches respectively across the benchmarks. Same as before, higher bars indicate higher energy efficiency. Values are normalized to non-approximated version of the application, that acts as a baseline. On harmonic mean, increasing the error rate from 1% to 10% results in 3.2-10.5% less energy consumption.

If the FLOP functions are memory intensive, reducing the precision bits results in lower memory bandwidth, and consequently more energy savings. That is the reason why benchmarks such as Bodytrack, Fluidanimate, and Radar reduces the memory energy by more than 60%. In rest of the benchmarks, the FLOP functions were solely compute intensive.

To put the experiments above to a conclusion, we illustrate the WP rule as a sample for prior work [79] which tries to find a single most optimal approximation for the whole application. The per-function rules of NEAT show off the ability of the replacement rules to allow programmers to explore a richer set of tradeoffs without having to come up with whole new implementations of existing program functionality.

In previous sections, we observed some benchmarks have a mixture of both $float$ and $double$ FLOPs. To choose the right optimization target, we compare the energy and accuracy of selected benchmarks in both single and double optimization targets. The FPI to function mapping is CIP in this experiment.

Figure 8 shows the normalized energy savings for both single and double optimization targets. As expected, if we choose the optimization target to be the same as the FP type which has larger ratio in FLOP distribution, higher energy savings would be achieved. This observation can be easily justified by the looking back at Section V-B. Both Canneal and Particlefilter contain more 64-bit than 32-bit FLOPs. Thus, double precision as NEAT directive is the right choice to achieve substantially higher energy efficiency.

Ferret requires special attention as it is not obvious how to choose the optimization target based on FLOP distribution ratio since it has almost equal amount of $float$ and $double$ FLOPs. At the 10% error rate, NEAT saves up to 92% of FPU energy corresponding to $double$ instructions while only 38% savings is available if we consider only $float$ instructions. There are two reasons for the discrepancy. One is that generally $double$ FLOPs yield more precise output, but they use more precision bits in return. Thus, NEAT has more freedom to cut down unnecessary floating point bits while not losing much accuracy because the $double$ baseline is already more accurate than the $float$ one. Second, the $double$ functions in Ferret are not accuracy sensitive, meaning that enforcing approximation on these functions would not excessively change the quality of the output. This is a great example of how NEAT determines the most efficient configurations for any benchmark regardless of how their floating point precision is specified in the source (or binary).

As we mentioned in section III-B4, if we map an FPI to a function, depending on the caller, the quality of output could change. While on most benchmarks, CIP and FCS approaches produce the same result, on the Radar they differ. Hence, we examine the impact of the caller of the FFT function on the energy and accuracy of the benchmark. Figure 9 illustrates the FPU energy savings normalized to a baseline for CIP and FCS placement rules. FCS was able to explore a handful of more optimal configurations, resulting in 7% more energy savings at 1% accuracy loss comparing to CIP without extra runtime overhead. At 5% and 10% error rate, the additional energy savings are 4% and 2% respectively.

Since we employ a heuristic exploration technique, we ensure that NEAT produces statistically sound results by evaluating each application with multiple inputs divided into training and test sets. We take the median of normalized accuracy loss and FPU energy for each set of inputs, compute a linear least squares fit of training data to test data, and compute the correlation coefficient of each fit. Higher correlation coefficients imply less input sensitivity; i.e. the behavior of configurations found during training data is a good predictor of test behavior.

Table III show the correlation coefficient (R-values) for accuracy loss and FPU energy for each benchmark. Due to heuristic nature of exploration technique, it might be possible to select configurations that perform differently on unseen data. For instance, Kmeans clearly stresses the difference between training and test inputs. Although, all benchmarks have uniformly high R-values on accuracy loss and FPU energy—at least $0.93$. This demonstrates that NEAT’s search techniques are robust and the accuracy and energy results they predict on training inputs hold up well for test inputs. The robustness of the energy results is, perhaps, not surprising as those should be highly predictable (simpler FLOP implementations should predictably lower energy). The robustness of the accuracy results is perhaps more surprising as it not intuitively obvious that floating point implementations that work well for one set of inputs would also work for another set.

The energy and resource constraints in neural networks creates an intriguing challenge. More recently, a growing body of literature have tried to sacrifice the precision of training and inference for the lower runtime and energy consumption[16]. NEAT can be used to identify the FLOP intensive sections of the network and then provide the minimum precision required for the computation without considerable model accuracy reductions. This tradeoff (small accuracy loss for large energy savings) is well known, and we perform this study not to claim a new result here, but to demonstrate that NEAT’s automated approach can produce the same types of savings for this problem that have been produced by human domain experts. We also believe that using NEAT’s programmable replacement rules to create DNNs with differing precision throughout the network is a new contribution that would (due to the size of the search space) be quite difficult even for human experts.

We use a hand-written digit classification with the MNIST dataset which includes 60K images and 10K labels. For the CNN, we consider the LeNet-5 model with the architecture summary listed in Table IV. The LeNet-5 architecture consists of two sets of convolutional and average pooling layers, followed by a flattening convolutional layer, then two fully-connected layers and finally a softmax classifier[48].

Figure 10 shows the FLOPs breakdown for CNN training with minibatch size of 4, learning rate of 1, and 30 epochs. We first measured how much of the operations are floating point to determine the applicability of NEAT. For the inference, more than 73% of operations were FLOPs which makes NEAT absolutely beneficial to apply. Next, we analyze the FLOP distribution between the layers. We observe that more than 69% of floating point computation happens in the convolutional layers where they extract interesting features in an image. Activation phases and internal compute functions are responsible for the majority of remainder. Finally, we show that the number of FLOPs decreases as we approach the latter layers of the CNN since the size of transferred data between layers reduces as well.

To apply the FPI to function placement rules for a CNN, there are two options. First, apply one FPI per layer category (we refer to as PLC) meaning that all convolutional layers use the same precision level. The second approach is to apply a different FPI Per Layer Instance (PLI) where in this case the first and third layers might use distinct precision levels, however, they are both convolutional layers.

Picking the right FPI placement policy is not trivial for the CNNs. Unlike the WP versus CIP rules where one has significantly larger tradeoff space, the PLC and PLI tradeoff spaces are both large enough that heuristic exploration is required. Thus, any of these rules could outperform the other with the same exploration time. For the PLC, NEAT explores a larger portion of the tradeoff space, leading to locating efficient configurations more quickly. On the other hand, PLI examines FPI mappings at a finer granularity, hence it has a higher chance of discovering more optimal configurations.

Figure 11(a) illustrates the lower convex hull of normalized FPU energy and accuracy for both approaches. The accuracy loss is the error difference to the baseline configuration without approximation. The baseline recognition accuracy in the inference stage is 99.04% with a full accurate trained model. Each point in the tradeoff space demonstrates an FPI to layer (category or instance) mapping. Closer points to the origin indicate higher energy efficiency.

As can be seen, the lower convex hull of the PLI (finer granularity) outperforms the PLC curve for the error rates of less than 20%. The quantized representation of FPU energy versus error rates tradeoff space is shown in Figure 11(b) for both PLC and PLI placements. Similar to previous evaluation, finer granularity results in higher energy efficiency. With 1%, 5%, and 10% accuracy loss, NEAT with PLI placements achieves 6%, 4%, and 3% more energy savings compared to the default configuration.

NEAT’s programmable placement rules allow developers to analyze various precision levels for different components of their neural network without requiring them to instrument the source code or re-design the architecture.

Since the FPIs are based on the bit truncation of mantissa, using the above analysis, NEAT finds the required precision bits for each layer in the LeNet-5 network under accuracy loss constraints. By default, each layer is implemented with single precision floating point numbers (24 mantissa bits) bits. Table V demonstrates the mantissa bits required for every layer in the network. These precisions could later be integrated with the MPFR library in C [30] or mpmath library in Python [42].