dissertacao - algoritmos para simulador de arquiteturas paralelas
DESCRIPTION
TRANSCRIPT
LUIZ ARTHUR FEITOSA DOS SANTOS
Desenvolvimento de Algoritmos Paralelos para Simulador de Multiprocessadores Superescalares
MARINGÁ
2005
LUIZ ARTHUR FEITOSA DOS SANTOS
Desenvolvimento de Algoritmos Paralelos para Simulador de Multiprocessadores Superescalares
Dissertação apresentada ao Programa de Pós-Graduação em Ciência da Computação da Universidade Estadual de Maringá, como requisito parcial para obtenção do grau de Mestre em Ciência da Computação. Orientador: Prof. Dr. João Angelo Martini
MARINGÁ
2005
LUIZ ARTHUR FEITOSA DOS SANTOS
Desenvolvimento de Algoritmos Paralelos para Simulador de Multiprocessadores Superescalares
Dissertação apresentada ao Programa de Pós-Graduação em Ciência da Computação da Universidade Estadual de Maringá, como requisito parcial para obtenção do grau de Mestre em Ciência da Computação.
Aprovado em
BANCA EXAMINADORA
Prof. Dr. João Angelo Martini Universidade Estadual de Maringá – UEM
Prof. Dr. Ronaldo A. L. Gonçalves Universidade Estadual de Maringá – UEM
Profa. Drª. Roberta Spolon Ulson Departamento de Computação – UNESP
DEDICATÓRIA
Dedico este trabalho
Aos meus pais, a minha namorada, aos meus amigos e principalmente a Deus.
AGRADECIMENTOS
Agradeço inicialmente aos meus pais Wanderley Feitosa dos Santos e Enezita
M. Verderio dos Santos, que me deram todo o apoio necessário para conclusão de mais esta
etapa da minha vida, e principalmente porque são fontes inesgotáveis de inspiração para mim.
Agradeço ao meu orientador João Angelo Martini, pelos conselhos
profissionais, amizade e pelo conhecimento compartilhado.
Agradeço à minha amada namorada Keula Massuda, por todo apoio que está
me deu nos momentos fácies e principalmente nos difíceis, demonstrando todo seu carinho e
consideração.
Agradeço aos meus amigos Ricardo Alexandre Lavarias, Edson Jose
Tomiazzi “Kitio”, Igor Wiese, Rogério Pozza, André Pozza, Edson Alves de Oliveira
Junior, Aysllan Possebom, Jeber Gonzaga e Leila Massuda, pela amizade e contribuições.
Agradeço a todos os professores que compartilharam conhecimento e me
ajudaram a concluir este trabalho, dentre eles: Ronaldo A. L. Gonçalves, Elisa Hatsue M.
Huzita, Itana M. S. Gimenes, Ademir Aparecido Constantino, Munif Gebara Junior,
Claudete Werner, Daniela Flor, Yandre Maldonato e Roni Fancis Shigueta.
Agradeço ao Departamento de Informática, principalmente à Maria Inês
Davanço, por toda atenção, respeito, paciência e amizade.
“Penso noventa e nove vezes e nada descubro deixo de pensar, mergulho em profundo silêncio e eis que a verdade se revela.”
Albert Einstein
RESUMO
A necessidade de resolver problemas intensivamente computacionais vem exigindo
arquiteturas computacionais com desempenhos cada vez mais elevados. Para atender essa
demanda, esforços de pesquisa têm sido desenvolvidos na área de arquiteturas paralelas. Para
se obter resultados satisfatórios com arquiteturas paralelas são necessários estudos
meticulosos de hardware e software. Uma alternativa de apoio a pesquisas em arquiteturas
paralelas é o uso de simuladores. Neste contexto, diversos grupos de pesquisa têm
desenvolvido simuladores de arquiteturas paralelas. O grupo de pesquisa em Arquiteturas de
Alto Desempenho da Universidade Estadual de Maringá desenvolveu uma ferramenta de
simulação denominada Simulador de Multiprocessadores Superescalares. Entretanto somente
essa ferramenta de simulação não permite investigar arquiteturas, é necessário também o uso
de algoritmos desenvolvidos especificamente para este simulador. Assim, este trabalho tem
por objetivo o desenvolvimento de algoritmos paralelos a serem utilizados em conjunto com o
Simulador de Multiprocessadores Superescalares, fornecendo assim meios de simular e
avaliar uma arquitetura paralela. Tais algoritmos visam testar e explorar os diversos aspectos
de uma arquitetura paralela. Viabilizando o estudo de arquiteturas paralelas em uma variedade
de configurações de arquiteturas fornecidas pelo simulador, possibilitando também que a
ferramenta seja usada como apoio ao ensino de arquiteturas paralelas. Após o
desenvolvimento dos algoritmos para simulação no SMS, ficou constatado que os algoritmos
em conjunto com a ferramenta de simulação proporcionam um ambiente ideal para o estudo e
experimentação de arquiteturas paralelas.
Palavras-chave:Arquitetura de Computadores. Computação Paralela. Simulação. Algoritmos.
ABSTRACT
The need for solving problems intensively related to computers has been demanding computer
architectures more and more developed. To attend this demand research efforts have been
developing the parallel architecture area. To obtain better results with them, it’s necessary
some, searches on meticulous. hardware and software
An alternative to support those search on parallel architectures is the use of simulators. On
this context, some research groups have been developing parallel architectures simulators.
The high development architectures from Universidade Estadual de Maringá developed a
simulator tool called Superscalar Multiprocessors Simulator. However only this simulator tool
isn’t able to investigate architectures, it’s also necessary the use of algorithms specifically
develop for that simulator. This way, this paper has main goal the development of parallel
algorithms to be used along with the Superscalar Multiprocessor Simulator offering
conditions to simulate and evaluate a parallel architecture. Those algorithms aim to test and
explore the diverse aspects of a parallel architecture. Making the study of parallel
architectures possible in a variety of architecture configuration given by the simulator, also
making possible that the tool be used as a support to the parallel architecture teaching. After
the development of those algorithms for simulation on the SMS, it was proved that the
algorithms along with the simulation tool permit an ideal environment for the parallel
architectures study and experiment.
Keywords: Computer Architectures. Parallel Computation. Simulation. Algorithms.
LISTA DE ILUSTRAÇÕES
Figura 1 - Máquina de von Neumann...........................................................................................18
Figura 2 - (a) Memória compartilhada (b) Memória distribuída..................................................23
Figura 3 - Arquitetura do simulador SMS....................................................................................33
Figura 4 - Inicializando a biblioteca de comunicação do SMS....................................................36
Figura 5 - Usando funções da biblioteca SMS .............................................................................38
Figura 6 - Características dos Speedups de tamanho fixo e tempo fixo.......................................59
Figura 7 - Speedup Absoluto ........................................................................................................60
Figura 8 - Speedup Relativo .........................................................................................................60
Figura 9 - Eficiência .....................................................................................................................62
Figura 10 - Matriz.........................................................................................................................64
Figura 11 - Algoritmo seqüencial para multiplicação de matrizes...............................................65
Figura 12 - Divisão da Matriz em Vetores no Programa Mestre .................................................65
Figura 13 - Multiplicação dos Vetores pelas Colunas da Matriz B nos Processadores
Escravos.............................................................................................................................66
Figura 14 - O programa mestre reagrupa os vetores resultantes dos processos escravos ............66
Figura 15 - Algoritmo paralelo de multiplicação de matrizes......................................................68
Figura 16 - Saída reduzida de uma simulação no SMS................................................................69
Figura 17 - Tempo de execução do algoritmo de multiplicação de matrizes...............................70
Figura 18 - Speedup apresentado pelo algoritmo paralelo de multiplicação de matrizes ............70
Figura 19 - Eficiência apresentada pelo algoritmo paralelo de multiplicação de matrizes ..........71
Figura 20 - Fórmula para calcular o valor de π ...........................................................................73
Figura 21 - Programa escravo do cálculo do π ...........................................................................74
Figura 22 - Speedup do algoritmo paralelo do cálculo do π .......................................................75
Figura 23 - Tempo de execução do algoritmo do cálculo do π ...................................................76
Figura 24 - Eficiência apresentada pelo algoritmo do cálculo do π ............................................76
Figura 25 - Definição de integral de uma função não negativa....................................................77
Figura 26 - Usando integral para definir trapézio ........................................................................78
Figura 27 - Trapézio .....................................................................................................................78
Figura 28 - Código do algoritmo Trapezoidal rule com MPI.......................................................79
Figura 29 - Código do algoritmo Trapezoidal rule com SMS......................................................81
Figura 30 - Tempo total de execução do Trapezoidal rule ..........................................................83
Figura 31 - Speedup Trapezoidal rule..........................................................................................84
Figura 32 - Eficiência do algoritmo Trapezoidal rule frente a arquitetura ..................................84
Figura 33 - Algoritmo de Round-Trip ..........................................................................................86
Figura 34 - Algoritmo Bubble Sort ..............................................................................................88
Figura 35 - Algoritmo de ordenação Odd-Even ...........................................................................89
Figura 36 - Processo de ordenação utilizando algoritmo Odd-even.............................................90
Figura 37 - Ordenação por Odd-Even utilizada no SMS .............................................................91
Figura 38 - Tempo total de execução do Odd-Even sort..............................................................92
Figura 39 - Speedup do Odd-Even sort ........................................................................................93
Figura 40 - Eficiência do Odd-even sort ......................................................................................93
Figura 41 - Uso da rede de interconexão do algoritmo Odd-Even sort........................................94
Figura 42 - Uso da rede de interconexão do algoritmo de cálculo do π .......................................94
Figura 43 - Linha de comando para executar o programa de cálculo do π com cache de dados
de tamanho de 4096...........................................................................................................96
Figura 44 - Speedup do π com alteração de cache de dados ........................................................97
Figura 45 - Eficiência do π com alteração de cache de dados......................................................98
Figura 46 - Linha de comando que dispara o simulador SMS com alterações no previsor de
desvio.................................................................................................................................98
Figura 47 - Speedup e eficiência do algoritmo Trapezoidal rule com previsor de desvio
alterado ..............................................................................................................................99
Figura 48 - Elapsed Time do algoritmo Odd-Even com duas redes de interconexão.................100
LISTA DE TABELAS
Tabela 1 - Simuladores do SimpleScalar......................................................................................27
Tabela 2 - Primitivas SMS para passagem de mensagem ............................................................32
Tabela 3 - Taxa de transferência da rede de interconexão em bytes por segundo........................87
SUMÁRIO
1 INTRODUÇÃO .......................................................................................................... ....15
2 COMPUTAÇÃO PARALELA.......................................................................................17
2.1 Processamento Seqüencial ..............................................................................................17
2.2 Classificação de Flynn .....................................................................................................19
2.3 Processamento Paralelo ..................................................................................................21
2.4 Arquiteturas Paralelas com Memória Compartilhada e Distribuída.........................22
2.4.1 Multiprocessadores com Memória Compartilhada............................................................22
2.4.2 Multiprocessadores com Memória Distribuída .................................................................23
3 SIMULADOR DE ARQUITETURAS ..........................................................................25
3.1 SimpleScalar ....................................................................................................................25
3.2 Simulador de Ambientes Paralelos ................................................................................27
3.3 Algoritmos para testes e avaliação de desempenho ......................................................29
3.4 Simulador de Multiprocessadores Superescalares - SMS ...........................................31
3.5 Biblioteca de Passagem de Mensagem do SMS ............................................................35
4 PROGRAMAÇÃO PARALELA E ALGORITMOS PARALELOS .........................39
4.1 Aplicações Paralelas ........................................................................................................41
4.2 Passagem de Mensagens..................................................................................................52
5 AVALIAÇÃO DE DESEMPENHO ..............................................................................54
5.1 Alguns aspectos quanto a medidas de desempenho......................................................55
5.2 Tempo de execução..........................................................................................................57
5.3 Speedup. ...........................................................................................................................57
5.4 Eficiência. .........................................................................................................................61
6 ALGORITMOS PARALELOS PARA O SMS ............................................................63
6.1 Algoritmo Paralelo de Multiplicação de Matrizes........................................................63
6.2 Algoritmo Paralelo para Cálculo doπ ..........................................................................72
6.3 Algoritmo Trapezoidal Rule ...........................................................................................76
6.4 Algoritmo para testes da Rede de Interconexão do Simulador SMS..........................84
6.5 Algoritmo de ordenação Odd-Even ...............................................................................87
6.6 Simulação de Outras Arquiteturas com o SMS e os Algoritmos ................................94
7 CONCLUSÃO................................................................................................................101
8 TRABALHOS FUTUROS ............................................................................................103
REFERÊNCIAS ............................................................................................................104
ANEXO A .......................................................................................................................108
15
1 INTRODUÇÃO
A motivação principal para investigação, desenvolvimento e utilização de
arquiteturas paralelas fundamenta-se na necessidade de se resolver problemas intensivamente
computacionais. São os chamados “Grand Challenges” (WOODWARD, 1996; CHANG;
EWING, 1999), problemas como previsão de tempo e simulação de dinâmica molecular, que
exigem máquinas com grande capacidade de processamento. Tal poder de processamento
pode ser viabilizado por meio de arquiteturas paralelas. Inicialmente a exploração de
paralelismo se deu em um nível mais baixo, como por exemplo, processadores superescalares
(SMITH, 1995).
Arquiteturas paralelas exploram o paralelismo em um nível mais alto. Neste
modelo o problema a ser resolvido é dividido entre os processadores que compõem a
arquitetura. Idealmente, se um trabalho foi subdivido e está sendo executado por p
processadores, espera-se que ele seja concluído p vezes mais rápido do que seria quando
executado por um único processador. Obviamente, esse caso ideal, na prática não é alcançado
devido a problemas como tempo de comunicação entre os processadores e trechos de código
do programa essencialmente seqüenciais.
Arquiteturas paralelas são normalmente complexas e apresentam um custo de
desenvolvimento elevado. Por isso, a simulação através de software se mostra como a melhor
técnica para avaliação dessas arquiteturas quando comparada à modelagem analítica e à
construção de máquinas reais. Em um software simulador, pode-se: modelar toda a
complexidade de uma arquitetura; efetuar alterações e correções durante o processo de
desenvolvimento; usar tantas máquinas quanto estiverem disponíveis e até simular recursos
que ainda não estão disponíveis fisicamente. Além do que em arquiteturas reais, há outros
16
custos relacionados aos problemas de instalação, gerenciamento e manutenção que também
encarecem as experiências pretendidas. O uso de simuladores também reduz esses fatores e
facilita o estudo de arquiteturas paralelas.
Dada a importância dos simuladores na pesquisa de computadores, o foco deste
trabalho consiste no desenvolvimento um conjunto de algoritmos para testes com o Simulador
de Multiprocessadores Superescalares.
O SMS permite o desenvolvimento de aplicações e a análise de desempenho de
arquiteturas paralelas e possibilita a configuração de diferentes modelos arquiteturais. O
usuário do SMS pode simular ambientes paralelos de memória distribuída, bem como definir
a topologia e o protocolo de rede de interconexão utilizada para comunicação entre os
processadores.
Em conjunto com os algoritmos a ferramenta pode ser vista como uma
alternativa de baixo custo para pesquisa e ensino na área de Arquitetura de Computadores de
Alto Desempenho, pois, viabiliza o desenvolvimento de aplicações paralelas e análise de
desempenho de diversos modelos de arquiteturas.
Este trabalho está organizado conforme segue: o capítulo 2 faz uma breve
descrição sobre Computação Paralela. O capítulo 3 descreve alguns simuladores e trata da
ferramenta de simulação SMS. No capítulo 4 são tratados os diversos aspectos de
programação em ambientes paralelos. Já o capítulo 5 apresenta medidas de desempenho para
auxiliar na análise das saídas do simulador. Por fim, no capítulo 6 são apresentados os
algoritmos propostos para o simulador SMS, e nos capítulos seguintes são apresentados as
conclusões finais e os trabalhos futuros.
17
2 COMPUTAÇÃO PARALELA
Este capítulo discute os fundamentos de computação paralela. Introduz as bases
do modelo seqüencial que servirá de modelo de comparação com o modelo de computação
paralela. Apresenta a taxonomia de Flynn, que é a mais utilizada nas classificações de
arquiteturas de computadores.
2.1 Processamento Seqüencial
O modelo de processamento seqüencial, teve dentre seus criadores Blaise Pascal,
Charles Babbage e John von Neumann. John von Neumann apresentou um modelo elementar
de execução seqüencial, composto basicamente por memória, unidade lógica e aritmética,
unidade de controle e os dispositivos de entrada/saída (Figura 1) (TANENBAUM, 2001). Em
computadores estritamente seqüenciais, as instruções que compõem um programa são
executadas de forma seqüencial (conforme foram definidas pelo programador) pelo
processador. Este modelo proposto serve até hoje como base para a resolução de problemas
através de algoritmos seqüenciais.
Entretanto, atualmente mesmo as arquiteturas seqüenciais utilizam algum tipo de
paralelismo interno ao processador ou aos dispositivos que compõem a arquitetura de forma a
conseguirem melhores desempenhos. Grande parte dos processadores modernos explora o
paralelismo em nível de instrução (ILP – Instruction-Level Parallelism) para melhora de
desempenho. Outra técnica, denominada pipeline, permite a execução sobreposta de várias
instruções. Antes do uso do pipeline uma instrução tinha que esperar a instrução anterior
completar a execução para poder ser executada. Por exemplo, para que uma instrução seja
18
completada ela necessita passar por estágios, tal como: busca de instrução, decodificação,
leitura de registradores, execução e escrita de resultado em registrador. Sem o uso do pipeline
as instruções têm que passar uma por vez, através de todos os estágios. Já com o advento do
pipeline, enquanto uma instrução está na unidade de decodificação, já existe outra instrução
sendo buscada, outra sendo executada e assim por diante. Dessa forma, o pipeline permite que
os estágios necessários para o processamento de instruções fiquem ocupados, de modo que o
processador não fique ocioso (HENNESSY, 2003).
Figura 1 - Máquina de von Neumann
Outra melhoria de desempenho foi obtida com o modelo superescalar.
Processadores superescalares basicamente buscam e decodificam diversos fluxos de
instruções ao mesmo tempo, permitindo que várias instruções sejam executadas em um único
ciclo de clock (SMITH, 1995). Processadores superescalares possibilitam a execução de
instruções em paralelo, utilizando o paralelismo em nível de instrução.
O funcionamento de um processador superescalar consiste basicamente nos
seguintes passos:
i. Os fluxos de dados são analisados quanto a dependências de dados, já que alguns dados
19
podem ter dependências em relação a outras instruções, necessitando aguardar a
execução dessas, para somente então poderem ser processadas.
ii. Depois deste passo é que as instruções são distribuídas para as unidades funcionais de
acordo com o tipo de instrução.
iii. As próximas instruções a serem iniciadas para a execução em paralelo, são baseadas
primeiramente na disponibilidade do operador de dados, que preferencialmente respeita
a ordem do programa seqüencial, porém o processador superescalar pode permitir a
execução de uma instrução fora de ordem (HENNESSY, 2003), o que é uma
característica marcante neste tipo de processador.
iv. Após os passos anteriores é necessário que essas instruções sejam reordenadas, tal tarefa
permite que as instruções apesar de serem executadas em ordem diferente do programa
original voltem à ordem original que foi estabelecida no programa seqüencial.
E desta forma termina-se a execução de uma instrução no processador
superescalar. Assim, processadores superescalares possibilitam que instruções sejam
executadas em uma ordem diferente daquela do programa original e de forma paralela,
fazendo melhor uso de unidades funcionais através do pipeline.
Todos esses aspectos de paralelismo em arquiteturas seqüenciais já trouxeram
inúmeros benefícios à computação, e uniram de certa forma modelos paralelos e seqüenciais,
necessitando assim de uma classificação para essas arquiteturas. A seção 2.2 discute a
Classificação de Flynn.
2.2 Classificação de Flynn
Michael Flynn, em 1966, classificou os inúmeros modelos de arquitetura
computacional de acordo com o número de instruções executadas e o número de conjuntos de
20
dados tratados (FLYNN, 1966), essa caracterização produziu quatro classes de computadores,
que são:
- Arquitetura SISD - Single Instruction, Single Data: Conjunto único de instruções,
conjunto único de dados. É a identificação mais simples de um computador, cujas
instruções são executadas de forma seqüencial, ou seja, tal máquina só processa uma
única instrução sobre um único dado por vez. É o modelo de von Neumann.
- Arquitetura MISD - Multiple Instruction, Single Data: Múltiplas instruções, conjunto
único de dados. São computadores que executam várias instruções ao mesmo tempo
sobre um único dado. Não existe nenhuma máquina implementada neste modelo, e até
mesmo Flynn duvidou que algum dia isso pudesse existir.
- Arquitetura SIMD – Single Instruction, Multiple Data: Conjunto único de instruções,
múltiplos conjuntos de dados. É o equivalente ao paralelismo de dados, no qual uma
instrução é executada paralelamente utilizando vários dados (processadores vetoriais,
matriciais se enquadram nesta categoria).
- Arquitetura MIMD – Multiple Instruction, Multiple Data: Múltiplos conjuntos de
instruções, múltiplos conjuntos de dados. Este modelo é o que faz a melhor referência à
computação paralela propriamente dita, pois se refere ao modelo de execução paralela,
no qual cada processador está essencialmente agindo independentemente, havendo,
portanto realmente múltiplos fluxos de instruções e múltiplos dados (ZARGHAN,
1995).
A taxonomia de Flynn, apesar de elementar está em uso até hoje em função de
sua classificação simples, fácil de entender e por ser muito semelhante aos modelos reais de
arquiteturas de computadores. Atualmente existem modelos híbridos que se enquadram em
mais de uma categoria, o que levou a outras propostas de taxonomias (GUTZMANN, 1996).
21
2.3 Processamento Paralelo
Existem problemas que requerem um grande poder de processamento, por
exemplo, simulações numéricas em sistemas complexos como previsão de clima, aplicações
aerodinâmicas, programas de exploração sísmica, engenharia genética, entre inúmeras outras
aplicações (WOODWARD, 1996; CHANG; EWING, 1999).
Em sistemas com apenas um processador o desempenho do modelo dito
seqüencial, está intrinsecamente relacionado às restrições tecnológicas de cada época, sendo
que uma aplicação só terá melhoras de desempenho se tal processador tiver uma melhora de
hardware. Em geral, os processadores têm melhorado seu desempenho em mais de 50% ao
ano, mas um dia essa evolução pode encontrar algum limite físico, o que se tornará um
empecilho para cientistas que desenvolvem cada vez mais programas que utilizam conjuntos
de dados gigantescos e necessitam de computadores que possam processar esta massa de
dados a uma velocidade cada vez mais rápida e não podem ficar limitados a esse obstáculo.
Neste contexto, a computação paralela é uma alternativa viável com potencial para superar
esse obstáculo.
Mas o que é computação paralela? A definição clássica dada por (ALMASI,
1989) é : “Um computador paralelo é um conjunto de elementos de processamento que se
comunicam e cooperam para resolver rapidamente grandes problemas”. Outras definições
podem ser obtidas, mas basicamente todas trazem a idéia de que é possível empregar vários
processadores para resolver um dado problema de forma paralela e obter-se um menor tempo
de processamento (WAHEED, 1993).
22
2.4 Arquiteturas Paralelas com Memória Compartilhada e Distribuída
Dentro da categoria MIMD é possível obter uma subclassificação das
arquiteturas em função do modelo de acesso à memória. Neste contexto existem dois modelos
bem definidos, que são: computadores com memória compartilhada e computadores com
memória distribuída, que são abordados nas subseções subseqüentes.
2.4.1 Multiprocessadores com Memória Compartilhada
Neste esquema os processadores acessam uma memória única, que é
compartilhada entre todos os processadores, ou mesmo que exista uma memória para cada
processador o endereçamento é global e compartilhado por todos (Figura 2a). A comunicação
entre a memória global e processadores é feita através de instruções load e store que dão
acesso aos endereços da memória. Neste modelo surge a necessidade de se coordenar os
acessos ao meio comum, gerenciando quem pode ler e escrever em um determinado endereço
comum da memória, a esta coordenação de acessos se dá o nome de sincronização.
Este modelo também é denominado de “fortemente acoplado”, e ainda pode ser
dividido em dois esquemas distintos que são: Multiprocessadores UMA (Uniform Memory
Access) e NUMA (NonUniform Memory Access). No modelo UMA ou SMP (Symmetric
MultiProcessor) todos os processadores consomem o mesmo tempo para acessar a memória
compartilhada; enquanto que no modelo NUMA alguns acessos à memória são mais rápidos
que outros. (BADER, 1997; PATTERSON, 2000).
23
Figura 2 - (a) Memória compartilhada (b) Memória distribuída
2.4.2 Multiprocessadores com memória distribuída
Nesta arquitetura cada processador possui memória própria que não é
compartilhada com outro processador, ou seja, o endereçamento de memória não é
compartilhado pelos processadores (figura 2b). Existem funções send e receive, para efetuar
trocas de mensagens e assim realizar a comunicação e sincronização dos processadores que
constituem a arquitetura, já que isso não ocorre diretamente via memória compartilhada. A
esta classificação pode-se também dar o nome de “fracamente acoplada” ou
multicomputadores, já que cada nó (unidade constituída por um processador, memória local e
dispositivos de entrada e saída) é composto por todos os dispositivos que compõem um
computador completo. Nesta categoria de arquitetura pode-se enquadrar os clusters.
Existem inúmeras características a serem observadas no modelo de memória
distribuída, sendo uma das principais para este trabalho o fato de que em sistemas
multicomputadores ao contrário do que ocorre na computação seqüencial, a programação
torna-se mais complexa, pois requer que o programador explore o paralelismo explícito
durante a programação. Assim, o programador tem que conhecer bem a arquitetura em que o
Processador 1
CacheMemória
Disp Entrada/
Saída
Barram
ento
Processador 2
Cache
Processador 3
Cache
Processador 1
Cache
Memória
Disp. Entrada/
Saída
Barram
ento
Processador 2
Cache
Processador NCache
Memória
Memória
(a) (b)
24
programa paralelo será executado, para poder explorar o paralelismo na arquitetura.
Outra desvantagem deste modelo é a necessidade constante de trocas de
mensagens necessárias para sincronização do programa pela rede. Isso pode levar à
sobrecarga do subsistema de comunicação, tornando a rede de interconexão um gargalo do
sistema. Porém, este tipo de arquitetura está sendo a melhor alternativa para realização de
pesquisas em universidades em função do custo e pode apresentar melhoras de desempenho
comparáveis aos supercomputadores.
25
3 SIMULADOR DE ARQUITETURAS
Simuladores possibilitam que novas arquiteturas sejam projetadas e analisadas
em ambientes de software antes de passarem para a linha de produção, reduzindo de certa
forma o custo e o tempo de conclusão envolvidos na construção das arquiteturas. Tal prática
permite até avaliar projetos arquiteturais de computadores que nem mesmo podem ser
construídos, devido às restrições tecnológicas da época. O uso de simuladores está tão
consolidado que mesmo empresas de renome, como Intel, utilizam simuladores para analisar
seus processadores, como é o caso do Pentium 4 (AUSTIN, 2002), proporcionando ao
mercado um processador que já passou por uma bateria de testes mesmo antes de ser
concebido.
Desde o advento do computador é uma prática comum para engenheiros utilizar
modelos de simulação para estudar sistemas físicos de computadores. Entretanto, para obter
simulações realistas principalmente em ambientes paralelos é necessário utilizar cargas de
trabalhos muito grandes de forma que os programas a serem simulados trabalhem com bilhões
de instruções (EECKHOUT, 2004). O nível de complexidade de simulação de arquiteturas
paralelas bem como a carga de trabalho dos algoritmos a serem testados cresce tão
rapidamente que já existem trabalhos que utilizam computadores paralelos para realizar
simulações dos próprios ambientes paralelos e desta forma diminuir o tempo consumido com
simulações de tais ambientes (TROPPER, 2002).
3.1 SimpleScalar
Existe um leque muito grande de simuladores (BAGRODIA, 2000) que são
26
utilizados para os mais diversos propósitos, alguns exemplos de simuladores de arquiteturas
computacionais são: Neander e Ramsés da Universidade Federal do Rio Grande do Sul,
baseados no modelo seqüencial proposto por John von Neumann; RSIM (Rice Simulation)
(PAI, 1997), que faz simulação de arquiteturas superescalares; ABSS (Augmentation-Based
SPARC Simulation) (SUNADA, 1998), empregado principalmente em simulações de
memórias e Proteus (BREWER, 1991), que fornece suporte a sistemas multiprocessadores.
Um outro simulador que tem sido extensivamente utilizado no meio acadêmico e também por
empresas é o simulador SimpleScalar (BURGER, 1997; AUSTIN, 2002).
O SimpleScalar foi desenvolvido em 1992 na Universidade de Wisconsin sob a
coordenação de Gurindar S. Sohi. E posteriormente Doug Burger disponibilizou uma versão
gratuita do simulador para uso não comercial, a qual está disponível na Internet no endereço
eletrônico www.simplescalar.com. O SimpleScalar pode emular diversos conjuntos de
instruções, como por exemplo: ARM, MIPS, Alpha, PowerPC e x86, e devido à sua
arquitetura aberta ele pode ser estendido a outros conjuntos de instruções. Outro fator que
influencia a utilização deste simulador em larga escala é o fato dele ser executado em sistemas
operacionais gratuitos como o Linux. Os pesquisadores de novas arquiteturas podem utilizar
benchmarks pré-compilados ou criar novas aplicações para serem testadas e analisadas neste
simulador, a construção desses programas é realizada utilizando-se uma linguagem de
programação de alto nível, que pode ser C ou Fortran. O código fonte depois de pronto é
compilado especialmente para ser executado no SimpleScalar, possibilitando assim a
execução de programas reais em protótipos virtuais de arquiteturas.
A ferramenta de simulação SimpleScalar é constituída por um conjunto de vários
simuladores, conforme pode-se observar na tabela 1. Desta forma, o SimpleScalar pode
viabilizar simulações de arquiteturas de forma rápida e concisa através do sim-fast ou
simulações mais detalhadas e dinâmicas através do sim-outorder, possibilitando a simulação
27
de processadores que dão suporte a caches non-bloking, execução especulativa, renomeação
de registradores e diversos modos de previsão de desvio.
Simulador Descrição Linhas de código
Velocidade de Simulação
sim-safe Simulador simples 320 6 MIPS
sim-fast Simulador otimizado 780 7 MIPS
sim-profile Programa dinâmico para análise 1300 4 MIPS
sim-bpred Simulador de previsão de desvios 1200 5 MIPS
sim-cache Simulador de caches multinível 1400 4 MIPS
sim-fuzz Testador e analisador de instruções aleatórias 2300 2 MIPS
sim-outorder Simulador de microarquiteturas detalhado 3900 0.3 MIPS
Tabela 1 - Simuladores do SimpleScalar
3.2 Simuladores de Ambientes Paralelos
Muitos centros de pesquisas em computação de alto desempenho têm
desenvolvido pesquisas no sentido de “construir” simuladores para arquiteturas paralelas
servindo como ferramenta para pesquisa e ensino de arquiteturas paralelas. Alguns desses são:
• MINT (MIPS Interpreter) (VEENSTRA, 1993) que utiliza threads para simular um
ambiente multiprocessador, conta com sistema de interconexão e hierarquia de
memória. O MINT roda executáveis compilados para plataformas MIPS (R3000).
• RSIM (Rice Simulator) (PAI, 1997) que implementa um modelo de processador
detalhado para arquitetura superescalar. Simula um sistema multiprocessador de
memória compartilhada. O RSIM roda nas plataformas SPARC e Solaris.
• ABSS (SPARC Simulator) (SUNADA, 1998) empregado principalmente nas
simulações de memória. O ABSS usa threads para simular multiprocessadores. Ele
roda apenas nas plataformas SPARC e possui interface gráfica derivada do MINT.
• Limes (Multiprocessor Simulator for PC Platforms) (MAGDIC, 1999) instrumenta o
28
código em assembler com chamadas “kernel call-outs” em tempo de compilação. Para
isso é preciso que as aplicações utilizem macros do tipo ANL (Argonne National Lab)
para expressar o paralelismo. O Limes também usa threads para simular um ambiente
multiprocessador e roda em plataformas PC.
• Proteus (BREWER, 1991) permite a simulação de multiprocessadores com
interconexões do tipo: bus, k-ary, n-cube e butterfly. Possui biblioteca para passagem
de mensagens, gerenciamento de memória e threads, além de coleta de dados e
interface gráfica sofisticada para representar as saídas da simulação.
• Augmint (NGUYEN, 1996) usa threads para simular um sistema multiprocessador
com espaço de memória compartilhada e privada (para determinadas variáveis). Ele
roda aplicações escritas em C e C++ com macros-m4. Ele roda em arquiteturas Intel
x86.
• Tango Lite (HERROD, 1993) simula um ambiente multiprocessador com memória
compartilhada. Ao contrário do seu predecessor o Tango, o Tango Lite usa threads ao
invés de Unix Process. As aplicações podem ser escritas em C ou Fortran e devem
fazer uso de macros-m4 para criação e controle de processos, bem como para a
comunicação e sincronização dos processos. O Tango Lite roda em plataforma MIPS
(R3000).
• MulSim (MATLOFF, 2005) é um simulador para ambiente multiprocessador com
memória compartilhada, dispondo de vários tipos de interconexão entre memória e
processador.
• Multiprocessor Enhancements of the SimpleScalar Tool Set (MANJIKIAN, 2001).
Simulador funcional (não detalhado) e simulador de cache baseados na ferramenta
SimpleScalar, usam threads para simular um ambiente multiprocessador. Conta com
suporte à visualização gráfica do conteúdo da cache.
29
• SMINT ou Superescalar MINT (LU, 1998) é um simulador de multiprocessadores
superescalares baseado no simulador MINT.
A ferramenta de simulação apresentada neste trabalho (nas seções subseqüentes)
difere-se dos demais simuladores apresentados por permitir simulações detalhadas de
arquiteturas paralelas de memória distribuída, com processadores superescalares que fazem
uso de passagem de mensagem para comunicação entre os processadores. Sendo que a grande
maioria dos simuladores existentes permite apenas a simulação de ambientes de memória
compartilhada usando threads para a programação.
Atualmente é muito interessante a simulação de ambientes com memória
distribuída que utilizam técnicas de passagem de mensagem, pois o uso desta tecnologia está
bastante difundido no mercado e em universidades. O que torna o simulador SMS muito útil,
já que tal simulador possibilita o estudo detalhado de tais ambientes de computação.
3.3 Algoritmos para testes e avaliação de desempenho
Os simuladores citados na seção 3.2 são utilizados para reproduzirem ambientes
computacionais reais e para isso precisam de algoritmos que possam ser executados nas
simulações. Mesmo abordando melhor o assunto sobre algoritmos e programação paralela no
capítulo 4, esta seção apresenta uma breve discussão dos programas utilizados com os
simuladores de arquiteturas ou mesmo algoritmos utilizados em testes de sistemas
computacionais reais.
Os algoritmos utilizados para testes de desempenho no meio computacional são
normalmente denominados benchmarks, que são programas reais ou apenas partes de
programas chamadas de kernels. Estes kernels são as partes mais críticas ou significativas de
um programa real utilizado para testar uma arquitetura ou apenas uma parte da arquitetura.
30
Então, um benchmark é um programa que tem por objetivo proporcionar uma carga de
trabalho a uma arquitetura computacional, de forma que se possa avaliar o desempenho da
arquitetura segundo as características do benchmark.
Existem vários benchmarks e um dos mais conceituados é o System Performance
Evaluation Cooperative (SPEC) (DUJMOVIC, 1998), que tem por objetivo melhorar os
resultados de testes sobre desempenho em sistemas computacionais. Fundado em 1988 o
SPEC iniciou com apenas alguns programas de testes simples que visavam apenas comparar
computadores da época. Porém, atualmente o SPEC está disponível para vários tipos de testes
com arquiteturas, abrangendo desde testes com computadores pessoais através do grupo OSG
(Open System Group), passando por testes de desempenhos de dispositivos com
funcionalidades gráficas com o grupo CPC (Graphics Performance Characterization) e
chegando por fim a grupos que criam benchmarks para computação de alto desempenho como
o grupo HPG (High-Performance Group).
Seguindo a linha de programas para testes de arquiteturas para computação
paralela ou de alto desempenho existem dois benchmarks que merecem destaques: NAS
Parallel Benchmarks (NPB) (BAILEY, 1993) e SPLASH (Standford Parallel Application for
Shared Memory) (WOO, 1995).
O NAS é um conjunto de programas desenvolvidos pela agência aeroespacial
dos Estados Unidos da América (NASA). Os benchmaks do NAS são derivados de aplicações
envolvendo dinâmicas de fluídos, consistindo de cinco kernels e três pseudo-aplicações. O
SPLASH, desenvolvido pela Universidade de Stanford está na versão 2, e é constituído por
kernels envolvendo matrizes e vetores tal como (Complex 1D FFT e Integer Radix Sort) e
aplicações completas como o Ocean Simulation e Water Simulation with Spatial Data
Structure.
Todos esses benchmarks auxiliam a comunidade científica a realizar testes com
31
sistemas computacionais. Entretanto, se utilizados para uso acadêmico, principalmente com
intuído de auxiliar no ensino de arquiteturas paralelas, tais benchmarks deixam a desejar, já
que quase todos são muito complexos dificultando a sua compreensão de imediato. Assim
esses benchmarks são bons para testes de arquiteturas, mas não para o ensino de aplicações
paralelas (BAGRODIA, 1999).
Como o objetivo deste trabalho é desenvolver os aplicativos para um simulador
de arquiteturas paralelas com fins educacionais, os algoritmos propostos aqui têm de ser o
mais simples possível para que um estudante possa entender o algoritmo e da mesma forma
possa utilizá-lo para testar a arquitetura.
3.4 Simulador de Multiprocessadores Superescalares - SMS
Neste contexto, o grupo de pesquisas de arquiteturas de alto desempenho do
Departamento de Informática da Universidade Estadual de Maringá também tem
desenvolvido pesquisas em simulação de arquiteturas paralelas e desenvolveu a ferramenta de
simulação SMS.
A ferramenta SMS viabiliza o desenvolvimento de aplicações e análise de
desempenho de computadores paralelos. O SMS tem como base o núcleo do simulador
SimpleScalar. Atualmente a ferramenta dispõe de memória distribuída, primitivas de
comunicação (Send e Receive) para troca de mensagens e uma rede de interconexão com
topologia de barramento compartilhado (SANDRI, 2004).
Dentre as alterações realizadas no SimpleScalar para o desenvolvimento do
SMS, uma das principais características implementadas é a biblioteca que realiza a
comunicação entre os vários processadores que constituem a arquitetura simulada. As
bibliotecas fornecem primitivas (ver tabela 2) de comunicação semelhantes às do MPI
32
(Message-Passing Interface) (PACHECO, 1997). Através desta biblioteca pode-se
desenvolver aplicativos paralelos e testá-los nas mais diversas arquiteturas.
Tabela 2 - Primitivas SMS para passagem de mensagem
A figura 3 mostra o modelo funcional da ferramenta. Existem 3 módulos
principais: Interface Gráfica, Interface do Simulador e Simulador.
O módulo de Interface Gráfica é usado pelo usuário para definir previamente os
parâmetros que caracterizam a arquitetura simulada, tais como: o número de conjuntos e de
associatividade da cache, o modo de previsão de desvios, o número de unidades funcionais,
memória compartilhada ou distribuída, a topologia e o protocolo de comunicação, e os
programas que serão simulados.
O módulo de Interface do Simulador é responsável por iniciar o módulo
Simulador, repassando a ele as configurações realizadas no módulo de Interface Gráfica. Esse
módulo realiza a distribuição dos processos entre os processadores, e faz a coleta de dados
disponibilizados pelo módulo Simulador, repassando-os para o módulo de Interface Gráfica.
O módulo Simulador é composto de 4 submódulos principais. Esses submódulos
interagem entre si, a fim de promover a execução de aplicações paralelas. São eles: Primitivas
Primitivas Descrição Não bloqueantes
Send Envia Sendbc Envia para todos os processadores em paralelo (Broadcast) Recv Recebe
Bloqueantes por espera ocupada Send_be Envia Sendbc_be Envia para todos os processadores em paralelo (Broadcast) Recv_be Recebe Recvo_be Recebe recuperando a origem Recvseto_be Recebe passando a origem
Bloqueantes por Interrupção Send_bi Envia Sendbc_bi Envia para todos os processadores em paralelo (Broadcast) Recv_bi Recebe Recvo_bi Recebe recuperando a origem Recvseto_bi Recebe passando a origem
33
de Comunicação, Gerenciador de Memória, Protocolo e Topologia.
Figura 3 - Arquitetura do simulador SMS
O submódulo Primitivas de Comunicação dispõe de primitivas Send e Receive
que operam de três maneiras distintas: não bloqueantes, bloqueantes por espera e bloqueantes
por interrupção. As primitivas não bloqueantes enviam e recebem mensagens sem realizar
nenhum tipo de espera ou bloqueio. As primitivas bloqueantes por espera enviam e recebem
mensagens, porém permanecem em espera ocupada aguardando até que uma outra mensagem
de confirmação de envio ou recebimento seja transmitida. As primitivas bloqueantes por
interrupção são semelhantes às bloqueantes por espera, entretanto, ao invés da espera
ocupada, o programa é interrompido pelo simulador fazendo com que os ciclos de execução
não sejam computados para esse programa.
O submódulo Gerenciador de Memória simula o uso de memória compartilhada
e distribuída. Quanto à hierarquia de memória, o simulador conta com cache de instruções,
cache de dados e opção para cache unificada. O gerenciador de memória conta também com
protocolo para coerência de cache e política de escrita na cache. A memória distribuída está
implementada, e a memória compartilhada está sendo implementada. O simulador
Interface Simulador
Interface para passagem de parâmetros da simulação
Disparador e Coletor
Programa 1 Programa 2 Programa N Programa 3 ...
Bibliotecas – Send e Receive Gerenciador de Memória
Protocolo
Topologia
Processador Processador 2 Processador Processador ...
Interface Gráfica
Simulador Paralelo
Programas do Usuário
34
possibilitará testar os mesmos algoritmos com arquiteturas paralelas de memória
compartilhada e distribuída, melhorando ainda mais o nível de simulação.
O submódulo Protocolo é encarregado do gerenciamento da comunicação da
rede de interconexão entre os processadores. O protocolo de comunicação é dependente da
topologia da rede de interconexão escolhida. Esse submódulo emprega desde políticas simples
de arbitragem de barramento até protocolos mais complexos de roteamento para redes de
interconexão.
O submódulo Topologia é responsável pela simulação da topologia da rede de
interconexão. Esse submódulo permite a simulação de diversas configurações de redes de
interconexão, como: barramento, redes multiestágio, crossbar, entre outras. A topologia tipo
barramento comum já está implementada neste submódulo.
Para a implementação da ferramenta foram replicadas as estruturas do simulador
sim-outorder do SimpleScalar de maneira que a ferramenta comporta-se como um conjunto de
vários simuladores sim-outorder sendo executados em paralelo. Para permitir a troca de
mensagens entre os processadores simulados, desenvolveu-se a biblioteca de primitivas de
comunicação que permite troca de mensagens entre os processadores. Essa biblioteca conta
com primitivas não bloqueantes, bloqueantes por espera e bloqueantes por interrupção.
Desta forma, a ferramenta atualmente permite a execução de qualquer algoritmo
desenvolvido em C, tanto de forma seqüencial, quanto paralela. Para a simulação de
programas paralelos é necessário o uso das primitivas de comunicação da própria ferramenta.
As simulações atualmente permitem comparação, estudo e análise de sistemas reais baseados
em arquitetura de memória distribuída que utilizam bibliotecas de passagem de mensagem. A
ferramenta é uma ótima alternativa para testes de Arquiteturas de Alto Desempenho.
35
3.5 Biblioteca de Passagem de Mensagem do SMS
O simulador SMS tem uma biblioteca de passagem de mensagem baseada na
biblioteca MPI, o que facilita o desenvolvimento de programas paralelos a serem executados
no simulador, pois essa metodologia é semelhante à utilizada em arquiteturas reais de
computação paralela (SANDRI, 2004).
Durante a programação de um algoritmo a ser simulado no SMS, o programador
irá desenvolver dois arquivos fontes, um arquivo fonte principal ou mestre, que irá fornecer
atributos e funcionalidades básicas para o programa e iniciará e terminará todo o processo
executado pela arquitetura paralela simulada. Esse programa é executado por um processador
também denominado de mestre. O outro é um arquivo fonte secundário ou escravo que será
executado pelos demais processadores (processadores escravos) que compõem a arquitetura
paralela. O arquivo escravo faz normalmente o serviço bruto de processamento e computação
de dados e é controlado pelo programa mestre.
Para se utilizar a biblioteca do SMS faz-se necessário incluir no corpo do
programa a chamada à biblioteca com.h., tanto no código fonte do arquivo mestre quanto do
escravo (figura 4). Depois de declaradas todas as estruturas, variáveis, funções e todos os
atributos que podem compor um código em C, faz-se necessário na função principal (do
programa mestre e do escravo) incluir a função de sincronização (openchanel). Sem o uso de
tal função os programas não se comportam adequadamente (não ficam sincronizados), assim o
uso da função openchanel é obrigatório. De forma geral, essas são as únicas exigências para
se desenvolver um programa paralelo a ser simulado pelo SMS. Entretanto, se um programa
não usa passagem de mensagem não é necessário utilizar a biblioteca com.h nem a função
openchanel para a simulação no SMS.
36
Figura 4 - Inicializando a biblioteca de comunicação do SMS
Após fazer a devida chamada à biblioteca de passagem de mensagem do SMS, e
sincronizar os programas, é possível utilizar as funções de passagem e recebimento de
mensagem dentro do simulador SMS. As principais funções da biblioteca SMS (todas as
funções da biblioteca SMS podem ser vistas na tabela 2) são: send, sendbc, recv e recv_be. A
função send, é responsável por enviar dados de um único computador de origem para um
único computador de destino. Tomando como exemplo a linha: send(((char *)&texto),
sizeof(texto),1). Tal linha envia o conteúdo da estrutura de dados texto ((char *)
&texto), e especifica o tamanho da mesma estrutura ( sizeof (texto)). O tamanho da estrutura
serve para alocar memória no processador que receber a estrutura. Por fim, envia a estrutura
ao processador 1.
A utilização de estruturas de dados para a passagem de valores no SMS facilita a
compreensão da programação paralela. Dentro da estrutura é possível passar qualquer variável
até mesmo um conjunto delas. A figura 5 mostra um exemplo de como poderia ser enviada a
# arquivo mestre.c #include <stdlib.h> #include <stdio.h> #include </usr/sms/com.h> ... void main (void) { int a, b, c; double soma; openchanel(); puts("Mestre: inicia\n"); ... }
# arquivo escravo.c #include <stdlib.h> #include <stdio.h> #include </usr/sms/com.h> ... void main (void) { int a, b, c; double soma; openchanel(); puts("Mestre: inicia\n"); ... }
Código fonte do programa mestre Código fonte do programa escravo
37
estrutura texto. A estrutura deve estar presente tanto no arquivo mestre como no arquivo
escravo. Após enviar os dados usando a função send será necessário recebê-los no
processador de destino. Isso é possível através da função recv, desta forma a sintaxe usada na
função para receber a estrutura texto é recv(((char *)&texto), sizeof(texto)).
Porém, com a função recv não haverá como sincronizar o algoritmo, de forma que, pode ser
mais conveniente o uso da função recv_be, que também irá receber o dado, porém o programa
que usa esta função ficará esperando (ocioso) até receber tal estrutura. Por fim, alguns dados
podem ter de ser enviados para todos os processadores de forma que a função de envio
broadcast (sendbc – envia para todos os processadores da arquitetura) é mais recomendada.
Tal função envia com apenas uma mensagem e de uma única vez toda a estrutura de dados
para todos os processadores, o que é bem mais eficaz do que enviar uma mensagem de cada
vez para todos os processadores. A sintaxe para sendbc é muito parecida com a do send,
omitindo-se apenas o processador de destino. Uma observação pertinente é que a mensagem
em broadcast é enviada para todos os processadores inclusive para o processador que faz o
uso da função, desta forma é necessário um recv_be neste processador também.
Existem mais funções (tabela 2), porém apenas com as funções send, sendbc e
recv_be é possível desenvolver a maioria dos algoritmos paralelos.
Desta forma, através do uso das bibliotecas de comunicação apresentadas pelo
simulador SMS, o usuário poderá de forma fácil e prática (já que não é necessário possuir um
computador com várias unidades de processamento) entender como funciona um programa
paralelo, e tão logo se acostume com os aspectos da programação paralela poderá facilmente
passar do simulador SMS para um ambiente real.
38
Figura 5 - Usando funções da biblioteca SMS
# arquivo mestre.c #include <stdlib.h> #include <stdio.h> #include </usr/sms/com.h> //declaração da estrutura texto struct __texto { char mensagem; int processador_número; } __texto; Struct _texto texto; void main (void) { int i; //abre canal openchanel(); // atribui texto a estrutura texto.mensagem=”ola mundo”; texto.processador_número=0; //envia ao processador 1 send((char *)&texto)
sizeof(texto), 1); //atribui novo texto texto.mensagem=”ola Todos”; texto.processador_número=0; //envia para todos sendbc((char *)&texto)
sizeof(texto)); //também recebe novo texto recv_be((char *)&texto)
sizeof(texto)); //mostra o que foi recebido printf(“o processador: %d
envia um %s”texto.processador_número, texto.mensagem);
}
# arquivo escravo.c #include <stdlib.h> #include <stdio.h> #include </usr/sms/com.h> //declaração da estrutura texto struct __texto { char mensagem; int processador_número; } __texto; Struct _texto texto; void main (void) { int i; //abre canal openchanel(); //processador 1 recebe recv_be((char *)&texto)
sizeof(texto)); //mostra o que foi recebido printf(“o processador: %d
envia um %s”texto.processador_número, texto.mensagem);
//recebe novo texto recv_be((char *)&texto)
sizeof(texto)); //mostra o que foi recebido printf(“o processador: %d
envia um %s”texto.processador_número, texto.mensagem);
}
Código fonte do programa mestre Código fonte do programa escravo
Fluxo das mensagens
39
4 PROGRAMAÇÃO PARALELA E ALGORITMOS PARALELOS
Normalmente arquiteturas MIMD com memória compartilhada ou distribuída
são criadas para computar programas das mais diversas áreas da ciência. Tais programas
necessitam ser muito bem elaborados para explorar ao máximo os recursos de uma máquina
paralela. Um algoritmo paralelo pode ser definido como um conjunto de processos (partes de
um programa) que podem ser executados simultaneamente, tais processos podem se
comunicar uns com os outros a fim de resolver um determinado problema. Já um algoritmo
seqüencial é executado passo a passo de forma seqüencial como foi definido durante a sua
programação (ZARGHAN, 1995).
Um fato de extrema importância na maioria dos sistemas paralelos,
principalmente os que exploram o paralelismo explícito (não em nível de instrução), é que o
sistema paralelo em si é a combinação de um algoritmo paralelo e uma arquitetura paralela na
qual o algoritmo é implementado (GUPTA, 1993), ou seja, para que um sistema paralelo
atinja o seu objetivo principal, que é a melhora de desempenho na resolução de determinados
problemas, é necessário, além de uma arquitetura física composta por vários processadores
um algoritmo que explore todo este potencial da arquitetura. Pois não adianta ter os recursos
necessários para melhorar o desempenho se estes não forem devidamente utilizados.
Entretanto, a tarefa de construir algoritmos paralelos ótimos, que empreguem da melhor
maneira possível todos os subsídios oferecidos pela arquitetura paralela, não é nada fácil, e
talvez seja uma das tarefas mais difíceis no desenvolvimento de um sistema paralelo.
Uma prática constantemente utilizada por programadores é a reutilização de
algoritmos, pois se um algoritmo realiza uma função de forma eficiente, ele pode ser utilizado
em outro programa que irá necessitar das funcionalidades desta função. Esta técnica de
40
reutilização também é normalmente empregada na computação paralela, entretanto, muitos
pesquisadores consideram que a melhor forma de se obter o paralelismo ideal é reconstruindo
o algoritmo inteiro, modelando-o para a arquitetura na qual ele será executado. Sobre este
problema Patterson (PATTERSON, 2000) comentou:
“O maior obstáculo ao sucesso dos sistemas multiprocessadores não é o custo dos
processadores usados em sua arquitetura, nem os problemas na topologia para conexão de
redes, muito menos a indisponibilidade de linguagens de programação adequadas a tais
sistemas; mas a grande dificuldade é o fato de que poucos programas de aplicação importantes
têm sido reescritos para executar suas tarefas em sistemas multiprocessadores”.
(PATTERSON, 2000, p. 416).
Assim reutilização de algoritmos não é recomendável nem para arquiteturas
paralelas semelhantes. Por exemplo, não se pode afirmar que um algoritmo projetado para ser
executado em um computador contendo 8 processadores vai ser executado mais rapidamente
em um sistema semelhante com 64 processadores, a menos que esse programa seja
remodelado para esta arquitetura. Isso ocorre porque quanto maior a quantidade de
processadores, maior será o esforço computacional para sincronizar os processos, e maior
ainda será a utilização da rede de interconexão que interliga os processadores (CHOI, 1993;
MATHESON, 1996). Por mais absurdo que possa parecer é bem provável que um programa
especificamente projetado para ser executado em um computador com 8 processadores faça
melhor uso desta arquitetura, do que de uma arquitetura com 64 processadores. Portanto, é
fácil concluir que o programador, neste caso, tem que ser um especialista em hardware e
software para tentar fazer um bom uso dos recursos de cada máquina paralela (KUMAR,
1991).
Dessa discussão, conclui-se que diferentes tipos de aplicações são mais
adequadas para uma determinada configuração ou outra dependendo de como foi paralelizado
o código do programa.
41
No que se refere à programação para computação paralela é possível encontrar
modelos computacionais em que o programador não precisa se preocupar em como o sistema
fará uso do paralelismo, ficando isso a cargo do compilador da arquitetura. Porém, é muito
difícil obter-se o uso ideal dos recursos de um computador paralelo de forma automática, já
que há diversas máquinas com as mais variadas configurações de hardware, o que dificulta o
processo do compilador em explorar as características de cada arquitetura paralela, sendo
então necessário um compilador para cada computador paralelo, o que é inviável.
Por isso, os métodos mais utilizados na programação paralela são aqueles nos
quais o programador deve instruir o programa em como explorar a arquitetura (os vários
processadores, a memória e a rede de interconexão), ou seja, o programador precisa conhecer
a arquitetura e não apenas programar e deixar que o compilador utilize os recursos
disponíveis.
Neste cenário destacam-se os métodos de variáveis compartilhadas e de
passagem explícita de mensagem. Na técnica de variáveis compartilhadas todos os processos
têm acesso a uma memória comum (endereçamento global), podendo se comunicar lendo e
escrevendo (load e store) nesta memória. Esta técnica é comumente utilizada em sistemas
multiprocessadores de memória compartilhada, e apesar de um pouco mais complexa pode ser
empregada também em sistemas multicomputadores com memória distribuída. O outro
método é o de trocas de mensagens, que tem se popularizado devido ao seu grande uso em
Clusters. Neste esquema são empregadas primitivas de envio e recebimento (send e receiver),
que são usadas para trocas de mensagens entre processos (TANENBAUM, 2001).
4.1. Aplicações Paralelas
Os sistemas computacionais, em geral, são projetados com o propósito de
42
agilizar a execução de uma determinada tarefa. Entretanto, algumas aplicações,
principalmente científicas, requerem grande poder computacional (WOODWARD, 1996;
CHANG, 1999; EWING, 1999). Algumas dessas aplicações podem consumir muito tempo de
processamento, e em casos extremos podem se tornar impraticáveis devido ao longo tempo de
computação. A fim de atender essa demanda foram desenvolvidas técnicas para reduzir o
tempo de execução de tais aplicações.
Uma técnica que vem tendo muito destaque é a exploração do paralelismo
apresentado por essas aplicações. Pois a maioria das aplicações possui algum nível de
paralelismo, que pode ser explorado de maneira que o programa possa ter seu tempo de
execução reduzido.
Então, aplicações paralelas fazem uso de múltiplos processadores para resolver
um determinado problema, e isso é possível através da execução simultânea de diversos
passos que compõem a solução do problema. Isso permite que uma aplicação paralela faça
uso de vários processadores, o que não ocorre em programas seqüenciais, que essencialmente
executam conjuntos básicos de passos de forma seqüencial, sem nenhum nível de paralelismo
(GRAMA, 2003).
Mesmo com o possível benefício de redução do tempo de execução da aplicação,
o uso do paralelismo requer alguns cuidados que não são necessários em aplicações
seqüenciais. Por exemplo, a aplicação paralela, apesar de possuir uma semântica parecida com
a aplicação seqüencial, deve tratar de aspectos inerentes às suas características paralelas tais
como: definir quais processos podem ser executados de forma paralela e gerenciar de forma
eficiente a sincronização e comunicação entre tais processos.
Segundo Grama a construção de um algoritmo paralelo segue basicamente os
seguintes passos (GRAMA, 2003):
• Identificar pontos do programa que podem ser executadas de forma paralela;
43
• Distribuir as entradas e saídas de dados pertinentes à aplicação, bem como os dados
intermediários gerados durante a execução das tarefas e que estão associados ao
programa;
• Gerenciar da melhor forma possível o acesso aos dados compartilhados pelos
processadores, para execução de um dado problema, reduzindo a comunicação entre
processos;
• Sincronizar eficientemente os processadores nos mais diversos estágios de execução
de um programa paralelo, de forma que os processadores não fiquem com uma carga
de trabalho muito elevada ou muito baixa.
Para que um programa obtenha um bom desempenho em uma arquitetura
paralela é necessário decompô-lo em um conjunto de tarefas (processos), que são unidades de
programas bem definidas que fazem parte da aplicação principal. A execução simultânea de
múltiplas tarefas para resolver um dado problema pode reduzir o tempo de execução da
aplicação. As tarefas podem ser executadas todas juntas ou em qualquer seqüência. Tarefas
também podem apresentar dependência, e desta forma necessitam esperar que outras tarefas
sejam executadas para terminar sua própria execução.
A decomposição de problemas em tarefas envolve o particionamento da
aplicação. O particionamento é definido como um conjunto específico de tarefas que irá
resolver um dado problema em um computador paralelo da maneira mais eficiente possível.
Existem dois métodos para se particionar tarefas (CHOI, 1993; ZARGHAN, 1995):
• Particionamento Estático: Neste método as tarefas são particionadas durante a
programação e não em tempo de execução, desta forma cada processador recebe sua
carga de trabalho antes de iniciar a computação. A vantagem é que normalmente neste
método existe pouca comunicação e disputa entre os processos, pois estes já foram
previamente particionados. Então, no particionamento estático existe uma
44
“simplicidade” relativa no gerenciamento das tarefas. Entretanto, é uma tarefa
extremamente complexa para o programador dividir as tarefas entre os processadores
de forma eficiente (principalmente em ambientes paralelos heterogêneos), e se a
divisão de tarefas não for feita de forma correta alguns processadores podem ficar
ociosos enquanto outros ficam sobrecarregados durante a execução.
• Particionamento Dinâmico: Neste método o particionamento é realizado durante a
execução do programa. A vantagem é que ele supervisiona os processadores de forma
que todos fiquem ocupados. A desvantagem é que esse método normalmente tem
grande demanda de comunicação.
Uma vez que o programa foi dividido em processos, cada processo pode ser
executado em um processador diferente. A esse mapeamento entre processos e processadores
dá se o nome de escalonamento, o qual tem por objetivo a melhor utilização dos recursos
computacionais fornecidos pela arquitetura paralela (GRAMA, 2003). O escalonamento é
comumente observado em Sistemas Operacionais, porém neste caso é conhecido como
escalonamento local, e refere-se ao problema de atribuição de time-slices de um processador
aos processos (TANENBAUM, 2001). O escalonamento em computação paralela faz
referência a um escalonamento aplicável a Sistemas Distribuídos ou Paralelos.
O escalonamento (KUMAR, 1991) da mesma forma que o particionamento,
também pode ser estático ou dinâmico. No estático, os processos e a ordem em que eles serão
executados são conhecidos antes da execução do programa. Para se realizar um bom
escalonamento estático é necessário conhecer o tempo de execução de cada tarefa e o tempo
que cada unidade de processamento e seus recursos consomem para executar tal tarefa. É
obvio que isso não é nada fácil. Outra dificuldade no escalonamento estático, é que se uma
unidade de processamento parar de funcionar, o programa será abortado, já que não há como
fazer o re-escalonamento das tarefas, pois este é estático. No escalonamento dinâmico os
45
processos são atribuídos aos seus processadores durante a execução. Neste ambiente não se
faz necessário conhecer totalmente o ambiente no qual o programa paralelo será executado, já
que normalmente o programa irá se adaptar e se moldar à arquitetura paralela, o que oferece
uma melhor utilização dos processadores disponíveis, incrementando desta forma a
flexibilidade quanto ao aproveitamento do número de processadores que compõem a
arquitetura.
Para se realizar um bom escalonamento dinâmico é preciso analisar os pontos
críticos da arquitetura (por exemplo, gargalos como a rede de interconexão) e buscar a melhor
maneira para dividir as tarefas entre os processadores, isso possibilitará a distribuição das
tarefas de forma eficiente e melhorará o desempenho do algoritmo. A esse processo se dá o
nome de balanceamento de carga (CALZAROSSA, 2003).
O número e o tamanho das tarefas decompostas em uma dada aplicação
determinam a granularidade do problema. Desta forma, granularidade refere-se ao tamanho
de uma tarefa em um processador e o desempenho de um algoritmo paralelo depende
diretamente da granularidade do programa (LU, 1998). Se um programa for dividido em um
pequeno número de grandes tarefas (granularidade grossa) a tendência é que esse algoritmo
seja mais adequado para arquiteturas com um número pequeno de processadores e desta
forma se torne uma aplicação com um nível de paralelização muito baixo. Já se um programa
for dividido em um grande número de pequenas tarefas (granularidade fina), o programa terá
um nível de paralelização maior, entretanto, é bem provável que neste caso o programa faça
maior uso da rede interconexão, podendo desta forma perder desempenho devido ao alto grau
de comunicação requerido entre as tarefas. O programador de aplicações paralelas deve
balancear a granularidade da aplicação tentando manter um alto coeficiente de paralelização e
da mesma forma tentando reduzir a necessidade de comunicação entre as tarefas, procurando
assim obter uma granularidade média.
46
Uma alternativa para reduzir a demanda de comunicação entre as tarefas é
definir grupos de tarefas, relacionando as tarefas que mais se comunicam e deixando-as juntas
onde a comunicação tenha um custo menor (CHOI, 1993; MATHESON, 1996;
CREMONESI, 1999).
Outro aspecto que deve ser observado é a relação entre o número de
processadores e o tamanho do problema, essa relação influencia na redução da comunicação
entre as tarefas (GUSTAFSON, 1988; GUPTA, 1993; GRAMA, 1993; HOGANSON, 1999;).
Esta relação será discutida mais detalhadamente no tópico sobre avaliação de desempenho, no
capítulo 5.
Portanto, ajustar o número de processadores ao tamanho do programa ou vice-
versa leva a um tempo de execução melhor, e o programador deve estar atento a esse fator e
aos outros discutidos anteriormente (GRAMA, 2003; ZARGHAN 1995).
Quanto ao ambiente de programação e desenvolvimento de aplicações paralelas
é possível encontrar basicamente três tipos de ferramentas de programação (GRAMA, 2003):
• Compiladores: Fazem a paralelização de forma automática. Neste tipo de ferramenta o
programa normalmente é construído de forma seqüencial, ficando a cargo do próprio
compilador explorar o paralelismo da aplicação. Neste modelo, normalmente
consegue-se um ganho de desempenho menor se comparado à exploração explícita do
paralelismo, mas a construção do aplicativo através de compiladores exige o mínimo
esforço do programador, já que este irá programar normalmente (de forma seqüencial),
sem se preocupar em descobrir qual trecho de código deve ser paralelizado e como
isso será realizado.
• Extensões de Paralelização: São normalmente bibliotecas que possuem primitivas de
comunicações (como por exemplo: MPI e PVM), que facilitam o gerenciamento dos
processos existentes em aplicações paralelas. Essas bibliotecas podem ser utilizadas a
47
partir de linguagens de programação normalmente seqüenciais (C++, Fortran, Pascal,
etc).
• Linguagens de Programação Paralelas: Especialmente projetadas para serem usadas
em ambientes paralelos, tais linguagens possibilitam a construção de aplicações bem
estruturadas e possuem rotinas de gerenciamento de processos paralelos muito
eficientes, dinamizando desta forma a comunicação, sincronização e gerenciamento da
aplicação paralela.
Todas as ferramentas apresentadas possuem seus prós e contras. O compilador
paralelo facilita a programação e agiliza o desenvolvimento da aplicação, mas normalmente
não consegue fazer o uso ideal dos recursos fornecidos por cada arquitetura paralela. Por sua
vez, as linguagens de programação paralelas conseguem um bom desempenho em arquiteturas
paralelas (GRAMA, 2003), entretanto, exigem que o programador aprenda uma nova
linguagem de programação, o que pode levar um tempo considerável e consumir também um
tempo precioso no desenvolvimento da aplicação paralela. Desta forma, as ferramentas que
atualmente merecem maior destaque são as extensões paralelas, que podem ser usadas pelo
programador em uma linguagem de programação já conhecida por ele, ficando a cargo do
programador apenas aprender como usar de forma eficiente as rotinas que possibilitam a
programação paralela. Além disso, as extensões permitem uma melhor adaptação de códigos
seqüenciais para códigos paralelos, e conseguem explorar de forma eficiente grande parte dos
recursos de uma arquitetura paralela.
Além de escolher alguma ferramenta de programação, é necessário ter-se em
mente como o algoritmo será paralelizado, principalmente se o desenvolvedor do aplicativo
escolher uma ferramenta na qual necessite paralelizar a aplicação de forma direta como
ferramentas de extensão e linguagens paralelas.
Modelos de algoritmos paralelos são formas de estruturar algoritmos paralelos
48
através de técnicas de decomposição, mapeamento e estratégias de minimização das
interações entre as tarefas.
O enfoque principal deste trabalho aborda paralelismo no contexto de memória
distribuída. Neste tipo de arquitetura pode-se aplicar as seguintes abordagens para se extrair o
paralelismo:
• Data Parallelism - Explora os dados a serem processados pelo programa paralelo.
Cada tarefa executa operações semelhantes sobre dados diferentes (GRAMA, 2003).
Este modelo emprega balanceamento de carga de trabalho estático, o que normalmente
garante um bom balanceamento de carga (GRAMA, 2003; ZHANG, 1994). O
paralelismo de dados apresenta ótimos resultados, pois geralmente não requer muita
comunicação o que diminui o overhead e o tempo gasto com a comunicação
(ZHANG, 1994), e quanto maior a entrada de dados melhor é seu desempenho
(GUSTAFSON, 1988; ZARGHAN, 1995). Um exemplo desta prática é um algoritmo
de multiplicação de matrizes no qual as colunas e as linhas das matrizes a serem
multiplicadas são distribuídas entre os diversos processadores que compõem a
arquitetura paralela, e cada processador executa o mesmo código para multiplicar
essas linhas e colunas, completando desta forma a aplicação.
• Task Graph - Neste modelo o inter-relacionamento entre as tarefas do problema é
utilizado para agrupar os dados relacionados. Procurando-se deixar os dados que se
inter-relacionam sempre onde possam ser acessados de forma mais rápida (por
exemplo, na memória local), facilitando a comunicação ou pelo menos reduzindo o
custo da comunicação entre os processos (CREMONESI, 1999). O modelo Task
Graph é utilizado para resolver problemas nos quais vários dados estão associados e as
tarefas necessitam interagir entre elas, fazendo uso desses dados (GRAMA, 2003).
Este tipo de modelo é mais facilmente implementado em arquiteturas de memória
49
compartilhada, mas pode ser implementado em arquiteturas de memória distribuída.
Desta forma, um programa paralelo pode ser representado por um grafo de tarefas
(task graph), no qual os nós representam módulos e as arestas indicam a necessidade
de comunicação entre esses nós (CHOI, 1993). Um exemplo de aplicação que utiliza
este modelo é o método de ordenação quicksort.
• Work Pool - Também conhecido como Task Pool, é caracterizado por um mapeamento
dinâmico entre tarefas e processadores visando desta forma um bom balanceamento de
carga entre os processadores. Tal mapeamento pode ser centralizado ou
descentralizado. As tarefas podem ser armazenadas em listas de prioridade, tabelas
hash, ou em árvores. Em arquiteturas de passagem de mensagem esse modelo é
normalmente usado quando a quantia de dados associados à tarefa é relativamente
pequena se comparada com a computação associada com as tarefas (GRAMA, 2003).
O mesmo exemplo da multiplicação de matriz pode ser utilizado aqui, mas neste caso
os processadores irão buscar as tarefas a serem executadas (as linhas e colunas) em
uma lista.
• Processor Farm – Neste modelo existe um processador principal (também chamado
de “mestre”) que é responsável por gerenciar um grupo de processadores (chamados
de “escravos”), no qual cada escravo processa assincronamente tarefas submetidas
pelo mestre. O mestre gerencia o trabalho dos escravos e faz o balanceamento de
carga. Este modelo é muito utilizado tanto por arquiteturas de memória compartilhada
quanto por memória distribuída, entretanto é necessário ter-se cuidado para que o
processador mestre não se torne um gargalo neste modelo (GRAMA, 2003).
Utilizando a mesma aplicação de multiplicação de matrizes, neste método um
processador ficará responsável por distribuir as colunas e linhas a serem multiplicadas.
50
• Pipeline ou Produtor-Consumidor – Este modelo segue o modelo de pipeline
empregado pelos processadores, ou seja, um fluxo de dados é passado através de uma
sucessão estágios (HENNESSY, 2003). Cada estágio executa uma tarefa diferente
sobre este fluxo de dados (ZARGHAN, 1995). Essa execução simultânea de diferentes
tarefas sobre um fluxo de dados também é chamado de stream parallelism. Cada
processo no pipeline pode ser visto como o consumidor de uma seqüência de dados do
processo que o precede e um produtor de dados para o processo seguinte do pipeline,
daí o nome Produtor-Consumidor (GRAMA, 2003). Utilizando mais uma vez o
exemplo da multiplicação de matrizes, neste método cada estágio seria responsável
por uma operação, sendo, o primeiro estágio responsável pela entrada de dados, o
segundo pela multiplicação, o seguinte pela adição e o último pela saída, terminando
desta forma todos os estágios do pipeline necessários para essa aplicação.
Em muitos casos mais de um modelo de programação paralela pode ser aplicado
para a resolução de um problema. Um modelo híbrido pode ser construído aplicando-se vários
modelos de forma hierárquica ou aplicando-se múltiplos modelos de forma seqüencial para
diferentes fases do algoritmo.
Ainda no que se refere a modelos de programação é possível encontrar mais
dois modelos (ZARGHAN, 1995): estruturas síncronas e assíncronas. Tais modelos podem
ser considerados como modelos base para os modelos discutidos anteriormente.
Na estrutura síncrona dois ou mais processos estão ligados por um ponto comum
de execução usado com propósitos de sincronização entre processos. Um processo irá atingir
um ponto no qual terá de esperar por um ou mais processos. Após os processos terem
alcançado o ponto de sincronização, eles podem continuar a execução do programa até o
próximo ponto de sincronização. Nesta estrutura, os demais processos sempre esperaram pelo
processo mais lento e esta é a principal desvantagem deste método. Esta estrutura de
51
algoritmo paralelo também é conhecida como Partitioning Algorithms.
É possível aplicar estruturas de sincronização em diversos problemas. Este
método envolve, por exemplo, uma série de iterações em grandes estruturas de matrizes. Cada
iteração usa o resultado parcial produzido pela iteração precedente e o transforma em busca
de uma solução final. A computação em cada iteração pode ser paralelizada de forma que
cada processo trabalhe em diferentes partes dos dados da matriz. De qualquer forma, depois
de cada iteração os processos devem ser sincronizados devido ao resultado parcial produzido,
que será usado pelo processo seguinte em outra iteração. Esse ciclo continuará até serem
cumpridos todos os passos e assim atingir uma solução final.
A estrutura assíncrona permite que os processos pertencentes ao algoritmo
trabalhem com o dado mais recente fornecido pela execução de outros processos. Quando um
processo termina um estágio, ele atualiza as informações necessárias e inicia o próximo
estágio. Quando este modelo é utilizado em um ambiente de passagem de mensagem, um
processo lê algumas mensagens de entrada de dados e depois completa um estágio. Baseado
nas mensagens e nos resultados obtidos pelo estagio anterior, o processo ativa seu próximo
estágio e envia mensagens para outros estágios. Desta forma, algoritmos assíncronos
continuam ou terminam seus processos conforme os valores de passagem de mensagem e não
esperam por um conjunto de entrada de dados como no caso do modelo síncrono.
Em comparação com algoritmos síncronos, os assíncronos requerem menos
acessos à memória compartilhada, o que reduz a disputa por memória. Em geral, algoritmos
assíncronos são mais eficientes devido à seguinte característica: os processos não esperam
pela execução de outros processos. Isso normalmente diminui o tempo de execução; os
resultados dos processos que são executados mais rapidamente podem ser usados para
eliminar processos mais lentos; proporcionando menos competição por memória. Entretanto,
52
algoritmos assíncronos são difíceis de programar. Sua análise é mais complexa que a de um
algoritmo síncrono.
Todas as técnicas de programação para ambientes paralelos não são exclusivas e
podem ser combinadas para produzirem resultados melhores em uma aplicação paralela.
Além disso, freqüentemente aplicações paralelas possuem várias etapas de computação, em
que pode ser necessário aplicar diferentes tipos de decomposição.
4.2 Passagem de Mensagens
Não basta dispor de diversos processadores para se obter computadores mais
rápidos. É necessário que haja um gerenciamento correto desses processadores para que o
programa obtenha um desempenho ideal e é justamente com o propósito de fornecer um
gerenciamento dos multiprocessadores ou multicomputadores que surge a técnica de
passagem de mensagem.
Conforme discutido na seção 4.1, não existe um modelo padrão de programação
paralela, porém existe uma prática chamada de extensão de paralelização que tem sido muito
utilizada. Neste contexto existem duas bibliotecas de passagem de mensagem, que têm sido
amplamente utilizadas e que efetuam a intercomunicação entre os processadores, podendo ser
tomadas como referência em programação paralela. As bibliotecas PVM (Parallel Virtual
Machine) e MPI (Message Passing Interface), são utilizadas a partir de linguagens de
programação como C ou FORTRAN e, possibilitam o compartilhamento de informações entre
os processadores que compõem a máquina paralela (PACHECO, 1997). Antes dessas
bibliotecas cada fabricante tinha que desenvolver sua própria forma de trocar informações
entre máquinas MIMD, o que dificultava ainda mais o cenário da programação em
computação paralela. Portanto, essas bibliotecas vieram para auxiliar o programador.
53
A passagem de mensagem é o método de comunicação baseado no envio e
recebimento de mensagens, cuja funcionalidade é a gerência dos processos, entretanto quem
determina como isso será feito é o programador, as bibliotecas fornecem apenas o meio de
gerenciar tais tarefas não fazendo isso automaticamente, como faz um compilador
(ZARGHAN, 1995).
54
5 AVALIAÇÃO DE DESEMPENHO
Quando um sistema paralelo utiliza dois processadores, logo se cria a expectativa
de que qualquer programa executado neste sistema será processado duas vezes mais rápido do
que numa máquina monoprocessada.
Porém, isso não é verdade. Para que a execução paralela atinja o máximo
possível de desempenho, o código do programa originalmente desenvolvido de forma
seqüencial deve, de alguma maneira, ser 100% paralelizado. Supondo que seja possível obter
esse patamar de programação, bem como possuir um sistema perfeito de sincronização entre
os processadores, no qual a comunicação também seja efetuada em um tempo desprezível,
então seria possível obter um sistema totalmente paralelo que certamente alcançaria um ganho
de desempenho equivalente ao número de processadores que compõem a arquitetura.
Entretanto é extremamente raro encontrar problemas a serem computados que
não empreguem trechos estritamente seqüenciais. Amdahl, em 1967, questionou a eficiência
de sistemas paralelos, afirmando que mesmo pequenas partes de um programa precisam ser
paralelizadas para que todo o potencial da arquitetura possa ser explorado (SUN, 1990).
Então, pode-se deduzir por essa afirmação, que o objetivo do ganho linear de desempenho
envolve a descoberta de novos algoritmos que sejam inerentemente paralelos. A lei de
Amdahl sugere que é muito difícil alcançar o desempenho de pico esperada para uma
arquitetura paralela (PATTERSON, 2000). Mas, ainda que não se consiga paralelizar
totalmente um algoritmo e alcançar sempre o desempenho ideal em sistemas paralelos, é
possível obter ganhos significativos de desempenho paralelizando os núcleos de programas
(partes em que se concentram os maiores esforços computacionais).
Neste contexto, este capítulo discute alguns aspectos relacionados à avaliação de
desempenho.
55
5.1 Alguns aspectos quanto a medidas de desempenho
O desempenho de sistemas paralelos é o resultado de interações complexas entre
recursos de hardware e software. O desempenho de computadores paralelos está relacionado a
características de aplicações, tais como estrutura do algoritmo, parâmetros de entrada,
tamanho do problema, a características físicas como número de processadores e taxas de
transferência da rede de interconexão. Todos esses aspectos determinam como a aplicação
explora os recursos disponíveis em arquiteturas paralelas e consequentemente como
influenciam no desempenho (CALZAROSSA, 2003, GRAMA, 2003).
Uma boa maneira de se conseguir uma ótima interação entre hardware e software
e atingir um bom desempenho usando sistemas paralelos é analisando o comportamento de
cada atributo da arquitetura frente a um conjunto de algoritmos (tais algoritmos são
denominados Benchmarks) que teste tal arquitetura da maneira mais completa possível
(FRANCIS, 1988; BAILEY, 1993). Para tal, são empregadas ferramentas que permitem
analisar como um algoritmo faz uso da arquitetura paralela. Softwares de análise e métricas de
desempenho são divididos em estáticos e dinâmicos (CREMONESI, 1999). Os estáticos são
derivados de modelos que adotam a descrição da aplicação. O software captura características
inerentes ao paralelismo da aplicação e sincronização. Métricas dinâmicas são extraídas a
partir da execução de aplicações, normalmente isso se dá através do uso de simuladores.
Medidas estáticas incluem: número de nós, grau de sincronização, tamanho do caminho a ser
percorrido, caminho máximo que um nó de entrada tem de percorrer até um nó de saída,
tamanho do problema, etc. Já algumas métricas dinâmicas são: tempo de computação dos
processadores, tempo de comunicação, tempo de execução, volume de comunicação, volume
de entrada/saída, entre outros. O uso de simuladores é muito considerado para este propósito,
já que conseguem obter dados significativos de um grande número de recursos de hardware.
56
Medidas em computação paralela fazem referência à execução de uma aplicação
paralela em P processadores, onde K diferentes atividades e N regiões de códigos podem estar
sendo monitoradas. A monitoração de tais aspectos da computação paralela pode ser obtida
através da análise de alguns parâmetros, tais como: medidas de atividades de computação (por
exemplo, número de instruções executadas pelo processador), comunicação, acesso à
memória, I/O (Input/Output – entrada/saída) ou regiões do código como loops, rotinas, etc.
Vários parâmetros podem ser medidos em arquiteturas paralelas:
• Parâmetros de tempo;
• Número de operações de entrada e saída;
• Número de bytes lidos e escritos;
• Número de acessos à memória;
• Número de faltas de cache (cache misses);
• Número de bytes enviados e recebidos;
Então, as propriedades das métricas de sistemas paralelos devem ser estudadas,
pois elas influenciam diretamente no desempenho de uma aplicação. Por exemplo, um fato
bem conhecido no emprego de arquiteturas paralelas é o tamanho fixo do problema, em que
os ganhos de desempenho dos algoritmos paralelos não continuam crescendo com o aumento
do número de processadores. Já que a arquitetura tende a saturar conforme aumenta o número
de processadores. Desta forma, o número ideal de processadores para uma arquitetura
depende do tamanho do problema (GUPTA, 1993; CREMONESI, 1999).
O tamanho do problema já foi um dos maiores empecilhos enfrentados pelos
pesquisadores. A lei de Amdahl (SUN, 1990), causou certo marasmo dentre as pesquisas de
sistemas paralelos, até que em 1988 Gustafson (GUSTAFSON, 1988), observou que Amdahl
assume que o número de processadores é independente do tamanho do problema, o que
57
normalmente não é o caso. Na prática o tamanho do problema é proporcional ao número de
processadores. Quando é dado mais poder computacional, o problema geralmente se expande
para fazer uso das facilidades da arquitetura, tal observação permitiu que os estudos sobre
sistemas paralelos tomassem novos rumos desde então.
Existem diversas medidas para a caracterização de desempenho de um sistema
paralelo, mas as que mais se destacam são: tempo de execução, speedup e eficiência
(EAGER, 1989; SUN, 1990).
5.2 Tempo de execução
Historicamente o tempo de execução ou o tempo decorrido (elapsed time) é uma
das métricas mais populares (CREMONESI, 1999; CALZAROSSA, 2003; GRAMA, 2003)
para verificar o desempenho em um dado sistema. O tempo de execução serial é o tempo
decorrido do início da execução do programa até o seu término em um computador
seqüencial. Já o tempo de execução paralelo é o tempo decorrente do momento em que o
programa inicialmente é executado na arquitetura paralela até o momento em que o último
processador empregado para a resolução do problema termina a execução.
5.3 Speedup
Em conjunto com o tempo decorrido existe uma métrica denominada speedup
(aceleração ou ganho de desempenho) que é extremamente utilizada. O speedup é a divisão do
tempo decorrido de uma arquitetura pela outra, por exemplo, uma arquitetura seqüencial por
uma paralela, ou até mesmo uma arquitetura paralela por outra. O speedup consegue
demonstrar de forma gráfica os diversos aspectos de uma arquitetura paralela (rede de
58
interconexão, número de processadores, etc) (CREMONESI, 1999). Existem inúmeros fatores
que influenciam no speedup, dentre alguns, a rede de interconexão, capacidade de
processamento do processador, o número de processadores, os aspectos de programação (ver
capítulo 4 sobre programação paralela), entre outros. O speedup é a medida do mérito relativo
de uma aplicação frente a diferentes números de processadores de um sistema paralelo, ou
seja, é a medida que representa o benefício relativo do uso de determinada arquitetura paralela
para resolver um dado problema.
Existem duas modalidades bem definidas para se medir o speedup, que são:
speedup absoluto e o relativo (SUN, 1990). O primeiro é definido como o tempo decorrido na
execução seqüencial do melhor algoritmo dividido pelo tempo de execução decorrente do
algoritmo paralelo. Já speedup relativo é definido como o tempo decorrente de um algoritmo
paralelo em um único processador e o tempo decorrente do mesmo algoritmo paralelo em N
processadores. A razão para se usar speedup relativo é que o desempenho de algoritmos
paralelos varia de acordo com o número de processadores disponíveis em uma arquitetura e
comparando-se o mesmo algoritmo em função da variação do número de processadores é
possível verificar de forma mais precisa o impacto do uso do paralelismo, do que se usando o
speedup absoluto que faz a comparação com um algoritmo serial (SUN, 1990).
Existem vários parâmetros que podem ser expressos através do speedup, os mais
significativos são: o speedup de tamanho de problema fixo (fixed-size speedup) que foi
descrito por Amdahl, e o speedup de tempo fixo (fixed-time speedup), descrito por Gustafson
que é o mais usado atualmente. No speedup de tamanho fixo o tamanho do problema é
mantido constante variando-se apenas o número de processadores da arquitetura, no speedup
de tempo fixo tanto o número de processadores quanto o tamanho do problema são alterados,
o que condiz mais com a realidade (GUSTAFSON, 1988). O tempo é dito fixo porque a idéia
é aumentar o número de processadores junto com o tamanho do problema de forma que o
59
tempo mantenha-se constante. Uma melhor compreensão dos speedups de Amdahl e de
Gustafson pode ser obtida através da figura 6, na qual W1 é o tamanho da parte seqüencial do
programa e WN é a parte paralela do programa, em conjunto com esses dados são
apresentados a relação entre o tamanho do problema e o número de processadores no speedup
de Amdahl e tempo de execução e número de processadores no speedup de Gustafson.
Figura 6 - Características dos Speedups de tamanho fixo e tempo fixo (SUN, 1990)
Na prática pode-se definir a aceleração (speedup) ou ganho que sofre cada
arquitetura (BAGRODIA, 2000), medindo-se o tempo de execução na arquitetura seqüencial
dividido pelo tempo consumido pela execução na arquitetura paralela, para executar o mesmo
problema (figura 7), isso para o speedup absoluto. No caso do speedup relativo é só colocar
W1
WN
W1
WN
W1
WN
W1
WN
1 2 3 4
Número processadores
Tamanho do Problema
T1
TN
T1
TN
T1
TN
T1
TN
1 2 3 4
Número processadores
Tempo de Execução
WN WN WN WN
1 2 3 4
Número processadores
Tamanho do Problema
T1
TN
1 2 3 4
Número processadores
Tempo de Execução
W1
W1
W1
W1 T1
TN
T1
TN
T1
TN
Amdahl - fixed-size speedup
Gustafson - fixed-time speedup
60
no lugar do tempo de execução do programa seqüencial o tempo do algoritmo paralelo
executado com apenas um processador (ver figura 8).
Paralelo
Seqüencial
çãoTempoExecuçãoTempoExecu
speedup =
Figura 7 - Speedup Absoluto
NoçãoParalelTempoExecuoçãoParalelTempoExecuspeedup 1=
Figura 8 – Speedup Relativo
Desta forma o speedup é a referência de quão melhor é um sistema paralelo em
relação ao sistema seqüencial ou outro sistema podendo ser até mesmo outro paralelo
(ZARGHAN, 1995; GRAMA, 2003).
Programas com finalidade de apresentar o desempenho de sistemas paralelos
(por exemplo, simuladores) são normalmente responsáveis por fornecer um grande montante
de dados ao usuário para viabilizar a análise do uso dos recursos. Para uma melhor
apresentação desses dados é necessário que tais programas permitam uma representação
gráfica de forma a facilitar a análise (WAHEED, 1993). O speedup viabiliza uma medida
gráfica extremamente útil para a apresentação do comportamento do algoritmo frente a
arquitetura paralela. Tais apresentações gráficas mostram ao usuário o estado global do
sistema paralelo, e o usuário pode analisar como está sendo efetuada a distribuição das tarefas
entre os recursos e se é possível melhorar ainda mais o desempenho do sistema.
61
5.4 Eficiência
Outra medida que pode ser empregada no estudo de arquiteturas paralelas, e é
derivada do speedup, é a eficiência. Eficiência é uma medida da fração de tempo na qual um
processador é realmente usado. Em sistemas paralelos ideais o speedup é igual ao número de
processadores e a eficiência é igual a um (GUTPA, 1993). Em sistemas reais o speedup é
menor que o número de processadores e a eficiência fica entre zero e um.
A análise de eficiência permite determinar a melhor combinação de algoritmo e
arquitetura para um problema (GRAMA, 1993). A eficiência relata o tamanho do problema e
o número de processadores requeridos para manter o sistema eficiente, e isso ajuda a
determinar a escalabilidade do sistema, sua velocidade e largura de banda da rede de
comunicação.
Existe uma referência direta entre o número de processadores, tamanho do
problema e a eficiência, de forma que, quando se aumenta o número de processadores a
eficiência é reduzida, e aumentando-se o tamanho do problema aumenta-se a eficiência. Desta
forma ao se aumentar ambos a eficiência será constante (ZHANG, 1994).
Uma pergunta natural então é: qual o limite para se aumentar o número de
processadores proporcionalmente ao tamanho do problema? Isso depende da arquitetura, mas
se o tamanho do problema é constante enquanto o número de processadores aumenta, a
eficiência apresenta quedas, por causa do acréscimo de overhead (controle de comunicação
entre os processadores) causado pelo número de processadores. Já se o tamanho do problema
aumenta enquanto o número de processadores é constante então, a eficiência aumenta devido
ao nível insignificante do overhead em relação à computação do problema. Desta forma,
pode-se manter a eficiência desde que se aumente de forma proporcional o tamanho do
problema (GRAMA, 1993). É claro que é muito difícil encontrar a relação exata entre o
62
tamanho do problema ideal para cada arquitetura, já que o problema pode estar associado a
inúmeros aspectos de hardware e software.
A eficiência é considerada uma métrica que investiga a escalabilidade dos
algoritmos. Tal métrica é obtida pela fórmula apresentada na figura (9).
resProcessadodeNúmeroSpeedupEficiência =
Figura 9 – Eficiência
Portanto, o número processadores deve ser escolhido de forma a maximizar a
eficiência e o speedup da arquitetura.
63
6 ALGORITMOS PARALELOS PARA O SMS
Neste capítulo são apresentados os algoritmos desenvolvidos para testes de
avaliação de desempenho em arquiteturas a serem simuladas no SMS. Tais algoritmos
viabilizam a investigação das arquiteturas simuladas, auxiliando assim na avaliação da
arquitetura. Os algoritmos também têm objetivos educacionais, permitindo que alunos de
computação possam analisar tais algoritmos, alterá-los e testá-los, introduzindo assim o
ambiente de computação paralela.
6.1 Algoritmo Paralelo de Multiplicação de Matrizes
A multiplicação de matrizes e as demais operações envolvendo matrizes estão
relacionadas com inúmeras aplicações da computação científica, engenharia, matemática,
química, biologia entre outras. Então, devido a sua usabilidade, será utilizada a multiplicação
de matrizes para demonstrar algumas características da computação paralela e os benefícios
que a programação paralela pode oferecer a esta operação, já que este tipo de função pode
estar presente nos mais diversos programas.
Antes de começar a desenvolver um algoritmo paralelo, no caso o de
multiplicação de matrizes deve-se verificar o que envolve a multiplicação de matrizes, como
ela é realizada em ambientes seqüenciais e finalmente como se pode obter um nível de
paralelismo neste problema.
Uma matriz é um arranjo de números (ver figura 10), tal que A é uma matriz 2×
3 A=( ija ) em que, para i=1,2 e j=1,2,3, o elemento da matriz na linha i e na coluna j é ija .
São usadas letras maiúsculas para denotarem matrizes, e letras minúsculas para denotarem
64
linhas e colunas da matriz, fazendo assim referência aos elementos da matriz.
=
23
13
22
12
21
11
aa
aa
aa
A
Figura 10 - Matriz
Já a multiplicação de matrizes pode ser descrita da seguinte forma: têm-se duas
matrizes A e B que são compatíveis no sentido de que o número de colunas de A é igual ao
número de linhas de B. Se A=( ija ) é uma matriz m× n e B=( jkb ) é uma matriz n× p, então o
produto de matrizes C=AB é a matriz m× p C=( ikc ), em que ∑=
=n
jjkijik bac
1
para i=1,2,...,m e
k=1,2,...,p (CORMEN, 2002).
Então, através da descrição de multiplicação de matrizes se pode construir o
algoritmo apresentado na figura 11 para realizar esta operação de maneira seqüencial.
Este algoritmo multiplicando uma matriz n×n, executa 3n multiplicações e
)1(2 −nn adições, portanto, pode-se concluir que o tempo de execução desse algoritmo é
)( 3nΘ (CORMEN, 2002).
Existem outras maneiras para se construir o algoritmo de multiplicação de
matrizes de forma seqüencial, o algoritmo de Strassem (CORMEN, 2002) apresenta uma
proposta recursiva para multiplicar matrizes n×n, apresentando um tempo de execução de
)()( 81,27lg nOn =Θ . Este algoritmo supera, em termos de complexidade, o algoritmo anterior,
porém como o algoritmo de Strassem normalmente não é o método mais utilizado por
programadores para multiplicação de matrizes, será usado como algoritmo base para os
estudos deste trabalho o primeiro algoritmo com tempo )( 3nΘ .
65
Figura 11 - Algoritmo seqüencial para multiplicação de matrizes
O algoritmo para a multiplicação de matrizes n× n em paralelo, proposto aqui,
baseia-se no primeiro modelo seqüencial, apresentado no início da seção, e tem como objetivo
obter um desempenho melhor que este. O algoritmo basicamente consiste em subdividir as
linhas de uma matriz A em vetores, em que o número de vetores é igual ao número de linhas
da matriz (ver figura 12) e o tamanho dos vetores é igual ao tamanho das linhas.
Figura 12 - Divisão da Matriz em Vetores no Programa Mestre
Cada vetor será multiplicado pelas colunas da matriz B, a qual será enviada para
todos os processadores que compõem a arquitetura (através da função sendbc). Então, para
desenvolver esse algoritmo paralelo utilizam-se dois programas um mestre e outro escravo. O
programa mestre envia os vetores a serem multiplicados (utilizando a função send(((char
*)&vetor), sizeof(_vetor),p) da biblioteca de comunicação do SMS), para os programas
escravos que estão sendo executados independentemente em cada processador. Os programas
Multiplica-Matrizes(A,B) n ← linhas[A] seja C uma matriz n×n for i←1 to n
do for j←1 to n do ijc ←0
for k←1 to n do ijc ← ijc + kjik ba *
return C
11a
21a
31a
12a
22a
32a
13a
23a
33a
Matriz A Matriz A Sub-dividida
11a 12a 13a
21a 22a 23a
31a 32a 33a
Vetor A1
Vetor A2
Vetor A3
66
escravos estarão esperando (através da função recv_be) os vetores para multiplicá-los com as
colunas da matriz B (figura 13).
Após multiplicar o vetor pelas colunas da matriz B, o programa escravo irá
enviar para o nó mestre o resultado da multiplicação de cada linha, que neste momento já será
o resultado final referente à mesma linha da matriz resposta. O processo mestre terá então
apenas que receber os resultados e atribuí-los à matriz resposta, construindo desta forma a
solução final da multiplicação (veja figura 14).
Portanto, o processo mestre fica encarregado de distribuir cada vetor a ser
multiplicado a um determinado programa escravo, que estará sendo executado em um
processador independente, em um esquema de memória distribuída, e tão logo os processos
escravos terminem a multiplicação dos vetores da matriz A pelas colunas da matriz B os
resultados serão enviados ao nó mestre que irá re-agrupar os resultados obtidos, finalizando
assim o trabalho.
Figura 13 - Multiplicação dos Vetores pelas Colunas da Matriz B nos Processadores Escravos
Figura 14 - O programa mestre reagrupa os vetores resultantes dos processos escravos
11a 12a 13a 11b
21b
31b
12b
22b
32b
13b
23b
33b
Matriz B
11c 12c 13c
Vetor C1
Vetor A1
Vetores C
11c 12c 13c
21c 22c 23c
31c 32c 33c
Vetor C1
Vetor C2
Vetor C3
11c
21c
31c
12c
22c
32c
13c
23c
33c
Matriz C
67
Ao analisar o algoritmo paralelo proposto (figura 15) pode-se notar que ele é
muito semelhante ao algoritmo seqüencial, apresentado na figura 11, a principal diferença é
que ele subdivide o loop que faz a multiplicação das linhas da matriz pelas colunas da outra
matriz. Essa subdivisão proporciona que o algoritmo se torne p vezes mais rápido do que o
algoritmo seqüencial original. Entretanto, ele é p vezes mais rápido na rotina de
multiplicação, ficando uma parte seqüencial sem nenhuma melhora, já que uma parte do
código do algoritmo é estritamente seqüencial, portanto, o tempo de execução do novo
algoritmo paralelo pode ser dado por )/( 3 pnO . No entanto, este tempo sofre algumas
influências externas e não chega a ser totalmente verdade que ao se usar 2 processadores
(p=2) o programa ficará duas vezes mais rápido ou ao se usar 32 processadores (p=32) o
programa tornar-se-á trinta e duas vezes mais rápido que o programa seqüencial. Um dos
fatores que influenciam nesta perda de velocidade é o tempo de transmissão dos dados na rede
de interconexão, então, ao tempo de execução pode-se acrescentar um fator chamado comt , que
seria o tempo de comunicação entre os elementos que constituem a arquitetura paralela que
executa o algoritmo em questão (BADER, 2004). Esse fator afeta diretamente o tempo de
execução.
Assim, o algoritmo deverá ter o seguinte tempo de execução ))/(( 3comtpnO + .
Ou seja, se for possível controlar o fator comt e reduzir os trechos estritamente seqüenciais
pode-se ter um ganho de tempo considerável.
Depois de implementar o algoritmo de multiplicação de matrizes no ambiente de
simulação SMS, foram realizados alguns testes com diferentes tamanhos de matrizes.
A figura 14 exibe um resumo do arquivo de saída da simulação do algoritmo de
multiplicação de matrizes de tamanho 800x800 utilizando dois processadores, sendo um
processador chamado 00 e o outro 01. Se houve n processadores os números que representam
68
os processadores teria uma saída para cada processador, cuja última saída seria n-1.
Figura 15 – Algoritmo paralelo de multiplicação de matrizes
Apesar da figura 16 não apresentar todas as saídas do arquivo original, é possível
analisar vários aspectos, como número de instruções executadas em cada processador, tempo
de simulação, total de dados enviados e recebidos, entre outras saídas que foram omitidas.
O ganho de desempenho do algoritmo paralelo foi devidamente comparado com
o algoritmo seqüencial. O algoritmo seqüencial foi implementado e testado no simulador
SimpleScalar (sim-outourder).
Através dos dados de simulações gerados pelo SMS (Figura 16) é possível obter
informações pertinentes sobre a simulação de cada arquitetura testada.
Através dos testes realizados é possível notar que o algoritmo de multiplicação
de matrizes em paralelo obteve um ótimo ganho de desempenho (ver figura 17, nos gráficos
de tempo em todo este trabalho a legenda do lado direito informa o número de processadores),
executando os problemas de forma paralela em um tempo de execução muito inferior ao
algoritmo seqüencial. Sendo que os algoritmos executados com um tamanho de problema
01. #include </usr/sms/com.h> 02. struct _matriz matriz; 03. struct _vetor vetor; 04. void main(void) { 06. openchanel(); 07. sendbc(((char *)&matriz),sizeof(_matriz)); 08. recv_be(((char *)&matriz),sizeof(_matriz)); 09. for (i=0;i<N;++i){ 10. for (t=0;t<N; ++t){vetor.X[t]=A[i][t];} 11. vetor.linha=i; 12. send(((char *)&vetor), sizeof(_vetor),p); 13. if (p==P) p=1;else p++; 14. } 15. /*recebe e monta vetores nas matrizes*/ 16. for (i=0;i<N;++i){ 17. recv_be(((char *)&vetor), sizeof(_vetor)); 18. for (t=0;t<N;++t) { 19. C[vetor.linha][t]=vetor.X[t]; 20. }
01. struct _matriz matriz; 02. struct _vetor vetor; 03. void main(void){ 04. openchanel(); 05. /*recebe matriz B para suas colunas serem multiplicadas 06. recv_be(((char *)&matriz),sizeof(_matriz)); 07. for (;;){ 08. for(i=0;i<N;++i){ 09. vtaux[i]=0;} 10. recv_be(((char *)&vetor), sizeof(_vetor)); 11. /* realiza a multiplicacao */ 12. for (t=0;t<N;++t){ 13. for (i=0;i<N;++i){ 14. vtaux[t]=vtaux[t]+(vetor.X[i]*matriz.B[i][t]);} 15. } 16. /*atribui os calculos ao vetor para devolver ao mestre*/ 17. for (t=0;t<N;++t){vetor.X[t]=vtaux[t];} 18. /*Envia vetor calculado ao mestre*/ 19. send(((char *)&vetor), sizeof(_vetor),0);
Mestre Escravos
69
maior (principalmente o 600x600) tiveram um ganho de tempo muito significativo se
comparados com o problema seqüencial.
Figura 16 – Saída reduzida de uma simulação no SMS
O algoritmo de multiplicação de matrizes desenvolvido neste trabalho emprega
técnicas de paralelismo de dados. O que significa que os processadores escravos executam a
mesma operação sobre dados diferentes para resolver um dado problema. Conforme foi
constatado no capítulo 4, sobre programação paralela, esse tipo de algoritmo é altamente
paralelo e apresenta ótimos resultados, o que pode ser observado na figura 15. Por fim, tem
como característica marcante o fato de que quanto maior o problema melhor o desempenho.
A partir da figura 18 são apresentados resultados referentes ao speedup e
eficiência. Nos gráficos de speedup e eficiência, a legenda do lado direito de cada figura
representa o tamanho do problema simulado.
Para o speedup mostrado na figura 18, nota-se que todos os problemas obtiveram
ganhos de desempenhos substanciais, sobressaindo mais uma vez os problemas de maior
# total simulation time in seconds sim_elapsed_time 53410 # total number of instructions executed sim_total_insn_00 23773083318 sim_total_insn_01 12126038543 # total simulation time in cycles sim_cycle 11878967426 # total number of ocupance cycles inet_ocupance_cycles_00 2560800 inet_ocupance_cycles_01 320400 # total number of bytes received inet_received_bytes_00 5123200 inet_received_bytes_01 3841600 # total number of bytes sended inet_sended_bytes_00 10243200 inet sended bytes 01 1281600
70
tamanho. Isso demonstra também a enorme relação que existe entre a arquitetura paralela, o
software a ser executado nesta arquitetura e o tamanho do problema, sendo que todos estes
influenciam diretamente o ganho de desempenho da arquitetura.
Multiplicação de Matrizes 50x50
02
46
810
1214
16
Processadores
Tem
po e
m s
egun
dos
12481632
Multiplicação de Matrizes 100x100
020
4060
80100
120140
160
Processadores
Tem
po e
m s
egun
dos
12481632
Multiplicação de Matrizes 600x600
05000
1000015000
2000025000
3000035000
40000
Processadores
Tem
po e
m s
egun
dos
12481632
Multiplicação de Matrizes 800x800
0100002000030000400005000060000700008000090000
Processadores
Tem
po e
m s
egun
dos
12481632
Figura 17 – Tempo de execução do algoritmo de multiplicação de matrizes
Multiplicação de Matrizes
0
5
10
15
20
25
30
1 2 4 8 16 32
Processadores
Spe
edup
50x50100x100600x600800x800
Figura 18 - Speedup apresentado pelo algoritmo paralelo de multiplicação de matrizes
71
A queda apresentada no gráfico (figura 18) do speedup, nos problemas de
tamanho 50x50 e 100x100, ocorre devido a fatores de granularidade do algoritmo e de
overhead na rede de interconexão. Provavelmente, se fosse utilizada uma rede mais eficiente
o algoritmo obteria ganhos de desempenhos melhores, mas não seriam ganhos ótimos já que o
problema de granularidade neste caso seria o principal fator pela perda de desempenho.
Assim, para um ótimo ganho de desempenho será necessária a implementação de um
algoritmo que permita uma granularidade de dados menor e que aproveite melhor a
arquitetura, não deixando processadores ociosos, como está ocorrendo no algoritmo de
multiplicação de matrizes que foi implementado.
Quanto ao fator eficiência, a figura 19 mostra que apesar dos fatores: tempo de
execução e speedup apresentarem bons ganhos de desempenho, existe uma queda de
eficiência da arquitetura quando esta é submetida a qualquer problema usando apenas 2
processadores. No entanto, quando os problemas foram submetidos a testes com 8 ou 16
processadores, o sistema passou atingir bons picos de eficiência, voltando a cair quando se
usou 32 processadores, principalmente nos menores problemas (50x50 e 100x100).
Multiplicação de Matrizes
00,20,40,60,8
11,21,41,61,8
1 2 4 8 16 32
Processadores
Efic
iênc
ia 50x50100x100600x600800x800
Figura 19 – Eficiência apresentada pelo algoritmo paralelo de multiplicação de matrizes
72
Portanto, em uma análise mais refinada verifica-se que se fosse necessário
implantar uma arquitetura real (com as mesmas características físicas simuladas) para resolver
este problema, seria uma ótima opção a construção de um computador paralelo com 8
processadores. Já que a maioria dos problemas testados atingiu seu pico de desempenho e
eficiência com esta configuração. E apesar da arquitetura continuar apresentando ganhos de
desempenho com 16 processadores, tal arquitetura não seria recomendada, pois seria
necessário dobrar o número de processadores para atingir ganhos de desempenhos
insatisfatórios e que não proporcionariam uma boa relação custo/beneficio.
Apesar de existirem inúmeros outros algoritmos de multiplicação de matrizes em
paralelo (O’LEARY, 1985; BAGRODIA, 1991; CHOI, 1998), o algoritmo paralelo
apresentado neste trabalho é suficiente para demonstrar de forma simples como se paralelizar
um algoritmo e permite analisar características importantes de arquitetura e também da
própria aplicação.
Por fim, os testes com o programa mostraram-se muito satisfatórios e
apresentaram resultados muito semelhantes aos obtidos em problemas de multiplicação de
matrizes apresentados em outros trabalhos (CHOI, 1998; O’LEARY, 1985; LAINE, 2003).
6.2 Algoritmo Paralelo para Cálculo do π
π (pi) é um dos números mais empregados na matemática e representa a relação
do comprimento L de uma circunferência e o diâmetro d da mesma. Oπ é um número
irracional expresso por uma dízima infinita não periódica. A busca incansável por esse
número surgiu devido ao fato dele estar ligado a dois problemas fundamentais do universo
matemático, que são: o problema de retificação da circunferência e da quadratura do círculo.
A busca por esse valor transcende épocas, desde as civilizações Babilônicas e
73
Egípcias antes de Cristo até os dias atuais. Atualmente os matemáticos que buscam um valor
mais preciso para o π utilizam computadores, e já conseguiram calculá-lo com uma precisão
de aproximadamente 1000 bilionésimos de dígitos binários, este número foi obtido após 25
dias de cálculos intensivos em um cluster desenvolvido pela Universidade Simon Franser.
A utilização de um cluster para o cálculo do π indica o uso de técnicas de
paralelismo para a resolução deste problema, e nesta seção será discutida a implementação de
um algoritmo paralelo para o cálculo do π através das bibliotecas de comunicação fornecidas
pelo simulador SMS.
Existem diversas maneiras de se calcular o π , tais como: série de Fourier,
Mclaurin, Taylor e via integração. O método utilizado para a construção do algoritmo aqui
proposto será o de integração, cuja fórmula pode ser vista na figura 20.
Para se determinar o valor de π será utilizado o cálculo da área gerada pela
função em um número finito de intervalos. Para tanto, a regra de decomposição do retângulo é
utilizada. A região x é dividida de 0 a 1 em n pontos. O valor da função é calculado no ponto
médio de cada intervalo. Os valores são somados e multiplicados pelo comprimento de um
intervalo (MENEGHETTI, 2004).
∫ +=
1
021
4x
π
Figura 20 - Fórmula para calcular o valor de π
Para a implementação do algoritmo de forma paralela a área da curva a ser
calculada é dividida pelo número de processadores p. Portanto, cada processador irá calcular
uma fatia do valor de π , que será um valor parcial (figura 21b). E no final todos os π ’s
parciais serão enviados para o processo mestre, que irá somar os valores parciais, calculando
desta forma o valor do π global (figura 21a).
74
Figura 21 - Programa escravo do cálculo do π
A parte fundamental para que esse algoritmo funcione de forma paralela é a
divisão das iterações, tal divisão ocorre no laço de repetição (for (i=NP; i<=N; i=i+TP)), no
qual o valor da variável i jamais irá se repetir em nenhum processo escravo na função x = w *
(i – 0,5). Caso o valor da variável i se repita nos processos paralelos o cálculo do π será
apresentado de forma errada devido às propriedades do cálculo do π via integral.
O algoritmo do cálculo do π é naturalmente paralelo, devido às propriedades
utilizadas pela função da integral utilizada para calcular o π (WILKINSON, 1999). O
algoritmo faz uso dos canais de comunicação apenas no início do processo enviando o total de
iterações (n) e o número total de processadores a serem utilizados para o processamento e, ao
final do processo envia apenas o resultado parcial (figura 21b), que é computado no
processador mestre (figura 21a). Devido a essas peculiaridades de processamento totalmente
independente e pouca necessidade de comunicação o algoritmo de cálculo do π via integral
atinge um bom speedup (figura 22).
Entrada: Número do processador NP. Saída: Valor parcial de π recv_be(N,TP) w = 1.0/n for (i=NP; i<=N; i=i+TP) x = w * (i – 0,5) pi = pi + (4.0 / (1.0 + (x * x)))
pi = pi * w send(pi)
(a)
Entrada: Nº iterações N, Total de processadores TP. Saída: Valor global de π pi_global send_bc(N,TP) for (x=1; x<=TP; x++) recv_be(pi) pi_global=pi_global+pi mostra (pi_global)
(b)
75
Cálculo do pi
02468
10121416
1 2 4 8 16 32
Processadores
Spe
edup
10.00020.000100.0001.000.000
Figura 22 - Speedup do algoritmo paralelo do cálculo do π
Analisando a figura 23, que faz referencia ao tempo de execução é possível
perceber que neste problema conforme aumenta-se o número de processadores diminui-se o
tempo de execução, isso devido às propriedades do algoritmo discutidas anteriormente.
Quanto a eficiência, a figura 24 mostra que a forma mais eficiente de se executar
tal problema é com apenas um único processador, entretanto devemos levar em conta os
resultados do speedup e tempo de execução que demonstram que apesar da arquitetura não
mostrar-se totalmente eficiente ela apresentou ganhos substanciais de desempenho, chegando
em alguns casos a reduzir pela metade o tempo de execução.
Desta forma, apesar desta arquitetura apresentar uma baixa eficiência para a
resolução deste problema, ainda assim é viável o uso da computação paralela, já que o tempo
economizado é relativamente grande, além do que, se for necessário aumentar o tamanho do
problema futuramente, tal arquitetura provavelmente apresentará um maior índice de
eficiência (ZHANG, 1994).
76
Cálculo do pi (n=10.000)
0
10
20
30
40
50
60
70
Processadores
Tem
po e
m s
egun
dos
12481632
Cálculo do pi (n=20.000)
0
20
40
60
80
100
120
140
Processadores
Tem
po e
m s
egun
dos
12481632
Cálculo do pi (n=100.000)
0
100
200
300
400
500
600
700
Processadores
Tem
po e
m s
egun
dos
12481632
Cálculo do pi (n=1.000.000)
01000
20003000
40005000
60007000
8000
Processadores
Tem
po e
m s
egun
dos
12481632
Figura 23 – Tempo de execução do algoritmo do cálculo do π
Cálculo do pi
0
0,2
0,4
0,6
0,8
1
1,2
1 2 4 8 16 32
Processadores
Efic
iênc
ia 10.000
20.000100.0001.000.000
Figura 24 – Eficiência apresentada pelo algoritmo do cálculo do π
6.3 Algoritmo Trapezoidal Rule
Um algoritmo muito semelhante ao algoritmo do π é o Trapezoidal rule, que
77
calcula integral através do uso de trapézios. Tal algoritmo foi descrito em detalhes por
Pacheco (PACHECO, 1997), para demonstrar o uso da biblioteca MPI neste trabalho será
também usado esse mesmo algoritmo com a biblioteca SMS. Sendo possível então notar
algumas semelhanças e diferenças entre o SMS e o MPI.
Pode-se determinar a integral de um ponto a para b em uma função não negativa
f(x) através da área restrita por um eixo x, onde x=a e x=b. O gráfico desta função pode ser
visto na figura 25 (PACHECO, 1997).
Figura 25 - Definição de integral de uma função não negativa (PACHECO, 1997)
Uma forma de se estimar a área ou integral é dividir a região em figuras
geométricas, neste caso em trapézios, sendo que cada trapézio é a base do eixo x, e em seu
ápice existem dois pontos que juntam a figura (ver figura 26).
Todas as bases dos trapézios têm o mesmo tamanho, então com n trapézios
cada base terá o tamanho de h=(b-a)/n. Assim, o primeiro trapézio da esquerda terá um
intervalo de [a,a+h], e o próximo terá [a+h,a+2h], de forma que o (ith) i-enésimo será [a+(i-
1)h, a +ih], i=1,..., n. Pode-se simplificar tal notação de forma que ix denota a+ ih, i=0,...,n.
Então o tamanho do lado esquerdo do i-enésimo trapézio será )1( −ixf , e o lado esquerdo
será )( ixf , conforme figura 27.
∫b
adxxf )(
f(x)
y
78
Figura 26 - Usando integral para definir trapézios (PACHECO, 1997)
Assim, a área do trapézio é dada por: )]()([21
1 ii xfxfh +− , e a área total da
figura é dada pela soma de todos os trapézios:
hxfxfxfxfxf
xfxfxfxfh
xfxfhxfxfhxfxfh
nn
n
nn
)](...)()(2/)(2/)([
)](...)(2)(2)([2
)]()([21...)]()([
21)]()([
21
1210
210
12110
−
−
+++++=
++++=
++++++
Figura 27 – Trapézio (PACHECO, 1997)
Pacheco (PACHECO, 1997) propõe um método de paralelização para este
y
x
)( 1−ixf
)( ixfh
1−ix ix
)(xf
b a
f(x)
y
x
79
algoritmo que consiste em distribuir os dados entre os processadores (Partitioning Data), e
cada processador executa exatamente o mesmo processo sobre dados diferentes. No caso do
Trapezoidal rule especificamente cada processador irá computar um intervalo entre [a,b] e o
número de trapézios n. O algoritmo utilizando MPI pode ser visto na figura 28.
Figura 28 – Código do algoritmo Trapezoidal rule com MPI (PACHECO, 1997)
Observando o código do trapezoidal rule escrito para MPI tem-se da linha 1 a 3
a declaração da biblioteca de comunicação e variáveis úteis ao programa, das linhas 5 a 8 tem-
se o uso específico de funções MPI, na linha 7 tem-se uma função que atribui à variável
my_rank o número de cada processador, já a linha 8 atribui à variável p o número total de
processadores, tais dados são importantes para se construir os intervalos a serem computados
pelos processadores. Posteriormente, no código (linhas 9 a 13) são realizados cálculos
pertinentes à função trapezoidal rule que fazem justamente o cálculo referente aos sub-
valores de integral de cada processador. Por fim, na linha 14 o programa difere o processador
mestre dos escravos, isso é necessário já que o MPI normalmente faz uso de um único código
1. #include "mpi.h" 2. double Trap(double local_a, double local_b, int local_n, double h); 3. double f(double x); 4. int main(int argc, char** argv) { 5. MPI_Status status; 6. MPI_Init(&argc, &argv); 7. MPI_Comm_rank(MPI_COMM_WORLD, &my_rank); 8. MPI_Comm_size(MPI_COMM_WORLD, &p); 9. h = (b-a)/n; /* h é o mesmo em todos os processadores */ 10. local_n = n/p; /* número de trapezoids por nós */ 11. local_a = a + my_rank*local_n*h; 12. local_b = local_a + local_n*h; 13. integral = Trap(local_a, local_b, local_n, h); 14. if (my_rank == 0) { 15. total = integral; 16. for (source = 1; source < p; source++) { 17. MPI_Recv(&integral, 1, MPI_DOUBLE, source, tag, MPI_COMM_WORLD, &status); 18. total = total + integral; } 19. } else { 20. MPI_Send(&integral, 1, MPI_DOUBLE, dest, tag, MPI_COMM_WORLD); } 21. if (my_rank == 0) { 22. printf("With n = %d trapezoids, our estimate\n",n); 23. printf("of the integral from %f to %f = %23.16e\n", a, b, total); } 24. MPI_Finalize(); 25. return 0; }
80
fonte tanto para o processador mestre quanto para os escravos. Neste caso, se o processo for o
mestre (my_rank for igual a zero) ele irá atribuir o valor calculado por ele à variável de
armazenamento global (linha 15), em seguida aguardará que os processadores escravos
enviem seus resultados (linha 17) para serem também somados à variável global (linha 18).
Após todos esses passos, o nó mestre apresenta o resultado obtido (linhas 21 a 23) e finaliza o
programa, bem como o uso da biblioteca MPI (linha 24).
Para mostrar a eficiência e o grau de realismo proporcionado pela biblioteca
SMS, o algoritmo trapezoidal rule apresentado anteriormente foi reproduzido, de forma muito
semelhante ao algoritmo em MPI. Tal código pode ser observado na figura 29.
O simulador SMS possibilita que o programa a ser paralelizado seja executado
com dois códigos distintos, sendo um para o mestre e o outro para o escravo, mas é possível
desenvolver tal código utilizando apenas um código para o mestre o e escravo (como neste
caso). O código do Trapezoidal rule utilizando o SMS inicia com a declaração da biblioteca
SMS (linha 01) e logo em seguida faz a declaração de estruturas usadas para a passagem de
mensagem dentro do simulador (linhas 02 a 11). Na linha 15 é utilizada a função que
sincroniza todos os processadores para dar início à execução do programa. Devido a
biblioteca SMS não possuir uma função para identificar o número de cada processador faz-se
necessário que o processador mestre identifique cada processador (linhas 17 a 22), é claro que
isso atribui um pouco de tráfego inicial na rede de comunicação, mas é de extrema
importância para o funcionamento correto do programa, quanto à obtenção do número total de
processadores, isso pode ser feito atribuindo tal valor à variável p durante a programação
(linha 16). O restante do programa é muito parecido com o programa em MPI, exceto pelo
fato de que para enviar e receber as integrais parciais, o programa faz uso das funções send e
recv_be do SMS, que passa tais valores através das estruturas declaradas anteriormente. As
funções Trap e f foram omitidas, mas são as mesmas do algoritmo em MPI.
81
Figura 29 - Código do algoritmo Trapezoidal rule com SMS
Com essa demonstração fica claro que diferenças existem entre o SMS e o MPI,
porém são mínimas, e o objetivo principal é atingido, já que o mesmo programa que é
executado em um ambiente real como o MPI, pode ser facilmente reconstruído usando-se
rotinas do SMS.
Após construir o algoritmo e testar no simulador, inúmeros dados pertinentes à
01. #include </usr/sms/com.h> 02. struct _rank 03. { // estrutura que informa passar o número do processador 04. int meu; 05. } _rank; 06. struct _integral 07. { // 08. double num; /* intervalo integral - local */ 09. } _integral; 10. struct _integral integral; 11. struct _rank rank; 12. double Trap(double local_a, double local_b, int local_n, double h); /* Calcula a integral local */ 13. double f(double x); 14. int main(int argc, char** argv) { 15. openchanel(); /*sincroniza os processos mestre e escravo*/ 16. p=1; //numero do processador 17. for (i=0; i<p; i++) 18. {// determinar o rank de cada processador 19. rank.meu=i; 20. send(((char *)&rank), sizeof(_rank),i); 21. recv(((char *)&rank), sizeof(_rank)); } 22. my_rank=rank.meu; 23. if (rank.meu==0) {printf("Eu sou %d\n", rank.meu);} 24. else {printf(">Eu sou %d escravo\n", rank.meu);} 25. recv(((char *)&rank), sizeof(_rank)); 26. h = (b-a)/n; /* h is the same for all processes */ 27. local_n = n/p; /* So is the number of trapezoids */ 28. local_a = a + my_rank*local_n*h; 29. local_b = local_a + local_n*h; 30. integral.num = Trap(local_a, local_b, local_n, h); 31. if (my_rank == 0) { 32. total = integral.num; 33. for (source = 1; source < p; source++) { 34. recv_be(((char *)&integral), sizeof(_integral)); 35. total = total + integral.num; } 36. } else { 37. send(((char *)&integral), sizeof(_integral),dest); } 38. if (my_rank == 0) { 39. printf("With n = %d trapezoids, our estimate\n", n); 40. printf("of the integral from %f to %f = %23.16e\n", a, b, total); } 41. return 0; }
82
execução do programa são obtidos. Usando esses dados é possível obter gráficos que mostram
o tempo de execução dos problemas frente aos processadores e analisar o quão melhor se
tornou ou não o sistema.
Observando a figura 30 é possível obter-se uma impressão positiva da execução
do algoritmo trapezoidal rule frente às arquiteturas testadas, sendo que na maioria dos casos
foram obtidos ganhos de tempo de aproximadamente cinqüenta por cento em relação às
arquiteturas anteriores, como por exemplo, no problema com 2.000.000 de interações o tempo
do algoritmo com apenas 1 processador é de 170 segundos, ao se acrescentar mais um
processador a esta arquitetura obteve-se um tempo de execução de 88 segundos, um ganho de
tempo de aproximadamente 49%, dobrando mais uma vez o número de processadores da
arquitetura obteve-se um ganho de 74% em relação a arquitetura com apenas um processador
e exatamente 50% de ganho de tempo se comparado com a arquitetura com 2 processadores.
Essa média de 50% de ganho se mantém até a arquitetura com 16 processadores. Porém a
arquitetura com 32 processadores teve um ganho de tempo de 36% em relação a arquitetura
de 16 processadores, mas mesmo assim teve um ganho de tempo de aproximadamente 95%
em relação a arquitetura com apenas um processador.
A figura 31 que apresenta o speedup, representa fielmente o ganho de
desempenho apresentado pelos gráficos de tempo. Mas é possível notar ainda que o menor
problema possui uma queda na aceleração quando a arquitetura utiliza 32 processadores, isso
se dá devido ao tamanho do problema (que é pequeno neste caso). Neste caso a granularidade
do problema é muito pequena causando muito overhead na rede (LU, 1998).
Com a visualização do speedup é possível concluir que existe um bom aumento
de desempenho conforme se aumenta o número de processadores. Entretanto, se for
visualizado o gráfico referente à eficiência (figura 32) é possível notar que nem todas as
arquiteturas são totalmente eficientes, sendo que apenas a arquitetura de 16 processadores
83
mostrou que consegue atingir uma ótima relação entre o ganho de desempenho e o número de
processadores empregados para tal aceleração.
Trapezoidal Rule (n=250.000)
0
5
10
15
20
25
Processadores
Tem
po e
m S
egun
dos
12481632
Trapezoidal Rule (n=750.000)
0
10
20
30
40
50
60
70
Processadores
Tem
po e
m S
egun
do 12481632
Trapezoidal Rule (n=1.000.000)
0102030405060708090
Processadores
Tem
po e
m S
egun
dos
12481632
Trapezoidal Rule (n=2.000.000)
020406080
100120140160180
Processadores
Tem
po e
m S
egun
dos
12481632
Trapezoidal Rule (n=4.000.000)
050
100150
200250
300350
400
Processadores
Tem
po e
m S
egun
dos
12481632
Figura 30 – Tempo total de execução do Trapezoidal rule
84
Trapezoidal Rule
0
510
15
20
2530
35
1 2 4 8 16 32
Processadores
Spe
edup
250.000750.0001.000.0002.000.0004.000.000
Figura 31 – Speedup Trapezoidal rule
Trapezoidal Rule
0
0,20,4
0,6
0,8
11,2
1,4
1 2 4 8 16 32
Processadores
Efic
iênc
ia
250.000750.0001.000.0002.000.0004.000.000
Figura 32 – Eficiência do algoritmo Trapezoidal rule frente a arquitetura
6.4 Algoritmo para testes da Rede de Interconexão do Simulador SMS
Numa arquitetura paralela, a rede de interconexão tem papel fundamental sobre o
desempenho de todo sistema paralelo. Neste contexto, é relevante que a ferramenta de
simulação viabilize a investigação da arquitetura simulada em função da rede de interconexão.
Tanto a taxa de transmissão e o protocolo de controle da rede de interconexão
85
podem se tornar gargalos de desempenho para a arquitetura paralela (MATHESON, 1996;
PATTERSON, 2000).
Portanto, o estudo sobre as tecnologias de transmissão de dados em redes de
interconexão é extremamente relevante em ambientes paralelos, pois a rede tem influência
direta sobre o desempenho das aplicações. Desta forma, é importante que o projetista de
sistema paralelo possa testar no simulador qual rede de interconexão é mais adequada para a
resolução de seu problema.
Existem inúmeras possibilidades para se configurar uma rede de interconexão.
No que ser refere à topologia é possível encontrar diversas configurações como: árvore,
barramento, estrela, hiper-cubo, crossbar, malha, entre outras.
Outro fator extremamente importante no quesito rede é a tecnologia empregada
para a transmissão de dados (alguns exemplos são: Ethernet, Fast-Ethernet, Gigabit-Ethernet,
ATM, etc). Através dessas características pode-se ainda mesclar as topologias com as
tecnologias de transmissão, isso proporciona uma imensa gama de configurações. E
utilizando-se a ferramenta SMS é possível simular e analisar essas diversas configurações e
identificar a rede de interconexão mais adequada para a resolução de um determinado
problema. Da mesma forma, é necessário que haja algoritmos que viabilizem testes para a
rede de interconexão utilizada na ferramenta SMS.
O primeiro algoritmo implementado com este fim é chamado de Round-Trip, que
é um algoritmo que mede a taxa de transferência dos dados na rede de interconexão do
simulador. O programa basicamente consiste em um programa mestre (figura 33a) e outro
escravo (figura 33b). A tarefa do programa mestre é de enviar uma mensagem contendo um
número qualquer de bytes para o programa escravo, o qual irá receber essa mensagem através
de uma primitiva de comunicação de recebimento e imediatamente reenviará a mesma
mensagem para o programa mestre, o qual irá contabilizar o tempo total do tráfego da
86
mensagem. Tal programa é muito utilizado para realização de testes em redes de
interconexões reais usando MPI.
Figura 33 - Algoritmo de Round-Trip
Após a implementação do Round-Trip, o programa foi testado no simulador
utilizando topologia em barramento. Nos testes realizados, foram alteradas as freqüências dos
ciclos que a interface de rede (número de ciclos de clock em relação ao processador) utiliza
para passar a informação pela rede de interconexão. A freqüência em questão (que será
chamada de fc) é a relação dos ciclos necessários para enviar os dados de uma mensagem pela
rede, ou seja, se for colocado um valor igual a 1 (fc=1), a rede irá demorar apenas um ciclo de
clock para enviar a mensagem, ao passo que se o valor de fc for igual a 10, a mensagem levará
10 ciclos de clock para ser enviada. É importante notar que quanto menor é fc mais rápida será
a taxa de transmissão da rede e conseqüentemente quanto maior for o valor de fc mais lenta
será a taxa de transferência dos dados em relação ao processador. Observando-se a tabela 3, é
possível notar que utilizando freqüências menores o simulador apresenta taxas de
transferências maiores. Já com uma freqüência muito alta, a rede passa a ter uma taxa de
transferência menor que 1Mbps.
(a)
Entrada: Tamanho em bytes da mensagem. Saída: Taxa de transmissão da rede de interconexão em bytes por segundo (bps) T1=tempo inicial; Msg= 1000; // bytes Send (msg, escravo); Recv_be(msg); T2=tempo final; Tempo_total=T2-T1; Calcula taxa de taxa de trasferencia(); Mostra taxa de transferência em bps.
Entrada: msg (mensagem do mestre) Saída: msg (mensagem par o mestre) Recv_be(msg); Send (msg, mestre);
(b)
87
1.000 2000 4000
1 10.243.802 11.046.794 11.794.191 2 5.799.589 5.829.884 6.308.472 3 4.086.971 4.193.892 4.302.806 4 3.013.319 3.084.535 3.208.439 5 2.535.703 2.557.434 2.541.619
10 1.312.808 1.283.974 1.313.513 20 0.650653 0.667792 0.627479 30 0.440441 0.437780 0.444038 100 0.135112 0.137166 0.112469 200 0.067977 0.068447 0.069002
bps
Tabela 3 - Taxa de transferência da rede de interconexão em bytes por segundo
Os testes realizados com a rede de interconexão demonstram que a rede presente
no simulador, desempenha seu papel no envio e recebimento de mensagens. Entretanto, é
necessário que novas redes sejam implementadas possibilitando novos testes com redes de
interconexão com diferentes topologias, protocolos de controle e taxas de transmissão.
6.5 Algoritmo de ordenação Odd-Even
É muito comum tanto em aplicações científicas quanto comerciais a utilização de
métodos de ordenação de dados. Desta forma o estudo sobre paralelização de algoritmos de
ordenação é muito pertinente, e da mesma maneira faz-se necessário testar o desempenho de
tais algoritmos nas mais diversas plataformas de computação paralela, para que se obtenha um
consenso de qual algoritmo é mais indicado em determinadas situações (FRANCIS, 1988).
Define-se como um algoritmo de ordenação, o que contenha funções para
rearranjar uma lista desordenada de elementos de maneira que tais elementos fiquem
ordenados de forma crescente ou decrescente (WILKINSON, 1999). Portanto, temos
Bytes msg
fc
88
>=< naaaS ,...,, 21 que é uma seqüência arbitrária de elementos, a ordenação colocará, por
exemplo, essa seqüência de forma crescente em que >=< ''2
'1
' ,...,, naaaS , de forma que
''ji aa ≤ para 1 ≤i ≤ j ≤ n, e S’ é uma permutação de S (GRAMA, 2003).
Um exemplo de algoritmo de ordenação bem simples e muito utilizado em
programação seqüencial é o Bubble Sort, no qual o maior número da lista a ser ordenada é
movido para baixo utilizando operações de comparação e troca. Na ordenação Bubble Sort,
existe uma seqüência de números 1210 ,...,,, −nxxxx , primeiro 0x e 1x são comparados e o
maior é movido para 1x e conseqüentemente o menor irá ocupar a posição 0x . Então 1x e 2x
são comparados e o 2x irá receber o maior número, essa operação será realizada até se
atribuir o maior número à posição 1−nx . Desta forma, com n números são necessárias n-1
operações de comparações e trocas para se ordenar o arranjo, sendo que na primeira fase o
algoritmo irá posicionar o maior número no final da lista (n-1) e na próxima fase o segundo
maior número será atribuído à posição (n-2). O código seqüencial pode ser observado na
figura 34.
O algoritmo Bubble Sort é estritamente seqüencial, portanto fica difícil
paralelizar tal algoritmo, uma sugestão para a paralelização deste algoritmo é a utilização do
método de decomposição pipeline.
Figura 34 - Algoritmo Bubble Sort
Para (i=n-1; i>0; i--) Para (j=0; j<i; j++) { K=j+1; if (a[j] > a[k]) { temp=a[j] a[j]=a[k] a[k]=temp } }
89
Um outro algoritmo bem semelhante ao Bubble, porém mais fácil de paralelizar,
é o Odd-Even Sort. Este algoritmo, utiliza duas fases para ordenação: uma fase ímpar e outra
par. Na fase ímpar os números situados na posição ímpar são comparados com seus vizinhos
da direita, e da mesma forma na fase par os números situados na posição par da lista a ser
ordenada são comparados com os seus vizinhos da direita. O código do algoritmo Odd-Even é
mostrado na figura 35.
O algoritmo Odd-Even ordena n elementos em n fases (sendo n ímpar), cada qual
requer n/2 operações de comparação e troca. O algoritmo funciona da seguinte forma, sendo
>=< naaaS ,...,, 21 a seqüência a ser ordenada. Durante a fase ímpar os elementos ),( 21 aa ,
),( 43 aa , ),( 65 aa , ..., ),( 1 nn aa − são comparados e trocados. Similarmente, na fase par
compara-se e troca-se os elementos ),( 32 aa , ),( 54 aa , ),( 76 aa , ..., ),( 12 −− nn aa . Por fim, depois
de n fases os elementos estarão ordenados (ver figura 36). Uma forma de se paralelizar este
processo de ordenação consiste em executar as fases pares em paralelo e depois as fases
ímpares. Sendo que, durante a fase ímpar, apenas os processadores ímpares e seus vizinhos à
direita irão fazer o processo de comparação e troca, já na fase par apenas os processadores
identificados como par irão fazer a comparação e troca entre seus vizinhos da direita.
Figura 35 - Algoritmo de ordenação Odd-Even
Send(A, iP -1) Recv(B, iP -1) If (A<B) A=B If (i<=n-3) { Send(A, iP +1) Recv(A, iP +1) If (A>B) A=B }
Send(A, iP +1) Recv(B, iP +1) If (A<B) A=B If (i<=2) { Recv(A, iP -1) Send(A, iP -1) If (A>B) B=A }
a) programa n b) programa n+1
90
Figura 36 - Processo de ordenação utilizando algoritmo Odd-even (GRAMA, 2003)
O algoritmo de ordenação Odd-Even proposto para o simulador SMS, segue o
mesmo princípio. Com a diferença de que o arranjo será dividido pelo número de
processadores (n/p), em que n e p são múltiplos de dois. Cada nó então conterá um sub-
arranjo, durante a fase ímpar, os nós irão enviar seus sub-arranjos para seus vizinhos à direita
e os seus vizinhos à direita irão da mesma forma enviar seus sub-arranjos para seus vizinhos
ímpares da esquerda. Em posse desses sub-arranjos cada nó que compõe a operação ímpar irá
ordenar os dois sub-arranjos da seguinte forma: o nó ímpar irá ficar com os menores
elementos que compõem os dois sub-arranjos, e o vizinho à direita deste nó ímpar irá ficar
com os maiores elementos dos dois sub-arranjos (ver figura 37). O mesmo ocorre na fase par
do algoritmo. Esse algoritmo é executado em p passos (em que p é igual ao número de
processadores).
O algoritmo de ordenação Odd-Even proposto para o SMS, tem como
característica marcante o intenso uso da rede de interconexão, desta forma ele é altamente
recomendado para testes com a rede de interconexão, já que faz uso constante da rede de
interconexão para transferir os sub-arranjos a serem ordenados. A complexidade deste
Passos P0 P1 P2 P3 P4 P5 P6 P7
0 4 2 7 8 5 1 3 6
1 2 4 7 8 1 5 3 6
2 2 4 7 1 8 3 5 6
3 2 4 1 7 3 8 5 6
4 2 1 4 3 7 5 8 6
5 1 2 3 4 5 7 6 8
6 1 2 3 4 5 6 7 8
7 1 2 3 4 5 6 7 8
Tempo
91
algoritmo é apresentada por (GRAMA, 2003) e é executada em
} } ocomunicaçãcomparaçãolocalordenação
nnpn
pnTp )()(log
_
Θ+Θ+
Θ=
48476
, desta forma o tempo do algoritmo é Θ((n/p)log(n/p)).
Figura 37 - Ordenação por Odd-Even utilizada no SMS (GRAMA, 2003)
Foram realizados vários testes com o algoritmo de ordenação Odd-Even. O
algoritmo ordenou chaves com os seguintes números: 2.048, 4.096, 8.192, 16.384, 32.768 e
65.536. Analisando-se os gráficos de tempo (figura 38) decorrido para ordenação das chaves é
possível observar que em comparação com a arquitetura com um único processador a
arquitetura paralela com dois processadores teve um ganho de desempenho de
aproximadamente 50% em todas as arquiteturas simuladas (que são: 1, 2, 4, 8, 16 e 32).
Porém, as arquiteturas paralelas com 4, 8, 16 e principalmente 32 processadores não
mantiveram o mesmo nível de ganho de tempo da arquitetura com 2 processadores, chegando
até mesmo no caso mais extremo (32 processadores) a obter um tempo pior do que o obtido
pela arquitetura anterior (16 processadores).
A queda de desempenho na ordenação entre as arquiteturas de 16 e 32
processadores pode ser vista na figura 39 que representa o speedup. Analisando essa figura é
FASE 1
FASE 2
FASE 3
FASE 4
3 9 4 2 6 9 1 5 8 3 6 9 0 2 7 8 P1 P2 P3 P4
1 2 3 4 5 6 9 9 0 2 3 6 7 8 8 9
1 2 3 4 0 2 3 5 6 6 9 9 7 8 8 9
0 1 2 2 3 3 4 5 6 6 7 8 8 9 9 9
92
possível notar que todas as arquiteturas obtiveram ganhos de desempenho exceto a de 32
processadores que apresenta queda de desempenho. Este pior caso se dá por conta do
algoritmo usar muito a rede de interconexão sendo necessário a comunicação de 32 processos
para executar a ordenação, o que evidentemente aumenta o overhead da rede.
A figura 40 confirma os dados anteriores mostrando de que a arquitetura não se
adapta adequadamente a este algoritmo principalmente com os tamanhos de problemas
testados, a eficiência apresenta quedas constantes cada vez que se aumenta o número de
processadores arquitetura.
Odd-Even Sort (n=2048)
0
12
34
5
67
8
Processadores
Tem
po e
m S
egun
dos
12481632
Odd-Even Sort (n=4096)
0
24
6
8
1012
14
16
Processadores
Tem
po e
m S
egun
dos
12481632
Odd-Even Sort (n=8192)
0
510
15
20
2530
35
40
Processadores
Tem
po e
m S
egun
dos
12481632
Odd-Even Sort (n=16384)
0102030405060708090
Processadores
Tem
po e
m S
egun
dos
12481632
Odd-Even Sort (n=32768)
0
50
100
150
200
Processadores
Tem
po e
m S
egun
dos
12481632
Odd-Even Sort (n=65536)
050
100150200250300350400450
Processadores
Tem
po e
m S
egun
dos
12481632
Figura 38 – Tempo total de execução do Odd-Even sort
93
Odd-Even Sort
0
2
4
6
8
10
1 2 4 8 16 32
Processadores
Spe
edup
204840968192163843276865536
Figura 39 – Speedup do Odd-Even sort
Odd-Even Sort
0
0,2
0,4
0,6
0,8
1
1,2
1 2 4 8 16 32
Processadores
Efic
iênc
ia
204840968192163843276865536
Figura 40 – Eficiência do Odd-even sort
Tais informações demonstram a ineficiência do algoritmo, já que este utiliza de
forma muito constante a rede de interconexão e demanda pouco processamento. Tal
informação pode ser melhor representada pela figura 41, que mostra o grande uso da rede
interconexão pelos processadores. É possível notar o funcionamento do algoritmo no qual os
nós das extremidades são os que trocam menos informações que os demais nós que compõem
a arquitetura (figura 37). Uma melhor comparação do uso intenso da rede de interconexão é
94
possível se for comparado o gráfico de uso da rede do algoritmo Odd-Even (figura 41) com o
algoritmo do cálculo do pi (figura 42). Sendo que o algoritmo do pi utiliza o nó mestre para
enviar informações iniciais aos escravos e depois recebe todas as informações no final da
execução do algoritmo, o que é claramente demonstrado no gráfico. Desta forma, o algoritmo
do pi faz pouco uso dos canais de comunicação o que não ocorre no algoritmo de ordenação.
Como o algoritmo Odd-Even tem como objetivo principal o teste da rede de
interconexão, tal algoritmo atinge este objetivo claramente. Desta forma, quando forem
implementadas redes mais eficazes no simulador, tal algoritmo servirá como ferramenta de
avaliação das redes.
Envio de Mensagens do Odd-Even Sort
0 50000 100000 150000 200000 250000 300000
Proc
essa
dore
s
Bytes
012345678
Recebimento de Mensagens do Odd-Even Sort
0 50000 100000 150000 200000 250000 300000
Pro
cess
ador
es
Bytes
012345678
Figura 41 – Uso da rede de interconexão do algoritmo Odd-Even sort
Envio de mensagens cálculo do pi
0 20 40 60 80 100 120
Pro
cess
ador
es
Bytes
012345678
Recebimento de mensagens cálculo do pi
0 10 20 30 40 50 60 70
Pro
cess
ador
es
Bytes
012345678
Figura 42 – Uso da rede de interconexão do algoritmo de cálculo do π
6.6 Simulação de outras arquiteturas com o SMS
O simulador foi desenvolvido com o intuito principal de possibilitar a alteração
95
dos vários componentes físicos da arquitetura paralela de forma simples e eficiente. Para
demonstrar como isso é feito, essa seção apresenta algumas simulações com diferentes
configurações arquiteturais.
O SMS possibilita a alteração de inúmeros itens de hardware de um processador
superescalar, de forma que é possível configurar e simular vários aspectos. Aqui são
apresentados alguns.
A simulação no SMS é dada via linha de comando, sendo possível passar ao
simulador o número de processadores, as opções de simulações e o arquivo que contém os
programas a serem executados pelos processadores do simulador. Então, um comando no
simulador seria sms 2 odd-even, neste caso foram omitidas as opções, mas elas normalmente
são utilizadas e permitem alterar a arquitetura. As opções mais importantes são:
- redir:sim <nome do arquivo> - Redireciona a saída do resultado da simulação
para um arquivo;
- redir:prog_00 <nome do arquivo> - Redireciona a saída de um processador,
neste caso, o 00 para um arquivo; se for colocado –redir:prog_01 a saída coletada será a do
processador 01, e assim por diante. Isso é valido para as opções que envolvem vários
processadores.
- bpred_00 <tipo> - Neste caso é alterado o esquema de previsão de desvio,
podendo-se alterar o tipo por: nottaken, taken, perfect, bimod, 2lev e comb.
- cache:dl1_00 dl1_00:128:32:4:1 – Esta opção altera as propriedades da cache
de dados primária. Após o comando são passados alguns parâmetros, que são: o nome da
cache, dl1 neste caso, seguido pelo tamanho da cache, tamanho do bloco da cache,
associatividade da cache, e por fim a estratégia de substituição utilizada, que pode ser 1 para
LRU, f para FIFO e r para random. Isso é válido para todas as caches.
-cache:dl2_00 ul2_00:1024:64:4:1 – Idem à opção anterior, mas para cache
96
secundária.
-cache:il1_00 il1_00:512:32:1:1 – Nesta opção altera-se a cache primária de
instrução. Como na cache de dados, aqui também existe uma cache secundaria que pode ser
configurada da mesma forma.
-mem:width_00 8 – Largura do barramento de acesso à memória em bytes, neste
caso 8.
-res:ialu_00 4 - Número total de unidades lógicas e aritméticas inteiras.
-res:fpalu_00 4 – Número total de unidades lógicas e aritméticas de ponto
flutuante disponíveis, neste caso como o anterior são 4.
-inetwork bus:4:3 – Configuração da rede de interconexão, neste caso a rede
tem topologia barramento, o protocolo utilizado (atualmente só existe um no simulador) e por
fim a freqüência da rede em relação ao processador, sendo que quanto menor a freqüência
mais rápida é a rede em relação ao processador.
Todas as possíveis alterações e configurações podem ser vistas em qualquer
arquivo de simulação gerado durante as simulações no SMS.
Um exemplo de alteração de simulação é trocar o tamanho da memória cache, tal
experimento foi feito com o algoritmo do π, apresentado a seguir.
No exemplo do algoritmo do π foi modificado o tamanho da memória cache de
dados de todos os processadores, sendo então colocada em cada processador uma cache de
dados com o tamanho de 4096 bytes (ver figura 43), sendo que o simulador tem como padrão
uma cache de dados com tamanho de 128 bytes, que foi o tamanho utilizado nas simulações
com o algoritmo do cálculo do π anteriormente.
Figura 43 – Linha de comando para executar o programa de cálculo do π com cache de dados de tamanho de 4096
/usr/sms/sms 3 -cache:dl1_00 dl1:4096:32:1:l -cache:dl1_01 dl1:4096:32:1:l -redir:sim PIParalelo-d4096-10.000-3.sim PIP
97
Os testes realizados com tamanho de memória cache de dados de 4096 foram
devidamente comparados com os testes anteriores (figura 22), e apresentaram um pequeno
ganho de desempenho (ver figura 44).
O aumento de desempenho proporcionado pela arquitetura possibilitou até
mesmo uma melhora de eficiência da arquitetura conforme pode ser visto na figura 45 o que
não havia ocorrido com a mesma arquitetura com memória cache de 128 bytes.
Essas possibilitades de alteração de configuração, viabilizam a identificação da
melhor configuração arquitetural para cada tipo de aplicação.
Algoritmo cálculo do pi com cache alterada
0
5
10
15
20
25
1 2 4 8 16 32
Processadores
Spe
edup
10.000 cache 128100.000 cache 12810.000 cache 4096100.000 cache 4096
Figura 44 – Speedup do π com alteração de cache de dados
Outro algoritmo submetido a uma mudança de arquitetura simulada foi o
Trapezoidal rule. Para este algoritmo foi alterado o previsor de desvios, trocando o bimod
(padrão do simulador) para o algoritmo 2lev (figura 46).
Tal modificação foi realizada em todos os processadores, mas poderia ser feita
individualmente simulando ambientes heterogêneos, para isso seria necessário especificar via
linha de comando, por exemplo: sms 2 –bpred_00 bimod –bpred_01 2lev trapezoide.
98
Algoritmo cálculo do pi com cache alterada
0
0,2
0,4
0,60,8
1
1,2
1,4
1 2 4 8 16 32
Processadores
Efic
iênc
ia 10.000 cache 128100.000 cache 12810.000 cache 4096100.000 cache 4096
Figura 45 – Eficiência do π com alteração de cache de dados
Figura 46 - Linha de comando que dispara o simulador SMS com alterações no previsor de
desvio
Tais mudanças no previsor de desvios, proporcionaram mudanças sutis no
desempenho do algoritmo frente a arquitetura. Os resultados podem ser observados na figura
47.
Por fim, como o algoritmo de ordenação Odd-Even proposto tem como
característica marcante o intenso uso da rede de interconexão, foram realizadas simulações
com duas arquiteturas, uma com uma rede de interconexão com 1Mb/s de largura de banda e
outra com 10Mb/s. A figura 48 mostra o tempo de execução da simulação para essas
configurações de rede.
#sms 2 -bpred_00 2lev -bpred_01 2lev -redir:sim trapezoide-2lev-44440.000-2.sim trapezoide
99
Alteração do sistema de previsão de desvio do algoritmo Trapezoidal rule
0
5
1015
20
25
30
1 2 4 8 16 32
Processadores
Spe
edup
1.000.000 2lev2.000.000 2lev4.000.000 2lev1.000.000 bimod2.000.000 bimod4.000.000 bimod
Alteração do sistema de previsão de desvio do algoritmo Trapezoidal rule
0
0,2
0,4
0,6
0,8
1
1,2
1 2 4 8 16 32
Processadores
Efic
iênc
ia
1.000.000 2lev2.000.000 2lev4.000.000 2lev1.000.000 bimod2.000.000 bimod2.000.000
Figura 47 – Speedup e eficiência do algoritmo Trapezoidal rule com previsor de desvio alterado
Através da simulação e dos dados gerados pode-se notar que a rede de
interconexão teve influência no desempenho do algoritmo de ordenação odd-even.
Assim, é possível constatar que o simulador SMS fornece uma maneira simples e
fácil de alterar a arquitetura simulada, possibilitando que um mesmo algoritmo seja testado
em inúmeros ambientes paralelos.
100
Odd-Even sort com rede de interconexão de 1 Mb/s(n=32768)
0
50
100
150
200
Processadores
Tem
po e
m s
egun
dos
12481632
Odd-Even sort com rede de interconexão de 10 Mb/s (n=32768)
0
50
100
150
200
Processadores
Tem
po e
m s
egun
dos
12481632
Odd-Even sort com rede de interconexão de 1 Mb/s (n=65536)
0
100
200
300
400
500
Processadores
Tem
po e
m s
egun
dos
12481632
Odd-Even sort com rede de interconexão de 10 Mb/s (n=65536)
0
100
200
300
400
500
Processadores
Tem
po e
m s
egun
dos
12481632
Figura 48 - Elapsed Time do algoritmo Odd-Even com duas redes de interconexão
101
7 CONCLUSÃO
Este capítulo resume as conclusões embasado nas discussões e dados expostos
nos capítulos precedentes.
Este trabalho utilizou a ferramenta de simulação SMS implementada por
(SANDRI, 2004), que atualmente simula ambientes paralelos de memória distribuída e
possibilita diversas configurações de arquiteturas.
Mas, tal ferramenta não possuía algoritmos para testes e simulações, assim,
este trabalho apresenta como contribuição o desenvolvimento de algoritmos de testes para em
conjunto com o simulador, viabilizar o estudo de arquiteturas paralelas em uma variedade de
configurações. Os algoritmos desenvolvidos neste trabalho possibilitam também que a
ferramenta seja usada para apoio ao ensino de arquiteturas paralelas, já que com os algoritmos
implementados os estudantes de arquiteturas paralelas podem primeiramente entender como
funciona um algoritmo paralelo antes de começar a implementar os seus próprios algoritmos.
Após o desenvolvimento dos algoritmos de testes propostos foram executados
intensos exercícios de simulação com a ferramenta SMS. Esses exercícios de simulação
mostraram que a ferramenta viabiliza a implementação de algoritmos paralelos e a análise de
desempenho de arquiteturas paralelas com diversas configurações de arquiteturas
computacionais.
Quanto a ferramenta SMS, durante os testes com os algoritmos foi possível notar
que a mesma permite realizar simulações, nas quais é possível alterar características físicas de
baixo nível como: larguras de barramentos internos ao processador, tamanho da memória
principal, configurações de memória cache, previsores de desvios, e unidades funcionais,
entre outras. Permitindo assim o estudo do paralelismo implícito, através do emprego de
102
processadores superescalares. E da mesma forma possibilita configurar características de mais
alto nível, tais como: número de processadores, topologia da rede de interconexão, protocolos
de comunicação, entre outras. Permitindo o estudo do paralelismo explícito inerente às
arquiteturas que fazem uso de memória distribuída e passagem de mensagem.
Quanto aos algoritmos desenvolvidos, eles possuem um papel fundamental, pois
em conjunto com o simulador, fornecem uma maneira fácil de testar diversas arquiteturas
explorando de forma eficiente os elementos físicos que compõem uma arquitetura paralela.
Permitem da mesma forma investigar parâmetros de desempenho importantes em arquiteturas
paralelas. Os algoritmos implementados permitem ainda que usuários que estejam iniciando
suas pesquisas em computação paralela, possam primeiramente analisar os algoritmos já
implementados, estudando-os e alterando-os, para posteriormente desenvolver seus próprios
algoritmos.
Tais algoritmos também permitiram validar a ferramenta, mostrando que ela é
uma ótima alternativa para testes de avaliação de desempenho em ambientes paralelos e como
ferramenta de auxílio ao ensino e pesquisa em Arquiteturas Paralelas.
103
8 TRABALHOS FUTUROS
A ferramenta de simulação já está validada e operacional. Permite simulações de
memória distribuída, fazendo uso de passagem de mensagem.
Diversos aspectos ainda podem ser investigados, suscitando trabalhos futuros
envolvendo a ferramenta de simulação e algoritmos paralelos.
O primeiro passo para continuidade do presente trabalho poderá focar a
implementação de memória compartilhada, o que tornará o SMS uma ferramenta de
simulação completa. Isso demandará um outro trabalho que consistirá no desenvolvimento de
algoritmos para testar a memória compartilhada assim que esse módulo for desenvolvido.
Um terceiro trabalho futuro poderá ser o desenvolvimento do módulo de
Interface Gráfica. Esse módulo facilitará as simulações, já que este possibilitará uma melhor
interação entre o usuário e a ferramenta, e facilitará o controle das simulações. A Interface
Gráfica também deverá fornecer saídas de simulações mais atrativas e representativas
(gráficas) dando uma melhor visão do comportamento da arquitetura.
Ainda há a possibilidade de se desenvolver os mesmos algoritmos deste trabalho,
mas voltados para outros simuladores de arquiteturas paralelas. Isso viabilizará análises
comparativas.
É interessante que o simulador no futuro apresente o tempo de execução
individual de cada processador, pois atualmente ele apresenta um tempo único de execução
para toda arquitetura.
Outro tópico de pesquisa para trabalhos futuros está relacionado às Redes de
Interconexão. Novas redes podem ser implementadas com diferentes topologias e protocolos
de controle.
104
REFERÊNCIAS
AUSTIN, Todd; LARSON, Eric; ERNST, Dan. SimpleScalar: An Infrastructure for Computer System Modeling. IEEE Computer. v. 35, n. 2, p. 59-67, feb.2002. ALMASI, G. S.; GOTTLIED, A. Highly Parallel Computing. 2. ed., Redwood City: The Benjamin/Cummings Company, 1994. BADER, David A.; JÁJÁ, Joseph.; SIMPLE : A Methodology for Programming High Performance Algorithms on Cluster of Symmetric Multiprocessors (SMPS) – (Preliminary Version). Institute for Advanced Computer Studies, University of Maryland, College Park, mai.1997. BADER, David A.; JÁJÁ, Joseph.; Pratical Parallel Algorithms for Dynamic Data Redistribution, Median Finding, and Selection. Institute of Advanced Computer Studies, and Department of Electrical Engineering, University of Maryland, College Park. Disponível em: http://ipdps.eece.unm.edu/1996/PAPERS/S08/DBADER8/DBADER8.PDF, Acesso em: mai.2004. BAGRODIA, Rajive L; TAKAI, Mineo; JHA, Vikas. Performance Evaluation of Conservative Algorithms in Parallel Simulations Languages. IEEE Transactions on Parallel and Distributed Systems, v. 11, n. 4. 2000. BAGRODIA, Rajive; MARTHUR, Sharad. Efficient Implementation of High-Level Parallel Programs. ACM Press. v. 26, n. 4, p. 142-153, abr.1991. BAGRODIA, Rajive; et al. Performance prediction of large parallel applications using parallel simulations. ACM Press, pg 151-162. 1999. BAILEY, David H.; BARSZCZ, Eric; DAGUM, Leonardo; SIMON, Horst D. NAS Parallel Benchmark Results. IEEE, pg 43-51. Fev 1993. BREWER, Eric A. et al. Proteus: A High-Performance Parallel-Architecture Simulator. Technical Report MIT/LCS/TR-516, Cambridge, set.1991. BURGER, Doug.; AUSTIN, Todd M. The Simplescalar Tool Set - Version 2.0. Technical Report 1342, University of Wisconsin-Madison Computer Science Department, jun.1997. CALZAROSSA, Maria; MASSARI, Luisa; TESSERA, Daniele. A methodology towards automatic performance analysis of parallel applications. Sience Direct, Ago 2003. CHANG, H. S. Tcheng; HUANG, K. Performance of a Weather Prediction Model on Parallel Machines, Proceedings of High Performance Computing – Grand Challenges in Computer Simulation (HPC-99), San Diego, California, (April 1999), pp.101-104, 1999. CHOI, Hyeong-Ah; NARAHARI, b. Efficient Algorithms for Mapping and Partitioning a
105
Class of Parallel Computations. Journal of Parallel and Distributed Computing 19, pg 349-363. Washington, 1993. CHOI, Jaeyoung. A New Matrix Multiplication Algorithm on Distributed-Memory Concurrent Computers. Concurrency: Pratice and Experience, v.10, n. 8, p. 655-670. 1998. CORMEN, Thomas H.; et al. Algoritmos Teoria e Prática Tradução da 2o Edição Americana. 2 ed., Rio de Janeiro: Ed. Campus, 2002. CREMONESI, Paolo; ROSTI, Emilia; SERAZZI, Giuseppe; SMIRNI, Evgenia. Performance evaluation of parallel systems. Parallel Computing 25. 1999. DUJMOVIC, J; DUJMOVIC, I. Evolution and evaluation of SPEC benchmarcks. ACM Press, pg 2-9. 1998. EAGER, Derek L.; ZAHORJAN, John; LAZOWSKA, Edward D. Speedup Versus Efficiency in Parallel Systems. IEEE transactions on Computer, vol 38, n 3, mar 1989. EECKHOUT, Lieven; BOSSCHERE, Koen De. Efficient simulation of trace samples on parallel machines. Sicence Direct, Parallel Computing. Fev 2004. EWING, T.; TENTNER, A. “A Scaleable Architecture for the Modeling and Simulation of Intelligent Transportation System”, Proceedings of High Performance Computing Symposium – Grand Challenges in Computer Simulation (HPC-1999), San Diego, California, pp.170-174. Abr 1999. FLYNN, M. Very high-speed computing system. Proceeding of the IEEE. n 54. P.1901-1909. Dez 1966. FRANCIS, Rhys S.; MATHIESON, Ian D. A benchmark Parallel Sort for Shared Memory Multiprocessors. IEEE Transactions on Computers, vol 37, n 12. Dez 1988. GRAMA, Ananth Y.; GUPTA, Anshul; KUMAR, Vipin. Measuring the Scalability of Parallel Algorithms and Architectures. IEEE Parallel & Distributed Technology, pg 12-21. 1993. GRAMA, Ananth.; GUPTA, Anshul.; KARYPIS, George.; KUMAR, Vipin. Introduction to Parallel Computing. 2 ed. Ed Addison Wesley, 2003. GUPTA, Anshul; KUMAR, Vipin. Performance Properties of Large Scale Parallel Systems. Journal of Parallel and Distributed Computing 19. Minnesota, 1993. GUTZMANN, Michael M; WEPER, Ralph. Classification Approaches for Parallel Architectures. Berichte zur Rechnerarchitektur, v. 2, n. 19, FSU – Friedrich-Schiller-Universitat, Jena, 1996. GUSTAFSON, John L. Reevaluating Amdahl’s Law. Communications of the ACM, vol 31, n 5, pg 532-533. Mai 1988. HENNESSY, John L.; PATTERSON, David A. Arquitetura de Computadores: Uma
106
Abordagem Quantitativa. 3 ed. Rio de Janeiro. Ed Campus, 2003. HERROD, S.A. “Tango Lite: A Multiprocessor Simulation Environment”. Stanford University. 1993. HOGANSON, Kenneth E. Workload Execution Strategies and Parallel Speedup on Clustered Computers. IEEE Transactions on Computers, vol 48, n 11. Nov 1999. KUMAR, Vipin; GUPTA, Anshul. Analysis of Scalability of Parallel Algorithms and Architectures: A Survey. ACM, pg 396-405. 1991. LAINE, Jean Marcos. Desenvolvimento de Modelos para Predição de Desempenho de Programas Paralelos MPI. São Paulo: USP, 2003. LU, N.P; CHUNG, C.P. Parallel exploitation in superscalar multiprocessing. IEEE Proc.-Comput. Digit. Tech, vol 145, n 4. jul 1998. MAGDIC, D. Limes: A Multiprocessor Simulation Environment for PC Platforms. In: Proceedings of the 3rd International Conference no Parallel Processing and Applied Mathematics (PPAM-99), Kazemiers Dolny, Poland, set.1999. MANJIKIAN, Naraig. More Enhacements of the Simplescalar Tool Set. ACM. Sigarch Computer Architecture News. v. 29, ed. 4, p. 5-12, set.2001. MATHESON, Lesley R.; TARJAN, Robert E. Analysis of Multigrid Algorithms on Massively Parallel Computers: Architectural Implications. Journal of Parallel and Distributed Computing 33. New Jersey, 1996. MATLOFF, Norman; RICH, Kevin. MulSim Multiprocessor Simulator. University of California. Disponivel em: http://heather.cs.ucdavis.edu/~matloff/MulSim/MulSimDoc.html. Acessado em: Jan 2005. NGUYEN, A.T.; MICHAEL, M.; SHARMA, A; TORRELLAS, J. “The Augmint Multiprocessor Simulation Toolkit for Intel x86 Architectures”. University of Illinois and University of Rochester. 1996. O’LEARY, Dianne P.; STEWART, G.W. Data-Flow Algoritms for Parallel Matrix Computations. Communications of the ACM, v. 28, n. 8, p. 840-853, ago.1985. PACHECO, Peter S.; Parallel Programming With MPI. California: Ed. Morgan Kaufmann Publishers, Inc. San Francisco, 1997. PAI, V.S.; RANGANATHAN, P.; ADVE, S.V. RSIN: Na Execution-Drive Simulation for ILP-Based Shared-Memory Multiprocessors and Uniprocessor. In: Proceedings of The 3rd Workshop on Computer Architecture Education, feb.1997. PATTERSON, David A.; HENNESSY, John L.; Organização e Projeto de Computadores – A Interface Hardware/Software. 2 ed., Rio de Janeiro: ed. LTC, 2000. SANDRI, A.L; GONÇALVES, R.A.L; MARTINI, J.A. SMS- Tool for Development and Performance Analysis of Parallel Applications. Annual Simulation Symposium. pg 196. 2004.
107
SMITH, James E.; SOHI, Gurindar. The Microarchitecture of Superscalar Processor. In: Proceedings of the IEEE. n 83, pg 1609-1624. Dez.1995. SUN, Xian-He; NI, Lionel M. Another veiw on parallel speedup. IEEE, pg 324-333. 1990. SUNADA, D.; GLASCO, D.; FLYNN, M. ABSS v2.0: a SPARC Simulation. Technical Report CSL-TR-98-755, Standford University, 1998. TANENBAUM, Andrew S. Organização Estruturada de Computadores. 4 ed., Rio de Janeiro: Ed. LTC, 2001. TROPPER, Carl. Parallel Discrete-Event Simulation Applications. Journal of Parallel and Distributed Computing 62, pg 327-335. 2002. VEENSTRA, J.E; FOWLER R.J. “MINT Tutorial and User Manual”. The University of Rochester. 1993. WAHEED, Abdul; ROVER, Diane T. Performance Visualization of Parallel Programs. IEEE, pg 174-182. 1993. WILKINSON, Barry.; ALLEN, Michael. Parallel Programming. 2ed., London: Ed. Pearson Prentice Hall, 1999. WOO, S.C; Ohara, M; TORRIE, E.; SINGH, J.P.; Gupta, A. The SPLASH-2 Programs: Characterization and Methodological Considerations. In Proceedings of the 22nd International Symposium on Computer Architecture, pages 24-36, Santa Margherita Ligure, ACM, Jun 1995. WOODWARD, P.R., “Perspectives on Supercomputing: Three Decades of Change”, IEEE Computer, Vol.29, No.10, pp.99-111. Out 1996. ZARGHAN, Mehdi R. Computer Architecture Single and Parallel Systems. 1 ed., New Jersey: Ed. Prentice Hall. 1995. ZHANG, Xiaodong; YAN, Yong; HE, Keqiang. Latency Metric: An Experimental Method for Measuring and Evaluating Parallel Program and Arquitecture Scalability. Journal of Parallel and Distributed Computing 22. 1994.
108
ANEXO A
Manual de Instalação do SMS
Segue neste trabalho todos os passos necessários para a instalação do conjunto de
ferramentas, que fazem parte do simulador de multiprocessadores de alto-desempenho
denominado SMS (Simulador de Multiprocessadores Superescalares), o qual é de licença
gratuita e pode ser publicamente avaliado.
O SMS, tem como base o núcleo do simulador SimpleScalar, e permite a configuração
de diferentes modelos arquiteturais paralelos e distribuídos.
Como o SMS é baseado no Simplescalar, faz-se necessário antes de instalar o SMS,
instalar o simplescalar, maiores informações sobre o Simplescalar podem ser obtidas no site
www.simplescalar.com. Porem será apresentado abaixo uma breve descrição do simplescalar
bem como a sua instalação.
A distribuição e uso do simulador Simplescalar possui somente duas restrições que
são: (1) a notificação dos direitos autorais tem que acompanhar todas as ferramentas e (2) é
estritamente proibido que terceiros coloquem restrições a qualquer ferramenta do simulador
mesmo que esta tenha sido melhorada ou incrementada. Então é permitido copias e
modificações e redistribuição do conjunto de ferramentas que compõem o SimpleScalar,
desde que algumas regras sejam respeitadas, tal como: o simulador é gratuito para uso não-
comercial, e todas as distribuições (mesmo as alteradas) tem de levar com sigo os direitos
autorais.
É possível obter o simulador e suas respectivas ferramentas, através do World Wide
Web (www.simplescalar.com) ou por ftp (ftp://ftp.cs.wisc.edu/sohi/code/simplescalar/), onde
nestes podem ser encontrados os seguintes arquivos:
• simplesim.tar.gz - Este arquivo contem o simulador propriamente dito. Este arquivo
é necessário para a instalação do simulador.
• Simpleutils.tar.gz – Contem os GNU binutils recompilados para a arquitetura
SimpleScalar. Esses utilitários não são requeridos para executar o simulador. Mas é
necessário para compilar seus próprios benchmark binários do SimpleScalar.
• Simpletools.tar.gz – Contem o compilador GNU e bibliotecas necessárias para criar
benchmarks binários (GCC, glibc e f2c), como também pré-criar versões das
bibliotecas big e little-endian.
109
• Simplebench.big.tar.gz – Contem um conjunto de benchmark binários SPEC95,
compilados para arquitetura SimpleScalar sendo executado em computadores big-
endian.
• Simplebench.little.tar.gz – igual ao Simplebench.big.tar.gz, só que é executado em
computadores little-endian.
Os arquivos virão com extensões tar.gz ou tgz, onde os arquivos que contenham estas
extensões, devem ser descompactados utilizando, por exemplo, o comando: tar –zxvf “nome
do arquivo”, em um diretório especifico (ex. /home/SimpleScalar/).
Depois de descompactar os arquivos pertinentes ao SimpleScalar, dever-se-á ter os
seguintes subdiretórios:
• simplesim-x – no qual o x, é a versão do simulador, por exemplo, o SimpleScalar 2.0
devera gerar o seguinte diretório simplesim-2.0. Este diretório conterá os códigos
fontes principais do simulador, scripts de suporte e pequenos benchmarks para testes.
• binutils-x – da mesma forma que o simplesim, o x representa a versão, que poderia
ser binutils-2.5.2. Neste diretório, está contido códigos binários GNU, reportados
especialmente para a arquitetura SimpleScalar.
• ssbig-na-sstrix – é o diretório raiz no qual os utilitários big-endian dos utilitários
SimpleScalar e ferramentas de compilação serão instalados. O pacote descompactado
conterá cabeçalhos de arquivos e uma copia pré-compilada do libc e um arquivo
objeto necessário.
• sslittle-na-sstrix – o mesmo que o ssbig-na-sstrix, só que este armazena a versão
little-endian dos utilitários SimpleScalar.
• gcc-x – o x deve ser substituído pela versão do arquivo, (ex. gcc-2.6.3). Este arquivo
contem o compilador C GNU, focado para a arquitetura SimpleScalar.
• glibc-x – idem aos itens a cima no qual o x deve ser substituído pela versão, tal como,
glibc-1.09, se for essa a versão. Este arquivo descompactado contem bibliotecas
GNU, portadas para a arquitetura SimpleScalar.
• f2c-1994.09.27 – O release de 1994 da AT&T Bell Labs’ para o tradutor do
FORTRAN para códigos em C.
• spec95-big – benchmark do SPEC95, pre-compilado para o SimpleScalar (na versão
big-endian).
• spec95-little – igual ao spec95-big só que na versão little-endian.
110
Instalação do Simplescalar
Passo(1) Baixar do site www.simplescalar.com ou do ftp
ftp://ftp.cs.wisc.edu/sohi/code/simplescalar/, os seguintes arquivos: gcc-2_7_2_3_ss_tar.gz simplesim-3v0c.tgz simpleutils-990811_tar.gz
Note que as versões dos arquivos encontrados no site podem ser diferentes desta, o que
deixaria os arquivos com nomes diferentes.
Passo(2) Descompacte os arquivos, utilizando o seguinte comando: tar –zxvf gcc-2_7_2_3_ss_tar.gz tar –zxvf simplesim-3v0c.tgz tar –zxvf simpleutils-990811_tar.gz
Depois de executar cada um desses comandos será criado um conjunto de diretórios e
subdiretórios e a partir destes podemos dar inicio a instalação.
Passo(3) Supondo que todos os arquivos acima foram copiados e descompactados no seguinte
diretório /home/SimpleScalar/, acesse o seguinte diretório: cd /home/SimpleScalar/simpleutils-990811
Então dentro deste diretório execute o seguinte comando: ./configure --host=i586-pc-linux --target=sslittle-na-sstrix --with-gnu-as --with-gnu-ld --prefix=/home/SimpleScalar/
Onde este comando irá gerar o arquivo Makefile adequado à instalação em questão.
Uma observação a ser feita sobre o comando acima, é que a identificação do host “i586-pc-
linux” pode ser alterada de acordo com a compatibilidade do sistema. A sintaxe geral é “i#86-
*-linux”, na qual # pode ser 2, 3 4, 5, 6 ou outra conforme a plataforma em uso e * pode ser
uma string qualquer que melhor represente o nome da sua plataforma. Ainda neste comando o
target “sslittle-na-sstrix” pode ser substituído por “ssbig-na-sstrix”, se for o caso de se utilizar
à plataforma big-endian ao invés da little-endian.
111
Passo (4) Após a execução do passo anterior deve-se executar o seguinte comando no mesmo
diretório: make
Passo (5) O passo cinco consiste em executar o comando: make install
Passo (6) Para execução dos passos seguintes faz-se necessário a mudança de diretório: cd /home/SimpleScalar/simplesim-3.0
Passo (7) Este passo requer a execução do comando a seguir: make config-pisa
Passo (8) Execute o comando: make
Somente as execuções dos passos acima já serão suficientes para a execução do
simulador Simplescalar, porem se, for desejável implementar e compilar benchmarks faz se
necessário à execução dos passos descritos a seguir.
Em algumas instalações do SimpleScalar, no RedHat Linux 9, foram detectados
alguns erros durante a execução dos passos acima, o erro consiste em mensagens referentes
aos arquivos eval.h e range.h, onde a correção desses erros, se da alterando os seguintes
arquivos:
Editar o arquivo eval.h e incluir as seguintes linhas que estão em negrito: linhas 17. #include <stdio.h> 18. #include <stdlib.h> 19. #include <string.h> 20. #if defined(__CYGWIN32__) 21. #include <errno.h> 22. #else 23. #include <errno.h> 24. #endif
Editar o arquivo range.h e incluir as seguintes linhas: linhas 19. #include <stdio.h> 20. #include <stdlib.h> 21. #include <string.h> 22. #if defined(__CYGWIN32__) 23. #include <errno.h>
112
24. #else 25. #include <errno.h> 26. #endif
Passo (9) Após a execução dos passos anteriores faz se necessário os passos a seguir para que
o usuário possa criar seus próprios benchmarks, para o passo 10 entre no seguinte diretório: cd /home/SimpleScalar/gcc-2.7.2.3
Passo (10) Execute o comando abaixo para criar o Makefile: ./configure --host=i586-pc-linux --target=sslittle-na-sstrix --with-gnu-as --with-gnu-ld --prefix=/home/SimpleScalar/
As mesmas considerações feitas no passo 3 são validas neste passo.
Atenção nos passos 11 e 12 a seguir podem surgir erros, que pode ser visto abaixo: _eprintf ./liggcc2.c:1419: stdio.h: No such file or directory make: *** [libgcc2.a] Error 1
Para a correção deste erro, a faz se necessário a alteração na linha 253 no arquivo Makefile
onde esta linha deve ser mudada para: LIBGCC2_INCLUDES = -I/usr/include
Depois desta alteração é possível executar os passos restantes sem maiores problemas.
Passo (11) Execute o comando: make LANGUAGES=c
Passo (12) Para terminar a instalação execute o comando: make install LANGUAGE=c
Com isto a instalação estará completa, porem se durante a instalação pode ter surgido outros
erros. Um outro erro que pode ser encontrado na instalação, é o que segue: _divdi3 ./libgcc2.c: In function `__udivmoddi4’: ./libgcc2.c: 484: `BITS_PER_UNIT’ undeclared (first use this function) ./libgcc2.c: 484: (Each undeclared identifier is reported only once ./libgcc2.c: 484: for each function it appears in.) make: *** [libgcc2.a] Error 1
A correção deste erro, consiste apenas em adicionar o código abaixo na linha 98 do arquivo
./libgcc2.c: #define BITS_PER_UNIT 8
113
Outro problema que o usuário SimpleScalar pode se deparar é o seguinte: gcc –o aditest aditest.c cc1: /tmp/ccuXmqQP.s: I/O error
O problema aqui é que o diretório tmp, que cotem arquivos temporários está cheio, e isso
ocasiona o erro, o gcc usa o valor da variável de ambiente $TMPDIR, portanto para sanar esse
erro, mude o valor de TMPDIR para outro valor (ex. export TMPDIR=/usr/tmp) ou apague
alguns arquivos do diretório /tmp.
Quando for necessário compilar qualquer programa usando o compilador target use a flag:
-I /usr/include, para especificar ao compilador a localização de qualquer arquivo de header
padrão e o flag –L para especificar a biblioteca.
Ainda é possível fazer o download do arquivo simpletools.tar.gz (no site do SimpleScalar),
que necessita ser descompactado. Dentro descompactando o arquivo, será encontrado no
diretório sslittle-na-sstrix/lib dois arquivos, o crt0.o e libc.a que já estão compilados para o
SimpleScalar. Copie eles para o diretório /home/SimpleScalar/lib. Supondo queira-se
compilar uma aplicação chamada teste.c. De dentro do diretório onde está a tal aplicação use a
seguinte linha de comando para a compilação: /home/SimpleScalar/sslittle-na-sstrix/bin/gcc –I/usr/include –L/home/SimpleScalar/lib –o teste.ss teste.c
Após executar todos os passos anteriores o simulador SimpleScalar estará pronto para ser
executado.
Instalação do SMS
A instalação do SMS, simulador multiprocessador implementado a partir do SimpleScalar, é
muito simples e consiste dos seguintes passos:
Passo (1) É requisito básico que já esteja instalado o SimpleScalar (veja sessão acima).
Passo (2) Descompacte o arquivo sms[1].tar.gz em um diretório (ex. /usr/SMS/), utilizando o
seguinte comando:
114
tar –zxvf sms[1].tar.gz
Passo (3) Execute o seguinte comando para realizar a instalação:
./make
Ao fim deste ultimo passo a instalação é estará concluída.
Para compilar um programa pode-se utilizar o seguinte comando:
/diretorio/do/simple/sslittle-na-sstrix-gcc -I/usr/include -L/root/Simple/lib -o mestre mestre.c
Para executar os programas compilados como acima, faz se necessário criar um arquivo (ex.
PROGRAMAS) no qual estará uma lista dos programas a serem executados, veja exemplo
abaixo:
# arquivo PROGRAMAS
mestre
escravo
escravo
escravo
Neste exemplo serão executados dois programas um denominado mestre e outro escravo,
sendo que o ultimo será executado em três instâncias.
Depois de criar este arquivo é só executar o comando que inicia a simulação, como segue
abaixo:
/.sms 2 PROGRAMAS
Pode-se notar que no comando anterior existe o numero 2 que representa o número de
processadores disponíveis para esta tarefa.
É possível ainda direcionar a saída do simulador para um arquivo, para isso faz se necessário
acrescentar ao comando ./sms as seguintes entradas:
/.sms 2 -redir:sim teste.txt PROGRAMS
115
O a opção –redir:sim cria um arquivo denominado teste.txt contendo as saídas do simulador,
este arquivo possibilita um melhor estudo das saídas do simulador.