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

• Autorzy: Hengeveld, Simon B. , Mucherino, A.
• Konferencja: Federated Conference on Computer Science and Information Systems (17 ; 04-07.09.2022 ; Sofia, Bulgaria)
• 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.

Słowa kluczowe

PL

geometria; kontekst; informatyka; jednostka przetwarzania grafiki; transformacja; teoria złożoności

EN

geometry; context; computer science; graphics processing unit; transform; optical computing; complexity theory

• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2022
• Tom: Vol. 30
• Strony: 333--336
• Opis fizyczny: Bibliogr. 14 poz., tab., wz.

Twórcy

autor

Hengeveld, Simon B.

• IRISA, University of Rennes 1, Rennes, France,

autor

Mucherino, A.

• IRISA, University of Rennes 1, Rennes, France,

Bibliografia

• 1. N.M. Freris, S.R. Graham, P.R. Kumar, Fundamental Limits on Synchronizing Clocks Over Networks, IEEE Transactions on Automatic Control 56(6), 1352–1364, 2010.
• 2. S.B. Hengeveld, N. Rubiano da Silva, D.S. Gonçalves, P.H. Souto Ribeiro, A. Mucherino, An Optical Processor for Matrix-by-Vector Multiplication: an Application to the Distance Geometry Problem in 1D, Journal of Optics 24(1), 015701, 2022.
• 3. K. Isupov, Multiple-Precision Sparse MatrixVector Multiplication on GPUs, Journal of Computational Science 61, 101609, 2022.
• 4. L. Liberti, C. Lavor, N. Maculan, A Branch-and-Prune Algorithm for the Molecular Distance Geometry Problem, International Transactions in Operational Research 15, 1–17, 2008.
• 5. L. Liberti, C. Lavor, N. Maculan, A. Mucherino, Euclidean Distance Geometry and Applications, SIAM Review 56(1), 3–69, 2014.
• 6. L. Liberti, B. Masson, J. Lee, C. Lavor, A. Mucherino, On the Number of Realizations of Certain Henneberg Graphs arising in Protein Conformation, Discrete Applied Mathematics 165, 213–232, 2014.
• 7. A. Monakov, A. Lokhmotov, A. Avetisyan, Automatically Tuning Sparse Matrix-Vector Multiplication for GPU Architectures, In: “High Performance Embedded Architectures and Compilers”, Y.N. Patt, P. Foglia, E. Duesterwald, P. Faraboschi, X. Martorell (Eds.), Lecture Notes in Computer Science 5952, Springer, 111–125, 2010.
• 8. A. Mucherino, Optimal Discretization Orders for Distance Geometry: a Theoretical Standpoint, Lecture Notes in Computer Science 9374, Proceedings of the 10th International Conference on Large-Scale Scientific Computations (LSSC15), Sozopol, Bulgaria, 234–242, 2015.
• 9. A. Mucherino, On the Exact Solution of the Distance Geometry with Interval Distances in Dimension 1. In: “Recent Advances in Computational Optimization”, S. Fidanova (Ed.), Studies in Computational Intelligence 717, 123–134, 2018.
• 10. J. Saxe, Embeddability of Weighted Graphs in k-Space is Strongly NP-hard, Proceedings of 17th Allerton Conference in Communications, Control and Computing, 480–489, 1979.
• 11. A. Singer, Angular Synchronization by Eigenvectors and Semidefinite Programming, Applied and Computational Harmonic Analysis 30(1), 20–36, 2011.
• 12. P. Verissimo, M. Raynal, Time in Distributed System Models and Algorithms. In: “Advances in Distributed Systems, Advanced Distributed Computing: From Algorithms to Systems”, S.K. Shrivastava, S. Krakowiak (Eds.), Springer, 1–32, 1999.
• 13. V. Volkov, J.W. Demmel, Benchmarking GPUs to Tune Dense Linear Algebra, IEEE Conference Proceedings, ACM/IEEE conference on Supercomputing (SC08), 11 pages, 2008.
• 14. Y-C. Wu, Q. Chaudhari, E. Serpedin, Clock Synchronization of Wireless Sensor Networks, IEEE Signal Processing Magazine 28(1), 124–138, 2011.

Uwagi

1. This work is partially supported by the international project MULTIBIOSTRUCT funded by the ANR French funding agency (ANR-19-CE45-0019).

2. Short article

3. Track 6: 15th International Workshop on Computational Optimization

4. Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023).

Identyfikatory

DOI

10.15439/2022F6