In this paper we will discuss different realizations for an efficient interval arithmetic implementation using expression templates and template meta programming in C++. We will improve the handling of the rounding mode switches using expression templates and show how the constructed expression trees can be combined with other features like automatic differentiation. For a further improvement of the run time performance we try to move as many functionality as possible to the compile time using template meta programming techniques. In addition we will illustrate how an interval arithmetic implementation will profit from new features and keywords defined in the upcoming C++ standard.

Interval arithmetic, as it is standardized by the IEEE working group P1788 can be implemented by using floating point arithmetic units with directed rounding modes. The easiest way to represent an interval is by its two bounds. Simple formulas for the arithmetic operations can be applied. Our goal is to perform interval operations as fast as their floating point counterparts. Hence, we provide at least two units per operation. We also specify the operation for reverse multiplication (Neumaier in Vienna proposal for interval standardization, 2008) which can be implemented with the division unit. In this paper we do not care about optimization. Our primary intention is to give an easily understandable specification of hardware for interval arithmetic.

In this paper we investigate how a C++ class library can be improved by the concept of expression templates. Our first result is a saving of rounding mode switches which considerably increases the performance. Our second result deals with handling the discontinuity flag that will probably be decided to be raised whenever a function is called outside its domain (loose evaluation). We discuss several alternatives and propose an expression related flag that can be used in a thread safe manner. Both results are reviewed with respect to the coming IEEE standard for interval arithmetic.

In this paper we define the interval overlapping relation and develop a parallel hardware unit for its realization. As one application we consider the interval comparisons. It is shown that a detailed classification of the interval overlapping relation leads to a reduction of floating-point comparisons in common applications.

In this paper we discuss the interaction of expression templates with OpenCL devices. We show how the expression tree of expression templates can be used to generate problem specific OpenCL kernels. In a second approach we use expression templates to optimize the data transfer between the host and the device which leads to a measurable performance increase in a domain specific language approach. We tested the functionality, correctness and performance for both implementations in a case study for vector and matrix operations.

In this paper we present a concept for a C++ implementation of forward automatic differentiation of an arbitrary order using expression templates and template meta programming. In contrast to other expression template implementations, the expression tree in our implementation has only symbolic characteristics. The run time code is then generated from the tree structure using template meta programming functions to apply the rules of symbolic differentiation onto the single operations at compile time. This generic approach has the advantage that the template meta programming functions are replaceable which offers the opportunity to easily generate different specialized algorithms. We tested the functionality, correctness and performance of a prototype in different case studies for floating point as well as interval data types and compared it against other implementations.

The interval overlapping relation defines 13 different states of the relative position of two intervals. In this paper we show that this relation can be used to define the interval comparisons and lattice operations. The shift from a boolean (binary) comparison to a comprehensive relation (13 different states) enables the user to exploit involved dependencies. We further introduce an object oriented abstract datatype to provide a userfriendly interface.

The computation of the first or higher derivatives of a function is a common problem in scientific computing. The most obvious approach to compute the derivative values is the symbolic differentiation which applies the well known rules of differentiation onto the expression to compute a formal expression of the derivative function. Another method called numerical differentiation is the approximation of the derivative with difference quotients. Superior to these approaches is the automatic differentiation which is a technique to compute a value of the expression and the derivative together by applying the well known rules of differentiation. The difference to symbolic differentiation is that it propagates numerical values instead of formal expressions. Commonly used implementations of automatic differentiation may be divided into two categories, the implementations using operator overloading to compute the values of the function and the derivative together in contrast to special tools applying the technique of source transformation to mix in the expressions to compute the derivatives. Both of these techniques are somehow inflexible in the manner that the operators are not overloaded for high order differentiation or additional tools are required for the source transformation. In this paper we use expression templates and template meta programming to mix in the code for the partial differentiation. The main concept is to apply the symbolic differentiation at compile time only onto the single operations of the expression tree to create the run time code for the automatic differentiation. This has two advantages, we can, in theory, compute derivatives of any order and secondly the differentiation of the operations is done with types. This means that the symbolic differentiation of an operation with a specified order is performed only once by the compiler. Our generic approach provides a domain specific language for partial automatic differentiation of an arbitrary order which is easily extendable by new types. Several C++ and especially C++0x template programming concepts and techniques like variadic templates, type lists or variadic tuples are used to realize the specification of the automatic differentiation at compile time. Common template meta programming techniques are refined. We tested the functionality, correctness and performance of our implementation in different case studies for floating point as well as interval data types and compared it against other implementations.

In this paper we start with the definition of the interval overlapping relation showing the 13 different cases that may occur when to compare two non-empty intervals. This paper serves 2 purposes: 1. to define a solid foundation for interval comparisons and lattice operations 2. to provide an advanced interface for language embedding and application programs.

Im Bereich des wissenschaftlichen Rechnens stößt die Intervallarithmetik in den letzten Jahren auf immer mehr Akzeptanz. Eigenschaften, wie das sichere Einschließen der Ergebnisse bei der Intervallauswertung, machen sie zu einem guten Mittel um mit den Rundungsfehlern der Gleitkommazahlen umzugehen. Auch können Berechnungen auf Wertemengen mit garantierten Grenzen durchgeführt werden. Ebenso wird in Anwendungsgebieten wie der globalen Optimierung mittels "Branch and Bound" Algorithmen, der Robotik oder der Computergraphik die Intervallrechnung mit Erfolg eingesetzt. Im Gegensatz zu der vom "Institute of Electrical and Electronics Engineers" IEEE standardisierten Gleitkommaarithmetik, existiert für die Intervallrechnung jedoch keine Norm oder Implementierungsvorschrift. Viele verschiedene Implementierungen und Konzepte wurden über die Jahre entwickelt und auch eingesetzt. Eine einheitliche Semantik wie bei den Gleitkommazahlen ist jedoch nicht gegeben. Um die Unterstützung der Intervallarithmetik auf Rechnern zu verbessern, aber auch um die Akzeptanz bei Benutzern weiter zu erhöhen wird aktuell an einem IEEE Standard für Intervallrechnung gearbeitet. Diese Diplomarbeit beschäftigt sich mit den Möglichkeiten einer effizienten Implementierung der Intervallarithmetik auf Computersystemen mittels der Programmiersprache C++.