Pools de threads
Programação multi-threaded escalonável com pools de threads
Ron Fosner
A programação tem se tornado mais desafiadora, principalmente quando se trabalha em uma área que exige que você ajuste seu aplicativo para obter a taxa de transferência mais rápida possível. Um dos fatores que contribui para isso é que, nos últimos anos, temos visto uma mudança na forma como os PCs estão evoluindo. Em vez de contar com a velocidade cada vez maior de um único processador, agora a capacidade computacional dos PCs está sendo distribuída entre vários núcleos. Isso é um ponto positivo. Aumentos robustos na capacidade de processamento latente agora estão disponíveis a um custo relativamente baixo, e muitas vezes com necessidades de resfriamento e consumo de energia bem menores.
Mas a prevalência cada vez maior dos sistemas de vários núcleos tem uma desvantagem. Para usar vários processadores, é preciso mergulhar no mundo do processamento paralelo. Isso significa que é muito mais trabalhoso — e, às vezes, demanda uma curva de aprendizado considerável — para os programadores aproveitarem essa capacidade de processamento latente. É possível inserir algumas dicas de compilador no seu projeto e fazer com que o compilador crie um código multi-threaded para você. No entanto, para aproveitar todo o potencial dos PCs de vários núcleos, você terá de fazer algumas alterações na forma como programa trabalhos grandes.
Existem várias maneiras de distribuir o trabalho entre vários núcleos. Uma das mais fáceis e robustas é a chamada programação baseada em tarefas. As tarefas permitem que você pegue o trabalho do aplicativo e o distribua entre alguns ou todos os núcleos disponíveis da CPU. Com um pouco de programação bem-elaborada, você pode minimizar ou até mesmo eliminar quaisquer restrições de dependência de dados ou sincronização de hora. Para atingir esse estado de êxtase multi-core, você terá de reexaminar alguns dos seus preconceitos sobre como resolver um problema de programação e repensá-los em termos da programação baseada em tarefas.
Para mostrar como isso pode funcionar, vou orientá-lo nas etapas — e mostrar as etapas erradas — que segui para converter um aplicativo de um único thread em um que pode ser escalonado para usar todas as CPUs disponíveis no computador. Neste artigo, apresentarei alguns conceitos da programação multi-threaded e algumas maneiras simples de introduzir a execução de thread no código com o OpenMP e pools de threads. Você também aprenderá a usar o Visual Studio 2010 para avaliar o aperfeiçoamento de desempenho conquistado com essas técnicas. Em um próximo artigo, falarei mais sobre essa base para mostrar uma execução multi-threaded mais sofisticada com tarefas.
De threads a tarefas
O principal desafio ao se escalonar um programa de acordo com o número de núcleos de CPU é que não se pode decidir colocar alguns trabalhos em seus próprios threads e deixar que sejam executados. Na verdade, é isso que muita gente faz, mas o escalonamento só funciona com o número de núcleos para os quais o aplicativo foi projetado. O escalonamento não é eficiente com um número menor ou maior de núcleos do que o pretendido e ignora completamente a obsolescência interna causada por uma abordagem como essa.
Uma forma melhor de se certificar de que o aplicativo está bem-escalonado com um número variável de núcleos é dividir trabalhos grandes em menores, subtrabalhos compatíveis com threads chamados de tarefas. A parte mais desafiadora de se converter um programa monolítico de um único thread ou um programa que tenha alguns threads dedicados em um sistema de trabalho baseado em tarefas é dividir os trabalhos em tarefas.
Existem algumas diretrizes que devem ser consideradas ao se converter um trabalho grande de um único thread em tarefas multi-threaded:
- O trabalho grande pode ser dividido arbitrariamente em 1 a n tarefa(s).
- As tarefas devem poder ser executadas em qualquer ordem.
- As tarefas devem ser independentes umas das outras.
- As tarefas devem ter dados de contexto associados.
Se isso fosse fácil, você não teria dificuldade para fazer seus aplicativos executarem em qualquer número de núcleos. Infelizmente, nem todos os problemas podem ser divididos de uma forma tão clara em tarefas que atendam a essas diretrizes.
Essas diretrizes são importantes porque, se seguidas, permitem executar cada tarefa de forma independente em um thread, sem dependência entre tarefas. O ideal é que as tarefas possam ser executadas em qualquer ordem, por isso eliminar ou diminuir as dependências é fundamental para o funcionamento de um sistema baseado em tarefas.
A maioria dos programas do mundo real passará por vários estágios de processamento, sendo que cada estágio deve ser concluído antes de se iniciar o próximo. Esses pontos de sincronização muitas vezes são inevitáveis, mas com um sistema baseado em tarefas o objetivo é assegurar que você aproveite qualquer que seja a capacidade de CPU disponível de imediato. Usando um pouco de critério na divisão dos trabalhos grandes em menores, com frequência é possível começar a misturar alguns resultados de tarefas concluídas com o próximo estágio de processamento, enquanto algumas tarefas iniciais ainda estão sendo executadas.
Multithreading simples com o OpenMP
Antes de converter todo o aplicativo para usar tarefas, você deve estar ciente de outras formas de obter alguns dos benefícios do multithreading sem passar pelo rigoroso exercício de transformar tudo em tarefa. Existem inúmeras maneiras de incorporar o multithreading ao seu aplicativo — muitas demandam pouco trabalho, na verdade — mas que ajudam você a se beneficiar com a adição do multithread ao código.
O OpenMP é uma das formas mais simples de adicionar processamento paralelo aos seus programas e tem suporte no compilador Visual Studio C++ desde 2005. Para habilitar o OpenMP, adicione pragmas ao código que indiquem onde e que tipo de paralelismo você gostaria de acrescentar. Por exemplo, você pode adicionar paralelismo a um programa Hello World simples:
#include <omp.h> // You need this or it won't work
#include <stdio.h>
int main (int argc, char *argv[]) {
#pragma omp parallel
printf("Hello World from thread %d on processor %d\n",
::GetCurrentThreadfID(),
::GetCurrentProcessorNumber());
return 0;
}
O pragma OpenMP processa o próximo bloco de código em paralelo — neste caso, é apenas printf — e o executa simultaneamente em todos os threads de hardware. O número de threads dependerá da quantidade de threads de hardware disponíveis no computador. A saída é uma instrução printf executando em cada thread de hardware.
Para que qualquer programa OpenMP processe em paralelo (e não ignore seus pragmas OpenMP silenciosamente), você precisa habilitar o OpenMP para o programa. Primeiro, você deve incluir a opção de compilador /openmp (Properties | C/C++ | Language | Open MP Support). Depois, é preciso incluir o arquivo de cabeçalho omp.h.
O OpenMP realmente se destaca quando o seu aplicativo passa a maior parte do tempo executando funções ou dados em loop e você deseja adicionar suporte para multiprocessamento. Por exemplo, se você tem um loop for que demora um pouco para ser executado, pode usar o OpenMP para paralelizar o loop. Este é um exemplo que divide cálculos de matriz automaticamente e os distribui entre o número de núcleos disponíveis:
#pragma omp parallel for
for (int i = 0; i < 50000; i++)
array[i] = i * i;
O OpenMP tem outras construções que oferecem mais controle sobre o número de threads criados, independentemente da necessidade de concluir o trabalho distribuído antes de o próximo bloco de código ser executado, criando dados locais no thread, pontos de sincronização, seções críticas e assim por diante.
Como você pode ver, o OpenMP é uma maneira fácil de moderadamente introduzir o paralelismo em uma base de código já existente. Contudo, embora a simplicidade do OpenMP seja atraente, há situações em que você precisa ter mais controle sobre o que o aplicativo está fazendo; por exemplo, quando você deseja que o programa ajuste dinamicamente o que está fazendo ou quando precisa assegurar que um thread permaneça em um determinado núcleo. A finalidade do OpenMP é integrar facilmente alguns aspectos da programação multi-threaded ao seu programa, mas ele carece de alguns dos recursos avançados que você descobrirá que precisa para aproveitar ao máximo os vários núcleos. É neste ponto que as tarefas e os pools de threads entram em ação.
Usando o pool de threads
Os threads exigem muito controle por parte do sistema operacional, por isso não é uma boa ideia criá-los e destruí-los arbitrariamente. Existem custos nada insignificantes associados à criação e à destruição de um thread; portanto, se você fizer isso com frequência, poderá perder facilmente qualquer vantagem obtida com o multithreading.
Em vez disso, é melhor usar um conjunto de threads existente, reciclado quando necessário, para toda a atividade de thread. Esse design é chamado de pool de threads, e o Windows fornece um para que você possa usar. Usando esse pool de threads, você não precisa lidar com a criação, a destruição e o gerenciamento de threads, pois tudo isso é providenciado pelo pool. O OpenMP usa um pool de threads para distribuir o trabalho com threads, e tanto o Windows Vista quanto o Windows 7 fornecem versões otimizadas do pool para você usar diretamente.
Embora seja totalmente possível criar o seu próprio pool de threads, o que talvez você precise fazer se tiver alguns requisitos de agendamento incomuns, é recomendável utilizar o pool fornecido pelo sistema operacional ou pelo Microsoft .NET Framework.
Agora preciso esclarecer a terminologia. Quando a maioria das pessoas fala em thread, estão se referindo ao fluxo de execução por meio de um único núcleo da CPU — em outras palavras, um thread de software. Em uma CPU, o fluxo de execução (a execução de instruções propriamente dita) ocorre em threads de hardware. O número de threads de hardware é limitado pelo hardware no qual o aplicativo está em execução. Antigamente, costumava ser uma CPU de um único thread, mas agora é comum encontrar sistemas que têm pelo menos processadores de núcleo duplo. Uma CPU de quatro núcleos poderá executar quatro threads de hardware ou oito se tiver a tecnologia Hyper-Threading. Sistemas desktop de ponta contêm até 16 threads de hardware, e algumas configurações de servidor possuem mais de 100!
Embora um thread de hardware na verdade execute as instruções, um thread de software refere-se ao contexto inteiro — valores de registro, identificadores, atributos de segurança, entre outros — o que é necessário para efetivamente executar o trabalho em um thread de hardware. É importante observar que você pode ter muito mais threads de software do que de hardware, e esta é a base de um pool de threads. Ele permite enfileirar tarefas com threads de software e, depois, agendá-las para execução nos threads de hardware propriamente ditos.
A vantagem de usar um pool de threads em vez de criar seus próprios threads é que o sistema operacional se encarregará de agendar as tarefas para você — seu trabalho será continuar inserindo tarefas no pool de threads para que o SO possa manter todos os threads de hardware ocupados. O processo é ilustrado na Figura 1. Tudo no computador forma o pool de threads e está fora do domínio do programador. Fica a critério do aplicativo carregar tarefas no pool de threads, onde elas são colocadas na fila de threads e, mais tarde, agendadas para execução em um thread de hardware.
Figura 1 Um pool de threads
Agora você chegou à parte difícil: qual é a melhor forma de estruturar trabalhos para manter os núcleos ocupados e a utilização da CPU no seu máximo? Isso depende do que o aplicativo precisa fazer.
Com frequência trabalho com empresas de videogames, que são um dos tipos de aplicativos mais desafiadores para se trabalhar, pois há muito que fazer — geralmente em uma certa ordem serial — e ficamos suscetíveis a atrasos. Normalmente há uma determinada taxa de quadros para a atualização do programa, por isso, se as taxas de quadros começam a ficar para trás, a experiência do jogo é afetada. Como consequência, existe muito incentivo para maximizar o uso do hardware.
Por outro lado, se o seu aplicativo faz uma operação grande de cada vez, o que você precisa fazer fica um pouco mais óbvio, mas continua sendo desafiador tentar distribuir um único trabalho entre vários núcleos.
Classificação multi-threaded
Primeiro, vamos analisar um trabalho monolítico que muitas vezes é encontrado em aplicativos e ver como transformá-lo em um formulário mais amigável para multithreading. É claro que estou pensando em classificação. A classificação é um exemplo particularmente bom porque apresenta um grande obstáculo: como classificar algo e espalhar a classificação entre vários núcleos para que a classificação em um núcleo seja independente do que está sendo classificado em outro núcleo?
Uma abordagem simples vista com frequência é bloquear o acesso a qualquer dado que possa ser acessado por vários núcleos usando algo como um mutex, um semáforo ou uma sessão crítica. Isso funcionará. No entanto, se for usado como panaceia por não agendar corretamente o acesso a dados compartilhados, na melhor das hipóteses você vai acabar minando os ganhos obtidos por impedir a execução de outros threads. Na pior das hipóteses, você poderá introduzir uma sutil condição de concorrência que será penosamente difícil de controlar.
Felizmente, é possível projetar o aplicativo para eliminar a maior parte do acesso compartilhado a dados entre threads escolhendo o algoritmo de classificação apropriado.
Uma abordagem mais adequada é dar a cada núcleo uma subseção da matriz para classificar. Este método “dividir e conquistar” é uma forma fácil de distribuir o trabalho no mesmo conjunto de dados entre vários núcleos. Algoritmos como classificação por mesclagem e classificação rápida funcionam em uma estratégia “dividir e conquistar” e são simples de implementar para aproveitar as vantagens de um sistema de vários núcleos.
Vejamos como funciona a classificação por mesclagem na cadeia de inteiros aleatórios mostrada na Figura 2. O primeiro passo é escolher um ponto médio na matriz e dividi-a em duas sublistas. Continue dividindo até ter listas contendo zero ou um elemento.
Figura 2 Classificando uma cadeia de inteiros aleatórios
Na maioria das implementações, na verdade existe um limite de tamanho de lista abaixo do qual se tem um algoritmo eficiente para listas pequenas, mas ele também funciona se você continuar dividindo até não ser mais possível dividir. O ponto importante a ser observado é que, uma vez que você divida uma lista em duas sublistas, as listas são independentes. Isso é ilustrado pelas linhas vermelhas tracejadas na Figura 2. Quando você divide a lista em sublistas, cada sublista é independente e é possível atribuir cada uma para uma CPU manipulá-la da forma desejada, sem precisar bloquear nada.
Para tornar a classificação o mais eficiente possível, escolha um algoritmo que usará cada sublista e a classificará localmente. Isso é importante não somente para evitar a cópia desnecessária dos dados, mas também para mantê-los seguros no cache L2 da CPU. À medida que você procura criar um código paralelo cada vez mais eficiente, deve saber como os dados são inseridos e trocados no cache L2, que geralmente tem cerca de 256 KB na maioria dos processadores modernos.
Existem muitos algoritmos de classificação que servem para paralelização. Classificação rápida, classificação por seleção, classificação por mesclagem e classificação base são algoritmos que subdividem os dados e operam neles de maneira independente. Então vamos dar uma olhada em uma implementação serial de uma rotina de classificação e convertê-la em paralela.
Teoricamente, se você continuar subdividindo uma matriz de forma recursiva, terminará com um único elemento. Nesse ponto, não há nada para ser classificado, portanto o algoritmo passará para a próxima etapa, que é mesclar as sublistas classificadas. Os elementos individuais são mesclados em listas classificadas maiores. Em seguida, essas sublistas classificadas são mescladas em listas classificadas ainda maiores, até que você tenha a matriz original em uma ordem classificada. Como mencionei antes, geralmente é mais rápido alternar para um algoritmo que é otimizado para classificar listas pequenas quando o tamanho das listas atinge um certo limite.
Existem várias maneiras de criar um algoritmo de classificação, e eu optei por escrever uma rotina de classificação rápida simples em C#, como ilustrado na Figura 3. Este programa preenche uma matriz grande com a mesma sequência de números aleatórios e os classifica usando uma rotina de classificação rápida, que reporta o tempo gasto.
Figura 3 Classificação rápida
using System;
using System.Threading;
using System.Threading.Tasks;
using System.Diagnostics;
namespace ParallelSort {
class Program {
// For small arrays, use Insertion Sort
private static void InsertionSort(
int[] list, int left, int right) {
for (int i = left; i < right; i++) {
int temp = list[i];
int j = i;
while ((j > 0) && (list[j - 1] > temp)) {
list[j] = list[j - 1];
j = j - 1;
}
list[j] = temp;
}
}
private static int Partition(
int[] array, int i, int j) {
int pivot = array[i];
while (i < j) {
while (array[j] >= pivot && i < j) {
j--;
}
if (i < j) {
array[i++] = array[j];
}
while (array[i] <= pivot && i < j) {
i++;
}
if (i < j) {
array[j--] = array[i];
}
}
array[i] = pivot;
return i;
}
static void QuickSort(
int[] array, int left, int right) {
// Single or 0 elements are already sorted
if (left >= right)
return;
// For small arrays, use a faster serial routine
if ( right-left <= 32) {
InsertionSort(array, left, right);
return;
}
// Select a pivot, then quicksort each sub-array
int pivot = Partition(array, left, right);
QuickSort(array, left, pivot - 1);
QuickSort(array, pivot + 1, right);
}
static void Main(string[] args) {
const int ArraySize = 50000000;
for (int iters = 0; iters < 1; iters++) {
int[] array;
Stopwatch stopwatch;
array = new int[ArraySize];
Random random1 = new Random(5);
for (int i = 0; i < array.Length; ++i) {
array[i] = random1.Next();
}
stopwatch = Stopwatch.StartNew();
QuickSort(array, 0, array.Length - 1);
stopwatch.Stop();
// Verify it is sorted
for (int i = 1; i < array.Length; ++i)
if (array[i - 1] > array[i - 1])
throw new ApplicationException("Sort Failed");
Console.WriteLine("Serialt: {0} ms",
stopwatch.ElapsedMilliseconds);
}
}
}
}
Se você reparar na função QuicSort, verá que ela divide a matriz em duas recursivamente até atingir um limite, quando então classifica a lista sem mais subdivisões. Se você mudar isso para uma versão paralela, tudo o que terá de fazer é alterar estas duas linhas:
QuickSort( array, lo, pivot - 1);
QuickSort( array, pivot + 1, hi);
A versão paralelizada é:
Parallel.Invoke(
delegate { QuickSort(array, left, pivot - 1); },
delegate { QuickSort(array, pivot + 1, right); }
);
A interface Parallel.Invoke faz parte do namespace Systems.Threading.Tasks encontrado na Biblioteca de Tarefas Paralelas do .NET. Ela permite especificar uma função a ser executada de modo assíncrono. Nesse caso, digo a ela que quero executar cada função de classificação em um thread à parte.
Embora seja mais eficiente gerar apenas um novo thread e usar o thread de execução atual para classificar a outra sublista, quis manter a simetria e mostrar como é fácil converter um programa serial em um programa paralelo.
Utilização de núcleos
A próxima pergunta óbvia é: Essa paralelização melhorou o desempenho?
O Visual Studio 2010 tem diversas ferramentas que ajudam a entender onde o seu programa está gastando tempo e como ele se comporta em um aplicativo multi-threaded. Existe uma excelente introdução sobre como usar essas ferramentas para avaliar o desempenho do seu aplicativo multi-threaded com o Visual Studio 2010 na edição de setembro de 2009 da MSDN Magazine no artigo “Depurando aplicativos paralelos com base em tarefas no Visual Studio 2010”, de Stephen Toub e Daniel Moth (msdn.microsoft.com/magazine/ee410778), além de uma boa introdução em vídeo elaborada por Daniel Moth no Channel 9 (channel9.msdn.com/posts/DanielMoth/Parallel-Tasks--new-Visual-Studio-2010-debugger-window/).
A programação paralela exige que você de fato adote medidas para verificar se verdadeiramente melhorou o desempenho e se está utilizando todo o hardware. Para saber mais sobre como a paralelização estava sendo usada no meu aplicativo de exemplo, vamos utilizar essas ferramentas para avaliar as rotinas de classificação em ação. Iniciei o Performance Wizard do Visual Studio 2010 para tirar medidas de simultaneidade do meu aplicativo de classificação enquanto ele é executado.
A primeira coisa que vamos verificar é a utilização de núcleos, que mostra como o aplicativo utilizou os ciclos de CPU disponíveis. Meu programa de teste executa a classificação serial, entra no modo de suspensão por um segundo e, depois, executa a versão paralela da classificação. No meu computador de 4 núcleos, tenho o gráfico da utilização de núcleos mostrado na Figura 4. O verde é o meu aplicativo, o amarelo é o SO e outros programas, e o cinza indica o que está ocioso. A linha reta no nível do núcleo 1 mostra que saturei totalmente o processamento em um único núcleo quando executo a versão serial e que tenho cerca de 2,25 de quatro núcleos quando executo a versão paralela. Não é de surpreender que o tempo necessário para executar a classificação paralela é aproximadamente 45% do tempo necessário para a classificação serial. Nada muito precário para alterar duas linhas de código.
Figura 4 Utilização de núcleos
Agora vamos passar do gráfico de utilização da CPU para a tela de threads mostrada na Figura 5, que ilustra como o aplicativo utilizou os threads disponíveis. Observe que há um único thread para a maior parte do tempo de execução. Só são criados mais threads quando você começa a gerar tarefas. Nesta tela, a cor salmão indica um thread que foi bloqueado por outro thread.
Figura 5 Trabalho com threads
Na verdade, a tela de threads mostra que, apesar de eu ter obtido um aumento considerável na velocidade de execução, não fiz isso com muita eficiência. Não há problema nenhum em ter um bloqueio de threads, aguardando outros threads da mesma forma que o thread principal está aguardando a conclusão das tarefas. Porém, o que realmente queremos ver é um verde sólido em tantas tarefas quantos são os núcleos da CPU. Por isso, embora o gráfico de uso da CPU mostre uma melhor utilização dos núcleos, quando vemos de perto como as tarefas foram distribuídas pelo pool de threads, percebemos que há espaço para mais otimização.
Na verdade, sempre devemos avaliar o desempenho do código só depois de trabalharmos com multithreading — mesmo que seja um trabalho tão simples quanto o que fiz aqui. No caso de trabalhos pequenos, não é preciso usar multithreading porque a sobrecarga anulará qualquer desempenho de threading. Para trabalhos maiores, você deve dividir o trabalho entre tantos núcleos de CPU quantos estiverem disponíveis para não subscrever o pool de threads em excesso.
O que vem a seguir?
Existem várias maneiras de atingir um desempenho ainda melhor através do código, mas esse não é o objetivo deste artigo inicial. Mas você percebeu como obter 80% de utilização da CPU fazendo apenas algumas alterações no código para torná-lo amigável para threads. No entanto, melhor do que otimizar ainda mais esse código, vamos nos concentrar em obter o máximo desempenho das CPUs de um sistema criando trabalhos de uma forma um pouco diferente.
Do modo como demonstrei aqui, a classificação é particularmente acessível para multithreading. É possível calcular até que ponto dividir o trabalho e atribuir cada subtrabalho a um thread. Todavia, embora eu tenha realmente conseguido um aumento no desempenho, também perdi um pouco de desempenho.
Mas, em aplicativos reais, talvez você se depare com uma situação em que ou há muitos trabalhos que geram grupos de tarefas exclusivas ou possivelmente você não sabe por quanto tempo uma determinada tarefa será executada e a necessidade de agendar tarefas levando em consideração essa dúvida. É um problema extraordinariamente desafiador. No meu próximo artigo, vou analisar uma arquitetura que usa uma abordagem holística de threading, que permite distribuir múltiplos e, porventura, diferentes trabalhos. Mostrarei como projetar um aplicativo para torná-lo compatível com vários núcleos, desde o início até o uso de tarefas e de pools de threads.
Ron Fosner otimiza jogos e aplicativos de alto desempenho no Windows há 20 anos e está começando a entender como tudo funciona. É especialista em imagens e otimização na Intel e fica mais feliz quando vê todos os núcleos da CPU funcionando sem restrições. Você pode entrar em contato com ele pelo email Ron@directx.com.
Agradecemos ao seguinte especialista técnico pela revisão deste artigo: Stephen Toub