HIERARCHICAL IN-MEMORY SORT ENGINE

摘要

A local sorting module includes a set of storage elements storing binary vectors configured in a one-dimensional (1D) or two-dimensional (2D) array structure and separated by respective comparators configured to conditionally compare and sort the binary vectors. The comparators may perform a sort using a compare-and-flip or a compare-and-swap operation. Local sorting modules may be coupled with a global sorting module for enabling a tournament sort algorithm to output values stored in storage elements one at a time until all data is outputted in a predetermined sorting order.

主权项

1. A sorting module including a two-dimensional (2D) local sorting module, the 2D local sorting module comprising:
a first data storage element; a second data storage element adjacent to the first data storage element along a first axis, whereby the first and second data storage elements are operatively connected via a first comparator; a third data storage element adjacent to the second data storage element along a second axis, wherein the second axis is substantially perpendicular to the first axis, whereby the second and third data storage elements are operatively connected via a second comparator; a fourth data storage element adjacent to the third data storage element along the first axis, and adjacent to the first data storage along the second axis, whereby the third and fourth data storage elements are operatively connected via a third comparator, and the first and fourth data storage elements are operatively connected via a fourth comparator; and wherein the first, second, third, and fourth comparators are configured to logically compare data stored in adjacent ones of the first, second, third, and fourth data storage elements according to a sorting order indicated by a processor.