A partition-merge based cache-conscious parallel sorting algorithm for CMP with shared cache

Song Hao, Zhihui Du, David A. Bader, Yin Ye

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

To explore chip-level parallelism, the PSC (Parallel Shared Cache) model is provided in this paper to describe high performance shared cache of Chip Multi-Processors (CMP). Then for a specific application, parallel sorting, a cache-conscious parallel algorithm, PMCC (Partition-Merge based Cache-Conscious) is designed based on the PSC model. The PMCC algorithm consists of two steps: the partition-based in-cache sorting and merge-based k-way merge sorting. In the first stage, PMCC first divides the input dataset into multiple blocks so that each block can fit into the shared L2 cache, and then employs multiple cores to perform parallel cache sorting to generate sorted blocks. In the second stage, PMCC first selects an optimized parameter k which can not only improve the parallelism but also reduce the cache missing rate, then performs a k-way merge sorting to merge all the sorted blocks. The I/O complexity of the in-cache sorting step and k-way merge step are analyzed in detail. The simulation results show that the PSC based PMCC algorithm can out-performance the latest PEM based cache-conscious algorithm and the scalability of PMCC is also discussed. The low I/O complexity, high parallelism and the high scalability of PMCC can take advantage of CMP to improve its performance significantly and deal with large scale problem efficiently.

Original languageEnglish (US)
Title of host publicationICPP-2009 - The 38th International Conference on Parallel Processing
Pages396-403
Number of pages8
DOIs
StatePublished - 2009
Externally publishedYes
Event38th International Conference on Parallel Processing, ICPP-2009 - Vienna, Austria
Duration: Sep 22 2009Sep 25 2009

Publication series

NameProceedings of the International Conference on Parallel Processing
ISSN (Print)0190-3918

Conference

Conference38th International Conference on Parallel Processing, ICPP-2009
Country/TerritoryAustria
CityVienna
Period9/22/099/25/09

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics
  • Hardware and Architecture

Keywords

  • Cache-conscious algorithm
  • Chip multi-processors (CMP)
  • Parallel sorting

Fingerprint

Dive into the research topics of 'A partition-merge based cache-conscious parallel sorting algorithm for CMP with shared cache'. Together they form a unique fingerprint.

Cite this