Сказати, що Petrify вирішує, поставлені перед нею завдання, можна лише з великою натяжкою. Вірніше вона дещо може для невеликих завдань (де кількість сигналів ледь перевищує 20), проблема вибуху станів так і не була вирішена. Але і для таких завдань задовільний результат не гарантований. Декомпозиція далеко не завжди дає прийнятні результати.
У чому причина цих невдач? Я б назвав 3 основні:
1. Захопленість STG. Так, це красива, кумедна модель, дуже цікаво грати маркерами і т. п. Але, подумайте, процес перемикання сигналів схеми це такий же процес як виконання будь-якої програми. Ми використовуємо для опису програми мережі Петрі? Для чого тоді вони потрібні при описі процесів, що відбуваються в схемі? У результаті розробники Petrify левову частку своїх зусиль витратили на вивчення властивостей мереж Петрі. А власне завдання синтезу схем так і не були вирішені.
2. Упор на «обчислювальність». Під цим я маю на увазі переконаність, що для синтезу схем обов'язково потрібно обчислювати логічні функції. Як результат, замість вирішення завдань синтезу, досліджувалися тільки можливості зменшення таких обчислень.
3. Нездатність розібратися в причинах проблем, що виникають. Але про це нижче.
А чи є в Petrify, що-небудь хороше? Так, є! Це - ДЕКОМПОЗИЦІЯ. Насправді це природний, фундаментальний і чудовий метод. Важливо тільки розібратися в причинах, чому зазвичай неможлива декомпозиція до мінімальних двовходових елементів без порушення спід-індепендед. А причина цього - кратні сигнали. Під цим я маю на увазі сигнали, які перемикаються більш ніж 2 рази за цикл, або ж сигнали переключаються в двох і більш альтернативних гілках. Авторами Petrify цей факт встановлений не був, чому свідчення «жадібний» алгоритм додавання додаткових сигналів. При цьому кількість додаткових сигналів зменшується за рахунок збільшення числа перемикань таких сигналів. Так, це зменшує обсяг обчислень (які, як я покажу нижче взагалі не потрібні), але створює додаткові проблеми для декомпозиції.
Покажу на прикладі що я маю на увазі. Розгляньмо поведінку з такими обмеженнями:
1. немає вибору;
2. немає паралелізму;
3. немає вхідних сигналів;
4. поведінка знайома, за «» + «» слідує «» - «», за «» - «» - «» + «»;
5. всі сигнали перемикаються строго по 2 рази.
Усунення CSC протиріч, навіть зі збереженням вище перерахованих обмежень, ні у кого викликати проблем не повинно. Тепер кожен сигнал представимо у вигляді тригера:
було:
стало:
Після цього рівняння в загальному вигляді для кожного сигналу виглядає так:
Поведінка сигналів цього рівняння виглядає так:
Обчислювати таке рівняння немає потреби. Потрібно на графі знайти ланцюжок підхоплень a, b, c, d (проти годинникової стрілки) від x-, що перескакує через x +. Властивість CSC забезпечує.
А тепер зробимо декомпозицію цього рівняння:
Поведінка виглядатиме так:
Як видно таким чином можна синтезувати спід-індепендент схему на двовходових елементах. Здається що уявлення кожного сигналу у вигляді тригера виглядає громіздко, але далеко не для кожного сигналу в цьому є необхідність. Виникають при цьому порушення знакоочерговості вирішуються дуже легко, що я покажу нижче.
Отже, ми можемо синтезувати схему на двовходових елементах для будь-якої поведінки, що задовольняє 5 вище перерахованих обмежень. Почнемо ці обмеження поступово знімати.
Знімемо обмеження 4 - вимога знакочинюваності. У отриманій підсумковій схемі всі двовходові елементи мають два види поведінки:
Скасування обмеження 4 може створити тільки одну проблему: розголошеність напрямку перемикань між сигналами a і b. Це виправляється введенням інвертора (сигнал c). Знову ж без порушення спід-індепендед.
У зв'язку з цим знаки можна розставити в самому кінці процесу синтезу схеми (з метою мінімізації кількості додаткових інверторів).
Знімемо обмеження 3, введемо вхідні сигнали. Оскільки перемикання додаткового сигналу робити причиною перемикання вхідного сигналу погана практика, ми це заборонимо. У зв'язку з цим можуть виникнути проблеми, ознакою яких є ситуація, коли перемикання вхідного сигналу є причиною перемикання вхідного сигналу. Всього виділяються 3 класи проблемних поведінок.
1 клас. У спрощеному вигляді це перемикання вхідного сигналу двічі поспіль:
У цьому випадку доводиться вставляти додаткові події перед вхідним. Інакше схему взагалі не можна побудувати. Робиться це найщаднішим чином. Виправляється так:
При цьому:
Сигнали a, b, c оголошуються псевдовхідними, тобто вводиться заборона на вставку додаткових подій перед ними. Далі можна працювати з поведінкою як описано вище, при цьому сигнал n взагалі можна вивести з розгляду.
2 клас - вибір залежно від порядку перемикання двох вхідних сигналів:
Тут я забігаю вперед, оскільки обмеження на використання вибору ще не знято. Сенс коригування в тому, щоб отримати поведінку з простим вибором, залежно від того, який з двох псевдовхідних сигналів переключиться (h або g).
Сигнали e, j, i, h, f, k, g оголошуються псевдовхідними. Сигнали a, b можна прибрати з розгляду. Більш складна корекція у верхній гілці обумовлена порядком перемикань a- і b-. Якщо у верхній гілці їх поміняти місцями, то рішення буде таке ж як у нижній гілці.
3 клас - вибір за рівнем. Вибір робиться в момент перемикання вхідного сигналу a + залежно від значення вхідного сигналу b, що встановився до цього моменту.
Мета корекції така ж, як у попередньому випадку.
Сигнали g, h, f, j оголошуються псевдовхідними. Сигнали a, b, g далі можна не розглядати. Вибір тепер визначається подіями h + і j +. Як видно тут навіть немає порушення спід-індепендент.
Тепер знімемо обмеження 5, введемо кратні сигнали.
Для нейтралізації кратного сигналу x введемо додаткові сигнали.
Сигнали x, b, g оголошуються псевдовхідними. Сигнал x далі може не розглядатися.
Скасуємо обмеження 2, введемо паралелізм. З паралелізмом пов'язані наступні проблеми.
1. Потрібно забезпечити синхронізацію паралельних гілок.
Сигнали f, g оголошуються псевдовхідними.
2. Подія a + не може бути причиною події b-, якщо події a- і b + паралельні.
Крім перерахованих вище проблем паралелізм не перешкоджає декомпозиції.
Нарешті, скасуємо обмеження 1, введемо вибір.
Для зручності будемо розглядати поведінку без паралелізму. А вибір здійснюється залежно від перемикання одного з двох вхідних сигналів. Поведінку будемо представляти у вигляді орієнтованого графа, де вершини - точки вибору, дуги - послідовні перемикання сигналів. У кожній вершині рівно по дві вихідні дуги.
Метод синтезу полягає в послідовному подрібненні вихідної поведінки з вибором до отримання декількох окремих поведінок без вибору.
Визначимо поняття: безліч досяжних дуг з дуги N. Це всі дуги через які проходять всі можливі шляхи з дуги N. При цьому точка вибору, з якої виходить дуга N, є останньою для кожного шляху.
Наприклад: для дуги 4 безліч досяжних дуг - {4, 5, 6, 1, 2}. Для дуги 3 - {3, 1, 2}. Алгоритм синтезу такий. Для кожної точки вибору, для обох її вихідних дуг шукаємо безлічі досяжних дуг.
1. Якщо знайдеться точка вибору, для якої безлічі досяжних дуг не перетинаються. За цією точкою можна розділити поведінку на окремі частини. Для цього ізолюємо сигнали, які перемикаються в обох частинах.
Сигнали x, c, d тепер псевдовхідні. Сигнал x далі не розглядаємо. Тепер в обох частинах немає загальних сигналів. Взаємодія між частинами здійснюється за допомогою вхідних і псевдовхідних сигналів. Кожну таку частину можна розглядати як окрему поведінку. При цьому кількість точок вибору порівняно з вихідною поведінкою зменшилася як мінімум на 1.
2. Якщо для всіх точок вибору безлічі досяжних дуг перетинаються, але знайдеться точка вибору, де ці безлічі не збігаються. За цією точкою поведінку можна розділити на дві частини, але більш складним чином.
Поділ проходить за точкою вибору з вихідними дугами 4 і 3. В іншому все теж: ізоляція загальних сигналів і поділ на дві окремі поведінки з меншою кількістю точок вибору.
3. Якщо для всіх точок вибору безлічі досяжних дуг збігаються. Беремо будь-яку дугу і ізолюємо всі сигнали які перемикаються в ній непарне число разів.
Сигнали x, y, c, d тепер псевдовхідні. Після цього ізолюємо кратні сигнали. У обраній дузі залишилися тільки сигнали, які перемикаються тільки в цій дузі (по два рази). Таку дугу можна розглядати як повноцінну циклічну поведінку. З вихідної поведінки ця дуга вилучається, так що кількість точок вибору зменшується на 1.
Таким чином поведінка з вибором поступово дробиться до поведінок без вибору.
Описаний вище метод не є штучним, придуманим. Хоча синтез схем на двовходових елементах здається екстремальним, насправді він простий в тому сенсі, що до межі звужує простір можливих рішень. Наприклад, ізоляція кратних сигналів потрібна не для декомпозиції, і не для дроблення поведінок з вибором. Ізоляція потрібна сама по собі. Без неї неможливо вбудувати кратні сигнали в двовходову схему. А вже якщо доводиться робити ізоляцію, то абсолютно безглуздо відмовлятися від декомпозиції і від дроблення поведінок з вибором.
Всі описані проблеми властиві і синтезу в довільній елементній базі. Тільки вирішення цих проблем зазвичай носить випадковий, не явний характер. І як наслідок цього вони надлишкові. Наприклад, я порівнював свої рішення з бенчмарками Petrify. Мої рішення в 1.5 рази менше. І це при тому, що Petrify дозволяє собі такі вольності, як використання нестандартних елементів (C-елемент), використання елементів з дворівневою логікою, набагато менше обмеження за кількістю входів елемента, обмеження щодо затримок при використанні вхідних інверторів.







