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

Кафедра информатики и автоматизации научных исследований

Специальность: Прикладная информатика в области принятия решений

Преподаватель: Афраймович Л.Г.

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

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

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

В результате освоения дисциплины «Модели и методы эффективного использования распределенных вычислительных систем» обучающийся должен:

Знать основы моделей и методов эффективного использования распределенных вычислительных систем.

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

Владеть навыками построения моделей методов решения оптимизационных задач эффективного использования распределенных вычислительных систем.

Содержание

Введение в предметную область. Математические модели вычислительных систем (элементы системы, каналы связи, топология системы). Математические модели алгоритмов (элементарные операции алгоритмов, зависимости по данным и выполнению). Задача балансировки с произвольной декомпозицией. Поиска оптимального сбалансированного потока. Построение расписания при реализации сбалансированного потока. Балансировка с регулярной декомпозицией. Эвристический метод решения основанный на декомпозиции на одномерные задачи. Задача минимизации циклов обменов параллельных процессов. Сведение к задаче о раскраске графа. Задача отображения графа коммуникаций процессов на граф топологии вычислительной системы. Сведение к квадратичной задаче о назначениях. Задача выполнения совокупности взаимозависимых задач на параллельных процессорах. Фронтальный метод решения. Задача выполнения независимых задач на параллельных процессорах. Выполнение в пакетном режиме. Применение метода генерации столбцов.

Литература

а) основная литература

  1. Афраймович Л.Г. Учебно-методическое пособие по курсу «Модели и методы эффективного  использования  распределенных вычислительных систем» при изучении темы «Задачи статической балансировки». Учебно-методическое пособие. – Нижний Новгород: Нижегородский госуниверситет, 2011, 13 С. http://www.unn.ru/books/met_files/StatB.pdf
  1. Афраймович Л.Г. Потоковые алгоритмы исследования совместности иерархических систем распределения ресурсов с ограничениями // Вестник Нижегородского государственного университета. Математическое моделирование и оптимальное управление. 2006. 2(31). – С. 129-138.
  2. Афраймович Л.Г., Прилуцкий М.Х. Многоиндексные задачи распределения ресурсов в иерархических системах // Автоматика и телемеханика. 2006. №6. – C. 194-205.
  3. Афраймович Л.Г., Прилуцкий М.Х. Распределение ресурсов в иерархических системах транспортного типа. Учебно-методический материал по программе повышения квалификации «Новые подходы в исследованиях и разработках информационно-телекоммуникационных систем и технологий». Нижний Новгород, 2007, 78 с.
  4. Прилуцкий М. Х., Кумагина Е. А Управляемый фронтальный алгоритм решения задачи распределения ресурсов в сетевых канонических структурах // Вестник Нижегородского университета им. Н. И. Лобачевского. № 6 -Н. Новгород: Изд-во ННГУ, 2008. с. 126—129.
  5. Прилуцкий М.Х. Многокритериальное распределение однородного ресурса в иерархических системах // Автоматика и телемеханика. 1996. №2. – С. 24-29.
  6. Deikmann R., Frommer A., Monien B. Efficient schemes for nearest neighbor load balancing // Parallel Computing. 25. 1999. – P. 789-812.
  7. Isanders P. On the Efficiency of Nearest Neighbor Load Balancing for Random Load // Proc. Parcella ’96: Parallel Processing by Cellular Automata and Arrays. 1996. – P. 120-127.
  8. Lucking T., Monien B., Rode M. On the Problem of Scheduling Flows on Distributed Networks // Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science. 2002. – P. 495-505.

 б) дополнительная литература

  1. Афраймович Л. Г., Прилуцкий М. Х. Многопродуктовые потоки в древовидных сетях // Известия РАН. Теория и системы управления. 2008. №.2. – С. 57-63.
  2. Афраймович Л.Г., Прилуцкий М.Х. Поиск потока в несовместных транспортных сетях // Управление большими системами. Выпуск М.: ИПУ РАН. 2009. С.147-168.
  3. Прилуцкий М.Х. Распределение однородного ресурса в иерархических системах древовидной структуры // Труды международной конференции «Идентификация систем и задачи управления SICPRO’2000». – М.: Институт проблем управления им. В.А. Трапезникова РАН. 2000. – С. 2038-2049.
  4. Прилуцкий М. Х. Многокритериальные многоиндексные задачи объёмно- календарного планирования // Известия РАН. Теория и системы управления. 2007. № 1. – С. 78-82.
  5. Brucker P., Jurisch B., Krämer A. Complexity of scheduling problems with multi-purpose machines // Annals of Operations Research. V. 70. 1997. – P. 57- 73.
  6. Gairing M., Lucking T., Mavronicolas M., Monien B. Computing Nash Equilibria for Scheduling on Restricted Parallel Links // Proc. 36th Annual ACM Sympos. Theory Comput. 2004. – P. 613-622.
  7. Zsuzsanna M. On scheduling problems with parallel multi-purpose machines // TR-2005-02. 2005.

Отчетность

  • Семестр 1: Зач