Схема, квазинечувствительная к задержке

В цифровой логики проектировании схема квазинечувствительна асинхронная к задержке (QDI), когда она работает правильно, независимо от задержки затвора и провода, с самым слабым исключением, необходимым для того, чтобы быть полной по Тьюрингу .

Обзор

Плюсы

• Устойчивость к изменениям обработки , колебаниям температуры, перепроектированию схемы и переназначению FPGA.
• Естественная последовательность событий упрощает работу сложных схем управления.
• Автоматическое стробирование тактовой частоты и время цикла, зависящее от вычислений, могут сэкономить динамическую мощность и повысить пропускную способность за счет оптимизации характеристик рабочей нагрузки в среднем случае, а не в худшем случае.

Минусы

• Кодировки , нечувствительные к задержке, обычно требуют вдвое больше проводов для одних и тех же данных.
• Протоколы связи и кодировки обычно требуют вдвое больше устройств для той же функциональности.

Чипсы

Схемы QDI использовались для производства большого количества исследовательских микросхем, небольшая часть которых приведена ниже.

• Асинхронный микропроцессор Калифорнийского технологического института и клон MIPS R3000
• TITAC Токийского университета и ТИТАК-2 процессоры

Теория

QDI Конвейерная схема

QDI конвейера Система правил событий

Простейшая схема QDI представляет собой кольцевой генератор , реализованный с использованием цикла инверторов . Каждый вентиль управляет двумя событиями на своем выходном узле. Либо повышающая сеть управляет напряжением узла от GND до Vdd, либо понижающая сеть от VDD до GND. это дает кольцевому генератору Всего шесть событий.

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

Если известно, что циклы взаимоисключающие , то их можно соединить с помощью комбинационной логики ( И , ИЛИ ). Это позволяет активному циклу продолжаться независимо от неактивных циклов и обычно используется для реализации , нечувствительного к задержке кодирования .

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

Стабильность и невмешательство

Правильная работа схемы QDI требует, чтобы события ограничивались монотонными цифровыми переходами. Нестабильность ( сбой ) или помехи ( короткое замыкание ) могут перевести систему в недопустимые состояния, что приведет к неверным/нестабильным результатам, тупиковой ситуации и повреждению схемы. Описанная ранее циклическая структура, обеспечивающая стабильность, называется подтверждением . Переход T1 признает еще один T2 если существует причинно-следственная последовательность событий T1 к T2 это предотвращает T2 от возникновения до T1 завершилось. Для схемы DI каждый переход должен подтверждать каждый вход связанного с ним вентиля. Для схемы QDI есть несколько исключений, в которых свойство стабильности поддерживается с использованием предположений о синхронизации, гарантированных ограничениями компоновки, а не причинно-следственной связью.

Предположение изохронной вилки

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

Фактически, каждый вентиль КМОП имеет одну или несколько внутренних изохронных вилок между повышающей и понижающей цепями. Сеть с понижением подтверждает только восходящие переходы входов, тогда как сеть с понижением подтверждает только нисходящие переходы.

Предположение о состязательном пути

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

Предположение о времени полупериода

Это предположение еще больше ослабляет требования к QDI в стремлении к повышению производительности. С -элемент фактически представляет собой три вентиля: логику, драйвер и обратную связь, и не является инвертирующим. Это становится громоздким и дорогим, если требуется большой объем логики. Теорема подтверждения гласит, что водитель должен подтвердить логику. Предположение о времени полупериода предполагает, что драйвер и обратная связь стабилизируются до того, как входы логики смогут переключиться. Это позволяет разработчику напрямую использовать выходные данные логики, минуя драйвер и делая более короткие циклы для более высокочастотной обработки.

Ворота атомного комплекса

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

Относительное время

Относительная синхронизация — это основа для создания и реализации произвольных предположений о синхронизации в схемах QDI. Он представляет собой предположение о времени в виде виртуальной дуги причинности для завершения разорванного цикла в графе событий. Это позволяет разработчикам рассуждать о предположениях о синхронизации как о методе реализации схем с более высокой пропускной способностью и энергоэффективностью, систематически жертвуя надежностью.

Представительства

Коммуникационные аппаратные процессы (CHP)

Коммуникационные аппаратные процессы (CHP) — это программная нотация для схем QDI, вдохновленная Тони Хоара и коммуникативными последовательными процессами (CSP) защищенными Эдсгера В. Дейкстры командами . Синтаксис описан ниже в порядке убывания приоритета.

• Пропускать skip ничего не делает. Он просто действует как заполнитель для условий прохождения.
• Назначение без данных a+ устанавливает напряжение узла a в ВДД в то время как a- устанавливает напряжение a к земле.
• Назначение a := e оценивает выражение e затем присваивает полученное значение переменной a.
• Отправлять X!e оценивает выражение e затем отправляет полученное значение по каналу X. X! это отправка без данных.
• Получать X?a не появится действительное значение ждет, пока в канале X затем присваивает это значение переменной a. X? это прием без данных.
• Зонд #X возвращает значение, ожидающее на канале X без выполнения приема.
• Одновременная композиция S * T выполняет фрагменты процесса S и T в то же время.
• Внутренняя параллельная композиция S, T выполняет фрагменты процесса S и T в любом порядке.
• Последовательная композиция S; T выполняет фрагменты процесса S с последующим T.
• Параллельная композиция S || T выполняет фрагменты процесса S и T в любом порядке. Это функционально эквивалентно внутренней параллельной композиции, но с более низким приоритетом.
• Детерминированный отбор [G0 -> S0[]G1 -> S1[]...[]Gn -> Sn] осуществляет выбор, при котором G0,G1,...,Gn являются охранниками , которые представляют собой логические выражения без данных или выражения данных, которые неявно приводятся с использованием проверки достоверности и S0,S1,...,Sn являются фрагментами процесса . Детерминированный выбор ждет, пока один из охранников не выдаст значение Vdd, а затем приступает к выполнению связанного с ним фрагмента процесса . Если два охранника оценивают Vdd в течение одного и того же окна времени, возникает ошибка. [G] это сокращение от [G -> skip] и просто реализует ожидание.
• Недетерминированный отбор [G0 -> S0:G1 -> S1:...:Gn -> Sn] аналогичен детерминированному выбору, за исключением того, что более чем одному охраннику разрешено оценивать Vdd. Выполняется только фрагмент процесса , связанный с первым защитным устройством, оценивающим Vdd.
• Повторение *[G0 -> S0[]G1 -> S1[]...[]Gn -> Sn] или *[G0 -> S0:G1 -> S1:...:Gn -> Sn] аналогично соответствующим операторам выбора, за исключением того, что действие повторяется, пока любой предохранитель оценивается как Vdd. *[S] это сокращение от *[Vdd -> S] и реализует бесконечное повторение.

Расширения рукопожатия (HSE)

Расширения квитирования связи — это подмножество CHP, в котором канальные протоколы расширены до защит и назначений, и разрешены только операторы без данных. Это промежуточное представление для синтеза схем QDI.

Сети Петри (ПН)

Основная статья: сеть Петри

Сеть Петри (PN) — это двудольный граф позиций и переходов, используемый в качестве модели для схем QDI. Переходы в сети Петри представляют собой переходы напряжения в узлах схемы. Места представляют частичные состояния между переходами. Токен внутри места действует как программный счетчик, определяющий текущее состояние системы, и в сети Петри одновременно может существовать несколько токенов. Однако для схем QDI наличие нескольких токенов в одном месте является ошибкой.

Если переход имеет маркеры на каждом входном месте, этот переход включен. Когда переход срабатывает, токены удаляются из входных позиций, а новые токены создаются во всех выходных позициях. Это означает, что переход, имеющий несколько выходных позиций, представляет собой параллельное разделение, а переход с несколькими входными позициями — параллельное слияние. Если место имеет несколько выходных переходов, то может сработать любой из этих переходов. Однако это удалит токен с места и предотвратит срабатывание любого другого перехода. Это эффективно реализует выбор. Таким образом, место с несколькими выходными переходами представляет собой условное разделение, а место с несколькими входными переходами — условное слияние.

Системы правил событий (ER)

Системы правил событий (ER) используют аналогичную нотацию для реализации ограниченного подмножества функций сети Петри, в которых есть переходы и дуги, но нет мест. Это означает, что базовая ER-система не имеет выбора, реализованного с помощью условных разбиений и слияний в сети Петри, а также дизъюнкции, реализуемой с помощью условных слияний. Базовая система скорой помощи также не допускает обратной связи.

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

Системы правил повторяющихся событий (RER) добавляют обратную связь, сворачивая трассу обратно на себя, отмечая точку сгиба галочкой. Расширенные системы правил событий (XER) добавляют дизъюнкцию.

Набор правил производства (PRS)

Основная статья: Производство (информатика)

Производственное правило определяет либо повышающую, либо понижающую сеть вентиля в схеме QDI и следует синтаксису G -> S в котором G является охранником , как описано выше, и S представляет собой одно или несколько присваиваний без данных параллельных , как описано выше. В состояниях, не охваченных защитой, предполагается, что назначенные узлы остаются в своих предыдущих состояниях. Этого можно добиться с помощью статикизатора либо слабой, либо комбинационной обратной связи (показано красным). Самым простым примером является C-элемент , в котором охранники не охватывают состояния, в которых A и B не имеют одинакового значения.

КМОП- НЕ-вентиль A & B -> Out- ~A | ~B -> Out+

КМОП С-элемент со слабой обратной связью A & B -> _O- ~A & ~B -> _O+ _O -> O- ~_O -> O+

КМОП С-элемент с комбинационной обратной связью A & B -> _O- ~A & ~B -> _O+ _O -> O- ~_O -> O+

Синтез

Полубуфер слабого состояния без данных

Re & Lr -> _Rr-
~_Rr -> Rr+

Rr -> Le-

~Re & ~Lr -> _Rr+
_Rr -> Rr-

~Rr -> Le+

Полубуфер предварительной зарядки без данных

en & Lr -> _Rr-
~_Rr -> Rr+

Lr & Rr -> _Lv-
~_Lv -> Lv+
Lv -> Le-
~Le & ~Re -> _en+
_en -> en-

~en -> _Rr+
_Rr -> Rr-

~Lr & ~Rr -> _Lv+
_Lv -> Lv-
~Lv -> Le+
Le & Re -> _en-
~_en -> en+

Существует множество методов построения схем QDI, но в целом их можно разделить на две стратегии.

Формальный синтез

Формальный синтез был введен Аленом Мартином в 1991 году. Этот метод предполагает выполнение последовательных преобразований программы, которые, как доказано, сохраняют корректность программы. Целью этих преобразований является преобразование исходной последовательной программы в параллельный набор взаимодействующих процессов, каждый из которых хорошо соответствует одному этапу конвейера. Возможные преобразования включают в себя:

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

После того как программа разбивается на набор небольших взаимодействующих процессов, она расширяется до расширений рукопожатия (HSE) . Действия канала расширены до составляющих их протоколов, а многобитовые операторы расширены до их схемных реализаций. Затем эти HSE перетасовываются для оптимизации реализации схемы за счет уменьшения количества зависимостей. После принятия решения о перетасовке добавляются переменные состояния для устранения неоднозначности состояний схемы для полного кодирования состояния . Затем для каждого назначения сигнала выводятся минимальные защитные меры, создавая правила продукции. Для этого существует несколько методов, включая усиление защиты , ослабление защиты и другие. На этом этапе производственные правила не обязательно реализуемы КМОП, поэтому пузырьковая перетасовка перемещает инверсии сигналов по схеме, пытаясь добиться этого. Однако успех перетасовки пузыря не гарантирован. Именно здесь в программах автоматического синтеза обычно используются элементы атомного комплекса.

Синтаксически управляемый перевод

Вторая стратегия, синтаксически-ориентированная трансляция , была впервые представлена ​​в 1988 году Стивеном Бернсом. Это ищет более простой подход за счет производительности схемы путем сопоставления каждого синтаксиса CHP с шаблоном схемы, скомпилированным вручную. Синтез схемы QDI с использованием этого метода строго реализует поток управления, заданный программой. Позже это было использовано исследовательскими лабораториями Philips при реализации Tangram. В отличие от подхода Стивена Бернса, использующего шаблоны схем, Танграм сопоставил синтаксис со строгим набором стандартных ячеек, упрощая как компоновку, так и синтез.

Шаблонный синтез

Гибридный подход, предложенный Эндрю Лайнсом в 1998 году, преобразует последовательную спецификацию в параллельную спецификацию, как при формальном синтезе, но затем использует предопределенные шаблоны конвейера для реализации этих параллельных процессов, аналогичных синтаксически-ориентированной трансляции. Линии обрисовали три эффективных логических семейства или перетасовки .

Полубуфер слабого состояния (WCHB)

Полубуфер слабого состояния (WCHB) — это самое простое и быстрое из логических семейств с 10 циклами конвейера перехода (или 6, если использовать предположение о времени полупериода). Однако он также ограничен более простыми вычислениями, поскольку более сложные вычисления, как правило, требуют использования длинных цепочек транзисторов в подтягивающей сети драйвера прямого действия. Более сложные вычисления обычно можно разбить на более простые этапы или выполнить непосредственно с помощью одного из семейств предварительной зарядки. WCHB представляет собой полубуфер, что означает, что конвейер N этапы могут содержать не более N/2 жетоны сразу. Это связано с тем, что сброс запроса на вывод Rr необходимо дождаться сброса входа Lr.

Полубуфер предварительной зарядки (PCHB)

Полубуфер предварительной зарядки (PCHB) использует логику домино для реализации более сложного этапа вычислительного конвейера. Это устраняет проблему длинной подтягивающей сети, но также приводит к изохронному ответвлению входных данных, которое необходимо устранить позже в цикле. Это приводит к тому, что цикл конвейера будет длиться 14 переходов (или 10, если использовать предположение о времени полупериода).

Полный буфер предварительной зарядки (PCFB)

Полные буферы предварительной зарядки (PCFB) очень похожи на PCHB, но корректируют фазу сброса перестановки для реализации полной буферизации. Это означает, что трубопровод N Стадии PCFB могут содержать не более N жетоны сразу. Это связано с тем, что сброс запроса на вывод Rr допускается, чтобы это произошло до сброса входа Lr.

Проверка

Наряду с обычными методами проверки, такими как тестирование, покрытие и т. д., схемы QDI могут быть проверены формально путем обращения формальной процедуры синтеза для получения спецификации CHP из схемы. Затем эту спецификацию ТЭЦ можно сравнить с оригиналом, чтобы доказать ее правильность.

Внешние ссылки

Инструменты

• «Petrify: инструмент для синтеза сетей Петри и асинхронных схем» . Группа UPC/DAC VLSI CAD . Проверено 6 октября 2017 г.
• Фанг, Дэвид. «Набор инструментов для компилятора иерархических асинхронных схем» . Проверено 6 октября 2017 г.
• «Система асинхронного синтеза Бальза» . Гитхаб . Проверено 6 октября 2017 г.
• Манохар, Раджит. «Язык ACT и основные инструменты» . Гитхаб . Проверено 14 февраля 2020 г.
• Бингхэм, Нед (14 февраля 2020 г.). «Симулятор ВШЭ» . Гитхаб . Проверено 14 февраля 2020 г.

Учебники

• Введение в самосинхронные схемы ( «паутина» . , «слайды» . , «видео» . Ютуб . )
• Летняя школа ASYNC 2022 ( «паутина» . )
• Силиконовая подборка в Йельском университете ( «паутина» . )