Hierarchical load balance algorithm based on feedback in chip multiprocessors system

Focusing on the problem that existing load balance algorithms failed to make full use of chip multiprocessors (CMP) system's thread level parallelism (TLP) and did 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%.