nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

Испытания новой АЛУ, сортировка против часовой стрелки

Опробуем вот этот код:

;состояние регистров к данному моменту:
;X = Y =Z = Points2D
;i = индекс наиболее отдалённой точки  (не понадобится)
;j=k=0
;Inv неизвестен
;C = [Fx0]  (не понадобится)
;Acc = разность полусумм квадратов (не понадобится)
SortCCW		proc
;Далее: нужно расставить оставшиеся точки против часовой стрелки
;Первый шаг к этому: переместить начало координат в МДД3, который сейчас по нулевому индексу
	X	Fx1	;чтобы индекс от 2 до 0 соотв. точкам (Fx1,Fy1) ... (Fx3, Fy3)
	Z	Fx2	;чтобы иметь сдвинутую на 1 адресацию
;потом вернём как ни в чём не бывало, у нас фикс. точка, все правила арифм. соблюдаются						
	CALL	ShiftOrigin
;вот теперь пора сортировать!
	j	1
	i	1
;Делаем "сдвинутую" адресацию [Fx2 + j], т.е j=1 указывает на 3-ю точку, j=0 - на 2-ю.
;но при этом, i = 1 указывает на 2-ю, i=0 - на 1-ю
;а нулевую пока вообще не рассматриваем - она на своём месте!
;хотим на позицию j+2 поставить "самую большую", для этого надо выбрать между j+1,...1
;здесь заведомо k=0, так что X+2i / X+2j не нужны!
@@loop:	C	[Z+2j+k]
	MUL	[X+2i+1]
	C	[Z+2j+1]
	FMS	[X+2i+k]	;нахождение "векторного произведения"
	JL	@@skip
	;меняем местами, как обычно, точки с коорд. i и с коорд. j
	CALL 	SwapPoints
@@skip:	iLOOP	@@loop
	jLOOP	@@loop
				
	CALL	ShiftOrigin		
	;а теперь ещё надо два последних поменять местами, для совместимости с алг. сопровождения
	;здесь i=j=k=0
	X	Fx3
	CALL	SwapPoints
SortCCW		endp


Но ещё здесь вызывается процедура ShiftOrigin:
;отражает точки относительно наиболее отдалённой. Повторное применение этой операции возврщает точки на место!
;состояние регистров к данному моменту:
;X = Points2D+2 = Fx1 (т.е указывает на точку с индексом 1)
;Y = Points2D (точка с индексом 0)
;Z неважен (вообще Fx2, точка с индексом 2)
;i неважен (вообще это индекс наиболее отдалённой точки, а потом 0)
;j,k неважны (вообще j=k=0)
;Inv неизвестен
;C неважен (вообще [Fx0] при первом вызове, одна из коорд. при втором) 
;Acc неважен (вобще разность полусумм квадратов при первом вызове, результат сравн. при втором)
ShiftOrigin proc
;надо из всех точек вычесть коорд. наиболее отдалённой (с индексом 0)
;кроме неё самой, разумеется
		k		1
@@k_loop:	i		2
@@i_loop:	Acc		[Y+k]
		SUB		[X+2i+k]
		[X+2i+k]	Acc
		iLOOP		@@i_loop
		kLOOP		@@k_loop
		JMP		[--SP]
ShiftOrigin endp


На старом АЛУ всё это безобразие выполняется (до выхода из нижнего ShiftOrigin) 13,08 мкс, или 327 тактов. Происходит 3 сравнения, и на самом первом из них (индексы 1 и 2) точки меняются местами.

Для начала сами прикинем, насколько быстрее здесь может оказаться новое АЛУ и как можно "разогнать" этот код, не увеличивая его размер. Потом запустим симуляцию.


Начнём с ShiftOrigin. Загрузка значения в аккумулятор выполнится за свои 3 такта. Вычитание - на такт меньше (наложится на предыдущую команду). Дальше, увы, мы встанем, чтобы результат сразу положить в память, и только потом заняться циклами. И вряд ли тут что-то можно поделать, ведь в память надо заносить, пока индексы i,k не поменялись!

Но поскольку всё это происходит в цикле, то 6 тактов мы всё же экономим на каждом вызове ShiftOrigin. Мы эту процедуру вызываем дважды, перед сортировкой и после неё (вернуть всё на место), так что 12 тактов.

Теперь сама сортировка. Тут мы ищем "векторное произведение" двумерных векторов, это ПСЕВДОСКАЛЯР :) указывающий, идут ли точки по часовой стрелке. Первая команда, "C", выполняется за 1 такт, как обычно. Вторая, MUL, за 18 тактов. Третья, "C", целиком накладывается на вторую, так что 1 такт мы экономим. Четвёртая, FMS (Fused Multiply-Subtract) выполняется положенные 18 тактов, и команда условного перехода, JL, "застревает" на всё это время, и ещё на один такт, пока мы не получим результат.

Можно сделать упрощение, не связанное с АЛУ. Видно, как мы мучительно "перепрыгиваем" через команду CALL SwapPoints. Действительно, если использовать нормальную "конвенцию" вызова процедуры через [SP++] и возврат на [--SP], ничего лучше не получится - условно переходить на процедуру неприятно, т.к неизвестно куда стек уедет.

А вот если договориться вызывать эту процедуру с занесением адреса возврата в [SP] (без сдвижки) и возвращаться по [SP], то можно адрес возврата занести перед началом циклов сортировки, и он будет оставаться неизменным, а две команды

JL   @@skip
CALL SwapPoints


заменить на
JGE  SwapPoints


Условный вызов процедуры - это круто :)

Размер кода не увеличивается, зато всевозможных конвейерных заморочек гораздо меньше! Где-то 1-2 такта на итерацию должны выиграть (лениво точно считать).

Итераций всего 3, так что ожидаем 6-9 тактов выигрыша ещё здесь, итого 18-21.

Можно было бы ещё попытаться в цикл запихать какие-то инструкции, которые там выполнятся "нахаляву" (всё равно АЛУ ждать), но это не так-то просто, там 4 команды подряд с обращением к памяти, поэтому тот же "[SP] SwapPoints" туда не всунется - возникнет конфликт по адресной шине памяти.

Вот немудрено, что я в своё время не горел желанием переделывать АЛУ - сам по себе факт, что оно позволит процессору продолжить работу, НЕ ДАЁТ ВЫИГРЫША в этих алгоритмах, где после вычислений мы сразу куда-то сбрасываем результат, поэтому дождаться окончания всё равно приходится. Вот "конвейеризация" (возможность начать выполнять следующую команду, не закончив предыдущую) тихонечко приносит свои плоды :)

Что ж, переделываем процедуру SwapPoints, заменяя [--SP] на [SP], соответственно в FindMDD3 заменяем CALL SwapPoints на [SP] Call(SwapPoints), ну и в процедуре сортировки небольшие изменения:
SortCCW		proc
;Далее: нужно расставить оставшиеся точки против часовой стрелки
;Первый шаг к этому: переместить начало координат в МДД3, который сейчас по нулевому индексу
		X	Fx1	;чтобы индекс от 2 до 0 соотв. точкам (Fx1,Fy1) ... (Fx3, Fy3)
		Z	Fx2	;чтобы иметь сдвинутую на 1 адресацию
;потом вернём как ни в чём не бывало, у нас фикс. точка, все правила арифм. соблюдаются						
		CALL	ShiftOrigin
;вот теперь пора сортировать!
		[SP]	@@loopEnd
		j	1
		i	1
;Делаем "сдвинутую" адресацию [Fx2 + j], т.е j=1 указывает на 3-ю точку, j=0 - на 2-ю.
;но при этом, i = 1 указывает на 2-ю, i=0 - на 1-ю
;а нулевую пока вообще не рассматриваем - она на своём месте!
;хотим на позицию j+2 поставить "самую большую", для этого надо выбрать между j+1,...1
;здесь заведомо k=0, так что X+2i / X+2j не нужны!
@@loop:		C	[Z+2j+k]
		MUL	[X+2i+1]				
		C	[Z+2j+1]
		FMS	[X+2i+k]	;нахождение "векторного произведения"
		JGE	SwapPoints
@@loopEnd:	iLOOP	@@loop
		jLOOP	@@loop
						
		CALL	ShiftOrigin		
		;а теперь ещё надо два последних поменять местами, для совместимости с алг. сопровождения
		;здесь i=j=k=0
		X	Fx3
		[SP]	Call(SwapPoints)
SortCCW		endp


Попробуем теперь всё это запустить на новом АЛУ. Случился очередной Can't find fit, когда я использовал простейший алгоритм построения "непосредственных значений", поэтому включил более сложный (он ШИКАРНО работал на малом количестве непосредственных значений, но потом ему резко плохело по мере их роста вширь и в количестве). Он очень хорошо сработал, причём понял, что байтовый режим обращения к памяти мне не нужен - и не стал его делать. Но когда я и в QuatCore этот режим отключил - опять, несмотря на сильное сокращение ЛЭ, выскочило Can't find fit.

В итоге я разозлился - и выполнил эту "таблицу непосредственных значений" не в виде логики, а тупо как ROM 128x16. Занимает один блок памяти, причём лишь половину, что несколько обидно, зато в кои-то веки всё ядро уместилось в 499 ЛЭ и отсинтезировалось моментально!

Что ж, посмотрим:


Приведём листинг по первому кусочку:
        SortCCW     proc
17  CD09   X       Fx1 ;чтобы индекс от 2 до 0 соотв. точкам (Fx1,Fy1) ... (Fx3, Fy3)
18  ED0A   Z       Fx2 ;чтобы иметь сдвинутую на 1 адресацию
19  F3B5   CALL    ShiftOrigin
1A  FC0B   [SP]    @@loopEnd
1B  A104   j       1


И ещё листинг кусочка оперативной памяти, с которым будем ковыряться:
Fx0:        18   53
Fy0:        19   -7
Fx1:        1A   480
Fy1:        1B   -30
Fx2:        1C   -539
Fy2:        1D   -302
Fx3:        1E   400
Fy3:        1F   -997


Теперь смотрим. В регистр X заносим адрес Fx1, то есть 0x1A. В регистр Z: адрес Fx2, или 0x1C. Ну и прыгаем в ShiftOrigin, вот его листинг:

ShiftOrigin proc
95  A204             k           1
96  A00B  @@k_loop:  i           2   ;как всегда, чтобы Y и X
97  80D8  @@i_loop:  Acc         [Y+k]
98  83C9             SUB         [X+2i+k]
99  C980             [X+2i+k]    Acc
9A  A82D             iLOOP       @@i_loop
9B  AA2E             kLOOP       @@k_loop
9C  B0FF             JMP         [--SP]
ShiftOrigin endp


Присваиваем k=1, i=2. Пока идёт второе присвоение, делаем выборку из памяти [Y+k], выходит 0xFC1B = -997, это Y-координата самой отдалённой точки, которую теперь поместили на нулевую позицию.

Команда Acc не тормозит нас, на такт застреваем из-за выборки [X+2i+k], это 0xFFF9 = -7. Да, эти две точки мы поменяли местами тогда.

На вычитании застреваем на 4 такта, но на первом одновременно заканчивается предыдущая команда, а последний такт ждём, чтобы запихнуть правильное значение из Acc на шину данных. Там оказывается 0xFC22 = -990, всё нормально работает.

Ладно, тут всё нормально, запишем, что сейчас у нас должно оказаться в памяти:
Fx0:        18   400  (0x0190)
Fy0:        19   -997 (0xFC1B)
Fx1:        1A   -80  (0xFFB0)
Fy1:        1B   -967 (0xFC39)
Fx2:        1C   939  (0x03AB)
Fy2:        1D   -695 (0xFD49) 
Fx3:        1E   347  (0x015B)
Fy3:        1F   -990 (0xFC22)


Возвратимся к сортировке:


И листинг этого кусочка:
1A  FC0B              [SP]    @@loopEnd
1B  A104              j       1
1C  A004              i       1
1D  8AEA  @@loop:     C       [Z+2j+k]
1E  90C1              MUL     [X+2i+1]                
1F  8AE2              C       [Z+2j+1]
20  93C9              FMS     [X+2i+k]    ;нахождение "векторного произведения"
21  BC0C              JGE     SwapPoints
22  A80D  @@loopEnd:  iLOOP   @@loop


Начинается неплохо: на стек кладётся адрес возврата, 0x22. Выполняется j=1, i=1, производится выборка памяти [Z+2j+k], значение 0x15B = 347. Оно кладётся в регистр C, и в этом время производится выборка памяти [X+2i+1], значение 0xFD49=-695. (для векторного произведения нужно брать значения "крест накрест", сейчас вот Fx3 и Fy2)

Следующая команда: умножение, MUL. Она нас не останавливает, задержка на такт из-за выборки памяти [Z+2j+1] = 0xFC22 = -990.

И наконец, мы добираемся до команды C, и в это же время выборка памяти [X+2i+k] = 0x3AB = 939. Тут мы застреваем, поскольку ещё не выполнилась MUL. Она должна занимать 18 тактов, причём 2 уже выполнились. На последнем такте выполняется и команда С.

Теперь идёт команда FMS, и в это же время на шину данных приходит адрес процедуры SwapPoints, 0x8E. Эта команда нас не останавливает, что пока правильно.

А вот на JGE происходит какая-то полная фигня! Мы вроде как останавливаемся, ожидая окончания работы АЛУ, но как-то уж слишком быстро мы оттуда уходим!

Похоже, что мы забыли "самозапереться"! Чтобы не возникало "комбинаторных обратных связей", QuatCorePC при "застревании" на JGE из-за ожидания АЛУ выдаёт только SrcStall, чтобы остановить "соседа". Но он и сам должен остановиться! Сейчас выходит, что стоит лишь прийти правильному знаку из АЛУ (такому, что разрешит прыжок) - и прыжок-таки начнёт выполняться! Именно об этом свидетельствует SrcDiscard=1, за которым начинается DestDiscard = 1. Вот только счётчик инструкций у нас замирает из-за продолжающегося SrcStall, поэтому происходит что-то совсем непонятное.

Ещё разок взглянем на строки внутри QuatCorePCpipelineRelJumpDecision.v:
wire isFlags = isOurOp & DestAddr[4];
wire DoJL	= isFlags & (~DestAddr[1]) & (isNeg ^ DestAddr[2]);
wire DoJO	= isFlags & DestAddr[1] & (isOFLO ^ DestAddr[2]);

assign DoJump = DoiLOOP | DojLOOP | DokLOOP | DoJik | DoJL | DoJO;

assign SrcStallReq = (isFlags & (~DestAddr[1]) & ALUsbusy) | (isFlags & DestAddr[1] & ALUbusy);


Если здесь возникнет DoJump, то прыжок начнёт выполняться, даже если при этом SrcStallReq = 1 ! Так что надо и сюда добавить "блокировку":

wire isFlags = isOurOp & DestAddr[4];
wire DoJL	= (~ALUsbusy) & isFlags & (~DestAddr[1]) & (isNeg ^ DestAddr[2]);
wire DoJO	= (~ALUbusy) & isFlags & DestAddr[1] & (isOFLO ^ DestAddr[2]);

assign DoJump = DoiLOOP | DojLOOP | DokLOOP | DoJik | DoJL | DoJO;

assign SrcStallReq = (isFlags & (~DestAddr[1]) & ALUsbusy) | (isFlags & DestAddr[1] & ALUbusy);


Теперь вот так:


По тактам всё совпадает, только вот незадача - прыжок не осуществляется! Ведь на старой АЛУ в этом месте процедура вызывалась! Да и если "ручками" посчитать выражение
347*(-695) - (-990)*939 = 688445
Оно явно положительное, и условный переход JGE ДОЛЖЕН БЫЛ СРАБОТАТЬ! Что за нахрен...

Сначала я думал на логику, управляющую флагом знака, что она не срабатывает, или срабатывает невовремя, но там всё худо-бедно правильно. Есть одна неточность: если младший разряд регистра C нулевой, то на самом деле мы проверим знак не самого результата, а результата + B / 65536, из-за того что регистр знака подключён к выходу сумматора, сумматор работает всегда, просто не всегда результат его работы защёлкивается в аккумулятор. Так что в "тонких случаях", когда результат зависит от самых-самых младших разрядов, может сыграть, но у нас пока всё дубово, пущай пока так.

Нет, всё дело в управлении регистром C:
//Cmode=0x - idle
//	10 - shift
//	11 - load
assign Cmode[1] = (isIdle | isAdd | finished)? isOurAddr & DestAddr[3] & (((~DestAddr[4])&(~DestAddr[2])&DestAddr[1])|(DestAddr[4]&DestAddr[2])) : isMult;								
assign Cmode[0] = ~isMult;


Когда команда C (или SQRxx) приходит во время состояния sIdle или sAdd (т.е на последнем такте сложения, вычитания, взятия модуля и прочих "коротких" команд), всё хорошо, тогда Cmode = 11, что означает загрузку из шины данных нового значения.

А вот если состояние было sMult и шёл последний такт умножения, так что уже "зажглось" finished, то выйдет Cmode = 10, что вообще-то означает циклический сдвиг! И вся наша арифметика катится в тартарары...

Придётся усложнить код немного:
//Cmode=0x - idle
//	10 - shift
//	11 - load
wire LoadCCommand = isOurAddr & DestAddr[3] & (((~DestAddr[4])&(~DestAddr[2])&DestAddr[1])|(DestAddr[4]&DestAddr[2]));
assign Cmode[1] = (isIdle | isAdd | finished)? LoadCCommand : isMult;								
assign Cmode[0] = (~isMult) | (finished & LoadCCommand);


Попробуем теперь:


УРА! Вот теперь знак принимается правильный. Внизу для отладки выведены флаг знака, isNeg, и управляющий сигнал DSena, т.е Debug Sign enable, я проверял, что эта "подсистема" работает корректно.

И тут же вызывается процедура SwapPoints. Мы проверяли взаимное положение последних двух точек с координатами (939;-695) и (347;-990), или в Hex: (0x03AB; 0xFD49) и (0x015B; 0xFC22), и сейчас они должны поменяться местами. Вот листинг:

SwapPoints  proc
8E  A204          k           1
8F  8900          NOP         0   ;хотим избежать warning'ов
90  8AEA  @@swap: C           [Z+2j+k]
91  EAC9          [Z+2j+k]    [X+2i+k]
92  C983          [X+2i+k]    C
93  AA2C          kLOOP       @@swap
94  B0FC          JMP         [SP]
SwapPoints  endp 


Тут мы делаем "по-старинке", через дополнительный регистр C. Если помните, отключив Hazard'ы, можно "чудеса творить", но когда это обмен "память-память", то самую чуточку не складывается. Там даже адрес один и тот же, и одновременное чтение из памяти и запись в память, но у памяти Flex10k поведение немножко не такое, как нам надо. Можно было бы поставить очередной интерлок, который задержит такую операцию на один такт, и тем самым мы ровно здесь сэкономим одну строку. Но пока лениво...

Мы видим, что в регистр C отправилось значение 0xFC22, на его место (в память): 0xFD49, и наконец, на место 0xFD49 из регистра приходит 0xFC22, после чего прыгаем на @@swap = 0x90.

Глянем, что возвращаемся куда и ожидали:


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

И затем две итерации проходят уже без вызова процедуры, что соответствует выполнению на старом АЛУ. Наконец, повторно вызывается процедура ShiftOrigin, чтобы вернуть все точки на свои места (мы зеркально отразили их от наиболее отдалённой точки, сделав её "началом координат", чтобы упростить математику):


И остаётся последний SwapPoints, который у нас "на перспективу". Мы ожидаем, что на дальней дистанции будем использовать эти 4 точки, а по мере приближения начнут разрешаться отдельные точки внутри мишени ближней дистанции, и если эту самую точку, МБД, положить "в самый конец", а 8 отдельных точек - в самое начало, ПЕРЕД нашими тремя, то выбором правильного интервала получится единообразно обработать обе ситуации.


Фух, исправили ещё две ошибки, сейчас оно работает правильно, и "сортировка" (второй этап аффинного алгоритма) выполнилась за 12,24 мкс, или 306 тактов, что на 21 такта меньше, чем раньше. Ровно столько мы и ожидали! Итого, улучшение на 6,4%, мелочь, а приятно. Самое драматическое улучшение мы ожидаем на алгоритме обнаружения пятен, ради которого всё это и затеяли. Но его куда тяжелее отлаживать, поэтому пока тренируемся на кошках.

Дальше на очереди: перемножение матриц для нахождения матрицы аффинного преобразования.
Tags: ПЛИС, программки, работа, странные девайсы
Subscribe

Recent Posts from This Journal

  • Огарь крупным планом

    Прям как на пьедестале, гордый такой, здоровенный, песенку спел, потом спустился водички попить, небось горло пересохло. Только на видео я заметил,…

  • Я создал монстра!

    Вот нормальная счастливая пара разъёмов ОНЦ-БС-1-10/14-Р12-2-В и ОНЦ-БС-1-10/14-В1-2-В: У розетки кроме основного выступа, отмечающего "верх",…

  • Нахождение двух самых отдалённых точек

    Пока компьютер долго и упорно мучал симуляцию, я пытался написать на ассемблере алгоритм захвата на ближней дистанции. А сейчас на этом коде можно…

  • Слишком общительный счётчик

    Вчера я чуть поторопился отсинтезировать проект,параметры не поменял: RomWidth = 8 вместо 7, RamWidth = 9 вместо 8, и ещё EnableByteAccess=1, чтобы…

  • Балансируем конвейер QuatCore

    В пятницу у нас всё замечательно сработало на симуляции, первые 16 миллисекунд полёт нормальный. А вот прошить весь проект на ПЛИС и попробовать "в…

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

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

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments