multithreading - Perl - 同步数据访问

Question

我开始学习并行编程，我想比较一下单线程程序和多线程程序。

我需要做一个非常简单的算法，在一分钟内计算出最大数量的可能素数，并显示最后计算出的素数及其在素数中的位置。

例如，素数 23，将显示为数字 23 及其位置 9，因为它是第 9 个素数。

在不使用线程的情况下，找到的素数为 233,596，最后一个素数为 3,246,107。但是对于线程，找到了 229,972 个素数，最后一个素数是 3,192,463。

我认为这是错误的，因为多线程理应获得比单线程更好的结果。我认为这是一个非常基本的错误，但我无法解决它，因为我仍然不太了解 Perl 的并行性。

这是代码。它在单线程中计算质数一分钟，然后使用共享变量在四个线程中进行相同的计算。

use threads;
use threads::shared;

my $seconds = 60;

 # WITHOUT THREAD #
print "\n\n Calc without Threads:\n";
my $endTime = time() + $seconds;
calcWithoutThread();


print "\n\n ----------------===========================---------------- \n";

 # WITH THREAD #
print "\n\n Calc with Threads:\n";
my $prime :shared = 5;          # Starts from the 5th prime
my $totalPrime :shared = 2; # Starts with prime 2 and prime 3
my $lastPrime :shared = 0;
my $endTime1 = time() + $seconds;
my $thread1 = threads->create(\&calcWithThread);
my $thread2 = threads->create(\&calcWithThread);
my $thread3 = threads->create(\&calcWithThread);
my $thread4 = threads->create(\&calcWithThread);
$thread1->join();
$thread2->join();
$thread3->join();
$thread4->join();
print " Was found $totalPrime prime numbers. Last prime: $lastPrime.";


# SUB's #

sub calcWithoutThread{
    $prime = 5;            # Starts from the 5th prime
    $totalPrime = 2;           # Starts with prime 2 and prime 3
    $lastPrime = 0;
    while (time() < $endTime){
        if(calcPrime($prime)){  
            $totalPrime ++;
            $lastPrime = $prime;
        }
        $prime ++;
    }
    print " Was found $totalPrime prime numbers. Last prime: $lastPrime.";
}

sub calcWithThread{
    while (time() < $endTime1) {
        lock($prime);           
        if(calcPrime($prime)){
            $totalPrime ++;
            $lastPrime = $prime;
        }
        $prime ++;
    }   
}

sub calcPrime{
    for($i=2 ; $i< sqrt ($prime) ; $i++){
        if( $prime % $i == 0){
            return 0;
        }
    }
    return 1;   
}

逻辑是线程同步计算，无论是否为素数，计算时也不会重叠值。

Answer 1

问题是您的线程通过锁定变量 $prime 相互同步。这意味着它们没有机会同时运行，并且还会承受切换线程和同步访问变量的开销

素数不是并行处理的好测试，因为每个素数的计算都取决于之前的结果。但是，您可以通过保留一个单独的 $prime 变量来实现，但对于四个线程从 5、6、7 和 8 开始，并在测试之间添加 4。这样他们就不会重复彼此的工作，而是一起覆盖每个整数

这会立即产生一个问题，因为偶数永远不会是质数，因此四个线程中的两个永远不会产生结果。它仍然是并行性的有效测试，但显然效率很低。您可以通过以 5、7、9 和 11 启动线程并在每次测试之前递增 8 来解决此问题。那么每个线程都会盈利

不要忘记您必须为单线程代码编写相同的算法，否则并行部分会获得不公平的优势

---

更新

也许更好的方法是锁定 $prime 以获取下一个要测试的数字并递增它。这样所有的线程都可以并行计算并且只排队等待下一个任务

然后您必须锁定 $total_prime 以防止两个线程同时递增它，并且还必须在该锁定生效时更新 $last_prime。因为并行线程很可能会乱序生成素数，所以您还必须检查刚刚找到的素数是否大于任何线程发现的最新素数

你的子程序看起来像这样。对于更改标识符，我深表歉意，但 Perl 传统上使用 snake_case，我发现 camelCase 读起来不愉快。对于许多第一语言不是英语并且不能那么容易地识别大写字母的人来说，蛇形大小写也容易得多

sub calc_with_thread {

    while ( time() < $end_time_1 ) {

        my $test = do {
            lock $prime;
            $prime++;
        };

        if ( calc_prime($test) ) {
            lock $total_prime;
            ++$total_prime;
            $last_prime = $test if $test > $last_prime;
        }
    }   
}