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

Бакулев Александр Валериевич

МОДЕЛИ И АЛГОРИТМЫ ОРГАНИЗАЦИИ МОБИЛЬНЫХ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ В СРЕДЕ МНОГОЯДЕРНЫХ ПРОЦЕССОРОВ

Специальность 05.13.11 —Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат диссертации на соискание ученой степени кандидата технических наук

О 3 ОЕЗ 2011

Рязань-2011

4843550

Работа выполнена на кафедре систем автоматизированного проектирования вычислительных средств ГОУВПО «Рязанский государственный радиотехнический университет».

Научный руководитель:

кандидат технических наук, доцент Телков Игорь Анатольевич

Официальные оппоненты:

доктор технических наук, профессор Каширин Игорь Юрьевич

кандидат технических наук, доцент Минаев Юрий Михайлович

Ведущая организация:

Московский государственный институт электроники и математики (технический университет)

Защита состоится 18.02.2011 г. в 12 часов на заседании диссертационного совета Д 212.211.01 в ГОУВПО «Рязанский государственный радиотехнический университет» по адресу: 390005, г. Рязань, ул. Гагарина, д. 59/1.

С диссертацией можно ознакомиться в библиотеке ГОУВПО «Рязанский государственный радиотехнический университет».

Автореферат разослан «12» января 2011 г.

Отзывы на автореферат в двух экземплярах, заверенные печатью организации, просим направлять по адресу: 390005, Рязань, ул. Гагарина, д. 59/1, Рязанский государственный радиотехнический университет.

Ученый секретарь диссертационного совета

канд. техн. наук, доцент

Пржегорлинский В.Н.

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

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

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

Большое разнообразие существующих сегодня архитектурных платформ, операционных систем (ОС), использующих многоядерные процессоры, а также технологий и языков программирования, положенных в основу последовательного ПО, заставляет искать решение указанной задачи для каждой из них в отдельности. Это создает вторую проблему — проблему переносимости параллельных программ, то есть ставит задачу приведения ПО в соответствие с требованием мобильности. Термин мобильное ПО (portable software) подразумевает программы, которые могут быть откомпилированы и корректно выполнены на вычислительных системах (ВС) с различной архитектурой, без каких-либо изменений.

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

Степень разработанности темы. Научно-методической основой исследований представленных в диссертационной работе являются труды отечественных и зарубежных учёных и специалистов: ГлушковаВ.М, Воеводина В.В., Воеводина Вл.В., Прангишвили И.В., Виленкина С.Я., Поспелова Д.А., Касьянова В.Н., Корячко В.П., Телкова И.А., Скворцова C.B., Каширина И.Ю., Цейтлина Г.Е., Ющенко E.JL, Бутомо И.Д., Дейкстры Э., Пратга Т., Таненбаума Э., Дала Э., Хоара Ч.Э., Brandis М.М., Kazi I.H., Steffan J.G., Mowry T.C., Gupta R и других.

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

В работах Глушкова В.М., Цейтлина Г.Е., Ющенко E.JI. предложен аппарат систем алгоритмических алгебр, предназначенный для исследования свойств алгоритмов и программ. В работах Каширина И.Ю. исследованы свойства алгоритмических языков на базе алгебраических моделей, предложен подход к представлению данных и управляющих конструкций программ на основе формального описания программной машины. Во второй главе диссертации предложено развитие данных подходов с позиции обеспечения мобильности данных, разработано семейство алгебраических систем типов данных.

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

В работах Скворцова C.B. предложены модели и методы организации параллельных процессов на мелкозернистом уровне параллелизма на основе теоретико-графового подхода. В диссертационной работе предлагается использовать графовые модели на крупноблочном уровне параллелизма.

В работах Steffan J.G. и Mowry Т.С представлено описание метода спекулятивной многопоточности и проведён анализ возможных способов повышения его эффективности на этапе исполнения, в частности за счет использования аппаратной реализации контроля нарушения зависимостей по данным. В работах Kazi LH. предложен способ организации спекулятивного многопоточного кон-веера для параллельной обработки смежных итераций цикла. В третьей главе диссертационной работы предложены формальная модель метода спекулятивной многопоточности и алгоритмы повышения эффективности его применения на этапе выделения спекулятивных циклических регионов.

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

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

В соответствии с поставленной целью необходимо решить следующие основные задачи:

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

2) разработать формальные модели мобильного представления последовательных программ;

3) разработать алгоритмы перевода исходных текстов последовательных программ на языках высокого уровня в переносимую параллельную форму;

4) разработать алгоритмы планирования и оптимизации вычислительного процесса исполнения программ, представленных в переносимой параллельной форме, в среде ВС с многоядерными процессорами;

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

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

Научная новизна работы состоит в следующем.

1. Предложена формальная модель мобильного параллельного промежуточного кода (МППК), основанная на алгебраических моделях типов данных и операций языков программирования, обеспечивающая мобильность параллельного представления последовательных программ, заданных на различных языках высокого уровня, отличающаяся использованием нового базиса управляющих операций.

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

3. Предложена формальная модель подсистемы управления процессами ОС, основанная на предложенной модели МППК и модели автоматной сети, обеспечивающая представление вычислительного процесса на уровне ОС среды многоядерных процессоров.

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

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

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

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

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

- спроектированы программы-конверторы исходных текстов последовательных программ с языков высокого уровня Паскаль и Си в мобильный параллельный промежуточный код;

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

Апробация результатов диссертации. Результаты, полученные в рамках работы над диссертацией, докладывались на 5 международных и 8 всероссийских научно-технических конференциях: международных конференциях «Управление и информационные технологии на транспорте» (Санкт-Петербург, 1999), «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций» (Рязань, 1997,1999, 2000, 2001), всероссийских конференциях «Новые информационные технологии в научных исследованиях и образовании» (Рязань, 1997, 1998, 1999, 2000, 2006, 2008 — 2 доклада, 2009 — 2 доклада, 2010 — 2 доклада).

Публикации. По теме диссертации опубликовано 30 работ: 13 статей (в том числе 3 статьи в журналах из перечня ВАК), 16 тезисов докладов на международных и всероссийских конференциях, одно свидетельство об официальной регистрации программы.

Внедрение результатов работы. Результаты, полученные в диссертационной работе, внедрены в разработки научно-технической продукции филиала ФГУП «ГНПРКЦ «ЦСКБ-Прогресс» - «ОКБ «Спектр» и научно-производственного предприятия ООО «ЭЛЬФ 4М», а также представляют часть НИР № 7-98, № 42/10-01, выполненных в Рязанском государственном радиотехническом университете.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, библиографического списка (157 источников). Основной текст работы содержит 177 страниц, 20 таблиц, 22 рисунка. В приложении на 3 страницах приведены акты внедрения результатов и свидетельство о регистрации программы для ЭВМ.

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

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

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

Выполнен обзор существующих систем параллельного программирования, автоматического и полуавтоматического распараллеливания последовательных программ (DVM-система, трС, Т-Система, V-Ray, OpenMP, Cilk, Аг-gonne/GMD, BERT 77, FORGExplorer, КАР, VAST-C/Parallel, PIPS), в результате которого были отмечены их достоинства и общие недостатки.

Произведён анализ существующих способов организации мобильных вычислений, на основе которого выделено три уровня обеспечения мобильности: уровень языка программирования, уровень ОС, уровень архитектуры ВС и сделан вывод, что в полной мере мобильность можно обеспечить лишь на основе использования концепции промежуточного языка и абстрактной виртуальной машины. В работе рассмотрены реализации программных систем, использующих данную концепцию (BCPL, UCSD Pascal, Java Virtual Machine, Common Language Runtime, Low Level Virtual Machine) и выявлены их общие недостатки.

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

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

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

2. В рамках данной концепции возникает задача построения оптимального по структуре и набору операций мобильного параллельного промежуточного представления — МППК.

3. Модель МППК должна быть основана на формальных моделях данных и программ языков программирования. При этом выбор был сделан в пользу применения алгебраического и теоретико-графового математического аппарата.

4. Возникает необходимость использования как статических, так и динамических методов на этапе анализа и синтеза параллельных программ на основе МППК, а также их адаптации к особенностям мобильного промежуточного представления путём разработки новых эффективных алгоритмов.

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

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

Предложено использовать в качестве промежуточной формы последовательной программы представление, основанное на алгебраической модели типов данных и операций императивных языков программирования высокого уровня. Формальная модель типов данных языков программирования представлена семействами частично универсальных алгебраических систем и 35={ГДГ/,Г/,Г/}, соответствующих элементарным (тип целых чисел Г/, тип действительных чисел Г*, перечислимый тип Т°) и составным («массив» Г/, «структура» Г/, «объединение» Т", «ссылочный тип» Г/) типам данных. Предложенная модель отличается явной спецификацией атрибутов типов данных, зависящих от машинной реализации и включенных в состав алгебраических систем, что обеспечивает мобильность представления данных программы. Определены основные множества алгебраических систем, задана их сигнатура и приведены примеры представления типов языков программирования Паскаль и См в предложенной алгебраической модели типов данных.

Для представления операционной семантики конструкций языков программирования предложена алгебраическая модель операций, как совокупность алгебраических систем операций над данными =<0^,Р/,К/> и управляющих операций 1с=<Ос,Гс,Яс>. Основное множество О} составляют допустимые выражения над данными, в качестве базисного подмножества используются операции из сигнатуры алгебраических систем типов данных, представленные в виде функциональных термов. Сигнатура ^ представлена множеством

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

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

концепции охраняемых операторов. Предложен следующий состав базиса алгебры управляющих операций: О® = {csq,cgd,cmg,cmc}, где csq соответствует структуре «последовательность» в аксиоматике Хоара, cgd называется «стражем», задающим условие вьтолнения вложенного в него оператора, cmg, стс называются «объединителями» ветвей условной и циклической конструкций соответственно. Множество Rc определяет отношения эквивалентности и вхождения управляющих структур из Ос. Сигнатура алгебры представлена множеством Fc = {®} на основе единственной операции композиции управляющих структур. В работе определены правила конструирования производных управляющих операций на основе предложенного базиса. В соответствии с которыми основное множество алгебраической системы было расширено операциями, представляющими основные управляющие конструкции языков программирования высокого уровня {с'г,с'°", С*\ С"41, С™} — «альтернатива», цикл с параметром, цикл с пред и постусловием и «переключатель»:

с< = cf{p(o^,cM)®cM ®cZ(c?,c^);

см = С;?(Г(Х) о{))®с™х(сГ, с*,с*)®с*2(р(х, см) ®

®ci+3(c,.+4 ®сиг(х, о()))®с^{р{хУ}), 0); _

= с, ®cZ(cn cfd2, c*)<9c*(p(of), см)9см ), 0);

cgd(p0^),cM)®cM®...

Ci+2*+l ^ ®cmg (cgd cgi cgd cgd \

i+2k+2 Vi > j+2 ' i+4' —> i+2k /'

где Vc, e Oc, Vpk — предикат стража, задающий условие выполнения охраняемого оператора, хе (Е1 \JE°) —элемент из основного множества алгебры целого или перечислимого типов, / = е Op Oj £ Of, G Oj.

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

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

На основе разработанных алгебраических моделей в работе предложена математическая модель МППК в виде системы:

РЖ = (X, Т, V, F, G, 8Т, 8у, SF, 8Р, 8„ 80), где X — множество информационных объектов (переменных и констант), Т s (ТЕ — множество типов данных, V = } — множество операторов программы, Fc(/;Uy — множество операционных объектов (функций), описываемых алгебраическими системами операций над данными и управляющих операций, G = {gj} — множество регионов программы — подграфов

управляющего графа программы, порожденных теми вершинами-операторами, условия выполнения которых одни и те же. Связи между объектами системы PIR заданы следующими отношениями: от'.Х—*Т — отображение, определяющее тип информационных объектов; Sy :G—*V — отображение, определяющее распределение операторов по регионам программы; SF:V —» F — отображение, определяющее функции операторов; 8P'.G—$G — отображение, определяющее множество непосредственно вложенных регионов; 8,: V —> X" | Х1 с X — отображение, определяющее входную информацию операторов (множество операндов); 8а: V —» Xq \ Ха С X — отображение, определяющее выходную информацию операторов (множество результатов).

Согласно модели, каждый оператор, входящий в состав у'-го региона, рассматривается как тройка v, = (SF, 8It80) | v( eVj =8y(gj)cV. Все операторы нумеруются исходя из лексикографического порядка их следования в программе. Программу целиком определяет полный перечень всех операторов <vl(SF,SI,ö0),v2(SF,SnS0).....vm(8F,8„80)>, что отражает операционный подход к представлению программы. Предложена и другая трактовка программы, как совокупности информационных объектов, подвергаемых некоторым операциям. Для этого были заданы отношения Ss, 8W, обратные к S,, 80, а информационные объекты представлены в виде xl=(ST,SR,S№). Программа тогда представляется как последовательность изменения состояний информационных объектов < х,(ST,8X,SW), хг(5T,Sg,Sw).....xm(ST,6R,öw)>.

На основе предложенной модели МППК разработан алгоритм, осуществляющий крупноблочное разбиение программы на совокупность связанных регионов. Предложенное алгебраическое представление программы позволило осуществить построение графа регионов за один просмотр списка управляющих конструкций программы, с трудоёмкостью алгоритма порядка 0(п) от числа операций МППК, аналогичные известные алгоритмы имеют сложность порядка 0(п3).

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

Ош—И ' т—сиг

возможная антизависимость, — возможная выходная зависимость, бла-

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

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

Так как в среде исполнения универсальных ВС с многоядерными процессорами за планирование вычислений отвечают сервисы ОС, в работе разработана иерархическая модель подсистемы управления процессами ОС, выполненная по результатам анализа наиболее общих закономерностей современных многозадачных ОС. На верхнем уровне предложено использовать алгебраическую модель подсистемы управления процессами М ={©, й7), средний уровень представляет сеть управляющих автоматов 91(.Г), а на нижнем уровне используется предложенная во второй главе модель МППК.

В состав основного множества © = Р, I, Г2, Л, П, А, Г} алгебраической модели входят соответственно: множество задач, процессов, информационных объектов, объектов синхронизации, управляющих автоматов, уровней приоритетов процессов, система диспетчеризации процессов, граф информационных связей между процессами. Сигнатура модели Й7 = (0,Ф) задаёт множество отношений О = {£,р,^,7],(Т} на объектах модели и множество функций ф = (Фсгеше' Ф,гтш!еФрпоП1у} на элементах множества процессов. Определены следующие отношения: £ описывает состав задачи з1 Е 2, как совокупность её процессов г]е Рп е: Ъ Р| 3(з,.£г7) => з,.е Ъ, е РпР1 сР,е з,.; р описывает структуру управляющих связей процесса вычисления и разделяет множество процессов Р на подмножества родительских РА с Р и дочерних Р°£Р, р:РА->Р°\ 32^Р°,РЛ^Р, £ = {Р и I, Г) задает структуру информационного графа Г с (Р XI) и (IX Р), отражающего всю совокупность информационных зависимостей процессов задачи; 7]: Р —» П взвешивает элементы множества процессов значениями приоритетов обслуживания; с: I —» £2 определяет закрепление объектов синхро-

низации за разделяемыми между конкурирующими процессами информационными объектами.

Так как вычислительный процесс носит асинхронный характер, в рамках среднего уровня иерархической модели предложено представить его в виде сети 91 {Г) взаимосвязанных управляющих автоматов двух классов. Отдельный

автомат класса А =< (X, (р, 5,6, Л, .у, > однозначно сопоставляется каждому элементу из множества процессов zi —> Д-1 е Р, Д- е А с Л, / = 1,и, отдельный автомат В =< /9,4* > — соответственно каждому элементу, принад-

лежащему множеству информационных объектов у) —» В] | V у] е I,

е В С Л, ) = 1, т. Информационный граф Г определяет связи — линии обмена между автоматами разных типов составляющих сеть ЩГ). При этом смена состояния автомата каждого типа приводит к выработке определенного набора выходных сигналов, на основе которых происходит срабатывание связанных с ним автоматов другого типа. В работе определены входной и выходной алфавиты двух классов автоматов, заданы функции их входов и выходов.

На основе предложенной во второй главе модели МППК и модели подсистемы управления процессами разработан алгоритм статического синтеза параллельной реализации последовательной программы. Процесс синтеза рассматривается как задача построения укладки я(А) макрографа программы А = (С,и,3), заданного на множестве вершин-регионов МППК

g¡e 0,1 = 1, взвешенных временем их выполнения т^г)е 3 на одном процессорном элементе в тактах процессора, связанных дугами и информационных и управляющих зависимостей, в пространственно-временную 1} -решётку РТ, образованную парой ортогональных осей координат, с осью Р пространства процессорных элементов ВС и осью Т времени выполнения в тактах процессора.

В работе введён ряд характеристик укладки: проекция вершины графа = 0,1=1,Ы, определяющая процессорный элемент, ис-

полняющий программный регион в заданный момент времени; ts -сечение укладки = g¡^G}, определяющее множество параллельно исполняемых регионов в момент времени ; рк -сечение укладки = = Рк> Я,е О}, определяющее множество регионов, назначенных на исполнения на заданный процессорный элемент рк; ширина /5-

сечения укладки И^(ж(А)) ; общая ширина укладки

н

¡¥(я(А)) = тах{Ж. (х(А))}; высота укладки Н = Т(тг(А)) = -1, определи

ляющая общее время исполнения всех программных регионов укладки, где

— конечная фиктивная вершина графа. Предложен способ определения наиболее раннего E(gt) и наиболее позднего L(gnH) из возможных сроков выполнения Vg'j вершины графа, для заданной укладки, на основе расчета длин критических путей на графе. Осуществлена постановка задачи получения оптимальной по времени исполнения укладки программы, как задача минимизации целевой функции: Т(тг(А)) —» min на системе ограничений, заданных структурой связей графа и максимальным количеством доступных процессорных элементов р ВС:

's! <g'j-Tig,), з(g„gj)e U, t = Vf,j = lN;

■ gi>E(gl), i=m ^ _■

ft' * ft'. 3/, I g, E G(t,) A g, e G{t,), i = W =

W(k(A)) < p.

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

Так как методы статического синтеза параллельных программ невозможно использовать для программных регионов, имеющих зависимости вида ^Zt-in' ^to-mа> ^out-out> в работе предложено использовать динамический синтез, основанный на методе спекулятивной многопоточности. Чтобы организовать многопоточное выполнение подобных регионов, называемых спекулятивными

\fgt е GSP | GSP С G, i = I,К, формируется динамическая последовательность стадий их исполнения, называемых эпохами Ve^ е EPt с ЕР \

j = 1 ,N,N =| EP. I,е. e p£P(g,),pEF :—) ЕР. Например, для циклического

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

Лемма 3.1. При одновременном параллельном спекулятивном исполнении р эпох ер £у+1,... на вычислительной системе состоящей из р

процессорных элементов, гарантируется корректность выполнения Уе^ и отсутствие её повторного перезапуска, где + + р — 1 — номера эпох,

Лемма 3.2. При одновременном параллельном спекулятивном исполнении р эпох в] е ЕР | ] = - р + 1),ЛГ =| ЕР | на вычислительной системе состоящей из р процессорных элементов, корректность выполнения | к = 1,(р — 1) гарантируется, если подтверждена корректность эпохи и проверки корректности результатов между каждой парой эпох

, бу+и ) | т = 0, — 1) дали положительный результат.

Лемма 3.3. Если при одновременном параллельном спекулятивном исполнении р эпох в], е;+1,..., «у+ , е ЕР \ ] = 1, (ТЯ - р +1), N =| ЕР | на вычислительной системе состоящей из р процессорных элементов Зе^ | к = 1, (р — 1), для которой было зафиксировано нарушение корректности выполнения, то после перезапуска и повторного исполнения её корректность будет гарантирована.

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

==2+1/2. . . 1}+^. '

где V (д,) — объём вычислений циклического региона при последовательном исполнении; У (§,) — удельный объём вычислений, приходящийся на один процессорный элемент при параллельном исполнении циклического региона; УСОП!/ — объём дополнительных вычислений на организацию спекуляции; р — количество процессорных элементов ВС; Ргг_ — вероятность нарушения зависимости для одной итерации циклического региона; пМЕ — число смежных итераций циклического региона , последовательно размещённых внутри каждой эпохи; п„ — число операторов в теле цикла региона gi.

Предложено использовать ) в качестве критерия оптимальности

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

за один просмотр списка регионов параллельного промежуточного кода, с трудоёмкость порядка О(Ы), где N =| С^ |.

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

Для осуществления исследования разработанных алгоритмов был проведён ряд численных экспериментов, в рамках которых были написаны программы с реализацией алгоритмов на языке программирования Си++. В качестве среды разработки программ использовалось кроссплатформенное программное обеспечение ОТ 4.6 с компилятором йСС 4.4.0. Результаты численных экспериментов представлены на рис. 1 - рис.4.

1012 14%!в20 22 34 26ХэаЗ!Э1ХЭеЮСМ46«а)

/ '

»3aJ5««®5S®W70 75 8Di

S ICC «Я 1101151» 13

* 'Саотзяимыый "«Првдлситий алкр<ги алгсрп"ы

Рис.1. Зависимость времени выполнения про- Рис.2. Сравнение времени выполнения программы

граммы реализации алгоритма исключения one- реализации алгорнгма выделения регионов и со-

ратора continue из МППК от количества опера- поставляемого с ним от количества операторов

торов входной последовательности входной последовательности

1, Л1С

—Решение т- — г^едлажшый тоаэд ветвей глгориш „

кфгниц

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

39 31 33 3S 37 э& 41 С «

* °Ссгестж*ммиЯ ""Првцломжыв алгсеиш &ЯГЛЖТМ

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

Другая часть исследований была направлена на определение области практического применения результатов работы. Итогом явилась разработка программных средств поддержки этапа трансляции исходных текстов последовательных программ на языках Си и Паскаль в МППК, структура которых представлена на рис.6.

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

Мобильный параллельный промежуточный код программы

Среда исполнения параллельной виртуальной машины j

Модуль загрузки параллельного |j промежуточнго кода

Модуль статического распараллеливания

H

Мящь привязки к параметрам целевой срезы исполнения

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

î 1

Операционная система

WINDOWS уг:'.'ООО ХР,< 200.1 Vi®;;

POSCi

BSD,' Unix

QKx; RTLlfmx

" Аппаратная платформа

ARM

Intel

My.siïasprKifçc.ojwat i ¡SM« Умапюттт ! \ *J*»*«4>» ! «pwwweja* ; • Hyp!?r-thr«äd;iiQ) j (Mute-core) : Ояног.уяпчт.нае

Рис.5. Архитектура параллельной виртуальной машины

/¡ш

/Паскаль /Шсколь

/Паска: Исходный

à

х......tïû+Ц

/ С in-л- : / ГЙ++1

j Исходный I текст ; программы

Конвертор исходных текстов Паскаль-программ а промежуточное представление i

M

Конвертор исходных текстов Си++ программ

в промежуточное представление ' ♦

/

Промежуточное представление программы

Модуш. анализа и предварительного распараллеливания

Мобильный параллельный промежуточный код программы

Рис.6. Программные средства преобразования исходных текстов программ в МППК

I

Lil L

□ Jjxïp/i и 2 >1*>1>а Ш 4 ядра I ilntp.l/мп) (Inh'l/limix) (AMD/uin)

4 iiitpa (ЛШ>Лтн\)

Рис.7. Результаты ускорения, полученного при многопоточном спекулятивном выполнения МППК на различных платформах

С помощью разработанных программных модулей было организовано многопоточное исполнение МППК программы архивации файлов (LZW) и программы реализации алгоритмов оперативного анализа, основанных на кратно-масштабном представлении данных (OLAP), в среде ОС Window ХР и Mandriva Linux 2010.1 на ВС с двухъядерным процессором Intel Core 2 Duo Е7200 и 4-х ядерным процессором AMD Phenom Х4 9650. Результаты сравнения произво-

дительности их выполнения с работой параллельной версии программы реализации алгоритмов оперативного анализа (РОЬАР), созданной вручную, представлены на рис.7.

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

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

В ходе выполнения работы были получены следующие результаты.

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

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

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

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

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

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

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

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

1. Бакулев A.B. Автоматическое распараллеливание последовательных программ // Новые информационные технологии: межвуз. сб. науч. тр. Рязань: РГРТА, 1997. С.31-37.

2. Бакулев A.B., Телков И.А. Инструментальные средства создания мобильного программного обеспечения // Проблемы передачи и обработки информации в информационно-вычислительных сетях: тез. докл. 7го междунар. науч-техн. семинара. - М.: НИЦПрИС, 1997. С. 13-15.

3. Бакулев A.B., Телков И.А Программные средства организации мобильных параллельных вычислений // Новые информационные технологии. Межвуз. сб. научн. трудов. Рязань: РГРТА, 1997. С. 25-31.

4. Бакулев A.B., Телков И.А. Разработка математической модели и инструментальных средств распараллеливания последовательных программ // Новые информационные технологии в радиоэлектронике: тез. докл. 2-ой всерос. науч.-техн. конф. - Рязань: РГРТА, 1997. С.27-29.

5. Бакулев A.B., Телков И.А. Математическая модель вычислительного процесса симметричной мультипроцессорной системы // Новые информационные технологии в радиоэлектронике: тез. докл. 3-ей всерос. науч.-техн. конф. - Рязань: РГРТА, 1998. С.45-46.

6. Бакулев A.B. Настройка мобильного кода на архитектурные особенности исполнительной системы // Новые информационные технологии: межвуз. сб. науч. тр. Рязань: РГРТА, 1998. С.15-20.

7. Бакулев A.B., Телков И.А. Оптимизация вычислений в SMP-системах // Математическое и программное обеспечение вычислительных систем: межвуз. сб. научн. тр. Рязань: РГРТА, 1999. С. 96-100.

8. Бакулев A.B., Телков И.А. Оптимизация параллельных вычислений в среде MICROSOFT WINDOWS NT // Новые информационные технологии в научных исследованиях и в образовании: тез. докл. 4-ой всерос. науч.-техн. конф. - Рязань: РГРТА, 1999. С.81-83.

9. Бакулев A.B., Телков И.А. Оптимизация параллельных вычислений // Проблемы передачи и обработки информации в информационно-вычислительных сетях: тез. докл. 8-го междунар. науч-техн. семинара. - Рязань, РГРТА, 1999. С.25-26.

10. Бакулев A.B., Телков И.А. Параллельные процессы в Windows NT // Вычислительные машины, комплексы и сети. Межвуз. сб. научн. трудов. Рязань: РГРТА, 1999. С. 112-115.

П.Бакулев A.B., Телков И.А. Программные средства организации мобильных параллельных вычислений // Управление и информационные технологии на транспорте: тез. докл. междунар. науч.-техн. конф. «Транском-99». - СПб: СПГУВК, 1999. С.195-198.

12. Бакулев A.B., Ручкин В.Н., Телков И.А. Вероятностная модель организации параллельных процессов // МГОУ-ХХШ-Новые технологии. Научно-технический журнал. - М, МГОУ, 2000. - №5. - С.35-37.

13. Бакулев A.B., Телков И.А. Конвертор исходных текстов программ с языка Паскаль в мобильный параллельный промежуточный код. М.: Роспатент, 2000 (свидетельство о регистрации программы для ЭВМ №2000610207 от 23.03.2000).

14. Бакулев A.B. Модель операционной среды при организации мобильных вычислений // Новые информационые технологии: межвуз. сб. науч. тр. Рязань, РГРТА, 2000. С. 4-6.

15. Бакулев A.B. Модель организации параллельных процессов в условиях стохастично-сти // Новые информационные технологии в научных исследованиях и в образовании: тез. докл. 5-ой всерос. науч.-техн. конф. - Рязань: РГРТА, 2000. - С.40-41.

16. Бакулев A.B., Телков И.А. Оценка случайной задержки времени исполнения взаимодействующих процессов // Проблемы передачи и обработки информации в информационно-вычислительных сетях: тез. докл. 9-ой междунар. науч-техн. конф. - Рязань, РГРТА, 2000. С. 3-5.

17. Бакулев A.B. Автоматная модель подсистемы управления процессами операционной системы // Новые информационные технологии: межвуз. сб. науч. тр. Рязань: РГРТА, 2001. С.133-137.

18. Бакулев A.B. Модель операций параллельного промежуточного кода // Проблемы передачи и обработки информации в сетях и системах телекоммуникаций: тез. докл. 10-ой междунар. научно-техн. конф. - Рязань, РГРТА, 2001. - С.3-5.

19. Бакулев A.B., Телков И.А. Алгебраическая модель операций мобильного промежуточного кода // Новые информационные технологии: межвуз. сб. науч. тр. Рязань: РГРТА, 2002. С.19-22.

20. Бакулев A.B. Представление управляющих конструкций универсальных языков в алгебраической системе управляющих операций // Новые информационные технологии: межвуз. сб. науч. тр. Рязань: РГРТА, 2002. С. 14-18.

21. Бакулев A.B. Повышение производительности выполнения последовательных программ в среде современных многоядерных процессоров // Новые информационные технологии в научных исследованиях и в образовании: тез. докл. 11-ой всерос. науч.-техн. конф,- Рязань: РГРТУ, 2006. - С.91-92.

22. Бакулев A.B., Бакулева М.А. Применение вейвлет-преобразования для анализа данных хранилища // Вестник РГРТУ. Научно-технический журнал. Выпуск 21. Рязань: РГРТУ, 2007. С. 57-60.

23. Бакулев A.B., Бакулева М.А., Телков И.А. Алгоритм автоматизации проектирования хранилищ данных // Вестник РГРТУ. Научно-технический журнал. Выпуск 23. Рязань: РГРТУ, 2008. С. 90-93.

24. Бакулев A.B. Использование спекулятивных многопоточных вычислений в среде многоядерных архитектур // Новые информационные технологии в научных исследованиях и в образовании: тез. докл. 13-ой всерос. науч.-техн. конф.. - Рязань: РГРТУ, 2008.140-141.

25. Бакулев A.B., Бакулева М.А. Параллельная реализация алгоритмов оперативного анализа, основанных на кратномасшгабном представлении данных хранилища // Новые информационные технологии в научных исследованиях и в образовании: тез. докл. 13-ой всерос. науч.-техн. конф. - Рязань: РГРТУ, 2008. С.139-140.

26. Бакулев A.B., Бакулева М.А. Алгоритм исключения операторов выхода за пределы ветви управляющей конструкции в произвольной точке // Новые информационные технологии в научных исследованиях и в образовании: тез. докл. 14-ой всерос. науч.-техн. конф. -Рязань: РГРТУ, 2009.-С. 191-192.

27. Бакулев A.B. Алгоритм приведения промежуточного кода последовательной программы в соответствие с правилом однократного присваивания // Новые информационные технологии в научных исследованиях и в образовании: тез. докл. 14-ой всерос. науч.-техн. конф. - Рязань: РГРТУ, 2009. С. 190-191.

28. Бакулев A.B. Алгоритм синтеза параллельной реализации последовательной программы для вычислительных систем, построенных на базе многоядерных процессоров // Вестник РГРТУ. Научно-технический журнал. Выпуск 30. Рязань: РГРТУ, 2009. С. 43-49.

29. Бакулев A.B. Алгоритм разбиения управляющего графа последовательной программы на слабо связанные регионы // Новые информационные технологии в научных исследованиях и в образовании: тез. докл. 15-ой всерос. науч.-техн. конф. - Рязань: РГРТУ, 2010. С. 191192.

30. Бакулев A.B. Выявление информационных зависимостей между операторами последовательной программы // Новые информационные технологии в научных исследованиях и в образовании: тез. докл. 15-ой всерос. науч.-техн. конф. - Рязань: РГРТУ, 2010. С. 191-192.

Бакулев Александр Валериевич

МОДЕЛИ И АЛГОРИТМЫ ОРГАНИЗАЦИИ МОБИЛЬНЫХ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ В СРЕДЕ МНОГОЯДЕРНЫХ ПРОЦЕССОРОВ

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Бумага офисная. Печать цифровая. Усл. печ. л. 1,0. Тираж 100 экз.

Рязанский государственный радиотехнический университет. 390005, г.Рязань, ул.Гагарина, д.59/1.

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

ВВЕДЕНИЕ

1. АНАЛИЗ ПРОБЛЕМЫ ОРГАНИЗАЦИИ МОБИЛЬНЫХ ПАРАЛ- 12 ЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ

1.1. Анализ существующих языков и систем параллельного программиро- 13 вания

1.2. Анализ существующих систем автоматического и полуавтоматическо- 16 го распараллеливания последовательных программ

1.3. Анализ формальных моделей данных, алгоритмов и программ

1.3.1. Модель алгоритма

1.3.2. Модель программы

1.4. Анализ существующих алгоритмов и методов распараллеливания по- 38 следовательных программ

1.4.1. Методы и алгоритмы, используемые на стадии анализа последова- 39 тельной программы

1.4.2. Методы и алгоритмы, используемые на стадии синтеза параллель- 41 ной версии программы

1.5. Анализ существующих способов организации мобильных вычислений

1.5.1. Достижение переносимости на уровне ЯВУ

1.5.2. Переносимость в пределах заданной ОС

1.5.3. Архитектура ВС и обеспечение переносимости ПО

1.5.4. Использование промежуточного представления и абстрактной вы- 50 числительной машины

2. МОДЕЛЬ ПАРАЛЛЕЛЬНОГО ПРОМЕЖУТОЧНОГО КОДА И 55 АЛГОРИТМЫ ПРЕОБРАЗОВАНИЯ ИСХОДНЫХ ТЕКСТОВ ПОСЛЕДОВАТЕЛЬНЫХ ПРОГРАММ В ПРОМЕЖУТОЧНЫЙ КОД

2.1. Модель типов данных

2.1.1. Элементарный тип данных

2.1.2. Составной тип данных

2.2. Модель операций

2.2.1. Семантика операций над данными

2.2.2. Семантика управляющих операций

2.3. Модель параллельного промежуточного представления

2.3.1. Разработка алгоритма исключения оператора break из программы

2.3.2. Разработка алгоритма исключения оператора continue из програм- 93 мы

2.3.3. Разработка алгоритма выделения регионов на основе управляю- 96 щей структуры программы

2.4. Модель параллельного промежуточного кода

2.4.1. Выявление параллелизма между регионами параллельного про- 101 межуточного кода

3. СИНТЕЗ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ НА ОСНОВЕ 107 ПАРАЛЛЕЛЬНОГО ПРОМЕЖУТОЧНОГО КОДА

3.1. Модель операционной системы как среды функционирования парал- 108 дельных процессов

3.1.1. Алгебраическая модель подсистемы управления процессами ОС

3.1.2. Автоматная сеть как модель параллельного вычислительного про- 112 цесса

3.2. Статический синтез параллельной реализации последовательной про- 116 граммы для мультипроцессорной вычислительной системы с общей памятью

3.2.1. Разработка алгоритма статического синтеза параллельной про- 121 граммы

3.2.2. Разработка алгоритма отображения параллельной программы на 125 модель операционной среды

3.2.3. Уточнение длительности исполнения параллельных регионов про- 127 граммы в условиях неопределенности

3.2.4. Расчет величины уточняющей задержки на основе предваритель- 129 ных статистических испытаний

3.3. Динамический синтез параллельной реализации последовательной про- 134 граммы для мультипроцессорной вычислительной системы с общей памятью

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

3.3.2. Расчет характеристик использования метода спекулятивной мно- 143 гопоточности для динамического распараллеливания циклов

3.3.3. Выделение спекулятивных регионов и эпох на основе параллель- 148 ного промежуточного кода

4. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ РАЗРАБОТАННЫХ 154 АЛГОРИТМОВ

4.1. Экспериментальное исследование характеристик разработанных алго- 154 ритмов

4.1.1. Экспериментальное исследование алгоритма исключения опера- 155 тора break

4.1.2. Исследование алгоритма исключения оператора continue

4.1.3. Экспериментальное исследование алгоритма выделения регионов

4.1.4. Экспериментальное исследование алгоритма статического синтеза 160 параллельной программы

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

4.2.1. Программные средства поддержки этапа преобразования последо- 162 вательных программ в мобильный параллельный промежуточный код

4.2.2. Программные средства поддержки этапа исполнения параллель- 163 ного промежуточного кода

4.3. Результаты внедрения 167 ЗАКЛЮЧЕНИЕ 169 СПИСОК ЛИТЕРАТУРЫ 171 ПРИЛОЖЕНИЯ

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

ВС — вычислительная система;

МППК — мобильный параллельный промежуточный код;

ОС — операционная система;

ПВМ — параллельная виртуальная машина;

ПО — программное обеспечение;

ЭВМ — электронная вычислительная машина;

ЯВУ — язык высокого уровня;

MPI — интерфейс передачи сообщений (Message Passing Interface);

POSIX — переносимый интерфейс операционных систем Unix (Portable

Operating System Interface for Unix);

РУМ — виртуальная параллельная машина (Parallel Virtual Machine);

SMP — симметричная мультипроцессорная обработка (Symmetric Multiprocessing).

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

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

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

Большое разнообразие существующих сегодня архитектурных платформ, операционных систем (ОС), использующих многоядерные процессоры, а также технологий и языков программирования, положенных в основу последовательного ПО, заставляет искать решение указанной задачи для каждой из них в отдельности. Это создает вторую проблему — проблему переносимости параллельных программ, то есть ставит задачу приведения ПО в соответствие с требованием мобильности. Термин мобильное ПО (portable software) подразумевает программы, которые могут быть откомпилированы и корректно выполнены (или корректно интерпретированы) на ВС с различной архитектурой, без каких-либо изменений [118].

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

Степень разработанности темы. Научно-методической основой исследований представленных в диссертационной работе являются труды отечественных и зарубежных учёных и специалистов: Глушкова В.М, Воеводина В.В., Воеводина Вл.В., Прангишвили И.В., Виленкина С.Я., Поспелова Д.А., Касьянова В.Н., Корячко В.П., Телкова И.А., Скворцова C.B., Каширина И.Ю., Цейтлина Г.Е., Ющенко E.JL, Бутомо И.Д., Дейкстры Э., Пратта Т., Таненбаума Э.,

Дала Э., Хоара Ч.Э., Brandis М.М., Kazi I.H., Steffan J.G., Mowry T.C., Gupta R и других.

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

В работах Глушкова В.М., Цейтлина Г.Е., Ющенко E.JI. предложен аппарат систем алгоритмических алгебр, предназначенный для исследования свойств алгоритмов и программ. В работах Каширина И.Ю. исследованы свойства алгоритмических языков на базе алгебраических моделей, предложен подход к представлению данных и управляющих конструкций программ на основе формального описания программной машины. Во второй главе диссертации предложено развитие данных подходов с позиции обеспечения мобильности данных, разработано семейство алгебраических систем типов данных.

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

В работах Скворцова C.B. предложены модели и методы организации параллельных процессов на мелкозернистом уровне параллелизма на основе теоретико-графового подхода. В диссертационной работе предлагается использовать графовые модели на крупноблочном уровне параллелизма.

В работах 81ейап .Ш. и Мошгу Т.С представлено описание метода спекулятивной многопоточности и проведён анализ возможных способов повышения его эффективности на этапе исполнения, в частности за счет использования аппаратной реализации контроля нарушения зависимостей по данным. В работах 1.Н. предложен способ организации спекулятивного многопоточного кон-веера для параллельной обработки смежных итераций цикла. В третьей главе диссертационной работы предложена формальная модель метода спекулятивной многопоточности и алгоритмы повышения эффективности его применения на этапе выделения спекулятивных циклических регионов.

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

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

Задачи работы. В соответствии с поставленной целью основными задачами диссертационной работы являются следующие:

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

2) разработать формальные модели мобильного представления последовательных программ;

3) разработать алгоритмы перевода исходных текстов последовательных программ на языках высокого уровня в переносимую параллельную форму;

4) разработать алгоритмы планирования и оптимизации вычислительного процесса исполнения программ, представленных в переносимой параллельной форме, в среде ВС с многоядерными процессорами;

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

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

В качестве инструментальных средств использовалось кроссплатформен-ное программное обеспечение ОТ 4.6 с компилятором GCC 4.4.0 [35, 78, 102, 54].

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

1. Предложена формальная модель мобильного параллельного промежуточного кода (МППК), основанная на алгебраических моделях типов данных и операций языков программирования, обеспечивающая мобильность параллельного представления последовательных программ, заданных на различных языках высокого уровня, отличающаяся использованием нового базиса управляющих операций.

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

3. Предложена формальная модель подсистемы управления процессами ОС, основанная на предложенной модели МППК и модели автоматной сети, обеспечивающая представление вычислительного процесса на уровне ОС среды многоядерных процессоров.

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

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

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

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

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

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

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

Апробация результатов диссертации. Результаты, полученные в рамках работы над диссертацией, докладывались на международных [30, 12, 24, 29,

33] и на всероссийских научно-технических конференциях [14, 16, 19, 11, 7, 18, 8, 10, 34, 26, 27].

Публикации. По теме диссертации опубликовано 30 работ: 13 статей [13, 22, 6, 17, 23, 20, 21, 9, 5, 32, 15, 28, 31] (в том числе 3 статьи в журналах из перечня ВАК), 16 тезисов докладов на международных и всероссийских конференциях. Получено свидетельство о регистрации программы для ЭВМ (Роспатент. №2000610207) [25].

Внедрение результатов работы. Результаты, полученные в диссертационной работе, внедрены в разработки научно-технической продукции филиала ФГУП «ГНПРКЦ «ЦСКБ-Прогресс» - «ОКБ «Спектр» и научно-производственного предприятия ООО «ЭЛЬФ 4М», г.Рязань, а также представляют часть НИР № 7-98 «Рабочая станция разработчика мобильного программного обеспечения для параллельных вычислительных систем на основе совре- . менной вычислительной базы», НИР № 42/10-01 «Модели, методы, инструментальные средства и научно-методическое обеспечение процесса проектирования параллельных систем с использованием СА8Е-технологии», выполненных в Рязанском государственном радиотехническом университете.

Структура и объем диссертации. Диссертация состоит из введения, че- . тырех глав, заключения, списка литературы (157 источников), изложенных на 177 страницах, содержит 20 таблиц и 22 рисунка. В приложении на 3 страницах приведены акты внедрения результатов и свидетельство о регистрации программы для ЭВМ.

ЗАКЛЮЧЕНИЕ

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

В ходе выполнения работы были получены следующие результаты.

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

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

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

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

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

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

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

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

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

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

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

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

1. Абрамов С.М., Кузнецов A.A., Роганов В.А. Кроссплатформенная версия Т-системы с открытой архитектурой// Вычислительные методы и программирование. 2007. Т. 8. №1. Раздел 2. С. 175-180.

2. Арапов Д.М., Калинов А.Я., Ластовецкий А.Л., Дедовских H.H. Посыпкин H.A. Язык и система программирования для высокопроизводительных параллельных вычислений на неоднородных сетях// Программирование. 2000. - №4. - С. 55-80.

3. Ахо А., Сети В., Ульман Дж. Компиляторы: принципы, технологии и инструменты. -М.: Издательский дом "Вильяме", 2007.

4. Ахо А., Ульман Дж., Хопкрофт Дж. Структуры данных и алгоритмы. М.: Издательский дом "Вильяме", 2000.-384с.

5. Бакулев A.B. Автоматическое распараллеливание последовательных программ //Новые информационные технологии: Межвуз. сб. науч. трудов. Рязань: РГРТА, 1997. с.31-37.

6. Бакулев A.B. Автоматная модель подсистемы управления процессами операционной системы// Новые информационные технологии: Межвуз. сб. науч. трудов. Рязань: РГРТА, 2001. с.133-137.

7. Бакулев A.B. Алгоритм синтеза параллельной реализации последовательной программы для вычислительных систем, построенных на базе многоядерных процессо-ров//Вестник РГРТУ. Выпуск 30. Рязань: РГРТУ, 2009. С. 43-49.

8. Бакулев A.B. Модель операций параллельного промежуточного кода//Тез. докл. 10-ой Международной научно-технической конференции "Проблемы передачи и обработки информации в сетях и системах телекоммуникаций". Рязань, РГРТА, 2001. - с.3-5.

9. Бакулев A.B. Модель операционной среды при организации мобильных вычислений// Новые информационые технологии. Межвузовский сборник научных трудов. Рязань, РГРТА, 2000.

10. Бакулев A.B. Настройка мобильного кода на архитектурные особенности исполнительной системы// Новые информационные технологии: Межвуз. сб. науч. трудов. Рязань: РГРТА, 1998. с.15-20.

11. Бакулев А.В. Представление управляющих конструкций универсальных язы-ков в алгебраической системе управляющих операций// Новые информационные технологии: Межвуз. сб. науч. трудов. Рязань: РГРТА, 2002. с. 14-18.

12. Бакулев А.В., Бакулева М.А. Применение вейвлет-преобразования для анализа данных хранилища//Вестник РГРТУ. Выпуск 21. Рязань: РГРТУ, 2007. С. 57-60.

13. Бакулев А.В., Бакулева М.А., Телков И.А.Алгоритм автоматизации проектирования хранилищ данных//Вестник РГРТУ. Выпуск 23. Рязань: РГРТУ, 2008. С. 90-93.

14. Бакулев А.В., Ручкин В.Н., Телков И.А. Вероятностная модель организации параллельных процессов// МГОУ-ХХШ-Новые технологии. Научно-технический журнал. М, МГОУ, 2000. - №5. - с.35-37.

15. Бакулев А.В., Телков И.А. Алгебраическая модель операций мобильного промежуточного кода// Новые информационные технологии: Межвуз. сб. науч. трудов. Рязань: РГРТА, 2002. с. 19-22.

16. Бакулев А.В., Телков И.А. Конвертор исходных текстов программ с языка Паскаль в мобильный параллельный промежуточный код. М.: Роспатент, 2000 (свидетельство о регистрации программы для ЭВМ №2000610207 от 23.03.2000).

17. Бакулев А.В., Телков И.А. Оптимизация вычислений в SMP-системах// Математическое и программное обеспечение вычислительных систем. Межвуз. сб. научн. трудов. Рязань: РГРТА, 1999. С. 96-100.

18. Бакулев А.В., Телков И.А. Оптимизация параллельных вычислений// Материалы 8-го Международного научно-технического семинара "Проблемы передачи и обработки информации в сетях и системах телекоммуникаций". Рязань, РГРТА., 1999.

19. Бакулев A.B., Телков И.А. Параллельные процессы в Windows NT// Вычислительные машины, комплексы и сети. Межвуз. сб. научн. трудов. Рязань: РГРТА, 1999. С. 112115.

20. Бакулев A.B., Телков И.А. Программные средства организации мобильных параллельных вычислений// Новые информационные технологии. Межвуз. сб. научн. трудов. Рязань: РГРТА, 1997. С. 25-31.

21. Бакулев A.B., Телков И.А. Программные средства организации мобильных параллельных вычислений// Управление и информационные технологии на транспорте: Тез. докл. Международной научно-технической конференции "Транском-99". СПб: СПГУВК, 1999.

22. Бланшет Ж., Саммерфилд М. Qt 4: Программирование GUI на С++. 2-е дополненное издание. М.: "КУДИЦ-ПРЕСС", 2008. - С. 736.

23. Бутомо И.Д., Дробинцев Д.Ф., Питько А.Е. Методы распараллеливания алгоритмов и их реализация в вычислительных системах. Учебное пособие.-Ленинград:ЛПИ, 1980.-78с.

24. Васенин В.А., Водомеров А.Н., Инюхин A.B. Средства автоматизированного динамического распараллеливания программ на основе сочетания императивных и функциональных механизмов// Информационные Технологии. 2007. №5. 32с.

25. Вирт Н. Алгоритмы и структуры данных. СПб.: Невский Диалект. 2008. - 352.

26. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург,2004.

27. Воеводин В.В., Капитонова А.П. Методы описания и классификации вычислительных систем. Издательство МГУ, 1994.

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

29. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра. Языки. Про-граммирование. Киев: Наук. Думка, 1989.

30. Гмурман В.Е. Теория вероятностей и математическая статистика. М.: Высш. шк., 2000.- 479с.

31. Головкин Б.А. Вычислительные системы с большим числом процессоров. М.: Радио и связь, 1995.-320 с.

32. Головкин Б.А. Расчет характеристик и планирование параллельных вычислительных процессов.-М.: Радио и связь, 1983.-272с.

33. Гради Буч, Максимчук P.A., Энгл М.У., Янг Б.Дж., Коналлен Д., Хьюстон К.А. Объектно-ориентированный анализ и проектирование с примерами приложений. М.: Вильяме. 2010.-720.

34. Гречук Б.В., Фуругян М.Г. Составление оптимальных расписаний с прерываниями в многопроцессорных системах с неполным графом связей. Российская Академия Наук Вычислительный центр сообщения по прикладной математике, Москва, 2004. 66 с.

35. Гриффите Артур. GCC. Полное руководство. Platinum Edition. М.: ТИД "ДС", 2004.

36. Дал У., Дейкстра Э., Хоор К. Структурное программирование.- М.: Мир, 1975. 247с.

37. Дарахвелидзе П. Г., Марков Е.П. Delphi 2005 для Win32. Наиболее полное руководство.- СПб.: БХВ, 2005.

38. Дейкстра Э. Дисциплина программирования. М.: Мир, 1978.-280с.

39. Джехани Н. Язык Ада. М.: Мир, 1988.

40. Жабин В.И. Автоматическое динамическое распараллеливание процессов в вычислительных системах// Искусственный интеллект. 2005. - № 3. - С. 235-241.

41. Земсков Ю.В. Qt 4 на примерах. СПб.: "БХВ-Петербург", 2008. - С. 608.

42. Калинин А.Г., Мацкевич И.В. Универсальные языки программирования. Семантический подход. М.: Радио и связь, 1991. - 400с.

43. Кастер X. Основы Windows NT и NTFS. М.: Издательский отдел "Русская редакция" ТОО "Channel Trading Ltd", 1996. - 400с.

44. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. СПб.: БХВ-Петербург, 2003.

45. Кауфман В.Ш. Языки программирования. Концепции и принципы. М.: Радио и связь. 1993

46. Каширин И.Ю. Объектно-ориентированное проектирование программ в среде С++; Вопросы практики и теории/ Под.ред.Л.П.Коричнева.- М.: Госкомвуз России. НИЦПрИС, 1996.

47. Кнут Д. Искусство программирования. Т.1. Основные алгоритмы. М.: Вильяме, 2009.

48. Козуб В.М. Системы прерывания ЦВМ. М.: Сов. радио, 1976. -220с.

49. Конев И.М., Степанов Е.А. Автоматизация динамического распараллеливания программ: планирование, управление памятью, работа в гетерогенной среде// Информационные технологии. 2007. №10. С.71-73.

50. Коновалов Н.А., Крюков В.А., Сазанов ЮЛ. C-DVM язык разработки мобильных параллельных программ. Программированием 1, 1999.

51. Корнеев В.В. Параллельные вычислительные системы. М.: "Нолидж". 1999.

52. Корнеев В.Д. Параллельное программирование в MPI. М.: Институт компьютерных исследований.2003.

53. Корнелл Г., Хорстманн К.С. Java 2. Библиотека профессионала, том 1. Основы Core Java 2, Volume I - Fundamentals. - 8-е изд. - M.: Вильяме, 2008. - 816 с

54. Корячко В.П. Микропроцессоры и микроЭВМ в радиоэлектронных средствах. М.: Высшая школа. 1990. 407 с.

55. Корячко В.П. Теоретические основы САПР. М.: Высшая школа. 1987. 400 с.

56. Корячко В.П., Курчидис В.А. Об укладке графов программ // Изв.АН СССР. Техническая кибернетика. 1979, № 6, С. 129-136.

57. Корячко В.П., Скворцов С.В., Телков И.А. Архитектуры многопроцессорных систем и параллельные вычисления: учеб. пособие.- М.: Высш.шк., 1999.

58. Котов В.Е. Сети Петри. М.: Наука, 1984. 159с.

59. Котов В.Е. Формальные модели параллельных вычислений: Препринт/СО АН СССР, Вычислительный центр: №165. Новосибирск, 1979. 56с.

60. Котов В.Е., Сабелльфельд В.К. Теория схем программ. М.: Наука, 1991.

61. Коффман Э.Г. Теория расписаний и вычислительные машины. М.: Наука, 1984.

62. Липатов В.В., Филипов Е.Н. Мобильность программ и данных в открытых информационных системах. М.: Научная книга, 1997. -386с.

63. Львовский Е.Н. Статистические методы построения эмпирических формул. М.: Высш. шк., 1988.-239с.

64. Майника Э. Алгоритмы оптимизации на сетях и графах.-М.: Мир, 1981.-323с.

65. Макс Шлее. Qt 4.5. Профессиональное программирование на С++. СПб.: "БХВ-Петербург", 2010.-С. 896.

66. Марков А.А. Избранные труды. Том 2. Теория алгорифмов и конструктивная математика, математическая логика, информатика и смежные вопросы. М: МЦНМО, 2007.

67. Мезенцев Ю. А. Алгоритмы синтеза расписаний многостадийных обслуживающих систем в календарнрм планировании// Омский научный вестник. 2006. №3(36). С.141-145.

68. Модели, методы, инструментальные средства и научно-методическое обеспечение процесса проектирования параллельных систем с использованием CASE-технологии/Ютчет о научно-исследовательской работе по теме 10-01. Рязань, 2001.

69. Мотвани Р., Ульман Дж, Хопкрофт Дж. Введение в теорию автоматов, языков и вычислений. М.: Вильяме, 2008. - 528с.

70. Немнюгин С.А., Стесик O.JI. Параллельное программирование для многопроцессорных вычислительных систем. СПб.: БХВ-Петербург, 2002. - 400с.

71. Ноден П., Китте К. Алгебраическая алгоритмика. М.: Мир, 1999. - 720с.

72. П.Браун. Макропроцессоры и мобильность программного обеспечения. М.: Мир, 1977.

73. Параллельная обработка информации: В 5 томах. Том 1. Распараллеливание алгоритмов обработки информации/ Бабичев А.В., Вальковский В.А., Грицык В.В. и др.; Под ред. А.Н.Свенсона. Киев: Наук, думка, 1985. 280с.

74. Поспелов Д.А. Введение в теорию вычислительных систем. М.: Сов радио, 1972. -280с.

75. Прангишвили И.В., Виленкин С.Я., Медведев И.Л. Параллельные вычислительные системы с общим управлением.-М.: Энергоатомиздат, 1983.

76. Пратт Т., Зелковиц М. Языки программирования: разработка и реализация. СПб.: Питер, 2002. - 688с.

77. Рихтер Д. Windows для профессионалов. Создание эффективных \Уш32-приложений с учетом специфики 64-разрядной версии Windows. СПб.: Питер, Русская Редакция, 2001. -752с

78. Рихтер Дж. CLR via С#. Программирование на платформе .NET Framework 2.0 на языке С# = CLR via С#. СПб.: Питер, 2008

79. Сандерсон С. ASP.NET MVC Framework с примерами на С# для профессионалов. -СПб.: Вильяме, 2010.

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

81. Таненбаум Э., Вудхалл А. Операционные системы. Разработка и реализация. 3-е изд. -СПб.: Питер, 2007.

82. Телков И.А. Математическая модель алгоритмов и мобильного программного обеспечения// Вестник РГРТА. 1997. №3. С.51-59.

83. Телков И.А. Математическая модель многоядерных процессоров в пространстве состояний// Информационные технологии в образовании: Межвузовский сборник научных трудов. Рязань: РГРТУ, 2010. С.135-140.

84. Телков И.А. Метод синтеза архитектур неоднородных вычислительных систем// Проблемы обработки информации: Межвуз. сб. Рязань, 1995.

85. Телков И.А. Тензорная модель программных средств параллельных вычислительных систем// Вестник РГРТА. 1996. №1. С.32-39.

86. Теория алгоритмов и формализация исследования программ: Учеб. пособие/ И.Ю. Ка-ширин.; Рязан.гос.радиотехн.акад. Рязань, 1996.

87. Трауб Дж., Васильковский Г., Вожьняковский X. Информация, неопределенность, сложность: Пер. с англ. -М.: Мир, 1988.-184с.

88. Триливен Ф.К. Модели параллельных вычислений// Системы параллельной обработки/ Под ред. Д. Ивенса. М.: Мир, 1985. С. 277-284.

89. Чеботарев А. Библиотека Qt 4. Создание прикладных приложений в среде Linux. М.: "Диалектика", 2006. - С. 256.

90. Элементы параллельного программирования/ В.А.Вальковский, В.Е.Котов, А.Г.Марчук, Н.Н.Миренков. М.:Радио и связь, 1983.-240.

91. Эндрюс Г.Р. Основы многопоточного, параллельного и распределенного программирования. М.: Издательский дом "Вильяме", 2003. - 512с.

92. Янов Ю.И. О логических схемах алгоритмов. Сб.: Проблемы ки-бернетики, вып. I, М. Физматгиз, 1958, с 75-127.

93. Ammann U. On Code Generation in a Pascal Compiler, Software-Practice and Experience, Vol. 7, No. 3, 1977, pp. 391-423

94. Appel A.W. Semantics-Directed Code Generation, 1984.

95. Basu A. Parallel Processing Systems: a Nomenclature based on their Characteristics // Proc. IEE(UK).N 134. 1987. P.143-147.

96. Bender M.A., Rabin M.O. Scheduling Cilk Multithreaded Parallel Programs on Processors of Different Speeds. Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, July, 2000.

97. Blumofe R. D. Executing multithreaded programs efficiently: Ph.D. thesis / Massachusetts Institute of Technology. Cambridge, MA, 1995.

98. Brandis M.M. Optimizing Compilers for Structured Programming Languages. A dissertation for the degree of Doctor of Technical Sciences. 1995

99. Brode В., Rodden C. VAST/Parallel: Automatic Parallelization for SMP systems. Pacific-Sierra Research Corporation. 2005.

100. Chapman В., Jost G., Ruud van der Pas. Using OpenMP: Portable Shared Memory Parallel Programming. The MIT Press. 2007. 353p.

101. Cytron R.K., Ferrante J. Efficiently computing f-nodes on the fly// ACM Trans, on Programming Languages and Systems. 1995. -Vol.17, N3. - P.487-505.

102. Cytron R.K., Ferrante J., Rosen B.K., Wegman M.N., Zadeck F.K. Efficiently computing static single assignment form and the control dependence graph// ACM Trans, on Programming Languages and Systems. 1991. -Vol.13, N4. - P.451-490.

103. Dasgupta S. A Hierarchical Taxonomic System for Computer// 1990. V.23. N 3. P.64-74.

104. Documentation for the LLVM System at SVN head. 2010 (http://llvm.org/docs/).

105. Franz M. Code-Generation On-the-Fly: A Key for Portable Software. PhD thesis (ETH №10497). Zurich, ETH, 1994. 97p.

106. Grunwald D., Srinivasan H. Data flow equations for explicitly parallel programs. In РРОРРД993.

107. Guy Blelloch, Phil Gibbons, Yossi Matias. Provably efficient scheduling for languages with fine-grained parallelism. Journal of the ACM, 46(2), P.281-321, 1999. i

108. Hempel R. The Argonne/GMD Macros in Fortran for Portable Parallel Programming using the Message Passing Programming Model, Feb. 1991.

109. Hoare C.A.R. "An axiomatic basis of computer programming", Comm. ACM 12,10, 1969, pp.576-580.i 123. ISO 10206:1991. Информационные технологии. Языки программирования. Язык программирования Расширенный Паскаль.

110. ISO 7185:1990. Информационные технологии. Языки программирования. Язык программирования Паскаль.

111. ISO 9899:1999. Информационные технологии. Языки программирования. Язык программирования Си.

112. ISO/IEC 10967-1:1994. Information technology. Language independent arithmetic. Part 1: Integer and floating point arithmetic.

113. ISO/IEC 14882:2003. Информационные технологии. Языки программирования. Язык программирования Си++.

114. ISO/IEC 1539-1:2010. Информационные технологии. Языки программирования. Язык программирования Фортран.

115. ISO/IEC 1989:2002. Информационные технологии. Языки программирования. Язык программирования Кобол.

116. ISO/IEC 23270:2006. Информационные технологии. Языки программирования. Язык программирования С#.

117. ISO/IEC 23271:2006. Информационные технологии. Common Language Infrastructure (CLI).

118. Iffat Hoque Kazi. Dynamically Adaptive Parallelization Model Based on Speculative Multithreading. PhD thesis. Minnesota, 2000. 188p.

119. Intel 64 and IA-32 Architectures Software Developer's Manual. Volume 1: Basic Architecture. Intel Corporation. 2010. ("http://www.intel.com/products/processor/manuals/index.htm)

120. Intel 64 and IA-32 Architectures Software Developer's Manual. Volume 3A: System Programming Guide, Part 1. Intel Corporation. 2010. (http://www.intel.com/ products/ processor/ manuals/index.htm)

121. Jean-Louis Pazat. Tools for high performance fortran: A survey. 2006.

122. Keryell R. PPS: a Workbench for Building Interprocedural Parallelizers, Comilers and Optimizers. 1996.

123. Kofftnan Elliot B. Turbo Pascal: problem solving and program Design. -2nd ed, 1989.

124. Krishnamurthy E.V. Parallel Processing Principles and Practice. Addison-Wesley Pub. Company. 1989. P.208-246.

125. Lattner C. Introduction to the LLVM Compiler Infrastructure// Itanium Conference and Expo, San Jose, California, April 2006.

126. Lengauer T.,Tarjan R.E. A fast algorithm for finding dominators in a flow graohs // ACM Trans. Prog. Lang. Syst. 1979.- Vol.1, N 1. - P. 121-141.

127. MPI:A Message-Passing Interface Standard. Version 2.2. Message Passing Interface Forum. 2009 (http://www.mpi-forum.org/docs/docs.html).

128. Nori K.V., Ammann U., Jensen, Nageli H. The Pascal P Compiler Implementation Notes. Zurich: Eidgen. Tech. Hochschule. 1975.

129. Oancea C.E., Mycroft A., Harris T. A Lightweight In-Place Implementation for Software Thread-Level Speculation// Journal of the ACM, 08, 2009

130. OpenMP Application Program Interface. Version 3.0. 2008 (http://openinp.orii/ wp/ openmp-specifications/).

131. Patrick W. Sathyanathan. Interprocedural Dataflow Analysis Alias Analysis. PhD thesis. -2001. 186p.

132. Richards M„ Whitby-Strevens C. Bcpl: the Language and Its Compiler. Cambridge University Press. 1980

133. Sabine Glesner. An ASM Semantics for SSA Intermediate Representations// Proceedings of the 11th International Workshop on Abstract State Machines. 2004

134. Sanjiv K.Gupta, Naveen Sharma. Alias Analysis for Intermediate Code// Proceedings of the GCC Developers' Summit. 2003

135. SkillicornD. A Taxonomy for Computer Architectures//Computer. 1988. V.21. N 11. P.46-57.

136. Skillicorn D.B. A New Framework for Software Development. External Technical Report. Department of Computing and Information Science, Queen's University, Canada, 1999

137. Software Optimization Guide for AMD Family lOh Processors. Advanced Micro Devices, Inc. Rev.3.11. 2009. (http://support.amd.com/us/ProcessorTcchDocs/40546-PUB-Optguide3-Il5-21-O9.pdf)

138. Steffan J.G., Mowry T.C. The Potential for Using Thread-Level Data Speculation to Facilitate Automatic Parallelization. Carnegie Mellon University, HPCA-4, February 1-4, 1998.

139. Sutter H. The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software. Dr. Dobb's Journal, March 2005.

140. Tian C., Feng M., Nagarajan V., Gupta R. Speculative Parallelization of Sequential Loops on Multicores// Int J Parallel Prog, 2009.