{"id":526,"date":"2012-04-05T17:07:57","date_gmt":"2012-04-05T21:07:57","guid":{"rendered":"http:\/\/gameangst.com\/?p=526"},"modified":"2012-04-05T17:07:57","modified_gmt":"2012-04-05T21:07:57","slug":"scalable-concurrency-in-despair-engine","status":"publish","type":"post","link":"http:\/\/gameangst.com\/?p=526","title":{"rendered":"Scalable Concurrency in Despair Engine"},"content":{"rendered":"

In my last article I promised a follow-up description of the memory allocation system that I wrote for Despair Engine<\/a> during the development of F.E.A.R. 3. \u00a0Before I get to that, however, I’ve been inspired by Charles Bloom<\/a>‘s recent posts on the job queue system<\/a> that is apparently part of RAD Game Tools<\/a>‘ Oodle, and I thought it might be interesting to describe the current job system and thread layout in Despair.<\/p>\n

The “concurrency manager” in Despair Engine consists of worker threads and job queues. \u00a0By default there is one pool of worker threads that share a single job queue, referred to as public workers, and some number of additional worker threads, each with its own job queue, referred to as private workers.<\/p>\n

The job queues and their worker threads are relatively simple constructs. \u00a0Jobs can be added to a queue from any thread and, when jobs are added, they create futures<\/a> which can be used to wait on the job’s completion. \u00a0A job queue doesn’t directly support any concept of dependencies between jobs or affinities to limit which worker threads a job can run on.<\/p>\n

Jobs are fetched by worker threads in strictly FIFO order, but with multiple worker threads servicing a single queue, that doesn’t provide many guarantees on the order in which jobs are processed. \u00a0For example, jobs A<\/strong><\/em> and B<\/strong><\/em>, enqueued in that order, may be fetched consecutively by worker threads 1<\/strong>\u00a0and 2<\/strong>. \u00a0Because these tasks are asynchronous, worker thread 2<\/strong> might actually manage to start and finish processing job B<\/strong><\/em> before worker thread 1<\/strong> has done any meaningful work on job A<\/strong><\/em>.<\/p>\n

What this means in practice is that any job added to the public worker queue must be able to be processed on any public worker thread and concurrently with any other job in the queue. \u00a0If a job really needs to enforce a dependency with other jobs, it can do so by either waiting on the futures of the jobs it is dependent on or by creating the jobs that are dependent on it at the end of its execution. \u00a0Combinations of these techniques can be used to create almost arbitrarily complex job behavior, but such job interactions inhibit maximum parallelism so we try to avoid them in our engine.<\/p>\n

Public worker threads are mostly used by data-parallel<\/a> systems that divide their work into some multiple of the number of public workers, enqueue jobs for each worker, and then, at some later point in the frame, wait on all the jobs’ futures. \u00a0Examples of systems like this are animation, cloth simulation, physics, effects, and rendering. \u00a0Although all of the users of the public job queue try to provide as much time as possible between adding work to the queue and blocking on its completion, work in the public job queue is considered high-priority and latency intolerant.<\/p>\n

Systems that have work that can be processed asynchronously, but doesn’t meet the requirements of the public job queue, create private job queues. \u00a0The primary reason for using a private job queue is that the work is long but latency tolerant, and we don’t want it delaying the latency intolerant work in the public job queue.<\/p>\n

In Fracture, terrain deformation was processed in a private worker thread, consuming as much as 15 ms a frame but at low priority.<\/p>\n