Диссертация (1149957), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

Выбор конкретного способа определения массивов влияет наэффективность использования памяти, а также на операции доступа к данным.Соответственно, при внесении изменений в метод размещения массивов,программисту приходится изменять все операции доступа к элементам массива,что является достаточно трудоемким процессом.Проект TALC [33], [34] предназначен для того, чтобы избавитьпрограммиста от необходимости переписывать программу, в случае измененияметода размещения массивов. TALC входит в систему компиляторов ROSE ипредставляет собой расширение языков C/C++. С помощью него программистпосредством специальных схем данных может определять массивы структур, атакже способ размещения полей внутри структур.

Поля внутри структур могуттакже быть массивами. По схемам данных TALC генерирует соответствующие имструктуры данных языка Си. Также генерируются операции доступа к этим33структурам внутри программы. Тестирование производительности TALC велосьна нескольких программах решения задач гидродинамики и продемонстрировалоускорение в 40-60% [33].В работе [36] отмечается важность использования переразмещения данныхдля увеличения уровня SLP (Superword Level Parallelism). При правильном выбореметода размещения данных уменьшается количество дополнительных операцийупаковки/распаковки данных.

С этой целью в компиляторе SUIF [42], [40] былареализованаавтоматизацияпереразмещенияпеременных.Врезультатеприменения оптимизатора на 16 программах было получено среднее ускорение в15.2% за счет увеличения SLP.1.6.Выводы к первой главеВ первой главе описаны понятия необходимые для изложения результатовдиссертации. В параграфе 1.1 приведены принципы работы иерархии памятисовременныхвычислительныхсистем.Даетсяопределениекеш-памяти,виртуальной памяти, кеш-памяти TLB. Параграф 1.2 посвящен методу тайлинга,который предназначен для оптимизации временной локальности данных.

Впараграфе 1.3 приведено определение пространственной локальности данных, атакже различные методы размещения данных. В частности, описывается блочноеразмещение данных, автоматическую поддержку которого реализовал автордиссертации в системе ОРС. В параграфе 1.4 приводится понятие выравниванияданных в памяти. На примерах представлено как производится выравниваниеданныхсовременнымикомпиляторами.Параграф1.5содержитобзоркомпиляторов, которые содержат в своем составе нестандартные оптимизацииработы с памятью. В частности, приводится описание проекта TALC, которыйпозволяет программисту размещать структуры и массивы согласно определеннойсхемы.34Глава 2Модель времени выполнения программ для иерархической памятиСкорость доступа к данным, находящимся в памяти, для многих задачостается слабым местом в работе компьютера: процессоры обрабатывают данныенамного быстрее, чем подкачивают их из памяти.

Память современныхпроцессоров имеет иерархическую структуру. Чаще всего она состоит изрегистрового файла процессора, иерархической кеш-памяти и оперативнойпамяти. Данные между оперативной памятью и кеш-памятью пересылаютсяблоками(кеш-линейками) фиксированнойдлины. В некоторыхмоделяхпроцессоров Intel [58], [59] реализована трехуровневая кеш-память (Рисунок 6).Замыкает иерархию оперативная память.Рис.

6: Иерархия памяти процессоров Intel Sandy Bridge, IvyBridge, Haswel [58, 59]В то же самое время современные процессоры имеют большое количествопараметров. Например, в Таблице 2 приведены некоторые важные параметрыпроцессора Intel Core i5-2410m.35Таблица 2. Параметры процессора Intel Core i5-2410mCache line size64 bytesL1 size32 KBL1 banks count64L1 associativity8L1 latency3 opsL2 size256 KBL2 banks count512L2 associativity8L2 latency10 opsL3 size3072 KBL3 banks count4096L3 associativity12L3 latency22 opsTLB cache size512 itemsTLB cache associativity4CPU frequency2.3 GHzКаждый из данных параметров должен учитываться во время оптимизациипрограммы.

Общая формула времени выполнения программы имеет следующийвид:T (n)  Texecution (n)  Tload (n)(2)где n – размер входных данных, T(n) – время выполнения программы, Texecution(n) общее время выполнения арифметических операций,Tload (n)- общее времяперекачки данных между оперативной памятью и кеш-памятью. Точная формулавремени выполнения зависит от алгоритма.36Пусть исходный алгоритм можно представить в виде нескольких подзадач.В этом случае формула времени выполнения алгоритма будет иметь следующийвид:T (n)  R  (Ttaskexecu tion  Ttaskload )Где(3)Ttasklo a d — время подкачки данных, используемых подзадачей, изоперативной памяти в кеш,Ttaskexecution —время выполнения подзадачи, R –количество подзадач. Предположим, что функция сложности алгоритмов решенияисходной задачи и подзадач одинаковая и равна F (количество операций, какфункция от количества входных данных), объем данных исходной задачи D1 иобъем данных всех подзадач одинаков и равен D2.

В этом случае количествоподзадачRF ( D1)F ( D 2)(4)Пусть подзадачи запрограммированы оптимально ( Ttaskexecution минимально).Для того чтобы уменьшить время выполнения алгоритма нужно уменьшитьTtasklo a d .Рассмотрим подзадачу в виде совокупности подзадач меньшего размера. Вэтом случае к ней также будет применима формула (3). Сведение задачи кнескольким подзадачам выполняется рекурсивно. Согласно модели, оптимальноеколичество шагов рекурсии равно количеству уровней памяти, при условии, чтоисходную задачу можно разбить на подзадачи таким образом. Ниже представленонесколько примеров использования формулы (3).

Для упрощения будемпредполагать, что кеш данных является полностью ассоциативным.37Пример 3. Вычисление формулы времени выполнения для задачи однородногодоступа к памяти. Рассмотрим случай, когда в качестве задачи выступает чтениеиз памяти элементов массива X с i1 по i2 с шагом h. Предполагается, что Данные выровнены по типу данных, т.е. адрес данного кратен размеру типаэтого данного. Размер типа данного меньше размера кеш-линейки. Первый элемент массива, к которому производится обращение, смещенотносительно начала кеш-линейки на p0 байт, а относительно началавиртуальной страницы — на p1 байт.Подсчитаем количество кеш-линеек S0 загруженных из оперативной памяти вкеш: Если h   Lk  , тоd  d  (i 2  i1  1)  po S0  Lk(5)иначе i 2  i1  1S0  hгде Lk — размер кеш-линейки, d — размер типа данных. Значение выражения xравноминимальномуцеломучислубольшемуилиравномучемx(соответственно, значение выражения x равно максимальному целому числуменьшему или равному чемx ).Количество виртуальных страниц S1,задействованных в данной задаче, вычисляется схожим образом.

Если h  Vk  , тоd  d  (i 2  i1  1)  p1S1  Vkиначе i 2  i1  1S1  h(6)38Здесь Vk – размер виртуальной страницы. Таким образом,Ttasklo a d  k 0  S 0  k1 S1 ,где k0 – время перекачки кеш-линейки из оперативной памяти в кеш-память, а k1– время трансляции виртуальной страницы. Данный пример демонстрирует, чтодля того, чтобы данные считывались максимально быстро из памяти, они должныхраниться рядом друг с другом.Пример 4.

Эффективное разбиение задачи умножения матриц на подзадачи.Использование блочного кода и блочного размещения данных. Пусть решаетсязадача умножения матриц C=A*B. Будем предполагать, что матрицы –квадратные, размер матрицы равен N, каждая из них не помещается в кеш-памяти.Рассмотрим стандартный алгоритм умножения матриц:Листинг 5. Стандартный алгоритм умножения матриц.for(i=0; i<N; ++i)for(j=0; j<N; ++j)for(k=0; k<N; ++k)C[i*N+j]+=A[i*N+k]*B[k*N+j];В данном алгоритме общее время подкачки данных T зависит в большейстепени от операций, проводимых над матрицей B. Это связано с тем, что доступк элементам B происходит с шагом N.

Поэтому время выполнения алгоритмаравноT1 (n)  k 0  N 3  k1  N 3  k 2  N 3(7)где k0 – время перекачки кеш-линейки из оперативной памяти в кеш-память, k1 –время трансляции виртуальной страницы, k2 – время выполнения арифметическойоперации.39Время работы алгоритма (7) можно уменьшить, если представить исходнуюзадачу в виде набора подзадач – умножений блоков матриц. Для этогомодифицируем исходный алгоритм умножения матриц, используя тайлинг:Листинг 6. Алгоритм умножения матриц после применения к нему методатайлинга.for(di=0; di<N; di+=d)for(dj=0; dj<N; dj+=d)for(dk=0; dk<N; dk+=d)for(i=di; i< MIN(N,di*d); ++i)for(j=dj; j< MIN(N,dj*d); ++j)for(k=dk; k< MIN(N,dk*d); ++k)C[i*N+j]+=A[i*N+k]*B[k*N+j];Время работы данного алгоритма равно3Nd d T2 ( n )     ( k 0  d     k 1  d     k 2  d 3 )d Lk Vk (8)Где Lk — размер кеш-линейки, VK – размер виртуальной страницы d —размер типа данных.

Характеристики

Список файлов диссертации