Как реализовать рекурсивный поиск комбинаций в CUDA или OpenCL для больших наборов данных? ⇐ C++

[Anonymous]

У меня проблема с несколькими тысячами списков целых чисел, каждый из которых содержит тысячи элементов. Моя цель — найти комбинацию элементов (по одному из каждого списка), чтобы метод IsCombinationValid возвращал true. Вот как работает проверка:

• Метод IsCombinationValid принимает список выбранных значений и
  проверяет, образуют ли они допустимую комбинацию.
• Если введенные данные (например, x, y, z) недействительны, все комбинации, начинающиеся
  с этого ввода, также недействительны, поэтому их можно пропустить.

В настоящее время я использую рекурсивный подход в C++. Я выбираю один элемент из списка, проверяю его вместе с ранее выбранными значениями и, если он недействителен, перехожу к следующему элементу. Если все элементы в списке недействительны, я возвращаюсь к предыдущему списку и пробую его следующий элемент и так далее. Вот мой код на C++:

Код: Выделить всё

void Finder(uint32_t threadIdx, uint32_t firstListStartElementIdx, uint32_t firstListEndElementIdx, std::vector &lists) {
std::vector listsCurrentElementIdx;
listsCurrentElementIdx.push_back(firstListStartElementIdx);
size_t firstListElementCount = lists[0].size();

CheckCurrentList:;

if (isFound) return;

uint32_t currentListIdx = listsCurrentElementIdx.size() - 1;

if (currentListIdx == 0) {
if (listsCurrentElementIdx.back() >= firstListEndElementIdx) {
printf("### failed : threadIdx %u\n", threadIdx);
return;
} else {
listsCurrentElementIdx.push_back(0);
goto CheckCurrentList;
}
}

std::vector &currentList = lists[currentListIdx];
uint32_t &currentListElementIdx = listsCurrentElementIdx.back();

while (currentListElementIdx < currentList.size()) {
if (!IsCombinationValid(lists, listsCurrentElementIdx)) goto CurrentListElementInvalid;

// Valid combination found
if (lists.size() == listsCurrentElementIdx.size()) {
isFound = 1;
// Print combination
return;
}
listsCurrentElementIdx.push_back(0);
goto CheckCurrentList;

CurrentListElementInvalid:;
++currentListElementIdx;
}

listsCurrentElementIdx.pop_back();
listsCurrentElementIdx.back()++;
goto CheckCurrentList;
}

В этом коде первый список разделен между потоками. Этот подход работает, но неосуществим для больших списков, даже при многопоточности процессора. Я хочу реализовать это в CUDA или OpenCL, чтобы использовать параллелизм графического процессора, но я новичок в программировании графического процессора.
Проблема:
Я не знаю, как эффективно разделить работу между потоками графического процессора для решения этой проблемы:

• Каждому потоку может потребоваться выполнить обратный поиск независимо , а некоторые потоки могут завершиться раньше времени, не найдя допустимой комбинации, что приведет к простою потоки.
• Синхронизация работы и обмен частичными результатами между потоками кажутся сложными в этой рекурсивной проблеме с возвратом.

Может ли кто-нибудь подсказать мне, как структурировать эту проблему для CUDA или OpenCL? Есть ли какие-либо примеры или шаблоны, которым я могу следовать для решения подобных рекурсивных задач, связанных с досрочным завершением и возвратом? Также будут полезны любые советы по разделению рабочей нагрузки и обработке простаивающих потоков.

Подробнее здесь: https://stackoverflow.com/questions/793 ... large-data