Согласованность выпуска - одна из моделей согласованности на основе синхронизации, используемых в параллельном программировании (например, в распределенной разделяемой памяти , распределенных транзакциях и т. Д.).
Введение [1]
В современных системах параллельных вычислений необходимо поддерживать согласованность памяти, чтобы избежать нежелательных результатов. Модели строгой согласованности, такие как последовательная согласованность , составлены интуитивно, но могут быть весьма ограничивающими с точки зрения производительности, поскольку они отключают параллелизм на уровне команд, который широко применяется в последовательном программировании. Чтобы добиться лучшей производительности, исследуются некоторые расслабленные модели, и последовательность релиза является агрессивной расслабляющей попыткой.
Согласованность выпуска против последовательной согласованности
Структура оборудования и усилия на программном уровне
Последовательная согласованность может быть достигнута простой аппаратной реализацией, в то время как согласованность выпуска также основана на наблюдении, что большинство параллельных программ правильно синхронизированы. На уровне программирования синхронизация применяется для четкого планирования определенного доступа к памяти в одном потоке, который должен происходить за другим. При доступе к синхронизированной переменной аппаратное обеспечение должно гарантировать, что все записи, локальные для процессора, были распространены на все другие процессоры, и все записи от других процессоров просматриваются и собираются. В модели согласованности выпуска действия входа и выхода из критического раздела классифицируются как получение и выпуск, и в любом случае в программу должен быть включен явный код, показывающий, когда выполнять эти операции .
Условия последовательного непротиворечивого результата
В общем, распределенная разделяемая память является релиз-согласованной, если она подчиняется следующим правилам: [2]
1. Прежде чем будет выполнен доступ к общей переменной, все предыдущие операции сбора данных этим процессором должны быть завершены.
2. Перед выполнением выпуска все предыдущие операции чтения и записи этого процесса должны быть завершены.
3. Доступ к получению и освобождению должен согласовываться с процессором .
Если указанные выше условия выполнены и программа правильно синхронизирована (т. Е. Процессоры правильно реализуют получение и выпуск), результаты любого выполнения будут точно такими же, как если бы они были выполнены после последовательной согласованности. Фактически, доступ к совместно используемым переменным разделяется на блоки атомарных операций примитивами получения и освобождения, чтобы предотвратить скачки и чередование между блоками.
Реализации [3]
Разблокировка
Снятие блокировки можно рассматривать как вид синхронизации выпуска. Предположим, что операция цикла выполняется с использованием кода, показанного справа. Два потока намереваются войти в критическую секцию и прочитать самое последнее значение a , а затем выйти из критической секции. Код показывает, что поток 0 сначала получает блокировку и входит в критическую секцию. Для того , чтобы правильно выполнить, P1 должен прочитать последнюю величину написана P0. В этом случае только один поток может быть в критической секции одновременно. Следовательно, сама синхронизация гарантирует, что успешное получение блокировки на P1 произойдет после снятия блокировки с помощью P0. Кроме того, необходимо обеспечить порядок S2 -> S3, поскольку P0 должен передавать новое значение a в P1. По той же причине S5 должен стоять после S4.
Примечательно, что на корректность это не влияет, если доступ к памяти после проблемы разблокировки до завершения разблокировки или доступ к памяти до проблемы блокировки после получения блокировки. Однако код в критическом разделе не может быть выпущен до завершения получения блокировки, поскольку взаимное исключение не может быть гарантировано.
Пост-ждать
Синхронизация после ожидания - еще одна форма реализации согласованности выпуска. Как показано в коде справа, корректность может быть гарантирована, если пост-операции выполняются только после того, как все обращения к памяти завершены, особенно сохранение в 'a'. Кроме того, операция чтения не должна выполняться до завершения операции ожидания. S2 действует как синхронизация освобождения, а S3 действует как синхронизация получения. Следовательно, S2 необходимо предотвратить предыдущее выполнение после него, а S3 необходимо предотвратить любое последующее выполнение до него. S2 не нужно предотвращать последующее выполнение перед ним. Аналогично, S3 не нужно предотвращать любое предыдущее выполнение после него.
Последовательность отложенного выпуска [4]
Ленивая согласованность выпуска - это дальнейшая оптимизация согласованности выпуска. Предполагается, что поток, выполняющий доступ на получение, не нуждается в значениях, записанных другими потоками, до тех пор, пока доступ на получение не завершится. Следовательно, все поведение когерентности может быть отложено, а время распространения записи может быть изменено.
Пример
Рассмотрим сценарии, описанные на изображении справа. Этот случай показывает, когда распространение записи выполняется в системе с согласованной кэш-памятью на основе модели согласованности выпуска. Перед распространением datumIsReady полностью распространяется переменная датум . Но значение datum не требуется до тех пор, пока не будет получен доступ к синхронизации в P1, и его можно распространить вместе с datumIsReady без ущерба для результата программы.
На втором изображении показано, что происходит при применении согласованности ленивого выпуска. Учитывая этот сценарий, все значения, записанные перед синхронизацией выпуска, задерживаются и распространяются вместе с распространением самого доступа к выпуску. Следовательно, datum и datumIsReady распространяются вместе в точке выпуска.
«TreadMarks» [5] - это актуальное приложение для обеспечения согласованности ленивых релизов.
Улучшение производительности по сравнению с согласованностью выпуска
В некоторых случаях ленивая согласованность выпуска может превзойти согласованность выпуска. Если существует система с небольшой полосой пропускания между процессорами или она сильно страдает от более высоких накладных расходов из-за частого распространения небольшого блока данных по сравнению с нечастым распространением большого блока данных, LRC действительно может повысить производительность.
Представьте, что система использует абстракцию разделяемой памяти на программном уровне, а не реальную аппаратную реализацию. В этой системе распространение записи выполняется со степенью детализации страницы, что делает чрезвычайно затратным распространение всей страницы, когда изменяется только один блок на этой странице. Следовательно, распространение записи откладывается до тех пор, пока не будет достигнута точка синхронизации выпуска, и в это время будет изменена вся страница, а вся страница будет распространена.
Недостаток
LRC требует выполнения массового распространения записи в точке освобождения синхронизации. Распространение такого большого количества операций записи в целом замедлит доступ к выпуску и последующий доступ к получению. Следовательно, это вряд ли может улучшить производительность системы согласования аппаратного кэша.
Согласованность выпуска по сравнению с другими моделями ослабленной согласованности [6]
Слабый порядок ( Слабая последовательность )
Согласованность выпуска требует от программистов большего по сравнению со слабым порядком. Они должны помечать доступ к синхронизации как получение или освобождение, а не только как доступ к синхронизации. Подобно слабому упорядочиванию, согласованность выпуска позволяет компилятору свободно переупорядочивать загрузки и сохранения, за исключением того, что они не могут мигрировать вверх после синхронизации получения и не могут мигрировать вниз после синхронизации выпуска. Однако преимущество в гибкости и производительности согласованности выпуска достигается за счет того, что доступ к синхронизации должен быть правильно идентифицирован и идентифицирован как приобретение и выпуск. В отличие от слабого упорядочения, доступ к синхронизации не может быть легко идентифицирован с помощью одних только кодов операций. Следовательно, на плечах программистов ложится бремя, необходимое для правильной идентификации доступа для получения и освобождения синхронизации. [3]
Согласованность процессора
Для согласованности процессора все процессы видят записи от каждого процессора в том порядке, в котором они были инициированы. Записи с разных процессоров могут не отображаться в одном и том же порядке, за исключением того, что записи в одно и то же место будут отображаться везде в одном и том же порядке. По сравнению с согласованностью процессора, согласованность выпуска является более расслабленной, поскольку она не обеспечивает упорядочение между хранилищами, которое происходит при согласованности процессора. Он не следует интуиции программистов, поскольку относительно менее ограничивает оптимизацию компилятора.
Смотрите также
Рекомендации
- ^ Согласованность памяти и порядок событий в масштабируемых мультипроцессорах с общей памятью Куроша Гарачорлоо, Даниэля Леноски, Джеймса Лаудона, Филиппа Гиббонса, Анупа Гупты и Джона Хеннесси, опубликованные в Протоколах ISCA '90 17-го ежегодного международного симпозиума по компьютерной архитектуре
- ^ Таненбаум, Эндрю (1995). Распределенные операционные системы . Pearson Education. С. 327–330. ISBN 9788177581799.
- ^ а б Солихин, Ян (2015). Основы параллельной многоядерной архитектуры . Чепмен и Холл / CRC Computational Science. С. 315–320. ISBN 9781482211184.
- ^ Последовательность ленивых выпусков для программного обеспечения с распределенной разделяемой памятью Питом Келехером, Аланом Л. Коксом и Вилли Цваенепоэлем, опубликованным в Proceeding ISCA '92 Proceedings 19-го ежегодного международного симпозиума по компьютерной архитектуре
- ^ TreadMarks: распределенная разделяемая память на стандартных рабочих станциях и операционных системах Пита Келехера, Алана Л. Кокса, Сандхья Двааркадаса и Вилли Цваенепола, опубликованные в WTEC'94 Proceedings of the USENIX Winter 1994 Technical Conference on USENIX Winter 1994 Technical Conference
- ^ Каллер, Дэвид; Гупта, Ануп; Сингх, Джасвиндер (1997). Параллельная компьютерная архитектура: аппаратно-программный подход . Морган Кауфманн Паблишерс Инк., Стр. 620–626. ISBN 1558603433.