{"metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00091775","sets":["1164:2592:7086:7157"]},"path":["7157"],"owner":"11","recid":"91775","title":["AGPUモデルでの並列ソートアルゴリズムの計算量について"],"pubdate":{"attribute_name":"公開日","attribute_value":"2013-05-10"},"_buckets":{"deposit":"eeb635fc-4750-4d30-a220-0a251c511d7e"},"_deposit":{"id":"91775","pid":{"type":"depid","value":"91775","revision_id":0},"owners":[11],"status":"published","created_by":11},"item_title":"AGPUモデルでの並列ソートアルゴリズムの計算量について","author_link":["0","0"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"AGPUモデルでの並列ソートアルゴリズムの計算量について"},{"subitem_title":"On Complexities of Parallel Sort Algorithms on AGPU model","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"2013-05-10","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"国立情報学研究所"},{"subitem_text_value":"国立情報学研究所"},{"subitem_text_value":"国立情報学研究所"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"National Institure of Informatics","subitem_text_language":"en"},{"subitem_text_value":"National Institure of Informatics","subitem_text_language":"en"},{"subitem_text_value":"National Institure of Informatics","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/91775/files/IPSJ-AL13144012.pdf"},"date":[{"dateType":"Available","dateValue":"2100-01-01"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-AL13144012.pdf","filesize":[{"value":"577.4 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"0","billingrole":"9"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"7c135197-a585-4595-8454-46854b588b19","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2013 by the Institute of Electronics, Information and Communication Engineers\nThis SIG report is only available to those in membership of the SIG."}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"小池, 敦"},{"creatorName":"定兼, 邦彦"},{"creatorName":"Hoa, Vu"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Atsushi, Koike","creatorNameLang":"en"},{"creatorName":"Kunihiko, Sadakane","creatorNameLang":"en"},{"creatorName":"Hoa, Vu","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN1009593X","subitem_source_identifier_type":"NCID"}]},"item_4_textarea_12":{"attribute_name":"Notice","attribute_value_mlt":[{"subitem_textarea_value":"SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc."}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_18gh","resourcetype":"technical report"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"本稿では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) である．","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"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).","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"6","bibliographic_titles":[{"bibliographic_title":"研究報告アルゴリズム（AL）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2013-05-10","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"12","bibliographicVolumeNumber":"2013-AL-144"}]},"relation_version_is_last":true,"weko_creator_id":"11"},"id":91775,"updated":"2025-01-21T15:18:15.180036+00:00","links":{},"created":"2025-01-18T23:40:56.303129+00:00"}