dynarrc
A linked-list allocator implemented as a dynamic array instead of pointers in C. It gives you a linked-list like interface with which you can add/remove nodes. However, internally, nodes are stored in a dynamic array and instead of a next-pointer for a list-node we have next-index.
Motivation
Consider the following scenario:
- You have a linked-list data structure for a regular C program
- You do some computation on these lists, probably add/delete/modify nodes
- Now you want to copy that list to GPU memory and perform computation on the lists
- You may add/delete/modify nodes in GPU memory
- You need to bring your data back to the CPU memory and resume computation
Because each linked-list node contain a pointer (memory-reference) to the next node, we have a problem. Nodes created/modified in CPU memory will refer to CPU-memory addresses, but these addresses are meaningless when you are in GPU memory because you (most probably) do not have any control over the location where your copied-data are placed in GPU memory.
The project at hand can be used to circumvent this problem. Because nodes are allocated in dynamic array, nodes are linked through indexes not pointers, and you can safely copy your data back-and-forth between CPU memory and GPU memory.
Where to Use
- If you have an algorithm that operates on a linked list but you (may) need to do it in GPU, you can use this project and write your code from scratch.
- If you have an existing program that uses a linked list but you plan to port it to GPU, it is easy to replace your existing linked-list data structure with the current data structure because we give a linked-list-like interface.
This project, in a more specific form, has already been used to port an existing CPU program was ported to GPU. The program used linked-lists to simulate water distribution networks.
Limitations
- Although dynamic, arrays are preallocated and hence some memory will remain unused.
- For completeness, we will add a GPU companion in future.
Contact
I will be excited to answer your questions about this project. Email me here: saad dot quader at uconn dot edu