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).
vak: (Улыбка)
Сколько существует монотонных булевых функций с N аргументами?

Монотонной назовём булеву функцию, значение которой не убывает при росте значения аргументов. Интересуют нетривиальные функции, то есть реально зависящие от аргументов. Варианты, отличающиеся перестановкой аргументов, считаем за один.

Для двух аргументов имеем всего две монотонные функции:
    a | b
    ab

В случае трёх аргументов таких функций уже пять:
    a | b | c
    a | bc
    ab | ac
    ab | ac | bc
    abc

При N=4 получается двадцать функций:
    a | b | c | d
    a | b | cd
    a | bc | bd
    a | bc | bd | cd
    a | bcd
    ab | ac | ad
    ab | ac | ad | bc
    ab | ac | ad | bc | bd
    ab | ac | ad | bc | bd | cd
    ab | ac | ad | bcd
    ab | ac | bcd
    ab | acd
    ab | acd | bcd
    ab | bc | ad
    ab | cd
    abc | abd
    abc | abd | acd
    abc | abd | acd | bcd
    abcd
    ac | bc | ad | bd

Для пяти аргументов я насчитал 180 монотонных функций. Вычисление для шести аргументов всё еще идет и, надеюсь, закончится к утру. (Результат 16143 штук)

Монотонные функции играют важную роль в методике асинхронных цифровых схем. про это напишу позже.

Для наглядности булевы функции можно представлять как N-мерные кубики с углами, раскрашенными в два цвета. К примеру, так выглядит функция f(a, b, c, d) = ab | bc | ad.

vak: (Улыбка)
Так выглядит самый маленький чип из семейства Xilinx Artix-7 (xc7a15ti), заполненный вентилями TH22 на 88%.





У диджилента есть подходящая платка с этим чипом, всего за $75.

Сюда помещается 8150 асинхронных гейтов - больше, чем 4656 в чипе xc3s500e. Но на самом деле эффективность использования чипа хуже, так как из-за архитектурных ограничений Artix-7 удаётся задействовать только 12.5% от имеющихся регистров. В семействе Spartan-3 были доступны 50% регистров.
vak: (Улыбка)
Как много NCL-вентилей можно поместить в FPGA? По одному в каждый слайс. Вот пример чипа xc3s500e, набитого гейтами TH22 под завязку: всего 4656 вентилей, по числу слайсов.



+3 )