Gradient-boosted trees and random forests are among the most popular machine learning algorithms. They are applied to a broad spectrum of applications as diverse as search engine ranking, credit card fraud detection, customer relationship management, fault diagnosis in machinery, and geological studies, to name a few. Inference of these models is supported by many widely-used libraries and frameworks including Scikit-Learn, XGBoost, and ONNX Runtime. Many of the inference algorithms integrated in these libraries are optimized for performing fast predictions for large input batches, often targeted at ensemble models containing relatively shallow decision trees. This does not necessarily match well with the requirements of new emerging applications that depend on real-time predictions for individual samples or small input batches. Also, cloud-based inference services put more emphasis on small memory footprints. This paper aims to fill this gap by proposing a novel inference scheme for decision-tree ensembles that efficiently handles a wider range of application requirements and model characteristics. Performance is maximized for an extensive number of parameter combinations through a new concept in which a predict function is selected dynamically at runtime. This is done in a way that the processing resources, including the use of SIMD vector processing units and multithreading, are optimally exploited. Experiments have shown substantial performance improvements over state-of-the-art algorithms for common models.

This paper presents a tensor-based algorithm that leverages a hardware accelerator for inferencing decision-tree-based machine learning models. The algorithm has been integrated in a public software library and is demonstrated on an IBM z16 server, using the Telum processor with the Integrated Accelerator for AI. We describe the architecture and implementation of the algorithm and present experimental results that demonstrate its superior runtime performance compared with popular CPU-based machine learning inference implementations.

Application and technology trends are increasingly forcing computer systems to be designed for specific workloads and application domains. Although memory is one of the key components impacting the performance and power consumption of state-of-art computer systems, its operation typically cannot be adapted to workload characteristics beyond some limited controller configuration options. In this paper, we present a novel near-memory acceleration platform based on an Access Processor that enables the main memory system operation to be programmed and adapted dynamically to the accelerated workload. The platform targets both ASIC and FPGA implementations integrated within IBM POWER systems. We show how this platform can be applied to accelerate stencil processing.

Processing-in-memory and near-memory computing have recently been rediscovered as a way to alleviate the “memory wall problem” of traditional computing architectures. In this paper, we discuss the implementation of a 3D-stacked near-memory accelerator, targeting radio astronomy and scientific applications. After exploring the design space of the architecture by focusing on minimizing the execution power of the processing pipeline of the SKA1-Low central signal processor, we show that our accelerator can achieve an energy efficiency of up to 390 GFLOPS/W, corresponding to an energy consumption one order of magnitude lower than alternative state-of-the-art implementations. When running additional mathematical and streaming-oriented kernels, our accelerator achieves from 6.4x to 20x energy efficiency improvement compared to alternative solutions.

We demonstrate the use of an FPGA as a memory buffer in a POWER8® system, creating a novel prototyping platform that enables innovation in the memory subsystem of POWER-based servers. Our platform, called ConTutto, is pin-compatible with POWER8 buffered memory DIMMs and plugs into a memory slot of a standard POWER8 processor system, running at aggregate memory channel speeds of 35 GB/s per link. ConTutto, which means "with everything", is a platform to experiment with different memory technologies, such as STT-MRAM and NAND Flash, in an end-to-end system context. Enablement of STT-MRAM and NVDIMM using ConTutto shows up to 12.5x lower latency and 7.5x higher bandwidth compared to the respective technologies when attached to the PCIe bus. Moreover, due to the unique attach-point of the FPGA between the processor and system memory, ConTutto provides a means for in-line acceleration of certain computations on-route to memory, and enables sensitivity analysis for memory latency while running real applications. To the best of our knowledge, ConTutto is the first ever FPGA platform on the memory bus of a server class processor.

To increase the performance of data-intensive applications, we present an extension to a CPU architecture that enables arbitrary near-data processing capabilities close to the main memory. This is realized by introducing a component attached to the CPU system-bus and a component at the memory side. Together they support hardware-managed coherence and virtual memory support to integrate the near-data processors in a shared-memory environment. We present an implementation of the components, as well as a system-simulator, providing detailed performance estimations. With a variety of synthetic workloads we demonstrate the performance of the memory accesses, the mixed fine- and coarse-grained coherence mechanisms, and the near-data processor communication mechanism. Furthermore, we quantify the inevitable start-up penalty regarding coherence and data writeback, and argue that near-data processing workloads should access data several times to offset this penalty. A case study based on the Graph500 benchmark confirms the small overhead for the proposed coherence mechanisms and shows the ability to outperform a real CPU by a factor of two.

Regular-expression accelerators often rely on sophisticated compilers to fully exploit the available hardware capabilities for achieving wire-speed scan rates of multiple tens of gigabits per second. This paper presents a method for the efficient compilation of pattern-matching functions specified by deterministic finite automata (DFAs) into executable structures targeted at accelerators based on B-FSM programmable state machines. The compilation scheme presented is able to effectively exploit an adaptive compression mechanism to obtain one of the most compact state-transition-table structures in the industry, in combination with fast compilation times. The heuristic-based approach scales to very large DFAs having tens of millions of transitions, while achieving an approximately linear growth of the storage needs as a function of the DFA size.

The Square Kilometre Array (SKA) is a future radio telescope, currently being designed by the worldwide radio-astronomy community. During the first of two construction phases, more than 250,000 antennas will be deployed, clustered in aperture-array stations. The antennas will generate 2.5 Pb/s of data, which needs to be processed in real time. For the processing stages from A/D conversion to central correlation, we propose an ASIC solution using only three chip architectures. The architecture is scalable - additional chips support additional antennas or beams - and versatile - it can relocate its receiver band within a range of a few MHz up to 4GHz. This flexibility makes it applicable to both SKA phases 1 and 2. The proposed chips implement an antenna and station processor for 289 antennas with a power consumption on the order of 600W and a correlator, including corner turn, for 911 stations on the order of 90 kW.

Programmable hardware accelerators for regular expression (regex) matching are evolving into increasingly complex stream processors, which involve multiple state machines that operate in parallel, and specialized post-processors that can process instructions dispatched by the state machines. To improve the speed and the storage-efficiency, complex regexs are decomposed into simpler subexpressions, where each subexpression can fire one or more instructions. Although the impact of regex decompositions on the storage efficiency is well-known, little has been done to address the correctness and completeness. We show that regex decompositions can result in false positives if overlaps between subexpressions are not taken into account. We describe formal methods to recognize various types of subexpression overlaps that can arise in regex decompositions. We also describe efficient post-processing techniques to eliminate the associated false positives. To enable efficient mapping of the decomposed regexs to the postprocessors, we propose integer programming based register allocation methods. Our methods pack narrow variables to reduce the register and instruction usage, and take advantage of multi-register reset instructions to reduce the number of instructions that must be executed in parallel. Experiments on regex sets obtained from open-source and proprietary network intrusion detection systems demonstrate orders of magnitude improvement in the storage efficiency over state-of-the-art.

Hardware acceleration of regular expression matching is key to meeting the throughput requirements of state-of-the-art network intrusion detection systems (NIDSs) dictated by fast growing link speeds. This paper presents extensions to a programmable state machine, called B-FSM, which was initially optimized for string matching. These extensions enable direct support in hardware for essential regular expression features, such as character classes and case insensitivity. Moreover, they also allow the exploitation of regular expression properties that show up at the data structure level as common transitions shared between multiple states, resulting in storage reductions of up to 95% for five NIDS pattern sets analyzed. Additional instruction support based on a flexible integration within the B-FSM data structure increases the processing capabilities and enables the scaling to larger pattern collections. The new IBM Power Edge of NetworkTMprocessor employs the B-FSM technology to provide scanning capabilities at typical rates of 20-40 Gb/s.

A growing number of applications rely on fast pattern matching to scan data in real-time for security and analytics purposes. The RegX accelerator in the IBM Power Edge of Network (PowerEN) processor supports these applications using a combination of fast programmable state machines and simple processing units to scan data streams against thousands of regular-expression patterns at state-of-the-art Ethernet link speeds. RegX employs a special rule cache and includes several new micro-architectural features that enable various instruction dispatch and execution options for the processing units. The architecture applies RISC philosophy to special-purpose computing: hardware provides fast, simple primitives, typically performed in a single cycle, which are exploited by an intelligent compiler and system software for high performance. This approach provides the flexibility required to achieve good performance across a wide range of workloads. As implemented in the PowerEN processor, the accelerator achieves a theoretical peak scan rate of 73.6 Gbit/s, and a measured scan rate of about 15 to 40 Gbit/s for typical intrusion detection workloads.

New generations of network intrusion detection systems create the need for advanced pattern-matching engines. This paper presents a novel scheme for pattern-matching, called BFPM, that exploits a hardware-based programmable statemachine technology to achieve deterministic processing rates that are independent of input and pattern characteristics on the order of 10 Gb/s for FPGA and at least 20 Gb/s for ASIC implementations. BFPM supports dynamic updates and is one of the most storage-efficient schemes in the industry, supporting two thousand patterns extracted from Snort with a total of 32 K characters in only 128 KB of memory.

Emerging Internet applications create the need for advanced packet classifiers. We propose a novel multifield classification scheme, called P2C, which exploits the strengths of state-of-the-art memory technologies to provide wire-speed classification performance for OC-192 and beyond, in combination with very high storage efficiency and the support of fast incremental updates. Key features of the new scheme are its ability to adapt to the complexity of a classification rule set, whereas the storage requirements and update dynamics can be tuned at the granularity of individual rules. This makes P2C suitable for a broad spectrum of applications.

Emerging Internet applications create the need for advanced packet classifiers. This paper investigates the mechanisms that determine the performance of state-of-the-art multi-field classification methods, and proposes a novel scheme called P/sup 2/C for packet classification at OC-192 and OC-768 speeds. P/sup 2/C combines the strengths of embedded memory and ternary CAM technologies to achieve very high storage efficiency while maintaining fast incremental updates. Key feature of the new scheme Is Its ability to adapt to the complexity of a classification rule set, while providing effective control over the update dynamics and storage requirements at the granularity of individual rules. This makes P/sup 2/C suitable for a broad range of applications.

Exponentially growing routing tables create the need for increasingly storage-efficient lookup schemes that do not compromise on lookup performance and update rates. This paper evaluates the mechanisms that determine the storage efficiency of state-of-the-art IP lookup schemes. A novel scheme named BARTS (balanced routing table search) is proposed for searching large routing tables in wide embedded memory at OC-192 and OC-768 speeds, while also supporting fast incremental updates. BARTS supports a 38 K-entry routing table in 255 KB and a 72 K-entry table in 453 KB; a 500 K-entry table is estimated to fit into 3 MB. More sophisticated memory management can further reduce these figures to 215, 375 KB, and approximately 2.5 MB, respectively. This is sufficient to handle the large routing tables towards which the Internet seems to be heading in the near future.

The balanced routing table search (BaRTs) scheme is a novel method for searching large routing tables at OC-192 and OC-768 speeds. The scheme employs a compression technique that leaves all prefix information intact and creates a stand-alone data structure that can be incrementally updated. Performance-critical parts of the update operation are suitable for hardware implementation, enabling update rates beyond several hundred thousand per second. Simulations with actual routing tables have shown that BaRTs supports a routing table with 36,292 entries in only 292 KB of storage, a table with 72,825 entries in 555 KB, and a future table with 500,000 entries is estimated to fit in 3.7 MB.