International Business Machines Corporation

Jan Van Lunteren

Christoph Hermann Hagleitner

Giora Biran

Timothy Hume Heil

Russell Dean Hoover

Antonius Paulus Engbersen

Heiner Giefers

Charalampos Pozidis

Clark Debs Jeffries

Kubilay Atasu

Fabrice Jean Verplanken

Gordon Taylor Davis

Nikolaos Papandreou

Thomas P Parnell

Markus Kaltenbach

Ulrich Mayer

Thomas Pflueger

Francois Abel

Raphael C Polig

Harald Huels

Joerg-Stephan Vogt

Rolf Fritz

Marcel Waldvogel

Jonathan Bruno Rohrer

Glenn A Marcy

Cordt W Starke

Angelo Haller

Sang Hoo Dhong

Jean Louis Calvignac

Nikolas Ioannou

Martin L Schmatz

Harm Peter Hofstee

Ajay Dholakia

Osamu Takahashi

Douglas James Joseph

Andreas Kind

Everett Arthur Corl, Jr

Milos Stanisavljevic

Peter L Buchmann

Andreas Guenther Herkersdorf

Andreea Anghel

Uzi Shvadron

Martin Petermann

Brooks Johnston

James P Coghlan

Florian Dorfler

Jean L Cavignac

Florian Doerfler

Plyush C Patel

Hoi Sun Ng

A method of dynamically optimizing decision tree inference is provided. The method, which is performed at the computerized system, repeatedly executes one or more decision trees for inference purposes and repeatedly performs an optimization procedure according to two-phase cycles. Each cycle includes two alternating phases, i.e., a first phase followed by a second phase. The decision trees are executed based on a reference data structure, whereby attributes of nodes of the decision trees are repeatedly accessed from the reference data structure during the first phase of each of the cycles. First, the accessed attributes are monitored during the first phase of each cycle, which leads to update statistical characteristics of the nodes. Second, a substitute data structure is configured during the second phase of each cycle based on the updated statistical characteristics. Third, the reference data structure is updated in accordance with the substitute data structure.

Dynamically optimizing decision tree inferences

A method and computer program product for performing machine learning inferences are disclosed. A set of input records to be processed by decision trees is selected, and the decision trees are run. Running the decision trees includes identifying operations to be performed as matrix elements, wherein the matrix elements correspond to the input records. Running the decision trees also includes using vector processing to process disjoint subsets of the matrix elements based on vector instructions operating on data stored in vector registers, such that the matrix elements of each subset of the disjoint subsets are processed in parallel. All leaf nodes of each decision tree involved are processed as split nodes looping to themselves until a termination condition is met. The termination condition is met if at least one of the leaf nodes has been reached for each of the decision trees involved.

Vector processing of decision trees to form inferences

An approach of accelerating inferences based on decision trees based on accessing one or more decision trees, wherein each decision tree of the decision trees accessed comprises decision tree nodes, including nodes grouped into one or more supersets of nodes designed for joint execution. For each decision tree of the decision trees accessed, the nodes are executed to obtain an outcome for the one or more decision trees, respectively. For each superset of the one or more supersets of said each decision tree, the nodes of each superset are jointly executed by: loading attributes of the nodes of each superset in a respective cache line of the cache memory processing said attributes from the respective cache line until an inference result is returned based on the one or more outcomes.

Joint execution of decision tree nodes for accelerating inferences

Methods are provided for inference processing of a decision tree model in processing apparatus which executes vector instructions to perform inference computations on vectors of operands stored in vector registers of the apparatus. Such a method includes, for each decision tree of the model, indexing nodes of the tree by consecutive node indexes which are assigned to nodes in a breadth-first order and increase with node-depth in the tree. During the inference processing, a vector of N node indexes, corresponding to a set of nodes for which N inference computations will be performed in parallel, is stored in a vector register of the apparatus. The method further includes adaptively selecting the granularity N of the vector of node indexes, in dependence on (at least) the node-depth of nodes in the set, to accelerate inference processing of the model.

Inference processing of decision tree models using vector instructions

Methods, computer program products, and/or systems are provided that perform the following operations: setting a memory buffer having contiguous memory blocks; obtaining a decision tree comprising nodes including split nodes and leaf nodes, wherein each of the split nodes includes at least two child nodes that are ordered according to a likelihood of accessing a child node after each of the split nodes; mapping the nodes onto respective blocks of the memory blocks, each of the memory blocks storing attributes of a corresponding one of the nodes, wherein each of the split nodes and any child nodes of each split node are mapped onto successive blocks, wherein ordered child nodes of a same one of the split nodes are mapped onto successive blocks; executing the nodes by processing the attributes of the nodes as accessed from the memory according to an order of the memory blocks in the memory buffer.

Accelerating decision tree inferences

The invention is notably directed to a computing system configured to perform linear algebraic operations. The computing system comprises a co-processing module comprising a co-processing unit. The co-processing unit comprises a parallel array of bit-serial processing units. The bit-serial processing units are adapted to perform the linear algebraic operations with variable precision. The invention further concerns a related computer implemented method and a related computer program product.

Bit-serial linear algebra processor

Performing n-dimensional stencil processing may include providing a memory unit organized in memory banks for storing elements of an nD matrix, processing the matrix using a stencil vector unit in a first processing direction of the matrix tile-wise(/d). Data elements of the matrix can be equally distributed over the memory banks, and the number of memory banks can be equal to the number of data elements processable by the stencil vector unit in parallel, which is equal to the number of data elements in a width direction of one of the tiles. Additionally, the boundary elements can be grouped in the width direction of the tiles into a nD sub-matrix, and the nD sub-matrix can be processed equally to the processing the nD matrix orthogonal to the first processing direction.

Vector-based tiled processing with data-sharing neighboring tiles

A method for accessing a binary data vector in a memory unit comprising a plurality of memory banks in which the binary data vector is stored in portions includes receiving a start address of the binary data vector and a power-of-2-stride elements of the data vector and determining offsets, wherein the offsets are determined by applying a plurality of bit-level XOR functions to the start address resulting in a Z vector, using the Z vector for accessing a mapping table, and shifting mapping table access results according to a power-of-2-stride of the binary data vector. Additionally, the method includes determining a sequence of portions of the binary data vector in the n memory banks depending on a binary equivalent value of the Z vector, and accessing the binary data vector in the n memory banks of the memory unit in parallel.

Address generation for high-performance vector processing

A computing system comprising a central processing unit (CPU), a memory processor and a memory device comprising a data array and an index array. The computing system is configured to store data lines comprising data elements in the data array and to store index lines comprising a plurality of memory indices in the index array. The memory indices indicate memory positions of data elements in the data array with respect to a start address of the data array. There is further provided a related computer implemented method and a related computer program product.

Index based memory access using single instruction multiple data unit

A method for performing enhanced pattern scanning includes the steps of: providing a three-dimensional memory structure including multiple physical memory elements; compiling multiple programmable finite state machines, each of the programmable finite state machines representing at least one deterministic finite automation data structure, the data structure being distributed over at least a subset of the physical memory elements; configuring a subset of the programmable finite state machines to operate in parallel on a same input data stream, while each of the subset of programmable finite state machines processes a different pattern subset; and providing a local result processor, the local result processor transferring at least a part of a match state from the deterministic finite automation data structures to corresponding registers within the local result processor, the part of the match state being manipulated being based on instructions embedded within the deterministic finite automation data structures.

Three-dimensional chip-based regular expression scanner

A reconfigurable computing device having a plurality of reconfigurable partitions and that is adapted to perform parallel processing of operand data by the partitions is provided. The computing system includes a memory device that is adapted to store configuration data to configure the partitions of the computing device, to store operand data to be processed by the configured partitions and to store processing results of the operand data. A programmable memory access processor having a predefined program is provided. The access processor performs address generation, address mapping and access scheduling for retrieving the configuration data from the memory unit, for retrieving the operand data from the memory unit and for storing the processing results in the memory unit. The access processor also transfers the configuration data from the memory unit to the computing device and transfers the operand data from the memory unit to the computing device.

Access processor

A computing system includes a host processor, an access processor having a command port, a near memory accelerator, and a memory unit. The system is adapted to run a software program on the host processor and to offload an acceleration task of the software program to the near memory accelerator. The system is further adapted to provide, via the command port, a first communication path for direct communication between the software program and the near memory accelerator, and to provide, via the command port and the access processor, a second communication path for indirect communication between the software program and the near memory accelerator. A related computer implemented method and a related computer program product are also disclosed.

Near memory accelerator

Methods, systems and computer program products are disclosed for detecting patterns in a data stream that match multi-pattern rules. One embodiment of the invention provides a method of recognizing a specified group of patterns in a data stream. The method comprises identifying a rule for said specified group of patterns in the data stream, and using a first array of finite state machines to scan the data stream for at least some of the patterns in the specified group. For patterns in the specified group that are found in the data stream by the first array of finite state machines, pattern identifiers are sent to a second array of finite state machines. The second array of finite state machines determines if the specified group of patterns is in the data stream in accordance with the identified rule by, at least in part, using said pattern identifiers.

Match engine for detection of multi-pattern rules

Growing community of inventors

Gattikon, Switzerland

Jan Van Lunteren