Диссертация (Оптимизация размещения массивов в общей памяти), страница 4

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

Перед трансляцией адреса виртуальной страницы в физическийадрес производится проверка на его наличие в кеш-памяти TLB. Если адресвиртуальной страницы найден в кеш-памяти TLB, то такая ситуация называетсяпопаданием в кеш-память TLB. При попадании в кеш-память TLB трансляцияадреса виртуальной страницы не производится. В случае, если искомый адресвиртуальной страницы не найден в кеш-памяти TLB, то возникает ситуацияпромаха к кеш-памяти TLB, и начинается процесс трансляции виртуальногоадреса в физический. Ввиду того, что размер кеш-памяти TLB невелик (128-51221записей), физически он часто реализуется в виде полностью ассоциативной кешпамяти. Особенностью кеш-памяти TLB является то, что при обработке промаха ккеш-памяти TLB процессор не может выполнять другие инструкции и находится всостоянии ожидания.

Более того время обработки промаха к кеш-памяти TLB внесколько раз больше чем время обработки промаха к кеш-памяти.1.2.Увеличение временной локальности данных. Метод тайлинга.Большинствосовременныхпроцессоровспособныэффективнозадействовать кеш-память при выполнении программ, имеющих высокуювременную локальность данных [4]. Временная локальность данных заключаетсяв повторном использовании одних и тех же данных за короткий промежутоквремени.

Если программа имеет высокую временную локальность данных, тоданные, к которым производится повторное обращение, не успевают вытеснятьсяиз кеш-памяти. В результате количество обращений к основной памятиснижается.Одним из основных способов увеличения временной локальности данныхявляется метод тайлинга (tiling) [6], [2], [3]. Тайлинг [78] – это преобразованиеалгоритмадляполучениямакроопераций.Получаемыеврезультатепреобразования макрооперации называются зерном вычислений или тайла.Множество операций алгоритма, составляющих зерно вычислений, выполняетсяатомарно, как одна единица вычислений.При использовании тайлинга возникает проблема выбора оптимальногоразмера блока, при котором блочная программа будет работать максимальнобыстро.

Существуют алгоритмы ([7]), которые асимптотически максимальноэффективно используют кеш-память без учета точных размеров кеш-памяти икеш-линеек. Их преимуществом является то, что они легко переносимы на разныевычислительные системы, поддерживающие кеш-память. Тем не менее былопоказано [8], что такие алгоритмы имеет меньшую производительность чемалгоритмы, в которых параметры кеш-памяти используются явно.22В качестве примера использования тайлинга рассмотрим задачу умноженияматриц.Листинг 1. Стандартный алгоритм умножения матрицfor (i=0; i<N; ++i)for (k=0; k<N; ++k)for (j=0; j<N; ++j)C[i][j] = C[i][j] + A[i][k] * B[k][j];Результатом применения тайлинга является следующий блок кода:Листинг 2. Блочное умножение матриц.for (ii = 0; ii < SIZE; ii += BLOCK_SIZE)for (kk = 0; kk < SIZE; kk += BLOCK_SIZE)for (jj = 0; jj < SIZE; jj += BLOCK_SIZE)for (i = ii; i < ii + BLOCK_SIZE && i < SIZE; i++)for (k = kk; k < kk + BLOCK_SIZE && k < SIZE; k++)for (j = jj; j < jj + BLOCK_SIZE && j < SIZE; j++)C[i][j] = C[i][j] + A[i][k] * B[k][j];Впервые тайлинг был использован в середине 80-х годов [5].

В статьеподчеркивается, что использование тайлинга в последние десятилетия сталокритически важным для достижения высокой производительности программлинейной алгебры.Недостатком тайлинга является то, что при его использовании меняетсяпорядок выполнения операций. Поэтому не всегда очевидно, является ли блочнаяпрограмма эквивалентной исходной.Количество умножений в стандартном алгоритме умножения квадратныхматриц равно n3, где n – размер матриц. Или (N/2)3/2, где N – количество входныхданных (количество элементов двух квадратных матрицы размерности n).23Если матрица размера n*n не помещается в кеш-памяти, то в кеш-памятьпопадут строка матрицы A и столбец матрицы B (все, что необходимо длявыполнения внутреннего цикла).

Над данными, попавшими в кеш-память,программавыполняетсячастью,вычисляющейскалярныепроизведения.Процессор недогружен, ожидает поступления данных.Оценим количество пересылок данных между оперативной памятью и кешпамятью. Если в кеш-памяти находится вектор-строка матрицы A, и к немуподкачиваются векторы-столбцы матрицы B, то каждый столбец матрицы B будетподкачиваться n раз. Итого, чтений из оперативной памяти будет порядка n3.Теперь рассмотрим блочный алгоритм умножения квадратных матриц.Сложность по умножениям блочного алгоритма такая же, как и у стандартного n3.Размер блоков подбирается так, чтобы умножаемые блоки поместились в кешпамяти.

Оценим количество пересылок данных между оперативной памятью икеш-памятью. Если в кеш-памяти находится блок матрицы A и к немуподкачиваются блоки матрицы B , то каждый блок матрицы Bбудетподкачиваться n/m раз. Итого, чтений блоков матрицы B из оперативной памятибудет порядка (n/m)3. Поскольку каждый блок содержит m2 чисел, общееколичество чтений чисел матрицы B из оперативной памяти будет порядка n3/m это в m раз меньше, чем при обычном умножении.В [41] подробно описаны методы подсчета локальности данных, а такжеалгоритмвыборацепочкипреобразований,приводящийкувеличениюлокальности данных.Метод разбиения задачи на подзадачи – это метод создания эффективныхпрограммдлякомпьютеровсиерархиейпамяти.Этотметодможнорассматривать, как обобщение перехода к блочному коду.Иерархия архитектуры предполагает адекватное ей разбиение задачи наподзадачи – на вычислительном устройстве каждого уровня архитектурырешается подзадача соответствующего уровня иерархии подзадач.

Разбиениезадач на подзадачи необходимо даже для простой иерархической структурыпамяти, состоящей из большой, но медленной, и из быстрой, но малой по объему24памяти. Адекватное разбиение задачи на подзадачи определяет эффективностьвсей высокопроизводительной системы. Компиляторы и процессоры выполняюттакое разбиение автоматически, но, практически, без минимизации обращений кпамяти – хорошую оптимизацию программист должен выполнять сам.Увеличение пространственной локальности данных. Переразмещение1.3.данныхВ предыдущем разделе было введено понятие временной локальностиданных. Другим важным понятием является пространственная локальностьданных [4].

Принцип пространственной локальности данных заключается вчастом обращении к данным, хранящимся в одном месте памяти. Как следует изопределения пространственной локальности данных, временная локальностьданных является ее частным случаем.1.3.1.Нестандартные размещения данныхВ современных языках программирования используются стандартныеразмещения массивов - по строкам (row-major) либо по столбцам (column-major),которые еще называются каноническими размещениями (Canonical layouts) [10].Существует также мортоновское размещение матриц. При таком методеразмещения матрица разбивается на 4 одинаковых блока.

Элементы одного блокахранятся в памяти рядом. Далее каждый блок также разбивается на 4 подблока,элементы которого хранятся рядом. Этот процесс разбиения блоков на подблокивыполняется рекурсивно до тех пор, пока размер разбиваемого блока не станетравен 1. Из определения следует, что мортоновское размещение применимотолько к квадратным матрицам, размер которых является степенью 2. На Рисунке4 представлен пример использования мортоновского размещения для матрицы8x8.

Числа, которыми отмечены элементы матрицы, означают адреса храненияэлементов в линейной памяти после размещения.25Рис. 4: Мортоновское размещение матрицы 8x8. На месте элементов.матрицы расположен относительный адрес соответствующего элемента.Мортоновское размещение может использоваться в целях уменьшенияколичества кеш-промахов [20] для различных приложений, выполняющих многоопераций над данными.

В частности, в приложениях обработки графики [21] иприложениях баз данных [22].В [9] приводится результаты оптимизации ссылочных структур хранения.Предложены 3 методики оптимизации: clustering (кластеризация), сжатие(compression) и раскраска (coloring). В методе кластеризации используетсянестандартное размещение данных, при котором используемые вместе элементыструктур находятся в одной кеш-линейке. В частности, в случае кластеризацииэлементов дерева в одной кеш-линейке стоит хранить поддерево.Если кэлементам производится параллельный доступ, то такие элементы размещаются вразных банках кеш-памяти. Использование данных методик позволило ускоритьпакеты RADIANCE на 42% и VIS на 27%.Важностьподдержкинестандартныхразмещенийвязыкахпрограммирования отмечается в [10].

Исследуется производительность 4D- имортоновского размещений. При использовании нестандартных размещений26добавляются незначительные временные расходы (2-5% от времени работыпрограммы),втовремякакскоростьвыполнениясамойпрограммыувеличивается в 1.1-2.5 раза (блочное умножение матриц, алгоритм Штрассенаумножения матриц, разложение Холецкого, сжатие изображения с помощьювейвлета Хаара).В [12] приводятся результаты сравнения блочно-рекурсивного размещения(Morton data layout) данных со стандартными размещениями. Было взятонесколько тестовых программ (Alternating Direction Implicit Kernel; умножениематриц; решение двумерной задачи Дирихле уравнения Лапласа методом Якоби;разложение Холецкого).