Комментарии 29
Если взять лучшее время 12.8 секунд для CPU #2 на размере N=1500, то увеличение N в 4 раза увеличит время в 256 раз, до 54,5 минуты.
Т.е. примерно за час на CPU можно посчитать для N=6000.
Самая короткая сказка о потерянном времени.
одно из чисел будет кратно 11
(0..10) ^5 mod 11== 0, 1, 10
0 0 0 1 10 =0
0 1 1 10 10 = 0
значит минимум 1 кратен 11
т.е. первый параметр берешь с шагом 11 0 11 22 33 итд
все остальное так же
переписываешь в виде e^5-a^5-b^5-c^5=d^5
e берешь с шагом в 11
ускорение в 5.5 раза 11/2
здесь кратно 11 число 110.
55^5 + 3183^5 + 28969^5 + 85282^5 = 85359^5
а здесь — 55
e нельзя перебирать с шагом 11.
И заранее не известно, какое можно.
первое ты перебираешь с шагом в 11, а порядок остальных делаешь независимым от него.
Потом — оптимальнее всего перебирать от больших к меньшим (чтобы сузить диапазон самых вариабельных значений).
Перебор одного из слагаемых в полном диапазоне может легко съесть всю экономию.
можно разбить на 2 варианта
for (uint32_t a = from; a < to; ++a) {
if (a%11=0) is11=true else is11=false
for (uint32_t b = 1; b < a; ++b) {
if (b%11=0) is11=true
for (uint32_t c = 1; c < b; ++c) {
if (c%11=0) is11=true
if(is11)
{
for (uint32_t d = 11; d < c; d+=11) {
const uint64_t sum = powers[a] + powers[b] + powers[c] + powers[d];
if (std::binary_search(std::begin(powers), std::end(powers), sum)) {
const auto it = std::lower_bound(std::begin(powers), std::end(powers), sum);
uint32_t e = static_cast<uint32_t>(std::distance(std::begin(powers), it));
std::cout << a << " " << b << " " << c << " " << d << " " << e << "\n";
}
}
else
{
for (uint32_t d = 1; d < c; ++d) {
const uint64_t sum = powers[a] + powers[b] + powers[c] + powers[d];
if (std::binary_search(std::begin(powers), std::end(powers), sum)) {
const auto it = std::lower_bound(std::begin(powers), std::end(powers), sum);
uint32_t e = static_cast<uint32_t>(std::distance(std::begin(powers), it));
std::cout << a << " " << b << " " << c << " " << d << " " << e << "\n";
}
}
}
Во вторых если is11 == false — то перебирать d надо все равно полностью, т.к. нет гарантии что кратным 11 числом является не e, а d.
— то разность пятых степеней может принимать не любые значения по модулям 11, 31, 41 и 61… Так что проверив сумму a^5+b^5+c^5 по модулю 11*31*41*61, четвертый цикл примерно в 80% случаев можно вообще не выполнять…
Ускорим во много раз
(a^5) mod 7 =
таблица соответствия
t f[t]
0 0
1 1
2 4
3 5
4 2
5 3
6 6
зная первые 4 последнее находим как (f[a]+f[b]+f[c]+f[d])mod 7 =f[e]
аналогично для 13
t R[r]
0 0
1 1
2 6
3 9
4 10
5 5
6 2
7 11
8 8
9 3
10 4
11 7
12 12
зная первые 4 последнее находим как (R[a]+R[b]+R[c]+R[d])mod 13 =R[e]
аналогично для 17
if (std::binary_search(std::begin(powers), std::end(powers), sum)) {
const auto it = std::lower_bound(std::begin(powers), std::end(powers), sum);
вы тут при попадании внутрь if второй раз бинарный поиск делаете (aka lower_bound), зачем?
нужно сделать 1 раз lower_bound и сравнить значение по итератору с искомым.
А то 64 бита заканчиваются очень быстро.
Получить по сравнению с одним ядром CPU 10-кратное ускорение на видеокарте с 1500 ядрами как-то слишком неэффективно. На других задачах у меня, как правило, получалось 20х на 200 ядрах, без особых оптимизаций. Согласитесь, 150-кратное замедление по сравнению с "теорией" — это много.
Нужно попробовать учесть специфику CUDA (выполнение программы варпами и некоторую нелюбовь к ветвлениям):
- Для определения, является ли число sum пятой степенью целого числа, вместо бинарного поиска можно бы попробовать
double r = pow(sum,0.2) ; bool isPower5 = abs((uint32)(r+0.5)-r) < EPS;Не уверен, что возведение в степень действительно будет быстрее, но вдруг. - Самое важное: нити в вашей программе получают блоки работы разного объёма, поэтому в конце будут работать лишь несколько (а не несколько тысяч, как поддерживает GPU) варпов, на которые свалилась бОльшая часть работы. Остальная часть GPU будет простаивать. Нужно разбить задачу на блоки примерно равного объёма, например, как-то пронумеровавать их, или обсчитывать меньшими кусками (вызывать ядро много раз), чтобы равномерно загрузить GPU. На OpenMP было бы достаточно написать
#pragma omp sсhedule(dynamic,n), на CUDA, наверно, можно попробовать рекурсивно вызывать ядро из того же ядра, CUDA вроде бы это сейчас поддерживает.
Я же просто продемонстрировал что даже скопировав код, не углубляясь в тонкости GPU, можно получить ускорение по времени в 10 раз.
А попробуйте внешний цикл на CPU вынести?
не углубляясь в тонкости GPU
Это зря. Не рекомендую такой подход. У GPU совершенно другая архитектура, CPU-код очень плохо ложится на неё. Если задача не разбита на несколько тысяч одновременно работающих нитей (в несколько раз больше, чем ядер) — видеокарта будет работать неэффективно. Туда же относятся особенности ветвлений.
В общем случае, архитектуру "железа" следует иметь в виду.
(Конечно, есть случаи, когда 10х будет достаточно, тогда можно просто скопировать код. Но чаще получить 200х вместо 10х будет лучше)
У Core i5-4440 99 ГФлопс с AVX. Так что чудес от видеокарты не ждите.
А для GPU не пытались проверить полосу (bandwidth) и сравнить с максимальной?
Я боюсь, что задачка для CUDA не очень показательная: объем данных небольшой, проблем с обращениями к памяти не будет.
Можно прямо код брать.
Многопоточная сказка о потерянном времени