В.А. Фисун 14.12.2000 МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М.В.Ломоносова Факультет Вычислительной математики и кибернетики ПРОГРАММА курса Параллельная обработка данных (1-я ступень) с уточнениями, дополнительной литературой и экзаменационными вопросами Эволюционная классификация вычислительных систем на примере развития отечественной техники. 1. Критерий, положенный в основу эволюционной классификации ЭВМ. 2. Основоположники отечественной вычислительной техники. Б.Н. Малиновский. История вычислительной техники в лицах. - К.,фирма <КИТ>, ПТОО <А.С.К.>, 1995. -384 с. А.Д. Смирнов. Архитектура вычислительных систем.-М. Наука.1990.320 с. Вычислители фон-Нейманновской архитектуры. Суперскалярные, векторные и VLIW системы команд микропроцессоров. Конвейерная обработка данных и команд. Зацепление конвейеров. Предсказание переходов. Архитектура па- мяти. Кэш-память. Особенности программирования для вычислителей фон-Нейманновской архитектуры. 1. Принципы фон-Нейманновской архитектуры ЭВМ. 2. CISC и RISC архитектуры ЭВМ. 3. Принципы VLIW архитектуры. 4. Конвейеризация вычислений. 5. Векторные вычислители. 6. Внеочередное и спекулятивное выполнения команд. 7. Механизмы предсказания переходов. 8. Виртуальная память. 9. Алгоритмы подкачки страниц. 10. Иерархия оперативной памяти. 11. Ассоциативная память. 12. Расслоение памяти. 13. Полностью ассоциативная кэш-память. 14. Кэш-память с прямым отображением. 15. Частично ассоциативная кэш-память. 16. Стратегии записи в кэш-память. 17. Определить среднее время выборки для кэшей L1 и L2, если: веро- ятность попадания в прямоадресуемый кэш L1 составляет 80%, а время вы- борки из него 20 нс; в частично-ассоциативный кэш L2 вероятность попа- даний - 87%, время выборки 24 нс. Цена кэш-промаха у L1 и L2 - 200 нс. 18. Привести пример программы, вызывающей перезагрузку кэша с прямым распределением. 19. Привести пример программы, для которой расслоение памяти не эф- фективно. 20. Алгоритмы оптимизации объектных программ, которые могут повлиять на точность вычислений. В.В. Корнеев, А.В. Киселев. Современные микропроцессоры.-М. <Нолидж>, 1998.-240 с. Тенденции развития вычислительных архитектур. Классификация параллель- ных вычислительных систем по Флинну. 1. Принципы классификации вычислительных систем по Флинну. 2. Примеры классификации вычислителей по Флинну. 3. Недостатки способа классификации вычислительных систем по Флинну. МКМД системы: сильно и слабо связанные распределенные системы. Масштабируемость мультипроцессорных вычислителей. 1. Архитектурные особенности МКМД мультипроцессоров. 2. Особенности масштабирования SMP и MPP мультипроцессоров. Симметричные мультипроцессорные системы. Архитектура ccNUMA (SPP-XXXX). 1. Описать схему симметричного мультипроцессора. 2. Особенности архитектура ccNUMA. - 2 - Топологии коммутаторов MPP систем: полный коммутатор, решетка, пирами- да, гиперкуб. 1. Статические и динамические сети МРР систем. 2. Параметры статических коммутационных сетей. 3. Свойства полного коммутатора. 4. Топология гиперкуба. 5. Согласование сеточных алгоритмов со структурой типа гиперкуб. Кун С. Матричные процессоры на СБИС: -М.: Мир, 1991. - 672с. ОКМД системы: матричные системы, конвейерные вычислительные системы. 1. Матричные процессоры (AP120-B). 2. Современные ОКМД системы. 3. Использование элементов Крей архитектуры в процессорах ЭВМ. Производительность вычислительных систем. Пиковая производительность. Методы оценки производительности, Бенч-марки. 1. Единицы измерения пиковой производительности. 2. Реальная производительность. 3. Закон Амдала. Нетрадиционные архитектуры: потоковые и нейронные вычислители. 1. Принципы потоковой обработки информации. 2. Схема потокового вычислителя. 3. Нейронные сети. 4. Области применения нейронных сетей. В.А. Вальковский, И.Б. Вирбицкайте. Сб.Потоковые вычислительные системы. Системная информатика. Вып. 2. - Новосибирск:ВО "Наука", 1993. -247с. Ф.Уоссерман. Нейрокомпьютерная техника. М.: Мир, 1992. Модели программирования для систем с разделяемой, распределенной па- мятью. Синхронизация параллельных процессов. Семафоры. Элементы параллель- ного программирования в Фортране-90. 1. Критические секции. Двоичные и общие семафоры. 2. Разделение программ на нити при автоматическом распараллеливании. Ограничения на распараллеливание циклов. 3. Упорядоченные секции. Распараллелить цикл, используя упорядочен- ные секции и семафоры: 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 4. Средства параллельного программирования в Фортране-90. Протоколы обмена в системах передачи сообщений. Фортран-GNS для МВК-100. Системы PVM, MPI. 1. Статический и динамический способы образования параллельных процессов, 2. Требования с системам программирования методом передачи сообщений. 3. Назначение систем PVM, MPI. 4. Средства описания и создания процессов в языке Фортран-GNS. 5. Средства передачи и приема сообщений в языке Фортран-GNS. 6. Протоколы передачи и приема сообщений в языке Фортран-GNS. 7. Идентификация абонентов при передачи сообщений в языке Фортран-GNS. Допускаются ответы на пп 4 - 7 в терминах PVM,MPI. Горелик А.М., Задыхайло И.Б. Расширение Фортрана для многопроцессорных систем с распределенной памятью. -М. Препринт ИПМ РАН 1992. N32 - 3 - Адаптация последовательных программ к параллельным архитектурам. Век- торизация и распараллеливание циклов. Методы координат, гиперплоскос- тей. 1. Автоматическое распараллеливание последовательных программ. 2. Семантика циклов, выполняемых параллельно на ОКМД системах. 3. Алгоритмы преобразования программ методом координат. 4. Схема преобразования программ методом гиперплоскостей. 5. Оценить возможность параллельного выполнения цикла: DO i = 2,N A(i) = (B(i) + C(i))/A(i+CONST) ENDDO 6. Определить возможность выполнения циклов на ОКМД системах: DO 2 I=2,N,2 2 A(I) = (A(I)+A(I-1))/2.0 DO 3 I=2,N A(I) = B(I)+A(I+1) 3 B(I) = (A(I)+A(I+1))/2.0 DO 4 I=1,N A(I) = B(I)+A(I+1) 4 C(I) = (A(I)+A(I+1))/2.0 DO 5 I=1,N A(I) = B(I)+A(I+1) 5 С(I) = A(I+1) Ручное распараллеливание. Стандарты OpenMP. 1. Назначение OpenMP. М. Кузьминский. Открытые системы N3/98 Воеводин В.В. Математические модели и методы в параллельных процес- сах.-М.: Наука. 1986.-296 с. Э, А. Трахтенгерц. Введение в теорию анализа и распараллеливания прог- рамм ЭВМ в процессе трансляции. -М.: Наука,1981.-254с. Распараллеливание алгоритмов обработки информации. Том 1. -Киев: На- ук.думка, 1985.-280 с. Доклады В.В. Воеводина, Вл.В. Воеводина, А.В. Забродина на Всесоюзной молодежной школе "Суперкомпьютерные вычислительно-информационные тех- нологии в физических и химических исследованиях" 1999 г. Черноголовка - http://parallel.ru:81/info/education/chg99.html Особенности выполнения арифметических выражения на ЭВМ. Распараллели- вание вычислительных алгоритмов. Метод распараллеливания алгоритма об- щей рекурсии 1-го порядка. 1. Распараллеливание алгоритмов сложения методом редукции. 2. Метод распараллеливания алгоритма общей рекурсии 1-го порядка. 3 Арифметика машинных чисел. 4. Погрешности при вычислениях чисел на параллельных системах. Оце- нить полную ошибку для суммирования положительных чисел. 5. Точность плавающей арифметики. Р.Хокни, К.Джасхоуп. Параллельные ЭВМ. М.: Радио и связь. 1986. Г.К. Боровин и др. Ошибки-ловушки при программировании на Фортране.-М. Наука. 1987. 144 с. Литература 1. В.В. Корнеев. Параллельные вычилительные системы.-М. <Нолидж>, -320с. 2. Б.А.Головкин. Вычислительные системы с большим числом процессо- ров.-М.: Радио и связь, 1995.-320с. 3. М. Амамия, Ю.Танака. Архитектура ЭВМ и искусственный интеллект: 4. Языки и параллельные ЭВМ. Сб.>Алгоритмы и алгоритмические языки>, М.: Наука, 1990. 5. http://parallel.ru:81