Алгоритм сопоставления параллельных строк первого порядка

Question

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

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

Итак, вопрос в том, будет ли у меня больше успеха, нарушая текст между процессами и сканированием таким образом? Или было бы лучше, если бы какой-то процесс выполнял синхронизацию процессов, где j-й процесс ищет j-й символ шаблона? Если тогда все процессы возвращают true для их соответствия, процессы будут менять свою позицию в соответствии с указанным шаблоном и снова двигаться вверх, продолжая до тех пор, пока все символы не будут сопоставлены, а затем вернут индекс первого совпадения.

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

С р процессорами, текстом длиной т, а шаблоном длиной L и потолком L процессоров, используемым:

 
for i=0 to t-l: 
    for j=0 to p: 
     processor j compares the text[i+j] to pattern[i+j] 
      On false match: 
       all processors terminate current comparison, i++ 
      On true match by all processors: 
       Iterate p characters at a time until L characters have been compared 
       If all L comparisons return true: 
        return i (position of pattern) 
       Else: 
        i++ 

Answer 1

Я боюсь, что нарушение струны не будет выполнено.

Вообще говоря, раннее ускорение сложно, поэтому вам лучше сломать текст кусками.

Но давайте попросим Херба Саттера объяснить поиск с помощью параллельных алгоритмов сначала на Dr Dobbs. Идея состоит в том, чтобы использовать неравномерность распределения для раннего возвращения. Конечно, Саттер заинтересован в любом матче, что не является проблемой, поэтому давайте приспособиться.

Вот моя идея, скажем, мы имеем:

• Текст длины N
• p Процессоры
• эвристика: max максимальное количество символов кусок должен содержать, вероятно, порядок величина больше, чем M длина рисунка.

Теперь, что вы хотите, чтобы разбить текст на k равные куски, где k является минимальным и size(chunk) максимальна еще хуже max.

Затем у нас есть классический шаблон Producer-Consumer: процессы p подаются кусками текста, каждый процесс ищет шаблон в получаемом куске.

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

Давайте пример, с 3-мя процессорами:

[ 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ] 
         x  x 

Куски 6 и 8 оба содержат строку.

Производитель сначала будет подавать 1, 2 и 3 процессам, затем каждый процесс будет продвигаться в своем собственном ритме (это зависит от сходства найденного текста и шаблона).

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

Основная идея заключается в том, что вы не хотите смотреть на весь текст! Это расточительно!

Answer 2

Учитывая образец длиной L, и поиск в строке длины N более P процессоров я бы просто разделил строку над процессорами. Каждый процессор занимает кусок длины N/P + L-1, причем последний L-1 перекрывает строку, принадлежащую следующему процессору. Затем каждый процессор будет исполнять битвер-боре (две таблицы предварительной обработки будут разделены). Когда каждый заканчивается, они будут возвращать результат в первый процессор, который поддерживает таблицу

Process Index 
    1 -1 
    2 2 
    3 23 

После откликнулись все процессы (или с небольшим количеством мысли вы можете иметь ранний побег), вы вернете первый матч , Это должно быть в среднем O (N/(L * P) + P).

Подход к i-му процессору, соответствующему i-му символу, потребует слишком больших затрат на межпроцессное взаимодействие.

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