文献

J-GLOBAL ID：201502209220484780   整理番号：15A0303498

スレッド間パイプによる逐次化を用いたハッシュ表の並列構築手法

著者 (5件)： 中山誠 (NTTドコモ 先進技研) ,  中山誠 (早稲田大) ,  山崎憲一 (芝浦工大) ,  田中聡 (NTTドコモ 先進技研) ,  笠原博徳 (早稲田大)
資料名： 電子情報通信学会論文誌 D(Web)
巻： J97-D  号： 10  ページ： 1541-1552 (WEB ONLY)  発行年： 2014年10月01日 
JST資料番号： U0473A  ISSN： 1881-0225  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： ハッシュ表を複数スレッドから並列操作するには逐次化手段が必要となる。ロックによらない,任意のスレッド数における共有データの無待機な逐次化にはCAS(Compare-And-Swap)命令が必要であることが示されて以来,CAS命令を用いた並列操作可能なハッシュ表が多数提案されてきた。しかし,CAS命令はオーバーヘッドの大きい命令である。また,複数スレッドがCAS命令に競合した場合,CAS命令に失敗したスレッドの操作は破棄されるため,競合が多い状況ほどオーバーヘッドは更に増える。本論文では,並列処理中における逐次化の対象をハッシュ表へのキー/値の登録操作に限定し,ロックやCAS命令を用いないハッシュ表の並列構築手法を提案する。提案手法により,ハッシュ表への登録操作頻度が高い状況でも,並列処理によって構築時間を短縮できることを示す。(著者抄録)

シソーラス用語： *表 ,  *ハッシュ関数 ,  *データ構造 ,  *並列処理 ,  *マイクロプロセッサ ,  *スレッド ,  辞書 ,  配列 ,  連想 ,  衝突 ,  木構造 ,  部分グラフ ,  シーケンシャル処理
準シソーラス用語： ハッシュテーブル ,  マルチコア ,  逐次処理

分類 (2件)： システムプログラミング一般  (JD03010Y) ,  制御方式  (JC02030K)

引用文献 (26件)：

• 中山 誠, 山崎憲一, 田中 聡, 笠原博徳,“重複部分木情報を利用した事前圧縮を特徴とする serde の開発と評価,”信学論 (D), vol.J96-D, no.10, pp.2089-2100, Oct. 2013.
• 新田 淳, 石川 博,“インメモリ db への適用に向けた実用的で安全な高並列オープンアドレスハッシュテーブル,”情報処理学会論文誌. データベース, vol.5, no.3, pp.126-140, 2012.
• IBM,“System/370 principles of operation, manual number ga22-7000,”1970.
• S.A. Bahra,“Nonblocking algorithms and scalable multicore programming,”CACM, vol.56, Issue 7, pp.50-61, 2013.
• 新田 淳, 石川 博,“インメモリ db への適用に向けた実用的なロックフリーハッシュテーブル,”情報処理学会研究報告. データベース・システム研究会報告, vol.153, no.35, pp.1-9, 2011.

タイトルに関連する用語 (5件)： スレッド ,  パイプ ,  逐次 ,  構築 ,  手法