Асинхронна логіка

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Асинхронна логіка — різновид взаємодії логічних елементів цифрових пристроїв. Відрізняється від синхронної тим, що її елементи діють асинхронно в часі, не підкоряючись глобальному генератору тактових імпульсів.

Принцип самосинхронності[ред.ред. код]

Термін «самосинхронна» «аперіодична» схемотехніка підкреслює відміну від двох традиційних схемотехнічних підходів: синхронного та асинхронного. Перший, який є основним в обчислювальній техніці, пов'язаний з використанням механізму тактування, що задається синхронізуючим пристроєм (таймером, годинником) і застосовуваного для узгодження роботи пристроїв у часі. Другий підхід знайшов застосування лише в тих системах дискретної автоматики, де синхронізація не використовується. Синхронні схеми мають ряд переваг, головним з яких є відносна простота у порівнянні з асинхронними, в яких відсутність тактового генератора пов'язана з необхідністю введення надмірності для боротьби з аномаліями їх динамічної поведінки (змаганнями, ризиком). Використання асинхронного підходу не дає збільшення швидкодії, оскільки відсутність відліків часу трансформується у вимогу дотримання часових інтервалів між подачею сусідніх вхідних впливів.
Альтернативою традиційним підходам є самосинхронна схемотехніка. При реалізації самосинхронного підходу годинник в схемі замінюється механізмом індикації, який не відраховує абсолютне час, а фіксує ті моменти часу, коли в схемі закінчилися перехідні процеси, викликані зміною вхідного впливу. Моменти видачі сигналів індикації визначаються величинами реальних затримок, які залежать від умов функціонування елементів схеми і можуть змінюватись від нуля до будь-якої кінцевої величини, що робить самосинхронні схеми стійкими до часової нестабільності елементів.
У синхронних і асинхронних схемах величина такту повинна вибиратися виходячи з максимальних величин затримок елементів, і в разі перевищення розрахункового такту в реальній схемі правильність функціонування схеми порушується. Таким чином, традиційні концепції стають безглуздими, якщо граничні значення величини затримок апріорі невідомі. Для самосинхронних схем знання величин відхилень в життєвому циклі схеми не потрібно: схема гарантовано правильно функціонує інваріантно до часових параметрів елементів. При цьому вимога фізичної наявності індикатора в самосинхронній схемі не обов'язкова. Роль індикатора можуть виконувати спеціальні самосинхронні коди, наявність або відсутність яких на виході схеми несе для з'єднаних з нею пристроїв інформацію про завершення в ній перехідних процесів. Самосинхронні схеми нагадують синхронні тим, що вони можуть мати виділену в явному вигляді пару керуючих сигналів: запит (аналог тактового сигналу, який видається після установки інформаційних входів) і відповідь, який квитує (підтверджує) отримання запиту. При такому поданні перехідний процес в схемі щодо пари керуючих сигналів моделюється елементом затримки. Самосинхронні схеми мають переваги і недоліки в порівнянні з традиційними схемами.

Синоніми[ред.ред. код]

У літературі зустрічаються наступні синоніми поняття «самосинхронні схеми»:

  • самосинхронні (self-timed) схеми;
  • схеми, які не залежать від швидкості (speed-independent circuits);
  • схеми, які не залежать від затримок елементів, схеми, нечутливі до затримок (delay-insensitive circuits);
  • аперіодичні (dead-beat) схеми ;
  • напівмодулярні (semimodular) схеми ;
  • схеми Маллера (Muller's circuits).

У тлумаченнях цих базових понять є деякі відмінності. Найчастіше їх використовують для найменування тих класів «чистих» схем, які правильно функціонують в припущенні про будь-які кінцеві величини затримок елементів і їх варіацій.

Основне завдання аперіодичної схемотехніки формулюється так. Здається специфікація, моделююча в певному сенсі деякий реальний процес. Ця специфікація аналізується з метою виявлення деяких як корисних, так і аномальних властивостей процесу. Потім специфікація модифікується з метою парирування аномалій, і за новим поданням (шляхом використання формальних або евристичних процедур) конструюється (синтезується) схема, поведінка якої збігається з необхідною специфікацією. Для отримання нової якості схем потрібні як відмінні від традиційних моделі (динамічного типу з можливістю відображення паралелізму), так і альтернативні методи аналізу і синтезу.

Коротка історія[ред.ред. код]

Теоретичною базою схемотехніки, як і обчислювальної техніки, є теорія автоматів, де в якості структурної моделі асинхронного автомата панівне місце займає модель Хаффмена [Huffman, 1954; Варшавський, 1976]. Двома роками пізніше Д. Є. Маллер, американський фахівець з теорії автоматів з Іллінойського університету, разом зі своїм колегою У. С. Бартків опублікував звіт, в якому вперше було намічено новий напрямок, пов'язаний з розробкою схем, поведінка яких не залежить від швидкості елементів . Ця основоположна робота, на жаль, майже не зустріла відповідної реакції фахівців. Багато пізніше Р. Є. Міллер [Міллер, 1971] намагався звернути увагу читачів своєї книги на маллеровський підхід, але успіху не досяг, оскільки надмірне захоплення теоретичними аспектами моделі відштовхнуло практиків, які не побачили ніяких образотворчих схемних рішень. Самого Маллера між тим хвилювали не тільки фундаментальні питання: він намагався втілити свої думки в рамках створення обчислювальної системи ILLIAC II, для чого потрібна розробка програмного забезпечення аналізу асинхронних схем на напівмодулярність (що рівносильно перевірці їх на приналежність класу аперіодичних) і відповідної елементної бази. Однак ця спроба закінчилася невдачею через недостатній рівень технологічної бази того часу (навісні елементи), слабким опрацюванням схемотехніки базових вузлів комп'ютера. Мала ефективність запропонованих в той час схемних рішень звела нанівець очікуване збільшення швидкодії самосинхронних схем, що випливає з організації їх роботи за реальних затримок елементів. Правда, деякі теоретики [Ангер, 1977; Фрідман та ін, 1978] звернули увагу на специфічний запит-відповідь режим функціонування схем Маллера.
У 60-і роки спостерігалося становлення нової наукової дисципліни - теорії мереж Петрі, що отримала назву по імені німецького вченого Карла Адама Петрі, який запропонував у 1962 р. нову модель інформаційних потоків в системах. Висунута ним ідея була розвинена в США та інших країнах [Пітерсон, 1984; Котов, 1984; Розенблюм, 1983]. Такі достоїнства нової моделі, як можливість відображення асинхронності та паралелізму, недетермінованості процесів, динаміки їх функціонування, простий синтаксис і наочність моделі в поєднанні з досить широкими функціональними можливостями, з'явилися причиною її популярності. Теорія мереж Петрі розвивалася самостійно, але тим не менше вона може розглядатися не тільки як автономна область науки, але і як гілка теорії автоматів в її широкому розумінні, що займає раніше не досліджену нішу між кінцевими автоматами і машинами Тьюрінга. Переважна частина робіт по мережах Петрі «обслуговує» проблематику загальної теорії систем та паралельного програмування, але частина питань теорії мереж Петрі, пов'язаних з виділенням підкласу живих і безпечних мереж і їх дослідженнями, близька до концепції самосинхронізації, причому безсумнівною перевагою мережевого підходу є можливість переходу від мережі із зазначеного підкласу до самосинхронної схемою в обхід процедури кодування.
Розробки Дж. Денніса [Dennis, 1970] і його колег по проекту МАС в частині створення машин, керованих потоками даних, також концептуально близькі до проблематики самосинхронних схем, але особливих успіхів в схемотехнічній частині, наскільки з'ясувалося, досягнуто не було.
У 1972 р. вивчення асинхронних тригерних схем наштовхнуло проф. В. І. Варшавського на думку про примусове розщеплення перехідного процесу в таких схемах на дві фази з метою фіксації закінчення перехідних процесів в кожній фазі. Роботу [Варшавський, 1976] слід вважати першою в світі монографією з проблеми самосинхронізації. Основний наголос в ній робився на створенні аперіодичної схемотехніки, що принципово відрізняло підхід авторів книги від підходу попередників, наприклад, описаного в [Cavarroc et al., 1974]. Фізичне моделювання на рівні макетів обчислювальних пристроїв на елементах малого ступеня інтеграції підтвердило наявність позитивних ефектів самосинхронної реалізації - підвищення швидкодії за рахунок роботи з реальними затримками елементів у 1,5-2 рази в порівнянні з синхронним варіантом, а також додатковий ефект - збільшення стабільності схем при варіації напруги живлення і зміни умов їх функціонування.
Найважливішим результатом, отриманим в наступному десятилітті [Варшавський, 1986], було встановлення властивості повної самоперевірки самосинхронних схем щодо константних несправностей елементів. Цей результат суттєвий з трьох точок зору: самосинхронні схеми «безпечні» в тому сенсі, що їх функціонування припиняється при виникненні несправності і виключається можливість виникнення помилкових подій; несправності самосинхронних схем можуть бути просто локалізовані при зіставленні значення вихідного сигналу із зразком; сигнал несправності може бути використаний для організації саморемонту; самоперевірність використовується як засіб функціонального діагностування.

Інтегральні схеми[ред.ред. код]

В кінці 70-х років з'явилися великомасштабні програми по створенню великих, надвеликих і ваферних інтегральних схем - ВІС, НВІС. Професора Ч. Сейц [Seitz, 1980] і Дж. Денніс [Bryant, 1980] висунули тезу про те, що синхронний підхід не в змозі гарантувати отримання працездатних НВІС в умовах субмікронної технології. Справа в тому, що в міру зменшення розмірів вентилів, підвищення швидкодії, збільшення площі та «насиченості» мікросхем більш гостро проявляють себе технологічні проблеми, пов'язані із забезпеченням прийнятного відсотка виходу придатних, розсіюванням потужності і істотним підвищенням величини затримок проводів щодо затримок вентилів. Ці проблеми нерозривно пов'язані з труднощами, обумовленими складністю проектування і тестування НВІС, особливо замовних, а також з організацією міжмодульних зв'язків і синхронізації. Самосинхронний підхід дозволяє полегшити проектування топології схем і уникнути необхідності генерації вичерпних тестів.
Проблема організації зв'язків і взаємодії модулів включає в себе як структурний, так і часовий аспекти. Перший пов'язаний з тим, що в процесорних структурах з високим ступенем інтеграції та паралелізму обмін сигналами неефективний з точки зору витрат площі, часу і потужності. Тому обмін намагаються звести до локальних взаємодій (систолічний та хвилефронтовий масиви) між сусідніми модулями. Другий аспект пов'язаний з синхронізацією і відображає тенденцію до зміни ролей між затримками проводів і вентилів (особливо при провідникових з'єднаннях в дифузійному та полікремнієвому шарах). Підвищення відносної затримки провідників уповільнює роботу синхронізатора, що розподіляє синхросигнали по всій системі, так як частота такту повинна бути знижена для компенсації перекосу локальних синхросигналів. Існує спроба паліативного вирішення цієї проблеми шляхом розбиття площі НВІС на так звані зони [Seitz, 1980], в межах яких є локальні тактові генератори. Однак така спроба наштовхується на проблему усунення арбітражних аномалій і синхронізаційних збоїв [Варшавський, 1986], що виникають при незалежному тактуванню зон.
Досвід проектування самосинхронних структур продемонстрував одночасно переваги і недоліки канонічного підходу. Пофрагментна трансляція специфікацій в модульні реалізації, збільшуючи швидкість і зменшуючи трудомісткість конструювання, обертається витратами в числі необхідних елементів. Тому реально проектування, особливо на рівні базисних вузлів (осередків бібліотеки модулів), вимагає винахідництва. Поєднання неформальних кроків з формальними прийомами пов'язано з психологічними навантаженнями дизайнерів, які сильно зростають при перенавчанні з метою освоєння методології самосинхронного підходу. Мабуть не можна буде повністю відмовитися від традиційних видів схемотехніки на користь самосинхронної. Цими міркуваннями можна пояснити виникнення напрямків, проміжних між старими і новими. Відповідно до паліативних (квазісамосинхронних) підходів пристрій на деякому рівні не обов'язково має бути самосинхронним (наприклад, він може мати локальне тактування), але композиція таких пристроїв повинна вести себе за встановленими правилами, тобто на наступному (верхньому) ієрархічному рівні система зобов'язана бути строго самосинхронною. Рівень «чистоти» самосинхронності визначається уявленнями проектувальника.
Така ідеологія має під собою й іншу аргументацію. Наприклад, більшість наявних стандартних протоколів інформаційного обміну інтерфейсів (як стандартних, так і нових перспективних типів, орієнтованих на обмін типу «handshaking», природного для концепції самосинхронізації) містять часові функції, пов'язані з виходом із режимів по таймеру, бродкатінгом, арбітражем, компенсацією перекосів і т. д. Навіть «чиста» самосинхронність не вирішує всіх проблем синхронізації для інтерфейсу, тому квазісамосинхронний підхід виявляється більш адекватним - важливо лише компенсувати власні помилки апаратної реалізації.
Враховуючи всі перелічені проблеми, які диктуються практикою проектування НВІС, були зроблені суттєві спроби нового осмислення теорії самосинхронізації. Перш за все необхідно відзначити нові підходи до визначення того, що таке самосинхронна система.

Самосинхронна система[ред.ред. код]

Самосинхронна система визначається [Seitz, 1980] як самосинхронний елемент або «допустима» композиція самосинхронних елементів. Це рекурсивне визначення на абстрактному рівні не викликає сумнівів, але з конструктивної точки зору мало що дає, оскільки поняття допустимої композиції може тлумачитися довільно. Змістовно самосинхронні схеми можна тлумачити як композицію самосинхронних модулів, які взаємодіють через асинхронні протоколи. Проте основна складність у визначенні поняття «допустимість»; воно завжди залежить від рівня деталізації моделі.
У роботах групи Варшавського зазначається, що незалежність від затримок і тому самоперевірність на рівні логічних елементів не означає наявності таких властивостей на рівні транзисторів і провідникових затримок. Таким чином, слід говорити не про абсолютну самосинхронність, а обумовлювати заданий її рівень. Зважаючи на велику складність проектів на рівні НВІС по-новому ставиться теоретичне питання про синтез. Все більша увага приділяється розвитку методів блочного синтезу, в результаті яких допустимість (чи коректність) з'єднання самосинхронних елементів забезпечується з побудови так званої автокорректної реалізації [Варшавський та ін, 1988], яка здійснюється поблочною трансляцією елементів вихідної специфікації в самосинхронні схемні «шаблони». Однак при цьому повинна бути забезпечена перевірка коректності вихідної формальної специфікації по синтаксису і семантиці. Поряд з дослідженнями в області традиційних для теорії самосинхронізації формалізмів намітилася тенденція до «аналізу» інших адекватних формалізмів. Останні можна розділити на наступні категорії:

Теоретико-Графові моделі глобального і подієвого типу[ред.ред. код]

Прикладами моделей першого типу є: сигнальні графи [Варшавський, 1986], діаграми змін [Варшавський та ін, 1981], а також моделі, пов'язані з паралельними граф-схемами алгоритмів (РСА) та ін. Принципи побудови цих моделей однотипні: вершинам подій ставляться у відповідність зміни стану керуючих та інформаційних змінних, а локальні відносини між парами окремих вершин ставляться у відповідність того чи іншого класу причинно-наслідкових зв'язків між подіями в самосинхронній системі. Так, аналіз та приведення до напівмодулярності мережі Петрі пов'язані з необхідністю побудови графа досяжних маркувань схеми і подальших трудомістких (експоненціальних по складності) маніпуляцій з ними.
Клас схем, представимих за допомогою сигнальних графів, - не всеосяжний, зате складність їх аналізу при деяких підходах може бути доведена до поліноміальної, до того ж схеми, як правило, виходять простішими.

Характеристика[ред.ред. код]

Асинхронна логіка являє собою свого роду симбіоз комбінаційної логіки і асинхронної секвенційної логіки. У теорії цифрових пристроїв асинхронна логіка відрізняється від синхронної тим, що її пропозиційні елементи діють асинхронно в часі, не підкоряючись загальному регулятору, або датчику часу. Це означає, що кожен вхід модельованого цифрового пристрою керується своїм власним часом, своїм генератором тактових імпульсів. Асинхронна логіка є розділом дискретної математики, і може розглядатися як прикладна дисципліна математичної логіки. Математичним апаратом асинхронної логіки служить Булева алгебра, яка доповнюється алгебраїчними інструментами асинхронної секвенційної логіки - вен'юнкціею і секвенцією.

Математичні інструменти[ред.ред. код]

1. Вен'юнкція - це логіко-динамічна операція (знак ) над двома пропозиційними змінними:

  якщо   на тлі
якщо або або

2. Секвенція - це послідовність пропозиційних змінних (обрамлення ), яка, будучи двійковою функцією, приймає одиничне значення при такій черговості перемикань:

В інших випадках секвенційна функція дорівнює нулю.

Формули асинхронної логіки[ред.ред. код]

Формули асинхронної логіки - це аналітичні вирази, в яких пропозиційні змінні з'єднані булевими операціями кон'юнкції, диз'юнкції і заперечення з участю логіко-динамічної операції вен'юнкція. Крім того, поряд з двійковими змінними, в формулах можуть бути присутніми секвенції. Перетворення формул асинхронної логіки підпорядковані певним правилам.

Закони вен'юнкціі[ред.ред. код]

1. Заперечення вен'юнкціі:

2. Поєднання вен'юнкціі з кон'юнкцією:

3. Поєднання вен'юнкціі з диз'юнкцією:

  4. Зв'язок вен'юнкції з секвенцією:

Перетворення секвенцій[ред.ред. код]

1. Асоціативність:

2. Обнулення:

3. Поглинання:

4. Розщеплення:

5. Склеювання (за умови ):

6. Декомпозиція:

7. Зв'язок з кон'юнкцією (кон'юнктівной розкладання секвенції):

8. Зв'язок з вен'юнкціей (вен'юнктівное розкладання секвенції):

Тригерна функція[ред.ред. код]

Тригерної називається функція-шаблон, відповідно до якої реалізуються асинхронні парафазного пристрої тригерній типу. Це секвенційного функція двох змінних, яка надається у вигляді двох рівнянь:

Аргументи X та Y повинні задовольняти наступним співвідношенням:

Перспективи[ред.ред. код]

Самосинхронна схемотехніка може виявитися перспективним напрямком у розвитку обчислювальної техніки і, отже, апаратних засобів підтримки інтелектуальних систем. На користь цієї гіпотези - безліч різноманітних факторів, проти, мабуть, тільки один: необхідність подолання психологічного відторгнення концепції, не дуже знайомій більшості проектувальників і досить складною у порівнянні з загальноприйнятою. Можна очікувати, що після створення ефективних САПР з'являться вироби, відповідні новинкам теоретичних досліджень в області самосинхронізації, і виникнуть ринкові тенденції, стимулюючі масовий випуск самосинхронної техніки. Що стосується найближчої перспективи, то напрямки фундаментальних досліджень більш-менш зрозумілі:
1) продовження поглиблення теорії самосинхронних схем для побудови результатів по лінії забезпечення завдань САПР;
2) перехід на вирішення завдань сннтеза самосинхронних схем з рівня функціональних елементів на рівень транзнсторов для різних інтегральних технологій;
З) вирішення завдань підвищення рівня виходу придатних вафер-ІС за рахунок введення надмірності, механізмів локалізації несправностей та організації саморемонта для парирування технологічних дефектів;
4) формування більш чітких критеріїв визначення самосинхронних структур, у відсутність яких утруднена оцінка результатів і реалізації: з точки зору «чистої» теорії більшість випущених схем, оголошених творцями самосинхронними, не належать до класу незалежних від швидкості, а отже, не володіють частиною корисних властивостей , з яких найбільш значним є самоперевірність.
Використовувані при реалізації самосинхронних схем моделі (мережі Петрі, сигнальні графи тощо) можуть з успіхом застосовуватися при вирішенні багатьох завдань створення інтелектуальних систем. Так, мережі Петрі служать адекватним засобом опису і аналізу продукційних і мережевих моделей, дедуктивного виведення і т. п. [Вагін та ін, 1987].

Див. також[ред.ред. код]

Література[ред.ред. код]

  • В. І. Варшавський, В. Б. Мараховський, Л. Я. Розенблюм і А. В. Яковлєв, § 4.3 аперіодичного схемотехніка, в кн. Штучний інтелект, т.3: Програмні та апаратні засоби. Під ред. В. Н. Захарова і В. Ф. Хорошевського. М.: Радіо і зв'язок, 1990.
  • J. B. Dennis, "Modular asynchronous control structures for a high performance processor," Project MAC conference on concurrent systems and parallel computation, 1970, pp. 55-80.
  • M. Rem, "Mathematical aspects of VLSI design," Caltech conference on VLSI, 1979, pp. 55-63.
  • G. V. Bochman, "Hardware specification with temporal logic: an example," IEEE Trans. on Computers, 1982, Vol. C-31, № 43, pp. 223-231.
  • Y. Malachi and S. S. Owicki, "Temporal specification of self-timed systems," CMU conference on VLSI Systems and Computations, 1981, pp. 203-212.
  • Васюкевіч В. О. Вен'юнкція - логіко-динамічна операція. Визначення, реалізація, додатки. / / Автоматика і обчислювальна техніка, 1984, № 6, стор 73-78.
  • Васюкевіч В. О. Елементи асинхронної логіки. Вен'юнкція і секвенція. - 2009. - 123 с. - URL: http://asynlog.balticom.lv/Content/Files/ru.pdf.
  • Васюкевіч В. О. Аналітика тригерних функцій / / Автоматика і обчислювальна техніка, 2009, № 4, стор 21-29, ISSN 0132-4160.

Посилання[ред.ред. код]

Шаблон:Вікіфіціровать