Ускорение

Процесс повышения производительности между двумя системами, решающими одну и ту же задачу

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

Определения

Ускорение можно определить для двух различных типов величин: задержки и пропускной способности . ^[1]

Задержка архитектуры — это величина, обратная скорости выполнения задачи:

${\displaystyle L={\frac {1}{v}}={\frac {T}{W}},}$

где

• v — скорость выполнения задачи;
• T — время выполнения задачи;
• W — объем работы по выполнению задачи.

Пропускная способность архитектуры — это скорость выполнения задачи:

${\displaystyle Q=\rho vA={\frac {\rho AW}{T}}={\frac {\rho A}{L}},}$

где

• ρ — плотность выполнения (например, число этапов в конвейере инструкций для конвейерной архитектуры);
• A — производительность (например, количество процессоров для параллельной архитектуры).

Задержка часто измеряется в секундах на единицу рабочей нагрузки выполнения. Пропускная способность часто измеряется в единицах рабочей нагрузки выполнения в секунду. Другая единица пропускной способности — это инструкции за цикл (IPC), а ее обратная величина — циклы за инструкцию (CPI) — это еще одна единица задержки.

Ускорение не имеет размерности и определяется по-разному для каждого типа величины, поэтому оно является единой метрикой.

Ускорение задержки

Ускорение задержки определяется по следующей формуле: ^[2]

${\displaystyle S_{\text{latency}}={\frac {L_{1}}{L_{2}}}={\frac {T_{1}W_{2}}{T_{2}W_{1}}},}$

где

• S _latency — ускорение задержки архитектуры 2 по отношению к архитектуре 1;
• L ₁ — задержка архитектуры 1;
• L ₂ — задержка архитектуры 2.

Ускорение задержки можно предсказать с помощью закона Амдаля или закона Густафсона .

Ускорение пропускной способности

Ускорение пропускной способности определяется по формуле: ^[3]

${\displaystyle S_{\text{throughput}}={\frac {Q_{2}}{Q_{1}}}={\frac {\rho _{2}A_{2}T_{1}W_{2}}{\rho _{1}A_{1}T_{2}W_{1}}}={\frac {\rho _{2}A_{2}}{\rho _{1}A_{1}}}S_{\text{latency}},}$

где

• S _{пропускная способность} — ускорение пропускной способности архитектуры 2 по отношению к архитектуре 1;
• Q ₁ — пропускная способность архитектуры 1;
• Q ₂ — пропускная способность архитектуры 2.

Примеры

Использование времени выполнения

Мы тестируем эффективность предиктора ветвлений при выполнении программы. Сначала мы выполняем программу со стандартным предиктором ветвлений на процессоре, что дает время выполнения 2,25 секунды. Затем мы выполняем программу с нашим модифицированным (и, как мы надеемся, улучшенным) предиктором ветвлений на том же процессоре, что дает время выполнения 1,50 секунды. В обоих случаях рабочая нагрузка на выполнение одинакова. Используя нашу формулу ускорения, мы знаем

${\displaystyle S_{\text{latency}}={\frac {L_{\text{old}}}{L_{\text{new}}}}={\frac {2.25~\mathrm {s} }{1.50~\mathrm {s} }}=1.5.}$

Наш новый предсказатель ветвлений обеспечил ускорение в 1,5 раза по сравнению с оригиналом.

Использование циклов на инструкцию и инструкций на цикл

Мы также можем измерить ускорение в циклах на инструкцию (CPI), что является задержкой. Сначала мы выполняем программу со стандартным предсказателем ветвлений, что дает CPI 3. Затем мы выполняем программу с нашим модифицированным предсказателем ветвлений, что дает CPI 2. В обоих случаях рабочая нагрузка выполнения одинакова, и обе архитектуры не являются конвейерными и не параллельными. Использование формулы ускорения дает

${\displaystyle S_{\text{latency}}={\frac {L_{\text{old}}}{L_{\text{new}}}}={\frac {3~{\text{CPI}}}{2~{\text{CPI}}}}=1.5.}$

Мы также можем измерить ускорение в инструкциях за цикл ( IPC ), что является пропускной способностью и обратной величиной CPI. Использование формулы ускорения дает

${\displaystyle S_{\text{throughput}}={\frac {Q_{\text{new}}}{Q_{\text{old}}}}={\frac {0.5~{\text{IPC}}}{0.33~{\text{IPC}}}}=1.5.}$

Мы достигли того же 1,5-кратного ускорения, хотя мы измерили разные величины.

Дополнительные подробности

Пусть S — ускорение выполнения задачи, а s — ускорение выполнения части задачи, которая выигрывает от улучшения ресурсов архитектуры. Линейное ускорение или идеальное ускорение достигается, когда S = s . При запуске задачи с линейным ускорением удвоение локального ускорения удваивает общее ускорение. Поскольку это идеально, это считается очень хорошей масштабируемостью .

Эффективность — это показатель использования ресурсов улучшенной системы, определяемый как

${\displaystyle \eta ={\frac {S}{s}}.}$

Его значение обычно находится в диапазоне от 0 до 1. Программы с линейным ускорением и программы, работающие на одном процессоре, имеют эффективность 1, в то время как многие труднораспараллеливаемые программы имеют эффективность, такую ​​как 1/ln( s ) ^{[ необходима ссылка ]} , которая стремится к 0 по мере увеличения числа процессоров A = s .

В инженерном контексте кривые эффективности чаще используются для графиков, чем кривые ускорения, поскольку

• вся площадь графика полезна (тогда как в кривых ускорения половина пространства тратится впустую);
• легко увидеть, насколько хорошо работает усовершенствование системы;
• нет необходимости строить кривую «идеального ускорения».

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

Суперлинейное ускорение

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

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

Аналогичная ситуация возникает при поиске больших наборов данных, таких как геномные данные, искомые реализациями BLAST . Там накопленная оперативная память от каждого из узлов в кластере позволяет перемещать набор данных с диска в оперативную память, тем самым радикально сокращая время, необходимое, например, mpiBLAST для поиска. ^[5]

Сверхлинейное ускорение может также возникать при выполнении возврата параллельно: исключение в одном потоке может привести к тому, что несколько других потоков выполнят возврат раньше, прежде чем они сами достигнут исключения. ^[6]

Сверхлинейное ускорение может также возникать при параллельной реализации метода ветвей и границ для оптимизации: ^[7] обработка одного узла одним процессором может повлиять на работу, которую должны выполнить другие процессоры для других узлов.

Смотрите также

• Закон Амдаля
• Закон Густафсона
• Закон Брукса
• Метрика Карпа–Флатта
• Параллельное замедление
• Масштабируемость

Ссылки

1. Мартин, Майло. "Производительность и бенчмаркинг" (PDF) . Получено 5 июня 2014 г.
2. Хеннесси, Джон Л.; Дэвид А., Паттерсон (2012). Архитектура компьютера: количественный подход . Уолтем, Массачусетс: Morgan Kaufmann . стр. 46–47. ISBN 978-0-12-383872-8.
3. Baer, ​​Jean-Loup (2010). Архитектура микропроцессора: от простых конвейеров до чиповых мультипроцессоров . Нью-Йорк: Cambridge University Press . С. 10. ISBN 978-0-521-76992-1.
4. Бензи, Джон; Дамодаран, М. (2007). «Параллельное трехмерное прямое моделирование Монте-Карло для моделирования микропотоков». Параллельная вычислительная гидродинамика 2007: Реализации и опыт в области крупномасштабных и сеточных вычислений . Параллельная вычислительная гидродинамика. Springer. стр. 95. Получено 21.03.2013 .
5. http://people.cs.vt.edu/~feng/presentations/030903-ParCo.pdf ^{[ пустой URL-адрес PDF ]}
6. Спекенмейер, Эвальд (1988). «Суперлинейное ускорение для параллельного обратного отслеживания». Суперкомпьютерные вычисления . Конспект лекций по информатике. Том 297. С. 985–993. doi :10.1007/3-540-18991-2_58. ISBN 978-3-540-18991-6.
7. "Gurobi против CPLEX benchmarks". cmu.edu . 29 января 2009 г. Получено 23 апреля 2018 г.