私がやっていることの基本的な考え方
連立構造形成問題・コンビナトリアル・オークションを完成させる。
N 個のエージェントのセットが与えられた場合、エージェントのセットのどの部分集合をばらばらにするかが最良の結果をもたらします。
例Agents = {a,b}とその値
{a} = 2{b} = 3{a,b} = 4
この例では、 の連立が{{a},{b}} = 5最良の結果をもたらし{a,b}ます。
つまり、問題はセットを分割し、分割の合計が元のセットよりも大きいかどうかを確認することです。(この部分は、分割の生成とデータの表現方法に関しては優れています。)
データをどのように表現するかは、基本的に値の配列であり、インデックスはセット構成です (セットは整数として表されます)。
上記の例では:
int val[4] = {0,2,3,4}設定した場所
{a} = 01 = index 1{b} = 10 = index 2{a,b} = 11 = index 3
したがって、セットは値配列のインデックスとして機能します。
2^n問題は、考慮すべき値がある多数のエージェントを指定すると、ランダムなメモリ アクセスが発生することです。
メモリアクセスの問題については、ここをスキップしてください
たとえば、20 エージェントの環境では、要素 10000000000000000001の値10000000000000000000は 1048575 インデックス離れて00000000000000000001おり、メモリ内では 4194300 バイト離れており、128 バイトの距離の 32767 キャッシュラインを表しています。したがって、恐ろしいアクセスパターン。
私が探してみた解決策には、カーディナリティ/ハミングの重みの観点からインデックスを並べ替えることが含まれます。
私の計算では、ランダムアクセスによるペナルティを覆い隠す算術オーバーヘッドに苦しんでいます。特に、シリアライズされてスレッドをブロックする多くの依存計算を使用するハミングの重みベースのインデックス作成。
最後の手段として、ここでもう一度お尋ねします。解決策がランダム アクセスに依存している場合にアクセス時間を改善する方法 (この問題に対して実行するのが難しい合体について知っています) はありますか、それとも無力な状態ですか?
現在、そのため、命令リプレイのオーバーヘッドが約 45% あり、ブロックサイズを変更しても目立った結果は得られません。はい、スレッドごとにいくつかの連合を計算することで、レイテンシを隠そうとしますが、これはある程度機能します。