Параллельный бинарный поиск

Я только начинаю изучать параллельное программирование и смотрю на бинарный поиск.

Это нельзя реально оптимизировать, добавляя больше процессоров, верно? Я знаю, что он якобы делится и побеждает, но вы действительно "убываете и побеждаете" (из Википедии).

Или вы могли бы распараллелить сравнения? (если X меньше чем array[mid]поиск от low в mid - 1; иначе если X больше, чем array[mid] поиск от mid + 1 в high, иначе возврат mid, индекс X)

Или как насчет того, чтобы отдать половину массива одному процессору для выполнения двоичного поиска, а другую половину - другому? Разве это не расточительно? Потому что это уменьшается и завоевывает, а не просто разделяет и завоевывает? Мысли?

6 ответов

Вы можете легко использовать параллелизм.

За k меньше чем n процессоры, разбить массив на n/k групп и назначить процессор для каждой группы.

Запустите бинарный поиск по этой группе.

Теперь время log(н / к).

Есть также метод команды, который является logn / log(k + 1).

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

У меня нет большого опыта в параллельном программировании, но я сомневаюсь, что это хороший кандидат для параллельной обработки. Каждый шаг алгоритма зависит от выполнения одного сравнения, а затем продвижения по заданному "пути" на основе этого сравнения (вы либо нашли свое значение, либо теперь должны продолжать поиск в заданном "направлении" на основе сравнения). Два отдельных потока, выполняющие одно и то же сравнение, никуда не приведут вас быстрее, и оба потока должны будут полагаться на одно и то же сравнение, чтобы решить, что делать дальше, так что они не могут действительно выполнять какую-либо полезную, разделенную работу самостоятельно,

Что касается вашей идеи разделения массива, я думаю, что вы просто отрицаете преимущество бинарного поиска в этом случае. Ваше значение (при условии, что оно находится в вашем массиве) будет либо в верхней, либо в нижней половине вашего массива. Первое сравнение (в средней точке) в бинарном поиске покажет вам, какую половину вы должны искать. Если вы пойдете дальше, рассмотрите возможность разбиения массива из N элементов на N различных бинарных поисков (наивная попытка параллельного поиска). -ize). Теперь вы делаете N сравнений, когда вам это не нужно. Вы теряете силу бинарного поиска, поскольку каждое сравнение сужает ваш поиск до соответствующего подмножества.

Надеюсь, это поможет. Комментарии приветствуются.

Да, в классическом смысле распараллеливания (многоядерный), бинарный поиск и BST не намного лучше.

Существуют методики, такие как наличие нескольких копий BST в кэше L1 для каждого процессора. Активен только один процессор, но выигрыш от использования нескольких кэшей L1 может быть большим (4 цикла для L1 против 14 циклов для L2).

В реальных задачах вы часто ищете несколько ключей одновременно.

Теперь есть другой вид распараллеливания, который может помочь: SIMD! Ознакомьтесь с разделом "Быстрый поиск по дереву с учетом архитектуры на современных процессорах и графических процессорах" от команды Intel/UCSC/Oracle (SIGMOD 2010). Это очень круто. Кстати, я основываю свой текущий исследовательский проект именно на этой статье.

Параллельная реализация может ускорить бинарный поиск, но улучшение не является особенно значительным. В худшем случае, время, необходимое для бинарного поиска log_2(n) где n количество элементов в списке Простая параллельная реализация разбивает основной список на k подсписки для бинарного поиска параллельными потоками. Результирующее наихудшее время для двоичного поиска log_2(n/k) реализуя теоретическое сокращение времени поиска.

Пример: список 1024 записи занимает столько, сколько 10 циклически выполняет бинарный поиск, используя один поток. С помощью 4 потоки, каждый поток только будет принимать 8 циклы для завершения поиска. И используя 8 потоки, каждый поток занимает 7 циклы. Таким образом, 8 параллельный двоичный поиск может быть до 30% быстрее, чем однопоточная модель.

Однако его ускорение не следует путать с повышением эффективности: 8 резьбовая модель на самом деле выполняется 8 * 7 = 56 сравнения для завершения поиска по сравнению с 10 сравнения выполняются однопоточным двоичным поиском. Программист сам решает, является ли предельный выигрыш в скорости параллельного применения бинарного поиска подходящим или выгодным для их применения.

Я почти уверен, что бинарный поиск может быть ускорен с коэффициентом log (M), где M - число процессоров. log (n / M) = log (n) - log (M)> log (n) / log (M) для константы M. У меня нет доказательства для жесткой нижней границы, но если M = n, то время выполнения O (1), что не может быть лучше. Схема алгоритма следующая.

Parallel_Binary_Search (sorted_arraylist)

  1. Разделите ваш sorted_arraylist на M кусков размером n/M.
  2. Примените один шаг сравнения к среднему элементу каждого куска.
  3. Если компаратор сигнализирует равенство, верните адрес и завершите.
  4. В противном случае идентифицируйте оба смежных блока, где компараторы сигнализировали (>) и (<) соответственно.
  5. Сформируйте новый блок, начиная с элемента, следующего за сигнальным (>), и заканчивая элементом, предшествующим сигнальному (<).
  6. Если это один и тот же элемент, верните fail и завершите.
  7. В противном случае, Parallel_Binary_Search(Chunk)
Другие вопросы по тегам