Optimal Software Reliability and Optimal Multiprocessor Scheduling Problems

Abstract

The scheduling and mapping of the precedence-constrained task graph to processors is considered to be the most crucial NP-complete problem in parallel and distributed computing systems. Several algorithms including genetic algorithms have been developed to solve this problem [18], [47], [124], [136]. A common feature in most of these has been the use of chromosomal representation for a schedule. However, these algorithms are monolithic, as they attempt to scan the entire solution space without considering how to reduce the complexity of the optimization process. In the case of multiprocessor scheduling problems there is still no optimum scheduling algorithm available in literature that can be applied to every type of problems that can be represented using Directed-Acyclic-Graphs of job pool. There is still a need for an efficient algorithm that can results in minimum execution time and at the same time making maximum utilization of the resources. Keeping this in view, in the present thesis we have focused on developing a genetic based approach for minimizing the schedule length (makespan) of tasks as well as maximizing the utilization of the resources. Estimating the reliability of a software under development can help managers to make release decisions during the testing stage itself. Several methods have been proposed in literature to estimate the defect content using a vast variety of software reliability growth models (SRGMs) [3], [53], [60], [107], [113]. SRGMs have certain underlying assumptions which are usually not met fully in practice. However, empirical evidence has shown that many SRGMs are quite robust despite these assumption violations. The problem is that, because of assumption violations in practice, it is often difficult to decide in a given situation which model to apply in practice. Keeping this in mind we propose in the present thesis a method for selecting an appropriate SRGM to make release decisions. The proposed method provides guidelines on how to select an appropriate SRGM which may be used to decide on the best model to be used in practice for estimating the likely release date during testing stage itself and estimate the cost of the software under development. Thesis consists of ten chapters. Chapter 1 is introductory in nature. Chapters 2 to 4 deal with multiprocessor scheduling problems, chapters 5 to 9 deal with optimal software reliability problems. Chapter 1 underlines the main objectives and motivations behind carrying out the research reported in this thesis. A brief review of the relevant literature available on the subject has also been given here. The chapter closes with a brief summary of the work presented in the thesis. In chapter 2, a genetic algorithm based approach has been proposed for multiprocessor task scheduling to minimize the makespan of tasks represented using Directed acyclic graphs. The algorithm uses suitably designed encoding and crossover approaches in assigning priorities dynamically to the tasks of the task graph. The proposed encoding and priority assignment techniques are simple and easy to implement. The proposed algorithm for minimizing the total processing time i.e. makespan makes use of the heterogeneous earliest finish time heuristic algorithms. This heuristic based task to processor mapping technique is used to search for a solution in order to minimize makespan without violating precedence constraints and accelerate convergence speed of the proposed algorithm. The proposed algorithm has five components which are executed in a sequential order for a given number of iterations to achieve the optimal makespan. We have applied the developed algorithm to a total of 20 problems listed in appendix A. Out of these 7 are of homogeneous type and 5 of heterogeneous type. All these problems have been taken from literature. The remaining eight (which are comparatively of larger size) are randomly self-generated. The number of tasks in these problems varies from 9 to 120 and the number of processors varies from 2 to 6. Our simulation results show that the proposed algorithm yields results which are generally better than those given in literature like DCP (Dynamic critical Path), PETS (Performance effective task scheduling), HEFT (Heterogeneous Earliest Finish Time), PMC (Priority based multi chromosome) and BGA (Basic Genetic Algorithm). Moreover in most of the cases the obtained results are quite close to results obtained using exhaustive search. In chapter 3, we have further modified our algorithm developed in chapter 2 by adding one more fitness function to further improve it’s performance so as to achieve load balancing as well. The two fitness functions have been applied one after the other. The first fitness function is concerned with minimizing the total execution time (schedule length), and the second with the maximizing the load balance on each processor. The developed algorithm is tested on a total of fifteen problems taken from literature and given in appendix A. The performance of the proposed algorithm is also compared with the results of traditional heuristic scheduling techniques like HEFT, BGA and DCP. Our results show that the proposed algorithm outperforms the algorithms which are commonly used for this purpose. In Chapter 4, we focus on the problem of determining the optimal number of processors which are needed in a multiprocessor (homogeneous as well as heterogeneous) system so as to minimize the overall system cost. Results obtained in the case of homogeneous multiprocessor systems show that for a problem of fixed size with the increase in the number of processors, the execution time first decreases upto a certain stage and after that the speedup becomes zero. On the basis of this study it has been observed that 2 to 3 processors are in general sufficient for small size scheduling problems of upto 9 tasks on and 4 processors are sufficient for problems of size from 10 to 40 tasks. In fact not more than 8 processors are needed for problems of size up to 120 tasks. In the case of heterogeneous multiprocessor systems it is observed that one hardly needs more than three processors for executing medium size problems of upto 18 tasks and not more than 4 processors for executing problems of size up to 40 tasks. Infact in general it is observed that not more than 6 processors are required for problems up to 120 tasks. In chapter 5, a method for selecting the most appropriate reliability growth model that best fits the available detected fault data midway during its testing stage itself is proposed. In order to select an appropriate software reliability growth model, various comparison criteria have been proposed in literature to compare models quantitatively. Most of these take into account more than ten parameters. Our study has shown that the following relatively simple criteria can be used to rank competing software reliability models. 〖Rank Index〗_j=1/2 [〖RSq〗_j/(〖max〗_j^n (〖RSq〗_j))+(〖min〗_j^n (〖RMSE〗_j) )/〖RMSE〗_j ]. where symbols have their usual meanings explained in chapter. Competing models be then ranked in descending order of this rank index value, rank 1 being assigned to the model with the highest rank index value. In case there is a tie (two models getting close rank index values) then both be assigned same rank. For testing the effectiveness of the proposed criteria, it has been applied on ten datasets taken from literature and listed in appendix B. A comparison of the results obtained with corresponding results available in literature shows that the proposed approach is in general simpler and quite effective and faster in selecting the appropriate SRGM to depict the behavior of the actual observed failure data. Whereas in chapter 5 we confined ourselves to sixteen software reliability growth models, in chapter 6, the method proposed in chapter 5 is applied to select an appropriate model from a set of generalized software reliability growth models considering perfect and imperfect processes during the testing and debugging stages. We have used the proposed approach on eleven real software failure datasets taken from literature and given in appendix B to compare its relative performance on some of the currently used perfect and imperfect debugging models. In chapter 7, a genetic algorithm based technique has been proposed to estimate the unknown parameters of non-homogeneous Poisson process (NHPP) software reliability growth models (SRGMs). The objective function used in this case is: min J=√(∑_(t=0)^n▒〖[m(t)-μ(t)〗 ]^2 ) where m(t) is the actual number of observed failure, μ(t) is the estimated number of failures. The technique is used to estimate the unknown parameters of ten NHPP SRGMs and use it to rank ten data sets listed in appendix B. The performance of proposed technique is compared with results obtained using least squared estimation technique. The results show that it works well for estimating the unknown parameters of SRGMs, and it selects an appropriate SRGM faster with precision. In chapter 8, a method for predicting the release date of software during its testing stage is proposed. The method is based on selecting the most appropriate reliability growth model that best fits the available detected fault data midway during its testing stage and then using it to predict the likely release date of the software under development. The selected model can then be used to estimate the total number of expected errors in the software. By specifying the reliability level to be achieved before release one can also estimate as to how much additional testing time will be needed in order to achieve the specified value of reliability. The proposed method is tested on ten real datasets given in appendix B. The results show that in most of the cases prediction of release time midway during the testing itself is quite close to actual release date. A comparison of results with other approaches currently in use shows that proposed approach in general is more effective and can be used to estimate the likely release date much earlier. In chapter 9, an effort has been made to estimate the cost of software under development for achieving desired level of reliability. The main objective being to minimize the cost being incurred to achieve desired reliability level. The proposed method has been tested on a set of eleven real datasets collected from literature and given in appendix B. The comparison of with earlier methods show that the method is able to reasonably estimate the cost of software under development. Conclusions based on the present study and scope for possible future work in this field are finally drawn in the concluding chapter 10.