We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A Novel Algorithm and its Hardware Support for the Run-Time Detection of And-Parallelism.
- Authors
Marsh, Andy
- Abstract
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.
- Publication
Parallel Processing Letters, 1998, Vol 8, Issue 4, p489
- ISSN
0129-6264
- Publication type
Article
- DOI
10.1142/S0129626498000481