Почему время выполнения параллельной задачи лучше для нечетного числа потоков? - PullRequest
Новая
       28

Почему время выполнения параллельной задачи лучше для нечетного числа потоков?

0 голосов
/ 26 марта 2020

Я параллельно реализовал алгоритм, который находит и печатает все круговые простые числа в интервале [2, X]. Я измерил время выполнения задачи, варьируя количество потоков от 1 до 16. Может кто-нибудь объяснить, почему у меня ухудшается время выполнения, когда число потоков четное? (Примечание: на самом деле я получаю худшее время для нечетного числа потоков, если основной поток также учитывается)

Процессор компьютера, на котором я запускал программу, - "Intel® Core ™ i7-8550U", с 4 ядрами и гиперпоточностью.

Это функция, которую выполняют потоки (я выполнил балансировку нагрузки): 

void *printIfCircularPrime(void *threadId)
{
    int tid = (int)threadId;
    printf("Hi, I am thread %d\n", threadId);

    for (long i = 2 + tid; i <= X; i += NR_THREADS)
    {
        if (isCircularPrime(i))
        {
            printf("%ld\n", i);
        }
    }

    pthread_exit(NULL);
}

Это мои измерения времени выполнения:

enter image description here

Полный код: 

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

#define NR_THREADS 16
#define X 120000000

int isPrime(long n)
{
    if (n <= 1)
    {
        return 0;
    }
    if (n == 2)
    {
        return 1;
    }   
    if (n % 2 == 0)
    {
        return 0;
    }
    for (int d = 3; d <= floor(sqrt(n)); d += 2)
    {
        if (n % d == 0)
        {
            return 0;
        }
    }
    return 1;
}

int countDigits(long n)
{
    int digits = 0;
    while (n)
    {
        n /= 10;
        digits++;
    }
    return digits;
}

long cyclicallyPermute(long n, int numberOfDigits)
{
    int lastDigit = n % 10;
    return pow(10, numberOfDigits - 1) * lastDigit + n / 10;
}

int isCircularPrime(long n)
{
    int numberOfDigits = countDigits(n);
    for (int i = 0; i < numberOfDigits; i++)
    {
        if (!isPrime(n))
        {
            return 0;
        }
        n = cyclicallyPermute(n, numberOfDigits);
    }
    return 1;
}

void *printIfCircularPrime(void *threadId)
{
    int tid = (int)threadId;
    printf("Hi, I am thread %d\n", threadId);

    for (long i = 2 + tid; i <= X; i += NR_THREADS)
    {
        if (isCircularPrime(i))
        {
            printf("%ld\n", i);
        }
    }

    pthread_exit(NULL);
}

int main(int argc, char *argv[])
{
    printf("Number of threads: %d\n", NR_THREADS);
    pthread_t threads[NR_THREADS];

    struct timespec start, stop;
    clock_gettime(CLOCK_REALTIME, &start);

    for (int i = 0; i < NR_THREADS; i++)
    {
        pthread_create(&threads[i], NULL, printIfCircularPrime, (void *)i);
    }

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

    clock_gettime(CLOCK_REALTIME, &stop);

    printf("\nExecution time: %ld seconds\n", stop.tv_sec - start.tv_sec);

    pthread_exit(NULL);
}
...