Мультитредові мікропроцесори

У суперскалярному процесорі в принципі можлива генерація досить широкого вікна виконання з великою глибиною передбачення розгалужень. Можна генерувати дуже гнучкий план виконання команд. Однак суперскалярний процесор не має уявлення про ГУЗ програми.

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

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

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

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

1.3 Виявлення тредів

Треди можуть виявлятися як на основі потоків управління (control driven), так і на основі потоків даних (data driven) програм. Треди бувають умовно чи безумовно виконуваними.

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

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

При виявленні тредів на основі потоків управління аналізуються керуючі структури послідовної програми, такі як цикли, ітерації звернення до функцій і підпрограм. Робиться спроба виявлення сегментів коду з мінімальними взаємозалежностями.

На концептуальному рівні треди, які виявляються на основі потоків даних програми, складаються з однієї команди. Тред породжується, коли у команди з'являється один операнд. Можливим розширенням концепції цих тредів служить виконання не однієї команди по готовності всіх операндів, а послідовності команд, очолюваної цією командою. Передачі даних між тредами вказуються явно.

Автоматичне перетворення програм на імперативних мовах в програми потоків даних знаходиться в стадії дослідження. Програми потоків даних пишуться на функціональних мовами або спеціальних мовах потоків даних.

1.4 Специфіка мультитредових моделей розпаралелювання

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

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

Програма, призначена для виконання на мультитредовому процесорі, повинна складатися із сукупності тредів, кожен з яких представляє собою одиницю обробки даних. Важливою рисою мультитредових процесорів служить можливість ефективної реалізації не тільки доступу в пам'ять, але і доступу до пристроїв вводу/виводу, а також контролерам мережевих адаптерів комунікаційних середовищ. У мультитредовій програмі можливе досягнення граничного суміщення обчислень в мультитредових процесорах з міжпроцесорними обмінами. Тред, який звернувся до мережного адаптера, буде чекати завершення обміну, в той час як інші треди будуть виконуватися. Ця властивість мультитредових мікропроцесорів робить їх проблемно-орієнтованими на побудову з них масово паралельних систем.

Слід зазначити, що до мультитредових мікропроцесорів можна віднести трансп’ютер з їх апаратно підтриманим виключно малим, при відповідній тактовій частоті, часом перемикання контексту процесів і віртуалізацією каналів (Т-9000).

Таким чином, мультитредова архітектура є наступним, після суперскалярної, кроком у напрямку розвитку методів динамічного розпаралелювання програм при повному використанні результатів статичного розпаралелювання. Ця архітектура, якщо не знімає взагалі, не висуває вимоги локалізації оброблюваних даних.

Мультитредова архітектура пропонує рішення для наступних проблем, що перешкоджають розвитку суперскалярних мікропроцесорів:

- ефективного завантаження великої кількості функціональних пристроїв;

- подолання розриву у швидкодії виконання регістрових команд і команд доступу в пам'ять;

- зменшення часу обслуговування переривань в порівнянні з суперскалярними процесорами за рахунок можливості виділення окремого треду, який виконує програми обробки переривання, і можливість роботи в режимі жорсткого реального часу;

- ефективного поєднання обчислень в мікропроцесорах з міжпроцесорними обмінами.

РОЗДІЛ 2 Теоретична частина

2.1 Мультитредові процесори з тредами, що виявляються шляхом аналізу потоків управління програми

Мультитредова модель виконання програми

Мультитредові процесори з умовно виконуваними тредами використовують агресивну парадигму виконання коду з метою вилучення умовно виконуваних тредів з послідовної програми. Відповідно до даної парадигми програма розбивається на сукупність одиниць обробки, які називаються сегментами, за допомогою програмних і апаратних засобів. Сегмент - частина програми, виконанню якої відповідає тред. Сегмент являє собою безперервну область послідовності команд (наприклад, частина базисного блоку, базисний блок, безліч базисних блоків, одиночну ітерацію циклу, повний цикл, звернення до функції і т.д.). Можливі різні методи формування сегментів і організації їх виконання. Далі буде представлений один з можливих варіантів, який предметно ілюструє суть мультитредового мікропроцесора з умовно виконуваними тредами.

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

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

Кожен з процесорних елементів вибирає і виконує команди, що належать виділеному йому сегменту. Значення поділюваних процесорними елементами регістрів копіюються в кожен ПЕ. Результат модифікації вмісту регістрів динамічно направляється безлічі паралельних ПЕ відповідно до генерованими компілятором масками.

Доступ до пам'яті здійснюється спекулятивно (умовно, за припущенням), без знання послідовності попередніх команд завантаження або збереження. Звернення до даних здійснюється паралельно багатьом ПЕ, обробка призупиняється тільки у випадку справжньої залежності даних.

Приклад архітектури мультитредового процесора зображений в додатку 2.

Важливо зауважити, що сегменти хоча і розділені на групи команд, але не є незалежними. Так як сегменти є частинами послідовного потоку команд, то відносини за даними і управлінням між індивідуальними командами повинні підтримуватися в процесі виконання. Ключовим питанням у мультитредовій реалізації є забезпечення зв'язку за даними і управлінням між паралельними процесорами. Тобто, як забезпечити виконання послідовного обходу ГУЗ, якщо фактично виконується непослідовний обхід?

Послідовний обхід підтримується наступним чином. По-перше, для кожного процесора забезпечується послідовна модель виконання призначеного йому сегменту. По-друге, пропонується послідовний порядок виконання для сукупності процесорів, який підтримується за допомогою організації циклічної черги ПЕ. Покажчики початку, і кінця черги ідентифікують ПЕ, які виконують найраніший і найпізніший з призначених сегментів відповідно.

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

У разі використання регістрової пам'яті логіка управління синхронізує створення значень регістрів в сегментах-попередниках з використанням цих значень в сегментах-наступниках. Вироблювані сегментом регістрові значення можуть бути визначені статично і відзначені в масці створення сегмента. У момент вироблення відповідного регістрового значення, якщо є відмітка в масці створення, це значення надсилається через односпрямований кільцевий канал (див. Дод. 2) наступним сегментам, тобто в ПЕ, які є логічними наступниками ПЕ, яке виробило значення. Завантажувані з кільцевого каналу в регістри значення, призначені для сегментів-наступників, визначаються в масці накопичення, яка є об'єднанням масок створення активних сегментів-попередників. Як тільки значення отримані з ПЕ попередників, очищаються ознаки збереження в ПЕ-наступників. Якщо сегмент використовує одне з цих значень, потребуюча команда може бути виконана тільки в тому випадку, якщо значення було отримано, інакше вона чекає одержання необхідного значення.

На відміну від значень регістрів, для значень, що зберігаються в пам'яті, в силу динамічного обчислення адрес не можна заздалегідь точно визначити, які з них використовуються або виробляються сегментом. Якщо відомо, що сегмент використовує значення з пам'яті (використовуючи команду завантаження), яке вироблене (за допомогою команди збереження) у більш ранньому сегменті, можливо синхронізувати використання і виробництво цього значення. Тобто завантаження в сегменті-наступнику може бути відкладене до тих пір, поки в сегменті-попереднику не буде виконана команда збереження (схоже на ситуацію з регістрами, проте механізм синхронізації все ж інший зважаючи несувимірності розмірів простору імен).

У загальному випадку, коли таке знання недоступне, може бути зроблений консервативний або агресивний підхід. Консервативний підхід має на увазі необхідність очікування до тих пір, поки не виникне впевненість, що команда завантаження прочитає правильне значення. Цей підхід зазвичай має на увазі затримку виконання команд завантаження всередині сегмента до тих пір, поки не завершили операції запису в пам'ять всі сегменти-попередники, результат яких може бути використаний наступною командою. При агресивному підході завантаження з пам'яті в регістри ПЕ повинні виконуватися спекулятивно, в припущенні, що сегмент-попередник пізніше не буде зберігати значення в ту ж саму комірку пам'яті. Щоб гарантувати, що ніякий сегмент-попередник не записує значення в комірку пам'яті, попередньо зчитану сегментом-наступником, повинна проводитися перевірка в процесі виконання обчислень. Якщо ця перевірка ідентифікує завантаження і збереження, які знаходяться в суперечності (не відбуваються у відповідному порядку), пізніша одиниця обробки повинна бути перервана, і повинна бути ініціалізована відповідна процедура відновлення. У мультитредових процесорах використовується агресивний підхід.

Через спекулятивний характер мультитредове виконання повинно мати як засоби підтвердження правильності виконання, так і засоби виправлення у разі неправильного виконання. Виконання команд усередині сегмента може розглядатися як спекулятивне з двох точок зору:

- спекулятивне по управлінню;

- спекулятивне за даними.

Якщо в результаті спекулятивного управління передбачення наступного сегменту виявилося невірним, то наступний сегмент (сегменти) повинен бути скасований і відновлена правильна послідовність сегментів. Аналогічно сегмент, який використовує неправильні дані, повинен бути скасований, і повинно бути відновлено правильне значення даних. У будь-якому випадку скасування сегмента призводить до скасування всіх сегментів, виконуваних після скасованого (інакше підтримка послідовної семантики виявляється складною).