• Специальные главы дискретной математики
• Параллельные вычислительные методы
• Архитектура ЭВМ и сетей
• Основы параллельного программирования
• Математическое обеспечение высокопроизводительных вычислительных систем
  • Вопросы к экзамену
  • Динамические свойства параллельных программ (Городничев М.А.)

Специальные главы дискретной математики

Бально-рейтинговая система

Долги можно посмотреть тут.

Доступны для скачивания следующие материалы:

• Билеты по теоретической части курса СГДМ
• Методическое пособие по курсу (Дата последнего обновления: 4 сентября 2008 года)
• Методическое пособие. Модуль 1 (обновлено 18 сентября 2009 года)
• Методическое пособие. Модуль 2 (обновлено 18 сентября 2009 года)
• Методическое пособие. Модуль 3 (обновлено 13 октября 2009 года)
• Методическое пособие. Модуль 4 (обновлено 7 ноября 2009 года)
• Методическое пособие. Модуль 5 (обновлено 6 ноября 2009 года)
• М. Гэри, Д. Джонсон: Вычислительные машины и трудно решаемые задачи
• Т. Хоар: Взаимодействующие последовательные процессы
• Р. Столл: Множества. Логика. Аксиоматические теории.
• В.Э.Малышкин, В.Д.Корнеев. Параллельное программирование мультикомпьютеров.

Расчетно-Графическое Задание для студентов 2-го курса ФПМИ:

1. Вариант задания определяется номером в журнале посещаемости группы.
2. Работы принимаются в письменном или печатном виде, обязательно с титульным листом, на котором указываются ФИО и номер группы студента.
3. Для получения допуска к экзамену необходимо сдать РГЗ в конце декабря.
4. Все студенты, не имеющие неотработанных пропусков, имеют возможность, защитив РГЗ, получить оценку по практике досрочно. Защита предварительно планируется на конец декабря. При защите преимущества имеют студенты, посетившие все семинарские занятия и активно на них работавшие.
5. Кроме решенных задач для защиты необходимо знать основные понятия, формулы и определения, которые вводились на семинарах, уметь ими оперировать.
6. По всем вопросам нужно обращаться к преподавателю либо по email, либо на семинарах.
7. Варианты заданий:
   
   

   Вариант №1 Вариант №2 Вариант №3 Вариант №4 Вариант №5 Вариант №6 Вариант №7 Вариант №8 Вариант №9 Вариант №10 Вариант №11 Вариант №12 Вариант №13 Вариант №14 Вариант №15 Вариант №16 Вариант №17 Вариант №18 Вариант №19 Вариант №20 Все варианты в архиве

1. Э. Рейнгольд, Ю. Нивергельт, Н. Нео. Комбинаторные алгоритмы: теория и практика. Мир, 1980.
2. Т.Кормен, Ч.Лейзерсон, Р.Ривест. Алгоритмы: построение и анализ. МЦНМО, Москва, 2000.
3. Ч.Хоар. Взаимодействующие последовательные процессы. Мир, 1989.
4. Комбинаторный анализ. Задачи и упражнения. Под ред. Рыбникова. - М.: Наука, 1982. - 368 с.
5. И.А. Лавров, Л.Л. Максимова. Задачи по теории множеств, математической логике и теории алгоритмов. - М.: ФИЗМАТЛИТ, 2001. - 256 с.
6. Андерсон Дж. Дискретная математика и комбинаторика. Изд-во Вильямс, 2004 г.
7. Малышкин В.Э., Корнеев В.Д. Параллельное программирование мультикомпьютеров. Изд-во НГТУ, 2006 г.

Параллельные вычислительные методы

Доступны для скачивания следующие материалы:

• Методичка по лабораторным работам

Прочие материалы

• Описание функций MPI
• Описание замера времени

Архитектура ЭВМ и ВС

Доступны для скачивания следующие материалы:

Вопросы по курсу

• Вопросы по курсу (2010 год)

Задания к лабораторным работам

• Описание заданий для лабораторных работ

Результаты лабораторных работ

• ПМ-01
• ПМ-02
• ПМ-03
• ПМ-04
• ПМИ-01
• ПМИ-02

  Дополнительные материалы

• Архитектура современных ЭВМ
• Представление чисел. Использование SIMD-расширений x86.Функции замера времени.
• Организация памяти
• Виртуальная память
• Оптимизация программ
• Конвейерные вычисления
• Описание RISC-процессров
• Набор инструкций
• Архитектуры P6-P8
• Суперскалярный процессор
• EPIC
• Примеры суперскаляров
• Современные процессоры
• Тенденции развития современных микропроцессоров

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

Вопросы к экзамену

Куликов И.М.

1. Назначение библиотек AMD Core Math Library и Intel Math Kernel Library. Структура библиотек, основные функции.
2. Матрично-векторные операции в Intel MKL. Оптимизация матрично-векторных операций: последовательный обход памяти, использование кэша данных при работе с векторами, оптимизация работы циклов.
3. Возможности библиотеки Intel MKL для решения разреженных СЛАУ, полученных в результате конечно-объёмных аппроксимаций.

Городничев М.А.

1. Динамические свойства параллельных программ, необходимость динамических свойств.
2. Представление задачи в виде графа. Планирование распределения вычислительной загрузки с помощью разбиения графа задачи. Задача оптимизации разбиения.
3. Методы разбиения графов. Сравнение геометрических методов и методов, основанных на теории графов.

Корнеев В.Д.

1. Модель параллелизма в языке HPF (DVM).
2. Семантика директивы задания массива процессоров (пример).
3. Семантика директив отображения данных на массив процессоров (простой пример).
4. Семантика директив параллельных циклов (пример).

Малышкин Н.В.

1. Определение Grid, отличие от мультикомпьютера. Зачем необходимо строить Grid. Перечислить несколько известных grid проектов и их основные цели и идеи.
2. Описание задачи для запуска Grid. Общая идея.
3. Основные проблемы программирования для неоднородных Grid.
4. Построение Grid систем. Требования к Grid системам, основные компоненты, структура. Сформулируйте основные проектные решения по конструированию Grid системы.
5. Как оценивается производительность Grid системы? Как замеряется производительность Grid системы.
6. Утилиты для запуска/удаления/управления задачами в Globus Toolkit. Чем управление задачами в Grid отличается управления задачами в ОС?

Динамические свойства параллельных программ (Городничев М.А.)

Лекция №1. Динамические свойства. Задача статического распределения вычислительной загрузки.

Лекция №2. Динамическая балансировка вычислительной загрузки.

Лабораторная работа №1. Программный пакет ParMETIS для параллельного разбиения графов и переупорядочивания разреженных матриц.

Цель работы:
Познакомиться с библиотекой ParMETIS --- одним из средств параллельного разбиения графов, которое может служить как инструмент для планирования распределения вычислений в параллельных программах.
Порядок выполнения работы:

1. Получить дистрибутив библиотеки ParMETIS у преподавателя, здесь, или в ином месте.
2. Установить библиотеку согласно инструкции (файл INSTALL в корневом каталоге дистрибутива).
   Краткий перевод инструкции на русский язык:
   
   • В файле Makefile.in в корневой директории дистрибутива установить значение переменной CC равным имени команды для компиляции программ MPI. По умолчанию стоит mpicc, должно в большинстве случаев работать. Проверить и исправить в случае необходимости значения других переменных, в частности LD должна указывать на правильный редактор связей (линковщик).
   • В корневой директории дистрибутива запустить команду make. В результате будут получены файлы библиотеки ParMETIS: libmetis.a и libparmetis.a.
3. Далее, есть 2 варианта выполнения лабораторной работы. Студент произвольно выбирает из них один. Подробное руководство по применению ParMETIS находится в каталоге Manual.
   • Вариант 1. Необходимо разобраться с устройством тестовой программы ptest.с (каталог Programs в дистрибутиве), осуществить запуск этой программы с помощью средства для запуска программ MPI (обычно mpirun, mpiexec или run.sh на кластере ФПМИ НГТУ) и проанализировать результатов.. Исполняемый код программы должен быть в файле ptest в каталоге Graphs после успешного выполнения вышеупомянутой команды make. Нужно обратить внимание на то, что ptest требует параметра: название файла с описанием графа. Для тестов могут использоваться в этом качестве файлы bricks.hex3d, rotor.graph из каталога Graphs. Например: "mpirun -np 4 ptest rotor.graph".
     Файл rotor.graph.xyz служит для тестировании функций разбиения, использующих информацию о координатах. Способ его применения нужно установить самостоятельно. Разбирать программу нужно не всю, а только в той части, где тестируются функции ParMETIS_V3_PartKway(), ParMETIS_V3_PartGeomKway, ParMETIS_V3_PartGeom.
   • Вариант 2. Написать свою программу для тестирования тех же трех функций, что и в первом варианте: ParMETIS_V3_PartKway(), ParMETIS_V3_PartGeomKway, ParMETIS_V3_PartGeom.

Лабораторная работа №2. Обеспечение надежности распределенных вычислений.

• имеется сервер, осуществляющий управление вычислениями, и клиенты, выполняющие вычисления по заданию сервера;
• вся задача вычислений заключается в том, что должен быть выполнен ряд независимых заданий;
• список заданий, и сами задания находятся на сервере;
• сервер считается надежным;
• взаимодействие сервера с клиентами осуществляется одним из двух способов (продумать либо первый, либо второй):
  1. клиент подключается к серверу, берет у него задание,отключается, когда результат готов, подключается к серверу и отдает результат;при этом в любой момент времени с клиентом может случиться неприятность, сервер же должен контролировать выполнение заданий и в случае необходимости обеспечить переназначение задания другому клиенту;
  2. клиент подключается к серверу и сохраняет с ним постоянную связь до некоторого момента времени (выключение, поломка клиента); в то время, пока сохраняется связь, возможно общение между сервером и клиентом по инициативе обеих сторон;подключившись, клиент получает задание от сервера, возвращает результат, и повторяет это итеративно; клиент можен погибнуть в любой момент; клиент, потерявший связь с сервером, в случае повторного подкючения к серверу считается новым клиентом;

Литература и сайты:

1. Y. F. Hu and R. J. Blake. Load Balancing for Unstructured Mesh
2. Hu, Y.F., Blake, R.J.: An improved diffusion algorithm for dynamic load balancing, Parallel Computing 25, 1999, pp. 417--444.
3. K.Barker, N. Chrisochoides. An evaluation of a framework for the dynamic load balancing of highly adaptive and irregular parallel applications. In proceedings of SC2003, November, Phoenix, Arizona, USA.
4. Johan Steensland, Stefan Soederberg, Michael Thune, Comparison of dynamic load balancing techniques for a parallel SAMR algorithm, in Proceedings of PARA2000, Workshop on Applied Parallel Computing, volume 1947 of LNCS. Springer Verlag.
5. M. Bhandarkar, R.Brunner, L.Kale. Run-time Support for Adaptive Load Balancing.
6. М.А.Корнилина, М.В.Якобовский. Динамическая балансировка загрузки процессоров при моделировании задач горения. Материалы конференции "Высокопроизводительные вычисления и их приложения", 30 октября – 2 ноября 2000 года, Черноголовка.
7. PARTY Partitioning Library.
8. ParMETIS - Parallel Graph Partitioning and Fill-reducing Matrix Ordering.