Modeling, Verification and Evaluation of Multiprocessor Scheduling using Extended CBRLA Algorithm

Abstract

Nowadays Multi-processor systems are used extensively in personal computers, Cell phones and also in distribution systems. Scheduling of operations in distributed computing systems is of particular importance for optimal use of existing computing machines and also spending less time for running time consuming algorithms. Regarding to the issue that complex computing operations cannot run in an acceptable time frame, we divided them into finely smaller tasks and run those using distributed computing system, by relying on the distributed nature of the tasks. Generally, in the issue of multi-processor timing, the aim is parallel execution of a program on multiple processors, So that according to tasks' execution time and relation between processors, the time of execution of total program will decrease. Timing techniques are divided into two groups, homogeneous and heterogeneous. One of the methods of assignment of tasks in heterogynous computing systems is CBR-LA, where it is a combination of case base reasoning (CBR) is and learning automata (LA). In this paper at first step, Basic CBR method is modeled using colored Petri net. Then its operation is evaluated using simulating of the model. One of our aims in second phase is improving accuracy of scheduling algorithm, in which performance and efficiency of the offered algorithm will be increased. On third phase, we used model for simulation, by applying probability distribution functions of events, and will achieve our needed statistics about performance, average waiting time and average termination time of tasks.