Два типа событий

[vak]

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



Представим, что мы прогнали симулятор до останова #24 (модельное время равно 24), а затем дали команду выполнить ещё один цикл (до останова #25). Что при этом произойдёт?

Из очереди событий выполнятся некоторые действия (типа A), затем счётчик модельного времени увеличится на единицу, после этого выполнятся ещё какие-то действия (типа B).

События типа A - это "неразрушающие" действия, типа чтения из памяти. Они не изменяют состояние моделируемого объекта. События типа B - изменение состояния, например запись в память.

По опыту, события A обычно начинают некоторый процесс, растянутый по времени. События B завершают его. К примеру, рассмотрим выполнение оператора "x += 1". Оно состоит из двух событий:

• чтение значения x - событие типа A
• запись значения x+1 - событие типа B

Если выполнение этого оператора занимает один такт - действия A и B выполняются в одном цикле симуляции. Если больше - событие B откладывается на N-1 цикл.

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

Comments

[perdakot]

Может, A и B нельзя выполнять в одном цикле?

[vak]

Они в одном цикле симуляции, но время для них разное.

[perdakot]

одни выполняются в начале цикла, другие в конце цикла

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

[vak]

Модельное время дискретное. Обычно события выполняются между приращениями времени. Этого недостаточно, о чём и пост.

[ichthuss]

Полагаю, что в литературе это попросту записывалось в математической нотации, как state(n+1) = f(state(n)). В этом случае весь забор данных выполняется при предыдущем счетчике, а все записи идут в новый.

[vak]

И это работает плохо, как показывает практика. Об этом я собственно, и пытаюсь сказать.

[ichthuss]

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

[vak]

Потому что мне потом приходится такой код переписывать.

[nz]

событие B откладывается на N-1 цикл

Эмулятор машины времени?

[vak]

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

[nz]

Я к тому, что точно -, а не +?
А то звучит как "приходите вчера".

[chabapok]

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

> дискретного времени на multi-threading

У меня тоже что-то подобное было: сплошные подводные камни.

Уже на этапе работы с часами начинаются проблемы. Например, ntp может двигать время назад. вроде не должен, но иногда делает, например когда високосная секунда прилетает, то ntp переставлял таймер на 1секуну назад. (Щас наверное это уже исправили)

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

Ну и всякие такое, щас уже не вспомнишь.

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

Еще бывает, что по ntp приходили пакеты некорректные - и часам крышу срывало полностью.

[vak]

Не то чтобы боль, но обретённая мудрость. 😀

Понижение гранулярности не помогает. Если у вас проблемы между тактами #24 и #25, то переход с миллисекунд на наносекунды приведет к тем же проблемам между #24000 и #24001. Или между #24999 и #25000. Или где-то ещё. Дискретное время, оно такое.

[ircicq]

Напомнило недавний пост о двух тактовых фазах в CPU:

[vak]

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

[spamsink]

Собственно, обновление значений сигналов в левых частях non-blocking assignments с задержкой - это и есть события типа B.

Кстати, https://dl.acm.org/doi/pdf/10.1145/360715.360758 (хотя там скорее про структуры данных)

[vak]

В верилоге всё сделано правильно, да. Но никто ж не объясняет механизм, народ и не в курсе.

Любопытная статья. Выходит, в 1975 году народ активно интересовался эффективным представлением очереди событий. Нынче оно реализуется в Си++ стандартным std::set с несложной функцией сравнения. Недавно я показывал: https://vak.dreamwidth.org/1105670.html

[vit_r]

Автоматы Мили и Мура не стоит, наверно, совмещать в одной схеме. B надо разбивать на части.

[vak]

"Когда у вас в руках молоток - всё вокруг выглядит как гвозди."

Честно говоря, не вижу тут автоматов Мили и Мура. 😀

[vit_r]

С автоматами проще.

[vak]

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

[vit_r]

Вот там, где "не приходится задумываться" и скрыты резервы. (^_-)