Спекулятивне виконання

План

Лекція №31

Контрольні питання

Розмір сторінки

Розроблювачі ОС для існуючих машин рідко мають можливість впливати на розмір сторінки. Однак для знову створюваних комп'ютерів розв'язок щодо оптимального розміру сторінки є актуальним. Як і слід було сподіватися, немає одного найкращого розміру. Скоріше є набір факторів, що впливають на розмір. Звичайно розмір сторінки – це ступінь двійки від 29 до 214 байт.

Чим більше розмір сторінки, тем менше буде розмір структур даних, що обслуговують перетворення адрес, але тим більше будуть втрати, пов'язані з тим, що пам'ять можна виділяти тільки посторінково.

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

Як правило, розмір сторінок задається апаратно, наприклад в DEC PDP-11 – 8 Кбайт, в DEC VAX – 512 байт, в інших архитектурах, таких як Motorola 68030, розмір сторінок може бути заданий програмно. Враховуючи всі обставини, у ряді архитектур виникають множинні розміри сторінок, наприклад в Pentium розмір сторінки коливається від 4 Кбайт до 8 Кбайт. Проте більшість комерційних ОС через складність переходу на множинний розмір сторінок підтримують тільки один розмір країн

1. Уведіть поняття сегментно-сторінкової організації.

2. Уведіть поняття «організація таблиці сторінок».

3. Дайте пояснення що таке інвертована таблиця сторінок.

Тема: Спекулятивне виконання команд.

Ціль: Вивчити можливості спекулятивного виконання команд при обробці програм процесором.

1. Спекулятивне виконання.

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

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

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

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

Рис. 1. Граф базового блоку для фрагмента програми, наведеного в лістингу 1

Лістинг 1. Фрагмент програми

evesum=0; oddsum=0; 1=0;

while (I<limit) { k=i*i*i;

if(((i/2)*2)-=i)

evensum=evensum+k;

else

oddsum=oddsum+k; i=i+l;

}

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

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

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

Однак при наявності спекулятивних команд виникає ще одна проблема, яку не можна розв'язати шляхом підміни регістрів. Що відбудеться, якщо спекулятивна команда викличе виключення? Як приклад можна привести команду LOAD, яка викликає кеш-промах у комп'ютері з рядком кэша досить великого розміру (скажемо, 256 байт) і пам'яттю, яка працює набагато повільніше, чим центральний процесор і кеш. Якщо нам потрібна команда LOAD і робота машини зупиняється на кілька циклів, поки завантажується рядок кэша, то це не так страшно, оскільки дане слово дійсне потрібно. Але якщо машина простоює, щоб викликати слово, яке, як виявиться пізніше, нам ні до чого, це зовсім нераціонально. Якщо подібних "оптимизаций" занадто багато, то центральний процесор буде працювати повільніше, чим якби "оптимизаций" взагалі не було. (Якщо машина містить віртуальну пам'ять, про яку розповідається в главі 6, те спекулятивне виконання команди LOAD може навіть викликати звертання до відсутньої сторінки. Подібні помилки можуть значно вплинути на продуктивність, тому важливо їх уникати.)

У ряді сучасних комп'ютерів дана проблема вирішується в такий спосіб. У них підтримується спеціальна команда SPECULATIVE-LOAD, яка робить спробу викликати слово з кеш-пам'яті, а якщо слова там ні, просто припиняє виклик. Якщо значення в кэше виявляється й воно дійсно потрібно, його можна використовувати, а якщо його в кэше ні, апаратне забезпечення повинне відразу ж його одержати. Якщо потім виявиться, що дане значення нам не потрібно, то ніяких втрат часу не буде.

Більш складну ситуацію можна проілюструвати наступним оператором:

if (х > 0) z = у/х;

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

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

Дата добавления: 2014-01-05