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

Оглавление

• Закон Амдала: предыстория

  - Максимальное ускорение

  – Предостережения

• Закон Густавсона: предыстория

  - Масштабированное ускорение

  – Предостережения

• Сильное масштабирование против слабого масштабирования

  – Масштабируемые тесты

  — Сильное масштабирование

  — Слабое масштабирование

• Выводы

Закон Амдала: предыстория

Еще в 1967 году на весенней объединенной компьютерной конференции доктор Джин Амдал, занимавшийся серьезным компьютерным волшебством в IBM, собрался вместе с тремя другими технически подкованными людьми, включая умника Дэниела Слотника, гения, стоящего за внутренней работой Illiac-IV. Что они задумали, спросите вы? Ну, они обсуждали будущее компьютерной архитектуры. Во время этой конференции доктор Джин Амдал изложил свои мысли о препятствиях, с которыми сталкивается «многопроцессорный подход» при решении реальных проблем и всех их неприятных причуд. И знаете что, он высоко оценил «однопроцессорный подход» для решения проблем такого рода!

Работая в IBM, Амдал остро заметил, что значительная часть вычислительной работы занимает то, что он метко назвал « управлением данными ». Он твердо утверждал, что эта конкретная фракция оставалась удивительно стабильной в течение примерно десяти лет, последовательно поглощая 40% выполняемых инструкций в производственных циклах.

Что входит в сферу этой «домашней» работы? Он охватывает широкий спектр вычислительных задач, которые, хотя и важны, но не способствуют непосредственному выполнению основной вычислительной задачи. В зависимости от конкретного алгоритма и приложения это может включать ввод-вывод данных, предварительную обработку, управление памятью, обработку файлов и многое другое. Такая согласованность предполагает, что для многих приложений значительная часть времени обработки тратится на эти задачи. Определенный уровень управления данными почти неизбежен, и его сложно значительно минимизировать. Амдал отмечает, что эти издержки кажутся последовательными, то есть происходят шаг за шагом и не подходят для методов параллельной обработки.

«Довольно очевидный вывод, который можно сделать на этом этапе, заключается в том, что усилия, затраченные на достижение высоких скоростей параллельной обработки, напрасны, если они не сопровождаются достижениями в скорости последовательной обработки почти такой же величины». - Доктор Джин Амдал [1]

В своей оригинальной статье [1] Амдал добавляет, что сфера «домашних» задач — это лишь верхушка айсберга проблем, с которыми сталкивается «многопроцессорный» подход. Имея впечатляющий опыт работы физиком-теоретиком и докторской степенью, Амдал обладал глубоким пониманием реальных физических проблем, для решения которых были созданы компьютеры. Он подчеркивает множество сложностей, таких как неровные границы, неоднородные внутренние помещения, а также пространственные и временные зависимости от переменных состояний, которые представляют собой огромные препятствия для «многопроцессорной» парадигмы.

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

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

Закон Амдала: максимальное ускорение

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

Закон Амдала основан на предположении, что часть времени выполнения последовательной программы в идеале поддается распараллеливанию без каких-либо затрат на связь или синхронизацию. Дополнительная часть, представленная как s = 1 − f, является полностью последовательной.

Таким образом, если T — время выполнения последовательной программы, время выполнения на p ядрах T(p) определяется выражением:

Ускорение , представляющее собой отношение времени последовательного выполнения к времени параллельного выполнения, дает:

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

Предостережения

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

На следующем рисунке показано влияние распараллеливания на ускорение, определяемое законом Амдала. Понятно, что даже при значительной доле параллельности в 95% и большом наборе процессоров максимально достижимое ускорение ограничивается примерно 20-кратным пределом. Увеличение процента распараллеливания до 99% и использование бесконечного числа процессоров может привести к более впечатляющему 100-кратному ускорению, что является многообещающим.

Однако важно понимать, что наличие такого количества процессоров — редкость . Мы часто работаем с гораздо более скромным числом, например, 64 или даже меньше.

Когда мы применяем закон Амдала к программе, использующей 64 процессора (с f равным 95%), максимальное ускорение колеблется в районе 15,42x. Правда, эта цифра не очень многообещающая!

Это понимание несколько затемняется ограничением, используемым в этом выражении:

За этим ограничением скрывается тот факт, что показатели ускорения заметно ниже, если принять во внимание практическое, реальное количество процессоров.

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

По сути, предполагается, что распараллеливаемая часть остается неизменной независимо от количества используемых ядер. Это ограничение было тщательно рассмотрено и расширено Джоном Л. Густавсоном , который предложил модифицированную точку зрения, теперь известную как закон Густавсона . Однако, несмотря на эти общепризнанные проблемы и предостережения, важно признать, что закон Амдала имеет свои преимущества, предлагая ценную информацию о сложностях распараллеливания. Закон Амдала находит применение в виде сильных тестов масштабирования , эту тему мы рассмотрим позже.

Закон Густавсона: предыстория

Работая над массово-параллельными вычислительными системами в Национальных лабораториях Сандии, доктор Джон Л. Густафсон и его команда получили впечатляющие коэффициенты ускорения для трех различных приложений на 1024-процессорном гиперкубе. Доля серийного кода соответствовала 0,4–0,8%.

«…мы достигли коэффициентов ускорения на гиперкубе с 1024 процессорами, которые мы считаем беспрецедентными: 1021 для анализа напряжений балки с использованием сопряженных градиентов, 1020 для моделирования рассеянных поверхностных волн с использованием явных конечных разностей и 1016 для нестабильного потока жидкости с использованием поправки на поток транспорт." - Доктор Джон Л. Густафсон [2]

В последнем разделе мы ясно видели, что согласно закону Амдала максимальное ускорение, достижимое для большого количества процессоров, составляет 1/с. Итак, как же можно добиться такого поразительного ускорения в 1021 раз?

Густафсон [2] подчеркнул, что в математическом выражении есть тонкое предположение, подразумевающее, что переменная f не связана с p . Однако этот сценарий редко является реальностью, с которой мы сталкиваемся. В реальных сценариях мы обычно не берем задачу фиксированного размера и не запускаем ее на разном количестве процессоров, за исключением, возможно, контролируемой среды академических исследований. Вместо этого в практических приложениях размер проблемы имеет тенденцию увеличиваться вместе с количеством процессоров.

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

По мнению Густавсона, зачастую более реалистично предположить, что на практике время выполнения остается относительно постоянным, а не размер проблемы.

Густафсон заметил, что количество параллельных или векторных программ увеличивается пропорционально размеру задачи. Такие элементы, как векторный запуск, загрузка программы, узкие места последовательного порта и операции ввода-вывода, которые в совокупности вносят вклад в компонент времени выполнения программы, обычно остаются относительно постоянными и не демонстрируют значительного роста с увеличением размера проблемы.

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

В ходе углубленного изучения трех упомянутых приложений Густавсон и его коллеги обнаружили, что параллельный компонент имеет коэффициенты масштабирования примерно 1023,9969, 1023,9965 и 1023,9965.

Закон Густавсона: масштабируемое ускорение

Предположение Густафсона заключается в рассмотрении нормализованного времени выполнения на p ядрах, которое в сумме дает (1 − f) + f , что дает общее значение 1. Согласно этой логике, если (1 − f) + f означает время выполнения на p ядрах , то время работы на одном ядре можно выразить как (1 − f) + p*f . Следовательно, ускорение, которое Густавсон назвал « масштабным ускорением », можно рассчитать следующим образом:

Когда мы применяем закон Густавсона к программе, использующей 64 процессора (при f равном 95%), прогнозируемое ускорение составит 60,85x (по сравнению с 15,42x по закону Амдала). Сейчас поговорим😉

На следующих рисунках показаны различия между двумя законами.

Предостережения

Точки зрения Амдала и Густавсона предлагают разные взгляды на распараллеливание, каждый со своими собственными предположениями.

Закон Амдала предполагает, что объем работы, который можно распараллелить, постоянен и не зависит от количества процессоров, что делает его очень пессимистичным. Точка зрения Густавсона, которая предполагает, что объем работы, которую можно распараллелить, растет линейно с количеством ядер, несомненно, практична для многих сценариев. Однако иногда он может быть слишком оптимистичным.

Реальные приложения часто сталкиваются с ограничениями, которые могут ограничить линейную масштабируемость. Например, по мере увеличения количества ядер может происходить снижение отдачи из-за сложностей параллельной обработки, зависимостей данных и накладных расходов на связь. Более того, аппаратные ограничения практически ограничивают количество ядер, которые можно эффективно интегрировать в один чип. Закон Густавсона не всегда может учитывать эти сложные проблемы реального мира, поэтому необходимо учитывать оговорки, влияющие на его применимость.

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

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

Сильное масштабирование против слабого масштабирования

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

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

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

Масштабирование тестов

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

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

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

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

Сильное масштабирование

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

Сильное масштабирование закреплено в законе Амдала, при котором размер задачи остается фиксированным, а количество обрабатывающих элементов увеличивается. Этот метод часто оправдан для программ со значительной нагрузкой на процессор.

Конечная цель сильного масштабирования — найти оптимальную «золотую середину», которая позволит завершить вычисления в разумные сроки, минимизируя при этом потери циклов обработки из-за параллельных накладных расходов.

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

Наконец, я попробовал провести строгие тесты масштабирования для одного из моих кодов. Fluidchen-EM — это вычислительная программа для решения задач гидродинамики, способная решать многие задачи гидродинамики. Следующие результаты соответствуют моделированию полости с приводом от крышки . Визуализируется скорость в конечной временной метке (после сходимости) и рассчитывается время выполнения. Fluidchen-EM использует MPI для распределения вычислительной области между процессорами iproc*jproc .

Примечание . Результаты были просчитаны на моем персональном компьютере, и все ядра соответствуют только одному процессору. Результаты могут отличаться, если моделирование выполняется на более крупной и лучшей машине!

Расчетная область разделена на совокупность точек сетки imax*jmax .

iproc: количество процессоров в направлении x.

jproc: количество процессоров в направлении y

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

Слабое масштабирование

При слабом масштабировании количество процессоров и размер задачи увеличиваются, сохраняя постоянную рабочую нагрузку на процессор. Слабое масштабирование соответствует закону Густавсона, согласно которому масштабируемое ускорение рассчитывается на основе рабочей нагрузки масштабированной задачи, в отличие от закона Амдала, который фокусируется на фиксированном размере задачи.

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

Слабое масштабирование оправдывает приложения со значительными требованиями к памяти или ресурсам (с привязкой к памяти), которые требуют большего объема памяти, чем может предоставить один узел. Такие приложения часто демонстрируют эффективное масштабирование, поскольку их стратегии доступа к памяти отдают приоритет соседним узлам, что делает их хорошо подходящими для большего количества ядер.

В случае слабого масштабирования линейная масштабируемость достигается, когда время выполнения остается постоянным, поскольку рабочая нагрузка увеличивается прямо пропорционально количеству процессоров.

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

Наконец, я провел тесты слабого масштабирования с помощью Fluidchen-EM . Следующие результаты соответствуют моделированию конвекции Рэлея – Бенара . Опять же, визуализируется скорость в конечной временной метке (после сходимости) и рассчитывается время выполнения. Fluidchen-EM использует MPI для распределения вычислительной области между процессорами iproc*jproc .

Примечание. Результаты были просчитаны на моем персональном компьютере, и все ядра соответствуют только одному процессору. Результаты могут отличаться, если моделирование выполняется на более крупной и лучшей машине!

Расчетная область разделена на совокупность точек сетки imax*jmax .

iproc: количество процессоров в направлении x.

jproc: количество процессоров в направлении y

imax: количество точек сетки по длине канала.

jmax: количество точек сетки по высоте канала.

xlength: длина канала

ylength: высота канала

Как показано на рисунке выше, время выполнения увеличивается с ростом размера задачи и количества процессоров. Такое поведение можно объяснить несколькими факторами. Поскольку все ядра расположены на одном процессоре, по мере увеличения размера проблемы и задействования большего числа процессоров часть времени обработки уходит на настройку связи MPI (интерфейс передачи сообщений). Кроме того, больший размер проблемы требует увеличения обмена данными между ядрами, увеличивая задержку связи из-за ограниченной пропускной способности сети связи.

Таким образом, результаты этих тестов дают решающее представление о распараллеливании проблемы.

Заключение

Выбор между законом Густавсона и законом Амдала при распараллеливании алгоритмов зависит от адаптируемости вычислительной нагрузки. Закон Густавсона применим, когда алгоритм может динамически регулировать объем вычислений в соответствии с доступным распараллеливанием. Напротив, закон Амдала более подходит, когда вычислительная нагрузка фиксирована и не может быть существенно изменена путем распараллеливания. В реальных сценариях адаптация алгоритма для распараллеливания часто предполагает некоторую степень модификации вычислений, и оба закона служат ценными ориентирами, предлагая верхние и нижние границы прогнозируемого ускорения. Выбор между ними зависит от объема вычислительных изменений, вносимых во время распараллеливания, что позволяет всесторонне оценить потенциальный выигрыш в ускорении.

Рекомендуемое чтение

[1] Действительность однопроцессорного подхода для достижения крупномасштабных вычислительных возможностей, перепечатано из материалов конференции AFIPS, Vol. 30 (Атлантик-Сити, Нью-Джерси, 18–20 апреля), AFIPS Press, Рестон, Вирджиния, 1967, стр. 483–485, когда доктор Амдал работал в International Business Machines Corporation, Саннивейл, Калифорния | Журналы и журналы IEEE | IEEE исследование

[2] Переоценка закона Амдала | Коммуникации ACM

[3] Дурганшу/Флюидхен-ЭМ

[4] Закон Амдала для предсказания будущего многоядерных процессоров считается вредным (tu-berlin.de)

[5] Масштабирование — HPC Wiki (hpc-wiki.info)

[6] Амдал против Густавсона от r1parks — Infogram

Рекомендованное фото Марка Сендры Марторелла на Unsplash