Hirdetés

2024. március 29., péntek

Gyorskeresés

Hozzászólások

(#34) P.H.


P.H.
senior tag

Nem hagy(ott) nyugodni a kisördög. A teljesen 32 bitesre átírással megnyílt pár lehetőség: külön jelölő byte az oszlopnak, külön a sornak, külön a bevezető sorjelölésnek, így sikerült drasztikusan csökkenteni a load-op-store utasításokat, sima store-ral helyettesítve őket.

Kombinálva ezt az AMD 2 load/cycle felépítésével, sikerült elérni a 30 db 25x25-ös mátrix per ezredmásodperc teljesítményt, 2.6 GHz-es Shanghai-on.

Csak Intel-en ne lenne fele ilyen gyors így, 2.5 GHz Core2-n tesztelve... (Sandy Bridge-ig, ami ugyancsak 2 load/cycle felépítésű - lesz -).

Az algoritmuson látható, hogy egyetlen szorzáson kívül összeadás, kivonásnál és bitmanipulációknál bonyolultabb utasítás nincs benne benne (ADC, SBB és CMOVcc viszont elég sok van), a skálázott memóriahozzáférést sem használom már ki, viszont egy pointer-rel két adatterületet is címzek, egyet-egyet a pozitív és a negatív oldalán.

pushad
lea edx,[ebp*08h]
mov ebx,offset(MARKS)
xor ecx,ecx
lea edi,[ebx+ebp*04h]
imul ebp,BYTE(-4)
@mark0:
sub edx,04h
mov [ebx+edx],ecx
jg @mark0
@@REDUCE_ROWS:
mov ebx,ebp
@rowmin:
mov esi,01000000h
mov ecx,ebp
xor edx,edx
@findrowmin:
cmp esi,[eax]
cmovz edx,ecx
cmova esi,[eax]
add ecx,04h
lea eax,[eax+04h]
jnz @findrowmin
sub ecx,ebp
cmp esi,01000000h
jz @specific
add eax,ebp
@subrow:
xor edx,edx
cmp byte ptr [eax+03h],00h
cmovz edx,esi
sub [eax],edx
sub ecx,04h
lea eax,[eax+04h]
jnz @subrow
jmp @reducenxrow
@specific:
test edx,edx
jz @@ABNORMAL_EXIT
bts dword ptr [edi+edx],00h
jnc @mark
@@ABNORMAL_EXIT:
add esp,20h
xor eax,eax
mov edx,7FFFFFFFh
stc
ret
@mark:
add ecx,ebx
sub dword ptr [esp+__SYS0],01h
mov byte ptr [edi+ebx+02h],01h
mov [edi+ecx],edx
jz @count_result_STACK
@reducenxrow:
add ebx,04h
jnz @rowmin
@@RECUDE_COLUMNS:
sub ebx,04h
sub eax,04h
cmp ebx,ebp
jl @@2ND_STEP
test byte ptr [edi+ebx],01h
jnz @@RECUDE_COLUMNS
mov edx,01000000h
mov ecx,ebp
@findcolmin:
cmp edx,[eax]
cmova edx,[eax]
add eax,ebp
add ecx,04h
jnz @findcolmin
cmp edx,01000000h
lea ecx,[ebp-04h]
jz @@ABNORMAL_EXIT
@subcol:
xor esi,esi
add ecx,04h
jz @@RECUDE_COLUMNS
sub eax,ebp
cmp byte ptr [eax+03h],00h
cmovz esi,edx
sub [eax],esi
jnz @subcol
bts dword ptr [edi+ecx],10h
jc @subcol
bts dword ptr [edi+ebx],00h
mov esi,ecx
jc @subcol
sub esi,ebp
sub dword ptr [esp+__SYS0],01h
mov byte ptr [eax+03h],01h
mov [edi+esi],ebx
jnz @subcol
jmp @count_result_STACK
@@3RD_STEP:
mov byte ptr [esi+03h],02h
mov byte ptr [edi+ebx+01h],01h
mov byte ptr [edi+edx],00h
@@2ND_STEP:
mov esi,[esp+__MTX]
sub esp,20h
mov eax,ebp
mov edx,00FFFFFFh
@nx2row:
mov bh,[edi+eax+01h]
mov ecx,ebp
@zeroinrow:
mov bl,[edi+ecx]
and bl,01h
cmp edx,[esi]
adc bl,[edi+eax+01h]
jnz @nx2col
xor edx,edx
add esp,20h
add edx,[esi]
jz @@DECIDE_NEXT_STEP
pushad
@nx2col:
add ecx,04h
lea esi,[esi+04h]
jnz @zeroinrow
add eax,04h
jnz @nx2row
@@5TH_STEP:
mov ebx,ebp
mov esi,[esp+_SAVE+__MTX]
@nx5row:
cmp byte ptr [edi+ebx+01h],00h
mov ecx,ebp
jnz @increase_double_markeds
@decrease_row_free:
bt dword ptr [edi+ecx],00h
mov al,[esi+03h]
adc al,00h
mov eax,00000000h
cmovz eax,edx
sub [esi],eax
add ecx,04h
lea esi,[esi+04h]
jnz @decrease_row_free
jmp @step5row
@increase_double_markeds:
mov al,[esi+03h]
and al,11111100b
bt dword ptr [edi+ecx],00h
sbb al,00h
mov eax,00000000h
cmovc eax,edx
add [esi],eax
add ecx,04h
lea esi,[esi+04h]
jnz @increase_double_markeds
@step5row:
add ebx,04h
jnz @nx5row
popad
xor edx,edx
@@DECIDE_NEXT_STEP:
mov ebx,eax
sub eax,ebp
add edx,[edi+eax]
jnz @@3RD_STEP
@@4TH_STEP:
mov edx,[esp+__MTX]
@colon_to_star:
mov [edi+eax],ecx
sub ecx,ebp
mov byte ptr [esi+03h],01h
lea esi,[edx+ecx]
mov eax,ebp
mov byte ptr [edi+ebx+01h],00h
@search_star_in_column:
test byte ptr [esi+03h],01h
jz @nxstar
cmp eax,ebx
jnz @0_star
@nxstar:
sub esi,ebp
add eax,04h
jnz @search_star_in_column
jmp @@1ST_STEP
@0_star:
mov ebx,eax
mov byte ptr [esi+03h],00h
sub eax,ebp
sub esi,ecx
mov dword ptr [edi+eax],00000000h
mov ecx,ebp
@search_colon_in_row:
test byte ptr [esi+03h],02h
jnz @colon_to_star
add ecx,04h
lea esi,[esi+04h]
jnz @search_colon_in_row
@error:
nop
@@1ST_STEP:
sub dword ptr [esp+__SYS0],01h
jz @count_result_STACK
mov ebx,ebp
mov ecx,[edi+00h]
jmp @nxclear
@clear_colon:
and byte ptr [esi+03h],11111101b
add eax,04h
lea esi,[esi+04h]
jnz @clear_colon
@nxclear:
mov eax,ebp
@markedrow:
cmp byte ptr [edi+ebx+01h],00h
mov esi,edx
mov dword ptr [edi+ebx],00000000h
jnz @clear_colon
sub edx,ebp
add ebx,04h
jnz @markedrow
@markcol:
mov edx,[edi+ebx]
add eax,04h
lea ebx,[ebx+04h]
mov byte ptr [edi+edx],01h
jnz @markcol
mov [edi+00h],ecx
jmp @@2ND_STEP
@count_result_STACK:
xor ecx,ecx
neg ebp
xor eax,eax
mov esi,[esp+__SAVE]
mov ebx,[esp+__MARKS]
add esp,20h
@results:
mov edx,[edi+ecx]
add ecx,04h
add edx,ebp
add eax,[esi+edx]
shr edx,02h
add esi,ebp
cmp ecx,ebp
mov [ebx],dl
lea ebx,[ebx+01h]
jnz @results

[ Szerkesztve ]

Arguing on the Internet is like running in the Special Olympics. Even if you win, you are still ... ˙˙˙ Real Eyes Realize Real Lies ˙˙˙

Copyright © 2000-2024 PROHARDVER Informatikai Kft.