Разбиение цикла для автоматической векторизации
Способы преобразования больших циклов посредством их разбиения на несколько более простых циклов с последующей разверткой и векторизацией на современных процессорах. Предлагается ряд вспомогательных преобразований для разбиения и последующей векторизации.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 15.01.2019 |
| Размер файла | 22,7 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Разбиение цикла для автоматической векторизации
Брагилевский В.Н.,
старший преподаватель кафедры информатики и вычислительного эксперимента ЮФУ, bravit@sfedu.ru
Штейнберг О. Б., ассистент кафедры алгебры и дискретной математики ЮФУ, olegsteinb@gmail.com
В настоящем докладе обсуждаются возможные способы преобразования больших циклов посредством их разбиения на несколько более простых циклов с последующей разверткой и векторизацией на современных процессорах. Перед выполнением разбиения циклы иногда необходимо приводить к виду, пригодному для разбиения и последующей векторизации, для чего предлагается использовать ряд вспомогательных преобразований, также представленных в докладе.
«Разбиение цикла» (loop distribution) - это преобразование программ, суть которого состоит в том, чтобы заменить цикл, в теле которого много операторов присваивания, на эквивалентный фрагмент программы из нескольких циклов, в телах которых меньше операторов.
Современные процессоры имеют средства для исполнения векторного кода (MMX, SSE, AVX для процессоров от Intel, AltiVec для PowerPC, NEON для SPARC и пр.), в то же время компиляторы языков программирования поддерживают векторные расширения, используемые программистом для написания такого кода. При этом возможности компиляторов по автоматической векторизации циклов в последовательных программах довольно ограничены.
Иногда цикл, в теле которого много операторов, не может быть эффективно отображен на архитектуру процессора, например, из-за неудобного набора инструкций или нехватки регистров или кэш памяти. В этом случае «разбиение» может привести к тому, что все или хотя бы некоторые из результирующих циклов смогут быть вычислены более эффективно, что в свою очередь приведет к повышению эффективности. В частности, после «разбиения цикла» могут получиться пригодные для векторизации циклы [6].
Некоторые циклы невозможно «разбить» в исходном виде и тогда можно попытаться применить вспомогательные преобразования. Такими преобразованиями, приводящими цикл к разбиваемому виду, могут являться «растягивание скаляров» или «введение временных массивов» [6].
К коротким циклам, получающимся в результате разбиения, впоследствии можно применить преобразование «развертка цикла» (loop unrolling) так, чтобы количество операторов в теле цикла было кратно размеру регистров векторизатора. После этого тело цикла векторизуется, и получившийся код исполняется на векторном процессоре.
Задача разбиения циклов рассматривалась в работах [1], [2], [3], [4]. Она также близка к задачам векторизации [5] или частичной векторизации [6] одномерного цикла. Подобная задача решается также в LLVM [8], где возможности векторизации в настоящее время ограничены самыми простыми циклами, к которым предварительно может применяться развертка.
Рассмотрим примеры разбиений цикла как без использования вспомогательных преобразований, так и с их использованием, приводящие в конечном итоге к коду, который поддается эффективной векторизации.
Разбиение цикла без использования вспомогательных преобразований. Преобразование «разбиение цикла» заключается в следующем. Предположим, что рассматриваемый цикл имеет вид:
for(i = 0; i < N; i++)
{
S1[i]
…
Sk[i]
Sk+1[i]
…
Sm[i]
}
т.е. его тело состоит из операторов Sj, 1 ? j ? m. Этот цикл преобразуется к фрагменту программы, состоящему из двух циклов:
for(i = 0; i < N; i++)
{
S1[i]
…
Sk[i]
}
for(j = 0; j < N; j++)
{
Sk+1[j]
…
Sm[j]
}
При решении данной задачи ключевую роль играет граф информационных связей [3]. Вершинами этого графа являются вхождения переменных. Дуга идет из i-той вершины в j-тую, если вхождения, соответствующие этим вершинам, обращаются к одной и той же ячейке памяти, причем сначала вхождение, соответствующее i-той вершине, а затем вхождение, соответствующее j-той вершине. Если при обращении к ячейке памяти происходило чтение, то такое вхождение называется использованием (in), а если запись, то генератором (out). В зависимости от того, какого типа вхождения образуют дугу зависимости, дуги подразделяются на четыре типа: 1) in-in - входная, 2) out-out - выходная, 3) out-in - истинная (прямая), 4) in-out - дуга анти-зависимости.
Условия применения преобразования «разбиение цикла»:
§ Из фрагмента Sk+1, ... , Sm во фрагмент S1, ... , Sk не идет ни одной дуги (снизу вверх) анти, выходной или истинной зависимости.
§ В каждом из данных фрагментов должно быть по одному входу и выходу.
Предположим, что в целевом процессоре поддерживаются регистры кратности 4. Тогда в результате развертки, к примеру, первый цикл, полученный в результате разбиения, приобретает следующий вид:
for(i = 0; i < N/4; i++)
{
S1[i]; …; Sk[i];
S1[i+1]; …; Sk[i+1];
S1[i+2]; …; Sk[i+2];
S1[i+3]; …; Sk[i+3];
}
Теперь тело цикла может быть записано через k векторных инструкций или их комбинаций:
for(i = 0; i < N/4; i++)
{
VS1
…
VSk
}
Разумеется, такая векторизация реализуема далеко не всегда, причем она оказывается тем проще, чем меньше размер получившихся тел циклов. Условия корректности векторизации описываются графом информационных связей [5]. Отдельное влияние на эффективность векторизации оказывает наличие в процессоре составных векторных инструкций, объединяющие в себе сразу несколько базовых операций, например, сложение с умножением и побитовым сдвигом, что характерно, в частности, для DSP-процессоров.
Приведение цикла к разбиваемому виду. Иногда условия разбиения цикла не выполняются, но после проведения некоторых эквивалентных преобразований этого можно добиться. Препятствиями для разбиения цикла могут быть либо синтаксические особенности (управляющие связи в теле цикла), либо информационные зависимости. Поэтому предварительные преобразования, ориентированные на дальнейшее разбиение цикла, состоят в устранении управляющих связей или информационных зависимостей.
Использование перестановки операторов для разбиения цикла. Иногда бывает так, что в исходном виде цикл не разбивается, но если в теле этого цикла переставить местами некоторые операторы, то «разбиение» станет возможным.
Не всегда при необходимости можно произвести перестановку операторов, потому что это преобразование может оказаться неэквивалентным. Иногда после перестановки операторов цикл все равно нельзя «разбить», потому что вместо одной дуги, направленной снизу вверх, появляется другая имеющая такое же направление.
Использование преобразования «введение временных массивов» для «разбиения цикла». Преобразование «введение временных массивов» [6] иногда может устранить дугу анти-зависимости идущую снизу вверх. Правда, в результате преобразования появятся две дуги, идущие сверху вниз, которые не препятствуют разбиению. После этого неразбиваемый цикл может стать разбиваемым.
Рассмотрим, к примеру, следующий цикл:
for(i = 0; i < N; i++)
{
A[i]=B[i]+C[i];
C[i]=A[i+1]+B[i];
}
Если выполнять его развертку непосредственно, то провести затем эффективную векторизацию не удается из-за наличия зависимости по элементам массива C. Если же ввести сначала временный массив TEMP, то после этого цикл станет пригодным для «разбиения» на три цикла, каждый из которых после развертки оказывается эффективно векторизуемым:
for(i = 0; i < N; i++)
{
TEMP[i]=A[i+1];
A[i]=B[i]+C[i];
C[i]=TEMP[i]+B[i];
}
Массивы, используемые в коде с векторными инструкциями, должны рассматриваться как массивы векторов, располагаясь при этом в памяти по тем же адресам, что и исходные массивы. Для обозначения этого факта будем добавлять к их именам префикс V и называть такие массивы векторизованными. Теперь окончательно получаем следующие три цикла, в которых все операции становятся векторными:
for(i = 0; i < N/4; i++)
VTEMP[i]=VA'[i];
for(i = 0; i < N/4; i++)
VA[i]=VB[i]+ VC[i];
for(i = 0; i < N/4; i++)
VC[i]=VTEMP[i]+VB[i];
Векторизованный массив VA' получается чтением из памяти элементов исходного массива A со сдвигом на один элемент либо обращением с таким же сдвигом к регистровому файлу процессора, если последний поддерживает такую возможность.
Повышение размерности массивов для разбиения циклов («растягивание скаляров»)
«Растягивание скаляров» также может быть использовано для устранения дуги анти-зависимости идущей снизу-вверх. Это преобразование применяется в случае, когда зависимость образована вхождением переменной, не зависящей от счетчика цикла. Оно заключается в том, чтобы заменить такую переменную массивом, зависящим от счетчика цикла. Следует отметить, что такое преобразование предполагает дополнительный расход памяти.
Цикл до «растягивания скаляров»:
for(i = 0; i < N; i++)
{
A[i]=B[i]+C;
C=A[i+1]+B[i];
}
цикл после «растягивания скаляров» (пригодный для «разбиения» на два цикла):
CC[0]=C
for(i = 0; i < N; i++)
{
CC[i+1]=A[i+1]+B[i];
A[i]=B[i]+CC[i];
}
C=CC[N]
Заметим, что после разбиения и развертки под векторные регистры, размер которых кратен четырем, этот фрагмент оказывается эффективно векторизуемым:
VCC[0][0]=C
for(i = 0; i < N/4; i++)
VCC'[i]=VA'[i]+VB[i]
for(i = 0; i < N/4; i++)
VA[i]=VB[i]+VCC[i]
C=VCC[N/4][3]
Массивы VA, VB и VCC являются векторизованными, штрих в имени означает чтение из памяти или регистрового файла со сдвигом на один элемент. Второй индекс в векторизованном массиве соответствует взятию компонента вектора (первого или последнего в данном примере).
разбиение цикл автоматический векторизация
Заключение
Таким образом, в целях повышения эффективности исполнения цикла предлагается следующая схема его трансформации:
1) Некоторое вспомогательное преобразование.
2) Разбиение цикла.
3) Развертка цикла.
4) Векторизация тела цикла.
Первые три этапа трансформации не зависят от целевого процессора и его возможностей и поэтому могут быть реализованы в высокоуровневом внутреннем представлении. Последний этап при этом должен являться частью оптимизирующих преобразований в бэкенде, поскольку различия между поддерживаемыми векторными инструкциями могут быть слишком велики, тогда как ориентация на усредненные возможности способна воспрепятствовать генерации наиболее эффективного кода. Разумеется, развертка цикла должна параметризовываться размером имеющихся в процессоре векторных регистров.
Литература
1. R. Allen, K. Kennedy Optimizing compilers for modern architectures. Morgan Kaufmann Publishers, 2002, p. 790.
2. Штейнберг Б.Я., Черданцев Д.Н., Науменко С.А., Бутов А.Э., Петренко В.В. Преобразования программ для открытой распараллеливающей системы// Искусственный интеллект. Научно-теоретический журнал. Институт проблем искусственного интеллекта НАНУ. Украина, Донецк, ДонДИШИ, “Наука и Освита”, 2003, № 3, с. 97-104.
3. Штейнберг Б.Я. Математические методы распараллеливания рекуррентных программных циклов на суперкомпьютеры с параллельной памятью.// Ростов-на-Дону, Издательство Ростовского университета, 2004 г., 192 с.
4. Штейнберг О. Б. Минимизация количества временных массивов в задаче разбиения циклов. «Известия ВУЗов. Северокавказский регион. Естественные науки», №5, 2011 г., с. 18-21.
5. Lamport L. The parallel execution of DO loops// Commun. ACM.- 1974.- v.17, N 2, p. 83-93.
6. Векторизация программ. // Векторизация программ: теория, методы, реализация. / Сборник переводов статей М.: Мир, 1991. С. 246 - 267.
7. www.ops.rsu.ru
8. The LLVM Compiler Infrastructure, http://llvm.org
Размещено на Allbest.ru
...Подобные документы
Способ представления графа в информатике. Алгоритмы поиска элементарных циклов в глубину в неориентированных графах. Описание среды wxDev-C++, последовательность создания проекта. Руководство пользователю программы поиска и вывода на экран простых циклов.
курсовая работа [783,2 K], добавлен 18.02.2013Постановка задачи. Математическое обоснование. Последовательность разбиений множества. Язык программирования. Реализация алгоритмов. Генерирование разбиений множества. Генерирование всех понятий.
курсовая работа [29,9 K], добавлен 20.06.2003Разбиение задачи на несколько более простых подзадач. Вычисление логарифма с использованием ряда Тейлора при небольших значениях. Функция поиска строки с максимальной суммой. Создание дополнительной функции. Процедура печати строки с максимальной суммой.
контрольная работа [171,0 K], добавлен 17.08.2013Понятие и основные определения гамильтоновых графов, теоремы их достаточности и особенности методов нахождения циклов. Сущность метода перебора Робертса и Флореса и его улучшение. Задачи отыскания гамильтоновых циклов в графах, создание программы.
курсовая работа [76,5 K], добавлен 01.07.2010Источники геоданных для геоинформационных систем, принципы их обработки. Технические средства переноса данных с бумажных карт. Технология векторизации данных. Обзор современных средств и технологий непосредственного ввода координат. Геокодирование.
презентация [4,7 M], добавлен 02.10.2013Предназначение цикла for - оформление циклов (набора действий) с заданным количеством повторений. Пример программы, выводящей на экран все целые числа от 0 до 99. Решение задачи с помощью двух алгоритмов, используя известные функции ввода-вывода.
лабораторная работа [35,1 K], добавлен 15.07.2009Применение циклической управляющией структуры для организации многократного выполнения некоторого оператора. Конструкция цикла: заголовок и тело, и алгоритм выполнения операторов while, do while и for. Отличия циклов с постусловием и предусловием.
контрольная работа [65,8 K], добавлен 30.12.2010Описание методов нахождения и построения эйлеровых циклов в графах при раскрытии содержания цикломатических чисел и фундаментальных циклов. Изучение алгоритма решения задачи "Китайского почтальона" и разработка программы, решающей задачу на языке Си.
курсовая работа [924,3 K], добавлен 09.01.2011Элементы интерфейса AutoCAD 2014. Инструментальная топографическая съёмка. Векторизация растровых изображений. Классификатор Credo Topoplan. Построение модели рельефа по данным векторизации горизонталей. Вычисление объемов методом по квадратам.
курсовая работа [4,2 M], добавлен 01.06.2015Анализ выполнения векторизации фрагмента карты с помощью программы CorelDRAW Х6. Работа по составлению теста (вопросов с вариантами ответов). Построение точечной диаграммы, создание макроса в Microsoft Excel. Правила работы с PDF и Microsoft Word.
контрольная работа [622,6 K], добавлен 26.04.2015Методы расчета термодинамических свойств рабочих тел. Исследование циклов простых газотурбинных установок. Проектирование заданной установки с использованием математической модели. Изучение влияния температур газа перед турбинами на КПД газотурбины.
курсовая работа [436,9 K], добавлен 30.11.2013Табличный вывод значений суммы ряда и номера последнего элемента суммы в зависимости от значений величин входных параметров с применением операторов ветвления и циклов. Блок-схема алгоритма решения. Время работы программы для расчета одного значения.
контрольная работа [762,9 K], добавлен 14.05.2013Понятие, основные принципы, этапы и методы векторизации изображения. Автоматическая векторизация CorelDRAW 12. Программное обеспечение AutoCAD Raster Design. Программное обеспечение Easy Trace. Редактирование объекта без потери качества изображения.
курсовая работа [923,4 K], добавлен 08.12.2014Концепция "прозрачного" кэша. Программная предвыборка в процессорах К6+ и РIII+, в процессорах AMD К6 и VIA C3. Инструкция prefetch. Предвыборка в процессорах РIII и Р4. Pentium III. Pentium 4. Эффективность предвыборки в многозадачных системах.
доклад [13,6 K], добавлен 22.09.2008Написание программы, которая вводит исходные данные, выполняет расчет и выводит на экран. Использование вспомогательных переменных и счетчиков циклов в программе. Расчет сумм заработков по каждому виду одежды за день, количества изготовленных деталей.
курсовая работа [2,4 M], добавлен 17.01.2015Порядок составления программ копирования строки символов в рядом расположенную область памяти в обратном порядке и напрямую. Определение адресов источника и получателя. Организация адресации операндов, строк и циклов посредством промежуточного регистра.
контрольная работа [20,6 K], добавлен 09.11.2010Создание приложения и освоение начала технологии графического программирования. Использование CASE-структур в создаваемых приложениях и применение циклов типа For-Do. Создание программы, которая будет подсчитывать время выполнения определенного цикла.
курсовая работа [321,4 K], добавлен 24.06.2013Понятие алгоритма и сортировки. Способы и алгоритмы сортировки массивов. Быстрая сортировка Хоара. Описание алгоритма "быстрой сортировки". Реализация на языке программирования. Анализ наихудшего разбиения. Вероятностные алгоритмы быстрой сортировки.
курсовая работа [291,5 K], добавлен 22.03.2012Характеристики операторов языка Си. Операторы безусловного и условного перехода: if, if-else, if-else if. Оператор переключатель switch. Оператор цикла с предусловием while, постусловием do-while. Упрощение логических выражений, взаимозаменяемость циклов.
лабораторная работа [30,0 K], добавлен 06.07.2009Решение задач, прямо связанных с применением циклов и массивов. Условия применения различных видов циклической структуры. Операторы цикла с предусловием while, постусловием do-while и for. Особенности работы с одномерными и двумерными массивами.
курсовая работа [1,1 M], добавлен 31.08.2019
