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

Теоретическое значение размераблока близко к практическому значению и равно 192.Так же, как и в эксперименте, посвященному блочному умножению матриц,для того чтобы уменьшить влияние ассоциативности кеш-памяти на размер блока,разместим матрицу блочно. В Таблице 6 приведены результаты численногоэксперимента, в котором замерялось время работы блочного алгоритма ФлойдаУоршалла с блочным размещением.49Таблица 6. Результаты профилировки блочного алгоритма Флойда-Уоршалла сблочным размещениемNdLL3 cacheL2 cacheL1 cacheElapsedTheoreticalmiss impactmissmiss(sec)time (sec)impactimpact20482720.261.10.5943.762151 25.7244920483360.280.850.6143.4894120484000.310.870.5143.375812 25.5597220484960.440.840.4743.320609 25.4919520485280.530.680.543.144292 25.4748420485600.880.680.4243.352389 25.4596820486242.70.480.4144.037547 25.4340320486883.90.10.5644.883257 71.8940125.62641Из эксперимента видно, что оптимальный размер блока равен 528.Теоретическое оптимальное значение размера блока близко к практическомузначению и равно 624.2.3.Анализ масштабируемости параллельного блочного алгоритма ФлойдаВажнойхарактеристикойпараллельногоалгоритмаявляетсяегомасштабируемость.

Параллельный алгоритм является масштабируемым, если приросте количества ядер он обеспечивает увеличение ускорения при сохранииэффективностииспользованияядер.Эффективностьвычислительного ядра определяется соотношениемSP использованияT (1, N ), гдеP  T ( P, N )T ( p, N ) - время работы последовательной программы, запущенной на процессорес количеством ядер равным p.Согласно формуле предлагаемой модели времени выполнения (3):50SP Texecution(1, N )  Tload (1, N )P  (Texecution( P, N )  Tload ( P, N ))Рассмотрим, чему равны значения Texecution( p, N ) и Tload ( p, N ) в случаепараллельного блочного алгоритма Флойда.

Время выполнения арифметическихопераций равно Texecution( p, N ) загрузки2 N3, где ν – это частота одного ядра. Времяp определяетсяследующейформулой:2 N N  d ( p) 3N 3Tload ( p, N )  p  3d ( p) 2 , гдеd ( p)pd ( p)   d ( p) - это оптимальный размер блока, при котором данные, используемыеразличными ядрами, не вытесняются из общей кеш-памяти. Еслипредположить, что кеш-память является полностью ассоциативной, тооптимальныйd ( p) размерблокаопределяетсяследующимобразом:CacheSize1 CacheSize3  p  sizeof (double) 26p µ - частота подкачки данных из оперативной памяти в кеш-память.Удобно определить величину  , которая показывает во сколько разбыстрее одно вычислительное ядро обрабатывает данные чем их подкачивает.Из приведенный соотношений следует, что CacheSize 36 начиная с p  23время загрузки данных будет занимать большевремени чем время выполнения арифметических операций. Минимальное теоретическое время работы алгоритма достигается при23 2  CacheSize  .Popt  3 3 Эффективность использования ядер монотонно убывает, начиная с p  1 .512.4.Статическое определение количества кеш-промаховКак было сказало ранее, время обращения к данным является намногобольшим,чемпрограммиствремяпривыполненияреализацииарифметическихпрограммыдолженопераций.представлять,Поэтомусколькообращений к памяти производит его программа во время своего выполнения.Ситуация усложняется тем, что одна и та же программа на разных компьютерахможет производить различное количество обращений к памяти.

Это связано с тем,чтосуществуюткомпьютерысразличнымипараметрамикеш-памяти(ассоциативность, размер, количество уровней, политика замещения элементов),данная задача становится очень трудоемкой.Информация по количеству кеш-промахов, возникших за время работыпрограммы, хранится в специальных регистрах – счетчиках производительностипроцессора (hardware performance counters).На основе данных счетчиковработают несколько известных динамических профилировщиков [53], [54], позволяющих подсчитать количество кеш-промахов, возникающих впрограмме. Они основаны на том, что входная программа запускается вспециальном режиме на целевом компьютере, и во время ее работы берутсязамеры счетчиков производительности.Основным недостатком такого подхода является то, что для анализапрограммынеобходимоеезапустить(собственно,поэтомутакиепрофилировщики называются динамическими). Некоторые приложения требуютмного времени для своей работы.

И поэтому профилировка таких программстановится очень долгой. Другим недостатком является зависимость отплатформы, на которой производится запуск программы. В качестве исключенияможно привести продукт Valgrind [55], позволяющий эмулировать требуемыйпроцессор и выполнять программу на нем.Последним важным недостатком динамической профилировки является то,что невозможно за один проход получить оценку количества кеш-промахов какфункцию от входных данных, т.к.

за один проход можно получить количество52кеш-промахов только для конкретного набора входных данных. Поэтомутребуется запускать программу на разных наборах входных данных.В данном разделе приводятся методы статического определения количествакеш-промахов. Изложенные методы одинаково работают как для иерархииуровней кеш-памяти, так и для кеш-памяти TLB. Поэтому с их помощьювозможно получить численные оценки количества обращений к основной памяти,количество промахов к промежуточным уровням кеш-памяти, количествопромахов к виртуальным страницам. Запуск исследуемых программ не требуется.Рассмотрим задачу определения количества промахов к уровню кеш-памятиверхнего уровня.

Будем предполагать, что политикой замещения элементов вкеш-памяти является политика LRU (Last Recently Used). Остальные параметрыкеш-памяти:1. CacheAssoc - ассоциативность кеш-памяти A2. BankCount - количество банков кеш-памяти B.3. CacheSize = BankCount*AssocПример 5.

Во фрагменте программыЛистинг 9. Чтение элементов одномерного массива с шагом.x = 0;for (j=0; j<N; j++)x += A[a*j+b]);на каждой итерации происходит чтение с шагом a элементов массива A.Количество кеш-промахов ограничено сверху числом N. Т.к. физически чтениеданных из оперативной памяти происходит блоками, то более точная формулаколичества кеш-промахов имеет вид:.N , a * DataTypeSize  BlockSizeNCacheMissCount  , a * DataTypeSize  BlockSizeBlockSize a * DatTypeSize53Пример 6. Фрагмент программыЛистинг 10. Повторное чтение элементов одномерного массива с шагом.for (i=0; j<N1; i++) {x=0for j=0; j<N; j++x += A[a*j+b];}отличается от фрагменты программы из Примера 5 тем, что в нем присутствуетвнешний цикл, который производит повторное обращение к считанным данным.Рассчитаем необходимые параметры кеш-памяти при которых повторные кешпромахи производиться не будут.

Введем несколько понятий:Определение1.Эффективноеколичествобанковпамяти( EffectiveBankCount ) - количество банков кеш-памяти, в которые отображаютсясчитываемые данные. Для вхождения массива A из Примера 6 оно равноBankCount EffectiveBankCount  BankCount . a * DataTypeSize BloclSizeОпределение2.Эффективнаяассоциативностькеш-памяти( EffectiveCasheAssoc ) – необходимая минимальная ассоциативность кеш-памяти, прикоторой повторное обращение к уже считанным в кеш данным не приводит ккеш-промаху. Для вхождения массива A из Примера 6 она равнаEffectiveCasheAssoc EffectiveBankCountN54Если в Примере 5 для вхождения A EffectiveCacheAssoc  CacheAssoc , то прикаждой новой итерации по i данные массива A будут повторно считываться вкеш-память и количество кеш-промахов возрастет в N1 раз.Пример 7.

Подсчитаем количество кеш-промахов для стандартного алгоритмаФлойда нахождения матрицы кратчайших расстояний:Листинг 11. Стандартный алгоритм Флойда-Уоршалла.for (int k=0; k < N; ++k)for (int i=0; i < N; ++i)for (int j=0; j < N; ++j)A[F(I, j)] (1) += MIN(A[F(i, j)] (2), A[F(i,k)] (3) + A[F(k,j)] (4))Рассмотрим случай, при котором элементы матрицы A хранятся по строкам,т.е.F (i, j )  i * N  jПодсчитаем количество кеш-промахов, которые произойдут во времявыполнения данного алгоритма.Сначала заметим, что внутри гнезда цикловпроизводится обращение только к элементам матрицы A.