Новые теории лишь уточняют и интерпретируют закон Амдала
Новые теории лишь уточняют и интерпретируют закон Амдала. Источник: IBM

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

На презентации, озаглавленной «Нарушая закон», которая была проведена на прошедшей в июне в Лейпциге международной конференции International Supercomputing Conference, ученый объяснил, каким образом ловушку закона Амдала в конкретных ситуациях можно обойти, опираясь на результаты проведенных под его руководством экспериментов в области параллельных вычислений.

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

«Сколько бы процессоров вы ни выделили на параллельную обработку, если какую-то часть задачи можно выполнить только последовательно, она будет ограничивать дальнейшее ускорение», — поясняет Натан Бруквуд, главный аналитик Insight 64.

Закон Амдала многократно пытались «уточнять». К примеру, Джон Густафсон (сегодня он работает в AMD главным архитектором графических продуктов) внес поправку, касающуюся распараллеливания задач, размер которых может увеличиться. Согласно выведенному им следствию, названному законом Густафсона, при увеличении числа процессоров задачи большего размера можно выполнять за прежнее время.

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

Взяться за работу, представленную в Лейпциге, Липперта, по его словам, побудила история оптимизации суперкомпьютера Blue Gene/L, который в 2004 году стал самым быстрым в мире. Системы данной архитектуры отличаются высокой масштабируемостью и энергоэффективностью, но применяются для задач, не адаптированных для параллельной обработки.

Презентация Липперта была подготовлена по результатам экспериментов, проведенных в рамках проекта DEEP, который исследует модели вычислений с высокой степенью параллелизма, позволяющие ускорять обработку на суперкомпьютерах. Помимо исследования инструментов программирования в рамках проекта JUROPA (Juelich Research on Petaflop Architectures), конструируются высокопроизводительные системы.

«Моя команда построила систему JUROPA совместно со специалистами Bull, Partec и Intel, — сообщил Липперт. — Эта машина оптимальна для очень сложных, труднораспараллеливаемых задач. Мы хотим выяснить, можно ли одновременно выполнять трудно- и легкораспараллеливаемый код. В JUROPA разный код в зависимости от степени его параллелизма исполняется на компонентах системы с различной архитектурой».

Такая возможность есть, например, в языке программирования OmpSS, разработанном в Барселонском суперкомпьютерном центре, отметил Липперт.

Как утверждает Липперт, его цель не в том, чтобы оспорить закон Амдала: «Напротив, на мой взгляд, этот закон воспринимается недостаточно глубоко. Ведь это очевидно, что необходимо адаптировать различные элементы оборудования для соответствующих уровней параллелизма. Только такой подход способен обеспечить одновременно максимальную энергоэффективность и высокое быстродействие».

Закон Амдала не может быть «нарушен» в математическом смысле — он действует всегда, напоминает Пол Лу, профессор компьютерных наук Университета Альберты.

Однако, как и в случае с любой математической теоремой, если условия не выполняются, закон не действует. «Но это не значит, что он 'нарушен', это лишь говорит о неприменимости закона в конкретной ситуации, — отметил Лу и предупредил, что для задач с постоянным размером закон Амдала — это отрезвляющее напоминание о реальности».

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

«Закон Амдала действует, даже если задержку при обмене данными, доступе к памяти и другие тормозящие факторы свести к нулю. Если у вашей программы есть последовательная часть, ускорение, обеспечиваемое параллельной обработкой, все равно будет ограниченным, — поясняет ученый. — Это ограничение присутствует независимо от того, насколько совершенное у вас оборудование. Закон Густафсона, в свою очередь, утверждает, что ограниченность ускорения можно преодолеть за счет параллелизма, если допустить возможность увеличения размера задачи».

Сянь Хэ сформулировал собственное следствие, в котором дополнительно учитывается ограничение по памяти.

«Учитывая давнюю проблему 'барьера памяти' (memory wall, отставание пропускной способности шины памяти от быстродействия процессоров. — Прим. ред. ) и более новую проблему Больших Данных, увеличение размера задачи ограничивается задержкой доступа к памяти, — объясняет Сянь Хэ. — И данное ограничение тоже надо учитывать: необходимо пересмотреть модели программирования и архитектуру оборудования таким образом, чтобы уменьшить время доступа к данным и получить возможность более свободного масштабирования задач».

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

«Для любых законов и теорем нужно постоянно анализировать их основные условия, как это сделал Густафсон, — уверен Лу. — Первоначальный закон по-прежнему действует, но следствия, порождаемые им, могут быть весьма полезными».

Поделитесь материалом с коллегами и друзьями