Последовательность выпуска - Release consistency

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

Введение[1]

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

Согласованность выпуска против последовательной согласованности

Структура оборудования и усилия на программном уровне

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

Условия последовательного непротиворечивого результата

В общем, распределенная разделяемая память является релиз-согласованной, если она подчиняется следующим правилам:[2]

1. Перед выполнением доступа к общей переменной все предыдущие операции сбора данных этим процессором должны быть завершены.

2. Перед выполнением выпуска все предыдущие операции чтения и записи этого процесса должны быть завершены.

3. Доступ к получению и освобождению должен быть согласованный процессор.

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

Реализации[3]

Освобождение замка

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

Снятие блокировки можно рассматривать как вид синхронизации выпуска. Предположим, что операция цикла выполняется с использованием кода, показанного справа. Два потока намереваются войти в критический раздел и прочитать самое последнее значение а, затем выйдите из критического раздела. Код показывает, что поток 0 сначала получает блокировку и входит в критическую секцию. Для правильной работы P1 должен прочитать последнее значение а написано P0. В этом случае только один поток может быть в критической секции одновременно. Следовательно, сама синхронизация гарантирует, что успешное получение блокировки на P1 произойдет после снятия блокировки с помощью P0. Кроме того, необходимо обеспечить порядок S2 -> S3, так как P0 должен распространять новое значение а к P1. По той же причине S5 должен стоять после S4.

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

Пост-ждать

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

Синхронизация после ожидания - еще одна форма реализации согласованности выпуска. Как показано в коде справа, правильность может быть гарантирована, если пост-операции выполняются только после того, как все обращения к памяти завершены, особенно сохранение в «a». Кроме того, операция чтения не должна выполняться, пока не завершится операция ожидания. S2 действует как синхронизация освобождения, а S3 действует как синхронизация получения. Следовательно, S2 необходимо предотвратить предыдущее выполнение после него, а S3 необходимо предотвратить любое последующее выполнение до него. S2 не нужно предотвращать последующее выполнение до него. Аналогично, S3 не нужно предотвращать любое предыдущее выполнение после него.

Последовательность отложенного выпуска[4]

Распространение записи в модели согласованности выпуска

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

пример

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

Распространение записи в модели согласованности отложенного выпуска

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

"TreadMarks"[5] это реальное приложение ленивого выпуска.

Повышение производительности по сравнению с согласованностью выпуска

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

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

Недостаток

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

Согласованность выпуска по сравнению с другими моделями ослабленной согласованности[6]

Слабый порядок (Слабая консистенция )

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

Согласованность процессора

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

Смотрите также

использованная литература

  1. ^ Согласованность памяти и порядок событий в масштабируемых мультипроцессорах с общей памятью Куроша Гарачорлоо, Даниэля Леноски, Джеймса Лаудона, Филиппа Гиббонса, Анупа Гупты и Джона Хеннесси, опубликованные в ISCA '90 Proceedings of the 17th Annual International Symposium on Computer Architecture
  2. ^ Таненбаум, Эндрю (1995). Распределенные операционные системы. Pearson Education. С. 327–330. ISBN  9788177581799.
  3. ^ а б Солихин, Ян (2015). Основы параллельной многоядерной архитектуры. Чепмен и Холл / CRC Вычислительная наука. С. 315–320. ISBN  9781482211184.
  4. ^ Последовательность отложенного выпуска для распределенной разделяемой памяти программного обеспечения Пита Келехера, Алана Л. Кокса и Вилли Цваенепола, опубликованных в Proceeding ISCA '92 Proceedings 19-го ежегодного международного симпозиума по компьютерной архитектуре
  5. ^ TreadMarks: распределенная разделяемая память на стандартных рабочих станциях и операционных системах Пит Келехер, Алан Л. Кокс, Сандхья Двааркадас и Вилли Цваенепол опубликованы в WTEC'94 Proceedings of the USENIX Winter 1994 Technical Conference on USENIX Winter 1994 Technical Conference
  6. ^ Каллер, Дэвид; Гупта, Ануп; Сингх, Джасвиндер (1997). Параллельная компьютерная архитектура: аппаратно-программный подход. Морган Кауфманн Паблишерс Инк., Стр. 620–626. ISBN  1558603433.