関連する可能性のある既知の数値的方法に関する方法は、ここに投稿してください!
バックグラウンド
各セットの配列がありvalues、各値へのインデックスは値がバインドされているセットに対応するため、セットを整数として表します。要素はビット位置を表します。たとえば、要素が 1 のセットはとして表さ...001れ1ますLSB。
したがって、セットは単なるインデックスであり、保存されることはありません。オンザフライで生成されます。これは、セットの値を表す配列内のインデックスにつながるキーです。
私が行うことは、セットが与えられ、そのセットの値よりも大きいペアごとに素なサブセットの合計値です。たとえば、set0111の値が 3 で、2 つのサブセットの値が0100 = 2との0011 = 2場合、この分割はより効果的です。セットのすべてのサブセットに対してこれを行います。
3 つのエージェントが与えられ、順序付けはセット数の表現です。
val[8] = {0,1,2,4,3,2,4,2} the values is not important, only how they are ordered
0 0 0 0 1 1 1 1 MSB bit representation of the index
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1 LSB
111 の最良の分割は 011 と 100 で、合計は 7 です。したがって、最初の要素のみを含むセットの値、つまり 001 を取得するには、要素 1 と 3(101) のセットに対して val[1] を入力します。 val[5] を入れます。
カーディナリティでグループ化した場合の val 配列の順序付け方法
val[8] = {0,1,2,3,4,2,4,2}
0 0 0 1 0 1 1 1 MSB bit representation of the index
0 0 1 0 1 0 1 1
0 1 0 0 1 1 0 1 LSB
ここでは、インデックスを配列内の正しいビンに変換する必要があるため、3 番目の要素 (100)、val[translate(4)] のみを含むセットの場合は次のようになります。サイズが >2^25 要素の配列を考えてください。さらに明確にするために、ランダムアクセスが必要な場合のランダムメモリアクセスの改善を参照してください。
ただし、カーディナリティに従ってグループ化しても、メモリ内のランダムアクセスの順序が高くなります。現在、カーディナリティによってそれらをグループ化しており、インデックスの生成は、セットが表す番号の後に並べ替えるよりも遅くなります。
カーディナリティによってグループ化されたセットでインデックスを生成する方法は、2 つの整数間の辞書式距離を決定するの回答で説明されているように、定数メモリでパスカルの三角形を使用することです。
4 つのエージェントを使用してカーディナリティによって順序付けおよびグループ化された場合に、sets 値が配置される場所
n index 1 2 4 8 3 5 6 9 10 12 7 11 13 14 15
-----------------------------------------------------
MSB 0 0 0 1 | 0 0 0 1 1 1 | 0 1 1 1 | 1
0 0 1 0 | 0 1 1 0 0 1 | 1 0 1 1 | 1
0 1 0 0 | 1 0 1 0 1 0 | 1 1 0 1 | 1
LSB 1 0 0 0 | 1 1 0 1 0 0 | 1 1 1 0 | 1
n index は、カーディナリティで順序付けされていない場合のインデックスを表します。これは、各セットの値がどこにあるかを示すためのものです。
整数セットは、直接インデックス（私が現在行っていること、ランダムアクセスを提供します）またはセットからインデックスへの変換を介して、値配列のインデックスを表します。
アイデア
セットをサブセットに分割する代わりに、ボトムアップでセットを生成することを考えました。たとえば、対ごとに互いに素なサブセットのすべてに分割0111する代わりに、ある時点で if from the sets を生成します{0100,0011},{0010,0101},{0001,0110}。
どのように、なぜ機能する必要があるのか
セットのすべての分割をカーディナリティ 3 で評価したいとします。エルゴ セット7,11,13,14です。カーディナリティ 3 のセットを分割する唯一の方法は、カーディナリティ 1 と 2 のセットに分割することであるため、カーディナリティ 1 と 2 の素集合のすべての合計が、これらのセットの和よりも大きいかどうかを評価する必要があります。
必要なものの表記（少し不備があるかもしれません）：
|C|=n,∀ a,b : a ∪ b = C , a ∩ b ={Ø}, |a|+|b| = n
そのため、各スレッドへの合体メモリアクセスを使用して値を読み取ることにより、カーディナリティ n のセットを形成するサブセットごとに、その値が形成されたセットより大きいかどうかを確認し、大きい場合は値を更新します。
簡単な例では、n = 2カーディナリティ 1 のすべての値を読み込み、それらのセットのすべての組み合わせを実行し、それに応じて更新する必要があります。この例は、すべてのセットが互いに素であるため簡単です。
pseudo code for 4 threads, input card1 is pointer to array of sets |s| =1
__shared__ int value[4];
tid = threadIdx.x;
value[tid] = card1[tid]; // coalesced memory access
int thvalue = value[tid]; // holds the value for the thread, to avoid bank conflict
int rvalue[blockDim.x/2]= 0; //holds the sum
int i = blockDim.x;
int x = 0;
//reduction loop that dont generate duplicate sets
for(;i>0;i>>=1) {
if(tid < i) {
x++;
rvalue[x-1] = value[(tid+x)%blockDim.x] + thvalue;
}
}
for(i = 0; i < x; i++) {
int index = getindex(tid,i,1); //gets the index for the set it generated, 1 represent the cardinality
if(output[index] < rvalue[i])
output[index] = rvalue[i];
}
リダクションループの繰り返し
Thread set specific for thread first iteration second iteration
0 0001 0001 + 0010 0001 + 0100
1 0010 0010 + 0100 0010 + 1000
2 0100 0100 + 1000 none
3 1000 1000 + 0001 none
ご覧のとおり、カーディナリティ 2 のセットを形成するすべてのサブセットのすべての値を取得しています。
ただし、問題は、すべてのセットが互いに素であるとは限らないため、2 より大きいカーディナリティのセットを生成するのがより難しいことです。たとえば、0001 と 0011 は互いに素ではありません。
セットはどこにも保存せず、セットの値のみを保存することに注意してください。
ついに
これを念頭に置いて、結合されたメモリを読み取るアルゴリズムを作成し、バラバラのサブセットからすべてのセットを生成する方法についてはどうでしょうか。サブセットが互いに素であるかどうかをチェックしなくても、完全に決定論的である必要があります。
賞金のために
アルゴリズムは、明確なステップがマークされたテキストまたは疑似コードで説明する必要があります。
それが機能することを例で証明する必要があります。このアルゴリズムは最大 n^32 セットになるわけではないため、適切にスケーリングする必要があります。
アルゴリズムは、2 つ以上のインスタンスに吐き出すことができます。たとえば、1 つは偶数、もう 1 つは奇数です。
あなたが使用している技術に関する情報源を参照していただければ幸いです。
アルゴリズムは、できるだけ少ない割り当てと命令を使用し、発散を回避する必要があります。しかし、あなたがこれをたくさん持っているにもかかわらず、あなたがそれを手に入れたと思うなら、試して投稿してください。私はどんな情報でも満足します.
別の方法で注文しても、説明どおりに機能する場合は、ここに投稿してください。どんな助けも本当に役に立ちます
不明な点があれば質問してください。
TL/DR 簡単な説明
私は値を持つ配列を持っています.の順序に応じて整数セットを表すZインデックス. 3,5,6,7 <-関数(この関数を実装しています)を使用して、インデックスを正しいインデックスに変換します。例: セット 3-> インデックス 4。iZ[i]Z
カーディナリティによってグループ化されたセットの値を持つことで、私が望むのは、ペアごとに素なセットの値のいずれかが、それらが形成するセットよりも大きいかどうかを確認したいということです。
たとえば、 type の値の量と type の値の量を|a| = 3, |b|+|c| =3, b ∩ c ={Ø}, |b| =1読み取り、 typeとtypeからの互いに素な部分集合(カーディナリティ 3 のセット) をすべて見つけて、それらの合計を取得します。すべてのセットが「生成」されるまで続行しますXbXcbca