sapiСистемный анализ и прикладная информатика«System analysis and applied information science»2309-49232414-0481Belarusian National Technical University10.21122/2309-4923-2017-1-4-11sapi-144Research ArticleСистемный анализSystem analysisУСОВЕРШЕНСТВОВАННЫЙ ПЛАНИРОВЩИК КООПЕРАТИВНОГО ВЫПОЛНЕНИЯ ПОТОКОВ НА МНОГОЯДЕРНОЙ СИСТЕМЕADVANCED SCHEDULER FOR COOPERATIVE EXECUTION OF THREADS ON MULTI-CORE SYSTEMКарасикО. Н.KarasikO. N.

Карасик Олег Николаевич – аспирант кафедры «Программное обеспечение вычислительной техники и автоматизированных систем» БНТУ, ведущий инженер программист компании «EPAM Systems»

Karasik Aleh  – postgraduate of the Computer and system software department and a leading software engineer at EPAM Systems. 

ПрихожийА. А.PrihozhyA. A.

Прихожий Анатолий Алексеевич –доктор технических наук, профессор кафедры программного обеспечения вычислительной техники и автоматизированных систем.

Белорусский национальный технический университетБеларусьBelarusian National Technical UniversityBelarus20170405201701411Copyright © Карасик О.Н., Прихожий А.А., 20172017Карасик О.Н., Прихожий А.А.Karasik O.N., Prihozhy A.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://sapi.bntu.by/jour/article/view/144

Рассматриваются три архитектуры планировщика кооперативного выполнения потоков в многопоточном приложении, исполняемом на многоядерной системе. Архитектура А0 использует средства взаимодействия и синхронизации потоков, предоставляемые операционной системой. Архитектура А1 вводит новый примитив синхронизации потоков и единую для планировщика очередь заблокированных потоков, благодаря которым уменьшает активность взаимодействия потоков с операционной системой и значительно ускоряет процессы блокировки и разблокировки потоков. Архитектура А2 заменяет единую очередь заблокированных потоков на отдельные очереди для каждого примитива синхронизации и расширяет набор внутренних состояний примитива, уменьшая взаимозависимость потоков планирования и значительно ускоряя процессы блокировки и разблокировки рабочих потоков. Архитектуры планировщика реализованы в операционных системах Windows на базе технологии User Mode Scheduling. Важные экспериментальные результаты получены для многопоточных приложений, реализующих два блочно-параллельных алгоритма решения систем линейных алгебраических уравнений методом Гаусса. Алгоритмы различаются способами распределения данных между потоками и моделями синхронизации потоков. Число потоков варьировалось от 32 до 7936. Архитектура А1 показала ускорение до 8.65%, а архитектура А2 показала ускорение до 11.98 % по сравнению архитектурой А0 на блочно-параллельных алгоритмах с учетом их прямого и обратного хода. На обратном ходе алгоритмов архитектура А1 дала ускорение до 125 %, а архитектура А2 дала ускорение до 413 % по сравнению архитектурой А0. Эксперименты убедительно доказывают, что предлагаемые в статье архитектуры А1 и А2 выигрывают у А0 тем значительнее, чем большее количество блокировок и разблокировок потоков происходит во время выполнения многопоточного приложения.

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.

многопоточное приложениепланировщиккооперативная модельмногоядерная система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 facilitieswhich are provided by the operating system. Architecture A1 introduces a new synchronization primitive and a single queue of the blocked threads in the schedulerwhich reduces the interaction activity between the threads and operating systemand significantly speed up the processes of blocking and unblocking the threads. Architecture A2 replaces the single queue of blocked threads with dedicated queuesone for each of the synchronizing primitivesextends the number of internal states of the primitivereduces the inter- dependence of the scheduling threadsand 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 algorithmsarchitecture 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 architecturesA1 and A2 outperform A0 depending on the number of thread blocking and unblocking operationswhich 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.ReferencesRajagopalan, 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.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.Yun, H. Deterministic Real-time Thread Scheduling / H. Yun, C. Kim, and L. Sha // preprint arXiv: 1104.2110, 2011.Yun, H. Deterministic Real-time Thread Scheduling / H. Yun, C. Kim, and L. Sha // preprint arXiv: 1104.2110, 2011.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.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.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.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.Прихожий, А. А. Исследование методов реализации многопоточных приложений на многоядерных системах / А. А. Прихожий, О. Н. Карасик // Информатизация образования, 2014, № 1.  С. 43–62.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.Прихожий, А. А. Кооперативная модель оптимизации выполнения потоков на многоядерной системе / А. А. Прихожий, О. Н. Карасик // Системный анализ и прикладная информатика, 2014, № 4.  С. 13–20.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.Прыхожы A. A. Кааператыўныя блочна-паралельныя алгарытмы рашэння задач на шмат’ядравых сістэмах / А. А. Прыхожы, А. М. Карасік // Системный анализ и прикладная информатика, 2015, № 2. – С. 10–18.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.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.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.Manchanda, Nakul, and Karan Anand. Non-uniform memory access // New York University, 2010.  4 p.Manchanda, Nakul, and Karan Anand. Non-uniform memory access // New York University, 2010.  4 p.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.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.

The authors declare that there are no conflicts of interest present.