В вычислениях шаблон доступа к памяти или шаблон доступа к вводу-выводу — это шаблон, с помощью которого система или программа считывает и записывает память во вторичном хранилище . Эти шаблоны различаются уровнем локальности ссылок и существенно влияют на производительность кэша [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 использовала обычное обратное наложение текстур, но обрабатывала любую обработку разброса/сборки «внутри кристалла» с использованием EDRAM, в то время как 3D-модель (и множество данных текстур) из основной памяти последовательно подавалась по DMA. Вот почему в нем отсутствовала поддержка индексированных примитивов, и иногда требовалось управлять текстурами «заранее» в списке отображения .
В шаблоне доступа к памяти со сбором операции чтения адресуются или индексируются случайным образом, а записи являются последовательными (или линейными). [26] Примером может служить обратное отображение текстур , где данные могут быть записаны линейно по строкам сканирования , в то время как адреса текстур произвольного доступа рассчитываются для каждого пикселя .
По сравнению с разбросом, недостатком является то, что кэширование (и обход задержек) теперь необходимо для эффективного чтения небольших элементов, однако его легче распараллелить, поскольку записи гарантированно не перекрываются. Таким образом, подход сбора более распространен для программирования gpgpu , [27] где массивная многопоточность (обеспечиваемая параллелизмом) используется для сокрытия задержек чтения. [27]
Алгоритм может собирать данные из одного источника, выполнять некоторые вычисления в локальной памяти или памяти чипа и распределять результаты по другим местам. По сути, это полная работа конвейера графического процессора при выполнении 3D-рендеринга — сбор индексированных вершин и текстур и рассеяние затененных пикселей в экранном пространстве . Растеризация непрозрачных примитивов с использованием буфера глубины является «коммутативной», позволяя переупорядочивать, что облегчает параллельное выполнение. В общем случае потребуются примитивы синхронизации.
Противоположной крайностью является действительно случайный шаблон доступа к памяти. Некоторые многопроцессорные системы специализируются на таких задачах. [28] Подход PGAS может помочь в сортировке операций по данным на лету (полезно, когда проблема *является* выяснением местоположения неотсортированных данных). [21] Структуры данных, которые в значительной степени полагаются на погоню за указателями, часто могут привести к плохой локальности ссылок , хотя сортировка иногда может помочь. Учитывая действительно случайный шаблон доступа к памяти, его можно разбить на части (включая этапы разброса или сбора или другую промежуточную сортировку), что может улучшить локальность в целом; это часто является предпосылкой для распараллеливания .
Проектирование, ориентированное на данные, — это подход, призванный максимизировать локальность ссылок путем организации данных в соответствии с тем, как они просматриваются на различных этапах программы, в отличие от более распространенного объектно-ориентированного подхода (т. е. организации, при которой расположение данных явно отражает шаблон доступа). [29]
Локальность ссылки относится к свойству, проявляемому шаблонами доступа к памяти. Программист изменит шаблон доступа к памяти (переработав алгоритмы), чтобы улучшить локальность ссылок [30] и/или увеличить потенциал параллелизма. [26] Программист или разработчик системы может создавать структуры или абстракции (например, шаблоны C++ или функции высшего порядка ), которые инкапсулируют конкретный шаблон доступа к памяти. [31] [32]
Различные соображения относительно шаблонов доступа к памяти проявляются в параллелизме за пределами локальности ссылок, а именно в разделении чтения и записи. Например: даже если чтение и запись «совершенно» локальны, распараллеливание может оказаться невозможным из-за зависимостей ; разделение операций чтения и записи на отдельные области приводит к другому шаблону доступа к памяти, который поначалу может показаться хуже с точки зрения чисто локальности, но желательно использовать современное параллельное оборудование. [26]
Локальность ссылки может также относиться к отдельным переменным (например, способность компилятора кэшировать их в регистрах ), тогда как термин «шаблон доступа к памяти» относится только к данным, хранящимся в индексируемой памяти (особенно в основной памяти ).
{{cite journal}}
: Требуется цитировать журнал |journal=
( помощь )На практике шаблонов доступа к вводу-выводу так же много, как звезд.