ATOM-BY-ATOM SEARCHING USING MASSIVE PARALLELISM - IMPLEMENTATION OF THE ULLMANN SUBGRAPH ISOMORPHISM ALGORITHM ON THE DISTRIBUTED ARRAY PROCESSOR

The AMT Distributed Array Processor (DAP) is a massively parallel SIMD processor array that contains thousands of processing elements. This paper describes the implementation of atom-by-atom searching on the DAP using Ullmann's subgraph isomorphism algorithm. Two alternative algorithms are discussed. The first of these allows rapid processing of a single structure, the adjacency matrix of which is distributed across the array of processing elements. The second is much slower in execution for a single molecule but allows very large numbers of structures to be searched in parallel. With current codes, the first algorithm is faster and out-performs a large mainframe; however, developments of the second algorithm are expected to make this the faster. Combined algorithms are also described that utilize both approaches.