Главная › Статьи

Об авторе

Дмитрий Устюгов – студент 3 курса Московского Физико-Технического Института, обучающийся на кафедре «Микропроцессорные технологии», базирующейся при московском отделении компании Интел, проект IAG, стипендиат фонда Абрамова и Фролова. Стажер Летней школы Intel 2010, Москва.
Менторы: Владимир Гнатюк, Александр Титов.
Менеджер: Александр Бутузов.

Аннотация

Эффективная работа инструкционного кэша (ИК) вносит значительный вклад в производительность всего микропроцессора особенно в многопотоковых архитектурах с часто сменяющимися задачами. Проделанный в работе теоретический анализ «узких» мест в подсистеме памяти команд на примере современной многопотоковой архитектуры с векторным счетчиком команд позволил предположить эффективность использования предвыборки строк в ИК. Согласно результатам симуляции, с его использованием количество «промахов» в ИК уменьшилось на 29%, увеличив производительность системы на 2,2%, в среднем. По сравнению с традиционной суперскалярной архитектурой исследуемая не уступает по производительности, подкачивая на декодирующие устройства в 6 раз больше инструкций с использованием предвыборки строк в ИК.

Введение

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

Кэш-память - самая быстрая память компьютера, зачастую именно ее производительность и организация существенным образом влияет на производительность микропроцессора в целом. Именно кэш призван решать проблему разницы скоростей работы системы процессор-память, обеспечивая минимальное время работы «быстрого» процессора с «медленной» подсистемой памяти. Структуре и различным оптимизациям кэша всегда уделялось большое внимание ([9], [2]), и сегодня, когда все ярче проявляется тенденция к созданию многопотоковых микропроцессоров, проблема становится особенно актуальной.

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

В данной работе исследование проводилось на примере многопотоковой архитектуры с векторным счетчиком команд (АВСК). Число самих инструкционных потоков в данной архитектуре является величиной динамической и варьируется от 16-ти до 64-х в зависимости от выбранной модификации. Основное внимание в работе уделено построению оптимальной для данной архитектуры модели инструкционного кэша первого уровня, а также оптимизации его основных характеристик: размер, топология, а также аппаратура предвыборки строк в инструкционный кэш, введение которой является важным аспектом построения высокопроизводительного кэша для архитектуры с высоким уровнем параллелизма на уровне команд.

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

Считается ([2], [7], [9]), что введение блока предвыборки строк в инструкционный кэш способно существенно уменьшить количество промахов в инструкционный кэш, и тем самым, ускорить работу блока выборки (подкачки) команд для различных инструкционных потоков на декодирование и исполнение. В данной работе было проведено исследование эффективности динамического последовательного алгоритма предвыборки в инструкционный кэш в зоне «холодных» промахов (т.е. возникающих при первой загрузке программы в инструкционный кэш).

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

Архитектура с такими особенностями предъявляет особые требования к организации аппаратуры выборки инструкций. Большому количеству потоков требуется значительное количество вовремя подкаченных команд, готовых к декодированию и исполнению. Очевидно, что узким местом такой архитектуры становится не только подсистема памяти, но и вся управляющая логика процессора (front-end). В данной статье мы уделили внимание только оптимизации устройства выборки команд в целом и инструкционного кэша, в частности.

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

Обзор исследований и работ в данной сфере

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

Введение аппаратуры предвыборки должно уменьшить количество «промахов», тем самым обеспечивая производительность системы памяти. Предвыборка, как оптимизация кэш-памяти, это довольно распространенная и успешно применяемая методика ([9], [3], [8]). Исторически основными тенденциями являются: использование динамической или статической предвыборки. Динамическая предвыборка может быть последовательной (основанной на локальности кода) или непоследовательной (основанной на динамическом предсказании переходов). Для исследования был отобран динамический алгоритм последовательной предвыборки строк в инструкционный кэш. Данный алгоритм, несмотря на свою кажущуюся простоту, используется во многих современных процессорах. Его использование способно как бы «расширить» локальность данных (что подчеркивается в [3]), способствуя достижению меньшего количества промахов при меньшем размере «дорогой», для размещения на кристалле, кэш-памяти. Такой алгоритм максимально загружает шину памяти, ускоряя обработку «промахов» в инструкционный кэш, при этом, не «засоряя» ИК ненужными строками (т.к. запись в ИК осуществляется, только после того, как данную строку потребует блок выборки команд).

Помимо абсолютного количества промахов для сравнения производительности различных архитектур одного семейства в литературе ([2]) обычно используется нормировка количества «промахов» на общее количество запросов в кэш, либо на некоторое количество выполненных инструкций.

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

Исследование в данной работе проводилось на моделях процессора сконфигурированных как представлено в Таблице 1.

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

Для ответов на вопросы, поставленные в теоретической части статьи, приведенных выше, предметами исследования были отобраны следующие основные метрики, отражающие производительность ИК (см. пред. главу):

1. Количество «промахов» и «попаданий» в инструкционный кэш.
2. Отношение количества промахов к общему числу запросов в инструкционный кэш (miss rate).
3. Количество инструкций исполненных за такт (в среднем) (IPC).
4. Количество подкаченных на декодирующее устройство инструкций.

Из набора тестов, генерируемых бинарным компилятором из x86-го кода, были выбраны те, которые дают ощутимую нагрузку на подсистему памяти команд. Среди них: микротесты - небольшие программы для рассмотрения производительности кэша при первой загрузке программы (взяты из наборов SPEC 92, 95 [15]), а также части программы bzip2_SPEC2006 [15]. Такие относительно большие тесты дают достаточное количество конфликтных промахов в инструкционный кэш, необходимое для определения оптимальных характеристик в зонах «холодных» (т.е. возникающих при первой загрузке программы в кэш), конфликтных, а также промахов из-за размера кэша ([2]).

Анализ эффективности предвыборки выполнялся методом последовательных приближений модели с идеальной подсистемой памяти к реальной: вначале была сделана оценка (при помощи специальных счетчиков, введенных в симуляторе), а затем проведена симуляция модели с реальной подсистемой памяти команд (вплоть до кэша третьего уровня). Для проведения этой части исследования были взяты микротесты, т.к. они позволяют исследовать производительность подсистемы памяти и ИК в зоне «холодных» промахов, т.е. когда шина память максимально загружена. Таким образом, анализировалась перспективность введения аппаратуры в реальном процессоре.

Статистика работы потактового симулятора архитектуры с векторным счетчиком команд собиралась при помощи программы PLOT-SHELL [13], задача которой была преобразовать полученный файл статистики (*.xml) в удобный для анализа вид (*.xls).

Нахождение оптимальной конфигурации инструкционного кэша

Рис.1 Зависимость количества промахов от размера и конфигурации ИК

Для начала было проведено исследование инструкционного кэша на предмет определения его оптимальных характеристик. На Рис. 1 представлена зависимость количества «промахов» в инструкционном кэше от размера кэша при разной ассоциативности последнего.

При размере более 32Кб наблюдаются только «промахи», возникающие при первой загрузке программы в кэш, это т.н. «холодные промахи», избежать которых невозможно. При размерах кэша менее 32Кб начинают преобладать конфликтные «промахи», связанные с постоянными замещениями линий в кэше. Можно видеть, что 8-входовый кэш (N-входовая структура представлена в [1]) является наиболее оптимальной конфигурацией.

Рис.2 Зависимость количества инструкций выполненных за такт от размера ИК

На Рис. 2 представлена зависимость количества инструкций, выполненных за такт (IPC), от размера кэша. Анализ данной диаграммы показывает, что с размером в 32Кб практически нет разницы, какая из ассоциативных моделей была выбрана. При прочих равных условиях использование более ассоциативного кэша является более затратным по времени поиска записей, вместе с тем обеспечивая меньше «промахов» в кэш, тем самым взаимно компенсируя затраты на поиск записей. Исходя из этого, можно сделать вывод, что 8-входовый инструкционный кэш размером 32 Кб является оптимальным решением для исследуемой архитектуры, такая конфигурация кэш-памяти была принята в качестве «рабочей» в последующих исследованиях.

Исследование эффективности аппаратуры предвыборки

Как было сказано выше, данное исследование проводились методом последовательных приближений идеальной модели к реальной. Сначала, путем введения в код симулятора, была выполнена оценка эффективности аппаратуры предвыборки. Алгоритм счетчиков работал следующим образом: каждый раз, когда в кэше случался «промах», происходил поиск в кэше предыдущей строки, в случае нахождения оной, делался вывод, что строка, по которой случался «промах», могла быть подкаченной заранее, если бы работала аппаратура последовательной предвыборки. Таким образом, был получен теоретический предел эффективности предвыборки строк в инструкционный кэш: до 50% всех «промахов» можно избежать, используя аппаратуру предвыборки.

Рис.3 Эффективность механизмов предвыборки

На Рис. 3 можно видеть, что при использовании модели симулятора с реальной подсистемой памяти порядка 40% строк, запрашиваемых блоком предвыборки, не успели вовремя записаться в кэш в силу следующих причин:

• Строка, выбранная блоком предвыборки, могла не успеть подкачаться из кэша второго уровня, и по её адресу, вслед за запросом предвыборки, произойдет запрос по «промаху».
• Шина подсистемы памяти слишком занята обработкой запросов по «промахам» в кэше, и, следовательно, запросы предвыборки практически не обрабатываются, т.к. они имеют меньший приоритет. В таком случае новые запросы, генерируемые блоком предвыборки строк, перетирают старые запросы в буфере предвыборки.

Основной причиной, вероятно, являлась чрезмерная загрузка шины при работе в зоне «холодных» промахов (при тестировании на микротестах, именно «холодные» промахи играют основную роль).
Итак, результаты симуляции показали, что в среднем предвыборка позволяет избежать порядка 29% промахов в инструкционный кэш, что должно значительно ускорить обработку «промахов» в ИК при работе многозадачной системы.

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

В ходе данной части исследования было проведено сравнение эффективности аппаратуры предвыборки (для последовательного алгоритма, рассмотренного выше) для архитектуры с векторным счетчиком команд (АВСК) и традиционной суперскалярной архитектуры (ТСА) с неупорядоченным выполнением команд (Out-of-Order). Данная архитектура имеет схожую структуру блока выборки команд, что являлось определяющим фактором при выборе предмета сравнения. Более того, она использует схожую схему предвыборки строк в инструкционный кэш.

Рис.4 Упрощенная схема подсистемы памяти команд ТCА

Рис.5 Упрощенная схема подсистемы памяти команд АВСК

Во-первых, стоит заметить, что архитектура, с которой проводилось сравнение, не обладает параллелизмом на уровне инструкций. В ней могут присутствовать до двух инструкционных потоков команд (потоки в данной архитектуре представляют собой инструкции различных сред (процессов), между которыми должно проводиться переключение контекста), но в один момент в ней может выполняться только один из потоков. Кроме того, в ней присутствует блок детектирования циклов в коде инструкций, что позволяет кэшировать их, тем самым как бы пропуская, в этих случаях, аппаратуру выборки команд. Т.к. основной метрикой производительности можно считать количество промахов ([2]) в инструкционный кэш, а данный блок не оказывает на данную метрику серьезного воздействия (девиации составляют не более 1% от минимума), но зато «скрывает» большую часть попаданий в кэш, принято решение об отключении данной функциональности при проведении сравнений. Наконец, следует учитывать тот факт, что данная архитектура, в отличие от исследуемой, использует динамическое предсказание переходов, в то время как последняя - статическое при помощи компилятора, а также полноценное спекулятивное исполнение инструкций (т.е. имеется возможность исполнить противоположные по предикату ветки, как различные инструкционные потоки).

Сравнение производилось на кэшах одинакового размера (32Кб), использовались микротесты хорошо нагружающие инструкционный кэш.

Итак, перейдем к полученным результатам.

Рис.6 Сокращение времени исполнения тестов при использовании последовательного алгоритма предвыборки

Симуляция показала, что для архитектуры с векторным счетчиком команд данный алгоритм позволяет добиться большей скорости исполнения программ (Рис. 6): в среднем скорость исполнения увеличилась на 2,2% (в АВСК) и на 0,3% (в ТСА). Таким образом, для исследуемой архитектуры (АВСК) введение предвыборки оказалось более актуальным решением, что подтверждает теоретические ожидания (см. Введение).

Рис.7 Количество промахов в ИК на различных микротестах для различных архитектур, на 1000 команд

Рис.8 Отношение количества промахов в ИК к общему числу запросов на различных микротестах

Рис.9 Количество подкаченных инструкций на декодер(ы) на различных микротестах за один такт

На Рис. 7 и 8 представлены данные по количеству «промахов» в кэш, нормированных на количество исполненных инструкций (чтобы обусловить качественное сравнение различных архитектур), и отношение количества промахов в инструкционном кэше к общему количеству запросов в кэш (т.е. сумме «промахов» и «попаданий»). Также на Рис. 9 представлены данные по количеству инструкций, выбираемых блоком выборки инструкций за один такт: в АВСК за такт выбирается и подается на декодирующие устройства до 6-7 раз больше инструкций. На микротестах проявляются только «холодные промахи», т.е. те, которые возникают при первой загрузке программы в кэш. Они являются репрезентативными параметрами сравнения производительности кэшей первого уровня различных архитектур.
Полученные результаты для исследуемой архитектуры являются вполне удовлетворительными. АВСК подкачивает больше кода (и исполняет больше потоков, что видно на Рис. 9) и, разумеется, в абсолютном исчислении неизбежно превышение непосредственного количества «промахов» в среднем в 4 раза. Количество «промахов», нормированное относительно общего количества запросов в ИК, оказывается примерно одинаковым. Большее количество попаданий в кэш исследуемой архитектуры (и, следовательно, более низкий miss rate) вызвано большим средним размером инструкций (длина инструкции в среднем составляет 16 байт против 3,5-4 байт в суперскалярной архитектуре), а также «большей» спекулятивностью исполнения, как было замечено ранее.
В итоге, можно сделать вывод, что для исследуемой архитектуры (АВСК) введение аппаратуры предвыборки является актуальным решением, т.к. она использует большое число инструкционных потоков, чем традиционная (ТСА), а, следовательно, требуется подавать больше инструкций на декодирующее устройство. Производительность подсистемы памяти инструкций архитектуры с векторным счетчиком команд не уступает производительности традиционной суперскалярной архитектуры. Основная функция ИК в многопотоковой архитектуре по поддержанию как можно большего количества активных инструкционных конвейеров, также в целом выполнена (Рис. 9).

Заключение

В ходе работы было установлено, что основными параметрами, позволяющими оценить эффективность работы подсистемы памяти команд в целом, и инструкционного кэша в частности, являются количество «промахов» в кэше, количество «промахов» нормированное на общее число запросов в инструкционный кэш, а также количество подкачиваемых на декодирующее устройство инструкций.
В результате проведенного исследования были найдены оптимальные характеристики ИК для архитектуры с векторным счетчиком команд: 8-входовый кэш размером 32 Кб. Данная конфигурация даёт минимальное количество «промахов» в ИК и максимальное количество инструкций, выполняемых за такт (IPC).
Введение аппаратуры предвыборки способствует максимальной загрузке шины памяти, тем самым ускоряя обработку «промахов» в ИК. Изучение эффективности динамического последовательного алгоритма предвыборки строк в ИК показало что количество «промахов» в ИК может быть снижено в среднем на 29%, что составляет порядка 60% от максимально достижимой планки (50%). Основные причины: это многочисленные ситуации, когда строки выбранные блоком предвыборки не успевали подкачаться в кэш из-за большой загруженности шины подсистемы памяти, занятой обработкой запросов по истинным «промахам». В результате часть запросов не успевает обработаться. Другая часть запросов частично вытесняется новыми, которые продолжают генерироваться в случае «промахов».
По сравнению с традиционной суперскалярной архитектурой введение аппаратуры предвыборки является более эффективным решением: скорость выполнения программных тестов (в тактах) увеличивается на 2,2% в среднем. Подсистема памяти команд исследуемой архитектуры не уступает по производительности и позволяет эффективно использовать всю ширину многопотокового конвейера, подкачивая на декодирующие устройства в 6-7 раз больше инструкционного кода, чем в традиционной суперскалярной архитектуре.

Литература

[1] Таненбаум Э.”Архитектура компьютера”. 5-е изд. – СПб.:Питер, 2007.
[2] J.L. Hennessy and D.A. Patterson. “Computer architecture: a quantitative approach” -4th ed., 2007.
[3] Wei-Chung Hsu and James E. Smith. “A performance study of instruction cache prefetching methods”, IEEE Trans on computers, vol. 47, no. 5, May 1998.
[4] Yi Zhang, Steve Haga, Rajeev Barua. “Execution history guided instruction prefetching”, The Journal of Supercomputing, vol. 27, p. 129–147, 2004.
[5] Ayose Falcon, Alex, Ramirez, Mateo Valero. “Effective instruction prefetching via fetch prestaging”. Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS’05), 2005.
[6] L. Spracklen, Yuan Chou and S. G. Abraham Scalable Systems Group Sun Microsystems Inc., Sunnyvale, CA. “Effective instruction prefetching in chip multiprocessors for modern commercial applications”. Proceedings of the 11th Int’l Symposium on High-Performance Computer Architecture (HPCA-11 2005).
[7] J. Smith. “Sequential program prefetching in memory hierarchies”. IEEE, Computer, Dec. 1978.
[8] V. Veidenbaum, Qingbo Zhao, A. Shameer. “Non-secuentional instruction cache prefetching for multiple-issue processors”. International Journal of High Speed Computing, vol. 10, no. 1 (1999) pp. 115-140, 1999.
[9] A.J. Smith, “Cache Memories,” ACM Computing Surveys, Sept. 1982.
[10] Kenneth M. Wilson and Kunle Olukotun, Member, IEEE. “High bandwidth on-chip cache design”. IEEE Trans on computers, vol. 50, no. 4, April 2001.
[11] Intel Nehalem Architecture.
[12] What you need to know about Intel’s Nehalem CPU.
[13] ] Plot-Shell documentation.
[14] Закон Мура.
[15] SPEC CPU 2006.

Пожалуйста, обратитесь к странице Уведомление об оптимизации для более подробной информации относительно производительности и оптимизации в программных продуктах компании Intel.

Комментарии (8)

Обратная ссылка (1)

• Немного о лете или Как студенты проводят лето с пользой и с Интел – Блоги Intel® Software Network
  11.10.2010 01:07

Оставить комментарий  

Имя (обязательно)*

Электронная почта (обязательно; не будет отображено на этой странице)*

Ваш URL-адрес (необязательно)


Комментарий*