Implementações eficientes de conversores reversos e multiplicações por constante usando residue number systems

Abstract

A decomposição de um número inteiro em um conjunto de valores independentes é uma das técnicas mais utilizadas para aumentar o desempenho de implementações digitais de circuitos aritméticos. O RNS é um sistema não posicional que permite a representação de um valor inteiro através de um conjunto de dígitos independentes. Esse sistema apresenta maior paralelismo e pode fornecer circuitos aritméticos com menor área e baixo consumo de energia, em comparação com sistemas posicionais de representação numérica. Consequentemente, o RNS tem sido utilizado em aplicações que demandam grande capacidade de processamento. Este trabalho de pesquisa tem como principal objetivo o desenvolvimento de métodos de projeto e arquiteturas de hardware eficientes para implementação de circuitos integrados digitais baseados em RNSs. Assim, as contribuições desta tese se concentram na implementação eficiente de conversores reversos para faixas dinâmicas amplas e também na implementação eficiente de multiplicações por constante usando os módulos \(2^n\), \(2^n-1\) e \(2^n+1\). Com respeito aos conversores reversos, dois métodos de implementação são propostos e avaliados. Primeiramente, o CRTF é aplicado ao conjunto modular \(\mathcal{M}_f=\{2^{n+\beta}, 2^n\pm 1, 2^n \pm k_1, 2^n \pm k_2, \dots, 2^n \pm k_f\}\) utilizando compressores modulares esparsos. Posteriormente, extensões modulares escalonáveis e genéricas até \(10n+1\) bits são propostas através da aplicação do NCRT1 e do MRC. Finalmente, uma busca exaustiva restringida no RNS é formulada para obter grafos de somas eficientes para realização de multiplicações por constante. Resultados de síntese lógica demonstram que métodos de projeto propostos para os conversores reversos superam os do estado da arte em área e potência. Os grafos de somas encontrados apresentam profundidade e número de somas reduzidos, em comparação com grafos obtidos através de ferramentas de multiplicação por constante populares da literatura.

Abstract: The decomposition of an integer into a set of independent values is one of the most used techniques to increase performance in digital implementations of arithmetic circuits. The RNS is a non-positional number system that allows the representation of an integer value as a set of independent digits. Such a system leads to increased parallelism while providing architectures with reduced circuit area and low power consumption, in comparison with positional number systems. Hence, RNSs have been extensively applied to computationally demanding applications. This research work focuses on the development of design methods and hardware architectures to produce efficient digital integrated circuits based on RNSs Thus, the contributions of this thesis concentrate on the efficient implementation of reverse converters for wide dynamic ranges and also on the efficient implementation of constant multiplications using the modulus \(2^n\), \(2^n-1\) e \(2^n+1\). Regarding reverse converters, two design methods are proposed and evaluated. First, the CRTF is applied to the set \(\mathcal{M}_f=\{2^{n+\beta}, 2^n\pm 1, 2^n \pm k_1, 2^n \pm k_2, \dots, 2^n \pm k_f\}\) by considering sparse modular compressors. Afterwards, generic and scalable modular extensions up to \(10n+1\) bits are obtained by applying the NCRT1 and the MRC Finally, a bounded exhaustive search based on the RNS is developed to obtain efficient adder graphs to implement multiple constant multiplications. Logical synthesis results show that the proposed design methods for the reverse converters outperform the related state of the art ones in term of circuit area and power. The adder graphs obtained present reduced depth and number of additions in comparison with graphs produced by popular multiplication-by-constant tools of the related literature.