抄録/ポイント:
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
動的技術は,同時プログラムを分析するスケーラブルで有効な方法である。プログラムの全ての挙動を解析する代わりに,これらの技法は単一プログラム実行に焦点を合わせて誤りを検出する。これらの技術の重要なステップは実行時の事象間の因果的順序を定義することであり,次にベクトルクロックを用いて計算され,スレッドの論理的時間を保存する簡単なデータ構造である。ベクトルクロックの2つの基本演算,すなわち,結合とコピーは,kがスレッドの数であるΘ(k)時間を必要とする。したがって,kが大きいとき,それらは計算ボトルネックである。本研究では,プログラム実行における因果順序を計算するためのベクトルクロックを置き換える新しいデータ構造であるツリークロックを導入した。ツリークロックの連結とコピーは,修正されるエントリの数におおよそ比例する時間をとり,従って,2つの操作は,アプリケーションあたりアプリオリΘ(k)コストに悩まない。著者らは,古典的発生前(HB)部分次数を計算するために使用するとき,他のデータ構造がより小さな漸近実行時間に導くことができないという意味で,ツリークロックが最適であることを示した。さらに,ツリークロックを用いて,スケジュール可能ハプペン(SHB)と標準Mazurkiewicz(MAZ)部分次数のような他の部分次数を計算し,従って多目的データ構造であることを示した。著者らの実験は,ベクトルクロックをツリークロックで置き換えるだけで,計算が,ベンチマーク当たり平均で2.02×高速(MAZ)から2.66×(SHB)と2.97×(HB)までなることを示した。これらの結果は,ツリークロックが同時解析における広い応用を有する標準データ構造になる可能性を有することを示した。【JST・京大機械翻訳】