Программное и аппаратное обеспечение для суперЭВМ

2

Поступила в редакцию 28.10.2018

Подписана в печать 15.02.2019

14 с.

PDF

В work-stealing балансировщиках параллельных задач, каждое ядро имеет свой буфер задач – дек (англ. deque). Владелец дека использует один конец для добавления и извлечения задач, а из второго конца задачи перехватываются другими ядрами. В статье анализируются два метода представления деков: один из распространенных методов - раздельное последовательное циклическое представление деков; и новый предложенный нами метод, где общая память для деков заранее не делится и они двигаются друг за другом по кругу. Ранее эти методы анализировались нами для представления FIFO-очередей в сетевых приложениях, где для некоторых значений параметров системы метод «Друг за другом» давал лучший результат.
Целью исследования является построение и анализ модели процесса работы с двумя последовательными деками, когда они двигаются друг за другом по кругу в общей памяти. Математическую модель мы будем строить как случайное блуждание по целым точкам в пирамиде. Имитационная модель строится с помощью метода Монте-Карло. Используемая стратегия work-stealing – перехват одного элемента. Предложены математическая и имитационная модели данного процесса и проведены численные эксперименты. (англ.)

Ключевые слова: work-stealing балансировщики, work-stealing деки, структуры
данных, поглощающие цепи Маркова, случайные блуждания.

Ссылка на статью обязательна

цифровой идентификатор статьи DOI

https://doi.org/10.25209/2079-3316-2019-10-1-19-32