Distributed OR Scheduling with Granularity Information
Resumo
Logic Programming has some implicit sources of parallelism as OR parallelism that facilitates the automatic parallelization. There are several parallel logic systems (PLPS) that exploit only OR parallelism but most part consider shared memory in its design. Few distributed implementations exist. PLoSys is an example of this kind of distributed implementation of parallel Prolog. This paper presents a proposal of granularity control for parallel logic system and the possible enhancement in PLoSys OR parallel system concerning scheduling using granularity information. Scheduling is one of the most important part in a distributed system since it decides the task attribution to processing elements and the execution order of each task. Several performance measures could be optimized in this allocation process.
Palavras-chave:
parallel logic programming, static analysis, task scheduling, granularity analysis
Referências
H. AÏT-KACI. Warren's Abstract Machine – A Tutorial Reconstruction. MIT Press, 1991.
K. A. M. ALI and R. KARLSSON. The Muse Or-parallel Prolog Model and its Performance. In Proceedings of North American Conference on Logic Programming, pages 757–776. MIT Press, October 1990.
J. L. V. BARBOSA. Granlog: Um modelo para análise automática de granulosidade na programação em lógica. Dissertação de mestrado, Universidade Federal do Rio Grande do Sul, 1996.
J. L. V. BARBOSA and C. F. R. GEYER. Análise de complexidade na programação em lógica: Taxonomia, modelo granlog e análise ou. XXVIII Conferência Latino Americana de Informática / Encontro Chileno de Computação da Sociedade Chilena de Computação (CLEI-PANEL'97), 1997, Valparaíso, Chile.
J. L. V. BARBOSA, O. WERNER, and C. F. R. GEYER. Automatic granularity analysis in logic programming. In Tenth Logic Programming Workshop – WLP94, Zurich: Institut für Informatik der Universität Zurich, Sept. 1994.
J. BRIAT, M. FAVRE, C. F. R. GEYER, and J. CHASSIN. Scheduling of or-parallel prolog on a scalable, reconfigurable, distributed-memory multiprocessor. In PARLE’91, 1991.
L. F. P. CASTRO, V. SANTOS COSTA, C. F. R. GEYER, F. SILVA, P. K. VARGAS, and M. E. CORREA. DAOS – Scalable And-Or Parallelism. In EUROPAR’99, pages 899–898, Aug 31 – Sept 3 1999, Toulouse, France.
W. F. CLOCKSIN. Principles of the DelPhi parallel inference machine. Computer Journal, 30(5):386–392, 1987.
P. CODGENT and D. DIAZ. Wamcc: Compiling prolog to c. In L. Sterling, editor, Proceedings of the Twelfth International Conference on Logic Programming, pages 317–331, Tokyo, Japan, June 1995. MIT Press.
C. A. COSTA and C. F. R. GEYER. Uma Proposta de Escalonamento Distribuído para Exploração de Paralelismo na Programação em Lógica. In X Simpósio Brasileiro de Arquitetura de Computadores e Processamento de Alto Desempenho, 1998, Búzios, RJ.
S. K. DEBRAY and N. LIN. Cost analysis of logic programs. ACM Transactions on Programming Languages and Systems, 15(5):826–875, Nov. 1993.
S. K. DEBRAY, N.-W. LIN, and M. HERMENEGILDO. Task granularity analysis in logic programs. In Proc. of the 1990 ACM Conf. on Programming Language Design and Implementation, pages 174–188. ACM Press, 1990.
I. C. DUTRA. Distributing And- and Or-Work in the Andorra-I Parallel Logic Programming System. PhD thesis, University of Bristol, Department of Computer Science, February 1995.
I. C. DUTRA, V. SANTOS COSTA, J. L. V. BARBOSA, and C. F. R. GEYER. Using Compile-Time Granularity Information to Support Dynamic Work Distribution in Parallel Logic Programming Systems. In X Simpósio Brasileiro de Arquitetura de Computadores, SBAC-PAD, October 1999.
J. EL-REWINI, T. G. LEWIS, and H. H. ALI. Task Scheduling in Parallel and Distributed Systems. Prentice-Hall, 1994.
D. N. FERRARI, P. K. VARGAS, J. L. V. BARBOSA, and C. F. R. GEYER. Modelo de Integração Plosys-Granlog: Aplicação da Análise de Granulosidade na Exploração do Paralelismo OU. In XXV Conferência Latino Americana de Informática / Encontro Chileno de Computação da Sociedade Chilena de Computação (CLEI-PANEL'99), September 1999, Asuncion, Paraguay.
P. L. GARCIA, M. HERMENEGILDO, and S. K. DEBRAY. Towards granularity based control of parallelism in logic programs. In International Symposium on Parallel Computation, Linz, Austria, Sept. 1994.
C. GEYER, P. K. VARGAS, and I. C. DUTRA. Parallelism in logic programming. International School on Advanced Algorithmic Techniques for Parallel Computation with Applications – CIMPA’99, page 35, September 1999.
G. GUPTA, M. V. HERMENEGILDO, E. PONTELLI, and V. SANTOS COSTA. ACE: And/Or-parallel Copying-based Execution of Logic Programs. In Proceedings of the Eleventh International Conference on Logic Programming, Italy, June 1994.
G. GUPTA and B. JAYARAMAN. On Criteria for Or-parallel Execution of Logic Programs. In Proceedings of the 1990 North American Conference on Logic Programming, pages 737–756. MIT Press, October 1990.
G. GUPTA, E. PONTELLI, and M. V. HERMENEGILDO. ACE: A High Performance Parallel Prolog System. In Proceedings of the First International Symposium on Parallel Symbolic Computation (PASCO’94), 1994.
M. V. HERMENEGILDO and K. J. GREENE. The &-prolog system: Exploiting independent and-parallelism. New Generation Computing, 9(3,4):233–256, 1991.
L. HUELSBERGEN, J. R. LARUS, and A. AIKEN. Using run-time list sizes to guide parallel thread creation. In Proc. ACM Conf. on Lisp and Functional Programming, June 1994.
S. KAPLAN. Algorithm complexity of logic programs. In Proceedings of the Fifth International Conference and Symposium on Logic Programming, pages 780–793. MIT Press, 1990.
J. C. KERGOMMEAUX and P. CODOGNET. Parallel logic programming systems. Computing Surveys, 26(3):295–336, September 1994.
B. KRUATRACHUE and T. LEWIS. Grain size determination for parallel processing. IEEE Software, 5(1):23–32, January 1988.
N. LIN. Automatic Complexity Analysis of Logic Programs. PhD Thesis, Department of Computer Science, University of Arizona, Tucson, 1993.
E. LUSK et al. The Aurora or-parallel Prolog system. New Generation Computing, 7(2,3):243–271, 1990.
C. McCREARY and H. GILL. Automatic determination of grain size for efficient parallel processing. Communications of the ACM, 32(9):1073–1078, 1989.
E. MOREL, J. BRIAT, and J. CHASSIN DE KERGOMMEAUX. Cuts and side-effects in distributed-memory or-parallel prolog. Parallel Computing, 22:1883–1896, 1997.
E. MOREL, J. BRIAT, J. C. D. KERGOMMEAUX, and C. GEYER. Side-effects in PloSys Or-parallel Prolog on Distributed Memory Machines. In IJCLSP’96 Post-Conference Workshop on Parallelism and Implementation Technology for (Constraint) Logic Programming Languages, Bonn, Germany, September 1996.
E. MOREL, J. BRIAT, J. C. D. KERGOMMEAUX, and C. F. R. GEYER. Parallelism and Implementation of Logic and Constraint Logic Programming, chapter Side-effects in PloSys Or-parallel Prolog on Distributed Memory Machines. Nova Science Inc., 1999.
K. SHEN, V. SANTOS COSTA, and A. KING. A New Metric for Controlling Granularity for Parallel Execution. In ILPS’97 Workshop on Parallelism and Implementation Technology for (Constraint) Logic Programming Languages, Port Jefferson, USA, October 1997.
E. TICK. Compile Time Granularity Analysis for Parallel Logic Programming Systems. New Generation Computing, 7(2,3):325–337, 1990.
E. TICK and X. ZHONG. A compile-time granularity analysis algorithm and its performance evaluation. New Generation Computing, 11(3–4):271–295, 1993.
K. A. M. ALI and R. KARLSSON. The Muse Or-parallel Prolog Model and its Performance. In Proceedings of North American Conference on Logic Programming, pages 757–776. MIT Press, October 1990.
J. L. V. BARBOSA. Granlog: Um modelo para análise automática de granulosidade na programação em lógica. Dissertação de mestrado, Universidade Federal do Rio Grande do Sul, 1996.
J. L. V. BARBOSA and C. F. R. GEYER. Análise de complexidade na programação em lógica: Taxonomia, modelo granlog e análise ou. XXVIII Conferência Latino Americana de Informática / Encontro Chileno de Computação da Sociedade Chilena de Computação (CLEI-PANEL'97), 1997, Valparaíso, Chile.
J. L. V. BARBOSA, O. WERNER, and C. F. R. GEYER. Automatic granularity analysis in logic programming. In Tenth Logic Programming Workshop – WLP94, Zurich: Institut für Informatik der Universität Zurich, Sept. 1994.
J. BRIAT, M. FAVRE, C. F. R. GEYER, and J. CHASSIN. Scheduling of or-parallel prolog on a scalable, reconfigurable, distributed-memory multiprocessor. In PARLE’91, 1991.
L. F. P. CASTRO, V. SANTOS COSTA, C. F. R. GEYER, F. SILVA, P. K. VARGAS, and M. E. CORREA. DAOS – Scalable And-Or Parallelism. In EUROPAR’99, pages 899–898, Aug 31 – Sept 3 1999, Toulouse, France.
W. F. CLOCKSIN. Principles of the DelPhi parallel inference machine. Computer Journal, 30(5):386–392, 1987.
P. CODGENT and D. DIAZ. Wamcc: Compiling prolog to c. In L. Sterling, editor, Proceedings of the Twelfth International Conference on Logic Programming, pages 317–331, Tokyo, Japan, June 1995. MIT Press.
C. A. COSTA and C. F. R. GEYER. Uma Proposta de Escalonamento Distribuído para Exploração de Paralelismo na Programação em Lógica. In X Simpósio Brasileiro de Arquitetura de Computadores e Processamento de Alto Desempenho, 1998, Búzios, RJ.
S. K. DEBRAY and N. LIN. Cost analysis of logic programs. ACM Transactions on Programming Languages and Systems, 15(5):826–875, Nov. 1993.
S. K. DEBRAY, N.-W. LIN, and M. HERMENEGILDO. Task granularity analysis in logic programs. In Proc. of the 1990 ACM Conf. on Programming Language Design and Implementation, pages 174–188. ACM Press, 1990.
I. C. DUTRA. Distributing And- and Or-Work in the Andorra-I Parallel Logic Programming System. PhD thesis, University of Bristol, Department of Computer Science, February 1995.
I. C. DUTRA, V. SANTOS COSTA, J. L. V. BARBOSA, and C. F. R. GEYER. Using Compile-Time Granularity Information to Support Dynamic Work Distribution in Parallel Logic Programming Systems. In X Simpósio Brasileiro de Arquitetura de Computadores, SBAC-PAD, October 1999.
J. EL-REWINI, T. G. LEWIS, and H. H. ALI. Task Scheduling in Parallel and Distributed Systems. Prentice-Hall, 1994.
D. N. FERRARI, P. K. VARGAS, J. L. V. BARBOSA, and C. F. R. GEYER. Modelo de Integração Plosys-Granlog: Aplicação da Análise de Granulosidade na Exploração do Paralelismo OU. In XXV Conferência Latino Americana de Informática / Encontro Chileno de Computação da Sociedade Chilena de Computação (CLEI-PANEL'99), September 1999, Asuncion, Paraguay.
P. L. GARCIA, M. HERMENEGILDO, and S. K. DEBRAY. Towards granularity based control of parallelism in logic programs. In International Symposium on Parallel Computation, Linz, Austria, Sept. 1994.
C. GEYER, P. K. VARGAS, and I. C. DUTRA. Parallelism in logic programming. International School on Advanced Algorithmic Techniques for Parallel Computation with Applications – CIMPA’99, page 35, September 1999.
G. GUPTA, M. V. HERMENEGILDO, E. PONTELLI, and V. SANTOS COSTA. ACE: And/Or-parallel Copying-based Execution of Logic Programs. In Proceedings of the Eleventh International Conference on Logic Programming, Italy, June 1994.
G. GUPTA and B. JAYARAMAN. On Criteria for Or-parallel Execution of Logic Programs. In Proceedings of the 1990 North American Conference on Logic Programming, pages 737–756. MIT Press, October 1990.
G. GUPTA, E. PONTELLI, and M. V. HERMENEGILDO. ACE: A High Performance Parallel Prolog System. In Proceedings of the First International Symposium on Parallel Symbolic Computation (PASCO’94), 1994.
M. V. HERMENEGILDO and K. J. GREENE. The &-prolog system: Exploiting independent and-parallelism. New Generation Computing, 9(3,4):233–256, 1991.
L. HUELSBERGEN, J. R. LARUS, and A. AIKEN. Using run-time list sizes to guide parallel thread creation. In Proc. ACM Conf. on Lisp and Functional Programming, June 1994.
S. KAPLAN. Algorithm complexity of logic programs. In Proceedings of the Fifth International Conference and Symposium on Logic Programming, pages 780–793. MIT Press, 1990.
J. C. KERGOMMEAUX and P. CODOGNET. Parallel logic programming systems. Computing Surveys, 26(3):295–336, September 1994.
B. KRUATRACHUE and T. LEWIS. Grain size determination for parallel processing. IEEE Software, 5(1):23–32, January 1988.
N. LIN. Automatic Complexity Analysis of Logic Programs. PhD Thesis, Department of Computer Science, University of Arizona, Tucson, 1993.
E. LUSK et al. The Aurora or-parallel Prolog system. New Generation Computing, 7(2,3):243–271, 1990.
C. McCREARY and H. GILL. Automatic determination of grain size for efficient parallel processing. Communications of the ACM, 32(9):1073–1078, 1989.
E. MOREL, J. BRIAT, and J. CHASSIN DE KERGOMMEAUX. Cuts and side-effects in distributed-memory or-parallel prolog. Parallel Computing, 22:1883–1896, 1997.
E. MOREL, J. BRIAT, J. C. D. KERGOMMEAUX, and C. GEYER. Side-effects in PloSys Or-parallel Prolog on Distributed Memory Machines. In IJCLSP’96 Post-Conference Workshop on Parallelism and Implementation Technology for (Constraint) Logic Programming Languages, Bonn, Germany, September 1996.
E. MOREL, J. BRIAT, J. C. D. KERGOMMEAUX, and C. F. R. GEYER. Parallelism and Implementation of Logic and Constraint Logic Programming, chapter Side-effects in PloSys Or-parallel Prolog on Distributed Memory Machines. Nova Science Inc., 1999.
K. SHEN, V. SANTOS COSTA, and A. KING. A New Metric for Controlling Granularity for Parallel Execution. In ILPS’97 Workshop on Parallelism and Implementation Technology for (Constraint) Logic Programming Languages, Port Jefferson, USA, October 1997.
E. TICK. Compile Time Granularity Analysis for Parallel Logic Programming Systems. New Generation Computing, 7(2,3):325–337, 1990.
E. TICK and X. ZHONG. A compile-time granularity analysis algorithm and its performance evaluation. New Generation Computing, 11(3–4):271–295, 1993.
Publicado
24/10/2000
Como Citar
VARGAS, Patrícia Kayser; BARBOSA, Jorge Luis V.; FERRARI, Débora Nice; GEYER, Cláudio F. R.; CHASSIN, Jacques.
Distributed OR Scheduling with Granularity Information. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 12. , 2000, São Pedro/SP.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2000
.
p. 253-260.
DOI: https://doi.org/10.5753/sbac-pad.2000.41223.
