Análise de Políticas de Escalonamento para Sistemas Prolog que Exploram Paralelismo OU
Autores
|
1873 |
Adriana Marino Carrusca
|
795,160
|
|
1874 |
795,160
|
Informações:
Publicações do PESC
Análise de Políticas de Escalonamento para Sistemas Prolog que Exploram Paralelismo OU
Adriana Marino Carrusca
Março/2000
| Orientador: | Inês de Castro Dutra | |
| ||
Esta tese tem por objetivo realizar uma análise comparativa entre diferentes técnicas de escalonamento para sistemas Prolog que exploram paralelismo OU.
Para o desenvolvimento deste trabalho foram implementados dois simuladores: um seqüencial e outro paralelo. O primeiro executa programas de acordo com os mecanismos básicos de qualquer sistemas Prolog. No segundo, o paralelismo é obtido pela execução simultânea das clausulas que fazem matching com um determinado objetivo. Neste caso, é utilizado um número variável de processadores.
Foram estudadas quatro políticas: top-most, bottom-most, left-most e menor custo. As três primeiras utilizam um critério fixo para a escolha de tarefas, segundo sua posição na árvore de execução. A última escolhe, m cada momento, a tarefa que representa o menor custo. Este é calculado como o número de nós que devem ser percorridos até que a nova tarefa seja atingida.
Em nossos experimentos, utilizamos aplicações pertencentes a um conjunto de benchmarks, que normalmente são testadas em sistemas paralelos de programação lógica que exploram paralelismo OU.
Para estudar o impacto das estratégias de escalonamento em ambientes paralelos distintos, consideramos os custos inerentes às trocas de contexto para memória compartilhada e distribuída. É analisada também, uma ideal, em que os custos não são computados.
Nossos resultados mostram que a política que escolhe a tarefa de menor custo apresenta-se bastante eficiente para a maioria dos casos, sendo, portanto, uma boa opção para deslocamento de trabalho.
Analysis of Scheduling Policies for OR-Parallel Prolog Systems
Adriana Marino Carrusca
March/2000
| Advisor: | Inês de Castro Dutra | |
| Department: Systems Engineering and Computer Science | ||
The main objective of this work is to perform a comparative analysis of different scheduling strategies for OR-parallel Prolog systems. Two simulators were implemented to develop this work: a sequential and a parallel one. The sequential simulator executes programs according to the basic mechanisms of any Prolog system. In the parallel simulation, the parallelism is obtained executing all the clauses which match a specific goal simultaneously. In this case, we use a variable number of processors.
In the parallel execution, the scheduling phase has deep importance because, depending on the way tasks are attributed to free processors and on the tree shape, different speedups may be obtained in the program execution.
We analyse four policies: top-most, bottom-most, left-most and minor cost. The first three policies use estabilished criterias to choose tasks from the task queue, according to their position in the execution tree. The last one chooses the task which represents the minor cost at each moment. The cost is calculated as the number of nodes which should be traversed in order to reach the new task.
In our tests, we use a set of benchmark applications, which are commonly used in OR-parallel logic programming systems.
To study the impact of scheduling strategies in different parallel environments, we consider the costs inherent to task switching for shared and distributed memory.
We also analyse an ideal situation, where costs are not taken into account.
In our results, the minor cost policy proved to be very efficient to most cases, therefore being a good option to scheduling work.