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

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ Институт- систем информатики

На правах рукописи УДК 681.3.06

БУЛЫШЕВА Лариса Андреевна

РАЗРАБОТКА МЕТОДА МНОГОФУНКЦИОНАЛЬНОГО СОВМЕЩЕНИЯ ПРИ АВТОМАТИЗАЦИИ ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ ДЛЯ УШ - ПРОЦЕССОРОВ

05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Новосибирск - 1993

Работа выполнена в Вычислительном центре СО РАН и Институте теоретической и прикладной механики СО РАН

Научный руководитель : доктор физико-математических наук,

профессор H.H. Миренков Научный консультант : доктор физико-математических наук,

профессор В.М. Фомин

Официальные оппоненты: доктор физико-математических наук,

доцент В,А: Евстигнеев, доктор технических наук, профессор, А. Д. Рычков

Ведущая организация: Башкирский Университет

Защита состоится " " Д^РД 1994 г. в _ч. на заседании

специализированного совета К 003.93.01 по присувдению степени кандидата наук при Институте систем информатики СО РАН по адресу: 630090, Новосибирск, 50, пр. Акад. Лаврентьева, 6.

С диссертацией можно ознакомиться в читальном зале Вычислительного центра СО РАН (пр. Акад. Лаврентьева, 6).

Автореферат разослан "10 " декабРя 1993 года.

Ученый секретарь Специализированного Совета К 003.93.01 к.ф.-м.н.•

В.К. Сабельфельд

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность теш. Современные высокопроизводительные ЭВМ - это компьютеры параллельного действия. Одним из перспективных направлений среди них являются VLIW-процессоры (Very Long Instruction Word processors - т.е. процессоры с длинным командным словом). Особенность VLIW-машин - необычно длинное командное слово, разделенное на поля микроопераций, каждое из которых управляет одновременной работой определенного функционального устройства. Среди наиболее известных в настоящее время VLIW - ЭВМ, можно отметить: AP-I2QB, AP-I90L, FPS-164 (США), ЕС-2706, 2709 (Болгария); QA/I, QA/2 (Япония); Эльбрус - 3(Россия); Тгасе-7/100, 7/200, 14/200, 28/300 (США). Длина командного слова в этих машинах колеблется от 64 до Т024 бит.

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

В данной работе для повышения эффективности параллельного программирования на основе учета некоторых дополнительных свойств, связанных с проведением численных экспериментов и организацией параллельного счета, предлагается метод многофункционального совмещения вычислений. Многофункциональное совмещение предполагает, в общем случае, одновременное выполнение в рамках одного VLIW - процессора и единственной программы, нескольких процедур над несколькими- входными наборами данных. Эффективность этого метода связывается со следующими особенностями проведения численных экспериментов: многовариантности расчетов, использовании многомодульных комплексов программ, применении

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

Разработка многофункциональных процедур • позволяет повышать эффективность вычислений и использования высокопроизводительных ■систем параллельного действия, благодаря:

- укрупнению программ и увеличению их внутреннего • параллелизма, что приводит к улучшенной загрузке функциональных устройств;

- использованию промежуточных результатов, полученных при вычислении одних функций, для вычисления других;

- применению оптимизирующих преобразований кода методами упаковки и сокращению числа выполнений общих операций;

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

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

Целью работы является исследование и реализация метода многофункционального совмещения при автоматизации параллельного программирования для УЬШ - процессоров. Достижение цели предполагает:

- анализ существующих методов и средств оптимизации вычислений для УШ/-архитектур,

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

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

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

А

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

'- разработаны параллельные алгоритмы совмещенной реализации тригонометрических и цилиндрических функций;

- реализована библиотека базовых многофункциональных процедур;

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

Практическая ценность диссертационной работы состоит в разработке:

- библиотеки многофункциональных процедур для спецпроцессоров типа ЕС-2706;

- экспериментальной системы интегрирования программ, после распараллеливания, позволяющей автоматизировать трудоемкий процесс разработки процедур с повышенной реализационной эффективностью и функционирующей на ЭВМ типа IBM РС-АТ.

Результаты сравнения вычислений многофункциональных процедур, написанных на языке ассемблерного типа, и тех же процедур, но без совмещения, показали, что достигается ускорение вычислений в 1.22.7 раза, а по сравнению с процедурами, написанными на языке Фортран для EC-I066 - в 4.6- 9.2 раза.

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

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

Публикации и апробация работы. По теме диссертации опубликовано 10 работ. Основные результаты докладывались на 10-ом Всесоюзном семинаре "Параллельное программирование и высокопроизводительные системы: метода представления знаний в информационных технологиях" (Уфа, 1990), Всесоюзной школе-семинаре по комплексам программ математической физики (Ростов - на - Дону, 1990), Международной конференции " Технологии параллельных вычислений "(Новосибирск, 1991), 24 Региональной математической школе-конференции

(Екатеринбург, 1993), Российской научно-технической конференции: "Интерактивные системы" (Ульяновск, 1993), на семинарах в ИТПМ СО РАН, ВЦ СО РАН И ИСИ СО РАН.

Структура и обьем работы. Диссертация состоит из введения, трех глав, заключения, приложений и списка литературы из 99 наименований, 3 рисунков и 13 таблиц. Общий обьем работы - 170 страниц. Приложения - 29 страниц.

СОДЕРЖАНИЕ РАБОТЫ

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

Первая глава посвящена обзору существующих методов и средств оптимизации вычислений для процессоров с длинным командным словом. В первом параграфе отмечаются перспективность VbIW-архитектур и кратко их особенности, связанные с необычно длинным командным словом и возможностью одновременного выполнения различных микроопераций в одной микрокоманде. Для достижения наивысшей производительности этих машин эффективное микропрограммирование, т.е. учет мелкозернистого параллелизма ( уровня микроопераций) становится решающим фактором и превращается в быстро развивающуюся область научных исследований, как за рубежом, так и у нас в стране. Обычно микропрограммная оптимизация выполняется как минимизация требуемой памяти и/или времени вычислений. Минимизация памяти достигается сокращением числа используемых слов памяти. Минимизация времени вычислений - уменьшением числа микрокоманд. Оптимизация для VLTW-архитвктур имеет дело как со стандартными оптимизирующими преобразованиями, так и с особенными, присущими только ей. Эти особенные преобразования вызваны параллелизмом выполнения микроопераций, наличием конфликтов ресурсов и полей микрокоманды. Методы оптимизации вычислений для этих архитектур, получили название методов упаковки и делятся на методы, локальной, глобальной упаковки и программной конвейеризации. Отмечается, что несмотря на теоретическую сложность, рассматриваемых методов, получены практические алгоритмы, рекомендуемые к использованию.

Во втором параграфе описываются базовые определения и методы

локальной упаковки микропрограмм. Упаковка микропрограммы -процесс преобразования кода исходной программы в семантически эквивалентный высокопараллельный код для ТТЛ-архитектуры с более плотной загрузкой функциональных устройств или это процесс комбинирования микроопераций в микрокоманды для сокращения места и /или времени, необходимого для выполнения микропрограммы. Локальная упаковка микропрограммы - процесс формирования последовательности микрокоманд на базе анализа линейных участков или базисных блоков, транслируемых программ. Линейным участком называют часть программы без условных переходов и циклов. Преобразования подразумевают полную переработку исходного кода на основе анализа графа программных зависимостей, учета конфликтов ресурсов и микроопераций, времени срабатывания различных функциональных • устройств и выполнения оптимизирующих преобразований, как традиционных, так и особенных, присущих УЪШ-архитектурам. Описываются алгоритмы "первый пришел - первый обслужен критического пути, метод ветвей и границ, планирования списков. Все алгоритмы рассматриваются в рамках одной вычислительной модели. При этом предполагается, что заданы граф зависимостей данных, конфликты микроопераций и длительность выполнения микрокоманд, ресурсы неограничены. Рассматриваются примеры, поясняющие работу этих алгоритмов, отмечаются их достоинства и недостатки, оценивается вычислительная сложность и делаются вывода о возможности применения на • практике. Методы локальной упаковки используются в качестве одного из шагов в методах глобальной упаковки.

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

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

В четвертом параграфе описываются методы программной конвейеризации. Эти методы являются дополнительным средством к описанным ранее методам оптимизации вычислений для УЬШ-архитектур и применяются обычно к циклам: для совмещения вычислений итераций внутренних циклов, т.е. планируя запуск новой итерации в каждом такте. Известно, что разработка программных конвейеров сопряжена с вычислительными трудностями и относится, к труднорешаемым проблемам при наличии ресурсных ограничений, также как и получение оптимальной последовательности микрокоманд из микроопераций, в методах упаковки микропрограмм. Рассматриваются следующие методы: совершенная конвейеризация, конвейерное планирование, расширенное конвейерно-проникающее планирование. Описываются основные шаги алгоритмов, приводятся оценки их вычислительной сложности.

Формулируются следующие выводы: - методы упаковки - мощный базис оптимизирующих преобразований для УЫШ-архитектур; -несмотря на теоретическую сложность, они показали свою высокую практическую ценность; - однако, эффективность применения этих методов имеет ограниченный характер, особенно для алгоритмов с существенно последовательной природой вычислений.

Вторая глава посвящена разработке библиотеки

многофункциональных процедур и параллельных алгоритмов на базе совмещенной реализации нескольких функций над несколькими наборами данных для УЬШ-процессора типа ЕС-2706. Отмечаются особенности архитектур с длинным командным словом и процессора ЕС-2706, как процессора с такой архитектурой, рассматривается новый подход к разработке средств автоматизации параллельного программирования -ме.тод многофункционального совмещения и созданная на его основе библиотека высокоэффективных процедур, раскрывается сущность метода, показывается его место среди известных подходов к оптимизации вычислений для ТЫЩ-архитектур и применение при разработке эффективных параллельных алгоритмов для таких

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

Во втором параграфе рассматриваются архитектуры процессоров с длинным командным словом, описываются особенности УЬШ-архитектур и спецпроцессора ЕС-2706, как процессора с данной архитектурой. Отмечается, что ЕС- 2706 имеет следующие особенности: - один поток команд и несколько параллельно, работающих функциональных устройств; - длинный формат команда, разделенный на поля, обеспечивает одновременное управление всеми функциональными блоками в каждом такте; - время выполнения каждой операции составляет известное число тактов; - конвейерные сумматор и умножитель, разделение памяти данных на блоки с чередованием адресов обеспечивают возможность запуска в каждом такте новой

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

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

В четвертом и пятом параграфах описываются параллельные алгоритмы совмещенной реализации тригонометрических скалярных функций и цилиндрических функций. Проблемам вычисления функций на ЭВМ посвящены многочисленные исследования. Известно, что выбирая к применению алгоритмы, необходимо учитывать специфику архитектуры. Проведенный анализ реализаций алгоритмов базовых функций спецпроцессора ЕС-2706 и других ЭВМ, позволил разработать параллельные алгоритмы совмещенного вычисления функций, которые учитывают специфику этого процессора (например, что деление выполняется программно, длину конвейерных устройств и др.), используют результаты (или их часть) одних, для вычисления других. Рассматриваются алгоритмы вычисления функций синус и косинус от одного аргумента, синус и косинус от двух аргументов, показательных функций от мнимого аргумента, функций тангенс и

котангенс от одного аргумента, функций тангенс и котангенс от двух

•

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

Рассмотрим эффективность метода многофункционального совмещения на примере реализации в совмещенном режиме тригонометрических функций SIN(X) и COS(X), и укажем источники эффективности вычислений. Основные шаги параллельного алгоритма вычисления этих функций в виде многофункциональной процедуры STTíCOS(X) следующие: -I) приведение аргумента к интервалу (0, ти/2). Абсолютное значение аргумента умножается на масштабирующий множитель 2/к и выделяется целая и дробная части I и 7. В качестве аргументов используют F и T-F. Процедура приведения выполняется один раз для двух функций, что дает экономию вычислений;

-2) вычисление полиномов. Производится по одной формуле для двух аргументов F и I-F, так как C0S(X)= SIN(X+u:/2), а после приведения аргументы отличаются только на единицу:

SIN(F)= A*F+F 3*(B+C*F 2)+F7*(B+E*F 2), SIN(I-F)= A*(I-F)+(I-F)3*(B+C*(I-F)2)+(I-F)7*(B+E*(I-F)2), где А, В, С, D, E - известные коэффициенты, хранящиеся в памяти констант. Одновременное вычисление полиномов обеспечивает более полную загрузку функциональных устройств спецпроцессора EC-270S;

- 3) идентификация функций. Если I- четное, то SIN(X) определяется через SIN(F), a COS(X) через STN(I-F) и наоборот. Проверка на четность выполняется один раз для двух функций;

- 4Определение знаков функций. Знаки вычисляются в зависимости от четности величин I, 1/2 и знака X по известным формулам. Указанные действия выполняются один раз и дают определенную экономию вычислений. Данный алгоритм позволяет повысить скорость вычисления функций по сравнению с последовательным их вычислением по алгоритму из библиотеки базовых функций ЕС-2706 в 1.83 - 1.89 раз.

Эффективность идеи многофункционального совмещения демонстрируется далее на примере реализации алгоритма, вычисляющего в совмещенном режиме четыре функции: SIN(X), COS(X), SIN(Y), COS(Y) в процедуре SINCOS(X.Y). Алгоритм подобен описанному, но отличается вычислениями полиномов, которые производятся по схеме Горнера с тем же числом членов ряда, что и базовая процедура: ((((E*W )*W 2+C)*W 2+B )*W 2+A)*W, где W -четырехкомпонентный вектор аргументов = {F, I-F, F1, I-F1). Данная схема обеспечивает повышенную эффективность использования функциональных устройств спецпроцессора ЕС-2706. Алгоритм позволяет повысить скорость вычислений в 2.56-2.62 раза по сравнению с вычислениями по микропрограммам из библиотеки базовых Функций. Точность вычислений в этих процедурах совпадает с точностью г-азовой процедуры и составляет 5*10 Приводится

описание параллельных . алгоритмов для вычисления других, перечисленных ранее тригонометрических функций и которые базируются на описанных выше алгоритмах, и указываются источники повышения эффективности счета. Отмечается, что разработанные многофункциональные процедуры, могут быть применены при решении задач статистической физики и переноса излучения методом' Монте-Карло. Они нашли применение при решении задач геофизики для вычисления цилиндрических функций, которые в свою очередь требуются для широкого класса задач дифракции и распространения волн. Далее рассматривается эффективность применения многофункционального совмещения при вычислении цилиндрических функций. Приводятся соответствующие параллельные алгоритмы, указываются источники повышения эффективности вычислений и достигаемые коэффициенты ускорения вычислений. Так, при вычислении в совмещенном режиме функций Бесселя и Неймана нулевого и первого порядков и различных их сочетаний, достигается ускорение вычислений в 1.2-2.7 раз по сравнению с вычислением этих же функций, но без совмещения. Приводятся обобщенные данные по достигаемым коэффициентам ускорения счета.

В шестом параграфе приводится состав реализованной библиотеки многофункциональных ■ процедур , и процедур без совмещения, разработанных для расширения библиотеки базовых функций спецпроцессора ЕС-2706, проведения сравнительного анализа,

определения ускорения вычислений, и анализируется точность их вычислений. Точность вычислений'в спецпроцессоре по сравнению с ЕС-Т06В на один знак больше и составляет восемь десятичных цифр, что вызвано большей разрядностью мантиссы и соответствующим алгоритмом округления. Библиотека процедур, разработанных для спецпроцессора ЕС-2706 составляет более 200 К байт.

Формулируются следующие выводы: - предлагаемый метод является развитием методов упаковки; - метод увеличивает внутренний параллелизм программ и может быть эффективен даже в случае последовательной природы . алгоритмов; - представляется целесообразным применить данный подход для разработки средств автоматизации параллельного программирования: библиотек многофункциональных процедур и автоматических объединителей (интеграторов) программ; - разработанные многофункциональные процедуры и соответствующие им параллельные алгоритмы дают ускорение вычислений; - эти и подобные наборы процедур могут быть эффективно применены в задачах геофизики и статистической физики; -созданные процедуры являются базой для развития библиотеки нового вида для спецпроцессоров типа ЕС-270в и других параллельных ЭВМ.

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

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

различных последовательных программ, или генерировать код, обслуживающий обработку нескольких наборов данных на базе одной и той же программы. Сущность интеграции заключается в обьединении программы с другими в единое целое для экономии вычислений от совмещения и упаковки, экономии накладных расходов по запуску программ, сокращении числа операций ввода/вывода и других, а не в ее "расщеплении" на части, как происходит в распараллеливателях. Цель интеграции - создание новой (интегрированной) программы, Функционально эквивалентной группе совмещаемых программ, но с большим параллелизмом и соответствием архитектуре.

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

Б третьем параграфе описывается экспериментальная система интегрирования идентичных программ после распараллеливания для УЫ7)-процессора типа ЕС-2706, приводится общая структура системы и описываются функции ее частей, а также базовый алгоритм, его реализация и результаты численных экспериментов. Система состоит из головной и вспомогательных процедур. Головная программа читает входной код, задает параметры интеграции, шаблоны микрокоманд, идентифицирует микрооперации, вызывает соответствующие процедуры обработки, которые принимают решения о копировании, упаковке, оптимизации, сохранении результатов и затем передают управление обратно для обработки следующих микрокоманд, выводит выходную программу на экран монитора. Вспомогательные процедуры обрабатывают каждый оператор, который идентифицирован в микропрограмме.

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

транслятора, либо написана программистом на языке АРАЬ асоемблнрного типа, для процессоров типа ЕС-2706. На выходе системы получается интегрированная, высокопараллельная, упакованная программа, семантически эквивалентная исходной и позволяющая проводить вычисления с п наборами данных. Интегрированная программа создается "Интегратором" также на языке АРАЪ. Основные шаги алгоритма.

Шаг Т. Вспомогательные действия. Шаг заключается в подготовке к выполнению программных преобразований: читается входной код для спецпроцессора ЕС-2706 на языке_ АРАЪ; задаются параметры интеграции, образцы микроопераций и др.;

Шаг 2. Построение трассы программы. Шаг заключается в сведении исходной программы к новой программе и базируется на предположении известного метода планирования трасс. Суть которого в том, что для огромного числа программ (особенно для научного кода) вычисления пи одному (или нескольким) путям доминируют- ь вычислительном времени лтих щюграмм. Такой наиболее важный путь планируется и упаковывается первым и т.д.

Шаг. 3. Идентификация типа микроопераций в микрокоманде. Шаг осуществляется путем сравнения в циклах микрокоманд исходной программы и образцов - шаблонов допустимых микроопераций.

Шаг. 4. Упаковка микрокоманд. Шаг заключается в локальной и глобальной упаковке микроопераций в длинные поля микрокоманд исходного кода. Выполняется локальная упаковка на основе метода "первый пришел, первый обслужен ". Но это и глобальная упаковка, так как базисным блоком является целая программа, и упаковывается несколько базисных блоков одновременно, путем перемещения микроопераций из одного блока в другой, что не позволял метод планирования трасс. На данном шаге формируется, по-существу, и программный конвейер, как побочный . результат совмещения вычислений, если позволяют ресурсы и алгоритм программы. На этом шаге, также, принимается решение о копировании исходной микрокоманды в рабочий файл, где создается интегрированная программа. Здесь же выполняются оптимизирующие преобразования, такие как, однократное чтение совместно используемых констант, сокращение идентичных вычислений над одними и теми же, неизменяемыми данными. Эти преобразования осуществляются системой

б зависимости от типа анализируемой микрооперации и ее "окружения", т.е. микроопераций этой же микрокоманда и следующих за ней макрокоманд в программе. Этим достигается экономия вычислений. Для корректности процесса упаковки анализируются конфликты полей микрокоманды и конфликты ресурсов, и не нарушается неявно используемый граф информационно-логических связей. Решение о сохранении результатов микроопераций принимается автоматически системой за счет введения компенсационного кода с использованием принятых в системе для этих целей регистров и устройств. Выполняется переименование операндов в микрооперациях, т.е. смена используемых устройств при построении копии микрокоманды для поддержания семантической корректности и сохранения информационно-логических связей.

Затем осуществляется переход на шаг 3, пока не будет обработана последняя микрокоманда микропрограммы. Результат работы "Интегратора" автоматически заносится в текстовый файл и может использоваться для дальнейшей работы. . Вычислительная сложность алгоритма сводится к 0(n , где п - длина исходного кода.

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

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

В заключении формулируются основные результаты работы.

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

0СНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Учитывая особенности организации численного моделирования, предложен метод многофункционального совмещения (ШС) вычислений, который позволяет увеличить внутренний параллелизм программ и связан о вмполнйнием преобразований, обратных преобразованиям распараллеливателей. Проведен обзор методов и средств оптимизации вычислений для VT.TW - архитектур и покачано место ШС. среди них.

2. На основе предложенного подхода разработаны и реализованы параллельны« алгоритмы поьмлщвнного вьчислчкия тригонометрических и цилиндр^'-<ео«их функций, которые составили библиотеку многофункциональных процедур, обладав ».их поьышннной реализационной эффективное''" ью.

Проведеннке чиоданнне »ксп*римвнтн демонстрируют ускорено вычислений ь многофункциональных процедурах по сравнению с их последовательным выполнением.

4. Создана экспериментальная система автоматической интеграции программ после распараллеливания, позволяющая за счет новой организации вычислений и преобразований кода, повысить, эффективность вычислений-в программах с последовательной природой алгоритмов.

Автор благодарит научного руководителя H.H. Миренкова и научного консультанта R.M. Фомина за внимание к работе, помощь и поддержку.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Т. Булычева Л.А., Миренков H.H. Метод многофункционального совмещения и его реализация для матричного процессора ЕС-2706. // Тез. докл. ТО Всесоюзн. семинара Параллельное программирование: -Уфа, 1990. - С. Т5Я-ТБ9.

2. Булышева' Л.А., Блинов В.Д., Миренков H.H. Вычисление цилиндрических функций методом многофункционального совмещения на матричных процессорах. Новосибирск, 1990. - Т4 с. - (Препринт / АН СССР, Сиб.отд-ние, ВЦ; 9Т9).

■ 3. Булышева Л.А., Миренков H.H. Многофункциональные процедуры и

паряллельнов программирование //Программирование. - Т99Т. - N б. -С. TTR-T24.

4. Wlrenkov N.Tí., Bulysheva Ь.А. Multiple function multiple data procedures arid parallel programming. // Proc. of the Int. Con*. Parallel Computing Technologies. - Novosibirsk, 1991. - P. ?9?-303.

5. Булышева -IT.А., Миренков H.H. Разработка эффективных алгоритмов и библиотек программ нового типа методом многофункционального совмещения для процессоров с архитектурой длинных командных слов // Вычислительные технологии. Труды Школы-семинара по комплексам программ математической физики. (Ростов-на-Дону, Т990) - Новосибирск: РАН ИВТ, 1992. - T.I, N 2, ч.Т. - С.ЯТ-69.

6. Булышева Л.А. Методы и средства оптимизации вычислений для процессоров о. ТТ.Ш-аруитектурой. Новосибирск, 1993. - 38 с. -(Припринт / РАН , Сиб.отд-ние, ВЦ; 975).

7. Булниева Л.А. Разработка программных средств на основе многофункционального совмещения для VT.IW - архитектур. // Тез. д'.ш. 24 Региональной школы-конференции молодых ученых. Екатеринбург, 1993. - 2 с. ■

о. Булншява Л.А. Высокоэффективные программные средства на основе многофункционального совмещения для VLIW - процессоров. // Тез. докл. 5 школы молодых ученых по численным методам механики сплошной среды . - Ростов- на- Дону, 1993. - С. 5.

9. Булышева Л.А. Система интеграции программ после распараллеливания для VLIW-архитектур . // Интерактивные системы: Тез. докл. Российской научно-технич. конференции. - Ульяновск, 1993. - С. 9-10.

10. Булышева Л.А. Экспериментальная система интеграции программ после распараллеливания .- Новосибирск, 1993. - 28 с. - (Препринт /РАН , Сиб.отд-ние, ИТПМ; 7-93).