Публикации
Е.А.Аксенова, Е.А.Барковский, А.В.Соколов.
Метод представления трех work-stealing деков в двухуровневой памяти
// Вестник ЮУрГУ. Серия "Вычислительная математика и информатика". Т. 14, No 3. 2025. C. 28-41
Ключевые слова: двухуровневая память; метод Монте-Карло; структуры данных; work-stealing деки
Эффективность работы распределенных систем во многом зависит от равномерной загруженности потоков, что обеспечивается за счет различных стратегий балансировки задач между ними. Одним из методов децентрализованной динамической стратегии балансировки, где каждый поток участвует в распределении задач, является «work-stealing». Принцип метода в том, что поток не имеющий задач перехватывает («steal») их у других потоков. В основе процесса лежит специальная структура данных, work-stealing дек, в котором находятся указатели на задачи. При работе с деками возникает проблема их эффективного расположения в памяти. В двухуровневой памяти дек можно расположить разделив его на концы и середину: в быстрой памяти (первый уровень) находятся вершина и основание дека; в медленной памяти (второй уровень) — середина. Таким образом, система может быстро обращаться к концам дека, где элементы активно добавляются и удаляются. В статье анализируется новый метод представления трех work-stealing деков в двухуровневой памяти, где концы деков находятся в отдельных участках памяти. Для него строится имитационная модель на основе метода Монте-Карло, с помощью которой исследуются задачи оптимального разделения памяти. В качестве критерия оптимальности используется максимальное среднее время работы системы до перераспределения памяти.
DOI: 10.14529/cmse250302
Индексируется в РИНЦ, РИНЦ (WS)
Последние изменения: 20 октября 2025



