DT-CSR: Dynamic Time CSR

[JoelMathewC]

Note: This will most likely not see the light of day

Dynamic time CSR is a double offset CSR representation. There are 4 arrays, row offset, time offset, column indices, values.

1. The row offset is an array with length equal to num_nodes + 1. The value in each cell indicates the starting index of the time offset array for that node.
2. The time offset is an array of 64 bits each, where first 32 bits represents the time and the last 32 bits represents the index in the column indices matrix where the destination for the given source for the given discrete time exists.

Labeling edges

DT-CSR during forward propagation, will first invoke a label edges kernel which will label edges involved in that particular timestamp. We will need to translate a particular discrete time to a window size with starting ending to indicate all the edges within that particular snapshot. This window's starting and ending indcies are passed to the kernel which then labels the edges. Additionally by using a 2D grid we might be able to increase parallelism

Forward propagation

We modify the kernel to account for the indirection introduced by the time offset array. So for a particular node, loop through time offset to find the starting and ending times. Then use their column indices pointer to obtain the starting and ending indices on the column indices and values array.

Backward propagation

During backward propagation we simply label the DT-CSR and then use the build reverse CSR kernel on the edges of that timestamp. Again this could use a 2D grid. Something important to note here is that the forward prop uses a DT-CSR but backward prop uses a CSR and hence different templates must be used for both those kernel units when generating the code. Additionally we can use node degrees kernel to refer to the updates of every discrete time from the DT-CSR to then update the in-degrees of each node at each timestamp. For out degrees we simply find the difference between the column indices pointed to by the last and first time offset pointers indicating the window size.

Analysis

This will work better than GPMA and be more memory efficient than GPMA. However the slowest step will the build backward CSR, label edges and node updates. Till we find a faster way to implement those, we cannot expect great results with this approach.