1

私は C++ で高性能の動的プログラムを作成しており、その結果は M × N テーブル (およそ 2000 行 × 30000 列) に配置されています。
各エントリ ( r、c ) は、テーブル内の他のいくつかの列のいくつかの行に依存します。

行rの計算をP個のプロセッサ間で並列化する最も明白な方法は、データを静的に分割することです。つまり、プロセッサpにすべての有効なkのエントリ (r, p + k P ) を計算させます。

ただし、異なる列のエントリは計算に多少異なる時間がかかります (たとえば、一方のエントリは他方のエントリの 5 倍の時間がかかる場合があります) 。早く終了する CPU は、代わりにまだ追いついている CPU から作業を盗みます。

これにアプローチする 1 つの方法は、既に計算された列の数を指定するアトミック グローバル カウンターを保持し、CPU がより多くの作業を必要とするたびにそれを増やすことです。ただし、これにより、テーブル内のすべてのエントリを計算した後、すべての CPU が同じグローバル カウンタ
にアクセスするように強制されます。つまり、プログラムがある程度シリアライズされます。各エントリの計算は多かれ少なかれ迅速なプロセスであるため、これはやや望ましくありません。

ですから、私の質問は次のとおり
です。この動的パーティショニングをよりスケーラブルな方法で実行する方法はありますか (つまり、すべてのエントリを計算した後に単一のグローバル カウンターにアクセスする必要はありません)。

4

1 に答える 1

0

新しい値に 2 番目の配列を使用していると思います。もしそうなら、TBB や Cilk Plus のループ構造がそうであるように思えます。どちらもワークスティーリングを使用して、使用可能なプロセッサ間で作業を配分し、1 つのプロセッサが作業を使い果たすと、使用可能な作業のあるプロセッサから作業を盗みます。これにより、データの「チャンキー」が均等になります。

Cilk を使用するには、Cilk Plus をサポートするコンパイラが必要です。GCC 4.9 と Intel コンパイラの両方がサポートしています。通常、次のように記述します。

cilk_for (int x = 0; x < XMAX; x++) {
    for (int y = 0; y < YMAX; y++) {
        perform-the-calculation;
    }
}

TBB の構造は似ています。

もう 1 つのアプローチは、キャ​​ッシュを意識しない方法で計算を「並べて表示」することです。つまり、計算をキャッシュ効率の良いチャンクに分割する独自の分割統治アルゴリズムを実装します。キャッシュ無視アルゴリズムの詳細については、 http://www.1024cores.net/home/parallel-computing/cache-oblivious-algorithms/implementationを参照してください。

バリー

于 2015-03-19T02:04:46.260 に答える