14

シーケンシャル バージョンよりもパフォーマンスを向上させるために、Java でマルチスレッド アプリケーションを作成しています。これは、0/1 ナップザック問題に対する動的計画法ソリューションの並列バージョンです。異なるパーティションに Ubuntu と Windows 7 Professional の両方を搭載した Intel Core 2 Duo を使用しています。私はUbuntuで実行しています。

私の問題は、並列バージョンが実際には順次バージョンよりも時間がかかることです。これは、スレッドがすべて同じカーネルスレッドにマップされているか、同じコアに割り当てられているためだと考えています。各 Java スレッドが個別のコアにマップされるようにする方法はありますか?

この問題に関する他の投稿を読みましたが、何も役に立たないようです。

以下は、(Thread を拡張する) KnapsackThread クラスの main() とすべての run() の終わりです。スライスとエクストラを使用して myLowBound と myHiBound を計算する方法は、各スレッドが dynProgMatrix のドメインで重複しないようにすることに注意してください。したがって、競合状態は発生しません。

    dynProgMatrix = new int[totalItems+1][capacity+1];
    for (int w = 0; w<= capacity; w++)
        dynProgMatrix[0][w] = 0;
    for(int i=0; i<=totalItems; i++)
        dynProgMatrix[i][0] = 0;
    slice = Math.max(1,
            (int) Math.floor((double)(dynProgMatrix[0].length)/threads.length));
    extra = (dynProgMatrix[0].length) % threads.length;

    barrier = new CyclicBarrier(threads.length);
    for (int i = 0; i <  threads.length; i++){
        threads[i] = new KnapsackThread(Integer.toString(i));
    }
    for (int i = 0; i < threads.length; i++){
        threads[i].start();
    }

    for (int i = 0; i < threads.length; i++){
        try {
            threads[i].join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

public void run(){
    int myRank = Integer.parseInt(this.getName());

    int myLowBound;
    int myHiBound;

    if (myRank < extra){
        myLowBound = myRank * (slice + 1);
        myHiBound = myLowBound + slice;
    }
    else{
        myLowBound = myRank * slice + extra;
        myHiBound = myLowBound + slice - 1;
    }

    if(myHiBound > capacity){
        myHiBound = capacity;
    }

    for(int i = 1; i <= totalItems; i++){
        for (int w = myLowBound; w <= myHiBound; w++){

            if (allItems[i].weight <= w){
               if (allItems[i].profit + dynProgMatrix[i-1][w-allItems[i].weight]
                        > dynProgMatrix[i-1][w])
                {
                    dynProgMatrix[i][w] = allItems[i].profit +
                                      dynProgMatrix[i-1][w- allItems[i].weight];
                }
                else{
                    dynProgMatrix[i][w] = dynProgMatrix[i-1][w];
                }
            }
            else{
                dynProgMatrix[i][w] = dynProgMatrix[i-1][w];
            }
        }
        // now place a barrier to sync up the threads
        try {
            barrier.await(); 
        } catch (InterruptedException ex) { 
            ex.printStackTrace();
            return;
        } catch (BrokenBarrierException ex) { 
            ex.printStackTrace(); 
            return;
        }
    }
}

アップデート：

ブルート フォースを使用する別のバージョンのナップザックを作成しました。このバージョンでは、1 つのスレッドの実行の最後に bestSoFar 変数を更新するだけでよいため、同期はほとんどありません。したがって、各スレッドは、最後の小さなクリティカル セクションを除いて、ほぼ完全に並行して実行する必要があります。

これをシーケンシャルブルートフォースと比較して実行しましたが、それでも時間がかかります。スレッドが同じコアまたは同じネイティブ スレッドにマップされているため、スレッドが順次実行されているという以外の説明はありません。

誰か洞察力がありますか？

4

3 に答える 3

1

各ワーカースレッドが終了するまでにかかる時間を確認することをお勧めします。おそらく、スレッドの1つにははるかに難しいタスクがあります。その場合、同期などによって引き起こされるオーバーヘッドは、スレッド化から得たものを簡単に使い果たしてしまいます。

于 2009-12-13T14:49:29.520 に答える