Можем ли мы распараллелить эту задачу?

Question

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

EDIT : я не обеспокоен тем, что выполнение этой задачи параллельно можетиметь гораздо большие накладные расходы или нет.Просто хочу знать, можно ли это сделать (используя что-то вроде openmp и т. Д.)

Answer 1

Нет, не может. Потому что каждый шаг требует, чтобы предыдущее состояние было известно (встречались ли мы с нулем на предыдущем символе). Вы можете безопасно проверять только 1 символ за раз.

Представьте, что вы переворачиваете камни, и вы ДОЛЖНЫ остановиться на одной из них с белой краской внизу (ноль), иначе вы умрете (так называемая ошибка сегмента и т. Д.).

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

Наличие нескольких человек (потоков / процессов) будет просто по очереди превращать их в следующий камень. Они никогда не будут переворачивать камни одновременно друг с другом.

Answer 2

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

Answer 3

Вы могли бы сделать что-то ужасное в 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 инструкции для ускорения кода несколько параллельным способом.

EDIT : В конце концов, это может быть не очень хорошая идея для Windows, см. IsBadXxxPtr Раймонда Чена:на самом деле называется CrashProgramRandomly .

Answer 4

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

Конечно, это не так сложно, как ответ 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 5

Я бы сказал, что только со стандартной C-струной это сделать невозможно. Однако, если вы можете определить личную строку завершения, содержащую столько символов, сколько процессов - это просто.

Answer 6

Позвольте мне подтвердить это,

Следующий код был написан с использованием C #, а не C. Вы можете связать идею с тем, что я пытаюсь сформулировать. И большая часть контента взята из Parallel Pattern (это был проект документа Microsoft о параллельном подходе)

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

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

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

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(); 
} 
}