Как стать автором
Обновить

Комментарии 11

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

В общем автор сумел отбить желание читать статью.
В следующий раз буду анекдотами перемежать.
Лишь бы это помогало пониманию.
Согласен. На более простой модели в первых частях пытался писать не формально. Параллелизм, как мне кажется, без формализмов будет еще менее понятен.
Я вижу, что Вы — специалист и пишите, наверняка, общепринятым языком для специалистов Вашей профессии. Некоторое время назад я участвовал в проекте по разработке микроэлектроники, мне знакома логика и тоже интересно то, о чем Вы рассуждаете. Могу ли я полностью понять Ваши идеи, если никогда не программировал прошивки для ПЛИС? Можно ли передать смысл исследуемой Вами проблемы, каким-то образом скрыв несущественные технические подробности? Я вполне допускаю, что часто сделать так не получается, но, если это все же удается, то результаты работы оказываются потенциально ценными далеко за пределами той области, в которой они были впервые получены.
Исследуемая проблема специальными знаниями не перегружена. В свое время мой руководитель ввел меня в курс дела буквально за полчаса. Этого хватило, чтобы сразу начать двигаться вперед.
Суть проблемы. Имеем двоичный вектор. Координаты вектора принимают значение 0 или 1. Координаты принято называть сигналами. Исследуется процесс изменения значений сигналов. Изменение значения сигнала принято называть переключением или событием. Процесс изменения значений сигналов называют поведением. Поведение описывается на языке STG. О языке можно почитать здесь. Но вполне достаточно знать, что STG это интерпретированная сеть Петри, где каждому переходу в соответствие ставится какое-то событие. Основное требование: между двумя переключениями одного знака одного и того же сигнала обязательно должно быть переключение того же сигнала противоположного знака.
Поведение (описанное на языке STG) — это исходное задание. Задача: построить систему логических функций, которая реализует данное поведение. При этом каждому сигналу ставится в соответствие одна функция. Логическая функция определяется на множестве всех возможных значений двоичного вектора. Каждое конкретное значение вектора называется состоянием.
Логическая функция для сигнала определяется так. Вводится понятие возбуждения сигнала. Сигнал возбужден, если (применительно к языку описания) созданы условия для срабатывания перехода (события, переключения данного сигнала), но сам переход еще не сработал. При срабатывании перехода (переключении сигнала) возбуждение снимается. Итак логическая функция сигнала равна 1 для тех состояний, в которых сигнал равен 1 и не возбужден или же сигнал равен 0 и возбужден. Значение 0 определяется аналогично.
Казалось бы задача тривиальная: по таблице истинности вычислить минимальную функцию. Но есть 2 «НО».
1. Предел для машинных вычислений 20-30 сигналов («взрыв состояний»).
2. Чем сложнее функция, тем менее реальный физический логический элемент соответствует модельным представлениям. Современные технологии подошли к порогу необходимости использования только минимальных двухвходовых элементов.
Первая проблема решается с помощью вычисления функций непосредственно по графу (STG). Эта публикация вводная часть. Сложность вычисления одной функции пропорциональна (приблизительно) квадрату от количества событий в графе.
Вторая проблема решается добавлением новых координат (сигналов) в двоичный вектор и соответственно в STG. При этом проекция полученного STG на первоначальные сигналы совпадает с исходным заданием. Этому посвящены другие посты.
Данная тематика используется применительно к синтезу самосинхронных схем, поскольку в STG заложен неограниченный промежуток времени на переключение возбужденного сигнала и соответственно этим же свойством обладают полученные логические функции (логические элементы в схеме).
Вот — умеете ведь понятно объяснять!

Но почему предел такой маленький — 20-30 сигналов? Это же 2 в степени 20-30 возможных состояний, то есть миллион-миллиард, тогда как для компьютера и триллион состояний не такая большая проблема даже при использовании простейшего перебора (ну посчитает часик, но зато всё пространство в триллион состояний охватит). При более эффективном обходе пространства состояний можно получить результат много быстрее (чем вы, похоже, как раз занимаетесь). Или рассматриваются исключительно железные реализации перебора?

Так же интересно — как предлагаемая в статье модель описания системы соответствует подходам к моделированию нейро-сетей? Там тоже «включено-выключено» на каждом нейроне, правда с учётом весов связей, но в случае одинаковых весов — очень похоже, то есть имеем частный случай.

И почему сложность вычисления функции пропорциональна квадрату количества переключений? Функция (комбинацию которых ставится задача найти) может описывать один элемент, и может миллион элементов — как осуществляется выбор количества элементов? Например, в случае цепочки элементов сложность будет константой, ибо входной элемент определяет выход всей цепочки (или я не понимаю способа взаимодействия элементов?).

То есть по каждому шагу вашего рассуждения о графах из элементов нужно пройтись с точки зрения «а понятен ли данный шаг не разбирающемуся в данной специфической области технически грамотному человеку?». И тогда получится прекрасная статья.
Миллиард состояний это только начало. Из этого миллиарда перебираются все возможные пары для потенциального объединения в более крупные кубы. Полученные объекты подвергаются такой же процедуре. Количество объектов множится экспоненциально. Затем с такой же скоростью начинают сокращаться, но алгоритм до этого момента не доживает. При работе с графом перебор не нужен. Экстремаль вычисляется за один проход по графу. Отсюда и оценка сложности алгоритма.
Про нейросети надо будет поинтересоваться, возможно что-то похожее.
Благодарю за подробное объяснение, Вы решаете действительно интересную задачу. На досуге постараюсь внимательно прочитать Ваши статьи и дать обратную связь.
Свежий взгляд полезен, поскольку асинхронное сообщество зациклено на состояниях, не замечая преимуществ работы с событиями.
Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории