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

Предположим, что d нацело делится на LK, и d < VK. ТогдаT2 (n)  N 3  (k0k 12  k 2 )d  Lk d(9)Разделим T1 ( n) на T2 (n) и получим ускорение, полученное за счет разбиенияна подзадачи:T1 (n)T2 (n)k 0  k1  k 2k0k 12  k 2d  Lkd(10)40Скорость доступа к данным можно увеличить еще больше, если матрицыразместить блочно, выбрав размер блока равным d. В этом случае формула (8)примет вид3d2d2NT3 (n)     (k 0  k1  k2  d 3 )LkVkd(11)Как видно из формул (8) и (11) имеет место следующая теорема:Теорема. Применение блочного размещения матриц к блочному алгоритмуd  Lk позволяет уменьшить количество промахов к кеш-памяти в   раз, а к кешdLkd Vk памяти TLB – в   раз.dVk2.1.Анализ блочного алгоритма умножения матрицРассмотрим задачу определения оптимального уровня кеш-памяти длякоторого следует производить тайлинг.2.1.1.Определение уровня кеш-памяти, для которого оптимальнопроизводить тайлингБудем предполгалать, что кеш-память каждого уровня является полностьюассоциативной.

Формула времени выполнения (2) блочного алгоритма умноженияматриц имеет следующий вид:T (n, L)  Texecution(n)  Tload (n, L)(12)Где L – уровень кеш-памяти под который производится тайлинг, Texecution(n)- время выполнения всех арифметических операций, Tload (n, L) - время загрузкииспользуемых данных в уровень кеш-памяти L. Время подкачки данныхвыражается через время подкачки одного блока следующим образом:41 nTload n, L   d L3  T (d )loadL(13)Если кеш-память каждого уровня является полностью ассоциативной, тоdL .LSizeDataTypeSize(14)Это связано с тем, что в кеш-память должен помещаться только блокматрицы B.Теорема:Отношениевремензагрузкиданныхвуровникеш-памятиобратнопропорционально корню квадратному отношения размеров уровней кешпамяти и прямопропорционально отношению латентностей уровней кеш-памяти:3 n  L1 Size    1  d 1   DataTypeSizeTload n, L1 Tload (n, L2 )  n d21 L2 Size  2  1 32 L2 Size  L1 Size    2   DataTypeSize(15)Параметр  1 определяет время закачки данных из кеш-памяти L1 врегистры процессора.

Параметр  2 соответственно определяет время закачкиданных из кеш-памяти L2 в регистры. Найдем теперь уровень кеш-памяти, длякоторого время загрузки данных будет минимально при использовании тайлинга:1Tload n, L2   3  210  2 1010  8   12 *1Tload (n, L3 )  2  22221Tload n, L1   3  210  2 33  5   12 2 *1Tload (n, L3 )  2  2222Tload n, L1   2 8Tload (n, L2 )  2 512 33   2 3 *  110 10Tload (n, L3 )  Tload n, L1   Tload (n, L2 )42Таким образом, минимальное общее время закачки данных достигается притайлинге, проводимом для кеш-памяти L3. Следующий уровень кеш-памяти, длякоторого следует производить тайлинг, является кеш-память L1.Рассмотрим теперь задачу определения оптимального размера блока дляконкретного уровня кеш-памяти.2.1.2.Определение оптимального размера блока для блочного алгоритмаумножения матрицПредположим, что тайлинг производится под кеш-память L3. В этом случае,если кеш-память L3 является полностью ассоциативной, то оптимальный размерблока равенdL L3 SizeDataTypeSize(16)Рассмотрим теперь случай, когда кеш-память L3 не является полностьюассоциативной.

Пусть step – минимальное положительное число, такое что(step  N  DataTypeSize)( L3 BankCount  CacheLineSize)(17)В этом случае элементы каждой строки матрицы с номером кратным числуstep будут отображаться в одни и те же кеш-линейки.ЕслиN  2048 ,тоstep  16иприразмереблокаd  L3 Assoc  step  12  16  192 элементы одного блока уже начнут вытеснять другдруга из кеш-памяти, и тем самым существенно увеличится количество кешпромахов. Таким образом, оптимальный размер блока d  192 .Для блочного умножения матриц со стандартным размещением данныхимеет место следующая формула времени выполнения:Если d  192 , то4323 n  1  d  3  memory _ latency d  cache _ latencyT (n)      d 3  2  k CacheLineS izeCacheLineS ized   3(18), иначеT ( n) n 3  memory _ latency cache _ latency 2k  CacheLineS izeCacheLineS izeГде ʋ - частота процессора, k -(19)время выполнения арифметическихопераций.

Точность данной формулы подтверждается результатами численногоэксперимента. В данном эксперименте подсчитывается время выполненияпрограммы, реализующей блочное умножение матриц для разных размеров блока:Таблица 3. Результаты профилировки блочного умножения матрицNdLL3 cache L2 cacheL1 cacheElapsed (sec)Theoreticalmissmissmissimpactimpactimpact2048 640.713.60.01464.44380527.397922048 960.431.90.6963.76399426.66842048 1280.511.80.663.26770526.30372048 1600.611.40.6863.40907526.08492048 1922.30.670.9465.79833225.93902048 2244.10.250.8669.21062771.894time (sec)Данный эксперимент, а также последующие эксперименты данной главыпроведены с помощью инструмента Intel Vtune Amplifier [53]. На базе собранных с помощью него профилей работы программ былирассчитаны следующие характеристики программы:1.

Влияние кеш-промахов к L1-кешу.442. Влияние кеш-промахов к L2-кешу.3. Влияние кеш-промахов к L3-кешу.Каждая из характеристик показывает относительное количество кешпромахов к определенному уровню кеш-памяти, произошедших во времявыполнения программы. Чем больше это значение, тем больше влияние кешпромаховкконкретномууровнюкеш-памятинаобщеепадениепроизводительности программы.Из эксперимента видно, что оптимальный размер блока равен 128.

ВТаблице 3 приведено также теоретическое время работы программы, котороевычисляется с использованием формул 18-19. Теоретическое значение размераблока близко к практическому значению и равно 192.Для того чтобы уменьшить влияние ассоциативности кеш-памяти на размерблока, разместим матрицы блочно. В Таблице 4 приведены результатычисленного эксперимента, в котором замерялось время работы блочногоалгоритма умножения матриц, размещенных блочно.45Таблица 4.

Результаты профилировки блочного умножения матриц с блочным размещениемNdLL3L2 cache L1 cacheElapsedTheoreticalcachemissmiss(sec)time (sec)missimpactimpactimpact2048640.160.0271.453.200717 27.397920482560.250.370.8548.364546 25.756620483840.180.430.7147.757125 25.574320485120.290.380.7547.244979 25.483120485680.520.380.7448.283772 25.456120486241.30.260.749.350072 25.434020487682.60.090.7349.797658 71.8940204810242.50.0230.3450.419416 71.8940Из эксперимента видно, что оптимальный размер блока равен 512.Оптимальное теоретическое значение размера блока близко к практическомузначению и равно 624.2.2.Определение оптимального размера блока для блочного алгоритмаФлойда-УоршаллаВ данном разделе будут приведены оценки времени выполнения дляалгоритма Флойда-Уоршалла поиска кратчайших расстояний между вершинамиграфа.

Стандартная реализация алгоритма Флойда-Уоршалла, представлена ниже:Листинг 7. Стандартный алгоритм Флойда-Уоршалла.for (int k = 0; k < N; k++)for (int i = 0; i < MIN(dl+d, N); i++)for (int j = 0; j < MIN(dl+d, N); j++)A[i*N+j] = min(A[i*N+j], A[i*N+k]+A[k*N+j]);46Ниже приведена блочная реализация алгоритма Флойда-Уоршалла:Листинг 8. Блочной алгоритм Флойда-Уоршалла.for (dl = 0; dl < N; dl += d) {for (k = dl; k < MIN(dl+d, N); k++)for (i = dl; i < MIN(dl+d, N); i++)for (j = dl; j < MIN(dl+d, N); j++)A[i*N+j] = min(A[i*N+j], A[i*N+k]+A[k*N+j]);for (dk = 0; dk < N; dk += d) {if (dk == dl)continue;for (k = dl; k < MIN(dl+d, N); k++)for (i = dl; i < MIN(dl+d, N); i++)for (j = dk; j < MIN(dk+d, N); j++)A[i*N+j] = min(A[i*N+j], A[i*N+k]+A[k*N+j]);for (k = dl; k < MIN(dl+d, N); k++)for (i = dk; i < MIN(dk+d, N); i++)for (j = dl; j < MIN(dl+d, N); j++)A[i*N+j] = min(A[i*N+j], A[i*N+k]+A[k*N+j]);}for (dk = 0; dk < N; dk += d)for (ds = 0; ds < N; ds += d) {if (dk == dl || ds == dl) continue;for (k = dl; k < MIN(dl+d, N); k++)for (i = dk; i < MIN(dk+d, N); i++)for (j = ds; j < MIN(ds+d, N); j++)A[i*N+j] = min(A[i*N+j], A[i*N+k]+A[k*N+j]);}}47Предположим, что тайлинг производится под L3-кеш.

В этом случае, еслиL3-кеш является полностью ассоциативным, то оптимальный размер блока равенdL L3 SizeDataTypeSizeРассмотрим теперь случай, когда(20)L3-кеш не являетсяполностьюассоциативным. Пусть step – минимальное положительное число, такое что(step  N  DataTypeSize)( L3 BankCount  CacheLineSize)(21)В этом случае элементы каждой строки матрицы с номером кратным числуstep будут отображаться в одни и те же кеш-линейки.ЕслиN  2048 ,тоstep  16иприразмереблокаd  L3 Assoc  step  12  16  192 элементы одного блока уже начнут вытеснять другдруга из кеш-памяти, и тем самым существенно увеличится количество кешпромахов. Таким образом, оптимальный размер блока d  192 .Для блочного алгоритма Флойда со стандартным размещением данныхимеет место следующая формула времени выполнения:Если d  192 , то23 n  1  d  3  memory _ latency d  cache _ latencyT (n)      d 3  2  k CacheLineS izeCacheLineS ized   3(22), иначеn 3  memory _ latency cache _ latencyT ( n)   2k  CacheLineS izeCacheLineS izeГде ʋ - частота процессора, k -(23)время выполнения арифметическихопераций.

Точность формул 22-23 подтверждается результатами численного48эксперимента. В эксперименте подсчитывается время выполнения программы,реализующей блочный алгоритм Флойда-Уоршалла для разных размеров блока:Таблица 5. Результаты профилировки блочного алгоритма Флойда-УоршаллаNdLL3 cacheL2 cacheL1 cacheElapsedTheoreticalmissmissmiss(sec)time (sec)impactimpactimpact2048641.26.90.2247.91999627.397922048961.05.20.4446.65286426.668420481280.924.40.745.93637226.3037520481600.923.10.9545.51396326.0849220481763.02.50.7947.38281426.0053420481926.01.71.049.60171925.93903204825611.00.411.250.24860771.89401Из эксперимента видно, что оптимальный размер блока равен 160. ВТаблице 5 приведено также теоретическое время работы программы, котороевычисляется с использованием формул 22-23.