Techniques are disclosed for employing a set of stream processors to greatly accelerate common video encoding and transcoding tasks, with the goal of making these tasks run at a reasonable rate on off-the-shelf hardware. Stream processors are most commonly found in the graphics processing unit (GPU), a commodity piece of computer hardware used to generate images for display. Embodiments of the invention are particularly advantageous to accelerate video encoding and transcoding tasks in which the blocks being processed have dependencies on their neighboring blocks.