УСОВЕРШЕНСТВОВАННЫЙ ПЛАНИРОВЩИК КООПЕРАТИВНОГО ВЫПОЛНЕНИЯ ПОТОКОВ НА МНОГОЯДЕРНОЙ СИСТЕМЕ

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

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. Прихожий, А. А. Исследование методов реализации многопоточных приложений на многоядерных системах / А. А. Прихожий, О. Н. Карасик // Информатизация образования, 2014, № 1.  С. 43–62.

6. Прихожий, А. А. Кооперативная модель оптимизации выполнения потоков на многоядерной системе / А. А. Прихожий, О. Н. Карасик // Системный анализ и прикладная информатика, 2014, № 4.  С. 13–20.

7. Прыхожы A. A. Кааператыўныя блочна-паралельныя алгарытмы рашэння задач на шмат’ядравых сістэмах / А. А. Прыхожы, А. М. Карасік // Системный анализ и прикладная информатика, 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.