Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ КАЗАХСТАН

Северо - Казахстанский государственный университет им. М. Козыбаева

Факультет информационных технологии

Кафедра Информационных систем

Процесс параллельной обработки данных

Выполнила: Махкамбаева А.С.

Проверил: Касимов И. Р.

Петропавловск, 2014

Введение

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

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

В 1967 году Джин Амдал сформулировал закон ограничения роста производительности при распараллеливании вычислений: «В случае, когда задача разделяется на несколько частей, суммарное время ее выполнения на параллельной системе не может быть меньше времени выполнения самого длинного фрагмента». Согласно этому закону, ускорение выполнения программы за счет распараллеливания её инструкций ограничено временем, необходимым для выполнения её последовательных инструкций.

Классификация по Флинну

процесс синхронизация доступ планирование

В основе классификации лежат два понятия: потоки команд и потоки данных. Система с N процессорами имеет N счетчиков команд и, следовательно, N потоков команд.

Потоки команд	Потоки данных	Названия

SISD (Single Instruction, Single Data) -- архитектура компьютера, в которой один процессор выполняет один поток команд, оперируя одним потоком данных. Для данного класса возможен только псевдопараллелизм.

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

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

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

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

OpenMP (Open Multi-Processing) -- открытый стандарт для распараллеливания программ на языках С, С++ и Фортран. Описывает совокупность команд, которые предназначены для программирования многопоточных приложений на многопроцессорных системах с общей памятью. OpenMP реализует параллельные вычисления с помощью многопоточности, в которой «главный» поток создает набор подчиненных потоков и задача распределяется между ними.

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

Следующий цикл складывает массивы «a» и «b» поэлементно. Все, что требуется для параллельного выполнения в этом случае - одна прагма, вставленная непосредственно перед циклом.

#pragma omp parallel for

for (i=0; i < numPixels; i++)

c[i] = a[i]+b[i];

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

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

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

#pragma omp parallel for

for (i=2; i < 10; i++)

factorial[i] = i * factorial;

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

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

MPI (Message Passing Interface) -- программный интерфейс для передачи информации, который позволяет обмениваться сообщениями между процессами, выполняющими одну задачу. В первую очередь MPI ориентирован на системы с распределенной памятью. Существуют реализации для языков Фортран, С и С++.

В первой версии MPI количество процессов (ветвей) задается в момент запуска программы, т.е. не существует возможности порождать ветви динамически. В версии 2.0 эта возможность появилась.

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

Для C, общий формат имеет вид

rc = MPI_Xxxxx(parameter, ...);

Заметим, что регистр здесь важен. Например, MPI должно быть заглавным, так же как и первая буква после подчеркивания. Все последующие символы долны быть в нижнем регистре. Переменная rc - есть некий код возврата, имеющий целый тип. В случае успеха, он устанавливается в MPI_SUCCESS. Программа на C должна включать файл "mpi.h".

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

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

К информации «на обложке» относятся ранг в коммуникаторе - идентификатор процесса в коммуникационном поле, тег - произвольное число, которое помогает различать сообщения и сам коммуникатор, проверка которого обеспечивает передачу внутри одного коммуникационного поля.

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

Существует несколько способов разделения обязанностей между процессами:

* делегирование («управляющий-рабочий»);

* сеть с равноправными узлами;

* конвейер;

* «изготовитель-потребитель».

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

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

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

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

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

Синхронные и асинхронные процессы

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

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

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

Синхронизация процессов -- приведение нескольких процессов к такому их протеканию, когда определённые стадии разных процессов совершаются в определённом порядке, либо одновременно.

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

Межпроцессное взаимодействие

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

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

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

С системами передачи сообщения связано большое количество проблем. Например, сообщение может потеряться. Чтобы избежать потери, получатель отсылает обратно сообщение с подтверждением приема. Если отправитель не получает подтверждения через некоторое время, он отсылает сообщение еще раз.

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

Семафор -- объект, позволяющий войти в заданный участок кода (обычно - критическую секцию) не более чем n процессам.

С семафором возможны три операции:

1) init(n); - инициализация счетчика (число, переданное счетчику, является количеством процессов, которые могут одновременно обращаться к критической секции)

2) wait(); - ждать пока счётчик станет больше 0; после этого уменьшить счётчик на единицу.

3) leave(); - увеличить счетчик на единицу.

Перед обращением процесса к критической секции необходимо вызвать метод wait(), после выполнения которого гарантировано, что количество процессов, одновременно обращающихся к ней не превышает n-1. Тогда процесс может продолжить работу и выполнить метод leave() после работы с критической секцией, тем самым дав знать остальным процессам, что “место освободилось”.

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

	Процесс 1	Процесс 2
	Хочет захватить A и B, начинает с A	Хочет захватить A и B, начинает с B
	Захватывает ресурс A	Захватывает ресурс B
	Ожидает освобождения ресурса B	Ожидает освобождения ресурса A
	Взаимная блокировка

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

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

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

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

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

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

Одним из преимуществ алгоритма является то, что он не требует специальных Test-and-set инструкций и вследствие этого он легко переносим на разные языки программирования и архитектуры компьютеров. Недостатками можно назвать его применимость к случаю только с двумя процессами и использование Busy waiting вместо приостановки процесса (использование busy waiting предполагает, что процессы должны проводить минимальное количество времени внутри критической секции).

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

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

Общий принцип алгоритмом Петерсона для 2-х потоков:

Размещено на http://www.allbest.ru/

Планирование процессов

Планирование - обеспечение поочередного доступа процессов к одному процессору.

Планировщик - отвечающая за это часть операционной системы.

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

Алгоритм планирования с вытеснением (приоритетный) - требует прерывание по аппаратному таймеру, процесс работает только отведенный период времени, после этого он приостанавливается по таймеру, чтобы передать управление планировщику.

Процессы размещаются в приоритетных очередях в соответствии со стратегией Планирования. В системах UNIX/Linux используются две стратегии планирования: FIFO (сокр. от First In First Out, т.е. первым прибыл, первым обслужен) и RR (сокр. От round-robin, т.е. циклическая).

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

RR-планирование совпадает с FIFO-планированием с одним исключением: после истечения кванта времени процесс помещается в конец своей приоритетной очереди, и процессору назначается следующий (по очереди) процесс.

Для обеспечения параллельной работы процессов может подойти приоритетное планирование. Каждому процессу присваивается приоритет, и управление передается процессу с самым высоким приоритетом. Приоритет может быть динамический и статический. Динамический приоритет может устанавливаться так: П=1/Т, где Т- часть использованного в последний раз кванта (если использовано 1/50 кванта, то приоритет 50. Если использован весь квант, то приоритет 1).

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

Размещено на Allbest.ur

Подобные документы

Структура, специфика и архитектура многопроцессорных систем; классификация Флинна. Организация взаимного исключения для синхронизации доступа к разделяемым ресурсам. Запрещение прерываний; семафоры с драйверами устройств. Кластеры распределения нагрузки.

курсовая работа , добавлен 07.06.2014


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

презентация , добавлен 24.01.2014


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

курсовая работа , добавлен 02.12.2009


Основные функции и процессы подсистемы управления процессами. Диспетчеризация процессов (потоков). Алгоритмы планирования выполнения потоков. Назначение и разновидности приоритетов в операционных системах. Функции подсистемы управления основной памятью.

презентация , добавлен 20.12.2013


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

дипломная работа , добавлен 09.09.2010


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

курсовая работа , добавлен 21.06.2013


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

курсовая работа , добавлен 21.06.2013


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

лекция , добавлен 05.02.2009


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

презентация , добавлен 24.07.2013


Классификация параллельных ВС. Системы с общей и распределенной памятью. Конвейеры операций. Производительность идеального конвейера. Суперскалярные архитектуры. VLIW-архитектура. Предсказание переходов. Матричные процессоры. Законы Амдала и Густафсона.

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

Информатика, кибернетика и программирование

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

Лекция 1

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

План

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

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

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

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

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

Производительность параллельных ВС зависит от многих факторов и в значительной степени от архитектуры и структуры системы (рисовать структуру параллельной системы и объяснять):

От степени и уровня параллелизма в системе;

От организации передачи данных между параллельно работающими процессорами;

От системы коммутации;

От взаимодействия процессоров и памяти;

От соотношения между аппаратной и программной реализацией макрооперации.

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

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

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

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

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

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

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

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

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

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

1. Длина графа (количество ярусов) – L .

2. Ширина i -го яруса - b i .

3. Ширина графа ярусно-параллельной формы – B = max (b i ).

4. Средняя ширина графа ЯПФ – В ср – .

5. Коэффициент заполнения i -го яруса – k i – .

6. Коэффициент разброса операций в графе - Q j i – , j БНО , где - количество j -го типа операций в i -м ярусе.

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

8. Минимальное время решения алгоритма (сумма времен срабатывания вычислителей с максимальным объемом вычислений по каждому ярусу) – Т min .

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

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

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

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

Характер изменения степени параллелизма при подготовке машинной программы показан на рис. 2.2.

потенциальный параллелизм

Метод

решения

Исходный текст

Машинная программа

Рис. 2.2. Изменение потенциального параллелизма при разработке программы:

1 – система параллельного программирования;

2 – последовательное программирование и

векторизующий компилятор

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

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

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

Явная параллельная обработка может быть обнаружена среди процессов i и j (i ≠ j ), удовлетворяющих следующим условиям:

входные данные одного процесса не должны модифицироваться (записываться) другим процессом

никакие два процесса не должны модифицировать общие переменные

а) R i W j =;

б) W i R j =;

в) W i W j =;

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

а) уменьшение высоты деревьев арифметических выражений (рис.2.3). Для арифметических выражений с n переменными или константами уменьшение высоты дерева позволяет достигнуть ускорения обработки порядка O (n / log 2 n ) при использовании O (n ) процессоров;

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

((a + b) + c) + d

(a + b)+ (c + d )

Рис. 2.3. Уменьшение высоты дерева

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

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

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

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

При преобразовании параллелизма программы учитывают: 1) схему размещения данных в памяти; 2) адресацию памяти (индексирование); 3) выбор маршрута данных (способ соединения процессоров и ЗУ).

Рис.2.4. Хранение

матрицы со сдвигом

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

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

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

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

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

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

3) Высокая степень: от 100 до 10 4 процессоров.

4) Сверхвысокая степень: от 10 4 до 10 6 процессоров.

Рис. 2.5. Профиль параллелизма

Графическое представление параметра D (t ) как функции времени называют профилем параллелизма программы . Изменения в уровне загрузки процессоров за время наблюдения зависят от многих факторов (алгоритма, доступных ресурсов, степени оптимизации, обеспечиваемой компилятором и т.д.). На рис. 2.5 показан типичный профиль параллелизма.

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

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

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

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

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

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

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

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

а) между частями программы (части одной задачи выполняются на множестве вычислителей);

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

(Если отдельные итерации в цикле на зависят друг от друга. Например: For I:=1 to N do A(I):=B(I) + C(I))

3. Командный уровень:

а) между фазами выполнения команд.

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

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

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

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

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

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

1. На уровне логических вентилей и элементов памяти. Это низший уровень – уровень транзисторов. Здесь из логических вентилей строят параллельные логические схемы (ЛС ) (например: параллельный сумматор).

2. Уровень логических схем и простых автоматов с памятью. Из логических схем строят параллельный элементарный автомат (ЭА ).

3. Уровень регистров и интегральных схем памяти. На элементарных автоматах получают параллельные схемы микропроцессоров (МП ).

4. Уровень элементарных микропроцессоров. Из микропроцессоров строят параллельные макропроцессоры для выполнения среднеблочных операций (МАП ).

5 . Уровень макропроцессоров, реализующих крупные операции. Здесь реализуется параллелизм макроопераций. На макропроцессорах строят параллельные многопроцессорные системы (МПС ).

6. Уровень вычислительных машин, процессоров и программ. Высший уровень параллелизма – из многопроцессорных систем получают параллельные вычислительные системы (ВС ).

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

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

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

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

Задача обладает естественным параллелизмом , если в её исходной постановке она сводится к операции над многомерными векторами, многомерными матрицами или над решётчатыми функциями (рис.2.6). Здесь не используются промежуточные результаты задач. Каждая задача программируется независимо от других. Этот вид параллелизма не требует объединения ЭВМ в комплексы. Однако увеличение числа независимых задач в СОД повышает пропускную способность системы. Например: обработка транзакций к БД на многопроцессорных серверах.

1 задача

2 задача

Рис. 2.6. Информационный граф задания, характеризующегося естественным параллелизмом

Орi

Орi

Орi

Орi

Орi+1

Орi+1

Орi+1

Орi+1

у 1

у 2

у 3

у 4

Рис. 2.7. Информационный граф

задачи, характеризующейся

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

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

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

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

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

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

Параллелизм множества объектов характеризуется следующими параметрами :

1. Суммарная длина программы L – суммируются длины всех операторов по всем ветвям.

2. Средняя длина программы L ср – вычисляется исходя из ранга задачи.

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

3. Величина расхождения задачи D

Если программа обработки информации по всем r объектам в точности одинакова, то D =1 и чем сильнее между собой отличаются программы разных объектов, тем больше D .

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

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

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

Рис. 2.8. Информационный граф задачи, характеризующейся

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

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

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

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

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

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

Локальный параллелизм характеризуется следующими параметрами :

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

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

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

4. Глубина параллелизма смежных операций L ПСО – это математическое ожидание длины цепочки операций, которые можно выполнять одновременно

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

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

________________________________________________________________________________________________

Курс «Организация ЭВМ»

10 -

(курсовой проект)

А также другие работы, которые могут Вас заинтересовать
54055.		Урочисте відкриття тижня Логіки	149.5 KB
	Учень. Відкрити тиждень логіки дозволяю Капітанів прошу представити команди і здати рапорти команди здають рапорти 1 учень. Увага Увага 2 учень. Доброго дня дорогі діти і гості 1 учень.
54056.		Інтегрування змісту навчальних предметів та логіки	120.5 KB
	Дітям необхідно знати правила і закони логіки у них мають бути сформовані логічні вміння розвинуте логічне мислення. Особливо виразно продуктивність застосування інтегрованого підходу можна побачити на уроках логіки. Знання учителя основних правил і законів логіки дає змогу користуватися логічними прийомами під час розвязування проблемних ситуацій з будь якої освітньої галузі; розвивати в учнів вміння застосовувати правила і закони логіки щодо аналізу подій явищ оцінки своїх і чужих думок формулювати і приймати обґрунтовані рішення під...
54057.		Межпредметная интеграция как средство активизации учебного процесса	135.5 KB
	В специализированных школах с углубленным изучением иностранного языка межпредметная интеграция должна занимать не последнее место. В этой связи совместные уроки математики и английского языка могут быть очень интересными.
54058.		АЛГЕБРА ВЫСКАЗЫВАНИЙ. ОСНОВНЫЕ ОПЕРАЦИИ АЛГЕБРЫ ВЫСКАЗЫВАНИЙ	1.77 MB
	Таблица истинности - это таблица, устанавливающая соответствие между всеми возможными наборами логических переменных, входящих в логическую функцию и значениями функции.
54059.		Логика	81.18 KB
	Знаешь ли ты этого человека запутанного в плащ Нет. А между прочим это твой отец. Объект логики это то на что направлен интерес ученого в логике это мышление на человекомышление. Логика это наука не о всем мышлении а о правильном мышлении о правильном рациональном мышлении которое можно выразить в знаково символической форме словами.
54061.		Ліс. Дерева. Кущі. Ягоди. Розвиток зв’язного мовлення	40 KB
	Мета: Збагачувати словник дітей на основі знань, уявлень про довкілля. Учити перераховувати якості, властивості предметів, намагатись давати їм характеристику, формувати вміння найбільш точно застосовувати слова, що підходять до конкретної ситуації або опису.
54062.		Пригоди веселих кошенят	44.5 KB
	Під музичний супровід діти разом із логопедом заходять до музичної зали. Логопед: Доброго ранку доброго дня Хай плещуть долоньки Хай тупають ніжки Хай ротик співає Та сяють усмішки. Піпіпі куди це я потрапила Логопед.
54063.		Логопсихокорекція у роботі з дітьми з порушеннями мовлення	67.5 KB
	Ігри і вправи на розвиток емоційної сфери Казка-гра: Про рибака та рибку Логопед читає уривок з казки О. Гра із шишками напруження та розслаблення мязів рук. Гра з бджілкою напруження та розслаблення мязів ніг. Ведмедиця кличе золоту бджілку погратися з ведмежатами.

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

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

Южно-Российский государственный технический университет

(Новочеркасский политехнический институт)

Шахтинский институт (филиал) ЮРГТУ (НПИ)

ЛЕКЦИИ ПО ДИСЦИПЛИНЕ

«ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ»

Шахты- 2010

Введение

Основные понятия

1. Общие вопросы решения "больших задач"

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

1.2.2 Абстрактные модели параллельных вычислений

1.2.3 Способы параллельной обработки данных, погрешность вычислений

1.3 Понятие параллельного процесса и гранулы распараллеливания

1.4 Взаимодействие параллельных процессов, синхронизация процессов

1.5 Возможное ускорение при параллельных вычислениях (закон Амдаля)

2. Принципы построения многопроцессорных вычислительных систем

2.1 Архитектура многопроцессорных вычислительных систем

2.2 Распределение вычислений и данных в многопроцессорных вычислительных системах с распределенной памятью

2.3 Классификация параллельных вычислительных систем

2.4 Многопроцессорные вычислительные системы c распределенной памятью

2.4.1 Массивно-параллельные суперкомпьютеры серии Cry T3

2.4.2 Кластерные системы класса BEOWULF

Заключение

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

Введение

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

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

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

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

Требования получить максимум производительности при минимальной стоимости привели к разработке многопроцессорных вычислительных комплексов; известны системы такого рода, объединяющие вычислительные мощности тысяч отдельных процессоров. Следующим этапом являются попытки объединить миллионы разнородных компьютеров планеты в единый вычислительный комплекс с огромной производительностью посредством сети Internet. На сегодняшний день применение параллельных вычислительных систем является стратегическим направлением развития вычислительной техники. Развитие "железа" с необходимостью подкрепляются совершенствованием алгоритмической и программной компонент – технологий параллельного программирования.

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

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

Рассмотрим два основных вопроса:

1. Многопроцессорные вычислительные системы – (массивно-параллельные суперкомпьютеры) Cray T3D(E) с количеством процессоров от 40 до 2176. Это суперкомпьютеры с распределенной памятью на RISC-процессорах типа Alpha21164A, с топологией коммуникационной сети – трехмерный тор, операционной системой UNIX с микроядром и трансляторами для языков FORTRAN, HPF, C/C++. Поддерживаемые модели программирования: MPI, PVM, HPF.

2. Беовульф-кластеры рабочих станций. Кластеры рабочих станций – совокупность рабочих станций, соединенных в локальную сеть. Кластер – вычислительная система с распределенной памятью и распределенным управлением. Кластерная система может обладать производительностью, сравнимой с производительностью суперкомпьютеров. Кластеры рабочих станций обычно называют Беовульф-кластерами (Beowulf cluster – по одноименному проекту), связанны локальной сетью Ethernet и используют операционную систему Linux.

Основные понятия

Наиболее распространенной технологией программирования для кластерных систем и параллельных компьютеров с распределенной памятью в настоящее время является технология MPI. Основным способом взаимодействия параллельных процессов в таких системах является передача сообщений друг другу. Это и отражено в названии данной технологии – Message Passing Interface (интерфейс передачи сообщений). Стандарт MPI фиксирует интерфейс, который должен соблюдаться как системой программирования на каждой вычислительной платформе, так и пользователем при создании своих программ. MPI поддерживает работу с языками Фортран и Си. Полная версия интерфейса содержит описание более 125 процедур и функций.

Интерфейс MPI поддерживает создание параллельных программ в стиле MIMD (Multiple Instruction Multiple Data), что подразумевает объединение процессов с различными исходными текстами. Однако писать и отлаживать такие программы очень сложно, поэтому на практике программисты, гораздо чаще используют SPMD-моделъ (Single Program Multiple Data) параллельного программирования, в рамках которой для всех параллельных процессов используется один и тот же код. В настоящее время все больше и больше реализаций MPI поддерживают работу с так называемыми "нитями".

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

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

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

Для локализации взаимодействия параллельных процессов программы можно создавать группы процессов, предоставляя им отдельную среду для общения – коммуникатор. Состав образуемых групп произволен. Группы могут полностью совпадать, входить одна в другую, не пересекаться или пересекаться частично. Процессы могут взаимодействовать только внутри некоторого коммуникатора, сообщения, отправленные в разных коммуникаторах, не пересекаются и не мешают друг другу. Коммуникаторы имеют в языке Фортран тип integer (в языке Си – предопределенный тип MPI Comm).

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

Процессоры с сокращенным набором команд (RISC). В основе RISC-архитектуры (RISC – Reduced Instruction Set Computer) процессора лежит идея увеличения скорости его работы за счет упрощения набора команд.

Исследования показали, что 33% команд типичной программы составляют пересылки данных, 20% – условные ветвления и еще 16% – арифметические и логические операции. В подавляющем большинстве команд вычисление адреса может быть выполнено быстро, за один цикл. Более сложные режимы адресации используются примерно в 18% случаев. Около 75% операндов являются скалярными, то есть переменными целого, вещественного, символьного типа и т. д., а остальные являются массивами и структурами. 80% скалярных переменных – локальные, а 90% структурных являются глобальными. Таким образом, большинство операндов – это локальные операнды скалярных типов. Они могут храниться в регистрах.

Согласно статистике, большая часть времени тратится на обработку операторов "вызов подпрограммы" и "возврат из подпрограммы". При компиляции эти операторы порождают длинные последовательности машинных команд с большим числом обращений к памяти, поэтому даже если доля этих операторов составляет всего 15%, они потребляют основную часть процессорного времени. Только около 1% подпрограмм имеют более шести параметров, а около 7% подпрограмм содержат более шести локальных переменных.

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

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

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

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

1. Общие вопросы решения "больших задач"

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

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

1.1. Современные задачи науки и техники, требующие

для решения суперкомпьютеры

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

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

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

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

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

Науки о материалах

Построение полупроводниковых приборов

Сверхпроводимость

Разработка фармацевтических препаратов

Генетика человека

Астрономия

Транспортные задачи большой размерности

Гидро и газодинамика

Управляемый термоядерный синтез

Разведка нефти и газа

Вычислительные задачи наук о мировом океане

Распознавание и синтез речи, распознавание изображений

Одна из серьезнейших задач – моделирование климатической системы и предсказание погоды. При этом совместно численно решаются уравнения динамики сплошной среды и уравнения равновесной термодинамики. Для моделирования развития атмосферных процессов на протяжении 100 лет и числе элементов дискретизации 2,6×106 (сетка с шагом 10 по широте и долготе по всей поверхности Планеты при 20 слоях по высоте, состояние каждого элемента описывается 10 компонентами) в любой момент времени состояние земной атмосферы описывается 2,6×107 числами. При шаге дискретизации по времени 10 минут за моделируемый промежуток времени необходимо определить 5×104 ансамблей (то есть 1014 необходимых числовых значений промежуточных вычислений). При оценке числа необходимых для получения каждого промежуточного результата вычислительных операций в 102÷103 общее число необходимых для проведения численного эксперимента с глобальной моделью атмосферы вычислений с плавающей точкой доходит до 1016÷1017.

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

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

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

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

Недостатком метода оценки пиковой производительности как числа выполняемых компьютером команд в единицу времени (MIPS, Million Instruction Per Second) дает только самое общее представление о быстродействии, так как не учитывает специфику конкретных программ (трудно предсказуемо, в какое число и каких именно инструкций процессора отобразится пользовательская программа).

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

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

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

При организации параллелизма излишне быстро растут потери производительности. По гипотезе Минского (Marvin Minsky) достигаемое при использовании параллельной системы ускорение вычислений пропорционально двоичному логарифму от числа процессоров (при 1000 процессорах возможное ускорение оказывается равным всего 10).

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

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

Контраргумент. Аналогичное развитие свойственно и параллельным системам.

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

Контраргумент. При реально имеющемся разнообразии архитектур параллельных систем существуют и определенные "устоявшиеся" способы обеспечения параллелизма. Инвариантность создаваемого программного обеспечения обеспечивается при помощи использования стандартных программных средств поддержки параллельных вычислений (программные библиотеки PVM, MPI, DVM и др.). PVM и MPI используются в суперкомпьютерах Cray-T3.

За десятилетия эксплуатации последовательных электронно-вычислительных машинах накоплено огромное программное обеспечение, ориентировано на последовательные электронно-вычислительные машины; переработка его для параллельных компьютеров практически нереальна.

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

Существует ограничение на ускорение вычисление при параллельной реализации алгоритма по сравнению с последовательной.

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

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

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

1.2.1 Принципиальная возможность параллельной обработки

Практически все разработанные к настоящему времени алгоритмы являются последовательными. Например, при вычислении выражения a + b × c , сначала необходимо выполнить умножение и только потом выполнить сложение. Если в электронно-вычислительных машин присутствуют узлы сложения и умножения, которые могут работать одновременно, то в данном случае узел сложения будет простаивать в ожидании завершения работы узла умножения. Можно доказать утверждение, состоящее в том, что возможно построить машину, которая заданный алгоритм будет обрабатывать параллельно.

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

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

1.2.2. Абстрактные модели параллельных вычислений

Модель параллельных вычислений обеспечивает высокоуровневый подход к определению характеристик и сравнению времени выполнения различных программ, при этом абстрагируются от аппаратного обеспечения и деталей выполнения. Первой важной моделью параллельных вычислений явилась машина с параллельным случайным доступом (PRAM – Parallel Random Access Machine), которая обеспечивает абстракцию машины с разделяемой памятью (PRAM является расширением модели последовательной машины с произвольным доступом RAM – Random Access Machine). Модель BSP (Bulk Synchronous Parallel, массовая синхронная параллельная) объединяет абстракции как разделенной, так и распределенной памяти. Считается, что все процессоры выполняют команды синхронно; в случае выполнения одной и той же команды PRAM является абстрактной SIMD-машиной, (SIMD – Single Instruction stream/Multiple Data stream – одиночный поток команд наряду со множественным потоком данных), однако процессоры могут выполнять и различные команды. Основными командами являются считывание из памяти, запись в память и обычные логические и арифметические операции.

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

Базовая модель PRAM поддерживает конкурентные (в данном контексте параллельные) считывание и запись. Известны подмодели PRAM, учитывающие правила, позволяющие избежать конфликтных ситуаций при одновременном обращении нескольких процессоров к общей памяти.

Моделировать схемы из функциональных элементов с помощью параллельных машин с произвольным доступом (PRAM) позволяет теорема Брента. В качестве функциональных элементов могут выступать как 4 основных (осуществляющих логические операции NOT, AND, OR, XOR – отрицание, логическое И, логическое ИЛИ и исключающее ИЛИ соответственно), более сложные NAND и NOR (И-НЕ и ИЛИ-НЕ), так и любой сложности.

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

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

Рисунок 1. Моделирование схемы размера 15, глубины 5 с двумя процессорами с помощью параллельной машины с произвольным доступом (PRAM – машина)

На рисунке 1 приведен результат моделирования схемы размером (общее количество процессоров) n=15 при глубине схемы (максимальное число элементов на каждом из уровней глубины) d=5 с числом процессоров p=2 (одновременно моделируемые элементы объединены в группы прямоугольными областями, причем для каждой группы указан шаг, на котором моделируются ее элементы; моделирование происходит последовательно сверху вниз в порядке возрастания глубины, на каждой глубине по р штук за раз). Согласно теоремы Брента моделирование такой схемы займет не более ceil(15/2+1)=9 шагов.

1.2.3. Способы параллельной обработки данных, погрешность вычислений

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

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

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

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

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

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

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

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

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

Ускорение вычислений достигается за счет использования всех ступеней конвейера для потоковой обработки данных (данные потоком поступают на вход конвейера и последовательно обрабатываются на всех ступенях). Конвейеры могут быть скалярными или векторными устройствами (разница состоит лишь в том, что в последнем случае могут быть использованы обрабатывающие векторы команды). В случае длины конвейера l время обработки n независимых операций составит l+n−1 (каждая ступень срабатывает за единицу времени). При использовании такого устройства для обработки единственной порции входных данных потребуется время l×n и только для множества порций получим ускорение вычислений, близкое к l.

Из рисунка 2 видно, что производительность E конвейерного устройства асимптотически растет с увеличением длины n набора данных на его входе, стремясь к теоретическому максимуму производительности 1/τ

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

1.3. Понятие параллельного процесса и гранулы распараллеливания

Наиболее общая схема выполнения последовательных и параллельных вычислений приведена на рисунке 3 (моменты времени S и E – начало и конец задания соответственно).

Рисунок 3. Диаграммы выполнения процессов при последовательном вычислении – а), при близком к идеальному распараллеливании – б) и в общем случае распараллеливания – в)

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

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

Характерная длина последовательно выполняющейся группы команд в каждом из параллельных процессов называется размером гранулы (зерна). В любом случае целесообразно стремиться к "крупнозернистости" (идеал – диаграмма 3б). Обычно размер зерна (гранулы) составляет десятки-сотни тысяч машинных операций (что на порядки превышает типичный размер оператора языков Fortran или C/C++). В зависимости от размеров гранул говорят о мелкозернистом и крупнозернистом параллелизме.

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

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

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

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

Для реальных задач (традиционно) характерный размер зерна распараллеливания на несколько порядков превышает характерный размер оператора традиционного языка программирования (C/C++ или Fortran).

1.4. Взаимодействие параллельных процессов, синхронизация процессов

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

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

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

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

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

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

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

1.5. Возможное ускорение при параллельных вычислениях (закон Амдаля)

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

Рисунок 4. Схема к выводу закона Амдаля

Закон Амдаля (1967) связывает потенциальное ускорение вычислений при распараллеливании с долей операций, выполняемых априори последовательно. Пусть f (0

При переносе алгоритма на параллельную машину время расчета распределится так:

· f×ts – время выполнения части алгоритма, которую распараллелить невозможно,

· (1-f)×ts/n – время, затраченное на выполнение распараллеленной части алгоритма.

Время t p , необходимое для расчета на параллельной машине с n процессорами, равно

t p =f×ts+(1-f)×ts/n .

Ускорение времени расчета при малой доли последовательной операций (f<<1) возможно достичь (не более чем в n раз) ускорения вычислений.

В случае f=0,5 ни при каком количестве процессоров невозможно достичь S>2! Заметим, что эти ограничения носят фундаментальный характер (их нельзя обойти для заданного алгоритма), однако практическая оценка доли f последовательных операций априори обычно невозможна.

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

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

Рисунок 6. Производительность вычислительной кластерной системы на процедуре умножения матриц (эксперимент и расчет по формуле Амдаля)

На рисунке 6 приведены результаты эксперимента на кластере SCI-MAIN НИВЦ МГУ на задаче умножения матриц по ленточной схеме (размерность 103×103 вещественных чисел двойной точности), экспериментальные данные наилучшим образом (использован метод наименьших квадратов) соответствуют формуле Амдаля при f=0,051.

Закон Амдаля удобен для качественного анализа проблемы распараллеливания.

2. Принципы построения многопроцессорных вычислительных систем

2.1. Архитектура многопроцессорных вычислительных систем

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

Рисунок 7. Параллельные компьютеры:

а) с общей памятью б) с распределенной памятью

Типичный пример такой архитектуры – компьютеры класса SMP (Symmetric Multi Processors), включающие несколько процессоров, но одну память, комплект устройств ввода/вывода и операционную систему. Достоинством компьютеров с общей памятью является относительная простота программирования параллельных задач, минусом – недостаточная масштабируемость. Реальные SMP-системы содержат обычно не более 32 процессоров, для дальнейшего наращивания вычислительных мощностей подобных систем используется NUMA-технология.

В компьютерах с распределенной памятью (мультикомпьютерные системы) каждый вычислительный узел является полноценным компьютером и включает процессор, память, устройства ввода/вывода, операционную систему и др. (рисунок 7б). Типичный пример такой архитектуры – компьютерные системы класса MPP (Massively Parallel Processing), в которых с помощью некоторой коммуникационной среды объединяются однородные вычислительные узлы. Достоинством компьютеров с распределенной памятью является (почти неограниченная) масштабируемость, недостатками – необходимость применения специализированных программных средств (библиотек обмена сообщениями) для осуществления обменов информацией между вычислительными узлами. Для многопроцессорных вычислительных систем с общей и распределенной памятью используются термины сильно- и слабосвязанные машины соответственно.

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

Рисунок 8. Многопроцессорные системы

а) - с общей шиной, б) - с матричным коммутатором

в) - с каскадированием коммутаторов (Омега-сеть)

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

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

Рисунок 9. Варианты топологий связи процессоров в многопроцессорных вычислительных системах

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

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

Топология "решетка" (рисунок 9г) использовалась еще в начале девяностых годов при построении суперкомпьютера Intel Paragon на основе процессоров i860; нахождение минимального пути передачи данных между процессорами A и B для топологии "трехмерная решетка" иллюстрировано на рисунке 10. Топология "двумерный тор" (рисунок 9д) расширяет "двумерную решетку" дополнительными связями, снижающими длину среднего пути (само собой, возможен и "трехмерный тор") и характерна для сетевой технологии SCI. Применяется (рисунок 9e) характеризующаяся наличием связи каждого процессора с каждым трехмерная топология "клика". На рисунке 9з приведен общий вид топологии полной связи всех процессоров между собой; такая топология характеризуется наименьшей длиной среднего пути между процессорами, однако аппаратно практически нереализуема при значительном числе процессоров вследствие катастрофического роста числа связей.

Для топологии "гиперкуб" (рисунок 9и) характерна сокращенная длина среднего пути и близость к структурам многих алгоритмов численных расчетов, что обеспечивает высокую производительность. N-мерный гиперкуб содержит 2N процессоров. Двухмерный гиперкуб – это квадрат, трехмерный гиперкуб образует обычный куб, а четырехмерный гиперкуб представляет собой куб в кубе. Для семейства суперкомпьютеров nCube гиперкуб максимальной размерности 13 содержит 8192 процессора, в системе nCube 3 число процессоров может достигать 65536 (16-мерный гиперкуб).

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

Рисунок 10. Нахождение минимального пути для передачи сообщений между процессорами в топологии "трехмерная решетка"

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

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

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

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

Естественным представляется объединение преимуществ систем с общей (относительная простота создания параллельных программ) и распределенной памятью (высокая масштабируемость); решением этого вопроса явилось создание компьютеров с архитектурой NUMA (Non Uniform Memory Access).

В этом смысле классические SMP-компьютеры обладают архитектурой UMA (Uniform Memory Access). При этом применяется механизм (обычно аппаратного уровня – что быстрее), позволяющий пользовательским программам рассматривать всю (физически) распределенную между процессорами память как единое адресное пространство. Примерами NUMA-компьютеров является построенная еще в семидесятых годах и содержащая объединенный межкластерной шиной набор кластеров система Cm и объединяющий 256 процессоров комплекс BBN Butterfly (1981, фирма BBN Advanced Computers).

2.2. Распределение вычислений и данных в многопроцессорных
вычислительных системах с распределенной памятью

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

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

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

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

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

2.3. Классификация параллельных вычислительных систем

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

SISD (Single Instruction stream / Single Data stream) – одиночный поток команд и одиночный поток данных; к SISD-классу относятся классические последовательные (фон-Неймановского типа) машины. В таких машинах имеется только один поток (последовательно обрабатываемых) команд, каждая из которых инициирует одну скалярную операцию. В этот класс попадают и машины с технологией конвейерной обработки.

SIMD (Single Instruction stream / Multiple Data stream) – одиночный поток команд наряду со множественным потоком данных. При этом сохраняется один поток команд, но включающий векторные команды, выполняющие одну арифметическую операцию сразу над многими данными. Выполнение векторных операций может производиться матрицей процессоров (как в машине ILLIAC IV) или конвейерным способом (Cray-1). Фактически микропроцессоры Pentium VI и Xeon c набором инструкций MMX, SSE, SSE2 являются однокристальными SIMD-системами.

Из стран СНГ SIMD-систем следует назвать ПС-2000 (1972 – 1975) – высокопараллельная компьютерная система для обработки информации с производительностью до 200 млн. оп/с.

MISD (Multiple Instruction stream/Single Data stream) – множественный поток команд и одиночный поток данных. Архитектура подразумевает наличие многих процессоров, обрабатывающих один и тот же поток данных; считается, что таких машин не существует.

MIMD (Multiple Instruction stream / Multiple Data stream) – множественные потоки как команд, так и данных. К классу MIMD принадлежат машины двух типов: с управлением от потока команд и управлением от потока данных; если в компьютерах первого типа используется традиционное выполнение команд последовательно их расположения в программе, то второй тип предполагает активацию операторов по мере их текущей готовности.

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

Классический пример – система Denelcor HEP (Heterogeneous Element Processor); содержит до 16 процессорных модулей, через многокаскадный переключатель связанных со 128 модулями памяти данных, причем все процессорные модули могут работать независимо друг от друга со своими потоками команд, а каждый процессорный модуль может поддерживать до 50 потоков команд пользователей.

2.4. Многопроцессорные вычислительные системы с распределенной памятью

С последнего десятилетия 20 века наблюдается тенденция к монополизации архитектур супер-ЭВМ системами с распределенной памятью, причем в качестве процессоров на вычислительных узлах все чаще применяются легкодоступные готовые устройства. Основными преимуществами таких систем является огромная масштабируемость (в зависимости от класса решаемых задач и бюджета пользователь может заказать систему с числом узлов от нескольких десятков до тысяч); что привело к появлению нового названия для рассматриваемых систем – массивно-параллельные компьютеры (вычислительные системы архитектуры MPP – Massively Parallel Processing).

Первый суперкомпьютер с массивной параллельной обработкой – Connection Machine (СМ-1), была оснащена 64000 процессоров, каждый из который имел собственную память. СМ-1 выполняла сканирование 16 тыс. статей со сводками последних новостей за 1/20 сек. и разработала интегральную схему процессора с 4 тыс. транзисторов за три минуты. Выпуклыми представителями MPP-систем являются суперкомпьютеры серии Cry T3.

Cry T3E (1350) это мультипроцессорная вычислительная система 2000 года выпуска, с распределенной памятью построена из RISC-процессоров. Топология коммуникационной сети – трехмерный тор. Операционная система UNICOS/mk (операционная система UNIX с микроядром). Трансляторы для языков FORTRAN, HPF, C/C++. Тактовая частота 675 МГц. Количество процессоров от 40 до 2176. Максимальный объем оперативной памяти для каждого узла 512 Мбайт и максимальное быстродействие 2938 Гфлоп/с. В отличие от предшественника – Cry T3D, данной системе не требуется фронтальный компьютер.

В системе используется процессор Alpha21164A, однако, при необходимости, его несложно заменить другим, например, более быстродействующим процессором. Каждый процессорный элемент содержит центральный процессор, модуль памяти и коммуникационный узел для связи с другими процессорами. Пропускная способность канала связи между процессорами 325 Мбайт/с.

Поддерживаются модели программирования MPI, PVM, HPF, собственная библиотека обмена сообщениями Cray shmem. Быстродействие, полученное при решении систем линейных алгебраических уравнений, достигает 1,12 Тфлоп/с.

МРР – система состоит из однородных вычислительных узлов, включающих:

Один, а иногда несколько центральных процессоров (обычно архитектуры RISC – Reduced Instruction Set Computing, для которой характерно длинное командное слово для задания операций, сокращенный набор команд и выполнение большинства операций за один такт процессора),

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

Коммуникационный процессор (или сетевой адаптер),

Жесткие диски (необязательно) и/или другие устройства ввода/вывода.

К системе добавляются специальные узлы ввода-вывода и управляющие узлы. Вычислительные узлы связаны некоторой коммуникационной средой (высокоскоростная сеть, коммутаторы и т.п.).

Техническое обслуживание многопроцессорных систем является непростой задачей – при числе вычислительных узлов сотни/тысячи неизбежен ежедневный отказ нескольких из них; система 5k управления ресурсами (программно-аппаратный комплекс) массивно-параллельного компьютера обязана обрабатывать подобные ситуации в обход катастрофического общего рестарта с потерей контекста исполняющихся в данный момент задач.

2.4.1. Массивно-параллельные суперкомпьютеры серии CRY T3

Основанная в 1972 году фирма Cry Research Inc. (сейчас Cry Inc.), прославившаяся разработкой векторного суперкомпьютера Cry 1, в 1993 – 1995 годы выпустила модели Cry T3D/T3E, полностью реализующие принцип систем с массовым параллелизмом (систем MPP-архитектуры). В максимальной конфигурации эти компьютеры объединяют 32 – 2048 процессоров DEC Alpha 21064/150 MHz, 21164/600 MHz, 21164A/675 MHz (в зависимости от модели), вся предварительная обработка и подготовка программ (например, компиляция) выполняется на управляющей машине (хост-компьютере).

Разработчики серии Cry T3D/T3E пошли по пути создания виртуальной общей памяти. Каждый процессор может обращаться напрямую только к своей локальной памяти, но все узлы используют единое адресное пространство. При попытке обращения по принадлежащему локальной памяти другого процессора адресу генерируется специализированное аппаратное прерывание и операционная система выполняет пересылку страницы с одного узла на другой, причем вследствие чрезвычайно высокого быстродействия коммуникационной системы (пиковая скорость передачи данных между двумя узлами достигает 480 Мбайт/с) этот подход в целом оправдан. Однако замечен резко снижающий производительность эффект "пинг-понга" – в случае попадания на одну страницу переменных, модифицируемых несколькими процессорами, эта страница непрерывно мигрирует между узлами. Вычислительные узлы выполняют программы пользователя в монопольном режиме (однозадачный режим).

Конкретное исполнение компьютеров серии Cry T3 характеризуется тройкой чисел, например, 24/16/576 (управляющие узлы/узлы операционной системы/вычислительные узлы); при используемой топологии "трехмерный тор" каждый узел (независимо от его расположения) имеет шесть непосредственных соседей. При выборе маршрута между двумя узлами А и В (3D-координаты которых суть рисунок 11) сетевые машрутизаторы, начиная процесс с начальной вершины А, сначала выполняют смещение по координате X таким образом, пока координаты очередного узла связи и узла B не станут равными; затем аналогичные действия выполняются по координате Y и далее по Z (физически подобная маршрутизация происходит одновременно по всем трем координатам). Смещения могут быть и отрицательными, при отказе одной или нескольких связей возможен их обход.

Другой интересной особенностью архитектуры Cry T3 является поддержка барьерной синхронизации – аппаратная организация ожидания всеми процессами определенной точки в программе, при достижении которой возможна дальнейшая работа. Компьютеры серии T3E демонстрировали производительность 1,8 – 2,5 Тфлопс (на 2048 микропроцессорах Alpha/600 MHz).

Дальнейшим развитием линии массивно-параллельных компьютеров Cry T3 является суперкомпьютер Cry XT3. Каждый вычислительный узел Cry XT3 включает процессор AMD Opteron, локальную память (1 – 8 Гбайт) и обеспечивающий связь по коммуникационному блоку Cry SeaStar канал Hyper Transport, имеющий пиковую производительность (для AMD Opteron 2,4 GHz) от 2,6 Тфлопс (548 процессоров, оперативная память 4,3 Тбайт, топология 6×12×8) до 147 Тфлопс. Cray XT3 работает под управлением операционной системы UNICOS/lc, позволяющей объединять до 30000 вычислительных узлов, применяются компиляторы Fortran 77/90/95 и C/C++, коммуникационные библиотеки MPI (Message Passing Interface c поддержкой стандарта MPI 2.0) и ShMem (разработанная Cray Research Inc. библиотека для работы с общей памятью), стандартные библиотеки численных расчетов.

Несмотря на достигнутые столь высокие результаты в области MPP-систем фирма Cry Inc. производит векторно-конвейерный компьютеры, причем эти модели могут быть объединены в MPP-систему. Производительность каждого процессора компьютера Cry SV1 достигает 4 Гфлопс (общая пиковая производительность системы 32 Гфлопс), общее число процессоров может достигать 1000.

Рисунок 11. Коммуникационная решетка "трехмерный тор" компьютера Cray T3E

2.4.2. Кластерные системы класса BEOWULF

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

Вычислительный кластер представляет собой совокупность вычислительных узлов (от десятков до десятков тысяч), объединенных высокоскоростной сетью c целью решения единой вычислительной задачи. Каждый узел вычислительного кластера представляет собой фактически программируемых электронно-вычислительных машин (часто двух- или четырех- процессорный/ядерный SMP-сервер), работающую со своей собственной операционной системой (в подавляющем большинстве Linux(*)); объединяющую сеть выбирают исходя из требуемого класса решаемых задач и финансовых возможностей, практически всегда реализуется возможность удаленного доступа на кластер посредством InterNet.

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

Windows-кластеры значительной мощности до настоящего времени остаются экзотикой в силу известных причин (несмотря на активно продвигаемые MS решения класса Windows Compute Cluster Server – WCCS).

Одним из первых кластерных проектов явился проект BEOWULF. Проект "БЕОВУЛЬФ" был заложен в созданном на основе принадлежащей NASA организации GSFC (Goddard Space Flight Center) исследовательском центре CESDIS (Center of Excellence in Space Data and Information Sciences) в 1994 году и стартовал сборкой в GSFC 16шестнадцатиузлового кластера (на процессорах 486DX4/100 MHz, 16 Mb памяти, 3 сетевых адаптера на каждом узле и 3 параллельных 10 Mbit Ethernet-кабелей); вычислительная система предназначалась для проведения работ по проекту ESS (Earth and Space Sciences Project).

Позднее в подразделениях NASA были собраны другие модели BEOWULF-подобных кластеров: например, theHIVE (Highly-parallel Integrated Virtual Environment) из 64 двухпроцессорных (Pentium Pro/200 MHz, 4 Gb памяти и 5 коммутаторов Fast Ethernet в каждом) узлов. Именно в рамках проекта Beowulf были разработаны драйверы для реализации режима Channel Bonding.

Рисунок 12. Укрупненная схема вычислительного кластера

"Беовульф" – типичный образец многопроцессорной системы MIMD (Multiple Instruction − Multiple Data), при этом одновременно выполняются несколько программных ветвей, в определенные промежутки времени обменивающиеся данными. Многие последующие разработки во всех странах мира фактически являются кланами Beowulf.

В 1998 году в национальной лаборатории Лос-Аламос астрофизик Michael Warren с сотрудниками группы теоретической астрофизики построили вычислительную систему Avalon, представляющую Linux-кластер на процессорах DEC Alpha/533 MHz. Первоначально Avalon состоял из 68 процессоров, затем был расширен до 140, в каждом узле установлено 256 MB оперативной памяти, EIDE-жесткий диск 3,2 Gb, сетевой адаптер фирмы Kingston.

Узлы соединены с помощью четырех коммутаторов Fast Ethernet и центрального двенадцатипортового коммутатора Gigabit Ethernet фирмы 3Com.

Типичным образцом массивно-параллельной кластерной вычислительной системы являются МВС-1000M (коммуникационная сеть – Myrinet 2000, скорость обмена информацией 120–170 Мбайт/сек, вспомогательные – Fast и Gigabit Ethernet) и МВС-15000ВС.

Требование максимальной эффективности использования ресурсов вычислительных мощностей (как процессорных, так и оперативной и дисковой памяти) отдельных процессоров кластера неизбежно приводит к снижению "интеллектуальности" операционной системы вычислительных узлов до уровня мониторов; с другой стороны, предлагаются распределенные кластерные операционные системы – например, Amoeba, Chorus, Mach и др.

Специально для комплектации аппаратной части вычислительных кластеров выпускаются Bladed - сервера (*) – узкие вертикальные платы, включающие процессор, оперативную память (обычно 256 – 512 МБайт при L2-кэше 128 – 256 КБайт), дисковую память и микросхемы сетевой поддержки; эти платы устанавливаются в стандартные "корзины" формата 3U шириной 19² и высотой 5,25² до 24 штук на каждую (240 вычислительных узлов на стойку высотою 180 см). Для снижения общего энергопотребления могут применяться расходующие всего единицы ватт (против 75 W для P4 или 130 W для кристаллов архитектуры IA-64) процессоры Transmeta Crusoe серии TM 5x00 с технологией VLIW; при этом суммарная потребляемая мощность при 240 вычислительных узлах не превышает 1 кВт.

Заключение

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

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

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

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

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

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

2. Гарви М.Дейтел. Введение в операционные системы (пер. с англ. Л.А.Теплицкого, А.Б.Ходулева, Вс.С.Штаркмана под редакцией Вс.С. Штаркмана). -М.: Мир, 1987 (электронная версия, 2004)

3. Гергель В.П., Стронгин Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем (учебное пособие, изд. 2, дополненное). -Н.Новгород.: изд. ННГУ им. Н.И.Лобачевского, -2003 (электронная версия http://pilger.mgapi.edu/metods/1441/basic_pr.zip).

4. Корнеев В.В. Вычислительные системы. -М.: Гелиос АРВ, -2004, -512 с.

5. Лацис А.О. Как построить и использовать суперкомпьютер. -М.: Бестселлер, 2003.

6. Шпаковский Г.И. Организация параллельных ЭВМ и суперскалярных процессоров. // Учеб. пособие. -Минск.: Белгосуниверситет, 1996. -296 с. (электронная версия http://pilger.mgapi.edu/metods/1441/spakovsk.zip)

7. Шпаковский Г.И., Серикова Н.В. Программирование для многопроцессорных систем в стандарте MPI. -Минск:, БГУ, 2002. -325 с. (электронная версия http://www.cluster.bsu.by/download/book_PDF.pdf, http://pilger.mgapi.edu/metods/1441/pos_mpi.pdf)

По дисциплине "Параллельные вычисления в оптике и оптоинформатике" в 10 семестре Формы...

Лекции по дисциплине «теоретические основы автоматизированного управления»

Задача

... ____________________________ «____»__________________200_ Лекции по дисциплине «Теоретические основы... вычислений : 1) полностью централизованная система - классический последовательный алгоритм 2) полностью децентрализованная система - параллельный ...

КОНСПЕКТ ЛЕКЦИЙ по дисциплине «СЕТЕВЫЕ ТЕХНОЛОГИИ» (дополненная версия) для студентов специальности 7

Конспект

Кафедра «Информационные системы в менеджменте» КОНСПЕКТ ЛЕКЦИЙ по дисциплине «СЕТЕВЫЕ ТЕХНОЛОГИИ» (дополненная версия) для... очень важное преимущество - способность выполнять параллельные вычисления . Когда в вычислительной системе, задача...

Конспект лекций по дисциплине «нейрокомпьютерные системы» шебакпольский

Конспект

Конспект лекций по дисциплине «Нейрокомпьютерные системы» Шебакпольский М.Ф. Содержание... об обучении, простота модели параллельных вычислений . Нет оснований полагать, ... компьютерах, присущая им параллельная природа вычислений теряется; каждая операция...

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

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

Попробуем разобраться, какой из этих факторов оказывается решающим для достижения рекордной производительности. Обратимся к известным историческим фактам. На одном из первых компьютеров мира - 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 раз. Откуда же взялось остальное? Ответ очевиден -- использование новых решений в архитектуре компьютеров. Основное место среди них занимает принцип параллельной обработки данных, воплощающий идею одновременного (параллельного) выполнения нескольких действий.

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

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

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

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

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

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

Сообщения

• Параллельная и конвейерная обработка

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

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

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

  огород может быть вскопан одним солдатом за 10 часов, а рота солдат количеством 50 человек с такими же способностями при одновременной работе выкопают его уже за 12 минут — действие принципа параллельности в действии .

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

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

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

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

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

  Стоимость автомобиля будет колоссальной. Поэтому и возникла конвейерная обработка .

  Современные параллельные системы

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

  Векторно-конвейерные компьютеры

  Особенности таких машин заключаются в наборе векторных команд и конвейерных функциональных устройствах. В отличие от традиционного подхода, векторные команды способны оперировать целыми массивами независимых данных, а значит появляется возможность эффективно загружать доступные конвейеры, т.е. команда вида А=В+С может означать не сложение двух чисел, а двух массивов. Характерный представитель данного направления — семейство векторно-конвейерных компьютеров CRAY.

  Массивно-параллельные компьютеры с распределенной памятью.

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

  Однако, существует значительный минус, превосходящий многие плюсы. В данных компьютерах межпроцессорное взаимодействие идет намного медленнее, чем происходит локальная обработка данных самими процессорами. В связи с этим, очень сложно написать эффективную программу для таких компьютеров, для некоторых алгоритмов иногда просто невозможно. Примеры таких компьютеров: Intel Paragon, IBM SP1, Parsytec, в некоторой степени IBM SP2 и CRAY T3D/T3E, хотя влияние указанного минуса в этих компьютерах значительно меньше. Сети компьютеров, которые все чаще рассматривают как достаточно дешевую альтернативу крайне дорогим компьютерам, так же можно отнести к этому же классу.

  Параллельные компьютеры с общей памятью

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

  Комбинированные системы

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

  Данное направление является в настоящий момент наиболее перспективным для конструирования компьютеров с рекордными показателями производительности .

  Уровни параллелизма

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

  Микроуровень . Выполнение команды разделено на фазы, а фазы нескольких соседних команд могут быть перекрыты за счет конвейеризации. Достичь данный уровень возможно на ВС с одним процессором.

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

  Уровень команд . Несколько команд выполняются параллельно, в процессоре размещаются сразу несколько конвейеров. Характерен для суперскалярных процессоров.

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

  Понятие уровня параллелизма тесно связано с понятием гранулярности. Гранулярность — мера отношения объема вычислений, выполненных в параллельной задаче, к объему коммуникаций (для обмена сообщениями). Степень гранулярности варьируется от мелкозернистой до крупнозернистой. Закон Амдала ориентирован на крупнозернистый
  параллелизм.

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

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

  Литература

  1. Баденко В.Л. Высокопроизводительные вычисления. Учебное пособие. - СПб.: Изд-во Политехн. ун-та, 2010. — 180 с.
  2. Барский А.Б. Параллельные информационные технологии: Учебное пособие/А.Б. Барский.-М.: Интернет-университет информационных технологий; БИНОМ. Лаборатория знаний, 2007.-503 с.: ил.,таб.-(серия «Основы информационных технологий»)- с.20-28, с.56-58.
  3. Корнеев В.В. Вычислительные системы.-М.:Гелиос APB, 2004.-512с., ил.- с. 34-46
  4. Лацис А.О. Параллельная обработка данных. М.: Академия, 2010. - 336 с.
  5. Цилькер Б.Я., Орлов С.А. Организация ЭВМ и систем. Учебник для вузов. - СПб.: Питер, 2004. - 668 с.

Сообщения