A Novel Algorithm and its Hardware Support for the Run-Time Detection of And-Parallelism
Andy Marsh · Parallel Processing Letters · 1998
It is well established in query evaluation literature that pushing constants (i.e. bound variable values) through selections, enables the problem specific information to be used effectively and is essential for constraining a query's search space. This amounts to a decision on how information gained about bindings in some body atom in a clause is to be used in evaluating other atoms in the clause. This binding passing algorithm is referred to in deductive database literature as a 'sideways information passing strategy' (sip). A sip that is determined at compile-time for uncovered definite clauses can only devise the most general sip and therefore may be sub-optimal at run-time. A sip determined at run-time is however inefficient - overheads outweigh advantages. To overcome these dilemmas a dynamic sip has been devised that uses a hybrid compile-time analysis, based on abstract interpretation, combined with a run-time verification. The pragmatics of the run-time verification is presented in this paper along with its novel hardware support providing a uniform performance of 155ns independent of the number of body atoms to detect an initial processing order for the independent atoms.