6

{（2-8）、（13-22）、（380-7931）、（40032-63278）}などの範囲のセットがあります。簡単にするために、それらは重複していないと仮定する場合があります（重複する範囲はすでにマージされています）。

私の目標は、{4、64、1024、16384}などの特定の「長さ」のセットの組み合わせを使用してこれらの範囲を「カバー」することです。N = 32など、最大N個の長さを使用するように制限されています。最大値を下回っている限り、使用する「長さ」の数は関係ありませんが、「余分な」領域の合計を最小限に抑えたいと考えています。つまり、最初の範囲のセットにない長さで「カバー」される数です。

（2-66）（64の1つの長さを使用）でカバーされる例{（2-8）}には、58個の「余分な」番号があります。{（2-6）、（6-10）}（4の2つの長さ）でカバーされる{（2-8）}は、2つの「余分な」数しかなく、望ましいです。

私の実際のアプリケーションでは、固定MMU TLBを事前にプログラミングして、特定の範囲のメモリアドレスのみにアクセスできるようにします（したがって、TLBミスは禁止されたアクセスを表し、それに応じて処理できます）。違反が後でではなく早くキャッ​​チされるように、可能な限り厳密に範囲をカバーしたいのですが、使用できるスロットは32個で、固定ページサイズは4個しかありません。コードを手作業で適切なレベルのパフォーマンスに調整することはできますが、この問題に対してよりエレガントで汎用的な解決策があるかどうか知りたいです。ナップサック問題に関連しているようですが、検索するのが難しいほど異なっています。

4

3 に答える 3

1

これは、最短経路問題のバリエーションとして定式化できます。

全長Mの一連の範囲を最大でNページカバーする必要があります。ページはL個の異なる長さを持つ可能性があり、整列されていません (任意のアドレスに配置される可能性があります)。「余分な」領域の合計とページの合計の長さの差は定数Mに等しく、ページの合計の長さを最小限に抑えることができます。

この問題に関連するグラフを作成してみましょう。任意の範囲内の各メモリ アドレスには、グラフ内の対応する頂点があります。各頂点には、指定されたアドレスから始まるL pagesに対応するL個の出力エッジがあります。各辺の長さはページの長さと同じです。各エッジは、対応するページが終了する場所に応じて、グラフ内のいくつかの頂点に到達します。

  1. ページは空いている位置で終了します。エッジは、この位置の後の最初の範囲の開始アドレスに対応する頂点に来ます。
  2. ページはある範囲内で終了します。ページのエンドアドレスに対応する頂点にエッジが来る。
  3. ページが占有されていない位置で終了し、任意の範囲のアドレスよりも大きいアドレスがあります。エッジが目的の頂点に到達します。(最初の範囲の開始アドレスはソース頂点に対応し、これら 2 つの頂点間の最短パスを見つける必要があります)。

結果のグラフはDAGであるため、頂点をトポロジー順 (または、より単純に、対応するメモリ アドレスの順) に処理することにより、線形時間で最短パスを見つけることができます。

頂点ごとに、Nペアの配列 {path-length, back-pointer} を保持します。最短パス アルゴリズムが任意の頂点を訪問している間、パス内のホップ数でこの配列にインデックスを付けます。パスが格納されているパス長よりも短い場合は、{パス長、バック ポインター} を置き換えます。すべての頂点が処理されたら、目的の頂点に属するペアの配列で最短パスを見つけ、バックポインターを使用してパスを再構築します。このパスは、最適なカバーについて説明しています。

最悪の場合の時間計算量 O(L*M*N) は、エッジの最大数 (L*M) と、各頂点に属する配列内の要素の数 (N) によって決まります。範囲がまばらな場合、ほとんどのエッジはある範囲の開始アドレスに到達し、内部アドレスに対応するほとんどの頂点は使用されず、時間の複雑さははるかに少なくなります。

このアルゴリズムは O(M*N) スペースを必要としますが、疎な範囲の場合、すべてのグラフ頂点 (またはおそらくすべての長さ/ポインターのペア) をハッシュ マップに入れると、これが大幅に減少する可能性があります。

于 2012-09-24T18:40:28.297 に答える
0

各長さが最後の倍数である場合に機能する、ボトムアップの貪欲なアプローチ:

すべての範囲を最小限にカバーする最小長の間隔のセットから始めます。最大範囲カウントを下回るまで、最長ランを繰り返しマージします。

あなたの場合、TLB では、問題を少し複雑にするアライメント制約がある可能性があります。

于 2012-09-24T16:15:03.947 に答える
0

カバーしたい範囲は非常に低い値の間隔 (「範囲」と呼びます) であり、ギャップ (「エクストラ」と呼びます) は非常にコストのかかる間隔であると考えてください。ここで、すべての「範囲」をカバーし、いくつかの「追加」を含む可能性がある最大 N 間隔 (「カバー」を呼び出します) で総コストを最小化したいと考えています。以下のアルゴリズムは本質的に貪欲です。

最初に、カバーしたいすべてのインターバル (「範囲」) と、それらの間の「エクストラ」を取得します。

1）「範囲」の最小から最大までの大きな間隔でそれらをカバーします。

2) カバーの数が N になるか、コストのかかる「エクストラ」がなくなるまで、その間にある最もコストのかかる「エクストラ」(つまり、最大のスパン) を反復して削除し、余分な「カバー」を作成するとして分割をカウントします。

于 2012-09-24T16:08:55.947 に答える