Параллельные вычисления

Из проекта Викизнание

Параллельные вычисления — вычисления, в которых операции производятся параллельно. В этом они противоположны последовательным вычислениям.

1 Проблематика вычислений и предпосылки к параллельным вычислениям
2 Математические основы параллельных вычислений
3 Реализация параллельных вычислений
- 3.1 Однопоточный паралеллизм
- 3.2 Многопоточный паралеллизм
4 См. также
- 4.1 Интернет

[редактировать]

Проблематика вычислений и предпосылки к параллельным вычислениям

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

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

[редактировать]

Математические основы параллельных вычислений

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

$5\cdot7+3\cdot13$

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

$(5\cdot7\cdot3)+13$ ,

можно вычислить только последовательно, сначала первое умножение, затем второе, и только после этого — сложение.

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

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

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

Иллюстрация распараллеливания фрагмента алгоритма БПФ.
Последовательный	2 операции за такт максимум	3 операции за такт максимум	Предел параллельности
`1. t1=br·qr 2. t2=bi·qi 3. t3=br·qi 4. t4=bi·qr 5. cr=t1−t2 6. ci=t3+t4 7. xr=ar+cr 8. xi=ai+ci 9. yr=ar−cr 10. yi=ai−ci`	`1. t1=br·qr t2=bi·qi 2. t3=br·qi t4=bi·qr 3. cr=t1−t2 ci=t3+t4 4. xr=ar+cr xi=ai+ci 5. yr=ar−cr yi=ai−ci`	`1. t1=br·qr t2=bi·qi t3=br·qi 2. t4=bi·qr cr=t1−t2 3. ci=t3+t4 xr=ar+cr yr=ar−cr 4. xi=ai+ci yi=ai−ci`	`1. t1=br·qr t2=bi·qi t3=br·qi t4=bi·qr 2. cr=t1−t2 ci=t3+t4 3. xr=ar+cr xi=ai+ci yr=ar−cr yi=ai−ci`

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

[редактировать]

Реализация параллельных вычислений

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

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

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

[редактировать]

Однопоточный паралеллизм

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

Однопоточный паралеллизм обладает своими достоинствами и недостатками. Достоинства:

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

Недостатки:

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

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

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

[редактировать]

Многопоточный паралеллизм

Поэтому были разработаны специальные технологии для создания многопроцессорных систем. Которые позволяли обрабатывать данные параллельно, а, следовательно, быстрее. Соответственного создавались операционные системы поддерживающие многопроцессорные технологии. Такие как: Solaris (Sun Microsystems), Unix-подобные OS: Irix (SGI), AIX (IBM); Linux RedHat; Windows XP. Рассмотрим операционную системы Solaris версии 2.4. Solaris 2.4 - это Unix-подобная система, разработанная Sun Microsystems.

В операционной системе Solaris 2.4 существует такое понятие как поток. Поток (thread) — это последовательность инструкций выполняемых в пределах контекста процесса. Эта операционная система поддерживает многопоточные процессы. Слово «многопоточные» подразумевает содержание множества управляемых потоков. Традиционный UNIX процесс содержит один управляемый поток. Многопоточный в свою очередь содержит множество потоков, которые выполняются независимо. Так как каждый поток выполняется независимо, распараллеливание кода программы приводит к:

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

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

Потоки видны только внутри процесса, когда они разделяют ресурсы процесса такие, как адресное пространство, открытые файлы, и т. д. Каждая нить имеет уникальные ID, регистр, стек, маску, приоритет. Т.к. потоки делят инструкции процесса и большинство данных, изменения данных одним потоком видно другими потоками в процессе. Когда поток должен взаимодействовать с другими потоками процесса, он может сделать это без привлечения операционной системы. Потоки это главный программный интерфейс в многопоточном программировании. Потоки пользовательского уровня управляются в пользовательском пространстве и поэтому могут запрещать контекстному ядру переключение ресурсов. Приложение может иметь тысячи потоков, и не потреблять много ресурсов ядра. Количество ресурсов ядра, потребляемых приложением, во многом определяется самим приложением. По умолчанию потоки «легковесны». Для получения большего контроля за потоками, приложение может ограничивать потоки. Когда приложение ограничивает потоки в доступе к ресурсам, поток становится ресурсами ядра. Функции для работы с потоками, такие как thr_create(….), thr_self(), thr_join(….) и т. д., описаны в библиотеке libthread. Функция thr_create создает поток в зависимости от заданных параметров. Функция thr_join объединяет потоки в параллельный процесс. Функция thr_self возвращает номер потока в процессе.

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

[редактировать]