Главная › Услуги › Виды параллелизма. Классификация систем параллельной обработки данных

Виды параллелизма. Классификация систем параллельной обработки данных

Министерство образования и науки Российской Федерации

ФГБОУ ВПО «Брянская государственная инженерно-технологическая

академия»

Кафедра информационных технологий

Последовательная и параллельная обработка информации

Расчётно-графическая работа № 1

по дисциплине

«Технологии обработки информации»

Вариант № 16

РГР-02068025.230400.084

Брянск 2015

Введение 3

Параллельная обработка информации 4

Системы с разделением памяти 6

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

Последовательная обработка информации 9

Простые пакетные системы 10

Список литературы 13

Введение

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

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

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

Параллельная обработка информации

Параллельная обработка данных, воплощая идею одновременного выполнения нескольких действий, имеет две разновидности: конвейерность и параллельность.

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

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

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

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

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

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

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

4 курс, 1 и 2 потоки, 7-й семестр

лекции (34 часа), зачет

Кафедра, отвечающая за курс : АСВК

Составитель программы : чл.-кор. РАН, доктор физ.-мат. наук Воеводин Вл.В.,

Лекторы : чл.-кор. РАН, доктор физ.-мат. наук Воеводин Вл.В.

Аннотация

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

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

Программа

1. Большие задачи и суперкомпьютеры. Параллельная и конвейерная обработка данных. Параллелизм и конвейерность в архитектуре современных высокопроизводительных компьютеров. Скалярные и векторные команды. Скалярные, конвейерные и векторные устройства. Иерархия памяти в компьютерах как средство повышения скорости выполнения программ, локальность вычислений и локальность использования данных. Закон Амдала и его следствия, суперлинейное ускорение.

2. Основные классы современных параллельных вычислительных систем. Компьютеры с общей памятью, примеры, причины снижения производительности на реальных программах. Архитектуры SMP, NUMA, ccNUMA. Коммутация процессоров и модулей памяти, шина, матричный коммутатор, омега-сеть. Векторно-конвейерные вычислительные системы, примеры, причины снижения производительности. Компьютеры с распределенной памятью, примеры, причины снижения производительности. Топология связи между процессорами: звезда, решетка, трехмерный тор, двоичный гиперкуб, их свойства. Вычислительные кластеры, примеры, латентность и пропускная способность различных коммуникационных технологий. Архитектуры с параллелизмом на уровне машинных команд, VLIW, суперскалярность.

3. Технологии параллельного программирования. Традиционные последовательные языки и распараллеливающие компиляторы, проблемы. Спецкомментарии и директивы компилятору, расширения существующих языков. Специальные языки параллельного программирования. Программирование с использованием библиотек и интерфейсов передачи сообщений. Параллельные предметные библиотеки, специализированные пакеты и программные комплексы высокого уровня. Технологии параллельного программирования MPI, OpenMP, Linda.

4. Производительность параллельных вычислительных систем. Универсальность и специализация компьютеров, производительность спецпроцессоров. Закон Мура. Методы оценки производительности. Введение единого числового параметра, Mflops, MIPS. Пиковая и реальная производительность компьютеров. Тест Linpack и его варианты. Наборы взаимодополняющих тестовых программ, STREAM и NPB.

5. Графовые модели программ. Граф управления и информационный граф программы. Информационная и операционная история реализации программ. Граф алгоритма как компактная параметрическая форма представления информационной истории. Информационная независимость операций и возможность их параллельного исполнения. Длина критического пути графа алгоритма как мера степени параллельности. Конечный и массовый параллелизм, координатный и скошенный параллелизм. Эквивалентные преобразования программ, элементарные преобразования циклов.

6. Неоднородные распределенные вычислительные системы. Метакомпьютеры и метакомпьютинг, существующие метакомпьютерные проекты. Отличительные свойства метакомпьютеров. Понятие GRID, базовые компоненты и сервисы, существующие проекты GRID-сегментов, понятие виртуальной организации.

Литература

1. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ Петербург, 2002. - 608 с.

2. Королев Л.Н. Архитектура процессоров электронных вычислительных машин. – М.: Изд. факультета ВМК МГУ, 2003.

3. В.В.Корнеев. Параллельные вычислительные системы. – М.: Изд-во "Нолидж", 1999. – 320с.

4. Материалы информационно-аналитического центра по параллельным вычислениям Parallel.ru.

Дополнительная литература

1. Антонов А.С. Параллельное программирование с использованием технологии

MPI: Учебное пособие. – М.: Изд-во МГУ, 2004. - 71 с.

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

1. Повышение производительности ЭВМ и ВС не за счет совершенствования элементной базы, а за счет эффективной организации вычислительных процессов.

2. Обеспечение высокой надежности ВС за счет дублирования вычислительной аппаратуры.

Рис. 5.1. Уровни параллелизма

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

Параллельная обработка информации может производиться на нескольких уровнях (рис. 5.1).

Очевидно, что чем ниже уровень, тем мельче дробление программных процессов, тем мельче, как принято говорить, «зерно параллелизма ». В общем случае возможно реализовать параллелизм как на отдельном уровне, так и на нескольких одновременно. Независимая однопроцессорная обработка реализует параллелизм на уровне 1. Векторная обработка заключается в параллельном выполнении циклов на уровне 2 и может производиться как на одном, так и нескольких процессорах. Уровни 3 и 4 соответствуют многопроцессорным ВС. Параллелизм уровня 5 характерен для многомашинных вычислительных комплексов.

Существует два основных способа организации параллельной обработки:

· совмещение во времени этапов решения разных задач;

· одновременное решение различных задач или частей одной задачи;

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

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

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

1. Естественный параллелизм независимых задач.

2. Параллелизм объектов или данных.

3. Параллелизм ветвей задачи или программы.

Рассмотрим эти типы параллелизма.

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

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

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

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

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

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

· ни одна из выходных величин этих ветвей задачи не является входной величиной для другой такой ветви (отсутствие функциональных связей);

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

Хорошее представление о параллелизме ветвей дает ярусно-параллельная форма(ЯПФ) программы, пример которой приведен на рис. 5.2.

Программа представлена в виде совокупности ветвей, расположенных на нескольких уровнях - ярусах. Кружками с цифрами внутри обозначены ветви. Длина ветви представляется цифрой, стоящей около кружка и говорящей, сколько временных единиц выполняется данная ветвь. Стрелками показаны входные данные и результаты обработки. Входные данные обозначаются символом X, выходные данные - символом Y. Символы Х имеют нижние цифровые индексы, обозначающие номера входных величин; символы Y имеют цифровые индексы и внизу, и вверху; цифра вверху соответствует номеру ветви, при выполнении которой получен данный результат, а цифра внизу означает порядковый номер результата, полученного при реализации данной ветви программы. На одном ярусе размещаются независимые ветви задачи, не связанные друг с другом, т.е. результаты решения какой-либо ветви данного яруса не являются входными данными для другой ветви этого же яруса.

Рис. 5.2. Пример ярусно-параллельной формы программы

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

Примем, что длина i -й ветви представляется числом временных единиц t i , которые требуются для ее исполнения. Тогда нетрудно подсчитать, что для исполнения всей программы на 1 процессоре потребуется время T 1 :

T 1 =S (10+20+15+30+55+10+15+25+15)=195

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

Рассмотрим, например, такой вариант выполнения программы, представленной на рис. 5.2. Пусть процессор 1 выполняет ветви 1-3-4-6-7-9, а процессор 2 выполняет ветви 2-5-8. На рис. 5.3 представлены временные диаграммы выполнения процессорами ветвей программы.

Рис. 5.3. Разложение ветвей программы по 2 процессорам

Нетрудно подсчитать, что процессор 1 затрачивает 105, а процессор 2 - 100 единиц времени. При этом имеется два промежутка времени, когда один из процессоров вынужденно простаивает – П1 длительностью 10 единиц и П2 длительностью 5 единиц времени. Промежуток П1, во время которого работает только процессор 2, образовался из-за того, что ветвь 7 зависит от ветви 5 (к моменту завершения ветви 6 еще не готовы данные Y 5 1). Промежуток П1, во время которого работает только процессор 1, образовался по причине окончания счета процессором 2.

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

Коэффициент распараллеливанияизменяется от 0 до 1 (от 0 до 100%) и отражает эффективность использования вычислительных ресурсов. В нашем примере нетрудно посчитать, что ускорение S = 195/105 = 1,86, а коэффициент распараллеливания K п = 0,93. Как видим, по причине простоев одного из процессоров ускорение счета значительно меньше 2, т.е. количества используемых процессоров. Заметим, что в нашем примере не учитывались временные задержки, связанные с переключением контекстов программы (смены ветвей) и передачи данных от одной ветви к другой. Тем не менее, в силу алгоритмических особенностей программы, часть вычислений в промежутки П1 и П2 производится только одним процессором, т.е. фактически последовательно.

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

Данное соотношение носит название закона Амдала . На примере программы рис. 5.2 мы можем видеть, что доля последовательных вычислений составляет f = 15/195. Подставляя эту величину в формулу закона Амдала, получаем для системы из двух процессоров максимальное ускорение 1,86 раза, что соответствует ранее рассчитанному значению.

Для иллюстрации действия закона Амдала приведем следующий пример. Пусть доля последовательных вычислений в некоторой программе составляет 10%. Тогда максимальное ускорение счета на 100 процессорах не превысит 9,2. Коэффициент распараллеливания составит всего лишь 9,2%. На 10 процессорах ускорение составит 5,3, а коэффициент распараллеливания ‑ 53%. Нетрудно видеть, что даже такая небольшая доля последовательных вычислений уже на теоретическом уровне, без учета неизбежных задержек в реальной ВС, серьезно ограничивает возможности масштабирования программы.

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

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

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

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

Простые рассчеты показывают, что конфигурации подобных систем могут стоить не один миллион долларов США - ради интереса прикиньте, сколько стоят, скажем, лишь 4 Тбайта оперативной памяти? Возникает целый ряд естественных вопросов: какие задачи настолько важны, что требуются компьютеры стоимостью несколько миллионов долларов? Или, какие задачи настолько сложны, что хорошего Пентиума не достаточно? На эти и подобные им вопросы хотелось бы найти разумные ответы.

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

Примем упрощенную схему, при которой моделируемая область отображается в куб, однако и ее будет достаточно для оценки числа необходимых арифметических операций. Разумные размеры куба, при которых можно получать правдоподобные результаты - это 100*100*100 точек. В каждой точке куба надо вычислить от 5 до 20 функций: три компоненты скорости, давление, температуру, концентрацию компонент (вода, газ и нефть - это минимальный набор компонент, в более реалистичных моделях рассматривают, например, различные фракции нефти). Далее, значения функций находятся как решение нелинейных уравнений, что требует от 200 до 1000 арифметических операций. И наконец, если исследуется нестационарный процесс, т.е. нужно понять, как эта система ведет себя во времени, то делается 100-1000 шагов по времени. Что получилось:

10 6 (точек сетки)*10(функций)*500(операций)*500(шагов по времени) = 2.5*10 12

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

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

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

В 1995 году корпус автомобиля Nissan Maxima удалось сделать на 10% прочнее благодаря использованию суперкомпьютера фирмы Cray (The Atlanta Journal, 28 мая, 1995г). С помощью него были найдены не только слабые точки кузова, но и наиболее эффективный способ их удаления.

По данным Марка Миллера (Mark Miller, Ford Motor Company), для выполнения crash-тестов, при которых реальные автомобили разбиваются о бетонную стену с одновременным замером необходимых параметров, съемкой и последующей обработкой результатов, компании Форд понадобилось бы от 10 до 150 прототипов новых моделей при общих затратах от 4 до 60 миллионов долларов. Использование суперкомпьютеров позволило сократить число прототипов на одну треть.

Совсем недавний пример - это развитие одной из крупнейших мировых систем резервирования Amadeus, используемой тысячами агенств со 180000 терминалов в более чем ста странах. Установка двух серверов Hewlett-Packard T600 по 12 процессоров в каждом позволила довести степень оперативной доступности центральной системы до 99.85% при текущей загрузке около 60 миллионов запросов в сутки.

И подобные примеры можно найти повсюду. В свое время исследователи фирмы DuPont искали замену хлорофлюорокарбону. Нужно было найти материал, имеющий те же положительные качества: невоспламеняемость, стойкость к коррозии и низкую токсичность, но без вредного воздействия на озоновый слой Земли. За одну неделю были проведены необходимые расчеты на суперкомпьютере с общими затратами около 5 тысяч долларов. По оценкам специалистов DuPont, использование традиционных экспериментальных методов исследований потребовало бы около трех месяцев и 50 тысяч долларов и это без учета времени, необходимого на синтез и очистку необходимого количества вещества.

Увеличение производительности ЭВМ, за счет чего?

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

Попробуем разобраться, какой из этих факторов оказывается решающим для достижения рекордной производительности. Обратимся к известным историческим фактам. На одном из первых компьютеров мира - EDSAC, появившемся в 1949 году в Кембридже и имевшем время такта 2 микросекунды (2*10-6 секунды), можно было выполнить 2*n арифметических операций за 18*n миллисекунд, то есть в среднем 100 арифметических операций в секунду. Сравним с одним вычислительным узлом современного суперкомпьютера Hewlett-Packard V2600: время такта приблизительно 1.8 наносекунды (1.8*10-9 секунд), а пиковая производительность около 77 миллиардов арифметических операций в секунду.

Что же получается? За полвека производительность компьютеров выросла более, чем в семьсот миллионов раз. При этом выигрыш в быстродействии, связанный с уменьшением времени такта с 2 микросекунд до 1.8 наносекунд, составляет лишь около 1000 раз. Откуда же взялось остальное? Ответ очевиден -- использование новых решений в архитектуре компьютеров. Основное место среди них занимает принцип параллельной обработки данных, воплощающий идею одновременного (параллельного) выполнения нескольких действий.

Параллельная обработка данных на ЭВМ

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

Кстати, пионером в параллельной обработке потоков данных был академик А.А.Самарский, выполнявший в начале 50-х годов расчеты, необходимые для моделирования ядерных взрывов. Самарский решил эту задачу, посадив несколько десятков барышень с арифмометрами за столы. Барышни передавали данные друг другу просто на словах и откладывали необходимые цифры на арифмометрах. Таким образом, в частности, была расчитана эволюция взрывной волны. Работы было много, барышни уставали, а Александр Андреевич ходил между ними и подбадривал. Это, можно сказать, и была первая параллельная система. Хотя расчеты водородной бомбы были мастерски проведены, точность их была очень низкая, потому что узлов в используемой сетке было мало, а время счета получалось слишком большим.

Казалось бы конвейерную обработку можно с успехом заменить обычным параллелизмом, для чего продублировать основное устройство столько раз, сколько ступеней конвейера предполагается выделить. В самом деле, пять устройств предыдущего примера обработают 100 пар аргументов за 100 единиц времени, что быстрее времени работы конвейерного устройства! В чем же дело? Ответ прост, увеличив в пять раз число устройств, мы значительно увеличиваем как объем аппаратуры, так и ее стоимость. Представьте себе, что на автозаводе решили убрать конвейер, сохранив темпы выпуска автомобилей. Если раньше на конвейере одновременно находилась тысяча автомобилей, то действуя по аналогии с предыдущим примером надо набрать тысячу бригад, каждая из которых (1) в состоянии полностью собрать автомобиль от начала до конца, выполнив сотни разного рода операций, и (2) сделать это за то же время, что машина прежде находилась на конвейере. Представили себестоимость такого автомобиля? Нет? Согласен, трудно, разве что Ламборгини приходит на ум, но потому и возникла конвейерная обработка...

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

Сегодня параллелизмом в архитектуре компьютеров уже мало кого удивишь. Все современные микропроцессоры, будь то Pentium III или PA-8700, MIPS R14000, Е2К или Power3 используют тот или иной вид параллельной обработки. В ядре Pentium 4 на разных стадиях выполнения может одновременно находиться до 126 микроопераций. На презентациях новых чипов и в пресс-релизах корпораций это преподносится как последнее слово техники и передовой край науки, и это действительно так, если рассматривать реализацию этих принципов в миниатюрных рамках одного кристалла.

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

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

IBM 701 (1953), IBM 704 (1955): разрядно-параллельная память, разрядно-параллельная арифметика .
Все самые первые компьютеры (EDSAC, EDVAC, UNIVAC) имели разрядно-последовательную память, из которой слова считывались последовательно бит за битом. Первым коммерчески доступным компьютером, использующим разрядно-параллельную память (на CRT) и разрядно-параллельную арифметику, стал IBM 701, а наибольшую популярность получила модель IBM 704 (продано 150 экз.), в которой, помимо сказанного, была впервые применена память на ферритовых сердечниках и аппаратное АУ с плавающей точкой.

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

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

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

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

время такта 100нс,
производительность 2-3 млн. операций в секунду,
оперативная память разбита на 32 банка по 4096 60-ти разрядных слов,
цикл памяти 1мкс,
10 независимых функциональных устройств.

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

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

такт 27,5 нс,
10-15 млн. опер/сек.,
8 конвейерных ФУ,
2-х уровневая память.

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

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

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

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

УУ это простая ЭВМ с небольшой производительностью, управляющая матрицей ПЭ; все ПЭ матрицы работали в синхронном режиме, выполняя в каждый момент времени одну и ту же команду, поступившую от УУ, но над своими данными;
ПЭ имел собственное АЛУ с полным набором команд, ОП - 2Кслова по 64 разряда, цикл памяти 350нс, каждый ПЭ имел непосредственный доступ только к своей ОП;
сеть пересылки данных: двумерный тор со сдвигом на 1 по границе по горизонтали;

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

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

А что же сейчас используют в мире?

По каким же направлениям идет развитие высокопроизводительной вычислительной техники в настоящее время? Основных направлений четыре.

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

Если 9/10 программы исполняется параллельно, а 1/10 по-прежнему последовательно, то ускорения более, чем в 10 раз получить в принципе невозможно вне зависимости от качества реализации параллельной части кода и числа используемых процессоров (ясно, что 10 получается только в том случае, когда время исполнения параллельной части равно 0).

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

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

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

S = 0 Do i = 1, n s = s + a(i) EndDo (можно тоже самое на любом другом языке)

По своей природе он строго последователен, так как на i-й итерации цикла требуется результат с (i-1)-й и все итерации выполняются одна за одной. Имеем 100% последовательных операций, а значит и никакого эффекта от использования параллельных компьютеров. Вместе с тем, выход очевиден. Поскольку в большинстве реальных программ (вопрос: а почему в большинстве, а не во всех?) нет существенной разницы, в каком порядке складывать числа, выберем иную схему сложения. Сначала найдем сумму пар соседних элементов: a(1)+a(2), a(3)+a(4), a(5)+a(6) и т.д. Заметим, что при такой схеме все пары можно складывать одновременно! На следующих шагах будем действовать абсолютно аналогично, получив вариант параллельного алгоритма.

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

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

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

Заключительный вопрос . Как вы думаете, верно ли утверждение: чем мощнее компьютер, тем быстрее на нем можно решить данную задачу?

Заключительный ответ . Нет, это не верно. Это можно пояснить простым бытовым примером. Если один землекоп выкопает яму 1м*1м*1м за 1 час, то два таких же землекопа это сделают за 30 мин - в это можно поверить. А за сколько времени эту работу сделают 60 землекопов? За 1 минуту? Конечно же нет! Начиная с некоторого момента они будут просто мешаться друг другу, не ускоряя, а замедляя процесс. Так же и в компьютерах: если задача слишком мала, то мы будем дольше заниматься распределением работы, синхронизацией процессов, сборкой результатов и т.п., чем непосредственно полезной работой.

Совершенно ясно, что не все так просто...

Лаборатория Параллельных Информационных Технологий, НИВЦ МГУ

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

Параллельная обработка - модель выполнения прикладного процесса одновременно группой процессоров. Различают три способа реализация параллелизма:
-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 … Справочник технического переводчика

Книги

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