Latency bounds for concurrent host-thread submissions to a shared OpenCL out-of-order queue

Short answer

No OpenCL version (1.x through 3.0) or widely supported extension provides a guaranteed upper bound on the latency a runtime may add when multiple host threads submit concurrently to a shared queue. The specification guarantees that API calls are thread-safe; it says nothing about their timing, fairness, or how internal serialization scales with thread count. So: the portable strategy is to measure with event profiling, not to rely on a documented bound — and per-thread queues remove your contention on the shared queue object but carry no stronger guarantee.

1. Bounding or measuring the added latency

There is no bounding mechanism, but there is a portable measuring mechanism: event profiling. Create the queue with CL_QUEUE_PROFILING_ENABLE and read timestamps via clGetEventProfilingInfo:

• CL_PROFILING_COMMAND_QUEUED — when the host enqueued the command
• CL_PROFILING_COMMAND_SUBMIT — when the runtime handed it to the device
• CL_PROFILING_COMMAND_START / END — device execution

The QUEUED → SUBMIT delta is exactly where host-side serialization and runtime-internal locking show up. If that delta grows as you add submitting threads while START → END stays flat, the contention is in submission, not execution. Caveats: timestamp resolution and profiling overhead are implementation-defined, and enabling profiling can itself perturb timing on some drivers.

2. Is there a configuration with guaranteed constant submission cost?

No. Internal locking, implicit synchronization, and queue management are explicitly implementation-defined. There is no queue creation flag or extension that promises submission cost independent of thread count. clEnqueueMarkerWithWaitList and clEnqueueBarrierWithWaitList define ordering only — their completion latency relative to concurrent submissions is unspecified, and barriers can force the runtime to drain in-flight work, which worsens tail latency under load.

The defensible portable position is: accept that behavior is implementation-defined, set an empirical latency budget per target driver, and re-validate after any runtime update. A bound observed on Intel Compute Runtime tells you nothing reliable about NVIDIA's or AMD's implementation.

3. Does one queue per thread change the guarantees?

The specification treats all queues identically, so per-thread queues come with no additional latency guarantee. What they do change is the practical picture: if the runtime serializes on the queue object, giving each thread its own queue removes that specific contention point. If the serialization is deeper (per-context or per-device locking inside the driver), per-thread queues won't help. This is directly testable: run your N-thread workload against one shared queue, then against N queues, and compare the QUEUED → SUBMIT deltas.

Suggested verification

1. Create the queue with CL_QUEUE_PROFILING_ENABLE.
2. Submit identical kernels from N = 1, 2, 4, 8 threads, each with its own event.
3. Record QUEUED, SUBMIT, START, END per event; plot SUBMIT − QUEUED against N.
4. Repeat with one queue per thread to localize the contention.
5. Repeat on every target driver before treating any number as a bound.

Practical mitigations

• Batch commands and call clFlush once per batch instead of relying on implicit flushing.
• Minimize event wait-list dependencies that force runtime-side synchronization.
• If the device supports device-side enqueue (CL_QUEUE_DEVICE capability), moving submission off host threads sidesteps the problem entirely — support is uneven, so query the device first.

One note on scope: an out-of-order queue relaxes execution ordering only; it does not relax host-side submission serialization, which is where your observed contention most likely lives. All scaling claims here should be verified on your specific driver versions, since runtime behavior can change between releases.