nabbla (nabbla1) wrote,
nabbla
nabbla1

Category:

Мучаем 5576ХС4Т - часть 'h30 - вычислитель множества Мандельброта

Часть 0 - покупаем, паяем, ставим драйвера и софт
Часть 1 - что это вообще за зверь?
Часть 2 - наша первая схема!
Часть 3 - кнопочки и лампочки
Часть 4 - делитель частоты
Часть 5 - подавление дребезга кнопки
Часть 6 - заканчиваем кнопочки и лампочки
Часть 7 - счетчики и жаба
Часть 8 - передатчик UART
Часть 9 - Hello, wolf!
Часть 'hA - приёмник UART
Часть 'hB - UART и жаба
Часть 'hC - полудуплексный UART.
Часть 'hD - МКО (МКИО, Mil-Std 1553) для бедных, введение.
Часть 'hE - приёмопередатчик МКО "из подручных материалов" (в процессе)
Часть 'hF - модуль передатчика МКО
Часть 'h10 - передатчик сообщений МКО
Часть 'h20 - работа с АЦП ADC124s051
Часть 'h21 - преобразование двоичного кода в двоично-десятичный (BCD)
Часть 'h22 - Bin2Bcd с последовательной выдачей данных
Часть 'h23 - перемножитель беззнаковых чисел с округлением
Часть 'h24 - перемножитель беззнаковых чисел, реализация
Часть 'h25 - передаём показания АЦП на компьютер
Часть 'h26 - работа над ошибками (быстрый UART)
Часть 'h27 - PNG и коды коррекции ошибок CRC32
Часть 'h28 - передатчик изображения PNG
Часть 'h29 - принимаем с ПЛИС изображение PNG
Часть 'h2A - ZLIB и коды коррекции ошибок Adler32
Часть 'h2B - ускоряем Adler32
Часть 'h2C - формирователь потока Zlib
Часть 'h2D - передаём сгенерированное PNG-изображение
Часть 'h2E - делим отрезок на равные части
Часть 'h2F - знаковые умножители, тысячи их!
Часть 'h30 - вычислитель множества Мандельброта
Часть 'h31 - ускоренные сумматоры
Часть 'h32 - ускоренные счётчики (делаем часы)
Часть 'h33 - ускоряем ВСЁ
Часть 'h34 - ускоренные перемножители
Часть 'h35 - умножители совсем просто
Часть 'h36 - уравновешенный четверичный умножитель


С днём радио всех причастных!

По такому поводу самое время отойти от скучного верилога и нарисовать схему электрическую принципиальную :)

Вот он, вычислитель множества Мандельброта! Голубым обозначен провод тактовой частоты clk (чтобы не сильно отвлекал от всего остального), светло-зелёным - цепи сброса.


Сейчас тут много "отладочных" выходов, чтобы понять, как оно функционирует, а вообще внешние соединения весьма скромны - два входа (тактовая частота clk и импульс запуска start) и два выхода: ByteCE (сюда поступает единичка, когда у нас готов очередной пиксель) и Q (это и есть очередной пиксель, то есть, сколько понадобилось итераций, чтобы последовательность "убежала").


"Сердце" конструкции - два умножителя LeadingMAC17param (Leading Multiply-ACcumulator 17 bit parametrized, ведущий сумматор-перемножитель на 17 бит с возможностью задать ширину аккумулятора) и GuidedMACtimes2 (ведомый сумматор-перемножитель с умножением на 2), рассмотренные в предыдущей части.

К ним добавляется два сумматора XminusY и XplusY. Вот их код, весьма простецкий:
module XplusY (input [15:0] X, input [15:0] Y, output [16:0] Q);

wire [16:0] Xext = {X[15], X};
wire [16:0] Yext = {Y[15], Y};

assign Q = Xext + Yext;

endmodule


module XminusY (input [15:0] X, input [15:0] Y, output [16:0] Q);

wire [16:0] Xext = {X[15], X};
wire [16:0] Yext = {Y[15], Y};

assign Q = Xext - Yext;

endmodule


Мы "расширяем" 16-битную шину до 17 бит, для чего старший бит дублируется (чтобы получить корректный дополнительный код), после чего просто складываем или вычитаем эти два значения.

Для генерации константы C = cx + cyi, используются два модуля EqualPartsDivider, рассмотренные в части 'h2E. Задавая 3 параметра в них, мы можем определить интересующую нас область множества Мандельброта. Сейчас для отладки мы поделили отрезок -1..+1 всего лишь на 8 частей, чтобы можно было увидеть на симуляторе весь процесс целиком, от начала до конца. Как оказалось, "тривиальный частный случай", когда на каждом шаге нужно попросту прибавить константу, не заморачиваясь с дробями, наш EqualPartsDivider достойно выполняет! Может, он получается чуть более громоздким (образуется целый 2-битный регистр и 2-битный сумматор, которые в действительности "стоят на месте", поскольку остаток от деления - 0 - этих 4 ЛЭ можно было бы избежать), но по крайней мере "не делит на ноль".

Затем у нас стоят два счётчика Mandel_cnt_1920 и Mandel_cnt_1080, чтобы понимать, на каком мы сейчас пикселе, и должным образом управлять нашими "делителями отрезка на равные части", а также чтобы корректно завершить работу, когда мы дойдём до последнего пикселя изображения. В данный момент они считают всего до 8, в целях отладки.

Справа снизу у нас стоит счётчик итераций Mandel_iter_cnt, который тоже в идеале должен быть 8-битным, но пока мы сделали его 3-битным, чтобы не убить симулятор. Все эти счётчики - библиотечные элементы lpm_counter - все необходимые параметры задаются через Wizard. В этой схеме, если мы хотим считать до чего-то отличного от степеней двойки, например, до 1920, лучше будет считать не от 0 до 1920, а от 128 до 2048 - как показал опыт, "родной" выход cout (каскадирования счётчика) гораздо шустрее "искусственного", если мы зададим modulo равное, например, 1920. По сути, визард поставит туда 11-битный компаратор, а выходы каскадирования сложных логических операций работают чрезвычайно медленно, у меня timing analyzer начинает ругаться даже на быстром кристалле "-1". А если считать от 128 до 2048 - не ругается.

И наконец, половину принципиальной схемы занимает связующая логика, которая превращает эти разрозненные узлы в единый механизм! К сожалению, она здесь расположена немного "наобум", поскольку её пришлось переделывать раз 5, пока схема не заработала корректно.

В первую очередь, рассмотрим цепи сброса (светло-зелёные). Вход запуска start поступает на "триггер-защёлку", поскольку симулятор считает, что мы его тащим с одного из входов ПЛИС через глобальный интерконнектор, и создаёт задержку чуть ли не в один такт, что иногда вообще не даёт схеме запуститься. Так мы делаем запускающему импульсу хороший, красивый фронт, который расположен почти где надо.

Затем этот импульс, задержанный на такт, обнуляет нам все 3 счётчика, два "делителя отрезка на равные части", а также оба перемножителя. Надо заметить, что для обнуления перемножителя мы задерживаем наш запускающий импульс на такт, а затем и ещё на такт (см. цепь задержки внизу схемы). Это нужно, поскольку только после первого импульса мы будем убеждены, что с выходов "делителей отрезков на равные части" поступают корректные начальные значения. Поэтому только спустя такт мы должны подать импульс запуска на перемножитель. Когда пройдёт этот импульс, на выходах перемножителей появятся начальные значения, и именно их (должным образом обработанных) мы хотим видеть на входах перемножителей B, C. Второй запускающий импульс решает нашу задачу - по сути, мы инициализировали нашу схему значениями cx, cy, и теперь считаем выражение
X <= X * X - Y * Y + cx;
Y <= 2 * X * Y + cy;


Итак, чтобы начать новую последовательность (с новыми значениями cx, cy), нам нужно сначала дождаться появления корректных значений InitVal, а затем дать два идущих подряд импульса start на наши перемножители. Если же мы по окончании вычислений подаём всего один импульс start, то продолжим текущую последовательность. Весьма удобно!

Дальше рассмотрим, что происходит по окончании умножения.
Как ни странно, нам не интересно, какие значения получил умножитель, интересно лишь - случилось ли переполнение в одном из двух перемножителей? Такой же эффект должен иметь счётчик итераций, дошедший "до упора" - во всех этих случаях пора заканчивать работу с текущим пикселем и переходить к следующему.

Но сначала разберём, что происходит, если переполнения нет. В этом случае сигнал ready с перемножителя прибавляет единичку к счётчику итераций, и перезапускает перемножители, чтобы они продолжили итерации. Этот сигнал проходит через элемент "И" (inst31) и элемент "ИЛИ" (inst16).

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

Также этот сигнал переполнения объединяется через логическое "И" (inst18) с выходом окончания работы перемножителя, поскольку сигнал переполнения может "зажигаться" в середине работы перемножителя, но эти показания ничего не стоят. (Возможно, стоило бы это "И" убрать внутрь перемножителя.)

Результирующий сигнал очень важен: именно он поступает на выход ByteCE, указывая: счётчик итераций досчитал до конца, и пора занести это число в память как цвет очередного пикселя. И он же осуществляет синхронный сброс данного счётчика. Очень важно, чтобы этот сброс был синхронным, иначе мы понятия не имеем, что пойдёт в память! Также этот сигнал поступает на элемент "И", расположенный на схеме слева снизу (inst28). Второй вход этого элемента равен единице всегда, кроме случая, когда мы обрабатываем самый последний пиксель, т.е оба счётчика (по строкам и по столбцам) досчитали до конца.

Таким образом, на выходе элемента "И" (inst28) появляется единичный импульс всегда, когда нам нужно перейти к следующему пикселю. Он поступает на вход разрешения счёта по строке (Mandel_cnt_1920), а также разрешает прибавить 1 к счётчику по столбцам (Mandel_cnt_1080), если мы уже досчитали до конца строки (появился сигнал cout с Mandel_cnt_1920). Вместе с сигналами разрешения счёта мы также подаём сигналы на "делители отрезков на равные части", чтобы они обновляли начальные значения cx и cy соответственно.

И наконец, этот сигнал с выхода "И" (inst28) поступает на линию задержки (внизу схемы, inst20, inst27), чтобы перемножители начали вычислять новую последовательность, т.е сначала произошла бы инициализация аккумуляторов новыми значениями cx, cy, а затем, на следующем такте - инициализация входных регистров перемножителя значениями cx-cy, cx+cy (на верхнем перемножителе, для действительной части) и cx, cy (на нижнем перемножителе, для мнимой части).

Вот, собственно, и всё - ничего шибко мудрёного тут не происходит.

Запустим симуляцию этого дела. Даже расчёт картинки 8х8 при "8 градациях серого" занимает 82,2 мкс, и осциллограмма получается чрезвычайно длинной - на одном экране и даже на 10 экранах её не уместишь!

Здесь мы наблюдаем начало работы:


Пришёл импульс запуска, обнулил всё, кроме перемножителей. Наконец, спустя один такт, появляется сигнал запуска перемножителей DMACstart, длящийся два такта. По прошествии первого такта мы видим, что в аккумулятор защёлкнулись начальные значения -1. Мы для отладки вытащили всего по 1 байту с чисел X, Y, иначе Fitter(place&router) начинает тупить (error: couldn't find fit), ну и ладно. Поэтому чтобы узнать, какое число имеется в виду, делим значения X, Y на 64. В данном случае это (-1; -1).

Первая итерация дала новые значения: (-1; 1) - всё верно,
(-1 - 1i)2 + (-1 - 1i) = -1 + 1i. 


И переполнения пока нет - это тоже верно. Благодаря этому импульс DMACready (перемножитель закончил работу) напрямую поступает на вход DMACstart (запуск перемножителя), и он продолжает считать эту последовательность. К счётчику итераций прибавилась единица. Теперь перемножители находят:
(1+1i)2 + (-1 - 1i) = -1 - 3i


Минус единица - на своём месте. Вместо минус тройки - единица, поскольку разряд "минус четвёрок" не вместился. Ну и появился сигнал переполнения - всё верно!

Сигнал переполнения заставил сформироваться импульс Byte_CE (т.е значение 1 счётчика итераций поступило в память), а также сбросить счётчик итераций и прибавить единичку к "переменной i", которая считает по строке.

Мы снова видим сдвоенный импульс запуска перемножителя - теперь в него поступило число (-0,75 ; -1), и на первой же итерации он обработал его, получив (-1,1875 ; 0,5), а ещё спустя итерацию - (0,41015625 ; -2,1875), но мнимая часть вышла за пределы, и мы снова получили переполнение. Это заставило нас перейти на следующий пиксель, теперь мы начинаем с числа (-0,5 ; 1), оно ближе к центру, и последовательность длится дольше - мы успеваем досчитать до 2.

Отмотаем немного вперёд:


Здесь мы в пикселе (4; 0), которому соответствует число (0; -1). Из него мы получаем (-1; -1), затем (0; 1), затем снова (-1; -1), т.е мы вошли "в бесконечный цикл" - эта последовательность никогда не переполнится! "Умные" программы могут обнаруживать такие циклы и прерывать их, но у нас всё проще - придётся досчитать максимальное число итераций (для отладки это всего 8), и перейти к следующему пикселю. Т.е счётчик, дошедший до значения 7 (от нуля), подействовал точно так же, как сигналы переполнения.

Следующий слайд!


Здесь мы видим, как быстро "разошёлся" пиксель (7;0), с числом (0,75 ; -1), всего за одну итерацию. И теперь мы перешли к пикселю (0; 1) - переход на новую строку работает как надо!

Также мы видим, что на новой строке мы первым делом занесли число (-1; -0,75), т.е "шагнули" по мнимой оси, а по действительной оси вернулись на исходную позицию -1 - всё правильно.

Наконец, посмотрим, чем всё это заканчивается:


Мы перешли на последний пиксель, (7; 7), начали считать очередную итерацию. Она завершилась без переполнения, поэтому мы начали следующую. В ней произошло переполнение, поэтому мы выдали последний байт "в память", и на этом вся работа замерла. Всё корректно - как начало работы, так и её окончание.

Данный драндулет в своей "отладочной версии" занимает 338 ЛЭ, а в "полной версии" (когда хотим получить картинку 1920х1080, с палитрой из 256 цветов) - 425 ЛЭ. Это уже 4,3% от общего количества ЛЭ. Если объединить этот модуль с формирователем потока Zlib и передатчиком PNG, это получится около 750 ЛЭ, или 7,5% от общего количества. Не так уж и плохо: вполне может когда-нибудь сойти за "пасхальное яйцо", когда у нас остались незадействованные элементы, и мы решили, а пусть устройство "для приколу" ещё строит фрактал Мандельброта! Но всё-таки мы видим, что ПЛИС у нас не бездонная...


В следующей части мы соединим этот вычислитель с формирователем потока Zlib и передатчиком картинки PNG.
Tags: ПЛИС, математика, работа, странные девайсы
Subscribe

  • Огари разговаривают

    Сегодня по пути на работу встретил огарей прямо в Лосином острове, на берегу Яузы. Эти были на удивление бесстрашны, занимались своими делами, не…

  • Очень запоздало о лыжах

    Давненько (с 16 февраля) не писал о лыжах, хотя каждую неделю катался. Первый раз - на Гремячий и назад, с разведкой нового пути к маленькому…

  • Воскресная прогулка в сторону Гремячего

    Не было особенных планов "доехать во что бы то ни стало", хотел просто посмотреть "что вообще творится"? после обильных снегопадов в пятницу-субботу.…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 3 comments