Research On CMP Load Balancing Scheduling Algorithm Based On Hypercube Structure

With the increasement of the chip implanted in transistors, it is possible that integrating more processor core in a chip.According to Moore's Law, the speed of microprocessors and single-chip integration will be doubled every 18 months. Then, the number of transistor integrated in a chip will be over one billion around 2010. How to efficiently manage the data communication and resource sharing in order to balance the load of each processor core is a key question of improving CMP's multi-core resource utilization and system performance.Hypercube structure was popular by researchers because of its informality, symmetry, the scalability of network communications capability. A load balancing scheduling algorithm based on the hypercube CMP was proposed. The CMP structure communication between the cores was expressed by the mathematical model of hypercube structure. Vertex express processor core, edge express relation between cores. Load balancing scheduling was realizing by task allocation algorithm and load balancing algorithm. Task allocation algorithm can speed up the allocation of tasks, shorten the system performance time. Load balancing algorithm can improve the utilization of CMP processor resource through Thread Migration.CMP simulator of many-threaded was designed and implemented based on the analysis of existing simulators based. The algorithm was testec on CMP system based on four-dimensional hypercube supported 8-thread. The experiment show that the average turnaround time was shorten by 14.8%, the system performance was improved by 22.3%.