Analysis of Parallel Prefix Adders

Abstract

Parallel prefix adders are essential components of contemporary digital arithmetic circuits and are found in many different devices, including digital signal processors and microprocessors. In order to improve the effectiveness and performance of parallel prefix adders, this research investigates their design and optimization. This paper analyses in detail the state of the parallel prefix adder architectures and provide new designs that minimize power consumption and critical path delays. The speed and area efficiency benefits of the parallel prefix designs with thorough simulations and comparisons is reviewed. This research have ramifications for high-performance computing systems and point to interesting avenues to further the state of the art in parallel prefix adder design.

Introduction

I. INTRODUCTION

The majority of contemporary digital control systems and DSP circuits depend heavily on the fundamental operation of binary addition. Adders come in different varieties, and each has a distinct function and significance [1]. The choice of adder type is contingent upon the intended application [2]. In order to achieve high accuracy and minimal space consumption, adders must be able to compute more quickly. In a digital system, binary adders are among the most important logic components. These impact the design's performance. Aside from Arithmetic Logic Units (ALU), binary adders are also useful in memory addressing units, multipliers, dividers, and other units [3]. Any enhancement to binary addition can boost the performance of any computing device, which in turn enhances the system as a whole. The carry chain is the main disadvantage of binary addition.[2] [3]. The carry chain's length grows in tandem with the width of the input operands. Accelerating the carry chain, but not completely eliminating it, can help the carry-propagate adders perform better. Because they often set the critical path for most computations, most digital designers end up building faster adders by optimizing computer architecture [1]. The primary goal of this paper is to identify an improved adder with respect to cell usage, device utilization, and delay constraints [1] [2].

II. METHODOLOGY

With the rising processing demands of the present generation, DSP is essential. A variety of procedures are carried out in order to create an effective architecture. One of the key components that aid in creating an effective architecture is the adder [4]. The way an architecture is implemented determines how effective it is. In this work, Verilog coding is used for the implementation and analysis of adders [5]. Targeting the Spartan 6 FPGA family, analysis, synthesis, and pre-simulation compilation were carried out using the Xilinx ISE design tool. Fig. 1 displays the block diagram of the high-speed architecture utilizing serial adders and parallel prefix [6]. This picture illustrates the several processes that must be taken in order to calculate assessment parameters like area and delay [8].

III. PARALLEL PREFIX ADDERS

These adders determine carriers for several bits at once using a variety of methods, such as the prefix calculation. By anticipating whether a carry will be formed or propagated from each bit addition, the carry lookahead logic lessens the need to compute the current carry by relying on the prior one [4]. Different designs of parallel prefix adders exist, including the Brent-Kung adder, the Kogge-Stone adder, and others. Each has a distinct method for computing the carry signals in parallel with the goal of maximizing performance and minimizing latency in multi-bit addition operations [1][7][2].

A. Stages of Parallel Prefix Adders

The purpose of parallel prefix adders is to calculate the prefix sum of a group of binary values. Usually, they are divided into many stages:

1. Generation Stage: In this stage, partial prefix sums are calculated without taking the carry bits into account [4].
2. Stage of Propagation: Manages the carry propagation via the adder. The carry bits that must be conveyed to higher order bits are calculated by it [4].
3. Reduction Stage: To get the final total, the carry bits are effectively reduced or processed in this last stage [4]. Together, these steps allow for the prefix sum to be computed efficiently, which lowers the critical path time when adding several bits in parallel. Prefix adders come in different designs, such as the Kogge-Stone, Brent-Kung, and Han-Carlson adders, and each one implements these phases in a different method for quicker results [5][6].

???????B. Types of Parallel Prefix Adders

1) Kogge Stone Adders

Kogge and Stone created KSA, a parallel prefix form of CLA, in 1973[7]. It is often referred to as the faster adder and is used in industries for higher performance arithmetic circuits because it generates a carry in O (logn) time. In the Kingdom of Saudi Arabia, carry is produced more quickly by calculating it concurrently at the risk of an expanded area [10]. Because of its uniform structure, KSA can be readily integrated with current electronic technologies. KSA's minimum fan-out or minimum logic depth is another advantage. KSA consequently developed into a larger but faster adder[11]. The number of stages for the "o" operator, or log2n, is the delay of KSA. The KSA has an area of (n*log2n)-n+1, where n is the number of "o" operators [12][13]. The features of the kogge-Stone adder are:

• Low depth 
• High node count (suggests greater area).
• Each node has a minimum fan-out of 1, which suggests faster performance [14][15].

Calculating the propagation and carry generation, there are three phases to it:

• Pre-Processing stage:  P = A xor B; G = A and B
• Generation of carry: CP = P(previous) and P; CG= G or (P and G(previous))  
• Final processing stage: S = P xor C; C = CG (previous)[16][17].

It is claimed to be a good substitute for high performance applications and is the fastest adder that concentrates on design time. Low propagation delay is frequently the outcome of the Kogge-Stone adder's parallel structure. For applications like high-performance computing, where quick arithmetic operations are crucial, this feature is indispensable.

2) Brent Kung Adders

A particular kind of parallel prefix adder that is frequently used in digital circuit design for quick binary addition is the Brent-Kung adder [18]. It was first introduced by Tim S. Kung and C. L. Brent in 1982, and it effectively reduces calculation time and critical path latency to overcome the drawbacks of conventional adders. Multiple additions can occur simultaneously because the adder has a tree-like structure in which input bits are separated into groups and carry values are computed in parallel [19]. Because of its ability to provide quicker addition operations, this parallelism is appropriate for highspeed arithmetic applications such as GPUs and CPUs [20]. It is widely utilized in digital circuit design for speedy binary addition. It effectively overcomes the limitations of traditional adders by reducing critical path latency and computation time [21][22].

The extreme boundary case of the following applies to the

Brent-Kung parallel prefix adder:

• Maximum logic depth in PP adders (implies longer calculation time).
• Minimum area implied by minimum number of nodes [23][24].

Three steps make up the computation of carry generation and propagation: 

• Preprocessing stage :P=A xor B; G=A and B
• Generation of carry: CP=P and p(previous); CG= G and P and p(previous)
• Final processing stage: Sum=CP; Carry=CG [25].

The Brent Kung Adder is best for area and power performance [26].

IV. APPLICATIONS

Parallel prefix adders, often referred to as carry-select adders or prefix adders, are vital parts of digital circuit design and are used in a wide range of industries [35]. These adders are especially helpful in situations requiring high-speed arithmetic operations as they are made to efficiently complete binary addition operations. Digital circuit design uses parallel prefix adders, often referred to as carry-lookahead adders, extensively [36].

Both speed and efficiency are major benefits of these specialized adders. They are mostly used in the core of processors, where they improve the efficiency of the arithmetic units of digital signal processors and microprocessors [37]. These processors' high-speed addition operations—which are necessary for a variety of arithmetic and logic operations—are dependent on parallel prefix adders. Furthermore, they are essential to digital signal processing because they enable faster addition and multiplication operations for real-time signal processing, including the processing of audio and images [38]. Additionally, cryptographic systems make use of their quick modular arithmetic skills to provide strong data security. Parallel prefix adders are utilized by network switches and routers. Parallel prefix adders are also used in error correction codes in memory systems to ensure data integrity, and they are also used in network routers and switches for quick packet routing and switching [39]. They are an essential part of many applications needing high-speed arithmetic operations, and their effect can be seen in digital filters, graphics processing units, high-performance computing, image and video compression, and even FPGA and ASIC designs [40][41]. The core of contemporary digital systems is parallel prefix adders, which maximize performance in a variety of application [42].

Conclusion

Due to their logarithmic delay, parallel-prefix structures have been found to be appealing for adders. The path for Adders Design\'s quicker development has been cleared by this project analysis. Our only goal was to identify which of the many binary and PPA types previously discussed was the fastest adder. The results demonstrated that, when the lower bits are considered, there is almost no difference in delays; however, when the number of bits is increased, there is a noticeable difference in delays. Once more, the area used will increase with the number of LUTs used. The findings imply that no one architecture type is optimal for all bit values; rather, they provide sufficient information to determine which kind of adders is most effective for a given bit value. Bold fonts are used to highlight the comparison view\'s best numbers. In terms of the future, we can go into more detail about other crucial design factors like area, power, energy, and comparability. In order to optimize tree-based adder designs for place and routing, it would be beneficial for future FPG A designs to incorporate an optimized carry path.

References

[1] A. Beaumont-Smith and C. . -C. Lim, \"Parallel prefix adder design,\" Proceedings 15th IEEE Symposium on Computer Arithmetic. ARITH-15 2001, Vail, CO, USA, 2001, pp. 218-225, doi: 10.1109/ARITH.2001.930122. [2] K. S. Pandey, D. K. B, N. Goel and H. Shrimali, \"An Ultra-Fast Parallel Prefix Adder,\" 2019 IEEE 26th Symposium on Computer Arithmetic (ARITH), Kyoto, Japan, 2019, pp. 125-134, doi: 10.1109/ARITH.2019.00034. [3] U. Penchalaiah and S. K. VG, \"Design of High-Speed and Energy-Efficient Parallel Prefix Kogge Stone Adder,\" 2018 IEEE International Conference on System, Computation, Automation and Networking(ICSCA), [4] R. Nicole, “Title of paper with only first word capitalized,” J. Name Stand. Abbrev., in press. [5] Y. Yorozu, M. Hirano, K. Oka, and Y. Tagawa, “Electron spectroscopy studies on magneto-optical media and plastic substrate interface,” IEEE Transl. J. Magn. Japan, vol. 2, pp. 740–741, August 1987 [Digests 9th Annual Conf. Magnetics Japan, p. 301, 1982]. [6] M. Young, The Technical Writer’s Handbook. Mill Valley, CA: University Science, 1989 [7] Raju, Aradhana & Patnaik, Richi & Babu, Ritto & Mahato, Purabi. (2016). Parallel prefix adders — A comparative study for fastest response. 1-6. 10.1109/CESYS.2016.7889974. [8] Avinash Shrivastava et al. Int. Journal of Engineering Research and Application, www.ijera.com ISSN : 2248-9622, Vol. 7, Issue 4, ( Part -5) April 2017, pp.01-08 [9] A. Garg, D. Agrawal, P. Kularia, N. Gaur, A. Mehra and S. Rajput, \"Area efficient modified booth adder based on sklansky adder,\" 2017 2nd International Conference for Convergence in Technology (I2CT), Mumbai, India, 2017, pp. 308-312, doi: 10.1109/I2CT.2017.8226142. [10] Design and Analysis of 32-bit Parallel Prefix Adders for Low Power VLSI Applications,Volume 4, Issue 2, Page No 102-106, 2019Author’s Name: Samraj Daphnia), Kasinadar Sundari Vijula Grace [11] Basha, S. Mahaboob and Dollu Madhu Mohan. “Design and Characterization of Parallel Prefix Adders.” International Journal of Research 6 (2019): 28-48. [12] J. R. Dinesh Kumar & C. Ganesh Babu (2023) Performance Investigation of a Modified Hybrid Parallel Prefix Adder for Speedy and Lesser Power Computations, IETE Journal of Research, 69:5, 2310-2327, DOI: 10.1080/03772063.2022.2108914 [13] Implementation of Efficient Parallel Prefix Adders for Residue Number System,CH. Pavan Kumar1 and K.Sivani2 ,1, 2 KITS, Warangal, Telangana, India ,Received 22 March 2015, Revised 1 July 2015, Accepted 20 August 2015, Published 1 October 2015 [14] Implementation of 32-Bit Parallel Prefix Adders and Comparative Study forFastest Response,CHILAKA LYDIA1, Dr. M. ASHOK KUMAR2 1 P.G Scholor, PYDAH College of Engineering & Technology, Visakhapatnam, Andhra Pradesh, 2 Associate Professor, PYDAH College of Engineering & Technology, Visakhapatnam, Andhra Pradesh. [15] S. K.C., S. M., G. B.C., L. D.M., Navya and P. N.V., \"Performance Analysis of Parallel Prefix Adder for Datapath Vlsi Design,\" 2018 Second International Conference on Inventive Communication and Computational Technologies (ICICCT), Coimbatore, India, 2018, pp. 1552-1555, doi: 10.1109/ICICCT.2018.8473087. [16] Higher Radix Kogge-Stone Parallel Prefix Adder Architectures ,FrankK. Gurkaynad, Yusuf Leblebicit, Laurent Chaouatt and P atrik J. McGuinnessz t Ele ctrical and Computer Enginering Department Worcester Polytechnic Institute Worcester, MA 01609 t SoCDT Advanc ti Tools, Motorola, Inc. A ustin, TX 78730 [17] Pondicherry,India,2018,pp.17,doi:10.1109/ICSCAN.2018.8541143. [18] M P, Sunil. (2018). Simulation study of brent kung adder using cadence tool. 4. 564-573. [19] Shilpa, C. & Shinde, Kunjan & Nithin, H.. (2016). Design, Implementation and Comparative Analysis of Kogge Stone Adder Using CMOS and GDI Design: A VLSI Based Approach. 570-574. 10.1109/CICN.2016.117. [20] Anjana, R. et al. “Implementation of vedic multiplier using Kogge-stone adder.” 2014 International Conference on Embedded Systems (ICES) (2014): 28-31. [21] Bai, Peng and M. Vijaya Laxmi. “Design of 128- bit Kogge-Stone Low Power Parallel Prefix VLSI Adder for High Speed Arithmetic Circuits.” (2013). [22] N. U. Kumar, K. B. Sindhuri, K. D. Teja and D. S. Satish, \"Implementation and comparison of VLSI architectures of 16 bit carry select adder using Brent Kung adder,\" 2017 Innovations in Power and Advanced Computing Technologies (i-PACT), Vellore, India, 2017, pp. 1-7, doi: 10.1109/IPACT.2017.8244982. [23] Design of High Performance Low Power 16 Bit Arithmetic Units Using Kogge-Stone Parallel Prefix Adder Architectures,Shubhajit Roy Chowdhury, Aritra Banerjee, Aniruddha Roy and Hiranmay Saha [24] Eppili, Jaya & Sai, Sri & Akshay, Kumar & Hem, Kumar & Sunil, D. & Rajesh, R.. (2023). VLSI implementation of Kogge-Stone Adder for low-power applications. i-manager\'s Journal on Digital Signal Processing. 11. 9. 10.26634/jdp.11.1.19372. [25] S. Daphni and K. S. V. Grace, \"A review analysis of parallel prefix adders for better performnce in VLSI applications,\" 2017 IEEE International Conference on Circuits and Systems (ICCS), Thiruvananthapuram, India, 2017, pp. 103-106, doi: 10.1109/ICCS1.2017.8325971. [26] Gulliya, Nikita & Baliyan, Anjali & Raj, Geetanjali. (2019). Design & Implementation of Wallace Tree Multiplier and Kogge Stone Adder. 10.13140/RG.2.2.22400.25605. [27] V. Pudi and K. Sridharan, \"Low Complexity Design of Ripple Carry and Brent–Kung Adders in QCA,\" in IEEE Transactions on Nanotechnology, vol. 11, no. 1, pp. 105-119, Jan. 2012, doi: 10.1109/TNANO.2011.2158006. [28] Saxena, Pallavi. (2015). Design of low power and high speed Carry Select Adder using Brent Kung adder. 2015 International Conference on VLSI Systems, Architecture, Technology and Applications, VLSI-SATA 2015. 1-6. 10.1109/VLSI-SATA.2015.7050465. [29] Siddhhan, Ravi & Nair, Shaji & Narayan, Rajeev & Kittur, H.. (2015). Low Power and Efficient Dadda Multiplier. Research Journal of Applied Sciences, Engineering and Technology. 9. 53-57. 10.19026/rjaset.9.1376. [30] Brent and Kung, \"A Regular Layout for Parallel Adders,\" in IEEE Transactions on Computers, vol. C-31, no. 3, pp. 260-264, March 1982, doi: 10.1109/TC.1982.1675982.. [31] Macedo, Morgana & Soares, Leonardo & Silveira, Bianca & Diniz, Cláudio & Costa, Eduardo. (2017). Exploring the use of parallel prefix adder topologies into approximate adder circuits. 298-301. 10.1109/ICECS.2017.8292078. [32] V. Pudi and K. Sridharan, \"Efficient Design of a Hybrid Adder in Quantum-Dot Cellular Automata,\" in IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 19, no. 9, pp. 1535-1548, Sept. 2011, doi: 10.1109/TVLSI.2010.2054120. [33] BabaFariddin, S. & Vijay, E.. (2013). Design of Efficient 16-Bit Parallel Prefix Ladner-Fischer Adder. International Journal of Computer Applications. 79. 10-14. 10.5120/13943-1784. [34] Ladner Fischer Adder V.Srinivas1, Gourishankar Sharma2 Assistant Professor1,2 Department of ECE Malla Reddy Engineering College [35] R. Pandey, \"Implementation of Approximate Adder circuit of Ladner Fischer Adder (16 bit),\" 2020 4th International Conference on Electronics, Communication and Aerospace Technology (ICECA), Coimbatore, India, 2020, pp. 31-34, doi: 10.1109/ICECA49313.2020.9297540. [36] Patnala, Madhu Kumar. “Design of High Speed Ladner-Fischer Based Carry Select Adder.” (2013). [37] S. Knowles, \"A family of adders,\" Proceedings 15th IEEE Symposium on Computer Arithmetic. ARITH-15 2001, Vail, CO, USA, 2001, pp. 277-281, doi: 10.1109/ARITH.2001.930129. [38] A. Garg, D. Agrawal, P. Kularia, N. Gaur, A. Mehra and S. Rajput, \"Area efficient modified booth adder based on sklansky adder,\" 2017 2nd International Conference for Convergence in Technology (I2CT), Mumbai, India, 2017, pp. 308-312, doi: 10.1109/I2CT.2017.8226142. [39] V. S. Veeravalli and A. Steininger, \"Architecture for monitoring SET propagation in 16-bit Sklansky adder,\" Fifteenth International Symposium on Quality Electronic Design, Santa Clara, CA, USA, 2014, pp. 412-419, doi: 10.1109/ISQED.2014.6783354. [40] A. Prasath A.M., R. V. Arjun, K. Deepaknath and K. Gayathree, \"Implementation of optimized digital filter using sklansky adder and kogge stone adder,\" 2020 6th International Conference on Advanced Computing and Communication Systems (ICACCS), Coimbatore, India, 2020, pp. 661-664, doi: 10.1109/ICACCS48705.2020.9074440. [41] M. Moghaddam and M. B. Ghaznavi-Ghoushchi, \"A new low-power, low-area, parallel prefix Sklansky adder with reduced inter-stage connections complexity,\" 2011 IEEE EUROCON - International Conference on Computer as a Tool, Lisbon,Portugal,2011,pp.14,doi:10.1109/EUROCON.2011.5929280. [42] Dakupati.Ravi Sankar, Shaik Ashraf Ali / International Journal of Engineering Research and Applications (IJERA) ISSN: 2248-9622 ,www.ijera.com Vol. 3, Issue 1, January -February 2013, pp.1036-1040,Design of Wallace Tree Multiplier by Sklansky Adder. Dakupati.Ravi Sankar1, Shaik Ashraf Ali2. NRI Institute of Technology, Pothavarrapadu, Agiripalli (M), Vijayawada –522212, Andhra Pradesh, India.

Copyright

Copyright © 2023 Dr.S V Viraktimath , Khushi S A, Vaishnavi P, W Wiranchi. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.