Master's Research Study
Block-Based Work-Stealing Scheduler Study
An in-progress Master's study of contention-aware work-stealing scheduler design. The work examines how task-queue structure, block-oriented access patterns, steal policies, task granularity, and workload skew affect multicore scheduling behavior.
Study Status
Scope And Research Boundary
The study is intentionally presented as ongoing research. It distinguishes source-paper findings from original implementation and evaluation work.
Reference
Research Context
The study is informed by published systems research on reducing owner/thief interference in work-stealing queues.
BWoS: Formally Verified Block-based Work Stealing for Parallel Processing
The reference paper introduces a block-based work-stealing design and reports its own evaluations. Its results belong to the original authors and are not presented as results of this study.
- This is an independent study informed by BWoS. It does not claim to reproduce BWoS, its formal verification, or its published performance results.
- No benchmark result, speedup claim, or formal-verification claim is published here until the implementation and evaluation are complete.
Question
Research Question And Hypotheses
How do block-oriented task-queue layouts and queue-selection policies affect contention, scheduling overhead, load balance, and throughput under controlled parallel workloads?
Reducing owner and thief access to the same queue region can lower synchronization interference for fine-grained tasks.
Queue-length-aware stealing can improve load distribution under skewed workloads, but its measurement and selection overhead must be evaluated.
The benefit of a scheduling policy depends on task granularity, workload imbalance, core count, and the cost of synchronization.
Method
Experimental Design
The design prioritizes comparable scheduler baselines, reproducible workloads, and recorded environment details before any performance conclusion is made.
- Establish a shared-queue baseline to expose contention under concurrent task submission and consumption.
- Compare conventional per-worker work stealing with a block-oriented queue variant inspired by the paper's separation of owner and thief access.
- Vary task granularity, worker count, workload skew, and task-generation patterns while keeping benchmark inputs reproducible.
- Compare random victim selection with queue-length-aware or probabilistic selection policies only after their measurement overhead is recorded.
- Record experimental configuration, machine characteristics, compiler/runtime version, workload seed, and raw benchmark output for each run.
Measurement
Metrics To Publish
Results will be reported with enough context to distinguish useful scheduler behavior from hardware-, runtime-, or workload-specific effects.
Completed tasks per second and total execution time
Scheduler overhead per task or scheduling operation
Successful, failed, and retried steal attempts
Per-worker idle time and load-distribution fairness
p50 and p95 task wait or scheduling latency where instrumentation permits
CPU utilization and contention-related profiling data where tooling permits
Plan
Research Milestones
The public record will grow from study design to implementation, controlled evaluation, and a written account of findings and limitations.
Stage 1
Define workload generator, baseline scheduler interface, benchmark protocol, and result schema.
Stage 2
Implement and validate shared-queue and conventional work-stealing baselines.
Stage 3
Implement the block-oriented experimental variant with correctness tests and deterministic workload seeds.
Stage 4
Run controlled comparisons, inspect anomalous results, and document limitations before drawing conclusions.
Stage 5
Publish a research note with methodology, observations, limitations, and next hypotheses.