Feeds:
Posts

Guest Lecture on Sorting Networks

Today, I presented a guest lecture to a class of graduate students at the University of Texas at Austin. The topic was Parallel Sorting Networks, and covered material from the seminal Introduction to Algorithms, by Cormen Leiserson and Rivest.

The problem statement: How can a random selection of N numbers be sorted in sub-linear time? Sorting is indeed a well-known problem, and there exist numerous algorithms and implementations in serially-computed software instructions. However, a sorting network is a comparison network in which multiple comparisons can be performed in parallel. The aim of the lecture was to provide a methodical construction of parallel sorting networks in hardware.

There are few assumptions on the input to such a network, consisting of N arbitrarily-ordered numbers which can be compared to one another. The expected output is a list of N numbers in a positionally-sorted order, where the sorting direction can be set to either ascending or descending order. N is assumed to be a power-of-2, but the techniques can be extended to non-power-of-2.

Besides the functional goal above, there is an efficiency goal to reduce the network complexity, i.e. number of comparisons, whilst maintaining a shallow network depth from input to output. In hardware terms, this translates to maintaining low hardware complexity whilst shortening the latency through the network. Low latency is particularly important for stability when such a system is used within an automatic feedback loop.

Chapter 28 in the aforementioned textbook on Algorithms covers this topic extremely well. The authors present a step-by-step approach to solving this problem and provide some good references. Parallel sorting is an old topic, and has been covered as far back as Donald Knuth‘s Sorting and Searching chapter in Volume 3 of The Art of Computer Programming from 1973, and further. There will likely never be an end to applications for these methods.

I concluded the talk with an application example that is very relevant to my current research. A fast and small parallel sorting network is needed within the vector quantizer of a vector-based mismatch shaper. In this case, the vector quantizer is used within the feedback loop of a Delta-Sigma data converter.