Sgutil

SGLIB/SGUTIL package contains Dave Haddle's noise reduction software with segment finding extensions. It resides in $CODA/src/codatt/sgutil.c and is called from $CLON/src/cmon/prlib/sglib.c.

SGLIB contains following functions:

• sginit() - must be called once at initialization stage; creates differencial shift table and fills lookup tables

• sgtrigger() - works for specified sector; return 0 if sector does not have required track information, otherwise returns the number of superlayers with segments; calls function RemoveNoise() from SGUTIL

• sgremovenoise() - works for specified sector; rewrites all DC banks removing single hits; calls function RemoveNoise() from SGUTIL

• sglib() - find segments for one sector; three options can be specified: noise removing only, segment finding only, noise removing and then segment finding; calls functions RemoveNoise(), SegmentSearch128() and SegmentSearch192() from SGUTIL

• sgprint() - print results for one sector

• sgroad() - fill road finding structures, SWAPING region 1

SGUTIL contains following functions:

• BinaryPrint32(), PrintWord192(), CopyWord192(), ANDWord192(), ORWord192(), XORWord192(), CheckBitWord192(), SetBitWord192(), ClearWord192(), NegateWord192(), BleedRightWord192(), BleedLeftWord192() - functions for 192-bit words operations

• RightShiftWord192(), LeftShiftWord192(), RIGHTSHIFT(), RightShiftWord192_00(), RightShiftWord192_01(), RightShiftWord192_02(), RightShiftWord192_03(), LEFTSHIFT(), LeftShiftWord192_00(), LeftShiftWord192_01(), LeftShiftWord192_02(), LeftShiftWord192_03() - macroses for 192-bit words operations

• RemoveNoise() - works for one superlayer, removes single hits; it is very much the same as original Dave's program, with some optimization; it returns 0 if nothing left after single hits removing, or 1 otherwise

• SuperLayerSum() - used by RemoveNoise() only; does fast summing of the 6 192-bit words following algorithm suggested by Pavel Degtiarenko; output is the 192-bit word where every bit contains result of the summing of the corresponding 6-bit vertical column

ALGORITHMS DESCRIPTION

Example can be found here.

192-bit words were summed using binary numbers adding procedure. As it was suggested by Pavel Degtyarenko, following adding procedure was used to get a sum of 6 192-bit words representing 6 layers of the Drift Chamber superlayer. This method was used in SuperLayerSum/RemoveNoise procedure to found areas with segments, and in the first stage of SegmentSearch192 procedure. Here is the fragment of the binary summing program:

   b1 = (w0)&(w1);
   b0 = (w0)^(w1);
   b1 = (b1)^((b0)&(w2));
   b0 = (b0)^(w2);
   tmp = (b0)&(w3);
   b2 = (b1)&tmp;
   b1 = (b1)^tmp;
   b0 = (b0)^(w3);
   tmp = (b0)&(w4);
   b2 = (b2)^((b1)&tmp);
   b1 = (b1)^tmp;
   b0 = (b0)^(w4);
   tmp = (b0)&(w5);
   b2 = (b2)^((b1)&tmp);
   b1 = (b1)^tmp;
   b0 = (b0)^(w5);

SegmentSearch192 searches for segments in 3 steps. On the first step shift-and-sum operation is performed separately for axial and stereo superlayers. Results are stored in 3 192-bit words, where vertical 3-bit columns contains the number of hits. Using lookup tables those numbers are converted into integers to be used on following step.

On second step one of the superlayers is shifted against another one, search is conducted for the region-based segments, and list of segment candidates is produced.

On the third step segment list is processed to select the segment with the maximum number of hits, and final list of segments is created.

SegmentSearch192 calls 4 macros:

TWOSLPROCESS(192):

• input: superlayer data in a form of 6 192-bit words (layers); dshift table
• action: loop over NSHIFT shifts, shifting layers in according to dshift table, binary summing 6 layers, store results in 3 192-bit words, convert bit sums to integer sums using '3 layers 4 bits' lookup table method
• output: char tmp1[NSHIFT][192] (superlayer1) and char tmp2[NSHIFT][192] (superlayer2) - the number of hits for every wire and every shift

REGIONPROCESS(192):

• input: tmp1[NSHIFT][192] and tmp2[NSHIFT][192] from previous macro
• action: loop over NSHIFT shifts, nested loop over superlayer-to-superlayer shift
• output: list of region-based segments:

PEAKSEARCH(192):

SEGMENTLIST(192):

NIM paper draft

Described approach was used to search for the track segments. Track segments search is the first stage of the pattern recognition process (second stage is road finding) which is part of level 3 (software) trigger, as well as online event reconstruction software.

The segment finding process can be explained using data sample shown on fig.1. Drift chamber consists of 3 regions, each contains axial and stereo superlayers. Track segment inside the region can be considered as straight line, so program is looking for the segments with the same slope in both superlayers. Segments in 2 superlayers can be spaced few wires from each other due to the phi angle of the track, which creates another degree of freedom.

Noise removal is usually running first to cleanup data as much as possible. Red color hits on fig.1 will be removed at that point.

Segment search is conducted in 3 steps. On the first step shift-and-sum operation is performed separately for axial and stereo superlayers for the set of shift patterns representing different track segment angles from +30 to -30 degrees approximately. In our example (as it shown on fig.2) shift pattern was (0,0,1,1,1) for layers 2 through 6, which means layers 4,5 and 6 were shifted one step to the left. After every shift, 192-bit words were summed using binary numbers adding procedure as it was suggested by Pavel Degtyarenko (fig.3). Results are stored in 3 192-bit words, where vertical 3-bit columns contains the number of hits in binary format. Using 3x8 lookup tables those numbers are converted into integers stored in 192-dim arrays. Those arrays will be used on the following steps (fig.2). Only segments with the number of hits above threshold are kept. As it was found threshold equal to 4 is the best from both segment search efficiency and execution time prospectives. However because of significant number of the 'dead' wires in some areas that threshold must be set to 3, which increases significantly the number of segment candidates and execution time per event. One way to address the issue would be to convert 'dead' wires into 'hot' wires assigning hits to them permanently, but it is not the part of existing procedure.

On the second step one of the superlayers is shifted against another one, search is conducted for the region-based segments, and list of segment candidates is produced. Another threshold has been applied to the region-based segments, usually minimum 8 hits were required. Again, threshold was lowered later because of 'dead' wires to burst segment search efficiency. As soon as threshold is decreased, the length of the segment list grows significantly, and execution time come with it.

On the third step segment list is processed to select the segment with the maximum number of hits, and final list of region-based segments is created. Every segment in the list contains participated wire numbers, the slope and the shift between superlayers (latest value represents the phi angle of the track). If thresholds are reasonably high (4 and 8 for superlayer and region respectively) then the list will be short, for our example (fig.2) only one region-based segment will be reported as following: axial wire numbers are 66,66,0,0,65,65; stereo wire numbers are 70,70,0,69,0,69; slope 33; phi 17 (slope and phi are reported as an corresponding table indexes).

It takes an average few hundreds of microseconds on regular PC to process segment finding for one event with the efficiency of 96-98%. To get remaining few percent thresholds must be lowered which leads to the significant increase of both the execution time and the number of segment candidates. As result following road finding procedure must deal with the huge number of combinations which increases execution time even more. In general drift chamber inefficiency was the biggest challenge for the speed of the presented approach. It was used successfully in online reconstruction where some inefficiency is allowed, however in the level 3 (software) trigger it was running in tagging mode only.

There is a plan to use described approach in upcoming CLAS12 Trigger System as FPGA-based implementation, where in can be executed much fasted. We hope to address 'dead' wired issue and develop fast and efficient component of the Level 1 (hardware) trigger.