C ++ 0x потоки не дают ускорения
Я написал программу для поиска максимума в массивах, используя потоки c ++ 0x (для целей обучения). Для реализации я использовал стандарт нить а также будущее классы. Однако параллельная функция постоянно показывает одинаковое или худшее время выполнения, чем непараллельная.
Код ниже. Я пытался хранить данные в одномерном массиве, многомерном массиве и получил несколько массивов. Однако ни один вариант не дал хороших результатов. Я пытался скомпилировать и запустить мой код из Eclipse и командной строки, но безуспешно. Я также попробовал подобный тест без использования массива. Распараллеливание дало там только 20% скорости. С моей точки зрения, я запускаю очень простую параллельную программу, без блокировок и почти без совместного использования ресурсов (каждый поток работает со своим собственным массивом). Что такое узкое место?
На моей машине установлен процессор Intel Core i7 с тактовой частотой 2,2 ГГц и 8 ГБ оперативной памяти, работающий под управлением Ubuntu 12.04.
const int n = 100000000;
int a[n], b[n], c[n], d[n];
int find_max_usual() {
int res = 0;
for (int i = 0; i < n; ++i) {
res = max(res, a[i]);
res = max(res, b[i]);
res = max(res, c[i]);
res = max(res, d[i]);
}
return res;
}
int find_max(int *a) {
int res = 0;
for (int i = 0; i < n; ++i)
res = max(res, a[i]);
return res;
}
int find_max_parallel() {
future<int> res_a = async(launch::async, find_max, a);
future<int> res_b = async(launch::async, find_max, b);
future<int> res_c = async(launch::async, find_max, c);
future<int> res_d = async(launch::async, find_max, d);
int res = max(max(res_a.get(), res_b.get()), max(res_c.get(), res_d.get()));
return res;
}
double get_time() {
timeval tim;
gettimeofday(&tim, NULL);
double t = tim.tv_sec + (tim.tv_usec / 1000000.0);
return t;
}
int main() {
for (int i = 0; i < n; ++i) {
a[i] = rand();
b[i] = rand();
c[i] = rand();
d[i] = rand();
}
double start = get_time();
int x = find_max_usual();
cerr << x << " " << get_time() - start << endl;
start = get_time();
x = find_max_parallel();
cerr << x << " " << get_time() - start << endl;
return 0;
}
Время показало, что почти все время в find_max_parralel потребляется
int res = max(max(res_a.get(), res_b.get()), max(res_c.get(), res_d.get()));
Компиляция командной строки
g++ -O3 -std=c++0x -pthread x.cpp
Обновить. Проблема решена. Я получил желаемые результаты с тем же тестом. 4 потока увеличивают скорость примерно на 3,3, 3 потока увеличивают скорость примерно на 2,5, 2 потока ведут себя почти идеально с ускорением 1,9. Я только что перезагрузил систему с некоторыми новыми обновлениями. Я не видел существенной разницы в загрузке процессора и запуске программ.
Спасибо всем за помощь.
Решение
Вы должны явно установить std::launch::async,
future<int> res_c = async(std::launch::async, find_max, c);
Если вы опустите флаг std::launch::async | std::launch::deferred isimpnd, который оставляет за собой право выбирать, запускать ли задачу асинхронно или с задержкой.
Текущие версии GCC используют std::launch::deferredMSVC имеет планировщик времени выполнения, который во время выполнения определяет, как должна выполняться задача.
Также обратите внимание, что если вы хотите попробовать:
std::async(find_max, c);
это также заблокирует, потому что деструктор std::future ждет завершения задачи
Другие решения
Я только что выполнил тот же тест с gcc-4.7.1, а многопоточная версия примерно в 4 раза быстрее (на 4-ядерном сервере).
Таким образом, проблема, очевидно, не в реализации std :: future, а в выборе параметров потоков, не оптимальных для вашей среды. Как было отмечено выше, вы тестируете не процессор, а память, поэтому узким местом является доступ к памяти.
Возможно, вы захотите запустить какой-нибудь интенсивный процессорный процесс (например, вычисление числа PI с высокой точностью), чтобы правильно протестировать многопоточность.
Не экспериментируя с разным количеством потоков и разными размерами массивов, трудно сказать, где именно находится узкое место, но в игре, вероятно, есть несколько вещей:
— У вас, вероятно, есть 2-канальный контроллер памяти (это либо 2, либо 3), так что если вы перейдете выше 2 потоков, это приведет к дополнительному конфликту вокруг доступа к памяти. Таким образом, ваш тезис об отсутствии блокировки и совместного использования ресурсов не верен: на аппаратном уровне существует конфликт вокруг одновременного доступа к памяти.
— Непараллельная версия будет эффективно оптимизирована путем предварительной загрузки данных в кэш. С другой стороны, есть вероятность, что в параллельной версии вы столкнетесь с интенсивным переключением контекста и, как следствие, перегрузкой кеша процессора.
Для обоих факторов вы, вероятно, увидите ускорение, если уменьшите число потоков до 2.