Вопрос про многопоточность
По заданию нужно написать программу, вычисляющую число Пи с точностью до 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-ти включительно не должно стоять в очереди).
