МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М.В.Ломоносова
Факультет Вычислительной математики и кибернетики
ПРОГРАММА
курса «Параллельная обработка данных»
(III поток, 9 семестр)

---

---

Лектор:
кандидат физ.-мат. наук В. А. Фисун
15.5.2004

Основы информатики.

     1. Информация. Меры Хартли, Шеннона.
     2. Знания и ЭВМ.
Литература:
     Корогодин В.И., Корогодина В.Л. Информация как основа жизни. -Дубна: Изд.центр Феникс, 2000.-208с.
     Цимбал Л.А. Синергетика информационных процессов. Закон информативности и его следствия. М.:Наука,1995.-119с.

Эволюционная классификация вычислительных систем на примере развития отечественной техники.

     1. Критерий, положенный в основу эволюционной классификации ЭВМ.
     2. Основоположники отечественной вычислительной техники.
Литература:
     Б.Н. Малиновский. История вычислительной техники в лицах. - К.,фирма "КИТ", ПТОО "А.С.К.", 1995. -384 с.
     А.Д. Смирнов. Архитектура вычислительных систем.-М. Наука.1990.320 с.

Вычислители фон-Нейманновской архитектуры. Конвейерная обработка данных и команд. Архитектура памяти.

     1. Принципы фон-Нейманновской архитектуры ЭВМ.
     2. Конвейерная обработка данных.
     3. Зацепление конвейеров.
     4. Векторно-конвейерные вычислители.
     5. CISC и RISC архитектуры ЭВМ.
     6. Внеочередное и спекулятивное выполнения команд.
     7. Механизмы предсказания переходов.
     8. Управление виртуальной памятью.
     9. Ассоциативная память.
     10. Назначение и структура кэш-памяти.
     11. Полностью ассоциативная кэш-память.
     12. Кэш-память с прямым отображением.
     13. Частично ассоциативная кэш-память.
     14. Дисциплина обновления кэш-памяти.
     15. Стратегии записи в кэш-память.
     16. Расслоение памяти.
     17. Принципы VLIW архитектуры.
     18. Суперскалярные и мультитредовые архитектуры микропроцессоров.
     19. Стандарт IA-64.
     20. Оптимизация программ под архитектуру микропроцессора.
Литература:
     Столлингс В. Структурная организация и архитектура компьютерных систем. Пер. С анг.-М.:Изд. дом Вильямс,2002.-896с.
     Корнеев В.В., Киселев А.В.. Современные микропроцессоры. - М. «Нолидж», 1998.-240 с.
     Касперски К. Техника оптимизации программ. Эффективное использование памяти.-СПб-Петербург,2003.-464с.

Архитектура параллельных вычислительных систем

     1. Гетерогенные распределенные вычислительные системы.
     2. Метакомпъютинг.
     3. Кластерные архитектуры.
     4. Симметричные мультипроцессорные системы.
     5. Матричные мультипроцессорные системы.
     7. Классификации вычислителей по Флинну.
     8. Масштабируемость мультипроцессорных вычислителей.
     9. Управление памятью в мультипроцессорных системах.
     10. Когерентность данных.
Литература:
     Корнеев В.В. Параллельные вычислительные системы. - М. «Нолидж», 1999.-320 с.

Топологии мультипроцессорных коммутационных сетей.

     1. Типы внутренних связей.
     2. Статические и динамические коммуникаторы.
     3. Параметры статических коммутационных сетей.
     4. Топологии линейки, решетки, пирамиды.
     5. Топология гиперкуба.
     6. Согласование сеточных топологий со структурой гиперкуба.
     7. Перекрестный коммутатор.
     8. Многокаскадные коммутационные сети.
Литература:
     Головкин Б.А.. Вычислительные системы с большим числом процессоров. - М.: Радио и связь, 1995.-320с.
     Кун С. Матричные процессоры на СБИС: -М.: Мир, 1991. - 672с.

Производительность вычислительных систем.

     1. Пиковая производительность.
     2. Методы оценки производительности.
     3. Закон Амдала.
Литература:
     Барановская Т. П. и др. Архитектура компьютерных систем и сетей.-М: Финансы и статистика,2003.-256с.

Нетрадиционные архитектуры: потоковые и нейронные вычислители.

     1. Принципы потоковой обработки информации.
     2. Схемы потоковых вычислителей.
     3. Нейронные сети.
     4. Области применения нейронных сетей.
Литература:
     В.А. Вальковский, И.Б. Вирбицкайте. Сб.Потоковые вычислительные системы. Системная информатика. Вып. 2. - Новосибирск:ВО "Наука", 1993. -247с.
     Ф. Уоссерман. Нейрокомпьютерная техника. М.: Мир, 1992.

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

     1.Модели программирования для систем с разделяемой, распределенной памятью.
     2. Разделение последовательных программ на параллельные нити.
     3. Ограничения на распараллеливание циклов.
     4. Синхронизация параллельных процессов. Барьеры.
     5. Критические секции. Двоичные и общие семафоры.
     6. Упорядоченные секции. Распараллелить цикл, используя упорядоченные секции и семафоры:
        DO I=2,N
          A(I) = 2*A(I) + C(I)
          B(I) = C(I)*sin(X(I))
          Y(I) = Y(I-1) + X(I)
          D(I) = P(I)*B(I)/A(I)
        ENDDO

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

Системы передачи сообщений. Фортран-GNS.

     1. Статический и динамический способы образования параллельных процессов.
     2. Требования с системам программирования методом передачи сообщений.
     3. Система программирования MPI.
     4. Средства описания и создания процессов в языке Фортран-GNS.
     5. Средства передачи и приема сообщений в языке Фортран-GNS.
     6. Протоколы передачи и приема сообщений в языке Фортран-GNS.
     7. Идентификация абонентов при передачи сообщений в языке Фортран-GNS.
     Допускаются ответы на пп 4-7 в терминах PVM,MPI.
Литература:
     Немнюгин С.А., Стесик О.Л. Параллельное программирование для многопроцессорных вычислительных систем.-СПб.: Петербург,2002.-400с.
     Горелик А.М., Задыхайло И.Б. Расширение Фортрана для многопроцессорных систем с распределенной памятью. -М.: Препринт ИПМ РАН 1992. N32

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

     1. Автоматическое распараллеливание последовательных программ.
     2. Семантика циклов, выполняемых параллельно на ОКМД системах.
     3. Алгоритмы преобразования программ методом координат.
     4. Схема преобразования программ методом гиперплоскостей.
     5. Метод параллелепипедов.
     6. Оценить возможность параллельного выполнения цикла:
     DO i = 2,N
      A(i) = (B(i) + C(i))/A(i+CONST)
     ENDDO

Литература:
     Сб. «Языки и параллельные ЭВМ». Сер. «Алгоритмы и алгоритмические языки», М.: Наука, 1990.
     Э. А. Трахтенгерц. Введение в теорию анализа и распараллеливания программ ЭВМ в процессе трансляции. -М.:Наука,1981.-254с.

Языки параллельного программирования

     1. Стандарты OpenMP.
     2. Язык Фортран-DVM.
     3. Язык Sisal.
     4. Система программирования Норма.

Литература:
     Бен-Ари М. Языки программирования, Пер. С анг. -М:Мир,2000.-366с.
     Норма. Система построения параллельных программ. - www.applmat.ru/pvages/norma/
     Fortran-DVM. Версия 2.0. Описание языка - 2001. - www.keldysh.ru/dvm/dvmhtm1107/rus/usr/fdvm/fdvmLDr.html

Особенности выполнения арифметических выражения на ЭВМ. Распараллеливание вычислительных алгоритмов. Метод распараллеливания алгоритма общей рекурсии 1-го порядка.

     1. Распараллеливание алгоритмов сложения методом редукции.
     2. Метод распараллеливания алгоритма общей рекурсии 1-го порядка.
     3. Представление машинных чисел.
     4. Арифметика машинных чисел.
     5. Погрешности при вычислениях чисел на параллельных системах. Оценить полную ошибку суммирования положительных чисел.
     6. Точность плавающей арифметики. Машинный эпсилон.
     7. Перечислить алгоритмы оптимизации объектных программ, которые могут повлиять на точность вычислений.
Литература:
     Р.Хокни, К.Джасхоуп. Параллельные ЭВМ. М.: Радио и связь. 1986.
     Г.К. Боровин и др. Ошибки-ловушки при программировании на Фортране.-М.Наука. 1987. 144 с.

Литература

1. В.В. Корнеев. Параллельные вычилительные системы.-М. "Нолидж", 1999.-320с.
2. Б.А.Головкин. Вычислительные системы с большим числом процессоров.-М.: Радио и связь, 1995.-320с.
3. М. Амамия, Ю.Танака. Архитектура ЭВМ и искусственный интеллект: Пер. с японск. - Мир, 1993. 400с.
4. Языки и параллельные ЭВМ. Сб. "Алгоритмы и алгоритмические языки", М.: Наука, 1990.
5. Р.Хокни, К.Джасхоуп. Параллельные ЭВМ. М.: Радио и связь. 1986.
6. http://parallel.ru
7. http://www.osp.ru

Приммечание:

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

Дополнительная информация

     Текст программы курса «Параллельная обработка данных» (Zip-архив файла WinWord97: http)
     В.А.Фисун. Язык Фортран GNS для систем с распределенной памятью. Рекомендации по использованию языка (Zip-архив файла в DOS-кодировке: http).
     Т.П. Баранова, И.Б. Задыхайло, В.А. Фисун. Платформа CONVEX SPP1000. - М.: Препринт ИПМ РАН (Zip-архив файла в DOS-кодировке: http).

---

---