Параллельный бинарный поиск
Я только начинаю изучать параллельное программирование и смотрю на бинарный поиск.
Это нельзя реально оптимизировать, добавляя больше процессоров, верно? Я знаю, что он якобы делится и побеждает, но вы действительно "убываете и побеждаете" (из Википедии).
Или вы могли бы распараллелить сравнения? (если 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)
- Разделите ваш sorted_arraylist на M кусков размером n/M.
- Примените один шаг сравнения к среднему элементу каждого куска.
- Если компаратор сигнализирует равенство, верните адрес и завершите.
- В противном случае идентифицируйте оба смежных блока, где компараторы сигнализировали (>) и (<) соответственно.
- Сформируйте новый блок, начиная с элемента, следующего за сигнальным (>), и заканчивая элементом, предшествующим сигнальному (<).
- Если это один и тот же элемент, верните fail и завершите.
- В противном случае, Parallel_Binary_Search(Chunk)