2022, issue 2, p. 58-66
Received 14.09.2022; Revised 22.09.2022; Accepted 29.09.2022
Published 30.09.2022; First Online 05.10.2022
https://doi.org/10.34229/2707-451X.22.2.6
Previous | FULL TEXT (in Ukrainian) | Next
Parallel Implementation of Sparse Distributed Memory for Semantic Storage
Ruslan Vdovychenko *
, Vadim Tulchinsky
V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
Introduction. Sparse Distributed Memory (SDM) and Binary Sparse Distributed Representations (Binary Sparse Distributed Representations, BSDR), as two phenomenological approaches to biological memory modelling, have many similarities. The idea of their integration into a hybrid semantic storage model with SDM as a low-level cleaning memory (brain cells) for BSDR, which is used as an encoder of high-level symbolic information, is natural. A hybrid semantic store should be able to store holistic data (for example, structures of interconnected and sequential key-value pairs) in a neural network. A similar design has been proposed several times since the 1990s. However, the previously proposed models are impractical due to insufficient scalability and/or low storage density. The gap between SDM and BSDR can be bridged by the results of a third theory related to sparse signals: Compressive Sensing or Sampling (CS). In this article, we focus on the highly efficient parallel implementation of the CS-SDM hybrid memory model for graphics processing units on the NVIDIA CUDA platform, analyze the computational complexity of CS-SDM operations for the case of parallel implementation, and offer optimization techniques for conducting experiments with big sequential batches of vectors.
The purpose of the paper is to propose an efficient software implementation of sparse-distributed memory for preserving semantics on modern graphics processing units.
Results. Parallel algorithms for CS-SDM operations are proposed, their computational complexity is estimated, and a parallel implementation of the CS-SDM hybrid semantic store is given. Optimization of vector reconstruction for experiments with sequential data batches is proposed.
Conclusions. The obtained results show that the design of CS-SDM is naturally parallel and that its algorithms are by design compatible with the architecture of systems with massive parallelism. The conducted experiments showed high performance of the developed implementation of the SDM memory block.
Keywords: GPU, CUDA, neural network, Sparse Distributed Memory, associative memory, Compressive Sensing.
Cite as: Vdovychenko R., Tulchinsky V. Parallel Implementation of Sparse Distributed Memory for Semantic Storage. Cybernetics and Computer Technologies. 2022. 2. P. 58–66. (in Ukrainian) https://doi.org/10.34229/2707-451X.22.2.6
References
1. Kanerva P. Sparse Distributed Memory. Cambridge, MA: MIT Press, 1988. 180 p. https://isbnsearch.org/isbn/9780262111324
2. Jaeckel L.A. An Alternative Design for a Sparse Distributed Memory : Report RIACS TR 89.28 / Research Institute for Advanced Computer Science, NASA Ames Research Center. 1989. https://ntrs.nasa.gov/citations/19920001073
3. Albus J.S. A
theory of cerebellar functions. Mathematical Biosciences. 1971. 10
(1-2). P. 25–61.
https://doi.org/10.1016/0025-5564(71)90051-4
4. Smith D.J.,
Forrest S., Perelson A.S. Immunological memory is associative. Artificial
Immune Systems and Their Applications / Dasgupta, D. (eds). Berlin,
Heidelberg: Springer, 1999. P. 105–112.
https://doi.org/10.1007/978-3-642-59901-9_6
5. Sjödin G. The Sparchunk Code: A method to build higher-level structures in a sparsely encoded SDM. IJCNN/WCCI’98 : Proceedings of IEEE International Joint Conference on Neural Networks. London: Springer, 1998. P. 50–58. https://doi.org/10.1109/IJCNN.1998.685982
6. Rachkovskij D.A., Kussul E.M. Binding and normalization of binary sparse distributed representations by context-dependent thinning. Neural Comput. 2001. 13 (2). P. 411–452. https://doi.org/10.1162/089976601300014592
7. Schlegel K., Neubert P., Protzel, P. A comparison of vector symbolic architectures. Artif Intell Rev. 2022. 55. P. 4523–4555. https://doi.org/10.1007/s10462-021-10110-3
8. Gayler R.W. Vector symbolic architectures are a viable alternative for Jackendoff's challenges. Behavioral and Brain Sciences. 2006. 29 (1). P. 78–79. https://doi.org/10.1017/S0140525X06309028
9. Candès E.J., Romberg J., Tao T. Stable signal recovery from incomplete and inaccurate measurements. Comm. Pure Appl. Math. 2006. 59 (8). P. 1207–1223. https://doi.org/10.1002/cpa.20124
10. Candès E.J., Wakin M.B. An introduction to compressive sampling. IEEE Signal Process. Mag. 2008. 25 (2). P. 21–30. https://doi.org/10.1109/MSP.2007.914731
11. Vdovychenko R., Tulchinsky V. Increasing the Semantic Storage Density of Sparse Distributed Memory. Cybernetics and Systems Analysis. 2022. 58 (3). P. 331–342. https://doi.org/10.1007/s10559-022-00465-y
12. Vdovychenko R., Tulchinsky V. Sparse Distributed Memory for Binary Sparse Distributed Representations. ACM International Conference Proceeding Series (ICMLT’2022: 7th International Conference on Machine Learning Technologies). 2022. P. 266–270. https://doi.org/10.1145/3529399.3529441
13. Needell D., Tropp J.A. CoSaMP: Iterative signal recovery from incomplete and inaccurate samples. Applied and Computational Harmonic Analysis. 2008. 26 (3). P. 301–321. https://doi.org/10.1016/j.acha.2008.07.002
14. Dantzig G.B.
Linear programming and extensions. Princeton, NJ: Princeton University Press.
1963. 656 р.
https://doi.org/10.7249/R366
15. Virmaux A.
CoSaMP implementation in Python/NumPy. 2017.
https://github.com/avirmaux/CoSaMP/blob/master/cosamp.ipynb (accessed: 14.09.2022).
16. Virtanen P., Gommers R., Oliphant T.E. et al. SciPy 1.0: fundamental algorithms for scientific computing in Python. Nature Methods. 2020. 17 (3). P. 261–272. https://doi.org/10.1038/s41592-019-0686-2
17. Bland R.G. New finite pivoting rules for the simplex method. Mathematics of Operations Research. 1977. 2 (2). P. 103–107. https://doi.org/10.1287/moor.2.2.103
18. Andersen E.D., Andersen K.D. The Mosek Interior Point Optimizer for Linear Programming: An Implementation of the Homogeneous Algorithm. High Performance Optimization, Applied Optimization, / Frenk, H., Roos, K., Terlaky, T., Zhang, S. (eds). Boston, MA: Springer, 2000. 33. P. 197–232. https://doi.org/10.1007/978-1-4757-3216-0_8
19. Huangfu Q., Hall J.A. Parallelizing the dual revised simplex method. Mathematical Programming Computation. 2018. 10 (1). P. 119–142. https://doi.org/10.1007/s12532-017-0130-5
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | FULL TEXT (in Ukrainian) | Next