Vector Binary Search Algorithm
Original Publication Date: 1979-Jul-01
Included in the Prior Art Database: 2005-Feb-20
In binary search, a single processing pipeline usually cannot be fully utilized because of branching and data dependency. A vector processing solution toward full utilization is presented. Consider a binary tree as set forth in the figure, which has n nodes and m levels, with n = 2 1 and m >1. Suppose each nonleaf node represents an entry of a directory. A binary search is a process to locate a particular leaf of the tree that matches a search key. A vector binary search is a process which consists of k independent searches, with k>>1.