Структурные решения и методы аппаратной компрессии данных в подсистеме памяти многоядерных процессоров общего назначения тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Сурченко Александр Викторович

• Сурченко Александр Викторович
• кандидат наук
• 2024

Оглавление диссертации кандидат наук Сурченко Александр Викторович

Введение

Глава 1. Выбор направления научного исследования

1.1. Введение

1.2. Производительность вычислительных систем

1.3. Роль подсистемы памяти в производительности вычислительных систем

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

Глава 2. Обзор и анализ существующих подходов

2.1. Введение

2.2. Алгоритмы аппаратной компрессии данных

2.2.1. Frequent Value Compression

2.2.2. Frequent Pattern Compression

2.2.3. C-Pack

2.2.4. Base-Delta-Immediate

2.2.5. Выводы

2.3. Увеличение эффективного объёма кэша при использовании в нем компрессии данных

2.3.1. Compressed Cache и Frequent Value Cache

2.3.2. Variable Segment Cache

2.3.3. Zero-Content Cache

2.3.4. Base-Delta-Immediate Cache

2.3.5. Decoupled Compressed Cache и Skewed Compressed Cache

2.3.6. Base-Victim Compression Cache

2.3.7. Выводы

2.4. Увеличение пропускной способности каналов передачи данных за счёт использования компрессии данных

2.4.1. Использование статического справочника в контроллере шины

2.4.2. Использование статического справочника для каждого абонента шины

2.4.3. Использование справочников для пары отправитель-приёмник

2.4.4. Выделение типов локальности передаваемых данных

2.4.5. Особенности передачи сжатых данных по сети-на-кристалле

2.4.6. Применение справочников с часто встречающимися значениями к сети-на-кристалле

2.4.7. Содержание справочников для отдельных направлений передачи

2.4.8. NoA: использование в сети-на-кристалле алгоритма компрессии на основе слабо отличающихся значений

2.4.9. DISCO: перенос компрессии из устройств в коммутаторы

2.4.10. Выводы

2.5. Увеличение эффективного объёма оперативной памяти при использовании аппаратной компрессии данных

2.5.1. IBM MXT

2.5.2. Устранение основных недостатков IBM MXT

2.5.3. Linearly Compressed Pages

2.5.4. MemZip

2.5.5. CRAM

2.5.6. Compresso

2.5.7. Qualcomm Centriq

2.5.8. Выводы

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

Глава 3. Теоретические результаты работы

3.1. Введение

3.2. Алгоритм аппаратной компрессии BAI*-HL

3.2.1. Упрощённая версия BAI: алгоритм компрессии B+Д

3.2.2. Алгоритм компрессии BAI

3.2.3. Модификация для упрощения вычислений: алгоритм компрессии BAI* (BAI Modified)

3.2.4. Поддержка сжатия до половинного размера: итоговый алгоритм компрессии BAI*-HL

3.3. Структурные решения для увеличения эффективного объёма кэш-памяти за счёт аппаратной компрессии данных

3.3.1. Структура кэш-памяти последнего уровня в современных процессорах архитектуры «Эльбрус»

3.3.2. Предлагаемые структурные решения для поддержки увеличения эффективного объёма кэш-памяти

3.3.3. Модификация логики записи и чтения кэш-строк

3.3.4. Особенности выдачи данных чтения из кэш-памяти с поддержкой компрессии данных

3.4. Метод размещения данных в кэш-памяти с поддержкой аппаратной компрессии данных

3.4.1. Алгоритм размещения и вытеснения в кэш-памяти последнего уровня современных процессоров архитектуры «Эльбрус»

3.4.2. Дополнительные действия при работе алгоритма размещения и

вытеснения данных в рамках предлагаемого метода

3.4.3. Поддержка целостности данных в ходе транзакций, имеющих доступ к одной и той же ячейке памяти данных

3.5. Метод увеличения пропускной способности каналов передачи данных

3.5.1. Рассматриваемая конфигурация сети

3.5.2. Предлагаемый метод

3.5.3. Дополнительные оптимизации передачи данных

Глава 4. Практические результаты работы

4.1. Введение

4.2. Алгоритм аппаратной компрессии BAI*-HL

4.2.1. Инструментарий исследования

4.2.2. Сравнение алгоритмов B+Д и BAI с прочими алгоритмами с быстрой декомпрессией

4.2.3. Алгоритмы с модифицированным вычислением B+Д* и BAI* и их сравнение с базовыми алгоритмами B+Д и BAI

4.2.4. Характеристики алгоритма BAI*-HL

4.2.5. Результаты синтеза реализаций алгоритмов BAI, BAI* и BAI*-HL

4.3. Структурные решения и метод размещения данных для увеличения эффективного объёма кэш-памяти при использовании аппаратной компрессии

данных

4.3.1. Инструментарий исследования

4.3.2. Оценка эффективности предлагаемых структурных решений и метода размещения данных на модели процессора

4.3.3. Оценка эффективности предлагаемых структурных решений и метода размещения данных на FPGA-прототипе процессора

4.3.4. Результаты синтеза кэш-памяти с поддержкой аппаратной

компрессии данных

4.4. Метод увеличения пропускной способности каналов передачи данных

4.4.1. Инструментарий исследования

4.4.2. Теоретическая оценка эффекта аппаратной компрессии на межпроцессорные каналы связи

4.4.3. Влияние аппаратной компрессии данных на пропускную способность сети-на-кристалле

4.4.4. Влияние аппаратной компрессии данных на пропускную способность межпроцессорных каналов связи

Заключение

Список сокращений и условных обозначений

Список литературы

Список иллюстраций

Список таблиц

Приложение А (Свидетельство о государственной регистрации программы для ЭВМ)

Приложение Б (Акты внедрения)

Введение

Введение диссертации (часть автореферата) на тему «Структурные решения и методы аппаратной компрессии данных в подсистеме памяти многоядерных процессоров общего назначения»

Актуальность работы

В настоящее время при разработке процессоров общего назначения наблюдается тенденция к повышению числа процессорных ядер с целью увеличения производительности системы.

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

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

Одной из оптимизаций, рассматриваемых научным сообществом в рамках повышения пропускной способности подсистемы памяти многоядерных процессоров, является аппаратная компрессия данных. Ее использование позволяет достичь увеличения пропускной способности памяти за счёт двух факторов:

• уменьшения объёма данных, передаваемых в каналах подсистемы памяти;

• более компактного хранения данных в том же объёме памяти.

Традиционные методы компрессии, такие, как алгоритмы семейства LZ

(Лемпель-Зив) [1][2][3] или алгоритм Хаффмана [4][5][6], предназначены для работы с файлами, где не предъявляется строгих требований к задержке, вносимой компрессией и декомпрессией, а доступ в память осуществляется в основном последовательно. В то же время в подсистеме памяти доступ к данным осуществляется преимущественно случайным образом, а требования по времени доступа существенно строже. В связи с этим традиционные методы становятся неприменимыми, и потому при реализации аппаратной компрессии данных необходима разработка новых алгоритмов и методов, учитывающих более жёсткие требования.

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

Степень разработанности темы исследования

Работы, посвящённые аппаратной компрессии данных в подсистеме памяти процессоров общего назначения, можно разделить на несколько направлений исследований:

• алгоритмы аппаратной компрессии данных (работы Yang J., Zhang Y. и Gupta R., Alameldeen A. и Wood D., Chen X., Pekhimenko G. и др.);

• структурные решения и методы увеличения эффективного объёма кэшпамяти за счёт аппаратной компрессии данных (работы тех же учёных, а также Dusser J., Sardashti S., Gaur J. и др.);

• методы аппаратной компрессии при передаче данных (работы Kant K. и Iyer R., Liu C., Yang J., Thuresson M., Das R., Jin Y., Zhou P., Zhan J., Pekhimenko G. и др.);

• структурные решения и методы аппаратной компрессии данных в оперативной памяти (работы Tremaine R., Abali B., Ekman M. и Stenstrom P., Pekhimenko G., Shafiee A., Young V., Choukse E. и др.);

• обеспечение защиты информации при использовании аппаратной компрессии данных (работа Tsai P. и др.).

Цели и задачи исследования

Объектом исследования является подсистема памяти многоядерных процессоров общего назначения на примере процессоров с архитектурой «Эльбрус». Предметом исследования является её производительность при

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

Целью диссертационной работы является разработка структурных решений и методов аппаратной компрессии данных для повышения производительности подсистемы памяти многоядерных процессоров общего назначения. В соответствии с этой целью определены основные задачи диссертационного исследования:

• Анализ существующих решений, предлагаемых для реализации аппаратной компрессии данных в подсистеме памяти процессоров общего назначения, выявление их недостатков.

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

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

о разработка структурных решений, позволяющих увеличить эффективный объём памяти без введения дополнительных структурных элементов в устройства хранения данных в подсистеме памяти;

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

подсистеме памяти; o разработка метода увеличения пропускной способности каналов передачи данных большой ширины с политикой управления потоком wormhole за счёт аппаратной компрессии передаваемых данных.

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

• Внедрение полученных в диссертационной работе результатов в разработках многоядерных процессоров общего назначения архитектуры «Эльбрус».

Научная новизна

Решение поставленных в диссертационной работе задач определяет научную новизну исследования, заключающуюся в следующем:

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

• Разработаны структурные решения, позволяющие увеличить эффективный объём NCID-кэш-памяти (Non-inclusive Cache, Inclusive Directory) [7] при использовании аппаратной компрессии данных без введения дополнительных структурных элементов.

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

• Предложен метод увеличения пропускной способности сети-на-кристалле

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

Теоретическая и практическая значимость работы

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

Практическая значимость работы заключается в разработке структурных решений и методов, повышающих пропускную способность подсистемы памяти и производительность процессоров общего назначения на примере процессоров архитектуры «Эльбрус». Результаты, полученные в диссертационной работе, внедрены при разработке процессоров архитектуры «Эльбрус» в АО «МЦСТ», использованы в ходе обоснования технических решений по реализации разработок ПАО «ИНЭУМ им. И.С. Брука», а также внедрены в учебный процесс кафедры информатики и вычислительной техники МФТИ и кафедры управляющих ЭВМ «РТУ МИРЭА».

Методология и методы исследования

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

Положения, выносимые на защиту

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

2. Структурные решения, позволяющие увеличить эффективный объём КСГО-кэш-памяти с поддержкой аппаратной компрессии данных за счёт утилизации освободившегося после компрессии данных пространства.

3. Метод размещения данных в КСГО-кэш-памяти с поддержкой аппаратной компрессии на основе разработанных структурных решений по увеличению эффективного объёма кэш-памяти и алгоритма аппаратной компрессии данных, который позволяет повысить производительность подсистемы памяти без существенных расходов аппаратуры и значительных дополнительных задержек доступа к подсистеме памяти.

4. Метод увеличения пропускной способности сети-на-кристалле и межпроцессорных каналов связи большой ширины с политикой управления потоком wormhole за счёт аппаратной компрессии данных, минимизирующий задержки на компрессию и декомпрессию.

Соответствие паспорту специальности

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

Достоверность полученных результатов

Достоверность полученных результатов обеспечивается верификацией внедрённых решений с использованием симулятора RTL-описания и прототипа процессора архитектуры «Эльбрус», моделированием с использованием симулятора подсистемы памяти, достоверность которого проверена сравнением с реальным многоядерным процессором, а также подтверждается

экспериментальными данными.

Апробация работы

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

1. V Международная конференция «Инжиниринг & Телекоммуникации En&T 2018» (Москва, МФТИ, 15-16 ноября 2018 г.)

2. VII Международная конференция «Инжиниринг & Телекоммуникации En&T 2020» (Москва, МФТИ, 25-26 ноября 2020 г.)

3. VI научно-техническая конференция для специалистов организаций, входящих в АО «Концерн ВКО «Алмаз-Антей» (Москва, 25 ноября 2021 г.)

4. XI Международная научно-техническая и научно-методическая конференция «Актуальные проблемы инфотелекоммуникаций в науке и образовании» (Санкт-Петербург, СПбГУТ, 15-16 февраля 2022 г.)

5. IX Международная конференция «Инжиниринг & Телекоммуникации — En&T-2022» (Москва, 23-24 ноября 2022 г.)

6. 65-я Всероссийская научная конференция МФТИ (Москва, 3-8 апреля 2023 г.)

7. 9-я научная конференция «ЭКБ и микроэлектронные модули» в рамках российского форума «Микроэлектроника 2023» (Сочи, Федеральная территория «Сириус», 10-13 октября 2023 г.)

8. X Международная конференция «Инжиниринг & Телекоммуникации — En&T-2023» (Москва, 22-23 ноября 2023 г.)

Публикации по теме диссертации

По результатам, полученным в ходе диссертационного исследования, были опубликованы 12 работ. Из них 5 работ было опубликованы в журналах, входящих в перечень ВАК (в т.ч. 2 работы - в журналах, соответствующих специальности), 4 работы - в журналах, входящих в список Scopus. Получено свидетельство о регистрации программы для ЭВМ.

Структура работы

Диссертация состоит из введения, 4 глав, заключения и списка литературы (75 наименований). Полный объем диссертации составляет 163 страницы, включая 77 рисунков и 7 таблиц.

Глава 1. Выбор направления научного исследования

1.1. Введение

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

В частности, указывается роль подсистемы памяти в определении производительности вычислительных систем. Приводятся метрики, отражающие производительность самой подсистемы памяти в рамках вычислительной системы. Демонстрируется эффект от применения компрессии кэш-данных для повышения производительности подсистемы памяти как подтверждение актуальности её использования.

1.2. Производительность вычислительных систем

Эффективность вычислительной системы определяется временем, которое такая система затрачивает на выполнение определённой программы.

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

CPU clock cvcles for proqram

CPU time = -, , ---(1)

Clock rate

Здесь CPU time - время исполнения программы, CPU clock cycles for program - число тактов, требуемое для выполнения программы, Clock rate - частота работы процессора.

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

Во-первых, число тактов, за которое будет выполнена программа, можно представить как число инструкций в программе (Instruction count), умноженное на число тактов, требуемых в среднем на выполнение одной инструкции (Cycles per instruction, или CPI):

CPU clock cycles per instruction = Instruction count * Cycles per instruction

Во-вторых, вместо частоты работы процессора можно использовать более удобную для измерения обратную ей величину - длительность одного такта (clock cycle time):

Три параметра, указанные в формуле (4), т.е. количество инструкций в программе, среднее количество тактов на исполнение одной инструкции и длительность такта, определяют собой производительность вычислительной системы.

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

Во второй половине XX века, с начала появления и развития вычислительной техники, увеличение частоты работы процессора являлось одним из основных методов повышения производительности. В дальнейшем, с появлением микропроцессоров, возможность наращивания частоты определялась двумя законами, определявшими направление технологического развития разработки микропроцессоров - законом Мура [8] и законом Деннарда [9].

Закон Мура был высказан в качестве предположения о дальнейшем развитии индустрии одним из основателей Intel Гордоном Муром. В своём изначальном виде это предположение гласило, что число транзисторов на кристалле интегральной схемы будет удваиваться каждый год. Позднее Мур внёс туда корректировку, предсказывая удвоение числа транзисторов каждые два года.

Закон Деннарда носит имя инженера Роберта Деннарда, исследования которого показали, что при увеличении числа транзисторов на интегральной схеме потребляемую мощность кристалла можно сохранить неизменной. Это связано с выведенной им зависимостью мощности P от ёмкости транзисторов C, напряжения

1

Clock cycle time = ——--

Clock rate

Отсюда получается преобразованная формула (1):

CPU time = Instruction count * Cycles per instruction *

Clock cycle time

(3)

(4)

питания V и частоты f. Ниже приведена приблизительная формула такой зависимости (5):

1

Р= -СУ2 Г (5)

Увеличение числа транзисторов достигается за счёт улучшения технологии, в связи с чем сами транзисторы становятся меньше. Уменьшение их размера уменьшает время передачи сигналов, и, как следствие, появляется возможность повысить частоту процессора. Мощность при этом можно сохранить неизменной за счёт снижения ёмкости транзисторов и напряжения питания.

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

Таким образом, в настоящее время повышение производительности процессора путём повышения частоты его работы затруднительно. Среди популярных в настоящее время методов можно выделить динамическое изменение частоты работы процессорных ядер [10] и отключение питания для неиспользуемых в данный момент частей интегральной схемы [11].

Рассмотрим два других параметра в формуле (4) - количество инструкций в программе (Ю) и число тактов на инструкцию (CPI).

Тенденция к сокращению количества инструкций, которыми кодируется программа, в основном проявлялась в 70-х годах XX века. Преимущественно она была связана с тем, что в это время начали активно развиваться языки программирования высокого уровня. Чтобы облегчить работу компилятора по трансляции команд высокого уровня в архитектурные команды, разработчики добавляли в архитектуру новые команды, которые напрямую соответствовали бы

высокоуровневым командам.

Одним из наиболее ярких примеров подобных архитектур является архитектура VAX [12], обладающая очень большим количеством специализированных инструкций, размеры которых могли превышать 320 байт, а время исполнения могло занимать больше 10 процессорных тактов.

В противовес такому подходу, окрещённому CISC (Complex Instruction Set Computer), в начале 80-х годов был предложен подход RISC (ReducedInstruction Set Computer) [13][14]. Сторонники RISC утверждали, что наилучший способ разработки компьютеров состоит в использовании небольшого числа простых команд, способных исполняться за один процессорный такт. По их мнению, даже несмотря на то, что RISC-системе требуется выполнять несколько команд там, где CISC-системе только одну, RISC окажется быстрее из-за более высокой скорости обработки команд.

Во многом это предположение оправдалось, что демонстрируют представленные ниже результаты (Рисунок 1.1). Сравнивается производительность на задачах пакета SPEC89 двух машин со схожей аппаратной реализацией, одна из которых использует CISC-архитектуру VAX 8700, а другая - RISC-архитектуру MIPS M2000 [15][16]. Можно видеть, что несмотря на то, что MIPS исполняет примерно в 2 раза большее количество инструкций, использование этой архитектуры даёт примерно в 3 раза большую производительность.

Увеличение скорости обработки команд при использовании RISC-подхода достигается за счёт конвейеризации исполнения команд. Конвейеризация заключается в разбиении выполнения каждой команды на несколько независимых стадий, что удаётся сделать благодаря тому, что команды RISC просты по функциональности и имеют единый формат. В конвейере затем одновременно может исполняться несколько таких команд на разных стадиях.

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

за которых значение CPI будет больше 1. Среди возможных конфликтов выделяют структурные, конфликты по данным и конфликты по управлению.

Рисунок 1.1 - Сравнение производительности на задачах пакета SPEC89 для двух машин со схожей аппаратной реализацией, использующих архитектуру VAX 8700

и MIPS M2000 [15]

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

Конфликты по данным могут происходить, когда одна команда в конвейере использует результаты другой, ещё не завершившейся команды. Они могут быть частично устранены перестановкой команд, байпасированием результатов команд внутри конвейера и использованием не только архитектурных, но и физических регистров для хранения значений, используемых в вычислениях.

Конфликты по управлению связаны с тем, что одна из обрабатываемых команд может являться командой передачи управления, и в таком случае необходима её частичная обработка, прежде чем можно будет сказать, какие

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

Рассмотрим также другие методы снижения CPI, помимо конвейеризации. Прежде всего остановимся на методах, которые основаны на параллелизме на уровне инструкций (instruction-level parallelism).

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

Другим методом, частично упомянутым ранее, является динамическое переупорядочивание команд и их внеочередное исполнение (out-of-order execution). Этот подход снижает негативный эффект на CPI от неразрешимых зависимостей по данным, позволяя, в случае конфликта по данным для текущей команды, запускать следующие команды в конвейере, если между ними и командой с конфликтом нет зависимостей. В этом случае результаты работы таких команд будут получены заранее (out-of-order execution), но регистровый файл будет обновляться в том порядке, в котором команды были указаны в программе (in-order commit).

Ещё одним популярным методом понижения CPI является суперскалярность [17]. В суперскалярных процессорах одновременно на исполнение в конвейере может выбираться несколько инструкций, но также одновременно могут работать несколько исполнительных устройств. Поиск возможности параллельного запуска двух команд происходит динамически во время работы программы. Зачастую этот метод совмещают с out-of-order, таким образом более эффективно наполняя конвейер командами.

Альтернативным подходом является VLIW (Very Long Instruction Word) [18]. VLIW-машины также имеют несколько исполнительных устройств, способных работать параллельно, но задача по поиску параллелизма инструкций в них

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

Помимо использования параллелизма на уровне инструкций, для понижения CPI также может использоваться параллелизм на уровне процессов и потоков (thread-levelparallelism). Исполняемая программа может иметь сегменты, которые могут исполняться параллельно, что можно использовать для её ускорения.

Одним из способов достичь такого ускорения является многоядерность, которая после окончания выполнения закона Деннарда позволила продолжать наращивать производительность процессоров. Все действия, которые выполняются в программе, можно разделить на параллелизуемые и не параллелизуемые, и затем параллелизуемые действия распределить по нескольким ядрам. При этом необходимо учитывать, что наличие непараллелизуемой части программы накладывает ограничение на потенциальный прирост производительности при увеличении числа ядер (закон Амдала [19]).

Использование многоядерности для повышения CPI хорошо дополняется таким методом, как многопоточность (multithreading) [20]. В этом случае распараллеливание задачи может производиться не только по отдельным ядрам, но и по нескольким потокам в пределах одного ядра. При этом переключение на другой поток может происходить тогда, когда при работе с текущим потоком появляется задержка, вызывающая простой конвейера (крупнозернистая многопоточность, coarse-grain multithreading) или каждые несколько тактов (мелкозернистая многопоточность, fine-grain multithreading).

Чаще всего многопоточность рассматривается в сочетании с суперскалярностью, в таком случае возможно одновременное исполнение нескольких потоков в конвейере, используя незанятые исполнительные устройства (т.н. simultaneous multithreading, или SMT). Рисунок 1.2 показывает, как загружены исполнительные устройства процессорного ядра при обычном суперскалярном исполнении, крупнозернистой, мелкозернистой многопоточности и SMT. Можно

видеть, что SMT обеспечивает наибольшую производительность, плотнее загружая конвейер.

Рисунок 1.2 - Загруженность исполнительных устройств при использовании различных подходов к исполнению команд [15]

1.3. Роль подсистемы памяти в производительности вычислительных систем

Обратимся теперь к тому, какой эффект на производительность вычислительной системы оказывает производительность подсистемы памяти этой системы. Необходимо учесть в исходной формуле (1) влияние задержек на обращение за данными в память. Число тактов на исполнение программы будет складываться из числа тактов, затраченных непосредственно на исполнение программы (CPU execution clock cycles), и числа таков ожидания ответа из памяти (Memory stall cycles). Ниже приведена новая формула для CPU time, где по сравнению с формулой (1) также дополнительно используется длительность одного такта вместо частоты процессора:

Список литературы диссертационного исследования кандидат наук Сурченко Александр Викторович, 2024 год

Список литературы

1. Ziv J., Lempel A. A universal algorithm for sequential data compression //IEEE Transactions on information theory. - 1977. - Т. 23. - №. 3. - С. 337-343.

2. Ziv J., Lempel A. Compression of individual sequences via variable-rate coding //IEEE transactions on Information Theory. - 1978. - Т. 24. - №. 5. - С. 530536.

3. Welch T. A. A technique for high-performance data compression //Computer. - 1984. - Т. 17. - №. 06. - С. 8-19.

4. Huffman D. A. A method for the construction of minimum-redundancy codes //Proceedings of the IRE. - 1952. - Т. 40. - №. 9. - С. 1098-1101.

5. Vitter J. S. Design and analysis of dynamic Huffman codes //Journal of the ACM (JACM). - 1987. - Т. 34. - №. 4. - С. 825-845.

6. Lelewer D. A., Hirschberg D. S. Data compression //ACM Computing Surveys (CSUR). - 1987. - Т. 19. - №. 3. - С. 261-296.

7. Zhao L. et al. NCID: a non-inclusive cache, inclusive directory architecture for flexible and efficient cache hierarchies //Proceedings of the 7th ACM international conference on Computing frontiers. - 2010. - С. 121-130.

8. Moore G. E. Cramming more components onto integrated circuits, Reprinted from Electronics, volume 38, number 8, April 19, 1965, pp. 114 ff //IEEE solid-state circuits society newsletter. - 2006. - Т. 11. - №. 3. - С. 33-35.

9. R. Dennard, et al. Design of ion-implanted MOSFETs with very small physical dimensions //IEEE Journal of Solid State Circuits. - 1974. - Т. SC-9. - № 5. -С. 256-268.

10. Charles J. et al. Evaluation of the intel® core™ i7 turbo boost feature //2009 IEEE International Symposium on Workload Characterization (IISWC). - IEEE, 2009. - С. 188-197.

11. Esmaeilzadeh H. et al. Dark silicon and the end of multicore scaling //Proceedings of the 38th annual international symposium on Computer architecture. -2011. - С. 365-376.

12. Strecker W. D. VAX-11/780-A virtual address extension to the DEC PDP-11 family //Managing Requirements Knowledge, International Workshop on. - IEEE Computer Society, 1978. - C. 967-967.

13. Patterson D. A., Ditzel D. R. The case for the reduced instruction set computer //ACM SIGARCH Computer Architecture News. - 1980. - T. 8. - №. 6. - C. 25-33.

14. Patterson D. A. Reduced instruction set computers //Communications of the ACM. - 1985. - T. 28. - №. 1. - C. 8-21.

15. Hennessy J.L., Patterson D.A. Computer Architecture: A Quantitative Approach. 6th Edition, Morgan Kaufmann publishers, 2019.

16. Bhandarkar D., Clark D. W. Performance from architecture: comparing a RISC and a CISC with similar hardware organization //Proceedings of the fourth international conference on Architectural support for programming languages and operating systems. - 1991. - C. 310-319.

17. Smith J. E., Sohi G. S. The microarchitecture of superscalar processors //Proceedings of the IEEE. - 1995. - T. 83. - №. 12. - C. 1609-1624.

18. Fisher J. A. The VLIW machine: A multiprocessor for compiling scientific code //Computer. - 1984. - T. 17. - №. 07. - C. 45-53.

19. Amdahl G. M. Validity of the single processor approach to achieving large scale computing capabilities //Proceedings of the April 18-20, 1967, spring joint computer conference. - 1967. - C. 483-485.

20. Tullsen D. M., Eggers S. J., Levy H. M. Simultaneous multithreading: Maximizing on-chip parallelism //Proceedings of the 22nd annual international symposium on Computer architecture. - 1995. - C. 392-403.

21. Hebbar SR R., Milenkovic A. SPEC CPU2017: Performance, event, and energy characterization on the core i7-8700K //Proceedings of the 2019 ACM/SPEC International Conference on Performance Engineering. - 2019. - C. 111-118.

22. Bucek J., Lange K. D., v. Kistowski J. SPEC CPU2017: Next-generation compute benchmark //Companion of the 2018 ACM/SPEC International Conference on Performance Engineering. - 2018. - C. 41-42.

23. Balasubramonian R., Jouppi N. P., Muralimanohar N. Multi-core cache hierarchies. - Williston, VT, USA : Morgan & Claypool, 2011. - C. 1-153.

24. Patterson D.A., Hennessy J.L. Computer Organization and Design. 4th Edition, Morgan Kaufmann publishers, 2009.

25. Harris S., Harris D. Digital design and computer architecture. - Morgan Kaufmann, 2015.

26. Ahmed N., Natarajan T., Rao K. R. Discrete cosine transform //IEEE transactions on Computers. - 1974. - T. 100. - №. 1. - C. 90-93.

27. Yang J., Zhang Y., Gupta R. Frequent value compression in data caches //Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture. - 2000. - C. 258-265.

28. Alameldeen A., Wood D. Frequent pattern compression: A significance-based compression scheme for L2 caches. - University of Wisconsin-Madison Department of Computer Sciences, 2004.

29. Chen X. et al. C-pack: A high-performance microprocessor cache compression algorithm //IEEE transactions on very large scale integration (VLSI) systems. - 2009. - T. 18. - №. 8. - C. 1196-1208.

30. Pekhimenko G. et al. Base-delta-immediate compression: Practical data compression for on-chip caches //2012 21st international conference on parallel architectures and compilation techniques (PACT). - IEEE, 2012. - C. 377-388.

31. Zhang Y., Yang J., Gupta R. Frequent value locality and value-centric data cache design //ACM SIGARCH Computer Architecture News. - 2000. - T. 28. - №. 5. - C. 150-159.

32. Alameldeen A. R., Wood D. A. Adaptive cache compression for highperformance processors //Proceedings. 31st Annual International Symposium on Computer Architecture, 2004. - IEEE, 2004. - C. 212-223.

33. Dusser J., Piquet T., Seznec A. Zero-content augmented caches //Proceedings of the 23rd international conference on Supercomputing. - 2009. - C. 4655.

34. Sardashti S., Wood D. A. Decoupled compressed cache: Exploiting spatial locality for energy-optimized compressed caching //2013 46th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO). - IEEE, 2013. - C. 62-73.

35. Sardashti S., Seznec A., Wood D. A. Skewed compressed caches //2014 47th Annual IEEE/ACM International Symposium on Microarchitecture. - IEEE, 2014.

- C. 331-342.

36. Gaur J., Alameldeen A. R., Subramoney S. Base-victim compression: An opportunistic cache compression architecture //2016 ACM/IEEE 43rd Annual International Symposium on Computer Architecture (ISCA). - IEEE, 2016. - C. 317328.

37. Dally W. J., Towles B. Route packets, not wires: on-chip interconnection networks //Proceedings of the 38th annual design automation conference. - 2001. - C. 684-689.

38. Nurmi J. Network-on-chip: A new paradigm for system-on-chip design //2005 International Symposium on System-on-Chip. - IEEE, 2005. - C. 2-6.

39. Kant K., Iyer R. Design and performance of compressed interconnects for high performance servers //Proceedings 21st International Conference on Computer Design. - IEEE, 2003. - C. 164-169.

40. Liu C., Sivasubramaniam A., Kandemir M. Optimizing bus energy consumption of on-chip multiprocessors using frequent values //12th Euromicro Conference on Parallel, Distributed and Network-Based Processing, 2004. Proceedings.

- IEEE, 2004. - C. 340-347.

41. Yang J., Gupta R., Zhang C. Frequent value encoding for low power data buses //ACM Transactions on Design Automation of Electronic Systems (TODAES). -2004. - T. 9. - №. 3. - C. 354-384.

42. Thuresson M., Spracklen L., Stenstrom P. Memory-link compression schemes: A value locality perspective //IEEE Transactions on Computers. - 2008. - T. 57. - №. 7. - C. 916-927.

43. Das R. et al. Performance and power optimization through data compression in network-on-chip architectures //2008 IEEE 14th International Symposium on High Performance Computer Architecture. - IEEE, 2008. - C. 215-225.

44. Jin Y., Yum K. H., Kim E. J. Adaptive data compression for highperformance low-power on-chip networks //2008 41st IEEE/ACM International Symposium on Microarchitecture. - IEEE, 2008. - C. 354-363.

45. Zhou P. et al. Frequent value compression in packet-based NoC architectures //2009 Asia and South Pacific Design Automation Conference. - IEEE, 2009. - C. 13-18.

46. Zhan J. et al. NoA: Leveraging delta compression for end-to-end memory access in NoC based multicores //2014 19th Asia and South Pacific Design Automation Conference (ASP-DAC). - IEEE, 2014. - C. 586-591.

47. Wang Y. et al. DISCO: A low overhead in-network data compressor for energy-efficient chip multi-processors //Proceedings of the 53rd Annual Design Automation Conference. - 2016. - C. 1-6.

48. Wang Y. et al. A low overhead in-network data compressor for the memory hierarchy of chip multiprocessors //IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. - 2017. - T. 37. - №. 6. - C. 1265-1277.

49. Tremaine R. B. et al. IBM memory expansion technology (MXT) //IBM Journal of Research and Development. - 2001. - T. 45. - №. 2. - C. 271-285.

50. Abali B. et al. Memory expansion technology (MXT): software support and performance //IBM Journal of Research and Development. - 2001. - T. 45. - №. 2. - C. 287-301.

51. Tremaine R. B. et al. Pinnacle: IBM MXT in a memory controller chip //IEEE Micro. - 2001. - T. 21. - №. 2. - C. 56-68.

52. Ekman M., Stenstrom P. A robust main-memory compression scheme //32nd International Symposium on Computer Architecture (ISCA'05). - IEEE, 2005. -C. 74-85.

53. Pekhimenko G. et al. Linearly compressed pages: A low-complexity, low-latency main memory compression framework //Proceedings of the 46th Annual IEEE/ACM International Symposium on Microarchitecture. - 2013. - С. 172-184.

54. Shafiee A. et al. MemZip: Exploring unconventional benefits from memory compression //2014 IEEE 20th International Symposium on High Performance Computer Architecture (HPCA). - IEEE, 2014. - С. 638-649.

55. Young V., Kariyappa S., Qureshi M. K. CRAM: Efficient Hardware-Based Memory Compression for Bandwidth Enhancement //arXiv preprint arXiv:1807.07685. - 2018.

56. Choukse E., Erez M., Alameldeen A. R. Compresso: Pragmatic main memory compression //2018 51st Annual IEEE/ACM International Symposium on Microarchitecture (MICRO). - IEEE, 2018. - С. 546-558.

57. Speier T., Wolford B. Qualcomm centriq 2400 processor //Hot Chips: A Symposium on High Performance Chips (HC29. - 2017. - №. 2017.

58. Lipp M. et al. Meltdown: Reading kernel memory from user space //27th USENIX Security Symposium (USENIX Security 18). - 2018. - С. 973-990.

59. Kocher P. et al. Spectre attacks: Exploiting speculative execution //2019 IEEE Symposium on Security and Privacy (SP). - IEEE, 2019. - С. 1-19.

60. Tsai P. A. et al. Safecracker: Leaking secrets through compressed caches //Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems. - 2020. - С. 1125-1140.

61. Кожин А.С., Сурченко А.В. Исследование применимости компрессии данных в кэш-памяти микропроцессоров с архитектурой «Эльбрус» // Вопросы радиоэлектроники. 2018. №2. С. 32-39.

62. Kozhin A. S., Surchenko A. V. Evaluation of cache compression for Elbrus processors //2018 Engineering and Telecommunication (EnT-MIPT). - IEEE, 2018. - С. 135-139.

63. Kozhin A. S., Surchenko A. V. Design of Data Compression Mechanism in Cache Memory of Elbrus Processors //2020 International Conference Engineering and Telecommunication (En&T). - IEEE, 2020. - С. 1-5.

64. Deb D., Rohith M. K., Jose J. Flitzip: Effective packet compression for noc in multiprocessor system-on-chip //IEEE Transactions on Parallel and Distributed Systems. - 2021. - Т. 33. - №. 1. - С. 117-128.

65. Li X., Sondhi T. FlitReduce: Improving Memory Fabric Performance via End-to-End Network Packet Compression //UC Berkeley CS262A Report. - 2021.

66. Pullaiah T., Manjunathachari K., Malleswari B. L. BA-NIS: Performance analysis of an efficient data compression technique for on-chip communication network //Integration. - 2023. - Т. 89. - С. 83-93.

67. Nedbailo Y. Fast and scalable simulation framework for large in-order chip multiprocessors //2020 26th Conference of Open Innovations Association (FRUCT). -IEEE, 2020. - С. 335-345.

68. Henning J. L. SPEC CPU2000: Measuring CPU performance in the new millennium //Computer. - 2000. - Т. 33. - №. 7. - С. 28-35.

69. Nedbailo Y. A., Surchenko A. V., Bychkov I. N. Reducing miss rate in a non-inclusive cache with inclusive directory of a chip multiprocessor //Компьютерные исследования и моделирование. - 2023. - Т. 15. - №. 3. - С. 639-656.

70. Jaleel A. Memory characterization of workloads using instrumentation-driven simulation //Web Copy: http://www.glue.umd.edu/ajaleel/workload. - 2010. - С. 1-12.

71. Singh S., Awasthi M. Memory centric characterization and analysis of spec cpu2017 suite //Proceedings of the 2019 ACM/SPEC International Conference on Performance Engineering. - 2019. - С. 285-292.

72. Jaleel A. et al. Adaptive insertion policies for managing shared caches //Proceedings of the 17th international conference on Parallel architectures and compilation techniques. - 2008. - С. 208-219.

73. McCalpin J. D. et al. Memory bandwidth and machine balance in current high performance computers //IEEE computer society technical committee on computer architecture (TCCA) newsletter. - 1995. - Т. 2. - №. 19-25.

74. Gove D. CPU2006 working set size //ACM SIGARCH Computer Architecture News. - 2007. - Т. 35. - №. 1. - С. 90-96.

75. Сурченко А. В. Применение методики увеличения эффективного объёма кэш-памяти при использовании аппаратной компрессии данных в процессорах архитектуры «Эльбрус» //Сборник тезисов 65-й Всероссийской научной конференции МФТИ в честь 115-летия Л.Д. Ландау. - МФТИ, 2023.

Список иллюстраций

Рисунок 1.1 - Сравнение производительности на задачах пакета SPEC89 для двух машин со схожей аппаратной реализацией, использующих архитектуру VAX 8700

и MIPS M2000 [15]........................................................................................................19

Рисунок 1.2 - Загруженность исполнительных устройств при использовании

различных подходов к исполнению команд [15]........................................................22

Рисунок 1.3 - Утилизация тактов исполнения задач SPEC CPU2017 в режиме rate

на процессоре Intel Core i7-8700K [21].......................................................................23

Рисунок 2.1 - Компрессия данных по алгоритму Frequent Value Compression [27] ...

......................................................................................................................................... 31

Рисунок 2.2 - Компрессия по алгоритму Base-Delta-Immediate (показан случай без

рассмотрения нулевого базового значения) [30]........................................................34

Рисунок 2.3 - Организация Compressed Cache [27]...................................................37

Рисунок 2.4 - Совместное использование FVC с обычным кэшем прямого

отображения [31]...........................................................................................................37

Рисунок 2.5 - Организация Zero Content Augmented Cache [33]..............................40

Рисунок 2.6 - Организация кэша для алгоритма Base-Delta-Immediate [30]..........40

Рисунок 2.7 - Поведение кэша при использовании Base-Victim Compression [36] 42

Рисунок 2.8 - Использование CVC при передаче сжатых данных [40]...................45

Рисунок 2.9 - Организация компрессии передаваемых данных при использовании

подходов CC и NC [43].................................................................................................48

Рисунок 2.10 - Уменьшение количества флитов для передачи данных при

использовании дельта-компрессии [46] ...................................................................... 50

Рисунок 2.11 - Сжатие страницы при использовании подхода LCP [53]................55

Рисунок 2.12 - Упаковка сжатых кэш-строк при использовании подхода

CRAM [55]......................................................................................................................57

Рисунок 2.13 - Увеличение пропускной способности памяти в Qualcomm Centriq

2400 при использовании аппаратной компрессии данных в [57].............................59

Рисунок 2.14 - Изменение формата хранения кэш-строк в оперативной памяти при использовании аппаратной компрессии данных в Qualcomm Centriq 2400 [57] .... 59

Рисунок 3.1 - Компрессия данных по алгоритму BAI...............................................66

Рисунок 3.2 - Декомпрессия данных по алгоритму BAI...........................................66

Рисунок 3.3 - Компрессия данных по алгоритму BAI*.............................................67

Рисунок 3.4 - Декомпрессия данных по алгоритму BAI*.........................................68

Рисунок 3.5 - Организация одного ассоциативного набора кэш-памяти последнего

уровня современных процессоров с архитектурой «Эльбрус»................................72

Рисунок 3.6 - Изменения в организации одного ассоциативного набора кэшпамяти последнего уровня для хранения в нем сжатых данных..............................74

Рисунок 3.7 - Изменения в организации одного ассоциативного набора кэшпамяти последнего уровня для увеличения его эффективного объёма...................75

Рисунок 3.8 - Конфликт при выдаче данных чтения, вызванный задержкой на

декомпрессию сжатых данных.....................................................................................78

Рисунок 3.9 - Разрешение конфликта по выдаче данных чтения, связанного с

задержкой на декомпрессию сжатых данных.............................................................78

Рисунок 3.10 - Действия при промахе в справочник (LD Miss)...............................81

Рисунок 3.11 - Действия при попадании в LDD (LDD Hit)......................................82

Рисунок 3.12 - Действия при попадании в LDX (LDX Hit)......................................83

Рисунок 3.13 - Действия при попадании в LDD при применении метода

размещения данных в кэш-памяти с поддержкой аппаратной компрессии данных

.........................................................................................................................................85

Рисунок 3.14 - Действия при попадании в LDX при применении метода размещения данных в кэш-памяти с поддержкой аппаратной компрессии данных

.........................................................................................................................................86

Рисунок 3.15 - Действия при промахе в справочник при применении метода размещения данных в кэш-памяти с поддержкой аппаратной компрессии данных

.........................................................................................................................................87

Рисунок 3.16 - Действия при промахе в справочник при применении метода размещения данных в кэш-памяти с поддержкой аппаратной компрессии данных:

случай двойного вытеснения из LDX.........................................................................89

Рисунок 3.17 - Потеря значимых данных в ходе транзакций, имеющих доступ к

одной ячейке памяти данных.......................................................................................91

Рисунок 3.18 - Внешний вид пакета с данными, в котором передаётся одна кэш-

строка ..............................................................................................................................96

Рисунок 3.19 - Задержка при компрессии данных непосредственно в самой сети-

на-кристалле...................................................................................................................98

Рисунок 3.20 - Задержка при декомпрессии данных непосредственно в самой

сети-на-кристалле..........................................................................................................99

Рисунок 3.21 - Компрессия данных в ходе транзакции по записи данных...........100

Рисунок 3.22 - Компрессия большого пакета с данными из 4 кэш-строк.............102

Рисунок 3.23 - Компрессия большого пакета с данными из 4 кэш-строк в случае,

когда все данные нулевые...........................................................................................103

Рисунок 3.24 - Транзакция по записи нулевых данных..........................................104

Рисунок 3.25 - Транзакция по чтению нулевых данных, владелец данных передаёт

информацию о нулевом значении данных напрямую инициатору запроса..........105

Рисунок 3.26 - Транзакция по чтению нулевых данных, владелец данных передаёт

информацию о нулевом значении данных через справочник.................................105

Рисунок 4.1 - Тестовый стенд для сравнения эффективности работы алгоритмов

компрессии...................................................................................................................107

Рисунок 4.2 - Модель процессора «Эльбрус» на основе трасс событий..............108

Рисунок 4.3 - Сравнение количества инструкций, исполняемых за такт, на задачах пакета SPEC CPU2017 для реального процессора и его модели на основе трассы

событий при запуске на одном ядре..........................................................................108

Рисунок 4.4 - Замедление при запуске задач пакета SPEC CPU2017 на реальном

процессоре и его модели на основе трассы событий на 16 ядрах..........................109

Рисунок 4.5 - Доля сжатых строк по алгоритмам компрессии нулевых и

повторяющихся значений, B+Д и BAI.......................................................................110

Рисунок 4.6 - Вклад схем компрессии алгоритмов B+Д и BAI для целочисленных

задач...............................................................................................................................111

Рисунок 4.7 - Вклад схем компрессии алгоритмов B+Д и BAI для задач с плавающей точкой.......................................................................................................112

Рисунок 4.8 - Частота срабатывания схем компрессии алгоритмов B+Д и BAI ... 113 Рисунок 4.9 - Степень сжатия данных по алгоритмам компрессии нулевых и

повторяющихся значений, их сочетанию, B+Д и BAI.............................................113

Рисунок 4.10 - Доля сжатых строк по алгоритмам компрессии нулевых и

повторяющихся значений, B+Д* и BAI*...................................................................115

Рисунок 4.11 - Вклад схем компрессии алгоритмов B+Д* и BAI* в общую долю

сжатых строк для целочисленных задач...................................................................116

Рисунок 4.12 - Вклад схем компрессии алгоритмов B+Д* и BAI* в общую долю

сжатых строк для задач с плавающей точкой...........................................................116

Рисунок 4.13 - Частота срабатывания схем компрессии алгоритмов B+Д* и BAI*

.......................................................................................................................................117

Рисунок 4.14 - Степень сжатия данных по алгоритмам компрессии нулевых и

повторяющихся значений, их сочетанию, B+Д* и BAI*.........................................118

Рисунок 4.15 - Сравнение алгоритмов BAI и BAI* по доле сжатых строк...........119

Рисунок 4.16 - Сравнение алгоритмов BAI, BAI* и BAI*-HL по доле сжатых строк

.......................................................................................................................................120

Рисунок 4.17 - Доля сжатых строк для алгоритма BAI*-HL на задачах пакета

SPEC CPU2017.............................................................................................................121

Рисунок 4.18 - Частота срабатывания схем компрессии алгоритма BAI*-HL......121

Рисунок 4.19 - Степень сжатия данных по алгоритму компрессии BAI*-HL......122

Рисунок 4.20 - Тестовый стенд для оценки эффективности использования

предлагаемых решений по увеличению эффективного объёма кэш-памяти........124

Рисунок 4.21 - Частота промахов в L3-кэш при использовании предлагаемых решений для увеличения эффективного объёма кэш-памяти на задачах SPEC

CPU2017.......................................................................................................................126

Рисунок 4.22 - Относительное увеличение IPC при использовании предлагаемых решений для увеличения эффективного объёма кэш-памяти на задачах пакета SPEC CPU2017.............................................................................................................126

Рисунок 4.23 - Зависимость максимального темпа доступа к данным от размера рабочих данных задач пакета stream в кэш-памяти без использования и с

использованием аппаратной компрессии данных....................................................129

Рисунок 4.24 - Зависимость среднего времени на итерацию в рамках задач пакета stream от размера рабочих данных в кэш-памяти без использования и с

использованием аппаратной компрессии данных....................................................130

Рисунок 4.25 - Зависимость максимального темпа доступа к данным от размера рабочих данных задач read и set в кэш-памяти без использования и с

использованием аппаратной компрессии данных....................................................131

Рисунок 4.26 - Зависимость среднего времени на итерацию в рамках задач read и set от размера рабочих данных в кэш-памяти без использования и с

использованием аппаратной компрессии данных....................................................131

Рисунок 4.27 - Тестовый стенд для оценки эффективности аппаратной

компрессии данных при передаче через межпроцессорные каналы связи...........135

Рисунок 4.28 - Доля трафика межпроцессорных каналов связи, относящегося к

сообщениям с данными, на задачах пакета SPEC CPU2000................................... 136

Рисунок 4.29 - Доля сжатых строк среди данных, передаваемых по

межпроцессорным каналам связи, для задач пакета SPEC CPU2000.................... 136

Рисунок 4.30 - Процент снижения трафика данных в межпроцессорных каналах связи при использовании аппаратной компрессии данных для задач пакета SPEC

CPU2000....................................................................................................................... 137

Рисунок 4.31 - Интенсивность трафика данных в сети-на-кристалле, вызванного

промахами в L2-кэш и L3-кэш...................................................................................138

Рисунок 4.32 - Доля сжатых строк при применении алгоритма BAI*-HL в сети-на-

кристалле и межпроцессорных каналах связи.........................................................138

Рисунок 4.33 - Относительное увеличение IPC при применении аппаратной

компрессии данных в сети-на-кристалле..................................................................139

Рисунок 4.34 - Относительное увеличение IPC при применении аппаратной компрессии данных в межпроцессорных каналах связи для разной доли страниц памяти в другом процессоре......................................................................................140

Список таблиц

Таблица 1.1 - Сравнение базовых оптимизаций для увеличения AMAT................27

Таблица 2.1 - Frequent Pattern Encoding [28]..............................................................32

Таблица 3.1 - Схемы компрессии алгоритмов B+Д и BAI (на основе [30])............64

Таблица 3.2 - Схемы компрессии алгоритма BAI*-HL [63].....................................70

Таблица 4.1 - Конфигурация процессора, используемая в симуляции.................109

Таблица 4.2 - Результаты синтеза модулей компрессии и декомпрессии для

алгоритмов BAI, BAI* и BAI*-HL..............................................................................123

Таблица 4.3 - Результаты запуска задачи 179.art на разном количестве ядер на FPGA-прототипе современного процессора архитектуры «Эльбрус»..................132

Приложение А (Свидетельство о государственной регистрации программы

для ЭВМ)

Приложение Б (Акты внедрения)

Эльбрус

АО «МЦСТ»

ул. Профсоюзная, д.108, Москва, 117437 тел: [phone] факс: [phone] http://www.mcst.ru e-mail: [e-mail]

ОГРН 1027739148469 ИНН 7736053886 КПП 773601001

АКТ ВНЕДРЕНИЯ

результатов диссертационной работы Сурченко Александра Викторовича «Структурные решения и методы аппаратной компрессии данных в подсистеме памяти многоядерных процессоров общего назначения», представленной на соискание учёной степени кандидата технических наук

Настоящим актом подтверждается, что результаты диссертационной работы Сурченко Александра Викторовича, посвященной решению задачи повышения производительности подсистемы памяти с помощью применения аппаратной компрессии данных, а именно:

предназначенный для применения в подсистеме памяти процессоров общего назначения,

• структурные решения для увеличения эффективного объёма кэшпамяти при использовании аппаратной компрессии данных,

• метод размещения данных в кэш-памяти с поддержкой аппаратной компрессии данных

внедрены при разработке микропроцессоров архитектуры «Эльбрус» в АО

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

• алгоритм аппаратной компрессии данных ВА1*-НЬ,

«МЦСТ».

Генеральный директор АО «МЦСТ», к.т.н.

Ким. А.К.

«

ИНСТИТУТ ЭЛЕКТРОННЫХ УПРАВЛЯЮЩИХ МАШИН им. И.С. Брука (ПАО «ИНЭУМ им. И.С. Брука»)

ПУБЛИЧНОЕ АКЦИОНЕРНОЕ ОБЩЕСТВО

»

119334, Москва, ул Вавилова, 24 тел. [phone] [e-mail] факс [phone]

[e-mail] wwwineum.ru

ОКНО 11494554 ОГРН 1027/00297426 ИНН/КПП 7736005096/773601001

|%\Л ч—,д —~ И.Н. Бычков

2024 г.

.С. Брука»

акт внедрения

результатов диссертационной работы Сурченко Александра Викторовича «Структурные решения и методы аппаратной компрессии данных в подсистеме памяти многоядерных процессоров общего назначения» на соискание учёной степени кандидата технических наук

Мы, нижеподписавшиеся, комиссия в составе: Председатель комиссии:

Руководитель управления 3.4 - Парамонов Николай Борисович

главный научный сотрудник,

заведующий базовой кафедрой

№ 234 - управляющих ЭВМ «РТУ

МИРЭА», заместитель

председателя учёного совета, д.т.н.,

профессор

и члены комиссии:

Учёный секретарь, к.т.н. Кривосинная Елена Вадимовна

Старший научный сотрудник, Кирилюк Михаил Андреевич старший преподаватель базовой кафедры № 234 - управляющих ЭВМ «РТУ МИРЭА» составили настоящий акт о том, что структурные решения для увеличения эффективного объёма кэш-памяти при использовании аппаратной компрессии данных, разработанные Сурченко A.B. в ходе выполнения диссертационной работы, использовалась в ходе обоснования технических решений по реализации программно-аппаратной платформы на отечественной элементной базе и отечественном программном обеспечении в рамках выполнения СЧ НИР «Антарес-22-Эльбрус», а также внедрены в учебный процесс базовой кафедры № 234 -управляющих ЭВМ «РТУ МИРЭА».

Члены комиссии:

Председатель комиссии:

Парамонов Н.Б.

Кривосинная Е.В. Кирилюк М.А.

УТВЕРЖДАЮ

Баган Виталий Анатольевич £_2024 г.

•те, к.ф.-м.н.

АКТ

об использовании теоретических и практических результатов диссертационной работы Сурченко Александра Викторовича «Структурные решения и методы аппаратной компрессии данных в подсистеме памяти многоядерных процессоров общего назначения», представленной на соискание учёной степени кандидата технических наук, в учебном процессе на кафедре информатики и вычислительной техники МФТИ

В рамках дисциплин «Архитектура высокопроизводительных микропроцессоров и вычислительных систем» и «Архитектура подсистемы памяти современных микропроцессоров», которые читаются студентам бакалавриата и магистратуры МФТИ соответственно на кафедре информатики и вычислительной техники, использованы теоретические и практические результаты диссертационной работы Сурченко Александра Викторовича «Структурные решения и методы аппаратной компрессии данных в подсистеме памяти многоядерных процессоров общего назначения». Среди них: алгоритм аппаратной компрессии данных ВАР-НЬ; структурные решения по увеличению эффективного объёма МСГО-кэш-памяти; метод размещения данных в КСГО-кэш-памяти, позволяющий реализовать структурные решения по увеличению ее эффективного объёма.

Зав. кафедрой информатики и

вычислительной техники МФТИ,

д.т.н., профессор

Фельдман Владимир Марткович