The Optimal Control of Two Work-Stealing Deques, Moving One After Another in a Shared Memory

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