Минимизация средних затрат на перераспределение при работе с work-stealing деком в двухуровневой памяти

В работе рассмотрена задача оптимального управления workstealing деком (англ. — deque) в двухуровневой памяти. Предполагается, что известны вероятности параллельных операций с деком и временные характеристики памяти для двух уровней. Задача состоит в нахождении оптимального числа элементов с двух сторон дека, которые при перераспределении дека должны быть оставлены в быстрой памяти. В качестве критерия оптимальности рассмотрены минимальные средние затраты на перераспределение памяти, которые возникают в случае переполнения или опустошения быстрой памяти. Такой критерий позволяет учитывать конкретные скорости доступа к уровням памяти и применять разработанные методы к разным сочетаниям быстрой и медленной памяти. Построены математическая и имитационная модели процесса работы с деком, представлены результаты численных экспериментов.