Autores

4647
160,2060
4648
160,2060

Informações:

Publicações do PESC

Título
Um Estudo do Impacto de Informação de Granulosidade em Estratégias de Escalonamento para Sistemas Prolog que Exploram Paralelismo-OU
Linha de pesquisa
Arquitetura e Sistemas Operacionais
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
26/3/2004
Resumo

Este trabalho tem por objetivo integrar informação de granulosidade gerada em tempo de compilação (análise estática) pela ferramenta ORCA (OR Complexity Analyzer) em um programa que simula o funcionamento paralelo de uma máquina Prolog com um número variável de processadores. Esta informação é aplicada no auxílio a decisões de escalonamento dos programas em lógica para as políticas topmost, bottom-most, menor-custo e para uma nova política chamada ORCA-Top.

Para estudar as políticas de escalonamento que já existiam no simulador, comparamos os resultados obtidos com e sem informação de granulosidade, e da nova política. Extraímos estes resultados numa situação ideal, quando nenhum custo para exploração do paralelismo é considerado e quando se leva em consideração custos arquiteturais (memória compartilhada e distribuída).

Quanto ao conjunto de benchmarlts, utilizamos aplicações que possuem somente paralelismo OU.

Nossos resultados mostram que o desempenho dos programas Prolog é afetado positivamente quando introduzimos informação de granulosidade às decisões do escalonador. Mostramos que a medida default de complexidade pode ser muito "gulosa" ao atribuir pesos às cláusulas, o que pode levar a speedups menores. De forma geral, todas as aplicações estudadas melhoram seu speedup mínimo e máximo com a introdução de medidas de complexidade.

Abstract

This worlt intends to integrate compile-time granularity inforrnation generated by the ORCA to01 (static analysis) in a program that simulates the parallel execution of a Prolog machine with a varying number of processors.

This ltind of information is helpful for scheduling decisions in logic programs execution, when choosing one of the following strategies: top-most, bottom-most and minor cost. That information was also used to create a new strategy that we called ORCA-Top.

In order to study the strategies already created, we compare the results obtained with and without granularity information, and the new strategy. We obtained these results under an ideal situation, when no cost for exploration of parallelism is considered and when we consider architectural costs (Shared and Distributed Memory).

The benchmarlts used have only OR-Parallelism. 

The results showed that the performance of Prolog programs is positively affected when we add granularity information to the decisions made by the scheduler. We showed that the default complexity measure generated by ORCA may be very "greedy" when attributing weights to clauses, which can lead to smaller speedups. In general, all applications studied improve their minimum and maximum speedups when adding complexity measures.

Arquivo
Topo