LISP and Symbolic Computation, 7(2/3)231-247
Using Multilisp for Solving Constraint Satisfaction Problems: An Application to Nucleic Acid 3D Structure DeterminationMarc Feeley, D'epartement d'informatique et de recherche op'erationnelle, Universit'e de Montr'eal, Montr'eal (Qu'ebec) Canada, H3C 3J7
Marcel Turcotte, D'epartement d'informatique et de recherche op'erationnelle, Universit'e de Montr'eal, Montr'eal (Qu'ebec) Canada, H3C 3J7
Guy Lapalme, D'epartement d'informatique et de recherche op'erationnelle, Universit'e de Montr'eal, Montr'eal (Qu'ebec) Canada, H3C 3J7
|
Abstract: This paper describes and evaluates a parallel program
for determining the three-dimensional structure of nucleic acids. A
parallel constraint satisfaction algorithm is used to search a
discrete space of shapes. Using two realistic data sets, we compare a
previous sequential version of the program written in Miranda to the
new sequential and parallel versions written in C, Scheme, and
Multilisp, and explain how these new versions were designed to attain
good absolute performance. Critical issues were the performance of
floating-point operations, garbage collection, load balancing, and
contention for shared data. We found that speedup was dependent on the
data set. For the first data set, nearly linear speedup was observed
for up to 64 processors whereas for the second the speedup was limited
to a factor of 16. Keywords: parallel computation, symbolic computation, multilisp, constraint satisfaction, functional programming, applications |
[local copy]
![[picture of journal cover]](../LISP.JPG)