ADVANCED SCHEDULER FOR COOPERATIVE EXECUTION OF THREADS ON MULTI-CORE SYSTEM

Three architectures of the cooperative thread scheduler in a multithreaded application that is executed on a multi-core system are considered. Architecture A0 is based on the synchronization and scheduling facilities, which are provided by the operating system. Architecture A1 introduces a new synchronization primitive and a single queue of the blocked threads in the scheduler, which reduces the interaction activity between the threads and operating system, and significantly speed up the processes of blocking and unblocking the threads. Architecture A2 replaces the single queue of blocked threads with dedicated queues, one for each of the synchronizing primitives, extends the number of internal states of the primitive, reduces the inter- dependence of the scheduling threads, and further significantly speeds up the processes of blocking and unblocking the threads. All scheduler architectures are implemented on Windows operating systems and based on the User Mode Scheduling. Important experimental results are obtained for multithreaded applications that implement two blocked parallel algorithms of solving the linear algebraic equation systems by the Gaussian elimination. The algorithms differ in the way of the data distribution among threads and by the thread synchronization models. The number of threads varied from 32 to 7936. Architecture A1 shows the acceleration of up to 8.65% and the architecture A2 shows the acceleration of up to 11.98% compared to A0 architecture for the blocked parallel algorithms computing the triangular form and performing the back substitution. On the back substitution stage of the algorithms, architecture A1 gives the acceleration of up to 125%, and architecture A2 gives the acceleration of up to 413% compared to architecture A0. The experiments clearly show that the proposed architectures, A1 and A2 outperform A0 depending on the number of thread blocking and unblocking operations, which happen during the execution of multi-threaded applications. The conducted computational experiments demonstrate the improvement of parameters of multithreaded applications on a heterogeneous multi-core system due the proposed advanced versions of the thread scheduler.

1. Rajagopalan, M. Thread Scheduling for Multi-Core Platforms / M. Rajagopalan, B. T. Lewis, and T. A. Anderson, // HOTOS’07 Proc. of the 11th USENIX workshop on Hot topics in operating systems, San Diego, CA, 2007.

2. Yun, H. Deterministic Real-time Thread Scheduling / H. Yun, C. Kim, and L. Sha // preprint arXiv: 1104.2110, 2011.

3. Shelepov, D. Scheduling on heterogeneous multicore processors using architectural signatures / D. Shelepov, and A. Fedorova // Proc. Workshop on the Interaction between Operating Systems and Computer Architecture, in conjunction with ISCA-35, Beijing, China, 2008.

4. Fedorova, A. Cache-fair thread scheduling for multicore processors / A. Fedorova, M. I. Seltzer, and M. D. Smith // Harvard Computer Science Group Technical Report TR-17-06, 2006.

5. Prihozhy, A. A. Investigation of implementation methods of multi-thread applications on multi-core systems / A. A. Prihozhy, O. N. Karasik // Informatization of Education, 2014, № 1.  С. 43–62.

6. Prihozhy, A. A. Cooperative model of optimal thread execution on multi-core system / A. A. Prihozhy, O. N. Karasik // System analysis and applied computer science, 2014, № 4.  С. 13–20.

7. Prihozhy, A. A. Cooperative block-parallel algorithms for solving tasks on multi-core systems / A. A. Prihozhy, O. N. Karasik // System analysis and applied computer science, 2015, № 2. – С. 10–18.

8. Al-Rayes, H. T. Concurrent Programming in Windows Vista / H.T. Al-Rayes // International Journal of Electrical & Computer Sciences IJECS-IJENS Vol.12 No.5, pp. 32–37.

9. Manchanda, Nakul, and Karan Anand. Non-uniform memory access // New York University, 2010.  4 p.

10. Rajput, V. Performance Analysis of UMA and NUMA Models / V. Rajput, S. Kumar and V. K. Patle. // IJCSIT Vol. 2, Issue 10, pp. 1457–1458.