vak: (Default)
Я наконец осилил back annotation в Верилоге. Это когда синтезируется прошивка для Xilinx FPGA, и на этапе, когда уже известно точное расположение всех элементарных примитивов, образуется файл с описанием всех задержек для каждого провода и логического вентиля. Даже есть такой стандартный формат SDF, или Standard Delay Format. После этого синтезированная схема преобразуется обратно в Верилог (структурный) и симулируется, загружая SDF-файл как набор параметров тайминга. Предполагается, что временная диаграмма такой симуляции будет примерно соответствовать реальному железу.

Вот что я получил для упомянутого сигнала цикла вычисления наибольшего общего делителя. Цикл в 20 итераций должет выполняться за 99500 пикосекунд, или почти ровно 100 нсек.



В реальности на осциллографе имеем 500 нсек.



Как-то точность времянки не особо радует. Плюс-минус порядок получается.
vak: (Default)
Так выглядит сигнал цикла вычисления асинхронного НОД на чипе Xilinx Artix-7. Сигнал сильно смазанный, увы, так как мой осциллограф Rigol DS1102E имеет полосу пропускания всего 100МГц.

Async GDC(20,1) on Rigol DS1102E scope
vak: (Default)
Асинхронный наибольший общий делитель на микросхеме Xilinx FPGA Artix-7 занимает вот такое количество ресурсов:
Report Cell Usage:
+----------+------+
|Cell |Count |
+----------+------+
|BUFR | 2|
|LUT2 | 236|
|LUT3 | 4|
|LUT4 | 153|
|LUT5 | 26|
|LUT6 | 102|
|LUT6_2 | 28|
+----------+------+
Здесь LUT2-LUT6 это элементарные логические функции с несколькими входами и одним выходом. Примитив LUT6_2 чуть сложнее, он имеет два выхода. BUFR это повторитель-усилитель сигнала.
vak: (Default)
Вот что происходит с альтеровским софтом Quartus II при попытке синтезировать простую схему асинхронного счётчика, содержащую LUTs с обратными связями.
Фатальная ошибка )
Это если поставить для таких ячеек параметр dont_touch="yes", иначе квартус их просто тихо выкидывает из схемы.
vak: (Default)
Измерил скорость работы асинхронного алгоритма вычисления наибольшего общего делителя на Xilinx FPGA. Цикл в 20 итераций выполняется чуть меньше чем за 500 наносекунд. Получается 25 нс на итерацию, или 40M итераций в секунду. Для сравнения, если собрать такую схему на рассыпухе (на микросхемах CD4007), будет 72 микросекунды на 20 итераций, или около 280k в секунду.
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