Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

Примеры [ править ]

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

Последовательный [ править ]

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

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

Strided [ править ]

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

Линейный [ править ]

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

Ближайший сосед [ править ]

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

2D пространственно согласованный [ править ]

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

Scatter [ править ]

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

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

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

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

Собрать [ править ]

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

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

Комбинированный сбор и разброс [ править ]

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

Случайно [ править ]

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

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

Подходы [ править ]

Дизайн, ориентированный на данные [ править ]

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

Контраст с месторасположением ссылки [ править ]

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

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

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

См. Также [ править ]

  • Gather-scatter (векторная адресация)
  • Местонахождение ссылки
  • Параллельные вычисления
  • Рабочий набор

Ссылки [ править ]

  1. ^ "дизайн, ориентированный на данные" (PDF) .
  2. ^ Jang, Byunghyun; Шаа, Дана; Мистри, Перхаад и Кейли, Дэвид (27 мая 2010 г.). «Использование шаблонов доступа к памяти для повышения производительности памяти в архитектурах с параллельными данными». Транзакции IEEE в параллельных и распределенных системах . Нью-Йорк: IEEE . 22 (1): 105–118. DOI : 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 .  Цитировать журнал требует |journal=( помощь )
  11. ^ Мацубара, Юки; Сато, Юкинори (2014). «Анализ шаблонов доступа к оперативной памяти с помощью средства профилирования приложений». 2014 Второй международный симпозиум по вычислениям и сетям . С. 602–604. DOI : 10,1109 / CANDAR.2014.86 . ISBN 978-1-4799-4152-0. S2CID  16476418 .
  12. ^ «Упорядочивание данных и кода: данные и макет» .
  13. ^ «CuMAPz: инструмент для анализа шаблонов доступа к памяти в CUDA» .
  14. ^ «Защита шаблонов доступа к памяти для устройств с ограниченными ресурсами» (PDF) .
  15. ^ "понимание кэш-атак" (PDF) .
  16. ^ «защита данных в облаке» .
  17. ^ "повышение-облачной-безопасности с ---- не обращая внимания-барана" .предложенная конструкция ОЗУ, исключающая уязвимости паттернов доступа к памяти
  18. ^ Чак Paridon. «Рекомендации по сравнительному анализу производительности хранилища - Часть I: Разработка рабочих нагрузок» (PDF) . На практике шаблонов доступа к вводу-выводу столько же, сколько звезд
  19. ^ «Оптимизация для тайлинга и локализации данных» (PDF) . В статье рассматривается мозаика цикла и ее значение для параллельного кода
  20. ^ «Оптимальное разделение 2D-данных для передачи DMA на MPSoC» (PDF) .
  21. ^ a b «Программирование глобального адресного пространства с разделами» .охватывает случаи, когда PGAS является преимуществом, когда данные могут быть еще не отсортированы, например, при работе со сложными графиками - см. «наука по всему спектру нерегулярностей».
  22. ^ «Количественная оценка локальности в шаблонах доступа к памяти приложений HPC» (PDF) . упоминает шаблоны доступа к ближайшему соседу в кластерах
  23. ^ «Дизайн и анализ архитектуры кэша для отображения текстур» (PDF) . см. приказ Мортона, шаблон доступа к текстуре
  24. ^ "Мортон приказ ускорить текстурирование" (PDF) .
  25. ^ «Матрицы порядка Мортона заслуживают поддержки компилятора, технический отчет 533» (PDF) . обсуждает важность порядка Мортона для матриц
  26. ^ a b c d "gpgpu scatter vs gather" . Архивировано из оригинала на 2016-06-14 . Проверено 13 июня 2016 .
  27. ^ a b c Драгоценные камни графического процессора . 2011-01-13. ISBN 9780123849892.имеет дело с "шаблонами доступа к памяти" и "шаблонами доступа к памяти" в тексте
  28. ^ «Cray и HPCC: сравнительные разработки и результаты за последний год» (PDF) . см. глобальные результаты произвольного доступа для Cray X1. векторная архитектура для сокрытия задержек, не очень чувствительная к когерентности кеша
  29. ^ "дизайн, ориентированный на данные" (PDF) .
  30. ^ "оптимизировать-структуры-данных-и-шаблоны-доступа-памяти-для-улучшения-локальности-данных" .
  31. ^ «Механизм доступа к памяти на основе шаблонов для ускорителей в SoC» (PDF) .
  32. ^ «Многоцелевая векторизация с помощью универсальной библиотеки MTPS C ++» (PDF) . библиотека шаблонов C ++ для создания оптимизированных шаблонов доступа к памяти