Издержки на блок-схеме Intel TBB

Question

Издержки на блок-схеме Intel TBB

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

Отправка одного широковещательного узла continue_msg в N последующие узлы
(а 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 микросекунды?

3

multithreading parallel-processing intel tbb parallelism-amdahl

Источник

user2030532 03 янв '18 в 17:06

3 ответа

Решение

Объявление 1)

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

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

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

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

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

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

Объявление 2)

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

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

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

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

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

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

Ошибки 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/us/en/processors/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/ о / продукты / процессоры / ядро / шестая-генераторная й-серия спекуляция-update.html

2

Источник

user3666197 03 янв '18 в 17:38

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

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

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

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

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

2

Источник

user2611220 04 янв '18 в 19:25

Другие вопросы по тегам multithreading parallel-processing intel tbb parallelism-amdahl

user752843 03 янв '18 в 17:44 2018-01-03 17:44 · Accepted Answer · 2018-01-03 17:44

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

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

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

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

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

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

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

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

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

Достижение лучшей скорости

Лучший способ ускорить выполнение кода подобным образом - это выполнять операции параллельно, только если их много, и / или регулировать количество потоков, выполняющих работу, так чтобы у каждого потока было много работы. В 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)

Издержки на блок-схеме Intel TBB

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

3 ответа

Объявление 1)

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

Объявление 2)

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

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