Infraestrutura automática para aritmética computacional baseada em RNS

Abstract

O projeto de hardware para sistemas de processamento digital de sinais tem recebido atenção considerável nas últimas décadas. O crescimento da demanda por arquiteturas com alta eficiência energética, segurança e alto nível de paralelismo elevou o interesse em circuitos aritméticos baseados em sistemas de representação numérica não convencionais. Um destes sistemas é o Residue Number System (RNS), o qual oferece soluções arquiteturais com alta velocidade de computação, efetuando cálculos livres de carry. A técnica consiste na decomposição de um número inteiro em um conjunto de valores independentes, também chamados de resíduos. Com estes é possível realizar operações como adição, multiplicação, acumulação e subtração, de forma paralela. Sistemas RNS são frequentemente interfaceados com sistemas binários comuns. Neste sentido, dada a necessidade de troca de informações entre as porções binária e RNS, tem-se como interface entre blocos, um conversor binário para RNS como entrada, também chamado de conversor direto, e um conversor RNS para binário como elemento de saída, intitulado de conversor reverso. O objetivo deste trabalho é propor uma arquitetura eficiente a qual poderá ser aplicável tanto na implementação de conversores RNS diretos e reversos, como também em operações aritméticas modulares existentes em aplicações de DSP (Digital Signal Processing). A proposta baseia-se em uma nova tendência de solução a qual faz uso de unidades aritméticas compressoras sendo implementadas de forma similar à uma árvore de Wallace. Tal tendência também traz a reinserção de bits de carry-out à própria árvore, com o intuito de evitar o uso de Lookup Tables, o qual apresenta aumento exponencial em área a medida que utiliza-se um número de bits elevado. Tais arquiteturas terão foco em conjuntos modulares 2n ± k os quais encontram-se fora da faixa de uso convencional baseada nos valores 2n , 2n ? 1, 2n + 1, com o intuito de futuras investigações de aplicações com ampla faixa dinâmica. Resultados experimentais demonstram possíveis ganhos no atraso de computação de até 12% nas distintas comparações entre o método desenvolvido e circuitos do estado da arte. Por fim, com as arquiteturas construídas, foi realizada uma nova proposta de seleção de conjuntos modulares a partir da fatoração da propriedade QM i=1 mi = 2a ? 1. É demonstrado que tal fatoração pode proporcionar balanceamento entre canais aritméticos e conversores reversos por meio da aplicação de pipeline e prover possíveis ganhos de área e atraso quando comparado a conjuntos de módulos comumente empregados em projetos RNS.

Abstract: Hardware design for digital signal processing has received considerable attention in recent decades. The growing demand for architectures with characteristics such as high energy efficiency, security and high level of parallelism has raised interest in arithmetic circuits based on non-conventional numerical representations. One approach that fits in such tendency is the Residue Number System (RNS), which offers architectural solutions with carry free operations leading to high computation speed. The technique consists of decomposing an integer into a set of independent values, also called residues. With these residues it is possible to perform operations such as addition, multiplication, accumulation and subtraction, in a parallel scheme. RNS systems are often interfaced with common binary systems. In this sense, given the need to exchange information between the binary and RNS blocks, their interface is composed by a binary to RNS converter, also called direct converter, and an RNS to binary converter, that can be refered to as reverse converter. The objective of this dissertation is to propose an efficient architecture which can be applied both in the implementation of forward and reverse RNS converters, as well as in modular arithmetic operations existing in DSP (Digital Signal Processing) applications. The proposal is based on a new trend which makes use of arithmetic units being implemented similarly to a Wallace tree. This trend also brings the reinsertion of carry-out bits that are fed back into the tree, in order to avoid the use of Lookup Tables. The objective of avoiding these Tables is due to their exponential increase in area as the number of bits increases. Such architectures will focus on modular sets in the form of 2n ± k which fall outside the conventional range of the most used values of 2n , 2n?1, 2n + 1. The intent behind such choice is to enable future investigations of applications with wide dynamic range. Experimental results show possible gains in circuit delays of up to 12% in the different comparisons between the developed method and state-of-the-art architectures. Finally, by using the built architectures, a new proposal for the selection of modular sets was conducted based on the factorization of the property QM i=1 mi = 2a ? 1. It is demonstrated that such factorization can provide critical path balance between arithmetic channels and reverse converters through the application of a pipeline, providing possible gains of area and delay when compared to modules sets commonly used in RNS projects.