Параллельный алгоритм для сохранения порядка выбора из таблицы индексов

Сохранение порядка выбора из таблицы индексов тривиально в последовательном коде, но в многопоточности менее просто, особенно если требуется сохранить эффективность (весь смысл многопоточности), избегая связанных списков. Рассмотрим серийный код

template<typename T>
std::vector<T> select_in_order(
  std::vector<std::size_t> const&keys, // permutation of 0 ... key.size()-1
  std::vector<T> const&data)           // anything copyable
{ // select data[keys[i]] allowing keys.size() >= data.size()
  std::vector<T> result;
  for(auto key:keys)
    if(key<data.size())
      result.push_back(data[key]);
  return result;
}

Как я могу сделать это многопоточным (скажем, используя TBB или даже OpenMP), в частности, если data.size() < key.size()?

Источник

2 ответа

Решение

Операция параллельных вычислений, которую вы ищете, называется Stream Compaction.

Сжатие потока

Он может быть эффективно реализован параллельно, хотя алгоритм нетривиален. Лучше всего будет использовать библиотеку, которая уже реализует это, например Thrust. Если вы действительно хотите реализовать себя, объяснение алгоритма можно найти в главе 39.3.1 "Программирование на GPU" или, альтернативно, в курсе "Введение в параллельное программирование" Udacity, урок 4.5.

По сути, это включает в себя определение логического предиката для вашего массива (в вашем примере, key<data.size() ), сопоставляя его с отдельным массивом, просматривая массив предикатов, затем делая разброс.

Map() а также Scatter() легко реализовать параллельно; реализация Scan() нетривиальная часть. Большинство параллельных библиотек будут иметь Scan() реализация; если нет, то обе ссылки описывают несколько алгоритмов параллельного сканирования.

Все это при условии, что у вас много ядер, как на GPU. На процессоре, вероятно, было бы просто сделать это последовательно; или для разделения массива на большие порции, последовательной обработки порций (параллельно на разных ядрах) и объединения результатов воедино. Какой подход лучше всего, зависит от ваших данных (первый работает лучше, если ожидается, что большинство ключей будет в конечном массиве).

Источник

Распределение ключей между потоками, например, с помощью N потоков вы дадите T1 ключи {0, key.size() / N - 1}, T2 получит ключи {key.size() / N, 2 * key.size() / N - 1} и т. Д., И TN получает ключи {(N - 1) / N * keys.size(), keys.size() - 1}. Каждый поток помещает свои результаты в локальный контейнер потока, и вы объединяете контейнеры, когда потоки заканчиваются. Таким образом, вам не нужно выполнять синхронизацию между потоками.

Самый эффективный способ объединить контейнеры - это связать контейнеры списками, поскольку список T2 легко добавить в список T1 и так далее. Однако, как вы сказали, лучше избегать связанных списков, так как они плохо распараллеливаются.

Другой вариант заключается в том, чтобы каждый поток сохранял свои результаты в локальном массиве thead и затем объединял эти массивы после завершения потоков; Вы можете выполнить это слияние параллельно (размер результатов каждого потока равен T{N}results.size(); с учетом окончательного массива слияния final_resultsT1 объединяет свои данные с final_results[0, T1results.size()-1]T2 объединяет свои данные с final_results[T1results.size(), T1results.size() + T2results.size()-1]T3 объединяет свои результаты с final_results[T1results.size() + T2results.size(), T1results.size() + T2results.size + T3results.size()-1], так далее).

Другой вариант - использовать общий concurrent_hash_map из TBB с key в качестве ключа и data[key] в качестве значения.

Источник
Другие вопросы по тегам