Sıkıştırılmış Başvuru Çizelgeleri Kullanarak Yarı-rastgele Erişilebilir İşlevlerin Verimli Mantıksal Gerçeklemesi

Abstract

Cebirsel ve cebirsel olmayan fonksiyonlar (örneğin, ex, cosx, logx..) bilimsel hesaplamalar ve sayısal işaret işleme uygulamalarında yoğun biçimde kullanılmaktadır. Bu fonksiyonları hızlı ve düşük kaynak kullanarak hesaplamak bilgisayar sistemlerinde önemli bir araştırma konusudur. Cebirsel olan fonksiyonlar polinomlar üzerinden dört işlem, kök ve üst alma işlemleri sonucu elde edilir. Cebirsel olmayan fonksiyonlar ise bu şekilde ifade edilemeyen fonksiyonlardır. Bu tür fonksiyonları hesaplayabilmek için polinomlarla ifade edilmesi gereklidir. Cebirsel olmayan fonksiyonları polinomlarla ifade edebilmek için Taylor serisi kullanılabilir. Gerçek zamanlı olmayan uygulamalarda belirlenen bir hata değerine kadar, serinin gerekli olan elemanları hesaba katılır. Serideki eleman sayısı arttıkça, hesaplama hatası azalır ancak hesaplamanın süresi artar. Örnek olarak ele aldığımız sinüs seri açılımına dayalı hesaplama işlemi bir programa yaptırıldığında belli bir süre almaktadır. Bu hesaplama süresi, zaman kısıtı olan gerçek zaman uygulamalarında sorunlara neden olmaktadır. Zaman kısıtının olduğu gerçek zamanlı uygulamalarda hesaplamanın hızlı yapılabilmesi için fonksiyon değerlerinin önceden hesaplanmasına gidilir. Bu yönteme “Başvuru Çizelgesi” (BÇ) yöntemi denir. Bir başka yöntem, ardışıl yaklaşım yöntemi fonksiyonun değerlerini hesaplamaktır. Ardışıl yaklaşım yöntemleri için önemli bir örnek Coordinate Rotation Digital Computer (CORDIC) tir. CORDIC trigonometrik fonksiyonları hesaplamak için özelleşmiş bir yöntemdir. CORDIC’te belirli rotasyon açılarının tanjant değerlerini tutan bir BÇ kullanılır. Bu değerler hesaplanması istenen açı değerine yaklaşırken rotasyonlarda kullanılan değerlerdir. Yüksek çözünürlüklü sonuç elde edilmek için adım sayısı artırılır. Sonuç olarak adım sayısının artması hesaplama süresini artırır. Bu yöntemin ana özelliği, hesaplama süresinin, hesaplamadan beklenen doğrulukla orantılı olmasıdır. Başvuru çizelgesi tabanlı yöntemler parçalı ve toplamalı olmak üzere ikiye ayrılır: Parçalı BÇ yöntemi ve Toplamalı BÇ Yöntemi. Parçalı BÇ yönteminde fonksiyon önceden belli parçalara ayrılır. Bu parçalar üzerinde işlem yapılır. Toplamalı BÇ yönteminde ise sadece değerler BÇ de tutulur. Herhangi bir çarpma işlemi yapılmaz, sadece tablodaki değerlerin toplamı ile sonuç üretilir. Fonksiyon üretme yöntemleri ile ilgili çalışmalar ağırlıklı olarak başvuru çizelgesinin boyutunu küçültmeye, mantıksal devreyi küçültmeye ve kritik yolu azaltmayı hedeflemektedir. Bu tez çalışmasında toplamalı BÇ yöntemine uygun yeni bir yöntem önerilip kendine benzer yöntemlerle karşılaştırılması yapılıp sonuçlar sunulacaktır. Tez çalışmasında bu tür fonksiyonları gerçekleyebilmek BÇ’nin kapladığı alanı küçülten ve mantıksal devrenin gecikmesini azaltan melez bir çözüm önerilmiştir. Önerilen çözümün diğer bir üstünlüğü ise doğrudan BÇ yöntemi ile sağlanan rastgele erişim belli ölçüde sağlanmaktadır. Önerilen yöntem ile fonksiyonun ardışık elemanları arası sadece fark bilgileri tutularak bellekte %75 oranında küçülme sağlanmıştır. Önerilen çözüm Verilog-HDL dilinde yazılmıştır. Geliştirilen çözümü sentezlenme ortamı ise Xilinx Spartan-6 FPGA’dir. Çalışmamızda, örnek olarak trigonometrik fonksiyon olan sinüs hesaplaması yapılmıştır. Ayrıca ekler kısmında 16-bit giriş ve çıkış çözünürlüğüne sahip sinüs üreteci için tasarlanan çözümün Verilog-HDL kodları verilmiştir.

Generating waveforms is a fundamental problem in signal processing applications. Low-latency calculation of a transcendental (i.e., non-algebraic) functions is an expensive operation, therefore many improvements have been proposed. A well-known method is to store all the pre-computed values in a piece of memory, called Look-Up Table (LUT), and directly send them as output. Although this is the fastest way of doing it, using a large memory is expensive in terms of both power and area. The state of the art methods present hybrid approaches that use efficient functions with smaller look-up tables. Usage of a LUT is indispensable. Moreover, the LUT method is the only practical option in cases where transcendental functions need to be computed in real-time. Therefore, LUT reduction is still an active research area. LUT based method is separated into two categories: Piecewise and Addition based LUT methods. Piecewise LUT method is also separated into two categories: approximation and interpolation method. Approximation method calculates nth order polynomial with minimum error. Coefficients of the polynomial expression are stored into LUT. Desired value is calculated using these coefficients in run-time. Product and summation blocks are used. Product determines critical path of the system. Interpolation method everything is same as approximation. However, simple interpolation polynomials, which is linear interpolation, can be calculated in run-time. Product and summation blocks are also necessary. Addition based LUT method only uses summation. Result is superposition of LUT elements. Disadvantages of this method is that it requires more memory space than previous methods. Our method is classified in this section. In this thesis, we propose a new look-up table (LUT) based logic architecture for implementation of transcendental functions, which is low-latency but area efficient. Our architecture improves on the LUT approach by storing not the function values but the differences of consecutive function values. Storing just the differences offers a significant reduction in LUT size, hence reducing hardware area. A simple function generator that generates a fixed sequence of values is quite straight-forward and can easily benefit from our idea. However, what is proposed here is beyond that. Our architecture allows a certain level of random access with little loss in speed-up. Such non-fixed function generators are useful in control systems. We demonstrate our idea through a 16-bit sine generator implemented on FPGA, where the LUT size reduction is 4x. Our novel method is called “compressed LUT” (cLUT) in this thesis. We compress the LUT by storing differences of consecutive values in cLUT instead of actual values of the function. As an example, instead of storing 16-bit values, we store 4-bit differences and then calculate actual function outputs from differences. Bit-width of difference depends on first derivative of the target function. If first derivative is higher, difference needs to more area. Hence, memory utilization closes direct LUT method. The cLUT method offers a significant reduction in memory for a compromise in the level of random access. This is acceptable since most applications require more or less consecutive access to a function as the independent variable of the function comes from a physical quantity that has some continuity. The method consists of three main modules, which are address generation, memory array, and data calculation. Memory array consists of delta number of cLUT, which stores the differences. Output is the value of the signal for the given index . The previously requested output is stored in the data calculation module and used to calculate current requested output. A random output can be selected in the range of . The necessary cLUT cells are selected by the address generator based on the requested. As a result, the output is calculated by a small amount of logic and sent out in a single clock cycle. The memory array consists of delta number of cLUTs. Pre-computed differential signal values are stored in cLUTs in a special way. Subsequent data is stored in the same addresses of the parallel cLUTs. This means that if the cell of first cLUT stores the signal data indexed by , cell consists of the data indexed by . Memories are read in parallel under the control of the address generation module. The address generation module calculates the required memory accesses according to input . A limited random access capability is supported, thanks to the address generation module. Input can be smaller or bigger than the previous as the number of memory. Address generation module is composed of two main parts, which are differential address calculation unit and memory address control unit. Differential address calculation unit keeps the previous address in a register and calculates intermediate results that will be used by address control unit and data selection unit. First, previous input is subtracted from the current input so that the differential address, which may be forward or backward, is calculated. The result of subtraction is interpreted as magnitude and sign. The vector, named as thermo, is shifted in the direction of sign as the amount of the Magnitude. Finally, thermo and the result of shift are XORed. Output of the XOR block is used to determine the cLUT selection. Shifting operation operates on thermo vector, whose size is . First , second , and last bits of thermo are always 0, while the third bits is the result of thermometer regulator block. Thermometer regulator block is used to handle the overflows that occur because of shifting operation. This block checks upper and lower side of thermo and selects the convenient thermo vector as given in Fig. 4. Memory address controller unit takes XOR outputs of differential address calculation unit and outputs necessary cLUT addresses. In order to calculate the next address of cLUTs, a conditional addition mechanism is designed. Addition is selected by the output of the differential address calculation unit and 1, -1 or 0 added to address register, which stores the previous address. For example, current address pointer points to any location of last memory bank and the desired value is 3 steps forward from the current pointer. In this situation, address pointer should be incremented by 1 because of the current pointer location. The address register and its update mechanism is shown in Fig. 7. Data selection unit selects and sums the outputs of the cLUTs using the XOR outputs of address calculation unit. As an example, consider a scenario that a random access is applied to 3 steps behind. Only outputs of 3 cLUTs will be summed. In this paper, we have presented a compressed look up table (cLUT) method for function generation, which provides a limited amount of random data access. A 16-bit addressable and 16-bit value sine function is implemented on Xilinx Spartan-6 FPGA using the proposed cLUT method. Memory requirement has been reduced, by the ratio of 75%, to 32kB from 128kB. The clock frequency achieved for this hardware is 87,4 MHz.