Map Sort：マルチコアプロセッサに向けたスケーラブルなソートアルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 2007-03-15
• タイトル: Map Sort：マルチコアプロセッサに向けたスケーラブルなソートアルゴリズム
• タイトル / 言語: en
• タイトル: Map Sort: A Scalable Sorting Algorithm for Multi-Core Processors
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: NECシステムデバイス研究所
• 著者所属: NECソリューション開発本部
• 著者所属(英): en
• 著者所属(英): System Devices Res. Labs, NEC Corporation
• 著者所属(英): en
• 著者所属(英): Solutions Dev. Labs, NEC Corporation
• 著者名: 枝廣, 正人; 山下, 慶子
• 著者名(英): Masato, EDAHIRO; Yoshiko, YAMASHITA
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: マルチコア向けの並列ソートアルゴリズムMap Sortを提案する。今後単体CPUの性能向上が鈍化し、プロセッサがマルチコアによって性能向上する時代では、並列対応されていないソフトウェアは計算機が進歩しても性能は向上しない。従って単体CPUでは従来と同等処理時間で、かつ並列CPUではスケーラブルに性能向上するようなアルゴリズムが必須となるが、我々はそれをスケーラブルアルゴリズムとよんでいる。本論文ではソート問題を取り上げ、新しいスケーラブルアルゴリズムMap Sortを提案する。Map Sortの時間に関する計算複雑度はN個のデータ、P台のCPUでO((N/P) log N) であり、単体CPU上での下界値O(N log Ｎ)の(1/Ｐ)である。また計算機実験の結果、単体CPU上のクイックソートと比較し、単体CPUでは同等性能、４CPUでは3倍の性能向上であることが示された。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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 O((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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12149313
• 書誌情報: 情報処理学会研究報告組込みシステム（EMB）; 巻 2007, 号 27(2007-EMB-004), p. 19-24, 発行日 2007-03-15
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会