Keywords

1 Introduction

Nowadays single core architectures is gradually replaced by multiple cores due to problems in obtaining further performance increases from single core processors [1]. Heterogeneous multicore architecture (HMA) is an integration of special purpose processing cores. The purpose of task assignment in HMA is to help system designers to get the best-performance and the lowest-cost design scheme in HMA [2]. Task assignment in HMA minimizes the execution time and consumed power of the target system [3] with certain constraint conditions.

Task assignment in HMA is an NP-hard problem [4]. Many heuristic algorithms have been applied to solve the NP-hard problem [5,6,7,8]. Due to the advantages of few control parameters, computed conveniently and carried out easily, ABC algorithm has been applied to solve many practical optimization problems [9], which have obtained preferable results.

ABC algorithm is based on swarm behavior, with the characteristics of integrity, relevance, dynamic and orderliness on systematics [10]. It can be evolved from disorder to order by self-organizing. Bees and bee colonies have feedback features at the same time [11]. Because it is limited by the way of evolution, there are still some disadvantages, such as low precision, slow convergence [12], poor local search ability [13,14,15]. In this paper, we describe the HMA as a model of a task assignment. The HMA are combined with two different cores. The original ABC algorithm is used in the model to achieve the DAG diagram corresponding to system tasks. Then an improved method based on adaptive neighborhood search is proposed to address the original ABC algorithm’s disadvantages. Five DAG figures are generated randomly with TGFF [16] tools as a test set in order to compare the performance of the original and the improved ABC algorithms. The experimental results demonstrate that the improved ABC algorithm is more efficient.

2 Task Assignment Based on ABC

2.1 Bees Behavior

ABC simulates the co-operation, mutual coordination between individuals and groups in intelligent foraging and breeding behavior of bee swarms. They exchange information through dance and odor to finish foraging behavior. In a typical ABC algorithm, three types of artificial bees are considered as agents for solving an optimization problem, called employed bees, onlooker bees and scout bees. They have their own division or labor in foraging. The scout bees are responsible for investigation. The employed bees and onlooker bees are responsible for the exploitation of food sources. The bees maintained good coordination to achieve a better balance, and then completed the bee groups of foraging, reproduction and other behaviors.

2.2 Mathematical Model of the Artificial Bee Colony Algorithm

A system task is divided into a number of sub-tasks which can be completed by a combination of core A (represented by 0) and core B (represented by 1). When the two cores process the same task they consume different time and power. The coded information corresponding to the task assignment can be seen as an ordered set of binary numbers. The task assignment in HMA can be abstracted as a multi-objective combinatorial optimization problem in mathematics, to find a sub-optimal solution or the optimal solution under different constraints.

Bees can quickly find a better food source in foraging. Similarly, the task assignment can quickly find a better solution in the process. The correspondence among bee foraging behavior, mathematical model and task assignment is shown in Table 1.

Table 1. The correspondence among Bee foraging behavior, mathematical model and task assignment
Full size table

Apparently, the more nodes there are, the more task assignment schemes. The number of schemes is growing at an exponential rate to the number of nodes. In a DAG, some tasks are completed by core A, the others are completed by core B. Figure 1 presents one scheme of the task assignments.

Fig. 1.
figure 1

One scheme of the task assignments.

Full size image

The best scheme from all the task assignment schemes is to be selected according to their fitness values and the probability to be searched. The maximum fitness food source is selected, which may be the optimal or suboptimal solution corresponding to the best task assignment in HMA. The Eq. (1) is used to describe the best scheme of task assignment in HMA.

$$ \left\{ {\begin{array}{*{20}l} {Max\_fitness: = \hbox{max} (fitness[i])} \hfill \\ {\quad \quad \sum\limits_{j = 0}^{N - 1} {T_{j} < Time\_Limit} } \hfill \\ {s.t.} \hfill \\ {\quad \sum\limits_{j = 0}^{N - 1} {Power_{j} < Power\_Limit} } \hfill \\ \end{array} } \right. $$
(1)

Here \( fitness(i) \) is the fitness value of i-th food source, \( T_{j} \) and \( Power_{j} \) are the total time consuming and the total power consuming of the j-th node respectively. \( Time\_Limit \) and \( Power\_Limit \) are the maximum time and the maximum power limitations respectively.

2.3 Description of the Original ABC Algorithm

ABC is applied to solve the traveling salesman problem in literature [11]. The algorithm based on the mathematical model in Eq. (1) is applied to task assignment in HMA.

At first, the bees are equally divided into scout bees and onlooker bees. The scout bees search the food source and the food source in its neighborhood. If the fitness of its neighborhood position is greater than its fitness, then the location of i-th food source is substituted by the location of its neighborhood. Onlooker bees are sent according to the probability of each candidate food source to search food. The greater the probability is, the greater likelihood of neighborhood search is. If the fitness of the neighborhood position is greater than that of the current location, the current location is substituted by the location of its neighborhood.

When the time consumed by the neighborhood search is greater than the maximum limit time of food source, the food source is initialized. When its search time is greater than the global maximum limit, the worst food source is initialized. Every bit of coding information (0 or 1) is selected probably in the initialization.

At last the optimal or suboptimal food source searched is recorded. The information coding corresponds to the best scheme of task assignment in HMA. In original ABC algorithm, scout bees and onlooker bees finish their neighborhood search by updating one bit of information coding randomly, such as 0 (1) is updated as 1 (0). So the information update of food source is implemented.

3 The Analysis and Improvement of ABC Algorithm

3.1 The Shortcoming of the Original ABC Algorithm

In ABC algorithm, food source is updated through replacing the sub-optimal position by optimal position. The food-searching process is equivalent to the process of finding the optimal solution to task assignment in HMA.

When the initial position of the food source is far away from the optimal food source, there is a big difference between the encoded information of them. The method mentioned above will be very low efficiency. Obviously, the convergence rate will be lower and the method will increase the number of invalid iterative search. It is a broader range and high-discrete solution space. Finding the optimal solution is a continuous iteration and selection process. Therefore, in order to improve the optimization capability and reduce the time overhead, invalid iterations should be avoided or minimized.

3.2 The Improvement of ABC Algorithm

In view of the deficiencies of the original ABC algorithm, the efficiency of ABC algorithm is improved from the aspects of invalid iteration and neighborhood search strategy.

The Improvement of Neighborhood Search Strategy

When neighborhood search iteration is less than the constraint condition, the neighborhood search strategy updates one bit of the coded information in an iteration. On the contrary, when neighborhood search iterations exceed the constraint condition, but the fitness of the corresponding food source cannot be improved, then, the neighborhood search strategy is changed to update several bits of the coded information in an iteration.

Function named Search_Neighbourfood_Strategy_Improved([i]) is used to updates the coded information of the food source randomly. The pseudo-code is as follows (Table 2):

Table 2. The pseudo-code of the new neighborhood search program for the i-th food source.
Full size table

Here, \( X_{i,old\_location} \) is the information coding of the i-th food’s current location, \( X_{i,neighbour\_location} \) is the information coding of the i-th food source’s neighborhood.

The Improvement of Calculating the Worst Food Source

During later iteration, all of the current food sources are approaching the final result. The worst food source is re-coded according the best food source’s current location instead of initialize the worst food source. Several bits of the best food source’s current location are kept and the remaining bits are re-coded. The pseudo-code is as follows (Table 3):

Table 3. The pseudo-code of generating a new solution.
Full size table

Here, \( X_{best\_location} \) is the information coding of the current best food source’s location, \( X_{neighbour\_location} \) is the information coding of the current best food source’s neighborhood, \( X_{new\_location} \) is the information of the new solution.

4 Experimental Results and Analysis

Algorithms in this paper are implemented in C-language and tested on a computer with Intel core i5-4460 and 8 GB RAM. The running environments consists of Windows 10 and Microsoft Visual Studio 2013 Ultimate. In the experiment we set population size as 15. Food sources number is equal to 0.5 * population size. The number of initial time scout bees is equal to the follow bee, which scale is equal to 0.5 * population size.

Five DAGs generated randomly with TGFF tool are regarded as a sample set to compare the test results of the original ABC algorithm and the improved ABC (I-ABC) algorithms. The parameter settings are shown in Table 4.

Table 4. Parameter settings
Full size table

The comparison results between the ABC and the I-ABC algorithms are shown in Table 5.

Table 5. Comparison results between the ABC and the I-ABC algorithms
Full size table

To illustrate the effectiveness of the I-ABC algorithm, its performances are shown in Figs. 2 and 3.

Fig. 2.
figure 2

Comparison of two algorithms over the average solution and the average execution time.

Full size image
Fig. 3.
figure 3

Comparison results between the ABC and the I-ABC algorithms (132 nodes).

Full size image

According to the comparison in Table 5, Figs. 2 and 3, data could be analyzed from the following three aspects:

The Local Search Ability:

Although the number of iterations is reduced from 1000 to 900, the optimal solution of the improved algorithm is not only not worse, even better than that of the original algorithm. It is more obvious for the case of 52 nodes. From 30 nodes to 132 nodes, the quality of the solution increases about the 21.27%, 23.02%, 18.11%, 14.57%, 3.37% respectively. Meanwhile the time-consumed is reduced, and the power-consumed is the similar. Therefore, the I-ABC algorithm shows better local search ability.

The Solution Accuracy:

The D-value between the worst solution and the optimal solution in the I-ABC algorithm is reduced obviously. The final solution is also reduced significantly. For the case of 132 nodes, the final solution reduced about 3.5%, so the algorithm’s accuracy is improved.

The Convergence Speed:

When the consumed power is substantially the same, the improved algorithm can reduce the average execution time of the task.

From what we have been discussed above, we can get a conclusion that the precision of optimal solution of the I-ABC algorithm is higher than that of the original ABC algorithm, and the average execution time is reduced. The I-ABC algorithm is more efficient.

5 Conclusion

ABC algorithm has the features of less parameter and strong robustness, for which it is used in task assignment in HMA. Based on the original ABC algorithm, the neighborhood search scheme is proposed to solve the problems of low precision, slow convergence and poor local search ability. The experimental result shows that, in the case of less iterations, the I-ABC algorithm reduces the task execution time, and in case that the power-consumed obeys the restrictive conditions, the I-ABC algorithm reduces average solution with reduced numbers of iteration. D-value between the worst solution and the optimal solution is also reduced. The task assignment in HMA could be more efficient with the I-ABC algorithm.