US 11,954,093 B2 · Performing a top-k function using a binary heap tree

Abstract

Embodiments of the disclosure provide devices and methods for performing a top-k function. The device can include: a memory comprising a plurality of register files for storing the data elements, the plurality of register files comprising a parent register file and a first child register file associated with the parent register file, wherein the parent register file is associated with: first interface circuitry configured for reading a first parent data element from the parent register file and receiving a first child data element and a second child data element from the first child register file; and first comparison circuitry configured for updating the parent register file and the first child register file based on the first parent data element, the first child data element, and the second child data element according to a given principle.

Claims19

Dependent claims

A computer processing unit for heapifying data elements, comprising:

a memory comprising storage circuitry forming a plurality of register files for storing the data elements, the plurality of register files comprising a parent register file and a first child register file associated with the parent register file;
a plurality of hardware nodes including a parent hardware node and children hardware nodes, each parent hardware node comprising:
first interface circuitry associated with the parent register file and configured for reading a first parent data element from the parent register file and receiving a first child data element and a second child data element from the first child register file;
and
first comparison circuitry associated with the parent register file and configured for updating the parent register file and the first child register file, by generating one or more indication signals, based on the first parent data element, the first child data element, and the second child data element according to a given principle;
a multiplexer configured to transceive data elements with other hardware nodes, wherein the first comparison circuitry is configured to receive the first parent data element, the first child data element, and the second child data element from the multiplexer and sequentially perform comparison on two of the first parent data element, the first child data element, and the second child data element.

3 more elements

A method for heapifying a hardware binary tree that comprises K nodes distributed across N node levels, each of the K nodes being a hardware node comprising interface circuitry and storage circuitry, wherein K and N are integers greater than three, the method comprising:

assigning and storing K initial data elements received by the interface circuitry of the K nodes from a host system to the storage circuitry of the K nodes, the N node levels comprising a first node level, a second node level that is a child level of the first node level, a third node level that is a child level of the second node level, and a fourth node level that is a child level of the third node level;
and
heapifying the hardware binary tree by heapifying the first and third node levels and the second node level in an interleaving manner in machine cycles of the host system, by generating one or more indication signals, wherein heapifying the hardware binary tree comprises:
heapifying data elements stored in nodes of the first node level and the third node level in a first cycle of the machine cycles;
and
heapifying data elements stored in nodes of the second node level in a second cycle of the machine cycles,
wherein heapifying the data elements stored in the nodes comprises receiving the data elements from a corresponding multiplexer, sequentially performing comparison on two of the received data elements, and updating the node according to a result of the comparison.

4 more elements

A non-transitory computer readable medium that stores a set of instructions that is executable by at least one processor of a computer system to cause the computer system to perform a method for heapifying a hardware binary tree that comprises K nodes distributed across N node levels, each of the K nodes being a hardware node comprising interface circuitry and storage circuitry, wherein K and N are integers greater than three, the method comprising:

assigning and storing K initial data elements received by the interface circuitry of the K nodes from a host system to the storage circuitry of the K nodes, the N node levels comprising a first node level, a second node level that is a child level of the first node level, a third node level that is a child level of the second node level, and a fourth node level that is a child level of the third node level;
and
heapifying the hardware binary tree by heapifying the first and third node levels and the second node level in an interleaving manner in machine cycles of the host system, by generating one or more indication signals, wherein heapifying the hardware binary tree comprises:
heapifying data elements stored in nodes of the first node level and the third node level in a first cycle of the machine cycles;
and
heapifying data elements stored in nodes of the second node level in a second cycle of the machine cycles,
wherein heapifying the data elements stored in the nodes comprises receiving the data elements from a corresponding multiplexer, sequentially performing comparison on two of the received data elements, and updating the node according to a result of the comparison.

4 more elements

Dependencies are inferred from the claim text.

Performing a top-k function using a binary heap tree

Life of this patent

Performing a top-k function using a binary heap tree

Life of this patent

Abstract

Claims19