Ценообразование процессорного времени
Ключевые слова и синонимы
Конкурентный аукцион (Competitive auction); рыночное равновесие (Market equilibrium); планирование ресурсов (Resource scheduling)
Постановка задачи
В данной задаче рассматривается модель вальрасовского равновесия для определения цен на процессорное время. В рыночной модели задачи о планировании заданий процессора владелец процессорного времени продает клиентам временные интервалы, и цена каждого временного интервалы зависит от стратегии продавца и предложений клиентов (функций оценки). В случае вальрасовского равновесия рынок чист, и каждый клиент максимально удовлетворен в соответствии со своей оценочной функцией и текущими ценами. В работе Дэна, Хуан и Ли [ ] были установлены условия существования вальрасовского равновесия и получены результаты сложности для определения существования равновесия. В ней также обсуждаются вопросы избыточного предложения процессорного времени и динамики цен.
Нотация
Рассмотрим комбинаторный аукцион (QI, V).
Любая оценочная функция vi может быть выражена XOR-комбинацией атомарных заявок,
vi = (Si1;qi1) XOR(Si2;qi2)::: XOR(Sin;qin)
Если имеются входные данные в виде (Q, I, V), продавец определяет распределение и вектор цен в качестве выходных данных:
• Распределение X = fX0;X1;X2... представляет собой разбиение Q, в котором Xi – совокупность товаров, выделенная покупателю i, а X0 – множество нераспределенных товаров.
• Вектор цен p – это неотрицательный вектор в пространстве R m, j-м элементом которого является цена товара !J 2 Q.
Для любого подмножества Г = {a>i x ai,... , com x am} С Q определим p(T) равным p(T) = Pmj=1 ajPj. Если покупателю i выделена совокупность Xi, его полезность равна щ (Xi ; p) = vi (Xi) - p(Xi).
Определение. Вальрасовское равновесие для комбинаторного аукциона (Q, I, V) представляет собой кортеж (X,p), где X = fX0; X1 Xng – распределение, а p – вектор цен, удовлетворяющий условию:
Такой вектор цен также называется рыночной клиринговой ценой, вальрасовской ценой или равновесной ценой.
Задача о планировании заданий процессора
В ориентированной на рынок модели распределения ресурсов процессора есть два типа игроков: поставщик ресурса и n потребителей. Поставщик продает потребителям временные интервалы процессора, каждый потребитель имеет задания, требующие фиксированного объема времени процессора, и его оценочная функция зависит от временных интервалов, выделенных для задания, обычно от последнего выделенного временного интервала. Предположим, что все задания выпускаются в момент времени t = 0, и каждое задание требует si единиц времени. Задания можно прерывать без затрат на вытеснение, как это часто моделируется для заданий процессора.
Переводя ситуацию на язык комбинаторных аукционов, на рынке имеется m товаров (единиц времени), Q = f!1 ;:::; !mg, и n покупателей (заданий), I = f1; 2... n g. Каждый покупатель имеет оценочную функцию vi, зависящую только от времени завершения. Более того, если это не указано явно, оценочная функция каждого задания является невозрастающей относительно времени завершения.
Основные результаты
Рассмотрим следующую задачу линейного программирования:
Обозначим задачу как LPR (релаксацию линейного программирования), а ее целочисленное ограничение – как IP (целочисленное программирование. Следующая теорема показывает, что из ненулевого разрыва между задачей целочисленного программирования IP и ее линейной релаксацией следует несуществование вальрасовского равновесия.
Теорема 1. В комбинаторном аукционе вальрасовское равновесие существует тогда и только тогда, когда оптимум IP равен оптимуму LPR. Размер задачи LP линейно зависит от общего числа XOR-заявок.
Теорема 2. Задача определения существования вальрасовского равновесия в задаче планирования заданий на процессоре является NP-трудной в сильном смысле.
Теперь рассмотрим задачу планирования заданий, в которой все оценочные функции клиентов линейны. Предположим, что в момент времени t = 0 на одной машине запускается n заданий, время выполнения j-го задания составляет sj 2 N+, а вес wj > 0. Целью планирования является минимизация взвешенного времени завершения: Pni=1 witi, где ti – время завершения задания i. Такая задача называется задачей MWCT (минимальное взвешенное время завершения).
Теорема 3. В одномашинной задаче планирования заданий MWCT вальрасовское равновесие всегда существует, если m > EM + A, где m – общее количество процессорного времени, EM = Pin=1 si и A = maxk fskg. Равновесие может быть вычислено за полиномиальное время.
Следующая теорема доказывает существование невозрастающей последовательности цен в случае, если существует вальрасовское равновесие.
Теорема 4. Если существует вальрасовское равновесие в задаче планирования заданий, то оно может быть приведено к равновесию с последовательным распределением и невозрастающим вектором равновесных цен.
Применение
Информационные технологии изменили образ жизни людей, создав множество цифровых товаров, таких как программы для обработки текстов, компьютерные игры, поисковые системы и онлайн-сообщества. Новая экономика уже потребовала применения многих теоретических инструментов (новых и старых, из экономики и других смежных дисциплин) для их разработки и производства, маркетинга и ценообразования. Отсутствие полного понимания новой экономики в основном связано с тем, что цифровые товары часто могут быть повторно произведены без дополнительных затрат, хотя в числе трудностей могут выступать и другие многочисленные факторы. Работа Дэна, Хуан и Ли [ ] посвящена процессорному времени как товару, продаваемому на рынке, с помощью вальрасовской модели ценообразования в экономике. Процессорное время как коммерческий продукт широко изучается в сетевых коллективных вычислениях. Обособление ценообразования на процессорное время позволяет отложить в сторону другие сложные вопросы, вызванные второстепенными факторами, а полное понимание этого особого цифрового товара (или услуги) может пролить свет на изучение других товаров в цифровой экономике.
Использование процессорного времени несколькими клиентами было важнейшим вопросом в развитии концепции операционных систем. Развитие сетевых коллективных вычислений предполагает полное использование вычислительных ресурсов, например, процессорного времени, дискового пространства, пропускной способности. В работах [2, 5] были предложены ориентированные на рынок схемы для эффективного распределения ресурсов вычислительной сетки. В дальнейшем появились различные практические и имитационные системы управления ресурсами вычислительных сетей. Помимо распределения ресурсов в распределенных сетях, экономический механизм также был внедрен в задачи управления перегрузками TCP, см. Келли [ ].
См. также
Литература
1. Deng, X., Huang, L.-S., Li, M.: On Walrasian Price of CPU time. In: Proceedings of COCOON'05, Knming, 16-19 August 2005, pp. 586-595. Algorithmica 48(2), 159-172 (2007)
2. Ferguson, D., Yemini, Y., Nikolaou, C.: Microeconomic Algorithms for Load Balancing in Distributed Computer Systems. In: Proceedings of DCS'88, pp.419-499. San Jose, 13-17 June 1988,
3. Goldberg, A.V., Hartline, J.D., Wright, A.: Competitive Auctions and Digital Goods. In: Proceedings of SODA'01, pp. 735-744. Washington D.C., 7-9 January 2001
4. Kelly, F.P.: Charging and rate control for elastic traffic. Eur. Trans. Telecommun. 8,33-37 (1997)
5. Kurose, J.F., Simha, R.: A Microeconomic Approach to Optimal Resource Allocation in Distributed Computer Systems. IEEE Trans. Comput. 38(5), 705-717 (1989)
6. Nisan, N.: Bidding and Allocation in Combinatorial Auctions. In: Proceedings of EC'00, pp. 1-12. Minneapolis, 17-20 October 2000