Embed Size (px)
Citation preview
Grand Central Dispatch
Marcio Rocha dos Santos
Trabalho de conclusão de cursoOrientador: Prof. Dr. Alfredo Goldman vel Lejbman
Co-Orientador: Emilio De Camargo Francesquini
São Paulo, Dezembro de 2010
Sumário
I Parte técnica 1
1 Introdução 3
2 História 5
3 Conceitos 9
3.1 Programação paralela . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 Speedup e eficiência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.3 Programação concorrente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4 Grand Cental Dispatch 13
4.1 Block Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.1.1 Sintaxe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.2 Dispatch queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.3 Synchronization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.4 Event sources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.5 Leitura e construção do código . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
iv SUMÁRIO
5 Atividades realizadas 21
5.1 Explorando as funcionalidades . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.2 Testes de desempenho e Resultados obtidos . . . . . . . . . . . . . . . . . . . . 22
5.2.1 Tarefas crescentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.2.2 Tarefas curtas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5.2.3 Divisão do trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
6 Conclusões 29
II Parte subjetiva 31
7 Experiência pessoal 33
7.1 Estudos futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
7.2 Disciplinas relevantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
A Códigos de comparação 39
B Código de implementação de concorrência 41
Parte I
Parte técnica
Capítulo 1
Introdução
A velocidade dos processadores, que vinham seguindo a Lei de Moore [9], não demoroua esbarrar num determinado conjunto de limitações físicas, das quais uma denominou-se porpower wall ou “barreira de potência”, pois devido a um tráfego intenso de energia atraés decada chip, bem como da dissipação dessa energia em forma de calor, de maneira que cadachip alcançasse a temperatura de fusão do metal que o compunha, dessa forma aruinando-ocompletamente. Os sistemas atuais de arrefecimento já estão com certa dificuldade de dissiparesse calor de um modo eficiente e barato.
Até a década de 80, computadores com um único processador ainda tinham boa par-ticipação na lista dos top 500 [10], porém desde 1996 essa lista é preenchida apenas comcomputadores de arquitetura multicore.
Como a demanda por computadores de alto desempenho continua crescendo, a indústriamudou para chips com múltiplos núcleos e clocks mais baixos, que podem fornecer maior poderde processamento, consumindo menos energia. Mas para tirar o máximo proveito dessesprocessadores, um novo modo de programar deve acompanhar o desenvolvimento da novaarquitetura. Entretanto, mesmo com os avanços na área de hardware, a computação paralelanão tem se desenvolvido rápido o suficiente. A computação enfrenta uma crise com a falta deprogramadores qualificados nessa área e de ferramentas que auxiliem a paralelização. Muitosdos programas atuais que se utilizam de dois ou quatro processadores não tirarão melhorproveito dos manycores do futuro com dezenas de núcleos.
4 Introdução
A programação paralela é difícil com a gestão manual de threads. No entanto, os me-lhores programadores do mundo são pressionados a criar grandes programas multithread emlinguagens de baixo nível como C ou C + +, garantindo exclusão mútua, sem ocorrência dedeadlock, condição de corrida, e outros perigos inerentes à programação concorrente. Aplica-ções extremamente cuidadosas de bloqueio primitivo se fazem necessárias para evitar quedade desempenho e bugs, ao lidar com dados compartilhados. Portanto nosso problema é: ousuário impedido de usar todos recursos computacionais, mesmo que estejam ociosos, pois osprogramas não sabem lidar com esses recursos.
Estudaremos uma solução da Apple, já implementada na versão Snow Leopard doMAC OS X, que promete tornar o trabalho dos desenvolvedores de software mais fácil, utili-zando os recursos do hardware ao máximo. Essa solução da Apple se chamada Grand CentralDispatch (GCD) [3], uma biblioteca C introduzida nos níveis mais baixos do sistema operaci-onal.
Capítulo 2
História
A primeira geração de computadores estabeleceu os conceitos básicos de organização doscomputadores eletrônicos, e na década de 50 apareceu o modelo computacional que se tornariaa base de todo o desenvolvimento subsequente, chamado "modelo de von Neumann"(figura2.1). O modelo de von Neumann é composto basicamente por processador, memória e dis-positivos de E/S. O processador executa instruções sequencialmente, de acordo com a ordemditada por uma unidade de controle.
Figura 2.1: Arquitetura de von Neumann
O problema dessa arquitetura chama-se gargalo de von Neumann, que é a limitação dataxa de transferência entre a memória e a CPU. Quando as arquiteturas eram mais simples,
6 História
funcionava bem. Porém, foram surgindo necessidades de melhora, tais como o aumentar avelocidade dos dispositivos, o que depende do desenvolvimento tecnológico, e executar tarefasem paralelo.
O avanço dos dispositivos foi acontecendo de forma gradual até os anos 80, com o surgi-mento da filosofia VLSI (Very-large-scale integration) [11]. VLSI é o processo de criação decircuitos integrados, combinando milhares de transistores em um único chip. Historicamente,a utilização de paralelismo começou pelo hardware. O aumento da velocidade do hardware,por mais rápida que possa ser, sempre esbarra no limite tecnológico de cada época. Dessaforma, desde o início do desenvolvimento dos computadores, percebeu-se que a utilização deparalelismo é essencial. A paralelização proporcionou grandes mudanças nas arquiteturas, queevoluíram ao longo dos anos com o surgimento de diversas características nas máquinas, taiscomo:
· em 1953, surgiu o conceito de palavra, levando à manipulação de vários bits em paralelo,ao invés da unidade;
· em 1958, processadores de E/S possibilitaram o paralelismo entre E/S e processamento,tornando a tarefa de E/S mais independente;
· em 1963, como memória também era o gargalo do sistema, surgiram técnicas como cachee interleave (que permite a obtenção de mais de uma palavra na memória, em paralelo);
· em 1970, aparecimento de pipelines, paralelizando a execução de instruções, operaçõesaritméticas, etc;
· no período de 1953 a 1970, o paralelismo existente é transparente ao usuário, influen-ciando apenas na melhoria do desempenho da máquina, sendo denominado paralelismode baixo nível.
· em 1975, nasceu o Illiac IV, com 64 processadores, primeira forma em que o paralelismodiferia do de baixo nível. Foi o computador mais rápido até o aparecimento do Cray;
7
· em 1984, surgimento da filosofia VLSI de projeto de microcomputadores, oferecendomaior facilidade e menor custo no projeto de microprocessadores cada vez mais comple-xos e menores (computadores pessoais).
A partir do aparecimento dos computadores pessoais e a redução dos custos dos compo-nentes, foi possível colocar dois ou mais processadores em máquinas paralelas. E enfim osurgimento, em 2005, dos processadores multicore no mercado, com o IntelrPentiumrD, deuinício a era da arquitetura multicore.
8 História
Capítulo 3
Conceitos
3.1 Programação paralela
A programação sequencial consiste na execução de várias tarefas, uma após a outra. Aprogramação concorrente é definida como a execução simultânea de várias instruções. Podetambém ser formada por várias instruções que foram iniciadas em determinado instante e aindanão finalizaram. A programação concorrente pode ser executada tanto em um só processador,explorando o que se chama de pseudoparalelismo, quanto em uma arquitetura paralela, comvários processadores. No caso de vários processadores, essa programação passa a incorporara chamada programação paralela, que se caracteriza pela execução de várias tarefas em ummesmo instante. Embora relacionada com programação paralela, programação concorrentefoca mais na interação entre as tarefas.
Algumas definições de programação paralela:
- Almasi, G. S. [12]: "Coleção de elementos de processamento que se comunicam e coope-ram entre si e resolvem um problema mais rapidamente".
- Quinn, M. J. [13]: "Processamento de informação que enfatiza a manipulação concor-rente de dados que pertencem a um ou mais processos que resolvem um único problema".
- Hwang, K. [14]: "Forma eficiente do processamento de informações com ênfase na ex-ploração de eventos concorrentes no processo computacional"
10 Conceitos
As vantagens da utilização de programação paralela consistem em:
· Alto desempenho, minimizando com o chamado gargalo de von Neumann. É o objetivoprincipal da programação paralela. A divisão de um problema em diversas tarefas podelevar a uma redução considerável no tempo de execução;
· Substituição dos computadores de altíssimo custo. As arquiteturas paralelas apresentamum custo menor que uma arquitetura com um único processador e a mesma capacidade;
· Tolerância a falhas, pois a programação paralela facilita a implementação de mecanismosde tolerância a falhas;
· Modularidade, sendo que um programa longo pode ser subdividido em várias tarefas queexecutam independentemente e se comunicam entre si.
· Economia de energia. Reduzindo o clock dos processadores, mesmo com quantidadesmaiores de processadores ou núcleos, é possível ter maior poder de processamento gas-tando menos energia.
O uso de programação paralela também tem desvantagens. Podemos citar a programaçãomais complexa, pois acarreta em uma série de problemas inexistentes na programação sequen-cial, tais como comunicação, sincronismo, balanceamento de carga, etc. Também pode serintroduzido sobrecargas para suprir fatores como comunicação e sincronismo entre as tarefasem paralelo. Essas sobrecargas devem ser cuidadosamente analisadas, pois impedem que sejaalcançado o speedup ideal.
3.2 Speedup e eficiência
Uma característica fundamental da computação paralela trata-se do aumento de veloci-dade de processamento através da utilização do paralelismo. Neste contexto, duas medidasimportantes para a verificação da qualidade de algoritmos paralelos são speedup e eficiência.Uma definição largamente aceita para speedup é: aumento de velocidade observado quando se
3.3 Programação concorrente 11
executa um determinado processo em p processadores em relação à execução deste processoem 1 processador. Então, tem-se:
speedup =T1
Tp
onde,
· T1 = tempo de execução em 1 processador;
· Tp = tempo de execução em p processadores.
Idealmente, o ganho de speedup deveria tender a p, que seria o seu valor ideal. Porém, trêsfatores podem ser citados que influenciam essa relação: sobrecarga da comunicação entre osprocessadores, partes do algoritmo não paralelizáveis e o nível de paralelismo inadequado naarquitetura de software. Outra medida importante é a eficiência, que trata da relação entre ospeedup e o número de processadores.
Eficiencia =speedup
p
No caso ideal (speedup = p), a eficiência seria máxima e teria valor 1 (100%).
3.3 Programação concorrente
Um programa sequencial é composto por um conjunto de instruções que são executadassequencialmente, sendo que a execução dessas instruções é denominada um processo. Umprograma concorrente especifica dois ou mais programas sequenciais que podem ser executadosconcorrentemente como processos paralelos [1].
A programação concorrente existe para que se forneçam ferramentas para a construção deprogramas paralelos, de maneira que se consiga melhor desempenho e melhor utilização dohardware paralelo disponível. A computação paralela apresenta vantagens importantes emrelação à computação sequencial, como foi exposto acima, e todas essas vantagens podem sercitadas como pontos de incentivo para o uso da programação concorrente.
Um programa sequencial é constituído basicamente de um conjunto de construções já bem
12 Conceitos
dominadas pelo programador em geral, como por exemplo, atribuições, comandos de decisão(if... then... else), laços (for... do), entre outras. Um programa concorrente, além dessasprimitivas básicas, necessita de novas construções que o permitam tratar aspectos decorrentesda execução paralela dos vários processos. A fase de definição da organização das tarefasparalelas é de extrema importância, pois o ganho de desempenho adquirido da paralelizaçãodepende fortemente da melhor configuração das tarefas a serem executadas concorrentemente.
Na definição do algoritmo, é necessário um conjunto de ferramentas para que o progra-mador possa representar a concorrência, definindo quais partes do código serão executadassequencialmente e quais serão paralelas. As construções para definir, ativar e encerrar a exe-cução de tarefas concorrentes são o foco da tecnologia a ser tratada nesta monografia.
Capítulo 4
Grand Cental Dispatch
O nome faz referência ao Grand Central Terminal, um importante terminal ferroviário emetroviário localizado em Manhattan, Nova Iorque, por onde milhares de pessoas circulam.Grand Central Dispatch ou GCD é um sistema de gerenciamento de pools de threads em nívelde sistema operacional, desenvolvido pela Apple e lançado junto ao MAC OS X 10.6 SnowLeopard. A idéia é combinar um modelo fácil de usar com melhor aproveitamento dos recursosde hardware disponíveis, para isso o GCD transfere a responsabilidade do gerenciamentointeligente de threads para o sistema operacional. As vantagens, ao fazer uso desta tecnologia,são muito relevantes.
Mesmo a aplicação mais bem escrita pode não ter o melhor desempenho possível, poispara obter tal desempenho é necessário ter pleno conhecimento sobre tudo o que acontece nosistema em tempo de execução. E desse princípio vem o diferencial do GCD, pois é muito maissimples para o programador escrever seus aplicativos sem se preocupar com a disponibilidadedos recursos no momento da execução. Os blocos de tarefas serão colocados em filas deexecução e gerenciados pelo sistema operacional que tem controle total sobre os eventos dosistema. Sendo assim, o desenvolvedor de software só precisa escrever código compatível como GCD, tentando paralelizar ao máximo seu código, para tirar o máximo proveito dos núcleose processadores múltiplos, e confiar no sistema operacional para fazer a melhor distribuiçãodas tarefas entre os processadores disponíveis.
A Apple disponibilizou os códigos da biblioteca da API de espaço de usuário (libdispatch)
14 Grand Cental Dispatch
e das alterações realizadas no kernel XNU (o kernel de código aberto da Apple comum aoDarwin e ao OS X), sob os termos de Apache License, versão 2.0. Porém o GCD tambémdepende de uma extensão da linguagem para fazer uso dos blocks (estrutura que será abordadamais adiante). O fato de que GCD é uma biblioteca C significa que ele pode ser usado portodos os derivados da linguagem C suportados no SO: Objective-C, C++ e Objective-C++.Apesar disso o suporte à extensão no compilador é um pré-requisito para os desenvolvedoresde aplicativos que queiram tirar proveito do GCD.
O GCD é semelhante a outras tecnologias, como OpenMP ou ao TBB da Intel. E astrês trabalham com certo tipo de abstração à criação de threads, permitindo com isso que odesenvolvedor defina partes do código como "tarefas"a serem paralelizadas de alguma forma.Contudo, o GCD faz uso de "blocos"em vez das diretivas de pré-processador do OpenMP oudos modelos do TBB.
Como dito, o GCD é implementado com um conjunto de extensões da a linguagem C, umanova API e mecanismo de runtime. O GCD permite programar várias unidades de trabalhousando as seguintes quatro abstrações:
· Block objects;
· Dispatch queues;
· Synchronization;
· Event sources.
4.1 Block Objects
Block Objects (informalmente, “blocos”) é uma extensão da linguagem C, assim comoObjective-C e C++, que torna mais fácil para os programadores a definição de unidadesindependentes de trabalho. Esses blocos são semelhantes a ponteiros de funções tradicionais,mas com algumas características de objeto. As principais diferenças que distingue blocos deponteiros de funções apresentam-se a seguir:
4.2 Dispatch queues 15
· Os blocos podem ser definidos em linha, como “funções anônimas”;
· Os blocos fazem cópias das variáveis do escopo pai com permissão somente para leitura,similar as closures em outras linguagens.
Esse tipo de funcionalidade é comum em linguagens interpretadas, dinamicamente tipadas,mas não o era para programadores C. A Apple publicou as especificações de blocos e suasimplementações em código aberto sob a licença MIT, adicionou suporte a blocos através doprojeto compiler-rt, GCC 4.2 e clang, e apresentou suas considerações como parte da próximaversão da linguagem C. [7]
4.1.1 Sintaxe
Uma variável block assemelha-se a um ponteiro para função, exceto pelo uso de acentocircunflexo em vez de um asterisco.
void (^meuBloco)(void);
A variável resultante pode ser instanciada, atribuindo-a um bloco literal com a mesmaassinatura (argumentos e tipos de retorno).
meuBloco = ^(void){ printf("hello world\n"); };
Esta variável pode ser invocada como um ponteiro de função:
meuBloco(); // imprime "hello world\n"
4.2 Dispatch queues
Dispatch queues (filas de despacho) é a uma das principais abstrações do GCD, pois é atra-vés das filas que os desenvolvedores programam as unidades de trabalho para serem executadasde forma concorrente ou serial, com a vantagem de ser muito fácil de utilizar, acrescido da
16 Grand Cental Dispatch
promessa de maior eficiência. Dispatch queues pode ser usado em todas as tarefas que sãoexecutadas em threads diferentes.
O Dispatch queues é a estrutura que serve de interface entre a aplicação e o mecanismode execução. E as Tarefas (unidades independentes de trabalho) são incluídas e retiradasdas filas com operações atômicas que garantem a confiabilidade dos dados. Assim sendo,dispatch queues é um caminho fácil para executar tarefas de forma concorrente ou serial numaaplicação, e todos os tipos de Dispatch queues são estruturas first-in, first-out (FIFO). Destaforma, o disparo da execução de uma tarefa na fila respeita a ordem em que foi adicionada.O GCD já fornece alguns tipos de dispatch queues pré-definidas, mas outros tipos podemser criadas pelo próprio programador para propósitos específicos. Vamos ver os tipos de filadispatch fornecidas pelo GCD e os respectivos funcionamentos.
Serial queue (Fila serial) ou fila privada é geralmente usado para controlar o acesso arecursos específicos tal qual “regiões críticas”. Cada serial queue tem suas tarefas executadasuma de cada vez e em ordem como já mencionado acima, mas a execução de tarefas em serialqueues distintos podem ser concorrentes.
Concurrent queue (Fila de concorrência), ou global queue, tem suas tarefas executadassimultaneamente em quantidade variada que depende da disponibilidade dos recursos do sis-tema. A execução dessas tarefas ocorre em threads distintas, gerenciadas pelo dispatch queue.O GCD fornece três filas de concorrência ao aplicativo, e se diferem apenas pela prioridade.O programador não pode criar novas filas de concorrência.
Main dispatch queue (Fila principal) se trata da fila serial que tem a execução de suastarefas na thread principal do aplicativo, frequentemente utilizada como ponto chave parasincronização das tarefas.
4.3 Synchronization
Quatro mecanismos primários são fornecidos pelo Grand Central Dispatch para melhorcontrole da finalização das tarefas assíncronas, que são aquelas em que uma não depende documprimento de execusão da outra.
4.3 Synchronization 17
· Synchronous Dispatch - Quando algumas instruções precisam aguardar o término daexecução de um bloco, antes que sejam executadas, a forma mais simples de fazer isso éadicionar o bloco na fila de maneira que as instruções seguintes aguardem a conclusãodeste bloco:
dispatch_sync(uma_fila, ^{ espere_por_mim(); });
Todavia, esse recurso requer atenção do processo pai, que fica parado aguardando atéque o bloco chamado finalize sua execução.
· Groups - Outra forma fácil, e muito útil, de acompanhar a conclusão de blocos é o usoda barreira de sincronização Groups. As execuções de vários blocos de tarefas ligadasa um certo grupo, independente das filas utilizadas, permite fácil controle da conclusãode todas as tarefas do grupo sem que o processo pai tenha que ficar parado aguardandoaté que os blocos finalizem suas execuções.
dispatch_group_t meu_grupo = dispatch_group_create();
dispatch_group_async(meu_grupo, fila_a, ^{ uma_tarefa(); });
dispatch_group_async(meu_grupo, fila_b, ^{ outra_tarefa(); });
dispatch_group_notify(meu_grupo, outra_fila, ^{
// este bloco é executado assim que
// as tarefas do grupo terminarem
faca_isto_quando_tudo_terminar();
});
dispatch_release(meu_grupo);
// continua o trabalho sem esperar pelas tarefas do grupo
· Semaphores. Além das ferramentas já citadas, para controle de acesso a seções críticase sincronização de tarefas, GCD também tem seu próprio semáforo. O uso é similarao do semáforo já conhecido na linguagem C, mas como outras ferramentas do GCD, osemáforo dispatch não precisa fazer chamadas ao kernel.
18 Grand Cental Dispatch
4.4 Event sources
O Grand Central Dispatch também fornece uma ferramenta que permite agendar a execu-ção de tarefas. Quando o aplicativo tem que interagir com sistemas subjacentes, o programadordeve prepará-lo para o caso da tarefa levar uma quantidade de tempo não trivial, pois esse tipode interação envolve uma mudança de contexto que é razoavelmente cara em comparação achamadas dentro do próprio processo. Por esse motivo, muitas bibliotecas fornecem interfacesassíncronas para permitir que o código submeta as requisições para o sistema e prossiga comoutras tarefas enquanto a requisição é processada.
O GCD usufrui desse comportamento permitindo que o código obtenha os resultados desuas requisições usando blocos e filas dispatch, substituindo as funções assíncronas normal-mente usadas para tratar os eventos do sistema. Ao configurar um dispatch source, especifi-camos o evento que queremos monitorar, bloco e a fila dispatch que queremos para processareste evento. Os blocos podem ser relacionados a event souces como timers, signals, sockets,file descriptors, process state changes e outros. Exemplo de source timer :
dispatch_queue_t global_queue;
global_queue = dispatch_get_global_queue(
DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);
dispatch_source_t src_timer;
src_timer = dispatch_source_create(
DISPATCH_SOURCE_TYPE_TIMER, 0, 0,
global_queue );
dispatch_source_set_timer(src_timer, 0, DURACAO, 0);
dispatch_source_set_event_handler(src_timer, ^{
printf("Event source\n");
});
dispatch_resume(src_timer);
4.5 Leitura e construção do código 19
4.5 Leitura e construção do código
Com o uso da tecnologia Grand Central Dispatch, torna-se bem menos arduo transformarimplementações seriais de tarefas independentes em implementações paralelizadas. Os “blocos”têm grande participação nesse tipo de tarefa: ao identificar um trecho de código que poderiaser executado assincronamente, movemos esse trecho para um bloco e disparamos sua execuçãoassíncona, sem o acrescimo de muitas linhas de código e sem muitas modificações na estruturado código já existente.
A clareza, legibilidade dos códigos e até facilidade de distribuição das tarefas são pontosmuito favoráveis ao GCD. No apêndice A.1 e A.2 podemos observar códigos de um dos testesexecutados, e vemos algumas diferenças entre o GCD e a programação direta com threads. Nocódigo que utiliza o GCD, o tratamento da concorrência fica encapsulado, enquanto que nouso manual de threads o disparo e sincronização manual dos threads deixa o código poluído,pois mistura instruções feitas em diferentes níveis de abstração (realização da tarefa e códigode sincronização).
Para dar um exemplo da simplicidade de implementar tarefas paralelas e concorrentes,podemos observar no apêndice B.1 o código de uma pequena aplicação que simula um callcenter. Processos “atendentes” e processos “clientes” executando paralelamente, e concorrendoa recursos do aplicativo, como entrar na fila de atendimento e atender o primeiro cliente da fila.Podemos observar que o controle de exclusão mútua e disparo das tarefas são bem simples.
20 Grand Cental Dispatch
Capítulo 5
Atividades realizadas
5.1 Explorando as funcionalidades
O Grand Central Dispatch é uma tecnologia bem recente com poucas fontes de documen-tação. Por esse motivo, suas funcionalidades foram testadas de diversas formas para que seuuso fosse bem entendido. Dessa forma, os benefícios que o GCD trouxe puderam ser melhorexplorados.
A máquina usada nos testes foi um MacBook white com processador Intel Core 2 Duo2.26GHz, 2GB de memória rodando MAC OS X 10.6.5, e não houve problema algum aodeixar a máquina preparada para programação com a biblioteca libdispatch. O computadorveio de fábrica com a versão Snow Leopard do MAC OS X, que contém suporte nativo aoGCD, e foi necessário instalar apenas o pacote de programação Xcode, para que o computadorficasse apto a compilar e executar os programas que fazem uso da biblioteca libdispatch e dosblocos.
A primeira ferramenta a ser examinada foi o Block Object, e esse exame teve início nasvariações de sua sintaxe, bem como variáveis de acesso ao escopo pai, suas variáveis de escopolocal, e execução de suas operações. A partir disso uma abordagem do uso de blocos pôde serfeita. Em seguida, foi a vez das ferramentas de sincronização e bloqueio. Tarefas com tempode funcionamento variado permitiram examinar ferramentas de sincronização, concorrênciasentre as tarefas e acesso exclusivo a regiões críticas.
22 Atividades realizadas
5.2 Testes de desempenho e Resultados obtidos
Após analisar as facilidades e utilidades abordadas pelas ferramentas disponíveis do GrandCentral Dispatch, partimos para a avaliação do desempenho das aplicações constituídas coma tecnologia.
O GCD foi feito pela Apple, que é uma empresa privada com fins lucrativos, por essemotivo a maioria das publicações que falam sobre o GCD são da própria Apple, com muitaspropagandas prometendo melhor desempenho dos aplicativos, aproveitamento máximo dosnúcleos ou dos processadores, tudo respaldado pela facilidade de uso. Segundo a própria Apple,o overhead gerado com a criação manual de inúmeros threads é evitado no GCD, pois as tarefasaguardam a disponibilidade de processadores lógicos para serem executadas. As instruçõesde encapsulamento de tarefas são curtas, portanto eficientes; incluir ou remover tarefas dasfilas são operações atômicas disponíveis no hardware, o que assegura a confiabilidade dosdados e a rapidez da operação, portanto, os testes feitos visavam verificar as reais vantagense desvantagens do GCD como ferramenta usada pelos programadores para paralelizar seuscódigos e criar eficientes aplicativos. O objetivo desses testes é fazer uma comparação entreo desempenho dos aplicativos constituidos com as ferramentas do Grand Central Dispatch ecom com uso manual de threads.
Os testes foram feitos com aplicativos que têm seu trabalho facilmente paralelizável, paranão haver dúvidas quanto a qualidade da divisão de tarefas escolhida.
5.2.1 Tarefas crescentes
Nos primeiros testes, implementamos um algoritmo para o cálculo do produto de matrizesquadradas por se tratar da escolha mais natural e intuitiva. Cada linha da matriz resultantedo produto foi gerada por uma tarefa independente, e matrizes do tipo double foram geradasdinamicamente com entradas adquiridas de uma função que gerava números aleatórios.
No estudo das ferramentas do GCD, focamos em duas formas de disparar várias tarefasem paralelo e aguardar a conclusão das mesmas, usando a chamada dispatch_apply() e dis-patch_group_async(). Esse foco duplo é devido à observação de comportamentos distintos
5.2 Testes de desempenho e Resultados obtidos 23
entre as duas chamadas. Ao fazer uso da chamada dispatch_apply(), para várias tarefas con-tendo um “sleep(aleatório)”, o sistema permitia somente duas tarefas em execução por vez,provavelmente por estar sendo executado em um computador com dois núcleos. Já com o usoda chamada dispatch_group_async() todas as tarefas foram disparadas.
Cada ferramenta foi executada inúmeras vezes, ou seja, produto de matrizes de mesmadimensão foram executadas várias vezes para cada ferramenta. Observe os resultados compa-rativos:
Figura 5.1: Gráfico dos resultados
24 Atividades realizadas
Figura 5.2: Resultados obtidos
Os resultados do teste de desempenho não mostraram vantagem do GCD sobre o usomanual de threads. Inclusive o aplicativo que usa os threads diretamente começou com umaumento no desvio padrão e seu tempo médio de execução não acompanhou o tamanho dotrabalho a ser realizado, deixando o GCD em desvantagem. Resultados semelhantes foramobtidos ao aplicar testes no problema de encontrar números primos, em que cada tarefa inde-pendente procurava primos num intervalo distinto, mas de mesmo tamanho.
Observe que esses problemas tinham uma característica comum. No produto de matrizes,o tamanho de cada unidade de trabalho dependia da dimensão da matriz, pois o tamanho dalinha é proporcional a dimensão da matriz. Na busca por números primos, o tamanho dasunidades de trabalho também crescem acompanhando o escopo, pois quanto mais distante umnúmero está de 1, maior é o número de comparações que a tarefa deve executar.
5.2.2 Tarefas curtas
O GCD é um forte incentivo para que programadores compartilhem ao máximo o trabalhoa ser realizado por seus aplicativos em tarefas menores, obtendo o melhor desempenho nosfuturos processadores com número expressivo de núcleos. Mas como é o desempenho dessesaplicativos nos processadores usados atualmente?
Resolvemos testar o desempenho dos aplicativos com esse tipo de característica. Teríamos,
5.2 Testes de desempenho e Resultados obtidos 25
dessa forma, um grande número de tarefas curtas a serem executadas nos aplicativos. O testeque realizamos foi reproduzido com tarefas que executavam um número fixo de operações desoma e produtos de números “reais” gerados aleatoriamente. Assim, o tamanho de cada tarefanão tem relação com o número de tarefas. Observe os resultados do desempenho das aplicaçõescom essa característica:
Figura 5.3: Gráfico dos resultados
26 Atividades realizadas
Figura 5.4: Resultados obtidos
Aqui podemos observar o crescimento mais comportado do aplicativo escrito com a ferra-menta estudada. Enquanto o uso manual de threads certamente paga um preço mais caro pordisparar muitos threads simultâneos.
5.2.3 Divisão do trabalho
Muitas vezes, temos que conhecer o hardware em que o software será rodado para escrevê-lode maneira a obter o melhor desempenho possível. Entretanto, sabemos que não é uma tarefafácil escrever o software pensando o tempo todo em como se dará o comportamento do mesmoem um hardware específico. E ainda podemos perder em desempenho ao rodar o aplicativoem hardware diferente. O GCD promete ser uma arma muito poderosa para a solução dessetipo de problema, pois a administração dos threads, por conta do sistema operacional, permiteprogramar sem se preocupar com a disponibilidade dos recursos. Nosso objetivo nesse testefoi verificar essa afirmação.
No teste anterior foi possível observar certa vantagem do GCD com inúmeras tarefas, poisa grande quantidade de tarefas de tamanho fixo nos deu indícios fortes de que o uso manual deThread pode ter desempenho menor que o GCD com overhead muito grande. Nesse novo teste,o trabalho total a ser realizado pelo aplicativo não muda de tamanho. Então, foi estudadoo desempenho das tecnologias ao dividir o trabalho a ser realizado pelo aplicativo em tarefascada vez menores para analisar o quanto perdemos em desempenho ao criar mais unidades detrabalho, mantendo o trabalho total para deixar mais clara essa diferença.
5.2 Testes de desempenho e Resultados obtidos 27
Criamos duas matrizes quadradas do tipo double de ordem 512. Para calcular uma matrizresultante do produto dessas duas matrizes são necessários 5122 produtos de vetores. Então ototal desses produtos foram distribuídos entre 2 tarefas, depois 23, 25, 27, 28, 29, 211, 213, 214,215 tarefas. Observe os resultados:
Figura 5.5: Gráfico dos resultados
Para melhor visualização no gráfico, só é mostrado até 215 tarefas, mas podemos observara tabela de valores e verificar que mesmo com uma distribuição muito grande o GCD nãoaumenta segnificativamente seu tempo de execução.
28 Atividades realizadas
Figura 5.6: Resultados obtidos
Capítulo 6
Conclusões
Nos testes que fizemos os aplicativos implementados com uso da tecnologia fornecida peloGrand Central Dispatch obtiveram resultados favoráveis na divisão do trabalho total a serrealizado por várias outras tarefas menores. O seu mecanismo de gerenciamento de threadsnão mostrou vantagem quando o trabalho a ser realizado por uma tarefa independente crescebastante. Mas podemos verificar que em todos os testes o GCD obteve menor desvio padrão,mostrando-se mais estável em suas execuções; e embora o GCD não resolva o problema dedecidir quais as partes do trabalho podem ser realizadas em paralelo, o que ainda é umproblema difícil, quando o programador resolve essa etapa, a participação do GCD traz muitosbenefícios ao restante do trabalho.
É importante reforçar, que o processamento paralelo permite uma grande economia deenergia e consequentemente a diminuição da quantidade de calor liberado. Essa diminuiçãono consumo de energia e liberação de calor aumenta a vida útil dos componentes, permite aexistência de notebooks robustos com baterias de longa duração, e ajuda a solucionar proble-mas de aquecimento nas centrais de processamento de dados etc. Todas essas vantagens noslevam a crer que o futuro dos processadores será com números muito grandes de núcleos comclocks não tão elevados.
Nesse contexto, o Grand Central Dispatch se mostra uma tecnologia realmente preparadapara o futuro, pois mesmo que os computadores de hoje ainda possuam poucos núcleos, osprogramas construídos com essa tecnologia hoje já têm um bom desempenho, e não terão
30 Conclusões
que ser reescritos para obter melhor desempenho nos futuros processadores com centenas oumilhares de núcleos. E por se tratar de uma tecnologia disponibilizada à comunidade desoftware livre, as possibilidades de propagação de seu uso e possíveis aperfeiçoamentos nosfazem acreditar no sucesso da tecnologia.
Parte II
Parte subjetiva
Capítulo 7
Experiência pessoal
Quando ingressei na universidade, no curso de licenciatura em matemática, após cursarIntrodução à computação e lecionar aulas particulares de matemática, descobri, já no primeiroano que seria na computação que eu aplicaria a matemática da forma que mais gosto. Dessaforma, meu primeiro desafio acadêmico, foi conseguir transferência para a computação. Apósdecidir fazer a transferência, tive que aguardar mais de um ano para conseguir, buscandocursar todas as disciplinas exigidas e manter a média ponderada acima do mínimo, tambémexigido para transferência.
Ao longo do curso percebi que ter boa familiaridade com o inglês é muito importante naformação de um Bacharel em Ciência da computação, mas foi neste trabalho que o inglês semostrou, para mim, um grande desafio que eu me propus a vencer. No mundo da tecnologia,qualquer novidade será apresentada ao mundo primeiro na língua inglesa, e como o assuntoestudado neste trabalho é uma tecnologia nova, não ouve a opção de buscar por material emportuguês para auxiliar o estudo.
Um grande desafio neste trabalho foi a liberdade. Uma tecnologia nova, que levou-nos adecidir por qual abordagem escolher bem como a maneira pela qual trata-la. A falta de práticacom pesquisa e confecção de texto acadêmico também foram dificuldades encontradas. Tiveque aprender novos conceitos e não havia muitas fontes de informação a respeito da tecnologiaestudada.
34 Experiência pessoal
A frustração que tenho, é de não ter testado o Grand Central Dispatch em outras pla-taformas, avaliar as dificuldades de instalação, comparação de desempenho e apresentar essaexperiência neste trabalho. Sei que o FreeBSD foi o pioneiro, das plataformas open source,a implementar a tecnologia. O linux também está se movimentando a respeito, o Debiantambém tem testado implementações da tecnologia.
7.1 Estudos futuros
Para futuros estudos seria interessante testar a tecnologia em computadores com 4, 6 oumais núcleos. Limitação de recursos e tempo me impediram de fazer tais testes. Dessa formateremos informações mais precisas, com relação ao desempenho e mais dúvidas esclarecidas,como a limitação de disparos da ferramenta dispatch_apply().
Com a disseminação da tecnologia, outras plataformas terão implementações estáveis damesma. Sendo assim, experimentos devem ser feitos nessas plataformas e as diferenças, seme-lhanças, facilidades e dificuldades apuradas e documentadas.
7.2 Disciplinas relevantes
MAC0110 — Introdução à computação O contato com os conceitos lógicos e aplicaçãoda lógica matemática foram motivadores e essenciais para dar sequência ao minha for-mação.
MAC0323 — Estruturas de Dados Essa disciplina me mostrou a computação sob umpanorama diferente. As diferentes estruturas lógicas e a eficiência no tratamento dosdados esteve muito presente no curso.
MAC0338 — Análise de Algoritmos Nessa disciplina, em que aprendemos a analisar acomplexidade dos softwares, vimos a maneira correta e eficiente de implementar algo-ritmos “gulosos”. Aprendemos que soluções “ingênua” podem ser muito ruins, e comomelhora-las.
MAC0412 — Organização de Computadores Saber o comportamento do hardware esuas limitações trás muitos benefícos no desenvolvimento de software, principalmente
7.2 Disciplinas relevantes 35
na programação de alto desempenho. Em Organização de Computadores pude entendermelhor o funcionamento da máquina para aproveitar melhor seus recursos.
MAC0438 — Programação Concorrente Certamente umas das disciplinas mais intere-santes e importantes na minha formação. Desde de os estudos aos testes, este trabalhome exigiu bastante os conhecimentos que obtive nessa disciplina. Hoje vivemos vivemosa ascenção dos processadores multicore, e conhecer esses conceitos é estar um passo afrente.
MAC0342 — Laboratório de Programação Extrema A experiencia adquirida nessa dis-ciplina é de grande valia a um profissional da area de desenvolvimento de software. Osprincípios e valores dos métodos ágeis, técnicas de refatoração, acompanhamento doprocesso de desenvolvimento, desenvolvimento dirigido por testes, tudo isso proporci-ona ao estudante aprender na prática, contribuindo com soluções de um problema reale envolvendo-se com pessoas e ideias trocadas ao longo do semestre. Deveria ser umdisciplina obrigatória.
36 Experiência pessoal
Referências Bibliográficas
[1] ANDREWS, G. R., Schineider, F. B., Concepts and Notations for Concurrent Program-ming, ACM Computing Survey, v. 15, no.1, pp. 3-43,1983. 11
[2] Computação Paralela - USP - São Carlos - R.H.C. Santana, M.J. Santana, M.A. Souza,P.S.L. Souza, A.E.T. Piekarski
[3] http://arstechnica.com/apple/reviews/2009/08/mac-os-x-10-6.ars/12 4
[4] http://libdispatch.macosforge.org/
[5] http://lwn.net/Articles/352978/
[6] http://developer.apple.com/technologies/mac/snowleopard/gcd.html
[7] http://developer.apple.com/library/mac/#featuredarticles/BlocksGCD/index.html 15
[8] http://developer.apple.com/ GCD /Reference/reference.html
[9] http://en.wikipedia.org/wiki/Moore’s_law 3
[10] www.top500.org 3
[11] http://en.wikipedia.org/wiki/Very-large-scale_integration 6
[12] ALMASI, G. S., Gottlieb A., Highly Parallel Computing, 2a. ed., The Benjamin Cum-mings Publishing Company, Inc., 1994. 9
[13] QUINN, M.J., Designing Efficient Algorithms for Parallel Computers, McGraw Hill, 1987.9
38 REFERÊNCIAS BIBLIOGRÁFICAS
[14] HWANG, K., Briggs, F. A., Computer Architecture and Parallel Processing, McGraw-HillInternational Editions, 1984. 9
Apêndice A
Códigos de comparação
1 #include <dispatch/dispatch.h>
2 #include "matrix.h"
3
4 int main(int argc, char *argv[]) {
5 dispatch_queue_t globalQueue;
6 globalQueue = dispatch_get_global_queue (
7 DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);
8 initialize(argc, argv);
9
10 dispatch_apply(dimension, globalQueue, ^(size_t line) {
11 int column;
12 for (column = 0; column < dimension; column ++) {
13 matrixProduct[line][column] =
14 scalar_product(matrixA[line], matrixB[column]);
15 }
16 });
17 return 0;
18 }
Código A.1: Código usando Apply por linha da matriz
40 Códigos de comparação
1 #include <pthread.h>
2 #include "matrix.h"
3
4 void *thread_func(void *argument) {
5 int line, column;
6 line = *((int *) argument);
7 for (column = 0; column < dimension; column++)
8 matrixProduct[line][column] =
9 scalar_product(matrixA[line], matrixB[column]);
10 return NULL;
11 }
12 int main(int argc, char *argv[]){
13 int i, *indice;
14 pthread_t *threads;
15
16 initialize(argc, argv);
17 indice = (int *) malloc (dimension * sizeof(int));
18 threads = (pthread_t *)malloc(dimension*sizeof(pthread_t));
19
20 for(i = 0; i < dimension; i++){
21 indice[i] = i;
22 pthread_create(&(threads[i]), NULL, thread_func,
23 &(indice[i]));
24 }
25 for(i = 0; i < dimension; i++)
26 pthread_join(threads[i], NULL);
27 return 0;
28 }
Código A.2: Código usando Thread por linha da matriz
Apêndice B
Código de implementação de concorrência
1 #include <stdio.h>
2 #include <time.h>
3 #include <stdlib.h>
4 #include <dispatch/dispatch.h>
5
6 #define MAX_CLIENTES 1000
7 #define MAX_ALEATORIO 5
8 #define VAZIO -1
9 #define PERIODOdeEXECUCAO 30
10
11 typedef dispatch_group_t Grupo;
12
13 bool esperando[MAX_CLIENTES];
14 int filaDeClientes[MAX_CLIENTES];
15
16 dispatch_queue_t lockQueue;
17
18 int n, m; /* numero de processos */
19 int cabeca, clientesNaFila;
20 bool terminar = false;
42 Código de implementação de concorrência
21 void inicializa(int argc, char *argv[]);
22
23 void despachaTarefas(Grupo clienteGrp, Grupo atendenteGrp);
24
25 int aleatorio();
26
27 void entraNaFila(int idCliente);
28
29 int atendeCliente();
30
31 void Atendente(int id);
32
33 void Cliente(int id);
34
35 void mandaTerminar(Grupo clienteGrp, Grupo atendenteGrp);
36
37 int main(int argc, char *argv[]) {
38 Grupo clienteGrp, atendenteGrp;
39
40 inicializa(argc, argv);
41
42 clienteGrp = dispatch_group_create();
43 atendenteGrp = dispatch_group_create();
44
45 despachaTarefas(clienteGrp, atendenteGrp);
46
47 sleep(PERIODOdeEXECUCAO);
48 mandaTerminar(clienteGrp, atendenteGrp);
49 return 0;
50 }
43
51 void inicializa(int argc, char *argv[]){
52 srand (time(NULL));
53 n = atoi(argv[1]);
54 m = atoi(argv[2]);
55 cabeca = clientesNaFila = 0;
56 lockQueue = dispatch_queue_create("secao.critica", NULL);
57 }
58 /* Devolve valor aleatorio entre 0 e MAX_ALEATORIO */
59 int aleatorio(){
60 return (int)(rand()/RAND_MAX) * MAX_ALEATORIO;
61 }
62
63 void despachaTarefas(Grupo clienteGrp, Grupo atendenteGrp){
64 int i;
65 dispatch_queue_t globalQueue;
66
67 globalQueue = dispatch_get_global_queue (
68 DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);
69 for (i = 0; i < n; i++) {
70 dispatch_group_async(clienteGrp, globalQueue, ^{
71 Cliente(i);
72 });
73 }
74
75 for (i = 0; i < m; i++) {
76 dispatch_group_async(atendenteGrp, globalQueue, ^{
77 Atendente(i);
78 });
79 }
80 }
44 Código de implementação de concorrência
81 /* Processo Cliente */
82 void Cliente(int id){
83 while (! terminar) {
84 sleep(aleatorio());
85 dispatch_sync(lockQueue, ^{
86 entraNaFila(id);
87 });
88 printf("Cliente %d esperando\n", id);
89 while (esperando[id])
90 sleep(1);
91 printf("Cliente %d atendido\n", id);
92 }
93 }
94 /* Processo Atendente */
95 void Atendente(int id) {
96 __block int idCliente;
97 while (! terminar) {
98 dispatch_sync(lockQueue, ^{
99 idCliente = atendeCliente();
100 });
101 if (idCliente != VAZIO){
102 /* Atendeu o cliente: idCliente */
103 sleep(aleatorio());
104 esperando[idCliente] = false;
105 /* Atendimento finalizado */
106 }
107 else
108 sleep(aleatorio());
109 }
110 }
45
111 void entraNaFila(int idCliente){
112 filaDeClientes[cabeca + clientesNaFila] = idCliente;
113 esperando[idCliente] = true;
114 clientesNaFila++;
115 }
116
117 int atendeCliente(){
118 int idCliente;
119 if (clientesNaFila < 1)
120 return VAZIO;
121 idCliente = filaDeClientes[cabeca];
122 cabeca = (cabeca + 1) % n;
123 clientesNaFila--;
124 return idCliente;
125 }
126
127 void mandaTerminar(Grupo clienteGrp, Grupo atendenteGrp){
128 terminar = true;
129 dispatch_group_wait(clienteGrp, DISPATCH_TIME_FOREVER);
130 dispatch_group_wait(atendenteGrp, DISPATCH_TIME_FOREVER);
131 }
Código B.1: Concorrência no CallCenter
