Файл: Синхронизация. Два вида синхронизации. Синхронизация.docx
Добавлен: 26.10.2023
Просмотров: 22
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Методы параллельных вычислений
-
Синхронизация. Два вида синхронизации.
Синхронизация (synchronization) - это механизм, управляющий порядком выполнения задач. При совместном использовании данных, а также когда задачи взаимодействуют друг с другом или конкурируют между собой, нужны два вида синхронизации. Синхронизация взаимодействия (cooperation synchronization) между задачами А и В требуется, когда задача А должна ожидать, пока задача В закончит выполнение определенных действий, прежде чем задача А сможет продолжить свою работу. Синхронизация конкуренции (competition synchronization) между двумя задачами необходима, когда обе задачи нуждаются в использовании некоторого ресурса, который невозможно использовать одновременно. В частности, если задача А нуждается в получении доступа к совместно используемой ячейке х в то время, когда эта ячейка находится в распоряжении задачи В, то задача А должна ожидать, пока задача В не закончит обработку ячейки х, независимо от того, что именно представляет собой эта обработка.
Общий подход к обеспечению взаимно исключающего доступа к совместно используемому ресурсу заключается в том, что этот ресурс рассматривается как сущность, которая одновременно может принадлежать только одной задаче. Чтобы получить право владения совместно используемым ресурсом, задача должна запросить его. Завершив свое выполнение, задача должна освободить ресурс, чтобы он стал доступен другим задачам.
Три метода обеспечения взаимно исключающего доступа к совместно используемым ресурсам: семафоры, мониторы, передача сообщений.
Механизмы синхронизации должны иметь возможность задерживать выполнение задач. Синхронизация устанавливает порядок выполнения задач, определяемый этими задержками. Программа, называемая планировщиком (scheduler), управляет распределением процессоров между задачами. Если не происходит никаких прерываний и все задачи имеют одинаковый приоритет, то планировщик просто предоставляет каждой задаче некоторый отрезок времени. Когда подходит очередь какой-либо задачи, планировщик позволяет процессору выполнять ее в течение некоторого времени.
-
Императивное программирование в отличии от декларативного программирования. Асинхронное параллельное программирование?
Кроме императивных (явный параллелизм) программ имеются
декларативные программы — функциональные и логические (неявный
параллелизм).
Асинхронное программирование (условие → действие)
Векторные и конвейерные вычисления
-
Состав однопроцессорной машины.
Современная однопроцессорная машина состоит из нескольких компонентов: центрального процессорного устройства (ЦПУ), первичной памяти, одного или нескольких уровней кэш-памяти (кэш), вторичной (дисковой) памяти и набора периферийных устройств (дисплей, клавиатура, мышь, модем, CD, принтер и т.д.). Основными компонентами для выполнения программ являются ЦПУ, кэш и память.
Процессор выбирает инструкции из памяти, декодирует их и выполняет. Он содержит управляющее устройство (УУ), арифметико-логическое устройство (АЛУ) и регистры. УУ вырабатывает сигналы, управляющие действиями АЛУ, системой памяти и внешними устройствами. АЛУ выполняет арифметические и логические инструкции, определяемые набором инструкций процессора. В регистрах хранятся инструкции, данные и состояние машины (включая счетчик команд).
-
Состав мультипроцессорной машины. Виды организации памяти.
Мультикомпьютеры с распределенной памятью
В мультикомпьютерах с распределенной памятью существуют соединительная сеть, но каждый процессор имеет собственную память. Соединительная сеть поддерживает передачу сообщений. Мультикомпьютеры (многопроцессорные системы с распределенной памятью) не обеспечивают общий доступ ко всей имеющейся в системах памяти. Каждый процессор системы может использовать только свою локальную память, в то время как для доступа к данным, располагаемых на других процессорах, необходимо использовать интерфейсы передачи сообщений (например, стандарт MPI). Данный подход используется при построении двух важных типов многопроцессорных вычислительных систем - массивно-параллельных систем (massively parallel processor or MPP) и кластеров (clusters).
Мультикомпьютер (многомашинная система) –
мультипроцессор с распределенной памятью, в котором процессоры и сеть расположены физически близко (в одном помещении). Также называют тесно связанной машинной. Она одновременно используется одним или небольшим числом приложений; каждое приложение задействует выделенный набор процессоров. Соединительная сеть с большой пропускной способностью предоставляет высокоскоростной путь связи между процессорами.
Сетевая система – это многомашинная система с распределенной памятью, связаны с помощью локальной сети или глобальной сети Internet (слабо связанные мультикомпьютеры). Здесь процессоры взаимодействуют также с помощью передачи сообщений, но время их доставки больше, чем в многомашинных системах, и в сети больше конфликтов. С другой стороны, сетевая система строится на основе обычных рабочих станций и сетей, тогда как в многомашинной системе часто есть специализированные компоненты, особенно у связующей сети.
Под кластером обычно понимается множество отдельных компьютеров, объединенных в сеть, для которых при помощи специальных аппаратно-программных средств обеспечивается возможность унифицированного управления, надежного функционирования и эффективного использования. Кластеры могут быть образованы на базе уже существующих у потребителей отдельных компьютеров, либо же сконструированы из типовых компьютерных элементов, что обычно не требует значительных финансовых затрат. Применение кластеров может также в некоторой степени снизить проблемы, связанные с разработкой параллельных алгоритмов и программ, поскольку повышение вычислительной мощности отдельных процессоров позволяет строить кластеры из сравнительно небольшого количества (несколько десятков) отдельных компьютеров (lowly parallel processing). Это приводит к тому, что для параллельного выполнения в алгоритмах решения вычислительных задач достаточно выделять только крупные независимые части расчетов (coarse granularity), что, в свою очередь, снижает сложность построения параллельных методов вычислений и уменьшает потоки передаваемых данных между компьютерами кластера. Вместе с этим следует отметить, что организация взаимодействия вычислительных узлов кластера при помощи передачи сообщений обычно приводит к значительным временным задержкам, что накладывает дополнительные ограничения на тип разрабатываемых параллельных алгоритмов и программ.
Мультипроцессор с разделяемой памятью
В мультипроцессоре и в многоядерной системе исполнительные устройства (процессоры и ядра процессоров) имеют доступ к разделяемой оперативной памяти. Процессоры совместно используют оперативную память.
У каждого процессора есть собственный кэш. Если два процессора ссылаются на разные области памяти, их содержимое можно безопасно поместить в кэш каждого из них. Проблема возникает, когда два процессора обращаются к одной области памяти. Если оба процессора только считывают данные, в кэш каждого из них можно поместить копию данных. Но если один из процессоров записывает в память, возникает проблема согласованности кэша: в кэш-памяти другого процессора теперь содержатся неверные данные. Необходимо либо обновить кэш другого процессора, либо признать содержимое кэша недействительным. Обеспечение однозначности кэшей реализуется на аппаратном уровне – для этого после изменения значения общей переменной все копии этой переменной в кэшах отмечаются как недействительные и последующий доступ к переменной потребует обязательного обращения к основной памяти. Необходимость обеспечения когерентности приводит к некоторому снижению скорости вычислений и затрудняет создание систем с достаточно большим количеством процессоров.
Наличие общих данных при выполнении параллельных вычислений приводит к необходимости синхронизации взаимодействия одновременно выполняемых потоков команд. Так, например, если изменение общих данных требует для своего выполнения некоторой последовательности действий, то необходимо обеспечить взаимоисключение с тем, чтобы эти изменения в любой момент времени мог выполнять только один командный поток. Задачи взаимоисключения и синхронизации относятся к числу классических проблем, и их рассмотрение при разработке параллельных программ является одним из основных вопросов параллельного программирования.
-
Согласованность памяти.
В системах баз данных согласованность (или корректность) относится к требованию, согласно которому любая данная транзакция с базой данных должна изменять затронутые данные только разрешенными способами. Любые данные, записываемые в базу данных, должны быть действительными в соответствии со всеми определенными правилами, включая ограничения, каскады, триггеры и любую их комбинацию. Это не гарантирует корректность транзакции всеми способами, которые могли потребоваться программисту приложения (за это отвечает код уровня приложения), а просто то, что любые ошибки программирования не могут привести к нарушению каких-либо определенных ограничений базы данных.
Согласованность также можно понимать как то, что после успешной записи, обновления или удаления записи любой запрос на чтение немедленно получает последнее значение записи.
-
Мультипроцессоры с распределенной памятью. Мультикомпьютер.
Во втором типе параллельной архитектуры каждый процессор имеет свою собственную память, доступную только этому процессору. Такая разработка называется мультикомпьютером или системой с распределенной памятью. Она изображена на рис. 8.2, а. Мультикомпьютеры обычно (хотя не всегда) являются системами со слабой связью.
Ключевое отличие мультикомпьютера от мультипроцессора состоит в том, что каждый процессор в мультикомпьютере имеет свою собственную локальную память, к которой этот процессор может обращаться, выполняя команды LOAD и STORE, но никакой другой процессор не может получить доступ к этой памяти с помощью тех же команд LOAD и STORE.
Таким образом, мультипроцессоры имеют одно физическое адресное пространство, разделяемое всеми процессорами, а муль-тикомпыотеры содержат отдельное физическое адресное пространство для каждого центрального процессора.
Поскольку процессоры в мультикомпьютере не могут взаимодействовать друг с другом просто путем чтения из общей памяти и записи в общую память, здесь необходим другой механизм взаимодействия. Они посылают друг другу сообщения, используя сеть межсоединений. В качестве примеров мультикомпьютеров можно назвать IBM SP/2, Intel/Sandia Ootion Red и Wisconsin COW.
При отсутствии памяти совместного использования в аппаратном обеспечении предполагается определенная структура программного обеспечения. В мультикомпьютере невозможно иметь одно виртуальное адресное пространство, из которого все процессы могут считывать информацию и в которое все процессы могут записывать информацию просто путем выполнения команд LOAD и STORE. Например, если процессор 0 (в верхнем левом углу) на рис. 8Д,б обнаруживает, что часть его объекта попадает в другую секцию, относящуюся к процессору 1, он может продолжать считывать информацию из памяти, чтобы получить хвост самолета. Однако если процессор 0 на рис. 8.2, обнаруживает это, он не может просто считать информацию из памяти процессора 1. Для получения необходимых данных ему нужно сделать что-то другое.