Цей сайт відвідують люди, які не оскаржуватимуть ту думку, що паралелізм допомагає підвищити продуктивність систем. Тому агітацію за користь паралелізму опускаємо :-). Також не заперечується думка про те, що автоматна технологія дозволяє досить ефективно реалізовувати різні алгоритми.
Строго кажучи, вся цифрова техніка вдає із себе реалізацію теорії цифрових автоматів. Комбінаційні схеми - це цифрові автомати з одним станом. Всі пристрої з пам'яттю - це кінцеві цифрові автомати. Будь-мікроконтролер і мікропроцесор - це цифровий автомат з гігантським числом станів, переходи в якому визначаються зовнішньою програмою. Зрештою, будь-який комп'ютер також представляє з себе цифровий автомат з ще більшим числом станів.
На жаль, на побутових і загальнодоступних мікропроцесорах і мікроконтролерах неможливо реалізувати паралельні алгоритми. У кращому випадку пропонується емуляція паралелізму за рахунок швидкого (для людини) перемикання завдань. Але коли перемикання завдань засноване на пріоритетах, не рідкість зависання комп'ютера при обробці самих високопріоритетних завдань (мій XP, наприклад, вважає, що вставка нового CD - це найважливіше завдання.).
Але потрібно пам'ятати про те, що цифрова техніка не вичерпується микроконтроллерами і тим більше комп'ютерами. Залишаються ще різні схеми, розсипна логіка і програмована логіка (ПЛІС). Використовуючи останню, можна при мінімумі витрат домогтися створення пристрою з будь-якою архітектурою. Отже, використовуючи всілякі FPGA і CPLD, можна створювати паралельні системи.
Як виявилося на сьогоднішній день, немає (вірніше, я не знайшов) точної і вичерпної теорії, що описує процес опису паралельного алгоритму і його синтезу. Є різні способи опису паралельних алгоритмів, але немає чітких методів їх подальшого синтезу. А якщо і є, то це, в основному, всілякі окремі випадки або методи, що вимагають великих апаратних витрат.
Але що ж нам заважає використовувати стару і добру теорію цифрових автоматів для створення паралельних систем? Про це я подумав перед вступом до аспірантури. Подумав - і вирішив зайнятися дослідженням цього питання. Таким чином, в процесі своїх досліджень я займуся наступним: 1) дослідженням існуючої теорії цифрових автоматів, 2) дослідженням способів опису паралельних алгоритмів, 3) з'єднанням 1-го і 2-го і 4) реалізацією вищесказаного в розсипному базисі і на програмованих логічних пристроях .
Послідовний цифровий автомат - фізична поведінка
Те, що зазвичай називається "цифровим автоматом", я буду називати, природно, "послідовним цифровим автоматом". Напрошується абревіатура ПЦА. Але так як я в майбутньому введу "паралельні цифрові автомати" з тим же першим П, послідовні я буду скорочено називати КЦА - "класичні цифрові автомати" (втім, якщо моя теорія стане класикою, доведеться переобозначать :-). ).
Отже, що ж таке найпростіший "цифровий автомат"? Перш за все, це цифровий пристрій. Отже, воно базується на двійковій логіці. Якщо воно базується на двійковій логіці, все пристрій може бути описано булеві функціями - діз'юнкіі кон'юнкція. Дії виконуються над деякими операндами. Значить, цифровий автомат - це пристрій, який обробляє вхідні дані. Таким чином, цифровий автомат може бути описаний таким чином:
Стан a залежить від часу t і поточного значення вхідних впливів x (t).
Інтерес представляє поточний час t. Строго кажучи, воно вимірюється в секундах (точніше, в наносекундах). Використовуючи цей час, ми можемо розмежувати сосденіе стану:
Мал. 3 Перемикання станів
Як видно з рисунку 3 (що, втім, ясно і без малюнка), деякий час t ст цифровий пристрій перебуває в стані a t. Однак потім за час t пер змінюється значення регістра пам'яті. Цей час залежить від часу поширення сигналу всередині схеми і від швидкодії елементів пам'яті і логіки. В цей час автомат знаходиться в практично непередбачуваному стані. Природно, в цей час значення виходів буде непередбачувано.
Але на наше щастя цей проміжок часу дуже малий. Тому їм зазвичай нехтують і умовно вважають нульовим (по крайней мере, його не розглядають при моделюванні схеми).
Отже, якщо ми викреслимо проміжки часу t пер. ми отримаємо набір цілком дискретних станів пристрою. Чи важливо нам буде знати фізичне значення часу? Ні. Тому в розгляд береться якесь умовне час 0, 1, 2, вимірюється в ежиках :-). Втім, при створенні реального пристрою ці "їжачки" враховуються.
В який момент часу відбувається зміна стану пристрою? Зазвичай це деякий зовнішній сигнал. Кажуть, що він "тактирует" роботу пристрою, "синхронізує" зміну його станів (дійсно, зміна станів відбувається синхронно по всьому пристрою). Тому цей сигнал називають "тактом синхроимпульса". Для його реалізації зазвичай роблять генератор прямокутних імпульсів.
Отже, резюмуємо (рис. 4). Цифровий пристрій обробляє вхідні сигнали X за законом f (X) і видає результат Y. При наявності елементів пам'яті змінюється стан пристрою a по закону. Зміна станів ініціюється зовнішнім сигналом c.
Мал. 4 Поведінка цифрового пристрою
Послідовний цифровий автомат - математична модель
Для математичної моделі не підійдуть прямоугольнички, рисочки і крапочки. Там необхідно говорити мовою формул.
Цифровий пристрій, воно ж у нашому випадку цифровий автомат описується поруч множин: безліч вхідних впливів X. безліч вихідних сигналів Y і безліч станів A.
Безліч вхідних впливів - це набір всіляких комбінацій, число яких визначається розрядністю вхідного слова. Всі можливі вхідні слова утворюють вхідний алфавіт. Можливі ситуації (та так воно на практиці, в основному, і відбувається), коли використовується не весь вхідний алфавіт.
Безліч вихідних сигналів визначається тими сигналами, які автомат видає назовні. Ці сигнали також описуються словами, які формують вихідний алфавіт, який також може повністю не використовуватися.
Безліч внутрішніх станів - це набір всіх можливих комбінацій внутрішніх елементів пам'яті. У більшості реальних випадків використовуються не всі можливі комбінації значень елементів пам'яті. Це властивість з успіхом користується для мінімізації рівнянь.
З усіх можливих значень важливо виділити той стан, в яке потрапляє автомат в перший раз. Як правило, включення харчування вводить автомат в якийсь непередбачений стан. Тому вводиться зовнішній сигнал скидання, який переводить автомат в чітко певний стан. Цей стан називається "початковим" і зазвичай позначається a 0 (або a 1 - так більше класично).
Крім цих множин необхідно вказати дві функції - функцію переходів і функцію виходів.
Функцію переходів ми вже проаналізували.
Функція виходів описує значення виходів в залежності від поточного стану і поточних вхідних параметрів:
Однак функція виходів з тим же успіхом може залежати і від попереднього стану. Це залежить від того, в який момент часу сформований вихідний сигнал - до переходу або після. У другому випадку виходить інша функція виходів:
Як нескладно догдадаться, поточний час a (t) може бути виражено через попередній час a (t - 1). У зв'язку з цим в моделі застосовується формула (4).
З формули (4) можливі 4 окремих випадки - 1) автомат залежить від стану і входів, 2) залежить тільки від стану, 3) залежить тільки від входів і 4) взагалі ні від чого не залежить. 3-ий випадок - це комбінаційна логіка. 2-ий випадок отримав назву автомата Мура. 1-ий випадок - автомат Мілі. 4-ий випадок - генератор константи.
Отже, математична модель класичного цифрового автомата описується наступною системою:
У цій множині формула (5.1) описує безліч вхідних слів, (5.2) - безліч вихідних сигналів, (5.3) - безліч станів, (5.4) - початковий стан, (5.5) - функцію переходів, (5.6) - функцію виходів, (5.7 ) - дискретність роботи в часі.
Паралельний цифровий автомат
А тепер спробуємо додати паралелізм в КЦА. Як це можна зробити?
Насамперед заглянемо в математику. Точніше, в систему рівнянь (5). Що там можна поміняти? Або, якщо більш науково, що можна змінити в системі (5) для забезпечення паралелізму і без руйнування цілісності зі збереженням автомата як чорного ящика незмінним? Розшифруємо останню думку :-).
Цифровий автомат як чорний ящик помінятися не повинен. Тобто заміна КЦА на еквівалентну їй ПЦА і навпаки повинна бути зовні непомітною (під "еквівалентність" в даному випадку розуміється виконання тих же самих функцій) - інтерфейс змінюватися не повинен. Отже, безлічі (5.1) і (5.2) не змінюються.
Чи не змінюється концепція ПЦА як цифрового пристрою з безліччю станів. Значить, (5.3) теж не змінюється.
Чи не змінюється концепція дискретної зміни часу - (5.7) не змінюється.
Якщо подумати, паралелізм в даному випадку мається на увазі наявність безлічі активних в даний момент станів на відміну від одного активного у КЦА. Значить, змінюються рівняння (5.4), (5.5) і (5.6), де активно одне стан:
Що означає (6.1)? Це означає, що в початковий момент часу можуть бути активними кілька станів одночасно. (6.2) означає залежність безлічі одночасно активних станів в даний момент часу від безлічі активних в попередній дискретний момент часу і вхідних сигналів. (6.3) означає залежність вихідних значень від безлічі одноврмененно активних станів і вхідних сигналів.
Чи змінює система (6) інтерфейс цифрового автомата? Очевидно, що ні, так як інтерфейс обмежений множинами (5.1) і (5.2).
Зміна станів проводиться одночасно (рівняння (6.2)).
За сигналом зовнішнього скидання автомат переходить в деякий безліч початкових станів (рівняння (6.1)).
Отже, отримана модель ПЦА. Додавання системи (6) в систему (5), а також кілька необхідних переобозначеніе дають нам математичну модель ПЦА:
Символом позначається безліч активних в даний момент станів. Це безліч не може збігатися з усім безліччю станів, що відзначено в (7.4) (якщо б це було так, мова б йшла знову про комбінаційної логіки).
Чи достатньо системи (7) для опису ПЦА? Очевидно, що так.
Втім, це очевидно комп'ютера, який оперує математичними абстракціями. Якщо ж взяти будь-яку задачу (наприклад, www.softcraft.ru/auto/ka/fil/), то відразу ж відчуваєш якесь безсилля - це ж скільки треба паперу списати і байтів зайняти, щоб цими множинами описати роботу пристрою!
Якщо спробувати оперувати діаграмою станів, то теж буде нелегче - діаграма буде абсолютно нечитабельною.
Очевидно, що потрібно вводити спрощення та узагальнення.
Непогано б ввести такі популярні у програмістів процеси і потоки з нитками, буффер обміну, прапори, семафори.
З огляду на це, дану модель я буду називати "абстрактної математичної моделлю". Просто "моделлю" я буду називати таку, яка доступна для людини.
Все це цілком реально :-). Більш того, на момент написання статті вже існувала модель, яка працювала (в рамках середовища моделювання - на більше грошей не вистачило.).
Отже, ми отримали математичну абстракцію, виражену тим чи іншим способом - діаграма станів, матриця, таблиця переходів або ще чого-небудь. Що з цим робити?
Розглянемо процес синтезу для КЦА.
Якщо мова йде про розсипний логіці, то вибираються елементи пам'яті, кодуються стану. Потім за отриманими станів створюється функція переходів і функція виходів. Проводиться спрощення на рівні булевих функцій. Потім купується ціла купа елементів "І", "АБО", "НІ" і тригерів з дешифратором і все це запаюється в невеликого монстрика :-).
На щастя, є більш зручний (але не більше дешевий) спосіб - використовувати програмовані логічні пристрої. Береться одна з мов опису апаратури - Verilog або VHDL (на момент написання статті інших популярних мов ще не було), - описується поведінка пристрої, проводиться тестування і налагодження, синтезується і, нарешті, імплементується. Весь процес займає куди менше часу, ніж попередній.
Все це може бути застосовано і для ПЦА. Виробляються ті ж дії, хіба що значно більше пузатими виходять формули і листинги. Але отриманий код також може бути синтезований і імплементований.
Необхідно відзначити таку деталь. Сучасні ПЛІС розраховані на синтез цифрових автоматів - у них є кілька ліній для синхроимпульса і скидання, які коротше інших ліній, а також безпосередньо підводяться до елементів пам'яті. У зв'язку з цим дещо спрощується синтез таких пристроїв. Це також є для ПЦА.
У даній статті була розглянута абстрактна математична модель ПЦА, яка може бути синтезована. Складність процесу синтезу не вище синтезу КЦА.
Цифровий автомат - звичне поняття для розробника цифрових пристроїв. Отже, використання ПЦА куди більш зрозуміло і просто, ніж використання, наприклад, мереж Петрі.
Плануються подальші статті, де будуть висвітлені наступні дослідження.