Рассуждение о переупорядочении операций IORef в параллельных программах

Документы говорят:

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

Что я даже не совсем уверен, как разобрать. Эдвард Ян говорит

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

Так что... это не сломает весь хаскелл; не очень полезно Обсуждение, из которого возник пример модели памяти, также оставило меня с вопросами (даже Саймон Марлоу казался немного удивленным).

Вещи, которые кажутся мне понятными из документации

  1. в потоке atomicModifyIORef "никогда не наблюдалось, чтобы это происходило перед какими-либо более ранними операциями IORef или после каких-либо более поздних операций IORef", т.е. мы получаем частичное упорядочение: stuff над атомарным mod -> atomic mod -> stuff после. Хотя формулировка "никогда не наблюдается" здесь наводит на мысль о жутком поведении, которого я не ожидал.

  2. readIORef x может быть перемещен раньше writeIORef yпо крайней мере, когда нет никаких зависимостей данных

  3. Логически я не вижу, как что-то вроде readIORef x >>= writeIORef y может быть переупорядочен

Что мне не понятно

  • Будет newIORef False >>= \v-> writeIORef v True >> readIORef v всегда возвращайся True?

  • в maybePrint случай (из документов IORef) будет readIORef myRef (наряду с возможно seq или что-то) раньше readIORef yourRef заставили барьер для переупорядочения?

Какая у меня должна быть простая ментальная модель? Это что-то вроде:

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

...? Если нет, то в чем исправленная версия выше?

Если ваш ответ "не используйте IORef в параллельном коде; использование TVar"Пожалуйста, убедите меня с конкретными фактами и конкретными примерами того, о чем вы не можете спорить IORef,

Источник

3 ответа

Решение

Я не знаю параллелизма в Haskell, но кое-что знаю о моделях памяти.

Процессоры могут переупорядочивать инструкции так, как им нравится: нагрузки могут идти впереди нагрузок, нагрузки могут идти впереди магазинов, загрузки зависимых вещей могут идти впереди нагрузок вещей, от которых они зависят (a[i] может сначала загрузить значение из массива, тогда ссылка на массив a!) может быть переупорядочена друг с другом. Вы просто не можете указать на это пальцем и сказать: "эти две вещи определенно появляются в определенном порядке, потому что нет способа их переупорядочить". Но для работы параллельных алгоритмов им необходимо наблюдать за состоянием других потоков. Здесь важно, чтобы состояние потока выполнялось в определенном порядке. Это достигается путем размещения барьеров между инструкциями, которые гарантируют, что порядок команд будет одинаковым для всех процессоров.

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

Thread 1: x=1

Thread 2: y=1

Thread 3: r1=x;
          r2=y;

Thread 4: r4=y;
          r3=x;

Если все эти операции являются заказанными грузами и заказанными магазинами, то вы можете сделать вывод (1,0,0,1)=(r1,r2,r3,r4) это невозможно. Действительно, упорядоченные хранилища в потоках 1 и 2 должны появляться в некотором порядке для всех потоков, и r1=1,r2=0 свидетельствует о том, что y=1 выполняется после x=1. В свою очередь, это означает, что поток 4 никогда не сможет наблюдать r4=1, не наблюдая r3=1 (который выполняется после r4=1) (если упорядоченные хранилища выполняются таким образом, наблюдение y==1 подразумевает x==1).

Кроме того, если загрузки и хранилища не были упорядочены, процессорам, как правило, разрешалось наблюдать за назначениями, появляющимися даже в разных порядках: один мог видеть, что x = 1 появляется перед y=1, другой мог видеть, что y=1 появлялся перед x=1, поэтому допускается любая комбинация значений r1,r2,r3,r4.

Это достаточно реализовано так:

заказанный груз:

load x
load-load  -- barriers stopping other loads to go ahead of preceding loads
load-store -- no one is allowed to go ahead of ordered load

заказанный магазин:

load-store
store-store -- ordered store must appear after all stores
            -- preceding it in program order - serialize all stores
            -- (flush write buffers)
store x,v
store-load -- ordered loads must not go ahead of ordered store
           -- preceding them in program order

Из этих двух я вижу, что IORef реализует заказанный магазин (atomicWriteIORef), но я не вижу заказанного груза (atomicReadIORef), без которого вы не можете рассуждать о проблеме IRIW выше. Это не проблема, если вашей целевой платформой является x86, потому что все загрузки будут выполняться в программном порядке на этой платформе, и хранилища никогда не будут идти впереди нагрузок (фактически все нагрузки являются упорядоченными нагрузками).

Атомное обновление (atomicModifyIORef) мне кажется реализация так называемого цикла CAS (цикл сравнения и установки, который не останавливается, пока значение не будет атомарно установлено в b, если его значение равно a). Вы можете видеть атомарную операцию модификации как объединение упорядоченной загрузки и упорядоченного хранилища со всеми этими барьерами и выполненными атомарно - ни одному процессору не разрешается вставлять инструкцию модификации между загрузкой и сохранением CAS.

Кроме того, writeIORef дешевле, чем atomicWriteIORef, поэтому вы хотите использовать writeIORef настолько, насколько позволяет протокол обмена данными между потоками. В то время как writeIORef x vx >> writeIORef y vy >> atomicWriteIORef z vz >> readIORef t не гарантирует порядок, в котором writeIORefs появляются в других потоках относительно друг друга, есть гарантия, что они оба появятся раньше atomicWriteIORef - Итак, увидев z==vz, вы можете сделать вывод, что в этот момент x==vx и y==vy, и вы можете сделать вывод, что IORef t был загружен после сохранения в x, y, z других потоков. Этот последний пункт требует, чтобы readIORef была упорядоченной загрузкой, которая, насколько я могу судить, не предусмотрена, но она будет работать как упорядоченная загрузка на x86.

Обычно вы не используете конкретные значения x, y, z при рассуждении об алгоритме. Вместо этого должны сохраняться некоторые зависящие от алгоритма инварианты о назначенных значениях, которые могут быть проверены - например, как в случае IRIW, вы можете гарантировать, что поток 4 никогда не увидит (0,1)=(r3,r4), если Тема 3 видит (1,0)=(r1,r2)и Thread 3 может воспользоваться этим: это означает, что что-то взаимно исключается без получения какого-либо мьютекса или блокировки.

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

Предположим, что z покажет либо x, пока y не будет вычислено, либо y, если x также было вычислено. Не спрашивайте почему, это не очень легко увидеть вне контекста - это своего рода очередь - просто наслаждайтесь тем, какие рассуждения возможны.

Thread 1: x=1;
          if (z==0) compareAndSet(z, 0, y == 0? x: y);

Thread 2: y=2;
          if (x != 0) while ((tmp=z) != y && !compareAndSet(z, tmp, y));

Итак, два потока устанавливают x и y, а затем устанавливают z на x или y, в зависимости от того, были ли вычислены y или x. Предположим, изначально все равны 0. Переводим в грузы и магазины:

Thread 1: store x,1
          load z
          if ==0 then
            load y
            if == 0 then load x -- if loaded y is still 0, load x into tmp
            else load y -- otherwise, load y into tmp
            CAS z, 0, tmp -- CAS whatever was loaded in the previous if-statement
                          -- the CAS may fail, but see explanation

Thread 2: store y,2
          load x
          if !=0 then
          loop: load z -- into tmp
                load y
                if !=tmp then -- compare loaded y to tmp
                  CAS z, tmp, y  -- attempt to CAS z: if it is still tmp, set to y
                  if ! then goto loop -- if CAS did not succeed, go to loop

Если нить 1 load z не заказанный груз, тогда будет разрешено идти впереди заказанного магазина (store x). Это означает, что куда бы z не загружался (регистр, строка кэша, стек,...), значение является таким, которое существовало до того, как значение x может быть видимым. Глядя на это значение бесполезно - вы не можете судить, где находится поток 2. По той же причине у вас должна быть гарантия, что буферы записи были сброшены до load z выполняется - в противном случае оно все равно будет отображаться как загрузка значения, существовавшего до того, как поток 2 сможет увидеть значение x. Это важно, как станет ясно ниже.

Если нить 2 load x или же load z не заказаны грузы, они могут идти впереди store yи будет наблюдать значения, которые были записаны до того, как y станет видимым для других потоков.

Тем не менее, обратите внимание, что, если загрузки и хранилища упорядочены, потоки могут договориться о том, кто должен устанавливать значение z, не опуская z. Например, если поток 2 соблюдает x==0, есть гарантия, что поток 1 обязательно выполнит x = 1 позже и увидит z==0 после этого - так что поток 2 может выйти, не пытаясь установить z.

Если поток 1 соблюдает z==0, то он должен попытаться установить для z значение x или y. Итак, сначала он проверит, был ли y уже установлен. Если он не был установлен, он будет установлен в будущем, поэтому попытайтесь установить x - CAS может потерпеть неудачу, но только если поток 2 одновременно установит z на y, так что нет необходимости повторять попытку. Точно так же нет необходимости повторять попытку, если Поток 1 заметил, что y был установлен: если CAS терпит неудачу, то он был установлен Потоком 2 на y. Таким образом, мы можем видеть, что Поток 1 устанавливает z в x или y в соответствии с требованием, и не слишком много конкурирует с z.

С другой стороны, поток 2 может проверить, был ли x уже вычислен. Если нет, то задачей Thread 1 будет установка z. Если поток 1 вычислил x, тогда нужно установить z в y. Здесь нам нужен цикл CAS, потому что один CAS может потерпеть неудачу, если Поток 1 пытается установить z равным x или y одновременно.

Важным выводом здесь является то, что, если "несвязанные" загрузки и хранилища не сериализуются (включая буферы очистки записи), такие рассуждения невозможны. Однако после упорядочения загрузок и хранилищ оба потока могут определить путь каждого из них _will_take_in_the_future и таким образом устранить конфликт в половине случаев. Большую часть времени x и y будут вычисляться в существенно различающиеся моменты времени, поэтому, если y вычисляется до x, вполне вероятно, что поток 2 вообще не будет касаться z. (Как правило, "прикосновение к z" также может означать "пробуждение потока, ожидающего cond_var z", так что это не только вопрос загрузки чего-либо из памяти)

Источник
  1. в потоке atomicModifyIORef "никогда не наблюдается перед любыми более ранними операциями IORef или после любых последующих операций IORef", то есть мы получаем частичное упорядочение: stuff над atomic mod -> atomic mod -> stuff после. Хотя формулировка "никогда не наблюдается" здесь наводит на мысль о жутком поведении, которого я не ожидал.

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

  1. ReadIORef x может быть перемещен перед writeIORef y, по крайней мере, когда нет никаких зависимостей данных

Правда

  1. Логически я не понимаю, как что-то вроде readIORef x >>= writeIORef y можно переупорядочить

Исправьте, поскольку эта последовательность имеет зависимость от данных. Значение для записи зависит от значения, возвращенного при первом чтении.

По другим вопросам: newIORef False >>= \v-> writeIORef v True >> readIORef v всегда вернется True (у других потоков нет возможности получить доступ к ссылке здесь).

в myprint Например, вы можете сделать очень мало для обеспечения надежной работы в условиях новых оптимизаций, добавленных в будущие GHC и для различных архитектур ЦП. Если вы напишите:

writeIORef myRef True
x <- readIORef myRef
yourVal <- x `seq` readIORef yourRef

Несмотря на то, что GHC 7.6.3 выдает правильный cmm (и, вероятно, asm, хотя я не проверял), ничто не мешает процессору с расслабленной моделью памяти перемещать readIORef yourRef до того, как все myref/seq вещи. Единственный 100% надежный способ предотвратить это - использовать забор памяти, который GHC не предоставляет. (В блоге Эдварда рассказывается о некоторых других вещах, которые вы можете сделать сейчас, а также о том, почему вы не можете на них полагаться).

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

Изменить: на уровне cmm, фрагмент кода выше выглядит следующим образом (упрощенный, псевдокод):

[StackPtr+offset] := True
x := [StackPtr+offset]
if (notEvaluated x) (evaluate x)
yourVal := [StackPtr+offset2]

Таким образом, есть пара вещей, которые могут произойти. GHC в его нынешнем виде вряд ли сможет сдвинуть последнюю строчку раньше, но я думаю, что он мог бы, если бы это казалось более оптимальным. Меня больше беспокоит то, что, если вы компилируете через LLVM, оптимизатор LLVM может заменить вторую строку только что записанным значением, а затем третья строка может быть константно свернута из существования, что повысит вероятность того, что чтение может быть перенесено раньше. И независимо от того, что делает GHC, большинство моделей памяти ЦП позволяют самому ЦП перемещать чтение ранее без барьера памяти.

Источник

http://en.wikipedia.org/wiki/Memory_ordering для неатомарных параллельных операций чтения и записи. (в основном, когда вы не используете атомарность, просто посмотрите на модель упорядочения памяти для вашего целевого процессора)

В настоящее время ghc может рассматриваться как неупорядоченный процесс чтения и записи для неатомарных (и обязательных) загрузок и хранилищ. Тем не менее, GHC Haskell в настоящее время не определяет какую-либо параллельную модель памяти, поэтому эти неатомарные операции будут иметь семантику упорядочения базовой модели CPU, как я ссылаюсь выше.

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

то есть: единственная семантическая модель, которую вы можете иметь прямо сейчас, - это "способ ее реализации"

пристрелите мне письмо! Я работаю над исправлением атомики для 7.10, давайте попробуем подготовить немного семантики!

Изменить: некоторые люди, которые понимают эту проблему лучше, чем я, включились в ветку ghc-users здесь http://www.haskell.org/pipermail/glasgow-haskell-users/2013-December/024473.html December/024473.html. Предположим, что я не прав как в этом комментарии, так и во всем, что я сказал в ветке ghc-users:)

Источник
Другие вопросы по тегам