Аннотация в настоящем докладе обсуждаются возможные способы преобразования больших циклов посредством их разбиения на несколько более простых циклов с последующей разверткой и векторизацией на современных процессорах.
Скачать 78.28 Kb.
|
| Разбиение цикла для автоматической векторизации Брагилевский В. Н., старший преподаватель кафедры информатики и вычислительного эксперимента ЮФУ, 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 – дуга анти-зависимости. Условия применения преобразования «разбиение цикла»:
Предположим, что в целевом процессоре поддерживаются регистры кратности 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 являются векторизованными, штрих в имени означает чтение из памяти или регистрового файла со сдвигом на один элемент. Второй индекс в векторизованном массиве соответствует взятию компонента вектора (первого или последнего в данном примере). ЗаключениеТаким образом, в целях повышения эффективности исполнения цикла предлагается следующая схема его трансформации:
Первые три этапа трансформации не зависят от целевого процессора и его возможностей и поэтому могут быть реализованы в высокоуровневом внутреннем представлении. Последний этап при этом должен являться частью оптимизирующих преобразований в бэкенде, поскольку различия между поддерживаемыми векторными инструкциями могут быть слишком велики, тогда как ориентация на усредненные возможности способна воспрепятствовать генерации наиболее эффективного кода. Разумеется, развертка цикла должна параметризовываться размером имеющихся в процессоре векторных регистров. Литература
|
Добавить документ в свой блог или на сайт
Похожие:
 | Рабочая программа учебной дисциплины «Русский язык» Спо 230401 Информационные системы (по отраслям) предусматривает изучение следующих учебных циклов: общеобразовательного; общего гуманитарного... | | Программа по формированию навыков безопасного поведения на дорогах... Если учебная дисциплина сформирована за счет вариативной части циклов опоп, ее индекс и наименование не должны совпадать с индексом... |
 | Урокам тема №5: программирование на языке turbo-pascal. Организация... Цели и задачи: Знакомство с операторами цикла языка Turbo-Pascal. Выработка навыков работы в Turbo-Pascal. Решение практических задач... | | Аннотация к программе подготовки специалистов среднего звена по специальности... Наименование учебных циклов, разделов, модулей, требования к знаниям, умениям, практическому опыту |
| Московский государственный университет приборостроения и информатики... Реферат относится к активным видам учебного процесса. Его выполнение имеет своей целью более глубокое и творческое изучение основных... | | Аннотация рабочей программы дисциплины Сдф. 4 и читается в 6-м семестре. Изучение данной дисциплины осуществляется на основе знаний, приобретённых студентами ранее, в ходе... |
| Эволюция теорий волновой макродинамики экономического развития: природа... | | В. Г. Редько Институт оптико-нейронных технологий ран Аннотация. В статье аргументируется, что исследование проблемы эволюционного происхождения интеллекта могло бы внести радикальный... |
| Тематический план изучения дисциплины Классификация ресурсных циклов. Система контролирующих показателей мониторинга природных ресурсов | | Руководитель основной образовательной программы Основная образовательная программа бакалавриата предусматривает изучение следующих учебных циклов |
| Конкурс «Музыкальный знак» Дыгодюк Н. В. на школьной конференции, посвященной интеграции предметов общеобразовательного и музыкально-теоретического циклов на... | | Публичный отчет Анализ обеспечения качественного образования являлся... Анализ обеспечения качественного образования являлся предметом особого внимания предметных циклов. Каждое предметное объединение... |
| Предисловие введение Вторая часть раскрывает секреты создания имиджа политика, в нем анализируются психологические способы воздействия лидера на своих... | | Анализ фгос спо и учебного плана по специальности Алгоритм действий при разработке рабочей программы учебной дисциплины циклов огсэ, ен, оп |
| Циклов Состав, основное содержание и содержательно-логические связи содержания учебных курсов дисциплин (модулей), практик, нир, входящих... | | Циклов Состав, основное содержание и структурно-логические связи содержания учебных курсов, предметов, дисциплин (модулей), практик, нир,... |
