vak: (Default)
Довёл я наконец до ума библиотеку асинхронных компонентов для Xilinx FPGA, и затолкал на плату пример вычисления наибольшего общего делителя. В большинстве случаев он даже корректно работает. :) Вводим с переключателей два шестнадцатеричных числа, нажимаем на кнопку, получаем результат. Вот как это выглядит:



Здесь НОД(0x34, 0x27) даёт результат 0xd. В десятичном виде это НОД(52, 39) -> 13.

Но иногда схема врёт. И это ожидаемо, так как для арифметических вычислений я полагаюсь на синтезатор Xilinx Vivado, а он без понятия, что надо генерить "позитивную" логику. Задействовать стандартные примитивы типа CARRY4 нельзя, потому что нарушается монотонность. Получаются вот такие глюки:



Можно видеть, что сигналы out_hidata и out_lodata иногда встают одновременно, и это ошибка. Долдно быть так:



Выход в том, чтобы не доверять арифметические вычисления стандартному синтезатору Verilog, а порождать нужную позитивной логики в структурном виде. Тогда синтезатор уже не сможет ничего испортить.
vak: (Default)
Я наконец доотладил библиотеку асинхронных компонентов, так что заработала схема вычисления наибольшего общего делителя. На рисунке можно видеть, как идёт процесс для НОД(203, 116) -> 29.
  1. Ввод X := 203 и Y := 116
  2. Вычитание X := X - Y = 87
  3. Вычитание Y := Y - X = 29
  4. Вычитание X := X - Y = 58
  5. Вычитание X := X - Y = 29
  6. Вывод Out := 29



Теперь надо прошить эту схему в FPGA и проверить на реальном железе.
vak: (Default)
Обычно под асинхронным триггером понимают так называемую RS-защёлку, состоящую из пары соединённых крест-накрест элементов И-НЕ:



Работа такого триггера описывается таблицей:
/Set  /Reset  Действие
---------------------------
  0     0     Запрещено
  1     0     Q = 0
  0     1     Q = 1
  1     1     Без изменения
Недостаток этой схемы состоит в наличии запрещенного состояния: когда на вход поступают нули, выход оказывается в неопределённом, или хуже того, в метастабильном состоянии.

Между тем, гораздо более удобным оказывается схема, состоящая из элементов И + ИЛИ:



Функционирует эта схема похожим образом, но без неопределённого состояния:
 Set  Enable  Действие
---------------------------
  x     0     Q = 0
  1     1     Q = 1
  0     1     Без изменения
Как можно заметить, защёлка И+ИЛИ работает в "положительной" логике: передний фронт на входе превращается в передний фронт на выходе и наоборот, отрицательный фронт превращается в отрицательный. Комбинируя с другой положительной логикой, можно получить все нужные примитивы для асинхронного дизайна. К примеру, добавив на входах пару элементов И и ИЛИ, получаем известный С-элемент Мюллера.
vak: (Default)
Обнаружил изумительный способ генерить диаграммы сигналов из текстового описания. Диаграмма описывается на языке WaveJSON и выглядит следующим образом:
{ "signal": [
  { "name": "activate.req", "wave": "01........0.",  "node": ".A.........." },
  { "name": "activate.ack", "wave": "0........1.0",  "node": ".........F.." },
  { "name": "out1.req",     "wave": "0.1.0.......",  "node": "..B........." },
  { "name": "out1.ack",     "wave": "0..1.0......",  "node": ".....D......" },
  { "name": "out2.req",     "wave": "0.1....0....",  "node": "..C........." },
  { "name": "out2.ack",     "wave": "0.....1.0...",  "node": "........E..." }
  ],
  "edge": [ "A~B", "A~C", "D~F", "E~F" ]
}
Утилита wavedrom преобразует этот формат в SVG, а дальше посредством inkscape можно делать PNG, EPS или PDF. Вышеприведённый текст превращается в рисунок:



Для интересующихся асинхронной логикой: сей примитив называется Concur и в асинхронном верилоге реализует блок fork...join.

vak: (Default)
В качестве теста возьмём упомянутый наибольший делитель.
module gcd (
input activate,
input [7:0] a,
input [7:0] b,
output [7:0] c
);
reg [7:0] x, y;

always while (activate) begin
fork
x <= a;
y <= b;
join

while select
x > y:
x = x - y;
y > x:
y = y - x;
endselect

c <= x;
end
endmodule
Парсер преобразует исходный текст в следующее синтаксическое дерево:Осталось научиться генерить из этого дерева асинхронную схему.
vak: (Default)
До сих пор мои рассуждения про асинхронную логику носили несколько теоретический характер, но наконец я дозрел до реального примера. Попробуем соорудить схему для вычисления наибольшего общего делителя двух целых чисел. Ограничимся размером в 8 бит, до есть диапазон от 0 до 255. Исходный текст на воображаемом асинхронном диалекте языка Verilog мог бы выглядеть так:
module gcd (
    sync   slave        activate,              
    input  master [7:0] a,
    input  master [7:0] b,
    output master [7:0] c                      
);
    logic [7:0] x, y;

    while (activate) begin
        fork
            x <= a;
            y <= b;
        join

        while select
        x > y:
            x -= y;
        y > x:
            y -= x;
        endselect

        c <= x;
    end
endmodule
Исходный текст преобразуется компилятором в схему, составленную из элементарных асинхронных примитивов:



Результат компиляции на языке SystemVerilog получается следующий:Код и временные диаграммы )
vak: (Default)
"Ученые Технического университета Эйндховена (Нидерланды) создали энергонезависимое органическое электромеханическое устройство, имитирующее поведение синапсов мозга, со всеми их достоинствами и недостатками."

Статья в Nature: "A non-volatile organic electrochemical device as a low-voltage artificial synapse for neuromorphic computing"

"Here we describe an electrochemical neuromorphic organic device (ENODe) operating with a fundamentally different mechanism from existing memristors. ENODe switches at low voltage and energy (<10 pJ for 103 μm2 devices), displays >500 distinct, non-volatile conductance states within a ~1 V range, and achieves high classification accuracy when implemented in neural network simulations. Plastic ENODes are also fabricated on flexible substrates enabling the integration of neuromorphic functionality in stretchable electronic systems. Mechanical flexibility makes ENODes compatible with three-dimensional architectures, opening a path towards extreme interconnectivity comparable to the human brain."

Фактически мы получаем технологию, на которой можно строить асинхронную логику произвольной сложности, вплоть до объёмов человеческого мозга. Об чём я и толкую последний год. Осталось только разработать средства проектировния этой самой асинхронной логики.
vak: (Default)
К вопросу о некремниевой электронике: статья в "Nature" показывает возможность использования молекулы ДНК в качестве "транзистора" с переключаемой проводимостью. Еще один потенциальный потребитель асинхронной логики.

vak: (Default)
С какой максимальной скоростью может работать асинхронный процессор на FPGA? Многие считают, что это в принципе невозможно, а я тем временем решил измерить реальную цифру. Возьмём пустой цикл следующего вида:
    forever
        continue;
Еслибы существовал транслятор с SystemVerilog в асинхронные компоненты, он бы породил такую схему:
                 ,---. out ,---.
    activate ---o| # |----o|run|
                 `---'     `---'
                 Loop     Continue
Примитив Continue я уже упоминал недавно. Loop это компонент, реализующий бесконечный цикл. У него два синхропорта: по ведомому порту он получает сигнал активации, после чего начинает генерить последовательность импульсов на ведущем порту. Реализуется он следующим образом:
    module Loop (sync.slave activate, sync.master out);

        wire req = activate.req & !out.ack;

        BUFR b (.O(out.req), .I(req));

        assign activate.ack = '0;
    endmodule
Работает схема так:



С точки зрения формальной логики буфер BUFR здесь не требуется. Однако без него схема не работает. У семейства Xilinx Artix7 есть три типа подходящых буферов на выбор: BUFG, BUGH и BUFR. Я загрузил прошивку в плату Digilent Basys3 и измерил результат для всех трёх вариантов. Самая высокая частота получается с BUFR, а именно 309 МГц. Это будет верхний предел для скорости асинхронного процессора на данном типе FPGA.
vak: (Default)
В мире асинхронной логики всё не так. Если для традиционной логики основные кубики это триггеры, защёлки, мультиплексоры и т.п., то здесь набор элементарных компонентов совсем другой. Теоретическое обоснование дал математик Кис ван Беркель в книжке "Handshake circuits: an asynchronous architecture for VLSI programming" (есть ранний вариант в виде PDF). Более практичный список асинхронных примитивов можно найти в главе 13 "The Breeze Components" документации по компилятору Balsa.

Принципы построения асинхронных компонентов:
1. Каждый компонент имеет один или несколько портов.
2. Каждый порт состоит из двух направлений: передача и приём.
3. Направление передачи может состоять из нескольких проводов, при этом приём имеет всего один провод. Такой порт называется передающим (output).
4. Направление приёма может состоять из нескольких проводов, при этом передача имеет всего один провод. Такой порт называется принимающим (input).
5. Направление приёма и направление передачи могут иметь по одному проводу. Такой порт называется синхронизирующим (sync или nonput).
6. Порт называется ведущим (master), если сначала становится активным (ненулевым) передающее направление, и затем ожидается ответ на приёмном направлении.
7. Порт называется ведомым (slave), если сначала ожидается ненулевой сигнал на приёмном направлении, и затем формируется ответ на передающем направлении.
8. Компонент обязан подчиняться принципу самоинициализации: когда все входные сигналы всех портов равны нулю (неактивны), все выходные сигналы также обязаны перейти в нулевое состояние.

Таким образом, возможны шесть типов портов: master_output, master_input, slave_output, slave_input, sync_output и sync_input. Используя конструцию interface языка SystemVerilog из предыдущего поста эти шесть типов можно определить следующим образом:
vak: (Default)
Продолжаю постигать азы асинхронной логики. Про сигналы и базовый протокол взаимодействия я уже писал. Но то были теоретические рассуждения, а теперь пора заняться реальным кодом. Для описания асинхронных каналов задействуем конструкцию interface языка SystemVerilog. Будет использовать кодирование dual-rail. Адаптировать для quad-rail или 1-of-N будет нетрудно.

Существует три типа асинхронных каналов: push, pull и nonput. В первом случае активная сторона (мастер) выдаёт данные, а пассивная (slave) отвечает подтверждением:
_______           ______
       |  data   |
Master | ======> | Slave
output |         | input
       |  req    |
_______| <------ |______
Второй вариант - канал типа pull. Здесь мастер выдаёт запрос, а в ответ приходят данные:
_______           ______
       |  req    |
Master | ------> | Slave
input  |         | output
       |  data   |
_______| <====== |______
Каналы push и pull с кодированием dual rail ширины N бит можно описать следующим образом:
vak: (Улыбка)
В микро-БЭСМ в качестве программируемого таймера использовалась микросхема к580ви53. Ну не вопрос, подумал я, это ведь классический Intel 8253. Для него в интернете есть куча исходников на Верилоге, сейчас быстренько привинчу. Не тут-то было. Нашёл три разные реализации i8253 - все оказались кривоватые и не соответствующие реальному чипу. И неспроста: проблема оказалась глубже. Дело в том, что этот чип представляет собой классический пример асинхронного дизайна, забытого в наше время. В микросхеме отсутствует опорный синхросигнал.



Интерфейс к управляющему процессору состоит из сигналов адреса, данных, /CS, /RD, /WR. Здесь не участвуют сигналы CLK. Они влияют только на декремент счётчиков времени, но не на логику внешнго интерфейса. Хитрая задача абитража между осинхронными запросами от процессора и событиями от синхросигналов решается схемотехникой, что нетривиально. Современные средства Verilog-синтеза такое не могут. Приходится признать, что с развитием технологий разработки цифровых микросхем мы кое-что утеряли, а именно способность проектировать асинхронные схемы.

Чтобы сделать i8253 "понятным" для современных Verilog-синтезаторов, достаточно сделать его синхронным, то есть ввести глобальный высокоскоростной сигнал CLK со стороны процессора, и тактировать все остальные события по нему. Хотя это будет уже не совсем i8253, но для проектов типа микро-БЭСМ вполне годится.
vak: (Улыбка)
Почему-то считается, что асинхронную логику нельзя засунуть в традиционную FPGA. Я решил поисследовать этот вопрос. Чем дольше разбираюсь, тем яснее становится, что это просто предубеждение. Я взял популярную плату Digilent Basys3 на основе чипа Xilinx Virtex-7, и стал смотреть, что тут можно сделать.

Основа асинхронной логики - несколько базовых примитивов: C-элемент, арбитр, S-элемент, T-элемент. Все их удалось реализовать на имеющейся FPGA. Вот, к примеру, как выглядит двухвходовый С-элемент Мюллера:


Дальше про трёхвходовый С-элемент, асинхронный арбитр, S-элемент и Т-элемент... )
vak: (Улыбка)
Вначале было слово
Вначале была статья Тони Хоара "Communicating Sequential Processes" 1978 года. Да, сэр Хоар - тот самый, который разработал язык Алгол-60 и получил за это Тьюринговскую премию. В статье он описывает некий вариант языка программирования с концепцией существенного параллелизма. Он не ставил задачу полностью определить язык, так только, набросал несколько идей с высоты своего гения. Насколько я знаю, никто так и не сделал реальный язык програмирования, но математикам идея понравилась, и они часто используют нотацию Хоара в своих статьях для рассуждения о параллельных процессах.

Пример программы в нотации Хоара: решето Эратосфена.
[SIEVE(i:1..100)::
  p,mp:integer;
  SIEVE(i-l)?p;
  print!p;
  mp := p; comment mp is a multiple of p;
 *[m:integer; SIEVE(i-l)?m ->
   *[m > mp -> mp := mp + p];
    [m = mp -> skip
    []m < mp -> SIEVE(i + l)!m
] ]
||SIEVE(0)::print!2; n:integer; n := 3;
    *[n < 10000 -> SIEVE(1)!n; n := n + 2]
||SIEVE(101)::*[n:integer; SIEVE(100)?n -> print!n]
||print::*[(i:0..101) n:integer; SIEVE(0?n --> ...]
]
Гении не ходят в одиночку. В 1985 году в Калифорнийском технологическом институте Алан Мартин обнаружил, что такой язык замечательно преобразуется в асинхронные цифровые схемы. Его статья "Compiling Communicating Processes into Delay-Insensitive VLSI Circuits" стала отправной точкой для многочисленных последователей. Мартин не изобретал язык, его увлекала исключительно возможность построения схем. Но главное - он распахнул дверь в огромную неисследованную область. Забегая вперед, стоит упомянуть, что два года назад Калтех отмечал 25-летие первого в мире асинхронного процессора, созданного под руководством профессора Алана Мартина.

Мощная бронебойная сила подошла в виде голландского математика Kees van Berkel из университета Eindhoven. В своей основополагающей работе 1993 года "Handshake circuits: an asynchronous architecture for VLSI programming" (ранний вариант в виде PDF) он досконально математически исследовал всю область асинхронных цифровых цепей и элементарных составных компонентов. Осталось дело за практиками. По ходу дела ван Беркель доопределил язык, унаследованный от Хоара, и назвал его Tangram. Вот к примеру простейший компонент типа буфер:
(a?W & c!W) · |[ x, y: var W | a?x; #[(a?y || c!x); (a?x || c!y)] ]|
Он преобразуется в следующую схему:


Идею Танграма подхватила фирма Philips. В недрах её исследовательского отделения была разработана коммерческая реализация тулчейна, а в 2003 отпочкована в виде отдельной фирмы. Первым продуктом компании был асинхронный процессор 80с51. В 2006 году был разработан асинхронный процессор с архитектурой ARM. По слухам, большинство чипованных кредитных карт и биометрических паспортов в мире сделано на процессорах этой фирмы. По каким-то причинам в 2009 году Филипс решил закрыть этот бизнес. Фирма Handshake Solutions внезапно канула в небытие вместе со всем софтом.

Но технология не умерла, нет: на помощь пришли британцы. С конца 90-х в университет Манчестера разрабатывался альтернативный вариант реализации идей ван Беркеля: упомянутый в предыдущем посте язык Balsa. Хотя работа и остановилась несколько лет назад, исходные тексты вполне доступны. Имеется описание языка и софта. Язык сильно ушёл от Хоара и стал вполне читабельным. Показанный выше буфер на Бальсе выглядит так:
type word is 8 bits

procedure buffer (input a: word; output c: word) is
local
    variable x, y: word
begin
    a -> x;
    loop
        a -> y || c <- x;
        a -> x || c <- y
    end
end
vak: (Улыбка)
В поисках неортодоксальных подходов к разработке хардвера, в частности в области асинхронной логики, я неожиданно для себя открыл интересный язык Balsa, и стоящую за ним методику, называемую 'Handshake Circuits'. Взгляните, вот программа вычисления наибольшего общего делителя на Бальсе:
procedure GCD (
    input x: byte;
    input y: byte;
    output z: byte
) is
local 
    variable a, b: byte
begin
    loop
        x -> a || y -> b;
        loop
            while a /= b then
            begin
                if a > b
                then a := (a - b as byte)
                else b := (b - a as byte)
                end
            end
        end;
        z <- b
    end
end
При компиляции она превращается в такую асинхронную схему:

Дальше она преобразуется в Verilog и синтезируется в собственно микросхему. Разве не прелесть? Не одним верилогом жив человек! :)

Бальса разрабатывалась в 1998-2010 годах в университете Манчестера. Её исходные тексты доступны на сайте университета на условиях лицензии GPL. Подход подробно описан в диссертации Andrew Barsley "Balsa: An Asynchronous Circuit Synthesis System".
vak: (Улыбка)
Столкнулся с необходимостью изобразить на FPGA асинхронный арбитр. Это такая схема, которая определяет, который из двух сигналов поступил раньше. Для ASIC задача решается так:

Выглядит как простая цифровая схема, но на самом деле здесь решается нетривиальная проблема фильтраци метастабильного состояния, аналоговая по своей сути. Об эту тему много копий сломано и научных статей написано. Для FPGA качественного решения не существует. В идеале изготовители FPGA должны бы закладывать в архитектуру чипа некоторое количество модулей-арбитров. Увы, в нынешних чипах от Xilinx и Altera их нет, поэтому приходится измышлять решения "на коленке". Пока думаю обойтись двумя вентилями NAND2, а в качестве фильтра метастабильности задействовать пару MUX7. По идее, всё это должно поместиться в один слайс. Еще можно попробовать вместо NAND2 использовать штатную RS-защелку типа FDCPE. У неё есть асинхронные входы для сброса и установки. Да и время выхода из метастабильного состояния должно получиться поменьше.
vak: (Улыбка)
"Compiling from Haste to CDFG: a front end for an asynchronous circuit synthesis system" (PDF).

Вычисление факториала на языке Haste выглядит следующим образом:
int = type [0..2^32-1] &

fact : main proc (in?chan int & out!chan int).
  begin x,y :var int ff
  |
    forever do
      in ? x
    ; y := 1
    ; do x > 1 then
        y := y * x
      ; x := x - 1
      od
    ; out ! y
  od
end

Эта функция превращается в такую асинхронную схему:


Дальнейшее преобразование в Верилог и синтез делаются элементарно.
vak: (Улыбка)
Главная фишка асинхронного дизайна - отсутствие тактирующего сигнала. Вместо глобального генератора синхроимпульсов используется локальный сигнал подтверждения и четырехфазовый протокол взаимодействия. Есть разные варианты протоколов, подробно описанные в умной книжке. Я здесь коротенько набросаю один их них.



Сигналы данных направлены от передатчика к приёмнику. Обычно один бит данных кодируется двумя сигналами (1-из-2). Иногда два бита кодируются четырьмя сигналами (1-из-4), это имеет свои преимущества.



Фаза 1: исходно сигналы данных равны нуль (состояние NULL). Подтверждение также равно нулю. Инициатива на стороне передатчика. Когда готов, передатчик выставляет один из сигналов данных в единицу (cостояние DATA).

Фаза 2: данные поступили на вход приёмника (cостояние DATA). Приёмник выставляет сигнал подтверждения.

Фаза 3: передатчик получил сигнал подтверждения и переводит сигналы данных обратно в состояние NULL.

Фаза 4: приёмник обнаружил состояние NULL на входе данных и сбрасывает сигнал подтверждения.

Здесь действуют два важных правила. В фазе 1 (когда ack=0) передатчик имеет право формировать на шине данных только положительные фронты. В фазе 3 (когда ack=1) допускаются только отрицательные фронты. При этих условиях синхронизация всегда устойчива, независимо от времени распространения сигнала и задержек на логических элементах.

Я обещал объяснить, почему так важны монотонные булевы функции. Всякие вычисления и прочие преобразования данных выполняются на фазе 1. Сигналы данных проходят через блок комбинационной логики. На вход поступают положительные фронты. Важно, чтобы на выходе тоже появлялись только положительные фронты, иначе собьётся синхронизация. Если комбинационную логику составлять только из монотонных функций, можно гарантировать, что отрицательных фронтов на выходе не будет.
vak: (Улыбка)
Посчитал, теперь у меня есть полный список из 16143 монотонных функций шести аргументов. Прямо комбинаторный взрыв какой-то. Для семи аргументов должно быть 489996795, но я проверять не буду: нет уверенности, что пентиуму для вычислений хватит времени жизни вселенной. :)

Математика - царица наук. Как оказалось, последовательность 1,2,5,20,180,16143 давно известна и сводится к подсчёту количества абстрактных симплициальных комплексов из N неразмеченных элементов. Спасибо [livejournal.com profile] spamsink и [livejournal.com profile] a_shen за подсказку.

Желающие приобщиться к суровой науке могут попытаться прорубить статью, которая всё объясняет.

Почему интересны именно функции с шестью входами? У них есть определённое практическое применение. Дело в том, что в последних семействах микросхем Xilinx FPGA используются именно шестивходовые программируемые матрицы (LUT6).