Синхронная и асинхронная обработка данных в высокопроизводительных ЭВМ. Параллельные процессы

Московский  институт радиотехники, электроники  и автоматики

 

 

 

 

 

 

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

Синхронная  и асинхронная обработка данных в высокопроизводительных ЭВМ. Параллельные процессы.

 

 

 

 

 

 

 

 

Курсовая

студента II курса

очного отделения

факультета «Кибернетика»

специальности «Компьютерная    

                              безопасность»

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Москва 2011

Содержание

 

 

 

 

 

Введение                                                                                         стр. 3

 

Классификация по Флинну                                                           стр. 3

 

OpenMP                                                                                           стр. 4

 

MPI                                                                                                  стр. 5

 

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

 

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

 

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

 

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

 

Используемая литература                                                             стр. 12

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

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

 

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

 

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

 

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

 

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

 

Потоки команд	Потоки данных	Названия
1	1	SISD
1	Много	SIMD
Много	1	MISD
Много	Много	MIMD

 

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

 

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

 

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

 

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

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

 

OpenMP

 

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

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

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

может существовать зависимость данных.

Зависимость данных существует, если различные

итерации цикла (точнее говоря, итерация, которая 

выполняется в другом потоке) выполняют  чтение

или запись общей памяти.

 

 

MPI

 

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

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

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

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

 

rc = MPI_Xxxxx(parameter, ... );

 

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

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

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

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

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

 

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

 

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

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

• конвейер;

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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