UNIVERSIDADE CATÓLICA DE PELOTAS
CENTRO POLITÉCNICO
PROGRAMA DE PÓS-GRADUAÇÃO EM INFORMÁTICA
Aplicação de Algoritmos Heurísticos na Ordenação e Particionamento de
Coeficientes em Arquiteturas de Filtros FIR
por
Angelo Gonçalves da Luz
Trabalho Individual I
TI-2009/2-002
Orientador: Prof. Dr. Eduardo Antonio César Costa
Co-Orientador: Prof. Dr. Marilton Sanchotene de Aguiar
Pelotas, Fevereiro de 2010
SUMÁRIO
LISTA DE FIGURAS .................................................................................................................................... 4
LISTA DE TABELAS .................................................................................................................................... 5
LISTA DE ABREVIATURAS E SIGLAS .......................................................................................................... 6
RESUMO .................................................................................................................................................. 7
ABSTRACT ................................................................................................................................................ 8
1
Introdução ................................................................................................................................... 9
2
Consumo de Potência em Circuitos CMOS.................................................................................. 11
2.1
3
4
5
Consumo de Potência Dinâmica .................................................................................................. 11
Codificação para Baixo Consumo de Potência ............................................................................. 14
3.1
Codificação Bus-Invert ................................................................................................................. 14
3.2
Codificação Gray .......................................................................................................................... 15
3.3
Codificação Híbrida...................................................................................................................... 15
FILTROS DE RESPOSTA FINITA AO IMPULSO - FIR ......................................................................... 17
4.1
Características ............................................................................................................................. 17
4.2
Tipos de Filtros ............................................................................................................................. 19
Heurísticas .................................................................................................................................. 23
5.1 Heurísticas Construtivas .............................................................................................................. 23
5.1.1
Heurística do Vizinho mais Próximo .................................................................................. 23
5.1.2
Heurística de Bellmore e Nemhauser ................................................................................ 24
5.2 Metaheurísticas ........................................................................................................................... 25
5.2.1
Algoritmos Genéticos ......................................................................................................... 26
5.2.1.1
Representação ............................................................................................................... 27
5.2.1.2
Decodificação ................................................................................................................ 27
5.2.1.3
Avaliação da População................................................................................................. 27
5.2.1.4
Operadores Genéticos ................................................................................................... 28
5.2.1.4
Substituição da população ........................................................................................... 29
5.2.1.5
Critério de Parada.......................................................................................................... 29
5.2.2
GRASP ................................................................................................................................. 30
5.2.2.1
Fase de Construção........................................................................................................ 30
5.2.2.2
Fase de Busca Local ....................................................................................................... 32
5.2.2.3
Critério de Parada.......................................................................................................... 32
5.2.3
Outras Metaheurísticas...................................................................................................... 33
5.2.3.1 Multi-Start ............................................................................................................................ 33
5.2.3.2 Simulated Annealing ............................................................................................................ 33
5.2.3.3 Busca Tabu ........................................................................................................................... 34
5.2.3.4 Colônia de Formigas ............................................................................................................. 35
6
7
Resultados.................................................................................................................................. 37
6.1
Resultados Obtidos com os Coeficientes Originais ..................................................................... 38
6.2
Resultados obtidos através da Codificação ................................................................................ 39
Trabalhos Relacionados .............................................................................................................. 41
2
8
Conclusões .................................................................................................................................. 43
Referências .......................................................................................................................................... 44
3
LISTA DE FIGURAS
Figura 1. Caracterização da potência dinâmica de uma porta CMOS .............................12
Figura 2. Gráfico da variação das correntes dinâmicas com capacitâncias de carga e
rampas ..............................................................................................................................13
Figura 3. Codificação Bus-Invert.....................................................................................15
Figura 4. Codificação Gray .............................................................................................15
Figura 5. Conversão entre codificação Binária e Híbrida ...............................................16
Figura 6. Exemplo de número de transições em codificação Binária e Híbrida .............16
Figura 7. Arquitetura do Filtro FIR totalmente paralelo ..................................................18
Figura 8. Arquitetura do filtro FIR totalmente sequencial...............................................19
Figura 9. Arquitetura do filtro FIR Semi-paralelo ...........................................................19
Figura 10. Filtro FIR passa baixa com 40 coeficientes ...................................................20
Figura 11. Filtro FIR passa baixa com 11 coeficientes ..................................................21
Figura 12. Filtro FIR passa alta .......................................................................................21
Figura 13. Filtro Passa Faixa ...........................................................................................22
Figura 14. Filtro Rejeita faixa..........................................................................................22
Figura 15. Exemplo de aplicação do operador crossover ................................................28
Figura 16. Exemplo de aplicação do operador de mutação .............................................29
Figura 17. Pseudocódigo do procedimento GRASP .......................................................30
Figura 18. Pseudocódigo da fase de construção. .............................................................32
Figura 19. Pseudocódigo da fase de busca local. ............................................................32
Figura 20. Relação entre temperatura e aceitação de movimentos.................................34
Figura 21. Ferramenta automática para ordenação e particionamento de coeficientes ...38
4
LISTA DE TABELAS
Tabela 1. Representação do código Híbrido (m=2) ........................................................16
Tabela 2. Vizinhança de Elementos .................................................................................23
Tabela 3. Natureza e Algoritmos Genéticos ....................................................................26
Tabela 4. Etapas de Algoritmos genéticos .......................................................................26
Tabela 5. Tipos de representação dos cromossomos .......................................................27
Tabela 6. Avaliação de aptidão ........................................................................................28
Tabela 7. Especificações dos Filtros FIR .........................................................................37
Tabela 8. Número de transições dos coeficientes originais .............................................38
Tabela 9. Número de transições dos coeficientes originais e codificados .......................39
Tabela 10. Número de transições dos coeficientes originais e codificados com a
aplicação de Heurísticas ..................................................................................................40
5
LISTA DE ABREVIATURAS E SIGLAS
FIR
Finite Impulse Response.
DSP
Digital Signal Processing.
PMOS
P-type Metal Oxide Semiconductor.
CMOS
Complementary Metal Oxide Semiconductor.
NMOS
N-type Metal Oxide Semiconductor.
VLSI
Very Large Scale Integration.
IIR
Infinity Impulse Response.
DFT
Transformada Discreta de Fourier
GRASP Greedy Randomized Adaptive Search Procedure
LRC
Lista Restrita de Candidatos.
ASIC
Application-Specific Integrated Circuit
TDF
Transposed Direct-Forms
DF
Direct Form
6
RESUMO
Este trabalho tem como objetivo a implementação de algoritmos baseados em
heurísticas para encontrar a melhor ordenação e particionamento de coeficientes de
filtros FIR (Finite Impulse Response). Devido às características destes filtros, que
envolvem multiplicações de dados de entrada com coeficientes apropriados, em uma
operação conhecida como convolução, a busca pela melhor ordenação e particionamento
destes coeficientes pode contribuir para a redução da atividade de chaveamento nos
barramentos de dados, o que resulta na redução do consumo de potência nos filtros.
Desta forma, foram implementados quatro algoritmos para a busca da melhor ordenação
e do melhor particionamento dos coeficientes. Os resultados são apresentados em
termos da distância de Hamming entre os coeficientes consecutivos. Outra técnica
utilizada neste trabalho para a redução do consumo de potência nos filtros é a
codificação de operandos. Esta técnica é utilizada para reduzir o consumo de potência
na transmissão de informações em barramentos, reduzindo a atividade de chaveamento.
Em particular, algumas destas técnicas, tais como Bus-Invert, Gray e codificação
Híbrida foram utilizadas neste trabalho juntamente com heurísticas a fim de analisar o
seu impacto na redução do consumo de potência dos filtros.
Palavras-chave: Filtros FIR, convolução, ordenação e particionamento de coeficientes,
codificação de operandos, redução de consumo de potência.
7
ABSTRACT
This work aimed the implementation of heuristic-based algorithms for the best
ordering and partitioning of coefficients in Finite Impulse Response (FIR) filters. Due
to the characteristics of the FIR filter algorithms, which involve multiplications of input
data with appropriate coefficients, in an operation known as convolution, the search for
the best ordering and partitioning of these operations can contribute for the reduction of
the switching activity in data buses, what leads to the minimization of power
consumption in the filters. Thus, four algorithms were implemented for the ordering
and partitioning of the coefficients and all of them are based on some heuristic
approach. The results are presented in terms of the Hamming distance between the
consecutive coefficients. Another technique used in this work for the power reduction in
the filters is the data encoding. This technique is used for the decrease of power
consumed for transmitting information over buses by reducing the switching activity, we
have used some of these encoding techniques in the coefficients. Bus-Invert, Gray and
Hybrid encoding are used in order to verify the impact on reducing the switching
activity of the coefficients after using the implemented heuristic-based algorithms.
Keywords: FIR filters, convolution, Ordering and Partitioning of the Coefficients,
encoding operands, reduce power consumption.
8
1
INTRODUÇÃO
O consumo de potência é um dos principais parâmetros em projetos de circuitos
integrados, devido ao fato de não haver um crescimento da eficiência na tecnologia das
baterias na mesma velocidade com que há a demanda por equipamentos portáteis
operados por bateria.
Desta forma, há uma pressão natural para a redução do consumo de potência
nestes equipamentos, de tal forma que haja um aumento do tempo de vida útil das suas
baterias. Diante disso, surge o desafio de implementar arquiteturas que consumam o
mínimo de potência, sem comprometer o seu desempenho, para a utilização nestes
dispositivos operados por bateria.
Uma classe de algoritmos que tem merecido especial atenção, com aspectos de
baixa potência, são os de processamento digital de sinais (Digital Signal Processing –
DSP). Este interesse tem se intensificado desde a proliferação dos equipamentos
eletrônicos portáteis de alto desempenho operados por baterias, tais como telefones
celulares, leitores de CD´s, equipamentos biomédicos, etc.
Em aplicações DSP, uma das operações mais utilizadas inclui a filtragem dos
sinais com resposta finita ao impulso (FIR – Finite Impulse Response) [1], [2]. Dada a
natureza deste tipo de algoritmo, que inclui um elevado número de operações
aritméticas de soma e multiplicação, a sua implementação geralmente apresenta um
elevado consumo de potência. Este fato se deve principalmente aos circuitos
multiplicadores, que são responsáveis por uma parte significativa do consumo de
potência global dos equipamentos da área DSP. Desta forma, torna-se importante a
aplicação de técnicas de baixa potência em circuitos desta área.
No algoritmo de filtro FIR, que envolve o processo de convolução, a ordem da
computação dos produtos dos dados de entrada com os coeficientes afeta diretamente a
sequencia com que os coeficientes aparecem no barramento de dados. Por outro lado,
dado que a operação em filtros FIR é comutativa e associativa, a saída dos filtros FIR é
independente da ordem de computação dos produtos dos coeficientes. Desta forma, a
ordenação dos coeficientes pode ser utilizada como técnica para a redução do consumo
de potência, onde todos os coeficientes são ordenados em um circuito totalmente
sequencial, a fim de minimizar o número de transições no multiplexador de entrada e no
barramento de dados [3]. Em [4], esta técnica foi estendida para fazer a ordenação e
9
também o particionamento de coeficientes a fim de poder ser utilizada em arquiteturas
de filtros FIR do tipo Semi-Paralela, onde o hardware é duplicado e os coeficientes são
divididos em grupos. Sendo assim, é escolhido para cada coeficiente em qual partição
ele se encaixa melhor, fazendo o cálculo do Hamming entre ele e todos outros
coeficientes, para então inseri-lo na melhor partição.
Embora as técnicas de [3] e [4] obtenham resultados satisfatórios com a
ordenação e particionamento dos coeficientes, estes algoritmos exploram todas as
possibilidades possíveis de ordenação, o que os limita a um pequeno grupo de
coeficientes, onde as permutações ainda são calculadas em um tempo razoável. No
entanto, para um maior número de coeficientes estes algoritmos exaustivos são menos
atraentes devido ao tempo necessário para processar um grande número de
combinações.
Neste trabalho foram implementados dois algoritmos baseados em heurísticas
chamados Vizinho Mais Próximo e Bellmore e Nemhauser [5], [6], a fim de alcançar
resultados o mais próximo possível de soluções ótimas para a ordenação e
particionamento de filtros com uma grande quantidade de coeficientes. Foi testado o uso
dos algoritmos na combinação de diferentes números de coeficientes e diferentes
larguras de operandos que foram obtidos a partir do algoritmo de Remez através da
ferramenta Matlab. A ferramenta proposta calcula automaticamente a distância de
Hamming entre coeficientes consecutivos.
Métodos de codificação de dados são bastante utilizados para a redução de
consumo potência nos barramentos, através da redução de atividade de chaveamento.
Sendo assim, foram utilizadas algumas dessas técnicas de codificação, tais como BusInvert [7], Gray [8] e Codificação Hibrida [4] a fim de verificar o impacto na redução da
atividade de chaveamento dos coeficientes. Os resultados mostram que dependendo da
heurística utilizada, o número de transições pode ser reduzido consideravelmente. Com
o uso da heurística Bellmore e Nemhauser aplicado nos coeficientes da codificação
híbrida, mais de 70% de redução no número de transições pode ser alcançado.
10
2
CONSUMO DE POTÊNCIA EM CIRCUITOS CMOS
Um dos principais parâmetros no projeto de circuitos digitais é o consumo de
potência. Sendo assim, a potência de pico é utilizada a fim de analisar a confiabilidade
dos circuitos, porém o fator mais importante é o consumo de potência médio durante
determinado tempo [9].
Existem três fontes principais de consumo de potência em circuitos CMOS,
sendo elas: consumo de potência estática, consumo de potência de curto circuito e o
consumo de potência dinâmica. O consumo de potência estática é causado pelas
correntes de fuga, o consumo de potência de curto circuito é causado pela corrente direta
da fonte de alimentação para o terra durante o processo de chaveamento de uma porta
lógica, e o consumo de potência dinâmica é dado pela carga e descarga das capacitâncias
dos circuitos.
Dentre estas fontes de consumo de potência, a responsável pelo maior gasto de
energia, na maioria dos casos, é o consumo de potência dinâmica, para tecnologias
acima de 100nm.
2.1 Consumo de Potência Dinâmica
Este trabalho tem por objetivo reduzir a potência dinâmica em filtros FIR, pois
esta parcela representa a maior fonte de consumo de potência em circuitos digitais
CMOS para tecnologias acima de 100nm.
A potência dinâmica consumida ocorre pela carga e descarga da capacitância dos
circuitos. A componente de chaveamento dinâmica de dissipação de potência (Pdin) em
uma transição na saída de uma porta carregada por um capacitor CL é dada de acordo
com a Equação 1, onde A não é simplesmente f (frequência), mas em geral uma
probabilidade de atividade normalizada a (menor do que 1 para modelo de atraso zero) é
computada como função da estatística de entrada e modelos lógicos, pois nem todos os
nós mudam em um determinado ciclo de relógio.
P = C AV
= afC V
(1)
A componente de chaveamento de energia drenada da fonte de alimentação para
uma transição 0 → na saída de uma porta CMOS é dada por , onde é a
capacitância de carga no nó de saída. A Figura 1 mostra um modelo de circuito
destacando a componente de potência de chaveamento [10].
11
Figura 1. Caracterização da potência dinâmica de uma porta CMOS
Considerando uma transição 0 → na saída do circuito, pode-se estabelecer a
potência instantânea (ignorando a potência de curto-circuito) de acordo com a Equação
2, onde é a corrente drenada da fonte de alimentação e que circula no capacitor e é dada de acordo com a Equação 3 [10].
=
= = (2)
(3)
A energia drenada da fonte de alimentação para uma transição 0 → no nó de
saída é dada de acordo com a Equação 4.
&
→
= ! " = !
%%
"#$ = (4)
Para a transição na saída do circuito, a energia armazenada no capacitor de carga
de saída, Ecap é dada pela Equação 5.
T
T
vdd
Ecap = ∫ Pcap (t )dt = ∫ Vout L(t )dt =
i
0
0
∫CV
L out
0
1
dVout = C LVdd2
2
(5)
Conclui-se que metade da energia drenada da fonte de alimentação é armazenada
no capacitor de carga, e metade da energia é dissipada na rede PMOS. Para uma
transição Vdd → 0 na saída, nenhuma carga é drenada da fonte de alimentação e a
1
energia armazenada no capacitor ( C LVdd2 ) é dissipada na rede NMOS pull-down.
2
A Figura 2 mostra que a componente dinâmica normalizada é linearmente
proporcional à capacitância de carga C L e a extrapolação para C L = 0 é somente
12
dependente dos fatores parasitas da porta, de acordo com a Equação 4 [11].
Deste modo, a potência dinâmica ( Pdin ) pode ser macro modelada, para um
projeto baseado em células, de acordo com a Equação 6, onde C L é a capacitância de
carga extrínseca da porta e Ci é a carga intrínseca para uma célula lógica dada.
Pdin =
1
afVdd2 (Ci + C L )
2
(6)
Como pode ser visto na Figura 2, a rampa de entrada não afeta significativamente
a componente de potência dinâmica, quando esta é controlada para ser rápida o
suficiente em relação à saída. Para uma rampa de entrada infinita (T ≅ 0ns ) até uma
variação mais lenta na entrada T=2ns (isto é, entrada Tin = 0,4ns / V para Vdd = 5V ), a
potência dinâmica tem como fator de controle fundamentalmente a carga/descarga do
capacitor externo. Para rampas de entrada extremamente lentas (T=25ns ou mais),
observa-se a condição que tende ao regime de chaveamento adiabático [12]. Neste
regime, pode-se ter uma componente dinâmica tão pequena quanto se queira, ao custo
de circuitos extremamente lentos (como mostrado para uma rampa de entrada de 25ns
na Figura 2). O regime adiabático não é considerado na modelagem da potência
dinâmica, dado que neste regime, a principal componente de dissipação de potência é o
curto-circuito.
Figura 2. Gráfico da variação das correntes dinâmicas com capacitâncias de carga e rampas
13
3
CODIFICAÇÃO PARA BAIXO CONSUMO DE POTÊNCIA
Codificação tem sido muito utilizada em sistemas de comunicação para controlar
as estatísticas dos símbolos de dados transmitidos, ou em outras palavras, para controlar
o espectro do sinal transmitido [8].
Técnicas para baixo consumo de potência na comunicação global em CMOS
VLSI utilizando métodos de codificação de dados podem ser encontradas em [9], onde é
comprovado que essas técnicas podem reduzir a energia consumida para a transmissão
de informações sobre os caminhos de carga pesada de comunicação (barramento),
reduzindo a atividade de chaveamento. Neste trabalho foram utilizadas as codificações
Bus-Invert, Gray e a codificação híbrida, com os seguintes objetivos: i) verificar o
impacto na redução da atividade de chaveamento dos coeficientes de um filtro FIR e ii)
verificar a melhor ordenação dos coeficientes quando utilizando-se os algoritmos
heurísticos.
3.1
Codificação Bus-Invert
O método de codificação Bus-Invert faz a codificação das palavras a fim de
reduzir o consumo de potência, onde cada uma das palavras pode ter o seu valor
invertido antes da sua transmissão, se isso proporcionar uma redução no número de
transições [7]. Neste método uma linha extra de barramento é utilizada, chamada invert.
O método faz a analise de duas palavras de dados consecutivas do barramento. Se a
distância de Hamming entre a palavra seguinte e a atual for menor do que W/2, a palavra
seguinte é enviada como está, com invert igual a 0. Caso contrário, cada bit da palavra
seguinte é invertido e o invert recebe valor igual a 1, indicando que a palavra foi
invertida. O método Bus-Invert é explorado em [7] em seqüências de palavras para
minimizar transições. Por exemplo, palavras podem ser invertidas, reordenadas e então
transmitidas. A Figura 3 mostra um exemplo de aplicação de Bus-Invert
14
Figura 3. Codificação Bus-Invert
3.2 Codificação Gray
Um dos métodos de codificação mais utilizado para redução da atividade de
chaveamento é a codificação Gray [8]. Em uma seqüência de contagem em código Gray
apenas um bit muda de representação entre valores consecutivos, podendo produzir,
desta forma, uma redução bastante significativa no número de transições em relação ao
código binário.
Um exemplo de transformada de codificação binária em codificação Gray é
apresentada na Figura 4.
Figura 4. Codificação Gray
3.3 Codificação Híbrida
A idéia da codificação híbrida é dividir os operandos em grupos de m-bits,
codificando cada grupo utilizando código Gray e usando o método binário para propagar
o carry entre estes grupos [4]. Desta forma, o número de transições dentro de cada
grupo é minimizado e uma estrutura regular pode ser facilmente construída. A Tabela 1
15
exemplifica a codificação híbrida para 4 bits com m=2.
Tabela 1. Representação do código Híbrido (m=2)
Dec
Hyb
Dec
Hyb
Dec
Hyb
Dec
Hyb
0
0000
4
0100
8
1100
12
1000
1
0001
5
0101
9
1101
13
1001
2
0011
6
0111
10
1111
14
1011
3
0010
7
0110
11
1110
15
1010
O código híbrido pode facilmente ser aplicado em barramentos, onde economia
de energia pode ser mais facilmente alcançada quando existe um maior grau de
correlação entre os bits. Uma característica da codificação híbrida é que a conversão
entre Binário e Híbrido é muito simples, como mostra a Figura 5. Transformando
palavras de W bits entre Binário e Híbrido em qualquer direção, tudo que é necessário é
uma porta EXOR em cada grupo de m=2. Desta forma, o overhead em termos de
transcodificação é reduzido. Fazer esta codificação é muito desejável mesmo em caso de
endereços de barramentos. A Figura 6 mostra um exemplo de numero de transições
necessárias para os códigos Binários e Híbridos.
Figura 5. Conversão entre codificação Binária e Híbrida
Figura 6. Exemplo de número de transições em codificação Binária e Híbrida
16
4 FILTROS DE RESPOSTA FINITA AO IMPULSO - FIR
Em processamento de sinais, há muitos casos em que um determinado sinal de
entrada para um determinado sistema apresenta informações desnecessárias ou mesmo
ruídos adicionais que podem degradar a qualidade do que se deseja transmitir. Nestes
casos, pode-se remover ou filtrar as amostras inúteis. Por exemplo, no caso do sistema
de telefonia, não há razão para transmitir freqüências muito altas desde que todos os
sinais estejam dentro de uma determinada faixa (400 a 3.400 Hertz). Portanto, neste
caso, todas as frequências acima e abaixo dessas frequências são filtradas. A faixa de
freqüência entre 400 e 3.400 Hz, as quais não são filtradas, são conhecidas como banda
passante (“passband”) e a banda de freqüência que é bloqueada é conhecida como
banda rejeitada (“stopband”). Alguns filtros podem ser utilizados para realizar a
operação necessária de filtragem do sinal dentro de uma determinada faixa útil. Alguns
exemplos são filtros de resposta finita ao impulso (FIR – Finite Impulse Response),
filtros de resposta infinita ao impulso (IIR – Infinite Impulse Response) e filtros
adaptativos.
Neste trabalho, os filtros FIR são utilizados como estudo de caso para o
uso das técnicas de redução da atividade de chaveamento nos barramentos de dados. A
seguir são apresentadas as principais características deste tipo de filtro.
4.1
Características
A operação de filtragem de resposta finita ao impulso (FIR) é realizada a partir
do processo de convolução das amostras dos dados de entrada com a resposta ao
impulso unitária.
Um filtro FIR pode ser matematicamente expresso pelo somatório dos pesos das
ultimas N amostras de dados de entrada, como apresentado na Equação 7.
N −1
Y [ n ] = ∑ H [i ] X [ n − i ]
(7)
i =0
Na equação 7, “X” representa o sinal de entrada, “H” os coeficientes do filtro,
“Y” o sinal de saída, “n” é a posição atual, “N” é o numero de coeficientes (taps) do
filtro. Essa é uma operação de convolução dos coeficientes do filtro sobre o sinal. Os
coeficientes do filtro FIR são obtidos pela Transformada Discreta de Fourier (DFT –
Discrete Fourier Transform) da freqüência necessária da função de transferência,
aplicando algum método de janelamento. Nesse trabalho foram utilizados algoritmos de
17
Remez para o cálculo dos coeficientes.
A forma mais direta de implementação de filtros FIR é a partir da arquitetura
totalmente paralela, onde unidades de atraso são usadas para armazenar previamente
amostras de sinal. Na forma direta, em cada ciclo de relógio uma nova amostra e os
correspondentes coeficientes do filtro são simultaneamente aplicados a cada
multiplicador. O resultado de todos multiplicadores são somados simultaneamente. Essa
arquitetura é apresentada na figura 7.
Figura 7. Arquitetura do Figura
Filtro FIR
5. totalmente paralelo
Na implementação totalmente seqüencial um conjunto de operações de
multiplicações e somas é realizado para cada amostra de dados de sinal de entrada. Isso
é realizado, multiplicando-se as “N” amostras de entrada pelos coeficientes e somando
os resultados parciais para gerar o sinal de saída. Na implementação totalmente
seqüencial a idéia básica é de reduzir os requisitos do hardware reutilizando-o o
máximo possível. A Figura 8 mostra a arquitetura totalmente seqüencial do filtro FIR.
A fim de acelerar as computações do filtro FIR, uma arquitetura semi-paralela
pode ser implementada, onde os requisitos de hardware são duplicados com relação à
totalmente seqüencial, permitindo que duas amostras possam ser processadas
simultaneamente. A figura 9 mostra a arquitetura semi-paralela do filtro FIR.
18
Figura 8. Arquitetura do filtro FIR totalmente sequencial
Figura 9. Arquitetura do filtro FIR Semi-paralelo
4.2 Tipos de Filtros
Existem vários diferentes tipos de respostas de filtros. Cada um apresenta uma
resposta única baseada: i) na freqüência de corte do tipo do filtro, ii) no número de
coeficientes utilizado e iii) no nível de tolerância utilizado. Para melhor entendimento
pode-se observar estes atributos na Figura 10, e o comportamento obtido pelos
diferentes tipos de filtros também serão mostrados a seguir.
A Figura 10 demonstra a curva de um filtro FIR passa baixa com 40 coeficientes
19
(taps) onde, “passband ripple” representa a tolerância da banda passante, “stopband
ripple” a banda de parada e “stopband attenuation” representa a atenuação na banda de
parada. A Figura 11 apresenta o mesmo filtro FIR da Figura 10 (passa baixa), porém
representado com apenas 11 coeficientes, o que mostra uma grande redução na precisão
do sinal. Isso mostra a importância do número de coeficientes na resposta do filtro, que
é representada pelo processo de convolução.
A representação de um filtro que rejeita as baixas freqüências e aceita as altas
freqüências é apresentado na Figura 12. Este filtro é chamado de Passa Alta. A Figura 13
apresenta um filtro do tipo passa faixa (passband), que rejeita as freqüências extremas e
aceita as freqüências intermediarias. O filtro rejeita faixa (stopband) mostrado na Figura
14 apresenta comportamento inverso ao passband, aceitando apenas as freqüências das
extremidades e rejeitando as freqüências intermediárias.
Figura 10. Filtro FIR passa baixa com 40 coeficientes
20
Figura 11. Filtro FIR passa baixa com 11 coeficientes
Figura 12. Filtro FIR passa alta
21
Figura 13. Filtro Passa Faixa
Figura 14. Filtro Rejeita faixa
22
5 HEURÍSTICAS
Heurísticas são algoritmos que têm por objetivo encontrar boas soluções,
ocasionalmente a melhor, sem grande custo computacional para problemas que exigem
alto poder computacional para encontrar soluções ótimas.
Existem muitas heurísticas na literatura, as quais podem ser classificadas como
construtivas ou de refinamento. Neste trabalho apenas heurísticas construtivas são
utilizadas.
5.1
Heurísticas Construtivas
Heurísticas construtivas [5], [6] têm por características a construção de soluções
do tipo elemento a elemento, ou seja, faz escolhas ótimas locais, escolhendo sempre a
melhor solução para o elemento atual, sem tratamento em busca de ótimos globais.
Algumas heurísticas construtivas encontradas na literatura são: Heurística do
Vizinho mais Próximo, Heurística de Bellmore e Nemhauser e Heurística da Inserção
Mais Barata.
Dentre as heurísticas construtivas apresentadas acima, foram implementadas
neste trabalho, a do Vizinho Mais Próximo e a de Bellmore e Nemhauser.
5.1.1
Heurística do Vizinho mais Próximo
Nesta heurística parte-se de um elemento inicial e adiciona-se como elemento
seguinte o considerado melhor vizinho levando em conta uma determinada função de
custo. Tomando como exemplo os valores inseridos na Tabela 2 como sendo o custo
para inserção de um elemento.
Tabela 2. Vizinhança de Elementos
Elemento
E1
E2
E3
E4
E5
E6
E1
0
2
1
4
9
1
E2
2
0
5
9
7
2
E3
1
5
0
3
8
6
E4
4
9
3
0
2
5
E5
9
7
8
2
0
2
E6
1
2
6
5
2
0
Aplicando a heurística do Vizinho mais Próximo aos elementos da Tabela 2, temse então como ordem de menor custo encontrada ([E1] [E3] [E4] [E5] [E6] [E2]) através
23
dos seguintes passos (considerando como elemento inicial o E1):
Passo 1: Adiciona-se E3, como elemento seguinte, já que é o elemento com
menor custo na vizinhança de E1. Lista atual ([E1] [E3]).
Passo 2: Adiciona-se o E4, já que o E1, que é o elemento de menor custo, já foi
inserido, sendo assim então é inserido o segundo melhor vizinho. Lista atual ([E1] [E3]
[E4]).
Passo 3: Adiciona-se E5, já que é o melhor vizinho de E4 disponível. Lista atual
([E1] [E3] [E4] [E5]).
Passo 4: Adiciona-se E6, já que é o melhor vizinho de E5 disponível. Lista atual
([E1] [E3] [E4] [E5] [E6]).
Passo 5: Adiciona-se E2, que é o único elemento restante. Lista final ([E1] [E3]
[E4] [E5] [E6] [E2]).
O custo total dos elementos da lista é dado por:
CustoTotal = custo (E1,E3) + custo(E3, E4) + custo(E4, E5) + custo(E5, E6) +
custo(E6, E2) = 12.
5.1.2
Heurística de Bellmore e Nemhauser
Nesta heurística, parte-se de um elemento inicial, fazendo-se então a inserção de
seu melhor vizinho. A partir daí sempre são analisados os dois extremos da lista, onde
caso o melhor custo seja o da inserção do melhor vizinho do extremo esquerdo da lista,
é inserido então este vizinho como elemento extremo esquerdo da lista. Caso o extremo
direito que tenha o melhor vizinho, então é inserido o elemento como extremo direito da
lista.
Considerando-se os valores da Tabela 1, tem-se como resposta a seguinte
seqüência de elementos ([E2] [E6] [E1] [E3] [E4] [E5]), que são adquiridos através dos
seguintes passos (partindo de E1 como elemento inicial):
Passo 1: Adiciona-se E3, já que é o melhor vizinho de E1. Lista atual ([E1]
[E3]).
Passo 2: Adiciona-se E6, pois dentre os elementos ainda não adicionados,
analisando os melhores vizinhos de cada extremo da lista, tem-se que o melhor vizinho
de E1 é E6 com custo igual a 1, enquanto no outro extremo da lista tem-se E3 com seu
melhor vizinho E4 com custo 3. Desta forma, adiciona-se E6 ao extremo esquerdo da
rota. Lista atual ([E6] [E1] [E3]).
Passo 3: Adiciona-se E2 no extremo esquerdo da lista, pois dos elementos ainda
24
não adicionados, o melhor vizinho de E6 é E2 com custo igual a 2, e a que tem menor
distância de E3 é E4 com custo 3. Lista atual ([E2] [E6] [E1] [E3]).
Passo 4: Adiciona-se E4 no extremo direito da lista, pois o melhor vizinho de E2
é E5 com custo igual 7 e a que tem menor distância de E3 é E4 com custo igual a 3.
Lista atual ([E2] [E6] [E1] [E3] [E4]).
Passo 5: Como o único elemento restante é o E5, basta ver em qual extremo sua
inserção possui menor custo. Como vizinho de E2 seu custo é igual a 7, e como vizinho
de E4 seu custo é 2, então é inserido no extremo direito. Lista final ([E2] [E6] [E1] [E3]
[E4] [E5]).
O custo total é dado por:
CustoTotal = custo(E2,E6) + custo(E6, E1) + custo(E1, E3) + custo(E3, E4) +
custo(E4, E5) = 16
5.2
Metaheurísticas
Metaheurísticas são procedimentos destinados a encontrar uma boa solução,
eventualmente a ótima, consistindo na aplicação, em cada passo, de uma heurística
subordinada, a qual tem que ser modelada para cada problema específico [16].
Contrariamente às heurísticas convencionais, as metaheurísticas são de caráter
geral e têm condições de escapar de ótimos locais. Para isso, utiliza-se de técnicas que
serão apresentadas a seguir, que dão a possibilidade de alcançar os ótimos globais.
O que diferencia uma Metaheurísticas de outra é a técnica utilizada para escapar
dos ótimos locais. As metaheurísticas podem ser classificadas em duas categorias de
acordo com o princípio usado para explorar o espaço de soluções: busca local e busca
populacional.
Nas metaheurísticas de Busca Local, a exploração do espaço de soluções é feita
através de movimentos, os quais são aplicados a cada passo da solução atual, a fim de
gerar soluções melhores que a atual. Algumas Metaheurísticas baseadas nesta técnica
encontradas na literatura são: Multi-Start, Simulated Annealing e Busca Tabu.
As metaheurísticas de Busca Populacional têm por característica manter um
conjunto de boas soluções e combiná-las para a produção de soluções melhores. Um
exemplo deste tipo de algoritmo são os Algoritmos Genéticos e GRASP.
Algumas destas metaheurísticas serão apresentadas nas próximas seções, onde as
de maior interesse e maior detalhamento neste trabalho serão: Algoritmos Genéticos e
GRASP.
25
5.2.1
Algoritmos Genéticos
Os algoritmos genéticos [15], [16], [20] são técnicas baseadas na teoria da
evolução, nos quais as variáveis são representadas como genes de um cromossomo.
Juntamente com estratégias evolucionárias e programação evolutiva formam uma classe
de pesquisa baseado em evolução natural.
Algoritmos Genéticos são métodos que simulam, através de algoritmos, os
processos de evolução natural e genética buscando resolver problemas de otimização
onde o espaço de busca é muito grande e os métodos convencionais não se demonstram
eficientes.
O algoritmo básico foi estruturado de forma que as informações referentes a um
determinado sistema pudessem ser codificadas de maneira análoga aos cromossomos
biológicos.
A analogia entre o sistema natural e os algoritmos genéticos é apresentada na
Tabela 3.
Tabela 3. Natureza e Algoritmos Genéticos
Natureza
Algoritmos Genéticos
Cromossomo
Palavra binária, vetor, etc
Gene
Característica do Problema
Alelo
Valor da característica
Loco
Posição da palavra, vetor, etc
Genótipo
Estrutura
Fenótipo
Estrutura submetida ao problema
Indivíduo
Solução
Geração
Ciclo
Eles ocupam lugar de destaque entre os paradigmas da computação evolutiva.
Além disso, têm resultados bastante aceitáveis com relação aos recursos empregados e
pela ampla gama de problemas aplicáveis.
O Algoritmo Genético para um determinado problema deve ter os componentes
e etapas da Tabela 4:
Tabela 4. Etapas de Algoritmos genéticos
1
Uma representação genética para a solução do problema;
2
Decodificação do cromossomo;
3
Avaliação;
5
Operadores genéticos;
6
Substituição da população.
26
5.2.1.1 Representação
A representação das possíveis soluções do espaço de busca de um problema
define a estrutura do cromossomo a ser manipulado pelo algoritmo [20]. Este
cromossomo depende do tipo de problema e do que, essencialmente, se deseja
manipular geneticamente. Alguns tipos de representação são apresentados na Tabela 5.
Tabela 5. Tipos de representação dos cromossomos
Representação
Problemas
Binária
Numéricos, Inteiros
Números Reais
Numéricos
Permutação de Símbolos
Baseados em Ordem
Símbolos Repetidos
Grupamento
5.2.1.2 Decodificação
A decodificação do cromossomo consiste basicamente na construção de uma
solução real do problema a partir do cromossomo. O processo de decodificação constrói
a solução para que esta seja avaliada pelo problema.
5.2.1.3 Avaliação da População
A função objetivo gera uma avaliação do grau de adaptação de cada cromossomo
da população. Esta função está diretamente ligada às especificações do problema.
A função efetua a avaliação de modo que é atribuído um valor de aptidão as
possíveis soluções através de uma função de aptidão, que é definida conforme o
problema que se tem a intenção de solucionar.
A geração desta avaliação de aptidão torna-se a parte mais importante para o
procedimento do Algoritmo Genético.
O retorno desta função, que ordena os indivíduos conforme a sua adaptação, é
uma característica intrínseca ao indivíduo, que indicará biologicamente, qual é a
habilidade que um indivíduo possui para sobreviver e produzir a melhor resposta.
No Algoritmo Genético essa etapa é a mais crítica, pois já que as funções
deverão ser avaliadas para cada cromossomo de cada população durante todo o processo
evolutivo.
Em um exemplo de função de avaliação podemos considerar uma função f(x) =
x², que mede a aptidão de cada cromossomo, onde a Tabela 6 apresenta a aptidão de dois
cromossomos, onde podemos notar que a função retornou um valor bem maior para C1,
27
o que implica que ele está mais apto que C2.
Tabela 6. Avaliação de aptidão
Cromossomo
x
f(x)
C1
001001
9
81
C2
000100
4
16
5.2.1.4 Operadores Genéticos
O principal objetivo dos operadores genéticos é de serem capazes de formar uma
nova população através de sucessivas operações para que obtenha um resultado
satisfatório no final do processo.
Os operadores são de extrema importância para que se tenha uma diversificação
da população e manter as características de adaptação adquiridas das antigas gerações.
Um exemplo de operador é o operador Crossover, onde pares de genitores são
escolhidos aleatoriamente da população, baseado na aptidão, e novos indivíduos são
criados a partir da troca do material genético, sendo assim, os descendentes serão
diferentes de seus pais, mas com características genéticas de ambos.
A Figura 15 apresenta um exemplo simples de utilização deste operador, onde é
selecionado aleatoriamente um ponte de corte entre os dois genitores, gerando dois
novos indivíduos, onde de acordo com a função de avaliação vista anteriormente D1 é
um cromossomo mais apto que seus genitores, entretanto, D2 é um individuo medíocre
(baixa avaliação em f(x) = x²).
Figura 15. Exemplo de aplicação do operador crossover
Os cromossomos criados a partir do operador de crossover são então submetidos
ao operador de mutação (com uma probabilidade '( ).
Mutação é um operador exploratório que tem por objetivo aumentar a
diversidade da população.
O operador de mutação troca o conteúdo de uma posição do cromossomo, com
uma determinada probabilidade, que normalmente é baixa (menor que 1%), um exemplo
28
desta aplicação pode ser visto na Figura 16.
Figura 16. Exemplo de aplicação do operador de mutação
5.2.1.4 Substituição da população
A substituição consiste na alteração da antiga população pela nova população
gerada com os cromossomos escolhidos e modificados na fase dos operadores
genéticos, formando uma nova população.
Os critérios com que selecionam os pais não necessariamente têm que ser os
mesmos usados para selecionar os filhos. Para atender o critério de substituição existem
quatro modelos:
•
Substituição Imediata: onde os descentes substituem seus progenitores.
•
Substituição por Fator Cheio: onde os descentes substituem aqueles da
população que são mais parecidos com eles.
•
Substituição por Inserção: os membros da população de criadores são
selecionados para serem eliminados sendo substituídos pelos seus decentes.
•
Substituição por Inclusão: onde os descendentes são somados aos
progenitores gerando uma única população, de onde serão selecionados
apenas os melhores.
5.2.1.5
Critério de Parada
Um critério de parada de um algoritmo genético é verificado através de um teste,
e se a condição de parada for satisfatória é parada a execução do algoritmo. Caso não
seja atingido o critério de parada estabelecido, a população retorna às fases do algoritmo
para que se ache a melhor solução.
Outro critério da parada pode ser quando o Algoritmo Genético atingir um dado
número de gerações ou quando a função objetivo chegar a um determinado valor
definido previamente. Outro critério poderá ser a convergência, ou seja, quando não
ocorrer melhoramento significativo no cromossomo de maior aptidão por um dado
numero de gerações, o processamento pára.
29
5.2.2
GRASP
A metaheurística GRASP [15],[16],[17] (Greedy Randomized Adaptive Search
Procedure) é um algoritmo muito aplicado a problemas de otimização combinatória.
Esta metaheurística consiste em criar uma solução inicial construtiva, onde uma solução
viável para o problema, e depois efetuar uma busca local para melhorar a qualidade da
solução. Seu diferencial para outros métodos está na geração dessa solução inicial,
baseada nas três primeiras iniciais de sua sigla em inglês: gulosa (Greedy), aleatória
(Randomized) e adaptativa (Adaptive).
Algoritmos GRASP são ditos construtivos por privilegiar a geração de uma
solução inicial de melhor qualidade para utilizar a busca local apenas para pequenas
melhorias.
A estratégia de construção de uma solução no GRASP consiste na definição de
um critério de avaliação dos elementos que podem ser inseridos em um conjunto que, ao
final do processo, será uma solução para o problema de otimização que se pretende
resolver. Esse critério adapta-se à solução já construída, de forma que a valorização dos
elementos muda durante a construção da solução. Entretanto, esse critério não é tomado
como referência absoluta para a decisão do próximo elemento a ser inserido, havendo
uma escolha aleatória entre os melhores elementos a cada iteração.
A melhor solução obtida ao final da execução do GRASP é a solução final. A
Figura 17 mostra um pseudocódigo para o GRASP.
Figura 17. Pseudocódigo do procedimento GRASP
5.2.2.1 Fase de Construção
A fase de construção do GRASP é também iterativa, onde uma solução é
construída elemento a elemento. Cada inserção de um novo elemento é feita através da
30
escolha aleatória em uma lista restrita de candidatos (LRC). Considere para a construção
da LRC que o problema aqui tratado é de maximização de uma função f. A LRC é
composta de elementos candidatos à solução, avaliados de acordo com o benefício
associado a sua inclusão na solução parcial através de uma função gulosa g. Os
elementos participantes da LRC podem ser escolhidos através de duas formas: pelo
número de elementos ou pela qualidade dos elementos [18].
Na primeira forma, os elementos candidatos são ordenados em ordem
decrescente de benefício segundo a função g e os p primeiros elementos são incluídos
na LRC. O valor de p é definido como p = 1 + a (a – 1), onde a é número total de
candidatos (a é um dado de entrada que tem valores definidos no intervalo [0,1]). Note
que, se a = 0 um algoritmo totalmente guloso é executado, já que só é possível a
escolha de um único elemento a ser inserido na solução. Por outro lado, se a = 1, a lista
conterá todos os possíveis candidatos, o que resultará em um algoritmo aleatório.
Na segunda forma, considerando um problema de maximização, emin
= min{g(e)} o menor incremento a solução parcial de acordo com g e emax
= max{g(e)}, o maior incremento, a LRC será constituída dos elementos candidatos à
solução cujo valor retornado pela função g esteja no intervalo [(1 – a)(emin – emax) +
emax , emax].
Como já citado, a é um valor definido no intervalo [0,1]. Neste caso, se a = 1,
estará sendo executado um algoritmo absolutamente guloso, já que somente elementos
de maior incremento emax podem ser inseridos na solução e se a = 0, a lista conterá
todos os possíveis candidatos, o que resultará em um algoritmo aleatório.
Portanto é perceptível que a escolha do valor de a é um ponto importante no
desempenho da metaheurística GRASP. A influência desta escolha na qualidade da
solução construída é estudada em [18]. Na Figura 18 é mostrado o pseudocódigo da
rotina de construção de uma solução.
31
Figura 18. Pseudocódigo da fase de construção.
5.2.2.2 Fase de Busca Local
A busca local é uma tentativa de melhoria da solução obtida na fase de
construção (Solução). Nesta fase, percorre-se a vizinhança da solução corrente buscando
uma solução de melhor qualidade. Por exemplo, em um problema onde o objetivo é a
maximização de uma função f, entende-se que uma solução t é a melhor solução se f (t)
> f (Solução). Se não existir uma melhor solução na vizinhança, a solução corrente é
considerada um ótimo local. A busca termina quando um ótimo local for atingido. O
pseudocódigo da busca local é apresentado na Figura 19.
Figura 19. Pseudocódigo da fase de busca local.
5.2.2.3 Critério de Parada
O critério de parada do algoritmo é normalmente dado por um valor N de
iterações indicado pelo usuário. Este valor corresponde à quantidade de soluções
factíveis encontradas pela fase construtiva em que foram aplicadas a busca local. Dentre
as soluções geradas é escolhida aquela de melhor resultado gerou.
32
5.2.3
Outras Metaheurísticas
Algumas das outras metaheurísticas existentes na literatura serão apresentadas a
seguir:
5.2.3.1 Multi-Start
Esta é uma metaheurística que consiste em fazer amostragens do espaço de
soluções, aplicando às soluções procedimentos de refinamento [16].
As amostras normalmente são obtidas aleatoriamente, a fim de gerar amostras
bem diversificadas com o intuito de escapar das soluções ótimas locais.
Como critério de parada neste método, normalmente é utilizado um tempo
máximo de execução ou um número N de iterações que se considere suficiente.
Este método tem como principal vantagem a sua simplicidade de implementação.
5.2.3.2 Simulated Annealing
Uma das técnicas mais populares de busca local é a chamada Simulated
Annealing [15],[16], que é uma analogia à técnica utilizada na termodinâmica, ao
simular o resfriamento de um conjunto de átomos aquecidos, operação conhecida como
recozimento.
Esta técnica é inicializada a partir de uma solução inicial qualquer, que pode ser
obtida aleatoriamente. Em seguida, o procedimento principal consiste de um loop que
gera aleatoriamente, em cada uma das iterações, um único vizinho s’ da solução corrente
s.
Considerando esta técnica para um problema de minimização, sendo ∆ a variação
de valor da função objetivo ao mover-se para uma solução vizinha candidata, ou seja,
∆= *+ , − *+.
Se ∆ < 0 o movimento é aceito e a solução vizinha passa a ser a nova solução
corrente. Caso ∆ ≥ 0 a solução pode também ser aceita, mas com uma probabilidade
∆
dada por . /0 , onde T é um parâmetro da função que regula a probabilidade de se aceitar
soluções de pior custo chamado temperatura. Esta probabilidade de aceitar movimentos
de pior custo é utilizada a fim de escapar dos ótimos locais.
A temperatura T é reduzida gradativamente quando o número de iterações
aumenta para diminuir a aceitação de movimentos de piora conforme o algoritmo
evolui.
33
A Figura 6 mostra a relação entre temperatura e a probabilidade de aceitação de
um movimento, onde se pode claramente notar que quanto menor for a temperatura,
menor é a probabilidade de aceitar o movimento, até que quando a temperatura fica
próxima a zero a aceitação de novos movimentos se torna praticamente nula também.
Sendo assim, o critério de parada do algoritmo é dado pela sua aproximação da
temperatura ao valor 0.
Figura 20. Relação entre temperatura e aceitação de movimentos
5.2.3.3 Busca Tabu
O Busca Tabu [14],[15],[16], é um método de busca local que explora as
soluções movendo-se de um vizinho para o seu melhor vizinho.
Esta técnica, juntamente com uma estrutura de memória para armazenar as
soluções geradas possibilita escapar dos ótimos locais.
O membro s’ de uma vizinhança V com melhor valor nessa região segundo a
função f(.) torna-se a nova solução corrente mesmo que s’ seja pior que s, isto é, que
f(s’) > f(s) para um problema de minimização.
O critério de escolha do melhor vizinho é utilizado para escapar de um ótimo
local. Porém, isto pode fazer com que o algoritmo entre em um processo de ciclagem,
ou seja, acabe sempre gerando a mesma solução.
34
Para evitar este problema, foi criada uma lista chamada “Tabu”, que é uma lista
que contém movimentos proibidos. Ela é uma lista que contém os movimentos reversos
aos últimos |T| movimentos realizados, e é uma fila de tamanho fixo, que quando cheia,
ao inserir um novo elemento, o mais antigo é retirado da lista, podendo novamente ser
escolhido.
A lista Tabu, embora reduza significativamente o risco de ciclagem, por não
deixar ser feita a escolha de uma mesma solução por N iterações, ela introduz um novo
problema ao algoritmo, que ao proibir os movimentos da lista, podem também proibir
que o algoritmo passe por novos caminhos que poderiam levar a uma melhor escolha.
Para contornar este problema inserido pela lista Tabu, é utilizada uma função de
aspiração, que em determinadas circunstâncias permite a remoção do movimento da
lista Tabu. Para cada movimento v a função de aspiração retorna um valor A(v), que
representa o valor aspirado pelo algoritmo.
Um exemplo de utilização da função de aspiração é a permissão de movimentos
Tabu apenas se ele conduzir a um vizinho melhor que o melhor vizinho encontrado até o
momento.
O critério de parada deste algoritmo é normalmente dado ao atingir determinado
número de iterações.
5.2.3.4 Colônia de Formigas
Esta técnica [15], [16] tem por objetivo simular o comportamento de uma
colônia de formigas, que cooperam entre si para resolver um problema de otimização
por meio de comunicação muito simples.
No comportamento das formigas, ao deslocarem-se, elas deixam um rastro de
uma substância chamada feromônio, que é usada para se comunicarem quimicamente.
Na computação, se considera um conjunto de m formigas, cada uma localizada
em diferentes áreas de interesse (no nosso caso coeficientes), que se move de um ponto
para outro. O algoritmo executa N iterações, onde N é o número total de pontos. Em
cada iteração do algoritmo, m formigas constroem uma solução em N. Estando em um
ponto i, a formiga faz uma escolha probabilística do próximo ponto j e o arco (i, j) é
adicionado à solução.
A quantidade de feromônios depositada no arco (i,j), representa a atratividade de
escolher este caminho. As formigas depositam uma quantidade de feromônios
proporcional à qualidade da solução produzida. Sendo assim, quanto menor for o custo
35
do caminho percorrido, maior será a quantidade de feromônio depositado sobre seus
arcos, o que ajuda a dirigir a busca para soluções satisfatórias.
Para não repetir caminhos as formigas possuem um esquema de memória
baseado no mecanismo de Busca Tabu, o que evita que a formiga passe duas vezes no
mesmo caminho em uma mesma rota.
A tabela de decisão 12 = [124 ]|78 | do nó i é obtida pela composição dos
valores locais de feromônios com os valores heurísticos locais, como mostra a Equação
8.
[&8: ]; [<8: ]=
924 = ∑@
A8 [&8: ]
? [< ]=
8:
∀C ϵN
(8)
Onde:
F24 (t) é a quantidade de feromônio no arco (i,j) na iteração t.
G24 = é o valor heurístico, "24 é o peso do arco (i, j).
8:
N é o conjunto de nós vizinhos ao nó i;
H e J são os parâmetros que controlam o peso relativo entre o feromônio e a
distância entre os dois pontos. Assim, um alto valor de H significa que o valor do
feromônio é muito importante, e deste modo, as formigas tendem a escolher caminhos
pelos quais outras formigas já passaram. E se o valor de J for muito alto, a formiga
tende a eleger a cidade mais próxima.
36
6
RESULTADOS
Nesta seção são apresentados os resultados obtidos com a utilização dos
algoritmos baseados em heurísticas que foram descritos anteriormente. Estes algoritmos
foram aplicados para a redução da distancia de Hamming entre coeficientes
consecutivos, onde o distancia de Hamming representa os bits que diferem entre duas
palavras consecutivas. Os coeficientes dos filtros foram gerados a partir da ferramenta
MATLAB utilizando algoritmo de Remez. Foram utilizados os mesmos filtros FIR
apresentados em [10]. As cinco colunas da Tabela 7 apresentam as especificações do
filtro, onde Filter é apenas um identificador do filtro, passband e stopband são
freqüências normalizadas, #tap é o numero de coeficientes de cada filtro e width é o
número de bits utilizado para representação das palavras de cada coeficiente.
Tabela 7. Especificações dos Filtros FIR
Filter
passband
stopband
#tap
width
1
0.10
0.25
27
10
2
0.15
0.25
18
12
3
0.10
0.15
25
14
4
0.15
0.25
29
14
5
0.10
0.15
48
16
6
0.15
0.20
29
14
7
0.15
0.20
49
16
8
0.10
0.12
49
16
9
0.10
0.12
60
18
10
0.24
0.25
53
12
11
0.20
0.25
36
8
12
0.20
0.25
36
12
Com a finalidade de incluir os dois algoritmos baseados em heurísticas e as
codificações utilizadas neste trabalho, e gerar a ordenação e particionamento dos
coeficientes automaticamente, foi implementada uma ferramenta. Esta ferramenta
recebe como entrada os coeficientes de filtros FIR (em decimal ou em binário) e estes
são ordenados e/ou particionados de acordo com a técnica selecionada e a codificação
selecionada. A saída da ferramenta é a distância de Hamming dos coeficientes gerada
pela melhor ordenação alcançada pelos algoritmos heurísticos. A Figura 21 mostra a
interface da ferramenta proposta.
37
Figura 21. Ferramenta automática para ordenação e particionamento de coeficientes
6.1
Resultados Obtidos com os Coeficientes Originais
A Tabela 8 mostra os resultados que foram obtidos, em termos do número de
transições, dos coeficientes originais e depois utilizando as heurísticas Bellmore e
Nemhauser e Vizinho Mais Próximo para a ordenação e o particionamento dos
coeficientes. O particionamento de coeficientes divide os coeficientes em duas metades
(como um filtro FIR semi-paralelo é implementado, como mostrado anteriormente na
Figura 9).
Tabela 8. Número de transições dos coeficientes originais
Número de transições entre os coeficientes
(distância de Hamming)
Bellmore e Nemhauser
Vizinho mais Próximo
Coeficientes
Ordenação/
Ordenação/
Originais
Particionamento
Particionamento
1
85
53/52
56/53
2
67
44/42
47/45
3
102
71/69
74/71
4
139
79/76
81/78
5
249
149/146
157/155
6
150
89/87
93/92
7
276
147/144
152/151
8
294
177/174
182/179
9
398
231/228
242/239
10
204
95/93
98/96
11
56
33/32
34/33
12
137
83/81
87/86
Filtro
38
Como pode ser observado na Tabela 4, apesar das duas aplicações de heurísticas
reduzirem significativamente o número de transições dos coeficientes, a heurística de
Bellmore e Nemhauser se mostrou mais eficiente para todos os filtros testados. Isto
ocorre porque este algoritmo faz uma busca mais ampla procurando por melhores
vizinhos de dois coeficientes distintos a fim de inserir apenas um. Como também pode
ser observado na Tabela 4 o particionamento dos coeficientes também implicou em uma
redução no número de transições em todos os filtros, porque a busca pela melhor
ordenação ocorre em um específico pequeno grupo de coeficientes. Isto é um importante
problema para a implementação de filtros FIR semi-paralelos, porque estas arquiteturas
podem operar rapidamente (duas amostras processadas por vez) com um reduzido
número de transições entre os coeficientes (provavelmente menor consumo de potência).
6.2
Resultados obtidos através da Codificação
Os resultados obtidos através da codificação dos coeficientes são apresentados
na Tabela 9, onde pode ser observado que o número de transições é reduzido para quase
todos os filtros, após a aplicação da codificação nos coeficientes. Em particular, a
técnica Bus-Invert apresentou os melhores resultados. Na verdade, as codificações Gray
e Hibrido não apresentaram reduções significativas no número de transições dos
coeficientes, devido ao fato destas técnicas serem mais efetivas quando há correlação
entre coeficientes consecutivos. Para o conjunto de coeficientes selecionado, este
aspecto não foi considerado.
Tabela 9. Número de transições dos coeficientes originais e codificados
Coeficientes
Filtro
Originais
Híbrido
Gray
Bus-Invert
1
85
82
82
81
2
67
65
70
64
3
102
122
120
100
4
139
140
145
139
5
249
244
256
246
6
150
135
158
146
7
276
289
279
272
8
294
285
301
276
9
398
403
402
387
10
204
216
202
197
11
56
62
66
51
12
137
147
140
131
39
Foram realizados testes também com a aplicação dos algoritmos heurísticos nos
coeficientes codificados. Os principais resultados são mostrados na Tabela 10, onde em
vários casos podemos notar que houve ainda maior redução do hamming total, com
relação a apenas aplicação dos métodos heurísticos.
Tabela 10. Número de transições dos coeficientes originais e codificados com a aplicação de Heurísticas
Número de transições entre os coeficientes
(distância de Hamming)
Vizinho mais Próximo
Bellmore and
Nemhauser
Filtro
Coeficientes
Ordenação/
Ordenação/
Originais
Particionamento
Particionamento
Híbrido
Gray
Bus-Invert
Híbrido
Gray
Bus-Invert
1
85
50/49
58/56
52/51
56/55
60/58
56/55
2
67
47/45
42/39
42/40
51/49
46/44
44/42
3
102
73/71
74/72
75/74
78/74
74/70
80/76
4
139
85/83
93/91
79/76
90/87
95/91
81/78
5
249
146/143
146/143
162/161
150/148
146/144
158/157
6
150
92/90
98/95
95/93
93/91
102/98
100/99
7
276
150/149
159/158
163/160
155/153
158/153
165/161
8
294
180/177
172/169
191/188
186/182
180/177
198/195
9
398
232/229
244/242
251/248
233/228
248/244
257/252
10
204
99/97
108/106
109/108
101/104
114/112
112/111
11
56
35/34
39/38
38/36
36/35
41/39
41/40
12
137
79/77
88/87
82/80
80/78
90/88
87/86
40
7 TRABALHOS RELACIONADOS
São encontrados na literatura alguns trabalhos relacionados que utilizam heurísticas
ou alguma outra técnica algorítmica para reduzir consumo de potência em arquiteturas
de filtros FIR. Em [3], por exemplo, foi proposta a ordenação dos coeficientes afim de
reduzir o consumo de potência nas arquiteturas de filtros FIR. Porém, esta ordenação
gera apenas soluções ótimas, o que limita o algoritmo à geração da ordenação para um
número limitado de coeficientes. Além disso, a sua utilização se limita a apenas filtros
totalmente seqüenciais.
No algoritmo de ordenação de coeficientes apresentado em [4], foi proposta uma
extensão da idéia apresentada em [3], onde a função de custo que determina a melhor
seqüência de coeficientes continua sendo calculada para todas as combinações dos
coeficientes, mas adiciona o particionamento dos coeficientes, o que possibilita a sua
utilização em filtros semi-paralelos. Este algoritmo, para um filtro FIR de 8ª ordem
usado como exemplo em [4], ainda é razoável, pois encontra a solução ótima de forma
exaustiva. Entretanto, para um maior número de coeficientes este algoritmo não se torna
atrativo devido ao tempo necessário para processar o alto número de combinações.
Em [13], também foi realizada a ordenação dos coeficientes em arquiteturas de
filtros FIR para a redução do consumo de potência, e utilizando técnicas heurísticas.
Porém, o foco do trabalho é mostrar a diferença de ganho em redução de consumo de
potência das implementações DF (forma direta) sobre as implementações TDF (forma
direta transposta), onde é mostrado que, em aplicações TDF consegue-se uma redução
de até 34% de consumo de potência, porém ao custo de um overhead em área de 56%.
Por outro lado, na implementação DF, a redução no consumo de potência alcançou uma
redução de apenas 19% mas sem introduzir nenhum overhead. Entretanto, neste trabalho
não é apresentado especificamente qual tipo de heurística foi utilizada para realizar a
ordenação dos coeficientes, são apenas apresentados os resultados.
Em [19], foi proposto um algoritmo que insere perturbações nos coeficientes, onde
os bits de última ordem tem seu valor alterado para 1, e então, o conjunto de
coeficientes é divido em subconjuntos de tamanho t, e em seguida é feita uma média de
todos os bits da posição k de cada subconjunto de coeficientes que está sendo analisada.
Em seguida, todos os bits da posição k, recebem como valor, a média que é calculada no
algoritmo. Porém nem sempre esta substituição pode ser realizada. Existe uma lista de
restrições que indica o que não pode ocorrer, como por exemplo, um coeficiente
41
simétrico, tem que se manter simétrico durante toda a execução. De acordo com [19],
com a utilização deste algoritmo foi possível obter reduções de até 50% na atividade de
chaveamento dos coeficientes.
42
8
CONCLUSÕES
Neste trabalho foram implementados dois algoritmos baseados em Heurísticas
chamadas Vizinho Mais Próximo e Bellmore e Nemhauser, para a ordenação e
particionamento de filtros do tipo FIR. Os resultados mostraram que os algoritmos
podem encontrar as funções de melhor custo para a ordenação e particionamento dos
coeficientes. Desta forma, a distância de Hamming entre coeficientes consecutivos pode
ser significativamente reduzida. Uma ferramenta foi proposta para que os algoritmos
heurísticos possam ser aplicados de tal forma que a geração da melhor ordenação e do
melhor particionamento dos coeficientes possam ser geradas automaticamente.
A ferramenta automática também está apta a aplicar algumas técnicas de
codificação de coeficientes. Em particular, as codificações Gray, Hibrido e Bus-Invert
foram usadas com o propósito de reduzir o número de transições dos coeficientes. Os
resultados mostraram que a codificação Bus-Invert pode ser eficiente na redução do
número de transições quando comparado com os coeficientes originais. Depois de
aplicar a técnica de codificação seguida do algoritmo baseado em heurística, pode ser
observado que em muitos casos foi possível obter resultados melhores do que com
apenas a aplicação de heurísticas.
Como trabalho futuro, pretende-se fazer a implementação em ASIC
(Application-Specific Integrated Circuit) dos filtros com coeficientes originais e
ordenados (para filtros FIR sequenciais) e particionados (para filtros FIR semiparalelos) a fim de analisar o impacto na redução de potência dos filtros com a redução
do número de transições dos coeficientes. Também se tem por objetivo, a
implementação de outros algoritmos baseados em metaheurísticas.
43
REFERÊNCIAS
[1] M. Mehendale, S. Sherlekar, G. Venkatesh. Low Power Realization of FIR Filters on
Programmable DSP’ s. IEEE Transactions on Very Large Scale Integration (VLSI)
Systems, 6(4):546-553. December 1998.
[2] A. Erdogan and T. Arslan. High Throughput FIR Filter Design for Low Power SOC
Applications. In: 13th Annual IEEE International ASIC/SOC Conference, pp. 21-24.
2000.
[3] M. Mehendale, S. Sherlekar, G. Venkatesh. Techniques for Low Power Realization
of FIR Filters. In: Asia and South Pacific Design Automation Conference, ASPDAC,
1995. Proceedings… New York: ACM, 1995. p.447-450.
[4] E. Costa, J. Monteiro , and S. Bampi. Gray Encoded Arithmetic Operators Applied
to FFT and FIR Dedicated Datapaths. In: 11th IEEE/IFIP International Conference on
Very Large Scale Integration. VLSI-SoC. 2003.
[5] Ansari, Nirwan and Hou, E. Computational Intelligence for Optimization. Kluwer
Academic Publishers, 1997.
[6] Reeves, C.R. Modern Heuristic Techniques for Combinatorial Problems. Blackwell
Scientif Publications, 1993.
[7] M. Stan; W. Burleson. Bus-Invert Coding for Low Power I/O. IEEE Transactions on
Very Large Scale Integration (VLSI) Systems, New York, 1995, P. 49-58.
[8] A. Chandrakasan and R. Brodersen. Low Power Digial CMOS Design. Kluwer
Academic Publishers. 1995.
[9] M. Stan and W. Burleson. Low-Power Encodings for Global Communication in
CMOS VLSI. IEEE Transactions on VLSI Systems. March 1997.
[10] E. Costa, P. Flores, and J. Monteiro. Maximal Sharing of Partial Terms in MCM
under Minimal Signed Digit Representation. In: European Conference on Circuit Theory
and Design. pp. 221-224. 2005.
[11] E. Costa, L. Carro, S. Bampi. Avaliação de Potência em Circuitos CMOS Digitais.
Trabalho Individual de Pesquisa (Doutorado em Ciência da Computação), UFRGS.
1999.
[12] A. Dickson, S. Denker. Adiabatic Dynamic Logic. IEEE Journal of Solid-State
Circuits, p. 311 – 315. 1995.
[13] A. T. Erdogan, T. Arslan. Low Power FIR Filter Implementations Based on
44
Coefficient Ordering Algorithm. IEEE Transactions on Very Large Scale Integration
(VLSI) Systems. 2004.
[14] Glover, F., Laguna, M. & Taillard, E. Tabu Search. Annals of Operations Research,
v.41, J.C.Baltzer,1993
[15] Glover, F. and Kochenberger, G. Iterated Local Search. In: Handbook of
Metaheuristics. Kluwer Academic Publishers, 2003
[16] Ribeiro, C.C. Metaheuristics and Applications. Advanced School on Artificial
Intelligence. Estoril, Portugal, 1996
[17] Nascimento, M.C.V. Uma heurística GRASP para o problema de dimensionamento
de lotes com múltiplas plantas, Dissertação de Mestrado, 2007.
[18] Resende, M. & Ribeiro, C. Greedy randomized adaptive search procedures
(GRASP). In: Handbook of Metaheuristics [edited by F. Glover and G. Kochenberger],
Kluwer Academic Publishers, 219-249, 2002
[19] Kasturi, N. Power Reducing Algorithms in FIR Filters (Dissertação de mestrado,
MIT), 1997.
[20] Pacheco, M. A. C. Algoritmos Genéticos: princípios e aplicações, PUC-RJ (Notas
de aula), 2008.
45