Abstract: The article considers the problem of programmable logic device reconfiguration after a failure of logic elements. The task is relevant to areas such as space exploration and important industrial facilities management that use highly reliable fault-tolerant systems. The article considers the failures of logic elements in the configurable logic blocks. For optimal reconfiguration logic modules must be placed on a programmable logic device without using faulty logic elements, while minimizing occupied area, the bond lengths and delays. The first step in solving the problem is to choose compactly located logic elements that will be involved in the implementation of the circuit. Compactness is understood as the minimum amount of information necessary to describe the set of logic elements. This task can not be solved exactly and effectively, but can be approximately solved by using various heuristics, including genetic algorithms. This article describes several well-known approaches to the problem and offers an original two-level coding method for constructing a genetic algorithm that takes into account features of the problem and uses standard genetic operators. The proposed algorithm is implemented in practice in the form of a computer program to compare its performance with some other algorithms. Comparison of different heuristic algorithms in terms of accuracy of the solution and estimated speed of the proposed algorithm are given. One can say that the proposed genetic algorithm works on average longer than other heuristic algorithms, but finds a more accurate solution. This leads to a reduction of reconfiguration time and, thereby, increase availability ratio of the programmable logic device.

Keywords: programmable logic devices, reconfiguration, reliability, genetic algorithm.

ACM Classification Keywords: I.2 Artificial Intelligence: I.2.8 Problem Solving, Control Methods, and Search - Heuristic methods, B.8 Performance and Reliability: B.8.1 Reliability, Testing, and Fault-Tolerance?

Link:

ДВУХУРОВНЕВЫЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ РЕКОНФИГУРАЦИИ ПРОГРАММИРУЕМЫХ ЛОГИЧЕСКИХ ИНТЕГРАЛЬНЫХ СХЕМ (Two-level genetic algorithm for programmable logic devices reconfiguration)

Алексей Городилов

http://www.foibg.com/ijitk/ijitk-vol08/ijitk08-02-p05.pdf