Schedule Analysis of Concurrent Logic Programs

A compilation technique is proposed for concurrent logic programs called schedule analysis. Schedule analysis deduces at compile-time a partial schedule for the processes of a program by partitioning the atoms of each clause into threads. Threads are totally ordered sets of atoms whose relative ordering is determined by a scheduler. Threads reduce scheduler activity and permit a wealth of traditional Prolog optimisations to be applied to the program. A framework for schedule analysis is proposed and this defines a procedure for creating threads. A safety result is presented stating the conditions under which the work of the scheduler can be reduced from ordering processes to ordering threads. Schedule analysis has been integrated into a compiler and implementation has suggested that it can play a central role in compilation. Optimisations which follow from schedule analysis include a reduction in scheduling, the removal of synchronisation checks, the simplification of unification, decreased garbage collection and a reduction in argument copying.