Cologne Excellence Cluster on Cellular Stress Responses in Aging Associated Diseases
computer science publication serverNot a member yet
819 research outputs found
Sort by
Hardware-Aware Automatic Code-Transformation to Support Compilers in Exploiting the Multi-Level Parallel Potential of Modern CPUs
No full textModern compilers offer more and more capabilities to automatically parallelize code-regions if these match certain properties. However, there are several application kernels that, although rather simple transformations would suffice in order to make them match these properties, are either not at all parallelized by state-of-the-art compilers or could at least be improved w.r.t. their performance. This paper proposes a loop-tiling approach focusing on automatic vectorization and multi-core parallelization, with emphasis on a smart cache exploitation. The method is based on polyhedral code transformations that are applied as a pre-compilation step and it is shown to help compilers in generating more and better parallel code-regions. It automatically adapts to hardware parameters such as the SIMD register width and cache sizes. Further, it takes memory-access patterns into account and is capable to minimize communication among tiles that are to be processed by different cores. An extensive computational study shows significant improvements
in the number of instructions vectorized, cache miss rates, and running times for a range of application kernels. The
method often outperforms the internal auto-parallelization techniques implemented into gcc and icc
Two-Page Book Embeddings of 4-Planar Graphs
No full textBack in the eighties, Heath showed that every 3-planar graph is subhamiltonian and asked whether this result can be extended to a class of graphs of degree greater than three. In this paper we affirmatively answer this question for the class of 4-planar graphs. Our contribution consists of two algorithms: The first one is limited to triconnected graphs, but runs in linear time and uses existing methods for computing hamiltonian cycles in planar graphs. The second one, which solves the general case of the problem, is a quadratic-time algorithm based on the book embedding viewpoint of the problem
On the non-unit count of interval graphs
No full textWe introduce the non-unit count of an interval graph as the minimum number of intervals in an interval representation whose lengths deviate from one. We characterize a variant of the non-unit count (where all interval lengths are required to be at least one) and graphs with non-unit count 1
Optimal general offset assignment
No full textWe present an exact approach to the General Offset Assign-
ment problem arising in the domain of address code gen-
eration for application specific and digital signal processors.
General Offset Assignment is composed of two subproblems,
namely to find a permutation of variables in memory and to select a responsible address register for each access to one of these variables. Our method is a combination of established techniques to solve both subproblems using integer linear programming. To the best of our knowledge, it is the first approach capable of solving almost all instances of the established OffsetStone benchmark set to global optimality within reasonable time. We provide a first comprehensive evaluation of the quality of several state-of-the-art heuristics relative to the optimal solutions
Perfect Smooth Orthogonal Drawings
No full textSmooth orthogonal drawings were recently intro- duced with the view of combining two different graph drawing approaches: Orthogonal drawings and Lombardi drawings. In this paper, we focus on perfect smooth orthogonal drawings in which each edge is made of either a rectilinear segment or a circular arc. We prove that every 3-planar graph admits a planar perfect smooth orthogonal drawing. If we relax planarity constraints, we show that every graph of maximum degree 4 admits a (non-planar) perfect smooth orthogonal drawing. We demonstrate that there exist infinitely many planar graphs that do not admit planar perfect smooth orthogonal drawings under the Kandinsky model. Finally, we introduce classes of graphs admitting perfect smooth orthogonal drawings of different styles and study relations between these classes
Single-commodity robust network design problem: Complexity, instances and heuristic solutions.
No full textWe study a single-commodity Robust Network Design problem (RND) in which an undirected
graph with edge costs is given together with a discrete set of balance matrices, representing different
supply/demand scenarios. In each scenario, a subset of the nodes is exchanging flow. The goal is
to determine the minimum cost installation of capacities on the edges such that the flow exchange
is feasible for every scenario. Previously conducted computational investigations on the problem
motivated the study of the complexity of some special cases and we present complexity results on
them, including hypercubes. In turn, these results lead to the definition of new instances (random
graphs with {-1,0,1} balances) that are computationally hard for the natural flow formulation. These
instances are then solved by means of a new heuristic algorithm for RND, which consists of three
phases. In the first phase the graph representing the network is reduced by heuristically deleting
a subset of the arcs, and a feasible solution is built. The second phase consists of a neighborhood
search on the reduced graph based on a Mixed-Integer (Linear) Programming (MIP) flow model.
Finally, the third phase applies a proximity search approach to further improve the solution, taking
into account the original graph. The heuristic is tested on the new instances, and the comparison
with the solutions obtained by Cplex on a natural flow formulation shows the effectiveness of the
proposed method
Reduzieren robuste Fahrpläne Verspätungen in Stadtbahnnetzen? - Es kommt drauf an!
No full textNicht in jedem Stadtbahnnetz ist Robustheit als Optimierungskriterium für Fahrpläne gleich-sam geeignet. Im Rahmen dieses Beitrags werden deshalb Faktoren für die Netzstruktur bestimmt, die die Wirksamkeit von Robustheit als verspätungsmindernden Faktor beeinflus-sen. Anhand von Optimierungs- und Simulationsexperimenten auf Basis von Modellen der Stadtbahnnetze von Köln und Montpellier werden die definierten Einflussfaktoren getestet
Model-based parallelization of discrete traffic simulation models
No full textTo re-establish regular operations in a tram traffic network after a large disturbance, e.g. resulting from vehicle
breakdown or station closure, the viability of several rescheduling and rerouting strategies has to be evaluated
prior to their implementation. Here, a multi-modal traffic simulation system can help to enhance the
decision quality. Such a system obviously faces tight time constraints, so simulation data has to be acquired
fast.
In this paper we propose a method for the parallel execution of discrete traffic simulation models, which
would accelerate data generation in comparison to a sequential model. To assess this method's dynamic behavior
in real-world applications, some experiments conducted on a software system modeling schedule
based tram traffic are presented.
After giving an introduction to the scope and aim, we show some background on the parallelization of discrete
simulation models. The main part of the paper begins with the proposal of a method to parallelize the
execution of simulation models with problem specific properties. Some estimations of the method's efficiency
are shared, followed by several experiments to highlight its dynamic behavior in real-world applications.
The paper ends with a short summary and some thoughts on further research
Single-Commodity Robust Network Design with Finite and Hose Demand Sets
Full text linkWe study a single-commodity Robust Network Design problem (sRND) defined on an undirected graph. Our goal is to determine minimum cost capacities such that any traffic demand from a given uncertainty set can be satisfied by a feasible single-commodity flow. We consider two ways of representing the uncertainty set, either as a finite list of scenarios or as a polytope. We propose a branch-and-
cut algorithm to derive optimal solutions to sRND, built on a capacity-based integer linear programming formulation. It is strenghtened with valid inequalities derived as {0,1/2 }-Chvátal-Gomory cuts. Since the formulation contains exponentially many constraints, we provide practical separation algorithms. Extensive computational experiments show that our approach is effective, in comparison to existing approaches from the literature as well as to solving a flow based formulation by a general purpose solver