k-ary search on modern processors

ABSTRACT

This paper presents novel tree-based search algorithms that exploit the SIMD instructions found in virtually all modern processors. The algorithms are a natural extension of binary search: While binary search performs one comparison at each iteration, thereby cutting the search space in two halves, our algorithms perform k comparisons at a time and thus cut the search space into k pieces. On traditional processors, this so-called k-ary search procedure is not beneficial because the cost increase per iteration offsets the cost reduction due to the reduced number of iterations. On modern processors, however, multiple scalar operations can be executed simultaneously, which makes k-ary search attractive. In this paper, we provide two different search algorithms that differ in terms of efficiency and memory access patterns. Both algorithms are first described in a platform independent way and then evaluated on various state-of-the-art processors. Our experiments suggest that k-ary search provides significant performance improvements (factor two and more) on most platforms.

REFERENCES

• 1: Cell Broadband Engine Programming Handbook.
• 2: Jatin Chhugani , Anthony D. Nguyen , Victor W. Lee , William Macy , Mostafa Hagog , Yen-Kuang Chen , Akram Baransi , Sanjeev Kumar , Pradeep Dubey, Efficient implementation of sorting on multi-core SIMD CPU architecture, Proceedings of the VLDB Endowment, v.1 n.2, August 2008 [doi>10.1145/1454159.1454171]
• 3: Code available at: wwwdb.inf.tu-dresden.de/schlegel.
• 4: Buǧra Gedik , Rajesh R. Bordawekar , Philip S. Yu, CellSort: high performance sorting on the cell processor, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 5: Sándor Héman , Niels Nes , Marcin Zukowski , Peter Boncz, Vectorized data processing on the cell broadband engine, Proceedings of the 3rd international workshop on Data management on new hardware, June 15-15, 2007, Beijing, China [doi>10.1145/1363189.1363195]
• 6: Intel Corporation. Intel AVX: New Frontiers in Performance Improvements and Energy Efficiency, March 2008.
• 7: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 8: PowerPC Microprocessor Family: Vector/SIMD Multimedia Extension Technology Programming Environments Manual.
• 9: Ronny Ronny Ronen, Larrabee: a many-core Intel® architecture for visual computing, Proceedings of the 6th ACM conference on Computing frontiers, p.225-225, May 18-20, 2009, Ischia, Italy [doi>10.1145/1531743.1531744]
• 10: Kenneth A. Ross, Conjunctive selection conditions in main memory, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543628]
• 11: K. A. Ross. Efficient hash probes on modern processors. ICDE, 0:1297--1301, 2007.
• 12: Jingren Zhou , Kenneth A. Ross, Implementing database operations using SIMD instructions, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564709]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Single-instruction-stream, multiple-data-stream processors (SIMD)

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis

General Terms:
Algorithms, Design, Performance