# Presentation: 577648

## Advanced Topics on FPGA ApplicationsScreen B

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

## 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, Supplemental Materials

- Oct. 2007, Wu Jinyuan, Fermilab

## Doublet Matching

- 2*y1 = y2
- 3*y1 = y3

- IEEE NSS Refresher Course, Supplemental Materials

- Oct. 2007, Wu Jinyuan, Fermilab

## Example of Evaluating the Key Number

- 3*y1 = y3

- K= 3*y1/8
- K= y3/8

- *3

- y1

- y3

- K

- K

- IEEE NSS Refresher Course, Supplemental Materials

- Oct. 2007, Wu Jinyuan, Fermilab

## Link List Structure of Hash Sorter

- DIN

- DOUT

- Index RAM

- Pointer RAM

- DATA RAM

- K

- IEEE NSS Refresher Course, Supplemental Materials

- Oct. 2007, Wu Jinyuan, Fermilab

## Histogram with Fast Reset

**K**

**DV**

- +1

**0**

- IEEE NSS Refresher Course, Supplemental Materials

- Oct. 2007, Wu Jinyuan, Fermilab

## An Example of Track Recognition: Hits

- IEEE NSS Refresher Course, Supplemental Materials

- Oct. 2007, Wu Jinyuan, Fermilab

## An Example of Track Recognition: Doublets

- Hits are paired together as doublet.

- Ghost doublets may exist.

- Ghost doublets may exist.

- IEEE NSS Refresher Course, Supplemental Materials

- Oct. 2007, Wu Jinyuan, Fermilab

## An Example of Track Recognition: Histogram

- Two track parameters can be calculated for each doublet.

- A 2-D histogram is booked.

- Doublets from same track are entered into same bin, (since they have same track parameters).

- Sometimes they are stored in clusters.

- This is a “ghost”.

- IEEE NSS Refresher Course, Supplemental Materials

- Oct. 2007, Wu Jinyuan, Fermilab

## An Example of Track Recognition: Tracks

- All doublets from a track are contained in a cluster.

- IEEE NSS Refresher Course, Supplemental Materials

- Oct. 2007, Wu Jinyuan, Fermilab

## Simulation Results

- An event with 200 tracks

- It still works at 1000 tracks/event

- IEEE NSS Refresher Course, Supplemental Materials

- Oct. 2007, Wu Jinyuan, Fermilab

## Example: Finding “Soft Jets”

- A simulated event with 200 tracks.
- Flat distributions.
- Min. R = 55 cm

- 16 soft tracks are added.
- They are grouped in 2 small initial angle regions, i.e., 2 “soft jets”.

- Can you see the “soft jets”?

- Can you see the “soft jets” now?

- IEEE NSS Refresher Course, Supplemental Materials

- 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, Supplemental Materials

- Oct. 2007, Wu Jinyuan, Fermilab

## Slide 14

- IEEE NSS Refresher Course, Supplemental Materials

- Oct. 2007, Wu Jinyuan, Fermilab

## Triplet Finding

- Three data items must satisfy the condition: xA+ xC = 2 x**B**.
- A total of n3 combinations must be checked (e.g. 5x5x5=125).
- Three layers of loops if the process is implemented in software.
- Large silicon resource may be needed without careful planning: O(N2)

- Plane A

- Plane B

- Plane C

- IEEE NSS Refresher Course, Supplemental Materials

- Oct. 2007, Wu Jinyuan, Fermilab

## Block Diagram, Step 1

- IEEE NSS Refresher Course, Supplemental Materials

- Oct. 2007, Wu Jinyuan, Fermilab

## Block Diagram, Step 2

- IEEE NSS Refresher Course, Supplemental Materials

- Oct. 2007, Wu Jinyuan, Fermilab

## Circular Tracks from Collision Point on Cylindrical Detectors 

- For a given hit on layer 3, the coincident between a layer 2 and a layer 1 hit satisfying coincident map signifies a valid circular track.
- A track segment has 2 free parameters, i.e., a triplet.
- The coincident map is invariant of rotation.

- 1-3)+64

- 2-3)+64

- IEEE NSS Refresher Course, Supplemental Materials

- Oct. 2007, Wu Jinyuan, Fermilab

## Logarithmic Shifter

- S1

- S2

- S4

- # of bits: N
- Shift distance: L
- # of stages: log2L
- Total LE usage: N*log2L

- A shift of X bit of the bit pattern is done in one clock cycle rather than X cycles.
- Logarithmic shifter is also known as “barrel shifter”, but the term “logarithmic” reflects nature of implementation, resource usage and propagation delay better.

- IEEE NSS Refresher Course, Supplemental Materials

- Oct. 2007, Wu Jinyuan, Fermilab

## Logic Cell Usage

- Both 64- and 128-bit TTF designs fit $100 FPGA comfortably.
- A simple 64-bit Hough transform design is shown for scale.
- A $1200 FPGA is shown for scale.

**TTF64**

**TTF128**

**$100**

**$1200**

**Hough64**

- IEEE NSS Refresher Course, Supplemental Materials

- Oct. 2007, Wu Jinyuan, Fermilab

## Complex Triplet Finding Problems

- IEEE NSS Refresher Course, Supplemental Materials

- 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, Supplemental Materials

- Oct. 2007, Wu Jinyuan, Fermilab

## FPGA Process Sequencing Options

|  | Program
Type | Program
Length
(CLK cycles) | Reprogram | Resource
Usage |
| --- | --- | --- | --- | --- |
| Finite State Machine
(FSM) | Fixed
Wired | 10 | Hard | Small |
| Enclosed Loop Micro-Sequencer
(ELMS) | Memory
Stored
Program | 10-1000 | Easy | Small |
| Microprocessor
(MP)
 | Memory
Stored
Program | >1000 | Easy | Large |

- IEEE NSS Refresher Course, Supplemental Materials

- Oct. 2007, Wu Jinyuan, Fermilab

## The Between Counter

- 0,1,2,3,4,5,6,7,8,9,A

- 5,6,7,8,9,A

- 5,6,7,8,9,A

- 5,6,7,8,9,A

- 5,6,7,8,9,A

- 5,6,7,8,9,A,B,C,D,E,F...

- PC0: instr0
- PC1: instr1
- PC2: instr2
- PC3: instr3
- PC4: instr4
- PC5: instr5
- PC6: instr6
- PC7: instr7
- PC8: instr8
- PC9: instr9
- PCA: instrA
- PCB: instrB
- PCC: instrC
- PCD: instrD

- T

- ROM

- Between
- Counter

- Control
- Signals

- IEEE NSS Refresher Course, Supplemental Materials

- Oct. 2007, Wu Jinyuan, Fermilab

## ELMS – Detailed Block Diagram

- User
- Control
- Signals

- 	FOR	BckA1 EndA1 #n
- 	LD	R2, #addr_a
- 	LD	R3, #addr_X
- 	LD	R7, #0
- BckA1	LD	R4, (R2)
- 	INC	R2
- 	LD	R5, (R3)
- 	INC	R3
- 	MUL	R6, R4, R5
- EndA1	ADD	R7, R7, R6
- 	LD	R8, R7

- The Stack supports nested loops, up to 128 layers.

- IEEE NSS Refresher Course, Supplemental Materials

- Oct. 2007, Wu Jinyuan, Fermilab

## What’s Good About ELMSFOR Loops at Machine Code Level

- Looping sequence is known in this example before entering the loop.
- Regular micro-processor treat the sequence as unknown.
- ELMS supports FOR loops with pre-defined iterations at machine code level.
- Execution time is saved and micro-complexities (branch penalty, pipeline bubble, etc.) associated with conditional branches are avoided.

- 	LD	R1, #n
- 	LD	R2, #addr_a
- 	LD	R3, #addr_X
- 	LD	R7, #0
- BckA1	LD	R4, (R2)
- 	INC	R2
- 	LD	R5, (R3)
- 	INC	R3
- 	MUL	R6, R4, R5
- EndA1	ADD	R7, R7, R6
- 	DEC	R1
- 	BRNZ	BckA1

- 	FOR	BckA1 EndA1 #n
- 	LD	R2, #addr_a
- 	LD	R3, #addr_X
- 	LD	R7, #0
- BckA1	LD	R4, (R2)
- 	INC	R2
- 	LD	R5, (R3)
- 	INC	R3
- 	MUL	R6, R4, R5
- EndA1	ADD	R7, R7, R6

- 25%

- Microprocessor

- The ELMS

- Conditional Branch

- IEEE NSS Refresher Course, Supplemental Materials

- 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, Supplemental Materials

- Oct. 2007, Wu Jinyuan, Fermilab

## The Problem: 3 60Hz AC

- Rectify noise from power supply using  3-phase 60Hz AC are picked up by the input cable laying in the accelerator tunnel.

- Time Domain

- Frequency Domain

- IEEE NSS Refresher Course, Supplemental Materials

- Oct. 2007, Wu Jinyuan, Fermilab

## Filtering Results

- Noises >360Hz, the dominating portion, are filtered out in both filter functions.
- CIC sum is a lot smoother than the sliding sum.
- But small signals are still buried under ripples of 60 and 180 Hz.

*Sliding*
*Sum*

*CIC*
*Sum*

- IEEE NSS Refresher Course, Supplemental Materials

- Oct. 2007, Wu Jinyuan, Fermilab

## Recursive Implementation of CIC Sum

- The non-recursive
- implementation needs:
- 248 memory fetches,
- 248 multiplications,
- 248 additions and more ops for longer sum lengths.

- The CIC sum constructed
- as a sliding sum of sliding
- sums:
- 2 memory fetches,
- 0 multiplications,
- 4 add/sub ops for any sum length.

- The re-formulated CIC sum uses the raw data buffer rather than a separate buffer.

*CIC*
*Sum*

- IEEE NSS Refresher Course, Supplemental Materials

- Oct. 2007, Wu Jinyuan, Fermilab

## Exponential Sequence Generator

- 

- Q

- SET

- D

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

- This is also an example of recursive structure.
- This is IIR but it is stable.
- Dropping exponential components are used to stabilize other recursive structures.

- IEEE NSS Refresher Course, Supplemental Materials

- Oct. 2007, Wu Jinyuan, Fermilab

## The EndThanks

- IEEE NSS Refresher Course, Supplemental Materials

- Oct. 2007, Wu Jinyuan, Fermilab