Introduzindo o Paralelismo OU na Programação em Lógica com Restrições

  • Patrícia Kayser Vargas UFRGS
  • Claúdio Fernando Resin Geyer UFRGS

Resumo


O objetivo da programação em lógica com restrições (Constraint Logic Programming ou CLP) é obter maior eficiência do que as linguagens em lógica durante a execução através do uso de restrições para descartar opções inválidas, diminuindo o espaço de busca do problema. A execução em paralelo é uma das opções para melhorar ainda mais o seu desempenho. Esse artigo propõe um modelo multi-seqüencial de exploração de paralelismo OU em CLP, onde cada trabalhador possui uma máquina CLP completa sobre domínios finitos. Além disso, propõe-se uma política de escalonamento de tarefas distribuída. O protótipo pclp(FD) será baseado nesse modelo. Ele facilitará a inclusão de novas características no futuro. Para tal, serão utilizados objetos distribuídos.

Referências

AIT-KACI, Hassan. The WAM: A (Real) Tutorial. Paris: Digital Equipment Corporation, Research Laboratory, Jan 1990.

ALI, Khayri A. KARLSSON, Roland. The Muse Or-Parallel Prolog Model and its Performance". NACLP 1990. Proceedings... pp. 757-776.

BARBOSA, Jorge Luís Victória; GRANLOG: Um Modelo para Análise Automática de Granulosidade na Programação em Lógica. Porto Alegre: CPGCC-UFRGS, 200p,1995. (dissertação de mestrado)

CASTRO, Luis Fernando Pias de. Um Modelo de Analisador Estático Baseado na Interpretação Abstrata Direcionado à Paralelização de Programas em Lógica Porto Alegre: CPGCC-UFRGS (dissertação de mestrado em andamento)

CODOGNET, Philippe; DIAZ, Daniel. wamcc: Compiling Prolog to C. In: 12th International Conference on Logic Programming, Tokyo, Japan. Proceedings... MIT Press, 1995, p.317-331.

CODOGNET, Philippe; DIAZ, Daniel. Compiling Constraints in clp(FD). Journal of Logic Programming, New York, v.27, n.1, 45p., 1996.

COSTA, Cristiano André da. Uma Proposta de Escalonamento Distribuído para Exploração do Paralelismo na Programação em Lógica. Porto Alegre: CPGCC-UFRGS (dissertação de mestrado em andamento)

DINCBAS, M.; HENTENRYCK, P. Van; SIMONIS, H.; AGGOUN, A.; GRAF, T., BERTIDER, F. The Constraint Logic Programming Language 395 CHIP. In: Intemational Conference on Fifth Generation Computer Systems 1988. Proceedings." ICOT, 1988, p.693-702 ..

FRÜHWITH, Thom et all. Constraint Logic Programming: An Informal lntroduction. Müchen, Germany: ECRC, 25p, February 1993. (relatório técnico ECRC-93-5- disponível em ftp://ftp.ecrs.de:/pub/ECRC_tech_reports)

GEYER, Cláudio Fernando Resin; Briat, Jacques. et al. OPERA: Or-Parallel Prolog System on Supernode. In: lmplementations of Distributed Prolog, John Wiley & Sons Ltda, 1992.

JAFFAR, Joxan; MAHER, Michael J. Constraint Logic Programming: A Survey. The Journal of Logic Programming, New York, v.19/20, p.503-581. May/July 1994.

KERGOMMEAUX, Jacques Chassin; CODOGNET, Philippe. Parallel Logic Systems. France: Institut Grenoble/IMAG. Maio 1992 (relatório de pesquisa)

LUSK, E. WARREN; H., HARIDI, S. The Aurora. Or-Parallel Prolog System. University of Bristol, 1990. (relatório técnico TR-90-07)

MUDAMBI, Shyam; SCHIMPF, Joachim. Parallel CLP on Heterogeneous Networks. In: Eleventh Intemational Conference on Logic Programming, June 13-18, 1994, Santa Marherita Ligure, Italy. Proceedings ... MIT Press, p.124-141, 1994

PREE, Wolfgang; et al. Application of Design Pattems in Commercial Domains. In: 10th European Conference on Object-Oriented Programming. Austria. Proceedings ... 1996.

PRESTWICH, Steven. ElypSys Programming Tutorial. ECRC, 30p., April 1993 (relatório técnico)

RÉTY, Jean-Huges. A Distributed Concurrent Constraint Programming Language. S.L: s.n. March 1996.

TONG, Bo-Ming; LEUNG, Ho-Fung. Concurrent Constraint Logic Programming on Massively Parallel SIMD Computers. In: 1993 lntemational Symposium in Logic Programming, Vancouver, Canada, Proceedings... MIT Press, 1993

VARGAS, Patrícia Kayser. Implementação de um Analisador de Granulosidade para Prolog. Porto Alegre: CIC/UFRGS, 1995. 71p. (projeto de diplomação)

VARGAS, Patrícia Kayser. Um Estudo sobre as Linguagens em Lógica com Restrições. CPGCC/UFRGS: Porto Alegre, 1997. 40p. (trabalho individual)

WERNER, Otília Uma Máquina Abstrata Estendida para o Paralelismo E na Programação em Lógica. CPGCC/UFRGS: Porto Alegre, 1994. 170p. (dissertação de mestrado)

YAMIN, Adenauer Corrêa Um Ambiente para Exploração de Paralelismo na Programação em Lógica. Porto Alegre: CPGCC-UFRGS, 1994. 212p. (dissertação de mestrado)

YANG, Rong lmplementing a Finite Domain Constraint Solving System. ICLP95 - Workshop on Parallel Logic Programming, Kanagawa, Japan. Proceedings ... June 1995
Publicado
07/10/1997
VARGAS, Patrícia Kayser; GEYER, Claúdio Fernando Resin. Introduzindo o Paralelismo OU na Programação em Lógica com Restrições. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 9. , 1997, Campos do Jordão/SP. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 1997 . p. 381-396. DOI: https://doi.org/10.5753/sbac-pad.1997.22637.