Виды параллелизма. Параллельная обработка данных на эвм

">Лекция " xml:lang="en-US" lang="en-US">6

">Параллельная обработка данных

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

В основу параллельной обработки могут быть положены различные принципы:

Пространственный параллелизм;

Временной параллелизм:

1. Конвейеризация.
2. ">Векторизация.
3. ">Матричный.
4. ">Систолический.
5. ">Организация структуры обработки потока данных.
6. ">Организация системы на основе структуры гиперкуб.
7. ">Динамическая перестройка структуры ВС.

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

">1. Ярусно-параллельная форма алгоритма

">Наиболее общей формой представления алгоритмов является информационно-управляющий граф алгоритма. Более определенной формой представления параллелизма задач является аппарат ярусно-параллельной формы (ЯПФ).

">Алгоритм в ярусно-параллельной форме представляется в виде ярусов, причем в нулевой ярус входят операторы (ветви) независящие друг от друга.

">На графе можно обозначить переходы, означающие передачу результатов вычисления примитивной операции из одного яруса к операции из следующего яруса. Ярусы делятся по переходам. Могут быть «пустые» переходы и «пустые» примитивные операции.

">При построении ЯПФ опираются на базовый набор примитивных операций (БНО). Ярусно-параллельная форма характеризуется следующими параметрами:

">1. Длина графа (количество ярусов) – " xml:lang="en-US" lang="en-US">L ">.

">2. Ширина " xml:lang="en-US" lang="en-US">i ">-го яруса - " xml:lang="en-US" lang="en-US">b ;vertical-align:sub" xml:lang="en-US" lang="en-US">i ">.

">3. Ширина графа ярусно-параллельной формы – " xml:lang="en-US" lang="en-US">B ">= " xml:lang="en-US" lang="en-US">max ">(" xml:lang="en-US" lang="en-US">b ;vertical-align:sub" xml:lang="en-US" lang="en-US">i ">).

">4. Средняя ширина графа ЯПФ – В ;vertical-align:sub">ср "> – ">.

">5. Коэффициент заполнения " xml:lang="en-US" lang="en-US">i ">-го яруса – " xml:lang="en-US" lang="en-US">k ;vertical-align:sub" xml:lang="en-US" lang="en-US">i "> – ">.

">6. Коэффициент разброса операций в графе - " xml:lang="en-US" lang="en-US">Q ;vertical-align:super" xml:lang="en-US" lang="en-US">j ;vertical-align:sub" xml:lang="en-US" lang="en-US">i "> – ">, " xml:lang="en-US" lang="en-US">j ">БНО, где ">- количество " xml:lang="en-US" lang="en-US">j ">-го типа операций в " xml:lang="en-US" lang="en-US">i ">-м ярусе.

">7. Минимальное необходимое количество вычислителей (из БНО) для реализации алгоритма, представленного данным графом в ЯПФ.

">8. Минимальное время решения алгоритма (сумма времен срабатывания вычислителей с максимальным объемом вычислений по каждому ярусу) – Т ;vertical-align:sub" xml:lang="en-US" lang="en-US">min ">.

">9. Связность алгоритма (количество промежуточных результатов, которое необходимо хранить в процессе реализации алгоритма) – С.

">2. Автоматическое обнаружение параллелизма

">Возможны два пути построения параллельного алгоритма: непосредственно из постановки задачи или путем преобразования последовательного алгоритма.

">Методы построения параллельного алгоритма из последовательного основаны на выделении в последовательном алгоритме типовых часто встречающихся конструкций, которые по определенным правилам заменяются параллельными.

">Несмотря на меньший уровень параллелизма, достигаемый при построении параллельного алгоритма путем преобразования из последовательного, такой метод находит широкое применение, так как обеспечивает возможность использовать дорогостоящие прикладные программы, разработанные и отлаженные для последовательных СОД.

">В последовательной программе различают явную и скрытую параллельную обработку.

">При анализе программы строится граф потока данных. Чтобы обнаружить явную параллельность процессов, анализируются множества входных (считываемых) переменных " xml:lang="en-US" lang="en-US">R "> и выходных (записываемых) переменных " xml:lang="en-US" lang="en-US">W "> каждого процесса.

">Скрытая параллельная обработка требует некоторой процедуры преобразования последовательной программы, чтобы сделать возможным ее параллельное выполнение. Преобразование может быть следующим:

">а) уменьшение высоты деревьев арифметических выражений (рис.6.3);

">б) преобразование линейных рекуррентных соотношений;

">в) замена операторов;

">г) преобразование блоков условных переходов и циклов к каноническому виду;

">д) распределение циклов.

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

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

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

">3. Степень и уровни параллелизма

">Степень параллелизма "> (" xml:lang="en-US" lang="en-US">D ">) "> – это порядок числа параллельно работающих устройств в системе при реализации алгоритма задач, при условии, что количество процессоров (обрабатывающих устройств) не ограничено.

">1) Низкая степень: от 2 до 10 процессоров.

">2) Средняя степень: от 10 до 100 процессоров.

">3) Высокая степень: от 100 до 10 ;vertical-align:super">4 "> процессоров.

">4) Сверхвысокая степень: от 10 ;vertical-align:super">4 "> до 10 ;vertical-align:super">6 "> процессоров.

">Графическое представление параметра " xml:lang="en-US" lang="en-US">D ">(" xml:lang="en-US" lang="en-US">t ">) как функции времени называют профилем параллелизма программы. На рис.6.5 показан типичный профиль параллелизма.

">В прикладных программах имеется широкий диапазон потенциального параллелизма. В вычислительно интенсивных программах в каждом цикле параллельно могут выполнятся от 500 до 3500 арифметических операций, если для этого имеется существующая вычислительная среда. Однако даже правильно спроектированный суперскалярный процессор способен поддерживать от 2 до 5,8 команды за цикл. Такое падение связано в первую очередь с коммуникационными и системными издержками.

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

Рассматривают алгоритмический и схемный уровни параллелизма.

Выделяют следующие алгоритмические уровни параллелизма:

1. Уровень заданий:

а) между заданиями;

б) между фазами заданий.

2. Программный уровень:

а) между частями программы;

б) в пределах циклов.

3. Командный уровень (между фазами выполнения команд).

4. Арифметический и разрядный уровень:

">а) между элементами векторной операции;

">б) внутри логических схем АЛУ.

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

">Схемный уровень параллелизма – это аппаратный уровень, на котором осуществляется распараллеливание обработки данных или организация параллельных вычислений.

">Параллельная обработка может быть реализована на следующих схемных уровнях:

">1. На уровне логических вентилей и элементов памяти (рис.6.6).

">2. Уровень логических схем и простых автоматов с памятью (рис.6.7).

">3. Уровень регистров и интегральных схем памяти (рис.6.8).

4. Уровень элементарных микропроцессоров (рис.6.9).

">5. Уровень макропроцессоров, реализующих крупные операции (рис.6.10).

6. Уровень вычислительных машин, процессоров и программ (рис.6.11).

">4. Виды параллелизма

">4.1. Естественный параллелизм и

">параллелизм множества объектов

В информационном графе могут быть выделены «вертикальные» независимые подграфы, которые не используют взаимно каких-либо промежуточных результатов, полученных при реализации примитивных операций другого подграфа. Такой вид параллелизма получил название естественного параллелизма независимых задач.

Задача обладает естественным параллелизмом, если в её исходной постановке она сводится к операции над многомерными векторами, многомерными матрицами или над решётчатыми функциями (рис.6.12).

Параллелизм множества объектов представляет собой частный случай естественного параллелизма. Его смысл в том, что задача состоит в обработке информации о различных, но однотипных объектах, обрабатываемых по одной и той же или почти по одной и той же программе (рис.6.13).

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

">4.2. Параллелизм независимых ветвей

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

">Ветвь программы Y не зависит от ветви X, если:

">- между ними нет функциональных связей, т.е. ни одна из входных переменных ветви Y не является выходной переменной ветви X либо какой-нибудь ветви, зависящей от X;

">- между ними нет связи по рабочим полям памяти;

">- они должны выполняться по разным программам;

">- независимы по управлению, т.е. условие выполнения ветви Y не должно зависеть от признаков, вырабатываемых при выполнении ветви X или ветви, от нее зависящей.

">4.3. Параллелизм смежных операций или

">локальный параллелизм

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

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

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

">5. Модель задачи

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

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

1. скалярных участков (СК);
2. участков с параллелизмом независимых ветвей (ВТ);
3. векторных участков (ВК).

Модель задачи – это совокупность параметров, характеризующих параллельную программу

При построении модели задачи главная цель – определение относительного времени ее выполнения при реализации исследуемым алгоритмом.

">Рис.6.15. Соотношение общего числа вычислений, приходящихся на разные участки алгоритма в модели задачи

" xml:lang="en-US" lang="en-US">W ">ск

" xml:lang="en-US" lang="en-US">Wвт

" xml:lang="en-US" lang="en-US">W ">вк

" xml:lang="en-US" lang="en-US">m ;vertical-align:sub">ск

" xml:lang="en-US" lang="en-US">m ;vertical-align:sub" xml:lang="en-US" lang="en-US">вт

" xml:lang="en-US" lang="en-US">m ;vertical-align:sub">вк

" xml:lang="en-US" lang="en-US">А

" xml:lang="en-US" lang="en-US">В

" xml:lang="en-US" lang="en-US">C

объем вычислений

относительная длина

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

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

Параллельная обработка - модель выполнения прикладного процесса одновременно группой процессоров. Различают три способа реализация параллелизма:
-1- способ SIMD работы с одним потоком команд и несколькими потоками данных, при котором все процессоры, работающие по одной программе, обрабатывают собственные массивы данных под управлением ведущего процессора;
-2- способ MIMD работы с несколькими потоками команд и несколькими потоками данных, при котором процессоры работают по своим программам независимо друг от друга, лишь эпизодически связываясь друг с другом;
-3- способ MISD работы с несколькими потоками команд и одним потоком данных.

По-английски: Parallel processing

Финансовый словарь Финам .

Смотреть что такое "Параллельная обработка" в других словарях:

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

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

параллельная обработка - — Тематики электросвязь, основные понятия EN parallel processing …

параллельная обработка - lygiagretusis apdorojimas statusas T sritis automatika atitikmenys: angl. parallel processing vok. Parallelverarbeitung rus. параллельная обработка, f pranc. traitement en parallèle, m … Automatikos terminų žodynas

параллельная обработка информации - модель обработки информации в мозге головном, согласно коей информация проходит ряд преобразований в определенных «функциональных блоках» мозга так, что в каждый момент времени ее обработка ведется одновременно (параллельно) в нескольких… … Большая психологическая энциклопедия

ПАРАЛЛЕЛЬНАЯ ОБРАБОТКА ИНФОРМАЦИИ - См. обработка информации, параллельная …

Способ параллельной обработки данных большим числом процессоров, реализующий способ организации параллелизма MIMD. По английски: Massively Parallel Processing Синонимы английские: MPP См. также: Параллельная обработка Финансовый словарь Финам … Финансовый словарь

ОБРАБОТКА, ПАРАЛЛЕЛЬНАЯ - Обработка информации, при которой более чем одна последовательность операций по обработке проводятся одновременно, или параллельно. Обработка может включать чрезвычайно низкий уровень, несимволические компоненты, такие, которые используются в… … Толковый словарь по психологии

параллельная конвейерная обработка - lygiagretusis konvejerinis apdorojimas statusas T sritis radioelektronika atitikmenys: angl. parallel pipelining vok. Parallel Pipelineverarbeitung, f rus. параллельная конвейерная обработка, f pranc. traitement de pipeline parallèle, m … Radioelektronikos terminų žodynas

одновременная обработка - параллельная обработка — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом Синонимы параллельная обработка EN simultaneous processing … Справочник технического переводчика

Книги

• Параллельная обработка данных
• Параллельная обработка данных , А. О. Лацис. В учебном пособии дан углубленный систематический обзор технологий параллельной обработки данных. Основное внимание уделено традиционным программным технологиям параллельного программирования…

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

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

Параллельные ЭВМ часто подразделяются по классификации Флинна на машины типа SIMD (Single Instruction Multiple Data - с одним потоком команд при множественном потоке данных) и MIMD (Multiple Instruction Multiple Data - с множественным потоком команд при множественном потоке данных). Как и любая другая, приведенная выше классификация несовершенна: существуют машины прямо в нее не попадающие, имеются также важные признаки, которые в этой классификации не учтены. В частности, к машинам типа SIMD часто относят векторные процессоры, хотя их высокая производительность зависит от другой формы параллелизма - конвейерной организации машины. Многопроцессорные векторные системы, типа Cray Y-MP, состоят из нескольких векторных процессоров и поэтому могут быть названы MSIMD (Multiple SIMD).

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

Можно выделить четыре основных типа архитектуры систем параллельной обработки:

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

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

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

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

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

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

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

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

4) Многопроцессорные машины с SIMD-процессорами.

Многие современные супер-ЭВМ представляют собой многопроцессорные системы, в которых в качестве процессоров используются векторные процессоры или процессоры типа SIMD. Такие машины относятся к машинам класса MSIMD.

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

Многопроцессорные системы за годы развития вычислительной техники претерпели ряд этапов своего развития. Исторически первой стала осваиваться технология SIMD. Однако в настоящее время наметился устойчивый интерес к архитектурам MIMD. Этот интерес главным образом определяется двумя факторами:

1. Архитектура MIMD дает большую гибкость: при наличии адекватной поддержки со стороны аппаратных средств и программного обеспечения MIMD может работать как однопользовательская система, обеспечивая высокопроизводительную обработку данных для одной прикладной задачи, как многопрограммная машина, выполняющая множество задач параллельно, и как некоторая комбинация этих возможностей.
2. Архитектура MIMD может использовать все преимущества современной микропроцессорной технологии на основе строгого учета соотношения стоимость/производительность. В действительности практически все современные многопроцессорные системы строятся на тех же микропроцессорах, которые можно найти в персональных компьютерах, рабочих станциях и небольших однопроцессорных серверах.

Одной из отличительных особенностей многопроцессорной вычислительной системы является сеть обмена, с помощью которой процессоры соединяются друг с другом или с памятью. Модель обмена настолько важна для многопроцессорной системы, что многие характеристики производительности и другие оценки выражаются отношением времени обработки к времени обмена, соответствующим решаемым задачам. Существуют две основные модели межпроцессорного обмена: одна основана на передаче сообщений, другая - на использовании общей памяти. В многопроцессорной системе с общей памятью один процессор осуществляет запись в конкретную ячейку, а другой процессор производит считывание из этой ячейки памяти. Чтобы обеспечить согласованность данных и синхронизацию процессов, обмен часто реализуется по принципу взаимно исключающего доступа к общей памяти методом "почтового ящика".

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

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

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

Таким образом, существующие MIMD-машины распадаются на два основных класса в зависимости от количества объединяемых процессоров, которое определяет и способ организации памяти и методику их межсоединений.

К первой группе относятся машины с общей (разделяемой) основной памятью, объединяющие до нескольких десятков (обычно менее 32) процессоров. Сравнительно небольшое количество процессоров в таких машинах позволяет иметь одну централизованную общую память и объединить процессоры и память с помощью одной шины. При наличии у процессоров кэш-памяти достаточного объема высокопроизводительная шина и общая память могут удовлетворить обращения к памяти, поступающие от нескольких процессоров. Поскольку имеется единственная память с одним и тем же временем доступа, эти машины иногда называются UMA (Uniform Memory Access). Такой способ организации со сравнительно небольшой разделяемой памятью в настоящее время является наиболее популярным. Структура подобной системы представлена на рис. 10.1.

Рис. 10.1. Типовая архитектура мультипроцессорной системы с общей памятью.

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

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

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

Обычно устройства ввода/вывода, также как и память, распределяются по узлам и в действительности узлы могут состоять из небольшого числа (2-8) процессоров, соединенных между собой другим способом. Хотя такая кластеризация нескольких процессоров с памятью и сетевой интерфейс могут быть достаточно полезными с точки зрения эффективности в стоимостном выражении, это не очень существенно для понимания того, как такая машина работает, поэтому мы пока остановимся на системах с одним процессором на узел. Основная разница в архитектуре, которую следует выделить в машинах с распределенной памятью заключается в том, как осуществляется связь и какова логическая модель памяти.

Рис. 10.2. Типовая архитектура машины с распределенной памятью.

Пути повышения производительности ВС заложены в ее архитектуре. С одной стороны это совокупность процессоров, блоков памяти, устройств ввода/вывода ну и конечно способов их соединения, т.е. коммуникационной среды. С другой стороны, это собственно действия ВС по решению некоторой задачи, а это операции над командами и данными. Вот собственно и вся основная база для проведения параллельной обработки. Параллельная обработка, воплощая идею одновременного выполнения нескольких действий, имеет несколько разновидностей: суперскалярность, конвейеризация, SIMD – расширения, Hyper Threading , многоядерность. В основном эти виды параллельной обработки интуитивно понятны, поэтому сделаем лишь небольшие пояснения. Если некое устройство выполняет одну операцию за единицу времени, то тысячу операций оно выполнит за тысячу единиц. Если предположить, что есть, пять таких же независимых устройств, способных работать одновременно, то ту же тысячу операций система из пяти устройств может выполнить уже не за тысячу, а за двести единиц времени. Аналогично система из N устройств ту же работу выполнит за 1000/N единиц времени. Подобные аналогии можно найти и в жизни: если один солдат вскопает огород за 10 часов, то рота солдат из пятидесяти человек с такими же способностями, работая одновременно, справятся с той же работой за 12 минут (параллельная обработка данных), да еще и с песнями (параллельная обработка команд).

Конвейерная обработка . Что необходимо для сложения двух вещественных чисел, представленных в форме с плавающей запятой? Целое множество мелких операций таких, как сравнение порядков, выравнивание порядков, сложение мантисс, нормализация и т.п. Процессоры первых компьютеров выполняли все эти "микрооперации" для каждой пары аргументов последовательно одна за одной до тех пор, пока не доходили до окончательного результата, и лишь после этого переходили к обработке следующей пары слагаемых. Идея конвейерной обработки заключается в выделении отдельных этапов выполнения общей операции, причем каждый этап, выполнив свою работу, передавал бы результат следующему, одновременно принимая новую порцию входных данных. Получаем очевидный выигрыш в скорости обработки за счет совмещения прежде разнесенных во времени операций.

Суперскалярность. Как и в предыдущем примере, только при построении конвейера используют несколько программно-аппаратных реализаций функциональных устройств, например два или три АЛУ, три или четыре устройства выборки.

Hyper Threading . Перспективное направление развитие современных микропроцессоров, основанное на многонитевой архитектуре. Основное препятствие на пути повышения производительности за счет увеличения функциональных устройств – это организация эффективной загрузки этих устройств. Если сегодняшние программные коды не в состоянии загрузить работой все функциональные устройства, то можно разрешить процессору выполнять более чем одну задачу (нить), чтобы дополнительные нити загрузили – таки все ФИУ (очень похоже на многозадачность).

Многоядерность . Можно, конечно, реализовать мультипроцессирование на уровне микросхем, т.е. разместить на одном кристалле несколько процессоров (Power 4). Но если взять микропроцессор вместе с памятью как ядра системы, то несколько таких ядер на одном кристалле создадут многоядерную структуру. При этом в кристалле интегрируются функции (например, интерфейсы сетевых и телекоммуникационных систем) для выполнения которых обычно используются наборы микросхем (процессоры Motorola MPC8260, Power 4).

Реализация высокопроизводительной вычислительной техники в настоящее время идёт по четырем основным направлениям.

1. Векторно-конвейерные компьютеры . Конвейерные функциональные устройства и набор векторных команд - это две особенности таких машин. В отличие от традиционного подхода, векторные команды оперируют целыми массивами независимых данных, что позволяет эффективно загружать доступные конвейеры, т.е. команда вида A=B+C может означать сложение двух массивов, а не двух чисел. Характерным представителем данного направления является семейство векторно-конвейерных компьютеров CRAY куда входят, например, CRAY EL, CRAY J90, CRAY T90 (в марте 2000 года американская компания TERA перекупила подразделение CRAY у компании Silicon Graphics, Inc.).

2. Массивно-параллельные компьютеры с распределенной памятью. Идея построения компьютеров этого класса тривиальна: возьмем серийные микропроцессоры, снабдим каждый своей локальной памятью, соединим посредством некоторой коммуникационной среды - вот и все. Достоинств у такой архитектуры масса: если нужна высокая производительность, то можно добавить еще процессоров, если ограничены финансы или заранее известна требуемая вычислительная мощность, то легко подобрать оптимальную конфигурацию и т.п.

Однако есть и решающий "минус", сводящий многие "плюсы" на нет. Дело в том, что самостоятельным, а скорее представляет собой комбинации предыдущих трех. Из нескольких процессоров (традиционных или векторно-конвейерных) и общей для них памяти сформируем вычислительный узел. Если полученной вычислительной мощности не достаточно, то объединим несколько узлов высокоскоростными каналами. Подобную архитектуру называют кластерной SV1 , HP Exemplar , Sun StarFire , NEC SX-5 , последние модели IBM SP2

3. Параллельные компьютеры с общей памятью . Вся оперативная память таких компьютеров разделяется несколькими одинаковыми процессорами. Это снимает проблемы предыдущего класса, но добавляет новые - число процессоров, имеющих доступ к общей памяти, по чисто техническим причинам нельзя сделать большим. В данное направление входят многие современные многопроцессорные SMP-компьютеры или, например, отдельные узлы компьютеров HP Exemplar и Sun StarFire .

4. Кластерные системы. Последнее направление, строго говоря, не является самостоятельным, а скорее представляет собой комбинации предыдущих трех. Из нескольких процессоров (традиционных или векторно-конвейерных) и общей для них памяти сформируем вычислительный узел. Если полученной вычислительной мощности не достаточно, то объединим несколько узлов высокоскоростными каналами. Подобную архитектуру называют кластерной , и по такому принципу построены CRAY SV1 , HP Exemplar , Sun StarFire , NEC SX-5 , последние модели IBM SP2 и другие. Именно это направление является в настоящее время наиболее перспективным для конструирования компьютеров с рекордными показателями производительности.

Таким образом, основные признаки, характеризующие супер-ЭВМ , следующие:

• самая высокая производительность;
• самый современный технологический уровень (например, GaAs -технология);
• специфические архитектурные решения, направленные на повышение быстродействия (например, наличие операций над векторами);
• цена, обычно свыше 1-2 млн. долларов.

Какой из факторов является решающим в достижении современных фантастических показателей производительности? Обратимся к историческим фактам. На одном из самых первых компьютеров EDSAC (1949 г.), имевшем время такта 2 мкс, можно было выполнить в среднем 100 арифметических операций в секунду. А пиковая производительность суперкомпьютера CRAY C90 с временем такта порядка 4 нс - около 1 миллиарда арифметических операций в секунду. Таким образом, производительность компьютеров за этот период возросла примерно в 10 миллионов раз, а время такта уменьшилось лишь в 500 раз. Следовательно, увеличение производительности происходило и за счет других факторов, важнейшим среди которых является использование новых архитектурных решений, в частности - принципа параллельной обработки данных .

Имеет две разновидности: конвейерность и параллельность.

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

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

Закон Амдала

Закон Амдала

S<= 1/

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

Следствие из закона Амдала : для того чтобы ускорить выполнение программы в q раз, необходимо ускорить не менее чем в q раз и не менее чем (1-1/q) -ую часть программы. Следовательно, если нужно ускорить программу в 100 раз по сравнению с ее последовательным вариантом, то необходимо получить не меньшее ускорение на не менее чем 99,99 % кода!

История появления параллелизма в архитектуре ЭВМ

Все современные процессоры используют тот или иной вид