Dificultad relativa entre el conteo cero inicial y la suma

1

Considere una ALU de 32 bits o 64 bits que debe implementar tanto la suma de ceros iniciales como la suma de enteros , con baja latencia (digamos unos pocos ciclos), implementada en un proceso lógico moderno de alta frecuencia.

¿Cuál es generalmente más complejo, un sumador rápido o un conteo cero inicial rápido?

BeeOnRope
fuente
2
hm, ¿para qué necesitas "contar ceros iniciales"?
Marcus Müller
¿Qué tipo de ceros a la izquierda quieres contar? ¿Binario? ¿Maleficio? BCD? ¿Decimal? ¿Y la forma en que se almacena la información coincide con la forma en que desea contarla? Los ceros binarios son al menos sencillos, pero contar ceros decimales en un valor base 2 es un poco más complejo.
Chris Stratton
@ChrisStratton - binario. Es decir, como las clzinstrucciones disponibles en la mayoría de las ISA modernas.
BeeOnRope
@ MarcusMüller: es una instrucción común sobre los ISA de CPU modernos, y estaba en una discusión en la que se afirmaba que no era "más difícil que un sumador", y quería comprobarlo. En particular, los chips Intel x86 modernos pasan por la molestia de implementar su clzinstrucción SIMD entera en la unidad flotante, lo cual es bastante inusual (la única otra cosa entera que sigue ese patrón es el número entero mul, lo que no es sorprendente teniendo en cuenta el costo de la rapidez, multiplicadores de ancho).
BeeOnRope

Respuestas:

2

Para un contador cero inicial de 64 bits, lo que necesitaría es como máximo una cadena combinatoria de 6 NOR de profundidad más un XOR (o equivalente) ("es el primer bit cero y el segundo bit uno", "son los bits anteriores cero, utilizando el resultado del paso anterior ") y LUT de 6 bits.

Eso es muy poco.

Un sumador trivial de búsqueda anticipada con operandos de 64 bits necesita seis etapas, por lo que puede ser mínimamente más rápido, lo que también es muy poco.

En otras palabras: no puedo darte una respuesta definitiva; Las implementaciones rápidas reales dependerán de los bloques estándar que el diseñador de hardware puede emplear: por ejemplo, en un FPGA moderno de alto rendimiento, simplemente usarías un bloque aritmético (y no te importaría el diseño), o lo construirías a partir de 6 -LUTs; entonces, estas consideraciones combinatorias no tienen relevancia para el diseño de FPGA. En un ASIC de una CPU de silicio real, ninguno de los componentes estará cerca de ser lo más complejo durante un solo ciclo de reloj y, por lo tanto, se podrían favorecer más pasos combinatorios a favor de, por ejemplo, una sobrecarga de enrutamiento más baja o una menor probabilidad de conmutación.

Marcus Müller
fuente
Solo un pensamiento que se me ocurrió mientras leía la pregunta y su respuesta. El OP no mencionó un FPGA, por lo que puedo decir. Entonces estaba pensando en ASIC cuando leía el OP.
jonk
@jonk de hecho, tenía ASIC en mente cuando escribí esta respuesta. Pero la verdad es que es probable que los estudiantes que implementan ALU lo hagan en pura simulación o FPGA ...
Marcus Müller