# Presentation: 569785

## Digital Design with FPGAs:Examples and Resource Saving TipsScreen B

- Wu, Jinyuan
- Fermilab
- IEEE NSS 2007 Refresher Course
- Oct, 2007

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Indirect Cost of Complexity

- If something like this can do the job...

- ... why do these?

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Outline

- Digital Design with FPGAs (This 45 min. Course)
- Logic Element in a Nutshell
- Variations of the Registered Adders
- Tricks of Using RAM
- RAM based histograms
- Topics on Multipliers
- Curved Track Fitter
- Advanced Topics on FPGA Applications (Included as Supplemental Materials)
- Doublet Finding, Hash Sorter
- Triplet Finding, Tiny Triplet Finder (TTF)
- Options of Sequence Control, Recursive Structure, etc.

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## What Can Be Done With a Logic Element

- A
- B
- C
- D

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Xilinx Look-Up Table

- LUT4

- SRL16

- RAM16

- 4-input
- Look-Up Table

- 16-bit
- Shift Register

- 16-bit
- Distributed RAM

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Transistor Usage of Logic Element

- LUT
- 16-bit

- 6-transistor RAM bit

- At least 96 transistors

- X 16

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Full Adder

- LUT
- 8-bit

- LUT
- 8-bit

- At least 96 transistors

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Transistor Counts

| FPGA 1LE: 4-in LUT + DFF | >96 |
| --- | --- |
| 4-input NAND, NOR etc. | 8 |
| 2-to-1 MUX | 6 |
| Static RAM | 6/bit |
| Full Adder | 24-28 |
| N-bit Multiplier | > (N2)/2 FA |

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## TDC Using FPGA Logic Chain Delay

- This scheme uses current FPGA technology 
- Low cost chip family can be used.  (e.g. EP1K10QC208-2 $15.25) 
- Fine TDC precision can be implemented in slow devices (e.g., 0.4 ns in a 200 MHz chip). 

- IN

- CLK

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Edge Detection + Sample Selection

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## ADC Test: Waveform Digitization on BD3_19

- Raw
- Data

- Input Waveform, Overlap Trigger
- & Reference Voltage

- Converted

- FPGA

- TDC

- TDC

- 50

- 50

- 1000pF

- 100

- VREF

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Sorter Operation

- Operation:
- Initialization: All registers become 0xFF after DUMP=1 for at least 4 clock cycles.
- Data Fetching: All data are clocked through and lowest four numbers are stored.
- Dump: The lowest four numbers are output in sequence and all registers become 0xFF, i.e., initialized.
- Warning:  To keep all sorted data, do not use this circuit. Consider other schemes.

- Sorter

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Outline

- Digital Design with FPGAs (This 45 min. Course)
- Logic Element in a Nutshell
- Variations of the Registered Adders
- Tricks of Using RAM
- RAM based histograms
- Topics on Multipliers
- Curved Track Fitter
- Advanced Topics on FPGA Applications (Included as Supplemental Materials)
- Doublet Finding, Hash Sorter
- Triplet Finding, Tiny Triplet Finder (TTF)
- Options of Sequence Control, Recursive Structure, etc.

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## LE Implementation of Registered Adder

- LUT
- 8-bit

- LUT
- 8-bit

- LUT
- 8-bit

- LUT
- 8-bit

- A1

- B1

- A2

- B2

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## The Counter With Inc, Dec and Count Enable Controls, a Special Case of Accumulator

- D[]

- Q[]

- 0/+1/-1

- B[]

- A+B

- D[]

- EN

- Don’t confuse the count enable CNTEN
- With clock enable EN.

- 0: Disable
- +1: Inc
- -1: Dec

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Decimations: With Integer ratios

- f S

- f D = f S / 6

- Sample
- Interval = 6

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Resource Usage of Comparators

- A

- A

- B

- A

- B

- A

- B

- A

- B

- Equality
- Comparator
- A==Constant
- 0.25 LE/bit +

- Equality
- Comparator
- A==B
- 0.5 LE/bit +

- Magnitude
- Comparator
- A>B
- 1 LE/bit

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Decimation With Non-integer ratios

- f S

- f D = f S / 6

- f D = f S / 6.2

- Sample
- Interval = 6

- Sample
- Interval = 7

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Duty-Cycle Based Single-Pin DAC

- Counter

- Q

- A

- B

- A>B

- DAC Input

- The duty-cycle of the comparator output is proportional to the DAC input at port A.
- Use external RC as low-pass filter.
- Output voltage of an ideal LP filter is proportional to the DAC input.

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Exponential Sequence Generator

- 

- Q

- SET

- D

- if (CO==1) {Q = Q - Q/32;}

- An exponential sequence is generated using an accumulator shown above.
- Note that not even one multiplier is used.
- Other function sequences: sine, co-sine, tangent, co-tangent etc. can also be generated similarly.

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Outline

- Digital Design with FPGAs (This 45 min. Course)
- Logic Element in a Nutshell
- Variations of the Registered Adders
- Tricks of Using RAM
- RAM based histograms
- Topics on Multipliers
- Curved Track Fitter
- Advanced Topics on FPGA Applications (Included as Supplemental Materials)
- Doublet Finding, Hash Sorter
- Triplet Finding, Tiny Triplet Finder (TTF)
- Options of Sequence Control, Recursive Structure, etc.

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Implementation of Pipeline and FIFO

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Zero-Suppression

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Pipeline and FIFO

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## TDC  Data Concentration 48 Ch

- L1 Buffer
- 1xM4K
- 16x256

- Zero
- Supp.

- TDC/HRL

- TDC/HRL

- EV Buffer &
- Truncating
- 16x128x2

- TDC/HRL

- TDC/HRL

- Ch 4-7, TDC & L1 Buffer

- TDC/L1 Buffer/MUX
- Channels 16-31

- TDC/L1 Buffer/MUX
- Channels 32-47

- Ch 8-11, TDC & L1 Buffer

- Ch 12-15, TDC & L1 Buffer

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Ping-Pong Paged RAM

- MPU

**UPDATA**

**FA**

**P**

**MA**

- AA[9]=!P

- AB[9]=P

**FA**

**MA**

- P==0
- MPU accesses page 0
- FPGA accesses page 1
- P==1
- MPU accesses page 1
- FPGA accesses page 0

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## FPGA RAM Aspect Ratio

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Each Address Line: Doubles RAM Size.

- 256
- Words

- 256
- Words

- 256
- Words

- 256
- Words

- 256
- Words

- 8
- address
- lines

- 9
- address
- lines

- 8+8
- address
- lines

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## High Precision 2^N LUT

- 2(A+B+C) = 2(A) * 2(B) *(1+(ln2)*C)

- X

- A

- B

- ROM LUT
- 28=256 w

- ROM LUT
- 28=256 w

- C

- 2(A)

- 2(B)

- X

- 1+

- (32-bit Precision)

- X

- 0.6931471

- Constant Multiplication,
- May use LUT

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Outline

- Digital Design with FPGAs (This 45 min. Course)
- Logic Element in a Nutshell
- Variations of the Registered Adders
- Tricks of Using RAM
- RAM based histograms
- Topics on Multipliers
- Curved Track Fitter
- Advanced Topics on FPGA Applications (Included as Supplemental Materials)
- Doublet Finding, Hash Sorter
- Triplet Finding, Tiny Triplet Finder (TTF)
- Options of Sequence Control, Recursive Structure, etc.

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Histogram Booking

- +1

**RA,WA**

**K**

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Read-After-Write (RAW) Hazard

**K4**

**DV**

- +1

**K1**

**K1**

**K0**

**K2**

**N1**

- Wrong!
- Wanted to be **N1+1**

| K0 | K1 | K2 | K1 | K4 |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  | K0 | K1 | K2 | K1 | K4 |  |  |  |
|  |  | K0 | K1 | K2 | K1 | K4 |  |  |
|  |  |  | K0 | K1 | K2 | K1 | K4 |  |
|  |  |  | N0 | N1 | N2 | N1 | N4 |  |
|  |  |  |  | K0 | K1 | K2 | K1 | K4 |
|  |  |  |  | N0+1 | N1+1 | N2+1 | N1+1 | N4+1 |

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## RAW Hazard Prevention: Instruction Merging

**K**

**DV**

- +1+N

- &&==

- &&==

- &&==

- If a bin is hit several times, they are combined in a single accumulation instruction.

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Histogram Fast Reset

- Keep a run counter RC that ++ for each reset.
- Assign an Index RAM that has same number of bins as the Content RAM.
- When a bin is hit, the Index RAM is first readout (to MR) and then written with current RC.
- If MR!=RC, the bin is to be reset.
- If MR==RC, the bin is to be +1.

- +1

**RA,WA**

**K**

**RC**

- RC
- CE

- ==

**0**

**MR!=RC**
**Old run**

**MR==RC**
**Current run**

**Index**
**RAM**

**Reset**

**Content**
**RAM**

**MR**

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Prevent Index RAM from Rolling Over

- The RC/Index RAM have limited bits that may cause roll-over (millennium-bug).
- E.g. RC=1, =513, =1025 look same with 9-bit RC.
- To prevent roll-over, write a bin of Index RAM with RC in rotational address at each reset.
- For a 256-bin histogram, the contents in Index RAM will be always RC-256 or newer.

- +1

**RA,WA**

**K**

**RC**

- RC
- CE

- ==

**0**

**MR!=RC**
**Old run**

**MR==RC**
**Current run**

**Index**
**RAM**

**Reset**

**Content**
**RAM**

**MR**

**A(RC)**

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Outline

- Digital Design with FPGAs (This 45 min. Course)
- Logic Element in a Nutshell
- Variations of the Registered Adders
- Tricks of Using RAM
- RAM based histograms
- Topics on Multipliers
- Curved Track Fitter
- Advanced Topics on FPGA Applications (Included as Supplemental Materials)
- Doublet Finding, Hash Sorter
- Triplet Finding, Tiny Triplet Finder (TTF)
- Options of Sequence Control, Recursive Structure, etc.

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Multipliers in Cyclone II

- Multiplier
- 18-bit x 18-bit

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Approximation is OK

- X

- 8-bit Square

- |Y-X|<0.5
- INT(Y+0.5)=X

- X2

- 00

- FF00&X2

- Y

- ^2

- &

- sqrt

- X=256-511

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Replacing Multiplication With Addition

- 0

- 0

- A

- A

- +)

- 5*A

- 0

- 0

- A

- A

- -)

- 248*A

- 0

- 0

- 0

- 0

- 0

- 0

- 0

- 0

- 0

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Outline

- Digital Design with FPGAs (This 45 min. Course)
- Logic Element in a Nutshell
- Variations of the Registered Adders
- Tricks of Using RAM
- RAM based histograms
- Topics on Multipliers
- Curved Track Fitter
- Advanced Topics on FPGA Applications (Included as Supplemental Materials)
- Doublet Finding, Hash Sorter
- Triplet Finding, Tiny Triplet Finder (TTF)
- Options of Sequence Control, Recursive Structure, etc.

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Relative Errors of Several Track Fitter Schemes

**Least Square Fitter**

**Multiplier-less FPGA LS Fitter**

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Coefficient Table, Least Square Fitter

| Half-length of the Track |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| z-z0 | 16 |  | 14 |  | 12 |  | 10 |  | 8 |  | 6 |  | 4 |  |
|  | ei | e[i] | ei | e[i] | ei | e[i] | ei | e[i] | ei | e[i] | ei | e[i] | ei | e[i] |
| -16 | 5.3 | 6 |   |  |   |  |   |  |   |  |   |  |   |  |
| -14 | 3.3 | 2 | 7.5 | 8 |  |  |  |  |  |  |  |  |  |  |
| -12 | 1.6 | 2 | 4.3 | 4 | 11.3 | 12 |  |  |  |  |  |  |  |  |
| -10 | 0.1 | 0 | 1.6 | 2 | 5.6 | 5 | 17.9 | 18 |  |  |  |  |  |  |
| -8 | -1.1 | 0 | -0.7 | -2 | 1.0 | 1 | 7.2 | 7 | 31.0 | 31 |  |  |  |  |
| -6 | -2.0 | -3 | -2.4 | -2 | -2.6 | -4 | -1.2 | -1 | 7.8 | 8 | 61.0 | 56 |  |  |
| -4 | -2.6 | -3 | -3.6 | -5 | -5.1 | -5 | -7.2 | -8 | -8.9 | -9 | 0.0 | 12 | 146.3 | 144 |
| -2 | -3.0 | -3 | -4.4 | -4 | -6.6 | -5 | -10.7 | -9 | -18.8 | -20 | -36.6 | -40 | -73.1 | -64 |
| 0 | -3.2 | -2 | -4.6 | -2 | -7.2 | -8 | -11.9 | -14 | -22.2 | -20 | -48.8 | -56 | -146.3 | -160 |
| 2 | -3.0 | -3 | -4.4 | -4 | -6.6 | -5 | -10.7 | -9 | -18.8 | -20 | -36.6 | -40 | -73.1 | -64 |
| 4 | -2.6 | -3 | -3.6 | -5 | -5.1 | -5 | -7.2 | -8 | -8.9 | -9 | 0.0 | 12 | 146.3 | 144 |
| 6 | -2.0 | -3 | -2.4 | -2 | -2.6 | -4 | -1.2 | -1 | 7.8 | 8 | 61.0 | 56 |   |  |
| 8 | -1.1 | 0 | -0.7 | -2 | 1.0 | 1 | 7.2 | 7 | 31.0 | 31 |   |  |  |  |
| 10 | 0.1 | 0 | 1.6 | 2 | 5.6 | 5 | 17.9 | 18 |   |  |  |  |  |  |
| 12 | 1.6 | 2 | 4.3 | 4 | 11.3 | 12 |   |  |  |  |  |  |  |  |
| 14 | 3.3 | 2 | 7.5 | 8 |   |  |  |  |  |  |  |  |  |  |
| 16 | 5.3 | 6 |   |  |  |  |  |  |  |  |  |  |  |  |
| Error | 2.91 | 3.02 | 3.05 | 3.15 | 3.22 | 3.26 | 3.41 | 3.43 | 3.65 | 3.65 | 3.93 | 3.99 | 4.28 | 4.29 |
| Ratio |   | 1.04 |   | 1.03 |   | 1.01 |   | 1.00 |   | 1.00 |   | 1.02 |   | 1.00 |

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Coefficient Table, ML Fitter

| Half-length of the Track |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| z-z0 | 16 |  | 14 |  | 12 |  | 10 |  | 8 |  | 6 |  | 4 |  |
|  | ei | e[i] | ei | e[i] | ei | e[i] | ei | e[i] | ei | e[i] | ei | e[i] | ei | e[i] |
| -16 | 5.3 | 6 |   |  |   |  |   |  |   |  |   |  |   |  |
| -14 | 3.3 | 2 | 7.5 | 8 |  |  |  |  |  |  |  |  |  |  |
| -12 | 1.6 | 2 | 4.3 | 4 | 11.3 | 12 |  |  |  |  |  |  |  |  |
| -10 | 0.1 | 0 | 1.6 | 2 | 5.6 | 5 | 17.9 | 18 |  |  |  |  |  |  |
| -8 | -1.1 | 0 | -0.7 | -2 | 1.0 | 1 | 7.2 | 7 | 31.0 | 31 |  |  |  |  |
| -6 | -2.0 | -3 | -2.4 | -2 | -2.6 | -4 | -1.2 | -1 | 7.8 | 8 | 61.0 | 56 |  |  |
| -4 | -2.6 | -3 | -3.6 | -5 | -5.1 | -5 | -7.2 | -8 | -8.9 | -9 | 0.0 | 12 | 146.3 | 144 |
| -2 | -3.0 | -3 | -4.4 | -4 | -6.6 | -5 | -10.7 | -9 | -18.8 | -20 | -36.6 | -40 | -73.1 | -64 |
| 0 | -3.2 | -2 | -4.6 | -2 | -7.2 | -8 | -11.9 | -14 | -22.2 | -20 | -48.8 | -56 | -146.3 | -160 |
| 2 | -3.0 | -3 | -4.4 | -4 | -6.6 | -5 | -10.7 | -9 | -18.8 | -20 | -36.6 | -40 | -73.1 | -64 |
| 4 | -2.6 | -3 | -3.6 | -5 | -5.1 | -5 | -7.2 | -8 | -8.9 | -9 | 0.0 | 12 | 146.3 | 144 |
| 6 | -2.0 | -3 | -2.4 | -2 | -2.6 | -4 | -1.2 | -1 | 7.8 | 8 | 61.0 | 56 |   |  |
| 8 | -1.1 | 0 | -0.7 | -2 | 1.0 | 1 | 7.2 | 7 | 31.0 | 31 |   |  |  |  |
| 10 | 0.1 | 0 | 1.6 | 2 | 5.6 | 5 | 17.9 | 18 |   |  |  |  |  |  |
| 12 | 1.6 | 2 | 4.3 | 4 | 11.3 | 12 |   |  |  |  |  |  |  |  |
| 14 | 3.3 | 2 | 7.5 | 8 |   |  |  |  |  |  |  |  |  |  |
| 16 | 5.3 | 6 |   |  |  |  |  |  |  |  |  |  |  |  |
| Error | 2.91 | 3.02 | 3.05 | 3.15 | 3.22 | 3.26 | 3.41 | 3.43 | 3.65 | 3.65 | 3.93 | 3.99 | 4.28 | 4.29 |
| Ratio |   | 1.04 |   | 1.03 |   | 1.01 |   | 1.00 |   | 1.00 |   | 1.02 |   | 1.00 |

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Fitting Errors From Approximations

- 20% approximation in coefficients ...

- ...increases fitting error by only 2%.

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## Additional Courses on FPGA Applications

- Digital Design with FPGAs (This 45 min. Course)
- Logic Element in a Nutshell
- Variations of the Registered Adders
- Tricks of Using RAM
- RAM based histograms
- Topics on Multipliers
- Curved Track Fitter
- Advanced Topics on FPGA Applications (Included as Supplemental Materials)
- Doublet Finding, Hash Sorter
- Triplet Finding, Tiny Triplet Finder (TTF)
- Options of Sequence Control, Recursive Structure, etc.
- Reconfigurable Computing with FPGA (Planned)

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab

## The End

- Thank you

- IEEE NSS Refresher Course

- Oct. 2007, Wu Jinyuan, Fermilab