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. |
Year | DOI | Venue |
---|---|---|
1995 | 10.1109/69.390243 | Knowledge and Data Engineering, IEEE Transactions |
Keywords | Field | DocType |
hash function,datalog program,mapping datalog program execution,closest approximate mapping,approximate mapping,program segment,parallel bottom,interconnection topology,non-adjacent processor,bottom up,parallel programming,parallel algorithms,high performance computing,logic programming,datalog,knowledge based systems,network topology,computer architecture,message passing,databases,parallelization,hash functions,computer science | Architecture,Program transformation,Computer science,Top-down and bottom-up design,Parallel computing,Automated theorem proving,Theoretical computer science,Hash function,Logic programming,Partition (number theory),Datalog | Journal |
Volume | Issue | ISSN |
7 | 3 | 1041-4347 |
Citations | PageRank | References |
14 | 14.56 | 11 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Sumit Ganguly | 1 | 813 | 236.01 |
A. Silberschatz | 2 | 5204 | 1988.79 |
Shalom Tsur | 3 | 1540 | 535.93 |