Segmented scan generalizes scan to two dimensions so we can perform scan on particular regions. We can visually think about this as a one dimensional array that has been chopped into regions and the start of each region is flagged. According to this paper (https://research.nvidia.com/sites/default/files/publications/nvr-2008-003.pdf) which has a lot of interesting information on the implementation of segmented scan, even though we can visualize the flags as a vector of integer 1s and 0s marking off region starts, in practice, the flags are just bits in a word.
captainFlint
What are some of the applications of segmented scan (other than sparse matrix multiplication)? Also, in the case sparse matrix multiplication, I'm not sure how it helps. How does it reduce work since it requires compressing rows, storing column values within those rows and the row_starts?
bmperez
If you look at slide 41, @ote has a link a video that shows the use of segmented scan with sparse matrix multiplication. The basic idea is that the naive representation of a sparse matrix (2D array) is extremely space inefficient. Also, it reduces SIMD utilization, as most elements are 0. So, to reduce the memory size of the sparse matrix, it can be represented as a list of lists, or a compressed representation. This is where the segmented scan can become useful, because it is the data format it is designed for.
ArbitorOfTheFountain
This reminds me of the scan across pixels then across circles per pixel in assignment 2.
Segmented scan generalizes scan to two dimensions so we can perform scan on particular regions. We can visually think about this as a one dimensional array that has been chopped into regions and the start of each region is flagged. According to this paper (https://research.nvidia.com/sites/default/files/publications/nvr-2008-003.pdf) which has a lot of interesting information on the implementation of segmented scan, even though we can visualize the flags as a vector of integer 1s and 0s marking off region starts, in practice, the flags are just bits in a word.
What are some of the applications of segmented scan (other than sparse matrix multiplication)? Also, in the case sparse matrix multiplication, I'm not sure how it helps. How does it reduce work since it requires compressing rows, storing column values within those rows and the row_starts?
If you look at slide 41, @ote has a link a video that shows the use of segmented scan with sparse matrix multiplication. The basic idea is that the naive representation of a sparse matrix (2D array) is extremely space inefficient. Also, it reduces SIMD utilization, as most elements are 0. So, to reduce the memory size of the sparse matrix, it can be represented as a list of lists, or a compressed representation. This is where the segmented scan can become useful, because it is the data format it is designed for.
This reminds me of the scan across pixels then across circles per pixel in assignment 2.