Кооперативный многопоточный планировщик для эффективного решения прикладных задач на многоядерных системах

Abstract

Предлагается архитектура кооперативного многопоточного планировщика выполнения потоков на многоядерных системах под управлением ОС Windows. Архитектура реализована с помощью механизма User Mode Scheduling, позволяющего пользовательскому приложению организовывать кооперативное выполнение потоков. Исследуемая архитектура включает в себя потоки пользователя, исполняющие пользовательский код; потоки планировщика, управляющие выполнением потоков пользователя; примитив синхронизации для организации взаимодействия потоков пользователя, выполняющихся на разных ядрах многоядерной системы; механизм передачи управления между потоками пользователя, выполняющимися на одном ядре. Распределенный по ядрам планировщик позволяет потокам самим логически планировать порядок передачи управления и повышать производительность многоядерной системы при исполнении блочно-параллельных алгоритмов решения практически важных задач. Многопоточные алгоритмы, построенные известными способами, не обладают нужными планировщику свойствами. В связи с этим предложен новый способ построения кооперативных потоковых блочно-параллельных алгоритмов. Производительность планировщика оценена экспериментально на кооперативных блочно-параллельных алгоритмах решения систем линейных алгебраических уравнений методом Гаусса и на кооперативных блочно-параллельных алгоритмах нахождения кратчайших путей на графе методом Флойда-Уоршелла. Алгоритмы балансируют распределение блоков данных по потокам и потоков по ядрам; устанавливают порядок выполнения потоков на каждом ядре; минимизируют слоты времени на управление, ожидание и простаивание потоков; повышают полезную загрузку ядер близко к 100%; позволяют находить оптимальный размер блока; сокращают обмен данными между кэшем ядер и между уровнями иерархической памяти.