Многопоточный обход графа

Question

У меня есть график, который представляет большую сетевую сеть. Каждый провод / устройство может быть либо "активным" (он - через некоторый путь проводов и устройств - подключен к источнику питания), либо "неактивным" (он не подключен к источнику питания). Никакие заземляющие провода или напряжения не моделируются. Это либо активно, либо неактивно.

Существуют разные виды устройств. Устройства могут иметь любое количество разъемов. штекеры соединяют устройства через провода. Точная схема расположения проводов не важна. Имеет значение только то, какие штекеры соединены вместе.
Несколько примеров для устройств:

• Фонарь
  Используется для простого отображения определенных состояний схемы. Он имеет один штекер, который контролирует состояние лампы. Как видно на скриншотах ниже, активные устройства и провода отображаются красным, неактивные синим.
  
• Источник питания
  Всегда активный. Он имеет один штекер, который всегда будет выводить сигнал. Поэтому провод, подключенный к этому разъему, всегда будет активным, и устройства, подключенные к этому проводу, также станут активными.
  
• вход
  Представляет некоторый способ взаимодействия с внешним миром. Может быть установлен активным или неактивным процессом, который запускает симуляцию. Он будет отражать свое состояние на своем единственном разъеме.
  
• Реле
  Это устройство делает что-то более сложное. Он состоит из нескольких частей: он имеет штекер катушки, который контролирует состояние катушки в реальном реле. Он имеет любое количество переключателей, которые контролируются состоянием реле. У каждого есть три разъема, такие как переключатель SPDT. Когда реле неактивно, входящие сигналы от нормально замкнутого штепселя будут пересылаться на общий штекер и наоборот, а сигналы от нормально разомкнутого штепселя не будут пересылаться. Когда реле активно, оно вместо этого подключает общий и нормально разомкнутый разъем.
  

Я хотел бы пройтись по этому графику как можно быстрее. Состояния устройств и проводов на графике перед прохождением - это "генерация тока". Обход графика рассчитывает состояния следующего поколения. После завершения обхода состояния устройств и проводов устанавливаются в новые состояния. Обновление состояний выполняется в две части (вычисление состояний и их применение), чтобы избежать проблем, например, когда реле может изменить свое состояние и немедленно повлиять на обход. Как и при запуске Game of Life, но вместо того, чтобы записывать результаты в новый массив и копировать все обратно после расчета, вы постепенно перезаписываете данные последнего поколения и создаете неправильные результаты.
Обход должен в основном сделать это:

• Сначала предположим, что все объекты (устройства, вилки, провода) будут неактивными в следующем поколении. Они будут отмечены как активные, когда они достигнут обходом.
  
• Затем найдите все вилки, которые определенно питаются. Как и источники питания, среди других устройств, которые могут выводить сигналы. Это отправные точки для прохождения.
  
• Если он уже помечен как активный, пропустите его. Объекты могут быть достигнуты несколько раз путем обхода. Это приведет к бесконечным циклам / рекурсиям, если этот случай не будет обнаружен.
  
• Отметьте его как активный.
  
• Сообщите устройству, к которому он подключен, что штепсель стал активным. В зависимости от того, какой разъем на каком устройстве, сделать что-то. например, общая вилка на одном из переключателей реле. Если реле активно, выполните возврат для нормально разомкнутой вилки, в противном случае для нормально замкнутой вилки
  
• Сообщите о подключенном проводе, отметьте его как активный и выполните поиск всех остальных разъемов, прикрепленных к проводу.
  
• Когда все начальные точки выполнены, присвойте состояние "следующего поколения" фактическому состоянию каждого из объектов.
  

Вот пример простой схемы. Сначала все неактивно:

В следующем поколении проводная сеть слева, провод вверху и левая лампа все становятся активными, потому что они каким-то образом связаны с питанием:

Здесь я активировал вход внизу:

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

В следующем поколении провода меняются:


Существующий в настоящее время график не оптимизирован для быстрого обхода. Он оптимизирован для удобства редактирования и для отображения более подробной информации, например маленьких стрелочек на красных проводах, которые показывают, откуда поступил сигнал. И есть много "ненужных" шагов, которые можно оптимизировать. Есть устройства, которые просто соединяют провода с другими проводами в другой части цепи. Это только для оптики, так как она проясняет, какие части схемы образуют логическую единицу. А поскольку провода должны быть легко редактируемыми, каждый изгиб или пересечение - это устройство, которое ничего не делает функционально, но его можно перетаскивать на экран. Проводная сеть на левой стороне скриншотов выше - это фактически 4 отдельных провода и 2 из этих псевдоустройств.
Из-за этого это слишком медленно. С самой большой сетью я получаю в лучшем случае 3 поколения в секунду.

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

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

Какие данные должен содержать график и какие приемы можно использовать для оптимизации скорости? (высокое использование памяти не проблема вообще)
И как я могу распределить нагрузку на несколько потоков? Сделать это однопоточным достаточно просто, но как сделать так, чтобы несколько потоков не делали глупостей, не снижая производительность, создавая повсеместные блокировки? Может быть, на этапе настройки можно определить, какие части графика должны выполняться каким потоком?

Я использую.NET (Framework 4.0), но любые общие советы приветствуются.