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

• Бакулев, Александр Валериевич
• кандидат технических наук
• 2011

Оглавление диссертации кандидат технических наук Бакулев, Александр Валериевич

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

ВВЕДЕНИЕ

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

Список литературы диссертационного исследования кандидат технических наук Бакулев, Александр Валериевич, 2011 год

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.