202

8. 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.

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

10. 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.

11. 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.

12. Mahlke, S. A., W. У. 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.

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

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

15. 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.

16. 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.

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

18. 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.

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

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

21. 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.

22. 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.

23. Smith, M. D., M. Johnson, and M. A. Horowitz [1989]. "Limits on multiple instruction issue".

24. 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.

25. SOFII, 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.

26. THORLIN, J. E [1967]. "Code generation for PIE (parallel instruction execution) computers", Proc. Spring Joint Computer Conf. 27.

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

28. 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.

---

203

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

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

31. 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.

32. 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.

33. 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.

5.12. Питання до розділу 5

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

2. Назвіть три класи конфліктів у конвеєрі команд та причини їх появи.

3. Які є дві групи структурних конфліктів?

4. Наведіть приклад структурних конфліктів, які виникають через потребу порушення такто­вої частоти роботи конвеєра.

5. Наведіть приклад структурних конфліктів, які виникають у зв'язку з необхідністю очіку­вання на звільнення ресурсів комп'ютера.

6. Чому розробники допускають наявність структурних конфліктів?

7. Яка причина створення процесорів з неконвеєрними функціональними пристроями?

8. На який час потрібно призупинити роботу конвеєра команд при появі структурних конф­ліктів?

9. Які є способи вирішення структурних конфліктів?

10. Коли виникає конфлікт за даними?

11. Назвіть три можливі конфлікти за даними.

12. Поясніть суть конфлікту "читання після запису".

13. Поясніть суть конфлікту "запис після читання".

14. Поясніть суть конфлікту "запис після запису".

15. Які можливі конфлікти за даними?

16. Які є методи зменшення впливу залежностей між даними на роботу конвеєра команд?

17. Що дає призупинення роботи конвеєра при виявленні конфлікту за даними?

18. Що дає застосування випереджувального пересилання при виявленні конфлікту за даними?

19. Як реалізується в конвеєрі команд випереджувальне пересилання?

20. Чи завжди є можливим випереджувальне пересилання?

21. Приведіть приклади можливих та неможливих випереджувальних пересилань.

22. Що роблять, оптимізуючи компілятори, щоб не допустити конфліктів за даними?

23. Які є ознаки наявності конфліктів за даними?

24. Для яких частин програми є ефективною статична диспетчеризація послідовності команд під час компіляції?

25. Як здійснюється динамічна диспетчеризація послідовності команд у програмі під час ком­піляції?

26. Поясніть суть методу перейменування регістрів.

27. Які є типи конфліктів керування?

28. Назвіть способи зниження втрат на вибірку команд переходу.

29. Поясніть суть способу обчислення виконавчої адреси команди переходу в ярусі декоду­вання команди.

---

204

30. Поясніть суть способу використання буфера адрес переходів.

31. Поясніть суть способу використання буфера команд переходів.

32. Поясніть суть способу використання буфера циклу.

33. Назвіть способи зниження втрат на виконання команд умовного переходу.

34. Поясніть суть способу введення буфера попередньої вибірки з метою зниження втрат на виконання команд умовного переходу.

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

36. Поясніть суть способу затримки переходу з метою зниження втрат на виконання команд умовного переходу.

37. Поясніть суть способу статичного передбачення переходу з метою зниження втрат на ви­конання команд умовного переходу.

38. Назвіть методи статичного передбачення умовного переходу.

39. Поясніть суть методу повернення, який застосовується при статичному передбаченні умовного переходу.

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

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

42. Поясніть суть методу статичного передбачення умовного переходу, за яким результат пе­реходу визначається напрямом переходу.

43. Поясніть суть динамічного передбачення переходу.

44. Що таке таблиця історії переходів? Як вона реалізується?

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

46. Наведіть однорівневу схему передбачення переходу з формуванням адреси таблиці історії переходів у регістрі глобальної історії.

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

48. Наведіть дворівневу схему передбачення переходу з використанням таблиці локальної історії.

49. Наведіть структуру гібридної схеми передбачення переходу.

50. Проаналізуйте тотожність та розбіжність КДФК і суперскалярної архітектур.

51. Визначте місце суперскалярних і КДФК архітектур в ієрархії сучасних комп'ютерів.

52. Визначте та поясніть основні чинники, що обмежують ефективність КДФК архітектури.

53. Наведіть основні ідеї, покладені в основу архітектури EPIC.

---

^{Розділ 6}

Алгоритм виконання операцій

обробки даних

Операції обробки даних ініціюються відповідними командами обробки даних. До числа цих операцій входять:

• логічні операції (логічне множення, логічне додавання, інверсія і т. д.) над розряда­ми слів, скалярами та векторами;

• операції зсуву (праворуч, ліворуч) над скалярами та векторами;

• операції відношення: менше, більше, рівне, менше-рівне, більше-рівне;

• арифметичні операції (додавання, віднімання, множення та ділення) над одиноч­ними даними та векторами даних;

• операції обчислення елементарних функцій типу ехр X, In X, Sin X, Cos X, arctg y/x, Sh X, Ch X, піднесення до степеня А^m;

• операції перетворення даних (перетворення із формату з фіксованою в формат з рухомою комою і навпаки, перетворення з двійково-десяткового коду в двійковий і на­впаки і т. д.);

• операції реорганізації масивів і визначення їх параметрів: сортування, пошук мак­симуму або мінімуму, вибір заданого масиву зсув елементів масиву стиск масиву;

• операції обробки символів та стрічок символів: пошук символу, зсув, заміна симво­лів у стрічці, пакування стрічок символів, порівняння стрічок символів.

В останніх комп'ютерах у зв'язку з широким використанням засобів телекомуніка-цій та мультимедіа до складу основних операцій добавилися складні операції типу коду­вання, компресії, шифрування тощо.

В даному розділі розглянемо основні алгоритми виконання вищеназваних операцій, не вникаючи в питання їх реалізації в комп'ютері.

6.1. Логічні операції

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

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

---

206

6.1.1. Операція заперечення

Операція заперечення (інверсія, НЕ, NOT) є операцією над одним операндом і озна­чає, що біти із значенням "0" набувають значення "1" і навпаки. Для відображення дії ло­гічної операції часто використовують так звані таблиці істинності. Табл. 6.1 є таблицею істинності для операції заперечення.

Таблиця 6.1

біт операнда	біт результату
0	1
1	0

Приклади:

NOT (1000 10100010 1100) =0111 0101 1101 0011.

NOT (1110 1011 10100111) = 0001 01000101 1000.

6.1.2. Логічне І

Ця операція (загальноприйняте позначення І, AND) передбачає наявність як міні­мум двох операндів, назвемо їх X та Y. Вона виконує порозрядну кон'юнкцію змінних, тобто отримання одиниці лише тоді, коли всі вхідні змінні рівні одиниці. Відобразимо значення функції наступною таблицею істинності (табл. 6.2.)

Таблиця 6.2

бітХ	біт Y	біт результату
0	0	0
0	1	0
1	0	0
1	1	1

Приклади виконання операції логічного множення приведено на рис. 6.1.

6.1.3. Логічне АБО

Ця операція (загальноприйняте позначення АБО, OR) також передбачає наявність як мінімум двох операндів X та Y. Вона виконує порозрядну диз'юнкцію змінних, тобто отримання одиниці тоді, коли хоча б одна вхідна змінна рівна одиниці. Відобразимо зна­чення функції наступною таблицею істинності (табл. 6.3).

Таблиця 6.3

біт X	біт Y	біт результату
0	0	0
0	1	1

---

Смотрите также файлы

• Екологія посібник.doc

• LR3_[5405].doc

• Питання до модуля 1 з АК.doc

• Питання до 1 модуля з КЕ.doc

• ДБН В.3.2-2-2009_Жил_здания_реконст_кап_ремонт.doc