Распараллелить цикл while с OpenMP - PullRequest
Новая
       4

Распараллелить цикл while с OpenMP

9 голосов
/ 23 сентября 2011

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

int main()
{
  char buffer[BUFFER_SIZE];
  while(fgets(buffer, BUFFER_SIZE, stdin))
  {
    fgets(buffer, BUFFER_SIZE, stdin);
    do_some_simple_processing_on_the_second_line_of_the_record(buffer);
    fgets(buffer, BUFFER_SIZE, stdin);
    fgets(buffer, BUFFER_SIZE, stdin);
  }
  print_out_result();
}

Это, конечно, оставляет некоторые детали (здравомыслие / проверка ошибок и т. Д.), Но это не имеет отношения к вопросу.

Программа работает нормально, но файлы данных, с которыми я работаю, огромны. Я решил попытаться ускорить программу, распараллелив цикл с OpenMP. Однако после небольшого поиска выясняется, что OpenMP может обрабатывать только циклы for, если заранее известно количество итераций. Поскольку я заранее не знаю размер файлов, и даже такие простые команды, как wc -l, занимают много времени, как я могу распараллелить эту программу?

Ответы [ 3 ]

9 голосов
/ 24 сентября 2011

Как уже упоминалось, этот код может быть ограничен вводом / выводом. Однако в наши дни многие компьютеры могут иметь SSD и RAID-диски с высокой пропускной способностью. В таком случае вы можете получить ускорение от распараллеливания. Более того, если вычисление не тривиально, то распараллеливание выигрывает. Даже если ввод-вывод эффективно сериализован из-за насыщенной полосы пропускания, вы все равно можете получить ускорение, распределяя вычисления на многоядерные.

Возвращаясь к самому вопросу, вы можете распараллелить этот цикл с помощью OpenMP. С stdin я понятия не имею, чтобы распараллелить, потому что он должен читать последовательно и без предварительной информации о конце. Однако, если вы работаете с типичным файлом, вы можете это сделать.

Вот мой код с omp parallel. Я использовал Win32 API и MSVC CRT: 

void test_io2()
{
  const static int BUFFER_SIZE = 1024;
  const static int CONCURRENCY = 4;

  uint64_t local_checksums[CONCURRENCY];
  uint64_t local_reads[CONCURRENCY];

  DWORD start = GetTickCount();

  omp_set_num_threads(CONCURRENCY);

  #pragma omp parallel
  {
    int tid = omp_get_thread_num();

    FILE* file = fopen("huge_file.dat", "rb");
    _fseeki64(file, 0, SEEK_END);
    uint64_t total_size = _ftelli64(file);

    uint64_t my_start_pos = total_size/CONCURRENCY * tid;
    uint64_t my_end_pos   = min((total_size/CONCURRENCY * (tid + 1)), total_size);
    uint64_t my_read_size = my_end_pos - my_start_pos;
    _fseeki64(file, my_start_pos, SEEK_SET);

    char* buffer = new char[BUFFER_SIZE];

    uint64_t local_checksum = 0;
    uint64_t local_read = 0;
    size_t read_bytes;
    while ((read_bytes = fread(buffer, 1, min(my_read_size, BUFFER_SIZE), file)) != 0 &&
      my_read_size != 0)
    {
      local_read += read_bytes;
      my_read_size -= read_bytes;
      for (int i = 0; i < read_bytes; ++i)
        local_checksum += (buffer[i]);
    }

    local_checksums[tid] = local_checksum;
    local_reads[tid]     = local_read;

    fclose(file);
  }

  uint64_t checksum = 0;
  uint64_t total_read = 0;
  for (int i = 0; i < CONCURRENCY; ++i)
    checksum += local_checksums[i], total_read += local_reads[i];

  std::cout << checksum << std::endl
    << total_read << std::endl
    << double(GetTickCount() - start)/1000. << std::endl;
}

Этот код выглядит немного грязным, потому что мне нужно было точно распределить объем файла для чтения. Тем не менее, код довольно прост. Имейте в виду, что вам нужно иметь указатель файла для каждого потока. Вы не можете просто поделиться указателем файла, потому что внутренняя структура данных не может быть поточно-ориентированной. Кроме того, этот код может быть распараллелен parallel for. Но я думаю, что этот подход более естественный.

Простые экспериментальные результаты

Я протестировал этот код для чтения файла объемом 10 ГБ на жестком диске (WD Green 2 ТБ) и на SSD (Intel 120 ГБ).

С жестким диском да, ускорений не было. Даже замедления не наблюдалось. Это ясно показывает, что этот код ограничен вводом / выводом. Этот код практически не имеет вычислений. Просто я / O.

Однако с SSD у меня было ускорение на 1,2 с 4 ядрами. Да, ускорение мало. Но вы все равно можете получить его с SSD. И если вычисления станут немного больше (я просто поставил очень короткий цикл ожидания занятости), ускорения будут значительными. Я смог получить ускорение 2,5.

В целом, я хотел бы рекомендовать вам попробовать распараллелить этот код.

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

3 голосов
/ 23 сентября 2011

Вы проверили, что ваш процесс на самом деле связан с процессором, а не с вводом / выводом?Ваш код очень похож на код ввода-вывода, который ничего не выиграет от распараллеливания.

0 голосов
/ 09 марта 2015

В ответ на «возражение» я не думаю, что ваш код на самом деле что-то здесь оптимизирует. Существует много распространенных недоразумений в отношении этого оператора «#pragma omp parallel», этот на самом деле просто порождает потоки, без ключевого слова «for», все потоки будут просто выполнять любые коды, которые следуют. Таким образом, ваш код будет дублировать вычисления в каждом потоке. Отвечая на вопрос Даниэля, вы были правы: OpenMP не может оптимизировать цикл while, единственный способ оптимизировать его - это реструктурировать код так, чтобы итерация была известна заранее (например, при выполнении цикла один раз со счетчиком). Извините за публикацию другого ответа, так как я пока не могу комментировать, но, надеюсь, это устраняет распространенные недоразумения.

...