Member 8464407
Большое спасибо за ответы. Я думаю, мне нужно добавить немного дополнительной информации.
I am perhaps naive, but I really did hope for nearly a 16x speedup on my ancient server (Dell R900) with 16 processor cores. It's a Linux machine and my Windows program is running under Wine. The "top" command usually says that my program is getting 1580% to 1590% of the CPU out of a total of 1600%. There are certainly other processes running but they are taking very few cpu cycles. My program does no I/O, my threads do not interact (no queues, no locking, no waiting, etc.), and there is ample memory. (When I run on Windows, there is more "Windows junk" running in the background, but I can still usually get 350% percent or so of the machine for my program out of 400% possible with four processor cores.)
Я действительно не верю, что моя программа имеет проблему многопоточного проектирования (но, конечно, это вполне возможно). Поэтому я решил попробовать создать полную фиктивную программу, которая иллюстрирует проблему и которая достаточно мала для публикации. Вот он.
// timing_test.cpp : dummy program to test the timing of multiple CPU bound threads.
//
#include "stdafx.h"
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <boost/timer/timer.hpp>
#include <boost/thread.hpp>
std::vector<int> numbers; // vector to contain 10,000,000 numbers to be sorted as dummy work.
void timing_test_2(void); // function prototype for thread worker
class Comp_modulus // functor for comparing intergers mod k
{
public:
int k; // k value to calculate modulus
bool operator()(const std::vector<int>::iterator &x, const std::vector<int>::iterator &y)
{
return ( ( (*x) % k ) < ( (*y) % k ) ); // compare the integers by their modulus rather than by their
// .... values to sort in strange ways. It is iterators that
// .... are being sorted, not the integers themselves.
}
};
int main(void)
{
int N = 16; // number of threads to create
numbers.resize(10000000); // storage for 10,000,000 numbers
int i = 0;
for (std::vector<int>::iterator it = numbers.begin(); it != numbers.end(); it++)
(*it) = i++; // fill in the numbers 0 to 9,999,999 which will be sorted in a variety of strange ways.
std::cout << "beginning timing test, number of threads = " << std::setw(2) << (int)N << std::endl;
boost::timer::auto_cpu_timer auto_t; // Quick and dirty overall timer. It prints automatically
// .... when it is destructed at the end of the program.
boost::thread_group tg; // Define a thread group in preparation ....
// .... for creating the threads
for (int i = 0; i < N; i++)
{
tg.create_thread( boost::bind( timing_test_2) ); // Create the N threads
}
tg.join_all(); // Wait until all the threads are done.
std::cout << "completed timing test" << std::endl;
return 0;
}
void timing_test_2(void) // this is the thread that creates the artificial load to simulate work.
{
std::vector<std::vector<int>::iterator> numbers_p; // storage for iterators (pointers) which point to the array of integers
numbers_p.resize( numbers.size() ); // allocate the correct amount of storage, same number of iterators
// ... as integers to which they point.
std::vector<int>::iterator it = numbers.begin(); // point to the beginning of the integer array.
for (std::vector<std::vector<int>::iterator>::iterator it_it = numbers_p.begin(); it_it != numbers_p.end(); it_it++)
(*it_it) = it++; // populate the iterator vector with iterators pointing the the integers
Comp_modulus comp_modulus; // instantiate the functor which does strange compares
// create the dummy work
comp_modulus.k = 2; std::sort(numbers_p.begin(), numbers_p.end(), comp_modulus );
comp_modulus.k = 3; std::sort(numbers_p.begin(), numbers_p.end(), comp_modulus );
comp_modulus.k = 5; std::sort(numbers_p.begin(), numbers_p.end(), comp_modulus );
comp_modulus.k = 7; std::sort(numbers_p.begin(), numbers_p.end(), comp_modulus );
comp_modulus.k = 11; std::sort(numbers_p.begin(), numbers_p.end(), comp_modulus );
comp_modulus.k = 13; std::sort(numbers_p.begin(), numbers_p.end(), comp_modulus );
comp_modulus.k = 17; std::sort(numbers_p.begin(), numbers_p.end(), comp_modulus );
comp_modulus.k = 19; std::sort(numbers_p.begin(), numbers_p.end(), comp_modulus );
comp_modulus.k = 23; std::sort(numbers_p.begin(), numbers_p.end(), comp_modulus );
comp_modulus.k = 29; std::sort(numbers_p.begin(), numbers_p.end(), comp_modulus );
}
Как видите, это C++. Я компилирую на Windows с Visual Studio 2010. Поэтому я использую boost для некоторых функций синхронизации и многопоточности. Если у вас не установлен boost и если у вас есть достаточно новый компилятор C++, было бы просто выполнить синхронизацию и многопоточность с помощью стандартных библиотечных функций C++.
То, что делает моя тестовая программа, выглядит довольно странно, но на самом деле она довольно хорошо отражает то, что делает моя настоящая программа. Тестовая программа сначала создает массив (std::vector), содержащий 10 000 000 целых чисел в диапазоне от 0 до 9 999 999. Затем он создает искусственную рабочую нагрузку для целей синхронизации путем сортировки целых чисел по различным простым модулям. Например, сортировка по модулю 2 сортирует все четные числа перед всеми нечетными числами. Использование простых чисел для модулей гарантирует, что числа будут скремблированы довольно тщательно, и что std::sort имеет много работы, чтобы сделать.
Сортируемые числа хранятся только один раз и концептуально сортируются одновременно каждым потоком. Тем не менее, нет никакой блокировки между потоками, и числа на самом деле не перемещаются сортировкой вообще. Скорее, это волшебство достигается тем, что каждый поток создает свой собственный частный набор указателей на целые числа (итераторы в терминах стандартной библиотеки C++). Тогда сортируются указатели, а не целые числа.
В программе тестирования синхронизации целые числа 32-битные, а указатели 64-битные, поэтому каждый поток может также иметь свою собственную копию целых чисел и сортировать их напрямую, вместо того чтобы иметь указатели и сортировать программу. В моей реальной программе целые числа становятся 32-байтовыми перестановками, и потокам гораздо эффективнее работать с 64-битными указателями (8 байт), чем с 32-байтовыми перестановками. Кроме того, сортировка элементов длиной 8 байт выполняется намного быстрее, чем сортировка элементов длиной 32 байта.
Приложение-это вычислительная теория групп, и задача состоит в том, чтобы попытаться перечислить оптимальное решение для каждого из возможных положений Куба Рубика. Поиск оптимального решения для позиции является гораздо более вычислительно интенсивным, чем просто поиск решения для позиции. Существует около 4,3 х 10^19 позиций кубика Рубика, так что это чрезвычайно нетривиальная проблема. Это окончательное решение, несомненно, потребует многих сотен, если не тысяч или сотен тысяч машин, работающих над проблемой по частям.
Here are the results of running the dummy timing program on my ancient server. The test program is so simple minded that I had to run it 16 different times, changing the number of threads each time. You can see how the wall clock and cpu times do not scale up as you might hope. For example, with one thread the wall clock time and the cpu time are both about 24 seconds. So one would hope would be that with two threads the wall clock time would be about 24 seconds and that the cpu time would be about 48 seconds. But the real figures are about 26.5 seconds and about 53 seconds, respectively. The problem only gets worse with more threads. The same thing happens on my Windows machine. And the same thing happens if you get rid of the threads and just run multiple instances of a one thread program.
Джерри Брайан
beginning timing test, number of threads = 1
completed timing test
24.109956s wall, 23.990000s user + 0.080000s system = 24.070000s CPU (99.8%)
beginning timing test, number of threads = 2
completed timing test
26.558628s wall, 52.820000s user + 0.210000s system = 53.030000s CPU (199.7%)
beginning timing test, number of threads = 3
completed timing test
27.632885s wall, 82.410000s user + 0.310000s system = 82.720000s CPU (299.4%)
beginning timing test, number of threads = 4
completed timing test
33.766357s wall, 120.150000s user + 0.390000s system = 120.540000s CPU (357.0%)
beginning timing test, number of threads = 5
completed timing test
34.820234s wall, 152.480000s user + 0.510000s system = 152.990000s CPU (439.4%)
beginning timing test, number of threads = 6
completed timing test
33.279489s wall, 183.450000s user + 0.680000s system = 184.130000s CPU (553.3%)
beginning timing test, number of threads = 7
completed timing test
35.896250s wall, 235.820000s user + 0.890000s system = 236.710000s CPU (659.4%)
beginning timing test, number of threads = 8
completed timing test
36.156149s wall, 275.370000s user + 1.170000s system = 276.540000s CPU (764.8%)
beginning timing test, number of threads = 9
completed timing test
38.529383s wall, 319.610000s user + 1.540000s system = 321.150000s CPU (833.5%)
beginning timing test, number of threads = 10
completed timing test
40.542099s wall, 367.840000s user + 1.970000s system = 369.810000s CPU (912.2%)
beginning timing test, number of threads = 11
completed timing test
45.129656s wall, 421.800000s user + 2.340000s system = 424.140000s CPU (939.8%)
beginning timing test, number of threads = 12
completed timing test
44.265782s wall, 485.820000s user + 2.650000s system = 488.470000s CPU (1103.5%)
beginning timing test, number of threads = 13
completed timing test
45.339959s wall, 545.310