Matrix-based scans on parallel processors

A system for performing a scan of an input sequence on a parallel processor having a shared register file with N memory banks, comprising a scan kernel configured to perform actions including:

• b) generating a two-dimensional matrix in the shared register file, the matrix having H rows and W data elements of the input sequence in each row;
• c) traversing, in parallel, each of the H rows with a corresponding thread, storing a resulting reduction value corresponding to each row of the H rows in an array in the shared register file;
• d) performing a scan of the array;
• and
• e) performing, in parallel, a scan of each of the rows, and selectively combining a corresponding element of the array in each row scan.

A parallel processor-based system for performing a scan of an input sequence of length B in a parallel processor having a shared register file divided into N memory banks, comprising:

• a) matrix generation means for generating a two-dimensional matrix having a number of rows H and a number of columns W representing elements of the input sequence and a number of columns P representing padding elements;
• b) first matrix traversal means for performing a first traversal of a plurality of rows of the two-dimensional matrix in parallel by a corresponding plurality of threads, each traversal determining a reduction value of the corresponding row;
• and
• c) second matrix traversal means for performing a second traversal of the plurality of rows in parallel by the corresponding plurality of threads, selectively propagating the reduction values to the elements of the plurality of rows.