Problemas Agradavelmente Paralelos

Publicado em 2013-09-25 23:09 por JP Negri

Problemas agradavelmente paralelos são aqueles que podem ser resolvidos através de sua divisão em partes pequenas e cada parte ser resolvida sem nenhuma (ou pouca) coordenação entre os executores. São também chamados de problemas embaraçosamente paralelos, dado ser vergonhoso não executar tarefas assim em múltiplos threads, dado a existência de recursos para tal. O .Net Framework, via Task Parallel Library, facilita muito esse tipo de trabalho; aqui mostro uma classe para facilitar ainda mais o uso, experiências interessantes com escalabilidade em função do número de CPUs, e faço um apelo.

Dois exemplos de problemas agradavelmente paralelos são:

• Cálculo do Risco de Mercado através de Simulação Monte Carlo: É o contexto em que este artigo foi escrito, posto ser um dos métodos de VaR que nosso RiskSystem utiliza. Consiste em apreçar um portfolio milhares de vezes, cada vez com um cenário de mercado (conjunto de preços) diferente e, dos milhares de resultados finais, inferir estatísticas interessantes tais como VaR e Short Fall. Cada apreçamento pode ser realizado de modo independente dos demais, e só após todos serem realizados é que as estatísticas são computadas.

• Obtenção de Senhas a partir do Hash delas: Nenhum sistema decente deve armazenar as senhas dos usuários, nem mesmo criptografadas; e sim armazenar um hash criptográfico que não seja trivialmente calculável. Mas ainda assim, no evento de um sistema ser hackeado, o atacante pode tentar adivinhar as senhas computando o hash criptográfico para milhões de possíveis senhas gerando uma Rainbow Table. Cada cálculo do hash a partir de uma possível senha pode ser executado de modo independente dos demais cálculos. É por isso que nós, designers de sistemas, devemos usar um Salt único para cada senha, e devemos iterar o algoritmo de hash algumas milhares de vezes (Bcrypt, scrypt, PBKDF2 etc): para aumentar o custo do ataque. E é por isso que nós, usuários, não devemos usar a mesma senha em mais de um site. Infelizmente há mais sistemas indecentes do quê seria esperado.

O Loop Paralelo

Um dos algoritmos mais simples e fáceis de usar é o Loop Paralelo, suportado nativamente, ou via bibliotecas, na maior parte das linguagens interessantes.

Um loop tão simples quanto

for (int i = 0; i < passwordCandidates.Length; ++i)
{
	hashs[i] = ComputeHash(passwordCandidates[i]);
}

Parallel.For(0, passwordCandidates.Length,
	i => hashs[i] = ComputeHash(passwordCandidates[i]));

Usando-se algum dos overloads do método pode-se atender a cenários mais sofisticados, incluindo o cancelamento da execução, a execução de tarefas em todo ínicio (ou fim) de thread, o uso de um TaskScheduler personalizado e definições do grau de paralelismo. A implementação da Microsoft é longe de trivial e usa execução adaptativa para definir o quando cada Thread irá executar de modo que a carga seja distribuída e termine de modo bastante uniforme, evitando que uma CPU fique vazia antes de outra.

A documentação na MSDN é excelente, e eu não faria melhor.

Mas um cenário não contemplado é um meio de, enquanto o loop paralelo executa, obter atualizações regulares do andamento, seja para dar algum feedback ao usuário final do sistema, seja para estimar o momento de termino. E é uma classe que faz isso que apresento neste artigo.

Notificações Regulares

int batchSize = passwordCandidates.Length/10;
int index = 0;
while (index < passwordCandidates.Length)
{
	int initial = index;
	int final = Math.Min(initial + batchSize, 
						 passwordCandidates.Length);

	Parallel.For(initial, final,
		i => hashs[i] = ComputeHash(passwordCandidates[i]));

	index = final;
	Console.WriteLine("Feitos {0}...", index);
}

Neste caso haverão notificações a cada décimo da tarefa total feita. E, se a tarefa total não tomar muito tempo, se todas as CPUs puderem dedicar seu tempo à tarefa, e se as tarefas forem todas de mesma complexidade, então as notificações serão fornecidas a intervalos regulares de tempo. Mas e se todas essas condições não forem atendidas? Eventualmente nosso usuário pode ficar um bom tempo sem saber o que ocorre, ou ainda ter estimativas de término bastante incorretas.

O quê queremos é um meio de ter notificações em intervalos regulares, ou tão regulares quanto possível. A solução é não fixar o tamanho de cada lote, iniciando com um tamanho pequeno, medindo a performance e então ir ajustando o tamanho dos lotes de modo a ter medidas em tempos regulares.

A classe LongParallelWork, em nosso GitHub, implementa essa idéia, e acrescenta suporte a configurar o paralelismo e receber notificações (opcionais) de progresso e notificações gerais do algoritmo.

O uso é tão simples quanto:

LongParallelWork.WorkResult workDone = LongParallelWork.DoWork(
	i => PiCalculation.GetPi(piDigits), 
	numberOfRepetitions, parallelFactor, 
	batchTime, initialBatchSize,
	(workDone, timeTaken) =>
	{
		Console.WriteLine("Feito {1:N0} em {2:N1}s...", 
			workDone, timeTaken.TotalSeconds);
		if (Console.KeyAvailable)
		{
			ConsoleKeyInfo ck = Console.ReadKey(true);
			return ck.Key != ConsoleKey.Escape;
		}
		return true;
	},
	s => Console.WriteLine(s));

Na linha 2 está a função de trabalho, no caso computar dígitos de Pi usando uma implementação da fórmula de Fabrice Bellard (sim! o criador do FFMPEG entre outros projetos). Costumamos usar essa implementação como forma de medir a performance de CPUs das máquinas que executam nossas aplicações.

Entre as linhas 5 e 15 está a função que é chamada cada vez que um bloco termina. No exemplo ela apenas mostra no console o tempo gasto e o quanto foi feito. Essa função também permite a interrupção graciosa do loop de execução.

Na linha 16 está a função que mostra outros updates do algoritmo, tais como ajustes de tamanho de cada lote.

Somente os dois primeiros parâmetros são obrigatórios, gerando tarefas quebradas em lotes de 10 segundos ideais, e com o primeiro lote de tamanho 100.

Mas... Escala Linearmente?

Uma solução de problema paralelo ideal deve escalar linearmente em função:

1. do tamanho da tarefa: bastante óbvio, computar 100 digitos de Pi mil vezes deve levar um décimo do tempo que computar 10 mil vezes. E a implementação escala, desde que não hajam interrupções excessivas em função da tarefa total, por exemplo: notificações a cada décimo de segundo quando a tarefa total leva poucos segundos e cada notificação consome alguns milésimos de segundo.
2. do número de CPUs alocadas para a tarefa: parece simples, rodar em 8 CPUs deve consumir metade do tempo que rodar em 4 CPUs. Infelizmente não é sempre assim, devido as CPUs não serem sempre todas iguais, não estarem todas disponíveis todo o tempo (a máquina tem outras tarefas a executar), e a tarefa nunca ser dependente apenas de CPU, dependendo muitas vezes de memória ou até de recursos bem mais lentos tais como armazenamento e rede.

A tabela e o gráfico abaixo mostram a execução do programa mencionado neste artigo em máquinas de diferentes capacidades para determinar o fator de paralelismo, isto é, a divisão do tempo entre executar com uma thread e executar com N threads. O fator de paralelismo ideal é igual ao número de threads usadas.

e os dados que deram origem ao gráfico acima.

Algumas conclusões interessantes:

1. Não adianta, num loop paralelo, configurar ParallelOptions.MaxDegreeOfParallelism com um valor acima do número de CPUs lógicas relatadas por Environment.ProcessorCount, a não ser que cada item da tarefa dependa de algo com latência maior que memória, ou você queira reservar potência na máquina para outras tarefas. Para máxima eficiência é melhor deixar o parâmetro com o valor padrão.
2. Hyper-threading é bom, mas também é frustrante. As máquinas que mais perfeitamente escalaram foram as duas que não possuem hyper-threading. As máquinas com hyper-threading escalaram de modo pior, embora tenham apresentado ganho de escala até o número de CPUs lógicas.

Perguntas, e um apelo

Algumas perguntas não puderam ser respondidas:

1. Como se comportam as CPUs da AMD em função da carga paralela?
2. Como se comportam as vCPUs de máquinas virtuais?
3. No caso de máquinas virtuais o comportamento varia em função da CPU da máquina host? Em função do software hypervisor?

O projeto associado a este artigo, aqui compilado para 32 bits e para 64 bits pode me ajudar a responder estas questões, se você dispuser de 15 minutos numa máquina multi-core, virtual ou real, Intel ou AMD.

O programa é uma aplicação console, que precisa do .Net Framework 4.0 na máquina. Ao iniciar ele vai obter alguma informação da máquina, em especial o número de CPUs fisicas e cores, além de uma identificação do modelo da CPU; em seguida executar por 5 vezes a computação de uma tarefa pesada (computar Pi com 100 digitos 1.000 vezes); seguido de uma tarefa leve (computar Pi com 25 digitos 20.000 vezes); e então gerar no diretório de execução um arquivo com nome similar a "Test.ParallelWork.20130925.1955.txt". Caso ele não possa escrever o arquivo no diretório de execução os resultados serão copiados para o clipboard. Nenhuma permissão administrativa é necessária para executar o programa, e nenhuma informação pessoal, ou da máquina, exceto informação da CPU, é obtida.

A execução do programa dá feedback a cada 1 segundo e na maior parte do tempo vai usar quase toda a CPU disponível na máquina, embora seja bastante leve em termos de memória e demais recursos.

Após a execução mande, por favor, os resultados para negri@elekto.com.br. Garanto privacidade nestas questões (odeio spam tanto quanto você!). E só publicarei um agradecimento a você, ou sua instituição, com sua permissão.

Em obtendo novas medições atualizarei este artigo com as conclusões possiveis. Me ajude, por favor!

Notas

1. Todo o código deste artigo usa a licença MIT, ou seja: o uso é livre em qualquer circunstância, mas não damos qualquer garantia.