첫 번째 발생 병렬 문자열 매칭 알고리즘

Question

앞에 오면이 은 숙제입니다. 말하자면, 매우 개방적이며,이 문제 (또는 병렬 알고리즘)에 대해 생각하기 시작하는 방법에 관해서는 거의 지침이 없습니다. 포인터가 올바른 방향으로 가고 싶습니다. 은 전체 솔루션이 아닙니다. 도움이 될 수있는 독서도 우수 할 것입니다.

병렬 알고리즘을 사용하여 많은 양의 텍스트에서 패턴의 첫 번째 일치 항목을 일치시키는 효율적인 방법을 찾고 있습니다. 패턴은 간단한 문자 매칭이며 정규 표현식은 관련이 없습니다. 나는 의 모든을 찾을 수있는 방법을 찾아 낼 수 있었지만 그 다음에는 모든 경기를 살펴보고 첫 번째 것을 찾아야합니다.

그렇다면 질문을 통해 프로세스간에 텍스트를 깨고 성공을 거둘 수 있을까요? 아니면 j'th 프로세스가 패턴의 j 번째 문자를 검색 할 때 프로세스 동기화 검색을하는 것이 가장 좋을까요? 모든 프로세스가 일치하는 경우 true를 반환하면 프로세스는 해당 패턴과 일치하는 위치를 변경하고 모든 문자가 일치 될 때까지 계속 진행 한 다음 첫 번째 일치 항목의 인덱스를 반환합니다.

내가 지금까지 가지고있는 것은 극도로 기본이며, 작동하지 않을 수도 있습니다. 나는 이것을 구현하지 않겠지 만, 어떤 조언도 감사 할 것입니다.

P 프로세서, 길이 t의 텍스트, 길이 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

문자열을 깨는 것이 두려워합니다.

일반적으로 일찍 탈출하기가 어렵 기 때문에 텍스트를 분할하는 것이 좋습니다.

하지만 Herb Sutter에게 먼저 병렬 알고리즘으로 검색하는 방법을 Dr Dobbs에 설명하도록 요청합시다. 아이디어는 배포판의 비 균일 성을 사용하여 조기 반환을하는 것입니다. 물론 Sutter는 모든 경기에 관심이 있습니다.이 문제는 당면 문제가 아니므로 적응합시다.여기

내 생각이다,의 우리가 있다고 가정 해 봅시다 : N

p 프로세서 길이의

• 텍스트
• 발견 : max는 덩어리가 포함되어야 최대 문자 수의 아마 순서입니다 크기가 M보다 크면 패턴의 길이가됩니다.

지금, 당신이 원하는 것은 k을 최소화하고 size(chunk) 아직 최대 max 열등입니다 k 동일 덩어리로 텍스트를 분할하는 것입니다.

그런 다음 우리는 고전적인 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 over P processors 나는 프로세서를 통해 문자열을 분리 할뿐입니다. 각 프로세서는 길이 N/P + L-1의 청크를 취하고 마지막 L-1은 다음 프로세서에 속하는 문자열을 중첩합니다. 그런 다음 각 프로세서는 무거운 무어를 수행합니다 (두 개의 사전 처리 테이블이 공유 됨). 각 마감, 그들은 모든 프로세스가 응답 한 후 테이블을

Process Index 
    1 -1 
    2 2 
    3 23 

을 유지 최초의 프로세서에 결과를 반환 할 때 (또는 생각의 비트와 함께 당신은 조기 탈출을 할 수 있습니다), 당신은 첫 경기를 반환 . 평균 O (N/(L * P) + P)이어야합니다. i 번째 문자와 일치하는 i 번째 프로세서를 갖는 접근법은 프로세스 간 통신 오버 헤드가 너무 많이 필요합니다.

편집 : 이미 해결책이 있다는 것을 알고 있으며 모든 해결책을 찾을 필요없이 방법을 찾고 있습니다. 글쎄, 나는이 접근법이 필요하다고 생각하지 않는다. 조기 탈출 조건을 생각해 낼 수는 있지만 그다지 어렵지는 않지만 일반적으로 텍스트의 성냥 배포에 대한 추가 지식이없는 한 일반적으로 퍼포먼스가 향상 될 것이라고 생각하지 않습니다.