Titulo: Procura de Códigos Convolucionais Baseado no Critério da Distância de Hamming entre Símbolos

Titulo: Procura de Códigos Convolucionais Baseado no Critério da Distância de Hamming entre Símbolos - Busca Paralela

Nome dos autores: Getúlio A. de Deus Júnior, Jaime Portugheis, Luciano de Oliveira Costa e Hélio José da Silva Júnior.

Unidade Acadêmica onde o trabalho foi desenvolvido: Escola de Engenharia Elétrica e de Computação (EEEC).

E-mail (do autor principal): getulio@eee.ufg.br

Palavras-Chave: Computação Paralela, Códigos Convolucionais, Receptores FFH-CDMA, Capacidade de Canal.

Introdução:

Na maioria das vezes, a busca por sistemas paralelos se dá pela necessidade de se ter sistemas que suportem uma alta demanda de processamento, mantido um desempenho satisfatório na maior parte do tempo. Os sistemas paralelos podem atender necessidades de processamento diferenciadas, bem como processar várias tarefas independentes, sendo a quantidade de tarefas processadas uma medida de desempenho do sistema, ou podem dedicar-se a processar uma única tarefa distribuída entre os vários processadores, que em síntese é a definição de processamento paralelo [1].

Este artigo propõe a busca de códigos convolucionais utilizando sistemas paralelos, visto que o esforço computacional para tal tarefa pode ser muito alto.

Material e Método (Metodologia):

Agrupamento de Computadores: Existem diversas aplicações típicas de mainframes adequadas a rodar em máquinas mais fracamente acopladas do que em máquinas com acesso não uniforme à memória. A maioria dessas aplicações deve ter o maior grau de disponibilidade possível, requerendo, portanto, algum mecanismo para implementação de tolerância de falhas. Tais aplicações, somadas à similaridade que os nós de um sistema multiprocessador apresentam com os computadores de mesa e à emergência das redes locais comutadas com largura de faixa alta, sugerem que futuramente as máquinas para processamento pesado utilizarão agrupamento (do inglês: cluster) de máquinas individuas. Um agrupamento, nada mais é que a utilização de dois ou mais computadores em conjunto para uma determinada finalidade [2].

Tipos de Agrupamentos: Basicamente duas categorias de agrupamento: os de alta

disponibilidade (do inglês: High Availability (HA)) e os de alto desempenho de computação (do inglês: High Peformance Computing (HPC)). O agrupamento de alta

disponibilidade tem por finalidade manter um determinado serviço de forma segura o maior tempo possível. Para cumprir com o objetivo, agrupamento de computadores utilizam equipamentos agregados de forma conjunta. O agrupamento de alto desempenho de computação visa fornecer um alto desempenho de processamento, sendo uma alternativa a supercomputadores comerciais de alto custo [2].

Vantagens da utilização de agrupamentos: Dentre as inúmeras vantagens em se utilizar agrupamento de computadores, pode-se destacar: alto desempenho; escalabilidade; tolerância a falhas; baixo custo; independência de fornecedores [2].

Desvantagens da utilização de agrupamentos: Uma das desvantagens do agrupamento é o fato de o custo de administração de um sistema composto por N máquinas ser equivalente ao da administração de N máquinas independentes. Outra desvantagem dos agrupamentos é o fato de eles serem em geral conectados usando-se o barramento de entrada/saída de um computador, enquanto os multiprocessadores são ligados ao barramento de memória. Uma última fragilidade dos agrupamentos é a divisão da memória [1].

Resultados e Discussão:

Agrupamento de Computadores Construído: Foram utilizados cinco computadores pessoais com processadores Duron, com memória principal de 128Mb. Foram criadas duas partições no disco rígido, uma de 1,5 GB, usando sistema de arquivo ext3 para instalação do sistema operacional, outra de 300Mb para utilização como área de troca (do inglês: swap). A máquina designada como nó principal recebeu o nome de homer, e as demais máquinas: marge, bart, lisa e maggie. O sistema operacional Linux, em sua distribuição Slackware, versão 9.1, foi instalado em todas as Máquinas [3]. Os pacotes escolhidos foram apenas os necessários para funcionamento do sistema em rede, principais ferramentas e bibliotecas. A interface gráfica foi instalada juntamente com o compilador apropriado. Os serviços de rede SSH (do inglês: Secure Shell) e NFS (do inglês: Network File System) foram configurados. Os computadores foram conectados por rede Ethernet e protocolo TCP/IP. O conjunto de bibliotecas utilizado para passagem de mensagens foi o MPICH (do inglês: Message-Passing Interface Chamaleon) [4]. A linguagem de programação utilizada para implementar o programa paralelo foi o C/C++.

Algoritmo Paralelizado para a Busca dos Códigos k'/5: A metodologia utilizada para a paralelização reflete diretamente no número máximo de conexões procuradas na última camada do algoritmo original (versão serial) [5, 7]. A função Procura_CC() precisou sofrer uma modificação para possibilitar tal distribuição [6]. Esta modificação consiste basicamente na criação de dois parâmetros de entrada para a função, que determinam os valores iniciais e finais para a nova faixa de busca que cada nó do agrupamento irá buscar. Assim, para que a nova faixa de busca do algoritmo partisse do parâmetro correspondente ao valor inicial até o parâmetro correspondente ao valor final. Uma outra modificação, porém de menor importância, foi a possibilidade da função Procura_CC(limite_inf, limite_sup) retornar o número de vizinhos encontrados em sua busca [6].

Resultados Obtidos: A métrica escolhida para realizar a comparação entre a busca

serializada e a busca paralelizada foi o tempo de execução das aplicações, considerando os mesmos equipamentos [6]. A busca serializada foi realizada em uma das máquinas do agrupamento (nó principal). Para a classe de códigos convolucionais de taxa k'/5, apenas os códigos com taxa 4/5 foram considerados neste trabalho, pois o tempo de execução para a busca de códigos com taxas 2/5 e 3/5 foram respectivamente, 3 e 12 minutos, não justificando o uso de sistemas paralelos. Após a execução das aplicações, primeiramente a serializada e depois a paralelizada, obtivemos o tempo de execução de cada aplicação, conforme mostrado na tabela I. O tempo de execução de cada implementação foi obtido através do comando time do Linux.

Tabela I: Tempo de execução obtidos para cada aplicação na busca do codificador convolucional (5, 4, 2).

Aplicação	Tempo de execução
Serializada	19:19'56''866 milésimos
Paralela	5:15'28''709 milésimos

Os códigos convolucionais encontrados pelos nós marge, bart, lisa e maggie, respectivamente, foram 540:1661:7322:2224:6350, 544:1660:7321:2222:6351, 550:1660:7321:2222:6346 e 554:1660:7321:2222:6344, com d_Hamm = 3 (critério principal do algoritmo de busca). A soma do número de códigos procurados pelos nós é igual ao número de códigos procurados pela aplicação serializada (1.048.576 códigos). A soma do número de códigos válidos encontrados pelos nós é igual ao número de códigos válidos encontrados pela aplicação serializada (923.521 códigos). Para um tamanho de bloco igual a 5 seções de treliça, o número de vizinhos para os códigos convolucionais encontrados por todos os nós foram 128 vizinhos. [6]. Entretanto, para um tamanho de bloco igual a 50 seções de treliça, o número de vizinhos para os códigos convolucionais encontrados pelos nós marge, bart, lisa e maggie, respectivamente, foram 5.754, 5.024, 7.444 e 4.954 vizinhos (melhor código, coincidente com o algoritmo serial).

Conclusão:

Seja o índice temporal µ, dado por µ = t_p/t_s, onde t_p é o tempo, em segundos, gasto pela execução paralela e t_s é o tempo gasto pela execução serial. Ao final deste trabalho pôde-se perceber bem as vantagens de se utilizar sistemas paralelos para busca de códigos convolucionais, visto que, para percorrer todas as conexões na última camada de um codificador de taxa k'/5, utilizando sistemas paralelos, obtivemos um índice temporal µ = 0,272 em relação ao sistema serial.

Referências Bibliográficas:

[1] D. A. Patterson e J. L. Hennessy. Organização e Projeto de Computadores. LTC, Rio de Janeiro, Brasil, 2000.

[2] M. J. Pitanga Alves. Construindo Supercomputadores com Linux. BRASPORT, Rio de Janeiro, Brasil, 2002.

[3] Slackware versão 9.1: http://www.slackware.com/.

[4] Message Passing Interface Chamaleon: http://www-unix.mcs.anl.gov/mpi/mpich/.

[5] G. A. de Deus Júnior, Sistemas FFH-CDMA Codificados, Tese de Doutoramento, Universidade Estadual de Campinas, 2002.

[6] H. J. da Silva Júnior e L. de O. Costa, Busca de Códigos Convolucionais Utilizando Computação Paralela, Projeto Final de Curso, Universidade Federal de Goiás, 2003.

[7] G. A. de Deus Júnior e J. Portugheis. Procura de Códigos Convolucionais Baseado no Critério da Distância de Hamming entre Símbolos - Busca Serial. XXI Simpósio Brasileiro de Telecomunicações, CD-ROM, 06-10 de Setembro, Belém-PA.

Fonte de financiamento: não houve.