High-Energy Physics - Signal Processing Systems - page 159

partitioning affects the required interconnection and bandwidth between devices.
A common approach is to minimize the cut-size (min-cut)—that is, the number of
data connections or cross-sectional bandwidth—between partitions. This helps to
mitigate bottlenecks in the inter-device communication systems. Minimizing cut
size is also important in HEP systems as interconnection is a major contributor to
system complexity.
Techniques for automated design partitioning on FPGA devices have been
studied by several research groups. Some tools, such as SPARCS [ 52 ] use graph-
based partitioning methods that may be complementary to some of the dataflow-
based design techniques discussed in Sect. 4.4 . These methods are effective at
bandwidth-driven partitioning. Since HEP triggering systems often have tight end-
to-end latency constraints, performance-driven partitioning algorithms [ 27 ] maybe
preferable in some situations. It is not clear, however that partitioning techniques
based on randomized pre-partitioning and iterative incremental optimizations are
well-suited to HEP. HEP algorithms tend to be highly regular and therefore may
be better suited to manual partitioning at the level of a task graph or through the
use of customized partitioning algorithms. Moreover, the high sustained bandwidth
of HEP algorithms forces the bulk of their communication onto a smaller number
of high-speed serial links rather than a large number of simpler nets. This raises
questions about whether traditional min-cut heuristics are still the most appropriate
way of judging complexity. As internal nets must be routed to the serial transceivers,
a move towards routability-focused partitioning heuristics may be more appropriate.
Efficient partitioning methods may be a potential avenue of future research.

5 Example Problems from the CMS Level-1

Calorimeter Trigger

Thus far, we have primarily focused on HEP challenges in a general sense, supported
by selected examples from specific HEP systems. To give the reader a better sense
of the precise type of algorithms and designs that may occur in HEP applications,
this section presents a set of more detailed challenges specifically faced in the
SLHC upgrade of the CMS Level-1 Calorimeter Trigger at CERN's Large Hadron
Collider. The CMS is a general-purpose HEP experiment that searches for a variety
of different physics phenomena. As such, its systems share similarities with other
general-purpose HEP systems, such as the LHC's ATLAS experiment and the
Tevatron's D0 experiment [ 31 ] . All three experiments use energy readings from one
or more calorimeters and muon detectors as a source of raw data. Each experiment
uses a triggering system to attempt to isolate and identify fundamental particles
created in collisions, and avoid storing data for uninteresting events. Whereas
the exact specifications of the CMS Trigger are unique, its functions are similar
to those that are likely to be encountered in other triggering systems. In this
section, we discuss algorithms for two such functions: particle identification and
jet reconstruction.