A METHODOLOGY FOR GRANULARITY-BASED CONTROL OF PARALLELISM IN LOGIC PROGRAMS

Several types of parallelism can be exploited in logic programs while preserving correctness and efficiency, i.e. ensuring that the parallel execution obtains the same results as the sequential one and the amou nt of work performed is not greater. However, such results do not take into account a number of overheads which appear in practice, such as process creation and scheduling, which can induce a slow-down, or, at least, limit speedup, if they are not controlled in some way. This pap er describes a methodology whereby the granularity of parallel tasks, i.e. the work available under them, is efficiently estimated and used to limit parallelism so that the effect of such overheads is controlle d. The run-time overhead associated with the approach is usually quite small, since as much work is done at compile time as possible. Also, a number of run-time optimizations are proposed. Moreover, a static an alysis of the overhead associated with the granularity control process is performed in order to decide its convenience. The performance impr ovements resulting from the incorporation of grain size control are sh own to be quite good, specially for systems with medium to large paral lel execution overheads. (C) 1996 Academic Press Limited