Как преобразовать этот последовательный итеративный бинарный поиск в параллельный алгоритм?

У меня есть этот массив (A) с n элементами, которые гарантированно будут отсортированы, и мне нужно выполнить бинарный поиск по ним в параллельной системе. Я начал с создания этого алгоритма бинарного поиска. Это итеративно, потому что я пока не уверен, как включить рекурсию в параллельную обработку.

/* Looking for element k in array A of length n */
min = 0;
max = n - 1;
while(min <= max)
{
    midpoint = min + ((max-min)/2); //index
    if(A[midpoint] > k) //discard upper half
        max = midpoint - 1;
    else if(A[midpoint] < k) //discard lower half
        min = midpoint + 1;
    else
        return midpoint; //Found k, return index
}
return -1; //not found

В параллельном алгоритме у меня есть доступ к процессорам p, и это система, которая позволяет одновременное чтение, но монопольную запись. Настоящая проблема в том, что я все еще думаю последовательно. То есть я не вижу способа, которым это можно было бы сделать с более чем одним процессором, поскольку вы не можете «выбросить» ненужную часть массива, не зная сначала, где вы находитесь с точки зрения среднего значения. Это кажется таким по своей сути последовательным.

Псевдокод:

Global:  //Variables accessible by all processors
  index; //index of k
  p;     //number of processors
  i;     //the i^th processor
  n;     //number elements in array A
  A[0, 1, ... , (n-1)];
local:   //Variables accessible by only the owning processor
         //Not sure what I need yet
Begin
  Spawn(P1, P2 . . . P(p-1)); //"create" the p processors
  for all P where 0 <= i <= (p-1) do //each processor does the following code
    //I'm stuck here
  endfor
End

И последнее: я увидел вопрос, отправленный пользователем, который спрашивал, есть ли способ выполнить бинарный поиск с параллельной обработкой. На этот вопрос не было действительно решающего ответа, потому что оба соответствующих ответа получили по 1 голосу. Один сказал, что это практически невозможно, потому что это пошаговый процесс, в то время как другой, похоже, уверен, что это будет действительно легко реализовать. Что ты думаешь?

Предыдущий вопрос о параллельном двоичном поиске


parallel-processing algorithm sequential
person The Unknown Dev    schedule 27.11.2012    source источник
comment
Я собирался предложить разделиться и бежать ... прежде чем я заметил, что это был второй ответ в том, который вы связали. Это технически неэффективно, но, вероятно, быстрее. Но я предполагаю, что причина путаницы в другом вопросе заключается в том, что это не распараллеливание бинарного поиска, а просто распараллеливание самого поиска.   -  person Karthik T    schedule 27.11.2012
comment
Разделение на P фрагментов сокращает время этапа поиска на O(log P) шага. Но настройка P потоков занимает O(P) времени.   -  person Daniel Fischer    schedule 27.11.2012

Ответы (2)


arrow_upward
3
arrow_downward

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

Наилучшими алгоритмами для параллельной работы являются те, которые имеют отдельные отдельные элементы, которые могут выполняться одновременно. Например, рендеринг 3D-графики в видео удобен тем, что каждый кадр независим и может быть передан отдельному процессору.

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

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

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

person user1855149    schedule 27.11.2012

arrow_upward
3
arrow_downward

Как и все проблемы, которые нужно решать параллельно… это во многом зависит от размера ваших данных, скорости ваших сообщений/разделяемой памяти и ваших требований.

Как быстро работают блокировки записи и как быстро выполняется синхронизация? Если они достаточно быстрые (например, с использованием общей памяти на одной машине) и размер ваших данных достаточно велик, может сработать особый вид техники «разделить и запустить». Вы можете думать об этом следующим образом:

Двоичный поиск — это подход «разделяй и властвуй», при котором вы обновляете диапазон, который изучаете, после каждой итерации — диапазон уменьшается вдвое на каждой итерации. Вместо того, чтобы делить текущий диапазон на 2, можно разделить его на p частей, где каждый процесс отвечает за одну из частей; на каждой итерации «победившая» часть (та, которая имеет целевое значение в своем диапазоне) записывает новый диапазон для поиска в память, и вы синхронизируете процессы перед запуском следующей итерации. Если у вас достаточно данных, переход от сокращения вдвое к сокращению данных на p каждый раз может оказаться выигрышным. Вы бы перешли от $O(log_2(x))$ к $O(log_p(x))$.

Такой подход работает только в том случае, если запись и синхронизация выполняются достаточно быстро, поскольку это зависит от выполнения много операций записи и синхронизации. Если вы делаете это в кластере, это становится дорогим. Если взаимодействие между процессами затруднено, возможно, лучшее, что вы можете сделать, — это «разделить и запустить», предложенное в другом посте, на который вы ссылаетесь. В частности, возьмите каждый p элемент вашего отсортированного списка и поместите его в другой узел. Затем, когда приходит запрос, выполните бинарный поиск на всех узлах. Если значения в вашем массиве уникальны, только один из узлов найдет ответ, и этот узел может вернуть результат. Это относительно плохой параллелизм, потому что вы повторяете большую часть работы — вы игнорируете порядок, существующий между массивами на разных узлах. Но это даст вам ускорение от $O(log_2(x))$ до $O(log_2(x/p))$.

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

person illya    schedule 27.11.2012