Параллельное программирование

Министерство образования Российской Федерации Санкт-Петербургский государственный электротехнический университет “ЛЭТИ”

РАБОЧАЯ ПРОГРАММА дисциплины “Параллельное программирование” Для подготовки дипломированных специалистов по направлению 654600 – “Информатика и вычислительная техника” по специальности 220400 -“Программное обеспечение вычислительной техники и автоматизированных систем”.

Санкт-Петербург 2000

2 Санкт-Петербургский государственный электротехнический университет “ЛЭТИ”

“УТВЕРЖДАЮ” Проректор по учебной работе проф. ___________ Ушаков В.Н. “_____”_______________2000 г. РАБОЧАЯ ПРОГРАММА дисциплины “Параллельное программирование” Для

подготовки дипломированных специалистов по направлению: 1. 654600–“Информатика и вычислительная техника”: а) специальности 220400 -“Программное обеспечение вычислительной техники и автоматизированных систем”.

Факультет компьютерных технологий и информатики Кафедра Математического обеспечения и применения ЭВМ Курс – V Семестр(ы) – 10 Лекции Практические занятия Лабораторные занятия Курсовое проектирование Аудиторные занятия Самостоятельные занятия Всего часов

30 ч. 0ч. 15ч. 0ч. 45 ч. 53 ч. 98 ч.

2000

Экзамен

10 семестр

Зачет

10 семестр

3 Рабочая программа обсуждена на заседании кафедры Математического обеспечения и применения ЭВМ “ 15 ” ноября 2000 г., протокол № 4. Рабочая программа составлена в соответствии с государственным образовательным стандартом по направлению 654600, специальности 220400 -“Программное обеспечение вычислительной техники и автоматизированных систем”. Рабочая программа согласована с рабочими программами изученных ранее дисциплин: 1) Дискретная математика; 2) Математическая логика; 3) Формальные языки и грамматики; 4)Теория вычислительных процессов и структур.

Рабочая программа одобрена методической комиссией факультета компьютерных технологий и информатики “____”_____________2000г.

4 Цели и задачи дисциплины 1. Изучение основных положений современной концепции процесса, особенностей формальных моделей параллельного программирования, принципов организации взаимодействия асинхронных процессов, методов распараллеливания алгоритмов. 2. Формирование навыков работы с параллельными вычислителями, разработки и отладки параллельных программ в среде параллельных операционных систем, исследования особенностей структуры параллельных вычислителей и учета этих особенностей при проведении вычислений. Требования к уровню освоения дисциплины В результате изучения дисциплины студенты должны: Знать основные положения современной концепции процесса, метамодели асинхронных и вычислительных процессов; формальные модели параллельного программирования, принципы организации взаимодействия асинхронных процессов, методы реализации мультипрограммных режимов обработки информации в вычислительных комплексах различных структур и параллельной обработки в параллельных вычислителях; основные подходы и методы решения задачи десеквенции алгоритмов. Уметь (владеть или иметь навыки) разрабатывать требования и спецификации программного обеспечения для реализации на основе принципов параллельной обработки информации; спецификации протоколов взаимодействия асинхронных процессов; параллельные программы в среде операционной системы PARIX на одном процессоре и на сетке процессоров. Иметь представление (понимать) об основных проблемах теории и практики параллельного программирования; особенностях современных языков параллельного программирования; о критериях оптимизации выбора средств вычислительной техники, программного обеспечения и методов их использования для эффективной реализации параллельной обработки информации; о перспективах развития параллельных вычислителей и средств параллельного программирования. Содержание рабочей программы Тема 1. Краткая характеристика курса в целом и основных разделов. Связь с другими дисциплинами учебного плана. Концепция процесса и принципы параллельной обработки информации. Основные проблемы параллельного программирования. Тема 2. Формальные модели параллельного программирования. Параллельные схемы программ. Информационный базис и схема управления. Асинхронные вычислительные процессы над информационным базисом. Неуправляемые вычислительные процессы. Тема 3. Схема управления параллельной схемы программы. Управляющий автомат и особенности автоматных функций. Эквивалентность вычислительных процессов по произвольному отношению. Детерминизм и отношение “большей параллельности” схем управления.

5 Тема 4. Концепции управления. Параллельные операторные схемы Келлера. Область определения и область значений. Основные аксиомы. Определение реализации операторных схем Келлера. Понятие свободной реализации. Тема 5. Атрибуты вычислительных процессов. Виды эквивалентности вычислительных процессов по отношению равенства атрибутов. Отношение сводимости различных видов эквивалентности вычислительных процессов. Максимальная параллельность на множестве схем управления. Тема 6. Десеквенция алгоритмов как задача преобразования программ одного класса в параллельные программы другого класса. Вычислительный процесс и операторные схемы Келлера. Условия существования свободной реализации. Тема 7. Реализация параллельных операторных схем с очередями. Построение свободной реализции. Процедура расщепления диаграммы переходов согласованного автомата. Переход к автомату, реализующему максимально параллельную схему управления. Содержательная интерпретация реализации операторной схемы с очередями. Тема 8. Принципы организации взаимодействия асинхронных процессов. Механизмы взаимодействия асинхронных процессов. Понятие синхропримитива. Использование сетей Петри как средства формальной спецификации протоколов взаимодействия асинхронных процессов. Отображение спецификации в реализацию системного и встроенного программного обеспечения. Аппаратные и программные средства организации взаимодействия асинхронных процессов, их взаимосвязи и разделения ресурсов. Тема 9. Вычислительные системы с массовым параллелизмом. Определение и примеры. Особнности применения: моделирующие вычислительные системы и системы реального времени. Примеры. Характерные особенности таких систем. Тема 10. Архитектура многопроцессорных вычислительных систем. Классификация ВС по Флину. Реконфигурируемые системы MIMD архитектуры. Статическая и динамическая реконфигурация. Оценка производительности массивно параллельных ВС. Причины снижения производительности. Тема 11. Проектирование массивно параллельных ВС: RISC процессоры и транспьютеры. Традиционная классическая и нетрадиционная архитектура микропроцессорных элементов. Архитектура и специфические особенности внутренней организации транспьютерных элементов. Адресация сообщений, каналы, организация линков. Тема 12. Введение в среду ОС UNIX. Основы командного интерпретатора оболочки UNIX. Средства создания и управления файлами. Удаленный доступ в системе UNIX. Средства создания и отладки С-программ. PARIX - расширение ОС UNIX для работы с параельными вычислителями на основе различных платформ. Компиляция и запуск программ в среде PARIX. Тема 13. ОС PARIX - среда разработки параллельных программ. PARIX-компоненты. Программная модель PARIX. Статические и динамические параметры PARIX. Системная библиоека PARIX. Цикл разработки программ в среде PARIX.

6 Тема 14. Мультикластер фирмы Parsytec MC-3. Особенности внутренней организации параллельного вычислителя. Позиционирование процессорных элементов. Средства подержки синхронных и асинхронных взаимодействий процессорных элементов в среде PARIX. Принципы работы аппаратного планировщика. Состояния процессов. Средства создания виртуальной топологии. Библиотека виртуальных топологий. Виртуальные линки. Тема 15. Выполнение параллельных программ на одном процессорном элементе. Организация взаимодействия процессов на одном процессорном элементе. Библиотека системные функций. Функции STARTTHREAD, MAKELINK, LOGERROR, SENDLINK. Тема 16. Организация параллельных вычислений на сетке процессорных элементов. Масштабируемость программ в среде PARIX. Реализация кольцевых топологий. Тема 17. Проблема конфигурации параллельных программ. Методы конфигурации на основе максимальной или суммарной функции. Структурный подход. Современные системы с массовым параллелизмом. Тема 18. Заключение. Перспективы развития параллельных вычислителей и средств параллельного программирования.

Перечень лабораторных работ № 1 2 3 4 5

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

Номер темы 11,12,13 8,9,15 14,16,17 14,16,17 2,3,6

7 Распределение учебных часов по темам и видам занятий №№ темы

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

Название разделов и тем

Введение Формальные модели параллельного программирования Схема управления параллельных схем программ Операторные схемы Келлера Эквивалентность вычислительных процессов Проблема распараллеливания алгоритмов Процедура распаралеливания с очередями Организация взаимодействия процессов ВС с массовым параллелизмом Архитектура многопроцессорных ВС Транспьютерные параллельные ВС Введение в UNIX ОС PARIX Параллельный вычислитель MC-3 Параллельные вычисления на одном процессоре Параллельные вычисления на сетке процессоров Конфигурация параллельных программ Заключение

ИТОГО:

Объем учебных часов Лек ции

Лабор. занятия

Практ. занятия

Аудит. занятия

Самост. работа

Всего

Семе стр

1 3

1

-

1 4

1 5

2 9

10 10

2

1

-

3

4

7

10

2 3

-

-

2 3

3 4

5 7

10 10

2

1

-

3

3

6

10

1

-

-

1

1

2

10

3

1

-

4

4

8

10

1

1

-

2

2

4

10

1

-

-

1

2

3

10

1

1

-

2

2

4

10

1 3 1

1 1 2

-

2 4 3

2 5 3

4 9 6

10 10 10

1

1

-

2

2

4

10

2

2

-

4

5

9

10

1

2

-

3

4

7

10

1

15

-

1 45

1 53

2 98

10

30

8 ЛИТЕРАТУРА Основная №

1 2 3

4 5 6

Название, библиографическое описание

Элементы параллельного программирования / В.Е.Котов, А.В.Вальковский А.Г.Марчук, Н.Н.Миренков. -М.: Радио и связь. 1983. -296с Вальковский В.А. Распараллеливание алгоритмов и программ. Структурный подход. -М.: Радио и связь, 1989. -176с. Karp R., Miller R. Parallel programs shemats. //JCSS, v.3, No.4, 1969. -p.p.147-195. (Русск.пер. в кн.: Кибернетический сборник:Новая серия, вып.13. М.: Мир,1976. -с.с.5-51 Программирование на параллельных вычислительных системах /Пер. с англ. -М.:Мир, 1991. -376с. PARIX Release 2.1, Parsytec Computer GmbH, 1993. 500c. Foster T. Ian. Designing and building parallel programs: Conception and tools for parallel software engineering. Addison-Wesley Publlishing Company , 1995. -381 p.

Л

Лр

*

*

*

*

*

*

*

*

*

*

*

*

Пз (С)

Кп (р)

Ин д Зад.

К-во экз. в библ. (на каф.)

Дополнительная №

Название, библиографическое описание

1

Семик В.П., Агаранян А.Л., Каменкова М.С. Технология программирования параллельных вычислительных систем на базе транспьютерных сетей /В кн.: Итоги науки и техники. Техническая кибернетика. т.30. -М.: ВИНИТИ, 1990. С.с.3-50. Culler David E., Singh Jaswinder Pal. Parallel computer architecture: A hardware / software approach. -Morgan Kaufmann Publishers, Inc., San Francsco, California, 1999. -1025 p.

2

К-во экз. в библ. (на каф.)

9 Авторы: с к.т.н., доцент к.т.н., доцент Рецензент д.т.н., профессор

Красюк В.И. Татаринов Ю.С. Водяхо А.И.

Зав. кафедрой МД ЭВМ д.т.н., профессор

Лисс А.Р.

Декан факультета КТИ д.т.н., профессор

Герасимов И.В.

Программа согласована: Зав. кафедрой МО ЭВМ д.т.н., профессор

Лисс А.Р.

Декан факультета КТИ д.т.н., профессор

Герасимов И.В.

Зав. отделом учебной литературы

Смирнова О.Н.

Председатель методической комиссии факультета КТИ к.т.н., доцент Руководитель методического отдела к.т.н., доцент

Чугунов Л.А. Марасина Л.А.