{'fraction_non_alphanumeric': 0.027558277360726986, 'fraction_numerical': 0.015260766495456341, 'mean_word_length': 4.637249443207127, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Local reconstruction software for the CMS silicon strip tracker

CMS has a two level trigger system. The first stage is hardware based and provides fast trigger decisions up to a rate 100 kHz. The second stage, known as the High-Level Trigger, is entirely software based and required to provide a trigger decision within 40 ms and a rejection factor of a thousand to achieve a write-to-disk rate of 100 Hz. One of the most CPU-intensive tasks within the High-Level Trigger is the reconstruction of tracking hits using raw data from the strip tracker. This study profiles the performance of these reconstruction algorithms. Even at low luminosities, the average processing time is 5.5 s, which already exceeds the HLT budget. A new schema, optimised for speed and performance, has been developed to reconstruct hits within regions-of-interest only. For the entire sub-detector, hit reconstruction times are reduced to 140 ms. Since only 10 % of High-Level Trigger events are expected to require track reconstruction, the average contribution per event is then ∼14 ms i.e. 30 % of the full budget. Regional reconstruction is tested over Z0 → e+e− events, by unpacking in η-ϕ windows of 0.16 × 0.16 around seeds identified in the calorimeter. In this case, only 2 ± 1 % of the silicon strip tracker raw data is reconstructed in 5 ± 3 ms (or an average contribution per event of 0.5 ms) whilst maintaining 99 % of the original dielectron trigger efficiency.


The CMS experiment
Compact Muon Solenoid (CMS) is one of the four main detectors at the Large Hadron Collider (LHC) based at CERN, Switzerland. It is a general purpose collider detector optimized to discover the Higgs Boson and signatures of physics beyond the Standard Model (SM). At the heart of CMS is a 13 m long, 5.9 m inner diameter superconducting solenoid, designed to produce nearly uniform magnetic fields of 4 T . Within the solenoid sits the LHC beam pipe, the tracking detector and the calorimeter. In order to deal with the high track multiplicities expected in the LHC environment and provide precision momentum measurements, CMS uses 9 to 12 layers of highly granular silicon microstrip detectors, resulting in a very large channel count. Three layers of silicon pixel detectors are placed closed to the interaction region for the precision spatial measurement of particle vertices. The calorimeter consists of both electromagnetic (Ecal) and hadronic (Hcal) components. Beyond the magnet sits an iron return yoke and a muon tracking system.  Table 1. Event data summary for the dominant sub-detectors at high luminosity running.

The event data
The CMS detector is unprecedented in terms of its size and complexity. At high luminosity running (10 34 cm −2 s −1 ) event data sizes of ∼2 MB are expected. Raw data are expected to contribute a significant fraction of this size. A breakdown on the contribution of the most dominant sub-detectors is shown in Table 1. Although the pixel detector has almost a factor 10 more channels than the strip tracker, larger occupancies in the latter result in a data rate almost 7 times larger [1].

The strip tracker readout system
The readout system is based on the front-end analogue APV25 readout chip [2], analogue optical links and an off-detector Front-End Driver (FED) processing board [3]. The APV25 chip samples, amplifies, buffers and processes signals from 128 channels of a silicon strip sensor at the LHC collision frequency of 40 MHz. On receipt of a Level-1 trigger, pulse height and bunch crossing information from pairs of APV25 chips are multiplexed onto a single line and the analogue data are converted to optical signals before being transmitted via optical fibres to the off-detector FED boards. The FEDs digitize, process and format the pulse height data from up to 96 pairs of APV25 chips, before forwarding zero-suppressed data to a computing farm for further event filtering.

The trigger
An LHC bunch crossing frequency of 40 MHz and large event data sizes necessitate a fast and efficient triggering system. The CMS trigger comprises two decision levels: Level-1 (L1) reduces the event rate to 100 KHz using calorimeter and muon information; the High Level Trigger (HLT) combines information from the full detector and reduces further to the write-to-disk rate of 100 Hz [4]. The HLT processes all events accepted by L1 in a single computer farm. The selection of events is optimized by rejecting un-interesting events as quickly as possible. With this in mind, each trigger path consists of several software modules, where each module fulfills a well defined task such as reconstruction or a trigger decision.

Track reconstruction
The raw data output from each FED encodes the basic hit information (pulse heights and corresponding strip numbers) necessary for tracking along with information on the bunch crossing number, the status of the tracker hardware and the status of the data acquisition system. Prior to reconstruction, these data are unpacked and the zero-suppressed strip information, known as a digis, are extracted.
Track reconstruction proceeds in two phases: local and global. In the first phase, localized hits are constructed from the extracted digis within the geometry of CMS. In the second phase, tracks are constructed from groups of these hits. Local reconstruction itself is a two-stage process involving clusterization (grouping together neighbouring, gain corrected digis) and incorporation of the geometrical position of the hit. Global reconstruction can be subdivided into four steps: track candidate generation, track fitting, ambiguity resolution and smoothing. A track candidate defines the inital trajectory parameters and their errors. The pixel detector is best suited for track candidate formulation due to its low occupancy, the precision of its hits and its proximity to the beam pipe. To streamline this process for the HLT, tracking regions of interest can be identified within the pixel detector through seeds identified in external subdetectors, such as the Ecal.
One pattern recognition algorithm used for track fitting is a combinatorial Kalman filter [5]. The filter proceeds from the coarse estimate of tracking parameters provided by the seed, determines which layers are compatible and extrapolates the trajectory to these layers according to the equations of motion of a charged particle in a magnetic field through material. As the trajectory encounters each hit, it is updated according to the Kalman filter formalism. If a stopping condition is satisfied, the algorithm is interrupted. It is especially useful for the HLT where, for example, the required performance is often reached after 5 or 6 hits.
Once the tracks are formed, ambiguities and instances of double counting are resolved. Since the full tracking information is only available at this point, any bias introduced with the imposed constraints is removed by a final fit. More details on the full tracking procedure can be found in [1].

The HLT time budget
During the first year of operating at low luminosity (2 × 10 33 cm −2 s −1 ), L1 is expected to provide an input trigger rate of 50 kHz to the HLT farm. The HLT farm will comprise 2000 CPUs, which results in an average time quota of 40 ms per event for each HLT processing node [6].

Local reconstruction software architecture
The HLT is implemented within the CMS offline reconstruction framework, CMSSW, which is designed around the Event Data Model (EDM) [7]. The basic premise of the EDM is that all user-defined types are contained within a single object called the event. All event products relate to a single triggered readout of the CMS detector. They are processed by passing the event object through a series of user-defined plugin modules within a CMSSW path. User access to auxiliary conditions data (e.g. cabling information) is given via an independent object called the event setup.
The CMSSW software design for the local phase of track reconstruction is shown in Figure 1. It describes the unpacking, clusterization and hit production modules interacting directly with the event and event setup. In the event data model, no interaction between software modules is allowed. Hence, there is no direct communication between the local reconstruction and track reconstruction software modules. Additionally, no information from the muon and calorimetry systems on the event topology is communicated to the tracking code.

Software performance
All studies in this document were performed in version 1.6.0 of CMSSW. Times quoted are wall-clock times measured on an a dual core AMD Opteron TM processor 248, with 2.14 GHz CPU and a 1 MB cache.
The software performance can be measured in two ways: through its timing cost to the HLT and through direct validation of the product digis against the input raw data. For the latter, an input source of fake raw data with configurable hit distributions has been developed. Though allowing the raw-to-digis module to be tested exhaustively, the clusterizer and hit producer raw-to-digis raw-to-clusters raw-to-hits cannot be validated in such a rigorous fashion. In general, the clusterizer algorithms reject digis below threshold and so the data are not directly comparable. The integrated reconstruction time up to the level of digis, clusters and hits is shown as a function of occupancy in Figure 2 for low luminosity minimum bias events. The time cost for the unpacking stage (identified in the plot as raw-to-digis) increases with strip occupancy, albeit with a relatively shallow gradient, due a single loop over all occupied digis stored within the raw data.
The time to clusterize the event data (raw-to-clusters) is strongly dependent on strip occupancy. This is to be expected since the algorithm performs two full loops over the zerosuppressed data: one to search for seeds and the second to find neighbouring strips above threshold. Multiple use of conditional statements also serve to make the clusterizer module the dominant time cost.
The hit production algorithm (raw-to-hits) is clearly the least time consuming. This is for several reasons: its task is simple with little memory overhead or CPU requirement; it deals with a smaller data-set since below threshold digis may be rejected by the clusterizer and it loops over clusters rather than digis reducing the number of loop iterations further still.
Since the expected mean tracker occupancy at low luminosity running is 0.56 % the corresponding mean local reconstruction time is 5.5 s. Although as few as 10 % of L1 accepted events are expected to require track reconstruction on the HLT [4], this still exceeds the total HLT budget (Section 1.5). To address these performance issues, the primary algorithmic inefficiencies and bottlenecks in the timing have been identified below: • The majority of the unpacked raw data is not used within the tracking algorithms. A more sophisticated, regional approach to unpacking could be implemented to reduce this overhead, though not eliminate entirely since the smallest unpacking granularity is a single FED. 1 • At the heart of the clusterizer's inefficiency is its use of an initial loop over strips to find cluster seeds. A more streamlined algorithm is required to clusterize within a single loop. • The templated container class DetSetVector T used by most CMSSW software modules within the reconstruction chain is effective, though highly inefficient when dealing with such large amounts of data. Every insertion into this collection forces a sort and copy. Since the number of insertions is large for the SST (for a low luminosity event, approximately 6×10 4 digis are generated and 1.5×10 4 clusters), a new container class is required. • The entire software scheme enforces a copy of a large fraction of the raw data at both the unpacking and clusterization stages. Since C++ copy times are linear with the data size, this becomes a highly significant effect for a 10 7 channel detector. Furthermore, each stage in the low level reconstruction chain introduces a loop over channels. Integrating the unpacking and clusterizing algorithms within a single loop would serve to halve these effects.

Local reconstruction on demand
To address the issues itemized in Section 2.1 and hence streamline the local reconstruction chain, a new software architecture was devised. The SST modules are grouped into geometrical regions, defined by a grid on the η-φ plane (where η is the pseudorapidity and φ the azimuthal angle) with configurable dimensions. The new design allows raw data from regions-of-interest only to be considered. More specifically, any FED raw data packet with at least one channel connected to a region-of-interest is fully unpacked. A schematic of the regional concept is shown in Figure  3. These regions-of-interest can be defined by a dedicated CMSSW module, based on objects identified in external sub-detectors. The same module can also be configured to identify the full set of regions: termed global mode. Hit reconstruction is triggered by a request from any downstream module. A new cluster container has also been developed. Storing clusters by region (numbered sequentially from zero) means read and write operations can be performed by direct access to the relevant memory address rather than through a search, which is inherently slow. A fixed container size also means the sort and copy involved with DetSetVector T insertions is no longer necessary.
A framework feature is that once data are stored within the event, they can no longer be changed. This becomes an obstacle when multiple tracking modules exist within a single path, each with an independent set of tracking regions-of-interest. For example, within the HLT where multiple reconstruction chains can be executed for every event. To overcome this, an empty cluster container is added (by a clusterizer facility) with access to the raw data and relevant calibrations. When the raw-to-hits module requests clusters, the container self-fills by unpacking and clusterizing all regions-of-interest within a single loop.  software design is shown in Figure 4.

Software performance
The total number of tracker regions has a significant effect on the overall software performance, demonstrated by Figure 5. This trend is mainly due the overhead introduced by initialising the cluster container at the start of every event. A balance exists between increasing reconstruction times and improved detector granularity. With this in mind, a 20 × 20 configuration has been chosen. Since each of these divisions is further divided into layers, this corresponds to ∼ 4000 regions in total. Figure 6 shows the distribution in hit reconstruction times for low luminosity minimum  Figure 5. The variation in hit reconstruction time with regional granularity for minimum bias events at low luminiosity. Here, the new regional scheme is used but in global mode. 20 divisions in η and φ corresponds to a regional granularity ∆η × ∆φ of 0.250 × 0.314. For reference, a calorimeter tower in the barrel has granularity 0.0870 × 0.0873.
bias events when unpacking all regions. Over 1000 events, all times were measured at under 400 ms with a mean value of 140 ms. This is almost a factor 40 improvement on the previous reconstruction scheme. Since only 10 % of L1 accepted events are expected to require track reconstruction on the HLT, the average contribution per event is therefore ∼14 ms. This is ∼30 % of the full budget. The variation of time with strip occupancy and mean cluster width is shown in Figure 7. The figure on the left shows a linear increase in reconstruction times with occupancy, analogous to the trend of Figure 2. High luminosity conditions, with a mean strip occupancy of 1.7 %, require 380 ms. If only 10 % of events require hit reconstruction this is almost the entire HLT budget. Although a significant fraction of the timing budget is taken at both low and high luminosity, further improvements will be made when using the regional approach. Figure 7 also validates the fake cluster source described in Section 2.1 which is used in the figure on the right. Here the occupancy is fixed, hence the cluster width and total number of clusters are inversely proportional. Therefore, increasing cluster width results in a decreasing reconstruction time. Table 2 gives a breakdown of the dominant time costs measured over a characteristic HLT path. Due to the nature of the new SST reconstruction schema, the hit reconstruction time is absorbed by the L2.5 track reconstruction module. Of the 60 ms measured here, ∼50 % goes toward reconstructing hits. In comparison, the full Ecal hit production chain costs 22.6 ms with only 1/5 th the data rate ( Table 1). The averaged times demonstrate the true timing cost of each module after considering the fraction of L1 events they are required for. They clearly show the strip tracker is no longer the primary reconstruction bottleneck. Also, for minimum bias events without pile-up the HLT quota of 40 ms has been achieved. Figure 8 demonstrates the benefits seen with the regional approach. The fit is for a linear increase in time with regions-of-interest over evenly distributed fake clusters. An overhead of less than 5 ms exists in the case of no reconstruction being performed.
Over Z 0 → e + e − events, the calorimeter seeds used within isolated electron reconstruction were also used to define the tracker regions-of-interest. The dielectron trigger efficiency has been recorded for various ∆η × ∆φ windows around these center-points. Figure 8 indicates that 99 % of the efficiency achieved with full hit reconstruction occurs with a 0.16 × 0.16 window. This corresponds to an array of dimension 2×2, 3×3, 2×3 or 3×2, depending on the η,φ position of Here, the new regional software scheme is used, but in global mode.  A direct comparison of regional and global reconstruction is shown in Table 3 over Z 0 → e + e − events without pile-up. With a 0.16 × 0.16 ∆η × ∆φ window only 2 ± 1 % of the tracker is reconstructed in 5 ± 3 ms. This corresponds to ∼0.5 ms when considering the track reconstruction rate on the HLT. It is a factor 13 faster than the global approach. Similar performances are expected for all trigger paths and at higher luminosities.   Global 100 0.24 ± 0.06 70 ± 10 Regional 2 ± 1 0.4 ± 0.1 5 ± 3 Table 3. Performance summary of the local reconstruction software in both regional and global modes over Z 0 → e + e − events without pile-up. Here, regional occupancy corresponds to the regions-of-interest only.

Integration with the tracking algorithms
Work is ongoing to introduce these algorithms within the tracking code itself. In this way, detector regions of interest can be defined layer-by-layer using the projected track trajectory and its error. Information external to the SST would no longer be required, simplifying the software management considerably. Also, since all regions intersecting the track's path are reconstructed by definition, trigger efficiencies would remain unaffected. In this sense it is the best possible scenario.

Summary
Local reconstruction of the CMS silicon strip tracker data (to the level of hits) on the HLT computer farm is subject to stringent requirements in terms of the time budget (40 ms/event) and the raw data volume to be processed (0.5 MB/event). To minimize their contribution to the former, the local reconstruction algorithms have been redesigned, reducing the reconstruction time for minimum bias events at low luminosity from 5.5 s to 140 ms. Since approximately 10% of level-1 accepted events are expected to require track reconstruction, the average contribution per event is ∼14 ms. This is ∼30 % of the full budget. Additionally, the new schema is also capable of reconstructing only physics regions-of-interest, in order to reduce the time cost further. For an example trigger path of Z 0 → e + e − events, 99 % of the original dielectron trigger efficiency is maintained whilst unpacking only 2 ± 1 % of the tracker in 5 ± 3 ms. This too is expected to reduce by a factor of 10 when considering the fraction of events requiring track reconstruction. Similar performances are expected for all trigger paths and at higher luminosities.