stringtranslate.com

Шаблон доступа к памяти

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

Компьютерную память обычно называют « произвольным доступом », но при обходе программным обеспечением все равно будут обнаруживаться закономерности, которые можно использовать для повышения эффективности. Существуют различные инструменты, помогающие системным разработчикам [7] и программистам понять, проанализировать и улучшить шаблон доступа к памяти, включая VTune и Vectorization Advisor , [8] [9] [10] [11] [12] , включая инструменты для решения проблемы доступа к памяти графического процессора. узоры [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]

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

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

Случайный

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

Подходы

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

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

Контраст с местностью ссылки

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

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

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

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

Рекомендации

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