ДРОБОВИК: арифметическое устройство для дробей (часть 2)

Feb 02, 2022 19:06

Автомат Калашникова - устройство, преобразующее стек в очередь

На предлагаемый в статье 1983 года алгоритм мы взглянули, попробовали даже выполнить, и в общем и целом остались довольны (см. часть 1).

Теперь надо попробовать нарисовать Datapath предполагаемого модуля, т.е части, которые непосредственно выполняют операции над данными. Модуль управления, как водится, оставим "на сладкое".

Пока что оно выглядит так:



Что называется, "в минимальной комплектации", без "байпасов" и констант. Их потом тоже можно будет "прикрутить", если всё остальное заработает и будет во всём этом хоть какой-то смысл.


Начнём с правой части, с регистров P и Q. Они практически идентичны, отличаются только "схемой подключения" и шириной в один бит.

Вот описание регистра P:

//регистр P - тоже довольно нагруженный
//либо ничего не делать, либо вычесть, либо сдвиг влево, либо занести значение из Q
//как будто бы 4 режима, могло бы хватить 2 бит, но тогда ena не получится задействовать
//видимо, проще всё же ышшо один бит припахать

module ShotGunPreg (input clk, input ena, input shift, input sload, input [Width:0] denom, input [Width:0] dif, output reg [Width:0] Q, output Norm);

parameter Width = 16;

always @(posedge clk) if (ena)
Q <= shift? {Q[Width-1:0], 1'b0} : sload? denom : dif;

assign Norm = Q[Width-1]; //пользуемся этим "флагом" когда сдвигаем влево и тот, и другой,
//там единица в самом старшем возникнуть ещё не может

endmodule

В нём мы храним "числитель" исходной дроби, которую мы обозначали p/q. Ширина этого регистра на 1 бит больше, поскольку мы столкнулись с ситуацией, когда после "нормализации" регистра Q он становился больше, чем P, поэтому вычитания не выходило, и затем следовал сдвиг P влево. Не будь одного лишнего бита - мы бы словили переполнение.

На каждом такте этот регистр может выполнить одно из 4 действий:
- сохранить своё значение, как было (когда ena=0), это нужно, к примеру, когда Q>P,
- сдвинуться на 1 влево: так происходит при начальной "нормализации", где P на пару c Q выдвигают максимально влево, а затем это происходит, когда один из разрядов "частного" (в явном виде нигде не участвующего) уже обработан, пора приниматься за следующий.
- загрузить значение из сумматора (точнее, "вычитатора"), т.е P-Q,
- загрузить значение Q, для того, чтобы P и Q поменять местами по завершении одной итерации разложения в цепную дробь.

Как видно, инициализации P из шины данных не предусмотрено - мы пока предполагаем, что раз уж P и Q могут свободно меняться местами, мы можем "вдвинуть" значение P как раз транзитом через Q.

Синтезируется регистр P в 34 ЛЭ при ширине 16 бит. (ну то есть, работаем с дробями, где по 16 бит на числитель и знаменатель, но реально в регистре P получается 17 бит) Да, здесь ничего не попишешь: из 4 входов одного ЛЭ, один вход - разрешения работы регистра, второй - от "соседа" для сдвига влево, третий - от "вычитатора", четвёртый - для замены P и Q местами, но теперь ещё нужно 2 управляющих, явно они никуда не влезут!

Флаг Norm=1 указывает, что значение "нормализовано", т.е его старший бит единичный. Это как учили пользоваться стрелочными приборами: для достижения приемлемой точности стрелка должна находиться во второй половине шкалы! Этот флаг будет использоваться модулем управления, чтобы закончить первый шаг алгоритма. Дополнительный бит, как видно, не используется, т.к при инициализации P там заведомо будет ноль, а в тех местах, где туда может что-то "прилететь", мы нормировку P уже не проверяем...

Далее, рассмотрим регистр Q:

//"входной" знаменатель
//4 варианта работы:
//- ничего не делать (когда ena = 0, самый приоритетный вход),
//- сдвиг влево (когда shift = 1, второй по приоритетности),
//- загрузить значение с шины данных (когда sload = 1),
//- загрузить значение из P (когда ena = 1, shift = 0, sload = 0)

module ShotGunQreg (input clk, input ena, input shift, input sload, input [Width:0] P, input [Width-1:0] Data, output [Width:0] Q, output Norm);

parameter Width = 16;

reg [Width-1:0] Qreg;

assign Q = {1'b0, Qreg}; //регистру P нужен дополнительный бит, чтобы не переполниться

always @(posedge clk) if (ena)
Qreg <= shift? {Qreg[Width-2:0], 1'b0} : sload? Data : P[Width-1:0];

assign Norm = Qreg[Width-1];

endmodule

Здесь мы храним знаменатель исходной дроби p/q. Точнее, загружаем мы знаменатель, а потом на каждой итерации, по сути, откидываем целую часть, оставляя здесь только дробную (т.е вместо 22/7 оставляем 1/7 и т.д.), а потом её переворачиваем вверх тормашками.

Также 4 режима работы, но чуть другие:
- ничего не делать, хранить своё значение (используется во "внутреннем цикле"),
- сдвиг влево (используется на первом шаге, для "нормализации", а затем в начале каждой итерации разложения в цепные дроби),
- загрузить значение P (чтобы поменять местами P и Q в конце итерации),
- загрузить значение из шины данных, для инициализации работы.

Собственно, как и прошлый раз - сдвиг и загрузка с двух разных входов. Но здесь лишний бит не нужен, поэтому при размере знаменателя 16 бит, этот модуль занимает 32 ЛЭ.

Флаг Norm выполняет ту же роль, что и в регистре P. Но здесь он проверяется не только на первом шаге, но и в начале каждой итерации разложения в цепную дробь.

Как таковой выход с регистров P и Q мы делать не хотим - данные здесь очень быстро "протухают" и дальнейшего интереса обычно не представляют. Хотя в этой злополучной статье ведутся размышления, что если округляешь дробь, то именно финальные значения P,Q содержат "поправку", позволяющие из этой округлённой дроби восстановить оригинал. Но авторы честно признались, что до конца всю эту "механику" не продумали.

И ещё для работы данной "подсистемы" был необходим "вычитатор". Для 16-битных значений он 17-битный, занимает аккурат 17 ЛЭ, и ещё используется выход "переполнения", по которому мы должны определить знак разности. Возможно, вместо переполнения надо было взять выход Borrow Out, узнаю опытным путём, чего-то до сих пор не запомнил, как у этих сумматоров "вспомогательные выходы" построены. Собственно, увидев, что Q>P, нужно "запретить" занесение разности в регистр P, а ещё на основании правильно выбрать следующее состояние.

Регистры A и C идентичны, поэтому для них написан один модуль, который на общую схему "кинут" дважды:

module ShotGunACreg (input clk, input aclr, input [Width-1:0] sum, input [Width-1:0] BD, input sload, input ena, output reg [Width-1:0] Q);

parameter Width = 16;

always @(posedge clk or posedge aclr)
Q <= aclr? {Width{1'b0}} : ena? (sload? BD : sum) : Q;

endmodule

Это два самых простых регистра. От них требуется следующие 4 режима:
- ничего не делать (пока мы нормализуем P/Q, затем только Q, а затем, если оказалось Q>P),
- загрузить сумму (т.е A = A + B, либо C = C + D),
- загрузить соседний регистр, чтобы поменять местами A и B, а также C и D.
- сброс в нулевое значение.

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

Мне просто страшно не хочется "вручную", по одному, загружать значения 0,1,1,0 (для регистров A,B,C,D, такие значения нужны для "округления") из шины данных, когда можно получить нули путём сброса, а единицы - с помощью входа cin сумматора, когда повсюду будут лежать нули. Да и в других арифметических операциях хоть один ноль, да нужно загрузить.

В итоге, регистры A и C при ширине 16 бит занимают по 16 ЛЭ каждый. Это абсолютный минимум, понятное дело.

А вот регистры B,D вышли сейчас наиболее "толстыми"... Вот их код:

//куда более злостный сдвиговый регистр
//должен производить сдвиг как влево, так и вправо,
//а также загружать значение "соседа" (A или C соответственно),
//либо значение с шины данных, либо вообще нолик / единичку для округления/сокращения
//и также он должен уметь "держать результат"

//итого, 1 вход разрешения работы ena.
//и выбор значений для загрузки:
//00 - сдвиг влево,
//01 - сдвиг вправо,
//10 - загрузить из A/C,
//11 - загрузить из шины данных
//и пока этого хватит: будем "ручками" управлять этой хреновиной
//эх, надо бы асинхронный сброс всё же задействовать...
//обязательно с регистрового выхода, чтобы комбинаторный мусор не породить

module ShotGunBDreg (input clk, input aclr, input [1:0] mode, input ena, input [Width-1:0] AC, input [Width-1:0] DataBus, output reg [Width-1:0] Q);

parameter Width = 16;

always @(posedge clk or posedge aclr)
Q <= aclr? {Width{1'b0}} :
ena? ((mode == 2'b00)? {Q[Width-2:0], 1'b0} : (mode == 2'b01)? {1'b0, Q[Width-1:1]} : (mode == 2'b10)? AC : DataBus) :
Q;
endmodule

Они должны иметь функциональность регистра Q (сдвиг влево, поменяться местами с соседом, загрузить данные с шины данных), но впридачу уметь сдвигаться вправо, и асинхронно сбрасываться. Последнее "бесплатно" (у каждого ЛЭ есть отдельные входы асинхронного сброса и установки), а вот ещё один дополнительный вход (от соседнего бита, для сдвига вправо) делает логику очень громоздкой: для 16 бит получается 48 ЛЭ! И таких целых два...

Возможно, здесь получилось бы убрать вход разрешения работы, потому как, если умеешь сдвигаться и влево, и вправо, то можешь так и "елозить взад-вперёд", вместо того, чтобы вообще встать как вкопанный. Это позволяет сэкономить по 1 ЛЭ на бит (т.е 32 ЛЭ вместо 48), но это усложнит логику работы, пока на такие меры идти не хочется. Возможно также, надо по-другому пронумеровать режимы (т.е какое значение mode чему соответствует), хотя я не очень понимаю, как это могло бы помочь. Тут просто жуткий перебор входов...

Сумматоры я пока что поставил самые простые. Впоследствии можно будет добавить сюда входы cin, чтобы легко инициализировать регистры значениями 0,1,1,0, а также выходы переполнения, по которым мы будем "досрочно" прекращать разложение в цепную дробь.

Ещё здесь пока нет счётчика K, который должен указывать, на сколько позиций сдвинуты B,D относительно исходной. В статье они зачем-то вообще указали его как сдвиговый регистр с одинокой единичкой, двигающейся вправо-влево. Но в этом нет никакого смысла, зачем нам унарный счётчик (унарный код - это *=1, **=2, ***=3, ****=4 и так далее, много так не сосчитаешь!), если можно поставить нормальный двоичный. Ну да ладно, его посадим непосредственно в модуль управления, так оно, по сути, и есть.

Также ещё не хватает выходного мультиплексора, чтобы выдать на шину данных либо B, либо D. Пока что, в отладочных целях, лучше просто наблюдать все регистры "параллельно". Но такой мультиплексор (2 к 1, на 16 разрядов) займёт 16 ЛЭ. Ещё очень полезен был бы "байпас", перемещающий B,D напрямую в P,Q, но пока обойдёмся без него.

Итого, для работы с 16-битными числителями и знаменателями (пока беззнаковыми), этот драндулет синтезировался в 243 ЛЭ (и есть возможность уменьшения до 211 ЛЭ ценой некоторого усложнения модуля управления). Модуль управления ещё добавит сколько-то размера, но, подозреваю, незначительно. Пока у меня удавалось их реализовать без микрокода, на чистой логике.

Если учесть, что таким модулем можно покрыть ВСЮ АРИФМЕТИКУ ДРОБЕЙ (сложение, вычитание, умножение, деление), по-моему, не так уж и плохо.

Хотя, если я правильно понял, тут должен быть большой запас по всем регистрам для промежуточных вычислений, поэтому, если хочешь свободно обращаться с дробями, у которых по 16 бит на числитель и знаменатель, тут ширину надо увеличить до 32 бит, а это, где-то навскидку, уже 486 ЛЭ.

Предельная тактовая частота: 68,49 МГц для моей ПЛИС 5576ХС4Т. "Критические пути" - в 17-битном сумматоре. Похоже, он сильно медленнее 16-битного, тот и на 80 МГц "шпарил". Но учитывая, что QuatCore у меня пока на 25 МГц работает, сойдёт ещё как!

Вот как раз преимущество дробей в том, что сумматоры все выходят вдвое короче, и задержка распространения к старшему разряду меньше. Своего рода "распараллеливание" происходит, что для ПЛИС завсегда приятно.

странные девайсы, математика, ПЛИС, работа

Previous post Next post
Up