Согласованность выпуска

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

Введение

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

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

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

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

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

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

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

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

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

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

Реализации

Снятие блокировки

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

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

После ожидания

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

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

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

Пример

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

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

«ТредМаркс» ^[5] это фактическое применение согласованности отложенного выпуска.

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

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

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

Недостаток

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

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

Слабая упорядоченность ( Слабая последовательность )

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

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

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

См. также

Ссылки

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

[1] Согласованность памяти и порядок событий в масштабируемых мультипроцессорах с общей памятью Куроша Гарачорлоо, Дэниела Леноски, Джеймса Лаудона, Филиппа Гиббонса, Анупа Гупты и Джона Хеннесси, опубликованные в ISCA '90 Труды 17-го ежегодного международного симпозиума по компьютерной архитектуре

[2] Таненбаум, Эндрю (1995). Распределенные операционные системы . Пирсон Образование. стр. 327–330. ISBN 9788177581799 .

[:0-3] Jump up to: ^а ^б Солихин, Ян (2015). Основы параллельной многоядерной архитектуры . Чепмен и Холл/CRC Вычислительная наука. стр. 315–320. ISBN 9781482211184 .

[4] Ленивая согласованность выпусков программного обеспечения с распределенной общей памятью Пита Келехера, Алана Л. Кокса и Вилли Звенепола, опубликованная в Proceeding ISCA '92 Proceedings of the 19th Annual International Symposium on Computer Architecture.

[5] TreadMarks: распределенная разделяемая память на стандартных рабочих станциях и операционных системах Пита Келехера, Алана Л. Кокса, Сандхья Дваркадас и Вилли Зваенепола, опубликованная в WTEC'94 Proceedings of the USENIX Winter 1994 Техническая конференция на USENIX Winter 1994 Техническая конференция

[6] Каллер, Дэвид; Гупта, Ануп; Сингх, Джасвиндер (1997). Параллельная компьютерная архитектура: аппаратно-программный подход . Morgan Kaufmann Publishers Inc., стр. 620–626. ISBN 1558603433 .

[1]

[2]

[3]

[4]

[5]

[6]