Proceedings of the 17th Conference on Computer Science and Intelligence Systems

DOI: http://dx.doi.org/10.15439/2022F6

Citation: Proceedings of the 17th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 30, pages 333–336 (2022)

Full text

Abstract. 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.

References

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.