Здравствуйте, eao197, Вы писали:

E>В конце года не просто найти время на реализацию подобного теста, тем более, что готовой очереди на основе CAS

Что такое CAS? Мне вспоминается только code access security. Имеется в виду очередь на спинлоках?

Здравствуйте, remark, Вы писали:

R>Здравствуйте, thesz, Вы писали:

G>>>>Что, до такой степени "обычная", что в определении этой переменной, которую вы собрались читать обычными read даже не надо писать volatile, и компилятор ее спокойно применяет к ней регистровую оптимизацию, как в моем случае? .
R>>>Ох, ну не надо только в сторону уводить. volatile, не volatile там в С. Считай, что это вообще на асме.

T>>Если нужен volatile, то на чём ни пиши, всё равно в регистры не уложишь.
T>>Поэтому реплику про ассемблер считаю неорганизованной и отметаю.


R>Стоп-стоп-стоп. Что Вы имеете в виду с Gaperton'ом? В чём тезис и при чём тут всплыл volatile и регистровые оптимизации? Вы хотите сказать, что это вносит какие-то серьёзные издержки в работу алгоритма? Т.е. я правильно понимаю, что Вы хотите, что бы примитив синхронизации работал только с регистрами? Или что?

R>Я имею в виду, что суть в том, что там, на машинном уровне, стоит обычная инструкция загрузки. Как она там появилась — абсолютно не важно в данном контектсе — хоть volatile в С, хоть напрямую на асме её написали (на асме написали инструкцию загрузки! а НЕ заставили примитив синхронизации работать только с регистрами!).
R>Для любого примитива синхрониазации абсолютно важно подавить оптимизации/переупорядочивания компилятора. Очередь это тоже делает. К счастью, это НЕ вносит НИКАКОГО существенного оверхеда в ран-тайм.



T>>Про передачу сообщений.

T>>Её можно сделать сколь угодно мало требовательной путём группировки сообщений.

T>>Типа, пишется в одну очередь, читается из другой. По переполнению/опустошению очереди сливаются, перед этим создаётся новый объект для изменяемой очереди.

T>>Чтение из текущей рабочей очереди не имеет проблем с разделением ресурсов. Запись в текущую рабочую тоже таких проблем не имеет большую часть времени.


R>Теоретически — да. На практике это не работает.
R>Группировка будет работать только в вырожденном случае, когда агнет посылает сообщения только одному другому агенту, и всё это, понятно, в одном потоке. Когда произвольное множество агентов посылает сообщения произвольному множеству агентов + это происходит во множестве потоков + надо гарантировать ФИФО (это тут очень важно — это рушит всю идею группирования) — ничего не получится, придётся честно каждое сообщение посылать. Если не согласен — обрисуй схему, которая будет работать для множества отправителей, множества получаетелей, множества потоков.

Зачем надо гарантировать ФИФО именно в самой очереди?

Для синхронизации это не важно, будет ли ФИФО в очереди, или нет.

Я приводил ссылку на систему WaveScalar, там очень интересная система синхронизации обращений в память, построенная для недетерминированной по своей сути системы потока данных.

Так и здесь — надо всё писать из расчёта общей недетерминированности процесса.

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

Смотри. Ты смотришь на агентов, как на совершенно независимые сущности, способные послать кому угодно что угодно.

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

Такая иерархия очень важна, это, буквально, единственный способ сделать нормальный межпроцесс(ор)ный обмен. Топология называется fat tree и она эффективней гиперкуба.

В результате получится, что у каждого узла-процессора будет не более трех источников входящих и исходящих данных. (в общем случае, конечно, коэффициент-репликации-нижних+коэффициент-репликации-верхних*2). Поскольку количество приемных очередей конечно, то производители (ретрансляторы) сообщений сталкиваться не будут.

Поскольку не будет никакого "отсылает то одному, то другому" больше, чем заранее заданное число этих самых одних и других.

При этом самих агентов могут быть сотни тысяч, а процессоров — всего десятки.

R>Плюс кэш сообщений уже надо хранить не один на рабочий поток, а один на каждого агента (которых могут быть сотни тысяч), а потом как-то эти кэши опрашивать, мы ж не можем кэшировать вечно. Плюс необходима поддержка языка, типа как для GC — должны иметь возможность гарантированно периодически дергать функцию сброса кэша из рабочего потока (или мы будет дергать сброс кэша из другого потока, и защищать каждое обращение к этой очереди мьютексом?).

Не очень понятно.

R>Вобщем, на практике это сыпется как карточный домик, вопросов больше, чем ответов.

Я же делал такие системы.

Вопросов много, но и ответы-решения очень простые.

R>Про очередь вообще не понял, чего мы с такой схемой добились. У нас была multi-producer/single-consumer очередь. Потребитель тут и так работает без конфликтов, т.к. он один — взять хотя бы ту же two-lock queue. Производители гарантированно сталкиваются, и то, что разбили на 2 очереди ни как не повлияет на сталкновения — всё производители всё равно будут работать с одной очередью.

Надеюсь, иерархия узлов-процессоров кое-что развеяла.

Здравствуйте, AndrewVK, Вы писали:

E>>В конце года не просто найти время на реализацию подобного теста, тем более, что готовой очереди на основе CAS

AVK>Что такое CAS?

Compare And Swap.

AVK>Имеется в виду очередь на спинлоках?

Я хотел использовать вот эту, но она написана с использованием atomic из состава C++0x, поэтому нужно будет ее адаптировать к C++03, а на это пока нет времени. К тому же она использует динамическую память, а это явный проигрыш, поэтому ее еще нужно адаптировать к сохранению указателей по значению.

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

Здравствуйте, thesz, Вы писали:

R>>Теоретически — да. На практике это не работает.
R>>Группировка будет работать только в вырожденном случае, когда агнет посылает сообщения только одному другому агенту, и всё это, понятно, в одном потоке. Когда произвольное множество агентов посылает сообщения произвольному множеству агентов + это происходит во множестве потоков + надо гарантировать ФИФО (это тут очень важно — это рушит всю идею группирования) — ничего не получится, придётся честно каждое сообщение посылать. Если не согласен — обрисуй схему, которая будет работать для множества отправителей, множества получаетелей, множества потоков.

T>Зачем надо гарантировать ФИФО именно в самой очереди?

T>Для синхронизации это не важно, будет ли ФИФО в очереди, или нет.

Потому что никто даже и не взглянет на такую реализацию актёров. Погляди на любые реализации модели актёров — они все гарантируют ФИФО, и это не спроста.

Или ты имешь в виду, что ФИФО будет делаться на уровень выше? Векторные часы там? Подожди, ты о железе опять говоришь? Для софта это не будет работать — проще сразу класть в одну очередь. Если о железе — ну для железа видимо подходит — поиск минимального времени можно сделать за O(1) и т.д. Но железо меня не сильно интересует, я ж не с программатором сижу.



T>Я приводил ссылку на систему WaveScalar, там очень интересная система синхронизации обращений в память, построенная для недетерминированной по своей сути системы потока данных.

Опять железо? В железе можно много чего сделать — аппаратную поддержку ассоциативных контейнеров, HTM, поддержку сборки мусораи т.д. Я сижу за x86, как я думаю 99% здесь, и меня интересует как я могу здесь и сейчас использовать модель актёров и передачуц сообщений.



T>Так и здесь — надо всё писать из расчёта общей недетерминированности процесса.

Какие есть прецеденты реализации модели актёров без ФИФО?


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

T>Смотри. Ты смотришь на агентов, как на совершенно независимые сущности, способные послать кому угодно что угодно.

T>В действительности же агенты будут получены из текста последовательной программы путём её преобразования (автоматического ли, ручного ли). Это наложит на их посылки определённый порядок. Далее мы построим иерархию узлов-процессоров (каждый нижний узел ответственен за выполнение нескольких агентов, узлы уровнем выше нижнего ответственны за группировку и передачу сообщений узлам выше и ниже).

T>Такая иерархия очень важна, это, буквально, единственный способ сделать нормальный межпроцесс(ор)ный обмен. Топология называется fat tree и она эффективней гиперкуба.

T>В результате получится, что у каждого узла-процессора будет не более трех источников входящих и исходящих данных. (в общем случае, конечно, коэффициент-репликации-нижних+коэффициент-репликации-верхних*2). Поскольку количество приемных очередей конечно, то производители (ретрансляторы) сообщений сталкиваться не будут.

T>Поскольку не будет никакого "отсылает то одному, то другому" больше, чем заранее заданное число этих самых одних и других.

T>При этом самих агентов могут быть сотни тысяч, а процессоров — всего десятки.

R>>Плюс кэш сообщений уже надо хранить не один на рабочий поток, а один на каждого агента (которых могут быть сотни тысяч), а потом как-то эти кэши опрашивать, мы ж не можем кэшировать вечно. Плюс необходима поддержка языка, типа как для GC — должны иметь возможность гарантированно периодически дергать функцию сброса кэша из рабочего потока (или мы будет дергать сброс кэша из другого потока, и защищать каждое обращение к этой очереди мьютексом?).

T>Не очень понятно.

R>>Вобщем, на практике это сыпется как карточный домик, вопросов больше, чем ответов.

T>Я же делал такие системы.

T>Вопросов много, но и ответы-решения очень простые.


Только один вопрос: fat tree — это ты про аппаратную реализацию, правильно? Если да, то тогда вопросов больше нет.
А нет, вот ещё один: как делать динамический лоад-балансинг агентов между процессорами?

Здравствуйте, remark, Вы писали:

R>Только один вопрос: fat tree — это ты про аппаратную реализацию, правильно? Если да, то тогда вопросов больше нет.
R>А нет, вот ещё один: как делать динамический лоад-балансинг агентов между процессорами?

Всё ясно:

...invented the fat tree interconnection network, a hardware-universal interconnection network...

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

Мне у Charles Eric Leiserson больше по душе Cilk, потому что я могу его сейчас скачать и запустить на своём компьютере. И чем они занимаются в Cilk Arts — Hyperobejcts там всякие и верификация параллельных программ.

Здравствуйте, Gaperton, Вы писали:

R>> _ReadWriteBarrier() — это барьер КОМПИЛЯТОРА. Подавляет переупорядочивания компилятором. Всё. 0 тактов оверхеда в ран-тайм.

G>То есть, ты хочешь сказать, что эта хрень не дает компилятору переупорядочивать инструкции. И типа, совсем вся работа делается в блокировке писателя. Ну допустим.

Ну типа того. Т.е. то, что ты говорил до этого — неправда.

G>Во-первых, структура у тебя все-таки volatile, и регистровые оптимизации запрещены.

Да, это ещё один тривиальный факт. Ты что-то ещё хочешь этим сказать?

Здравствуйте, Gaperton, Вы писали:

G>На самом деле, в реальном сравнении мутабельного словаря в данной задаче на разделяемой памяти, и иммутабельного на сообщениях, это мало что дает.

G>Во-вторых, пока ты меняешь структуру, все читатели стоят на блокировке. Что, в случае высоколатентной памяти, обойдется дорого.

G>В случае с дизайном на сообщениях нет ни того, ни другого. Читаешь ты из очереди один раз, переписывая сообщение в non-volatile память, и используя переменную потом в цикле, что разрешает регистровые оптимизации. Далее — во время модификации структуры в моем случае все спокойно работают на предыдущей ее версии, и не блокируются вовсе — единственная задержка будет на CAS, и очень редко — в момент получения пакета.

Что ж ты всё время так узко и так фанатично смотришь на вещи... Лучше, хуже, серебряные пули...
Моя позиция, что нет серебряных пуль, есть просто разные техники с разными наборами "плюсов" и "минусов". Задача профессионального инженера — грамотно выбрать среди альтернатив, а не слепо привязаться к одному подходу.
Если решение с мьютексом подходит хуже, то я просто не будут его использовать (оно, кстати, тут и появилось по другому поводу). Если оно подходит лучше, то будут использовать его.
На его минусы ты уже указал. Основной — длительное блокирование читателей. Но ключевой момент то, что на ряду с минусами у него есть и плюсы. Основные плюсы (которые, кстати, непосредственно следуют из минусов):
1. Нет необходимости копировать структуру или её части и хранить какие-либо предыдущие версии. Т.е. либо создаём новые части, вставляем их в структуру, и старые сразу освобождаем; либо непосредственно переиспользуем старые части под новые. В некоторых ситуациях это может быть showstopper'ом для подхода на иммутабельных структурах (если размер данных большой и/или изменения часты и/или каждый узел хранит много данных).
2. С мьютексом можно использовать структуру данных любой сложности, а не только тот очень и очень ограниченный набор структур, которые можно делать иммутабельными. Например, под такой мьютекс я могу положить cache-conscious hash-map. И в то время, как ты будешь экономить при редких изменениях со своим деревом, я буду экономить при каждом частом чтении. Ты, кстати, не можешь сделать своё дерево cache-conscious, т.е. будешь заниматься проверкой скорости работы основной памяти. Ну и не говоря уже обо всём разнообразии структур данных, т.е. я могу просто открыть справочник, выбрать структуру и положить её под мьютекс. Ты же будешь вынужден думать как прикрутить дерево к задаче.

Именно из таких соображений я и разрабатываю *различные* алгоритмы. Кстати, среди моих алгоритмов ты можешь видеть и алгоритмы для поддержки именно неизменяемых структур данных:
http://groups.google.ru/group/lock-free

Здравствуйте, remark, Вы писали:

R>Здравствуйте, thesz, Вы писали:

R>>>Теоретически — да. На практике это не работает.
R>>>Группировка будет работать только в вырожденном случае, когда агнет посылает сообщения только одному другому агенту, и всё это, понятно, в одном потоке. Когда произвольное множество агентов посылает сообщения произвольному множеству агентов + это происходит во множестве потоков + надо гарантировать ФИФО (это тут очень важно — это рушит всю идею группирования) — ничего не получится, придётся честно каждое сообщение посылать. Если не согласен — обрисуй схему, которая будет работать для множества отправителей, множества получаетелей, множества потоков.

T>>Зачем надо гарантировать ФИФО именно в самой очереди?

T>>Для синхронизации это не важно, будет ли ФИФО в очереди, или нет.

R>Потому что никто даже и не взглянет на такую реализацию актёров. Погляди на любые реализации модели актёров — они все гарантируют ФИФО, и это не спроста.

R>Или ты имешь в виду, что ФИФО будет делаться на уровень выше? Векторные часы там? Подожди, ты о железе опять говоришь? Для софта это не будет работать — проще сразу класть в одну очередь. Если о железе — ну для железа видимо подходит — поиск минимального времени можно сделать за O(1) и т.д. Но железо меня не сильно интересует, я ж не с программатором сижу.

Нет, я не про железо.

T>>Я приводил ссылку на систему WaveScalar, там очень интересная система синхронизации обращений в память, построенная для недетерминированной по своей сути системы потока данных.

R>Опять железо? В железе можно много чего сделать — аппаратную поддержку ассоциативных контейнеров, HTM, поддержку сборки мусораи т.д. Я сижу за x86, как я думаю 99% здесь, и меня интересует как я могу здесь и сейчас использовать модель актёров и передачуц сообщений.

Так же, как и любую другую модель.

WaveScalar недетерминирован. Он может выполнять "задачи из будущего". Главное — это синхронизация в ключевых местах. Синхронизация редкая, надо сказать.

T>>Так и здесь — надо всё писать из расчёта общей недетерминированности процесса.
R>Какие есть прецеденты реализации модели актёров без ФИФО?

Да иди ты смотреть на WaveScalar. Хотя бы.

T>>Вопросов много, но и ответы-решения очень простые.

R>Только один вопрос: fat tree — это ты про аппаратную реализацию, правильно? Если да, то тогда вопросов больше нет.

Все, что делается в железе, может быть сделано и программно.

R>А нет, вот ещё один: как делать динамический лоад-балансинг агентов между процессорами?

Вероятностно.

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

R>>Только один вопрос: fat tree — это ты про аппаратную реализацию, правильно? Если да, то тогда вопросов больше нет.
R>>А нет, вот ещё один: как делать динамический лоад-балансинг агентов между процессорами?

R>Всё ясно:
R>

R>...invented the fat tree interconnection network, a hardware-universal interconnection network...

R>Понятно, что со специализированной аппаратной поддержкой чего угодно можно уехать далеко, и доказать потом превосходство этого над тем, что не имеет аппаратной поддержки.
R>Можно сказать: представь вся моя программа будет реализована в железе и будет занимать в программе одну инструкцию. Представь как она будет всё рвать!

Да ни-хе-ра.

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

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

Здравствуйте, Gaperton, Вы писали:

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

G>Пытаешься спасти свою репутацию? Угу, искушенные люди конечно
сразу тебе поверили про ускорение в 300 раз . Которого в данной
задаче, естественно, не будет,

А я на неискушенных людей и не рассчитываю, поэтому и не заворачиваю
всякий бред в умных вид. Для неискушенных людей — это фразы типа
"здесь нужен lwsync", повторённая 3 раза, или типа "Которого в данной
задаче, естественно, не будет" (ну "естественно", раз уж так
Gaperton сказал).
А люди из SUN, IBM, Intel, которые десятки лет занимаются
синхронизацией в ядрах ОС, виртуальных машинах, библиотеках поддержки,
не брезгают верить, слушать, просить лицензии на мои работы.


G>особенно если построить очередь на технике, подобной твоему mutex.

Опять трендёж. Ну давай, попробуй, построй. Хотя бы обрисуй алгоритм.
Это не возможно. В синхронизации всё не так просто, нельзя просто
взять 2 вещи и соединить. Так же как ты не можешь просто вот так взять
и применить технику иммутабельных/персистентых структур данных,
например, к вектору и сохранить при этом его свойства и малое число копирований.


G>Ты вообще плохо отдаешь себе отчет, с чем споришь.

Да, нет, я прекрасно понимаю с чем я спорю — с Gaperton'ом



R>> "Обкакался, так будь мужиком, блин, и имей смелость это признать"
(с) Gaperton

G>Как тебе однако хочется, чтобы я обкакался. Вот это называется обкакался.
G>

G>А уж по поводу ситуации, где нам надо только считать данные — обмен
сообщениями (на любых очередях), так и останется медленнее на
несколько порядков.

Я за любое своё утверждение могу ответить и обосновать. Потому что я
на ходу не выдумываю, а чётко знаю о чём говорю. А если не знаю, то
молчу.


G>А то, что я не знаю, какой там нахрен барьер _ReadWriteBarrier(),
что послужило поводом твоей бурной радости

Ой, а уж тебя-то сколько радости вызвало, когда ты _ReadWriteBarrier()
подметил в коде. Звон услышал и понеслась шашка сверкать


G> — так всего знать невозможно

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


G> (ты, к примеру, не знаешь про lwsync), да и в контексте общего
спора, в котором глупые тезисы выдвигаешь ты, а не я, это совершенно
не принципиально. Касательно того, что atomic_read, на котором eao
собирался решать эту задачу, медленнее обычного — это правда и
остается правдой, в данном случае нужен честный барьер в получателе
чтобы все работало.

Это хорошо, что ты вспомнил про lwsync. Ну что мы тут сдвинемся с
мёртвой точки? Твою фразу, что тут нужен lwsync, а на x86 надо ещё
какую store-load последовательность упорядочить уже все слышали 3
раза. Я же третий раз повторяю повторяю тебе свои простые и ясные
вопросы: в каком именно месте и для упорядочивания каких обращений
нужен lwsync? какую store-load последовательность требуется
упорядочить на стороне читателя?
Пока же это выглядит, что ты опять слышал какой-то звон, но не знаешь где он...

Здравствуйте, eao197, Вы писали:

E>Здравствуйте, Gaperton, Вы писали:

G>>Примерно так бы все и было. С незначительными нюансами туда-сюда.

E>Феерический рассказ о том, как Gaperton поспорил сам с собой и блестяще выиграл спор у самого себя.

Присоединяюсь к поздравлениям! Молодец, Gaperton, ты полностью себя порвал!

Здравствуйте, thesz, Вы писали:

R>>>Только один вопрос: fat tree — это ты про аппаратную реализацию, правильно? Если да, то тогда вопросов больше нет.
R>>>А нет, вот ещё один: как делать динамический лоад-балансинг агентов между процессорами?

R>>Всё ясно:
R>>

R>>...invented the fat tree interconnection network, a hardware-universal interconnection network...

R>>Понятно, что со специализированной аппаратной поддержкой чего угодно можно уехать далеко, и доказать потом превосходство этого над тем, что не имеет аппаратной поддержки.
R>>Можно сказать: представь вся моя программа будет реализована в железе и будет занимать в программе одну инструкцию. Представь как она будет всё рвать!

T>Да ни-хе-ра.

T>Ты эту самую иерархию можешь сделать и программой. В случае программного решения тебе этого не избежать. Ни иерархии, ни её реализации.

Сделать-то, конечно, можно. Только смысл? Ты ж пытаешься скорость оптимизировать, а если ты своё решение не можешь сэмулировать быстро и с низкой латентностью, то вся твоя идея рассыпается.

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

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

Здравствуйте, thesz, Вы писали:

R>>Или ты имешь в виду, что ФИФО будет делаться на уровень выше? Векторные часы там? Подожди, ты о железе опять говоришь? Для софта это не будет работать — проще сразу класть в одну очередь. Если о железе — ну для железа видимо подходит — поиск минимального времени можно сделать за O(1) и т.д. Но железо меня не сильно интересует, я ж не с программатором сижу.

T>Нет, я не про железо.

Пока не похоже. Пока что ты обрисовал решение на *логическом* уровне. Попробуй обрисовать его *эффективную* реализацию на *физическом* уровне в софте для общего случая. Ты увидишь, что это сделать нельзя. То, что ты говоришь — это решение, но это решение либо для железа (ты ж оттуда эту идею взял?), либо для частных случаев в софте. Но не для общего случая в софте. Ты не можешь с таким решением выходить и громко заявлять, что ты решил какую-то общую проблему, и что "Её можно сделать сколь угодно мало требовательной путём группировки сообщений.".
Как ты будешь справляться со значительной внесённой латентностью? Кто будет рулить этими промежуточными узлами? Отдельные потоки, рабочие потоки этим нельзя нагружать, т.к. они могут обрабатывать сообщения долго. Отдельные процессоры выделять под эти потоки не целесообразно. Если они будут разделять процессоры с другими потоками, значит они могут шедулиться для выполнения через 40 мс и больше. Ну вот проходит такое сообщение через эту сеть и получаем внесённую латентность 200 мс.
Такой схемой ты порождаешь массу дополнительно трафика по протоколу когерентности. В традиционной схеме у нас сообщение сразу качует от кэша-источника в кэш-получателя. С твоей схемой оно покачает по N кэшей. Это чудовищный оверхед, проще сразу сделать одну атомарную RMW операцию и отправить сообщение получателю. Как ты предлагаешь это нивелировать?
Неупорядоченные сообщения это, может, и кошерно. Но факт в том, что никто такую систему использовать не будет. Если кто-нибудь придёт к пользователям Erlang, Scala Actors, Concurrency and Coordination Runtime и др. и скажет, что давайте ка мы у вас уберём ФИФО, т.к. так более кошерно, то его сразу пинками погонят. Правильно, а зачем им это надо?
Динамический лоад-балансинг как будешь делать? Пока что ты увильнул статическим. Но это не катит для систем общего назначения. Обработка сообщений выполняется недетерминированнное время, зависит от входных данных, зависит от внешних систем, плюс часть процессоров периодически занимается другими процессами. Тот лоад-балансинг, который ты описал всасёт в такой ситуации — скорость работы системы будет определяться самым медленным процессором, а он может быть сколь угодно медленным.

Вобщем, пока ты никакой общей задачи не решил, и ничего нового не открыл. Я подобные решения применял, но в очень *частных* случаях, и оно не обобщается на общий случай.
Если можешь обрисовать решения всех проблем, которые я указал — то, пожалуйста. Буду очень признателен. И это будет, наверное, первая интересная и новая информация в этом топике.

Здравствуйте, Gaperton, Вы писали:

G>А потом кто-нибудь додумался бы до того, чтобы читать из разделяемого мутабельного массива, используемого в качестве индекса, атомарними ридами, и писать туда атомарными райтами с мемори барьером. Типо тогда что-то напоминающее транзакционную память получится.

Подожди, у нас же тут с атомарными чтениями должны быть какие-то дорогие барьеры памяти?
Или нет?

R>Дело тут не с блокировках. Агентная система достаточно распределенная, плюс нет проблемы очереди сделать неблокирующими. Проблема в том, что каждая отправка сообщения имеет существенную стоимость и с ней надо считаться. Извини, но твоё решение на общее пока не тянет. И твой тезис "Её можно сделать сколь угодно мало требовательной путём группировки сообщений." в общем случае не выполняется.

Это не моё решение, это решение <a href=http://ru.wikipedia.org/wiki/%D0%91%D1%83%D1%80%D1%86%D0%B5%D0%B2,_%D0%92%D1%81%D0%B5%D0%B2%D0%BE%D0%BB%D0%BE%D0%B4_%D0%A1%D0%B5%D1%80%D0%B3%D0%B5%D0%B5%D0%B2%D0%B8%D1%87&gt;академика Бурцева</a>.

Да, с латентностью надо считаться. Но если дать этой системе сильно параллельную задачу, то её параллелизм придётся сдерживать с помощью throttling'а.

В отличии от.

R>Пока не похоже. Пока что ты обрисовал решение на *логическом* уровне. Попробуй обрисовать его *эффективную* реализацию на *физическом* уровне в софте для общего случая. Ты увидишь, что это сделать нельзя. То, что ты говоришь — это решение, но это решение либо для железа (ты ж оттуда эту идею взял?), либо для частных случаев в софте. Но не для общего случая в софте. Ты не можешь с таким решением выходить и громко заявлять, что ты решил какую-то общую проблему, и что "Её можно сделать сколь угодно мало требовательной путём группировки сообщений.".

Почему не могу. Могу. Смотри.

Громко заявляю, что я решил какую-то общую проблему, и что "её можно сделать сколь угодно мало требовательной путём группировки сообщений".

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

Так не надо, чтобы долго обрабатывали. Надо, чтобы недолго.

Более того, динамический поток данных даёт возможность рулить размером программы сообщения. Можно балансировать — чем больше входов у узла, тем больше будет программа узла и меньше выявляемый параллелизм выше уровня ILP. И наоборот.

R> Отдельные процессоры выделять под эти потоки не целесообразно. Если они будут разделять процессоры с другими потоками, значит они могут шедулиться для выполнения через 40 мс и больше. Ну вот проходит такое сообщение через эту сеть и получаем внесённую латентность 200 мс.

Да.

При условии, что оно через неё проходит.

R>Такой схемой ты порождаешь массу дополнительно трафика по протоколу когерентности.

Нет. Я не понимаю, откуда ты это взял.

R>В традиционной схеме у нас сообщение сразу качует от кэша-источника в кэш-получателя. С твоей схемой оно покачает по N кэшей. Это чудовищный оверхед, проще сразу сделать одну атомарную RMW операцию и отправить сообщение получателю. Как ты предлагаешь это нивелировать?

Путём высокопараллельной обработки небольших сообщений.

R>Неупорядоченные сообщения это, может, и кошерно. Но факт в том, что никто такую систему использовать не будет. Если кто-нибудь придёт к пользователям Erlang, Scala Actors, Concurrency and Coordination Runtime и др. и скажет, что давайте ка мы у вас уберём ФИФО, т.к. так более кошерно, то его сразу пинками погонят. Правильно, а зачем им это надо?

В Эрланге нет ФИФО, как такового. "Внимательней вглядись" (C) Басё

R>Динамический лоад-балансинг как будешь делать? Пока что ты увильнул статическим.

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

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

Но это тоже решаемо. Достаточно отправлять выше по иерархии те сообщения, что не должны сейчас выполняться на этом процессоре.

R>Но это не катит для систем общего назначения. Обработка сообщений выполняется недетерминированнное, но малое и с небольшой дисперсией время, зависит от входных данных, не зависит от внешних систем, плюс часть процессоров периодически занимается другими процессами. Тот лоад-балансинг, который ты описал всасёт в такой ситуации — скорость работы системы будет определяться самым медленным процессором, а он может быть сколь угодно медленным.

Вставки мои.

Посему достаточно поменьше нагружать самый медленный процессор.

Вот.

R>Вобщем, пока ты никакой общей задачи не решил, и ничего нового не открыл. Я подобные решения применял, но в очень *частных* случаях, и оно не обобщается на общий случай.

Я и не решал. "Всё украдено до нас" (C) ОЫ

R>Если можешь обрисовать решения всех проблем, которые я указал — то, пожалуйста. Буду очень признателен. И это будет, наверное, первая интересная и новая информация в этом топике.

Я ленюсь.

Вот ссылки:
http://thesz.mskhug.ru/svn/hiersort/ — там в подкаталоге doc лежит статья про машину динамического потока данных с частичной сортировкой сообщений.

http://thesz.livejournal.com/545287.html — чуток описания про преобразование обычной программы в программу для машины динамического потока данных. Делаем такую VM и все преимущества у нас в кармане.

Где-то у меня ещё что-то было, но я сейчас отыскать не могу.

Здравствуйте, remark, Вы писали:

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

Здравствуйте, thesz, Вы писали:

R>>Неупорядоченные сообщения это, может, и кошерно. Но факт в том, что никто такую систему использовать не будет. Если кто-нибудь придёт к пользователям Erlang, Scala Actors, Concurrency and Coordination Runtime и др. и скажет, что давайте ка мы у вас уберём ФИФО, т.к. так более кошерно, то его сразу пинками погонят. Правильно, а зачем им это надо?

T>В Эрланге нет ФИФО, как такового. "Внимательней вглядись" (C) Басё

Правильно ли я понимаю, что если в Эрланге процессу пришло несколько однотипных сообщений, то Эрланг не гарантирует их выборку в receive в порядке ФИФО?

Здравствуйте, eao197, Вы писали:

E>Правильно ли я понимаю, что если в Эрланге процессу пришло несколько однотипных сообщений, то Эрланг не гарантирует их выборку в receive в порядке ФИФО?

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

Здравствуйте, Курилка, Вы писали:

E>>Правильно ли я понимаю, что если в Эрланге процессу пришло несколько однотипных сообщений, то Эрланг не гарантирует их выборку в receive в порядке ФИФО?

К>ФИФО гарантируется для пары "автор-получатель", язык динамически типизированный, так что типы сообщений значения не имеют (если не учитывать более хитрые вещи аля вложенные receive).

Про динамическую типизацию я в курсе Подразумевались конструкции вида:

receive
  { OK, Data } -> ...
  { FAILURE, Reason } -> ...
  ...

Если процесс получил несколько сообщений вида {OK, D}, где D в каждом экземпляре сообщения имеет собственное значение (например, {OK, 2007}, {OK, 2008}, {OK, 2009}), то гарантирует ли Эрланг, что эти сообщения (т.е. {OK, D}) будут извлекаться из хранилища сообщений процесса в ФИФО?