otimização e processamento paralelo de alto desempenho

ARTIGO
OTIMIZAÇÃO E PROCESSAMENTO
PARALELO DE ALTO DESEMPENHO
Celso Carneiro Ribeiro e Noemi de la Rocque Rodriguez
INTRODUÇÃO
otimização computacionalmente difíceis com
uma grande aceleração, cuja resolução por
A utilização de métodos quantitativos de
máquinas seqüenciais era praticamente
otimização e de técnicas da pesquisa ope-
inviável. Finalmente, apresenta-se algumas
racional vem se revelando cada vez mais
tendências na área de cluster computing,
como uma ferramenta de grande impor-
que representa a plataforma de hardware
tância na solução de problemas de en-
mais promissora, ilustrando-se ainda outras
Depto. de Informática,
genharia e de planejamento. Tais ferra-
aplicações industriais na área bancária e de
PUC-Rio
mentas encontram aplicação crescente em
serviços de Internet.
Celso Ribeiro e
Noemi Rodriguez
problemas nos setores energético e petrolífero, no projeto e na exploração de redes de
COMUNICAÇÃO ENTRE PROCESSOS
comunicação, em problemas de planejamento e escalonamento da produção, de rotea-
Uma aplicação paralela ou multiproces-
mento de veículos e de gestão de frotas de
sada é formada por um conjunto de pro-
empresas aéreas (composição de frotas,
cessos que cooperam na obtenção de um re-
rodízio de tripulações), entre outras áreas.
sultado. Tipicamente, esses processos preci-
O advento das técnicas e ferramentas de
sam se comunicar para trocar dados e pedi-
programação paralela, portáveis e de fácil
dos entre si. Como cada processo progride de
uso, e a disponibilidade de máquinas
forma independente dos demais, muitas
paralelas, com desempenho e confiabilidade
vezes é necessário definir pontos de sincro-
crescentes e custos cada vez menores, vem
nização entre eles, de forma a garantir a
contribuindo sobremaneira para o sucesso
coerência da computação global.
da aplicação de métodos de otimização como
Nos últimos anos, vários sistemas opera-
uma solução prática, computacionalmente
cionais passaram a oferecer suporte a um
viável. Implementações paralelas são tão
tipo de processos denominados threads, ou
mais eficientes quanto a aceleração que
processos de peso leve, que podem se comu-
proporcionam aproxima-se do número de
nicar através de variáveis globais compar-
processadores utilizados. Neste trabalho,
tilhadas. Do ponto de vista do programador
apresenta-se um rápido panorama das
paralelo, threads são importantes em má-
técnicas de programação paralela. São
quinas com vários processadores, onde eles
apresentadas duas aplicações reais, em que
permitem o desenvolvimento de aplicações
o paralelismo permitiu tratar problemas de
paralelas cujas partes se comunicam por
45
memória compartilhada e, além disso,
ALGUMAS FERRAMENTAS DE PROGRAMAÇÃO
de bibliotecas de programação paralela para
muitas vezes executam de forma mais efici-
PARALELA
este tipo de ambiente [6]. Entre elas, prova-
ente do que processos tradicionais. A comu-
velmente a que obteve a maior divulgação e
nicação por memória compartilhada requer
Um número crescente de ferramentas
difusão de uso foi o PVM (Parallel Virtual
um cuidado grande com o problema de sincro-
(bibliotecas, linguagens) para programação
Machine). PVM foi inicialmente implemen-
nização. Para garantir uma relação de prece-
paralela estão disponíveis para o desenvol-
tada para máquinas Unix que se comunicas-
dência entre comandos de processos distin-
vimento de aplicações paralelas. Duas destas
sem por TCP/IP, aproveitando assim o impul-
tos, o programador deve utilizar comandos
ferramentas, utilizadas recentemente em
so de crescimento da Internet. Atualmente
explícitos de sincronização, que devem ser
projetos desenvolvidos em cooperação com
existem versões para diversos outros siste-
providos pela linguagem ou sistema opera-
duas grandes empresas brasileiras, são
mas. A biblioteca PVM é disponível publica-
cional. Com threads, o mecanismo de sincro-
descritas a seguir.
mente, através da Internet, e amplamente
nização mais freqüentemente oferecido é o de
Em 1995, o IEEE definiu um padrão de
variáveis de condição, que correspondem a
interface de programação com threads,
documentada, em especial através de um
um serviço que permite que um processo
conhecido como Posix threads ou Pthreads
Em 1995, autores e usuários de biblio-
permaneça bloqueado até que uma condição
[5]. Desde então, diversos sistemas operacio-
tecas de troca de mensagens fomaram um
seja verdadeira.
livro [4] também disponível por rede.
nais vêm incluindo suporte a esse padrão,
grupo [7] com o intuito de definir uma inter-
O desenvolvimento de aplicações basea-
também implementado por uma biblioteca
face de programação paralela comum, de mo-
das em variáveis compartilhadas e condições
disponível publicamente [8]. No modelo
do a evitar a proliferação de programas escri-
pode ser bastante complexo. Os bloqueios e
Pthreads, vários threads podem ser definidos
tos em diferentes “dialetos”. Esse grupo en-
sinalizações associados a variáveis de condi-
dentro de um único processo. O processo fun-
volveu aproximadamente 40 pessoas de 60
ção podem estar espalhados por um código
ciona como o espaço de endereços de memória
instituições. O resultado desse esforço foi a
extenso, e qualquer acesso a uma variável
que uma determinada aplicação pode uti-
definição do MPI (Message Passing Interfa-
global pode representar uma necessidade de
lizar. Os diversos threads associados a um
ce) [12], que inclui a definição de interfaces de
sincronização, tornando árdua a tarefa de de-
processo compartilham memória: quando um
um conjunto de rotinas para comunicação por
puração do programa paralelo. Muitos auto-
thread realiza escritas na memória (por
troca de mensagens. Desde a publicação do
res acreditam que a forma alternativa de
exemplo, atribuições a variáveis), outro
MPI, em 1995, diversas implementacões já
comunicação entre processos, por troca de
thread pode ler o resultado. O sistema opera-
foram desenvolvidas, sendo várias delas dis-
mensagens, representa uma base mais
cional gerencia a alocação de processadores
poníveis publicamente [7]. O desenvolvimen-
segura para o desenvolvimento de aplicações
para a execução dos threads como se eles
to dessas várias implementacões totalmente
paralelas.
fossem processos independentes. Em uma
compatíveis com a definição original vem fa-
De qualquer maneira, a troca de mensa-
máquina com múltiplos processadores, dife-
zendo do MPI um padrão ad hoc para biblio-
gens é a forma natural de comunicação entre
rentes threads de uma mesma aplicação
tecas de troca de mensagens. O núcleo do
processos que não compartilham memória
podem ser simultaneamente executados em
MPI é formado por rotinas de comunicação
(por exemplo, entre processos que executam
diferentes CPUs. A interface Pthreads define
entre pares de processos (tipo send e receive).
nos vários nós de um cluster de computado-
basicamente os seguintes grupos de rotinas:
Além desse núcleo, o MPI define várias ou-
res). Em sua forma mais básica, um mecanis-
rotinas de controle, que permitem criar,
tras rotinas, entre as quais se destacam roti-
mo de troca de mensagens fornece uma pri-
eliminar e suspender a execução de threads,
nas de comunicação e sincronização em gru-
mitiva para envio de dados para um processo
rotinas de sincronização, entre as quais as
po. A instalação das bibliotecas das diferentes
específico (send) e de recebimento de dados de
que manipulam as variáveis de condição
versões de MPI costuma ser simples. Embora
um processo específico ou de qualquer pro-
descritas na seção anterior, e rotinas para
exija uma certa intimidade com os conceitos
cesso que tenha enviado alguma mensagem
controle de escalonamento, que permitem
de programação paralela, a programação com
(receive). Muitas abstrações e expansões po-
alterar as prioridades relativas dos diversos
MPI não apresenta maiores dificuldades.
dem ser oferecidas em cima desse modelo bá-
threads de uma aplicação.
APLICAÇÃO NO SETOR PETROLÍFERO
sico. Por exemplo, pode-se citar bibliotecas de
Com o aumento da banda passante ofere-
programação paralela que, além de fornece-
cida pelas redes locais, passou a ser comum o
rem diversas variantes de send e receive,
uso de redes de estações de trabalho como se
A otimização da exploração de reserva-
muitas vezes oferecem mecanismos para co-
fossem máquinas multiprocessadoras. Surgi-
tórios de petróleo requer muitas avaliações
municação e sincronização de grupos [11,12].
ram então desde o final dos anos 80 uma série
de possíveis combinações das variáveis de
46
decisão envolvidas, tais como as proprie-
completamente heterogêneas, formadas por
procedimentos exatos, mas computacio-
dades dos reservatórios, a localização dos
estações de trabalho de pelo menos três
nalmente mais custosos. A metodologia
poços e os parâmetros de escalonamento da
fabricantes diferentes.
desenvolvida foi aplicada a um sistema
produção, de modo a obter a melhor estratégia em termos econômicos. Executar uma
realista de grande porte, formado por parte
APLICAÇÃO NO SETOR ELÉTRICO
simulação para tal número de avaliações
da rede brasileira, definido por 19 agentes (empresas), 79 barras e 283 circuitos.
pode não ser viável em termos práticos,
Problemas de programação linear com
O sistema computacional desenvolvido na
devido aos elevados tempos de computação
um número muito grande de variáveis e res-
linguagem C implementando a metodologia
envolvidos. Uma das ferramentas eficientes
trições aparecem em muitas aplicações em
proposta foi capaz de resolver de forma
desenvolvidas para resolver esta aplicação
diferentes áreas, tais como planejamento e
exata este problema [10], utilizando quase
foi um algoritmo genético híbrido [2], cuja
operação de sistemas de produção e trans-
42 horas de processamento em um compu-
estratégia de otimização integra análise
missão de energia, projeto de redes de teleco-
tador Sun UltraSparc com 256 Mbytes de
econômica, simulação dos reservatórios e
municações, localização e dimensionamento
memória. Embora o tempo de processamen-
otimização do projeto.
de plataformas de petróleo, distribuição de
to seja elevado, isto decorre da dificuldade
Embora tal ferramenta tenha apresen-
produtos, roteamento de veículos, localização
intrínseca do problema, que até então não
tado um ótimo desempenho na prática, en-
de centros de serviços e exploração de
havia sido resolvido numericamente.
contrando soluções economicamente muito
recursos naturais, entre outras.
Em uma segunda fase, procurou-se uti-
boas, os tempos de computação observados
Um problema importante no setor elé-
lizar o processamento paralelo como forma
são extremamente elevados. Isto decorre da
trico, em especial dentro do atual contexto
de aceleração da metodologia proposta. A
necessidade de executar muitas simulações,
econômico, consiste na alocação de custos de
estratégia de paralelização adotada baseia-
uma para cada configuração avaliada. Desta
serviços de transmissão entre os diversos
se em buscas cooperativas paralelas, cada
forma, o paralelismo oferece uma excelente
agentes (empresas) que participam do siste-
uma delas implementando uma heurística
alternativa para este tipo de aplicação, per-
ma elétrico interligado, cada um controlando
diferente para acelerar a geração de restri-
mitindo que diferentes configurações sejam
um certo número de usinas e devendo aten-
ções [1]. No caso desta aplicação, foi utiliza-
avaliadas simultaneamente por diferentes
der uma certa demanda em sua área de res-
da uma máquina paralela Sun Starfire
processadores. Através de um projeto contra-
ponsabilidade. Através de projeto contratado
ENT10000 do CENAPAD MG-GO, dispon-
tado em 1998 pela Gerência de Tecnologia e
em 1997 pelo Laboratório de Análises
do de até 32 processadores UltraSparc de
Simulação de Reservatórios da Petrobras, foi
Técnico-Econômicas de Sistemas de Potência
250 MHz. A implementação paralela em C
desenvolvida uma implementação paralela
do Centro de Pesquisas em Energia Elétrica
utiliza Posix threads, em razão da arqui-
utilizando MPI deste algoritmo genético
(CEPEL), desenvolveu-se e implementou-se
tetura desta máquina ser baseada em me-
híbrido. MPI foi escolhida em função de sua
uma metodologia para resolver este proble-
mória compartilhada (vide seção 2). Os re-
portabilidade e das facilidades que oferece
ma de programação linear com um número
sultados obtidos através do processamento
para programação do controle de falhas nos
exponencial de restrições, baseado em uma
paralelo demonstram claramente a eficácia
processadores atuando de forma concorrente.
formulação através da teoria dos jogos coope-
do emprego de paralelismo na solução desta
Os resultados obtidos foram particular-
rativos [3]. A dificuldade computacional
classe bastante importante de problemas
mente animadores, indicando a aderência do
associada à resolução deste problema decorre
de otimização. A implementação da estraté-
paralelismo como solução para este tipo de
do número extremamente elevado de sub-
gia adotada, usando uma configuração com
problema. Em razão das tarefas paraleliza-
problemas de planejamento da expansão da
apenas um processador mestre e quatro es-
das (a simulação de cada configuração) serem
transmissão que devem ser resolvidos a cada
cravos (dentre os 32 disponíveis), permitiu
completamente independentes e do tempo de
iteração de um procedimento de geração de
reduzir o tempo de processamento para ape-
processamento de cada simulação ser bastan-
restrições, cada um deles constituindo por si
nas 5.4 horas, ou seja, para cerca de apenas
te elevado (da ordem de algumas horas, em
só um problema de programação inteira.
12% do tempo observado originalmente.
certos casos), a estratégia de paralelização
A solução inovadora, proposta na primei-
consegue atingir rendimento máximo, obten-
ra fase deste projeto, consistiu na utilização
do-se acelerações da ordem do número de pro-
de meta-heurísticas de última geração
cessadores utilizados. Deve-se ainda men-
(algoritmos genéticos, busca tabu e GRASP
O desenvolvimento de ferramentas de
cionar a flexibilidade do MPI, já que esta
[9]) para acelerar o procedimento de geração
software portáveis, eficientes e simples de
aplicação vem sendo processada em redes
de restrições, minimizando-se a chamada de
utilizar, associado à disponibilidade de
TENDÊNCIAS
47
REFERÊNCIAS
uma gama de máquinas paralelas com
Outra grande vantagem destes siste-
grande capacidade de processamento e
mas decorre de serem facilmente escaláveis
custos decrescentes, vem tornando o pro-
(adição de novos processadores) e atualizá-
[1] R.M. Aiex, C.C. Ribeiro e M.P. Aragão,
cessamento paralelo uma alternativa viá-
veis (upgrade dos processadores, componen-
“Parallel cut generation for service cost allocation
vel para o desenvolvimento de técnicas
tes, redes e software). Finalmente, clusters
in transmission systems”, III Metaheuristics In-
computacionalmente eficientes para a solu-
oferecem uma importante solução não ape-
ternational Conference, 1-6, Angra dos Reis, 1999.
ção de problemas práticos reais de simu-
nas para aplicações científicas, mas também
[2] A.C. Bittencourt e R.N. Home, “Reservoir
lação, otimização, data mining e processa-
para aplicações comerciais exigindo altas
Development and Design Optimization”, Annual
mento de imagens, entre outras aplicações.
taxas de disponibilidade (por exemplo, ban-
Technical Conference and Exhibition of the
Dentre as atuais tendências em pro-
cos e operadoras de cartões de crédito com
Society of Petroleum Engineering, 545-558,
cessamento paralelo, destaca-se a idéia de
processamento de transações on-line).
San Antonio, 1997.
cluster computing. Basicamente, um cluster é
Neste caso, o sistema pode rapidamente
[3] N. Campodónico e M.V. Pereira, “A metho-
uma coleção de PCs ou estações de trabalho
identificar e isolar um elemento do cluster
dology for transmission service cost allocation in
conectados por uma rede, montados com
que entre em pane, transferindo as tarefas
the core of cooperative games”, Relatório técnico,
componentes comerciais padrão. Os super-
por ele desempenhadas para outro pro-
Power Systems Research Inc., Rio de Janeiro, 1996.
computadores até recentemente oferecidos
cessador. Provedores de serviços livres de
[4] A. Geist, A. Beguelin, J. Dongarra, W. Jiang,
como a principal alternativa para o proces-
correio eletrônico (e.g. hotmail) e mecanis-
R. Manchek e V. Sunderman, “PVM: Parallel
samento paralelo de alto desempenho (tais
mos de busca na Internet (e.g. hotbot) são
Virtual Machine - A User's Guide and Tutorial for
como computadores Cray ou Connection
motorizados por clusters, de modo a prover
Networked Parallel Computing”, The MIT
Machine) apresentavam preços muito ele-
altas taxas de acesso simultâneo a um
Press, 1994. (disponível através do WWW em
vados (na casa de alguns milhões de
grande número de usuários.
http://www.netlib.org/pvm3/book/pvmbook.html)
dólares) e taxas de obsolescência extrema-
O Laboratório de Paralelismo da PUC-Rio
[5] Institute of Electric and Electronic Engi-
mente altas, agravadas pelo rápido desa-
conta atualmente com um cluster formado
neering, “Information Technology - Portable
parecimento do mercado de alguns fabri-
por 32 processadores Pentium II 400 MHz
Operating Systems Interface (POSIX) - Part 1 -
cantes. O significativo aumento do desem-
IBM PC 300GL, cada um com unidade de
Amendment 2: Threads Extension”, 1995.
penho e da confiabilidade de PCs, redes e
disco própria, conectados por uma rede
[6] S. Martins, C.C. Ribeiro e N.R. Rodriguez,
estações de trabalho viabilizou o uso de
Ethernet através de um switch IBM 8274
“Ferramentas para programação paralela em
clusters como uma alternativa de baixo
modelo W93 na placa ESM-C-32W que
ambientes de memória distribuída”, Investi-
custo para processamento paralelo em apli-
permite 32 segmentos a 10 Mbps, fun-
gación Operativa 5 (1996), 67-98.
cações que exigem recursos computacionais
cionando sob o sistema operacional Linux.
[7] MPI Forum, http://www.unix.mcs.anl.gov/mpi/
de forma intensiva.
Este cluster entrou em operação recente-
[8] C. Provenzano, “Pthreads”,
Clusters podem ser montados rapida-
mente e foi um importante aporte para
http://www.mit.edu:8001/people/proven/pthreads
mente, utilizando versões de domínio públi-
nossas instalações e capacidade de desen-
[9] C.R. Reeves, “Modern heuristic techniques
co de Linux como sistema operacional; redes
volvimento de pesquisas e projetos. Entre os
for combinatorial problems”, Blackwell, 1993.
Ethernet, SCI ou Myrinet; e ambientes po-
projetos atualmente em desenvolvimento
[10] C.C. Ribeiro, M.P. Aragão, A.I. Tavares,
pulares de software como PVM ou MPI.
neste cluster, deve-se citar a cooperação
R.M. Aiex e E.U. Barbosa, “Projeto LABTEC:
Alguns sistemas baseados em clusters en-
estabelecida com os laboratórios de pes-
Alocação de custos de serviços de transmissão”,
contram-se entre as máquinas apresentan-
quisa da AT&T nos Estados Unidos, visan-
Relatório técnico, Departamento de Informática,
do melhores índices de custo/desempenho.
do o desenvolvimento de uma metodologia
PUC-Rio, Rio de Janeiro, 1997.
Recentemente foi noticiada a montagem de
para solução de um problema de projeto de
[11] V. Sunderam, “A framework for parallel
um cluster formado por 1000 computadores
redes de acesso a serviços de telecomuni-
distributed computing”, Concurrency: Practice
Pentium II 350 MHz padrão e um compu-
cações. O objetivo consiste em desenvolver
and Experience 2 (1990), 315-339.
tador hospedeiro. O laboratório Sandia dis-
um software de otimização que permita
[12] D. Walker, “The design of a standard
ponibilizou em agosto de 1999 um cluster
balancear o lucro potencial que pode ser
message passing interface for distributed
com cerca de 1400 processadores Compaq
obtido provendo-se acesso a um novo
memory
Alpha que atinge 1.1 TFlop/s de desem-
serviço a determinados grupos de usuá-
Computing 20 (1994), 657-673.
penho de pico, que o coloca entre os 10 siste-
rios, em relação ao custo de construir a
mas mais rápidos atualmente disponíveis.
rede que permita oferecer tais serviços.
48
concurrent
computers”,
Parallel