Потенциал в некооперативной игре управления заданиями с линейными экстерналиями

Аннотация

Представлена и исследована теоретико-игровая математическая модель управления заданиями в вычислительной системе с линейными экстерналиями. Каждый игрок стремится максимизировать свою производительность в присутствии положительных экстерналий. Предложенная модель описывает управление заданиями в системе добровольных вычислений типа Desktop Grid, а экстерналии выражают обмен информацией в процессе решения научной задачи. Системы Desktop Grid задействуют вычислительные мощности неспециализированных компьютеров, объединенных сетью передачи данных и выполняющих вычисления в то время, когда они не заняты другой работой. В таких системах вычислительноемкая научная задача зачастую делится на несколько взаимосвязанных подзадач, выполняемых параллельно. Промежуточные ре-зультаты решения одной подзадачи способны помогать в решении остальных подзадач, оптимизируя или сокращая вычисления. В данной работе доказано, что игра является потенциальной в случаях однородных процессоров или заданий и одинаковых экстерналий, инвариантных или симметричных экстерналий. При этом в случаях с однородными процессорами или заданиями и одинаковыми экстерналиями или инвариантными экстерналиями равновесие по Нэшу единственно и глобально оптимально, в то время как случай с симметричными экстерналиями допускает множество равновесий по Нэшу в чистых стратегиях. Приводятся результаты вычислительных экспериментов по моделированию управления заданиями предложенным методом в сравнении с рядом популярных алгоритмов. Представленные результаты расширяют область применения классических моделей, доказывая существование равновесия и сходимость к нему как в задачах минимизации задержки, так и в задачах максимизации производительности. Найденный вид функции потенциала позволяет исполь- зовать методы глобальной оптимизации для поиска равновесий.