私は、テキストファイルから任意の整数の10000行を配列に読み込み、ターゲットに追加する3つの整数を見つけなければならないCプロジェクトを行っています値。次に、値を見つけるのにかかる時間を表示します。C - 並行スレッドを使用して目標値に追加する3つの数値を見つける
たとえば、ターゲットが233の場合、3つの数値は81/102/50になります。つまり、それらの数字がテキストファイルにある場合です。
私は3つのネストされたforループを作成して10000の整数のすべての組み合わせを見つけました。スレッドを一切使わずに約5分かかりました。
私のプロジェクトには並列スレッドの実装が含まれていますが、数値を見つけるためのより速い方法を見つけることができません。
私は、1つのスレッドが0-5000ともう1つの5000-10000の組み合わせを見つけたところで、配列を半分に分割することを考えましたが、3つの数値がどちらかにある可能性があるため動作しないことに気付きました。何か案は？
いずれかの値が負の値ですか？あなたは入力中に遭遇した最大値と最小値の記録を保持できますか？ （答え：はい、それは簡単です。外側のループでターゲットに追加できない2つの値が識別された場合は、内部ループを削除することができます）
N個の数字があるとします。次に、3つのスレッド間でワークロードを分割できるようにすることができます（例えば、細い空気から分数を引き出すなど）。
をインデックスN/3 + 1のための外部ループを動作しますループは中間インデックス+ 1で開始します。
非対称パーティショニングの理由は、最初のスレッドが他のスレッドよりも中間ループと内部ループでより多くの値を調べるためです。実際には、ワークロードを十分に歪ませていないことを期待しています。5は、おそらくより大きな数値である必要があります.3も大きくなければなりません。スレッド数が増えると、計算が難しくなります。各スレッドの負荷を大まかにバランスさせる必要があります。
あなたがF1、F2、F3、各スレッドの外側のループの範囲の分数を指定した場合、その後：
あなたはC1≈C2≈C3が必要です。 mスレッドへの一般化はかなり明確です。解決策はありません。範囲の倍数を使用するか、またはスレッド1の場合は[L1..U1]、スレッド2の場合は[L2..U2]、スレッド3の場合は[L3..U3]を指定するように命名法を変更できますL2 = U1 + 1、L3 = U2 + 1、[L1..U3]は全範囲Nをカバーする。
まず、配列をソートします。次に、3つのネストされたループの代わりに、2つのネストされたループとバイナリ検索を使用できます。 2つのネストされたループは、2つの数のすべての合計を見つけます。 2つの数値の合計を取得したら、3番目の数値は目標値からその合計を差し引いた数値に等しくなければなりません。したがって、2番目の検索を実行して、3番目の数値が配列に存在するかどうかを判断できます。
新しいアルゴリズムの速度は次のように推定できます。 3つのネストされたループは、10000 choose 3の合計を計算します。これは1670億の合計です。これは約5億回の合計です（ランタイムが5分だったとします）。
2つのネストループは、10000 choose 2部分和を計算します。それは5千万部分和です。これらの部分和のそれぞれについて、コードはバイナリ検索を実行する必要があり、最大でceil(log_2(10000)) = 14の比較が必要です。したがって、比較の合計数は7億です。
この結果、1670億の合計を7億回の比較で置き換えます。比較が合計よりも高価であると仮定すると、同時スレッドがなくても約4秒の実行時間が求められます。
同時実行性を追加するには、アレイを所有しているプロセッサコアの数で単純に除算します。コアより多くのスレッドがある場合、スレッドは実際に同時に実行されていないことに注意してください。各スレッドの外側ループは、配列の一部分のみを使用します。スレッドの内部ループは配列全体をスキャンして部分和を計算します。次にスレッドはバイナリー検索を実行して、配列に3番目の番号が存在するかどうかを調べます。
たとえば、4コアプロセッサを使用している場合、各スレッドには、アレイの1/4を使用する外側ループがあります。これにより、4分の1の速度が上がり、ランタイムが約1秒に短縮されます。
我々としても、次のようにマルチスレッドを使用することができます。
int save_num[3][8]; //To give a different cache line
omp_set_num_threads(3); Set number of threads as 3
#pragma omp parallel for
for(int i = 0; i< 10000; i++){
int local_sum = file[i];
int thread = omp_get_thread_num();
save_num[thread][1]=local_sum;
#pragma omp critical
if(save_num[0][1] + save_num[1][1] + save_num[2][1] ==233) {
break;
}
}
私はこのコードをテストしていません。論理は同じままですが。これは3つのスレッドで実行され、クリティカルセクションに1回だけ入力し、save_num変数に3つの数値を保存している間に条件が真であるかどうかをチェックします。