В вычислительной технике шаблон доступа к памяти или шаблон доступа ввода-вывода — это шаблон, с помощью которого система или программа считывает и записывает память на вторичном хранилище . Эти шаблоны различаются по уровню локальности ссылок и существенно влияют на производительность кэша , [1] а также имеют последствия для подхода к параллелизму [2] [3] и распределению рабочей нагрузки в системах с общей памятью . [4] Кроме того, проблемы с когерентностью кэша могут влиять на производительность многопроцессорных систем , [5] что означает, что определенные шаблоны доступа к памяти устанавливают потолок для параллелизма (который стремятся преодолеть многоядерные подходы). [6]
Компьютерная память обычно описывается как « случайный доступ », но обходы программным обеспечением все равно будут демонстрировать закономерности, которые можно использовать для повышения эффективности. Существуют различные инструменты, помогающие проектировщикам систем [7] и программистам понимать, анализировать и улучшать закономерности доступа к памяти, включая VTune и Vectorization Advisor , [8] [9] [10] [11] [12] включая инструменты для решения закономерностей доступа к памяти графического процессора [13]
Модели доступа к памяти также имеют последствия для безопасности , [14] [15] , что побуждает некоторых пытаться скрыть активность программы из соображений конфиденциальности. [16] [17]
Простейшей крайностью является последовательный шаблон доступа , где данные считываются, обрабатываются и записываются с помощью прямой инкрементной/декрементной адресации. Эти шаблоны доступа хорошо поддаются предварительной выборке .
Пошаговые или простые 2D, 3D шаблоны доступа (например, пошаговое прохождение многомерных массивов ) также легко предсказать, и они встречаются в реализациях алгоритмов линейной алгебры и обработки изображений . Циклическая мозаика является эффективным подходом. [19] Некоторые системы с DMA предоставляют пошаговый режим для передачи данных между субплиткой больших 2D массивов и памятью блокнота . [20]
Линейный шаблон доступа тесно связан с «пошаговым», где адрес памяти может быть вычислен из линейной комбинации некоторого индекса. Последовательное прохождение индексов с линейным шаблоном дает пошаговый доступ . Линейный шаблон доступа для записей (с любым шаблоном доступа для неперекрывающихся чтений) может гарантировать, что алгоритм может быть распараллелен, что используется в системах, поддерживающих вычислительные ядра .
Модели доступа к памяти ближайшего соседа появляются в моделировании и связаны с последовательными или шаговыми моделями. Алгоритм может проходить по структуре данных, используя информацию от ближайших соседей элемента данных (в одном или нескольких измерениях) для выполнения вычисления. Они распространены в физических симуляциях, работающих на сетках. [21] Ближайший сосед может также относиться к межузловой связи в кластере; физические симуляции, которые полагаются на такие локальные модели доступа, могут быть распараллелены с данными, разделенными на узлы кластера, с чисто ближайшей соседней связью между ними, что может иметь преимущества для задержки и пропускной способности связи. Этот вариант использования хорошо отображается на топологию сети тора . [22]
В 3D-рендеринге шаблоны доступа для текстурного отображения и растеризации небольших примитивов (с произвольными искажениями сложных поверхностей) далеки от линейных, но все еще могут демонстрировать пространственную локальность (например, в пространстве экрана или пространстве текстуры ). Это можно превратить в хорошую локальность памяти с помощью некоторой комбинации порядка Мортона [23] и тайлинга для текстурных карт и данных буфера кадра (отображение пространственных областей на строки кэша) или путем сортировки примитивов с помощью отложенного рендеринга на основе тайлов . [24] Также может быть выгодно хранить матрицы в порядке Мортона в библиотеках линейной алгебры . [25]
Шаблон доступа к памяти с разбросом объединяет последовательное чтение с индексированной/случайной адресацией для записи. [26] По сравнению со сбором, он может создавать меньшую нагрузку на иерархию кэша, поскольку элемент обработки может отправлять записи по принципу «запустил и забыл» (полностью минуя кэш), используя при этом предсказуемую предварительную выборку (или даже DMA) для своих исходных данных.
Однако распараллелить его может быть сложнее, поскольку нет гарантии, что записи не будут взаимодействовать [27] , и многие системы по-прежнему проектируются с учетом того, что аппаратный кэш будет объединять множество небольших записей в более крупные.
В прошлом метод прямого текстурирования пытался справиться со случайностью с помощью «записей», последовательно считывая информацию об исходной текстуре.
Консоль PlayStation 2 использовала обычное обратное текстурное отображение, но обрабатывала любую обработку scatter/gather "на чипе" с помощью EDRAM, в то время как 3D-модель (и множество текстурных данных) из основной памяти подавались последовательно через DMA. Вот почему в ней отсутствовала поддержка индексированных примитивов, и иногда требовалось управлять текстурами "заранее" в списке отображения .
В шаблоне доступа к памяти со сбором данных чтения адресуются или индексируются случайным образом, тогда как записи являются последовательными (или линейными). [26] Примером может служить обратное текстурное отображение , где данные могут быть записаны линейно по строкам сканирования , тогда как адреса текстур произвольного доступа вычисляются по пикселям .
По сравнению с scatter, недостаток в том, что кэширование (и обход задержек) теперь необходимо для эффективного чтения небольших элементов, однако его легче распараллелить, поскольку записи гарантированно не будут перекрываться. Таким образом, метод gather более распространен для программирования gpgpu , [27] где массивная потоковая обработка (обеспечиваемая параллелизмом) используется для сокрытия задержек чтения. [27]
Алгоритм может собирать данные из одного источника, выполнять некоторые вычисления в локальной или встроенной памяти и рассеивать результаты в другом месте. По сути, это полная работа конвейера GPU при выполнении 3D-рендеринга — сбор индексированных вершин и текстур и рассеивание затененных пикселей в пространстве экрана . Растеризация непрозрачных примитивов с использованием буфера глубины является «коммутативной», что позволяет переупорядочивать, что облегчает параллельное выполнение. В общем случае потребуются примитивы синхронизации.
На противоположной стороне находится действительно случайный шаблон доступа к памяти. Несколько многопроцессорных систем специализируются на работе с ними. [28] Подход PGAS может помочь, сортируя операции по данным на лету (полезно, когда проблема *заключается* в выяснении локальности несортированных данных). [21] Структуры данных, которые в значительной степени полагаются на отслеживание указателя, часто могут давать плохую локальность ссылок , хотя сортировка иногда может помочь. При наличии действительно случайного шаблона доступа к памяти может быть возможным разбить его (включая этапы рассеивания или сбора или другую промежуточную сортировку), что может улучшить локальность в целом; это часто является предпосылкой для распараллеливания .
Ориентированное на данные проектирование — это подход, призванный максимизировать локальность ссылок путем организации данных в соответствии с тем, как они обрабатываются на различных этапах программы, в отличие от более распространенного объектно-ориентированного подхода (т. е. организации таким образом, что структура данных явно отражает схему доступа). [29]
Локальность ссылки относится к свойству, демонстрируемому шаблонами доступа к памяти. Программист изменит шаблон доступа к памяти (переработав алгоритмы), чтобы улучшить локальность ссылки, [30] и/или увеличить потенциал для параллелизма. [26] Программист или проектировщик системы может создать фреймворки или абстракции (например, шаблоны C++ или функции более высокого порядка ), которые инкапсулируют определенный шаблон доступа к памяти. [31] [32]
Различные соображения относительно шаблонов доступа к памяти появляются в параллелизме за пределами локальности ссылок, а именно разделение чтения и записи. Например: даже если чтение и запись «совершенно» локальны, их может быть невозможно распараллелить из-за зависимостей ; разделение чтения и записи на отдельные области дает другой шаблон доступа к памяти, который может изначально показаться хуже в терминах чистой локальности, но желателен для использования современного параллельного оборудования. [26]
Локальность ссылки может также относиться к отдельным переменным (например, способность компилятора кэшировать их в регистрах ), в то время как термин «шаблон доступа к памяти» относится только к данным, хранящимся в индексируемой памяти (особенно в основной памяти ).
{{cite journal}}: Цитировать журнал требует |journal=( помощь )На практике шаблоны доступа к вводу-выводу столь же многочисленны, как и звезды