Parallel tasks work-stealing schedulers yield near-optimal tasks distribution (i.e. all CPU cores are loaded equally) and have low time, memory and inter-thread synchronizations. The key idea of work-stealing strategy is that when scheduler worker runs out of tasks for execution, it start stealing tasks from the queues of other workers. It’s been shown that double ended queues based on circular arrays are effective in this scenario. They are designed with an assumption that tasks pointer are stored in these data structures, while tasks object reside in heap memory. By modifying tasks queues so that they can hold task objects instead pointers we managed to increase the performance above 2.5 times on CPU bound applications and decrease last-level cache misses 30% compared to Intel TBB and Intel/MIT Cilk work-stealing schedulers.

Original languageEnglish
Pages (from-to)91-102
Number of pages12
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10963
DOIs
StatePublished - 4 Jul 2018
Event18th International Conference on Computational Science and Its Applications, ICCSA 2018 - Melbourne, Australia
Duration: 2 Jul 20185 Jul 2018

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

    Research areas

  • Data structures, Work-stealing deques, Work-stealing scheduler

ID: 35284195