c - Cで並列に配列を埋める方法

Question

(サイズ n の) 配列に同じ値を log(n) 時間で並列に入力できるアルゴリズムが必要です。それは時間がかかるので単純な解決策でfor(i=0;i<=n-1;i++) T[i] = 10は不十分であることを意味します. これは PARALLEL で実行する必要があることに言及することは非常に重要です。依存症について考えていましたが、理解できないようです。O(n)O(log(n))

Answer 1

この単純なループとして自分自身を混乱させる方法が複数ある可能性があります

for (i = 0; i <= (SIZE / 2); i++) {
    arr[i]=10;
    arr[SIZE-(i+1)]=10;
}

これは単に o(n/2) であると感じさせますが、実際には値のn時間をメモリに書き込む必要があります。したがって、どちらの方法をとっても、最終的には割り当て操作時間を実行することになりますn。

Answer 2

他の人が対処した "O(log n)" と呼ぶことに伴う問題は無視しますが、代わりに解決策を概説したいと思います。openMPに慣れていない場合、これは共有メモリ計算用の並列フレームワークです。

#pragma omp parallel for shared(T)
for(int i = 0; i < n; i++) T[i] = 10;

(n / log(n)) 個のプロセッサがある場合でも、O(n) 個の作業を行うことになりますが、各プロセッサは O(n / (n / log(n))) 個の作業、または O を実行するだけで済みます。 (ログ n)。これはおそらくあなたが望むものです。

これは、この問題の実現可能性にとって何を意味するのでしょうか?

n     #num procs
4     2
16    4
256   32
65536 4096

この問題への対処は、要素数が 16 以上、要素数が 256 以下の配列の場合にのみ意味があると結論付けることができます(この問題があなたにとって非常に重要な場合は、512 まで、さらには 1024 まで上げることができます)。

分散マシンへの移行は、もう 1 つの問題です。必要なノードの数が O(n / log(n)) で増加しているため、配列を収集するための通信コストは、初期化の並列処理を大幅に上回ります。配列を作成したノードですべての計算を行う必要があります。

Answer 3

n 個のプロセッサを使用して n 個のスレッドを実行するO(1)* n = O(n)と、合計でもプロセッサになります (そして、パフォーマンスはひどいものになります)。

tスレッド ( )を実行するt=n/factorと、配列の大きさによってはパフォーマンスが向上する場合があります (プロセッサの数が多い場合、非常に大きな配列でもパフォーマンスが向上します)。しかし、要点は、まだO(n).

何らかの条件に基づいて特定の操作をスキップできる場合にのみ、何かをO(logn)実行できます (たとえば、並べ替えられた配列のバイナリ検索)。配列内の n 要素を初期化するには、n 要素すべてにアクセスする必要があります。単にあなたが望むことは不可能です。