6

並列クイックソートを試しているので、100万個の整数の配列があります。私は時々次の奇妙な行動をします：

配列が正しくソートされているかどうかを確認するために、ソート後に次のコードを入力しました。

for(int j=0; j < array_parallel.length-1; ++j)
   if(array_parallel[j] > array_parallel[j+1])
    System.out.println("ERROR! NOT SORTED CORRECTLY!");

場合によっては、正しくソートされていないというエラー出力が表示され、デバッグすると次のようになります（例、常に異なる）。

j = 1942 array_parallel [1942] = 6000; array_parallel [1943] = 6000;

（特定の値や範囲ではなく、数値を無視してみてください）したがって、左の値が右の値と等しい場合は常にそうです。まあ、より大きいの比較のために、これはfalseで返されるはずですが、私は間違いなく出力を取得します。

一体何が悪いのか！？

配列をクロスチェックしたところ、正しくソートされています。小さな配列（約100）をプロットすると、それも問題ありません。私は私の心が私をだます何かを逃しましたか？

編集21:32（UTC + 1）：

private static int ANZAHL = 1000000;        // Größe des Arrays

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        int array_single[] = new int[ANZAHL];
        int array_parallel[] = new int[ANZAHL];

        Speedmeasure sp_single = new Speedmeasure();
        Speedmeasure sp_parallel = new Speedmeasure();
        ArrayReader ar = null;

        try {
            ar = new ArrayReader(array_single, array_parallel);
        } catch (FileNotFoundException e1) {
            // TODO Auto-generated catch block
            e1.printStackTrace();
        } catch (IOException e1) {
            // TODO Auto-generated catch block
            e1.printStackTrace();
        } catch (ClassNotFoundException e1) {
            // TODO Auto-generated catch block
            e1.printStackTrace();
        }

        if(ar == null) {
            System.err.println("Großes Problem. Lass es sein!");
            System.exit(-1);
        }
        else {

            for(int i=0; i < 5; ++i) {
                Quicksort_Single qs = new Quicksort_Single();
                sp_single.setStart(System.currentTimeMillis());

                qs.quicksort_start(array_single);
                sp_single.setStop(System.currentTimeMillis());

                //printArray(array);
                PrintSpeed(sp_single.getSpeed(), "Single");


                System.out.print("\nUnd jetzt treiben wir es parallel! \n\n");
                Thread t1 = new Thread(new Quicksort_Parallel(0, array_parallel.length-1, array_parallel));

                sp_parallel.setStart(System.currentTimeMillis());
                t1.start();

                try {
                    t1.join();
                } catch (InterruptedException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }

                sp_parallel.setStop(System.currentTimeMillis());

                //printArray(array_parallel);
                PrintSpeed(sp_parallel.getSpeed(),"Parallel");

                System.out.println("Speed up was: "+sp_parallel.calcSpeedup(sp_single.getSpeed(), sp_parallel.getSpeed()));
                System.out.println("******************************************");

                for(int j=0; j < array_single.length-1; ++j)
                    if(array_single[j] > array_single[j+1])
                        System.out.println("ERROR! NICHT SORTIERT KORREKT BEI SINGLE!");

                for(int j=0; j < array_parallel.length-1; ++j)
                    if(array_parallel[j] > array_parallel[j+1])
                        System.out.println("ERROR! NICHT SORTIERT KORREKT BEI PARALLEL!");



                ar.copyArray(array_single, array_parallel);
            }
        }
    }

並列ソートを開始するスレッドで結合を行います。最初のスレッドは、同時に最大4つのスレッドを生成します。デバッガーで配列がソートされていることがわかるので、同時実行性が100％わからない。2つの整数の出力を追加して、別の外観にします。

編集済み23/05/1216:46UTC + 1

私は、JDK1.7の新しい非常に簡単なForkJoinPoolで動作するようにすべてを変更していました。最大10mioの整数の整数配列でテストし、興味深い結果を得ました。Core2Duo（2010）MacBook ProおよびCore-i5（2011）Windows7でテストしました。

core2duoとi5はハイパースレッディングを実行できるので、availableProcessors（）* 2->でテストしました。core2duoは、2スレッドで1.8と1.7に高速化するために少しブーストされました。i5は現在、利用可能なProcessors（）*2ごとに最大8スレッドで3.2のスピードアップを実現しています。

まだ私のマシンのたわごとを実験しています。すべてのテストは同じアレイで実行され、平均は各アレイサイズでの1000回のソート反復から計算されました。

4

3 に答える 3

3

コードを見ると、スレッドが生成されますが、すぐにメインの実行スレッドに結合されます。

        Thread t1 = new Thread(new Quicksort_Parallel(0, array_parallel.length-1, array_parallel));

        sp_parallel.setStart(System.currentTimeMillis());
        t1.start();

        try {
            t1.join();

問題は、Quicksort_Parallelルーチンで何をしているのかということです。追加のスレッドを生成していますか？それらすべてに参加していますか？そうでない場合は、表示されている結果を説明する競合状態を作成しています。

于 2012-05-22T19:31:26.970 に答える
1

あなたは競合状態の犠牲者であるかもしれません、これはあなたの出力が他のイベントのシーケンスに依存していることを意味します。したがって、より高速に動作するスレッドが1つある場合は、競合状態になります。これを停止する方法は、セマフォを使用するか、ループをスレッド間で分割することです。お元気ですか？リダクションを使用していますか？

于 2012-05-22T19:32:04.827 に答える