автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Разработка методов определения параметров устройств предварительной выборки команд в ЭВМ общего назначения

ВВЕДЕНИЕ

ГЛАВА I. ПРОБЛЕМЫ И СПОСОШ АНАЛИЗА ИЕРАРХИЧЕСКОЙ

ПАМЯТИ ЭВМ.

1.1. Принциш построения иерархической памяти

1.2. Методы расчета параметров иерархической памяти

1.3. Особенности организации и работы верхних уровней иерархической памяти

1.4. Дуфер команд.

1.5. Оценка предельного увеличения производительности процессора за счет использования буферов команд и операндов

1.6. Выводы

ГЛАВА 2. ЭКСПЕРШЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ' ПОТОКА КОМАНД

2.1. Краткая характеристика средств использованных для исследования потоков команд.

2.2. Марковские модели потока форматов

2.3. Модели потока обращений к памяти за командами.

2.4. Частотный состав команд и форматов команд.

2.5. Экспериментальное исследование потока форматов команд.

2.6. Экспериментальное исследование потоков обращений к памяти за командами

2.7. Выводы

ГЛАВА 3. РАЗРАБОТКА И ИССЛЕДОВАНИЕ АНАЛИТИЧЕСКИХ МОДЕЛЕЙ

ПРЕДВАРИТЕЛЬНОЙ ВЫБОРКИ КОМАНД.

3.1. Общая характеристика задач аналитического моделирования процессов предварительной выборки команд

3.2. Полумарковская модель процесса выборки команд из оперативной памяти (поток форматов моделируется односвязной марковской цепью)

3.3. Полумарковская модель процесса выборки команд из оперативной памяти (элементы потока форматов взаимно независимы)

3.4. Оценка алгоритмов выборки команд из оперативной памяти . НО

3.5. Упрощенные аналитические модели работы процессора с буфером команд

3.5.1. Марковская модель работы процессора с буфером команд.

3.5.2. Упрощенная модель работы процессора с буфером команд, учитывавшая конфликты при обращениях к оперативной памяти

3.6. Выводы

ГЛАВА 4. ИССЛЕДОВАНИЕ НЕКОТОРЫХ МЕТОДОВ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ ПРОЦЕССОРОВ С ПРЕДВАРИТЕЛЬНОЙ ВЫБОРКОЙ КОМАНД.

4.1. Упрощенные аналитические модели конвейерной обработки данных при одинаковых длительностях выполнения этапов обработки команды.

4.2. Экспоненциальная модель трехэтапной конвейерной обработки команд.

4.3. Пример оценки эффективности конвейерной обработки команд.

4.4. Процессор с несколькими буферами команд.

4.5. Буферирование команд с прогнозированием адресов переходов

4.6. Реализация буфера команд с прогнозированием адресов переходов

4.7. Вывода

ГЛАВА 5. ОЦЕНКА ТОЧНОСТИ АНАЛИТИЧЕСКИХ МОДЕЛЕЙ ПРОЦЕССОВ

ВЫПОЛНЕНИЯ КОМАНД.

5.1. Трассовая имитационная модель работы процессора

5.2. Методика сопоставления данных имитационного и аналитического моделирования.

5.3. Оценка точности аналитических моделей

5.4. Выводы

ЗАШЯЕНИЕ

Актуальность проблемы. В "Основных направлениях экономического и социального развития СССР на I98I-I985 годы и на период до 1990 года" подчеркивается необходимость совершенствования вычислительной техники ее элементной базы и математического обеспечения, средств и систем сбора, передачи и обработки информации, повышения технического уровня вычислительной техники.

Решение этих задач невозможно без повышения уровня проектирования средств вычислительной техники, для чего необходимы научно обоснованные метода согласованного выбора и расчета параметров узлов и блоков ЭВМ в процессе их проектирования, а также методы оценки эффективности алгоритмов обработки информации закладываемых в аппаратуру и математическое обеспечение.

Успехи в совершенствовании и повышении технического уровня средств вычислительной техники существенным образом зависят от решения задач, связанных с проектированием оптимальных систем пашти, и согласования их параметров с параметрам! других узлов ЭВМ. Значительный вклад в решение этих задач внесли советские ученые: Авен О.И., Акиныпин Ю.С., Башарин Г.П.,Богусловский Л.Б., Журавлев Ю.П., Коган Я.А,, Штрик А.А. и др.

Быстрое совершенствование технологии производства ЭВМ и их компонент приводит к тому, что многие методы и алгоритмы обработки информации, еще вчера применявшиеся только в высокопроизводительных или специализированных ЭВМ, сегодня находят все более широкое применение в массовых ЭВМ общего назначения. Появляются возможности использования новых принципов обработки данных, в частности, предварительной выборки и буферирования команд, прогнозирования адресов переходов, конвейерной обработки и т.п. Целесообразность использования этих принципов, требующих дня своей реализации определенных затрат, должна быть обоснована уже на ранних этапах проектирования. Это требует разработки, исследования и использования в практике проектирования средств вычислительной техники моделей распараллеливания процессов выборки команд и их выполнения. Этим вопросам посвящены многие работы таких ученых, как Артамонов Г.Т., Брехов О.М., Ломов Ю.С., Майоров С.А., Новиков Г.И. и др. Эффективное использование таких моделей требует знания статистических данных о характеристиках потоков команд. Для некоторых отдельных случаев данные подобного рода приводятся в работах Журавлева Ю.П., Максимея И.В., Кошма-на Е.А., Окороченко Г.Е. Однако потоки команд и операндов в ЭВМ общего назначения исследованы недостаточно подробно, особенно в целях повышения уровня проектирования ЭВМ. Отсутствуют также детально разработанные и приспособленные для практического использования модели предварительной выборки и конвейерной обработки команд.

Поэтому разработка методов анализа потоков команд и операндов, получения представительных статистик о характеристиках этих потоков, разработка моделей конвейерной обработки команд, позволяющих обоснованно выбирать структуру и параметры устройств предварительной выборки в ЭВМ общего назначения, являются актуальными.

Цель работы. Диссертационная работа посвящена вопросам анализа и оценки эффективности способов предварительной выборки и конвейерной обработки команд, разработке и исследованию методов и моделей позволяющих обоснованно выбирать структуру и параметры устройств предварительной выборки на основе данных о характеристиках потоков команд, оперативной памяти и процессора.

Методы исследования. Теоретической основой проведенных исследований являются методы математической статистики, теории вероятностей, теории марковских цепей и случайных процессов. Для проверки теоретических выводов и получения экспериментальных данных использовались имитационное моделирование, аппаратные и программные средства измерений характеристик реальных ЭВМ.

Научная новизна. Разработаны методы получения и классификации информации о характеристиках потоков команд. Разработаны и исследованы модели процессов обработки команд в процессоре с предварительной выборкой и при конвейерной организации вычислений. Исследовано влияние команд перехода на производительность процессора и предложен способ реализации одного из алгоритмов прогнозирования адресов переходов. На основе предложенных моделей получены и проанализированы зависимости, позволяющие оценивать эффективность различных способов организации обработки информации в системе "процессор-оперативная память".

Дтэдчедзая ,ЗД5ШМост;ь И реадзавдя резудьтздор рабозд. Разработана методика, алгоритмы и программы для получения характеристик потока команд реальных программ по динамическим трассам команд. Разработаны модели и получены зависимости, позволяющие обоснованно выбирать значения параметров буфера команд и оценивать возможные границы значений выигрыша в производительности процессора от использования конвейерной обработки команд. Разработано устройство выборки команд с прогнозированием адресов переходов. Предложенное техническое решение признано изобретением. Результаты диссертации использованы в процессе разработки ЭВМ общего назначения, а также при проведении научно-исследовательских работ по проблемам развития ЕС ЭВМ.

Апробация паботы. Основные результаты диссертационной работы обсуждены на республиканских научно-технических конференциях по проблемам создания и совершенствования технических и программных средств ЕС ЭВМ (Шнек, 1977, 1982 гг.), на Всесоюзном совещании "Высокопроизводительные вычислительные системы" (Тбилиси,

I981 г.).

Публикации. По материалам диссертационной работы опубликовано 6 печатных работ.

Стшктгоа и объем работы. Диссертация состоит из введения, пяти глав и заключения, изложенных на 114 страницах машинописного текста, 58 страницах рисунков, 35 страницах таблиц, и списка использованной литературы, включакщего 63 наименования.

Основные результаты работы сводятся к следующим:

1. Обоснована необходимость использования статистических моделей процессов обработки данных для получения оценок эффективности методов распараллеливания этапов выполнения команд, выбора алгоритмов и параметров устройств предварительной выборки, буфе-рирования и конвейерной обработки команд.

2. Предложены и проанализированы модели потоков форматов команд и обращений к памяти за командами. На основе предложенных методов обработки данных о потоках команд и их классификации изучены основные характеристики потоков. Показано, что при моделировании процессов предварительной выборки команд в большинстве практических случаев можно использовать независимые модели потоков команд.

3. Разработаны аналитические модели для оценки влияния алгоритмов выборки команд из оперативной памяти, параметров памяти и процессора на производительность процессора при марковской и независимой моделях потоков форматов команд. Показано, что при существенных затратах времени на предварительную выборку команд предпочтительнее применять алгоритм использования полезного остатка. Приведены оценки границ применимости различных алгоритмов выборки команд из оперативной памяти.

4. Разработаны аналитические модели работы процессора с буфером команд. Показано, что введение буфера команд небольшой емкости позволяет до 15-20 % повысить производительность процессоpa ЭВМ общего назначения средней производительности. Выигрыш существенно увеличивается при уменьшении вероятности нарушения адресной последовательности команды.

5. Проанализированы методы увеличения эффективности процессоров с буферированием команд. Разработаны аналитические модели конвейерной обработки команд, обеспечивающие получение оценок возможного выигрыша в номинальной производительности процессора. Предложена реализация процессора с прогнозированием адресов переходов. Показано, что при циклическом характере выполняемых программ процессор с прогнозированием адресов переходов требует меньших аппаратных затрат и эффективнее процессора с несколькими буферами команд.

6. Разработана имитационная модель процессов обработки команд, использующая реальные динамические трассы команд, получаемые с помощью программного монитора. Проведенное сопоставление данных имитационного моделирования с результатами расчета, полученными с помощью разработанных в диссертации аналитических моделей, свидетельствует о высокой точности оценок, получаемых с помощью этих моделей. Трассовая имитационная модель может использоваться для решения разнообразных задач проектирования ЭВМ.

1. Материалы 26-го съезда КПСС. - М.: Политиздат, 1981. - 223 с.

2. Авен О.И., 1>рин Н.Н., Коган Я.А. Оценка качества и оптимизация вычислительных систем. М.: Наука, 1982. - 464 с.

3. Артамонов Г.Т., Брехов О.М. Аналитические вероятностные модели функционирования ЭВМ. М.: Энергия, 1978. - 368 с.

4. А.с. 545990 (СССР). Устройство дня сбора и регистрации данных о работе узлов электронной вычислительной машины/ Флеров А.Б., Аскерко Л.Ф., Кирьянова Н.И., Николаева Г.В.

5. Башарин Г.П., Богусловский Л.Б., Штейнберг В.И. Анализ конфликтов в общей памяти мультипроцессорных систем. Автоматика и вычислительная техника, 1980, $ 6, с. 27-32.

6. Вензель Е.Ф. Разработка и исследование приближенного метода анализа вычислительных систем. Дис. на соиск. ученой степ, канд. техн. наук, Минск, 1984.

7. Гарбер К.Д. Исследование комплексной производительности моделей ЭВМ Единой системы "Ряд-1". В сб.: Автоматика и вычислительная техника. Мн., 1981, вып. II, с. 94-99.

8. ГОСТ 16325-76. Машины вычислительные электронные цифровые общего назначения. Общие технические требования.

9. Деннинг П., Грейам Г. Управление памятью в режиме мультипрограммирования. ТИИЭР, 1975, т. 63, JS 6, с. II5-I33.

10. Джонсон Н., Лион Ф. Статистика .и планирование экспериментав технике и науке: Методы обработки данных. М.: Мир,1980.-610 с.

11. ЕС ЭВМ. Программа измерения времен выполнения команд и производительности. Ц50.094.ЮЗ Д1.

12. Журавлев Ю.П., Акиньшин Ю.С. Системное проектирование памяти ЦВМ. М.: Советское радио, 1976. - 344 с.

13. Иванченко Ю.И. Аналитическая модель процесса выборки команд из оперативной памяти ЭВМ. В кн.: Тез. докл. научно-технической конференции "Проблемы создания и совершенствования технических и программных средств ЕС ЭВМ", Мн., 1977,с. 37-38.

14. Иванченко Ю.И., Курьянова Н.И. Вопросы организации иерархической памяти мультипроцессорных вычислительных систем.

15. В кн.: Тез. докл. Всесоюзного совещания "Высокопроизводительные вычислительные системы", ч. I, М., 1981, с. 64-66.

16. Иванченко Ю.И., Сигалов Г.Г. Модель работы процессора с буфером команд. В сб.: Вопросы радиоэлектроники. Сер. ЭВТ, 1982, вып. 13, с. 76-82.

17. Иванченко Ю.И., Сигалов Г.Г., Смирнова Т.Ф. Исследование алгоритмов динамического распределения памяти. В сб.: Автоматика и вычислительная техника. Мн., 1981, вып. II, с. 86-90.

18. Исследование информационных потоков с целью повышения эффективности ЭВМ 3-го поколения. Отчет по НИР $ 1470;

19. ГР У20621; Инв. № Г50171. Шнек, 1976. - 277 с.

20. Исследование и разработка принципов развития технических и программных средств систем обработки данных ЕС ЭВМ "Ряд-3".-Отчет по НИР J& 2410; № IP Г66637; Инв. № Г66637. Шнек, 1978. - 246 с.

21. Катцан Г. Вычислительные машины системы 370. М.: Мир, 1974. - 240 с.

22. Качков В.П., Кондратьев А.П., Ленкова В.М., Ростовцев И.К., Смирнов Г.Д. Электронная вычислительная машина EC-I022. -М.: Статистика, 1979. 208 с.

23. Кошман Е.А. Исследование, разработка и автоматизация статистических методов оценки производительности вычислительных систем: Дис, на соиск. ученой степ. канд. техн. наук. М., 1979. - 193 с.

24. Кошман Е.А., Соловьев С.П. Оценка номинальной производительности универсальных ЭВМ. В сб.: Вопросы радиоэлектроники. Сер. ЭВТ, 1977, вып. 3, с. 60-70.

25. Кохонен Т. Ассоциативные запоминающие устройства. М.: Мир, 1982. - 384 с.25i Ломов Ю.С., Малыпаков В.Д. Анализ и оптимизация структуры процессора с совмещением команд. В сб.: Вопросы радиоэлектроники. Серия ЭВТ, 1976, вып. 5, с, 37-47.

26. Ломов Ю.С., Малярский Н.М., Почечуев Ю.А. Некоторые вопросы конвейерной организации обработки информации в ЭВМ. В сб.: Вопросы радиоэлектроники. Серия ЭВТ, 1982, вып. 16, с. 9- .

27. Майоров С.А., Новиков Г.И., Алиев Т.Н. и др. Основы теории вычислительных систем. М.: Высшая школа, 1978. - 408 с.

28. Майоров С.А., Новиков Г.И. Структура электронных вычислительных машин, Л.: Машиностроение, 1978. - 384 с.

29. Максимей И.В. Функционирование вычислительных систем (измерения и анализ). М.: Сов. радио, 1979. - 272 с.

30. Мойса Р.С., Реморова Р.А. Буферизация и частичное совмещение выполнения команд в микропрограммной ЭВМ. В сб.: Вопросы радиоэлектроники. Сер. ЭВТ, 1975, вып. II, с. 58-62.

31. Николаева Г.В. Разработка и исследование приближенных методов расчета характеристик моделей вычислительных систем: Дис. на соиск. ученой степ. канд. техн. наук. Мн., 1982.- 184 с.

32. Окороченко Г.Е. Исследование эффективности функционирования мультипрограммных ВС методом натурного измерения и моделирования: Дис. на соиск. ученой степ. канд. техн. наук. М., 1978. - 220 с.

33. Пржиялковский В.В. Сравнительный анализ оценок производительности различных ЭВМ. В сб.: Вопросы радиоэлектроники. Сер. ЭВТ, 1980, вып. 3, с. 3-12.

34. Пркиялковский В.В., Ломов Ю.С. Технические и программные средства Единой системы ЭВМ (ЕС ЭВМ-2). М.: Статистика, 1980. - 232 с.

35. Решение о выдаче авторского свидетельства от 27.10.83. Заявка .£ 3578919/18-24 от 11.04.83. Устройство предварительной выборки команд. Сигалов Г.Г., Люперсольский A.M., Иванченко Ю.И., Заблоцкий В.Н.

36. Сборник научных программ на ФОРТРАНе. Вып. 2. Матричная и линейная алгебра. М.: Статистика, 1974. - 224 с.

37. Сигалов Г.Г., Иванченко Ю.И. Оценка алгоритмов выборки команд из оперативной памяти ЭВМ. В сб.: Вопросы радиоэлектроники. Сер. ЭВТ, 1980, вып. II, с. 66-73.

38. Синюкова Л.Ф., Штрик А.А. Оценка потерь производительности многопроцессорных комплексов при конфликтах в секционированной общей памяти. Автоматика и телемеханика, 1978, № 10, с. 192-199.

39. Феррари Д. Оценка производительности вычислительных систем.-М.: Мир, 1981. 576 с.

40. Штаркман B.C. Сравнительный анализ транслятора ГОРЕХ. Препринт Института прикладной математики АН СССР, 1978, IS 129.

41. Anderson D.W. ХВМ System 360 Model 91, machine philosophy and instruction handling.-IBM J. Res. Dev.,1967,v.11,No.1,p. 8-24.

42. Chow O.K. On optimization of storage hierarchies. IBM J. Res. and Devel.,1974,v.18,No.3,p.194-203.

43. Chu W.W.,Opderbeck H. Analisys of the PEP replacement algorithm via a semimarkov model.- Comm. of the ACM,1976,v.19, No.5,p.298-304.

44. Chu W.W.,Opderbeck H. Perfomance of replacement algoritms with different page sizes.-Compute,1974,No.11,p.14-21.

45. Coffman E.G.,Denning P.J. Operating System theory.N.У., P.H.,1973.

46. Denning P.J. The working set model for program behavior. Comm. of the ACM,1968,v.11,No.5,p.323-333.

47. Flynn M.J. Some Compute organizations and their effectiveness.-IEEE Trans, on Comput.,1972,v.C-21,No.9,p.948-960.

48. Franklin M.A.,Gupta R.K. Computation of page fault probability from program transition diagram.-Comm. of the ACM, 1974,v.17,No.4,p. 186-191.

49. Gecsei J. Determining hit ratios for multilevel hierarchies. IBM J. Res. Devel.,1974,v.18,No.4,p.316-327.

50. Gecsei J., Lukes J.A. A model for the evaluation of storage hierarchies.- IBM Syst. J.,1974,v.13,No.2,p.163-178.

51. Geist R.M., Trivedi K.S. Optimal design of multilevel storage hierarchies.- IEEE Trans, on Comput.,1982,v.C-31,No.3,p.248-260.

52. Hartigan J.A.,Wong M.A. A K-means clustering algorithm.-Applied statist.,1979,v.28,No.1,p.100-108.55» Kaneko Т. Optimal task swiching policy for a multilevel storage system,- IBM J. Res, and Devel,,1974»v,18,No,4f p.310-315.

53. Kaplan K.R., Winder R.O. Cache-based compute systems.-Compute,1973,v.6,No.3,p.30-36.

54. Pat. 4 200 927. US.Int. CI. G 06 f 9/00. Multi-instruction stream branch processing mechanism.

55. Rao G.S. Performance analysis of cache memories.- J.of the ACM,1978,v.25,No.3,p.378-395.

56. Smith A.J. Characterizing the storage process and its effect on the update of main memory by write-through.- J. of the ACM,1979,v.26,No.1,p.6-27.

57. Smith A.J. On the effectiveness of set associative page mapping and its application to main memory management.-In: "2-nd International Conference Software Engineering. 1976".N.Y.,1976,p.286-292.

58. Smith J.E. A stady of branch prediction strategies.- In: "International Symposium on Compute Architecture,8-th, 1981 p.135-148.

59. Trivedi K.S. Designing linear storage hierarchies so as to maximize reliability subject to cost and performance constraints.- In: "International Symposium on Compute Architecture ,7-th,1980",p.211-217.

60. Trivedi K.S.,Sigmon T.M. Optimal design of linear storage hierarchies.- J. of the ACM,1981,v.28,No.2,p.270-288.