Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2506.19379 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916809370763264 |
|---|---|
| author | Paul, Subrata Das, Sukanta Sikdar, Biplab K |
| author_facet | Paul, Subrata Das, Sukanta Sikdar, Biplab K |
| contents | This work proposes a computing model to reduce the workload of CPU. It relies on the data intensive computation in memory, where the data reside, and effectively realizes an in-memory computing (IMC) platform. Each memory word, with additional logic, acts as a tiny processing element which forms the node of a Cayley tree. The Cayley tree in turn defines the framework for solving the data intensive computational problems. It finds the solutions for in-memory searching, computing the max (min) in-memory and in-memory sorting while reducing the involvement of CPU. The worst case time complexities of the IMC based solutions for in-memory searching and computing max (min) in-memory are $\mathcal{O}\log{n}$. Such solutions are independent of the order of elements in the list. The worst case time complexity of in-memory sorting, on the other hand, is $\mathcal{O}(n\log{n})$. Two types of hardware implementations of the IMC platform are proposed. One is based on the existing/conventional memory architecture, and the other one is on a newly defined memory architecture. The solutions are further implemented in FPGA platform to prove the effectiveness of the IMC architecture while comparing with the state-of-the art designs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_19379 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | In-Memory Sorting-Searching with Cayley Tree Paul, Subrata Das, Sukanta Sikdar, Biplab K Formal Languages and Automata Theory Hardware Architecture This work proposes a computing model to reduce the workload of CPU. It relies on the data intensive computation in memory, where the data reside, and effectively realizes an in-memory computing (IMC) platform. Each memory word, with additional logic, acts as a tiny processing element which forms the node of a Cayley tree. The Cayley tree in turn defines the framework for solving the data intensive computational problems. It finds the solutions for in-memory searching, computing the max (min) in-memory and in-memory sorting while reducing the involvement of CPU. The worst case time complexities of the IMC based solutions for in-memory searching and computing max (min) in-memory are $\mathcal{O}\log{n}$. Such solutions are independent of the order of elements in the list. The worst case time complexity of in-memory sorting, on the other hand, is $\mathcal{O}(n\log{n})$. Two types of hardware implementations of the IMC platform are proposed. One is based on the existing/conventional memory architecture, and the other one is on a newly defined memory architecture. The solutions are further implemented in FPGA platform to prove the effectiveness of the IMC architecture while comparing with the state-of-the art designs. |
| title | In-Memory Sorting-Searching with Cayley Tree |
| topic | Formal Languages and Automata Theory Hardware Architecture |
| url | https://arxiv.org/abs/2506.19379 |