Parallel Prefix Sum

Design a hardware module for the Parallel Prefix Sum problem.

Given an input sequence array, output the inclusive prefix sum at every position.

For output index i, produce the sum of array[0] + array[1] + ... + array[i].

Hardware I/O Encoding

• array is a one-dimensional stream of unsigned 16-bit integers
• the output is a one-dimensional stream of unsigned 24-bit integers
• each output element is the inclusive running sum up to the matching input position
• the output stream length matches the input stream length

Examples

Example 1

• input array = [1, 2, 3, 4]
• output: [1, 3, 6, 10]

Example 2

• input array = [5]
• output: [5]

Example 3

• input array = [2, 0, 7]
• output: [2, 2, 9]