Understanding the Final Value in a Stream Compaction Algorithm

Question

What should happen with the final exclusive scan value in a stream compaction algorithm?

This is an example to pick out all the 'A' characters.

Sequence A:

Input:       A B B A A B B A
Selection:   1 0 0 1 1 0 0 1
Scan:        0 1 1 1 2 3 3 3

0 - A
1 - A
2 - A
3 - A

Sequence B (same except the last value):

Input:       A B B A A B B B
Selection:   1 0 0 1 1 0 0 0
Scan:        0 1 1 1 2 3 3 3

0 - A
1 - A
2 - A
3 - B

Clearly the second example gives the wrong final result based on doing a naive loop through the scan values writing into these addresses.

What am I missing here?

Update:

As I understand the scan algorithm, I would do the equivalent of the following:

for (int i = 0; i < scan.length(); i++)
{
    result[scan[i]] = input[i];
}

In parallel this would involve a scatter instruction.

Answer 1

After an A, you are asuming that there will be at least another A. Therefore, you asume that the sequence ends with an A. If it doesn't, you pick the wrong final letter.

You just need to count the As. Don't start with 1. Start with 0. Only increase this count when you find an A.

Or... Update:

Input:       A B B A A B B A
Selection:   1 0 0 1 1 0 0 1
Scan:        0 1 1 1 2 3 3 3 4
                             ^
0 - A                        |
1 - A                        Four elements
2 - A
3 - A


Input:       A B B A A B B B
Selection:   1 0 0 1 1 0 0 0
Scan:        0 1 1 1 2 3 3 3 3
                             ^
0 - A                        |
1 - A                        Three elements
2 - A