nedoPC.org

bar, ты приватные сообщения никогда не читаешь?

P.S. я на старой работе лет эдак 14 назад делал симулятор функциональных блоков (по сути схемный ввод абстрактных алгоритмов) и компилятор из графического представления этих блоков в си тоже делал - так что могу на пальцах обрисовать все возможные подводные камни - начиная от путей избегания зацикливания симулирующего алгоритма и кончая автоматической отрисовкой непекрывающихся соединений между компонентами

Это по-моему не требует особых "путей". По одному биту на каждый элемент, значения которых одинаковы перед началом очередной итерации симуляции, и которые инвертируются к концу этой самой итерации.
Что значит "неперекрывающихся"? В смысле тех, что проходят не под компонентами? Я как-то не задумывался о том, чтобы прятать соединения под компонентами. А это надо?

Это если надо будет автоматически рисовать соединения между компонентами (не вручную), то я знаю как сделать проще

P.S. А в каком порядке будет происходить твоя итерация симуляции?

Понял, о чём речь. И как, интересно? Мне ничего умнее проецирования на две перпендикулярные прямые (одна из которых параллельна новому соединению) в голову не приходит.
Ну если честно, я не особо вдумывался в это. То есть понятно, что проблемы определённого рода там возникнут, в том числе и проблемы типа того, что соединение должно быть в двух состояниях 0 и 1. И эти проблемы не решаются порядком обхода. Другое дело что они всплывать могут на разных этапах. Но чем это может помочь -- я не вижу. То есть если бы был какой-то более умный способ выбрать состояние для проводника, нежели "кто первый тот и папа"... Хотя да, если обход не рандомизировать принудительно, то если в схеме есть два соединённых выхода которые дают противоречивые значения для соединения, то всегда "побеждать" будет один и тот же, и определяться этот один будет, наверное, порядком добавления элементов в схему. И выглядит это не очень правильным. То есть два соединённых выхода уже выглядят неправильно, но...
Короче, если я правильно всё понимаю, порядок обхода не влияет на выбор структур данных. А раз так, то и какая на данном этапе разница?

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

По поводу отрисовки - у каждого компонента входы располагаются слева, а выходы справа. К каждому входу пририсовываем смотрящий влево отрезок длиной, равной порядковому номеру входа - к первому длиной 1, ко второму длиной 2 и т.д. Со входами делаем тоже самое, но отрезки будут смотреть вправо. В результате у нас получается эдакая ёлочка. Теперь очень просто рисовать соединения между нужными цепями - считаем что соединения всегда состоят из трёх сегментов - вертикального, горизонтального и опять вертикального - т.е. это может быть подобие буквы П либо Ц либо нечто среднее - просто перебираем все варианты двигаясь всё дальше и дальше, находя такую отрисовку, при которой соединение не будет перекрывать никаких других компонентов и не будет лежать поверх соединений того же самого направления, причём если окажется, что мы по ходу уже пересеклись с нужной цепью то на ней и останавливаемся, ставя жирную точку в месте соединения. При этом мы добъёмся полностью автоматического соединения компонентов, расставленных вручную - выглядеть это будет примерно так:



При компиляции в C++ это превращалось вот в такой класс с методом step (один шаг симуляции):


Так что у меня был как интерпретатор схемы, так и компилятор

Кстати при интерпретации можно было записывать "осциллограммы":



Теперь я хочу соорудить нечто подобное, но на си и опенсорцное

А. Я понял к чему это. Это если состояние выходов элемента -- функция его входов и времени, так? Про время в качестве параметра я не подумал.

И почему-то был уверен, что у нас время будет измерятся в количестве итераций симуляции. Ведь для того, чтобы все сигналы появлялись в нужной последовательности, то, при условии что произвольный элемент, в произвольный момент времени, без внешних видимых причин, может вдруг изменить состояние своих выходов... При этом условии, придётся реализовывать (или симулировать) нечто типа "на каждый элемент по real-time thread'у". Просимулировать это вполне возможно, создав очередь "будущих" событий, отсортированную по возрастанию времени до наступления этих событий. М-м-м... [s]и переключая стеки с кода одного элемента на код другого элемента по мере наступления времени того или иного события. Это будет жёстко и круто. Торвальдс с его монолитным ядром на говно изойдётся от зависти.[/s]
Может именно для этого cedar'овский симулятор логики использует очереди событий? Я заглядывал туда, у него там, судя по всему свои события и свои очереди функционирующие вне зависимости от работы очереди gui событий.

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

Неа - как раз время измеряется в количестве итераций симуляции. Функция step схемы перебирает все компоненты, вызывая у них свои функции step. Просто в зависимости от порядка перебора результаты могут различаться или быть вовсе неправильными - например: имеем вход A и 3 выхода - B,C,D. Выход B подключен к входу A через один инвертор I1, выход C подключен к выходу инвертора I1 через инвертор I2, выход D подключен к выходу инвертора I2 через инвертор I3. Предположим, что мы посылаем на вход последовательность 01010101. Вот что выдаст упорядоченная симуляция (считаем, что изначально все выходы обнулены):

А вот что сгенерит неправильная последовательность обхода:

Как видишь результат "симуляции" выглядит совершенно иначе из-за того что у нас имеется трёхступенчатая обратная связь - правильный сигнал доходит до выхода за три такта и если период изменений нашего входного сигнала меньше времени задержки, то могут получатся наложения и неправильная работа симуляции, а если больше - то просто 3-тактовая задержка в распостранении сигнала...

Я может тупой очень... Но чесслово, я долго думал и очень старался. И так и не понял, как эта схема должна выглядеть. То есть во-первых, там по-моему опечатка, наверное так надо(?):Но даже в таком формате, я видимо чего-то не понимаю, поскольку никакой обратной связи у меня не образуется, когда я пытаюсь это нарисовать.

Ага - поправил

Обратная связь получается если эти блоки в неправильном порядке вызывать...

а...
Но я, кажется, понял таки о чём речь.

Я попробую переформулировать, для проверки связи.
Все элементы мы раскидываем по непересекающимся множествам -- слоям. Слой #0 состоит из входов. Слой #N состоит из элементов, от которых длина кратчайшего пути до слоя входов равна N. Говоря путь я имею в виду путь в графе, с вершинами -- элементами схемы, и рёбрами-соединениями между элементами.
И обход оказывается таким:

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

P.S. А зачем отдельно выделять такую абстракцию как слои? Просто компоненты упорядочены в списке и при шаге симуляции мы просто идём по списку, вызывая у каждого компонента метод step (причём компоненты внутри себя также могут содержать списки своих внутренних компонентов, у которых тоже дёргается step)

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

Так понятнее, с чем приходится иметь дело. Я не говорю, что процессору от этого будет проще, но мозгу проще от этого по-любому. И, при этом, "мозговые" абстракции вовсе не обязательно навязывать процессору.

Кстати мой подход с учётом координаты X имеет изъяны - например классическая схема триггера с ходу не заработает - придётся разнести элементы по горизонтали, чтобы обратная связь была только одна, а не две. Так что наверное я возьму на вооружение совет bara - при обходе метить блоки и если пришли к уже отмеченному, то это цикл и его надо разорвать - другой вопрос что надо аккуратнее выбирать место разрыва, чтобы как можно меньше сигналов задерживалось на 1 такт...

А я наконец допёр, почему этот мой подход с одним битом не будет работать. Как раз в случае триггера. Точнее в случае наличия обратной связи.

У меня мысль-то была примерно такая. Поделить всё множество элементов на три непересекающихся подмножества:
1. обработанные на текущей итерации
2. находящиеся на расстоянии 1 от обработанных
3. все остальные

И перенос элемента из 2 в один (как мне казалось) возможен лишь в одной ситуации: если все элементы на расстоянии -1 от данного уже обработаны. (я не знаю, насколько нормально использовать отрицательные расстояния в орграфах, но напрашивается). Дык вот неверно это. В случае если мы пытаемся обработать rs-триггер нам придётся помечать один из И-НЕ как помеченный, несмотря на то, что его состояние зависит от ещё не помеченного второго И-НЕ.

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

Нужен именно твой подход, только вместо "координаты X", надо использовать расстояние в графе. Которое вычислять единожды перед началом симуляции. Допустим организовав обход графа "в ширину". Этот обход в ширину можно было бы использовать и для собственно итерации, но я не вижу хорошего способа реализовать is_nearer_to_scheme_input(ELEMENT a, ELEMENT b). Конечно можно заменить один бит на один трит, и метить "насовсем" пройденные элементы значением 1, совсем не пройденные значением -1, и иметь множество помеченное значением нуль -- это элементы находящиеся на текущем уровне. Но для этого, по факту, придётся в каждый элемент заглядывать дважды. Один раз, чтобы пометить нулём, второй раз, чтобы вызывать его метод step и пометить единичкой. Вероятно при этом не удастся найти способа обойтись без предварительного обхода всех элеменотв с развешиванием на них метки -1. Хотя не, можно, просто на чётных итерациях надо будет помножать эти значения на -1.

По-моему ты черезчур усложняешь...

Кстати в случае триггера оба элемента будут равноправны - и от входов они будут на одинаковом "расстоянии" - как быть в этом случае?

P.S. В случае использования координаты X триггер с двумя И-НЕ, расположенных друг на другом будет просто самовозбуждаться, превращаясь в генератор...