How (and whether) to parallelize a three-stage 2D graphics algorithm, for example on the GPU?

I have a 2D graphics algorithm I'd like to speed up. The algorithm converts an input image to a pseudo-colored output image in which pixels are colored according to their histograms. It operates on an RGB bitmap with a bit depth of 8 bits per color channel, and consists of these three steps:

1. Compute the histogram of each color channel. The result is three arrays, each consisting of 256 integers. For example in the red channel's histogram, the first element contains the count of pixels with a red value of zero, the second element contains the count of pixels with a red value of one, and so on up to 255.
2. Normalize the three histograms. For each histogram array, first find the histogram's maximum value, and then scale all the values so that the maximum value is 255. For a given channel, arrBin[i] = round(double(arrBin[i]) / nHistMax * 255)
3. For each pixel, for each color channel, use the color value as an index into the corresponding histogram, and use the normalized histogram value as the new color value.

The second stage has a negligible effect on performance because it operates on only 3 * 256 = 768 integers regardless of image size. It's the other two stages that are the problem. A single-threaded implementation can take on the order of a quarter of a second on a typical CPU. In theory stages one and three are both amenable to parallelization, however there are some complications.

1. The three stages must be completed in order, in other words stage two can't begin until stage one is complete, and stage three can't begin until stage two is complete. How is this handled on a GPU?
2. In stage one, while all pixels could in theory be processed in parallel, they would compete for RMW access to the output histograms. On a CPU this could managed with an interlocked add instruction. Is there some equivalent to this on a GPU?

Re the second problem, another approach that might work on a CPU would be to divide the input image into separate bands, one for each core, compute each band's histograms in parallel, and then sum the resulting per-band histograms into full-image histograms. This would avoid contention and the need for interlocked adds or serialization. However this only makes sense for a relatively small number of cores. I doubt such an approach is workable for the much larger number of cores found on GPUs.

Another issue is the time required to load the input image into GPU memory, and then retrieve the output image back into CPU memory. In certain applications, the operation might need to be performed repeatedly on the same input image (for example because parameters are changing), in which case the image could remain in GPU memory, incurring the load penalty only initially. But there's probably no avoiding the cost of retrieving the output image, except perhaps in a video-processing plugin environment where the entire process is occurring in GPU space.

Additionally, what framework would make the most sense? I'm using Visual Studio 2012. Do I have to use HSL? Could AMP or CUDA help?

Caveat: I have coded many CPU multi-threaded applications, but I'm inexperienced with GPUs. I figure the band approach described above could give an order of magnitude improvement at best, using 8 or perhaps 16 cores, but in theory a GPU could deliver two orders of magnitude improvement no?