QRD and SVD processor design based on an approximate rotations algorithm

A silicon implementation of the Approximate Rotations algorithm capable of carrying the computational load of algorithms such as QRD and SVD, within the real-time realisation of applications such as Adaptive Beamforming, is described. A modification to the original Approximate Rotations algorithm to simplify the method of optimal angle selection is proposed. Analysis shows that fewer iterations of the Approximate Rotations algorithm are required compared with the conventional CORDIC algorithm to achieve similar degrees of accuracy. The silicon design studies undertaken provide direct practical evidence of superior performance with the Approximate Rotations algorithm, requiring approximately 40% of the total computation time of the conventional CORDIC algorithm, for a similar silicon area cost. © 2004 IEEE.

Exchange-correlation energy and potential as approximate functionals of occupied and virtual Kohn-Sham orbitals: Application to dissociating H-2

The standard local density approximation and generalized gradient approximations fail to properly describe the dissociation of an electron pair bond, yielding large errors (on the order of 50 kcal/mol) at long bond distances. To remedy this failure, a self-consistent Kohn-Sham (KS) method is proposed with the exchange-correlation (xc) energy and potential depending on both occupied and virtual KS orbitals. The xc energy functional of Buijse and Baerends [Mol. Phys. 100, 401 (2002); Phys. Rev. Lett. 87, 133004 (2001)] is employed, which, based on an ansatz for the xc-hole amplitude, is able to reproduce the important dynamical and nondynamical effects of Coulomb correlation through the efficient use of virtual orbitals. Self-consistent calculations require the corresponding xc potential to be obtained, to which end the optimized effective potential (OEP) method is used within the common energy denominator approximation for the static orbital Green's function. The problem of the asymptotic divergence of the xc potential of the OEP when a finite number of virtual orbitals is used is addressed. The self-consistent calculations reproduce very well the entire H-2 potential curve, describing correctly the gradual buildup of strong left-right correlation in stretched H-2. (C) 2003 American Institute of Physics.

A Significance-Driven Programming Framework for Energy-Constrained Approximate Computing

Approximate execution is a viable technique for energy-con\-strained environments, provided that applications have the mechanisms to produce outputs of the highest possible quality within the given energy budget.
We introduce a framework for energy-constrained execution with controlled and graceful quality loss. A simple programming model allows users to express the relative importance of computations for the quality of the end result, as well as minimum quality requirements. The significance-aware runtime system uses an application-specific analytical energy model to identify the degree of concurrency and approximation that maximizes quality while meeting user-specified energy constraints. Evaluation on a dual-socket 8-core server shows that the proposed
framework predicts the optimal configuration with high accuracy, enabling energy-constrained executions that result in significantly higher quality compared to loop perforation, a compiler approximation technique.

Approximate credal network updating by linear programming with applications to decision making

Credal nets are probabilistic graphical models which extend Bayesian nets to cope with sets of distributions. An algorithm for approximate credal network updating is presented. The problem in its general formulation is a multilinear optimization task, which can be linearized by an appropriate rule for fixing all the local models apart from those of a single variable. This simple idea can be iterated and quickly leads to accurate inferences. A transformation is also derived to reduce decision making in credal networks based on the maximality criterion to updating. The decision task is proved to have the same complexity of standard inference, being NPPP-complete for general credal nets and NP-complete for polytrees. Similar results are derived for the E-admissibility criterion. Numerical experiments confirm a good performance of the method.

Generalized loopy 2U: A new algorithm for approximate inference in credal networks

Credal networks generalize Bayesian networks by relaxing the requirement of precision of probabilities. Credal networks are considerably more expressive than Bayesian networks, but this makes belief updating NP-hard even on polytrees. We develop a new efficient algorithm for approximate belief updating in credal networks. The algorithm is based on an important representation result we prove for general credal networks: that any credal network can be equivalently reformulated as a credal network with binary variables; moreover, the transformation, which is considerably more complex than in the Bayesian case, can be implemented in polynomial time. The equivalent binary credal network is then updated by L2U, a loopy approximate algorithm for binary credal networks. Overall, we generalize L2U to non-binary credal networks, obtaining a scalable algorithm for the general case, which is approximate only because of its loopy nature. The accuracy of the inferences with respect to other state-of-the-art algorithms is evaluated by extensive numerical tests.

Generalized Loopy 2U: A New Algorithm for Approximate Inference in Credal Networks

Credal nets generalize Bayesian nets by relaxing the requirement of precision of probabilities. Credal nets are considerably more expressive than Bayesian nets, but this makes belief updating NP-hard even on polytrees. We develop a new efficient algorithm for approximate belief updating in credal nets. The algorithm is based on an important representation result we prove for general credal nets: that any credal net can be equivalently reformulated as a credal net with binary variables; moreover, the transformation, which is considerably more complex than in the Bayesian case, can be implemented in polynomial time. The equivalent binary credal net is updated by L2U, a loopy approximate algorithm for binary credal nets. Thus, we generalize L2U to non-binary credal nets, obtaining an accurate and scalable algorithm for the general case, which is approximate only because of its loopy nature. The accuracy of the inferences is evaluated by empirical tests.

Approximate Computing with Unreliable Dynamic Memories

Embedded memories account for a large fraction of the overall silicon area and power consumption in modern SoC(s). While embedded memories are typically realized with SRAM, alternative solutions, such as embedded dynamic memories (eDRAM), can provide higher density and/or reduced power consumption. One major challenge that impedes the widespread adoption of eDRAM is that they require frequent refreshes potentially reducing the availability of the memory in periods of high activity and also consuming significant amount of power due to such frequent refreshes. Reducing the refresh rate while on one hand can reduce the power overhead, if not performed in a timely manner, can cause some cells to lose their content potentially resulting in memory errors. In this paper, we consider extending the refresh period of gain-cell based dynamic memories beyond the worst-case point of failure, assuming that the resulting errors can be tolerated when the use-cases are in the domain of inherently error-resilient applications. For example, we observe that for various data mining applications, a large number of memory failures can be accepted with tolerable imprecision in output quality. In particular, our results indicate that by allowing as many as 177 errors in a 16 kB memory, the maximum loss in output quality is 11%. We use this failure limit to study the impact of relaxing reliability constraints on memory availability and retention power for different technologies.

Exploiting Significance of Computations for Energy-Constrained Approximate Computing

Approximate execution is a viable technique for environments with energy constraints, provided that applications are given the mechanisms to produce outputs of the highest possible quality within the available energy budget. This paper introduces a framework for energy-constrained execution with controlled and graceful quality loss. A simple programming model allows developers to structure the computation in different tasks, and to express the relative importance of these tasks for the quality of the end result. For non-significant tasks, the developer can also supply less costly, approximate versions. The target energy consumption for a given execution is specified when the application is launched. A significance-aware runtime system employs an application-specific analytical energy model to decide how many cores to use for the execution, the operating frequency for these cores, as well as the degree of task approximation, so as to maximize the quality of the output while meeting the user-specified energy constraints. Evaluation on a dual-socket 16-core Intel platform using 9 benchmark kernels shows that the proposed framework picks the optimal configuration with high accuracy. Also, a comparison with loop perforation (a well-known compile-time approximation technique), shows that the proposed framework results in significantly higher quality for the same energy budget.

A two-competitive approximate schedulability analysis of CAN

Consider the problem of deciding whether a set of n sporadic message streams meet deadlines on a Controller Area Network (CAN) bus for a specified priority assignment. It is assumed that message streams have implicit deadlines and no release jitter. An algorithm to solve this problem is well known but unfortunately it time complexity is non-polynomial. We present an algorithm with polynomial time-complexity for computing an upper bound on the response times. Clearly, if the upper bound on the response time does not exceed the deadline then all deadlines are met. The pessimism of our approach is proven: if the upper bound of the response time exceeds the deadline then the response time exceeds the deadline as well for a CAN network with half the speed.

Approximate cost of completing the railway from Port Dalhousie to St. Catharines and an estimate of the cost of the piers at Port Dalhousie signed by William Hamilton Merritt

Approximate cost of completing the railway from Port Dalhousie to St. Catharines and an estimate of the cost of the piers at Port Dalhousie signed by William Hamilton Merritt (5 pages, handwritten), July 8, 1854.

Approximate estimate of the cost of completing the Port Dalhousie Railway to the Grand Central Railway Station at Lock 12

Approximate estimate of the cost of completing the Port Dalhousie Railway to the Grand Central Railway Station at Lock 12. This document is badly torn and burned but most of the text is legible, July 14, 1854.

Approximate estimate of the cost of constructing and completing the Port Dalhousie and Thorold Railway to St. Catharines

Approximate estimate of the cost of constructing and completing the Port Dalhousie and Thorold Railway to St. Catharines signed by S.D. Woodruff (2 pages, handwritten), Jan. 8, 1855.

Approximate estimate of the cost of extending the Port Dalhousie and Thorold Railway from Geneva Street to the Great Western Railway Station at Lock no. 12

Approximate estimate of the cost of extending the Port Dalhousie and Thorold Railway from Geneva Street to the Great Western Railway Station at Lock no. 12 (2 copies) [one appears to be a rough copy] (2 pages, handwritten), Feb. 2, 1855.

Memorandum respecting differences between the approximate and the final estimate

Memorandum respecting differences between the approximate and the final estimate (3 ¼ pages, handwritten), n.d.

Second copy of the memorandum respecting differences between the approximate and final estimate but this one has “memorandum of extras of Brown and McDonall contract” written on the outer page

Second copy of the memorandum respecting differences between the approximate and final estimate but this one has “memorandum of extras of Brown and McDonall contract” written on the outer page (3 pages, handwritten), n.d.