Кластерные системы для организации параллельных вычислений
Определение параллелизма как возможности одновременного выполнения нескольких арифметико-логических или служебных операций. Разработка алгоритмов для решения сложных научно-технических задач. Параллельное программирование как источник сложности.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | статья |
Язык | русский |
Дата добавления | 25.05.2018 |
Размер файла | 16,7 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
УДК 621.3.083
Кластерные системы для организации параллельных вычислений
Тен Т.Л., Когай Г.Д., Томилова Н.И.
Параллелизм - это возможность одновременного выполнения нескольких арифметико-логических или служебных операций. На стадии постановки задачи параллелизм не определен, он появляется только после выбора метода вычислений. В зависимости от характера этого метода параллелизм алгоритма, то есть количество одновременно выполняемых операций, может меняться в довольно больших пределах.
Параллелизм используемой ЭВМ также меняется в широких пределах и зависит в первую очередь от числа процессоров, способа размещения данных, методов коммутации и способов синхронизации процессов. Язык программирования является средством переноса параллелизма алгоритма на параллелизм ЭВМ и тип языка может в сильной степени влиять на результат переноса. параллелизм логический программирование сложность
Для сравнения параллельных алгоритмов необходимо уметь оценивать степень параллелизма. Одновременное выполнение операций возможно, если они не зависят друг от друга по данным или управлению.
Разработка алгоритмов (в особенности методов параллельных вычислений) для решения сложных научно-технических задач часто представляет собой значительную проблему. С учетом высказанных предположений последующие действия для определения эффективных способов организации параллельных вычислений могут состоять в следующем:
выполнить анализ имеющихся вычислительных схем и осуществить их разделение (декомпозицию) на части (подзадачи), которые могут быть реализованы в значительной степени независимо друг от друга;
выделить для сформированного набора подзадач информационные взаимодействия, которые должны осуществляться в ходе решения исходной поставленной задачи;
определить необходимую (или доступную) для решения задачи вычислительную систему и выполнить распределение имеющего набора подзадач между процессорами системы.
При самом общем рассмотрении понятно, что объем вычислений для каждого используемого процессора должен быть примерно одинаков - это позволит обеспечить равномерную вычислительную загрузку (балансировку) процессоров. Кроме того, также понятно, что распределение подзадач между процессорами должно быть выполнено таким образом, чтобы количество информационных связей (коммуникационных взаимодействий) между подзадачами было минимальным.
После выполнения всех перечисленных этапов проектирования можно оценить эффективность разрабатываемых параллельных методов: для этого обычно определяются значения показателей качества порождаемых параллельных вычислений (ускорение, эффективность, масштабируемость). По результатам проведенного анализа может оказаться необходимым повторение отдельных (в предельном случае всех) этапов разработки - следует отметить, что возврат к предшествующим шагам разработки может происходить на любой стадии проектирования параллельных вычислительных схем.
Чтобы применить получаемый в конечном итоге параллельный метод, необходимо выполнить разработку программ для решения сформированного набора подзадач и разместить разработанные программы по процессорам в соответствии с выбранной схемой распределения подзадач. Для проведения вычислений программы запускаются на выполнение (программы на стадии выполнения обычно именуются процессами), для реализации информационных взаимодействий программы должны иметь в своем распоряжении средства обмена данными (каналы передачи сообщений).
Следует отметить, что каждый процессор обычно выделяется для решения единственной подзадачи, однако при наличии большого количества подзадач или использовании ограниченного числа процессоров это правило может не соблюдаться и, в результате, на процессорах может выполняться одновременно несколько программ (процессов). В частности, при разработке и начальной проверке параллельной программы для выполнения всех процессов может использоваться один процессор (при расположении на одном процессоре процессы выполняются в режиме разделения времени).
Параллельное программирование представляет дополнительные источники сложности необходимо явно управлять работой тысяч процессоров, координировать миллионы межпроцессорных взаимодействий. Для того, что бы решить задачу на кластере, необходимо распределить вычисления между процессорами системы, так чтобы каждый процессор был занят решением части задачи. Кроме того, желательно, чтобы как можно меньший объем данных пересылался между процессорами, поскольку коммуникации значительно больше медленные операции, чем вычисления.
Часто, возникают конфликты между степенью распараллеливания и объемом коммуникаций, то есть, чем между большим числом процессоров распределена задача, тем больший объем данных необходимо пересылать между ними. Среда параллельного программирования должна обеспечивать адекватное управление распределением и коммуникациями данных.
Основные модели параллельного программирования, их абстракции в параллельном программировании:
Процесс/канал (Process/Channel). В этой модели программы состоят из одного или более процессов, распределенных по процессорам. Процессы выполняются одновременно, их число может измениться в течение времени выполнения программы. Процессы обмениваются данными через каналы, которые представляют собой однонаправленные коммуникационные линии, соединяющие только два процесса. Каналы можно создавать и удалять.
Модель процесс/канал характеризуется следующими свойствами:
Параллельное вычисление состоит из одного или более одновременно исполняющихся процессов, число которых может изменяться в течение времени выполнения программы.
Процесс - это последовательная программа с локальными данными. Процесс имеет входные и выходные порты, которые служит интерфейсом к среде процесса.
В дополнение к обычным операциям процесс может выполнять следующие действия: послать сообщение через выходной порт, получить сообщение из входного порта, создать новый процесс и завершить процесс.
Посылающаяся операция асинхронная - она завершается сразу, не ожидая того, когда данные будут получены. Получающаяся операция синхронная: она блокирует процесс до момента поступления сообщения.
Пары из входного и выходного портов соединяются очередями сообщений, называемыми каналами (channels). Каналы можно создавать и удалять. Ссылки на каналы (порты) можно включать в сообщения, так что связность может измениться динамически.
Процессы можно распределять по физическим процессорам произвольным способами, причем используемое отображение (распределение) не воздействует на семантику программы. В частности, множество процессов можно отобразить на одиночный процессор.
Обмен сообщениями (Message Passing). В этой модели программы, возможно различные, написанные на традиционном последовательном языке исполняются процессорами компьютера. Каждая программа имеет доступ к памяти исполняющего ее процессора. Программы обмениваются между собой данными, используя подпрограммы приема/передачи данных некоторой коммуникационной системы. Программы, использующие обмен сообщениями, могут выполняться только на MIMD компьютерах.
Модель обмен сообщениями не накладывает ограничений ни на динамическое создание процессов, ни на выполнение нескольких процессов одним процессором, ни на использование разных программ для разных процессов. На практике сложилось так, что большинство систем обмена сообщениями при запуске параллельной программы создает фиксированное число идентичных процессов и не позволяет создавать и разрушать процессы в течение работы программы.
В таких системах каждый процесс выполняет одну и ту же программу (параметризованную относительно идентификатора либо процесса, либо процессора), но работает с разными данными, поэтому о таких системах говорят, что они реализуют SPMD (single program multiple data - одна программа много данных) модель программирования. SPMD модель приемлема и достаточно удобна для широкого диапазона приложений параллельного программирования, но она затрудняет разработку некоторых типов параллельных алгоритмов.
Параллелизм данных (Data Parallel). В этой модели единственная программа задает распределение данных между всеми процессорами компьютера и операции над ними. Распределяемыми данными обычно являются массивы. Как правило, языки программирования, поддерживающие данную модель, допускают операции над массивами, позволяют использовать в выражениях целые массивы, вырезки из массивов. Распараллеливание операций над массивами, циклов обработки массивов позволяет увеличить производительность программы. Компилятор отвечает за генерацию кода, осуществляющего распределение элементов массивов и вычислений между процессорами. Каждый процессор отвечает за то подмножество элементов массива, которое расположено в его локальной памяти.
Следовательно, компиляторы языков с параллелизмом данных часто требуют, чтобы программист предоставил информацию относительно того, как данные должны быть распределены между процессорами, другими словами, как программа должны быть разбита на процессы. Компилятор транслирует программу с параллелизмом данных в SPMD программу, генерируя коммуникационный код автоматически.
Общей памяти (Shared Memory). В этой модели все процессы совместно используют общее адресное пространство. Процессы асинхронно обращаются к общей памяти как с запросами на чтение, так и с запросами на запись, что создает проблемы при выборе момента, когда можно будет поместить данные в память, когда можно будет удалить их. Для управления доступом к общей памяти используются стандартные механизмы синхронизации - семафоры и блокировки процессов.
В модели программирования с общей памятью, все процессы совместно используют общее адресное пространство, к которому они асинхронно обращаются с запросами на чтение и запись. В таких моделях для управления доступом к общей памяти используются всевозможные механизмы синхронизации типа семафоров и блокировок процессов.
Преимущество этой модели с точки зрения программирования состоит в том, что понятие собственности данных (монопольного владения данными) отсутствует, следовательно, не нужно явно задавать обмен данными между производителями и потребителями.
Список используемых источников
1. Г.И. Малашонок, А.И. Аветисян, Ю.Д. Валеев, М.С. Зуев. Параллельные алгоритмы компьютерной алгебры, 2004. -376 с.
2. Вл.В.Воеводин, А.П.Капитонова. Методы описания и классификации вычислительных систем". М.: Издательство МГУ,1994, 413 с.
3. В.В.Воеводин, Вл.В.Воеводин. Параллельные вычисления. М.: Издательство МГУ, 2002. -342 с.
Размещено на Allbest.ru
...Подобные документы
Математическая основа параллельных вычислений. Свойства Parallel Computing Toolbox. Разработка параллельных приложений в Matlab. Примеры программирования параллельных задач. Вычисление определенного интеграла. Последовательное и параллельное перемножение.
курсовая работа [1,1 M], добавлен 15.12.2010Основные модели вычислений. Оценки эффективности параллельных алгоритмов, их коммуникационная трудоемкость. Последовательный алгоритм, каскадная схема и способы ее улучшения. Модифицированная каскадная схема. Передача данных, классификация операций.
презентация [1,3 M], добавлен 10.02.2014Пути достижения параллелизма вычислений. Понятие и разновидности, а также сферы и особенности использования суперкомпьютеров. Параллельные вычисления как процессы решения задач, в которых могут выполняться одновременно несколько вычислительных операций.
презентация [8,3 M], добавлен 11.10.2014Пакетный метод как основной способ выполнения коммуникационных операций, его содержание и предъявляемые требования. Оценка трудоемкости операции передачи данных между двумя узлами кластера. Этапы разработки параллельных алгоритмов (распараллеливания).
презентация [318,1 K], добавлен 10.02.2014Алгоритм логарифмического сдваивания. Средняя степень параллелизма. Характеристики векторных компьютеров. Модель ускорения для параллельной вычислительной системы. Суммирование методом рекурсивного удвоения. Условия выполнения несогласованного алгоритма.
лекция [183,2 K], добавлен 22.10.2014Общая характеристика и свойства системы Matlab - пакета прикладных программ для решения задач технических вычислений. Разработка математической модели в данной среде, программирование функций для задающего воздействия. Проектирование GUI-интерфейса.
курсовая работа [1023,2 K], добавлен 23.05.2013Понятие двоично-десятичного кода (ДДК), его получение и использование. Изучение арифметико-логических устройств, использующихся для обработки ДДК. Алгоритмы сложения, вычитания, умножения и деления ДДК при помощи арифметико-логических устройств.
контрольная работа [145,5 K], добавлен 05.09.2010Классификация параллельных ВС. Системы с общей и распределенной памятью. Конвейеры операций. Производительность идеального конвейера. Суперскалярные архитектуры. VLIW-архитектура. Предсказание переходов. Матричные процессоры. Законы Амдала и Густафсона.
курсовая работа [810,9 K], добавлен 03.10.2008Запоминающие устройства компьютера. Создание системы памяти. Характеристика микросхем динамических запоминающих устройств. Выполнение арифметических, логических или служебных операций. Ярусно-параллельная форма алгоритма. Степень и уровни параллелизма.
презентация [2,4 M], добавлен 28.03.2015Многоблочный метод решения сложных задач. Программирование параллельных ЭВМ. Алгоритм сокращения критического пути (CPR). Упаковка в контейнеры. Алгоритмы EVAH. Общая архитектура разработанного средства. Первоначальные предложения по отображению.
дипломная работа [611,5 K], добавлен 15.10.2010- Разработка алгоритмов и программ для определения сходства семантических сетей на основе их сложности
Семантические сети как модели представления знаний. Основные методы определения сходства графовых моделей систем. Метод решения задач определения сходства семантических сетей на основе их сложности. Разработка алгоритмов и их программная реализация.
дипломная работа [1,3 M], добавлен 17.12.2011 Теоретическое изучение системы проведения арифметических операций над двоичными числами. Создание описания операций умножения и блок-схемы алгоритма её выполнения. Определение набора управляющих сигналов и синтез схемы арифметико-логического устройства.
курсовая работа [169,3 K], добавлен 25.12.2012Разработка технологии обработки информации, а также структуры и формы представления данных. Подбор алгоритма и программы решения задачи. Определение конфигурации технических средств. Специфика процесса тестирования и оценки надежности программы.
курсовая работа [959,1 K], добавлен 12.12.2011Понятие алгоритма и анализ теоретических оценок временной сложности алгоритмов умножения матриц. Сравнительный анализ оценки временной сложности некоторых классов алгоритмов обычным программированием и программированием с помощью технологии Open MP.
дипломная работа [1,6 M], добавлен 12.08.2017Изучение особенностей создания алгоритмов вычислительных задач. Визуальное программирование стандартных компонентов среды программирования Delphi. Технология создания компонента Delphi для решения производственной задачи. Выполнение блок-схемы алгоритма.
курсовая работа [638,0 K], добавлен 30.01.2015Классификация алгоритмов маршрутизации. Методы передачи данных. Характеристики коммуникационной составляющей длительности выполнения параллельного алгоритма. Преимущества и недостатки CTR. Оценки трудоемкости для различных топологий и кластеров.
презентация [875,8 K], добавлен 10.02.2014Программирование логических игр с помощью подходов СИИ. Методы работы с Windows Forms в языке С#, алгоритм поиска в пространстве состояний. Формализация дерева состояний. Описание использованных алгоритмов. Иерархическая схема и блок-схемы программы.
курсовая работа [1,7 M], добавлен 01.12.2015Основные направления развития параллелизма, модели параллельного программирования. Автоматические средства разработки параллельного ПО, анализ последовательной программы. Разработка системы автоматического распараллеливания программ на языке Fortran77.
дипломная работа [57,7 K], добавлен 14.10.2010Средства формализации процесса определения спецификаций. Назначение языка (PSL) и анализатора определения задач (PSA). Разработка алгоритма решения задачи, критерии оценки его сложности. Локальный и глобальный уровни повышения эффективности алгоритмов.
контрольная работа [144,9 K], добавлен 26.10.2010Цель ТРИЗ - области знаний о механизмах развития технических систем и методах решения изобретательских задач. Значение точной формулировки мини-задачи. Три вида противоречий в порядке возрастания сложности разрешения. Законы развития технических систем.
презентация [248,5 K], добавлен 18.03.2017