|
1. Перечень услуг, предоставляемых распределёнными информационно-вычислительными системами (ИВС), постоянно расширяется. Соответственно, растёт число потенциальных пользователей ИВС и увеличивается полезность, которую мог бы получить каждый пользователь. Для развития ИВС, для привлечения информационно-вычислительных ресурсов (ИВР), причём именно тех, которые нужны пользователям, необходимо, чтобы владелец ресурса получал вознаграждение, увязанное с полезностью, которую получает потребитель ресурса. Тогда поставщики будут требовать, чтобы ИВС предоставляла ресурсы наиболее эффективным пользователям, которые способны извлечь из этих ресурсов максимальную полезность и, следовательно, согласны за них больше заплатить. Поэтому система управления ресурсами (СУР) будет руководствоваться в первую очередь не техническими критериями (как среднее время пребывания задания в системе), а стремлением каждого поставщика к максимизации прибыли и каждого пользователя - к максимизации полезности. Другими словами, ИВС станет субрынком рынка ИВР, а СУР будет обеспечивать ценовое согласование спроса и предложения на этом субрынке. Следовательно, минимальная "рыночная" роль СУР состоит в создании инфраструктуры, позволяющей агентам спроса и агентам предложения "находить друг друга" и договариваться об объёмах и ценах сделок. Такой подход реализован, например, в [1 - 3].
Многие авторы отводят СУР более активную роль. Они исходят из того, что каждого агента рынка представляет программа-брокер, которая "знает" бюджетное ограничение агента и модель его предпочтений на множестве ресурсных наборов. Взаимодействуя с программами-брокерами, СУР может вычислить цены равновесия (если оно существует). Затем агенты рынка (представляющие их программы) определяют спрос и предложение при этих ценах. Если удастся (децентрализованно или с участием СУР) выбрать оптимальные ресурсные наборы пользователей так, чтобы они попарно не пересекались, то получим равновесное распределение ресурсов. Мы рассмотрим два таких подхода к распределению ИВР. Рассматриваемые ниже модели описывают весьма частные случаи ИВС и опираются на сильные предположения, которые необходимо верифицировать. В докладе представлен лишь начальный этап исследования этих моделей.
2. R.Wolski с соавторами [4 - 6] моделируют ИВС, в которой распределяются ресурсы двух видов: процессорное время (в неделимых "слотах") и машинная память (в неделимых блоках). Для вычисления цен равновесия предложен разностный аналог механизма Смэйла [7]. Применимость этого алгоритма сомнительна, так как он на каждой итерации использует частные производные вектор-функции избыточного спроса по ценам, вычисленные на текущем векторе цен. Более того, из-за неверной интерпретации динамики процесса описанный авторами алгоритм существенно отличается от механизма Смэйла. Поэтому нет оснований предполагать, что алгоритм сходится вообще и к равновесию - в частности.
Нетрудно показать, что предложенный авторами подхода способ вычисления спроса и предложения отражает иррациональное поведение агентов рынка. Поэтому мы вводим простые, но правдоподобные функции полезности. Поставщик при фиксированных ценах максимизирует прибыль, эта задача в рассматриваемой модели решается тривиально. Для потребителя (задания) пусть V(t) - денежная оценка полезности завершения задания к моменту t, равная нулю для достаточно больших t. Допустим, что ресурсный набор r обеспечивает завершение задания в момент t(r) (если набор недостаточен, то t(r) бесконечно). Тогда при фиксированных ценах потребитель максимизирует величину F(r), равную V(t(r)) за вычетом стоимости ресурсов (потребительский излишек). Мы построили алгоритм для решения задачи потребителя и показали, что к описанной модели рынка можно (с некоторыми модификациями) применить механизм ценовой адаптации, опубликованный J.Ma и F.Ni в [8] (MN-механизм). Он не требует знания производных и строит сходящуюся последовательность векторов цен. Если равновесие существует, то пределом этой последовательности является вектор цен равновесия.
При всех достоинствах MN-механизм является "нащупывающим", то есть допускает распределение и использование ресурсов только по ценам равновесия. Поэтому реализацию подхода приходится представлять себе следующим образом. Заявки на выполнение заданий в "плановом периоде" [t,t+T] принимаются до момента t-a. Затем, в период [t-a,t], СУР вычисляет приближение к предельному вектору цен, каждое задание определяет множество оптимальных (при полученных ценах) ресурсных наборов на период [t,t+T], и СУР, используя эту информацию, находит близкое к равновесию распределение ресурсов (эта последняя задача, вообще говоря, NP-трудна). Процедура может оказаться весьма трудоемкой и вряд ли способна обеспечить хорошее распределение ресурсов на концах плановых периодов. Мы предполагаем, что идеи MN-механизма можно использовать для построения более реалистичной процедуры.
3. J.Bredin, D.Kotz и D.Rus в [9 - 11] рассматривают распределение непрерывного процессорного времени в многопроцессорной системе. Каждый пользователь (задание) на каждый единичный период выбирает процессор и скорость выполнения задания (число тактов процессора). Смена процессора происходит мгновенно и бесплатно. Предпочтения пользователей для каждого периода описаны функциями полезности в форме Кобба-Дугласа, зависящими от скорости и остатка бюджета после оплаты услуг выбранного процессора.
Устранив некоторые погрешности исходной модели, мы показали, что задача пользователя для каждого периода решается формульно, причем пользователь всегда выбирает процессор с минимальной текущей ценой процессорного времени. Более того, при любом распределении заданий между процессорами равновесие существует и легко вычисляется. Этот результат подсказывает следующую процедуру: каждое новое задание размещается на том процессоре, на котором цена равновесия (с учетом этого размещения) окажется минимальной. Заметим, что подробности механизма (прежде всего, перемещения заданий, уже находящихся в системе) требуют уточнения. Пока не изучены свойства распределений и динамика цен, порождаемых указанной процедурой. Мы предполагаем, что здесь есть возможность построения "ненащупывающего" механизма, позволяющего динамически распределять процессорное время с учетом интересов пользователей.
Литература
1. Buyya R., Abramson D., Giddy J., Stockinger H. Economic models for resource management and scheduling in Grid computing // Concurrency and Computation: Practice and Experience, 2002, 14, 1507 - 1542.
2. Buyya R., Giddy J., Abramson D. An evaluation of economy-based resource trading and scheduling on Computational power Grids for parameter sweep applications // Proceedings of the 2nd International Workshop on Active Middleware Services (AMS 2000), August 1, 2000, Pittsburg, PA, USA. - Kluwer Academic Press, 2000.
3. Buyya R., Murshed M. GridSim: A toolkit for the modeling and simulation of distributed resource management and scheduling for Grid Computing // Concurrency and Computation: Practice and Experience, 2002, 14, 1175 - 1220.
4. Wolski R., Plank J.S., Brevik J. G-Commerce - building computational marketplaces for the computational Grid. University of Tennessee Technical Report UT-CS-00-439, 2000.
5. Wolski R., Plank J.S., Bryan T., Brevik J. Analyzing market-based resource allocation strategies for the computational grid // International Journal of High Performance Computing Applications, 2001, v. 15(3).
6. Wolski R., Brevik J., Plank J.S., Bryan T. Grid resource allocation and control using computational economies. Глава 32 книги: Grid computing. Making the global infrastructure a Ieality. - Chichester, England: John Wiley & Sons, 2003.
7. Smale S. A convergent process of price adjustment and global Newton methods // Journal of Mathematical Economics, 1976, v. 3, 107 - 120.
8. Ma J., Nie F. Walrasian equilibrium in an exchange economy with indivisibilities // Mathematical Social Science, 2003, v. 46, 159 - 192.
9. Bredin J., Kotz D., Rus D. Market-based resource control for mobile agents. Technical Report PCS-TR97-326, Dept. of Computer Science, Dartmouth College, 1997.
10. Bredin J., Kotz D., Rus D. Utility Driven Mobile-Agent Scheduling // Dartmouth Technical Report PCS-TR98-331, Dartmouth College, Hanover, 1998.
11. Bredin J., Kotz D., Rus D. Economic markets as a means of open mobile-agent systems. In: Proceedings of the Workshop "Mobile Agents in the Context of Competition and Cooperation (MAC3)", 1999, p. 43-49.
Примечание. Тезисы докладов публикуются в авторской редакции
Ваши комментарииОбратная связь |
![[ICT SBRAS]](/picture/copan/ict-logo.gif){kind=logo}
[Головная страница] [Конференции] |
© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск