MLUE : Multiple look-up table based exponentiation

Abstract

Many scientific applications require computation of exponents. In this thesis, we are specifically interested in computing a constant to the power of a variable number (ax), which can always be converted to 2x through an extra multiplication without loss of generality. In real-time systems or any application where run-time matters, ax is computed using a Look-Up Table (LUT). However, when the targeted precision is high, the table size blows up. Piecewise Polynomial Approximation (PPA) offers a tradeoff between speed and table size and is commonly used in the literature. Our contribution in this thesis is an alternative method, which can also offer a trade-off between speed and table size. It is called MLUE (short for Multiple Look-Up table based Exponentiation). MLUE partitions the input bits into segments. There is a LUT for each segment, and the result is the product of LUT outputs. While PPAs contain both method error and truncation error, MLUE has only truncation error. Although MLUE can be utilized in software implementations, we have looked at its performance when implemented in hardware – and specifically with combinational logic. Our claim is that MLUE offers smaller area for a reasonable target speed and precision. We wrote fully automated and parameterized design (RTL level Verilog) generators for both PPA and MLUE. We back up our claim through numerous results obtained with an automated regression script, which calls our generators. The contributions of this thesis also include regression methodology/scripts, a novel logic synthesis strategy/script, fully automated testing of the generated designs as well as automatic determination polynomial degree in PPA and number of MLUE bit partitions.

Birçok bilimsel uygulama üs hesaplaması gerektirir. Bu tezde, biz özellikle bir sabit sayının değişken bir üssünü (ax) almayla ilgileniyoruz. ax her durumda ekstra bir çarpma kullanarak 2x’e dönüştürülebilir. Gerçek-zamanlı sistemlerde veya işlem süresinin kritik olduğu tüm uygulamalarda, ax bir sayı-tablosu (LUT: Look-Up Table) kullanarak hesaplanabilir. Ancak hedeflenen hesap hassasiyeti yüksek olduğunda, tablo boyutu aşırı büyür. Parçalı Polinom Yaklaşıklama (PPA: Piecewise Polynomial Approximation) hesaplama hızı ve tablo boyutu arasında bir dengeleme yapılmasına imkân verir. Bu tezin literatüre katkısı, aynı şekilde bir dengelemeyi mümkün kılan alternatif bir yöntemdir. Bu yöntemin ismi MLUE’dur (Çoklu Sayı-Tablosu Kullanarak Üs Alma’nın kısaltması). MLUE argümanın bitlerini segmanlara böler. Her segman için bir LUT oluşturulur ve işlem sonucu LUT çıkışlarını çarparak hesaplanır. PPA’de hem metot hem de kırpma hatası varken, MLUE’da sadece kırpma hatası vardır. MLUE’dan yazılım uygulamalarında da faydalanılabilir; ama biz MLUE’nun donanım olarak (birleşimsel lojikle) gerçeklendiğindeki performasını değerlendirdik. Hipotezimiz, MLUE’nun belli bir hız (aşırı olmayan) ve hassasiyet için rakiplerine göre daha az alanlı tasarımlar ürettiğidir. Hem PPA hem de MLUE için otomatik ve parametrize tasarım (RTL seviyesinde Verilog) üreteçleri yazdık. Hipotezimizi otomatik bir regresyon programı tarafından (Verilog üreteçlerimizi çağıran) üretilmiş birçok sentez sonucu ile destekliyoruz. Bu tezin literatüre katkıları arasında, regresyon metodolojisi/kodları, yeni bir lojik sentez stratejisi/kodu, üretilen tasarımların tamotomatik testi ve PPA polinom derecesi ile MLUE bit segmanlarının sayısının otomatik olarak belirlenmesi de vardır.