Накладные расходы потокового графа Intel TBB

Вот моя попытка оценить производительность потокового графа Intel TBB. Вот установка:

  • Один широковещательный узел отправляет continue_msg узлам-преемникам N
    (a broadcast_node<continue_msg>)
  • Каждый последующий узел выполняет вычисление, которое занимает t секунд.
  • Общее время вычислений при серийном выполнении составляет Tserial = N * t.
  • Идеальное время вычисления, если используются все ядра, составляет Tpar(ideal) = N * t / C, где C - количество ядер.
  • Ускорение определяется как Tpar(actual) / Tserial.
  • Я тестировал код с помощью gcc5 на 16-ядерном ПК.

Вот результаты, показывающие ускорение в зависимости от времени обработки отдельной задачи (т. Е. Тела):

t = 100 microsecond  ,   speed-up =  14
t  = 10 microsecond  ,   speed-up =   7
t  =  1 microsecond  ,   speed-up =   1

Как и в случае легких задач (вычисление которых занимает менее 1 микросекунды), параллельный код на самом деле медленнее, чем последовательный.

Вот мои вопросы:

1) Соответствуют ли эти результаты тестам Intel TBB?
2) Это лучшая парадигма, чем потоковый граф для случая, когда есть тысячи задач. каждый занимает менее 1 микросекунды?


multithreading parallel-processing intel parallelism-amdahl tbb-flow-graph
person motam79    schedule 03.01.2018    source источник

Ответы (3)


arrow_upward
4
arrow_downward

Накладные расходы на параллелизм

Ваша модель затрат неверна.

Идеальное время параллельных вычислений:

Tpar(ideal) = N * t / C + Pstart + Pend

где Pstart - это время, необходимое для начала параллелизма, а Pend - время, необходимое для его завершения. Для Pstart нет ничего необычного в том, что оно составляет порядка десятков миллисекунд.

Я не уверен, знаком ли вы с OpenMP (хотя это полезно знать), но для наших целей это модель потоков, которая разделяет работу между группой потоков. На следующей диаграмме показаны накладные расходы некоторых команд в зависимости от размера группы потоков:

Накладные расходы на потоки OpenMP

Вывод состоит в том, что запуск вашего параллелизма (строка parallel for) потенциально дорогостоящий и растет с увеличением количества потоков. Прекращение параллелизма (строка barrier) имеет аналогичные затраты.

Фактически, если вы посмотрите учебник TBB, Раздел 3.2.2 («Автоматическое разбиение на части») говорит:

ВНИМАНИЕ: Обычно цикл должен занять не менее миллиона тактов для parallel_for, чтобы повысить его производительность. Например, цикл, который занимает не менее 500 микросекунд на процессоре с частотой 2 ГГц, может выиграть от parallel_for.

Повышение скорости

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

#include <tbb/parallel_for.h>

// . . .
if(work_size>1000)
  tbb::serial::parallel_for( . . . );
else
  tbb::parallel_for( . . . );
// . . .

где вы хотели бы установить 1000 на достаточно высокое число, чтобы вы начали замечать выгоды от параллелизма.

Вы также можете уменьшить количество потоков, так как это несколько снижает накладные расходы:

tbb::task_scheduler_init init(nthread);

TBB также выполняет динамическую балансировку нагрузки (см. здесь). Это замечательно, если вы ожидаете, что ваши итерации / задачи цикла будут иметь широкое распределение времени выполнения, но представляют собой ненужные накладные расходы, если ожидаемое время выполнения одинаково. Я не уверен, есть ли у TBB статическое планирование, но, возможно, стоит изучить его.

Если люди останутся здесь без твердой приверженности TBB, в OpenMP вы должны сделать что-то вроде:

#pragma omp parallel for if(work_size>1000) num_threads(4) schedule(static)
person Richard    schedule 03.01.2018
comment
Стоимость не будет отличаться, и мне нравятся цифры. - person Richard; 03.01.2018
comment
@Richard Ваш ответ действителен в контексте parallel_for, когда разбиение на части можно легко контролировать, изменяя размер зерна. Однако, если у нас есть граф вычислений с несколькими узлами, время вычислений которых различается (но известно), необходим дополнительный уровень оптимизации / планирования, чтобы на каждой фазе графа решить, сколько следует выполнить разбиение на части. Я думаю, что потоковый граф Intel TBB не подходит для графов массовых вычислений с микро-полезными нагрузками. - person motam79; 03.01.2018
comment
Это похоже на многопоточное планирование DAG с учетом накладных расходов. Я не уверен, есть ли какие-нибудь библиотеки / инструменты, которые могут это сделать. - person motam79; 03.01.2018
comment
@ motam79: Я на самом деле сейчас работаю над похожими проблемами. Если вы можете структурировать свой DAG как обход в ширину, я думаю, есть способы его ускорить, и у меня есть пример кода / документа, над которым я работаю, который я мог бы вам прислать. - person Richard; 03.01.2018
comment
@Richard Это было бы здорово! Я скоро напишу вам электронное письмо. Я также могу прислать вам свой образец кода на C ++. - person motam79; 03.01.2018
comment
@ motam79: Вы можете легко найти мою электронную почту в моем профиле. Если мы сможем что-то выяснить, я могу скорректировать свой ответ здесь, чтобы отразить то, что необходимо. - person Richard; 03.01.2018
comment
Позвольте нам продолжить это обсуждение в чате. - person motam79; 04.01.2018

arrow_upward
2
arrow_downward

Ad 1 )

Это отличный пример, где важны детали. Tpar(ideal) = N * t / C - это больше желание, чем что-то, что могло бы случиться на самом деле.

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

Почему слишком строгий закон Амдала?

Почему? Потому что эти накладные расходы решают больше, чем количество ядер.

Дело в том, что по мере того, как размер "полезной" нагрузки становится все меньше и меньше, накладные расходы (даже те очень маленькие, как в сверхоптимизированном инструменте, например, о TBB не может быть и речи) - эти накладные расходы всегда накапливаются на чистом. [SERIAL] часть графа проблемных вычислений.

Итак, поскольку мы продолжаем становиться все меньше и меньше [PARALLEL] полезных нагрузок, их принципиально ненулевые затраты на {setup | termination}, что планирование по ядрам на самом деле стоит, в какой-то момент станет выше, чем любая "следующая" выгода от обратно пропорционального коэффициента 1 / numCOREs, который применяется только к линейной продолжительности чистого [PARALLEL]-вычислительного пути, но все это добавляет -on накладные расходы суммируют и расширяют путь [SERIAL]-вычислений быстрее, чем любой растущий numCOREs может компенсировать, а ускорения становятся ниже ‹< 1x.
QED

Ad 2 )

Это из описанных выше игровых площадок, игра с минимумом боли.

Если кто-то хочет ускорить примерно ~ 4,000 CPU uops ~ <= 1 [us], он не должен тратить буквально ни одной наносекунды на все задержки и дополнительные накладные расходы, если пытается это сделать, предположим, что окончательное ускорение остается не менее> = 1x

Если мы не верим в сказки, лучше всего получить FPGA для прототипирования PoC и ASIC / SoC для развертывания производственного уровня.

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

Бонус: векторизованный код может дать сбой на некоторых CPU (лучше этого избегайте):

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

Ошибки, связанные с повреждением Intel Hyperthread (SKZ7 / SKW144 / SKL150 / SKX150 / SKZ7 / KBL095 / KBW095) Короткие циклы, в которых используются регистры AH / BH / CH / DH, могут вызывать непредсказуемое поведение системы .

Проблема:
В сложных условиях микроархитектуры короткие циклы из менее чем 64 инструкций, которые используют регистры AH, BH, CH или DH, а также соответствующие им более широкие регистры (например, RAX, EAX или AX для AH) может вызвать непредсказуемое поведение системы. Это может произойти только в том случае, если активны оба логических процессора на одном физическом процессоре.

Последствия:
Из-за этой ошибки система может работать непредсказуемо. Эта ошибка может повлиять на ... гостевую ОС.

Ссылки:
https://caml.inria.fr/mantis/view.php?id=7452 http://metadata.ftp-master.debian.org/changelogs/non-free/i/intel-microcode/unstable_changelog https://www.intel.com/content/www/us/en/processors/core/desktop-6th-gen-core-family-spec-update.html https://www.intel.com/content/www/us/en/processors/core/7th-gen-core-family-spec-update.html https://www.intel.com/content/www/нас/en/процессоры/xeon/xeon-e3-1200v6-spec-update.html https://www.intel.com/content/www/us/en/processors/xeon/xeon-e3-1200v5-spec-update.html https://www.intel.com/content/www/us/en/products/processors/core/6th-gen-x-series-spec-update.html

person user3666197    schedule 03.01.2018
comment
Что за Ad, пожалуйста? - person Mark Setchell; 03.01.2018
comment
: o) услышали это впервые за 60 лет. Классическое латинское наследие - так часто используется как во время обучения, так и в таких терминах, как ad-hoc, ad absurdum, ad informandum, ad infimum - person user3666197; 03.01.2018
comment
Итак, вы просто используете его в латинском смысле в сторону или в направлении - извините, я просто не ожидал латыни. Должен признаться, что я тоже не знаю до бесконечности - для меня это звучит как толстая мать. - person Mark Setchell; 03.01.2018
comment
: o) математика, элементарные термины {supremum, infimum, ..} N / P. Я слышу это изо дня в день, так что вы действительно поймали меня своим первым вопросом. - person user3666197; 03.01.2018

arrow_upward
1
arrow_downward

У @Richard есть правильный ответ (а в руководствах TBB рассказывается о концепции планирования амортизации накладных расходов), и обычно я просто оставляю это как комментарий, но я хотел бы добавить одну вещь.

TBB использует «жадное планирование» для задач. Если существует задача, созданная выполнением предыдущей задачи (технически, если задача возвращает указатель задачи), эта задача является следующей, выполняемой в потоке. Это дает два преимущества:

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

tbb::flow_graph использует ту же идею; если у узла есть один или несколько преемников, по завершении его выполнения один из этих преемников выбирается следующим для запуска.

Обратной стороной этого является то, что если вы хотите изменить это поведение (выполнение узлов в порядке «в ширину» вместо «в глубину»), вам придется перепрыгнуть через некоторые препятствия. Это также будет стоить вам накладных расходов на планирование и потери местоположения.

person cahuson    schedule 04.01.2018