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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


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


курсовая работа Архитектура параллельных вычислений

Информация:

Тип работы: курсовая работа. Добавлен: 02.11.2012. Сдан: 2012. Страниц: 36. Уникальность по antiplagiat.ru: < 30%

Описание (план):


Parallel Programming Architecture
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Введение
Идея параллельной обработки  данных не нова. Можно считать, что  она возникла еще на заре человеческой цивилизации, когда оказалось, что  племя может успешно бороться за выживание, если каждый его член выполняет свою часть общей работы. 
В ближайшее время под  эффективным использованием аппаратных средств компьютера будут пониматься применение параллельных алгоритмов. Это связано с замедлением  темпов роста тактовой частоты микропроцессоров и быстрым распространением многоядерных микропроцессоров.
Под средствами реализации параллельности понимаются языки программирования или библиотеки, обеспечивающие инфраструктуру параллельных программ.  К ним можно отнести: Occam, MPI, HPF, Open MP, DVM, Open TS, Boost.Thread, Posix Threads. Сюда также можно отнести библиотеку Integrated Performance Primitives компании Intel.
В работе будут рассмотрены  несколько базовых параллельных алгоритмов, имеющих практическое значение во многих областях, в том числе  в экономике, в численном моделировании  и в задачах реального времени.
Данная работа состоит  из трех взаимосвязанных тематических разделов.
Первый из них содержит информацию о математическом обеспечении  параллельных вычислительных систем, о способах приема, обработки, хранения информации, о функционировании элементов  высокопроизводительных систем.
Второй раздел работы посвящен аппаратной части параллельных вычислений. В этой части содержится информация о технологиях параллельных вычислений, классификации процессоров, принципах  работы высокопроизводительных систем.
Третий раздел включает в  себя информацию, касающуюся практического  использования ресурсов и возможностей параллельных вычислительных систем в  решении задач из разных областей науки и техники. Также здесь  приводятся примеры нескольких вычислительных алгоритмов.
 
 
 
 
 
Глава 1. Математическое обеспечение параллельных вычислений.
 
1.1 Проблемы разработки параллельных алгоритмов
Проблеме распараллеливания  алгоритмов  для задач  вычислительной  математики  посвящено  множество  работ.  Для  создания  эффективных  алгоритмов необходимо учитывать архитектуру  параллельных  компьютеров. Компьютеры могут отличаться между собой  типами межпроцессорных связей: архитектура  с универсальной коммуникационной средой, со  смешанной системой связи, с общей шиной; со структурами  межпроцессорных связей типа линейка, кольцо, кольцо  с  хордами,  решетка,  гиперкуб, дерево и др.
Основной целью при  создании параллельных алгоритмов является достижение по  возможности  наибольшего  сокращения  времени  решения  задач. Однако на практике максимальное сокращение времени (в  количество  раз,  близкое  к количеству  процессоров) можно получить только для  задач,  по существу, тривиальных. Главные факторы, препятствующие этому, таковы:
1) отсутствие полного  параллелизма в алгоритмах исследования  и  решения задач (некоторые  операции алгоритмов являются  последовательными);
2) неравномерная загрузка  процессоров по числу арифметических  операций (несбалансированность нагрузки  процессоров);
3)  коммуникационные потери, обусловленные необходимостью  обмена  информацией между процессорами  и синхронизацией вычислительной  системы. 
При разработке и реализации параллельных алгоритмов к проблемам  компьютерных вычислений добавились новые, связанные с распараллеливанием вычислений:
–  распараллеливание  не только  арифметических действий, а и обменов  данными между  процессорами;
        –   определение топологии и количества  процессоров, необходимых для  эффективного решения задачи;
–  обеспечение равномерной  загрузки всех процессоров, которые  используются для решения задачи;
–  организация обменов  между процессорами;
–  синхронизация обменов  между процессорами;
–  минимизация обменов  между процессорами;
–  распределение исходной информации между процессорами в  соответствии с выбранной конфигурацией  и др.
Значительным шагом к  улучшению сбалансированности загрузки процессоров, а следовательно, и эффективности вычислительных  алгоритмов стала идея циклического способа хранения  и обработки матриц,  который приводит к сбалансированной  схеме для алгоритмов  триангуляции  и трехдиагонализации матриц. В соответствии, например, со строчно-циклической схемой матрица распределяется по процессорам следующим образом: в -м  процессоре  располагаются строки с номерами . Эта схема, сохраняя тот же, что и для последовательных  алгоритмов триангуляции  и трехдиагонализации матриц, порядок обработки строк (столбцов), предусматривает изменение на единицу номера  процессора  при переходе от одной строки к следующей. Таким образом, достигается примерно одинаковый объем вычислений в каждом процессоре  при реализации  алгоритмов, т.е. практически исключается влияние эффекта Гайдна. 
0




0




 
  Рисунок 1                                                      Рисунок 2
Двумерное  блочно-циклическое  распределение столбцов, включает  все предыдущие схемы как специальные  случаи. Таким образом, эффективность  алгоритмов в значительной мере определяется решением  проблем согласованности алгоритмов решения задачи с архитектурой микропроцессоров, топологией межпроцессорных соединений, схемой  декомпозиции исходных данных, наличием вычислительных и коммуникационных ядер.
 
1.2 Представление алгоритма
Для точной формулировки задачи, прежде всего, определим понятие представления алгоритма , вычисляющего функцию . Рассматриваться будут лишь такие представления алгоритма, в которых в явном виде используются преобразователи значений входных величин (переменных)  в значения выходных.  Такой преобразователь изображает элементарный шаг в интуитивном понятии алгоритма. Представление алгоритма,  которое может быть исполнено компьютером,  называется программой.  Обычно программа содержит назначение ресурсов для реализации всех объектов алгоритма.
Каждый преобразователь  (будем впредь называть его операцией)  вычисляет функцию , значение которой есть результат выполнения преобразования (выполнение операции) . 
Представление алгоритма есть набор , где - конечное множество переменных,   - конечное множество операций. 
С каждой операцией  связаны входной и выходной наборы переменных из . Наборы и будут при необходимости рассматриваться и как множества со всеми определенными для множеств операциями. Две операции и   называются информационно зависимыми, если пересечение непусто. Две операции и называются транзитивно информационно зависимыми, если существует последовательность операций,  попарно информационно зависимых. Будем говорить, что операция вычисляет переменные из переменных .
Для определенности считается,  что для выполнения операции в программе используется одноименная процедура , у которой есть входной и есть выходной наборы переменных, в программе обращение к имеет вид .
– управление, т. е. множество  ограничений на порядок выполнения операций. Управление может задаваться разными способами, это бинарное отношение частичного порядка на множестве  операций алгоритма .
 –функция, задающая отображение  множеств переменных и операций  в физические устройства параллельной  вычислительной системы, т. е.  задает распределение ресурсов мультикомпьютера.

Рисунок 3
Реализацией алгоритма , представленного в форме , называется выполнение операций в некотором произвольном допустимом порядке, который не противоречит управлению . Предполагается, что при любой реализации вычисляется функция , т.е. всегда содержит потоковое управление, которое и гарантирует вычисление . Множество всех реализаций алгоритма , представленного в форме , обозначим через . Если есть одноэлементное множество, то -  последовательное   представление. Будем говорить, что - параллельное представление алгоритма , если множество содержит, более одной реализации.
Пусть , – операции,  ,  ,  . Тогда алгоритм вычисления функции , представлен в параллельной форме , , и – операции. Определим теперь бинарное отношение непроцедурности на множестве представлений алгоритма .  Будем говорить,  что представление алгоритма более непроцедурно, чем , если . 
Представление алгоритма с потоковым управлением и тождественным распределением ресурсов является максимально непроцедурным представлением .
 
1.3 Коммуникационно-замкнутые слои параллельной программы
Это понятие  вводится для упрощения верификации (доказательства правильности) параллельных программ. Основная идея здесь - это разбиение каждого процесса параллельной программы на последовательность его операторов:
( может быть выбрано одним и тем же для всех процессов,  если допустить возможность использовать в качестве пустой оператор). Таким образом, параллельная программа может быть представлена как:
 
Эту программу можно изобразить матрицей (рис. 4)
           
           
           
           

Рисунок 4
Каждая -я строка изображает процесс как последовательность    операторов:
 
Параллельная программа  называется -м слоем параллельной программы (-й столбец матрицы). 
Слой называется коммуникационно-замкнутым, если при всех вычислениях взаимодействие процессов происходит только внутри этого слоя, или, иными словами, ни одна команда взаимодействия среди операторов при всех выполнениях не будет синхронизироваться (сочетаться) с командами взаимодействия из операторов при . 
Тогда последовательность слоев  представляет собой параллельную программу:
,
В программе  все исполняются последовательно в порядке перечисления,  а операторы каждой исполняются параллельно. Программа называется безопасной, если все ее слои коммуникационно-замкнуты. 
Если программа безопасна, то вместо верификации всей параллельной программы можно проводить ее послойную верификацию, т.е. доказывать утверждение вместо утверждения . Здесь, как обычно, обозначает утверждение, что программа частично корректна по отношению к предусловию и постусловию (вход-выходные соотношения), при этом, если до начала исполнения программы предикат истинен, то после исполнения предикат тоже истинен. 
Таким образом, если параллельную программу  удается разбить на последовательность коммуникационно-замкнутых слоев, то доказательство ее (частичной) корректности сводится к последовательному доказательству вход-выходных соотношений для каждого слоя.  Это существенно упрощает анализ корректности параллельной программы.
 
 
 
1.4 Граф достижимости
Для использования сетей  Петри необходимо знать их свойства, такие, например, как безопасность, а для этого следует изучить  множество всех возможных разметок сети с заданной начальной разметкой. 
Разметка  называется достижимой, если при некоторой конечной последовательности срабатываний переходов, начиная с начальной разметки , сеть переходит к разметке . Граф достижимости определяет все достижимые разметки и последовательности срабатываний переходов,  приводящих к ним. Его вершинами являются разметки, а дуга, помеченная символом перехода , соединяет разметки и такие, что сеть переходит от разметки к разметке при срабатывании перехода . Любой конечный фрагмент графа достижимости, начинающийся с начальной разметки и до некоторых достижимых разметок, называется разверткой сети.  Множество всех разверток определяет поведение сети Петри. Пример различных разверток сети  показан на рис. 4с. Каждая разметка определяет состояние сети. Состояние сети характеризуется множеством переходов, которые могут сработать в состоянии .
  

Рисунок 5
Сеть на рисунке 5а определяет управление двумя параллельно протекающими процессами с синхронизацией ? оба процесса поставляют фишки, необходимые для срабатывания  перехода . Граф достижимости показан на рис. 5b. Он бесконечен, однако после разметки в каждой ветви повторяется один и тот же фрагмент и потому возможно конечное представление графа достижимости  (рис.  5b).  Множество разверток сети  бесконечно,  примеры разверток приведены на рис. 5с.
 
1.5 Сети Петри
Сеть Петри–это математическая модель, которая имеет широкое  применение для описания поведения  параллельных устройств и систем  процессов. Наиболее интересны сети Петри тем, что они позволяют  представлять и изучать в динамике поведение системы параллельных взаимодействующих процессов программы  или любого другого дискретного  устройства.
Определение сети Петри дадим  в три приема. Сеть есть двудольный ориентированный граф. Напомним, что  двудольный граф – это такой граф, множество вершин которого разбивается  на два подмножества и не существует дуги, соединяющей две вершины  из одного подмножества. Итак, сеть –  это набор

где
 – подмножество  вершин, называющихся переходы, – подмножество вершин, называющихся местами, –множество ориентированных дуг. 
По определению, ориентированная  дуга соединяет либо место с переходом либо переход с местом. Состояние сети в каждый текущий момент определяется системой условий. Для того, чтобы стало возможным и удобным задавать условия типа “в буфере находится три значения” в определение сети Петри добавляются фишки (размеченные сети). Фишки изображаются точками внутри места. В применении к программированию можно представлять себе переходы как процедуры, а места – как переменные.
Фишка свидетельствует о  том, что в переменной/буфере имеется  значение, а если место имеет, к  примеру, 3 фишки, то это может интерпретироваться как наличие трех значений в буфере. Если место содержит фишку,  то место  маркировано и сеть называется маркированной.  Начальное распределение фишек  задает начальную маркировку сети.  Маркировка сети определяет ее текущее состояние.  Она задается функцией , , а функция представляется вектором, в котором -ый компонент задает маркировку места . В определение сети добавляется понятие срабатывания перехода. Срабатывание перехода состоит из того,  что из всех входных мест перехода забирается по одной фишке и во все выходные места добавляется по одной фишке. Если представить себе переход как процедуру, то она корректно выполняется и вырабатывает значения своих выходных переменных, если есть значения всех аргументов.
 
1.6 Задача взаимного исключения
Сетью Петри можно строго описать поведение процессов  в задаче взаимного исключения. Такая  сеть должна описывать поведение  системы процессов с взаимным исключением доступа к неразделяемому ресурсу.
Пусть заданы два процесса и , конкурирующие за доступ к общему неразделяемому ресурсу (рис. 6). Общий ресурс изображается местом .  Переходы обозначают какие-то действия с использованием ресурсов.  Например, если процессу выделен затребованный блок памяти , то процесс сможет выполнить свою подпрограмму . Количество экземпляров ресурса обозначается фишками в месте - один экземпляр. 

Рисунок 6
Итак, два процесса (переходы t3 и t5) запрашивают единственный экземпляр  ресурса  но только одному процессу ресурс может быть выделен. Во множестве поведение сети на рис. 6 нет такой развертки сети, которая бы привела к одновременному срабатыванию переходов и .
Сеть Петри не определяет, какой именно из двух конкурирующих  процессов получит доступ к ресурсу.  Она лишь описывает ограничение на доступ к ресурсу - только один процесс получает доступ к ресурсу . Как следствие,  при таком задании управления возможна ситуация,  когда доступ к ресурсу будет постоянно получать один и тот же процесс, например ,  а процесс останется “навечно” ожидать выделения ему ресурса .
При организации выполнения системы процессов эта ситуация разрешается с использованием дополнительных средств. Например, в операционных системах в описание состояния процессов  вводится дополнительная характеристика - приоритет. Запрошенный ресурс выделяется процессу с наибольшим приоритетом. Начальный приоритет любого процесса растет с ростом времени ожидания ресурса.  Таким образом,  всякий процесс со временем получит запрошенный  ресурс. 
Другой  способ выделения  ресурса  -  устройство очереди.  Все запросы ресурса выстраиваются  в очередь к ресурсу и процесс, раньше все запросивший ресурс,  получит его первым  (дисциплина обслуживания FIFO - First_In - First_Out).
 
1.7 Динамические и итерационные вычислительные модели с массивами
Для ограничения вычислений нужны дополнительные средства, которые  и вводятся в вычислительных моделях  с массивами. Вначале определяются динамические вычислительные модели с  массивами (ВММ), а затем итеративные
Пусть заданы:
1.  Множество переменных  , где и Y—те же множества простых переменных и компонентов массивов, а —конечное множество переменных, называемых счетчиками, ; каждому массиву соответствует счетчик из , который обозначается .
2.  Множество  экземпляров операций,  оно определяется так,  что входные и выходные наборы экземпляров операций могут содержать счетчики. Кроме того:
а)  если —массовая операция,  то(.); 
б)  в множестве существует только одна такая простая операция , что
Счетчики являются особыми  переменными, значение счетчика определяет число компонентов массива (допускаются только такие интерпретации). Массивы называются динамическими массивами.
Набор называется динамической вычислительной моделью с массивами. Пусть . Предполагается,  что если какие-либо компоненты массива входят в ,  то и ,  это же справедливо и для .
Понятие терма определяется обычным образом. В реализации терма  необходимо будет учитывать,  что в нем не может использоваться такой компонент , что превосходитзначение, полученное счетчиком .
Понятно, что в динамических моделях может быть задан алгоритм вычисления любой примитивно-рекурсивной  функции. Число компонентов массива  заранее не определено, но в ходе вычислений значение счетчика определяется до начала использования компонентов  массива.
Добавим ещё и итеративные  массивы,  которые бы допускали  введение предикатов-предусловий операций и возможность задания счетчикам  различных значений,  чтобы число  компонентов массива могло расти  в ходе вычислений (как это нужно  для определения оператора минимизации). Такое расширение делается довольно сложно технически, а поэтому итеративные ВММ демонстрируются на примерах. В примерах предполагается, что понятия структурной и содержательной интерпретаций вводится обычным образом.
На рис. 7. показана массовая операция a итеративной ВММ, ,  план, вычисляющий массив x , содержит все термы вида . При должной интерпретации алгоритм, заданный планом, может считывать в оперативную память все записи файла.
 

Рисунок 7
На рис.8а показана структурированная итеративная ВММ .  Структурная интерпретация массовых операций и приведена на рис. 8б и 8в. Операциям и ВММ (рис. 8а) соответствуют ВММ (см.  рис. 8б) и (см. рис. 8в); ; переменные—это счетчики , а — массивы в ВММ   и .

Рисунок 8а.

Рисунок 8б.

Рисунок 8в.
Если содержательно интерпретировать:
: (цельное положительное  число),
; ввод )),
(ввод)), : (ввод),
 
 
; печать (),
: (печать (),
Область интерпретации —вещественные числа, тогда -план задает алгоритм ввода и сложения массивов и с результатом и печатью, т. е. его термы вырабатывают значения компонентов , равные сумме значений компонентов и . Максимально непроцедурная форма задания этого алгоритма множеством термов плана позволяет (нет запрещающих ограничений) конструировать различные программы, реализующие его.
Выбор конкретного вида программы  определяется количеством ресурсов ЭВМ, выделенных для реализации алгоритма, и функционалом, который характеризует качество программы.
 
 
Глава 2. Аппаратное обеспечение параллельных вычислений.
 
2.1 Классификация  Флинна
Одной из наиболее известных схем классификации компьютерных архитектур является таксономия Флинна, предложенная Майклом Флинном в 1972 году. В ее основу положено описание работы компьютера с потоками команд и данных. В классификации Флинна имеется четыре класса архитектур:
1. SISD (Single Instruction Stream — Single Data Stream) — один поток   команд и один поток данных.
2. SIMD (Single Instruction Stream — Multiple Data Stream) — один  поток команд и несколько потоков данных.
3. MISD (Multiple Instruction Stream — Single Data Stream) — несколько  потоков команд и один поток данных.
4. MIMD (Multiple Instruction Stream — Multiple Data Stream) —  несколько потоков команд и несколько потоков данных.
Рассмотрим  эту классификацию более подробно.
SISD-компьютеры (рис. 9) — это обычные  последовательные компьютеры, выполняющие  в каждый момент времени только  одну операцию над одним элементом  данных. Большинство современных  персональных ЭВМ принадлежат  именно этой категории.
 

Рисунок 9
Многие современные вычислительные системы включают в свой состав несколько  процессоров, но каждый из них работает со своим независимым потоком  данных, относящимся к независимой  программе. Такой компьютер является, фактически, набором SISD-машин, работающих с независимыми множествами данных.
SIMD-компьютеры (рис. 10 и 11) состоят  из одного командного процессора (управляющего модуля), называемого  контроллером, и нескольких модулей обработки данных, называемых процессорными элементами (ПЭ). Количество модулей обработки данных таких машин может быть от 1024 до 16 384. Управляющий модуль принимает, анализирует и выполняет команды. Если в команде встречаются данные, контроллер рассылает на все ПЭ команду, и эта команда выполняется либо на нескольких, либо на всех процессорных элементах. Процессорные элементы в SIMD-компьютерах имеют относительно простое устройство, они содержат арифметико-логическое устройство (АЛУ), выполняющее команды, поступающие из устройства управления (УУ), несколько регистров и локальную оперативную память. Одним из преимуществ данной архитектуры считается эффективная реализация логики вычислений. До половины логических команд обычного процессора связано с управлением процессом выполнения машинных команд, а остальная их часть относится к работе с внутренней памятью процессора

Рисунок 10

Рисунок 11
и выполнению арифметических операций. В SIMD-компьютере управление выполняется  контроллером, а "арифметика" отдана процессорным элементам. Подклассом SIMD-компьютеров  являются векторные компьютеры. Пример такой вычислительной системы — Hitachi S3600.
Другой пример SIMD-компьютера — матричные процессоры (Array Processor). В качестве примера можно привести вычислительную систему Thinking Machines CM-2, где 65 536 ПЭ связаны между собой сетью коммуникаций с топологией "гиперкуб". Часто компьютеры с SIMD-архитектурой специализированы для решения конкретных задач, допускающих матричное представление. Это, например, могут быть задачи обработки изображений, где каждый модуль обработки данных работает на получение одного элемента конечного результата.
MISD-компьютеры. Вычислительных машин такого класса мало. Один из немногих примеров - систолический массив процессоров, в котором процессоры находятся в узлах регулярной решетки. Роль ребер в ней играют межпроцессорные соединения, все ПЭ управляются общим тактовым генератором. В каждом цикле работы любой ПЭ получает данные от своих соседей, выполняет одну команду и передает результат соседям. На рис. 12 дана схема фрагмента систолического массива.

Рисунок 12
MIMD-компьютеры. Этот класс архитектур (рис. 13 и 14) наиболее богат примерами успешных реализаций. В него попадают симметричные параллельные вычислительные системы, рабочие станции с несколькими процессорами, кластеры рабочих станций и т. д. Довольно давно появились компьютеры с несколькими независимыми процессорами, но вначале на них был реализован только принцип параллельного исполнения заданий, т. е. на разных процессорах одновременно выполнялись независимые программы. Разработке первых компьютеров для параллельных вычислений были посвящены проекты под условным названием СМ* и С.ММР в университете Карнеги (США). Технической базой для этих проектов были процессоры DEC PDP-11. В начале 90-х годов прошлого века именно MIMD-компьютеры вышли в лидеры на рынке высокопроизводительных вычислительных систем.

Рисунок 13

Рисунок 14
Классификация Флинна не дает исчерпывающего описания разнообразных архитектур MIMD-машин, порой существенно отличающихся друг от друга. Например, существуют такие  подклассы MIMD-компьютеров, как системы  с разделяемой памятью и системы  с распределенной памятью. Системы  с разделяемой памятью могут  относиться по классификации Флинна как к MIMD, так и к SIMD-машинам. То же самое можно сказать и о  системах с распределенной памятью.
Развитием концепции MIMD-архитектуры  с распределенной памятью является распределенная обработка, когда вместо набора процессоров в одном корпусе используются компьютеры, связанные достаточно быстрой сетью. Концептуального отличия от MIMD-архитектуры с распределенной памятью нет, а особенностью является медленное сетевое соединение.
 
2.2 Основные типы архитектур высокопроизводительных вычислительных систем
SIMD-архитектуры с разделяемой  памятью
SIMD-архитектуры с разделяемой  памятью объединяют векторные  процессоры, VLIW-процессоры и др. В  векторных процессорах часто  нет кэш-памяти, поскольку при  векторной обработке использование  преимуществ кэш-памяти затруднено  и даже может отрицательно  сказываться на производительности (например, вследствие частых переполнений  кэш-памяти).
Современные векторные процессоры используют векторные регистры, а  не прямое обращение к памяти. Разница  в быстродействии небольшая, но векторные  регистры обеспечивают большую гибкость программирования. Если отношение числа  арифметических операций к числу  операций обращения к памяти мало, потери производительности будут большими, вследствие относительно низкой скорости обмена с памятью. Бороться с потерями такого рода можно, наращивая пропускную способность каналов доступа  к памяти, но это сравнительно дорогой  способ, поэтому обычно используются другие, компромиссные способы.
Устройство векторных узлов  может варьироваться в широких  пределах. Каждый узел обычно содержит несколько векторных функциональных устройств. Среди них конвейеры, реализующие функции доступа  к памяти, несколько узлов целочисленной  арифметики и логических операций, сложения и умножения с плавающей  точкой (раздельные и комбинированные), конвейер операций маскирования.
SIMD-машины с распределенной  памятью
SIMD-машины с распределенной памятью  называют также матричными процессорами. В системах с такой архитектурой все процессоры в один и тот же момент времени выполняют одну команду. Имеется управляющий процессор, который передает команды процессорам массива. Обычно есть и "фронтальный" (front-end) процессор, которому отводится функция связи с пользователями, а также выполнение тех операций, которые не могут быть выполнены массивом процессоров (например, операции ввода/вывода). Коммуникационная сеть в таких системах имеет топологию двумерной решетки или, по крайней мере, включает ее в качестве составной части подсистем коммуникации. С помощью логических условий некоторые процессоры можно исключать из процесса обработки данных, переводя их в режим ожидания.
Одной из проблем, связанных с работой  систем с распределенной памятью, является обработка ситуаций, когда данные, необходимые для продолжения  работы определенного процессора, находятся  в локальной памяти другого процессора. Выборка необходимых операндов  и их пересылка по сети требует  значительного времени, поэтому SIMD-машины с распределенной памятью часто  специализированы для решения вполне определенных задач -в этом случае можно добиться наиболее полного использования присущего задаче параллелизма. Имеются специализированные системы для расчетов методом Монте-Карло (таких, где не требуется большой обмен данными между процессорами), обработки изображений и сигналов и т. д.
Управляющий процессор в рассматриваемых  системах должен не только формировать  поток команд и направлять его  процессорам массива, но и решать, какие операции следует "поручить" фронтальному процессору и связанными с ним периферийными устройствами. Такими операциями могут быть, например, печать результатов или их сохранение на магнитном носителе информации. Впрочем, операции ввода/вывода в подобных системах часто реализованы независимо от фронтальной машины, с помощью  специализированных устройств.
MIMD-машины с разделяемой  памятью
Основной проблемой в вычислительных системах такого рода является связь  процессоров между собой и  с памятью. С увеличением числа  процессоров суммарная пропускная способность каналов доступа  к памяти в идеале должна расти  линейно с ростом числа процессоров, а коммуникации между процессорами должны быть, по возможности, прямыми, минуя медленный промежуточный  этап обращения к оперативной  памяти. Обеспечить полную связь сложно, поскольку число коммуникаций растет пропорционально второй степени  числа процессоров.
Тип соединения важен и для синхронизации  выполнения задач на разных процессорах. Большинство векторных процессоров  имеют специальные коммуникационные регистры, с помощью которых решается задача синхронизации с другими  процессорами. Реже используется синхронизация  через разделяемую память. Этот способ более медленный и он подходит для ситуаций, в которых потребность  в синхронизации возникает редко. В системах с использованием шины для синхронизации работы процессоров  применяют специальную шину, отдельную  от шины данных.
MIMD-машины с распределенной  памятью
Это наиболее быстро растущий класс  высокопроизводительных компьютеров. Программирование для таких систем сложнее, чем для MIMD-машин с разделяемой  памятью. В матричных процессорах  основной структурой данных являются массивы, которые хорошо отображаются на структуру машины. В этом случае распределение данных является "прозрачным" для программиста и в значительной степени автоматизировано системным  программным обеспечением. В системах с распределенной памятью, напротив, программист сам должен позаботиться о распределении данных между  процессорами и обмене данными между  ними. Решение проблемы декомпозиции данных и задачи, разработка эффективного параллельного алгоритма часто  оказываются непростым делом.
Значительным преимуществом систем данного класса является отсутствие проблемы ограниченной скорости обмена данными и хорошая масштабируемость. Не так остро стоит и проблема согласования скорости работы процессора и памяти.
В MIMD-машинах с распределенной памятью  часто используется топология "гиперкуб". Теоретически, в сетях с топологией гиперкуба можно имитировать  другие топологии, такие как "дерево", "кольцо", "решетка" и др. Другой эффективной топологией соединения является "толстое дерево". Простое  дерево имеет тот. существенный недостаток, что вблизи его "корня", где пропускная способность относительно невелика, увеличивается концентрация циркулирующих сообщений. В топологии "толстое дерево" используется дублирование связей с высокими уровнями дерева. Пример такой структуры приведен на рис. 15.
У "толстого дерева" пропускная способность у "корня" выше, чем  у "листьев".
Достаточно часто используются коммуникационные матрицы, однокаскад-ные для систем с небольшим числом процессоров (порядка 64) и многокаскадные для систем с большим числом процессоров.
Процессоры используются любые, обычно это RISC-процессоры и векторные процессоры. Часто применяется также специальный  коммуникационный процессор.

Рисунок 15
 
2.3 Основные элементы архитектуры высокопроизводительных вычислительных систем
Архитектура традиционных последовательных компьютеров основана на идеях Джона  фон Неймана и включает в себя центральный процессор, оперативную  память и устройства ввода/вывода. Последовательность команд применяется к последовательности данных. Скорость работы такого компьютера определяется быстродействием его  центрального процессора и временем доступа к оперативной памяти. Быстродействие центрального процессора может быть увеличено за счет увеличения тактовой частоты, величина которой  зависит от плотности элементов  в интегральной схеме, способа их "упаковки" и быстродействия микросхем  оперативной памяти. И, тем не менее, традиционные однопроцессорные системы  не могут обеспечить достаточное  быстродействие для решения сложных  задач. Для моделирования сложных  систем в физике, экономике, биологии, технике, для обработки больших  объемов информации требуется выполнение значительного объема вычислений.
Другие методы повышения  быстродействия основаны на расширениях  традиционной фон-неймановской архитектуры, включающих:
    конвейерную обработку данных и команд;
    использование процессоров с сокращенным набором команд (RISC-процессоров). В RISC-процессорах большая часть команд выполняется за 1—2 такта;
    использование суперскалярных процессоров;
    векторную обработку данных;
    использование процессоров со сверхдлинным командным словом;
    использование многопроцессорных конфигураций.
В этом разделе мы кратко рассмотрим реализацию этих расширений, а также методы и типы межпроцессорных  коммуникаций, особенности организации  оперативной памяти для высокопроизводительных вычислительных систем.
Наиболее перспективным  классом высокопроизводительных систем являются многопроцессорные системы. В организации многопроцессорных  вычислительных систем следует выделить следующие ключевые моменты:
    количество и архитектура индивидуальных процессоров;
    структура и организация доступа к оперативной памяти;
    топология коммуникационной сети и ее быстродействие;
    работа с устройствами ввода/вывода.
Важнейшей характеристикой  многопроцессорной вычислительной системы является ее масштабируемость. Масштабируемость является мерой, которая показывает, можно ли данную проблему решить быстрее, увеличив количество процессорных элементов. Данным свойством обладает как аппаратное, так и программное обеспечение.
 
2.4 Конвейеры
Идея конвейера состоит  в том, чтобы сложную операцию разбить на несколько более простых, таких, которые могут выполняться  одновременно. Операция суммирования, например, включает вычитание порядков, выравнивание порядков, сложение мантисс и нормализацию. Каждая из подопераций может выполняться на отдельном блоке аппаратуры. При движении объектов по конвейеру одновременно на разных его участках (сегментах) выполняются различные подоперации, что дает увеличение производительности за счет использования параллелизма на уровне команд. При достижении объектом конца конвейера он окажется полностью обработанным. Конвейеры применяются как при обработке команд (конвейеры команд), так и в арифметических операциях (конвейеры данных). Поскольку использование конвейерной обработки усложняет конструкцию процессора, эффективным конвейер данных может быть при выполнении векторных операций. Операция над одним элементом данных в конвейере будет выполняться дольше, чем в обычном АЛУ.
Для эффективной реализации конвейера должны выполняться следующие  условия:
    система выполняет повторяющуюся операцию;
    операция может быть разделена на независимые части;
    трудоемкость подопераций примерно одинакова.
Количество сегментов  называют глубиной конвейера. Важным условием нормальной работы конвейера является отсутствие конфликтов, приводящих к простоям конвейера. Для этого объекты, поступающие в конвейер, должны быть независимыми. Если, например, операндом является результат предыдущей операции, возникают периоды работы конвейера ("конвейерные пузыри"), когда он пуст. "Пузырь" проходит по конвейеру, занимая место, но не выполняя при этом никакой полезной работы.
Теоретически, максимально  достижимое увеличение быстродействия, которое можно получить с помощью  конвейера данных, определяется формулой ,
где п — количество операндов, загружаемых в конвейер, d — глубина конвейера.
Цикл выполнения команды  состоит из нескольких шагов:
1. Выборка команды.
2. Декодирование команды,  вычисление адреса операнда и  его выборка.
3. Выполнение команды.
4. Обращение к памяти.
5. Запись результата в  память.
Эти шаги могут выполняться  на устройствах, организованных в конвейер (рис. 16), тогда обработка следующей  команды может начинаться, пока идет обработка предыдущей команды. Для  выполнения каждого этапа команды  отводится один такт и в каждом новом такте начинается выполнение новой команды. Для хранения промежуточных  результатов каждого этапа используется быстрая память (регистры). В результате, в каждом такте будут выполняться  несколько (пять) команд и, несмотря на то, что время выполнения отдельной  команды несколько увеличится, производительность системы в целом возрастет.

Рисунок 16
Для того чтобы задействовать  все  сегментов конвейера, требуется такт. После этого достигается максимальная производительность.
Казалось бы, увеличение числа сегментов будет увеличивать  и скорость выполнения команд, однако с ростом глубины конвейера увеличиваются  затраты времени на передачу информации между сегментами и синхронизацию, возрастает сложность аппаратной части, труднее избежать простоев конвейера.
Простой конвейера команд вызывается ситуацией, когда очередную  команду из потока команд нельзя загрузить  в конвейер сразу, а по какой-либо причине приходится ожидать несколько  тактов. Если очередная команда в  соответствующем ей такте не может  быть выполнена, говорят о конфликте. В этом случае команда ожидает своей очереди, а пропускная способность конвейера падает. Ожидать своей очереди приходится и всем последующим командам. Команды, уже загруженные в конвейер, продолжают выполняться.
Принято выделять три типа конфликтов:
    структурные конфликты;
    конфликты по данным;
    конфликты по управлению.
Причиной структурных конфликтов является одновременный запрос на использование одного ресурса несколькими командами. Избежать частого повторения структурных конфликтов можно, дублируя некоторые ресурсы, используя разделение кэш-памяти для данных и команд и т. д. Однако это усложняет конструкцию процессора и значительно повышает его стоимость.
Конфликты по данным являются следствием логической зависимости команд между собой и происходят, если для выполнения очередной команды требуется результат выполнения предыдущей команды. В этом случае команда не будет выполняться до тех пор, пока предыдущая команда не завершит свое выполнение и не передаст ей свой результат.
Конфликты по управлению вызываются наличием в программах условных конструкций. Выполняемая ветвь условного оператора определяется только после вычисления условия ветвления. Если учесть, что в программах до трети операторов являются ветвлениями, потери производительности вследствие простоев по управлению могут быть большими. Условные переходы труднее поддаются оптимизации, но и здесь имеются способы повышения производительности конвейера при обработке условных переходов.
 
 
 
2.5 Суперскалаярные  процессоры 
Показателем эффективности  работы конвейера является среднее  количество тактов на выполнение команды (CPI — Cycles Per Instruction). Чем меньше эта  величина, тем выше производительность процессора. Идеальной величиной  является 1, однако значение CPI может  быть и меньше единицы, если в одном  такте параллельно выполняются  несколько команд. Параллельное выполнение команд реализовано в суперскалярных процессорах и процессорах со сверхдлинным командным словом.
Это позволяет делать и  конвейер, но при этом команды должны находиться на различных стадиях  обработки (в разных сегментах конвейера). Суперскалярный процессор не только включает возможность конвейерной  обработки, но и позволяет одновременно выполнять несколько команд в  одном сегменте конвейера. Несколько  команд одновременно могут выполняться  в течение одного такта.
Суперскалярные процессоры используют параллелизм на уровне команд путем дублирования функциональных устройств и передачи в них  нескольких команд из общего потока. Прежде всего, используют несколько конвейеров, работающих параллельно. Правда, параллельное выполнение команд в суперскалярных процессорах не всегда возможно. Это  может быть следствием любой из трех причин.
    Конфликты по доступу к ресурсам. Возникают, если несколько команд одновременно обращаются к одному ресурсу. Это может быть регистр, оперативная память или что-нибудь еще. Эта ситуация аналогична структурным конфликтам. Снизить отрицательный эффект подобных ситуаций можно дублированием устройств.
    Зависимость по управлению. У зависимости по управлению есть два аспекта. Первый — это проблемы, связанные с обработкой ветвлений. Второй связан с использованием команд переменной длины. В этом случае выборку следующей команды нельзя сделать, пока не завершено декодирование предыдущей команды. Таким образом, суперскалярная архитектура более всего подходит для RISC-процессоров с их фиксированным форматом и длиной команд.
    Конфликты по данным. Причиной конфликтов по данным являются зависимости по данным между командами, когда очередная операция не может быть выполнена, если ей требуется результат предыдущей операции. Такая зависимость является свойством программы и не может быть исключена компилятором или с помощью каких-то аппаратных решений. Избежать простоев можно, загрузив узлы выполнением других команд, пока формируется результат предыдущей операции.
Для разрешения возможных  конфликтов используют методы внеочередной выборки и завершения команд, прогнозирование  переходов, условное выполнение команд и др.
В суперскалярных процессорах  используется динамическое распределение  команд, причем порядок их выборки  может не совпадать с порядком следования в программе, но при этом, разумеется, результат выполнения должен совпадать с результатом строго последовательного выполнения. Для эффективной реализации данного подхода последовательность команд, из которой производится выборка, должна быть достаточно большой — требуется довольно большое окно выполнения (Window of Execution).
Окно выполнения — это  набор команд, которые являются кандидатами  на выполнение в данный момент. Любая  команда из этого окна может быть взята для исполнения с учетом вышеупомянутых ограничений. Количество команд в окне должно быть максимально  большим.
Основными компонентами суперскалярного  процессора являются устройства для  интерпретации команд, снабженные логикой, позволяющей определить, являются ли команды независимыми, и достаточное  число исполняющих устройств. В  исполняющих устройствах могут  быть конвейеры.
В суперскалярном процессоре в одном такте может выполняться  обработка до восьми команд (например, в процессорах Pentium — две, а в  процессорах UltraSPARC — четыре). Это  значение изменяется в процессе работы, поскольку практически неизбежные конфликты будут приводить к  простоям оборудования. В результате этого производительность суперскалярного  процессора оказывается переменной.
Почти все современные  микропроцессоры, включая Pentium, PowerPC, Alpha и SPARC — суперскалярные. Примером компьютера с суперскалярным процессором является IBM RISC/6000. При тактовой частоте 62,5 МГц  быстродействие системы на вычислительных тестах достигало 104 Мфлоп/с. (Мфлоп/с - "мегафлоп в секунду" единица  измерения быстродействия процессора, составляющая один миллион операций с плавающей точкой в секунду). Суперскалярный процессор не требует  специальных векторизующих компиляторов, хотя компилятор должен в этом случае учитывать особенности архитектуры.
 
2.6 Процессоры с сокращенным набором команд (RISC)
В основе RISC-архитектуры (RISC — Reduced Instruction Set Computer) процессора лежит  идея увеличения скорости его работы за счет упрощения набора команд. Противоположную  тенденцию представляют CISC-архитектуры, процессоры со сложным набором команд (CISC — Complete Instruction Set Computer). Основоположником архитектуры CISC является компания IBM, а  в настоящее время лидером  в данной области является Intel (процессоры Pentium). Идеи RISC-архитектуры использовались еще в компьютерах CDC6600 (разработчики — Крей, Торнтон и др.). Оба варианта относятся к противоположным  границам семантического разрыва — увеличивающегося разрыва между программированием на языках высокого уровня и программированием на уровне машинных команд. В рамках CISC-подхода набор команд включает команды, близкие к операторам языка высокого уровня. В рамках RISC-подхода набор команд упрощается и оптимизируется под реальные потребности пользовательских программ.
В основу RISC-архитектуры  положены следующие принципы и идеи. Набор команд должен быть ограниченным и включать только простые команды, время выполнения которых после  выборки и декодирования один такт или чуть больше. Используется конвейерная обработка. Простые RISC-команды  допускают эффективную аппаратную реализацию, в то время как сложные  команды CISC могут быть реализованы  только средствами микропрограммирования. Конструкция устройства управления в случае RISC-архитектуры упрощается, и это дает возможность процессору работать на больших тактовых частотах. Использование простых команд позволяет  эффективно реализовать и конвейерную  обработку данных, и выполнение команд.
Сложные команды RISC-процессором  выполняются дольше, но их количество относительно невелико. Простые команды CISC-процессором выполняются не очень  быстро, что объясняется сложностью реализации команд в данной архитектуре. В RISC-процессорах небольшое число  команд адресуется к памяти. Выборка  данных из оперативной памяти требует  более одного такта. Большая часть  команд работает с операндами, находящимися в регистрах. Все команды имеют  унифицированный формат и фиксированную  длину. Это упрощает и ускоряет загрузку и декодирование команд, поскольку, например, код операции и поле адреса всегда находятся в одной и  той же позиции. Переменные и промежуточные  результаты вычислений могут храниться  в регистрах. С учетом статистики использования переменных, большую  часть локальных переменных и  параметров процедур можно разместить в регистрах. При вызове новой  процедуры содержимое регистров  обычно перемещается в оперативную  память, однако, если количество регистров  достаточно велико, удается избежать значительной части длительных операций обмена с памятью, заменив их операциями с регистрами. Благодаря упрощенной архитектуре RISC-процессора, на микросхеме появляется место для размещения дополнительного набора регистров. Распределение регистровой памяти под переменные выполняется компилятором.
Несмотря на упомянутые преимущества RISC-архитектуры, нет простого и однозначного ответа на вопрос о том, что лучше  — RISC или CISC. Так, например, для RISC-архитектуры  характерны повышенные требования к  оперативной памяти. Примером CISC-процессора является процессор Pentium (количество команд более 200, длина команды 1—11 разрядов, имеется 8 регистров общего назначения), а в качестве примера RISC-процессора можно привести SunSPARC (количество команд около 50, длина команды 4 разряда, имеется 520 регистров общего назначения).
В настоящее время вычислительные системы с RISC-архитектурой занимают лидирующие позиции на мировом компьютерном рынке рабочих станций и серверов. Развитие RISC-архитектуры связано  с развитием компиляторов, которые  должны эффективно использовать преимущества большого регистрового файла, конвейеризации и т. д.
 
2.7 Процессоры со сверхдлинным командным словом
В суперскалярных процессорах  вопрос о параллелизме команд решается аппаратно, аппаратно реализованы  и методы снижения потерь быстродействия от разного рода зависимостей. Между  суперскалярными процессорами имеется  совместимость программ на уровне исполняемых (бинарных) файлов, добавление новых  параллельных функциональных узлов  может повлиять на выполнение программы  только в сторону увеличения скорости ее выполнения. Но у них есть и  свои недостатки. Это, прежде всего, сложность  аппаратной части, а также ограниченный размер окна выполнения, что уменьшает  возможности определения потенциально параллельных команд.
Альтернативой суперскалярным процессорам являются процессоры со сверхдлинным командным словом (VLIW - Very Large Instruction Word). Работа VLIW-процессора основана на выявлении параллелизма команд во время трансляции. Транслятор анализирует программу, определяя, какие операции могут выполняться  параллельно. Такие операции "упаковываются" в одну большую команду (рис. 17). После  того, как "большая" команда выбрана  из памяти, составляющие ее обычные команды выполняются параллельно. В этом случае решается проблема окна выполнения, поскольку транслятор анализирует всю программу в целом в поисках параллельных операций.

Рисунок 17
Схема VLIW-процессора приведена  на рис. 18.
В VLIW-процессорах количество функциональных узлов можно увеличивать, не усложняя остальную аппаратную часть, что приходится делать в RISC-процессорах.
Вместе с тем, есть и  свои проблемы. Для хранения данных и обслуживания многочисленных функциональных узлов требуется большое количество регистров. Между функциональными  устройствами и регистрами, между  регистрами и оперативной памятью  возникает интенсивный обмен  данными. Кэш-память команд и устройство выборки должен связывать канал  с большой разрядностью — если размер обычной команды 24 бита, а  одно сверхбольшое слово содержит 7 простых команд, в результате получим 168 битов на одну команду. Увеличивается  размер исполняемого кода, теряется совместимость  на уровне бинарных файлов.

Рисунок 18
Эффективность использования  данной архитектуры зависит от качества трансляторов.
В трансляторах для VLIW-процессоров  применяются такие специальные  приемы, как развертка циклов, предсказание ветвлений и планирование выдачи команд. Метод трассировочного планирования заключается в том, что из последовательности обычных команд исходной программы  длинные команды генерируются путем  просмотра (трассировки) линейных (без  ветвлений) участков программы.
 
2.8 Векторная обработка данных
В набор команд векторного процессора входят не только скалярные  команды, но и команды, операндами которых  являются массивы (векторы), поэтому  векторный процессор может обработать одной командой сразу множество  значений. Пусть  и — это три массива, имеющие одинаковую размерность и одинаковую длину, и имеется оператор: .  Векторный процессор за один цикл выполнения команды произведет поэлементное сложение массивов и и присвоит полученные значения соответствующим элементам массива р. Каждый операнд при этом хранится в особом, векторном регистре. Обычному, последовательному процессору пришлось бы многократно исполнить, операцию сложения элементов двух массивов. Векторный процессор выполняет лишь одну команду. Разумеется, реализация такой команды будет более сложной.
Векторные команды:
    загружают операнд из оперативной памяти в векторный регистр;
    записывают операнд из регистра в память;
    выполняют арифметические и логические операции над векторами;
    выполняют другие операции над векторами и скалярами.
Векторный модуль содержит несколько векторных регистров  общего назначения, регистр длины  вектора (для хранения длины обрабатываемого  вектора), регистр маски. Регистр  маски содержит последовательность битов — двоичные разряды вектора, которым соответствуют нулевые  биты маски, в определенных ситуациях  игнорируются при выполнении векторных  операций.
Следует заметить, что именно векторные ЭВМ были первыми высокопроизводительными  компьютерами (векторный компьютер  Сеймора Крэя) и, традиционно, именно ЭВМ с векторной архитектурой назывались суперкомпьютерами.
Векторные компьютеры различаются  тем, как операнды передаются командам процессора. Здесь можно выделить следующие основные схемы:
    из памяти в память — в этом случае операнды извлекаются из оперативной памяти, загружаются в АЛУ и результат возвращается в оперативную память;
    из регистра в регистр — операнды сначала загружаются в векторные регистры, затем операнд передается в АЛУ и результат возвращается в один из векторных регистров.
Преимущество первой схемы  заключается в том, что она  дает возможность работать с векторами  произвольной длины, тогда как во втором случае требуется разбиение  длинных векторов на части, длина  которых соответствует возможностям векторного регистра. С другой стороны, в первом случае имеется определенное время запуска, которое должно пройти между инициализацией команды и появлением в конвейере первого результата. Если конвейер уже загружен, результат на его выходе будет появляться в каждом такте. Примером ЭВМ с такой архитектурой являются компьютеры серии CYBER 200, время запуска у которых составляло до 100 тактов. Это очень большая величина, даже при работе с векторами длиной 100 элементов, вышеупомянутые компьютеры достигали лишь половины от своей максимально возможной производительности.
В векторных компьютерах, работающих по схеме регистр-регистр, длина вектора гораздо меньше. Для компьютеров серии Cray эта длина составляет всего 64 слова, однако, существенно меньшее время запуска позволяет увеличить быстродействие. Правда, если работать с длинными векторами, их приходится разбивать на части меньшей длины, что снижает быстродействие. Векторные компьютеры, работающие по схеме из регистра в регистр, в настоящее время доминируют на рынке векторных компьютеров и наиболее известными представителями этого семейства являются компьютеры фирм Cray, NEC, Fujitsu и Hitachi.
Мультимедийные приложения обычно работают с большими массивами  данных, состоящими из коротких (8- или 16-разрядных) значений с фиксированной  точкой. Такие приложения представляют огромный потенциал векторного (SIMD) параллелизма, поэтому новые поколения  микропроцессоров общего назначения снабжаются мультимедийными командами. Мультимедийные расширения включены в системы команд процессоров Intel (MMX-расширение системы  команд Pentium и новые SIMD-команды Pentium III), AMD (3D Now!), Sun (VIS SPARC), Compaq (Alpha MVI), Hewlett Packard (PA-RISC MAX2), SGI (MDMX), Motorola (PowerPC AltiVec).
 
2.9 Статические топологии
Соединение с помощью  одиночной шины является самым простым  и дешевым (рис. 19). Основной его недостаток заключается в том, что в каждый момент времени возможна только одна пересылка данных/команд. Пропускная способность обратно пропорциональна  количеству процессоров, подключенных к шине. Такой способ соединения хорош только для систем, содержащих не более 10 процессоров.

Рисунок 19
Стандарт IEEE P896 для высокопроизводительной шины, который получил название Scalable Coherent Interface (SCI — масштабируемый когерентный  интерфейс), позволяет отчасти решить проблему сравнительно низкой скорости работы шины, но данное устройство имеет  более сложную организацию, чем  простая шина. Такая шина применялась  в системе HP/Convex SPP-2000.
Более эффективным является другой способ соединения — одномерная решетка. У каждого элемента в  этом случае есть две связи с соседями, а граничные элементы имеют по одной связи (рис. 20). Если замкнуть концы  одномерной решетки, получим топологию "кольцо".

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

Рисунок 21
В топологии "звезда" есть один центральный узел, с которым  соединяются все остальные процессорные элементы. Таким образом, у каждого  ПЭ имеется одно соединение, а у центрального ПЭ — N— I соединение (рис. 22).

Рисунок 22
В такой топологии слабым звеном оказывается центральный  узел, поэтому она тоже не подходит для больших систем.
В сети с полносвязной топологией (рис. 23) все процессорные элементы связаны  друг с другом. Пересылки могут  выполняться одновременно между  различными парами процессорных элементов. В такой системе легко могут  быть реализованы широковещательные  и многоадресные пересылки. Как  быстродействие, так и стоимость системы высоки, причем стоимость существенно возрастает с увеличением числа процессорных элементов.

Рисунок 23.
Довольно распространенной является хорошо масштабируемая топология "гиперкуб" (рис. 24). В ней  процессорных элементов могут быть организованы в -мерный гиперкуб. У каждого ПЭ имеется соединений. Здесь также требуется маршрутизация пакетов с данными, причем максимальное количество промежуточных узлов равно . Оно и определяет максимальную задержку передачи данных.

Рисунок 24
Для адресации узлов в  гиперкубе каждому узлу присваивается  свой идентификационный номер, при  этом двоичные представления идентификационных  номеров соседних узлов отличаются одним разрядом. Алгоритм пересылки  сообщения от одного узла к другому  в этом случае достаточно простой  и основан на побитовом сравнении  двоичных представлений идентификационных  номеров текущего узла и адресата. Например, в 4-мерном гиперкубе связаны ПЭ с номерами 1 (0001), 2 (0010), 4 (0100) и 8 (1000). Такая нумерация узлов называется схемой кода Грея.
 
 
2.10 Динамические топологии
Основным представителем этого класса является перекрестное соединение (рис. 25).
Оно обеспечивает полную связность, т. е. каждый процессор может связаться  с любым другим процессором или  модулем памяти (как на рисунке). Пропускная способность сети при  этом не уменьшается. Схемы с перекрестными  переключениями могут использоваться и для организации межпроцессорных  соединений. В этом случае каждый процессор  имеет собственный модуль памяти (системы с распределенной памятью).
Для соединения процессоров с модулями памяти требуется переключателей. Такая зависимость ограничивает масштабируемость системы (обычно не более 256 узлов).

Рисунок 25
 
2.11 Кластеры рабочих станций
Кластеры рабочих станций  представляют собой совокупность рабочих  станций, соединенных в локальную  сеть, обычно, в масштабе отдела, факультета или института. Такой кластер  можно считать вычислительной системой с распределенной памятью и распределенным управлением. Кластерная система, при  относительно невысокой стоимости, может обладать производительностью, сравнимой с производительностью  суперкомпьютеров. Ведь часто оказывается, что рабочие станции, роль которых  могут играть персональные компьютеры, закуплены и установлены и не всегда загружены работой, так почему бы не превратить их в виртуальный вычислительный комплекс? Необходимое для работы параллельного кластера программное обеспечение — бесплатное, в том числе и операционная система. Еще одним из преимуществ такой, в общем случае гетерогенной (разнородной) вычислительной системы может быть то, что отдельные части параллельных программ могут выполняться на наиболее подходящих для этого компьютерах.
Для того чтобы построить  работоспособный параллельный кластер, необходимо решить ряд проблем. Прежде всего, следует иметь в виду, что  довольно часто в сеть объединяются компьютеры различных фирм-производителей, имеющие разную архитектуру, работающие под управлением разных операционных систем, имеющих разные файловые системы  и т. д. То есть возникает проблема совместимости. Имеется и проблема доступа, т. к. для входа в любой  компьютер может потребоваться  разрешение работать на нем. Может быть и так, что время счета измеряется днями, а то и неделями, а некоторые  из рабочих станций кластера время  от времени должны быть загружены  своей собственной работой. Следовательно, особенно важным оказывается управление такой вычислительной системой, динамичной и специфической.
Кластеры рабочих станций  обычно называют Беовульф-кластерами (Beowulf cluster — по одноименному проекту). Типичный современный Беовульф-кластер представляет собой кластер рабочих станций, связанных локальной сетью Ethernet и обычно работающих под управлением ОС Linux, хотя в настоящее время разнообразие Беовульф-кластеров достаточно велико.
Взаимодействие компьютеров  в кластере может быть организовано с помощью сети Ethernet 10 или 100 Мбит/с. Это наиболее экономичное решение, но не самое эффективное (время отклика  около 100 микросекунд). Сеть на основе Gigabit Ethernet имеет пропускную способность  на порядок больше. Имеются и другие возможности, это сети Myrinet, Giganet cLAN и SCI (время отклика 10—20 микросекунд). Наибольшая пропускная способность  у сети SCI (до 500 Мбит/с), поэтому данный вариант часто используется в  кластерах. Кластерные системы можно  отнести к MIMD-системам с распределенной памятью.
 
2.12 Примеры архитектур суперкомпьютеров
Архитектура суперкомпьютера NEC SX-4
NEC SX-4 1996 года выпуска (NEC — японская фирма, один из  крупнейших производителей суперкомпьютеров), является параллельно-векторным  компьютером с двухступенчатой  архитектурой. Основным строительным  блоком является узел, содержащий  до 32 процессоров с общей пиковой  производительностью 64 Гфлоп/с. Процессоры  в узле соединяются посредством  коммутационной матрицы с 1024 банками  памяти общим объемом до 16 Гбайт.  Кроме того, каждый узел (рис. 1.26) поддерживает до 4 модулей расширенной  памяти (XMU — Extended Memory Unit) с суммарным объемом до 32 Гбайт оперативной памяти и 4 процессорами ВВ (IOР — I/O Processor).
Каждый процессор состоит  из векторного модуля, скалярного модуля и модуля обработки команд. Тактовая частота относительно невелика — 125 МГц. Векторный модуль развивает  максимальное быстродействие 2 Гфлоп/с. Скалярный модуль имеет обычную суперскалярную архитектуру с той же тактовой частотой, что и векторный модуль, и максимальное быстродействие 250 Мфлоп/с. Процессор поддерживает форматы представления чисел с плавающей точкой IEEE, Cray и IBM, а пользователь может выбрать тип используемой арифметики во время трансляции программы.
Compaq AlphaServer SC
Эта система 1999 года выпуска  представляет собой симметричную многопроцессорную  систему с распределенной памятью, RISC-архитектурой и коммутационной матрицей. Программное обеспечение — ОС Digital UNIX, трансляторы для языков FORTRAN, High-Performance FORTRAN (HPF), С и C++. Тактовая частота 833 МГц, максимальный размер оперативной памяти 2 Тб и максимальное число процессоров 512. Скорость обмена между процессором и памятью 1,33 Гбайт/с и между ПЭ 210-Мбайт/с. Теоретическое максимальное быстродействие каждого процессора 1,67 Гфлоп/с, а всей системы 853 Гфлоп/с.
Каждый узел представляет собой 4-процессорную симметричную систему (Compaq ES40). Процессоры — Alpha 21264a (EV67). В каждом узле используется коммуникационная матрица с пропускной способностью 5,2 Гбайт/с и разделяемая память. Узлы собраны в кластер и соединяются сетью QsNet (SQW Ltd.) с топологией "толстого дерева".
Если для выполнения параллельной программы достаточно не более четырех  процессоров, можно использовать модель программирования с разделяемой  памятью (например, с использованием ОрепМР).
Архитектура суперкомпьютера Cray SX-6
В 2001 году фирма Cray Inc. совместно  с NEC выпустила на рынок масштабируемый, параллельно-векторный суперкомпьютер Cray SX-6, один из наиболее мощных современных  суперкомпьютеров. Cray SX-6 представляет собой симметричную мультипроцессорную систему, строительными блоками  которой являются параллельно-векторные  процессорные узлы. Узлы состоят из нескольких (от двух до восьми) векторных  процессоров, максимальное быстродействие каждого из них составляет 8 Гфлоп. Каждый процессор имеет доступ к  разделяемой высокопроизводительной памяти объемом от 16 до 64 Гбайт и  скоростью передачи данных 256 Гбайт/с. Конфигурации, состоящие из нескольких узлов, развивают максимальное быстродействие до 8 Тфлоп (один триллион операций с  плавающей точкой в секунду), имеют  оперативную память объемом 8 Тбайт  и скорость обмена данными с устройствами ВВ 800 Гбайт/с.
Cray T3E (1350)
Это мультипроцессорная вычислительная система 2000 года выпуска, с распределенной памятью построена из RISC-процессоров. Топология коммуникационной сети —  трехмерный тор. Операционная система UNICOS/mk (ОС UNIX с микроядром). Трансляторы  для языков FORTRAN, HPF, C/C++. Тактовая частота 675 МГц. Количество процессоров от 40 до 2176.
Максимальный объем оперативной  памяти для каждого узла 512 Мбайт  и максимальное быстродействие 2938 Гфлоп/с. В отличие от предшественника — Cray T3D, данной системе не требуется фронтальный компьютер.
В системе используется процессор Alpha21164A, однако, при необходимости, его  несложно заменить другим, например, более  быстродействующим процессором. Пропускная способность канала связи между  процессорами 325 Мбайт/с.
Поддерживаются модели программирования MPI, PVM, HPF, собственная библиотека обмена сообщениями Cray shmem. Быстродействие, полученное при решении систем линейных алгебраических уравнений, достигает 1,12 Тфлоп/с.
Cray MTA-2
Это мультипроцессорная система  с распределенной памятью, 2001 года выпуска. Работает под управлением ОС BSD. Количество процессоров до 256. В данной системе  используется многопоточная архитектура. При выполнении программы поток  команд разбивается на части, которые  могут обрабатываться одновременно. Если, например, обращение к памяти в каком-либо из потоков не может быть выполнено, этот поток приостанавливается, а вместо него активизируется другой поток. Коммуникационная сеть представляет собой трехмерный куб. Каждый узел имеет собственный порт ввода/вывода. Параллелизм в многопоточной архитектуре выявляется и реализуется автоматически, однако в системе Cray MTA-2 могут использоваться и явные модели параллельного программирования.
 
 
 
 
 
 
 
 
 
Глава 3. Практическое применение методов параллельных вычислений.
 
3.1 Языки параллельного  программирования
Применение параллельных архитектур повышает производительность при решении задач, явно сводимых к обработке векторов. Но автоматические методы распараллеливания редко способны обеспечить значительное ускорение вычислений. Более успешным может быть выражение языковыми средствами параллелизма на уровне постановки задачи. В таком случае при оптимизирующей компиляции возможен аккуратный выбор эффективной схемы параллелизма.
И в настоящее время  для большинства специализированных языков параллельного программирования типично. В результате можно независимо варьировать структуры данных, функционалы (функции высших порядков), методы сборки полного результата отображения и набор отображаемых множеств. Языки параллельного программирования занимают видное место среди функциональных языков.
Рассмотрим кратко основные языки и их расширения.
Fortran
Fortran — первый реализованный  язык программирования высокого  уровня, правда, с одной небольшой  оговоркой — для машин, построенных  по классической схеме фон  Неймана. Фортран широко используется  в первую очередь для научных  и инженерных вычислений. Одно  из преимуществ современного  Фортрана — большое количество  написанных на нём программ  и библиотек подпрограмм. 
Диалекты языка Fortran: Fortran-DVM, Cray MPP Fortran, F--, Fortran 90/95, Fortran D95, Fortran M, Fx, HPF, Opus, Vienna Fortran.
Fortran D95 - экспериментальный  язык программирования, основанный  на HPF. Расширения направлены на  поддержку основных классов параллельных  приложений, работающих с большими  массивами данных, нерегулярными  и разреженными матрицами и  т.д. 
Fortran M - небольшой набор  расширений языка Fortran, предоставляющих  возможность модульной разработки  последовательных и параллельных  программ. Есть средства порождения  процессов и их коммуникации  путем посылки сообщений. 
HPF - дальнейшее развитие языка Fortran 90. Включены богатые средства для распределения данных по процессорам. Необходимые коммуникации и синхронизации реализуются компилятором. Часть расширений реализована в виде функций и операторов языка, а часть - в виде директив компилятору.
Vienna Fortran 90 - дальнейшее развитие языка Fortran 90. Включает в себя многочисленные возможности распределения массивов данных по секциям процессорных массивов, а также распределения итераций циклов.
C/C++
Си— стандартизированный процедурный язык программирования, разработанный в начале 1970-х годо. Си был создан для использования в операционной системе UNIX. Для языка Си характерны современный набор конструкций управления потоком выполнения, структур данных и обширный набор операций.
C++ — компилируемый статически  типизированный язык программирования  общего назначения. В сравнении  с его предшественником — языком C, — наибольшее внимание уделено  поддержке объектно-ориентированного  и обобщённого программирования.
Charm/Charm++ - параллельные расширения  языков C и C++ соответственно. Программы,  написанные с их использованием, могут выполняться на компьютерах как с общей, так и с распределенной памятью.
Cilk - язык программирования  с поддержкой многопоточности,  базирующийся на языке C. Программист  должен заботиться о задании  максимального параллелизма, а его  использование и конкретную загрузку  процессоров определяет Cilk runtime system.
HPC - проект, разрабатываемый в CRIM (Centre de Recherche Informatique de MontrВal). Цель проекта - создание на основе языка C средства для поддержки параллельных вычислений на большом количестве различных платформ. Параллельные расширения языка строятся по аналогии с языком HPF.
MPL - объектно-ориентированный  язык программирования, базирующийся  на языке C++. Распределение данных  задается программистом, а все  необходимые пересылки и синхронизации  определяются компилятором и  осуществляются во время исполнения  с помощью Mentat run-time system.
mpC - язык программирования, основанный на языках C и C, предоставляющий  средства создания параллельных  программ для компьютеров с  распределенной памятью.  Посылка  сообщений организована с использованием  интерфейса MPI.
MPC++ - расширение языка  C++, предназначенное для написания  параллельных программ. Каждому  процессору параллельного компьютера  сопоставляется один процесс,  который в свою очередь может  состоять из нескольких потоков.
Adl
Adl - функциональный язык  с небольшим числом конструкций  и типов данных, разработанный  для написания параллельных программ. Ориентирован на программирование абстрактной машины с распределенной памятью.
Ada
Ada - универсальный язык  программирования, включающий в  себя средства для создания  параллельных программ. Официальный  язык программирования министерства  обороны США. Существует множество  компиляторов для самых разных  платформ.
MC#
MC# - новый проект по  созданию асинхронного параллельного  языка программирования MC#, ориентированного  на кластерные и GRID-архитектуры,  который позволил бы использовать  все преимущества языка C# в  параллельном программировании.
DVM
DVM-система предназначена для создания переносимых и эффективных вычислительных приложений на языках C-DVM и Fortran-DVM для параллельных компьютеров с различной архитектурой.  Аббревиатура DVM соответствует двум понятиям: Distributed Virtual Memory и Distributed Virtual Machine.
Linda
Linda - параллельный язык  программирования. Программа рассматривается  как совокупность процессов, которые  могут обмениваться данными через  пространство кортежей. В чистом  виде практически не встречается,  чаще всего используется совместно  с другими языками высокого  уровня как средство общения  параллельных процессов. 
NESL
NESL - язык параллельного  программирования, созданный с целью как написания параллельных программ, так и обучения. Поддерживает параллелизм по данным, позволяя задавать параллельное выполнение любых функций над однотипными данными.
Occam
Orca - язык параллельного  программирования для компьютеров  с распределенной памятью. Предоставляет  средства динамического порождения  процессов и отображения их  на процессоры, а также коммуникации  процессов при помощи разделяемых  объектов.
Sisal
Sisal - функциональный язык  программирования. Программист не  заботится о параллельных свойствах  программ, компилятор определяет  все зависимости, распределяет  работу по процессорам, вставляет  необходимые пересылки и синхронизации. 
ZPL
ZPL - параллельный язык  программирования. Включает в себя  возможности операций на целыми массивами и секциями массивов. Программист не задает никакого параллелизма, все параллельные свойства извлекаются компилятором.
 
3.2 Технологии  параллельного программирования
 
Введение в  технологию Open MP
В технологии Open MP за основу берется последовательная программа. Для создания параллельной версии пользователю представляются наборы:
1) директив,
2) процедур,
3) переменных окружения.
Стандарт Open MP разработан для языков Fortran и C (Fortran 77, 90, 95 и C, C++) и поддерживается производителями всех больших параллельных систем. Реализации стандарта доступны в UNIX и в среде Windows NT.
Конструкции Open MP в различных  языках мало отличаются, поэтому ограничимся языком Fortran.
Распараллеливание программы  состоит в том, чтобы весь текст  разбить на последовательные и параллельные области. В начальный момент порождается  нить-мастер (или основная нить), которая  начинает выполнение программы со стартовой  точки. Основная нить и только она  исполняет все последователь ные области секции программы.
Для поддержки параллелизма используется схема
FORK/JOIN.
При входе в параллельную область основная нить порождает  дополнительные нити (выполняется операция FORK). После порождения дополнительные нити нумеруются последовательными натуральными числами, причем основная нить имеет номер 0; таким образом, каждая нить получает свой уникальный номер. Все порожденные нити выполняют одну и ту же программу, соответствующую параллельной области. При выходе из параллельной области основная нить дожидается завершения работы остальных нитей (выполняется операция JOIN), и дальнейшее выполнение программы осуществляется основной нитью.
В параллельной области все  переменные в программе делятся  на два класса:
1) общие (shared – разделяемые);
2) локальные (private – собственные).
Общие переменные существуют в одном экземпляре для всей программы  и под одним и тем же именем доступны всем нитям. Объявление локальной  переменной приводит к порождению многих экземпляров (по числу нитей) этой переменной под этим именем – по одному собственному экземпляру для каждой нити. Изменение  какой-либо нитью значения своего экземпляра локальной переменной никак не влияет на изменение значений экземпляров  этой переменной в других нитях.
Понятия областей программы  и классов переменных вместе с  порождением (расщеплением) и уничтожением (соединением) нитей определяют общую  идею написания программы с использованием технологии Open MP. Все директивы Open MP располагаются в комментариях и начинаются с одной из следующих комбинаций !$OMP, C$OMP или*$OMP (по правилам языка Fortran строки, начинающиеся с символов !,С или *, означают комментарии).
Все переменные окружения  и функции, реализующие стандарт Open MP, начинаются с префикса OMP_.
Описание параллельных областей: для такого описания используются две  директивы
!$OMP PARALLEL
< параллельная область  программы >
!$OMP END PARALLEL
Для выполнения фрагмента  программы, расположенного между данными  директивами, основная нить порождает  нити в количестве OMP_NUM_THREADS-1, где OMP_NUM_THREADS переменная окружения, значение которой пользователь задаёт перед запуском программы. Все порожденные нити исполняют программу, находящуюся между указанными директивами.
На директиве !$OMP END PARALLEL происходит неявная синхронизация нитей: сначала все нити достигают директиву!$OMP END PARALLEL, и лишь после этого происходит слияние всех нитей в основную нить, которая и продолжает процесс.
В параллельной области каждой имеющейся нитью может быть порождена  параллельная секция (порождение нитью  параллельных нитей) и последующее  их соединение (с сохранением главенства порождающей нити). Число нитей  в параллельной секции можно задавать с помощью функции OMP_SET_NUM_THEADS, которая устанавливает значение переменной OMP_ NUM_THEADS(при этом значения переменной OMP_DYNAMIC должно быть установлено в 1 с помощью функции OMP_SET_DYNAMIC). Стратегию обработки вложенных секций можно менять с помощью функции OMP_SET_NESTED.
Необходимость порождения нитей  и параллельного исполнения может  определяться динамически в ходе исполнения программы с помощью  условия IF:
!$OMP PARALLEL IF (< условие >).
Если < условие > не выполнено, то директива не выполняется и  программа обрабатывается в прежнем  режиме.
Распределение работы в Open MP можно проводить следующими способами:
1) программировать на  низком уровне;
2) использовать директиву !$OMP DO для параллельного выполнения циклов;
3) использовать директиву!$OMP SECTIONS для параллельного выполнения  независимых фрагментов программы;
4) применить директиву !$
и т.д.................


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.