Опубликован: 18.01.2010 | Уровень: специалист | Доступ: платный | ВУЗ: Московский государственный технологический университет «Станкин»
Введение в параллельные алгоритмы Рассматриваются параллельные алгоритмы и методы решения задач различных классов на многопроцессорных вычислительных системах. Рассматриваются факторы, влияющие на время выполнения параллельных программ и на эффективность использования вычислительной мощности многопроцессорных систем.
Рассматриваются параллельные алгоритмы решения задач различных классов. Курс содержит следующие учебные разделы: cредства описания параллельных алгоритмов; методы построения параллельных алгоритмов; параллельные алгоритмы сортировки данных; параллельные алгоритмы генерации псевдослучайных чисел; динамическая балансировка загрузки процессоров на примере параллельных алгоритмов интегрирования функций; параллельные алгоритмы решения систем линейных уравнений специального вида.
Цель: Цель курса состоит в изучении основных методов создания параллельных алгоритмов и программ для многопроцессорных систем.
Необходимые знания: При изложении учебного материала курса у обучаемых предполагается наличие начальных знаний в области программирования и общее представление о видах многопроцессорных систем. Для выполнения практических заданий необходимы начальные навыки составления и запуска простых параллельных программ.

План занятий

ЗанятиеЗаголовок <<Дата изучения
-
Лекция 1
Введение
Во введении дается общее представление об учебном курсе. Рассматриваются задачи, решаемые на многопроцессорных системах. Обсуждаются требования к алгоритмам для суперкомпьютеров. Рассматривается содержание учебного курса и обсуждаются навыки, необходимые для его успешного освоения. Обсуждение конечного автомата "жизнь". В завершении лекции указывается учебно-методическая литература, которая может быть полезна при изучении курса.
Оглавление
    -
    Лекция 2
    Основные понятия
    Рассматриваются следующие понятия: многопроцессорные системы с общей и с распределенной памятью; канал передачи данных и его свойства; синхронная и асинхронная передача данных; семафоры и операции над ними. Обсуждаются понятия ускорения и эффективности параллельных алгоритмов, свойство внутреннего параллелизма алгоритма. Приводится пример алгоритма, обладающего низкой эффективностью, но высоким быстродействием (нахождение суммы конечного ряда).
    Оглавление
      -
      Тест 1
      15 минут
      -
      Лекция 3
      Методы построения параллельных алгоритмов. Часть 1
      Рассматриваются простые методы построения параллельных алгоритмов, в том числе методы: геометрического параллелизма, конвейерного параллелизма, коллективного решения. Рассматриваются их свойства. Обсуждаются проблемы статической и динамической балансировки загрузки процессоров. Рассматривается алгоритм диффузной балансировки загрузки. Приводится пример задачи, для сокращения времени решения которой необходимо создание нового алгоритма (сложение длинных чисел).
      Оглавление
        -
        Тест 2
        18 минут
        -
        Лекция 4
        Методы построения параллельных алгоритмов. Часть 2
        Построение эталонного последовательного алгоритма сортировки. Описание "плохого" последовательного, но быстрого параллельного метода сортировки. Оценка времени выполнения алгоритма в наилучшем, среднем и наихудшем случае. Зависимость времени сортировки от вида исходной последовательности.
        Оглавление
          -
          Тест 3
          15 минут
          -
          Лекция 5
          Сортировка данных с точки зрения МВС. Часть 1
          Рассмотрение минимальных сетей сортировки, сети четно-нечетное слияния. Построение на основе сетей сортировки параллельного алгоритма сортировки данных. Определение его характеристик при реализации на системах с общей и с распределенной памятью. Оценка времени выполнения сортировки. Оценка необходимого объема оперативной памяти. Обсуждение возможности сокращения объема передаваемых данных и требуемой оперативной памяти.
          Оглавление
            -
            Тест 4
            15 минут
            -
            Лекция 6
            -
            Тест 5
            18 минут
            -
            Лекция 7
            Решение систем линейных уравнений и диффузная балансировка нагрузки процессоров
            Задачи, приводящие к появлению систем линейных уравнений (СЛАУ) с трехдиагональной матрицей коэффициентов. Параллельные алгоритмы решения трехдиагональных СЛАУ. Итерационные методы.
            Оглавление
              -
              Тест 6
              15 минут
              -
              Лекция 8
              Последовательности псевдослучайных чисел для многопроцессорных вычислительных систем
              Задачи, решаемые с использованием последовательностей псевдослучайных чисел (ПСЧ). Параллельные алгоритмы решения таких задач. Требования к генераторам ПСЧ для многопроцессорных систем. Параллельные алгоритмы генерации ПСЧ. Тестирование полученных последовательностей.
              Оглавление
                -
                Тест 7
                12 минут
                -
                Лекция 9
                Параллельные алгоритмы численного интегрирования
                Параллельные алгоритмы интегрирования функции одной переменной, построенные на основе методов геометрического параллелизма и коллективного решения. Адаптивный последовательный алгоритм интегрирования. Параллельный алгоритм интегрирования с динамической балансировкой загрузки для многопроцессорных систем с общей памятью.
                Оглавление
                  -
                  5 часов
                  -
                  Алексей Токарев
                  Алексей Токарев

                  Добрый день.
                  Подскажите, пожалуйста, каким плеером просматривать видео. 

                  Тамара Механцева
                  Тамара Механцева

                  Добрый день!

                  Подскажите, пожалуйста, требуется ли какое-то специальное ПО для просмотра видео-лекций? С сайта скачивается архив с различными файлами: есть ли нечто вроде ReadMe-инструкции, какие из них необходимо запускать и в какой последовательности? 

                  Селена Шаронова
                  Селена Шаронова
                  Россия, Тольятти
                  Екатерина Кудрявцева
                  Екатерина Кудрявцева
                  Россия, Самара, ПГУТИ, 2013