Keywords

1 Introduction

With the development of computer architecture, chip multi-processor (CMP) [1] becomes the mainstream architecture and provides a platform for high-performance computing. In order to play the parallelism of CMP fully, a good task scheduling algorithm is very important.

Many scholars at home and abroad have carried out many studies on task scheduling, which has been proved to be NP complete [2]. Based on the above research, a new improved genetic algorithm (NIGA) for heterogeneous CMP is proposed, which improves the initial population mode, selection strategy, crossover and mutation probability. The experimental results show that the performance of NIGA is better than genetic algorithm (GA).

2 New Improved Genetic Algorithm

The GA can search the solution in parallel, but it also has the problems of premature and poor stability [3]. In response to the above shortcomings, NIGA is proposed to optimize GA.

2.1 Encoding and Decoding of Chromosomes

Chromosome encoding [4] mode is substring, a substring represents a processor core and each substring contains the number of task which is assigned to the same processor in sequence. Figure 1 is an example of chromosome encoding.

Fig. 1.
figure 1

An example of chromosome encoding

Full size image

Chromosome decoding and encoding corresponds to each other, decoding is assigning tasks in sequence on the substring of chromosome to the corresponding processor core, then the structure of corresponding task scheduling is constructed.

2.2 Population Initialization and Fitness Function

The individual generation strategy in population is to randomly assign tasks to different processor cores. The tasks on the same core are sorted by the task height. The sequence of tasks with same height is generated randomly. The task height is defined as Eq. (1).

$$ h(N_{i} ) = \left\{ {\begin{array}{*{20}l} 0, \hfill & {if\,pre(N_{i} ) = \phi } \hfill \\ {\mathop {\hbox{max} }\limits_{{N_{j} \in pre(N_{i} )}} \{ h(N_{j} )\} + 1} \hfill & {else} \hfill \\ \end{array} } \right. $$
(1)

In NIGA, the quality of individuals is measured with fitness value, the individual with larger value has greater probability to be selected into next generation, and with smaller will be eliminated after some operations. The calculation of fitness is shown in Eq. (2).

$$ f(Xi) = \frac{1}{{SL(X_{i} )}} $$
(2)

In Eq. (2), \( SL(X_{i} ) \) represents the scheduling length of individual \( X_{i} \).

2.3 Selection

After the population initialization, the selection strategy is used to select several individuals randomly, then choosing individual with the highest fitness value to the next step. The difference between initial individuals is large, only the smaller competition scale can guarantee the population diversity. With the individual quality becomes better, the scale becomes larger in order to search the optimal solution globally. The strategy sets the scale double by 20 times, as shown in Eq. (3).

$$ K = 2 \times \frac{t}{20},\;\;\;\;t \in T $$
(3)

2.4 Crossover and Mutation

The main function of crossover is to generate new individual, the mutation operation is mainly to maintain species diversity [5]. If crossover and mutation probability is too large, some individuals with better fitness may be destroyed, it is not conducive to the solution convergence; if the probability is too small, it may not produce new individuals. Therefore, the probability should be adaptive, which can be changed with the fitness value, so as to ensure that individuals with low fitness value have a large probability, and the individuals with high fitness value has a small probability to save excellent individuals. The probability is shown in Eq. (4).

$$ P(i) = \left\{ {\begin{array}{*{20}l} {P_{\hbox{max} } } \hfill & {f_{i} \le f_{avg} } \hfill \\ {P_{\hbox{min} } + (P_{\hbox{max} } - P_{\hbox{min} } )\cot [\frac{\pi }{4}(\frac{{f_{i} - f_{avg} }}{{f_{\hbox{max} } - f_{avg} }} + 1)]} \hfill & {f_{i} > f_{avg} } \hfill \\ \end{array} } \right. $$
(4)

In Eq. (4), \( P_{\hbox{min} } \) and \( P_{\hbox{max} } \) is the minimum and maximum of crossover and mutation probability, \( f_{\hbox{max} } \), \( f_{avg} \), \( f_{i} \) is the maximum, average and i-th individual of fitness value respectively.

2.5 Termination Conditions

Set the maximum evolution number Tmax, NIGA is stopped after the certain iterations, then the individual with maximum fitness value is the optimal task scheduling.

3 Experiments

Randomly generated DAG is used as input data, by comparing the scheduling length and algorithm convergence to measure NIGA and GA.

The communication calculation rate (CCR) of DAG is 0.5 and the processor number is 3. The initial calculation parameters of GA and NIGA are: population size M = 100, maximum iterations Tmax = 200. Moreover, \( P_{c} \) of GA is 0.7, \( P_{m} \) is 0.02, the crossover \( P_{\hbox{min} } \) and \( P_{\hbox{max} } \) of NIGA are 0.8 and 0.2 respectively, the mutation \( P_{\hbox{min} } \) and \( P_{\hbox{max} } \) are 0.03 and 0.002 respectively. In order to avoid the randomness, the average of 15 experimental results is used as the test result of scheduling length.

The experiment mainly tests the scheduling length of GA and NIGA with different nodes, the result as shown in Table 1.

Table 1. The scheduling length of GA and NIGA with different nodes
Full size table

The experiment mainly tests the iterative evolution on same task number (Task Nodes = 20) of GA and NIGA algorithm, the experimental results are shown in Fig. 2.

From Table 1 and Fig. 2, it can be concluded that the scheduling length of NIGA is shorter than that of GA with the same task nodes, that is, the optimal solution of NIGA is the best, the time of optimal solution is shorter and the convergence speed is faster.

Fig. 2.
figure 2

The iterative evolution of GA and NIGA

Full size image

4 Conclusion

The NIGA algorithm is a better task scheduling algorithm based on heterogeneous CMP. It overcomes the shortcomings of GA and improves the scheduling efficiency. NIGA improves the initial population, uses the fitness selection strategy, adopts adaptive crossover and mutation probability to promote the global optimal solution. The experimental results show that the NIGA algorithm has the highest quality of the optimal solution and is faster than GA algorithm.