CLEVERSON AFONSO BOFFCLEVERTON APARECIDO KRENSKI

JULIANO LORENZET

MODELAGEM DE FLUXOS DE TRABALHO UTILIZANDOHIPERGRAFOS DIRECIONADOS

CURITIBA

2009

CLEVERSON AFONSO BOFFCLEVERTON APARECIDO KRENSKI

JULIANO LORENZET

MODELAGEM DE FLUXOS DE TRABALHO UTILIZANDOHIPERGRAFOS DIRECIONADOS

Trabalho de Conclusao de Curso apresentado abanca examinadora da Universidade Federal doParana, como exigencia para obtencao do tıtulode Bacharel em Ciencia da Computacao.

Orientador: Prof. Dr. Andre Luiz Pires Gue-des

CURITIBA

2009

Sumario

Lista de Figuras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v

Resumo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii

Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii

1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

2 Fluxo de Tarefas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.1 Paralelismo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

3 Conceitos e Fundamentacao Teorica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3.1 Hipergrafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3.2 Hipergrafo Direcionado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3.3 Hiper-Caminho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

3.4 Conexao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3.5 Propriedades sobre conjuntos de hiper-arcos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3.5.1 Propriedade B. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3.5.2 Propriedade F . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3.5.3 Propriedade S . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3.5.4 Ciclos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

ii

iii

3.6 HSPD - Hipergrafos Serial-Paralelo-Disjuncao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3.7 Modelagem de fluxos de tarefas com Hipergrafos Direcionados . . . . . . . . . . . . . . . 12

3.8 Informacoes pre-existentes na estrutura de dados . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.8.1 OU-F-Condicao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3.8.2 OU-B-Condicao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3.8.3 E-F-Condicao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.8.4 E-B-Condicao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.9 Detalhamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.10 Trechos de execucao opcionais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

4 Definicoes Adotadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

5 Execucao do fluxo sobre Hipergrafos Direcionados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

5.1 Um algoritmo para execucao de fluxo de tarefas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

5.1.1 Funcao Execucao (Principal) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

5.1.2 Funcao realizaTrabalho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

5.1.3 Funcao verificaDependencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

6 Paralelismo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

6.1 Grau de paralelismo da execucao em um instante t . . . . . . . . . . . . . . . . . . . . . . . . . . 28

6.2 Grau de paralelismo maximo em um instante t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

6.3 Grau de paralelismo maximo do hipergrafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

6.4 Grau maximo medio de paralelismo do hipergrafo . . . . . . . . . . . . . . . . . . . . . . . . . . 30

7 Algoritmos para Calculo do Maior Paralelismo em Hipergrafos Direcionados . . . . 31

iv

7.1 Algoritmo A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

7.1.1 Consideracoes iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

7.1.2 Funcionamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

7.1.3 Pseudocodigo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

7.2 Algoritmo B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

7.2.1 Consideracoes iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

7.2.2 Funcionamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

7.2.3 Pseudocodigo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

8 Conclusao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

Referencias Bibliograficas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

Anexo A -- Algoritmo (A) para calculo do maior paralelismo . . . . . . . . . . . . . . . . . . . . . . . . 51

Anexo B -- Algoritmo (B) para calculo do maior paralelismo . . . . . . . . . . . . . . . . . . . . . . . . 58

Anexo C -- Estrutura de Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

Lista de Figuras

Figura 1.1 Um exemplo de workflow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

Figura 3.1 Hipergrafo Direcionado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

Figura 3.2 Hiper-caminho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

Figura 3.3 Fluxo de controle modelado atraves de um Hipergrafo Direcionado . . . . . . . . 11

Figura 3.4 Um exemplo de fluxo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

Figura 3.5 Um exemplo de OU-F-Condicao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

Figura 3.6 Um exemplo de OU-B-Condicao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

Figura 3.7 Um exemplo de E-F-Condicao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

Figura 3.8 Um exemplo de E-B-Condicao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

Figura 3.9 Um hipergrafo direcionado incompatıvel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

Figura 3.10 Um exemplo de modelagem de fluxo com trecho de execucao opcional . . . . . 19

Figura 6.1 Um Hipergrafo Direcionado com trechos de execucao paralela . . . . . . . . . . . . 27

Figura 6.2 Destaque das tarefas que podem ser executadas paralelamente . . . . . . . . . . . . . 27

Figura 6.3 Calculo do grau de paralelismo em cada instante da execucao . . . . . . . . . . . . . 29

Figura 6.4 Grau medio de paralelismo do hipergrafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

Figura 7.1 Hipergrafo Direcionado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

v

vi

Figura 7.2 Fluxo de Tarefas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

Figura 7.3 Um exemplo de lista de tempos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

Figura 7.4 Criacao dos itens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

Resumo

Este trabalho tem como objetivo estudar a modelagem de problemas relacionados a fluxos de

atividades atraves de hipergrafos direcionados. Realizando alguns calculos e tirando proveito

das vantagens deste modelo de representacao, buscamos otimizar os recursos disponıveis, en-

contrando no hipergrafo direcionado possıveis tarefas que podem ser realizadas simultanea-

mente. Assim, conseguimos determinar o numero maximo de execucoes paralelas em um de-

terminado fluxo de atividades.

Palavras chave: Hipergrafos, Fluxo, Paralelismo, Fluxo de Atividades.

vii

Abstract

This paper’s goal is to study the modeling of problems related to workflows through directed

hypergraphs. Performing some calculations and taking advantages of this representation model,

we sought to optimize the availables resources, finding on directed hypergraph possible tasks

that could be simultaneously performed. Therefore, we could determine the maximum number

of parallels executions in a determined workflow.

Keywords: Hypergraphs, flow, parallelism, workflow.

viii

1

1 Introducao

E muito comum nos depararmos com determinadas situacoes onde eventos devem

acontecer obedecendo a uma certa ordem, pois existe uma relacao de dependencia a aconte-

cimentos anteriores. Este conjunto de eventos nada mais e do que um fluxo de tarefas, que pode

ser modelado de diversas formas.

Neste trabalho sera apresentado um estudo sobre a modelagem de problemas relaci-

onados a fluxos de atividades atraves de hipergrafos direcionados. Com a analise desta estru-

tura, busca-se determinar o numero maximo de execucoes paralelas em um determinado fluxo,

numero esse utilizado para auxiliar em um melhor dimensionamento dos recursos disponıveis.

Temos como exemplo os processos de negocios, em que algo ou alguem executa um

trabalho que e pre-requisito para o inıcio de algum outro trabalho, ou seja, a execucao e termino

de determinada tarefa permite o inıcio de uma ou mais tarefas seguintes. Uma possıvel situacao

para este exemplo seria em construcao civil. Nas construcoes, as paredes so podem ser ergui-

das depois que o alicerce foi construıdo, a estrutura do telhado so pode ser iniciada depois das

paredes terem sido erguidas, e assim por diante. Na computacao tambem existe esta relacao de

dependencia, pois determinadas instrucoes ou procedimentos devem ser executados em deter-

minada ordem para que o resultado apresentado seja correto. Nos casos apresentados acima,

alem de muitos outros que se encaixam neste perfil de problema, e necessario que as tarefas

sejam executadas no menor tempo possıvel.

Poderıamos pensar entao em executar cada tarefa do conjunto separadamente e parale-

lamente, visando um melhor desempenho, ou mesmo a minimizacao do custo e otimizacao de

tempo e recursos. Mas nem sempre isso e tao simples, pois podem existir dependencias entre

2

determinadas tarefas, o que significa que tarefas que dependam de resultados ou dados gerados

por outras tarefas so podem ser executadas depois que as tarefas responsaveis por gerar os dados

ou os resultados tenham sido finalizadas.

Para representar este fluxo de tarefas e as dependencias entre elas podemos usar um

diagrama de modo a facilitar a visualizacao do problema.

O exemplo abaixo representa um fluxo de tarefas onde cada tarefa e representada por

um cırculo e as setas representam as dependencias.

Figura 1.1: Um exemplo de workflow

Nesta figura esta representado um exemplo de sequencia de passos para lavagem de

roupas. Primeiramente as roupas sao lavadas e posteriormente centrifugadas para acelerar o

processo de secagem, que e feito logo em seguida. Quando o processo de secagem termina as

roupas sao entao passadas e finalmente guardadas.

Em alguns casos, nao temos um fluxo tao linear como o exemplo acima, no qual podem

3

existir tarefas simultaneas ou tomadas de decisoes que resultam em tarefas excludentes, ou seja,

momentos nos quais uma tarefa deve ser executada juntamente com outra ou em outros casos,

deve ser tomada uma decisao que escolhera apenas uma tarefa para execucao. Com isso caımos

em condicoes E e condicoes OU, respectivamente, que discutiremos no momento apropriado.

Computacionalmente, podemos utilizar um hipergrafo direcionado, definido mais adi-

ante, para modelar um fluxo como o do exemplo, ou um fluxo mais complexo contendo condicoes

E e OU. No hipergrafo direcionado cada tarefa e representada por um vertice e os hiper-arcos

representam as dependencias[STIVANIN, 2006].

Para que os recursos sejam utilizados da melhor forma e auxiliem na melhoria do

desempenho do processo, e necessario algum tipo de analise, pois caso contrario, e possıvel que

se aumente o desperdıcio em decorrencia da sobrecarga de alguns componentes.

A otimizacao do tempo e dos recursos disponıveis de modo que permanecam ociosos

pelo menor tempo possıvel auxilia na diminuicao dos custos e em contrapartida aumenta a

produtividade.

Encontrar o maior grau de paralelismo com o intuito de otimizar os recursos e acelerar

a resolucao dos problemas e o nosso objeto de estudo.

4

2 Fluxo de Tarefas

Fluxo de tarefas e uma sequencia de passos necessarios para que se possa atingir um

objetivo, de acordo com um conjunto de regras definidas, envolvendo a nocao de processos e

permitindo que estes possam ser transmitidos de uma entidade para outra obedecendo a algumas

regras.

Um processo de work f low, fluxo de trabalho ou de tarefas pode ser entendido como

um conjunto de atividades interligadas por transicoes, que deve ser executado em uma or-

dem de tal forma que alcance um objetivo. Assim podemos ter diversos processos, tais como:

solicitacao de servicos, reserva de recursos, prestacao de contas.

Podemos representar um fluxo de tarefas atraves de fluxogramas, que e um tipo de

diagrama que pode ser entendido como uma representacao esquematica de um processo, mui-

tas vezes construıdo atraves de graficos que ilustram de forma descomplicada a transicao de

informacoes entre os elementos que o compoem [SERRALHEIRO, 2008]. Podemos entender

os fluxogramas na pratica, como a documentacao dos passos necessarios para a execucao de um

processo qualquer. O fluxograma e uma das Sete Ferramentas da Qualidade, muito utilizada em

fabricas e industrias para a organizacao de produtos e processos.

Assim, alguns conceitos basicos envolvendo o fluxograma podem ser definidos:

• Processo: e o mapeamento do fluxo;

• Atividades, tarefas, trabalhos: sao procedimentos a serem executados;

• Transicoes: sao elementos de ligacao entre as atividades que determinam o caminho que

5

o fluxo seguira; [PARANA, 2008]

Temos tambem o conceito de instancias. Sempre que o fluxo for iniciado, uma instancia de

execucao sera gerada. As instancias representam as ocorrencias de execucao de um processo. A

execucao percorrera um determinado caminho no fluxo ate chegar na atividade final, o objetivo

da execucao do fluxo [PARANA, 2008].

2.1 Paralelismo

A execucao simultanea de tarefas pode ser a solucao para muitos problemas de otimizacao

em que deseja-se ganhar tempo realizando varias tarefas o mais rapido possıvel. Quando dispo-

mos de mais de um recurso, podendo ser esse recurso, mao de obra, processadores, maquinas

ou qualquer entidade que possa realizar uma tarefa, podemos ter execucoes paralelas.

Alem da diminuicao do tempo total de realizacao de uma sequencia de atividades,

o paralelismo permite que separemos o problema em varios pedacos, onde varias entidades

possam executar o trabalho simultaneamente. Ao final, juntamos os resultados de cada pedaco

e temos o resultado geral do problema. Por outro lado, criamos novos desafios e problemas que

as vezes sao tao complexos quanto os problemas originais [ROBERTO, 2008].

Para mapearmos um problema ou um processo qualquer que envolva execucoes para-

lelas, devemos observar que ao utilizarmos o paralelismo, temos a necessidade que as respostas

e as trocas de informacoes acontecam de forma correta [ROBERTO, 2008] e alem disso te-

mos que garantir que todas as dependencias estao satisfeitas e principalmente que as tarefas

executadas paralelamente nao dependam umas das outras.

Quando temos processos e fluxos de trabalho que possibilitam a execucao paralela de

tarefas, as vezes nao dispomos de recursos suficientes para tal, como por exemplo, em uma em-

presa em que um determinado processo, cinco tarefas podem perfeitamente serem executadas

em paralelo, mas a empresa dispoe de apenas tres funcionarios para a equipe responsavel pelo

processo. Neste caso, duas tarefas que poderiam ser executadas em conjunto, economizando

6

tempo, ficam pendentes, esperando o termino de alguma, por falta de mao de obra. Este pro-

blema ocorre frequentemente, pois o gestor responsavel pela gerencia dos recursos nao soube,

ou nao teve, como dimensionar sua equipe ou a quantidade de maquinas para a realizacao das

atividades. Em muitos casos, nao e possıvel o dimensionamento dos recursos, simplesmente

porque o gestor nao sabe quantas tarefas podem ser executadas paralelamente em determinado

fluxo de atividades. Tal resposta, que pode ser simples em fluxos pequenos, pode ser bastante

complexa em fluxos grandes. Uma ferramenta que faz justamente o calculo de quantas ativida-

des podem ser executadas paralelemante em um fluxo sera discutida mais adiante.

7

3 Conceitos e Fundamentacao Teorica

3.1 Hipergrafo

Um Hipergrafo e uma generalizacao de um grafo. Um grafo e um par ordenado de

conjuntos finitos (V,E) tal que E ⊆ C2V onde V e um conjunto de vertices e E e um conjunto

de arestas [DONADELLI, 2008]. O hipergrafo, por sua vez, e um par ordenado de conjuntos

finitos (V,E), porem temos E ⊆ 2V onde V e um conjunto de vertices e E e um conjunto de

hiper-arcos tal que a cardinalidade do hiper-arco pode ser diferente de 2 [GUEDES, 2001].

3.2 Hipergrafo Direcionado

Um hipergrafo direcionado H = (V,E) e uma dupla, onde V e um conjunto finito de

vertices e E e um conjunto de hiper-arcos. Um hiper-arco e pertencente a E e um par ordenado

(X ,Y ) tais que X e Y sao subconjuntos disjuntos de V . Dado um hipergrafo direcionado H =

(V,E), e um hiper-arco e = (X ,Y ) pertencente a E, chamamos X de origem e Y de destino,

respectivamente denotamos por Org(e) e Dest(e). Podemos usar esta notacao tambem para

conjuntos de hiper-arcos. Assim, se A e um conjunto de hiper-arcos, entao:

Org(A) = ∪e∈A Org(e);

Dest(A) =∪e∈A Dest(e). Tambem podemos definir os conjuntos que representam as relacoes de

incidencia em um hipergrafo direcionado, que sao BS(v) e FS(v), chamados de hiper-arcos de

entrada e hiper-arcos de saıda de v, respectivamente, onde v ∈V de um hipergrafo direcionado

H = (V,E). As letras B e F representam as expressoes backward e forward, respectivamente.

BS(v) = {e|v ∈ Dest(e)} (Entrada);

8

FS(v) = {e|v ∈ Org(e)} (Saıda); [GUEDES, 2001]

Na figura 3.1 podemos ver o hipergrafo direcionado H =(V,E), onde V = {1,2,3,4,5,6,7},

e E = {a,b,c,d,e}. Como exemplo de hiper-arco temos a = ({1,2},{4,5}).

Figura 3.1: Hipergrafo Direcionado

3.3 Hiper-Caminho

Dado um Hipergrafo direcionado H = (V,E), e dois vertices s e t, um hiper-caminho

de s a t, de tamanho k, e uma sequencia de hiper-arcos C = (ei1,ei2, ...,eik) onde s pertence a

Org(ei1) e t pertence a Dest(eik), e para cada hiper-arco eip de C com 1≤ p≤ k temos que:

Org(eip)∩ (Dest(ei1,ei2, ...,eip−1)∪{s}) 6= {};

Dest(eip)∩ (Org({eip+1,eip+2, ...,eik})∪{t}) 6= {}.

Onde Org(ei1) e Dest(eik) sao Org(C) e Dest(C), respectivamente [GUEDES, 2001].

Na figura 3.2 podemos ver um exemplo de hiper-caminho no hipergrafo da figura 3.1.

O hiper-caminho C = {a,c,d}, de 1 a 7, tem origem {1,2} e destino {7}.

9

Figura 3.2: Hiper-caminho

3.4 Conexao

Dizemos que um vertice x esta hiper-conectado ou simplesmente conectado ao vertice

y se existe um hiper-caminho de x a y.

3.5 Propriedades sobre conjuntos de hiper-arcos

3.5.1 Propriedade B

Seja C um conjunto de hiper-arcos, um hiper-caminho de C, de s a t, de tamanho k,

tem a propriedade B se, para cada hiper-arco eip de C, com 1 ≤ p ≤ k, temos que: Org(eip) ⊆

(Dest({ei1,ei2, ...,eip−1})∪{s}) [GUEDES, 2001].

Um hiper-caminho com esta propriedade e um B-caminho.

3.5.2 Propriedade F

Um hiper-caminho de C, de s a t, de tamanho k, tem a propriedade F se, para cada

hiper-arco eip de C, com 1 ≤ p ≤ k, temos que: Dest(eip) ⊆ (Org({eip+1,eip+2,...,eik}) ∪ {t})

[GUEDES, 2001].

Um hiper-caminho com esta propriedade e um F-caminho.

10

3.5.3 Propriedade S

Seja Hc o hipergrafo direcionado induzido por C. O conjunto C tera a propriedade S se,

para todo vertice x de Hc, |FS(x)| ≤ 1 e |BS(x)| ≤ 1, ou seja, cada vertice aparece no maximo

em um conjunto origem e um conjunto destino de C. Assim podemos definir um outro tipo de

hiper-caminho [GUEDES, 2001].

Um hiper-caminho com esta propriedade e um S-caminho.

A letra S utilizada aqui representa a expressao star.

Um hipergrafo pode conter as tres propriedades simultaneamente B, F e S. E este tipo

de hiper-caminho que sera utilizado.

3.5.4 Ciclos

Um ciclo e um hiper-caminho C onde Org(C)∩Dest(C) 6= {} [GUEDES, 2001].

3.6 HSPD - Hipergrafos Serial-Paralelo-Disjuncao

Da mesma maneira como os fluxos de tarefas sequenciais podem ser modelados utilizando-

se dos grafos direcionados, como na figura 1.1, seria interessante que problemas que contenham

paralelismo tambem pudessem ser modelados. Para isso utilizamos os Hipergrafos Direciona-

dos. Para apresentar os problemas que possuem paralelismos de uma maneira estruturada po-

demos utilizar a classe dos Hipergrafos Serial-Paralelo-Disjuncao (HSPD), que sera definida a

seguir.

Um hipergrafo de controle Hp = (V,E,s, t) associado a um programa paralelo P e uma

quadrupla onde (V,E) e um hipergrafo direcionado, s ∈ V e o vertice origem, em que neste hi-

pergrafo existe um B-caminho de s para qualquer outro vertice em V , e um vertice t pertencente

a V , onde:

1. cada instrucao (ou conjunto de instrucoes elementar) de P e um vertice de V ;

11

2. cada dependencia de execucao entre instrucoes de P e um hiper-arco de E;

3. s e o vertice inıcio e t o vertice final. [GUEDES, 2001]

Abaixo temos um hipergrafo direcionado que modela o seguinte fluxo de controle:

int a = 0, b = 0; (P1)

if (a < 10){ (P2)

a++; (P3)

b–; (P4)

}

else{ (P5)

a–; (P6)

b++; (P7)

}

Figura 3.3: Fluxo de controle modelado atraves de um Hipergrafo Direcionado

Com base na figura 3.3 acima podemos descrever como ocorre a execucao do fluxo

sobre o hipergrafo apresentado. A execucao inicia-se pelo passo 1 (P1). Quando a execucao

chega em P2 uma decisao deve ser tomada. Executam-se, entao, os passos 3 e 4 OU os passos 6

e 7. Se a condicao do passo 2 for satisfeita entao, P3 e P4 devem ser executados, e esta execucao

pode ser feita em paralelo, pois uma nao depende da outra. Caso a condicao seja falsa, entao,

os passos 6 e 7 devem ser executados. Note que a condicao em P2 gera um OU-Exclusivo, se

P3 e P4 forem executados, P5 nao sera executada, e vice-versa.

12

Finalmente podemos definir os hipergrafos Serial-Paralelo-Disjuncao. Esta famılia de

hipergrafos se faz bastante util para representarmos fluxos de controle de programas escritos em

linguagens que suportam estruturas do tipo if-then-else, case, while, etc.

Um hipergrafo Serial-Paralelo-Disjuncao (HSPD) H = (V,E,s, t) e um hipergrafo di-

recionado e os dois vertices, s e t, satisfazem uma das condicoes abaixo:

• Trivial: V = s.E = 0 e t = s.

• Serial: V = V1 ∪ V2, E = E1 ∪ E2 ∪ {({t1},{s2})}, s = s1 e t = t2, onde H1 = (V1, E1, s1,

t1) e H2 = (V2, E2, s2, t2) sao HSPDs (nao necessariamente distintos).

• Paralelo: V = ∪ki=1Vi ∪

{s, t},E = ∪ki=1Ei∪ {({s},{s1,...,sk}), ({t1,...,tk},{t})}, onde Hi = (V,Ei, si, ti). com i =

1...k, sao HSPDs distintos, e s e t sao vertices novos.

• Disjuncao: V = ∪ki=1Vi

∪ {s,t}, E = ∪ki=1

(Ei ∪{({s},{Si}),({ti},{t})}), onde Hi = (vi, Ei, si, ti), com i = 1...k, sao HSPDs distintos,

e s e t sao vertices novos.

Em todas estas condicoes, quando os HSPDs Hi forem distintos tambem devem ser disjuntos

[GUEDES, 2001].

3.7 Modelagem de fluxos de tarefas com Hipergrafos Direci-onados

O objeto de estudo deste trabalho e a modelagem de um fluxo de atividades ou tarefas,

atraves de um hipergrafo direcionado no qual os vertices representam as atividades [STIVANIN,

2006] e os hiper-arcos representam dependencias e tarefas que precisam ser cumpridas para

que as atividades sejam concluıdas; Cada atividade possui caracterısticas proprias como por

exemplo, o tempo para ser executada.

13

Figura 3.4: Um exemplo de fluxo

No exemplo da figura 3.4, as tarefas sao representadas pelos vertices e sao nomeadas de

“A”ate “K”. Para cada tarefa existem hiper-arcos que saem e que chegam aos vertices. Os hiper-

arcos que saem indicam as proximas tarefas que necessitam ser realizadas apos a conclusao da

tarefa atual. Os que chegam indicam dependencias para o inıcio da realizacao da nova tarefa

gerada.

3.8 Informacoes pre-existentes na estrutura de dados

Com os hipergrafos direcionados, e possıvel modelar e visualizar no nıvel de estrutura

de dados, uma serie de informacoes relevantes sem a necessidade de anexos, como variaveis

auxiliares que nao pertencem a estrutura basica. Assim e possıvel visualizar e modelar com

facilidade as dependencias entre as tarefas. Podemos descrever e obter varios tipos de condicoes

e dependencias atraves da estrutura basica do hipergrafo-direcionado, sendo possıvel verifcar

14

as condicoes definidas adiante:

3.8.1 OU-F-Condicao

Sejam u, v e w vertices distintos de um hipergrafo, e E1,E2,...,En conjuntos distintos

de hiper-arcos que partem de u, formando hiper-caminhos entre u e v e entre u e w. Assim,

podemos definir uma OU-F-Condicao como sendo duas ou mais sequencias de hiper-arcos dis-

tintas que ligam os dois extremos de um hiper-caminho, porem somente um dos hiper-caminhos

possıveis precisa ser percorrido para que uma determinada condicao seja satisfeita. Tendo

u como o extremo inicial v e w como opcoes de destino, sendo que somente um dos hiper-

caminhos deve ser tomado. Por questoes de nomenclatura chamaremos de OU-F-Condicao,

mas o mais correto seria XOR-F-Condicao, por se tratar de um OU exclusivo.

Figura 3.5: Um exemplo de OU-F-Condicao

3.8.2 OU-B-Condicao

Sejam u, v e w vertices distintos de um hipergrafo, e E1,E2,...,En conjuntos distintos

de hiper-arcos que chegam em u, formando hiper-caminhos entre v e u e entre w e u. Assim,

podemos definir uma OU-B-Condicao como sendo duas ou mais sequencias de hiper-arcos dis-

tintas que ligam os dois extremos de um hiper-caminho, porem somente um dos hiper-caminhos

possıveis precisa ser percorrido para que uma determinada condicao seja satisfeita. Tendo v e

w como extremo inicial u como destino, sendo que somente um dos hiper-caminhos deve ser

tomado. Por questoes de nomenclatura chamaremos de OU-B-Condicao, mas o mais correto

seria XOR-B-Condicao, por se tratar de um OU exclusivo.

15

Figura 3.6: Um exemplo de OU-B-Condicao

3.8.3 E-F-Condicao

Sejam u, v e w vertices distintos de um hipergrafo, e E1,E2,...,En conjuntos distintos

de hiper-arcos que partem de u, formando hiper-caminhos entre u e v e entre u e w. Assim, po-

demos definir uma E-F-Condicao como sendo duas ou mais sequencias de hiper-arcos distintas

que ligam os dois extremos de um hiper-caminho, sendo que todos os hiper-caminhos possıveis

precisam ser percorridos para que uma determinada condicao seja satisfeita. Considerando u

como o extremo inicial v e w como destinos. Obrigatoriamente todos os hiper-caminhos que sa-

tisfazem a E-F-Condicao precisam ser percorridos para que v e w sejam alcancados e visitados.

Figura 3.7: Um exemplo de E-F-Condicao

3.8.4 E-B-Condicao

Sejam u, v e w vertices distintos de um hipergrafo, e E1,E2,...,En conjuntos distintos de

hiper-arcos que chegam em u, formando hiper-caminhos entre v e u e entre w e u. Assim, po-

demos definir uma E-B-Condicao como sendo duas ou mais sequencias de hiper-arcos distintas

que ligam os dois extremos de um hiper-caminho, sendo que todos os hiper-caminhos possıveis

precisam ser percorridos para que uma determinada condicao seja satisfeita. Considerando v

16

e w como o extremo inicial e u como destino. Obrigatoriamente todos os hiper-caminhos que

satisfazem a E-B-Condicao precisam ser percorridos para que u seja alcancado e visitado.

Figura 3.8: Um exemplo de E-B-Condicao

3.9 Detalhamento

Voltando ao exemplo da figura 3.4. O ponto de inıcio da execucao do fluxo e a tarefa

nomeada por “A”. “A” nao tem pai, portanto, e a tarefa inicial.

Proposicao: Seja o vertice v, se BS(v) = {}, entao v e o vertice inicial do fluxo.

Dizemos que o fluxo F e inicializavel, se para todo vertice v pertencente a F , existe

somente um vertice v, onde BS(v) = {}. Se existir mais de um vertice que satisfaca esta condicao

(BS(v) = {}), entao o fluxo e denotado multi-inicializavel. Se nao existir nenhum vertice tal que

BS(v) = {}, o fluxo e denominado nao-inicializavel.

Imediatamente apos a conclusao da Tarefa “A”, e gerada a Tarefa “B” (utilizaremos o

verbo “gerar” para indicar que uma tarefa pode e deve ser executada). Neste momento inicia-se

a execucao de “B”, verificando-se ao mesmo tempo se as dependencias de “B” foram atendidas,

neste caso a execucao da Tarefa “B”. Cada tarefa necessita de um tempo para ser executada e

apos o seu termino novas tarefas sao iniciadas e geradas. Concluindo-se a Tarefa “B”, inicia-se a

tarefa subsequente, no exemplo a Tarefa “C”. Ao termino da execucao de “C” uma decisao deve

ser tomada, pois temos mais de um hiper-arco partindo do vertice correspondente a Tarefa “C”.

Neste caso apenas um dos caminhos deve ser tomado, pois se trata de uma OU-F-Condicao. Se

escolhermos a Tarefa “H” como a proxima tarefa, o fluxo seguira normalmente ate a conclusao

da Tarefa “J”, havendo, entao, a tentativa de gerar a Tarefa “K”. Como existe mais de um

hiper-arco chegando em “K”, ou seja, temos uma OU-B-Condicao, algumas condicoes devem

17

ser verificadas. Neste caso, “K” podera ser gerada, pois apenas um dos pre-requisitos precisam

ser satisfeitos, neste caso a execucao de “J”. Voltando a Tarefa “C”, toma-se agora o caminho

indicado pela Tarefa “D”. O fluxo sera percorrido normalmente ate a finalizacao da execucao

de “E”, onde temos uma ramificacao no hiper-arco de saıda. Esta ramificacao significa que

todas as tarefas indicadas por esse hiper-arco como proximas deverao ser geradas. Neste caso

temos uma E-F-Condicao. Assim, as Tarefas “F”e “G”sao geradas e percorridas em paralelo.

Portanto, sao nestes casos, onde temos E-F-Condicoes, que ocorre o paralelismo de execucao

de tarefas. Ao termino da execucao de “F” e “G” as proximas tarefas convergem para uma so,

a Tarefa “K”. “K”so pode ser gerada se, e somente se, “F”e “G” tiverem sido executadas.

Esta condicao pode ser verificada atraves do hiper-arco {{F,G},{K}} onde temos uma E-B-

Condicao. Como “F”e “G” ja foram finalizadas, a Tarefa “K” e gerada e executada. Assim, a

execucao do fluxo finaliza com a conclusao da execucao de “K”.

Considere a situacao na qual sai-se de um vertice “A” atraves de um hiper-arco e, por

dois hiper-caminhos p1 e p2, onde p1 e p2 possuem uma ou mais atividades, e ambos os hiper-

caminhos convergem para um vertice “B”atraves de um hiper-arco OU. Neste caso a execucao

do fluxo segue a partir de “B” no momento em que o primeiro hiper-caminho chegar em “B”,

marcando o vertice “B”como “executado” para nao executar novamente quando o outro hiper-

caminho chegar em “B”.

Considere a situacao onde saımos de um vertice “A” atraves de um hiper-arco OU,

por dois hiper-caminhos p1 e p2, onde p1 e p2 possuem uma ou mais atividades, e ambos os

hiper-caminhos convergem para um vertice “B” atraves de um hiper-arco “E”. O hipergrafo e

considerado inconsistente, pois em “A”ele possibilitou uma escolha onde apenas um dos hiper-

caminhos sera executado, mas em “B” e exigido que os dois hiper-caminhos, p1 e p2, tenham

sido percorridos.

No exemplo da figura 3.9, “D” requer a execucao de “B” e “C”, porem nunca podera

ser alcancada, pois apenas “B” ou “C” sera executada. Assim, um fluxo pode ser qualificado da

seguinte forma:

18

Figura 3.9: Um hipergrafo direcionado incompatıvel

Quanto a inicializacao:

• mono-inicializavel (para simplificar, chamaremos apenas de inicializavel);

• multi-inicializavel;

• nao-inicializavel.

Quanto ao seu percurso:

• compatıvel;

• incompatıvel.

Dizemos que um fluxo nao-inicializavel ou incompatıvel e intratavel.

19

3.10 Trechos de execucao opcionais

Com hipergrafos direcionados podemos modelar tarefas que nao necessariamente pre-

cisam ser executadas para a conclusao do fluxo. Para isto, utilizamos uma combinacao especial

de hiper-arcos e vertices. Esta combincao consiste em uma condicao OU onde um dos hiper-

arcos tem seu conjunto |Origens| > 1 (hiper-arcos b e c do diagrama abaixo). Na execucao do

fluxo, as tarefas pertencentes ao conjunto destino do hiper-arco no qual o tamanho do conjunto

Origens e maior do que 1 ficarao pendentes ate que todas as tarefas do conjunto Origens sejam

finalizadas. Assim, todas as tarefas pertencentes ao conjunto destino deste hiper-arco serao exe-

cutadas obrigatoriamente, mesmo que uma das origens da aresta pertenca a uma condicao OU.

Neste caso as outras hiper-arestas que pertercam ao OU podem ser percorridas opcionalmente,

visto que umas das condicoes ja esta satisfeita.

Para demonstrar um desses casos, podemos utilizar o exemplo abaixo.

Figura 3.10: Um exemplo de modelagem de fluxo com trecho de execucao opcional

Perceba o retangulo na figura composto pelos vertices e hiper-arcos ditos opcionais.

Nos hiper-arcos de saıda do vertice B temos dois hiper-arcos formando um OU, note que o

hiper-arco c tem seu conjunto |Origens| > 1. O vertice G sempre sera executado, (salvo a

20

excecao de B, C ou D, nunca terminarem). Neste caso, a opcao de se executar a tarefa G

nao ocorreu em consequencia da escolha realizada da OU-F-Condicao em B, mas sim da E-B-

Condicao em B,C e D. O hiper-arco b ainda pode ser escolhido para execucao, porem ja temos

o hiper-arco c pertencente ao hiper-caminho da execucao do fluxo. Sendo assim, a execucao de

E, F e H nao precisa acontecer obrigatoriamente para a finalizacao do fluxo, enquanto que os

vertices G e I serao sempre executados, independente da escolha em B.

21

4 Definicoes Adotadas

Para efeito deste estudo consideraremos apenas fluxos trataveis, ou seja, fluxos inicia-

lizaveis e compatıveis. Sendo que os hipergrafos da classe hipergrafo Serial-Paralelo-Disjuncao

(HSPD), sao os que melhor atendem a estes requisitos.

Dependencia: definimos como dependencia a relacao entre os vertices de destino e os vertices

de origem de um hiper-arco. Para a execucao dos vertices do conjunto de vertices de destino de

um hiper-arco e necessario que todos os vertices do conjunto de origem estejam finalizados.

Utilizacao de vertices dependentes: Nos hipergrafos utilizados neste documento existem

varios exemplos onde ocorrem dependencias. As tarefas dependentes so podem ser executa-

dos depois que a dependencia foi resolvida. Assume-se que uma determinada tarefa que ja

tenha sido executada sera considerada finalizada durante a execucao de todo o fluxo, ou seja,

tarefas que dependam desta execucao nao precisam faze-la novamente. Assim, tarefas que ja

foram finalizadas podem ser usadas quantas vezes forem necessarias durante uma execucao. Ha

casos em que poderia ser interessante o vertice dependente ser usado apenas umas vez durante

a execucao, porem este caso nao sera abordado aqui.

22

5 Execucao do fluxo sobre Hipergrafos Direcionados

Este capıtulo apresenta o funcionamento de um algoritmo simples para execucao de

fluxos modelados com hipergrafos direcionados.

5.1 Um algoritmo para execucao de fluxo de tarefas

Genericamente a modelagem sobre um hipergrafo direcionado segue a seguinte logica:

a partir do vertice inicial I escolhe-se uma hiper-aresta pertencente ao conjunto de hiper-arestas

de saıda de I. Se nao houver nenhuma dependencia, o vertice em que a hiper-aresta corrente

incide e executado e posteriormente colocado em uma lista auxiliar L. Escolhe-se um vertice

pertencente a L e repete-se o procedimento de execucao ate que o vertice final do fluxo seja

alcancado e executado. Caso exista alguma dependencia, um vertice nao pode ser executado ate

que todas as dependencias tenham sido resolvidas.

Abaixo temos um algoritmo simples de execucao em hipergrafos direcionados mode-

lando um fluxo de tarefas. Nesta versao utilizamos quatro tipos de listas:

• lExecucao: Armazena os vertices que estao prontos para serem executados;

• lRecem Finalizados: Armazena os vertices que foram finalizados na ultima iteracao do algo-

ritmo;

• lFinalizados: Armazena os vertices que ja foram concluıdos;

• lPendentes: Armazena os vertices que ainda nao podem ser executados em razao de alguma

dependencia.

23

Ao longo da execucao do algoritmo as listas vao sendo atualizadas de modo que as de-

pendencias sejam respeitadas e todo o fluxo seja percorrido. No primeiro passo o vertice inicial

I e executado e os vertices pertencentes a FS(I) sao colocados na lista de tarefas pendentes. Em

seguida, executa-se um laco ate que a lista de tarefas que podem ser executadas esteja vazia.

Esta execucao consiste em percorrer a lista de tarefas pendentes, e para cada vertice v escolhe-

se uma hiper-aresta e pertencente a FS(v). Se nao houver dependencia, os vertices nos quais

a aresta e incide sao inseridos na lista de proximas tarefas que podem ser executadas. Apos

percorrer a lista de pendencias, a lista de tarefas que podem ser executadas e concatenada com

a lista de proximas tarefas que foi construıda durante a ultima iteracao. O algoritmo termina

quando a lista de tarefas que podem ser executadas estiver vazia.

24

5.1.1 Funcao Execucao (Principal)

Algoritmo 1: Execucao do FluxoDados: H = (V,E) e s ∈V

inıciolExecucao←− s

lRecem Finalizados←− /0

lFinalizados←− /0

lPendentes←− /0

enquanto lExecucao 6= /0 facalRecem Finalizados←− realizaTrabalho(lExecucao)

lProximas←− /0

lFinalizados←− lFinalizados∪ lRecem Finalizados

lPendentes←− lPendentes∪ lRecem Finalizados

para cada vertice ∈ (lPendentes) faca

se tamanho(FS(vertice)) = 1 entaotome a unica aresta ∈ FS(vertice) como e

senao escolha e ∈ FS(vertice)

se verificaDependencias(e, lFinalizados) = NAO entaolProximas←− lProximas∪Dest(e)

lPendentes←− lPendentes− vertice

lExecucao←− lExecucao∪ lProximas

fim

V contem a propriedade tarefa, e esta contem a propriedade tempo.

5.1.2 Funcao realizaTrabalho

A funcao realizaTrabalho recebe uma lista de tarefas (vertices), e diminui o tempo

em 1 a cada iteracao. Quando o tempo for igual a zero significa que a tarefa foi executada. A

tarefa e removida da lista de tarefas em execucao e incluıda na lista de tarefas finalizadas.

25

Funcao realizaTrabalho

Dados: lExecucao

inıciolRetorno←− /0

para cada Tarefa ∈ lExecucao facaDecremente seu Tempo em 1

se Tempo = 0 entaolRetorno = lRetorno∪ Tarefa

lExecucao = lExecucao−Tarefa

retorna lRetorno

fim

5.1.3 Funcao verificaDependencias

A funcao verificaDependencias verifica se todos os vertices de origem da aresta

pela qual o vertice foi alcancado foram finalizadas, verificando se estas tarefas pertencem a lista

de tarefas finalizadas. Se as tarefas foram finalizadas, inclui na lista de tarefas a gerar e retorna

esta lista.

Funcao verificaDependencias

Dados: e ∈ E, lFinalizados

inıcioTemDependencia = NAO

para cada vertice ∈ e.origens faca

se vertice /∈ lFinalizados entaoTemDependencia = SIM

retorna TemDependencia

fim

26

6 Paralelismo

Na execucao paralela varias tarefas sao realizadas simultaneamente. Com isso busca-se

a otimizacao de diversos fatores, entre eles recursos, tempo e lucro, minimizando o desperdıcio

dos mesmos. A paralelizacao vem sendo amplamente utilizada em diferentes meios, como por

exemplo processos em fluxo de trabalho dentro de empresas, onde equipes podem se dividir e

trabalhar paralelamente, buscando um objetivo em comum. Tem-se tambem, a paralelizacao de

processos computacionas, uma alternativa que a cada dia se difunde mais. Na execucao de um

hipergrafo direcionado o paralelismo ocorre durante uma execucao, quando uma ou mais tarefas

estiverem sendo executadas no mesmo momento, ou seja, determinado vertice e alcancado e

outros encontram-se na mesma situacao ou ja foram alcancados mas ainda estao em execucao,

porem atraves de outros hiper-caminhos. Para acontecer uma execucao paralela basta existir

uma E-F-Condicao. Havera paralelismo no fluxo se, e somente se, houver no mınimo uma E-

F-Condicao, pois esta proporciona a condicao necessaria que e a ramificacao em E, pela qual as

proximas tarefas geradas devem ser executadas. Este e o principal fator que modela a condicao

de paralelismo.

27

Figura 6.1: Um Hipergrafo Direcionado com trechos de execucao paralela

Na figura 6.1 temos uma representacao grafica de um hipergrafo direcionado. Este

hipergrafo pode modelar um fluxo qualquer no qual cada letra representa uma tarefa diferente.

No hiper-arco de saıda de A, tem-se uma bifurcacao apontando para dois destinos, originando

uma condicao E, logo, as tarefas B e C devem ser executadas. Neste caso a execucao pode se

dar de forma paralela.

Figura 6.2: Destaque das tarefas que podem ser executadas paralelamente

A figura 6.2 mostra o mesmo hipergrafo, na qual os retangulos indicam quais tarefas

podem ser executadas paralelamente, considerando que o tempo de execucao de cada uma de-

las e exatamente o mesmo. Na reprentacao grafica acima atribuımos cores diferenciadas aos

retangulos, indicando os possıveis hiper-caminhos seguidos nas diferentes execucoes do fluxo

que podem ocorrer. Durante a execucao, que inicia-se pela tarefa A, apenas uma tarefa e exe-

28

cutada simultaneamente, no caso a propria tarefa A. Apos seu termino, as tarefas B e C sao ini-

ciadas, pois trata-se de uma condicao E. Neste instante, B e C pertencem ao mesmo retangulo,

portanto duas tarefas podem ser executadas paralelamente. Apos o final da execucao destas

duas tarefas outras devem ser executadas. Partindo de B temos D,E e F, e partindo de C temos

duas opcoes de tarefas a executar. Ou executa-se a tarefa G, ou executam-se H e I, portanto,

tem-se dois hiper-caminhos diferentes a seguir, e duas possibilidades de tarefas que podem ser

executadas paralelamente, ou as taredas (D, E, F) e (G) indicadas pelos retangulos cinzas, ou

(D, E, F) e (H e I) indicadas pelos retangulos verdes. Na continuacao do fluxo seguimos a

mesma logica.

6.1 Grau de paralelismo da execucao em um instante t

Dado um hipergrafo-direcionado H que modela um fluxo de tarefas no qual acontece

uma execucao X , no instante t, definimos como p(H,X , t) o grau de paralelismo no momento

t da execucao. Por exemplo, existe um processo sendo executado que teve inıcio as 8 horas

da manha. Vamos calcular p(H,X , t) as 11 horas, momento em que existem 5 pessoas traba-

lhando e nao existe mais nenhuma tarefa que possa ser executada por outra pessoa, sendo que

algumas tarefas ja foram executadas e que o fluxo segue um certo caminho. Dizemos entao

que p(H,X , t) e igual a 5, independentemente de outros caminhos que possam ter um grau de

paralismo maior. Considera-se o grau do paralelismo no instante desejado no caminho que a

execucao vem seguindo.

6.2 Grau de paralelismo maximo em um instante t

Dado um hipergrafo-direcionado H que modela um fluxo de tarefas, definimos como

P(H, t) o grau maximo de paralelismo que o hipergrafo pode alcancar no instante t. Seguindo

o mesmo exemplo, porem supondo que hajam outros (um ou mais) caminhos nos quais mais

pessoas possam executar paralelamente, o valor de P(H, t) e o grau do paralelismo do caminho

em que o maior numero de pessoas estao trabalhando paralelamente. Na figura 6.3 tem-se o

29

grau de paralelismo calculado para cada instante considerando o tempo de execucao de cada

tarefa como sendo 1. Em cada linha este t e incrementado em um.

Figura 6.3: Calculo do grau de paralelismo em cada instante da execucao

6.3 Grau de paralelismo maximo do hipergrafo

Dado um hipergrafo-direcionado H que modela um fluxo de tarefas, definimos como

MP(H), o grau do paralelismo maximo do hipergrafo em qualquer instante da execucao do

fluxo. MP(H) = max[P(H, t)∀t ∈ N ≤ max[T ]] onde T e o conjunto de tempos t possıveis

discretizados, e max[T ] e o tempo maximo de execucao do fluxo.

30

6.4 Grau maximo medio de paralelismo do hipergrafo

Dado um hipergrafo-direcionado H que modela um fluxo de tarefas, definimos como

dP(H) a media de tarefas que podem ser executadas simultaneamente. Discretizando o valor

de t temos que dP(H) = ∑T1 P(H, t).

Figura 6.4: Grau medio de paralelismo do hipergrafo

No hipergrafo da figura 6.4 o grau medio e 2. Pois:

P(H,1) = 1

P(H,2) = 2

P(H,3) = 4

P(H,4) = 3

P(H,5) = 2

P(H,6) = 1

P(H,7) = 1

como ∑71 P(H, t) = 14 e 14/T = 2, portanto dP(H)= 2.

31

7 Algoritmos para Calculo do Maior Paralelismo emHipergrafos Direcionados

Neste capıtulo sao apresentados dois algoritmos o para calculo do maior paralelismo

em fluxo de trabalhos modelados em hipergrafos direcionados. Estes algoritmos utilizam metodos

distintos para o calculo. Nomeados como algoritmo A e B apenas para fazer distincao entre eles.

7.1 Algoritmo A

7.1.1 Consideracoes iniciais

Neste algoritmo, nos referimos a VETOR DE LISTAS como sendo uma lista de listas.

O VETOR e a lista principal, onde cada nodo possui uma outra lista, que por sua vez possui

vertices.

7.1.2 Funcionamento

A ideia por tras do algoritmo e que dado um determinado vertice A do Hipergrafo

Direcionado (hgd), e analisado se os hiper-arcos que saem deste vertice formam uma hiper-arco

E ou um hiper-arco OU.

Seja H o hgd abaixo.

Considere o vertice B. Podemos observar que de B parte apenas um hiper-arco, cha-

mado a. Portanto trata-se de uma E-F-Condicao, que por definicao exige B e C para seguir

para D. Neste caso, devemos analisar se todas as origens do hiper-arco a estao marcadas como

PRONTO. Para tanto, marcamos B como pronto e verificamos se estao todos prontos. Se sim,

32

Figura 7.1: Hipergrafo Direcionado

removemos todos os vertices origem de a e colocamos no lugar de B todos os vertices desti-

nos de a. Senao, nao podemos seguir ate estarem todos prontos. Devemos partir entao para o

proximo vertice da lista.

Considere agora o vertice E. Podemos observar que de E partem mais de um hiper-

arco, no caso os hiper-arcos b e c. Portanto trata-se de uma OU-F-Condicao. Nesta situacao,

para cada hiper-arco verificamos se suas origens estao prontas. Se todas as origens de todas os

hiper-arcos estiverem prontas, entao criamos uma copia da lista em que estamos trabalhando

para cada hiper-arco, e em cada uma delas substituımos as origens por seus respectivos destinos.

Em seguida removemos a lista original. Assim teremos uma copia da lista para o hiper-arco b,

substituindo E por F e G; e outra copia para o hiper-arco c, substituindo E por H. Se alguma

das origens dos hiper-arcos que saem de E nao estiver pronta, entao apenas marcamos E como

pronto e seguimos para o proximo vertice da lista.

Esperamos todas as arestas estarem prontas mesmo quando se trata de um hiper-arco

OU, pois como consideramos todos os tempos igual a 1, se um caminho andar e o outro nao,

entao pode ocorrer de o calculo do paralelismo para aquele nıvel se dar de forma errada. O

maior paralelismo e determinado pelo tamanho da maior das listas do VETOR em qualquer

momento da execucao do algoritmo.

33

7.1.3 Pseudocodigo

O algoritmo segue o fluxo de execucao a partir do vertice dado como inıcio, criando

novos fluxos de execucao a medida que encontra hiper-arcos do tipo OU-F-CONDICAO, adi-

cionando e removendo vertices da estrutura de listas e monitorando a quantidade de vertices de

um mesmo nıvel para ao final da execucao ter determinado o maior paralelismo.

34

Algoritmo 4: Algoritmo Ainıcio

lVetor← /0 ; lLista← /0 ; lProntos← /0indiceVetor← 0 ; indiceLista← 0 ; maiorParalel← 0 ; nivel← 0primeiro← Nodo() ; primeiro.vertice← inicio ; primeiro.nivel← 1primeiro.pronto← False ; primeiro.origem← NulllLista← lLista∪ primeiro ; lVetor← lLista∪ lLista ; acabou← Falseenquanto ((lVetor 6= /0)) e (nao acabou) faca

nivel← nivel + 1 ; iv← 0 ; il← 0enquanto (iv < len(lVetor)) e (nao acabou) faca

enquanto (il < len(lVetor[iv])) e (nao acabou) facase lVetor[iv][il].nivel ≤ nivel entao

se lVetor[iv][il].vertice.fs = /0 entaolVetor[iv]← lVetor[iv] - {lVetor[iv][il]} ; il← il - 1se lVetor[iv] = /0 entao lVetor← lVetor - {lVetor.[iv]}

senaose tamanho(lVetor[iv][il].vertice.fs) ≤ 1 entao

se VerificaProntos(lVetor, lProntos, iv, il) entaoil← RemoveOrigens(lVetor, lProntos, iv, il,lVetor[iv][il].vertice.fs)nodo← lVetor[iv][il]lVetor[iv]← lVetor[iv] - {lVetor[iv][il]}para cada vert ∈ nodo.vertice.fs[0].destinos faca

lVetor[iv]← lVetor[iv] ∪ {vert} na posicao ilse (nodo.vertice.fs[0].destinos = /0) e (lVetor[iv] = /0)entao

lVetor← lVetor - {lVetor[iv]}

senaose VerificaProntos(lVetor, lProntos, iv, il) entao

indiceVerticeOriginal← ilpara cada aresta ∈ lVetor[iv][il].vertice.fs faca

ReplicaLista(lVetor, iv)il← RemoveOrigens(lVetor, lProntos, iv+1, il,lVetor[iv][il].vertice.fs)nodo← lVetor[iv+1][il] ; lVetor[iv+1]← lVetor[iv+1] -{lVetor[iv+1][il]}para cada vert ∈ aresta.destinos faca

lVetor[iv+1]← lVetor[iv+1] ∪ {vert} na posicao ilse (aresta.destinos = /0) e (lVetor[iv+1] = /0) entao

lVetor← lVetor− lVetor[iv+1]il← indiceVerticeOriginal

lVetor← lVetor− lVetor[iv]

il← il + 1 ; LimpaVetor(lVetor)se lVetor = /0 entao

acabou← True ; no← Nodo ; lLista← /0 ; lLista← lLista∪ {no}lVetor← lVetor∪ {lLista}

LimpaVetor(lVetor) ; iv← iv + 1se lVetor = /0 entao acabou← True

maiorParalel← VerificaMaiorParalel(lVetor, maiorParalel, nivel+1)retorna maiorParalel

fim

35

Rotinas auxiliares

Abaixo temos uma breve descricao das funcoes utilizadas pelo algoritmo.

• RemoveOrigens: Esta funcao faz um loop nas listas de origens das arestas que saem do

vertice atual. Para cada vertice origem procura em lVetor o vertice correspondente e

caso nao seja o vertice atual entao remove. Remove tambem de lProntos. O vertice

atual e removido manualmente.

• VerificaProntos: Esta funcao marca o vertice atual como pronto e varre lVetor em busca

dos vertices que fazem parte das listas de origens dos hiper-arcos que chegam no

vertice atual verificando se todos estao marcados como prontos. Retorna Verdadeiro

ou Falso.

• ReplicaLista: Esta funcao e utilizada para criar uma copia de uma determinada lista

dentro de lVetor. Ela cria uma nova lista e copia todos os itens da lista indicada.

• VerificaMaiorParalel: Esta funcao passa por lVetor contando quantos vertices pertencen-

tes ao nıvel atual de execucao estao presentes, determinando assim o paralelismo

neste dado momento da execucao do algoritmo.

• LimpaVetor: Esta funcao e chamada para retirar de lVetor listas vazias. Ela varre lVetor

removendo todas as listas que nao contem elementos.

36

7.2 Algoritmo B

7.2.1 Consideracoes iniciais

Este algoritmo tem seu funcionamento baseado no conceito de itens. Cada item carrega

varias informacoes uteis que sao usadas para o calculo do maior paralelismo. Durante a criacao

dos itens, o hipergrafo e simplificado, onde os vertices sao agrupados de tal maneira que cada

item ja detem o paralelismo pre-calculado. Para isso, uni-se os vertices que estao em E e agrupa-

se os itens com o mesmo pai. Os itens criados sao separados em uma lista de tempos, que e

uma lista de listas indexada pelo tempo discretizado. Ao fim da construcao desta lista, e feita

uma analise sobre estes itens. A analise consiste em escolher o maior paralelismo dos itens

com nıveis iguais e somar os paralelismos dos itens com nıveis diferentes. Ao final escolhe-se

o maior deles e obtemos o maior paralelismo.

Um item e um conjunto de nodos de destino de um hiper-arco. Basicamente e uma

quıntupla (t, p,n, id, pai), onde:

• t: e a unidade de tempo em que o item foi alcancado

• p: e o grau do paralelismo do item

• n: e o nıvel do item, em relacao a outros itens com o mesmo tempo, niveis iguais indicam

OU, e niveis diferentes indicam E

• id: e o identificador unico do item, quando o item e agrupado, todos ganham o mesmo id

• pai: e o id do item pai

Alem dessas propriedades temos outras que sao:

• Agrupamento: Agrupamento a qual o item pertence, no caso de pertencer a algum.

• Nıvel filho: Quando um dos hiper-arcos e visitado, a variavel nivel filho do item a qual

o vertice pertence e atualizada com o numero do nıvel do item de destino, esta variavel e

37

necessaria para atualizar corretamente o nıvel de um item, caso o item a ser criado tiver

um nıvel igual a outro dentro de um mesmo agrupamento.

• Nıvel de Referencia do Agrupamento: Esta variavel pertence ao agrupamento, ela indica

o nivel de referencia do agrupamento como um todo, e nao so de um unico item. Auxilia

no calculo de um novo valor do nıvel de um novo item a ser criado.

7.2.2 Funcionamento

Podemos visualizar melhor o funcionamento deste algoritmo atraves do exemplo da

figura 7.2.

Figura 7.2: Fluxo de Tarefas

Neste diagrama temos um fluxo de tarefas representado por um hipergrafo direcionado

38

H = ({A,B,C,E,F,G,H,I,J,K,L,M},{a,b,c,d,e, f ,g,h, i, j,k}), onde A e M sao os vertices ini-

cial (s) e final (t), respectivamente. Tendo este hipergrafo como entrada do algoritmo, o mesmo

e iniciado atraves do vertice A, sendo que para este primeiro vertice e criado um item automati-

camente. Feito isto, e tomado o hiper-arco a e deste todos os vertices de destino do mesmo sao

agrupados em um conjunto, um vertice somente e agrupado se o vertice nao pertencer a lista

de prontos. Em seguida um item e criado com os seus respectivos dados, relembrando que os

dados de um item sao: o momento em que o item e criado, o tamanho do conjunto do vertices

do destino do hiper-arco, a relacao deste item com algum outro item criado na mesma unidade

de tempo (trataremos melhor desta informacao adiante, onde chamaremos esta de nıvel), quem

e o item que deu origem a este novo item e um identificador unico para o item. Assim que um

item e criado, ele e inserido na lista de tempos, essa lista e basicamente uma lista de listas, ou

seja e uma lista principal indexada pelo tempo, onde cada tempo tem uma lista de itens, onde

estes itens tem o campo tempo, em seu respectivo item. Podemos ter uma melhor visualizacao

da lista de itens, na figura 7.3:

Figura 7.3: Um exemplo de lista de tempos

Apos a inclusao de um item na lista de tempos, os vertices deste item passam pela

realizacao de trabalho onde e simulada a execucao da tarefa. A realizacao do trabalho consiste

39

em diminuir o tempo executado em 1 cada vez que passar por essa funcao, em que cada vertice

tem um tempo de execucao, tempo este podendo ser qualquer numero pertencente ao conjunto

dos numeros naturais. Por exemplo, determinada tarefa representada por um vertice demora 10

unidades de tempo para ser concluıda, entao cada vez que este vertice passar por uma execucao

este tempo e subtraıdo em 1 ate chegar a zero, quando chegar a este valor, o vertice e dado como

executado.

O algoritmo apresentado aqui foi preparado para funcionar com tarefas tendo qualquer

tempo de execucao, por isso temos a lista de prontos, a lista de pendentes e os conceitos de

execucao e realizacao de trabalho, mas neste documento, trabalharemos apenas com tarefas

com tempo de execucao igual a uma unidade. E importante ressaltar que para que o algoritmo

funcione com tempos diferentes de 1, e necessario que se inclua uma nova entrada informando

quais os tempos de cada tarefa.

Voltando ao momento da execucao, ao final da realizacao do trabalho, os vertices fina-

lizados sao retirados da lista anterior e dispostos em uma nova lista, e para cada vertice desta

lista e incluıdo na lista geral de vertices prontos.

Para cada vertice recem finalizado, e calculado o valor do nıvel que ira ser repassado

para os filhos do item atual, pois apos isso, para cada vertice sao selecionados todos os hiper-

arcos do conjunto FS do vertice e a funcao de criacao de itens e chamada recursivamente para

cada hiper-arco, passando o nıvel calculado como sendo um dos parametros.

O calculo do nıvel consiste em verificar se o item atual, no caso o item pai do item que

ira receber o nıvel calculado, pertence a algum agrupamento de itens. Caso pertencer a algum

agrupamento, e verificado se algum item neste agrupamento tem o mesmo nıvel do item atual,

se tiver o novo valor e igual ao valor do nıvel filho do item com o mesmo nıvel, senao, e gerado

um novo valor para o nıvel. Este valor e o resultado da soma de tres valores distintos, que sao:

o nıvel de referencia, a posicao do vertice atual no grupo de vertices do item atual e a posicao

do item atual no agrupamento a qual ele pertence se ele pertencer a algum.

Ao fim, o dado calculado e salvo na variavel nıvel de referencia do agrupamento e o

40

item filho do item atual recebe o novo valor de nıvel recem calculado.

Com o nıvel calculado, e chamada a funcao de criacao de itens para cada hiper-arco.

Ao final da criacao de todos os itens estruturados na lista de tempos, temos uma saıda

como no exemplo da figura 7.4.

Figura 7.4: Criacao dos itens

No hipergrafo, a esquerda da figura 7.4, temos os retangulos azuis indicando os itens,

os retangulos vermelhos indicando os agrupamentos de itens, e os conjuntos a direita sao a lista

de tempos, com seus respectivos itens entre parenteses e seus atributos separados por vırgula,

que sao: Tempo, Paralelismo, Nıvel, ID do Item ou Agrupamento (quando um item pertence

a algum agrupamento, todos os itens desse agrupamento tem o mesmo ID) e ID do Item Pai.

41

Sendo que as chaves indicam o agrupamento.

Com esta estrutura montada, parte-se para a analise dos itens, onde cada lista de itens

em um determinado tempo e analisada calculando o maior paralelismo naquele tempo. Para

calcular o maior paralelismo em um determinado tempo, e seguido o seguinte lema: Escolhe-se

o maior valor do paralelismo de itens com o mesmo nıvel ou apenas um dos itens caso tenha o

mesmo valor, removendo do calculo os itens com valores menores e somando o paralelismo de

itens com nıveis diferentes. Sempre fazendo o calculo internamente aos agrupamentos primeiro

e depois para o restante, assim como calculos em algebra analogicamente.

Com os valores de cada tempo calculado, verifica-se qual dos tempos tem o maior

paralelismo, chegando entao ao resultado final.

42

7.2.3 Pseudocodigo

Criacao dos Itens

Abaixo temos o pseudo-codigo para o algoritmo de criacao dos itens, sendo o passo

fundamental para o calculo do paralelismo.

43

Algoritmo 5: CriaItens()Entrada: H = (V,E), ltempos, lprontos, lpendencias, itempai, hiper arco s ∈ E,

t ∈ N,nivel ∈ N, contadorid item ∈ NSaıda: Lista de Itens indexado por tempoinıcio

lnodos← /0 l f inalizados← /0se hiper arco = Nulo entao

tome v sendo Vertice Inicial ∈ Hlnodos← lnodos∪ Nodo(v,v.tempo)

senaolnodos←DST(hiper arco)−lprontos

repitalgrupo←CriaGrupo(lnodos)contadorid item←− contadorid item +1 item←Item(tempo, tamanho(lnodos),nivel,grupo, itempai,contadorid item)se item.paralelismo < 0 entao

lgrupo← InsereTempo(ltempos, item)lnodos, l f inalizados←− RealizaTrabalho(lnodos)l f inalizados← l f inalizados∪ lpendenciaslpendencias← /0para cada n ∈ l f inalizados faca

lprontos← lprontos∪{n}se n.item.lagrupamento 6= /0 entao

iditem igual ← VerificaSeHaNivelIgual(n.item, n.item.lagrupamento)se iditem igual 6=−1 entao

nivel← n.item.lagrupamento[iditem igual].nivel f ilho

senaonivel← RetornaNivelReferencia(item) + pos(n.item.lgrupo,n) +pos(n.item.lagrupamento, n.item)

senaose n ∈ n.item.grupo entao

nivel← pos(n.item.lgrupo,n)

SalvaNivelReferencia(item, nivel)n.item.nivel f ilho← nivelpara cada e ∈ n.vertice.fs faca

t← tempo+1se algum vertice ∈ ORG(e) /∈ lprontos entao

lpendencias← lpendencias∩{n}senao

ltempos = CriaItens(Nulo, ltempos,e, t,nivel, item)

tempo← tempo+1ate lnodos 6= /0retorna ltempos

fim

44

Rotinas Auxiliares

InsereTempo

Funcao InsereTempo

Entrada: ltempos, item

Saıda: Lista de Itens indexado por tempo atualizada

inıcio

se tamanho(lTempos) ≤ item.tempo entaolnova← /0

lnova← lnova∪{item}

lTempos← lTempos∪{lnova}

senao

para cada it ∈ lTempos[item.tempo] faca

se (it.nivel 6= item.nivel) e (it.itempai.id = item.itempai.id) entaoAgrupaItens(it, item)

lTempos[item.tempo]← lTempos[item.tempo] ∪{item}retorna lTempos

fim

45

Outras Rotinas Auxiliares

A seguir uma breve descricao de algumas rotinas ulizadas. Uma tentativa de implementacao

completa encontra-se nos Anexos.

• VerificaSeHaNivelIgual: Funcao que procura no agrupamento algum item com o mesmo

nıvel do item procurado e retorna este item.

• RealizaTarefa: Executa uma tarefa, retorna uma lista de tarefas finalizas e outra lista

de tarefas que nao foram completadas. Faz basicamente o trabalho do algoritmo

apresentado na secao 5.1.2.

• AgrupaItens: Esta funcao verifica se dois itens pertencem a algum agrupamento, o item

que nao pertencer a nenhum, e incluso no agrupamento existente. Se os dois itens

pertencerem a agrupamento distintos, e feita a uniao destes agrupamentos, caso

contrario um novo agrupamento e criado contendo os itens. Quando um item e

incluso em um agrupamento, o numero identificador do item passa a ser o numero

identificador do agrupamento.

• RetornaNivelReferencia: Funcao que retorna o Nıvel de referencia do Agrupamento ou

do Item. Se o item passado como parametro nao pertencer a algum agrupamento,

o valor retornado e o valor de referencia do item, senao, e retornado o valor do

primeiro item do agrupamento.

• SalvaNivelReferencia: Funcao que salva o valor do Nıvel de referencia do Agrupamento

ou do Item, se o item nao pertencer a nenhum agrupamento, o valor e salvo no

valor de referencia do item, se nao, o valor e sempre salvo no primeiro item do

agrupamento.

46

Analise dos Itens e Calculo do Maior Paralelismo

Tendo o algoritmo de criacao de itens pronto, pode-se usa-lo na funcao de calculo do

paralelismo. O algoritmo abaixo chama a funcao CriaItens que cria a lista de tempos e faz a

analise desta lista para calcular o valor do maior paralelismo do hipergrafo.

Algoritmo 7: CalculaParalelismoEntrada: H = (V,E)

Saıda: Valor do grau do maior paralelismo do Hipergrafo dado como entrada

inıcioltempos← CriaItens(H, /0, /0, /0,Nulo,Nulo,0,0,0)

lTempoFinal ← /0

lSomas← /0

para cada lItens ∈ lTempos facalgrupo← /0

para cada item ∈ lItens faca

se item percencer a algum agrupamento entaoQualifica(item.lagrupamento)

soma← SomaItens(item.lagrupamento)

lSomas← lSomas∪{soma}

item.lagrupamento← /0

senaolgrupo← lgrupo∪{item}

Qualifica(lgrupo)

soma← SomaItens(lgrupo)

lSomas← lSomas ∪{soma}

maiorSoma, k← max(lSomas)

lTempoFinal ← lTempoFinal ∪{maiorSoma}maior← max(lTempoFinal)

retorna maior

fim

47

Rotinas Auxiliares

Procedimento Qualifica

O procedimento Qualilifica, verifica na lista de itens quais possuem o mesmo valor

do nıvel. Quando dois itens estiverem nesta situacao, devemos escolher qual o maior valor do

paralelismo do item, aquele com o maior valor e indicado como maior.

Procedimento Qualifica

Entrada: litens = lista de itens

inıcio

para cada item1 ∈ litens faca

se item1.maior = Verdadeiro entao

para cada item2 ∈ litens faca

se item2.maior = Verdadeiro entao

se item1.nivel = item2.nivel entao

se item1.paralelismo < item2.paralelismo entaoitem1.maior← Falso

item2.maior← Verdadeiro

senaoitem2.maior← Falso

item1.maior← Verdadeiro

fim

48

Soma Itens

Esta funcao verifica na lista de itens dada como parametro e soma de todos os valo-

res do paralelismo dos itens marcados como maior, dados pelo procedimento de qualificacao.

Retornando o valor da soma.

Funcao SomaItens

Entrada: litens = lista de itens ja qualificada.

Saıda: Valor da soma.

inıciosoma← 0

para cada item ∈ litens faca

se item.maior == Verdadeiro entaosoma← soma + item.paralelismo

retorna soma

fim

49

8 Conclusao

Neste trabalho e possıvel concluir que o uso de hipergrafos direcionados na modela-

gem de fluxos de tarefas, sejam eles workflow, processos computacionais ou regras de negocio,

entre outros, e extremamente util para a resolucao de uma serie de problemas que utilizam este

tipo de estruturas. Com os hipergrafos direcionados e possıvel modelar e enxergar no nıvel

de estrutura de dados uma serie de informacoes relevantes sem a necessidade de anexos, como

variaveis auxiliares nao pertencentes a sua estrutura basica. Assim e possıvel visualizar e mode-

lar muito facilmente as dependencias entre as tarefas. Vimos que podemos modelar paralelismo

em OU e em E, e atraves deles podemos calcular onde temos possıveis momentos de execucoes

paralelas, e qual e o ponto com o maior grau de paralelismo. Informacao extremamente util

em muitas areas, mas principalmente para gestores e analistas de negocio e de sistemas, pois

com tais informacoes e criada uma base solida que auxilia a tomada de diversas decisoes, sa-

bendo exatamente o maximo de recursos a alocar sem ocorrer desperdıcio de recursos, alem

da otimizacao dos recursos existentes. Sem muita dificuldade e possıvel perceber que o para-

lelismo e uma das saıdas para a otimizacao de qualquer processo e o hipergrafo direcionado

e a ferramente adequada para a sua modelagem por guardar um serie de informacoes relevan-

tes. Enfim, e um assunto que merece muito estudo, apesar de ser pouco explorado atualmente,

tendera a um futuro promissor.

50

Referencias Bibliograficas

DONADELLI, J. Algoritmos e Teoria dos Grafos. Dezembro 2008. Disponıvel em:<http://www.inf.ufpr.br/jair/ci065>.

GUEDES, A. L. P. Hipergrafos Direcionados. Tese (Doutorado) — Universidade Federal doRio de Janeiro, 2001.

PARANA, C. I. do. Expresso Livre - Workflow. Dezembro 2008. Disponıvel em:<http://www.expressolivre.org/html/expressolivre/index.php?page=workflow>.

ROBERTO, M. e. Pargo - Paralelismo, Grafos e Otimizacao Combinatoria - Seminarios -Problema de ordenacao de mensagens em sistemas paralelos. Dezembro 2008. Disponıvel em:<http://www.lia.ufc.br/ pargo/index.php?n=Seminarios.MarcioRoberto>.

SERRALHEIRO, W. Estrutura Organizacional. Dezembro 2008. Disponıvel em:<http://wiki.cefetsc.edu.br/mediawiki/images/5/5a/Aru empreend cap3.pdf>.

STIVANIN, Z. Tracado Automatico de Hipergrafos Direcionados. Dissertacao (Mestrado) —Universidade Federal do Parana, 2006.

51

ANEXO A -- Algoritmo (A) para calculo do maior paralelismo

import sys

import os

import re

from hipergrafo import *

#—————————————————————————

#Classe para armazenar cada vertice

#—————————————————————————

class TNodo:

vertice = TVertice()

pronto = False

origem = TVertice()

nivel = 0

#—————————————————————————

#Remove todas as origens do hiper arco. Menos o vertice atual.

#—————————————————————————

def fnRemoveOrigens(vetor, prontos, indiceVetor, indiceLista, arestas):

quantRemovidos = 0

for aresta in arestas:

for vertice in aresta.origens:

indiceL = 0

#procura no vetor para remover.

while (indiceL < len(vetor[indiceVetor])):

#verifica se vertice e uma das origens que procuramos

if (vetor[indiceVetor][indiceL].vertice.rotulo == vertice.rotulo):

# Se e o vertice atual, pula

if (indiceL==indiceLista):

indiceL = indiceL + 1

else: # Se nao e o vertice atual, remove.

52

vetor[indiceVetor].pop(indiceL)

#Atualiza indice do vetor que e utilizado externamente a esta funcao

if (indiceL < indiceLista):

indiceLista = indiceLista - 1

#remove tambem da lista de prontos

indiceP = 0

tirou = False

while (indiceP < len(prontos)) and (not tirou):

#procura na lista de prontos

if (prontos[indiceP].vertice.rotulo == vertice.rotulo):

# Se achou, remove da lista de prontos

prontos.pop(indiceP)

tirou = True

else:

indiceP = indiceP + 1

quantRemovidos = quantRemovidos + 1

else:

#senao vai para o proximo elemento.

indiceL = indiceL + 1

return indiceLista

#—————————————————————————

#Marca vertice atual como pronto e verifica se todas as origns estao prontas.

#—————————————————————————

def fnVerificaProntos(vetor, prontos, indiceVetor, indiceLista):

#marca vertice como pronto

vetor[indiceVetor][indiceLista].pronto = True

#Adiciona como pronto

verticePronto = TNodo()

verticePronto.vertice = vetor[indiceVetor][indiceLista].vertice

verticePronto.nivel = vetor[indiceVetor][indiceLista].nivel

verticePronto.pronto = vetor[indiceVetor][indiceLista].pronto

verticePronto.origem = vetor[indiceVetor][indiceLista].origem

prontos.append(verticePronto)

#Verifica quantos estao prontos

todosProntos = True

idAresta = 0

53

while (idAresta < len(vetor[indiceVetor][indiceLista].vertice.fs)) and todosProntos:

aresta = vetor[indiceVetor][indiceLista].vertice.fs[idAresta]

idOrigem = 0

while (idOrigem < len(aresta.origens)) and todosProntos:

vert = aresta.origens[idOrigem]

achou = False

idProntos = 0

while (idProntos < len(prontos)) and (not achou):

if (vert.rotulo == prontos[idProntos].vertice.rotulo):

achou = True

else:

idProntos = idProntos+1

todosProntos = achou

#Se nao achou 1, entao nao estao todos prontos.

idOrigem = idOrigem+1

idAresta = idAresta+1

return todosProntos

#—————————————————————————

#Faz uma copia da lista no vetor.

#—————————————————————————

def fnReplicaLista(vetor, indiceVetor):

novaLista = []

for vert in vetor[indiceVetor]:

nodo = TNodo()

nodo.vertice = vert.vertice

nodo.origem = vert.origem

nodo.pronto = vert.pronto

nodo.nivel = vert.nivel

novaLista.append(nodo)

vetor.insert(indiceVetor+1, novaLista)

#—————————————————————————

#Verifica o maior paralelismo atual

#—————————————————————————

def fnVerificaMaiorParalel(vetor, maior, nivel):

indiceLista = 0

54

while (indiceLista < len(vetor)):

quant = 0

indiceItem = 0

while (indiceItem < len(vetor[indiceLista])):

quant = quant + 1

indiceItem = indiceItem + 1

if (quant > maior):

maior = quant

indiceLista = indiceLista + 1

return maior

#—————————————————————————

#Remove listas vazias do vetor

#—————————————————————————

def fnLimpaVetor(vetor):

i = 0

while (i < len(vetor)-1):

if (len(vetor[i]) == 0):

vetor.pop(i)

else:

i = i + 1

#—————————————————————————

#Funcao Principal

#—————————————————————————

def fnParalelismo(inicio):

vetor = []

lista = []

prontos = []

indiceVetor = 0

indiceLista = 0

maiorParalel = 0

nivel = 0

primeiro = TNodo()

primeiro.vertice = inicio

primeiro.nivel = 1

primeiro.pronto = False

primeiro.origem = None

55

# Adicionar 1o vertice no Vetor[0,0]

lista.append(primeiro)

vetor.append(lista)

acabou = False

#LOOP ate vetor ficar vazio.

while (vetor != []) and (not acabou):

nivel = nivel + 1

iv = 0

il = 0

#loop por todas as listas do vetor

while (iv < len(vetor)) and (not acabou):

#loop por todos os vertices da lista

while (il < len(vetor[iv])) and (not acabou):

#Verifica se o vertice e do nıvel atual ou menor

if (vetor[iv][il].nivel <= nivel):

#verifica se o vertice tem aresta fs (que saem).

if (len(vetor[iv][il].vertice.fs) == 0):

#Se nao tem, ele e o ultimo do caminho.

vetor[iv].pop(il)

il = il-1

#Se a lista ficou vazia, remove do vetor

if len(vetor[iv]) == 0:

vetor.pop(iv)

else:

#Verifica se sai em E, ou seja, se o nr. de arestas que saem do vertice e igual a 1

if(len(vetor[iv][il].vertice.fs)<=1):

#verificar se os vertices dependentes estao marcados como ”pronto”.

#Se sim, tira todos e coloca o destino.

if (fnVerificaProntos(vetor, prontos, iv, il)):

#Remover todas as origens das listas.

il = fnRemoveOrigens(vetor, prontos, iv, il, vetor[iv][il].vertice.fs)

#Remove vertice atual da lista atual

nodo = vetor[iv].pop(il)

#Adiciona vertices do destino na lista atual

for vert in nodo.vertice.fs[0].destinos:

56

novo = TNodo()

novo.vertice = vert

novo.origem = nodo.vertice

novo.nivel = nivel + 1

novo.pronto = False

#Insere na posicao atual

vetor[iv].insert(il, novo)

#Se nao tem nenhum destino entao nao adicionou ninguem.

#Neste caso se a lista ficou vazia, remove do vetor

if (len(nodo.vertice.fs[0].destinos) == 0) and (len(vetor[iv]) == 0):

vetor.pop(iv)

#fim if tipo E

else:

#Sai aresta do tipo OU

#Verifica se estao todos prontos

if (fnVerificaProntos(vetor, prontos, iv, il)):

indiceVerticeOriginal = il

for aresta in vetor[iv][il].vertice.fs:

#Duplica lista

fnReplicaLista(vetor, iv) #Nova lista esta em iv+1, lista original em iv

#Remove origens da aresta

il = fnRemoveOrigens(vetor, prontos, iv+1, il, vetor[iv][il].vertice.fs)

#Remove vertice atual da lista replica

nodo = vetor[iv+1].pop(il)

#Adiciona vertices do destino na lista replica

for vert in aresta.destinos:

novo = TNodo()

novo.vertice = vert

novo.origem = nodo.vertice

novo.nivel = nivel + 1

novo.pronto = False

#Insere na posicao atual

vetor[iv+1].insert(il, novo)

#Se nao tem nenhum destino entao nao adicionou ninguem.

#Neste caso se a lista ficou vazia, remove do vetor

if (len(aresta.destinos) == 0) and (len(vetor[iv+1]) == 0):

57

vetor.pop(iv+1)

il = indiceVerticeOriginal

#Remove a lista original

vetor.pop(iv)

#fim if E else OU

#fim if e ultimo no caminho

#fim if nıvel

il = il + 1

fnLimpaVetor(vetor)

if (vetor == []):

acabou = True

#Adiciona um nodo vazio para nao gerar erro ao analizar a condicao do loop, antes de sair dele.

no = TNodo

lista = []

lista.append(no)

vetor.append(lista)

#fim while il

fnLimpaVetor(vetor)

iv = iv + 1

if (vetor == []):

acabou = True

#fim while iv

maiorParalel = fnVerificaMaiorParalel(vetor, maiorParalel, nivel+1)

#fim while vetor != []

return maiorParalel

#fim fnParalelismo()

#——————————————————————————-

#Inıcio do Programa

#——————————————————————————-

hipergrafo = THipergrafo()

arquivo = raw input(”Digite o nome do arquivo que contem o hipergrafo a ser analisado:”)

hipergrafo.fnLeHiperGrafo(arquivo.strip())

maior = fnParalelismo(hipergrafo.lista vertices[0])

58

ANEXO B -- Algoritmo (B) para calculo do maior paralelismo

# coding: utf-8

import sys

import os

import re

from hipergrafo import *

#——————————————————————————-

# Classe TNodo

#——————————————————————————-

class TNodo:

vertice = None

tempo restante = 0

item = None

def init (self, vertice, tempo):

self.vertice = vertice

self.tempo restante = tempo

#——————————————————————————-

# Cada Item e um conjunto de nodos de destino de uma hiper arco.

#——————————————————————————-

class TItem:

id = 0

id original = 0

tempo = 0

paralelismo = 0

nivel = 0

grupo = None

item pai = None

agrupamento = None

59

ref = 0

nivel filho = -1

maior = True

#—————————————————————————

#Construtor da classe

#—————————————————————————

def init (self, tempo, paralel, nivel, grupo, item pai, id):

self.tempo = tempo

self.paralelismo = paralel

self.nivel = nivel

self.grupo = grupo

self.item pai = item pai

self.id = id

self.id original = id

self.referencia = nivel

for n in grupo:

n.item = self

#—————————————————————————

# Mostra um item na tela

#—————————————————————————

def mostrar(self):

if (self.item pai != None):

idPai = self.item pai.id

else:

idPai = 0

if (self.paralelismo > 0):

if (self.agrupamento == None):

print (”(”+ str(self.tempo) + ”,”+ str(self.paralelismo) + ”,”+ str(self.nivel) + ”,”+ str(self.id) +”,”+ str(idPai) +”) ”),

else:

if (self.agrupamento[0] == self):

print (”*[”),

for i in self.agrupamento:

if (i.paralelismo > 0):

print (”(”+ str(i.tempo) + ”,”+ str(i.paralelismo) + ”,”+ str(i.nivel) + ”,”+ str(i.id) +”,”+ str(i.item pai.id) +”) ”),

print (”]*”),

60

#——————————————————————————-

# Classe para calculo do maior paralelismo

#——————————————————————————-

class TParalelismo:

listaTempos = []

listaProntos = []

listaPendencias = []

contador id item = 0

#—————————————————————————

# Retorna primeiro vertice do hipergrafo

#—————————————————————————

def fnRetornaPrimeiroVertice(self, hipergrafo):

return hipergrafo.lista vertices[0]

#—————————————————————————

# Retorna o nivel de referencia do agrupamento

#—————————————————————————

def fnRetornaNivelReferencia(self,item pai):

if (item pai != None):

if (item pai.agrupamento == None):

return item pai.referencia

else:

return item pai.agrupamento[0].referencia

else:

return 0

#—————————————————————————

# Altera o nivel de referencia do agrupamento

#—————————————————————————

def fnSalvaNivelReferencia(self,item pai, referencia):

if (item pai != None):

if (item pai.agrupamento == None):

item pai.referencia = referencia

else:

item pai.agrupamento[0].referencia = referencia

#—————————————————————————

# Retorna todo os vertices de destino do hiper arco

#—————————————————————————

61

def fnRetornaProximosVerticesDoHiperArco(self, hiper arco):

listaNodos = []

for vertice in hiper arco.destinos:

if (not self.fnBuscaVerticesNalistaNodos(self.listaProntos, vertice)):

nodo = TNodo(vertice, vertice.tempo)

listaNodos.append(nodo)

return listaNodos;

#—————————————————————————

# Procura vertice na lista de nodos

#—————————————————————————

def fnBuscaVerticesNalistaNodos(self, lista, vertice):

bAchou = False

i = 0

while ((not bAchou) and (i < len(lista))):

if (vertice.rotulo == lista[i].vertice.rotulo):

bAchou = True

else:

i = i + 1

return bAchou

#—————————————————————————

# Verifica se uma vertice de origem da hiper arco nao foi executado

#—————————————————————————

def fnVerificaSeTodoOsVerticesDepentendesEstaoProntos(self, hiper arco):

bSim = True

for vertice in hiper arco.origens:

if (not self.fnBuscaVerticesNalistaNodos(self.listaProntos, vertice)):

bSim = False

return bSim;

#—————————————————————————

# Executa a tarefa, diminuindo em um, cada vez que passa por essa funcao.

# Simula a execucao da tarefa

#—————————————————————————

def fnRealizaTrabalho(self, conjunto nodos):

finalizados = []

for n in conjunto nodos:

n.tempo restante = n.tempo restante - 1

62

if (n.tempo restante < 1):

finalizados.append(n)

for n in finalizados:

print(n.vertice.rotulo)

conjunto nodos.remove(n)

return conjunto nodos, finalizados

#—————————————————————————

# Verifica se ha alguem no agrupamento com o mesmo nıvel

#—————————————————————————

def fnVerificaSeHaNivelIgual(self, item, agrupamento):

iAchou = -1

i = 0

while ((iAchou == -1) and (i < len(agrupamento))):

if ((agrupamento[i].nivel == item.nivel) and (agrupamento[i].id original != item.id original)):

iAchou = i

else:

i = i + 1

return iAchou

#—————————————————————————

# Verifica se o item pertence ao grupo

#—————————————————————————

def fnPertenceA(self, item, grupo):

bAchou = False

i = 0

while ((bAchou == False) and (i < len(grupo))):

if (grupo[i].id original == item.id original):

bAchou = True

else:

i = i + 1

return bAchou

#—————————————————————————

# Unifica dois grupos

#—————————————————————————

def fnUnifica(self, grupo1, grupo2):

63

for item in grupo2:

if (not self.fnPertenceA(item, grupo1)):

grupo1.append(item)

grupo2 = grupo1

#—————————————————————————

# Agrupa itens

#—————————————————————————

def fnAgrupaItens(self, item1, item2):

if (item1.agrupamento != None):

if (item2.agrupamento == None):

item1.agrupamento.append(item2)

item2.agrupamento = item1.agrupamento

item2.id = item1.id

else:

self.fnUnifica(item1.agrupamento, item2.agrupamento)

item2.agrupamento = item1.agrupamento

item2.id = item1.id

else:

if (item2.agrupamento != None):

item2.agrupamento.append(item1)

item1.agrupamento = item2.agrupamento

item1.id = item2.id

else:

self.contador id item = self.contador id item + 1

item1.id = self.contador id item

item1.agrupamento = []

item1.agrupamento.append(item1)

item1.agrupamento.append(item2)

item2.agrupamento = item1.agrupamento

item2.id = item1.id

#—————————————————————————

# Insere um item no seu tempo correto, alem de agrupar os itens que tem

# mesmo pai e niveis diferentes

#—————————————————————————

64

def fnInsereTempo(self,item):

if (len(self.listaTempos) <= item.tempo):

l = []

l.append(item)

self.listaTempos.append(l)

else:

# Varre em busca de itens com nıvel diferente do que esta sendo inserido e com o mesmo pai,

for it in self.listaTempos[item.tempo]:

if ((it.nivel != item.nivel) and (it.item pai.id == item.item pai.id)):

# faz o agrupamento destes itens

self.fnAgrupaItens(it, item)

self.listaTempos[item.tempo].append(item)

return self.listaTempos

#—————————————————————————

# Cria um grupo

#—————————————————————————

def fnCriaGrupo(self, conjunto nodo):

l = []

for n in conjunto nodo:

l.append(n)

return l

#—————————————————————————

# Funcao principal do calculo, desce em recursao, fazendo busca em

# profundidade e calculando os itens.

# Itens esses, que sao usados para o calculo final

#—————————————————————————

def fnCriaItens( self, hipergrafo, hiper arco, tempo, nivel, item pai):

conjunto nodos = []

finalizados = []

# primeiro vertice

if (hiper arco == None):

v = self.fnRetornaPrimeiroVertice(hipergrafo)

conjunto nodos.append(TNodo(v,v.tempo))

else:# Cria um conjunto contendo todos o vertices do grupo de destino do hiper-arco atual

conjunto nodos = self.fnRetornaProximosVerticesDoHiperArco(hiper arco)

while(True):

65

grupo = self.fnCriaGrupo(conjunto nodos)

self.contador id item = self.contador id item + 1

item = TItem(tempo,len(conjunto nodos),nivel, grupo, item pai, self.contador id item)

if (item.paralelismo > 0):

grupo = self.fnInsereTempo(item)

conjunto nodos, finalizados = self.fnRealizaTrabalho(conjunto nodos)

finalizados.extend(self.listaPendencias)

self.listaPendencias = []

for n in finalizados:

self.listaProntos.append(n)

# calculo do nıvel

# Se o item do nodo atual pertencer a algum agrupamento

if (n.item.agrupamento != None):

# Verifica no agrupamento, se existe algum item com o mesmo nıvel do item procurado

id item igual = self.fnVerificaSeHaNivelIgual(n.item, n.item.agrupamento)

if (id item igual != -1):

# Recupera o nivel filho do item encontrado,

nivel = n.item.agrupamento[id item igual].nivel filho

else:

# Busca o nıvel de referencia do agrupamento de itens

nivel = self.fnRetornaNivelReferencia(item)

# Gera um numero novo para ser o nıvel

nivel = nivel + n.item.grupo.index(n) + n.item.agrupamento.index(n.item)

# Se o item do nodo atual NAO pertencer a algum agrupamento

else:

if (n.item.grupo. contains (n)):

# o valor do nivel e a posicao do vertice no grupo do item

nivel = n.item.grupo.index(n)

# Salva o nıvel de referencia do agrupamento

self.fnSalvaNivelReferencia(item, nivel)

# O item filho do item atual, recebera o novo valor de nıvel recem calculado, logo este e salvo

# na variavel nivel filho do item atual

n.item.nivel filho = nivel

# fim do calculo do nıvel

for e in n.vertice.fs:

66

t = tempo + 1

if (not self.fnVerificaSeTodoOsVerticesDepentendesEstaoProntos(e)):

self.listaPendencias.append(n)

else:

self.fnCriaItens(hipergrafo, e, t, nivel , item)

tempo = tempo + 1

if (conjunto nodos == []):

break

return self.listaTempos

#—————————————————————————

# Mostra os itens, o Resultado pode visualizado analisando os itens

#—————————————————————————

def fnMostrarItensResultado(self):

i = 0

for l in self.listaTempos:

print

print i

for item in l:

item.mostrar()

i = i + 1

#—————————————————————————

# Retorna o maior valor na lista

#—————————————————————————

def fnRetornaMaior(self, lista):

maior = 0

i = 0

iTempo = 0

for valor in lista:

if (valor > maior):

maior = valor

iTempo = i

i = i + 1

return maior, iTempo

#—————————————————————————

# Soma os paralelismos dentro de uma lista de itens

#—————————————————————————

67

def fnSomaItens(self,lista):

soma = 0

for item in lista:

if (item.maior == True):

soma = soma + it.paralelismo

return soma

#—————————————————————————

# Qualifica os itens indicando quais sao os que tem o maior paralelismo dentre

# aqueles que tem o mesmo valor do nıvel

#—————————————————————————

def fnQualifica(self, lista):

for item 1 in lista:

if (item 1.maior == True):

for item 2 in lista:

if (item 2.maior == True):

if(item 1.nivel == item 2.nivel):

if (item 1.paralelismo < item 2.paralelismo):

item 1.maior = False

item 2.maior = True

else:

item 2.maior = False

item 1.maior = True

#—————————————————————————

# Faz a analise sobre os itens o mostra o resultado final na tela

#—————————————————————————

def fnCalculaParalelismo(self, hipergrafo, bMostrarItens):

# Cria os itens, indexando por tempo

self.fnCriaItens(hipergrafo, None,0,0, None)

if (bMostrarItens): # Se desejado, mostra-se ou nao os itens criados na tela

self.fnMostrarItensResultado()

# Com a lista de tempos criada, faz a analise sobre ela retornando o valor final

listaTempoFinal = []

listaSomas = []

for l in self.listaTempos:

grupo = []

for item in l:

68

if (item.agrupamento != None):

if (item.agrupamento != []):

self.fnQualifica(item.agrupamento)

soma = self.fnSomaItens(item.agrupamento)

listaSomas.append(soma)

item.agrupamento = []

else:

grupo.append(item)

self.fnQualifica(grupo)

soma = self.fnSomaItens(grupo)

listaSomas.append(soma)

maiorSoma, k = self.fnRetornaMaior(listaSomas)

listaTempoFinal.append(maiorSoma)

maior, tempo = self.fnRetornaMaior(listaTempoFinal)

return maior, tempo

#——————————————————————————-

#Inıcio do Programa

#——————————————————————————-

hipergrafo = THipergrafo()

arquivo = raw input(”Digite o nome do arquivo que contem o hipergrafo a ser analisado:”)

hipergrafo.fnLeHiperGrafo(arquivo.strip())

p = TParalelismo()

p.fnCalculaParalelismo(hipergrafo, False)

69

ANEXO C -- Estrutura de Dados

class TVertice:

dado = None

visita = None

rotulo = “ ”

tempo = 1

fs = []

bs = []

b = None

f = None

def init (self):

self.fs = []

self.bs = []

class THiperArco:

rotulo = “ ”

origens = []

destinos = []

p = None

def init (self):

self.origens = []

self.destinos = []

class THipergrafo:

lista vertices = []

lista arestas = []

def init (self):

self.lista vertices = []

self.lista hiperarcos = []