SAISort: An Energy Efficient Sorting Algorithm for Many-Core Systems

Abstract:

Energy efficiency is an important aspect of nearly all computing systems for applications ranging from large data centers to mobile devices. Many applications, especially those used in data centers, make heavy use of sorting algorithms. This thesis proposes the implementation of a novel sorting algorithm on a many-core chip to be used as a co-processor in conjunction with a general purpose processor. This algorithm takes advantage of the parallelism offered by a many core system to sort lists for database applications. The algorithm is implemented on the Asynchronous Array of Simple Processors second version (AsAP2) as a proof of concept. The results show that large gains in energy efficiency can be obtained for the first phase of a database sort. The implementation on the AsAP2 chip is able to sort a 10 GB list of entries into 783-entry lists using 23% of the energy a mobile i7 processor consumes during the execution of a quicksort while leaving the keys and payload attached. When sorting the keys and payloads separately, the AsAP2 implementation uses 21% of the energy compared to the i7 implementation while sorting into lists of 3,911 entries. Lowering the voltage of the AsAP2 processor allows the processor to function even more efficiently, with the AsAP2 implementation using 8% and 7% of the energy compared with their i7 counterparts for payload and key attached and separated cases respectively.

Paper

  PDF (861 KB),   (c) Copyright, 2011

Reference

Lucas Stillmaker, "SAISort: An Energy Efficient Sorting Algorithm for Many-Core Systems" Technical Report ECE-VCL-2011-2, VLSI Computation Laboratory, ECE Department, University of California, Davis, 2011.

BibTeX entry

@mastersthesis{lstill:msthesis,
   author      = {Lucas Stillmaker},
   title       = {SAISort: An Energy Efficient Sorting Algorithm for Many-Core Systems},
   school      = {University of California},
   year        = 2011,
   address     = {Davis, CA, USA},
   month       = sep,
   note        = {\url{http://www.ece.ucdavis.edu/vcl/pubs/theses/2011-2/}}
   }