تحمل گسل الگوریتم های ژنتیکی سلولی سه بعدی پویا

This paper proposes a new dynamic and algorithm-based approach to achieve fault tolerance using 3D cellular genetic algorithms (Dynamic Fault-Tolerant 3D-cGA). The proposed algorithm is an improved version of our previous algorithm (Fault-Tolerant 3D-cGA) that introduces and utilizes a dynamic adaptation feature to achieve further improvement. In Dynamic Fault-Tolerant 3D-cGA, faulty individuals are isolated and the maximum number of fitness evaluations is recalculated to adapt to faults encountered. To improve the performance of the algorithm, a mitigation technique is integrated into our algorithm by introducing an explicit migration operator. A benchmark of well-known real-world and test problems is used to test the effectiveness of the algorithm in order to investigate the influence of adaptation schemes and migration on algorithm performance. Faulty critical system data is tackled in conjunction with various fault ratios. To illustrate the improvement achieved, Dynamic Fault-Tolerant 3D-cGA is compared with Fault-Tolerant 3D-cGA, the previously proposed algorithm. The overall results demonstrate the ability of Dynamic Fault-Tolerant 3D-cGA to maintain system’s functionality despite an increasing number of faults with up to 40% of processing elements (PEs), and clearly illustrate the importance of migration. Significant improvements in the performance of the algorithm, measured as efficiency, efficacy, and speed, are achieved, especially when migration is employed.

Evolutionary Algorithms (EAs) have been widely employed for different applications. This paper targets EAs’ application to the design of Fault-Tolerant systems. The considerable reduction in feature sizes of electronic circuits increases the possibility of transient errors to occur; in particular, single event upsets (SEUs) [33]. For this reason, there is high demand for implementing efficient and reliable high-performance systems that can quickly adapt to different failures. EAs are powerful optimization techniques that have shown success and universal applicability in different fields. They have proved their ability to solve problems of diverse complexities, along with considerable gains in terms of reliability, scalability, and efficiency due to their inherent parallelism. They work over a population of potential solutions (individuals) and apply simple stochastic operators that push the population towards better solutions. They are classified into either serial or parallel search techniques according to the way individuals communicate with each other [30]. Serial versions use a single population, while parallel versions use a structured population. There are several parallel models; the two most popular models are distributed (dEAs) and cellular (cEAs) evolutionary algorithms. In dEAs, the population is divided into multiple subpopulations (islands), where each of them is assigned to a processing element (PE). In this model, each island is evolved independently, and interactions between individuals occur by exchanging a number of individuals among islands (i.e., migration). On the other hand, in cEAs the population is distributed over PEs arranged as nn-dimensional grid with wrapped edges (i.e., toroidal). In addition, each individual is assigned to a PE (or cell), and interactions among individuals occur through their defined local neighborhoods, where an implicit migration is applied due to the overlapped neighborhoods. The spatial arrangement of the population leads to better exploration and exploitation trade-off, which is the key for determining the behavior of the algorithm. The exploration is provided through the overlapped neighborhoods, and aims at enhancing the diversity of the population and avoiding premature stagnation. In contrast, the exploitation targets each neighborhood to improve the quality of the solutions; and can be controlled through genetic operators. Inappropriate balance between exploration and exploitation leads to inefficient search. There are several studies for controlling exploration/exploitation trade-off. Giacobini et al. [14], Alba and Troya [3], and Alba and Dorronsoro [1] showed that the balance between exploration and exploitation can be achieved through changing the size and shape of the neighborhoods and/or the grid’s shape. In later works, Simoncini et al. [27] and [28] proposed new selection techniques, namely, anisotropic and centric selections for tuning the exploration/exploitation trade-off. Based on the latter, another adaptive cEA was proposed in [4]. The grid’s topology also plays an important role in determining the performance of the algorithm. Research works surrounding cGAs are commonly concerned with their implementation on one- or two-dimensional grid topology. In this study, a 3D cubic topology is utilized. A cubic topology allows good solutions to spread quickly to all PEs due to its shorter diameter [10], as well as diverse degrees of exploration and exploitation. In past studies [9] and [19], a 3D architecture was utilized and investigated; the overall results showed improvements in the performance of the algorithm when compared with smaller grid dimensions. A further reason for using a 3D topology is its amenability to be implemented with new advanced custom silicon chip technologies to achieve added significant benefits, such as fast operation, reduction in power consumption, new design possibilities, heterogeneous integration, circuit security, and wide bandwidth [12]. In this study, a cGA is employed because it is one of well-known cEA techniques. cEAs and cGAs in particular showed not only their ability to solve problems of different complexities, but also exhibit speedup in computation time, robustness, ability to escape local optima, and therefore achieve high efficiency and efficacy [2]. Consequently, cGAs’ suitability for real-time applications increases. This work aims to introduce a new dynamic 3D-cGA, which is tolerant to SEU faults targeting PE’s registers that correspond to critical data (in this study, fitness score registers). Given the fact that there are various fault scenarios, the most critical fault scenario (which will be defined and discussed later) is tackled in this study. The basis of our design was proposed in our previous study [5], which is improved by introducing a dynamic adaptation feature in this study. The first objective of this study is to maintain system reliability even with a growing number of faulty registers or PEs (recall that in a cGA each PE holds one individual, therefore comprises one fitness score register). The other objective is to improve the performance of the algorithm by mitigating the impact of faults. The paper is structured as follows. Section 2 presents an introduction to fault tolerance. The canonical model for cGAs implemented on a 3D architecture is discussed in Section 3. Dynamic Fault-Tolerant 3D-cGA is proposed in Section 4. The benchmark problems selected to evaluate and analyze the proposed algorithm are described in Section 5. Section 6 presents the parameters used in experiments and the results obtained. Finally, concluding remarks are given in Section 7.

This study proposed a new algorithm, Dynamic Fault-Tolerant 3D-cGA, for handling failures that occur in individuals’ fitness score registers, due to SEUs in particular. The algorithm is based on the canonical model of cGAs and is a modified version of the past approach (Fault-Tolerant 3D-cGA [5]) that uses genetic diversity to identify and isolate faulty individuals. The worst-case fault model was tackled in conjunction with different fault ratios. Our main motivation for this study was to improve the reliability and performance of Fault-Tolerant 3D-cGA through dynamic control of the exploration/exploitation trade-off. The dynamic calculation of MaxGens based on fault ratio encountered helped to enhance the exploration. On the other hand, the exploitation was enhanced through the use of the proposed migration technique. To illustrate the improvements achieved, Dynamic Fault-Tolerant 3D-cGA was compared with Fault-Tolerant 3D-cGA in terms of efficiency, efficacy, and speed. Both algorithms demonstrated successful recovery for up to 40% faults, especially when the migration technique was employed. The use of migration as a mitigation technique to fault tolerance offers considerable improvements in efficiency, efficacy, speed, and reliability of the algorithms, especially for cases with high ratio of faults. In addition, migration plays an important role in controlling exploration/exploitation trade-off. Exploration and exploitation are the two main issues that determine the performance of EAs. The population diversity is improved by exploring the search space, while the optimum solution could be found by exploiting the fitness information. In this study, the best overall performance in terms of efficiency, efficacy, and speed was achieved with migration, owing to its effect in enhancing the local selection intensity and diversity. In conclusion, we note that the Fault-Tolerant 3D-cGA and Dynamic Fault-Tolerant 3D-cGA with migration showed the best performance, and the differences between the results obtained by both algorithms were insignificant. An exception was for View the MathML sourcefAck, in which case the Dynamic FT 3D-cGA with migration significantly outperformed the FT 3D-cGA with migration mainly in terms of efficacy and reliability. The best efficiency was achieved by FT 3D-cGA with migration; however, the lower number of generations was found to be due to the significant difference in the obtained search success rate.