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

Федеральное агентство по образованию 
 
Государственное образовательное учреждение

высшего профессионального образования

«Санкт-Петербургский  государственный

инженерно-экономический  университет»

 

 

 

 

РЕФЕРАТ

 

“Параллельная обработка данных” 
по дисциплине "Информатика"

 

 

 

 

 

 

 

 

 

 

 

Выполнил: Скачков Г.Н. 
Студент 1 курса, группа 3602 
Специальность: 230201 
Преподаватель: Попов Е. Б. 

 

 

 

 

 

Санкт-Петербург 
2011

ОГЛАВЛЕНИЕ

 

Введение 3

Глава 1. Параллельная обработка данных 4

1.1. Параллельность 4

1.2. Конвейерность 4

1.3. Векторная обработка 5

Глава 2. Классификация архитектур по параллельной обработке данных 5

Глава 3. Архитектуры MIMD 6

3.1. Мультипроцессоры 7

3.2. Мультикомпьютеры 8

Глава 4. Закон Амдала 9

Заключение 10

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

 

 

Введение

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

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

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

 

Рис.1 Tianhe-1

 

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

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

Глава 1. Параллельная обработка данных

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

1.1. Параллельность

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

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

1.2. Конвейерность

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

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

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

 

 

1.3. Векторная обработка

Векторный процессор "умеет" обрабатывать одной  командой не одно единственное значение, а сразу массив (вектор) значений. Пусть A1, A2 и P - это три массива, имеющие одинаковую размерность и одинаковую длину, и имеется оператор P=A1+A2. Векторный процессор за один цикл выполнения команды выполнит попарное сложение элементов массивов A1 и A2 и присвоит полученные значения соответствующим элементам массива P. Каждый операнд при этом хранится в особом, векторном регистре. Обычному, последовательному процессору пришлось бы несколько раз выполнять операцию сложения элементов двух массивов. Векторный процессор выполняет лишь одну команду!

 

 

 

Глава 2. Классификация архитектур по параллельной обработке данных

Самой ранней и наиболее известной является классификация архитектур вычислительных систем, предложенная в 1966 году М.Флинном (Flynn). Классификация базируется на понятии потока, под которым понимается последовательность элементов, команд или данных, обрабатываемая процессором. На основе числа потоков команд и потоков данных Флинн выделяет четыре класса архитектур:

• SISD (single instruction stream / single data stream) - одиночный поток команд и одиночный поток данных. Вообще говоря, эта архитектура не имеет отношения к высокопроизводительным системам. К этому классу относятся, прежде всего, классические последовательные машины. В таких машинах есть только один поток команд, все команды обрабатываются последовательно друг за другом и каждая команда инициирует одну операцию с одним потоком данных. Не имеет значения тот факт, что для увеличения скорости обработки команд и скорости выполнения арифметических операций может применяться конвейерная обработка. В случае векторных систем векторный поток данных следует рассматривать как поток из одиночных неделимых векторов.
• MISD (multiple instruction stream / single data stream) - множественный поток команд и одиночный поток данных. Определение подразумевает наличие в архитектуре многих процессоров, обрабатывающих один и тот же поток данных. Однако ни Флинн, ни другие специалисты в области архитектуры компьютеров до сих пор не смогли представить убедительный пример реально существующей вычислительной системы, построенной на данном принципе. Ряд исследователей относят конвейерные машины к данному классу, однако это не нашло окончательного признания в научном сообществе. В качестве аналог работы такой системы, по-видимому, можно рассматривать работу банка. С любого терминала можно подать команду и что-то сделать с имеющимся банком данных. Поскольку база данных одна, а команд много, то мы имеем дело с множественным потоком команд и одиночным потоком данных.
• SIMD (single instruction stream / multiple data stream) - одиночный поток команд и множественный поток данных. В архитектурах подобного рода сохраняется один поток команд, включающий, векторные команды. Это позволяет выполнять одну арифметическую операцию сразу над многими данными - элементами вектора. Способ выполнения векторных операций не оговаривается, поэтому обработка элементов вектора может производиться либо процессорной матрицей, либо с помощью конвейера.
• MIMD (multiple instruction stream / multiple data stream) - множественный поток команд и множественный поток данных. Этот класс предполагает, что в вычислительной системе есть несколько устройств обработки команд, объединенных в единый комплекс и работающих каждое со своим потоком команд и данных. Таким образом, в системе такого рода можно наблюдать реальное распараллеливание.

 

 

 

Глава 3. Архитектуры MIMD

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

 

Рис. 2 Классификация MIMD

 

 

3.1. Мультипроцессоры

Мультипроцессор – это компьютерная система, которая содержит несколько процессоров, взаимодействующих между собой, и одно адресное пространство (ОЗУ) для всех процессоров

Способы построения общей памяти (Рис.3):

• Однородный доступ к памяти (Uniform Memory Access или UMA) – служит основой для построения симметричных мультипроцессоров (Symmetric Multiprocessing или SMP) – использование единой, общей памяти.
• Неоднородный доступ к памяти (Non-Uniform Memory Access или NUMA) – память является физически распределённой по различным частям системы, но логически разделяемой, так что пользователь видит единое адресное пространство.

 

 

NCC-NUMA

Мультипроцессоры

Распределённая  память

NUMA

Общая память

UMA

CC-NUMA

NCC-NUMA

NCC-NUMA

NCC-NUMA

 

 

 

 

 

 

 

 

 

 

Рис.3 Мультипроцессорные системы

 

 

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

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

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

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

 

NUMA (Non-Uniform Memory Access) - это архитектура с неоднородным доступом к памяти.

Гибридная архитектура воплощает в себе удобства систем с общей памятью  и относительную дешевизну систем с раздельной памятью. Суть этой архитектуры - в особой организации памяти, а  именно: память является физически  распределенной по различным частям системы, но логически разделяемой, так что пользователь видит единое адресное пространство. Система состоит  из однородных базовых модулей (плат), состоящих из небольшого числа процессоров  и блока памяти. Модули объединены с помощью высокоскоростного коммутатора. Поддерживается единое адресное пространство, аппаратно поддерживается доступ к удаленной памяти, т.е. к памяти других модулей. При этом доступ к локальной памяти осуществляется в несколько раз быстрее, чем к удаленной. По существу архитектура NUMA является MPP (массивно-параллельная архитектура) архитектурой, где в качестве отдельных вычислительных элементов берутся SMP ( cсимметричная многопроцессорная архитектура) узлы. 

 

3.2. Мультикомпьютеры

Мультикомпьютеры - вычислительная система без общей памяти, состоящая из большого числа взаимосвязанных компьютеров, у каждого из которых имеется собственная память. Мультикомпьютеры (многопроцессорные системы с распределенной памятью) уже не обеспечивают общего доступа ко всей имеющейся в системах памяти (no-remote memory access или NORMA). При всей схожести подобной архитектуры с системами с распределенной общей памятью (NUMA), мультикомпьютеры имеют принципиальное отличие: каждый процессор системы может использовать только свою локальную память, в то время как для доступа к данным, располагаемым на других процессорах, необходимо явно выполнить операции передачи сообщений (message passing operations). Данный подход применяется при построении двух важных типов многопроцессорных вычислительных систем - массивно-параллельных систем (massively parallel processor или MPP) и кластеров (clusters) (Рис.4)

 

Мультикомпьютеры (NORMA)

_MPP

_Clusters

 

 

 

 

 

 

 

Рис.4 Мультикомпьютерные системы

 

 

 

MPP (Massive Parallel Processing) - класс архитектур параллельных вычислительных систем. Особенность архитектуры состоит в том, что память физически разделена. Система строится из отдельных модулей, содержащих процессор, локальный банк операционной памяти, коммуникационные процессоры или сетевые адаптеры, иногда — жесткие диски и/или другие устройства ввода/вывода. Доступ к банку операционной памяти из данного модуля имеют только процессоры из этого же модуля. Модули соединяются специальными коммуникационными каналами.

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

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

 

Кластеры (Сlusters) - группа компьютеров, объединённых высокоскоростными каналами связи и представляющая с точки зрения пользователя единый аппаратный ресурс. Кластерные технологии стали логическим продолжением развития идей, заложенных в архитектуре MPP систем. Если процессорный модуль в MPP системе представляет собой законченную вычислительную систему, то следующий шаг напрашивается сам собой: почему бы в качестве таких вычислительных узлов не использовать обычные серийно выпускаемые компьютеры.

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

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

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

Глава 4. Закон Амдала

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

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

 

  , где

p – количество вычислителей,

S –  ускорение работы программы на  p процессорах,

f – доля операций в программе, которые выполняются последовательно.

 

 

 

 

Иллюстрация:

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

 

 

p f	10	100	1000
0%	10	100	1000
10%	5,263	9,174	9,911
25%	3,077	3,883	3,988
40%	2,174	2,463	2,496

 

 

Из  таблицы видно, что только алгоритм, вовсе не содержащий последовательных вычислений (f = 0), позволяет получить линейный прирост производительности с ростом количества вычислителей в системе. Если доля последовательных вычислений в алгоритме равна 25 %, то увеличение числа процессоров до 10 дает ускорение в 3,077 раза, а увеличение числа процессоров до 1000 даст ускорение в 3,988 раза. Отсюда же очевидно, что при доле последовательных вычислений f общий прирост производительности не может превысить 1 / f. Так, если половина кода — последовательная, то общий прирост никогда не превысит двух. Это показано на диаграмме ниже (Рис. 5).

 

Рис. 5 Диаграмма, иллюстрирующая закон Амдала

 

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

Заключение

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

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

 

 

Список использованной литературы

 

1. В.Л.Бройдо, «Вычислительные системы, сети и телекоммуникации», Учебник для ВУЗов. – Спб: Питер, 2006.
2. http://sci.informika.ru/text/teach/topolog/index.htm
3. http://rsusu1.rnd.runnet.ru/tutor/method/index.html
4. http://www.intuit.ru/department/calculate/paralltp/1/