Incentive Compatible Online Scheduling of Malleable Parallel Jobs with Individual Deadlines
Incentive Compatible Online Scheduling of Malleable Parallel Jobs with Individual Deadlines
复制标题
具有单独截止日期的可延展并行作业的激励兼容在线调度
DOI：
10.1109/icpp.2010.60
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Daniel Grosu
中科院分区：
文献类型：
--
作者：
T. E. Carroll;Daniel Grosu
我们考虑并行系统，如集群，对称多处理机，多核处理器计算机上的可延展作业的在线调度。可延展作业是一种并行处理模型，其中作业适应分配给它们的处理器数量。该模型允许调度器和资源管理器更有效地利用可用资源。每个可延展的工作都有到达时间、截止日期和价值的特征。如果作业在截止日期前完成，用户获得的收益由值表示;否则，她获得的收益为零。调度的目标是最大化在相关截止日期前完成的作业的价值之和。使问题复杂化的是，真实的世界中的用户是理性的，如果这样做对他们有利，他们会试图通过误报作业参数来操纵调度程序。为了减轻这种行为，我们设计了一个激励兼容的在线调度机制。激励相容性保证了用户只有如实地向调度器报告其作业的参数，才能获得最大的收益。最后，我们模拟和研究的机制，显示误报对作弊者和系统的影响。
We consider the online scheduling of malleable jobs on parallel systems, such as clusters, symmetric multiprocessing computers, and multi-core processor computers. Malleable jobs is a model of parallel processing in which jobs adapt to the number of processors assigned to them. This model permits the scheduler and resource manager to make more efficient use of the available resources. Each malleable job is characterized by arrival time, deadline, and value. If the job completes by its deadline, the user earns the payoff indicated by the value; otherwise, she earns a payoff of zero. The scheduling objective is to maximize the sum of the values of the jobs that complete by their associated deadlines. Complicating the matter is that users in the real world are rational and they will attempt to manipulate the scheduler by misreporting their jobs' parameters if it benefits them to do so. To mitigate this behavior, we design an incentive compatible online scheduling mechanism. Incentive compatibility assures us that the users will obtain the maximum payoff only if they truthfully report their jobs' parameters to the scheduler. Finally, we simulate and study the mechanism to show the effects of misreports on the cheaters and on the system.