The Experts below are selected from a list of 276 Experts worldwide ranked by ideXlab platform
Jürgen Teich - One of the best experts on this subject based on the ideXlab platform.
-
Dynamic Defragmentation of Reconfigurable Devices
ACM Transactions on Reconfigurable Technology and Systems, 2012Co-Authors: Sándor P. Fekete, Jan C. Van Der Veen, Dirk Koch, Josef Angermeier, Tom Kamphans, Nils Schweer, Christopher Tessars, Jürgen TeichAbstract:We propose a new method for defragmenting the module layout of a Reconfigurable Device, enabled by a novel approach for dealing with communication needs between relocated modules and with inhomogeneities found in commonly used FPGAs. Our method is based on dynamic relocation of module positions during runtime, with only very little reconfiguration overhead; the objective is to maximize the length of contiguous free space that is available for new modules. We describe a number of algorithmic aspects of good defragmentation, and present an optimization method based on tabu search. Experimental results indicate that we can improve the quality of module layout by roughly 50p over the static layout. Among other benefits, this improvement avoids unnecessary rejections of modules.
-
FPL - Stress-Aware Module Placement on Reconfigurable Devices
2011 21st International Conference on Field Programmable Logic and Applications, 2011Co-Authors: Josef Angermeier, Daniel Ziener, Michael Glaß, Jürgen TeichAbstract:A lot of research has been spent on improving the reliability and extending the lifetime of ASIC and SoC Devices, but only little on improving the long-term reliability of dynamically Reconfigurable systems. In order to increase the lifetime of a Reconfigurable Device, we propose a placement strategy to distribute the stress equally on the Reconfigurable resources at runtime such that all have a similar level of degradation. Thereby, we present a new aging model which is applied to estimate the influence of aging effects on dynamically Reconfigurable Devices, and which can be evaluated at runtime, while providing quite accurate aging results. Furthermore, we present a new stress-aware placement algorithm that takes the degradation of the Reconfigurable resources into account and can significantly extend the lifetime of Reconfigurable Devices.
-
FPT - Runtime stress-aware replica placement on Reconfigurable Devices under safety constraints
2011 International Conference on Field-Programmable Technology, 2011Co-Authors: Josef Angermeier, Daniel Ziener, Michael Glaß, Jürgen TeichAbstract:Ever shrinking Device structures result in an increased susceptibility of modern embedded systems to radiation and temperature-dependent aging effects. This work introduces a runtime placement algorithm for dynamically Reconfigurable systems that have to meet varying safety requirements. The algorithm first allocates replicas of modules to cope with soft-errors and meet the safety-level of the module and then places the modules onto the FPGA in such a way that the stress, and therefore aging, is minimized. For the replica allocation, a lifetime analysis is employed to predict the reliability of a module depending on its sensitive configuration bits and the expected runtime of the module. Moreover, the temperature profile of each active module is utilized to predict the degradation of each part of the Reconfigurable area. The presented algorithm then equally distributes active modules to minimize the degradation effects while respecting placement constraints that arise from the need for majority voting between the different replicas of a module. A case study gives evidence of the capability of the proposed online placing algorithm to harden a system against radiation effects and meet safety constraints while extending the overall lifetime of the Reconfigurable Device by minimizing stress.
-
IPDPS Workshops - Virtual area management: Multitasking on dynamically partially Reconfigurable Devices
2010 IEEE International Symposium on Parallel & Distributed Processing Workshops and Phd Forum (IPDPSW), 2010Co-Authors: Josef Angermeier, Sándor P. Fekete, Tom Kamphans, Nils Schweer, Jürgen TeichAbstract:Every year the computing resources available on dynamically partially Reconfigurable Devices increase enormously. In the near future, we expect many applications to run on a single Reconfigurable Device. In this paper, we present a concept for multitasking on dynamically partially Reconfigurable systems called virtual area management. We explain its advantages, show its challenges, and discuss possible solutions. Furthermore, we investigate one problem in more detail: Packing modules with time-varying resource requests. This problem from the Reconfigurable computing field results in a completely new optimization problem not tackled before. ILP-based and heuristic approaches are compared in an experimental study and the drawbacks and benefits discussed.
-
Offline and Online Aspects of Defragmenting the Module Layout of a Partially Reconfigurable Device
IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2008Co-Authors: Sándor P. Fekete, Jan C. Van Der Veen, Ali Ahmadinia, Mateusz Majer, Diana Gohringer, Jürgen TeichAbstract:Modern generations of field-programmable gate arrays (FPGAs) allow for partial reconfiguration. In an online context, where the sequence of modules to be loaded on the FPGA is unknown beforehand, repeated insertion and deletion of modules leads to progressive fragmentation of the available space, making defragmentation an important issue. We address this problem by proposing an online and an offline component for the defragmentation of the available space. We consider defragmenting the module layout on a Reconfigurable Device. This corresponds to solving a 2D strip packing problem. Problems of this type are NP-hard in the strong sense, and previous algorithmic results are rather limited. Based on a graph-theoretic characterization of feasible packings, we develop a method that can solve 2D defragmentation instances of practical size to optimality. Our approach is validated for a set of benchmark instances. We also discuss a simple strategy for dealing with online scenarios, called ldquoleast-interference fitrdquo (LIF); we give a number of analytic results that allow a comparison of LIF with the best offline solution, and demonstrate that it works well on benchmark instances of moderate size.
Ioannis Papaefstathiou - One of the best experts on this subject based on the ideXlab platform.
-
implementing rainbow tables in high end fpgas for super fast password cracking
Field-Programmable Logic and Applications, 2010Co-Authors: Ioannis Papaefstathiou, Charalampos ManifavasAbstract:One of the most efficient methods for cracking passwords, which are hashed based on different cryptographic algorithms, is the one based on “Rainbow Tables”. Those lookup tables offer an almost optimal time-memory tradeoff in the process of recovering the plaintext password from a password hash, generated by a cryptographic hash function. In this paper, the first known such generic system is demonstrated. It is implemented in a state-of-the-art Reconfigurable Device that cracks passwords, which are encrypted with a number of different cryptographic algorithms. The proposed FPGA-based system is up to 1000 times faster than the corresponding software approach. This is achieved by using a highly parallel architecture employing a fine-grained pipeline.
-
high end Reconfigurable systems for fast windows password cracking
Field-Programmable Custom Computing Machines, 2009Co-Authors: K Theoharoulis, Charalampos Manifavas, Ioannis PapaefstathiouAbstract:One of the most efficient methods for cracking passwords is the one based on ldquorainbow tablesrdquo; those lookup tables are offering an almost optimal time-memory tradeoff in the process of recovering the plaintext password from a password hash generated by a cryptographic hash function. In this paper, we demonstrate the first known system, implemented in a state-of-the-art Reconfigurable Device that cracks passwords up to 1000 times faster than the software approach. This is achieved by using a highly parallel architecture employing a fine-grained pipeline.
-
FCCM - HighEnd Reconfigurable Systems for Fast Windows' Password Cracking
2009 17th IEEE Symposium on Field Programmable Custom Computing Machines, 2009Co-Authors: K Theoharoulis, Charalampos Manifavas, Ioannis PapaefstathiouAbstract:One of the most efficient methods for cracking passwords is the one based on ldquorainbow tablesrdquo; those lookup tables are offering an almost optimal time-memory tradeoff in the process of recovering the plaintext password from a password hash generated by a cryptographic hash function. In this paper, we demonstrate the first known system, implemented in a state-of-the-art Reconfigurable Device that cracks passwords up to 1000 times faster than the software approach. This is achieved by using a highly parallel architecture employing a fine-grained pipeline.
-
FPL - A fast parallel matrix multiplication Reconfigurable unit utilized in face recognitions systems
2009 International Conference on Field Programmable Logic and Applications, 2009Co-Authors: I. Sotiropoulos, Ioannis PapaefstathiouAbstract:In this paper we present a Reconfigurable Device which significantly improves the execution time of the most computational intensive functions of three of the most widely used face recognition algorithms; those tasks multiply very large dense matrices. The presented architecture utilizes numerous digital signal processing units (DSPs) organized in a parallel manner within a state-of-the-art FPGA Device. In order to accelerate those functions we have implemented a ldquoblockedrdquo matrix multiplication algorithm which multiplies certain sub-matrices of fixed-point 32-bit numbers; the size of the sub-matrices has been selected so as to fully exploit the resources of the underlying Reconfigurable Device. Our system is up to 550 times faster than a conventional general purpose processor when implementing the most CPU intensive parts of a number of very widely used face identification schemes, whereas it is more than 40 times faster than the similar schemes implemented in Reconfigurable Devices. Moreover, our system is general enough so as to be efficiently utilized in any application incorporating fixed-point matrix multiplications.
Takahiro Watanabe - One of the best experts on this subject based on the ideXlab platform.
-
Multi-Shape Task Placement Algorithm Based on Low Fragmentation Resource Management on 2D Heterogeneous Dynamic Partial Reconfigurable Devices
IEEE Access, 2020Co-Authors: Tingyu Zhou, Tieyuan Pan, Michael Conrad Meyer, Yiping Dong, Takahiro WatanabeAbstract:The Dynamic Partial Reconfiguration function of Reconfigurable Devices permits tasks to be performed simultaneously on a single Device. Nevertheless, task placement and resource management problems emerge with the parallelism of Reconfigurable Devices. Traditional task placement algorithms are based on the assumption of a homogeneous architecture and simplify the task as a rectangular shape, which inevitably results in internal unused areas, thereby wasting a significant amount of programmable resources. To address the resource waste that comes with the assumption of a rectangular task shape and improve the placement quality, we adopted an interval list set to manage available programmable resources for a heterogeneous Reconfigurable Device and proposed an interval-based placement algorithm combined with a low-fragmentation selection strategy targeting the placement problem of multi-shape tasks. The efficiency of the proposed approach is proved theoretically, and simulation results demonstrate that the rejection ratio is decreased by at least 8.9% with an average fragmentation reduction of 18.1%.
-
Fault-tolerant image filter design using particle swarm optimization
Artificial Life and Robotics, 2011Co-Authors: Zhiguo Bao, Fangfang Wang, Xiaoming Zhao, Takahiro WatanabeAbstract:This article describes a mixed constrained image filter design with fault tolerance using particle swarm optimization (PSO) on a Reconfigurable processing array. There may be some faulty configurable logic blocks (CLBs) in a Reconfigurable processing array. The proposed method with PSO autonomously synthesizes a filter fitted to the Reconfigurable Device with some faults in order to optimize the complexity and power of the circuit, and the signal delay in both the CLBs and the wires. An image filter for noise reduction is experimentally synthesized to verify the validity of our method. By evolution, the quality of the optimized image filter on a Reconfigurable Device with a few faults is almost same as that on a Device with no faults.
-
Fault-tolerant image filter design using GA
TENCON 2010 - 2010 IEEE Region 10 Conference, 2010Co-Authors: Zhiguo Bao, Fangfang Wang, Xiaoming Zhao, Takahiro WatanabeAbstract:This paper describes mixed constrained image filter design with fault tolerant using Genetic Algorithm (GA) on a Reconfigurable processing array. There may be some faulty Configurable Logic Blocks (CLBs) in a Reconfigurable processing array at random. The proposed method with GA autonomously synthesizes a filter fitted to the Reconfigurable Device with some faults, evaluating the complexity, power and signal delay in both CLBs and wires. An image filter for noise reduction is experimentally synthesized to verify the validity of our method. By evolution, the quality of the optimized image filter on a Reconfigurable Device with a few faults is almost same as that with no fault.
Yukihiro Nakamura - One of the best experts on this subject based on the ideXlab platform.
-
Autonomous Repair Fault Tolerant Dynamic Reconfigurable Device
IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, 2008Co-Authors: Kentaro Nakahara, Shin'ichi Kouyama, Tomonori Izumi, Hiroyuki Ochi, Yukihiro NakamuraAbstract:Recently, Reconfigurable Devices are widely used in the fields of small amount production and trial production. They are also expected to be utilized in such mission-critical fields as space development, because system update and pseudo-repair can be achieved remotely by reconfiguring. However, in the case of conventional Reconfigurable Devices, configuration memory upsets caused by radiation and alpha particles reconfigure the Device unpredictably, resulting in fatal system failures. Therefore, a Reconfigurable Device with high fault-tolerance against configuration upsets is required. In this paper, we propose an architecture of a fault-tolerant Reconfigurable Device that autonomously repairs configuration upsets by itself without interrupting system operations. The Device consists of a 2D array of “Autonomous-Repair Cells” each of which repairs its upsets autonomously. The architecture has a scalability in fault tolerance; a finer-grained Autonomous-Repair Cell provides higher fault-tolerance. To determine the architecture, we analyze four autonomous repair techniques of the cell experimentally. Then, two autonomous repair techniques, simple multiplexing (S.M.) and memory multiplexing (M.M.), are applied; the former to programmable logics and the latter to cell-to-cell routing resources. Through evaluation, we show that proposed Device achieves more than 10 years average lifetime against configuration upsets even in a severe situation such as a satellite orbit.
-
Fault Tolerant Dynamic Reconfigurable Device Based on EDAC with Rollback
IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, 2006Co-Authors: Kentaro Nakahara, Shin'ichi Kouyama, Tomonori Izumi, Hiroyuki Ochi, Yukihiro NakamuraAbstract:Reconfigurable Devices are expected to be utilized in such mission-critical fields as space development and undersea cables, because system updates and pseudo-repair can be achieved remotely by reconfiguring. However, conventional Reconfigurable Devices suffer from memory-bit upset caused by charged particles in space which results in fatal system problems. In this paper, we propose an architecture of a fault-tolerant Reconfigurable Device. The proposed Device is divided into "autonomous-repair cells" with embedded control circuits. The autonomous-repair cell proposed in this paper is based on error detection and correction (EDAC) and uses hardware and time redundancy. From evaluation, it is shown that the proposed architecture achieves sufficient reliability against configuration memory upset. Trade-offs between performance and cost are also analyzed.
-
FPL - Fault Tolerant Reconfigurable Device Based on Autonomous-Repair Cells
2006 International Conference on Field Programmable Logic and Applications, 2006Co-Authors: Kentaro Nakahara, Shin'ichi Kouyama, Tomonori Izumi, Hiroyuki Ochi, Yukihiro NakamuraAbstract:Reconfigurable Devices are expected to be utilized in the mission-critical fields such as space development, because a system update and a pseudo-repair can be achieved remotely by reconfiguration. However, conventional Reconfigurable Devices suffer from configuration memory upsets caused by radiation in space. This paper proposes an architecture of a fault-tolerant Reconfigurable Device based on island-style FPGA. The Device consists of "Autonomous-Repair Cells" which repairs these upsets autonomously and dynamically. To determine the architecture, we analyze four autonomous repair techniques of the cell experimentally. Then, optimal autonomous repair techniques are applied to both of programmable logics and cell-to-cell routing resources. Through evaluation, we show that proposed Device achieves more than 10 years average lifetime against configuration upsets even in a severe situation such as a satellite orbit.
Josef Angermeier - One of the best experts on this subject based on the ideXlab platform.
-
Dynamic Defragmentation of Reconfigurable Devices
ACM Transactions on Reconfigurable Technology and Systems, 2012Co-Authors: Sándor P. Fekete, Jan C. Van Der Veen, Dirk Koch, Josef Angermeier, Tom Kamphans, Nils Schweer, Christopher Tessars, Jürgen TeichAbstract:We propose a new method for defragmenting the module layout of a Reconfigurable Device, enabled by a novel approach for dealing with communication needs between relocated modules and with inhomogeneities found in commonly used FPGAs. Our method is based on dynamic relocation of module positions during runtime, with only very little reconfiguration overhead; the objective is to maximize the length of contiguous free space that is available for new modules. We describe a number of algorithmic aspects of good defragmentation, and present an optimization method based on tabu search. Experimental results indicate that we can improve the quality of module layout by roughly 50p over the static layout. Among other benefits, this improvement avoids unnecessary rejections of modules.
-
FPL - Stress-Aware Module Placement on Reconfigurable Devices
2011 21st International Conference on Field Programmable Logic and Applications, 2011Co-Authors: Josef Angermeier, Daniel Ziener, Michael Glaß, Jürgen TeichAbstract:A lot of research has been spent on improving the reliability and extending the lifetime of ASIC and SoC Devices, but only little on improving the long-term reliability of dynamically Reconfigurable systems. In order to increase the lifetime of a Reconfigurable Device, we propose a placement strategy to distribute the stress equally on the Reconfigurable resources at runtime such that all have a similar level of degradation. Thereby, we present a new aging model which is applied to estimate the influence of aging effects on dynamically Reconfigurable Devices, and which can be evaluated at runtime, while providing quite accurate aging results. Furthermore, we present a new stress-aware placement algorithm that takes the degradation of the Reconfigurable resources into account and can significantly extend the lifetime of Reconfigurable Devices.
-
FPT - Runtime stress-aware replica placement on Reconfigurable Devices under safety constraints
2011 International Conference on Field-Programmable Technology, 2011Co-Authors: Josef Angermeier, Daniel Ziener, Michael Glaß, Jürgen TeichAbstract:Ever shrinking Device structures result in an increased susceptibility of modern embedded systems to radiation and temperature-dependent aging effects. This work introduces a runtime placement algorithm for dynamically Reconfigurable systems that have to meet varying safety requirements. The algorithm first allocates replicas of modules to cope with soft-errors and meet the safety-level of the module and then places the modules onto the FPGA in such a way that the stress, and therefore aging, is minimized. For the replica allocation, a lifetime analysis is employed to predict the reliability of a module depending on its sensitive configuration bits and the expected runtime of the module. Moreover, the temperature profile of each active module is utilized to predict the degradation of each part of the Reconfigurable area. The presented algorithm then equally distributes active modules to minimize the degradation effects while respecting placement constraints that arise from the need for majority voting between the different replicas of a module. A case study gives evidence of the capability of the proposed online placing algorithm to harden a system against radiation effects and meet safety constraints while extending the overall lifetime of the Reconfigurable Device by minimizing stress.
-
No-Break Dynamic Defragmentation of Reconfigurable Devices
arXiv: Data Structures and Algorithms, 2010Co-Authors: Sándor P. Fekete, Jan C. Van Der Veen, Dirk Koch, Josef Angermeier, Tom Kamphans, Nils Schweer, Christopher Tessars, Juergen TeichAbstract:We propose a new method for defragmenting the module layout of a Reconfigurable Device, enabled by a novel approach for dealing with communication needs between relocated modules and with inhomogeneities found in commonly used FPGAs. Our method is based on dynamic relocation of module positions during runtime, with only very little reconfiguration overhead; the objective is to maximize the length of contiguous free space that is available for new modules. We describe a number of algorithmic aspects of good defragmentation, and present an optimization method based on tabu search. Experimental results indicate that we can improve the quality of module layout by roughly 50 % over static layout. Among other benefits, this improvement avoids unnecessary rejections of modules
-
IPDPS Workshops - Virtual area management: Multitasking on dynamically partially Reconfigurable Devices
2010 IEEE International Symposium on Parallel & Distributed Processing Workshops and Phd Forum (IPDPSW), 2010Co-Authors: Josef Angermeier, Sándor P. Fekete, Tom Kamphans, Nils Schweer, Jürgen TeichAbstract:Every year the computing resources available on dynamically partially Reconfigurable Devices increase enormously. In the near future, we expect many applications to run on a single Reconfigurable Device. In this paper, we present a concept for multitasking on dynamically partially Reconfigurable systems called virtual area management. We explain its advantages, show its challenges, and discuss possible solutions. Furthermore, we investigate one problem in more detail: Packing modules with time-varying resource requests. This problem from the Reconfigurable computing field results in a completely new optimization problem not tackled before. ILP-based and heuristic approaches are compared in an experimental study and the drawbacks and benefits discussed.