  There is growing interest in accelerating irregular data-parallel algorithms
on GPUs. These algorithms are typically blocking, so they require fair
scheduling. But GPU programming models (e.g.\ OpenCL) do not mandate fair
scheduling, and GPU schedulers are unfair in practice. Current approaches avoid
this issue by exploiting scheduling quirks of today's GPUs in a manner that
does not allow the GPU to be shared with other workloads (such as graphics
rendering tasks). We propose cooperative kernels, an extension to the
traditional GPU programming model geared towards writing blocking algorithms.
Workgroups of a cooperative kernel are fairly scheduled, and multitasking is
supported via a small set of language extensions through which the kernel and
scheduler cooperate. We describe a prototype implementation of a cooperative
kernel framework implemented in OpenCL 2.0 and evaluate our approach by porting
a set of blocking GPU applications to cooperative kernels and examining their
performance under multitasking. Our prototype exploits no vendor-specific
hardware, driver or compiler support, thus our results provide a lower-bound on
the efficiency with which cooperative kernels can be implemented in practice.
