Устранение узких мест производительности памяти в архитектуре фон Неймана с помощью глубокого обучения

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

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

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

Исследование в этой статье рассматривает введение модели нейронной сети на основе последовательности в архитектуру микропроцессора, направленной на решение проблем, связанных со стеной памяти, и применение обучения последовательности к сложной проблеме предварительной выборки памяти. Проблема упреждающей выборки памяти по сути может рассматриваться как проблема регрессии. Однако выходное пространство этой задачи очень велико и очень разрежено, и стандартные модели регрессии трудно использовать для получения хороших результатов. Авторы этой статьи рассматривают возможность использования некоторых из последних исследований в области создания изображений и языков, таких как PixelRNN и Wavenet. Эти результаты исследования дискретизируют пространство поиска, делая модель предварительной выборки памяти более похожей на модель нейронного языка, и используют ее в качестве отправной точки для создания средства предварительной выборки памяти нейронной сети. Модель нейронной сети, предложенная в этой статье, может успешно смоделировать выходное пространство задачи, реализовать предварительную выборку памяти нейронной сети и обеспечить значительно более высокую производительность, чем существующие традиционные аппаратные средства предварительной выборки. Кроме того, RNN, использованный в статье, может идентифицировать основную семантическую информацию приложения на основе траектории доступа к памяти приложения, что дает более интерпретируемые результаты.

жизненный опыт

Предварительная выборка памяти (предварительная выборка)

Средство предварительной выборки памяти — это аппаратная конструкция компьютера, которая использует исторические записи доступа к памяти для прогнозирования будущих моделей доступа к памяти. Существующие средства предварительной выборки памяти можно условно разделить на две категории. Один называется «предварительный выбор шага», а другой — «предварительный выбор корреляции». Предварительная выборка размера шага обычно используется в современных процессорах, и в последовательности фиксируется стабильная и повторяемая разница адресов (то есть разница между двумя соседними адресами памяти в последовательности). Например, при заданном шаблоне доступа к памяти (0, 4, 8, 12) разность адресов каждого доступа равна 4, тогда модуль предварительной выборки может предсказать следующий шаблон доступа к адресу (16, 20, 24).

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

Рекуррентная нейронная сеть (RNN)

Глубокое обучение подходит для многих задач прогнозирования последовательности, таких как распознавание языка и обработка естественного языка. Среди них RNN может моделировать долгосрочные зависимости. LSTM, широко используемый вариант RNN, решает проблему обучения стандартных RNN, распространяя внутренние состояния аддитивным, а не мультипликативным образом. LSTM состоит из скрытых состояний, состояние клетки, входные ворота, выходные воротаи ворота памятиКомпозиция представляет информацию, которую нужно сохранить, и информацию, которую нужно распространить на следующем временном шаге, соответственно. заданный временной шаги ввод x_N , состояние LSTN можно рассчитать с помощью следующей процедуры:

1 Вычислительный входной вентиль, выходной вентиль и вентиль памяти

$i_N=\sigma(W_i[x_n,h_{N-1}+b_i])$

$f_N=\sigma(W_f[x_N,h_{N-1}]+b_f)$

$o_N=sigma(W_o[x_N,h_{N-1}]+b_f)$

2 Обновите состояние ячейки

$c_N=f_N \odot c_{N-1}+i_N\odot tanh(W_c[x_N,h_{N-1}]+b_c)$

3 Рассчитайте скрытое состояние LSTM (выход)

$h_N=o_N \odot tanh(c_N)$

в, $[x_n,h_{N-1}]$ представляет объединение текущего ввода и предыдущего неявного состояния, $\odot$ представляет поэлементное умножение, $\sigma(u)=\frac{1}{1+exp(-u)}$ является сигмовидной нелинейной функцией. Приведенный выше процесс представляет собой форму обработки одного слоя LSTM, $W_{\{i,f,o,c\}}$ вес слоя, $b_{\{i,f,o,c\}}$ является отклонением. Слои LSTM могут быть сложены, а выходные данные слоя LSTM на временном шаге N могут использоваться в качестве входных данных другого слоя LSTM, что аналогично многослойной структуре в нейронной сети с прямой связью. Это делает модель более гибкой при использовании относительно небольшого количества дополнительных параметров.

определение проблемы

Относитесь к предварительной выборке как к проблеме прогнозирования

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

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

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

Исходная модель может использоваться на каждом временном шагеИспользуя два входных признака, т.е. вАдреса промахов кэша, сгенерированные шагами, и промахи кэша шага N+1, предсказанные ПК. Но есть проблема, адресное пространство приложения очень разрежено. Для обучающих данных для этой задачи пространственная сложность промаха кеша равна O(100M) величины, из которых только O(10M) Адрес промаха кеша появляется по адресу $2^{64}$ в физическом адресном пространстве. На рис. 1 показано использование стандартного SPEC. Ситуация с кешем тестового набора CPU2006 omnetpp, красные точки обозначают адреса промахов кеша. Этот пространственный диапазон является широким и сильно мультимодальным по своей природе, что бросает вызов традиционным моделям регрессии временных рядов. Например, хотя нейронные сети хорошо подходят для упорядочения входных данных, представление с плавающей запятой с ограниченной точностью приведет к значительной потере информации при упорядочении таких данных. Эта проблема влияет на моделирование входного и выходного слоев. В данной статье автор дает решение этой проблемы.

Рисунок 1Кэш отсутствует в наборе данных omnetpp. На рисунке показаны разреженные шаблоны доступа в различных масштабах.

Относитесь к предварительной выборке как к проблеме классификации

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

Однако есть проблема ожидания $2^{64}$ Существуют возможные цели softmax, поэтому необходимо указать режим квантования. Что еще более важно, предварительная выборка должна быть абсолютно точной, чтобы она работала. Это должно иметь место для обычных 64 байтов, и то же самое должно быть верно для страниц, которые обычно имеют размер 4096 байт. Прогнозы на уровне страницы дадут $2^{52}$ возможные цели. чтобы избежать более $2^{16}$ Каждое значение применяется softmax, и в некоторых исследованиях предлагается применять режим нелинейного квантования, чтобы уменьшить размерность пространства до 256 классов. Но эти обходные пути не относятся к проблеме, описанной в этой статье. Поскольку эти методы уменьшают разрешение адреса, предварительная выборка не может обеспечить требуемую высокую точность.

Из-за динамических граничных эффектов, таких как проблемы рандомизации адресного пространства (ASLR), несколько запусков одной и той же программы могут обращаться к разным исходным адресам. Однако одна и та же программа будет давать стабильное поведение для данного макета. Поэтому возможная стратегия состоит в том, чтобы предсказать разницу адресов $\Delta_N=Addr_{N+1}-Addr_{N}$ , а не напрямую предсказывать сам адрес. Как показано в таблице 1, разница адресов $\Delta_N$ Возможное появление адреса пространственно экспоненциально ниже, чем возможное появление адреса.

Таблица 1Статистика набора данных отслеживания программы, «М» для «миллионов»

Описание модели

В статье представлены две модели предварительной выборки на основе LSTM. Первая модель называется «встроенной моделью LSTM», она похожа на стандартную языковую модель. Вторая модель использует структуру пространства доступа к памяти для уменьшения размера словаря и уменьшения объема памяти, занимаемой моделью.

Встроить модель LSTM

Модель ограничивает размер выходного словаря и моделирует только наиболее часто встречающиеся интервалы адресов. Согласно Таблице 1, для получения оптимальной 50%-ной точности требуется всего лишь словарный запас. O(1000) величины или даже меньше. Словарь такого размера вполне соответствует возможностям стандартных языковых моделей. Исходя из этого, первая модель, предложенная в этой статье, ограничивает размер выходного словаря и выбирает 50 000 наиболее часто встречающихся уникальных различий адресов. Для входного словаря модель учитывает все различия адресов, которые встречаются в словаре не менее 10 раз. Дальнейшее расширение словарного запаса является сложной задачей как в статистическом, так и в численном отношении. Эти проблемы можно решить с помощью иерархических методов, подобных softmax, которые подлежат дальнейшему изучению.

Структура встроенного LSTM показана на рисунке 2. Модель представляет разницу между входным и выходным адресами как категориальное представление (т. е. горячее кодирование). шаг по времени, соответственно вложенные во вход $PC_{N}$ и $\Delta_{N}$ и объединить словарь встраивания, чтобы сформировать вход двухслойного LSTM. Кроме того, LSTM классифицирует словарь различий адресов и выбираетРазность адресов с наибольшей вероятностью используется для предварительной выборки. Методы классификации напрямую дают предсказанные вероятности, что является еще одним преимуществом по сравнению с традиционным оборудованием.

фигура 2Встроенная структура модели LSTM. где f и g представляют функцию вложения соответственно

В практических реализациях модуль предварительной выборки будет возвращать несколько прогнозов, поэтому между ними существует компромисс. Хотя большее количество предикторов увеличивает вероятность попадания в кэш на следующем временном шаге, из кэша можно удалить некоторые другие полезные элементы. В документе выбрана предварительная выборка 10 лучших прогнозов LSTM на каждом временном шаге. Здесь есть и другие возможности, такие как использование поиска луча для прогнозирования следующего временного шага или непосредственное изучение прямой операции, которая предшествует LSTM, чтобы давать прогнозы для временных шагов от N до N+n.

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

Комбинированная модель кластеризации и LSTM

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

Глядя на более узкую область адресного пространства, действительно существует богатый локальный контекст. С этой целью документ берет часть набора адресов из omnetpp и использует K-Means для его кластеризации в 6 различных регионов. Два из этих кластеров показаны на рисунке 3.

изображение 3Показаны два из шести кластеров K-средних для эталонного набора данных omnetpp. Доступы к памяти индивидуально окрашены в соответствии с компьютером, который сгенерировал доступ.

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

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

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

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

Рисунок 4Структура комбинированных моделей кластеризации и LSTM, а также обработка данных

эксперимент

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

Сбор экспериментальных данных

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

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

В эксперименте набор данных доступа к памяти делится на обучающий набор и тестовый набор, из которых 70% используется для обучения, а 30% — для тестирования. Обучайте каждый LSTM независимо от каждого набора данных. Встраиваемый LSTM обучается с помощью ADAM, а кластерный LSTM обучается с помощью Adagrad. Используемые гиперпараметры см. в приложении к исходному тексту.

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

сравнение моделей

Эксперименты сравнивают предварительную выборку на основе LSTM с двумя аппаратными предварительными выборками. Первый — это стандартный предварительный выбор потока. Чтобы сохранить согласованность модуля предварительной выборки с машинным обучением и традиционного модуля предварительной выборки, в эксперименте моделируется аппаратная структура, поддерживающая до 10 одновременных потоков. Второй - предсказатель GHB PC/DC. Это ассоциативный префетчер, использующий две таблицы. Одна таблица используется для хранения ПК, а сохраненные ПК используются в качестве указателей для выполнения второй таблицы. Во второй таблице хранится историческая информация о различиях адресов. При каждом доступе модуль предварительной выборки GHB переходит ко второй таблице и выполняет предварительную выборку разницы адресов в истории. Ассоциативные упреждающие выборки хорошо работают со сложными шаблонами доступа к памяти с меньшим отзывом, чем потоковые упреждающие выборки.

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

Рисунок 5Сравнение точности и отзыва между традиционными предварительными выборками и предварительными выборками LSTM. где "Geomean" означает среднее геометрическое

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

$\Delta s$ Сравните прогнозы ПК

Этот эксперимент отдельно удаляет входные данные из встроенной модели LSTM. $\Delta s$ или ПК. План эксперимента был предназначен для определения относительного содержания информации, содержащейся в различных входных модулях.

Результаты эксперимента показаны на рисунке 6. Как видно из рисунка, в разнице между ПК и адресом содержится много прогностической информации. Информация предсказания в последовательности разности адресов может повысить точность, в то время как последовательность ПК помогает улучшить отзыв.

Изображение 6Встраивание LSTM-моделей различных входных модулей, сравнение точности и полноты

семантика интерпретатора

Основное преимущество модели обучения шаблонам по сравнению с предикторами на основе справочных таблиц заключается в том, что смысл данных может быть получен путем проверки модели. На рис. 7 показано $(\Delta,PC)$ t-SNE визуализация вложения каскадов на mcf.

Рисунок 7 $(\Delta,PC)$ Визуализация t-SNE каскадных строк, встроенных в mcf, показанных разными цветами по инструкции

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

Заключение и дальнейшая работа

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

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

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

Наконец, по влиянию на производительность приложений можно оценить эффективность предварительных выборок RNN. В идеале RNN напрямую оптимизируют производительность приложений. Одним из соображений является использование методов обучения с подкреплением в качестве метода обучения RNN в динамических средах.

Конечно, предварительная выборка памяти — не единственная область компьютерных систем, где требуется спекулятивное выполнение. Всякий раз, когда речь идет о поведении ветвления, необходимо делать прогнозы. Алгоритм ветвления используется для перенаправления адреса потока управления, а алгоритм замены кеша предсказывает наилучшую замену из кеша, когда необходимо принять решение о замене. Если эвристические правила в традиционных микроархитектурах заменить системами машинного обучения, поведение систем можно будет лучше понять, исследуя такие системы. Эксперименты с t-SNE в статье дают лишь поверхностные наблюдения, показывающие, что шаблоны доступа к памяти являются показателем поведения программы. Это показывает, что использование недавно исследованных систем RNN предоставляет большое количество возможностей для исследования архитектуры компьютерных систем.

Посмотреть исходный текст статьи: Learning Memory Access Patterns

благодарныйЦай ФанфанОбзор этой статьи.