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.

Improving Packet Processing Performance in the ATLAS FELIX Project – Analysis and Optimization of a Memory-Bounded Algorithm - Schumacher, Jörn; T. Anderson, J.; Borga, A.; Boterenbrood, H.; Chen, H.; Chen, K.; Drake, G.; Francis, D.; Gorini, B.; Lanni, F.; Lehmann-Miotto, Giovanna; Levinson, L.; et al. (Proc. Int. Conf. on Distributed Event-Based Systems (DEBS))

Aktuelles Schlagwort: Approximate Computing - Plessl, Christian; Platzner, Marco; Schreier, Peter J. (Informatik Spektrum)
Keywords: approximate computing; survey

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.

FELIX: a High-Throughput Network Approach for Interfacing to Front End Electronics for ATLAS Upgrades - Anderson, J; Borga, A; Boterenbrood, H; Chen, H; Chen, K; Drake, G; Francis, D; Gorini, B; Lanni, F; Lehmann Miotto, G; Levinson, L; Narevicius, J; et al. (Journal of Physics: Conference Series)
The ATLAS experiment at CERN is planning full deployment of a new unified optical link technology for connecting detector front end electronics on the timescale of the LHC Run 4 (2025). It is estimated that roughly 8000 GBT (GigaBit Transceiver) links, with transfer rates up to 10.24 Gbps, will replace existing links used for readout, detector control and distribution of timing and trigger information. A new class of devices will be needed to interface many GBT links to the rest of the trigger, data-acquisition and detector control systems. In this paper FELIX (Front End LInk eXchange) is presented, a PC-based device to route data from and to multiple GBT links via a high-performance general purpose network capable of a total throughput up to O(20 Tbps). FELIX implies architectural changes to the ATLAS data acquisition system, such as the use of industry standard COTS components early in the DAQ chain. Additionally the design and implementation of a FELIX demonstration platform is presented and hardware and software aspects will be discussed.

An Overview of Topic Discovery in Twitter Communication through Social Media Analytics - Chinnov, Andrey; Kerschke, Pascal; Meske, Christian; Stieglitz, Stefan; Trautmann, Heike (Proceedings of the 20$^th$ Americas Conference on Information Systems (AMCIS ’15))
The need for automatic methods of topic discovery in the Internet grows exponentially with the amount of available textual information. Nowadays it becomes impossible to manually read even a small part of the information in order to reveal the underlying topics. Social media provide us with a great pool of user generated content, where topic discovery may be extremely useful for businesses, politicians, researchers, and other stakeholders. However, conventional topic discovery methods, which are widely used in large text corpora, face several challenges when they are applied in social media and particularly in Twitter – the most popular microblogging platform. To the best of our knowledge no comprehensive overview of these challenges and of the methods dedicated to address these challenges does exist in IS literature until now. Therefore, this paper provides an overview of these challenges, matching methods and their expected usefulness for social media analytics.

Detecting Funnel Structures by Means of Exploratory Landscape Analysis - Kerschke, Pascal; Preuss, Mike; Wessing, Simon; Trautmann, Heike (Proceedings of the Genetic and Evolutionary Computation Conference (GECCO ’15))
In single-objective optimization different optimization strategies exist depending on the structure and characteristics of the underlying problem. In particular, the presence of so-called funnels in multimodal problems offers the possibility of applying techniques exploiting the global structure of the function. The recently proposed Exploratory Landscape Analysis approach automatically identifies problem characteristics based on a moderately small initial sample of the objective function and proved to be effective for algorithm selection problems in continuous black-box optimization. In this paper, specific features for detecting funnel structures are introduced and combined with the existing ones in order to classify optimization problems regarding the funnel property. The effectiveness of the approach is shown by experiments on specifically generated test instances and validation experiments on standard benchmark problems.

Evaluation of a Multi-Objective EA on Benchmark Instances for Dynamic Routing of a Vehicle - Meisel, Stephan; Grimme, Christian; Bossek, Jakob; Wölck, Martin; Rudolph, Guenter; Trautmann, Heike (Proceedings of the Genetic and Evolutionary Computation Conference (GECCO ’15))
We evaluate the performance of a multi-objective evolutionary algorithm on a class of dynamic routing problems with a single vehicle. In particular we focus on relating algorithmic performance to the most prominent characteristics of problem instances. The routing problem considers two types of customers: mandatory customers must be visited whereas optional customers do not necessarily have to be visited. Moreover, mandatory customers are known prior to the start of the tour whereas optional customers request for service at later points in time with the vehicle already being on its way. The multi-objective optimization problem then results as maximizing the number of visited customers while simultaneously minimizing total travel time. As an a-posteriori evaluation tool, the evolutionary algorithm aims at approximating the related Pareto set for specifically designed benchmarking instances differing in terms of number of customers, geographical layout, fraction of mandatory customers, and request times of optional customers. Conceptional and experimental comparisons to online heuristic procedures are provided.

Improving the State of the Art in Inexact TSP Solving Using Per-Instance Algorithm Selection - Kotthoff, Lars; Kerschke, Pascal; Hoos, Holger; Trautmann, Heike (Learning and Intelligent Optimization)
We investigate per-instance algorithm selection techniques for solving the Travelling Salesman Problem (TSP), based on the two state-of-the-art inexact TSP solvers, LKH and EAX. Our comprehensive experiments demonstrate that the solvers exhibit complementary performance across a diverse set of instances, and the potential for improving the state of the art by selecting between them is significant. Using TSP features from the literature as well as a set of novel features, we show that we can capitalise on this potential by building an efficient selector that achieves significant performance improvements in practice. Our selectors represent a significant improvement in the state-of-the-art in inexact TSP solving, and hence in the ability to find optimal solutions (without proof of optimality) for challenging TSP instances in practice.

R2 Indicator Based Multiobjective Search - Brockhoff, D; Wagner, T; Trautmann, Heike (Evolutionary Computation Journal)
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 extended version of our previous conference 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. Furthermore, the R2 indicator is integrated into an indicator-based steady-state evolutionary multiobjective optimization algorithm (EMOA). It is shown that the so-called R2-EMOA can accurately approximate the optimal distribution of µ solutions regarding R2.

Multi-Objective Analysis of Approaches to Dynamic Routing Of a Vehicle - Grimme, C; Meisel, S; Trautmann, Heike; Rudolph, G; Wölck, M (Proceedings of the European Conference On Information Systems)
We consider a routing problem for a single vehicle serving customer Locations in the course of time. A subset of these customers must necessarily be served, while the complement of this subset contains dynamic customers which request for service over time, and which do not necessarily need to be served. The decision maker’s conflicting goals are serving as many customers as possible as well as minimizing total travel distance. We solve this bi-objective Problem with an evolutionary multi-objective algorithm in order to provide an a-posteriori evaluation tool for enabling decision makers to assess the single objective solution strategies that they actually use in real-time. We present the modifications to be applied to the evolutionary multi-objective algorithm NSGA2 in order to solve the routing problem, we describe a number of real-time single-objective solution strategies, and we finally use the gained efficient trade-off solutions of NSGA2 to exemplarily evaluate the real-time strategies. Our results show that the evolutionary multi-objective approach is well-suited to generate benchmarks for assessing dynamic heuristic strategies. Our findings point into future directions for designing dynamic multi-objective approaches for the vehicle routing problem with time windows.

Analyzing the BBOB Results by Means of Benchmarking Concepts - Mersmann, O; Preuss, M; Trautmann, Heike; Bischl, B; Weihs, C (Evolutionary Computation Journal)
We present methods to answer two basic questions that arise when benchmarking optimization algorithms. The first one is: which algorithm is the "best" one? and the second one is: which algorithm should I use for my real-world problem? Both are connected and neither is easy to answer. We present a theoretical framework for designing and analyzing the raw data of such benchmark experiments. This represents a first step in answering the aforementioned questions. The 2009 and 2010 BBOB benchmark results are analyzed by means of this framework and we derive insight regarding the answers to the two questions. Furthermore, we discuss how to properly aggregate rankings from algorithm evaluations on individual problems into a consensus, its theoretical background and which common pitfalls should be avoided. Finally, we address the grouping of test problems into sets with similar optimizer rankings and investigate whether these are reflected by already proposed test problem characteristics, finding that this is not always the case.

VCCFinder: Finding Potential Vulnerabilities in Open-Source Projects to Assist Code Audits - Perl, Henning; Dechand, Sergej; Smith, Matthew; Arp, Daniel; Yamaguchi, Fabian; Rieck, Konrad; Fahl, Sascha; Acar, Yasemin (Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security)

To Pin or Not to Pin-Helping App Developers Bullet Proof Their TLS Connections - Oltrogge, Marten; Acar, Yasemin; Dechand, Sergej; Smith, Matthew; Fahl, Sascha (24th USENIX Security Symposium, USENIX Security 15, Washington, D.C., USA, August 12-14, 2015)

Learning Feature-Parameter Mappings for Parameter Tuning via the Profile Expected Improvement - Bossek, Jakob; Bischl, Bernd; Wagner, Tobias; Rudolph, Günter (Proceedings of the Genetic and Evolutionary Computation Conference)
The majority of algorithms can be controlled or adjusted by parameters. Their values can substantially affect the algorithms’ performance. Since the manual exploration of the parameter space is tedious – even for few parameters – several automatic procedures for parameter tuning have been proposed. Recent approaches also take into account some characteristic properties of the problem instances, frequently termed instance features. Our contribution is the proposal of a novel concept for feature-based algorithm parameter tuning, which applies an approximating surrogate model for learning the continuous feature-parameter mapping. To accomplish this, we learn a joint model of the algorithm performance based on both the algorithm parameters and the instance features. The required data is gathered using a recently proposed acquisition function for model refinement in surrogate-based optimization: the profile expected improvement. This function provides an avenue for maximizing the information required for the feature-parameter mapping, i.e., the mapping from instance features to the corresponding optimal algorithm parameters. The approach is validated by applying the tuner to exemplary evolutionary algorithms and problems, for which theoretically grounded or heuristically determined feature-parameter mappings are available.
Keywords: evolutionary algorithms; model-based optimization; parameter tuning

Evaluation of a Multi-Objective EA on Benchmark Instances for Dynamic Routing of a Vehicle - Meisel, Stephan; Grimme, Christian; Bossek, Jakob; Wölck, Martin; Rudolph, Günter; Trautmann, Heike (Proceedings of the Genetic and Evolutionary Computation Conference)
We evaluate the performance of a multi-objective evolutionary algorithm on a class of dynamic routing problems with a single vehicle. In particular we focus on relating algorithmic performance to the most prominent characteristics of problem instances. The routing problem considers two types of customers: mandatory customers must be visited whereas optional customers do not necessarily have to be visited. Moreover, mandatory customers are known prior to the start of the tour whereas optional customers request for service at later points in time with the vehicle already being on its way. The multi-objective optimization problem then results as maximizing the number of visited customers while simultaneously minimizing total travel time. As an a-posteriori evaluation tool, the evolutionary algorithm aims at approximating the related Pareto set for specifically designed benchmarking instances differing in terms of number of customers, geographical layout, fraction of mandatory customers, and request times of optional customers. Conceptional and experimental comparisons to online heuristic procedures are provided.
Keywords: combinatorial optimization; metaheuristics; multi-objective optimization; online algorithms; transportation

Towards Context-Sensitive Service Composition for Service-Oriented Image Processing - Jungmann, Alexander; Kleinjohann, Bernd (Proceedings of the 6th IEEE International Conference on Cloud Computing Technology and Science (CloudCom))
Automatically composing service-based software solutions is a challenging task. Considering context information during this service composition process is even more challenging. In domains such as image processing, however, context-sensitivity is inherent and cannot be ignored when developing techniques for automatic service composition. Formal approaches tend to create ambiguous solutions, whenever the expressive power of the applied formalism is limited. For example, services may have the same formal specification, although their actual functionality depends on the concrete context. In order to satisfy individual user requests while providing data-dependent functionality, formal approaches have to be extended. We propose to incorporate Reinforcement Learning techniques and combine them with planning based composition approaches. While planning ensures formally correct solutions, learning enables the composition process to resolve ambiguity by implicitly considering context information. Preliminary results show that our combined approach adapts to a static context while still satisfying formally specified requirements.

Incorporating Reputation Information into Decision-Making Processes in Markets of Composed Services - Jungmann, Alexander; Brangewitz, Sonja; Petrlic, Ronald; Platenius, Marie Christin (International Journal on Advances in Intelligent Systems 7(3&4))
One goal of service-oriented computing is to realize future markets of composed services. In such markets, service providers offer services that can be flexibly combined with each other. However, although crucial for decision-making, market participants are usually not able to individually estimate the quality of traded services in advance. To overcome this problem, we present a conceptual design for a reputation system that collects and processes user feedback on transactions, and provides this information as a signal for quality to participants in the market. Based on our proposed concept, we describe the incorporation of reputation information into distinct decisionmaking processes that are crucial in such service markets. In this context, we present a fuzzy service matching approach that takes reputation information into account. Furthermore, we introduce an adaptive service composition approach, and investigate the impact of exchanging immediate user feedback by reputation information. Last but not least, we describe the importance of reputation information for economic decisions of different market participants. The overall output of this paper is a comprehensive view on managing and exploiting reputation information in markets of composed services using the example of On-The-Fly Computing.

Applying Reinforcement Learning for Resolving Ambiguity in Service Composition - Jungmann, Alexander; Mohr, Felix; Kleinjohann, Bernd (Proceedings of the 7th International Conference on Service Oriented Computing and Applications (SOCA))
Automatically composing service-based software solutions is still a challenging task. Functional as well as nonfunctional properties have to be considered in order to satisfy individual user requests. Regarding non-functional properties, the composition process can be modeled as optimization problem and solved accordingly. Functional properties, in turn, can be described by means of a formal specification language. Statespace based planning approaches can then be applied to solve the underlying composition problem. However, depending on the expressiveness of the applied formalism and the completeness of the functional descriptions, formally equivalent services may still differ with respect to their implemented functionality. As a consequence, the most appropriate solution for a desired functionality can hardly be determined without considering additional information. In this paper, we demonstrate how to overcome this lack of information by means of Reinforcement Learning. In order to resolve ambiguity, we expand state-space based service composition by a recommendation mechanism that supports decision-making beyond formal specifications. The recommendation mechanism adjusts its recommendation strategy based on feedback from previous composition runs. Image processing serves as case study. Experimental results show the benefit of our proposed solution.

Fast Many-Worlds Simulation to Resolve Nondeterminism of Fault Effect Propagation - Becker, Markus; Kuznik, Christoph (Forum on Specification & Design Languages (FDL 2014))