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

Question

У меня есть этот массив (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 голос. Один сказал, что это фактически невозможно, потому что это пошаговый процесс, в то время как другой кажется довольно уверенным, что это будет действительно легко осуществить. о чем ты думаешь?

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

Answer 1

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

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

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

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

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

Answer 2

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

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

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

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

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