高级检索
    刘 轶, 张 昕, 李 鹤, 钱德沛. 一种面向多核处理器并行系统的启发式任务分配算法[J]. 计算机研究与发展, 2009, 46(6): 1058-1064.
    引用本文: 刘 轶, 张 昕, 李 鹤, 钱德沛. 一种面向多核处理器并行系统的启发式任务分配算法[J]. 计算机研究与发展, 2009, 46(6): 1058-1064.
    Liu Yi, Zhang Xin, Li He, Qian Depei. A Heuristic Task Allocation Algorithm for Multi-Core Based Parallel Systems[J]. Journal of Computer Research and Development, 2009, 46(6): 1058-1064.
    Citation: Liu Yi, Zhang Xin, Li He, Qian Depei. A Heuristic Task Allocation Algorithm for Multi-Core Based Parallel Systems[J]. Journal of Computer Research and Development, 2009, 46(6): 1058-1064.

    一种面向多核处理器并行系统的启发式任务分配算法

    A Heuristic Task Allocation Algorithm for Multi-Core Based Parallel Systems

    • 摘要: 多核处理器使得并行系统的结构更加复杂并且其中任务个数大大增加,为了在这类系统中高效地进行任务分配,建立了任务分配模型,并提出了一种包含两轮操作的启发式任务分配算法,分别完成进程到处理节点和进程内线程到处理器核的分配.每轮操作经过带回溯的多次迭代处理,最终得到任务到处理器核的分配方案.与穷举查找法和遗传算法的对比测试表明该算法能在较短时间内求得近优解,并且当线程个数增大时,算法的求解时间远小于遗传算法.

       

      Abstract: Parallel systems based on multi-core or many-core processors have more complicated structure and more tasks running on it than traditional uni-core based systems. To allocate tasks in this kind of systems efficiently, a task allocation model based on the task interaction graph is built, in which the processes, threads and communications among them are taken into account. And then an iteration-based heuristic algorithm is proposed based on the model. The algorithm is composed of two rounds of operations, in which the processes are assigned to processing nodes in the first round and the threads of a process are assigned to processing cores in the second round respectively. Each round of operation partitions the task interaction graph by iterations with backtracking. As a result, the final partitioned graph corresponds to the task allocation solution which assigns tasks to processing cores. The heuristic algorithm is evaluated by comparing it with exhaustive searching and genetic algorithms using 1400 random-generated task interaction graphs, and the results show that the proposed heuristic algorithm can find near-optimal solutions in reasonable time, and behave better in scalability than genetic algorithms when the number of threads increases, since it can find solutions in much less time than genetic algorithms.

       

    /

    返回文章
    返回