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

Иерархическаяструктура памяти продиктована тем, что многие алгоритмы в определенныйпромежуток времени обращаются к фиксированному набору данных несколькораз.1.1.1.Кеш-память процессораКеш-память процессора – это память, которая находится на одномкристалле с процессором. В современных процессорах кеш-память по степениудаленности от процессора разделяется на несколько уровней. В частности,некоторые процессоры Intel [58], [59] включают в себе 3 уровня кеш-памяти,которые называются кеш-памятью L1, кеш-памятью L2 и кеш-памятью L3.

Кешпамять L1 расположена ближе всего к процессору. Соответственно, скоростьдоступа к ней выше чем скорость доступа к остальным уровням кеш-памяти.Размер кеш-памяти L1 составляет десятки килобайт. Кеш-память L3 являетсясамым медленной, но, в то же самое время, и самой большой. Ее размерисчисляются в мегабайтах. В некоторых многоядерных процессорах [58], [59]кеш-память L3 является общей для всех ядер, в то время как каждое ядро имеетсвою кеш-память меньших уровней.15Кеш-память процессора может хранить не только данные, но и инструкции(код исполняемых в данный момент программ).

Например, в [58] кеш-память L3позволяет хранить как данные, так и исполняемый код программ. В кеш-памятиL1 и кеш-памяти L2 данные и инструкции хранятся в двух разных уровнях кешпамяти, которые называются кеш-памятью данных (L1d, L2d) и кеш-памятьюинструкций (L1i, L2i) соответственно. В данной работе речь в большей степенибудет идти о кеш-памяти данных.В тот момент времени, когда данное считывается из оперативной памяти,производится проверка на наличие этого данного в кеш-памяти процессора.

Еслиданное находится в кеш-памяти, то обращение к оперативной памяти неосуществляется. Такая ситуация называется попаданием в кеш-память (caсhe hit).В противном случае происходит кеш-промах (caсhe miss) - считывание данного изоперативной памяти. Т.к. время считывания данных из оперативной памятинамного выше чем из кеш-памяти, то возникает задача минимизации кешпромахов. Один из методов минимизации кеш-промахов описан в разделе 1.2.Рассмотрим более подробно процесс сохранения данных в кеш-памяти.Будем предполагать, что адрес данного представляет собой 64-битное целое.Физически кеш-память представляет собой набор банков памяти (Рисунок 2).Рис 2: Банки кеш-памяти.Данные пересылаются из памяти в кеш-память и наоборот небольшимиблоками - кеш-линейками.

Размер кеш-линейки обычно равен 32 либо 64 байт изависит от процессора. Сохранение кеш-линейки в кеш-памяти означаетсохранение этой кеш-линейки в определенном банке памяти кеш-памяти. Длятого чтобы определить номер банка памяти, в который сохраняется кеш-линейка,16необходимо проанализировать адрес запрашиваемого данного, Его можноразделить на 3 части (Рисунок 3) Тэг (T) Номер банка памяти, в который попадает данное (S). Смещение относительно начала кеш-линейки (O).Рис 3: Адрес элемента.Очевидно, что T + S + O = 64 (размер адреса).O = log(CacheLineSize).Число S определяет номер банка памяти, в который попадет запрашиваемаякеш-линейка.

Так, например, при последовательном чтении массива данные будутсохраняться в последовательных банках памяти. Соответственно, при достижениипоследнего банка памяти следующий банк памяти будет иметь номер 0. Притаком методе считывания данных реально используемое количество банковпамяти равно максимальному значению, кеш-память используется максимальноэффективно.Размер банка памяти, т.е. количество кеш-линеек, которые он можетвместить,называетсяассоциативностьюкеш-памяти.Увеличениеассоциативности кеш-памяти приводит к усложнению ее проектирования. Этосвязано с тем, что усложняется схема устройства, производящего проверку наналичие запрашиваемой кеш-линейки в банке памяти.Если в кеш-памяти присутствует всего один банк памяти (S равен 0), токеш-память называется полностью ассоциативной.

Если банк памяти можетхранить одну кеш-линейку, то кеш-память называется кеш-памятью прямогоотображения. Кеш-память прямого отображения является самой простой с точкизрения проектирования. Большим ее минусом является то, что при ее17использовании вероятность возникновения кеш-промахов намного больше, чемпри использовании полностью ассоциативной кеш-памяти.

На практике вкачестве компромисса между полностью ассоциативной кеш-памятью и кешпамятью прямого отображения часто используется кеш-память с k-канальнойассоциативностью, при которой каждый банк памяти может хранить k кешлинеек. Число k обычно варьируется в диапазоне 4-16. В некоторых случаях кешпамять L1 является полностью ассоциативной.Последний элемент адреса (T) называется тэгом. По тэгу кеш-линейкипроизводится проверка на ее наличие в банке памяти.

Если кеш-линейки с такимтегом нет, то возникает ситуация кеш-промаха.При попытке сохранения кеш-линейки в банке памяти, происходитоперация вытеснения из него другой кеш-линейки. Существует несколькоалгоритмов вытеснения данных из банков памяти, и каждый из них имеет своиплюсы и минусы. На данный момент наиболее часто используемыми методамивытеснения данных является метод вытеснения наиболее давно использовавшихсяданных (LRU - Least Recently Used), а также метод вытеснения наиболее недавноиспользовавшихся данных (MRU - Most Recently Used).Кеш-память делится на инклюзивную (включающую) и эксклюзивную(исключающую) кеш-память. В инклюзивной кеш-памяти выполняется условие:если кеш-линейка хранится в младшем уровне кеш-памяти, то она хранится такжеи в старших уровнях кеш-памяти. В эксклюзивной кеш-памяти наоборот: кешлинейки хранятся только в одном из уровней кеш-памяти.Важной особенностью работы кеш-памяти является также то, чтопрограммист не имеет возможности адресовать находящиеся в ней данные.Единственная возможность явно повлиять на работу кеш-памяти состоит впрограммной предвыборке данных (software data prefetching).

Программнаяпредвыборка данных заключается в заблаговременной перекачке данных изоперативной памяти в кеш-память с целью уменьшения времени простаиванияпроцессора.Такаяобработкаданныхзачастуюраспараллелить вычисления и загрузку данных.позволяетэффективно18Набор операций предвыборки данных зависит от архитектуры процессора.Так, например, в некоторых процессорах Intel с инклюзивной кеш-памятью [58],[59] поддерживается программная предвыборка данных в нескольких режимах(Таблица 1).Таблица 1. Набор операций предвыборки данных в архитектуре x86.PREFETCH0Закачка кеш-линейки во все уровни кеш-памятиPREFETCH1Закачка кеш-линейки во все уровни кеш-памяти заисключением кеш-памяти L1PREFETCH2Закачка кеш-линейки во все уровни кеш-памяти заисключением кеш-памяти L2PREFETCHNTAЗакачка кеш-линейки в кэщ-память с учетом того, что еене следует сохранять в кеш-памяти на долгое времяСтоит отметить, чтокомандыпредвыборкиданныхимеютлишьрекомендательный для процессора характер, т.к.

они не влияют на результатработы программы.Длятогочтобыпроизвестипрограммнуюпредвыборкуданныхпрограммист обязан вставить в код программы вызовы специальной функции,осуществляющей предвыборку данных. Функция, позволяющая программиступроизвестипрограммнуюпредвыборкуданных,частореализуетсявкомпиляторах в виде встроенной (intrinsic) в компилятор функции.

Так, например,в компиляторе MSVC 2010 функция предвыборки кеш-линейки объявленаследующим образом:void _mm_prefetch(char * p , int type);где аргумент p является адресом кеш-линейки, а аргумент type принимает одно изследующих значений: _MM_HINT_T0 - закачка кеш-линейки во все уровни кеш-памяти.19 _MM_HINT_T1 - закачка кеш-линейки в L2 и L3 уровни кеш-памяти. _MM_HINT_T2 - закачка кеш-линейки в L3-уровень кеш-памяти. _MM_HINT_NTA – особый режим предвыборки данных, позволяющийзакачивать данные в кеш-память L1 в обход остальных уровней кешпамяти. Этот режим стоит использовать только при подкачке данных,обрабатываемых только один раз.Многие существующие процессоры являются многоядерными.

В такихпроцессорах кеш-память L1 и кеш-память L2 реализуются локальными длякаждого из ядер в отдельности. Кеш-память L3 является общей для всех ядер иможет использоваться для синхронизации данных различных уровней кеш-памятиL2. Такая кеш-память должна обладать свойством когерентности. Когерентностькеш-памяти – это свойство кеш-памяти, означающее целостность данных,хранящихся в локальных уровнях кеш-памяти.Существует много протоколов обмена данными между локальнымиуровнями кеш-памяти, которые обеспечивают когерентность кеш-памяти (MSI,MESI, MOSI и т.д.). Протокол MESI - широко используемый в современныхпроцессорах протокол поддержки когерентности кеш-памяти. В соответствии сним каждая кеш-линейка имеет одно из четырех состояний:1.

Modified2. Exclusive3. Shared4. InvalidСостояние Modified означает, что кеш-линейка загружена в кеш-памятьтекущего ядра, и данные, хранящиеся внутри нее, изменены.Кеш-линейка принимает состояние Exclusive, если она присутствует в кешпамяти только одного ядра и неизменена.20Аппаратная поддержка виртуальной памяти.

Кеш-память TLB.1.1.2.Виртуальная память – это технология управления памятью, котораяразработана для многозадачных операционных систем. Для данных каждогопроцесса, выполняемого на такой системе, выделяется диапазон адресов,называемых виртуальными адресами.

Процесс не имеет непосредственногодоступа к данным другого процесса.При обращении к данным в программе, написанной для многозадачнойсистемы, происходит отображение виртуальных адресов в физические. За этотпроцессотображенияадресовотвечаетоперационнаясистема.Процесстрансляции виртуального адреса в физический является дорогостоящей повремени операцией. Для его оптимизации соседние виртуальные адресагруппируютсяввиртуальныестраницы,размеркоторыхопределяетсянастройками ОС и может варьироваться от нескольких килобайт до несколькихгигабайт.