我們可以並行執行此任務嗎？

Question

給定一個C字符串（以NULL字符常量結尾的字符數組），我們必須找到字符串的長度。你能否建議一些方法來並行化N個執行線程。我有問題分爲子問題，因爲訪問不存在的數組位置會導致分段錯誤。

編輯：我不擔心並行執行此任務可能會有更大的開銷或更大的開銷。只是想知道這是否可以完成（使用類似openmp等）

Answer 1

不，它不能。因爲每一步都要求先前的狀態是已知的（我們是否在前一個字符上遇到null）。您一次只能安全檢查1個字符。想象一下，你正在翻越岩石，你必須停在一個白色的油漆下（空），否則你會死（又名塞格故障等）。

你不能讓人們彼此「向前工作」，因爲白色的油漆岩石可能介於兩者之間。

擁有多個人（線程/進程）只不過是他們輪流成爲下一個搖滾樂的人。他們永遠不會在彼此的同一時間翻轉岩石。

Answer 2

這可能不值得嘗試。如果字符串很短，開銷將大於處理速度的增加。如果字符串非常長，速度可能會受到內存速度的限制，而不是CPU處理速度。

Answer 3

讓我承認這一點，

下面的代碼已經被使用C＃，而不是C.你可以什麼，我想闡明想法的寫入。並且大部分內容來自並行模式（由微軟提供並行方式的草稿文件）

爲了儘可能做到最好的靜態分區，您需要能夠提前準確預測所有迭代將會持續多久採取。這很少可行，導致需要更加動態的分區，系統可以快速適應不斷變化的工作負載。我們可以通過轉移到分區折衷頻譜的另一端來解決這個問題，儘可能多的負載平衡。

爲此，我們可以讓線程競爭迭代，而不是向每個線程推送一組給定的索引進行處理。我們使用剩餘迭代池進行處理，最初開始充滿所有迭代。在處理完所有迭代之前，每個線程都進入迭代池，刪除迭代值，處理它，然後重複。以這種方式，我們可以以貪婪的方式達到最佳負載均衡水平的逼近（只有先驗知道每次迭代需要多長時間才能達到真正的最佳水平）。如果某個線程處理特定的長迭代，其他線程將同時處理來自池中的工作進行補償。當然，即使有了這個方案，你仍然可以發現自己的分區很不理想（如果一個線程碰巧遇到了比其他任務大得多的工作，就會發生這種情況），但是不知道處理時間多少給定的工作將需要，還有一點可以做。

下面是一個示例實現，它將負載平衡帶到了極致。迭代值的池保持爲代表的下一次迭代提供一個整數，並通過原子遞增這個整數參與處理「刪除項目」的主題：

public static void MyParallelFor( 
int inclusiveLowerBound, int exclusiveUpperBound, Action<int> body) 
{ 
// Get the number of processors, initialize the number of remaining 
// threads, and set the starting point for the iteration. 
int numProcs = Environment.ProcessorCount; 
int remainingWorkItems = numProcs; 
int nextIteration = inclusiveLowerBound; 
using (ManualResetEvent mre = new ManualResetEvent(false)) 
{ 
// Create each of the work items. 
for (int p = 0; p < numProcs; p++) 
{ 
ThreadPool.QueueUserWorkItem(delegate 
{ 
int index; 
while ((index = Interlocked.Increment( 
ref nextIteration) - 1) < exclusiveUpperBound) 
{ 
body(index); 
} 
if (Interlocked.Decrement(ref remainingWorkItems) == 0) 
mre.Set(); 
}); 
} 
// Wait for all threads to complete. 
mre.WaitOne(); 
} 
} 

Answer 4

我只用一個標準的C說字符串這不能完成。但是，如果你可以定義一個個人終止字符串，其字符數與過程一樣多 - 這很簡單。

Answer 5

你知道char數組的最大尺寸嗎？如果是這樣，你可以在不同的帆船上進行並行搜索，並返回索引最小的終止索引。 因此，你只是在分配的內存上工作，你不能得到段錯誤。

當然，這並不像s_nairs那樣複雜，而是非常簡單。 例如：

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <omp.h> 

int main(int argc, char **argv) 
{ 
    int N=1000; 
    char *str = calloc(N, sizeof(char)); 
    strcpy(str, "This is a test string!"); 
    fprintf(stdout, "%s\n", str); 

    int nthreads = omp_get_num_procs(); 
    int i; 
    int ind[nthreads]; 
    for(i = 0; i < nthreads; i++){ 
     ind[i] = -1; 
    } 

    int procn; 
    int flag; 
#pragma omp parallel private(procn, flag) 
    { 
     flag = 1; 
     procn = omp_get_thread_num(); 
#pragma omp for 
     for(i = 0; i < N; i++){ 
      if (str[i] == '\0' && flag == 1){ 
       ind[procn] = i; 
       flag = 0; 
      } 
     } 
    } 
    int len = 0; 
    for(i = 0; i < nthreads; i++){ 
     if(ind[i]>-1){ 
      len = ind[i]; 
      break; 
     } 
    } 
    fprintf(stdout,"strlen %d\n", len); 
    free(str); 
    return 0; 
} 

Answer 6

你可以做一些醜陋這樣在Windows封閉不安全內存在SEH __try塊讀取：

#include <windows.h> 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

#define N 2 

DWORD WINAPI FindZeroThread(LPVOID lpParameter) 
{ 
    const char* volatile* pp = (const char* volatile*)lpParameter; 

    __try 
    { 
    while (**pp) 
    { 
     (*pp) += N; 
    } 
    } 
    __except (EXCEPTION_EXECUTE_HANDLER) 
    { 
    *pp = NULL; 
    } 

    return 0; 
} 

size_t pstrlen(const char* s) 
{ 
    int i; 
    HANDLE handles[N]; 
    const char* volatile ptrs[N]; 
    const char* p = (const char*)(UINT_PTR)-1; 

    for (i = 0; i < N; i++) 
    { 
    ptrs[i] = s + i; 
    handles[i] = CreateThread(NULL, 0, &FindZeroThread, (LPVOID)&ptrs[i], 0, NULL); 
    } 

    WaitForMultipleObjects(N, handles, TRUE /* bWaitAll */, INFINITE); 

    for (i = 0; i < N; i++) 
    { 
    CloseHandle(handles[i]); 
    if (ptrs[i] && p > ptrs[i]) p = ptrs[i]; 
    } 

    return (size_t)(p - s); 
} 

#define LEN (20 * 1000 * 1000) 

int main(void) 
{ 
    char* s = malloc(LEN); 

    memset(s, '*', LEN); 
    s[LEN - 1] = 0; 

    printf("strlen()=%zu pstrlen()=%zu\n", strlen(s), pstrlen(s)); 

    return 0; 
} 

輸出：

strlen()=19999999 pstrlen()=19999999 

我認爲這可能是更好地使用MMX/SSE指令以某種平行的方式加速代碼。

編輯：這可能是在Windows不是一個很好的主意畢竟看到Raymond Chen的 IsBadXxxPtr should really be called CrashProgramRandomly。