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

Question

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

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

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

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

Answer 1

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

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

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

Теперь время составляет log (n / k) .

Существует также метод экипажа, который logn / log (k + 1) .

Answer 2

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

Answer 3

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

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

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

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

Answer 4

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

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

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

Answer 5

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

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

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

Answer 6

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