|
|
Fault tolerant systems design automation
Lojda, Jakub ; Plíva, Zdeněk (oponent) ; Steininger, Andreas (oponent) ; Sekanina, Lukáš (vedoucí práce)
If a digital system is required to maintain a high level of reliability, it must withstand the presence of naturally-emerging failures. Many of such systems utilize Field Programmable Gate Arrays (FPGAs). One of the approaches to increase the system's reliability is the insertion of the so-called Fault Tolerance (FT) mechanisms. It is, however, a significant challenge to design systems to be FT. In this thesis, an approach is designed and researched, capable of automatically transforming an unhardened design into its FT version. The thesis emphasizes the generality of such a process, which allows for the reusability of the methods among various description formats, languages, and abstraction levels. This thesis describes the proposed method and its main aspects: the source code modification approaches, design strategies, and acceleration of FT parameters measurement. Last but not least, design flows that target the minimization of required measurements are proposed, which significantly accelerates the complete automated design of the FT system. Several cases were experimentally studied during the research presented in this thesis. Multiple circuits described in different languages were targeted with various reliability metrics to cover multiple scenarios. The first steps use a robot controller written in C++ as a target for evaluating the source code manipulations and the so-called critical bits representation of an FPGA design. After that, our C++ benchmark circuits were used instead of the robot controller. At first, a strategy based on the Multiple-choice Knapsack Problem (MCKP) was used to automatically select the most suitable hardening from available hardening schemes (e.g., Triple Modular Redundancy, or N-modular Redundancy). The proposed design strategy found a solution with 18% fewer critical bits while even lowering the design size overhead compared to the previous approach with the static allocation of FT mechanisms. After that, means of FT mechanism insertion were implemented for VHDL. VHDL benchmarks were also used with the MCKP strategy to find solutions with the best Median Time to Failure (a.k.a. t50). For the actual case study, circa 25% savings in the area were achieved compared to the reference design to which the FT mechanisms were assigned statically and manually. The method allows the user to constrain the available chip area and obtain the result optimal on reliability for this given area (under assumptions specified in the thesis). Also, system recovery was tested, which further improved the t50 results by 70%. Finally, a comprehensive case was studied on a real circuit, the FPGA reconfiguration controller. This presents a method of finding a Pareto-frontier of optimal designs considering multiple criteria (i.e., power consumption, size, and Mean Time to Failure - MTTF). The method exploits the principles of dynamic partial reconfiguration.
|
|
|
OPTIMIZATION OF ALGORITHMS AND DATA STRUCTURES FOR REGULAR EXPRESSION MATCHING USING FPGA TECHNOLOGY
Kaštil, Jan ; Plíva, Zdeněk (oponent) ; Vlček, Karel (oponent) ; Kotásek, Zdeněk (vedoucí práce)
This thesis deals with fast regular expression matching using FPGA. Regular expression matching in high speed computer networks is computationally intensive operation used mostly in the field of the computer network security and in the field of monitoring of the network traffic. Current solutions do not achieve throughput required by modern networks with respect to all requirements placed on the matching unit. Innovative hardware architectures implemented in FPGA or ASIC have the highest throughput. This thesis describes two new architectures suitable for the FPGA and ASIC implementation. The basic idea of these architectures is to use perfect hash function to implement transitional function of deterministic finite automaton. Also, architecture that allows the user to introduce small probability of errors into the matching process in order to reduce memory requirement of the matching unit was introduced. The thesis contains analysis of the effect of these errors to overall reliability of the system and compares it to the reliability of currently used approach. The measurement of properties of regular expressions used in analysis of the traffic in modern computer networks was performed in the thesis. The analysis implies that most of the used regular expressions are suitable for the implementation by proposed architectures. To guarantee high throughput of the matching unit new algorithms for alphabet transformation is proposed. The algorithm allows to transform the automaton to accept several input characters per one transition. The main advantage of the proposed algorithm over currently used solutions is that it does not have any limitation over the number of characters that are accepted at once. Implemented architectures were compared with the current state of the art algorithm and 200MB memory reduction was achieve
|
|
|
Polymorphic circuits synthesis and optimization
Crha, Adam ; Plíva, Zdeněk (oponent) ; Fišer, Petr (oponent) ; Růžička, Richard (vedoucí práce)
This thesis deals with synthesis and optimization methods of polymorphic circuits. Ordinary and multi-functional synthesis and optimization methods are discussed. The main objective of this thesis is to introduce novel methodologies for scalable synthesis of multi-functional digital circuits. Despite the fact that several approaches have been proposed during recent years, those are applicable for small-scale circuits only or are based on various evolution-inspired techniques. Obviously, scalable synthesis methodology for complex multi-functional circuits does not exist yet. The proposed methodology is based on And-Inverter Graphs ( AIGs ) with built-in extension for multi-functional circuits where the employment of rewriting techniques reduces the area by sharing common resources of two different input circuits. Experiments performed on publicly available benchmark circuits demonstrate significant optimization achievements.
|
|
|
Metodika aplikace testu obvodu založená na identifikaci testovatelných bloků
Herrman, Tomáš ; Plíva, Zdeněk (oponent) ; Racek, Stanislav (oponent) ; Kotásek, Zdeněk (vedoucí práce)
Dizertační práce se zabývá analýzou číslicových obvodů popsaných na úrovni meziregistrových přenosů. Je v ní zahrnuta pouze problematika související s testovatelností obvodových datových cest, řadičem ovládajícím tok dat těmito cestami se nezabývá. Stěžejní částí práce je návrh konceptu testovatelného bloku (TB), pomocí něhož se obvod rozdělí na části, jež jsou plně testovatelné přes jejich vstupy a výstupy, přes takzvané hraniční registry bloku nebo primární vstupy/výstupy. Přínosem nové metodiky je také redukce počtu registrů v řetězci scan, do něhož jsou zařazeny pouze hraniční registry. Segmentací obvodu dosáhneme také zjednodušení generování testu rozdělením tohoto problému na více menších částí. Navržená metodika pro identifikaci TB v číslicovém obvodu využívá dvou vybraných evolučních algoritmů operujících na formálním modelu obvodu na úrovni RT.
|
|
|
Novel approach to polymorphism in gate-level digital circuits
Nevoral, Jan ; Plíva, Zdeněk (oponent) ; Stopjaková,, Viera (oponent) ; Růžička, Richard (vedoucí práce)
Nearly twenty years ago, a non-conventional approach to implementation of multifunctional circuits called polymorphic electronics was proposed. The concept of polymorphic electronics allows to implement two or more functions in a single circuit, whereas the currently selected function depends on the state of the circuit operating environment. Key components of such circuits are polymorphic gates. Since the introduction of polymorphic electronics, several dozens of polymorphic gates have been published. However, a large number of them do not meet reasonable parameters. As a result, perspective of their utilisation for real applications becomes rather bleak. This dissertation introduces a new approach to the polymorphic electronics. It is based on gates whose behaviour depends on polarity of dedicated power supply rails. The goal of this thesis is to show that such approach allows to design gates with significantly better parameters. In order to systematically design proposed gates at the transistor level, an evolutionary method based on Cartesian genetic programming was proposed. That allowed to design several sets of efficient polymorphic gates employing conventional MOSFET and emerging double-gate ambipolar transistors. These gate sets were arranged into a library which is currently freely available for other researchers. Furthermore, a number of more complex circuits based on proposed gates were designed in this thesis. It is demonstrated at various levels of circuit design (gate, RTL, application) that the proposed gate-level polymorphism provides significant advantages compared to the first generation of polymorphic gates, but it can also be competitive or even better compared to the conventional CMOS solutions.
|
|
|
Fault tolerant systems design automation
Lojda, Jakub ; Plíva, Zdeněk (oponent) ; Steininger, Andreas (oponent) ; Sekanina, Lukáš (vedoucí práce)
If a digital system is required to maintain a high level of reliability, it must withstand the presence of naturally-emerging failures. Many of such systems utilize Field Programmable Gate Arrays (FPGAs). One of the approaches to increase the system's reliability is the insertion of the so-called Fault Tolerance (FT) mechanisms. It is, however, a significant challenge to design systems to be FT. In this thesis, an approach is designed and researched, capable of automatically transforming an unhardened design into its FT version. The thesis emphasizes the generality of such a process, which allows for the reusability of the methods among various description formats, languages, and abstraction levels. This thesis describes the proposed method and its main aspects: the source code modification approaches, design strategies, and acceleration of FT parameters measurement. Last but not least, design flows that target the minimization of required measurements are proposed, which significantly accelerates the complete automated design of the FT system. Several cases were experimentally studied during the research presented in this thesis. Multiple circuits described in different languages were targeted with various reliability metrics to cover multiple scenarios. The first steps use a robot controller written in C++ as a target for evaluating the source code manipulations and the so-called critical bits representation of an FPGA design. After that, our C++ benchmark circuits were used instead of the robot controller. At first, a strategy based on the Multiple-choice Knapsack Problem (MCKP) was used to automatically select the most suitable hardening from available hardening schemes (e.g., Triple Modular Redundancy, or N-modular Redundancy). The proposed design strategy found a solution with 18% fewer critical bits while even lowering the design size overhead compared to the previous approach with the static allocation of FT mechanisms. After that, means of FT mechanism insertion were implemented for VHDL. VHDL benchmarks were also used with the MCKP strategy to find solutions with the best Median Time to Failure (a.k.a. t50). For the actual case study, circa 25% savings in the area were achieved compared to the reference design to which the FT mechanisms were assigned statically and manually. The method allows the user to constrain the available chip area and obtain the result optimal on reliability for this given area (under assumptions specified in the thesis). Also, system recovery was tested, which further improved the t50 results by 70%. Finally, a comprehensive case was studied on a real circuit, the FPGA reconfiguration controller. This presents a method of finding a Pareto-frontier of optimal designs considering multiple criteria (i.e., power consumption, size, and Mean Time to Failure - MTTF). The method exploits the principles of dynamic partial reconfiguration.
|
|
|
Fault tolerant systems design automation
Lojda, Jakub ; Plíva, Zdeněk (oponent) ; Steininger, Andreas (oponent) ; Sekanina, Lukáš (vedoucí práce)
If a digital system is required to maintain a high level of reliability, it must withstand the presence of naturally-emerging failures. Many of such systems utilize Field Programmable Gate Arrays (FPGAs). One of the approaches to increase the system's reliability is the insertion of the so-called Fault Tolerance (FT) mechanisms. It is, however, a significant challenge to design systems to be FT. In this thesis, an approach is designed and researched, capable of automatically transforming an unhardened design into its FT version. The thesis emphasizes the generality of such a process, which allows for the reusability of the methods among various description formats, languages, and abstraction levels. This thesis describes the proposed method and its main aspects: the source code modification approaches, design strategies, and acceleration of FT parameters measurement. Last but not least, design flows that target the minimization of required measurements are proposed, which significantly accelerates the complete automated design of the FT system. Several cases were experimentally studied during the research presented in this thesis. Multiple circuits described in different languages were targeted with various reliability metrics to cover multiple scenarios. The first steps use a robot controller written in C++ as a target for evaluating the source code manipulations and the so-called critical bits representation of an FPGA design. After that, our C++ benchmark circuits were used instead of the robot controller. At first, a strategy based on the Multiple-choice Knapsack Problem (MCKP) was used to automatically select the most suitable hardening from available hardening schemes (e.g., Triple Modular Redundancy, or N-modular Redundancy). The proposed design strategy found a solution with 18% fewer critical bits while even lowering the design size overhead compared to the previous approach with the static allocation of FT mechanisms. After that, means of FT mechanism insertion were implemented for VHDL. VHDL benchmarks were also used with the MCKP strategy to find solutions with the best Median Time to Failure (a.k.a. t50). For the actual case study, circa 25% savings in the area were achieved compared to the reference design to which the FT mechanisms were assigned statically and manually. The method allows the user to constrain the available chip area and obtain the result optimal on reliability for this given area (under assumptions specified in the thesis). Also, system recovery was tested, which further improved the t50 results by 70%. Finally, a comprehensive case was studied on a real circuit, the FPGA reconfiguration controller. This presents a method of finding a Pareto-frontier of optimal designs considering multiple criteria (i.e., power consumption, size, and Mean Time to Failure - MTTF). The method exploits the principles of dynamic partial reconfiguration.
|
|
|
Polymorphic circuits synthesis and optimization
Crha, Adam ; Plíva, Zdeněk (oponent) ; Fišer, Petr (oponent) ; Růžička, Richard (vedoucí práce)
This thesis deals with synthesis and optimization methods of polymorphic circuits. Ordinary and multi-functional synthesis and optimization methods are discussed. The main objective of this thesis is to introduce novel methodologies for scalable synthesis of multi-functional digital circuits. Despite the fact that several approaches have been proposed during recent years, those are applicable for small-scale circuits only or are based on various evolution-inspired techniques. Obviously, scalable synthesis methodology for complex multi-functional circuits does not exist yet. The proposed methodology is based on And-Inverter Graphs ( AIGs ) with built-in extension for multi-functional circuits where the employment of rewriting techniques reduces the area by sharing common resources of two different input circuits. Experiments performed on publicly available benchmark circuits demonstrate significant optimization achievements.
|
|
|
Novel approach to polymorphism in gate-level digital circuits
Nevoral, Jan ; Plíva, Zdeněk (oponent) ; Stopjaková,, Viera (oponent) ; Růžička, Richard (vedoucí práce)
Nearly twenty years ago, a non-conventional approach to implementation of multifunctional circuits called polymorphic electronics was proposed. The concept of polymorphic electronics allows to implement two or more functions in a single circuit, whereas the currently selected function depends on the state of the circuit operating environment. Key components of such circuits are polymorphic gates. Since the introduction of polymorphic electronics, several dozens of polymorphic gates have been published. However, a large number of them do not meet reasonable parameters. As a result, perspective of their utilisation for real applications becomes rather bleak. This dissertation introduces a new approach to the polymorphic electronics. It is based on gates whose behaviour depends on polarity of dedicated power supply rails. The goal of this thesis is to show that such approach allows to design gates with significantly better parameters. In order to systematically design proposed gates at the transistor level, an evolutionary method based on Cartesian genetic programming was proposed. That allowed to design several sets of efficient polymorphic gates employing conventional MOSFET and emerging double-gate ambipolar transistors. These gate sets were arranged into a library which is currently freely available for other researchers. Furthermore, a number of more complex circuits based on proposed gates were designed in this thesis. It is demonstrated at various levels of circuit design (gate, RTL, application) that the proposed gate-level polymorphism provides significant advantages compared to the first generation of polymorphic gates, but it can also be competitive or even better compared to the conventional CMOS solutions.
|
|
|
Metodika aplikace testu obvodu založená na identifikaci testovatelných bloků
Herrman, Tomáš ; Plíva, Zdeněk (oponent) ; Racek, Stanislav (oponent) ; Kotásek, Zdeněk (vedoucí práce)
Dizertační práce se zabývá analýzou číslicových obvodů popsaných na úrovni meziregistrových přenosů. Je v ní zahrnuta pouze problematika související s testovatelností obvodových datových cest, řadičem ovládajícím tok dat těmito cestami se nezabývá. Stěžejní částí práce je návrh konceptu testovatelného bloku (TB), pomocí něhož se obvod rozdělí na části, jež jsou plně testovatelné přes jejich vstupy a výstupy, přes takzvané hraniční registry bloku nebo primární vstupy/výstupy. Přínosem nové metodiky je také redukce počtu registrů v řetězci scan, do něhož jsou zařazeny pouze hraniční registry. Segmentací obvodu dosáhneme také zjednodušení generování testu rozdělením tohoto problému na více menších částí. Navržená metodika pro identifikaci TB v číslicovém obvodu využívá dvou vybraných evolučních algoritmů operujících na formálním modelu obvodu na úrovni RT.
|
host ::
RSS.