Como o número inteiro máximo não assinado é implementado no hardware?

10

Estou trabalhando em um design que envolve muitas funções máximas (e funções máximas como argumentos para outras funções máximas).

Em um esforço para simplificar o design do hardware, eu queria saber como o max é implementado no hardware?

Matematicamente, Max (a, b) pode ser representado como [(a + b) + abs (b - a)] / 2.

É assim que é implementado em hardware? (ou seja, em estágios; adição, divisão de deslocamento de bits, etc.)

Se sim, como é calculado o absoluto da diferença?

James
fonte

Respostas:

10

Uma abordagem muito simples seria implementar (a> b)? A: b. a> b pode ser implementado iniciando à esquerda e verifique cada par de bits de (a, b):

  • 0 ou 1: continua para o próximo par inferior
  • a é 1: a é mais alto; b é 1: b é o mais alto

Quando você souber qual é o mais alto, poderá selecioná-lo por um mux 2N-> N.

Com alguns truques inteligentes, a verificação dos pares de bits pode ser combinada com o muxer para o mesmo par de bits.

Wouter van Ooijen
fonte
2

Vamos analisar o algoritmo na pergunta:

[(a + b) + abs(b - a)]/2

Isto tem um estágio de adição e subtração que é então alimentado para um segundo estágio. A divisão por 2 é trivial em hardware, isso pode ser feito removendo o LSB. No entanto, o somador completo / subtrator de dois estágios é bastante lento e exige muitos portais, especialmente se você estiver conectando múltiplos caparisões em cascata como você.

Partindo da resposta de Wouter van Ooijen, a estrutura generalizada é um comparador digital que alimenta o sinal de seleção de um mux:

esquemático

simular este circuito - esquemático criado usando o CircuitLab

O esquema acima é para:

(A > B) ? A : B

mas observe que ele pode ser facilmente reconfigurado para qualquer comparação entre as duas entradas, fazendo conexões lógicas diferentes entre as saídas do comparador e o mux select.

Portanto, se soubermos formular as três saídas do comparador, poderemos implementar qualquer comparação em hardware. A lógica do comparador é bem descrita aqui . Para otimizar o hardware, removeríamos a lógica que aciona as saídas do comparador não utilizadas.

Mas no final, se for para hardware, ele precisa passar por síntese. Portanto, você não deve ficar obcecado com o esquema em nível de porta ideal. Em vez disso, otimize seu código e algoritmos para que você pelo menos não force o sintetizador a produzir um resultado ineficiente. "Com alguns truques inteligentes, a verificação dos pares de bits pode ser combinada com o muxer para o mesmo par de bits", e a maneira mais fácil de executar essa otimização é com a síntese.

travisbartley
fonte
1

Se você realmente deseja construir um circuito especializado para calcular o máximo, pode começar com um bloco básico com as seguintes equações:

EEu,ovocêtEEu,Eun¬(umaEubEu)euEu,ovocêt(¬EEu,EuneuEu,Eun)(EEu,EunumaEu¬bEu)rEu(¬EEu,Eun((euEu,EunumaEu)(¬euEu,EunbEu)))(EEu,Eun(umaEubEu))

e conecte-os ao dígito mais significativo que alimenta o próximo. A parte crítica vai do MSB ao LSB, enquanto o circuito baseado na subtração terá, na melhor das hipóteses, um caminho crítico que vai do LSB ao MSB e depois ao LSB.

É o equivalente a um somador de transporte. Se você estiver interessado, pode criar o equivalente a add-carry carry-save ou carry-select.

Eeu¬Euma

AProgrammer
fonte