Эта многопоточная программа работает лучше, чем не многопоточная?

Question

Мой коллега попросил меня написать домашнее задание для него. Хотя это было не слишком этично, но я признал себя виновным. Вот как выглядит проблема: Напишите программу на C, в которой вычисляется последовательность 1 ² + 2 ² + ... + n ² . Предположим, что n кратно p и p - количество потоков. Вот что я написал:

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

#define SQR(X) ((X) * (X))

int n, p = 10, total_sum = 0;

pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER;
/* Function prototype */
void *do_calc(void *arg);

int main(int argc, char** argv)
{
    int i;
    pthread_t *thread_array;
    printf("Type number n: ");
    fscanf(stdin, "%d", &n);

    if (n % p != 0 ) {
        fprintf(stderr, "Number must be multiple of 10 (number of threads)\n");
        exit(-1);
    }


    thread_array = (pthread_t *) malloc(p * sizeof(pthread_t));
    for (i = 0; i < p; i++)
        pthread_create(&thread_array[i], NULL, do_calc, (void *) i);
    for (i = 0; i < p; i++)
        pthread_join(thread_array[i], NULL);

    printf("Total sum: %d\n", total_sum);
    pthread_exit(NULL);
}

void *do_calc(void *arg)
{
    int i, local_sum = 0;
    int thr = (int) arg;
    pthread_mutex_lock(&mtx);
    for (i = thr * (n / p); i < ((thr + 1) * (n / p)); i++)
    local_sum += SQR(i + 1);
    total_sum += local_sum;
    pthread_mutex_unlock(&mtx);
    pthread_exit(NULL);
}

Помимо логической / синтаксической точки зрения, мне было интересно:

1. как будет работать соответствующая не многопоточная программа
2. как я могу проверить / увидеть их производительность
3. что бы программа без использования потоков

Заранее спасибо, и я с нетерпением жду ваших мыслей

Answer 1

Вы приобретаете Mutex перед расчетами. Вы должны сделать это непосредственно перед суммированием локальных значений.

pthread_mutex_lock(&mtx);
total_sum += local_sum;
pthread_mutex_unlock(&mtx);

Answer 2

Это будет зависеть от того, сколько у вас процессоров. С одним ядром ЦП программа, связанная с вычислениями, никогда не будет работать быстрее с несколькими потоками.

Более того, поскольку вы выполняете всю работу с удерживаемой блокировкой, вы в конечном итоге получите только один поток, работающий в любое время, так что в любом случае он фактически является однопоточным.

Answer 3

Не беспокойтесь о многопоточности и т. Д. Фактически, вообще не делайте никаких дополнений в цикле. Просто используйте эту формулу:

∑ (r = 1; n) r ^ 2 = 1/6 * n (n + 1) (2 n + 1) [1]

[1] http://thesaurus.maths.org/mmkb/entry.html?action=entryById&id=1539

Answer 4

Поскольку ваш код сериализуется мьютексом в реальных вычислениях, он будет работать медленнее, чем не поточная версия. Конечно, вы могли бы легко проверить это сами.

Answer 5

Немного не по теме, но, возможно, избегайте мьютекса, заставляя каждый поток записывать свой результат в элемент массива (поэтому присвойте "results = calloc (sizeof (int), p)") (кстати, "p" - ужасное имя для переменной, содержащей число потоков) и результатов [thr] = local_sum), и объединяющий поток (ну, main ()) выполняет суммирование результатов. Таким образом, каждый поток отвечает только за вычисление его итога: только main (), который управляет потоками, объединяет их данные. Разделение интересов.

Для дополнительного кредита (: p) используйте аргумент, переданный do_calc (), в качестве способа передачи идентификатора потока и местоположения, в которое нужно записать результат, вместо того, чтобы полагаться на глобальный массив.

Answer 6

Гораздо большее внимание уделяется планированию. Самый простой способ реализации потоков на стороне ядра состоит в том, чтобы каждый поток получал равное время независимо. Процессы - это просто потоки с собственным пространством памяти. Если все потоки получают одинаковое время, добавление потока приводит вас к 1 / n времени к 2 / (n + 1) времени, что, очевидно, лучше, если> 0 других потоков не вы.

Фактические реализации могут и действительно сильно различаться.

Answer 7

1) Однопоточный, вероятно, будет работать немного лучше, чем этот, потому что все вычисления выполняются в пределах блокировки, а накладные расходы на блокировку увеличивают общее время. Лучше блокировать только при добавлении локальных сумм к общей сумме или сохранении локальных сумм в массиве и вычислении общей суммы в главном потоке.

2) Используйте временные операторы в своем коде, чтобы измерить прошедшее время в течение алгоритма. В многопоточном случае измерять только истекшее время в главном потоке.

3) Получено из вашего кода:

int i, total_sum = 0;
for (i = 0; i < n; i++)
  total_sum += SQR(i + 1);

Answer 8

для сравнения производительности просто запомните системное время при запуске программы, наберите его с n = 1000 и посмотрите системное время в конце. сравнить с непотоковым результатом программы. как сказал bdonlan, без резьбы будет работать быстрее

Answer 9

Я бы попытался посмотреть, сколько занимают эти вычисления. В случае, если это очень малая доля времени, я бы, вероятно, пошел на одну модель процесса, так как порождение потока для каждого вычисления само по себе требует некоторых затрат.