Программа дисциплины «Паралельные вычисления»



страница1/15
Дата16.02.2017
Размер1.2 Mb.
Просмотров1515
Скачиваний0
ТипПрограмма дисциплины
  1   2   3   4   5   6   7   8   9   ...   15


УМКД 042-39.1.142/02-2013
Редакция №1 от 03.09.2013.

Страница из


Министерство образования и науки Республики Казахстан

Государственный Университет имени Шакарима города Семей

Документ СМК 3 уровня

УМКД

УМКД

042-39.1.142/02-2013




УМКД

Рабочая учебная программа дисциплины «Паралельные вычисления» для студентов



Редакция №1 от 03.09.2013


УЧЕБНО-МЕТОДИЧЕСКИИ КОМПЛЕКС

ДИСЦИПЛИНЫ

«Параллельные вычисления»

для специальности 5В060200 – «Информатика »
УЧЕБНО-МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ


Семей

2014
СОДЕРЖАНИЕ


  1. Глоссарий

  2. Лекции

  3. Лабораторные занятия

  4. Самостоятельная работа студента



  1. Глоссарий

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



Векторно-конвейерные вычислительные системы относятся к классу SIMD-систем.

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

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

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

Вычислительная системы MISDisd существуют различные точки зрения. По одно них – за всю историю развития вычислительной техники системы MISD не были созданы.

Классификации Флина охватывает только два классификационных признака – тип потока команд и тип потока данных.

Кластерные системы (вычислительные кластеры) представляют собой более дешевый вариант MPP-систем

Структуру вычислительной системы можно определить как совокупность аппаратных средств ЭВМ с указанием основных связей между ними.
2. ЛЕКЦИИ
Лекция 1. Архитектура параллельных вычислительных систе. Основные классы параллельных вычислительных систем. Классификация параллельных вычислительных систем


  • Классификация Флина;

  • Классификация по типу строения оперативной памяти;

  • Классификация по типу коммуникационной сети;

  • Классификация по степени однородности.

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



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

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

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

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

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

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



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

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



http://bigor.bmstu.ru/?img/?doc=parallel/ch010101.mod/?n=1

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

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

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

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



http://bigor.bmstu.ru/?img/?doc=parallel/ch010101.mod/?n=2

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


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

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

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



  • SISD (ОКОД);

  • MISD (МКОД);

  • SIMD (ОКМД);

  • MIMD (МКМД).

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

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



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

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

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

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

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



Классификация по типу строения оперативной памяти.

По типу строения оперативной памяти системы разделяются на системы с общей (разделяемой) памятью, системы с распределенной памятью и системы с физически распределенной, а логически общедоступной памятью (гибридные системы).

В вычислительных системах с общей памятью (Common Memory Systems или Shared Memory Systems) значение, записанное в память одним изпроцессоров, напрямую доступно для другого процессора. Общая память обычно имеет высокую пропускную способность памяти (bandwidth) и низкую латентность памяти (latency) при передачи информации между процессорами, но при условии, что не происходит одновременного обращения нескольких процессоров к одному и тому же элементу памяти. К общей памяти доступ разных процессорами системы осуществляется, как правило, за одинаковое время. Поэтому такая память называется еще UMA-памятью (Unified Memory Access) — памятью с одинаковым временем доступа. Система с такой памятью носит название вычислительной системы с одинаковым временем доступа к памяти. Системы с общей памятью называются также сильносвязанными вычислительными системами.

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



Вычислительные системы с гибридной памятью - (Non-Uniform Memory Access Systems) имеют память, которая физически распределена по различным частям системы, но логически разделяема (образует единое адресное пространство). Такая память называется еще логически общей (разделяемой) памятью(logically shared memory). В отличие от UMA-систем, в NUMA-системах время доступа к различным частям оперативной памяти различно.

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



Классификация по типу коммуникационной сети.

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



Классификация по степени однородности

По степени однородности различают однородные (гомогенные) и неоднородные (гетерогенные) вычислительные системы. Обычно при этом имеется в виду тип используемых процессоров.

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

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

Рассмотренные классификационные признаки параллельных вычислительных систем не исчерпывают всех возможных их характеристик. Существует, например, еще разделение систем по степени согласованности режимов работы (синхронные и асинхронные вычислительные системы), по способу обработки (с пословной обработкой и ассоциативные вычислительные системы), по жесткости структуры (системы с фиксированной структурой и системы с перестраиваемой структурой), по управляющему потоку (системы потока команд -instruction flow и системы потока данных — data flow) и т.п.

Современные высокопроизводительные системы имеют, как правило, иерархическую структуру. Например, на верхнем уровне иерархии система относится к классу MIMD, каждый процессор которой представляет собой систему MIMD или систему SIMD.

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

Перечислите классификационные признаки, используемые в классификации вычислительных систем Флина, а также типы вычислительных систем по этой классификации.



 Ответ 

Классификации Флина охватывает только два классификационных признака – тип потока команд и тип потока данных.

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

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

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

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

В соответствии с классификацией Флина различают следующие четыре класса вычислительных система: SISD (ОКОД); MISD (МКОД); SIMD (ОКМД); MIMD (МКМД).



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

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

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

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

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

Назовите три основных класса параллельных вычислительных систем в зависимости от типа строения их оперативной памяти.



 Ответ 

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

1) В вычислительных системах с общей памятью (Common Memory Systems или Shared Memory Systems) значение, записанное в память одним из процессоров, напрямую доступно для другого процессора. Общая память обычно имеет высокую пропускную способность памяти (bandwidth) и низкую латентность памяти (latency) при передачи информации между процессорами, но при условии, что не происходит одновременного обращения нескольких процессоров к одному и тому же элементу памяти. К общей памяти доступ разных процессорами системы осуществляется, как правило, за одинаковое время. Поэтому такая память называется еще UMA–память (Unified Memory Access) — памятью с одинаковым временем доступа. Системы с такой памятью называются UMA-системами. Системы с общей памятью называются также сильносвязанными системами. Вычислительные системыс общей памятью Вычислительные системы с общей памятью называются мультипроцессорными вычислительными системами или мультипроцессорами.

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

3) Системы с гибридной памятью - NUMA-системы (Non-Uniform Memory Access Systems) имеют память, которая физически распределена по различным частям системы, но логически разделяема (образует единое адресное пространство). Такая память называется еще логически общей (разделяемой) памятью (logically shared memory). В отличие от UMA-систем, в NUMA-системах время доступа к различным частям оперативной памяти различно.


Лекция 2. Векторно-конвейерные системы и векторно-параллельные (SIMD-системы)

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

  • Векторно-параллельные системы.


Векторно-конвейерные вычислительные системы относятся к классу SIMD-систем. Основные принципы, заложенные в архитектуру векторно-конвейерных систем:

  • конвейерная организация обработки потока команд;

  • введение в систему команд набора векторных операций, которые позволяют оперировать с целыми массивами данных.

Длина обрабатываемых векторов в современных векторно-конвейерных системах составляет, как правило, 128 или 256 элементов. Основное назначение векторных операций состоит в распараллеливании выполнения операторов цикла, в которых обычно сосредоточена большая часть вычислительной работы.

Первый векторно-конвейерный компьютер Cray-1 появился в 1976 году. Архитектура этого компьютера оказалась настолько удачной, что он положил начало целому семейству компьютеров.

Современные векторно-конвейерные системы имеют иерархическую структуру:


  • на нижнем уровне иерархии расположены конвейеры операций (например, конвейер (pipeline) сложения вещественных чисел, конвейер умножения таких же чисел и т.п.);

  • некоторая совокупность конвейеров операций объединяется в конвейерное функциональное устройство;

  • векторно-конвейерный процессор содержит ряд конвейерных функциональных устройств;

  • несколько векторно-конвейерных процессоров (2-16), объединенных общей памятью, образуют вычислительный узел;

  • несколько таких узлов объединяются с помощью коммутаторов, образуя либо NUMA-систему либо MPP-систему.

Типичными представителями такой архитектуры являются компьютеры CRAY J90/T90, CRAY SV1, NEC SX-4/SX-5. Уровень развития микроэлектронных технологий не позволяет в настоящее время производить однокристальные векторно-конвейерные процессоры, поэтому эти системы довольно громоздки и чрезвычайно дороги.

Каждая часть конвейера операций называется ступенью конвейера операций, а общее число ступеней - длиной конвейера операций.


Пример 1

Рассмотрим следующий 4-х ступенчатый конвейер операций сложения вещественных чисел http://bigor.bmstu.ru/?frm/?doc=parallel/ch010102.mod/?n=1/?k=10



Таблица 1    

Номер ступени

Наименование

1

Вычитание порядков http://bigor.bmstu.ru/?frm/?doc=parallel/ch010102.mod/?n=2/?k=10

2

Сдвиг одной из мантисс http://bigor.bmstu.ru/?frm/?doc=parallel/ch010102.mod/?n=3/?k=10

3

Сложение мантисс

4

Нормализация

Положим, что выполняется сложение двух http://bigor.bmstu.ru/?frm/?doc=parallel/ch010102.mod/?n=4/?k=10 -векторов вещественных чисел http://bigor.bmstu.ru/?frm/?doc=parallel/ch010102.mod/?n=5/?k=10 http://bigor.bmstu.ru/?frm/?doc=parallel/ch010102.mod/?n=6/?k=10. Диаграмма сложения этих векторов приведена на рис. 1http://bigor.bmstu.ru/?frm/?doc=parallel/ch010102.mod/?n=7/?k=10



http://bigor.bmstu.ru/?img/?doc=parallel/ch010102.mod/?n=1

Рис. 1.  К примеру 1. Временная диаграмма сложения (n*1)-векторов вещественных чисел X ,Y на 4-х ступенчатом конвейере операции сложения.

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

Пример 2

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



http://bigor.bmstu.ru/?frm/?doc=parallel/ch010102.mod/?n=8/?k=10

 (1)

где http://bigor.bmstu.ru/?frm/?doc=parallel/ch010102.mod/?n=9/?k=10 - http://bigor.bmstu.ru/?frm/?doc=parallel/ch010102.mod/?n=4/?k=10 -векторы вещественных чисел, под произведением и делением векторов понимается их покомпонентное умножение и деление, соответственно. Иными словами, операции, указанные в выражении (1), понимаются в смысле 



http://bigor.bmstu.ru/?frm/?doc=parallel/ch010102.mod/?n=10/?k=10

 (2)

Положим также, что конвейерное функциональное устройство данной векторно-конвейерной системы имеет следующие конвейеры операций:



  • конвейер сложения вещественных чисел;

  • конвейер умножения вещественных чисел;

  • конвейер деления вещественных чисел

Тогда для повышения скорости вычисления компонент вектора E целесообразно использовать зацепление указанных конвейеров (см. рис. 2). В результате, можно сказать, получается новый конвейер, который выполняет сложную операцию (2)http://bigor.bmstu.ru/?frm/?doc=parallel/ch010102.mod/?n=7/?k=10

http://bigor.bmstu.ru/?img/?doc=parallel/ch010102.mod/?n=2


Поделитесь с Вашими друзьями:
  1   2   3   4   5   6   7   8   9   ...   15


База данных защищена авторским правом ©nethash.ru 2017
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал