Encontrar los dos enteros más grandes y cinco lo más rápido posible

9

Utilizo una variación de un filtro mediano de 5 cruces en los datos de imagen en un pequeño sistema integrado, es decir

    x
  x x x
    x

El algoritmo es realmente simple: lea 5 valores enteros sin signo, obtenga los 2 más altos, haga algunos cálculos y escriba el resultado entero sin signo.

Lo que es bueno es que los 5 valores de entrada enteros están todos en el rango de 0-20. ¡El valor entero calculado también está en el rango 0-20!

A través de la elaboración de perfiles, he descubierto que obtener los dos números más grandes es el cuello de botella, así que quiero acelerar esta parte. ¿Cuál es la forma más rápida de realizar esta selección?

El algoritmo actual usa una máscara de 32 bits con 1 en la posición dada por los 5 números y una función CLZ compatible con HW.
Debo decir que la CPU es propietaria, no está disponible fuera de mi empresa. Mi compilador es GCC pero hecho a medida para esta CPU.

He intentado averiguar si puedo usar una tabla de búsqueda, pero no he podido generar una clave que pueda usar.

Tengo combinaciones para la entrada, pero el orden no es importante, es decir, es el mismo que .215[5,0,0,0,5][5,5,0,0,0]

¡Sucede que la siguiente función hash produce un hash perfecto sin colisiones!

def hash(x):
    h = 0
    for i in x:
        h = 33*h+i
    return h

Pero el hash es enorme y simplemente no hay suficiente memoria para usarlo.

¿Hay un mejor algoritmo que pueda usar? ¿Es posible resolver mi problema usando una tabla de búsqueda y generando una clave?

Fredrik Pihl
fuente
1
¿Qué algoritmo usas actualmente? Siete comparaciones enteras son suficientes, ¿es demasiado lento? Tu hashya realiza más operaciones. ¿Las llamadas posteriores al método están relacionadas, por ejemplo, la central se xmueve a través de la matriz fila por fila?
Raphael
El filtro está enredado en la imagen fila por fila. Es decir, obtener los 5 valores y hacer los cálculos, luego mover todo un paso hacia la derecha y repetir. El hash fue solo un ejemplo. Comparé varias soluciones de ventana deslizante para minimizar la lectura de datos, pero todo se reduce a encontrar los 2 valores más altos.
Fredrik Pihl
3
Lo más probable es que su algoritmo, si se implementa correctamente, estaría limitado por el acceso a la memoria y no por el cálculo. El uso de una tabla hash solo aumentaría la cantidad de accesos a la memoria y ralentizaría las cosas. Publique su código actual para que podamos ver cómo se puede mejorar. Creo que solo es posible la microoptimización. Lo máximo que puedo pensar es: ¿tal vez podamos aprovechar el hecho de que 2 valores son comunes entre ventanas vecinas?
jkff
@jkff Dependiendo de la matriz, los tamaños de caché y la función de mapeo (caché), es posible que cada valor solo deba cargarse una vez; la mayoría de las operaciones deberían ejecutarse en registros o caché L1 entonces. Sin embargo, la canalización es otro problema.
Raphael
1
Por cierto, ¿ya haces esto en paralelo? Esto parece particularmente adecuado para la paralelización de vectores o SIMD (por ejemplo, en una GPU). Esa ruta ayudaría mucho más que ahorrar un pequeño porcentaje por celda.
Raphael

Respuestas:

11

En mi otra respuesta , sugiero que los saltos condicionales podrían ser el principal impedimento para la eficiencia. Como consecuencia, las redes de clasificación vienen a la mente: son independientes de los datos, es decir, la misma secuencia de comparaciones se ejecuta sin importar la entrada, y solo los intercambios son condicionales.

Por supuesto, la clasificación puede ser demasiado trabajo; solo necesitamos los dos números más grandes. Por suerte para nosotros, las redes de selección también se han estudiado. Knuth nos dice que encontrar los dos números más pequeños de cinco² se puede hacer con comparaciones [1, 5.3.4 ex 19] (y como máximo tantos intercambios).U^2(5)=6

La red que da en las soluciones (reescrita en matrices basadas en cero) es

[0:4][1:4][0:3][1:3][0:2][1:2]

que implementa, después de ajustar la dirección de las comparaciones, en pseudocódigo como

def selMax2(a : int[])
  a.swap(0,4) if a[0] < a[4]
  a.swap(1,4) if a[1] < a[4]
  a.swap(0,3) if a[0] < a[3]
  a.swap(1,3) if a[1] < a[3]
  a.swap(0,2) if a[0] < a[2]
  a.swap(1,2) if a[1] < a[2]
  return (a[0], a[1])
end

Ahora, las implementaciones ingenuas todavía tienen saltos condicionales (a través del código de intercambio). Sin embargo, dependiendo de su máquina, puede evitarlos con instrucciones condicionales. x86 parece ser su fango habitual; ARM parece más prometedor ya que aparentemente la mayoría de las operaciones son condicionales en sí mismas. Si entiendo las instrucciones correctamente, el primer intercambio se traduce en esto, suponiendo que nuestros valores de matriz se hayan cargado en los registros a R0través de R4:

CMP     R0,R4
MOVLT   R5 = R0
MOVLT   R0 = R4
MOVLT   R4 = R6

Sí, sí, por supuesto, puede usar el intercambio XOR con EOR .

Solo espero que tu procesador tenga esto o algo similar. Por supuesto, si construye la cosa para este propósito, ¿tal vez pueda conectar la red allí?

Esto es probablemente (¿probablemente?) Lo mejor que puede hacer en el ámbito clásico, es decir, sin hacer uso del dominio limitado y realizar magias malvadas dentro de las palabras.


  1. Ordenar y buscar por Donald E. Knuth; El arte de la programación de computadoras vol. 3 (2a ed., 1998)
  2. Tenga en cuenta que esto deja los dos elementos seleccionados sin ordenar. Ordenarlos requiere una comparación adicional, es decir en total [1, p234 Tabla 1].W^2(5)=7
Rafael
fuente
Estoy aceptando esto Recibí muchas ideas nuevas que necesito comparar antes de continuar. Referirme a Knuth siempre funciona para mí :-) ¡Gracias por su esfuerzo y tiempo!
Fredrik Pihl
@FredrikPihl Cool, ¡cuéntanos cómo resulta al final!
Raphael
¡Voy a! Leyendo el Capítulo 5.3.3 ahora mismo. Me encanta el comienzo de la misma con referencias a Lewis Carroll y el torneo de tenis :-)
Fredrik Pihl
2
Dependiendo del conjunto de instrucciones, puede ser útil usar 2 * max (a, b) = a + b + abs (ab) junto con la red de selección; podría ser menos costoso que los saltos condicionales impredecibles (incluso sin un movimiento intrínseco o condicional para abdominales: gcc, al menos para x86, genera una secuencia sin salto que no parece depender de x86). Tener una secuencia sin salto también es útil cuando se combina con SIMD o una GPU.
Programador
1
Tenga en cuenta que las redes de selección (como las redes de clasificación) son susceptibles de operaciones paralelas; específicamente en la red de selección especificada, las comparaciones 1: 4 y 0: 3 se pueden realizar en paralelo (si el procesador, el compilador, etc. admiten eso de manera eficiente), y las comparaciones 1: 3 y 0: 2 también se pueden realizar en paralelo.
Bruce Lilly
4

Solo para que esté sobre la mesa, aquí hay un algoritmo directo:

// Sort x1, x2
if x1 < x2
  M1 = x2
  m1 = x1
else
  M1 = x1
  m1 = x2
end

// Sort x3, x4
if x3 < x4
  M2 = x4
  m2 = x3
else
  M2 = x3
  m2 = x4
end

// Pick largest two
if M1 > M2
  M3 = M1
  if m1 > M2
    m3 = m1
  else
    m3 = M2
  end
else
  M3 = M2
  if m2 > M1
    m3 = m2
  else
    m3 = M1
  end
end

// Insert x4
if x4 > M3
  m3 = M3
  M3 = x4
else if x4 > m3
  m3 = x4
end

Mediante la implementación inteligente de if ... else, uno puede deshacerse de algunos saltos incondicionales que tendría una traducción directa.

Esto es feo pero solo toma

  • cinco o seis comparaciones (es decir, saltos condicionales),
  • nueve a diez asignaciones (con 11 variables, todas en registros) y
  • sin acceso a memoria adicional.

De hecho, seis comparaciones son óptimas para este problema como lo muestra el Teorema S en la sección 5.3.3 de [1]; aquí necesitamos .W2(5)

Sin embargo, no se puede esperar que esto sea rápido en máquinas con tuberías; dado que tienen un alto porcentaje de saltos condicionales, la mayor parte del tiempo probablemente se gastaría en el puesto.

Tenga en cuenta que una variante más simple, ordenar x1y x2luego insertar los otros valores posteriormente, toma de cuatro a siete comparaciones y solo de cinco a seis asignaciones. Como espero que los saltos sean de mayor costo aquí, me quedé con este.


  1. Ordenar y buscar por Donald E. Knuth; El arte de la programación de computadoras vol. 3 (2a ed., 1998)
Rafael
fuente
Me pregunto qué puede hacer un compilador de optimización con estos.
Raphael
Implementaré esto y lo compararé con la solución actual basada en CLZ. ¡Gracias por tu tiempo!
Fredrik Pihl
1
@FredrikPihl ¿Cuál fue el resultado de sus puntos de referencia?
Raphael
1
¡El enfoque basado en SWAP supera a CLZ! En el móvil ahora. Puede publicar más datos en otro momento, en el móvil ahora
Fredrik Pihl
@FredrikPihl ¡Genial! Estoy feliz de que el viejo enfoque teórico pueda (todavía) ser de uso práctico. :)
Raphael
4

Esta podría ser una gran aplicación y un caso de prueba para el proyecto Souper . Souper es un superoptimizador : una herramienta que toma una secuencia corta de código como entrada y trata de optimizarla lo más posible (trata de encontrar una secuencia equivalente de código que sea más rápida).

Souper es de código abierto. Puede intentar ejecutar Souper en su fragmento de código para ver si puede hacerlo mejor.

Vea también el concurso de John Regehr sobre cómo escribir código rápido para ordenar 16 valores de 4 bits ; Es posible que algunas de las técnicas allí sean útiles.

DW
fuente
Me interesaría lo que esto puede hacer en los programas que el OP ha estado intentando.
Raphael
3

213

T[T[T[441*a+21*b+c]*21+d]*21+e]

214

212

212

Yuval Filmus
fuente