Embed Size (px)
Citation preview
UmaUnidade Lógica e Aritmética
Reversível
Amanda Leonel Nascimento
DSC / POLI / UPE
[email protected] Antônio Brasil Kowada
PESC / COPPE / UFRJ
[email protected] Rosa de Oliveira
DEINFO / UFRPE
R o t e i r o
I. Introdução
II. Unidades Lógicas e Aritméticas
III. Módulos Lógicos Básicos Reversíveis
IV. Módulos Aritméticos Reversíveis
V. Módulos Lógicos Reversíveis
VI. Aplicações Quânticas
VII. Observações Finais
Lei de MooreComputação IrreversívelComputação Reversível
ULA-CULA-QULA-R
NOT
AND
OR
XORSomadorSubtratorMultiplicadorDivisor
Detector de IgualdadeComparadorROL
ROR
WECIQ - 09/10/06 Uma Unidade Lógica e Aritmética Reversível Amanda Leonel 2 / 29
Lei de Moore
Pesquisadores da IBM anunciam fabricação de chips com fios de menos
de 30 nanômetros. Na foto, comparação com
os fios atuais (à direita).
Agência FAPESP 21/02/2006
Lei de Lei de MooreMoore ganha novo fôlego!ganha novo fôlego!
WECIQ - 09/10/06 Uma Unidade Lógica e Aritmética Reversível Amanda Leonel 3 / 29
Computação Irreversível� Computação convencional expressa em passos irreversíveis.
� Informações de entrada eliminadas pelas portas lógicas clássicas.
� Parte da energia das entradas é dissipada (calor).
� Princípio de Landauer– Qualquer manipulação lógica e irreversível deinformação aumenta a entropia do sistema, em conseqüência, aumenta a temperatura.
� Circuitos atuais apagam informação sempre que executam uma operação.
� Operações irreversíveis� Eliminação ineficiente da informação
C = A v B
WECIQ - 09/10/06 Uma Unidade Lógica e Aritmética Reversível Amanda Leonel 4 / 29
Computação Reversível
� Lógica reversível.
� Informação de entrada armazenada,
e não dissipada.
� Garantia de implementação de circuitos
de forma conservativa.
� Otimização do consumo de energia.
� Portas devem ter número de saídas igual
ao número de entradas.
Toffoli
Fredkin
Portas Reversíveis Universais
WECIQ - 09/10/06 Uma Unidade Lógica e Aritmética Reversível Amanda Leonel 5 / 29
Computação Reversível
Computador Óptico
“Microtecnologia”
Computador Quântico
Nanotecnologia
Layout de umaporta reversível emsilício, observada emum microscópio ótico
� Alternativa promissora!
WECIQ - 09/10/06 Uma Unidade Lógica e Aritmética Reversível Amanda Leonel 6 / 29
Unidade Lógica e Aritmética
Arquitetura von Neumann
� Memória
� Unidade de Controle
� Dispositivos de Entrada e Saída
� Unidade Lógica e Aritmética (ULA)
WECIQ - 09/10/06 Uma Unidade Lógica e Aritmética Reversível Amanda Leonel 7 / 29
John von Neumann(� 1903 , † 1957)
Arquitetura atual dos computadores convencionais
ULA Clássica
� Dois operandos de n bits
� Um código F de tamanho x
� 2x possíveis funções
� Saída S = f (A,B) de tamanho n
� Sinal carry-out para saída “vai-um”
Símbolo padrão para ULA-C convencional,
na representação em diagrama de blocos
WECIQ - 09/10/06 Uma Unidade Lógica e Aritmética Reversível Amanda Leonel 8 / 29
ULA QuânticaArquitetura
de um Computador Quântico
resistente a falhas, proposto em [Oskin, Chong
and Chuang 2002]
WECIQ - 09/10/06 Uma Unidade Lógica e Aritmética Reversível Amanda Leonel 9 / 29
ULA Reversível
Representação em bloco de uma
Unidade Lógica e Aritmética Reversível
WECIQ - 09/10/06 Uma Unidade Lógica e Aritmética Reversível Amanda Leonel 10/ 29
Códigos F de seleção em uma ULA-R básica
ULA Reversível
WECIQ - 09/10/06 Uma Unidade Lógica e Aritmética Reversível Amanda Leonel 11/ 29
ULA Reversível
n
n
n
A A
F0 F0
F1 F1
F2 F2
F3 F3
B B
0 S=f(A,B)
I ¬A ¬B A=B A>B...
...
Combinação dos módulos no interior de uma ULA-R
WECIQ - 09/10/06 Uma Unidade Lógica e Aritmética Reversível Amanda Leonel 12/ 29
Módulos Lógicos Básicos
0 1
X =
1 0
NOT
Inversor de n q-bits
Operador quântico NOT
Inversor clássico
WECIQ - 09/10/06 Uma Unidade Lógica e Aritmética Reversível Amanda Leonel 13/ 29
Módulos Lógicos Básicos
AND reversível
Módulo AND de n q-bits
Porta AND clássica
WECIQ - 09/10/06 Uma Unidade Lógica e Aritmética Reversível Amanda Leonel 14/ 29
Módulos Lógicos Básicos
Módulo OR de n q-bits
Porta OR clássica
OR reversível
WECIQ - 09/10/06 Uma Unidade Lógica e Aritmética Reversível Amanda Leonel 15/ 29
Módulos Lógicos Básicos
Porta XOR clássica
XOR reversível
Módulo XOR de n q-bits
WECIQ - 09/10/06 Uma Unidade Lógica e Aritmética Reversível Amanda Leonel 16/ 29
Módulos Aritméticos
Módulo Somador Reversível
Somador reversível
Full Adder clássico
Tabela-Verdade para somadores
WECIQ - 09/10/06 Uma Unidade Lógica e Aritmética Reversível Amanda Leonel 17/ 29
Módulos Aritméticos
Módulo Subtrator Reversível
Subtrator reversível
Full Subtractor clássico
Tabela-Verdade para subtratores
WECIQ - 09/10/06 Uma Unidade Lógica e Aritmética Reversível Amanda Leonel 18/ 29
Multiplicador Reversível
Módulos Aritméticos
Circuito reversível proposto em [Kowada 2006]
WECIQ - 09/10/06 Uma Unidade Lógica e Aritmética Reversível Amanda Leonel 19/ 29
Módulos Aritméticos
Divisor Reversível
WECIQ - 09/10/06 Uma Unidade Lógica e Aritmética Reversível Amanda Leonel 20/ 29
Circuito reversível proposto em [Kowada 2006]
Módulos Lógicos
Detector de Igualdade reversível
Detector de Igualdade clássico
Módulo reversível de n q-bits
WECIQ - 09/10/06 Uma Unidade Lógica e Aritmética Reversível Amanda Leonel 21/ 29
Módulos Lógicos
Comparador reversível
Comparador clássico
Módulo Comparador de n q-bits
WECIQ - 09/10/06 Uma Unidade Lógica e Aritmética Reversível Amanda Leonel 22/ 29
Módulos Lógicos
Deslocadores de Registro
Módulo ROL de n q-bits
Rotate Left
Logical
WECIQ - 09/10/06 Uma Unidade Lógica e Aritmética Reversível Amanda Leonel 23/ 29
Módulos Lógicos
Deslocadores de Registro
Módulo ROR de n q-bits
Rotate Right
Logical
WECIQ - 09/10/06 Uma Unidade Lógica e Aritmética Reversível Amanda Leonel 24/ 29
Aplicações Quânticas ?
Circuito Somador Quântico corrigido de [Milosav 2005]
Somador Reversível operando em superposição
WECIQ - 09/10/06 Uma Unidade Lógica e Aritmética Reversível Amanda Leonel 25/ 29
Somador Reversível
Observações Finais
� Possível execução da ULA-R tanto em computadores clássicos quanto em quânticos;
�Aplicações quânticas a serem mais exploradas;
� Propostas de circuitos reversíveis mais eficientes, graças à Transformada de Fourier Quântica:[Draper 2000] e [Nguyen 2001];
�Muito trabalho até uma ULA Quântica... Estamos menos distantes agora!
WECIQ - 09/10/06 Uma Unidade Lógica e Aritmética Reversível Amanda Leonel 26/ 29
Referências• Draper, T.G. (2000). Addition on a Quantum Computer. ArXiv:quant-ph/ 0008033.• Kowada, L. A. B. (2006). Construção de Algoritmos Reversíveis e Quânticos. Tese de
Doutorado – COPPE / UFRJ.• Kowada, L. A. B.; Portugal, R. Figueiredo and C. M. H. de (2006). Reversible Karatsuba.
Journal of Universal Computer Science.vol 12, n. 5 pg 499-511.• Mermin, N.D. (2002). From Cbits to Qbits: Teaching Computer Scientists Quantum
Mechanics. ArXiv:quant-ph/ 0207118.• Milosav, M.U. (2005). Quantum Circuits Engineering: Efficient Simulation and
Reconfigurable Quantum Hardware. Ph.D. Thesis. Universitatea “Politehnica” Din Timiçoara, România.
• Nielsen, M. A. and Chuang, I. L. (2005). Computação Quântica e Informação Quântica. Bookman.
• Nguyen, A. Q. (2001). Optimal Reversible Quantum Circuit for Multiplication. Tech Reports/2004010, v.2.
• Oskin, M.; Chong, F. T. and Chuang, I. L. (2002). A Practical Architecture for Reliable Quantum Computers. IEEE Computer, Jan.2002. pg 79-87
• Pacheco, M. A. C.; et al. Uma Introdução à Nanotecnologia. ICA. DEE. PUC-Rio.• Thapliyal, H and Srinivas, M. B. (2006). Novel Reversible Multiplier Architecture Using
Reversible TSG Gate. Center for VLSI and Embedded Technologies.• Uyemura, J. P. (2002). Sistemas Digitais – Uma Abordagem Integrada. Thomson
Learning.• Vargas, F. L. (2004). Engenharia de Computadores I. DEE, PUCRS.• Vedral, V.; Barenco, A. and Ekert, A. (1996). Quantum Networks for Elementary
Arithmetic Operations. Physical Review A, v.54, n.1.• Vignatti, A. L.; Netto Summa, F. and Bittencourt, L. F. (2004). Uma Introdução à
Computação Quântica. Departamento de Informática. UFPR.
WECIQ - 09/10/06 Uma Unidade Lógica e Aritmética Reversível Amanda Leonel 27/ 29
Comentários ?Dúvidas ?
WECIQ - 09/10/06 Uma Unidade Lógica e Aritmética Reversível Amanda Leonel 28/ 29
