Work Stealing with Parallelism Feedback

摘要: We present a randomized work-stealing thread scheduler for fork-join multithreaded jobs that provides continual parallelism feedback to the job in form of processor requests. Our A-STEAL algorithm is appropriate large parallel servers where many share common multiprocessor resource and which number processors available particular may vary during job’s execution. Assuming never allots more than requested by scheduler, guarantees completes near-optimal time while utilizing at least constant fraction allotted processors. analysis models as scheduler’s adversary, challenging be robust system environment administrative policies. For example, can make huge exactly when has little use them. To analyze performance our adaptive under this stringent adversarial assumption, we introduce new technique called “trim analysis,” allows us prove performs poorly on most small steps, exhibiting behavior vast majority. precise, suppose work T1 critical-path length T∞. On machine with P processors, expected O(T1/P +T∞+ L lgP ) scheduling quantum denotes O(T∞ +L )-trimmed availability. This quantity average availability over all but + steps having highest When dominates trimmed available, is, ≪ T1/T∞, achieves nearly perfect linear speedup. Conversely, mean research was supported part Singapore-MIT Alliance NSF Grants ACI-0324974 CNS-0305606. Yuxiong He Visiting Scholar MIT CSAIL Ph.D. candidate National University Singapore. parallelism, asymptotic running its critical path. measured simulated using synthetic workloads. sufficient experiments indicate almost speedup across variety profiles. In these experiments, typically wasted less 20% cycles job. compared ABP algorithm, an workstealing developed Arora, Blumofe, Plaxton does not employ feedback. moderateto heavy-loaded machines predetermined profiles, completed twice quickly, despite being same or fewer every step, wasting only 10% ABP.