Федеральное агентство по образованию

Государственное образовательное учреждение высшего профессионального образования

«Новосибирский государственный университет» (НГУ)

Факультет информационных технологий

Кафедра Параллельных вычислений

ПРОГРАММА

«Математическое обеспечение современных

ДИСЦИПЛИНЫ

высокопроизводительных вычислительных систем»

ЦИКЛ* «Специальные дисциплины»

НАПРАВЛЕНИЕ ПОДГОТОВКИ БАКАЛАВРОВ 552800 «ИНФОРМАТИКА И

ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА»

Авторы Малышкин В.Эм., проф., д.т.н.

Городничев М.А., ассистент Киреев С.Е., ст. преподаватель Перепелкин В.А., ассистент Калгин К.В., ассистент Новосибирск * Наименование цикла дисциплин в соответствии с ГОС ВПО Программа дисциплины «Математическое обеспечение современных высокопроизводительных вычислительных систем» составлена в соответствии с требованиями к обязательному минимуму содержания и уровню подготовки бакалавров по циклу «Специальных дисциплин» Федерального государственного образовательного стандарта высшего профессионального образования по направлению «Информатика и вычислительная техника» от 13 марта 2000 г.

1. Цели и задачи дисциплины (курса) Дисциплина «Математическое обеспечение современных высокопроизводительных вычислительных систем» имеет своей целью изучение современных перспективных высокопроизводительных вычислительных систем, их программного обеспечения и тенденций развития, а также получение навыков разработки программ для таких вычислительных систем в современном технологическом окружении.

Для достижения поставленной цели выделяются задачи курса:

• Изучить архитектуры современных высокопроизводительных вычислительных систем (ВВС).

• Рассмотреть проблемы организации вычислений на ВВС.

• Познакомиться с тенденциями в развитии программного обеспечения для ВВС.

• Изучить технологии программирования ВВС.

• Получить навыки эффективного программирования современных ВВС.

2. Требования к уровню освоения содержания дисциплины В результате освоения дисциплины студент должен:

Иметь представление о • областях применения ВВС, • принципах организации вычислений на современных ВВС, • тенденциях развития ВВС, Знать • архитектуру существующих ВВС, • системное и прикладное программное обеспечение ВВС, • способы создания эффективных программ для современных ВВС.

Уметь • использовать существующее программное обеспечение для организации вычислений на ВВС, • разрабатывать эффективные алгоритмы для современных ВВС, • пользоваться различными средствами создания и отладки программ для ВВС.

3. Объем дисциплины и виды учебной работы Вид учебной работы Всего Семестры часов Общая трудоемкость дисциплины 72 Аудиторные занятия, в том числе: 54 Лекции 18 Семинары Лабораторные работы 36 Самостоятельная работа, в том числе: 18 Курсовой проект Реферат 10 Расчетные работы Другие виды самостоятельной работы: 8 оформление отчетов по лаб.работам подготовка к контрольным вопросам на защите Общая трудоемкость дисциплины составляет 72 зачетных единицы (если применяется на факультете/кафедре).

4. Содержание дисциплины 4.1. Новизна курса (научная, содержательная; сравнительный анализ с подобными курсами в России и за рубежом).

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

4.2. Тематический план курса (распределение часов по видам учебной работы).

распределенной памятью.

ВВС общего назначения с распределенной памятью.

программ, динамическая балансировка нагрузки.

общей памятью.

ВВС общего назначения с общей 7. Архитектура графических ускорителей 1 графических ускорителей алгоритмы.

мелкозернистых алгоритмов и структур с использованием системы WinALT 4.3. Содержание разделов и тем курса.

А) Теоретическая часть.

1. Введение. Цели и задачи курса. Обзор современных вычислителей. Организация современных ВВС. Классификация современных ВВС по архитектурам, технологиям программирования и программному обеспечению.

2. ВВС общего назначения с распределенной памятью (мультикомпьютеры, кластеры, 3.1. Сети ЭВМ, их назначение и способы организации вычислений.

3.2. Мультикомпьютеры и кластеры, их архитектуры и аппаратное обеспечение.

3.3. Системное программное обеспечение кластеров.

3.4. Сети ЭВМ, их назначение и организация.

3.5. Системное программное обеспечение организации и поддержки вычислений 3.6. Организация доступа к кластерам и сетям ЭВМ, безопасность вычислений.

3.7. Организация отказоустойчивости вычислений на кластерах и сетях ЭВМ.

3.8. Применение кластеров и вычислительных сетей.

3.9. Языки и средства программирования систем с распределенной памятью.

3.10. Современные достижения в области организации параллельных вычислений на 3.11. Статическая и динамическая настройки программ на доступные ресурсы, централизованные и распределенные алгоритмы, формирование начальной 3.12. Динамические свойства параллельных программ, динамическая балансировка нагрузки (синхронные, асинхронные, централизованные, диффузионные и смешанные алгоритмы). Алгоритмы и средства планирования загрузки.

3.13. Надежность вычислений, различные определения надежности, методы 3. ВВС общего назначения с общей памятью 4.1. Архитектура компьютеров с общей памятью. Эмуляция общей памяти на 4.2. Примеры современных архитектур. Тенденции развития.

4.3. Модели параллельного программирования.

4.4. Программирование в модели Shared Memory.

4.5. Способы параллельного программирования в общей памяти. Их применение 4.6. Технологические аспекты распараллеливания. Оценка эффективности параллельных программ. Оптимизация программ с общей памятью.

4.7. Языки и средства программирования систем с общей памятью. Библиотеки 4.8. Перспективы развития архитектур с общей памятью и особенности их 5. Программирование специализированных вычислителей. Программирование графических ускорителей (CUDA, Brook+, OpenCL).

5.1. Архитектура графических ускорителей NVIDIA и ATI. Иерархия памяти.

Существующие и разрабатываемые графические ускорители. Различия SIMD и SIMT 5.2. Устройство мультипроцессора. Разделяемая память и файл регистров.

Константные и текстурные кэши.

5.3. Особенности эффективного обращения к разделяемой памяти.

5.4. Особенности эффективного обращения к глобальной памяти.

5.5. Исполнение программы на графическом ускорителе. Планирование потоков.

Загрузка планировщика. Размер блока потоков и его влияние на загрузку планировщика.

5.6. Передача данных на графический ускоритель. Блокируемый, асинхронный и дуплексный режимы.

5.7. Средства программирования графических ускорителей: CUDA, Brook+, 5.8. Использование математических библиотек NVIDIA и AMD для графических ускорителей.

5.9. Средства отладки и профилирования программ для графических ускорителей.

5. Мелкозернистые вычисления: модели, алгоритмы и приложения.

6.1. Обзор формальных моделей массовых параллельных вычислений: основные определения, характерные черты, области применения. Обзор компьютерных систем моделирования клеточных автоматов и их расширений.

6.2. Алгоритм параллельных подстановок. Базовые понятия. Синхронная и асинхронная моды выполнения системы параллельных подстановок. Понятие алгоритма параллельных подстановок. Подклассы и расширения алгоритмов 6.3. Асинхронная композиция алгоритмов параллельных подстановок.

Композиционное расширение алгоритма параллельных подстановок, способы 6.4. Корректность систем параллельных подстановок. Распознавание неоднозначности систем параллельных подстановок и незавершаемости 6.5. Компьютерное моделирование мелкозернистых алгоритмов и структур с использованием системы WinALT. Общее описание системы WinALT..

Языковые средства системы. Графическая среда системы WinALT.

6.6. Основы клеточной технологии конструирования моделей. Выполнение и 7. Заключение.

В) Лабораторные работы 1. Знакомство с кластерами, очереди заданий на кластерах, доступ к вычислительным ресурсам.

2. Программирование коммуникаций на основе протокола TCP/IP.

3. Разработка и реализация распределенной отказоустойчивой системы выполнения заданий.

4. Реализовать задание по варианту на графическом ускорителе. Количество невыровненных обращений в глобальную и разделяемую памяти свести к минимуму.

Передачи данных на графический ускоритель выполнять на фоне вычислений.

5. Эксперименты с библиотеками для разбиения графов Metis, ParMetis, Jostle, Chaco, Party, PMRSB, S-HARP, SCOTCH, TOP/DOMDEC, WGPP. Использования этих инструментов для реализации балансировки в численных параллельных программах.

6. Реализация алгоритмов балансировки в модельных задачах.

7. Разработка системы поддержки надежных вычислений (в смысле устойчивости к сбоям).

8. Реализация подсистемы мониторинга и визуализации для численных задач.

9. Построение в системе WinALT имитационных моделей машины Тьюринга.

10. Построение в системе WinALT имитационных моделей классических клеточных Самовоспроизводящаяся структура Сиппера, Самовоспроизводящаяся петля Лангтона.

11. Построение в системе WinALT имитационных моделей информационных структур:

Многоступенчатые конвейеры арифметических операций, Динамически перестраиваемые в процессе вычислений многоступенчатые конвейеры, Ассоциативные процессоры, Однородные вычислительные структуры.

12. Построение в системе WinALT имитационных моделей физических процессов:

Модели диффузии, Модели FHP-газа.

13. Конструирование средствами системы WinALT пользовательских меню, диалогов, окон с графиками и диаграммами для задания параметров графической среды и управления процессом моделирования.

Варианты заданий для лабораторных работ по программированию специализированных вычислителей:

1. Умножение плотных матриц большого размера.

2. Клеточный автомат: игра «Жизнь».

3. Гравитационное взаимодействие N-тел.

4. Параллельная сортировка.

5. Решение двумерного уравнения Пуассона методом Якоби.

6. Решение волнового уравнения с помощью явной разностной схемы.

7. Многомерное интегрирование методом Гаусса.

8. Многомерное интегрирование методом Монте-Карло.

4.4. Перечень примерных контрольных вопросов и заданий для самостоятельной работы.

Примерные контрольные вопросы:

1. Организация вычислений в мультипроцессорном узле кластера. Особенности программирования взаимодействия процессов над общим полем неоднородоной памяти (NUMA).

2. Программное обеспечение кластеров.

3. Учет топологий связи в кластерах при проектировании параллельных программ.

4. Сокрытие передачи данных на фоне вычислений.

5. Методы динамической балансировки вычислительной загрузки узлов вычислительных систем.

6. Обеспечение надежности вычислений.

7. К какому классу ближе видеокарта в классификации Флинна (SISD, MISD, SIMD, MIMD)? Понятие SIMT-архитектуры.

8. Возможность синхронизации на уровне блоков потоков в графическом ускорителе.

9. Как влияют на производительность графического ускорителя количество используемых регистров и разделяемой памяти?

10. Как эффективно организовать загрузку массива однобайтовых элементов в разделяемую память графического ускорителя?

11. Особенности исполнения условных переходов в мультипроцессоре графического 12. Клеточный автомат - модель пространственно-распределенной динамической системы (изучение явлений: упорядочение, турбулентность, хаос, нарушение симметрии, фрактальность и др.).

13. Охарактеризовать однородные вычислительные структуры, привести пример вычисления булевской функции в ПЛМ.

14. Охарактеризовать итеративные структуры, привести пример вычисления булевской функции в итеративной структуре.

15. Описать технологию ПЛИС, привести пример ее применения для создания специализированных процессоров.

16. Описать технологию проектирования систолических алгоритмов, построить пример систолического алгоритма умножения матриц.

17. Описать принципы конструирования матричных схем, разобрать пример построения матричного умножителя.

18. Описать клеточную технологию конструирования конвейерных алгоритмов арифметических операций, ориентированную на реализацию в 3D СБИС.

4.5. Примерная тематика рефератов.

1. Разработка системы распределенных вычислений на простаивающих персональных компьютерах в рамках организации.

2. Обзор архитектуры процессора Larrabee.

3. Обзор архитектуры и средств программирования графических ускорителей от ATI.

4. Сравнение графических ускорителей NVIDIA и ATI.

5. Построить WinALT модель конвейерного алгоритма умножения двоичных чисел (на основе счетчиковой схемы 3->2) в матричном процессоре.

6. Построить WinALT модель конвейерного алгоритма вычисления скалярного произведения в матричном процессоре.

7. Построить WinALT модель алгоритма визуальной криптографии.

8. Построить WinALT модель FHP газа.

9. Построить WinALT модель универсальной машины Тьюринга.

10. Построить WinALT модель клеточно-нейронной сети.

5. Учебно-методическое и информационное обеспечение дисциплины (курса) 5.1. Примерный перечень вопросов к зачету (экзамену) по всему курсу.

• Организация вычислений в мультипроцессорном узле кластера. Особенности программирования взаимодействия процессов над общим полем неоднородоной • Влияние количества используемых регистров и разделяемой памяти на производительность графического ускорителя.

• Программное обеспечение кластеров.

• Описание графических средств системы WinALT.

• Сокрытие передачи данных на фоне вычислений.

• Иерархическая организация памяти графического ускорителя. Исполнение программ на графическом ускорителе. Сравнение с командами RISC-архитектур.

• Методы динамической балансировки вычислительной загрузки узлов вычислительных систем.

• Сеть Петри - модель поведения параллельной системы.

• Обеспечение надежности вычислений.

• Декомпозиция алгоритмов параллельных подстановок и расслоение клеточных • Учет топологий связи в кластерах при проектировании параллельных программ.

• Обобщенная модель клеточных вычислений – Алгоритм Параллельных Подстановок.

• Общее устройство графического ускорителя (процессоры и мультипроцессоры).

• Компьютерное моделирование клеточных вычислений. Структура и основные характеристики системы имитационного моделирования WinALT.

• Уровни иерархии блоков потоков графического ускорителя. Синхронизация потоков на различных уровнях иерархии. Общая и различная память на различных уровнях организации. Запуск ядра.

• Описание языковых средств системы WinALT.

• Клеточный автомат: определение, свойства, классы, теоретическое и практическое • Асинхронная композиция алгоритмов параллельных подстановок.

• Применение клеточных моделей вычислений для исследований в физике и • Интерпретация алгоритма параллельных подстановок сетью автоматов. Процедура • Клеточная технология проектирования параллельных алгоритмов и архитектур.

• Планирование исполнения потоков в графических ускорителях. Минимальная единица планирования и исполнения. Обработка условных переходов.

5.1. Основная литература*.

1. NVIDIA CUDA Zone, http://www.nvidia.com/cuda 2. В.Э. Малышкин. Введение в параллельное программирование мультикомпьютеров.

– Новосибирск, 2003. – ИВМ и МГ СО РАН, 268 с.

3. Корнеев В.В. Параллельное программирование в MPI. Москва-Ижевск: институт компьютерных исследований, 2003 г.

4. NVIDIA CUDA Zone, http://www.nvidia.com/cuda 5. CUDA University Courses, http://www.nvidia.com/object/cuda_university_courses.html 6. Тоффоли Т., Марголус Н. Машины клеточных автоматов. - М.: Мир, 1991, 278 с.

7. Achasova S., Bandman O., Markova V. and Piskunov S. Parallel Substitution Algorithm.

Theory and Application. - Singapore:World Scientific, 1994, 220 р.

5.2. Дополнительная литература.

1. Top 500 supercomputer sites, www.top500.org 2. К.Е.Афанасьев, С.В.Стуколов. Многопроцессорные вычислительные системы и госуниверситет, 2003г.

3. В.В.Воеводин, Вл.В.Воеводин. Параллельные вычисления. СПб.: БХВ-Петербург.

4. Barcelona Supercomputing Center: Cell Superscalar, www.bsc.es/cellsuperscalar 5. RapidMind Development Platform, www.rapidmind.net 6. Mercury Computer Systems, http://www.mc.com 7. Дж. фон Нейман. Теория самовоспроизводящихся автоматов. - М.: Мир, 1971.

8. Методы параллельного микропрограммирования / Под ред. О.Л. Бандман.Новосибирск: Наука, Сибирское отделение, 1981.

9. Lect. Notes in Artificial Intelligence. 2001. 2159. P.282.

10. Евреинов Э.В., Косарев Ю.Г. Однородные универсальные вычислительные системы высокой производительности.- Новосибирск: Наука. Сибирское 11. OpenCL specifications, http://www.khronos.org/opencl/ 12. Brook specifications, http://merrimac.stanford.edu/brook/ 5.3. Программное и коммуникационное обеспечение (если используется).

Лабораторные работы проводятся на вычислительных системах ИВМиМГ СО РАН:

кластер HKC-30 (100 4х-ядерных процессора Intel Xeon E5450), кластер HKC-160 ( процессора Intel Itanium 2), сервер с общей памятью HP DL580 G5 (4 4х-ядерных процессора Intel Quad Core Х7350), Sony Playstation 3 на основе процессора Cell Broadband Engine. При этом используется все необходимое программное обеспечение установленное на этих системах: MPICH, POSIX Threads, OpenMP, GNU compiler collection, Intel compilers, SSH-клиент, соединение с Интернет.

Не более 10 источников.

6. Методические рекомендации по организации изучения дисциплины Курс является обзорным и состоит из четырех основных тем, соответствующих различным классам высокопроизводительных вычислителей: вычислители с распределенной памятью, вычислители с общей памятью, графические ускорители и мелкозернистые вычисления. По каждой теме дается набор лекций, вводящих в проблематику использования данного класса вычислителей и представляющих необходимые программные средства.

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

Текущий контроль. В течение семестра контролируются навыки и теоретические знания путем защиты лабораторных работ. Выполнение лабораторных работ является обязательным для всех студентов, результаты текущего контроля служат основанием для выставления оценок в ведомость контрольной недели на факультете.

Промежуточный контроль. Для контроля усвоения дисциплины учебным планом предусмотрен экзамен. Перечень вопросов приведён выше. К экзамену допускаются студенты, выполнившие все лабораторные работы.