**Associative memory for track finding.** Update 27-Jul-99 D. Husby

I\'ve run some further simulations for my associative memory track
finder using a data file provided by Mike Procario. The file contains
996 events with a mix of minimum-bias events and B events. The station
spacing is 40 mm. The plane spacing is 4 mm. The file was "pixelated" to
reflect a pixel size of 50 x 400 with a resolution of 10 x 400.

My simulations are mostly concerned with measuring data flow. Data flow
is probably the most difficult problem to solve for this part of the
trigger. Without extreme effort, data rates between individual modules
are limited to 200 to 400 MBytes/Sec unidirectional. 400 MB/S
corresponds to a 32-bit bus cycling at 100MHz.

Global data rates are more of a problem. When data must be shared among
many modules, or must be collected from all modules, the requirements
can get very high. In addition, since the modules are working
independently, data must be sorted by timestamp in order to insure that
each module operates on the proper event. This requires a smart
switching network of the type used in the baseline triplet trigger. Each
of its processing farms is capable of accepting data from 32 sources,
sorting it by timestamp, and delivering it to one of 192 buffers in 64
processors. It can sustain a data rate of 800 MB/S. With a little
additional effort, this type of network can be pushed to 6400 MB/S.

My simulation also includes some measures of physics performance. I
measure how well found doublets and tracks correspond to real HEP
tracks. We\'ll have to wait until the algorithm can be incorporated into
the triggering simulations to determine how effective it is for physics.

Here are my results:

**[Hits:]{.underline}**

The average number of hits per station-quadrant is 5.53. This equates to
\~366 Megabytes/Sec into each doublet finder.

366 MB/S = (5.53 Hits/Event + 1 timestamp/Event) \* 7 MHz \* 2
planes/station \* 4 bytes/Hit

**[Doublets:]{.underline}**

Doublets are found by choosing a hit in one plane and finding all hits
in the second plane that fall within 4000 microns in both X and Y. The
4000 micron window is adjustable, and corresponds to tracks with a slope
less than 1.

For the best case, the average number of doublets generated per
station-quadrant is 5.28. This corresponds to \~352 MB/Sec. In addition
to doublet rate, I measured two other paramters:

**Bad** doublets are those that aren\'t really on a track. They're
generated when two tracks are close enough that plane hits from one
track fall within the search window of the other track.

**Good** doublets are doublets that are on a real track, but were not
found. These tracks have slopes that are steeper than the search window.

I also try two variations on the algorithm:

**RejectUsed**: This rejects a doublet if it has a steep slope and one
of its plane hits has already been used to form a doublet. This helps in
the case where two parallel tracks are near each other, but will tend to
favor smaller slopes when, perhaps, it shouldn\'t. The effect is also
dependent on data ordering.

In the tables, a RejectUsed value of 4000 correponds to no rejection,
while a value of 1000 will reject doublets that have a slope greater
than ¼. The RejectUsed feature seems to eliminate a significant number
of bad doublets without significantly increasing the loss of good
doublets.

**ConvertUnused**: This converts a plane hit into a doublet if it isn\'t
part of another doublet. This is intended to deal with pixel
inefficiencies. Unfortunately, it also increases the effect of noise
hits. The ConvertUnused feature adds about 1 extra doublet per station.

**[Tracks:]{.underline}**

Tracks are found from left to right by matching a station doublet to a
partial track. Doublets that match are added to the track and projected
to the next station. Doublets that do not match a track are sent to the
next station as the start of a new track. Match window sizes are
determined by pixel geometry, scattering, and curvature. For the first
match of a track, a 4100µ x 4100µ window is used. This roughly
corresponds to the coarse pixel resolution (400µ) times the ratio of
station spacing to plane spacing (40/4). For each additional match, a
window of 500µ x 4000µ is used. The X window size (500µ) is dominated by
scattering. The size of the Y window is dominated by curvature. (Note
that by 'window' I mean the distance from center to edge.) See figures
3, 4, and 5 for measured window sizes.

I tried a variation of the algorithm that uses the curvature of the
track when predicting the next station hit. This had almost no effect on
performance (see Table 2). I don't understand why, but it probably has
something to do with the fact that very curvy tracks also have a lot of
scattering. Table 3 shows that using curvature, 59.6 percent of the
doublets fall within 250 microns of their predicted position. Not using
curvature, 57 percent are within 250 microns of the prediction. With a
window size of 3100 microns, the two cases are almost identical.

For the best case, there were an average of 5.62 tracks per
station-quadrant. This corresponds to a data rate of about 433 MB/S.

**[Track Ends]{.underline}**

Track ends are emitted when the first three or last three hits of a
track are found. The best case generated 1.7 track ends per station.
Since all of the track ends must be gathered into a single processor,
this represents a global data rate of \~4430 megabytes per second per
quadrant. Such a high data rate will probably require a 2-level
processing farm to handle all 4 quadrants. The first level can handle
quadrants independently, trim down the data, and pass only
vertex-specific data to a vertex farm, while saving the rest of the
track data for triggered readout.

Figure 2 shows a single event including track ends circled in blue.
Track ends include 3 hits unless the track evaporates before leaving the
pixel array B . The yellow lines represent predicted station hits.
Purple lines represent a prediction after a station miss A . Green lines
connect plane hits that form good doublets. Red lines connect plane hits
that form bad doublets C .

**[Track Windows]{.underline}**

Figures 3, 4, and 5 are histograms of window sizes.

Figure 3 shows that all but 2% of hits in a doublet are within 4000
microns of each other.

Figure 4 shows that 90% of all first track hits are within 4100 microns
of their predictions.

Figure 5 shows that 90% of other track hits are within 500 microns of
their predicted X position and 3000 microns of their predicted Y
position.

![](media/image1.png)