Análise de Desempenho de Sistemas de Programação Lógica
Autores
|
1741 |
Vanusa Menditi Calegario
|
435,160
|
|
1742 |
435,160
|
Informações:
Publicações do PESC
Análise de Desempenho de Sistemas de Programação Lógica
Vanusa Menditi Calegário
Março/1999
| Orientador: | Inês de Castro Dutra | |
| ||
Este trabalho faz uma análise de desempenho de sistemas de programação lógica, em particular sistemas seqüenciais e paralelos. Programação lógica não é muito utilizada devido a sua conhecida ineficiência, embora tenha se mostrado mais simples que programação imperativa, por exemplo. Assim, procurou-se avaliar técnicas como compilação, tabulação e paralelismo que visam amenizar esta deficiência. Sempre que possível foi feita uma comparação tomando como base a linguagem C, devido à popularidade e eficiência de sistemas convencionais construídos utilizando-se esta linguagem. Desta forma, um conjunto de aplicações científicas e simbólicas foi escolhido e escrito em Prolog e em C objetivando-se verificar programabilidade, tempo de execução e escalabilidade (considerando paralelismo). Primeiramente, foram averiguados os ganhos obtidos desde a interpretação até a geração de código nativo. Para isto, Sicstus e Yap foram utilizados numa UltraSparc1. Com Sicstus, os ganhos variaram de 1,14 a 9,41 vezes quando altera-se de código interpretado para emulado e de 1,24 a 3,61 vezes quando altera-se de emulado para compilado. A seguir, tabulação foi avaliada com o uso de XSB também numa UltraSparc1. Os ganhos com tabulação mostraram-se, como previsto, bastante favoráveis para aquelas aplicações com alto índice de recomputação. Por fim, paralelismo foi avaliado utilizando-se, basicamente, simulação e execução real. No que diz respeito à simulação, foi utilizado um simulador orientado a eventos, baseado em hardware DSM (Distributed Shared Memory) (DASH), para execução paralela de C e Aurora, compilados para a arquitetura MIPS. Aurora é um sistema paralelo de programação lógica que explora somente paralelismo-OU. Com isto, foi possível fazer uma análise bem detalhada do comportamento dos dois sistemas utilizando-se de 1 a 32 processadores. Os resultados indicaram que sistemas paralelos de programação lógica são competitivos com programas C paralelos no que diz respeito à programabilidade, escalabilidade e eficiência. Otimizações tais como geração de código nativo e uso de diferentes estratégias de escalonamento podem melhorar o desempenho substancialmente. Pode-se observar, para algumas aplicações, que Aurora obteve boa escalabilidade. Além disto, mesmo com um alto número de referênciasà memória, Aurora conseguiu manter um bom índice de localidade. A análise de distintos protocolos de coerência de cache permitiu-nos concluir que Aurora se beneficia de protocolos híbridos. Considerando execução real, C e Aurora foram avaliados numa SMP (Symmetric MultiProcessor) com quatro processadores. A escalabilidade nesta diferente arquitetura foi similar àquela atingida com as simulações. Como principais conclusões gerais obtidas podemos citar: As técnicas estudadas em programação lógica podem tornar Prolog competitivo com outras linguagens convencionais; programas C paralelos precisam ser bem escritos e estrutura de dados bem organizadas para conseguir bom desempenho e boa localidade em diferentes arquiteturas; sistemas paralelos de programação lógica podem ser competitivos com outras linguagens com certas otimizações para aumentar desempenho. Melhorias no escalonamento mostrar-se-iam bastante relevantes não só para Aurora como também para os programas em C.
Performance Analysis of Logic Programming Systems
Vanusa Menditi Calegário
March/1999
| Advisor: | Inês de Castro Dutra | |
| Department: Systems Engineering and Computer Science | ||
This work analyses the performance of sequential and parallel logic programming systems. Logic programming is known to be easier and simpler than imperative programming, but it is not very popular because of its believed inefficiency. In this work we investigate the reasons for this inefficiency and show that techniques such as compilation, tabling and parallelism can minimize it. We use the C language as a comparison basis. A set of symbolic and scientific applications was chosen and written in Prolog and in C so that we could evaluate programmability, execution time and scalability (considering parallelism). Our first experiment measured the gains we can obtain with sequential systems when using sophisticated compile-time tools, native code generation and tabling. In order to perform these experiments we use three Prolog systems: Sicstus, Yap and XSB, on a UltraSparc1. Regarding Sicstus, results showed that emulated code runs from 1.14 to 9.41 times faster than interpreted code and compiled code runs from 1.24 to 3.61 times faster than emulated code. Tabling was very good for those applications with a high rate of recomputation. Our second experiment consisted of real and simulated execution of parallel C applications and Aurora, a system that exploits implicit parallelism in logic programming. Regarding real execution, Aurora and C were evaluated on a SMP (Symmetric MultiProcessor) machine with 4 processors. Scalability was similar to that obtained with simulation. Considering simulation, we used an execution-driven simulator based on hardware DSM (Distributed Shared Memory) (DASH) for parallel execution of C and Aurora, compiled for the MIPS architecture. A detailed analysis was done using from 1 to 32 processors. Results showed that parallel logic programming systems are competitive with parallel C systems regarding programmability, scalability and efficiency. Optimisations such as native code generation and different scheduling strategies can improve performance significantly. For some applications, Aurora had a reasonable scalability in spite of the high number of shared memory references. Furthermore, Aurora managed to maintain good locality. In our third experiment distinct cache coherence protocols were evaluated and we concluded that Aurora benefits from hybrid protocols. Finally, we can pinpoint some general conclusions: techniques studied in logic programming can make Prolog competitive with conventional languages; parallel C programs need a good programming style and data structures need to be well organised in order to achieve good performance and good locality in different architectures; parallel logic programming systems with optimisations that improve performance can be competitive with other languages. Improving scheduling policies would be favorable not only for Aurora but also for C programs. Our best result, recursive fibonacci, showed that a logic program could run faster than its C counterpart using the tabling technique.