A lot of academic work has been done on using GPUs for general purpose workloads. I would recommend familiarizing yourself with the literature if you have not already. Some work that may be interesting to you is the idea of Persistent Thread Groups [0].

Also, have you considered using Xeon Phi instead of GPUs? Seems like this would be a perfect use case, and it would probably be much easier to work with x86.

[0] - http://cs.olemiss.edu/heroes/persistentThread.pdf