A new carry save tree algorithm

Abstract

Elde taşıyıcılı toplayıcı ağaç yapıları, Carry Save Adder (CSA) tree, toplama için tasarlanmışözel mantık devre yapılarıdır. İkilik tabanda üç veya daha fazla n-bit sayının toplamını tek birsonuç yerine iki sayıdan oluşan bir ara sonuç olarak hesaplamayı amaçlarlar. Bu iki sayınınson bir toplayıcıyla toplanması istenen sonuca ulaşılmasını sağlar. Bu işlemigerçekleştirebilmek için yarım toplayıcı ve tam toplayıcı gibi sayıcı devreler kullanılmaktadır.Bu işleme aynı zamanda sütun sıkıştırma da denmektedir. Biz CSA ismi yerine elde taşıyıcılıağaç yapıları, Carry Save Tree (CST) ismini kullanacağız.Bu tez çalışmasında sürme tabanlıCST (PCST) oluşturma adlı özgün bir CST algoritması sunulmuştur. PCST nin bir parçasıolarak kullandığımız ve son toplayıcıda bit genişliğini azaltan özel tekniğimize sürme(Plowing) adını verdik. Bu tez çalışması içerisinde PCST, yarım ve tam toplayıcılarlatanımlanmış olsada esnek yapısından ötürü diğer çok girişli sayıcı devrelerlede kullanılabilir.Sentez ve test amacıyla kullanılmak üzere Perl dilinde donanım tanımlama dili (HDL) koduüreten bir script hazırlanmıştır. Bu script farklı CST algoritmalarını ufak değişikliklerleçalıştırabilmektedir. Wallace ağaç yapısı ve Dadda Ağaç yapısını hali hazırdadesteklemektedir. Bu scriptin en önemli özelliği zamana bağlı olarak CST algoritmalarınıgerçeklemesidir. Zamana bağlıdan kastedilen bitlerin gecikmelerine bağlı olarak yarımtoplayıcı ve tam toplayıcı devrelerin girişleriyle eşleştirilmesidir bu yapılırken tam toplayıcıve yarım toplayıcı devrelerinin girişten çıkışa olan gecikmelerinin birbirlerine eşit olmadığıgöz önünde bulundurulmuştur. Bu yöntem CST devresinin toplam gecikmesininoptimizasyonunu sağlar. PCST endüstriyel sentez yazılımlarından (örnek, SynopsysDC/DesignWare) daha iyi sonuçlar üretebilen devreler oluşturabilmektedir. Tezde Wallaceağaç yapısı, Dadda ağaç yapısı ve PCST kullanarak belli bir değerde doyuma ulaşan işaretsiztoplama ve çarpma işlemleri gerçeklenmiştir. Yapılan sentezlerin yüzde 88.68 inde zamanabağlı üretilen PCST, Wallace ağaç yapısı ve Dadda ağaç yapısı daha iyi sonuçlar üretmiştir.PCST algoritması belli bir değerde doyuma uylaşan işaretsiz çarpma işlemleri için yapılansentezlerin yüzde 9.43'ünde, belli bir değerde doyuma ulaşan işaretsiz toplama işlemleri içinyapılan sentezlerin yüzde 53.85'inde diğerlerine göre daha iyi sonuçlar üretmiştir.Anahtar Kelimeler: CSA ağaç yapıları, Satır Sıkıştırma, Wallace ağaç yapısı, Dadda ağaçyapısı

Carry Save Adder (CSA) trees are special logic circuit structures for summation. They arealso mainly used for multiplication which is a special form of summation. They target tocompute the sum of three or more n-bit binary numbers and produce two numbers instead ofone as a result. Addition of these two numbers by a final adder gives the actual result. To doso it uses logic blocks named counters like half adder and full adder. This process is alsonamed as column compression. We will use Carry Save Tree (CST) name instead of CarrySave Adder (CSA) tree. In this thesis a novel CST algorithm is introduced which we namedas Plowing based Carry Save Tree (PCST) generation. Plowing word is used to define aspecial technique we use as part of PCST that reduces the bitwidth of the final adder. Thoughthe algorithm is defined by the use of full adders and half adders, it can be defined withdifferent counter structure with more inputs, because it is actually a topology not a singledesign definition. For the synthesis and functional testing purposes a HDL code generator iswritten in Perl. This generator is capable of applying different CST algorithms with minorchanges. Wallace tree, Dadda tree and PCST are already defined in this generator. Most vitalpoint about this generator is its time routed CST generation capability. What we mean by timerouting is the matching process of bits according to their delays with the half adder and fulladder inputs considering that there isn?t a fixed delay for each input to output path. Thisprovides an optimization for the critical path of the CST circuit. PCST yields circuits withbetter than even commercial software synthesis tools (e.g., Synopsys DC/DesignWare).Weimplemented Wallace tree, Dadda tree, and PCST for saturated unsigned summation andmultiplication.Time routed PCST, Wallace tree, and Dadda Tree generator outputs gave better timing resultsthan ordinary ones up to 88.68 percent of the cases. PCST gave better timing results of 9.43percent for saturated unsigned multiplication cases and 53.85 percent for saturated unsignedsummation cases.Keywords: CSA tree, Column Compression, Wallace tree, Dadda tree.