Комп'ютери з явним паралелізмом виконання команд

Як ми вже побачили з матеріалу даного розділу, планування порядку обчислень є досить важким завданням, яке доводиться вирішувати при проектуванні сучасного комп’ютера. У суперскалярній архітектурі для розпізнавання залежностей між команда­ми застосовуються досить складні апаратні рішення (наприклад, в Р6 і наступних про­цесорах фірми Intel для цього використовується буфер перевпорядковування команд - Reorder Buffer). Проте розміри такого апаратного планувальника при збільшенні кіль­кості функціональних пристроїв зростають в геометричній прогресії. Тому суперскалярні проекти зупинилися на відмітці 5-6 оброблюваних за цикл команд. Навіть КДФК теж далеко не завжди можуть забезпечити повне заповненням в’язанок команд - реальне завантаження близько 6-7 команд в такті.

Вище зазначені проблеми призначена вирішувати нова архітектура із назвою EPIC (Explicitly Parallel Instruction Set Computing).

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

Архітектура EPIC передбачає пряме розпаралелювання виконання програми, тобто компілятор мусить повідомляти процесор про те, яка частина коду може виконуватися паралельно. Оптимізований за попереднім означенням компілятор EPIC аналізує про­грамний код, аби визначати, де та коли відбудуться/не відбудуться умовні переходи та знайти і позначити ті частини програмного коду, які можна виконувати паралельно.

Прикладом процесора з архітектурою EPIC є процесор ІА-64 фірми Intel. В цьому процесорі команди, як і в архітектурі КДСК, пакуються компілятором в 128-розрядні в’язанки команд. Кожна в’язанка команд процесора ІА-64 містить три команди та ша­блон, як це показано на рис. 5.30.

127 0

Команда 2 Команда 1 Команда 0 Шаблон

Рис. 5.30. В’язанка команд процесора ІА-64

В шаблоні вказується залежність між командами в одній в’язанці та між в’язанками, тобто вона вказує, чи можна одночасно виконувати i-ту (і= 0,1,2) команду в’язанки m од­ночасно з j-ю (j= 0,1,2) командою в’язанки п. Кожній в’язанці в процесорі виділяється три функціональних пристрої, тобто кожній команді виділяється один пристрій. Вміст поля шаблону встановлюється або при генеруванні коду компілятором, або безпосередньо системним програмістом, що пише мовою асемблер. Процес генерації коду виконують так, аби гарантовано позбутися конфліктів типу RAW, WAW в межах командної групи.

Кожна з трьох команд в’язанки має формат, приведений на рис. 5.31.

39 27 26 21 20 14 13 7 6 0
Код операції Предикат Рг операнда 1 Рг операнда 2 Рг результату

Рис. 5.31. Формат кожної з трьох команд в’язанки

 

До складу команди входять наступні поля: коду операції, предиката, номери регістрів двох операндів та регістра результату. Розрядності кожного поля вказані на рисунку.

Поле предиката вказує номер регістра предиката, яких в процесорі є 64. Предикація - це спосіб обробки умовних переходів. В процесорі ІА-64 виконуються обидві вітки переходу. Суть способу предикації полягає в наступному. Командам різних гілок одного умовного переходу виділяються різні регістри предиката. Ці команди виконуються на функціональних пристроях процесора, а їх результати записуються до пам’яті тільки після визначення вмісту регістрів предиката, тобто після обчислення умови переходу Вмісту регістрів вітки переходу, якій відповідає умова переходу, присвоюється значення і, а вмісту регістрів вітки переходу, якій не відповідає умова переходу, присвоюється значення 0. Процесор перевіряє вміст регістрів предикату і записує в пам’ять результати тільки тих команд, які вказують на регістри предикатів з одиничним вмістом.

Архітектура ІА-64 підвищує рівень паралельного виконання команд за рахунок того, що вона дозволяє на рівні мови асемблер прямо вказувати на паралелізм, реалізує в’я­занки, кожна з яких містить три виконувані команди та містить множину надлишкових програмно-недосяжних регістрів, що дублюють операнди поточних команд, запобіга­ючи тим самим завчасному перезапису цих операндів.

 

5.9. Короткий зміст розділу

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

Розглянуто особливості запобігання конфліктам в суперскалярних процесорах, які є наступним кроком в побудові високопродуктивних процесорів, Суперскалярний про­цесор має кілька функціональних блоків і виконує кілька команд за один такт, тобто в такому процесорі одна команда виконується менще як за один такт. Прикладами супер- скалярних процесорів є PowerPC фірми IBM, UltraSparc фірми Sun, Alpha фірми DEC. Але методи запобігання конфліктам в таких процесорах є ще складнішими, ніж у конве­єрних процесорах, що вимагає відповідного ускладнення апаратних засобів.

Були розглянуті архітектури комп’ютерів, в яких відсутні конфлікти команд, а саме: комп’ютери з довгим форматом команди, а також комбіновані архітектури, в яких по­єднано архітектури КГІСК та КДФК.

Проблеми забезпечення динамічного планування виконання команд привели роз­робників до архітектури комп’ютера з явним паралелізмом EPIC, прикладом якої ста­ла розробка ІА-64 фірми Intel. Комп’ютери цієї архітектури опрацьовують паралельно в’язанку команд, яка вказує декілька операцій, що можуть виконуватися паралельно.

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

Для зменшення впливу умовних переходів на продуктивність конвеєра в процесо­рі ІА-64 введено предикатні команди. В цьому процесорі всі команди виконуються, але результати їх виконання записуються до регістрового файла лише тоді, коли розряд пре­диката рівний 1. Результатом є те, що не потрібно зупиняти конвеєр до вияснення умови переходу, хоча виконується більша кількість команд.

5. 10. Література для подальшого читання

Конфлікти в конвеєрі команд та методи їх усунення розглянуті в роботах [7, 8,13, 14, 16,18-21]. В роботах [3,4,30-33] проведено аналіз методів запобігання трьох класів кон­фліктів: структурних, конфліктів за даними та конфліктів керування. Опис симулятора WinDLX є на web-сторінці www.

В роботах [9, 10, 22-26] розглянуто особливості запобігання конфліктам в суперска- лярних процесорах. Для аналізу особливостей реалізації засобів запобігання конфлік­там в суперскалярних процесорах PowerPC фірми IBM, UltraSparc фірми Sun, Alpha фір­ми DEC та інших доцільно пошукати їх описи на web-сторінках цих фірм. Використання розподіленої буферної пам’яті (вікна команд) для перевпорядкування команд запропо­новано в роботах [1, 27].

Обмеження паралелізму рівня команд проаналізовано в [28, 29]. В роботах [3, 5, 6, 12, 15] детально розглянуті архітектури комп’ютерів, у яких відсутні конфлікти команд, а саме комп'ютерів з довгим форматом команди. Зокрема в роботі [2] розглянуті питан­ня побудови перших процесорів обробки сигналів АР-120В фірми FPS з архітектурою КДФК. Принципи побудови компіляторів КДФТСможна знайти в [4, 11, 17].

Інформацію про комбіновані архітектури, в яких поєднано архітектури КПСК та КДФК, можна знайти в [5].

Архітектура комп’ютера з явним паралелізмом EPIC описана в [7].

5.11. Література до розділу 5

1. Anderson, D. W., F. J. Sparacio, and R. M. Tomasulo [1967]. “The IBM 360 Model 91: Processor philosophy and instruction handling”, IBM J. Research and Development 11:1 (January), 8-24.

2. Charlesworth, A. E. [1981]. “An approach to scientific array processing: The architecture design of the AP-120B/FPS-164 family”, Computer 14:12 (December), 12-30.

3. COLWELL, R. P., R. P. NIX, J. J. O’DONNELL, D. B. PAPWORTH, AND P. K. RODMAN [1987]. “A VLIW architecture for a trace scheduling compiler”, Proc. Second Conf. on Architectural Support for Programming Languages and Operating Systems, IEEE/ACM (March), Palo Alto, Calif., 180-192.

4. Ellis, J. R. [1986]. Bulldog: A Compiler for VLIW Architectures, MIT Press, Cambridge, Mass.

5. FISHER, J. A. [1981]. “Trace scheduling: A technique for global microcode compaction”, IEEE Trans, on Computers 30:7 (July), 478At90.

6. FISHER, J. A. [1983]. “Very long instruction word architectures and ELI-512”, Proc. Tenth Symp­osium on Computer Architecture (June), Stockholm, 140-150.

7. Fisher, J. A. and S. M. Freudenberger [1992]. “Predicting conditional branches from previous runs of a program”, Proc. Fifth Conf. on Architectural Support for Programming Languages and Operating Systems, IEEE/ACM (October), Boston, 85-95.

Hwu, W.-M. and Y. Patt [1986]. “HPSm, a high performance restricted data flow architecture having minimum functionality”, Proc. 13th Symposium on Computer Architecture (June), Tokyo, 297-307.

8. Johnson, M. [1990]. Superscalar Microprocessor Design, Prentice Hall, Englewood Cliffs, N.J.

9. JOUPPI, N. P. AND D. W. WALL [1989]. “Available instruction-level parallelism for superscalar and superpipelined processors”, Proc. Third Conf. on Architectural Support for Programming Languages and Operating Systems, IEEE/ACM (April), Boston, 272-282.

10. Lam, M. [1988]. “Software pipelining: An effective scheduling technique for VLIW processors”, SIGPLAN Conf. on Programming Language Design and Implementation, ACM (June), Atlanta, Ga., 318-328.

11. Mahlke, S. A., W. Y. Chen, W.-M. Hwu, B. R. Rau, and M. S. Schlansker [1992]. “Sentinel sched­uling for VLIE and superscalar processors”, Proc. Fifth Conf on Architectural Support for Programming Languages and Operating Systems (October), Boston, IEEE/ACM, 238-247.

12. McFarling, S. [1993] “Combining branch predictors”, WRL Technical Note TN-36 (June), Digital Western Research Laboratory, Palo Alto, Calif.

13. McFarling, S. and J. Hennessy [1986]. “Reducing the cost of branches”, Proc. 13th Symposium on Computer Architecture (June), Tokyo, 396-403.

14. N1COLAU, A. AND J. A. Fisher [1984]. “Measuring the parallelism available for very long instr­uction word architectures”, IEEE Trans, on Computers C-33:ll (November), 968-976.

15. Pan, S.-T., K. So, and J. T. Rameh [1992]. “Improving the accuracy of dynamic branch prediction using branch correlation”, Proc. Fifth Conf. on Architectural Support for Programming Languages and Operating Systems, IEEE/ACM (October), Boston, 76-84.

16. RAU, B. R., C D. GLAESER, AND R. L. PICARD [1982]. “Efficient code generation for horizontal architectures: Compiler techniques and architectural support”, Proc. Ninth Symposium on Computer Architecture (April), 131-139.

17. Riseman, E. M. and C. C Foster [1972]. “Percolation of code to enhance parallel dispatching and execution”, IEEE Trans, on Computers C-2L12 (December), 1411-1415.

18. SMITH, A. and J. LEE [1984]. “Branch prediction strategies and branch-target buffer design”, Computer 17:1 (January), 6-22.

19. Smith, J. E. [1981]. “A study of branch prediction strategies”, Proc. Eighth Symposium on Comp­uter Architecture (May), Minneapolis, 135-148.

20. Smith, J. E. and A. R. Pleszkun [1988]. “Implementing precise interrupts in pipelined processors”, IEEE Trans, on Computers 37:5 (May), 562-573. This paper is based on an earlier paper that appeared in Proc. 12th Symposium on Computer Architecture, June 1988.

21. Smith, M. D., M. Horowitz, and M. S. Lam [1992]. “Efficient superscalar performance through boosting”, Proc. Fifth Conf. on Architectural Support for Programming Languages and Operating Syste­ms (October), Boston, IEEE/ACM, 248-259.

22. Smith, M. D., M. Johnson, and M. A. Horowitz [1989]. “Limits on multiple instruction issue”.

23. SOHI, G. S. [1990]. “Instruction issue logic for high-performance, interruptible, multiple functi­onal unit, pipelined computers”, IEEE Trans, on Computers 39:3 (March), 349-359.

24. SOHI, G. S. AND S. Vajapeyam [1989]. “Tradeoffs in instruction format design for horizontal architectures”, Proc. Third Conf. on Architectural Support for Programming languages and Operating Systems, IEEE/ACM (April), Boston, 15-25.

25. THORLIN, J. F. [1967]. “Code generation for PIE (parallel instruction execution) computers”, Proc. Spring Joint Computer Conf. 27.

26. TOMASULO, R. M. [1967]. “An efficient algorithm for exploiting multiple arithmetic units”, IBM J. Research and Development 11:1 (January), 25-33.

27. WALL, D. W. [1991]. “Limits of instruction-level parallelism”, Proc. Fourth Conf. on Architectu­ral Support for Programming Languages and Operating Systems (April), Santa Clara, Calif., IEEE/ ACM, 248-259.

 

28. Wall, D. W. [1993]. Limits of Instruction-Level Parallelism, Research Rep. 93/6, Western Research Laboratory, Digital Equipment Corp. (November).

29. WEISS, S. and J. E. Smith [1984]. “Instruction issue logic for pipelined supercomputers”, Proc. 11th Symposium on Computer Architecture (June), Ann Arbor, Mich., 110-118.

30. WEISS, S. and J. E. SMITH [1987]. “A study of scalar compilation techniques for pipelined sup­ercomputers”, Proc. Second Conf. on Architectural Support for Programming Languages and Operating Systems (March), IEEE/ACM, Palo Alto, Calif., 105-109.

31. Yeh, T. and Y. N. Patt [1992]. “Alternative implementations of two-level adaptive branch predicti­on”, Proc. 19th Symposium on Computer Architecture (May), Gold Coast, Australia, 124-134.

32. YEH, T. AND Y. N. Patt [1993]. “A comparison of dynamic branch predictors that use two levels of branch history”, Proc. 20th Symposium on Computer Architecture (May), San Diego, 257-266.