IMPLEMENTAÇÃO DISTRIBUÍDA DE BANCOS DE FILTROS FIR UTILIZANDO MPI Tadeu N. Ferreira, Eng., Paulo S. R. Diniz, Ph.D., Felipe M. G. França, Ph.D. COPPE / Universidade Federal do Rio de Janeiro Cidade Universitária – Ilha do Fundão Cx. P. 68504, 21.945-970 – Rio de Janeiro, RJ e-mail:
[email protected] Palavras-chave: filtros digitais, algoritmos distribuídos, convolução, MPI. O uso de algoritmos distribuídos na implementação de sistemas digitais tem como principal objetivo obter ganhos na performance do sistema em relação às implementações tradicionais. Neste artigo são descritas implementações distribuídas de bancos de filtros FIR, focando-se a análise em ganhos de tempo e em número de operações proporcionado pelo paralelismo do sistema. Os bancos de filtros utilizados são projetados usando-se algoritmos de convolução aperiódica. O sistema foi desenvolvido com aplicativos gratuitos e em plataformas genéricas (PCs) garantindo o baixo custo financeiro da implementação. Keywords: digital filters, distributed algorithms, convolution, MPI. Using distributed algorithms in order to implement digital systems aims to improve the overall performance of the system, when compared to the traditional implementations. Distributed implementations of FIR filter banks are described in this paper, focusing on the improvement in speed and computation rate due to the parallelism of the system. All the filter banks were designed using aperiodic convolution algorithms. The system was developed using free software and generic platforms (PCs) lowering the financial cost of the implementation.
1. INTRODUÇÃO A filtragem digital de sinais é uma operação básica da área de processamento de sinais, sendo muito útil num conjunto vasto de aplicações, incluindo sistemas de comunicações e processamento de áudio e imagem. Sistemas multitaxas são aqueles em que diferentes taxas de amostragem convivem no mesmo sistema. Manipulações adequadas das operações de decimação (diminuição da taxa de amostragem) e de interpolação (aumento da taxa de amostragem), em conjunto com o uso de banco de filtros, permitem que haja uma economia de operações, quando comparado a formas tradicionais de filtragem. A idéia central de um banco de filtros é a de dividir o filtro em sub-bandas de maneira a possibilitar um processamento independente de cada sub-banda, isto pode ser verificado na figura 1 [DINIZ,2002].
Essa independência entre as sub-bandas traz consigo a possibilidade de se processar as bandas em paralelo, permitindo um ganho ainda maior de desempenho do sistema. 2. ALGORITMOS DE CONVOLUÇÃO APERIÓDICA Algoritmos de convolução aperiódica (ACA) são basicamente manipulações inteligentes de produtos de polinômios, aproveitando-se que a transformada Z de um sinal de tamanho infinito pode ser vista como um polinômio [VETTERLI,1988]. O uso de ACAs na síntese de bancos de filtros, conforme visto em [VETTERLI,1988], representa uma economia adicional no número de operações realizadas e permite uma paralelização total no processamento das sub-bandas. Ao se utilizar este algoritmo, um filtro de tamanho N pode ser dividido em três sub-bandas de tamanho N/2. Isto pode ser verificado a partir da Figura 2. As sub-bandas geradas H0(z) e H1(z) guardam as seguintes relações com a função de transferência original H(z):
H 0 (z 2 ) = Figura 1: Esquema geral de um banco de filtros.
1 2
[H ( z) + H (− z )]
(1)
H 1 ( z 2 ) = 12 z[H ( z ) − H (− z )]
(2)
Figura 2: Banco de Filtros gerado por ACA.
Numa abordagem tradicional, a filtragem de uma seqüência de tamanho N por um filtro de tamanho L resulta em NL multiplicações complexas. Ao se utilizar o ACA, em cada sub-banda há 0,25NL multiplicações complexas, ou seja,um total de 0,75NL multiplicações complexas. A presença de bancos de filtros de síntese e análise, entretanto, geram uma carga extra de implementação. Com isso, não há uma garantia de que, mesmo o sistema sendo implementado de maneira paralela, haja um ganho em sua performance. Nota-se ainda que, para cada sub-banda gerada, pode-se aplicar novamente o algoritmo de convolução aperiódica. Com isso, aplicando-se recursivamente este algoritmo pode-se subdividir a função de transferência original em tantos blocos quanto se queira. 3. MODELAGEM DE DISTRIBUIÇÃO E COMPARTILHAMENTO DE RECURSOS
direção a este nó, então este está utilizando o recurso. Quando o nó finaliza a utilização do recurso, todas as arestas ligadas a ele têm a orientação revertida. A figura 3 mostra o funcionamento do mecanismo do SER. A cada instante o nó mais escuro é o que está utilizando o recurso. No sistema descrito neste artigo, cada nó representa efetivamente um processo e o recurso a ser compartilhado é a capacidade de processamento. 4. IMPLEMENTAÇÃO O sistema foi projetado visando o funcionamento em um conjunto de PCs conectados numa rede local Ethernet 10 Mbps. A implementação foi feita utilizando-se a linguagem C++, o padrão de troca de mensagens MPI para computação distribuída e o sistema operacional Linux. A utilização de bibliotecas de trocas de mensagens LAM/MPI, que implementam o padrão MPI, permitiu que todo o mecanismo de comunicação de dados entre os computadores fosse realizado em alto nível, através de chamadas de rotinas em C++. Este mecanismo de comunicações é implementado dentro da biblioteca LAM/MPI fazendo uso da pilha de protocolos TCP/IP. Numa das tentativas de se obter maiores ganhos no desempenho do sistema, tentou-se substituir as rotinas do LAM/MPI por uma implementação baseada em sockets TCP. Este novo sistema, no entanto, revelou-se, de duas a três ordens de grandeza mais lento que seu equivalente com MPI.
Uma modelagem muito usada na área de computação distribuída para o compartilhamento de recursos é o algoritmo de Escalonamento por Reversão de Arestas (SER), descrito em [BARBOSA,1996]. Apesar de não se utilizar estritamente o algoritmo SER na execução do sistema, utiliza-se as notações próprias deste algoritmo na modelagem dos recursos distribuídos. Na modelagem do SER, o sistema distribuído é representado por um grafo orientado. Cada nó do grafo representa uma parte do sistema computacionalmente independente das demais. Em termos de implementação, cada nó normalmente é mapeado como um processo. Os ramos (ou arestas) no grafo representam compartilhamento de recursos, ou seja, cada par de nós ligado por um ramo está compartilhando um determinado recurso. O compartilhamento de recursos é definido de modo bem simples. Quando todos os ramos ligados a um determinado nó estão orientados em
Figura 3: Funcionamento do Escalonamento por Reversão de Arestas.
Foi implementado o ACA, seguindo o explicado na seção 2, no qual o sistema subdivide uma função de transferência em três funções menores. Além disso, foi implementada também uma versão recursiva do ACA. Ou seja, é aplicado o algoritmo de convolução aperiódica em cada sub-banda, gerando-se então bancos de filtros com 3N bandas. Em particular, as medições de desempenho se concentraram em bancos de filtros com 3, 9 e 27 sub-bandas.
pois também transforma a operação de filtragem em um conjunto de operações de menor tamanho que podem ser realizadas em paralelo. O algoritmo clássico Overlap-and-Add realiza convoluções utilizando a FFT (Fast Fourier Transform). A fim de que o ganho representado pelo uso do domínio da freqüência não influenciasse na análise de desempenho do sistema, o algoritmo foi modificado a fim de que as convoluções fossem realizadas no domínio do tempo.
A modelagem de compartilhamento de recursos do sistema com 3 bandas pode ser vista na figura 4. O nó zero calcula as funções de transferência de cada subbanda e envia os valores encontrados para os nós 1, 2 e 3. Além disso, a seqüência de entrada também é transmitida do nó zero para os nós da camada intermediária. Os nós 1, 2 e 3 fazem efetivamente o processamento em paralelo, sendo responsáveis por cada braço do banco de filtros da figura 2, o resultado da filtragem em cada nó intermediário é então enviado para o nó quatro que totaliza as respostas na saída do sistema.
Cada versão do algoritmo foi comparada com uma rotina de convolução tradicional. Esta rotina foi otimizada, sendo mais rápida que seu equivalente builtin do aplicativo Matlab, quando usado para seqüências de entrada e de filtro de comprimento até 512.
No caso de bancos de filtros com mais sub-bandas, ou seja, quando um ACA é aplicado recursivamente, novas camadas de nós aparecem entre o nó de entrada e os nós da camada intermediária e entre os nós da camada intermediária e o nó de saída.
Os algoritmos foram implementados tanto de modo seqüencial quanto distribuído, a fim de se verificar o quanto do ganho de performance se deve ao fato de as operações serem realizadas em paralelo. 5. RESULTADOS Foram realizadas medidas de tempo de execução de filtragens feitas com o ACA e com Overlap-and-Add para seqüências de entrada de diversos tamanhos. Variou-se também o número de amostras da resposta ao impulso do filtro em questão. A fim de que se limitasse o número de medidas, durante as medições, usou-se o número de amostras da resposta ao impulso do filtro original sempre igual ao tamanho da seqüência de entrada. Os algoritmos distribuídos foram executados em redes de dois e de quatro processadores. A alocação dos nós nos processadores era decidida pelo próprio daemon MPI. Posteriormente, foi estudado e implementado um algoritmo de alocação de nós a processadores de maneira ótima. 5.1 Primeiras Medições
Figura 4: Modelagem do compartilhamento de recursos para bancos de filtros com três sub-bandas.
A presença dos bancos de filtros de análise e síntese tende a aumentar o número de operações do sistema, o que pode, em muitas situações tornar a implementação distribuída menos eficiente que uma simples convolução. Foi então implementada, para fins de comparação, uma versão ligeiramente modificada do algoritmo Overlap-and-Add, cuja descrição pode ser vista em [DINIZ,2002]. Este algoritmo foi escolhido,
As tabelas 1 e 2 mostram de maneira resumida os resultados da primeira medição. Na tabela 1, comparase diretamente o banco de filtros gerado ACA com a convolução tradicional, enquanto na tabela 2 está se comparando o algoritmo Overlap-And-Add com a convolução. Cada número nas tabelas representa em quantas “medidas” o algoritmo em questão revelou-se mais rápido.
Tabela 1-2:Comparação dos algoritmos distribuídos com a convolução na implementação original.
Banco de Filtros é mais rápido 2
Convolução tradicional é mais rápida 37
Overlap-and-Add é mais rápido 10
Convolução tradicional é mais rápida 29
Cada “medida” na verdade é a média de dez medidas tomadas independentemente, com o objetivo de diminuir a incerteza nos dados. Além disso, cada medida corresponde a um tamanho diferente para a seqüência de entrada e uma versão diferente do algoritmo em questão (ou seja, no caso do banco de filtros, um número diferente de sub-bandas e, no caso do Overlap-and-Add,de um número diferente de subseqüências). Pelas tabelas 1 e 2 percebe-se que os resultados foram decepcionantes, principalmente em relação ao banco de filtros. As implementações distribuídas tiveram um desempenho bem abaixo do esperado. A fim de se verificar qual a etapa do processo que demandava mais tempo, foram feitas medições de tempo para diversas etapas do sistema. Além disso, também se verificou que os algoritmos distribuídos apresentaram um desempenho superior em redes com dois computadores do que em redes com quatro computadores. 5.2 Medições das Etapas do Sistema Com o propósito de se verificar qual parte do sistema atrasava a implementação, foram medido os tempos relativos às etapas de processamento nos nós da camada intermediária (aquela onde está o processamento mais pesado, ou seja, nós 1, 2 e 3 da figura 4). As etapas medidas são: • • • • •
Recepção de Dados. Filtro de Análise. Convolução. Filtro de Síntese. Envio de Dados.
As medições foram feitas com os mais variados tamanhos da seqüência de entrada e para diversos tamanhos da resposta ao impulso do filtro. A fim de se simplificar o processo de medições, só foram feitas
medidas para tamanhos da resposta em freqüência iguais aos tamanhos da seqüência de entrada. Para seqüências de entrada de tamanho até 2048 amostras, as etapas mais lentas foram as referentes à recepção e envio de dados. Isto explica o desempenho superior do algoritmo Overlap-and-Add, pois este algoritmo se utiliza de menos nós e menos comunicação de dados que o banco de filtros gerado pelo ACA. Além disso, também se explica porque os algoritmos distribuídos tiveram melhor desempenho em redes com dois computadores, já que nestas redes há uma menor quantidade de informações trafegando na rede local. A fim de se minimizar o problema, foi diminuída a quantidade de tráfego entre os nós do sistema. Para tanto, várias quantidades originalmente transmitidas, como o tamanho das seqüências a serem enviadas, deixaram de ser transmitidas entre os nós e passaram a ser informadas através de parâmetros de funções. Além disso, o tipo das variáveis a serem transmitidas foi mudado de double para float, diminuindo-se pela metade a quantidade de bits enviados. Foram então realizadas novas medições. 5.3 Novas Medições A partir das tabelas 3 e 4, percebe-se que as modificações na implementação do sistema surtiram efeito. O número de medições em que o banco de filtros gerado por ACA e o algoritmo overlap-and-add foram melhores que a convolução tradicional aumentou dentro de um conjunto de medições menor que o original (29 medidas contra 39 originalmente). Lembrando que as medições foram realizadas tanto em redes com 2 computadores quanto em redes com 4 computadores, pode-se separar as medições realizadas de acordo com o tamanho da rede utilizada. Isso está representado nas tabelas 5 e 6. Tabela 3-4: Novas medidas comparando o desempenho dos algoritmos distribuídos com a convolução linear tradicional .
Banco de Filtros é mais rápido 13
Convolução tradicional é mais rápida 16
Overlap-and-Add é mais rápido 16
Convolução tradicional é mais rápida 13
Tabela 5-6: Compara-se o desempenho dos algoritmos distribuídos e da convolução, discriminando-se a rede usada.
Redes
Banco de Filtros é mais rápido 6 2 computadores 8 4 computadores Redes 2 computadores 4 computadores
Overlap-and-Add é mais rápido 7 9
Convolução é mais rápida 9 7 Convolução é mais rápida 7 6
Verifica-se que o sistema desta vez se comporta melhor em sistemas com quatro computadores em rede. Isto se explica pelas soluções encontradas para o problema da transmissão entre os nós, o que diminuiu o peso computacional do maior número de comunicações entre os nós encontrado em redes com mais computadores. Além disso, a vantagem de desempenho que o algoritmo Overlap-and-Add possuía em relação ao banco de filtros diminuiu sensivelmente. Uma análise mais profunda de desempenho leva em conta, além do tamanho da rede utilizada, também o tamanho da seqüência de entrada e da resposta ao impulso do filtro em cada medição. Lembra-se que, a fim de se limitar a quantidade de valores a se medir, foi usado sempre um tamanho para seqüência de entrada igual à resposta ao impulso do filtro. Este estudo está contido nas tabelas 7 e 8. Tabela 7-8: Compara-se os algoritmos distribuídos e a convolução tradicional para diversos tamanhos de seqüência de entrada.
Seqüência de Entrada 64 256 1024 2048 8192
Banco de Filtros é mais rápido 1 1 2 4 6
Convolução é mais rápida 5 5 4 2 0
Seqüência de Entrada 64 256 1024 2048 8192
Overlap-and-Add Convolução é mais é mais rápido rápida 0 6 0 6 4 2 6 0 6 0
Percebe-se que os algoritmos distribuídos apresentam um melhor desempenho quando o tamanho da seqüência de entrada e da resposta ao impulso do filtro aumentam. O algoritmo Overlap-and-Add apresenta-se melhor, aparentemente, que o banco de filtros gerado por ACA para seqüências de maior tamanho. Essa observação é, na verdade, ilusória, pois se está apenas computando o número de medidas em que um e outro algoritmo se mostram melhor para determinados tamanho de seqüência. Na verdade, é muito complicado se fazer uma comparação direta, cada implementação do banco de filtros gerados por ACA e do algoritmo Overlap-andAdd, já que as várias implementações de cada um foram construídas com critérios completamente diferentes. Um tipo de comparação possível é a medição de desempenho de versões do banco de filtros e do Overlap-and-Add que dividissem a seqüência de entrada em seqüências do mesmo tamanho. Com isto, o banco de filtros da figura 2, com três sub-bandas, que divide a seqüência de entrada de tamanho N em três sub-seqüências de tamanho N/2 para serem processadas independentemente, é comparado com o Overlap-andAdd com duas sub-bandas, que divide uma seqüência de entrada de tamanho N em seqüências de tamanho N/2 para serem processados independentemente. O resultado desta comparação pode ser visto na tabela 9. Percebe-se por estes resultados que o algoritmo Overlap-and-Add apresenta melhores resultados com seqüências até 2048. O banco de filtros gerado por ACA é o melhor para seqüências de tamanho 8192. Os bancos de filtros gerados por ACA dividem tanto a seqüência de entrada quanto a resposta ao impulso do filtro antes de convoluí-los. O algoritmo Overlap-andAdd divide apenas a seqüência de entrada (ou apenas a resposta ao impulso do filtro) antes de convoluir. Para uma seqüência de entrada de tamanho N e uma resposta ao impulso de tamanho L, enquanto o banco de filtros da figura 2 faz 3 convoluções de subseqüências de tamanho N/2 e L/2, o algoritmo Overlap-and-Add com duas sub-bandas faz 2 convoluções com seqüências de tamanho N/2 e L. Com isso, é de se esperar que o banco de filtros seja mais rápido para qualquer tamanho de seqüências, mais a presença dos bancos de análise e síntese geram um overhead de operações menor que overhead gerado pela preparação das seqüências antes de serem dividas no Overlap-and-Add.
Tabela 9:Compara-se o desempenho do banco de filtros gerado por ACA e o algoritmo Overlap-and-Add.
Seqüência de Entrada 64 256 1024 2048 8192
Banco de Filtros é mais rápido 2 2 1 1 4
Overlap-and-Add é mais rápida 4 4 5 5 2
Supõe-se então que, para tamanhos de seqüência até 2048, o maior overhead gerado pelo banco de filtros torne este sistema mais lento que o Overlap-and-Add. Para tamanhos maiores que 8192, esse overhead é compensado pelas convoluções serem mais lentas. Isso é confirmado pelas medições de etapas do sistema mostrado na seção 5.2, onde é mostrado que a etapa do sistema mais lenta para seqüências com até 2048 amostras é a transmissão de dados, e que, para seqüências a partir de 8192 amostras, a etapa mais lenta é a convolução. Como no banco de filtros gerado por ACA, o número de nós é maior que no caso do algoritmo Overlap-andAdd, então, para seqüências com até 2048 amostras, onde as etapas mais lentas são as de envio/recepção de dados, os bancos de filtros são logicamente mais lentos. Para seqüências acima de 8192 amostras, como a convolução se torna a etapa mais lenta, os bancos de filtros têm um desempenho melhor que o Overlap-andAdd.
bandas, temos que o custo computacional total (CT) do sistema, com algumas simplificações é o seguinte:
CT = (0,3L2 + 0,7 NL + 0,4 N 2 )C + + (1,1L2 + 2,2 NL + 1,1N 2 )A +
+ (0,4 L2 + 0,7 NL + 0,4 N 2 )I +
(1,8L + 3,7 NL + 1,8N )S + + (1,5L + 3NL + 1,5N )M + (4 N + L )T 2
2
2
2
(3)
Conforme o que foi visto na seção 5.2, a etapa que mais demora para seqüências com até 2048 amostras é a de transmissão de dados. Com isto, a tendência natural é a do custo individual T ser o maior dentre as operações básicas. Como este custo é o único que não contém termo quadrático em relação a N e a L e nem termos NL multiplicando-o, explica-se porque para grandes seqüências, ou seja, acima de 8192 amostras o custo de transmissão não ser o mais alto. Para seqüências menores predomina mais o fato de o custo T ser o mais alto. A medida em que se aumenta N e L, os termos quadráticos dos outros custos passam a predominar, tornando os outros custos maiores que o de transmissão. 7 ALOCAÇÃO DE NÓS A PROCESSADORES
6 ANÁLISE DOS ALGORITMOS
Como já foi visto, o daemon MPI pode controlar automaticamente qual nó será processado por qual computador. No entanto, surge a questão de se saber se haveria uma maneira ótima de alocação de nós a processadores de maneira a otimizar o sistema.
As análises feitas até o momento têm como pano de fundo uma implementação específica. Procura-se, nesta seção, que se coloque mais ênfase no número de instruções e não no tempo de execução dos algoritmos.
Foi desenvolvido então um programa em C++ que define a melhor alocação de nós a processadores, considerando-se uma rede homogênea, ou seja, que todos os processadores tenham a mesma velocidade.
Considerando que deseja-se convoluir uma seqüência de entrada de tamanho N com um filtro FIR com resposta ao impulso de tamanho L. Considerando o custo computacional referente às seguintes operações básicas:
Duas regras principais foram definidas para se fazer esta alocação:
• • • • •
Comparação (C) Atribuição (A) Incremento (I) Soma/Subtração (S) Multiplicação/Divisão (M)
Com isso, considerando o sistema da figura 2, ou seja, um banco de filtros gerado por ACA com três sub-
• •
Nós da mesma camada são alocados a computadores diferentes. Todos os computadores devem se responsabilizar pela mesma quantidade de nós, na medida do possível.
A primeira regra deve-se ao fato de os nós de uma mesma camada realizarem o processamento em paralelo. Quando estes nós são alocados ao mesmo computador, perde-se o caráter paralelo e estes são executados seqüencialmente.
A segunda regra se deve à homogeneidade da rede. Se alguns computadores forem responsáveis por uma quantidade de nós muito maior que os outros, recursos do sistema, que poderiam torna-lo mais rápido são desperdiçados. 8 CONCLUSÕES O elevado custo das transmissões de dados do sistema, que se devem à implementação em software, que cria um sobrecarga de tempo de transmissão gerado pela pilha de protocolos TCP/IP, cria uma série de empecilhos para uma implementação eficiente do banco de filtros gerados por ACA. Recomenda-se então o uso de algoritmos que tornem cada nó da mesma camada computacionalmente mais intensivo, mas que diminua a quantidade de dados transmitidos. O uso da técnica Overlap-and-Add revelou-se extremamente eficiente, principalmente para tamanhos de seqüência de entrada de 256 até 2048 amostras, para redes com quatro processadores. Pode ser testada futuramente sua implementação via banco de filtros como descrito em [NUSSBAUMER,1982], apesar de, neste caso, incluir-se bancos de análise e síntese. A utilização das bibliotecas MPI para C++ facilitaram bastante a implementação, mas limitaram a otimização do sistema justamente nas funções que se revelaram mais críticas, as de envio e recepção de dados. Recomenda-se o desenvolvimento de funções de transmissão e recepção de dados eficientes. As tentativas de se desenvolver estas funções através de TCP sockets revelaram-se desastrosas, como visto na seção 4. 9 BIBLIOGRAFIA [DINIZ,2002] DINIZ, P.S.R, SILVA, E.A.B., LIMA NETTO, S., Digital Signal Processing: System Analysis and Design, Cambridge University, Cambridge, 2002. [VETTERLI,1988] VETTERLI, M., Running FIR and IIR Filtering using Multirate Filter Banks, IEEE Transactions on Acoustics, Speech and Signal Processing, v.36, no 5, pp.730-737, maio, 1988. [BARBOSA,1996] BARBOSA, V.C., An Introduction to Distributed Systems, The MIT Press, Cambridge, 1996.
[NUSSBAUMER,1982] NUSSBAUMER, H.J., Fast Fourier Transform and Convolution Algorithms, Springer-Verlag, New York, 1982.
