Результаты экспериментального исследования эффективности кэш-памяти микропроцессорных систем на основе имитационного моделирования

РЕЗУЛЬТАТЫ ЭКСПЕРИМЕНТАЛЬНОГО ИССЛЕДОВАНИЯ ЭФФЕКТИВНОСТИ КЭШ-ПАМЯТИ МИКРОПРОЦЕССОРНЫХ СИСТЕМ НА ОСНОВЕ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ

Рассматриваются различные подходы к моделированию микропроцессорных систем, которые широко используются в вычислительных системах и комплексах. Проектирование высокопроизводительных процессоров является сложной задачей и требует предварительной верификации и анализа полученных данных на уровне моделей, для чего обычно используется аналитическое и имитационное моделирование. Достоинством аналитических моделей является их высокая гибкость. Однако аналитическое моделирование параллельных вычислительных систем является довольно сложным, поскольку представление подобных систем в виде цепей Маркова основанных на вероятностном подходе является довольно громоздкой задачей, а модели на основе сетей массового обслуживания обычно не достигают желаемой точности. В качестве объекта исследования рассматривается топология, в которой все процессоры располагаются на общей системной шине. Разработка многопараметрической имитационной модели многопроцессорной системы для оценки эффективности работы алгоритмов кэш-памяти и оптимизации ее структуры является актуальной задачей, поскольку оптимизация структуры и алгоритмов работы кэш-памяти позволяет ускорить взаимодействие процессора с памятью и, таким образом, повысить производительность всей системы. Приводится схема имитационной модели кэш-памяти мультипроцессора и описание ее реализации. Представлены зависимости производительности системы от разных способов организации кэш-памяти, полученные в результате моделирования. На основании анализа результатов имитационного моделирования показано, что эффективность работы многопроцессорной системы с кэш-памятью зависит не только от параметров кэш-памяти и выбранного алгоритма замещения, но и от класса решаемой задачи. Ветвящиеся программы с большим числом условных переходов, зависящих от случайных входных данных, дают неплохие результаты практически с любыми алгоритмами замещения. Программы, которые имеют большое число повторяющихся участков, например, часто вызываемых подпрограмм и/или циклов при прочих равных условиях обеспечивают более высокую эффективность использования кэш-памяти, чем ветвящиеся программы. Особенно сильно это проявляется при увеличении числа задействованных ячеек кэш-памяти.

Информация об авторах:

Толмачев Валерий Вячеславович, к.т.н., преподаватель Военно-космической академии имени А.Ф. Можайского, г. Санкт-Петербург, Россия

Булах Сергей Сергеевич, курсант Военно-космической академии имени А.Ф. Можайского, г. Санкт-Петербург, Россия Клычков Иван Александрович, курсант Военно-космической академии имени А.Ф. Можайского, г. Санкт-Петербург, Россия

Для цитирования:

Толмачев В.В., Булах С.С., Клычков И.А. Результаты экспериментального исследования эффективности кэш-памяти микропроцессорных систем на основе имитационного моделирования // T-Comm: Телекоммуникации и транспорт. 2017. Том 11. №11. С. 41-47.

For citation:

Tolmachev V.V., Bulach S.S., Klychkov I.A.

Толмачев Валерий Вячеславович,

Военно-космическая академия имени А.Ф. Можайского, г. Санкт-Петербург, Россия, pim_tolm@mail.ru

Булах Сергей Сергеевич,

Военно-космическая академия имени А.Ф. Можайского, г. Санкт-Петербург, Россия

Ключевые слова: эксперимент, имитационное моделирование, многопроцессорные системы, вычислительные системы, вычислительные комплексы, модель, оптимизация, кэш-память; эффективность кэш-памяти, число процессоров, число уровней кэш-памяти, емкость кэш-памяти, протокол когерентности кэш-памяти, алгоритм замещения строк.

Клычков Иван Александрович,

Военно-космическая академия имени А.Ф. Можайского, г. Санкт-Петербург, Россия

7Т>

Введение

В настоящее время разработчики процессоров создают конвейерные и суперскалярные архитектуры, поскольку на микросхему можно помещать все больше и больше транзисторов, что еще больше увеличивает быстродействие процессоров. Разработчики памяти обычно используют новые технологии для увеличения ее емкости, а не быстродействия. При этом разрыв в быстродействии процессора и памяти увеличивается. Для обеспечения быстродействия памяти ее необходимо размещать прямо на микросхеме процессора, поскольку информация через шину поступает очень медленно. Однако размещение памяти большого объема на микросхеме процессора увеличивает его размеры и как следствие стоимость. При этом существуют ограничения на размеры создаваемых процессоров, Применение многоуровневой кэш-памяти наряду с усовершенствованием алгоритмов прогнозирования ветвлений является эффективным средством повышения производительности современных многоядерных процессоров [1]. В настоящее время проводится множество исследований, целью которых является усовершенствование алгоритмов прогнозирования ветвлений. В связи с этим, для многопроцессорных вычислительных систем и комплексов повышение эффективности использования памяти является весьма актуальной задачей.

Проектирование высокопроизводительных процессоров является сложной задачей и требует предварительной верификации и анализа полученных данных на уровне моделей, для чего обычно используется аналитическое и имитационное моделирование [2, 3]. Достоинством аналитических моделей является их высокая гибкость. Однако аналитическое моделирование параллельных вычислительных систем является довольно сложным, поскольку представление подобных систем в виде цепей Маркова основанных на вероятностном подходе является довольно громоздкой задачей, а модели на основе сетей массового обслуживания (СМО) обычно не достигают желаемой точности.

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

Постановка задачи

В качестве первоначального объекта исследований рассмотрим простейшую топологию; все процессоры располагаются на общей системной шине. Общая структура моделируемой многопроцессорной системы представлена на рис. 1.

Зависимость между орг анизацией кэш-памяти и производительностью системы целесообразно представить в виде некоторой функции С? = /(У), где У - вектор входных параметров модели, которые представляют собой характеристики многопроцессорной системы, С - вектор выходных

параметров, которые характеризуют эффективность системы. В свою очередь вектор У можно представить, как объединение двух множеств параметров:

¥ = Г1Ц¥2,(Г1Г[¥2=0),

где >'| - множество аппаратных характеристик системы, а У-) — множество случайных величин, которые представляют собой параметры моделирования.

В качестве аппаратных характеристик рассмотрим вектор из 11 параметров:

К] =|и, к, vKnu, von, С, R, М, A, tK3lu, ton, fj^j.

где п - число процессоров; к - число уровней кэш-памяти; УКЭШ - емкость кэш-памяти первого уровня (LIS); Vqjj -емкость оперативной памяти; С - используемый протокол когерентности кэш-памяти (Write once, Synapse, MSI, MF.SI, MORS!); R — используемый алгоритм замещения строки контроллером кэш-памяти (FIFO, LRU, LFU , Random); M — используемый алгоритм согласования содержимого основной и кэш-памяти (алгоритмы сквозной записи, обратной записи и обратной записи с флагом); А - алгоритм отображения основной памяти на кэш, который характеризуется ассоциативностью кэш-памяти; tKm¡ - время чтения/записи

в кэш-память; Íq[j- время доступа к оперативной памяти (в

пересчете на такты процессора); t — время поиска указала

теля в кэш-памяти.

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

При возникновении кэш-промаха контроллер кэш-памяти должен выбрать подлежащую замещению строку. Д|я решения этой задачи используется набор правил, который называется алгоритмом замещения: FIFO (первый пришедший выбывает первым); LRU (дольше всего не использовался); LFU (реже других использовался); Random (случайное

Основная память

Рис. 1. Общая структура многопроцессорной системы

замещение). Для большинства задач наиболее подходит алгоритм обработки элемента, который дольше всего не использовался (LRU), то есть удаляется тот элемент, который находится в конце списка.

Архитектура ассоциативности кэша определяет способ, при помощи которого данные из оперативного запоминающего устройства (ОЗУ) отображаются в кэше. Существуют следующие основные варианты архитектуры ассоциативности кэширования: кэш с прямым отображением - определенный участок кэша отвечает за определенный участок ОЗУ; полностью ассоциативный кэш - любой участок кэша может ассоциироваться с любым участком ОЗУ; смешанный кэш (наборно-ассоциативный). На различных уровнях кэша обычно могут использоваться различные архитектуры ассоциативности кэша. Кэширование с прямым отображением ОЗУ является самым быстрым вариантом кэширования, поэтому эта архитектура обычно используется для кэшей большого объема. 1* свою очередь, полностью ассоциативный кэш обладает меньшим количеством ошибок кэширования (промахов).

Для согласования содержимого кэш-памяти и оперативной памяти используют три метода записи: сквозная запись (write through) - одновременно с кэш-памятью обновляется оперативная память; буферизованная сквозная запись (buffered write through) - информация задерживается в кэш-буфере перед записью в оперативную память и переписывается в оперативную память в тс циклы, когда процессор к ней не обращается; обратная запись (write back) - используется бит изменения в поле тега, и строка переписывается в оперативную память только в том случае, если бит изменения рааеи 1. Как правило, все методы записи, кроме сквозной, позволяют откладывать и группировать операции записи в оперативную память для увеличения производительности.

В качестве параметров моделирования рассматривается вектор, состоящий из 4 элементов:

^ 2 = {п • ^чтеч - ¡мод}' где Рзап - вероятность того, что в очередной такт процессор сгенерирует запрос к памяти; Рнтен ~ вероятность того,

что это будет запрос на чтение; S - отклонение следующего адреса запроса по отношению к предыдущему (с целыо соблюдения принципа локальности используем нормальное распределение); tМО(у - время моделирования, то есть число

тактов, которые должен выполнить процессор.

В качестве показателей эффективности системы принят вектор, состоящий из трех параметров:

G = у цикл* р

где ttlllKJJ ~ среднее время обмена данными с памятью,

р - загрузка системы, h - коэффициент кэш-попаданий.

Проектируемая система позволяет моделировать поведение многопроцессорной системы с характеристиками Y\ в

среде с параметрами Y-, и как результат моделирование позволяет получить вектор характеристик эффективности G

Система считается наиболее эффективной, если среднее время обмена данными с памятью стремится к сумме времени чтения/записи в кэш-память и времени поиска указателя

в кэш-памяти, то есть / —»I / +/ V а загрузка сис-'цикл у кэш ' ук} '

темы и коэффициент кэш-попаданий стремятся к единице (р —^ 1 и й->1).

Рис. 2, Структура имитационной модели

Общая структура имитационной модели

Имитационная модель реализована как многопотачное приложение, структура которой представлена на рис. 2 и она легко может быть перенесена на распределенную архитектуру.

Сама имитационная модель состоит из N потоков, моделирующих процессоры, N потоков для моделирования их кэш-контроллеров и кэш-памяти, единственного потока для системной шины и потока «монитора процессоров». Таким образом, для моделирования мультипроцессора с N ядрами требуется 2N + 2 потоков; отдельный поток реализует интерфейс пользователя.

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

Эффективность работы многопроцессорной системы с кэш-памятью будет зависеть не только от параметров кэшпамяти и выбранного алгоритма замещения, по и от класса решаемой задачи, реализованной с помощью программного кода. Для этого разработаны блок-схемы алгоритмов для двух программ. I !ервая программа реализует разветвляющий процесс, разветвление в котором зависит от исходных данных, а алгоритм использует команды условной передачи управления. Во второй иро1рамме, используется подпрограмма для экономии памяти, за счет сокращения многократно повторяющейся последовательности команд.

T-Comm Vol. 11. #11-2017

У

У

T-Comm Vol. 11. #11-2017

Выводы

Анализ результатов имитационного моделирования показал, что эффективность работы многопроцессорной системы с кэш-памятью зависит не только от параметров кэш-памяти и выбранного алгоритма замещения, но и от класса решаемой задачи. Ветвящиеся программы с большим числом условных переходов, зависящих от случайных входных данных, дают неплохие результаты практически с любыми алгоритмами замещения. 11рограммы, которые имеют большое число повторяющихся участков, например, часто вызываемых подпрограмм и/или циклов при прочих равных условиях обеспечивают более высокую эффективность использования кэш-памяти, чем ветвящиеся программы. Особенно сильно это проявляется при увеличении числа задействованных ячеек кэш-памяти.

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

Литература

!. Таненбаум Э„ Остин Т. Архитектура компьютера. 6-е им. СПб.: Питер. 2013.816 с.

2. O.E. Suh. S. Devadas, and L. Rudolph, Analytical Cache Models with Application to Cache Partitioning. Proceedings of the 15th Internal i onal Conference on Supercomputing, June 2001.

3. K. Skadron. P.S. Ahuja, M. Martonosi, und D.W. dark. Branch Prediction, Instruction-Window Size, and Cache Size: Performance Tradeoffs and Simulation Techniques. IliBII Transactions oti Computers, 48(11^1260-81, Nov. 1999.

4. Фельдман Л.П.. Дедищев В О. Математическое обеспечение САПР: Моделирование вычислительных и управляющих систем. К.: УМК ВО, 1992. 256 с.

5. Пом А„ Агравал О. Быстродействующие системы памяти: Пер. с англ, М: Мир. 1987.264 с,

6. Хрчпшнков A.C. Модели и алгоритмы распределения нагрузки. Модель коллектива вычислителей. Модели с соперником // Информационные технологии и вычислительные системы. №2. 2009. С,65-80,

7. Ким А.К.. Перекатов В.И., Ермаков С.Г. Микропроцессоры и вычислительные комплексы семейства «Эльбрус». СПб.: Питер, 2013.272 с.

8. Ким А.К.. Перекатов В.И., Сахин Ю.Х, Развитие и реализация архитектуры вычислительных комплексов серии «Эльбрус» для решения задач ракетно-космической обороны // Вопросы радиоэлектроники. Сер. ЭВТ. 2010. Вып.З.С. 5-17.

9. Исаев М.В.. Кожин A.C.. Костенко В.О.. Поляков Н.Ю., Сахин Ю.Х. Двух ядер пая гетерогенная система на кристалле «Элбрус-2С+» // Вопросы радиоэлектронике. Сер. ЭВТ. 2012. Вып.З. С. 42-52.

10. Моро з Я. И. Основные этапы и методы физического проектирования микропроцессора «Эльбрус-КС» // Вопросы радиоэлектроники. Сер. Э8Т,

2016. Вып.З.С. 38-47.

11. Жматн А.П. Архитектура ЭВМ: 2-ое и ш., перераб. и доп.: учеб. пособие. СПб.: БХВ-Петербург, 2010. 352 с.

12.ЮровВ И. Assembler, Спб.: Пигер, 2000.624 с.

13. Кожин A.C.. Нейман-зет М.И.. Тихорский В В. Влияние подсистемы памяти восьмнядерного микропроцессора «Эльбрус-ВС » на его производительность // Вопросы радиоэлектроники. 2017, №3. С. 13-21.

14. Орлов С.А.. Цияъкер Б.Я. Организация ЭВМ н систем: учебник .для вузов. 2-е изд. CI IG.: 11итср, 2011. 668 с.

15. Сорока Т.Е.. Фельдман Л.П.. Михайлова Т.В. Оценка эффективности алгоритмов работы кэш-памяти мультипроцессора с помощью имитационного моделирования И Моделювання та комп'ютериа граф1ка. Четверта м1жнародна вауково-техшчна конференшя. 5-8 жовтня 2011 р., Донецьк, Дон! 1 ГУ. 2011 С. 246-250.

16. Легкое К.Е.. Нестеренко O.E. Алгоритм формирования информационной структуры параллельных программ иерархической вычислительной системы // Наукоемкие технологии в космических исследованиях Земли,

2017. Т.9. № I. С, 52-59,

17. Буренин А.И.. Нестеренко O.E., Лединкин H.A., Легкое К.Е. Алгоритм оценивания целесообразности распараллеливания вычислительной задачи II Труды Северо-Кавказского филиала Московского технического университета связи и информатики. 2016. Т. I № 9, С, 68-71.

18. Буренин А Н., Легкое К.Е., Нестеренко О Е. Методический подход к организации обработки оперативной информации распределенными вычислительными комплексами специального назначения // Наукоемкие технологии в космических исследованиях Земли. 2016. Т. 8. № 6. С. 18-30.

19. Бурении А Н., Нестеренко O.E., Легкое К.Е., ЛеОянкчн H.A. Комплексный алгоритм оценивания целесообразности распараллеливания информационной структуры вычислительной задачи // Системы синхронизации, формирования и обработки сигналов. 2016. "Г. 7. №3. С. 12-16.

20. Ледянкин И.А., Легкое К.Е. С) некоторых концептуальных вопросах разработки параллельных струкгур вычислительных задач кластерных вычислительных систем // Наукоемкие технологии в космических исследованиях Земли. 2014. Т. 6. № 6. С. 30-38.

21. Зверев А.Б.. Легкое К.Е.. Нестеренко O.E. Направления совершенствования систем информационной поддержки обслуживающего персонала при технической эксплуатации систем специального назначения И Наукоемкие технологии в космических исследованиях Земли. 2014. Г. 6. Ks 6. С. 44-50.

T-Comm Том II. #11-20 17

COMPUTER SCIENCE

RESULTS OF EXPERIMENTAL STUDY OF CACHE-MEMORY EFFICIENCY OF MICROPROCESSOR SYSTEMS BASED ON IMITATION MODELING

Valery V. Tolmachev, Military Space Academy named after A.F. Mozhaisky, St-Peterburg Russia, pim_tolm@mail.ru Sergei S. Bulach, Military Space Academy named after A.F. Mozhaisky, St-Peterburg Russia Ivan A. Klychkov, Military Space Academy named after A.F. Mozhaisky, St-Peterburg Russia

Abstract

Various approaches to modeling of microprocessor systems that are widely used in computer systems and complexes are considered. Designing high-performance processors is a complex task and requires preliminary verification and analysis of the obtained data at the model level, which is usually done using analytical and simulation modeling. As a research object, a topology is considered in which all processors are located on a common system bus. Development of a multiparametric simulation model of a multiprocessor system for evaluating the efficiency of algorithms cache memory and optimization of its structure is an actual task, as optimization of the structure and algorithms of the cache memory allows to accelerate the interaction of the processor with memory and, thus, to increase the productivity of the entire system. The scheme of the simulation model of the cache memory of the multiprocessor and a description of its implementation are given. Dependencies of system performance on different ways of cache memory organization, obtained as a result of modeling, are presented. Based on the analysis of simulation results, it is shown that the performance of a multiprocessor system with a cache memory depends not only on the parameters of the cache and the chosen substitution algorithm, but also on the class of the problem being solved. Branching programs with a large number of conditional transitions, depending on random input data, give good results with almost any substitution algorithms. Programs that have a large number of repetitive areas, for example, often called subroutines and / or cycles, all other things being equal, provide better cache utilization than branching programs. This is especially true when the number of cache cells involved increases.

Keywords: experiment, simulation modeling, multiprocessor systems; computer systems, computer systems, model, optimization, cache memory, cache memory efficiency, number of processors, number of cache levels, capacity of the cache, cache coherency protocol, string substitution algorithm.

References

1. Tanenbaum E., Austin T. (2013). Computer architecture. 6th ed. St. Petersburg: Peter. 816 p. (In Russian).

2. Suh G.E., Devadas S., and Rudolph L. (2001). Analytical Cache Models with Application to Cache Partitioning. Proceedings of the 15th International Conference on Supercomputing, June 2001.

3. Skadron K., Ahuja P.S., Martonosi M. and Clark D.W. (1999). Branch Prediction, Instruction-Window Size, and Cache Size: Performance Tradeoffs and Simulation Techniques. IEEE Transactions on Computers, 48(II):I260-8I, Nov. 1999.

4. Feldman L.P., Dedischev V.O. (1992). Mathematical support of CAD: Modeling of computing and control systems. K.: UMK VO. 256 p. (In Russian).

5. Pom A., Agraval O. (1987). Fast-acting memory systems. Moscow: Mir, 1987. 264 p.

6. Khratankov A.S.

7. Kim A.K., Perekatov V.I., Ermakov S.G.

8. Kim A.K., Perekatov V.I., Sakhin Yu.Kh.

9. Isaev M.V., Kozhin A.S., Kostenko V.O., Polyakov N.Yu., Sakhin Yu.Kh.

10. Moroz Ya.N.

I I. Zhmakin A.P.

12. Yurov V.I. Assembler.

13. Kozhin A.S., Neiman-zade M.I., Tikhorskiy V.V.

14. Orlov S.A., Tsilker B.Ya.

15. Soroka T.E., Feldman L.P., Mikhailova T.V. (20II). Evaluation of the efficiency of cache algorithms of the multiprocessor using simulation. Simulation and computer graphics. Fourth international scientific and technical conference. October 5-8, 20II, Donetsk, DonNTU - 20II, pp. 246-250.

16. Legkov K.E., Nesterenko O.E.

17. Burenin A.N., Nesterenko O.E., Ledengin I.A., Legkov K.E.

18. Burenin A.N., Legkov K.E., Nesterenko O.E.

19. Burenin A.N., Nesterenko O.E., Legkov K.E., Ledengin I.A.

20. Ledengin I.A., Legkov K.E.

21. Zverev A.B., Legkov K.E., Nesterenko O.E.

Information about authors:

Valery V. Tolmachev, PhD, lecturer of the Military Space Academy named after A.F. Mozhaisky, St-Peterburg, Russia

Sergey S. Bulach, cadet of the Military Space Academy named after A.F. Mozhaisky, St-Peterburg, Russia Ivan A. Klychkov, cadet of the Military Space Academy named after A.F. Mozhaisky, St-Peterburg, Russia

r i >