Study of Scheduling in Programming Languages of Multi-Core Processor

چکیده مقاله

The paper "Study of Scheduling in Programming Languages of Multi-Core Processor," published in the Journal of Computing and Applied Informatics in 2018, investigates the impact of different scheduling techniques on the performance of parallel programming languages for multi-core processors. Authored by Mina Hosseini-Rad, Majid Abdolrazzagh-Nezhad, and Seyyed-Mohammad Javadi-Moghaddam, the study emphasizes that as multi-core architectures have become mainstream, the shift from serial to parallel programming models has introduced significant challenges in achieving high efficiency. The choice of programming language and its underlying scheduling method plays a crucial role in optimizing performance, load balancing, and resource utilization in such environments.

The research provides a comprehensive overview of several prominent parallel programming frameworks, including PThread, Skandium, OpenMP, Cilk++, TBB, and Multi-BSP. Each of these implements distinct scheduling strategies, which are analyzed in terms of their queue structures and task management mechanisms. The study categorizes scheduling queues into three types: central queues, private queues, and hierarchical queues. Central queues, as used in PThread and Skandium, often lead to contention and synchronization overhead due to concurrent access. Private queues, employed by Cilk++ and OpenMP, reduce contention by assigning each core its own queue and utilizing work-stealing to balance loads. Hierarchical queues, such as those in TBB and Multi-BSP, introduce more complex structures aimed at optimizing memory locality but may incur additional overhead.

To evaluate the practical efficiency of these scheduling approaches, the authors conducted experiments using two classic sorting algorithms—Merge-Sort and Quick-Sort—executed on an Intel Core i7 quad-core processor. The results revealed that languages using private queues with work-stealing, notably Cilk++ and OpenMP, consistently outperformed those relying on central or hierarchical queues. For Merge-Sort, which generates a balanced task tree, both Cilk++ and OpenMP demonstrated superior speedup and lower execution times compared to TBB and PThread. In the case of Quick-Sort, which produces an imbalanced task dependency tree, the work-stealing mechanism in Cilk++ and OpenMP effectively mitigated load imbalances, whereas TBB's hierarchical queue structure showed reduced efficiency due to its complexity and overhead.

The key achievement of this paper lies in its empirical demonstration that scheduling strategies based on private queues with work-stealing are generally more effective for current multi-core processors than those using central or hierarchical queues. The study also highlights the importance of selecting a programming model that aligns with the algorithmic characteristics of the application—for instance, work-stealing proves particularly beneficial for irregular and recursive algorithms like Quick-Sort. These findings provide valuable guidance for developers and researchers in choosing appropriate parallel programming tools to maximize performance on modern multi-core systems.

In conclusion, the paper successfully bridges theoretical scheduling concepts with practical performance evaluation, offering clear insights into the trade-offs between different parallel programming paradigms. The positive outcomes underscore the efficiency of lightweight, decentralized scheduling mechanisms in reducing contention and improving load balance. For future work, the authors suggest exploring hierarchical scheduling models in the context of more complex cache architectures or through simulation, which could further optimize performance as multi-core processors continue to evolve in complexity and scale.