From: Sébastien Miquée Date: Wed, 19 May 2010 12:33:21 +0000 (+0200) Subject: Creation of the publication for HeteroPar'10 X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/interreg4.git/commitdiff_plain/cd6cba274c30661ccf72fa4c75b772a34de59361?ds=inline Creation of the publication for HeteroPar'10 --- diff --git a/heteropar10/biblio.bib b/heteropar10/biblio.bib new file mode 100644 index 0000000..a2b725e --- /dev/null +++ b/heteropar10/biblio.bib @@ -0,0 +1,153 @@ +@inproceedings{minimax, + author = {S. Kumar and + S. K. Das and + R. Biswas}, + title = {Graph Partitioning for Parallel Applications in Heterogeneous + Grid Environments}, + booktitle = {IPDPS}, + year = {2002}, +} + +@inproceedings{fastmap, + author = {S. Sanyal and + A. Jain and + S. K. Das and + Rupak Biswas}, + title = {A Hierarchical and Distributed Approach for Mapping Large + Applications to Heterogeneous Grids Using Genetic Algorithms}, + booktitle = {CLUSTER}, + year = {2003}, + pages = {496-499}, +} + + +@article{metis, + author = {G. Karypis and + V. Kumar}, + title = {A Fast and High Quality Multilevel Scheme for Partioning Irregular Graphs}, + journal = {SIAM Journal on Scientific Computing}, + year = {1998}, + number = {1}, + volume = {20}, + pages = {359-392} + +} + + +@manual{chaco, + author = {B. Hendrickson and + R. W. Leland}, + title = {The Chaco User's Guide}, + organization = {Sandia National Laboratory}, + address = {Albuquerque}, + year = {1995} +} + + +@phdthesis{qm_these, + author = {P. Phinjaroenphan}, + title = {An Efficient, Pratical, Portable Mapping Technique on Computational Grids}, + school = {School of Computer Science and Information technology Science, Engineering and Technology Portfolio, RMIT University}, + year = {2006} +} + + +@inbook{cg, + AUTHOR = "J. K. Reid (Ed)", + TITLE = "On the method of conjugate gradients for the solution of large sparse systems of linear equations", + PUBLISHER = "Academic Press Inc", + PAGES = "231-254", + MONTH = "March", + YEAR = "1971" +} + + +@inbook{book_raph, + AUTHOR = "J. Bahi and S. Contassot-Vivier and R. Couturier", + TITLE = "Parallel Iterative Algorithms: from Sequential to Grid Computing", + CHAPTER = "Asynchronous Iterations", + PAGES = "124-131", + publisher = {Chapman \& Hall/CRC}, + series = {Numerical Analysis \& Scientific Computating}, + volume = 1, + year = 2007, + note = {}, +} + + +@inproceedings{jaceP2P-v2, + author = {J.-C. Charr and + R. Couturier and + D. Laiymani}, + title = {JACEP2P-V2: A Fully Decentralized and Fault Tolerant Environment + for Executing Parallel Iterative Asynchronous Applications + on Volatile Distributed Architectures}, + booktitle = {GPC}, + year = {2009}, + pages = {446-458}, +} + + +@techreport{nas, + AUTHOR = "D. Bailey and E. Barszcz and J. Barton and D. Browning and R. Carter and L. Dagun and R. Fatoohi and S. Fineberg and P. Frederickson and T. Lasinski and R. Schreiber and H. Simon and V. venkatakrishnan and S. Weeratunga", + TITLE = "The {NAS} {P}arallel {B}enchmarks", + NUMBER = "RNR-94-007", + INSTITUTION = "The Numerical Aerodynamic Simalation Program of NASA", + MONTH = "March", + YEAR = "1994" +} + + +@misc{g5k, + AUTHOR = {}, + TITLE = {Grid'5000}, + NOTE = {http://www.grid5000.fr} +} + + +@article{bcvc06:ij, + author = "J. Bahi and S. Contassot-Vivier and R. Couturier", + title = "Performance comparison of parallel programming environments + for implementing {AIAC} algorithms", + journal = "Journal of Supercomputing", + pages = "227--244", + volume = "35", + number = "3", + year = "2006" +} + + + +@inproceedings{tig1, + author = {D. L. Long and + L. A. Clarke}, + title = {Task Interaction Graphs for Concurrency Analysis}, + booktitle = {ICSE}, + year = {1989}, + pages = {44-52}, +} + + + +@inproceedings{pdsec10, +author = {R. Couturier and D. Laiymani and S. Miqu\'ee}, +title = {Mapping Asynchronous Iterative Applications on Heterogeneous Distributed Architectures}, +booktitle = {PDSEC}, +address = {Atlanta, USA}, +publisher = {{IEEE} Computer Society Press}, +year = {2010}, + +} + +@article{uncoord_cp, + author = {E. N. Elnozahy and L. Alvisi and Y. Wang and D. Johnson}, + title = {A survey of rollback-recovery protocols in message-passing systems}, + journal = {ACM Comput. Surv.}, + volume = {34}, + number = {3}, + year = {2002}, + issn = {0360-0300}, + pages = {375--408}, + publisher = {ACM}, + address = {New York, NY, USA}, + } diff --git a/heteropar10/heteropar10.pdf b/heteropar10/heteropar10.pdf new file mode 100644 index 0000000..b987afb Binary files /dev/null and b/heteropar10/heteropar10.pdf differ diff --git a/heteropar10/heteropar10.tex b/heteropar10/heteropar10.tex new file mode 100644 index 0000000..b0b366a --- /dev/null +++ b/heteropar10/heteropar10.tex @@ -0,0 +1,669 @@ +%% LNCS +\documentclass[10pt,conference]{llncs} + +\usepackage[T1]{fontenc} +\usepackage{ucs} +\usepackage[utf8x]{inputenc} +\usepackage{lmodern} +\usepackage{color} +\usepackage{amsmath} +\usepackage{amsfonts} +\usepackage[english]{babel} +\usepackage[pdftex,final]{graphicx} +\usepackage[ruled,vlined]{algorithm2e} +\usepackage[pdftex]{graphicx} +\DeclareGraphicsExtensions{.pdf,.jpeg,.png} + +\title{MAHEVE: A New Reliable AIAC Mapping Strategy for Heterogeneous + Environments \thanks{This work was supported by the European + Interreg IV From-P2P project.}} + + + +\author{Raphaël Couturier, David Laiymani and Sébastien Miquée} + \authorrunning{R. Couturier, D. Laiymani and S. Miquée} + \institute{ + University of Franche Comté \qquad LIFC laboratory\\[1mm] + IUT Belfort-Montb\'eliard, 2 Rue Engel Gros \\ BP 27 90016 Belfort, + France\\\{{\tt + raphael.couturier,david.laiymani,sebastien.miquee}\} + {\tt @univ-fcomte.fr} } + + +\date{} +\begin{document} + + +\maketitle + +\vspace{-0.2cm} + +\begin{abstract} + With the emergence of massive distributed computing resources, such + as grids and distributed clusters architectures, parallel + programming is used to benefit from them and execute problems of + larger sizes. The asynchronous iteration model, called AIAC, has + been proven to be an efficient solution for heterogeneous and + distributed architectures. An efficient mapping of applications' + tasks is essential to reduce their execution time. We present in + this paper a new mapping algorithm, called MAHEVE (Mapping Algorithm + for HEterogeneous and Volatile Environments) which is efficient on + such architectures and integrates a fault tolerance mechanism to + resist to computing nodes failures. Our experiments show gains on a + typical AIAC application's execution time about $55\%$, executed on + distributed clusters architectures containing more than 400 + computing cores with the JaceP2P-V2 environment. + +%\textup{\small \textbf{Keywords:} Mapping algorithm, Fault tolerance, +% Distributed clusters, Parallel iterative asynchronous algorithms, +% Heterogeneous architectures.} +\end{abstract} + +\section{Introduction} +\label{sec:intro} + +Nowadays, scientific applications require a great computation power to +solve their large problems. Though personal computers are more +powerful, in many cases they are not sufficient. One well adapted +solution is to use computers clusters in order to combine the power of +many machines. Distributed clusters form such an architecture, +providing a great computing power, by aggregating the computation +power of multiple clusters spread over multiple sites. Such an +architecture brings users heterogeneity in computing machines as well +as network latency. In order to use such an architecture, parallel +programming is required. In the parallel computing area, in order to +execute very large applications on heterogeneous architectures, +iterative methods are well adapted\cite{book_raph}. + + +These methods repeat the same instructions block until a convergence +state and a desired approximation of the solution are reached. They +constitute the only known approach to solving some kinds of problems +and are relatively easy to parallelize. The Jacobi or Conjugate +Gradient\cite{cg} methods are examples of such methods. + + +To parallelize this kind of algorithm, one of the most used methods is +the message passing paradigm which allows an efficient mechanism to +exchange data between tasks. As such a method, we focus here on the +asynchronous parallel iterative model, called AIAC\cite{book_raph} +(for \textit{Asynchronous Iteration and Asynchronous Communication}). + +\begin{figure}[h!] + \vspace{-0.4cm} + \centering + \includegraphics[width=7.4cm]{images/IACA} + \caption{Two processors computing in the Asynchronous Iteration - Asynchronous Communication (AIAC) model} + \label{fig:AIAC} + \vspace{-0.90cm} +\end{figure} + + +In this model, as can be seen on Figure \ref{fig:AIAC}, after each +iteration, a task sends its results to its neighbors and immediately +starts the next iteration with the last received data. The receiving +and sending mechanisms are asynchronous and tasks do not have to wait +for the reception of dependency messages from their +neighbors. Consequently, there is no idle time between two +iterations. Furthermore, this model is tolerant to messages loss and +even if a task is stopped the remaining tasks continue the +computation, with the last available data. Several +experiments\cite{bcvc06:ij} show the relevance of the AIAC algorithms +in the context of distributed clusters with high latency between +clusters. These works underline the good adaptability of AIAC +algorithms to network and processor heterogeneity. + + +In a previous study\cite{pdsec10} we proposed two static mapping +algorithms of tasks to processors dedicated to the AIAC model on +heterogeneous distributed clusters. Both these two algorithms, +AIAC-QM (for \textit{AIAC Quick-quality Map}) and F-EC (for +\textit{Farhat Edges-Cuts}) showed an important performances +improvement by reducing up to $50\%$ the application's execution +time. These experiments were performed by using the JaceP2P-V2 +environment. This Java based platform is an executing and developing +environment dedicated to the AIAC model. By implementing a distributed +backup/restore mechanism it is also fully fault +tolerant\cite{jaceP2P-v2}. In our previous experiments we did not +introduce computing nodes failures during the computation. And as +architecture's heterogeneity continually evolves according to +computing nodes volatility, we have to more precisely takes care about +the heterogeneity of the target platform. Thus in this paper our main +contribution is to propose a new mapping algorithm called MAHEVE +(\textit{Mapping Algorithm for HEterogeneous and Volatile + Environments}). This algorithm explicitly tackles the heterogeneity +issue and introduces a level of dynamism in order to adapt itself to +the fault tolerance mechanisms. Our experiments show gains about 55\% +on application's execution time, with about 10 points better than +AIAC-QM and about 25 points better than F-EC. + + +The rest of this paper is organized as +follows. Section~\ref{sec:jacep2p} reminds the JaceP2P-V2 middleware +by describing its architecture and briefly presenting its fault +tolerance mechanism. Section~\ref{sec:pb} formalizes our mapping and +fault tolerance problems and quotes existing issues to address +them. Section~\ref{sec:maheve} describes the new mapping strategy we +propose, MAHEVE. In section~\ref{sec:expe} we present the experiments +we have conducted on the Grid'5000 testbed with more than 400 +computing cores. Finally, we give some concluding remarks and plan our +future work in section~\ref{sec:conclu}. + + +\section{JaceP2P-V2} +\label{sec:jacep2p} + +JaceP2P-V2\cite{jaceP2P-v2} is a distributed platform implemented in +Java, dedicated to developing and executing parallel iterative +asynchronous applications. It is fully fault tolerant allowing it to +execute parallel applications over volatile environments. To our +knowledge this is the only platform dedicated to designing and +executing AIAC algorithms in such volatile environments. + + +The JaceP2P-V2 platform part, which is based on the daemons and +supervisors paradigm, is composed of three main entities: + +\begin{itemize} +\item The ``super-nodes'', which is in charge of supervising free + computing nodes connected to the platform. + +\item The ``spawner'', which is launched by a user wanting to execute + a parallel application. It is in charge of a group of computing + nodes and monitor them. If one of them fails, it requires a + replacing one to a super-node. + +\item The ``daemon'', when launched, connects to a super-node and + waits for a task to execute. Each daemon can communicate directly + with its computing neighbors. + +\end{itemize} + + +To be able to execute asynchronous iterative applications, JaceP2P-V2 +has an asynchronous messaging mechanism. In order to resist daemons' +failures, it implements a distributed backup mechanism called the +\textit{uncoordinated distributed checkpointing}\cite{uncoord_cp}. +This decentralized procedure allows the platform to be very scalable, +with no weak points and does not require a secure nor a stable station +for backups. When a daemon dies, it is replaced by another one. Here +we suppose that we have enough available free nodes. Moreover, to +resit to supervisors failures and to be scalable, it reserves some +extra nodes. For more details on the JaceP2P-V2 platform, interested +readers can refer to \cite{jaceP2P-v2}. + + +\section{Mapping and fault tolerance problems} +\label{sec:pb} + +\subsection{Model formalization} +\label{sec:pbmodel} + +\subsubsection{Application modeling} +\label{sec:pbmodelapp} + + +With the AIAC model, all tasks compute in parallel at the same time, +without precedence nor synchronization. During an iteration, each task +computes its job and sends its results to its neighbors, and +immediately starts the next iteration. The TIG\cite{tig1} +(\textit{Task Interaction Graph}) is the most appropriate model to our +problem, as it only models relationships between tasks. In this model, +all the tasks are considered simultaneously executable and +communications can take place at any time during the computation, with +no precedence nor synchronization. + + +In the TIG model, a parallel application is represented by a graph +$GT(V,E)$, where \mbox{$V = \{V_1,V_2,\dots V_v\}$} is the set of +$|V|$ vertices and \mbox{$E \subset V \times V$} is the set of +undirectional edges. The vertices represent tasks and the edges +represent the mutual communication among tasks. A function \mbox{$EC : + V \rightarrow \mathbb{R}^+$} gives the computation cost of tasks and +\mbox{$CC : E \rightarrow \mathbb{R}^+$} gives the communication cost +for message passing on edges. We define \mbox{$|V| = v$, $EC(V_i) = + e_i$} and \mbox{$CC(V_i,V_j) = c_{ij}$}. Another function +\mbox{$D : V \rightarrow \mathbb{R}^+$} gives the amount of +dependencies of a task, and we define \mbox{$D(V_i) = d_i$}. + + +\subsubsection{Architecture modeling} +\label{sec:pbmodelarchi} + + +A distributed clusters architecture can be modeled by a +three-level-graph. The levels are \textit{architecture} (a) (here the +Grid'5000 grid), \textit{cluster} (c), and \textit{computing node} (n) +levels. Let $GG(N,L)$ be a graph representing a distributed clusters +architecture, where \mbox{$N = \{N_1,N_2,\dots N_n\}$} is the set of +$|N|$ vertices and $L$ is the set of $|L|$ undirectional edges. The +vertices represent the computing nodes and the edges represent the +links between them. An edge \mbox{$L_i \in L$} is an unordered pair +\mbox{$(N_x,N_y) \in \mathbb{N}$}, representing a communication link +between nodes $N_x$ and $N_y$. A function \mbox{$WN : N \rightarrow + \mathbb{R}^+$} gives the computational power of nodes and another +function \mbox{$WL : L \rightarrow \mathbb{R}^+$} gives the +communication latency of links. We define \mbox{$WN(N_i) = wn_i$} and +\mbox{$WL(L_i,L_j) = wl_{ij}$}. Let be $|C|$ the number of clusters +contained in the architecture. A function \mbox{$CN : C \rightarrow + \mathbb{N}^+$} gives the amount of computing nodes contained in a +cluster, and another function \mbox{$CF : C \rightarrow \mathbb{R}^+$} +gives the amount of available computing nodes (not involve in an +application computation) of a cluster. We define \mbox{$CN(C_i) = + C_{Ni}$} and \mbox{$CF(C_i) = C_{Fi}$}. We also define \mbox{$C_{Pi} + = \sum_{j=1}^{C_{Ni}}{wn_j}$} as the whole computation power of +cluster $C_i$ and \mbox{$C_{\overline{P}i} = \frac{C_{Pi}}{C_{Ni}}$} +as the average computation power of cluster $C_i$, and +$C_{\overline{P}fi}$ the average power of its available resources. + +We evaluate the \textit{heterogeneity degree} of the architecture, +noted $hd$, by using the \textit{relative standard deviation} method, +with $hd = \frac{\sigma_{PN}}{avg_{PN}}$ where $avg_{PN}$ is the +average computing power of nodes and $\sigma_{PN}$ represents the +standard deviation of computing nodes power. This measure provides us +the coefficient of variation of the platform in percentage -- we only +consider \mbox{$0 \leq hd \leq 1$} as considering values of \mbox{$hd + > 1$} is not relevant, as \mbox{$hd = 1$} denotes a fully +heterogeneous platform. + + +\subsubsection{Mapping functions} +\label{sec:pbmodelmapping} + + +When a parallel application $App$, represented by a graph $GT$, is +mapped on a distributed clusters architecture, represented by a graph +$GG$, the execution time of the application, $ET(App)$, can be defined +as the execution time of the slowest task. Indeed, an application ends +when all the tasks have detected convergence and reached the desired +approximation of the solution. We define $ET(App) = \max_{i=1 \dots + v} ( ET(V_i) )$ where the execution time of each task $i$ +\mbox{($i=1 \dots v$)}, $ET(V_i)$ is given by $ET(V_i) = +\frac{e_i}{wn_i} + \sum_{j \in J} c_{ij} \times wl_{ij}$ where $e_i$ +is the computational cost of $V_i$, $wn_i$ is the computational power +of the node $N_i$ on which $V_i$ is mapped, $J$ represents the +neighbors set of $V_i$, $c_{ij}$ is the amount of communications +between $V_i$ and $V_j$, and $wl_{ij}$ is the link latency between the +computing nodes on which are mapped $V_i$ and $V_j$. As described in +this formula, the execution time of a task depends on the task weight +and communications it may occur with its neighbors. We underline here +that in the AIAC model, it is impossible to predict the number of +iterations of a task. So it is difficult to evaluate a priori its cost +$e_i$. + +This tasks mapping problem is similar to the classical graph +partitioning and task assignment problem, and is thus NP-complete. + + +\subsection{Fault tolerance} +\label{sec:pbft} + +In volatile environments, computing nodes can disconnect at any time +during the computation, and these ones have to efficiently be replaced. + + +The replacing nodes should be the best ones at the fault time, +according to the chosen mapping algorithm, by searching them in +available nodes. As executing environments can regularly evolve, due +to computing nodes' volatility, a mapping algorithm has to keep a +right overview of the architecture, in real time. Thus, criteria to +assign tasks to nodes should evolve too. + + +Another problem appears after multiple crashes: some tasks may have +migrated over multiple computing nodes and clusters, and the initial +mapping may be totally changed. So, after having suffered some nodes +failures the tasks mapping could not always satisfy the mapping +criteria (not on the more powerful available machine, too far away +from its neighbors\dots{}). A good fault tolerance policy has to +evolve dynamically with the executing +environment. + + +\subsection{Specificities of the AIAC mapping problem} +\label{sec:specAIACmapping} + +An important point to take into consideration is that we do not allow +the execution of multiple tasks on the same computing node, as this +provides a fall of performance when this one fails. Indeed we should +redeploy all of the tasks from this node to another one, using last +saves, which can be spread on multiple computing nodes. This may +result in large communication overheads and a waste of computation +time. Nevertheless, to benefit of multi-cores processors, we use a +task level parallelism by running multi-threaded sequential solver for +example. + + +Another important point in the AIAC model is that as the JaceP2P-V2 +environment is fault tolerant and tasks save checkpoints on their +neighbors, it is more efficient to save on near nodes than on far ones +in order to reduce the communication overhead during this operation, +and to faster restart a task. + + +\subsection{Related work} +\label{sec:pbrw} + +In the literature of the TIG mapping many algorithms exist, which can +be broadly classified into two categories. The first one is the +\textit{Edge-cuts optimization} class, which minimizes the use of the +penalizing links between clusters. As tasks are depending on +neighbors, which are called dependencies, the goal is to choose nodes +where distance, in term of network, is small to improve communications +between tasks. Here we can cite Metis\cite{metis} and +Chaco\cite{chaco} which are libraries containing such kind of +algorithms. The second category is the \textit{Execution time + optimization} class, which aims to minimize the whole application's +execution time. These algorithms look for nodes which can provide the +smallest execution time of tasks using their computational power. Here +we can cite QM\cite{qm_these}, FastMap\cite{fastmap}, and +MiniMax\cite{minimax} as such kind of algorithms. + + +Both classes of algorithms may fit with our goals as in our model we +have both the computational power of nodes and communication costs +which may influence the applications performances. + + +All mentioned algorithms do not tackle the computing nodes failures +issue, or basically by applying the same policy. As explain in section +\ref{sec:pbft}, a more efficient and dedicated replacement function is +needed. Nevertheless, to the best of our knowledge, no tasks mapping +algorithm, addressing explicitly both the executing platform +heterogeneity and the computing nodes failures issues, exists. + + +\vspace{-0.25cm} +\section{MAHEVE} +\label{sec:maheve} + +Here we present our new tasks mapping strategy, called MAHEVE (for +\textit{Mapping Algorithm for HEterogeneous and Volatile + Environments}). This algorithm aims to take the best part of each +category mentioned in section \ref{sec:pbrw}, the edge-cuts +minimization and the application's execution time optimization +algorithms. + + +This new algorithm can be divided into two parts. The first part aims +to perform the initial mapping, and the second part is devoted to +search replacing nodes when computing nodes' failures occur. + + +\vspace{-0.20cm} +\subsection{Initial mapping} +\label{sec:maheve_init} + +In this section we will study the main mechanisms of the +\textit{static mapping} done by MAHEVE, which is composed of three +phases: sort of clusters, sort of tasks, and the effective mapping, +which maps tasks (in their sort order) on nodes of clusters (also in +their sort order) with a reservation of some nodes in each cluster. + + +\vspace{-0.15cm} +\subsubsection{Sorting clusters} +\label{sec:maheve_sort_clusters} + +The first step of the initial mapping is to sort clusters accordingly +to the executing platform's heterogeneity degree $hd$. The main +principles are that a cluster obtain a better mark when $hd < 0.5$ and +it contains more computing nodes than other clusters ($C_{Fi}$, the +amount of available free nodes, is privileged), and when $hd \ge 0.5$ +and it contains more powerful computing nodes ($C_{\overline{P}fi}$, +the average computation power, is privileged). These choices come from +several experiments with the AIAC model, which show that in such +environments it is more efficient to privilege the computation power +or the amount of nodes. As the amount of nodes, $C_{Fi}$, and the +average computing power, $C_{\overline{P}fi}$, are not in the order of +magnitude, we normalize them with two functions, $normN$ and +$normP$. They are defined as \mbox{$normN\left(C_{Fi}\right) = C_{Fi} + \times 100 \div \sum_{j=1}^{|C|}C_{Fj}$}, which is the rate (in +percent) of computing nodes, and \mbox{$normP(C_{\overline{P}fi}) = + C_{\overline{P}fi} \times 100 \div \sum_{j=1}^{|C|} + C_{\overline{P}fj}$}, which is the rate (in percent) of the average +power, both representing the cluster in the architecture. We note +$NC_{Fi} = normN\left( C_{Fi} \right)$ and $NC_{\overline{P}fi} = +normP(C_{\overline{P}fi})$. + + +The formula used to give a mark, $M_i$, to a cluster is +\begin{equation} + \label{eq:cluster} + M_i = {NC_{\overline{P}fi}}^{hd} + {NC_{Fi}}^{1 - hd}. +\end{equation} + + +This compromise function allows us to privilege clusters following our +criteria, as explained previously, according to the heterogeneity +degree. If we study its limits for the $hd$'s extremities, $hd = 0$ +and $hd = 1$, we obtain $\lim_{hd \rightarrow 0} M_i = NC_{Fi}$ and +$\lim_{hd \rightarrow 1} M_i = NC_{\overline{P}fi}$, which fit with +our objectives. + +Clusters are so sorted and placed in a list containing them, starting +from the cluster which receives the better mark to the one which +receives the lower mark. + + +\subsubsection{Sorting tasks} +\label{sec:maheve_sort_tasks} + +Like clusters, tasks are also sorted accordingly to the heterogeneity +degree of the executing platform. This sort is done in the same way as +previously, as when $hd < 0.5$ tasks with higher dependencies will be +privileged, and when $hd \ge 0.5$ tasks with higher computing cost are +privileged, in order to be executed on highest powered computing +nodes. + + +The main function used to classified tasks is +\begin{equation} + \label{eq:tasks} + Q_i = e_i^{hd} \times d_i^{1 - hd} +\end{equation} + +where $Q_i$ is the evaluation of the task $i$ according to the +heterogeneity degree $hd$ and $d_i$, the amount of dependencies of +task $i$. + + +Tasks are taken in the order of the first sort, determined with +equation (\ref{eq:tasks}), and each task is placed in a new list (the +final one) and some of its dependencies are added. We note $Nb_i = +d_i^{1 - hd}$ this amount of dependencies as the lower the +heterogeneity degree is the higher this number will be. This final +operation allows to control the necessary locality of tasks according +to the heterogeneity degree of the platform. + + +\subsubsection{Mapping method} +\label{sec:maheve_mapping_method} + +The third step of the initial mapping is to allocate tasks to +computing nodes. As clusters and tasks have been sorted accordingly to +the executing platform's heterogeneity degree, ordered from the +highest mark to the lower, this function maps tasks on each available +computing nodes of clusters, in their respective order in lists (for +example task classified first in the tasks list is mapped on an +available node of the cluster classified first in clusters list). + +The idea here is not to fulfill each cluster, but preserve some +computing nodes in each cluster. These conserved nodes will be used to +replace failed nodes. The fact of considering in the initial mapping +the fault tolerance is a new approach in mapping algorithms. + + +\subsection{Replacing function} +\label{sec:maheve_rep} + +This function is essential in a volatile environment, as an efficient +replacement should reduce the overhead on the application execution +time due to the loss of computing steps and data. + +As we have shown in the previous section, during the initial mapping +some computing nodes in each cluster have been preserved for fault +tolerance. When a node fails this function replace it by a free node +of the same cluster. If none is available this function sorts again +clusters, to take into consideration platform's modifications, and +replace the failed node by one available in the new sorted clusters +list. This mechanism allows to keep tasks' locality and a real time +overview of the executing platform. + + +\section{Experimentation} +\label{sec:expe} + +\subsection{A typical AIAC application and the execution platform} +\label{sec:cond} + +We used the ``Kernel CG'' application of the NAS Parallel Benchmarks +(NPB) \cite{nas} to evaluate the performances of our new mapping +algorithm. This benchmark is designed to be used on large +architectures, because it stresses communications over latency +networks, by processing unstructured matrix vector multiplication with +a Conjugate Gradient method. As this method cannot be executed with +the asynchronous iteration model we have replaced it by another method +called the multisplitting method. This latter supports the +asynchronous iterative model. For more details about this method, +interested readers are invited to see \cite{book_raph}. The chosen +problem used a matrix of size $5,000,000$ with a low bandwidth, fixed +to $35,000$. This bandwidth size generates, according to the problem's +size, between 8 and 20 neighbors per tasks. This application was +executed on 64 computing nodes. + + +The platform used for our tests, called Grid’5000\cite{g5k}, is a +French nationwide experimental set of clusters which provides us +distributed clusters architectures (28 heterogeneous clusters spread +over 9 sites). We used three distributed clusters architectures on +the Grid'5000 testbed, each having a different heterogeneity +degree. The first one was composed of four clusters spread over four +sites, with a total of 106 computing nodes representing 424 computing +cores with \mbox{$hd = 0.08$}; the second one was composed of four +clusters spread over three sites, with a total of 110 computing nodes +representing 440 computing cores with \mbox{$hd = 0.50$}; and finally +the third one was composed of five clusters spread over four sites +with 115 computing nodes representing 620 computing cores with +\mbox{$hd = 0.72$}. + + +All computing nodes of these clusters have at least 4 computing cores +(in the last used architecture, with \mbox{$hd = 0.72$}, two clusters +are composed of 8 computing cores machines) with a minimum of 4GB of +memory (in order to execute the application with a big problem's +size). All computing nodes can communicate with each other through an +efficient network. Nevertheless, this latter is shared with many other +users so high latencies appear during executions. + + +\subsection{Experiments} +\label{sec:experiments} + +During executions, we introduced two failures in computing nodes +involved in the computation every 20 seconds to simulate a volatile +environment. Unfortunately, we had not the opportunity to realize +experiments with more computing nodes over more sites with problems of +larger sizes, but we plan to extend our experiments in the future. + + +Here we present the results of the evaluation of the MAHEVE algorithm, +compared with FT-AIAC-QM (for \textit{Fault Tolerant AIAC-QM}) and +FT-FEC (for \textit{Fault Tolerant F-EC}) which are respectively the +fault tolerant versions of the AIAC-QM and F-EC mapping algorithms +presented in \cite{pdsec10}. Table \ref{tab:results} shows the +execution times of each mapping algorithm compared to the default +mapping strategy of the JaceP2P-V2 platform, with the corresponding +gains on application's execution time, in brackets. + +\renewcommand{\arraystretch}{1.7} +\begin{table}[h!] + \centering + \begin{tabular}{|c|c|c|c|c|} + \hline + ~$ hd$~ & ~Default~ & ~FT-AIAC-QM~ & ~FT-FEC~ & ~MAHEVE~ \\ + \hline + ~$0.08$~&229s&178s (22\%)&154s (33\%)&113s (50\%)\\ + ~$0.50$~&242s&118s (51\%)&133s (45\%)&85s (65\%)\\ + ~$0.72$~&192s&99s (45\%)&121s (33\%)&86s (53\%)\\ + \hline + \end{tabular} + \vspace{0.15cm} + \caption{Application's execution time in seconds and corresponding gains on various + platforms using different mapping algorithms with 2 computing + nodes' failures each 20 seconds} + \label{tab:results} + \vspace{-0.7cm} +\end{table} + + +First of all, we can note that all mapping algorithms provide an +enhancement of the application's performances by considerably reducing +its execution time, with an average gain about $45\%$ in general in +comparison to the default policy. As shown in \cite{pdsec10}, FT-FEC +is efficient on architectures with a low heterogeneity degree +(\mbox{$hd = 0.08$} by providing gains about $33\%$, and gains are +seemly the same on heterogeneous architectures (\mbox{$hd = + 0.72$}). FT-AIAC-QM is efficient on architectures with a high +heterogeneity degree (\mbox{$hd = 0.72$}) by providing gains about +$45\%$, whereas it is not so efficient on homogeneous architectures +(\mbox{$hd = 0.08$}) by providing gains about $22\%$. We can note here +that on an architecture with a heterogeneity degree of $0.50$ +FT-AIAC-QM is more efficient than FT-FEC by providing gains up to +$50\%$. + +Now if we look at the performances of our new solution, MAHEVE, we can +see that it is all the time better than other algorithms. As can be +seen in \mbox{Table \ref{tab:results}}, it reduces the application's +execution time by about $50\%$ on homogeneous architectures (here of +$0.08$ heterogeneity degree) what is more than 25 point better than +FT-FEC and near 30 points better than FT-AIAC-QM. On heterogeneous +architectures (here of $0.72$ heterogeneity degree) it also +outperforms other mapping algorithms by reducing the application's +execution time by about $53\%$ what is near about 10 points better +than FT-AIAC-QM and 20 points better than FT-FEC. On middle +heterogeneity degree architectures (here of $0.50$ heterogeneity +degree), MAHEVE is another one time better than its two comparative +mapping algorithms by reducing the application's execution time by +about $53\%$. These good performances come from the fact that it is +designed to be efficient on both architectures, homogeneous and +heterogeneous. Moreover, as it integrates a fault tolerance +\textit{security} in the initial mapping, it is more efficient when +computing nodes fail. Here we can point out that this algorithm allows +in general gains on application's execution time about $55\%$. + + +\section{Conclusion and future works} +\label{sec:conclu} + +In this paper we have presented a novel mapping algorithm, called +MAHEVE, to address the AIAC mapping issue on heterogeneous and +volatile environments. It aims to do an efficient mapping of tasks on +distributed clusters architectures by taking the best part of the two +known approaches, application's execution time optimization and +edge-cuts minimization. Experiments show that it is the most efficient +mapping algorithm on all kinds of architectures, as it takes care +about their heterogeneity degree and adapt its sort methods to it. We +have shown that it is all the time better than the two other +comparative mapping algorithms, FT-AIAC-QM and FT-FEC. This can be +explained by the fact that it not only takes care about computing +nodes and clusters, but also about the tasks' properties, what refines +the mapping solution. + +In our future works we plan to enhance the MAHEVE algorithm +performances by modifying the notation of clusters as their locality +is now not taken into consideration, in order to favor tasks locality, +which will reduce communications delays providing a better convergence +rate. + + +%%% + + +\bibliographystyle{unsrt} + +\bibliography{biblio} + + +\end{document} + diff --git a/heteropar10/images/IACA.pdf b/heteropar10/images/IACA.pdf new file mode 100755 index 0000000..718aaa2 Binary files /dev/null and b/heteropar10/images/IACA.pdf differ diff --git a/heteropar10/llncs.cls b/heteropar10/llncs.cls new file mode 100644 index 0000000..1ee2791 --- /dev/null +++ b/heteropar10/llncs.cls @@ -0,0 +1,1206 @@ +% LLNCS DOCUMENT CLASS -- version 2.16 (15-Apr-2010) +% Springer Verlag LaTeX2e support for Lecture Notes in Computer Science +% +%% +%% \CharacterTable +%% {Upper-case \A\B\C\D\E\F\G\H\I\J\K\L\M\N\O\P\Q\R\S\T\U\V\W\X\Y\Z +%% Lower-case \a\b\c\d\e\f\g\h\i\j\k\l\m\n\o\p\q\r\s\t\u\v\w\x\y\z +%% Digits \0\1\2\3\4\5\6\7\8\9 +%% Exclamation \! Double quote \" Hash (number) \# +%% Dollar \$ Percent \% Ampersand \& +%% Acute accent \' Left paren \( Right paren \) +%% Asterisk \* Plus \+ Comma \, +%% Minus \- Point \. Solidus \/ +%% Colon \: Semicolon \; Less than \< +%% Equals \= Greater than \> Question mark \? +%% Commercial at \@ Left bracket \[ Backslash \\ +%% Right bracket \] Circumflex \^ Underscore \_ +%% Grave accent \` Left brace \{ Vertical bar \| +%% Right brace \} Tilde \~} +%% +\NeedsTeXFormat{LaTeX2e}[1995/12/01] +\ProvidesClass{llncs}[2010/04/15 v2.16 +^^J LaTeX document class for Lecture Notes in Computer Science] +% Options +\let\if@envcntreset\iffalse +\DeclareOption{envcountreset}{\let\if@envcntreset\iftrue} +\DeclareOption{citeauthoryear}{\let\citeauthoryear=Y} +\DeclareOption{oribibl}{\let\oribibl=Y} +\let\if@custvec\iftrue +\DeclareOption{orivec}{\let\if@custvec\iffalse} +\let\if@envcntsame\iffalse +\DeclareOption{envcountsame}{\let\if@envcntsame\iftrue} +\let\if@envcntsect\iffalse +\DeclareOption{envcountsect}{\let\if@envcntsect\iftrue} +\let\if@runhead\iffalse +\DeclareOption{runningheads}{\let\if@runhead\iftrue} + +\let\if@openbib\iffalse +\DeclareOption{openbib}{\let\if@openbib\iftrue} + +% languages +\let\switcht@@therlang\relax +\def\ds@deutsch{\def\switcht@@therlang{\switcht@deutsch}} +\def\ds@francais{\def\switcht@@therlang{\switcht@francais}} + +\DeclareOption*{\PassOptionsToClass{\CurrentOption}{article}} + +\ProcessOptions + +\LoadClass[twoside]{article} +\RequirePackage{multicol} % needed for the list of participants, index +\RequirePackage{aliascnt} + +\setlength{\textwidth}{12.2cm} +\setlength{\textheight}{19.3cm} +\renewcommand\@pnumwidth{2em} +\renewcommand\@tocrmarg{3.5em} +% +\def\@dottedtocline#1#2#3#4#5{% + \ifnum #1>\c@tocdepth \else + \vskip \z@ \@plus.2\p@ + {\leftskip #2\relax \rightskip \@tocrmarg \advance\rightskip by 0pt plus 2cm + \parfillskip -\rightskip \pretolerance=10000 + \parindent #2\relax\@afterindenttrue + \interlinepenalty\@M + \leavevmode + \@tempdima #3\relax + \advance\leftskip \@tempdima \null\nobreak\hskip -\leftskip + {#4}\nobreak + \leaders\hbox{$\m@th + \mkern \@dotsep mu\hbox{.}\mkern \@dotsep + mu$}\hfill + \nobreak + \hb@xt@\@pnumwidth{\hfil\normalfont \normalcolor #5}% + \par}% + \fi} +% +\def\switcht@albion{% +\def\abstractname{Abstract.} +\def\ackname{Acknowledgement.} +\def\andname{and} +\def\lastandname{\unskip, and} +\def\appendixname{Appendix} +\def\chaptername{Chapter} +\def\claimname{Claim} +\def\conjecturename{Conjecture} +\def\contentsname{Table of Contents} +\def\corollaryname{Corollary} +\def\definitionname{Definition} +\def\examplename{Example} +\def\exercisename{Exercise} +\def\figurename{Fig.} +\def\keywordname{{\bf Keywords:}} +\def\indexname{Index} +\def\lemmaname{Lemma} +\def\contriblistname{List of Contributors} +\def\listfigurename{List of Figures} +\def\listtablename{List of Tables} +\def\mailname{{\it Correspondence to\/}:} +\def\noteaddname{Note added in proof} +\def\notename{Note} +\def\partname{Part} +\def\problemname{Problem} +\def\proofname{Proof} +\def\propertyname{Property} +\def\propositionname{Proposition} +\def\questionname{Question} +\def\remarkname{Remark} +\def\seename{see} +\def\solutionname{Solution} +\def\subclassname{{\it Subject Classifications\/}:} +\def\tablename{Table} +\def\theoremname{Theorem}} +\switcht@albion +% Names of theorem like environments are already defined +% but must be translated if another language is chosen +% +% French section +\def\switcht@francais{%\typeout{On parle francais.}% + \def\abstractname{R\'esum\'e.}% + \def\ackname{Remerciements.}% + \def\andname{et}% + \def\lastandname{ et}% + \def\appendixname{Appendice} + \def\chaptername{Chapitre}% + \def\claimname{Pr\'etention}% + \def\conjecturename{Hypoth\`ese}% + \def\contentsname{Table des mati\`eres}% + \def\corollaryname{Corollaire}% + \def\definitionname{D\'efinition}% + \def\examplename{Exemple}% + \def\exercisename{Exercice}% + \def\figurename{Fig.}% + \def\keywordname{{\bf Mots-cl\'e:}} + \def\indexname{Index} + \def\lemmaname{Lemme}% + \def\contriblistname{Liste des contributeurs} + \def\listfigurename{Liste des figures}% + \def\listtablename{Liste des tables}% + \def\mailname{{\it Correspondence to\/}:} + \def\noteaddname{Note ajout\'ee \`a l'\'epreuve}% + \def\notename{Remarque}% + \def\partname{Partie}% + \def\problemname{Probl\`eme}% + \def\proofname{Preuve}% + \def\propertyname{Caract\'eristique}% +%\def\propositionname{Proposition}% + \def\questionname{Question}% + \def\remarkname{Remarque}% + \def\seename{voir} + \def\solutionname{Solution}% + \def\subclassname{{\it Subject Classifications\/}:} + \def\tablename{Tableau}% + \def\theoremname{Th\'eor\`eme}% +} +% +% German section +\def\switcht@deutsch{%\typeout{Man spricht deutsch.}% + \def\abstractname{Zusammenfassung.}% + \def\ackname{Danksagung.}% + \def\andname{und}% + \def\lastandname{ und}% + \def\appendixname{Anhang}% + \def\chaptername{Kapitel}% + \def\claimname{Behauptung}% + \def\conjecturename{Hypothese}% + \def\contentsname{Inhaltsverzeichnis}% + \def\corollaryname{Korollar}% +%\def\definitionname{Definition}% + \def\examplename{Beispiel}% + \def\exercisename{\"Ubung}% + \def\figurename{Abb.}% + \def\keywordname{{\bf Schl\"usselw\"orter:}} + \def\indexname{Index} +%\def\lemmaname{Lemma}% + \def\contriblistname{Mitarbeiter} + \def\listfigurename{Abbildungsverzeichnis}% + \def\listtablename{Tabellenverzeichnis}% + \def\mailname{{\it Correspondence to\/}:} + \def\noteaddname{Nachtrag}% + \def\notename{Anmerkung}% + \def\partname{Teil}% +%\def\problemname{Problem}% + \def\proofname{Beweis}% + \def\propertyname{Eigenschaft}% +%\def\propositionname{Proposition}% + \def\questionname{Frage}% + \def\remarkname{Anmerkung}% + \def\seename{siehe} + \def\solutionname{L\"osung}% + \def\subclassname{{\it Subject Classifications\/}:} + \def\tablename{Tabelle}% +%\def\theoremname{Theorem}% +} + +% Ragged bottom for the actual page +\def\thisbottomragged{\def\@textbottom{\vskip\z@ plus.0001fil +\global\let\@textbottom\relax}} + +\renewcommand\small{% + \@setfontsize\small\@ixpt{11}% + \abovedisplayskip 8.5\p@ \@plus3\p@ \@minus4\p@ + \abovedisplayshortskip \z@ \@plus2\p@ + \belowdisplayshortskip 4\p@ \@plus2\p@ \@minus2\p@ + \def\@listi{\leftmargin\leftmargini + \parsep 0\p@ \@plus1\p@ \@minus\p@ + \topsep 8\p@ \@plus2\p@ \@minus4\p@ + \itemsep0\p@}% + \belowdisplayskip \abovedisplayskip +} + +\frenchspacing +\widowpenalty=10000 +\clubpenalty=10000 + +\setlength\oddsidemargin {63\p@} +\setlength\evensidemargin {63\p@} +\setlength\marginparwidth {90\p@} + +\setlength\headsep {16\p@} + +\setlength\footnotesep{7.7\p@} +\setlength\textfloatsep{8mm\@plus 2\p@ \@minus 4\p@} +\setlength\intextsep {8mm\@plus 2\p@ \@minus 2\p@} + +\setcounter{secnumdepth}{2} + +\newcounter {chapter} +\renewcommand\thechapter {\@arabic\c@chapter} + +\newif\if@mainmatter \@mainmattertrue +\newcommand\frontmatter{\cleardoublepage + \@mainmatterfalse\pagenumbering{Roman}} +\newcommand\mainmatter{\cleardoublepage + \@mainmattertrue\pagenumbering{arabic}} +\newcommand\backmatter{\if@openright\cleardoublepage\else\clearpage\fi + \@mainmatterfalse} + +\renewcommand\part{\cleardoublepage + \thispagestyle{empty}% + \if@twocolumn + \onecolumn + \@tempswatrue + \else + \@tempswafalse + \fi + \null\vfil + \secdef\@part\@spart} + +\def\@part[#1]#2{% + \ifnum \c@secnumdepth >-2\relax + \refstepcounter{part}% + \addcontentsline{toc}{part}{\thepart\hspace{1em}#1}% + \else + \addcontentsline{toc}{part}{#1}% + \fi + \markboth{}{}% + {\centering + \interlinepenalty \@M + \normalfont + \ifnum \c@secnumdepth >-2\relax + \huge\bfseries \partname~\thepart + \par + \vskip 20\p@ + \fi + \Huge \bfseries #2\par}% + \@endpart} +\def\@spart#1{% + {\centering + \interlinepenalty \@M + \normalfont + \Huge \bfseries #1\par}% + \@endpart} +\def\@endpart{\vfil\newpage + \if@twoside + \null + \thispagestyle{empty}% + \newpage + \fi + \if@tempswa + \twocolumn + \fi} + +\newcommand\chapter{\clearpage + \thispagestyle{empty}% + \global\@topnum\z@ + \@afterindentfalse + \secdef\@chapter\@schapter} +\def\@chapter[#1]#2{\ifnum \c@secnumdepth >\m@ne + \if@mainmatter + \refstepcounter{chapter}% + \typeout{\@chapapp\space\thechapter.}% + \addcontentsline{toc}{chapter}% + {\protect\numberline{\thechapter}#1}% + \else + \addcontentsline{toc}{chapter}{#1}% + \fi + \else + \addcontentsline{toc}{chapter}{#1}% + \fi + \chaptermark{#1}% + \addtocontents{lof}{\protect\addvspace{10\p@}}% + \addtocontents{lot}{\protect\addvspace{10\p@}}% + \if@twocolumn + \@topnewpage[\@makechapterhead{#2}]% + \else + \@makechapterhead{#2}% + \@afterheading + \fi} +\def\@makechapterhead#1{% +% \vspace*{50\p@}% + {\centering + \ifnum \c@secnumdepth >\m@ne + \if@mainmatter + \large\bfseries \@chapapp{} \thechapter + \par\nobreak + \vskip 20\p@ + \fi + \fi + \interlinepenalty\@M + \Large \bfseries #1\par\nobreak + \vskip 40\p@ + }} +\def\@schapter#1{\if@twocolumn + \@topnewpage[\@makeschapterhead{#1}]% + \else + \@makeschapterhead{#1}% + \@afterheading + \fi} +\def\@makeschapterhead#1{% +% \vspace*{50\p@}% + {\centering + \normalfont + \interlinepenalty\@M + \Large \bfseries #1\par\nobreak + \vskip 40\p@ + }} + +\renewcommand\section{\@startsection{section}{1}{\z@}% + {-18\p@ \@plus -4\p@ \@minus -4\p@}% + {12\p@ \@plus 4\p@ \@minus 4\p@}% + {\normalfont\large\bfseries\boldmath + \rightskip=\z@ \@plus 8em\pretolerance=10000 }} +\renewcommand\subsection{\@startsection{subsection}{2}{\z@}% + {-18\p@ \@plus -4\p@ \@minus -4\p@}% + {8\p@ \@plus 4\p@ \@minus 4\p@}% + {\normalfont\normalsize\bfseries\boldmath + \rightskip=\z@ \@plus 8em\pretolerance=10000 }} +\renewcommand\subsubsection{\@startsection{subsubsection}{3}{\z@}% + {-18\p@ \@plus -4\p@ \@minus -4\p@}% + {-0.5em \@plus -0.22em \@minus -0.1em}% + {\normalfont\normalsize\bfseries\boldmath}} +\renewcommand\paragraph{\@startsection{paragraph}{4}{\z@}% + {-12\p@ \@plus -4\p@ \@minus -4\p@}% + {-0.5em \@plus -0.22em \@minus -0.1em}% + {\normalfont\normalsize\itshape}} +\renewcommand\subparagraph[1]{\typeout{LLNCS warning: You should not use + \string\subparagraph\space with this class}\vskip0.5cm +You should not use \verb|\subparagraph| with this class.\vskip0.5cm} + +\DeclareMathSymbol{\Gamma}{\mathalpha}{letters}{"00} +\DeclareMathSymbol{\Delta}{\mathalpha}{letters}{"01} +\DeclareMathSymbol{\Theta}{\mathalpha}{letters}{"02} +\DeclareMathSymbol{\Lambda}{\mathalpha}{letters}{"03} +\DeclareMathSymbol{\Xi}{\mathalpha}{letters}{"04} +\DeclareMathSymbol{\Pi}{\mathalpha}{letters}{"05} +\DeclareMathSymbol{\Sigma}{\mathalpha}{letters}{"06} +\DeclareMathSymbol{\Upsilon}{\mathalpha}{letters}{"07} +\DeclareMathSymbol{\Phi}{\mathalpha}{letters}{"08} +\DeclareMathSymbol{\Psi}{\mathalpha}{letters}{"09} +\DeclareMathSymbol{\Omega}{\mathalpha}{letters}{"0A} + +\let\footnotesize\small + +\if@custvec +\def\vec#1{\mathchoice{\mbox{\boldmath$\displaystyle#1$}} +{\mbox{\boldmath$\textstyle#1$}} +{\mbox{\boldmath$\scriptstyle#1$}} +{\mbox{\boldmath$\scriptscriptstyle#1$}}} +\fi + +\def\squareforqed{\hbox{\rlap{$\sqcap$}$\sqcup$}} +\def\qed{\ifmmode\squareforqed\else{\unskip\nobreak\hfil +\penalty50\hskip1em\null\nobreak\hfil\squareforqed +\parfillskip=0pt\finalhyphendemerits=0\endgraf}\fi} + +\def\getsto{\mathrel{\mathchoice {\vcenter{\offinterlineskip +\halign{\hfil +$\displaystyle##$\hfil\cr\gets\cr\to\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\textstyle##$\hfil\cr\gets +\cr\to\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptstyle##$\hfil\cr\gets +\cr\to\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptscriptstyle##$\hfil\cr +\gets\cr\to\cr}}}}} +\def\lid{\mathrel{\mathchoice {\vcenter{\offinterlineskip\halign{\hfil +$\displaystyle##$\hfil\cr<\cr\noalign{\vskip1.2pt}=\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\textstyle##$\hfil\cr<\cr +\noalign{\vskip1.2pt}=\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptstyle##$\hfil\cr<\cr +\noalign{\vskip1pt}=\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptscriptstyle##$\hfil\cr +<\cr +\noalign{\vskip0.9pt}=\cr}}}}} +\def\gid{\mathrel{\mathchoice {\vcenter{\offinterlineskip\halign{\hfil +$\displaystyle##$\hfil\cr>\cr\noalign{\vskip1.2pt}=\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\textstyle##$\hfil\cr>\cr +\noalign{\vskip1.2pt}=\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptstyle##$\hfil\cr>\cr +\noalign{\vskip1pt}=\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptscriptstyle##$\hfil\cr +>\cr +\noalign{\vskip0.9pt}=\cr}}}}} +\def\grole{\mathrel{\mathchoice {\vcenter{\offinterlineskip +\halign{\hfil +$\displaystyle##$\hfil\cr>\cr\noalign{\vskip-1pt}<\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\textstyle##$\hfil\cr +>\cr\noalign{\vskip-1pt}<\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptstyle##$\hfil\cr +>\cr\noalign{\vskip-0.8pt}<\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptscriptstyle##$\hfil\cr +>\cr\noalign{\vskip-0.3pt}<\cr}}}}} +\def\bbbr{{\rm I\!R}} %reelle Zahlen +\def\bbbm{{\rm I\!M}} +\def\bbbn{{\rm I\!N}} %natuerliche Zahlen +\def\bbbf{{\rm I\!F}} +\def\bbbh{{\rm I\!H}} +\def\bbbk{{\rm I\!K}} +\def\bbbp{{\rm I\!P}} +\def\bbbone{{\mathchoice {\rm 1\mskip-4mu l} {\rm 1\mskip-4mu l} +{\rm 1\mskip-4.5mu l} {\rm 1\mskip-5mu l}}} +\def\bbbc{{\mathchoice {\setbox0=\hbox{$\displaystyle\rm C$}\hbox{\hbox +to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}} +{\setbox0=\hbox{$\textstyle\rm C$}\hbox{\hbox +to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptstyle\rm C$}\hbox{\hbox +to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptscriptstyle\rm C$}\hbox{\hbox +to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}}}} +\def\bbbq{{\mathchoice {\setbox0=\hbox{$\displaystyle\rm +Q$}\hbox{\raise +0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.8\ht0\hss}\box0}} +{\setbox0=\hbox{$\textstyle\rm Q$}\hbox{\raise +0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.8\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptstyle\rm Q$}\hbox{\raise +0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.7\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptscriptstyle\rm Q$}\hbox{\raise +0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.7\ht0\hss}\box0}}}} +\def\bbbt{{\mathchoice {\setbox0=\hbox{$\displaystyle\rm +T$}\hbox{\hbox to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}} +{\setbox0=\hbox{$\textstyle\rm T$}\hbox{\hbox +to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptstyle\rm T$}\hbox{\hbox +to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptscriptstyle\rm T$}\hbox{\hbox +to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}}}} +\def\bbbs{{\mathchoice +{\setbox0=\hbox{$\displaystyle \rm S$}\hbox{\raise0.5\ht0\hbox +to0pt{\kern0.35\wd0\vrule height0.45\ht0\hss}\hbox +to0pt{\kern0.55\wd0\vrule height0.5\ht0\hss}\box0}} +{\setbox0=\hbox{$\textstyle \rm S$}\hbox{\raise0.5\ht0\hbox +to0pt{\kern0.35\wd0\vrule height0.45\ht0\hss}\hbox +to0pt{\kern0.55\wd0\vrule height0.5\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptstyle \rm S$}\hbox{\raise0.5\ht0\hbox +to0pt{\kern0.35\wd0\vrule height0.45\ht0\hss}\raise0.05\ht0\hbox +to0pt{\kern0.5\wd0\vrule height0.45\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptscriptstyle\rm S$}\hbox{\raise0.5\ht0\hbox +to0pt{\kern0.4\wd0\vrule height0.45\ht0\hss}\raise0.05\ht0\hbox +to0pt{\kern0.55\wd0\vrule height0.45\ht0\hss}\box0}}}} +\def\bbbz{{\mathchoice {\hbox{$\mathsf\textstyle Z\kern-0.4em Z$}} +{\hbox{$\mathsf\textstyle Z\kern-0.4em Z$}} +{\hbox{$\mathsf\scriptstyle Z\kern-0.3em Z$}} +{\hbox{$\mathsf\scriptscriptstyle Z\kern-0.2em Z$}}}} + +\let\ts\, + +\setlength\leftmargini {17\p@} +\setlength\leftmargin {\leftmargini} +\setlength\leftmarginii {\leftmargini} +\setlength\leftmarginiii {\leftmargini} +\setlength\leftmarginiv {\leftmargini} +\setlength \labelsep {.5em} +\setlength \labelwidth{\leftmargini} +\addtolength\labelwidth{-\labelsep} + +\def\@listI{\leftmargin\leftmargini + \parsep 0\p@ \@plus1\p@ \@minus\p@ + \topsep 8\p@ \@plus2\p@ \@minus4\p@ + \itemsep0\p@} +\let\@listi\@listI +\@listi +\def\@listii {\leftmargin\leftmarginii + \labelwidth\leftmarginii + \advance\labelwidth-\labelsep + \topsep 0\p@ \@plus2\p@ \@minus\p@} +\def\@listiii{\leftmargin\leftmarginiii + \labelwidth\leftmarginiii + \advance\labelwidth-\labelsep + \topsep 0\p@ \@plus\p@\@minus\p@ + \parsep \z@ + \partopsep \p@ \@plus\z@ \@minus\p@} + +\renewcommand\labelitemi{\normalfont\bfseries --} +\renewcommand\labelitemii{$\m@th\bullet$} + +\setlength\arraycolsep{1.4\p@} +\setlength\tabcolsep{1.4\p@} + +\def\tableofcontents{\chapter*{\contentsname\@mkboth{{\contentsname}}% + {{\contentsname}}} + \def\authcount##1{\setcounter{auco}{##1}\setcounter{@auth}{1}} + \def\lastand{\ifnum\value{auco}=2\relax + \unskip{} \andname\ + \else + \unskip \lastandname\ + \fi}% + \def\and{\stepcounter{@auth}\relax + \ifnum\value{@auth}=\value{auco}% + \lastand + \else + \unskip, + \fi}% + \@starttoc{toc}\if@restonecol\twocolumn\fi} + +\def\l@part#1#2{\addpenalty{\@secpenalty}% + \addvspace{2em plus\p@}% % space above part line + \begingroup + \parindent \z@ + \rightskip \z@ plus 5em + \hrule\vskip5pt + \large % same size as for a contribution heading + \bfseries\boldmath % set line in boldface + \leavevmode % TeX command to enter horizontal mode. + #1\par + \vskip5pt + \hrule + \vskip1pt + \nobreak % Never break after part entry + \endgroup} + +\def\@dotsep{2} + +\let\phantomsection=\relax + +\def\hyperhrefextend{\ifx\hyper@anchor\@undefined\else +{}\fi} + +\def\addnumcontentsmark#1#2#3{% +\addtocontents{#1}{\protect\contentsline{#2}{\protect\numberline + {\thechapter}#3}{\thepage}\hyperhrefextend}}% +\def\addcontentsmark#1#2#3{% +\addtocontents{#1}{\protect\contentsline{#2}{#3}{\thepage}\hyperhrefextend}}% +\def\addcontentsmarkwop#1#2#3{% +\addtocontents{#1}{\protect\contentsline{#2}{#3}{0}\hyperhrefextend}}% + +\def\@adcmk[#1]{\ifcase #1 \or +\def\@gtempa{\addnumcontentsmark}% + \or \def\@gtempa{\addcontentsmark}% + \or \def\@gtempa{\addcontentsmarkwop}% + \fi\@gtempa{toc}{chapter}% +} +\def\addtocmark{% +\phantomsection +\@ifnextchar[{\@adcmk}{\@adcmk[3]}% +} + +\def\l@chapter#1#2{\addpenalty{-\@highpenalty} + \vskip 1.0em plus 1pt \@tempdima 1.5em \begingroup + \parindent \z@ \rightskip \@tocrmarg + \advance\rightskip by 0pt plus 2cm + \parfillskip -\rightskip \pretolerance=10000 + \leavevmode \advance\leftskip\@tempdima \hskip -\leftskip + {\large\bfseries\boldmath#1}\ifx0#2\hfil\null + \else + \nobreak + \leaders\hbox{$\m@th \mkern \@dotsep mu.\mkern + \@dotsep mu$}\hfill + \nobreak\hbox to\@pnumwidth{\hss #2}% + \fi\par + \penalty\@highpenalty \endgroup} + +\def\l@title#1#2{\addpenalty{-\@highpenalty} + \addvspace{8pt plus 1pt} + \@tempdima \z@ + \begingroup + \parindent \z@ \rightskip \@tocrmarg + \advance\rightskip by 0pt plus 2cm + \parfillskip -\rightskip \pretolerance=10000 + \leavevmode \advance\leftskip\@tempdima \hskip -\leftskip + #1\nobreak + \leaders\hbox{$\m@th \mkern \@dotsep mu.\mkern + \@dotsep mu$}\hfill + \nobreak\hbox to\@pnumwidth{\hss #2}\par + \penalty\@highpenalty \endgroup} + +\def\l@author#1#2{\addpenalty{\@highpenalty} + \@tempdima=15\p@ %\z@ + \begingroup + \parindent \z@ \rightskip \@tocrmarg + \advance\rightskip by 0pt plus 2cm + \pretolerance=10000 + \leavevmode \advance\leftskip\@tempdima %\hskip -\leftskip + \textit{#1}\par + \penalty\@highpenalty \endgroup} + +\setcounter{tocdepth}{0} +\newdimen\tocchpnum +\newdimen\tocsecnum +\newdimen\tocsectotal +\newdimen\tocsubsecnum +\newdimen\tocsubsectotal +\newdimen\tocsubsubsecnum +\newdimen\tocsubsubsectotal +\newdimen\tocparanum +\newdimen\tocparatotal +\newdimen\tocsubparanum +\tocchpnum=\z@ % no chapter numbers +\tocsecnum=15\p@ % section 88. plus 2.222pt +\tocsubsecnum=23\p@ % subsection 88.8 plus 2.222pt +\tocsubsubsecnum=27\p@ % subsubsection 88.8.8 plus 1.444pt +\tocparanum=35\p@ % paragraph 88.8.8.8 plus 1.666pt +\tocsubparanum=43\p@ % subparagraph 88.8.8.8.8 plus 1.888pt +\def\calctocindent{% +\tocsectotal=\tocchpnum +\advance\tocsectotal by\tocsecnum +\tocsubsectotal=\tocsectotal +\advance\tocsubsectotal by\tocsubsecnum +\tocsubsubsectotal=\tocsubsectotal +\advance\tocsubsubsectotal by\tocsubsubsecnum +\tocparatotal=\tocsubsubsectotal +\advance\tocparatotal by\tocparanum} +\calctocindent + +\def\l@section{\@dottedtocline{1}{\tocchpnum}{\tocsecnum}} +\def\l@subsection{\@dottedtocline{2}{\tocsectotal}{\tocsubsecnum}} +\def\l@subsubsection{\@dottedtocline{3}{\tocsubsectotal}{\tocsubsubsecnum}} +\def\l@paragraph{\@dottedtocline{4}{\tocsubsubsectotal}{\tocparanum}} +\def\l@subparagraph{\@dottedtocline{5}{\tocparatotal}{\tocsubparanum}} + +\def\listoffigures{\@restonecolfalse\if@twocolumn\@restonecoltrue\onecolumn + \fi\section*{\listfigurename\@mkboth{{\listfigurename}}{{\listfigurename}}} + \@starttoc{lof}\if@restonecol\twocolumn\fi} +\def\l@figure{\@dottedtocline{1}{0em}{1.5em}} + +\def\listoftables{\@restonecolfalse\if@twocolumn\@restonecoltrue\onecolumn + \fi\section*{\listtablename\@mkboth{{\listtablename}}{{\listtablename}}} + \@starttoc{lot}\if@restonecol\twocolumn\fi} +\let\l@table\l@figure + +\renewcommand\listoffigures{% + \section*{\listfigurename + \@mkboth{\listfigurename}{\listfigurename}}% + \@starttoc{lof}% + } + +\renewcommand\listoftables{% + \section*{\listtablename + \@mkboth{\listtablename}{\listtablename}}% + \@starttoc{lot}% + } + +\ifx\oribibl\undefined +\ifx\citeauthoryear\undefined +\renewenvironment{thebibliography}[1] + {\section*{\refname} + \def\@biblabel##1{##1.} + \small + \list{\@biblabel{\@arabic\c@enumiv}}% + {\settowidth\labelwidth{\@biblabel{#1}}% + \leftmargin\labelwidth + \advance\leftmargin\labelsep + \if@openbib + \advance\leftmargin\bibindent + \itemindent -\bibindent + \listparindent \itemindent + \parsep \z@ + \fi + \usecounter{enumiv}% + \let\p@enumiv\@empty + \renewcommand\theenumiv{\@arabic\c@enumiv}}% + \if@openbib + \renewcommand\newblock{\par}% + \else + \renewcommand\newblock{\hskip .11em \@plus.33em \@minus.07em}% + \fi + \sloppy\clubpenalty4000\widowpenalty4000% + \sfcode`\.=\@m} + {\def\@noitemerr + {\@latex@warning{Empty `thebibliography' environment}}% + \endlist} +\def\@lbibitem[#1]#2{\item[{[#1]}\hfill]\if@filesw + {\let\protect\noexpand\immediate + \write\@auxout{\string\bibcite{#2}{#1}}}\fi\ignorespaces} +\newcount\@tempcntc +\def\@citex[#1]#2{\if@filesw\immediate\write\@auxout{\string\citation{#2}}\fi + \@tempcnta\z@\@tempcntb\m@ne\def\@citea{}\@cite{\@for\@citeb:=#2\do + {\@ifundefined + {b@\@citeb}{\@citeo\@tempcntb\m@ne\@citea\def\@citea{,}{\bfseries + ?}\@warning + {Citation `\@citeb' on page \thepage \space undefined}}% + {\setbox\z@\hbox{\global\@tempcntc0\csname b@\@citeb\endcsname\relax}% + \ifnum\@tempcntc=\z@ \@citeo\@tempcntb\m@ne + \@citea\def\@citea{,}\hbox{\csname b@\@citeb\endcsname}% + \else + \advance\@tempcntb\@ne + \ifnum\@tempcntb=\@tempcntc + \else\advance\@tempcntb\m@ne\@citeo + \@tempcnta\@tempcntc\@tempcntb\@tempcntc\fi\fi}}\@citeo}{#1}} +\def\@citeo{\ifnum\@tempcnta>\@tempcntb\else + \@citea\def\@citea{,\,\hskip\z@skip}% + \ifnum\@tempcnta=\@tempcntb\the\@tempcnta\else + {\advance\@tempcnta\@ne\ifnum\@tempcnta=\@tempcntb \else + \def\@citea{--}\fi + \advance\@tempcnta\m@ne\the\@tempcnta\@citea\the\@tempcntb}\fi\fi} +\else +\renewenvironment{thebibliography}[1] + {\section*{\refname} + \small + \list{}% + {\settowidth\labelwidth{}% + \leftmargin\parindent + \itemindent=-\parindent + \labelsep=\z@ + \if@openbib + \advance\leftmargin\bibindent + \itemindent -\bibindent + \listparindent \itemindent + \parsep \z@ + \fi + \usecounter{enumiv}% + \let\p@enumiv\@empty + \renewcommand\theenumiv{}}% + \if@openbib + \renewcommand\newblock{\par}% + \else + \renewcommand\newblock{\hskip .11em \@plus.33em \@minus.07em}% + \fi + \sloppy\clubpenalty4000\widowpenalty4000% + \sfcode`\.=\@m} + {\def\@noitemerr + {\@latex@warning{Empty `thebibliography' environment}}% + \endlist} + \def\@cite#1{#1}% + \def\@lbibitem[#1]#2{\item[]\if@filesw + {\def\protect##1{\string ##1\space}\immediate + \write\@auxout{\string\bibcite{#2}{#1}}}\fi\ignorespaces} + \fi +\else +\@cons\@openbib@code{\noexpand\small} +\fi + +\def\idxquad{\hskip 10\p@}% space that divides entry from number + +\def\@idxitem{\par\hangindent 10\p@} + +\def\subitem{\par\setbox0=\hbox{--\enspace}% second order + \noindent\hangindent\wd0\box0}% index entry + +\def\subsubitem{\par\setbox0=\hbox{--\,--\enspace}% third + \noindent\hangindent\wd0\box0}% order index entry + +\def\indexspace{\par \vskip 10\p@ plus5\p@ minus3\p@\relax} + +\renewenvironment{theindex} + {\@mkboth{\indexname}{\indexname}% + \thispagestyle{empty}\parindent\z@ + \parskip\z@ \@plus .3\p@\relax + \let\item\par + \def\,{\relax\ifmmode\mskip\thinmuskip + \else\hskip0.2em\ignorespaces\fi}% + \normalfont\small + \begin{multicols}{2}[\@makeschapterhead{\indexname}]% + } + {\end{multicols}} + +\renewcommand\footnoterule{% + \kern-3\p@ + \hrule\@width 2truecm + \kern2.6\p@} + \newdimen\fnindent + \fnindent1em +\long\def\@makefntext#1{% + \parindent \fnindent% + \leftskip \fnindent% + \noindent + \llap{\hb@xt@1em{\hss\@makefnmark\ }}\ignorespaces#1} + +\long\def\@makecaption#1#2{% + \small + \vskip\abovecaptionskip + \sbox\@tempboxa{{\bfseries #1.} #2}% + \ifdim \wd\@tempboxa >\hsize + {\bfseries #1.} #2\par + \else + \global \@minipagefalse + \hb@xt@\hsize{\hfil\box\@tempboxa\hfil}% + \fi + \vskip\belowcaptionskip} + +\def\fps@figure{htbp} +\def\fnum@figure{\figurename\thinspace\thefigure} +\def \@floatboxreset {% + \reset@font + \small + \@setnobreak + \@setminipage +} +\def\fps@table{htbp} +\def\fnum@table{\tablename~\thetable} +\renewenvironment{table} + {\setlength\abovecaptionskip{0\p@}% + \setlength\belowcaptionskip{10\p@}% + \@float{table}} + {\end@float} +\renewenvironment{table*} + {\setlength\abovecaptionskip{0\p@}% + \setlength\belowcaptionskip{10\p@}% + \@dblfloat{table}} + {\end@dblfloat} + +\long\def\@caption#1[#2]#3{\par\addcontentsline{\csname + ext@#1\endcsname}{#1}{\protect\numberline{\csname + the#1\endcsname}{\ignorespaces #2}}\begingroup + \@parboxrestore + \@makecaption{\csname fnum@#1\endcsname}{\ignorespaces #3}\par + \endgroup} + +% LaTeX does not provide a command to enter the authors institute +% addresses. The \institute command is defined here. + +\newcounter{@inst} +\newcounter{@auth} +\newcounter{auco} +\newdimen\instindent +\newbox\authrun +\newtoks\authorrunning +\newtoks\tocauthor +\newbox\titrun +\newtoks\titlerunning +\newtoks\toctitle + +\def\clearheadinfo{\gdef\@author{No Author Given}% + \gdef\@title{No Title Given}% + \gdef\@subtitle{}% + \gdef\@institute{No Institute Given}% + \gdef\@thanks{}% + \global\titlerunning={}\global\authorrunning={}% + \global\toctitle={}\global\tocauthor={}} + +\def\institute#1{\gdef\@institute{#1}} + +\def\institutename{\par + \begingroup + \parskip=\z@ + \parindent=\z@ + \setcounter{@inst}{1}% + \def\and{\par\stepcounter{@inst}% + \noindent$^{\the@inst}$\enspace\ignorespaces}% + \setbox0=\vbox{\def\thanks##1{}\@institute}% + \ifnum\c@@inst=1\relax + \gdef\fnnstart{0}% + \else + \xdef\fnnstart{\c@@inst}% + \setcounter{@inst}{1}% + \noindent$^{\the@inst}$\enspace + \fi + \ignorespaces + \@institute\par + \endgroup} + +\def\@fnsymbol#1{\ensuremath{\ifcase#1\or\star\or{\star\star}\or + {\star\star\star}\or \dagger\or \ddagger\or + \mathchar "278\or \mathchar "27B\or \|\or **\or \dagger\dagger + \or \ddagger\ddagger \else\@ctrerr\fi}} + +\def\inst#1{\unskip$^{#1}$} +\def\fnmsep{\unskip$^,$} +\def\email#1{{\tt#1}} +\AtBeginDocument{\@ifundefined{url}{\def\url#1{#1}}{}% +\@ifpackageloaded{babel}{% +\@ifundefined{extrasenglish}{}{\addto\extrasenglish{\switcht@albion}}% +\@ifundefined{extrasfrenchb}{}{\addto\extrasfrenchb{\switcht@francais}}% +\@ifundefined{extrasgerman}{}{\addto\extrasgerman{\switcht@deutsch}}% +}{\switcht@@therlang}% +\providecommand{\keywords}[1]{\par\addvspace\baselineskip +\noindent\keywordname\enspace\ignorespaces#1}% +} +\def\homedir{\~{ }} + +\def\subtitle#1{\gdef\@subtitle{#1}} +\clearheadinfo +% +%%% to avoid hyperref warnings +\providecommand*{\toclevel@author}{999} +%%% to make title-entry parent of section-entries +\providecommand*{\toclevel@title}{0} +% +\renewcommand\maketitle{\newpage +\phantomsection + \refstepcounter{chapter}% + \stepcounter{section}% + \setcounter{section}{0}% + \setcounter{subsection}{0}% + \setcounter{figure}{0} + \setcounter{table}{0} + \setcounter{equation}{0} + \setcounter{footnote}{0}% + \begingroup + \parindent=\z@ + \renewcommand\thefootnote{\@fnsymbol\c@footnote}% + \if@twocolumn + \ifnum \col@number=\@ne + \@maketitle + \else + \twocolumn[\@maketitle]% + \fi + \else + \newpage + \global\@topnum\z@ % Prevents figures from going at top of page. + \@maketitle + \fi + \thispagestyle{empty}\@thanks +% + \def\\{\unskip\ \ignorespaces}\def\inst##1{\unskip{}}% + \def\thanks##1{\unskip{}}\def\fnmsep{\unskip}% + \instindent=\hsize + \advance\instindent by-\headlineindent + \if!\the\toctitle!\addcontentsline{toc}{title}{\@title}\else + \addcontentsline{toc}{title}{\the\toctitle}\fi + \if@runhead + \if!\the\titlerunning!\else + \edef\@title{\the\titlerunning}% + \fi + \global\setbox\titrun=\hbox{\small\rm\unboldmath\ignorespaces\@title}% + \ifdim\wd\titrun>\instindent + \typeout{Title too long for running head. Please supply}% + \typeout{a shorter form with \string\titlerunning\space prior to + \string\maketitle}% + \global\setbox\titrun=\hbox{\small\rm + Title Suppressed Due to Excessive Length}% + \fi + \xdef\@title{\copy\titrun}% + \fi +% + \if!\the\tocauthor!\relax + {\def\and{\noexpand\protect\noexpand\and}% + \protected@xdef\toc@uthor{\@author}}% + \else + \def\\{\noexpand\protect\noexpand\newline}% + \protected@xdef\scratch{\the\tocauthor}% + \protected@xdef\toc@uthor{\scratch}% + \fi + \addtocontents{toc}{\noexpand\protect\noexpand\authcount{\the\c@auco}}% + \addcontentsline{toc}{author}{\toc@uthor}% + \if@runhead + \if!\the\authorrunning! + \value{@inst}=\value{@auth}% + \setcounter{@auth}{1}% + \else + \edef\@author{\the\authorrunning}% + \fi + \global\setbox\authrun=\hbox{\small\unboldmath\@author\unskip}% + \ifdim\wd\authrun>\instindent + \typeout{Names of authors too long for running head. Please supply}% + \typeout{a shorter form with \string\authorrunning\space prior to + \string\maketitle}% + \global\setbox\authrun=\hbox{\small\rm + Authors Suppressed Due to Excessive Length}% + \fi + \xdef\@author{\copy\authrun}% + \markboth{\@author}{\@title}% + \fi + \endgroup + \setcounter{footnote}{\fnnstart}% + \clearheadinfo} +% +\def\@maketitle{\newpage + \markboth{}{}% + \def\lastand{\ifnum\value{@inst}=2\relax + \unskip{} \andname\ + \else + \unskip \lastandname\ + \fi}% + \def\and{\stepcounter{@auth}\relax + \ifnum\value{@auth}=\value{@inst}% + \lastand + \else + \unskip, + \fi}% + \begin{center}% + \let\newline\\ + {\Large \bfseries\boldmath + \pretolerance=10000 + \@title \par}\vskip .8cm +\if!\@subtitle!\else {\large \bfseries\boldmath + \vskip -.65cm + \pretolerance=10000 + \@subtitle \par}\vskip .8cm\fi + \setbox0=\vbox{\setcounter{@auth}{1}\def\and{\stepcounter{@auth}}% + \def\thanks##1{}\@author}% + \global\value{@inst}=\value{@auth}% + \global\value{auco}=\value{@auth}% + \setcounter{@auth}{1}% +{\lineskip .5em +\noindent\ignorespaces +\@author\vskip.35cm} + {\small\institutename} + \end{center}% + } + +% definition of the "\spnewtheorem" command. +% +% Usage: +% +% \spnewtheorem{env_nam}{caption}[within]{cap_font}{body_font} +% or \spnewtheorem{env_nam}[numbered_like]{caption}{cap_font}{body_font} +% or \spnewtheorem*{env_nam}{caption}{cap_font}{body_font} +% +% New is "cap_font" and "body_font". It stands for +% fontdefinition of the caption and the text itself. +% +% "\spnewtheorem*" gives a theorem without number. +% +% A defined spnewthoerem environment is used as described +% by Lamport. +% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\def\@thmcountersep{} +\def\@thmcounterend{.} + +\def\spnewtheorem{\@ifstar{\@sthm}{\@Sthm}} + +% definition of \spnewtheorem with number + +\def\@spnthm#1#2{% + \@ifnextchar[{\@spxnthm{#1}{#2}}{\@spynthm{#1}{#2}}} +\def\@Sthm#1{\@ifnextchar[{\@spothm{#1}}{\@spnthm{#1}}} + +\def\@spxnthm#1#2[#3]#4#5{\expandafter\@ifdefinable\csname #1\endcsname + {\@definecounter{#1}\@addtoreset{#1}{#3}% + \expandafter\xdef\csname the#1\endcsname{\expandafter\noexpand + \csname the#3\endcsname \noexpand\@thmcountersep \@thmcounter{#1}}% + \expandafter\xdef\csname #1name\endcsname{#2}% + \global\@namedef{#1}{\@spthm{#1}{\csname #1name\endcsname}{#4}{#5}}% + \global\@namedef{end#1}{\@endtheorem}}} + +\def\@spynthm#1#2#3#4{\expandafter\@ifdefinable\csname #1\endcsname + {\@definecounter{#1}% + \expandafter\xdef\csname the#1\endcsname{\@thmcounter{#1}}% + \expandafter\xdef\csname #1name\endcsname{#2}% + \global\@namedef{#1}{\@spthm{#1}{\csname #1name\endcsname}{#3}{#4}}% + \global\@namedef{end#1}{\@endtheorem}}} + +\def\@spothm#1[#2]#3#4#5{% + \@ifundefined{c@#2}{\@latexerr{No theorem environment `#2' defined}\@eha}% + {\expandafter\@ifdefinable\csname #1\endcsname + {\newaliascnt{#1}{#2}% + \expandafter\xdef\csname #1name\endcsname{#3}% + \global\@namedef{#1}{\@spthm{#1}{\csname #1name\endcsname}{#4}{#5}}% + \global\@namedef{end#1}{\@endtheorem}}}} + +\def\@spthm#1#2#3#4{\topsep 7\p@ \@plus2\p@ \@minus4\p@ +\refstepcounter{#1}% +\@ifnextchar[{\@spythm{#1}{#2}{#3}{#4}}{\@spxthm{#1}{#2}{#3}{#4}}} + +\def\@spxthm#1#2#3#4{\@spbegintheorem{#2}{\csname the#1\endcsname}{#3}{#4}% + \ignorespaces} + +\def\@spythm#1#2#3#4[#5]{\@spopargbegintheorem{#2}{\csname + the#1\endcsname}{#5}{#3}{#4}\ignorespaces} + +\def\@spbegintheorem#1#2#3#4{\trivlist + \item[\hskip\labelsep{#3#1\ #2\@thmcounterend}]#4} + +\def\@spopargbegintheorem#1#2#3#4#5{\trivlist + \item[\hskip\labelsep{#4#1\ #2}]{#4(#3)\@thmcounterend\ }#5} + +% definition of \spnewtheorem* without number + +\def\@sthm#1#2{\@Ynthm{#1}{#2}} + +\def\@Ynthm#1#2#3#4{\expandafter\@ifdefinable\csname #1\endcsname + {\global\@namedef{#1}{\@Thm{\csname #1name\endcsname}{#3}{#4}}% + \expandafter\xdef\csname #1name\endcsname{#2}% + \global\@namedef{end#1}{\@endtheorem}}} + +\def\@Thm#1#2#3{\topsep 7\p@ \@plus2\p@ \@minus4\p@ +\@ifnextchar[{\@Ythm{#1}{#2}{#3}}{\@Xthm{#1}{#2}{#3}}} + +\def\@Xthm#1#2#3{\@Begintheorem{#1}{#2}{#3}\ignorespaces} + +\def\@Ythm#1#2#3[#4]{\@Opargbegintheorem{#1} + {#4}{#2}{#3}\ignorespaces} + +\def\@Begintheorem#1#2#3{#3\trivlist + \item[\hskip\labelsep{#2#1\@thmcounterend}]} + +\def\@Opargbegintheorem#1#2#3#4{#4\trivlist + \item[\hskip\labelsep{#3#1}]{#3(#2)\@thmcounterend\ }} + +\if@envcntsect + \def\@thmcountersep{.} + \spnewtheorem{theorem}{Theorem}[section]{\bfseries}{\itshape} +\else + \spnewtheorem{theorem}{Theorem}{\bfseries}{\itshape} + \if@envcntreset + \@addtoreset{theorem}{section} + \else + \@addtoreset{theorem}{chapter} + \fi +\fi + +%definition of divers theorem environments +\spnewtheorem*{claim}{Claim}{\itshape}{\rmfamily} +\spnewtheorem*{proof}{Proof}{\itshape}{\rmfamily} +\if@envcntsame % alle Umgebungen wie Theorem. + \def\spn@wtheorem#1#2#3#4{\@spothm{#1}[theorem]{#2}{#3}{#4}} +\else % alle Umgebungen mit eigenem Zaehler + \if@envcntsect % mit section numeriert + \def\spn@wtheorem#1#2#3#4{\@spxnthm{#1}{#2}[section]{#3}{#4}} + \else % nicht mit section numeriert + \if@envcntreset + \def\spn@wtheorem#1#2#3#4{\@spynthm{#1}{#2}{#3}{#4} + \@addtoreset{#1}{section}} + \else + \def\spn@wtheorem#1#2#3#4{\@spynthm{#1}{#2}{#3}{#4} + \@addtoreset{#1}{chapter}}% + \fi + \fi +\fi +\spn@wtheorem{case}{Case}{\itshape}{\rmfamily} +\spn@wtheorem{conjecture}{Conjecture}{\itshape}{\rmfamily} +\spn@wtheorem{corollary}{Corollary}{\bfseries}{\itshape} +\spn@wtheorem{definition}{Definition}{\bfseries}{\itshape} +\spn@wtheorem{example}{Example}{\itshape}{\rmfamily} +\spn@wtheorem{exercise}{Exercise}{\itshape}{\rmfamily} +\spn@wtheorem{lemma}{Lemma}{\bfseries}{\itshape} +\spn@wtheorem{note}{Note}{\itshape}{\rmfamily} +\spn@wtheorem{problem}{Problem}{\itshape}{\rmfamily} +\spn@wtheorem{property}{Property}{\itshape}{\rmfamily} +\spn@wtheorem{proposition}{Proposition}{\bfseries}{\itshape} +\spn@wtheorem{question}{Question}{\itshape}{\rmfamily} +\spn@wtheorem{solution}{Solution}{\itshape}{\rmfamily} +\spn@wtheorem{remark}{Remark}{\itshape}{\rmfamily} + +\def\@takefromreset#1#2{% + \def\@tempa{#1}% + \let\@tempd\@elt + \def\@elt##1{% + \def\@tempb{##1}% + \ifx\@tempa\@tempb\else + \@addtoreset{##1}{#2}% + \fi}% + \expandafter\expandafter\let\expandafter\@tempc\csname cl@#2\endcsname + \expandafter\def\csname cl@#2\endcsname{}% + \@tempc + \let\@elt\@tempd} + +\def\theopargself{\def\@spopargbegintheorem##1##2##3##4##5{\trivlist + \item[\hskip\labelsep{##4##1\ ##2}]{##4##3\@thmcounterend\ }##5} + \def\@Opargbegintheorem##1##2##3##4{##4\trivlist + \item[\hskip\labelsep{##3##1}]{##3##2\@thmcounterend\ }} + } + +\renewenvironment{abstract}{% + \list{}{\advance\topsep by0.35cm\relax\small + \leftmargin=1cm + \labelwidth=\z@ + \listparindent=\z@ + \itemindent\listparindent + \rightmargin\leftmargin}\item[\hskip\labelsep + \bfseries\abstractname]} + {\endlist} + +\newdimen\headlineindent % dimension for space between +\headlineindent=1.166cm % number and text of headings. + +\def\ps@headings{\let\@mkboth\@gobbletwo + \let\@oddfoot\@empty\let\@evenfoot\@empty + \def\@evenhead{\normalfont\small\rlap{\thepage}\hspace{\headlineindent}% + \leftmark\hfil} + \def\@oddhead{\normalfont\small\hfil\rightmark\hspace{\headlineindent}% + \llap{\thepage}} + \def\chaptermark##1{}% + \def\sectionmark##1{}% + \def\subsectionmark##1{}} + +\def\ps@titlepage{\let\@mkboth\@gobbletwo + \let\@oddfoot\@empty\let\@evenfoot\@empty + \def\@evenhead{\normalfont\small\rlap{\thepage}\hspace{\headlineindent}% + \hfil} + \def\@oddhead{\normalfont\small\hfil\hspace{\headlineindent}% + \llap{\thepage}} + \def\chaptermark##1{}% + \def\sectionmark##1{}% + \def\subsectionmark##1{}} + +\if@runhead\ps@headings\else +\ps@empty\fi + +\setlength\arraycolsep{1.4\p@} +\setlength\tabcolsep{1.4\p@} + +\endinput +%end of file llncs.cls