UNIVERSIDADE FEDERAL DO RIO GRANDE DO SUL
INSTITUTO DE INFORMÁTICA
PROGRAMA DE PÓS-GRADUAÇÃO EM COMPUTAÇÃO
Software Multiparadigma
Paralelo e Distribuído
por
Jorge Luis Victória Barbosa
Exame de Qualificação
EQ-36 PPGC-UFRGS
Prof. Dr. Cláudio Fernando Resin Geyer
Orientador
Porto Alegre, julho de 1999
2
Agradecimentos
Olá. Em [BAR 99, p.2] salientei que percebia o doutorado como uma
viagem. Neste momento, creio que cheguei à metade da jornada. Agradeço
aos companheiros de percurso. Eles continuam comigo e os momentos
compartilhados estão cada vez mais interessantes. A viagem continua.
"Essa habilidade do homem em separar a si próprio do ambiente, bem como em dividir e
distribuir as coisas, levou em última instância a um largo espectro de resultados negativos e
destrutivos, pois ele perdeu a consciência do que estava fazendo e, deste modo, estendeu o
processo de divisão além dos limites dentro dos quais este opera adequadamente. Em essência, o
processo de divisão é uma maneira conveniente e útil de pensar sobre as coisas, principalmente
no domínio das atividades práticas, técnicas e funcionais (por exemplo, dividir um terreno em
diferentes campos onde várias safras serão cultivadas). Todavia, quando este modo de
pensamento é aplicado de uma forma mais ampla à noção do homem a respeito de si mesmo e a
respeito do mundo todo em que vive (isto é, à sua visão de mundo pessoal), então ele deixa de
considerar as divisões resultantes como meramente úteis ou convenientes e começa a ver e a
experimentar a si próprio, e ao seu mundo, como efetivamente constituídos de fragmentos
separadamente existentes. Guiado por uma visão pessoal de mundo fragmentária, o homem
então age no sentido de fracionar a si mesmo e ao mundo, de tal sorte que tudo parece
corresponder ao seu modo de pensar. Ele assim obtém uma prova aparente de que é correta a
sua visão de mundo fragmentária, embora, é claro, negligencie o fato de que é ele próprio,
agindo de acordo com o seu modo de pensar, a causa da fragmentação que agora parece ter uma
existência autônoma, independente da sua vontade e do seu desejo."
David Bohm, A Totalidade e a Ordem Implicada ([BOH 80, p.20-21])
"O homem solitário pensa sozinho e cria novos valores para a humanidade. Inventa assim
novas regras morais e modifica a vida social. A personalidade criadora deve pensar e julgar por
si mesma, porque o progresso moral da sociedade depende exclusivamente da sua
independência. A não ser assim, a sociedade estará inexoravelmente votada ao malogro, e o ser
humano privado da possibilidade de comunicar. Defino uma sociedade sadia por este laço
duplo. Somente existe por seres independentes, mas profundamente unidos ao grupo."
Albert Einstein, Como vejo o mundo ([EIN 81, p.15])
"Es preciso que el hombre de ciencia deje de ser lo que hoy es con deplorable frecuencia:
un bárbaro que sabe mucho de una cosa.... Todo aprieta para que se invente una nueva
integrácion del saber, que hoy anda hecho pedazos por el mundo... Ha llegado a ser un asunto
urgentísimo e inexcusable da la humanidad inventar una técnica para habérselas adecuadamente
con la acumulación de saber que hoy posee. Si no encuentra maneras fáciles para dominar esa
vegetación exuberante quedará el hombre ahogado por ella. Sobre la selva primaria de la vida
vendría a yuxtaponerse esta selva secundaria de la ciencia, cuya intención era simplificar
aquélla. Si la ciencia puso ordem en la vida, ahora será preciso poner también orden en la
ciencia, organizarla - ya que no es posible reglamentarla-, hacer posible su perduración sana.
Para ello hay que vitalizarla, esto es, dotarla de una forma compatible con la vida humana que la
hizo y para la cual fue hecha. De otro modo - no vale recostarse en vagos optimismos - la
ciencia se volatizará, el hombre se desinteresará de ella... Y el movimiento que lleva a la
investigácion a disociarse indefinidamente en problemas particulares, a pulverizarse, exige una
regulácion compensatoria - como sobreviene en todo organismo saludable - mediante un
movimiento de dirección inversa que contraiga y retenga en un rigoroso sistema la ciencia
centrífuga."
José Ortega y Gasset, Mision de la Universidad ([ORT 92, p.71-72])
3
Sumário
Lista de Figuras .......................................................................................5
Lista de Tabelas.......................................................................................6
Lista de Abreviaturas ............................................................................. 7
Resumo ..................................................................................................... 8
Abstract ..................................................................................................... 9
1
Introdução ...................................................................................................... 10
1.1
Tema................................................................................................................. 10
1.2
Motivação ......................................................................................................... 10
1.3
Objetivos .......................................................................................................... 13
1.4
Estrutura do texto ............................................................................................. 13
Abrangência – Software Paralelo e Distribuído ........................................ 15
2
Concorrência, paralelismo e distribuição....................................................... 16
2.1
Definições......................................................................................................... 16
2.2
História ............................................................................................................. 22
2.3
Arquiteturas distribuídas .................................................................................. 23
2.4
Paralelismo implícito e semântica paralela ...................................................... 27
2.5
Distribuição implícita e semântica distribuída ................................................. 29
2.6
Conclusão ......................................................................................................... 31
3
Software paralelo e distribuído ....................................................................... 32
3.1
Paradigmas de software.................................................................................... 32
3.1.1
Evolução......................................................................................................... 32
3.1.2
Características ................................................................................................ 34
3.1.2.1
Convencional ............................................................................................... 34
3.1.2.2
Lógica .......................................................................................................... 35
3.1.2.3
Funcional ..................................................................................................... 37
3.1.2.4
Orientação a objetos .................................................................................... 38
3.1.2.5
Orientação a agentes .................................................................................... 39
3.2
Modelos e linguagens para exploração do paralelismo .................................... 40
3.2.1
Propriedades ideais ........................................................................................ 41
3.2.2
Classificação baseada em níveis de abstração ............................................... 43
3.2.3
Comunicação e sincronismo .......................................................................... 44
3.2.4
Paralelismo implícito e explícito .................................................................. 46
4
3.3
Paralelismo nos paradigmas de software.......................................................... 47
3.3.1
Semântica paralela nos paradigmas ............................................................... 47
3.3.2
Convencional ................................................................................................. 48
3.3.3
Lógica............................................................................................................. 48
3.3.4
Funcional........................................................................................................ 50
3.3.5
Orientação a Objetos ...................................................................................... 51
3.4
Estudos de caso ................................................................................................ 54
3.4.1
Paradigma procedimental: SR (Synchronizing Resources)............................ 54
3.4.2
Paradigma em lógica: Concurrent Prolog ..................................................... 55
3.4.3
Paradigma funcional: GPH (Glasgow Parallel Haskell) ............................... 57
3.4.4
Paradigma orientado a objetos: DPC++ ........................................................ 58
3.5
Conclusão ......................................................................................................... 60
Profundidade – Software Multiparadigma Paralelo e Distribuído .... 63
4
Software multiparadigma ................................................................................ 64
4.1
História ............................................................................................................. 64
4.2
Estudos de caso ................................................................................................ 65
4.2.1
OLI (Object Logic Integration)...................................................................... 65
4.2.2
OWB (Objects With Brain)............................................................................ 67
4.2.3
I+ ..................................................................................................................... 68
4.2.4
DLO (Distributed Logic Objects) .................................................................. 69
4.2.5
ETA (Everything buT Assignment) ................................................................ 70
4.2.6
G..................................................................................................................... 71
4.2.7
Oz ................................................................................................................... 73
4.3
Taxonomia multiparadigma ............................................................................. 74
4.4
Conclusão ........................................................................................................... 76
5
Software multiparadigma paralelo e distribuído........................................... 78
5.1
I+ ..................................................................................................................... 78
5.2
DLO (Distributed Logic Objects)..................................................................... 80
5.3
Mozart (Distributed Oz) ................................................................................... 84
5.4
Conclusão ......................................................................................................... 90
6
Conclusão .........................................................................................92
Bibliografia ..............................................................................................95
5
Lista de Figuras
FIGURA 1.1 - Estrutura do texto............................................................................. 14
FIGURA 2.1 - Organização das definições encontradas em fontes literárias .......... 19
FIGURA 2.2 - Proposta para organização das definições........................................ 20
FIGURA 2.3 - Organização de um sistema computacional distribuído................... 23
FIGURA 2.4 - Classificação dos nodos de arquiteturas distribuídas....................... 24
FIGURA 2.5 - Taxonomia para arquiteturas de sistemas computacionais .............. 25
FIGURA 2.6 - Rede de computadores fictícia ......................................................... 26
FIGURA 2.7 - Rede como arquitetura distribuída ................................................... 26
FIGURA 2.8 - Níveis de abstração da arquitetura distribuída ................................. 26
FIGURA 2.9 - Exploração automática do paralelismo ............................................ 28
FIGURA 2.10 - Exploração automática da distribuição ............................................ 30
FIGURA 2.11 - Origem da distribuição implícita e da semântica distribuída........... 30
FIGURA 3.1 - Duplicidade no uso dos paradigmas ................................................ 48
FIGURA 3.2 - Fontes de paralelismo na programação em lógica ........................... 49
FIGURA 3.3 - Modelo computacional do SR.......................................................... 55
FIGURA 3.4 - Programa Fibonacci implementado em GPH .................................. 57
FIGURA 5.1 - Objeto como processador virtual ..................................................... 79
FIGURA 5.2 - Evolução da proposta DLO.............................................................. 81
FIGURA 5.3 - Implementação de DLO ................................................................... 83
FIGURA 5.4 - Organização básica do Mozart......................................................... 88
FIGURA 5.5 - Ambiente de execução Mozart......................................................... 89
6
Lista de Tabelas
TABELA 4.1 - Classificação de modelos multiparadigma....................................... 77
7
Lista de Abreviaturas
AKL
Andorra Kernel Language
DLO
Distributed Logic Objects
DOBPS
Distributed, Object Based Programming System
DSM
Distributed Shared Memory
ECCD
Espaço Computacional Compartilhado Distribuído
EHU
Enriched Herbrand Universe
ET
Espaço de Tuplas
ETA
Everything buT Assignment
ETL
Espaço de Tuplas Lógicas
ESP
Extended Shared Prolog
GHC
Glasgow Haskell Compiler
GPH
Glasgow Parallel Haskell
GUM
Graph reduction for a Unified Machine model
LAN
Local Area Network
MI
Multiparadigma de Integração
MET
Múltiplos Espaços de Tuplas
MPI
Message Passing Interface
MUP
Multiparadigma de Unificação Parcial
MUT
Multiparadigma de Unificação Total
OLI
Object Logic Integration
OPM
Oz Programming Model
OWB
Objects With Brain
PVM
Parallel Virtual Machine
RMI
Remote Method Invocation
RPC
Remote Procedure Call
PERDIO
Persistent and Distributed Programming in Oz
SP
Shared Prolog
SR
Synchronizing Resources
WAM
Warren Abstract Machine
WAN
Wide Area Network
8
Resumo
Este trabalho dedica-se ao software multiparadigma paralelo e distribuído. O
estudo é organizado em duas etapas. A primeira aborda de forma abrangente o software
paralelo e distribuído. Neste escopo, são discutidos conceitos relacionados com
concorrência, paralelismo e distribuição. Em complemento, são apresentadas as
características dos paradigmas de desenvolvimento considerados básicos
(convencional, lógica, funcional, orientado a objetos e orientado a agentes). Logo após,
são abordados tópicos genéricos relacionados com linguagens paralelas e distribuídas.
Finalmente, é discutida a exploração do paralelismo nos paradigmas de
desenvolvimento. Neste sentido, destaca-se a apresentação de quatro estudos de caso, ou
seja: convencional (SR), lógica (Concurrent Prolog), funcional (GPH) e orientação a
objetos (DPC++).
Na segunda etapa é realizado em estudo em profundidade sobre exploração do
paralelismo em modelos multiparadigma, ou seja, modelos de desenvolvimento
criados através da integração de paradigmas básicos. Neste escopo, o texto apresenta a
evolução da proposta multiparadigma e descreve sete modelos (OLI, OWB, I+, DLO,
ETA, G, Oz) enfatizando a exploração do paralelismo. Utilizando como base o estudo
destes modelos, é apresentada uma taxonomia multiparadigma. Logo após,
apresenta-se um estudo específico sobre exploração do paralelismo em três modelos
multiparadigma (I+, DLO e Mozart).
Palavras-Chaves: Paradigmas de desenvolvimento, Software paralelo e distribuído,
Multiparadigma,
Taxonomia
multiparadigma,
Software
multiparadigma paralelo e distribuído.
9
TITLE: Distributed and Parallel Multiparadigm Software
Abstract
This work is dedicated to the study of distributed and parallel multiparadigm
software. The text is organized in two parts. The first presents a wide study about
parallel and distributed software. In this context, concepts related with concurrency,
parallelism and distribution are discussed. In complement, the characteristics of basic
development paradigms (conventional, logic, functional, object oriented, agent
oriented) are presented. After that, topics related with parallel and distributed languages
are approached. Finally, the exploitation of parallelism in development paradigms is
presented. In this context, four cases are presented, namely: conventional (SR), logic
(Concurrent Prolog), functional (GPH) and object oriented (DPC++).
The second part presents a deep study about exploitation of parallelism in
multiparadigm models. A multiparadigm model is a development technique created
through the integration of basic paradigms. In this context, the work presents the
evolution of multiparadigm proposal and describes seven models (OLI, OWB, I+, DLO,
ETA, G, Oz). Using the study of these models, it's presented a multiparadigm
taxonomy. After that, a specific study about exploitation of parallelism in three
multiparadigm models are presented (I+, DLO e Mozart).
Keywords: Development paradigm, Distributed and parallel software, Multiparadigm,
Multiparadigm taxonomy, distributed and parallel multiparadigm software.
10
1 Introdução
Este capítulo contém uma introdução ao trabalho. As próximas seções apresentam
o tema pesquisado, a motivação, os objetivos e a estrutura do texto.
1.1
Tema
Este trabalho aborda a exploração do paralelismo e da distribuição no âmbito do
software multiparadigma. Um software é dito multiparadigma quando desenvolvido
com o uso de mais de um paradigma básico ([BAR 98]). São considerados básicos os
seguintes paradigmas de software: convencional, funcional, em lógica, orientado a
objetos e orientado a agentes.
1.2
Motivação
A abstração é um dos principais instrumentos intelectuais do ser humano. Através
dela, a mente humana capta apenas as informações relevantes de uma determinada
realidade, ou seja, concentra esforços apenas no essencial e abstrai o restante. No
universo dos computadores a abstração tem sido utilizada em larga escala. Neste
contexto, sua principal função vem sendo a simplificação do uso dos sistemas
computacionais. Por exemplo, a abstração criada através da linguagem Assembly
simplificou o uso da linguagem de máquina. Por sua vez, as linguagens convencionais
de alto nível abstraíram o Assembly mas, no entanto, mantiveram a essência imperativa
da arquitetura Von Neumann. Em uma nova etapa, a criação dos paradigmas não
convencionais (por exemplo, funcional, lógica e objetos) abstraiu a natureza imperativa
do hardware e criou linguagens declarativas, as quais enfocam a descrição do problema
em detrimento da descrição do controle da execução. Estas abstrações demandam a
criação de camadas de software que simplifiquem a realidade abstraída. Por exemplo,
um montador concretiza a abstração Assembly. Por sua vez, um compilador concretiza a
abstração linguagem de alto nível. Em alguns casos, a abstração linguagem declarativa
necessita ainda de uma máquina abstrata para concretização de outra abstração, ou seja,
o código virtual. Independentemente dos níveis de abstração utilizados, a força vital do
sistema computacional possui sempre a mesma origem, ou seja, o hardware. A
abstração simplifica o uso dos computadores, mas exige vitalidade computacional para
sua concretização.
O surgimento do processamento paralelo trouxe maior vitalidade para os sistemas
computacionais. No entanto, trouxe também complexidade adicional para a fonte da
vitalidade, ou seja, o hardware. O hardware paralelo permite a exploração do
paralelismo em nível de execução. Neste nível, a paralelização do problema a ser
processado já deve ter sido realizada. Sendo assim, o paralelismo deve ser propagado
para as camadas de software criadas para simplificação do uso do computador, ou seja,
o paralelismo deve ser manipulado através do software básico.
A essência da arquitetura Von Neumann consiste em um único fluxo de controle
manipulando dados. Essa manipulação gera um único fluxo de dados. Sendo assim, Von
Neumann criou uma arquitetura para processamento seqüencial. As primeiras abstrações
criadas para simplificação do desenvolvimento de software mantiveram a mesma
essência. As linguagens imperativas são essencialmente seqüenciais, ou seja, dificultam
a exploração automática do paralelismo nas suas estruturas de controle. Sendo assim, a
abstração do paralelismo é dificultada e sua manipulação explícita estimulada. Por outro
11
lado, as linguagens declarativas abstraem a arquitetura Von Neumann e enfocam o
domínio dos problemas a serem modelados. A descrição declarativa está permeada do
paralelismo existente no domínio modelado. Neste caso, a abstração do paralelismo é
facilitada e sua manipulação implícita estimulada. Surge assim, a primeira motivação:
Primeira Motivação - Paralelismo Implícito: A exploração automática do paralelismo
implícito nos paradigmas não convencionais tem sido indicada como a melhor abstração
para simplificar o uso do processamento paralelo.
A tecnologia dos sistemas computacionais tem sofrido fortes mudanças. Os
avanços da microeletrônica vêm diminuindo o preço do hardware e aumentando seu
poder computacional. Em especial, o advento do microprocessador ocasionou uma
revolução na arquitetura dos computadores. Em complemento, o d esenvolvimento de
soluções eficientes para interconexão dos sistemas computacionais fez com que a área
de Redes de Computadores assumisse uma posição de destaque. Nos últimos anos, o
crescimento exponencial da Internet vem se destacando como um fenômeno tecnológico
e de mercado. Neste contexto, as plataformas computacionais vêm migrando de sua
natureza centralizada para uma nova realidade distribuída. Os sistemas distribuídos têm
recebido cada vez mais dedicação tanto dos centros de pesquisa quanto das empresas.
Entre os novos tópicos de pesquisa surgidos merecem destaque: uso de redes de
computadores como arquiteturas paralelas ([JOU 97], [IEE 98]), mobilidade de código e
dados através das redes ([ROY 97], [IEE 98], [LAN 98], [FER 99]) e tratamento da
heterogeneidade de hardware nas redes de computadores ([CAB 97]).
Uma análise da situação atual e das perspectivas futuras permite a previsão de que
em breve os sistemas computacionais serão compostos por uma grande variedade de
estações de alto desempenho conectadas por redes de alta velocidade organizadas em
topologias diversas (arquitetura distribuída). Este universo distribuído será a base para o
desenvolvimento de sistemas computacionais. As novas características e
potencialidades introduzidas pela realidade distribuída deverão ser exploradas.
Seguindo as tendências da evolução dos computadores, os sistemas distribuídos
necessitarão cada vez mais de abstrações que simplifiquem seu uso. A criação de
software (abstração) que viabilize o universo distribuído está se tornando uma das
principais tarefas da ciência da computação. Neste contexto, o estudo de metodologias
para o desenvolvimento de software distribuído ocupa uma posição de destaque
([SHS 89]). De forma semelhante à exploração automática do paralelismo (primeira
motivação), o principal problema para uso adequado da arquitetura distribuída consiste
na determinação de um paradigma de desenvolvimento de software que possua na sua
semântica o potencial para exploração automática da distribuição (distribuição
implícita). Através da distribuição implícita, o desenvolvimento de abstrações
distribuídas (software) será simplificada e estimulada. Sendo assim, destaca-se a
segunda motivação:
Segunda Motivação - Arquiteturas Distribuídas: Em breve, as arquiteturas
distribuídas serão a plataforma básica dos sistemas computacionais. Desta forma, tornase vital a criação de paradigmas de software que suportem de forma adequada a
semântica distribuída.
Conforme discutido durante a apresentação da primeira motivação, o
desenvolvimento de software é baseado em abstrações. Essas abstrações possuem como
base um paradigma, ou seja, uma forma de perceber e modelar o mundo real. No âmbito
do paradigma são desenvolvidas metodologias, linguagens e ferramentas. Por exemplo,
no contexto do paradigma orientado a objetos ([RUM 94]) existem metodologias,
12
linguagens de programação e ferramentas (ambientes de desenvolvimento,
compiladores, etc). Conforme salientado em [BAR 98, p.10], atualmente existem vários
paradigmas de desenvolvimento de software e uma grande variedade de linguagens de
programação.
Nos últimos anos vem crescendo o interesse da comunidade científica pelo tema
de pesquisa multiparadigma ([HAI 86], [IEE 86], [PLA 91], [WEG 93], [MUL 95],
[NGK 95], [CHA 97], [LEE 97], [BAR 98], [BAR 98a]). Os pesquisadores deste tema
propõem a criação de modelos de desenvolvimento de software através da unificação de
paradigmas básicos. Através dessa proposta buscam dois objetivos, ou seja, a superação
das limitações de cada paradigma e a e xploração das suas características consideradas
benéficas. Neste contexto, surge a terceira motivação:
Terceira Motivação – Software Multiparadigma: Atualmente, existe uma forte
tendência da comunidade científica em rever as atuais metodologias para o
desenvolvimento de software. A pesquisa multiparadigma enquadra-se neste universo.
Conforme destacado em [YAM 94] e [BAR 96] o paradigma convencional
dificulta a exploração automática do paralelismo. Este fato resulta da sua tendência em
modelar o universo através de comandos imperativos, resultando assim, em vários
níveis de dependências de dados e de controle ([BAR 93], [BAR 94]). Por outro lado, os
paradigmas não convencionais estimulam a exploração automática do paralelismo
através de sua modelagem que abstrai o controle da execução e enfoca a descrição do
domínio modelado (modelagem declarativa). Os paradigmas não convencionais tendem
a refletir no modelo as fontes naturais de paralelismo existentes no universo. Por
exemplo, o paradigma em lógica transmite para o modelo computacional o potencial de
paralelismo que está implícito na abordagem lógica do universo (paralelismo OU e
paralelismo E). Por sua vez, o paradigma orientado a objetos transmite o potencial de
paralelismo que existe no universo quando modelado através da filosofia de objetos
(paralelismo inter-objetos - entre objetos; e paralelismo intra-objeto - entre métodos de
um objeto).
A unificação de paradigmas envolve a unificação de suas características. Em
complemento, as características de cada paradigma estão relacionadas com suas fontes
de paralelismo implícito. Portanto, a unificação de paradigmas ocasiona a unificação de
fontes de paralelismo. Surge assim, o interesse na exploração automática de paralelismo
no software multiparadigma. Neste sentido, merecem destaque os estudos apresentados
em [NGK 95], [CIA 96] e [ROY 97]. Destaca-se como quarta motivação:
Quarta Motivação – Software Multiparadigma Paralelo e Distribuído: A
exploração automática do paralelismo é estimulada nos paradigmas não convencionais.
Em complemento, através da proposta multiparadigma ocorre a unificação das
características dos paradigmas. Sendo assim, tende a ocorrer também a unificação de
suas fontes de paralelismo implícito. Neste contexto, torna-se importante o estudo
relacionado com software multiparadigma paralelo e distribuído.
As quatro motivações apresentadas estimularam o desenvolvimento deste estudo,
o qual contempla a unificação de duas áreas de pesquisa da ciência da computação, ou
seja, software multiparadigma e software paralelo e distribuído. Sendo assim, define-se
software multiparadigma paralelo e distribuído como o software desenvolvido com o
uso de mais de um paradigma básico e que possua suporte para exploração de
paralelismo e distribuição. As duas primeiras motivações servem de estímulo para o
estudo em abrangência apresentado nos capítulos dois e três. Em complemento, as duas
13
últimas motivações estimularam o desenvolvimento do estudo em profundidade
documentado nos capítulos quatro e cinco.
1.3
Objetivos
O objetivo geral deste trabalho consiste na realização de um estudo abrangente
sobre software paralelo e distribuído e, em complemento, a realização de um estudo em
profundidade relacionado com software multiparadigma paralelo e distribuído.
Destacam-se como objetivos específicos:
realizar um estudo contemplando tópicos relacionados com concorrência,
paralelismo e distribuição, tais como: definições, história, vantagens,
desvantagens, aspectos sobre arquitetura de computadores e engenharia de
software;
pesquisar a evolução das técnicas de desenvolvimento de software paralelo e
distribuído;
pesquisar a relação entre paradigmas de software e modelos para exploração
do paralelismo e distribuição, enfocando aspectos tais como: características
dos paradigmas, características dos modelos e exploração do paralelismo e
distribuição nos paradigmas;
realizar estudos de caso relacionados com exploração do paralelismo e
distribuição no âmbito de diferentes paradigmas básicos;
analisar aspectos relacionados com a pesquisa multiparadigma, tais como:
definições, história e estudos de caso;
pesquisar a exploração do paralelismo e distribuição no âmbito dos modelos
multiparadigma;
realizar estudos de caso de modelos multiparadigma que suportem a
exploração do paralelismo;
difundir a cultura do software multiparadigma paralelo e distribuído;
suportar o desenvolvimento de relatórios e artigos relacionados com o tema
pesquisado.
1.4
Estrutura do texto
A figura 1.1 mostra uma visão geral da estrutura do texto. O trabalho é composto
de seis capítulos, os quais estão organizados em uma introdução, um estudo em
abrangência, um estudo em profundidade e uma conclusão geral. O primeiro capítulo
contém uma introdução ao trabalho, destacando tema, motivações, objetivos e estrutura
do texto. Os capítulos dois e três dedicam-se a um estudo abrangente sobre software
paralelo e distribuído. O capítulo dois apresenta um conjunto de tópicos introdutórios
considerados relevantes no âmbito da concorrência, paralelismo e distribuição. O
terceiro capítulo contempla o desenvolvimento de software paralelo e distribuído
enfocando aspectos relacionados com paradigmas de software. Portanto, o capítulo três
enfoca paradigmas de software e processamento paralelo e distribuído. Neste capítulo
destacam-se quatro estudos de caso sobre exploração de paralelismo em diferentes
paradigmas (SR, Concurrent Prolog, GPH e DPC++). A conclusão do capítulo três
14
pode ser considerada a conclusão do estudo em abrangência. Os próximos dois capítulos
apresentam um estudo em profundidade que contempla especificamente software
multiparadigma paralelo e distribuído. O capítulo quatro contém uma introdução à
pesquisa multiparadigma. O quinto capítulo enfoca a exploração do paralelismo e
distribuição no âmbito dos modelos multiparadigma. Destacam-se neste capítulo três
estudos de caso relacionados com exploração de paralelismo e distribuição em
propostas multiparadigma (I+, DLO e Mozart). A conclusão do capítulo cinco pode ser
percebida como a conclusão do estudo em profundidade. Finalmente, o sexto capítulo
contém uma conclusão geral do trabalho.
Introdução
Capítulo 1
Estudo em Profundidade
Estudo em Abrangência
Software Multiparadigma
Software Paralelo e Distribuído
Paralelo e Distribuído
Capítulos 2 e 3
Capítulos 4 e 5
Conclusão Geral
Capítulo 6
FIGURA 1.1 – Estrutura do texto
Estudo
em
Abrangência
Software Paralelo e Distribuído
Capítulo 2 - Concorrência, paralelismo e distribuição.......16
Capítulo 3 - Software paralelo e distribuído ......................32
16
2 Concorrência, paralelismo e distribuição
Este capítulo apresenta uma introdução ao universo da concorrência, paralelismo e
distribuição. O texto não aborda de forma exaustiva idéias já documentadas sobre o
assunto. Foram escolhidos e discutidos tópicos considerados relevantes. Em especial,
são propostas novas definições que servirão de base para o restante do texto e trabalhos
futuros. O capítulo é composto de seis seções. A primeira seção dedica-se à discussão e
organização de definições já existentes na área. Destaca-se nesta seção a introdução do
termo arquitetura distribuída. Em complemento, a seção 2.2 apresenta um breve
histórico relacionado com os termos concorrência, paralelismo e distribuição. Por sua
vez, a seção 2.3 aperfeiçoa a definição de arquitetura distribuída introduzida na seção
2.1. Esta seção propõe uma nova organização para sistemas computacionais
distribuídos. A seção 2.4 discute os termos paralelismo implícito e semântica paralela.
A seção 2.5 complementa a seção 2.4 discutindo dois novos termos, ou seja,
distribuição implícita e semântica distribuída. Finalmente, a última seção contém a
conclusão do capítulo.
2.1
Definições
Uma área de estudos possui um conjunto de termos considerados básicos. Eles são
compartilhados pela comunidade que desenvolve atividades na área. A definição clara e
consensual destes termos permite uma comunicação eficiente, evitando confusões e
facilitando a apresentação de novas idéias. Na área de processamento paralelo e
distribuído existem vários termos considerados básicos, os quais foram definidos e são
consenso de grande parte da comunidade. Por exemplo, existe pouca confusão em
relação aos termos speed-up ou granulosidade. Por outro lado, existem termos bastante
utilizados que ainda não possuem uma definição amplamente aceita. Este é o caso dos
termos que compõem o título deste capítulo, ou seja: concorrência, paralelismo e
distribuição. Os próximos parágrafos apresentam uma discussão em relação a estes
termos. Inicialmente, são apresentadas e discutidas definições encontradas em várias
publicações da área. Logo após, é apresentada uma proposta para organização das
definições. Por fim, encontram-se considerações diversas relacionadas com os termos
em análise.
No texto [AND 83, p.4], Andrews e Schneider afirmam que um programa
seqüencial especifica uma lista de comandos e sua execução é denominada processo.
Um programa concorrente especifica dois ou mais processos que podem ser
executados em paralelo. Os autores afirmam ainda que processos podem compartilhar
um processador ou podem ser executados em vários processadores. O primeiro caso é
denominado multiprogramação. O segundo caso recebe o nome de
multiprocessamento se os processadores compartilham memória ou recebe o nome de
processamento distribuído se os processadores são conectados por uma rede de
comunicação. Essas três definições abordam a forma de execução dos processos e não
possuem relação com o desenvolvimento dos programas. Neste contexto, merece
destaque que Andrews e Schneider caracterizam processamento distribuído pela
conexão dos processadores através de uma rede, não importando a distância física entre
eles.
Bal, Steiner e Tanenbaum ([BAL 89, p.262]) afirmam que não existe consenso na
literatura quanto à definição de um sistema computacional distribuído e dedicam uma
seção do seu artigo para criação de uma definição. No entanto, os autores salientam que
17
existe consenso em relação a uma idéia, ou seja, todas as definições apresentadas
requerem a presença de múltiplos processadores. Os autores não distinguem software
distribuído de hardware distribuído. No texto [BAL 89, p.263], os autores afirmam que
multiprocessadores são vários processadores autônomos compartilhando uma
memória. Afirmam ainda que multicomputadores não compartilham memória e se
comunicam pela troca de mensagens. Uma comparação dessas definições com as
afirmações do texto [AND 83] permite a criação da seguinte relação entre as idéias dos
autores: multiprocessadores suportam o multiprocessamento (memória compartilhada) e
multicomputadores suportam o processamento distribuído (memória distribuída).
Finalmente, Bal, Steiner e Tanenbaum apresentam a seguinte definição formal: um
sistema de computação distribuída consiste de múltiplos processadores autônomos que
não compartilham memória, mas cooperam via troca de mensagens através de uma rede
de comunicação.
Em complemento, Andrews ([AND 91, p.49]) afirma que programação
concorrente é a atividade de construção de um programa contendo múltiplos processos
que cooperam na realização de tarefas. Afirma ainda que um programa distribuído é
um programa concorrente no qual os processos se comunicam através da troca de
mensagens. Neste caso, o autor vincula o termo distribuído ao sistema de comunicação
em nível de programação, abstraíndo completamente o hardware. Sendo assim,
Andrews cria uma distinção entre software e hardware distribuído. A definição de
processamento distribuído apresentada em [AND 83, p.4] relaciona-se com o hardware
e a definição de programação distribuída discutida em [AND 91, p.49] com o software.
Basta que em nível de programação os processos se comuniquem apenas por troca de
mensagens para que a programação seja distribuída, mesmo que o hardware possua
apenas um processador ou existam vários processadores compartilhando memória.
Andrews classifica um programa distribuído como um tipo de programa concorrente.
Sendo assim, os programas concorrentes podem ser classificados em distribuídos (sem
compartilhamento de dados) e não distribuídos (com compartilhamento de dados).
Existe uma distinção entre a definição de Andrews e a definição apresentada em
[BAL 89]. Andrews não define sistema distribuído, mas sim, software e hardware
distribuídos. Por exemplo, para Andrews um programa distribuído pode ser executado
em um hardware que possua apenas um processador. Neste caso, Andrews não se
enquadra no consenso citado por Bal, Steiner e Tanenbaum
Andrews e Olsson ([AND 92, p.1]) salientam que programação concorrente
consiste na escrita de programas que possuam múltiplos processos, os quais podem ser
executados em paralelo. Afirmam ainda que, um programa concorrente especifica
dois ou mais processos que cooperam na realização de uma tarefa. Além disso, afirmam
que cada processo consiste de um programa seqüencial. Os processos cooperam através
de comunicação, a qual por sua vez leva à necessidade de sincronização. A
comunicação e sincronização são gerenciadas pela escrita e leitura em variáveis
compartilhadas ou pelo envio e recebimento de mensagens. Neste texto, torna-se clara a
distinção entre concorrência e paralelismo. Concorrência está ligada à existência de
várias tarefas criadas pelo programa (processos), as quais podem ser executadas em
paralelo. Neste caso, o paralelismo está relacionado com a existência de múltiplos
processadores, ou seja, paralelismo está relacionado com hardware. Os autores
destacam ainda a necessidade de especificação dos processos em nível de programação.
No entanto, não salientam como os processos devem ser especificados. Sendo assim,
para Andrews e Olsson a concorrência não envolve questões relacionadas com
18
hardware. Não importa o tipo de equipamento utilizado para execução, a concorrência
está ligada a linguagem de programação.
O texto [SKI 98] dedica-se ao estudo de modelos e linguagens para computação
paralela. O segundo capítulo é dedicado à apresentação de conceitos básicos sobre
paralelismo. Destaca-se a distinção entre paralelismo virtual e paralelismo físico. Os
autores definem paralelismo virtual como o número de processos independentes
criados por um programa. Em complemento, definem paralelismo físico como o
número de processos que podem ser executados simultaneamente, ou seja, o número de
processadores existentes na arquitetura. As definições de paralelismo virtual e físico
equivalem as definições de concorrência e paralelismo apresentadas por Andrews
([AND 92]). Da mesma forma que Andrews, os pesquisadores Skillicorn e Talia
enfocam de forma distinta software e hardware. Em [SKI 98] não são discutidas
definições relacionadas com distribuição, apenas com paralelismo.
Briot, Guerraoui e Löhr ([BRI 98]) criaram um artigo sobre concorrência e
distribuição na programação orientada a objetos. Os autores dedicam uma seção do seu
texto à discussão das distinções entre concorrência e distribuição. Afirmam os autores
que existem diferentes formas para execução de um programa concorrente. O programa
pode ser executado em um uniprocessador usando timesharing ou em um computador
paralelo. Desta forma, enquanto concorrência é uma propriedade semântica de um
programa, paralelismo está relacionado com sua conversão e execução, as quais são
realizadas pelo compilador e outros softwares do sistema. Afirmam ainda, que em
contraste com paralelismo, o qual pode ser visto como uma implementação da
concorrência, distribuição é uma noção independente. Distribuição não implica
necessariamente concorrência: um programa puramente seqüencial pode ser executado
fora da máquina origem usando chamadas remotas de procedimento, as quais
caracterizam uma abordagem distribuída. Além disso, distribuição implica falhas
independentes, ou seja, se parte de um programa falhar, o restante do programa pode
continuar. Por outro lado, em um programa concorrente não distribuído é usual assumir
uma semântica de falha total, ou seja, o programa deve executar de forma completa.
Se parte dele falha, todo o programa deve falhar. Destaca-se no artigo em questão, a
classificação do paralelismo como implementação da concorrência. Os autores vinculam
concorrência com programação e paralelismo com execução. Neste sentido, as
definições apresentadas assemelham-se às idéias de Andrews ([AND 83, p.4]). Além
disso, é interessante a distinção entre concorrência e distribuição. Afirmam os autores
que um programa não concorrente pode ser distribuído, ou seja, mais uma vez
distingüe-se a linguagem de programação da sua conversão e execução. Um programa
seqüencial pode ter uma execução distribuída. Finalmente, merece destaque o enfoque à
tolerância a falhas. Os autores vinculam distribuição com suporte a falhas e afirmam
que um programa concorrente possui uma semântica de falha total.
Ainda neste contexto, destacam-se os comentários apresentados no projeto
PERDIO [SMO 95a]. Este projeto está servindo de base para a criação do sistema
Mozart ([ROY 99]). Em [SMO 95a, p.5], os autores dedicam uma seção para discussão
dos termos concorrência, paralelismo e distribuição. Eles afirmam que concorrência é
um conceito relacionado com programação. Um linguagem é dita concorrente se suporta
a criação de múltiplas computações, as quais se comunicam e sincronizam. Afirmam
ainda que, paralelismo é um conceito relacionado com hardware. O paralelismo ocorre
quando o hardware executa mais de uma tarefa no mesmo instante de tempo. Em um
linguagem pode existir concorrência sem suporte de hardware paralelo. Além disso,
pode existir execução paralela sem concorrência na linguagem. No entanto,
19
concorrência aumenta o potencial para exploração do paralelismo. Em complemento,
afirmam os autores que distribuição é um conceito relacionado com software e
hardware. Um sistema computacional distribuído é uma rede de computadores. Um
programa distribuído é aquele que executa tarefas em mais de um computador de um
sistema distribuído. Sendo assim, distribuição necessita de paralelismo (hardware) e
concorrência (software).
Os parágrafos anteriores apresentam um conjunto de definições oriundas de várias
fontes literárias. Estas definições introduzem várias idéias importantes, mas no entanto,
não definem de forma clara os termos concorrência, paralelismo e distribuição.
Dependendo do texto, estes termos assumem diferentes significados. A figura 2.1
apresenta uma organização para as definições apresentadas nos parágrafos anteriores. A
base dessa organização são os textos de Andrews et al ([AND 83], [AND 91] e
[AND 92]). Conforme mostra a figura, os termos estão organizados em dois universos,
ou seja, software e hardware. A concorrência fica restrita ao universo de software,
enquanto o paralelismo fica restrito ao universo de hardware. Por outro lado, a
distribuição aparece em ambos os universos como um caso particular quando não existe
memória compartilhada (em nível de software ou hardware).
Programa não distribuído (Dados compartilhados)
Software: Concorrência
(Colaboração de múltiplas tarefas)
Programa distribuído (Troca de mensagens)
Multiprocessamento – Multiprocessadores
Hardware: Paralelismo
(Múltiplos processadores)
(Memória compartilhada)
Processamento distribuído - Multicomputadores
(Memória distribuída)
FIGURA 2.1 - Organização de definições encontrados em fontes literárias
A classificação mostrada na figura 2.1 pode ser aperfeiçoada. Merecem destaque
as seguintes melhorias propostas neste trabalho:
Inserção de situações híbridas: Um modelo de programação concorrente
pode suportar ambas formas de comunicação entre processos, ou seja,
compartilhamento de variáveis e troca de mensagens. Surge assim, uma
situação híbrida em nível de software, denominada concorrência híbrida. Em
complemento, uma arquitetura com múltiplos processadores pode suportar
ambas formas de comunicação, ou seja, memória compartilhada e troca de
mensagens. Surge assim, uma situação híbrida em nível de hardware,
denominada paralelismo híbrido;
Revisão da classificação “Programação Concorrente Distribuída”: O
simples fato de troca de mensagens entre processos não caracteriza
distribuição. A distribuição é uma qualidade espacial, e portanto está
20
relacionada com a existência de elementos de processamento separados e,
portanto, que se comunicam somente através de troca de mensagens. Esta
observação está de acordo com a definição apresentada em [BAL 89, p.263].
No entanto, não está de acordo com a definição apresentada por Andrews
([AND 91, p.49]).
Tendo como base a figura 2.1 e as melhorias propostas, surge a classificação
apresentada na figura 2.2.
Baseada em compartilhamento (Dados compartilhados)
Software: Concorrência
(Múltiplos processos)
Baseada em mensagens (Troca de mensagens)
Híbrida
Baseado em compartilhamento (Memória compartilhada)
Hardware: Paralelismo
Baseado em mensagens (Memória distribuída) = Distribuição
(Múltiplos processadores)
Híbrido
FIGURA 2.2 - Proposta para organização das definições
A figura 2.2 continua organizando as definições em dois universos, ou seja,
software e hardware. No entanto, são criadas novas classificações em cada universo. Em
nível de software, a concorrência pode ser baseada em compartilhamento, baseada em
mensagens ou híbrida. Em complemento, em nível de hardware o paralelismo segue a
mesma classificação. O paralelismo baseado em mensagens é classificado como
distribuição. Neste contexto, surgem três novos termos, ou seja, arquitetura paralela,
arquitetura distribuída e arquitetura híbrida. Uma arquitetura paralela possui múltiplos
processadores e, portanto, suporta paralelismo. Um arquitetura distribuída é uma
arquitetura paralela que suporta somente paralelismo baseado em mensagens. Em
complemento, arquitetura híbrida é uma arquitetura paralela que suporta ambos os
tipos de paralelismo. Merece destaque ainda, que em uma arquitetura distribuída a
distância física existente entre os processadores é relativa. Por exemplo, um computador
que suporte paralelismo baseado em mensagens constitui uma arquitetura distribuída.
De forma semelhante, uma LAN (Local Area Network) ou uma WAN (Wide Area
Network) podem também ser percebidas como arquiteturas distribuídas. A seção 2.3
discute em detalhes uma proposta para organização das arquiteturas distribuídas.
As definições apresentadas por diferentes autores podem ser enquadradas na
classificação proposta na figura 2.2. Por exemplo, Skillicorn e Talia ([SKI 98])
organizam o paralelismo em virtual e real. Em relação a figura 2.2, o paralelismo virtual
equivale à concorrência (software) e o paralelismo real equivale ao paralelismo
(hardware). Sendo assim, podem ser usados os termos paralelismo real e virtual em
comunhão com os termos: baseado em compartilhamento, baseado em mensagens ou
híbrido. Por exemplo, paralelismo virtual baseado em compartilhamento ou paralelismo
real baseado em mensagens (distribuição).
21
Tendo como base a classificação proposta nos parágrafos anteriores, pode ser
criada a seguinte classificação para o software:
Software Concorrente:
concorrência;
Software
direcionado
para
exploração
da
Software Paralelo: Software direcionado para arquiteturas paralelas;
Software Distribuído: Software direcionado para arquiteturas distribuídas;
Software Híbrido: Software direcionado para arquiteturas híbridas.
Neste caso, a palavra direcionado abrange dois universos, ou seja,
desenvolvimento e execução. No âmbito do desenvolvimento um software é dito
direcionado se trata de forma explícita. Por exemplo, uma linguagem é concorrente se
suporta explicitamente a gerência de processos (criação, destruição, comunicação,
sincronismo, etc). Em complemento, uma linguagem de programação é paralela se
contém estruturas que suportam a gerência explícita de arquiteturas paralelas, ou seja,
suporta explicitamente a gerência de processadores (escalonamento, balanceamento de
carga, etc). Por outro lado, no âmbito da execução, um software é direcionado se é
executado ou suporta a execução em um determinado tipo de arquitetura. Por exemplo,
um software é paralelo se é executado ou suporta a execução de programas em
arquiteturas paralelas. Esta proposta de classificação é genérica e pode ser utilizada em
qualquer tipo de software. Por exemplo, os termos programa, programação, compilador
e sistema operacional podem ser utilizados em conjunto com os termos concorrente,
paralelo, distribuído e híbrido.
Merece destaque ainda, a situação em que a exploração da concorrência,
paralelismo ou distribuição ocorre de forma automática. Neste caso, as linguagens de
programação e os programas não são classificados como concorrentes, paralelos ou
distribuídos, pois não realizam nenhum tratamento de forma explícita. A exploração
automática desfruta das características implícitas existentes nos paradigmas ou
linguagens. Essa situação é descrita como exploração automática do potencial implícito.
Sendo assim, surgem os termos concorrência implícita, paralelismo implícito e
distribuição implícita. Por exemplo, a programação em lógica possui duas fontes para
exploração automática da concorrência, ou seja, execução de ramos da árvore de busca
(concorrência OU) ou de partes independentes do corpo das cláusulas (concorrência
E). Sendo assim, existe concorrência implícita na programação em lógica, ou seja,
existe potencial para criação automática de tarefas independentes (processos) que
cooperem na solução de um problema. Se a exploração automática for direcionada para
execução em uma arquitetura paralela, ocorre a exploração automática do paralelismo
(paralelismo OU e paralelismo E). Neste caso, está sendo explorado o paralelismo
implícito existente nos programas em lógica. No caso específico da exploração
automática direcionada para arquiteturas paralelas baseadas em mensagens (arquiteturas
distribuídas), pode ser explorada a distribuição implícita existente na linguagem de
programação. A distribuição implícita é um caso particular do paralelismo implícito.
Ambos serão discutidos nas seções 2.4 e 2.5.
As características existentes em um paradigma ou linguagem, as quais suportam a
exploração da concorrência, paralelismo ou distribuição são referidas como a semântica
concorrente, paralela ou distribuída do paradigma ou linguagem. Se as características
suportam exploração explícita, utiliza-se o termo semântica explícita. Por outro lado,
se as características permitem a exploração automática, utiliza-se o termo semântica
implícita. Por exemplo, a programação em lógica possui uma semântica concorrente
22
implícita, baseada na concorrência natural existente na lógica. Por outro lado,
normalmente as linguagens imperativas concorrentes possuem uma semântica
concorrente explícita, pois exigem do usuário a utilização de comandos explícitos para
gerenciamento de processos.
2.2
História
Os dois primeiros marcos relevantes na história da computação foram a criação do
primeiro computador digital projetado pelo matemático inglês Charles Babbage (17921871) e a criação dos primeiros computadores à válvula na década de 40 do século
atual. Durante a década de 50 surgiram os primeiros transistores e entre as décadas de
60 e 80 nasceram os primeiros circuitos integrados. Além disso, neste período foram
introduzidos os primeiros controladores independentes de dispositivos. O
aprimoramento contínuo do hardware estimulou a criação de softwares complexos que
auxiliassem na gerência dos equipamentos. Surgiram assim, os primeiros softwares
básicos (sistemas operacionais, compiladores, etc). Neste contexto, entre os anos de
1965 e 1980 foram criadas várias técnicas avançadas de software para gerência de
equipamentos. Entre elas, destacava-se a multiprogramação. Esta técnica visava o
aumento da eficiência dos computadores, permitindo que várias tarefas compartilhassem
o uso de um único processador. Surgia assim a concorrência. A evolução dos sistemas
operacionais trouxe vários aprimoramentos para a técnica de multiprogramação.
Atualmente, existem técnicas sofisticadas de escalonamento, comunicação e
sincronização. Em complemento, várias linguagens de programação suportam a
manipulação de múltiplas tarefas colaborativas.
Durante a década de 60, começaram a ser utilizados múltiplos processadores para
construção de um único computador. No entanto, os processadores eram utilizados para
fins específicos, ou seja, um deles realizava a execução de programas do usuário (CPU)
e os demais gerenciavam dispositivos (disco magnético, impressora, etc). Este evento
pode ser considerado o primeiro marco da exploração do paralelismo na computação.
No entanto, nas últimas duas décadas a demanda crescente por poder computacional
ocasionou o surgimento de computadores com múltiplas CPUs, ou seja, múltiplos
processadores genéricos dedicados à solução de problemas. Atualmente, existem vários
tipos de arquiteturas paralelas dedicadas à execução eficiente de vários tipos de
aplicações complexas, tais como, previsão do tempo e simulação aerodinâmica.
Desde o surgimento dos primeiros computadores à válvula em 1945 até
aproximadamente a metade da década de 80 os computadores eram grandes e caros. A
maioria das organizações possuía um pequeno número de equipamentos, os quais
operavam de forma independente. No entanto, a partir da década de 80 surgiram duas
tecnologias que alteraram essa situação, ou seja, os microprocessadores e as redes de
computadores. Os microprocessadores diminuiram de forma significativa o tamanho e o
preço dos computadores, permitindo sua disseminação. Em complemento, as redes de
computadores permitiram a interligação confiável e rápida entre os equipamentos. A
combinação dessas duas novas tecnologias ocasionou uma mudança significativa de
filosofia na organização dos sistemas computacionais, ou seja, os sistemas deixaram de
ser centralizados e passaram a ser distribuídos. Surge assim a forma mais comum de
distribuição, ou seja, a distribuição de computadores interligados por redes locais e de
longa distância. No entanto, deve-se ressaltar que o primeiro tipo de distribuição surgiu
no interior de apenas um computador, quando vários processadores acompanhados de
23
suas próprias memórias foram interligados para criação de uma arquitetura paralela com
memória distribuída.
2.3
Arquiteturas distribuídas
Shatz e Wang ([SHS 89, p.1]) definem um sistema computacional distribuído
como um sistema composto de um conjunto de computadores (nodos de processamento)
interconectados por uma rede de comunicação. A figura 2.3 mostra sua organização.
Afirmam ainda os autores, que o sistema distribuído é considerado fracamente acoplado
porque os processadores comunicam-se trocando mensagens através da rede. Além
disso, alguns dos nodos de processamento podem ser compostos de conjuntos de
computadores, os quais podem se comunicar através de memória compartilhada.
Através dessa afirmação, os autores destacam duas importantes características dos
sistemas distribuídos, ou seja, a organização hierárquica e a heterogeneidade. Nos
próximos parágrafos a definição de Shatz e Wang será aperfeiçoada e o termo
arquitetura distribuída será utilizado para nomear a nova organização computacional
proposta.
Nodo de
Processamento
. . .
Nodo de
Processamento
Rede de
Comunicação
Nodo de
Processamento
. . .
Nodo de
Processamento
FIGURA 2.3 - Organização de um sistema computacional distribuído
No ponto de vista de Shatz e Wang, o nodo de um sistema distribuído pode ser
composto de vários computadores. Sendo assim, o sistema distribuído fica restrito a
apenas um nível hierárquico, conforme mostrado na figura 2.3. Por outro lado, em uma
arquitetura distribuída um nodo pode ser composto de outros nodos. Sendo assim, a
arquitetura distribuída é organizada em vários níveis hierárquicos. Cada nível é
composto de vários nodos que se comunicam através de mensagens. Nos níveis mais
básicos, a definição de Shatz e Wang será aplicada, ou seja, um nodo será composto de
um conjunto de computadores, os quais também serão considerados nodos. Surgem
assim, as seguintes definições:
Definição 1: Arquitetura Distribuída
Um arquitetura distribuída é uma organização computacional formada de nodos
que se comunicam via mensagens trocadas através de um meio de comunicação.
Definição 2: Nodo
Um nodo é o componente organizacional da arquitetura distribuída.
24
Definição 3: Nodo Elementar
Um nodo elementar é formado por um ou mais processadores acessando uma
memória. Sendo assim, um uniprocessador é um nodo elementar. Essa configuração é
denominada arquitetura elementar. Em complemento, uma arquitetura paralela
baseada em compartilhamento é também um nodo elementar.
Definição 4: Nodo Composto
Um nodo composto é um nodo formado por outros nodos, os quais podem ser
elementares e/ou compostos.
Definição 5: Nodo Homogêneo
Um nodo homogêneo é um nodo composto de nodos do mesmo tipo, ou seja,
somente elementares ou somente compostos.
Definição 6: Nodo Heterogêneo
Um nodo heterogêneo é um nodo composto de nodos de tipos diferentes, ou seja,
um ou mais nodos elementares misturados com um ou mais nodos compostos.
Definição 7: Nodo Homogêneo Básico ou Nodo Básico
Um nodo básico é um nodo composto de nodos elementares.
Definição 8: Nodo Homogêneo Avançado ou Nodo Avançado
Um nodo avançado é um nodo composto de nodos compostos.
A figura 2.4 organiza hierarquicamente os possíveis tipos de nodos existentes em
uma arquitetura distribuída.
Nodo
Composto
Homogêneo
Básico
Elementar
Heterogêneo
Avançado
FIGURA 2.4 - Classificação dos nodos das arquiteturas distribuídas
Tendo como base as definições surge o primeiro postulado:
Postulado 1 - Equivalência Arquitetura Distribuída/Nodo Composto: Todo nodo
composto equivale a uma arquitetura distribuída e vice-versa.
Através deste postulado deduz-se que os tipos de nodos compostos apresentados
na figura 2.4 podem também ser utilizados para classificação das arquiteturas
distribuídas. Além disso, a terceira definição permite a criação de um segundo
postulado.
25
Postulado 2 - Relação Arquitetura Elementar/Nodo Elementar: Toda arquitetura
elementar é um nodo elementar, no entanto, nem todo nodo elementar é uma arquitetura
elementar (caso dos multiprocessadores).
As definições e postulados introduzidos nesta seção podem ser utilizadas para
criação de uma taxonomia para arquiteturas de sistemas computacionais. A figura 2.5
apresenta uma proposta de taxonomia.
Arquitetura
Paralela
Elementar
(uniprocessador)
Distribuída
Centralizada
(multicomputador)
(multiprocessador)
Homogênea
Básica
Heterogênea
Avançada
FIGURA 2.5 - Taxonomia para arquiteturas de sistemas computacionais
Nos últimos anos, o número de computadores e redes de comunicação vem
aumentando de forma significativa. Em complemento, nota-se um crescente interesse
pelo uso das redes de computadores como arquiteturas paralelas ([JOU 97], [IEE 98]).
A presente realidade permite a previsão de que em um futuro próximo as redes,
organizadas através de diversos níveis, constituirão a base para organização dos
sistemas computacionais. A figura 2.6 apresenta uma rede de computadores fictícia
composta de vinte e oito estações de trabalho organizadas em diversos níveis e
topologias. Por sua vez, a figura 2.7 mostra a mesma rede como uma arquitetura
distribuída destacando os diversos níveis de nodos. A figura 2.8 mostra a arquitetura
distribuída do ponto de vista composicional sem levar em consideração as conexões
entre as estações. Nesta figura utiliza-se o círculo como representação de nodos
compostos e o quadrado como representação de nodos elementares. A figura mostra a
evolução dos detalhes da arquitetura na medida em que é decomposto cada nodo.
Assim, ficam explícitos os vários níveis de abstração da arquitetura distribuída
Do ponto de vista de distribuição espacial, as redes podem ser classificadas em
dois tipos, ou seja, LAN's e WAN's. Ambos os tipos podem ser organizados em
26
arquiteturas distribuídas e representados através da notação mostrada nas figuras 2.6,
2.7 e 2.8. Tomando-se como exemplo as redes de computadores existentes em um país,
pode-se considerar o país como o primeiro nodo da arquitetura distribuída (WAN
nacional interligando os estados). Por sua vez, as WAN's de cada estado comporiam os
nodos do segundo nível. Em um terceiro nível poderiam ser encontradas as WAN's dos
municípios conectados à rede estadual. Por último, em cada município poderiam haver
várias LAN's (universidades, empresas, ambientes domésticos, etc).
FIGURA 2.6 - Rede de computadores fictícia
FIGURA 2.7 - Rede como arquitetura distribuída
FIGURA 2.8 - Níveis de abstração da arquitetura distribuída
27
As principais vantagens introduzidas pelas arquiteturas distribuídas são:
Escalabilidade: o poder de processamento (poder das CPU's) de uma
arquitetura distribuída está diretamente relacionado com a quantidade e o
poder dos seus nodos elementares. Sendo assim, o simples acréscimo de novos
nodos ou a simples troca de nodos já existentes por outros mais poderosos
aumenta o potencial da arquitetura. Esta flexibilidade é valiosa para
organização dos sistemas computacionais. A eficiência de uma arquitetura
distribuída depende ainda da velocidade dos canais de comunicação e da
qualidade do software que gerencia o sistema. Neste sentido, a gerência da
escalabilidade assume uma posição de destaque;
Confiabilidade: a arquitetura distribuída permite a implementação de várias
técnicas de tolerância a falhas baseadas na redundância introduzida pela
existência de múltiplos nodos elementares (múltiplos recursos, tais como:
processadores e discos). As características introduzidas pelas arquiteturas
distribuídas trazem novos problemas de confiabilidade que devem ser
resolvidos por novas técnicas de tolerância a falhas. Por exemplo, o fluxo de
mensagens entre nodos é uma fonte de falhas que deve ser cuidadosamente
pesquisada. O simples envio de uma mensagem não significa sua recepção.
Vários fenômenos criam riscos durante sua viagem entre emissor e receptor;
2.4
Localidade: a natureza distribuída da arquitetura descrita nessa seção é
bastante atraente para organização dos sistemas computacionais, pois permite
a distribuição espacial dos recursos. Essa característica coincide com a forma
da humanidade organizar suas instituições. Atualmente, os computadores estão
distribuídos em vários níveis dentro de cada organização humana (países,
estados, municípios, cidades, bairros, universidades, empresas, ambientes
domésticos, etc). As arquiteturas distribuídas refletem de forma natural essa
realidade.
Paralelismo implícito e semântica paralela
Nos últimos anos o uso pleno do potencial de processamento disponível nas
arquiteturas paralelas vem sendo buscado através do desenvolvimento de softwares que
explorem o paralelismo de forma adequada. Essa exploração "adequada" envolve
questões relacionadas com a filosofia do desenvolvimento de software. A execução
paralela exige a existência de paralelismo em nível de execução. Este paralelismo chega
até a plataforma de execução através de várias camadas de desenvolvimento de
software. Sendo assim, surge a questão: onde encontra-se a gênese do paralelismo que
será explorado em nível de execução? Em ressonância com essa questão surge outra:
quais são as fontes que permitem a gênese do paralelismo? A solução destas questões é
primordial para compreensão do paralelismo como solução para o aumento do poder de
processamento dos sistemas computacionais. Vários textos já abordaram este problema
através de diversos enfoques ([BAR 96]).
Conforme analisado em [BAR 96, p.25], existem duas filosofias para exploração
do paralelismo, ou seja, paralelismo implícito e explícito. O paralelismo explícito
propõe a detecção do paralelismo pelo programador e sua inserção explícita nos
programas através de mecanismos específicos de software. Por sua vez, o paralelismo
implícito pretende a detecção automática do paralelismo e sua exploração através de
mecanismos inseridos nos softwares básicos dos sistemas computacionais. Ambas
28
filosofias dependem das questões apresentadas no parágrafo anterior. As estratégias
para exploração explícita ou implícita do paralelismo somente podem ser definidas se,
anteriormente, forem determinadas as fontes do paralelismo. Além disso, a facilidade
com que uma ou outra solução é implementada depende do potencial de paralelismo
disponível originalmente.
As fontes de paralelismo estão diretamente relacionadas com o universo que
sofrerá a modelagem computacional. Neste caso, a palavra sofrerá parece bastante
adequada, pois transmite a impressão de perda de informação que toda modelagem
impõe à realidade modelada. O processo de abstração utilizado na modelagem busca
capturar os aspectos relevantes da realidade que devem ser inseridos no modelo. Com o
intuito de viabilizar essa tarefa, foram criadas diversas metodologias baseadas em vários
paradigmas de desenvolvimento de software. Conforme destacado em [BAR 98, p.1011] a palavra paradigma possui diversas interpretações. No contexto deste trabalho, um
paradigma é um modelo ou padrão para percepção de um universo. Os textos [KUH 70]
e [KUH 77] são adequados para aprofundamento dos estudos sobre paradigmas no
âmbito da ciência.
As fontes de paralelismo estão relacionadas com os paradigmas utilizados para
modelagem e, em última instância, estão relacionadas com o universo a ser modelado.
Se o universo modelado não possuir naturalmente fontes de paralelismo, não importa o
paradigma utilizado na sua modelagem, o modelo computacional resultante não
possuirá paralelismo implícito. Por outro lado, se o universo modelado contiver
paralelismo em potencial, o paradigma utilizado na modelagem deve transferí-lo para o
modelo computacional, viabilizando assim sua exploração automática. A figura 2.9
mostra uma visão da exploração automática do paralelismo.
Realidade
Universo
Fontes de
Paralelism o
M odelagem Sublim inar
do paralelism o
Sem ântica
Paralela
Im plícita
Modelo
Com putacional
Paralelism o
Im plícito
Exploração autom ática
do paralelism o
Execução
Paralela
FIGURA 2.9 - Exploração automática do paralelismo
Neste ponto do texto, algumas constatações merecem destaque:
a transmissão do potencial de paralelismo entre universo e modelo pode ser
subliminar, ou seja, o paralelismo pode ser refletido de forma natural e, até
mesmo, inconsciente. Sendo assim, durante o processo de modelagem não
serão criados empecilhos para posterior exploração automática do paralelismo.
Neste caso, o paradigma deve suportar abstrações que transmitam as fontes de
paralelismo do universo para o modelo, ou seja, o paradigma deve possuir uma
semântica paralela implícita (figura 2.9). As abstrações utilizadas no
29
paradigma devem carregar o paralelismo, ou seja, o paradigma deve estar
permeado de paralelismo;
o paralelismo possui sua gênese no universo modelado. Sendo assim, a
exploração automática do paralelismo é um compromisso de toda a plataforma
de software, desde a modelagem até a execução. As diversas camadas de
software devem propagar as fontes de paralelismo desde o universo modelado
até o hardware paralelo. Sendo assim, parece interessante que o
desenvolvimento desses softwares seja orientado por esse objetivo em comum.
Neste caso, todas as camadas de software devem utilizar a mesma semântica
paralela como orientação no seu desenvolvimento;
2.5
considerando-se que o paralelismo possui sua gênese no universo e que vários
paradigmas podem ser utilizados para modelagem do mesmo universo (vários
tipos de paralelismo no mesmo universo), parece que um interessante tópico
de pesquisa seria a investigação da natureza do paralelismo existente na
realidade onde residem os universos a serem modelados. Através dessa busca,
poderiam ser detectadas as diversas oportunidades de paralelismo existentes na
semântica da realidade. Um bom ponto de partida, seria o estudo das
oportunidades de paralelismo implícito introduzidas pelos atuais paradigmas
de software (estudo apresentado na seção 3.3) e uma tentativa de unificação
dessas oportunidades através de um modelo que unisse os paradigmas
(modelos multiparadigma discutidos no estudo em profundidade apresentado
neste trabalho).
Distribuição implícita e semântica distribuída
Conforme analisado na seção 2.4 e mostrado na figura 2.9, a utilização de uma
semântica paralela implícita permite a transferência das fontes de paralelismo do
universo para o modelo computacional, facilitando assim a exploração automática do
paralelismo. Por sua vez, a seção 2.3 define arquitetura distribuída e cria uma
proposta para classificação dos sistemas computacionais (figura 2.5). Neste contexto,
torna-se interessante uma análise do potencial existente nas arquiteturas distribuídas.
Esta análise pode ser baseada nas seguintes questões: quais são as características das
arquiteturas distribuídas que podem ser exploradas? Como modelar as fontes de
distribuição de forma a potencializar a exploração das arquiteturas distribuídas? Essas
questões podem ser melhor compreendidas através da figura 2.9. Naquela figura, se o
bloco que representa a execução paralela for considerado uma arquitetura distribuída,
então a semântica que permea o desenvolvimento de software deve estabelecer quais as
fontes de distribuição serão mais adequadas para a arquitetura distribuída. Neste caso, o
interesse está direcionado para as fontes de distribuição e para uma semântica
distribuída.
A natureza da arquitetura distribuída cria várias oportunidades. Neste universo, o
aumento de desempenho surge como oportunidade, mas não como objetivo. Por outro
lado, nos últimos anos vem aumentando o interesse na utilização de arquiteturas
distribuídas como arquiteturas de alto desempenho. Este fenômeno possui várias
motivações dentre as quais se destacam: a proliferação de redes de computadores, o
aumento substancial do poder computacional das estações de trabalho, a subutilização
destas estações e o aumento da velocidade de transmissão nas redes de comunicação.
Considerando-se que existe uma forte tendência no aumento da força dessas
30
motivações, pode-se afirmar que existe uma forte tendência no aumento do interesse em
arquiteturas distribuídas.
As arquiteturas distribuídas possuem características que introduzem diversas
vantagens (o final da seção 2.3 salienta três delas). A exploração adequada dessas
características e oportunidades envolve as várias abstrações utilizadas no
desenvolvimento dos sistemas computacionais. A análise realizada na seção 2.4 para
exploração automática do paralelismo é válida também para o caso específico da
exploração automática da distribuição. O potencial de distribuição existente no universo
modelado pode ser transferido de forma subliminar para o modelo computacional.
Sendo assim, surge a definição de distribuição implícita, ou seja, a exploração
automática das caraterísticas distribuídas do universo modelado. Conforme analisado na
seção 2.4, o processo de exploração implícita demanda a criação de uma semântica
implícita, neste caso, uma semântica distribuída implícita. Neste contexto, seria
interessante o estudo das possíveis fontes de distribuição existentes no mundo real.
Além disso, a semântica distribuída deve ser considerada durante a criação de
paradigmas de software que almejem a exploração da distribuição implícita nos seus
modelos computacionais. A figura 2.10 representa a exploração automática da
distribuição.
Realidade
Fontes de
Distribuição
Universo
Modelagem Subliminar
da distribuição
Semântica
Distribuída
Implícita
Modelo
Computacional
Distribuição
Implícita
Exploração automática
da distribuição
Arquitetura
Distribuída
FIGURA 2.10 - Exploração automática da distribuição
A figura 2.11 mostra o surgimento do conceito de distribuição implícita, tendo
como base as definições de paralelismo implícito e arquiteturas distribuídas.
Paralelismo Implícito Semântica Paralela
Arquiteturas
Distribuídas
Distribuição Implícita Semântica Distribuída
FIGURA 2.11 - Origem da distribuição implícita e da semântica distribuída
31
2.6
Conclusão
A abordagem apresentada no capítulo dois serve de base para o restante do texto.
Esta abordagem constitui a primeira parte do estudo em abrangência relacionado com
software paralelo e distribuído. Foram discutidas e organizadas as definições de
concorrência, paralelismo e distribuição. Em complemento, foram propostas três
taxonomias, ou seja: conceitos básicos da área (figura 2.2), nodos de um arquitetura
distribuída (figura 2.4) e arquiteturas de sistemas computacionais (figura 2.5).
Finalmente, foram discutidas questões relacionadas com semântica paralela e distribuída
e exploração automática do paralelismo e distribuição (paralelismo implícito e
distribuição implícita)
Destacam-se como principais conclusões obtidas neste capítulo:
o termo concorrência está relacionado com software (múltiplos processos) e os
termos paralelismo e distribuição estão relacionados com hardware (múltiplos
processadores). No entanto, os três termos podem ser utilizados para designar
tipos de software conforme discutido na seção 2.1;
a distribuição é um caso especial de paralelismo, onde a memória é distribuída
e a comunicação é baseada em mensagens. Esta constatação é válida também
para classificação de arquiteturas, ou seja, uma arquitetura distribuída é um
tipo de arquitetura paralela;
a distância entre os processadores em uma arquitetura distribuída é relativa, ou
seja, do ponto de vista de classificação de arquiteturas não existe diferença
entre um computador paralelo baseado em memória distribuída e uma rede de
computadores;
a exploração automática do paralelismo deve ser baseada em uma semântica
paralela implícita existente na plataforma de desenvolvimento (linguagem ou
paradigma). No caso específico do paralelismo baseado em mensagens,
surgem características e oportunidades especiais. Neste caso, a exploração
deve ser baseada em uma semântica distribuída implícita, a qual permita a
exploração automática da distribuição (distribuição implícita).
O próximo capítulo aborda o desenvolvimento de software paralelo e distribuído.
32
3 Software paralelo e distribuído
Este capítulo aborda o desenvolvimento de software paralelo e distribuído. Neste
contexto, o estudo é direcionado para o relacionamento entre os paradigmas de software
e a exploração do paralelismo. A compreensão dessa relação serve de base para o estudo
em profundidade apresentado a partir do quarto capítulo. A seção 3.1 enfoca os
paradigmas de software. Esta seção apresenta a evolução e as características de cinco
paradigmas considerados básicos (convencional, lógica, funcional, orientado a objetos e
orientado a agentes). Por sua vez, a seção 3.2 aborda tópicos relacionados com a criação
de modelos e linguagens para exploração de paralelismo. Foram escolhidos quatro
tópicos considerados relevantes para o presente estudo. Tendo como base as duas
primeiras seções, a seção 3.3 aborda aspectos relacionados com a exploração do
paralelismo nos paradigmas de software. Em complemento, a seção 3.4 apresenta quatro
estudos de caso. Finalmente, a seção 3.5 contém a conclusão do capítulo, a qual pode
ser considerada como conclusão do estudo em abrangência.
3.1
Paradigmas de software
Esta seção apresenta a evolução (seção 3.1.1) e as características (seção 3.1.2) dos
paradigmas de software. A palavra paradigma possui diversas interpretações
([KUN 70], [KUN 77]). Neste trabalho, um paradigma é um instrumento de percepção.
O paradigma determina uma forma de perceber um universo e, principalmente,
determina quais são seus elementos constituintes. Sendo assim, um paradigma de
software é um instrumento utilizado para modelagem (percepção) computacional de um
universo. Um paradigma de software possui como base a entidade de modelagem
(entidade-base). Essa entidade atua como unidade de modelagem e determina as regras
a serem utilizadas na criação no modelo. Por exemplo, no desenvolvimento orientado a
objetos, a entidade-base é o objeto e a interação entre eles (mensagens) determina a
dinâmica do universo modelado. Da mesma forma, pode-se utilizar como entidade-base:
comandos, procedimentos, funções, predicados lógicos e agentes.
3.1.1
Evolução
Os textos [FRI 92] e [BYT 95] apresentam a história da evolução das linguagens
de programação. Apesar destes textos não contemplarem de forma explícita a evolução
dos paradigmas de software, percebe-se que a evolução das linguagens incorpora a
evolução dos paradigmas.
Segundo Sterling e Shapiro ([STE 86]), embora os computadores tenham sido
criados para interagir com seres humanos, as dificuldades para construí-los fizeram com
que as primeiras linguagens de programação fossem projetadas a partir da perspectiva
dos engenheiros de computadores. Conforme destacado em ([BAR 96]), estas
linguagens sofreram forte influência dos conceitos de Von Neumann, os quais são
utilizados para construção da maioria destes equipamentos. Os usuários que não
possuem conhecimento da arquitetura Von Neumann encontram dificuldades na
utilização destas linguagens. Além disso, devido a sua orientação para o hardware, estas
linguagens diferem da forma com que o homem pensa e expressa seus conhecimentos.
Neste contexto, surge o primeiro paradigma de desenvolvimento, ou seja, o
paradigma imperativo. Este paradigma consiste na criação de sistemas computacionais
através de comandos imperativos direcionados ao computador. Estes comandos
33
permitem o estabelecimento do fluxo de controle, o qual atua nos dados gerando um
fluxo de dados. O paradigma imperativo nasce com a criação da linguagem Assembly
(1950) e se desenvolve com a criação de diversas linguagens de alto nível (Fortran em
1957, Cobol em 1959). Na medida em que aumentavam os sistemas computacionais
aumentava a busca por soluções que permitissem o domínio da complexidade. A
aplicação da máxima "dividir para conquistar" conduziu a criação dos primeiros
conceitos relacionados com modularização baseada em blocos de comandos e
procedimentos (Algol em 1960, Pascal em 1968 e C em 1972). Surge assim, o
paradigma procedimental o qual, em essência, confunde-se com o paradigma
imperativo. Ambos paradigmas são considerados pela comunidade como o paradigma
tradicional ou convencional ([BAR 96]).
Com a passagem dos anos aumentava a procura por linguagens de programação
mais adequadas à forma do homem perceber o mundo. Além disso, cientistas
interessados em determinados universos específicos (lógica, matemática, etc)
dedicaram-se à criação de novas linguagens que facilitassem a solução de problemas na
sua área de interesse. Assim, nasceram os paradigmas não convencionais, tais como o
paradigma em lógica, funcional, orientado a objetos e orientado a agentes. O
paradigma funcional é baseado no cálculo Lambda ([CHU 41]) e possui como
entidade-base a função matemática. Destacam-se como representantes do paradigma
funcional as linguagens Lisp ([MCJ 65]) e Haskell ([THO 96]). Por sua vez, o
paradigma em lógica proposto por Kowalski ([KOW 74]) é baseado na lógica
([CAS 86], [ROB 92]) e possui como entidade-base o predicado lógico. Como principal
linguagem do paradigma em lógica destaca-se o Prolog ([ROU 75]). A linguagem
Prolog tornou-se reconhecida como ferramenta prática de programação através do
compilador/interpretador proposto por Warren ([PER 78], [AIT 91]). Em 1994, Peter
Van Roy publicou um interessante artigo ([ROY 94]) abordando a evolução das
implementações seqüenciais do Prolog entre os anos de 1983 e 1993. Os paradigmas em
lógica e funcional são considerados paradigmas declarativos ([BAC 78]).
O paradigma orientado a objetos ([REN 82]) propõe a diminuição da distância
(gap semântico) existente entre a modelagem computacional e o mundo real. Neste
sentido, surge o objeto como entidade-base. O universo composto por objetos possui
diversas características (herança, polimorfismo, encapsulamento, etc). Desta forma, o
paradigma orientado a objetos alcança um nível de abstração que aproxima o
desenvolvimento de sistemas computacionais à forma usual com a qual o homem
percebe o universo em que vive. No ano de 1980 surge a primeira versão de Smalltalk e
em 1986 surgem as linguagens Eiffel e C++. Por sua vez, o paradigma orientado a
agentes ([SHO 93]) tem sido apresentado como uma especialização do paradigma
orientado a objetos. Conforme afirma Amandi ([AMA 97]) um agente é uma entidade
que tem capacidades comportamentais e um estado interno (estado mental). O estado
mental do agente inclui crenças, desejos, intenções, etc. Nota-se assim, que esse
paradigma enfatiza as características psíquicas de sua entidade-base, ou seja, o agente.
Recentemente, foram propostas diversas linguagens orientadas a agentes. Em [AMA 97]
encontra-se a descrição das seguintes propostas: Agent0, Placa, AgentSPeak, Daisy,
Metatem e Cool.
A evolução dos paradigmas é guiada pela busca de entidades-base que facilitem a
modelagem computacional. Desde os comandos imperativos (década de 50) até os
agentes (década de 90) a busca é a mesma, ou seja, um paradigma que permita a
modelagem ideal de um determinado domínio. Parece que o problema essencial para a
criação de um paradigma genérico consiste na multiplicidade dos universos de interesse
34
e, assim, a necessária multiplicidade de entidades-base. Por exemplo, alguns problemas
são resolvidos de forma mais eficiente com a utilização da entidade-base predicado
lógico. Por outro lado, outros problemas encontram soluções mais atraentes com o uso
de funções. No entanto, a grande maioria de problemas que envolvem grande
complexidade não encontram soluções elegantes (puras) no âmbito de apenas um
paradigma. Além disso, continua a busca de paradigmas que permitam uma maior
abrangência na modelagem do mundo real. Os modelos multiparadigma constituem um
esforço neste sentido. A próxima seção apresenta os paradigmas de software salientando
suas características essenciais.
3.1.2
Características
Esta seção apresenta características essenciais dos paradigmas de software.
Pretende-se assim, determinar quais as contribuições que cada paradigma oferece.
Aconselha-se os textos [FIN 96], [PRA 96], [SEB 96] e [GHE 98] para aprofundamento
dos estudos sobre paradigmas de software.
3.1.2.1 Convencional
O paradigma convencional possui como entidade-base o comando imperativo para
controle explícito do fluxo de execução. Além disso, no âmbito desse paradigma
surgiram os primeiros esforços para controle da complexidade através da
modularização. Estes esforços representam a gênese do conceito de encapsulamento no
desenvolvimento de sistemas.
Conforme salientado por Niklaus Wirth ([WIR 76]), a essência do
desenvolvimento de programas no paradigma convencional pode ser representada pela
seguinte expressão:
PROGRAMA = ALGORITMO + ESTRUTURAS DE DADOS
O algoritmo representa a seqüência de comandos que manipula o fluxo de
controle. Por sua vez, as estruturas de dados representam as informações que são
manipuladas pelo controle gerando um fluxo de dados. Neste paradigma, a modelagem
consiste na representação explícita de como um problema deve ser percebido, ou seja, o
desenvolvimento explicita detalhadamente todos os passos a serem percorridos na
solução do problema.
Merece destaque ainda, uma característica do paradigma convencional conhecida
como atribuição destrutiva. A vinculação de um conteúdo a uma variável destrói o
conteúdo anterior, ou seja, qualquer informação antes vinculada à variável é
definitivamente perdida. Sendo assim, o ato isolado de atribuição não possui valor
histórico, ou seja, não representa um crescente acúmulo de conhecimento. A natureza
volátil da variável convencional (variável introduzida pelo paradigma convencional) é
essencial para compreensão do universo dos paradigmas de desenvolvimento.
O paradigma convencional serve de base histórica para todos os demais
paradigmas. Além disso, grande parte do desenvolvimento mundial de sistemas
computacionais ainda está baseado nas ferramentas criadas por esse paradigma. Por
outro lado, nota-se que uma conseqüência da evolução dos paradigmas de
desenvolvimento é a superação do paradigma convencional. Atualmente, essa superação
é visível na migração do desenvolvimento convencional para o desenvolvimento
orientado a objetos. Vários conceitos introduzidos pelo paradigma convencional foram
35
extrapolados pela orientação a objetos. A modularização é levada ao extremo através do
conceito de encapsulamento. As chamadas de procedimentos tornam-se invocação de
métodos em objetos. A passagem de parâmetros revigora-se através da troca de
mensagens. A variável convencional é substituída pelo conceito atributo (estado) de
objeto e os procedimentos no diversos níveis de escopo transforma-se em objetos e seus
métodos. Na verdade, a superação do paradigma convencional assemelha-se a uma
metamorfose.
3.1.2.2 Lógica
A entidade-base do paradigma em lógica é o predicado lógico. O desenvolvimento
de um sistema em lógica consiste na escolha de sentenças da lógica de primeira ordem
que expressem o problema de forma declarativa (expressa o que fazer e não como
fazer). Um programa não expressa quais os caminhos para solução do problema, ou
seja, um programa não expressa controle. Segundo Hermenegildo ([HER 86]) existem
dois elementos na programação em lógica, ou seja:
Programa: Conjunto de sentenças lógicas fornecidas pelo usuário;
Avaliador: Sistema responsável pela avaliação do programa para derivação de
conclusões consistentes com as sentenças lógicas.
De forma sucinta, Kowalski ([KOW 79], [KOW 79a]) representa estes elementos
através da expressão:
ALGORITMO = LÓGICA + CONTROLE
Sendo assim, torna-se clara a distinção entre a expressão do problema (programa
ou lógica) e a forma com que este será resolvido (avaliador ou controle). Portanto, o
controle da execução dos programas em lógica é implícito e transparente para o usuário.
O usuário utiliza a lógica para expressar o problema, abstraindo-se da execução. Por sua
vez, o avaliador executa o programa. Afirma ainda Hermenegildo ([HER 86]), que o
avaliador possui um enorme grau de liberdade (não-determinismo) na escolha dos
caminhos de dedução que serão percorridos para solucionar o problema.
O não-determinismo é uma das principais características do desenvolvimento em
lógica. O texto [BAR 96] destaca a existência de duas ocasiões, durante a execução de
um programa, em que o avaliador deve escolher uma entre várias alternativas. Durante a
solução de uma resolvente, o avaliador deve escolher a próxima meta a ser reduzida.
Além disso, durante a solução de um predicado, o avaliador deve escolher a próxima
cláusula a ser solucionada. O não-determinismo existente na escolha de cláusulas pode
ser subdividido em dois tipos, ou seja, não-determinismo don't care e não-determinismo
don't know.
No não-determinismo don't care apenas uma solução é gerada por meta. Desta
forma, mesmo que uma meta possua várias soluções, apenas uma será utilizada.
Portanto, a falha de uma meta ocasiona a falha de todo o programa. No nãodeterminismo don't know são geradas todas as soluções de uma meta. Desta forma,
uma meta poderá ser resolvida diversas vezes, dependendo do número de soluções
geradas pelas metas anteriores. Sendo assim, a falha de uma meta poderá ocasionar uma
nova tentativa até que não hajam mais possibilidades de execução. A linguagem Prolog
é baseada no não-determinismo don't know e utiliza uma técnica denominada
backtracking para geração de todas as soluções possíveis durante a execução de um
programa.
36
Segundo Shapiro ([SHA 89]), a principal diferença entre a programação em lógica
e a programação convencional consiste na variável lógica e sua manipulação através da
unificação. As principais caraterísticas da variável lógica são as seguintes:
Referência a termos: Nos programas em lógica uma variável referencia um
termo e não um local de armazenamento na memória (linguagens
convencionais). Os termos são as estruturas de dados básicas da programação
em lógica ([STE 86]);
Atribuições construtivas: Após especificar um termo, a variável não pode ser
alterada para referenciar outro termo. Em outras palavras, a programação em
lógica não permite a alteração do conteúdo de uma variável inicializada,
conforme ocorre na programação convencional (atribuições destrutivas);
Escopo de cláusula: Uma variável lógica possui seu escopo restrito à cláusula
na qual é utilizada, ou seja, não existem variáveis globais;
Sem tipo: Uma variável lógica não necessita definição, ou seja, não possui um
tipo definido. As linguagens convencionais normalmente necessitam da
definição de tipos para suas variáveis;
Atribuição de variáveis: Uma variável lógica pode referenciar outra variável
ou um termo contendo várias variáveis.
Conforme afirmam Sterling e Shapiro ([STE 86]), a manipulação de dados na
programação em lógica é realizada através da unificação. Do ponto de vista de Shapiro
([SHA 86]), compreender a programação em lógica equivale a compreender o poder da
unificação. Basicamente, a unificação de dois termos consiste na busca de valores para
suas variáveis que tornem os dois termos idênticos. Desta forma, a unificação pode ser
definida como um simples e poderoso processo de casamento de padrões. O processo de
atribuição a uma variável recebe o nome de instanciação. Em [SHA 86] encontra-se
uma comparação entre o processo de unificação e primitivas de manipulação de dados
nas linguagens convencionais. Nesta comparação, Shapiro ressalta a equivalência entre
a unificação de uma meta com a cabeça de uma cláusula e a passagem de parâmetros
nas linguagens convencionais.
Em [MUL 95] encontra-se a afirmação de que a variável lógica e o sistema de
busca de soluções proporcionado pelo não-determinismo don't know são as duas
principais contribuições do paradigma de desenvolvimento em lógica. Além disso, o
texto salienta que a programação em lógica é pioneira na computação especulativa com
informações parciais (proporcionada pela unificação). O texto [MUL 95] destaca ainda
que o paradigma em lógica é uma ótima solução para o desenvolvimento de aplicações
baseadas em estruturas de dados que mudam rapidamente, tais como: linguagem
natural, geração de programas, sistemas especialistas e prova de teoremas. Em
contrapartida, o mesmo texto salienta um conjunto de problemas introduzidos pelo alto
nível de abstração da semântica declarativa da programação em lógica. Entre esses
problemas destacam-se: controle implícito é primário e inflexível (depth-first search), o
uso de primitivas não lógicas (por exemplo, built-ins aritméticos e relacionais) é
problemático e faltam condições para modelagem de grandes sistemas (por exemplo,
encapsulamento, reutilização, etc).
A programação em lógica é bastante adequada para a solução de problemas que
possam ser completamente descritos pela lógica de primeira ordem. No entanto, existem
vários problemas que não se adaptam a esse universo. Nestes casos, a eficiência da
37
programação em lógica é bastante comprometida. Alguns conceitos introduzidos pelo
desenvolvimento em lógica são valiosos e representam importantes contribuições para a
evolução dos paradigmas. Destacam-se como principais contribuições os conceitos de
variável lógica, unificação e não-determinismo.
3.1.2.3 Funcional
O paradigma de desenvolvimento funcional possui como entidade-base a função
matemática. O desenvolvimento de um sistema através do paradigma funcional consiste
na escolha de funções matemáticas que expressem o problema de forma declarativa.
Neste caso, a abstração escolhida é a função e, de forma semelhante a programação em
lógica, o programador não expressa controle no programa. Conforme descrito em
[GHE 98], o paradigma funcional possui como principais componentes:
Objetos de Dados: Estruturas de dados de alto nível, tais como, listas e
matrizes;
Funções Built-in: Conjunto de funções básicas para manipulação dos objetos
de dados;
Funções de Alta Ordem: Conjunto de funções utilizadas para construir novas
funções.
A execução de programas funcionais é baseada em dois mecanismos
fundamentais, ou seja, ligação e aplicação. A ligação é utilizada para associar valores
com nomes (semelhante à programação em lógica). Por sua vez, a aplicação de funções
é utilizada para computar novos valores.
Diferentemente das linguagens imperativas, nas quais a semântica pode ser
compreendida como uma seqüência de passos especificados pelo programa, a semântica
de um programa funcional pode ser compreendida, mais naturalmente, em termos de
aplicação de funções. Sendo assim, o cálculo Lambda ([CHU 41]) tem sido
considerado um caminho adequado para estudo da programação funcional. O cálculo
Lambda é um cálculo simples que modela o aspecto computacional das funções.
Conforme salientam Ghezzi e Jazayeri ([GHE 98]), o estudo do cálculo Lambda ajuda a
compreensão dos elementos da programação funcional e salienta a semântica funcional
do paradigma independentemente dos detalhes de uma linguagem em particular.
A linguagem Lisp ([MCJ 65], [COM 91]) destaca-se como a primeira linguagem
funcional. Lisp é uma linguagem altamente dinâmica (escopo, definição de tipos e
estruturas de dados). Durante o desenvolvimento de Lisp, surge o importante conceito
de Garbage Collection (coleta de lixo). Este técnica permite a gerência da grande
demanda de alocação de memória dinâmica exigida por Lisp. A estratégia de garbage
collection é utilizada em diversas propostas de desenvolvimento, por exemplo, no
modelo multiparadigma Oz ([SMO 95]).
Conforme salientado no texto [MUL 95], uma importante contribuição do
paradigma funcional foram os sistemas de tipos para computação. Em [GHE 98]
encontra-se uma descrição dos sistemas de tipos introduzidos pelas linguagens
funcionais e técnicas para tratamento de tipos no universo funcional. Além disso, os
textos [PRA 96] e [GHE 98] apresentam as características específicas das linguagens
Lisp e ML. Aconselha-se o livro [THO 96] para estudo da moderna linguagem
funcional Haskell.
38
Durante um longo período o paradigma funcional atuou como a primeira opção
para a computação simbólica. O surgimento da programação em lógica introduziu uma
nova opção no universo da programação declarativa e da computação simbólica. A
programação funcional adapta-se à solução de problemas que podem ser descritos por
funções matemáticas. No entanto, vários problemas não encontram uma solução
adequada através dessa representação. Além disso, o paradigma funcional compartilha
com o paradigma em lógica a falta de características consideradas vitais, pela
Engenharia de Software, para o desenvolvimento de grandes sistemas (encapsulamento,
reutilização, etc). Destacam-se entre as principais contribuições do paradigma funcional
os conceitos de sistemas de tipo e coleta de lixo.
3.1.2.4 Orientação a objetos
Conforme salienta Iara Augustin em [AUG 94] o modelo computacional de
objetos é um mundo povoado por objetos, e somente objetos, que trabalham e cooperam
entre si, através da troca de mensagens para realização de uma tarefa (Princípio da
Uniformidade [REN 82]). Sendo assim, o paradigma de desenvolvimento orientado a
objetos possui como entidade-base o objeto. Destaca ainda Augustin, que o objeto é
uma entidade que possui estado interno (atributos), que corresponde a uma memória
local, e um comportamento, que é definido pelas ações (métodos) que os objetos
dispõem para responder às solicitações (mensagens) externas ou mesmo internas ao
próprio objeto. Todo processamento é ativado por mensagens entre objetos. O
recebimento de uma mensagem faz com que o objeto execute uma ação que resulta na
alteração do seu estado interno ou no envio de mensagem para outros objetos, ou ainda
na criação de outros objetos. Destacam-se como principais conceitos relacionados com
o paradigma orientado a objetos:
Objeto: Entidade básica do modelo;
Mensagem: Sistema de comunicação que permite a troca de informações e o
sincronismo entre objetos;
Encapsulamento: Mecanismo que permite a abstração da estrutura interna do
objeto (métodos e atributos). O objeto torna-se acessível apenas através da sua
interface. O encapsulamento é a modularização levada ao extremo;
Classe: Objeto que descreve um comportamento. Serve como molde para
instanciação (criação) de objetos;
Instância: Objeto que herda um comportamento de uma classe e possui um
estado interno. Recebe mensagens e reage de acordo com seu comportamento;
Herança: Propriedade que permite a um objeto a aquisição do comportamento
de outros objetos através de especialização (aperfeiçoamento de um objeto) ou
generalização (composição de vários objetos). A herança recebida de uma
única classe é denominada herança simples e a herança recebida de várias
classes é chamada herança múltipla;
Associação Dinâmica: Definição em tempo de execução de qual método será
utilizado para resolver uma solicitação. Permite um alto grau de flexibilidade e
generalidade;
Polimorfismo: Propriedade que permite o tratamento distinto de uma
mensagem idêntica dependendo do tipo do objeto que a recebe. Evita a
necessidade de testes de discernimento entremeados ao código;
39
Reusabilidade: Qualidade que permite a reutilização de software. A
orientação a objetos possui uma série de características que facilitam a
reusabilidade (classe, polimorfismo, encapsulamento, etc). Esta qualidade é
destacada pela Engenharia de Software como uma das principais contribuições
do paradigma orientado a objetos.
Atualmente, o paradigma orientado a objetos destaca-se como sucessor do
paradigma convencional. Conforme descrito no último parágrafo da seção 3.1.2.1,
vários conceitos do paradigma convencional foram aperfeiçoados através do surgimento
da orientação a objetos. Além disso, a semântica do paradigma (objetos, mensagens,
herança, etc) é comumente utilizada no cotidiano. Sendo assim, é natural que grande
parte da comunidade sinta-se atraída pela orientação a objetos. Várias soluções
comerciais criadas recentemente (sistemas operacionais, banco de dados, etc) estão
baseadas no conceito de objetos e utilizam a nomenclatura "orientado a objetos" como
forma de marketing.
Entre as principais contribuições da orientação a objetos encontram-se os
conceitos relacionados com o suporte ao desenvolvimento de grandes sistemas, tais
como, reusabilidade baseada em encapsulamento, polimorfismo e herança. Além
disso, destaca-se a forma elegante com que essas contribuições foram organizadas
(universo de objetos que herdam e se comunicam através de mensagens). Conforme
discutido no capítulo quatro, devido a estas características a orientação a objetos tem
sido utilizada como base para a criação de vários modelos multiparadigma.
Por outro lado, a orientação a objetos possui limitações. A entidade-base objeto
torna-se inadequada para solucionar problemas em várias situações. Por exemplo, o
universo da lógica e matemática não é adequadamente modelado por objetos que trocam
mensagens. Um usuário dos paradigmas em lógica e/ou funcional não encontra na
orientação a objetos um paradigma adequado para seus problemas permeados de
processamento simbólico. Além disso, a Inteligência Artificial vem sendo considerada
um dos principais caminhos a serem percorridos para evolução da ciência da
computação. A modelagem de capacidades comportamentais (crenças, desejos,
intenções, etc) é considerada importante para criação desse caminho. Objetos não
suportam este tipo de modelagem. Em complemento, a troca de mensagens como único
mecanismo de comunicação apresenta limitações. Alguns problemas são melhor
resolvidos quando o paradigma suporta de forma natural a existência de espaços de
armazenamento compartilhados. As pesquisas relacionadas com Memória
Compartilhada Distribuída (Distributed Shared Memory - DSM [LIK 89], [TAN 95],
[PRO 96], [AMZ 97]) demonstram essa realidade mesmo nos sistemas distribuídos.
3.1.2.5 Orientação a agentes
Nos últimos anos vem crescendo o interesse dos cientistas da computação pelo
paradigma orientado a agentes ([SHO 93], [AMA 97], [POR 97], [POR 98]). No
entanto, os textos [AMA 97] e [POR 97] salientam a dificuldade para criação de uma
definição de agente. Analía Amandi afirma em [AMA 97], que agente é uma entidade
computacional com um comportamento autônomo que decide suas próprias ações. A
escolha de uma ação considera seu ambiente e seus objetivos. O texto [POR 97]
apresenta uma definição semelhante. Um sistema multi-agente é definido como um
conjunto de agentes que colaboram entre si para cumprir suas responsabilidades.
Conforme apresentado em [AMA 97] um agente é caracterizado pelas seguintes
propriedades:
40
Autonomia: Mantém um controle sobre suas ações e estado interno;
Habilidade Social: Interage com outros agentes e/ou com humanos;
Ação: Percebe o ambiente e age em função das mudanças de ambiente;
Orientação: Exibe comportamentos dirigidos por objetivos.
Merece destaque ainda a seguinte afirmação apresentada em [AMA 97]. Um
agente possui inteligência para gerenciar sua autonomia. Esta inteligência possui como
base suas atitudes mentais ([SHO 94]). Exemplos de atitudes mentais são:
conhecimento, crenças, objetivos, desejos, intenções, obrigações, etc. Em função das
atitudes mentais um agente define seu comportamento autônomo. Este comportamento
consiste em decidir quais ações devem ser executadas para satisfação de um objetivo,
quando e para quem solicitar colaboração, que mudanças no ambiente fazem mudar
suas crenças e objetivos, etc.
O desenvolvimento orientado a agentes possui uma forte relação com o
desenvolvimento orientado a objetos. Em [POR 97] encontra-se uma interessante
comparação entre esses paradigmas. O conceito de agente inteligente introduz
consciência no universo inanimado dos objetos. Esta é uma das principais contribuições
do paradigma orientado a agentes. Um objeto simplesmente executa métodos em função
de solicitações (mensagens). Por outro lado, um agente inteligente cria planos para
solução de situações não previstas e aprende a partir da experiência. Neste sentido,
pode-se considerar a orientação a agentes como uma evolução da orientação a objetos.
Atualmente, as principais dificuldades no âmbito do paradigma orientado a
agentes estão relacionadas com a definição de caminhos para desenvolvimento de
sistemas multi-agentes. Conforme salienta Amandi ([AMA 97]), o paradigma orientado
a agentes necessita de arquiteturas (modelos) e linguagens que permitam o
desenvolvimento de sistemas. Uma arquitetura define o sistema em termos de
componentes e de interações entre eles ([SHM 95]). Por sua vez, uma linguagem
permite a programação dos componentes através de entidades de vários níveis de
abstração. Em [AMA 97] são apresentados vários exemplos de arquiteturas e linguagens
orientadas a agentes. Além disso, são apresentadas várias aplicações para os sistemas
multi-agentes. O texto [POR 97] apresenta em detalhes uma aplicação específica, ou
seja, agentes de informação. Os agentes de informação permitem o gerenciamento de
informações oriundas de fontes distribuídas. Este tipo de agente encontra sua principal
aplicação na organização de informações na rede Internet. Merece destaque ainda, o
texto [COM 94], contendo uma coletânea de artigos relacionados com agentes
inteligentes.
3.2
Modelos e linguagens para exploração do paralelismo
Esta seção apresenta tópicos relacionados com modelos e linguagens para
exploração do paralelismo. Os textos [BAL 89] e [SKI 98] apresentam estudos
abrangentes relacionados com o mesmo tema. O primeiro texto é um artigo clássico. O
segundo destaca-se pela abordagem recente e inovadora. Esta seção é subdividida em
quatro subseções. As duas primeiras são baseadas no texto de Skillicorn e Talia
([SKI 98]). A subseção 3.2.1 mostra as propriedades que devem ser encontradas em um
modelo ideal. Por sua vez, a subseção 3.2.2 contém uma classificação de modelos
baseada em níveis de abstração. A terceira subseção é baseada nos estudos apresentados
por Andrews, Tanenbaum et al ([AND 83], [BAL 89]) e aborda aspectos relacionados
41
com comunicação e sincronização. Finalmente, a quarta subseção aprofunda a discussão
sobre paralelismo implícito e explícito, tendo como base textos de vários autores.
3.2.1
Propriedades ideais
O artigo de Skillicorn e Talia destaca seis propriedades consideradas básicas para
um modelo que suporte a exploração do paralelismo ([SKI 98, p.130]). Estas
propriedades são as seguintes:
1) Facilidade de programação: Um modelo deve esconder do programador o
máximo de detalhes envolvidos na execução do programa. Na medida do
possível, os detalhes de execução devem ser suportados pelos mecanismos de
tradução (compilador e ambiente de execução). Neste sentido, Skillicorn e
Talia salientam que o modelo deve conciliar as seguintes tarefas:
Decomposição de um programa em tarefas paralelas. O programa deve ser
dividido em partes que serão executadas em processadores distintos. Sendo
assim, as estruturas de dados e código terão que ser divididas em um
número potencialmente grande de tarefas paralelas;
Mapeamento das tarefas paralelas em processadores. Esta decisão
normalmente é influenciada pelo montante de comunicação a ser realizada
entre as tarefas. Algumas heurísticas norteam as decisões de mapeamento.
Por exemplo, a comunicação entre tarefas que trocam muita informação
deve ser facilitada. Em complemento, algumas vezes é necessário o
mapeamento de determinadas tarefas para determinados processadores que
possuam alguma capacidade especial de hardware (por exemplo, unidades
funcionais específicas para cálculo de ponto-flutuante). Bal, Steiner e
Tanenbaum afirmam em [BAL 89, p.275] que existem três tipos de
mapeamento, ou seja: fixado em tempo de compilação, fixado em tempo de
execução e nunca fixado. Merece destaque a descrição do último tipo de
mapeamento ([BAL 89, p.276]), onde os autores salientam que poucas
linguagens o suportam e destacam a linguagem Emerald como um
exemplo que permite objetos migrarem entre processadores. Atualmente, o
terceiro tipo de mapeamento tem recebido cada vez mais atenção da
comunidade científica no âmbito das pesquisas relacionadas com
mobilidade ([ROY 97], [IEE 98], [LAN 98], [FER 99]);
Comunicação entre tarefas paralelas. Sempre que um dado não local é
necessário, surge a necessidade de comunicação entre tarefas paralelas. A
forma de comunicação depende da arquitetura e do software de
desenvolvimento utilizados. A seção 3.2.3 dedica-se em parte, ao estudo da
comunicação entre tarefas paralelas;
Sincronização entre tarefas paralelas. Existem determinadas situações em
que um grupo de tarefas deve tomar ciência de que um estado considerado
comum foi alcançado. O sincronismo organiza a execução conjunta das
tarefas. A seção 3.2.3 aborda a sincronização;
2) Suporte a uma metodologia para desenvolvimento de software: Afirmam
Skillicorn e Talia que a primeira propriedade (facilidade de programação) cria
uma distância considerável entre as informações fornecidas pelo programador
a respeito do programa e os detalhes necessários para sua execução. Para
42
vencer essa distância é necessária uma forte fundamentação semântica na qual
técnicas de transformação podem ser utilizadas;
3) Independência de arquitetura: Um modelo deve ser independente de
arquitetura. Sendo assim, os programas poderão migrar entre arquiteturas sem
mudanças relevantes;
4) Facilidade de compreensão: O aprendizado e o ensino de um modelo devem
ser fáceis. Sendo assim, será simples ensiná-lo ao desenvolvedores de
software. Afirmam Skillicorn e Talia que uma ferramenta simples com
objetivos claros é preferível a uma ferramenta complexa de difícil utilização;
5) Garantia de desempenho: Um modelo deve garantir ganho de desempenho
em uma grande variedade de arquiteturas. Neste contexto, destaca-se a
afirmação de que um modelo não deve alcançar sempre o máximo
desempenho possível em uma arquitetura, pois na maioria das aplicações o
nível máximo de desempenho não é necessário, especialmente se obtido em
função de esforço de desenvolvimento e manutenção. Merece destaque ainda,
que um modelo é considerado poderoso se, dado o texto do programa e
propriedades básicas da arquitetura, a execução ocorre com o desempenho
esperado. Geralmente a razão para baixo desempenho é congestionamento, o
qual surge não de ações individuais do programa, mas sim de comportamentos
coletivos. Além disso, o montante de comunicação que um programa realiza
pode ser reduzido de duas formas: reduzindo o número de comunicações
simultâneas ou reduzindo a distância percorrida por uma mensagem
específica;
6) Medidas de custo: Todo o desenvolvedor de sistemas é guiado em maior ou
menor grau por motivações de desempenho. O tempo de execução é o mais
importante destas motivações, mas existem outras, tais como utilização de
processadores e o custo de desenvolvimento. Skillicorn e Talia denominam o
conjunto destas motivações como custos do programa. Um modelo deve
tornar explícitos os custos do programa durante os estágios de
desenvolvimento de um software. Esta propriedade é difícil para um modelo,
pois tende a violação da noção de abstração. Não é possível a determinação do
custo do programa sem alguma informação a respeito da arquitetura na qual
ocorrerá a execução. No entanto, a informação necessária é mínima. Skillicorn
e Talia afirmam em [SKI 98, p.134] que um modelo possui medidas de custo
se é possível a determinação dos custos de um programa a partir: do texto do
programa, de informações mínimas a respeito da arquitetura (pelo menos o
número de processadores) e de informações a respeito do tamanho das suas
entradas. Em complemento, as medidas de custo devem ser composicionais,
ou seja, o custo do programa é equivalente a composição dos custos de suas
partes. No âmbito da análise de complexidade, destacam-se os artigos
[LAR 90] e [SEL 97], os quais enfocam o paradigma orientado a objetos. Os
textos [DEB 93] e [LIN 93] discutem o tema no paradigma em lógica.
Tendo como base essas seis propriedades, Skillicorn e Talia apresentam várias
implicações, dentre as quais destacam-se:
Modelos abstratos tornam fácil a construção de programas, mas difícil a
compilação para código eficiente. Em complemento, modelos pouco abstratos
tornam difícil a construção de software, mas facilitam a criação de uma
implementação eficiente. Tendo como base essa implicação, é criada uma
43
classificação baseada em seis níveis de abstração dos modelos. Essa
classificação é apresentada na seção 3.2.2;
3.2.2
Somente quando a estrutura dos programas é estática e o montante de
comunicação é limitado, um modelo pode garantir desempenho e permitir a
previsão através de medidas de custo. Através desta constatação, surge mais
uma medida utilizada por Skillicorn e Talia para classificação dos modelos
paralelos. A medida recebe o nome de restrições para estruturas dos
programas. Esta medida é considerada secundária, sendo complementar à
primeira (nível de abstração). Existem três níveis de restrição, ou seja:
modelos em que a estrutura dos processos é dinâmica, modelos em que a
estrutura dos processos é estática, mas a comunicação não é limitada e
modelos em que a estrutura dos processos é estática e a comunicação é
limitada.
Classificação baseada em níveis de abstração
O texto [SKI 98] comenta diversos modelos e linguagens para exploração do
paralelismo. A apresentação segue uma ordem decrescente de abstração. Segundo
Skillicorn e Talia os modelos e linguagens podem ser organizados em seis grupos, ou
seja:
1) Abstração completa do paralelismo: Modelos que descrevem somente o
propósito do programa e não sua execução. Os desenvolvedores de software
não precisam saber se o programa será executado em paralelo. Tais modelos
são necessariamente abstratos e relativamente simples, pois os programas que
serão executados em paralelo não podem ser mais complexos do que os
executados seqüencialmente. Como exemplo deste grupo destaca-se o modelo
Opera ([BRJ 91]);
2) Paralelismo é explícito, mas decomposição é implícita (portanto, são
implícitos também o mapeamento, a comunicação e a sincronização): Os
desenvolvedores de software estão conscientes de que a execução será paralela
e, portanto, expressam o potencial de paralelismo nos programas. No entanto,
eles não sabem quanto paralelismo será explorado durante a execução. Tais
modelos normalmente requerem que os programas expressem ao máximo o
paralelismo existente no problema. Por sua vez, a implementação reduz o grau
de paralelismo de acordo com a arquitetura paralela a ser utilizada. Entre os
exemplos deste grupo destacam-se os modelos Concurrent Prolog (estudo de
caso apresentado na seção 3.4.2), Parlog e Delta-Prolog;
3) Paralelismo e decomposição são explícitas, mas mapeamento,
comunicação e sincronização são implícitas: Tais modelos requerem
decisões para divisão do programa, mas poupam os desenvolvedores das
implicações de suas decisões. Neste grupo são destacados dois exemplos, ou
seja, BSP e LogP;
4) Paralelismo, decomposição e mapeamento são explícitos, mas
comunicação e sincronização são implícitas: Os desenvolvedores realizam a
divisão do programa e decidem a localização das partes na arquitetura
paralela. A localização frequentemente influencia no desempenho da
comunicação. Portanto, este tipo de desenvolvimento exige um conhecimento
da rede que interconecta os processadores. Este fato, diminui a portabilidade
44
dos programas. Entre os modelos citados como exemplos deste grupo
destacam-se Linda e Compositional C++;
5) Paralelismo, decomposição, mapeamento, comunicação são explícitas,
mas sincronização é implícita: O desenvolvedor toma quase todas as
decisões de implementação, exceto as relacionadas com sincronização. Neste
grupo são enquadrados os modelos Atores, Emerald e Concurrent Smalltalk;
6) Tudo é explícito: O desenvolvedor especifica todos os detalhes da
implementação. Sendo assim, torna-se muito difícil o desenvolvimento de
software, pois a correção e o desempenho somente podem ser alcançados pela
atenção para um grande número de detalhes. Neste escopo são citados como
exemplos vários modelos, tais como PVM, MPI, SR (estudo de caso
apresentado na seção 3.4.1), Occam e Concurrent C.
3.2.3
Comunicação e sincronização
Bal, Steiner e Tanenbaum ([BAL 89, p.276]) destacam que um dos principais
temas que devem ser abordados no projeto de modelos e linguagens que suportem a
exploração do paralelismo consiste em como as tarefas paralelas irão cooperar. Essa
colaboração envolve dois tipos de interação, ou seja, comunicação e sincronização.
Destacam ainda os autores que as formas de expressão da comunicação podem ser
classificadas em duas categorias, ou seja, compartilhamento de dados e troca de
mensagens. Merece destaque a semelhança dessa classificação com a organização
proposta na seção 2.1 (figura 2.2).
No âmbito da troca de mensagens, o texto [BAL 89, p.276] salienta que a
primitiva elementar para este tipo de interação é a mensagem ponto-a-ponto. Neste
escopo, a principal decisão de implementação consiste na escolha entre troca de
mensagem síncrona ou assíncrona. No caso da troca síncrona o processo fonte
(processo que envia) é bloqueado até que o processo destino tenha aceito a mensagem.
Desta forma, os processos trocam informações e também realizam sincronização. No
caso da troca assíncrona o fonte não espera pelo destino. O texto destaca ainda que
existem situações onde torna-se necessária uma comunicação bidirecional. Neste caso,
surgem dois tipos de comunicação, ou seja, rendezvous e chamada remota de
processos (RPC). Em complemento, o texto destaca ainda que existem situações que
torna-se necessário o envio de mensagens de uma fonte para vários destinos. Neste caso,
o texto descreve duas abordagens, ou seja, broadcast e multicast.
Os autores em [BAL 89, p.280] destacam que vários textos abordam o
compartilhamento de dados entre processos executados em uniprocessadores. O texto
[AND 83] é citado como referencial para essa área. Em complemento, os autores
destacam que em [BAL 89] estão interessados em sistemas que usam memória
compartilhada como forma de comunicação e sincronização em sistemas com vários
processadores. Uma importante vantagem do compartilhamento de dados consiste na
sua abrangência. Enquanto a troca de mensagens normalmente envolve processos
específicos, os dados compartilhados estão acessíveis para qualquer processo. Além
disso, a atribuição em variáveis compartilhadas possui um resultado imediato, em
contraste com a troca de mensagens, a qual envolve o retardo do envio e recebimento.
Por outro lado, o compartilhamento implica no uso de técnicas que garantam a
integridade dos dados durante o acesso simultâneo de múltiplos processos. O texto
[BAL 89] organiza os trabalhos de compartilhamento de dados em dois universos, ou
45
seja, estruturas de dados distribuídas e variáveis lógicas compartilhadas. O
primeiro grupo relaciona-se com estruturas de dados que podem ser manipuladas
simultaneamente por vários processos. Neste caso, o modelo Linda é citado como
exemplo clássico. O segundo grupo aborda o compartilhamento de variáveis lógicas.
Neste caso, como exemplo é destacado o Concurrent Prolog (seção 3.4.2).
O texto [BAL 89] aborda ainda o não determinismo e a tolerância a falhas no
âmbito dos modelos paralelos. Em relação ao não determinismo, o texto salienta que
existem dois principais sistemas de controle, ou seja: comando select e cláusulas de
Horn com guardas. Ambos os sistemas são baseados no conceito de comandos com
guardas introduzido por Dijkstra. Em complemento, o texto discute o conceito de falha
parcial e aborda três aspectos relacionados com o desenvolvimento tolerante a falhas, ou
seja, desenvolvimento explícito (responsabilidade do desenvolvedor), transações
atômicas e desenvolvimento implícito.
No texto [GRE 83] são discutidos aspectos relacionados com modelos e
linguagens que suportam concorrência. Neste escopo, os autores destacam a importância
da comunicação e sincronização. A comunicação é classificada em dois grupos, ou seja,
baseada no uso de variáveis compartilhadas ou na troca de mensagens. Essa
classificação coincide com a utilizada em [BAL 89]. Os autores destacam ainda que a
sincronização é frequentemente necessária quando processos se comunicam. Em
[GRE 83] as primitivas de sincronização também são classificadas em dois grupos, ou
seja, baseadas em variáveis compartilhadas e baseadas em troca de mensagens. Em
complemento, os autores discutem modelos de linguagens para programação
concorrente. Neste escopo, destaca-se a classificação das linguagens em três grupos, ou
seja:
orientadas a procedimentos: interação entre processos é baseada no
compartilhamento de variáveis. Destacam-se como exemplos: Concurrent
Pascal, Modula, Mesa e Edison;
orientadas a mensagens: interação entre processos é baseada em mensagens.
Esta classe possui como base a comunicação utilizando primitivas send e
receive. São citados como exemplos: CSP, Gypsy e PLITS;
orientadas a operações: interação entre processos possui como principal
mecanismo a chamada remota de procedimentos. Os autores salientam que
este tipo de linguagem combina aspectos dos dois tipos anteriores. Entre os
exemplos destacam-se ADA e SR (estudo de caso apresentado na seção 3.4.1).
Em [SKI 98, p.126] são apresentados conceitos básicos sobre paralelismo. Nesta
abordagem, são salientadas três formas de comunicação entre processos, ou seja:
passagem de mensagens, memória compartilhada e acesso direto à memória remota. A
descrição das duas primeiras opções assemelha-se as abordagens apresentadas em
[GRE 83] e [BAL 89]. No entanto, a terceira opção enfatiza aspectos relacionados com
memória compartilhada distribuída. Neste escopo, é salientado que em arquiteturas
antigas que suportavam DSM, o processador era interrompido para tratamento de cada
mensagem que chegava pela rede de comunicação. Essa situação ocasionava um uso
ineficiente da proposta DSM. Sendo assim, novas arquiteturas introduziram dois
processadores por nodo de processamento. Um dedicado ao tratamento de mensagens e
o outro dedicado ao processamento genérico.
46
3.2.4
Paralelismo implícito e explícito
Conforme afirmam Mccreary e Gill ([MCC 89]) existem duas abordagens para
exploração do paralelismo:
Detecção do paralelismo pelo programador (paralelismo explícito);
Detecção automática do paralelismo (paralelismo implícito).
No paralelismo explícito, a linguagem de programação contém mecanismos para
paralelização do programa. Desta forma, o programador pode utilizar seu conhecimento
empírico para explorar ao máximo o potencial de paralelização de suas aplicações. No
entanto, afirmam Kruatrachue e Lewis ([KRU 88]) que a utilização de mecanismos
explícitos pode levar a uma exploração inadequada do potencial de paralelismo. Além
disso, conforme ressalta Karp ([KAR 88]), grande parte do trabalho necessário para
paralelização de programas é muito difícil para ser realizado por pessoas. Por exemplo,
Karp afirma que somente compiladores são confiáveis para realização da análise de
dependências em sistemas paralelos com memória compartilhada. Por outro lado, devese ressaltar que o paralelismo explícito diminui a complexidade dos compiladores
paralelizadores, pois elimina a necessidade da detecção automática do paralelismo em
tempo de compilação.
No paralelismo implícito, a linguagem de programação não contém mecanismos
para paralelização dos programas. A principal vantagem deste método consiste na
liberação do programador do envolvimento com a paralelização de suas aplicações.
Além disso, o paralelismo implícito aumenta a portabilidade de programas entre
sistemas paralelos, eliminando a necessidade da alteração do código fonte em função da
arquitetura paralela a ser utilizada. Outra característica interessante da exploração
automática consiste no aproveitamento tanto dos programas seqüenciais já existentes
quanto dos ambientes de desenvolvimento (depuração) direcionados para o paradigma
seqüencial.
Analisando-se as vantagens do paralelismo explícito e implícito, constata-se que
ambos os métodos possuem méritos e devem continuar sendo pesquisados. No entanto,
dois pontos relacionados com a exploração automática devem ser ressaltados:
as vantagens obtidas na exploração automática do potencial de paralelismo
inerente aos paradigmas não convencionais, as quais cada vez mais são
destacadas pela comunidade científica. A próxima seção apresenta a
exploração do paralelismo nos paradigmas de software (convencional e não
convencionais);
a tendência para simplificação do uso dos computadores e especificamente a
necessidade de simplificação do desenvolvimento de programas para
computadores paralelos. Sabe-se que a complexidade de desenvolvimento de
programas para plataformas paralelas é um das principais causas da crise do
software paralelo (atraso do desenvolvimento do software paralelo em
relação ao hardware paralelo).
Segundo Pancake ([PAN 91]) e Barbosa ([BAR 93]), os usuários de computadores
paralelos não estão interessados em envolver-se na exploração do paralelismo,
desejando apenas o aumento de desempenho proporcionado por esta nova tecnologia. O
envolvimento com o paralelismo aumenta a complexidade de desenvolvimento e
depuração de programas. Sendo assim, a exploração automática do paralelismo torna-se
a opção mais interessante. Este mesmo ponto de vista é salientado por Skillicorn e Talia
47
([SKI 98]). Desta forma, espera-se que a exploração do paralelismo siga a tendência
natural de simplificação do uso dos computadores, a qual vem sendo aplicada na
maioria das áreas da computação (interfaces gráficas para sistemas operacionais,
sistemas para gerenciamento de dados e outros).
Inevitavelmente, ficando a paralelização a cargo do sistema, a complexidade dos
compiladores aumenta, o que exige a utilização de computadores mais poderosos para
viabilização da análise e tradução dos programa fontes em tempos razoáveis. No
entanto, a aplicação do paralelismo nos projetos de arquiteturas de computadores vem
possibilitando um aumento significativo na velocidade dos sistemas computacionais.
Além disso, verifica-se atualmente um crescente aumento da capacidade de
armazenamento em disco magnético e na memória principal. Sendo assim, o aumento
da complexidade dos compiladores não representará obstáculo na tendência para
exploração automática do paralelismo.
3.3
Paralelismo nos paradigmas de software
As duas seções anteriores apresentaram os paradigmas de software e questões
relacionadas com modelos para exploração do paralelismo. Esta seção é dedicada ao
estudo da integração de ambos os temas, ou seja, a exploração do paralelismo nos
paradigmas de software. Diversas publicações foram dedicadas a este tópico. Destacamse como abordagens genéricas os textos [COM 86] e [ACM 89]. A seção 3.3.1
apresenta uma introdução ao tema. Por sua vez, as demais seções abordam a exploração
do paralelismo em quatro paradigmas, ou seja: convencional (3.3.2), lógica (3.3.3),
funcional (3.3.4) e orientação a objetos (3.3.5).
3.3.1
Semântica paralela nos paradigmas
Conforme afirmam Yamin ([YAM 94]) e Barbosa ([BAR 96]), o paradigma
convencional dificulta a exploração automática do paralelismo. Este fato resulta da sua
tendência em modelar o universo através de comandos imperativos, resultando assim,
em vários níveis de dependências de dados e de controle ([BAR 93], [BAR 94]). Por
outro lado, os paradigmas não convencionais estimulam a exploração automática do
paralelismo através de sua modelagem que abstrai o controle da execução e enfoca a
descrição do universo modelado. Os paradigmas não convencionais tendem a refletir no
modelo as fontes naturais de paralelismo existentes no universo. Por exemplo, o
paradigma em lógica transmite para o modelo computacional o potencial de paralelismo
que está implícito na abordagem lógica do universo (paralelismo OU e paralelismo E).
Por sua vez, o paradigma orientado a objetos transmite o potencial de paralelismo que
existe no universo quando modelado através da filosofia de objetos (paralelismo interobjetos - entre objetos; e paralelismo intra-objeto - entre métodos de um objeto). Tornase interessante ressaltar que o mesmo universo, modelado por paradigmas diferentes,
introduzirá no modelo computacional diferentes fontes de paralelismo. Sendo assim, a
opção pela forma de perceber o universo durante a modelagem (paradigma) influencia
nas fontes de paralelismo que ficarão disponíveis no modelo. A figura 3.1 representa
essa realidade para os paradigmas em lógica e orientado a objetos.
48
Realidade
Universo
Modelagem em Lógica:
Paralelismo E e OU
Modelo em
Lógica
Modelagem Orientada a Objetos:
Paralelismo Intra e Inter Objetos
Modelo Orientado
a Objetos
FIGURA 3.1 - Duplicidade no uso dos paradigmas
3.3.2
Convencional
O paradigma convencional é baseado em comandos imperativos, os quais tornam
explícitos os caminhos para solução dos problemas. A modelagem convencional não
possui abstrações que captem de forma natural as fontes de paralelismo existentes nos
universos modelados. O desenvolvedor descreve a solução dos seus problemas com o
uso de algoritmos e estruturas de dados. Através desse procedimento são criados fluxos
de controle que atuam nos dados criando fluxos de dados. Durante a programação
podem ser criados vários tipos de dependências, as quais dificultam a exploração do
paralelismo. O texto [PAD 86, p.1185] apresenta as dependências que podem surgir em
um programa convencional. As dependências podem ser organizadas em dois grupos,
ou seja, dependências de dados e dependências de controle. No âmbito das
dependências de dados são destacados três tipos, ou seja: dependência de fluxo (ou
verdadeira), antidependência e dependência de saída. O texto [BLU 94, p.38] aborda
o mesmo tema. Ambos os textos apresentam transformações em programas para
eliminação de dependências. Em complemento, o texto [TZE 93] dedica-se
especificamente à solução de dependências no interior de laços.
A maioria das plataformas dedicadas ao paralelismo em paradigmas
convencionais realizam a exploração de forma explícita. Por exemplo, recentes
trabalhos desenvolvidos no âmbito do PVM ([KON 97]) e MPI ([BRU 97]) criam
bibliotecas que inserem primitivas de comunicação explícitas que devem ser utilizadas
junto com o código de linguagens convencionais (C ou Fortran). Outro exemplo de
programação convencional que envolve a exploração explícita é a linguagem SR
([AND 92]). Esta linguagem será discutida como estudo de caso na seção 3.4.1. Por
outro lado, vários trabalhos dedicam-se à exploração automática de paralelismo nos
paradigmas convencionais. Neste escopo destacam-se os textos [KRU 88], [MCC 89],
[GIR 92], [BLU 94] e [ROG 94]. Em complemento, merece destaque a publicação
[IEE 94] dedicada a trabalhos relacionados com exploração de paralelismo em Fortran.
3.3.3
Lógica
Segundo Hermenegildo ([HER 86]), o relacionamento entre programação em
lógica e paralelismo está baseado na liberdade (não-determinismo) que o avaliador
possui na escolha dos caminhos de execução. Esta liberdade permite o desenvolvimento
de avaliadores que explorem em paralelo os diversos caminhos oriundos do não-
49
determinismo. Desta forma, os dois principais tipos de não-determinismo originam as
duas principais fontes de paralelismo, ou seja:
Paralelismo OU: execução paralela dos caminhos da árvore de busca. Este
tipo de paralelismo está baseado no não-determinismo OU, ou seja, na
liberdade de escolha das cláusulas no predicado;
Paralelismo E: execução em paralelo das metas do corpo de uma cláusula.
Este paralelismo baseia-se no não-determinismo E, ou seja, na liberdade de
escolha das metas na resolvente.
PROGRAMA:
p :- a,b.
p :- c.
p :- d,e.
.
.
.
CHAMADA:
:- p,q.
ÁRVORE DE EXECUÇÃO
:- p , q .
:- a , b , q .
:- a .
:- b .
:- q .
Caminho 1
:- d , e , q .
:- c , q .
:- c .
:- q .
:- d .
Caminho 2
:- e .
:- q .
Paralelismo E
Caminho 3
Paralelismo OU
FIGURA 3.2 - Fontes de paralelismo na programação em lógica
A figura 3.2 exemplifica a exploração do paralelismo na programação em lógica.
Para maior simplicidade são apresentados apenas os nomes de predicados. Conforme
mostrado na figura 3.2, o paralelismo OU é explorado na aplicação da regra de busca e
o paralelismo E na aplicação da regra de computação. Desta forma, o paralelismo OU
explora a busca paralela de diferentes caminhos para o mesmo objetivo e o paralelismo
E executa em paralelo passos de um caminho.
50
Durante a execução de um programa, normalmente surgem várias oportunidades
para exploração do paralelismo OU e do paralelismo E. O avaliador gerencia estas
oportunidades de acordo com sua política de paralelismo. Alguns sistemas exploram
apenas um tipo de paralelismo e outros implementam os dois tipos (paralelismo
E/OU).
Deve-se ressaltar ainda, que existem outras fontes de paralelismo na programação
em lógica. Estas fontes não estão relacionadas com o não-determinismo e exploram o
paralelismo em baixo nível. Destacam-se nesta categoria:
Paralelismo de unificação ([VLA 92]): A unificação entre uma meta e a
cabeça de uma cláusula normalmente exige que diversos pares de termos
(argumentos) sejam unificados. Estas unificações podem ser executadas em
paralelo;
Paralelismo de fluxo ([SHA 89]): A utilização de vários processos pode
acelerar o tratamento de estruturas de dados complexas. Um processo pode
atuar como produtor das estruturas e outros processos podem atuar como
consumidores (esquema produtor-consumidor). O processo produtor continua
sua execução logo após enviar uma estrutura de dados para um processo
consumidor. Por sua vez, o processo consumidor continua sua execução logo
após receber a estrutura. Desta forma, explora-se o potencial de paralelismo
existente no esquema produtor-consumidor. Conforme afirmam Gupta e
Jayaraman ([GUP 93]), o paralelismo de fluxo pode ser utilizado para explorar
o paralelismo E dependente. O Concurrent Prolog utiliza essa metodologia
(estudo de caso apresentado na seção 3.4.2);
Paralelismo de busca ([KAS 83]): Neste tipo de paralelismo o programa é
dividido em conjuntos disjuntos de cláusulas, os quais são avaliados por
diferentes processos durante a busca de soluções.
Vários textos podem ser utilizados para aprofundamento de estudos sobre
paralelismo na programação em lógica. Merecem destaque as seguintes publicações:
[SHA 89], [CIP 92] e [KER 94].
3.3.4
Funcional
Conforme afirmam Jones e Hudak ([JON 93]), as linguagens funcionais são
ferramentas poderosas para programação de sistemas paralelos. Os autores utilizam a
seguinte expressão para exemplificar a fonte de paralelismo existente no paradigma
funcional:
e1 + e2
A obtenção do resultado dessa expressão exige a avaliação das subexpressões e1 e
e2. Em uma linguagem convencional a avaliação de uma das subexpressões pode
influenciar na avaliação da outra, ou seja, pode existir uma relação de dependência entre
elas. Neste caso, a semântica da linguagem deve estabelecer que as subexpressões serão
solucionadas seqüencialmente em alguma ordem pré-definida. Por outro lado, o
paradigma funcional estabelece na sua semântica que uma avaliação não pode interferir
na outra. Portanto, as subexpressões podem ser avaliadas em paralelo agilizando a
obtenção do resultado.
51
Segundo Hammond ([HAM 94]), existem três classes de linguagens funcionais,
ou seja:
Linguagens estritas: os argumentos de funções são avaliados antes da
avaliação da função. Destacam-se como exemplos Hope e OPAL;
Linguagens não estritas: os argumentos são avaliados somente se forem
necessários. Como exemplo é citada a linguagem Haskell;
Linguagens híbridas: argumentos simples (por exemplo, inteiros) são
resolvidos antes da avaliação da função. Por outro lado, argumentos
complexos (por exemplo, listas) seguem a proposta das linguagens não
estritas. Como exemplo surge a linguagem Hope+.
Hammond afirma que o paralelismo em linguagens funcionais pode ser explorado
de forma implícita ou explícita. No caso da exploração implícita o paralelismo possui
diferentes aspectos dependendo do tipo de linguagem. Afirma o autor que a exploração
de paralelismo implícito em linguagens estritas é bastante simples, pois todos os
argumentos devem ser avaliados antes da chamada de uma função. Considerando-se que
os argumentos podem ser expressões, surge assim a oportunidade para exploração do
paralelismo sempre que uma função for avaliada. No entanto, ressalta o autor que essa
abordagem resulta na criação de um grande número de tarefas paralelas de pequena
granulosidade. Por outro lado, no caso de linguagens não estritas o paralelismo implícito
é obtido na solução paralela dos argumentos considerados necessários para avaliação de
uma função. A determinação de quais argumentos serão necessários é realizada através
de uma análise de restrições. No entanto, Hammond salienta que na prática este tipo de
análise normalmente falha na exploração de paralelismo em programas reais. A maior
parte do texto [HAM 94] dedica-se à descrição da exploração explícita do paralelismo.
Hammond descreve várias anotações utilizadas para a expressão do paralelismo em
linguagens funcionais. Neste escopo, é citada uma proposta de Hudak, a qual cria o
termo programação para-funcional para linguagens que introduzem anotações que
preservam a semântica funcional.
Jones e Hudak ([JON 93]) também abordam a exploração do paralelismo
implícito e explícito no âmbito do paradigma funcional. No entanto, a abordagem
enfoca de forma especial uma proposta para exploração de paralelismo na linguagem
Haskell. Neste escopo, destaca-se ainda o texto [TRI 93], o qual discute o
relacionamento entre estratégias de avaliação e exploração do paralelismo no paradigma
funcional. O texto propõe a estratégia utilizada no GPH (Glasgow Parallel Haskell). A
seção 3.4.3 dedica-se à descrição do GPH.
3.3.5
Orientação a objetos
Chin e Chanson ([CHI 91, p.91]) abordam a fusão da orientação a objetos e dos
sistemas distribuídos. Neste escopo, os autores salientam que um sistema distribuído de
programação baseado em objetos (distributed, object-based programming system –
DOBPS) suporta a programação como a mesma qualidade tanto em ambientes
centralizados como distribuídos. O texto discute os seguintes aspectos no âmbito dos
DOBPS:
Estrutura de objetos: Granulosidade e composição (objetos ativos e
passivos);
52
Gerenciamento de objetos: Gerenciamento de ações (serialização,
atomicidade e permanência), sincronização, segurança e recuperação de falhas;
Gerenciamento da interação entre objetos: Localização de objetos,
gerenciamento de invocações e detecção de falhas;
Gerenciamento de recursos: Gerenciamento de memória (primária e
secundária) e processadores.
Merece destaque que o texto é organizado tendo como base estes aspectos. Em
complemento, os autores apresentam para cada aspecto sete estudos de caso, ou seja:
Amoeba, Argus, Chorus, Clouds, Eden, Emerald e TABS/Camelot. Destaca-se ainda em
[CHI 91, p.94], as dez características consideradas básicas para um DOBPS, ou seja:
distribuição, transparência, integridade de dados, tolerância a falhas, disponibilidade de
objetos, recuperação de falhas, autonomia de objetos, concorrência no programa (interobjetos), concorrência no objeto (intra-objeto) e melhoria de desempenho em relação a
sistemas centralizados.
Os textos [AUG 92] e [WYA 92] apresentam estudos genéricos relacionados com
paralelismo na orientação a objetos. Ambos os textos descrevem os aspectos da
orientação a objetos e do paralelismo considerados relevantes no escopo em questão.
Em [AUG 92, p.26] destaca-se a afirmação de que existem dois modos de fornecer
concorrência na orientação a objetos, ou seja:
introduzir no modelo novas noções, tais como, processos ou monitores;
combinar os mecanismos de concorrência com conceitos do paradigma, por
exemplo, objeto e processo.
Augustin destaca que a principal questão no âmbito da exploração do paralelismo
na orientação a objetos consiste em como expressar e controlar as atividades
concorrentes. Em complemento, a autora salienta que as linguagens orientadas a objetos
seqüenciais são baseadas no modelo de objetos passivos, ou seja, um objeto somente é
ativado quando recebe uma mensagem de outro objeto. Neste caso, um objeto ativo
(emissor) emite uma mensagem e torna-se passivo. Em complemento, um objeto
passivo (receptor) recebe uma mensagem, torna-se ativo, responde a mensagem e tornase novamente passivo. O emissor recebe a resposta e torna-se novamente ativo. Em
[AUG 92, p.27] encontra-se a afirmação de que na orientação a objetos o paralelismo
pode surgir através da criação de um novo modelo com características paralelas (por
exemplo, modelo de Atores descrito em [AUG 92, p.29]) ou através de uma extensão do
modelo de objeto seqüencial. As seguintes estratégias podem ser utilizadas para
implementar a segunda opção:
permitir que um objeto torne-se ativo sem recebimento de uma mensagem;
permitir que um objeto receptor mantenha-se ativo após responder uma
mensagem;
suportar o envio de mensagens para vários objetos por vez;
permitir ao emissor continuar a execução após enviar uma mensagem.
As duas primeiras técnicas combinam um processo a um objeto, criando assim o
modelo de objetos ativos. Conforme afirma Augustin, basicamente as linguagens
orientadas a objetos concorrentes suportam objetos ativos ou Atores. Destaca-se ainda a
afirmação de que atores são objetos ativos em sua forma mais geral. A mesma autora no
53
ano de 1994 propõe uma biblioteca de classes para paralelismo em Eiffel (pEiffel,
[AUG 94]).
Destacam-se ainda como trabalhos vinculados à fusão dos temas paralelismo e
orientação a objetos: os trabalhos de Jungblut relacionados com exploração de
paralelismo implícito na orientação a objetos ([JUN 95] e [HES 97]) e os trabalhos de
Cavalheiro orientados para criação de um modelo que suporta programação distribuída
orientada a objetos (DPC++, [CAV 92] e [CAV 94]). O modelo proposto por
Cavalheiro é o estudo de caso apresentado na seção 3.4.4.
Briot et al possuem vários estudos relacionados com paralelismo e orientação a
objetos. Entre eles destacam-se a revisão e classificação de várias abordagens para
programação paralela e distribuída orientada a objetos ([BRI 96]) e, em especial, um
recente estudo sobre concorrência e distribuição no âmbito da orientação a objetos
([BRI 98]). Em [BRI 98, p. 2], os autores afirmam que as abordagens para programação
concorrente e distribuída orientadas a objetos podem ser classificadas em três grupos,
ou seja:
abordagem de bibliotecas: aplicação dos conceitos da orientação a objetos
para estruturação de sistemas concorrentes e distribuídos através de bibliotecas
de classes. Por exemplo, processos, construções de sincronismo, arquivos,
servidores de nomes são representados como classes de objetos;
abordagem integrativa: unificação dos conceitos da concorrência e
distribuição com os conceitos da orientação a objetos. Por exemplo, a fusão
das noções de processo e objeto resulta na noção de objeto ativo. Em
complemento, a fusão de transação e invocação de objetos resulta na noção de
invocação atômica;
abordagem reflexiva: separação entre programas de aplicação e aspectos de
implementação e execução através do uso de metaprogramação.
Os autores dedicam a cada abordagem uma seção do artigo. Na primeira
abordagem destaca-se o estudo relacionado com as bibliotecas de Smalltalk e C++. Na
segunda destaca-se a discussão sobre unificação de conceitos. Neste escopo discute-se
unificação objeto/processo (objetos ativos), sincronização/ativação de objetos (objetos
sincronizados), objeto/unidade de distribuição (objetos distribuídos). No âmbito da
terceira abordagem destacam-se os exemplos de arquiteturas de metaobjetos onde são
discutidos: Smalltalk, Coda, Actalk e GARF. Merece destaque ainda, no âmbito da
segunda abordagem, três classificações relacionadas com paralelismo e orientação a
objetos. Na primeira os autores destacam dois tipos de concorrência na orientação a
objetos, ou seja:
concorrência inter-objetos: concorrência entre objetos ativos. Cita-se como
exemplo a linguagem Pool que suporta somente este tipo de concorrência;
concorrência intra-objetos: concorrência entre execução de requisitos, ou
seja, um objeto suporta várias atividades internas. Neste caso, cita-se o modelo
de Atores.
Tendo como base esta classificação, os autores citam quatro tipos de objetos
ativos:
serial (conhecido como objeto atômico): suporta a execução de somente uma
requisição por vez. São exemplos: Pool e Eiffel//;
54
quase concorrente: suporta a execução de várias requisições, no entanto, pelo
menos uma delas não pode estar suspensa. Surgem como exemplos ABCL/1 e
Concurrent Smalltalk.
concorrente: suporta a execução de várias requisições, mas é necessário
algum nível de controle, tal como restrições aplicadas pelo programador.
Citam-se como exemplo: linguagens de atores, ACT++ e Ceiffel;
concorrência completa: não existe restrições em relação à concorrência intraobjetos. Os autores destacam que algumas linguagens de atores suportam este
tipo de concorrência. Neste caso, surgem os atores não serializados.
A concorrência intra-objetos aumenta o poder de expressão e a taxa de
concorrência. Por outro lado, exige controle da concorrência como garantia da
consistência dos estados dos objetos e necessita ainda de um gerenciamento cuidadoso
dos recursos para uma implementação eficiente. Destacam ainda os autores que, por
razões de eficiência, a concorrência completa é normalmente implementada com objetos
passivos (objetos padrões sem nenhuma atividade) sem nenhum sincronismo e
replicação dos objetos em todos os processadores. Sendo assim, toda invocação oriunda
de um objeto ativo é processada de forma imediata no processador onde ele reside.
Finalmente, os autores afirmam que existem dois tipos de objetos ativos:
objetos ativos reativos: são ativados somente através do envio de mensagens.
Por exemplo, em ACT++;
3.4
objetos ativos autônomos: podem estar ativos antes do envio de mensagens.
Por exemplo, em Pool e Eiffel//.
Estudos de caso
Esta seção apresenta quatro estudos de caso sobre paralelismo em paradigmas de
software. A seção 3.4.1 apresenta a linguagem SR no âmbito do paradigma
convencional. Por sua vez, Concurrent Prolog é descrito na seção 3.4.2 como estudo de
caso do paralelismo na programação em lógica. A seção 3.4.3 descreve o GPH
(Glasgow Parallel Haskell). Finalmente, na seção 3.4.4 é apresentado o DPC++ no
escopo do paralelismo na orientação a objetos.
3.4.1
Paradigma procedimental: SR (Synchronizing Resources)
A linguagem SR suporta a programação convencional acrescida de um conjunto
de novos conceitos e primitivas que permitem a exploração da concorrência. As
características clássicas do paradigma convencional são suportadas, tais como: tipos,
variáveis, atribuição destrutiva, comandos de controle de repetição, comandos de
seleção simples e múltipla, procedimentos, etc. Em complemento, SR fornece
mecanismos para gerenciamento da concorrência, comunicação e sincronização. A
linguagem SR vem sendo pesquisada e aperfeiçoada ([AND 81], [AND 82], [AND 86],
[AND 88], [AND 92]), obtendo uma boa aceitação em ambientes acadêmicos.
Um programa em SR pode ser composto por múltiplos espaços de endereçamento
(máquinas virtuais), os quais podem estar localizados em múltiplos computadores
(máquinas físicas). Os processos residentes em um mesmo espaço de endereçamento
podem compartilhar memória. Desta forma, a linguagem SR suporta programação em
ambientes distribuídos e ambientes com memória compartilhada.
55
As máquinas virtuais suportam instâncias de um módulo denominado recurso. Os
recursos são divididos em duas partes: especificação e implementação. A especificação
contém declarações de tipos, constantes e operações. Uma operação define um serviço
que deve ser fornecido na implementação. A implementação contém o código que
implementa as operações. Este código deve estar encapsulado em unidades
denominadas processos e procs. Todos os processos e procs executam na máquina
virtual onde foram definidos. A utilização de dois tipos de chamadas (síncrona/call e
assíncrona/send), as quais são servidas pelas operações, permite a criação dos seguintes
mecanismos de programação concorrente: criação dinâmica de processos, troca de
mensagens assíncronas, chamada remota de procedimentos (RPC) e rendezvous.
A figura 3.3 exemplifica o modelo computacional proposto pelo SR. Basicamente,
um programa consiste em uma máquina virtual executando em uma máquina física. Um
programa pode ser composto de múltiplas máquinas virtuais executando em múltiplas
máquinas físicas. A comunicação entre processos é independente das suas localizações
nas máquinas virtuais. Por exemplo, a troca de mensagens entre processos localizados
no mesmo recurso possui a mesma sintaxe e semântica do que a troca de mensagens
entre processos localizados em diferentes máquinas virtuais.
Máquina Física
Máquina Física
Máquinas Virtuais
(endereços compartilhados)
Máquina Virtual
Recursos
Recursos
Recurso
Processos
Processos
Processo
FIGURA 3.3 - Modelo computacional do SR
3.4.2
Paradigma em lógica: Concurrent Prolog
Conforme afirma Shapiro ([SHA 86, p.44]), Concurrent Prolog é uma linguagem
de programação em lógica projetada para programação concorrente e execução paralela.
Os componentes essenciais da programação concorrente (gerenciamento de processos,
comunicação e sincronização) são naturalmente suportados pela programação em
lógica. Shapiro afirma que além das interpretações declarativa e procedimental, a
programação em lógica pode ser interpretada do ponto de vista da concorrência. Neste
caso, surge a interpretação concorrente. Essa é a base do modelo computacional
proposto pelo Concurrent Prolog.
56
Shapiro destaca através de um exemplo ([SHA 86, p.47]) as semelhanças entre os
componentes da programação concorrente e os elementos da programação em lógica.
Neste contexto, surgem as seguintes analogias:
meta = processo;
conjunto de metas = rede de processos;
variáveis lógicas compartilhadas = canais de comunicação = atribuição única
em variáveis compartilhadas;
cláusulas da programação em lógica = instruções para o comportamento dos
processos.
Tendo como base estas analogias, Shapiro descreve o modelo do Concurrent
Prolog (interpretação concorrente). O término de um processo resulta de uma cláusula
sem corpo, por exemplo:
p(T1, T2,...,Tn).
A troca de dados e a troca de estados de um programa são implementados com
uma cláusula com apenas uma meta no corpo, ou seja:
p(T1, T2,...,Tn)
q(S1, S2,...,S3).
A criação de novos processos pode ser realizada com uma cláusula com várias
metas no corpo (m processos criados), por exemplo:
p(T1, T2,...,Tn)
q1, q2,...,qm .
Em contraste com Prolog seqüencial, em Concurrent Prolog uma ação realizada
por um processo não pode ser desfeita. Após um processo ser reduzido usando uma
cláusula, não pode haver backtracking. O comportamento resultante dessa proposta é
conhecido como indeterminismo (não-determinismo commited-choice ou nãodeterminismo don’t care). Neste caso, quando um processo realiza uma escolha, tornase vital que seja a opção correta. Visando a sincronização entre processos e o controle
do não-determinismo, Concurrent Prolog introduz dois operadores, ou seja, operador
somente de leitura (simbolizado por ?) e operador commit (simbolizado por |). O
operador ? é utilizado para indicar que uma variável é somente de leitura (por exemplo,
X?). Uma variável somente de leitura não pode ser lida antes de instanciada. Sendo
assim, a variável somente pode ser instanciada na sua versão que aceita escrita (X sem
?). Um processo que tenta instanciar uma variável somente de leitura suspende até que a
variável seja instanciada. Em complemento, o operador commit retarda a execução até
momento que fiquem disponíveis as informações necessárias para a tomada de decisão
relacionada com o não-determinismo. Este operador é utilizado para inserção de guardas
nas cláusulas. Uma cláusula com guardas possui o formato:
A
g1, g2,...,gn | b1, b2,..., bm.
n,m
0
O operador commit separa o lado direito de uma cláusula em uma guarda (metas
g) e um corpo (metas b). O corpo somente será executado quando ocorrer uma
unificação com a cabeça e, de forma complementar, a guarda obtiver sucesso. Sendo
assim, a guarda pode ser utilizada para controlar o indeterminismo. Merece destaque
ainda que, em Concurrent Prolog as guardas podem ser chamadas de programas. Desta
forma, guardas podem ser recursivas e o teste para execução do corpo de uma cláusula
pode ser bastante complexo.
57
3.4.3
Paradigma funcional: GPH (Glasgow Parallel Haskell)
GPH é uma extensão da linguagem Haskell que suporta execução paralela. Em
[TRI 93, p.2], os autores afirmam que o GPH adota um abordagem promissora que tem
sido utilizada por vários pesquisadores, ou seja, delega-se a maior parte do
gerenciamento do paralelismo para o ambiente de execução (run-time), mas permite-se
ao programador o gerenciamento de aspectos considerados críticos. Os aspectos do
programa descritos pelo programador são denominados comportamento dinâmico. Os
autores de [TRI 93] utilizam a seguinte expressão para representar o comportamento
dinâmico em GPH:
COMPORTAMENTO DINÂMICO = PARALELISMO + GRAU DE AVALIAÇÃO
Portanto, o comportamento possui dois componentes, ou seja:
Paralelismo: especifica quais tarefas paralelas devem ser criadas e a sua
ordem de execução. Este controle é baseado em duas anotações inseridas nos
programas (anotações seq e par);
Grau de avaliação: especifica quanta avaliação cada tarefa paralela deve
realizar. O grau de avaliação está relacionado com a estratégia de avaliação do
paradigma funcional (nível de estritez). Conforme comentando na seção 3.3.4,
Haskell é uma linguagem não estrita.
Em GPH o paralelismo é introduzido nos programas com a utilização de uma
anotação (anotação par). Esta anotação explicita que dois argumentos devem ser
executados em paralelo. A seguinte expressão mostra o uso da anotação:
p ‘par’ e
Neste caso, a expressão indica a execução paralela das expressões p e e. Durante a
execução uma nova tarefa paralela pode ser criada para executar p, enquanto e
continuará sendo executado na tarefa corrente. Em complemento é fornecida uma
anotação para indicar o interesse na execução seqüencial de dois argumentos (anotação
seq). A seguinte expressão indica que p e e devem ser executadas de forma sequencial.
p ‘seq’ e
A figura 3.4 mostra a aplicação das anotações seq e par na paralelização do
programa para cálculo do número de Fibonacci. Conforme mostra o programa, se n é
maior do que 1, então pfib (n-1) é paralelizado e a tarefa corrente continua com a
avaliação de pfib (n-2).
pfib n
| n <= 1 = 1
| otherwise = n1 ‘par’ n2 ‘seq’ n1+n2+1
where
n1 = pfib (n-1)
n2 = pfib (n-2)
FIGURA 3.4 - Programa Fibonacci implementado em GPH
58
No caso do grau de avaliação destaca-se o seguinte aspecto. Se o grau de
avaliação de uma função é menor do que seu nível de estritez, então o paralelismo é
conservativo, ou seja, nenhuma expressão que não seja reduzida na avaliação realizada
pela linguagem é executada em paralelo. Salientam os autores de [TRI 93] que, em
alguns casos torna-se útil a avaliação de expressões de forma especulativa, ou seja, o
grau de avaliação ser mais estrito do que a metodologia de avaliação da linguagem.
Merece destaque ainda que no ano de 1995, os mesmos autores de [TRI 93]
propuseram a criação de um ambiente de execução distribuída denominada GUM
([TRI 96]). Os princípios de paralelização em GUM são os mesmos do GPH. Conforme
afirmam os autores, GUM é uma implementação paralela de Haskell relacionada com a
versão 0.26 do GHC (Glasgow Haskell Compiler). Esta implementação é baseada na
troca de mensagens e a portabilidade é facilitada pelo uso de PVM como suporte à
distribuição. As principais características de GUM são:
portabilidade: baseada no uso do PVM;
desempenho: baseada na tecnologia de compilação do GHC. Afirmam os
autores que em GUM a execução seqüencial é quase tão rápida quanto a
execução em GHC;
ferramentas: disponibilidade de ferramentas
visualização da execução de programas;
para monitoramento
e
coleta de lixo: suporte à coleta de lixo orientado à distribuição;
regulagem da distribuição: tarefas paralelas nunca são exportadas visando
balanceamento de carga. A exportação somente acontece quando um
processador está ocioso. Afirmam os autores, que desta forma evita-se
problemas de localidade relacionados com exportação prematura;
mensagens assíncronas: todas as mensagens são assíncronas, aumentando
assim a concorrência entre tarefas paralelas.
3.4.4
Paradigma orientado a objetos: DPC++
O DPC++ (Processamento Distribuído em C++) é uma linguagem de
programação distribuída orientada a objetos. Esta linguagem implementada o modelo de
suporte à execução distribuída de processos proposto em [CAV 94]. Conforme afirma
Cavalheiro ([CAV 94, p.58]), o modelo pode ser compreendido sob dois aspectos, ou
seja:
visão do usuário: os mecanismos utilizados para implementação dos recursos
de distribuição são transparentes. A atenção do programador é direcionada
para a linguagem de programação;
visão de operação: suporta os meios que garantem a execução distribuída de
objetos.
O nível operacional é independente da linguagem utilizada. A operação do
modelo é transparente e provida por mecanismos de compilação, os quais introduzem
no programa o modelo operacional de objetos distribuídos. Destaca-se em
[CAV 94, p.60] a descrição das características básicas do modelo:
incorporação do paralelismo é explícita;
59
herança é realizada por cópia. Destaca Cavalheiro ([CAV 94, p.59]) que a
adoção do mecanismo de delegação utilizada em Atores distanciaria o modelo
proposto do usuário comum;
!
número de processadores é variável;
!
exploração da concorrência baseada em mensagens assíncronas. No entanto,
existe suporte ao sincronismo através de mensagens síncronas;
!
transparência de localização de objetos baseada em endereçamento implícito.
!
No nível de linguagem destacam-se duas restrições, ou seja, não podem ser
utilizadas variáveis de classe (compartilhamento de memória) e não existe suporte à
passagem de parâmetros por referência entre objetos distribuídos. Merece destaque
ainda que, o modelo suporta dois tipos de objetos, ou seja:
locais: pertencem a um cluster de um determinado objeto distribuído. Estes
objetos podem compartilhar memória e a identificação de localização é
provida pelo endereço da porção de memória que ocupam;
!
distribuídos: estes objetos estão sujeitos as duas restrições do modelo
(compartilhamento de memória e parâmetros por referência).
!
Existem dois tipos de objetos locais:
objetos de dados: manipulam informações pertinentes unicamente ao objeto
que os instancia. Os objetos de dados suportam métodos que não demandam
excessivo tempo de processamento, não compensando assim o custo para
executá-lo de forma distribuída;
!
objetos procuradores: suportam a comunicação (envio e recebimento de
mensagens) com objetos que estão localizados em outra área de
endereçamento. Um objeto procurador representa um único objeto distribuído.
!
Em relação à herança, podem ser utilizadas herança simples ou múltipla, tanto em
classes locais como em classes distribuídas. A herança em objetos locais é
implementada através de compartilhamento de código. No caso de classes de objetos
distribuídos, o código é replicado.
Em [CAV 94, p.65] encontra-se a afirmação de que a unidade de processamento
do modelo é o objeto distribuído. A granulosidade das operações é definida pelo
programador através das definições de classes dos objetos distribuídos. O sincronismo
entre objetos ocorre através da troca de mensagens, as quais representam a invocação de
métodos e o retorno de resultados. O tratamento das mensagens pelos objetos
distribuídos respeita a ordem das invocações recebidas. Entre objetos distribuídos as
mensagens são assíncronas. Por outro lado, entre objetos locais as mensagens são
síncronas. Merece destaque o sumário apresentado em [CAV 94, p.97] contendo tabelas
que descrevem todas as características do modelo.
O DPC++ suporta o modelo proposto através de uma extensão da linguagem
C++. Conforme afirma Cavalheiro ([CAV 94, p.100]), DPC++ herda do C++ a
estrutura de programação, a sintaxe, os tipos básicos e, sobretudo, as características
orientadas a objetos. DPC++ introduz duas novas palavras reservadas, ou seja:
distributed: identifica uma classe que descreve uma objeto distribuído;
!
!
confirmation: identifica métodos que suportam confirmação de recebimento
de mensagem (suporte à distribuição).
60
DPC++ utiliza sockets como mecanismo de comunicação entre objetos. Estes
mecanismos são fornecidos através de uma classe denominada Comunicacao. O
ambiente de desenvolvimento do DPC++ é composto de um pré-compilador DPC++ e
do compilador C++. O pré-compilador gera, a partir do programa, os clusters de
execução e as funções de inicialização da aplicação. As saídas do pré-compilador são
codificadas em C++.
Além disso, merece destaque que em DPC++ existem dois tipos de mensagens
para sincronismo entre objetos, ou seja, mensagens com invocação de métodos e
mensagens de resposta de objetos que tiveram métodos invocados. Tendo como base
estas mensagens surgem três tipos de sincronismo:
invocação assíncrona: mensagem enviada sem retorno de resultados.
Possibilita a obtenção de um grau máximo de concorrência. O objeto segue a
execução logo após o envio da mensagem;
"
invocação assíncrona com confirmação: o objeto que origina a mensagem
fica bloqueado até o recebimento de uma mensagem que confirme o início do
tratamento da solicitação;
"
invocação síncrona: o objeto que origina a mensagem fica bloqueado até que
o método invocado seja completamente executado e seja enviada uma
mensagem de resposta. Neste caso, não existe concorrência durante a execução
dos objetos.
"
3.5
Conclusão
Este capítulo abordou o desenvolvimento de software paralelo e distribuído. Neste
escopo, manteve-se o foco do estudo nos paradigmas de software considerados básicos
(convencional, lógica, funcional, orientado a objetos e orientado a agentes). A seção 3.1
destacou que os paradigmas trouxeram valiosas contribuições. Por outro lado, a mesma
seção destacou suas limitações. Nota-se que as contribuições e limitações estão
relacionadas com os universos específicos abordados pelos paradigmas. A mesma
abordagem específica que permite a especialização (contribuições) introduz as
limitações. Destacam-se como principais contribuições dos paradigmas básicos:
Convencional: Base histórica, modularização e desenvolvimento estruturado;
"
Lógica: Unificação, variável lógica e não-determinismo;
"
Funcional: Sistemas de tipo e garbage collection;
"
Orientação a Objetos: Encapsulamento, classe, herança e polimorfismo;
"
"
Orientação a Agentes: Consciência e autonomia.
Em complemento, a seção 3.2 apresentou aspectos genéricos relacionados com
modelos e linguagens dedicadas à exploração do paralelismo e distribuição. Neste
contexto, foram salientadas as propriedades consideradas ideais para um modelo (seção
3.2.1). A criação de modelos com o uso de paradigmas não convencionais facilita a
concretização dessas propriedades. Merece destaque ainda a classificação de modelos
baseada nos níveis de abstração (seção 3.2.2). Conforme descrito na seção 3.2.4, o uso
de paradigmas não convencionais estimula a abstração completa do paralelismo. Sendo
assim, as propostas de exploração de paralelismo nos paradigmas não convencionais
tendem a se enquadrar nos primeiros grupos da classificação de Skillicorn e Talia (seção
61
3.2.2). Por outro lado, as propostas baseadas no paradigma convencional enquadram-se
nos últimos. Por sua vez, a seção 3.2.3 destacou que um dos principais temas a serem
abordados na criação de modelos paralelos e distribuídos é o gerenciamento da
comunicação e sincronização entre tarefas. Alguns dos diversos tipos de mecanismos de
gerenciamento apresentados podem ser naturalmente implementados em paradigmas
não convencionais, conforme demonstrou Shapiro para o paradigma em lógica (seção
3.4.2) .
A seção 3.3 abordou a exploração do paralelismo nos paradigmas de software. A
seção 3.3.1 mostrou que a utilização de diferentes paradigmas introduz no modelo
diferentes fontes de paralelismo. Sendo assim, a escolha do paradigma é também uma
escolha das fontes de paralelismo a serem exploradas. No paradigma convencional, a
exploração do paralelismo é dificultada pelos vários níveis de dependências de dados e
de controle. No paradigma em lógica, destacam-se como fontes de paralelismo a
execução paralela de ramos da árvore de busca (paralelismo OU) e de metas no corpo
de uma cláusula (paralelismo E). Ambas as fontes oriundas do não-determinismo
inerente à lógica. O paradigma funcional tem como principal fonte de paralelismo
implícito a solução paralela de expressões, as quais podem estar localizadas nos
argumentos das funções. Na orientação a objetos surgem como principais fontes de
paralelismo a execução paralela de objetos (paralelismo inter-objetos) ou das
invocações de métodos de um mesmo objeto (paralelismo intra-objeto).
A seção 3.4 apresentou quatro estudos de caso. No âmbito do paradigma
convencional, mostrou-se que o SR exige que o paralelismo seja tratado de forma
explícita através de comandos imperativos. O Concurrent Prolog mostra que a
programação em lógica suporta uma interpretação concorrente, a qual torna implícita a
exploração do paralelismo. No entanto, o Concurrent Prolog insere anotações explícitas
que permitem um gerenciamento do sincronismo e não-determinismo. No âmbito do
paradigma funcional, o GPH utiliza anotações para exploração do paralelismo em uma
linguagem não estrita (Haskell). Finalmente, o DPC++ é utilizado como exemplo de
exploração da distribuição na orientação a objetos.
Os capítulos dois e três apresentaram um estudo em abrangência relacionado com
software paralelo e distribuído. Este estudo foi estimulado pelas duas primeiras
motivações apresentadas na seção 1.2, ou seja:
o paralelismo implícito existente nos paradigmas não convencionais tem sido
indicado como a melhor abstração para criação de modelos e linguagens que
explorem o paralelismo;
#
a arquitetura distribuída (seção 2.3) é uma das mais promissoras plataformas
para o desenvolvimento de sistemas computacionais.
#
Ainda no capítulo um foram destacadas as duas motivações que estimulam o
desenvolvimento da próxima etapa deste estudo, ou seja:
os paradigmas básicos possuem vantagens e limitações. A criação de modelos
de desenvolvimento de software através da unificação dos paradigmas vem
sendo indicada como forma de superação das limitações e exploração conjunta
das características benéficas. Surge assim, o software multiparadigma;
#
#
uma das características benéficas compartilhada pelos paradigmas não
convencionais são suas fontes naturais de paralelismo. Sendo assim, a união
dos paradigmas é também uma união dessas fontes, as quais podem ser
62
exploradas em conjunto. Surge assim, o software multiparadigma paralelo e
distribuído.
Os próximos capítulos apresentam um estudo em profundidade relacionado com
software multiparadigma paralelo e distribuído.
Estudo
em
Profundidade
Software Multiparadigma
Paralelo e Distribuído
Capítulo 4 - Software multiparadigma ......................................64
Capítulo 5 - Software multiparadigma paralelo e distribuído ...78
64
4 Software multiparadigma
Este capítulo apresenta uma introdução ao estudo em profundidade. O texto
aborda temas relacionados com software multiparadigma. A seção 4.1 resume a
evolução da pesquisa multiparadigma. Por sua vez, a seção 4.2 contém uma breve
descrição de sete modelos multiparadigma (OLI, OWB, I+, DLO, ETA, G e Oz). Entre
eles destacam-se três (I+, DLO e Oz) que servirão de base para o estudo relacionado
com exploração do paralelismo em modelos multiparadigma apresentado no quinto
capítulo. A seção 4.3 discute a pesquisa multiparadigma e propõe uma taxonomia para
classificação de modelos. Por fim, a seção 4.4 contém as conclusões do capítulo. No
início da seção 3.1 afirma-se que um paradigma de software é baseado na sua entidadebase, ou seja, em uma entidade que atua como unidade de modelagem e determina as
regras utilizadas para criação de modelos. Essa definição será utilizada no decorrer
deste capítulo para discussão dos modelos multiparadigma.
4.1
História
Desde os primórdios da computação as plataformas de desenvolvimento baseadas
no paradigma convencional permitem a ligação de módulos criados em diferentes
linguagens. A necessária conversão de todos os programas para linguagem de máquina
motiva a integração. Freqüentemente, rotinas desenvolvidas em Assembly trazem maior
eficiência para programas criados em Fortran, Cobol, Pascal e C. Além disso, o
desenvolvimento de sistemas utilizando mais de uma linguagem de alto nível do
paradigma convencional é um procedimento comum. Este fato possui duas motivações,
ou seja, as facilidades específicas de cada linguagem e a heterogeneidade da maioria das
aplicações.
A criação de várias linguagens baseadas no mesmo paradigma possui a mesma
motivação que a criação de vários paradigmas, ou seja, a busca de representações
computacionais que facilitem a solução de problemas em um determinado universo. Em
essência, a motivação para integração de linguagens do paradigma convencional possui
a mesma origem que a motivação para integração de paradigmas, ou seja, a superação
das limitações impostas pelas soluções específicas.
Entre as primeiras publicações dedicadas ao estudo das propostas multiparadigma,
destaca-se o texto [IEE 86]. Nesta edição são apresentados oito artigos relacionados
com a pesquisa multiparadigma. Entre estes artigos, salienta-se o texto [HAI 86] onde
são apresentados nove projetos que propõem a integração de paradigmas.
Os artigos [PLA 91] e [MUL 95] apresentam resumos da evolução dos trabalhos
de pesquisa multiparadigma. Em ambos os textos constata-se o interesse da comunidade
científica na criação de um modelo multiparadigma ideal que integre em uma estrutura
única os avanços introduzidos pelos paradigmas básicos. Por sua vez, o texto [NGK 95]
apresenta uma interessante tabela que compara vinte e três propostas multiparadigma.
Conforme salientado em [PLA 91], grande parte do esforço dedicado à pesquisa
multiparadigma enfoca a integração entre dois paradigmas básicos. Entre os primeiros
trabalhos que seguiram essa tendência destacam-se as propostas de integração dos
paradigmas em lógica e funcional. O texto [HAN 94] apresenta os conceitos básicos
envolvidos na integração desses paradigmas. Além disso, [HAN 94] descreve várias
propostas para uso conjunto da lógica e funções como solução para modelagem
65
computacional. Neste escopo, ainda podem ser citadas as publicações [CHA 97] e
[HAN 97].
Por sua vez, o texto [BUG 94] apresenta os esforços da comunidade científica em
aplicar na programação em lógica os conceitos de modularidade desenvolvidos no
paradigma procedimental. Conforme descrito em [BUG 94], a modularização soluciona
uma das principais limitações da programação em lógica, ou seja, a falta de estrutura
para desenvolvimento organizado de grandes programas.
O surgimento do paradigma orientado a objetos como evolução do paradigma
convencional fez com que a comunidade científica percebesse a possibilidade de
integração da orientação a objetos com a programação em lógica. O texto [DAV 93]
apresenta um estudo sobre a integração desses paradigmas destacando as motivações,
técnicas e modelos propostos. O recente artigo [LEE 97] contém um resumo de
trabalhos de pesquisa que propõem a integração objeto/lógica. Em complemento, [AMA
96] discute o tema e propõe um novo modelo. Por sua vez, o artigo [WEG 93] apresenta
uma análise dos problemas existentes nesta integração. Neste texto, Peter Wegner
sugere que a integração completa desses paradigmas é impossível. No entanto, vários
estudos demonstram que interessantes resultados podem ser obtidos ([DAV 93],
[OMI 94]).
Merecem destaque os recentes esforços para o desenvolvimento de sistemas
distribuídos baseados em modelos multiparadigma. O texto [CIA 96] descreve uma
proposta para criação de objetos lógicos distribuídos. Por sua vez, o modelo
multiparadigma Oz ([SMO 95]) serve de base para diversos estudos nesta área
([ROY 97], [HAR 98], [HAR 99]). Em complemento, os textos [VRA 95] e [ZAV 96]
apresentam estudos relacionados com pesquisa multiparadigma no âmbito da
Engenharia de Software.
4.2
Estudos de caso
Esta seção apresenta uma análise resumida de sete modelos multiparadigma. São
enfatizadas as características relacionadas com a exploração do paralelismo. Destacamse entre os modelos apresentados, as três propostas (I+, DLO e Oz) que servirão de base
para o estudo sobre software multiparadigma paralelo e distribuído apresentado no
capítulo cinco. Em complemento, a seção 4.3 realiza uma discussão da pesquisa
multiparadigma e resume as características dos sete modelos.
4.2.1
OLI (Object Logic Integration)
O modelo OLI ([LEE 97]) foi criado por pesquisadores das universidades de
Hong Kong e Manchester. Este modelo propõe a integração da lógica e objetos como
base para o desenvolvimento de sistemas. No âmbito dessa proposta foram criadas uma
metodologia e uma linguagem, ambas denominadas OLI.
Os autores de OLI afirmam que a implementação de um complexo sistema
computacional depende de sua compreensão sobre dois aspectos, ou seja, análise e
síntese. A compreensão baseada em análise consiste na determinação dos componentes
individuais que compõem o sistema. Por sua vez, a síntese consiste na compreensão da
relações existentes entre os elementos componentes do sistema. Além disso, afirmam
ainda Lee e Pun ([LEE 97]) que o desenvolvimento orientado a objetos enfoca a análise
através da decomposição do sistema em componentes bem definidos denominados
66
objetos. Em complemento, o desenvolvimento em lógica promove a compreensão
através da síntese fazendo com que a relação entre componentes torne-se explícita. Com
base nestas afirmações, Lee e Pun afirmam que a integração desses paradigmas permite
a criação de um modelo próximo ao modelo mental ideal.
Em OLI a base para integração da lógica e objetos consiste na definição de uma
interface para comunicação entre os paradigmas. Além disso, OLI permite o
desenvolvimento de sistemas multiparadigma, sistemas orientados a objetos e sistemas
baseados em lógica. Sendo assim, a semântica de OLI pode ser compreendida através de
duas perspectivas, ou seja, através da orientação a objetos ou através da lógica.
Conforme afirmado em [LEE 97], vários modelos propõem a integração de
objetos e lógica. A principal diferença entre os demais modelos e OLI consiste na
abordagem equilibrada de ambos os paradigmas, ou seja, em OLI nenhum dos
paradigmas sobrepõe o outro. As demais propostas baseam-se no acréscimo de
construções de um paradigma no outro, estabelecendo assim um deles como base e o
outro como complemento. Merece destaque em [LEE 97] a análise de outros modelos
que integram objetos e lógica.
Em OLI um sistema é composto de objetos e definição de predicados ou seja:
Sistema = Objetos + Predicados
Objetos são entidades que possuem um estado e um comportamento funcional. O
estado de um objeto consiste em um conjunto de propriedades e seus valores correntes.
Por sua vez, o comportamento funcional é descrito por um conjunto de métodos os
quais estabelecem as trocas dinâmicas de estado e o envio de mensagens. Em
complemento, um objeto possui comportamento relacional. Esse comportamento
consiste em um conjunto de predicados os quais estabelecem relações com outros
objetos. Neste contexto, o paradigma orientado a objetos realiza o papel da análise
através da modelagem da natureza dinâmica do estado e do comportamento funcional
dos objetos. Por outro lado, o paradigma em lógica realiza o papel da síntese através da
modelagem da natureza estática do estado e comportamento relacional dos objetos. A
separação da natureza dinâmica e natureza estática do estado de objetos é um
importante princípio de projeto do modelo OLI. Esta separação estabelece uma parceria
entre os paradigmas durante o projeto de sistemas em OLI.
A metodologia OLI propõe a modelagem de um sistema em quatro passos:
$
Identificar as entidades e suas propriedades no sistema;
%
Dividir as propriedades de cada entidade em seus estados e comportamentos
funcional e relacional;
&
Organizar os estados e comportamentos funcionais de todas as entidades em
um sistema como diferentes classes hierárquicas de objetos;
'
Representar os comportamentos relacionais de todas as entidades como
predicados envolvendo objetos.
A versão atual da linguagem OLI possui como base as linguagens Smalltalk e
Prolog. No entanto, a estrutura de OLI não depende de nenhuma característica
específica destas linguagens. Conforme afirmado em [LEE 97], ambas as linguagens
pode ser substituídas por linguagens puras orientadas a objetos e orientadas à lógica.
Um programa OLI é composto de duas partes, ou seja, a parte da lógica e a parte
de objetos. Os criadores de OLI argumentam que a interface entre os paradigmas é
67
definida pelas entidades considerando-se o ponto de vista de cada uma das partes do
programa. Considerando o ponto de vista da lógica, as entidades constituem um
Universo de Herbrand Enriquecido (enriched Herbrand universe- eHu). O eHu
resulta do acréscimo, ao universo de Herbrand, de objetos definidos na parte de objetos
do programa OLI. No eHu encontram-se dois tipos de entidades, ou seja, o-terms e hterms. H-terms são termos comuns encontrados nos programas em lógica. Do ponto de
vista semântico, o-terms também são termos. No entanto, o estado ou atributo de um oterm não está explícito na estrutura do termo. A obtenção dessas informações deve ser
realizada através de mensagens ao invés de unificação. Por outro lado, do ponto de vista
de objetos, todas as entidades são um conjunto de objetos. Os termos do universo de
Herbrand também são considerados objetos. Em OLI, termos de Herbrand são
instâncias de uma classe denominada PTerm. Essa classe prove métodos para
manipulação das estruturas dos termos.
Destacam-se como principais constatações sobre OLI:
o modelo OLI propõe a integração equilibrada dos paradigmas em lógica e
orientado a objetos. A base da integração consiste na definição de uma
interface que permita uma clara semântica do ponto de vista de ambos os
paradigmas. Os paradigmas em lógica e orientado a objetos ficam inalterados.
Existe apenas o acréscimo de algumas novas características em ambos de
forma a permitir a colaboração no desenvolvimento de sistemas. Não é criada
nenhuma nova entidade-base. Dependendo da parte do programa a entidadebase é o objeto (parte de objetos) ou o predicado lógico (parte da lógica);
(
os autores de OLI propõem uma metodologia e uma linguagem. Em [LEE 97] é
apresentado um exemplo da aplicação de ambas na solução de um problema.
Em complemento, em [LEE97] é destacada a importância da criação de uma
ferramenta CASE para utilização da metodologia OLI e geração automática de
código OLI.
(
4.2.2
OWB (Objects With Brain)
O modelo OWB ([AMA 96]) foi criado na Universidade Federal do Rio Grande
do Sul no âmbito da tese de doutorado de Analía Amandi ([AMA 97]) orientada pela
professora Ana Price. Este modelo propõe a integração dos paradigmas em lógica e
orientado a objetos como solução para o desenvolvimento de agentes.
Merece destaque no texto [AMA 96] a descrição dos possíveis caminhos para
integração de objetos e lógica. São citados três caminhos, ou seja:
extensão do paradigma em lógica com conceitos da orientação a objetos;
)
extensão da orientação a objetos com conceitos do paradigma em lógica;
)
)
criação de uma ponte entre orientação a objetos e o paradigma em lógica.
Conforme descrito em [AMA 96], OWB integra objetos e lógica permitindo que
objetos tenham parte de seu conhecimento privado expresso como cláusulas lógicas e
métodos implementados em lógica, de forma parcial ou total. Sendo assim, OWB opta
pelo segundo caminho, ou seja, estende a orientação a objetos com conceitos do
desenvolvimento em lógica. Essa extensão é suportada por uma nova classe denominada
LogicKnowledge. A implementação de OWB utiliza Smalltalk-80 estendida com MeiProlog, uma versão de Prolog desenvolvida em Smalltalk.
68
Amandi e Price destacam que a orientação a objetos possui as vantagens da
modularidade, herança e ocultamento de informações. No entanto, em algumas
aplicações é necessária a procura dinâmica de soluções que o paradigma em lógica
proporciona. Sendo assim, a possibilidade de acréscimo de conhecimento na forma
declarativa aos objetos torna-se interessante. Em complemento, é salientado em
[AMA 96] que uma característica benéfica do caminho escolhido por OWB é que o
comportamento procedimental (interfaces, gráficos, etc) pode ser expresso de forma
procedimental.
Entre as principais conclusões relacionadas com OWB destacam-se:
o principal objetivo de OWB consiste em suportar a programação orientada a
agentes. A lógica é introduzida como suporte à representação de conhecimento
dentro dos objetos. Sendo assim, OWB não possui nenhuma nova entidadebase. A modelagem é baseada em objetos apesar da possibilidade da
existência de objetos com conhecimento privado expresso em forma de
predicados lógicos. A modelagem utiliza três entidades distintas, ou seja,
agentes, objetos e predicados;
*
Amandi e Price propõem em [AMA 97] uma arquitetura de agentes
denominada Brainstorm. Essa arquitetura define como sistemas multi-agentes
podem ser construídos em termos de um metasistema de um sistema orientado
a objetos. A criação de agentes é baseada nesta arquitetura e na linguagem
OWB;
*
*
4.2.3
a implementação de OWB possui como base o Smalltalk. Mesmo o Prolog
utilizado na integração foi desenvolvido em Smalltalk. A linguagem OLI
(seção 4.2.1) também possui como base essas linguagens. Entretanto, em OLI
o usuário programa em ambos os paradigmas de forma separada. Na parte de
objetos o universo é orientado a objetos e na parte da lógica o universo é
orientado a lógica. Por outro lado, em OWB a programação em lógica é
encapsulada em objetos, ou seja, o desenvolvimento é orientado a objetos e a
lógica fica restrita ao interior dos objetos.
I+
O modelo I+ ([NGK 95]) está sendo desenvolvido através de um trabalho conjunto
entre a Universidade de Hong Kong e a Universidade de Toronto. Conforme salientado
em [NGK 95], o I+ é uma evolução da linguagem multiparadigma I. Esta evolução
contempla características do paradigma orientado a objetos e suporta um ambiente de
programação com facilidades de edição de texto, compilação e depuração.
O I+ integra três paradigmas básicos: desenvolvimento em lógica, funcional e
orientado a objetos. A integração desses paradigmas cria uma nova proposta de
desenvolvimento denominada programação declarativa orientada a objetos. O
modelo suporta os conceitos de classe, objeto, métodos, herança e troca de mensagens.
No entanto, na linguagem I+ os métodos são criados de forma diferente do que nas
linguagens orientadas a objetos com enfoque procedimental. No I+ os métodos não são
procedimentos, mas sim, conjuntos de cláusulas ou funções. Dessa forma, os
paradigmas declarativos (lógica e funcional) são incorporados no nível dos métodos da
orientação a objetos.
69
O modelo I+ permite dois tipos de classes, ou seja, classe lógica (logic_class) e
classe funcional (functional_class). Estas classes diferem na forma com que seus
métodos são definidos. Métodos na classe lógica são predicados lógicos e recebem o
nome de métodos lógicos (logic methods). Por sua vez, métodos na classe funcional são
funções e recebem o nome de métodos funcionais (functional methods). O texto
[NGK 95] apresenta a estrutura geral das classes em I+ através de uma representação em
BNF.
O I+ suporta dois níveis de paralelismo, isto é, paralelismo inter-objetos e intraobjetos. A primeira abordagem propõe a execução paralela de diferentes objetos. Por
sua vez, a segunda abordagem propõe a execução paralela de diferentes métodos no
mesmo objeto. O texto [NGK 95] apresenta uma comparação do I+ com outros modelos
multiparadigma com enfoque especial para os níveis de paralelismo explorados em cada
modelo. Merece destaque ainda no texto [NGK 95], uma comparação entre os três
paradigmas integrados salientando a contribuição de cada paradigma para o modelo
resultante.
As seguintes conclusões merecem destaque:
I+ integra em um único modelo os três paradigmas básicos envolvidos. No
entanto, a base do modelo consiste na orientação a objetos. A introdução de
novos paradigmas pode ser facilmente realizada através da criação de novas
classes. O usuário organiza os sistemas em objetos, mas programa os
algoritmos de forma declarativa (lógica ou funções). Sendo assim, o modelo
possui três entidades-base, ou seja: objetos, predicados e funções. O I+ não
propõe nenhuma nova entidade-base;
+
existe uma forte preocupação dos criadores do modelo com o suporte ao
paralelismo. Conforme descrito em [NGK 95], o I+ é executado em uma
plataforma composta de estações de trabalho com sistema operacional Unix.
Sendo assim, a versão atual suporta processamento distribuído. A seção 5.1
discute em detalhes a metodologia para exploração de paralelismo no I+.
+
4.2.4
DLO (Distributed Logic Objects)
O DLO ([CIA 96]) é um modelo multiparadigma que está sendo desenvolvido
através de um trabalho conjunto entre a Universidade de Bologna e a Universidade de
Ferrara, ambas localizadas na Itália. O modelo é baseado no paradigma de
desenvolvimento em lógica. No entanto, utiliza objetos, mensagens e herança,
características do paradigma orientado a objetos. A proposta estende a programação em
lógica, no entanto, mantém sua capacidade dedutiva e a leitura declarativa dos
programas. Conforme destacado em [CIA 96], o modelo explora características
interessantes da lógica, tais como, alto poder de expressão, semântica clara e
paralelismo implícito. Por outro lado, o DLO introduz características consideradas
fundamentais para o desenvolvimento de grandes aplicações, tais como, modularidade e
encapsulamento.
Merecem destaque as seguintes características do modelo DLO:
modelo de execução composto por processos assíncronos que se comunicam
através de mensagens;
+
+
linguagem lógica estendida com Cláusulas de Múltiplas Cabeças;
70
troca de estado é suportada pelo mapeamento de objetos lógicos em processos
e pelo uso de unificação e recursividade;
,
comunicação é implementada através da unificação e redução de metas
paralelas com cláusulas de múltiplas cabeças.
,
Os autores de [CIA 96] destacam ainda o alto nível de paralelismo implícito
existente no modelo DLO. Existem dois níveis de paralelismo, ou seja, instâncias da
mesma ou de diferentes classes podem executar em paralelo (paralelismo inter-objeto) e
a avaliação paralela de diferentes métodos da mesma instância (paralelismo intraobjeto).
As principais conclusões e constatações relacionadas com o modelo DLO são:
o modelo propõe a unificação dos paradigmas em lógica e orientado a objetos,
utilizando como base o primeiro. A entidade-base de DLO é o objeto lógico;
,
,
4.2.5
o modelo contempla a exploração do paralelismo implícito, em especial, a
utilização do processamento distribuído. A seção 5.2 aprofunda o estudo em
relação ao paralelismo em DLO.
ETA (Everything buT Assignment)
O modelo ETA ([AMB 96]) foi proposto por membros do Departamento de
Informática da Universidade de Pisa, Itália. Conforme destacado por seus criadores, a
principal motivação para a criação de ETA consiste no interesse em uma linguagem
para implementação de políticas de cooperação no desenvolvimento de sistemas.
Conforme destacado em [AMB 96], políticas de cooperação podem ser expressas em
linguagens que possuam as seguintes propriedades: modularidade, reusabilidade e
suporte à concorrência. Essas mesmas necessidades são compartilhadas por projetistas
de sistemas distribuídos.
O modelo ETA possui como base a união dos paradigmas em lógica e orientado a
objetos. Além disso, ETA utiliza o paradigma de Múltiplos Espaços de Tuplas (MET)
como suporte para essa unificação e para organização dos sistemas. Linguagens
concorrentes baseadas no paradigma de Espaços de Tuplas (ET) utilizam memória
compartilhada. Nesta abordagem, o espaço de armazenamento é um conjunto de tuplas
que representam os estados computacionais. Além disso, entidades computacionais
autônomas (processos) cooperam através de leituras e escritas no espaço de tuplas. A
proposta MET é uma extensão do paradigma ET. Nesta nova proposta, um sistema é
composto de um conjunto de ETs, os quais não compartilham memória. Em
complemento, tuplas podem ser enviadas de um ET para outro. Esta abordagem permite
a combinação dos paradigmas de memória compartilhada e troca de mensagens.
Conforme citado em [AMB 96], entre as linguagens de programação baseadas no
paradigma MET destacam-se Linda-3, ESP e Pâté. Merece destaque ainda no texto
[AMB 96], a afirmação de que um modelo MET permite dois tamanhos de grãos na
exploração do paralelismo, ou seja, alta granulosidade entre ETs e baixa granulosidade
entre processos. Estes dois níveis estão relacionados com os dois modelos de
cooperação proporcionados, respectivamente, troca de mensagens e memória
compartilhada.
O texto [AMB 96] destaca que a combinação da lógica e dos múltiplos espaços de
tuplas resulta em um paradigma que integra declaratividade e cooperação. Esta
combinação é baseada nas seguintes características:
71
uma tupla é um fato e a interação entre os espaços de tupla e os processos é
controlado pelo algoritmo de unificação. O texto [AMB 96] salienta que o
poder de expressão de uma linguagem baseada em espaços de tuplas é
incrementado pela unificação;
-
um subconjunto da linguagem Prolog é utilizado para realizar a computação
associada com cada regra.
-
Em relação à orientação a objetos, os criadores de ETA destacam que a interface
de um espaço de tuplas é definido pelas tuplas aceitas como entrada e aquelas
produzidas como saída, ou seja, existe uma semelhança na comunicação entre objetos e
entre espaços de tuplas. ETA controla o fluxo de tuplas entre objetos (espaços de tuplas)
através da unificação. Em complemento, a herança em ETA é baseada na definição de
novos espaços de tuplas pela extensão de interfaces e pela redefinição de parte das
regras que especificam o comportamento dos objetos. Merece destaque ainda que em
ETA o recebimento de uma mensagem faz com que a tupla recebida seja adicionada ao
estado do objeto (espaço de tuplas). Este comportamento difere da maioria das
linguagens orientadas a objeto onde a chegada de uma mensagem faz com que seja
realizada uma operação ou invocado um procedimento. Em [AMB 96] encontra-se uma
clara descrição da sintaxe e semântica de ETA.
Destacam-se as seguintes conclusões a respeito de ETA:
o modelo utiliza a orientação a objetos como estrutura básica para o
desenvolvimento de sistemas. Em complemento, conforme mostrado em
[AMB 96], ETA possui uma sintaxe semelhante à programação em lógica para
codificação dos objetos. A filosofia de Múltiplos Espaços de Tuplas é utilizada
como suporte para o fluxo e organização dos dados. Sendo assim, a entidadebase é o objeto codificado com sintaxe ETA, ou seja, o objeto ETA. Este tipo
de objeto é diferente do objeto lógico e do objeto utilizado no paradigma
orientado a objetos. Ele possui sintaxe própria criada pelo modelo ETA;
-
conforme destacado em [AMB 96], o modelo ETA possui uma estrutura
adequada para criação de sistemas distribuídos. Os autores destacam em
diversas partes do texto o interesse pela criação de um paradigma que suporte
o desenvolvimento de grandes sistemas distribuídos. Essa é uma das principais
motivações para a existência de ETA;
-
na conclusão do artigo [AMB 96] é destacado que os autores estão dedicando
seus esforços para a criação de um compilador e um sistema de execução
distribuída para ETA.
-
4.2.6
G
O texto [PLA 91] apresenta o modelo multiparadigma G. Este modelo foi
proposto na tese de doutorado de John Placer desenvolvida na Universidade de Oregon.
O modelo G suporta quatro paradigmas básicos, ou seja, os paradigmas em lógica,
funcional, convencional e orientado a objetos. Além disso, John Placer afirma que
pretende introduzir novos paradigmas em versões mais avançadas de G.
Conforme afirmado em [PLA 91], G é uma linguagem experimental que foi
projetada para o estudo de estruturas sintáticas e semânticas que suportem a integração
de vários paradigmas de desenvolvimento. A principal estrutura da linguagem G é a
stream. Em G todos os valores são considerados streams. Os tipos escalares, tais como
72
int, real, type, char e string são interpretados como streams de um único elemento.
Além disso, existem dois tipos compostos denominados stream e relation. Um tipo
composto é uma stream que pode possuir qualquer número de elementos. O artigo
[PLA 91] descreve como o conceito de stream e suas qualidades (ambiente, seqüência
de valores e protocolo de enumeração) permitem a criação de uma semântica unificada
para compreensão das estruturas de dados e estruturas de controle da linguagem G. Em
relação ao paralelismo, o autor destaca que o uso de streams como estrutura de dados
fundamental da linguagem estimula sua implementação em arquiteturas paralelas.
A linguagem G não possui como base nenhum dos paradigmas suportados. A
linguagem cria uma nova sintaxe e semântica baseadas no conceito de stream.
Conforme demonstrado através de exemplos em [PLA 91], G pode ser aplicada na
solução de problemas clássicos dos paradigmas em lógica, convencional, funcional e
orientado a objetos. Além disso, [PLA 91] exemplifica a mistura desses paradigmas
durante o desenvolvimento de sistemas.
John Placer afirma que durante o desenvolvimento de uma plataforma
multiparadigma não se deve considerar os paradigmas básicos como entidades atômicas,
mas sim, realizar a decomposição deles em suas características essenciais. Em seguida,
deve-se realizar a análise dessas características de forma independente. O projeto de um
modelo multiparadigma consiste na obtenção de soluções criativas que permitam o uso
das características essenciais dos paradigmas suportados. Merece destaque ainda, a
afirmação de que a impossibilidade de integração de uma característica considerada
essencial em um paradigma básico não deve eliminar o paradigma do modelo
multiparadigma em desenvolvimento. Neste sentido, salienta John Placer que a
linguagem G não suporta completamente variáveis lógicas, mas no entanto, permite que
várias características deste tipo de variável sejam suportadas.
Destacam-se as seguintes constatações a respeito de G:
a linguagem não estabelece nenhum paradigma como sua base, mas no
entanto, suporta os paradigmas em lógica, convencional, funcional e orientado
a objetos. Por outro lado, G estabelece a estrutura stream e suas características
como sendo a base sintática e semântica para criação de programas. Os
exemplos de expressão dos paradigmas básicos através de G, apresentados em
[PLA 91], demonstram que a stream é sempre utilizada como entidade da
modelagem. Sendo assim, a entidade-base de G é a stream;
.
o modelo não contempla o processamento paralelo e distribuído. Durante a
apresentação da linguagem G não são enfatizadas formas para exploração do
paralelismo na linguagem. Existe uma pequena citação do potencial de
streams para exploração do paralelismo, mas no entanto, torna-se claro que o
processamento paralelo e distribuído não foi priorizado nos estudos de John
Placer;
.
.
parece bastante adequado o caminho proposto por John Placer para o
desenvolvimento de modelos multiparadigma, ou seja, a decomposição dos
paradigmas básicos em suas características essenciais e a unificação dessas
características em um modelo único com uma nova visão sintática e semântica.
73
4.2.7
Oz
O modelo Oz ([SMO 95], [HAR 99a]) foi criado no Centro Germânico de
Pesquisa em Inteligência Artificial (DFKI), Alemanha. Este modelo possui como base a
linguagem AKL ([JAN 93a]) criada no Instituto Sueco de Ciência da Computação. Seus
criadores afirmam que Oz pode substituir linguagens de alto nível seqüenciais, tais
como, Lisp, Prolog e Smalltalk.
A computação em Oz ocorre em um espaço computacional onde existem tarefas
conectadas através de um armazenamento compartilhado. A computação avança através
da redução de tarefas. A redução de uma tarefa pode manipular o armazenamento e criar
novas tarefas. Uma tarefa desaparece quando reduzida. O armazenamento
compartilhado é denominado constraint store. Nele podem ser armazenados um
conjunto de fórmulas matemáticas denominadas restrições. Uma importante
característica da constraint store é o fato de que ela pode armazenar informações
parciais a respeito de variáveis. Além disso, é monotônica, ou seja, informações
armazenadas nunca se perdem. A informação acrescentada deve ser coerente com o
restante das informações armazenadas. Em complemento, a coerência da constraint
store é mantida após o acréscimo de informações. Uma tarefa pode atribuir restrições ao
armazenamento, podendo assim, ocasionar diversos efeitos colaterais. Conforme afirma
Gert Smolka ([SMO 95]), através da constraint store é criado um mecanismo
declarativo de sincronização entre tarefas.
Conforme demonstrado em [MUL 95], Oz é um poderoso modelo
multiparadigma. A sintaxe e semântica da linguagem não estão limitadas a nenhum
paradigma básico. Em [MUL 95], Oz é utilizado na solução de problemas clássicos do
universo do desenvolvimento em lógica, funcional e orientado a objetos. Apesar do seu
enfoque multiparadigma, Oz permite a utilização de conceitos de paradigmas básicos.
Por exemplo, estão disponíveis conceitos da orientação a objetos, tais como, objetos,
classes, métodos e mensagens.
Merecem destaque ainda as seguintes características de Oz ([SMO 95]):
suporta Procedimentos de Primeira Classe;
/
utiliza o conceito de Porta (procedimento ligado a uma stream) para
comunicação ([JAN 93]);
/
suporta o conceito de thread;
/
implementa Busca Encapsulada (suporte ao não-determinismo);
/
Nos últimos anos vários trabalhos de pesquisa vêm sendo desenvolvidos para
criação de uma plataforma distribuída para o modelo Oz ([ROY 97], [HAR 98],
[HAR 99]). Esta plataforma é denominada Mozart ([SMO 95a], [ROY 99]). Neste
escopo estão sendo pesquisados diversos tópicos, tais como, utilização de variáveis
lógicas em sistemas distribuídos ([HAR 99]) e objeto móveis em Oz distribuído
([ROY 97]).
Em relação ao modelo analisado destacam-se as seguintes conclusões:
/
Oz não foi construído a partir de nenhum paradigma básico. Os criadores de
Oz propõem um novo modelo baseado nos conceitos dos paradigmas
existentes. O principal conceito para compreensão de Oz é o espaço
computacional onde são executados os programas. As tarefas que são
reduzidas durante a computação podem ser consideradas como unidades de
74
processamento (procedimentos, processos, threads, objetos). Sendo assim, a
entidade-base de Oz é a tarefa executada no espaço computacional. No
entanto, nota-se em Oz uma forte tendência para organização das tarefas em
objetos ([HEN 97]);
Oz é um modelo de programação concorrente. O modelo computacional que
suporta a execução de diversas tarefas compartilhando um armazenamento
(espaço computacional) é inerentemente concorrente. Os textos que descrevem
o modelo destacam essa característica e seu potencial para exploração
implícita do processamento paralelo e distribuído ([SMO 95a], [ROY 97],
[HAR 98], [HAR 99]). Um estudo das características para exploração da
distribuição em Oz (modelo Mozart) é apresentado na seção 5.3;
0
0
4.3
Oz possui um ambiente de desenvolvimento composto de um compilador e
um depurador. No entanto, o modelo Oz não propõe uma metodologia
completa de desenvolvimento. Não é apresentada uma proposta para
modelagem de sistemas complexos através de instrumentos gráficos.
Taxonomia multiparadigma
A criação de uma taxonomia para os membros de um universo depende do estudo
de suas características. Durante esse estudo, normalmente surgem semelhanças que
podem ser utilizadas para organização dos membros em grupos. Com base na
amostragem apresentada na seção 4.2, pode-se criar uma taxonomia para os modelos
multiparadigma.
Os modelos multiparadigma compartilham a mesma proposta, ou seja, através da
união de paradigmas básicos propõem a criação de um modelo mais amplo e eficiente.
O modelo criado deve manter as características benéficas dos paradigmas unificados e
eliminar suas deficiências. Sendo assim, a palavra chave no universo multiparadigma é
unificação.
Conforme descrito na seção 3.1, os paradigmas podem ser caracterizados pelas
suas entidades-base. Quanto maior a proximidade semântica entre a entidade-base e as
entidades reais do universo a ser modelado, maior será a facilidade para o
desenvolvimento de sistemas. Os paradigmas básicos enfocam universos limitados que
devem ser modelados através de comandos, funções, lógica, objetos e agentes. Por outro
lado, a proposta multiparadigma está baseada na unificação de paradigmas. A
unificação semântica de paradigmas corresponde à criação de uma entidade-base que
suporte a modelagem nos universos semânticos que foram unificados. Portanto, o
modelo multiparadigma deve ser mais genérico que os paradigmas unificados, sem no
entanto, reduzir a eficiência na modelagem. O processo de generalização da entidadebase tende a diminuir seu poder de expressão nos universos que foram unificados. Este
é o principal desafio a ser vencido na criação de modelos multiparadigma.
A criação de modelos multiparadigma pelo processo de generalização constitui
uma abordagem bottom-up, ou seja, busca modelos mais genéricos pela unificação de
modelos mais específicos. Este processo é natural, pois os modelos mais específicos já
existem e servem de base para os novos modelos a serem criados. No entanto, o enfoque
bottom-up limita a criação de novos paradigmas. Essa limitação é ocasionada pelo
comprometimento da abordagem bottom-up com os conceitos existentes nos paradigmas
unificados. O termo multiparadigma é oriundo da abordagem bottom-up. Esse termo
75
enfoca a idéia de suporte a múltiplos paradigmas, ou seja, um modelo que suporte vários
paradigmas já existentes.
Os modelos multiparadigma podem ser classificados pela eficiência com que
atingem os objetivos da abordagem bottom-up. Essa eficiência pode ser medida de
acordo com dois índices, ou seja, número de paradigmas básicos unificados
(quantidade) e semântica da unificação (qualidade). O primeiro índice estabelece a
amplitude do modelo, ou seja, quantos universos específicos (paradigmas básicos) ele
abrange? O segundo índice estabelece a qualidade da unificação, ou seja, o quanto a
semântica do novo modelo torna implícita a semântica dos paradigmas unificados? Este
índice estabelece o quanto os paradigmas unificados ainda estão visíveis na nova
proposta. O primeiro índice é um número inteiro. O segundo índice é mais subjetivo e
possui três níveis, ou seja:
Multiparadigma de Integração (MI): O modelo não unifica os paradigmas,
apenas realiza a integração. Os paradigmas estão presentes, visíveis e
independentes. O modelo suporta algum nível de interação entre as entidadesbase dos paradigmas integrados. O desenvolvimento envolve modelagem em
universos distintos através de entidades-base distintas, ou seja, são utilizadas
semânticas diferentes. Normalmente, as linguagens de programação de um
paradigma básico suportam a chamada de rotinas desenvolvidas em outro. Este
é um caso clássico de modelo MI. A modelagem MI não estabelece um
equilíbrio entre paradigmas. Por exemplo, 90 % de um sistema pode ser
desenvolvido através do paradigma imperativo e os restantes 10 % através de
rotinas do paradigma em lógica. Neste caso, apesar da predominância de um
paradigma, o desenvolvimento utiliza dois paradigmas. Portanto, o sistema
possui características multiparadigma. Nenhum dos modelos apresentados na
seção 4.2 é MI;
1
Multiparadigma de Unificação Parcial (MUP): O modelo unifica
parcialmente os paradigmas. Os paradigmas estão presentes, visíveis, mas
dependentes. Durante a modelagem são utilizados universos distintos, ou seja,
entidades-base distintas. Portanto, ainda sobrevivem múltiplas semânticas. No
entanto, o modelo cria uma semântica multiparadigma de unificação parcial
(semântica MUP) que transcende a semântica dos paradigmas unificados. Essa
semântica é a base da unificação. No universo MUP, normalmente um
paradigma serve de base e os demais são complementares. Entre as propostas
descritas na seção 4.2, são MUP os modelos OLI, OWB e I+;
1
1
Multiparadigma de Unificação Total (MUT): O modelo unifica
completamente os paradigmas. Os paradigmas estão presentes através de suas
características, mas não são visíveis. Durante o desenvolvimento é utilizado
apenas um universo, ou seja, apenas uma entidade-base denominada entidade
de unificação total (entidade MUT). Não sobrevivem as semânticas dos
paradigmas unificados. O modelo cria uma semântica multiparadigma de
unificação total (semântica MUT). Entre os modelos descritos na seção 4.2
são propostas MUT: DLO, ETA, G e Oz. No universo MUT, o termo
multiparadigma assume um significado interessante. Um modelo MUT cria um
novo paradigma que suporta os paradigmas ditos unificados, ou seja, a visão
multiparadigma persiste apenas como uma abordagem bottom-up. A entidade
MUT e a semântica MUT são termos gerados pela abordagem bottom-up. O
universo do novo paradigma deve ser mais amplo do que apenas a união dos
universos unificados. Neste caso, a visão bottom-up é restritiva.
76
Os dois índices (quantidade e qualidade) devem ser aplicados em conjunto para
descrição de um modelo multiparadigma. Por exemplo, o I+ é um modelo MUP 3, ou
seja, unifica parcialmente três paradigmas (desenvolvimento em lógica, funcional e
orientado a objetos). No caso do universo MUT, o número de paradigmas unificados é
determinado pela apresentação do modelo. Normalmente, os autores salientam em
publicações o número de paradigmas suportados pela suas propostas. Além disso, os
autores costumam demonstrar, através de publicações, a aplicação de suas propostas em
problemas clássicos dos paradigmas suportados (veja o texto [MUL 95] para o modelo
Oz e o texto [PLA 91] para G).
A tabela 4.1 apresenta a classificação dos modelos descritos na seção 4.2. A tabela
possui oito colunas, ou seja: nome do modelo, nível de unificação, quantidade de
paradigmas unificados, paradigmas unificados, paradigma que serve de base para a
unificação, semântica utilizada como suporte à unificação, entidade-base do modelo e
classificação segundo a taxonomia multiparadigma. Os modelos estão listados na
mesma ordem em que foram descritos.
4.4
Conclusão
Este capítulo foi dedicado ao estudo do universo multiparadigma. A apresentação
de sete modelos permitiu uma visão concreta do tema. Em complemento, foi
apresentada uma taxonomia que possibilitou a organização e o aprofundamento do
estudo. Destacam-se como principais conclusões deste capítulo:
os modelos multiparadigma possuem como base os paradigmas de
desenvolvimento descritos na seção 3.1. Estes paradigmas estão presentes com
maior ou menor intensidade dependendo do modelo;
2
os modelos multiparadigma, da mesma forma que os paradigmas básicos,
possuem entidades-base. Um modelo multiparadigma pode utilizar as
entidades-base dos paradigmas que serviram para sua criação ou pode propor
uma nova entidade de unificação;
2
o principal desafio para criação de uma nova entidade-base para um modelo
multiparadigma consiste no fato de que a entidade criada é mais genérica do
que as entidades dos paradigmas unificados e, assim, existe uma tendência
natural à diminuição da eficiência na aplicação do novo modelo no âmbito dos
universos específicos que foram unificados;
2
algumas propostas de modelos multiparadigma enfocam, de forma especial, a
exploração do processamento paralelo e distribuído. Os modelos I+, DLO,
ETA e Oz possuem esse enfoque;
2
2
algumas propostas utilizam novas abordagens de modelagem como suporte à
proposta multiparadigma. Por exemplo, Objetos Lógicos Distribuídos no
modelo DLO, Espaço Computacional em Oz e Múltiplos Espaços de Tuplas
em ETA.
Trabalhos futuros poderão aperfeiçoar o estudo apresentado neste capítulo. Existe
uma grande variedade de modelos multiparadigma. A classificação de outros modelos
permitirá a expansão da tabela 4.1. Além disso, novas taxonomias multiparadigma
podem ser criadas. O próximo capítulo discute em detalhes a exploração do paralelismo
em três modelos multiparadigma, ou seja: I+, DLO e Oz.
77
TABELA 4.1 - Classificação de modelos multiparadigma
Mod.
OLI
OWB
I+
Nível
Parcial
Parcial
Parcial
Quant.
de
Parad.
2
3
3
DLO
Total
2
ETA
Total
2
G
Oz
Total
Total
4
4
Paradigmas
Unificados
Orientação a
Objetos e
Lógica
Orientação a
Objetos,
Orientação a
Agentes e
Lógica
Paradigma
Base
Semântica de
Unificação
Não
Possui
Mapeamento
Objeto
Lógica
(Classe Pterm) e
Lógica
Objeto
(Enriched
Herbrand Universe
- eHu)
3
Orientação a
Objetos
3
Suporte à criação
de agentes através
da inserção de
lógica em objetos
(classe
LogicKnowledge)
Entidades
Base
Objeto e
Predicado
Lógico
Objeto,
Agente e
Predicado
Lógico
Classif.
MUP 2
MUP 3
Orientação a
Objetos
Programação
Declarativa
Orientada a
Objetos, ou seja,
especificação de
objetos através da
lógica (logic_class)
e funções
(functional_class)
Objeto,
Predicado
Lógico e
Funções
Não
Possui
Processos
organizados em
Objetos Lógicos
implementados
através de
Cláusulas de
Múltiplas Cabeças
Objeto
Lógico
MUT 2
Orientação a
Objetos e
Lógica
Não
Possui
Múltiplos Espaços
de Tuplas
Objeto
ETA
MUT 2
Convencional,
Orientação a
Objetos,
Lógica e
Funcional
Não
Possui
Universo
de Streams
Stream
MUT 4
Tarefa
MUT 4
Orientação a
Objetos,
Lógica e
Funcional
Orientação a
Objetos e
Lógica
Convencional,
Orientação a
Objetos,
Lógica e
Funcional
Não
Possui
Espaço
Computacional, ou
seja, tarefas
conectadas através
de um
armazenamento
compartilhado
MUP 3
78
5 Software multiparadigma paralelo e distribuído
Este capítulo dedica-se ao estudo do software multiparadigma paralelo e
distribuído. Neste escopo são apresentados três estudos de caso. A seção 5.1 aborda o
paralelismo no âmbito do I+. Na seção 5.2 é discutida a exploração do paralelismo no
modelo DLO. Por sua vez, a seção 5.3 dedica-se ao estudo do Mozart, ou seja, a
plataforma para execução distribuída de programas desenvolvidos em Oz. Finalmente, a
seção 5.4 apresenta a conclusão do capítulo, a qual pode ser considerada a conclusão do
estudo em profundidade.
5.1
I+
Conforme descrito na seção 4.2.3, I+ integra os paradigmas em lógica, funcional e
orientado a objetos. Os paradigmas declarativos são utilizados para implementação dos
métodos e, portanto, ficam encapsulados nos objetos. Em [NGK 95, p.91], Kam e Chi
afirmam que existem duas formas para exploração do paralelismo em I+, ou seja,
paralelismo inter-objetos e intra-objetos.
No âmbito do paralelismo inter-objetos são utilizados dois modos para
invocação de métodos (mensagens), ou seja, síncrono e assíncrono. No modo síncrono,
após o envio de uma mensagem, o objeto origem aguarda a resposta do objeto destino.
Em I+ o envio de uma mensagem síncrona possui a seguinte sintaxe:
..., O::p, G,...
A meta G não será executada até que o resultado da chamada do método p no
objeto O seja retornado.
Em complemento, no modo assíncrono o objeto prossegue sua execução logo
após o envio da mensagem. Quando a resposta é recebida, seu conteúdo é armazenado
em uma estrutura de dados interna do objeto origem. A tentativa de acesso à resposta
pode ser realizada em qualquer momento após o envio da solicitação. No entanto, se a
resposta ainda não está disponível, o objeto origem deverá aguardar sua chegada. A
sintaxe de um chamada assíncrona em I+ é a seguinte:
..., O>>m(X), A, B, O??m(X), c(X), ...
Neste caso, a invocação do método m no objeto O é assíncrona (representada pelo
símbolo >>). O ponto de sincronismo ocorre após a execução das metas A e B.
Portanto, ambas serão executadas em paralelo com o objeto O. A resposta é acessada
com o uso do operador ??. Após o recebimento da resposta, a meta c será executada
utilizando o valor X obtido durante a execução do método m. Afirmam os criadores de
I+ que a decomposição de uma chamada de método em duas fases (requisição e
resposta) permite a execução paralela de atividades em múltiplos objetos. Afirmam
ainda que, os modos síncrono e assíncrono podem ser utilizados para a chamada de
métodos em lógica ou funcionais.
O paralelismo intra-objetos suporta a execução concorrente de mais de um
método em um mesmo objeto. Em I+, este tipo de paralelismo possui dois propósitos,
ou seja:
79
garantir a eficiência no atendimento das invocações de métodos;
4
evitar o deadlock entre chamadas mútuas de métodos em diferentes objetos.
4
Em I+ a execução de um método é denominada atividade do objeto. O
relacionamento entre atividades e objeto é análoga ao relacionamento entre processos e
processador em um ambiente multitarefa. Desta forma, um objeto pode ser percebido
como um processador virtual conforme apresentado na figura 5.1. A estrutura mostrada
na figura suporta o escalonamento de múltiplas atividades dentro do objeto.
Interface dos métodos
Implementação dos métodos
Variáveis de estado
Escalonador
Ready_Q
Requisições oriundas
de outros objetos
Request_Q
Waiting_Q
Respostas oriundas
de outros objetos
Avaliador
de métodos
Reply_Q
Respostas para
outros objetos
FIGURA 5.1 – Objeto como processador virtual
A parte estática do objeto contém a interface e a implementação dos métodos. A
parte dinâmica contém os seguintes componentes:
Variáveis de estado: estão presentes somente em objetos em lógica;
4
Escalonador: escalona as atividades do objeto usando uma política roundrobin;
4
Ready_Q: uma fila para armazenamento das atividades que estão prontas para
serem executadas;
4
Waiting_Q: uma fila para armazenamento das atividades que estão esperando
por alguma condição. Uma condição pode ser uma resposta de outro objeto ou
um semáforo;
4
4
Request_Q: uma fila para armazenamento das requisições (invocações de
métodos) oriundas de outros objetos;
80
Reply_Q: uma fila para armazenamento das respostas (resultados das
invocações de métodos) oriundas de outros objetos;
5
Avaliador de métodos: realiza a avaliação de métodos. Existem dois tipos de
avaliadores de métodos, ou seja, uma para métodos em lógica e outro para
métodos funcionais.
5
Normalmente, I+ maximiza o paralelismo intra-objetos pela execução concorrente
de todas as atividades que estão prontas (Ready_Q). No entanto, algumas vezes torna-se
necessária a execução seqüencial, por exemplo, durante o controle da exclusão mútua de
variáveis. Em complemento, I+ suporta dois tipos de objetos, ou seja, objetos passivos e
objetos ativos. Os objetos passivos são o padrão do I+ e somente são ativados quando
um dos seus métodos é invocado. O grau de concorrência pode ser aumentado com o
uso de objetos ativos. Este tipo de objeto executa suas próprias atividades após a
criação. Sendo assim, ele não necessita ser ativado por outro objeto. Em I+ um objeto é
tornado ativo pela inclusão de um método de inicialização com o mesmo nome da classe
que o define.
A implementação de I+ foi realizada em duas fases. Na primeira foi construído
um protótipo para execução em uma rede de estações de trabalho DEC/ULTRIX. Como
ferramentas para construção do protótipo foram utilizadas a linguagem de programação
C, Quintus Prolog e Lazy ML (LML). O protótipo possui dois componentes principais,
ou seja:
Conversor I+/Prolog: converte as definições de classes em lógica para grupos
de módulos em Prolog;
5
5
Conversor I+/LML: converte as definições de classes funcionais para grupos
de módulos LML.
A troca de mensagens é implementada em sockets padrão 4.3 BSD. Em
complemento, utiliza-se o protocolo TCP/IP. Na segunda fase de construção do I+, os
conversores foram rescritos para geração de programas na linguagem C. Essa mudança
foi motivada pela busca de eficiência na execução. Em complemento, foi desenvolvido
um ambiente de programação baseado nos padrões X11R5 e Motif. Este ambiente
executa em estações de trabalho UNIX.
5.2
DLO (Distributed Logic Objects)
A evolução da proposta DLO pode ser percebida em quatro etapas. A figura 5.2
mostra que em cada uma das etapas foi criado um modelo com características próprias.
Inicialmente, Brogi e Ciancarini ([BRO 91]) propuseram a primeira linguagem do
paradigma em lógica baseada na noção de Espaço de Tuplas Lógicas (ETL). Essa
linguagem foi denominada Shared Prolog (SP). Um sistema em Shared Prolog é
composto por um conjunto de tarefas paralelas. Estas tarefas são programas Prolog
estendidos com mecanismos de guarda. O mecanismos de sincronização e comunicação
entre tarefas é baseado no modelo blackboard. Este modelo é estendido com o
mecanismo de unificação clássico do paradigma em lógica. Em [BRO 91, p.100]
destaca-se a descrição de uma nova interpretação para a programação em lógica baseada
no modelo blackboard. Em complemento, em [BRO 91, p.121] os autores afirmam que
estão trabalhando em um modelo que suporte vários blackboards e destacam seu
interesse no estudo de ambientes de programação multiparadigma.
81
Na segunda etapa, Ciancarini ([CIP 94] propõe uma extensão para o Shared
Prolog, denominada ESP (Extended Shared Prolog). ESP suporta Múltiplos Espaços
de Tuplas. Este suporte é baseado em um novo modelo de programação denominado
PoliS, o qual estende Linda com o suporte de múltiplos espaços de tuplas. Destaca-se
em [CIP 94, p.263] uma discussão sobre a paralelização de Prolog tendo como base
ESP. Em complemento, em [CIA 97, p.278] Ciancarini compara ESP com linguagens
paralelas baseadas no paradigma em lógica.
A terceira etapa é apresentada em [AMB 96]. Este artigo propõe um novo modelo
denominado ETA (descrito na seção 4.2.5). Neste escopo, surge a primeira referência
entre união dos paradigma em lógica e orientado a objetos tendo como base a noção de
múltiplos espaços de tuplas. Em complemento, durante a descrição do modelo torna-se
clara a preocupação dos autores quanto a exploração de paralelismo. Em
[AMB 96, p.82], cita-se os modelos Shared Prolog e ESP como bases para criação de
ETA. Salientam os autores que ETA introduz a noção de orientação a objetos nas
propostas apresentadas em [BRO 91] e [CIP 94].
Shared Prolog - 1991
Espaço de Tuplas Lógicas
[BRO 91]
ESP - 1994
Múltiplos Espaços de Tuplas Lógicas
[CIP 94]
ETA - 1996
Múltiplos Espaços de Tuplas Lógicas
+
Orientação a Objetos
[AMB 96]
DLO - 1996
Objetos Lógicos Distribuídos
[CIA 96]
FIGURA 5.2 - Evolução da proposta DLO
Finalmente, na quarta etapa surge o modelo DLO ([CIA 96]). Os princípios deste
modelo estão descritos na seção 4.2.4. No âmbito do modelo DLO são desenvolvidas as
principais atividades relacionadas com a exploração do paralelismo. Em
[CIA 96, p.238] os autores destacam que uma das principais características do DLO é
seu alto grau de paralelismo implícito. DLO suporta a exploração de paralelismo interobjetos e intra-objetos. Em complemento, utiliza-se a técnica de tradução visando a
82
exploração do paralelismo. Esta técnica consiste na aplicação de metodologias de
transformação de programas, as quais preservam sua semântica. Os programas em DLO
são transformados para uma linguagem concorrente de programação em lógica
denominada Rose. Nesta linguagem a comunicação entre processos é baseada em
cláusulas de múltiplas cabeças. Em complemento, durante a exploração do paralelismo
E não podem ser compartilhadas variáveis (paralelismo E independente). Rose é
implementada em uma arquitetura paralela baseada na tecnologia de transputers. A
plataforma de execução possui como base uma extensão da máquina abstrata de Warren
([PER 78], [AIT 91]).
Em [CIA 96, p.244], os autores dedicam atenção especial às formas de
paralelismo suportadas por DLO, ou seja:
paralelismo inter-objetos: instâncias de objetos podem ser executadas em
paralelo. Em DLO, a exploração inter-objetos possui relação com o
paralelismo E suportado pelo paradigma em lógica;
6
paralelismo intra-objetos: Diferentes métodos podem ser executados em
paralelo. Os métodos executados em paralelo não podem alterar o valor de
uma mesma variável. Em DLO, a exploração intra-objetos possui relação com
o paralelismo OU.
6
A figura 5.3 apresenta a implementação de DLO. Conforme mostra a figura, a
implementação pode ser organizada em quatro blocos ([CIA 96, p.246]), ou seja:
Mapeamento DLO/Rose: O mapeamento DLO/Rose permitiu a criação de
um protótipo do modelo DLO em uma arquitetura distribuída. No processo de
tradução destaca-se o tratamento das características da orientação a objetos em
Rose. O processo de tradução mapea nomes de objetos em variáveis lógicas.
Em complemento, a unificação é utilizada como suporte à troca de mensagens.
Um objeto é particionado em um número de metas paralelas em Rose e
tratamento especial é necessário para mantenimento da ligação entre instâncias
de objetos e classes;
6
Máquina Abstrata Paralela: A execução paralela é baseada na Máquina
Abstrata Paralela Rose estendida com suporte ao DLO. Esta máquina é uma
extensão da WAM contendo novas instruções e estruturas de dados com
suporte à unificação de múltiplas cabeças, criação de processos, comunicação
e controle de não-determinismo (operador commit, descrito na seção 3.4.2 no
âmbito do Concurrent Prolog). A execução de um programa Rose é
representada por um grafo de processos E/OU criado dinamicamente. A
execução paralela de metas é mapeada em processos E. Em complemento, a
execução paralela de cláusulas é mapeada em processos OU. Os processos
realizam comunicação e sincronização através da unificação e operações
commit. Um característica interessante de Rose é a presença de múltiplos
átomos na cabeça das cláusulas. Em [CIA 96, p.249-250] é descrita a dinâmica
dos processos E e OU durante a execução de programas;
6
6
Suporte a processos: Imediatamente acima da arquitetura paralela existe uma
camada de software, a qual fornece mecanismos para gerenciamento de
processos e suporte à comunicação. Esta camada introduz um nodo de
gerenciamento para cada nodo de processamento da máquina. Um nodo de
gerenciamento é responsável pela criação dinâmica e escalonamento dos
processos. Em complemento, cuida da criação de processos em nodos remotos;
83
7
Arquitetura paralela: O suporte à execução de programas DLO foi
implementado em uma arquitetura paralela com memória distribuída
denominada Meiko Computing Surface. Este equipamento é baseado na
tecnologia de transputers. Cada nodo da máquina é composto de um
processador transputer baseado nos conceitos RISC, um coprocessador de
ponto-flutuante e uma memória RAM estática. Em complemento, cada nodo
possui a capacidade de comunicar-se com outros nodos através de quatro
ligações de dois caminhos. Um switch programável permite a configuração da
rede de comunicação através de software. Além disso, nos transputers o
processamento e a comunicação ocorrem de forma concorrente. O ambiente de
programação utilizado na Meiko é denominado CSTools. Este ambiente possui
um modelo de programação baseado no CSP, ou seja, processos trocam dados
e sincronismo através de mensagens. O gerenciamento de processos no
CSTools é bastante eficiente, tendo suporte para processos estáticos e
dinâmicos (criados durante a execução). Em complemento, CSTools possui
suporte à abstração completa das conexões de rede de comunicação, ou seja,
processos podem trocar mensagens independentemente da sua posição na
arquitetura paralela.
Programa DLO
Mapeamento DLO/Rose
Máquina Abstrata Paralela
Independente de hardware
Suporte a processos
Dependente de hardware
Arquitetura Paralela
Meiko Computing Surface
FIGURA 5.3 - Implementação de DLO
Merece destaque ainda, as seguintes características da implementação de DLO
apresentadas em [CIA 96, p.250]:
84
Paralelismo e granulosidade: O paralelismo inter-objetos é suportado pela
execução paralela de processos E. Em complemento, processos OU suportam
o paralelismo intra-objetos. Destaca-se ainda que, a definição da granulosidade
a ser utilizada depende das características da arquitetura disponível. Na atual
implementação de DLO, objetos e métodos são mapeados em vários processos
possivelmente alocados em diferentes nodos de processamento. Desta forma,
pode-se obter um alto grau de distribuição e uma baixa granulosidade. No
entanto, uma política de alta granulosidade pode ser adotada em DLO quando
a execução for direcionada para uma rede de estações de trabalho. Neste caso,
uma implementação eficiente pode ser gerada pela combinação de múltiplos
processos (alocados no mesmo processador) em apenas um, substituindo-se a
troca de mensagens locais pelo uso de chamadas de predicados de forma
semelhante à utilizada em Atores;
8
Transparência: Em DLO o programador não percebe o grau de paralelismo
explorado. Objetos DLO são transparentes em relação ao paralelismo e
localidade. Sendo assim, o paralelismo é implícito. No entanto, a execução
seqüencial pode ser induzida através de operadores especiais. Em
complemento, a localização de um objeto não é relevante para o envio de
mensagens. Em particular, a invocação de métodos em objetos locais segue o
mesmo princípio da invocação de métodos em objetos remotos, exceto pela
diferença em desempenho;
8
Replicação: Uma classe contendo código de um objeto pode ser replicada em
vários nodos. Em complemento, em DLO cada método é manipulado por um
processo gerenciador. No caso da replicação de um método, existirão vários
processos gerenciadores, ou seja, um para cada réplica. Cada processo
gerenciador fica desocupado até a chegada de uma requisição;
8
8
5.3
Comunicação: A tradução DLO/Rose mapea os nomes de objetos para
variáveis lógicas. Desta forma, em DLO o tratamento das mensagens é
bastante distinto do tratamento tradicional utilizado em linguagens orientadas
a objetos. Em DLO um objeto não envia uma mensagem para outro. O objeto
origem inclui o identificador do objeto destino na mensagem e a coloca na
estrutura blackboard (conjunto de metas correntes) utilizada no sistema. Em
complemento, o objeto destino busca a mensagem no blackboard através do
mecanismo de unificação. Sendo assim, o mecanismo de comunicação tornase bastante flexível, pois não existe troca explícita de mensagens. A
substituição de constantes por variáveis lógicas na identificação de objetos,
permite a implementação de mecanismos de broadcast. Em [CIA 96, p.252]
encontra-se a afirmação que a perda de desempenho gerada por mecanismos
de broadcast e unificação distribuída pode ser reduzida pelo uso de técnicas de
análise estática baseadas em interpretação abstrata.
Mozart (Distributed Oz)
No ano de 1995 Smolka, Schulte e Van Roy propuseram, através do projeto
Perdio ([SMO 95a]), a criação de uma plataforma de suporte à execução distribuída da
linguagem Oz. Essa plataforma é denominada Mozart ([ROY 99]).
Peter Van Roy et al ([ROY 97, p.805]) afirmam que existem dois objetivos
conflitantes para criação de uma plataforma distribuída, ou seja:
85
Transparência à rede: os programas devem ser executados corretamente
independentemente de como é realizada a distribuição das tarefas na rede;
9
Controle da rede: deve existir um controle simples e previsível sobre os
padrões de comunicação na rede.
9
Os autores destacam que Mozart satisfaz ambos os objetivos através de dois
princípios básicos:
define a linguagem através de duas semânticas: semântica da linguagem
(semântica do Oz 2.0, seção 4.2.7) e semântica de distribuição (regulamenta
a execução distribuída);
9
incorpora a mobilidade ([IEE 98], [LAN 98], [FER 99]) de uma forma
fundamental na semântica distribuída.
9
No âmbito da mobilidade, em Mozart as entidades móveis não deixam rastro, ou
seja, não é necessário suporte ao mapeamento do caminho percorrido pela entidade.
Afirmam os autores de [ROY 97] que Emerald, Obliq e Java com RMI sofrem de
problemas com rastreamento. O Mozart estende a semântica do Oz 2.0 criando uma
semântica distribuída que suporta noções sobre posicionamento na rede. Essa semântica
define as operações que ocorrem na rede quando um programa é distribuído. Sendo
assim, as operações de rede tornam-se previsíveis permitindo ao programador o
gerenciamento da comunicação.
O desenvolvimento de uma aplicação é realizado em duas etapas:
a aplicação é criada sem particionamento explícito e sem preocupações com a
comunicação entre nodos da rede. Nesta fase, a aplicação pode ser testada em
apenas um nodo;
9
a aplicação é distribuída de forma eficiente pelo controle da mobilidade das
entidades. Por exemplo, algumas entidades podem ser colocadas em nodos
específicos e outras podem assumir um comportamento particular para
mobilidade durante a execução.
9
Portanto, a semântica distribuída estende a semântica da linguagem com controle
de mobilidade. Existem quatro requisitos considerados básicos para o projeto de
Mozart, ou seja:
Transparência de rede: O comportamento do programa é o mesmo
independentemente da distribuição na rede. Esse requisito possui como base a
criação de um Espaço Computacional Compartilhado Distribuído
(ECCD). O ECCD cria a ilusão de um único espaço de endereçamento para
todas as entidades do sistema. A distinção entre referências locais e remotas é
imperceptível para o usuário. Por razões de segurança descritas em
[HAR 98, p.253], o ECCD não é apenas uma memória compartilhada
distribuída (DSM). A praticidade de uma proposta de transparência de
distribuição depende de sua habilidade em expressar as técnicas mais
importantes da programação distribuída. Neste sentido, devem ser suportados
múltiplos clientes acessando múltiplos servidores. Em Mozart, a base para
realização dessa tarefa é o suporte à concorrência;
9
9
Previsibilidade de comunicação: As entidades da linguagem suportam
padrões simples de comunicação na rede. Estes padrões permitem a previsão
do comportamento da comunicação durante a execução. A base para
86
implementação desse requisito é que as entidades que possuem estado (por
exemplo, objetos) devem residir em apenas um nodo (denominado nodo
home). O controle da mobilidade é utilizado para troca de nodo home. Por
outro lado, entidades sem estado (por exemplo, procedimentos) podem ser
replicadas em vários nodos. Em Mozart, as entidades podem ser classificadas
em três tipos, ou seja: entidades móveis migram para os nodos que as
invocam, entidades estacionárias exigem uma operação via rede para cada
invocação remota e entidades replicadas são copiadas para cada nodo que as
requisita;
Tolerância à latência: A eficiência da aplicação é afetada ao mínimo pelos
atrasos gerados pela comunicação em rede. Esse requisito é suportado por
quatro mecanismos. A concorrência suporta tolerância à latência entre
processos. Enquanto um processo aguarda comunicação através da rede, os
demais continuam executando. Uma memória cache aumenta a localidade da
computação. A sincronização baseada em fluxo de dados (dataflow)
sincroniza através de dependências de dados e não por comandos de envio
(send) e recebimento (receive). Em Mozart a sincronização é baseada em
variáveis lógicas. Estas variáveis possuem alto poder de expressão e podem ser
facilmente implementadas de forma eficiente. Além disso, são consistentes
com a semântica suportada pelo Oz. Um técnica conhecida como
Comunicação Ordenada Assíncrona generaliza as variáveis lógicas pela
adição de um sistema de buffers (portas em [JAN 93]);
:
Segurança na linguagem: O processamento e os dados são protegidos entre
diferentes usuários que utilizam a plataforma. Neste sentido, o programador
possui meios para restringir o acesso aos dados. Em Mozart as entidades são
representadas por referências ao ECCD. Um programador somente pode
acessar dados para os quais recebeu autorização. Este controle é implementado
através de escopo léxico e procedimentos de primeira ordem. A segurança na
linguagem é discutida em detalhes em [HAR 98, p.253].
:
Mozart possui uma verificação de tipos dinâmica, ou seja, os tipos estruturados
são verificados em tempo de execução. Os programas em Mozart são transformados
para comandos da linguagem de kernel conhecida como OPM (Oz Programming Model
[SMO 95], [ROY 97, p.812]). Em OPM destacam-se dois aspectos, ou seja, o
sincronismo baseado em fluxo de dados (dataflow) controlado por variáveis lógicas e a
unificação de funções de alta ordem com programação orientada a objetos. Em
complemento, Mozart provê duas características adicionais em relação ao OPM (ambas
discutidas em detalhes em [ROY 97, p.816-820]).
suporte sintático para objetos concorrentes baseados em classes com herança
múltipla e ligação dinâmica;
:
suporte a portas, ou seja, canais de comunicação assíncrona ([JAN 93]). Uma
porta suporta vários tipos de comunicação ordenada. Ela é composta de um
procedimento e uma stream (lista baseada em variáveis lógicas).
:
Mozart define uma semântica distribuída para as entidades da linguagem. Cada
operação em cada entidade possui um comportamento na rede. A semântica distribuída
pode ser compreendida através de três comportamentos:
:
Replicação: Todas as entidades sem estado (por exemplo, procedimentos) são
replicadas. Sendo assim, essas entidades nunca se movem. Existe um
87
algoritmo distribuído para gerenciamento da replicação (Protocolo de
Replicação). Este algoritmo estabelece que registros, números e literais são
sempre replicados, ou seja, não existe acesso remoto a estes tipos de entidades.
Por outro lado, procedimentos são replicados de acordo com a necessidade, ou
seja, podem existir chamadas remotas de procedimentos. Um procedimento é
replicado quando é invocado remotamente;
Variáveis lógicas: Uma variável lógica suporta a referência a um valor que
ainda não é conhecido. Existem duas operações básicas que manipulam
variáveis lógicas, ou seja, ligação da variável (atribuição construtiva) e espera
da ligação. A ligação de uma variável lógica faz com que ela seja atualizada
em todos os nodos que a refereciam. Um número arbitrário de entidades pode
estar aguardando a ligação da variável. O protocolo de ligação é denominado
Protocolo de Eliminação de Variáveis. Ele constitui o único algoritmo
distribuído necessário para implementação da unificação distribuída
([HAR 99]). Destaca-se ainda que, variáveis lógicas possibilitam uma forma
eficiente e expressiva para implementação de comunicação em grupo
(multicast). Em [ROY 97, p.821] encontra-se uma discussão sobre essa
característica;
;
;
Controle de mobilidade: Entidades com estado são caracterizadas pelo seu
nodo home. O controle de mobilidade define o que acontece com o nodo home
quando uma operação atua em uma dessas entidades. As entidades podem ser
móveis ou estacionárias. Por exemplo, objetos são móveis. Quando um
método é invocado remotamente, o procedimento que o implementa é
replicado para o nodo invocador. Se o estado do objeto é alterado durante a
execução do método, o objeto desloca-se para o novo nodo home.
Em [ROY 97, p.823] são descritas técnicas para programação de mobilidade em
Mozart. Afirmam os autores que os objetos são móveis por definição. No entanto, a
mobilidade pode ser limitada de forma transparente pela definição de procedimentos.
Tendo como base essas técnicas podem ser criadas três configurações para os objetos:
objetos livremente móveis (objetos são movidos para o nodo que envia uma mensagem
que atualiza o estado do objeto), objetos estacionários (executa os métodos sempre no
mesmo nodo) e objeto preferencialmente estacionário (mantém-se estacionário a menos
que seja explicitamente movido). Os dois últimos são baseados na definição de
procedimentos que controlam a mobilidade do objeto. Esta característica é interessante,
pois permite que o comportamento distribuído de um programa possa ser alterado sem
rescrita dos objetos. Os objetos e suas propriedades de mobilidade são definidos de
forma independente.
A organização básica do Mozart é apresentado na figura 5.4. Conforme mostra a
figura o Mozart é composto de dois módulos, ou seja, o compilador Oz e o ambiente de
execução. O compilador recebe um programa Oz e gera um programa em byte code. Por
sua vez, o byte code é entregue ao ambiente responsável pela execução distribuída do
programa. Cada nodo da rede possui um ambiente Mozart. O usuário usufrui da
distribuição de forma transparente e a execução é baseada no espaço computacional
compartilhado distribuído. Vários usuários podem compartilhar a utilização do ambiente
Mozart. Em [HAR 98, p.253] discutem-se aspectos de segurança relacionados com essa
característica.
88
Usuário 1
Usuário 2
Programa Oz
Programa Oz
Espaço Computacional
Distribuído
Compilador Oz
Compilador Oz
Byte code
Byte code
Ambiente de Execução
Ambiente de Execução
Interface do SO
Interface do SO
Sistema Operacional
Sistema Operacional
Nodo 1
Nodo 2
Interface da rede
Rede de Comunicação
Interface da rede
FIGURA 5.4 - Organização básica do Mozart
A figura 5.5 apresenta uma visão interna do ambiente de execução Mozart.
Conforme mostra a figura, a distribuição é adicionada de forma conservativa à
plataforma centralizada (emulador Oz 2.0). A extensão foi projetada para não afetar o
desempenho do suporte centralizado. Este suporte executa as operações locais. Em
[ROY 97, p.836] encontra-se a afirmação que o emulador Oz possui desempenho
similar ao emulador Java e que as threads do Oz 2.0 são mais rápidas do que as threads
Java.
O ambiente de execução Mozart é composto de três camadas:
Grafo da linguagem: Operações em entidades consideradas distribuídas são
passadas para a camada do grafo da linguagem. Esta camada implementa a
semântica distribuída para todas as entidades do Oz. Ela decide quando fazer
uma operação local ou realizar uma comunicação através da rede. Cada
entidade possui um protocolo. Em essência, existem três protocolos: controle
de mobilidade (gerenciamento da mobilidade de entidades), eliminação de
variáveis (gerenciamento de variáveis lógicas) e replicação (gerenciamento da
replicação de entidades). Estes protocolos criam a ilusão de que todas as
entidades são centralizadas;
<
Gerenciamento de memória: Basicamente possui três tarefas. A primeira é o
suporte ao ECCD. Neste sentido, são utilizados endereços locais e globais
(acesso a nodos remotos). A segunda é a construção e gerenciamento
automático de estruturas de acesso. Estas estruturas são utilizadas quando
entidades são referenciadas remotamente. A terceira é a coleta de lixo
distribuída, a qual é composta de um coletor local e um mecanismo distribuído
para gerenciamento de endereçamento global;
<
<
Suporte a mensagens. Implementa a transferência de sequências de bytes
entre nodos. Essa camada possui contato direto com o sistema operacional e
utiliza conexões TCP visando a transferência confiável entre nodos de uma
WAN. Abaixo dessa camada encontra-se o sistema operacional e a rede de
comunicação.
89
Van Roy et al afirmam em [ROY 97, p.840] que todos os sistemas distribuídos
pesquisados durante o desenvolvimento de Mozart, exceto Emerald e Obliq, suportam a
distribuição pela adição de uma camada acima da linguagem centralizada (CORBA,
DCE, Erlang, Java, Facile e Telescript). Sendo assim, a distribuição não torna-se uma
extensão natural da linguagem. Nestes casos, as operações distribuídas da linguagem
(tais como gerenciamento de objetos móveis e replicação) devem ser manipuladas de
forma explícita pelo programador. Os autores destacam sua preferência pela criação de
um ambiente de programação distribuída através da pesquisa das entidades da
linguagem e extensão do seu comportamento para um universo distribuído. Essa
abordagem exige que a linguagem possua uma semântica operacional que identifique
suas entidades. Tendo como base essa semântica, realiza-se a criação de um algoritmo
distribuído para cada entidade.
Usuário
Byte Code
Emulador Oz 2.0
Operações da Linguagem
Grafo da Linguagem
Acessos à memória compartilhada
Gerenciamento de Memória
Mensagens
Suporte a Mensagens
Rede de Comunicação
FIGURA 5.5 - Ambiente de execução Mozart
No âmbito da pesquisa relacionada com DSM, os autores de [ROY 97] afirmam
que existem duas opções de imple mentação, ou seja:
=
Baseada em páginas: as unidades de distribuição (páginas) não equivalem
diretamente as entidades da linguagem. A granulosidade das unidades é alta.
Essa característica ocasi ona altos índices de falso compartilhamento (false
sharing) e não é compatível com o padrão de aplicações do Mozart;
90
Baseada em bibliotecas: as unidades de distribuição são dados abstratos.
Portanto, pode existir uma equivalência com as entidades da linguagem. Essa
característica permite a diminuição da granulosidade e melhora os índices de
falso compartilhamento. Neste escopo são destacados como exemplos Orca
(compartilhamento de objetos) e Linda (compartilhamento de tuplas).
>
Mozart utiliza DSM baseado em bibliotecas. O ECCD implementa uma camada
DSM, a qual é projetada como suporte para todas as entidades da linguagem Oz. O
ECCD possui características distintas do tratamento tradicional de DSM, tais como,
suporte à atribuição construtiva (variáveis lógicas) e protocolos de compartilhamento
com suporte a dados somente de leitura e migração. Em complemento, o DSM em
Mozart suporta dinamicamente a conexão e a desconexão de nodos.
5.4
Conclusão
Este capítulo dedicou-se ao estudo da exploração do paralelismo em modelos
multiparadigma. Neste escopo foram apresentados três propostas multiparadigma que
exploram paralelismo. Merecem destaque as seguintes considerações:
o I+ explora paralelismo inter-objetos e intra-objetos. No caso intra-objetos,
métodos podem ser executados em paralelo. No entanto, o modelo não explora
o paralelismo implícito existente nos paradigmas declarativos utilizados na
implementação dos métodos. Por exemplo, poderiam ser explorados o
paralelismo OU e o paralelismo E durante a execução de métodos em lógica.
No caso dos métodos funcionais, poderia ser explorado o paralelismo implícito
existente na solução de funções. Surgiria assim, o paralelismo intra-método,
ou seja, a exploração do paralelismo durante a execução de um método;
>
a exploração do paralelismo intra-objeto através da percepção de um objeto
como um processador virtual (figura 5.1) é uma das principais contribuições
da proposta I+;
>
o modelo DLO explora paralelismo intra-objetos e inter-objetos. A exploração
possui como base o paralelismo implícito existente no paradigma em lógica. O
paralelismo inter-objetos está relacionado com o paralelismo OU. Em
complemento, o paralelismo intra-objetos possui relação com o paralelismo E.
Além disso, o modelo DLO é implementado com uma máquina abstrata
direcionada para o paradigma em lógica (versão paralela da WAM);
>
os modelos I+ e DLO são baseados em técnicas de tradução de código. No
âmbito do I+ existiram duas fases baseadas nesta técnica. Na primeira, os
programas eram traduzidos para Quintus Prolog e LML. Na segunda, os
programas são transformados para linguagem C. Por sua vez, DLO possui
como base a tradução de programas para a linguagem Rose;
>
>
os modelos DLO e Mozart são baseados em estruturas de dados
compartilhadas, as quais servem de suporte para exploração do paralelismo. O
DLO utiliza múltiplos espaços de tuplas e Mozart trabalha com um espaço
computacional compartilhado distribuído. No caso de Mozart destaca-se o
suporte à memória compartilhada distribuída.
Em relação ao estudo em profundidade apresentado nos capítulos quatro e cinco
merecem destaque as seguinte considerações:
91
no universo multiparadigma (capítulo 4) existem modelos que dedicam
atenção especial em relação à exploração do paralelismo (capítulo 5);
?
cada paradigma possui características que estimulam a exploração automática
do paralelismo. Nos modelos multiparadigma de unificação parcial é
estimulada a exploração do paralelismo em cada paradigma de forma isolada.
Por exemplo, em I+ é explorado o paralelismo existente na orientação a objetos
(inter-objetos e intra-objeto). No entanto, poderia ser explorado o paralelismo
implícito nos paradigmas em lógica e funcional, os quais estão encapsulados
nos objetos através da implementação dos métodos;
?
nos paradigmas com unificação total a exploração do paralelismo é baseada na
nova semântica criada pelo proposta. Por exemplo, no caso do DLO utiliza-se
os múltiplos espaços de tuplas e no caso do Mozart utiliza-se o espaço
computacional compartilhado distribuído como suporte à mobilidade;
?
alguns modelos multiparadigma são implementados com a utilização de
plataformas já existentes nos paradigmas unificados. Neste caso, em baixo
nível o paralelismo é explorado em apenas um paradigma. Por exemplo, os
programas em DLO são convertidos para linguagem Rose, a qual explora
paralelismo somente no paradigma em lógica. No entanto, alguns modelos são
baseados em plataformas multiparadigma. Este é o caso do modelo Mozart, o
qual suporta o paralelismo diretamente na plataforma de execução da
linguagem multiparadigma Oz;
?
?
Mozart propõe a utilização de duas semânticas distintas para tratamento da
linguagem e da distribuição. Desta forma, ficam isoladas as questões da
linguagem em relação as questões do paralelismo. Essa abordagem facilita a
criação de software multiparadigma paralelo e distribuído.
O próximo capítulo apresenta a conclusão do trabalho.
92
6 Conclusão
Este texto dedicou-se ao software multiparadigma paralelo e distribuído. Neste
escopo foi realizado um estudo em abrangência sobre software paralelo e distribuído e
um estudo em profundidade relacionado com a exploração de paralelismo em modelos
multiparadigma. Destacaram-se no texto quatorze estudos de caso organizados da
seguinte forma:
quatro casos de paralelismo nos paradigmas básicos: Convencional (SR),
Lógica (Concurrent Prolog), Funcional (GPH) e orientado a objetos (DPC++);
@
sete modelos multiparadigma: OLI, OWB, I+, DLO, ETA, G, Oz;
@
três casos de paralelismo nos modelos multiparadigma: I+, DLO e Mozart (Oz
distribuído).
@
No decorrer do texto foram apresentadas conclusões ao final de cada capítulo.
Essa metodologia aumentou a coesão dos demais capítulos e diminui a complexidade
deste. Além disso, as conclusões ficaram contextualizadas, ou seja, cada conclusão está
localizada no escopo onde foi obtida. Destaca-se ainda que, a conclusão do terceiro
capítulo pode ser considerada a conclusão do estudo em abrangência. Da mesma forma,
a conclusão do quinto capítulo abrange a conclusão do estudo em profundidade.
Merecem destaque as seguintes considerações, as quais resumem a motivação e os
resultados alcançados neste texto:
os paradigmas não convencionais possuem fontes de concorrência que
estimulam a exploração automática do paralelismo;
@
as arquiteturas paralelas e distribuídas estão sendo cada vez mais utilizadas;
@
existem diversos trabalhos relacionados com a exploração do paralelismo em
paradigmas de desenvolvimento, especialmente, nos paradigmas não
convencionais;
@
a integração de paradigmas (multiparadigma) vem sendo considerada uma
solução para aperfeiçoamento das técnicas de desenvolvimento de software;
@
o estudo da exploração do paralelismo e distribuição em modelos
multiparadigma surge como uma oportunidade para comunhão de dois
objetivos atuais, ou seja, aperfeiçoamento das ferramentas de desenvolvimento
de software e simplificação do uso de sistemas paralelos e distribuídos.
@
Trabalhos futuros poderão aprimorar os estudos apresentados neste texto. Neste
sentido, podem ser destacadas as seguintes tarefas:
aprimoramento da classificação de definições apresentada na figura 2.2
(concorrência, paralelismo e distribuição). Neste escopo, pode-se testar a
classificação através de sua aplicação em um grupo de modelos e linguagens
paralelas e distribuídas;
@
aprimoramento da definição de arquitetura distribuída discutida na seção
2.3. Neste sentido, merece atenção especial a criação de um formalismo para
representação da organização descrita durante a seção;
@
@
avaliação da proposta de taxonomia para arquitetura de sistemas
computacionais apresentada na figura 2.5. A proposta pode ser avaliada
93
através de um estudo envolvendo diferentes tipos de arquiteturas de
computadores, em especial, com múltiplos processadores;
aperfeiçoamento da taxonomia multiparadigma descrita na seção 4.3. A
tabela 4.1 pode ser expandida através da classificação de outros modelos
multiparadigma. De forma complementar, a taxonomia deve ser aperfeiçoada
visando uma classificação mais precisa. Os índices utilizados (amplitude do
modelo e qualidade de unificação) são superficiais e contêm pouca informação
sobre questões relevantes do universo multiparadigma, tais como, técnicas
utilizadas para unificação e objetivos almejados com a criação do modelo;
A
A
aprofundamento do estudo sobre paralelismo nos modelos multiparadigma
apresentado no capítulo cinco. Neste escopo, podem ser pesquisados outros
modelos e criada uma taxonomia para organização das técnicas de exploração
do paralelismo em modelos multiparadigma. Neste sentido, pode ser realizada
uma expansão da taxonomia apresentada na seção 4.3 visando a abrangência
da exploração do paralelismo e distribuição.
Finalmente, pode ser destacada a relação deste trabalho com tendências científicas
surgidas durante o século XX. Albert Einstein no discurso pronunciado por ocasião do
sexagésimo aniversário de Max Planck analisa os princípios da pesquisa. Naquela
abordagem ele salienta que, no âmbito da física, a extrema nitidez, a clareza e a certeza
só se adquirem à custa de um imenso sacrifício, ou seja, a perda da visão de conjunto da
realidade ([EIN 81, p.139]). Por sua vez, Ortega y Gasset ([ORT 92, p.72]), analisando
o mesmo tema, salienta que todo esforço criador é uma especialização. No entanto,
salienta ainda a necessidade da criação de sínteses do conhecimento. Destaca-se naquele
texto a afirmação de que o movimento que leva a investigação a dissociar-se
indefinidamente em problemas particulares exige uma regulagem compensatória. Essa
regulagem deve ser realizada através de um movimento de direção inversa que contraía
e retenha a tendência centrífuga da ciência. Além disso, David Bohm afirma em
[BOH 80, p.12] que a ciência carece de uma visão de mundo não fragmentária. Afirma
Bohm, que a abordagem que analisa o mundo em partes independentes não funciona
bem na física moderna. Ele salienta que tanto na teoria da relatividade como na teoria
quântica, noções que impliquem a totalidade indivisa de universo proporcionam um
modo mais ordenado de considerar a natureza da realidade. Durante o primeiro capítulo
do seu livro A Totalidade e a Ordem Implicada ([BOH 80]), David Bohm compara a
fragmentação e a totalidade do ponto de vista de paradigmas para percepção do
universo.
No âmbito da ciência da computação a fragmentação/especialização vem sendo
bastante utilizada para a solução de problemas. O desenvolvimento de sistemas
computacionais destaca a fragmentação como instrumento de domínio da complexidade.
A máxima "dividir para conquistar" atua como um arquétipo para a Engenharia de
Software ([MAR 91, p.75]). A fragmentação/especialização vem estimulando a criação
de diversos paradigmas de desenvolvimento de software e, em especial, a criação de
uma quantidade enorme de linguagens de programação. A diversidade gerada pela
proliferação de paradigmas e linguagens é simbolizada pela torre de babel. Esse
símbolo pode ser encontrado na capa de todas as revistas Computer Languages e, em
especial, no título de [FRI 92].
94
O estudo apresentado neste trabalho envolve duas sínteses cumulativas no âmbito
da ciência da computação, ou seja:
os modelos multiparadigma dedicam-se à síntese do conhecimento no
âmbito dos paradigmas de desenvolvimento. Um modelo multiparadigma é
baseado na unificação de paradigmas;
B
B
o software multiparadigma paralelo e distribuído envolve a integração da
pesquisa multiparadigma com os estudos relacionados com o desenvolvimento
de software paralelo e distribuído.
Portanto, as pesquisas relacionadas com software multiparadigma paralelo e
distribuído seguem uma tendência científica orientada para a síntese e organização do
conhecimento.
95
Bibliografia
[ACM 89]
ACM Computing Surveys. New York, v.21, n.3, September 1989.
510p. Special Issue on Parallel Processing and Software’s
Paradigm.
[AIT 91]
AÏT-KACI, Hassan. Warren's Abstract Machine - A Tutorial
Reconstruction. Cambridge: MIT Press, 1991. 114p.
[AMA 96]
AMANDI, Analía; PRICE, Ana. A Linguagem OWB: Combinando
Objetos e Lógica. In: SIMPÓSIO BRASILEIRO DE
LINGUAGENS DE PROGRAMAÇÃO, 1., 1996, Belo Horizonte.
Anais... Belo Horizonte: SBC, 1996. 404p. p.305-318.
[AMA 97]
AMANDI, Analía A. Programação de Agentes Orientada a
Objetos. Porto Alegre: CPGCC da UFRGS, 1997. 208p. Tese de
Doutorado.
[AMB 96]
AMBRIOLA, Vincenzo; CIGNONI, Giovanni A.; SEMINI; Laura. A
Proposal to Merge Multiple Tuple Spaces, Object Orientation and
Logic Programming. Computer Languages, Elmsford, v.22, n.2/3,
p.79-93, July/October 1996.
[AMZ 97]
AMZA,
Cristiana;
COX,
Alan;
RAJAMANI,
Karthick;
ZWAENEPOEL, Willy. Tradeoffs Between False Sharing and
Aggregation in Software Distributed Shared Memory. ACM
SIGPLAN Notices, New York, v.32, n.7, p.90-99, July 1997.
[AND 81]
ANDREWS, Gregory. Synchronizing resources. ACM Transactions
on Programming Languages and Systems, New York, v.3, n.4,
p.405-430, October 1981.
[AND 82]
ANDREWS, Gregory. The distributed programming language SR Mechanisms, design and implementation. Software-Practice and
Experience, v.12, n.8, p.719-753, August 1982.
[AND 83]
ANDREWS, Gregory R. Concepts and Notations for Concurrent
Programming. ACM Computing Surveys, New York, v.15, n.1,
p.3-43, March 1983.
[AND 86]
ANDREWS, Gregory.; OLSSON, Ronald. The evolution of the SR
language. Distributed Computing, v.1, n.3, p.133-149, July 1986.
[AND 88]
ANDREWS, Gregory; OLSSON, Ronald; COFFIN, Michael;
ELSHOFF, Irving; NILSEN, Kelvin; PURDIN, Titus; TWNSEND,
Gregg. An Overview of the SR language and Implementation.
ACM Transactions on Programming Languages and Systems,
New York, v.10, n.1, p.51-86, January 1988.
[AND 91]
ANDREWS, Gregory R. Paradigms for Process Interaction in
Distributed Programs. ACM Computing Surveys, New York,
v.23, n.1, p.49-90, March 1991.
[AND 92]
ANDREWS, Gregory R.; OLSSON, Ronald A. The SR
Programming Language. New York: The Benjamin/Cummings
Publishing Company, 1992. 344p.
96
[AUG 92]
AUGUSTIN, Iara. Paralelismo em Linguagens Orientadas a
Objetos. Porto Alegre: CPGCC-UFRGS, 1992. 86p. (TI-298).
[AUG 94]
AUGUSTIN, Iara. pEiffel: uma biblioteca de classes para
paralelismo em Eiffel. Porto Alegre: CPGCC da UFRGS, 1994.
202p. Dissertação de Mestrado.
[BAC 78]
BACKUS, John. Can Programming Be Liberated from the Von
Neumann Style? A Functional Style and Its Algebra of Programs.
Communications of the ACM, New York, v.21, n.8, p.613-641,
August 1978.
[BAL 89]
BAL, Henri E.; STEINER, Jennifer G.; TANENBAUM, Andrew S.
Programming Languages for Distributed Computing Systems.
ACM Computing Surveys, New York, v.21, n.3, p.261-322,
September 1989.
[BAR 93]
BARBOSA, Jorge L. V. Construção de Compiladores para
Máquinas de Processamento Paralelo. Pelotas: UCPel, 1993.
73p. Monografia de Especialização.
[BAR 94]
BARBOSA, Jorge L. V. Análise da Granulosidade de Tarefas para
Processamento Paralelo. Porto Alegre: CPGCC-UFRGS, 1994.
93p. (TI-376).
[BAR 96]
BARBOSA, Jorge L. V. GRANLOG: Um Modelo para Análise
Automática de Granulosidade na Programação em Lógic. Porto
Alegre: CPGCC da UFRGS, 1996. 167p. Dissertação de Mestrado.
[BAR 98]
BARBOSA, Jorge L. V. Paradigmas de Desenvolvimento de
Sistemas Computacionais. Porto Alegre: CPGCC da UFRGS,
1998. 49p. (TI-731).
[BAR 98a]
BARBOSA, Jorge L. V.; GEYER, Cláudio F R. Taxonomia
Multiparadigma. In: CONGRESO ARGENTINO DE CIENCIAS
DE LA COMPUTACIÓN, 4., 1998, Neuquén. Proceedings...
Neuquén: Universidad Nacional del Comahue, octubre 1998.
1162p. (poster, p.1162).
[BAR 99]
BARBOSA, Jorge L. V. Princípios do Holoparadigma. Porto
Alegre: CPGCC da UFRGS, 1999. 75p. (TI-748).
[BLU 94]
BLUME, William et al. Automatic Detection of Parallelism – A
Grand Challenge for High-Performance Computing. IEEE Parallel
and Distributed Technology: Systems and Applications, New
York, v.2, n.3, p.37-47, Fall 1994.
[BOH 80]
BOHM, David. A Totalidade e a Ordem Implicada - Uma Nova
Percepção da Realidade. São Paulo: Cultrix, 1980. 292p.
[BRI 96]
BRIOT, Jean-Pierre; GUERRAOUI, Rachid. A Classification of
Various Approaches for Object-Based Parallel and Distributed
Programming. Disponível por WWW em http://lsewww.epfl.ch/
~rachid/papers/surv96.ps (julho de 1999).
97
[BRI 98]
BRIOT, Jean-Pierre; GUERRAOUI, Rachid; LÖHR, Klaus-Peter.
Concurrency and Distribution in Object-Oriented Programming.
ACM Computing Surveys, New York, v.30, n.3, p.291-329,
September 1998.
[BRJ 91]
BRIAT, J.; FAVRE, M.; GEYER, C; CHASSIN de Kergommeaux.
Scheduling of OR-parallel Prolog on a scalable reconfigurable
distributed memory multiprocessor. In: PARLE’91 - Parallel
Architectures and Languages Europe, 1991. Proceedings... Berlin:
Springer-Verlang, 1991. p.385-402. (Lecture Notes in Computer
Science, v. 506).
[BRO 91]
BROGI, Antônio; CIANCARINI, Paolo. The Concurrent Language,
Shared Prolog. ACM Transactions on Programming Languages
and Systems, New York, v.13, n.1, p.99-123, January 1991.
[BRU 97]
BRUCK, Jehoshua et al. Efficient Message Passing Interface (MPI)
for Parallel Computing on Clusters of Workstations. Journal of
Parallel and Distributed Computing, New York, v.40, n.1, p.1934, January 1997.
[BUG 94]
BUGLIESI, Michele; LAMMA Evelina; MELLO, Paola. Modularity
in Logic Programming. Journal of Logic Programming, New
York, v.19/20, p.443-502, May/July 1994.
[BYT 95]
A Brief History of Programming Languages. Byte, p.121-122,
September 1995.
[CAB 97]
CABILLIC, Gilbert; PUAUT, Isabelle. Stardust: An Environment for
Parallel Programming on Networks of Heterogeneous
Workstations. Journal of Parallel and Distributed Computing,
New York, v.40, n.1, p.65-80, January 1997.
[CAS 86]
CASANOVA, M.A.; GIORNO, F.A.C.; FURTADO, A.L.
Programação em Lógica. Belo Horizonte: UFMG, 1986. 295p.
Escola de Computação, 5., 1986, Belo Horizonte.
[CAV 92]
CAVALHEIRO, Gerson G. H. Implementação de Concorrência em
C++. Porto Alegre: CPGCC-UFRGS, 1992. 76p. (TI-251).
[CAV 94]
CAVALHEIRO, Gerson G. H. Um Modelo para Linguagens
Orientadas a Objetos Distribuídos. Porto Alegre: CPGCC da
UFRGS, 1994. 145p. Dissertação de Mestrado.
[CHA 97]
CHAKRAVARTY, Manuel M. T.; LOCK, Hendrik C. R. Towards the
Uniform Implementation of Declarative Languages. Computer
Languages, Elmsford, v.23, n.2-4, p.121-160, July-December
1997.
[CHI 91]
CHIN, Roger S.; CHANSON, Samuel T. Distributed Object-Based
Programming Systems. ACM Computing Surveys, New York,
v.23, n.1, p.91-124, March 1991.
[CHU 41]
CHURCH, A. The Calculi of Lambda Conversion. In: ANNALS OF
MATHEMATICS STUDIES, 1941. Proceedings... Princeton:
Princeton University Press, 1941.
98
[CIA 96]
CIAMPOLINI, A.; LAMMA, E.; STEFANELLI, C; MELLO, P.
Distributed Logic Objects. Computer Languages, Elmsford, v.22,
n.4, p.237-258, December 1996.
[CIP 92]
CIANCARINI, Paolo. Parallel Programming with Logic Languages:
A Survey. Computer Languages, Elmsford, v.17, n.4, p.213-239,
October 1992.
[CIP 94]
CIANCARINI, Paolo. Distributed Programming with Logic Tuple
Spaces. New Generating Computing, Berlin, v.12, n.3, p.251-283,
1994.
[COM 86]
Computer. New York, v.19, n.8, August 1986. Special Issue on
Parallel Processing and Software’s Paradigm.
[COM 91]
Communications of the ACM. LISP – Adapting to the environment.
New York, v.34, n.9, September 1991. Special Issue on LISP.
[COM 94]
Communications of the ACM. Intellingent Agents. New York, v.37,
n.7, July 1994. 170p. Special Issue on Agents.
[DAV 93]
DAVISON, Andrew. A Survey of Logic Programming-Based ObjectOriented. In: AGHA, G.; WEGNER, P.; YONEZAWA, A. (eds.).
Research
Direction
in
Concurrent
Object-Oriented
Programming. Cambridge: Mit Press, 1993. p.42-106
[DEB 93]
DEBRAY, S. K.; LIN, N. Cost Analysis of Logic Programs. ACM
Transactions on Programming Languages and Systems, New
York, v.15, n.5, p.826-875, November 1993.
[EIN 81]
ENSTEIN, Albert. Como Vejo o Mundo. Rio de Janeiro: Nova
Fronteira, 1981. 213p.
[FER 99]
FERRARI, Débora N. Um Estudo sobre Mobilidade em Sistemas
Distribuídos. Porto Alegre: CPGCC-UFRGS, 1999. 50p. (TI-780).
[FIN 96]
FINKEL, Raphael A. Advanced Programming Language Design.
New York: Addison & Wesley, 1996. 480p.
[FRI 92]
FRIEDMAN, Linda W. From Babbage to Babel and Beyond: A Brief
History of Programming Languages. Computer Languages,
Elmsford, v.17, n.1, p. 1-17, 1992.
[GUP 93]
GUPTA, G.; JAYARAMAN, B. AND-OR Parallelism on SharedMemory Multiprocessors. Journal of Logic Programming, New
York, v.17, n.1, p.59-89, October 1993.
[GHE 98]
GHEZZI, Carlo; JAZAYERI, Mehdi. Programming Language
Concepts. New York: John Wiley & Sons, 1998. 427p.
[HAI 86]
HAILPERN, Brent. Multiparadigm Research: A Survey of Nine
Projects. IEEE Software, New York, v.3, n.1, p. 70-77, January
1986.
[HAM 94]
HAMMOND, Kevin. Parallel Functional Programming: Na
Introduction. In: International Symposium on Parallel Symbolic
Computation (PASCO), 1., 1994, Linz, Austria. Proceedings...
New Jersey: World Scientific Publishing Company, 1994. p.181193
99
[HAN 94]
HANUS, Michael. The Integration of Functions into Logic
Programming from Theory to Practice. Journal of Logic
Programming, New York, v.19/20, p.583-628, May/July 1994.
[HAN 97]
HANUS, Michael. Lazy Narrowing with Simplification. Computer
Languages, Elmsford, v.23, n.2-4, p.61-85, July-December 1997.
[HAR 98]
HARIDI, Seif et al. Programming Languages for Distributed
Applications. New Generating Computing, Berlin, v.16, n.3,
p.223-261, 1998.
[HAR 99]
HARIDI, Seif et al. Efficient Logic Variables for Distributed
Computing. Disponível por WWW em http://www.mozartoz.org/papers/abstracts/TOPLAS99.html (julho de 1999).
[HAR 99a]
HARIDI, Seif; FRANZÉN, Nils. Tutorial of Oz. Disponível por
WWW em http://mozart-oz.org/documentation/tutorial/index.html
(julho de 1999).
[HEN 97]
HENZ, Martin. Objects in Oz. Saarbrüchen: Universität des
Saarlandes, may 1997. 199p. PhD Thesis.
[HER 86]
HERMENEGILDO, M. An Abstract Machine Based Execution
Model for Computer Architecture Design and Efficient
Implementation on Logic Programs in Parallel. Austin:
University of Texas, August 1986. 244p. PhD Thesis.
[HES 97]
HESSEL, Roberta J. Exploração de Paralelismo Implícito no
Modelo de Objetos. Porto Alegre: CPGCC da UFRGS, 1997. 86p.
Dissertação de Mestrado.
[IEE 94]
IEEE Parallel & Distributed Technology – Systems & Applications.
New York, v.2, n.3, Fall 1994. Special Issue on High Performance
Fortran.
[IEE 86]
IEEE Software. New York, January 1986. Special Issue on
Multiparadigm Languagens and Environments.
[IEE 98]
IEEE Transactions on Software Engineering. New York, v.24, n.5,
May 1998. Special Issue on Mobility and Network-Aware
Computing.
[JAN 93]
JANSON, Sverker; MONTELIUS, Johan; HARIDI, Seif. Ports for
Objects in Concurrent Logic Programs. In: AGHA, G.; WEGNER,
P.; YONEZAWA, A. (eds.). Research Direction in Concurrent
Object-Oriented Programming. Cambridge: Mit Press, 1993.
p.211-231
[JAN 93a]
JANSON, Sverker; HARIDI, Seif. An Introduction to AKL: A
Multi-Paradigm Programming Language. Disponível por
WWW em http://www.sics.se/~seif/pubs1.html (julho de 1999).
[JON 93]
JONES, Mark P.; HUDAK, Paul. Implicit and Explicit Parallel
Programming in Haskell. Disponível por FTP em
nebula.systemsz.cs.yale.edu/pub/yale-fp/reports/RR-982.ps.Z
(julho de 1999).
100
[JOU 97]
Journal of Parallel and Distributed Computing. New York, v.40, n.1,
January 1997. 146p. Special Issue on Workstation Clusters and
Network-Based Computing.
[JUN 95]
JUNGBLUT, Roberta. Estudo sobre Concorrência e Paralelismo
em Linguagens Orientadas a Objeto. Porto Alegre: CPGCCUFRGS, 1995. 41p. (TI-455).
[KAR 88]
KARP, A. H.; BABB II, R. G. A Comparison of 12 Parallel Fortran
Dialects. IEEE Software, New York, v.5, n.5, p.52-67, September
1988.
[KAS 83]
KASIF, S.; KOHLI, M.; MINKER, J. PRISM: a Parallel Inference
System for Prolog Solving. Lisboa: Universidade de Nova Lisboa,
1983. 23p. (Relatório Técnico).
[KER 94]
KERGOMMEAUX, Jacques Chassin; CODOGNET, Philippe.
Parallel Logic Programming Systems. ACM Computing Surveys,
New York, v.26, n.3, p.295-336, September 1994.
[KOW 74]
KOWALSKI, R. A. Predicate Logic as a Programming Language. In:
IFIP WORLD CONGRESS, 1974. Proceedings... [s.l.]:NorthHolland, 1974. p.589-674
[KOW 79]
KOWALSKI, Robert. Logic for Problem Solving. New York:
Elsevier, 1979.
[KOW 79a]
KOWALSKI, Robert. Algorithms = Logic + Control.
Communications of the ACM, New York, v.22, n.7, p.424-436
July 1979.
[KON 97]
KONURU, Ravi B.; OTTO, Steve W.; WALPOLE, Jonathan. A
migratable User-Level Process Package for PVM. Journal of
Parallel and Distributed Computing, New York, v.40, n.1, p.81102, January 1997.
[KUH 70]
KUHN, Thomas S. A Estrutura das Revoluções Científicas. São
Paulo: Perspectiva, 1970. 257p.
[KUH 77]
KUHN, Thomas S. Reconsiderações Acerca dos Paradigmas. In:
KUHN, T. (ed.). A Tensão Essencial. Lisboa: Edições 70, 1977.
p.353-382
[KRU 88]
KRUATRACHUE, B.; LEWIS, T. Grain Size Determination for
Parallel Processing. IEEE Software, New York, v.5, n.1 p.23-32,
January 1988.
[LAN 98]
LANGE, Danny B. Mobile Objects and Mobile Agents: The Future of
Distributed Computing? In: JUL, Eric (ed.). ECOOP’98 ObjectOriented Programming. Berlin: Springer-Verlang, 1998. p.1-12.
[LAR 90]
LARANJEIRA, Luiz A. Software Size Estimation of Object-Oriented
Systems. IEEE Transactions on Software Engineering. New
York, v.16, n.5, p.510-522, May 1990.
101
[LEE 97]
LEE, J. H. M.; PUN, P. K. C. Object Logic Integration: A
Multiparadigm Design Methodology and a Programming
Language. Computer Languages, Elmsford, v.23, n.1, p.25-42,
april 1997.
[LIK 89]
LI, Kai; HUDAK, Paul. Memory Coherence in Shared Virtual
Memory Systems. ACM Transactions on Computer Systems,
New York, v.7, n.4, p.321-359, November 1989.
[LIN 93]
LIN, N. Automatic Complexity Analysis of Logic Programs.
Tucson: University of Arizona, 1993. 244p. Ph.D. Thesis.
[MAR 91]
MARTIN, James; MCCLURE, Carma. Técnicas Estruturadas e
Case. São Paulo: McGraw-Hill, 1991. 854p.
[MCC 89]
MCCREARY, C.; GILL, H. Automatic Determination of Grain Size
for Efficient Parallel Processing. Communications of the ACM,
New York, v.32, n.9, p.1073-1078, September 1989.
[MCJ 65]
MCCARTHY, J. et al. LISP 1.5 Programmer's Manual. Cambridge:
MIT Press, 1965.
[MUL 95]
MULLER, Martin; MULLER, Tobias; ROY, Peter V. Multiparadigm
Programming in Oz. In: SMITH, Donald; RIDOUX, Olivier; ROY,
Peter V. (eds.). Visions for the Future of Logic Programming:
Laying the Foundations for a Modern Sucessor of Prolog.
Portland, Oregon, December 1995.
[NGK 95]
NG, K. W.; LUK, C. K. I+: A Multiparadigm Language for ObjectOriented Declarative Programming. Computer Languages,
Elmsford, v.21, n.2, p. 81-100, July 1995.
[OMI 94]
OMICINI, Andrea; NATALI, Antonio. Object-Oriented Computations
in Logic Programming. In: EUROPEAN CONFERENCE ON
OBJECT-ORIENTED PROGRAMMING, 8., 1994, Bologna, Italy.
Proceedings... Berlin: Springer-Verlag, 1994. p.194-212. (Lecture
Notes in Computer Science, v.821).
[ORT 92]
ORTEGA y GASSEY, José. Mision de la Universidad. Madri:
Alianza Editorial, 1992. 238p.
[PAD 86]
PADUA, D. A.; WOLFE, M. J. Advanced Compiler Optimizations for
Supercomputers. Communications of the ACM, New York, v.29,
n.12, p.1184-1201, December 1986.
[PAN 91]
PANCAKE, C. M. Where are we headed? Communications of the
ACM, New York, v.34, n.11, p.53-64, November 1991.
[PER 78]
PEREIRA, L. M.; PEREIRA, F. C. N.; WARREN, D. H. D. User's
Guide to DECsystem-10 Prolog. Edinburgh: University of
Edinburgh- Departament of Artificial Intelligence. 1978. 197p.
[PLA 91]
PLACER, John. The Multiparadigm Language G. Computer
Languages, Elmsford, v.16, n.3/4, p.235-258, 1991.
102
[POR 97]
PORTO, Paulo Ricardo P.; PALAZZO, Luiz Antônio M.;
CASTILHO, José Mauro V. Agentes de Informação Inteligentes.
In: OFICINA DE INTELIGÊNCIA ARTIFICIAL, 1., 1997,
Pelotas. Anais... Pelotas: Educat, 1997. 107p. p.81-107.
[POR 98]
PORTO, Paulo Ricardo P. Engenharia de Software Baseada em
Agentes. In: OFICINA DE INTELIGÊNCIA ARTIFICIAL, 2.,
1998, Pelotas. Anais... Pelotas: Educat, 1998. 132p. p.95-109.
[PRA 96]
PRATT, Terrence W.; ZELKOWITZ, Marvin V. Programming
Languages Design and Implementation. New Jersey: Simon &
Schuster, 1996. 654p.
[PRO 96]
PROTIC, Jelica; TOMASEVIC, Milo; MILUTINOVIC, Veljko.
Distributed Shared Memory: Concepts and Systems. IEEE
Parallel and Distributed Technology: Systems and
Applications. New York, v.4, n.2, p.63-79, Summer 1996.
[REN 82]
RENTSCH, Tim. Object-Oriented Programming. Sigplan Notices,
v.17, n.9, p.51-57, September 1982.
[ROB 92]
ROBINSON, J. A. Logic and Logic Programming. Communications
of the ACM, New York, v.35, n.3, p.40-65, March 1992.
[ROG 94]
ROGERS, Anne; PINGALI, Keshav. Compiling for Distributed
Memory Architectures. IEEE Transactionson Parallel and
Distributed Systems. New York, v.5, n.3, p.281-298, March 1994.
[ROU 75]
ROUSSEL, P. Prolog: Manuel de Reference et d'Utilisation. [s.l.]:
Univ. d'Aix-Marseille, Groupe de IA, 1975. (Technical report).
[ROY 94]
ROY, Peter V. 1983- 1993: The Wonders Years of Seqüential Prolog
Implementation. Journal of Logic Programming, New York,
v.19/20, p.385-441, May/July 1994.
[ROY 97]
ROY, Peter V. et al. Mobile Objects in Distributed Oz. ACM
Transactions on Programming Languages and Systems, New
York, v.19, n.5, p.804-851, September 1997.
[ROY 99]
ROY, Peter V.; HARIDI, Seif; BRAND, Per Distributed
Programming in Mozart – A Tutorial Introduction. Disponível
por WWW em http://mozart-oz.org/documentation/dstutorial/
index.html (julho de 1999).
[RUM 94]
RUMBAUGH, James; et al. Modelagem e Projetos Baseados em
Objetos. Rio de Janeiro: Campus, 1994. 652p.
[SEB 96]
SEBESTA, Robert W. Concepts of Programming Languages. New
York: Addison & Wesley, 1996. 634p.
[SEL 97]
SELLERS, B. Henderson. Corrigenda: Software Size Estimation of
Object-Oriented Systems. IEEE Transactions on Software
Engineering, New York, v.23, n.4, p.260-261, April 1997.
[SHA 86]
SHAPIRO, E. Concurrent Prolog: A Progress Report. Computer,
New York, v.19, n.8, p.44-58, August 1986.
103
[SHA 89]
SHAPIRO, E. The Family of Concurrent Logic Programming
Languages. ACM Computing Surveys, New York, v.21, n.3,
p.413-510, September 1989.
[SHM 95]
SHAW, M. et al. Abstractions for Software Architecture and Tools to
Support Them. IEEE Transactions on Software Engineering,
New York, v.21, n.4, p.314-335, April 1995.
[SHO 93]
SHOHAM, Y. Agent-oriented programming. Artificial Intelligence,
Amsterdam, v.60, n.1, p.51-92, March 1993.
[SHO 94]
SHOHAM, Y.; COUSINS, S. Logics of Mental Attitudes in AI. In:
LAKEMEYER, G.; NEBEL, B. (Eds.). Foundations of
Knowledge Representation and Reasoning. Berlin: SpringerVerlang, 1994. p.296-309. (LNAI, v.810).
[SHS 89]
SHATZ, Sol M.; WANG Jia-Ping. Tutorial: Distributed-Software
Engineering. New York: IEEE Computer Society Press, 1989.
279p.
[SKI 98]
SKILLICORN, David B.; TALIA, Domenico. Models and Languages
for Parallel Computation. ACM Computing Surveys, New York,
v.30, n.2, p.123-169, June 1998.
[SMO 95]
SMOLKA, Gert. The Oz Programming Model. In: COMPUTER
SCIENCE TODAY, 1995. Proceedings... Berlin: Springer-Verlag,
1995. p. 324-343. (Lecture Notes in Computer Science, v.1000).
[SMO 95a]
SMOLKA, Gert; SCHULTE, Christian; VAN ROY, Peter. PERDIO
– Persistent and Distributed Programming in Oz. 1995.
Disponível por WWW em http://www.sics.se./~seif (julho de
1999).
[STE 86]
STERLING, L.; SHAPIRO, E. The Art of Prolog. Cambridge: MIT
Press, 1986. 437p.
[TAN 95]
TANENBAUM, Andrew S. Distributed Operating Systems. New
Jersey: Prentice-Hall, 1995. 613p.
[THO 96]
THOMPSON, Simon. Haskell: The Craft of Functional
Programming. New York: Addison & Wesley, 1996. 500p.
[TRI 93]
TRINDER, P. W.; HAMMOND, K.; LOIDL H. W.; JONES, S. L. P.
Algorithm + Strategy = Parallelism. Journal of Functional
Programming, v.8, n.1, January 1993.
[TRI 96]
TRINDER, P. W.; HAMMOND, K.; MATTSON, J. S.;
PARTRIDGE, A. S.; JONES, S. L. P. GUM: A Portable Parallel
Implementation of Haskell. ACM SIGPLAN Notices, New York,
v.31, n.5, p.79-88, May 1996.
[TZE 93]
TZEN, Tem H.; NI, Lionel M. Dependence Uniformization: A Loop
Parallelization Technique. IEEE Transactions on Parallel and
Distributed Systems, New York, v.4, n.5, p.547-558, May 1993.
[VLA 92]
VLAHAVAS, I; KEFALAS, P. A Parallel Prolog Resolution Based
on Multiple Unifications. Parallel Computing, New York, v.18,
n.11, p.1275-1283, November 1992.
104
[VRA 95]
VRANES, Sanja; STANOJEVIC, Mladen. Integrating Multiple
Paradigms within the Blackboard Framework. IEEE Transactions
on Software Engineering, New York, v.21, n.3, p.244-262, March
1995.
[WIA 92]
WYATT, Barbara B.; KAVI, Krishna; HUFNAGEL, Steve.
Parallelism in Object-Oriented Languages: A Survey. IEEE
Software, New York, v.9, n.6, p.56-66, November 1992.
[WIR 76]
WIRTH, Niklaus. Algorithms + Data Structures = Programs.
Prentice-Hall, 1976.
[WEG 93]
WEGNER, Peter. Tradeoffs between Reasoning and Modeling. In:
AGHA, G.; WEGNER, P.; YONEZAWA, A. (eds.). Research
Direction in Concurrent Object-Oriented Programming.
Cambridge: Mit Press, 1993. p.22-41
[YAM 94]
YAMIN, Adenauer C. Um Ambiente Para Exploração de
Paralelismo na Programação em Lógica. Porto Alegre: CPGCC
da UFRGS, 1994. 204p. Dissertação de Mestrado.
[ZAV 96]
ZAVE, Pamela; JACKSON, Michael. Where Do Operations Come
From? A Multiparadigm Specification Technique. IEEE
Transactions on Software Engineering, New York, v.22, n.7,
p.508-528, July 1996.