# Semi- and Fully-Random Access LUTs for Smooth Functions

Y. Serhan Gener, Furkan Aydin, Sezer Gören, H. Fatih Ugurdag

► To cite this version:

Y. Serhan Gener, Furkan Aydin, Sezer Gören, H. Fatih Ugurdag. Semi- and Fully-Random Access LUTs for Smooth Functions. 27th IFIP/IEEE International Conference on Very Large Scale Integration - System on a Chip (VLSI-SoC), Oct 2019, Cusco, Peru. pp.279-306, 10.1007/978-3-030-53273-4_13. hal-03476614

HAL Id: hal-03476614

https://inria.hal.science/hal-03476614

Submitted on 13 Dec 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Semi- and Fully-Random Access LUTs
for Smooth Functions

Y. Serhan Gener¹, Furkan Aydin², Sezer Gören³, and H. Fatih Ugurdag⁴

¹ Dept. of Computer Science, University of California Riverside, CA, USA
[ygene001@ucr.edu](mailto:ygene001@ucr.edu)

² Dept. of Electrical & Computer Eng., North Carolina State University, NC, USA
[faydn@ncsu.edu](mailto:faydn@ncsu.edu)

³ Dept. of Computer Eng., Yeditepe University, Istanbul, Turkey
[sgoren@cse.yeditepe.edu.tr](mailto:sgoren@cse.yeditepe.edu.tr)

⁴ Dept. of Electrical & Electronics Eng., Ozyegin University, Istanbul, Turkey
[fatih.ugurdag@ozyegin.edu.tr](mailto:fatih.ugurdag@ozyegin.edu.tr)

**Abstract.** Look-Up Table (LUT) implementation of complicated func-
tions often offers lower latency compared to algebraic implementations at
the expense of significant area penalty. If the function is smooth, Multi-
Partite table method (MP) can circumvent the area problem by breaking
up the implementation into multiple smaller LUTs. However, even some
of these smaller LUTs may be big in high accuracy MP implementations.
Lossless LUT compression can be applied to these LUTs to further im-
prove area and even timing in some cases. The state-of-the-art in the
literature decomposes the Table of Initial Values (TIV) of MP into a
table of pivots and tables of differences from the pivots. Our technique
instead places differences of consecutive elements in the difference tables
and result in a smaller range of differences that fit in fewer bits. Con-
straining the difference of consecutive input values, hence semi-random
access, allows us to further optimize designs. We also propose variants of
our techniques with variable length coding. We implemented Verilog gen-
erators of MP for sine and exponential using conventional LUT as well
as different versions of the state-of-the-art and our technique. We syn-
thesized the generated designs on FPGA and found that our techniques
produce up to 29% improvement in area, 11% improvement in timing,
and 26% improvement in area-time product over the state-of-the-art.

# 1 Introduction

Computationally complex functions often need to be efficiently implemented in
hardware so that they can be part of real-time systems. Look-Up Table (LUT)
based methods (see [1] for a comprehensive survey) offer a good balance between
latency and area in comparison to algebraic methods by a priori computing of the
function values. LUT-based methods usually have shorter latency as compared
to algebraic methods. A straight-forward LUT method, where function value
f(x) is stored in (read-only) memory's location x, and the input x is tied to the
address port of the memory and the output f(x) is tied to the dataOut port
of the memory (without any additional logic) is what we call the Conventional LUT (ConvLUT) method shown in Fig. 1. However, for large bit widths of x, the area of a ConvLUT blows up.

What we are proposing in this work is a “lossless LUT compression method” that can shrink the hardware area of complex functions (sometimes even with improvements in latency) when applied to:

- ConvLUTs or

- the below smarter methods with multiple LUTs

<figure><img src="image_2.png" /><figcaption>Fig. 1. LUT contents of a ConvLUT.</figcaption></figure>

When a ConvLUT blows up due to large input bit width, “multi-LUT methods” (including ours) come to rescue. Although our lossless compression method can be directly applied to ConvLUT, better results are obtained if a lossy multi-LUT method is used first, and our method is applied to the LUTs within. Multi-LUT methods use some arithmetic logic to combine the values in multiple tables. These methods do not produce the exact same output as the ConvLUT method but can stay within a prescribed error range. Some such popular methods are BiPartite method (BP) [2][3], Symmetric Bipartite Method (SBTM) [4], Symmetric Table Addition Method (STAM) [5], MultiPartite method (MP) [6][7], and Hierarchical MultiPartite method (HMP) [8].

BP [2][3] uses approximation by the first two terms of the Taylor expansion of a function using two LUTs: i. Table of Initial Values (TIV) and ii. Table of Offsets (TOs). The microarchitecture in Fig. 2 becomes BP, when the three TOs are combined into a single TO. BP uses an adder to add TIV and TO outputs. TIV downsamples the function values and hence stores a subset of them (at $x0$ values), whereas TO stores the derivative times $\Delta x(= x - x0)$.

For further reduction in TO size, TO can be partitioned into multiple smaller LUTs, which thus leads to the MP method. MP combines STAM [5] and the approach in [9]. In MP, there are multiple TOs and a single TIV. Fig. 2 depicts an MP microarchitecture with 3 TOs. A smaller $\Delta x$ can work with a derivative with fewer bits, hence the smaller the $\Delta x$ the narrower the $x0$ bits (subset) it uses. Each additional table reduces the total number of bits in all of the tables
<figure><img src="image_3.png" /><figcaption>Fig. 2. MP microarchitecture.</figcaption></figure>

but then increases the combinational logic complexity - all in all reduces the
total area.

In the recently proposed HMP method [8], the TIV is further decomposed
into the sum of another TIV and TOs. HMP also performs global bit width
optimization over all LUTs.

Fig. 3 sketches the LUT compression approach within the context of MP. For
any given function $f$, with any given input bit resolution ($w_i$), i.e., bit width,
output resolution ($w_o$), and $m$ value (which represents the number of TOs to be
generated), MP can be implemented as shown in Fig. 3, where $TIV_{new}$ is a new
TIV with fewer entries than TIV, while $TIV_{diff}$'s store differences of missing
entries from the entries $TIV_{new}$. Our lossless LUT compression and the one in
[11] can actually be applied to any LUT, hence TIV or TOs or both. However,
we applied it on TIV, as there is more compression opportunity in TIV because
it is bigger. Also, [11] is applied on TIV, and we wanted to compare our work
to theirs.

The concept of general-purpose lossless LUT compression for hardware design
was first introduced in [10]. The work in [10] proposes what we here classify
as Semi-Random Access differential LUT (SR-dLUT), where differential LUT
(dLUT) is a sort of $TIV_{diff}$. Note that [10] calls the dLUT in this chapter as
cLUT, short for “compressed LUT”. SR-dLUT can output any LUT location
within the range $[i - k, i + k]$ in a given cycle if location $i$ is output in the
previous cycle and $k$ is the number of difference tables (dLUT). Note that there
is no $TIV_{new}$ in SR-dLUT, there are only difference tables (cLUT in the case of
[10]).
<figure><img src="image_4.png" /><figcaption>Fig. 3. MP method combined with LUT compression for TIV.</figcaption></figure>

In [11], a lossless LUT compression approach was proposed and was used to
compress the TIV of MP method. Two schemes were proposed in [11], namely,
2-table decomposition and 3-table decomposition. We abbreviate them as 2T-
TIV and 3T-TIV, respectively. Details of both methods are discussed in Section
2.1 and 2.2. Furthermore, in [8] an improvement over the 2T-TIV method was
introduced, which we call 2T-TIV-IMP and discuss in detail in Section 2.3.

In this chapter, we propose four lossless LUT compression methods, namely, Fully-Random Access differential LUT (FR-dLUT) and Semi-Random Access differential LUT (SR-dLUT), “Variable Length” encoded FR-dLUT (FR-dLUT-VL), and “Variable Length” encoded SR-dLUT (SR-dLUT-VL). Note that FR-dLUT and FR-dLUT-VL microarchitectures were first proposed in our earlier paper [16] and an earlier version of SR-dLUT (cLUT) was introduced in [10]. SR-dLUT-VL is unique to this chapter. Also, SR-dLUT is here used as a building block of MP. Note that although this chapter targets hardware implementation, software implementation of our proposed methods are also possible.

Section 2 below covers the details of the state-of-the-art, namely, 2T-TIV
[11], 3T-TIV [11], and 2T-TIV-IMP [8] (which we call T-TIV methods), while
Section 3 presents our proposed methods. Section 4 gives synthesis results (area,
time, and area-time product) of all of the above methods and compares them,
and Section 5 concludes the chapter.

2 State-of-The-Art

In this section, previous state-of-the-art of fully-random access lossless LUT
compression are outlined, namely, T-TIV methods.

## 2.1 2T-TIV Microarchitecture

2T-TIV [11] decomposes TIV of the MP method into 2 LUTs, TIV$_{new}$ and TIV$_{diff}$ (i.e., a form of dLUT) as shown in Fig. 4, where the original TIV can be recovered from TIV$_{new}$ and TIV$_{diff}$ without introducing any errors.
<figure><img src="image_5.png" /><figcaption>Fig. 4. LUT contents of 2T-TIV for s = 2.</figcaption></figure>

In Fig. 4, we have $w_i = 16$ and $s = 2$ such that for every $2^s$ consecutive entries, $TIV_{new}$ stores one TIV value (i.e., the one in the middle of $2^s$). That is why $TIV_{new}$ has $2^{wi-s}$ entries. $TIV_{diff}$ is used to store differences between the original TIV values and their corresponding entries in $TIV_{new}$. Equation (1) shows how TIV is reconstructed back from $TIV_{new}$ and $TIV_{diff}$.

$$ \begin{array}{l} \text{TIV}(i) = \text{TIV}_{\text{new}}(i') + \text{TIV}_{\text{diff}}(i) \\ \text{where } i' = \text{integer} \left(\frac{i}{2^s}\right) \\ \text{and } \text{TIV}_{\text{new}}(i') = \text{TIV}(i' * 2^s + 2^{s-1}) \end{array} \qquad (1) $$

Note that every $2^s$ entries of $TIV_{diff}$ contains one zero entry (i.e., entries 2, 6, 10, etc. in Fig. 4).

## 2.2 3T-TIV Microarchitecture

3T-TIV [11] exploits the “almost symmetry” of function values around the entries of $TIV_{new}$. 3T-TIV has 3 LUTs as shown in Fig. 5 for a given function with $w_i = 16$ and $s = 3$. In 3T-TIV, $TIV_{new}$ serves the same purpose as in 2T-TIV. Fig. 5 shows an example, where $w_i = 16$ and $s = 3$. Hence, there is one entry in $TIV_{new}$ for every $8(= 2^{s=3})$ entries of the original TIV. The entries in $TIV_{new}$ correspond to f(4), f(12), f(20), and so on. The values of f(0), f(1), and up to f(7) need to be computed from f(4) in $TIV_{new}$. Half of those values, i.e., f(0), f(1), up to f(3) are calculated using the differences stored $TIV_{diff1}$ as in 2T-TIV, hence (2) where $i'$ is the same as in (1).

$$ \begin{array}{l} \text{TIV}(i) = \text{TIV}_{\text{new}}(i') + \text{TIV}_{\text{diff1}}(2^{s-1} * i' + j) \\ \text{for } j < 2^{s-1} \text{ where } j = \text{mod}(i, 2^s) \end{array} \qquad (2) $$

However, for f(4) through f(7), the second-order differences in $TIV_{diff2}$ are also added on top of $TIV_{new}$ and $TIV_{diff1}$. The value of f(7) is computed from f(1), while f(6) is derived from f(2), and so on. That can be expressed as in (3).
<figure><img src="image_6.png" /><figcaption>Fig. 5. LUT contents of 3T-TIV for s = 3.</figcaption></figure>

$$
\begin{align}
TIV(i) = TIV_{new}(i') &+ TIV_{diff1}(2^{s-1} * i' + j) + \nonumber \\
& TIV_{diff2}(2^{s-1} * i' + j - 2^{s-1}) \quad \text{for } j \ge 2^{s-1} \nonumber \\
& \text{where } TIV_{diff2}(k) = TIV(k' + 2^{s-1}) - \nonumber \\
& \qquad TIV(k' - 2^{s-1}) \tag{3} \\
& \text{and } k' = 2 * \text{integer}(\frac{k}{2^{s-1}}) + \text{mod}(k, 2^{s-1}) \nonumber
\end{align}
$$

In summary, when we group values of function f in groups of 2^s, the first 2^{s-1} values in every group of 2^s use TIV_new and TIV_diff1, while the second 2^{s-1} values use all three tables. Note that every 2^{s-1} entries of TIV_diff2 contains one zero entry (i.e., entry 0, 4, 8, etc. in Fig. 5).

## 2.3 2T-TIV-IMP Microarchitecture

2T-TIV-IMP [8] improves 2T-TIV [11] by reducing the bit width of TIV_new. This is possible when every TIV_diff entry is summed offline with least significant w_diff bits of the corresponding TIV_new entry. As a result of this, the least significant w_diff bits of all TIV_new entries can be zeroed out, hence do not need to be stored, which leads to a bit width of w_new - w_diff bits as shown in Fig. 6. On the other hand, TIV_diff entries become 1-bit larger (the w_diff + 1 in Fig. 6) if any TIV_diff entry overflows when summed with w_diff bits of TIV_new. If there is no overflow, then the bit width of TIV_new stays the same (w_diff).

This optimization not only reduces the bit width of TIV_new but also makes the subcircuit that sums TIV_new and TIV_diff smaller, when there is overflow resulting in 1 overlap bit, hence TIV_diff with w_diff + 1 bits. The optimization can even completely eliminate summing when there is no overflow during offline addition performed to compute the new TIV_diff values. In that case, summing TIV_new and TIV_diff can simply be realized by concatenating them.

One thing that is not addressed in [11] is that if TIV_new entries are truncated, TIV_diff entries may have to be 2-bit larger. For a guarantee on at most 1-bit larger TIV_diff, TIV_new entries have to be rounded down to w_new - w_diff bits from w_new bits.

Note that the described improvement on 2T-TIV cannot be applied to 3T-TIV because this optimization breaks the symmetry property 3T-TIV uses.
<figure><img src="image_7.png" /><figcaption>Fig. 6. 2T-TIV-IMP version of Fig. 4.</figcaption></figure>

## 3 Proposed Methods

In this section, our proposed microarchitectures, FR-dLUT and SR-dLUT as well as their variable length coded variants, namely, FR-dLUT-VL and SR-dLUT-VL, are presented. The critical difference between our approach and the previous state-of-the-art (2T-TIV and variants) is that $TIV_{diff}$ (which we call dLUT) entries store the difference from the neighboring function value instead of the difference from the corresponding value in $TIV_{new}$ as shown in (4) and (5). This allows elimination of $TIV_{new}$ if what is desired is only semi-random access [10]. If fully-random access is desired, we still need a $TIV_{new}$ table but our dLUTs store smaller differences compared to the above explained state-of-the-art. Below, we will describe FR-dLUT, SR-dLUT, FR-dLUT-VL, and SR-dLUT-VL.

### 3.1 FR-dLUT Microarchitecture

FR-dLUT can be implemented with any number of dLUTs. Fig. 7 shows an FR-dLUT with 4 dLUTs, which implements a function $f$ with $w_i = 16$ and $s = 3$ (hence $2^3 = 8$ difference values per each $TIV_{new}$ entry). If $TIV_{diff}$ in 2T-TIV and variants contain differences, dLUTs in FR-dLUT, in a way, contain difference of differences. More specifically, the entries in the dLUTs that correspond to points that neighbor $TIV_{new}$ entries (shown as shaded in Fig. 7) contain the same values as in 2T-TIV, while the other differences are equal to the differences of neighboring $TIV_{diff}$ entries in 2T-TIV (see (4) and (5)).

This allows us to store smaller values (i.e., fewer bits) in our difference tables. However, there is a tradeoff since the summation circuit gets bigger because we have to sum multiple difference values in our case. Note that, in the actual implementation, the last dLUT (i.e., dLUT3 in Fig. 7) has half the number of entries of the other dLUTs. (If logic synthesis is used, logic minimization would do area reduction when unused entries are specified as don't cares.)
<figure><img src="image_8.png" /><figcaption>Fig. 7. LUTs of FR-dLUT for $w_i = 16$, $s = 3$ (i.e., $\Delta = 2^{3-1} = 4$).</figcaption></figure>

Equations (4) and (5) are two specific examples of how original TIV values are constructed from $TIV_{new}$ and dLUTs in FR-dLUT. They are based on the tables in Fig. 7.

$$ \underbrace{f(10)}_{\text{TIV}} = \underbrace{f(12)}_{\text{TIV}_{new}} + \underbrace{f(11) - f(12)}_{\text{dLUT3}} + \underbrace{f(10) - f(11)}_{\text{dLUT2}} \quad (4) $$

$$ \underbrace{f(13)}_{\text{TIV}} = \underbrace{f(12)}_{\text{TIV}_{new}} + \underbrace{f(13) - f(12)}_{\text{dLUT0}} \quad (5) $$

The generalized construction of TIV from $TIV_{new}$ and dLUTs for FR-dLUT method is given in (6) and (7). There are separate construction formulae for odd (7) and even (6) rows of dLUTs. Note that $i'$ and $TIV_{new}(i')$ below use the definitions given earlier in (1). Also, in the summations of (6) and (7), if the upper index (finish index) is smaller than the lower index (start index), then the summation returns zero.

$$ \begin{gathered} \text{TIV}(i) = \text{TIV}_{new}(i') + \sum_{k=j}^{\Delta-1} \text{dLUTk}(2i') \quad \text{for } j \le 2^{s-1} \\ \text{where } j = \text{mod}(i, 2^s), \text{ and} \\ \text{dLUTk}(2i') = \text{TIV}(i' * 2^s + k) - \text{TIV}(i' * 2^s + k + 1) \end{gathered} \quad (6) $$

$$ \begin{gathered} \text{TIV}(i) = \text{TIV}_{new}(i') + \sum_{k=0}^{q} \text{dLUTk}(2i' + 1) \quad \text{for } j > \Delta = 2^{s-1} \\ \text{where } j = \text{mod}(i, 2^s), q = j - 2^{s-1}, \text{ and} \\ \text{dLUTk}(2i' + 1) = \text{TIV}(i' * 2^s + 2^{s-1} + k + 1) - \text{TIV}(i' * 2^s + 2^{s-1} + k) \end{gathered} \quad (7) $$

The top-level of FR-dLUT microarchitecture is shown in Fig. 8 for a function $f$ with $n$-bit input ($w_i = n$), hence $2^n$ possible output values, $k$-bit output resolution ($w_o = k$), $\Delta$ dLUTs ($\Delta = 2^s$), and $d$-bit differences. The top-level of FR-dLUT consists of 5 submodules, namely, AddressGenerator, $TIV_{new}$, a set of dLUTs, DataSelection, and SignedSummation.

If there are $\Delta$ dLUTs, where $\Delta$ is a power of 2 (to make address generation is simple), $TIV_{new}$ stores $k$-bit $TIV(\alpha)$, where $\alpha = \Delta, 3\Delta, 5\Delta, 7\Delta, \dots, 2^n - \Delta$. The number of locations in $TIV_{new}$ is $2^{(n-1)/\Delta}$. We denote the output of $TIV_{new}$ with $mval$ (short for main value). The address line of $TIV_{new}$, named as directAddress, has a bit width of $n - 1 - lg\Delta$ (lg denotes $log_2$). dLUTs store
<figure><img src="image_9.png" /><figcaption>Fig. 8. Top module of FR-dLUT microarchitecture.</figcaption></figure>

$d$-bit 2's complement differences. The number of locations in “dLUT $\Delta - 1$” is half the number of locations in the other dLUTs and is the same as in $TIV_{new}$. “dLUT of index $\Delta - 1$” shares the same address bus as $TIV_{new}$. The bit width of the address lines of other dLUTs, named as *indirectAddress*, is $n - lg\Delta$. The output of a dLUT is named *dval* (stands for “difference value”).

AddressGenerator, detailed in Fig. 9, generates three signals: *directAddress*, *indirectAddress*, and *select*. For every $2\Delta$ value in TIV, there is only one entry in $TIV_{new}$ (as well as in “dLUT $\Delta - 1$”), thus *directAddress* signal is the $n-1-lg\Delta$ most significant bits of the $n$-bit input $\alpha$ part-selected as $\alpha[n - 1 : lg\Delta + 1]$. Moreover, for each value in $TIV_{new}$ there are two entries in each dLUT (except “dLUT $\Delta - 1$”), that is why *indirectAddress* signal is the higher $n - lg\Delta$ bits of $n$-bit input $\alpha(\alpha[n - 1 : lg\Delta])$.

<figure><img src="image_10.png" /><figcaption>Fig. 9. AddressGenerator module.</figcaption></figure>
Signal named *select* is a thermometer vector, which consists of Δ consecutive ones, each bit representing whether the corresponding *dval* will be summed (by SignedSummation module). Consider (4), which shows how we compute f(10) using the differences in the dLUTs. In the case of f(10), signal *select* is 1100, i.e., *select*[3] = 1 (the MSB) and *select*[2] = 1. Therefore, the outputs of dLUT3 and dLUT2 (find the terms in (4) in Fig. 7) are summed. Positions of signal *select*'s bits match the dLUT locations in Fig. 7, Fig. 8, and the related figures to follow.

Now, consider f(13), which is given by (5). Its *select* vector is 0001 because only dLUT0's output is summed with TIV<sub>new</sub>. If we were computing f(15), *select* would be 0111. Note that unused dLUT entries always have a *select* bit of 0. On the other hand, f(9) and f(8) would have *select* of 1110 and 1111, respectively. If the α of f(α) we are computing corresponds to an even row of dLUTs (i.e., row 0, 2, 4, etc.), then *select* is a contiguous block of 1's starting with the LSB. On the other hand, If the α corresponds to an odd row (i.e., row 1, 3, 5, etc.), then *select* is a contiguous block of 1's starting with the MSB.

Let us now look at how we generate *select* from α. Fig. 9 shows how. Let us apply Fig. 9 to f(10), where Δ is 4, and hence *lgΔ* is 2. 10 in base 10 is 1010 in binary and α[lgΔ - 1 : 0], lower lgΔ bits of α is binary 10(= 2). We start with Δ1'b1, i.e., Δ 1's in Verilog notation. That is, binary 1111. Left-shift it by 2 positions to get Δ = 4 bits, and we get 1100. Bitwise XOR that with α[lgΔ] (bit 2 of α), which is 0, and we get 1100. That is indeed the *select* signal.

Let us do the same for f(13). 13 (α) in base 10 is 1101 in binary. Left-shift 1111 by binary 01 (α[lgΔ - 1 : 0]) positions, and we get 1110. Bitwise XOR that α[lgΔ] = 1, and all bits flip, resulting in 0001, which is the correct value.

DataSelection module shown in Fig. 10 is quite straight forward. It is practically a vector-multiplication unit or some sort of multiplexer as expressed in (8). It multiplies every *dval* (i.e., dLUT output) with the corresponding *select* bit, resulting in signal *dsel*. This can be done with an AND gate provided that each *select* bit duplicated *d* times (i.e., *dselect[i]*), which happens to be the bit width of *dval* as well as *dsel*.

$$dselect[i] = \begin{cases} dval[i], & \text{if } select[i] = 1 \\ 0, & \text{otherwise} \end{cases} \quad \text{where } i < \Delta = 2^{s-1} \quad (8)$$

After masking out some *dval*'s and obtaining *dsel*'s, we need to sum *dsel*'s and the corresponding entry from TIV<sub>new</sub>. That is best done with a Column Compression Tree (CCT). In our work, the summation is done by SignedSummation shown in Fig. 11, which is based on the CCT generator proposed in [13] (called RoCoCo). RoCoCo handles only the summation of unsigned numbers, which is why the following conversion had to be done.

Consider the summation when *mval* is 16 bits, hence *a* and 15 *x*'s in (9). The *dsel*'s are 4 bits each, and there are 4 dLUTs. That is why we have four 4-bit numbers in (9). These numbers are 2's complement, which is why their MSBs are negative. The underbar *a*, *b*, *c*, *d*, *e* show that these numbers are negative. In other words, *a*, *b*, *c*, *d*, *e* can be 0 or 1, and *a*, *b*, *c*, *d*, *e* are either -0=0 or -1. In summary, we need to perform the summation in (9), where most bit positions
<figure><img src="image_11.png" /><figcaption>Fig. 10. DataSelection module.</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>Fig. 11. SignedSummation module.</figcaption></figure>
have 0 and 1, while two bit positions have 0, 1, and -1. We can apply unsigned summation techniques only when -1 can be present in the highest bit position, that is, bit position 15 (the bit position a). For this, we may sign-extend the 4-bit 2's complement numbers in (9) to 16 bits. Then, the result will also be 16-bit 2's complement, that is, a binary number with negative bit 15. We also have to make sure that the summation does not overflow. If it may, we need to sign-extend all numbers to 17 bits. However, in our case, the sum is also guaranteed to be 16-bit 2's complement.

$$ \underline{a}xxxxxx\underline{a}xxxxxx + \underline{b}xxx + \underline{c}xxx + \underline{d}xxx + \underline{e}xxx \quad (9) $$

$$ = \bar{a}xxxxxx\bar{a}xxxxxx + \underline{1000000000000000} + \bar{b}xxx + \underline{1000 + \bar{c}xxx + 1000 + \bar{d}xxx + 1000 + \bar{e}xxx + 1000} \quad (10) $$

$$ = \bar{a}xxxxxx\bar{a}xxxxxx + \bar{b}xxx + \bar{c}xxx + \bar{d}xxx + \bar{e}xxx + \underline{10111111111100000} \quad (11) $$

$$ = \bar{a}xxxxxx\bar{a}xxxxxx + \bar{b}xxx + \bar{c}xxx + \bar{d}xxx + \underline{1011111111110\bar{e}xxx} \quad (12) $$

$$ = \bar{a}xxxxxx\bar{a}xxxxxx + \bar{b}xxx + \bar{c}xxx + \bar{d}xxx + \underline{0111111111110\bar{e}xxx} \quad (13) $$

Having said all that, a smarter (more area and speed efficient) approach, is to use the identity in Table 1, and hence, to replace the $\underline{a}$ in (9) with $\bar{a}+\underline{1}$, where $\bar{a}$ is an unsigned 0 or 1 and is the NOT of a. Through this we get (10), which is a summation of variable unsigned numbers and some 2's complement constant numbers with still varying positions for the negative bits. However, these 2's complement constants can be summed offline to obtain a single 16-bit 2's complement number, hence (11). Then, we happen to have negative bits only in bit position 15. Equation (12) does a little optimization by adding the rightmost two numbers in (10) offline and hence combining them into a single number ($\underline{1011111111110\bar{e}xxx}$). Equation (13), on the other hand, eliminates bit position 16 of that combined number as the sum is guaranteed to be 16 bits (bit positions 0 through 15).

<table><caption>**Table 1.** Proof of $\underline{a} = \bar{a} + \underline{1}$.</caption><thead><tr><th>a</th><th>ā + 1</th></tr></thead><tbody><tr><td>0</td><td>ā + 1 = 1 + (-1) = 0</td></tr><tr><td>1</td><td>ā + 1 = 0 + (-1) = -1</td></tr></tbody></table>
The SignedSummation module in Fig. 8 is detailed in Fig. 11. It is composed of CCT and a Final Adder. The little cones in Fig. 11 expose bits of signals and recombine them. The bit-level manipulation before the CCT is a pictorial representation of equations (9) through (13). Note that the number of zeros to the left of $\bar{e}$ does not have to be one as in (13) in the general case. It is $lg\Delta - 1$ zeros (assuming $\Delta$ is a power of 2) as in Fig. 11 (look under *dSEL*[0]). Also, note that the CCT in Fig. 11 not only sums $TIV_{new}$ and dLUT outputs but also the outputs of TOs (shown in Fig. 2). There is no reason why we should do two separate summations.

## 3.2 FR-dLUT-VL Microarchitecture

FR-dLUT-VL has a similar microarchitecture to FR-dLUT. They both have $\Delta$ dLUTs and a $TIV_{new}$. The contents of $TIV_{new}$ are the same for both architectures. The difference between FR-dLUT-VL and FR-dLUT is the dLUT contents (compare Fig. 12 with Fig. 7). FR-dLUT-VL's dLUTs store the compressed versions of the differences stored in the FR-dLUT's dLUT. Due to the nature variable length coding, dLUTs of FR-dLUT-VL are wider than those of FR-dLUT. However, unused bits of those dLUTs' entries are don't care, and logic synthesis can optimize them out.

Fig. 12 shows the entries of the FR-dLUT-VL with 4 dLUTs for a function with $w_i = 16$ and $w_o = 16$.

<figure><img src="image_13.png" /><figcaption>Fig. 12. LUT contents of FR-dLUT-VL implementation for $\Delta = 4$.</figcaption></figure>

It is obvious that one can apply any compression method on dLUT contents. In this work, Huffman coding [12] is chosen for this purpose. For each dLUT, the frequency of the values is calculated. According to the frequency, each value is assigned a Huffman code. Frequency for each value in a dLUT is calculated separately from the other dLUTs. Additionally, due to the encoded values stored in the dLUTs, after each value is read from its respective dLUT, it needs to go through a Decoder module before it can be used in SignedSummation module.

In FR-dLUT-VL microarchitecture, instead of encoding the whole value, a portion of the entry is taken and then the encoding method is applied. For example, if three MSBs are selected, each entry's three MSBs are encoded. To determine the separation point in a dLUT, starting from the two MSBs of an
entry to all bits of entry, each possible combination is tested. For each combination, dLUT sizes and the decoder sizes are calculated. Calculation of dLUT sizes are done by adding encoded values' bit width and the bit width of the remaining bits that are not used in the encoding. Among these combinations, the one with the lower bit count is selected for implementation. Pseudocode of separation point selection is shown in Algorithm 1.

<caption>**Algorithm 1** MSB calculation of FR-dLUT-VL design.</caption>

**Input:** $w_i$: input bit width, $w_o$: output bit width
1: $LUTsizeMin \leftarrow 2^{w_i} * w_o$
2: $MSBcountMin \leftarrow 0$
3: **for** $MSBcountMin \leftarrow 2$ **to** $w_o$ **do**
4: &nbsp;&nbsp;&nbsp;&nbsp;compute encoded representation of every entry
5: &nbsp;&nbsp;&nbsp;&nbsp;$LUTsize \leftarrow 0$
6: &nbsp;&nbsp;&nbsp;&nbsp;$DecoderSize \leftarrow 0$
7: &nbsp;&nbsp;&nbsp;&nbsp;**for all** unique encoded value **do**
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$LUTsize \leftarrow LUTsize + (encoded value bit length) * (frequency of the value)$
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$DecoderSize \leftarrow DecoderSize + (encoded value bit length)$
10: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
11: $LUTsize \leftarrow LUTsize + 2^{w_i} * (w_o - MSBcount) + DecoderSize$
12: **if** $LUTsize < LUTsizeMin$ **then**
13: &nbsp;&nbsp;&nbsp;&nbsp;$LUTsizeMin \leftarrow LUTsize$
14: &nbsp;&nbsp;&nbsp;&nbsp;$MSBcountMin \leftarrow MSBcount$
15: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
16: **end for**

-encoded part of the accessed dLUT entry is sent to the Decoder module. After the encoded value is decoded, output bits and the non-encoded segment of the stored value in dLUT is concatenated and sent to the DataSelection module. Top module of FR-dLUT-VL method is shown in Fig. 13. As shown in Fig. 13, after the values are read from the dLUT (dvals), part of dval goes through the Decoder, then the decoded value merges with the rest of the dval and becomes the decoded difference value (ddval) which is the input for the DataSelection module.

## 3.3 SR-dLUT Microarchitecture

The main idea in SR-dLUT is to eliminate the $TIV_{new}$ in FR-dLUT and instead add dLUT entries on top of the previous function value. This can be done when not only the function f is smooth but also the input (x in f(x)) is smooth. Smoothness of x means the consecutive values of x are close to each other. This is, for example, the case when x comes from a sensor for example in a closed-loop control application, or when x is a timer tick or a smooth function of time. Elimination of $TIV_{new}$ makes SR-dLUT quite competitive in terms of area.
<figure><img src="image_14.png" /><figcaption>**Fig. 13.** Top module of FR-dLUT-VL microarchitecture.</figcaption></figure>

Fig. 15 shows the top level of the proposed SR-dLUT microarchitecture, which consists of AddressGenerator (Fig. 16), dLUTs, DataSelection (Fig. 19), and SignedSummation (Fig. 20).

Note that $\Delta$ of SR-dLUT is not the same as $\Delta$ of FR-dLUT. For FR-dLUT, $\Delta$ is a purely internal parameter stating the number of dLUTs, and hence, it has nothing to do with how it functions. For SR-dLUT, $\Delta$ is not only an internal parameter but also shows how smooth $x$ is, that is the maximum amount of change between consecutive $x$ values.

AddressGenerator module calculates the required addresses of dLUTs for input $\alpha$. One register stores the previous input value. The previous input is subtracted from the current input to find *magnitude* and *diff_sign* that determines whether the shift direction may be forward or backward. The *thermo* vector is shifted in direction of *diff_sign* as the amount of the magnitude. (Fig. 18) shows the ThermoRegulator block that resolves the overflow issue due to the shift operation. The *thermo* vector is XOR'ed with the shifted *thermo* vector. Then, the output of the first XOR is shifted by 1 in a backward direction, and the resulting signal is named *tmp0*. The specific bit portion of *tmp0* is XOR'ed to determine *select* signals. Similarly, the specific bit portion of *thermo* is ORed to determine
$dLut\_Out\_En$ which is used in control mechanisms of both ThermoRegulator and DataSelection modules. (Fig. 17) shows the AddressSelection module that uses a conditional control mechanism by using $tmp_\alpha$ signals as input $tmpO$ signals as select to determine addresses of dLUTs.

Note that SR-dLUT has access to much more than $\pm\Delta$ values, since each TIV value is coupled with multiple TO tables in MP. In Fig. 2, we can see that the same TIV value is used for $2^{(\Delta x_1+\Delta x_2+\Delta x_3)}$ in the case of $m = 3$. While we can access $2 * \Delta$ different entries in dLUTs, we can compute the function for $2 * \Delta * 2^{(\Delta x_1+\Delta x_2+\Delta x_3)}$ different x values. For the reasons explained above, $\Delta = 1$ is a meaningful case for SR-dLUT unlike FR-dLUT.

There are $\Delta$ parallel dLUTs that store difference values in SR-dLUT microarchitecture. Fig.14 shows an example of SR-dLUT with 4 dLUTs, which implements a function $f$ with $w_i = 16$. SR-dLUTs store subsequent differences values in-order and each dLUT stores same amount of data with a length of $2^{(n-lg\Delta)}$. Since the SR-dLUT method does not require a $TIV_{new}$ table, we can no longer have half entries for one of the dLUTs like in Fig.7. In other words, there is no unused memory location in dLUTs.

<figure><img src="image_15.png" /><figcaption>Fig. 14. LUT contents of SR-dLUT implementation for $w_i = 16$ and $\Delta = 4$.</figcaption></figure>

DataSelection module of SR-dLUT is similar to DataSelection module of FR-dLUT. The difference from FR-dLUT is that there is an extra control mechanism that determines which signal is multiplied by the select signal. The multiplication is implemented using an AND gate. The results of multiplication are $dsel$ signals that are connected to the SignedSummation module.

SignedSummation module of SR-dLUT is different from the FR-dLUT's SignedSummation. Since it needs to hold the previous value of the TIV output in a register, and it could not use a single CCT to add dLUT outputs and the TOs output from MP method. Therefore, there is an additional CCT. The first CCT uses the current values of $dsel$ and the previous outputs of the CCT. It outputs two values, which are the values generated just before going through the second CCT. The outputs of the first CCT are saved in registers for the next iteration, at the same time used in the second CCT as inputs together with the TOs outputs. As a conclusion, a final adder sums outputs of the second CCT.

One of the differences between SR-dLUT and the earlier version of this work [10] is the form of thermo vector. While the size of thermo vector is $3\Delta$-bit
SR-dLUT, the size of the **thermo** vector is $\Delta$-bit in [10]. The advantage of using this new form of **thermo** vector is to find the dLUT addresses easier. In other words, the AdressSelection module in our proposed SR-dLUT is simpler than in [10]. Additionally, we used CCTs for the summation of *dsels* in our proposed SR-dLUT. On the other hand, conventional addition units are used in [10]. Our proposed summation module has an advantage in terms of area when $\Delta$ increases because the addition unit in [10] is proportional to $\Delta$.

<figure><img src="image_16.png" /><figcaption>Fig. 15. Top module of SR-dLUT microarchitecture.</figcaption></figure>

## 3.4 SR-dLUT-VL Microarchitecture

Difference between SR-dLUT-VL and SR-dLUT is similar to the difference between FR-dLUT and FR-dLUT-VL, where values inside dLUTs are partially compressed according to the algorithm shown in Algorithm 1. As in FR-dLUT-VL, partial output of dLUTs' (*dval*) in SR-dLUT-VL first go through a decoder, then output of the decoder is concatenated with the remaining part of the *dval*. The concatenated value represents the actual *dval* from the SR-dLUT microarchitecture, which can now be used in the SignedSummation module.

## 4 Results

In this section, we compare our proposed microarchitectures with the state-of-the-art (T-TIV methods) as well as ConvLUT (i.e., RegularTIV). For each of the 8 TIV construction methods listed above, we wrote a code generator in Perl that generates Verilog RTL for a complete MP design. The code generators take
<figure><img src="image_17.png" /><figcaption>Fig. 16. SR-dLUT AddressGenerator module.</figcaption></figure>

<figure><img src="image_18.png" /><figcaption>Fig. 17. SR-dLUT AddressSelection module.</figcaption></figure>

<figure><img src="image_19.png" /><figcaption>Fig. 18. SR-dLUT ThermometerRegulator module.</figcaption></figure>
<figure><img src="image_20.png" /><figcaption>Fig. 19. SR-dLUT DataSelection module.</figcaption></figure>

in $w_i$, $w_o$, and $m$ (number of MP's TOs) as well as parameters related to the specific TIV construction method such as $\Delta$ for our methods.

Generation of the original TIV (RegularTIV) and TOs, i.e., the MP method [6], is done using a tool [14], which is also part of FloPoCo [15]. This tool (written in Java) generates RTL code in VHDL targeting various mathematical functions and parameters $W_i$, $W_o$, and $m$. Our Perl script runs the Java MP generator with $W_i$, $W_o$, and $m$, where $W_o$ shows the precision of the output rather than the bit width of any of the embedded tables. MP generator decides what sizes RegularTIV and TOs have to be for the given set of $w_i$, $w_o$, and $m$. This information is embedded into Table 2 of [6] which, for example, shows that $w_i = 10$ and $w_o = 17$ for the RegularTIV part, when the function is sine and $w_i = 16$, $w_o = 16$, and $m = 1$. Our Perl takes in $w_i$, $w_o$, and $m$, runs the Java MP generator with the input parameters. Then, it parses the VHDL produced by the MP generator, extracts $w_i$ and $w_o$, and runs the TIV generator. Then, our script produces Verilog, in which we have an MP design equivalent to the input VHDL but the RegularTIV is replaced with our TIV of choice (one of FR-dLUT, FR-dLUT-VL, SR-dLUT, SR-dLUT-VL, 2T-TIV, 2T-TIV-IMP, 3T-TIV). Our script automates verification as well as design. We exhaustively test all function values by comparing the output of the VHDL and Verilog designs.

We generated the above listed 8 designs for $\sin(x)$ ($x = [0, \pi/2]$) and $2^x$ ($x = [0, 1]$) functions with $w_i = 16$, $w_o = 16$ and $w_i = 24$, $w_o = 24$, both with various $m$ for each resolution. We then synthesized them on to a Xilinx Artix-7 FPGA (more specifically XC7A100T-3CSG324). FR-dLUT and FR-dLUT-VL were synthesized for four $\Delta$ values (2, 4, 8, and 16) where SR-dLUT and SR-dLUT-VL synthesized for an additional $\Delta$ value, where $\Delta = 1$. For 24-bit res-
<figure><img src="image_21.png" /><figcaption>Fig. 20. SR-dLUT SignedSummation module.</figcaption></figure>

olution, *m* values of 1, 2, 3, and 4 were implemented. For 16-bit resolution, *m* values (number of TOs) of 1, 2, and 3 were implemented, since the Java tool at [14] gave an error and did not produce any VHDL. Note that all LUTs (RegularTIV, dLUTs, TIV<sub>new</sub>, TIV<sub>diff</sub>, TIV<sub>diff1</sub>, and TIV<sub>diff2</sub>) are logic-synthesized instead of instantiating memory blocks. This yields designs with smaller area for all methods including the original TIVs. The synthesis option of Area with High effort is selected for better area minimization in Xilinx ISE.

Tables 2, 3, and 4 show the Area, Time, and Area-Time Product (ATP) results we obtained for sine and exponent function (2<sup>x</sup>) for 16-bit resolutions, respectively. Similarly, Tables 5, 6, and 7 show the Area, Time, and ATP results we obtained for 24-bit versions of sine and exponent function. Area results are in terms of FPGA LUTs. Time (also called timing) is the latency (i.e., critical path) of the circuit measured in terms of nanoseconds (ns). ATP simply shows the product of Area (#LUTs) and Time (ns) columns divided by 10<sup>3</sup>. ATP of a design shows the tradeoff between area and timing, also ATP is usually correlated with power consumption. The best Area, Time, and ATP results are shaded for each *m* value in the tables.

In Table 2 through 7, all designs (60 for 16-bit and 80 for 24-bit) are equiv-
alent at MP level. That is, they all produce the same function with the same
resolution. However, the TIV microarchitectures are equivalent within the same
*m*. Therefore, it is best to compare the 8 microarchitectures separately for every
<table><caption>Table 2. Area Results for 16-bit Resolution</caption><thead><tr><th rowspan="2">Function</th><th rowspan="2">m</th><th rowspan="2">RegularTIV</th><th rowspan="2">2T-TIV</th><th rowspan="2">2T-TIV-IMP</th><th rowspan="2">3T-TIV</th><th colspan="4">Full Random</th><th colspan="4">Semi Random</th></tr><tr><th>Δ</th><th>FR-dLUT</th><th>FR-dLUT-VL</th><th>Δ</th><th>SR-dLUT</th><th>SR-dLUT-VL</th></tr></thead><tbody><tr><td rowspan="12">Sine<br>16-bit</td><td rowspan="4">1</td><td rowspan="4">346</td><td rowspan="4">343</td><td rowspan="4">346</td><td rowspan="4">357</td><td>2</td><td>249</td><td>277</td><td>1</td><td>245</td><td>268</td></tr><tr><td>4</td><td>249</td><td>271</td><td>2</td><td>285</td><td>306</td></tr><tr><td>8</td><td>313</td><td>349</td><td>4</td><td>368</td><td>380</td></tr><tr><td>16</td><td>435</td><td>454</td><td>8</td><td>521</td><td>547</td></tr><tr><td rowspan="4">2</td><td rowspan="4">188</td><td rowspan="4">192</td><td rowspan="4">187</td><td rowspan="4">212</td><td>2</td><td>208</td><td>215</td><td>1</td><td>253</td><td>257</td></tr><tr><td>4</td><td>245</td><td>245</td><td>2</td><td>287</td><td>293</td></tr><tr><td>8</td><td>320</td><td>320</td><td>4</td><td>362</td><td>364</td></tr><tr><td>16</td><td>451</td><td>448</td><td>8</td><td>606</td><td>610</td></tr><tr><td rowspan="4">3</td><td rowspan="4">147</td><td rowspan="4">157</td><td rowspan="4">159</td><td rowspan="4">185</td><td>2</td><td>181</td><td>187</td><td>1</td><td>205</td><td>210</td></tr><tr><td>4</td><td>220</td><td>222</td><td>2</td><td>242</td><td>244</td></tr><tr><td>8</td><td>277</td><td>277</td><td>4</td><td>317</td><td>325</td></tr><tr><td>16</td><td>402</td><td>406</td><td>8</td><td>550</td><td>555</td></tr><tr><td rowspan="12">2<sup>x</sup><br>16-bit</td><td rowspan="4">1</td><td rowspan="4">341</td><td rowspan="4">334</td><td rowspan="4">N/A</td><td rowspan="4">365</td><td>2</td><td>255</td><td>262</td><td>1</td><td>251</td><td>258</td></tr><tr><td>4</td><td>265</td><td>283</td><td>2</td><td>293</td><td>306</td></tr><tr><td>8</td><td>323</td><td>320</td><td>4</td><td>375</td><td>382</td></tr><tr><td>16</td><td>438</td><td>438</td><td>8</td><td>521</td><td>551</td></tr><tr><td rowspan="4">2</td><td rowspan="4">196</td><td rowspan="4">199</td><td rowspan="4">196</td><td rowspan="4">230</td><td>2</td><td>215</td><td>214</td><td>1</td><td>259</td><td>262</td></tr><tr><td>4</td><td>247</td><td>242</td><td>2</td><td>290</td><td>295</td></tr><tr><td>8</td><td>321</td><td>320</td><td>4</td><td>368</td><td>372</td></tr><tr><td>16</td><td>443</td><td>442</td><td>8</td><td>591</td><td>588</td></tr><tr><td rowspan="4">3</td><td rowspan="4">156</td><td rowspan="4">165</td><td rowspan="4">156</td><td rowspan="4">200</td><td>2</td><td>191</td><td>188</td><td>1</td><td>217</td><td>221</td></tr><tr><td>4</td><td>232</td><td>231</td><td>2</td><td>252</td><td>257</td></tr><tr><td>8</td><td>292</td><td>288</td><td>4</td><td>331</td><td>330</td></tr><tr><td>16</td><td>420</td><td>416</td><td>8</td><td>553</td><td>552</td></tr></tbody></table>

<table><caption>Table 3. Timing Results for 16-bit Resolution</caption><thead><tr><th rowspan="2">Function</th><th rowspan="2">m</th><th rowspan="2">RegularTIV</th><th rowspan="2">2T-TIV</th><th rowspan="2">2T-TIV-IMP</th><th rowspan="2">3T-TIV</th><th colspan="4">Full Random</th><th colspan="4">Semi Random</th></tr><tr><th>Δ</th><th>FR-dLUT</th><th>FR-dLUT-VL</th><th>Δ</th><th>SR-dLUT</th><th>SR-dLUT-VL</th></tr></thead><tbody><tr><td rowspan="12">Sine<br>16-bit</td><td rowspan="4">1</td><td rowspan="4">6.69</td><td rowspan="4">8.22</td><td rowspan="4">6.67</td><td rowspan="4">9.66</td><td>2</td><td>8.46</td><td>8.16</td><td>1</td><td>9.94</td><td>11.30</td></tr><tr><td>4</td><td>9.09</td><td>8.85</td><td>2</td><td>10.62</td><td>15.90</td></tr><tr><td>8</td><td>10.58</td><td>10.02</td><td>4</td><td>12.77</td><td>12.69</td></tr><tr><td>16</td><td>10.97</td><td>11.25</td><td>8</td><td>14.28</td><td>14.75</td></tr><tr><td rowspan="4">2</td><td rowspan="4">7.34</td><td rowspan="4">9.02</td><td rowspan="4">7.68</td><td rowspan="4">9.47</td><td>2</td><td>7.82</td><td>8.09</td><td>1</td><td>10.32</td><td>10.04</td></tr><tr><td>4</td><td>8.35</td><td>7.94</td><td>2</td><td>11.75</td><td>11.27</td></tr><tr><td>8</td><td>9.16</td><td>9.16</td><td>4</td><td>12.38</td><td>12.71</td></tr><tr><td>16</td><td>10.98</td><td>12.83</td><td>8</td><td>14.70</td><td>15.07</td></tr><tr><td rowspan="4">3</td><td rowspan="4">7.39</td><td rowspan="4">8.62</td><td rowspan="4">7.73</td><td rowspan="4">9.15</td><td>2</td><td>7.73</td><td>8.09</td><td>1</td><td>10.95</td><td>10.40</td></tr><tr><td>4</td><td>7.77</td><td>7.60</td><td>2</td><td>11.76</td><td>12.07</td></tr><tr><td>8</td><td>9.70</td><td>10.50</td><td>4</td><td>12.69</td><td>12.35</td></tr><tr><td>16</td><td>10.40</td><td>13.49</td><td>8</td><td>15.02</td><td>14.73</td></tr><tr><td rowspan="12">2<sup>x</sup><br>16-bit</td><td rowspan="4">1</td><td rowspan="4">6.69</td><td rowspan="4">8.31</td><td rowspan="4">N/A</td><td rowspan="4">9.81</td><td>2</td><td>8.32</td><td>7.88</td><td>1</td><td>10.19</td><td>11.11</td></tr><tr><td>4</td><td>9.08</td><td>9.08</td><td>2</td><td>10.94</td><td>11.42</td></tr><tr><td>8</td><td>9.38</td><td>9.45</td><td>4</td><td>12.57</td><td>11.42</td></tr><tr><td>16</td><td>10.78</td><td>11.38</td><td>8</td><td>14.97</td><td>15.20</td></tr><tr><td rowspan="4">2</td><td rowspan="4">7.77</td><td rowspan="4">9.14</td><td rowspan="4">7.65</td><td rowspan="4">9.27</td><td>2</td><td>8.14</td><td>8.14</td><td>1</td><td>9.45</td><td>10.07</td></tr><tr><td>4</td><td>8.70</td><td>8.66</td><td>2</td><td>12.34</td><td>11.81</td></tr><tr><td>8</td><td>10.16</td><td>12.92</td><td>4</td><td>12.96</td><td>13.08</td></tr><tr><td>16</td><td>10.97</td><td>16.13</td><td>8</td><td>15.72</td><td>15.38</td></tr><tr><td rowspan="4">3</td><td rowspan="4">8.16</td><td rowspan="4">8.69</td><td rowspan="4">7.81</td><td rowspan="4">8.44</td><td>2</td><td>7.60</td><td>7.50</td><td>1</td><td>10.45</td><td>10.50</td></tr><tr><td>4</td><td>7.57</td><td>7.95</td><td>2</td><td>12.55</td><td>12.70</td></tr><tr><td>8</td><td>9.90</td><td>12.36</td><td>4</td><td>13.61</td><td>12.43</td></tr><tr><td>16</td><td>11.14</td><td>13.61</td><td>8</td><td>15.62</td><td>15.90</td></tr></tbody></table>
<table><caption>**Table 4.** ATP Results for 16-bit Resolution</caption><thead><tr><th rowspan="2">Function</th><th rowspan="2">m</th><th rowspan="2">RegularTIV</th><th rowspan="2">2T-TIV</th><th rowspan="2">2T-TIV-IMP</th><th rowspan="2">3T-TIV</th><th colspan="2">Full Random</th><th colspan="2">Semi Random</th></tr><tr><th>Δ</th><th>FR-dLUT</th><th>FR-dLUT-VL</th><th>Δ</th><th>SR-dLUT</th><th>SR-dLUT-VL</th></tr></thead><tbody><tr><td rowspan="12">Sine<br>16-bit</td><td rowspan="3">1</td><td rowspan="3">2.31</td><td rowspan="3">2.82</td><td rowspan="3">2.31</td><td rowspan="3">3.45</td><td>2</td><td>2.11</td><td>2.26</td><td>1</td><td>2.44</td><td>3.03</td></tr><tr><td>4</td><td>2.26</td><td>2.40</td><td>2</td><td>3.03</td><td>4.86</td></tr><tr><td>8</td><td>3.31</td><td>3.50</td><td>4</td><td>4.70</td><td>4.82</td></tr><tr><td rowspan="3">2</td><td rowspan="3">1.38</td><td rowspan="3">1.73</td><td rowspan="3">1.44</td><td rowspan="3">2.01</td><td>16</td><td>4.77</td><td>5.11</td><td>8</td><td>7.44</td><td>8.07</td></tr><tr><td>2</td><td>1.63</td><td>1.74</td><td>1</td><td>2.61</td><td>2.58</td></tr><tr><td>4</td><td>2.05</td><td>1.95</td><td>2</td><td>3.37</td><td>3.30</td></tr><tr><td rowspan="3">3</td><td rowspan="3">1.09</td><td rowspan="3">1.35</td><td rowspan="3">1.23</td><td rowspan="3">1.69</td><td>8</td><td>2.93</td><td>2.93</td><td>4</td><td>4.48</td><td>4.63</td></tr><tr><td>16</td><td>4.95</td><td>5.75</td><td>8</td><td>8.91</td><td>9.19</td></tr><tr><td>2</td><td>1.40</td><td>1.51</td><td>1</td><td>2.24</td><td>2.18</td></tr><tr><td rowspan="3">2<sup>x</sup><br>16-bit</td><td rowspan="3">1</td><td rowspan="3">2.28</td><td rowspan="3">2.78</td><td rowspan="3">N/A</td><td rowspan="3">3.58</td><td>4</td><td>2.41</td><td>2.57</td><td>2</td><td>3.21</td><td>3.50</td></tr><tr><td>8</td><td>3.03</td><td>3.02</td><td>4</td><td>4.71</td><td>4.36</td></tr><tr><td>16</td><td>4.72</td><td>4.98</td><td>8</td><td>7.80</td><td>8.38</td></tr><tr><td rowspan="3">2</td><td rowspan="3">1.52</td><td rowspan="3">1.82</td><td rowspan="3">1.50</td><td rowspan="3">2.13</td><td>2</td><td>1.75</td><td>1.74</td><td>1</td><td>2.45</td><td>2.64</td></tr><tr><td>4</td><td>2.15</td><td>2.10</td><td>2</td><td>3.58</td><td>3.48</td></tr><tr><td>8</td><td>3.26</td><td>4.13</td><td>4</td><td>4.77</td><td>4.87</td></tr><tr><td rowspan="3">3</td><td rowspan="3">1.27</td><td rowspan="3">1.43</td><td rowspan="3">1.22</td><td rowspan="3">1.69</td><td>16</td><td>4.86</td><td>7.13</td><td>8</td><td>9.29</td><td>9.04</td></tr><tr><td>2</td><td>1.45</td><td>1.41</td><td>1</td><td>2.27</td><td>2.32</td></tr><tr><td>4</td><td>1.76</td><td>1.84</td><td>2</td><td>3.16</td><td>3.26</td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td>8</td><td>2.89</td><td>3.56</td><td>4</td><td>4.51</td><td>4.10</td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td>16</td><td>4.68</td><td>5.66</td><td>8</td><td>8.64</td><td>8.78</td></tr></tbody></table>

m. However, out of curiosity we compare all solutions for each of the 4 cases (16-bit sine, 16-bit $2^x$, 24-bit sine, 24-bit $2^x$).

Tables 2, 3, and 4 implement 16-bit sine and $2^x$ 60 different ways each, where 57 comes from (RegularTIV + 2T-TIV + 2T-TIV-IMP + 3T-TIV + 4×FR-dLUT + 4×FR-dLUT-VL + 4×SR-dLUT + 4×SR-dLUT-VL) × (3 m values). In the above tables, one result is missing for 2T-TIV-IMP because $TIV_{new}$ and $TIV_{diff}$ in the corresponding 2T-TIV have equal bit width, hence no optimization is possible.

Tables 5, 6, and 7 implement 24-bit sine and $2^x$ for an additional 20 different ways due to the $m = 4$ case. The Time and ATP of RegularTIV for $m = 1$ are missing for both functions and for 2T-TIV-IMP for $2^x$ function in Table 6 and 7 because the synthesis tool was not able to complete routing. The tool reported the Area but did not report the timing (Time).

Looking at Tables 2, 3, and 4, we can see that, except for 5 cases (2 in Area, 1 in Timing, and 2 in ATP), the proposed method is surpassed by the RegularTIV and the T-TIV variants for 16-bit implementations. Though in a few cases, our proposed methods offer up to 29%, 4%, 9% improvement in area, timing, ATP, respectively over the state-of-the-art and RegularTIV. The area improvements come from SR-dLUT. Time and ATP improvements come from FR-dLUT and FR-dLUT-VL.

Looking at Tables 5, 6, and 7 show the results for 24-bit implementations of sine and $2^x$. In area, SR-dLUT (and a few times SR-dLUT-VL) gives the best results. In timing, FR-dLUT gives the best result in 3 out of the 8 cases (2 different designs and 4 different $m$s for each design). FR-dLUT-VL, on the other
<table><caption>Table 5. Area Results for 24-bit Resolution</caption><thead><tr><th rowspan="2">Function</th><th rowspan="2">m</th><th rowspan="2">RegularTIV</th><th rowspan="2">2T-TIV</th><th rowspan="2">2T-TIV-IMP</th><th rowspan="2">3T-TIV</th><th colspan="3">Full Random</th><th colspan="3">Semi Random</th></tr><tr><th>Δ</th><th>FR-dLUT</th><th>FR-dLUT-VL</th><th>Δ</th><th>SR-dLUT</th><th>SR-dLUT-VL</th></tr></thead><tbody><tr><td rowspan="16">Sine<br>24-bit</td><td rowspan="4">1</td><td rowspan="4">54045</td><td rowspan="4">36068</td><td rowspan="4">51145</td><td rowspan="4">30472</td><td>2</td><td>30907</td><td>30801</td><td>1</td><td>28175</td><td>29776</td></tr><tr><td>4</td><td>29402</td><td>29643</td><td>2</td><td>28132</td><td>29131</td></tr><tr><td>8</td><td>28755</td><td>29525</td><td>4</td><td>28088</td><td>28240</td></tr><tr><td>16</td><td>28461</td><td>28942</td><td>8</td><td>28502</td><td>28702</td></tr><tr><td rowspan="4">2</td><td rowspan="4">4922</td><td rowspan="4">4064</td><td rowspan="4">4687</td><td rowspan="4">3817</td><td>2</td><td>3468</td><td>3579</td><td>1</td><td>2923</td><td>2956</td></tr><tr><td>4</td><td>3291</td><td>3378</td><td>2</td><td>2968</td><td>3024</td></tr><tr><td>8</td><td>3172</td><td>3208</td><td>4</td><td>3235</td><td>3317</td></tr><tr><td>16</td><td>3575</td><td>3628</td><td>8</td><td>3589</td><td>3652</td></tr><tr><td rowspan="4">3</td><td rowspan="4">3015</td><td rowspan="4">2673</td><td rowspan="4">2890</td><td rowspan="4">2572</td><td>2</td><td>2468</td><td>2490</td><td>1</td><td>2248</td><td>2293</td></tr><tr><td>4</td><td>2379</td><td>2405</td><td>2</td><td>2376</td><td>2424</td></tr><tr><td>8</td><td>2525</td><td>2545</td><td>4</td><td>2528</td><td>2570</td></tr><tr><td>16</td><td>2797</td><td>2821</td><td>8</td><td>2901</td><td>2977</td></tr><tr><td rowspan="4">4</td><td rowspan="4">2583</td><td rowspan="4">2225</td><td rowspan="4">2500</td><td rowspan="4">2156</td><td>2</td><td>2083</td><td>2103</td><td>1</td><td>1849</td><td>1871</td></tr><tr><td>4</td><td>1934</td><td>1965</td><td>2</td><td>1939</td><td>1993</td></tr><tr><td>8</td><td>2073</td><td>2097</td><td>4</td><td>2099</td><td>2135</td></tr><tr><td>16</td><td>2345</td><td>2993</td><td>8</td><td>2466</td><td>2538</td></tr><tr><td rowspan="16">2<sup>x</sup><br>24-bit</td><td rowspan="4">1</td><td rowspan="4">57511</td><td rowspan="4">57400</td><td rowspan="4">55059</td><td rowspan="4">48156</td><td>2</td><td>45849</td><td>45721</td><td>1</td><td>46925</td><td>46888</td></tr><tr><td>4</td><td>44484</td><td>44649</td><td>2</td><td>43715</td><td>45061</td></tr><tr><td>8</td><td>43910</td><td>43989</td><td>4</td><td>43371</td><td>43271</td></tr><tr><td>16</td><td>43765</td><td>44004</td><td>8</td><td>43655</td><td>43694</td></tr><tr><td rowspan="4">2</td><td rowspan="4">5845</td><td rowspan="4">4703</td><td rowspan="4">5658</td><td rowspan="4">4970</td><td>2</td><td>4594</td><td>4626</td><td>1</td><td>4126</td><td>4126</td></tr><tr><td>4</td><td>4283</td><td>4331</td><td>2</td><td>4157</td><td>4179</td></tr><tr><td>8</td><td>4234</td><td>4415</td><td>4</td><td>4427</td><td>4480</td></tr><tr><td>16</td><td>4545</td><td>4626</td><td>8</td><td>4798</td><td>4880</td></tr><tr><td rowspan="4">3</td><td rowspan="4">3512</td><td rowspan="4">3341</td><td rowspan="4">3434</td><td rowspan="4">3235</td><td>2</td><td>3071</td><td>3090</td><td>1</td><td>2862</td><td>2883</td></tr><tr><td>4</td><td>3004</td><td>3037</td><td>2</td><td>2989</td><td>3022</td></tr><tr><td>8</td><td>3117</td><td>3120</td><td>4</td><td>3154</td><td>3198</td></tr><tr><td>16</td><td>3267</td><td>3265</td><td>8</td><td>3526</td><td>3591</td></tr><tr><td rowspan="4">4</td><td rowspan="4">2844</td><td rowspan="4">2614</td><td rowspan="4">2804</td><td rowspan="4">2515</td><td>2</td><td>2390</td><td>2413</td><td>1</td><td>2206</td><td>2217</td></tr><tr><td>4</td><td>2325</td><td>2363</td><td>2</td><td>2281</td><td>2312</td></tr><tr><td>8</td><td>2441</td><td>2453</td><td>4</td><td>2452</td><td>2492</td></tr><tr><td>16</td><td>2345</td><td>2572</td><td>8</td><td>2822</td><td>2886</td></tr></tbody></table>
hand, is the best in 3 cases. 2T-TIV and RegularTIV each are the best in 1 case. In ATP, FR-dLUT, FR-dLUT-VL, and SR-dLUT are best in 4, 3, and 1 case, respectively. Our proposed methods offer up to 23%, 11%, 26% improvement in area, timing, ATP, respectively over the state-of-the-art and RegularTIV.

<table><caption>**Table 6.** Timing Results for 24-bit Resolution</caption><thead><tr><th rowspan="2">Function</th><th rowspan="2">m</th><th rowspan="2">RegularTIV</th><th rowspan="2">2T-TIV</th><th rowspan="2">2T-TIV-IMP</th><th rowspan="2">3T-TIV</th><th colspan="2">Full Random</th><th colspan="2">Semi Random</th></tr><tr><th>Δ</th><th>FR-dLUT</th><th>FR-dLUT-VL</th><th>Δ</th><th>SR-dLUT</th><th>SR-dLUT-VL</th></tr></thead><tbody><tr><td rowspan="12">Sine<br>24-bit</td><td rowspan="4">1</td><td rowspan="4">Can't Route</td><td rowspan="4">14.72</td><td rowspan="4">24.48</td><td rowspan="4">16.49</td><td>2</td><td>14.77</td><td>14.78</td><td>1</td><td>17.49</td><td>17.94</td></tr><tr><td>4</td><td>15.62</td><td>16.02</td><td>2</td><td>16.46</td><td>17.37</td></tr><tr><td>8</td><td>16.39</td><td>17.27</td><td>4</td><td>16.26</td><td>17.47</td></tr><tr><td>16</td><td>17.51</td><td>17.45</td><td>8</td><td>17.39</td><td>18.45</td></tr><tr><td rowspan="4">2</td><td rowspan="4">12.44</td><td rowspan="4">11.46</td><td rowspan="4">11.63</td><td rowspan="4">12.18</td><td>2</td><td>10.70</td><td>10.79</td><td>1</td><td>13.50</td><td>12.41</td></tr><tr><td>4</td><td>10.45</td><td>11.16</td><td>2</td><td>13.75</td><td>13.78</td></tr><tr><td>8</td><td>11.01</td><td>11.73</td><td>4</td><td>14.98</td><td>15.49</td></tr><tr><td>16</td><td>12.27</td><td>11.96</td><td>8</td><td>16.08</td><td>16.73</td></tr><tr><td rowspan="4">3</td><td rowspan="4">11.71</td><td rowspan="4">10.99</td><td rowspan="4">11.21</td><td rowspan="4">11.59</td><td>2</td><td>10.01</td><td>10.16</td><td>1</td><td>11.79</td><td>13.15</td></tr><tr><td>4</td><td>9.80</td><td>10.13</td><td>2</td><td>13.60</td><td>14.48</td></tr><tr><td>8</td><td>11.16</td><td>10.98</td><td>4</td><td>14.40</td><td>14.44</td></tr><tr><td>16</td><td>11.21</td><td>11.29</td><td>8</td><td>16.55</td><td>16.69</td></tr><tr><td rowspan="4">4</td><td rowspan="4">12.49</td><td rowspan="4">10.52</td><td rowspan="4">11.53</td><td rowspan="4">10.87</td><td>2</td><td>10.11</td><td>10.57</td><td>1</td><td>12.58</td><td>12.73</td></tr><tr><td>4</td><td>11.29</td><td>9.99</td><td>2</td><td>14.72</td><td>14.36</td></tr><tr><td>8</td><td>10.89</td><td>11.02</td><td>4</td><td>15.17</td><td>15.78</td></tr><tr><td>16</td><td>11.51</td><td>12.98</td><td>8</td><td>18.00</td><td>17.93</td></tr><tr><td rowspan="12">2<sup>x</sup><br>24-bit</td><td rowspan="4">1</td><td rowspan="4">Can't Route</td><td rowspan="4">16.11</td><td rowspan="4">Can't Route</td><td rowspan="4">17.92</td><td>2</td><td>16.14</td><td>15.99</td><td>1</td><td>17.85</td><td>18.66</td></tr><tr><td>4</td><td>16.95</td><td>16.80</td><td>2</td><td>16.38</td><td>17.27</td></tr><tr><td>8</td><td>17.43</td><td>16.63</td><td>4</td><td>17.10</td><td>17.41</td></tr><tr><td>16</td><td>18.45</td><td>18.66</td><td>8</td><td>17.65</td><td>17.82</td></tr><tr><td rowspan="4">2</td><td rowspan="4">10.86</td><td rowspan="4">11.76</td><td rowspan="4">12.07</td><td rowspan="4">12.15</td><td>2</td><td>11.13</td><td>11.68</td><td>1</td><td>13.35</td><td>12.58</td></tr><tr><td>4</td><td>10.98</td><td>11.21</td><td>2</td><td>12.95</td><td>12.82</td></tr><tr><td>8</td><td>12.42</td><td>12.19</td><td>4</td><td>15.53</td><td>15.13</td></tr><tr><td>16</td><td>12.37</td><td>12.21</td><td>8</td><td>15.48</td><td>15.20</td></tr><tr><td rowspan="4">3</td><td rowspan="4">11.06</td><td rowspan="4">11.98</td><td rowspan="4">11.54</td><td rowspan="4">12.21</td><td>2</td><td>10.38</td><td>10.25</td><td>1</td><td>12.17</td><td>12.19</td></tr><tr><td>4</td><td>10.71</td><td>10.49</td><td>2</td><td>13.08</td><td>13.05</td></tr><tr><td>8</td><td>11.35</td><td>11.32</td><td>4</td><td>14.20</td><td>14.38</td></tr><tr><td>16</td><td>11.59</td><td>11.88</td><td>8</td><td>16.00</td><td>15.79</td></tr><tr><td rowspan="4">4</td><td rowspan="4">12.15</td><td rowspan="4">10.94</td><td rowspan="4">11.24</td><td rowspan="4">11.42</td><td>2</td><td>9.72</td><td>10.08</td><td>1</td><td>12.42</td><td>12.57</td></tr><tr><td>4</td><td>10.27</td><td>10.34</td><td>2</td><td>14.02</td><td>14.77</td></tr><tr><td>8</td><td>11.58</td><td>10.77</td><td>4</td><td>14.57</td><td>15.09</td></tr><tr><td>16</td><td>11.51</td><td>11.84</td><td>8</td><td>17.06</td><td>16.77</td></tr></tbody></table>

In summary, proposed methods offer, in greater bit widths, significant improvement in all of Area, Time, and ATP even beyond the state-of-the-art T-TIV methods.

The bar graphs (Fig. 21) summarize the results by comparing RegularTIV, the best of T-TIV methods, the best of FR-dLUT methods, and the best of SR-dLUT methods. RegularTIV and T-TIV methods combined are, on the average, superior to proposed FR-dLUT and SR-dLUT methods in 16-bit results. However, in 24-bit results either FR-dLUT or SR-dLUT method ore their variants (-VL) are superior. Only with one *m* value, we lose to our competition for each function (sine and 2^x), and that is in time metric. In each of the two 24-bit functions, there are 4 cases (i.e., 4 different *m*'s), and 3 metrics (Time, Area, ATP). Therefore, we are speaking of 12 ways to compare the TIV microarchitectures. Ours are better in 11 out of 12.
<table><caption>Table 7. ATP Results for 24-bit Resolution</caption><thead><tr><th rowspan="2">Function</th><th rowspan="2">m</th><th rowspan="2">RegularTIV</th><th rowspan="2">2T-TIV</th><th rowspan="2">2T-TIV-IMP</th><th rowspan="2">3T-TIV</th><th colspan="3">Full Random</th><th colspan="3">Semi Random</th></tr><tr><th>Δ</th><th>FR-dLUT</th><th>FR-dLUT-VL</th><th>Δ</th><th>SR-dLUT</th><th>SR-dLUT-VL</th></tr></thead><tbody><tr><td rowspan="12">Sine<br>24-bit</td><td rowspan="4">1</td><td rowspan="4">N/A</td><td rowspan="4">530.85</td><td rowspan="4">1252.13</td><td rowspan="4">502.36</td><td>2</td><td>456.56</td><td>455.18</td><td>1</td><td>492.75</td><td>534.15</td></tr><tr><td>4</td><td>459.20</td><td>474.73</td><td>2</td><td>462.91</td><td>505.86</td></tr><tr><td>8</td><td>471.15</td><td>509.84</td><td>4</td><td>456.68</td><td>493.38</td></tr><tr><td>16</td><td>498.27</td><td>505.12</td><td>8</td><td>495.65</td><td>529.49</td></tr><tr><td rowspan="4">2</td><td rowspan="4">61.24</td><td rowspan="4">46.57</td><td rowspan="4">54.53</td><td rowspan="4">46.51</td><td>2</td><td>37.12</td><td>38.60</td><td>1</td><td>39.46</td><td>36.70</td></tr><tr><td>4</td><td>34.38</td><td>37.69</td><td>2</td><td>40.80</td><td>41.66</td></tr><tr><td>8</td><td>34.93</td><td>37.63</td><td>4</td><td>48.47</td><td>51.38</td></tr><tr><td>16</td><td>43.87</td><td>43.37</td><td>8</td><td>57.69</td><td>61.08</td></tr><tr><td rowspan="4">3</td><td rowspan="4">35.29</td><td rowspan="4">29.38</td><td rowspan="4">32.40</td><td rowspan="4">29.81</td><td>2</td><td>24.70</td><td>25.30</td><td>1</td><td>26.50</td><td>30.16</td></tr><tr><td>4</td><td>23.31</td><td>24.36</td><td>2</td><td>32.31</td><td>35.10</td></tr><tr><td>8</td><td>28.17</td><td>27.95</td><td>4</td><td>36.40</td><td>37.11</td></tr><tr><td>16</td><td>31.35</td><td>31.83</td><td>8</td><td>48.00</td><td>49.70</td></tr><tr><td rowspan="4">4</td><td rowspan="4">32.26</td><td rowspan="4">23.41</td><td rowspan="4">28.81</td><td rowspan="4">23.43</td><td>2</td><td>21.07</td><td>22.23</td><td>1</td><td>23.25</td><td>23.81</td></tr><tr><td>4</td><td>21.83</td><td>19.63</td><td>2</td><td>28.53</td><td>28.62</td></tr><tr><td>8</td><td>22.58</td><td>23.10</td><td>4</td><td>31.84</td><td>33.68</td></tr><tr><td>16</td><td>26.98</td><td>38.84</td><td>8</td><td>44.40</td><td>45.51</td></tr><tr><td rowspan="12">2<sup>x</sup><br>24-bit</td><td rowspan="4">1</td><td rowspan="4">N/A</td><td rowspan="4">924.66</td><td rowspan="4">N/A</td><td rowspan="4">862.91</td><td>2</td><td>740.09</td><td>731.08</td><td>1</td><td>837.38</td><td>875.02</td></tr><tr><td>4</td><td>753.91</td><td>750.06</td><td>2</td><td>716.14</td><td>778.11</td></tr><tr><td>8</td><td>765.44</td><td>731.63</td><td>4</td><td>741.64</td><td>753.18</td></tr><tr><td>16</td><td>807.55</td><td>820.94</td><td>8</td><td>770.69</td><td>778.80</td></tr><tr><td rowspan="4">2</td><td rowspan="4">63.47</td><td rowspan="4">55.32</td><td rowspan="4">68.27</td><td rowspan="4">60.37</td><td>2</td><td>51.14</td><td>54.01</td><td>1</td><td>55.07</td><td>51.88</td></tr><tr><td>4</td><td>47.04</td><td>48.55</td><td>2</td><td>53.84</td><td>53.59</td></tr><tr><td>8</td><td>52.58</td><td>53.82</td><td>4</td><td>68.76</td><td>67.76</td></tr><tr><td>16</td><td>56.24</td><td>56.48</td><td>8</td><td>74.25</td><td>74.19</td></tr><tr><td rowspan="4">3</td><td rowspan="4">38.84</td><td rowspan="4">40.04</td><td rowspan="4">39.63</td><td rowspan="4">39.50</td><td>2</td><td>31.89</td><td>31.66</td><td>1</td><td>34.83</td><td>35.15</td></tr><tr><td>4</td><td>32.17</td><td>31.85</td><td>2</td><td>39.09</td><td>39.43</td></tr><tr><td>8</td><td>35.37</td><td>35.33</td><td>4</td><td>44.77</td><td>45.99</td></tr><tr><td>16</td><td>37.87</td><td>38.78</td><td>8</td><td>56.42</td><td>56.69</td></tr><tr><td rowspan="4">4</td><td rowspan="4">34.55</td><td rowspan="4">28.60</td><td rowspan="4">31.52</td><td rowspan="4">28.72</td><td>2</td><td>23.24</td><td>24.33</td><td>1</td><td>27.39</td><td>27.86</td></tr><tr><td>4</td><td>23.88</td><td>24.44</td><td>2</td><td>31.98</td><td>34.15</td></tr><tr><td>8</td><td>28.28</td><td>26.42</td><td>4</td><td>35.72</td><td>37.59</td></tr><tr><td>16</td><td>26.98</td><td>30.44</td><td>8</td><td>48.13</td><td>48.40</td></tr></tbody></table>
<figure><img src="image_22.png" /><figcaption>(a) Bar graph of sine for 16-bit input resolution.</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>(b) Bar graph of 2^x for 16-bit input resolution.</figcaption></figure>

<figure><img src="image_24.png" /><figcaption>(c) Bar graph of sine for 24-bit input resolution.</figcaption></figure>

<figure><img src="image_25.png" /><figcaption>(d) Bar graph of 2^x for 24-bit input resolution.</figcaption></figure>

<caption>**Fig. 21.** Bar graphs of Area, Time, and ATP for sine and 2^x.</caption>
Fig. 21(a) and Fig. 21(b) shows the 16-bit results. For 16 bits, RegularTIV has the best outcome in 8 out of 18 cases, 2T-TIV-IMP is the best in 7 cases, and our proposed methods are the best in 5 cases. The total is 20, not 18, because there are 2 cases with a tie.

In Fig. 21(c) and Fig. 21(d), due to the routing errors we removed the results of $m=1$ from the bar graphs. From the remaining $m$ values (2, 3, and 4) we can see that proposed method is the best in terms of area, time, and ATP except for one case where $m=2$, in which RegularTIV shows better timing results. When comparing FR-dLUT and SR-dLUT, we can see that SR-dLUT has the best performance in terms of area, and FR-dLUT has the best timing. In the current implementation of SR-dLUT, FR-dLUT shows much better timing performance but only falls behind a little in terms of area, which is why for almost all cases, FR-dLUT outperforms SR-dLUT in terms of ATP.

## 5 Conclusion

In this chapter, we have presented lossless LUT compression methods, called FR-dLUT and SR-dLUT as well as their variants FR-dLUT-VL and SR-dLUT-VL, which can be used to replace TIVs of Multi-Partite (MP) function evaluation method among other applications. It is possible to use our methods and the previous state-of-the-art within the context of any LUT-based method for evaluation of smooth functions. Although it is possible to implement these techniques in software, we implemented our proposed methods in hardware (i.e., low-level Verilog RTL) and benchmarked at 16-bit and 24-bit resolutions within MP implementations of sine and exponential.

It was observed that our four methods yield significant and consistent improvements at high resolution (i.e., 24 bits) over the previous state-of-the-art, which we also implemented through design generators for fair comparison. We synthesized the generated designs on FPGA and found that our methods result in up to 29% improvement in area, 11% improvement in latency, and 26% improvement in ATP over the previous state-of-the-art.

This chapter introduces SR-dLUT-VL for the first time. SR-dLUT is, on the other hand, is based on [10]. Yet, it is optimized and plugged into MP here, besides getting compared with the other methods in many cases. Moreover, FR-dLUT and FR-dLUT-VL are presented in greater detail compared to [16].

In future work, SR-dLUT can be modified to utilize pre-fetching. That may make SR-dLUT better than all other techniques in latency at the expense of some additional area. Since SR-dLUT is already efficient in area, it can afford some additional area. However, pre-fetching can also allow memory packing, which can lower area at the expense of some additional latency.

## References

1. L.J.Y. Lih and C.C. Jong, "A Memory-efficient tables-and-additions method for accurate computation of elementary functions", IEEE Trans. on Computers, vol. 62, pp. 858-872, 2013.
2. H. Hassler and N. Takagi, "Function evaluation by table look-up and addition", Proc. of Symp. on Computer Arithmetic (ARITH), pp. 10-16, 1995.

3. D.D. Sarma and D.W. Matula, "Faithful bipartite ROM reciprocal tables", Proc. of Symp. on Computer Arithmetic (ARITH), pp. 17-28, 1995.

4. M.J. Schulte and J.E. Stine, "Approximating elementary functions with symmetric bipartite tables", IEEE Trans. on Computers, vol. 48, pp. 842-847, 1999.

5. J.E. Stine and M.J. Schulte, "The symmetric table addition method for accurate function approximation", Journal of VLSI Signal Processing, vol. 21, pp. 167-177, 1999.

6. F.D. Dinechin and A. Tisserand, "Multipartite table methods", IEEE Trans. on Computers, vol. 54, pp. 319-330, 2005.

7. J. Detrey and F.D. Dinechin, "Multipartite tables in JBits for the evaluation of functions on FPGA", Diss. INRIA, 2001.

8. S.F. Hsiao, C.S. Wen, Y.H. Chen, and K.C. Huang, "Hierarchical multipartite function evaluation", IEEE Trans. on Computers, vol. 66, pp. 89-99, 2017.

9. J.-M. Muller, "A few results on table-based methods", Reliable Computing, vol. 5, pp. 279-288, 1999.

10. H. Unlu, M.A. Ozkan, H.F. Ugurdag, and E. Adali, "Area-efficient look-up tables for semi-randomly accessible functions", Proc. of WSEAS Recent Advances in Electrical Engineering, pp. 171-174, 2014.

11. S.F. Hsiao, P.H. Wu, C.S. Wen, and P.K. Meher, "Table size reduction methods for faithfully rounded lookup-table-based multiplierless function evaluation", IEEE Trans. on Circuits and Systems II: Express Briefs, vol. 62, pp. 466-470, 2015.

12. D.A. Huffman, "A method for the construction of minimum-redundancy codes", Proceedings of IRE, vol. 40, pp. 1098-1101, 1952.

13. H.F. Ugurdag, O. Keskin, C. Tunc, F. Temizkan, G. Fici, and S. Dedeoglu, "Ro-CoCo: row and column compression for high-performance multiplication on FP-GAs", Proc. of East-West Design and Test Symp. (EWDTS), pp. 98-101, 2011.

14. F.D. Dinechin, "The multipartite method for function evaluation", http://www.ens-lyon.fr/LIP/Arenaire/Ware/Multipartite/. Last accessed on Mar. 8, 2020.

15. F.D. Dinechin and B. Pasca, "Designing custom arithmetic data paths with FloPoCo", IEEE Design & Test of Computers, vol. 28, pp. 18-27, 2011.

16. Y.S. Gener, S. Gören, and H.F. Ugurdag, "Lossless Look-Up Table Compression for Hardware Implementation of Transcendental Functions", Proc. of IFIP/IEEE Int. Conf. on Very Large Scale Integration (VLSI-SoC), pp. 52-57, 2019.