(4) An Optimization Technique of Efficient Goal Scheduling for KL1 Programs

Conventional implementations of concurrent logic languages, including KLIC, dynamically schedule the execution order of goals, and thus scheduling overhead may cause significant performance degradation if a program consists of, for example, communicating sequential processes. Our research aims to reduce the scheduling overhead by compile-time dependency analysis and run-time scheduling exploiting the analysis result. The compiler statically analyzes the dependency among goals to find threads. The analyzer does not only examine the input/output mode of a variable, but also find out which goal(s) really requires the instantiation of the variable and which goal(s) is really necessary to be scheduled to give a value to it. Thus unless a pair of goals has a real bidirectional data dependency, their execution order is statically determined as a part of a thread without any risk of deadlock. This static scheduling makes it possible the run-time system efficiently executes a thread without scheduling overhead. Moreover, this new scheduling mechanism will drastically reduces GC invocation because it maintains the execution environment of a thread using a stack. As for the scheduling of threads, which are now objects for dynamic scheduling in place of goals, we devised a sophisticated method named reply-first scheduling. Since the compiler knows the real dependency of a variable shared by threads, the variable is annotated with its producer thread on its creation. When its consumer thread is suspended to wait for its value, the run-time system looks up the annotation to give high priority to the producer thread. We have shown the threading and reply-first scheduling complementarily work for efficient execution. That is, the threading accelerate the execution on single processor and reply-first scheduling prevents a thread from executing too long to keep quick inter-processor response.