Hosted with the Supercomputer Software Department RAS Home
Parallel Computing Technologies Third International Conference (PaCT-95) September 12-15, 1995. St.-Petersburg, Russia Proceedings Home PaCTs Prev Contents Next Authors
	Vol. 964

Optimization Scheme on Execution of Logic Program in a Dataflow Environment

by A. R. Hurson, B. U. Jun

Abstract:
We have developed a technique that maps logic programs (database queries) onto a dataflow graph to support static scheduling in a multiprocessor environment [8]. A datafiow graph explicitly shows the execution paths, data dependence, and synchronization points in a query. The scheme attempts to properly group fine grain operations - select and join - into coarser grains as a means to exploit parallelism while minimizing the communication costs. This leads to a higher hardware utilization and performance. In this paper, we expand the scope of our scheme by using a set of heuristic rules to assign processes to available processors more efficiently. This is made possible by analyzing the probability of success of each branch in the logic program. In a logic program, the early scheduling and execution of some branches with higher probability of failure leads to a higher possibility to eliminate many other branches. On the other hand, early execution of some branches with higher probability of success can lead to a higher hardware utilization. The extended scheme has been simulated, and its performance has been compared against the original model and the traditional parallel execution paradigm of the logic program.

Keywords: Software



Classification:
	C.1	processor architectures
	C.2	computer-communication networks
	C.3	special-purpose and application-based systems; microprocessor/microcomputer applications; process control systems; real-time systems; signal processing systems
	C.4	performance of systems; design studies; measurement techniques; modeling techniques; performance attributes; reliability, availability, and serviceability
	D.1	programming techniques
	D.2	software engineering
	D.3	programming languages
	D.4	operating systems
	F.1	computation by abstract devices
	F.2	analysis of algorithms and problem complexity


Source:
A. R. Hurson, B. U. Jun, Optimization Scheme on Execution of Logic Program in a Dataflow Environment.
In V. Malyshkin (ed.), Parallel Computing Technologies: Proceedings of the 3th International Conference, Lect. Notes in Comp. Sci., Vol. 964, Springer, 1995, pp. 204-218

ISSN 0302-9743
ISBN 3-540-60222-4

Search LNCS articles for:
Hurson, A. R. ; Jun, B. U.



Scanned first page:

Designed by the Supercomputer Software Department RAS, 1998