Computer Engineering and Applications ›› 2018, Vol. 54 ›› Issue (8): 55-60.DOI: 10.3778/j.issn.1002-8331.1701-0230

Previous Articles     Next Articles

Global constraints for multi-objective based task allocation and scheduling algorithm

YU Kun1, ZHANG Zhengben1, HAI Benzhai2   

  1. 1.Department of Computer Science and Technology, Henan Institute of Technology, Xinxiang, Henan 453002, China
    2.College of Computer and Information Engineering, Henan Normal University, Xinxiang, Henan 453002, China
  • Online:2018-04-15 Published:2018-05-02

基于多目标全局约束的任务分配和调度算法

于  琨1,张正本1,海本斋2   

  1. 1.河南工学院 计算机科学与技术系,河南 新乡 453002
    2.河南师范大学 计算机与信息工程学院,河南 新乡 453002

Abstract: Aiming at the problem of target cost which is not cared about by most task execution algorithms in embedded systems, a task allocation and scheduling algorithm based on global constraints for multi-objective is proposed in this paper. The approach uses constraint logic programming to impose global constraints for multi-objective on the task execution resources such as processing units, communication devices and the usage of code and data memory. The proposed algorithm assumes that ROM and RAM are used for implementing code memory and data memory respectively, and also considers the actual placement of data in data memory. The experimental results show that, under the multiple constraints, the proposed task allocation and scheduling algorithm can perform both in terms of the usage of code and data memory as well as solving effectively the task better than the widely used greedy scheduling algorithms.

Key words: multi-objective, global constraints, allocation and scheduling, memory size, cost

摘要: 针对嵌入式系统中大多数任务执行算法不考虑目标成本问题,提出了一种基于多目标全局约束的任务分配和调度算法。算法使用约束逻辑编程来对任务执行资源如处理单元、通信设备以及代码和数据存储量的使用进行多目标全局约束。算法假设ROM和RAM分别用于代码存储和数据存储,算法还考虑数据在数据存储器中的位置。实验结果表明,尽管在多个约束条件下,提出的任务分配和调度算法无论在代码存储和数据存储量使用方面,还是在对任务有效求解方面都能取得比普遍采用的贪婪调度算法更好的结果。

关键词: 多目标, 全局约束, 分配和调度, 存储量, 成本