c - 使用多线程将大数相乘

Question

我需要使用多线程来乘以大数。要相乘的两个数字最多可以有 10000 位。我使用单线程编写了乘法代码。但当我将多个线程分配给不同的数字时，我不确定如何相乘。

例如，如果两个数字是:254678 和 378929 并且有 3 个线程，我将这两个数字中的每一个分配给一个线程(2,5-线程 1),(4,6->线程 2) ,(7,8-> 线程 3) 并且每个数字应乘以第二个数字-> 378929。

当线程并行运行时，当多个线程同时更新变量时，我不知道如何管理进位变量。

输入:数组包含两个数字
索引:i1 包含第一个数字的最后一位
索引:i2 包含第二个数字的最后一位数字

enter code here
for (int i=i1-1; i>=1; i--){ 
    int carry = 0; 
    int n1 = input[i]; 
    t2 = 0;
    for(int j=i2-1; j>i1-1; j--){                                               
        int n2 = input[j]; 
        int sum = n1*n2 + output[t1+t2] + carry;
        carry = sum/10;
        output[t1+t2] = sum % 10; 
        t2++; 
    }
    if(carry > 0)                                                                   
        output[t1 + t2] += carry; 
    t1++; 
}
int main() { 
    pthread_t threads[MAX_THREAD];
    for (int i = 0; i < MAX_THREAD; i++) 
        pthread_create(&threads[i], NULL, &multiply, (void*)NULL); 

    for (int i = 0; i < MAX_THREAD; i++) 
        pthread_join(threads[i], NULL); 
}

Answer 1

When the threads will run in parallel I don't know how to manage the carry variable when multiple threads will update the variable at the same time.

不允许多个线程同时更新任何内容。

具体来说(假设每个数字都是“base 1<<32”中的数字)，每个线程可以是这样的:

my_accumulator = table_of_per_thread_accumulators[thread_number];
for (int src1_digit_number = startDigit; src1_digit_number >= 0; src1_digit_number -= NUM_THREADS ) {
    for (int src2_digit_number = src2_digits-1; src2_digit_number >= 0; src2_digit_number-- ) {
        int dest_digit_number = src1_digit_number  + src2_digit_number;

        uint32_t n1 = input1[src1_digit_number];
        uint32_t n2 = input2[src2_digit_number];
        uint64_t r = (uint64_t)n1 * n2;
        while(r != 0) {
            uint64_t temp = my_accumulator[dest_digit_number] + (r & 0xFFFFFFFFUL);
            my_accumulator[dest_digit_number++] = temp;
            temp >>= 32;
            r = (r >> 32) + temp;
        }
    }
}

然后，当所有线程完成时(在一些“pthread_join()”调用之后？)，您可以将每个线程单独的 my_accumulator 中的数字相加，以获得实际的值结果。

注释 1:理论上，您可以进行一些“累加器的二进制合并”，这样奇数编号的线程就会等待下一个编号较低的线程完成，并将该线程的累加器添加到自己的累加器中；然后满足“my_thread_number % 4 == 3”的线程等待编号为“my_thread_number - 2”的线程完成并将其累加器添加到自己的累加器中；那么...这可能太复杂、太困惑，不值得费心。

注 2:另一种方法(如果您使用由多个线程修改的单个 output[])是使用互斥锁来确保只有一个线程可以修改 output[] code> 同时(或多个互斥体以确保一次只有一个线程可以修改一段 output[])；这会严重破坏性能，因此使用单线程会更快。

注释 3:另一种选择是以某种方式使用原子，或使用内联汇编(例如“lock add [output+rdi],eax;”)，这样就不需要互斥锁。这仍然非常糟糕，因为 CPU 将争夺对同一缓存行的独占访问(并且您将通过让 CPU 花费大部分时间尝试获得对缓存行的独占访问来破坏性能)。