Організація блоку вибірки для вирішення конфліктів по керуванню

Реферат

Організація блоку вибірки для вирішення конфліктів по керуванню


Команди умовних і безумовних переходів часто зустрічаються у програмах. У типовій програмі вони складають біля 20% загальної кількості команд.

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

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

На рис. 1, а показано, як виконання команди безумовного переходу впливає на роботу 4-стадійного конвеєра. Наприклад: команда І2 являється командою умовного переходу. Тому, адреса переходу обчислюється на кроці E2, а Ik – цільова команда переходу. Для ефективної роботи конвеєра необхідно видалити команди I3 й I4, а також вибрати команду Ik на такті 5. Накладні витрати в цьому прикладі складають 2 такти.

Для скорочення накладних витрат переходу, адресу переходу можна обчислювати раніше за допомогою додаткової підсистеми у блоці вибірки команди, яка призначена для швидкого виявлення команд переходу і обчислення їх цільових адрес. Завдяки цій підсистемі конфлікт можна розв’язати (видалити з конвеєра команди І3 й І4) на етапі D2, результатом чого буде послідовність подій на рис. 1, б. У цьому випадку накладні витрати переходу складатимуть один такт.

Для скорочення негативних наслідків команд переходів або промахів при зверненні до кеш-пам’яті до складу багатьох процесорів включають складні блоки вибірки, які вибирають команди ще до того, як вони знадобляться, і поміщують їх у чергу. Блок диспетчеризації пересилає команди, розташовані на початку черги, до блоку виконання (рис. 2). Крім вибірки команд з черги блок диспетчеризації виконує їх декодування. Для ефективного функціонування конвеєра блок вибірки повинен володіти потужними засобами декодування і обробки команд, які дозволяють розпізнати і виконати команди переходу. Його завдання – постійне формування черги команд, що зменшує вплив на роботу конвеєра випадкових затримок при вибірці чергової команди. Якщо зупинка конвеєра викликана конфліктом по даних, блок диспетчеризації не може передавати наступним стадіям команди з черги. Однак, це не заважає блоку вибірки продовжувати вибирати команди і поміщувати їх у чергу. Коли затримка при вибірці команди виникає внаслідок переходу або промаху при зверненні до кеш-пам’яті, блок диспетчеризації може продовжити вибирати команди з черги і передавати наступним блокам для виконання.

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




Такти

Команди

1

2

3

4

5

6

7

Час

І1

І2 (перехід)

І3

І4

а)

F1

D1

E1

W1

F2

D2

E2

F3

D3

х

F4

х

Рис. 1. Часові діаграми роботи конвеєра при виконанні команди безумовного переходу: адреса переходу обчислюється на стадії виконання (а); адреса переходу обчислюється на стадії декодування (б).

8

Іk

Іk+1

Fk

Dk

Ek

Wk

Fk+1

Dk+1

Ek+1

Такти

1

2

3

4

5

6

7

І1

І2 (перехід)

І3

б)

F1

D1

E1

W1

F2

D2

F3

х

Іk

Іk+1

Fk

Dk

Ek

Wk

Fk+1

Dk+1

Ek+1

Час

F: Вибірка команди

Блок вибірки команд





  





Черга команд

D: Блок диспетчеризації/ декодування



E: Вибірка команди

W: Запис результату



Рис. 2. Черга команд конвеєра


Припустимо, команда I1 викликає зупинку конвеєра на 2 такти. Оскільки у черзі ще є місце, блок вибірки продовжує свою роботу, а довжина 

Такти

1

2

3

4

5

6

7

Час

І1

І2

І3

І4

F1

D1

E1

Е1

F2

D2



F3

Рис. 3. Виконання переходів при наявності черги команд.

8

Іk

Іk+1

Fk

Dk

Ek

Wk

Fk+1

Dk+1

Ek+1

Довжина черги

1

1

1

1

2

3

2

І5 (перехід)

І6

F5

D5

F6

х

1

1

1

9

10

Е1

W1

Е2

W2



D3

E3

W3

F4



D4

E4

W4черги на такті 6 збільшується до 3.



Команда I5 є командою переходу. Її цільова команда Ik вибирається у такті 7, а команда I6 видаляється з конвеєра на тому ж такті. Але видалення команди I6 не приводить до зупинки конвеєра на такті 7, як при відсутності черги. Замість цього команда I4 диспетчеризується з черги на стадію дешифрування. Після видалення команди I6 довжина черги на такті 8 скорочується до одної команди і залишається такою, поки не відбудеться наступна зупинка конвеєра.

Команди I1, I2, I3, I4, Ik завершуються у послідовних тактах. При цьому команда переходу не збільшує загальний час виконання, оскільки вибірка цільової команди Ik здійснюється одночасно з виконанням інших команд. З цією метою її адреса обчислюється ще при вибірці команди переходу. Описана технологія обробки переходів називається розгалуженням із суміщенням. Слід відмітити, що розгалуження із суміщенням може здійснюватися тільки у випадку, коли на момент виявлення команди переходу в черзі знаходиться хоча б одна команда. Тому слід підтримувати чергу заповненою, щоб з неї в будь-який час можна було вибрати команду для обробки. Для цього можна підвищити швидкість вибірки команд з кеша блоком вибірки. У багатьох процесорах ширина шини між блоком вибірки і кешем команд дозволяє зчитувати більше одної команди за один такт.

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

*Цикл обробки команди розбивається на чотири незалежні етапи наведених нижче:

F: Вибірка (Fetch) – читання команди з пам’яті.

D: Декодування (Decode) – декодування команди і вибірка її вхідних операндів.

E: Виконання (Execute) – виконання заданої в команді операції.

W: Запис (Write) – збереження результату по цільовій адресі.

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

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



Вибірка

Вибірка

Команда

Команда

Результат

а)

Вибірка

Вибірка

Команда

Команда

Результат

б)

Очікування

Очікування

Скидання

Нова адреса

Рис. 4. 2-стадійний конвеєр виконання командРозглянемо найпростішу схему розділення процесу обробки команди на два етапи – вибірка команди і виконання. При виконанні команди існують інтервали часу, коли звернення до пам’яті не здійснюється. Їх можна використати для вибірки наступної команди паралельно з виконанням поточної. Цей підхід проілюстровано на рис. 1, а. 



Конвеєр має дві незалежні „робочі стадії” – вибірка команди і виконання команди. На першій стадії команда вибирається з пам’яті та завантажується в буфер. Коли друга стадія звільниться, перша передаватиме їй команду з буфера. Поки команда виконуватиметься на другій стадії, на першій можна використати будь-який вільний цикл звернення до пам’яті та вибрати наступну команду, завантаживши її в буфер. Цей процес називається вибіркою команди з упередженням (instruction prefetch) або накладанням вибірки (fetch overlap).

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

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

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

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

F: Вибірка (Fetch) – читання команди з пам’яті.

D: Декодування (Decode) – декодування команди і вибірка її вхідних операндів.

E: Виконання (Execute) – виконання заданої в команді операції.

W: Запис (Write) – збереження результату по цільовій адресі.Послідовність подій при такій схемі обробки команди показана на рис. 2, а. У кожний момент часу процесор обробляє 4 команди. Це означає, що він містить 4 окремих функціональних блока (рис. 2, б). Інформація передається від одного блоку до іншого через проміжні буфери. По мірі обробки команди конвеєром у проміжні буфери повинна поступати вся необхідна для чергової стадії інформація. Усі етапи виконуються за однакові проміжки часу, які називаються тактом конвеєра. 4 команди виконуватимуться на такому конвеєрі протягом 7 тактів (замість 16 тактів на процесорі без конвеєру). Таким чином, конвеєризація збільшує пропускну здатність процесора (кількість виконаних команд за одиницю часу), не зменшуючи часу виконання однієї команди

При побудові діаграми на рис. 2, а передбачається, що кожна команда проходить усі 4 етапи обробки. У дійсності справи відбуваються інакше. Наприклад, при обробці команди завантаження даних з пам’яті етап W пропускається. Але при організації конвеєра для спрощення схем керування синхронізація проводиться таким чином, що кожна команда затримується на етапі певний час, навіть якщо ніякі операції з нею не виконуються. По-друге, при побудові діаграми вважається, що всі етапи можна виконувати паралельно і що при цьому, наприклад, не виникають конфлікти при доступі до пам’яті.

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





Такти

Команди

1

2

3

4

5

6

7

Час

І1

І2

І3

І4

а)

F1

D1

E1

W1

F2

D2

E2

W2

F3

D3

E3

W3

F4

D4

E4

W4

F: Вибірка команди

В1

D: Вибірка команди

В2

E: Вибірка команди

В3

W: Вибірка команди

Проміжні буфери

б)

Рис. 5. Структура 4-стадійного конвеєра: команди за 4 кроки (а); апаратна організація (б).


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

2. Складність схем керування пам’яттю і регістрами, оптимізації роботи конвеєра різко зростає зі збільшенням стадій. Це може привести до того, що схема керування конвеєром виявиться складнішою тих засобів, що реалізують самі операції.

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


Література



Мюллер Скотт. Модернизация и ремонт ПК. 12-е издание. - М.: Вильямс, 2001. – 1162с.

Гук М. Интерфейсы ПК. – СПб.: Питер, 1999. – 416с.





11