Шаблон доступа к памяти - Memory access pattern

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

Память компьютера обычно описывается как "произвольный доступ ", но программные обходы по-прежнему будут демонстрировать закономерности, которые можно использовать для повышения эффективности. Существуют различные инструменты, помогающие разработчикам систем[7] и программисты понимают, анализируют и улучшают схему доступа к памяти, включая VTune и Советник по векторизации,[8][9][10][11][12] включая инструменты для решения GPU шаблоны доступа к памяти[13]

Шаблоны доступа к памяти также имеют значение для безопасность,[14][15] что побуждает некоторых пытаться замаскировать деятельность программы для Конфиденциальность причины.[16][17]

Примеры

Последовательный и Линейный паттерны некорректно отрисовываются как дубликаты в некоторых публикациях; в то время как в реальном мире рабочие нагрузки содержат почти бесчисленные шаблоны[18]

Последовательный

Основная статья: Последовательный доступ

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

Шаговый

Шаговый или простые 2D, 3D шаблоны доступа (например, пошаговое многомерные массивы ) аналогично легко предсказать, и их можно найти в реализациях линейная алгебра алгоритмы и обработка изображений. Плитка петли это эффективный подход.[19] Некоторые системы с DMA предоставлен пошаговый режим для передачи данных между субтилью более крупными 2D массивы и блокнотная память.[20]

Линейный

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

Ближайший сосед

Шаблоны доступа к памяти ближайшего соседа появляются при моделировании и связаны с последовательными или последовательными шаблонами. Алгоритм может обходить структуру данных, используя информацию от ближайших соседей элемента данных (в одном или нескольких измерениях) для выполнения вычислений. Это обычное явление в физическом моделировании, работающем на сетках.[21] Ближайший сосед также может относиться к обмену данными между узлами в кластере; физическое моделирование, основанное на таких локальных шаблонах доступа, может быть распараллелено с данными, разделенными на узлы кластера, с обменом данными между ними только с ближайшим соседом, что может иметь преимущества для задержки и пропускной способности связи. Этот вариант использования хорошо отображается на топология сети тор.[22]

2D пространственно когерентный

В 3D рендеринг, шаблоны доступа для наложение текстуры и растеризация малых примитивов (с произвольными искажениями сложных поверхностей) далеки от линейных, но все же могут демонстрировать пространственную локальность (например, в экранное пространство или текстура пространства ). Это можно превратить в добро объем памяти местности через некоторую комбинацию приказ Мортона[23] и черепица для карты текстур и кадровый буфер данных (отображение пространственных областей на строки кэша) или путем сортировки примитивов через отложенный рендеринг на основе плитки.[24] Также может быть выгодно хранить матрицы в мортонном порядке в библиотеки линейной алгебры.[25]

Разброс

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

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

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

В PlayStation 2 Консоль использовала обычное обратное наложение текстуры, но обрабатывала любую обработку разброса / сбора «на кристалле» с помощью EDRAM, в то время как 3D-модель (и множество данных текстуры) из основной памяти последовательно загружалась через DMA. Вот почему ему не хватало поддержки индексированных примитивов, и иногда требовалось управлять текстурами "впереди" в список отображения.

Собрать

В собирать В шаблоне доступа к памяти операции чтения адресуются или индексируются случайным образом, а операции записи являются последовательными (или линейными).[26] Пример можно найти в обратное наложение текстуры, где данные могут быть записаны линейно по линии сканирования, а адреса текстур произвольного доступа рассчитываются по пиксель.

По сравнению с разбросом недостатком является то, что кэширование (и обход задержек) теперь необходимо для эффективного чтения небольших элементов, однако его легче распараллелить, поскольку записи гарантированно не перекрываются. Таким образом, метод сбора более распространен для gpgpu программирование,[27] где массовая многопоточность (включенная параллелизмом) используется для сокрытия задержек чтения.[27]

Комбинированный сбор и разброс

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

Случайный

Основная статья: Произвольный доступ

Противоположная крайность - это действительно случайный доступ к памяти. Несколько многопроцессорных систем специализируются на их решении.[28] В PGAS подход может помочь путем сортировки операций по данным на лету (полезно, когда проблема * заключается * в определении местоположения несортированных данных).[21] Структуры данных, которые сильно зависят от погоня за указателем часто может привести к плохим местонахождение ссылки, хотя сортировка иногда может помочь. При наличии действительно произвольной схемы доступа к памяти ее можно разбить (включая этапы разброса или сбора данных или другую промежуточную сортировку), что может улучшить локальность в целом; это часто является предпосылкой для распараллеливание.

Подходы

Дизайн, ориентированный на данные

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

Контраст с месторасположением ссылки

Местоположение ссылки относится к свойству, проявляемому шаблонами доступа к памяти. Программист изменит шаблон доступа к памяти (переработав алгоритмы), чтобы улучшить локальность ссылок,[30] и / или увеличить потенциал параллелизма.[26] Программист или системный разработчик может создавать структуры или абстракции (например, Шаблоны C ++ или функции высшего порядка ) это инкапсулировать определенный шаблон доступа к памяти.[31][32]

Различные соображения относительно шаблонов доступа к памяти проявляются в параллелизме за пределами локальности ссылки, а именно в разделении операций чтения и записи. Например: даже если операции чтения и записи "идеально" локальны, параллелизация может оказаться невозможной из-за зависимости; разделение операций чтения и записи на отдельные области приводит к другому шаблону доступа к памяти, который может сначала казаться хуже с точки зрения локальности, но желательно использовать современное параллельное оборудование.[26]

Местоположение ссылки может также относиться к индивидуальным переменным (например, способность компилятор кэшировать их в регистры ), в то время как термин "шаблон доступа к памяти" относится только к данным, хранящимся в индексируемой памяти (особенно основная память ).

Смотрите также

использованная литература

  1. ^ "дизайн, ориентированный на данные" (PDF).
  2. ^ Чан, Бёнхён; Шаа, Дана; Мистри, Перхаад и Каэли, Дэвид (27 мая 2010 г.). «Использование шаблонов доступа к памяти для повышения производительности памяти в архитектурах с параллельными данными». Транзакции IEEE в параллельных и распределенных системах. Нью-Йорк: IEEE. 22 (1): 105–118. Дои:10.1109 / TPDS.2010.107. eISSN  1558-2183. ISSN  1045-9219. S2CID  15997131. Уникальный идентификатор NLM 101212014.
  3. ^ Джефферс, Джеймс; Рейндерс, Джеймс; Содани, Авинаш (31.05.2016). xeon phi оптимизация. ISBN  9780128091951.
  4. ^ «Анализ энергии и производительности преобразований кода для шаблонов доступа к данным на основе PGAS» (PDF).
  5. ^ «Улучшение согласованной архитектуры кэша с помощью шаблонов доступа к памяти для встроенных многоядерных систем» (PDF).
  6. ^ "Intel Terascale" (PDF).
  7. ^ «анализ схем доступа к памяти».
  8. ^ "QUAD анализатор шаблонов доступа к памяти" (PDF).
  9. ^ «Dymaxion: Оптимизация схем доступа к памяти для гетерогенных систем» (PDF).
  10. ^ «Оценка схемы классификации доступа к памяти для указателей и числовых программ». CiteSeerX  10.1.1.48.4163. Цитировать журнал требует | журнал = (Помогите)
  11. ^ Мацубара, Юки; Сато, Юкинори (2014). «Анализ шаблонов доступа к оперативной памяти с помощью средства профилирования приложений». 2014 Второй международный симпозиум по вычислениям и сетям. С. 602–604. Дои:10.1109 / CANDAR.2014.86. ISBN  978-1-4799-4152-0. S2CID  16476418.
  12. ^ «Упорядочивание данных и кода: данные и макет».
  13. ^ «CuMAPz: инструмент для анализа шаблонов доступа к памяти в CUDA».
  14. ^ «Защита шаблонов доступа к памяти для устройств с ограниченными ресурсами» (PDF).
  15. ^ "понимание кэш-атак" (PDF).
  16. ^ «защита данных в облаке».
  17. ^ "повышение-облачной-безопасности с ---- не обращая внимания-барана".предложенная конструкция ОЗУ, исключающая уязвимости паттернов доступа к памяти
  18. ^ Чак Паридон. «Рекомендации по сравнительному анализу производительности хранилища - Часть I: Дизайн рабочей нагрузки» (PDF). На практике шаблонов доступа к вводу-выводу столько же, сколько звезд
  19. ^ "оптимизация для тайлинга и локализации данных" (PDF).В статье рассматривается мозаика цикла и его значение для параллельного кода
  20. ^ «Оптимальное разделение 2D-данных для DMA-передачи на MPSoC» (PDF).
  21. ^ а б "программирование разделенного глобального адресного пространства".охватывает случаи, когда PGAS является преимуществом, когда данные могут быть еще не отсортированы, например, при работе со сложными графиками - см. «наука по всему спектру нарушений».
  22. ^ «Количественная оценка локальности в шаблонах доступа к памяти приложений HPC» (PDF).упоминает шаблоны доступа ближайшего соседа в кластерах
  23. ^ «Проектирование и анализ архитектуры кэша для отображения текстур» (PDF).см. приказ Мортона, шаблон доступа к текстуре
  24. ^ "Мортон приказ ускорить текстурирование" (PDF).
  25. ^ "Матрицы порядка Morton заслуживают поддержки компиляторов, технический отчет 533" (PDF).обсуждает важность порядка Мортона для матриц
  26. ^ а б c d "gpgpu scatter vs gather". Архивировано из оригинал на 2016-06-14. Получено 2016-06-13.
  27. ^ а б c Драгоценные камни GPU. 2011-01-13. ISBN  9780123849892.имеет дело с "шаблонами доступа к памяти" и "шаблонами доступа к памяти" в тексте
  28. ^ «Cray и HPCC: сравнительные разработки и результаты за последний год» (PDF).см. глобальные результаты произвольного доступа для Cray X1. векторная архитектура для сокрытия задержек, не очень чувствительная к когерентности кеша
  29. ^ "дизайн, ориентированный на данные" (PDF).
  30. ^ "оптимизировать-структуры-данных-и-шаблоны-доступа-памяти-для-улучшения-локальности-данных".
  31. ^ «Механизм доступа к памяти на основе шаблонов для ускорителей в SoC» (PDF).
  32. ^ «Многоцелевая векторизация с помощью универсальной библиотеки MTPS C ++» (PDF).библиотека шаблонов C ++ для создания оптимизированных шаблонов доступа к памяти