A GPU approach to distance geometry in 1D: an implementation in C/CUDA

• Autorzy: Hengeveld Simon B. , Mucherino Antonio

Identyfikatory

DOI

10.15439/2022F6

• Języki publikacji: EN

Abstrakty

EN

We present a GPU implementation in C and CUDA of a matrix-by-vector procedure that is particularly tailored to a special class of distance geometry problems in dimension 1, which we name “paradoxical DGP instances”. This matrix-by-vector reformulation was proposed in previous studies on an optical processor specialized on this kind of computations. Our computational experiments shows that a large speed-up is observed when comparing our GPU implementation against a standard algorithm for distance geometry, called the Branch-and-Prune algorithm. These results confirm that a suitable implementation of the matrix-by-vector procedure in the context of optic computing is very promising. We also remark, however, that the total number of detected solutions grows with the instance size in our implementations, which appears to be an important limitation to the effective implementation of the optical processor.

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2022
• Tom: Vol. 30
• Strony: 333--336
• Opis fizyczny: Bibliogr. 14 poz.

Twórcy

autor

Hengeveld Simon B.

autor

Mucherino Antonio