Вопрос про многопоточность

По заданию нужно написать программу, вычисляющую число Пи с точностью до 100_000_000 знаков после запятой по формуле:

формула

Конечно, точность здесь понятие условное - нас интересует только то, что цикл, который будет вычислять число Пи, должен отработать 100_000_000 итераций. Выполнение этого цикла нужно разбить на потоки. Каждый поток должен выполнять свой блок, содержащий примерно 300_000 итераций. Как только поток выполнит свой блок, он должен переключиться на любой другой свободный блок. Ниже представлена программа, решающая эту задачу, а также замеряющая время для 1, 2, 4, 6, 8, 12 и 16 потоков.

#pragma comment(lib, "winmm.lib")

#include<iostream>
#include<windows.h>

#define N 100000000
#define BLOCK 300000

using std::cout;
using std::endl;
using std::cin;

double pi = 0;
int offset_for_next_block_of_threads = 0;

typedef struct Position
{
    int position;
}
*PositionPointer;

DWORD WINAPI ThreadFunction(LPVOID lpParameter)
{
    PositionPointer position = (PositionPointer)lpParameter;
    int start_position = position->position;
    int finish_position = start_position + BLOCK;

    while (start_position < N)
    {
        double pi_part = 0;
        for (int i = start_position; i < N && i < finish_position; ++i)
        {
            double xi = (double)((i + 0.5) / N); // промежуточное значение
            pi_part += (double)(4 / (1 + xi * xi)); // наращиваем промежуток для Пи
        }
        pi += pi_part; // критический момент
        start_position = offset_for_next_block_of_threads;
        offset_for_next_block_of_threads += BLOCK; // ещё критический момент
        finish_position = start_position + BLOCK;
    }

    return 0;
}

void test(int number_of_threads)
{
    HANDLE* threads = new HANDLE[number_of_threads];
    PositionPointer positions = new Position[number_of_threads];
    DWORD start_time, end_time, time;

    offset_for_next_block_of_threads = BLOCK * (number_of_threads);
    for (int i = 0; i < number_of_threads; ++i)
    {
        positions[i].position = i * BLOCK;
    }

    for (int i = 0; i < number_of_threads; ++i)
    {
        threads[i] = CreateThread(NULL, 0, ThreadFunction, &positions[i], CREATE_SUSPENDED, NULL);
    }

    start_time = timeGetTime();
    for (int i = 0; i < number_of_threads; ++i)
    {
        ResumeThread(threads[i]);
    }

    WaitForMultipleObjects(number_of_threads, threads, TRUE, INFINITE);
    end_time = timeGetTime();
    time = end_time - start_time;

    for (int i = 0; i < number_of_threads; ++i)
    {
        CloseHandle(threads[i]);
    }

    pi = (double)(pi / N);
    printf("%.12lf\n", pi);
    cout << "threads: " << number_of_threads << ", time: " << time << endl << endl;
}

int main()
{
    int* numbers = new int[7] {1, 2, 4, 6, 8, 12, 16};
    for (int i = 0; i < 7; ++i)
    {
        test(numbers[i]);
        pi = 0;
    }
    return 0;
}

Функция ThreadFunction, собственно, и является функцией, которая выполняется потоками. Можно заметить, что у каждого потока будут свои переменные, отвечающие за стартовую и конечную позицию блока, а также за промежуточное значение числа Пи. Вычислив pi_part, поток затем добавит его к числу Пи - критическое место, но я специально этот момент не синхронизирую (ещё одним критическим местом является offset_for_next_block_of_threads).

Итак, перехожу к вопросу. Результат запуска этой программы на своём компьютере я привожу ниже.

3.141592653590
threads: 1, time: 284

3.141592653590
threads: 2, time: 143

3.141592653590
threads: 4, time: 88

3.141592653590
threads: 6, time: 61

3.141592653590
threads: 8, time: 52

3.141592653590
threads: 12, time: 43

3.141592653590
threads: 16, time: 45

Можно заметить, что при запуске 4-х потоков программа не ускоряется в 4 раза, а при запуске 6-ти - совершенно не ускоряется в 6 раз. Мой процессор имеет 6 физических ядер, каждое из которых поддерживает 2 потока. Насколько я знаю, если потоки выполняются на разных ядрах (а им нет причин не выполняться на разных ядрах), то они совершенно точно выполняются одновременно. А обозначенные выше критические места занимают совсем мало от общего объёма работы и не могут так сильно влиять на производительность. И опять же, переменные xi и pi_part, с которыми ведётся работа во внутреннем цикле, у каждого потока свои, соответственно, они с ними должны работать абсолютно независимо.

Почему я не получаю ожидаемого ускорения, если программе ничего не мешает выполнять действия поистине одновременно и независимо друг от друга? Я пытался найти разные ответы на этот довольно стандартный вопрос "почему не ускоряется в N раз при запуске N потоков?", но все они сводились к критическим секциям (критическое место в нашем случае совсем малозначительно), переключениям контекста (какие уж тут переключения, когда потоки по идее должны выполняться одновременно) и становлению потоков в очередь (мы ведь имеем 6 ядер, соответственно, число потоков до 6-ти включительно не должно стоять в очереди).


Ответы (0 шт):