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.
