# Presentation: 884891

## Resource Awareness FPGA Design Practices for Reconfigurable Computing: Principles and Examples

- _Wu, Jinyuan_
- Fermilab, PPD/EED
- April 2007

## Introduction

- Short Course (1/2 day):
- “How to Design Compact FPGA Functions:
- 	Resource awareness design practices.”
- http://www-ppd.fnal.gov/EEDOffice-W/Projects/ckm/comadc/CompactFPGAdesign.pdf
- Refresher Course (45min):
- “Resource Saving in Micro-Computer Software & FPGA Firmware Designs”
- http://www-ppd.fnal.gov/EEDOffice-W/Projects/ckm/comadc/ResourceSaving.ppt
- This Document
- Resource Awareness FPGA Design Practices for Reconfigurable Computing: Principles and Examples

- What can be done with an FPGA?

## Example: ADC Using FPGA

- AMP &
- Shaper

- AMP &
- Shaper

- AMP &
- Shaper

- AMP &
- Shaper

- AMP &
- Shaper

- AMP &
- Shaper

- AMP &
- Shaper

- AMP &
- Shaper

- ADC

- ADC

- ADC

- ADC

- FPGA

- TDC

- TDC

- TDC

- TDC

- R1

- R1

- C

- R2

- FPGA

- VREF

- Analog signals from AMP & Shapers are directly fed to FPGA pins.
- FPGA outputs and passive RC network are used to generate ramping reference voltage VREF.
- The input voltages and VREF are compared using FPGA differential input receivers.
- The times of transitions representing input voltage values are digitized by TDC blocks in FPGA.

## TDC Inside FPGA

**c0**

**c90**

**c180**

**c270**

**c0**

**Multiple**
**Sampling**

**Clock**
**Domain**
**Changing**

**Trans. Detection**
**& Encode**

**Q0**

**Q1**

**Q2**

**Q3**

**QF**

**QE**

**QD**

**c90**

**Coarse Time**
**Counter**

**DV**

**T0**
**T1**

**TS**

- Sampling rate: 360 MHz x4 phases = 1.44 GHz.
- LSB = 0.69 ns.
- Logic elements with critical timing are assigned as shown.

- 4Ch

- Logic elements with non-critical timing are freely placed by the fitter of the compiler.

## ADC Test: Waveform Digitization on BD3_19

- Raw
- Data

- Input Waveform, Overlap Trigger
- & Reference Voltage

- Converted

- FPGA

- TDC

- TDC

- 50

- 50

- 1000pF

- 100

- VREF

- A lot can be done with an FPGA if one can image.

## Micro-computing vs. Reconfigurable Computing

- In microprocessor, the users specify program on fixed logic circuits.
- In FPGA, the users specify logic circuits (as well as program).
- The FPGA computing needs not to follow microprocessor architectures.  (But useful experiences can be borrowed.)
- The usefulness of FPGA reconfigurable computing is still to be fully appreciated.

- (100+3-4)*5+7 =?

- 100

- 3

- 4

- 5

- 7

- Control:

- Data: 100,3,4,5,7

- LD

- (-)

- (+)

- (*)

- (+)

- CPU

- FPGA

- Data

- Program

- Configuration

- Data

- Program

## Example: Track Fitting

## Relative Errors of Several Track Fitter Schemes

**Least Square Fitter**

**Multiplier-less FPGA LS Fitter**

## Least Square Fitter

- y1

- y2

- y3

- y4

- y5

- y6

- y7

- c1

- c2

- c3

- c4

- c5

- c6

- c7

- d1

- d2

- d3

- d4

- d5

- d6

- d7

- e1

- e2

- e3

- e4

- e5

- e6

- e7

- X

- 

- X

- 

- X

- 

- The parameters can be described as inner-products.
- Hit coordinates and coefficients are fed simultaneously.
- The inner-products can be calculated with multiplier-accumulator structures.

## Multiplier-less (ML) Quasi-Least Square Fitter

- 

- 

- 

- y1

- y2

- y3

- y4

- y5

- y6

- y7

- x1

- x2

- x3

- x4

- x5

- x6

- x7

- <<

- +/-

- +/-

- +/-

- <<

- <<

- 4

- The coefficients are described as “two-bit” numbers, e.g.:
- 5=4+1; 7=8-1; 112=128-16;
- The multiplication is replaced with two shift & add/sub operations.
- There are two clock cycles to fetch a measurement point (i.e., y1, y2, etc.) allowing two shift & add/sub operations

- +1

- 8

- -1

- 128

- -16

## Inaccuracy Doesn’t Matter, A Lot of Time

**Least Square Fitter**

**Multiplier-less**
**Quasi-Least Square**
**FPGA Fitter**

## Fitting is easy. Matching hits is harder.

|  | Software | FPGA
Typical | FPGA Resource Saving Approaches |
| --- | --- | --- | --- |
|  | O(n2)
for(){
     for(){...}
} | O(n)*O(N)
Comparator
Array | Hash Sorter
O(n)*O(N): in RAM |
|  | O(n3)
for(){
     for(){
        for(){...}
     }
} | O(n)*O(N2)
CAM,
Hugh Trans. | Tiny Triplet Finder
O(n)*O(N*logN) |
|  | O(n4)
for(){ for(){
   for(){ for()
    {...}
}}} |  |  |

## Resource Saving Tricks

- Loop Reduction Tricks:
- The number of computations in a given task is reduced by (1) using fewer iterations in loops or/and (2) using fewer operations in each iteration.

- Non-Loop Reduction Tricks:
- The number of computations in a given task is unchanged. The FPGA resource is saved by (1) reusing the resources multiple times via sequencing or/and (2) using transistor-saving resources such as RAM.

## Resource Saving TricksLoop-Reduction

- Multiplier-less (ML) Approaches

- Recursive Implementation of FIR Filter

- FFT: O(n)*O(log(N))

- Tiny Triplet Finder: O(n)*O(N*log(N))

## Resource Saving TricksNon-Loop-Reduction

- Sequencing:

- Using RAM: Hash Sorter/Histogram

- OP1

- Initialization

- OP2

- OP3

- OP4

- OP1

- OP2

- OP3

- OP4

- OP1

- OP2

- OP3

- OP4

- OP1

- OP2

- OP3

- OP4

- Initialization 1

- Initialization 2

- Initialization 3

- OP1

- OP2

- OP3

- OP4

- OP1

- OP2

- OP3

- OP4

- OP1

- OP2

- OP3

- OP4

- OP1

- OP2

- OP3

- OP4

## An Example of 

- Input
- Ctrl

- D

- W/R

- WA

- RA

- 16

- 32

*An Example of*
- Inexplicit Computing & Hidden Resource

- Data with random time stamp are re-ordered according to beam crossing (BCO).
- Data with same BCO output together and the bandwidth becomes smaller.
- Inexplicit computing (sorting) is performed with hidden resource (RAM, it should be static RAM not dynamic RAM.)

- RAM

## Why Saving Resource?

- Why not?

## The Fever of Moore’s Law vs. Maxwell’s Equations

- 1998 2000 2002 2004 2006 2008 2010

- Op/sec

- MIT, 2002

- During the hot days of Moore’s Law, the rules of thumb are:
_**BRB**_ – Buy Rather than Build
_**URU**_ – Use Rather than Understand
_**WRW**_ – Wait Rather than Work
- From fundamental principles like Maxwell’s Equations, it is known limits of Moore’s Law exist.  The technology advance should come from:
_**The I**__**3**__** Law**_: Imagination, Innovation & Implementation.

- WRW

## Total Useful Works = (Clock Frequency) x (Silicon Size) x (Efficiency)

- There is a big room for improvement on computation efficiency in both micro-computer software and FPGA firmware.
- Resource awareness not only saves direct cost, but also indirect cost like power consumption, PC board layout, cooling etc.
- Unnecessary artificial complexities confuse people, often including the designer.
- Resource saving helps today when technology stales.
- Resource saving helps future with technology progresses.

- E

- F

- S

- E

- F

- S

- Primarily Users’
- Responsibility