Approximation Algorithms for QMA-Complete Problems - Gharibian, Sevag; Kempe, Julia (SIAM Journal on Computing)
Approximation algorithms for classical constraint satisfaction problems are one of the main research areas in theoretical computer science. Here we define a natural approximation version of the QMA-complete local Hamiltonian problem (where QMA stands for Quantum Merlin Arthur) and initiate its study. We present two main results. The first shows that a nontrivial approximation ratio can be obtained in the class NP using product states. The second result (which builds on the first one) gives a polynomial time (classical) algorithm providing a similar approximation ratio for dense instances of the problem. The latter result is based on an adaptation of the “exhaustive sampling method” by Arora, Karger, and Karpinski [J. Comput. System Sci., 58 (1999), p. 193] to the quantum setting and might be of independent interest.

Quantifying nonclassicality with local unitary operations - Gharibian, Sevag (Physical Review A)
We propose a measure of non-classical correlations in bipartite quantum states based on local unitary operations. We prove the measure is non-zero if and only if the quantum discord is non-zero; this is achieved via a new characterization of zero discord states in terms of the state's correlation matrix. Moreover, our scheme can be extended to ensure the same relationship holds even with a generalized version of quantum discord in which higher-rank projective measurements are allowed. We next derive a closed form expression for our scheme in the cases of Werner states and (2 x N)-dimensional systems. The latter reveals that for (2 x N)-dimensional states, our measure reduces to the geometric discord [Dakic et al., PRL 105, 2010]. A connection to the CHSH inequality is shown. We close with a characterization of all maximally non-classical, yet separable, (2 x N)-dimensional states of rank at most two (with respect to our measure).

Convey Vector Personalities – FPGA Acceleration with an OpenMP-like Effort? - Meyer, Björn; Schumacher, Jörn; Plessl, Christian; Förstner, Jens (Proc. Int. Conf. on Field Programmable Logic and Applications (FPL))
Although the benefits of FPGAs for accelerating scientific codes are widely acknowledged, the use of FPGA accelerators in scientific computing is not widespread because reaping these benefits requires knowledge of hardware design methods and tools that is typically not available with domain scientists. A promising but hardly investigated approach is to develop tool flows that keep the common languages for scientific code (C,C++, and Fortran) and allow the developer to augment the source code with OpenMPlike directives for instructing the compiler which parts of the application shall be offloaded the FPGA accelerator. In this work we study whether the promise of effective FPGA acceleration with an OpenMP-like programming effort can actually be held. Our target system is the Convey HC-1 reconfigurable computer for which an OpenMP-like programming environment exists. As case study we use an application from computational nanophotonics. Our results show that a developer without previous FPGA experience could create an FPGA-accelerated application that is competitive to an optimized OpenMP-parallelized CPU version running on a two socket quad-core server. Finally, we discuss our experiences with this tool flow and the Convey HC-1 from a productivity and economic point of view.
Keywords: funding-upb-forschungspreis; funding-maxup; tet_topic_hpc

IMORC: An Infrastructure and Architecture Template for Implementing High-Performance Reconfigurable FPGA Accelerators - Schumacher, Tobias; Plessl, Christian; Platzner, Marco (Microprocessors and Microsystems)
Keywords: funding-altera

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.

Programming and Scheduling Model for Supporting Heterogeneous Accelerators in Linux - Beisel, Tobias; Wiersema, Tobias; Plessl, Christian; Brinkmann, André (Proc. Workshop on Computer Architecture and Operating System Co-design (CAOS))
Keywords: funding-enhance

On the Feasibility and Limitations of Just-In-Time Instruction Set Extension for FPGA-based Reconfigurable Processors - Grad, Mariusz; Plessl, Christian (Int. Journal of Reconfigurable Computing (IJRC))

On the Properties of the R2 Indicator - Brockhoff, Dimo; Wagner, Tobias; Trautmann, Heike (Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation)
In multiobjective optimization, set-based performance indicators are commonly used to assess the quality of a Pareto front approximation. Based on the scalarization obtained by these indicators, a performance comparison of multiobjective optimization algorithms becomes possible. The R2 and the Hypervolume (HV) indicator represent two recommended approaches which have shown a correlated behavior in recent empirical studies. Whereas the HV indicator has been comprehensively analyzed in the last years, almost no studies on the R2 indicator exist. In this paper, we thus perform a comprehensive investigation of the properties of the R2 indicator in a theoretical and empirical way. The influence of the number and distribution of the weight vectors on the optimal distribution of μ solutions is analyzed. Based on a comparative analysis, specific characteristics and differences of the R2 and HV indicator are presented.
Keywords: hypervolume indicator; multiobjective optimization; performance assessment; r2 indicator

Algorithm Selection Based on Exploratory Landscape Analysis and Cost-Sensitive Learning - Bischl, Bernd; Mersmann, Olaf; Trautmann, Heike; Preuß, Mike (Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation)
The steady supply of new optimization methods makes the algorithm selection problem (ASP) an increasingly pressing and challenging task, specially for real-world black-box optimization problems. The introduced approach considers the ASP as a cost-sensitive classification task which is based on Exploratory Landscape Analysis. Low-level features gathered by systematic sampling of the function on the feasible set are used to predict a well-performing algorithm out of a given portfolio. Example-specific label costs are defined by the expected runtime of each candidate algorithm. We use one-sided support vector regression to solve this learning problem. The approach is illustrated by means of the optimization problems and algorithms of the BBOB’09/10 workshop.
Keywords: machine learning; exploratory landscape analysis; fitness landscape; benchmarking; evolutionary optimization; bbob test set; algorithm selection

Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness - Mersmann, Olaf; Bischl, Bernd; Bossek, Jakob; Trautmann, Heike; Wagner, Markus; Neumann, Frank (Learning and Intelligent Optimization)
With this paper we contribute to the understanding of the success of 2-opt based local search algorithms for solving the traveling salesman problem (TSP). Although 2-opt is widely used in practice, it is hard to understand its success from a theoretical perspective. We take a statistical approach and examine the features of TSP instances that make the problem either hard or easy to solve. As a measure of problem difficulty for 2-opt we use the approximation ratio that it achieves on a given instance. Our investigations point out important features that make TSP instances hard or easy to be approximated by 2-opt.

Resampling Methods in Model Validation - Bischl, B; Mersmann, O; Trautmann, Heike; Weihs, C (Evolutionary Computation Journal)
Meta-modeling has become a crucial tool in solving expensive optimization problems. Much of the work in the past has focused on finding a good regression method to model the fitness function. Examples include classical linear regression, splines, neural networks, Kriging and support vector regression. This paper specifically draws attention to the fact that assessing model accuracy is a crucial aspect in the meta-modeling framework. Resampling strategies such as cross-validation, subsampling, bootstrapping, and nested resampling are prominent methods for model validation and are systematically discussed with respect to possible pitfalls, shortcomings, and specific features. A survey of meta-modeling techniques within evolutionary optimization is provided. In addition, practical examples illustrating some of the pitfalls associated with model selection and performance assessment are presented. Finally, recommendations are given for choosing a model validation technique for a particular setting.

Homogene Approximation der Paretofront bei mehrkriteriellen Kontrollproblemen - Rudolph, G; Trautmann, Heike; Schütze, O (at-Automatisierungstechnik)
Es werden mehrkriterielle evolutio-näre Algorithmen (EMOA) für zwei- und höherdimensio-nale Probleme vorgestellt, die gleichmäßig verteilte Lö-sungen entlang der wahren Paretofront generieren. Diesist insbesondere wichtig im Kontext mehrkriterieller Kon-trollprobleme. Die Methodik beruht auf der Minimierungdes gemittelten Hausdorff-Abstandes in Bezug aufdie Paretofront. Die EMOA-Varianten werden vergleichendzu aktuellen Verfahren auf Benchmarkproblemen getestet.

Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness - Mersmann, Olaf; Bischl, Bernd; Bossek, Jakob; Trautmann, Heike; Wagner, Markus; Neumann, Frank (Revised Selected Papers of the 6th International Conference on Learning and Intelligent Optimization - Volume 7219)
With this paper we contribute to the understanding of the success of 2-opt based local search algorithms for solving the traveling salesman problem TSP. Although 2-opt is widely used in practice, it is hard to understand its success from a theoretical perspective. We take a statistical approach and examine the features of TSP instances that make the problem either hard or easy to solve. As a measure of problem difficulty for 2-opt we use the approximation ratio that it achieves on a given instance. Our investigations point out important features that make TSP instances hard or easy to be approximated by 2-opt.
Keywords: 2-opt; Classification; Feature Selection; MARS; TSP

Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness - Mersmann, Olaf; Bischl, Bernd; Bossek, Jakob; Trautmann, Heike; Wagner, Markus; Neumann, Frank (Learning and Intelligent Optimization)
With this paper we contribute to the understanding of the success of 2-opt based local search algorithms for solving the traveling salesman problem (TSP). Although 2-opt is widely used in practice, it is hard to understand its success from a theoretical perspective. We take a statistical approach and examine the features of TSP instances that make the problem either hard or easy to solve. As a measure of problem difficulty for 2-opt we use the approximation ratio that it achieves on a given instance. Our investigations point out important features that make TSP instances hard or easy to be approximated by 2-opt.

SYSTEMC UVM VERIFICATION COMPONENTS - Kuznik, Christoph; Oliveira, Marcio F.; Müller, Wolfgang (Design, Automation and Test in Europe DATE)
We present an enhanced UVM for SystemC library which incorporates verification best practices from OVM-ML and UVM as well as project partner implementations. Moreover, we extended functionality and implemented missing features, such as domain specific components, stimuli sequence generation and management, call-back facilities, response to request routing, transaction recording and many more. Apart from that, we added crucial verification components, such as functional coverage.

Dynamic Load Balancing in Peer-to-Peer Networks - Korzeniowski, Miroslaw