Комп'ютери з явним паралелізмом виконання команд
Як ми вже побачили з матеріалу даного розділу, планування порядку обчислень є досить важким завданням, яке доводиться вирішувати при проектуванні сучасного комп’ютера. У суперскалярній архітектурі для розпізнавання залежностей між командами застосовуються досить складні апаратні рішення (наприклад, в Р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 Symposium 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 scheduling 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 instruction 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 Computer 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 Systems (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 functional 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 Architectural 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 supercomputers”, 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 prediction”, 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.