Высокопроизводительные вычисления: курс лекций
В конце 2001 года я разработал цикл лекций по архитектуре и программированию
для высокопроизводительных компьютеров и вычислительных систем; лекции читались
Очевидно, что некоторые моменты курса за прошедшее время устарели, но большая часть информации будет актуальна еще долго, это и история развития высокопроизводительных компьютеров, это и общие принципы построения таких компьютеров, ровно как и принципы параллельного программирования и проектирования параллельных процессов.
Объем курса — около 300 страниц, частично
[09–10–2003] Update: выложил курс в свободный доступ, можно качать прямо с сайта.
Последние полтора года курс не обновлялся, так что информация частично устарела,
более того, ситуация со временем усугубится, так как вероятность того, что я
буду этот курс читать в ближайее время очень невелика. Пользуйтесь, если
Не так давно вышла книга Воеводиных «Параллельные Вычисления», и она хороша! Очень рекомендую. Содержание книги в большой степени перекрывает содержание курса лекций и проработана она, конечно, куда лучше. Купить ее можно, напимер, на Озоне.
Огромное спасибо за помощь моему научному руководителю, проф. Птицыной Ларисе Константиновне.
Архитектура высокопроизводительных компьютеров и вычислительных систем
Лекция №1. Введение в тему, общие сведения.
1. Введение.
2. Предмет курса.
2.1. Классификация компьютеров:
2.1.1. персональные компьютеры
2.1.2. рабочие станции
2.1.3. x-терминалы
2.1.4. серверы
2.1.5. мэйнфреймы
2.1.6. минисуперкомпьютеры
2.1.7. суперкомпьютеры
2.1.8. кластеры
2.1.9. мета компьютеры
2.2. Нечеткость классификации, история развития суперкомпьютеров, сравнение с состоянием дел на данный момент. Рост частоты процессоров в сравнении с ростом производительности, значение архитектуры.
2.3. Трактовка понятия "архитектура".
3. Проблемная, предметная и объектная ориентация высокопроизводительных компьютеров и вычислительных систем. Специфика предъявляемых к ним требований.
4. Системы классификационных признаков суперкомпьютеров.
4.1. Классическая систематика Флинна.
4.2. Дополнения Ванга и Бриггса к классификации Флинна.
4.3. Классификация Фенга.
4.4. Классификация Базу.
4.5. Другие классификации.
5. Классификация вычислительных систем: однопроцессорные и многопроцессорные системы; многопроцессорные системы с общей памятью и с локальной памятью; параллельные и распределенные вычислительные системы.
5.1. Краткая история появления параллелизма в архитектуре ЭВМ.
5.1.1. IBM 701 (1953), IBM 704 (1955): разрядно-параллельная память, разрядно-параллельная арифметика
5.1.2. IBM 709 (1958): независимые процессоры ввода/вывода.
5.1.3. IBM STRETCH (1961): опережающий просмотр вперед, расслоение памяти.
5.1.4. ATLAS (1963): конвейер команд.
5.1.5. CDC 6600 (1964): независимые функциональные устройства.
5.1.6. CDC 7600 (1969): конвейерные независимые функциональные устройства.
5.1.7. ILLIAC IV (1974): матричные процессоры.
5.1.8. CRAY 1 (1976): векторно-конвейерные процессоры
6. Оценка производительности высокопроизводительных компьютеров и вычислительных систем.
6.1. Стандарты в области оценки производительности.
6.2. Стратегии построения систем тестирования.
6.3. Виды тестов. Что такое FLOPS, MIPS. Синтетические тесты.
6.4. Supercomputer TOP500, критерии ранжирования, тест LINPACK, место России.
6.5. МВС-1000М, что это на самом деле.
6.6. Закон Амдала, теоретический и реальный рост производительности при распараллеливании вычислений.
Лекция №2. Базовые архитектурные представления.
1. Оценка производительности высокопроизводительных компьютеров и вычислительных систем, продолжение. История и цифры для сравнения.
1.1. Stone Age in performance testing:
1.1.1. WhetStone
1.1.2. DhryStone
1.2. Рейтинги различных систем по WhetStone, критерии разбиения на суперкомпьютеры, мэйнфреймы, миникомпьютеры, рабочие станции и ПК и их изменение за последние 30 лет. Стоимость одного MWIPS, $K, ситуация за последние 30 лет.
1.3. Пакеты тестов, базирующихся на реальных прикладных программах:
1.3.1. SPEC (Standard Performance Evaluation Corporation)
1.3.1.1. CPU2000
1.3.1.1.1. CINT2000
1.3.1.1.2. CFP2000
1.3.1.2. HPC96
1.3.2. TPC (Transaction Processing Performance Council)
1.4. Закон Гроша применительно к производительности компьютеров.
2. Многоплановое толкование понятия "архитектура".
2.1. Концепция взаимосвязи элементов сложной структуры.
2.2. Компоненты логической, физической и программной структур.
3. Типы архитектур:
3.1. фон-неймановская архитектура,
3.2. гарвардская архитектура,
3.3. Отступление, концепция многоуровневой работы ВМ, понятие семантического разрыва.
3.4. не-фон-неймановские архитектуры.
3.4.1. Стековая архитектура, каноническая стековая машина.
3.4.2. Теговая архитектура (tagged architecture).
3.4.3. Разрядно модульная архитектура (bit-slice architecture).
Лекция №3. Базовые архитектурные представления, продолжение.
1. Классификация функциональных устройств.
2. Классификация процессоров.
2.1. Архитектура системы команд.
2.1.1. CISC процессоры.
2.1.2. RISC процессоры.
2.1.3. MISC процессоры.
2.2. Матричные процессоры.
2.3. Процессоры с конвейерной обработкой.
2.3.1. Пример типового конвейера команд.
2.3.2. Выигрыш от конвейерной обработки и основные проблемы эффективного заполнения конвейера.
2.4. Суперскалярный процессор.
2.4.1. Пример суперскалярной обработки. Процессор Pentium.
2.5. VLIW машины.
2.6. Коммуникационный процессор.
2.7. Отступление, понятие о сигнальных процессорах:
2.7.1. Систолические матрицы.
2.7.2. Волновые процессоры.
3. Системы команд процессора.
3.1. Типы команд.
3.2. Принципы управления потоком команд.
3.3. Методы адресации.
3.4. Типы и размеры операндов.
4. Типы процессорных сетей связи. Ключевые принципы организации системы памяти. Типы интерфейсов. Основные принципы организации ввода/вывода.
5. Отступление: подъем популярности векторной обработки. Векторные операции в ПК. MMX, 3D now!.
Лекции №4,5,6. Архитектура суперкомпьютеров.
1. Классификация архитектур суперкомпьютеров.
1.1. Векторно-конвейерные суперкомпьютеры.
1.2. Многопроцессорные векторные суперкомпьютеры.
1.3. Суперкомпьютеры с архитектурой симметричных многопроцессорных систем.
1.4. Суперкомпьютеры массивно параллельной архитектуры.
1.5. Суперкомпьютеры с обобщенной архитектурой кластерных систем, систем с массовым параллелизмом и симметричных многопроцессорных систем.
2. Запоминающие устройства ЭВМ
2.1. Определение понятия "память".
2.2. Основная память.
2.2.1. Классификация памяти по специфике использования (СОЗУ, ОЗУ, ПЗУ, ППЗУ).
2.2.2. Виды памяти: статическая и динамическая.
2.2.3. DRAM.
2.2.3.1. Структура организации блока памяти (2D, 3D, 2.5D).
2.2.3.2. Регенерация памяти. Различные методы регенерации (ROR, CBR, SR).
2.2.4. SRAM.
2.2.4.1. Классификация (ROM, PROM, EPROM, EEPROM, Flash Memory)
2.2.4.2. Понятие "кэш память".
2.2.4.2.1. Политики чтения и записи из/в кэш память.
2.2.4.2.2. Варианты организации кэш памяти (с прямым отображением (direct mapped), полностью ассоциативный (fully associative) и группово-ассоциативный (set-associative)).
2.2.5. Аппаратный контроль корректности работы памяти. Контроль четности. ECC.
2.2.6. Логическая организация памяти.
2.2.7. Основные характеристики памяти.
2.2.8. Варианты организации памяти ЭВМ с целью ускорения к ней доступа, и обеспечения возможности параллельного доступа. Расслоение памяти.
2.3. Дисковая память.
2.3.1. Варианты эффективной организации дисковых накопителей с целью повышения надежности и скорости доступа. RAID.
2.3.1.1. Уровни RAID.
2.3.1.2. Аппаратное обеспечение RAID.
2.3.1.3. Затраты и целесообразность применения RAID.
3. Специфика подсистем ввода/вывода.
4. Топология сетей связей.
4.1. Компоненты ЭВМ (АЛУ, управление, память, периферийные устройства). Необходимость наличия связей между компонентами.
4.2. Варианты организации связей. Компромисс между количеством связей и скоростью передачи данных.
4.3. Шины. Мезонинные шины. Синхронизация на шине. Bus masters and bus slaves. Арбитраж. История развития шин на примере IBM PC (XT, ISA, EISA, VLB, PCI).
4.4. Варианты организации сетей связей процессоров (решетка, кольцо, дерево, N мерный тор, гиперкуб).
5. Более подробно о основных классах современных параллельных компьютеров.
5.1. Симметричные мультипроцессорные системы (SMP).
5.2. Массивно-параллельные системы (МРР).
5.3. Системы с неоднородным доступом к памяти (NUMA).
5.4. Параллельно-векторные системы (PVP).
5.5. Кластерные системы.
5.6. Модели программирования, применяемые в различных классах параллельных ЭВМ.
Лекция №7. Архитектура реально существующих суперкомпьютеров.
1. Векторно-конвейерные супер-ЭВМ (на примере CRAY C90).
1.1. Структура оперативной памяти.
1.2. Ввод-вывод.
1.3. Организация процессора. Состав регистров. Функциональные устройства. Управление.
1.4. Параллельное выполнение программ. Векторная обработка. Зацепление команд.
1.5. Структура процессора и примеры выполнения различных векторных команд.
1.6. Понятие о векторизации программ. Преграды для векторизации.
1.7. Объединение отдельных векторных процессоров в C90.
2. Массивно-параллельные компьютеров (на примере CRAY T3D).
2.1. Вычислительные узлы и процессорные элементы.
2.2. Коммуникационная сеть. Нумерация вычислительных узлов.
2.3. Факторы, снижающие производительность параллельных компьютеров. Закон Амдала и его следствия. Равномерная загрузка процессоров системы.
2.4. Понятие о распараллеливании программ. Модель программирования MPP систем (message passing).
3. Характеристики и архитектура современных микропроцессоров (Alpha, Power PC, SPARC).
Лекция №8. Слабосвязанные многомашинные системы.
1. Кластерные системы.
1.1. Кластерный подход к обеспечению высокой готовности и наращиванию производительности компьютеров.
1.2. Предметная ориентация кластерных систем. Отличие кластеров серверов от вычислительных кластеров (MOSIX). Преимущества кластерного подхода к организации систем с множественным потоком команд и множественным потоком данных. Классификация кластеров. Архитектура кластерных систем. Характеристика коммуникационной инфраструктуры. Особенности организации взаимодействия между процессами. Модели обмена сообщениями. Повышение производительности кластерных систем.
1.3. VAX кластер, как исторический прототип. Признаки VAX кластера.
1.4. Системы высокой готовности.
1.4.1. Задача обеспечения продолжительного функционирования системы. надежность, готовность и удобство обслуживания.
1.4.2. Среднее время наработки на отказ (MTBF - Mean Time Between Failure), коэффициент готовности.
1.4.3. Типы систем, свойством которых является та или иная форма снижения планового и непланового времени простоя.
1.5. Linux кластеры. Проект Beowulf. Примеры Beowulf кластеров: theHive, Avalon. Принципы построения Beowulf кластеров. Значение сетей связи, варианты организации сетей связи. Классы Beowulf систем.
2. Мета-компьютинг и мета-компьютеры.
2.1. Примеры: distributed net, SETI@home.
Лекция №9,10. Операционные системы распределенных вычислительных систем.
1. 2 взгляда на ОС. ОС, как менеджер ресурсов.
2. История ОС. Развитие от библиотек процедур до современного состояния.
3. Виды операционных систем (сетевые ОС, распределенные ОС, ОС мультипроцессорных ЭВМ).
4. Принципы построения распределенных ОС (прозрачность, гибкость, надежность, эффективность, масштабируемость).
5. Операционные системы мультипроцессорных ЭВМ. Процессы и нити. Виды многозадачности.
6. Взаимодействие процессов. Взаимное исключение критических интервалов. Алгоритмы Деккера и Петерсона. Использование неделимой операции TEST_and_SET_LOCK. Семафоры Дейкстры.
7. Планирование процессов.
8. Коммуникации. Семиуровневая модель ISO.
9. Синхронизация в распределенных системах. Синхронизация времени. Абсолютное и логическое время. Алгоритм Лэмпорта. Выбор координатора в многопроцессорной системе.
10. Распределенные файловые системы. Файловые серверы и серверы каталогов. Именование ресурсов. Двухуровневая схема именования. Семантика разделения файлов. Кэширование. Проблема когерентности кэшей. Размножение файлов. Пример: NFS.
11. Распределенная общая память. Алгоритмы реализации DSM (с центральным сервером, миграционный алгоритм, алгоритм с размножением для чтения, с полным размножением). Модели консистентности.
12. Обеспечение надежности в распределенных системах. Виды отказов, восстановление после отказов.
Лекция №11. Программирование для высокопроизводительных ЭВМ.
1. Две модели программирования: последовательная и параллельная. Две парадигмы параллельного программирования. Параллелизм данных. Параллелизм задач.
2. Издержки и выигрыш при реализации параллельных и векторных вычислений. Трудовые затраты на распараллеливание или векторизацию программы. Способы векторизации и распараллеливания программ. Применение разных языков программирования. Различие и сходство между распараллеливанием и векторизацией программ. Сходство алгоритмов - параллелизм данных. Различие алгоритмов - параллелизм действий.
3. Векторные ЭВМ и векторные программы. Предельное быстродействие векторных программ. Две части программ - скалярная и векторная. Дополнительные затраты на организацию векторных вычислений во время работы программы. Ограниченное число векторных регистров. Ограничения на используемые операторы в векторизуемых циклах.
4. Параллельные ЭВМ и параллельные программы. Три части программы - параллельная, последовательная и обмен данными. Синхронизация процессов, равномерность загрузки процессов. Средства распараллеливания в трансляторах и параллельные библиотеки.
Лекция №12. Message Passing Interface (MPI).
1. MPI. История MPI. Стандарты MPI. Терминология и обозначения. Общие процедуры MPI. Прием/передача сообщений между отдельными процессами. Объединение запросов на взаимодействие. Совмещенные прием/передача сообщений. Коллективные взаимодействия процессов. Синхронизация процессов. Работа с группами процессов. Предопределенные константы. Примеры MPI-программ.
Лекция №13. Параллельный язык mpC.
1. Решаемые задачи. Особенности синтаксиса. Сети процессов. Операции над набором процессов. Тип сети, определение типов сети. Синхронизация процессов. Барьерные функции. Подсети. Векторные вычисления. Неоднородные вычисления, распределение нагрузки в гетерогенном окружении.
Лекция №14,15,16. Базовые вычислительные алгоритмы и методы распараллеливания вычислений.
1. Задача распараллеливания алгоритма. 3 основных требования к параллельному алгоритму: concurrency, scalability, locality.
2. Методика разработки параллельных алгоритмов.
2.1. Разбиение исходной задачи. Декомпозиция на уровне данных, функциональная декомпозиция.
2.2. Определение связей. Локальные и глобальные связи. Выявление параллелизма. Неструктурированные и динамические сети связи. Асинхронные коммуникации.
2.3. Агломерация. Увеличение гранулярности данных и вычислений. Репликация данных и вычислений.
2.4. Отображение на реальное аппаратное обеспечение. Алгоритмы динамической балансировки загрузки. Алгоритмы планирования задач.
Assembled 17/12/2001
By Ivan Shagin
- Скачать архив текстов лекций. (.rar, 1 mb).
- Скачать содержание курса лекций (.doc, 70 kb).
- Скачать экзаменационные вопросы к курсу лекций (.doc, 50 kb).
- Скачать список ссылок к курсу лекций (.doc, 40 kb).
 |
|