5.2Alternative Ways of Expressing Parallelism

The SAXPY-shaped grid-of-threads model fits regular parallelism like a glove — and everything else awkwardly. Three research threads loosen the fit.

Fine-grained hardware worklists

Kim & Batten give each SIMT core a hardware worklisthardware worklistPer-lane on-chip queues with greedy/needy rebalancing (and inter-core sorting) for data-driven irregular parallelism.Glossary → — per-lane SRAM queues with push/pull ISA instructions — so irregular, data-driven applications get the work-efficiency of dynamic task generation without the memory contention and load imbalance of software worklists:

lane 0: [t3 t7 t9 t12 t15]   ← greedy (5 tasks)
lane 1: [t4]                 ← needy (1)
lane 2: [t5 t8 t11]          (3)
lane 3: []                   ← needy (0)

Nested parallel patterns

For nested patterns (a map over reduces, filters over maps…), where you expose the parallelism is a real decision: Lee et al. generalize to a 1D mapping (outer loop → threads), a block/thread mapping (outer → CTAs, inner → threads), and a warp-based mapping (outer → warps, inner → lanes). Their compiler assigns each nest level a dimension, then tunes per-dimension span/splitspan / splitNested-parallel-pattern knobs: how many collection elements one thread handles; split(n) shards span(all) across n threads + a combiner kernel.Glossary →: span(1) = one element per thread (max parallelism); span(all) = one thread does the whole dimension — forced when an inner size is runtime-dynamic or the pattern synchronizes (reduce); split(n) = shard span(all) across n threads plus a combiner kernel to merge. A scored search (hard constraints = correctness, e.g. max threads/block; soft constraints = performance, e.g. sequential accesses on the x-dimension for coalescing) sweeps the whole space in seconds — the exponential’s base is small and nests are shallow — landing within reach of expert-tuned code, with pre-allocation and shared-memory prefetch thrown in.

Dynamic parallelism, done right

CDP lets kernels launch kernels — and Wang & Yalamanchili measured why that disappointed on Kepler: applications spawn hordes of ~40-thread kernels, each dragging launch-configuration storage, each parked in its own stream to reach Hyper-Q’s 32 queues. Utilization crumbles. DTBLDTBLDynamic thread block launch: aggregate device-launched blocks onto running kernels of the same code, fixing CDP's tiny-kernel overheads.Glossary → (Wang et al.) keeps the programming model but changes the unit: device-launched work becomes thread blocks aggregated onto an already-running kernel with the same code (a linked list of pending blocks feeds the hardware scheduler) — 1.4× over CDP, 1.2× over highly tuned CUDA that avoids CDP altogether. A follow-up places child blocks on the parent’s SM (data locality!) while watching load balance: another +27% over round-robin.