MAPPING DATALOG PROGRAM EXECUTION TO NETWORKS OF PROCESSORS

The problem of mapping the parallel bottom up execution of Datalog pro grams to an interconnected network of processors is studied. The paral lelization is achieved by using hash functions that partition the set of instantiations for the rules. We first examine this problem in an e nvironment where the number of processors and the interconnection topo logy is known, and communication between program segments residing at nonadjacent processors is not permitted. An algorithm is presented tha t decides whether a given Datalog program can be mapped onto such an a rchitecture. We then relax the constraint on the architecture by allow ing program segments residing at nonadjacent processors to communicate . A theory of approximate mappings is developed, and an algorithm to o btain the closest approximate mapping of a given Datalog program onto a given architecture is presented.