We construct a natural number n > 1 by trichotomy n = g + xpd; xp= 22p, 0 les gp, 0p, applied recursively, and by systematically sharing nodes with equal integer value. The resulting integer decision diagram IDD is a directed acyclic graph DAG which represents n by s(n) nodes in computer memory. IDDs compete with bit arrays, which represent the consecutive bits of n within roughly 1(n) contiguous bits in memory. Unlike the binary length 1(n), the size s(n) is not monotonic. Most integers are dense: their size is near worst & average. The IDD size of sparse integers is arbitrarily smaller. Over dense numbers, the worst/average time/space complexity of IDDs arithmetic operations is proportional to that of bit arrays. Yet, equality testing is performed in unit time with IDDs and the time/space complexity of some operations (e.g. sign(n - m), n plusmn 2m, 22n) are (at least) exponentially better with IDDs than with bit arrays, even over dense operands. Over sparse operands, the time and space complexity of all ALU operations {cap , cup, oplus, +, -} are (in general) arbitrarily better with IDDs than bit-arrays. The coding powers of integers lets IDDs implement integer sets and predicates as well as arithmetics. The IDD package is a one shop alternative to 3 (and more) successful yet rather different packages for processing large numbers, dictionaries and Boolean functions. Performance levels are comparable over dense structures, and IDDs prove best in class over sparse structures.

We present an efficient implementation of a state of the art algorithm PixelMatch for matching all pixels within consecutive video frames. The method is of practical interest for tracking movements in video; it is also related to block-matching in standard video compression methods. From the source specification of PixelMatch, a limited number of high-level code transformations are first performed and analyzed, to produce an intermediate executable software code. From the intermediate software code, an efficient reconfigurable hardware circuit is synthesized, in a fully automatic manner, to process Standard Definition video streams in real-time on a current mid-size FPGA. The software implementation compiled from the same code runs orders of magnitude faster than the original specification. Despite this, real-time software processing of video streams by PixelMatch is still only within reach of the highest-end workstations

In this paper we describe a recontigurable architecture optimised for media processing, and based on 4-bit ALUs and interconnect.

Programmable active memories (PAM) are a novel form of universal reconfigurable hardware coprocessor. Based on field-programmable gate array (FPGA) technology, a PAM is a virtual machine, controlled by a standard microprocessor, which can be dynamically and indefinitely reconfigured into a large number of application-specific circuits. PAM's offer a new mixture of hardware performance and software versatility. We review the important architectural features of PAM's, through the example of DECPeRLe-1, an experimental device built in 1992. PAM programming is presented, in contrast to classical gate-array and full custom circuit design. Our emphasis is on large, code-generated synchronous systems descriptions; no compromise is made with regard to the performance of the target circuits. We exhibit a dozen applications where PAM technology proves superior, both in performance and cost, to every other existing technology, including supercomputers, massively parallel machines, and conventional custom hardware. The fields covered include computer arithmetic, cryptography, error correction, image analysis, stereo vision, video compression, sound synthesis, neural networks, high-energy physics, thermodynamics, biology and astronomy. At comparable cost, the computing power virtually available in a PAM exceeds that of conventional processors by a factor 10 to 1000, depending on the specific application, in 1992. A technology shrink increases the performance gap between conventional processors and PAM's. By Noyce's law, we predict by how much the performance gap will widen with time.

The future Large Hadron Collider (LHC) to be built at CERN, by the turn of the millenium, provides an ample source of challenging real-time computational problems. We report here some results from a collaboration between CERN EAST (RD-11) group and DEC-PRL PAM team. We present the implementations of the three foremost LHC algorithms on DECPeRLe-1 [2]. Our machine is the only one which presently meets the requirements from CERN (100 kHz event rate), except for another dedicated FPGA-based board built for just one of the algorithm. All other implementations based on single and multiprocessor general purpose computing systems fall short either of computing power, or of I/O resources or both.

The Hough transform is the choice technique for identifying straight lines through digital images, with applications to high energy physics and computer vision. Classical methods for implementing the Hough transform of a N/spl times/N binary image require to compute N/sup 3/ additions over n=log/sub 2/(N) bits integers, hence nN/sup 3/ bit operations per transform. We introduce a new algorithm for computing the fast Hough transform FHT which only requires log/sub 2/(N)/spl times/N/sup 2/ additions, for a total of n/sup 2/N/sup 2/ bit operations per transform. The method is based on a recursive algorithm for raster-scan line drawing, which is different from Bresenham's iterative one The FHT has a divide and conquer recursive structure similar to that of the classical fast Fourier transform FFT algorithm, with simpler atomic operations-additions over n bits numbers-and a more complex interconnect. The FHT algorithm can readily be implemented in software. It maps into hardware as well, and we detail the structure of a bit-serial circuit for computing the FHT.>

We establish new, yet intimate relationships between the 2-adic integers /sub 2/Z from arithmetics and digital circuits, both finite and infinite, from electronics. 1) Rational numbers with an odd denominator correspond to output only synchronous circuits. 2) Bit-wise 2-adic mappings correspond to combinational circuits. 3) Online functions /spl forall/n/spl isin/N,x/spl isinsub 2/Z:f(x)=f(xmodd2/sup n/)mod2/sup n/), correspond to synchronous circuits. 3) Continuous functions, /sub 2/Z/spl rarrsub 2/Z, correspond to circuits with output enable. The proof is obtained by constructing synchronous decision diagrams SDDs. They generalize to sequential circuits as classical BDD constructs do for combinational circuits. From simple identities over /sub 2/Z, we derive both classical and new bit-serial circuits for computing: {+,-,/spl times/,1/(1-2x), (1+8x)}. The correctness of each circuit directly follows from the 2-adic definition of the corresponding operator. All but the adders (+,-) above are infinite. Yet the use of reset signals reduces all previously infinite operators to finite circuits. The present work lays out the semantic basis of a new language for describing synchronous circuits. Language 2Z incorporates arithmetic synthesis for some of the above bit-serial operators, and for periodic binary constants (logic from chronograms). It also provides for the powerful deeply binding synchronous enable and reset operators, whose meaning is discussed.>

The authors detail and analyze the critical techniques that may be combined in the design of fast hardware for RSA cryptography: chinese remainders, star chains, Hensel's odd division (also known as Montgomery modular reduction), carry-save representation, quotient pipelining, and asynchronous carry completion adders. A fully operational PAM (programmable active memory) implementation of RSA that combines all of the techniques presented here delivers an RSA secret decryption rate over 600-kb/s for 512-b keys, and 165-kb/s for 1-kb keys. This is an order of magnitude faster than any previously reported running implementation. While the implementation makes full use of the PAM's reconfigurability, it is possible to derive from the (multiple PAM designs) implementation a (single) gate-array specification with estimated size under 100 K gates and speed over 1 Mb/s for RSA 512-b keys. Matching gains in software performance which are also analyzed.>

The author introduces a synchronous binary counter which can be operated under a high clock frequency, independent of the counter's length n: all signals traverse at most two three-input logic gates during each clock phase. The proposed design is simple enough to have practical implications, as illustrated by a CMOS programmable gate array implementation which has counted up to 2/sup 40/ with a 40-MHz clock. The area required for laying out this design is no larger than that of the (much slower) carry-ripple counter.>

Article Hardware speedups in long integer multiplication Share on Authors: M. Shand Digital Equipment Corp., Paris Research Laboratory, 85 Av Victor Hugo. 92500 Rueil-Malmaison, France Digital Equipment Corp., Paris Research Laboratory, 85 Av Victor Hugo. 92500 Rueil-Malmaison, FranceView Profile , P. Bertin Institut National de Recherche en Informatique et Automatique, 78150, Rocquencourt, France Institut National de Recherche en Informatique et Automatique, 78150, Rocquencourt, FranceView Profile , J. Vuillemin Digital Equipment Corp., Paris Research Laboratory, 85 Av Victor Hugo. 92500 Rueil-Malmaison, France Digital Equipment Corp., Paris Research Laboratory, 85 Av Victor Hugo. 92500 Rueil-Malmaison, FranceView Profile Authors Info & Claims SPAA '90: Proceedings of the second annual ACM symposium on Parallel algorithms and architecturesMay 1990 Pages 138–145https://doi.org/10.1145/97444.97679Published:01 May 1990 19citation402DownloadsMetricsTotal Citations19Total Downloads402Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

A discussion is presented of parallel division algorithms that can be classified among modified higher radix nonrestoring online division methods, where redundant representations are extensively utilized to speed up the operation. The network realizations of these algorithms are cellular, or even systolic with exclusively local control; they have both size (area) and time of O(n), where n is the length of the dividend representation. The same structures can also be used as a signed, digit-serial multiplier. When suitably equipped with some control and a few registers, the divider/multiplier brings remarkable performance to large modular arithmetic, RSA cryptography, and greatest common divisor computations. They are also of interest for the design of floating-point units and signal processing applications.>

A representation of the computable real numbers by continued fractions is introduced. This representation deals with the subtle points of undecidable comparison and integer division, as well as representing the infinite 1/0 and undefined 0/0 numbers. Two general algorithms for performing arithmetic operations are introduced. The algebraic algorithm, which computes sums and products of continued fractions as a special case, basically operates in a positional manner, producing one term of output for each term of input. The transcendental algorithm uses a general formula of Gauss to compute the continued fractions of exponentials, logarithms, trigonometric functions, and a wide class of special functions. A prototype system has been implemented in LeLisp and the performance of these algorithms is promising.>

A family of VLSI circuits is presented to perform open convolution, i.e., polynomial multiplication. The circuits are all based on a recursive construction and are therefore particularly well adapted to automated design. All the circuits presented are optimal with respect to the area–time2 tradeoff, and, depending on the degree of paralleism or pipeline, they range from a compact but slow convolver to a large but very fast convolver.

We introduce a property of Boolean functions, called transitivity which consists of integer, polynomial, and matrix products as well as of many interesting related computational problems. We show that the area of any circuit computing a transitive function grows quadratically with the circuit's maximum data rate, expressed in bits/S. This result provides a precise analytic expression of an area-time tradeoff for a wide class of VLSI circuits. Furthermore (as shown elsewhere), this tradeoff is achievable. We have thus matching (to within a constant multiplicative factor) upper and lower complexity bounds for the three above products, in the VLSI circuits computational model.

We introduce a property of boolean functions, called transitivity which holds of integer, polynomial, and matrix products as well as of many interesting related computational problems. We show that the area of any circuit computing a transitive function grows quadratically with the circuit's maximum data-rate, expressed in bit/second. This result provides a precise analytic expression of an area-time tradeoff for a wide class of V.L.S.I. circuits. Furthermore, (as shown elsewhere), this tradeoff is achievable. Thus we have matching (to within a constant multiplicative factor) upper and lower complexity bounds for the three above products, in the V.L.S.I. circuits computational model.

It IS shown that two widely different notions of program equivalence coincide for the language of recurslve definitions with simplification rules The first is the now classical equivalence for fixed-point semantics.The other is purely operational in nature and is much closer to a programmer's intuition of program equivalence KEY WORDS AND PHgASES semantics of programming languages, algebraic semantics, subtree replacement systems CR CATEGORIES: 4 2, 5 2, 5 24

This paper presents the average case performance analysis of dynamic data structures subjected to arbitrary sequences of insert, delete and query operations. To such sequences of operations are associated, for each data type, a specific continued fraction and a familly of orthogonal polynomials : Tchebycheff for stacks, Laguerre for dictionaries, Hermite for priority queues, Meixner for linear lists and Charlier for symbol tables. We define a notion of integrated cost of a data structure as the average cost over all possible sequences of operations. Our main result is an explicit expression, for each of these data structures, of the generating function for integrated costs as a linear integral transform of the generating functions for individual operation costs. We use the result to explicitly compute integrated costs of various efficient data structure implementations.

We introduce a network of processing elements, the cube-connected-cycles (CCC), complying with the present technological constraints of VLSI design. By combining the principles of parallelism and pipelining, the CCC can emulate the cube-connected machine with no significant degradation of performance but with a much more compact structure. We describe in detail how to program the CCC for efficiently solving a large class of problems, which includes Fast-Fourier-Transform, sorting, permutations, and derived algorithms. The CCC can also be used as a general purpose parallel processor.

We introduce a notion of integrated cost of a dictionary, as average cost of sequences of search, insert and delete operations. We express generating functions of these sequences in terms of continued fractions; from this we derive an explicit integral expression of integrated costs for three common representations of dictionaries.

We present a new data-structure for representing priority queues, the pagoda. A detailed analysis shows that the pagoda provides a very efficient implementation of priority queues, where our measure of efficiency is the average run time of the various algorithms. It handles an arbitrary sequence of n primitive operations chosen from MIN, INSERT, UNION, EXTRACT and EXTRACTMIN in time o(n log n). The constant factors affecting these asymptotic run time are small enough to make the pagoda competitive with any other priority queue, including structures which cannot handle UNION or EXTRACT. The given algorithms process an arbitrary sequence of n operations MIN, INSERT and EXTRACT in linear average time O(n), and a sequence of n INSERT in linear worst case time O(n).

In this paper, we show that two widely different notions of program equivalence coincide for the language of recursive definitions with simplification rules. The first one is the now classical equivalence for fixed-point semantics. The other one is purely operational in nature and is much closer to a programmer's intuition of program equivalence.

Let An be the average number of registers required for evaluating arithmetic expressions of size n, or, equivalently, the minimal stack needed for exploring binary trees with n nodes. We give explicit expressions for An and related quantities and show that: An = log4(n) + C + E(log4n) + o(1) where C = 1/2 - γ + 2/2 log2 + log2Π 0.292 and E is continuous, periodic with period 1, with average value 0 and amplitude less than .05.

We investigate the maximum number C(P) of arguments of P that must be tested in order to compute P, a Boolean function of d Boolean arguments. We present evidence for the general conjecture that C(P)=d whenever P(0d) @@@@ P(1d) and P is left invariant by a transitive permutation group acting on the arguments. A non-constructive argument (not based on the construction of an “oracle”) proves the generalized conjecture for d a prime power. We use this result to prove the Aanderaa-Rosenberg conjecture by showing that at least v2/9 entries of the adjacency matrix of a v-vertex undirected graph G must be examined in the worst case to determine if G has any given non-trivial monotone graph property.

Numérisation avec OCR réalisée en 2024. La reconnaissance de caractères du PDF (format PDF/A) peut comporter des erreurs. Pour toutes informations complémentaires et les partages de propriété, merci de contacter le service IES [email protected]

In this paper, we present an algorithm which computes the optimal pattern for merging n equal size sorted sequences stored on a disk, in time O(log n) and constant space. The best previously known algorithm for solving this problem (Knuth [4], Schlumberger-Vuillemin [5]) takes time O(n2) and space O(n).

The object of this paper is to study the mechanism of recursion in a simple, LISP-like programming language, where the only mean of iteration is through recursion. The theory of computation developped in Scott [4] provides the framework of our study. We show how the implementations of recursion which deserve to be called “correct” can be characterized semantically, and demonstrate a general criterion for the correctness of an implementation. We then describe an implementation of recursion which is both correct and optimal in a general class of sequential languages, and therefore constitutes an attractive alternative to both “call-by-name” and “call-by-value”.