A new carry save tree algorithm
Yeni bir carry save tree algoritması
- Tez No: 266495
- Danışmanlar: YRD. DOÇ. DR. H. FATİH UĞURDAĞ
- Tez Türü: Yüksek Lisans
- Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
- Anahtar Kelimeler: CSA ağaç yapıları, Satır Sıkıştırma, Wallace ağaç yapısı, Dadda ağaçyapısı, CSA tree, Column Compression, Wallace tree, Dadda tree
- Yıl: 2010
- Dil: İngilizce
- Üniversite: Bahçeşehir Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektrik-Elektronik Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 64
Özet
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.
Özet (Çeviri)
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.
Benzer Tezler
- VHDL ile lojik devre tasarımı ve DSP uygulamaları için çarpma bloklarının modellenmesi
Başlık çevirisi yok
SIDDIKA BERNA ÖRS
Yüksek Lisans
Türkçe
1998
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. AHMET DERVİŞOĞLU
- Wave component sampling method for high performance pipelined circuits
Yüksek performanslı boru hattı mimarili devreler için dalga elemanı örnekleme metodu
REFİK SEVER
Doktora
İngilizce
2011
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiElektrik ve Elektronik Mühendisliği Bölümü
PROF. DR. MURAT AŞKAR
- Bursa örneğinde, kentleşmenin yeşil kent dokusu üzerindeki etkilerinin incelenmesi
Analyzing the effects of urbanisation on green urban tissue, on the example of the Bursa
FERDA ACAY
Yüksek Lisans
Türkçe
1997
Peyzaj Mimarlığıİstanbul Teknik ÜniversitesiPeyzaj Mimarlığı Ana Bilim Dalı
DOÇ. DR. NİLGÜN ERGUN
- Yeni bir çevrimiçi sınav modeli geliştirilmesi ve kağıt kalem testleri ile karşılaştırılması
Designing a new online examination model and a comparision with paper-based test
MUSTAFA YAĞCI
Doktora
Türkçe
2012
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSakarya ÜniversitesiElektronik-Bilgisayar Eğitimi Ana Bilim Dalı
PROF. DR. HÜSEYİN EKİZ
- Reaktif güç kontrol rölesinde optimal anahtarlama için yeni bir yöntem
A new method for optimal switching in reactive power control relay
MUSTAFA ŞEKKELİ
Doktora
Türkçe
2004
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektrik Mühendisliği Ana Bilim Dalı
PROF.DR. NESRİN TARKAN