Файлы для подготовки к экзамену (Архитектура компьютеров и ВС, принципы параллельного программирования)

Посмотреть архив целиком

45



Оглавление

Оглавление 2

1. Архитектура, технологические характеристики, принципы работы, проблемы развития компьютеров и ВС. 3

1.1. Краткая история развития параллелизма в архитектуре ЭВМ. 3

1.2. Введение и основные понятия. 4

1.2.1. Ряд основных понятий и определений. 4

1.2.2. Архитектурный облик современного компьютера. 5

1.2.3. Схема выполнения (команд) программы. 8

1.3. Режимы работы компьютера и связь с работой процессора. 10

1.3.1. Общая схема обслуживания процессов (задач). 11

1.3.2. Специальные процессоры (компьютеры). 11

1.4. Закон Амдала. 12

1.4.1. Классификационные признаки ВС. 13

1.4.2. Два вида параллелизма. 14

1.5. Показатели ВС, сравнение. 15

2. Принципы, языки, технологии параллельного программирования. 16

2.1. Параллелизм задач, его особенности и характеристики. 16

2.2. Процессы, их характеристики. 17

2.3. Типы и характеристики параллелизма. 17

2.4. Типы и особенности параллелизма. 22

2.5. Процессы модели и языки. 24

2.6. Сети Петри 24

2.4.1. Событийная модель; статические процессы. 24

2.6.2. Расширение сети Петри 29

2.7. Модели взаимодействующих последовательных процессов Хоара 31

3. 3. Реализация параллельных языков программирования 35

3.1. Примитивы и языки параллельного программирования 35

3.2. MPI 36

3.3. Язык граф - схемного потокового параллельного программирования (ЯГСПП) 37

3.4. Функциональное параллельное программирование 37

3.4.1. Functional Parallel Typified Language (FPTL) 37

  1. Архитектура, технологические характеристики, принципы работы, проблемы развития компьютеров и ВС.

    1. Краткая история развития параллелизма в архитектуре ЭВМ.

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

IBM 701 (1953), IBM 704 (1955): разрядно – параллельная память, разрядно – параллельная арифметика.

Все самые первые компьютеры (EDSAC, EDVAC, UNIVAC) имели разрядно-последовательную память, из которой слова считывались последовательно бит за битом. Наибольшую популярность получила модель IBM 704, в которой, была впервые применена память на ферритовых сердечниках и аппаратное арифметическое устройство с плавающей точкой.

IBM 709 (1958): независимые процессоры ввода/вывода.

Процессоры первых компьютеров сами управляли вводом/выводом. Однако скорость работы самого быстрого внешнего устройства была в 1000 раз меньше скорости процессора, поэтому во время операций ввода/вывода процессор фактически простаивал. В 1958г. к компьютеру IBM 704 присоединили 6 независимых процессоров ввода/вывода, которые после получения команд могли работать параллельно с основным процессором, а сам компьютер переименовали в IBM 709.

IBM STRETCH (1961): опережающий просмотр вперед, расслоение памяти.

В 1956 году IBM подписывает контракт с Лос-Аламосской научной лабораторией на разработку компьютера STRETCH, имеющего две принципиально важные особенности:

  • опережающий просмотр вперед для выборки команд;

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

ATLAS (1963): конвейер команд.

Впервые конвейерный принцип выполнения команд был использован в машине ATLAS, разработанной в Манчестерском университете. Выполнение команд разбито на 4 стадии: выборка команды, вычисление адреса операнда, выборка операнда и выполнение операции. Конвейеризация позволила уменьшить время выполнения команд с 6 мкс до 1,6 мкс. Данный компьютер оказал огромное влияние, как на архитектуру ЭВМ, так и на программное обеспечение: в нем впервые использована мультипрограммная ОС, основанная на использовании виртуальной памяти и системы прерываний.

CDC 6600 (1964): независимые функциональные устройства.

Фирма Control Data Corporation (CDC) при непосредственном участии одного из ее основателей, Сеймура Р.Крэя (Seymour R.Cray) выпускает компьютер CDC-6600 - первый компьютер, в котором использовалось несколько независимых функциональных устройств. Приведем некоторые параметры компьютера:

  • время такта 100нс,

  • производительность 2-3 млн. операций в секунду,

  • оперативная память разбита на 32 банка по 4096 60-ти разрядных слов,

  • цикл памяти 1мкс,

  • 10 независимых функциональных устройств.

Машина имела громадный успех на научном рынке, активно вытесняя машины фирмы IBM.

CDC 7600 (1969): конвейерные независимые функциональные устройства.

CDC выпускает компьютер CDC-7600 с восемью независимыми конвейерными функциональными устройствами - сочетание параллельной и конвейерной обработки. Основные параметры:

  • такт 27,5 нс,

  • 10-15 млн. опер/сек.,

  • 8 конвейерных ФУ,

  • 2-х уровневая память.

ILLIAC IV (1974): матричные процессоры.

Проект: 256 процессорных элементов (ПЭ) = 4 квадранта по 64ПЭ, возможность реконфигурации:

2 квадранта по 128ПЭ или 1 квадрант из 256ПЭ, такт 40нс, производительность 1Гфлоп; работы начаты в 1967 году, к концу 1971 изготовлена система из 1 квадранта, в 1974г. она введена в эксплуатацию, доводка велась до 1975 года;

центральная часть: устройство управления (УУ) + матрица из 64 ПЭ;

УУ это простая ЭВМ с небольшой производительностью, управляющая матрицей ПЭ; все ПЭ матрицы работали в синхронном режиме, выполняя в каждый момент времени одну и ту же команду, поступившую от УУ, но над своими данными;

ПЭ имел собственное арифметико-логическое устройство (АЛУ) с полным набором команд, оперативная память (ОП) - 2Кслова по 64 разряда, цикл памяти 350нс, каждый ПЭ имел непосредственный доступ только к своей ОП.

Несмотря на результат в сравнении с проектом: стоимость в 4 раза выше, сделан лишь 1 квадрант, такт 80нс, реальная производительность до 50Мфлоп - данный проект оказал огромное влияние на архитектуру последующих машин, построенных по схожему принципу, в частности: PEPE, BSP, ICL DAP.

    1. Введение и основные понятия.

      1. Ряд основных понятий и определений.

Определение 1a. Процесс – это программа на стадии ее выполнения, некоторое вычисление, которое может выполняться параллельно с другими.

Определение 1b. Процесс Windows– объект ОС; оболочка для манипулирования программой, в ней нет исполняемого кода.

Операции над процессами:

  • создание процесса;

  • уничтожение;

  • изменение приоритета;

  • запуск;

  • блокировка;

  • вытеснение;

  • приостановка;

  • возобновление.

При создании процесса создается главный поток.

Определение 2. Поток – объект ОС, который содержит выполняемый код и подлежит планированию.

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

      1. Архитектурный облик современного компьютера.

Архитектура ЭВМэто общее описание структуры и функций ЭВМ. Архитектура не несет в себе описание деталей технического и физического устройств компьютера.

Пояснения к схеме:

ПР – процессор;

П – порты;

УП – управление памятью;

ИНТ – интерфейс;

ОП – оперативная память;

Д – диски;

КР – коммутатор.

В данной схеме местная периферия (принтеры, мониторы и т.д.), общий блок УП для все процессоров.

Основные блоки процессора.

Пояснения к схеме:

СК – счетчик команд;

ИА – индексное устройство;

ДШ – дешифратор кода команд;

УП – управление памятью;

АУ – арифметическое устройство;

РК – регистры команд;

РО – регистры операнд;

РР – регистры результатов.


      1. Схема выполнения (команд) программы.

Параллельная обработка данных имеет две разновидности:

  • конвейерная

  • параллельная.

Параллельная обработка.

Если некое устройство выполняет одну операцию за единицу времени, то тысячу операций оно выполнит за тысячу единиц. Если предположить, что есть пять таких же независимых устройств, способных работать одновременно, то ту же тысячу операций система из пяти устройств может выполнить уже не за тысячу, а за двести единиц времени. Аналогично система из N устройств ту же работу выполнит за 1000/N единиц времени.

Конвейерная обработка.

Рассмотрим схему выполнения программы, введение конвейера и анализ его работы:

Пояснения к схеме:

СК – счетчик команд;

ИА – индексное устройство;

ДШ – дешифратор кода команд;

УП – управление памятью;

АУ – арифметическое устройство;

РК – регистры команд;

РО – регистры операнд;

РР – регистры результатов.


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

Процессоры первых компьютеров выполняли все эти "микрооперации" для каждой пары аргументов последовательно одна за другой до тех пор, пока не доходили до окончательного результата, и лишь после этого переходили к обработке следующей пары слагаемых. Идея конвейерной обработки заключается в выделении отдельных этапов выполнения общей операции, причем каждый этап, выполнив свою работу, передавал бы результат следующему, одновременно принимая новую порцию входных данных. Получаем очевидный выигрыш в скорости обработки за счет совмещения прежде разнесенных во времени операций. Предположим, что в операции можно выделить пять микроопераций, каждая из которых выполняется за одну единицу времени. Если есть одно неделимое последовательное устройство, то 100 пар аргументов оно обработает за 500 единиц. Если каждую микрооперацию выделить в отдельный этап конвейерного устройства, то на пятой единице времени на разной стадии обработки такого устройства будут находится первые пять пар аргументов, а весь набор из ста пар будет обработан за 5+99=104 единицы времени - ускорение по сравнению с последовательным устройством почти в пять раз.

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


Принципиальные характеристики компьютера:

  • производительность – [оп/сек];

  • быстродействие – время выполнения операций.

Выделим важнейшие факторы, влияющие на быстродействие процессора.

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

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

Количество тактов, затрачиваемых на выполнение команды, зависит от сложности этой команды и от методов адресации операндов.

Первоначально для количественной оценки производительности процессоров применялась единица измерения MIPS (Mega Instruction Per Second), соответствовавшая количеству миллионов выполняемых команд за секунду. Естественно, изготовители микропроцессоров старались ориентироваться на самые быстрые команды.

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

Время выполнения команд — важный, но далеко не единственный фактор, определяющий быстродействие. Большое значение имеет также структура системы команд процессора. Например, некоторым процессорам для выполнения какой-то операции понадобится одна команда, а другим процессорам — несколько команд. Какие-то процессоры имеют систему команд, позволяющую быстро решать задачи одного типа, а какие-то — задачи другого типа. Важны и методы адресации, разрешенные в данном процессоре, и наличие сегментирования памяти, и способы взаимодействия процессора с устройствами ввода/вывода и т.д.

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

Источники убыстрения:

  • организационно технологические;

-повышение быстродействия элементов процессора;

-введение дополнительных устройств, имеющих возможность работать параллельно;

(СДС – 7600, Крэй, Стрейч, БЭСМ6)

  • организационно управленческие решения;

-динамический анализ независимых команд в потоке. Накладные расходы на динамический анализ большие;

Определение. Команды являются независимыми, если выполняется

-параллельное выполнение ветвей программы связанное с условными переходами;

-введение сопроцессоров.

    1. Режимы работы компьютера и связь с работой процессора.

  • однопрограммный режим;

  • многопрограммный режим;

  • циклическое обслуживание.

      1. Общая схема обслуживания процессов (задач).

Одноуровневая дисциплина обслуживания.

Определение. Латентность связана с вызовом программ ОС. Идеальная латентность: 1 мксек – 100 мксек.

Простейший пример сети массового обслуживания (в схеме нет отложенных процессов).

P – время простоя процессора, K – количество процессов.

      1. Специальные процессоры (компьютеры).

  1. Манчестер data flow machine. Увеличение быстродействия на 60%.

  2. Ассоциативные процессоры.

Исследование эффективности компьютеров.


    1. Закон Амдала.

Коэффициент ускорения на N процессорах определяется следующем образом

,

где -программа, -последовательное выполнение программы, -параллельное выполнение программы.

Если , то .

Так же сформулировать закон Амдала следующим образом:

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

-коэффициент ускорения.

      1. Классификационные признаки ВС.

Многомашинные – многопроцессорные.

Сравним два варианта схем:

  1. Данный вариант предполагает наличие единого адресного пространства.

Системы с общей памятью различают:

- однородные (время доступа одно и тоже).

- неоднородные.

Узкие места:

  • ограничена масштабируемость.

  • При соединение N процессоров, соединяя каждый, получаем N2 соединений, что при больших системах является проблемой.

Здесь мы имеем параллелизм на уровне команд, мелко зернистый (fine grain).

  1. В этом случае у каждого процессора своя память.

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

Пример.

1970год. Burroushs (500, 6000, 6500).Процессор с магазинной памятью. 3мл. оп\сек.

      1. Два вида параллелизма.

Принципом распараллеливания является принцип ветвей.

Рассмотрим два вида параллелизма:

  1. мелко зернистый (fine grain).

  2. крупно зернистый (gros grain).

fine grain gros grain.

IBM M, CM.

Топологии связи в ВС:

  • Общая шина.

  • матричные переключатели.

Конструкции IBM:

ASCI WHITE

ВС-8196 – компьютер с пиковой производительностью 121012.

BLUE GENE / L

645336– компьютер с пиковой производительностью 130-1601012.

База SP 16-ти процессорная. По 4 компьютера с общей памятью. Сеть OMEGA или SP SWITCH.Стоит переключательная матрица.

    1. Показатели ВС, сравнение.

  1. Пиковая производительность равна количеству операций в секунду.

  2. Пропускная способность каналов.

  3. Пропускная способность процессор память.

  4. Объем памяти (Cache, ОП и др.)

Сравнение.

Стандартные смеси:

  1. Реальные задачи (задачи оптимизации).

  2. Синтетические смеси – набор смесей, которые позволяют проверить поведение системы в различных режимах.

- оценка системы.

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

Типы команд :, частота, с которой они появляются на интервале от 0 до t - .

- оценка системы.

  1. Принципы, языки, технологии параллельного программирования.

    1. Параллелизм задач, его особенности и характеристики.

Параллелизм процесс, одновременность актов.

Процесс:

  • дискретный (можно наблюдать в точках с частотой генераторов, работающих в системе).

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

  • асинхронный (не вводит временных ограничений).

  • синхронный (сохраняет причинно-следственные связи и вводит ограничения на время актов, которое не нарушает связи).

Может быть временное и событийное описание процесса.

Синхронный процесс.

ai – акты, k1..k4- команды.

После выполнения a1 –может выполнятся a2.

Введено ограничение на время протекания событий.

синхронная схема последовательная.

Асинхронный процесс.

Абсолютно параллельное вычисление.


    1. Процессы, их характеристики.

  1. Дискретный процесс – это множество протекающих (во времени) актов, упорядоченных отношениями (как правило) причинно-следственных связей между актами.

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

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

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

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

Пример конструктивного процесса.

Правила выполнения:

  • Выполнить P(x); в зависимости от истинности.

  • и окончить.

  • и окончить.

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

6. Каждый параллельный алгоритм характеризуется множеством потоков, каждый поток фиксирует последовательность выполнения актов при применении параллельного алгоритма к данным.

    1. Типы и характеристики параллелизма.

  1. Коэффициент ускорения.

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

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

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

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

, где - ближайшее целое к . Очевидно, .

Если попытаться реализовать процесс вычисления значений по этой программе, используя все возникающие при этом возможности распараллеливания, нетрудно показать, что этот процесс следует схеме:


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