Multi-FPGA Designs and Scaling of HPC Challenge Benchmarks via MPI and Circuit-Switched Inter-FPGA Networks - Meyer, Marius; Kenter, Tobias; Plessl, Christian (ACM Transactions on Reconfigurable Technology and Systems)
While FPGA accelerator boards and their respective high-level design tools are maturing, there is still a lack of multi-FPGA applications, libraries, and not least, benchmarks and reference implementations towards sustained HPC usage of these devices. As in the early days of GPUs in HPC, for workloads that can reasonably be decoupled into loosely coupled working sets, multi-accelerator support can be achieved by using standard communication interfaces like MPI on the host side. However, for performance and productivity, some applications can profit from a tighter coupling of the accelerators. FPGAs offer unique opportunities here when extending the dataflow characteristics to their communication interfaces. In this work, we extend the HPCC FPGA benchmark suite by multi-FPGA support and three missing benchmarks that particularly characterize or stress inter-device communication: b_eff, PTRANS, and LINPACK. With all benchmarks implemented for current boards with Intel and Xilinx FPGAs, we established a baseline for multi-FPGA performance. Additionally, for the communication-centric benchmarks, we explored the potential of direct FPGA-to-FPGA communication with a circuit-switched inter-FPGA network that is currently only available for one of the boards. The evaluation with parallel execution on up to 26 FPGA boards makes use of one of the largest academic FPGA installations.
Keywords: General Computer Science

XCS for Self-awareness in Autonomous Computing Systems - Hansmeier, Tim

On-The-Fly Computing -- Individualized IT-services in dynamic markets - Haake, Claus-Jochen; Meyer auf der Heide, Friedhelm; Platzner, Marco; Wachsmuth, Henning; Wehrheim, Heike
In the proposal for our CRC in 2011, we formulated a vision of markets for IT services that describes an approach to the provision of such services that was novel at that time and, to a large extent, remains so today: „Our vision of on-the-fly computing is that of IT services individually and automatically configured and brought to execution from flexibly combinable services traded on markets. At the same time, we aim at organizing markets whose participants maintain a lively market of services through appropriate entrepreneurial actions.“ Over the last 12 years, we have developed methods and techniques to address problems critical to the convenient, efficient, and secure use of on-the-fly computing. Among other things, we have made the description of services more convenient by allowing natural language input, increased the quality of configured services through (natural language) interaction and more efficient configuration processes and analysis procedures, made the quality of (the products of) providers in the marketplace transparent through reputation systems, and increased the resource efficiency of execution through reconfigurable heterogeneous computing nodes and an integrated treatment of service description and configuration. We have also developed network infrastructures that have a high degree of adaptivity, scalability, efficiency, and reliability, and provide cryptographic guarantees of anonymity and security for market participants and their products and services. To demonstrate the pervasiveness of the OTF computing approach, we have implemented a proof-of-concept for OTF computing that can run typical scenarios of an OTF market. We illustrated the approach using a cutting-edge application scenario – automated machine learning (AutoML). Finally, we have been pushing our work for the perpetuation of On-The-Fly Computing beyond the SFB and sharing the expertise gained in the SFB in events with industry partners as well as transfer projects. This work required a broad spectrum of expertise. Computer scientists and economists with research interests such as computer networks and distributed algorithms, security and cryptography, software engineering and verification, configuration and machine learning, computer engineering and HPC, microeconomics and game theory, business informatics and management have successfully collaborated here.

Compute Centers I: Heterogeneous Execution Environments - Hansmeier, Tim; Kenter, Tobias; Meyer, Marius; Riebler, Heinrich; Platzner, Marco; Plessl, Christian (On-The-Fly Computing -- Individualized IT-services in dynamic markets)

An Evaluation of XCS on the OpenAI Gym - Mehlich, Florian

Integrating Safety Guarantees into the Learning Classifier System XCS - Hansmeier, Tim; Platzner, Marco (Applications of Evolutionary Computation, EvoApplications 2022, Proceedings)

XCS on Embedded Systems: An Analysis of Execution Profiles and Accelerated Classifier Deletion - Hansmeier, Tim; Brede, Mathis; Platzner, Marco (GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference Companion)

Hardware Trojans in Reconfigurable Computing - Ahmed, Qazi Arbab
Wettstreit zwischen der Entwicklung neuer Hardwaretrojaner und entsprechender Gegenmaßnahmen beschreiten Widersacher immer raffiniertere Wege um Schaltungsentwürfe zu infizieren und dabei selbst fortgeschrittene Test- und Verifikationsmethoden zu überlisten. Abgesehen von den konventionellen Methoden um einen Trojaner in eine Schaltung für ein Field-programmable Gate Array (FPGA) einzuschleusen, können auch die Entwurfswerkzeuge heimlich kompromittiert werden um einen Angreifer dabei zu unterstützen einen erfolgreichen Angriff durchzuführen, der zum Beispiel Fehlfunktionen oder ungewollte Informationsabflüsse bewirken kann. Diese Dissertation beschäftigt sich hauptsächlich mit den beiden Blickwinkeln auf Hardwaretrojaner in rekonfigurierbaren Systemen, einerseits der Perspektive des Verteidigers mit einer Methode zur Erkennung von Trojanern auf der Bitstromebene, und andererseits derjenigen des Angreifers mit einer neuartigen Angriffsmethode für FPGA Trojaner. Für die Verteidigung gegen den Trojaner ``Heimtückische LUT'' stellen wir die allererste erfolgreiche Gegenmaßnahme vor, die durch Verifikation mittels Proof-carrying Hardware (PCH) auf der Bitstromebene direkt vor der Konfiguration der Hardware angewendet werden kann, und präsentieren ein vollständiges Schema für den Entwurf und die Verifikation von Schaltungen für iCE40 FPGAs. Für die Gegenseite führen wir einen neuen Angriff ein, welcher bösartiges Routing im eingefügten Trojaner ausnutzt um selbst im fertigen Bitstrom in einem inaktiven Zustand zu verbleiben: Hierdurch kann dieser neuartige Angriff zur Zeit weder von herkömmlichen Test- und Verifikationsmethoden, noch von unserer vorher vorgestellten Verifikation auf der Bitstromebene entdeckt werden.
Keywords: FPGA Security; Hardware Trojans; Bitstream-level Trojans; Bitstream Verification

A Comparison of Machine Learning Techniques for the On-line Characterization of Tasks Executed on Heterogeneous Compute Nodes - Kashikar, Chinmay
Automation becomes a vital part in the High-Performance computing system in situational dynamics to take the decisions on the fly. Heterogeneous compute nodes consist of computing resources such as CPU, GPU and FPGA and are the important components of the high-performance computing system that can adapt the automation to achieve the given goal. While implanting automation in the computing resources, management of the resources is one of the essential aspects that need to be taken care of. Tasks are continuously executed on the resources using its unique characteristics. Effective scheduling is essential to make the best use of the characteristics provided by each resource. Scheduling enables the execution of each task by allocating resources so that they take advantage of all the characteristics of the compute resources. Various scheduling heuristics can be used to create effective scheduling, which might require the execution time to schedule the task efficiently. Providing actual execution time is not possible in many cases; hence we can provide the estimations for the actual execution time . The purpose of this master's thesis is to design a predictive model or system that estimates the execution time required to execute tasks using historical execution time data on the heterogeneous compute nodes. In this thesis, regression techniques(SGD Regressor, Passive-Aggressive Regressor, MLP Regressor, and XCSF Regressor) are compared in terms of their prediction accuracy in order to determine which technique produces reliable predictions for the execution time. These estimations must be generated in an online learning environment in which data points arrive in any sequence, one by one, and the regression model must learn from them. After evaluating the regression algorithms, it is seen that the XCSF regressor provides the highest overall prediction accuracy for the supplied data sets. The regression technique's parameters also play a significant role in achieving an acceptable prediction accuracy. As a remark, when using online learning in regression analysis, the accuracy depends upon both the order of sequential data points that are coming to train the model and the parameter configuration for each regression technique.

Implementation and Profiling of XCS in the Context of Embedded Systems - Brede, Mathis
This bachelor thesis presents a C/C++ implementation of the XCS algorithm for an embedded system and profiling results concerning the execution time of the functions. These are then analyzed in relation to the input characteristics of the examined learning environments and compared with related work. Three main conclusions can be drawn from the measured results. First, the maximum size of the population of the classifiers influences the runtime of the genetic algorithm; second, the size of the input space has a direct effect on the execution time of the matching function; and last, a larger action space results in a longer runtime generating the prediction for the possible actions. The dependencies identified here can serve to optimize the computational efficiency and make XCS more suitable for embedded systems.

Self-aware Operation of Heterogeneous Compute Nodes using the Learning Classifier System XCS - Hansmeier, Tim (HEART '21: Proceedings of the 11th International Symposium on Highly Efficient Accelerators and Reconfigurable Technologies)

An Experimental Comparison of Explore/Exploit Strategies for the Learning Classifier System XCS - Hansmeier, Tim; Platzner, Marco (GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference Companion)

An Adaption Mechanism for the Error Threshold of XCSF - Hansmeier, Tim; Kaufmann, Paul; Platzner, Marco (GECCO '20: Proceedings of the Genetic and Evolutionary Computation Conference Companion)

Enabling XCSF to Cope with Dynamic Environments via an Adaptive Error Threshold - Hansmeier, Tim; Kaufmann, Paul; Platzner, Marco (GECCO '20: Proceedings of the Genetic and Evolutionary Computation Conference Companion)

A Case for a New IT Ecosystem: On-The-Fly Computing - Karl, Holger; Kundisch, Dennis; Meyer auf der Heide, Friedhelm; Wehrheim, Heike (Business & Information Systems Engineering)

Transparent Acceleration for Heterogeneous Platforms with Compilation to OpenCL - Riebler, Heinrich; Vaz, Gavin Francis; Kenter, Tobias; Plessl, Christian (ACM Trans. Archit. Code Optim. (TACO))
Keywords: htrop

Using Just-in-Time Code Generation to Transparently Accelerate Applications in Heterogeneous Systems - Vaz, Gavin Francis

Autonomous Operation of High-Performance Compute Nodes through Self-Awareness and Learning Classifiers - Hansmeier, Tim

Efficient parallel branch-and-bound search on FPGAs using work stealing and instance-specific designs - Riebler, Heinrich

Ampehre: An Open Source Measurement Framework for Heterogeneous Compute Nodes - Lösch, Achim; Wiens, Alex; Platzner, Marco (Proceedings of the International Conference on Architecture of Computing Systems (ARCS))
Profiling applications on a heterogeneous compute node is challenging since the way to retrieve data from the resources and interpret them varies between resource types and manufacturers. This holds especially true for measuring the energy consumption. In this paper we present Ampehre, a novel open source measurement framework that allows developers to gather comparable measurements from heterogeneous compute nodes, e.g., nodes comprising CPU, GPU, and FPGA. We explain the architecture of Ampehre and detail the measurement process on the example of energy measurements on CPU and GPU. To characterize the probing effect, we quantitatively analyze the trade-off between the accuracy of measurements and the CPU load imposed by Ampehre. Based on this analysis, we are able to specify reasonable combinations of sampling periods for the different resource types of a compute node.

Static Scheduling Algorithms for Heterogeneous Compute Nodes - Schnuer, Jan-Philip

Evaluation of OpenCL-based Compilation for FPGAs - Croce, Marcel

Study Effects of Approximation on Conjugate Gradient Algorithm and Accelerate it on FPGA Platform - Filmwala, Tasneem

Programmable Programs? - Designing FPGA Overlay Architectures with OpenCL - Gadewar, Onkar

A Highly Accurate Energy Model for Task Execution on Heterogeneous Compute Nodes - Lösch, Achim; Platzner, Marco (2018 IEEE 29th International Conference on Application-specific Systems, Architectures and Processors (ASAP))

Accelerating Molecular Dynamic Simulations by Offloading Fast Fourier Transformations to FPGA - Ramaswami, Arjun
Molecular Dynamic (MD) simulations are computationally intensive and accelerating them using specialized hardware is a topic of investigation in many studies. One of the routines in the critical path of MD simulations is the three-dimensional Fast Fourier Transformation (FFT3d). The potential in accelerating FFT3d using hardware is usually bound by bandwidth and memory. Therefore, designing a high throughput solution for an FPGA that overcomes this problem is challenging. In this thesis, the feasibility of offloading FFT3d computations to FPGA implemented using OpenCL is investigated. In order to mask the latency in memory access, an FFT3d that overlaps computation with communication is designed. The implementa- tion of this design is synthesized for the Arria 10 GX 1150 FPGA and evaluated with the FFTW benchmark. Analysis shows a better performance using FPGA over CPU for larger FFT sizes, with the 643 FFT showing a 70% improvement in runtime using FPGAs. This FFT3d design is integrated with CP2K to explore the potential in accelerating molecular dynamic simulations. Evaluation of CP2K simulations using FPGA shows a 41% improvement in runtime in FFT3d computations over CPU for larger FFT3d designs.
Keywords: FFT: FPGA; CP2K; OpenCL

OpenCL-based FPGA Design to Accelerate the Nodal Discontinuous Galerkin Method for Unstructured Meshes - Kenter, Tobias; Mahale, Gopinath; Alhaddad, Samer; Grynko, Yevgen; Schmitt, Christian; Afzal, Ayesha; Hannig, Frank; Förstner, Jens; Plessl, Christian (Proc. Int. Symp. on Field-Programmable Custom Computing Machines (FCCM))
The exploration of FPGAs as accelerators for scientific simulations has so far mostly been focused on small kernels of methods working on regular data structures, for example in the form of stencil computations for finite difference methods. In computational sciences, often more advanced methods are employed that promise better stability, convergence, locality and scaling. Unstructured meshes are shown to be more effective and more accurate, compared to regular grids, in representing computation domains of various shapes. Using unstructured meshes, the discontinuous Galerkin method preserves the ability to perform explicit local update operations for simulations in the time domain. In this work, we investigate FPGAs as target platform for an implementation of the nodal discontinuous Galerkin method to find time-domain solutions of Maxwell's equations in an unstructured mesh. When maximizing data reuse and fitting constant coefficients into suitably partitioned on-chip memory, high computational intensity allows us to implement and feed wide data paths with hundreds of floating point operators. By decoupling off-chip memory accesses from the computations, high memory bandwidth can be sustained, even for the irregular access pattern required by parts of the application. Using the Intel/Altera OpenCL SDK for FPGAs, we present different implementation variants for different polynomial orders of the method. In different phases of the algorithm, either computational or bandwidth limits of the Arria 10 platform are almost reached, thus outperforming a highly multithreaded CPU implementation by around 2x.
Keywords: tet_topic_hpc

Automated Code Acceleration Targeting Heterogeneous OpenCL Devices - Riebler, Heinrich; Vaz, Gavin Francis; Kenter, Tobias; Plessl, Christian (Proc. ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP))
Keywords: htrop

OpenCL-basierte Videoverarbeitung auf heterogenen Rechenknoten - Knorr, Christoph

reMinMin: A Novel Static Energy-Centric List Scheduling Approach Based on Real Measurements - Lösch, Achim; Platzner, Marco (Proceedings of the 28th Annual IEEE International Conference on Application-specific Systems, Architectures and Processors (ASAP))
Heterogeneous compute nodes in form of CPUs with attached GPU and FPGA accelerators have strongly gained interested in the last years. Applications differ in their execution characteristics and can therefore benefit from such heterogeneous resources in terms of performance or energy consumption. While performance optimization has been the only goal for a long time, nowadays research is more and more focusing on techniques to minimize energy consumption due to rising electricity costs.This paper presents reMinMin, a novel static list scheduling approach for optimizing the total energy consumption for a set of tasks executed on a heterogeneous compute node. reMinMin bases on a new energy model that differentiates between static and dynamic energy components and covers effects of accelerator tasks on the host CPU. The required energy values are retrieved by measurements on the real computing system. In order to evaluate reMinMin, we compare it with two reference implementations on three task sets with different degrees of heterogeneity. In our experiments, MinMin is consistently better than a scheduler optimizing for dynamic energy only, which requires up to 19.43% more energy, and very close to optimal schedules.

Efficient Branch and Bound on FPGAs Using Work Stealing and Instance-Specific Designs - Riebler, Heinrich; Lass, Michael; Mittendorf, Robert; Löcke, Thomas; Plessl, Christian (ACM Transactions on Reconfigurable Technology and Systems (TRETS))
Branch and bound (B&B) algorithms structure the search space as a tree and eliminate infeasible solutions early by pruning subtrees that cannot lead to a valid or optimal solution. Custom hardware designs significantly accelerate the execution of these algorithms. In this article, we demonstrate a high-performance B&B implementation on FPGAs. First, we identify general elements of B&B algorithms and describe their implementation as a finite state machine. Then, we introduce workers that autonomously cooperate using work stealing to allow parallel execution and full utilization of the target FPGA. Finally, we explore advantages of instance-specific designs that target a specific problem instance to improve performance. We evaluate our concepts by applying them to a branch and bound problem, the reconstruction of corrupted AES keys obtained from cold-boot attacks. The evaluation shows that our work stealing approach is scalable with the available resources and provides speedups proportional to the number of workers. Instance-specific designs allow us to achieve an overall speedup of 47 × compared to the fastest implementation of AES key reconstruction so far. Finally, we demonstrate how instance-specific designs can be generated just-in-time such that the provided speedups outweigh the additional time required for design synthesis.
Keywords: coldboot

Flexible FPGA design for FDTD using OpenCL - Kenter, Tobias; Förstner, Jens; Plessl, Christian (Proc. Int. Conf. on Field Programmable Logic and Applications (FPL))
Compared to classical HDL designs, generating FPGA with high-level synthesis from an OpenCL specification promises easier exploration of different design alternatives and, through ready-to-use infrastructure and common abstractions for host and memory interfaces, easier portability between different FPGA families. In this work, we evaluate the extent of this promise. To this end, we present a parameterized FDTD implementation for photonic microcavity simulations. Our design can trade-off different forms of parallelism and works for two independent OpenCL-based FPGA design flows. Hence, we can target FPGAs from different vendors and different FPGA families. We describe how we used pre-processor macros to achieve this flexibility and to work around different shortcomings of the current tools. Choosing the right design configurations, we are able to present two extremely competitive solutions for very different FPGA targets, reaching up to 172 GFLOPS sustained performance. With the portability and flexibility demonstrated, code developers not only avoid vendor lock-in, but can even make best use of real trade-offs between different architectures.
Keywords: tet_topic_hpc

Sicherheit von hybriden FPGA-Systemen in der industriellen Automatisierungstechnik -- Anforderungen und Umsetzung - Tölke, Christian

Dynamic OpenCL Task Scheduling for Energy and Performance in a Heterogeneous Environment - Wüllrich, Gunnar

Reconfigurable Accelerators in the World of General-Purpose Computing - Kenter, Tobias

Using Just-in-Time Code Generation for Transparent Resource Management in Heterogeneous Systems - Riebler, Heinrich; Vaz, Gavin Francis; Plessl, Christian; Trainiti, Ettore M. G.; Durelli, Gianluca C.; Bolchini, Cristiana (Proc. HiPEAC Workshop on Reonfigurable Computing (WRC))

Microdisk Cavity FDTD Simulation on FPGA using OpenCL - Kenter, Tobias; Plessl, Christian (Proc. Workshop on Heterogeneous High-performance Reconfigurable Computing (H2RC))

Using Just-in-Time Code Generation for Transparent Resource Management in Heterogeneous Systems - Riebler, Heinrich; Vaz, Gavin Francis; Plessl, Christian; Trainiti, Ettore M. G.; Durelli, Gianluca C.; Del Sozzo, Emanuele; Santambrogio, Marco D.; Bolchini, Christina (Proceedings of International Forum on Research and Technologies for Society and Industry (RTSI))
Hardware accelerators are becoming popular in academia and industry. To move one step further from the state-of-the-art multicore plus accelerator approaches, we present in this paper our innovative SAVEHSA architecture. It comprises of a heterogeneous hardware platform with three different high-end accelerators attached over PCIe (GPGPU, FPGA and Intel MIC). Such systems can process parallel workloads very efficiently whilst being more energy efficient than regular CPU systems. To leverage the heterogeneity, the workload has to be distributed among the computing units in a way that each unit is well-suited for the assigned task and executable code must be available. To tackle this problem we present two software components; the first can perform resource allocation at runtime while respecting system and application goals (in terms of throughput, energy, latency, etc.) and the second is able to analyze an application and generate executable code for an accelerator at runtime. We demonstrate the first proof-of-concept implementation of our framework on the heterogeneous platform, discuss different runtime policies and measure the introduced overheads.

Self-aware Compute Nodes - Agne, Andreas; Happe, Markus; Lösch, Achim; Plessl, Christian; Platzner, Marco (Self-aware Computing Systems)
Many modern compute nodes are heterogeneous multi-cores that integrate several CPU cores with fixed function or reconfigurable hardware cores. Such systems need to adapt task scheduling and mapping to optimise for performance and energy under varying workloads and, increasingly important, for thermal and fault management and are thus relevant targets for self-aware computing. In this chapter, we take up the generic reference architecture for designing self-aware and self-expressive computing systems and refine it for heterogeneous multi-cores. We present ReconOS, an architecture, programming model and execution environment for heterogeneous multi-cores, and show how the components of the reference architecture can be implemented on top of ReconOS. In particular, the unique feature of dynamic partial reconfiguration supports self-expression through starting and terminating reconfigurable hardware cores. We detail a case study that runs two applications on an architecture with one CPU and 12 reconfigurable hardware cores and present self-expression strategies for adapting under performance, temperature and even conflicting constraints. The case study demonstrates that the reference architecture as a model for self-aware computing is highly useful as it allows us to structure and simplify the design process, which will be essential for designing complex future compute nodes. Furthermore, ReconOS is used as a base technology for flexible protocol stacks in Chapter 10, an approach for self-aware computing at the networking level.

Potential and Methods for Embedding Dynamic Offloading Decisions into Application Code - Vaz, Gavin Francis; Riebler, Heinrich; Kenter, Tobias; Plessl, Christian (Computers and Electrical Engineering)
A broad spectrum of applications can be accelerated by offloading computation intensive parts to reconfigurable hardware. However, to achieve speedups, the number of loop it- erations (trip count) needs to be sufficiently large to amortize offloading overheads. Trip counts are frequently not known at compile time, but only at runtime just before entering a loop. Therefore, we propose to generate code for both the CPU and the coprocessor, and defer the offloading decision to the application runtime. We demonstrate how a toolflow, based on the LLVM compiler framework, can automatically embed dynamic offloading de- cisions into the application code. We perform in-depth static and dynamic analysis of pop- ular benchmarks, which confirm the general potential of such an approach. We also pro- pose to optimize the offloading process by decoupling the runtime decision from the loop execution (decision slack). The feasibility of our approach is demonstrated by a toolflow that automatically identifies suitable data-parallel loops and generates code for the FPGA coprocessor of a Convey HC-1. We evaluate the integrated toolflow with representative loops executed for different input data sizes.

Performance-centric scheduling with task migration for a heterogeneous compute node in the data center - Lösch, Achim; Beisel, Tobias; Kenter, Tobias; Plessl, Christian; Platzner, Marco (Proceedings of the 2016 Design, Automation & Test in Europe Conference & Exhibition (DATE))
The use of heterogeneous computing resources, such as Graphic Processing Units or other specialized coprocessors, has become widespread in recent years because of their per- formance and energy efficiency advantages. Approaches for managing and scheduling tasks to heterogeneous resources are still subject to research. Although queuing systems have recently been extended to support accelerator resources, a general solution that manages heterogeneous resources at the operating system- level to exploit a global view of the system state is still missing.In this paper we present a user space scheduler that enables task scheduling and migration on heterogeneous processing resources in Linux. Using run queues for available resources we perform scheduling decisions based on the system state and on task characterization from earlier measurements. With a pro- gramming pattern that supports the integration of checkpoints into applications, we preempt tasks and migrate them between three very different compute resources. Considering static and dynamic workload scenarios, we show that this approach can gain up to 17% performance, on average 7%, by effectively avoiding idle resources. We demonstrate that a work-conserving strategy without migration is no suitable alternative.

Opportunities for deferring application partitioning and accelerator synthesis to runtime (extended abstract) - Kenter, Tobias; Vaz, Gavin Francis; Riebler, Heinrich; Plessl, Christian (Workshop on Reconfigurable Computing (WRC))

Evaluation von Bildverarbeitungsalgorithmen in heterogenen Rechenknoten - Knorr, Christoph

Self-Aware and Self-Expressive Systems – Guest Editor's Introduction - Torresen, Jim; Plessl, Christian; Yao, Xin (IEEE Computer)
Keywords: self-awareness; self-expression

An LLVM Based Toolchain for Transparent Acceleration of Digital Image Processing Applications using FPGA Overlay Architectures - Funke, Lukas

Instance-Specific Computing in Hard- and Software for Faster Solving of Complex Problems - Löcke, Thomas

Accelerating Programmable Logic Controllers with the use of FPGAs - Wallaschek, Felix

Exploring Tradeoffs between Specialized Kernels and a Reusable Overlay in a Stereo-Matching Case Study - Kenter, Tobias; Schmitz, Henning; Plessl, Christian (International Journal of Reconfigurable Computing (IJRC))
FPGAs are known to permit huge gains in performance and efficiency for suitable applications but still require reduced design efforts and shorter development cycles for wider adoption. In this work, we compare the resulting performance of two design concepts that in different ways promise such increased productivity. As common starting point, we employ a kernel-centric design approach, where computational hotspots in an application are identified and individually accelerated on FPGA. By means of a complex stereo matching application, we evaluate two fundamentally different design philosophies and approaches for implementing the required kernels on FPGAs. In the first implementation approach, we designed individually specialized data flow kernels in a spatial programming language for a Maxeler FPGA platform; in the alternative design approach, we target a vector coprocessor with large vector lengths, which is implemented as a form of programmable overlay on the application FPGAs of a Convey HC-1. We assess both approaches in terms of overall system performance, raw kernel performance, and performance relative to invested resources. After compensating for the effects of the underlying hardware platforms, the specialized dataflow kernels on the Maxeler platform are around 3x faster than kernels executing on the Convey vector coprocessor. In our concrete scenario, due to trade-offs between reconfiguration overheads and exposed parallelism, the advantage of specialized dataflow kernels is reduced to around 2.5x.

Easy-to-Use On-The-Fly Binary Program Acceleration on Many-Cores - Damschen, Marvin; Plessl, Christian (Proceedings of the 5th International Workshop on Adaptive Self-tuning Computing Systems (ADAPT))
This paper introduces Binary Acceleration At Runtime(BAAR), an easy-to-use on-the-fly binary acceleration mechanismwhich aims to tackle the problem of enabling existentsoftware to automatically utilize accelerators at runtime. BAARis based on the LLVM Compiler Infrastructure and has aclient-server architecture. The client runs the program to beaccelerated in an environment which allows program analysisand profiling. Program parts which are identified as suitable forthe available accelerator are exported and sent to the server.The server optimizes these program parts for the acceleratorand provides RPC execution for the client. The client transformsits program to utilize accelerated execution on the server foroffloaded program parts. We evaluate our work with a proofof-concept implementation of BAAR that uses an Intel XeonPhi 5110P as the acceleration target and performs automaticoffloading, parallelization and vectorization of suitable programparts. The practicality of BAAR for real-world examples is shownbased on a study of stencil codes. Our results show a speedup ofup to 4 without any developer-provided hints and 5.77 withhints over the same code compiled with the Intel Compiler atoptimization level O2 and running on an Intel Xeon E5-2670machine. Based on our insights gained during implementationand evaluation we outline future directions of research, e.g.,offloading more fine-granular program parts than functions, amore sophisticated communication mechanism or introducing onstack-replacement.

Transparent offloading of computational hotspots from binary code to Xeon Phi - Damschen, Marvin; Riebler, Heinrich; Vaz, Gavin Francis; Plessl, Christian (Proceedings of the 2015 Conference on Design, Automation and Test in Europe (DATE))
In this paper, we study how binary applications can be transparently accelerated with novel heterogeneous computing resources without requiring any manual porting or developer-provided hints. Our work is based on Binary Acceleration At Runtime (BAAR), our previously introduced binary acceleration mechanism that uses the LLVM Compiler Infrastructure. BAAR is designed as a client-server architecture. The client runs the program to be accelerated in an environment, which allows program analysis and profiling and identifies and extracts suitable program parts to be offloaded. The server compiles and optimizes these offloaded program parts for the accelerator and offers access to these functions to the client with a remote procedure call (RPC) interface. Our previous work proved the feasibility of our approach, but also showed that communication time and overheads limit the granularity of functions that can be meaningfully offloaded. In this work, we motivate the importance of a lightweight, high-performance communication between server and client and present a communication mechanism based on the Message Passing Interface (MPI). We evaluate our approach by using an Intel Xeon Phi 5110P as the acceleration target and show that the communication overhead can be reduced from 40% to 10%, thus enabling even small hotspots to benefit from offloading to an accelerator.

Vertical Thread Migration in FPGA based Sound Localization - Wagener, Peter

Thread Shadowing: Using Dynamic Redundancy on Hybrid Multi-cores for Error Detection - Meisner, Sebastian; Platzner, Marco (Proceedings of the 10th International Symposium on Applied Reconfigurable Computing (ARC))
Dynamic thread duplication is a known redundancy technique for multi-cores. The approach duplicates a thread under observation for some time period and compares the signatures of the two threads to detect errors. Hybrid multi-cores, typically implemented on platform FPGAs, enable the unique option of running the thread under observation and its copy in different modalities, i.e., software and hardware. We denote our dynamic redundancy technique on hybrid multi-cores as thread shadowing. In this paper we present the concept of thread shadowing and an implementation on a multi-threaded hybrid multi-core architecture. We report on experiments with a block-processing application and demonstrate the overheads, detection latencies and coverage for a range of thread shadowing modes. The results show that trans-modal thread shadowing, although bearing long detection latencies, offers attractive coverage at a low overhead.

The Xilinx Zynq Architecture as a Platform for Reconfigurable Heterogeneous Multi-Cores - Rüthing, Christoph

Scheduling Shared Continuous Resources on Many-Cores - Brinkmann, Andre; Kling, Peter; Meyer auf der Heide, Friedhelm; Nagel, Lars; Riechers, Sören; Suess, Tim (Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA))
We consider the problem of scheduling a number of jobs on $m$ identical processors sharing a continuously divisible resource. Each job j comes with a resource requirement r_j \in {0,1}. The job can be processed at full speed if granted its full resource requirement. If receiving only an x-portion of r_j, it is processed at an x-fraction of the full speed. Our goal is to find a resource assignment that minimizes the makespan (i.e., the latest completion time). Variants of such problems, relating the resource assignment of jobs to their processing speeds, have been studied under the term discrete-continuous scheduling. Known results are either very pessimistic or heuristic in nature.In this paper, we suggest and analyze a slightly simplified model. It focuses on the assignment of shared continuous resources to the processors. The job assignment to processors and the ordering of the jobs have already been fixed. It is shown that, even for unit size jobs, finding an optimal solution is NP-hard if the number of processors is part of the input. Positive results for unit size jobs include an efficient optimal algorithm for 2 processors. Moreover, we prove that balanced schedules yield a 2-1/m-approximation for a fixed number of processors. Such schedules are computed by our GreedyBalance algorithm, for which the bound is tight.

Relocatable Hardware Threads in Run-Time Reconfigurable Systems - Wold, Alexander; Agne, Andreas; Torresen, Jim (Proceedings of the 10th International Symposium on Reconfigurable Computing: Architectures, Tools, and Applications)
Run-time reconfiguration provides an opportunity to increase performance, reduce cost and improve energy efficiency in FPGA-based systems. However, run-time reconfigurable systems are more complex to implement than static only systems. This increases time to market, and introduces run-time overhead into the system. Our research aims to raise the abstraction level to develop run-time reconfigurable systems. We present operating system extensions which enable seamless integration of run-time reconfigurable hardware threads into applications. To improve resource utilization, the hardware threads are placed on a fine granularity tile grid. We take advantage of a relocatable module placer targeting modern FPGA to manage the reconfigurable area. The module placer accurately models the FPGA resources to compute feasible placement locations for the hardware threads at run-time. Finally, we evaluate our work by means of a case study that consists of a synthetic application to validate the functionality and performance of the implementation. The results show a reduction in reconfiguration time of up to 42% and more than double resource utilization.

Budget-restricted utility games with ordered strategic decisions - Drees, Maximilian; Riechers, Sören; Skopalik, Alexander (Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT))
We introduce the concept of budget games. Players choose a set of tasks and each task has a certain demand on every resource in the game. Each resource has a budget. If the budget is not enough to satisfy the sum of all demands, it has to be shared between the tasks. We study strategic budget games, where the budget is shared proportionally. We also consider a variant in which the order of the strategic decisions influences the distribution of the budgets. The complexity of the optimal solution as well as existence, complexity and quality of equilibria are analysed. Finally, we show that the time an ordered budget game needs to convergence towards an equilibrium may be exponential.

Advanced AES-key recovery from decayed RAM-dumps using multi-threading and FPGAs - Mittendorf, Robert

A generalized loop accelerator implemented as a coarse grained array - Brand, Marcel

Energy-efficient Scheduling Algorithms - Kling, Peter
In meiner Dissertation beschäftige ich mich mit dem Entwurf und der Analyse energieeffizienter Schedulingalgorithmen, insbesondere für sogenannte Speed-Scaling Modelle. Diese stellen das theoretische Pendant von Techniken wie AMDs PowerNOW! und Intels SpeedStep dar, welche es erlauben die Geschwindigkeit von Prozessoren zur Laufzeit an die derzeitigen Bedingungen anzupassen. Theoretische Untersuchungen solcher Modelle sind auf eine Arbeit von Yao, Demers und Shenker (FOCS'95) zurückzuführen. Hier kombinieren die Autoren klassisches Deadline-Scheduling mit einem Prozessor der Speed-Scaling beherrscht. Es gilt Jobs verschiedener Größe fristgerecht abzuarbeiten und die dabei verwendete Energie zu minimieren. Der Energieverbrauch des Prozessors wird durch eine konvexe Funktion $\POW\colon\R_{≥0}→\R_{≥0}$ modelliert, welche die Geschwindigkeit auf den Energieverbrauch abbildet.Meine Dissertation betrachtet verschiedene Varianten des ursprünglichen Speed-Scaling Modells. Forschungsrelevante Ergebnisse sind in den Kapiteln 3 bis 6 zu finden und erstrecken sich über die im Folgenden beschriebenen Aspekte:- Kapitel 3 und 4 betrachten verschiedene Price-Collecting Varianten des Originalproblems. Hier dürfen einzelne Deadlines verfehlt werden, sofern eine jobabhängige Strafe gezahlt wird. Ich entwerfe insbesondere Online-Algorithmen mit einer beweisbar guten Competitiveness. Dabei liefern meine Ergebnisse substantielle Verbesserungen bestehender Arbeiten und erweitern diese unter Anderem auf Szenarien mit mehreren Prozessoren.- In Kapitel 5 wird statt des klassischen Deadline-Schedulings eine Linearkombination der durchschnittlichen Antwortzeit und des Energieverbrauchs betrachtet. Die Frage, ob dieses Problem NP-schwer ist, stellt eine der zentralen Forschungsfragen in diesem Gebiet dar. Für eine relaxierte Form dieser Frage entwerfe ich einen effizienter Algorithmus und beweise seine Optimalität.- Das letzte Kapitel betrachtet ein Modell, welches – auf den ersten Blick – nicht direkt zur Speed-Scaling Literatur zählt. Hier geht es stattdessen um ein allgemeines Resource-Constrained Scheduling, in dem sich die Prozessoren zusammen eine gemeinsame, beliebig aufteilbare Ressource teilen. Ich untersuche die Komplexität des Problems und entwerfe verschiedene Approximationsalgorithmen.

Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules - Antoniadis, Antonios; Barcelo, Neal; Consuegra, Mario; Kling, Peer; Nugent, Michael; Pruhs, Kirk; Scquizzato, Michele (Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS))
We give a polynomial time algorithm to compute an optimal energy and fractional weighted flow trade-off schedule for a speed-scalable processor with discrete speeds.Our algorithm uses a geometric approach that is based on structural properties obtained from a primal-dual formulation of the problem.

Easy-to-use on-the-fly binary program acceleration on many-cores - Damschen, Marvin

Verschiebungen an der Grenze zwischen Hardware und Software - Platzner, Marco; Plessl, Christian (Logiken strukturbildender Prozesse: Automatismen)
Im Bereich der Computersysteme ist die Festlegung der Grenze zwischen Hardware und Software eine zentrale Problemstellung. Diese Grenze hat in den letzten Jahrzehnten nicht nur die Entwicklung von Computersystemen bestimmt, sondern auch die Strukturierung der Ausbildung in den Computerwissenschaften beeinﬂusst und sogar zur Entstehung von neuen Forschungsrichtungen geführt. In diesem Beitrag beschäftigen wir uns mit Verschiebungen an der Grenze zwischen Hardware und Software und diskutieren insgesamt drei qualitativ unterschiedliche Formen solcher Verschiebungen. Wir beginnen mit der Entwicklung von Computersystemen im letzten Jahrhundert und der Entstehung dieser Grenze, die Hardware und Software erst als eigenständige Produkte diﬀerenziert. Dann widmen wir uns der Frage, welche Funktionen in einem Computersystem besser in Hardware und welche besser in Software realisiert werden sollten, eine Fragestellung die zu Beginn der 90er-Jahre zur Bildung einer eigenen Forschungsrichtung, dem sogenannten Hardware/Software Co-design, geführt hat. Im Hardware/Software Co-design ﬁndet eine Verschiebung von Funktionen an der Grenze zwischen Hardware und Software während der Entwicklung eines Produktes statt, um Produkteigenschaften zu optimieren. Im fertig entwickelten und eingesetzten Produkt hingegen können wir dann eine feste Grenze zwischen Hardware und Software beobachten. Im dritten Teil dieses Beitrags stellen wir mit selbst-adaptiven Systemen eine hochaktuelle Forschungsrichtung vor. In unserem Kontext bedeutet Selbstadaption, dass ein System Verschiebungen von Funktionen an der Grenze zwischen Hardware und Software autonom während der Betriebszeit vornimmt. Solche Systeme beruhen auf rekonﬁgurierbarer Hardware, einer relativ neuen Technologie mit der die Hardware eines Computers während der Laufzeit verändert werden kann. Diese Technologie führt zu einer durchlässigen Grenze zwischen Hardware und Software bzw. löst sie die herkömmliche Vorstellung einer festen Hardware und einer ﬂexiblen Software damit auf.

Partitioning and Vectorizing Binary Applications for a Reconfigurable Vector Computer - Kenter, Tobias; Vaz, Gavin Francis; Plessl, Christian (Proceedings of the International Symposium on Reconfigurable Computing: Architectures, Tools, and Applications (ARC))
In order to leverage the use of reconfigurable architectures in general-purpose computing, quick and automated methods to find suitable accelerator designs are required. We tackle this challenge in both regards. In order to avoid long synthesis times, we target a vector copro- cessor, implemented on the FPGAs of a Convey HC-1. Previous studies showed that existing tools were not able to accelerate a real-world application with low effort. We present a toolflow to automatically identify suitable loops for vectorization, generate a corresponding hardware/software bipartition, and generate coprocessor code. Where applicable, we leverage outer-loop vectorization. We evaluate our tools with a set of characteristic loops, systematically analyzing different dependency and data layout properties.

Seven Recipes for Setting Your FPGA on Fire – A Cookbook on Heat Generators - Agne, Andreas; Hangmann, Hendrik; Happe, Markus; Platzner, Marco; Plessl, Christian (Microprocessors and Microsystems)
Due to the continuously shrinking device structures and increasing densities of FPGAs, thermal aspects have become the new focus for many research projects over the last years. Most researchers rely on temperature simulations to evaluate their novel thermal management techniques. However, these temperature simulations require a high computational effort if a detailed thermal model is used and their accuracies are often unclear. In contrast to simulations, the use of synthetic heat sources allows for experimental evaluation of temperature management methods. In this paper we investigate the creation of significant rises in temperature on modern FPGAs to enable future evaluation of thermal management techniques based on experiments. To that end, we have developed seven different heat-generating cores that use different subsets of FPGA resources. Our experimental results show that, according to external temperature probes connected to the FPGA’s heat sink, we can increase the temperature by an average of 81 !C. This corresponds to an average increase of 156.3 !C as measured by the built-in thermal diodes of our Virtex-5 FPGAs in less than 30 min by only utilizing about 21 percent of the slices.

Reconstructing AES Key Schedules from Decayed Memory with FPGAs - Riebler, Heinrich; Kenter, Tobias; Plessl, Christian; Sorge, Christoph (Proceedings of Field-Programmable Custom Computing Machines (FCCM))
In this paper, we study how AES key schedules can be reconstructed from decayed memory. This operation is a crucial and time consuming operation when trying to break encryption systems with cold-boot attacks. In software, the reconstruction of the AES master key can be performed using a recursive, branch-and-bound tree-search algorithm that exploits redundancies in the key schedule for constraining the search space. In this work, we investigate how this branch-and-bound algorithm can be accelerated with FPGAs. We translated the recursive search procedure to a state machine with an explicit stack for each recursion level and create optimized datapaths to accelerate in particular the processing of the most frequently accessed tree levels. We support two different decay models, of which especially the more realistic non-idealized asymmetric decay model causes very high runtimes in software. Our implementation on a Maxeler dataflow computing system outperforms a software implementation for this model by up to 27x, which makes cold-boot attacks against AES practical even for high error rates.
Keywords: coldboot

Self-awareness as a Model for Designing and Operating Heterogeneous Multicores - Agne, Andreas; Happe, Markus; Lösch, Achim; Plessl, Christian; Platzner, Marco (ACM Transactions on Reconfigurable Technology and Systems (TRETS))
Self-aware computing is a paradigm for structuring and simplifying the design and operation of computing systems that face unprecedented levels of system dynamics and thus require novel forms of adaptivity. The generality of the paradigm makes it applicable to many types of computing systems and, previously, researchers started to introduce concepts of self-awareness to multicore architectures. In our work we build on a recent reference architectural framework as a model for self-aware computing and instantiate it for an FPGA-based heterogeneous multicore running the ReconOS reconfigurable architecture and operating system. After presenting the model for self-aware computing and ReconOS, we demonstrate with a case study how a multicore application built on the principle of self-awareness, autonomously adapts to changes in the workload and system state. Our work shows that the reference architectural framework as a model for self-aware computing can be practically applied and allows us to structure and simplify the design process, which is essential for designing complex future computing systems.

ReconOS - An Operating System Approach for Reconfigurable Computing - Agne, Andreas; Happe, Markus; Keller, Ariane; Lübbers, Enno; Plattner, Bernhard; Platzner, Marco; Plessl, Christian (IEEE Micro)
The ReconOS operating system for reconfigurable computing offers a unified multi-threaded programming model and operating system services for threads executing in software and threads mapped to reconfigurable hardware. The operating system interface allows hardware threads to interact with software threads using well-known mechanisms such as semaphores, mutexes, condition variables, and message queues. By semantically integrating hardware accelerators into a standard operating system environment, ReconOS allows for rapid design space exploration, supports a structured application development process and improves the portability of applications

Deferring Accelerator Offloading Decisions to Application Runtime - Vaz, Gavin Francis; Riebler, Heinrich; Kenter, Tobias; Plessl, Christian (Proceedings of the International Conference on ReConFigurable Computing and FPGAs (ReConFig))
Reconfigurable architectures provide an opportunityto accelerate a wide range of applications, frequentlyby exploiting data-parallelism, where the same operations arehomogeneously executed on a (large) set of data. However, whenthe sequential code is executed on a host CPU and only dataparallelloops are executed on an FPGA coprocessor, a sufficientlylarge number of loop iterations (trip counts) is required, such thatthe control- and data-transfer overheads to the coprocessor canbe amortized. However, the trip count of large data-parallel loopsis frequently not known at compile time, but only at runtime justbefore entering a loop. Therefore, we propose to generate codeboth for the CPU and the coprocessor, and to defer the decisionwhere to execute the appropriate code to the runtime of theapplication when the trip count of the loop can be determinedjust at runtime. We demonstrate how an LLVM compiler basedtoolflow can automatically insert appropriate decision blocks intothe application code. Analyzing popular benchmark suites, weshow that this kind of runtime decisions is often applicable. Thepractical feasibility of our approach is demonstrated by a toolflowthat automatically identifies loops suitable for vectorization andgenerates code for the FPGA coprocessor of a Convey HC-1. Thetoolflow adds decisions based on a comparison of the runtimecomputedtrip counts to thresholds for specific loops and alsoincludes support to move just the required data to the coprocessor.We evaluate the integrated toolflow with characteristic loopsexecuted on different input data sizes.

Kernel-Centric Acceleration of High Accuracy Stereo-Matching - Kenter, Tobias; Schmitz, Henning; Plessl, Christian (Proceedings of the International Conference on ReConFigurable Computing and FPGAs (ReConFig))
Stereo-matching algorithms recently received a lot of attention from the FPGA acceleration community. Presented solutions range from simple, very resource efficient systems with modest matching quality for small embedded systems to sophisticated algorithms with several processing steps, implemented on big FPGAs. In order to achieve high throughput, most implementations strongly focus on pipelining and data reuse between different computation steps. This approach leads to high efficiency, but limits the supported computation patterns and due the high integration of the implementation, adaptions to the algorithm are difficult. In this work, we present a stereo-matching implementation, that starts by offloading individual kernels from the CPU to the FPGA. Between subsequent compute steps on the FPGA, data is stored off-chip in on-board memory of the FPGA accelerator card. This enables us to accelerate the AD-census algorithm with cross-based aggregation and scanline optimization for the first time without algorithmic changes and for up to full HD image dimensions. Analyzing throughput and bandwidth requirements, we outline some trade-offs that are involved with this approach, compared to tighter integration of more kernel loops into one design.

Scheduling Variants with Speed-Scaling via the Primal-Dual Approach - Knopf, Michael

Profitable Scheduling on Multiple Speed-Scalable Processors - Kling, Peter; Pietrzyk, Peter (Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA))
We present a new online algorithm for profit-oriented scheduling on multiple speed-scalable processors.Moreover, we provide a tight analysis of the algorithm's competitiveness.Our results generalize and improve upon work by \citet{Chan:2010}, which considers a single speed-scalable processor.Using significantly different techniques, we can not only extend their model to multiprocessors but also prove an enhanced and tight competitive ratio for our algorithm.In our scheduling problem, jobs arrive over time and are preemptable.They have different workloads, values, and deadlines.The scheduler may decide not to finish a job but instead to suffer a loss equaling the job's value.However, to process a job's workload until its deadline the scheduler must invest a certain amount of energy.The cost of a schedule is the sum of lost values and invested energy.In order to finish a job the scheduler has to determine which processors to use and set their speeds accordingly.A processor's energy consumption is power $\Power{s}$ integrated over time, where $\Power{s}=s^{α}$ is the power consumption when running at speed $s$.Since we consider the online variant of the problem, the scheduler has no knowledge about future jobs.This problem was introduced by~\citet{Chan:2010} for the case of a single processor.They presented an online algorithm which is $α^{α}+2eα$-competitive.We provide an online algorithm for the case of multiple processors with an improved competitive ratio of $α^{α}$.

Performance and thermal management on self-adaptive hybrid multi-cores - Happe, Markus
Handling run-time dynamics on embedded system-on-chip architectures has become more challenging over the years. On the one hand, the impact of workload and physical dynamics on the system behavior has dramatically increased. On the other hand, embedded architectures have become more complex as they have evolved from single-processor systems over multi-processor systems to hybrid multi-core platforms.Static design-time techniques no longer provide suitable solutions to deal with the run-time dynamics of today's embedded systems. Therefore, system designers have to apply run-time solutions, which have hardly been investigated for hybrid multi-core platforms.In this thesis, we present fundamental work in the new area of run-time management on hybrid multi-core platforms. We propose a novel architecture, a self-adaptive hybrid multi-core system, that combines heterogeneous processors, reconfigurable hardware cores, and monitoring cores on a single chip. Using self-adaptation on thread-level, our hybrid multi-core systems can effectively perform performance and thermal management autonomously at run-time.

Identifikation und Wiederherstellung von kryptographischen Schlüsseln mit FPGAs - Riebler, Heinrich
Keywords: coldboot

Beschleunigung von Tiefenberechung aus Stereobildern durch FPGA-basierte Datenflussrechner - Bick, Christian

Bandbreiten-beschränktes Scheduling mit skalierbaren Jobanforderungen in Multiprozessor-Umgebungen - Meschede, Julian

FPGA-accelerated Key Search for Cold-Boot Attacks against AES - Riebler, Heinrich; Kenter, Tobias; Sorge, Christoph; Plessl, Christian (Proceedings of the International Conference on Field-Programmable Technology (FPT))
Cold-boot attacks exploit the fact that DRAM contents are not immediately lost when a PC is powered off. Instead the contents decay rather slowly, in particular if the DRAM chips are cooled to low temperatures. This effect opens an attack vector on cryptographic applications that keep decrypted keys in DRAM. An attacker with access to the target computer can reboot it or remove the RAM modules and quickly copy the RAM contents to non-volatile memory. By exploiting the known cryptographic structure of the cipher and layout of the key data in memory, in our application an AES key schedule with redundancy, the resulting memory image can be searched for sections that could correspond to decayed cryptographic keys; then, the attacker can attempt to reconstruct the original key. However, the runtime of these algorithms grows rapidly with increasing memory image size, error rate and complexity of the bit error model, which limits the practicability of the approach.In this work, we study how the algorithm for key search can be accelerated with custom computing machines. We present an FPGA-based architecture on a Maxeler dataflow computing system that outperforms a software implementation up to 205x, which significantly improves the practicability of cold-attacks against AES.
Keywords: coldboot

On-The-Fly Computing: A Novel Paradigm for Individualized IT Services - Happe, Markus; Kling, Peter; Plessl, Christian; Platzner, Marco; Meyer auf der Heide, Friedhelm (Proceedings of the 9th IEEE Workshop on Software Technology for Future embedded and Ubiquitous Systems (SEUS))
In this paper we introduce “On-The-Fly Computing”, our vision of future IT services that will be provided by assembling modular software components available on world-wide markets. After suitable components have been found, they are automatically integrated, configured and brought to execution in an On-The-Fly Compute Center. We envision that these future compute centers will continue to leverage three current trends in large scale computing which are an increasing amount of parallel processing, a trend to use heterogeneous computing resources, and—in the light of rising energy cost—energy-efficiency as a primary goal in the design and operation of computing systems. In this paper, we point out three research challenges and our current work in these areas.

Stereo Matching on a Convey HC-1 Hybrid Core Computer - Schmitz, Henning

Slow Down & Sleep for Profit in Online Deadline Scheduling - Cord-Landwehr, Andreas; Kling, Peter; Mallmann Trenn, Fredrik (Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg))
We present and study a new model for energy-aware and profit-oriented scheduling on a single processor.The processor features dynamic speed scaling as well as suspension to a sleep mode.Jobs arrive over time, are preemptable, and have different sizes, values, and deadlines.On the arrival of a new job, the scheduler may either accept or reject the job.Accepted jobs need a certain energy investment to be finished in time, while rejected jobs cause costs equal to their values.Here, power consumption at speed $s$ is given by $P(s)=s^{α}+β$ and the energy investment is power integrated over time.Additionally, the scheduler may decide to suspend the processor to a sleep mode in which no energy is consumed, though awaking entails fixed transition costs $γ$.The objective is to minimize the total value of rejected jobs plus the total energy.Our model combines aspects from advanced energy conservation techniques (namely speed scaling and sleep states) and profit-oriented scheduling models.We show that rejection-oblivious schedulers (whose rejection decisions are not based on former decisions) have – in contrast to the model without sleep states – an unbounded competitive ratio.It turns out that the jobs' value densities (the ratio between a job's value and its work) are crucial for the performance of such schedulers.We give an algorithm whose competitiveness nearly matches the lower bound w.r.t\text{.} the maximum value density.If the maximum value density is not too large, the competitiveness becomes $α^{α}+2eα$.Also, we show that it suffices to restrict the value density of low-value jobs only.Using a technique from \cite{Chan:2010} we transfer our results to processors with a fixed maximum speed.

Programming models for reconfigurable heterogeneous multi-cores - Plessl, Christian; Platzner, Marco; Agne, Andreas; Happe, Markus; Lübbers, Enno

On scheduling with multi-core and multi-speed processors using power down - Mallmann Trenn, Frederik

Generating Adjustable Temperature Gradients on modern FPGAs - Hangmann, Hendrik

Analyse und Simulation von energieeffizienten Online-Scheduling Algorithmen - Kratzmann, Julian

An outlook for self-awareness in computing systems - Lewis, Peter; Platzner, Marco; Yao, Xin

Eight Ways to put your FPGA on Fire – A Systematic Study of Heat Generators - Happe, Markus; Hangmann, Hendrik; Agne, Andreas; Plessl, Christian (Proceedings of the International Conference on Reconfigurable Computing and FPGAs (ReConFig))
Due to the continuously shrinking device structures and increasing densities of FPGAs, thermal aspects have become the new focus for many research projects over the last years. Most researchers rely on temperature simulations to evaluate their novel thermal management techniques. However, the accuracy of the simulations is to some extent questionable and they require a high computational effort if a detailed thermal model is used.For experimental evaluation of real-world temperature management methods, often synthetic heat sources are employed. Therefore, in this paper we investigated the question if we can create significant rises in temperature on modern FPGAs to enable future evaluation of thermal management techniques based on experiments in contrast to simulations. Therefore, we have developed eight different heat-generating cores that use different subsets of the FPGA resources. Our experimental results show that, according to the built-in thermal diode of our Xilinx Virtex-5 FPGA, we can increase the chip temperature by 134 degree C in less than 12 minutes by only utilizing about 21% of the slices.

Pragma based parallelization - Trading hardware efficiency for ease of use? - Kenter, Tobias; Plessl, Christian; Schmitz, Henning (Proceedings of the International Conference on ReConFigurable Computing and FPGAs (ReConFig))
One major obstacle for a wide spread FPGA usage in general-purpose computing is the development tool flow that requires much higher effort than for pure software solutions. Convey Computer promises a solution to this problem for their HC-1 platform, where the FPGAs are conﬁgured to run as a vector processor and the software source code can be annotated with pragmas that guide an automated vectorization process. We investigate this approach for a stereo matching algorithm that has abundant parallelism and a number of different computational patterns. We note that for this case study the automated vectorization in its current state doesn’t hold its productivity promise. However, we also show that using the Vector Personality can yield a signiﬁcant speedups compared to CPU implementations in two of three investigated phases of the algorithm. Those speedups don’t match custom FPGA implementations, but can come with much reduced development effort.

Hardware/Software Platform for Self-aware Compute Nodes - Happe, Markus; Agne, Andreas; Plessl, Christian; Platzner, Marco (Proceedings of the Workshop on Self-Awareness in Reconfigurable Computing Systems (SRCS))
Today's design and operation principles and methods do not scale well with future reconfigurable computing systems due to an increased complexity in system architectures and applications, run-time dynamics and corresponding requirements. Hence, novel design and operation principles and methods are needed that possibly break drastically with the static ones we have built into our systems and the fixed abstraction layers we have cherished over the last decades. Thus, we propose a HW/SW platform that collects and maintains information about its state and progress which enables the system to reason about its behavior (self-awareness) and utilizes its knowledge to effectively and autonomously adapt its behavior to changing requirements (self-expression).To enable self-awareness, our compute nodes collect information using a variety of sensors, i.e. performance counters and thermal diodes, and use internal self-awareness models that process these information. For self-awareness, on-line learning is crucial such that the node learns and continuously updates its models at run-time to react to changing conditions. To enable self-expression, we break with the classic design-time abstraction layers of hardware, operating system and software. In contrast, our system is able to vertically migrate functionalities between the layers at run-time to exploit trade-offs between abstraction and optimization.This paper presents a heterogeneous multi-core architecture, that enables self-awareness and self-expression, an operating system for our proposed hardware/software platform and a novel self-expression method.

Turning control flow graphs into function calls: Code generation for heterogeneous architectures - Barrio, Pablo; Carreras, Carlos; Sierra, Roberto; Kenter, Tobias; Plessl, Christian (Proceedings of the International Conference on High Performance Computing and Simulation (HPCS))
Heterogeneous machines are gaining momentum in the High Performance Computing field, due to the theoretical speedups and power consumption. In practice, while some applications meet the performance expectations, heterogeneous architectures still require a tremendous effort from the application developers. This work presents a code generation method to port codes into heterogeneous platforms, based on transformations of the control flow into function calls. The results show that the cost of the function-call mechanism is affordable for the tested HPC kernels. The complete toolchain, based on the LLVM compiler infrastructure, is fully automated once the sequential specification is provided.

Exploration of Ring Oscillator Design Space for Temperature Measurements on FPGAs - Rüthing, Christoph; Happe, Markus; Agne, Andreas; Plessl, Christian (Proceedings of the International Conference on Field Programmable Logic and Applications (FPL))
While numerous publications have presented ring oscillator designs for temperature measurements a detailed study of the ring oscillator's design space is still missing. In this work, we introduce metrics for comparing the performance and area efficiency of ring oscillators and a methodology for determining these metrics. As a result, we present a systematic study of the design space for ring oscillators for a Xilinx Virtex-5 platform FPGA.

User-space Scheduling for Heterogeneous System under Linux - Welp, Daniel

An Experimental Comparison of Load Balancing Strategies in a Web Computing Environment - Gehweiler, Joachim; Kling, Peter; Meyer auf der Heide, Friedhelm (Proceedings of the 9th International Conference on Parallel Processing and Applied Mathematics (PPAM))
Web Computing is a variant of parallel computing where the idle times of PCs donated by worldwide distributed users are employed to execute parallel programs. The PUB-Web library developed by us supports this kind of usage of computing resources. A major problem for the efficient execution of such parallel programs is load balancing. In the Web Computing context, this problem becomes more difficult because of the dynamic behavior of the underlying "parallel computer": the set of available processors (donated PCs) as well as their availability (idle times) change over time in an unpredictable fashion.In this paper, we experimentally evaluate and compare load balancing algorithms in this scenario, namely a variant of the well-established Work Stealing algorithm and strategies based on a heterogeneous version of distributed hash-tables (DHHTs) introduced recently. In order to run a meaningful experimental evaluation, we employ, in addition to our Web Computing library PUB-Web, realistic data sets for the job input streams and for the dynamics of the availability of the resources.Our experimental evaluations suggest that Work Stealing is the better strategy if the number of processes ready to run matches the number of available processors. But a suitable variant of DHHTs outperforms Work Stealing if there are significantly more processes ready to run than available processors.

Measuring and Predicting Temperature Distributions on FPGAs at Run-Time - Happe, Markus; Agne, Andreas; Plessl, Christian (Proceedings of the 2011 International Conference on Reconfigurable Computing and FPGAs (ReConFig))
In the next decades, hybrid multi-cores will be the predominant architecture for reconfigurable FPGA-based systems. Temperature-aware thread mapping strategies are key for providing dependability in such systems. These strategies rely on measuring the temperature distribution and redicting the thermal behavior of the system when there are changes to the hardware and software running on the FPGA. While there are a number of tools that use thermal models to predict temperature distributions at design time, these tools lack the flexibility to autonomously adjust to changing FPGA configurations. To address this problem we propose a temperature-aware system that empowers FPGA-based reconfigurable multi-cores to autonomously predict the on-chip temperature distribution for pro-active thread remapping. Our system obtains temperature measurements through a self-calibrating grid of sensors and uses area constrained heat-generating circuits in order to generate spatial and temporal temperature gradients. The generated temperature variations are then used to learn the free parameters of the system's thermal model. The system thus acquires an understanding of its own thermal characteristics. We implemented an FPGA system containing a net of 144 temperature sensors on a Xilinx Virtex-6 LX240T FPGA that is aware of its thermal model. Finally, we show that the temperature predictions vary less than 0.72 degree C on average compared to the measured temperature distributions at run-time.