IMPLEMENTAÇÃO DE UMA ARQUITETURA PARA UM DIVISOR
COMBINACIONAL DE 16 BITS EM COMPLEMENTO DE 2
† Diego Caldas Salengue, † César Augusto Prior , ‡João Baptista dos Santos Martins, ‡Cesar
Ramos Rodrigues
[email protected], [email protected] , [email protected], [email protected]
Universidade Federal de Santa Maria
Programa de Pós Graduação em Engenharia Elétrica
Departamento de Eletrônica e Computação
Grupo de Microeletrônica
ABSTRACT
This paper shows the implementation of a division algorithm VHDL description for integer 16 bits numbers. The
circuit was implemented in a combinational way, the division result will be achieved in only one step.
To validate the proposed division circuit simulations were done in the modelsim simulation tool. Furthermore, the
VHDL description was sinthezsized in the leonardo spectrum tool to the AMI0.5 technology and the icstation tool was
used to generate automaticaly the layout.
The logic simulations achieved the expected result validating the proposed architecture.
RESUMO
Neste artigo é mostrada a implementação da descrição VHDL de um algoritmo de divisão de números inteiros de
16 bits. O circuito foi implementado de forma combinacional, ou seja, o resultado da divisão é obtido em um único
passo.
Para a validação do circuito proposto foram feitas simulações com a ferramenta modelsim. Além disso, a descrição
VHDL foi sintetizada através da ferramenta Leonardo spectrum para a tecnologia AMI0.5, e o layout foi gerado
automaticamente pela ferramenta ic_station.
As simulações lógicas obtiveram o resultado esperado validando a arquitetura proposta.
†- Estudante de mestrado PPGEE / UFSM - Pesquisador bolsista pela CAPES
‡ - Professor DELC / PPGEE / UFSM
IMPLEMENTAÇÃO DE UMA ARQUITETURA PARA UM DIVISOR
COMBINACIONAL DE 16 BITS EM COMPLEMENTO DE 2
† Diego Caldas Salengue, † César Augusto Prior , ‡João Baptista dos Santos Martins, ‡Cesar
Ramos Rodrigues
[email protected], [email protected] , [email protected], [email protected]
Universidade Federal de Santa Maria
Programa de Pós Graduação em Engenharia Elétrica
Grupo de Microeletrônica
ABSTRACT
This paper shows the implementation of a division
algorithm VHDL description for integer 16 bits
numbers. The circuit was implemented in a
combinational way, the division result will be achieved
in only one step.
To validate the proposed division circuit simulations
were done in the modelsim simulation tool.
Furthermore, the VHDL description was sinthezsized in
the leonardo spectrum tool to the AMI0.5 technology
and the icstation tool was used to generate automaticaly
the layout.
The logic simulations achieved the expected result
validating the proposed architecture.
através de sucessivas subtrações do dividendo pelo
divisor, até que o número obtido seja menor que zero.
Esta seria a forma para dividir números decimais, o
fluxograma da fig. 1 ilustra o procedimento necessário
para efetuar-se a divisão.
aux ← dividendo
quoc ← 0
N
aux ≤ 0
S
1. INTRODUÇÃO
Algoritmos para divisão são processos tipicamente
iterativos, ou seja, são necessários vários ciclos de clock
para obter-se o resultado de uma operação. Em
hardware este tipo de algoritmo é implementado através
de circuitos seqüenciais. Uma implementação através de
circuitos combinacionais faz com que o resultado de
uma operação de divisão seja obtido de forma mais
rápida, dependendo somente do tempo de propagação
dentro do circuito. Utilizando o circuito proposto dentro
de um processador a operação de divisão seria efetuada
em um único ciclo de clock melhorando a sua
performance. Por ser combinacional, poderia ser
inserido em um processador com pipeline sem ocasionar
sua queda, ou seja, a busca e execução de outra
instrução enquanto o resultado de uma operação ainda
não foi obtido, a divisão é realizada em um único ciclo
do pipeline.
Na próxima seção são mostrados alguns
algoritmos para divisão, divisão de números decimais e
de números binários. O algoritmo de divisão proposto é
mostrado na seção 3. A simulação VHDL do circuito
pode ser vista na seção 4. Resultados obtidos através da
ferramenta Leonardo Spectrum e o layout gerado
automaticamente pelas ferramentas mentor graphics são
mostrados na seção 5.
2. ALGORITMOS ITERATIVOS PARA DIVISÃO
A divisão de números inteiros pode ser realizada
aux ← aux - divisor
quoc ← quoc + 1
resto ← aux + divisor
quociente ← quoc
Figura 1 – Algoritmo iterativo de divisão decimal
O dividendo é armazenado em uma variável
auxiliar e uma variável para acumular o valor do
quociente (quoc) é inicializada com zero. Enquanto o
valor desta variável auxiliar for maior que zero, efetuase a subtração de seu valor pelo divisor e incrementa-se
o valor do quociente. Quando a variável auxiliar possuir
um valor menor que zero significa que a divisão chegou
ao fim, o resultado da divisão está armazenado na
variável quoc e o resto da divisão é a soma de aux (com
valor negativo no momento) com o valor do divisor. O
quociente obtido é igual ao número de subtrações
necessárias para se chegar ao resultado. Na tab. 1 uma
divisão utilizando este algoritmo é exemplificada.
Como é possível perceber pela tab. 1, quanto maior
for o quociente da divisão mais iterações serão
necessárias para obter-se o resultado. Por este motivo
não é possível implementar este algoritmo de forma
combinacional, o número de blocos construtivos
(subtratores) teria de ser variável, já que o número de
subtrações varia dependendo dos números efetuados.
A outra forma de efetuar-se a divisão é através de
números binários, comparando os bits do dividendo com
o divisor. Como se trata de números binários, há
somente duas possibilidades para esta comparação. Se o
†- Estudante de mestrado PPGEE / UFSM - Pesquisador bolsista pela CAPES
‡ - Professor DELC / PPGEE / UFSM
dividendo for menor que o divisor, o quociente será zero
e se for maior ou igual o quociente será um. A fig. 2
mostra o algoritmo de divisão binária.
Dividendo
Divisor
32
4
- 4
28
- 4
24
- 4
20
- 4
16
- 4
12
- 4
8
- 4
4
- 4
0
- 4
-4 < 0
Quociente
0
1
2
3
4
5
6
7
8
Resto = -4 + 4 = 0
Tabela 1 – Exemplo de divisão usando algoritmo iterativo decimal
aux ← 0
quoc ← 0
i ← nro de bits do
dividendo
número de bits do dividendo. O primeiro passo é atribuir
ao bit menos significativo da variável auxiliar do
dividendo (aux) o valor do bit mais significativo do
dividendo. O valor da variável aux é então comparado
com o valor do divisor, como foi dito antes existem
apenas duas possibilidades para a atribuição do
quociente, se for maior ou igual então é atribuído o
valor 1 para o bit menos significativo do quociente e à
variável auxiliar (aux) é atribuído o seu próprio valor
subtraído do valor do divisor (como na forma intuitiva
de efetuar-se uma divisão). Caso contrário, se o valor da
variável aux for menor que o do divisor, seu valor é
deslocado 1 bit para a esquerda e a varíavel contadora ( i
) é decrementada. Após a comparação entre a variável
auxiliar e o divisor, verifica-se se a variável contadora (
i ) chegou a zero, caso contrário o quociente é deslocado
um bit para a esquerda e o processo se repete, é
atribuído ao bit menos significativo da variável aux o
valor do bit do dividendo apontado pela variável i, o
valor de aux é comparado com o divisor, etc. Quando a
variável i chega a zero o valor do resultado esta
armazenado na variável quoc e o resto da divisão na
variável aux. A tab. 2 exemplifica uma divisão
utilizando-se este algoritmo.
Aux (dividendo)
1 0 0 0 0 0 2 (32)
Divisor
1002 (4)
(comparação)
Quociente
0000002
i
5
aux(0) ←
dividendo( i )
1
< 1002
02
10
< 1002
002
100
-100
000
= 1002
0012
< 1002
00102
0000
< 1002
001002
00000
< 1002
0010002
000000
Resto = 0
< 1002
4
3
S
aux <
divisor
2
Shift_left (aux)
i←i-1
1
N
0
quoc(0) ← 1
aux ← aux - divisor
Quociente = 8
Tabela 2 – Exemplo de divisão usando algoritmo iterativo binário
S
Shift_left (quoc)
i>0
N
quociente ← quoc
resto ← aux
Figura 2 – Algoritmo iterativo de divisão binária
No caso do algoritmo binário de divisão o dividendo
e o quociente também são armazenados em variáveis
auxiliares inicializadas com zero. Além disso, uma
variável de contagem é inicializada com o valor do
Percebe-se no caso da tab. 2 que o número de
iterações necessárias para obter-se o resultado é igual ao
número de bits do dividendo, não importando qual
número seja, o resultado será obtido sempre em um
mesmo número de iterações. Este algoritmo é mais
otimizado que o primeiro e poderia ser implementado de
forma combinacional, já que o número de blocos
necessários é conhecido, só dependendo do tamanho do
dividendo em bits.
3. ARQUITETURA DE DIVISÃO PROPOSTA
A proposta apresentada foi implementar um divisor
de números inteiros de 16 bits de forma combinacional,
ou seja, o resultado é obtido imediatamente, dependendo
apenas do atraso da saída do circuito em relação a
entrada. O arquitetura implementada foi baseada no
algoritmo de divisão binário, mostrado na fig. 2. Foram
feitas modificações para transforma-lo em um algoritmo
combinacional e foram inseridas características de
dividir números inteiros com sinal e arredondar o
resultado. A fig. 4 mostra o fluxograma do algoritmo
proposto. Neste caso é mostrado o fluxograma para um
divisor de 2 bits, mas o mesmo algoritmo pode ser
dvd ← dividendo
dvr ← divisor
usado para uma maior quantidade de bits, como o de
16 bits implementado neste trabalho. A área do
fluxograma marcada com um quadrado pontilhado é a
base do divisor, basta replicar este código para obter-se
um divisor com o número de bits desejado. Este
algoritmo para divisão é próximo ao método intuitivo de
divisão de números ensinado nas escolas, o resultado é
obtido da direita para a esquerda.
aux1 ← dvd(1)
sinal ←
dvr(15) xor dvd(15)
S
aux1
≥
divisor
S
dvd ← not(dvd) + 1
Dvd(msb)
=1
aux1 ←aux1 - divisor
N
quoc(1) ← 0
quoc(1) ← 1
N
S
dvr ← not(dvr) + 1
Dvr(msb)
aux2 ← concatena
(aux1, dvd(0))
=1
N
S
aux2
≥
divisor
S
aux2 ←aux2 - divisor
Divisor ≠ 0
N
N
quoc(0) ← 0
quociente ← 0
resto ← 0
flag_dbz ← 1
quoc(0) ← 1
resto ← aux2
N
Resto
> divisor
(msb to 1 )
S
quociente ← quoc + 1
Sinal = 1
S
quociente ←
not(quociente) + 1
Figura 3 – Fluxograma do algoritmo combinacional de divisão de números binários inteiros de 16 bitscom sinal
Inicialmente o dividendo e o divisor são armazenados
em variáveis auxiliares (dvd e dvr). O bit mais
significativo destas variáveis é verificado com o
propósito de avaliar se são números positivos ou
negativos (o bit mais significativo com valor 1
significa número negativo). No caso deste divisor de
16 bits os valores pode variar de –32768 até 32767. Se
o dividendo ou o divisor forem números negativos é
aplicado o complemento de 2 para obter o módulo do
número. Uma variável sinal armazena o resultado de
uma operação xor entre o bit mais significativo do
divisor e do dividendo, 0 para números com sinais
iguais e 1 para números com sinais diferentes. Esta
variável é utilizada após a obtenção do quociente, para
avaliar se é necessário aplicar o complemento de 2 se
o resultado da operação for negativo. Após o
tratamento dos números negativos e do sinal resultante
da operação é verificado se o valor divisor é igual a
zero (divisão por zero não existe), caso seja é atribuído
zero para o quociente e para o resto da divisão e uma
flag (flag_dbz) é setada para assinalar divisão por zero.
Caso o valor do divisor seja diferente de zero a
operação de divisão é iniciada. O valor do bit mais
significativo do dividendo é armazenado em uma
variável auxiliar (aux1) e comparado com o divisor, se
for maior ou igual seu valor é subtraído do divisor e é
atribuído 1 ao bit mais significativo do quociente.
Caso contrário é atribuído zero ao bit mais
significativo do quociente. Depois disso, o valor
armazenado em aux1 é concatenado com o próximo
bit do dividendo (msb – 1) e o resultado é armazenado
em uma nova variável (aux2). O processo é então
repetido tantas vezes quantas forem necessárias (o
valor é comparado com o divisor, se for maior ou igual
a zero seu valor é subtraído do valor do divisor, o
próximo bit do quociente é setado, etc. A parte que se
repete é assinalada dentro do quadrado pontilhado. A
forma com que o algoritmo efetua as operações é
similar ao mostrado na tab. 2. Neste caso não são
necessários deslocamentos a esquerda (shifter), estes
são componentes seqüenciais e portanto não poderiam
ser inseridos em um divisor combinacional. O resto da
divisão é armazenado na última variável auxiliar dos
valores do dividendo. O valor do resultado é
arredondado no caso do resto da divisão ser maior que
a metade do valor do divisor, ou seja, o valor não
inteiro da divisão ser maior que 0,5. Por último é
verificado o sinal do quociente e o complemento de 2
é efetuado para transformar o resultado em um número
negativo, se necessário.
Neste trabalho, como já foi mencionado, o divisor
ilustrado pela fig. 3 foi descrito em VHDL
comportamental como uma procedure dentro de uma
package, para facilitar o uso em outras entidades
VHDL. Para teste do divisor foi criada uma entidade
VHDL e uma chamada a procedure que continha o
divisor foi usada dentro de um processo dependente de
um sinal de clock. Na borda de subida do sinal de
clock os valores do dividendo e divisor eram
repassados na procedure e o resultado era obtido. As
simulações que comprovaram o correto funcionamento
desta arquitetura de divisor encontram-se na próxima
seção.
4. RESULTADOS DAS SIMULAÇÕES
A descrição VHDL do divisor foi validada através
da compilação do código e simulações que são
apresentadas nesta seção.
Figura 4 – Simulação no modelsim de alguns valores para divisão
A fig. 4 mostra a tela de simulação do software
modelsim para a entidade VHDL que testa o divisor.
Como foi dito anteriormente, a procedure na qual o
divisor foi implementado foi usada dentro de um
processo dependente do sinal de clock. É possível
perceber pela fig. 4 que quando há uma variação na
entrada(dividendo e divisor) o resultado (quociente e
resto) só é obtido após a borda de subida do clock.
Primeiramente foram feitas simulações das quatro
possibilidades de sinal na entrada para os mesmos
números, neste caso o dividendo é 81 e o divisor é 9.
Após este teste, que avalia se o sinal do resultado do
quociente é o esperado, foram feitas algumas
simulações de números aleatórios. Estes resultados
podem ser vistos na tab. 3.
Dividendo Divisor
Quoc.
Quociente Resto
Resto Esperado Esperado
81
-81
-81
81
-25221
32767
-32768
-32768
32767
9
-9
9
-9
-48
39
256
1
-1
0
0
0
0
405
695
0
0
0
9
9
-9
-9
528
844
-128
-32768
-32767
9
-9
9
-9
-47,77
38,82
256
1
-1
0
0
0
0
405
695
0
0
0
Tabela 3 – Valores da simulação
Analisando a tab. 4 percebe-se que todos os valores
testados obtiveram um resultado condizente com o
esperado, inclusive verificando que o arredondamento
do quociente quando a parte fracionária de seu valor
for maior que 0,5. O valor esperado do resto é obtido
através da multiplicação da parte fracionária do
resultado real pelo divisor, todos os resultados de resto
de divisão estavam corretos. O sinal do resultado
também se mostrou correto em todas as divisões
efetuadas. Foram testados os extremos possíveis para
números de 16 bits (-32768 a 32767) para verificar se
alguma exceção poderia ocorrer nestes casos.
Os resultados obtidos validaram a lógica da
arquitetura de divisão proposta.
Figura 5 –Layout gerado automaticamente
5. SÍNTESE AUTOMÁTICA
Após as simulações lógicas utilizando a ferramenta
modelsim, a descrição VHDL foi sintetizada na
ferramenta Leonardo spectrum. A tecnologia AMI0.5
do design kit ADK foi utilizada para este fim. A
escolha desta tecnologia foi devido ao fato de estar
inserida no programa educacional da MOSIS,
futuramente o divisor poderá ser prototipado e suas
características avaliadas de forma real.
PORTAS DE E/S
REDES
INSTANCIAS
PORTAS LÓGICAS
NÚMERO DE TRANSISTORES
ÁREA DO NÚCLEO
ATRASO DA OPERAÇÃO
66
1217
1183
1764
8807
1093µmX1393µm
1,14 X 10-9S
Tabela 4 – Resultado da síntese lógica e extração elétrica
Os resultados obtidos na síntese da ferramenta
Leonardo spectrum podem ser vistos na tab. 4. A tab.
4 também mostra o resultado da extração elétrica do
modelo spice do circuito a partir do layout gerado pela
ferramenta ic station e o tamanho do core. A extração
elétrica fornece o número de transistores do circuito.
No caso, o circuito possui 8807 transistores e ocupa
uma área de 1093µm X 1393µm. A fig. 5 mostra o
layout gerado na ferramenta ic_station.
A tab. 4 também mostra o atraso estimado para
obter-se o resultado da divisão. Este tempo foi medido
através de uma simulação elétrica realizada no sofware
Figura 6 – Simulação elétrica do software eldo
eldo, é medido o intervalo de tempo entre o inicio da
borda de subida do sinal de clock (ck) até os sinais de
quociente e resto tornarem-se estáveis. A tela da
simulação elétrica do eldo é mostrada na fig. 6, como
pode ser observado o atraso para efetuar a divisão foi
de 1,14 X 10-9 segundos. Nesta simulação os valores
de
dividendo e
divisor
são inicializados
respectivamente com -32768 e 3 e as saídas quociente
e resto são verificadas. A tab. 5 mostra estes
resultados. Como pode ser observado o quociente foi
arredondado, pois a parte fracionária do resultado é
maior que 0,5, mas a divisão foi efetuada de forma
correta.
Dividendo
Divisor
Quociente real
Quociente
Resto
Binário
1000000000000000
0000000000000011
1101010101010101
0000000000000011
Decimal
-32768
3
-10922,67
-10923
3
Tabela 4 – Resultado da síntese lógica e extração elétrica
6. CONCLUSÕES
Este trabalho teve por objetivo criar um core de um
divisor combinacional de 16 bits que possa ser
facilmente utilizado em outros projetos do grupo de
microeletrônica da UFSM.
As simulações da descrição VHDL foram
consistentes e validaram a arquitetura de divisão
proposta. A simulação elétrica no software eldo
também ocorreu da forma esperada, fornecendo o
resultado correto da operação de divisão. Com o
atraso verificado para obter-se o resultado da divisão,
conclui-se que o circuito pode ser submetido a uma
freqüência de até 800MHz sem fornecer resultados
incorretos. A arquitetura proposta certamente leva um
tempo menor para fornecer o resultado em relação a
algoritmos iterativos de divisão.
Um trabalho futuro será inserir o core do divisor de
16 bits proposto dentro de uma descrição VHDL de
uma arquitetura de processador MIPS com pipeline.
AGRADECIMENTOS
Este trabalho é financiado pela Coordenação de
Aperfeiçoamento de Pessoal de Nível Superior CAPES e Fundação de Amparo a Pesquisa do Rio
Grande do Sul - FAPERGS.
REFERÊNCIAS
[1]
David A. Patterson, Jonh L. Hennessy,
Organização e Projeto de Computadores: A Interface
Hardware Software, LTC Editora, 2000
[2]
Andrew Rushton, VHDL for Logic Synthesis,
Editora Wiley, 1999
[3]
Fernando Moraes, Ney Calazans, VHDL:
Uma Linguagem de Descrição de Hardware, PUCRS, 2001