Programação Concorrente; mais especificamente, paralelização de algoritmos para aceleração do seu desempenho através do uso de várias CPUs ou núcleos de processamento. No artigo, focamos na conhecida técnica de “divisão e conquista”.
Para que serve:
Na nova ordem da tecnologia de CPUs, o único jeito de tornar seu código mais rápido é aumentar seu grau de concorrência. Para aplicações que executam um grande número de unidades de trabalho (transações, requests etc.) independentes, cada uma delas relativamente simples, o paralelismo é em boa parte proporcionado pela plataforma (por exemplo, servidor de aplicações Java EE). Mesmo nestas aplicações, a vida nem sempre é tão simples – ver quadro “O Paralelismo resolve tudo?”. Já em sistemas que possuem tarefas individuais pesadas, não resta outra saída senão botar a mão na massa dos threads e concorrência... o que, no caso geral, é difícil e trabalhoso.
Mas há uma categoria de problemas que pode ser tratada por uma técnica relativamente simples de paralelização; principalmente se, como é o caso da plataforma Java, tivermos e conhecermos algumas APIs e estratégias especializadas.
Em que situação o tema é útil:
A grande aplicação é para problemas que envolvem o processamento de um grande volume de dados de entrada; mais especificamente, dados de natureza razoavelmente “homogênea” (como grandes arrays ou matrizes de valores do mesmo tipo), o que facilita dividi-los em várias partes de forma arbitrária. A técnica da “divisão e conquista” permite acelerar este processamento de forma quase linear com o número de CPUs/cores disponíveis.
Nesta coluna, o leitor veterano poderá se lembrar de vários artigos já publicados sobre paralelismo e concorrência; em geral focados na tecnologia da JVM (“Concorrência e a JVM” – Edição 11) ou em APIs (“Concorrência no Java 5” – Edição 20). Um pouco mais recentemente, a Edição 68 trouxe o artigo “Aplicações Concorrentes em Java” de Ronald Blanc Rocha. Mas achei que já estava na hora de voltar ao assunto, e também de tentar uma abordagem diferente.
O plano dessa vez é partir dos problemas em direção às soluções. Apresentaremos ao leitor alguns problemas clássicos de programação – algoritmos de busca e ordenação. Veremos como acelerá-los através de uma técnica específica (pattern?), a Divisão e Conquista; mostraremos o código necessário, implementado através da API java.util.concurrent. Poderemos assim aprofundar esta técnica, conhecer suas dificuldades e casos especiais, etc. de maneira prática e realista.
Há alguns dias um colega disse: “Temos essa aplicação, assim e assado..., e processa 200 transações por segundo, mas precisamos chegar a 600 transações por segundo.” Brincando (mas nem tanto), comentei: “É muito fácil, use um servidor com 600 cores!”
· As transações usam algum recurso compartilhado, por exemplo caches, dados de configuração, ou canais de output (até algo tão simples quanto um objeto Logger);
· Transações fazem lock de registros compartilhados num SGBD, forçando outras transações que também precisam do mesmo lock a esperar na fila;
· Mesmo sem nenhum lock, o SGBD não consegue executar mais que certo número de transações por segundo, pois o paralelismo de I/O de disco é limitado (se bem que isso tende a melhorar, com a tecnologia de SSD substituindo discos).
Por outro lado, minha sugestão, ainda que fosse viável, não seria garantia de solução. Estes problemas quase sempre aparecem quando a concorrência ultrapassa determinado limite. Então não adianta jogar mais CPUs no servidor, que não teremos melhoria da taxa de transações (ou requests, etc.) por unidade de tempo.
Divisão e Conquista: Alô Mundo
Problema: Localizar o maior valor num array gigante de dados desordenados
Este tipo de problema conduz facilmente à técnica paralela de “divisão-e-conquista”, que pode ser descrita genericamente de forma simples: divida seus dados em duas ou mais partes independentes, processe estas partes em paralelo, e no final unifique os resultados de cada parte. É uma excelente técnica quando esta divisão é possível, ou seja, quando os dados de entrada (ou transações concorrentes etc.) são fáceis de separar em partes independentes.
A técnica de divisão e conquista é recursiva; mas para propósitos de paralelismo, a recursão não é um item essencial.
Podemos imaginar o seguinte algoritmo básico (assumindo 2 CPUs/corespara simplificar):
1. Dividir o array em duas metades, uma por CPU;
2. Localizar o maior elemento de cada metade, em paralelo;
3. Unificar os resultados parciais, determinando o maior valor do array inteiro.
Qual código devemos escrever para implementar esse algoritmo paralelo em Java? Será que o desempenho é realmente superior? Vamos responder a uma questão de cada vez. Para começar, veja na ...
