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?