Improvements to the Control Techniques of Sequential Inference Machines——from Instructions to Hardware Organization

Nondeterminism of PROLOG execution requires that a block of control information or a choicepoint for each procedure call be stored when there are other candidate clauses to be used.Whenthe currently selected clause fails,the bindings made by the clause must be undone and the storedchoice point is reactivated,and then another clause of the candidate ones is chosen to run on it.Storing and reactivating choice points and undoing account for the great overhead are required tocontrol PROLOG execution,which is quite different from conventional programs.This paper focuses on the techniques used in Sequential PROLOG Engine(SPE)to reduce theoverhead of control operations.The control instructions of SPE store no more choice points thanthe necessary.Its architecture takes the approaches of analysing the potential parallelism in the con-trol operations and developing a fraction of it due to the cost-effect consideration.The results ofexecuting two sample programs on SPE in the form of hand timings are presented,which favor theapproach.