Presentation 2007/3/8
Map Sort : A Scalable Sorting Algorithm for Multi-Core Processors
PDF Download Page PDF download Page Link
Abstract(in Japanese) (See Japanese page)
Abstract(in English) A sorting algorithm, called Map Sort, is proposed for multi-core processors. The proposed algorithm uses a map from subsets of input data to intervals in data range. Using the map, our algorithm is executed in parallel with multiple CPUs and has 0((N/P) log N) time complexity for N data and P CPUs. Experimental results show that, in comparison with quick sort on a single CPU, processing time of Map Sort is comparable on a single CPU and three times faster on four CPUs.
Keyword(in Japanese) (See Japanese page)
Keyword(in English) Multi-Core / Parallelism / Sorting / Algorithm
Paper # CPSY2006-80,DC2006-94
Date of Issue

Conference Information
Committee DC
Conference Date 2007/3/8(1days)
Place (in Japanese) (See Japanese page)
Place (in English)
Topics (in Japanese) (See Japanese page)
Topics (in English)
Vice Chair

Paper Information
Registration To Dependable Computing (DC)
Language JPN
Title (in Japanese) (See Japanese page)
Sub Title (in Japanese) (See Japanese page)
Title (in English) Map Sort : A Scalable Sorting Algorithm for Multi-Core Processors
Sub Title (in English)
Keyword(1) Multi-Core
Keyword(2) Parallelism
Keyword(3) Sorting
Keyword(4) Algorithm
1st Author's Name Masato EDAHIRO
1st Author's Affiliation System Devices Res. Labs, NEC Corporation()
2nd Author's Name Yoshiko YAMASHITA
2nd Author's Affiliation Solutions Dev. Labs, NEC Corporation
Date 2007/3/8
Paper # CPSY2006-80,DC2006-94
Volume (vol) vol.106
Number (no) 603
Page pp.pp.-
#Pages 6
Date of Issue