( PDF ) Estratégias de paralelização para renderização de documentos XSL-FO com uso da ferramenta FOP

Download PDF

ads:

Pontif´ıcia Universidade Cat´olica do Rio Grande do Sul

Faculdade de Inform´atica

P´os-Gradua¸c˜ao em Ciˆencia da Computa¸c˜ao

Estrat

egias de Paraleliza¸c

ao para

Renderiza¸c

ao de Documentos XSL-FO

com Uso da Ferramenta FOP

Rogerio Timmers Zambon

Disserta¸c˜ao apresentada como requi-

sito parcial `a obten¸c˜ao do grau de mes-

tre em Ciˆencia da Computa¸c˜ao.

Orientador: Prof. Dr. Luiz Gustavo Fernan-

des

Porto Alegre, outubro de 2006.

ads:

Livros Grátis

http://www.livrosgratis.com.br

Milhares de livros grátis para download.

Campus Central

Av. Ipiranga, 6681 – prédio 16 – CEP 90619-900

Porto Alegre – RS – Brasil

Fone: +55 (51) 3320-3544 – Fax: +55 (51) 3320-3548

Email: [email protected]

www.pucrs.br/biblioteca

Pontifícia Universidade Católica do Rio

Grande do Sul

Dados Internacionais de Catalogação na Publicação (CIP)

Z24e Zambon, Rogério Timmers

Estratégias de paralelização para renderização de documentos

XSL-FO com uso da ferramenta FOP / Rogério Timmers Zambon. –

Porto Alegre, 2006.

91 f.

Diss. (Mestrado) – Fac. de Informática, PUCRS

Orientador: Prof. Dr. Luiz Gustavo Fernandes

1. Linguagens de Marcação de Documento. 2. Processamento de

Alto Desempenho. 3. Modelagem de Dados. 4. Informática. I.

Título.

CDD 004.3

005.72

Ficha Catalográfica elaborada pelo

Setor de Processamento Técnico da BC-PUCRS

ads:

Agradecimentos

Agrade¸co ao professor Luiz Gustavo Fernandes, pela amizade em primeiro lugar e por acre-

ditar no projeto ao aceitar ser meu orientador.

Ao professor Paulo Fernandes, meu orientador no primeiro ano de mestrado pela conﬁan¸ca

e ajuda.

Aos colegas do CAP Pedro, Lucas, M´arcio, Mateus, Gustavo e Thiago pela grande ajuda em

tudo.

Ao professor De Rose por participar em todas as avalia¸c˜oes do trabalho sempre com dicas

para melhorar o andamento do trabalho.

A todos na HP, que me incentivaram a participar e concluir o curso principalmente quanto

`a ﬂexibilidade de hor´arios.

Ao meu colega de mestrado Ricardo Presotto pelo companheirismo e amizade.

Ao colega Fabio Giannetti da HP Bristol, pela grande amizade e companheirismo. Tamb´em

por revisar grande parte dos documentos entregues durante o curso e por auxiliar com o grande

conhecimento na ´area de publica¸c˜oes digitais.

”Preserve o que ´e bom. Reinvente o resto.”

Carly Fiorina

viii

Resumo

Grandes volumes de trabalho para impress˜ao s˜ao cada vez mais comuns devido ao aumento

da demanda por documentos personalizados. Neste contexto, Impress˜ao de Dados Vari´aveis

(Variable Data Printing - VDP) tornou-se uma ferramenta muito ´util para proﬁssionais de

marketing que necessitam personalizar mensagens para cada cliente em materiais promocionais

e campanhas de publicidade. VDP permite a cria¸c˜ao de documentos baseados em um modelo

(template) contendo partes est´aticas e vari´aveis. A ferramenta de renderiza¸c˜ao deve ser capaz de

transformar a parte vari´avel em um formato composto, ou PDL (Page Description Language) tais

como PDF (Portable Document Format), PS (PostScript) ou SVG (Scalable Vector Graphics). A

quantidade de conte´udo vari´avel em um documento ´e totalmente dependente do modelo (layout)

da publica¸c˜ao deﬁnido por um proﬁssional da ´area. Al´em disso, o conte´udo vari´avel a ser

renderizado p ode variar de acordo com os dados lidos do banco de dados. Desta forma, este

processo ´e chamado repetidamente e pode tornar-se facilmente um gargalo, esp ecialmente em

um ambiente de produ¸c˜ao comprometendo inteiramente a gera¸c˜ao de um documento. Neste

cen´ario, t´ecnicas de alto desempenho aparecem como uma interessante alternativa para aumentar

o rendimento da fase de renderiza¸c˜ao. Este trabalho introduz uma solu¸c˜ao paralela port´avel e

escal´avel para a ferramenta de renderiza¸c˜ao chamada FOP (Formatting Objects Processor), a

qual ´e usada para renderizar o conte´udo vari´avel expresso em linguagem XSL-FO (eXtensible

Stylesheet Language-Formatting Obects).

Abstract

High volume print jobs are getting more common due to the growing demand for personalized

documents. In this context, VDP (Variable Data Printing) has become a useful tool for mar-

keters who need to customize messages for each customer in promotion materials or marketing

campaigns. VDP allows the creation of documents based on a template with variable and static

portions. The rendering engine must be capable of transforming the variable portion into a

resulting composed format, or PDL (Page Description Language) such as PDF (Portable Do-

cument Format), PS (PostScript) or SVG (Scalable Vector Graphics). The amount of variable

content in a document is dependant on the publication layout. In addition, the features and the

amount of the content to be rendered may vary according to the data loaded from the database.

Therefore, the rendering process is invoked repeatedly and it can quickly become a bottleneck,

especially in a production environment, compromising the entire document generation. In this

scenario, high performance techniques appear to be an interesting alternative to increase the

rendering phase throughput. This paper introduces a portable and scalable parallel solution

for the Apache’s rendering tool FOP (Formatting Objects Processor) which is used to render

variable content expressed in XSL-FO (eXtensible Stylesheet Language-Formatting Objects).

xii

Sum´ario

RESUMO ix

ABSTRACT xi

LISTA DE TABELAS xvii

LISTA DE FIGURAS xix

LISTA DE S

IMBOLOS E ABREVIATURAS xxi

Cap´ıtulo 1: Introdu¸c˜ao 23

1.1 Motiva¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

1.2 Estrutura do Volume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

Cap´ıtulo 2: Engenharia de Documentos 27

2.1 Deﬁni¸c˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.1.1 An´alise de Documentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.1.2 Modelagem de Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.1.3 Uniﬁcando An´alise de Documentos e Modelagem de Dados . . . . . . . . 28

2.2 PPML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2.3 XSL-FO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.4 FOP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

Cap´ıtulo 3: Processamento de Alto Desempenho 37

3.1 Modelos de Arquiteturas de Processamento Paralelo . . . . . . . . . . . . . . . . 37

xiv SUM

ARIO

3.1.1 Classiﬁca¸c˜ao de Flynn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.1.2 Classiﬁca¸c˜ao de Duncan . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

3.2 Compartilhamento de Mem´oria . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

3.2.1 Multiprocessadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

3.2.2 Multicomputadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

3.3 Modelos de Programa¸c˜ao Paralela . . . . . . . . . . . . . . . . . . . . . . . . . . 49

3.3.1 Paralelismo Impl´ıcito e Expl´ıcito . . . . . . . . . . . . . . . . . . . . . . . 49

3.3.2 Paralelismo de Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

3.3.3 Paralelismo de Controle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

3.3.4 Troca de Mensagens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

3.4 Modelos de Algoritmos Paralelos . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

3.4.1 Divis˜ao e Conquista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

3.4.2 Pipeline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

3.4.3 Mestre/Escravo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

3.4.4 Pool de Trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

3.4.5 Fases Paralelas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

3.5 Crit´erios de Avalia¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

3.6 Fatores de Desempenho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

3.6.1 Granularidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

3.6.2 Portabilidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

3.6.3 Escalabilidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

Cap´ıtulo 4: Deﬁni¸c˜oes Gerais 55

4.1 An´alise do Problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4.1.1 Arquitetura Atual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

4.2 Posicionamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

4.3 Plataformas de Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

4.3.1 Amazˆonia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

4.3.2 Ombr´oﬁla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

4.4 Casos de Estudo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

SUM

ARIO xv

Cap´ıtulo 5: Estrat´egias de Alto Desempenho 65

5.1 Estrat´egia Inicial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

5.1.1 Implementa¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

5.1.2 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

5.2 M´ultiplos Brokers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

5.2.1 Implementa¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

5.2.2 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

5.3 Divis˜ao do Consumidor PPML . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

5.3.1 Implementa¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

5.3.2 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

5.4 An´alise Complementar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

5.4.1 Entrada/Sa´ıda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

5.4.2 Buﬀers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

Cap´ıtulo 6: Considera¸c˜oes Finais 83

6.1 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

REFER

ENCIAS BIBLIOGR

AFICAS 87

xvi SUM

ARIO

Lista de Tabelas

4.1 Tamanho dos arquivos PPML utilizado nos testes . . . . . . . . . . . . . . . . . 64

5.1 Tabela de eﬁciˆencia e tempo de execu¸c˜ao por processador . . . . . . . . . . . . . 70

5.2 Tabela comparando a execu¸c˜ao com diferentes conﬁgura¸c˜oes (brokers e m´odulos

FOP ) e 1 broker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

5.3 Tabela comparando o tempo de I/O entre as vers˜oes seq

uencial e paralela da

ferramenta FOP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

5.4 Comparativo de tempo e eﬁciˆencia de renderiza¸c˜ao Mini 1000 documentos com e

sem tempo de I/O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

5.5 Comparativo de tempo e eﬁciˆencia de renderiza¸c˜ao CAP 2000 documentos com e

sem tempo de I/O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

5.6 Comparativo de tempo e eﬁciˆencia de renderiza¸c˜ao Appl 1000 documentos com e

sem tempo de I/O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

xviii LISTA DE TABELAS

Lista de Figuras

2.1 Exemplo de renderiza¸c˜ao de um XSL-FO para um formato de sa´ıda . . . . . . . 31

2.2 Estrutura hier´arquica em um documento PPML . . . . . . . . . . . . . . . . . . 32

2.3 Exemplo de um copy-hole contendo conte´udo renderiz´avel XSL-FO . . . . . . . 33

2.4 Processo de renderiza¸c˜ao de XSL-FO para SVG . . . . . . . . . . . . . . . . . . 34

2.5 Fases do processo de renderiza¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.1 Taxonomia de arquiteturas (Flynn) . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.2 Modelo computacional SISD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.3 Modelo computacional SIMD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.4 Modelo computacional MISD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.5 Modelo computacional MIMD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

3.6 Classiﬁca¸c˜ao de Duncan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3.7 Arquitetura com mem´oria compartilhada . . . . . . . . . . . . . . . . . . . . . . 45

3.8 Arquitetura com mem´oria distribu´ıda . . . . . . . . . . . . . . . . . . . . . . . . 45

3.9 Multiprocessadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

3.10 Classiﬁca¸c˜ao UMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

3.11 Classiﬁca¸c˜ao NUMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

3.12 Classiﬁca¸c˜ao COMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

3.13 Multicomputadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

3.14 Exemplo de paralelismo de controle . . . . . . . . . . . . . . . . . . . . . . . . . . 50

4.1 Processo de impress˜ao de documentos em impressoras digitais . . . . . . . . . . . 56

4.2 Renderiza¸c˜ao de um XSL-FO em um documento PPML . . . . . . . . . . . . . 56

4.3 Vers˜ao seq

uencial da ferramenta FOP . . . . . . . . . . . . . . . . . . . . . . . . 57

4.4 Amazˆonia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

xx LISTA DE FIGURAS

4.5 Ombr´oﬁla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

4.6 Exemplo de documento gerado pelo PPML Mini . . . . . . . . . . . . . . . . . . 62

4.7 Exemplo de documento gerado pelo PPML CAP . . . . . . . . . . . . . . . . . 63

4.8 Exemplo de documento gerado pelo PPML Appl . . . . . . . . . . . . . . . . . 64

5.1 Solu¸c˜ao inicial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

5.2 Resultados: seq

uencial e vers˜ao rodando em paralelo com at´e 6 processadores . . 68

5.3 Compara¸c˜ao entre o ganho de desempenho (speedup) ideal e o alcan¸cado pela

execu¸c˜ao da solu¸c˜ao de alto desempenho com at´e 16 processadores . . . . . . . . 69

5.4 Tempo de comunica¸c˜ao m´odulos FOP . . . . . . . . . . . . . . . . . . . . . . . . 71

5.5 M´odulos FOP n˜ao balanceados . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

5.6 M´ultiplos brokers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

5.7 Arquitetura da solu¸c˜ao de divis˜ao do consumidor PPML . . . . . . . . . . . . . 75

5.8 Resultados com arquivo de entrada Mini com 1000 documentos . . . . . . . . . . 76

5.9 Resultados com arquivo de entrada CAP com 2000 documentos . . . . . . . . . 77

5.10 Resultados com arquivo de entrada Appl com 1000 e 2000 documentos . . . . . 78

Lista de S´ımbolos e Abreviaturas

PS PostScript x

VDP Variable Data Printing x

XSL-FO eXtensible Stylesheet Language formatting objects 23

XML EXtensible Markup Language 28

PODi Print on Demand Initiative 30

PPML Personalized Print Markup Language 30

URL Universal Resource Identiﬁer 30

LAN Local Area Network 30

TIFF Tagged Image File Format 31

BMP Bit-Mapped Graphic 31

FO Formatting Objects 31

W3C World Wide Web Consortium 31

XSL-T eXtensible Stylesheet Language - Transformations 31

FOP Formatting Object Processor 31

PDL Page Description Language 34

PCL Printer Control Language 34

PDF Portable Document Format 34

SVG Scalable Vector Graphics 34

SISD Single Instruction Stream/Single Data 38

xxii LISTA DE S

IMBOLOS E ABREVIATURAS

SIMD Single Instruction Stream/Multiple Data Stream 39

MISD Multiple Instruction Stream/Single Data Stream 40

MIMD Multiple Instruction Stream/Multiple Data 40

PVP Parallel Vector Processor 41

SMP Symmetric Multiprocessing 41

MPP Massively Parallel Processing 41

DSM Distributed Shared Memory 41

NOW Network of Workstations 42

COW Clusters of Workstations 42

ATM Asynchronous Transfer Mode 42

NUMA Non-Uniform Memory Access 46

COMA Cache-Only Memory Architecture 46

UMA Uniform Memory Access 46

NORMA Non-Remote Memory Access 49

JVM Java Virtual Machine 58

J2SDK Java Standard Development Kit 58

RAM Random Access Memory 59

CPAD Centro de Pesquisa de Alto Desempenho 59

I/O Input/Output 79

CPU Central Processing Unit 80

SAC Symposium on Applied Computing 83

DOM Document Object Model 84

Cap´ıtulo 1

Introdu¸c˜ao

Cria¸c˜ao de documentos personalizados ´e uma pr´atica cada vez mais comum com a evolu¸c˜ao do

mundo digital. A montagem e transforma¸c˜ao autom´atica de documentos tornou-se um processo

necess´ario para atender a demanda. Tipicamente, documentos personalizados contˆem ´areas que

s˜ao comuns em um conjunto de do cumentos, e portanto conte´udo est´atico, assim como ´areas

personalizadas e vari´aveis. No m´etodo tradicional de informa¸c˜ao vari´avel [PHOF03], ferramentas

de documenta¸c˜ao permitem que os designers deﬁnam um modelo que servir´a de base para um

conjunto de documentos. Al´em disso, o designer tamb´em deﬁne ´areas vazias (tamanho ﬁxo),

nas quais o conte´udo vari´avel ser´a colocado. Assim, o layout comum ´e o mesmo para todos os

documentos e embora possa conter dados vari´aveis, n˜ao pode responder a propriedades dinˆamicas

como redimensionamento do tamanho dos dados vari´aveis.

Estas limita¸c˜oes tˆem disparado esfor¸cos em pesquisas para automatizar o processo de cria¸c˜ao

de documentos personalizados. Do cumentos podem ser escritos como modelos e a produ¸c˜ao pode

ser automatizada mantendo um alto n´ıvel de qualidade de cria¸c˜ao. Este ´e o foco desse trabalho,

explorar como a gera¸c˜ao de tais documentos ´e alcan¸cada em um ambiente de produ¸c˜ao. Casas

de impress˜ao (print shops) requerem um processo previs´ıvel, eﬁciente, e de qualidade industrial

para imprimir e ﬁnalizar documentos. Tem sido provado que o uso de XSL-FO em partes n˜ao

deﬁnidas do documento torna poss´ıvel a integra¸c˜ao dos dados vari´aveis tardiamente no processo,

at´e mesmo durante a pr´opria impress˜ao. Esta forma ´e claramente mais vantajosa visto que n˜ao

requer disponibilidade dos dados vari´aveis durante a fase de projeto (design) do documento.

Tamb´em permite a transmiss˜ao dos documentos e dados ainda como modelos, ao inv´es de um

documento completamente expandido.

24 CAP

ITULO 1. INTRODU ¸C

1.1 Motiva¸c˜ao

O objetivo dessa pesquisa ´e explorar e indicar uma solu¸c˜ao escal´avel e modular para executar

a composi¸c˜ao de dados vari´aveis usando ferramentas paralelas de renderiza¸c˜ao.

A maioria dos ambientes de produ¸c˜ao de publica¸c˜oes digitais usam impressoras digitais em

paralelo para maximizar o equil´ıbrio entre os processos, assim como toda a produ¸c˜ao de docu-

mentos (jobs). Em tal ambiente, todas as atividades relacionadas `a prepara¸c˜ao do documento

precisam ser executadas em um determinado espa¸co de tempo, j´a que as tarefas jobs s˜ao com-

pletados em uma ordem seq

uencial em m´ultiplas impressoras. No caso de impress˜ao de dados

vari´aveis, acima dos passos existentes de prepara¸c˜ao para impress˜ao, existe a necessidade de

integrar os dados vari´aveis no modelo e renderizar as partes n˜ao deﬁnidas ou est´aticas do docu-

mento.

O processo de renderiza¸c˜ao ´e usualmente muito extenso e no caso de milhares de documentos

pode tornar-se um gargalo. Impressoras digitais modernas tamb´em s˜ao capazes de imprimir na

mesma velo cidade de um renderizador (cerca de 1 p´agina por segundo). Esta taxa ´e o m´ınimo

requerido para manter a impressora digital trabalhando em velocidade m´axima. Quando as

impressoras digitais s˜ao usadas em paralelo, a velocidade do renderizador ´e multiplicada pelo

n´umero de impressoras, assim, torna-se muito dif´ıcil de alimentar a to das as impressoras na

velocidade necess´aria.

Quando o processo de renderiza¸c˜ao ´e centralizado em um ´unico pro cessador, uma quebra

provavelmente ir´a acontecer, uma vez que a velocidade das impressoras em paralelo excede a

velocidade do processo de renderiza¸c˜ao criando um gargalo. Similarmente ao conceito de usar

impressoras em paralelo a ﬁm de alcan¸car um melhor desempenho e mais rapidamente consumir

os jobs, nosso objetivo ´e desenvolver uma proposta para paralelizar a ferramenta de renderiza¸c˜ao

de documentos XSL-FO. Os resultados mostram que o sistema desenvolvido pode combinar com

a velocidade de impressoras rodando em paralelo. Tamb´em temos que considerar que ´e necess´ario

prover um n´umero adequado de processadores para atingir a velocidade ideal.

Os resultados deste trabalho mostram uma solu¸c˜ao modular e escal´avel para impress˜ao de

dados vari´aveis com renderiza¸c˜ao em tempo de impress˜ao.

1.2. ESTRUTURA DO VOLUME 25

1.2 Estrutura do Volume

Este trabalho foi dividido em 6 cap´ıtulos incluindo introdu¸c˜ao e conclus˜ao. Os quatro primei-

ros descrevem as bases te´oricas a esta disserta¸c˜ao. No Cap´ıtulo 2, ´e feita uma conceitua¸c˜ao de

engenharia de documentos apresentando alguns padr˜oes, linguagens e ferramentas utilizados na

´area de publica¸c˜oes digitais. No Cap´ıtulo 3, conceitos de processamento de alto desempenho s˜ao

brevemente citados tamb´em como embasamento para a disserta¸c˜ao. Uma an´alise do problema

em sua vers˜ao seq

uencial ´e descrito no Cap´ıtulo 4 assim como um posicionamento em rela¸c˜ao `as

bases te´oricas listadas. Al´em disso, neste Cap´ıtulo o ambiente utilizado para desenvolvimento

da solu¸c˜ao paralela e uma descri¸c˜ao dos documentos utilizados para a realiza¸c˜ao dos testes s˜ao

abordados.

Nos demais cap´ıtulos est˜ao as principais contribui¸c˜oes obtidas ao longo desta disserta¸c˜ao.

No Cap´ıtulo 5, apresenta-se as estrat´egias de paraleliza¸c˜ao da ferramenta FOP utilizadas at´e

atingir-se o modelo atual. Finalmente, na conclus˜ao s˜ao tecidas as considera¸c˜oes ﬁnais a respeito

do modelo proposto bem como os trabalhos futuros relacionados.

26 CAP

ITULO 1. INTRODU ¸C

Cap´ıtulo 2

Engenharia de Documentos

Engenharia de Documentos est´a desenvolvendo-se como uma nova disciplina para especiﬁ-

car, esbo¸car, e implementar documentos eletrˆonicos que fornecem interfaces para processos de

neg´ocios via servi¸cos baseados em Web [GM02].

No mundo dos neg´ocios, documentos sempre tiveram um papel fundamental como meio de

intera¸c˜ao entre o neg´ocio e as pessoas envolvidas.

A medida que as empresas crescentemente

movem suas atividades para a Internet e experimentam novas maneiras de como fazer neg´ocios,

podemos come¸car a tratar documentos como interfaces [RGM99].

Muitos tipos de documentos s˜ao essenciais para os neg´ocios. Alguns como cat´alogos, bro-

churas e folhetos ajudam os compradores a localizar e selecionar produtos e servi¸cos. Outros

como guias de usu´arios e manuais, s˜ao feitos para proverem um uso mais efetivo dos produtos e

servi¸cos ap´os a compra. Primeiramente, documentos na Web eram usados somente para docu-

mentos n˜ao-transacionais. Mais tarde, com o avan¸co das tecnologias documentos como pedidos,

faturas, passaram a ter grande importˆancia como tipos de documentos eletrˆonicos.

2.1 Deﬁni¸c˜oes

Documentos narrativos s˜ao tradicionalmente chamados de publica¸c˜oes e a t´ecnica de

an´alise e modelagem empregada ´e denominada an´alise de documentos. Como contraste,

documentos transacionais s˜ao otimizados para uso em neg´ocios e diferem substancialmente das

publica¸c˜oes orientadas a usu´arios. O m´etodo utilizado neste caso ´e nomeado modelagem de

dados.

A Engenharia de Do cumentos surge ent˜ao como uma mescla desses m´etodos sendo efetivo

28 CAP

ITULO 2. ENGENHARIA DE DOCUMENTOS

tanto para documentos narrativos como para transacionais. Documentos modelos podem

ser criados e reutilizados para diferentes tipos de neg´ocios, encorajando os criadores a balance´a-

los para neg´ocios internos e a necessidade de serem entendidos em outras ´areas.

2.1.1 An´alise de Documentos

An´alise de documentos ´e conduzida com o objetivo de abstrair um modelo l´ogico de uma

instˆancia existente de um tipo de documento ´unico codiﬁcando o modelo em um esquema XML

(EXtensible Markup Language). O m´etodo de an´alise de documentos permite aos usu´arios

executarem tarefas espec´ıﬁcas com novas instˆancias criadas a partir do documento. Por exemplo,

quando o tipo de documento ´e uma publica¸c˜ao, o novo esquema separa descri¸c˜ao da estrutura do

documento e o conte´udo da estrutura de apresenta¸c˜ao do mesmo. Isto inclui fontes, tamanhos

e atributos de formata¸c˜ao que s˜ao usados para representar ou ressaltar v´arios conte´udos. Assim

que essa separa¸c˜ao acontece, um ou mais estilos podem ser utilizados para formatar de maneira

consistente qualquer instˆancia v´alida do documento.

2.1.2 Modelagem de Dados

A Modelagem de dados ´e dedicado a entender e descrever uma estrutura l´ogica de objetos

de dados que tˆem v´arias propriedades e associa¸c˜oes umas com as outras. O objetivo t´ıpico

da modelagem de dados ´e deﬁnir uma ou mais categorias ou esquemas para organizar essas

propriedades e associa¸c˜oes eﬁcientemente para criar, revisar, apagar objetos de dados ou para

encontrar aqueles com caracter´ısticas espec´ıﬁcas.

An´alise de documentos e modelagem de dados compartilha o objetivo de criar uma descri¸c˜ao

formal de uma classe de instˆancias, por´em o m´etodo ´e melhor aplicado quando n˜ao h´a um n´umero

ilimitado de instˆancias idˆenticas.

2.1.3 Uniﬁcando An´alise de Documentos e Modelagem de Dados

An´alise de documentos e modelagem de dados s˜ao provenientes de diferentes disciplinas e

utilizam diferentes ferramentas, terminologias e t´ecnicas. Especialistas de cada ´area n˜ao sabiam

como conversar e tamb´em n˜ao reconheciam uma parte comum em ambos objetivos. Ambos

oferecem valiosas contribui¸c˜oes para cria¸c˜ao de documentos por´em tˆem tido pouca intera¸c˜ao.

A Engenharia de Documentos uniﬁca estas duas perspectivas identiﬁcando e enfatizando o que

tˆem em comum ao inv´es de ressaltar suas diferen¸cas.

2.1. DEFINI ¸C

OES 29

Antes da an´alise de como a Engenharia de Documentos utiliza os conceitos de an´alise de

documentos e modelagem de dados, ´e importante que sejam apresentados os trˆes tipos de infor-

ma¸c˜oes encontradas em documentos:

• Conte´udo - informa¸c˜ao que diz “o que isso signiﬁca”.

• Estrutura - “onde ´e isso” ou “como isso ´e organizado ou montado”. Agrega conte´udo e

informa¸c˜ao em mais de um componente reus´avel.

• Apresenta¸c˜ao - “como isso ´e mostrado”.

Embora o item apresenta¸c˜ao seja o menos importante, ´e essencial analis´a-lo com cuidado,

primeiramente devido `a sua correla¸c˜ao com a estrutura e o conte´udo. Correla¸c˜oes estas que

seguem padr˜oes para diferentes tipos de documentos.

Os pontos cruciais da an´alise e mo delagem de dados harmonizados na Engenharia de Docu-

mentos s˜ao:

• Identiﬁcar a apresenta¸c˜ao, conte´udo, e componentes estruturais deﬁnindo os relacionamen-

tos entre si.

• Identiﬁcar componentes de “bom” conte ´udo.

• Esbo¸car, descrever, e organizar padr˜oes para facilitar o reuso.

• Montar modelos de documentos hier´arquicos para organizar os componentes de acordo

com os requerimentos de um contexto espec´ıﬁco.

Neste contexto, XML ´e uma tecnologia quem tem se destacado bastante no contexto da

Engenharia de Documentos. Dentre suas principais vantagens, podem ser citados:

• Permite que novos vocabul´arios sejam criados para tipos particulares de documentos.

•

E uma linguagem hier´arquica (o que facilita a organiza¸c˜ao dos componentes).

• Facilita a integra¸c˜ao de uma variedade de paradigmas tais como banco de dados, orienta¸c˜ao

a objetos, e estrutura de documentos.

Com o crescimento da Engenharia de Documentos e a facilidade de mesclar layout e conte´udos

provenientes de banco de dados, v´arias empresas come¸caram a desenvolver padr˜oes baseados

30 CAP

ITULO 2. ENGENHARIA DE DOCUMENTOS

em XML para controlar o processo de impress˜ao. Documentos personalizados para diferentes

campanhas de marketing aumentaram essa necessidade assim como a capacidade das impressoras

digitais cada vez mais poderosas. Para impedir a crescente cria¸c˜ao de modelos de composi¸c˜ao

de documentos por parte de empresas que lidam diretamente com impress˜ao digital, foi criado

um cons´orcio de empresas que trabalhariam unidas na deﬁni¸c˜ao de uma linguagem ´unica de

impress˜ao.

Criado em 1999, o PODi (Print on Demand Initiative) [POD05] ´e uma iniciativa sem ﬁns

lucrativos cuja miss˜ao ´e desenvolver a ind´ustria de impress˜ao digital encorajando a padroniza¸c˜ao.

Os membros dessa iniciativa desenvolveram uma linguagem n˜ao-propriet´aria denominada PPML

(Personalized Print Markup Language) a qual utiliza XML como base.

2.2 PPML

PPML [DdB00] ´e uma linguagem padr˜ao utilizada para impress˜ao digital constru´ıda a partir

de XML desenvolvida pelo PODi. PPML tem sido designado para melhorar o processo de

rasteriza¸c˜ao para o conte´udo de documentos que usam linguagens tradicionais de impress˜ao.

PPML na verdade introduz o m´etodo de conte´udo reus´avel atrav´es do qual conte´udos usados

em muitas p´aginas podem ser enviados para a impressora uma ´unica vez e acessados quantas

vezes for necess´ario. Isto permite que conte´udos de alta qualidade gr´aﬁca sejam rasterizados

tamb´em uma ´unica vez e acessados atrav´es de instru¸c˜oes modelo ao inv´es de reenviar-se todo o

gr´aﬁco toda vez que o mesmo deva ser impresso. Cada objeto reus´avel em PPML ´e chamado

recurso. A ﬁm de garantir que todos os recursos estejam dispon´ıveis e a impressora digital possa

acess´a-los, PPML permite referˆencias externas URL (Universal Resource Identiﬁer).

Usualmente, a impressora digital pode acessar os recursos requeridos diretamente de uma

unidade disco local ou atrav´es de uma LAN (Local Area Network). PPML ´e uma linguagem

hier´arquica que cont´em documentos, p´aginas e objetos. Os objetos contidos s˜ao denominados

reus´aveis ou dispon´ıveis. PPML tamb´em introduz o conceito de escopo, para os objetos reus´a-

veis, de forma que o produtor PPML pode instruir o PPML consumidor sobre o tempo de vida

de um objeto em particular. Esse m´etodo ´e bastante poderoso, eﬁciente e pode otimizar o re-

quisito de cache de impress˜ao e objetos pr´e-rasterizados que s˜ao reutilizados por todo o job e/ou

somente em uma p´agina particular. Alguns trabalhos tˆem sido apresentados [Bos00, MMM

04]

a ﬁm de endere¸car este problema que atualmente permanece aberto e est´a fora do escopo deste

2.2. PPML 31

Figura 2.1: Exemplo de renderiza¸c˜ao de um XSL-FO para um formato de sa´ıda

trabalho.

O conte ´udo vari´avel ´e integrado dentro do objeto PPML e ´e formatado atrav´es do uso de

XSL-FO. O objeto que cont´em o XSL-FO ´e denominado ”copy-hole”, que ´e uma ´area deﬁnida

no PPML a qual pode conter um conte ´udo vari´avel expresso na pr´opria linguagem XSL-FO

ou conte´udo n˜ao vari´avel como imagens TIFF (Tagged Image File Format), BMP (Bit-Mapped

Graphic), etc. XSL-FO (tamb´em abreviado como FO - Formatting Objects) ´e um padr˜ao deﬁ-

nido pelo cons´orcio W3C (World Wide Web Consortium), o qual conta com empresas envolvidas

com Internet e Web, [W3C] introduzido para formatar conte´udo XML em m´ıdias paginadas.

De modo ideal, funciona em conjunto com XSL-T (eXtensible Stylesheet Language - Transfor-

mations) [XT05] para mapear conte´udo XML em um modelo de p´agina. Quando o XSL-FO ´e

completado com ambos: modelo de pagina¸c˜ao e conte´udo formatado, o renderizador XSL-FO

executa o passo de composi¸c˜ao do conte´udo dentro das p´aginas obtendo assim o documento

ﬁnal conforme ilustrado na Figura 2.1. A composi¸c˜ao ´e um passo complexo e requer ordem de

impress˜ao assim como conhecimento do modelo. A ferramenta de renderiza¸c˜ao XSL-FO usada

em nossa solu¸c˜ao ´e o FOP (Formatting Object Processor).

Podemos dizer que PPML ´e utilizado para deﬁni¸c˜ao do layout da p´agina e XSL-FO cont´em

a parte renderiz´avel pela ferramenta FOP dentro da p´agina. PPML ´e hier´arquico. Como

podemos ver em 2.2, o elemento raiz pode conter elementos Tarefas (JOB), que podem conter

Documentos (DOCUMENTS), que contˆem P´aginas (PAGE), as quais contˆem marcas (MARKS)

32 CAP

ITULO 2. ENGENHARIA DE DOCUMENTOS

os quais s˜ao denominados copy-holes.

1 PPML...>...

2 <JOB...>...

3 <DOCUMENT...>...

4 <PAGE...>...

5 <MARK...>...</MARK>

6 <MARK...>...</MARK>

7 <PAGE>

8 <PAGE...>...</PAGE>

9 ...

10 <DOCUMENT>

11 <DOCUMENT>...

Figura 2.2: Estrutura hier´arquica em um documento PPML

2.3 XSL-FO

Em um documento PPML podemos encontrar copy-holes cujo conte´udo pode ser uma ima-

gem, espa¸co em branco, ou um conte´udo de texto. Neste trabalho, estamos particularmente

interessados em conte´udos de textos representados em XSL Formatting Objects, ou simples-

mente XSL-FO, visto que ´e a linguagem de entrada para a ferramenta de renderiza¸c˜ao FOP.

XSL-FO ´e um vocabul´ario que descreve como as p´aginas ir˜ao aparecer para o leitor. Existem

56 elementos XSL-FO todos listados em [W3C] sendo 99% deles inicializados pelo preﬁxo fo.

Os objetos de formata¸c˜ao (FOs) diferem basicamente naquilo que cada um deles representa.

Por exemplo, o objeto fo:list-item-label ´e um marcador localizado na frente de uma lista. Pode

ser um n´umero, uma bolinha ou um caracter qualquer. Um fo:list-item-body contem o texto de

um item na lista.

Um FO quando processado, pode ser quebrado em mais de uma p´agina e para facilitar a

impress˜ao, foi dividido em quatro ´areas principais tamb´em hier´arquicas como PPML :

• Regi˜oes: n´ıvel mais alto da hierarquia. Pode-se imaginar como uma regi˜ao de uma p´agina

contendo cabe¸calho, texto e rodap´e. FOs que produzem regi˜oes s˜ao do tipo fo:region-body,

fo:region-after.

• Blocos: representam um bloco de texto como um par´agrafo. fo:block e fo:list-block s˜ao

exemplos.

2.3. XSL-FO 33

• Linhas: esta ´area representa uma linha de texto dentro de um par´agrafo.

• Entre linhas: s˜ao partes de uma linha como um simples caracter, uma referˆencia de rodap´e,

ou uma equa¸c˜ao matem´atica. fo:external-graphic, fo:inline, etc.

Em um documento PPML, um copy-hole contendo XSL-FO ´e facilmente identiﬁcado pelo

delimitador <fo:ro ot> </fo:ro ot>, como mostrado em 2.3.

1 <fo:root>

2 <fo:layout-master-set>

3 <fo:simple-page-master page-width="162.00089pt" page-height="67.18196pt"

4 aster-name="simplePageMaster">

5 <fo:region-body />

6 </fo:simple-page-master>

7 <fo:page-sequence-master master-name="simplePageMasterSequence">

8 <fo:single-page-master-reference master-reference="simplePageMaster" />

9 </fo:page-sequence-master>

10 </fo:layout-master-set>

11 <fo:page-sequence master-reference="simplePageMasterSequence">

12 <fo:flow flow-name="xsl-region-body">

13 <fo:block-container width="162.00089pt" height="67.18196pt">

14 <fo:block language="en" hyphenate="true" font-family="Helvetica"

15 color="device-color(0,0,0,’http://www.hp.com/devicecmyk’,0,0,0,1)">

16 <fo:block space-before.optimum="12pt" font-size="11pt">

17 <fo:inline>

18 We here at

19 <fo:inline font-weight="bold">MINI of Portland</fo:inline>

20 <fo:inline> want to make your MINI experience Great!</fo:inline>

21 </fo:inline>

22 </fo:block>

23 </fo:block>

24 </fo:block-container>

25 </fo:flow>

26 </fo:page-sequence>

27 </fo:root>

Figura 2.3: Exemplo de um copy-hole contendo conte´udo renderiz´avel XSL-FO

A combina¸c˜ao de PPML e XSL-FO tem sido escolhida para representar modelos de do-

cumentos com alto grau de ﬂexibilidade, reusabilidade e otimiza¸c˜ao de impress˜ao. A sinergia

alcan¸cada por essa combina¸c˜ao garante que a parte n˜ao vari´avel do modelo seja expressa como

reus´aveis, e a parte vari´avel como fragmentos XSL-FO. Ap´os a inser¸c˜ao dos dados vari´aveis no

34 CAP

ITULO 2. ENGENHARIA DE DOCUMENTOS

documento, v´arias instˆancias de documentos s˜ao formadas. O passo ﬁnal ´e compor ou renderi-

zar as partes em XSL-FO em uma linguagem de descri¸c˜ao de p´agina (PDL - Page Description

Language) que nada mais ´e do que dispor os comandos de uma p´agina impressa para comandos

que a impressora possa execut´a-los. PCL (Printer Control Language) da HP e Postscript da

Adobe s˜ao dois dos PDLs mais utilizado atualmente. O processo de renderiza¸c˜ao ´e processado

pela ferramenta FOP [FOP05].

2.4 FOP

FOP ´e um dos mais comuns processadores no mercado n˜ao somente porque ´e uma aplica¸c˜ao

de c´odigo aberto, mas tamb´em porque provˆe uma grande variedade de formatos de sa´ıda al´em

de ﬂexibilidade.

E uma aplica¸c˜ao Java que lˆe objetos de formata¸c˜ao (FO) renderizando para

diferentes formatos de sa´ıda tais como PDF, PostScript, SVG , que ´e o foco dos resultados de

renderiza¸c˜oes realizadas nesse trabalho, entre outros.

Figura 2.4: Processo de renderiza¸c˜ao de XSL-FO para SVG

A Figura 2.4 mostra como o processo de renderiza¸c˜ao ´e feito com o uso da ferramenta FOP

partindo-se de um documento PPML contendo copy-holes em XSL-FO. Ao ser localizado no

documento uma marca que indica um copy-hole, <MARK Position=’X1,Y1’>, a ´area delimi-

tada pelas entradas fo:root ´e enviada para a ferramenta FOP que devolver´a o mesmo conte´udo

2.4. FOP 35

renderizado em SVG. O texto renderizado ´e realocado na mesma posi¸c˜ao onde encontrava-se o

XSL-FO no documento PPML.

O processo de renderiza¸c˜ao ´e tipicamente comp osto por trˆes diferentes passos como ilustrado

pela Figura 2.5.

Figura 2.5: Fases do processo de renderiza¸c˜ao

1. Gera¸c˜ao de uma ´arvore de objetos de formata¸c˜ao e resolu¸c˜ao de propriedades;

2. Gera¸c˜ao de uma ´arvore de trabalho (area tree) representando o documento modelado

composto por uma hierarquia retangular tendo as folhas como elementos de texto ou

imagens;

3. Convers˜ao ou mapeamento da ´arvore de trabalho (area tree) para o formato de sa´ıda.

As vantagens deste m´etodo est˜ao na completa independˆencia entre a representa¸c˜ao do docu-

mento XSL-FO e a constru¸c˜ao interna da ´arvore de trabalho. Deste modo, ´e poss´ıvel mapear a

area tree para diferentes conjuntos de PDLs.

36 CAP

ITULO 2. ENGENHARIA DE DOCUMENTOS

Cap´ıtulo 3

Processamento de Alto Desempenho

A ´area de processamento de alto desempenho vem se tornando ao longo dos anos cada vez

mais necess´aria para que se possa obter, de forma efetiva, a solu¸c˜ao de grandes problemas cient´ıﬁ-

cos. Em tais problemas, muitas vezes, os computadores tradicionais n˜ao conseguem produzir um

resultado necess´ario dentro de limites de tempo razo´aveis, comprometendo assim a viabilidade

das solu¸c˜oes para estes problemas. Por outro lado, sistemas computacionais de alto desempenho,

principalmente aqueles com arquitetura paralela, oferecem um maior p otencial para a aborda-

gem. Tais sistemas devem ser utilizados de forma que se possa efetivamente aproveitar a maior

capacidade computacional dispon´ıvel.

Este Cap´ıtulo, apresenta de forma resumida alguns dos principais conceitos abordados na

´area de processamento de alto desempenho tais como, mo delos de arquiteturas, programa¸c˜ao e

algoritmos, assim como alguns fatores de desempenho utilizados para medir o ganho em rela¸c˜ao

`a vers˜ao seq

uencial.

3.1 Modelos de Arquiteturas de Processamento Paralelo

Muito j´a foi desenvolvido em termos de hardware paralelo, e v´arias classiﬁca¸c˜oes foram

propostas [AG94, Dun90, HB84]. A mais conhecida pela comunidade computacional ´e a classiﬁ-

ca¸c˜ao de Flynn [Fly72], que apesar de antiga ´e bastante respeitada. J´a a classiﬁca¸c˜ao de Duncan

[Dun90], mais recente, representa o esfor¸co de acomodar novas arquiteturas que surgiram ap´os

a taxonomia de Flynn.

38 CAP

ITULO 3. PROCESSAMENTO DE ALTO DESEMPENHO

3.1.1 Classiﬁca¸c˜ao de Flynn

Segundo Flynn, o processo computacional deve ser visto como uma rela¸c˜ao entre ﬂuxos de

instru¸c˜oes e ﬂuxos de dados. Um ﬂuxo de instru¸c˜oes equivale a uma seq

uˆencia de instru¸c˜oes

executadas (em um processador) sobre um ﬂuxo de dados aos quais estas instru¸c˜oes est˜ao rela-

cionadas [Dun90] [Fly72].

As arquiteturas de computadores s˜ao divididas em 4 classes cada uma apresentando um

esquema gen´erico de acordo com o ﬂuxo de dados e instru¸c˜oes (Figura 3.1).

Figura 3.1: Taxonomia de arquiteturas (Flynn)

3.1.1.1 SISD

Single Instruction Stream/Single Data Stream (ﬂuxo ´unico de Instru¸c˜oes/ﬂuxo ´unico de da-

dos) corresponde ao tradicional modelo Von Neumann. Um processador executa seq

uencialmente

um conjunto de instru¸c˜oes sobre um conjunto de dados (Figura 3.2).

3.1. MODELOS DE ARQUITETURAS DE PROCESSAMENTO PARALELO 39

Figura 3.2: Modelo computacional SISD

3.1.1.2 SIMD

Single Instruction Stream/Multiple Data Stream (ﬂuxo ´unico de instru¸c˜oes/ﬂuxo m´ultiplo de

dados). Envolve m´ultiplos processadores controlados por uma ´unica unidade mestre executando

simultaneamente a mesma instru¸c˜ao em diversos conjuntos de dados (Figura 3.3). Arquiteturas

SIMD s˜ao utilizadas para manipula¸c˜ao de matrizes e processamento de imagens.

Figura 3.3: Modelo computacional SIMD

40 CAP

ITULO 3. PROCESSAMENTO DE ALTO DESEMPENHO

3.1.1.3 MISD

Multiple Instruction Stream/Single Data Stream (Fluxo m´ultiplo de instru¸c˜oes/Fluxo ´unico

de dados). Envolve m´ultiplos processadores executando diferentes instru¸c˜oes em um ´unico con-

junto de dados. Diferentes instru¸c˜oes operam a mesma posi¸c˜ao de mem´oria ao mesmo tempo,

executando instru¸c˜oes diferentes. Esta classe ´e considerada vazia, por ser tecnicamente impra-

tic´avel. (Figura 3.4).

Figura 3.4: Modelo computacional MISD

3.1.1.4 MIMD

Multiple Instruction Stream/Multiple Data Stream (ﬂuxo m´ultiplo de instru¸c˜oes/ﬂuxo m´ul-

tiplo de dados). Envolve m´ultiplos processadores executando diferentes instru¸c˜oes em diferentes

conjuntos de dados, de maneira independente (Figura 3.5). Esta classe engloba a maioria dos

computadores paralelos.

3.1. MODELOS DE ARQUITETURAS DE PROCESSAMENTO PARALELO 41

Figura 3.5: Modelo computacional MIMD

Dentro da classiﬁca¸c˜ao MIMD enquadram-se os seguintes modelos de arquiteturas:

M´aquinas Vetoriais (PVP - Parallel Vector Processor) - m´aquinas que possuem

processadores compostos de v´arios pipelines vetoriais com alto poder de processamento. Cray e

NEC s˜ao exemplos de m´aquinas vetoriais.

Multiprocessadores Sim´etricos (SMP - Symmetric Multiprocessing) - s˜ao sistemas cons-

titu´ıdos de v´arios processadores comerciais, conectados a uma mem´oria compartilhada, na mai-

oria dos casos atrav´es de um barramento de alta velocidade.

M´aquinas Massivamente Paralelas (MPP - Massively Parallel Processing) - diversos

micropro cessadores interligados atrav´es de uma rede de interconex˜ao normalmente propriet´aria.

Cada n´o de processamento da malha de interconex˜ao pode possuir mais de um processador

e podem existir m´aquinas com milhares destes n´os. A diferen¸ca em rela¸c˜ao aos dois ´ultimos

modelos de m´aquinas ´e que estas n˜ao possuem uma mem´oria compartilhada.

Mem´oria Compartilhada Distribu´ıda (DSM - Distributed Shared Memory) - sistemas

em que, apesar de a mem´oria encontrar-se ﬁsicamente distribu´ıda atrav´es dos n´os, todos os

processadores podem endere¸car todas as mem´orias. Isso se deve `a implementa¸c˜ao de um ´unico

espa¸co de endere¸camento.

Redes de Esta¸c˜oes de Trabalho (NOW - Network of Workstations) - s˜ao sistemas cons-

titu´ıdos por v´arias esta¸c˜oes de trabalho interligadas por tecnologia tradicional de rede como

Ethernet e ATM (Asynchronous Transfer Mode). Na pr´atica, uma rede local de esta¸c˜oes que j´a

42 CAP

ITULO 3. PROCESSAMENTO DE ALTO DESEMPENHO

existe ´e utilizada para execu¸c˜ao de aplica¸c˜oes paralelas.

Agregados (COW - Clusters of Workstations) - neste grupo enquadram-se m´aquinas cujo

princ´ıpio b´asico ´e o emprego de uma rede de custo baixo, por´em de alto desempenho, interligando

nodos que podem possuir mais de um processador. Podem ser vistas como uma evolu¸c˜ao das

redes de esta¸c˜oes de trabalho NOW, pois tamb´em s˜ao constitu´ıdas por v´arias esta¸c˜oes de trabalho

interligadas, mas com a diferen¸ca de terem sido projetadas com o objetivo de executar aplica¸c˜oes

paralelas.

Grades computacionais - s˜ao ambientes para computa¸c˜ao distribu´ıda de alto desempenho

que permitem o compartilhamento de recursos heterogˆeneos. Uma grade ´e uma cole¸c˜ao de

recursos computacionais distribu´ıdos sobre uma rede, que est˜ao dispon´ıveis a um usu´ario ou a

uma aplica¸c˜ao. Grade computacional ´e uma infra-estrutura de software e hardware que provˆe

servi¸cos seguros, consistentes, de acesso penetrante a um custo relativamente acess´ıvel.

3.1.2 Classiﬁca¸c˜ao de Duncan

A classiﬁca¸c˜ao de Duncan [Dun90] surgiu da necessidade de acomodar arquiteturas mais

recentes. Duncan exclui arquiteturas que apresentem apenas mecanismos de paralelismo de

baixo n´ıvel (pipeline, m´ultiplas unidades funcionais e pro cessadores dedicados para entrada e

sa´ıda), que j´a se tornaram lugar comum nos computadores modernos, e mant´em os elementos

da classiﬁca¸c˜ao de Flynn, no que diz respeito ao ﬂuxo de dados e instru¸c˜oes.

A classiﬁca¸c˜ao de Duncan apresentada na Figura 3.6, divide as arquiteturas em dois grupos

principais: arquiteturas s´ıncronas e ass´ıncronas.

3.1. MODELOS DE ARQUITETURAS DE PROCESSAMENTO PARALELO 43

Figura 3.6: Classiﬁca¸c˜ao de Duncan

3.1.2.1 Arquiteturas S´ıncronas

Arquiteturas paralelas s´ıncronas coordenam suas opera¸c˜oes concorrentes sincronamente em

todos os processadores, atrav´es de rel´ogios globais, unidades de controle ´unicas ou controladores

de unidades vetoriais [Dun90]. Tais arquiteturas apresentam pouca ﬂexibilidade para a express˜ao

de algoritmos paralelos [Ble94].

• Processadores Vetoriais: s˜ao caracterizados por possu´ırem um hardware espec´ıﬁco (m´ulti-

plas unidades funcionais organizadas utilizando pip eline) para a otimiza¸c˜ao de opera¸c˜oes

efetuadas sobre vetores.

• Arquiteturas SIMD: arquiteturas SIMD apresentam m´ultiplos processadores, sob a super-

vis˜ao de uma unidade central de controle, que executam a mesma instru¸c˜ao sincronamente

em conjuntos de dados distintos.

• Arquiteturas Sist´olicas: tˆem como principal objetivo fornecer uma estrutura eﬁciente para

a solu¸c˜ao de problemas que necessitem de computa¸c˜ao intensiva junto a grande quan-

tidade de opera¸c˜oes de E/S. Essas arquiteturas se caracterizam pela presen¸ca de v´arios

44 CAP

ITULO 3. PROCESSAMENTO DE ALTO DESEMPENHO

processadores, organizados de maneira pipeline, que formam uma cadeia na qual apenas

os processadores localizados nos limites desta estrutura possuem comunica¸c˜ao com a me-

m´oria.

3.1.2.2 Arquiteturas Ass´ıncronas

Estas arquiteturas caracterizam-se pelo controle descentralizado de hardware, de maneira que

os processadores s˜ao independentes entre si. Essa categoria ´e formada pelas m´aquinas MIMD,

sejam elas convencionais ou n˜ao [Dun90].

• Arquiteturas MIMD: relacionam arquiteturas compostas por v´arios processadores inde-

pendentes, onde se executam diferentes ﬂuxos de instru¸c˜oes em dados locais a esses pro-

cessadores.

• Paradigma MIMD: essa classe engloba as arquiteturas ass´ıncronas que, apesar de apresen-

tarem a caracter´ıstica de multiplicidade de ﬂuxo de dados e instru¸c˜oes das arquiteturas

MIMD, s˜ao organizadas segundo conceitos t˜ao fundamentais a seu projeto quanto suas

caracter´ısticas MIMD. Estas caracter´ısticas pr´oprias de cada arquitetura, diﬁcultam a sua

classiﬁca¸c˜ao como puramente MIMD. Por isso, tais arquiteturas se denominam paradigmas

arquiteturais MIMD.

3.2 Compartilhamento de Mem´oria

Um outro crit´erio para a classiﬁca¸c˜ao de m´aquinas paralelas ´e o compartilhamento da me-

m´oria.

Mem´oria compartilhada ´e assim denominada quando dois ou mais processos comparti-

lham uma mesma regi˜ao de mem´oria.

E a maneira mais r´apida dos processadores efetuarem uma

troca de dados, por´em um lugar da mem´oria n˜ao pode ser modiﬁcado por uma tarefa enquanto

outra estiver acessando. A Figura 3.7 mostra como o acesso `a mem´oria pelos processadores ´e

feito. M´aquinas SMP utilizam este modelo.

3.2. COMPARTILHAMENTO DE MEM

ORIA 45

Figura 3.7: Arquitetura com mem´oria compartilhada

Em arquiteturas de mem´oria distribu´ıda, cada processador possui sua pr´opria mem´oria lo-

cal (Figura 3.8), sendo ent˜ao fracamente acoplados. Em virtude de n˜ao haver compartilhamento

de mem´oria, os processos comunicam-se via troca de mensagens, que se trata da transferˆencia

explicita de dados entre os processadores.

Figura 3.8: Arquitetura com mem´oria distribu´ıda

Dependendo de uma m´aquina paralela utilizar-se ou n˜ao de uma mem´oria compartilhada por

todos os pro cessadores, pode-se diferenciar: Multiprocessadores ou Multicomputadores.

46 CAP

ITULO 3. PROCESSAMENTO DE ALTO DESEMPENHO

3.2.1 Multiprocessadores

Esse tipo de m´aquina possui apenas um espa¸co de endere¸camento, de forma que todos os

processadores P s˜ao capazes de endere¸car todas as mem´orias M. Essas caracter´ısticas resultam do

fato de esse tipo de m´aquina paralela ser constru´ıda a partir da replica¸c˜ao apenas do componente

processador de uma arquitetura convencional conforme mostra a Figura 3.9. Da´ı o nome

m´ultiplos processadores.

Figura 3.9: Multiprocessadores

Em rela¸c˜ao ao tipo de acesso `as mem´orias do sistema, multiprocessadores podem ser classiﬁ-

cados como: UMA (Uniform Memory Access), NUMA (Non-Uniform Memory Access) e COMA

(Cache-Only Memory Architecture).

3.2.1.1 UMA

A mem´oria usada nessas m´aquinas ´e centralizada e encontra-se `a mesma distˆancia de to dos

os processadores, fazendo com que a latˆencia de acesso `a mem´oria seja igual para todos os

processadores do sistema (uniforme) (Figura 3.10). Como o barramento ´e a rede de interconex˜ao

mais usada nessas m´aquinas e suporta apenas uma transa¸c˜ao por vez, a mem´oria principal ´e

normalmente implementada com um ´unico bloco.

3.2. COMPARTILHAMENTO DE MEM

ORIA 47

Figura 3.10: Classiﬁca¸c˜ao UMA

3.2.1.2 NUMA

A mem´oria usada nessas m´aquinas ´e distribu´ıda, implementada com m´ultiplos m´odulos que

s˜ao associados um a cada processador (Figura 3.11). O espa¸co de endere¸camento ´e ´unico, e cada

processador pode endere¸car toda a mem´oria do sistema. Se o endere¸co gerado p elo processador

encontrar-se no m´odulo de mem´oria diretamente ligado a ele (local) o tempo de acesso a ele ser´a

menor que o tempo de acesso a um m´odulo que est´a diretamente ligado a outro processador

(remoto) que s´o pode ser acessado atrav´es da rede de interconex˜ao. Por esse motivo, essas

m´aquinas possuem um acesso n˜ao uniforme `a mem´oria.

Figura 3.11: Classiﬁca¸c˜ao NUMA

3.2.1.3 COMA

Em uma m´aquina COMA, todas as mem´orias locais est˜ao estruturadas como mem´orias cache

e s˜ao chamadas de COMA caches (Figura 3.12). Essas caches tˆem muito mais capacidade que

48 CAP

ITULO 3. PROCESSAMENTO DE ALTO DESEMPENHO

uma cache tradicional. Arquiteturas COMA tˆem suporte de hardware para a replica¸c˜ao efetiva

do mesmo bloco de cache em m´ultiplos n´os fazendo com que essas arquiteturas sejam mais caras

de implementar que as m´aquinas NUMA.

Figura 3.12: Classiﬁca¸c˜ao COMA

3.2.2 Multicomputadores

Cada processador P possui uma mem´oria local M (Figura 3.13), a qual s´o ele tem acesso.

As mem´orias dos outros processadores s˜ao consideradas mem´orias remotas e possuem espa¸cos

de endere¸camento distintos. Como n˜ao ´e poss´ıvel o uso de vari´aveis compartilhadas nesse am-

biente, a troca de informa¸c˜oes com outros processos ´e feita por envio de mensagens pela rede

de interconex˜ao. Por essa raz˜ao, essas m´aquinas tamb´em s˜ao chamadas de sistemas de troca de

mensagens.

Figura 3.13: Multicomputadores

Em rela¸c˜ao ao tipo de acesso `as mem´orias do sistema, multicomputadores podem ser classi-

3.3. MODELOS DE PROGRAMA ¸C

AO PARALELA 49

ﬁcados como: NORMA (Non-Remote Memory Access).

3.2.2.1 NORMA

Como uma arquitetura tradicional inteira foi replicada na constru¸c˜ao dessas m´aquinas, os

registradores de endere¸camento de cada n´o s´o conseguem endere¸car a sua mem´oria local.

3.3 Modelos de Programa¸c˜ao Paralela

Os modelos de programa¸c˜ao paralela existem como uma camada de abstra¸c˜ao sobre a ar-

quitetura do hardware e da mem´oria do computador [Bar05]. No entanto, esses modelos n˜ao

s˜ao espec´ıﬁcos de uma determinada arquitetura nem de um tipo de mem´oria. Geralmente, a

escolha do modelo a ser utilizado depende do programador, do tipo de hardware dispon´ıvel e

das caracter´ısticas da aplica¸c˜ao.

3.3.1 Paralelismo Impl´ıcito e Expl´ıcito

No paralelismo expl´ıcito, a linguagem de programa¸c˜ao cont´em mecanismos para paraleliza-

¸c˜ao do programa. Desta forma, o programador pode utilizar seu conhecimento emp´ırico para

explorar ao m´aximo o potencial de paraleliza¸c˜ao de suas aplica¸c˜oes. No entanto, de acordo com

([KL88]) a utiliza¸c˜ao de mecanismos expl´ıcitos pode levar a uma explora¸c˜ao inadequada do po-

tencial de paralelismo. Al´em disso, conforme [KB88], grande parte do trabalho necess´ario para

paraleliza¸c˜ao de programas ´e muito dif´ıcil para ser realizado por pessoas. Por exemplo, somente

compiladores s˜ao conﬁ´aveis para realiza¸c˜ao da an´alise de dependˆencias em sistemas paralelos

com mem´oria compartilhada. Por outro lado, deve-se ressaltar que o paralelismo expl´ıcito di-

minui a complexidade dos compiladores paralelizadores, pois elimina a necessidade da detec¸c˜ao

autom´atica do paralelismo em tempo de compila¸c˜ao.

No paralelismo impl´ıcito, a linguagem de programa¸c˜ao n˜ao cont´em mecanismos para paraleli-

za¸c˜ao dos programas. A principal vantagem deste m´etodo consiste na libera¸c˜ao do programador

do envolvimento com a paraleliza¸c˜ao de suas aplica¸c˜oes. Al´em disso, o paralelismo impl´ıcito

aumenta a portabilidade de programas entre sistemas paralelos, eliminando a necessidade da

altera¸c˜ao do c´odigo fonte em fun¸c˜ao da arquitetura paralela a ser utilizada. Outra caracter´ıstica

interessante da explora¸c˜ao autom´atica consiste no aproveitamento tanto dos programas seq

uen-

ciais j´a existentes quanto dos ambientes de desenvolvimento (depura¸c˜ao) direcionados para o

50 CAP

ITULO 3. PROCESSAMENTO DE ALTO DESEMPENHO

paradigma seq

uencial.

3.3.2 Paralelismo de Dados

O paralelismo de dados representa o uso de m´ultiplas unidades para se aplicar a mesma

opera¸c˜ao simultaneamente em um dado conjunto de elementos. Segundo [Qui94], K unidades

de processamento adicionais geram um aumento de vaz˜ao de K vezes no sistema. Por vaz˜ao,

entende-se o n´umero de resultados obtidos por ciclo de tempo. A execu¸c˜ao deste tipo de algoritmo

pode ser veriﬁcada, por exemplo, em algoritmos paralelos de multiplica¸c˜ao de matrizes.

3.3.3 Paralelismo de Controle

O paralelismo de controle, diferentemente do paralelismo de dados onde o paralelismo ´e atin-

gido atrav´es de diversas unidades de processamento executando uma ´unica instru¸c˜ao, atinge o

paralelismo atrav´es da aplica¸c˜ao de diferentes opera¸c˜oes a diferentes conjuntos de dados simul-

taneamente. Conforme [Qui94], o ﬂuxo de dados sobre este processo pode ser arbitrariamente

complexo. No paralelismo de controle, a computa¸c˜ao ´e dividida em passos, chamados segmentos

ou est´agios, que s˜ao distribu´ıdos entre os processadores. Cada segmento realiza uma parte do

processamento, e pode ser poss´ıvel que a entrada de um segmento seja a solu¸c˜ao gerada na sa´ıda

do segmento anterior. Por exemplo, a modelagem de um ecossistema, onde cada programa cal-

cula a popula¸c˜ao de um determinado grupo que dep ende dos vizinhos como mostrado na Figura

3.14.

Figura 3.14: Exemplo de paralelismo de controle

3.4. MODELOS DE ALGORITMOS PARALELOS 51

3.3.4 Troca de Mensagens

O desenvolvimento de programas paralelos e distribu´ıdos encontra na programa¸c˜ao baseada

em troca de mensagens, uma abordagem eﬁcaz para explorar as caracter´ısticas das m´aquinas de

mem´oria distribu´ıda. Com o uso de clusters e de bibliotecas de suporte `as trocas de mensagens,

como o padr˜ao MPI (Message Passing Interface), aplica¸c˜oes eﬁcientes e economicamente vi´aveis

podem ser constru´ıdas. MPI ´e uma biblioteca que cont´em fun¸c˜oes para implementar programas

que executam trocas de mensagens em uma ambiente distribu´ıdo. Estes programas rodam em

um cluster e o ambiente MPI se encarrega da distribui¸c˜ao destes processos.

Existem implementa¸c˜oes de MPI para diversas plataformas de hardware e software. Isto

quer dizer que ´e poss´ıvel montar um cluster com n´os de diferentes arquiteturas e usar MPI

para resolver um problema de maneira distribu´ıda. Uma utilidade imediata disto seria utilizar

arquiteturas especializadas em um tipo de processamento para resolver partes do problema que

devem assim ser abordados. No entanto isto imediatamente nos leva a nos perguntarmos como

podemos trocar mensagens entre m´aquinas de arquiteturas diferentes, que possuem tipos internos

de dados diferentes. Para resolver este problema, MPI deﬁne seus pr´oprios tipos b´asicos, que

s˜ao independentes da arquitetura real da m´aquina. MPI se encarrega de converter esses tipos

de dados para os tipos de dados internos.

3.4 Modelos de Algoritmos Paralelos

Existem v´arios modelos de programa¸c˜ao paralela que podem ser escolhidos pelo programador

para estruturar ou organizar o desenvolvimento de programas. A escolha de um ou de outro

depende das caracter´ısticas da aplica¸c˜ao, dos recursos computacionais dispon´ıveis para quem vai

desenvolver o programa e do tipo de paralelismo encontrado no problema. Nas pr´oximas se¸c˜oes, ´e

explicado, resumidamente, alguns dos paradigmas mais comumente utilizados na implementa¸c˜ao

de programas paralelos [NBvO01].

3.4.1 Divis˜ao e Conquista

Um algoritmo de divis˜ao e conquista primeiramente divide o problema original em diversos

subproblemas, que s˜ao mais f´aceis de se resolver do que o original, e ent˜ao resolve os subproble-

mas, geralmente recursivamente. Finalmente o algoritmo mescla as solu¸c˜oes dos subproblemas

para construir uma solu¸c˜ao de um problema original.

52 CAP

ITULO 3. PROCESSAMENTO DE ALTO DESEMPENHO

3.4.2 Pipeline

No paradigma pipeline um n´umero de processos forma um pipeline virtual. Os processos

podem formar esses pipelines de uma maneira linear, multidimensional, c´ıclica ou ac´ıclica. Um

ﬂuxo cont´ınuo de dados entra no primeiro est´agio do pipeline e os processos s˜ao executados nos

demais est´agios complementares, de forma simultˆanea. Cada processo no pipeline pode ser visto

como um consumidor de uma seq

uˆencia de dados precedendo-o no pipeline e como produtor de

dados sucedendo-o no pipeline.

3.4.3 Mestre/Escravo

Neste paradigma, um ou mais processos mestre executam as tarefas essenciais do programa

paralelo e dividem o resto das tarefas para os processos escravos. Quando um processo escravo

termina sua tarefa, ele informa o mestre que atribui uma nova tarefa para o escravo. Este

paradigma ´e bastante simples, visto que o controle est´a centralizado em um processo mestre.

Sua desvantagem ´e que o mestre pode se tornar o gargalo na comunica¸c˜ao. Isso acontece quando

as tarefas s˜ao muito pequenas (ou escravos s˜ao relativamente r´apidos).

3.4.4 Pool de Trabalho

Neste modelo, um pool (conjunto) de tarefas ´e disponibilizado por uma estrutura de dados

global e um determinado n´umero de processos ´e criado para executar esse conjunto de tarefas.

No in´ıcio s´o existe um ´unico peda¸co de tarefa; gradativamente os processos buscam peda¸cos da

tarefa e imediatamente passam a execut´a-los, espalhando o processamento. O programa paralelo

termina quando o pool de trabalho ﬁca vazio.

3.4.5 Fases Paralelas

Neste modelo, a aplica¸c˜ao consiste em um n´umero de etapas, onde cada etapa ´e dividida em

duas fases: uma fase de computa¸c˜ao, quando os m´ultiplos processos executam processamentos

independentes; seguida de uma fase de intera¸c˜ao, quando os processos executam uma ou mais

opera¸c˜oes de intera¸c˜ao s´ıncrona, tais como barreiras ou comunica¸c˜oes bloqueantes.

3.5. CRIT

ERIOS DE AVALIA ¸C

AO 53

3.5 Crit´erios de Avalia¸c˜ao

Uma caracter´ıstica fundamental da computa¸c˜ao paralela trata-se do aumento de velocidade

de processamento atrav´es da utiliza¸c˜ao do paralelismo. Neste contexto, duas medidas muito

importantes, dentre v´arias outras, para a veriﬁca¸c˜ao da qualidade de algoritmos paralelos s˜ao

acelera¸c˜ao (speedup) e eﬁciˆencia.

Acelera¸c˜ao ´e o aumento de velocidade observado quando se executa um determinado pro-

cesso em p pro cessadores em rela¸c˜ao `a execu¸c˜ao deste processo em um ´unico processador.

Speedup =

T 1

T p

Onde, T1 = tempo de execu¸c˜ao em 1 processador (serial)

Tp = tempo de execu¸c˜ao em p processadores (paralela)

O ganho de speedup deveria tender a p, que seria o seu valor ideal 1. Outra medida importante

´e a eﬁciˆencia, que trata da rela¸c˜ao entre o speedup e o n´umero de processadores. Tal medida ´e

obtida atrav´es da seguinte f´ormula:

Eﬁciˆencia =

speedup

Np ´e o n´umero de processadores utilizados para executar o programa paralelo.

Dada as f´ormulas acima, nota-se que o speedup ideal deve ser igual a quantidade de proces-

sadores utilizados no programa paralelo. A eﬁciˆencia deve estar entre zero e um, pois indica um

valor relativo. Se for alcan¸cado um speedup ideal tamb´em ´e alcan¸cada a eﬁciˆencia ideal que ´e

igual a 1 (indicando 100% de eﬁciˆencia).

3.6 Fatores de Desempenho

3.6.1 Granularidade

A granularidade de um sistema paralelo corresponde ao tamanho das unidades de trabalho

submetidas aos processadores. Isto acaba inﬂuenciando na determina¸c˜ao do porte e da quanti-

dade de processadores, uma vez que existe uma rela¸c˜ao entre esses dois fatores.

Em uma linguagem seq

uencial, a unidade de paralelismo ´e todo o programa. Em uma

linguagem paralela, entretanto, a unidade de paralelismo pode ser deﬁnida, em ordem decrescente

54 CAP

ITULO 3. PROCESSAMENTO DE ALTO DESEMPENHO

de granularidade, como um processo, um objeto, um comando, uma express˜ao ou uma cl´ausula

[Hwa93].

O n´ıvel de granularidade varia de ﬁna (muito pouco processamento por comunica¸c˜ao de

byte) a grossa. Quanto mais ﬁna a granularidade, menor a acelera¸c˜ao devido `a quantidade de

sincroniza¸c˜ao exigida.

3.6.2 Portabilidade

Portabilidade ´e a capacidade que um software tem de ser compilado ou executado em diferen-

tes arquiteturas de sistemas computacionais (diferentes arquiteturas de hardware ou de sistema

operacional).

3.6.3 Escalabilidade

Escalabilidade ´e a capacidade de evoluir um software ou fazer com que o mesmo obtenha

recursos adicionais sem perda de desempenho em sua funcionalidade.

Cap´ıtulo 4

Deﬁni¸c˜oes Gerais

Neste Cap´ıtulo ´e apresentado uma an´alise do problema enfrentado atualmente com a vers˜ao

seq

uencial da ferramenta FOP. Al´em disso, um posicionamento em rela¸c˜ao ao embasamento

descrito nos Cap´ıtulos anteriores assim como uma descri¸c˜ao do ambiente de testes e hardware

utilizados na obten¸c˜ao dos resultados.

4.1 An´alise do Problema

Impressoras digitais atualmente encontradas no mercado tˆem velocidade de rasteriza¸c˜ao que

chegam a cerca de 60 p´aginas por minuto, que signiﬁca cerca de uma p´agina por segundo. Isto

´e poss´ıvel se a p´agina j´a esteja representada em um formato que a impressora possa consumir,

ou seja, j´a tenha passado pelo processo de renderiza¸c˜ao e tamb´em rasteriza¸c˜ao.

O conte´udo vari´avel de uma p´agina representado em XSL-FO varia de acordo com a pu-

blica¸c˜ao desenhada pelo designer. Isto signiﬁca que uma p´agina pode conter somente um ´unico

XSL-FO a ser renderizado em um documento PPML ou v´arios.

E importante que o processo

de renderiza¸c˜ao sustente este tipo de desempenho m´edio para que a impressora consiga atingir

seu potencial m´aximo de impress˜ao.

Na Figura 4.1, podemos notar que ap´os o processo de renderiza¸c˜ao h´a ainda outro processo

denominado rasteriza¸c˜ao que ir´a justamente converter o documento PPML na linguagem da

impressora. Entretanto, este processo ´e bem mais r´apido do que a fase de renderiza¸c˜ao n˜ao

amea¸cando o desemp enho da impress˜ao. De modo contr´ario, dependendo da quantidade de

copy-holes contendo dados vari´aveis em XSL-FO, a fase de renderiza¸c˜ao pode tornar-se um

gargalo.

56 CAP

ITULO 4. DEFINI ¸C

OES GERAIS

Figura 4.1: Processo de impress˜ao de documentos em impressoras digitais

Na vers˜ao seq

uencial da ferramenta FOP, somente um XSL-FO pode ser enviado por vez

ﬁcando o processo de renderiza¸c˜ao parado at´e que o XSL-FO enviado seja completamente

renderizado e realocado em sua posi¸c˜ao de origem no documento PPML (Figura 4.2). Em casas

de impress˜ao de grande porte, o n´umero de copy-holes com conte´udo vari´avel pode facilmente

chegar a milh˜oes. Por esse motivo, ´e comum disparar a renderiza¸c˜ao horas antes do processo de

impress˜ao para que n˜ao se perca tempo. Muitas vezes esse processo ´e executado durante a noite

para que a impress˜ao o corra sem problemas durante o dia.

Figura 4.2: Renderiza¸c˜ao de um XSL-FO em um documento PPML

Devido `a grande quantidade de dados a serem impressos, uma impress˜ao de uma campanha

de publicidade para um grande cliente pode durar muitas horas. Neste cen´ario, qualquer ganho

de desempenho signiﬁca muito tempo do total de horas utilizado. Isso ´e fundamental para que

um cliente decida por uma casa de impress˜ao e n˜ao outra na hora de solicitar o servi¸co. Em

busca desse ganho de desempenho, a proposta de paraleliza¸c˜ao da fase de renderiza¸c˜ao atrav´es

do uso da ferramenta FOP torna-se uma solu¸c˜ao de grande signiﬁcado, pois aumentaria em

muito a velocidade com que os documentos s˜ao renderizados dando a possibilidade de um apro-

veitamento maior da real capacidade de impress˜ao das atuais impressoras digitais dispon´ıveis no

4.2. POSICIONAMENTO 57

mercado.

4.1.1 Arquitetura Atual

No Cap´ıtulo 2, vimos que a ferramenta FOP renderiza FOs em diferentes formatos de sa´ıda, e

tamb´em que um documento PPML pode conter v´arios FOs . Entretanto, para que um XSL-FO

seja enviado para o FOP ´e necess´ario que o mesmo seja retirado do documento PPML, enviado

para a renderiza¸c˜ao, e realocado j´a no formato SVG na mesma posi¸c˜ao onde encontrava-se o

XSL-FO anteriormente ao processo de renderiza¸c˜ao. Na arquitetura seq

uencial apresentada na

Figura 4.3, ´e poss´ıvel notar que um extrator foi adicionado justamente para que esse mecanismo

de busca fosse poss´ıvel. De maneira seq

uencial, os FOs s˜ao extra´ıdos pelo extrator, o qual

envia para o FOP o conte´udo a ser renderizado aguardando o retorno no formato SVG . Nesta

arquitetura, o extrator tamb´em ´e respons´avel por realocar o conte´udo renderizado de volta no

documento PPML, que ´e o documento ﬁnal a ser impresso.

Figura 4.3: Vers˜ao seq

uencial da ferramenta FOP

A arquitetura mostra que o arquivo PPML ´e lido e salvo em um dispositivo de disco ou

qualquer outra m´ıdia de entrada/sa´ıda. Isto ser´a melhor apresentado no Cap´ıtulo 5, p or´em

´e importante destacarmos este fator que ´e de fundamental relevˆancia para ambos os modelos:

seq

uencial e paralelo.

4.2 Posicionamento

O primeiro problema que um programador de aplica¸c˜oes de alto desempenho tem que lidar ´e

com a escolha entre arquiteturas multiprocessadas ou multicomputadores. M´aquinas multipro-

cessadas, como apresentado na Se¸c˜ao 3.1 do Cap´ıtulo 3, utilizam um esquema global de acesso `a

mem´oria, e geralmente precisam de um bom barramento para interconex˜ao entre processadores

58 CAP

ITULO 4. DEFINI ¸C

OES GERAIS

e mem´oria. Hoje em dia, tais m´aquinas est˜ao perdendo espa¸co para plataformas de multicom-

putadores como clusters ou grades computacionais. Estas m´aquinas apresentam um esquema

de mem´oria distribu´ıda, e no caso de clusters, s˜ao conectados por uma rede r´apida dedicada.

O desenvolvimento de aplica¸c˜oes para esses tipos de m´aquinas ´e bem diferente. O primeiro

modelo ´e baseado no paradigma de mem´oria compartilhada e o segundo ´e tipicamente baseado

no paradigma de troca de mensagens.

Programar para plataformas com mem´oria distribu´ıda ´e mais complexo porque cada proces-

sador da arquitetura tem uma mem´oria local e n˜ao pode acessar diretamente a mem´oria de outros

processadores. Neste cen´ario, a aplica¸c˜ao deve ser dividida em m´odulos, tamb´em chamados de

processos, que n˜ao compartilham o mesmo espa¸co de endere¸camento entre eles. Assim, os pro-

cessos n˜ao podem trocar informa¸c˜oes atrav´es de vari´aveis compartilhadas. A alternativa ´e prover

uma s´erie de comunica¸c˜oes primitivas as quais baseiam-se em duas funcionalidades principais:

enviar e receber dados atrav´es de uma interconex˜ao de rede. Apesar da grande complexidade,

paradigma de programa¸c˜ao por troca de mensagens tem a grande vantagem de um alto grau

de portabilidade, visto que tais programas podem ser executados sobre plataformas de mem´o-

ria compartilhada sem nenhuma mudan¸ca considerando que uma inevit´avel perda de eﬁciˆencia

pode ser aceita. Por outro lado, programas com mem´oria compartilhada tˆem um baixo grau

de portabilidade, pois n˜ao podem ser executados em plataformas com mem´oria distribu´ıda. Tal

fato somente ser´a poss´ıvel atrav´es de uma completa convers˜ao dos programas para o paradigma

de troca de mensagens.

Considerando que portabilidade e escalabilidade s˜ao funcionalidades desej´aveis em implemen-

ta¸c˜oes de alto desempenho, decidimos adotar a linguagem de programa¸c˜ao Java em nossa imple-

menta¸c˜ao. Java n˜ao ´e freq

uentemente utilizada para esse tipo de aplica¸c˜oes [GHM98, MMG

00]

por duas raz˜oes: ´e uma linguagem interpretada e ´e baseada em um ambiente virtual (JVM -

Java Virtual Machine), que garante a portabilidade. Estes dois fatores s˜ao respons´aveis por um

custo computacional que na maioria das vezes ´e considerado muito signiﬁcativo pelos desenvol-

vedores de aplica¸c˜oes de alto desempenho. Entretanto, nesta implementa¸c˜ao, portabilidade e

compatibilidade com diferentes sistemas operacionais s˜ao cruciais.

Para o desenvolvimento deste trabalho foi utilizado o Java Standard Development Kit (J2SDK,

vers˜ao 1.4.2) e o modelo de programa¸c˜ao paralela por passagem de mensagens com utiliza¸c˜ao

da biblioteca MPI [SOHL

96] para realizar a comunica¸c˜ao entre os processos. Mais especiﬁca-

mente, foi escolhida a implementa¸c˜ao mpich (vers˜ao 1.2.6) juntamente com mpi.Java [mpi05]

4.3. PLATAFORMAS DE HARDWARE 59

(vers˜ao 1.2.5) que ´e uma implementa¸c˜ao Java orientada a objetos para o padr˜ao MPI . O mo-

delo de algoritmo paralelo escolhido foi o mestre/escravo, visto que em todas as arquiteturas

desenvolvidas h´a sempre um m´odulo mestre e escravos, no caso as ferramentas FOP rodando

em paralelo. Os experimentos foram realizados em processadores rodando Linux (distribui¸c˜ao

Slackware, kernel 2.4.29), visto que era a conﬁgura¸c˜ao de hardware dispon´ıvel para testes. En-

tretanto, ´e importante mencionar que mpi.Java tamb´em ´e compat´ıvel com o sistema operacional

Windows, assegurando a portabilidade.

4.3 Plataformas de Hardware

Os resultados apresentados neste trabalho foram obtidos em dois diferentes agregados: Amazˆo-

nia e Ombr´oﬁla. Ambos instalados no CPAD (Centro de Pesquisa de Alto Desempenho) sob

coordena¸c˜ao do professor C´esar De Rose, que disponibiliza a infra-estrutura para realiza¸c˜ao de

pesquisas em projetos cadastrados na ´area de Alto Desempenho.

4.3.1 Amazˆonia

Amazˆonia (Figura 4.4) ´e um agregado heterogˆeneo com 31 n´os com as seguintes conﬁgura¸c˜oes:

• 8 HP Compaq dc5000 MT com processadores Pentium IV de 2.8GHz com 1GB de mem´oria

RAM.

• 8 HP NetServers E800 cada um com 2 processadores Intel Pentium III 1GHz e 256MB de

mem´oria RAM

• 8 HP NetServers E60 cada um com 2 processadores Intel Pentium III 550MHz e 256MB

de mem´oria RAM

• 2 HP workstation zx2000 cada um com 1 processador Intel Itanium2 900MHz e 1GB de

mem´oria RAM

• 5 HP Integrity rx2600 cada um com 2 processadores Intel Itanium2 1.5GHz com 2GB de

mem´oria RAM

Utiliza uma rede de alto desempenho Myrinet para comunica¸c˜ao das aplica¸c˜oes e uma rede

Fast-Ethernet.

60 CAP

ITULO 4. DEFINI ¸C

OES GERAIS

Figura 4.4: Amazˆonia

Para os testes realizados neste agregado, foram utilizadas 8 m´aquinas com duplo processador

Pentium IV 1Ghz com 1GB de mem´oria RAM conectadas por uma rede FastEthernet de 100MB.

4.3.2 Ombr´oﬁla

O agregado Ombr´oﬁla (Figura 4.5) ´e composto de 16 m´aquinas HP e-pc com processador

Pentium III de 1GHz, 256 MB de mem´oria e 20GB de disco. Utiliza uma rede Fast-Ethernet

para comunica¸c˜ao das aplica¸c˜oes.

Figura 4.5: Ombr´oﬁla

Para os testes realizados neste agregado, foram utilizadas 8 m´aquinas conectadas por uma

rede 100MB FastEthernet.

4.4. CASOS DE ESTUDO 61

4.4 Casos de Estudo

Arquivos PPML podem conter ou referenciar uma grande quantidade de diferentes objetos

que v˜ao de v´arios tipos de imagens a documentos PDF e PostScript, e linguagens baseadas

em XML como SVG e XSL-FO. Contudo, neste trabalho o foco principal n˜ao ´e destacar

o potencial da linguagem PPML, mas sim a capacidade da ferramenta FOP em sua vers˜ao

paralela de renderizar uma grande quantidade de XSL-FOs . Logo, para a realiza¸c˜ao dos testes

os mesmos documentos foram replicados n vezes em um ´unico job em um arquivo PPML, ou

seja, os mesmos XSL-FOs com o mesmo conte´udo s˜ao enviados para o FOP.

O primeiro arquivo PPML de entrada, chamando Mini, contem um job com mil documentos

a serem renderizados. Cada documento ´e composto por duas p´aginas como mostra a Figura 4.6

distribu´ıdas da seguinte forma:

• P´agina 1: 1 copy-hole com XSL-FO composto por 4 blocos de texto e aproximadamente

107 palavras.

• P´agina 2: 3 copy-holes com XSL-FO, respectivamente composto por 6 blocos de texto

e aproximadamente 130 palavras, 2 blocos de texto e aproximadamente 43 palavras e 1

bloco de texto com 36 palavras.

• N´umero m´edio de palavras por bloco: 24,3

Os n´umero total de XSL-FOs a serem renderizados contidos nos copy-holes no do cumento

PPML somam quatro mil. Lembrando que cada referˆencia fo: dentro de um copy-hole ´e con-

siderado um FO renderizado. Os documentos PPML s˜ao instˆancias do modelo mostrado na

Figura 4.6.

O segundo teste (CAP) tem dois mil documentos. O documento tem duas p´aginas, cada

uma com as seguintes caracter´ısticas:

• P´agina 1: 3 copy-holes com XSL-FO, todos com 1 bloco de texto, respectivamente com 4

palavras, 6 palavras e 7 palavras.

• P´agina 2: 3 copy-holes com XSL-FO, respectivamente com 4 blocos de texto e 56 palavras,

1 bloco de texto e 6 palavras e 1 bloco de texto com 2 palavras.

• N´umero m´edio de palavras por bloco: 9

62 CAP

ITULO 4. DEFINI ¸C

OES GERAIS

Figura 4.6: Exemplo de documento gerado pelo PPML Mini

O n´umero total de XSL-FOs a serem renderizados chegam a 12000. O modelo mostrado na

Figura 4.7 foi usado para criar este arquivo de entrada.

O terceiro teste ´e denominado Appl. Tem um job com mil documentos. Cada documento

contem trˆes p´aginas como segue:

• P´agina 1: 2 copy-holes com XSL-FO, ambos compostos somente por 1 bloco de texto

cada, respectivamente com 11 palavras e com 13 palavras.

• P´agina 2: 1 copy-hole com XSL-FO, quem contem 1 bloco de texto e 32 palavras.

• N´umero m´edio de palavras por bloco: 18,67

4.4. CASOS DE ESTUDO 63

Figura 4.7: Exemplo de documento gerado pelo PPML CAP

Assim, o n´umero de fragmentos XSL-FO a serem renderizados chega a 3000. Tal entrada

foi gerada usando o modelo mostrado na Figura 4.8.

O ´ultimo teste ´e idˆentico ao terceiro mas com um job de dois mil documentos, o que

resultar´a em 6000 XSL-FOs a serem renderizados. Este ´ultimo teste tamb´em foi gerado pelo

modelo mostrado na Figura 4.8.

O tamanho dos arquivos a serem lidos e salvos da unidade de disco ´e apresentado na tabela

4.1. O tamanho do arquivo de sa´ıda afeta diretamente o tempo de E/S (Entrada/Sa´ıda) (Se¸c˜ao

5.4.1) gasto para salvar o arquivo ﬁnal no disco.

64 CAP

ITULO 4. DEFINI ¸C

OES GERAIS

Figura 4.8: Exemplo de documento gerado pelo PPML Appl

Arquivo Documentos Tamanho n˜ao renderizado Tamanho renderizado

Mini 1000 11MB 23MB

CAP 2000 24MB 33MB

Appl 1000 17MB 32MB

Appl 2000 33MB 62MB

Tabela 4.1: Tamanho dos arquivos PPML utilizado nos testes

Cap´ıtulo 5

Estrat´egias de Alto Desempenho

Neste Cap´ıtulo s˜ao apresentadas as estrat´egias de paraleliza¸c˜ao adotadas para a renderiza¸c˜ao

de documentos XSL-FO atrav´es do uso da ferramenta FOP. Para cada estrat´egia ´e descrito,

resumidamente, como a implementa¸c˜ao se desenvolveu seguido dos resultados obtidos em cada

arquitetura apresentada.

5.1 Estrat´egia Inicial

Tanto na vers˜ao seq

uencial do FOP como na solu¸c˜ao de alto desempenho, o documento

de sa´ıda gerado ap´os a renderiza¸c˜ao, ´e composto pela mesma estrutura do PPML de entrada,

por´em com os FOs substitu´ıdos por sua correspondente vers˜ao renderizada, conforme descrito

no Cap´ıtulo 4, Se¸c˜ao 4.1.

Na vers˜ao seq

uencial, a parte do documento PPML que n˜ao ´e renderiz´avel (parte est´atica)

´e automaticamente copiada para o PPML de sa´ıda at´e o momento em que um copy-hole com

conte´udo XSL-FO ´e encontrado. Este ´e enviado para o FOP que retorna SVG salvo no PPML

de sa´ıda. Entretanto, na vers˜ao de alto desempenho este processo de envio e espera pela rende-

riza¸c˜ao n˜ao ´e poss´ıvel, j´a que o extrator de FOs n˜ao p´ara a busca por XSL-FOs assim que o

primeiro ´e encontrado. Pelo contr´ario, ao encontr´a-lo j´a o envia para o FOP e segue a busca no

documento por mais copy-holes contendo XSL-FOs . Para lidar com o recebimento de v´arios

FOs enviados pelo extrator, que na arquitetura mostrada na Figura 5.1 aparece como consu-

midor PPML, foram adicionados ao esquema FOPs rodando em paralelo. Com v´arios FOs

sendo enviados para o FOP e SVGs retornando para serem realocados no PPML (para que

o consumidor PPML soubesse onde realoc´a-los) fez-se necess´ario a cria¸c˜ao de um identiﬁcador

66 CAP

ITULO 5. ESTRAT

EGIAS DE ALTO DESEMPENHO

´unico para conte´udo enviado para renderiza¸c˜ao. Assim, o arquivo PPML de sa´ıda ´e gerado da

seguinte forma: o consumidor PPML varre o documento em busca de copy-holes com conte´udo

renderiz´avel. Aquilo que n˜ao ´e renderiz´avel j´a vai sendo gravado no documento de sa´ıda em me-

m´oria. Quando um XSL-FO ´e encontrado, um identiﬁcador ´e gerado e o XSL-FO enviado para

o FOP, e no documento de sa´ıda abre-se uma lacuna esperando que o SVG com o identiﬁcador

corresp ondente retorne para que seja realocado em sua posi¸c˜ao. Como a busca por XSL-FOs

prossegue, o arquivo segue sendo gerado.

A medida que os FOs renderizados v˜ao retornando,

entram em uma ﬁla para que o consumidor veriﬁque qual o identiﬁcador correspondente `a pri-

meira lacuna no documento. Caso seja encontrado, o SVG ´e imediatamente re-inserido fechando

aquela lacuna. Caso n˜ao seja encontrado, a ﬁla de FOs renderizados cresce at´e que o esperado

seja enviado por um dos FOPs . Quando n˜ao h´a mais FOs na ﬁla, o documento ´e transposto

da mem´oria para a unidade de disco.

Figura 5.1: Solu¸c˜ao inicial

5.1.1 Implementa¸c˜ao

Para a implementa¸c˜ao dessa arquitetura, trˆes m´odulos s˜ao necess´arios: o consumidor PPML

(PPML consumer), broker e a pr´opria ferramenta FOP. Nos dois primeiros m´odulos, fez-se

necess´ario o uso de threads para lidar com as v´arias requisi¸c˜oes de comunica¸c˜ao em paralelo. A

Figura 5.1 mostra duas threads de entrada e sa´ıda no m´odulo broker e uma thread para receber

5.1. ESTRAT

EGIA INICIAL 67

os FOs renderizados no consumidor PPML. Este ´ultimo, ´e respons´avel por analisar o arquivo

PPML de origem removendo os FOs e envi´a-los para o broker. A thread de recebimento salva o

conte´udo est´atico (parte n˜ao renderizada) do PPML em mem´oria, e recebe os FOs renderizados

enviados pelos m´odulos FOP realocando-os em sua posi¸c˜ao de origem. O broker ´e respons´avel

por receber e enﬁleirar os FOs a serem renderizados. Estes FOs devem ser enviados para o

componente FOP que requisitou trabalho. De forma a obter um melhor desempenho, este

componente foi dividido em duas threads:

1. receiver (in): respons´avel por receber e enﬁleirar os FOs a serem renderizados;

2. sender (out): veriﬁca se existe algum FO esperando para ser enviado na ﬁla de FOs e o

envia para o primeiro m´odulo FOP ocioso.

O m´odulo FOP ´e o respons´avel por renderiz´a-los, e quando este processo ´e ﬁnalizado, o

resultado ´e enviado de volta para a thread de recebimento do consumidor PPML, que tamb´em

notiﬁca os m´odulos FOP de que est´a pronta para receber outro FO .

Um coment´ario ﬁnal sobre a implementa¸c˜ao do processo de renderiza¸c˜ao XSL-FO est´a re-

lacionado ao uso das threads. Sistemas de programa¸c˜ao concorrente usando threads introduzem

problemas relacionados ao acesso simultˆaneo de recursos compartilhados. Um sistema ´e deno-

minado thread-safe se este est´a salvo para chamar m´ultiplas threads mesmo que em paralelo.

O contr´ario pode causar comportamentos imprevis´ıveis e gerar resultados inesperados, corrom-

per estruturas de dados internas, etc. Em Java, uma implementa¸c˜ao chamada thread-safe ´e

alcan¸cada com:

1. uso de m´etodos sincronizados;

2. imutabilidade de dados encapsulados, ou seja, n˜ao ´e poss´ıvel modiﬁcar nenhum campo

depois que o objeto for criado.

5.1.2 Resultados

Alguns experimentos foram executados a ﬁm de que as vantagens e desvantagens da aborda-

gem descrita na Se¸c˜ao anterior fossem apontadas. Esta Se¸c˜ao apresenta os resultados destes ex-

perimentos que utilizaram o documento XSL-FO Mini apresentados na Se¸c˜ao 4.4 como entrada.

Buscando um parˆametro de compara¸c˜ao, a vers˜ao seq

uencial da ferramenta de renderiza¸c˜ao foi

68 CAP

ITULO 5. ESTRAT

EGIAS DE ALTO DESEMPENHO

executada utilizando um processador do agregado Amazˆonia descrito no Cap´ıtulo 4 Se¸c˜ao 4.3,

resultando em um tempo de execu¸c˜ao de 350,05 segundos. Cada tempo de execu¸c˜ao apresentado

nesta Se¸c˜ao foi obtido ap´os 5 execu¸c˜oes descartando o maior e o menor valor encontrado.

Figura 5.2: Resultados: seq

uencial e vers˜ao rodando em paralelo com at´e 6 processadores

O primeiro conjunto de experimentos foi executado com a seguinte conﬁgura¸c˜ao dos m´odulos:

um consumidor PPML, um broker, e de um a quatro m´odulos FOP. Em cada conﬁgura¸c˜ao,

cada m´odulo foi exclusivamente designado para um processador do agregado. Os resultados deste

experimento s˜ao mostrados na Figura 5.2. Como pode ser observado, o tempo de execu¸c˜ao cai

de 350,05 segundos para menos de 100 segundos (mais precisamente 98,23) com quatro m´odulos

FOP executando em paralelo em diferentes processadores.

A an´alise dos resultados revelam as diferen¸cas entre a vers˜ao seq

uencial e a vers˜ao de alto

desempenho usando somente trˆes processadores (somente 1 m´odulo FOP ). Embora o segundo

n˜ao apresente m´odulos FOP rodando em paralelo, um melhor tempo de execu¸c˜ao ´e alcan¸cado

apesar do custo de comunica¸c˜ao introduzido pelo agregado. Isto pode ser explicado pela modiﬁ-

ca¸c˜ao adicionada no procedimento de leitura e escrita dos arquivos de entrada e sa´ıda descritos

5.1. ESTRAT

EGIA INICIAL 69

na Se¸c˜ao 5.1.1. Os benef´ıcios reais da vers˜ao de alto desempenho come¸cam a aparecer no ex-

perimento com quatro processadores. Neste caso, existem dois m´odulos FOP executando em

paralelo e o tempo de execu¸c˜ao cai quase `a metade da conﬁgura¸c˜ao anterior (121,92 segundos).

Uma pequena diferen¸ca entre o tempo de execu¸c˜ao com trˆes ou quatro m´odulos FOP (100,09

para 98,23 segundos) ´e outra informa¸c˜ao interessante que podemos extrair do gr´aﬁco. Isso ´e um

forte ind´ıcio de que o m´odulo broker come¸ca a ter problemas para escalar quando tem que lidar

com mais de trˆes m´odulos FOP ro dando em paralelo. De modo a validar esta hip´otese, mais

experimentos foram executados com conﬁgura¸c˜oes de 5 `a 14 m´odulos FOP (7 `a 16 m´odulos

incluindo o Consumidor PPML e o broker).

Figura 5.3: Compara¸c˜ao entre o ganho de desempenho (speedup) ideal e o alcan¸cado pela exe-

cu¸c˜ao da solu¸c˜ao de alto desempenho com at´e 16 processadores

A Figura 5.3 evidencia a queda na eﬁciˆencia `a medida que o n´umero de processadores au-

menta. O gr´aﬁco mostra que o maior ganho obtido para os experimentos executados foi com 4

(71%) e 5 (69%) processadores. A partir disso, a eﬁciˆencia cai gradativamente comprovando que

n˜ao h´a ganho em usarmos todos os processadores do agregado, como pode ser observado nos

70 CAP

ITULO 5. ESTRAT

EGIAS DE ALTO DESEMPENHO

percentuais apresentados na Tabela 5.1. Isto se deve provavelmente ao aumento da comunica¸c˜ao

entre o m´odulo FOP e o m´odulo broker, visto que com muitas tarefas concorrentes para execu-

tar, este torna-se o gargalo do sistema tendo que prover a comunica¸c˜ao com todos os m´odulos

FOP.

N´umero de CPUs

3 4 5 6 7 8 9 10 11 12 13 14 15 16

Tempo (seg) 214,09 121,92 100,09 98,83 98,55 98,25 98,00 97,53 96,47 96,15 95,44 94,69 94,18 93,30

Eﬁciˆencia (%) 54,50 71,77 69,94 59,03 50,74 44,53 39,68 35,89 32,98 30,33 28,21 26,40 24,77 23,44

Tabela 5.1: Tabela de eﬁciˆencia e tempo de execu¸c˜ao por processador

A ﬁm de conﬁrmar tal suposi¸c˜ao, medimos o tempo que os m´odulos FOP ﬁcam aguardando

pela comunica¸c˜ao. A Figura 5.4 apresenta os resultados comparando o tempo total de execu¸c˜ao

para cada conﬁgura¸c˜ao com o tempo gasto com a comunica¸c˜ao dos m´odulos FOP. Com uma

conﬁgura¸c˜ao de 6 a 14 m´odulos FOP, o tempo gasto com comunica¸c˜ao por um m´odulo FOP

representa cerca de 70% do tempo de execu¸c˜ao.

Podemos colher outra an´alise imp ortante do gr´aﬁco apresentado na Figura 5.5, o qual mostra

a diferen¸ca entre o temp o de execu¸c˜ao do m´odulo FOP mais r´apido e do mais lento para

cada conﬁgura¸c˜ao executada.

E poss´ıvel notar que `a medida que o n´umero de m´odulos FOP

aumenta, a diferen¸ca entre o mais r´apido e o mais lento cresce at´e que atinja uma diferen¸ca de

aproximadamente 15 segundos. Nesta situa¸c˜ao, o m´odulo broker pode n˜ao responder ao grupo de

m´odulos FOP igualmente e por esta raz˜ao, alguns m´odulos FOP gastam mais tempo esperando

por comunica¸c˜ao com o broker do que os demais.

Levando-se em considera¸c˜ao as an´alises feitas at´e agora, a conﬁgura¸c˜ao ideal de m´odulos

FOP por broker para um conjunto de dados de entrada de mesma caracter´ıstica ´e de 1 broker

e 3 m´odulos FOP. Tais descobertas est˜ao alinhadas com o objetivo de identiﬁcar um conceito

de unidade composto p or um broker e um certo n´umero de renderizadores. Esta unidade ser´a

usada em paralelo de acordo com a velocidade das impressoras utilizadas nas Print Shops. Assim,

para melhorar o desemp enho desta abordagem, a melhor solu¸c˜ao seria ter uma conﬁgura¸c˜ao com

m´ultiplos brokers, na qual o m´odulo consumidor PPML coordena um conjunto de m´odulos broker

cada um lidando com seu pr´oprio grupo de m´odulos FOP. A Figura 5.6 representa este novo

esquema descrito na Se¸c˜ao 5.2 a seguir.

5.2. M

ULTIPLOS BROKERS 71

Figura 5.4: Tempo de comunica¸c˜ao m´odulos FOP

5.2 M´ultiplos Brokers

Com base nos resultados apresentados anteriormente na Se¸c˜ao 5.1.2 e em cima da an´alise de

que quanto maior o n´umero de m´odulos FOP o m´odulo broker pode n˜ao responder igualmente

devido ao tempo gasto com a comunica¸c˜ao, a estrat´egia de utiliza¸c˜ao de m´ultiplos brokers foi

implementada.

5.2.1 Implementa¸c˜ao

Basicamente, esta estrat´egia conforme mostrado na Figura 5.6 replica o n´umero de brokers

fazendo com que o consumidor PPML tenha mais op¸c˜oes livres ao enviar os FOs . Portanto,

a funcionalidade das threads anteriormente explicada na Se¸c˜ao 5.1.1 ´e mantida adicionando-se

somente a possibilidade do consumidor PPML enviar FOs para diferentes m´odulos brokers.

Cada broker seria respons´avel por um n´umero ﬁxo de m´odulos FOP, os quais seriam res-

pons´aveis por renderiz´a-los retornando-os para o consumidor PPML.

72 CAP

ITULO 5. ESTRAT

EGIAS DE ALTO DESEMPENHO

Figura 5.5: M´odulos FOP n˜ao balanceados

O objetivo desta estrat´egia era provar que mesmo com o aumento do tempo gasto com a

comunica¸c˜ao devido ao incremento do n´umero de brokers comunicando-se com m´odulos FOP

e conseq

uentemente do n´umero de FOs transitando, o m´odulo broker, identiﬁcado como um

poss´ıvel gargalo, pudesse ser aliviado e como conseq

uˆencia melhores resultados alcan¸cados.

5.2.2 Resultados

Os resultados apresentados na Tabela 5.2, por´em n˜ao conﬁrmaram as expectativas. Como

pode-se notar, com diferentes combina¸c˜oes de Brokers (B) e m´odulos FOP (F), o tempo de

execu¸c˜ao em segundos foi pior em todos os casos.

Indo mais a fundo na detec¸c˜ao da causa dessa queda no desempenho, mediu-se o tempo que

o m´odulo FOP gastava recebendo e enviando os FOs , e foi poss´ıvel identiﬁcar que o tempo

de recebimento caiu, por´em o tempo de envio aumentou sensivelmente. Isto demonstra que

com a adi¸c˜ao dos m´ultiplos brokers o gargalo transferiu-se para a fase posterior, que no caso ´e

consumidor PPML o qual recebe os v´arios FOs renderizados e monta o arquivo PPML de sa´ıda.

5.2. M

ULTIPLOS BROKERS 73

Figura 5.6: M´ultiplos brokers

Conﬁgura¸c˜ao Tempo(seg)Multi-broker Tempo 1 Broker (seg)

2B 3F 113,99 111,06

2B 4F 117,32 112,25

3B 3F 116,74 111,18

3B 4F 113,25 110,78

Tabela 5.2: Tabela comparando a execu¸c˜ao com diferentes conﬁgura¸c˜oes (brokers e m´odulos

FOP ) e 1 broker

Como o recebimento dos FOs renderizados ´e feito atrav´es de uma ´unica thread implementada

no consumidor PPML, h´a uma concorrˆencia com o processo de busca e envio de FOs que ´e

gerenciado tamb´em pelo mesmo m´odulo. Logo, com o aumento na velocidade de renderiza¸c˜ao

74 CAP

ITULO 5. ESTRAT

EGIAS DE ALTO DESEMPENHO

dos FOs tanto a montagem do arquivo ﬁnal quanto a busca por novos FOs a serem renderizados

que s˜ao tarefas que exigem muito do processo acabam concorrendo e conseq

uentemente a thread

de recebimento nem sempre est´a pronta para receber os FOs dos m´odulos FOP.

Portanto, uma poss´ıvel solu¸c˜ao para este problema seria implementar o recebimento dos FOs

separadamente em outro processo de modo que n˜ao haja concorrˆencia. A estrat´egia apresentada

a seguir na Se¸c˜ao 5.3 mostra como isto seria arquitetado.

5.3 Divis˜ao do Consumidor PPML

Diferentemente das solu¸c˜oes anteriores em que o m´odulo respons´avel por varrer o documento

PPML a procura de FOs era o mesmo respons´avel pela tarefa de recebimento dos FOs rende-

rizados enviados pelos m´odulos FOP, nesta arquitetura o objetivo foi justamente separar este

processo de recebimento colocando-o em um processo separado a ﬁm de evitar sobrecarga do

m´odulo consumidor. Al´em disso, um buﬀer de FOs foi adicionado ao m´odulo broker o qual

anteriormente enﬁleirava FOs enviando-os para os FOPs `a medida que estavam livres para o

processamento. Com essa nova funcionalidade, primeiro o buﬀer ´e preenchido com v´arios FOs

variando a quantidade de acordo com o tamanho do buﬀer e tamb´em do FO , e somente ap´os

estar cheio ´e enviado para um m´odulo FOP que ir´a process´a-los.

5.3.1 Implementa¸c˜ao

A Figura 5.7 mostra a adi¸c˜ao de um novo processo na arquitetura denominado recebedor

PPML (receiver), o qual anteriormente fazia parte do m´odulo consumidor PPML. O processo

de renderiza¸c˜ao se d´a ent˜ao da seguinte maneira: o consumidor PPML continua respons´avel por

varrer o arquivo PPML de origem retirando os FOs a serem enviados para os brokers. Estes

s˜ao enviados para um buﬀer de FOs no m´odulo broker que ao atingir o tamanho especiﬁcado os

distribui entre os m´odulos FOP para renderiza¸c˜ao. Durante o processo de varredura no PPML,

a parte n˜ao-renderiz´avel do documento vai sendo armazenada em um vetor, e assim que um

copy-hole contendo FOs ´e localizado ´e enviado para a ﬁla. Seguindo o processo normalmente,

o broker envia os FOs para os m´odulos FOP que os renderizam, e estes ap´os a renderiza¸c˜ao os

enviam para o receiver. Neste momento, para que o arquivo de sa´ıda seja montado substituindo

os FOs por SVGs , o receiver acessa o vetor preenchido pelo consumidor PPML a ﬁm de que

a parte n˜ao renderizada seja copiada para o arquivo de sa´ıda e, de acordo com o identiﬁcador

5.3. DIVIS

AO DO CONSUMIDOR PPML 75

do FO , este seja corretamente substitu´ıdo pelo c´odigo SVG . Este processo se repete at´e que

n˜ao hajam mais FOs a serem renderizados.

Figura 5.7: Arquitetura da solu¸c˜ao de divis˜ao do consumidor PPML

5.3.2 Resultados

Esta Se¸c˜ao apresenta os resultados destes experimentos que utilizaram os documentos XSL-

FO apresentados na Se¸c˜ao 4.4 como entrada. Maiores detalhes sobre estes resultados podem ser

encontrados em [FGZea06].

Buscando um parˆametro de compara¸c˜ao, a vers˜ao seq

uencial da ferramenta de renderiza¸c˜ao

foi executada utilizando um processador do agregado Ombr´oﬁla descrito na Se¸c˜ao 4.3, resultando

nos tempos apresentados nas ﬁguras 5.8, 5.9 e 5.10. Cada tempo de execu¸c˜ao apresentado nesta

Se¸c˜ao foi obtido ap´os 5 execu¸c˜oes descartando o maior e o menor valor encontrado.

Para entender melhor os gr´aﬁcos e tabelas apresentados, conforme descrito na implementa¸c˜ao

esta solu¸c˜ao apresenta em sua arquitetura a divis˜ao do consumidor PPML o que signiﬁca a adi¸c˜ao

de um novo processo. Assim, onde aparecem 4 processadores em paralelo temos a seguinte

conﬁgura¸c˜ao:

• 1 consumidor PPML

• 1 recebedor PPML

• 1 Broker

• 1 FOP

76 CAP

ITULO 5. ESTRAT

EGIAS DE ALTO DESEMPENHO

Desta forma, para termos pelo menos 2 m´odulos FOP trabalhando realmente em paralelo ´e

necess´ario no m´ınimo 5 processadores.

O primeiro experimento foi executado utilizando o arquivo de entrada Mini, o qual cont´em

1000 documentos. Este ´e o menor job utilizado nos testes, por´em representa uma alta densidade

em termos de n´umeros de palavras por bloco de texto. Neste caso, o melhor tempo de execu¸c˜ao

foi de 79,07 segundos (usando 12 processadores), mas esta conﬁgura¸c˜ao apresenta eﬁciˆencia

baixa (30,98%). Na verdade, de 7 `a 12 processadores o ganho em termos de tempo de execu¸c˜ao

n˜ao ´e muito signiﬁcativo, indicando que o sistema pode n˜ao ter vantagens quando h´a mais de 4

m´odulos FOP rodando em paralelo. A Figura 5.8 mostra os resultados para este caso de teste.

N´umero de Processadores

1 4 5 6 7 8 9 10 11 12

Tempo(seg) 293,96 204,52 118,19 96,34 86,51 81,88 78,51 79,98 78,18 79,07

Eﬁciˆencia(%) 100,00 35,94 49,74 50,85 48,54 44,88 41,60 36,75 34,18 30,98

Figura 5.8: Resultados com arquivo de entrada Mini com 1000 documentos

No segundo experimento, foi utilizado o arquivo de entrada CAP. Este ´e mais denso em

termos de elementos a serem renderizados. O tempo seq

uencial neste caso foi de 491,51 segundos

para renderizar 2000 documentos. O melhor tempo de execu¸c˜ao (129,73 segundos) foi alcan¸cado

5.3. DIVIS

AO DO CONSUMIDOR PPML 77

com 8 processadores, por´em novamente o ganho de 7 `a 12 processadores n˜ao ´e signiﬁcativo em

termos de tempo de execu¸c˜ao. Os resultados deste exp erimento s˜ao mostrados na Figura 5.9.

N´umero de Processadores

1 4 5 6 7 8 9 10 11 12

Tempo(seg) 491,51 349,23 194,96 161,39 142,35 129,73 133,52 135,80 131,51 131,62

Eﬁciˆencia(%) 100,00 35,18 50,42 50,76 49,32 47,36 40,90 36,19 33,98 31,12

Figura 5.9: Resultados com arquivo de entrada CAP com 2000 documentos

Para o ´ultimo experimento, foi utilizado o mesmo modelo somente trocando o n´umero de

documentos contidos no job de entrada Appl com 1000 e 2000 documentos. Tal procedimento

permitiu uma an´alise de escalabilidade da solu¸c˜ao em paralelo quando a quantidade de trabalho

´e aumentada. O experimento com 1000 documentos apresentou a melhor execu¸c˜ao com 11

processadores (101,37 segundos). Por outro lado, para renderizar 2000 documentos, a execu¸c˜ao

mais r´apida foi obtida com 10 processadores (190,10 segundos). Os resultados mostram que

a solu¸c˜ao paralela escalonou bem quando a quantidade de documentos a serem renderizados

dobrou. Os resultados s˜ao mostrados na Figura 5.10.

Comparando os trˆes casos de testes aqui apresentados, um comportamento em comum foi

detectado: rodando a aplica¸c˜ao com mais de 7 processadores n˜ao apresenta melhoras no tempo

78 CAP

ITULO 5. ESTRAT

EGIAS DE ALTO DESEMPENHO

N´umero de Processadores

1 4 5 6 7 8 9 10 11 12

Tempo(seg) 372,68 274,15 157,70 121,97 108,41 105,88 106,45 103,48 101,37 101,88

Eﬁciˆencia(%) 100,00 33,98 47,26 50,92 49,11 44,00 38,90 36,01 33,42 30,48

N´umero de Processadores

1 4 5 6 7 8 9 10 11 12

Tempo(seg) 742,17 529,57 316,11 245,91 203,79 198,18 198,71 190,10 195,79 192,80

Eﬁciˆencia(%) 100,00 35,03 46,96 50,30 52,03 46,81 41,50 39,04 34,46 32,08

Figura 5.10: Resultados com arquivo de entrada Appl com 1000 e 2000 documentos

de execu¸c˜ao que justiﬁcariam o uso de mais processadores. Acredita-se que a raz˜ao disso ´e

devido ao m´odulo Broker alcan¸car seu limite quando lida com 4 m´odulos FOP. Caso o n´umero

ultrapasse este valor, o m´odulo n˜ao consegue distribuir os FOs eﬁcientemente entre os m´odulos

FOP tornando-se um gargalo.

5.4 An´alise Complementar

Nos testes apresentados neste Cap´ıtulo, n˜ao levam em considera¸c˜ao dois fatores de grande

importˆancia nos resultados: o tempo de entrada e sa´ıda e a varia¸c˜ao do tamanho do buﬀer. Esta

5.4. AN

ALISE COMPLEMENTAR 79

Se¸c˜ao mostra uma an´alise complementar considerando estes dois fatores.

5.4.1 Entrada/Sa´ıda

Um fator relevante nos resultados mostrados ´e o dispositivo de entrada e sa´ıda (I/O - In-

put/Output). Em todos os testes realizados, o tempo gasto com I/O est´a presente nos resultados.

Entretanto, como o dispositivo de I/O ´e o mesmo para ambos os casos, seq

uencial e paralelo,

para que se tenha uma id´eia do ganho real obtido na paraleliza¸c˜ao da ferramenta FOP, ´e es-

sencial que o tempo de I/O seja analisado. Para isso, mais alguns testes foram executados para

que fossem coletados os tempos de I/O em ambas as vers˜oes. Como era esperado, o tempo de

I/O foi muito parecido como mostrado na Tabela 5.3.

Arquivo PPML N´umero de Documentos Tempo(seg) seq

uencial Tempo(seg) paralelo

Mini 1000 40,36 39,83

CAP 2000 60,04 57,00

Appl 1000 57,00 53,00

Tabela 5.3: Tabela comparando o tempo de I/O entre as vers˜oes seq

uencial e paralela da ferra-

menta FOP

Portanto, se removermos o tempo gasto com I/O nos casos de testes realizados, veriﬁcamos

que o ganho real com o paralelismo ´e muito grande conforme mostrado nas a tabelas 5.4, 5.5,

e 5.6. Em todos os casos a eﬁciˆencia foi maior do que 75% chegando at´e a atingir 89,45% para

renderizar o PPML Appl de 1000 documentos com 7 processadores.

Sem tempo de I/O

CPU 1 4 5 6 7 8 9 10 11 12

Tempo(seg) 253,96 165,33 79,19 57,34 47,51 42,87 39,51 40,98 39,18 40,07

Eﬁciˆencia(%) 100,00 38,40 64,14 73,81 76,36 74,05 71,41 61,97 58,92 52,81

Com tempo de I/O

Tempo(seg) 293,96 204,51 118,19 96,34 86,51 81,87 78,51 79,98 78,18 79,07

Eﬁciˆencia(%) 100,00 35,94 49,74 50,85 48,54 44,88 41,60 36,75 34,18 30,98

Tabela 5.4: Comparativo de tempo e eﬁciˆencia de renderiza¸c˜ao Mini 1000 do cumentos com e

sem tempo de I/O

80 CAP

ITULO 5. ESTRAT

EGIAS DE ALTO DESEMPENHO

Sem tempo de I/O

CPU 1 4 5 6 7 8 9 10 11 12

Tempo(seg) 431,51 292,23 133,96 102,39 83,68 67,73 73,52 66,80 70,51 70,62

Eﬁciˆencia(%) 100,00 36,91 64,42 70,24 73,66 79,64 65,21 64,59 55,63 50,92

Com tempo de I/O

Tempo(seg) 491,51 349,23 194,96 161,39 142,35 129,73 133,52 135,80 131,51 131,62

Eﬁciˆencia(%) 100,00 35,18 50,42 50,76 49,32 47,36 40,90 36,19 33,98 31,12

Tabela 5.5: Comparativo de tempo e eﬁciˆencia de renderiza¸c˜ao CAP 2000 documentos com e

sem tempo de I/O

Sem tempo de I/O

CPU 1 4 5 6 7 8 9 10 11 12

Tempo(seg) 315,68 221,15 103,70 66,97 50,41 51,88 52,45 50,48 47,53 47,17

Eﬁciˆencia(%) 100,00 35,69 60,88 78,56 89,45 76,05 66,87 62,53 60,38 55,77

Com tempo de I/O

Tempo(seg) 372,68 274,15 157,70 121,97 108,41 105,88 106,45 103,48 101,37 101,88

Eﬁciˆencia(%) 100,00 33,98 47,26 50,92 49,11 44,00 38,90 36,01 33,42 30,48

Tabela 5.6: Comparativo de tempo e eﬁciˆencia de renderiza¸c˜ao Appl 1000 documentos com e

sem tempo de I/O

5.4.2 Buﬀers

Na Figura 5.7, que descreve a arquitetura da solu¸c˜ao de divis˜ao do consumidor PPML,

nota-se que entre o consumidor PPML e o Broker h´a um buﬀer de FOs . Tendo em vista

que um ´unico FO ´e um dado muito pequeno, o buﬀer foi criado para acumular um n´umero

signiﬁcativo de FOs a serem enviados para os m´odulos FOP de modo que justiﬁcasse o tempo

de comunica¸c˜ao gasto neste processo. Desta forma, o consumidor PPML varre o arquivo PPML

retirando os FOs e enviando-os para o buﬀer at´e que este atinja um tamanho especiﬁcado, sendo

ent˜ao enviado para a renderiza¸c˜ao. Nos testes realizados neste trabalho, o tamanho do buﬀer foi

ﬁxado em 64 KBytes. Este mesmo tamanho ´e assumido para o buﬀer de sa´ıda do broker para

o recebedor PPML que realoca os SVGs nas posi¸c˜oes corretas no PPML. Portanto, a varia¸c˜ao

deste buﬀer pode interferir diretamente nos tempos encontrados tanto para mais quanto para

menos.

5.4. AN

ALISE COMPLEMENTAR 81

Um m´ınimo de testes utilizando-se outros tamanhos de buﬀer (32KB e 128KB) foram reali-

zados. Contudo, estes testes serviram somente para identiﬁcar qual tamanho base em KBytes

seria utilizado em todos os testes. Como resultado, o tamanho de 64KB mostrou um desempe-

nho superior, mas nada pode-se aﬁrmar visto que foi um teste isolado, sem varia¸c˜ao do tamanho

dos documentos de entrada, entre outras poss´ıveis vari´aveis.

82 CAP

ITULO 5. ESTRAT

EGIAS DE ALTO DESEMPENHO

Cap´ıtulo 6

Considera¸c˜oes Finais

Com o ganho de aproximadamente 30% ap´os a execu¸c˜ao da primeira estrat´egia que foi

implementada simplesmente para validar uma id´eia sem nenhuma preocupa¸c˜ao com otimiza¸c˜ao

de c´odigo e demais t´ecnicas computacionais, j´a foi poss´ıvel concluir que o ganho de termos uma

vers˜ao paralela de renderiza¸c˜ao de documentos XSL-FO seria v´alido. Considerando-se que um

cliente de grande porte imprime milh˜oes de documentos para distribuir aos seus clientes e este

processo leva por volta de 24 horas, um ganho de 50% na eﬁciˆencia j´a reduziria em 12 horas o

tempo total de renderiza¸c˜ao. Isto ´e um ganho muito grande tratando-se de mercado. Alguns

resultados ainda est˜ao por ser obtidos. Novas alternativas ainda est˜ao por serem exploradas

como apresentado na Se¸c˜ao 6.1. Espera-se um ganho ainda maior ao executarmos a solu¸c˜ao

em uma m´aquina SMP . Todavia, acreditamos que a solu¸c˜ao j´a esteja validada e os resultados

futuros s˜ao ainda mais promissores.

Este trabalho rendeu uma publica¸c˜ao em uma conferˆencia internacional (SAC - Symposium

on Applied Computing), al´em da colabora¸c˜ao e reconhecimento do laborat´orio da HP em Bristol

que vem demonstrando cada vez mais interesse na utiliza¸c˜ao dos modelos apresentados neste

trabalho em um de seus produtos.

6.1 Trabalhos Futuros

Os resultados apresentados neste trabalho indicam que ainda ´e poss´ıvel se alcan¸car resulta-

dos melhores na renderiza¸c˜ao de documentos XSL-FO usando t´ecnicas computacionais de alto

desempenho. Na primeira implementa¸c˜ao foi usado threads e o paradigma de programa¸c˜ao por

troca de mensagens para diminuir o tempo de execu¸c˜ao de 350,05 para 93,30 segundos para

84 CAP

ITULO 6. CONSIDERA¸C

OES FINAIS

uma tarefa contendo mil documentos. Embora o ganho de desempenho possa ser considerado

satisfat´orio, a principal contribui¸c˜ao deste trabalho foi indicar a melhor conﬁgura¸c˜ao entre as

estudadas.

A primeira estrat´egia apresentada com um ´unico broker traz `a tona o problema de satura¸c˜ao

do m´odulo broker, que lida com o recebimento de FOs renderizados ao mesmo tempo que

veriﬁca m´odulos FOP ociosos os quais requisitam novos FOs a serem processados. Baseado em

tal fato, uma segunda estrat´egia foi implementada contendo m´ultiplos m´odulos brokers que n˜ao

apresentou, num primeiro momento, os resultados esperados. Por´em, com a adi¸c˜ao de um buﬀer

no broker permitindo o envio n˜ao somente de um ´unico FO para ser renderizado, mas v´arios ao

mesmo tempo, foi obtido mais um ganho de desempenho conforme apresentado nos resultados

no Cap´ıtulo 5, Se¸c˜ao 5.2.2.

Entretanto, sabe-se que em ambas alternativas o arquivo PPML de sa´ıda ´e gerado em me-

m´oria at´e que seja inteiramente ﬁnalizado quando ´e descarregado para o ambiente f´ısico. Al´em

da limita¸c˜ao de tamanho que pode ser encontrada em testes futuros, j´a que, por exemplo, um

PPML com dois mil documentos pode em casos somente com FOs simples gerar um arquivo

de sa´ıda em torno de 23MB, existe o problema da ordena¸c˜ao dos FOs que deve ser mantida

conforme no PPML original.

Considerando todos os casos nesta linha potencial de pesquisa, como trabalhos futuros temos

alguns pontos interessantes que podemos destacar. Para solucionar o problema mencionado

acima da gera¸c˜ao do arquivo de sa´ıda, o uso de DOM (Document Object Model) [DOM05] pode

ser melhor investigado a ﬁm de que o documento seja montado dinamicamente `a medida em que

os FOs renderizados s˜ao enviados dos m´odulos FOP para o consumidor PPML. Fora isso, nessa

primeira vers˜ao implementada tanto os brokers quanto os m´odulos FOP foram implementados

utilizando-se de primitivas MPI s´ıncronas. Com isso, o recebedor PPML caso n˜ao esteja pronto

para receber um FO renderizado faz com que o m´odulo FOP ﬁque trancado no envio at´e que

o mesmo esteja pronto para o recebimento. Neste caso, primitivas ass´ıncronas podem utilizadas

de mode que os m´odulos FOP n˜ao ﬁquem trancados caso tal situa¸c˜ao ocorra.

Balanceamento de carga ´e uma outra p ossibilidade a ser pesquisada. Nos exemplos de ar-

quivos PPML utilizados neste trabalho optou-se por utilizar FOs de mesmo tamanho, j´a que

o objetivo era obter um volume signiﬁcativo de documentos e n˜ao complexidade. Entretanto, ´e

bastante comum termos diferentes tipos de FOs com diferentes complexidades em documentos

PPML os quais conseq

uentemente exigem um tempo maior ou menor de renderiza¸c˜ao. Tal

6.1. TRABALHOS FUTUROS 85

fato possibilita que em implementa¸c˜oes futuras seja p oss´ıvel dimensionar o tamanho de um FO

atrav´es de seu tipo de modo que seja poss´ıvel enviar os maiores FOs para os processadores de

maior capacidade balanceando, assim, o processamento.

Somando-se ainda a essas alternativas, o dimensionamento correto do buﬀer surge como

mais uma estrat´egia a ser explorada. A solu¸c˜ao com m´ultiplos brokers apresentada na Se¸c˜ao 5.2

considera um buﬀer cujo tamanho foi ﬁxado em 64KB. Contudo, este valor n˜ao foi deﬁnido de

forma estat´ıstica, pois no momento o que se buscava era a validade da solu¸c˜ao e se haveria ganho

de desempenho em rela¸c˜ao `as demais estrat´egias. Logo, testes com buﬀers de maior tamanho

devem ser executados para que se possa ter uma rela¸c˜ao entre ganho de desempenho e tamanho

do buﬀer e, por conseguinte, eleger a melhor op¸c˜ao baseada em resultados.

Experimentos em plataformas multi-processadas (SMP) para as quais a implementa¸c˜ao teria

que sofrer algumas adapta¸c˜oes, por´em a estrat´egia ´e idˆentica.

O m´odulo FOP tratado n˜ao como uma caixa-preta ´e uma id´eia a longo prazo, por´em n˜ao

descartada. Ap´os todos os experimentos realizados nos trabalhos aqui mencionados, dependendo

da resposta obtida em um ambiente real de impress˜ao talvez n˜ao seja necess´ario tal modiﬁca¸c˜ao.

Entretanto, uma vers˜ao preparada para uso de threads (thread safe) do FOP j´a est´a pronta para

ser utilizada. FOP em sua vers˜ao liberada atualmente usa vari´aveis est´aticas para conﬁgura¸c˜ao

de dados e leitura de imagens. Entretanto, uma vers˜ao n˜ao disponibilizada j´a contorna esses

problemas e ser´a a base para o desenvolvimento de uma vers˜ao paralela futuramente.

86 CAP

ITULO 6. CONSIDERA¸C

OES FINAIS

Referˆencias Bibliogr´aﬁcas

[AG94] G.S. Almasi and A. Gottlieb. Highly parallel computing, 2a. ed. The Benjamin

Cummings Publishing Company, Inc., 1994.

[Bar05] B.M. Barney. MPI performance topics. Extracted from

http://www.llnl.gov/computing/tutorials/mpi/ at Nov 19th, 2005.

[Ble94] R.A Blech. An overview of parallel processing. Extracted from

http://www.lerc.nasa.gov/othergroups/IFMD/2620/tutorialPP.html at Oct 20th,

1994. Slides presented at the Parallel Computing with PVM Workshop.

[Bos00] D. D. Bosschere. Book ticket ﬁles & imposition templates for variable data printing

fundamentals for PPML. In Proceedings of the XML Europe 2000, Paris, France,

2000. International Digital Enterprise Alliance.

[DdB00] P. Davis and D. de Bronkart. PPML (Personalized Print Markup Language). In

Proceedings of the XML Europe 2000, Paris, France, 2000. International Digital

Enterprise Alliance.

[DOM05] DOM. Document Object Model. Extracted from http://www.w3.org/DOM/ at Jan

19th, 2005.

[Dun90] R. Duncan. A survey of parallel computer architectures. IEEE Computer, pages

5–16, 1990.

[FGZea06] L.G. Fernandes, F. Giannetti, R.T. Zambon, and et al. High p erformance XSL-FO

rendering for variable data printing. In ACM Symposium on Applied Computing

(SAC), Dijon, France, 2006. Artigo aceito.

88 REFER

ENCIAS BIBLIOGR

AFICAS

[Fly72] M.J. Flynn. Some computer organizations and their eﬀectiveness. IEEE Transac-

tions on Computers, C(21):pp.948–960, 1972.

[FOP05] FOP. Formatting Objects Processor. Extracted from http://xml.apache.org/fop at

May 13th, 2005.

[GHM98] V. Getov, S.F. Hummel, and S. Mintchev. High-performance parallel programming

in Java: exploiting native libraries. Concurrency: Practice and Experience, 10(11–

13):863–872, 1998.

[GM02] R. Glushko and T. McGrath. Document Engineering for e-Business. In ACM

Symposium on Document Engineering, 2002.

[HB84] K. Hwang and F.A. Briggs. Computer architecture and parallel processing. McGraw-

Hill International Editions, 1984.

[Hwa93] K. Hwang. Advanced computer architecture - parallelism, scalability, programmabi-

lity. McGraw-Hill International Edition, 1993.

[KB88] A.H. Karp and R.G. Babb. A comparison of 12 parallel Fortran dialects. IEEE

Software, 5(5):52–67, 1988.

[KL88] B. Kruatrachue and T. Lewis. Grain size determination for parallel processing.

IEEE Software, 5(1):23–32, 1988.

[MMG

00] J. Moreira, S. Midkiﬀ, M. Gupta, P. Artigas, M. Snir, and R. Lawrence. Java

programming for high performance numerical computing. IBM Systems Journal,

39(1):21–56, 2000.

[MMM

04] F. Meneguzzi, L. Meirelles, F. Mano, J. Oliveira, and A. Silva. Strategies for docu-

ment optimization in digital publishing. In ACM Symposium on Document Engi-

neering, pages 163–170, Milwaukee, USA, 2004. ACM Press.

[mpi05] mpiJava. The mpiJava home page. Extracted from

http://www.hpjava.org/mpiJava.html at May 13th, 2005.

[NBvO01] P. Navaux, M. Barreto, R.

Avila, and F. Oliveira. ERAD - Escola Regional de Alto

Desempenho, chapter Execu¸c˜ao de aplica¸c˜oes em ambientes concorrentes, pages 2–9.

2001.

REFER

ENCIAS BIBLIOGR

AFICAS 89

[PHOF03] L. Purvis, S. Harrington, B. O’Sullivan, and E. C. Freuder. Creating personalized

documents: an optimization approach. In ACM Symposium on Document Engine-

ering, pages 68–77, Grenoble, France, 2003. ACM Press.

[POD05] PODi. Print on Demand Initiative. Extracted from http://www.podi.org at May

13th, 2005.

[Qui94] M. Quinn. Parallel computing: theory and practice. McGraw-Hill, 1994.

[RGM99] J. Tenenbaum R. Glushko and B. Meltzer. An XML framework for agent-based

e-commerce. Communications of the ACM, 42(3):106–114, 1999.

[SOHL

96] M. Snir, S. Otto, S. Huss-Lederman, D. Walker, and J. Dongarra. MPI: the complete

reference. MIT Press, 1996.

[W3C] W3C. The World Wide Web Consortium. Extracted from http://www.w3.org/ at

May 13th.

[XT05] XSL-T. XSL-Transformations. Extracted from

http://www.w3.org/TR/1999/REC-xslt-19991116 at May 13th, 2005.

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
 
 