Execução Especulativa em uma Máquina Virtual Dataflow
Autores
|
4801 |
2144,131
|
|
|
4802 |
2144,131
|
Informações:
Publicações do PESC
A programação paralela se tornou mandatória para explorar totalmente o potencial das CPUs modernas. Frequentemente o paralelismo é limitado pelas dependências entre instruções ou blocos de instruções. Para contornar esse problema, em modelos de execução otimistas ou especulativos, é permitido que threads prossigam mesmo que possa haver dependências. Neste caso, o último estado consistente da máquina deve ser recuperado e as computações conflituosas devem ser reexecutadas.
Acreditamos que modelos de execução especulativa se adequem naturalmente ao estilo de execução dataflow. No entanto, um problema do modelo dataflow é que ou as tarefas são muito pequenas, de granularidade fina, e o sistema paralelo tem seus canais de comunicação inundados; ou as tarefas são de granularidade muito grossa, fazendo com que suas dependências sejam complexas e difíceis de serem expressadas, levando programadores a subestimarem o paralelismo potencial. Usando especulação podemos liberar o programador para considerar apenas as dependências principais. O preço a pagar é que, como parte da computação pode ser desfeita, suporte para a reexecução é necessário.
Para validar nossa hipótese, implementamos um sistema dataflow de granularidade grossa com suporte à especulação. Um estudo inicial em uma aplicação artificial que simula um sistema de contas bancárias, com cenários que variam na carga computacional, tamanho de transações, profundidade da especulação e contenção, sugere que há uma grande faixa de valores onde a especulação pode ser bastante efetiva. Em um segundo experimento, paralelizamos uma importante aplicação na área de mineração de dados. Obtivemos desempenho bom em ambos os casos, tendo comparado a segunda aplicação com duas versões OpenMP da mesma.
Parallel programming has become mandatory to fully exploit the potential of modern CPUs. Most often, parallelism is limited by dependencies between instructions or blocks of instructions. In order to address this problem, in optimistic or speculative models of execution, threads can go ahead even if they may possibly be dependent: state is restored and computation is undone if dependencies lead to conflict.
We argue that speculative models of execution fit naturally with the dataflow style of execution. Indeed, one major problem with dataflow execution was that either tasks were too small and fine-grained, and a parallel system could be flooded by huge numbers of tasks; or tasks were too coarse, and dependencies were complex and hard to express, driving programmers to under-estimate parallelism. Using speculative execution liberates the programmer to considerate only the main dependencies, and still allows correct dataflow execution of coarse-grained tasks. The price to pay is that computation may be undone, requiring support for re-execution.
To validate our point, we implemented a speculative coarse-grained dataflow system. An initial study on a bank server artificial application with scenarios that vary on computation load, transaction size, speculation depth and contention suggests that there is a wide range of values where speculation can be very effective. As a second experiment, we parallelized an important application in the area of data-mining. We obtain good speedups, significantly better than two OpenMP implementations.