Конференція Високопродуктивні обчислення, Київ, 13-15 жовтня 2014

Закону Амдала кинуто виклик

Дослідники пропонують змішану архітектуру, одна частина якої ефективно виконує розпаралелені фрагменти програм, а інша покликана прискорювати нерозпаралелювані ділянки.

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

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

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

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

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

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

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

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

«Моя команда побудувала систему JUROPA спільно з фахівцями Bull, Partec та Intel, — повідомив Ліпперт. — Ця машина оптимальна для дуже складних, важкорозпаралелюваних задач. Ми хочемо з'ясувати, чи можна одночасно виконувати важко- та легкорозпаралелювальний код. У JUROPA різний код залежно від ступеня його паралелізму виконується на компонентах системи з різною архітектурою».

Швидкодія суперкомп'ютерів зростає не тільки завдяки апаратним удосконаленням, а й новим моделям програмування. Код можна було б секціонувати залежно від рівнів паралелізму. Така можливість є, наприклад, у мові програмування OmpSS, розробленій в Барселонському суперкомп'ютерному центрі, зазначив Ліпперт.

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

Закон Амдала не може бути «порушений» у математичному сенсі — він діє завжди, нагадує Пол Лу, професор комп'ютерних наук Університету Альберти. Однак, як і у випадку з будь-якої математичної теоремою, якщо умови не виконуються, закон не діє. «Але це не означає, що він "порушений", це лише говорить про незастосовність закону в конкретній ситуації, — зазначив Лу та попередив, що для задач з постійним розміром закон Амдала — це протверезне нагадування про реальність».

Тим часом існують певні обмеження не тільки на швидкість паралельної обробки, а й на розмір самих задач, зазначає Сянь Хе Сунь, декан факультету комп'ютерних наук Іллінойського технологічного інституту.

«Закон Амдала діє, навіть якщо затримку при обміні даними, доступі до пам'яті та інші гальмуючі фактори звести до нуля. Якщо у вашої програми є послідовна частина, прискорення, що забезпечується паралельною обробкою, все одно буде обмеженим, — пояснює вчений. — Це обмеження присутнє незалежно від того, наскільки досконале у вас обладнання. Закон Густафсона, у свою чергу, стверджує, що обмеженість прискорення можна подолати за рахунок паралелізму, якщо допустити можливість збільшення розміру задачі».

Сянь Хе сформулював власний наслідок, в якому додатково враховується обмеження за пам'яттю.

«Враховуючи давню проблему "бар'єру пам'яті" (memory wall, відставання пропускної здатності шини пам'яті від швидкодії процесорів) та більш нову проблему Великих Даних, збільшення розміру задачі обмежується затримкою доступу до пам'яті, — пояснює Сянь Хе. — І це обмеження теж треба враховувати: необхідно переглянути моделі програмування та архітектуру обладнання таким чином, щоб зменшити час доступу до даних та отримати можливість більш вільного масштабування задач».

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

«Для будь-яких законів та теорем потрібно постійно аналізувати їх основні умови, як це зробив Густафсон, — упевнений Лу. — Початковий закон як і раніше діє, але наслідки, породжувані ним, можуть бути дуже корисними».

Агам Шах, Служба новин IDG, Нью-Йорк

Теги: ISC, високопродуктивні обчислення, закон Амдала, закон Густафсона, паралельне програмування, паралельні обчислення, суперкомп'ютер

Матеріали за темою:

Коментарі