performance - multiplicacion - La forma más efectiva de restar una matriz de otra

suma de matrices

Question

Tengo el siguiente código que es el cuello de botella en una parte de mi aplicación. Todo lo que hago es restar en Matriz de otro. Ambas matrices tienen más de 100000 elementos. Estoy tratando de encontrar una manera de hacer que este sea más eficiente.

var
Array1, Array2 : array of integer;
.....
// Code that fills the arrays
.....
for ix := 0 to length(array1)-1
Array1[ix] := Array1[ix] - Array2[ix];
end;

¿Alguien tiene una sugerencia?

Answer 1

Al ejecutar esto en múltiples hilos, con esa gran matriz se obtendrá una aceleración lineal. Es embarazosamente paralelo como dicen.

Answer 2

Ejecutar la resta en más subprocesos suena bien, pero la sunstraction de 100K enteros no requiere mucho tiempo de CPU, así que tal vez subprocesos ... Sin embargo, los subprocesos de configuración también tienen mucha sobrecarga, por lo que las matrices cortas tendrán una productividad más lenta en hilos paralelos que ¡solo un hilo (principal)!

¿Se apagó en la configuración del compilador, desbordamiento y comprobación de rango?

Puedes intentar usar asm rutine, es muy simple ...

Algo como:

procedure SubArray(var ar1, ar2; length: integer);
asm
//length must be > than 0!
push ebx
lea ar1, ar1 -4
lea ar2, ar2 -4
@Loop:
mov ebx, [ar2 + length *4]
sub [ar1 + length *4], ebx
dec length
//Here you can put more folloving parts of rutine to more unrole it to speed up.
jz @exit
mov ebx, [ar2 + length *4]
sub [ar1 + length *4], ebx
dec length
//
jnz @Loop
@exit:
pop ebx
end;
begin
SubArray(Array1[0], Array2[0], length(Array1));

Puede ser mucho más rápido ...

EDITAR: procedimiento agregado con instrucciones SIMD. Este procedimiento solicita soporte de CPU SSE. Puede tomar 4 enteros en el registro XMM y restar de una vez. También existe la posibilidad de usar movdqa en movdqa lugar movdqu es más rápido, pero primero debe asegurarse de alineación de 16 bytes. También puede quitar el par de XMM como en mi primer caso de asm. (Estoy interesado en la medición de la velocidad :))

var
array1, array2: array of integer;
procedure SubQIntArray(var ar1, ar2; length: integer);
asm
//prepare length if not rounded to 4
push ecx
shr length, 2
jz @LengthToSmall
@Loop:
movdqu xmm1, [ar1] //or movdqa but ensure 16b aligment first
movdqu xmm2, [ar2] //or movdqa but ensure 16b aligment first
psubd xmm1, xmm2
movdqu [ar1], xmm1 //or movdqa but ensure 16b aligment first
add ar1, 16
add ar2, 16
dec length
jnz @Loop
@LengthToSmall:
pop ecx
push ebx
and ecx, 3
jz @Exit
mov ebx, [ar2]
sub [ar1], ebx
dec ecx
jz @Exit
mov ebx, [ar2 + 4]
sub [ar1 + 4], ebx
dec ecx
jz @Exit
mov ebx, [ar2 + 8]
sub [ar1 + 8], ebx
@Exit:
pop ebx
end;
begin
//Fill arrays first!
SubQIntArray(Array1[0], Array2[0], length(Array1));

Answer 3

No es una respuesta real a tu pregunta, pero investigaría si pudiera hacer la resta ya en algún momento al llenar los conjuntos con valores. Opcionalmente, incluso consideraría una tercera matriz en la memoria para almacenar el resultado de la resta. En la informática moderna, el "costo" de la memoria es considerablemente menor que el "costo" del tiempo que lleva realizar una acción extra en la memoria.

En teoría, obtendrás al menos un pequeño rendimiento cuando la resta se pueda realizar mientras los valores estén todavía en registros o caché del procesador, pero en la práctica podrías tropezar con algunos trucos que podrían mejorar el rendimiento de todo el algoritmo.

Answer 4

No soy un experto en ensamblaje, pero creo que los siguientes son casi óptimos si no se tienen en cuenta las instrucciones SIMD o el procesamiento paralelo, lo último se puede lograr fácilmente pasando porciones de la matriz a la función.

me gusta
Thread1: SubArray (ar1 [0], ar2 [0], 50);
Thread2: SubArray (ar1 [50], ar2 [50], 50);

procedure SubArray(var Array1, Array2; const Length: Integer);
var
ap1, ap2 : PInteger;
i : Integer;
begin
ap1 := @Array1;
ap2 := @Array2;
i := Length;
while i > 0 do
begin
ap1^ := ap1^ - ap2^;
Inc(ap1);
Inc(ap2);
Dec(i);
end;
end;
// similar assembly version
procedure SubArrayEx(var Array1, Array2; const Length: Integer);
asm
// eax = @Array1
// edx = @Array2
// ecx = Length
// esi = temp register for array2^
push esi
cmp ecx, 0
jle @Exit
@Loop:
mov esi, [edx]
sub [eax], esi
add eax, 4
add edx, 4
dec ecx
jnz @Loop
@Exit:
pop esi
end;
procedure Test();
var
a1, a2 : array of Integer;
i : Integer;
begin
SetLength(a1, 3);
a1[0] := 3;
a1[1] := 1;
a1[2] := 2;
SetLength(a2, 3);
a2[0] := 4;
a2[1] := 21;
a2[2] := 2;
SubArray(a1[0], a2[0], Length(a1));
for i := 0 to Length(a1) - 1 do
Writeln(a1[i]);
Readln;
end;

Answer 5

Tenía mucha curiosidad sobre la optimización de velocidad en este caso simple. Por lo tanto, he realizado 6 procedimientos simples y medido el tic de la CPU y el tiempo en el tamaño de matriz 100000;

1. Procedimiento Pascal con opción de compilación Rango y desbordamiento Comprobación activada
2. Procedimiento Pascal con opción de compilación Rango y desbordamiento
3. Procedimiento clásico de ensamblaje x86.
4. Procedimiento de ensamblador con instrucciones SSE y movimiento de 16 bytes sin alinear .
5. Procedimiento de ensamblador con instrucciones de SSE y movimiento alineado de 16 bytes .
6. Ensamblador 8 veces desenrollado lazo con instrucciones SSE y movimiento alineado de 16 bytes .

Verifique los resultados en la imagen y el código para más información.

Para obtener una alineación de memoria de 16 bytes, primero delimita el punto en la directiva ''FastMM4Options.inc'' del archivo {$ .define Align16Bytes}.

program SubTest;
{$APPTYPE CONSOLE}
uses
//In file ''FastMM4Options.inc'' delite the dot in directive {$.define Align16Bytes}
//to get 16 byte memory alignment!
FastMM4,
windows,
SysUtils;
var
Ar1 :array of integer;
Ar2 :array of integer;
ArLength :integer;
StartTicks :int64;
EndTicks :int64;
TicksPerMicroSecond :int64;
function GetCpuTicks: int64;
asm
rdtsc
end;
{$R+}
{$Q+}
procedure SubArPasRangeOvfChkOn(length: integer);
var
n: integer;
begin
for n := 0 to length -1 do
Ar1[n] := Ar1[n] - Ar2[n];
end;
{$R-}
{$Q-}
procedure SubArPas(length: integer);
var
n: integer;
begin
for n := 0 to length -1 do
Ar1[n] := Ar1[n] - Ar2[n];
end;
procedure SubArAsm(var ar1, ar2; length: integer);
asm
//Length must be > than 0!
push ebx
lea ar1, ar1 - 4
lea ar2, ar2 - 4
@Loop:
mov ebx, [ar2 + length * 4]
sub [ar1 + length * 4], ebx
dec length
jnz @Loop
@exit:
pop ebx
end;
procedure SubArAsmSimdU(var ar1, ar2; length: integer);
asm
//Prepare length
push length
shr length, 2
jz @Finish
@Loop:
movdqu xmm1, [ar1]
movdqu xmm2, [ar2]
psubd xmm1, xmm2
movdqu [ar1], xmm1
add ar1, 16
add ar2, 16
dec length
jnz @Loop
@Finish:
pop length
push ebx
and length, 3
jz @Exit
//Do rest, up to 3 subtractions...
mov ebx, [ar2]
sub [ar1], ebx
dec length
jz @Exit
mov ebx, [ar2 + 4]
sub [ar1 + 4], ebx
dec length
jz @Exit
mov ebx, [ar2 + 8]
sub [ar1 + 8], ebx
@Exit:
pop ebx
end;
procedure SubArAsmSimdA(var ar1, ar2; length: integer);
asm
push ebx
//Unfortunately delphi use first 8 bytes for dinamic array length and reference
//counter, from that reason the dinamic array address should start with $xxxxxxx8
//instead &xxxxxxx0. So we must first align ar1, ar2 pointers!
mov ebx, [ar2]
sub [ar1], ebx
dec length
jz @exit
mov ebx, [ar2 + 4]
sub [ar1 + 4], ebx
dec length
jz @exit
add ar1, 8
add ar2, 8
//Prepare length for 16 byte data transfer
push length
shr length, 2
jz @Finish
@Loop:
movdqa xmm1, [ar1]
movdqa xmm2, [ar2]
psubd xmm1, xmm2
movdqa [ar1], xmm1
add ar1, 16
add ar2, 16
dec length
jnz @Loop
@Finish:
pop length
and length, 3
jz @Exit
//Do rest, up to 3 subtractions...
mov ebx, [ar2]
sub [ar1], ebx
dec length
jz @Exit
mov ebx, [ar2 + 4]
sub [ar1 + 4], ebx
dec length
jz @Exit
mov ebx, [ar2 + 8]
sub [ar1 + 8], ebx
@Exit:
pop ebx
end;
procedure SubArAsmSimdAUnrolled8(var ar1, ar2; length: integer);
asm
push ebx
//Unfortunately delphi use first 8 bytes for dinamic array length and reference
//counter, from that reason the dinamic array address should start with $xxxxxxx8
//instead &xxxxxxx0. So we must first align ar1, ar2 pointers!
mov ebx, [ar2]
sub [ar1], ebx
dec length
jz @exit
mov ebx, [ar2 + 4]
sub [ar1 + 4], ebx
dec length
jz @exit
add ar1, 8 //Align pointer to 16 byte
add ar2, 8 //Align pointer to 16 byte
//Prepare length for 16 byte data transfer
push length
shr length, 5 //8 * 4 subtructions per loop
jz @Finish //To small for LoopUnrolled
@LoopUnrolled:
//Unrolle 1, 2, 3, 4
movdqa xmm4, [ar2]
movdqa xmm5, [16 + ar2]
movdqa xmm6, [32 + ar2]
movdqa xmm7, [48 + ar2]
//
movdqa xmm0, [ar1]
movdqa xmm1, [16 + ar1]
movdqa xmm2, [32 + ar1]
movdqa xmm3, [48 + ar1]
//
psubd xmm0, xmm4
psubd xmm1, xmm5
psubd xmm2, xmm6
psubd xmm3, xmm7
//
movdqa [48 + ar1], xmm3
movdqa [32 + ar1], xmm2
movdqa [16 + ar1], xmm1
movdqa [ar1], xmm0
//Unrolle 5, 6, 7, 8
movdqa xmm4, [64 + ar2]
movdqa xmm5, [80 + ar2]
movdqa xmm6, [96 + ar2]
movdqa xmm7, [112 + ar2]
//
movdqa xmm0, [64 + ar1]
movdqa xmm1, [80 + ar1]
movdqa xmm2, [96 + ar1]
movdqa xmm3, [112 + ar1]
//
psubd xmm0, xmm4
psubd xmm1, xmm5
psubd xmm2, xmm6
psubd xmm3, xmm7
//
movdqa [112 + ar1], xmm3
movdqa [96 + ar1], xmm2
movdqa [80 + ar1], xmm1
movdqa [64 + ar1], xmm0
//
add ar1, 128
add ar2, 128
dec length
jnz @LoopUnrolled
@FinishUnrolled:
pop length
and length, $1F
//Do rest, up to 31 subtractions...
@Finish:
mov ebx, [ar2]
sub [ar1], ebx
add ar1, 4
add ar2, 4
dec length
jnz @Finish
@Exit:
pop ebx
end;
procedure WriteOut(EndTicks: Int64; Str: string);
begin
WriteLn(Str + IntToStr(EndTicks - StartTicks)
+ '' Time: '' + IntToStr((EndTicks - StartTicks) div TicksPerMicroSecond) + ''us'');
Sleep(5);
SwitchToThread;
StartTicks := GetCpuTicks;
end;
begin
ArLength := 100000;
//Set TicksPerMicroSecond
QueryPerformanceFrequency(TicksPerMicroSecond);
TicksPerMicroSecond := TicksPerMicroSecond div 1000000;
//
SetLength(Ar1, ArLength);
SetLength(Ar2, ArLength);
//Fill arrays
//...
//Tick time info
WriteLn(''CPU ticks per mikro second: '' + IntToStr(TicksPerMicroSecond));
Sleep(5);
SwitchToThread;
StartTicks := GetCpuTicks;
//Test 1
SubArPasRangeOvfChkOn(ArLength);
WriteOut(GetCpuTicks, ''SubAr Pas Range and Overflow Checking On, Ticks: '');
//Test 2
SubArPas(ArLength);
WriteOut(GetCpuTicks, ''SubAr Pas, Ticks: '');
//Test 3
SubArAsm(Ar1[0], Ar2[0], ArLength);
WriteOut(GetCpuTicks, ''SubAr Asm, Ticks: '');
//Test 4
SubArAsmSimdU(Ar1[0], Ar2[0], ArLength);
WriteOut(GetCpuTicks, ''SubAr Asm SIMD mem unaligned, Ticks: '');
//Test 5
SubArAsmSimdA(Ar1[0], Ar2[0], ArLength);
WriteOut(GetCpuTicks, ''SubAr Asm with SIMD mem aligned, Ticks: '');
//Test 6
SubArAsmSimdAUnrolled8(Ar1[0], Ar2[0], ArLength);
WriteOut(GetCpuTicks, ''SubAr Asm with SIMD mem aligned 8*unrolled, Ticks: '');
//
ReadLn;
Ar1 := nil;
Ar2 := nil;
end.

...

El procedimiento de asm más rápido con 8 instrucciones SIMD desenrolladas solo requiere 68us y es aproximadamente 4 veces más rápido que el procedimiento de Pascal.

Como podemos ver, el procedimiento de bucle de Pascal probablemente no es crítico, solo lleva unos 277us (desbordamiento y rango de comprobación desactivados) en la CPU de 2,4 GHz a 100000 sustracciones.

¿Entonces este código no puede ser un cuello de botella?