Title :
Mapping Datalog program execution to networks of processors
Author :
Ganguly, Sumit ; Silberschatz, Abraham ; Tsur, Shalom
Author_Institution :
Dept. of Comput. Sci., Rutgers Univ., New Brunswick, NJ, USA
fDate :
6/1/1995 12:00:00 AM
Abstract :
The problem of mapping the parallel bottom up execution of Datalog programs to an interconnected network of processors is studied. The parallelization is achieved by using hash functions that partition the set of instantiations for the rules. We first examine this problem in an environment where the number of processors and the interconnection topology is known, and communication between program segments residing at non-adjacent processors is not permitted. An algorithm is presented that decides whether a given Datalog program can be mapped onto such an architecture. We then relax the constraint on the architecture by allowing program segments residing at non-adjacent processors to communicate, A theory of approximate mappings is developed, and an algorithm to obtain the closest approximate mapping of a given Datalog program onto a given architecture is presented
Keywords :
DATALOG; deductive databases; file organisation; logic programming; parallel programming; Datalog program execution mapping; approximate mappings; closest approximate mapping; hash functions; interconnected network of processors; networks of processors; parallel bottom up execution; parallelization; program segments; Computer architecture; Computer science; Context; Databases; High performance computing; Knowledge based systems; Message passing; Network topology; Parallel algorithms; Partitioning algorithms;
Journal_Title :
Knowledge and Data Engineering, IEEE Transactions on