3

並行して動作するはずのエラトステネスのふるいを書きましたが、そうではありません。スレッド数を増やしても計算時間が減りません。理由はありますか？

メインクラス

import java.util.Date;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class ConcurrentTest {
    public static void main(String[] args) throws InterruptedException {
        Sieve task = new Sieve();
        int x = 1000000;
        int threads = 4;
        task.setArray(x);
        Long beg = new Date().getTime();
        ExecutorService exec = Executors.newCachedThreadPool();
        for (int i = 0; i < threads; i++) {
            exec.execute(task);
        }
        exec.shutdown();
        Long time = 0L;
    // Main thread is waiting until all threads are terminated
    // ( it means that computing is done)
        while (true)
            if (exec.isTerminated()) {
                time = new Date().getTime() - beg;
                break;
            }

        System.out.println("Time is " + time);
    }
}

ふるいクラス

import java.util.concurrent.ConcurrentHashMap;

public class Sieve implements Runnable {
    private ConcurrentHashMap<Integer, Boolean> array = 
                       new ConcurrentHashMap<Integer, Boolean>();
    private int x;
    public void run() {
        while(true){
    // I am getting synchronized number to check if it's prime
            int n = getCounter();
    // If no more numbers to check, stop loop
            if( n == -1)
                break;
    // If HashMap contains number, we can further
            if(!array.containsKey(n))continue;
            for (int i = 2 * n; i <= x; i += n) {
    // Compound numbers are removed from HashMap, Eg. 6, 12 and much more.
                    array.remove(i);
            }
        }
    }
    private synchronized int getCounter(){
        if( counter < x)
            return counter++;
        else return -1;
    }
    public void setArray(int x) {
        this.x = x;
        for (int i = 2; i <= x; i++)
            array.put(i, false);
    }
}

異なる数のスレッドでいくつかのテストを行いました。これらは結果です:

Nr of threads 1    Time is 1850, 1795, 1825
Nr of threads 2    Time is 1845, 1836, 1814
Nr of threads 3    Time is 1767, 1820, 1756
Nr of threads 4    Time is 1732, 1840, 2083
Nr of threads 5    Time is 1791, 1795, 1803
Nr of threads 6    Time is 1825, 1728, 1707
Nr of threads 7    Time is 1754, 1729, 1686
Nr of threads 8    Time is 1760, 1717, 1817
Nr of threads 9    Time is 1721, 1699, 1673
Nr of threads 10   Time is 1661, 1722, 1718
4

1 に答える 1

4

スレッド数を増やしても計算時間が減らない

tl;dr : 問題のサイズが小さすぎます。x を 10000000 に増やすと、違いがより明確になります。ただし、それらはあなたが期待しているものではありません。

2 つのわずかな変更を加えて、8 コア マシンでコードを試しました。

  1. タイミングについては、日付に対して getTime() の代わりにSystem.nanoTime()を使用しました。
  2. 実行の終了を確認するために、スピンループではなく ExecutorServiceのawaitTerminationメソッドを使用しました。

固定スレッド プール、キャッシュされたスレッド プール、フォーク結合プールを使用して Sieve タスクを起動し、スレッド変数のさまざまな値の結果を比較してみました。

x=10000000 のマシンで次の結果 (ミリ秒単位) が表示されます。

    スレッド数 = 1 2 4 8 16
    固定スレッド プール = 5451 3866 3639 3227 3120
    キャッシュされたスレッド プール = 5434 3763 3709 3258 3078
    fork-join プール = 6732 3670 3735 3190 3102

これらの結果が示しているのは、1 つの実行スレッドから 2 つのスレッドに変更することの明らかな利点です。ただし、スレッドを追加するメリットはすぐに失われます。スレッド数が 2 から 4 までの興味深い停滞期と、最大 16 までの限界利益があります。

さらに、スレッド化メカニズムが異なれば、初期オーバーヘッドも異なることがわかります。Fork-Join プールの開始コストが、他のメカニズムよりもはるかに高くなるとは思いませんでした。

したがって、書かれているように、小さいが自明ではない問題セットに対して、2 つのスレッドを超える利点を実際に期待するべきではありません。

追加のスレッドの利点を増やしたい場合は、現在の実装を確認する必要があります。たとえば、同期された getCounter() からincrementAndGet()を使用してAtomicIntegerに切り替えたとき、同期されたメソッドのオーバーヘッドがなくなりました。その結果、4 つのスレッド番号すべてが 1000 ミリ秒程度減少しました。

于 2013-09-19T13:22:48.183 に答える