Presenting an Algorithm for Tasks Scheduling in Grid Environment along with Increasing Efficiency by using Fuzzy Models

Presenting an Algorithm for Tasks Scheduling in Grid Environment along with Increasing Efficiency by using Fuzzy Models

• 1.
  International Journal ofComputer Applications Technology and Research Volume 5– Issue 5, 312 - 319, 2016, ISSN:- 2319–8656 www.ijcat.com 312 Presenting an Algorithm for Tasks Scheduling in Grid Environment along with Increasing Efficiency by using Fuzzy Models Abolfazl Jafari Department Of Computer Engineering, Islamic Azad University. Sari, Iran Homayoun Motameni Department Of Computer Engineering, Islamic Azad University. Sari, Iran Alireza Ghonoodi Department Of Computer Engineering, Islamic Azad University. Sari, Iran Abstract: Nowadays, human faces with huge data. With regard to expansion of computer technology and detectors, some terabytes are produced. In order to response to this demand, grid computing is considered as one of the most important research fields. Grid technology and concepts were used to provide resource subscription between scientific units. The purpose was using resources of grid environment to solve complex problems. In this paper, a new algorithm based on Mamdani fuzzy system has been proposed for tasks scheduling in computing grid. Mamdani fuzzy algorithm is a new technique measuring criteria by using membership functions. In this paper, our considered criterion is response time. The results of proposed algorithm implemented on grid systems indicate priority of the proposed method in terms of validation criteria of scheduling algorithms like ending time of the task and etc. Also, efficiency increases considerably. Keywords: Grid scheduling, Mamdani fuzzy system, execution time, membership functions 1. INTRODUCTION The computing grid is a software and hardware ultra structure and it provides stable, universal, cheap, compatible and reliable accessing to computing resources of the network. In grid environment, tasks are not individually executed in a system. These tasks are divided into subtasks, and each of them is transferred to resources that are the member of grid for execution, Resources of the network are connected to each other by using connection links. A link provides communication and information exchange between two related computers. RMS communicates with all network computers in star topology. The task of RMS is to distribute subtasks between computers and to receive their results. Suppose that we have m machines Mj=(j=1,…,), and these machines process n tasks in the form of Ji=(j=1,…,n). In this way, a scheduler for j task is dedication of one or more machines in various times to execute that task. There are two sets in grid environment scheduling. as follows: 1) Tasks set, 2) computing elements. The purpose of scheduling algorithm is to schedule applications on computing resources transferred by various users to grid systems. Tasks scheduling in grid involves three basic stages: The first stage: resources detection that is accessible resource detection. In this step, resources used to solve the problems are detected and identified. The second stage: Information collection. In this step, information like speed of resource computing, its failure rate, communication like band width of resource, resources management system and etc are collected by schedules. Then, the best set involving resources and tasks; are selected according to tasks characteristics and related information. The third stage: Task execution. This stage involves execution of task, collecting the results and finally cleaning up the memory and being prepared for next scheduling. The policies of tasks scheduling are divided into two main groups. The first group is system-oriented group, while purpose is to increase throughout of the system to decrease response time of whole system and to create a load balance or combining them. These kinds of scheduling algorithms have high performance Unpredictable, insecure and dynamic environment shares different services between various users. Due to heterogeneous and dynamic nature of grid, methods used in old systems cannot be used for grid scheduling, so new methods must be taken into account. The research and studies show that revelation optimization methods inspired from the nature have better
• 2.
  International Journal ofComputer Applications Technology and Research Volume 5– Issue 5, 312 - 319, 2016, ISSN:- 2319–8656 www.ijcat.com 313 effect and efficiency than other methods. Bat algorithm is a evolutionary model based on algorithms inspired from the nature. This algorithm is used to solve optimization problems. The proposed methods dynamically provide an optimized schedule to complete transferred tasks with minimum time of flowtime and makes pan. 2. LITERATURE REVIEW kang presented grid scheduling algorithm on the basis of self- adjustable tabu search in 2010. The proposed algorithm is suitable to reduce makespan of transferred tasks. In the proposed method, during scheduling time, the panel signs and keeps the list of local optimized solutions in future search process to obtain a simple search method for these solutions. In the proposed algorithms resources utilization is not considered the most important function in tabu search algorithm is neighboring function. In 2012, Egrawal proposed scheduling algorithm to minimize makes pan. The presented algorithm is based on standard genetic algorithm. This method requires a coding design, and should show all possible solutions for scheduling problem. Each special solution can be shown by a chromosome (scheduler) chromosomes are manipulated by two genetic operators and different methods until it stops. In order to manipulate it appropriately, a fitness function is required. In the proposed method it is supplied that tasks are independent. In 2009, Chang proposed scheduling algorithm to minimize MAKESPAN and loud balance. The proposed algorithm has all characteristics of ants optimization algorithm, and it is considered to decrease ending time of tasks by considering the load of each resource in ionic grid environment, and it is used in Taiwan University. This algorithm changes pheromone intensity according to resources conditions by applying the function of updating local and global pheromone, and it tries to minimize ending time, while the system loud balance is kept. Izakian suggested optimization algorithm of discrete particles swarm to solve the problem of tasks scheduling in 2010. In the proposed algorithm, minimization of Flowtime and Makespan is simultaneously taken into account. In this method, optimization algorithm of binary particles swarm has been used. The matrix element, are considered as zero and one. Each particle can be converted from Zero to one and vise versa. In 2009, Chen presented PSO-SA involving combination of optimization algorithm of particles swarm and gradual simulation to reduce MAKESPAN time in grid tasks scheduling. One of the main problems of optimization algorithm of particles swarm is to be deceived by local optimization. In order to solve this problems, gradual simulation that is considered as local search algorithms. Krouz presented GA-SA algorithm that is a combination of gradual simulation and genetic algorithm in 2010 to decrease MAKESPAN time in grid tasks scheduling. Since genetic algorithm searches whole problem space, and it performs in weak local search, it has been tried to solve this problem by combining it with thermal simulation that is considered as local algorithms 3. PROPOSED ALGORITHM By using the presented algorithm, Tasks of grid network can be appropriately scheduled. The difference between the presented method and previous methods is that both response time and cost can be considered in this method. In other words, by providing a balance between response time and cost of task, scheduling can be performed in the best way. The results show that, in this proposed algorithm, criteria for measuring the quality of scheduling algorithm (completion time, waiting time and etc) can be improved in comparison to other precisions methods. 3.1 Proposed algorithm description Since some parameters may be described indefinitely to schedule tasks, they should be designed in mechanism may so that these variables can be analyzed in tasks scheduling. One of variables can be analyzed in tasks scheduling. One of the methods to create this mechanism, Mamdani fuzzy system has been used and considered in this research. In our proposed algorithm, Mamdani system uses membership functions to convert input values to Fuzzy equivalents. Membership function is a function by which input data are converted to fuzzy data; that is, each input in fuzzy system is converted to the number from one to Zero. Membership function is defined for both input and output data. There are various types of membership functions such as trapezoidal, triangular, sigmoid and Gaussian membership functions. In this research, trapezoidal membership function is used to convert indefinite input parameters. Since input variables of the system should be converted to fuzzy values, system input variables should be firstly explained as follows:
• 3.
  International Journal ofComputer Applications Technology and Research Volume 5– Issue 5, 312 - 319, 2016, ISSN:- 2319–8656 www.ijcat.com 314 3.2 Input variables 1- In order to obtain the response time in a system, criteria of processes priority, computing power of processes and input and output operation speed are used. Now we explain these criteria. Processing priority: This criterion identifies priority of each processing for execution. In order to measure processing priority two criteria involving burst time and real priority of processing are used. After inserting above values, these values are converted to Fuzzy equivalents by using membership functions. 𝝁 𝒃 = 𝟏 − 𝒂𝒄𝒕𝒖𝒂𝒍 𝒃𝒖𝒔𝒓𝒕 𝒕𝒊𝒎𝒆 𝐦𝐚𝐱𝐢𝐦𝐮𝐦 𝒃𝒖𝒓𝒔𝒕 𝒕𝒊𝒎𝒆+𝟏 𝝁 𝒑 = 𝒂𝒄𝒕𝒖𝒂𝒍 𝒑𝒆𝒓𝒊𝒐𝒓𝒊𝒕𝒚 𝐦𝐚𝐱𝐢𝐦𝐮𝐦 𝒑𝒆𝒓𝒊𝒐𝒓𝒊𝒕𝒚+𝟏 After measuring above mentioned values, new priority is introduced as follows. In other words, the process whose processing time requires less execution time and the process that has higher real priority are executed soon. 𝝁 𝒏𝒆𝒘 = 𝐦𝐚𝐱(𝝁 𝒃, 𝝁 𝒑) After detecting and identifying the new priority for each process, by using “linguistic Variables” of low, intermediate and high: this criterion is converted to equivalent linguistic variable. Diagram of membership function of priority parameter is as follows. Figure. 1 Diagram of membership function of priority parameter 2- Next input criterion of Mamdani inference system of response time is processors’ power. It’s clear that if computing power of processors is high, they will be executed quicker, and finally the response time is low, In order to state this parameter by using linguistic variables, variables of ‘weak, normal and strong’ are used. Diagram of membership function of processors'’ power is as follows. Figure. 2. Diagram of membership function of processors; power 3) Next input criterion is execution speed of input and output operations. They involve operations of entering a process to the system (loading in the memory, and time between service completion and exiting it from the system. If these operations are performed with higher speed, response time is less. In order to state this parameter, linguistic variables including “low, normal and quick” are used. Following feature shows membership function of input and output operations speed parameter. Figure. 3. Diagram of membership function of execution speed in input and output operations 4) After identifying input membership functions, output membership function must be determined as well. In this way, the result of each rule is stated. Output of this algorithm belongs to five intervals between Zero and one, and they include “low, relatively low, intermediate, relatively high, high”. The following feature shows output fuzzy membership function. Figure. 4 . Diagram of membership function Response Time
• 4.
  International Journal ofComputer Applications Technology and Research Volume 5– Issue 5, 312 - 319, 2016, ISSN:- 2319–8656 www.ijcat.com 315 In the second stage, rules database is created. Generally, it can be said that, in fuzzy inference stage, linguistic variables are executed on the basis of input linguistic variables, system rules and membership function, (fuzzy values). In Mamdani method, the methods of “multiplication-maximum” and “minimum- maximum” are used. In our proposed method, “maximum- minimum” method is used for fuzzy inference. The formula used for this purpose is as follows. 𝑶𝑹 = 𝝁 𝑶𝑹 𝑨𝑩(𝒙) = 𝐦𝐚𝐱[𝝁𝑨(𝒙), 𝝁𝑩(𝒙)] 𝑨𝑵𝑫 = 𝝁 𝑨𝑵𝑫 𝑨𝑩(𝒙) = 𝐦𝐢𝐧[𝝁𝑨(𝒙), 𝝁𝑩(𝒙)] After identifying formula, we follow fuzzy rules of knowledge base. According to input criteria and linguistic variables, rules of knowledge base are defined as follows. Table 1. The rules of knowledge base of Mamdani fuzzy system Response Time C on dition R ule H igh t hen (priority is low AND power of processor is weak AND speed of input/output is slow) R 1 if H igh (prio rity is low AND power of processor is weak AND speed of input/output is average) R 2 S lightly high (priority is low AND power of processor is weak AND speed of input/output is high) R 3 S lightly high (priority is low AND power of processor is normal AND speed of R 4 input/output is slow ) S lightly high (priority is low AND power of processor is normal AND speed of input/output is average ) R 5 A verage (priority is low AND power of processor is normal AND speed of input/output is quick ) R 6 A verage (priority is low AND power of processor is strong AND speed of input/output is slow) R 7 A verage (priority is low AND power of processor is strong AND speed of input/output is average) R 8 A verage (priority is low AND power of processor is strong AND speed of input/output is quick) R 9 A verage (priority is average AND power of processor is weak AND speed of input/output is slow) R 10 A verage (priority is average AND power of processor is weak AND speed of R 11
• 5.
  International Journal ofComputer Applications Technology and Research Volume 5– Issue 5, 312 - 319, 2016, ISSN:- 2319–8656 www.ijcat.com 316 input/output is average) S lightly low (priority is average AND power of processor is weak AND speed of input/output is high) R 12 A verage (priority is average AND power of processor is normal AND speed of input/output is slow ) R 13 S lightly low (priority is average AND power of processor is normal AND speed of input/output is average ) R 14 S lightly low (priority is average AND power of processor is normal AND speed of input/output is quick ) R 15 S lightly low (priority is average AND power of processor is strong AND speed of input/output is slow) R 16 S low (priority is average AND power of processor is strong AND speed of input/output is average) R 17 S low (priority is average AND power of processor is strong AND speed of R 18 input/output is quick) A verage (priority is high AND power of processor is weak AND speed of input/output is slow) R 19 A verage (priority is high AND power of processor is weak AND speed of input/output is average) R 20 S lightly low (priority is high AND power of processor is weak AND speed of input/output is high) R 21 A verage (priority is high AND power of processor is normal AND speed of input/output is slow) R 22 A verage (priority is high AND power of processor is normal AND speed of input/output is average ) R 23 S lightly low (priority is high AND power of processor is normal AND speed of input/output is quick ) R 24 S lightly low (priority is high AND power of processor is strong AND speed of R 25
• 6.
  International Journal ofComputer Applications Technology and Research Volume 5– Issue 5, 312 - 319, 2016, ISSN:- 2319–8656 www.ijcat.com 317 input/output is slow) L ow (priority is high AND power of processor is strong AND speed of input/output is average) R 26 L ow (priority is high AND power of processor is strong AND speed of input/output is quick) R 27 Now, we want to reduce some rules of this knowledge base by using an algorithm; as a result, complexity of proposed Mamdani fuzzy system decreases. Numbers 1-3 are respectively assigned to each of linguistic variables showing criteria. By considering input criteria and linguistic variables of these criteria, matrix is as follows: Table 2. Converting the rules of knowledge base to numerical equivalent 1 1 1 1 1 1 2 1 1 1 3 2 1 2 1 2 1 2 2 2 1 2 3 3 1 3 1 3 1 3 2 3 1 3 3 3 2 1 1 3 2 1 2 3 2 1 3 4 2 2 1 3 2 2 2 4 2 2 3 4 2 3 1 4 2 3 2 5 2 3 3 5 3 1 1 3 3 1 2 3 3 1 3 4 3 2 1 3 3 2 2 3 3 2 3 4 3 3 1 4 3 3 2 5 3 3 3 5 As it is observer in this table, the first-third column of the left side shows criteria values of Mamdani fuzzy system. The last column shows output criterion values of Mamdani fuzzy system. Now, we want to simplify these rules by using karnaugh map. The following karnaugh map demonstrates knowledge base rules of Mamdani fuzzy systems. karnaugh map of the proposed Mamdani fuzzy system 1 1 2 2 2 3 3 3 3 3 3 4 3 4 4 4 5 5 3 3 4 3 3 4 4 5 5 In this table, the rows show the first criteria, table the columns indicate the second and third criterion, Also are want to simplify the above mentioned table on the basis of karnaugh map. As an example, if we are going to simplify some cells of the table involving the value of 2, we consider the following mode:
• 7.
  International Journal ofComputer Applications Technology and Research Volume 5– Issue 5, 312 - 319, 2016, ISSN:- 2319–8656 www.ijcat.com 318 Table 3. Classification of karnaugh map with numerical values of 2 1 1 2 2 2 3 3 3 3 3 3 4 3 4 4 4 5 5 3 3 4 3 3 4 4 5 5 =1)OR3=2)] AND [(x2=1) OR(x2=1) AND [(x1If((x =2final=3)]) THEN X3(x=2)OR3(x In this rule, X1-X3 shows input criteria, and Xfinal demonstrated output parameter. Table 4. The rules of knowledge base after simplification Rule Condition Response Time Rule R1 If((x1=1)AND (x2=1)AND(x3=1 OR 2)) HIGH R1 R2 If((x1=1) AND [(x2=1) OR(x2=2)] AND [(x3=1)OR (x3=2)OR (x3=3)]) THEN SLOWLY HIGH R2 According to the rules obtained from above table, it is observed that the rules reduce from 27 to 11 rules, and in this case, complexity of Mamdani system decreases. For example, we consider the action of and as 8 units, then we have: For 27 rules: Execution time 27*2*2=108 For 11 rules: Execution time=22*2+21*1=65 3.3 Case Study Now, we want to implement our proposed algorithm on a system, and measure reliability and response time in the mentioned methods. In case studies, we try to find small and comprehensive examples. In this case, there isn't any complexity, and it is a small sample of other big and real examples. The example of bank ATM lacks much complexity, and it involves architecture products. In this example, appropriate architecture frame of CαISR has been taken into account. We compute reliability and response time by using the proposed method and executable model simulation. 3.4 Implementation The following table shows the values of input criteria in the proposed system for processes. Table 5. The values of each input parameters ATM system S.I/OP.O.PA.PET 43118 9732 2221 5964 3653 781112 81713 ET is execution time of the process, A.P is real priority of the process, P.O.P refers to the processor's power and S.I/O points to execution speed of input and output operations. Also, it is supposed that all processes enter the system in zero time. After entering required parameters of proposed Mamdani system, we should determine the priority of processes for execution by using the mentioned membership function of the algorithm. The following table shows this procedure as well as possible. Table 6. converting each value of input parameters to fuzzy equivalents Linguistic variable for new priority μnewμpμb Low0.0830.08330.0528 High0.8950.250.8948 High0.950.1660.9474 High0.790.50.7895 High0.840.41660.8422 High0.9170.91660.3685 Average0.580.58330.3158 After obtaining a new priority for processes, execution procedure of these processes is as follows: P3,P6,P2,P5,P4,P7,P1 After identifying execution procedure of processes, the response time is as follows. Waiting time= 14.86 Response time= 33 After determining input parameters positions, we follow the heart of Mamdani system called inference system of knowledge base. After implementing Mamdani system in CPN, we use MATLAB to obtain output results and to display output membership functions by using input membership functions. X1 X2X3
• 8.
  International Journal ofComputer Applications Technology and Research Volume 5– Issue 5, 312 - 319, 2016, ISSN:- 2319–8656 www.ijcat.com 319 Figure 5. Obtained diagram for response time by implementing the system on MATLAB As it can be observed in the figure, we can measure response time of ATM system by using simple Mamdani fuzzy system. 4. CONCLUSION Computing grids provide inexpensive and reliable accessing to others, computing resources. These recourses are heterogeneous, and they are distributed. Also, they are commonly used. On the other side, resources in grid belong to different organizations having managerial policies, models and costs for various users in different time. In this way, owners and users of resources have different objectives, strategies and different supply and demands. In order to manage such a complex environment, common methods trying to optimize efficiency in system level cannot be used to manage the resources. In this thesis, a new method has been presented to schedule tasks in computing grid environment. In this method applied on the basis of Mamdani fuzzy system, execution time parameter is considered to improve efficiency and performance. In this algorithm, parameters required to evaluate the response time are firstly calculated by using membership functions in Mamdani fuzzy system. Then, the criterion of response time is measured for Mamdani fuzzy system by using output MATLAB software. The results indicate priority of the proposed algorithm in comparison with other previous algorithms. 5. SUGGESTIONS One of the ideas stated about heuristic algorithm is to study and present new scheduling methods combining other parameters like reliability, load balance and etc and obtaining interesting results. In terms of using Mamdani fuzzy system algorithm, it can be proposed that this algorithm is used in combination with other algorithms. Another suggestion is using some mechanisms for applications classification and dividing the problems to subtasks. If we can do this task by a mechanism with high precision and speed and by considering tasks duration as a determinant of load balance in distributed systems especially grid system, then scheduling precision and speed will be high. In this case, resources are appropriately dedicated, and efficiency and performance increases in grid system. Future suggestions a terms of scheduling in grid environment are as follows: 1) Studying the methods of error tolerance in proposed algorithms 2) Presenting scheduling in hierarchical order 3) Measuring several parameters in Mamdani fuzzy system 6. REFERENCES [1] Afzal, A., McGough, A.S., Darlington, J., "Capacity planning and scheduling in Grid computing environment", Journal of Future Generation Computer Systems 24 , pp 404-414, 2008. [2] BenDaly Hlaoui Y., Jemni BenAyed L.; "Toward anUML-based Composition of Grid Services Workflows",Research Unit of Technologies of Information and Communication, Tunisia, ACM,AUPC’08, July 2008. [3] . Dai, Y.S., Levitin, G., "Optimal Resource Allocation for Maximizing Performance and Reliability in Tree- Structured Grid Services", IEEE Transaction on Reliability, Vol. 56, No.3, September 2007. [4] Dai, Y.S., Xie, M., Poh, K.l., "Reliability of grid service systems", Computers & Industrial Engineering 50, pp.130-147, Elsevier, 2006. [5] Foster, I., Kesselman, C., The Grid 2: Blueprint for a New Computing Infrastructure, Los Alios, Morgan- Kuffman,2003. [6] G. Murugesan1, An Economic-based Resource Management and Scheduling for Grid Computing Applications, IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 2, No 5, March 2010 [7] Kordic V., Petri Net Theory and Applications, Chapter:Model Checking of Time Petri Nets, Chapter Author:Boucheneb H., Hadjidj R., I-Tech Education and Publishing, Vienna, Austria, First Edition, February 2008. [8] Levitin, G., Dai, Y.S., "Service reliability and performance in grid system with star topology", Reliability Engineering and System Safety 92, pp. 40-46, Elsevier, 2007. [9] Li, M., Baker, M., The Grid Core Technologies, John Wiley & Sons Publishing, 2005 [10] Yagoubi, B., Slinani, Y., "Task Load Balancing Strategy for Grid Computing", Journal of Computer Science 3 (3),pp. 186-194, 2007 [11] Saeed Parsa. Fereshteh- Azadi Parand. 2012.Estimation of service reliability and performance in gr id environment: Journal of King Saud Univer sity Engineer ing Sciences vol: 24,pp: 151 157.. Cihan H. Dagli. 2011. Modified SPEA2 for Probabilistic Reliability Assessment: Procedia Computer Science volume 6 ,pp: 435 44.