3

2 つのスレッドを使用して 2 つの行列を乗算しています (ただし、プログラムは同様にスケールアップするように記述されているため、代わりに 3 つ、4 つなどのスレッドを使用することもできます)。各スレッドは、最終的な行列の 1 つの行 (または列) の作業を計算/実行します。1 つのスレッドが行で作業を行っている場合、他のスレッドはその行で作業してはなりません。次の使用可能な行に移動する必要があります。

まず、問題を実装した方法が正しいかどうかはわかりません。見やすい方法があれば教えてください。

第二に、私が行った方法では、テストするたびに (さまざまなサイズのマトリックスで、巨大なマトリックスでも)、1 つのスレッドだけが作業を行います。つまり、毎回、同じスレッドが run() メソッドの同期ブロックにアクセスします。他のスレッドは run() メソッドに入っていますが、常に 1 つのスレッドだけがロックを取得してすべての作業を行っているのはなぜでしょうか?

これは私の実行方法です：

 public void run() {
    System.out.println(Thread.currentThread().getName());
    while (i < number of columns in final matrix) {
        synchronized (this) {
            if (i < number of columns in final matrix) {
                for (int j = 0; j < Main.B[0].length; j++) { 
                    for (int k = 0; k < Main.A[0].length; k++) { 
                        Main.C[i][j] += Main.A[i][k] * Main.B[k][j];
                    }
                }
                i++;
            }
        }
    }
}

これは、スレッドを作成してプログラムを開始するドライバー クラスのコードです。

MyRunnable r = new MyRunnable();
Thread thread1 = new Thread(r);
Thread thread2 = new Thread(r);
thread1.start();
thread2.start();

try {
    thread1.join();
    thread2.join();
    } catch (InterruptedException ie) {
        System.out.println("\nThe following error occurred: " + ie);
        }
    }

私の質問は 2 つあると思います。私のアプローチは目前の問題に対して正しいですか? もしそうなら (もしそうでなければ) 1 つのスレッドが常にロックを取得し、すべての作業を行っているのはなぜですか? 20x20 行列で最大 6 つのスレッドを使用してプログラムをチェックしましたが、常に 1 つのスレッドだけが作業を行っています。

4

5 に答える 5

5

コメントのいくつかが示唆しているように、問題はロック（つまりsynchronized(this)パーツ）にあります。同期が行われ、thisこの場合、の単一のインスタンスでMyRunnableあるため、1つのスレッドがブロック内で作業を行っている間、synchronized他のすべてのスレッドは作業が終了するまで待機します。したがって、事実上、一度に1つのスレッドだけが実際の作業を行っています。

問題を解決する方法は次のとおりです。スレッドが異なる行で並行して動作する必要があるため、この作業をロックで同期してはなりません（ロックは逆を意味するため、一度に1つのスレッドのみが作業を実行できます）。同期する必要があるのは、各スレッドがどの行で動作するかを決定する部分です。

疑似コードの例を次に示します。

public void run(){
  int workRow;
  synchronized(this){
    workRow = findNextUnprosessedRow();
  }
  for(int i=0; i<matrix[workRow].length; i++){
    //do the work
  }
}

上記の理由により、実際の作業は意図的に同期されていないことに注意してください。

スレッドの使用方法は正しいので、問題はありませんが、Javaの並行性APIであるスレッドプールを確認することをお勧めします。コンテキストで使用する方法の例を次に示します。

//Creates a pool of 5 concurrent thread workers
ExecutorService es = Executores.newFixedThreadPool(5);

//List of results for each row computation task
List<Future<Void>> results = new ArrayList<Future<Void>>();
try{
  for(int row=0; row<matrix.length; row++){
    final int workRow = row;

    //The main part. You can submit Callable or Runnable
    // tasks to the ExecutorService, and it will run them
    // for you in the number of threads you have allocated.
    // If you put more than 5 tasks, they will just patiently
    // wait for a task to finish and release a thread, then run.
    Future<Void> task = es.submit(new Callable<Void>(){
      @Override
      public Void call(){
        for(int col=0; col<matrix[workRow].length; col++){
          //do something for each column of workRow
        }
        return null;
      }
    });
    //Store the work task in the list.
    results.add(task);
  }
}finally{
  //Make sure thread-pool is shutdown and all worker
  //threads are released. 
  es.shutdown();
}

for(Future<Void> task : results){
  try{
    //This will wait for threads to finish. 
    // i.e. same as Thread.join()
    task.get();
  }catch(ExecutionException e){
    //One of the tasks threw an exception!
    throw new RuntimeException(e);
  }
}

作業の分散はメインスレッド（外側のforループ）で行われるため、このアプローチは非常にクリーンであり、同期する必要はありません。

スレッドプールを操作すると、いくつかのボーナスも得られます。

  • 各スレッドでの計算中の例外を適切に処理します。アプローチのようにベアスレッドで作業する場合、例外を「失う」のは簡単です。

  • スレッドはプールされます。つまり、それらは自動的に再利用されるため、新しいスレッドを生成するコストについて心配する必要はありません。これは、マトリックスの行ごとにスレッドを生成する必要があるため、特に便利です。これはかなり大きい可能性があると思います。

  • 送信されたタスクExecutorServiceは、有用なオブジェクトにラップされFuture<Result>ます。これは、各計算タスクが実際に何らかの結果を返す場合に最も役立ちます。あなたの場合、マトリックス内のすべての値を合計する必要がある場合、各計算タスクは行の合計を返すことができます。次に、それらを合計する必要があります。

少し長くなりましたが、それがいくつかのことをクリアすることを願っています。

于 2012-05-05T06:43:57.877 に答える
4

問題は、リージョン全体を。と同期することですsynchronized(this)。これは、一度に1つのスレッドのみが計算を実行するループに入ることができることを意味します。もちろん、複数のスレッドが異なる部分を計算できるが、一度に複数のスレッドが計算されることはないことを意味する場合があります。これは、「並列」ソリューションが1つのスレッドよりも高速ではないことも意味します。

並列で計算を行いたい場合は、Java6のParallelMatrixMultiplicationとJavaのForkJoinMatrixMultiplicationを参照してください。トピックをカバーする必要があります。

于 2012-05-05T06:09:53.047 に答える
2

スレッドのスケジューリングは、特定のVMの実装によって異なります。一部の実装では、スレッドは、何らかの方法でブロックされるか、優先度の高いスレッドによってプリエンプトされるまで実行を継続します。あなたの場合、すべてのスレッドが同じ優先順位を持っているので、synchronizedブロックに入る最初のスレッドがブロックされることはなく、プリエンプトされません。一部のスケジューラーは優先エージングを実装しているため、枯渇したスレッドの優先度は最終的に高くなりますが、それが効果を発揮するのに十分な時間実行されていない可能性があります。

ブロックThread.yield()の終了直後に呼び出しを追加します。synchronizedこれは、実行する新しいスレッドを選択するようにスケジューラーに指示します（同じスレッドかもしれませんが、異なるスレッドかもしれません）。

于 2012-05-05T06:12:54.417 に答える
1

mruがコメントですでに述べたように、問題は、すべての行の計算が「同期された（this）」ブロック内で実行されることです。このため、すべてのスレッドは1つの行が処理されるのを待ってから次の行を開始します。計算はほとんどシングルスレッドで行われるため、同じスレッドが常にロックを取得するのはおそらく最適化の結果です。同期されたブロック内で処理する行のみを決定することを検討してください。

int rowToProcess;
synchronized (this) {
    if (i < number of columns in final matrix){
        rowToProcess = i;
        i++;
        }
    else
        return;
    }
于 2012-05-05T06:16:06.943 に答える
1

実行関数には、ロックを所有している間に行ですべての作業を行うロックを取得する最初のスレッドがあります。次の行では、別のスレッドがロックを取得する可能性がありますが、ロックが完了するまで他のすべてのスレッドがブロックされます。

私がすることは、行数と同じブール値の配列を持ち、これらを使用して個々の行を処理するタスクを要求することです。次の疑似コードのようなものになります。

//before creating the threads, pre-fill BoolList with trues
function run()
{
  while (true)
  {
    lock(BoolList)
    {
      //find first true value and set it to false
      //if no true found, return
    }
    //do the actual math of multiplying the row we claimed above
  }
}

また、新しいスレッドを作成するオーバーヘッドは十分であるため、このプログラムのマルチスレッド化は大規模な行列の場合にのみ価値があることに注意してください。

于 2012-05-05T06:04:17.933 に答える