Paralelismo em linguagens logicas

	Diferente das linguagens de programacao convencionais as
linguagens logicas nao permitem atribuicoes destrutivas e sequenciacao
explicita. Estas caracteristicas alem de permitir uma semantica mais
clara, permite ao mecanismo de inferencia empregar diferentes
estrategias de solucao.
	A semantica das linguagens logicas permite que operacoes
diferentes sejam executadas em qualquer ordem sem afetar a logica do
programa. Em particular, isto significa que as operacoes podem ser
efetuadas em paralelo.
	A execucao paralela de diferentes operacoes resulta numa
exploracao implicita do paralelismo, tirando do programador o onus de
tratar o paralelismo e colocando-o sobre o mecanismo de inferencia (ha
formas de explorar explicitamente o paralelismo). Isto contrasta com
outras abordagens normalmente usadas em linguagens convencionais onde
o paralelismo deve ser explicitado pelo programador.

	Sao dois os principais tipos de paralelismo:
	- MIMD - paralelismo de controle
	diferentes threads sao executados em paralelo.
	- SIMD - paralelismo dos dados
	instrucoes identicas sao executadas por processadores
diferentes sobre dados diferentes.

Cinco tipos principais de paralelismo podem ser identificados em
programacao logica:
	- paralelismo de busca
	o banco de dados de fatos e clausulas e dividido em segmentos
que sao distribuidos a multiplos processadores. Pode ser visto como
uma forma de SIMD.

	- paralelismo de unificacao
	diferentes argumentos podem ser unificados em paralelo. Mais
eficientemente explorado como SIMD.

	- paralelismo-ou
	mais de uma regra define uma relacao e a chamada do
procedimento unifica com a cabeca de mais uma regra. Os corpos de cada
regra podem ser executados em paralelo. MIMD.

	- paralelismo-e independente
	mais de um objetivo presente no corpo de uma clausula e suas
variaveis sao independentes. MIMD.

	- paralelismo-e dependente
	dois ou mais objetivos do corpo da clausula possuem variaveis
em comum. MIMD.
	
	Um ponto importante e notar que cada paralelismo independe um
do outro, podendo ser portanto explorado mais de um tipo ao mesmo
tempo. Contudo nenhum sistema paralelo eficiente foi construido
contendo todos os cinco tipos de paralelismo ate hoje.

	Paralelismo-e indepedente

	Fibonacci

	fib(0,1).
	fib(1,1).
	fib(M,N) :- [ M1 is M - 1 , fib(M1,N1) ] 
				&
			[M2 is M - 2 , fib(M2,N2) ] ,
			N is N1 + N2.

	As duas listas de 	objetivos entre colchetes sao
independentes e podem ser executadas em paralelo. Ja N is N1 + N2
depende dos objetivos anteriores e portanto so podera ser executado
quando estes terminarem.
	O paralelismo-e independente se encaixa perfeitamente em
algoritmos "dividir-para-conquistar" onde cada chamada recursiva
independente pode ser executada em paralelo.
	Enquanto o paralelismo-ou somente pode ser explorado em
programas nao deterministicos, o paralelismo-e pode ser explorado
tanto em programas deterministicos como nao deterministicos. Sendo
assim, quando temos um problema deterministico devemos tentar explorar
o paralelismo-e ao maximo.
	Embora o paralelismo-e seja explorado implicitamente, a
estrategia adotada na programacao pode tirar mais ou menos proveito do
paralelismo.

Ex.: Fatorial (Problema deterministico)

Fatorial Simples

	fat(0,1).
	fat(N,M) :- N > 0 , N1 is N - 1 , fat(N1,M1) , M is N * M1.

Fatorial Paralelo

	fat(N,M) :- fat(1, N , M).
	fat(N, N, N).
	fat(L, H, M) :- L < H , 
			[ MID1 is (L + H)/2 , fat(L , MID1, M1) ]
				&
			[MID2 is (L + H)/2 + 1, fat(MID2, H , M2) ] ,
			M is M1 * M2.

	Fases de um sistema de paralelismo-e independente

	I) Ordering phase

	Detecta dependencia entre os objetivos para decidir se podem
ou nao ser executados em paralelo. Se a execucao em paralelo for
iniciada sem checar a dependencia, grande quantidade de computacao
desnecessaria podera ocupar o processamento.
	A dependencia nao pode ser totalmente detectada em tempo de
compilacao.

Ex.: p(X , Y) :- r(X) , s(Y).

	r e s sao aparentemente independentes porem se for feita a
chamada p(Z , Z), r e s tornam-se dependentes.
	Sendo insuficiente a checagem em tempo de compilacao, devemos
fazer testes de dependencia em tempo de execucao, porem isto reduz a
velocidade de execucao do programa. Surge assim o problema de detectar
o maximo de paralelismo sem comprometer a velocidade de execucao com
testes excessivos.

	Algumas abordagens:

	I - Modos de entrada e saida:
	Os modos de cada variavel devem ser definidos pelo
programador. Uma variaval de entrada deve estar instanciada antes da
execucao do objetivo.

	II - Analise estatica de dependencia de dados:
	As clausulas sao globalmente analisadas em tempo de
compilacao, assumindo os piores casos para checar dependencia. Sendo
assim, muitas execucoes que poderiam ser efetuadas em paralelo nao sao
aproveitadas.

	III - Grafos de dependencia em tempo de execucao:
	Um grafo indicando a dependencia entre as variaveis e mantido
em tempo de execucao. O paralelismo e aproveitado ao maximo, porem o
grafo e custoso do ponto de vista de tempo de processamento.

	IV - Paralelismo-e restrito
	E um meio termo entre as abordagens II e III. Esta abordagem
encapsula a informacao de dependencia obtida em tempo de compilacao no
codigo gerado. Testes simples sao efetuados em tempo de execucao em
cima destas informacoes. Nao explora todo o paralelismo possivel,
porem explora uma porcao consideravel.

	II - Forward execution phase

	Nesta fase sao selecionados objetivos independentes que podem
ser executados em paralelo e e iniciada a execucao. A execucao segue
como uma execucao sequencial normal ate que ocorra uma falha ou que
uma solucao seja encontrada. Dependendo da abordagem adotada a
"ordering phase" pode voltar a ser executada. Na abordagem do esquema
de Conery, quando um termo nao instanciado e gerado a "ordering phase"
e novamente iniciada a fim de detectar dependencia. O unico problema
de implementacao desta fase e detectar eficientemente se um objetivo
esta pronto para ser executado em paralelo.

	III - Backward execution phase

	Esta fase e iniciada quando ocorre uma falha ou quando e
iniciada a busca de uma outra solucao apos ja ter encontrado a
primeira. Dois problemas principais podem ser apontados:
	I - terminar a execucao de sub-objetivos que estejam sendo
executados em paralelo de forma eficiente.
	II - selecionar de forma eficiente e correta o sub-objetivo
para onde devera ser feito o backtracking.

	Criterios para a execucao paralela-e

	I - Um sistema paralelo-e ideal nao deve efetuar computacao
desnecessaria.
	II - Nao deve conter analises complexas em tempo de execucao.
	III - Deve ter um sistema inteligente de backtracking.

	Backtracking inteligente

? a,b,c,d.

Suponhamos que b e c sejam independentes e possam ser executados em
paralelo. Numa execucao sequencial caso c falhe seria feito um
backtracking para b. Contudo como b e c nao tem nenhuma depencia de
dados, tentar achar outra solucao para b nao ajudaria c em nada. Entao
caso c falhe devemos fazer um backtracking para a. Como pode ser
observado a dependencia de dados e necessaria tanto para o
backtracking inteligente como para a execucao paralela-e. Sendo assim
um sistema paralelo-e deve aproveitar as analises de depencia de dados
para implementar um sistema de backtracking inteligente.

	Modelos de implementacao de paralelismo-e:

	Modelo de Conery:

	Neste metodo um grafo e construido na "ordering phase"
representando as relacoes produtor-consumidor entre os sub-objetivos.
Se um conjunto de sub-objetivos tem uma variavel nao instanciada V em
comum, um destes sub-objetivos e designado como produtor de V e e
resolvido primeiro. A sua solucao devera instanciar V. Quando o
produtor e resolvido, os outros sub-objetivos podem ter sua execucao
iniciada.
	Uma vez construido o grafo de fluxo de dados a "forward
execution" e iniciada pelos sub-objetivos que nao possuem arcos
incidentes no grafo. Quando um sub-objetivo e resolvido o no
correspondente e todos os arcos emanando do mesmo sao removidos do
grafo. Se um termo nao instanciado e criado a "ordering phase" deve
ser iniciada para que o grafo seja redesenhado (custo muito alto em
tempo de execucao).

	Modelo APEX ( Modelo de Conery Aperfeicoado) :

	Neste modelo a "forward execution phase" e implementada
atraves de um mecanismo de passagem de "token". Um "token" e criado
para cada nova variavel que aparece durante a execucao de uma
clausula. Um sub-objetivo P e produtor da variavel V se esta contem o
token de V. Um novo token para uma variavel V e dado para o
sub-objetivo mais a esquerda na clausula que contem a variavel. Um
sub-objetivo pode ser executado quando este possui os "tokens" de
todas as suas variaveis que nao estao instanciadas. O paralelismo e
explorado automaticamente quando mais de um sub-objetivo esta pronto
para a execucao.
	E feito um backtracking inteligente. Cada sub-objetivo Pi
mantem dinamicamente uma lista de sub-objetivos denotada como
B-list(Pi), contendo os sub-objetivos que contribuiram para instanciar
as variaveis nos argumentos de Pi. Quando Pi falha o backtracking e
feito para Pj, que e o sub-objetivo na cabeca da B-list(Pi). A calda
de B-list(Pi) e adicionada em B-list(Pj). Assim sendo, caso nao exista
outra solucao de Pj capaz de satisfazer Pi o backtracking passa a ser
feito nos demais elementos de B-list(Pi).

	Modelo RAP ( Restricted And-Parallelism):

	Neste metodo as clausulas do programa sao compiladas na forma
de expressoes de grafos condicionais (CGEs = Conditional Graph
Expressions).

	CGEs sao expressoes na forma:

	Condicao => objetivo1&objetivo2&...&objetivon.

	Significando que caso a condicao seja verdadeira os objetivos
devem ser executados em paralelo e caso contrario devem ser executados
sequencialmente. A condicao pode ser:

	ground(v1,...,vn) => checa se as variaveis v1,...,vn estao
instanciadas.
	independent(v1,...,vn) => checa se o conjunto de variaveis
alcancaveis a partir de v1,...,vn sao mutuamente exclusivas umas com
as outras.

	true => os objetivos podem ser executados em paralelo
incondicionalmente.

	As condicoes ground e independent sao implementadas atraves de
testes simples e conservativos, por exemplo, um termo pode ser
considerado nao instanciado mesmo quando instanciado. Assim sendo,
CGEs nao considem capturar todo o paralelismo-e existente, mas
consegue capturar uma porcao substancial.

	Paralelismo-e dependente:

	Dois sub-objetivos com dados dependentes podem ser executados
em paralelo desde que sejam estabelecidas certas restricoes, pois em
caso contrario poderia resultar em grande computacao desnecessaria. A
restricao que e normalmente imposta e a de que apenas um sub-objetivo
pode instanciar a variavel dependente (o produtor) enquanto o outro
apenas pode ler este valor (o consumidor). A variavel dependente
torna-se um canal de comunicacao entre os sub-objetivos.
	Ao inves de adotarmos a restricao de produtor-consumidor,
tambem podemos assumir uma comunicacao bilateral dando origem ao
efeito "coroutining". Assim sendo, o paralelismo-e dependente pode ser
explorado com ou sem "coroutining".

	Explorando o paralelismo-e dependente sem "coroutinig":

	Surgem dois problemas principais:

	I - determinar qual instancia da variavel e o produtor e qual
e o consumidor.
	II - obter um mecanismo eficiente para retomar os
sub-objetivos suspenso pela falta de uma determinada variavel quando
esta e instanciada.

	Como exemplo temos o DDAS (Dynamic Dependent And-Parallel
System), onde dois sub-objetivos que compartilham uma variavel sao
executados em paralelo ate que um deles acesse a variavel. Se o
sub-objetivo que acessou a variavel e o consumidor e a variavel nao
esta instanciada este e suspenso. Quando o produtor instancia a
variavel o consumidor e retomado.
	Nesta abordagem o paralelismo-e dependente e muito similar ao
paralelismo-e independente ja que dois sub-objetivos sao executados em
paralelo enquanto um nao interfere no outro.

	Explorando o paralelismo-e dependente com "coroutining":

	O grande problema desta abordagem e a existencia do
nao-determinismo.
	Antes de qualquer cooperacao entre os sub-objetivos o
nao-determinismo deve ser eliminado. Aparecem tres opcoes:

	I - Aplicar o nao-determinismo "don't care", eliminando todas
as alternativas menos uma para cada sub-objetivo (Comitted Choice
Languages)

	II- Deixar os sub-objetivos executarem tomando certos cuidados
para que apenas uma solucao seja encontrada para cada sub-objetivo
(Modelo de Andorra)

	III - Criar uma copia do objetivo consumidor para cada
alternativa do produtor e vice-versa, deixando a execucao correr em
cada combinacao. (Modelo de Andorra Extendido).

	O modelo de Andorra

	Neste modelo os objetivos podem seguir sua execucao em
paralelo se sao deterministicos, ou seja, se no maximo uma cabeca de
clausula unificar com o objetivo. Esta e a chamada fase
deterministica.
	Estes objetivos deterministicos podem ser dependentes um do
outro. Se nenhum objetivo deterministico pode ser encontrado para
execucao, uma ramificacao e criada (fase nao-deterministica) e a
execucao de objetivos deterministicos continua em cada ramo.
Paralelismo-ou pode ser utilizado na execucao dos diferentes ramos em
paralelo.

	O modelo de Andorra Estendido.

	Este modelo vai um passo alem eliminando a restricao de que os
objetivos devem se tornar deterministicos antes de sua execucao.
Entretanto, os objetivos nao deterministicos que seguem sua execucao
somente podem prosseguir enquanto estao produzindo, para as variaveis
nao instanciadas, valores compativeis com o escopo externo. Caso
contrario, a execucao e suspensa.
	Quando e alcancado um estado em que nao e mais possivel seguir
o processamento, cada objetivo suspenso que e um produtor cria no
escopo externo um novo "binding" para a variavel. Para cada "binding"
criado e criada uma copia do consumidor.

	Conclusoes

	O paralelismo-e, desde que bem explorado, pode acelerar muito
a execucao. A sua importancia e evidenciada em problemas
deterministicos onde ocorre a ausencia de paralelismo-ou.
	Um ponto a enfatizar e que o paralelismo e transparente ao
programador, o qual escreve o seu programa sem se preocupar de que
forma este sera executado (portabilidade).
	A questao "ser bem explorado" vem do problema de nao podermos
identificar todo, ou pelo menos uma parte substancial, do
paralelismo-e em tempo de compilacao, sendo necessarios testes em
tempo de execucao. A complexidade e a eficiencia destes testes sao
dois pontos a serem pesados para que ao mesmo tempo que o maximo de
paralelismo seja explorado, o tempo de execucao nao seja
demasiadamente tomado.

	Referencias

	Multiprocessor Execution of Logic Programs, Gopal Gupta.
	Distributing And- and Or-Work in the Andorra-I Parallel Logic
Programming System, Ines de Castro Dutra.