Распараллеливание циклов допускающих рекуррентные зависимости тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Штейнберг, Олег Борисович

• Штейнберг, Олег Борисович
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Штейнберг, Олег Борисович

Содержание

Введение

Глава 1 Понятия и определения теории графов и теории распараллеливания программ

1.1 Используемые в работе сведения теории графов

1.2 Граф информационных связей

1.3 ОР&ДВОР

1.4 Используемые в работе понятия из теории преобразования программ

1.5 Условия распараллеливания циклов на основные параллельные архитектуры

1.6 Выводы к первой главе

Глава 2 «Разбиение цикла»

2.1 «Разбиение цикла» без использования вспомогательных преобразований

2.2 Приведение цикла к «разбиваемому» виду

2.2.1 Использование «перестановки операторов» для «разбиения цикла»

2.2.2 Использование преобразования «введение временных массивов» для «разбиения цикла»

2.2.3 «Растягивание скаляров» для «разбиения цикла»

2.2.4 «Обобщенное растягивание скаляров» для «разбиения цикла»

2.2.5 «Подстановка вперед» для «разбиения цикла»

2.3 Алгоритм «разбиения цикла» использующий «перестановку операторов», «введение временных массивов», «растягивание скаляров» и «повышение размерности массива»

2.4 «Слияние циклов»

2.5 Выводы ко второй главе

Глава 3 Распараллеливание программных циклов, использующее вспомогательные преобразования

3.1 Векторизация программных циклов

3.2 Распараллеливание рекуррентных циклов

3.2.1 Векторизация рекуррентных циклов

3.2.2 Распараллеливание циклов с линейной рекуррентной зависимостью

3.2.3 Совместное применение распараллеливания и векторизации циклов с линейной рекуррентной зависимостью

3.2.4 Распараллеливание рекуррентных циклов предварительными вычислениями суперпозиций

3.3 Использование «разбиения» при распараллеливании циклов

3.4 Выводы к третьей главе

Заключение

Список литературы

СПИСОК СОКРАЩЕНИЙ

ВУ - вычислительное устройство

ДВОР - диалоговый высокоуровневый оптимизирующий распараллеливатель

ОРС - оптимизирующая распараллеливающая система

ПЛИС - программируемая логическая интегральная схема

AVX - Advanced Vector Extensions - набор векторных команд, оперирующих

с 256-битными регистрами

MIMD - many instructions, multiple data

OPS - Optimizing parallelization system

SIMD - single instructions, multiple data

SSE - Streaming SIMD Extensions

SUIF - Stanford University Intermediate Format

DVM - distributed virtual machine

VLIW - very long instruction word

Введение диссертации (часть автореферата) на тему «Распараллеливание циклов допускающих рекуррентные зависимости»

Введение

Актуальность темы

Сферы применения высокопроизводительных вычислений постоянно пополняются все новыми областями. Такими областями являются: задачи биоинформатики, моделирования поведения различных видов техники, проектирования электростанций, прогнозирования погоды и изменения климата, задачи криптографии, анализа данных социальных сетей, цифровой обработки сигналов и многие другие. Также возникает все больше задач, для которых необходимы вычисления в реальном времени (мобильная связь, распознавание речи и визуальных образов и т.д.).

В наше время даже персональные компьютеры стали параллельными (многоядерными, многоканальными). По этой причине является целесообразным развитие технологий параллельного программирования.

Ручная оптимизация и ускорение программ делаются долго и дорого. Преодолеть эту проблему можно за счет автоматической оптимизации и распараллеливания [3], [6], [9], [21], [49], [51], [54], [55], [60], [62], [63], [65], [67], [68], [70].

По автоматической оптимизации и распараллеливанию программ было написано много теоретических работ и создан ряд распараллеливающих оптимизирующих компиляторов [21], [49], [53], [54], [61]. Среди теоретических работ по автоматическому распараллеливанию наиболее значимыми можно отметить следующие [50], [51], [62], [70].

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

преобразований выделяются «разбиение цикла», «развертка цикла», «перестановка операторов», «введение временных массивов» и «растягивание скаляров».

«Развертка цикла» (loop unrolling) [7, стр.183], [31, стр.41], [51], [62, стр.559] является эффективным распараллеливающим преобразованием на VLIW и суперскалярные архитектуры. Это преобразование применяется для использования векторизации на современных процессорах, поддерживающих технологии S SE, AVX и им подобных.

«Перестановка операторов» (statement interchange) [51], [31, стр.22] используется для распараллеливания на VLIW архитектуру. Кроме того, это преобразование может быть использовано как вспомогательное для «разбиения цикла» и векторизации [31, стр.51], [51, стр.84], [60].

«Введение временных массивов» {node splitting) [7, стр.30], [31, стр.43], [51, стр.244], [62, стр.197], [70, стр.444] способствует «разбиению цикла» и векторизации [7, стр.30].

«Растягивание скаляров» (scalar expansion) [7, стр. 33], [31, стр.44], [51, стр.226], [70, стр.313] способствует «разбиению цикла» и векторизации. Подобные функции выполняют преобразования «экспансия массивов» {array expansion), «приватизация переменной» (privatization) и «повышение размерности массивов» [31, стр.56], [47], [51, стр.287], [56], [62], [70, стр.400].

«Разбиение цикла» {loop distribution, loop fission) применяется при оптимизации использования кэш-памяти и для векторизации [7 стр.36], [25], [31, стр.36], [51, стр.82], [62, стр.694], [70, стр.323], в том числе частичной.

Преобразования «введение временных массивов» и «растягивание скаляров» ведут к дополнительному расходу памяти. Вопрос возможности минимизации этих расходов, до исследований представленных в диссертации, в литературе не рассматривался.

Среди рекуррентных циклов распараллеливаются, как правило, только циклы, вычисляющие сумму ряда. В связи с этим представляет интерес

6

задача автоматического распараллеливания рекуррентных циклов более сложного вида.

В случае, когда цикл не удается векторизовать целиком, к нему можно применить преобразование «разбиение цикла». Если при этом один из результирующих циклов можно будет векторизовать, то стоит говорить о частичной векторизации. Вопрос частичной векторизации в литературе практически не освещается. Так, например, в статье Вольфа [7, с.ЗО] частичная векторизация описывается на примере, но алгоритм этого преобразования не приводится.

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

Объект исследований

Циклы последовательных программ и их преобразования к параллельному или частично параллельному коду.

Цель работы

Разработка новых алгоритмов преобразования программ, позволяющих существенно расширить класс последовательных программ, допускающих автоматическое распараллеливание.

Из сформулированной цели вытекают следующие задачи:

1. Разработка нового алгоритма «разбиения цикла» приводящего к распараллеливаемому виду более широкий класс программ, за счет использования вспомогательных преобразований.

2. Создание новых алгоритмов распараллеливания рекуррентных циклов с предварительным вычислением суперпозиций.

3. Разработка алгоритма включающего одновременную векторизацию и распараллеливание циклов с линейной рекуррентной зависимостью.

4. Проведение численных экспериментов для оценки производительности разработанного алгоритма «распараллеливания рекуррентных циклов с предварительным вычислением суперпозиций».

Методы исследований

В процессе решения рассматриваемых задач использовались математические методы теории распараллеливающих/оптимизирующих преобразований программ [17], [51], [62], [70], теории графов [14] и линейной алгебры [28], [29]. Разработанные алгоритмы программно реализованы с использованием технологии объектно-ориентированного программирования [5], [10], [27]. Эффективность разработанных алгоритмов и программ оценивалась численными экспериментами.

Научная новизна

• Разработан новый алгоритм «разбиения цикла» использующий вспомогательные преобразования «введение временных массивов», «растягивание скаляров» и «перестановку операторов» и оптимизирующий объем используемой дополнительной памяти.

• Разработан новый алгоритм, включающий одновременную векторизацию и распараллеливание циклов с линейной рекуррентной зависимостью.

• Алгоритм «распараллеливания рекуррентных циклов с опережающим вычислением коэффициентов», обобщен на 2К вычислительных устройств.

Практическая значимость

Разработанные алгоритмы распараллеливания могут быть использованы, как при автоматическом распараллеливании (в

8

распараллеливающих компиляторах), так и при ручном и полуавтоматическом распараллеливании. Предлагаемые методы позволяют:

• Ускорить время разработки параллельных программ.

• Удешевить разработку параллельных программ.

• Понизить требования к квалификации программистов, пишущих параллельные программы.

• Упростить перенос многих разработанных программ с последовательных компьютеров на параллельные.

Результаты диссертации могут быть использованы разработчиками параллельного программного обеспечения и разработчиками распараллеливающих компиляторов.

Личный вклад

Автором лично были разработаны алгоритмы: «разбиения цикла», «распараллеливания рекуррентных циклов с опережающим вычислением коэффициентов», «распараллеливания рекуррентных циклов с предварительным вычислением суперпозиций», «распараллеливания циклов с линейной рекуррентной зависимостью» и «совместного применения распараллеливания и векторизации». Алгоритм «разбиения цикла» создан с учетом минимизации количества применений вспомогательных преобразований, ведущих к дополнительным расходам памяти. Разработана программная реализация алгоритма «распараллеливания рекуррентных циклов с предварительным вычислением суперпозиций», учитывающая особенности архитектуры персональных компьютеров, для случая линейной и дробно-линейной рекуррентных зависимостей.

В рамках оптимизирующей распараллеливающей системы (OPS) автором были реализованы преобразования программ: «введение временных массивов», «растягивание скаляров», «разбиение цикла», «слияние цикла», «преобразование цикла к виду, допускающему векторизацию». На основе

изложенных в диссертации алгоритмов были написаны соответствующие преобразования, также вошедшие в OPS.

Проведен ряд численных экспериментов.

Использование результатов работы

Результаты диссертации внедрены в программном обеспечении высокопроизводительной электроники ОАО «Ангстрем». Также часть результатов диссертации используются в учебном процессе мехмата Южного федерального университета в магистерской программе «Высокопроизводительные вычисления и технологии параллельного программирования» в спецкурсе «Параллельные вычисления и преобразования программ».

Гранты, поддерживавшие исследования диссертации

• НИОКР "Разработка системной поддержки высокопроизводительного программного комплекса для квантово-механических расчетов и моделирования наноразмерных атомно-молекулярных систем и комплексов", госконтракт 02.524.11.4005 от 17 ноября 2008 г.

• ФЦП "Научные и научно-педагогические кадры инновационной России" по лоту "Проведение научных исследований коллективами научно-образовательных центров в области информатики" по теме: "Диалоговый высокоуровневый оптимизирующий распараллеливатель программ и его приложения", госконтракт 02.740.11.0208 от 07 июля 2009 г.

• ФЦП "Научные и научно-педагогические кадры инновационной России" по лоту " Проведение научных исследований коллективами научно-образовательных центров в области: - геномных и постгеномных технологий создания лекарственных средств; клеточных технологий; биоинженерии; биоинформационных технологий" по теме: "Создание биоинформационной технологии поиска взаимосвязанных сценариев организации в геномах животных и человека некодирующей ДНК и

10

кодирующей белок ДНК", госконтракт 14.740.11.0006 от 01 сентября 2010 г.

• Грант Российско-Белорусского государства «ТРИАДА», НИЦЭВТ, 2005 г.

• Внутренний грант Южного федерального университета «Учебно-научная лаборатория оптимизации и распараллеливания программ», 2007г.

• Федеральная целевая программа «Научные и научно-педагогические кадры инновационной России» на 2009-2013 гг., в рамках реализации мероприятия № 1.4 Развитие внутрироссийской мобильности научных и научно-педагогических кадров путем выполнения научных исследований молодыми учеными и преподавателями в научно-образовательных центрах. Государственный контракт 2012 г.

• Лаборатория Ангстрем-ЮФУ.

• Федеральная целевая программа «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2013 годы» по лоту шифр «2013-1.4-14-5140135» «Проведение проблемно-ориентированных исследований взаимодействия параллельных программ с памятью в суперкомпьютерных комплексах» по теме: «Распараллеливание программ с одновременной оптимизацией обращений к памяти» (шифр заявки «2013-1.4-14-514-0135-028»), Государственный контракт № 14.514.11.4104 от 10 октября 2013 г.

Степень достоверности и апробация результатов работы

Достоверность результатов подтверждается математической

строгостью изложения алгоритмов, а также ускорением программ,

установленным численными экспериментами.

Результаты изложенные в диссертации опубликованы в 9 научных работах [12], [39]-[45], [66], из которых 4 в журналах перечня ВАК. Также, докладывались на семинарах и конференциях:

1. На региональной научно-практической конференции молодых ученых и специалистов «Высокие информационные технологии» ВИНТП-2006, г. Ростов-на-Дону, 2006 г.

2. На научно-техническом совете ОАО «НКБ ВС», г. Таганрог, март, 2008 г.

3. «IEEE East-West Design & Test» Symposium (EWDTS'09). ). Moscow, Russia, September 18-21, 2009.

4. «Научный сервис в сети Интернет», г. Новороссийск, 20-26 сентября 2010 г.

5. На международной конференции «Параллельные вычисления и задачи управления» РАСО'2010. (2010 г, Москва).

6. На всероссийской научной конференции по проблемам информатики «СПИСОК-2013», 23-26 апреля, 2013, матмех Санкт-Петербургского университета, г. Санкт-Петербург.

7. На постоянно действующем научном семинаре мехмата ЮФУ «Автоматическое распараллеливание программ».

Доклад, посвященный алгоритму, описанному в пункте 3.2.4, получил 1-е место на конференции под номером 1 из приведенного списка.

Основные положения, выносимые на защиту

1. Алгоритм «разбиения цикла» использующий вспомогательные преобразования «введение временных массивов», «растягивание скаляров» и «перестановку операторов».

2. Алгоритм распараллеливания циклов с линейной рекуррентной зависимостью с постоянными коэффициентами.

3. Алгоритм «совместного применения распараллеливания и векторизации» циклов с линейной рекуррентной зависимостью с постоянными коэффициентами.

4. Алгоритмы распараллеливания рекуррентных циклов с предварительными вычислениями суперпозиций.

Структура и объем диссертации

Диссертация состоит из введения, трех глав, заключения, списка сокращений и списка литературы. Текст диссертации изложен на 114 страницах и содержит 29 примеров, 11 рисунков и 5 таблиц. Список литературы содержит 71 наименование.

Основное содержание работы

Первая глава носит вспомогательный характер. В ней описываются понятия необходимые для изложения результатов диссертации. В параграфе 1.1 приводятся определения из теории графов. В частности определяются матрица достижимости и правильная нумерация, фактор-граф и формат хранения разреженной матрицы СБИ.. Параграф 1.2 посвящен анализу информационных зависимостей в программе. Приводятся определения типов зависимостей, а также графа информационных связей и графа зависимостей по данным. В параграфе 1.3 описывается Оптимизирующая распараллеливающая система, частью которой являются, реализованные автором диссертации, некоторые алгоритмы и преобразования, описываемые в главах 2 и 3. Параграф 1.4 содержит определения различных преобразований программ используемых в главах 2 и 3. Такими определениями, например, являются: «перестановка операторов», «расщепление цикла», «развертка» и «раскрутка» цикла. В параграфе 1.5 приводятся два способа параллельного выполнения циклов, изложенные в известной статье Л. Лэмпорта [60]. Один из этих способов подходит для параллельного выполнения цикла на компьютерах с архитектурой М1МО(в частности, для современных многоядерных процессоров), а другой на

компьютерах с архитектурой SIMD(b частности, для векторных операций современных процессоров). Приводятся условия распараллеливания циклов на оба вида вычислительных архитектур. Лэмпортом описываются вспомогательные преобразования для распараллеливания, такие же, какие используются в данной работе для «разбиения цикла»: «перестановка операторов», «растягивание скаляров», «введение временных массивов».

Вторая глава посвящена преобразованию программ «разбиение цикла», способствующим ему вспомогательным преобразованиям и алгоритму разбиения. В параграфе 2.1 приводится определение того, в чем заключается преобразование «разбиение цикла» и указаны условия «разбиваемости». Параграф 2.2 посвящен возможностям приведения цикла к разбиваемому виду. В этом параграфе описывается ряд вспомогательных преобразований способствующих разбиению. Приведены скриншоты программной реализации описываемых преобразований (программная реализация выполнена в рамках распараллеливающей системы OPS). В параграфе 2.3 описывается «алгоритм «разбиения цикла» использующего «перестановку операторов», «введение временных массивов», «растягивание скаляров» и «повышение размерности массива»». Этот алгоритм включает минимизацию количества применений вспомогательных преобразований, вызывающих накладные расходы. Такими преобразованиями являются «растягивание скаляров», «введение временных массивов» и «повышение размерности массива» [45]. В параграфе 2.4 приведено преобразование «слияние циклов», обратное к «разбиению цикла».

В третьей главе приводятся разработанные в данной диссертации алгоритмы автоматической векторизации рекуррентных циклов. Эти алгоритмы реализованы в рамках Оптимизирующей распараллеливающей системы.

Для последующего сравнения предлагаемых в диссертации методов автором разработаны тестовые программы для четырех известных компиляторов: Clang/LLVM версии 3.3 (релиз 17.06.2013) [61], Microsoft

14

Visual С++ 2012 (релиз 15.08.2012) [54], GCC 4.8.1 (релиз 31.05.2013) [53], Intel С++ Compiler 13.1.3 (релиз 20.06.2013) [49]. Результаты тестирования выявили в этих компиляторах низкий уровень использования автоматической векторизации. Оказалось, что этими компиляторами не векторизуются циклы, предполагающие вспомогательные преобразования «перестановка операторов», «растягивание скаляров», «введение временных массивов».

В этой главе приводятся разработанные в данной диссертации алгоритмы автоматической векторизации рекуррентных циклов. Эти алгоритмы реализованы в рамках Оптимизирующей распараллеливающей системы.

В пункте 3.2.2 третьей главы рассмотрены методы автоматического распараллеливания рекуррентных циклов. Описан алгоритм преобразования цикла с линейной рекуррентной зависимостью с постоянными коэффициентами к виду, допускающему параллельное выполнение. Данный алгоритм является обобщением известных ранее методов и доведен до уровня программной реализации. Это преобразование сохраняет устойчивость вычислений. Устойчивость понимается в том смысле, что, если исходный рекуррентный цикл при малых изменениях входных данных давал малые изменения выходных данных, то таким же свойством обладает и преобразованный цикл (устойчивость доказана соавтором совместных исследований С.А. Суховерховым). Такое свойство устойчивости позволяет использовать это преобразование в распараллеливающих компиляторах.

В пункте 3.2.3 описан алгоритм совместного применения распараллеливания и векторизации рекуррентных циклов. Этот алгоритм является обобщением алгоритма из пункта 3.2.2 и также обладает устойчивостью. Алгоритм состоит в преобразовании исходного цикла к нескольким параллельным потокам, в каждом из которых применяется векторизация.

В пункте 3.2.4 третьей главы рассмотрены методы распараллеливания рекуррентных циклов использующие предварительные вычислениями

суперпозиций. Коэффициенты рекуррентной зависимости в данном пункте рассматриваются переменными в отличие от рекуррентных зависимостей, рассматриваемых в пунктах 3.2.2 и 3.2.3. Один из описываемых в этом пункте методов был предложен в [31] для распараллеливания вычислений на два вычислительных устройства. В данном параграфе этот метод обобщается на любое количество вычислительных устройств, которое является степенью двойки. Предложен алгоритм вычисления оптимальных параметров первого метода, использующий решение вспомогательной системы линейных уравнений с двухдиагональной матрицей.

На основе предложенных в пункте 3.2.4 методов, написаны параллельные программы, использующие технологию ОрепМР и С1ЮА для многоядерных процессоров и графического ускорителя соответственно. С разработанными программами проведены численные эксперименты, некоторые результаты которых приводятся в таблицах. Эксперименты показывают ускорение на десятки процентов. В частности, при распараллеливании на 4 потока преобразованная программа работает в два раза быстрее исходной.

Параграф 3.3 посвящен совместному применению преобразования «разбиение цикла» и распараллеливания циклов.

В параграфе 3.3 рассмотрен метод частичной векторизации и распараллеливания циклов. Суть метода состоит в том, чтобы цикл, который не получается распараллелить или векторизовать непосредственно, преобразовывался при помощи алгоритма «разбиения цикла», после чего результирующий код мог бы допустить параллельное или векторное выполнение.

Частичная векторизация циклов рассматривалась ранее, например, в работе [7, стр.66], но лишь на конкретном примере. Алгоритм, позволяющий реализовать частичную векторизацию в распараллеливающем компиляторе, не приводится.

В данной работе предлагается частичную векторизацию и распараллеливание выполнять с использованием преобразования «разбиение цикла».

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

Глава 1 Понятия и определения теории графов и теории распараллеливания программ

1.1 Используемые в работе сведения теории графов

В данной работе используется ряд понятий теории графов. Ориентированным графом {directed graph) G называется пара G = (V, Е), где V - конечное множество, называемое множеством вершин, a EczVxV — множество, называемое множеством ребер.

Маршрутом в ориентированном графе называют чередующуюся последовательность вершин и дуг, вида v0{v0,vi}vl{vl,v2}v2...vn (вершины и дуги могут повторяться).

Если в маршруте v0 = v„, то такой маршрут называется замкнутым. Путь - это маршрут в ориентированном графе без повторяющихся дуг. Если существует путь из одной вершины в другую, то вторая вершина достижима из первой.

Контур - это замкнутый путь.

Матрицей достижимости графа с конечным числом вершин п (пронумерованных числами от 1 до п) называется квадратная матрица А размера пхп, такая что A[i][j] = 1, если существует путь, ведущий из i-й вершины в j-ю и A[i][j] = 0, если такого пути нет.

Две вершины s и t графа сильно связаны, если существует ориентированный путь из 5 в t и ориентированный путь из t в 5.

Ориентированный граф называется сильно связным, если любые две его вершины сильно связны.

Компонентами сильной связности орграфа называются его максимальные по вложению сильно связные подграфы.

Пусть вершины конечного ориентированного графа пронумерованы. Нумерация дуги называется правильной, если номер начала дуги меньше, чем номер конца дуги. Нумерация вершин ориентированного графа называется правильной, если она правильна на всех его дугах.

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

Фактор граф по компонентам сильной связности это фактор-граф, в котором, в качестве различных классов эквивалентности взяты компоненты сильной связности.

Графы в памяти компьютера можно хранить разными способами. Рассмотрим те из них, которые используются в данной работе: матрица смежности и список дуг.

Матрицей смежности графа с конечным числом вершин п (пронумерованных числами от 1 до п) называется квадратная матрица А размера пхп, в которой значение элемента А|1]Ц] равно количеству дуг идущих из ьй вершины графа в ^ю вершину.

Списком дуг называется формат хранения графа, в котором все дуги графа хранятся в виде списка.

Если в графе мало дуг, то матрица смежности оказывается разреженной, т.е. содержащей много нулей. Такие матрицы хранить в памяти в виде двумерных массивов неэффективно, и для них существуют другие представления [24]. Использование специализированных способов хранения разреженных матриц позволяет не только экономить используемую память,

но и повысить быстродействие, поскольку уменьшается число обращений к памяти, которое является долговыполняемой операцией [57].

Рассмотрим пример хранения разреженной матрицы Пример 1.1. Рассмотрим граф, содержащий 6 вершин:

Матрица смежности этого графа имеет вид:

'0 5 6 0 0 0'

2 0 7 0 0 0

1 0 0 0 0 0

А =

0 0 0 0 0 0

7 0 0 9 0 3

,0 0 0 0 0 0,

Этот граф можно хранить в трех массивах. Такой формат хранения разреженных матриц носит название С8К.

Листинг 1.1. Запись матрицы в формате СБЯ.

АА= {5, 6, 2, 7, 1, 7, 9, 3}; 1А = {2, 3, 1, 3, 1, 1, 4, б}; аА = {1, 3, 5, б, б, 9};

В массиве АА находятся значения не нулевых элементов матрицы А записанные построчно сверху вниз. В массиве 1А на ьм месте массива указан номер столбца, в котором располагался в матрице А, ьй элемент массива АА. Массив 1А показывает, в каких строках располагались элементы. В частности, элементы матрицы А располагавшиеся во второй строке, будут находиться в диапазоне от 1А[2] до 1А[3].

Формат СБЯ, в частности, удобен для умножения матрицы на вектор. Пример 1.2. Рассмотрим задачу умножения разреженной матрицы А на вектор Ь:

а2,\ а2,2 ■■■ а2,1 а , а г, ...а

\ п, 1 я,2 т,т)

Данное умножение может быть реализовано следующим участком

кода:

Листинг 1.2. Умножение разреженной матрицы, хранимой в формате СБИ,

на вектор.

£ог(1 = 1; 1 < П+1; 1++)

{

Б[1] = 0;

}

:£ог(:1 = 1; ± < П+1; :1 + +)

{

1ог (j = ; j < ЗА [1 + 1] ; j++)

{

эш + = АА[Л *Ь [1А ] ] ;

}

}

1.2 Граф информационных связей

Приведем основные понятия, которые используются при анализе зависимостей в программе.

Вхождение переменной - это имя переменной в совокупности с тем местом в программе, в котором эта переменная появилась. Всякому вхождению (а для массивов - при конкретном значении индексного выражения) соответствует обращение к некоторой ячейке памяти. Если при обращении к ячейке памяти происходило чтение, то такое вхождение называется использованием (in), а если запись, то генератором (out). Пример 1.3. Рассмотрим оператор присваивания и присутствующие в нем вхождения:

Список литературы диссертационного исследования кандидат наук Штейнберг, Олег Борисович, 2014 год

Список литературы

1. Арапбаев Р.Н. // Анализ зависимостей по данным: тесты на зависимость и стратегии тестирования. // Диссертация на соискание ученой степени кандидата физико-математических наук, Новосибирск, ИСИ СО РАН, 2008 г., 116 с.

2. Арыков С.Б., Малышкин В.Э. // Система асинхронного параллельного программирования «Аспект» // Вычислительные методы и программирование. 2008. Т. 9, №1, с. 205-209.

3. Бабичев A.B., Лебедев В.Г. // Распараллеливание программных циклов./ Программирование // 1983, N 5, с. 52-63.

4. Буч Г., Рамбо Д., Джекобсон А. // Язык UML. Руководство пользователя // Пер. с англ. - М.: ДМК Пресс, 2001 - 432 е.: ил.

5. Буч Г. // Объектно-ориентированный анализ и проектирование с примерами приложений на С++, 2-е изд. // Пер. с англ. - М.: «Издательство БИНОМ», СПб.: «Невский диалект», 2000 - 560 е.: ил.

6. Вальковский В.А., // Распараллеливание алгоритмов и программ. Структурный подход // М., «Радио и связь», 1989 г., 176 с.

7. Векторизация программ // Векторизация программ: теория, методы, реализация // Сборник переводов статей М.: Мир, 1991. с. 246 - 267.

8. Воеводин В.В., Воеводин Вл.В. // Параллельные вычисления. // С-Петербург «БХВ-Петербург», 2002, 599 с.

9. Волконский В.Ю., Дроздов А.Ю., Ровинский Е.В. // Метод использования мелкоформатных векторных операций в оптимизирующем компиляторе. // Информационные технологии и вычислительные системы. № 3, 2004 г. с. 63-77.

10. Гамма Э., Хэлм Р., Джонсон Р., Влиссидес Дж. Приемы объектно-ориентированного проектирования. Паттерны проектирования. - СПб: Питер, 2001.-368 е.: ил.

11. Делиться не всегда полезно: оптимизируем работу с кэш-памятью // http://habrahabr.ru/companv/intel/blog/143446/ 25.07.2013.

12. Духанов А. В., Болгова Е. В., Гервич Л. Р., Колпаков В. Г., Кравченко Е. Н., Курочкин И. И., Масленников Е. Д., Офёркин И. В., Рубцов А. О., Смирнов С. А., Штейнберг О. Б., Юрушкин М. В. Предметно-ориентированные технологии создания виртуальных рабочих пространств в среде облачных вычислений Clavire Известия ВУЗов. Приборостроение, №5, 2013 г.

13. Ермолицкий А., Шлыков С. // Автоматическая векторизация выражений оптимизирующим компилятором. // Приложение к журналу «Информационные технологии», 2008, №11 с. 17-21.

14. Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения. 4-е издание. //-М.-Вузовская книга, 2001. 280с.

15. Зыков A.A. // Основы теории графов. // М., «Вузовская книга», 2004, 662 с.

16. Касперский // Подсистема кэш-памяти, как она есть // http://www.insidepro.com/kk/008/0Q8r.shtml дата обращения 25.07.2013.

17. Касьянов В.Н., Оптимизирующие преобразования программ/ М., «Наука», 1988 г., 336 с.

18. Кристофидес Н. // Теория графов. Алгоритмический подход. Второе издание. // - М.: Мир, 1978. 432 с.

19. Лазарева С. А. Использование многоуровневого внутреннего представления в автоматическом распараллеливании программ для многопроцессорных ЭВМ, диссертация на соискание ученой степени кандидата технических наук, Ростовский госуниверситет, Ростов-на-Дону, 2000 г., 150 с.

20. Линев A.B., Боголюбов Д.К., Бастраков С.И. Технологии параллельного программирования для процессоров новых архитектур. Учебник / Под ред. В.П. Гергеля. М.: Изд-во Московского ун-та, 2010, 160 с. - (Серия «Суперкомпью терное образование»)

21. Оптимизирующая распараллеливающая система www.ops.rsu.ru дата обращения 25.07.2013.

22. Пархи К. // Методы преобразования алгоритмов для параллельных процессоров // ТИИЭР, т. 77, 1989, №12, с. 96 - 114.

23. Петренко В.В. Внутреннее представление REPRISE распаралелливающей системы. РАСО'2008, Труды четвертой международной конференции «Параллельные вычисления и задачи управления», Москва.: 27-29 октября 2008 г.

24. Писсанецки С. Технология разреженных матриц. М., Мир, 1988, 411 с.

25. Разбиение цикла как пример высокоуровневой оптимизации http://habrahabr.rU/company/intel/blog/l61155/ дата обращения 25.07.2013.

26. Самарский A.A. // Введение в численные методы // «Наука», 1997, 239 с.

27. Страуструп Б. Язык программирования С++, 3-е изд. / Пер. с англ. — СПб.; М.: «Невский диалект» - «Издательство БИНОМ», 1999 г. - 991 е.: ил.

28. Фаддеева В.Н., Фаддеев Д.К. // Параллельные вычисления в линейной алгебре // «Кибернетика» №6, 1977, с 28-40.

29. Фаддеева В.Н., Фаддеев Д.К. // Параллельные вычисления в линейной алгебре. 2// «Кибернетика» №3, 1982, с 19-44.

30. Харари Ф. Теория графов. М.: Мир, 1973 г. 300 с.

31. Штейнберг Б.Я. // Математические методы распараллеливания рекуррентных программных циклов на суперкомпьютеры с параллельной памятью // Ростов-на-Дону, Издательство Ростовского университета, 2004, 192 с.

32. Штейнберг Б.Я. // Распараллеливание программных рекуррентных циклов // «Информационные технологии», 2004, №4, с. 16-23.

33. Штейнберг Б.Я. // Распараллеливание рекуррентных циклов с условными операторами // «Автоматика и телемеханика», 1995, №6, с. 176184.

34. Штейнберг Б.Я., Черданцев Д.Н., Науменко С.А., Бутов А.Э., Петренко В.В .И Преобразования программ для открытой распараллеливающей системы// Искусственный интеллект. Научно-теоретический журнал. Институт проблем искусственного интеллекта НАНУ. Украина, Донецк, ДонДИШИ, «Наука и Освита», 2003, №3, с. 97-104.

35. Штейнберг Б.Я. Открытая распараллеливающая система // РАСО'2001/ Труды международной конференции «Параллельные вычисления и задачи управления». М., 2-4 октября 2001 г., ИПУ РАН, с. 214-220.

36. Штейнберг Б.Я., Макошенко Д.В., Черданцев Д.Н., Шульженко A.M. Внутреннее представление в Открытой распараллеливающей системе // Искусственный интеллект. Научно-теоретический журнал. Институт проблем искусственного интеллекта НАНУ. Украина, Донецк, ДонДИШИ, "Наука и Освита", 2003, № 4, с. 89-97.

37. Штейнберг Б.Я., Черданцев Д.Н., Штейнберг Р.Б., Шульженко A.M., Бутов А.Э., Науменко С.А., Петренко В.В., Шилов М. В., Гуфан К.Ю., Тузаев A.B., Арутюнян О. Э., Морылёв Р.И. Обучающая распараллеливанию программа на основе ОРС. // Научно-методическая конференция «Современные информационные технологии в образовании: Южный Федеральный округ»/ 13-14 мая 2004 г., Ростов-на-Дону, Тезисы докладов, с. 248-250.

38. Штейнберг Б.Я., Штейнберг Р.Б., Морылев Р.И., Петренко В.В., Полуян С.В., Штейнберг О.Б., Баглий А.П., Нис З.Я., Скиба И.С., Юрушкин М.В., Шаповалов В.Н., Алымова Е.В., Кравченко E.H., Гуда С.А. «Диалоговый высокоуровневый оптимизирующий распараллеливатель

программ» Свидетельство о государственной регистрации программы для ЭВМ №2011617205 от 15 сентября 2011г.

39. Штейнберг Б.Я., Абрамов A.A., Алымова Е.В., Баглий А.П., Гуда С.А., Дубров Д.В., Кравченко E.H., Морылев Р.И., Нис З.Я., Петренко В.В., Полуян C.B., Скиба И.С., Шаповалов В.Н., Штейнберг О.Б., Штейнберг Р.Б., Юрушкин М. Диалоговый высокоуровневый автоматический распараллеливатель (ДВОР). Научный сервис в сети Интернет: Труды Всероссийской суперкомпьютерной конференции (20-26 сентября 2010 г., г. Новороссийск). М.: Изд-во МГУ, 2010., с. 71-75

40. Штейнберг Б.Я., Алымова Е.В., Баглий А.П., Гуда С.А., Кравченко E.H., Морылев Р.И., Нис З.Я., Петренко В.В., Скиба И.С., Шаповалов В.Н., Штейнберг О.Б. Особенности реализации распараллеливающих преобразований программ в ДВОР. РАСО'2010/ Труды международной конференции «Параллельные вычисления и задачи управления». М., 26-28 октября 2010 г., ИПУ РАН, с.787-854

41. Штейнберг Б.Я., Кравченко E.H., Морылев Р.И., Нис З.Я., Петренко В.В., Скиба И.С., Шаповалов В.Н., Штейнберг О.Б., Штейнберг Р.Б. Особенности реализации распараллеливающих преобразований программ в ДВОР. Известия ВУЗов. Приборостроение, т. 52, №10, 2011 г. с. 87-89.

42. Штейнберг О.Б. // Распараллеливание рекуррентных циклов // «Высокие информационные технологии в науке и производстве» Тезисы докладов Ростов-на-Дону, Издательство Ростовского университета, 2006, с. 80.

43. Штейнберг О. Б. Распараллеливание рекуррентных циклов с нерегулярным вычислением суперпозиций. «Известия ВУЗов. Северокавказский регион. Естественные науки», №2, 2009 г., с. 18-21.

44. Штейнберг О. Б., Суховерхов С.Е. // Автоматическое распараллеливание рекуррентных циклов с проверкой устойчивости // «Информационные технологии», 2010, №1, с. 40-45.

45. Штейнберг О.Б. // Минимизация количества временных массивов в задаче разбиения циклов // «Известия ВУЗов. Северо-Кавказский регион. Естественные науки», 2011, №5 с. 31-35.

46. Штейнберг Р.Б. Вычисление задержек в стартах конвейеров для суперкомпьютеров со структурно-процедурной организацией вычислений. // Международная научно-техническая конференция «Интеллектуальные и многопроцессорные системы»/ 22-27 сентября, 2003, Дивноморское, Россия, Тезисы докладов, с. 43-47.

47. Шульженко A.M. // Исследование информационных зависимостей программ для анализа распараллеливающих преобразований // диссертация на соискание учёной степени кандидата технических наук // РГУ Ростов-на-Дону 2006, 200 с.

48. Шульженко A.M. Автоматическое определение циклов ParDo в программе // Известия вузов. Северокавказский регион. Естественные науки. Приложение 2011, №05. с. 77-88.

49. A Guide to Auto-vectorization with Intel С++ Compilers http://software.intel.com/en-us/articles/a-guide-to-auto-vectorization-with-intel-c-compilers/ 27.04.2012

50. Aho A. V., Lam M. S., Sethi R., Ullman J. D.// Compilers: Principles, Techniques, and Tools // Second Edition.— Pearson Education, Inc, 2007.

51. Allen R., Kennedy K. // Optimizing compilers for modern architectures // San Francisco, San Diego, New York, Boston, London, Sidney, Tokyo // Morgan Kaufmann Publishers, 2002, 790 p.

52. Andrei Alexandrescu. Modern С++ Design: Generic Programming and Design Patterns Applied - Addison Wesley, 2001. - 352 p.

53. Auto-vectorisation in gcc http://gcc.gnu.org/projects/tree-ssa/vectorization.html дата обращения 25.07.2013.

54. Auto Vectorizer in Visual Studio 2012

http://b1ogs.msdn.com/b/nativeconcurrencv/archive/2012/04/12/auto-vectorizer-in-visual-studio-11-overview.aspx 12.04.2012.

55. DVM система http://www.keldysh.ru/dvm/.

56. Feautrier P. // Array Expansion. //In ACM Int. Conf. on Supercomputing, St Malo, 1988.

57. Graham S.L., Snir M., Patterson C.A. // Getting Up To Speed: The Future Of Supercomputing // National Academies Press, 2005. - 289 p.

58. Kulkurni D., Stumm M. // Loop and Data Transformations: A Tutorial. Technical Report CSRI 337 // Computer Systems Research Institute, University of Toronto, June 1993, 53 p.

59. Lamport L. The Coordinate Method for the parallel execution of DO loops // Sagamore Computer Conference on Parallel Processing.- 1973, p. 1-12.

60. Lamport L. // The parallel execution of DO loops // Commun. ACM.- 1974.-vol.17, №2, p. 83-93.

61. LLVM 3.3 Vectorization Improvements http://blog.llvm.org/2013/05/llvm-33-vectorization-improvements.html 28.05.2013.

62. Muchnick S.S. // Advanced Compiler Design and Implementation // San Francisco: Morgan Kauffman, 1997. - 856 p.

63. Polaris. Automatic Parallelization of Conventional Fortran Programs. http.V/polaris.cs.uiuc.edu/polaris/polaris-old.html.

64. Pottenger W.M. // Theory, Techniques and Experiments in Solving Recurrences in Computer Programs. // Thesis PhD in Computer Science, University of Illinois at Urbana-Champaign, May 1997.

65. Rose compiler http://rosecompiler.org/.

66. Steinberg В., Abramov A., Alymova E., Baglij A., Guda S., Demin S.,

Dubrov D., Ivchenko A., Kravchenko E., Makoshenko D., Molotnikov Z., Morilev ?

R., Nis Z., Petrenko V., Povazhnij A., Poluyan S., Skiba I., Suhoverkhov S., Shapovalov V., Steinberg O., Steinberg R. Dialogue-based Optimizing

113

Parallelizing Tool and C2HDL Converter. Proceedings of IEEE East-West Design & Test Symposium (EWDTS'09). Moscow, Russia, September 18-21, 2009 (pp. 216-218)

67. SUIF compiler system http://suif.stanford.edu/.

68. The Portland Group http://www.pgroup.com/.

69. Суворова E.A., Шейнин Ю.Е. // Проектирование цифровых систем на VHDL // Санкт-Петербург, «БХВ-Петербург», 2003, 560 с.

70. Wolfe М. // High performance compilers for parallel computing // Redwood city, Addison-Wesley Publishing Company, 1996. - 570 p.

71. Wolfe M., Banerjee U. Data Dependence and its Application to Parallel Processing/ International Journal of Parallel Programming // Vol.16, N 2, 1987, p. 137-178.

о о о с а с о о 3 о

К.фгМ.Н. Ж\'ЧК"ОН К. II

Binнп - :on<i

ei нональнаи научио-нрактичсская конференция молодых лченых и специалистов Высокие информационные технологии

Оргкомитет конференции награждает

III геинберг O.K.

«аняншего

на секции информации» циклов»

I место

«Алгоритмическое обеспечение

и методы оораоогки «Распараллеливание рек\ ррентных

(ОМ

ЮК.1

[ре

-1С

ОП1

им

председатель программного

Заворнн

Р© 0 Dili! ОЖ ¿Ш ФВДЖРАЦШШ

СВИДЕТЕЛЬСТВО

о государственной регистрации программы для ЭВМ

№2011617205

«Диалоговый высокоуровневый оптимизирующий распараллеливатель программ»

Правообладатель(ли): Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Южный федеральный университет» (Южный федеральный университет) (RU)

Автор(ы): Штейнберг Борис Яковлевич, Штейнберг Роман Борисович, Морылев Роман Игоревич, Петренко Виктор Владимирович, Полуян Степан Вячеславович, Штейнберг Олег Борисович, Баглий Антон Павлович, Hue Зиновий Яковлевич, Скиба Иван Сергеевич, Юрушкин Михаил Викторович, Шаповалов Василий Николаевич, Алымова Елена Владимировна, Кравченко Евгений Николаевич, 1уда Сергей Александрович (RU)

Заявка №2011615302

• Дата поступления 15 ИЮЛЯ 2011 Г.

Зарегистрировано в Реестре программ для ЭВМ

15 сентября 2011 г.

Руководитель Федеральной службы по интеллектуальной собственности, патентам и товарным макам

jy) .// Б.Ч. Симонов

¡5,1___Л