14

我正在用 Java 编写一个多线程应用程序，以提高顺序版本的性能。它是 0/1 背包问题的动态规划解决方案的并行版本。我有一个 Intel Core 2 Duo，在不同的分区上有 Ubuntu 和 Windows 7 Professional。我在 Ubuntu 中运行。

我的问题是并行版本实际上比顺序版本需要更长的时间。我在想这可能是因为线程都被映射到同一个内核线程，或者它们被分配到同一个内核。有没有办法可以确保每个 Java 线程都映射到一个单独的核心？

我已阅读有关此问题的其他帖子，但似乎没有任何帮助。

这是 KnapsackThread 类（它扩展了 Thread）的 main() 和所有 run() 的结尾。请注意，我使用 slice 和 extra 来计算 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;
        }
    }
}

更新：

我写了另一个版本的使用蛮力的背包。这个版本几乎没有同步，因为我只需要在单个线程执行结束时更新一个 bestSoFar 变量。因此，每个线程几乎应该完全并行执行，除了最后那个小的关键部分。

我运行这个而不是连续的蛮力，但仍然需要更长的时间。除了我的线程正在按顺序运行之外，我没有看到任何其他解释，因为它们被映射到同一个核心或同一个本机线程。

有没有人有任何见识？

4

3 回答 3

22

我怀疑这将是由于对所有线程使用相同的核心。调度取决于操作系统，但如果您调出操作系统的性能管理器，您应该能够看到发生了什么——它通常会显示每个内核的繁忙程度。

需要更长时间的可能原因：

  • 大量同步（必要或不必要）
  • 任务花费的时间如此之短，以至于线程创建占用了很大一部分时间
  • 上下文切换，如果您要创建太多线程 - 对于 CPU 密集型任务，创建与内核一样多的线程。
于 2009-12-13T10:19:55.323 回答
6

我有一段时间遇到同样的问题。我有一个 CPU 密集型程序，我将其划分为 2 个线程（双核 CPU），但有一天美好的一天，在处理更多数据时，它只是停止使用两个内核。我刚刚提高了堆内存大小（-Xmx1536m在我的情况下），它又可以正常工作了。

于 2012-02-14T12:12:50.633 回答
1

我建议您查看每个工作线程在终止之前需要多长时间。也许其中一个线程的任务要困难得多。如果是这种情况，那么同步等引起的开销很容易耗尽你从线程中获得的东西。

于 2009-12-13T14:49:29.520 回答