Hierarchical Load Balance Algorithm Based on Feedback in Chip Multiprocessors System

王鹏; 董渭清; 王甜

您当前的位置：

首页 >

文章列表页 >

Hierarchical Load Balance Algorithm Based on Feedback in Chip Multiprocessors System

更新时间：2025-12-08

- Hierarchical Load Balance Algorithm Based on Feedback in Chip Multiprocessors System
- Vol. 42, Issue 2, Pages: 179-183(2008)
- 作者机构：
  
  西安交通大学计算机科学与技术系,西安,710049
- 作者简介：
- 基金信息：
- DOI：
  CLC： TP31
- Online First：10 February 2008，
  
  Published：2008
- 稿件说明：
移动端阅览
王鹏, 董渭清, 王甜. Hierarchical Load Balance Algorithm Based on Feedback in Chip Multiprocessors System[J]. 2008, 42(2): 179-183.
DOI：

王鹏, 董渭清, 王甜. Hierarchical Load Balance Algorithm Based on Feedback in Chip Multiprocessors System[J]. 2008, 42(2): 179-183. DOI：

摘要

针对现有负载平衡算法未能有效利用片上多处理器系统线程级并行性

没有考虑线程间数据共享与通信以及产生颠簸等问题

提出了一种基于反馈的层次负载平衡算法.采用层次式调度

将属于同一进程的多个线程静态调度到特定规模的内核子集上

并在此基础上根据系统实时负载情况在特定内核子集内动态迁移线程

以降低同一进程的多个线程之间的通信代价.在线程迁移过程中

引入反馈机制

即以系统颠簸情况为反馈信息

实时调整迁移数目

最终使系统较快地达到平衡.实验表明

基于反馈的层次负载平衡算法能使系统的平衡程度达到较高的水平

引入的反馈机制可使系统平衡速度提高28%

并在系统平衡前使“颠簸”数目减少54%.

Abstract

Focusing on the problem that existing load balance algorithms failed to make full use of chip multiprocessors(CMP)system's thread level parallelism(TLP)anddid not take data sharing

communication

and excessive transformation among threads into account

a hierarchical load balance algorithm based on feedback is proposed. Hierarchical schedule algorithm is adopted in order to reduce the cost of communication. Thus

threads of the same process are assigned into the same set of cores and then migrated into the range of its assigned core set dynamically. Feedback is used during the migration of threads according to the number of excessive transformation that could be computed through information feedback mechanism. The experiment shows that the algorithm is capable of achieving high balancing degree. Moreover

the balancing speed of hierarchical load balance methods with feedback mechanism is increased by 28%

and the excessive transformation is reduced by 54%.

关键词

Keywords

references

PARKHURST J, DARRINGER J, GRUNDMANN B. From single core to multi-core: preparing for a new exponential [C]∥Proceedings of the ACM Great Lakes Symposium on VLSI. New York: Association for Computing Machinery, 2006:210-216.

TENDLER J, DODSON S, FIELDS S, et al. Sinharoy POWER4 system microarchitecture [J].IBM Journal of Research and Development, 2002, 46(1):5-26.

HOFSTEE P. Power efficient processor architecture and the cell processor [C]∥Proceedings of 11th International Symposium on High-Performance Computer Architecture. Los Alamitos, USA: IEEE Computer Society, 2005: 258-262.

SPRACKLEN L, ABRAHAM S G. Chip multithreading: opportunities and challenges [C]∥Proceedings of the 11th International of Symposium on High-Performance Computer Architecture. Los Alamitos, USA: IEEE Computer Society, 2005:248-52.

CHEN Guan'ing, LAI Ten-Hwang. Scheduling independent jobs on partitionable hypercube [J]. Parallel and Distributed Computing, 1991,12(1):74-78.

肖建华,陈建二,陈松乔.超立方体网络中任务调度的一个新近似算法 [J].小型微型计算机系统, 2001, 22(8):913-916.

XIAO Jianhua, CHEN Jian'er, CHEN Songqiao. New algorithm for jobs scheduling in hypercube network[J].Mini-Micro Systems,2001, 22(8):913-916.

ZHU Yahui, MOHAN A. Job scheduling on a hypercube [J]. IEEE Trans on Parallel and Distributed System, 1993,4(1):62-69.

LIN F C H, KELLER R M. The gradient model load distribution methods [J].IEEE Trans on Software Engineering, 1987,13(1):32-38.

CYBENKO G. Dynamic load balancing for distributed memory multiprocessors [J]. Journal of Parallel and Distributed Computing, 1989,7(2):279-301.

MANIMARAN G, MURTHY C S B. An efficient dynamic scheduling algorithm for multiprocessor real-time systems [J]. IEEE Trans on Parallel and Distributed Systems, 1998,9(3):312-319

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Sensitivity Analysis of Foil Geometrical Parameters for the Third-Generation CO2 Gas Foil Bearings Based on Design of Experiments Method

A Structure-Semantics-Residual Collaborative Image Compression Framework：Towards Privacy Protection and High-Fidelity Reconstruction

Integrated and Joint Design Optimization of Centrifugal Compressor Impeller and Casing Treatment at Multiple Working Points

Bi-Level Multi-Obj ective Optimization of a Wind-Solar Coupled Hydrogen Production System Based on the Synergy of Hybrid Electrolyzer Arrays

Windage Loss and Flow Characteristics in Impeller Back Gaps of sCO2 Radial Inflow Turbines

Related Author

No data

Related Institution

No data

⁰