Fine-Grained Energy-Efficient Sorting on a Many-Core Processor Array

Abstract:

Data centers require significant and growing amounts of power to operate, and with
increasing numbers of data centers worldwide, power consumption for enterprise workloads
is a significant concern. Sorting is a key computational kernel in large database
systems, and the development of energy efficient sorting capabilities would therefore
significantly reduce data center power usage. We propose highly parallel sorting
algorithms and mappings using a modular design for a fine-grained many-core system that
greatly decreases the amount of energy consumed to perform sorts of arbitrarily large
data sets. The memory, computational, and nearest-neighbor inter-processor communication
hardware of the many-core processor array require relatively small die area. We present
the design and implementation of several sorting variants that perform the first phase
of an external sort. They are built using program kernels operating on independent
processors in a many-core array with 256 bytes of data memory and fewer than 128
instructions per processor. The algorithms employed are simple and the vast majority of
processors contain identical programs. Compared to a quicksort implementation on an
Intel Core 2 Duo T9600 the highest throughput design achieves up to 9x higher
throughput per chip area, and the most energy efficient sort yields a 280x reduction
in energy dissipated per sorted block. Compared to a radix sort implementation on a GPU,
the highest throughput design achieves up to 22x higher throughput per chip area, and
the most energy efficient sort yields a 750x reduction in energy dissipated per sorted
block.

Paper

  PDF (655 KB),  
(c) 2012 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Digital Object Identifier: 10.1109/ICPADS.2012.93

Reference

Aaron Stillmaker, Lucas Stillmaker and Bevan M. Baas,
"Fine-Grained Energy-Efficient Sorting on a Many-Core Processor Array,"
IEEE International Conference on Parallel and Distributed Systems (ICPADS 2012), Singapore, December 2012.

BibTeX Entry

@INPROCEEDINGS{6413639, 
author={Stillmaker, Aaron and Stillmaker, Lucas and Baas, Bevan}, 
booktitle={Parallel and Distributed Systems (ICPADS), 2012 IEEE 18th
International Conference on}, title={Fine-Grained Energy-Efficient
Sorting on a Many-Core Processor Array}, 
year={2012}, 
month={dec.}, 
volume={}, 
number={}, 
pages={652 -659}, 
keywords={external sorting;fine-grained many-core;modular
programing;parallel processing;processor array;streaming sorting;}, 
doi={10.1109/ICPADS.2012.93}, 
ISSN={1521-9097},}