読者です 読者をやめる 読者になる 読者になる

たまにゃんのメモ帳

情報系関連のメモ書きを主に載せていきます。あわよくば他の人の参考になれば...

Concurrency without Locking in Parallel Hash Structures used for Data Processing(2012)

研究 論文

URL : http://www.waset.org/journals/waset/v61/v61-5.pdf

  1. Abstract
    • ロックとかセマフォとかバリアーとか従来の方法ではなく、現代のマルチスレッドアーキテクチャにおいてより有効な別の方法とマルチスレッドでのConcurrent Hash Tableについて考える。
    • 特にメモリシステムとメモリアクセスの特性にフォーカスを当てた環境ので並列ハッシュテーブルの効果についての理解を目的とする。
  2. Introduction
    • 高速化のためにはアルゴリズムの計算量、データ移動のコスト、メモリのレイアウト、データ構造の使用パターンなどが重要である。
    • この論文の目的は、主なパフォーマンス要因を特定し、その要因を計測することで、マルチコアCPUを有効活用するための様々な方法を提供する。
    • この研究のモチベーションは大規模WebのLogデータの処理である
    • データ処理にはハッシュテーブル必要だよね
    • 構成
      1. 現在の環境において並列アルゴリズムのパフォーマンスの要因を特定し、ロックを使ったハッシュテーブルの近年の研究を述べる
      2. 従来のロックを使う方法を説明する
      3. ロックとかセマフォとか伝統的な同期手法を使わないでそれぞれのスレッドが協力するようなロックフリーなハッシュテーブルの詳細な実装方法について述べる
      4. 計測結果を従来の方法と改善した方法で評価し分析する
      5. まとめ
  3. 関連研究
    • 逐次処理におけるパフォーマンスの要因 
      • パフォーマンスでも最も重要なのは計算量
      • データ、メモリ集約型のアプリケーションにおいて、パフォーマンスで次に重要なのはメモリアクセスの特性
    • 並列実行と排他処理
      • ハッシュテーブルの並列処理のいくつかの実装方法はロックを利用した同期方法を利用している。一つのハッシュテーブルレベルでのロックは簡単にボトルネックになりうる。それゆえ、改善するために発展させなければならない。
      • 2ロックレベル(グローバルのロックとそれぞれのバケットのロック)
      • リーダーとライターのロック
  4. Concurrent Hash Table の実装
    1. Rule-Based Cooperation
      • 従来のロックベースのシナリオと比べて一種の逆の作業割り当てをする
      • nスレッドでn個の領域に分解し、それぞれのスレッドがその領域を担当する
  5. 計測と結果
    • 3種類のタイプの実装を比較
      1. high-level section lock(2種類のロック?)
      2. CAS
      3. rule-based co-operation
    • 計測マシン
    • 50%の挿入と50%の参照と10%の挿入と90の参照の2つを計測