We present a task-parallel programming model for the GPU. Our task model is robust enough to handle irregular workloads that contain dependencies. We present two dependency-aware scheduling schemes -- static and dynamic -- and analyze their behavior using a synthetic workload. We apply our methods to intra prediction in the H.264 video codec and an N-queens backtracking problem.