ads:
Pontif´ıcia Universidade Cat´olica do Rio Gr ande do Sul
Faculdade de Inform´atica
P´os-Gradua¸c˜ao em Ciˆencia da Computa¸c˜ao
Alternativas de Alto
Desempenho para a
Multiplica¸c˜ao Vetor-descr i t or
Pedro Antˆonio Madeira de Campos Velho
Disserta¸c˜ao apresentada como
requisito parcial `a obten¸c˜ao do
grau de mestre em Ciˆencia da
Computa¸c˜ao.
Orientador: Prof. Dr. Luiz Gustavo
Le˜ao Fernandes
Porto Alegre, outubro de 2006.
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
Dados Internacionais de Catalogação na Publicação ( CIP )
C198a Campos Velho, Pedro Antônio Madeira de
Alternativas de alto desempenho para a multiplicação
vetor-descritor / Pedro Antônio Madeira de Campos Velho.
– Porto Alegre, 2006.
82 f.
Diss. (Mestrado em Ciência da Computação) – Fac.
de Informática, PUCRS.
Orientação: Prof. Dr. Luiz Gustavo Leão Fernandes.
1. Informática. 2. Avaliação de Desempenho
(Informática). 3. Álgebra Tensorial. I. Fernandes, Luiz
Gustavo Leão.
CDD 004.2
Ficha Catalográfica elaborada pelo
Setor de Processamento Técnico da BC-PUCRS
ads:
Agradecimentos
Gostaria de agradecer primeiramente as pessoas que trabalharam comigo no Centro de
Desenvolvimento de Aplica¸c˜oes Paralelas (CAP) durant e o desenvolvimento do presente
trabalho. Lucas Baldo, meu fiel amigo, colega de mestrado e s´ocio com qual dividi
e pretendo continuar dividindo momentos de alegria e realiza¸c˜ao profissio nal. Tivemos
a oportunidade de trabalhar juntos desde cedo e s˜ao incont´aveis as coisas que aprendi
e ainda aprendo com essa grande pessoa que tu ´es. M´arcio Castro, talvez o melhor
aluno que o curso de Ciˆencia da Computa¸c˜ao da PUCRS venha a ter em toda a hist´oria.
Mateus Raeder, um grande companheiro e um excelente profissional, principalmente na
reda¸c˜ao de artigos quando os pra zos n˜ao estavam a nosso favor. Thiago Tasca Nunes,
pela sua paciˆencia e amizade que n˜ao tem pre¸co, parab´ens por ser a pessoa que tu ´es e esse
profissional altamente capaz e sensato. Gustavo da Silva Serra, talvez o mais completo
programador C/C++ que eu venha conhecer em toda minha vida, muito obrigado pela tua
paciˆencia em responder minhas d´uvidas. Todos vo cˆes s˜ao g randes profissionais, altamente
capazes com os quais eu tive e tenho orgulho de continuar trabalhando. Nesse mesmo
manifesto de gratid˜ao, gostaria de mencionar o nome do meu amigo, orientador, padrinho
e s´ocio Luiz Gustavo Le˜ao Fernandes. A tua ajuda, aten¸c˜ao e amizade foi essencial
para a realiza¸c˜ao profissional que obtive at´e ent˜a o. Gostaria de deixar aqui registrado uma
d´ıvida eterna de gratid˜ao que tenho para com todos vocˆes. Sempre que vocˆes precisarem
de alguma coisa que esteja ao meu alcance eu estarei muito satisfeito em poder retribuir.
Gostaria de agradecer tamb´em ao pessoal do Performance Evaluation Group PEG.
Thais Webber, Ricardo Melo Czekster e Paulo Fernandes, vocˆes foram muito
importantes na escolha do tema e me ajudaram muito a o permitir que eu utilizasse o
prot´otipo desenvolvido por vocˆes. Tenho muita satisfa¸c˜ao em ter trabalhado com vocˆes e
me org ulho muito dos ar t ig os que publicamos em conjunto.
Finalmente, agrade¸co a minha fam´ılia que participou ativamente da etapa de minha
vida que resultou nessa disserta¸c˜a o. Obrigado m˜ae, Ros´alia Maria Pereira Madeira.
Tu sempre me deste muito apoio, aten¸c˜ao, amor e carinho. Espero poder t e dar mais
motivos de orgulho. Igualmente agrade¸co a minha V´o Rita (Rita Pereira Madeira) pelo
fato de me amar incondicionalmente e nunca ter questionado meus motivos e decis˜oes.
V´o Maria (Maria Hugo Velho), por ter investido tanto tempo e dinheiro na minha
educa¸c˜ao, os quais espero estar retribuindo com muito esfor¸co e dedica¸c˜ao. Aos demais
familiares e amigos gostaria de pedir desculpas por n˜ao colocar os seus nomes nessa p´agina
e dizer que se n˜ao o fiz foi realmente por falta de espa¸co. Obrigado a todos vocˆes.
Resumo
A modelagem anal´ıtica pode ser utilizada para prever desempenho, detectar deficiˆencias
e avaliar estrat´egias para melhorar sistemas. No contexto da modelagem computacional,
diversos formalismos para a modelagem anal´ıtica est˜ao se popularizando devido ao fato
de prover em alto-n´ıvel de abstra¸c˜ao e modularidade. No entanto, para inferir estimati-
vas de desempenho destes modelos, ´e necess´ario resolver um sistema de equa¸c˜oes. Em
modelos anal´ıticos estruturados, tais sistemas n˜ao se apresentam na forma tradicional,
Ax = b, pois a matriz de coeficientes (A) ´e trocada por uma express˜ao alg´ebrica (Q),
denominada Descritor Markoviano (ou s´o descritor). Logo, a multiplica¸c˜ao convencional,
Ax ´e substitu´ıda pela multipica¸c˜ao vetor-descritor (MVD), Qx. Dois algoritmos foram
propostos recentemente para implementar a MVD: shuffle e slice. Ambos apresentam
um a lto custo computacional, que eleva drasticamente o tempo necess´ario para resolver
modelos complexos. O objetivo do presente trabalho est´a relacionado com a utiliza¸c˜ao
de t´ecnicas de alto desempenho para propor vers˜oes mais r´apidas, tanto para o algoritmo
shuffle quanto para o s l i ce.
Abstract
Analytical modeling can be used to predict perfor mance, detect unexpected behavior and
evaluate strategies in order to enhance systems. In the subject of modeling computational
environments, a multitude of analytical modeling f ormalisms are becoming popular due
to the fact that they enable the use of high level abstractions and modularity. However,
to achieve performance statistics of a given analytical model, it is necessary to solve a
linear equations system. In structured formalisms, this system is not presented in the
usual notation, Ax = b, since the coefficients of matrix (A) are replaced by an algebraic
expressio n Q, called Markovian Descriptor (or descriptor, for short). Indeed, the original
multiplication, Ax is often changed for a vector-descriptor multiplication (MVD), Qx.
Recently, two algorithms that implement the MVD have been proposed: shuffle and slice.
Both demand high computational cost, which drastically increases the time necessary to
solve complex models. The goal of this work is to exploit the use of high performance
techniques in order to provide faster versions o f shuffle and slice algorithms.
Lista de Figuras
1 Cadeia de Markov modelando a disputa de dois processos por um recurso. 16
2 Modelo SAN onde dois processos disputam um recurso. . . . . . . . . . . . 16
3 Multiplica¸c˜ao do ´ultimo fator normal ( nlef t
N
⊗ Q
N
⊗ nright
N
). . . . . . 27
4 Exemplo da multiplica¸c˜ao de um AUNF pela ´ultima matriz de um termo. 29
5 Diagrama de comunica¸c˜ao para a MVD em paralelo. . . . . . . . . . . . . 33
6 Abordagem de distribui¸c˜ao de carga para o shuffle sem considerar custos. . 35
7 Exemplo de descritor com dois termos, cada um com trˆes matrizes. . . . . 42
8 Exemplo de arquivo de entrada para descritor da figura 7. . . . . . . . . . 43
9 Acelera¸c˜ao do Sh uffle, sem considerar custos (A) e considerando custos (B)
para o teste SC. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
10 Acelera¸c˜ao do Sh uffle, sem considerar custos (A) e considerando custos (B)
para o teste Misto. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
11 Acelera¸c˜ao do Sh uffle, sem considerar custos (A) e considerando custos (B)
para o teste Denso A. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
12 Acelera¸c˜ao do Sh uffle, sem considerar custos (A) e considerando custos (B)
para o teste Denso B. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
13 Detalhe do algoritmo de balanceamento de carga, shuffle, teste Misto. . . 47
14 Acelera¸c˜ao do pr´e-processamento para o algoritmo s l i ce. . . . . . . . . . . . 49
15 Acelera¸c˜ao do Slice considerando cada termo como uma tarefa (A) e con-
siderando cada AUNF como uma tarefa (B) para o teste SC . . . . . . . . 50
16 Acelera¸c˜ao do Slice considerando cada termo como uma tarefa (A) e con-
siderando cada AUNF como uma tarefa (B) para o teste Misto . . . . . . 50
17 Acelera¸c˜ao do Slice considerando cada termo como uma tarefa (A) e con-
siderando cada AUNF como uma tarefa (B) para o teste Denso A . . . . 51
18 Acelera¸c˜ao do Slice considerando cada termo como uma tarefa (A) e con-
siderando cada AUNF como uma tarefa (B) para o teste Denso B . . . . 51
19 Compara¸c˜ao do tempo de execu¸c˜ao entre shuffle (A) e o slice (B) pa ra caso
de teste SC. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
20 Compara¸c˜ao do tempo de execu¸c˜ao entre shuffle (A) e o slice (B) pa ra caso
Misto. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
21 Compara¸c˜ao do tempo de execu¸c˜ao entre shuffle (A) e o slice (B) pa ra caso
Denso A. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
22 Compara¸c˜ao do tempo de execu¸c˜ao entre shuffle (A) e o slice (B) pa ra caso
Denso B. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
23 Modelo SAN para o problema da SC . . . . . . . . . . . . . . . . . . . . . 62
24 Modelo SAN para o problema da SC com dois processos . . . . . . . . . . 63
25 Modelo SAN do caso de teste SC. . . . . . . . . . . . . . . . . . . . . . . 65
26 Modelo SAN do caso de teste Misto. . . . . . . . . . . . . . . . . . . . . 66
Lista de Tabelas
1 Descritor em SAN normalizado. . . . . . . . . . . . . . . . . . . . . . . . . 25
2 Detalhamento dos casos de t este . . . . . . . . . . . . . . . . . . . . . . . . 44
3 Comparativo entre custo de pr´e-processamento e o de uma itera¸c˜ao com o
slice. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4 Shuffle - escalonamento sem considerar custos - teste Misto. . . . . . . . . 67
5 Shuffle - escalonamento sem considerar custos - teste SC. . . . . . . . . . . 68
6 Shuffle - escalonamento sem considerar custos - teste Denso A. . . . . . . 69
7 Shuffle - escalonamento sem considerar custos - teste Denso B. . . . . . . 70
8 Shuffle - escalonamento considerando custos - teste SC. . . . . . . . . . . . 71
9 Shuffle - escalonamento considerando custos - teste Misto. . . . . . . . . . 72
10 Shuffle - escalonamento considerando custos - teste Denso A. . . . . . . . 73
11 Shuffle - escalonamento considerando custos - teste Denso B. . . . . . . . 74
12 Slice - escalonamento por termo - teste SC. . . . . . . . . . . . . . . . . . 75
13 Slice - escalonamento por termo - teste Misto. . . . . . . . . . . . . . . . 76
14 Slice - escalonamento por termo - teste Denso A. . . . . . . . . . . . . . . 77
15 Slice - escalonamento por termo - teste Denso B. . . . . . . . . . . . . . . 7 8
16 Slice - escalonamento por AUNF - teste SC. . . . . . . . . . . . . . . . . . 79
17 Slice - escalonamento por AUNF - teste Misto. . . . . . . . . . . . . . . . 80
18 Slice - escalonamento por AUNF - teste Denso A. . . . . . . . . . . . . . 81
19 Slice - escalonamento por AUNF - teste Denso B. . . . . . . . . . . . . . 8 2
Lista de S´ımbolos e Abreviaturas
CM Cadeia de Markov 14
DM Descritor Markoviano 14
MVD Multiplica¸c˜ao Vetor-descritor 14
SPN Stochastic Petri Nets 15
PEPA Performance Evaluation Process Algebra 15
SAN Stochastic Autom ata Networks 15
AUNF Additive Unitary Normal Factor 28
NOW Network of Workstations 31
MPI Message Passing Interface 31
SC Se¸c˜ao Cr´ıtica 43
MMP Milhares de Multiplica¸c˜oes em Ponto-flutuante 47
Lista de Algoritmos
1 Estrat´egia de para leliza¸c˜a o em alto n´ıvel. . . . . . . . . . . . . . . . . . . . 33
2 Shuffle utilizando abordagem de escalonamento sem considerar custos. . . . 34
3 Shuffle utilizando segunda abordagem de escalonamento, considerando custos. 36
4 Slice utilizando a bordagem simples de escalonamento . . . . . . . . . . . . 38
5 Slice, detalhe do pr´e-processamento, considerando cada AUNF como uma
tarefa. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
6 Slice utilizando a bordagem que considera cada AUNF como uma tarefa. . 40
Sum´ario
RESUMO 3
ABSTRACT 4
LISTA DE TABELAS 7
LISTA DE S
´
IMBOLOS E ABREVI ATURAS 8
Cap´ıtulo 1: Introdu¸c˜ao 14
1.1 Motiva¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.2 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3 Organiza¸c˜ao do Trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Cap´ıtulo 2: Multiplica¸c˜ao Vetor-descritor 18
2.1
´
Algebra Tensorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1.1 Produto Tensorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 9
2.1.2 Soma Tensorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.1.3 Termo Produto-tensorial . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2 Descritor Markoviano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3 Exemplos de Descritores . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3.1 Descritor em SAN . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.2 Descritor em Redes de Petri Estoc´asticas . . . . . . . . . . . . . . . 24
2.4 Algoritmos para a MVD . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4.1 Shuffle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4.2 Slice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Cap´ıtulo 3: MVD de Alto Desempenho 30
3.1 Aglomerados de Computadores . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2 MVD em Paralelo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3 Shuffle Paralelo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.3.1 Abordagem de Escalonamento Simples . . . . . . . . . . . . . . . . 34
3.3.2 Escalonamento Considerando Custos . . . . . . . . . . . . . . . . . 36
3.4 Slice Paralelo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.4.1 Primeira Abo r dagem de Escalonamento . . . . . . . . . . . . . . . . 38
3.4.2 Escalonamento por AUNF . . . . . . . . . . . . . . . . . . . . . . . 39
Cap´ıtulo 4: Resultados 41
4.1 Plataforma de Teste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.2 Casos de Teste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.3 Resultados Shuffle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.4 Resultados Slice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
Cap´ıtulo 5: Conclus˜ao 53
5.1 Compara¸c˜ao entre Shuffle e Slice . . . . . . . . . . . . . . . . . . . . . . . 53
5.2 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.3 Considera¸c˜ores Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
REFER
ˆ
ENCIAS BIBLIOGR
´
AFICAS 58
Apˆendice A: SAN - Exemplo de Modelo Anal´ıtico Estrutural 62
Apˆendice B: Semˆantica dos Modelos de Teste Utilizados 65
Apˆendice C: Detalhamento dos Resultados 67
14
Cap´ıtulo 1
Introdu¸c˜ao
A an´alise de desempenho vem se mostrando ´util em diversas situa¸c˜oes: prever o de-
sempenho de aplica¸c˜o es paralelas, avaliar qualidade de servi¸cos em sistemas distribu´ıdos,
etc. [6, 9, 10]. Entretanto, os formalismos para modelagem anal´ıtica apresentam limita-
¸c˜oes como o tempo necess´ario para inferir estimativas de desempenho e a alta necessidade
de armazenamento `a medida que os modelos s˜ao complexos [34].
Os formalismos estruturados constituem em um tipo de modelagem anal´ıtica. Esses se
caracterizam por apresentarem uma maneira estruturada e modular de projetar sistemas
gerando resultados comprovadamente equivalentes a Cadeias de Markov [5] (CM).
Apesar desses formalismos serem resolvidos da mesma maneira, o mapeamento de modelos
anal´ıticos estruturados em uma CM equivalente n˜ao ´e desejado porque exigiria um gra nde
custo de a r mazenamento [12]. Por esse motivo, tais formalismos utilizam algoritmos
para realizar as opera¸c˜o es necess´arias na resolu¸c˜ao dos modelos. Atualmente, os dois
algoritmos que realizam esta opera¸c˜ao, shuffle [18] e sli ce [34], apresentam um elevando
custo computacional na resolu¸c˜ao deste tipo de problema.
Formalismos para modelagem anal´ıtica estruturados caracterizam-se por possu´ırem
um Descritor Markoviano (DM ou descritor para abreviar) [5]. Esta estrutura ´e equi-
valente a um gerador infinitesimal, uma matriz que armazena as taxas de transi¸c˜ao entre
os diversos estados de uma CM. Da mesma maneira que as CMs, a resolu¸c˜ao desses mo-
delos ´e efetuada resolvendo-se um sistema de equa¸c˜oes lineares. Desta forma, a o pera¸c˜ao
central na resolu¸c˜ao de modelos anal´ıticos estruturados ´e a multiplica¸c˜ao de um vetor po r
uma matriz. Os algoritmos shuffle e slice manipulam a estrutura do descritor efetuando
esta multiplica¸c˜ao, a chamada Multiplica¸c˜ao Vetor-descritor (MVD) [2, 5, 22].
Utilizar m´aquinas mais potentes para aumentar o desempenho de aplica¸c˜oes ´e uma
t´ecnica que vem sendo constantemente empregada nos dias de hoje. Atualmente, aglome-
rados de computadores, do inglˆes clusters of comp uters, s˜ao atraentes uma vez que s˜ao
constru´ıdos com tecnologias para o consumidor final e conseq
¨
uentemente apresentam uma
boa rela¸c˜ao custo/benef´ıcio. Essas m´aquinas est˜ao ganhando popularidade no meio aca-
dˆemico onde s˜ao utilizadas para pesquisa de p onta nas mais diversas ´areas [7, 17, 25, 33].
15
1.1 Motiva¸c˜ao
O objetivo de realizar a MVD ´e efetuar a resolu¸c˜ao de um sistema de equa¸c˜oes line-
ares, indep endent e do m´etodo de resolu¸c˜ao empregado (M´etodo de Newton, M´etodo da
Potˆencia, etc.) [10, 29]. Atualmente, os m´etodos num´ericos mais utilizados para resolver
sistemas lineares s˜ao conhecidos como m´etodos iterativos. O que caracteriza um m´etodo
iterativo (para resolu¸c˜ao de sistemas de equa¸c˜oes lineares) ´e que, a cada itera¸c˜ao, ele se
aproxima da resolu¸c˜ao do sistema at´e que atinja um erro m´ınimo ou um n ´umero m´aximo
de itera¸c˜oes. Todavia, cada uma dessas itera¸c˜oes efetua a multiplica¸c˜ao de um vetor de
resultados aproximado por uma matriz de co eficientes. Lo go, a opera¸c˜ao da MVD ´e exe-
cutada diversas vezes (tipicamente centenas ou milhares de vezes) at´e que o problema seja
resolvido.
Existem diversas situa¸c˜oes nas quais ´e desejado analisar o desempenho de sistema s
computacionais, tais como: avaliar o desempenho de um novo processador; prever o de-
sempenho de configura¸c˜oes de ambientes e a lg oritmos; avaliar qualidade de servi¸co de
aplica¸c˜oes distribu´ıdas; assim por diante. Existem atualmente trˆes t´ecnicas empregadas
para avaliar o desempenho nestas situa¸c˜oes: bechmarks, modelos de simula¸c˜ao e modelos
anal´ıticos. Benchmarks consistem em uma s´erie de aplica¸c˜oes (de custo elevado em ter-
mos de processamento) que dever˜ao ser executadas de forma sistem´atica para qualificar e
quantificar o desempenho de dispositivo s espec´ıficos [4, 16].
A mo delagem por simula¸c˜ao visa a constru¸c˜ao de aplica¸c˜oes que simulem o comporta-
mento de um sistema. Essa t´ecnica pode ser utilizada par a avaliar a qualidade de sistemas
como redes de computadores, po r exemplo [30]. Em nosso trabalho, focamos nos m´etodos
anal´ıticos.
A modelagem anal´ıtica visa a constru¸c˜ao de um modelo que represente a realidade
sendo estudada. Mais precisamente, tais modelos caracterizam-se por agregar diversas in-
forma¸c˜oes de transi¸c˜ao (representando a intera¸c˜ao entre entidades do sistema) e a fr eq
¨
uˆen-
cia com as mesmas ocorrem. Existem diversos formalismos para modelagem anal´ıtica,
dentre as quais destacam-se: Redes de Autˆomatos Estoc´asticos [18], Redes Ativas
Estoc´asticas [31], Redes de Filas de Espera [21], Redes de Petri Estoc´asticas
(SPN) [2],
´
Algebra de Processos para Avalia¸c˜ao de Desempenho (PEPA) [22]
1
.
O escopo deste trabalho ´e restrito aos m´etodos de modelagem anal´ıtica estruturados.
Estes m´etodos caracterizam-se por utilizarem ´a lgebra tensorial para representar, atra-
v´es de uma express˜ao alg´ebrica, um gerador infinitesimal comprovadamente equivalente a
Cadeias de Markov [12, 15].
A va ntagem de utilizar modelos anal´ıticos estruturados env´es das Cadeias de Markov
est´a na obten¸c˜ao de um maior poder de abstra¸c˜ao. Para ilustrar, na figura 1, ´e apresentado
um exemplo de Cadeia de Markov que modela dois processos disputando o acesso a um
1
As siglas dos formalismos derivam de suas respectivas siglas internacionais em inglˆes: Stochastic Petri
Nets (SPN), Performance Evaluation Process Algebra (PEPA) e Stochastic Automata Networks (SAN).
16
P
A
(1)
R
(0)
P
B
(1)
P
A
(0)
R
(0)
P
B
(1)
P
A
(0)
R
(1)
P
B
(2)
P
A
(2)
R
(1)
P
B
(1)
P
A
(0)
R
(0)
P
B
(0)
P
A
(1)
R
(0)
P
B
(0)
P
A
(1)
R
(1)
P
B
(2)
P
A
(2)
R
(1)
P
B
(0)
τ
1
τ
1
τ
1
τ
1
τ
1
τ
1
τ
2
τ
2
τ
3
π
1
τ
3
π
1
τ
3
π
1
τ
3
π
1
τ
3
π
2
τ
3
π
2
τ
3
π
2
τ
3
π
2
τ
4
τ
4
Figura 1 : Cadeia de Markov modelando a disputa de do is processos por um recurso.
recurso compartilhado. Utilizando esse formalismo, somente um m´odulo ´e constru´ıdo
onde os estados representam a combina¸c˜ao de um estado de cada entidade do sistema.
J´a utilizando um formalismo de modelagem anal´ıtica estruturada, como por exemplo o
modelo SAN visto na Figura 2, ´e poss´ıvel separar em m´odulos cada entidade do sistema.
Assim, acrescenta-se poder de a bstra¸c˜ao uma vez que ambos modelos s˜ao equivalentes [1 9].
2
1
0
e
2
(π
2
)
e
2
(π
1
)
l
2
e
1
2
1
0
e
2
(π
2
)
l
1
e
2
(π
1
)
P rocesso
A
P rocesso
B
Recurso
e
2
1
0
e
3
e
1
, e
3
Figura 2: Modelo SAN onde dois processos disputam um recurso.
Os algoritmos para os quais apresentamos alternativas de alto desempenho podem ser
utilizados para a MVD independente do formalismo utilizado [2, 22]. Entretanto, cada
formalismo possui t´ecnicas espec´ıficas para o armazenamento das estruturas alg´ebricas,
e conseq
¨
uentemente desempenhos diferentes. Este cen´ario dificulta a elabora¸c˜ao de uma
biblioteca de primitivas para realizar a MVD.
1.2 Objetivos
O objetivo deste trabalho ´e empregar t´ecnicas de alto desempenho nos algoritmos
shuffle e slice visando acelerar a Multiplica¸c˜ao Vetor-descritor, a opera¸c˜ao empregada na
resolu¸c˜ao de modelos anal´ıticos estruturados.
17
A plataforma de alto desempenho utilizada para a execu¸c˜ao dos testes ´e um aglomerado
de computadores. Essas plataformas, conhecidas em inglˆes como clusters, s˜a o multi-
computadores que compartilham dados utilizando uma rede. O padr˜ao mais utilizado
para a troca de mensagens neste tipo de plata forma ´e MPI, por tratar-se de um padr˜ao
consolidado para a troca de mensagens em multi-computadores, port´avel, de comprovada
efic´acia e com ampla documenta¸c˜ao disp on´ıvel [24].
1.3 Organiza¸c˜ao do Trabalho
No cap´ıtulo 2, o problema da multiplica¸c˜ao vetor-descritor ´e apresentado seguido de
uma explica¸c˜ao dos algoritmos shuffle e slice utilizados para realizar esta opera¸c˜ao atu-
almente. No cap´ıtulo 3 s˜ao apresentadas as estrat´egias para realizar a MVD em uma
plataforma de computa¸c˜ao de alto desempenho onde detalhes de escalonamento s˜ao for-
necidos. A seguir, no cap´ıtulo 4, s˜ao mostrados como os test es foram realizados e em
seguida os resultados para cada um dos algoritmos. Finalmente, no cap´ıtulo 5 algumas
conclus˜oes e perspectivas, para trabalhos futuros, s˜ao discutidas. O a pˆendice A mostra
um exemplo de formalismo para modelagem anal´ıtica e como o Descritor Markovia no ´e
gerado. No apˆendice B, ´e apresentada uma descri¸c˜ao gr´afica dos modelos utilizados para
testar o desempenho das implementa¸c˜oes propostas ao longo deste tr abalho. Por fim, no
apˆendice C, s˜ao apresentados os detalhes num´ericos dos resultados.
18
Cap´ıtulo 2
Multiplica¸c˜ao Vetor-descritor
Os formalismos anal´ıticos estruturados caracterizam-se por apresentarem uma forma
modular de representar sistemas reais. Esses formalismos s˜ao mais atraentes que Cadeias
de Markov por permitirem projetar um sistema gra nde em pequenas partes independen-
tes, especificando as intera¸c˜oes entre cada m´odulo quando necess´ario. Dessa forma, o s
formalismos conservam as propriedades das CMs de forma que podem inferir as mesmas
estimativas de desempenho de um determinado sistema.
O mapeamento de um modelo anal´ıtico estruturado em uma CM ´e realizado utilizando
as opera¸c˜oes de ´algebra tensorial. Estas opera¸c˜oes combinam os estados independentes de
cada um dos m´odulos do modelo de forma a gerar uma estrutura equivalente ao gerador
infinitesimal. O gerador infinitesimal ´e uma matriz que cont´em as taxas de transi¸c˜oes
entre cada um dos estados em um modelo descrito utilizando Cadeias de Markov. Todavia,
como o gerador infinitesimal gerado neste processo ´e muito esparso, ´e prefer´ıvel armazenar
as matrizes de forma a minimizar a utiliza¸c˜ao de mem´oria. Para tr atar este problema,
o gerador infinitesimal ´e ent˜ao substitu´ıdo por um Descritor Markoviano (ou somente
descritor para abreviar), uma estrutura alg´ebrica que quando resolvida ´e equivalente ao
gerador infinitesimal.
Para resolver modelos descritos utilizando CM, ´e necess´ario resolver um sistema de
equa¸c˜oes lineares. Ao final deste processo, o vetor solu¸c˜ao do sistema conter ´a informa¸c˜o es
referentes `a permanˆencia em cada estado do modelo. Em outras palavras, apresentar´a
estimativas de desempenho para o sistema real sendo modelado. Como os formalismos
estruturados apresentam uma equivalˆencia a CM, o m´etodo de resolu¸c˜ao ´e an´alogo. No
entant o, o gerador infinitesimal n˜ao existe nestes ´ultimos, po is ´e substitu´ıdo pelo descritor.
Neste ponto a opera¸c˜a o de multiplica¸c˜ao do vetor solu¸c˜ao pela matriz de coeficientes, que ´e
o gerador infinitesimal em CM, ´e substitu´ıdo pela multiplica ¸c˜ao do vetor pelo Descritor
Markoviano. E portanto esta opera¸c˜ao de multiplica¸c˜ao ´e chamada de multiplica¸c˜ao
vetor-descritor.
A resolu¸c˜ao de sistemas de equa¸c˜oes lineares ´e r ealizada geralmente utilizando-se m´e-
todos iterativos. M´etodos iterativos caracterizam-se por aproximarem o vetor resultado
19
do sistema a cada itera¸c˜ao. Neste caso, o n´umero de itera¸c˜oes necess´arias para resolver
um sistema varia muito, pois ´e determinado por um erro m´ınimo do resultado aproximado
ou um n´umero m´aximo de itera¸c˜oes. A MVD, ´e portanto, uma opera¸c˜ao que ´e realizada
diversas vezes at´e que o modelo seja resolvido. O custo computacional desta opera¸c˜ao
determina o custo total de resolu¸c˜ao de um modelo, quantificado em termos de tempo de
processamento, po r isso existe um grande a pelo para que o custo desta opera¸c˜ao seja o
menor poss´ıvel.
Uma vez que a Multiplica¸c˜ao Vetor-descritor(MVD) ´e uma opera¸c˜ao alg´ebrica que
substitui a multiplica¸c˜ao de um vetor por uma matr iz, torna-se necess´ario compreender
as opera¸c˜oes alg´ebricas envolvidas nesta express˜ao. Na se¸c˜ao 2.1, os aspectos relevantes da
´algebra tensorial s˜ao apresentados, bem como algumas propriedade releva ntes para a cons-
tru¸c˜ao dos algoritmos e conseq
¨
uentemente importantes para compreender a paraleliza¸c˜ao
destes. Em seguida, na se¸c˜ao 2.3, os descritores de dois formalismos s˜ao apresentados
com o intuito de justificar a escolha do formato de entrada escolhido. Finalmente, na
se¸c˜ao 2.4 os dois algoritmos que realizam a MVD, shuffle e slice, s˜ao apresentados de
forma a ressaltar os aspectos que permitem distribuir o c´alculo.
2.1
´
Algebra Tensorial
Para entender como a Multiplica¸c˜ao Vetor-descritor (MVD) ´e efetuada, ´e necess´ario
conhecer as opera¸c˜oes alg´ebricas que s˜ao utilizadas para mapear um modelo anal´ıtico
em uma cadeia de Markov. Estas op era¸c˜oes s˜ao conhecidas como opera¸c˜o es de ´algebra
tensorial cl´assica ou tamb´em por opera¸c˜oes de Kronecker [15]. Apesar do Descritor Mar-
koviano apenas utilizar o produto tensorial, a soma tensorial ´e freq
¨
uentemente utilizada
e, portanto, se torna r elevante para compreens˜ao dos algoritmos que realizam a MVD.
As opera¸c˜oes de soma e produto tesorial s˜ao definidas entre duas matrizes reais. Como
no contexto dos formalismos anal´ıticos estruturados, estas matrizes s˜a o sempre quadradas.
Neste trabalho s˜ao apresentadas defini¸c˜oes e exemplos para casos que contemplam somente
matrizes quadradas. O leitor interessado em encontrar mais informa¸c˜oes sobre a ´algebra
tensorial pode consultar as referˆencias.
2.1.1 Produto Tensorial
O produto t ensorial ´e uma opera¸c˜ao alg´ebrica definida entre duas matrizes reais. Dado
duas matrizes A e B, onde A ´e uma matriz n
1
1
, e B ´e uma matriz de ordem n
2
, o produto
tensorial entre estas duas matrizes (denotado por A ⊗ B), gera uma matriz C de ordem
n
1
× n
2
, onde cada elemento C
i,j
´e dado segundo a equa¸c˜ao 1. Nesta equa¸c˜ao , x e y s˜ao
1
Como foi explicado anteriormente, as matrizes no contexto deste trabalho s˜ao sempre quadradas.
Dessa forma a or dem de uma matriz representa o n´umero de linhas e colunas.
20
n´umeros reais po sitivos. O operador un´ario x representa o n´umero inteiro imediatamente
inferior a x, e a opera¸c˜ao x y calcula o resto da divis˜ao inteira de x dividido por y.
C
i,j
= A
(i−1)/n
2
+1,(j−1)/n
2
+1
× B
((i−1) n
2
)+1,((j−1) n
2
)+1
(1)
A id´eia do produto tensorial ´e combinar cada elemento da matriz A com cada elemento
da matriz B. Para ilustrar est´a id´eia observe as matrizes abaixo:
A =
1 2
2 1
B =
3 4
5 6
A matriz resultante do produto tensorial entre A e B no exemplo acima fica:
1 2
2 1
⊗
3 4
5 6
=
1 × 3 1 × 4
2 × 3 2 × 4
1 × 5 1 × 6
2 × 5 2 × 6
2 × 3 2 × 4 1 × 3 1 × 4
2 × 5 2 × 6
1 × 5 1 × 6
Repare que esta opera¸c˜ao mapeia em cada elemento da matriz resultante o produto
de um elemento de A por um elemento de B. Em o utras palavras, o resultado desta
opera¸c˜ao ´e uma matriz que cont´em a combina¸c˜ao de todas as multiplica¸c˜oes poss´ıveis
entre elementos das matrizes A e B. Para ilustrar melhor esta id´eia, a ba ixo ´e apresentado
como a multiplica¸c˜ao de cada elemento a
ij
da matriz A multiplica cada elemento b
ij
da
matriz B, gerado ao final do produto tensorial.
a
11
a
12
a
21
a
22
⊗
b
11
b
12
b
21
b
22
=
a
11
×
b
11
b
12
b
21
b
22
a
12
×
b
11
b
12
b
21
b
22
a
21
×
b
11
b
12
b
21
b
22
a
22
×
b
11
b
12
b
21
b
22
21
2.1.2 Soma Tensorial
A soma tensorial ´e definida com base no produto tensorial. Esta opera¸c˜ao, dentro do
escopo deste trabalho, t amb´em recebe como operandos duas matrizes reais quadradas.
Dado duas matrizes A e B, a soma tensorial dest as matrizes (denotada por A ⊕ B), ´e
definida pela equa¸c˜a o 2. Onde, I
M
denota uma matriz identidade
2
da mesma dimens˜ao
da matriz M. Note que a soma t ensorial gera igualmente uma matriz de ordem n
1
× n
2
.
A ⊕ B = (A ⊗ I
B
) + (I
A
⊗ B) (2)
Para ilustrar o c´alculo de uma soma tensorial utilizaremos as mesmas matrizes que
utilizamos para exemplificar o produto tensorial:
A =
1 2
2 1
B =
3 4
5 6
Para este exemplo, a matriz resultante da soma tensorial entre A e B fica:
1 2
2 1
⊕
3 4
5 6
=
1 2
2 1
⊗
1 0
0 1
+
1 0
0 1
⊗
3 4
5 6
=
1 0 2 0
0 1 0 2
2 0 1 0
0 2 0 1
+
3 4 0 0
5 6 0 0
0 0 3 4
0 0 5 6
=
1 + 3 0 + 4
2 + 0 0
0 + 5 1 + 6
0 2 + 0
2 + 0 0 1 + 3 0 + 4
0 2 + 0
0 + 5 1 + 6
A soma tensorial ´e amplamente utiliza da para o mapeamento dos modelos descritos
em fo r malismos anal´ıticos estruturados em cadeias de Markov. No entanto, ´e prefer´ıvel
decompor esta opera¸c˜ao em produtos tensoriais para homogeneizar o t ratamento num´erico
realizado. Este aspecto se torna relevante para compreender os algoritmos que realizam a
MVD e consequentemente faz-se necess´ario apresentar como esta decomposi¸c˜ao pode ser
realizada.
Dada uma s´erie de somas tensoriais com N matrizes, esta propriedade diz que as N
2
Matriz identidade ´e uma matriz cujo todos os elementos localizados na diagonal principal s˜ao iguais
a 1 e todos os outros elementos s˜ao iguais a zero.
22
somas tensoriais podem ser compo stas na soma de N produtos tensoriais. Para ilustrar
est´a id´eia veja o exemplo abaixo:
8 7
0 9
⊕
3 4
5 6
⊕
3 2
0 1
=
8 7
0 9
⊗
1 0
0 1
⊗
1 0
0 1
+
1 0
0 1
⊗
3 4
5 6
⊗
1 0
0 1
+
1 0
0 1
⊗
1 0
0 1
⊗
3 2
0 1
Generalizando o exemplo acima para uma s´erie de somas tensoriais com N matrizes
temos:
M
1
⊕ M
2
⊕ M
3
⊕ . . . ⊕ M
N
= M
1
⊗ I
2
⊗ I
3
⊗ · · · ⊗ I
N
+
I
1
⊗ M
2
⊗ I
3
⊗ · · · ⊗ I
N
+
I
1
⊗ I
2
⊗ M
3
⊗ · · · ⊗ I
N
+
.
.
. ⊗
.
.
. ⊗
.
.
. ⊗
.
.
.
⊗
.
.
. +
I
1
⊗ I
2
⊗ I
3
⊗ · · · ⊗ M
N
2.1.3 Termo Produto-tensorial
A id´eia de um termo produto tensorial (ou somente termo, para abreviar) ´e re-
presentar diversas opera¸c˜oes de produto tensorial consecutivas. Fo r malmente, um termo
composto pelo produto tensorial de N matrizes M
1
a M
N
ficar´a como na equa¸c˜ao 3. Note
que esta opera¸c˜ao ´e bastante parecida com um somat´orio onde ao contr´ario de somas as
opera¸c˜oes realizadas s˜ao produtos tensoriais.
N
i=1
M
i
= M
1
⊗ M
2
⊗ · · · ⊗ M
N
(3)
23
2.2 Descritor Markoviano
Um conceito fundamental para a compreens˜ao da MVD ´e como o Descritor Marko-
viano ´e armazenado. Dependendo do fo rmalismo utilizado para modelagem, a estrutura
alg´ebrica do descritor varia. Para abstrair os detalhes espec´ıficos de cada fo r malismo, ado-
tamos o DM como sendo a soma consecutiva de diversos termos produto-tensorial. Dada
uma s´erie de somas de T termos, onde cada termo ´e composto pelo produto tensorial
entre N matrizes, o descritor ´e a presenta do como visto na equa¸c˜ao 4. Neste contexto, ´e
necess´ario restringir que cada matriz Q
i
possuir´a a mesma ordem, independente do termo
k no qual se encontra. Dessa forma, ´e poss´ıvel ga r antir que cada termo que comp˜oe o
descritor resulta em uma matriz, se resolvido, de mesma o rdem.
T
k=1
N
i=1
Q
(k)
i
(4)
Logo, um descritor composto por T termos com N matrizes cada fica como abaixo:
T
k=1
N
i=1
Q
(k)
i
= Q
(1)
1
⊗ Q
(1)
2
⊗ Q
(1)
3
⊗ · · · ⊗ Q
(1)
N
+
Q
(2)
1
⊗ Q
(2)
2
⊗ Q
(2)
3
⊗ · · · ⊗ Q
(2)
N
+
Q
(3)
1
⊗ Q
(3)
2
⊗ Q
(3)
3
⊗ · · · ⊗ Q
(3)
N
+
.
.
. ⊗
.
.
. ⊗
.
.
. ⊗
.
.
.
⊗
.
.
. +
Q
(T )
1
⊗ Q
(T )
2
⊗ Q
(T )
3
⊗ · · · ⊗ Q
(T )
N
+
Note que o s´ımbolo Q
(k)
n˜ao denota potencia¸c˜ao e sim funciona como um ´ındice para
o somat´orio (para fazer esta distin¸c˜ao s˜ao utilizados os parˆenteses). Durante o texto a
express˜ao Q
(k)
denota o k-´esimo termo do somat´orio do descritor. Para representar o
descritor inteira mente, o s´ımbolo Q ´e utilizado sem ´ındices.
2.3 Exemplos de Descr i tores
Nesta se¸c˜ao apresentar emos dois exemplos de descritores de dois formalismos anal´ıti-
cos estruturados. O objetivo aqui ´e exemplificar como descritores diferentes podem ser
manipulado algebricamente gerando uma soma de termos tensoriais como apresentado na
equa¸c˜ao 4. Ou, em outras palavra s, como os diferentes descritores de cada fo r malismo
podem ser a lg ebricamente manipualdos para a mesma estrutura.
Os dois formalismos abordados nessa se¸c˜ao, Redes de Autˆomatos Estoc´asticos (SAN) e
Redes de Petri Estoc´asticas (PEPA), foram escolhidos pela sua popularidade em trabalhos
24
cient´ıficos recentes [8, 6, 13].
2.3.1 Descritor em SAN
A id´eia de uma Rede de Autˆomatos Estoc´asticos ´e descrever um modelo global de
um sist ema em diversos m´odulos (subsistemas) independentes entre si, onde as intera¸c˜oes
entre esses subsistemas podem ocorrer em alguns casos. Cada m´odulo independente ´e
definido como um autˆomato estoc´astico. A modelagem de cada autˆomato ´e realizada
parametrizando-se estados, transi¸c˜oes e eventos. Uma vez que event os podem representar
sincronismo entre dois ou mais autˆomatos, os dados sobre um modelo s˜ao a r mazenados
em matrizes que definem o comportamento local e matrizes que definem o comportamento
sincronizante [18, 19, 20, 34]. O Descritor Markoviano, em SAN , apresenta-se como visto
na equa¸c˜ao 5. Nessa equa¸c˜ao, N r epresenta o n´umero de autˆomatos e E o total de eventos
que modelam intera¸c˜oes entre os autˆomatos (eventos sincronizantes).
Q =
N
i=1
Q
(i)
l
+
E
e=1
N
i=1
Q
(i)
e
+
+
N
i=1
Q
(i)
e
−
(5)
Como pode ser observado, o descritor de SAN representa uma parte descrita como
a soma tensorial entre matrizes. Como apresentando anteriormente, ´e poss´ıvel decompo r
uma s´erie de somas tensoriais aplicando-se a propriedade da decomposi¸c˜ao em fatores
normais. Logo, ´e poss´ıvel normalizar [18] o descritor de SAN em um descritor que
somente possui termos produto- t ensorial. A tabela 1 demonstra como fica o descritor de
SAN ap´os a normaliza¸c˜ao da parte local.
Foge do escopo desse trabalho a apresenta¸c˜ao do formalismo SAN em detalhes. En-
tretanto, devido `a utiliza¸c˜ao de estudos de caso utilizando este formalismo, no final do
trabalho uma explica¸c˜ao mais aprofundada sobre como os modelos SAN s˜ao constru´ıdos
´e fornecida no apˆendice A.
2.3.2 Descritor em Redes d e Petri Estoc´asticas
Redes de Petri Estoc´asticas (SPN) fornecem uma maneira de modelar sistemas basea-
dos no conceito cl´assico de Redes de Petri. De maneira geral, o s conceitos existentes em tal
formalismo se aproximam dos utilizados em SAN, uma vez que ambos apresentam m´odu-
los independentes com pont os de intera¸c˜oes espec´ıficos [11, 13, 2, 32]. De maneira an´aloga
a SAN, o descritor utilizando SPN, apresenta-se algebricamente dividido em uma parte
local e outra destinada a representar as intera¸c˜oes entre m´odulos (parte sincro nizante),
visto na equa¸c˜ao 6 [14].
25
Tabela 1: Descritor em SAN normalizado.
Q
(1)
l
⊗
g
I
n
2
⊗
g
· · · ⊗
g
I
n
N−1
⊗
g
I
n
N
I
n
1
⊗
g
Q
(2)
l
⊗
g
· · · ⊗
g
I
n
N−1
⊗
g
I
n
N
N
.
.
.
I
n
1
⊗
g
I
n
2
⊗
g
· · · ⊗
g
Q
(N−1)
l
⊗
g
I
n
N
I
n
1
⊗
g
I
n
2
⊗
g
· · · ⊗
g
I
n
N−1
⊗
g
Q
(N)
l
2E
Q
(1)
1
+
⊗
g
Q
(2)
1
+
⊗
g
· · · ⊗
g
Q
(N−1)
1
+
⊗
g
Q
(N)
1
+
e
+
.
.
.
Q
(1)
E
+
⊗
g
Q
(2)
E
+
⊗
g
· · · ⊗
g
Q
(N−1)
E
+
⊗
g
Q
(N)
E
+
Q
(1)
1
−
⊗
g
Q
(2)
1
−
⊗
g
· · · ⊗
g
Q
(N−1)
1
−
⊗
g
Q
(N)
1
−
e
−
.
.
.
Q
(1)
E
−
⊗
g
Q
(2)
E
−
⊗
g
· · · ⊗
g
Q
(N−1)
E
−
⊗
g
Q
(N)
E
−
R
=
N
i=1
R
(i)
+
τ
j
∈T
N
i=1
R
(i,j)
(6)
Da mesma forma que em SAN , as somas tensoriais do descritor para SPN apre-
sentado na equa¸c˜ao 6 podem ser substitu´ıdas pela soma consecutiva de diversos termos
produto-tensorial resultando em um descritor como o apresentado na equa¸c˜ao 4. Esses
exemplos indicam que, em geral, os formalismos de modelagem anal´ıtica estruturados
podem beneficiar-se das vers˜oes dos algoritmos propostos nesse trabalho.
2.4 Algoritmos para a MVD
Algebricamente, o problema da Multiplica¸c˜a o Vetor-descritor consiste na multiplica¸c˜ao
de um vetor x por um termo alg´ebrico, o descritor, Q. Formalizando essa id´eia, temos a
equa¸c˜ao 7 substituindo a multiplica¸c˜ao original Ax da matriz de coeficientes pelo vetor.
Qx =
m
k=1
N
i=1
Q
i
(k)
x (7)
Atualmente, existem dois algoritmos que manipulam o DM: shuffle e slice. A gera¸c˜a o
de uma ´unica matriz, resolvendo a express˜ao alg´ebrica do DM, n˜ao ´e desejada pois exi-
giria um grande custo computacional de armazenamento. Os algoritmos que realizam a
26
MVD tornam-se necess´arios para manipular esta estrutura de forma a manter o tamanho
ocupado pelo modelo gerenci´avel em termos de necessidade de mem´oria. A seguir ser˜ao
apresentados os princ´ıpios b´asicos dos dois algoritmos que atualmente realizam a MVD.
2.4.1 Shuffle
A demanda por alg oritmos que realizassem a MVD de maneira que n˜ao fosse necess´ario
resolver o descritor em um gerador infinitesimal fez surgir o algoritmo shuffle. Inicialmente
proposto por diversos autores, os principais trabalhos que fazem men¸c˜ao a este algoritmo
s˜ao [18] e [19].
De maneira geral, algumas propriedades da ´alg ebra tensorial s˜ao imperativas para a
realiza¸c˜ao da MVD sem incorrer na gera¸c˜ao do gerador infinitesimal. O shuffle se baseia
na decomposi¸c˜ao de um termo em um produto ordin´ario de fatores normais, vide
equa¸c˜ao 8. Esta propriedade permite que um termo produto-tensorial entre N matrizes
seja decomposto na multiplica¸c˜ao de N termos, cada um com N matrizes. No entanto,
ap´os realizada esta decomposi¸c˜ao, cada termo apresenta apenas uma matriz com valo-
res originais enquanto todas as outras N − 1 matrizes s˜ao substitu´ıdas por uma matriz
identidade que conserva a o rdem da matriz de mesma posi¸c˜ao no termo. O o bjetivo de
utilizar propriedade ´e realizar o mapeamento dos elementos de cada matriz no gerador
infinitesimal equivalente.
Q
1
⊗ Q
2
⊗ Q
3
⊗ . . . ⊗ Q
N
= (Q
1
⊗ I
2
⊗ I
3
⊗ · · · ⊗ I
N
) ×
(I
1
⊗ Q
2
⊗ I
3
⊗ · · · ⊗ I
N
) ×
(I
1
⊗ I
2
⊗ Q
3
⊗ · · · ⊗ I
N
) ×
.
.
. ⊗
.
.
. ⊗
.
.
. ⊗
.
.
.
⊗
.
.
. ×
(I
1
⊗ I
2
⊗ I
3
⊗ · · · ⊗ Q
N
)
(8)
O algoritmo shuffle define os operadores nleft
i
e nright
i
para mapear os elementos
das matrizes de um termo no gerador infinitesimal. O operador nlef t
i
´e um operador que
dado uma matriz qualquer Q
i
, de um termo qualquer, realiza o produt´orio da ordem de
todas a s matrizes que est˜ao `a esquerda de Q
i
. No caso da matriz Q
1
, ou seja, a primeira
matriz de um termo, o o perador nlef t
1
por defini¸c˜ao resulta em 1, uma vez que n˜ao h´a
matrizes `a esquerda deste termo. O operador nright
i
se diferencia de nlef t
i
por retornar
o produt´orio da ordem das matrizes que est˜ao `a direita de uma matriz Q
i
. De forma
an´aloga, este o perador ´e por defini¸c˜ao 1 quando a matriz est´a localizada na extremidade
direita de um termo, ou seja, nright
N
= 1, para um termo com N matrizes. Assim,
o algoritmo shuffle se baseia na propriedade da decomposi¸c˜ao em f atores normais para
27
reescrever cada termo do descritor como visto na equa¸c˜ao 8:
Q
1
⊗ Q
2
⊗ Q
3
⊗ . . . ⊗ Q
N
= nlef t
1
⊗ Q
1
⊗ nright
1
×
nlef t
2
⊗ Q
2
⊗ nright
2
×
nlef t
3
⊗ Q
3
⊗ nright
3
×
.
.
. ⊗
.
.
. ⊗
.
.
. ×
nlef t
N
⊗ Q
N
⊗ nright
N
O shuffle implementa a multiplica¸c˜ao de cada termo Q
(k)
utilizando o resultado da
decomposi¸c˜ao de um termo em fatores normais ordin´arios. Para cada matriz de um termo
Q
i
, o vetor deve ser multiplicado por esta matriz utilizando os resultados de nleft
i
e
nright
i
com o objetivo de mapear a localiza¸c˜ao dos elementos da i-´esima matriz deste no
gerador infinitesimal. Por exemplo, a multiplica¸c˜ao do vetor pela ´ultima matriz de cada
termo ficar´a como apresentado na figura 3.
Q
(N)
Q
(N)
Q
(N)
n
N
n
N
n
N
x
k
x
k+1
n
N
n
N
n
N
Figura 3: Multiplica¸c˜ao do ´ultimo fator normal ( nlef t
N
⊗ Q
N
⊗ nright
N
).
Neste caso particular, o operador nright
N
´e igual a 1 e n˜ao representa mudan¸ca
no resultado do produto tensorial. Logo, a matriz Q
N
deve ser replicada em nleft
N
blocos diagonais no gerador infinitesimal como visto na figura 3. Entretanto, para as
outras matrizes de um termo, esta opera¸c˜ao utiliza blocos n˜ao cont´ıguos do vetor e,
conseq
¨
uentemente, exige a altera¸c˜ao de diversos elementos.
O custo computacional em n´umero de multiplica¸c˜oes de ponto flutuante necess´a r ia s
para a multiplica¸c˜ao do vetor x por um termo qualquer t, ´e dado pela equa¸c˜ao 9 [18]. Onde
n
(t)
i
´e a ordem da i-´esima matriz do termo t e nz
(t)
i
corresponde ao n´umero de elementos
diferentes de zero na i-´esima matriz do termo t.
28
C
t
=
N
i=1
n
(t)
i
×
N
i=1
nz
(t)
i
n
(t)
i
(9)
2.4.2 Slice
O algor itmo slice ´e relativamente novo e j´a tem apresentado resultados interessantes
na resolu¸c˜ao de determinados modelos [20]. A id´eia central neste algoritmo consiste na
decomposi¸c˜ao dos termos produto- t ensorial em pequenas somas alg´ebricas. Acredita-se
que o slice possa aproveitar melhor o poder de processamento de aglomerados de compu-
tadores, uma vez que permite a decomposi¸c˜a o do problema em menores fat ia s.
O algoritmo slice ´e baseado na propriedade da decomposi¸c˜ao aditiva. Esta proprie-
dade demonstra que o produto tensorial consecutivo, entre duas ou mais matrizes, pode
ser descrito como a soma da multiplica¸c˜ao de diversas matrizes unit´arias. Esta proprie-
dade ´e formalizada na equa¸c˜ao 10. O princ´ıpio b´asico do algoritmo slice ´e aplicar essa
propriedade sem considerar a ´ultima matriz de cada termo. As o utras matrizes do termo
s˜ao representadas por diversas matrizes unit´arias, cada matriz unit´aria ´e chamada de Fa-
tor Normal Unit´ario Aditivo (AUNF ou fator para abreviar), essa sigla deriva da
nomenclatura internacional, em inglˆes, Aditive Unitary Normal Factor.
Q
(1)
⊗ · · · ⊗ Q
(N)
=
n
1
i
1
=1
· · ·
n
N
i
N
=1
n
1
j
1
=1
· · ·
n
N
j
N
=1
ˆq
1
(i
1
j
1
)
⊗ · · · ⊗ ˆq
N
(i
N
j
N
)
(10)
Para gerar os AUNFs, ´e efetuado o produto tensorial das N − 1 matrizes de cada
termo produto-tensorial. Por exemplo, supondo um termo produto-tensorial que envolva
trˆes matrizes Q
1
, Q
2
e Q
3
(Q
1
⊗ Q
2
⊗ Q
3
), a pro priedade da decomposi¸c˜ao aditiva ´e
efetuada apenas considerando o produto Q
1
⊗ Q
2
. Para exemplificar, supo ndo que as Q
1
,
Q
2
e Q
3
sejam:
Q
1
=
0 2
0 0
Q
2
=
3 0 4
0 0 5
0 0 0
Q
3
=
0 6 0
0 7 0
8 0 9
Utilizando a propriedade da decomposi¸c˜ao aditiva todos os elementos das matrizes Q
1
e Q
2
s˜ao multiplicados separadamente para depois serem multiplicados pela matriz Q
3
,
como abaixo:
29
[(2 × 3) ⊗ Q
3
] + [(2 × 4) ⊗ Q
3
] + [(2 × 5) ⊗ Q
3
]
Este procedimento se diferencia do realizado pelo shuffle principalmente por este ma-
pear apenas a localiza¸c˜ao da ´ultima matriz de cada t ermo no DM. Para realizar este
mapeamento, cada AUNF guarda a informa¸c˜ao de linha e coluna o nde este estaria loca-
lizado na matriz resultante do produto tensorial entre as N − 1 matrizes mais `a esquerda
de um termo. Guardando estes ´ındices, a gera¸c˜a o de todos os fatores (AUNFs) s´o precisa
ser realizada uma vez.
Esta t´ecnica, portanto permite que os diversos termos tensoriais sejam desmembrados
em pequenas multiplica¸c˜oes. Em m´aquinas de a lto desempenho, como aglomerado de
computadores, essa abordagem apresenta-se bastante atraente uma vez que torna poss´ıvel
considerar cada fator como uma tarefa independente. Este aspecto diferencia o slice do
shuffle principalmente pela quantidade de dados manipulados na multiplica¸c˜ao de cada
fator.
Q
(N)
n
N
x
k
x
k+1
n
N
Figura 4 : Exemplo da multiplica¸c˜ao de um AUNF pela ´ultima matriz de um termo.
Para ilustrar essa id´eia, a figura 4 apresenta um exemplo de multiplica¸c˜ao de um
AUNF pela ´ultima matriz de um termo. Neste caso, o n´umero de elementos n˜ao nulos
na ´ultima matriz do termo (nz
N
), determina a quantidade de multiplica¸c˜oes que ser˜ao
realizadas. No pior caso, o nde a ´ultima matriz do termo, Q
N
, n˜ao possui zeros, ser˜ao
necess´arias n
N
× n
N
multiplica¸c˜oes [20, 34].
30
Cap´ıtulo 3
MVD de Alto Desempenho
Atualmente, diversas aplica¸c˜oes utilizam computa¸c˜ao de a lto desempenho. O mape-
amento do DNA humano [3], a predi¸c˜ao de terremotos [1], a renderiza¸c˜ao de imagens
para aux´ılio ao diagn´ostico de doen¸cas [27], s˜a o alguns exemplos. Modelos anal´ıticos
apresentam-se de grande aplica¸c˜ao pr´atica [6, 9]. Estes podem ser utilizados, por exem-
plo, para modelar e apresentar estimativas de desempenho dos mais diversos sistemas
computacionais. Uma aplica¸c˜ao pr´atica poss´ıvel, por exemplo, ´e a utiliza¸c˜ao para anali-
sar sistemas de rede, auxiliando no diagn´ostico de problemas como gargalos e roteadores
sub-utilizados.
Os formalismos de modelagem anal´ıtica, de maneira geral, apresentam restri¸c˜oes na
complexidade dos modelos que podem ser resolvidos por dois motivos: mem´oria e tempo
de resolu¸c˜ao [12]. Tipicamente, a quantidade de mem´oria utilizada pelos modelos aument a
`a medida que a complexidade destes aumenta. Atua lmente, para mitigar este problema,
s˜ao utilizados a lgoritmos que realizam a MVD. A principal vantag em da utiliza¸c˜ao destes
algoritmos ´e evitar armazena r o gerador infinitesimal reduzindo drasticamente a demanda
de armazenamento. Em casos n˜ao raros, obt´em-se uma redu¸c˜ao de at´e 95% [20]. No
entant o, o tempo necess´ar io para a resolu¸c˜ao de alguns modelos pode ser um fator li-
mitador. Em trabalhos recentes, diversas abordagens vˆem sendo estudadas, o pr´oprio
algoritmo slice neste contexto apresenta avan¸cos significativos.
O presente cap´ıtulo mostra como as t´ecnicas de alto desempenho s˜ao utilizadas para
reduzir o custo de armazenamento e ainda como a MVD pode ser distribu´ıda. As t´ec-
nicas aqui empregadas s˜ao relacionadas a plataforma de execu¸c˜ao pretendida, no caso,
um aglo merado de computadores. Por esta raz˜ao a se¸c˜ao 3.1, recapitula as principais
caracter´ısticas deste tipo de plataforma, assim como as t´ecnicas de programa¸c˜ao consa-
gradas em tais ambientes. Para tornar a leitura mais clara, os algoritmos shuffle e s l i ce,
s˜ao apresentados respectivamente nas se¸c˜oes 3.3 e 3.4 separadamente. Para cada vers˜ao
de alto desempenho de um algor itmo s˜ao propostas duas a bordagens de distribui¸c˜ao de
carga (escalonamento).
31
3.1 Aglomerados de Computadores
Um aglomerado de computadores (conhecida pela sigla internacional NOW, Network
of Workstations) ´e uma rede dedicada a unir diversos computadores com o objetivo de
cooperarem na resolu¸c˜ao de problemas complexos. A conex˜ao das m´aquinas ´e realizada
utilizando-se uma infraestrutura de rede e software especial.
O que caracteriza a ar quitetura de um aglomerado ´e cada computador possuir seu
espa¸co de endere¸camento exclusivo. Uma vez que a mem´oria n˜ao ´e compartilhada, cada
conjunto de dados relevante para o c´alculo deve ser atribu´ıdo a uma das parti¸c˜oes do
espa¸co total de mem´oria existente. Desta forma, os dados precisam ser explicitamente
particionados. Ao mesmo tempo que essa caracter´ıstica adiciona complexidade na progra-
ma¸c˜ao ela encoraja o desenvolvedor a explorar a localidade. Localidade ´e a caracter´ısticas
de aproximar o dado r elevante ao processa mento de cada tarefa do processador que est´a
executando a tarefa [23]. Trantando-se portanto de uma caracter´ıstica importante para
atingir bons resultados em plataformas de alto desempenho. Uma vez que permite aos
processadores explorarem ao m´aximo o uso de suas mem´orias cache [23, 35].
Das caracter´ısticas citadas anteriormente surge um fator que deve ser levado em con-
sidera¸c˜ao no desenvolvimento de aplica¸c˜oes em aglomerados: sempre que dois processos
trocam da dos ´e necess´ario realizar um processo de sincroniza¸c˜a o. O processo de sincro-
niza¸c˜ao ´e realizado utilizando-se primitiva s para envio e recebimento de mensagens. Tais
primitivas s˜ao a base para o desenvolvimento de aplica¸c˜oes paralelas em aglomerados. A
terminologia troca de mensagens serve para denominar o paradigma utiliza do na constru-
¸c˜ao dessas aplica¸c˜oes.
As solu¸c˜oes de alto desempenho apresentadas neste trabalho utilizam uma platafo r ma
do tipo aglomerado de computadores. O padr˜ao de comunica¸c˜ao adotado ´e MPI [23, 35]
(do inglˆes, Mess age Pass i ng Interface) um padr˜ao consolidado para troca de mensagens
em aglomerados de computadores [24]. Na programa¸c˜ao por troca de mensagens s˜ao
criados diversos processos. Cada processo sendo designado a um computador. MPI
provˆe primitivas para cada processo receber um identificador ´unico e conhecer o n´umero
total de pro cessos em uma dada execu¸c˜ao . Um resumo das primitivas MPI utiliza da s
nesse trabalho e o seu significado ´e apresentado a seguir:
• MPI_Comm_rank - r etorna o identificador ´unico do processo;
• MPI_Comm_size - r etorna o n´umero tota l de processos executando a aplica¸c˜ao;
• MPI_Send - envia dados para um determinado processo;
• MPI_Recv - recebe dados de um determinado processo;
• MPI_Bcast - transmite dados para todos os processos do sistema;
32
• MPI_Reduce - recebe dados de todos os processo do sistema aplicando uma opera¸c˜ao
alg´ebrica;
A primitiva MPI_Send sincroniza com a primitiva MPI_Recv e vice-versa. Trata ndo-se
portanto de uma das principais primitivas envolvidas na implementa¸c˜ao dos algoritmos
para aglomerados de computadores. MPI_Bcast sincroniza diversos processos, funcio-
nando como uma barreira, onde ao final todos os processos recebem o mesmo conjunto de
dados. MPI_Reduce agrupa dados de diversos processo em um ´unico processo ao mesmo
tempo que realiza uma opera¸c˜ao alg´ebrica sobre os dados transmitidos.
Os aspectos de programa¸c˜ao utilizando MPI se tornam relevantes para a compreens˜ao
do presente trabalho. Importante ressaltar que cada processo conhece o n´umero total de
processos (MPI_Comm_size) e o seu identificador ´unico em uma execu¸c˜ao (MPI_Comm_rank).
Assim, a comunica¸c˜ao pode ser facilmente implementada sem a configura¸c˜ao de parˆame-
tros de baixo n´ıvel dependentes do protocolo de comunica¸c˜ao, tais como porta TCP ou
endere¸co IP das m´aquinas. Uma vez que MPI encapsula as primitivas b´asicas de comu-
nica¸c˜ao, o uso dessa biblioteca permite uma f´acil adapta¸c˜ao a diferentes tecnolo gias de
rede.
3.2 MVD em Paralelo
A id´eia da paraleliza¸c˜ao da Multiplica¸c˜ao Vetor-descritor (MVD) ´e distribuir algebri-
camente a multiplica¸c˜ao do vet or dentro do somat´orio. Desta forma, temos por exemplo
a possibilidade de executar a multiplica¸c˜ao do vetor por cada um dos termos de fo r ma
independente, como pode ser visto na equa¸c˜ao 11. Todavia, a maneira de distribui¸c˜ao da
multiplica¸c˜ao depende da propriedade alg´ebrica utilizada pelo algoritmo. Isso diferencia
as vers˜oes paralelas do shuffle e do slice.
m
k=1
N
i=1
Q
i
k
x =
m
k=1
N
i=1
Q
i
k
x
(11)
A MVD ocorre diversas vezes (tipicamente centenas ou milhares de vezes) para resol-
ver um modelo. Todavia, a paraleliza¸c˜ao dos algoritmos shuffle e slice, leva em conside-
ra¸c˜ao que a cada passo os processos calculam diversos resultados parciais. Precisamente,
cada processo p calcula um vetor parcial x
p
. O alg oritmo 1 ilustra como funciona a parale-
liza¸c˜ao de uma itera¸c˜ao onde a MVD ´e realizada. Na nota¸c˜ao do algoritmo 1, assim como
em outros algoritmos deste trabalho, adota-se a vari´avel procs para determinar o n´umero
total de processos existentes no ambiente de execu¸c˜ao (equivalente a uma chamada da
fun¸c˜ao MPI_Comm_size) e a vari´avel p para determinar cada processo (equivalente a uma
chamada da fun¸c˜ao MPI_Comm_rank) [24].
33
Algoritmo 1 Estrat´egia de paraleliza¸c˜ao em alto n´ıvel.
1: //Enquanto n˜ao atingi um crit´e rio de parada realiza a MVD
2: enquanto e rro < m´ınimo OU itera¸c˜ao > m´aximo fa¸ca
3: //Cada processo p calcula vetor parcial x
k
p
4: //Cada processo p en via vetor parcial x
k
p
para processo 0
5: //Processo 0 calcula novo vetor x
k+1
=
procs
p=0
x
k
p
6: //Processo 0 envia x
k+1
os outros processos
7: fim enquanto
Repare que na linha 2 do algoritmo 1, a MVD ´e realizada por um n´umero indetermi-
nado de itera¸c˜oes. Todavia, para solucionar modelos com um grau de confian¸ca razo´avel,
o erro aceito ´e em torno de 10
−9
o que exige um n´umero elevado de itera¸c˜oes [18]. Alguns
m´etodos iterativos para a solu¸c˜ao de sistemas de equa¸c˜oes lineares podem n˜ao convergir
para um resultado com o erro m´ınimo estipulado. Quando isso ocorre, os valores do vetor
oscilam sem uma tendˆencia clara a cada passo. Para evitar que o m´etodo execute por um
n´umero indeterminado de itera¸c˜oes, na linha 2, existe um n´umero m´aximo de itera¸c˜oes
toler´aveis para que o sistema chegue a um resultado. Caso este n´umero seja atingido,
mesmo que a resposta ainda n˜ao tenha a precis˜ao desejada, o algoritmo termina.
broadcast
Proccess 0 Proccess 1 Proccess 2 Proccess 3
broadcast
x
k+1
3
x
k+1
2
x
k+1
1
x
k+1
0
x
k
x
k+1
=
procs
p=0
x
k+1
p
.
.
.
.
.
.
.
.
.
.
.
.
x
k+1
x
k+2
1
x
k+2
2
x
k+2
3
x
k+2
0
Figura 5 : Diagrama de comunica¸c˜ao para a MVD em paralelo.
Na linha 3 do algoritmo 1, cada processo p multiplica uma parte do descritor pelo
vetor da itera¸c˜ao atual (x
k
) gerando parte do vetor da pr´oxima itera¸c˜ao (x
k+1
p
). A parte
do descritor que cada processo multiplica varia dependendo do algoritmo. Por´em, a
multiplica¸c˜ao de cada termo de forma independente pode ser realizada diretamente, como
visto na equa¸c˜ao 11. Pa ra obter-se o vetor da pr´oxima itera¸c˜ao, ´e necess´a rio somar todos
os vetores parciais (x
k+1
p
). Assim, nas linhas 4 e 5, cada processo envia o seu vetor parcial
para o processo de identifica¸c˜ao 0 e este fica encarregado de somar os vetores pa raciais
(x
k+1
p
) construindo o vetor da pr´oxima itera¸c˜ao x
k+1
. Ao final, na linha 6, o processo
34
0 envia o vetor da pr´oxima itera¸c˜ao (x
k+1
) para todos os outros processos (ou seja, em
broadcast). Ao final deste algoritmo, cada processo possui o vetor da pr´oxima itera¸c˜ao e
uma nova etapa de MVD pode iniciar.
O resultado do procedimento da MVD realizada em paralelo ´e que a cada itera¸c˜ao
os processos recebem o vetor da itera¸c˜ao atual x
k
, cada processo multiplica este por uma
parte do descritor gerando um vetor parcial da pr´oxima itera¸c˜ao x
k+1
p
. O processo de
menor identifica¸c˜ao (processo 0) acumula os vetores parciais gerando o veto r da pr´oxima
itera¸c˜ao (x
k+1
) e este ´e t ransmitido para todos os outros processos. Este ciclo se repete at´e
que o resultado atinja um erro m´ınimo ou um n´umero m´aximo de itera¸c˜oes previamente
estipulados. A figura 5, ilustra como funciona a comunica¸c˜a o entre os processos em alto
n´ıvel. Neste diagrama, a cada itera¸c˜ao k o vetor ´e transmitido para todos os processos
que calculam resultados parciais. O s resultados pa rciais s˜ao posteriormente somados no
processo 0, gerando o vetor da pr´oxima itera¸c˜ao que novamente ´e enviado a todos processos
iniciando um novo ciclo.
3.3 Shuffle Paralelo
O c´alculo espec´ıfico que ser´a realizado por cada processo ´e independente da estrat´egia
apresentada no algoritmo 1. Dependendo do algoritmo utilizado, shuffle ou sli ce, as possi-
bilidades de distribuir o processamento variam. Dessa maneira, o processamento realizado
por cada processo , linha 3, ´e diferente em cada caso espec´ıfico. Apresentaremos a seguir a
estrat´egia de paraleliza¸c˜ao para o algoritmo shuffle onde s˜ao discutidas duas abordagens
de escalonamento (distribui¸c˜ao de carga).
3.3.1 Abordagem de Escalonamento Simples
Na primeira abordagem, cada termo constitui uma tarefa independente e o n´umero
total de termos ´e conhecido. Uma vez que o descritor ´e a soma de diversos termos,
podemos efetuar a multiplica¸c˜ao de cada termo pelo vetor de forma independente. Assim,
´e poss´ıvel distribuir o la¸co que distribu´ı a multiplica¸c˜ao do veto r por cada termo.
Algoritmo 2 Shuffle utilizando abordagem de escalonamento sem considerar custos.
1: //Cada processo p come¸ca a computar o termo de mesmo ´ındice
2: t = p
3: //Enquanto existem termos para computar
4: enquanto t < terms fa¸ca
5: //Aplica o shuffle no termo t e n o vetor atual x
k
, acumula o resultado em x
k+1
p
6: x
k+1
p
= x
k+1
p
+ Shuffle(x
k
, t)
7: //Calcula o pr´ox imo termo de p baseando-se no n´umero total de processos
8: t = t + procs
9: fim enquanto
35
No algoritmo 2, ´e apresentado como a divis˜ao dos termos que cada processo dever´a
computar ´e realizada. Nesse algoritmo, terms representa o n´umero t otal de termos do
descritor executando em um ambient e com procs processos, cada um identificado pela
vari´avel p . Para g arantir que n˜ao haja c´alculo redundante, em outras palavr as, que dois
ou mais pro cessos n˜ao realizar˜ao o mesmo c´alculo, cada processador p come¸ca calculando
o termo (ou tarefa) de mesmo ´ındice que a identifica¸c˜ao do processo, linha 2. Esse ´ındice
recebe, a cada execu¸c˜ao do la¸co o n´umero total de processos (procs) mais ele mesmo
t = t + procs, linha 8. Assim, garanti-se que as tarefas designadas a cada processo n˜ao
coincidam. Mesmo quando a divis˜ao do n´umero de tarefas pelo n´umero de processadores
n˜ao ´e exata, esse algoritmo ´e capaz de distribuir o resto da divis˜ao.
2 8 11
lista de termos
9
tarefas do processo 0
tarefas do processo 2
tarefas do processo 1
5
0 1 3 4 6 7 10 12 13 14 15
Figura 6: Abordagem de distribui¸c˜ao de carga para o shuffle sem considerar custos.
Para exemplificar esta abordagem de escalonamento, apresentamos uma situa¸c˜ao de
execu¸c˜ao hipot´etica com 16 termos (numerados de 0 a 15 ) sendo executado por 3 processos
(identificados de 0 a 2), vista na figura 6. Na figura cada ´ındice da lista de termos ´e
designado para um processo, onde o padr˜ao de preenchimento indica o processo para o
qual um termo foi designado. Nesse caso, o primeiro processo (identificador 0) receberia
os termos de ´ındices 0, 3, 6, 9, 12 e 15 (prenchidos com
). O segundo processo, de
identificador 1, receberia os termos de ´ındice 1, 4, 7 , 10 e 13 (prenchidos com ). O terceiro
processo r eceberia os termos de ´ındices 2, 5, 8, 11 e 14 (prenchidos com
). Garantindo
que os processos n˜ao realizem c´alculo redundante e recebam aproximadamente o mesmo
n´umero de tarefas. Repare que esse algoritmo n˜ao imp˜oe restri¸c˜oes ao n´umero de processos
que dever˜ao executar uma aplica¸c˜ao. No entanto, n˜ao faz sentido executar a aplica¸c˜ao
com um n´umero de processos maior que o n´umero de tarefas (ou termos). Pois nessa
situa¸c˜ao, alg um processo n˜ao realizaria c´alculo.
Apesar dessa abordagem apresentar um m´etodo direto e eficaz de realizar a distribui¸c˜ao
de carga, o fato de n˜ao considerar o custo das tarefas pode ocasionar, em determinadas
situa¸c˜oes onde os termos possuem custos muito discrepante, um resultado pouco eficiente.
Apresentaremos a seguir uma vers˜ao de escalonamento para o shuffle que leva em conta
o custo computacional das tarefas.
36
3.3.2 Escalonamento Considerando Custos
A segunda abordagem de escalonamento considera os custos computacionais envolvidos
no c´alculo de cada uma das tarefas. Uma vez que o n´umero de elementos nulos varia em
cada uma das matrizes, a multiplica¸c˜ao de cada termo pelo vetor apresenta tipicamente
diferentes custos de um termo para outro. Nesse sentido, foi proposto um algoritmo
que tenta equilibrar a carga total de trabalho em cada processo. A id´eia no algoritmo
´e criar uma lista de tarefas (ou seja, termos) contendo o custo e ´ındice de cada um.
Posteriormente, ordena-se esta lista por custo em ordem decrescente. Uma vez que a lista
est´a ordenada, se percorre a lista designando uma tarefa sempre ao processo com menor
carga.
Algoritmo 3 Shuffle utilizando segunda abordagem de escalonamento, considerando cus-
tos.
1: //Gera lista contendo o ´ındice e o custo de cada tarefa
2: para t = 0 at´e terms − 1 fa¸ca
3: //Calcula custo d e processamento de cada termo, usand o equa¸c˜a o 9
4: ListaDeTarefas[t].custo =
N
i=1
n
(t)
i
×
N
i=1
nz
(t)
i
n
(t)
i
5: //Associa o termo correspondente a tarefa
6: ListaDeTarefas[t].indice = t
7: fim para
8: //Ordena a lista de tarefas por custo em ordem decrescente
9: OrdenaDecrescente(ListaDeTarefas)
10: para t = 0 at´e terms − 1 fa¸ca
11: menosCarregado = 0
12: //Encontra o processo com menos carga
13: para p = 0 at´e pro cs − 1 fa¸ca
14: se ( Carga[p] < Carga[menosCarregado] ) ent˜ao
15: menosCarregado = p
16: fim se
17: fim para
18: //Adiciona na lista de tarefas do processo com menos carga a tarefa atual
19: Ta r efas[menosCarregado].adiciona(ListaDeTarefas[t].indice)
20: //Atualiza a in f orma¸c ˜ao de carga total desse proces so com a carga da tarefa atual
21: Carga[menosCarregado] = Carga[menosCarregado] + (ListaDeTarefas[t].custo)
22: fim para
O alg oritmo 3, apresenta essa id´eia de escalonamento de forma detalhada. Primeira-
mente, o custo computacional do c´alculo de cada termo ´e realizado na linha 4 utilizando-se
a equa¸c˜ao 9 apresentada no cap´ıtulo 2. A medida que o custo de cada termo ´e calculado
os termos s˜ao inseridos numa lista com seus respectivos ´ındices, linha 6. Ap´os esse proce-
dimento, ordena-se a lista de tarefas por custo em ordem decrescent e, colocando a tarefa
de maior custo no in´ıcio da lista
1
. As etapas descr itas anteriormente, tornam poss´ıvel
1
A implementa¸c˜ao utiliza o m´etodo de ordena¸c˜ao quicksort que apresenta complexidade O(nlogn) [28].
37
percorrer a lista de termos de forma a atribuir cada tarefa ao processo com menor custo,
procedimento realizado nas linhas 10 a 2 2. Nesse la¸co, a cada itera¸c˜ao, seleciona-se o
processo com menor carga, linhas 13 a 17, atribuindo-lhe a tarefa. Uma vez que a tarefa
´e atribu´ıda, linha 19, atualiza-se a carg a total do processo, linha 21. Esse procedimento ´e
repetido at´e que todas as tarefas tenham sido designadas aos processos.
Ao final desse procedimento, as tarefas designadas a cada processo s˜ao conhecidas po r
todos. Isso implica que todos os processos realizam o algoritmo de distribui¸c˜ao de carga
simultaneamente. Com isso, acrescenta-se uma parcela de pr´e-processamento realizada
antes da MVD. Entretanto, este processamento n˜a o possui um custo significativo pois,
na maioria dos casos, o n´umero de termos ´e tipicamente pequeno.
3.4 Slice Paralelo
O alg oritmo s l i ce utiliza a propriedade da decomposi¸c˜ao de um produto tensorial em
fatores normais unit´arios aditivos (ou fato r es). Um fator ´e basicamente um elemento
composto pela multiplica¸c˜ao sucessiva de apenas um elemento n˜ao nulo de cada matriz de
um termo. Esta propriedade foi apresentada no cap´ıtulo 2, equa¸c˜ao 10. A id´eia que deu
origem ao algoritmo slice foi a de realizar a gera¸c˜ao dos fatores em um pr´e-processamento
guardando apenas estes e a ´ultima matriz de cada termo.
Para realizar o mapeament o dos elementos da ´ultima matriz de um termo no DM,
guarda-se o ´ındice desta e associa-se um ´ındice a cada fator (AUNF) juntamente com
o resultado das multiplica¸c˜oes sucessivas. Em outras palavras, cada fator ´e composto
por trˆes informa¸c˜oes (E, i, j), onde E ´e o resultado das multiplica¸c˜oes sucessivas de cada
elemento n˜ao nulo das N − 1 primeiras matrizes de um termo; i, j s˜ao respectivamente os
´ındices de linha e coluna deste elemento na matriz gerada resultante do produto tensorial
entre as N − 1 matrizes de um termo.
A gera¸c˜ao dos fatores (AUNFs) ´e realizada em uma etapa de pr´e-processamento uma
´unica vez. Portanto, essa etapa n˜ao representa uma por¸c˜ao significativa do c´alculo. Uma
vez gerada a lista de fatores, a mesma ´e a rmazenado e utilizada a cada etapa da MVD.
Independente do n´umero total de itera¸c˜oes necess´a r ia s para a resolu¸c˜ao dos modelos esses
valores permanecem constantes. A presente a bordagem apresenta um custo de mem´oria
diferente do sh uffle que armazena apenas as matrizes utilizando compacta¸c˜ao HBF
2
, pois
uma vez que a lista de fatores ´e gerada torna-se necess´ario armazenar somente essa e a
´ultima matriz de cada termo.
2
HBF ´e um forma to compacto para arma zenamento de matrizes, a sigla faz men¸c˜ao as pessoas envol-
vidas na constru¸c˜ao do formato: Harwell Boeing Form.
38
3.4.1 Primeira Abordagem de Escalonamento
Essa abordagem ´e bastante semelhante a primeira t´ecnica utilizada para o s h uffle.
Apesar de n˜ao explorar os aspectos positivos da divis˜ao de tarefas em um gr˜ao menor
proporcionadas pelo slice, tal abordagem se torna atraente por permitir que a gera¸c˜ao dos
AUNFs de cada termo possa ser realizada de forma distribu´ıda.
Como a gera¸c˜ao dos fatores ´e realizada para cada termo e cada termo ´e uma tarefa inde-
pendente, n˜ao ´e necess´ario que todos os processos realizem a etapa de pr´e-processamento.
Cada processo pode computar apenas a lista de fatores dos termos que ir´a efetivamente
multiplicar a cada itera¸c˜ao. Desta forma, antes de iniciar o procedimento iterativo que re-
aliza diversas vezes a MVD ( algoritmo 1), pode-se realizar o pr´e-processamento de forma
distribu´ıda. Devido a considerar cada t ermo como uma tarefa, essa abordagem assemelha-
se bastante com a primeira abordagem de escalonamento proposta para o shuffle.
Algoritmo 4 Slice utilizando abordagem simples de escalonamento
1: //Cada processo p efe tua o pr´e-proce ssamento dos termos relevantes
2: t = p
3: enquanto t < terms fa¸ca
4: //Realiza a gera¸c˜ao dos fatores para o termo
5: ListaFatoresNormais[t] = calculaFatoresNormais(t)
6: t = t + procs
7: fim enquanto
8: //Enquanto n˜ao atingi um crit´e rio de parada realiza a MVD
9: enquanto e rro < m´ınimo OU itera¸c˜ao > m´aximo fa¸ca
10: t = p
11: enquanto t < terms fa¸ca
12: //Aplica o slice no termo t e no vetor atual x
k
, acumula o resultado em x
k
p
13: x
k
p
= x
k
p
+ slice(ListaFatoresNormais[t], t, x
k
)
14: t = t + procs
15: fim enquant o
16: fim enquanto
De forma geral, o algoritmo 4 mostra como a estrat´egia de paraleliza¸c˜ao pode incluir
o pr´e-processa mento. As linhas 1 a 7, mostram a gera¸c˜ao de uma lista de fatores normais
para cada termo t. Posteriormente, nas linhas 8 a 16, a resolu¸c˜ao do sistema ´e realizada
por diversas itera¸c˜oes onde a cada passo o processamento ´e realizado de forma idˆentica
ao apresentado na primeira a bordagem de escalonamento do shuffle (linhas 10 a 15).
A principal vantagem desta abordagem ´e n˜ao existir interdependˆencia entre as tarefas,
possibilitando o particionamento do conjunto de dados. Pois cada termo somente precisa
ser armazenado pelo processo ao qual foi designado. Entretanto, esta abordagem n˜ao
se beneficia da caracter´ıstica do slice de poder quebrar as tarefas em g r˜aos menores.
A pr´oxima abordagem visa justamente implementar um a lgoritmo de balanceamento de
carga com essa caracter´ıstica.
39
3.4.2 Escalonamento por AUNF
O objetivo principal dessa abordagem ´e considerar cada fator (AUNF) como sendo
uma tarefa independente das outra s. A motiva¸c˜ao para tal abordagem ´e a possibilidade
de quebrar o problema em unidades de da dos com menores custo s de processamento. Em
outras palavras, aumenta-se o n´umero de tarefas reduzindo o custo computacional de cada
uma.
A id´eia central ´e criar uma lista de fatores que ser˜ao multiplicados por cada processo.
Assim, durante a etapa de pr´e-processamento, ´e poss´ıvel atribuir cada fator (tarefa) a
um processo, uma vez que o n´umero total de tarefas ´e conhecido a priori. Apesar de
tornar o gr˜ao da aplica¸c˜ao menor, essa abordagem impossibilita a distribui¸c˜ao da etapa
de pr´e- processamento.
Algoritmo 5 Sli ce, detalhe do pr´e-processamento, considerando cada AUNF como uma
tarefa.
1: //Computa o n´umero total de fatores
2: T otalDeAunf s = 0
3: para t = 0 at´e terms − 1 fa¸ca
4: produto = 1
5: N = t.NumeroDeMatrizes
6: //Da primeira a pen´ultima matriz
7: para i = 0 at´e N − 2 fa¸ca
8: //Efetua o p rodut´orio dos elementos n˜ao nulos de cada matriz i do termo
9: produto =(t.pegaMatriz(i)).NumNaoNulos()×produto
10: fim para
11: T otal DeAunfs = T otalDeAunfs + pro duto
12: fim para
13: //Calcula a divis˜ao inteira do n´umero de fatores
14: Fatores =TotalD eAunfs ÷ procs
15: //Calcula resto da divi s ˜ao
16: Resto =TotalDeAunfs % procs
17: //Calcula quan tos fatores s˜ao designados a cada processo p
18: para p = 0 at´e procs − 1 fa¸ca
19: //Recebe a divis˜ao inteira do n´umero d e tarefas
20: To t alDeTarefas[p] = Fatores
21: //Se a divis˜ao n˜ao ´e exata, recebe parte do resto
22: se ( p < Resto ) ent˜ao
23: TotalDeTarefas[p] = TotalDeTarefas[p] + 1
24: fim se
25: fim para
No algoritmo 5, ´e mostrado como o pr´e-processamento ´e realizado de forma a gerar
uma lista de tar efa s para cada processo. Ap´o s a execu¸c˜ao de tal etapa, ainda no pr´e-
processamento, ´e efetuado a gera¸c˜ao dos fatores. Neste processo, a ´ultima matriz de cada
termo ´e associada a cada tarefa. Garantindo assim que a multiplica¸c˜ao dos fatores pela
40
´ultima matriz de cada termo possa ser realizada de forma independente do termo ao qual
est˜a o a ssociadas.
Algoritmo 6 Slice utilizando abordagem que considera cada AUNF como uma tarefa.
1: //Cada processo p percorre a sua lista de tarefas
2: para taref a = ListaDeT arefas[p][0] at´e UltimaT aref a fa¸ca
3: //Aplica o s l i ce na tarefa atual gerando o vetor parcial (x
k+1
p
) da pr´oxima itera¸c˜ao
4: x
k+1
p
= x
k+1
p
+ Slice(x
k
, tar ef a)
5: fim para
Utilizando essa id´eia, o c´alculo que cada processo efetua em uma itera¸c˜ao fica como no
algoritmo 6. Nesse algoritmo os processos consideram como cada tarefa indep endente um
AUNF o que propicia uma distribui¸c˜a o de carga mais justa. Dividindo-se os termos em
peda¸cos menores pode-se realizar uma distribui¸c˜ao de carga bastante precisa, na qual a
diferen¸ca de processamento de um processo para outro n˜ao afeta de maneira significativa
o desempenho geral da aplica¸c˜a o.
41
Cap´ıtulo 4
Resultados
Os resultados obtidos pelas implementa¸c˜oes dos algoritmos propostos no presente tra-
balho ser˜ao apresentados atrav´es de gr´aficos de acelera¸c˜ao (speedup). Essa m´etrica visa
comparar o tempo de execu¸c˜a o da aplica¸c˜ao seq
¨
uencial com o obtido ap´os a paraleli-
za¸c˜ao [35]. Formalisando, se uma aplica¸c˜a o seq
¨
uencial leva um tempo T
seq
para uma
determinada entrada de dados, e executando-a em paralelo com p processadores a mesma
aplica¸c˜ao leva um tempo T
p
, diz-se que o speedup o btido com esta aplica¸c˜ao ´e dado pela
raz˜ao entre o tempo seq
¨
uencial e o tempo para lelo, como apresentado na equa¸c˜ao 12.
speedup =
T
seq
T
p
(12)
Os resultados apresentados fora m obtidos utilizando a m´edia de 10 execu¸c˜oes cada
uma realizando 100 itera¸c˜oes. O tempo de uma itera¸c˜ao foi medido utilizando o tempo
real da execu¸c˜ao com um cronˆometro interno `a aplica¸c˜ao. Neste tempo f oi inclu´ıdo o
tempo necess´ario para a transmiss˜ao do veto r e dos vetores parciais. A qualidade dos
resultados apresentados foi garantida atrav´es da observa¸c˜ao do desvio padr˜ao. Por raz˜oes
de clareza e espa¸co os detalhes de cada execu¸c˜ao n˜ao s˜ao a presentados nesta se¸c˜ao mas
no apˆendice C. Nesse apˆendice s˜ao apresentados a m´edia, o desvio padr˜ao, o speedup e a
eficiˆencia para cada execu¸c˜ao realizada.
4.1 Plataforma de Teste
A plataforma de testes utilizada ´e um aglo merado de computadores, cluster, deno-
minado i-cluster2. Esta m´aquina foi o primeiro supercomputador francˆes baseado na
fam´ılia de processador es Itanium-2 de 64 bits. O desempenho do i-cluster2 foi medido
utilizando o bench mark Linpack. Atingindo a marca de 5 61 GigaFlops (bilh˜oes de opera-
¸c˜oes de ponto flutuante por segundo). Em novembro de 2003, esta m´aquina ficou em 283
o
42
1 0 1 0
0 1 1 0
0 0 9 0
0 0 1 2
⊗
1 0 0
0 4 0
0 0 1
⊗
1 0 1
0 1 0
3 0 1
+
2 6 7 0
0 0 8 0
0 0 9 0
1 0 0 2
⊗
2 0 0
3 1 0
0 0 1
⊗
0 0 0
4 0 0
0 0 0
+
Figura 7: Exemplo de descritor com dois termos, cada um com trˆes matrizes.
lugar na lista das 500 m´a quinas mais velozes do mundo (TOP 500) [26 ].
Cada um dos 104 n´os desta plataforma possui dois processadores Itanium-2
1
de 64
bits operando a 900 Mhz. Equipados com 3 GB de mem´oria e 72 GB de disco r´ıgido.
Os computadores s˜ao interconectados por uma rede de baixa latˆencia Myrinet. No
total, o i-cluster2 ´e composto por 208 processadores, 312 GB de mem´orias, somando
uma capacidade de armazenamento em disco de 7,5 TB (TeraBytes). Em rela¸c˜ao ao
software, cada computador que comp˜oe o icluster-2 utiliza sistema operacional Linux
(kernel 2.4.21-32.0.1 .EL global) com a distribui¸c˜ao Red Hat (Enterprise Linux AS 3). A
biblioteca utilizada para a programa¸c˜ao MPI ´e lammpi.
Para ga r antir que outras aplica¸c˜oes n˜ao interferissem na execu¸c˜ao dos testes, pelo uso
da rede, o icluster-2 foi utilizado exclusivamente durante os testes. Desta forma, afir-
mamos que n˜ao havia transmiss˜oes de outras aplica¸c˜oes ocorrendo durante cada execu¸c˜ao.
Para mitigar o efeito de cache a cada experiment o, o a mbiente de execu¸c˜ao era restaurado.
Isto f oi realiza do utilizando o comando lamclean que remove arquivos t empo r ´arios, desa-
locando recurso s e cancela ndo registros de processos. A utiliza¸c˜ao deste comando garante
que a cada execu¸c˜ao realizada o estado de cada um dos n´os ´e semelhante ao obtido ap´os
uma r einicializa¸c˜ao dos daemons do MPI.
4.2 Casos de Teste
Como descrito no cap´ıtulo 2, a entrada da aplica¸c˜ao ´e um descritor markoviano (DM)
que consiste na soma consecutiva de uma s´erie de termos produto-tensoriais. Estes ter-
mos s˜ao carregados utilizando como entrada um arquivo composto por diversas matrizes.
Supondo um descritor com 2 termos, cada um contendo 3 matrizes como visto na figura 7,
o ar quivo de entrada seria como visto na figura 8. Neste formato de entrada, uma linha
precedida por “#” indica um coment´ario.
Foram utilizados quatro casos de teste para verificar o desempenho obtido com a s
implementa¸c˜oes paralelas propostas nesse trabalho. Dois casos de teste fora m estudos de
caso reais de modelagem anal´ıtica estruturada utilizando o formalismo SAN. O primeiro
1
Estes processadores possuem cada um uma mem´orica cache de 3MB.
43
# termo tensorial 0
3 # quantidade de matrizes que comp~oe este termo
4 # ordem da primeira matriz
1 0 1 0
0 1 1 0
0 0 9 0
0 0 1 2
3 # ordem da segunda matriz
1 0 0
0 4 0
0 0 1
3 # ordem da terceira matriz
1 0 1
0 1 0
3 0 1
# termo tensorial 1
3 # quantidade de matrizes que comp~oe este termo
4
2 6 7 0
0 0 8 0
0 0 9 0
1 0 0 2
3
2 0 0
3 1 0
0 0 1
3
0 0 0
4 0 0
0 0 0
Figura 8 : Exemplo de arquivo de entrada para descritor da figura 7.
modelo real ´e referenciado durante o texto por se¸c˜ao cr´ıtica (SC) pois representa a mode-
lagem do problema onde 16 recursos s˜ao disputadas por 4 processos. O segundo, batizado
como Misto, modela 9 m´odulos que exploram diversos parˆametros. Uma descri¸c˜ao gr´afica
mais detalhada de tais modelos pode ser visualizada no apˆendice B.
Um parˆametro relevante para determinar o aumento de desempenho de uma aplica-
¸c˜ao paralela ´e a quantidade de c´alculo distribu´ıda. Esse parˆametro se torna ainda mais
relevante em aglomerados de computadores, uma vez que nessas arquiteturas a comuni-
ca¸c˜ao representa um fator limitante da acelera¸c˜ao. A quantidade de c´alculo realizada por
cada algo ritmo varia de forma significativa. Por´em, existe um fator que colabora para o
aumento de complexidade simultaneamente em ambos algoritmos. Se um dado modelo
possui o mesmo n´umero de matrizes em cada termo e se a or dem destas matrizes s˜ao a s
mesmas, o fator releva nte dentro do escopo do trabalho que diferenciar´a estes modelos
ser´a o n´umero de elementos n˜ao nulos nas matrizes. Desta forma, defini-se que a esparsi-
dade de um descritor ´e dada pela m´edia da raz˜ao entre o n´umero de elementos n˜ao nulos
(nz
i
) e o n´umero to t al de elementos (n
i
2
) de cada matriz i. O resultado desta opera¸c˜ao ´e
a porcentagem de elementos n˜ao nulos geral do descritor. A equa¸c˜ao 13, mostra como a
esparsidade ´e calculada em um descritor composto por T termos, cada um com N matri-
zes, onde nz
(k)
i
e n
(k)
i
representam respectivamente o n´umero de elementos n˜ao nulo s e a
ordem da i-´esima matriz do k-´esimo termo.
T
k=1
N
i=1
nz
(k)
i
n
(k)
i
×n
(k)
i
N × T
× 100 (13)
44
Tabela 2: Detalhamento dos casos de teste
Teste
N
o
de
Termos
Esparsidade
N
o
de
AUNFs
Tempos Seq
¨
uenciais (s)
Shuffle Slice
SC 32 46,25 % 9469952 477,28 13,68
Misto 16 19,88 % 3280080 52,43 5,95
Denso A 16 22,13 % 10649600 57,11 13 ,1 4
Denso B 16 27,52 % 48771072 80,21 64 ,4 5
Assim, mais dois testes foram elaborados com base no modelo Misto com o intuito de
verificar o compor tamento dos algoritmos em situa¸c˜o es que envolvessem um g rande volume
de multiplica¸c˜oes. Para gerar esses dois modelos, chamados de Denso A e Denso B,
foram acrescentados elementos n˜ao nulos aleatoriamente nas matrizes do modelo Misto.
A tabela 2 mostra alguns parˆa metros relevantes de cada caso de teste. O primeiro
parˆametro ´e o n´umero de termos de cada descritor. Esse parˆametro se torna relevante
por constituir uma ta refa nos algorimtos shuffle (utilizando ambas abo r dagens de escalo-
namento) e s l i ce (primeira abordagem), limitando o n´umero de processadores que podem
ser utilizados nesses casos. Na segunda coluna, o parˆametro esparsidade mostra a po r -
centagem m´edia de elementos n˜ao nulos das matrizes de cada descritor. A terceir a coluna
apresenta o n´umero de fatores (AUNF) relevante por constituir o gr˜ao (uma tarefa indi-
vis´ıvel) na segunda a bordagem de escalonamento do algoritmo slice. A quarta e a quinta
coluna mostram os t empo s de execu¸c˜ao seq
¨
uencial (ou seja, com apenas um processa -
dor) necess´arios para realizar um passo da MVD utilizando o s algoritmos shuffle e slice
respectivamente. O tempo de execu¸c˜ao do slice neste caso n˜ao considera o tempo de
pr´e-processamento.
Nas pr´oximas se¸c˜oes, os resultados obtidos com a s abordagens de escalonamento de
ambos os algoritmos s˜ao apresentados. Na se¸c˜ao que aborda os resultados obtidos com
o algoritmo slice os tempos de pr´e-processamento s˜ao apresentados. Por uma quest˜ao
estrutural a compara¸c˜ao entre os dois algoritmos que realizam a MVD ´e realizada no
cap´ıtulo seguinte.
4.3 Resultados S huffle
Na presente se¸c˜ao s˜ao mostrados os resultados obtidos com as implementa¸c˜oes do
shuffle abo rda das no cap´ıtulo 3. Os resultados s˜ao apresentados de forma a tra¸car as
principais diferen¸cas entre os algoritmos de escalonamento propostos comparando-se o
tempo de execu¸c˜ao obtido com um determinado n´umero de processadores. Cada gr´afico
tra¸ca uma rela¸c˜ao entr e a acelera¸c˜ao obtida (eixo y) e o n´umero de processadores utilizados
(eixo x). O n´umero total de processadores utilizados ´e limitado pelo n´umero de termos
45
nas implementa¸c˜ao do shuffle.
A figura 9 apresenta dois gr´aficos com os resultados para as duas t´ecnicas de escalo-
namento apresentadas para o shuffle utilizando o caso de teste SC. A primeira t´ecnica,
mostrada na figura 9 (A), mostra valores de acelera¸c˜ao pr´oximos do ideal em alguns pon-
tos. Esses r esultados j´a apresentam-se satisfat´orios se considerado a simplicidade dessa
solu¸c˜ao. Por outro lado, observando a curva da t´ecnica que considera custos (figura 9 (B)),
conclui-se que essa abordagem, para este caso de teste, n˜ao apresenta vantagem. Outro
aspecto que chama aten¸c˜ao ´e que em determinados pontos ambas as curva s apresentam
uma estagna¸c˜ao nos valores de acelera¸c˜ao. Por exemplo, utilizando 16, 17, 18, 19, 20 e
21 processadores o speedup permanece praticamente constante. Isso se r epete em outros
intervalos, como: 13 a 15 e 22 a 31. Acredita-se que esses pontos de estagna¸c˜ao sejam
devido a distribui¸c˜a o de carga. Essa afirma¸c˜ao pode ser comprovada observando-se que,
nos pontos cujo o n´umero de processado res ´e um m´ultiplo do n´umero de tarefas (4, 8, 16
e 3 2), a acelera¸c˜ao est´a bastante pr´oxima do ideal.
0
5
10
15
20
25
30
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
speedup
número de processadores
SC
ótimo
0
5
10
15
20
25
30
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
speedup
número de processadores
SC
ótimo
(A) (B)
Figura 9: Acelera¸c˜ao do Shuffle, sem considerar custos (A) e considerando custos (B) para
o teste SC.
Na figura 10 observam-se os gr´aficos que apresentam os resultados para as duas aborda-
gens de escalonamento utilizando o caso de teste Misto. Semelhantemente aos resultados
analisados anteriormente, ambas as t´ecnicas apresentaram acelera¸c˜oes significativas. No-
vamente, percebe- se um comportamento bastante parecido. O que chama aten¸c˜ao nesses
dois gr´aficos ´e o speedup obtido com 8 processadores com os algoritmos de escalonamento.
Sem considerar custos, figura 10 (A), a acelera¸c˜ao com 8 processadores ´e maior do que
usando 7 processadores com essa mesma vers˜ao. J´a considerando custos, figura 10 (B), o
resultado com 8 processadores se monstra inferior ao obtido com 9. Esses aspectos refor-
¸cam a impress˜ao de que, na abordagem que considera custos, a rela¸c˜ao entre a quantidade
de termos n˜ao precisa ser um m´ultiplo do n´umero de processadores.
46
0
2
4
6
8
10
12
14
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
speedup
número de processadores
Misto
ótimo
0
2
4
6
8
10
12
14
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
speedup
número de processadores
Misto
ótimo
(A) (B)
Figura 10: Acelera¸c˜ao do Shuffle, sem considerar custos (A) e considerando custos (B)
para o teste Misto.
A figura 11 e a figura 12 apresentam os resultados obtidos respectiva mente com os casos
de teste Denso A e Denso B utilizando o sh uffle. Observe que para esses dois testes
as acelera¸c˜oes s˜ao praticamente as mesmas, independente da t´ecnica de escalonamento
utilizada. Ist o acontece devido ao fato que todas as tarefas possuem o mesmo custo nesses
casos de teste. A id´eia desses dois testes ´e demonstrar que mesmo com a abordagem que
considera custos, o algoritmo shuffle pode apresentar um comportamento po uco escal´avel
quando os termos possuem custos muito semelhantes. Isso acontece t amb´em devido ao
tamanho do gr˜ao ser sempre limitado pelo n´umero total de termos.
0
2
4
6
8
10
12
14
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
speedup
número de processadores
Denso A
ótimo
0
2
4
6
8
10
12
14
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
speedup
número de processadores
Denso A
ótimo
(A) (B)
Figura 11: Acelera¸c˜ao do Shuffle, sem considerar custos (A) e considerando custos (B)
para o teste Denso A.
47
0
2
4
6
8
10
12
14
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
speedup
número de processadores
Denso B
ótimo
0
2
4
6
8
10
12
14
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
speedup
número de processadores
Denso B
ótimo
(A) (B)
Figura 12: Acelera¸c˜ao do Shuffle, sem considerar custos (A) e considerando custos (B)
para o teste Denso B.
A figura 13 apresenta o detalhe da carga atribu´ıda a cada processo para algumas
configura¸c˜oes do caso de teste Misto. A carga ´e quantificada em n´umero de multiplica¸c˜oes
em ponto flutuantes. Nesta figura, os trˆes gr´aficos na parte superior apresentam o detalhe
do c´alculo realizado com 7, 8 e 9 processos respectivamente da esquerda para a direita.
A carga atribu´ıda a cada processo ´e apresentada em milhares de opera¸c˜oes de ponto
flutuante (MMP). Com 7 processos, o desempenho ´e limitado por um processo que realiza
aproximadamente 26 MMPs, j ´a com 8 processos o balanceamento de carga se apresenta de
forma mais eficiente uma vez que o processo com mais carga recebe em torno de 15 MMPs.
Por´em, ao aumentar o n´umero de processos para 9 a abordagem de escalonamento n˜ao
evolui. Como pode ser observado o processo mais carregado computa aproximadamente
15 MMPs tamb´em com 9 processadores limitando o aumento de desempenho geral da
aplica¸c˜ao.
0
2
4
6
8
10
12
14
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
speedup
número de processadores
Misto
ótimo
0
5
10
15
20
25
−1 0 1 2 3 4 5 6 7 8
carga total atribuída (MPF)
processador
0
5
10
15
20
25
−1 0 1 2 3 4 5 6 7 8 9
carga total atribuída (MPF)
processador
0
5
10
15
20
25
−1 0 1 2 3 4 5 6 7
carga total atribuída (MPF)
processador
Figura 13: Detalhe do algoritmo de balanceamento de carga, shuffle, teste Misto.
48
Tabela 3: Comparativo entre custo de pr´e-processamento e o de uma itera¸c˜ao com o slice.
Teste
Pr´e-processamento (s) Tempo Seq
¨
uencial (s)
M´edia Desvio Padr˜ao M´edia Desvio Padr˜ao
SC 39,959692 0,012540 13,688620 0,052211
Misto 1 0,688436 0,065441 5,953364 0,001414
Denso A 36,805741 0,032112 13,014060 0,019974
Denso B 15 0,569193 0,081030 80,211800 0,091440
Logo, pode-se concluir que como o gr˜ao de cada tarefa para esses m´etodos sempre ser´a
grande, os resultados obtidos n˜ao apresentam uma boa escalabilidade quando o n´umero
de tarefas n˜ao ´e divis´ıvel pelo n´umero de processadores. O desempenho geral da vers˜ao
paralela do shuffle f oi significativo. Entretant o, o compo r tamento da acelera¸c˜ao nos testes
n˜ao evolui em alguns intervalos. Isso se deve as caracter´ısticas intr´ınsecas deste algoritmo
que n˜ao permite dividir um termo em pequenas tarefas. Um das principais raz˜oes que
motivaram a paraleliza¸c˜ao do slice foi a possibilidade de quebrar os termos em mais ta refa s.
4.4 Resultados S l i ce
Esta se¸c˜ao tem como objetivo apresentar os resultados obtidos com o algoritmo slice
utilizando os mesmos casos de teste anteriores. Como j´a fo i discutido no cap´ıtulo 3, o
slice de alto desempenho inclui uma etapa de pr´e-processamento que deve ser realizada
uma ´unica vez. Nesse sent ido, a utiliza¸c˜ao da primeira abordagem de escalonamento,
que considera cada termo como uma ta r efa independente, fo i utilizada por permitir a
distribui¸c˜ao desse c´alculo.
A tabela 3 mostra os tempos de pr´e-processamento para quatro casos de teste utili-
zando a primeira abordag em de escalonamento. Nessa tabela, s˜ao apresentados tamb´em
o custo computacional para realizar uma itera¸c˜ao da MVD. Apesar do custo de uma
itera¸c˜ao ser menor que o custo de pr´e-processamento, o custo de processamento n˜ao ´e
impactante no tempo total de execu¸c˜ao. Isso porque s˜ao necess´arias centenas de itera¸c˜oes
para resolver um problema. O resultado ´e que o custo de pr´e-pro cessamento ´e dilu´ıdo ao
longo de algumas itera¸c˜oes.
Por exemplo, supo ndo que para o caso de teste SC necessita-se de 200 itera¸c˜oes pa ra
o sistema de equa¸c˜oes ser resolvido. Ao todo seriam necess´arios cerca de 2600 segundos
(200 vezes o tempo seq
¨
uencial de aproximadamente 13 segundos) para a resolu¸c˜ao do
modelo. Conseq
¨
uentemente, nessa situa¸c˜ao o temp o de pr´e-processamento, que para esse
teste ´e aproximadamente 39 segundos, representaria pouco mais de 1% do tempo total de
execu¸c˜ao. No entanto, os m´etodos iterativos de resolu¸c˜ao de sistemas de equa¸c˜oes lineares
n˜ao s˜ao determin´ısticos. Com isso, o n´umero de itera¸c˜oes necess´arias para realizar o pr´e-
49
processamento pode ser ou n˜ao ser significativo dependendo do modelo. Dessa forma,
faz-se interessante paralelizar a etapa de pr´e-processamento para abranger tais situa¸c˜oes.
A figura 14 mostra a acelera¸c˜ao obtida na etapa de pr´e-processamento quando utili-
zando a abordagem que considera cada termo como uma tarefa. Essa figura apresenta
as acelera¸c˜oes obtidas com os casos de teste SC (figura 14 (A)), Misto(figura 14 (B)),
Denso A (figura 14 (C)) e Denso B (figura 14 (D)). Com o teste SC ´e poss´ıvel observar
que o desempenho ´e melhor quando a quantidade de processadores ´e m´ultiplo do n´umero
de tarefas (4, 8, 16 e 32 processos). O caso de teste Misto apresenta um compo r t amento
semelhante.
´
E impo rt ante observar que nos casos de teste onde as tarefas possuem o
mesmo custo, figura 14 C e D, que a acelera¸c˜ao apresenta um comportamento unicamente
crescente. Isso ocorre porque nesses casos a distribui¸c˜ao de carga ´e uniforme, uma vez
que, n˜ao existe pra ticamente diferen¸ca nos custos de cada termo.
0
5
10
15
20
25
30
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
speedup
número de processadores
SC
ótimo
0
2
4
6
8
10
12
14
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
speedup
número de processadores
Misto
ótimo
(A) (B)
0
2
4
6
8
10
12
14
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
speedup
número de processadores
Denso A
ótimo
0
2
4
6
8
10
12
14
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
speedup
número de processadores
Denso B
ótimo
(C) (D)
Figura 1 4: Acelera¸c˜ao do pr´e-processa mento para o algoritmo slice.
Apesar da dist ribui¸c˜ao do c´alculo de pr´e-processamento ter sido satisfat´o r ia em alguns
casos, a necessidade de paralelizar esta etapa ´e menos significativa do que a MVD. Isso
porque o pr´e-processamento ´e computado soment e uma vez. J´a a MVD ´e uma opera¸c˜ao
efetuada diversas vezes a t´e que um modelo seja solucionado. Nesse ponto, o slice apresenta
uma vantagem em sua segunda abordagem de escalonamento por que esta considera cada
50
AUNF como sendo uma tarefa. Tornando po ss´ıvel quebrar os termos em mais tarefas de
custo menor (gr˜ao menor).
0
2
4
6
8
10
12
14
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
speedup
número de processadores
SC
ótimo
0
2
4
6
8
10
12
14
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
speedup
número de processadores
SC
ótimo
(A) (B)
Figura 1 5: Acelera¸c˜ao do Slice considerando cada termo como uma tarefa (A) e conside-
rando cada AUNF como uma tarefa (B) para o t este SC
Na figura 15 a acelera¸c˜ao obtida com a paraleliza¸c˜a o da MVD para ambas t´ecnicas de
escalonamento ´e apresentada utilizando o caso de teste SC. Faz-se importante ressaltar
que, para fins comparativos, o c´alculo de pr´e-processamento n˜ao foi considerado nos resul-
tados apresentados.
´
E percept´ıvel, comparando-se os gr´aficos (figura 15 (A) e (B)), que
a t´ecnica de escalonamento considerando cada termo como uma tarefa apresenta maior
escalabilidade. Isso comprova que a utiliza¸c˜ao de um gr˜ao menor ´e melhor. Mesmo consi-
derando que a segunda abordagem de escalonamento impede a paraleliza¸c˜ao da etapa de
pr´e-processamento.
0
2
4
6
8
10
12
14
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
speedup
número de processadores
Misto
ótimo
0
2
4
6
8
10
12
14
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
speedup
número de processadores
Misto
ótimo
(A) (B)
Figura 1 6: Acelera¸c˜ao do Slice considerando cada termo como uma tarefa (A) e conside-
rando cada AUNF como uma tarefa (B) para o t este Misto
Na figura 16 s˜ao apresentados os resultados para o caso de teste Misto com as duas
abordagens de escalonamento. De forma similar ao comportamento obtido com o caso
51
de teste SC, a utiliza¸c˜ao da segunda abordagem gera uma curva mais escal´avel. Isso
confirma a hip´otese de que a aplica¸c˜ao ´e mais adapt´avel a um gr˜ao menor. Um aspecto
que chama aten¸c˜ao nos gr´aficos da figura 16 ´e a distˆancia das curvas de speedup da curva
ideal. Nesse teste tal comportamento ´e justificado porque o tempo de execu¸c˜ao ´e bastante
pequeno utilizando a vers˜ao seq
¨
uencial do algoritmo slice, veja tabela 2. A conseq
¨
uencia
disso, ´e que como o tempo de execu¸c˜ao n˜ao ´e muito significativo, o tempo necess´ario para
transmiss˜ao dos dados n˜ao compensa tanto a utiliza¸c˜a o da vers˜ao paralela.
0
2
4
6
8
10
12
14
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
speedup
número de processadores
Denso A
ótimo
0
2
4
6
8
10
12
14
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
speedup
número de processadores
Denso A
ótimo
(A) (B)
Figura 1 7: Acelera¸c˜ao do Slice considerando cada termo como uma tarefa (A) e conside-
rando cada AUNF como uma tarefa (B) para o t este Denso A
0
2
4
6
8
10
12
14
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
speedup
número de processadores
Denso B
ótimo
0
5
10
15
20
25
30
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
speedup
número de processadores
Denso B
ótimo
(A) (B)
Figura 1 8: Acelera¸c˜ao do Slice considerando cada termo como uma tarefa (A) e conside-
rando cada AUNF como uma tarefa (B) para o t este Denso B
Nas figura 17 e 18 s˜ao apresentados, respectivamente, os resultados para os casos de
teste Denso A e Denso B. Com discutido anteriormente, esses dois modelos hipot´eticos
apresentam situa¸c˜oes onde considerar ou n˜ao o custo de cada termo n˜a o influencia no re-
sultado de escalonamento. Isso ocorre porque o custo computacional de cada tarefa nesses
dois casos ´e o mesmo. Por´em, ao utilizar a segunda a bordagem de escalonamento com
52
o slice vislumbra-se uma curva que apresenta um comportamento escal´avel. Observando
essas duas figura ´e poss´ıvel notar que, a medida que o tempo seq
¨
uencial do caso de teste
´e maior, as curvas de acelera¸c˜ao apresentam um comportamento mais pr´oximo do ideal.
Em geral, os resultados com a segunda abordagem de escalonamento do slice apre-
sentam um comportamento escal´avel e pr´o ximo do ideal. Faz-se ressalva aos casos de
teste que possuem um custo computacional baixo para a vers˜ao seq
¨
uencial. Por´em, ainda
obt´em-se resultados expressivos em tais situa¸c˜oes.
53
Cap´ıtulo 5
Conclus˜ao
O presente trabalho apresentou como t´ecnicas de alto desempenho podem ser empre-
gadas para acelerar a Multiplica¸c˜ao Vetor-descritor. Essa opera¸c˜ao ´e realizada diversas
vezes para obter estimativas de desempenho em modelos que utilizam um formalismo
anal´ıtico estruturado. Esses modelos s˜ao muito utilizados na predi¸c˜ao de desempenho de
sistemas em geral, pois apresentam uma forma mais eficiente de armazenamento do que
Cadeias de Markov. As solu¸c˜oes propostas nesse trabalho utilizam uma estrutura alg´e-
brica comum aos diversos formalismos de modelagem anal´ıtica estruturados existentes e
portanto podem ser empregadas em diferentes situa¸c˜oes.
O foco principal da paraleliza¸c˜ao foi o processo de uma etapa da MVD, opera¸c˜ao
que ´e realizada diversas vezes para inferir estimativas de desempenho de um modelo.
Por´em, os detalhes de distribui¸c˜ao de tarefas foram delineados com base nas o pera¸c˜oes
alg´ebricas envolvidas em cada um dos dois algoritmos para realizar tal opera¸c˜ao: shuffle e
slice. Para cada um dos algoritmos foram apresentadas duas abordagens de escalonamento
explorando as caracter´ısticas espec´ıficas de cada um.
Em todos os testes realizados, obteve-se uma acelera¸c˜ao (speedup) consider´avel inde-
pendentemente do algoritmo utilizado e da abordagem de escalonamento. Nesse mesmo
contexto, a utiliza¸c˜ao de diferentes abordagens de escalonamento tornou poss´ıvel estudar
aspectos relevantes na adapta¸c˜ao de aplica¸c˜oes em ambientes de alto desempenho, mais
especificamente, aglomerados de computadores (clusters). Apesar de uma completa ava-
lia¸c˜ao das diferen¸cas entre o shuffle e o slice fugir do escopo desse trabalho, discutiremos
a seguir as principais diferen¸cas entre as vers˜oes paralelas desses algoritmos utilizando os
casos de teste propostos no cap´ıtulo 4.
5.1 Compara¸c˜ao entre Shuffle e Slice
Para comparar os resultados obtidos com sh uffle e slice s˜ao mostrados dois gr´aficos
de tempo de execu¸c˜ao. Esses gr´aficos relacionam o n´umero de processadores utilizados
(eixo x) e o tempo de execu¸c˜ao obtido (eixo y) para realizar uma itera¸c˜ao da MVD. No
54
caso do algoritmo slice os tempos de pr´e-processamento, apresentados na tabela 3, n˜ao s˜ao
considerados, pois esses s˜ao referentes a uma parte do c´alculo que ´e realizada somente uma
vez e. Po rt anto, ao longo centenas o u milhares de itera¸c˜oes o tempo de pr´e- processamento
n˜ao ´e impactante no tempo total de execu¸c˜ao do mesmo.
0
50
100
150
200
250
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
tempo de execução (segundos)
número de processadores
Shuffle
0
1
2
3
4
5
6
7
8
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
tempo de execução (segundos)
número de processadores
Slice
(A) (B)
Figura 1 9: Compara¸c˜ao do tempo de execu¸c˜ao entre shuffle (A) e o slice (B) para caso de
teste SC.
Os melhores resultados obtidos com shuffle foram utilizando a abordagem de esca-
lonamento que considera o custo das tarefas. J´a com o slice, os melhores resultados
apresentados foram utilizando a abordagem de escalonamento que considera cada fator
como uma tarefa. Assim, compara-se os resultados obtidos com cada a lgoritmo utilizando
essas duas abordagens.
0
5
10
15
20
25
30
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
tempo de execução (segundos)
número de processadores
Shuffle
0
0.5
1
1.5
2
2.5
3
3.5
4
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
tempo de execução (segundos)
número de processadores
Slice
(A) (B)
Figura 2 0: Compara¸c˜ao do tempo de execu¸c˜ao entre shuffle (A) e o slice (B) para caso
Misto.
Na figura 19, os resultados em tempo de execu¸c˜ao para os dois algoritmos utilizando
o caso de teste SC s˜ao apresentados. Note que a escala utilizada nos gr´aficos ´e diferente.
Isso porque o tempo de execu¸c˜ao do algoritmo slice (figura 19 (B)) ´e significativamente
menor que o do shuffle (figura 19 (A)). Entr etanto, a mbos algoritmos apresentam um
comportamento bastante escal´a vel.
55
0
5
10
15
20
25
30
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
tempo de execução (segundos)
número de processadores
Shuffle
0
1
2
3
4
5
6
7
8
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
tempo de execução (segundos)
número de processadores
Slice
(A) (B)
Figura 2 1: Compara¸c˜ao do tempo de execu¸c˜ao entre shuffle (A) e o slice (B) para caso
Denso A.
A figura 20 mostra os resultados em tempo de execu¸c˜ao com o caso de teste Misto.
Nesse caso, as mesmas afirma¸c˜oes feitas anteriormente se aplicam pois, o comportamento
das curvas ´e ba stante semelhante. Ainda, os tempos de execu¸c˜ao obtidos com o slice
(figura 20 (B)) s˜ao bem inferiores aos obtidos utilizando o shuffle (figura 20 (A)) e por
isso as escalas dos gr´aficos s˜ao diferentes. Faz-se importante ressaltar que o n´umero de
processadores utilizados com o sl i ce, nesse caso de teste, ´e superior `a quantidade de termos.
Como o n´umero de termos ´e um fato r limitante do n´umero de processadores que podem
ser utilizados, a escalabilidade do shuffle ´e sempre limitada por esse fator. Por outro lado,
o slice pode escalar em um n´umero bem maior de processadores.
0
5
10
15
20
25
30
35
40
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
tempo de execução (segundos)
número de processadores
Shuffle
0
5
10
15
20
25
30
35
40
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
tempo de execução (segundos)
número de processadores
Slice
(A) (B)
Figura 2 2: Compara¸c˜ao do tempo de execu¸c˜ao entre shuffle (A) e o slice (B) para caso
Denso B.
Os gr´aficos da figura 21, que mostram os resultados para o teste Denso A, apresentam
as mesmas caracter´ısticas j´a mencionadas. Entretanto, nos gr´aficos com o caso de teste
Denso B (figura 22), em alguns pontos ´e poss´ıvel observar que os resultados obtidos com
o shuffle s˜ao melhores. Isso ocorre nas execu¸c˜oes com 4, 8 e 16 processadores. N˜ao por
coincidˆencia, esses s˜ao os casos cujo n´umero de processadores ´e m´ultiplo da quantidade de
56
termos. Em princ´ıpio, outro fator que contribui para esse comportamento ´e a semelhan¸ca
do tempo seq
¨
uencial de execu¸c˜ao do shuffle e do slice nesse caso de teste.
5.2 Trabalhos Futuros
Apesar do slice ter apresentado melhores resultados que o shuffle na maioria dos casos
de teste, estudos recentes apontam que a solu¸c˜ao ideal para realizar a MVD ´e uma aborda-
gem h´ıbrida [20], que misture aspectos de ambos algoritmos. Nesse sentido, a par aleliza¸c˜ao
deste algoritmo h´ıbrido poder´a explorar aspectos das abordagens de escalonamento aqui
apresentadas.
O estudo do impacto de paraleliza¸c˜ao com rela¸c˜ao `a quantidade de mem´oria utilizada
´e tamb´em outra poss´ıvel continuidade ao trabalho aqui apresentado. Principalmente em
modelos que apresentam um elevado n´umero de estados, tornando a mem´oria um fator
limitante.
Agrupar AUNFs para otimizar o volume de dados transmitidos a cada itera¸c˜ao ´e outro
poss´ıvel assunto a ser abordado em futuras investiga¸c˜oes. Entretanto, como o n´umero de
fatores tipicamente ´e bastante elevado, considerar as caracter´ısticas de cada fator um-a-
um pode levar em altos custos. O estudo de como esse a grupamento pode ser realizado
mantendo um compromisso entre tempo de escalonamento e a redu¸c˜ao na comunica¸c˜ao
torna-se necess´ar io .
5.3 Considera¸c˜ores Finais
O objetivo desse trabalho foi apresentar como t´ecnicas de alto desempenho podem ser
empregadas para acelerar a an´alise de modelos anal´ıticos estruturados. Nesse contexto, foi
contemplado o uso de MPI, uma ferrament a popular para o desenvolvimento em aglome-
rados de computadores. A escolha desse tipo de plataforma, foi motivada principalmente
pelo baixo custo envolvido em sua constru¸c˜ao. Estabelecendo um compromisso entre custo
e benef´ıcio que se adapta de maneira a a companhar a evolu¸c˜ao r´apida que ocorre com os
micro-processadores.
A principal impress˜ao deixada ap´os a an´alise dos resultados ´e que a vers˜ao paralela
do algoritmo slice apresenta melhores resultados que o shuffle. No enta nto, uma an´alise
aprofundada mostra que isso n˜ao ´e sempre verdade. Os resultados obtidos com o ´ultimo
caso de teste (Denso B) para o shuffle, po r exemplo, em alguns casos superam os resul-
tados do slice. Tamb´em ´e importante levar em considera¸c˜ao que o slice necessita de uma
etapa de pr´e-processamento. Logo, uma solu¸c˜ao h´ıbrida, que explore caracter´ısticas de
ambos os algoritmos aparentemente seja mais eficiente.
Em geral, o trabalho realizado at´e o momento apresentou resultados positivos. Essa
afirma¸c˜ao ´e atestada pelos bons desempenhos obtidos nos testes realizados. Mesmo
57
quando os tempos seq
¨
uenciais dos algoritmos n˜ao apresentavam um custo consider ´avel
para a realiza¸c˜ao da MVD estes mostraram-se adapt´aveis ao tipo de arquitetura utili-
zada. Refor¸cando as escolhas efetuadas ao longo do trabalho.
A principal contribui¸c˜ao do presente trabalho ´e apontar diretivas para o desenvolvi-
mento em aglomerados de computadores. Mesmo em diferentes formalismos, os algorit-
mos propostos podem ser utilizados. Entretanto, o trabalho iniciado aqui n˜ao se apresenta
completamente esgotado, restando assuntos a serem abordados em trabalhos futuros.
58
Referˆencias Bibliogr´aficas
[1] S. Abe, D. Place, and P. Mora. A Parallel Implementation of the Lattice Solid Model
for the Simulation of Rock Mechanics and Earthquake Dynamics. Pure and Applied
Geophysics, 161(11–12):2265–2277, 20 04.
[2] M. Ajmone Marsan, G. Balbo, G. Conte, S. Donat elli, and G. Franceschinis. Mo-
delling with Generalized Stochastic Petri Nets, Wiley Series in Parallel Computing.
John Wiley and Sons, England, 1995.
[3] Y. Akiyama, K. Onizuka, T. Noguchi, and M. Ando. Parallel Protein Information
Analysis (PAPIA) System Running on a 64-Node PC Cluster. In Workshop on
Genome Informatics, volume 9, pages 13 1–140, 1998.
[4] V. Aslot, M. Domeika, R. Eigenmann, G. Gaertner, W. B. Jones, and B. Parady.
SPEComp: A New Benchmark Suite for Measuring Parallel Computer Performance.
Lecture Notes in C omputer Scie nce, 2104:1–10, 2001.
[5] K. Atif and B. Plateau. Stochastic Automata Networks fo r Modelling Parallel Sys-
tems. IEEE Transactions on Software Engineering, 17(10):1093–1108, 1991.
[6] L. Baldo, L. Brenner, L. G. Fernandes, and A. Sales. Performance Models for
Master/Slave Parallel Programs. Electronic Notes in Theoretical Computer Science,
104(1):65–84, 2005 .
[7] L. Baldo, D. M. Cl´audio, L . G. Fernandes, P. Fernandes, M. Kolberg, P. Velho,
and T. Webber. Parallel Selfverified Method for Solving Linear Systems. In 7th
International Meeting of High Pe rformance Computing for Computational S c i ence -
VECPAR, pages 1–1 2, Rio de Janeiro, 2 006.
[8] L. Baldo, L. G. Fernandes, P. Roisenberg, P. Velho, and T. Webber. Parallel PEPS
Tool Performance Analysis Using Stochastic Automata Networks. In Euro-Par, pages
214–219, Pisa, Italy, 2004 .
[9] C. Bertolini, L. Brenner, A. Sales, P. Fernandes, and A. Z orzo. Structured Stochastic
Modeling of Fault-Tolerant Systems. In New York: IEEE Press, editor, 12th Annual
Meeting of the IEEE/ACM International Symposium on Modeling, Analysis, and
59
Simulation of Computer and Telecommunication Systems, MASCOTS’04, pages 13 9–
146, Volendam, Netherlands, 2004.
[10] L. Brenner, L. G. Fernandes, P. Fernandes, and A. Sales. Perf ormance Analysis Issues
for Parallel Implementations of Propagation Algorithm. In Publisher ACM Press,
editor, Proceedings of the 1 5th Symposium on Computer Architec ture and High Per-
formance Computing, pages 183–1 90, S˜ao Paulo, Brazil, 2003.
[11] P. Buchholz. Hierarchical Markovian Models - Symmetries and Reduction. In R.
Poo ley a nd J. Hillston, editors, 6th International Conference on Modelli ng Techni-
ques and Tools for Computer Performance Evaluation, pages 305–319, Edinburgh,
September 1992.
[12] P. Buchholz and T. Dayar. Block SOR for Kronecker structured representations.
In Proceedings of the 2003 International C onference on the Numerical Solution of
Markov Chains, pages 121–1 43, Urbana and Monticello, Illinois, USA, 20 03. Springer-
Verlag.
[13] P. Buchholz and P. Kemp er. Hierarchical Reachability Graph Generation for Petri
nets. Formal Methods in Systems Design, 21(3):2 81–315, 2002.
[14] G. Ciardo and M. Tilgner. On the Use of Kronecker Operators for the Solution of
Generalized Stochastic Petri Nets. Technical Report 96(35), ICASE, 1996.
[15] M. Davio. Kronecker Products and Shuffle Algebra. IEEE Transactions on Compu-
ters, C-30(2):116–125 , 1981.
[16] J. J. Dongarra, P. Luszczek, and A. Petitet. The LINPACK Benchmark: past, present
and future. Concurrency and Com putation: Practice and Experience, 15(9):803 – 820,
2003.
[17] L. G. Fernandes, E. Bezerra, F. Oliveira, M. Raeder, P. Velho, and L. Amara l. Probe
Effect Mitigation in the Software Testing of Parallel Systems. In Latin-American Test
Workshop LATW, pages 153–158, Buenos Aires, 2006.
[18] P. Fernandes. M´ethodes Num´eriques pour la Solution de Syst`emes Markoviens `a
Grand Espace d’
´
Etats. PhD thesis, Institut National Polytechnique de Grenoble,
Grenoble, 1998.
[19] P. Fernandes, B. Plateau, and W. J. Stewart. Efficient descriptor-Vector Multi-
plication in Stochastic Automata Networks. Journal of the ACM, 45(3):381 – 414,
1998.
60
[20] P. Fernandes, R. Presotto, A. Sales, and T. Webber. An Alternative Algorithm
to Multiply a Vector by a Kronecker Represented Descriptor. In 21th Annual UK
Performance Engineering Workshop, UKPEW, pages 57– 67, Newcastle, England,
2005.
[21] E. Gelenbe. G-Networks: Multiple Classes of Positive Customers, Signals, and Pro-
duct Form Results. Lecture Notes in Computer Science, 2459:1–16, 2002.
[22] S. Gilmore, J. Hillston, L. K loul, and M. Ribaudo. PEPA Nets: A Structured Per-
formance Modelling Formalism. Performance Evaluation, 17(10):79–104, 2003.
[23] A. Grama, A. Gupta, G. Karypis, and V. Kumar. Introduction to Parallel Computing
- Second Edi tion. Pearson - Addison Wesley, England, 1996.
[24] W. Gropp, E. Lusk, and A. Skjellum. Using MPI Portable Parallel Programming with
the Message-Passing Interface - Second Edition. The MIT Press, Lo ndon, England,
1999.
[25] M. Kolberg, L. Baldo, P. Velho, L. G. Fernandes, and D. M. Cl´audio. Optimizing a
Parallel Self-verified Method for Solving Linear Systems. In Workshop on State-of-
the-Art in Scientific and Pa rallel Computing - PARA, Umea, 2006.
[26] H. Meuer, E. Strohmaier, J. Dongarra, and H. Simon. Top 500 Supercomputer Sites.
http://www.top500.org, July 2006.
[27] J. Montagnat, F. Bellet, H. Benoit Cattin, V. Breton, L. Brunie, H. Duque, Y. Legr´e,
I. E. Magnin, L. Maigne, S. Miguet, J.-M. Pierson, L. Seitz, and T. Tweed. Medical
Images Simulation, Storage, and Processing on the European DataGrid Testbed.
Journal of Grid Computing, 2(4):3 87–400, 2004.
[28] B.M.E. Moret and H.D. Shapiro. Algorithms from P to NP. The Benja-
min/Cummings Publishing Company, INC., Redwood City, CA, USA, 1991.
[29] B. Philippe, Y. Saad, and W.J. Stewart. Numerical Methods in Markov Chain Mo-
delling. Operations Research, 40(6):1156–1179, 1992.
[30] G. F. Riley. The Georgia Tech Network Simulator. In Publisher ACM Press, editor,
AC M SIGCOMM Workshop on Mod els, Methods and Tools for Reproducible Network
Research, pages 5–12, Karlsruhe, Germany, 2003.
[31] W. H. Sanders and J. F. Meyer. Stochastic Activity Networks: Formal Definitions and
Concepts. Lectures on Formal Methods and Performance Analysis: First EEF/Euro
Summer School on Trends in Comp uter Science, 2090:315–343, 2001.
61
[32] M. Scarpa and A. Bobbio. Kronecker Representation of Stochastic Petri Nets with
Discrete PH Distributions. In 3rd I nt. Performance & Dependability Symposium
(IPDS ’98), pages 52–61, Durham (NC), 1998.
[33] P. Velho, L. G. Fernandes, M. R aeder, M. Castro, and L. Baldo. A Parallel Version
for the Propaga tion Algorithm. Lecture Notes in Computer Science, 3606:403–4 12,
2005.
[34] T. Webber. Alternativas para o Tratamento Num´erico Otimizado da Multiplica¸c˜ao
Vetor-Descritor. Disserta¸c˜ao de Mestrado, Programa de P´os-Gradua¸c˜ao em Ciˆencia
da Computa¸c˜ao - PPGCC, PUCRS, Faculdade de Inform´atica - FACIN, Porto Alegre,
Brasil, 2003.
[35] A.Y. Zomaya. Parallel and Distributed Computing Handbook. McGraw-Hill, New
York, NY, USA, 1 996.
62
Apˆendice A
SAN - Exemplo de Modelo Anal´ıtico
Estrutural
Modelos SAN s˜ao descritos geralmente de forma gr´afica onde um grafo dirigido ´e
projetado para cada m´odulo do sistema. A representa¸c˜ao gr´afica fornece uma maneira de
esquematizar o sistema em m´odulos independentes. Muitas vezes, esta separa¸c˜ao ajuda
a projetar o sistema, uma vez que m´o dulos com fun¸c˜oes diferentes podem ser modelados
separadamente e conseq
¨
uentemente, facilmente replicados. Um exemplo de modelo SAN
que ilustra isto pode ser visto na figura 23. O problema modelado neste exemplo ´e
conhecido como problema da se¸c˜ao cr´ıtica (SC). O problema da SC consiste no acesso
exclusivo de um processo a um determinado recurso. Neste exemplo, temos apenas um
processo acessando apenas um recurso. Os estados do modelo s˜a o representados pelos
v´ertices do gr afo, neste caso temos dois autˆomatos: um para representar o processo
(com trˆes estados) e outro chamado recurso (com dois estados). Repare como o processo
pode ser modelado independentemente do recurso facilitando a expans˜ao do modelo. Para
modelar o problema com um processo a mais, por exemplo, basta acrescentar um autˆomato
recurso (como mostra a figura 24).
Recurso
e
1
e
2
1
0
P rocesso
e
1
2
1
0
e
2
(π
2
)
l
1
e
2
(π
1
)
Figura 23: Modelo SAN para o problema da SC
63
No entanto, as afirma¸c˜oes anteriores n˜ao s˜ao suficientes para modelar como essas
interagem duas entidades (processo e recurso). Para modelar este comportamento, ´e
utilizado o conceito de eventos. Eventos s˜ao graficamente representados por arestas. Em
SAN, dispomos de dois tipos b´asicos de eventos: locais (pois alteram apenas o estado
de um autˆomato) e sincronizantes (pois representam uma intera¸c˜ao entre dois ou mais
autˆomatos). Em nosso exemplo, podemos detectar um evento sincronizante quando o
identificador aparece nos dois autˆomatos simultaneamente, por exemplo, o evento e
2
´e
um evento sincronizante. Foge do escopo deste trabalho fornecer uma explica¸c˜ao mais
detalhada sobre modelagem utilizando SAN. Os leitores inter essados em buscar mais
informa¸c˜oes podem consultar as referˆencias [10, 18, 34].
2
1
0
e
2
(π
2
)
e
2
(π
1
)
l
2
e
1
2
1
0
e
2
(π
2
)
l
1
e
2
(π
1
)
P rocesso
A
P rocesso
B
Recurso
e
2
1
0
e
3
e
1
, e
3
Figura 2 4: Modelo SAN para o pro blema da SC com dois processos
O Descritor Markoviano (DM) ´e uma estrutura alg´ebrica que armazena informa¸c˜oes
sobre: as transi¸c˜oes locais de cada autˆomato e os eventos sincronizantes. Para representar
as transi¸c˜oes locais, s˜a o armazenadas uma matriz para cada autˆomato. Nestas matrizes,
cada transi¸c˜ao n˜ao sincronizante de um estado i para outro estado j ´e representada por
um n´umero real positivo. Este n´umero indica a freq
¨
uˆencia com que esta tra nsi¸c˜a o ocorre
no mundo real. Por exemplo, considerando o modelo SAN para o problema da SC visto
na figura 23. Supondo-se que a transi¸c˜ao local do autˆomato processo (l
1
), do estado 1
para o estado 0, aconte¸ca com uma freq
¨
uˆencia µ, a matriz que representa algebricamente
o comportamento local deste autˆomato ser´a:
Q
(P )
l
=
0 0 0
µ −µ 0
0 0 0
Para representar algebricamente as intera¸c˜oes entre os autˆomatos s˜ao necess´arias duas
matrizes para cada autˆomato do modelo. De maneira an´a loga ao processo anterior, os
elementos destas matrizes representam a freq
¨
uˆencia com que estas transi¸c˜oes ocorrem na
realidade. Por exemplo, supondo que o evento e
1
ocorra na r ealidade com uma freq
¨
uˆencia
κ, par a cada um dos dois autˆomatos do exemplo da figura 23
1
ser˜a o criadas duas matrizes
como abaixo:
1
Os autˆomatos recurso e processo foram abreviados para R e P respectivamente.
64
Q
(R)
e
+
1
=
0 κ
0 0
Q
(R)
e
−
1
=
−κ 0
0 0
Q
(P )
e
+
1
=
0 κ 0
0 0 0
0 0 0
Q
(P )
e
−
1
=
−κ 0 0
0 0 0
0 0 0
Note que cada autˆomato tem uma matriz positiva e outra negativa para o evento e
1
.
A matriz positiva tem a mesma fun¸c˜ao da matriz local, ela indica qual transi¸c˜ao est´a
associada a f r eq
¨
uˆencia com que o evento ocorre na realidade. A par t e negativa faz um
ajuste diagonal, neste ajuste cada elemento da diagonal principal cont´em um valor que,
se somados todos os elementos de uma linha da matriz positiva com a negativa, resultar´a
zero.
O DM ´e ent˜ao uma express˜ao alg´ebrica que mapeia as diversas matrizes que comp˜oe
os modelos SAN em uma ´unica matriz. A equa¸c˜ao 14, generaliza como fica o DM para
um modelo SAN com N autˆomatos e E eventos sincronizantes.
Q =
N
i=1
Q
(i)
l
+
E
e=1
N
i=1
Q
(i)
e
+
+
N
i=1
Q
(i)
e
−
(14)
Para o exemplo apresentado na figura 23, o DM ficar´a:
Q
(P )
l
⊕ Q
(R)
l
+
Q
(P )
e
+
1
⊗ Q
(R)
e
+
1
+ Q
(P )
e
−
2
⊗ Q
(R)
e
−
2
+
Q
(P )
e
−
1
⊗ Q
(R)
e
−
1
+ Q
(P )
e
+
2
⊗ Q
(R)
e
+
2
Apesar de ser poss´ıvel resolver a express˜ao alg´ebrica do DM, gerando uma ´unica matriz
que represente o modelo, isto n˜ao ´e desejado. Uma das vantagens de se utilizar modelos
SAN em rela¸c˜ao a Cadeias de Markov ´e a utiliza¸c˜ao reduzida de mem´oria, gerando-se uma
´unica matriz essa vantagem desaparece. Neste ponto, entra em a¸c˜ao a Multiplica¸c˜ao Vetor-
descritor, ao inv´es de uma multiplica¸c˜ao de um vetor por uma matriz (Ax) o sistema de
equa¸c˜oes a ser resolvido se apresenta na forma da multiplica¸c˜ao do Descritor Markoviano
pelo vet or (Qx).
65
Apˆendice B
Semˆantica dos Modelos de Teste
Utilizados
O modelo SAN da figura 25 apresenta a descri¸c˜ao gr´afica do modelo de teste denomi-
nado SC. Baseado em um caso real, este modelo representa uma situa¸c˜ao onde 16 recursos
s˜ao disputados por 4 processos. Cada processo pode estar utilizando um recurso (estado
U) ou livre (estado L). De forma semelhante um recurso pode estar sendo utilizado por
um processo (estado U) ou estar livre (estado L).
Recurso
(1)
l
(1)
Recurso
(2)
l
(2)
Recurso
(3)
l
(3)
Recurso
(4)
l
(4)
r
(4)
r
(1)
r
(2)
r
(3)
r
(5)
Recurso
(5)
r
(6)
Recurso
(6)
l
(6)
r
(7)
Recurso
(7)
l
(7)
r
(8)
Recurso
(8)
l
(8)
r
(10)
Recurso
(10)
l
(10)
r
(11)
Recurso
(11)
l
(11)
r
(9)
Recurso
(9)
l
(9)
r
(12)
Recurso
(12)
l
(12)
r
[1..16]
P rocesso
(2)
P rocesso
(1)
r
[1..16]
r
(13)
Recurso
(13)
l
(13)
r
(14)
Recurso
(14)
l
(14)
r
(15)
Recurso
(15)
l
(15)
r
(16)
Recurso
(16)
l
(16)
r
[1..16]
P rocesso
(4)
r
[1..16]
P rocesso
(3)
U
L
L
U
U
L L
U
L
U
U
L
U
L
U
L
U
L
L
U
U
L
L
U
L
U
U
L
U
L
U
L
L
U
L
U
L
U
U
L
l
(5)
l
[1..16]
l
[1..16]
l
[1..16]
l
[1..16]
Figura 2 5: Modelo SAN do caso de teste SC.
66
Na figura 26, ´e apresentado o modelo SAN referente ao caso de teste Misto. Este
caso de t este explora diversos aspectos diferentes de transi¸c˜oes entre os estados, bem como
diversifica o n´umero de estados de cada autˆomato.
S
0
S
1
S
2
S
3
A
5
S
1
S
0
S
2
S
4
S
5
S
0
S
1
S
2
S
3
S
4
A
6
S
0
S
2
S
3
S
4
S
2
S
1
S
5
S
0
A
7
S
5
S
1
S
6
S
7
S
1
S
0
S
2
S
3
A
8
S
3
S
4
A
9
S
0
S
1
S
2
e
2
e
6
, π
2
e
3
l
2
e
6
, π
1
A
2
A
1
S
0
S
1
S
2
e
2
e
3
, l
1
e
6
l
4
S
1
A
3
S
2
S
0
S
3
e
1
e
2
e
1
e
1
e
2
e
1
e
1
e
2
e
2
e
2
S
3
S
4
A
4
e
1
e
5
e
2
e
5
e
5
e
2
e
2
e
2
e
2
e
2
e
2
e
4
e
4
e
4
e
4
e
2
e
1
e
2
, π
4
e
2
, π
1
e
2
, π
3
e
3
e
3
e
2
e
2
e
2
e
2
e
2
e
4
e
4
e
4
e
4
e
2
e
5
e
5
e
5
e
5
, π
2
e
5
, π
1
e
5
e
5
e
5
e
5
e
2
e
2
e
2
e
2
e
1
e
1
e
2
, π
2
e
2
, π
5
e
3
e
3
e
3
e
4
, l
3
Figura 26: Modelo SAN do caso de teste Misto.
67
Apˆendice C
Detalhamento dos Resul tados
Tabela 4: Shuffle - escalonamento sem considerar custos - teste Misto.
N´umero de Tempo de Execu¸c˜ao Speedup Eficiˆencia
Processadores M´edia Desvio Padr˜ao
1 52,432280 0,006782 - - %
2
26,647920 0,016673 1,967593 98,00 %
3
19,970660 0,015362 2,625465 87,00 %
4
13,965560 0,028442 3,754398 93,00 %
5
13,638080 0,028548 3,844549 76,00 %
6
10,776360 0,056347 4,865490 81,00 %
7 10,507700 0,026210 4,989891 71,00 %
8
7,249580 0,058000 7,232457 90,00 %
9
7,476920 0,041557 7,012550 77,00 %
10 7,651952 0,060324 6,852144 68,00 %
11
7,632818 0,030740 6,869321 62,00 %
12
7,632166 0,046411 6,869908 57,00 %
13
7,592220 0,099854 6,906053 53,00 %
14
7,566224 0,062457 6,929781 49,00 %
15
7,395264 0,027910 7,089980 47,00 %
16
4,099242 0,049699 12,79 0725 79,00 %
68
Tabela 5: Shuffle - escalonamento sem considerar custos - teste SC.
N´umero de Tempo de Execu¸c˜ao Speedup Eficiˆencia
Processadores M´edia Desvio Pa dr˜ao
1 477,77700 0 0,288315 - - %
2
242,94240 0 0,226192 1,966626 98,00 %
3
164,50620 0 0,201737 2,904309 96,00 %
4
121,99620 0 0,065505 3,916326 97,00 %
5
99,167940 0,035199 4,817857 96,00 %
6
84,036420 0,049507 5,685356 94,00 %
7
74,916560 0,096041 6,377455 91,00 %
8
61,135760 0,076391 7,815016 97,00 %
9
60,181460 0,048000 7,938939 88,00 %
10
53,943100 0,096659 8,857054 88,00 %
11
46,088540 0,025416 10,366503 94,00 %
12
46,077380 0,052839 10,369014 86,00 %
13
38,709540 0,072580 12,342616 94,00 %
14
38,720240 0,042083 12,339205 88,00 %
15
38,672260 0,029478 12,354514 82,00 %
16
30,894900 0,053131 15,464591 96,00 %
17
31,011020 0,054506 15,406684 90,00 %
18
31,019880 0,049608 15,402283 85,00 %
19
31,002920 0,096524 15,410709 81,00 %
20
30,984240 0,059598 15,420000 77,00 %
21
30,497700 0,094254 15,666001 74,00 %
22
23,662160 0,057480 20,191605 91,00 %
23
23,664500 0,016386 20,189608 87,00 %
24
23,634980 0,029563 20,214825 84,00 %
25
23,658360 0,021236 20,194848 80,00 %
26
23,641040 0,029376 20,209643 77,00 %
27
23,634900 0,074060 20,214894 74,00 %
28
23,637060 0,067542 20,213046 72,00 %
29
23,621680 0,042166 20,226207 69,00 %
30
23,644940 0,014647 20,206310 67,00 %
31
23,597060 0,037322 20,247310 65,00 %
32
15,831000 0,054332 30,179837 94,00 %
69
Tabela 6: Shuffle - escalonamento sem considerar custos - teste Denso A.
N´umero de Tempo de Execu¸c˜ao Speedup Eficiˆencia
Processadores M´edia Desvio Padr˜ao
1 58,276200 0,094138 - - %
2 29,225900 0,049152 1,993991 99,00 %
3
22,057380 0,037456 2,642027 88,00 %
4
14,892500 0,026962 3,913124 97,00 %
5
14,907260 0,047812 3,909249 78,00 %
6
11,285020 0,038910 5,164031 86,00 %
7
11,294160 0,044944 5,159852 73,00 %
8
7,684970 0,020780 7,583139 94,00 %
9
7,768198 0,012569 7,501894 83,00 %
10
7,776966 0,038013 7,493436 74,00 %
11
7,779560 0,078179 7,490937 68,00 %
12
7,748988 0,069368 7,520491 62,00 %
13
7,744112 0,029732 7,525226 57,00 %
14
7,734744 0,041303 7,534341 53,00 %
15
7,737362 0,048000 7,531791 50,00 %
16
4,154754 0,053282 14,02 6390 87,00 %
70
Tabela 7: Shuffle - escalonamento sem considerar custos - teste Denso B.
N´umero de Tempo de Execu¸c˜ao Speedup Eficiˆencia
Processadores M´edia Desvio Padr˜ao
1 64,450880 0,067394 - - %
2 32,379200 0,054147 1,990502 99,00 %
3
24,397160 0,021071 2,641736 88,00 %
4
16,470320 0,031352 3,913152 97,00 %
5
16,464200 0,042449 3,914607 78,00 %
6
12,469040 0,088277 5,168872 86,00 %
7
12,458760 0,013490 5,173137 73,00 %
8
8,454172 0,029949 7,623559 95,00 %
9
8,569142 0,063261 7,521275 83,00 %
10
8,559234 0,061497 7,529982 75,00 %
11
8,556078 0,025748 7,532759 68,00 %
12
8,536032 0,049919 7,550449 62,00 %
13
8,540486 0,068614 7,546511 58,00 %
14
8,534100 0,037456 7,552158 53,00 %
15
8,518720 0,042883 7,565793 50,00 %
16
4,524182 0,031890 14,24 5863 89,00 %
71
Tabela 8: Shuffle - escalonamento considerando custos - teste SC.
N´umero de Tempo de Execu¸c˜ao Speedup Eficiˆencia
Processadores M´edia Desvio Pa dr˜ao
1 477,77700 0 0,028315 - - %
2
238,73880 0 0,025204 2,001254 100,00 %
3
163,60560 0 0,070434 2,920297 97,00 %
4
119,54240 0 0,087487 3,996715 99,00 %
5
97,413100 0,018366 4,904648 98,00 %
6
82,103680 0,086792 5,819191 96,00 %
7
74,464140 0,010955 6,416202 91,00 %
8
60,042180 0,045243 7,957355 99,00 %
9
59,662300 0,015805 8,008021 88,00 %
10
52,434420 0,038072 9,111896 91,00 %
11
45,260960 0,095163 10,556050 95,00 %
12
44,690220 0,065169 10,690862 89,00 %
13
37,987740 0,093861 12,577136 96,00 %
14
37,564220 0,045464 12,718938 90,00 %
15
37,543680 0,087738 12,725896 84,00 %
16
30,338340 0,043600 15,748290 98,00 %
17
30,463280 0,063937 15,683701 92,00 %
18
30,411100 0,038039 15,710612 87,00 %
19
30,406080 0,102117 15,713206 82,00 %
20
29,952320 0,035341 15,951251 79,00 %
21
29,970260 0,018401 15,941703 75,00 %
22
23,208200 0,025670 20,586559 93,00 %
23
23,175560 0,068876 20,615553 89,00 %
24
22,751800 0,045044 20,999525 87,00 %
25
22,750480 0,050685 21,000743 84,00 %
26
22,792820 0,088107 20,961732 80,00 %
27
22,759080 0,042743 20,992808 77,00 %
28
22,748360 0,049030 21,002700 75,00 %
29
22,755220 0,095587 20,996369 72,00 %
30
22,743360 0,032186 21,007318 70,00 %
31
22,716620 0,060695 21,032046 67,00 %
32
15,543940 0,058369 30,737187 96,00 %
72
Tabela 9: Shuffle - escalonamento considerando custos - teste Misto.
N´umero de Tempo de Execu¸c˜ao Speedup Eficiˆencia
Processadores M´edia Desvio Padr˜ao
1 52,432280 0,060782 - - %
2 26,904400 0,017029 1,948836 97,00 %
3
19,841840 0,024413 2,642510 88,00 %
4
16,606380 0,029308 3,157357 78,00 %
5
12,288420 0,004242 4,266804 85,00 %
6
10,556380 0,033436 4,966880 82,00 %
7
9,854974 0,003605 5,320387 76,00 %
8
9,812808 0,013114 5,343249 66,00 %
9
7,512562 0,046335 6,979280 77,00 %
10
7,438968 0,053944 7,048327 70,00 %
11
7,209346 0,041279 7,272820 66,00 %
12
7,205354 0,030594 7,276849 60,00 %
13
7,120532 0,030265 7,363534 56,00 %
14
6,846824 0,035057 7,657898 54,00 %
15
6,784160 0,014317 7,728632 51,00 %
16
4,028760 0,024083 13,01 4495 81,00 %
73
Tabela 10: Shuffle - escalonamento considerando custos - teste Denso A.
N´umero de Tempo de Execu¸c˜ao Speedup Eficiˆencia
Processadores M´edia Desvio Padr˜ao
1 58,276200 0,094138 - - %
2 28,672600 0,099317 2,032470 100,00 %
3
21,616240 0,013038 2,695945 89,00 %
4
14,614560 0,050338 3,987543 99,00 %
5
14,604640 0,042602 3,990252 79,00 %
6
11,071720 0,060415 5,263518 87,00 %
7
11,049360 0,021540 5,274169 75,00 %
8
7,511606 0,005099 7,758154 96,00 %
9
7,625970 0,033689 7,641808 84,00 %
10
7,649860 0,087766 7,617943 76,00 %
11
7,616278 0,024166 7,651532 69,00 %
12
7,611996 0,046508 7,655836 63,00 %
13
7,615510 0,055416 7,652304 58,00 %
14
7,592870 0,041315 7,675121 54,00 %
15
7,600610 0,038716 7,667305 51,00 %
16
4,072288 0,040595 14,31 0431 89,00 %
74
Tabela 11: Shuffle - escalonamento considerando custos - teste Denso B.
N´umero de Tempo de Execu¸c˜ao Speedup Eficiˆencia
Processadores M´edia Desvio Padr˜ao
1 64,450880 0,067394 - - %
2 32,379200 0,054147 1,990502 99,00 %
3
24,397160 0,021071 2,641736 88,00 %
4
16,470320 0,031352 3,913152 97,00 %
5
16,464200 0,042449 3,914607 78,00 %
6
12,469040 0,088277 5,168872 86,00 %
7
12,458760 0,013490 5,173137 73,00 %
8
8,454172 0,029949 7,623559 95,00 %
9
8,569142 0,063261 7,521275 83,00 %
10
8,559234 0,061497 7,529982 75,00 %
11
8,556078 0,025748 7,532759 68,00 %
12
8,536032 0,049919 7,550449 62,00 %
13
8,540486 0,068614 7,546511 58,00 %
14
8,534100 0,037456 7,552158 53,00 %
15
8,518720 0,042883 7,565793 50,00 %
16
4,524182 0,031890 14,24 5863 89,00 %
75
Tabela 12: Slice - escalonamento por termo - teste SC.
N´umero de Tempo de Execu¸c˜ao Speedup Eficiˆencia
Processadores M´edia Desvio Padr˜ao
1 13,688620 0,052211 - - %
2
8,894016 0,067216 1,539082 76,00 %
3
6,176964 0,076980 2,216075 73,00 %
4 5,992858 0,088187 2,284155 57,00 %
5
4,327158 0,036124 3,163420 63,00 %
6 3,862116 0,085644 3,544331 59,00 %
7
4,064464 0,079799 3,367878 48,00 %
8
4,199792 0,086879 3,259356 40,00 %
9 3,878644 0,069627 3,529228 39,00 %
10
2,980424 0,070171 4,592843 45,00 %
11
3,629782 0,042544 3,771196 34,00 %
12
3,649434 0,011532 3,750888 31,00 %
13
3,558264 0,035298 3,846993 29,00 %
14
3,340428 0,047528 4,097864 29,00 %
15
2,424022 0,052915 5,647069 37,00 %
16
3,371016 0,042684 4,060680 25,00 %
17
3,190004 0,031984 4,291098 25,00 %
18
3,243402 0,063458 4,220451 23,00 %
19
3,190162 0,011180 4,290885 22,00 %
20
3,248610 0,018248 4,213685 21,00 %
21
3,105942 0,030413 4,407236 20,00 %
22
3,296434 0,012328 4,152553 18,00 %
23
3,255902 0,073545 4,204248 18,00 %
24
3,243776 0,045738 4,219964 17,00 %
25 3,192346 0,062825 4,287949 17,00 %
26
3,150564 0,022045 4,344815 16,00 %
27
3,122566 0,068738 4,383772 16,00 %
28
2,949378 0,024103 4,641188 16,00 %
29
2,864984 0,037643 4,777904 16,00 %
30 2,115834 0,016852 6,469609 21,00 %
31
2,030804 0,038249 6,740492 21,00 %
32 2,998770 0,054534 4,564744 14,00 %
76
Tabela 13: Slice - escalonamento por termo - teste Misto.
N´umero de Tempo de Execu¸c˜ao Speedup Eficiˆencia
Processadores M´edia D esvio Padr˜ao
1 5,953364 0,001414 - - %
2
3,897752 0,01 5132 1,527383 76,00 %
3 3,023084 0,026608 1,969301 65,00 %
4
3,154838 0,02 5357 1,887058 47,00 %
5
3,070490 0,04 5967 1,938897 38,00 %
6 2,429842 0,046249 2,450103 40,00 %
7
2,010514 0,02 8106 2,961115 42,00 %
8 2,215460 0,079195 2,687190 33,00 %
9
2,420620 0,04 9325 2,459437 27,00 %
10 3,731030 0,02 4617 1,595635 15,00 %
11 3,757254 0,03 8678 1,584498 14,00 %
12
2,716148 0,04 0124 2,191840 18,00 %
13 2,154746 0,08 6873 2,762907 21,00 %
14 2,319506 0,07 1819 2,566651 18,00 %
15
1,881302 0,01 1789 3,164491 21,00 %
16 1,971398 0,08 0709 3,019869 18,00 %
77
Tabela 14: Slice - escalonamento por termo - teste Denso A.
N´umero de Tempo de Execu¸c˜ao Speed up Eficiˆencia
Processadores M´edia Desvio Padr˜ao
1 13,014060 0,019974 - - %
2
8,086612 0,064676 1,609334 80,00 %
3
6,241818 0,048754 2,084979 69,00 %
4
4,418798 0,122584 2,945158 73,00 %
5
4,430600 0,052943 2,937313 58,00 %
6
3,503386 0,038613 3,714709 61,00 %
7
3,552140 0,085796 3,663723 52,00 %
8
2,573908 0,094836 5,056148 63,00 %
9
2,676764 0,036674 4,861863 54,00 %
10
2,619364 0,023769 4,968404 49,00 %
11
2,625688 0,036537 4,956438 45,00 %
12
2,619202 0,046141 4,968711 41,00 %
13
2,592868 0,066279 5,019175 38,00 %
14
2,603626 0,049040 4,998436 35,00 %
15
2,573324 0,057697 5,057295 33,00 %
16
1,668218 0,052076 7,801174 48,00 %
78
Tabela 15: Slice - escalonamento por termo - teste Denso B.
N´umero de Tempo de Execu¸c˜ao Speedup Eficiˆencia
Processadores M´edia Desvio Padr˜ao
1 80,211800 0 ,0 914400 - - %
2
41,638520 0 ,0 924639 1,926384 96,00 %
3
30,411480 0 ,0 752480 2,637550 87,00 %
4
20,503440 0 ,0 371160 3,912114 97,00 %
5
20,491720 0 ,0 393700 3,914351 78,00 %
6
15,658280 0 ,0 865740 5,122644 85,00 %
7
15,567400 0 ,0 112200 5,152549 73,00 %
8
10,588460 0 ,0 384160 7,575398 94,00 %
9
10,652080 0 ,0 958270 7,530153 83,00 %
10
10,643200 0 ,0 499090 7,536436 75,00 %
11
10,621360 0 ,0 375890 7,551933 68,00 %
12
10,622940 0 ,0 477280 7,550809 62,00 %
13
10,662780 0 ,0 383600 7,522597 57,00 %
14
10,639660 0 ,0 603980 7,538943 53,00 %
15
10,641680 0 ,0 329620 7,537512 50,00 %
16
5,664326 0,096 4880 14,160872 88,00 %
79
Tabela 16: Slice - escalonamento por AUNF - teste SC.
N´umero de Tempo de Execu¸c˜ao Speedup Eficiˆencia
Processadores M´edia Desvio Padr˜ao
1 13,688620 0,052211 - - %
2
7,230356 0,006164 1,893215 94,00 %
3
5,040522 0,029732 2,715714 90,00 %
4
3,937008 0,040743 3,476909 86,00 %
5
3,267300 0,055848 4,189581 83,00 %
6
2,831166 0,046335 4,834976 80,00 %
7
2,541796 0,048383 5,385412 76,00 %
8
2,258990 0,066324 6,059619 75,00 %
9
2,203872 0,052810 6,211168 69,00 %
10
2,048420 0,053366 6,682526 66,00 %
11
1,971498 0,089788 6,943258 63,00 %
12
1,811098 0,013416 7,558188 62,00 %
13
1,682134 0,042284 8,137651 62,00 %
14
1,615564 0,027802 8,472966 60,00 %
15 1,552416 0,064342 8,817623 58,00 %
16
1,553196 0,070781 8,813195 55,00 %
17
1,574482 0,053469 8,694046 51,00 %
18 1,591332 0,016639 8,601988 47,00 %
19
1,565582 0,012020 8,743470 46,00 %
20
1,460170 0,027712 9,374675 46,00 %
21 1,441544 0,054662 9,495804 45,00 %
22
1,420794 0,010000 9,634486 43,00 %
23
1,365770 0,017088 10,02 2639 43,00 %
24
1,366814 0,016309 10,01 4983 41,00 %
25
1,372324 0,014847 9,974772 39,00 %
26
1,358112 0,018867 10,07 9154 38,00 %
27
1,302340 0,010992 10,51 0788 38,00 %
28
1,241488 0,011489 11,02 5978 39,00 %
29
1,239436 0,078185 11,04 4233 38,00 %
30
1,260680 0,066385 10,85 8124 36,00 %
31
1,199684 0,078032 11,41 0188 36,00 %
32
1,205244 0,086151 11,35 7550 35,00 %
80
Tabela 17: Slice - escalonamento por AUNF - teste Misto.
N´umero de Tempo de Execu¸c˜ao Speedup Eficiˆencia
Processadores M´edia D esvio Padr˜ao
1 5,953364 0,001414 - - %
2
3,237224 0,02 6362 1,839033 91,00 %
3
2,497186 0,04 6946 2,384029 79,00 %
4
2,078450 0,03 9268 2,864328 71,00 %
5 1,809018 0,054516 3,290936 65,00 %
6
1,588262 0,05 9455 3,748351 62,00 %
7
1,467162 0,03 3211 4,057741 57,00 %
8 1,354258 0,026172 4,396033 54,00 %
9 1,374858 0,051971 4,330166 48,00 %
10
1,307164 0,05 1932 4,554412 45,00 %
11 1,224246 0,07 3341 4,862882 44,00 %
12
1,189710 0,03 6986 5,004046 41,00 %
13 1,167276 0,03 5397 5,100219 39,00 %
14 1,113842 0,03 3660 5,344890 38,00 %
15
1,086278 0,02 0784 5,480516 36,00 %
16 1,072648 0,01 4491 5,550156 34,00 %
17 1,153292 0,02 5729 5,162061 30,00 %
18
1,123958 0,04 2520 5,296785 29,00 %
19 1,124946 0,04 2755 5,292133 27,00 %
20
1,076650 0,02 6870 5,529525 27,00 %
21
1,063270 0,05 4827 5,599108 26,00 %
22 1,067802 0,04 2284 5,575344 25,00 %
23
1,055414 0,03 2046 5,640785 24,00 %
24
1,026576 0,01 0677 5,799243 24,00 %
25
1,030986 0,02 4433 5,774437 23,00 %
26 1,035368 0,05 4671 5,749998 22,00 %
27
1,000854 0,01 1747 5,948284 22,00 %
28
,991356 0,012727 6,005273 21,00 %
29 ,989672 0,030870 6,015492 20,00 %
30
,986363 0,042367 6,035672 20,00 %
31
,974733 0,048528 6,107686 19,00 %
32 ,963382 0,032202 6,179650 19,00 %
81
Tabela 18: Slice - escalonamento por AUNF - teste Denso A.
N´umero de Tempo de Execu¸c˜ao Speedup Eficiˆencia
Processadores M´edia Desvio Padr˜ao
1 13,014060 0,019974 - - %
2
6,714582 0,005656 1,938178 96,00 %
3
4,742060 0,014120 2,744389 91,00 %
4
3,724884 0,073952 3,493816 87,00 %
5
3,073160 0,058438 4,234748 84,00 %
6
2,667406 0,038118 4,878919 81,00 %
7
2,360068 0,031921 5,514273 78,00 %
8
2,160596 0,013101 6,023365 75,00 %
9
2,053854 0,059084 6,336409 70,00 %
10
1,976526 0,039818 6,584310 65,00 %
11
1,864110 0,093861 6,981379 63,00 %
12
1,790886 0,021367 7,266827 60,00 %
13
1,685814 0,070220 7,719748 59,00 %
14
1,627366 0,067786 7,997008 57,00 %
15 1,514380 0,097805 8,593655 57,00 %
16
1,521684 0,057332 8,552406 53,00 %
17
1,612196 0,044436 8,072256 47,00 %
18 1,593610 0,082669 8,166402 45,00 %
19
1,465108 0,012512 8,882662 46,00 %
20
1,473656 0,072855 8,831138 44,00 %
21 1,380690 0,024418 9,425765 44,00 %
22
1,394504 0,067069 9,332393 42,00 %
23
1,321062 0,036762 9,851210 42,00 %
24
1,280812 0,067734 10,16 0788 42,00 %
25
1,303096 0,059749 9,987030 39,00 %
26
1,272532 0,040385 10,22 6901 39,00 %
27
1,284482 0,010970 10,13 1757 37,00 %
28
1,250974 0,076830 10,40 3141 37,00 %
29
1,281332 0,049959 10,15 6665 35,00 %
30
1,241858 0,089367 10,47 9507 34,00 %
31
1,257948 0,084190 10,34 5467 33,00 %
32
1,277820 0,040516 10,18 4579 31,00 %
82
Tabela 19: Slice - escalonamento por AUNF - teste Denso B.
N´umero de Tempo de Execu¸c˜ao Speedup Eficiˆencia
Processadores M´edia Desvio Padr˜ao
1 80,211800 0 ,0 914400 - - %
2
34,964300 0,030185 2,2941 05 114,0 0 %
3
23,084420 0,099854 3,4747 15 115,0 0 %
4
17,412180 0,028220 4,6066 48 115,0 0 %
5
14,253360 0,031137 5,6275 71 112,0 0 %
6
11,903380 0,049103 6,7385 73 112,0 0 %
7
10,307940 0,031018 7,7815 54 111,0 0 %
8
9,336952 0,0 73866 8,590790 107,00 %
9
8,195608 0,0 37783 9,787168 108,00 %
10
7,424568 0,0 30153 10,803564 108,00 %
11
6,881746 0,0 30313 11,655733 105,00 %
12
6,252424 0,0 79466 12,828912 106,00 %
13
5,990370 0,0 53782 13,390124 103,00 %
14
5,909862 0,0 62863 13,572533 96,00 %
15
5,461962 0,0 51222 14,685528 97,00 %
16
5,309690 0,0 73413 15,106682 94,00 %
17
4,964894 0,0 20465 16,155793 95,00 %
18
4,639856 0,0 31063 17,287562 96,00 %
19
4,369046 0,0 32417 18,359110 96,00 %
20
4,272940 0,0 32095 18,772039 93,00 %
21
4,180504 0,0 61879 19,187112 91,00 %
22
4,177090 0,0 85882 19,202794 87,00 %
23
3,829066 0,0 30170 20,948137 91,00 %
24
3,809730 0,0 50741 21,054457 87,00 %
25
3,873178 0,0 62584 20,709556 82,00 %
26
3,774622 0,0 62709 21,250286 81,00 %
27
3,499926 0,0 43922 22,918141 84,00 %
28
3,358450 0,0 66261 23,883577 85,00 %
29
3,340434 0,0 62299 24,012388 82,00 %
30
3,205754 0,0 24458 25,021196 83,00 %
31
3,054564 0,0 45728 26,259656 84,00 %
32
2,941724 0,012 1872 27,266935 85,00 %
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
