Участник:StasFomin/Innopolis/Wtf — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 3: Строка 3:
 
= Эффективные алгоритмы для труднорешаемых задач =
 
= Эффективные алгоритмы для труднорешаемых задач =
 
: '''Квалификация выпускника''': бакалавр
 
: '''Квалификация выпускника''': бакалавр
−
: '''Направление подготовки''':  09.03.01 - “Информатика и вычислительная техника”
+
: '''Направление подготовки''':  Направление 01.04.02 «Прикладная математика и информатика».
−
: '''Направленность (профиль) образовательной программы''': Математические основы ИИ
+
: '''Направленность (профиль) образовательной программы''': «Системное программирование и компьютерные науки». Образовательная программа «Вычислительная математика».
 
: '''Программу разработал(а)''': Фомин С.А.
 
: '''Программу разработал(а)''': Фомин С.А.
  
Строка 20: Строка 20:
 
   
 
   
 
== 2. Перечень планируемых результатов обучения ==
 
== 2. Перечень планируемых результатов обучения ==
−
: '''Целью освоения дисциплины''' является формирование общего понимания высокоэффективной реализации общих вычислительных алгоритмов с использованием процессоров различных типов и архитектур, а также демонстрация современных подходов к вычислительным алгоритмам на базе технологий машинного обучения.
+
: '''Целью освоения дисциплины''' является формирование общего понимания высокоэффективной реализации  
 +
 
 +
 
 +
общих вычислительных алгоритмов с использованием процессоров различных типов и архитектур, а также демонстрация современных подходов к вычислительным алгоритмам на базе технологий машинного обучения.
  
 
: '''Задачами дисциплины''' являются изучение технологий параллельного программирования на центральных, графических и нейропроцессорах, анализ вычислительных алгоритмов с целью выявления точек параллелизма (hotpoints) и узких мест (bottle necks), а также внедрение технологий искусственного интеллекта и нейронных сетей в классические вычислительные задачи.
 
: '''Задачами дисциплины''' являются изучение технологий параллельного программирования на центральных, графических и нейропроцессорах, анализ вычислительных алгоритмов с целью выявления точек параллелизма (hotpoints) и узких мест (bottle necks), а также внедрение технологий искусственного интеллекта и нейронных сетей в классические вычислительные задачи.

Версия 14:47, 30 марта 2024

https://eduwiki.innopolis.university/index.php/BSc:_EfficientAlgorithms

Эффективные алгоритмы для труднорешаемых задач

Квалификация выпускника: бакалавр
Направление подготовки: Направление 01.04.02 «Прикладная математика и информатика».
Направленность (профиль) образовательной программы: «Системное программирование и компьютерные науки». Образовательная программа «Вычислительная математика».
Программу разработал(а): Фомин С.А.

1. Краткая характеристика дисциплины

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

  • Теорию сложности, для определения
    • классов задач допускающих эффективное решение детерминированными и вероятностными алгоритмами — классы P, RP, ZPP, BPP и т.п.
    • классов задач, для которых считается невозможным существование эффективных алгоритмов точного решения — NP-complete, PSPACE-complete.
    • классов задач, для которых считается невозможным существование эффективных алгоритмов поиска приближенного решения — APX-complete.
  • Классические алгоритмы решения задач на графах и множествах (кратчайшие пути, покрытия, сортировки)
  • Алгоритмы, подходы и эвристики, для решения NP-полных задач:
    • приближенные алгоритмы с гарантированной точностью, включая алгоритмы с любой, заранее выбранной точностью — PTAS, FPTAS.
    • вероятностные алгоритмы, и эвристики их порождения — методы Монте-Карло, вероятностного округления и т.п.
    • методы дерандомизации — получения детерминированных приближенных алгоритмов из вероятностных.

2. Перечень планируемых результатов обучения

Целью освоения дисциплины является формирование общего понимания высокоэффективной реализации


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

Задачами дисциплины являются изучение технологий параллельного программирования на центральных, графических и нейропроцессорах, анализ вычислительных алгоритмов с целью выявления точек параллелизма (hotpoints) и узких мест (bottle necks), а также внедрение технологий искусственного интеллекта и нейронных сетей в классические вычислительные задачи.

Общая характеристика результата обучения по дисциплине

Знания:
  • подходов к параллельному программированию,
  • архитектур современных процессоров,
  • программных моделей с общей памятью,
  • архитектуры современных графических процессоров,
  • основ выполнения вычислений общего назначения на разных платформах,
  • современных подходов к программированию алгоритмов решения задач математики и физики.
Умения:
  • SIMD- и MIMD-программирование для CPU,
  • SIMD-программирование для GPU,
  • выполнять синхронизацию потоков,
  • выполнять оптимизация общей памяти.
Навыки (владения):
  • проведения анализ алгоритмов на предмет возможного параллелизма с выявлением "горячих точек" и "бутылочных горлышек",
  • применения современного параллельного программирования к методам статистики,
  • решения систем алгебраических уравнений наиболее эффективным способом,
  • решения основных типов дифференциальных уравнений, встречающихся в широком спектре реальных задач,
  • применения современных вычислительных алгоритмов на основе машинного обучения для решения различных типов дифференциальных уравнений.

3. Структура и содержание дисциплины

№
п/п 		Наименование раздела
дисциплины 		Содержание дисциплины по темам
1. Введение в высокопроизводительные вычисления, OpenMP и OpenCL - Существующие суперкомпьютерные системы
- Модель общей памяти
- Подходы к программированию MIMD и SIMD
- Массивно-параллельные ускорители
- Иерархия памяти
2. Параллельные алгоритмы линейной алгебры - Матричное умножение: оптимизация производительности различных реализаций на основе различных типов памяти устройства
- Прямые методы решения СЛАУ: исключение Гаусса, разложение Холецкого, метод прогонки, параллельная реализация
- Итерационные методы решения СЛАУ: метод Якоби, метод Зейделя, релаксационные методы, параллельная реализация
3. Параллельные методы решения дифференциальных уравнений - Решение систем обыкновенных дифференциальных уравнений
- Решение волнового уравнения
- Решение задачи теплопроводности
- Решение задачи Дирихле для уравнения Пуассона
4. Физически информированные нейронные сети - Основы нейронных сетей
- Основы методов оптимизации
- Принципы преобразования задач, записанных в терминах дифференциальных уравнений, в оптимизационные
- Повышение эффективности процедуры обучения
5. Параллельные методы Монте-Карло - Вычисление определенных интегралов
- Способы уменьшения дисперсии
- Генераторы псевдослучайных чисел
- Подходы к распараллеливанию методов Монте-Карло
6. Высокопроизводительные вычисления и современные языки программирования - Многопоточность в современных языках программирования
- Существующие обертки для OpenCL и CUDA
- Другие высокоуровневые подходы к параллельному программированию

4. Методические и оценочные материалы

Задания для практических занятий:

№
п/п 		Наименование раздела
дисциплины (модуля) 		Перечень рассматриваемых тем (вопросов)
1. Введение в высокопроизводительные вычисления, OpenMP и OpenCL 1) Напишите программу, которая получает ID потока, печатает на консоли "Привет из потока #", печатает общее количество потоков из главного потока. Введите необходимые переменные локально, а затем сделайте их глобальными. Протестируйте программу. Используйте необходимые пункты для решения возникших проблем.
2) Напишите программу, которая хранит 3 массива фиксированной длины, инициализирует элементы массивов их индексами, печатает общее количество потоков из главного потока, суммирует элементы двух первых массивов и записывает их в третий, а также печатает результат из текущего потока. Запустите задачу в параллельной секции и с помощью параллельного цикла. Протестируйте программу. Попробуйте использовать параллельный цикл с параллельной секцией и без нее. Попробуйте измерить время вычислений.
3) Напишите программу, которая вычисляет определенный интеграл заданной функции на заданном интервале (с использованием метода трапеций). Протестируйте программу. Измерьте время вычисления.
2. Параллельные алгоритмы линейной алгебры 1) Реализуйте матрично-векторное умножение в OpenMP и OpenCL. Обсудите различные технологии хранения данных.
2)Выполните матричное умножение, попробуйте оптимизацию.
3) Реализуйте методы развертки и редукции для полосато-матричного СЛАУ. Использование инструментария OpenMP и OpenCL для распараллеливания.
4) Решите СЛАУ с помощью итерационного алгоритма. Реализуйте решение с помощью подходов OpenMP и OpenCL.
3. Параллельные методы решения дифференциальных уравнений 1) Реализуйте решение задачи распространения тепла с ленточной матрицей с помощью прямых методов.
2) Реализуйте решение задачи распространения тепла с ленточной матрицей с использованием итерационных методов.
3) Сравните вычислительную производительность реализаций на CPU и GPU.
4) Реализуйте визуализацию вычислительных экспериментов.
5) Напишите компьютерную программу, которая решает систему ОДУ, продумайте способы распараллеливания решения.
4. Физически информированные нейронные сети 1) Напишите компьютерную программу, которая решает обыкновенное дифференциальное уравнение с помощью классических численных алгоритмов.
2) Напишите компьютерную программу, реализующую физически информированную нейронную сеть для решения обыкновенного дифференциального уравнения.
3) Заранее реализуйте процедуру сравнения. Протестируйте решение на различных уравнениях. Сделайте вывод о сходимости алгоритма и о процедуре обучения.
4) Реализуйте параллельную версию алгоритма. Сравните вычислительную производительность.
5. Параллельные методы Монте-Карло 1) Реализуйте вычисление определенных интегралов с помощью классических квадратурных формул. Сравните погрешность вычислений с помощью метода Монте-Карло. Сравните время работы обоих подходов для достижения одинаковой точности.
2) Реализуйте технику уменьшения дисперсии для метода Монте-Карло. Проведите эксперименты, подтверждающие эффективность реализации.
3) Реализуйте генератор равномерного распределения. Проведите эксперименты по оценке корректности и производительности генератора.
4) Реализуйте генератор нормального распределения. Проведите эксперименты по оценке корректности и эффективности работы генератора.
6. Высокопроизводительные вычисления и современные языки программирования Нет.

Текущий контроль успеваемости обучающихся по дисциплине:

№
п/п 		Наименование раздела
дисциплины 		Форма текущего контроля
 Материалы текущего контроля
1. Введение в высокопроизводительные вычисления, OpenMP и OpenCL Проверка выполнения домашних заданий;
Тестирование (письменное или компьютерное) 		Тестирование (письменное или компьютерное)

- Как включить поддержку OpenMP в проекте?
- Как определить, поддерживает ли GPU OpenCL или нет?
- Как собрать информацию о CPU?
- Как собрать информацию о GPU?
- Как выполнять код параллельно с использованием OpenMP?
- Как выполнять код параллельно на GPU?

2. Параллельные алгоритмы линейной алгебры Проверка выполнения домашних заданий;
Тестирование (письменное или компьютерное);
Проверка разработки отдельных частей кода программного продукта 		Тестирование (письменное или компьютерное):

- Что такое разреженные матрицы?
- Опишите особенности умножения разреженных матриц
- Объясните прямой и обратный путь разложения Гаусса
- Как составить схему решения метода прогонки?
- Как организовать итерации для приближенного решения СЛАУ?
- Как понять, нужно ли останавливать итерационный процесс или нет?
- Как оптимизировать алгоритмы умножения матриц с точки зрения затрат памяти и времени?

3. Параллельные методы решения дифференциальных уравнений Проверка выполнения домашних заданий;
Тестирование (письменное или компьютерное);
Проверка разработки отдельных частей кода программного продукта 		Тестирование (письменное или компьютерное):

- Что такое волновое уравнение?
- Что такое уравнение теплопроводности?
- Как задача теплопроводности связана с задачей диффузии?
- Как описать такие задачи с помощью дифференциальных уравнений?
- Что такое "преобразование" с точки зрения математики?
- Какие типы преобразований вы знаете для решения дифференциальных уравнений?
- Как численно решать системы обыкновенных дифференциальных уравнений?

4. Физически информированные нейронные сети Проверка выполнения домашних заданий;
Тестирование (письменное или компьютерное);
Проверка разработки отдельных частей кода программного продукта 		Тестирование (письменное или компьютерное):

- Что такое нейронная сеть?
- Какова структура однослойного и многослойного перцептрона?
- Как переформулировать задачу Коши с начальным значением в терминах задачи оптимизации?
- Как оценить погрешность алгоритма PINN?
- В чем плюсы и минусы подхода PINN по сравнению с классическими численными методами?
- Как ускорить процедуру обучения с помощью параллельного программирования?

5. Параллельные методы Монте-Карло Проверка выполнения домашних заданий;
Тестирование (письменное или компьютерное);
Проверка разработки отдельных частей кода программного продукта 		Тестирование (письменное или компьютерное):

- Что такое определенный интеграл?
- Каковы классические формулы квадратур?
- Что такое равномерное распределение?
- Что такое нормальное распределение?
- Как использовать распределения при построении генераторов случайных величин?
- Как использовать статистический подход для оценки определенного интеграла?
- Как вычислить число Пи с помощью метода Монте-Карло?

6. Высокопроизводительные вычисления и современные языки программирования Проверка выполнения домашних заданий;
Устный опрос;
Доклад 		Темы докладов:

- Обзор Nvidia CUDA
- Обзор OpenACC
- C# и многопоточное программирование (Task Parallel Library)
- C# и программирование графических процессоров Nvidia CUDA (AleaGPU и альтернативы)
-C# и программирование на GPU OpenCL (Cudafy.NET, или Cloo.NET и альтернативные варианты)
- Java и многопоточное программирование
- Программирование на Java и Nvidia CUDA GPU
- Программирование на Java и OpenCL GPU
- Python и многопоточное программирование
- Обзор программирования на Python и GPU
- Swift и многопоточное программирование
- Swift и программирование на GPU
- Go и многопоточное программирование
- Go и программирование на GPU
- Rust и многопоточное программирование и программирование на GPU
- Erlang и многопоточное программирование

Контрольные вопросы для подготовки к промежуточной аттестации:

№
п/п 		Наименование
раздела дисциплины 		Вопросы
1. Введение в высокопроизводительные вычисления, OpenMP и OpenCL 1) OpenMP: подпрограммы библиотеки времени выполнения, переменные окружения
2) Директивы компилятора OpenMP: секции parallel
3) Директивы компилятора OpenMP: синхронизация
4) OpenCL: платформа и модели выполнения
5) OpenCL: модель памяти
2. Параллельные алгоритмы линейной алгебры 1) Матричная алгебра: разреженные матрицы
2) СЛАУ: устранение гаусса
3) СЛАУ: разложение Холецкого
4) СЛАУ: методы прогонки
5) СЛАУ: итерационные методы
3. Параллельные методы решения дифференциальных уравнений 1) Волновые уравнения
2) Сеточные методы
3) Задача теплопроводности
4) Задача Дирихле для уравнения Пуассона
5) Системы обыкновенных дифференциальных уравнений и соответствующие решения
4. Физически информированные нейронные сети 1) Физически обоснованные нейронные сети
2) PINN для решения обыкновенных дифференциальных уравнений
3) PINN и системы обыкновенных дифференциальных уравнений
4) PINN и частичные дифференциальные уравнения
5. Параллельные методы Монте-Карло 1) Математический анализ: определенные интегралы и методы их вычислений
2) Статистика: свойства случайной величины
3) Статистика: равномерное распределение
4) Статистика: нормальное распределение
5) Метод Монте-Карло
6. Высокопроизводительные вычисления и современные языки программирования 1) Модель программирования Nvidia CUDA
2) Модель памяти Nvidia CUDA
3) Модель программирования OpenACC

Вопросы/Задания к промежуточной аттестации в устной/письменной форме:

  1. Что такое закон Амдала?
  2. Перечислите особенности #pragma parallel
  3. Какие типы модификаторов доступа к памяти вы знаете?
  4. Сравните секции parallel и задачи OpenMP
  5. Как синхронизировать потоки в OpenMP?
  6. Опишите структуру программы OpenCL
  7. Какие виды памяти в OpenCL вы знаете?
  8. Что такое ядра OpenCL?
  9. Перечислите сервисные операции OpenCL
  10. Как вычислить определенный интеграл?
  11. Что такое случайная переменная?
  12. Что такое генератор случайных величин?
  13. Как построить генератор случайных величин?
  14. Как работают методы Монте-Карло?
  15. Как выполнить умножение разреженных матриц?
  16. Перечислите прямые методы решения СЛАУ
  17. В чем разница между устранением Гаусса и разложением Холецкого?
  18. Объясните итерационный алгоритм решения СЛАУ на графе
  19. Как ускорить алгоритмы линейной алгебры с помощью многопоточного программирования?
  20. Как задать граничные условия для дифференциальных уравнений с частными производными?
  21. Как задать начальные условия для дифференциальных уравнений с частными производными?
  22. В чем разница между явными и неявными конечно-разностными схемами?
  23. Перечислите возможные способы решения задачи о распространении тепла в пластине.
  24. Переформулируйте поставленную задачу Коши в оптимизационную задачу.
  25. Что такое PINN-подход к дифференциальным уравнениям?
  26. Перечислите известные оптимизаторы и их особенности.
  27. Как избежать влияния начального условия на значение, выдаваемое нейронной сетью?
  28. Что делать с начальным распределением функции в задаче PDE, формулируя задачу оптимизации?
  29. Что делать с граничными условиями в PDE-задаче при формулировке задачи оптимизации?
  30. Как решить систему ODE с помощью PINN-подхода?
  31. Сравните Nvidia CUDA и OpenCL. В чем плюсы и минусы обоих наборов инструментов?
  32. Сравнение библиотек OpenACC и OpenMP: основные различия и цели другого подхода
  33. C#: библиотека параллельных задач
  34. Java: Runnable
  35. Python: модуль потоков

Перечень учебно-методического обеспечения дисциплины

Список основной литературы:

  1. Barbara Chapman, Gabriele Jost, Ruud van der Pas. (2008) Using OpenMP: Portable Shared Memory Parallel Programming, The MIT Press,
  2. Scarpino, M. (2011) OpenCL in Action: How to Accelerate Graphics and Computations, Manning.
  3. Banger, R., Bhattacharyya, K. (2013) OpenCL Programming by Example, Packt Publishing.
  4. Sanders, J., Kandrot, E. (2010) CUDA by example: an introduction to general-purpose GPU programming, Addison-Weslye

Список дополнительной литературы:

  1. Введение в высокопроизводительные вычисления: introduction-high-performance-computing
  2. Введение в параллельное программирование: introduction-parallel-programming
  3. Учебные материалы по OpenMP: OpenMP-tutorials
  4. Учебные материалы по OpenCL: OpenCL-tutorials

Необходимое программное обеспечение:

  1. Microsoft VS Code / Microsoft Visual Studio / любая другая подходящая среда разработки на языке C++
  2. GNU Plot
  3. OpenMP, OpenCL, CUDA библиотеки

Методические указания для обучающихся по освоению дисциплины

Вид учебных
занятий/деятельности 		Деятельность обучающегося
Лекция Написание конспекта лекций: кратко, схематично, последовательно фиксировать основные положения лекции, выводы, формулировки, обобщения; помечать важные мысли, выделять ключевые слова, термины. Обозначить вопросы, термины или другой материал, который вызывает трудности, пометить и попытаться найти ответ в рекомендуемой литературе. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия.
Практические (лабораторные) занятия Практические занятия предназначены прежде всего для разбора отдельных сложных положений, тренировки аналитических навыков, а также для развития коммуникационных навыков. Поэтому на практических занятиях необходимо участвовать в тех формах обсуждения материала, которые предлагает преподаватель: отвечать на вопросы преподавателя, дополнять ответы других студентов, приводить примеры, задавать вопросы другим выступающим, обсуждать вопросы и выполнять задания в группах. Работа на практических занятиях подразумевает домашнюю подготовку и активную умственную работу на самом занятии. Работа на практических занятиях в форме устного опроса заключается прежде всего в тренировке навыков применять теоретические положения к самому разнообразному материалу. В ходе практических занятий студенты работают в группах для обсуждения предлагаемых вопросов.
Самостоятельная работа Самостоятельная работа состоит из следующих частей: 1) чтение учебной, справочной, научной литературы; 2) повторение материала лекций; 3) составление планов устных выступлений; 4) подготовка презентаций. При чтении учебной литературы нужно разграничивать для себя материал на отдельные проблемы, концепции, идеи. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис.
Доклад Публичное, развернутое сообщение по определенной теме или вопросу, основанное на документальных данных. При подготовке доклада рекомендуется использовать разнообразные источники, позволяющие глубже разобраться в теме. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис.
Дискуссия Публичное обсуждение спорного вопроса, проблемы. Каждая сторона должна оппонировать мнение собеседника, аргументируя свою позицию.
Разработка отдельных частей кода Разработать часть кода, исходя из поставленной задачи и рекомендаций преподавателя. При выполнении работы рекомендуется обращаться к материалам лекций и семинарских (практических) занятий. Если возникают затруднения, необходимо проконсультироваться с преподавателем.
Выполнение домашних заданий и групповых проектов Для выполнения домашних заданий и групповых проектов необходимо получить формулировку задания от преподавателя и убедиться в понимании задания. При выполнение домашних заданий и групповых проектов необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме.
Индивидуальная работа При выполнение индивидуальной работы необходимо взять задание у преподавателя, ознакомиться с требованиями к выполнению работы, изучить поставленную проблему, найти решение проблемы. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия. Оформить результаты работы.
Тестирование (устное/письменное) При подготовке к тестированию необходимо проработать материалы лекций, семинаров, основной и дополнительной литературы по заданной теме. Основная цель тестирования – показать уровень сформированности знаний по конкретной теме или ее части.

Методы и технологии обучения, способствующие формированию компетенции

Методы и технологии обучения, способствующие формированию компетенции
Информационно-коммуникационная технология, проектная технология, технология проблемного обучения, кейс-технология, традиционные технологии, модульные технологии
Источник — «https://discopal.ispras.ru/index.php?title=Участник:StasFomin/Innopolis/Wtf&oldid=28736»