Умножение больших чисел с помощью многопоточности

Question

Мне нужно умножить большие числа, используя многопоточность. Два числа, которые нужно умножить, могут иметь до 10000 цифр. Я написал код умножения, используя один поток. Но я не уверен, как умножать, когда я присваиваю несколько потоков разным цифрам.

Например, если два числа: 254678 и 378929, и есть 3 потока, я назначаю каждую из двух цифрна одну нить (2,5-нить 1), (4,6-> нить 2), (7,8-> нить 3) и каждая из цифр должна умножать цифры 2-го числа-> 378929.

Когда потоки будут работать параллельно, я не знаю, как управлять переменной переноса, когда несколько потоков обновят переменную одновременно.

input: array содержит оба числа
index:i1 содержит последнюю цифру 1-го числа
индекс: i2 содержит последнюю цифру 2-го числа

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

Когда потоки будут работать параллельно, я не знаю, как управлять переменной переноса, когда несколько потоков обновят переменную одновременно.

Не разрешать несколькопотоки для обновления чего-либо одновременно.

В частности (при условии, что каждая цифра является цифрой в «базе 1 << 32»), каждый поток может иметь вид: </p>

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[] одновременно (или несколько мьютексов, чтобы гарантировать, что только один поток может изменять фрагмент output[] одновременно);и это настолько сильно ухудшит производительность, что будет быстрее использовать один поток.

Примечание 3: Альтернативная альтернатива - использовать атомарные методы или использовать встроенную сборку (например, "lock add [output+rdi],eax;"), чтобымьютекс не нужен. Это все еще очень плохо, потому что процессоры будут бороться за эксклюзивный доступ к одной и той же строке кэша (и вы потеряете производительность, если процессоры будут тратить большую часть своего времени, пытаясь получить эксклюзивный доступ к строке кэша).