Digit-recurrence algorithms are widely used in actual microprocessors to compute floating-point division and square root. These iterative algorithms present a good trade-off in terms of performance, area and power. Traditionally, commercial processors have iterative division and square root units where the iteration logic is used over several cycles. The main drawbacks of these iterative units are long latency and low throughput due to the reuse of part of the logic over several cycles, and its hardware complexity with separated logic for division and square root. We present a radix-64 floating-point division and square root algorithm with a common iteration for division and square root and where, to have an affordable implementation, each radix-64 iteration is made of two simpler radix-8 iterations. The radix-64 algorithm allows to get low-latency operations, and the common division and square root radix-64 iteration results in some area reduction. The algorithm is mapped into two different microarchitectures: a low-latency and low area iterative unit, and a low-latency and high-throughput pipelined unit. In both units speculation between consecutive radix-8 iterations is used to reduce the timing.

Digit-recurrence algorithms are widely used in actual microprocessors to compute floating-point division and square root. These iterative algorithms present a good trade-off in terms of performance, area and power. Commercial processors have non-pipelined division and square root units where part of the logic is used over several cycles. The main drawbacks of these non-pipelined units are the long latency of the traditional division and square root implementations, the low bandwidth (or throughput) due to the reuse of part of the logic over several cycles, and its hardware complexity with separated logic for division and square root. We present a radix-64 floating-point division and square root algorithm with a common iteration for division and square root and where each radix-64 iteration is made of two simpler radix-8 iterations. The radix-64 algorithm allows to get low-latency operations, and the common division and square root radix-64 iteration results in some area reduction. The algorithm is mapped into a low-latency and high-bandwidth pipelined unit.

We present a hybrid methodology for the formal verification of arithmetic RTL designs that combines sequential logic equivalence checking with interactive theorem proving in a two-step process. First, an intermediate model of the design is extracted by hand and coded in Restricted Algorithmic C, a simple C subset augmented by the C++ register class templates of Algorithmic C, which provide the bit manipulation features of Verilog. The model is designed to mirror the RTL microarchitecture closely enough to allow efficient equivalence checking, but sufficiently abstract to be amenable to formal analysis. The model is then automatically translated to the logic of the ACL2 theorem prover, which is used to establish correctness with respect to an architectural specification. As an illustration, we describe the modeling and proof of correctness of a chained multiply-add module, designed to test techniques for area and power reduction and intended for implementation in future Arm graphics nrocessors.

Digit-recurrence algorithms are widely used in actual microprocessors to compute floating-point division and square root. These iterative algorithms present a good trade-off in terms of performance, area and power. We present a floating-point division and square root unit, which implements a radix-64 floating-point division and a radix-16 floating-point square root. To have an affordable implementation, each radix-64 division iteration and radix-16 square root iteration are made of simpler radix-4 iterations: 3 radix-4 iterations in division and 2 in square root. Speculation is used between consecutive radix-4 iterations to get a reduced timing. There are three different parts in digit-recurrence implementations: initialization, digit iterations, and rounding. The digit iteration is the iterative part and it uses the same logic for several cycles. Division and square root share partially the initialization and rounding stages, whereas each one has different logicforthe digit iterations. The result is a low-latency floating-point divider and square root, requiring 11, 6, and 4 cycles for double, single and half-precision division with normalized operands and result, and 15, 8 and 5 cycles for square root. One ortwo additional cycles are needed in case of subnormal operand(s) or result.

The papers in this special section examine the concept of computer arithmetic. Many services offered in the palm of our hand by today’s computing devices were undreamt of twenty years ago, and we probably don’t envision what services will be enabled twenty years from now. We even can’t be sure of the technology they will use, if good old silicon integration is no longer able to sustain Moore’s law. However, one can be confident that there will be computers, and that these computers will compute, and that at the core of these computations there will be adders, multipliers, elementary functions and other core arithmetic primitives. Computer arithmetic is the art of designing and using these core arithmetic primitives. It studies the representation of numbers in computers, and the transformation of these “machine numbers”. With the abacus and early mechanical calculators, it actually predates the computing era. Computer arithmetic has accompanied the evolutions of technology (from relays to vacuum tube to transistors and integrated circuits). It has also adapted to the evolution of applications: scientific computing, digital signal processing, cryptography, or machine learning use different kinds of numbers and operations. Formal proofs involving computer arithmetic components have become a major concern of many other applications.

The following topics are dealt with: floating point arithmetic; digital arithmetic; IEEE standards; field programmable gate arrays; learning (artificial intelligence); cryptography; parallel processing; table lookup; multiplying circuits; mathematics computing.

Hardware signatures based on Bloom filters are used to support and accelerate membership query in a set of items. They use modest hardware at the cost of false positives, but never produce false negatives. Signatures were traditionally used in different distributed and network applications, but in recent years their use has been extended to other fields (for instance, support for manycore/multicore parallel programming, such as data race detection, deterministic replay or transactional memory (TM)). One drawback of signatures is that they have a fixed size, and what is a good signature size for one application, may be not appropriate for another. Recently, we proposed a shared hardware module for managing signatures based on a collection of Bloom filters. It has the characteristic of hosting a variable number of signatures that change their size in runtime to adapt to the demand of the applications. However, the assignment of resources follows a single symmetric policy for all allocations leading to a module with a limited adaptability to the workloads. In this paper, we explore new techniques to allocate signatures in an asymmetric way in this module, with the aim of optimizing the resources and reducing even more the number of false positives. We explore several asymmetric strategies and their efficient hardware implementation, and we show specific examples using TM as a driver application. The results show that these strategies lead to a significant reduction in the number of false positives compared with symmetric policies.

Hybrid terrain models combine large regular data sets and high-resolution irregular meshes [triangulated irregular network (TIN)] for topographically and morphologically complex terrain features such as man-made microstructures or cliffs. In this paper, a new method to generate and visualize this kind of 3D hybrid terrain models is presented. This method can integrate geographic data sets from multiple sources without a remeshing process to combine the heterogeneous data of the different models. At the same time, the original data sets are preserved without modification, and, thus, TIN meshes can be easily edited and replaced, among other features. Specifically, our approach is based on the utilization of the external edges of convexified TINs as the fundamental primitive to tessellate the space between both types of meshes. Our proposal is eminently parallel, requires only a minimal preprocessing phase, and minimizes the storage requirements when compared with the previous proposals.

Newton-Raphson and Goldschmidt algorithms can be sped up by using variable latency hardware architectures for rounding division, square root and their reciprocals. A new approach based on a rounding method with remainder estimate calculated concurrently with the algorithm was proposed in [5]. This paper presents an study of the hardware implementation of this approach and shows that does not suppose additional latency and avoids conventional remainder calculation most of the times. By using a CMOS 90 nm technology library different hardware architectures are presented. The results show that the expected performance improvements are obtained with reasonable increments in area (up to 5.6%), critical path (up to 6.7%) and better power performance (up to -24%).

Multiplicative Newton–Raphson and Goldschmidt algorithms are widely used in current processors to implement division, reciprocal, square root and square root reciprocal operations. Based on an initial approximation of a given accuracy, several iterations are performed until the required result accuracy is achieved. The number of iterations depends on the initial approximation and on the required accuracy. Each iteration consists of several multiplications. In this paper, we present an accurate error analysis that takes into account all the contributions to the final error and allows us to obtain error bounds for each iteration. These error bounds can be used to obtain optimal unit designs by reducing the size of the multiplier and, therefore, to reduce the area requirements. To show the usefulness of the error analysis, we compare the optimal multiplier size obtained from our error analysis with the multipliers in the floating-point division and square root units of some popular processors and we conclude that the multiplier size and its area can be reduced by, roughly, 10%.

We present the algorithm and architecture of a BCD parallel multiplier that exploits some properties of two different redundant BCD codes to speedup its computation: the redundant BCD excess-3 code (XS-3), and the overloaded BCD representation (ODDS). In addition, new techniques are developed to reduce significantly the latency and area of previous representative high-performance implementations. Partial products are generated in parallel using a signed-digit radix-10 recoding of the BCD multiplier with the digit set [-5, 5], and a set of positive multiplicand multiples (0X, 1X, 2X, 3X, 4X, 5X) coded in XS-3. This encoding has several advantages. First, it is a self-complementing code, so that a negative multiplicand multiple can be obtained by just inverting the bits of the corresponding positive one. Also, the available redundancy allows a fast and simple generation of multiplicand multiples in a carry-free way. Finally, the partial products can be recoded to the ODDS representation by just adding a constant factor into the partial product reduction tree. Since the ODDS uses a similar 4-bit binary encoding as non-redundant BCD, conventional binary VLSI circuit techniques, such as binary carry-save adders and compressor trees, can be adapted efficiently to perform decimal operations. To show the advantages of our architecture, we have synthesized a RTL model for$16\times 16$-digit and$34\times 34$-digit multiplications and performed a comparative survey of the previous most representative designs. We show that the proposed decimal multiplier has an area improvement roughly in the range 20-35 percent for similar target delays with respect to the fastest implementation.

An algorithm and architecture for powering computation and root extraction, with fixed-point and floating-point exponents, is presented in this paper. The algorithm is based on an optimized iterative sequence of parallel and/or overlapped operations: 1) reciprocal, 2) high-radix digit-recurrence logarithm, 3) left-to-right carry-free multiplication, and 4) high-radix online exponential. A redundant number system is used to allow for the overlapping of the different operations of the algorithm. As the logarithm and exponential are part of the sequence of operations, some minor changes are made to allow for the independent computation of the logarithm and exponential functions. A sequential implementation of the algorithm is proposed and the execution times and hardware requirements are estimated for single and double-precision floating-point computations. These estimates are obtained for several radices, according to an approximate model for the delay and area of the main logic blocks, and help to determine the radix values, which lead to the most efficient implementations.

Hybrid terrains are a convenient approach for the representation of digital terrain models, integrating heterogeneous data from different sources. In this article, we present a general, efficient scheme for achieving interactive level-of-detail rendering of hybrid terrain models, without the need for a costly preprocessing or resampling of the original data. The presented method works with hybrid digital terrains combining regular grid data and local high-resolution triangulated irregular networks. Since grid and triangulated irregular network data may belong to different datasets, a straightforward combination of both geometries would lead to meshes with holes and overlapping triangles. Our method generates a single multiresolution model integrating the different parts in a coherent way, by performing an adaptive tessellation of the region between their boundaries. Hence, our solution is one of the few existing approaches for integrating different multiresolution algorithms within the same terrain model, achieving a simple interactive rendering of complex hybrid terrains.

With the advent of chip multiprocessors, new techniques have been developed to make parallel programing easier and more reliable. New parallel programing paradigms and new methods of making the execution of programs more efficient and more reliable have been developed. Usually, these improvements require hardware support to avoid a system slowdown. Signatures based on Bloom filters are widely used as hardware support for parallel programing in chip multiprocessors. Signatures are used in Transactional Memory, thread-level speculation, parallel debugging, deterministic replay and other tools and applications. The main limitation of hardware signatures is the lack of flexibility: if signatures are designed with a given configuration, tailored to the requirements of a specific tool or application, it is likely that they do not fit well for other different requirements. In this paper a new hardware signature organization, called Flexible Signatures ( FlexSig ), is proposed. FlexSig can change dynamically the resources assigned to a given signature and the number of signatures in the system, by redistributing the available hardware resources according to the system requirements. This allows higher flexibility than with traditional fixed-resources signatures based on Bloom filters, while maintaining a low false positive rate. FlexSig has been evaluated by comparing it with signatures based on parallel Bloom filters, and we conclude that FlexSig outperforms (in terms of false positive rate) conventional parallel Bloom filters in most cases, due to its ability to use all the signature resources available.

An algorithm for the q-th root extraction, q being any integer, is presented in this paper. The algorithm is based on an optimized implementation of X^{1/q} by a sequence of parallel and/or overlapped operations: (1) reciprocal, (2) digit-recurrence logarithm, (3) left-to-right carry-free multiplication and (4) on-line exponential. A detailed error analysis and two architectures are proposed, for low precision q and for higher precision q. The execution time and hardware requirements are estimated for single precision floating-point computations for several radices, this helps to determine which radices result in the most efficient implementations. The architectures proposed improve the features of other architectures for q-th root extraction.

The special section in this issue focuses on the topic of computer arithmetic.

A new variable latency Goldschmidt algorithm is presented. The algorithm is based on a new rounding method for division, square root, and their reciprocals that avoids the conventional remainder calculation in most of cases and improves previous proposals. The rounding decision is taken by checking the least significant bits of the output of the last Goldschmidt iteration without any other transformation. This helps to reduce the number of cases which need the calculation of the remainder. Additionally, we avoid the calculation of the remainder for most of those cases by using a remainder estimate that can be easily obtained from the Goldschmidt iteration. The calculation of the estimate is much simpler and less time consuming than the calculation of the remainder and this contributes to reducing the number of cases which need a large latency. The combination of both techniques allows us to define a variable latency algorithm which needs to compute the remainder in just nine percent of the total number of cases for reciprocal and division and in 12 percent for square root and square root reciprocal.

This paper presents a rounding method for functional iteration algorithms. The new method is made up of a new rounding algorithm and the calculation of a remainder estimation. The rounding method uses the result directly obtained from the algorithm without any transformation. The remainder estimation is calculated in parallel with the algorithm execution. This allow us to avoid the conventional remainder calculation after obtaining result, most of the times. In this way, the final implementation has a variable latency. By using adequate configurations the remainder calculation is only necessary in 9% of the total cases.

Multicore and many core processors are the new wave of computing, offering high performance by using large numbers of simple processors. In this paper, we describe the implementation of 2 applications into an Ambric massively parallel processor array from a hardware design point of view. An evaluation of performance and design effort is provided, showing that massive parallel processor arrays may challenges FPGAs in some applications.

Arithmetic coding is an efficient entropy compression method that achieves results close to the entropy limit and it is used in modern standards such as JPEG-2000 and H.264. Arithmetic decoding (AD) in H.264 video coding standard is a sequential task that takes a significant part of computing time. In present and future multicore and manycore systems, AD becomes a bottleneck as it cannot be parallelized, limiting the concurrent execution of other tasks. In this paper, an FPGA-based accelerator is proposed to speed-up AD in H.264 and enable parallel decoding at macroblock and frame levels scaling up to tens or hundreds of cores.

The aim of this work is to present a method for rounding quadratically converging algorithms that improves their performance. This method is able to reduce significantly the number of cases where the remainder calculation is necessary. It is based on previous methods and incorporates additional bits of the result approximation to be checked. This work includes the result of exhaustive simulations that permit us to measure exactly how many calculations are avoided. Using these simulations, it is concluded that the presented method is able to reduce by half the number of remainder calculations. Using adequate result approximations the remainder calculation is necessary in only 5% of the total cases.

A radix-2 digit-recurrence algorithm and architecture for the computation of the cube root are presented in this paper. The original recurrence based on the concept of completing the cube is modified to allow an efficient implementation of the algorithm, and the cycle time and area cost of the resulting architecture are estimated as 7.5 times the delay of a full adder and around 9000 $nand2$ cells, respectively, for double-precision computations.

Entropy encoding and decoding is a crucial part of any multimedia system that can be highly demanding in terms of computing power. Hardware implementation of typical compression and decompression algorithms is cumbersome, while conventional software implementations are slow due to bit-level operations, data dependencies and conditional branching. Several solutions have been proposed along the years, ranging from hardware accelerators for high-end systems to careful implementations in VLIW processors and instruction-set extensions, both hardwired and reconfigurable. Multimedia systems must often implement several encoders and decoders for different formats. Hence, a programmable solution is mandatory. However, programmable processors may be challenged by highly-complex algorithms. In this work, a highly efficient and low cost alternative is presented based on an array processor. The dataflow of several entropy coding algorithms has been studied, leading to the choice of an efficient programming model, processor layout and interconnection system. Results are presented for JPEG and H.264 image and video coding standards.

A general digit-recurrence algorithm for the computation of the mth root (with an m integer) is presented in this paper. Based on the concept of completing the mth root, a detailed analysis of the convergence conditions is performed and iteration- independent digit-selection rules are obtained for any radix and redundant digit set. A radix-2 version for mth rooting is also studied, together with closed formulas for both the digit selection rules and the number of bits required to perform correct selections.

AVC/H.264 is the new international standard for video coding jointly developed by ISO-MPEG and ITU-T, which offers a substantial compression gain when compared with H.263 and MPEG-4 simple profile. One of the main characteristics of H.264 is the introduction of a integer version of the discrete cosine transform initially applied to 4times4 pixels blocks, and later extended to 8times8 pixels for high quality video encoding. In this work, a unified architecture is proposed for parallel 8times8 integer DCT and iDCT, also able to process 4times4 DCT, iDCT and Hadamard transform. A very fast quantization/de-quantization scheme is presented based on prediction that allows parallel quantization with a single multiplier. This architecture also implements all-zero detection, eliminating coefficients with high cost as specified in the standard and anticipates entropy encoding. The proposed design has been synthesized in AMS 0.35mu technology and achieves a maximum speed of 67 MHz

We propose a modified Goldschimdt reciprocation algorithm for single precision computation, without using a look-up table. It is a variable latency algorithm i.e. the number of iterations depends on the input operands that provide a linear convergence. Multiplying with the dividend results division, our method requires a cycle for each iteration, performing multiply add and Booth recoding in a cycle. Initial approximation is a two’s complement of the divisor, which can be performed during partial product summation. The implementation is described in IBM G5 FPU(Floating Point Unit) and MIPS R10000 processor multiplier, evaluated and compared with conventional processors. It offers a good trade-off between performance and area, making it suitable for mobile computing applications such as PDA(Personal Digital Assistant), UPC(Ultra Personal Computer), mobile phone, tablet PC(Personal Computer) etc.

In this paper a new technique is presented that combines memory compression in video encoders with fast and efficient motion estimation (ME). This technique is mainly oriented to embedded systems, which demand simple and power aware algorithms. Video encoding needs increasing amounts of memory for storing reference pictures. Memory compression allows reducing the footprint of the application, lowering the total implementation cost. In this paper, we combine memory compression and hierarchical ME so that the overhead associated to implement both techniques is shared. Thus, a net gain in processing speed is obtained, while reducing costs and power consumption

New image and video coding standards have pushed the limits of compression by introducing new techniques with high computational demands. The Advanced Video Coder (ITU-T H.264, AVC MPEG-4 Part 10) is the last international standard, which introduces new enhanced features that require new levels of performance. Among the new tools present in AVC, the context-based binary arithmetic coder (CABAC) offers significant compression advantage over baseline entropy coders. CABAC is meant to be used in AVC's Main and High Profiles, which target broadcast and video storage and distribution of standard and high-definition contents. In these applications, hardware acceleration is needed as the computational load of CABAC is high, challenging programmable processors. Moreover, rate-distortion optimization (RDO) increases CABAC's load by two orders of magnitude. In this paper, we present a fast and new architecture for arithmetic coding adapted to the characteristics of CABAC, including optimized use of memory and context managing and fast processing able to encode more than two symbols per cycle. A maximum processing speed of 185 MHz has been obtained for 0.35 mu, able to encode high quality video in real time. Some of the proposed optimization may also be applied to software implementations obtaining significant improvements

In this paper we propose an architecture for the computation of the double-precision floating-point multiply-add fused (MAF) operation A+(B/spl times/C) that permits to compute the floating-point addition with lower latency than floating-point multiplication and MAF. While previous MAF architectures compute the three operations with the same latency, the proposed architecture permits to skip the first pipeline stages, those related with the multiplication B/spl times/C, in case of an addition. For instance, for a MAF unit pipelined into three or five stages, the latency of the floating-point addition is reduced to two or three cycles, respectively. To achieve the latency reduction for floating-point addition, the alignment shifter, which in previous organizations is in parallel with the multiplication, is moved so that the multiplication can be bypassed. To avoid that this modification increases the critical path, a double-datapath organization is used, in which the alignment and normalization are in separate paths. Moreover, we use the techniques developed previously of combining the addition and the rounding and of performing the normalization before the addition.

In this work, a new architecture for binary arithmetic coding is presented in the context of the new AVC/H.264 standard for video coding. Among the new technologies included in AVC/H.264 a context adaptive binary arithmetic coder (CABAC) is used that outperforms the baseline entropy coder in a significant manner. In this work we justify the need for a new architecture that implements the unique characteristics of CABAC that are not found in other implementations of arithmetic coding. We show that a fast architecture is needed that combines short cycle time and application-aware scheduling in order to accomplish with the high computational demands. A number of optimizations are introduced that allow processing several symbols per cycle and reduce data binarization overhead. Implementation results are shown for a Virtex-II FPGA and the main conclusions are presented.

A table-based method for high-speed function approximation in single-precision floating-point format is presented in this paper. Our focus is the approximation of reciprocal, square root, square root reciprocal, exponentials, logarithms, trigonometric functions, powering (with a fixed exponent p), or special functions. The algorithm presented here combines table look-up, an enhanced minimax quadratic approximation, and an efficient evaluation of the second-degree polynomial (using a specialized squaring unit, redundant arithmetic, and multioperand addition). The execution times and area costs of an architecture implementing our method are estimated, showing the achievement of the fast execution times of linear approximation methods and the reduced area requirements of other second-degree interpolation algorithms. Moreover, the use of an enhanced minimax approximation which, through an iterative process, takes into account the effect of rounding the polynomial coefficients to a finite size allows for a further reduction in the size of the look-up tables to be used, making our method very suitable for the implementation of an elementary function generator in state-of-the-art DSPs or graphics processing units (GPUs).

In this paper we propose an efficient implementation of CABAC's binary arithmetic coder and context management system. CABAC is the context adaptive binary arithmetic coder used in new H.264/AVC video standard. Arithmetic coding allows a significant enhancement in compression. However, implementation complexity is a drawback due to hardware cost and slowness. In this paper we show the need for a hardware implementation of arithmetic coding in current video compression systems. We propose a fast and efficient implementation of the encoding algorithm. We prove that memory accesses constitute a bottleneck and propose solutions that apply to the encoding algorithm and context management system. As a result, a fast architecture is presented, able to process one symbol per cycle.

We propose architecture for the computation of the double-precision floating-point multiply-add-fused (MAP) operation A + (B /spl times/ C). This architecture is based on the combined addition and rounding (using a dual adder) and in the anticipation of the normalization step before the addition. Because the normalization is performed before the addition, it is not possible to overlap the leading-zero-anticipator with the adder. Consequently, to avoid the increase in delay, we modify the design of the LZA so that the leading bits of its output are produced first and can be used to begin the normalization. Moreover, parts of the addition are also anticipated. We have estimated the delay of the resulting architecture considering the load introduced by long connections, and we estimate a delay reduction of between 15 percent and 20 percent, with respect to previous implementations.

An architecture for the computation of logarithm, exponential, and powering operations is presented in this paper, based on a high-radix composite algorithm for the computation of the powering function (X/sup Y/). The algorithm consists of a sequence of overlapped operations: 1) digit-recurrence logarithm, 2) left-to-right carry-free (LRCF) multiplication, and 3) online exponential. A redundant number system is used and the selection in 1) and 3) is done by rounding except from the first iteration, when selection by table look-up is necessary to guarantee the convergence of the recurrences. A sequential implementation of the algorithm, with a control unit which allows the independent computation of logarithm and exponential, is proposed and the execution times and hardware requirements are estimated for single and double-precision floating-point computations. These estimates are obtained for radices from r=8 to r=1,024, according to an approximate model for the delay and area of the main logic blocks and help determining the radix values which lead to the most efficient implementations: r=32 and r=128.

A high-radix composite algorithm for the computation of the powering function (X/sup Y/) is presented. The algorithm consists of a sequence of overlapped operations: (i) digit-recurrence logarithm, (ii) left-to-right carry-free (LRCF) multiplications, and (iii) online exponential. A redundant number system is used, and the selection in (i) and (iii) is done by rounding except from the first iteration, when selection by table look-up is necessary to guarantee the convergence of the recurrences. A sequential implementation of the algorithm is proposed, and the execution times and hardware requirements are estimated for single and double-precision floating-point computations, for radix r=128, showing that powering can be computed with similar performance as high-radix CORDIC algorithms.

Land consolidation is a strategic instrument for rural planning and thus economic development in the Spanish region of Galicia. This paper describes an experimental system embedded in a GIS environment to aid rural engineers to develop land consolidation plans. The system supports all the stages of the plan and many functionalities are implemented as heuristic processes based on expert knowledge and advice. The overall aim is to overcome administrative and technical problems of traditional consolidation procedures. The system provides an integrated framework for the management of spatial and administrative consolidation information. It also includes optimization-based algorithms for the automated generation of multiple alternative parcel reallocations, as well as an environment to refine and objectively evaluate the proposed solutions. These key capabilities result in a powerful tool for decision making that dramatically reduces the time and cost of land consolidation plans. Pilot experiences in two consolidation zones of Galicia assess the feasibility and effectiveness of the system.

A high-radix digit-recurrence algorithm or the computation of the logarithm is presented in this paper. Selection by rounding is used in iterations j/spl ges/2, and selection by table in the first iteration is combined with a restricted digit-set for the second one, in order to guarantee the convergence of the algorithm. A sequential architecture is proposed. and the execution time and hardware requirements of this architecture are estimated, for a target precision of n=32 bits and a radix r=256. These estimates are obtained according to a rough model for the delay and area cost of the main logic blocks employed, and show the achievement of a speed-up by over 4 times with regard to a conventional radix-2 implementation with redundant arithmetic.

An analysis of the impact of different methods for the double-precision computation of division and square root in the performance of a superscalar processor is presented in this paper. This analysis is carried out combining the SimpleScalar toolset, estimates of the latency and throughput of the compared methods and a set of benchmarks with typical features of intensive computing applications. Simulation results show the importance of having an efficient unit for the computation of these operations, since changes in the density of division and square root below 1% lead to changes in the performance around a 20%.

We propose an architecture for the computation of the floating-point multiply-add-fused (MAF) operation A+ (B /spl times/ C). This architecture is based on the combined addition and rounding (using a dual adder) and on the anticipation of the normalization step before the addition. Because the normalization is performed before the addition, it is not possible to overlap the leading-zero-anticipator with the adder. Consequently, to avoid the increase in delay we modify the design of the LZA so that the leading bits of its output are produced first and can be used to begin the normalization. Moreover, parts of the addition are also anticipated. We have estimated the delay of the resulting architecture for double-precision format, considering the load introduced by long connections, and estimate a reduction of about 15% to 20% with respect to traditional implementations of the floating-point MAF unit.

An analysis of the tradeoffs between area and speed for a sequential implementation of a high-radix recurrence for logarithm computation is presented in this paper The high-radix algorithm is outlined and a sequential architecture is proposed, with the use of selection by rounding of the digits and redundant representation. Estimates of the execution time and total area are obtained for n = 16, 32 and 64 bits of precision and for radix values from r = 8 to r = 1024. An analysis of the tradeoffs between area and speed is presented, showing that the most efficient implementations are obtained for radices r = 256 for 16, 32 bit and r = 128 for 64 bit computations.

A new method for the high-speed computation of double-precision floating-point reciprocal, division, square root, and inverse square root operations is presented in this paper. This method employs a second-degree minimax polynomial approximation to obtain an accurate initial estimate of the reciprocal and the inverse square root values, and then performs a modified Goldschmidt iteration. The high accuracy of the initial approximation allows us to obtain double-precision results by computing a single Goldschmidt iteration, significantly reducing the latency of the algorithm. Two unfolded architectures are proposed: the first one computing only reciprocal and division operations, and the second one also including the computation of square root and inverse square root. The execution times and area costs for both architectures are estimated, and a comparison with other multiplicative-based methods is presented. The results of this comparison show the achievement of a lower latency than these methods, with similar hardware requirements.

The double-datapath organization of a floating-point adder results in reduced latency. One of the main characteristics of this organization is the combination of addition/subtraction with rounding into a single add/round module, which is implemented as one pipeline stage and might be responsible for the cycle time. We propose the utilization of the most-significant carry detector and the corresponding adder using the reverse-carry approach to reduce the latency of this add/round module. In addition, the particular organization of the reverse-carry adder is used to reduce the contribution on the delay of the row of half adders that is included in the FAR datapath to produce the sum plus two. Estimates for a 64 bit add/round module show a potential reduction of delay of about 15%.

A method for the calculation of faithfully rounded single-precision floating-point powering (X/sup p/) is proposed in this paper. This method employs table look-up and a second-degree minimax approximation, which allows the employment of reduced size tables to store the coefficients from the polynomial approximation. A specialized squaring unit and a fused accumulation tree carry out with the computation of the quadratic polynomial. Both unfolded and pipelined architectures are presented, and the results of a pre-layout synthesis performed using CMOS 0.35 /spl mu/m technology are shown, achieving a 50% area reduction from linear approximation methods, and with improved speed over other second-degree approximation based algorithms. The pipelined architecture has a latency of three cycles and a throughput of one result per cycle.

A FPGA implementation of a method for the calculation of faithfully rounded single-precision floating-point powering (X/sup p/) is presented in this paper. A second-degree minimax polynomial approximation is used, together with the employment of table look-up, a specialized squaring unit and a fused accumulation tree. The FPGA implementation of an architecture with a latency of 3 cycles and a throughput of one result per cycle has been performed using a Xilinx XC4036XL device. The implemented unit has an operation frequency over 33 MHz.

A fast calculation of the most-significant carry in an addition is required in several applications. It has been proposed to calculate this carry by detecting the most-significant carry chain and collecting the carry after this chain. The detection can be implemented by a prefix tree of AND gates and the collecting by a multi-input OR. We propose a multilevel implementation, which allows the overlap of successive levels, thereby reducing the overall delay. For 64-bit operands we estimate a delay reduction of about 15% with respect to the traditional carry-lookahead-based method, with a similar hardware complexity.

The multilevel reverse-carry approach has been proposed previously for fast computation of the most-significant carry of an adder. We extend this approach to generate several carries and apply it to the implementation of the complete adder. Specifically, the operands are split into blocks and each block is added to produce the sum and the sum plus one. Concurrently with these additions the multilevel reverse-carry approach is used to generate the input carries of these blocks. Finally, these carries are used to select among the sum and the sum plus one. We have evaluated the resulting architecture for a 64-bit adder, considering the load introduced by long connections, and we estimate a reduction of about 15% in the critical path delay with respect to traditional implementations of prefix-tree based adders.

This paper presents a regular, fast, area-efficient and parallelizable architecture for the computation of the one dimensional discrete wavelet transform (DWT). This architecture is based on the lattice structure for wavelet filters, from which, using regularization and linear space-time mapping techniques, we deduce a general systolic array applicable to any number of decomposition levels. Next we show that each processor of the array can be parallelized in a simple and direct form, an advantage that, in addition to those pertaining to the lattices and the systolic arrays, make this an attractive alternative for the implementation in VLSI and/or in a distributed network.

A very-high radix algorithm and implementation for circular CORDIC is presented. We first present in depth the algorithm for the vectoring mode in which the selection of the digits is performed by rounding of the control variable. To assure convergence with this kind of selection, the operands are prescaled. However, in the CORDIC algorithm, the coordinate x varies during the execution so several scalings might be needed; we show that two scalings are sufficient. Moreover, the compensation of the variable scale factor (including the CORDIC scale factor and the prescaling factors) is done by computing the logarithm of the scale factor and performing the compensation by an exponential. Then, we combine, in a unified unit, the proposed vectoring algorithm and the very-high radix rotation algorithm, which was previously proposed by the authors. We compare with low-radix implementations in terms of latency and hardware complexity. Estimations of the delay for 32-bit precision show a speedup of about two with respect to the radix-4 case with redundant addition. This speedup is obtained at the cost of an increase in the hardware complexity, which is moderate for the pipelined implementation. We also compare at the algorithmic level with other very-high radix proposals, demonstrating the advantages of our algorithms.

A very-high radix algorithm and implementation for circular CORDIC in vectoring mode is presented. As for division, to simplify the selection function, the operands are pre-scaled. However in the CORDIC algorithm the coordinate x varies during the execution so several scalings might be needed; we show that two scalings are sufficient. Moreover, the compensation of the variable scale factor is done by computing the logarithm of the scale factor and performing the compensation by an exponential. Estimations of the delay for 32 bit precision show a speed up of about two with respect to the radix-4 case with redundant addition. This speed up is obtained at the cost of an increase in the hardware complexity, which is moderate for the pipelined implementation.

A fast calculation of the most-significant carry in an addition is required in several applications, such as comparisons of two operands by performing their difference, sign detection, and overflow detection. It has been proposed to calculate this carry by detecting the most-significant carry chain and collecting the carry after this chain. The detection can be implemented by a prefix tree of AND gates and the collecting by a multi-input OR or by a connection with tristate buffers. We have performed an estimate of the delay of this implementation for a datapath width of 64 bits and conclude that it is not significantly faster than the traditional carry-lookahead based method. We propose a multilevel implementation, which allows the overlap of successive levels thereby reducing the overall delay. For 64-bit operands we estimate a delay reduction of about 15% with respect to the traditional carry-lookahead based method, with a similar number of gates and number and length of interconnections.

This paper describes the design of a leading-one prediction (LOP) logic for floating-point addition with an exact determination of the shift amount for normalization of the adder result. Leading-one prediction is a technique to calculate the number of leading zeros of the result in parallel with the addition. However, the prediction might be in error by one bit and previous schemes to correct this error result in a delay increase. The design presented here incorporates a concurrent position correction logic, operating in parallel with the LOP, to detect the presence of that error and produce the correct shift amount. We describe the error detection as part of the overall LOP, perform estimates of its delay and complexity, and compare with previous schemes.

This paper describes the design of a Leading-one Predictor (LOP) for floating-point addition, with an exact determination of the shift amount required. Previous LOP proposals produce a shift amount which might be in error by one position, so that this error has to be corrected after the addition terminates, increasing the critical path. Our design incorporates a concurrent detection of this error so that the amount of shift is corrected before the actual shift, without increasing the latency. The scheme presented here is applicable to the common case of a single datapath floating-point addition in which the output of the adder is always positive. We estimate the reduction in the critical path and the increase in area.

A very-high radix digit-recurrence algorithm for the operation /spl radic/(x/d) is developed, with residual scaling and digit selection by rounding. This is an extension of the division and square-root algorithms presented previously, and for which a combined unit was shown to provide a fast execution of these operations. The architecture of a combined unit to execute division, square-root, and /spl radic/(x/d) is described, with inverse square-root as a special case. A comparison with the corresponding combined division and square-root unit shows a similar cycle time and an increase of one cycle for the extended operation with respect to square-root. To obtain an exactly rounded result for the extended operation a datapath of about 2n bits is needed. An alternative is proposed which requires approximately the same width as for square-root, but produces a result with an error of less than one ulp. The area increase with respect to the division and square root unit should be no greater than 15 percent. Consequently, whenever a very high radix unit for division and square-root seems suitable, it might be profitable to implement the extended unit instead.

This paper presents a new design for two operand normalization. The two operand normalization operation involves the normalization of at least one of two operands by left shifting both by the same amount. Our design performs the computation of the shift by making an OR of the bits of both operands in a tree network, encoding the position of the first nonzero bit. The encoded position is obtained most significant bit first, and then there is an overlapping with the shifting operation. The design we propose replaces two leading zero detector circuits and a comparator, that are present in the conventional approach. Our scheme demonstrates to be more area efficient than the conventional one. The circuit we propose is useful in floating point complex multiplication and COordinate Rotation DIgital Computer (CORDIC) processors.

In this paper we present new VLSI architectures for the arithmetic encoding and decoding of multilevel images. In these algorithms the speed is limited by their recursive natures and the arithmetic and memory access operations. They become specially critical in the case of decoding. In order to reduce the cycle length we propose working with two executions of the algorithm which alternate in the use of the pipelined hardware with a minimum increase in its cost.

The Viterbi algorithm is widely used in communications and signal processing. Recently, several area-efficient architectures for this algorithm have been proposed. Area-efficient architectures trade speed for area by means of mapping the N states of the trellis describing the Viterbi algorithm to P processing elements, where N>P. In this paper a practical VLSI implementation of an area-efficient architecture to evaluate the Viterbi algorithm is presented. The architecture that has been implemented is composed of only two processing elements and the corresponding routing network to process, in different cycles, all the states of the trellis. The resulting architecture has been integrated in a chip using a 0.7 /spl mu/ CMOS technology, occupying an area of 9 mm/sup 2/.

In this paper, we consider the errors appearing in angle computations with the CORDIC algorithm (circular and hyperbolic coordinate systems) using fixed-point arithmetic. We include errors arising not only from the finite number of iterations and the finite width of the data path, but also from the finite number of bits of the input. We show that this last contribution is significant when both operands are small and that the error is acceptable only if an input normalization stage is included, making unsatisfactory other previous proposals to reduce the error. We propose a method based on the prescaling of the input operands and a modified CORDIC recurrence and show that it is a suitable alternative to the input normalization with a smaller hardware cost. This solution can also be used in pipelined architectures with redundant carry-save arithmetic.

Traditionally, CORDIC algorithms have employed radix-2 in the first n/2 microrotations (n is the precision in bits) in order to preserve a constant scale factor. The authors present a full radix-4 CORDIC algorithm in rotation mode and circular coordinates and its corresponding selection function, and propose an efficient technique for the compensation of the nonconstant scale factor. Three radix-4 CORDIC architectures are implemented: 1) a word serial architecture based on the zero skipping technique, 2) a pipelined architecture, and 3) an application specific architecture (the angles are known beforehand). The first two are general purpose implementations where redundant (carry-save) or nonredundant arithmetic can be used, whereas the last one is a simplification of the first two. The proposed architectures present a good trade-off between latency and hardware complexity when compared with existing CORDIC architectures.

The Viterbi (1967) algorithm (VA) is known to be an efficient method for the realization of maximum-likelihood (ML) decoding of convolutional codes. The VA is characterized by a graph, called a trellis, which defines the transitions between states. To define an area efficient architecture for the VA is equivalent to obtaining an efficient mapping of the trellis. We present a methodology that permits the efficient hardware mapping of the VA onto a processor network of arbitrary size. This formal model is employed for the partitioning of the computations among an arbitrary number of processors in such a way that the data are recirculated, optimizing the use of the PEs and the communications. Therefore, the algorithm is mapped onto a column of processing elements and an optimal design solution is obtained for a particular set of area and/or speed constraints. Furthermore, the management of the surviving path memory for its mapping and distribution among the processors was studied. As a result, we obtain a regular and modular design appropriate for its VLSI implementation in which the only necessary communications between processors are the data recirculations between stages.

The main part of the Viterbi algorithm is a nonlinear feedback loop which presents a bottleneck for high-speed implementations. We present a novel scheduling scheme that allows increasing the available speed of the system. This is done through the utilization of look-ahead techniques to compute non-sequential data and, in this way, break the recursivity of the algorithm. This permits introducing pipelining. As a result, we obtain a speed growth comparable to previous parallel solutions, but with less hardware cost.

In this paper we present a new CORDIC algorithm for the vectoring mode, based on the use of radix-4 preserving a complexity in the microrotations that is similar to that of the conventional radix-2 CORDIC. The use of this radix, together with the inclusion in the CORDIC algorithm of the zero skipping technique, reduces by more than half the number of iterations with respect to the conventional radix 2 CORDIC, with the consequent reduction of time in recursive architectures or area in pipelined architectures. In processes such as SVD or matrix triangularization in which the evaluation of the rotation angle is required, this algorithm is shown to be specially efficient.

Trellis coded quantization (TCQ) is an efficient technique for encoding memoryless sources. Furthermore TCQ can be incorporated into a transform coding structure (such as the discrete cosine transform) for encoding monochrome and color images with fixed rate or entropy-constrained schemes. In all these cases an expanded codebook is partitioned into subsets used to label the branches of an appropriate graph (trellis). For a given data sequence, the Viterbi algorithm is then used to find the minimum mean square error path through the trellis. We present a generic architecture scheme that can be easily adapted to the different TCQ image compression methods. We also present a formal model that permits a regular and modular design solution that is optimal for a particular set of area and/or speed constraints.

We present a unified mixed radix CORDIC algorithm with carry-save arithmetic with a constant scale factor. The pipelined architecture of the processor is determined by a unique sequence of microrotations for the two modes of operation (rotation and vectoring) in circular and hyperbolic coordinates. The combination of radix-2 and radix-4 microrotations allows us to reduce the latency and size of the pipeline significantly. The unified algorithm is based on the correcting microrotation method, which we have extended to the vectoring mode in hyperbolic coordinates. We have also generalized the use of radix-4 microrotations to the two operation modes and coordinate systems.

We present a Cordic rotator, using carry-save arithmetic, based on the prediction of all the coefficients into which the rotation angle is decomposed. The prediction algorithm is based on the use of radix-2 microrotations with multiple shifts in the first iterations and the use of a redundant radix-2 and radix-4 representation for the coefficients in the rest of the microrotations. The use of multiple shifts facilitates the prediction of the coefficients in the case of microrotations where i/spl les/n/4, being n the precision of the algorithm, and the use of radix-4 microrotations helps to reduce the total number of iterations. The prediction is carried out using the redundant representation of the z coordinate, without any need for conversions to a non-redundant representation. Finally, we present a VLSI architecture based on this algorithm. As the production of the coefficients is very fast, and they are known before starting each microrotation, the resulting architecture can be highly pipelined and consequently appropriate for applications where high speeds are required.>

Many applications figure the evaluation of rotations at high speeds. However there is a trade-off between the chip area and the latency. In this paper we develop a digit on-line pipelined array architecture based on the radix-4 CORDIC algorithm in rotation mode. The radix-4 CORDIC algorithm halves the number of microrotations with respect the traditionally radix-2 algorithm with the drawback of a non-constant scale factor. Seeking a good compromise between silicon area and latency we have used digit on-line processing. This way the data inputs the processor in blocks of bits (digits) in MSD-first mode of processing. We have used redundant carry-save arithmetic to allow carry-free additions and on-line processing. The designed processor demonstrates to have a better performance than previous digit on-line architectures.

The compensation of scale factor imposes significant computation overhead on the CORDIC algorithm. In this paper we will propose two algorithms and architectures in order to perform the compensation of the scale factor in parallel with the computation of the CORDIC iterations. This way it is not necessary to carry out the final multiplication or add scaling iterations in order to achieve the compensation. With the architectures we propose the dependence on n of the compensation of the scale factor disappears, and this considerably reduces the latency of the system. The architectures developed are optimized solutions for the different operating modes of the CORDIC both in conventional and in redundant arithmetic.

Presents a VLSI architecture for the evaluation of the (8/spl times/8)-point 2-D DCT with on-line arithmetic. The utilization of on-line arithmetic, in combination with an algorithm based on FCT and matrix multiplication, reduces the total hardware maintaining a data rate and a latency similar to approaches based on distributed or parallel arithmetic. The architecture has been integrated in a chip using a 1 /spl mu/ CMOS technology, occupying an area of 56.7 mm/sup 2/.

We present an unified parallel architecture for four of the most important fast orthogonal transforms with trigonometric kernel: Complex Valued Fourier (CFFT), Real Valued Fourier (RFFT), Hartley (FHT), and Cosine (FCT). Out of these, only the CFFT has a data flow coinciding with the one generated by the successive doubling method, which can be transformed on a constant geometry flow using perfect unshuffle or shuffle permutations. The other three require some type of hardware modification to guarantee the constant geometry of the successive doubling method. We have defined a generalized processing section (PS), based on a circular CORDIC rotator, for the four transforms. This PS section permits the evaluation of the CFFT and FCT transforms in n data recirculations and the RFFT and FHT transforms in n-1 data recirculations, with n being the number of stages of a transform of length N=r/sup n/. Also, the efficiency of the partitioned parallel architecture is optimum because there is no cycle loss in the systolic computation of all the butterflies for each of the four transforms.>

A semisystolic architecture is presented for the parallel calculation of the decimation in time and radix-2 fast Hartley transform (FHT) of a real sequence with N=2/sup n/ data items. The architecture is based on a constant geometry algorithm for computing the FHT which facilitates its mapping in VLSI technology and minimizes the communications among processors. The circuit proposed is characterized by its modular design and its interconnective regularity. It permits the computation of arbitrarily sized FHTs as a consequence of the partition of the data and the recirculation of partial results over the processing units in the successive stages of the transform. Each calculation stage requires N/4Q cycles where Q is the number of processors (Q=2/sup q/). The total calculation time is (Nlog/sub 2/N)/4Q cycles.>

This paper describes ACLE (Array C Language Emulator), a software package comprising an ACLAN-to-C translator and a library of simulation routines enabling the execution of programs written in ACLAN to be simulated on a conventional sequential computer. Array C LANguage (ACLAN) is a machine-independent programming language that extends C by endowing it with structures for programming array processors. ACLAN was successfully proven by developing many parallel algorithms for hypercube computers. An algorithmic solution for mapping algorithms onto these computers is explained.