# Presentation: 279706

## Tiny Triplet Finder

- Jinyuan Wu, Z. Shi
- Dec. 2003

## Hits, Hit Data & Triplets

- Hit data come out of the detector planes in random order.
- Hit data from 3 planes generated by same particle tracks are organized together to form triplets.

## 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.

- Plane A

- Plane B

- Plane C

## Tiny Triplet Finder (Animation)

- x1

- x2

- x3

- Implement x1 and x3, the plane x2 is for eye-guide only.

- (1) Fill in hits to x1 and x3 planes.

- (2) Cycle through x2 hits.

- Line matched.

## Tiny Triplet Finder

- Bit Array/Shifter C

- Bit Array/Shifter A

- Bit-wise Logic Block

- Hash Sorter C

- Hash Sorter A

## TTF OperationsPhase I: Filling Bit Arrays

**Note: Flipped Bit Order**

- Physical Planes

- Bit Array/Shifters

**For any hit...**

**Fill a corresponding logic cell.**

- xA+ xC = 2 x**B**
- xA= - xC + constant

## TTF Operations Phase II: Making Match

**For any center plane hit...**

**Logically shift the bit array.**

**Perform bit-wise AND in this range.**

**Triplet is found.**

- Physical Planes

- Bit Array/Shifters

## TTF Operations Phase II: Making Match (Next Hit)

**Triplet is found through bit-wise AND.**

**Fake triplet may exist. It will be cut out in the later stages.**

- Physical Planes

**Loop to next center plane hit...**

**Logically shift the bit array.**

- Bit Array/Shifters

## TTF OperationsPhase II: Making Match (More...)

- Physical Planes

**Loop to next center plane hit...**

**Logically shift the bit array.**

**Triplet is found through bit-wise AND.**

- Bit Array/Shifters

## TTF Operations Phase II: Making Match (and More...)

- Physical Planes

**Loop to next center plane hit...**

**Logically shift the bit array.**

**Triplet is found through bit-wise AND.**

- Bit Array/Shifters

## TTF Operations Phase II: Making Match (Last Hit)

- Physical Planes

**Loop to next center plane hit...**

**Logically shift the bit array.**

**Triplet is found through bit-wise AND.**

- Bit Array/Shifters

## Multiple Hits & TripletsKeep Them All

- Each bin may be filled with more than one hits.
- Hits data are kept in hash sorters – allowing multiple hits per bin.
- There are may be more than one match in each bit-wise AND operation.
- They are all sent out, one-by-one, to the later stages for fine cut and arbitration processes.

## Boundary IssuesBeyond Just Bit-wise AND

- When the track hits near the boundary of a bin, simple bit-wise AND may miss the triplet.
- The bit-wise OR-AND logic will cover the boundary.
- The logic cells in most of today’s FPGA’s have 4 inputs.  So the OR-AND bit-wise logic doesn’t increase any resource usage.

## Tiny Triplet Finder: Block Diagram

- BitLogic

- KA

- XB

- EN

- C

- KC

- Pop

- Halt

- A

- 172 LUT
-  FF

- 92 LUT
-  FF

- 192 LUT
- 111 FF

- 77 LUT
- 66 FF

- 77 LUT
- 66 FF

- Tiny Triplet Finder: *Block Diagram*

## Schematics

## Simulation

- (1) Filling hits on Plane A and C.

- (2) Looping over hits on Plane B.

- Pipelined internal operations...

- Triplets are grouped together.

- This combination is a fake triplet.

- The extra combination halts the pipeline for proper operation.

## 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.

## Pentlet FindingBeyond Just Bit-wise AND

- Use 4 bit arrays.
- There are 3 constraints total.
- More constraints help to eliminating fake tracks.
- It is possible to use bit-wise majority logic (such as 3-out-of-4) to accommodate detector inefficiency issues.

- Pentlet Finding*Beyond Just Bit-wise AND*

- Plane A

- Plane C

- Plane E

- Plane B

- Plane D

## Comparison of Baseline and Tiny Triplet Finder: Data Flow

**FIFO**

**AM: **
**Long Doublet**

**FIFO**

**Station N-1**
**bend**

**Station N-1**
**Non-bend**

**Station N**
**Non-bend**

**FIFO**

**AM: **
**Triplet**

**FIFO**

**FIFO**

**FIFO**

**FIFO**

**FIFO**

**FIFO**

**AM: **
**Short Doublet**

**FIFO**

**AM: **
**Short Doublet**

**AM: **
**Short Doublet**

**Station N**
**bend**

**Station N+1**
**bend**

**Station N+1**
**Non-bend**

**Station N-1**
**bend**

**Station N-1**
**Non-bend**

**Station N**
**Non-bend**

**FIFO**

**FTF: **
**Triplet**

**FIFO**

**FIFO**

**FIFO**

**FIFO**

**FIFO**

**FIFO**

**FIFO**

**Hash Sorter: **
**Short Doublet**

**Station N**
**bend**

**Station N+1**
**bend**

**Station N+1**
**Non-bend**

**FIFO**

**Hash Sorter: **
**Short Doublet**

**Hash Sorter: **
**Short Doublet**

**Hash**
**Sorter**

**Hash**
**Sorter**

## The End

- Thanks

## Short Doublet Stage: 1 of 3 Identical Ones

- 77 LUT
- 66 FF

- Short Doublet Stage: *1 of 3 Identical Ones*

**Station N-1**
**Non-bend**

**FIFO**

**FIFO**

**Hash Sorter: **
**Short Doublet**

- Triplets In

- Triplets Out

- E

- P

- StnID

- HitMap

- y2y (8+3bits)

- x1x (8+3bits)

- y1(400u)

- y1y (8+3bits)

- x1(400u)

- y3y (8+3bits)

- H

- E

- P

- StnID

- HitMap

- y2y (8+3bits)

- y1y (8+3bits)

- y3y (8+3bits)

- H

- x1y (7bits)

- x2y (7bits)

- x3y (7bits)

- x2y (7bits)

- x3y (7bits)

## Hash Sorter: Vertex-II Implementation

- K(8:0)

- DI(27:0)

- DOB(27:0)

- IdN(7:0)

- RDY

- MD

- PUSH

- POP

- WT

- REPOP

- DUMPD

- SR

- CLK

- POPQ

- PUSHQ

- DIQ(27:0)

- IdP(7:0)

- IdQ(7:0)

- IdK(7:0)

- IdKQ(7:0)

- EVeq

- EV(9:0)

- EV(8:0)

- Vertex II Implementation

- Hash Sorter: *Vertex-II Implementation*

## Hash Sorter: Cyclone Implementation

- K(7:0)

- DI(28:0)

- DOB(28:0)

- IdN(6:0)

- RDY

- MD

- PUSH

- POP

- WT

- REPOP

- DUMPD

- SR

- CLK

- POPQ

- PUSHQ

- DIQ(28:0)

- IdP(6:0)

- IdQ(6:0)

- IdK(6:0)

- IdKQ(6:0)

- EVeq

- EV(8:0)

- EV(7:0)

- Cyclone Implementation

- Hash Sorter: *Cyclone Implementation*

## Bit Array/shifterXILINX Implementation

- Each Bit Array/Shifter has 64 bins.
- Each bin is a 16-bit RAM (look-up table).
- The RAM operates like a D Flip-flop.
- Each xc2v1000 FPGA has 10,240 such RAM’s.

## Bit Array/shifterFilling the Hits

- Each hit is written into 8 to 16 different RAM’s with different addresses.
- One clock cycle (not 8 to 16) is used to fill a hit.

## Bit Array/shifterShift Reading

- With given addresses of the RAM’s, hit patterns appear at the outputs of the arrays.
- Changing addresses shifts the hit patterns.
- One array shifts in unit of 1 bin, the other in unit of 8 bins.
- The relative shift of the two patterns covers 128 bins.
- One clock cycle is used for a reading, regardless the distance of the relative shifting.

## Bit Array/shifterComments: Xilinx or Not

- Writing/reading operations need only single clock cycle. 
- Storage and shifter are combined — big resource saving. 
- Maximum 16 clock cycles are needed for resetting. 
- Non-xilinx implementation:  Additional 64x8=512 LE’s may be needed.   But resetting needs only one clock cycle. 

## Challenge on Triplet Finding (1)The Facts in “Road” Language

- With two hits in two planes, two parameters can be determined.  The 3rd hit in the 3rd plane will provide the first constraint.
- Assume each parameter is sliced into 64 bins.  (That’s not too many.)
- There are 64 x 64 = 4096 “roads”, i.e., possible track configurations.
- Any hit can belong to 64 possible roads.  Two hits in two planes have one common road.  Three hits must have one common road to be in a triplet.

- Challenge on Triplet Finding (1)*The Facts in “Road” Language*

## Challenge on Triplet Finding (2)A Possible Implementation Using CAM

- Hit patterns are pre-stored in CAM.
- When a hit pattern match the pre-stored one, the address represent the road.
- Each of 3 planes has 64 possible hit locations.  (64x64=4096 roads)
- Assume one road can generate one hit pattern,  a CAM array with 64x3=192 input bits, 4096 words is needed.
- It can be done with 128 small CAM’s (32-bit 32-words).  EPC20K1000E has 160. (80%)
- Oops: boundary issues have not be considered.  (More patterns  )

- Challenge on Triplet Finding (2)*A Possible Implementation Using CAM*

- Plane A

- Plane B

- Plane C

- Road

## Challenge on Triplet Finding (3)A Possible Implementation Using Hough Transformation

- Each hit from plane A, C or B increments the counts of the 64 bins in a row, column or diagonal.
- The bins with count 3 are valid triplet roads.
- Each histogram bin is a counter plus selection logic.
- Assume each bin can be implemented with 4 Altera logic elements (LE’s).
- 4096 bins need 16,384 LE’s,  EPC20K1000E has 38,400. (16,384/38,400 = 43%)
- However:  How to find the bins with count 3 and encode them is not trivial.

- Challenge on Triplet Finding (3)*A Possible Implementation Using Hough Transformation*

## Silicon Usage (Estimate)

- The Tiny Triplet Finder (TTF) silicon usage is acceptable.
- The hash sorter silicon usage is acceptable.
- The Baseline, if not implemented automatically, could reduce the size a lot.

## NBin

- DI

- DOB

- IdNext

## Slide 33

## 0

- 5

- 6

- 1

- 2

- 3

- 1

- 5

- 6

- 1

- 2

- 3

- 1

- 2

- 5

- 6

- 1

- 2

- 3

- 1

- 2

- 3

- 5

- 6

- 1

- 2

- 3

- 4

- 1

- 2

- 3

- 5

- 6

- 1

- 2

- 3

- 4

- 5

- 1

- 2

- 3

- 5

- 6

- 1

- 2

- 3

- 4

- 5

- 6

- 1

- 2

- 3

- 5

- 6

- 1

- 2

- 3

- 4

- 5

- 6

- 7

- 1

- 2

- 3

- 5

- 6

- 1

- 2

- 3

- 4

- 4

- 4’

- 4’

- 4

- 4

- 4

- 4

- 7

- 4’

- 4’

- 4’

- 7

- 7

- 7

- 7

- 4

- 4

- 7

- 7

- 7

- 4’

- 4’

- 4’

## 4

- 5

- 6

- 7

- 0

- 1

- 2

- 3

- 5

- 6

- 7

- 0

- 1

- 2

- 3

- 5

- 6

- 7

- 1

- 2

- 3

- 5

- 6

- 7

- 0

- 1

- 2

- 3

- 5

- 6

- 7

- 2

- 3

- 5

- 6

- 7

- 0

- 1

- 2

- 3

- 5

- 6

- 7

- 3

- 5

- 6

- 7

- 0

- 1

- 2

- 3

- 5

- 6

- 7

- 5

- 6

- 7

- 0

- 1

- 2

- 3

- 5

- 6

- 7

- 5

- 6

- 7

- 0

- 1

- 2

- 3

- 6

- 7

- 5

- 6

- 7

- 0

- 1

- 2

- 3

- 7

- 5

- 6

- 7

- 0

- 1

- 2

- 3

- 4’

- 4’

- 4’

- 4’

- 4’

- 4’

- 4’

- 4’