Перейти к содержанию

    

Всем привет!

 

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

 

КА Мили - это автомат, у которого выходы зависят и от состояния самого автомата, и от его входов. КА Мура - автомат, выходы которого зависят только от его состояния. Ещё на просторах интернета попался некий КА Медведева :), у него выходы - это просто его состояние - по сути это вырожденный автомат Мура, но речь пока не про него.

 

Плюсы и минусы обоих вариантов очевидны:

 

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

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

 

А вопрос, собственно, такой: какое практическое преимущество даёт знание этой классификации нашему брату - ПЛИСоводу? Подозреваю, что для разработчиков компиляторов, синтезаторов эта классификация может быть полезна - например, в этой теории могут быть доказаны теоремы, что если, де, автомат Мили, то можно провести такую-то или такую-то оптимизацию, а если Мура, то вот такие-то или такие-то ограничения. Как сказал один мудрый человек: "Нет ничего практичнее хорошей теории". Но нам-то - простым пользователям компиляторов, синтезаторов, есть практическая польза? Например, вот описал я логику КА, вижу, что он Мили. Или Мура. И что? Что даёт это понимание? Ведь логику-то я описал, исходя из требований целевой задачи, а не ставя цель, сделать Мили или Мура.

 

И вот опыт, вроде, говорит, что сие знание скорее академическое, но в книжках-то и доках вендоров регулярно упоминают обе фамилии, когда речь заходит про КА. Это порождает сомнение - может, я чего-то важного не ухватил. В общем, прошу поделиться мнением/опытом: какая практическая польза для ПЛИСовода заключается в знании этой классификации и её свойств, где и как это применяется при описании логики на ПЛИС?

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

А очень часто многие академические знания, остаются академическими и на практике абсолютно не нужными, да и применить их не получится.

Я ещё как относительно недавний выпускник хорошо помню, как писал магистерскую диссертацию. Тема была связана с оптимизацией размещения системы электропитания внутри БНК. Я прочитал тонну литературы по методикам оптимизации. И в этой литературе было огромнейшее количество математики. Вот только все эта математика не имела практического применения. Ибо математически доказывалось что находились экстремумы целевой функции. Но как эту математику перенести на реальную жизнь - увы. Практически ни одна книга не давала ответа на этот вопрос.

Вот так-же приимерно с цифровыми автоматами.

Можно нарисовать граф переходов КА Мура, или Мили. Потом обратиться к теории графов - и оптимизировать этот автомат. И получить красивый "оптимизированный" КА место которому только на страницах учебника, ибо на практике это не применить.

Я считаю надо разделять грань между теоретическими(академическими) знаниями и практическими.

Пусть теория останется для профессоров и студентов. Нам важен результат (практика) !

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты
при описании КА смотришь на целевую задачу и решаешь её, исходя из доступных средств. Собственно, описываешь автомат так, чтобы его работа удовлетворяла целевой задаче, и почему-то тут [мне] ни разу совсем не потребовалось погружаться в эту классификацию и анализ свойств - просто кодишь логику, конечно имея в виду, что комбинационная задержка может подзатянуть слаки и/или дополнительный регистр сдвигает результат на такт, это надо тоже учитывать...

У меня тоже именно так и происходит. Решаешь в первую очередь задачу, но где-то в ПЗУ держишь мысли о том, что есть две разновидности КА. Академические знания - это фундаментальные знания. Как ни крути, мы всегда их используем, даже не подозревая иной раз. Какой бы КА вы не описали, если посмотреть на него внимательно, то можно увидеть, что это есть КА Мура или КА Мили. У меня чаще получается Мили, т.к. стараюсь описывать все одним автоматом. А если посмотреть темплейты, например, в квартусе, то там дается КА Мура. Но мы же в первую очередь решаем задачу, поэтому делаем, кто как привык, кому как удобнее.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты
Можно нарисовать граф переходов КА Мура, или Мили. Потом обратиться к теории графов - и оптимизировать этот автомат. И получить красивый "оптимизированный" КА место которому только на страницах учебника, ибо на практике это не применить.

но можно и по-другому: составить спецификацию, сделать автоматы управления, и получить нормальную шину, например AHB или AHB-lite. Что, собственно, обычно и происходит. Что характерно, и у меня так получалось, и у коллег, и у товарищей из synopsys, и у товарищей из ARM. Так что, дело не в том, что конечным автоматам место только на странице учебника. Исследование среди выпускников стенфорда (если верить Джеффри Ульману) вообще показало, что конечные автоматы - одна из наиболее часто используемых на практике вещей из всех тем, которым они научили своих студентов.

Изменено пользователем one_eight_seven

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты
составить спецификацию, сделать автоматы управления

А как тут применить ту же теорию графов ?

Т.е в какой момент теория поможет улучшить практический результат ?

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты
А как тут применить ту же теорию графов ?

Т.е в какой момент теория поможет улучшить практический результат ?

Какой-то сферический вопрос в вакууме. На сферический вопрос, держите сферический ответ.

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

 

Хотя, ессно, часто в одном автомате используется и та и другая концепция одновременно. Наверное, так не стоит делать, или нет?

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты
Наверное, так не стоит делать, или нет?

 

На мой взгляд - не стоит. Часто такое бывает, когда функции нескольких автоматов запихивают в один. Если же не тот случай, то можно сделать ещё один выход в автомате МУРа, которым блокировать или разрешать прохождение определённых сигналов.

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Несколько комментариев

1. Строго говоря, автоматы Мура и Мили, это алгоритмы, состоящие из шагов, т.е. по сути - программы. К электронике имели отношение весьма отдаленное. То, о чем вы пишете, это реализации алгоритмов Мура и Мили в виде автомата Хаффмана. Автомат Хаффмана - это логика, на выходе которой включена память, + необязательная обратная связь с выхода памяти на вход логики. Хаффман это придумал лет за 15 до появления алгоритмов Мура и Мили. Бывают еще не-Хаффмановские автоматы - проектируются с использованием графов, и не имеют четкого разделения элементов на память и логику.

2. Автомат Мили может быть сведен к автомату Мура, поэтому автоматы Мили упоминают лишь вскользь, для галочки.

3. Все синхронные схемы - уже автоматы Мура. Просто потому, что триггер - это элемент памяти, добавим перед ним логику - получаем Хаффмановскую модель автомата, т.е. фактически - реализацию алгоритма Мура/ автомат Мура.

4. Все же топикстартер спрашивает о более сложных автоматах, чем просто Мура/Мили. Как уже было верно написано, если воспользоваться теорией автоматов, то можно минимизировать число состояний у проектируемого FSM. На практике никто этого не делают - ваяют на верилоге как получится. Надо только понимать, что если минимизацию не делаете вы, то это придется делать тулу. А уж как он это сделает .. поэтому надо очень хорошо покрывать тестами автоматы в коде - их реализация вполне может оказаться некорректной. Синтез автоматов - одно из наиболее слабых мест современных тулов.

5. О применении теории графов. Если делать по науке, то можно вручную сократить число флопов в вашей FSM, не отдавая это на откуп синтезатору. Вот и все преимущество. Но на мой взгляд, гораздо полезнее просто научиться правильно описывать FSM на верилоге, тогда и тул будет корректно работать.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты
5. О применении теории графов. Если делать по науке, то можно вручную сократить число флопов в вашей FSM, не отдавая это на откуп синтезатору.

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

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

 

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

Позволю замечание. То, что в книгах не давались ответы на практические вопросы совсем не доказывает, что математический аппарат, который давали авторы, бестолковый и не применим на практике. Тут я не имею в виду именно те книги, которые вы прочитали. Сомнительным мне кажется сам подход игнорировать теоретическую науку, оставляя её 'академикам'.

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

 

По теме. Мне думается, что с триггерами происходит та же история. Когда-то люди придумывали разные бистабильные элементы, используя ламповые, а потом транзисторные структуры. Эти триггеры получали разные названия. D-, JK-, RS-, T-триггер и прочие. Сегодня, не смотря на то, что ключевой логический элемент физически может быть реализован в виде триггера какого-то конкретного типа, программист же может не задумываться, какой именно триггер по типу он использует, ориентируясь только на его конкретную функциональность. То есть, перефразируя ув. dxp, просто кодишь логику, не погружаясь в классификацию и анализ свойств.

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Доброго времени суток!

 

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

Поддержу вышесказанное. И вот почему.

Все, кто относит себя к практикам, пишут код не ради кода а ради результата. И тут важно понимать, что код, написанный для ПЛИС ложится на уже готовый кристалл. У "укладка" происходит при помощи неких компиляторов, умеющих оптимизировать много чего, в том числе и КА.

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

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

Поделиться сообщением


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

Принцип KISS :rolleyes:

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Спасибо всем за ответы, в общем и целом примерно так и думаю, рад, что моё понимание и личный опыт согласуется с общим трендом.

 

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

 

Такая докомпозиция позволяет проще воспринимать дизайн, легче им управлять. Например, такой "отделённый" автомат проще заменить на другой или разбить на два или более более мелких и простых КА. Опыт научил, что в большинстве случаев эффективнее реализовывать несколько более простых, хотя и связанных друг с другом, автоматов, вместо одного большого, с десятками состояний. Именно благодаря декомпозиции легче видеть "узкие" места и проще их исправлять (т.к. намного меньше по сравнению с большим КА перекрёстных связей).

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты
Можно замутить автомат по науке, но он будет не так прозрачен и понятен для программиста

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

Не могу согласиться по той простой причине, что такие серьезные пакеты, как Simulink Stateflow до сих пор придерживаются методологии разделения автоматов на Мили/Мура и рекомендуют их использовать вместо "классических" автоматов (я так понимаю, что "классический" автомат в представлении Stateflow - это просто микс из этого всего) как раз потому, что они более проверяемые на этапе компиляции и методичные, а Мура еще и более эффективные в железе. Надеюсь не стоит упоминания, что Stateflow автоматически генерит из автоматов вполне сносный и HDL и Си-код и все это сделано в угоду "скорость разработки, читаемость кода преобладают над аппаратурной эффективностью".

 

Поэтому знание автоматов Мили/Мура - это еще современность - хороший автоматчик с теоретической подготовкой на Матлабе может быстро забабахать очень вполне себе оптимизированный читаемый автомат, работающий на любой ПЛИСине или микроконтроллере, а вот ПЛИС-программист или Verilog-кодер - это ИМХО уже прошлое, но это отдельная тема.

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты
а вот ПЛИС-программист или Verilog-кодер - это ИМХО уже прошлое, но это отдельная тема.

У вас просто очень мало знаний в этой области и очень узкий кругозор.

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Для публикации сообщений создайте учётную запись или авторизуйтесь

Вы должны быть пользователем, чтобы оставить комментарий

Создать учетную запись

Зарегистрируйте новую учётную запись в нашем сообществе. Это очень просто!

Регистрация нового пользователя

Войти

Уже есть аккаунт? Войти в систему.

Войти