EM Algorithm Proposal 1

updated: 26-Oct-04

Summary

An ATLAS-style 2,0,1 algorithm will be used.
EM Isolation and EM/HAD Fraction information are included as an extra output bit for each of the 16 EM objects in a SW chip.
A brief description of the steps in the algorithm
The SW chip output is expanded to include the Isolation/EM-Fraction information using spare lines.
The TAB-to-GAB output also changes to accomodate the isolation information.
Examples of the use of Isolation in the And/Or terms (soon).
Here are a list of aspects of the algorithm about which there is still uncertainty
Numbering Convention for data in Sliding Windows Chips.
Note: each cell in the grid is can also be referenced by its (eta,phi) coordinates within the chip.
- eta = 0 - 8
- phi = 0 - 8
An older EM Algorithm proposal (21-Oct-04)

ATLAS-Style Algorithm

The algorithm described below is a variant of the 2,0,1 algorithm. Using 2x2 windows of TTs as the base, the algorithm checks for Local Maxima of Et in two possible ROIs within the 2x2 region as shown below.

o

x o

  Vertical: 1x2 ROI or
  Horizontal: 2x1 ROI

LM Finding

Local Maxima are found on a 3x3 grid of ROIs (this is different than the Jet algorithm which needs 5x5). The comparison grid in ROI-space for both horizontal and vertical ROIs (i.e. 1 cell per ROI) is shown below, with the ROI in question marked as yellow.

>= > >

>= x >

>= >= >=

Smallest Separation of LMs

Local Maxima (LM) can be found in two contiguous 2x2 base ROIs. In the diagrams below the following conventions are used.

The data seen by a single Sliding Windows chip is shown on a grid.
The main LM is shown in yellow, with its labeling TT marked with an "x".
The TTs used in the 2x2 base ROI are marked with an "r".
The TTs required to find the LM are marked with an "o" (unless this has been overwritten with an r or x).
Some of the nearest possible adjacent LMs are shown in cyan.

Vertical LM
^ \| \| phi	08
	07
	06				r	r
	05			o	x	o
	04		r	r	r	r	r	r
	03		x	r	x	r	x	r
	02			o	r	r
	01				x	r
	00
		00	01	02	03	04	05	06	07	08
		eta -->

Horizontal LM
^ \| \| phi	08
	07
	06				r	r
	05			o	x	r
	04		r	r	r	r	r	r
	03		x	r	x	r	x	r
	02			o	r	r
	01				x	r
	00
		00	01	02	03	04	05	06	07	08
		eta -->

EM-Isolation and EM/HAD Fraction

EM Isolation and the EM/HAD fraction is also calculated for horizontal and vertical ROIs.

EM Isolation

Isolation is calculated using EM TTs on either side of the ROI as illustrated below.

The ROI TTs are marked in yellow.
The TTs used for isolation are marked in cyan and labeled by numbers.

^
|
|
phi 04

03 2 o 4 3 4

02 1 x 3 x o

01 1 2

00

00 01 02 03 04 05 06 07 08

eta -->

The cut used is: Et(ROI) > 2^a Sum(1+2+3+4)
where a is a downloadable parameter that is the same for all thresholds and for all regions of the calorimeter.

EM/HAD Fraction

The EM/HAD fraction is calculated using the 3x3 HAD TTs behind the EM ROI and centered on the ROI anchor point.

EM TTs used in the ROI are marked with "x" and "o".
HAD TTs used in the calculation of the HAD region are marked in red and labeled with "." (unless already labeled with x or o).

^ \| \| phi	04
	03	.	o	.			.	.	.
	02	.	x	.			.	x	o
	01	.	.	.			.	.	.
	00
		00	01	02	03	04	05	06	07	08
	eta -->

The cut used is: Et(ROI) > 2^b HAD(3x3)
where b is a downloadable parameter that is the same for all thresholds and for all regions of the calorimeter.

Algorithm Flow

Steps in the algorithm are described in the table below. In the table

Horizontal refers to the branch of the algorithm that considers 2x1 ROIs in eta x phi
Vertical refers to the branch of the algorithm that considers 1x2 ROIs in eta x phi
Object Size refers to the eta x phi region used to make the object described
SW Inputs refers to the eta x phi region in the SW chip that is required to perform this step for all objects in the chip.

Horizontal Vertical

Step Description Object Size SW Inputs Object Size SW Inputs

1 Add ICR 1 TT as needed 1 TT as needed

2.a ROI Sums 2x1 TTS:
0-8 x 0-7 1x2 TTS:
0-7 x 0-8

2.b EM Iso Sums 2 (3x1) ROIs:
2-5 x 2-5 2 (1x3) ROIs:
2-5 x 2-5

2.c HAD Sums 3x3 ROIs:
2-5 x 2-5 3x13 ROIs:
2-5 x 2-5

3 ROI Compares 2x1 ROIs:
0-8 x 0-7 1x2 ROIs:
0-7 x 0-8

4.a EM Iso
LM > 2^a*Iso 2x1 ROIs:
2-5 x 2-5 1x2 ROIs:
2-5 x 2-5

4.b EM Frac
LM > 2^b*HAD 2x1 ROIs:
2-5 x 2-5 1x2 ROIs:
2-5 x 2-5

5 AND Iso & EM Frac 1-bit 2-5 x 2-5 1-bit 2-5 x 2-5

6 Find Highest Thresh Passed 3-bits 2-5 x 2-5 3-bits 2-5 x 2-5

7 Choose H or V ROIs: 2-5 x 2-5

8 Make Output Words
(Thresh & Iso) EM: 2-5 x 2-5

Rules for Choosing Horizontal or Vertical Objects

Note: making this choice does not use an entire bunch crossing worth of latency (as previously assumed). It only takes one 90 MHz clock tick to choose which of the H or V threshold words to write to the output word.

Rules for making the choice are given below.

For a given 2x2 region, if only one of the H or V ROIs produces a LM then choose that one.
If both H and V LMs exist, choose the one with the highest Et.
If Et(H) = Et(V) then consider the region to be Horizontal (needs to be discussed).
The Isolation bit corresponding to the H or V ROI chosen is output.

An important question is at what point in the algorithm to choose between the Horizontal and Vertical ROIs in a given 2x2 region. It turns out that latency is minimized if the choice is made just before writing threshold words for each ROI to the output word. So that is what we have decided on.

The following are also possible, but would cost a full BC in latency, and therefore disfavored.

Choose after step 2 based on rules 1 and 2 above. highest Et.
Choose the H or V LM remaining after step 3, or if both H and V LMs exist for a 2x2 region, use rules 1 and 2 above.

Constructing the SW Chip Output

The current SW chip outputs are described here. Briefly, a 3-bit word is used, for each of the 4x4 EM objects sent out from a SW chip, to indicate the highest threshold that was passed by that object. Consequences of this scheme are described here

In the new scheme, each of the 16 EM objects sent out by the SW chips has two types of output words associated with it.

3 bits: The highest of 7 Et thresholds passed by the object, without any requirements on EM-Isolation or EM/HAD fraction.
This information is passed in the currently existing EM words.
1 bit: The AND of EM-Isolation and EM/HAD-Fraction cuts on each object described above.
This information is passed as 16 bits in the spare lines.

The proposed form of the new SW chip output is shown here.

Constructing the TAB Output

Because of the new EM-Isolation bits, the TAB output has to change as well. The current TAB-to-GAB output is described here.

The new algorithm will pack one of the spare TAB-to-GAB lines with Isolation bits. For each eta-region sent out of the TAB (S,N,C) and for each phi (2,3,4,5) the corresponding bit in the output word will be set if any EM object in that eta-region passes the EM-Isolation and EM/HAD-Fraction cuts.

The EM information output from the TAB is then.

12, 12-bit words: (phi=2,3,4,5 x eta=S,C,N).
Each word contains six 2-bit counts of the number of EM objects that are found at for each of 6 Et thresholds (no isolation requirement) in that phi,eta-region.
3, 12-bit (4b used) words: (eta=S,C,N)
Each word uses 1 bit (0-3) for each of the four phi's in the eta-region considered. That bit is 1 if there is any EM object in the eta,phi-region that passes the EM-Isolation and EM/HAD-Fraction cuts.

A proposed form of the new TAB output is shown here.

Uncertainties in the Above Specification

Thresholds

Issues related to the thresholds are discussed here. In this proposal, Et and isolation information are separate. There are thus no problems related to the fact that we send only the highest threshold passed from the SW chips to the Global chip on the TAB.

Threshold usage is summarized below.

Type Thresholds avail inside TAB Thresholds avail inside GAB

Et Information 7
sent as highest threshold passed for each object in TAB 6
sent as 2-bit counts at each phi=0-31 for eta-regions=S,C,N

Isolation & EM-Fraction 1
1 criterion for all Et thresholds for each EM object in TAB 1
1 criterion for all Et thresholds ORed over all EM obects in the eta-region, for each phi=0-31

Single TT Algorithm

It may be necessary to include triggers based on single TTs into the EM list. A description of an algorithm can be found here.

EM-Isolation and EM/HAD-Fraction

We also need to decide on the geometry of both of these regions. Some possibilities are given below.

Combine Isolation and EM-Fraction:
This would use all the EM (7) and HAD (9) TTs in a 3x3 region centered on the ROI (except for the TTs participating in the ROI). The cut would be.
- EM(ROI) > 2^c [EM(7) + HAD(9)]
Different EM-Isolation Region Definitions Some possibilities are:
- The "U" shaped region surrounding the ROI.
- Use a 4x4 ring for both H and V ROIs
- Use a 4x3 (H) or 3x4 (V) ring for H and V ROIs

		Horizontal		Vertical
Step	Description	Object Size	SW Inputs	Object Size	SW Inputs
1	Add ICR	1 TT	as needed	1 TT	as needed
2.a	ROI Sums	2x1	TTS: 0-8 x 0-7	1x2	TTS: 0-7 x 0-8
2.b	EM Iso Sums	2 (3x1)	ROIs: 2-5 x 2-5	2 (1x3)	ROIs: 2-5 x 2-5
2.c	HAD Sums	3x3	ROIs: 2-5 x 2-5	3x13	ROIs: 2-5 x 2-5
3	ROI Compares	2x1	ROIs: 0-8 x 0-7	1x2	ROIs: 0-7 x 0-8
4.a	EM Iso LM > 2^a*Iso	2x1	ROIs: 2-5 x 2-5	1x2	ROIs: 2-5 x 2-5
4.b	EM Frac LM > 2^b*HAD	2x1	ROIs: 2-5 x 2-5	1x2	ROIs: 2-5 x 2-5
5	AND Iso & EM Frac	1-bit	2-5 x 2-5	1-bit	2-5 x 2-5
6	Find Highest Thresh Passed	3-bits	2-5 x 2-5	3-bits	2-5 x 2-5
7	Choose H or V	ROIs: 2-5 x 2-5
8	Make Output Words (Thresh & Iso)	EM: 2-5 x 2-5

Type	Thresholds avail inside TAB	Thresholds avail inside GAB
Et Information	7 sent as highest threshold passed for each object in TAB	6 sent as 2-bit counts at each phi=0-31 for eta-regions=S,C,N
Isolation & EM-Fraction	1 1 criterion for all Et thresholds for each EM object in TAB	1 1 criterion for all Et thresholds ORed over all EM obects in the eta-region, for each phi=0-31