Models and parameters

Neste cap´ıtulo foram abordados os conceitos b´asicos sobre otimiza¸c˜ao, considerados relevantes para o desenvolvimento do presente trabalho. O estudo do estado da arte das t´ecnicas de otimiza¸c˜ao evidenciou uma tendˆencia ao uso de metaheur´ısticas na solu¸c˜ao de problemas complexos em que os m´etodos exatos, baseadas no c´alculo gradiente, s˜ao de dif´ıcil implementa¸c˜ao e conduzem a tempos de execu¸c˜ao elevados.

Metaheur´ısticas baseadas em popula¸c˜oes, dentre as quais se destacam os algoritmos evolutivos e os algoritmos de inteligˆencia de enxames, utilizam t´ecnicas computaci- onais bioinspiradas nos princ´ıpios biol´ogicos evolutivos encontrados na natureza, tais como a sele¸c˜ao natural, heran¸ca gen´etica, muta¸c˜ao e comportamentos coletivos para in- tercˆambio de informa¸c˜ao. Neste trabalho foram escolhidos os algoritmos de otimiza¸c˜ao por inteligˆencia de enxames devido `a sua simplicidade de implementa¸c˜ao e capacida- des de paraleliza¸c˜ao, as quais podem ser exploradas visando ganhos de desempenho e melhoras na qualidade das solu¸c˜oes.

Neste cap´ıtulo tamb´em foi apresentada a tecnologia de hardware reconfigur´avel baseada em FPGAs, examinando a sua potencialidade para acelerar algoritmos, incrementando a taxa de processamento de dados mediante a execu¸c˜ao de processos paralelos. Os

dispositivos FPGAs possibilitam a implementa¸c˜ao de solu¸c˜oes hardware de alto de- sempenho e baixo consumo de potˆencia se comparado com solu¸c˜oes convencionais em software, sendo assim bons candidatos para aplica¸c˜oes embarcadas.

Espera-se, com as implementa¸c˜oes em arquiteturas reconfigur´aveis dos algoritmos es- tudados ganhar em desempenho, custo, flexibilidade e eficiˆencia de forma que as arqui- teturas propostas possam ser uma alternativa de estudo em problemas de otimiza¸c˜ao embarcados.

Os conceitos apresentados neste cap´ıtulo s˜ao importantes para o entendimento das implementa¸c˜oes de hardware e software realizadas no contexto deste trabalho. Estas implementa¸c˜oes s˜ao descritas nos seguintes cap´ıtulos.

Cap´ıtulo 3

IMPLEMENTAC¸ ˜AO DAS UNIDADES DE

C ´ALCULO ARITM´ETICO E TRIGONOM´ETRICO EM

PONTO FLUTUANTE

Este cap´ıtulo apresenta as implementa¸c˜oes dos operadores de c´alculo aritm´etico e tri- gonom´etrico, assim como os resultados de s´ıntese, execu¸c˜ao e desempenho. O cap´ıtulo est´a dividido da seguinte forma: Ap´os algumas considera¸c˜oes iniciais, ´e descrito o padr˜ao IEEE-754 para representa¸c˜ao bin´aria da aritm´etica de ponto flutuante. Poste- riormente, apresentam-se as arquiteturas de hardware dos operadores implementados. Em seguida os resultados de custo em ´area l´ogica, erro associado e tempo de execu¸c˜ao dos operadores implementados s˜ao apresentados. Finalmente ´e realizada uma discuss˜ao sobre os pontos mais relevantes associados aos resultados obtidos.

3.1 CONSIDERAC¸ ˜OES INICIAIS

A motiva¸c˜ao do estudo apresentado neste cap´ıtulo est´a relacionado com os estudos pouco aprofundados encontrados na literatura sobre a implementa¸c˜ao em FPGAs de operadores aritm´eticos e trigonom´etricos usando uma aritm´etica de ponto flutu- ante, principalmente quando direcionados para aplica¸c˜oes embarcadas. A escolha da aritm´etica de ponto flutuante para representa¸c˜ao num´erica obedece aos requerimen- tos de precis˜ao e faixa dinˆamica presentes nos problemas de otimiza¸c˜ao em diversos campos da engenharia. Neste contexto, existe uma necessidade cr´ıtica de atingir um compromisso entre desempenho, consumo de energia, consumo de recursos e precis˜ao nas opera¸c˜oes matem´aticas, de forma que sejam atendidos os requisitos espec´ıficos para uma aplica¸c˜ao em sistemas embarcados.

Atualmente, as ferramentas de desenvolvimento proporcionam a possibilidade de ins- tanciar blocos de propriedade intelectual (IPcores), dentre os quais podem-se encontrar unidades de c´alculo aritm´etico em ponto flutuante. Estas ferramentas s˜ao bastante flex´ıveis, possibilitando a escolha do tamanho de palavra, latˆencia, entre outras carac- ter´ısticas como otimiza¸c˜ao para aplica¸c˜oes de alto desempenho ou baixo consumo de

recursos. Contudo, os IPcores fornecidos por estas ferramentas est˜ao limitados a certas fam´ılias de um fabricante espec´ıfico. Adicionalmente, o usu´ario geralmente n˜ao tem acesso `a descri¸c˜ao de hardware dos operadores e, portanto, n˜ao ´e poss´ıvel realizar mo- difica¸c˜oes na l´ogica visando melhoras em uma ou mais vari´aveis de projeto digital, tais como, custo em ´area l´ogica, latˆencia, frequˆencia de opera¸c˜ao, erro associado, consumo de potˆencia, etc.

Tendo em conta as aplica¸c˜oes em sistemas embarcados, tais como rob´otica, redes de sensores, extra¸c˜ao de caracter´ısticas, processos de aprendizado de m´aquinas, s´ıntese de som, planejamento e otimiza¸c˜ao de trajet´oria, filtros adaptativos, entre outras; assim como as dificuldades acima descritas no uso de bibliotecas oferecidas por diversos fa- bricantes, foi decidido desenvolver as bibliotecas de c´alculo aritm´etico e trigonom´etrico em ponto flutuante, levando em considera¸c˜ao trˆes aspectos importantes: (a) descri¸c˜ao de hardware gen´erica que possibilite a portabilidade de plataformas (Xilinx, Altera ou Microsemi); (b) arquiteturas parametriz´aveis que permitam a mudan¸ca no tamanho de palavra viabilizando uma an´alise de erro associado e; (c) escolha de parˆametros pr´oprios de cada algoritmo, tais como n´umero de itera¸c˜oes e n´umero de sementes das aproxima¸c˜oes iniciais, viabilizando ajustes de precis˜ao, segundo o tipo de aplica¸c˜ao a que se destinam os operadores.

No contexto deste trabalho, foram utilizados os algoritmos Goldschmidt’s e Newton- Raphson para a implementa¸c˜ao dos operadores de divis˜ao e raiz quadrada, assim como as expans˜oes por s´eries de Taylor e o algoritmo CORDIC para a implementa¸c˜ao dos operadores trigonom´etricos. As arquiteturas desenvolvidas foram validadas para di- ferentes tamanhos de palavra (24, 28, 32, 43 e 64 bits), obtendo dados de consumo de recursos, desempenho, erro associado, frequˆencia de opera¸c˜ao e, em alguns casos, estima¸c˜ao do consumo de potˆencia.

Considerando a grande quantidade de resultados coletados, neste cap´ıtulo ser˜ao apre- sentadas unicamente as arquiteturas consideradas necess´arias para o entendimento das implementa¸c˜oes de hardware dos algoritmos de otimiza¸c˜ao, os quais s˜ao descritos no seguinte cap´ıtulo. No entanto, uma an´alise completa das implementa¸c˜oes dos opera- dores, dos algoritmos utilizados e dos resultados obtidos pode ser encontrada em [129], [130], [131] e [132].

Com base na an´alise experimental apresentada em [129] e [132] foi poss´ıvel estabelecer que a implementa¸c˜ao do algoritmo Goldschmidt’s (GS) para divis˜ao e raiz quadrada

requer mais recursos de hardware do que o algoritmo Newton-Raphson (NR). Embora o custo em ´area da arquitetura GS seja levemente maior do que a arquitetura NR, o primeiro algoritmo alcan¸ca frequˆencias de opera¸c˜ao maiores devido `a abordagem paralela na implementa¸c˜ao das equa¸c˜oes iterativas [129]. Adicionalmente, o algoritmo NR apresentou um erro associado levemente inferior em compara¸c˜ao com o algoritmo GS para os operadores de divis˜ao e raiz quadrada.

Por outro lado, conforme apresentado em [130] e [131], foi poss´ıvel concluir que a arquitetura de expans˜ao por s´eries de Taylor (FPTaylor ) para c´alculo das fun¸c˜oes tri- gonom´etricas ´e mais econˆomica em termos de flip-flops e LUTs do que as arquiteturas baseadas no algoritmo CORDIC (FPCordic). Este fato pode ser explicado devido a que na arquitetura FPTaylor apenas uma unidade FPadd ´e utilizada, enquanto a arquite- tura FPCordic ´e baseada em unidades FPadd em paralelo [129], [132]. As frequˆencias de opera¸c˜ao das arquiteturas FPCordic s˜ao aproximadamente 70MHz para uma imple- menta¸c˜ao de precis˜ao dupla e aproximadamente 85 MHz para uma implementa¸c˜ao de precis˜ao simples. Isto demonstra que a representa¸c˜ao de 32 bits ´e 17.6% mais r´apida do que a representa¸c˜ao de 64 bits, sendo, portanto, relevante para aplica¸c˜oes embarcadas de alto desempenho em que a precis˜ao do c´alculo n˜ao ´e um fator cr´ıtico.

A tabela 3.1 apresenta, de forma qualitativa, um quadro comparativo entre as arqui- teturas GS e NR e as arquiteturas FPCordic/FPTaylor para as vari´aveis de projeto de custo em ´area l´ogica, erro associado e latˆencia em ciclos de rel´ogio. Este quadro comparativo foi constru´ıdo considerando diferentes tamanhos de palavra, n´umero de itera¸c˜oes dos algoritmos, entre outros parˆametros de ajuste, segundo mostrado em [129], [130] e [131]. Na tabela ´e poss´ıvel observar que a arquitetura Newton-Raphson apresenta melhores resultados de custo em ´area, erro associado e tempo de execu¸c˜ao com rela¸c˜ao `a arquitetura Goldschmidt’s para o c´alculo da divis˜ao e da raiz quadrada. De forma similar, pode-se concluir que a arquitetura FPTaylor apresenta um custo em ´area e uma latˆencia menor se comparado com a arquitetura FPCordic, por´em o erro associado para o c´alculo das fun¸c˜oes sin, cos e atan ´e consideravelmente maior para a arquitetura FPTaylor.

Tabela 3.1: Quadro comparativo entre arquiteturas

Opera¸c˜ao Compara¸c˜ao Custo em ´area Erro associado Latˆencia

Divis˜ao GS/NR Maior Levemente maior Levemente maior

Raiz quadrada GS/NR Maior Igual Maior

Os resultados de s´ıntese obtidos durante a an´alise das arquiteturas propostas demons- traram que o consumo de blocos DSPs ´e um fator cr´ıtico no desenvolvimento em FPGAs dos operadores aritm´eticos e trigonom´etricos [129], [130]. Com base no anteriormente descrito e, ap´os a an´alise de tradeoff entre consumo de recursos, erro associado e tempo de execu¸c˜ao, foram escolhidos os algoritmos Newton-Raphson para a implementa¸c˜ao dos operadores de divis˜ao e raiz quadrada e o algoritmo CORDIC para a implementa¸c˜ao dos operadores trigonom´etricos.

Neste cap´ıtulo apresentam-se arquiteturas melhoradas dos operadores de soma e sub- tra¸c˜ao (F P add) e de multiplica¸c˜ao (F P mul) assim como dos algoritmos Newton- Raphson e CORDIC, as quais visam um consumo menor de blocos DSPs e uma frequˆencia de opera¸c˜ao maior sem detrimento do erro associado. As arquiteturas me- lhoradas das unidades F P add e F P mul permitiram um aumento na frequˆencia de opera¸c˜ao dos operadores de c´alculo trigonom´etrico. Adicionalmente, se comparado com os resultados apresentados em [129], [132], a nova arquitetura do algoritmo NR para divis˜ao apresenta uma economia de blocos DSPs de 5.5 e 2.7 vezes para tamanhos de palavra de 32 e 64 bits, respectivamente. De forma similar, a nova arquitetura NR para raiz quadrada apresenta uma economia de blocos DSPs de 6.5 e 5.1 vezes para tamanhos de palavra de 32 e 64 bits, respectivamente, se comparado com os resultados apresentados em [129], [132].

´

E comum encontrar na literatura implementa¸c˜oes de hardware em ponto flutuante de 32 e 64 bits, sendo a implementa¸c˜ao de 32 bits a mais utilizada devido ao baixo consumo de recursos. Entretanto, uma implementa¸c˜ao em ponto flutuante de 27 bits (1 bit de sinal, 8bits de expoente e 18 bits de mantissa) constitui uma implementa¸c˜ao mais eficiente em termos de consumo de recursos para desenvolvimento em FPGAs. Isto ´e devido a que os blocos DSPs usados nos dispositivos FPGAs s˜ao baseados em multiplicadores de 9x9 nas fam´ılias Cyclone e Stratix da Altera, ou 18x18 e 18x25 nas fam´ılias Spartan e Virtex da Xilinx, respectivamente. Desta forma, implementa¸c˜oes de hardware em ponto flutuante com mantissas de 18 bits usam menos blocos DSP do que implementa¸c˜oes de precis˜ao simples, as quais usam mantissas de 23 bits. Neste contexto, o presente cap´ıtulo tamb´em apresenta uma an´alise comparativa dos resultados de s´ıntese para representa¸c˜oes de 27, 32 e 64 bits. ´E importante salientar que a implementa¸c˜ao de 27 bits possibilita uma faixa dinˆamica similar `a implementa¸c˜ao de 32 bits, por´em com um aumento no erro associado, como ser´a explicado na an´alise dos resultados.