Багатоядерні процесори і програмування
- У гонитві за супервичіслітелем
- фізичний паралелізм
- Програмування фізично паралельних систем
- Операційні системи
- Переваги «дрібнозернистого» логічного паралелізму
- Багатопотоковий логічний паралелізм
- Логічний і фізичний паралелізм
- Як подолати кризу?
- Час переосмислити концепції
Десятиліттями програмування для персональних комп'ютерів існувало в оранжерейних умовах: оптимізація програм перебувала якщо не на останньому, то далеко не на першому місці. Багато уваги приділялося процесу групової розробки, об'єктним паттернам програмування, скорочення часу створення програм. Вважалося, що швидкість роботи програми збільшується незалежно від розробника, просто в силу постійного зростання потужності процесора, прискорення обміну даними з пам'яттю і периферією.
Дійсно, приблизно з 1970-го по 1985 рік продуктивність процесорів росла переважно за рахунок вдосконалення елементної бази та збільшення тактової частоти. Потім, аж до 2000 року, основну роль стали грати архітектурні удосконалення - конвейеризация, спеціалізація, суперскалярність, спекулятивні обчислення, кешування, збільшення розрядності. Всі ці фактори не впливали на процес проектування більшості програм, які продовжували залишатися прозорими, лінійними і переважно об'єктно-орієнтованими. Навіть без перекомпіляції вони виконувалися на нових платформах значно швидше, і програмісти вважали, що так буде тривати вічно.
У 2001 році був вичерпаний ресурс підвищення тактової частоти процесора. Для рядового користувача це пройшло непоміченим, оскільки організація масового виробництва процесорів з тактовою частотою більше 3 ГГц розтягнулася на кілька років. До 2005 року був освоєний серійний випуск 3-гігагерцевий процесор, і виявилися в основному вичерпаними ресурси архітектурного вдосконалення окремо взятого процесора. У квітні 2005 року Intel і AMD одночасно приступили до продажу двоядерних процесорів для персональних комп'ютерів - по суті, двох процесорів на одній підкладці. Золотий вік ПК закінчився. Тепер турбота про підвищення швидкості виконання програм повністю лягає на плечі кодувальників.
Програмування на декількох процесорах - проблема не нова, але для її рішення від розробника потрібні спеціальна підготовка, особливий образ мислення і висока кваліфікація. І до такого повороту подій комп'ютерний «мейнстрім» явно не готовий.
У гонитві за супервичіслітелем
Програмування створювалося і розвивалося як елітарна наукова дисципліна, яка вивчала способи розробки, перевірки і поліпшення програм для ЕОМ. Під програмою розумілася впорядкована послідовність дій машини, яка реалізує алгоритм вирішення деякої задачі. А під алгоритмом малося на увазі всяке точне розпорядження, яке задає обчислювальний процес, спрямований на отримання повністю визначається результату за вихідними даними. Йшлося виключно про обчислювальних алгоритмах, і, дійсно, переважна кількість завдань на зорі програмування були саме такими: розрахувати траєкторію польоту ракети, на основі метеорологічних даних видати прогноз погоди, знайти екстремум функції в економічній задачі, оцінити необхідну потужність електромагніта для циклотрона або обчислити інтеграл з точністю до десятого знака.
Одне надзвичайно важливе правило, що діяло в ті часи, здавалося настільки очевидним, що про нього навіть не згадувалося. Воно полягало в тому, що отримати рішення потрібно було якомога швидше. Мало того, що необхідність очікування моменту, коли машина «виплюне» перфокарти з відповіддю, нервувала програмістів. Результатів обчислень з нетерпінням чекали і конкретні споживачі - вчені, інженери, економісти. Швидкість обчислень визначала темпи розвитку народного господарства. При прогнозуванні погоди результат, отриманий із запізненням, взагалі не потрібен. Швидкість дешифрування важливої інформації, отриманої при радіоперехоплення, є питанням забезпечення національної безпеки, а можливість обрахувати ядерний вибух - важливим військово-політичним козирем. Такі міркування послужили сигналом до початку гонки на міждержавному рівні, метою якої було побудувати максимально продуктивну ЕОМ - суперкомп'ютер.
Продуктивність суперкомп'ютерів збільшується за рахунок вдосконалення елементної бази та архітектурних рішень. Елементна база визначає швидкодію транзисторів і розсіюється потужність, а основні архітектурні зміни спрямовані на розпаралелювання обробки даних, тобто одночасне виконання декількох дій [ 1 ].
фізичний паралелізм
Паралельна обробка має два різновиди: конвеєрні і власне паралельність. В тому і в іншому випадках передбачається архітектурне вичленення з системи окремих фізичних компонентів.
Ідея конвеєрної полягає в розбитті операції на послідовні етапи тривалістю в такт з подальшою реалізацією кожного з них окремим фізичним блоком. Якщо організувати роботу таких блоків у вигляді конвеєра (кожен блок, виконавши роботу, передає результат обчислень наступного блоку і одночасно приймає нову порцію даних), то вийде очевидний виграш.
Ідея «чесного» розпаралелювання ще простіше. Її можна пояснити за допомогою простої аналогії: якщо одному робітникові потрібно 10 годині на виготовлення 10 деталей, то 10 робочим для цього потрібен всього годину. На жаль, незважаючи на міць і простоту ідей фізичного паралелізму, установка 10 обчислювальних модулів замість одного не означає десятикратного збільшення обчислювальної потужності системи. Якщо в задачі не можна виділити ділянки, що допускають паралельну обробку, або масив однотипних операндів для конвейеризации, то скоротити час її виконання не вдасться. Це описується законом Амдала [1], який визначає максимально досяжну продуктивність.
Крім конвейеризации і фізичного розпаралелювання використовуються наступні методи:
- спеціалізація (застосування всередині процесорів блоків, оптимізованих під певний вид обчислень, наприклад математичних співпроцесорів);
- кешування;
- спекулятивні обчислення.
Серійно виготовляються комп'ютери дозволяють створити дешеву альтернативу суперкомп'ютерів, наприклад кластерну систему. При цьому основне завдання зводиться до програмування створеної системи.
Програмування фізично паралельних систем
Простота ідеї програмування фізично паралельних систем виливається на практиці в цілий ряд складних методик і умов.
- Алгоритм повинен допускати розпаралелювання.
- При виокремлення паралельних ділянок, як правило, доводиться надавати алгоритму спеціальну форму. Наприклад, якщо необхідно визначити суму масиву, при розпаралелювання на першому кроці одночасно підсумовуються сусідні парні і непарні елементи масиву, а на другому попарно підсумовуються результати, отримані на першому кроці, і т.д. Компактно записати паралельний варіант на мові Сі неможливо. У загальному випадку приведення алгоритму до форми, що дозволяє скоротити час обчислень, означає відхід від форми, що забезпечує найбільш наочне уявлення.
- У багатопроцесорної системі розбиття на занадто великі частини не дозволяє рівномірно завантажити процесори і домогтися мінімального часу обчислень, а зайве дрібна «нарізка» означає зростання непродуктивних витрат на зв'язок і синхронізацію.
- Фізичній паралелізму властива залежність глобальної структури алгоритму від топології обчислювальної платформи. Процес створення максимально ефективного алгоритму практично не автоматизується і пов'язаний з великими затратами на пошук специфічної структури алгоритму, оптимальної для конкретної топології цільової системи. Знайдена структура забезпечить мінімальний час отримання результату, але, швидше за все, буде неефективна для іншої конфігурації. Більш суворе наслідок залежності структури алгоритму від обчислювальної платформи - тотальна непереносимість не лише виконуваних кодів, а й самого вихідного тексту.
Дана залежність легко демонструється на класичному прикладі сортування. При O (N) порівняннях, необхідних для сортування масиву з N елементів, вартість паралельних алгоритмів сортувань дорівнює O (N2). У той же час швидкі послідовні алгоритми сортувань забезпечують вартість O (N log N). Таким чином, щоб впорядкувати масив з 1 тис. Чисел на десяти обчислювачах, треба розбити його на десять частин, впорядкувати їх за допомогою ефективного послідовного алгоритму, а потім паралельно злити ці частини в загальний список (вартість паралельного злиття - O (N)) [ 2].
Обнадіюють роботи, націлені на створення мовних засобів і методик забезпечення переносяться паралельних програм. Так, основна мета проекту «Піфагор» [3] - забезпечити розумний компроміс між швидкодією алгоритму і прийнятним рівнем його сопровождаемости (еволюційна розширюваність, переносимість, платформна незалежність). Однак цей підхід має свої особливості: програмування передбачає використання функціонального мови, що, як мінімум, вкрай незвично для більшості практикуючих програмістів.
Розмірковуючи про специфіку фізичного паралелізму, слід згадати питання надійності. Програміст, що пише фізично паралельну програму, обов'язково повинен мати уявлення про наступні речі:
- взаємні блокування паралельних ділянок;
- несинхронний доступ, або гонки;
- можливість зависання паралельних ділянок;
- небезпека використання сторонніх процедур і бібліотек;
- набір спеціалізованих засобів налагодження фізично паралельних програм;
- нелокальний характер помилок;
- динамічний характер помилок і, як наслідок, вплив засобів налагодження програм на коректність виконання останніх.
Операційні системи
Якщо ми спочатку распараллеліть деяку задачу, а потім виконаємо її в рамках однопроцессорной архітектури, то з точки зору мети фізичного паралелізму це здасться повним абсурдом - час розрахунку збільшиться. А ось з точки зору зручності програмування в такому розпаралелювання виявляється глибокий сенс.
Формула «розділяй і володарюй» має для програмістів силу закону. Складність сучасних програмних систем може бути подолана тільки шляхом розбиття проблеми на безліч відокремлених частин. І навпаки, програмні комплекси довільної складності можуть будуватися тільки на основі незалежних або, в крайньому випадку, слабо залежних один від одного компонентів. А це також має на увазі максимальну відособленість частин для мінімізації перехресних зв'язків, що необхідно для ефективної організації групової розробки. Якщо паралельні (а вірніше, незалежні) сутності виділяються на основі міркувань зручності програмування (в першу чергу, для зниження складності опису системи), то говорять про логічне паралелізм.
Логічний паралелізм на рівні операційних систем є багатозадачним; при цьому є виділена завдання (планувальник), яка займається перемиканням процесора з одного завдання на інше. Алгоритми перемикань можуть бути як примітивними, так і досить складними. Найпростіший - алгоритм розподілу за часом. Планувальник працює з чергою завдань і активізується по перериваннях від таймера з деяким заданим періодом. Після активізації він зберігає контекст поточного завдання, ставить її в кінець черги, відновлює контекст наступного завдання з черги і запускає її на виконання.
Оскільки завдання різні за виконуваним функціям і ресурсоємності, то виникає проблема розподілу обчислювальної потужності процесора пропорційно завданням. В цьому випадку базовий алгоритм може ускладнюватися, наприклад за рахунок механізму пріоритетів: завданням присвоюються пріоритети, і при зміні завдань управління передається найбільш пріоритетною. В системі може бути передбачено динамічна зміна пріоритетів. Планувальник допускається викликати по перериваннях не тільки від таймера, а й від інших джерел, а також на вимогу активної задачі, після виконання необхідних високопріоритетних операцій. Однак отримується гнучкість супроводжується підвищенням накладних витрат на планування, сильно залежать від кількості обслуговуваних завдань.
Переваги «дрібнозернистого» логічного паралелізму
Завдання з унікальним набором даних і функцій досить тяжеловесна для виклику і обслуговування. Багатозадачний логічний паралелізм передбачає невелику кількість завдань (зазвичай в межах одного десятка). Тим часом існують області, в яких необхідний «дрібнозернистий» логічний паралелізм - розбиття завдання на безліч невеликих незалежно виконуваних частин. У серверах баз даних, на новинних порталах, в мобільних сервісах, які обслуговують розподілені системи, призначені для декількох сотень тисяч абонентів, потрібно механізм незалежного обслуговування тисяч одночасно надходять запитів. У таких системах треба не тільки не пропустити надійшов запит, але і обслужити його, можливо, організувавши інтерактивний діалог, контроль над достовірністю і перезапроса інформації в разі помилки.
«Дрібнозернистий» логічний паралелізм ефективний в задачах управління складним промисловим обладнанням. Необхідність відображення паралелізму процесів, здійснюваних на об'єкті управління, вимагає створення щонайменше сотні паралельно виконуваних процесів. Наприклад, еквівалентну монолітне рішення у вигляді одного процесу, призначене для управління вирощуванням монокристалічного кремнію [4], призводить до розгляду 1030 різних ситуацій. Стиснення інформації досягається при логічному паралелізм за рахунок спрощеного опису комбінацій незалежних випадків: опис алгоритму як набору незалежних частин - це опис суми ситуацій, а монолітне опис - це опис твору ситуацій. Неймовірне число ситуацій (1030) можна отримати лише з сотні паралельно виконуваних компонентів з двома станами, в той час як незалежна опис алгоритму має на увазі розгляд всього 200 унікальних випадків.
Багатопотоковий логічний паралелізм
Переваги «дрібнозернистого» логічного паралелізму змушують шукати шляхи зниження накладних витрат, властивих багатозадачності. Відомі рішення для операційних систем - легковагі процеси (light-weight process). Так, в Sun OS 5.x є полегшений варіант завдань - потоки (thread), стан яких повністю характеризується значеннями покажчиків на код і стек. Перемикання процесора на потік мінімізовано аж до операцій збереження / відновлення цих покажчиків. Планувальник як і раніше присутня і активізується по перериваннях від таймера.
Відзначимо, що перемикання потоків за часом не завжди зручно і призводить до непродуктивних простоїв процесора. Якщо в потоці для продовження обчислень потрібно зовнішнє подія (відгук обладнання, реакція абонента на запит, підтвердження успішної передачі повідомлення), то потік «чесно» витрачає відведений йому час на очікування:
Step1 (); /* дія */
while (! EventOnStep1 ()); / * Очікування реакції на дію * /
Step2 (); / * Наступна дія * /
Якщо для реакції на дію потрібно чимало часу (наприклад, подія - це реакція користувача на запит системи), то більш прийнятна стратегія - передача управління після опитування. Цей підхід використовується при організації багатопоточності методом циклічного опитування (round-robin), який іноді позначають терміном «корпоративна багатозадачність». При циклічному опитуванні потоки можуть бути представлені просто функціями, які опитуються в нескінченному циклі:
Main () {
for (;;) {
thread_1 ();
thread_2 ();
...
thread_N ();
}
}
Необхідність очікування зовнішньої реакції природним чином задає розбиття потоків на частини, кожна з яких є найпростішою функцією. Якщо присвоїти кожній частині якесь число, то реалізація потоків природним чином буде виражатися в термінах мови Сі. З історичних причин найпростіші функції називають «станами».
thread_i () {
switch (State_i) {
...
case STATE_1:
Step1 (); /* дія */
if (EventOnStep1 ()) State_i = STATE_2; / * Зміна стану * /
break;
case STATE_2:
Step2 (); / * Наступна дія * /
...
}
}
Таким чином, при багатопоточності можна мінімізуваті або даже Повністю віключіті накладні витрати, властіві багатозадачності. А простота організації робить багатопоточність привабливою для забезпечення «дрібнозернистого» логічного паралелізму з гранулярністю на рівні декількох інструкцій. Одержуваний виграш компенсує ризик можливих помилок (які можуть виникнути, наприклад, через роботу із загальною областю даних). Мало того, ці ризики можна повністю виключити за рахунок застосування відповідних механізмів.
Наприклад, в мові Рефлекс (діалект мови Сі, призначений для опису алгоритмів управління) безпеку і неможливість руйнування програми мовними засобами забезпечені на концептуальному рівні. У цій мові синтаксис і семантика Сі розширені за рахунок поняття процесу - паралельно виконуваного ділянки коду, що допускає запуск, зупинку і перевірку свого стану [4]. Автоматизовані рутинні операції, пов'язані з організацією паралелізму, і користувач може повністю зосередитися на власне алгоритмі. Можливість звернення за довільним адресою виключена. Змінні мови типізовані. При такому підході конфлікти пам'яті просто неможливі.
Логічний і фізичний паралелізм
Основні відмінності фізичного і логічного паралелізму полягають в їх цілях (див. Таблицю). Фізичний паралелізм призначений для отримання результату за вхідними даними за найкоротший час. Основними цілями логічного паралелізму є скорочення часу розробки, спрощення створення, експлуатації та, в загальному випадку, супроводу програмних систем. В тому і в іншому випадках передбачається виділення ділянок алгоритму, що допускають незалежне або слабо залежне виконання.
Оскільки час отримання результату складається з часу розробки алгоритму і часу розрахунку, то для задач фізичного паралелізму також вкрай бажано забезпечення значній швидкості розробки і високого рівня сопровождаемости програм. Однак ці завдання відходять на другий план і навіть приносяться в жертву основної мети - скорочення часу отримання кінцевого результату. А в задачах логічного паралелізму часто виникає бажання зменшити час виконання алгоритму, наприклад для збільшення функціональності системи. Інша справа - те, що до теперішнього часу загальноприйнятою практикою було очікування нових рішень від виробників обчислювальних платформ.
Особливість фізичного паралелізму, яка обумовить складність програмування, полягає в тому, що структура максимально ефективного (з точки зору часу обчислення) алгоритму залежить від топології обчислювальної системи.
Як подолати кризу?
На жаль, «безкоштовні обіди» на основі закону Мура закінчилися: кошти підвищення обчислювальної потужності окремого процесора практично вичерпані, і залишилися лише вельми неоднозначні невеликі резерви, які забезпечуються збільшенням Кешована пам'яті [5].
Доводиться констатувати, що архітектурні удосконалення привели відносно однорідну ІТ-індустрію до межі поділу на більш дрібні області. Це викликано тим, що фізичне розпаралелювання не працює в довільному класі задач: збільшення розрядності процесора, використання гіперпотоковості (hyper-threading) і багатоядерності можуть дати ефект, протилежний очікуваному, тобто після розпаралелювання час виконання програми навіть збільшиться.
Не всяка завдання допускає фізичне розпаралелювання [ 5 ]. Цілі класи завдань (наприклад, швидке Фур'є-перетворення, обробка запиту до бази даних, швидкі алгоритми сортувань і т.п.) не отримують помітного виграшу від розпаралелювання або не распараллелівать в принципі. У розробників з'являється альтернатива - замість зміни структури програми приділяти більше уваги локальної оптимізації коду. До певної межі це виявиться робочим варіантом, причому буде підтримано зростанням інтересу до засобів розробки, орієнтованим на високошвидкісне виконання в рамках однопроцессорной архітектури.
Виникає проблема сумісності старих, написаних для однопроцесорних архітектур, бібліотек. Якщо бібліотеки фізично не підтримують паралельне виконання, то розпаралелювання алгоритму може привести до помилки. Не випадково Intel розширює програмістську складову своєї діяльності, зокрема - для створення безпечних бібліотек, які припускають і гнучке налаштування на конкретну обчислювальну платформу. Мабуть, в найближчому майбутньому йтиметься про динамічно реконфігурованих бібліотеках, кінцевий вигляд яких буде визначатися при завантаженні завдання і виявленні поточної топології системи.
Не цілком зрозуміле питання об'єктно-орієнтованого програмування: немає досліджень по сумісності об'єктно-орієнтованого програмування з многоядерной архітектурою процесора. Поточний стандарт ISO на Сі ++ тактовно обходить стороною фізичний паралелізм, а між тим, наприклад, Intel пише спеціалізовані бібліотеки на «чистому» Сі.
Цілком можливо, що певний корисне використання многоядерной архітектури без реінжинірингу старих програм операційні системи можуть забезпечити на рівні завдань. Однак в силу невеликого числа завдань такий підхід має цілком природні обмеження.
Необхідно відзначити видимі переваги мікроядерних архітектур ОС, які (на відміну від монолітних, оптимізованих для однопроцесорних систем) допускають фізичне розпаралелювання.
З одного боку, на ринку з'являлося досить привабливе, але все вимогливіше до швидкодії персонального комп'ютера програмне забезпечення. З іншого - виробники ПК створювали все потужніші оновлені рішення. Виникала при цьому межверсіонная несумісність приводила до того, що користувачі викидали свої старі ПК. Іншими словами, відбувалося постійне (приблизно раз в два-три роки) оновлення парку персональних комп'ютерів, системного і прикладного програмного забезпечення. Тепер ця ідилія закінчилася, і пошук нових областей застосування для пропонованих архітектур персональних комп'ютерів стає вкрай актуальним.
Головною тенденцією програмування вже найближчим часом стане створення нових мов і технік, які суміщають зручність розробки і фізичний паралелізм виконання. Цього вдасться досягти тільки за рахунок вирішення питань, пов'язаних з фізичним паралелізмом. На жаль, існуючі рішення типу pthread і OpenMP можна розцінювати лише як паліатив. Ручне управління фізичним паралелізмом (explicit parallelism) відкидає програмування назад, в епоху машинних кодів і ассемблеров, реанімуючи прихильність структури програми до фізичної архітектурі обчислювальної платформи.
Автоматичне розпаралелювання (implicit parallelism) для багатоядерних архітектур в більшості випадків забезпечує прискорення лише з певною ймовірністю. Проміжним рішенням можуть бути вже згадувані Реконфігуровані бібліотеки (Integrated Performance Primitives, MathKernelLibrary).
Найбільш перспективні мови і техніки, яким природно притаманний логічний паралелізм, незалежність або слабка залежність компонентів один від одного. В першу чергу, мова йде про многозадачном логічному паралелізм. Існуючі напрацювання - це, по суті, «напівфабрикати» для многоядерной платформи. Явний недолік багатозадачності полягає в тому, що практично нереально придумати переконливий випадок завантаження персонального комп'ютера достатньою кількістю (десятком і більше) дійсно ресурсномістких завдань.
Інша можливість - спробувати адаптувати до багатоядерним архитектурам існуючі техніки та мови багатопотокової організації програм. Досвід застосування мови Рефлекс [4] в багатопроцесорних системах показує, що таке цілком допустимо. Правда, що з'являються при цьому суті означають досить радикальна зміна програм на рівні машинних команд. Наприклад, відбувається очевидний відмова від використання стека при організації структури програми. При створенні програм змінюється і сприйняття процесу програмування: класичні функції доповнені процесами, які при їх запуску породжують окремий незалежний потік команд і даних.
Час переосмислити концепції
На сьогоднішній день досягнуто технологічна межа збільшення обчислювальної потужності окремо взятого процесора. Це підриває статус-кво у відносинах між виробниками апаратури, системного і прикладного програмного забезпечення та кінцевими користувачами, а відповідно, загрожує динаміці ІТ-індустрії в цілому.
Провідні виробники мікроелектронних компонентів, намагаючись зберегти тенденцію зростання продуктивності, пропонують радикальні зміни в базовій архітектурі персональних комп'ютерів - багатоядерні процесори. Ці архітектурні зміни передбачають корекцію підходів до створення програм, а саме - активне використання фізичного паралелізму. Однак він, з одного боку, непридатний до великого класу існуючих послідовних алгоритмів, а з іншого, означає повернення до низкорівневому програмування з усіма наслідками, що випливають звідси наслідками (від підвищення кваліфікаційних вимог до розробників до збільшення витрат на створення і реінжиніринг програм).
Все це дозволяє охарактеризувати нинішню ситуацію як кризову. Прийшов час переосмислити базові концепції організації та поширені техніки розробки системного програмного забезпечення з метою створення високорівневих методик і мов програмування, що не припускають окремого розгляду питань фізичного паралелізму.
література
- Воєводін В.В. Паралельна обробка даних. Курс лекцій. - Лабораторія паралельних інформаційних технологій НИВЦ МГУ, 2000..
- Макконнелл Дж. Основи сучасних алгоритмів. - М .: Техносфера, 2004.
- Легалів А., Кузьмін Д., Казаков Ф., Пріваліхін Д. На шляху до стерпним паралельним програмами // Відкриті системи, 2003 № 5.
- Зюбин В.Є., Пєтухов А.Д. Розподіл обчислювальних ресурсів в середовищах c багатопотокової реалізацією гіпер-автомата // Праці III Міжнародної конференції «Ідентифікація систем та завдання управління» SICPRO? 04. - Москва, 2004.
- Sutter H. The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software. Dr. Dobb? S Journal, March 2005.
Володимир Зюбин ( [email protected] ) - співробітник Інституту автоматики і електрометрії СО РАН (Новосибірськ).
Як подолати кризу?Розподіл обчислювальних ресурсів в середовищах c багатопотокової реалізацією гіпер-автомата // Праці III Міжнародної конференції «Ідентифікація систем та завдання управління» SICPRO?
Dobb?