Highly distributed training of Deep Neural Networks (DNNs) on future compute platforms (offering 100 of TeraOps/s of computational capacity) is expected to be severely communication constrained. To overcome this limitation, new gradient compression techniques are needed that are computationally friendly, applicable to a wide variety of layers seen in Deep Neural Networks and adaptable to variations in network architectures as well as their hyper-parameters. In this paper we introduce a novel technique - the Adaptive Residual Gradient Compression (AdaComp) scheme. AdaComp is based on localized selection of gradient residues and automatically tunes the compression rate depending on local activity. We show excellent results on a wide spectrum of state of the art Deep Learning models in multiple domains (vision, speech, language), datasets (MNIST, CIFAR10, ImageNet, BN50, Shakespeare), optimizers (SGD with momentum, Adam) and network parameters (number of learners, minibatch-size etc.). Exploiting both sparsity and quantization, we demonstrate end-to-end compression rates of ∼200× for fully-connected and recurrent layers, and ∼40× for convolutional layers, without any noticeable degradation in model accuracies.

The state-of-the-art hardware platforms for training deep neural networks are moving from traditional single precision (32-bit) computations towards 16 bits of precision - in large part due to the high energy efficiency and smaller bit storage associated with using reduced-precision representations. However, unlike inference, training with numbers represented with less than 16 bits has been challenging due to the need to maintain fidelity of the gradient computations during back-propagation. Here we demonstrate, for the first time, the successful training of deep neural networks using 8-bit floating point numbers while fully maintaining the accuracy on a spectrum of deep learning models and datasets. In addition to reducing the data and computation precision to 8 bits, we also successfully reduce the arithmetic precision for additions (used in partial product accumulation and weight updates) from 32 bits to 16 bits through the introduction of a number of key ideas including chunk-based accumulation and floating point stochastic rounding. The use of these novel techniques lays the foundation for a new generation of hardware training platforms with the potential for 2-4 times improved throughput over today's systems.

Convolution is a critical component in modern deep neural networks, thus several algorithms for convolution have been developed. Direct convolution is simple but suffers from poor performance. As an alternative, multiple indirect methods have been proposed including im2col-based convolution, FFT-based convolution, or Winograd-based algorithm. However, all these indirect methods have high memory overhead, which creates performance degradation and offers a poor trade-off between performance and memory consumption. In this work, we propose a memory-efficient convolution or MEC with compact lowering, which reduces memory overhead substantially and accelerates convolution process. MEC lowers the input matrix in a simple yet efficient/compact way (i.e., much less memory overhead), and then executes multiple small matrix multiplications in parallel to get convolution completed. Additionally, the reduced memory footprint improves memory sub-system efficiency, improving performance. Our experimental results show that MEC reduces memory consumption significantly with good speedup on both mobile and server platforms, compared with other indirect convolution algorithms.

In-place radix sort is a popular distribution-based sorting algorithm for short numeric or string keys due to its linear run-time and constant memory complexity. However, efficient parallelization of in-place radix sort is very challenging for two reasons. First, the initial phase of permuting elements into buckets suffers read-write dependency inherent in its in-place nature. Secondly, load balancing of the recursive application of the algorithm to the resulting buckets is difficult when the buckets are of very different sizes, which happens for skewed distributions of the input data. In this paper, we present a novel parallel in-place radix sort algorithm, PARADIS, which addresses both problems: a) "speculative permutation" solves the first problem by assigning multiple non-continuous array stripes to each processor. The resulting shared-nothing scheme achieves full parallelization. Since our speculative permutation is not complete, it is followed by a "repair" phase, which can again be done in parallel without any data sharing among the processors. b) "distribution-adaptive load balancing" solves the second problem. We dynamically allocate processors in the context of radix sort, so as to minimize the overall completion time. Our experimental results show that PARADIS offers excellent performance/scalability on a wide range of input data sets.

An important part of software maintenance is fixing software errors and bugs. Static analysis based tools can tremendously help and ease software maintenance. In order to gain user acceptance, a static analysis tool for detecting bugs has to minimize the incidence of false alarms. A common cause of false alarms is the uncertainty over which inputs into a program are considered legal. In this paper we introduce evidence-based analysis to address this problem. Evidence-based analysis allows one to infer legal preconditions over inputs, without having users to explicitly specify those preconditions. We have found that the approach drastically improves the usability of such static analysis tools. In this paper we report our experience with the analysis in an industrial deployment.

A falsifier is a tool for discovering errors by static source-code analysis. Its goal is to discover them while requiring minimal programmer effort. In contrast to lint-like tools or verifiers, which try to maximize the number of errors reported at the expense of allowing "false errors", a falsifier's goal is to guarantee no false errors. To further minimize programmer effort, no specification or extra information about the program is required. That, however, does not preclude project-specific information from being built in. The class of errors that are detectable without any specification is important not only because of the low cost of detection, but also because it includes errors of portability, irreproducible behavior, etc., which are very expensive to detect by testing. This paper describes the design and implementation of such a falsifier, and reports on experience with its use for design automation software. The main contribution of this work lies in combining data-flow analysis with symbolic execution to take advantage of their relative advantages.

The effective use of don't cares requires solving several theoretical and practical problems. The theoretical problems are caused by a need to have all tools in a methodology use a consistent semantics of don't cares, so as to guarantee correctness of the final implementation. Several common meanings of "don't care" will be considered, and their respective conditions for design correctness will be derived. The main theoretical result shows that in existing design languages, the following three desirable properties are mutually inconsistent: unrestricted use of non-Boolean values (e.g., X), implementing a large design one partition at a time, and assurance of correctness of the final implementation. A practical solution to this problem involves several issues: specifying don't cares in a language description, deriving them during high-level synthesis, and optimizing logic in their presence. Experimental results showing the impact of don't cares on logic quality are presented.

This paper studies the confidence with which power can be estimated at various levels of design abstraction. We report the results of experiments designed to evaluate and identify the sources of inaccuracies in gate-level power estimation. In particular, we are interested in power estimation during logic synthesis. Factors that may invalidate or diminish the accuracy of pourer estimates include optimization, technology mapping, transistor sizing, physical design, and choice of input stimuli.

This paper describes optimization techniques using don't-care conditions that span the domain of high-level and logic synthesis. The following three issues are discussed: (1) how to describe and extract don't-care conditions from high-level descriptions; (2) how to pass don't-care conditions from high-level to logic synthesis; and (3) how to optimize the logic using don't-care conditions. Efficient techniques are given for these three problems which allow the use of large don't-care sets. Results from several examples demonstrate that these techniques are very effective for both area and delay minimization.

It is commonly expected that any correct implementation can replace its specification inside a larger design without violating the correctness of the whole design. This property (called replaceability) is automatically satisfied in the absence of don't cares because "correctness" by definition implies that specification and implementation compute the identical function. However don't cares allow an implementation to compute a different function, and thus make it difficult to ensure replaceability. Whether this problem occurs depends on the exact meaning of "don't care" and the associated definition of "correctness". We will consider three meanings of "don't care" and for each give conditions under which correct implementations may replace their specifications.

The paper describes some of the synthesis controls in the BooleDozer synthesis system which are unique in concept and implementation. Rather than attempting to achieve the maximum amount of optimization in the minimum amount of run time, the designer specifies the restructuring level which allows him to specify to what extent the original structure should be preserved. We also describe controls which affect the mapping process. Finally we describe the incremental synthesis feature. The run time can be accurately controlled by a run-time budgeting mechanism.>

Various defects during fabrication have been shown in the literature to introduce delay faults in logic circuits. This paper analyzes the effects of these defects on the normal operation of logic circuits with the goal of developing an appropriate model for these faults. Single and multiple delay faults in this model are analyzed to determine if they are redundant with respect to the normal operation of the logic circuit. The relationships between delay redundancies and stuck-at redundancies are discussed. The redundancy identification techniques are applied to various benchmarks circuits and experimental data are presented.>

The problem of checking equality of Boolean functions can be solved successfully using existing techniques for only a limited range of examples. We extend the range by using a test generator and the divide and conquer paradigm.

Conditions for generating optimal two-level AND-EXOR representations using rewrite rules are considered. Four results are presented. First, it is shown that a necessary condition for obtaining minimality is a temporary increase in the size of expressions during minimization. Second, a sufficient condition for obtaining minimality that consists of adding certain two rules to rule sets proposed in the literature is given. Third, transformations that allow the minimization of an expression to proceed by minimizing a transformed expression instead are defined. Fourth, it is determined experimentally that the above three theoretical results lead to better benchmarks results as well.>

Simulation is today the most common form of verification. One disadvantage of simulation is the excessive number of tests needed for complete coverage. However, as will be shown, the number of tests may be substantially reduced if test case generation is combined with a structural analysis. The resulting set of test cases for exhaustive simulation may be smaller than exponential, which might make exhaustive simulation feasible. Even if the set of test cases is still too large, choosing tests from this reduced set results in better coverage than otherwise.>

While simulation is today the most common form of verification, one disadvantage is the excessive number of tests needed for complete coverage. However, the number of tests may be substantially reduced if test case generation is combined with a structural analysis. The resulting set of test cases for exhaustive simulation may be smaller than exponential, which might make exhaustive simulation feasible. Even if the set of test cases is still too large, choosing tests from this reduced set results in better coverage than otherwise.>

Gate delay faults can represent the effects of common point faults in logic circuits. A gate delay fault model based on the analysis of these effects in the normal operation of logic circuits is developed. The fault model allows for delay faults of both bounded and unbounded size. Techniques have been developed to identify single gate delay faults that do not have any effect on the normal operation of logic circuits. These techniques are applied to various benchmark circuits and indicate the existence of a surprisingly large number of such redundancies.>

A method of synthesizing scan designs that are testable with pseudorandom patterns is presented. The logic is first simplified by various transformations in a logic synthesis system. A fault simulator is then used to guide the placement of control points and observation points. In order to reduce the overhead, control points are shared when possible and a condensation network is used with the observation points. Experimental results which indicate that pseudorandom testability can be achieved with small area overheads using simple techniques are presented.>

A general optimization algorithm, which in some areas successfully competes with simulated annealing and the Kernighan-Lin algorithm, as well as special heuristics, is presented. It gains speed by taking advantage of the structure of the objective function in order to reduce the search space. Results obtained from the implementation of the algorithm on three problems are presented.>

The usual block-oriented timing analysis for logic circuits does not take into account functional relations between signals. If functional relations are taken into consideration, it could be found that a long path is never activated. This results in more accurate delays. A comparison is made of three arrival time functions, A, B, and R. A is the arrival time as given by exhaustive simulation; B is the arrival time as calculated by a usual block-oriented algorithm; and R is the arrival time, that does functional analysis. It is shown that B contained in R contained in A. The first relation means that R is never more conservative than B and whenever the containment is proper, R is an improvement over B. The second relation means that R is correct in the sense that it will never assert a signal to be valid when it is not valid according to the ideal A. Experimental results showing how often R is an improvement over B are presented.>

Systems which synthesize logic implementations from specifications have moved, under the pressure of production requirements, from Boolean minimizers to procedures attempting to satisfy a wider range of criteria. Gate or cell count, taken as a measure of area, continues to be a major factor in design acceptability, but timing constraints, testability, wirability, and efficient use of available primitives are important as well. Additional information, such as “don't care” conditions, can be used to improve the design quality. This paper describes how these requirements are specified to and enforced by the Logic Synthesis System (LSS), a tool which has been used in production on gate array chips. Trade-offs between varying requirements, and their effect on the logic produced, are discussed and illustrated with a standard set of examples.

In an MOS transistor network information can propagate through transistors and connections in both directions. Sometimes, however, it is intended to propagate in one direction only. Propagation in the wrong direction, causing a so called sneak path, could result in a functional error. We present an almost linear algorithm for detecting such sneak paths. Only consistent sneak paths, i.e., only paths that can possibly conduct, can cause a functional error; therefore, the algorithm allows inconsistent sneak paths to be left in the network. It does so without actually examining any paths, which would be too inefficient.

A model of commumcations protocols based on finite-state machines is investigated.The problem addressed is how to ensure certain generally desirable properties, which make protocols "wellformed," that is, specify a response to those and only those events that can actually occur.It is determined to what extent the problem is solvable, and one approach to solving it ts described.

A signal in a logical network is called redundant if it can be replaced by a constant without changing the function of the network. Detecting redundancy is important for two reasons: guaranteeing coverage in stuck-fault testing, and simplifying multilevel logic without converting to two levels. In particular, removing redundancy allows simplification in the presence of don't cares. The algorithm for redundancy removal described in this paper has been used successfully for both of the above purposes. It achieves savings in computer resources at the expense of possibly failing to discover some redundancies.

A version of the standard high level data link control protocol has been verified as an experiment with an automated verification system. This paper tries to answer questions such as: How can HDLC and its properties be represented? To what extent can they be proved? What are the main obstacles in verifying protocols like HDLC?

The production of error-free protocols or complex process interactions is essential to reliable communications. This paper presents techniques for both the detection of errors in protocols and for prevention of errors in their design. The methods have been used successfully to detect and correct errors in existing protocols. A technique based on a reachability analysis is described which detects errors m a design. This "perturbation technique" has been implemented and has successfully detected inconsistencies or errors in existing protocol designs including both X.21 and X.25. The types of errors handled are state deadlocks, unspecified receptions, nonexecutable interactions, and state smbiguities. These errors are discussed and their effects considered. An interactive design technique is then described that prevents design errors. The technique is based on a set of production rules which guarantee that complete reception capability is provided in the interacting processes. These rules have been implemented in the form of a tracking algorithm that prevents a designer from creating unspecified receptions and nonexecutable interactions and monitors for the presence of state deadlocks and ambiguities.

ABSFRACT A method for proving and disprowng propemes of programs ts described Its mam features are Recurstvely defined procedures can be used m assemons, loop mvarlants are not necessary, absence of run time errors is proven, counterexamples to incorrect programs can be given Experience with the method's lmplemen-taUon is reported.

A method for proving theorems in first order predicate calculus theories with equality is described and proven complete. Completeness of this “Modification Method” implies completeness of Paramodulation without the functionally reflexive axioms, thus proving a conjecture of Wos and Robinson (1969). Moreover, completeness holds with some other restrictions, such as limiting paramodulation into variables. Experimental results using the Modification Method are included.