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

中山 誠
山崎 憲一
田中 聡
笠原 博徳

誌名
電子情報通信学会論文誌 D   Vol.J97-D    No.10    pp.1541-1552
発行日: 2014/10/01
Online ISSN: 1881-0225
DOI: 
論文種別: 論文
専門分野: 情報・システム基礎
キーワード: 
ハッシュ表,  並列処理,  スレッド間通信,  

本文: PDF(1.6MB)>>
論文を購入



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