2015/06/30 by Fabio Cannizzo · 7 citations
Computer Science · Mathematics · #Algorithm #Arithmetic #Artificial intelligence #Binary number #Binary search algorithm #Computer science #Context (archaeology) #Digital Filter Design and Implementation #Discrete mathematics #Mathematics #Numerical Methods and Algorithms #Overhead (engineering) #Parallel Computing and Optimization Techniques #Parallel computing #Point (geometry) #SIMD #Search algorithm #Search engine indexing #cs.DS
paper · pdf · doi:10.1016/j.jpdc.2017.10.007
published in Journal of Parallel and Distributed Computing 113, 37-54 (Elsevier BV)
openalex created_date 2017/04/07 · arxiv created 2017/09/26 · openalex publication_date 2017/11/01 · arxiv updated 2017/12/01 · openalex updated_date 2026/08/05
Given an array X of N+1 strictly ordered floating point numbers and a floating point number z in the interval [X0,XN), a common problem is to find the index i of the interval [Xi,Xi+1) containing z. This problem arises for instance in the context of spline interpolation or the computation of empirical probability distribution from empirical data. Often it needs to be solved for a large number of different values z and the same array X, which makes it worth investing resources upfront in pre-processing the array X with the goal of speeding up subsequent search operations. In some cases the values z to be processed are known simultaneously in blocks of size M, which offers the opportunity to solve the problem vectorially, exploiting the parallel capabilities of modern CPUs. The common solution is to sequentially invoke M times the well known binary search algorithm, which has complexity O(log2 N) per individual search and, in its classic formulation, is not vectorizable, i.e. is not SIMD friendly. This paper describes technical improvements to the binary search algorithm, which make it faster and vectorizable. Next it proposes a new vectorizable algorithm, based on an indexing technique, applicable to a wide family of X partitions, which solves the problem with complexity O(1) per individual search at the cost of introducing an initial overhead to compute the index and requiring extra memory for its storage. Test results using streaming SIMD extensions compare the performance of the algorithm versus various benchmarks and demonstrate its effectiveness. Depending on the test case, the algorithm can produce a throughput up to two orders of magnitude larger than the classic binary search. Applicability limitations and cache-friendliness related aspects are also discussed.