nabbla (nabbla1) wrote,
nabbla
nabbla1

Испытания новой АЛУ, часть 0

Стряхнём пыль с аффинного алгоритма, и попробуем его запустить на QuatCore с новой АЛУ. Ну, АЛУ не совсем новая, изменения коснулись преимущественно модуля управления.

Начнём с первой процедуры, "поиск самой отдалённой точки". У нас этих точек обнаружено 4 штуки, для каждой указаны координаты. Мы находим одну точку, стоящую "особняком" - это будет Мишень Дальней Дистанции - 3 (МДД3). Для этого просто ищем сумму квадратов дальностей от каждой точки до всех остальных точек. Такая вот программка:

;состояние регистров неизвестно (за искл. PC и SP)
FindMDD3	proc
;перво-наперво, находим МДД3
;как точка, сумма квадратов расстояний до которой максимальна (т.е самая отдалённая)
;для каждой точки считаем сумму квадр. расстояний до всех остальных, в т.ч до самой себя (это 0, зато код упрощается)
;внешний цикл (по строкам) - перем. j
;внутр. цикл - по индексу перем (X или Y) - перем k
;самый-самый внутр. цикл (по столбцам) - перем. i
		Y	Points2D
		[SP+1]	0	;максимальная отдалённость, инициализируем нулём
		;рег. X будет хранить индекс точки с макс. отд. её иниц. не надо-заведомо на одной из итераций запишется
					
		j	3
@@j_loop:	k	1	;также от 0 до 3, чтобы все расстояния просуммировать
		[SP]	0	;здесь будет храниться текущий максимум
@@k_loop:	i	3	;от 0 до 1, т.е значения X и Y
;а теперь непосредственно прибавляем к акк. ([X+2i+k]-[X+2j+k])^2
@@i_loop:	Acc	[Y+2j+k]	;загрузили одно значение
		SUB	[Y+2i+k]	;вычитаем второе
		SQRD2	Acc			;возводим в квадрат
		ADD	[SP]		;прибавляем к пред. значению
		[SP]	Acc
		iLOOP	@@i_loop		;теперь то же самое для второй координаты
		kLOOP	@@k_loop
;хорошо, нашли сумму расстояний от точки j до всех остальных
;она лежит в Acc и в [SP]
;нужно сравнить с самым большим, и если больше - заменить
;самое большое значение мы храним в [SP+1],
;а его индекс - в X
		SUB	[SP+1]	;можно и "пожертвовать" значением в Acc,
;т.к в [SP] лежит точно такое же!
		JL	@@skip
;дистанция оказалась больше - надо обновить максимум и его индекс
		[SP+1]	[SP]	;двухпортовая память-это зашибись!
		X	j
@@skip:		jLOOP	@@j_loop
;по окончании этих циклов, у нас в X лежит индекс точки, которая является МДД3
;осталось эту точку поменять местами с точкой под индексом 0...
;здесь i=j=k=0 (все циклы завершились!)
		i	X
		X	Points2D
		Z	Points2D
		CALL	SwapPoints	;потёрли текущий максимум (лежал в [SP])-и хрен с ним
		
;на этом первая часть марлезонского балета закончена.
FindMDD3	endp


За быстродействием тут явно не гнались, эта операция выполняется один раз за кадр, и даже на 4 МГц проблем не было. Скорее, гонка была за простотой и компактностью кода: пусть мы по несколько раз посчитаем одни и те же квадраты, в том числе заведомые нули (когда i=k), зато лишних условий и хитрючих манипуляций с памятью нет.

На "старом" АЛУ всё это дело (до прыжка в SwapPoints) выполняется за 47,36 мкс при тактовой частоте 25 МГц. Для введённых сейчас точек:
;дистанция 300 метров, все углы нулевые
Fx0		Int16 53
Fy0		Int16 -7

Fx1		Int16 480
Fy1		Int16 -30

Fx2		Int16 -539
Fy2		Int16 -302

Fx3		Int16 400
Fy3		Int16 -997


самой отдалённой оказалась последняя - всё верно.

Посмотрим сначала, какого ускорения можем ждать от новой АЛУ, и можно ли чуть подрихтовать код, чтобы он воспользовался преимуществами. Как ни странно - без увеличения размера кода это практически нереально!


Первая операция во внутреннем цикле - загрузить значение в Acc - выполнится за положенные 3 такта. Вторая - вычитание - за 2, т.к наложится на первую (заработает по принципу конвейера), но затем, как и раньше, мы застрянем на лишний такт, т.к у нас запросили результат работы.

Операция SQRD2 - САМАЯ МЕДЛЕННАЯ из всех, выполняется за 19 тактов, так оно и выйдет (она не наложилась на предыдущую, т.к требовала результата предыдущей у себя на входе).

За ней последует сложение - оно выполнится за 2 такта, но мы ОПЯТЬ застрянем на такт, чтобы дождаться результатов работы и положить их в [SP]. И только после этого мы начнём возиться с циклами (kLOOP, iLOOP).

Итого, если оставить всё "как есть", во внутреннем цикле должно сэкономиться аж 2 такта. Выполнится он 32 раза, итого имеем 64 такта экономии, это 2,56 мкс, или 5% времени выполнения.

Можно было бы сэкономить чуть больше, если перенести "[SP] Acc" в начало цикла, а перед этими циклами занулить не [SP], а сам Acc. Тогда между сложением и взятием результата процессор не будет терять времени зря, а уже перепрыгнет в начало цикла "бесплатно". Но тогда при завершении циклов результат будет лишь в Acc, и мы его "разрушим" командой SUB [SP+1]. Тут либо добавляй ещё одну строку "[SP] Acc" после цикла, но этого нам не хочется, хочется выигрыша нахаляву! Либо команда CMP спасла бы бедного кота, но её вводить в только что отрихтованный АЛУ тоже лениво :) Так что ладно, пусть так.

Когда мы выходим из циклов по i и k, идёт команда вычитания, и здесь снова никакого выигрыша, ведь СРАЗУ после неё идёт условный переход, который обязан знать результаты работы этого вычитания, поэтому и здесь всё по-старому, остановимся и будем ждать!

Можно разве что перетащить сюда команду "Z Points2D", между вычитанием и переходом, т.к здесь она выполнится "за бесплатно" (параллельно с АЛУ), а внизу - отжирала свой собственный такт. Но это ЕДИНИЧНЫЙ выигрыш, то есть РОВНО ОДИН ТАКТ на всю процедуру FindMDD3. Итого, имеем аж 65 тактов экономии, в общем, совсем ни о чём.

Приведём листинг чуть подправленной программы, где "Z Points2D" перенесена выше:
main proc
00  FD00              SP      Stack
AffineAlgorithm     proc
    Associate4Points    proc
        FindMDD3    proc
01  DD01                  Y       Points2D
02  F002                  [SP+1]  0   ;максимальная отдалённость, инициализируем нулём
03  A103                  j       3
04  A204          @@j_loop:   k       1   ;также от 0 до 3, чтобы все расстояния просуммировать
05  FC02                  [SP]        0   
06  A003          @@k_loop:   i       3   ;от 0 до 1, т.е значения X и Y
07  80DA          @@i_loop:   Acc     [Y+2j+k]    ;загрузили одно значение       (3 такта)
08  83D9                  SUB     [Y+2i+k]    ;вычитаем второе               (2 такта, т.к не дожидаемся окончания ACC, но ещё один т.к нужно загрузить Acc в DataBus)
09  9C80                  SQRD2       Acc     ;возводим в квадрат          (19 тактов)
0A  82FC                  ADD     [SP]        ;прибавляем к пред. значению   (2 такта, т.к не дожидаемся SQRD2, но ещё один т.к Acc)
0B  FC80                  [SP]        Acc
0C  A805                  iLOOP       @@i_loop        ;теперь то же самое для второй координаты
0D  AA06                  kLOOP       @@k_loop
0E  83F0                  SUB     [SP+1]
0F  ED01                  Z       Points2D    ;вообще, оно перед SwapPoints, но здесь всё равно ждём окончания SUB        
10  B807                  JL      @@skip
11  F0FC                  [SP+1]  [SP]    ;двухпортовая память-это зашибись!
12  CDA1                  X       j
13  A908          @@skip: jLOOP       @@j_loop
14  A0CD                  i       X
15  CD01                  X       Points2D
16  F3B3                  CALL        SwapPoints  ;потёрли текущий максимум (лежал в [SP])-и хрен с ним


Ну и поглядим это на симуляции:


Указатель стека делаем равным 0x5D, всё верно, да этот фрагмент мы и не трогали. Затем в регистр Y заносим адрес начала наших точек, 0x18 - всё верно. Потом ещё [SP+1]=0, j=3, k=1, [SP]=0, i=3. Мы видим на шине данных 0, затем 0xA3, затем 0x41, снова 0 и снова 0xA3. НИКАКОГО КРИМИНАЛА: регистры i,j,k 5-битные, и младшие 5 бит, идущие к ним, верные. Видимо, компилятор объединил несколько констант.

Когда в регистр i поступало значение с шины данных, 3, мы остановились на один такт, поскольку в это время шла выборка [Y+2j+k] для следующей команды. В итоге на шину приходит значение 0xFC1B = -997, всё верно (это Y3).

И вот, БАРАБАННАЯ ДРОБЬ: DestAddr = 0x80 (Acc, занести значение в аккумулятор), в это время SrcAddr = 0xD9 (выборка [Y+2i+k]). До этого момента АЛУ отдыхало. Сейчас на первом такте работы ни DestStall, ни SrcStall не загорелись, это верно - АЛУ "отпускает нас" (даёт продолжить работу), а выборка [Y+2i+k], занимающая 2 такта, даёт DestStall с задержкой на такт.

И действительно, на втором такте мы получили DestStall = 1, благодаря чему АЛУ "поняло", что повторная команда Acc не пришла, и не выдало SrcStall=1 (дескать, мы заняты, подождите за дверью!). Пока всё правильно. Выборка дала то же значение 0xFC1B = -997, да, вот такой вот "оптимизированный" у нас код :)

И теперь у нас DestAddr = 0x83 (SUB, вычесть значение из аккумулятора), в это время SrcAddr = 0x80 (Acc, взять значение из аккумулятора). И снова на первом такте работы ни DestStall, ни SrcStall не загорелись, т.к АЛУ как раз начало 3-й такт, который у него совмещается с 1-м тактом новой команды, так что оно снова "отпускает нас". А вот Acc на стороне SrcAddr выдаёт DestStall, но, как обычно, с задержкой.

И тут очень удачно проскочил весьма скользкий момент! Мы почему-то его отсекли как неправдоподобный, а зря! Забыли про задержку DestStall на такт, благодаря чему на этом такте у нас встретились две команды DestAddr, принадлежащие АЛУ и выполняемые ОДНОВРЕМЕННО (завершающаяся Acc и только начавшаяся SUB) и SrcAddr, также принадлежащая АЛУ (Acc).

И АЛУ справилось с честью! Оно начало ждать завершения только-только поступившей команды SUB, прежде чем выдать результат на шину данных. При этом АЛУ приняло РОВНО ОДНУ команду SUB, так как сразу после этого включилось DestStall=1, что означает "поступающая сейчас команда недействительна".

Прошли положенные 3 такта, но мы задержались ещё и на четвёртый, чтобы дождаться правильного значения Acc. Значение это: НОЛЬ, всё правильно.

Далее идёт DestAddr = 0x9C (SQRD2), в это время SrcAddr = 0xFC ([SP]). К этому моменту АЛУ освободилось и с радостью приняло новую команду (возвести значение в квадрат и поделить на 2), а выборка из памяти опять заняла лишний такт. Как результат, мы загрузили текущую сумму, равную нулю.

И теперь начинается супер-монстр: DestAddr = 0x82 (ADD), в это время SrcAddr = 0x80 (Acc). Команда по DestAddr у нас имеет приоритет, поскольку это ПРЕДЫДУЩАЯ команда, тогда как SrcAddr относится к СЛЕДУЮЩЕЙ. Так у нас "зажглось" SrcStall. То есть остановка пришла по запросу DestAddr. Себя он останавливает сам (так сделано, чтобы избежать рекурсии), а "соседа" останавливает через SrcStall.

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


Как видно, остановились мы основательно, оно и понятно, возведение числа в квадрат и взятие от него половинки - это наша самая длинная операция, занимающая 19 тактов. Два уже прошло, ещё 16 идут с SrcStall = 1. Наконец, последний идёт со снятой SrcStall, т.е мы наконец-то начинаем исполнять команду Acc. Она не мешает завершить команду SQRD2, а на следующий такт включает DestStall.

И во время этой "передышки" на 1 такт, когда завершалось исполнение SQRD2, параллельно началось исполнение следующей команды, ADD, а именно загрузка в регистр B значения с шины данных, из [SP].

Далее, с DestStall = 1 проходит 2 такта, чтобы завершить выполнение ADD, и ещё один, чтобы правильное значение из Acc загрузить на шину данных. Это значение: 0. Не очень наглядно, но по тактам всё выглядит совершенно правильно.

Потом у нас DestAddr = 0xFC ([SP]), в это время SrcAddr = 0x05 (@@i_loop). Вычисленное значение, 0, помещается в [SP], в это время на шину данных заготавливаем адрес для условного перехода в начало цикла по i, 0x07.

Далее, DestAddr = 0xA8 (iLOOP) и SrcAddr = 0x06 (@@k_loop). Было i=3, это больше нуля, поэтому переход выполняется, мы оказываемся в PC=0x07. Команда SrcAddr = 0x06 признаётся недействительной (SrcDiscard=1), но это "непосредственное значение", оно не имеет побочных эффектов, и всё равно поступает на шину данных, это адрес 0x06 для прыжка в начало цикла по k.

Далее, DestAddr = 0xAA (kLOOP) и SrcAddr = 0xF0 ([SP+1]). Оба адреса объявлены недействительными и не выполняются (не происходит прыжка, не происходит задержки на такт для выборки из памяти).

Далее, DestAddr = 0x83 (SUB) и SrcAddr = 0xDA ([Y+2j+k]). При этом DestStall = 1, поэтому SUB не выполняется, а вот выборка [Y+2j+k] проходит за 2 такта, получаем значение 0xFC1B = -997. Всё верно, у нас по-прежнему j=3, так что мы взяли Y3.

Далее, DestAddr = 0x80 (Acc) и SrcAddr = 0xD9 ([Y+2i+k]). Значение -997 отправляется в аккумулятор, в это время идёт выборка из памяти значения Y2 = 0xFED2 = -302, что занимает 2 такта.

Далее, DestAddr = 0x83 (SUB) и SrcAddr = 0x80 (Acc). Да, мы уже "втянулись" во вторую итерацию (как только конвейер очистился от мусора), здесь мы из -997 вычитаем -302, что даёт 0xFD49 = -695, всё верно.

DestAddr = 0x9C (SQRD2) и SrcAddr = 0xFC ([SP]). Команда АЛУ начала выполняться, тем временем сделали выборку [SP], там пока нолик сидит.

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


По тактам как будто бы всё верно, однако результат пришёл кривой, 0xFFF9 = -7. Тут должна была быть просто семёрка, со знаком "плюс" разумеется. Семёрка - потому что (-695/32768)^2 * 32768 / 2 ≈ 7,37037. (У нас при умножениях со знаком используется формат 1.15, т.е число -32768..+32767 интерпретируется как -1..≈+1, результат также в этом формате, и берём мы квадрат числа, делёный пополам).


Что ж, начало многообещающее, но глюки есть. Может, это и хорошо. Заработай оно вообще с первого раза - это было бы очень подозрительно...
Tags: ПЛИС, Программки, работа, странные девайсы
Subscribe

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments