Method and apparatus for performing a high speed binary search in time critical environments
US7035995B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Dec 11, 2002 |
| Grant date | Apr 25, 2006 |
| Priority date | — |
| Expiry date | Jan 5, 2024 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F3/0683
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A hardware assisted searching mechanism is provided that offloads the processor from searching operations. In a preferred embodiment, the hardware assisted searching mechanism performs a binary search of an associated 32 bit register against a binary search table that is set up by the firmware of the storage system. From this binary search table, an index into other structures stored in firmware is obtained that may be used to identify a target device. For example, when a search is to be performed due to receipt of an I/O operation, the firmware, i.e. software instructions stored in the persistent memory chip that are executed by the system processor, writes a 32 bit value to a hardware register that is used by the hardware assisted searching mechanism of the present invention. The hardware assisted searching mechanism performs a binary search of a binary search table based on the contents of the hardware register and returns an index of the entry in another hardware register. This index is then used to index into a storage device mapping structure stored in the firmware that are indexed in the same manner as the binary search table. The index provides a starting point in the stora…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.