Modo combinacional de implementar una memoria asociativa de contenido en Verilog.
Estoy tratando de implementar una memoria de búsqueda de caché e índices en SystemVerilog. Es una combinación sencilla de memoria asociativa y búfer circular. La interfaz es la siguiente:
input rst_n;
input clk;
input [WORD_BITS-1:0] inp;
input rd_en;
input wr_en;
output logic [DEPTH_BITS-1:0] index;
output logic index_valid;
reg [WORD_BITS-1:0] buffer[$pow(2, DEPTH_BITS)];
reg [DEPTH_BITS-1:0] next;
Hay un código básico de reinicio asíncrono. Hay un bloque síncrono que almacena inp
en el buffer y avanza next
cuando wr_en
está en alto.
Ahora estoy tratando de encontrar una forma eficiente y legible de encontrar el índice de inp
cuando rd_en
está en alto. Parece que esto podría ser completamente combinacional, excepto al ingresar el resultado en la salida index
. La forma en que lo visualizo en mi mente es realizar una operación XOR entre inp
y todas las ubicaciones del búfer (que será bastante pequeño, tal vez 64 entradas). Si el resultado es igual a cero, se ha encontrado la entrada. Luego, se puede establecer un bloque para elegir arbitrariamente uno de los índices con un valor de 0. Aquí es donde difiere de una memoria asociativa tradicional, ya que puede haber múltiples entradas para el mismo valor, pero solo necesito el índice de una de ellas y no importa cuál sea.
¿Alguna idea sobre cómo hacer esto en System Verilog (2012)? Sé que puedo recorrer sincrónicamente todas las ubicaciones de memoria y ahorrar mucho espacio, pero prefiero que sea rápido en lugar de pequeño. Estoy apuntando a FPGA (inicialmente, partes económicas de Lattice y tal vez Xilinx). Sé que algunas partes de Lattice realmente tienen bloques de memoria asociativa, pero esto es para casos en los que eso no esté disponible.
davy.ai
Una posible solución es utilizar una búsqueda en un árbol binario para encontrar el índice de
inp
. Comienza comparandoinp
con la ubicación del búfer en el punto medio del búfer. Siinp
es menor, busca en la mitad inferior del búfer. Siinp
es mayor, busca en la mitad superior. Repite este proceso recursivamente hasta encontrar el índice coincidente. Esta sería una forma rápida y eficiente de buscar en el búfer, especialmente para búferes más grandes.Otro enfoque es utilizar una función hash para mapear
inp
a un índice único en el búfer. Esto eliminaría la necesidad de buscar en el búfer por completo, pero puede requerir más espacio para la lógica adicional necesaria para implementar la función hash.En general, es importante equilibrar la velocidad y el espacio al diseñar hardware para FPGAs. Experimenta con diferentes enfoques y optimiza para tu caso de uso específico.