Можно ли проводить параллельные вычисления на одном компьютере

Обновлено: 02.07.2024

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

Содержание

Безопасность

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

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

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

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

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

Модель параллельного выполнения программы

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

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

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

Классификация

Типы паралельных машин различаются по типу памяти – общая (shared) или распределенная (distributed), и по типу управления – SIMD и MIMD. Получается, четыре типа параллельных машин.

Общая память

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

Рисунок 1 – схема классического компьютера.

Способ расширить эту схему с учетом нескольких процессоров показан на рисунке 2.

Рисунок 2 – схема с учетом нескольких процессоров.

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

Вот как выглядит построенный по такой схеме Quad Pentium:

Рисунок 3 – схема Quad Pentium.

SIMD и MIMD

SIMD – Singe Instruction stream, Multiple Data stream. Управляющий узел один, он отправляет инструкции всем остальным процессорам. Каждый процессор имеет свой набор данных для работы.
MIMD – Multiple Instruction stream, Multiple Data Stream. Каждый процессор имеет свой собственный управляющий юнит, каждый процессор может выполнять разные инструкции.

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

Рисунок 4 – архиректуры SIMD и MIMD.

Так как “управляющий” процессор отправляет одни и те же инструкции всем “рабочим” процессорам, программирование таких систем требует некоторой сноровки. [Источник 3]

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

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

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

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

Классификация Флина

Наибольшее распространение получила классификация вычислительных систем, предложенная в 1966 г. профессором Стенфордского университета М.Д.Флином (M.J.Flynn) - классификация Флина. Эта классификация охватывает только два классификационных признака – тип потока команд и тип потока данных.

Классификация по типу потока команд

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

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

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

Классификация по типу потока данных

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

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

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

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

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

векторно-конвейерные вычислительные системы;
векторно-параллельные вычислительные системы или матричные вычислительные системы.

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

Рассмотренная классификации Флина позволяет по принадлежности компьютера к классу SIMD или MIMD сделать сразу понятным базовый принцип его работы. Часто этого бывает достаточно. Недостатком классификации Флина является "переполненность" класс MIMD.

Классификация по типу строения оперативной памяти

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

В вычислительных системах с общей памятью (Common Memory Systems или Shared Memory Systems) значение, записанное в память одним из процессоров, напрямую доступно для другого процессора. Общая память обычно имеет высокую пропускную способность памяти (bandwidth) и низкую латентность памяти (latency) при передачи информации между процессорами, но при условии, что не происходит одновременного обращения нескольких процессоров к одному и тому же элементу памяти. К общей памяти доступ разных процессорами системы осуществляется, как правило, за одинаковое время. Поэтому такая память называется еще UMA-памятью (Unified Memory Access) — памятью с одинаковым временем доступа. Система с такой памятью носит название вычислительной системы с одинаковым временем доступа к памяти. Системы с общей памятью называются также сильносвязанными вычислительными системами.

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

Вычислительные системы с гибридной памятью - (Non-Uniform Memory Access Systems) имеют память, которая физически распределена по различным частям системы, но логически разделяема (образует единое адресное пространство). Такая память называется еще логически общей (разделяемой) памятью (logically shared memory). В отличие от UMA-систем, в NUMA-системах время доступа к различным частям оперативной памяти различно.

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

Классификация по типу коммуникационной сети

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

Классификация по степени однородности

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

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

В настоящее время большинство высокопроизводительных систем относятся к классу однородных систем с общей памятью или к классу однородных систем с распределенной памятью. Рассмотренные классификационные признак и параллельных вычислительных систем не исчерпывают всех возможных их характеристик. Существует, например, еще разделение систем по степени согласованности режимов работы (синхронные и асинхронные вычислительные системы), по способу обработки (с пословной обработкой и ассоциативные вычислительные системы), по жесткости структуры (системы с фиксированной структурой и системы с перестраиваемой структурой), по управляющему потоку (системы потока команд -instruction flow и системы потока данных — data flow) и т.п.

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

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

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

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

Что самое удивительное, в университетах пока не спешат переводить программы обучения в русло параллельных вычислений! При этом сегодня нужно постараться, чтобы найти компьютер с одним ядром. В моем родном Carleton University курсы по параллельным вычислениям не входят в обязательную программу Bachelor of Computer Science, и доступны лишь для тех, кто прошел основные курсы первых трех лет. На том же уровне находятся курсы по распределенным вычислениям, и некоторых могут сбить с толку.

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

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

Вы можете спросить: а зачем нужно было придумывать новую структуру, потом корпеть над новыми алгоритмами, и нельзя ли было продолжать ускорять обычные компьютеры? Во-первых, пока нет возможности сделать один супер-быстрый процессор, который можно было бы сравнить с современными параллельными супер-компьютерами; а если и есть, то ресурсов на это уйдет уйма. К тому же, многие задачи хорошо решаются паралелльными машинами в первую очередь благодаря такой структуре! Расчет сложных хаотических систем вроде погоды, симуляции взаимодействий элементарных частиц в физике, моделирование на нано-уровне (да, да, нанотехнологии!), data mining (про который у нас на сайте есть блог), криптография… список можно долго продолжать.
Для программиста, как конечного “пользователя” параллельной машины, возможны два варианта: параллельность ему может быть “видна”, а может и нет. В первом случае программист пишет программы с расчетом на архитектуру компьютера, берет в расчет параметры этой конкретной машины. Во втором программист может и не знать, что перед ним не-классический компьютер, а все его классические методы умудряются работать благодаря продуманности самой системы.

Вот пример многоядерного процессора — любимый многими SUN UltraSPARC T1/T2:

8 ядер, каждое поддерживает 4 (у Т1) или 8 (у Т2) аппаратных потоков (thread), что простым умножением дает нам 32/64 (соответственно) потоков в процессоре. Теоретически это означает, что такой процессор может выполнять 32/64 задачи однопотокового процессора за то же время. Но, конечно же, много ресурсов тратится на переключение между потоками и прочую “внутреннюю кухню”.

А вот, например, знаменитые крутейшие графические юниты вроде nVidia GeForce 9600 GT, на борту которого 64 ядра.

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

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

256 ядер: 64 юнита, в каждом 4 ядра по 2.2 Ггц и по 8 гигабайт ОЗУ. Для соединения используется свитч Foundry SuperX и гигабитная сеть. ОС — Linux Rocks. Самым дорогим элементом часто является именно свитч: попробуйте найти быстрый свитч на 64 порта! Это пример одной из самых больших проблем параллельных компьютеров: скорость обмена информацией. Процессоры стали очень быстрыми, а память и шины все еще медленные. Не говоря уже о жестких дисках — по сравнению с процессорами они выглядят как орудия каменного века!

Классификация

Давайте наконец разберемся в типах паралельных машин. Они различаются по типу памяти — общая (shared) или распределенная (distributed), и по типу управления — SIMD и MIMD. Получается, четыре типа параллельных машин.

Общая память

Классический компьютер выглядит так:

И самый очевидный способ расширить эту схему с учетом нескольких процессоров таков:

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

Вот как выглядит построенный по такой схеме Quad Pentium:

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

Как вы наверное и сами догадались, в этом случае у каждого процессора “своя” память (напомню, что речь идет не о внутренней памяти процессора).

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

Самый простой вариант, который приходит на ум, это простой двумерный массив (mesh):

Похожей структурой обладает IBM Blue Gene, потомок знаменитого IBM Deep Blue, обыгравшего человека в шахматы. Похожей, потому что на самом деле Blue Gene это не куб, а тор — крайние элементы соединены:

Кстати, его назвали Gene, потому что он активно применяется в генетических исследованиях.

Другая интересная структура, которая должна была придти кому-то в голову, это любимое всеми дерево:

Так как глубина (или высота) бинарного дерева это logn, передача информации от двух наиболее удаленных узлов будет проходить расстояние 2*logn, что очень хорошо, но такая структура все равно используется не часто. Во-первых, чтобы разделить такую сеть на две изолированные подсети достаточно разрезать один провод (помните проблему min-cut?) В случае двумерного массива нужно разрезать sqrt(n) проводов! У куба посчитайте сами. А во-вторых, через корневой узел проходит слишком много трафика!

В 80е были популярны четырехмерные гиперкубы:

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

Вообще, дизайн сети для решения какой-то задачи — тема интересная. Вот, например, так называемая Omega Network:

С памятью разобрались, теперь об управлении.

SIMD vs. MIMD

SIMD — Singe Instruction stream, Multiple Data stream. Управляющий узел один, он отправляет инструкции всем остальным процессорам. Каждый процессор имеет свой набор данных для работы.
MIMD — Multiple Instruction stream, Multiple Data Stream. Каждый процессор имеет свой собственный управляющий юнит, каждый процессор может выполнять разные инструкции.

Так как “управляющий” процессор отправляет одни и те же инструкции всем “рабочим” процессорам, программирование таких систем требует некоторой сноровки. Вот простой пример:

if (B == 0)
then C = A
else C = A/B
Начальное состоянии памяти процессоров такое:

Первая строчка выполнилась, данные считались, теперь запускается вторая строка: then

При этом второй и третий процессоры ничего не делают, потому что переменная B у них не подходит под условие. Соответственно, далее выполняется третья строка, и на этот раз “отдыхают” другие два процессора:

Примеры SIMD-машин это старые ILLiac IV, MPP, DAP, Connection Machine CM-1/2, современные векторные юниты, специфичные сопроцессоры и графические юниты вроде nVidia GPU.

MIMD-машины обладают более широким функционалом, поэтому в наших пользовательских компьютерах используются именно они. Если у вас хотя бы двухядерный процессор в лаптопе — вы счастливый обладатель MIMD-машины с общей памятью! MIMD распределенной памятью это суперкомпьютеры вроде IBM Blue Gene, о которых мы говорили выше, или кластеры.

Вот итог всей классификации:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для аппаратуры характерен экспоненциальный рост, что нашло отражение в известном эмпирическом законе Мура, - экспоненциально росли все важнейшие характеристики - объем памяти на всех уровнях, уменьшение времени доступа к памяти, быстродействие процессоров. Согласно закону Мура (Гордон Мур - один из основателей фирмы Intel) каждые полтора года значения характеристик увеличивались вдвое. Росло и число процессоров, включаемых в состав компьютера. Изменялась и архитектура компьютера . Эти изменения во многом были шагами в сторону распараллеливания вычислений. Вот лишь некоторые изменения в архитектуре процессоров, связанные непосредственно с процессом распараллеливания:

Конвейерная обработка команд. Процесс выполнения потока команд процессором уже не рассматривался как последовательное выполнение команды за командой. Обработка потока команд выполнялась на конвейере, так что сразу несколько команд готовились к выполнению. При конвейерной обработке команды, не связанные между собой по данным, могли выполняться одновременно, что является уже настоящим параллелизмом.
"Длинные команды". Архитектура некоторых компьютеров включала несколько процессоров, позволяющих выполнять логические и арифметические операции над целыми числами, несколько процессоров, выполняющих операции над числами с плавающей точкой. Длинная команда позволяла указать в одной команде действия, которые должен выполнить каждый из существующих процессоров. Опять таки, это позволяло реализовать параллелизм на аппаратном уровне.
Векторные и матричные процессоры. В набор команд таких процессоров включаются базисные операции над векторами и матрицами. Одной командой, например, можно сложить две матрицы. Такая команда фактически реализует параллельные вычисления. Приложения, где эти операции составляют основу обработки данных, широко распространены. Реализуемая аппаратно параллельная обработка данных позволяет существенно повысить эффективность работы приложений этого класса.
Графические процессоры. Еще одним важным видом приложений, где на аппаратном уровне происходит параллельное выполнение, являются приложения, интенсивно работающие с графическими изображениями. Эту обработку осуществляют графические процессоры. Графическое изображение можно рассматривать как набор точек. Обработка изображения зачастую сводится к выполнению одной и той же операции над всеми точками. Распараллеливание по данным легко реализуется в такой ситуации. Поэтому графические процессоры давно уже стали многоядерными, что позволяет распараллелить обработку и эффективно обрабатывать изображение.
Суперкомпьютеры. К суперкомпьютерам относят компьютеры с максимальными характеристиками производительности на данный момент. В их состав входят сотни тысяч процессоров. Эффективное использование суперкомпьютеров предполагает самое широкое распараллеливание вычислений.

В научных исследованиях и в новых технологиях всегда есть задачи, которым требуется вся мощь существующих вычислительных комплексов. Научный потенциал страны во многом определяется существованием у нее суперкомпьютеров. Понятие суперкомпьютера это относительное понятие. Характеристики суперкомпьютера десятилетней давности сегодня соответствуют характеристикам рядового компьютера. Сегодняшние суперкомпьютеры имеют производительность , измеряемую в петафлопсах (10 15 операций с плавающей точкой в секунду). К 2020 году ожидается, что производительность суперкомпьютеров повысится в 1000 раз и будет измеряться в экзафлопсах.

Классификация компьютеров

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

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

Мы не будем рассматривать подробную классификацию компьютеров класса MIMD. Остановимся только на другом способе разделения компьютеров на три класса:

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

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

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

СОДЕРЖАНИЕ

Вступление

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

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

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

Точное время выполнения задач в параллельной системе зависит от расписания , и задачи не всегда должны выполняться одновременно. Например, для двух задач T1 и T2:

T1 может быть выполнен и завершен до T2 или наоборот (последовательный и последовательный)
Т1 и Т2 могут выполняться поочередно (последовательно и одновременно)
T1 и T2 могут выполняться одновременно в один и тот же момент времени (параллельно и одновременно)

Слово «последовательный» используется как антоним как «параллельный», так и «параллельный»; когда они явно различаются, параллельные / последовательные и параллельные / последовательные используются как противоположные пары. Расписание, в котором задачи выполняются по одной (последовательно, без параллелизма), без чередования (последовательно, без параллелизма: ни одна задача не начинается до завершения предыдущей задачи), называется последовательным расписанием . Набор задач, которые можно планировать последовательно, можно сериализовать , что упрощает управление параллелизмом .

Координация доступа к общим ресурсам

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

Предположим balance = 500 , и два параллельных потока выполняют вызовы withdraw(300) и withdraw(350) . Если строка 3 в обеих операциях выполняется перед строкой 5, обе операции обнаруживают, что она balance >= withdrawal равна true , и выполнение переходит к вычитанию суммы снятия. Однако, поскольку оба процесса производят снятие средств, общая снятая сумма в конечном итоге будет больше, чем исходный баланс. Подобные проблемы с общими ресурсами выигрывают от использования контроля параллелизма или неблокирующих алгоритмов .

Преимущества

Преимущества параллельных вычислений:

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

Модели

Представленные в 1962 году сети Петри были первой попыткой кодифицировать правила одновременного выполнения. Позже на их основе была основана теория потоков данных, и были созданы архитектуры потоков данных, чтобы физически реализовать идеи теории потоков данных. Начиная с конца 1970-х годов, были разработаны процессы исчисления, такие как исчисление коммуникационных систем (CCS) и коммуникационные последовательные процессы (CSP), чтобы позволить алгебраические рассуждения о системах, состоящих из взаимодействующих компонентов. Π-исчисление добавлена возможность для рассуждений о динамических топологиях.

Автоматы ввода / вывода были представлены в 1987 году.

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

Модели согласованности

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

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

Реализация

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

Взаимодействие и общение

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

История

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

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

Распространенность

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

На уровне языка программирования:

На уровне операционной системы:

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

Разделение времени , заменившее последовательную пакетную обработку заданий на одновременное использование системы.

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

Языки, поддерживающие параллельное программирование

Многие языки параллельного программирования были разработаны больше как языки для исследований (например, Pict ), а не как языки для производственного использования. Однако такие языки, как Erlang , Limbo и occam , за последние 20 лет в разное время использовались в промышленности. Неполный список языков, которые используют или предоставляют средства параллельного программирования:

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

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

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

Содержание

Задний план

Закон Амдала и закон Густафсона

Графическое представление Закон Амдала. Ускорение программы от распараллеливания ограничено тем, какая часть программы может быть распараллелена. Например, если 90% программы можно распараллелить, теоретическое максимальное ускорение с использованием параллельных вычислений будет в 10 раз, независимо от того, сколько процессоров используется.

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

S_{задержка} это потенциал ускорение в задержка выполнения всей задачи;
s - ускорение задержки выполнения распараллеливаемой части задачи;
п - это процент времени выполнения всей задачи относительно распараллеливаемой части задачи до распараллеливания.

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

Зависимости

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

Рассмотрим следующие функции, которые демонстрируют несколько видов зависимостей:

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

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

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

Условия гонки, взаимное исключение, синхронизация и параллельное замедление

Поток А	Резьба B
1A: чтение переменной V	1B: чтение переменной V
2A: добавить 1 к переменной V	2B: добавить 1 к переменной V
3A: обратная запись в переменную V	3B: обратная запись в переменную V

Если команда 1B выполняется между 1A и 3A или если команда 1A выполняется между 1B и 3B, программа выдаст неверные данные. Это известно как состояние гонки. Программист должен использовать замок предоставлять взаимное исключение. Блокировка - это конструкция языка программирования, которая позволяет одному потоку управлять переменной и предотвращать ее чтение или запись другими потоками, пока эта переменная не будет разблокирована. Поток, удерживающий блокировку, может выполнить свое критическая секция (раздел программы, требующий монопольного доступа к некоторой переменной), и для разблокировки данных по завершении. Следовательно, чтобы гарантировать правильное выполнение программы, указанная выше программа может быть переписана для использования блокировок:

Поток А	Резьба B
1A: переменная блокировки V	1B: заблокировать переменную V
2A: чтение переменной V	2B: чтение переменной V
3A: добавить 1 к переменной V	3B: добавить 1 к переменной V
4A: обратная запись в переменную V	4B: обратная запись в переменную V
5A: переменная разблокировки V	5B: переменная разблокировки V

Мелкозернистый, крупнозернистый и неприятный параллелизм

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

Модели согласованности

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

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

Математически эти модели можно представить несколькими способами. Представлен в 1962 году, Сети Петри были ранней попыткой кодифицировать правила моделей согласованности. Теория потока данных позже основывалась на этом, и Архитектуры потока данных были созданы для физической реализации идей теории потоков данных. Начиная с конца 1970-х гг., технологические расчеты такие как Расчет коммуникационных систем и Связь последовательных процессов были разработаны, чтобы позволить алгебраические рассуждения о системах, состоящих из взаимодействующих компонентов. Более свежие дополнения к семейству исчислений процессов, такие как π-исчисление, добавили возможность рассуждать о динамических топологиях. Логика вроде Лампорта TLA +, и математические модели, такие как следы и Диаграммы актерских событий, также были разработаны для описания поведения параллельных систем.

Таксономия Флинна

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

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

Типы параллелизма

Битовый параллелизм

Читайте также: