Метастабильность

[fregimus]

Сырые, только что освежеванные мысли.

Явление метастабильности хорошо известно в электронных схемах. Арбитр — электронное устройство, которое вычисляет, грубо говоря, по какой из входных линий сигнал пришел первым. В различных моделях арбитров возникает ситуация, когда схема приходит в неустойчивое состояние. Неустойчивое состояние разрешается (во всяком случае, инженер старается сделать схему такой, чтобы оно разрешалось). Однако (в моделях, опять же) оказывается, что построить арбитр, который гарантированно разрешает конфликт, невозможно: для любого арбитра случится такая ситуация, что схема не придет в определенное состояние ни за какое конечное время.

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

Насколько важна метастабильность на практике? Известно, что первые многопроцессорные вычислительные машины (а это было до того, как явление было исследовано математически) страдали от проблем с арбитражем. В современных системах минимизируется вероятность входа арбитра в метастабильную область. Например, в [3] показывается, что определенная схема арбитра имеет среднее время между ошибками арбитража, превышающее 10²⁰⁰ лет. Само собой, вероятность эта ничтожна, чтобы иметь практические последствия — дело даже не в том, что это на может произойти, а в том, что отказы по другим причинам в любом практическом устройстве имеют вполне ощутимые вероятности.

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

С другой стороны, обычные нейронные сети, во всяком случае, их вычислительно-модельном изводе, совершенно синхронны. Все вычисления в них ведутся дискретным образом: сперва вычисляются «новые» значения параметров сети на основании «старых», а затем, следующим шагом, «новые» значения деляются «старыми». Я не силен в этой области — вполне вероятно, что не все модели таковы.

В то же время, метастабильнось в вычислительной модели — а именно в теории акторов — тоже изучается. Весьма интересны в этой области работы Карла Хьюита (Carl Hewitt). Он полагает, что в асинхронной модели отсутствует глобальное состояние, то есть, вести речь о нем бессмысленно. Возвращаясь к арбитражу и принимая эту точку зрения, можно сказать, что о времени появления двух сигналов нельзя сказать, какой из них пришел раньше. Это рассуждение, на первый взгляд, противоречит интуиции, но, если задуматься, находится в русле системного подхода: во внутренней жизни, во внутреннем мире системы решение о том, какой сигнал пришел первым, иногда принять невозможно (в силу неизбежности метастабильности) [доб. — значит, во внутреннем языке системы возможно выражение случая, когда ни один из них не пришел раньше, т. е. утверждения «сигнал А пришел раньше» и «сигнал Б пришел раньше» не комплементарны.]

Интересно соотнести это рассуждение с некоторыми философскими рассуждениями, в которых участвует mental state, глобальное физическое состояние всего мозга. Модель мозговых вычислений, учитывающая метастабильность, вероятно, не обладает глобальным состоянием. Я еще не совсем сжился с этой мыслью, поэтому пока развивать ее не буду, хотя мне, само собой, интересно, что вы об этом слышали.

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

_________________________________
1. Palais R, Lamport L. On the glitch phenomenon. Technical Report CA-7611-0811, Massachusetts Computer Associates, Mass. 1976.
2. Anderson J, Gouda M. A New Explanation of the Glitch Phenomenon. Acta Informatica, Vol. 28, No. 4, April 1991.
3. Ginosar R. Fourteen Ways to Fool Your Synchronizer. Proc. of the Ninth International Symposium on Asynchronous Circuits and Systems, 2003.

Comments

Такие посты про "неалгоритмичность" нам по нраву

[pingback-bot.livejournal.com]

User plakhov referenced to your post from Такие посты про "неалгоритмичность" нам по нраву (http://plakhov.livejournal.com/163529.html) saying: [...] http://fregimus.livejournal.com/150368.html [...]

[catta.livejournal.com]

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

[janatem.livejournal.com]

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

[fregimus.livejournal.com]

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

Там вот что оказывается:

Definition: An arbiter is called delay-bounded iff each of its initialized histories is finite. An arbiter is called stable iff in each of its initialized histories the value of one external output remains unchanged. An arbiter is called glitch-free iff it is both delay-bounded and stable; otherwise it is called glitch-prone...

The feedback restriction is actually not needed to prove the nonexistence of stable arbiters... The proof that delay-bounded arbiters do not exist is another matter. In fact, as we now show, if the feedback restriction is removed from our definition of a circuit, then a delay-bounded arbiter exists.

[fregimus.livejournal.com]

Спасибо, рад, что именно Вас это заинтересовало.

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

Ограничение есть только в «цифровой» модели Андерсона-Гауды. В «аналоговой» модели его нет, там вместо него ограничение на время задержки. Оно, мне кажется, biologically plausible — у нейрона есть минимальный интервал между срабатываниями, время, когда он не реагирует на входные сигналы после выходного импульса, так ведь?

[catta.livejournal.com]

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

[janatem.livejournal.com]

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

Это я не понял. Во-первых, почему вероятность _повышается_ с понижением быстродействия? Интуитивно кажется, что будет в точности наоборот. (САПРы для разработки схем указывают на потенциальные источники нестабильности (например, говорит, что среднее время до наступления метастабильности меньше 10^8 лет); а если плохо развелось, то снижение тактовой как правило лечит.)

Во-вторых, с ростом сложности системы ситуация деградирует не экспоненциально, а вроде бы линейно. Если считать наступление метастабильного состояния невосстановимым отказом, то можно говорить о времени наработки на отказ. При некоторых предположениях можно считать, что отказы элементов имеют экспоненциальное распределение (то есть считаем, что элементы "не стареют" — вероятность получить отказ в течение этого часа такая же, как и в течение следующего часа), а сами элементы отказывают независимо друг от друга. Тогда время наработки на отказ всей системы растет _линейно_ по количеству элементов. (Я совсем недавно про это думал, когда пытался оценить пределы роста в области HPC.)

[fregimus.livejournal.com]

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

Насчет второго — просто не знаю. Я не до конца еще разобрался в этом. Посмотрите статью [2], если интересно. Там метастабильность выражается в порядке перебора элементов. Мне кажется, что число метастабильных вариантов может расти вообще как факториал от общего числа элементов — так что предположение об экспоненциальности здесь, возможно, даже консервативно. Но это рассуждение, сами видите, очень поверхностное, а глубже я не анализировал.

Доб. забыл: http://www.cs.unc.edu/~anderson/papers/acta91.pdf

[alisa-lebovski.livejournal.com]

А не есть ли это классическая проблема Буриданова осла?
Известно, что реальные ослы с ней успешно справляются.

[fregimus.livejournal.com]

Да. Вопрос здесь именно в том, как им это удается.

[alisa-lebovski.livejournal.com]

Мне кажется, тут нужен фактор случайности.
Т.е. внести в схемы генератор случайных чисел (может быть, квантовый).

[fregimus.livejournal.com]

Так внести-то я ничего не могу. У меня задача не изобрести осла, а понять, как он уже устроен.

[gabriel-irk.livejournal.com]

Мне отец как-то объяснил, что для реального осла — куда голову повернул, туда и ближе.
Уверен, что так оно и есть на самом деле.

[antihydrogen.livejournal.com]

Спасибо. Очень интересный пост

[fregimus.livejournal.com]

И не говорите, сам удивляюсь…

[antihydrogen.livejournal.com]

По крайней мере, из него я впервые узнал о существовании хорошо известного явления :). Далек я от схемотехники, страшно далек...

[palmas1.livejournal.com]

А насколько серьёзна проблема впадания в метастабильное состояние? Это препятствие для доказательства или техническая проблема?

Лет 10 назад я интересовался вопросом, в чём могут быть преимущества вычислительной системы с динамическим хаосом. Ответ получился такой: если интересует способность производить воспроизводимые вычисления, то хаос не нужен. Но если проблема арбитра весьма серьёзна, то там хаос как раз может пригодиться. Метастабильных состояний в хаосе уйма, но аттрактор всегда от них убегает, а сколь угодно малый шум их убивает.

[fregimus.livejournal.com]

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

[109.livejournal.com]

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

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

не могли бы вы его пересказать "in layman terms", каким-нибудь более понятным образом, чем это сделано в оригинальной работе?

[fregimus.livejournal.com]

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

[gouriev.livejournal.com]

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

[fregimus.livejournal.com]

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

[malaya-zemlya.livejournal.com]

: значит, во внутреннем языке системы возможно выражение случая, когда ни один из них не пришел раньше, т. е. утверждения «сигнал А пришел раньше» и «сигнал Б пришел раньше» не комплементарны

Существует же полно случаев, когда физически разделенные по времени сигналы воспринимаются как единое целое. Иногда это всякого рода временные иллюзии, иногда это часть нормального процесса, типа распознавания речи. Ну и понятие "одновременности" в нашем языке тоже пристутсвует.

Или не об этом речь?

[fregimus.livejournal.com]

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

[v-s-c.livejournal.com]

А есть ли в нервной системе арбитр?

Если есть, то не достаточно ли естественного шума, чтобы вывести систему из метастабильного состояния?

[fregimus.livejournal.com]

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

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

[poslednii-krot.livejournal.com]

Ничего не могу сказать по существу, к сожалению; просто напомнило: в книге Rhythms of the brain (G. Buzsáki) читал очень похожие мысли. О невозможности применить е мозгу понятие "состояние", о сложности восприятия одновременности. Вроде бы, многие сигналы (особенно пришедшие по разным каналам), воспринимаемые мозгом как одновременные, на самом деле такими не являются.

[fregimus.livejournal.com]

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