Как OpenMP реализует доступ к критическим разделам?

Question

Я хочу прочитать входной файл (в C/C++) и обработать каждую строку независимо, как можно быстрее. Обработка занимает несколько тактов, поэтому я решил использовать потоки OpenMP. У меня есть этот код:

#pragma omp parallel num_threads(num_threads)
{
  string line;
  while (true) {
#pragma omp critical(input)
    {
      getline(f, line);
    }
    if (f.eof())
      break;
    process_line(line);
  }
}

У меня вопрос, как мне определить оптимальное количество потоков для использования? В идеале я хотел бы, чтобы это динамически определялось во время выполнения. Я не понимаю вариант графика DYNAMIC для parallelПоэтому я не могу сказать, поможет ли это. Есть идеи?

Также я не уверен, как определить оптимальное количество "от руки". Я пробовал разные номера для моего конкретного приложения. Я бы подумал, что использование процессора сообщается top помогло бы, но это не (!) В моем случае загрузка ЦП остается неизменной на уровне num_threads*(85-95). Однако, используя pv чтобы наблюдать скорость, с которой я читаю ввод, я заметил, что оптимальное число составляет около 2-5; выше этого, входная скорость становится меньше. Итак, мой вопрос: зачем мне тогда использовать процессор 850 при использовании 10 потоков? Может ли это быть из-за неэффективности того, как OpenMP обрабатывает потоки, ожидающие попадания в критическую секцию?

РЕДАКТИРОВАТЬ: Вот некоторые моменты. Я получил их с:

for NCPU in $(seq 1 20) ; do echo "NCPU=$NCPU" ; { pv -f -a my_input.gz | pigz -d -p 20 | { { sleep 60 ; PID=$(ps gx -o pid,comm | grep my_prog | sed "s/^ *//" | cut -d " " -f 1) ; USAGE=$(ps h -o "%cpu" $PID) ; kill -9 $PID ; sleep 1 ; echo "usage: $USAGE" >&2 ; } & cat ; } | ./my_prog -N $NCPU >/dev/null 2>/dev/null ; sleep 2 ; } 2>&1 | grep -v Killed ; done

NCPU = 1 [8,27 МБ / с] использование: 98,4

NCPU = 2 [12,5 МБ / с] использование: 196

NCPU = 3 [18,4 МБ / с] использование: 294

NCPU = 4 [23,6 МБ / с] использование: 393

NCPU = 5 [28,9 МБ / с] использование: 491

NCPU = 6 [33,7 МБ / с] использование: 589

NCPU = 7 [37,4 МБ / с] использование: 688

NCPU = 8 [40,3 МБ / с] использование: 785

NCPU = 9 [41,9 МБ / с] использование: 884

NCPU = 10 [41,3 МБ / с] использование: 979

NCPU = 11 [41,5 МБ / с] использование: 1077

NCPU = 12 [42,5 МБ / с] использование: 1176

NCPU = 13 [41,6 МБ / с] использование: 1272

NCPU = 14 [42,6 МБ / с] использование: 1370

NCPU = 15 [41,8 МБ / с] использование: 1493

NCPU = 16 [40,7 МБ / с] использование: 1593

NCPU = 17 [40,8 МБ / с] использование: 1662

NCPU = 18 [39,3 МБ / с] использование: 1763

NCPU = 19 [38,9 МБ / с] использование: 1857

NCPU = 20 [37,7 МБ / с] использование: 1957

Моя проблема в том, что я могу достичь скорости 40 МБ / с при использовании процессора 785, а также при использовании процессора 1662. Куда идут эти дополнительные циклы??

РЕДАКТИРОВАТЬ 2: Благодаря Лирику и Джону Диблингу, я теперь понимаю, что причина, по которой я нахожу вышеописанные моменты времени, не имеет ничего общего с вводом / выводом, а скорее с тем, как OpenMP реализует критические секции. Моя интуиция заключается в том, что если у вас есть 1 поток внутри CS и 10 потоков, ожидающих входа, в момент, когда 1-й поток выходит из CS, ядро ​​должно пробудить еще один поток и позволить ему войти. Время показывает, что это может быть что нити много раз просыпаются сами по себе и обнаруживают, что CS занят? Это проблема с библиотекой потоков или с ядром?

Answer 1

"Я хочу прочитать входной файл (на C/C++) и обработать каждую строку независимо, как можно быстрее".

Чтение из файла ограничивает ввод-вывод вашего приложения, поэтому максимальная производительность, которую вы сможете достичь только для части чтения, - это чтение с максимальной скоростью диска (на моем компьютере это меньше 10% процессорного времени). Это означает, что если бы вы смогли полностью освободить поток чтения от какой-либо обработки, это потребовало бы, чтобы обработка заняла меньше, чем оставшееся время ЦП (90% на моем компьютере). Если потоки обработки строки занимают больше, чем оставшееся время ЦП, вы не сможете идти в ногу с жестким диском.

В этом случае есть несколько вариантов:

1. Поставьте в очередь входные данные и дайте обрабатывающим потокам отключить "работу", пока они не поймают введенный ввод (учитывая, что у вас достаточно ОЗУ для этого).
2. Открывайте достаточное количество потоков и просто максимально используйте свой процессор, пока все данные не будут прочитаны, что является вашим наилучшим сценарием.
3. Отрегулируйте чтение / обработку, чтобы не занимать все системные ресурсы (на случай, если вас беспокоит отзывчивость пользовательского интерфейса и / или взаимодействие с пользователем).

"... обработка занимает несколько тактов, поэтому я решил использовать потоки OpenMP"

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

Обновить

Почему существует разница между

• (i) каждый процесс получает блокировку, извлекает данные, снимает блокировку, обрабатывает данные; а также
• (ii) один процесс: извлечение данных, получение блокировки, постановка в очередь, освобождение блокировки,
• другие: получить блокировку, снять чанк, снять блокировку, обработать данные?

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

Наконец (и, вероятно, самое главное), вы можете использовать очередь без блокировки с одним производителем и одним потребителем, что сделает (ii) намного быстрее, чем (i) с точки зрения того, что вы будете связаны с вводом / выводом. С помощью очереди без блокировки вы можете извлекать данные, ставить в очередь блоки и блокировать блокировку без блокировки.

Answer 2

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

Оптимальное количество потоков, которое нужно использовать для обработки набора данных, сильно зависит от многих факторов, не в последнюю очередь из которых:

1. Сами данные
2. Алгоритм, который вы используете для его обработки
3. ЦП, на которых работают потоки
4. Операционная система

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

Как правило, для задач, связанных с вводом / выводом, я обычно начинаю с примерно 12 потоков на ядро ​​и настраиваюсь оттуда. Для задач, которые связаны с процессором, я бы начал с примерно 4 потоков на ядро ​​и пошел оттуда. Ключевым моментом является "переход оттуда", если вы действительно хотите оптимизировать использование вашего процессора.

Также имейте в виду, что вы должны сделать этот параметр настраиваемым, если вы действительно хотите оптимизировать, потому что каждая система, в которой он развернут, будет иметь разные характеристики.