- Home
- Documents
*7KH 5HWXUQ RI 7DEOH %DVHG &RPSXWLQJ parhami/pres_folder/parh18-asilo-return... 2fw 7kh...*

prev

next

out of 24

View

213Download

0

Embed Size (px)

The Return of Table-Based Computing

Behrooz ParhamiUniversity of California,

Santa Barbara

Oct. 2018 The Return of Table-Based Computing Slide 2

About This Presentation

This slide show was first developed in fall of 2018 for anOctober 2018 talk at the 52nd Asilomar Conference onSignals, Systems, and Computers), Pacific Grove, CA, USA.All rights reserved for the author. 2018 Behrooz Parhami

Edition Released Revised Revised Revised

First Fall 2018

Oct. 2018 The Return of Table-Based Computing Slide 3

Tabular Computing: A HistoryAncient tables: Manually computedCharles Babbage: Polynomial approximation of functionsMath handbooks: My generation used themModern look-up tables: Speed-up; Caching; Seed value

Oct. 2018 The Return of Table-Based Computing Slide 4

Example of Table-Based ComputationCompute log10 35.419

Table: log of values in [1.00, 9.99], in increments of 0.01]

Pre-scaling: log10 35.419 = 1 + log10 3.5419

Table access: log10 3.54 = 0.549 003log10 3.55 = 0.550 228

Interpolation: log10 3.5419 = log10 3.54 + e= 0.549 003 + (0.19)(0.550 228 0.549 003)= 0.549 236

Final result: log10 35.419 = 1 + 0.549 236 = 1.549 236

Oct. 2018 The Return of Table-Based Computing Slide 5

Direct and Indirect Table-Lookup

2 by table

Result(s) bits

Pre- proces- sing logic

Post- processing logic

Smaller table(s)

Operand(s) bitsu u v

v

Operand(s) bitsu

Result(s) bitsv

.

.

.

. . .

Direct lookup: Operands serve as address bits into tableIndirect lookup: Inputs pre-processed; output post-processed

Oct. 2018 The Return of Table-Based Computing Slide 6

Memory Cost Reduction Trends

Oct. 2018 The Return of Table-Based Computing Slide 7

Tables in Primary and Supporting RolesTables are used in two ways:

As main computing mechanism

In supporting role (e.g., as in initial estimate for division)

Boundary between two uses is fuzzy

Pure logic Hybrid solutions Pure tabular

Historically, we started with the goal of designing logic circuits for particular arithmetic computations and ended up using tables to facilitate or speed up certain steps

From the other side, we aim for a tabular implementation and end up using peripheral logic circuits to reduce the table size

Some solutions can be derived starting at either endpoint

Oct. 2018 The Return of Table-Based Computing Slide 8

Lx + f+() Lx + f-()

Strategy: Reduce the table size by using an auxiliary unary function to evaluate a desired binary function

Addition/subtraction in a logarithmic number system; i.e., finding Lz = log(x y), given Lx and Ly

Solution: Let = Ly Lx

Lz = log(x y)

= log(x (1 y/x))

= log x + log(1 y/x)

= Lx + log(1 log1)

Pre-process

f+ table f- table

Postprocess

Lx

Ly

Lz

= Ly Lx

Example for Table Size Reduction

Oct. 2018 The Return of Table-Based Computing Slide 9

Interpolating Memory Unit

Add

a

f(x)

Multiply

b

x

x

x lo x hi x

f(x)

Initial linear approximation

Improved linear approximation

a + b x

Linear interpolation: Computing f(x), x [xlo, xhi], from f(xlo) and f(xhi)

x xlof (x) = f (xlo) + [ f (xhi) f (xlo) ] 4 adds, 1 divide, 1 multiplyxhi xlo (2 adds) (1 shift)

Oct. 2018 The Return of Table-Based Computing Slide 10

Linear interpolation for computing f(x) using 4 subintervals.

Add

a

f(x)

Multiply 4x

x

x min x max x

f(x)

i = 0

a + b x

(i) b /4 (i)

4-entry tables 2-bit address

x

(i) (i)

i = 1 i = 2

i = 3

Approximating log2x for x in [1,2) using linear interpolation within 4 subintervals.

i xlo xhi a (i) b (i)/4 Max error

0 1.00 1.25 0.004 487 0.321 928 0.004 4871 1.25 1.50 0.324 924 0.263 034 0.002 9962 1.50 1.75 0.587 105 0.222 392 0.002 1423 1.75 2.00 0.808 962 0.192 645 0.001 607

Linear Interpolation with 4 Subintervals

Oct. 2018 The Return of Table-Based Computing Slide 11

Approximation of reciprocal (1/x) and reciprocal square root (1/x) functions with 29-30 bits of precision, so that a long floating-point result can be obtained with just one iteration at the end [Pine02]

u v w 1.

c Table

b Table

a Table

Squarer Radix-4 Booth

Radix-4 Booth

Partial products gen Partial products gen

9 bits 24 bits 19 bits

30 bits 20 bits 12 bits

16 bits

Multioperand adder

30 bits, carry-save

Double-precision significand f(x) = c + bv + av

2

1 square

Comparable to a

multiplier

2 mults

2 adds

Second-Degree Interpolation Example

Oct. 2018 The Return of Table-Based Computing Slide 12

Trade-offs in Cost, Speed, and Accuracy

6 8 10 -9

Wo

rst-

case

ab

solu

te e

rro

r

Number of bits (h)

Linear

0 2 4 10

-6 10

-3 10

-8 10

-5 10

-2 10

-7 10

-4 10

-1 10

Second- order

Third- order

For the same target error, higher-order interpolation leads to smaller tables (2h entries) but greater hardware complexity on the periphery

Oct. 2018 The Return of Table-Based Computing Slide 13

Distributed arithmetic for the evaluation of weighted sums and other linear expressions

Evaluation of linear expressions (assume unsigned values)

z = ax + by = a xi 2i + b yi 2i

= (axi + byi) 2i

0

Address

4-entry table

b

a + b

a

xi

yi

Sum

Carry

CSA

Data

k/

k1/

k1/

k/

k1/

k1/

LSBzi

CS residualSuper-efficient computation of linear forms using only bitwise addition hardware

Tables in Bit-Serial Arithmetic

Oct. 2018 The Return of Table-Based Computing Slide 14

Level-1 table provides a rough approximation for the sum

Two-Level Table for Approximate Sum

Level-2 table refines the sum for a greater precision

Oct. 2018 The Return of Table-Based Computing Slide 15

(x + y) mod p = (x mod p + y mod p) mod p

Table 1

Table 2

v

d d

Adder

Adder

p

Mux+

d-bit output

b-bit inputbg g

d d

d+1

dd

Sign

d+1

z

z mod p

LvH

Two-table modular reduction scheme based on divide-and-conquer.

Divide the argument z into (b g)-bit upper part (x) and g-bit lower part (y), where xends with g zeros

Modular Reduction: Computing z mod p

Oct. 2018 The Return of Table-Based Computing Slide 16

Modular reduction based on successive refinement.

Table 2 m*

d

d-bit output

bh h

z mod p

b-bit input

z

Adder

Table 1

v

d*

d*h h d*

d*

Table 1 provides a rough estimate for the final result

Table 2 refines the estimate

Divide the argument z into (b h)-bit upper part (x) and h-bit lower part (y), where x ends with h zeros

Another 2-Level Table for Mod Reduction

z mod p

Oct. 2018 The Return of Table-Based Computing Slide 17

Bipartite tables: Main idea

Total table size is 2a+b + 2kb, in lieu of 2k; width of table entries has been ignored in this comparison

a

k-bit input x

Add

u Table

v Table

b

kab

k-bit output y

x0

x1

x2

u(x0, x1)

v(x0, x2)

f(x)

Subintervals

An interval

f(x)

x

(a) Hardware realization (b) Linear approximation

Common Slope

Divide the domain of interest into 2a intervals, each of which is further divided into 2b smaller subintervals

The trick: Use linear interpolation with an initial value determined for each subinterval and a common slope for each larger interval

Bipartite and Multipartite Lookup Tables

Oct. 2018 The Return of Table-Based Computing Slide 18

Approximate value is read out from the top table, which also supplies an error direction and an accurate error bound

Adaptive Table-Based Computing

The more precise value is compared with the approximate value off the critical path for periodic quality monitoring

Oct. 2018 The Return of Table-Based Computing Slide 19

The more computationally complex the function, the greater the cost and latency benefits of using table-based schemes

FPGA-Based Integer Square-Rooters

Oct. 2018 The Return of Table-Based Computing Slide 20

Conclusions and Future Work

Use of tables is expanding: Memory cost Memory size

Benefits of Returning to Table-Based Computing:Fast approximation + added precision as needed

Knowable error direction and magnitudeTable-size/latency/precision trade-offs

Avoid waste from recomputation

Future work and more detailed comparisonsAssessment of speed benefits in application contexts

Quantifying cost and energy reductionBit-level table optimization methods

Sparse and associative tables

parhami@ece.ucsb.edu http://www.ece.ucsb.edu/~parhami/

Questions or Comments?

The Return of Table-Based Computing

Behrooz ParhamiUniversity of California,

Santa Barbara

Back-Up Slides

Oct. 20