3

そこで、特定の数までのすべての素数を見つけるために、以下のメソッドを作成しました。それをスピードアップする方法に関する提案はありますか？

私はそう呼んでいます。

interval = (value + NOOFTHREADS - 1) / NOOFTHREADS;
int max = interval * NOOFTHREADS;

tickets = new List<int>(NOOFTHREADS);
for (int i = 1; i <= NOOFTHREADS; i++)
{
    tickets.Add(i * (max / NOOFTHREADS));
}

Enumerable.Range(1, NOOFTHREADS)
.AsParallel()
.ForAll(_ => findPrimes());

いくつかのグローバル変数を使用。

static List<int> vals = new List<int>();
static List<int> tickets;
static int interval = new int();

そして方法。

public static void findPrimes()
    {
        int myTicket;
        lock (tickets)
        {
            myTicket = (int)tickets.Last();
            tickets.RemoveAt(tickets.Count - 1);
        }
        var max = myTicket;
        int min = max - interval +1;
        int num;

        var maxSquareRoot = Math.Sqrt(max);
        var eliminated = new System.Collections.BitArray(max + 1);
        eliminated[0] = true;
        eliminated[1] = true;
        for (int i = 2; i < (max) / 2; i++)
        {
            if (!eliminated[i])
            {
                if (i < maxSquareRoot)
                {
                    num = ((min + i -1 )/i)*i;

                    if (num == i)
                        num = num + i;

                    for (int j =num; j <= max; j += i)
                        eliminated[j] = true;
                }
            }
        }
        for (int b = (int)min; b < max; b++)
        {
            if (!eliminated[b])
                lock(vals)
                    vals.Add(b);
        }
    }
4

4 に答える 4

5

エラトステネスのふるいはかなり簡単に並列化できます。それを別々のチャンクに分割し、各チャンクを独自にふるいにかけるだけです。あなたはその分割から始めましたが、良い結果を得るには十分ではありませんでした. どのような問題があるか見てみましょうfindPrimes()

var max = myTicket;
int min = max - interval +1;
int num;

var maxSquareRoot = Math.Sqrt(max);
var eliminated = new System.Collections.BitArray(max + 1);

BitArray0 から までのすべての数値をカバーするスレッドごとに新しい を作成しますmax。最初のチャンクを選別するスレッドでは問題ありませんが、後のスレッドでは、必要以上に多くのメモリを割り当てています。上限が高く、多くのスレッドがあるため、それ自体が問題であり、(NOOFTHREADS + 1) * limit / 2約ビットしか必要とされない場所に大まかにビットを割り当てていlimitます。スレッド数を減らしたり、制限を低くしたりしても、局所性は低下し、キャッシュ ミスが増えます。

eliminated[0] = true;
eliminated[1] = true;
for (int i = 2; i < (max) / 2; i++)

のときに外側のループを停止する必要がありますi > maxSquareRoot。その場合、ループ本体はもう生産的なことは何もしません。1 回の読み取りと 1 回または 2 回のチェックを実行するだけです。これは各反復にそれほど時間はかかりませんが、すべてのifrom から√maxto までmaxを合計するmaxと、たとえば 10 11となります。最後のチャンクだけでこれを行うと、シングルスレッドのシングルチャンクふるいよりも時間がかかる場合があります。

{
    if (!eliminated[i])

eliminated[i]i >= min(または)に対してのみ真になることができます。これi < 2は、最初のチャンクでのみ遭遇する状況ですi <= maxSquareRoot(制限がとてつもなく低い場合を除きます)。したがって、他のチャンクについては、4、6、8、9、10、12、14、... の倍数も削除しています。無駄な作業が多い。

    {
        if (i < maxSquareRoot)

maxSquareRootがたまたま素数の場合、その平方を消去しているのではなく、比較は になるはず<=です。

        {
            num = ((min + i -1 )/i)*i;

            if (num == i)
                num = num + i;

            for (int j =num; j <= max; j += i)
                eliminated[j] = true;
        }
    }
}

さて、ふるい分けが終わったら、あなたはその塊をステップスルーしますBitArray 

for (int b = (int)min; b < max; b++)
{
    if (!eliminated[b])
        lock(vals)
            vals.Add(b);
}

素数を見つけるたびに、リストをロックしvalsて素数を追加します。2 つ以上のスレッドがほぼ同時にふるい分けを行った場合、それらは互いに足を踏み入れ、ロックと待機によりプロセスがさらに遅くなります。

スペースの使用量を減らすために、各スレッドは への素数のリストを作成しmaxSquareRoot、それを使用してそのチャンク内のコンポジットを削除して、がビットBitArrayのみを必要とするようにする必要があります。max - min + 1独自のリストを作成する各スレッドはいくつかの作業を重複させますが、ここでの上限は小さいため、追加の作業はそれほど多くありません。同時読み取りアクセスがどのように処理されるかはわかりません。同期のオーバーヘッドが追加されない場合は、すべてのスレッドに対して 1 つのリストのみを使用することもできますが、それで何かが得られるとは思えません。

コードは大まかに次のようになります。

List<int> sievePrimes = simpleSieve(maxSquareRoot);
// simpleSieve is a standard SoE returning a list of primes not exceeding its argument
var sieve = new System.Collections.BitArray(max - min + 1);
int minSquareRoot = (int)Math.Sqrt(min);
foreach(int p in sievePrimes)
{
    int num = p > minSquareRoot ? p*p : ((min + p - 1)/p)*p;
    num -= min;
    for(; num <= max-min; num += p)
    {
        sieve[num] =true;
    }
}

ここで、素数をリストに追加するときにスレッドが互いに足を踏み入れるのを避けるために、各スレッドは独自の素数のリストを作成し、それを 1 つのステップで追加する必要があります (各素数を独自のロックですが、そうでない場合は驚くでしょう)

List<int> primes = new List<int>();
for(int offset = 0; offset <= max-min; ++offset)
{
    if (!sieve[offset])
    {
        primes.Add(min + offset);
    }
}
lock(vals) vals.AddRange(primes);

（そしてvals、各チャンクの再割り当てを避けるために、予想される素数の数の初期容量で作成する必要があります）

于 2012-10-09T16:08:48.597 に答える
0

私はあなたのすべてのロックが問題になるかもしれないと思います、あなたはロックを避けるように努めるべきです、それらはかなり高価です。アルゴリズムの詳細はわかりませんが、なんとかしてロックを解除してみるべきだと思います。チケットを入力できますか？それらは、すべてが完了したときにマージする独自の出力キューを持つことができますか？

于 2012-10-09T13:39:25.863 に答える
0

並列コードと直列コードのパフォーマンスに関する多くのドキュメントが既にあります。Microsoft は、並列アーキテクチャを使用するようにコードを変換する前に、並列機能の使用に関するドキュメントを読むことをお勧めします。

ここに投稿された次の Q/AI を読むことを検討してください。

ネストされた Parallel.ForEach ループ

.NET でのパフォーマンス プロファイリング

于 2012-10-09T13:23:13.587 に答える
0

その教科書の数学で読める平方根アルゴリズムを実装する理由はありますか? 素数アルゴリズムを見てください

于 2012-10-09T12:55:35.557 に答える