Supercomputer resource planning method based on colonial competition algorithm

Abstract

The evolution of computing is such that it can be assumed as the fifth basic element after water, electricity, gas and telephone. In recent years, increasing attention has been paid to cloud computing.  Cloud computing is a large-scale distributed model that provides a scalable and virtualized collection of managed computing power, storage space and services through the Internet to customers.

The problem of allocating resources in cloud computing and scheduling each of the user's tasks on existing virtual machines is an NP-Complete problem that many algorithms have been presented to solve it. But none of these algorithms are able to meet the requirements related to speed and accuracy in cloud computing environments. In this research, a combination method of colonial competition algorithm and local search is proposed to solve this problem. By creating an initial empire, this algorithm tries to improve the possible answers by applying the stages of the colonial competition algorithm. In order to avoid premature convergence, the colonial competition algorithm is combined with a local search algorithm. The proposed hybrid algorithm uses a convergence detection mechanism based on the similarity coefficient and executes the local search method when the colonial competition method undergoes early convergence.

The quality of the answers and the efficiency of the proposed algorithm were compared with the efficiency of round robin, ant colony and genetic algorithms.

Results: The results obtained show that the proposed algorithm is faster than the two ant colony algorithms and the genetic algorithm in terms of execution time quality. slow down In addition, the proposed algorithm performs better than the other compared algorithms in terms of the quality of the answers.

Introduction:

In recent years, increasing attention has been paid to cloud computing. The most welcome of this technology is in the multimedia industry and analysis systems. In cloud computing, some decisions are known as scheduling decisions. The planning process determines the necessary resources to produce the set of activities required for scheduling [Baker00]. Scheduling is the allocation of limited resources to activities over time, in order to optimize one or more objective functions [Baker00]. The problem of scheduling cloud computing resources is one of the most important scheduling problems that has attracted the attention of many researchers. The resource scheduling problem is considered a very hard problem among NP-hard problems [Yu12, Garey76].

The problem of scheduling and allocating resources in a cloud and a network is a very hard problem, and as a result, the search space of this problem is so large that if an algorithm wants to examine this space sequentially and find the best solution, it will need exponential time. Among the innovative algorithms that have been used in the field of scheduling and resource allocation, we can mention the ant colony algorithm [Zhu12, Chen09] and the genetic algorithm [Javier07].

Ant colony algorithm is a type of algorithm based on collective intelligence that is inspired by studies and observations on ant colonies [Diargo96]. In the real world, ants first randomly wander around to find food. Then they return to the nest and leave a trail of pheromone[1] on the way. When an ant moves randomly and alone, encountering a path that has more pheromone effect, it is likely to choose the above path and reinforce it with the pheromone it leaves behind. Although the algorithms based on the ant colony presented [Zhu12, Chen09] provide parallel scheduling for the problem of resource allocation in cloud computing, but for the efficient implementation of this algorithm, powerful parallel hardware is required and its implementation on a scheduler system will require considerable time. Checked. Genetic algorithm is a type of heuristic algorithm that got ideas from Darwin's "survival of the fittest" [2] theory [Eiben07]. Genetic algorithm can be classified as a type of evolutionary algorithm[3] that encodes potential solutions to a specific problem in the form of data structures similar to chromosomes[4].. Genetic algorithm can be categorized as a type of evolutionary algorithm [3] that encodes the potential solutions of a specific problem in the form of chromosome-like data structures [4] and applies recombination operators on these structures to preserve vital information.

Accordingly, in this paper, a method based on the colonial competition algorithm [Atashpaz07] is presented to solve the task scheduling problem. This algorithm is classified in the class of population-based heuristic algorithms, and as a result, it does not have the problems of traditional systematic methods. In addition, in the proposed method, local search has been used to prevent the algorithm from getting stuck in local optima, and for this reason, this algorithm shows a more intelligent behavior than the genetic algorithm in the conditions of local optima. In addition, the proposed algorithm does not require special hardware to be implemented and can perform much better than the ant colony algorithm in terms of time.

Colonial competition

Figure 2-8 shows the flowchart of the colonial competition algorithm [Atashpaz07]. Like other evolutionary algorithms, this algorithm, with a number of random initial populations, each of which is called a "country"; It begins. Some of the best elements of the population (equivalent to elites in the genetic algorithm) are selected as imperialists [5]. The rest of the population is also considered as a colony [6]. The colonists, depending on their power, these colonies with a specific process that follows; They pull towards themselves. The total power of any empire depends on both its constituent parts, the imperialist country (as the central core) and its colonies. Mathematically, this dependence is modeled by defining the power of the empire as the total power of the imperialist country, plus a percentage of the average power of its colonies.

With the formation of early empires, the imperialist competition between them begins. Any empire that cannot succeed in the colonial competition and increase its power (or at least prevent its influence from decreasing), will be removed from the colonial competition scene. Therefore, the survival of an empire will depend on its ability to absorb the colonies of rival empires and bring them under control. As a result, in the course of imperialist competition, the power of larger empires will gradually be increased and weaker empires will be eliminated. Empires will be forced to develop their colonies to increase their power. Over time, the colonies will become closer to the empires in terms of power, and we will see a kind of convergence. The ultimate limit of colonial competition is when we have a single empire in the world, with territories that are very close in terms of location to the imperialist country itself.

Key words:

Resource allocation, cloud computing, colonial competition algorithm, local search, NP-Complete.

Chapter 1:

Overview

Introduction

The evolution of calculations is such that it can be assumed as the fifth basic element after water, electricity, gas and telephone. In such a case, users try to access a service based on their needs and regardless of where it is located or how it is transformed. There are various examples of computing systems that try to provide such services to users. Some of these computing systems are: cluster computing[1], grid computing[2] and recently cloud computing[3].

In recent years, increasing attention has been paid to cloud computing. The most welcome of this technology is in the multimedia industry [4] and analysis systems. In 2008, the benefit of using cloud computing for commercial applications was estimated to be three to four times that of non-cloud systems [Stanoevska10]. Foster and his colleagues [5] [Foster08] define cloud computing as follows: "Cloud computing is a large-scale distributed model that is a scalable and virtual set made of managed computing power, provides storage space and services to customers through the Internet."

In cloud computing, some decisions are known as planning decisions[6]. The planning process determines the necessary resources to produce the set of activities required for scheduling [Baker00]. Scheduling [7] is the allocation of limited resources to activities over time, in order to optimize one or more objective functions [Baker00]. The problem of scheduling cloud computing resources[8] is one of the most important scheduling problems that has attracted the attention of many researchers.