• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >Optimal quantization of periodic task requests on multiple identical processors
【24h】

Optimal quantization of periodic task requests on multiple identical processors

机译：在多个相同处理器上的周期性任务请求的最佳量化

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We simplify the periodic tasks scheduling problem by making a trade off between processor load and computational complexity. A set N of periodic tasks, each characterized by its density /spl rho//sub i/, contains n possibly unique values of /spl rho//sub i/. We transform N through a process called quantization, in which each /spl rho/i /spl isin/ N is mapped onto a service level s/sub j/ /spl isin/ L, where |L| = l /spl Lt/ n and /spl rho//sub i/ /spl les/ s/sub j/, (this second condition differentiates this problem from the p-median problem on the real line). We define the periodic task quantization problem with deterministic input (PTQ-D) and present an optimal polynomial time dynamic programming solution. We also introduce the problem PTQ-S (with stochastic input) and present an optimal solution. We examine, in a simulation study, the trade off penalty of excess processor load needed to service the set of quantized tasks over the original set, and find that, through quantization onto as few as 15 or 20 service levels, no more than 5 percent processor load is required above the amount requested. Finally, we demonstrate that the scheduling of a set of periodic tasks is greatly simplified through quantization and we present a fast online algorithm that schedules quantized periodic tasks.
机译：我们通过在处理器负载和计算复杂度之间进行权衡来简化周期性任务调度问题。一组N个定期任务，每个任务的密度为/ spl rho // sub i /，包含n个可能的唯一值/ spl rho // sub i /。我们通过称为量化的过程对N进行变换，其中每个/ spl rho / i / spl isin / N映射到服务级别s / sub j / / spl isin / L，其中| L |。 = l / spl Lt / n和/ spl rho // sub i / / spl les / s / sub j /，（第二个条件将这个问题与实线上的p中位数问题区分开了）。我们用确定性输入（PTQ-D）定义了周期性任务量化问题，并提出了一种最优的多项式时间动态规划解决方案。我们还介绍了问题PTQ-S（具有随机输入）并提出了最佳解决方案。在模拟研究中，我们检查了为量化任务集服务于原始任务集所需的额外处理器负载的权衡代价，并发现通过量化到少至15或20个服务级别，不超过5％需要的处理器负载超出了请求的数量。最后，我们证明了通过量化极大地简化了一组周期性任务的调度，并且我们提出了一种调度量化的周期性任务的快速在线算法。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号