US 10,095,765 B1Granted

Method and apparatus for a hardware-implemented AVL tree module

AssigneeMarvell International Ltd.

InventorsTianan Tim Ma, Timothy J. Donovan

Life of this patent

Estimating the term…

Loading patent…

Abstract

The present disclosure describes techniques and apparatuses for a hardware-implemented Adelson-Velskii and Landis' (AVL) tree module. In some aspects, commands are received at the AVL tree module that request operations be performed for an AVL tree table stored in memory. Each command is written to one of multiple hardware threads of the AVL tree module that perform AVL tree operations by causing records of the AVL tree table to be read from memory using a single read operation and then written to the AVL tree module, modifying those records without accessing memory, and causing modified records to be written back to memory using a single write operation. Once a command is written to a hardware thread, the hardware thread can perform the corresponding AVL tree operation. After the AVL tree operation is performed, results are returned to the requesting agent to indicate whether the AVL tree operation was performed successfully.

Claims20

Dependent claims

A method comprising:

receiving, at an Adelson-Velskii and Landis' (AVL) tree module that is implemented in hardware, a command requesting that the AVL tree module perform an associated AVL tree operation for an AVL tree table stored in a memory, the command having been received at the AVL tree module from an agent via an interface of the AVL tree module, and the AVL tree table including records stored in the memory;
writing the command to a first hardware thread of multiple prioritized hardware threads of the AVL tree module, wherein the multiple prioritized hardware threads have fixed priorities and at least one of the multiple prioritized hardware threads (i) has a different priority from another one of the multiple prioritized hardware threads and (ii) is configured to perform AVL tree operations that are associated with a respective priority of the hardware thread, in part, by:
(i) causing one or more of the records stored in the memory as part of the AVL tree table to be read from the memory using a single read operation,
(ii) causing one or more of the read records to be written to the AVL tree module to perform an AVL tree operation associated with the respective priority of the hardware thread,
(iii) causing one or more of the written records to be modified without accessing the memory, and
(iv) causing one or more of the modified records to be written back to the memory using a single write operation;
employing the first hardware thread to which the command is written to perform the associated AVL tree operation, the first hardware thread employed based at least in part on being a highest priority thread having an input command written thereto;
and
subsequent to the first hardware thread performing the associated AVL tree operation, returning results of the associated AVL tree operation to the agent via the interface, wherein the results indicate to the agent whether the associated AVL tree operation was successfully performed by the AVL tree module.

6 more elements

A device comprising:

a memory configured to store an Adelson-Velskii and Landis' (AVL) tree table that is representative of an AVL tree, the AVL tree table including records stored in the memory;
an AVL tree module implemented in hardware, wherein the AVL tree module (i) includes an interface to receive, from an AVL agent, commands requesting that the AVL tree module perform corresponding AVL tree operations for the AVL tree table, (ii) includes multiple prioritized hardware threads that are usable by the AVL tree module to perform the corresponding AVL tree operations associated with a priority of a respective hardware thread of the multiple hardware threads, and (iii) is configured to write one or more of the commands received via the interface to the respective hardware thread of the multiple prioritized hardware threads, and wherein at least one of the multiple prioritized hardware threads is configured to:
perform the AVL tree operations that correspond to the commands written to the hardware thread, in part, by:
(i) causing one or more of the records stored in the memory as part of the AVL tree table to be read from the memory using a single read operation,
(ii) causing one or more of the read records to be written to the AVL tree module to perform an AVL tree operation associated with the respective priority of the hardware thread,
(iii) causing one or more of the written records to be modified without accessing the memory, and
(iv) causing one or more of the modified records to be written back to the memory using a single write operation,
halt an AVL tree operation being performed when a command is written to another hardware thread of the multiple prioritized hardware threads, the other hardware thread having a higher priority than the hardware thread at which the AVL tree operation is being performed;
and
subsequent to performing one of the AVL tree operations that corresponds to one of the commands written to the hardware thread, output results of the one of the AVL tree operations, the results indicating to the AVL agent whether the one of the AVL tree operations was successfully performed by the AVL tree module.

7 more elements

One or more computer-readable memory devices embodying processor-executable instructions that, responsive to execution by a processor, implement operations to:

cause an Adelson-Velskii and Landis' (AVL) tree module, that is implemented in hardware, to receive a command requesting that the AVL tree module perform an AVL tree operation for an AVL tree table stored in a memory, the command having been received at the AVL tree module from an agent via an interface of the AVL tree module, and the AVL tree module including records stored in the memory;
cause the command to be written to a hardware thread of multiple prioritized hardware threads of the AVL tree module, wherein the hardware thread is configured to perform AVL tree operations that are associated with a respective priority of the hardware thread, in part, by:
(i) causing one or more of the records stored in the memory as part of the AVL tree table to be read from the memory using a single read operation,
(ii) causing one or more of the read records to be written to the AVL tree module to perform an AVL tree operation associated with the respective priority of the hardware thread,
(iii) causing one or more of the written records to be modified without accessing the memory, and
(iv) causing one or more of the modified records to be written back to the memory using a single write operation;
cause the hardware thread to begin performing the AVL tree operation requested by the command;
determine that a command is written to another hardware thread that has a higher priority than a priority of the hardware thread;
determine, based at least in part on a portion of the operation being performed, whether to complete the operation requested by the command or place the operation requested by the command on hold;
and
subsequent to the first hardware thread performing the AVL tree operation, cause results of the AVL tree operation to be returned to the agent via the interface, the results indicating to the agent whether the AVL tree operation was successfully performed by the AVL tree module.

8 more elements

Dependencies are inferred from the claim text.