%A L.V. Kale
%T Parallel architectures for problem solving
%R Ph.D. thesis
%I Department of Computer Science,
SUNY at Stony Brook, NY 11794
%D December 1985
%X ABSTRACT:
     The problem of exploiting a  large  amount  of  hardware  in
parallel is one of the biggest challenges facing computer science
today.  We investigate the problem of designing  parallel  archi-
tectures  and execution methods for solving large combinatorially
explosive problems.  Such problems typically do not have a  regu-
lar  structure  that can be readily exploited for parallel execu-
tion.  Prolog is chosen as  a  language  to  specify  computation
because  it  is seen as a language that is conceptually simple as
well as amenable to parallel interpretation.  A tree  representa-
tion of Prolog computation called the REDUCE-OR tree is described
as an alternative to the AND-OR tree representation.   A  process
model  based  on  this  representation is developed.  It captures
more parallelism than most other proposed  models.   A  class  of
bus-architectures  is proposed to implement the process model.  A
general model of parallel Prolog systems  is  developed  and  the
proposed  architectures  examined  in  its framework.  One of the
important features of the proposed  architectures  is  that  they
limit  contracting  of  work  to  a  close neighborhood.  Various
Interconnection networks are analyzed and a new  one  called  the
lattice-mesh  is  proposed.   The  lattice-mesh  improves  on the
square grid of buses, while retaining its  linear-area  property.
An  extensive  simulation  framework  has been built.  Results of
some of the experiments conducted on the  simulation  system  are
given.