As-Is Approximate Computing

Owing to the performance and energy gains from approximation, various approximation frameworks have been explored in the literature. The state-of-the-art general-purpose approximation frameworks are often harder to adopt since they lack execution time proportional gains in accuracy and the ability to interrupt the execution once the accuracy expectations have been met [13, 14, 48]. Moreover, these frameworks often rely on accuracy recovery mechanisms in the event that the output is not adequately accurate [22]. Even though few specialized approaches enable time-proportional approximation and support interruptibility, they are limited to specific algorithms which are being accelerated with approximation and cannot be extended to benefit various different workloads [10, 16, 27, 35, 52]. Table 1 compares the proposed As-Is system against relevant prior work. Kickstarter leverages iterative computation for graph algorithms and calculates intermediate values for subset of vertices. However, unlike As-Is they do not explore other benchmarks or even guarantee interruptibility of the application [52]. Brainiac also supports time proportional approximation using neural accelerators; however, their implementation does not claim that approximate outputs can be retrieved at any time. As-Is on the other hand employs a best-effort approach which allows retrieval of both precise and intermediate outputs [16]. In contrast, Samoyed is able to support an intermittent system by adopting smaller operations which can complete, when a larger operation requires more energy than a device can offer. However, it does not employ any approximation to achieve this, unlike As-Is [35]. Truffle exhibits high energy savings by supporting a low voltage knob for approximate calculations, but this does not guarantee that it will be able to give outputs with varying degrees of accuracy based on how long the system is allowed to run. As-Is is able to take care of the latter scenario along with energy savings [13]. Aloe is able to effectively demonstrate program reliability, but if the program is partially executed, as in for a shorter time, the checkers will consider any intermediate outputs as unacceptable [22].

The Anytime automaton [39] leverages anytime algorithms [11, 19, 29] that have been widely used in decision planning and artificial intelligence, to tackle key challenges in approximate computing. In the anytime automaton, increasingly accurate approximate versions of the final output are computed and used to eventually produce the final precise output. A key feature that anytime automaton provides is program interruptibility. At any point, if the program is interrupted, the automaton simply produces a best-effort or as-is output based on previously executed computations. This feature is useful since the application can now be stopped as soon as the output quality meets user expectations, saving both runtime as well as energy. In cases where the output quality falls below expectations, the user simply needs to let the application run longer.

The anytime automaton computation model provides a mechanism to extract significant parallelism from seemingly sequential applications (details of applications in Section 4.2). It accomplishes this by breaking down an application into a pipeline of fine-grained anytime computation tasks that can execute in parallel.

An ordered irregular parallel application consists of tasks with the following properties [21]. First, tasks follow a total or partial order. Second, tasks are dynamically created and creation order is different from execution order. Third, tasks may have data dependencies that are not known a priori. Ordered irregular parallel algorithms are common in data mining [50], graph analytics [18, 43], and event-driven systems [41].

An anytime automaton can also be considered as an ordered irregular parallel application. This is because in anytime automaton, each computation stage \(A\) is broken down into N tasks (i.e., \(A_1\), \(A_2\), ..., \(A_N\)), where N is input-dependent and may not be known a priori. The parent-child relationships between tasks are known, but the data dependencies between tasks are unknown in advance. Each task is also assigned a timestamp and may create and enqueue child tasks with any timestamp equal to or greater than its own, leading to a total order among tasks.

Figure 2(a) shows an example program broken down into two computation stages \(S\) and \(f\). We will use the same example throughout the article. The stage \(S\) samples all the pixels of an input image and builds a histogram of pixel intensities. The stage \(f\) takes a histogram as input and computes the arithmetic average of all the pixels. The stage \(S\) is made anytime with bit-reverse sampling and anytime stage \(f\) leverages reduced precision approximation. The stage \(S\) is broken down into three tasks and stage \(f\) is broken down into two tasks (Figure 2(b)). An execution schedule of tasks is shown in Figure 2(c).

As-Is uses a task-based programming model to declare programs in the form of anytime automata. Programs are composed of computation stages arranged in a feed-forward dataflow, as shown in Figure 2(a). Explicit buffers are used to pass information between parent and child stages (Figure 2(b)). The programmer specifies \(M\) computation stages: \(S_0 ... S_{M-1}\), in a high-level language such as C, along with per-stage information regarding the input buffer location, output buffer location, and any applicable approximation techniques (e.g., random input sampling and reduced precision). We discuss supported approximations later in Section 3.2.3. An example annotated program for the anytime model in Figure 2 is shown in Listing 1.

Computation Stages. There are three types of computation stages that can be declared.

As per the nomenclature in numerical methods, diffusive stages in As-Is are mapped to iterative stages where repeated state updates improve the solution with some convergence rate. However, we use the above terminology to remain consistent with the prior work this article is based on [39].

Computation Tasks. Each anytime computation stage \(S_i\) is decomposed into \(N\) tasks: \(T_{Si,1} ...\) \(T_{Si,N}\). These tasks are either iterations of an iterative stage or steps of a diffusive stage. The output of an iterative stage is 100% accurate upon completion of task \(T_{Si,N}\), while the output of a diffusive stage is 100% accurate upon completion of all \(N\) tasks. In the Figure 2(b) example, anytime stages \(S\) and \(f\) are executed as three and two tasks, respectively.

The number of tasks per stage can either be programmer-specified or dynamically selected at run-time. In our implementation, we profiled our applications and manually specified the number of tasks. Automating this process is left for future work.

Pipeline. The feed-forward composition of tasks can be executed as a pipeline as shown in Figure 3. There are two types of pipeline interactions listed below. Our As-Is run-time system can infer the appropriate pipeline depending on the types of parent and child stages.

Example. Figure 3 illustrates these concepts in practice, for the example program in Listing 1. Figure 3(a) shows the baseline sequential execution of the program. The first stage sampling is composed of three tasks, while the second stage f is composed of two tasks. With iterative stages in an asynchronous pipeline (Figure 3(b)), each later task potentially recomputes results that were previously computed and overwrites the current output with a more accurate version. f(11xx) represents the output of the first task of stage f after processing the output of its parent task i.e., first task of stage S, whereas f(1122) represents the second and final output generated by the stage f over the same output from the first task of stage S.

With diffusive stages in an asynchronous pipeline, child stage f processes different versions of outputs produced by parent stage S as opposed to merely updates of them. However, with diffusive stages in a synchronous pipeline (Figure 3(d)), each later task builds directly on top of previously computed results, making the cumulative output more accurate.

This section describes the As-Is architectural components and how they operate in detail.

In this section, we present an example of Histogram equalization (histeq) execution on the As-Is system as depicted in Figure 8. (histeq) is commonly used to enhance the contrast of an image by scaling its pixel intensities. In this example, there are three computation stages—A, B, and C. Stage A is a diffusive stage and uses input sampling with pseudo-random permutations. Stage B is a precise stage without any approximations. Stage C is a diffusive stage that employs output sampling with bit-reverse permutation. Stage A has two tasks \(A_1\) and \(A_2\), stage B has one task and stage C has two tasks \(C_1\) and \(C_2\). Even though stage B has a single task, it has two \(\mu\)tasks since there are two parent tasks \(A_1\) and \(A_2\). Similarly, stage C has four \(\mu\)tasks. As the \(\mu\)tasks execute, they produce intermediate output \(O_1\), \(O_2,\) and \(O_3\) with increasing accuracy which translates to improved contrast for (histeq). Precise output O4 is produced in the end.

We simulate the proposed As-Is architecture on a custom cycle-level, event-driven microarchitectural simulator based on Pin [34]. The simulator models simple x86-based in-order cores running at 2 GHz. We simulate a two-level cache hierarchy where each core has a 32 kB private, write-through L1 cache, and all cores share a unified 2 MB L2 cache. In addition to traditional microarchitectural components, the simulator models As-Is overheads such as conflict detection, mis-speculation penalties of aborted tasks, and re-execution of aborted tasks in detail. For power analysis, we use McPAT’s [32] in-order core and memory hierarchy models at 32 nm logic.

We evaluate As-Is on a range of approximate applications from PERFECT [5], AxBench [53], and SNAP [28]. PERFECT contains kernels from the embedded computing domain whereas AxBench is an approximate computing benchmark suite. SNAP is used for analyzing the scope of approximation in large graphs. We focus on six widely used kernels from diverse application domains which can benefit from approximate computing. We divide each benchmark into computation stages and apply appropriate approximation techniques per computation stage. Each anytime computation stage is further split into \(\mu\)Tasks at the time of execution. Table 2 lists all the benchmarks along with the configuration used in the evaluation. We use normalized root mean square error (NRMSE) for measuring the error of intermediate approximate outputs. We compute accuracy (i.e., QoR) as (1- NRMSE) of the approximate output against the precise output.

The following approximate techniques in our evaluation:

Sampling techniques are amenable to anytime computing as data elements can be sampled with progressively decreasing granularity. For unordered data, to avoid bias in the memory ordering, data is sampled in a random manner. In our experiments, we use a simple LFSR implementation for random number generation. When the position of data is significant such as in images and videos, sampling data in bit-reverse or tree permutation can improve the accuracy of intermediate outputs. Reduced fixed point precision techniques can also be made anytime by computing data bits in the order of significant (most significant bit to least significant bit).

2dconv. 2d convolution is used in computer vision, signal processing, and machine learning. Each output pixel is computed by the average of dot product sum of input pixels and the filter. We retain all the computations of 2dconv in a single stage anytime automaton. 2dconv benefits from both tree sampling as well as reduced fixed point precision.

histeq. Histogram equalization improves image contrast by calculating the cumulative distribution of pixel intensities and is commonly used for thermal, satellite, and x-ray images. The anytime automaton of this benchmark consists of three three computation stages—Stage 1 processes all the input pixels, Stage 2 calculates the scaling factor of each pixel for better contrast, and Stage 3 builds the final image.

dwt. Discrete wavelet transform is employed in data compression. We construct an automaton with a single stage that performs a discretely-sampled wavelet transform on an image. We evaluate the accuracy of this kernel by executing inverse transform precisely and comparing it to the precise output.

kmeans. K-means clustering partitions pixels of an image to different clusters based on its distance from the nearest mean and used in data mining applications. In this three stage automaton, the first stage computes the cluster centroids and assigns pixels to clusters based on their Euclidean distances, the second stage computes the average centroid values and the last stage samples the pixels and re-assigns them to a clusters.

debayer. Debayering algorithm takes an undersampled image from an image sensor and overlays a color filter array, to create a complete color image. A single-stage automaton suffices the computational complexity involved in the interpolation needed to re-create the complete image. To accommodate the scope of multiple \(\mu\)Tasks, we apply a tree-based sampling.

centrality. Betweenness centrality is a metric based on shortest paths between nodes, and used extensively to analyze social networks. It takes an unweighted graph and uses the Brandes algorithm for calculating betweenness centrality which is the fraction of shortest paths that pass through n [28].

pagerank. Pagerank is used by search engines to evaluate the importance of a web page for deciding the order of search results. The pages act as nodes and the hyperlinks as the edges of a graph.

In our experiments, each benchmark is run with variable number of \(\mu\)Tasks per anytime computation stage. The runtime numbers for these experiments are normalized with respect to the baseline system that executes each computation stage as a single \(\mu\)Task.

In this section, we present the performance-accuracy tradeoffs enabled by our As-Is system. Figure 9, shows runtime-accuracy profiles for all the benchmarks on three configurations of \(\mu\)tasks each: 8, 16, and 32 on a 4 processor system. The y-axis represents accuracy in terms of (1- NRMSE) and the x-axis is run time normalized to the sequential execution of the same program. For a fair comparison, we also indicate the execution time of the parallel implementation of the same program using pthreads with 32 threads and 4 processors.

For all the applications, the As-Is system produces several outputs of high accuracy much earlier than the parallel baseline. In debayer, dwt, and 2dconv outputs with over 90% accuracy are produced as early as 1% of the sequential execution time as seen in the runtime-accuracy profiles in Figure 9(a), (b), and (c). These applications are embarrassingly parallel and thus, the precise output is reached faster with increasing number of \(\mu\)tasks with many tasks executing concurrently and probability of hazards with random sampling being low.

It is worth noting that 2dconv takes longer to reach the precise output. This is because 2dconv employs reduced precision approximation which helps in saving only the latency of multiplies and in our experiments, multiplies take only a small fraction of the run time. Even though reduced precision is one of the heavily studied approximation techniques, we find its utility is not as effective for the applications we studied for the following two reasons: (1) Reduced precision only seems to work for applications where the latency of arithmetic instructions dominates the execution time. (2) Reducing the precision creates RAW hazards among the tasks which prolong the time to reach the precise output.

K-means and histeq consist of three computation stages and perform many redundant computations to generate intermediate approximate outputs. For very large unweighted graphs, the centrality or pagerank computed after processing a small subset of nodes is highly representative and thus, both metrics start from a fairly high accuracy. However, all tasks end up updating each node’s centrality leading to more conflicts thus, resulting in almost sequential run time. In contrast, pagerank is embarrassingly parallel and takes 60% time to reach the precise output. Conflicts in pagerank primarily occur between \(\mu\)tasks from two stages, unlike centrality.

We now look at the trends observed in the runtime-accuracy profiles further by showing how long it takes to achieve 100% accuracy as we vary the number of \(\mu\)Tasks and processors in Figure 10. More processors present more opportunities to exploit parallelism. As a result, increasing the number of processors reduces the execution time for almost all the applications. Similarly, increasing number of \(\mu\)Tasks allows many tasks to execute concurrently. Thus, increasing the \(\mu\)Tasks from 8 to 32 in embarrassingly parallel applications like debayer, dwt, and 2dconv reduce the run time as seen in Figure 10(a), (b), (c), and (f).

Though the first stage of pagerank is embarrassingly parallel, pagerank has a second stage that is non-anytime. Thus, higher number of \(\mu\)Tasks in the first stage lead to more redundant executions of the non-anytime second stage. This is the general trend for all benchmarks that have a non-anytime stage, i.e., pagerank, histeq, and kmeans. With many tasks trying to access similar data, the conflict rate of tasks increases. Thus, for these benchmarks, the runtime to achieve 100% accuracy increases with the number of \(\mu\)Tasks due to increased conflicts and redundant execution. As all the \(\mu\)Tasks in centrality update the same data, the runtime is less affected by increase in number of available processors. Centrality is more prone to hazards with increase in \(\mu\)Tasks as all the tasks modify the same centrality table.

We compare As-Is with a software only implementation, shown in Figure 11 for 8 \(\mu\)Tasks and 4-processor configuration. As-Is reaches 95% accuracy 1.22\(\times\) –11.89\(\times\) faster than the software implementation, due to significant software overheads. As expected, the applications that take longer to achieve 95% accuracy see significant benefits from As-Is over the benchmarks that achieve high accuracy within the first few \(\mu\)Tasks.

Figure 12 presents a comparison of As-Is hardware and software components with the closest relevant speculative architecture [21] for 32 \(\mu\)Tasks and 4 processor configurations. We analyze the speedup from As-Is system by comparing the runtime-accuracy profiles for three different configurations: (1) As-Is hardware and software (2) As-Is software with baseline speculative hardware and (3) baseline application with baseline speculative hardware.

The As-Is software component breaks down the application in \(\mu\)Tasks that generate increasingly accurate outputs whereas the baseline software application would generate only one final output. In As-Is, the potential conflicts among tasks are statically predetermined due to the nature of our synchronous and asynchronous pipelines. As-Is leverages the knowledge of potential conflicts to utilize the system better by letting tasks abort without re-executing them while trying to produce best-effort approximate outputs. However, a baseline speculative system would instead treat all the tasks as mandatory and force them to finish by re-executing them on every conflict. Moreover, in As-Is, producer-consumer relationships between stages are known a priori. This allows As-Is to deal with the false dependencies introduced because of the shared buffer between the stages by opting for lazy versioning and conflict detection, in contrast to the eager versioning and eager conflict detection of the baseline speculative system.

For all the benchmarks except centrality, As-Is achieves highly accurate outputs earlier than the other configurations. Centrality has lots of hazards and faster conflict resolution from eager conflict detection and versioning speeds it up on the baseline architecture.

Figure 13 presents the distribution of benefits from approximation alone and approximation along with speculation. For most benchmarks, unlocking the available parallelism with speculation gives significant benefits than just employing approximation techniques. However, there are two exceptions to these trends: centrality and histeq. Because of the partitioning of the histogram buckets there are lots of read and write conflicts in building the histogram and the earlier tasks get aborted very frequently upon parallelization. Similarly, centrality is also hurt by speculation because of lots of collisions between tasks.

Figure 14 presents the impact of cache block size on As-Is system performance. We study the performance of debayer application with cache block sizes of 4 B, 16 B, and 64 B. Large cache blocks reduce the number of cold misses. However, they also introduce false sharing of data. Our results indicate that the locality benefits of a larger cache block outweigh the resulting false sharing and increased conflicts among tasks.

The results reported so far correspond to a single input image or graph. However, to account for variability across different inputs, we run all the benchmarks across four different inputs and mean and standard deviation between runtimes to reach 90% accuracy scaled to the sequential baseline on a 32 \(\mu\)Tasks and 4 processor system is reported in Figure 15.

As-Is adds three additional hardware overheads: (1) 32 entry task queue (0.34 mm\(^2\)) (2) 16 kB dual port SRAM bloom filters (0.05 mm\(^2\)) and (3) 7 registers for sampling approximation (0.0007 mm\(^2\)). We use CACTI [33] to compute these areas at 32 nm ITRS-HP technology node. Overall these structures consume 4.4% additional area over the baseline speculative system [21].

The power overheads of the As-Is system are presented in Table 3. The y-axis is the average power to reach 100% accuracy on As-Is normalized to the average power of the pthreads implementation. In As-Is, the benchmarks have 32 \(\mu\)Tasks in total and the pthreads implementation employs 32 threads. Both configurations are run on a 4 processor system.

Kmeans, debayer and 2dconv incur high power overheads. In fact, kmeans takes 2.2\(\times\) power to reach 100% accuracy due to increased runtime and conflicts with a larger number of \(\mu\)tasks as observed in Figures 9 and 10. However, power consumption of histeq, dwt, centrality, and pagerank is at par with the baseline.

As-Is does enable significant energy savings for earlier approximate outputs. The fraction of energy spent on As-Is to achieve 80%, 85%, and 90% accuracy normalized to the energy consumed by parallel baseline is reported in Figure 16, given 32 \(\mu\)Tasks and a 4-processor configuration. Even though the kmeans power is 2.3\(\times\) that of parallel baseline as shown in Table 3 and the runtime to reach 100% accuracy is also 2\(\times\) that of parallel baseline as shown in Figure 9, As-Is is able to produce 80% accurate output with only 0.84\(\times\) energy of parallel baseline.

In Figure 17 we compare As-Is with other state-of-the-art approximate computing approaches like EnerJ [48]. For 2dconv benchmark with 4 bit reduced precision, EnerJ is able to achieve 97.04% accuracy and to reach the same level of accuracy, As-Is consumes 0.65\(\times\) energy when compared to Enerj.

Since diffusive tasks build on top of the previous output whereas iterative tasks overwrite the output buffer, all the diffusive computation stages can be expressed as iterative stages. Thus, from the efficiency perspective, we opted to implement stages as diffusive instead of iterative whenever possible to minimize the redundant computations. However, we perform a case study to compare diffusive and iterative implementations of the single-stage pagerank automaton in Figure 18 for 32 \(\mu\)Tasks and 4-processor configuration. With iterative stages even though it takes much longer for the precise output to be generated, outputs with high accuracy are still generated within 5% of the baseline runtime.

As-Is being an interruptible system, it would be hard to provide a dynamic accuracy mechanism that automatically infers when it is appropriate to terminate the program, given a desired user accuracy threshold. We train several regression-based models in order to gauge the runtime for a programmer-specified accuracy.

Currently, As-Is imposes programmer effort in porting over any application, breaking it into anytime computing stages and annotating it with the relevant information. With follow-on work on compilers, much of this effort can be avoided or reduced. However, this effort is currently outside the scope of this article. Our evaluation is based on simulations and even though this is common for research works in the architecture community, we understand that the benefits of the As-Is platform may look different on a real system. We believe that the current evaluation is highly reflective of the performance and energy savings on a realized As-Is system. We have not done a comprehensive search of the application space, particularly bigger and end-to-end applications, but we expect them to only strengthen our evaluation.