ログイン 新規登録
言語:

WEKO3

  • トップ
  • ランキング
To
lat lon distance
To

Field does not validate



インデックスリンク

インデックスツリー

メールアドレスを入力してください。

WEKO

One fine body…

WEKO

One fine body…

アイテム

  1. 研究報告
  2. アルゴリズム(AL)
  3. 2013
  4. 2013-AL-144

AGPUモデルでの並列ソートアルゴリズムの計算量について

https://ipsj.ixsq.nii.ac.jp/records/91775
https://ipsj.ixsq.nii.ac.jp/records/91775
ed41a3eb-63cc-4f83-bc4b-28aa3c6fb455
名前 / ファイル ライセンス アクション
IPSJ-AL13144012.pdf IPSJ-AL13144012.pdf (577.4 kB)
 2100年1月1日からダウンロード可能です。
Copyright (c) 2013 by the Institute of Electronics, Information and Communication Engineers
This SIG report is only available to those in membership of the SIG.
AL:会員:¥0, DLIB:会員:¥0
Item type SIG Technical Reports(1)
公開日 2013-05-10
タイトル
タイトル AGPUモデルでの並列ソートアルゴリズムの計算量について
タイトル
言語 en
タイトル On Complexities of Parallel Sort Algorithms on AGPU model
言語
言語 jpn
資源タイプ
資源タイプ識別子 http://purl.org/coar/resource_type/c_18gh
資源タイプ technical report
著者所属
国立情報学研究所
著者所属
国立情報学研究所
著者所属
国立情報学研究所
著者所属(英)
en
National Institure of Informatics
著者所属(英)
en
National Institure of Informatics
著者所属(英)
en
National Institure of Informatics
著者名 小池, 敦 定兼, 邦彦 Hoa, Vu

× 小池, 敦 定兼, 邦彦 Hoa, Vu

小池, 敦
定兼, 邦彦
Hoa, Vu

Search repository
著者名(英) Atsushi, Koike Kunihiko, Sadakane Hoa, Vu

× Atsushi, Koike Kunihiko, Sadakane Hoa, Vu

en Atsushi, Koike
Kunihiko, Sadakane
Hoa, Vu

Search repository
論文抄録
内容記述タイプ Other
内容記述 本稿ではAGPUモデルにおける並列ソートアルゴリズムの計算量を扱う.まず,既存のバイトニックソートとGPU-Warpsortの計算量を解析する.次に,AGPUモデルでの比較ソートのI/O計算量の下界を与える.1マルチプロセッサ内のコア数をb, 総コア数をp, マルチプロセッサ内の総共有メモリ量をMワードとすると,n要素の比較ソートに必要なグローバルメモリ読み込み回数はΩ(n/blog M/p n/b)である.さらに,I/O計算量がこの下界に一致するソートアルゴリズムを提案する.時間計算量はO(n/p log n/b log b) である.
論文抄録(英)
内容記述タイプ Other
内容記述 This paper is concerned with complexities of parallel sorting algorithms on AGPU model. First, we analyze known sort algorithms such as bitonic sort and GPU-Warpsort. Next, we give a lower bound of I/O complexities of comparison-based sorting algorithms on AGPU model. Let b be the number of cores in a multiprocessor, p be the total number of cores, and M be the total number of words in shared memories in multiprocessors. Then the necessary number of global memory accesses to comparison-sort n elements is shown to be Ω(n/b log M/p n/b). We also propose a sorting algorithm whose I/O complexity matches this lower bound. Its time complexity is O(n/p log n/b log b).
書誌レコードID
収録物識別子タイプ NCID
収録物識別子 AN1009593X
書誌情報 研究報告アルゴリズム(AL)

巻 2013-AL-144, 号 12, p. 1-6, 発行日 2013-05-10
Notice
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
出版者
言語 ja
出版者 情報処理学会
戻る
0
views
See details
Views

Versions

Ver.1 2025-01-21 15:18:14.136296
Show All versions

Share

Mendeley Twitter Facebook Print Addthis

Cite as

エクスポート

OAI-PMH
  • OAI-PMH JPCOAR
  • OAI-PMH DublinCore
  • OAI-PMH DDI
Other Formats
  • JSON
  • BIBTEX

Confirm


Powered by WEKO3


Powered by WEKO3