Функции обработки массивов для получения соответствия

Тест: Соответствие массивов

Тест: Функции понижения ранга

Тест: Операция переформирования массивов

Параллельные операторы

Глава 2.5. Языки высокого уровня для программирования MIMD-вычислительных систем

MPMD-языки высокого уровня. Средства описания процессов, средства инициализации и завершения процессов

Тест: MPMD- и SPMD-парадигмы параллельного программирования

Тест: Гранулированность параллельной программы

MPMD-языки высокого уровня. Средства синхронизации и обмена данными

MPMD-языки высокого уровня. Средства конфигурирования

Тест: Средства конфигурирования

SPMD-языки высокого уровня

Глава 2.6. Автоматическое распараллеливание последовательных программ

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

Распараллеливание ациклических участков

Тест: Граф зависимостей по данным

Тест: Алгоритм построения ЯПФ

Тест: Параметры ЯПФ

Особенности распараллеливание выражений

Тест: Задача распараллеливания выражений

Распараллеливание циклических фрагментов программ

Тест: Пространство итераций

Тест: Задача распараллеливания циклов

Глава 2.7. Коммуникационные библиотеки для организации параллельного выполнения программ

Библиотека OpenMP

Библиотека MPI

Библиотека PVM

Глава 2.8. Средства отладки и профилирования параллельных программ

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

Средства профилирования параллельных программ

Глава 3. Алгоритмы для параллельных вычислительных систем

Глава 3.1. Общие вопросы синтеза алгоритмов для параллельных вычислительных систем

Типы параллелизма и методы синтеза параллельных алгоритмов

Тест: Зернистость алгоритма

Тест: Параллелизм данных

Тест: Функциональный параллелизм

Тест: Геометрический параллелизм

Оценка эффективности параллельных алгоритмов

Тест: PRAM

Тест: Эффективный параллельный алгоритм

Тест: Ускорение параллельного алгоритма

Тест: Эффективность параллельного алгоритма

Тест: Закон Амдала

Тест: Парадокс параллелизма

Параллельные алгоритмы вычисления рекурсий

Глава 3.2. Параллельные методы и алгоритмы линейной алгебры

Базовые алгоритмы

Прямые методы решения систем линейных алгебраических уравнений. Метод исключения Гаусса

Итерационные методы решения систем линейных алгебраических уравнений. Метод Якоби

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

Глава 3.3. Параллельные алгоритмы интегрирования обыкновенных дифференциальных уравнений

Задача Коши

Двухточечная краевая задача для уравнений второго порядка

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

Нестационарная задача

Стационарная краевая задача

Литература

 

Классификация параллельных вычислительных систем

Под архитектурой вычислительной системы понимаются абстрактное представление ЭВМ с точки зрения программиста. Полное описание архитектуры системы включает в себя:

· основные форматы представления данных;

· способы адресации данных в программе;

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

В курсе рассматриваются только последние аспекты архитектуры вычислительной системы.

Структуру вычислительной системы можно определить как совокупность аппаратных средств ЭВМ с указанием основных связей между ними.

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

Классификация Флина.

Наибольшее распространение получила классификация вычислительных систем, предложенная в 1966 г. профессором Стенфордского университета М.Д.Флином (M.J.Flynn) - классификация Флина. Эта классификация охватывает только два классификационных признака – тип потока команд и тип потока данных (см. Рис.1, 2).

Рис. 1. К классификации Флина. Классификация по типу потока команд.

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

Во множественном потоке команд в один момент времени может выполняться много команд. В этом случае каждая из таких команд определяет в данный момент времени работу только одного или лишь нескольких (но не всех) устройств вычислительной системы.

В одиночном потоке последовательно выполняются отдельные команды, во множественном потоке – группы команд.

Рис. 2. К классификации Флина. Классификация по типу потока данных.

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

Множественный поток данных состоит из многих зависимых или независимых одиночных потоков данных.

В соответствии со сказанным, все вычислительные системы делятся на четыре типа:

· SISD (ОКОД);

· MISD (МКОД);

· SIMD (ОКМД);

· MIMD (МКМД).

Вычислительная система SISD представляет собой классическую однопроцессорную ЭВМ фон-неймановской архитектуры.

На вычислительную системы MISD существуют различные точки зрения. По одно них – за всю историю развития вычислительной техники системы MISD не были созданы. По другой точке зрения (менее распространенной, чем первая) к MISD-системам относятся векторно-конвейерные вычислительные системы. Мы будем придерживаться первой точки зрения.

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

· векторно-конвейерные вычислительные системы;

· векторно-параллельные вычислительные системы или матричные вычислительные системы.

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

Рассмотренная классификации Флина позволяет по принадлежности компьютера к классу SIMD или MIMD сделать сразу понятным базовый принцип его работы. Часто этого бывает достаточно. Недостатком классификации Флина является "переполненность" класс MIMD.