メモリ範囲とアクセスモードのリストからデータ依存性DAGを生成するための効率的なアルゴリズム

あなたは与えられたと仮定します:

  1. xとyが範囲の下限と上限を表す負でない整数である形式[x、y]のN(必然的には区別できない)メモリ範囲のリスト。
  2. N個のメモリアクセスモードのリスト(読み書き)

メモリアクセスリストの$ i ^ {th} $エントリは、データアクセスモードリストの$ i ^ {th}
$エントリに従ってアクセスされます(読み書きされます)。

おそらく重複するメモリ範囲への後続のアクセス間の依存関係を表すデータ依存性DAGを効率的に生成するにはどうすればよいですか?

DAGは冗長な依存関係を持つべきではありません。理想的には、アルゴリズムはN(または可能であればより良い)で2次の実行時間を持つ必要があります。

更新:明確にするために、2つのメモリアクセス間の依存関係が存在します。

  1. アクセスされる2つのメモリ範囲が重複しています(つまり、少なくとも1バイトは共通です)。
  2. 少なくとも1つのアクセスモードが書き込みです(同じメモリ範囲からの同時読み取りはOKです)。
ベストアンサー

作成されたすべての範囲を格納する間隔ツリーを作成します。そのデータ構造により、特定のメモリアドレスに対して、最後に書き込まれた時刻を効率的に判断することができます。

特に、操作を時系列順にスキャンします。書き込み操作が表示されたら、間隔ツリーを更新します。また、操作(読み取りまたは書き込み)ごとに、間隔ツリーを調べて、それが重なっている間隔をすべて見つけますを作成し、DAGに追加します。これにより、冗長性のない依存性DAGが構築されます。

ツリーに対する各更新は、$ O( log N)$ timeで実行できます。また、オーバーラップチェックは$ O(k +
log N)$で実行できます。$ k $は、その特定のクエリで重複する間隔の数です。

実行時間は、結果の依存関係グラフのサイズに依存しますが、そのグラフの$ Mエッジがある場合、合計実行時間は$ O(M + N
log N)$になります。特に、このDAGは最大$ O(N ^ 2)$のエッジを持つことができるため、アルゴリズムは確実に$ O(N
^ 2)$時間で実行されます。結果の依存性DAGが疎であれば、はるかに高速です。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です