From: Sébastien Miquée Date: Wed, 28 Jul 2010 11:06:00 +0000 (+0200) Subject: Adding the camera-ready version. X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/interreg4.git/commitdiff_plain/013c93d104bec94042ad7c3675d0810f7013084c Adding the camera-ready version. --- diff --git a/heteropar10/camera_ready/biblio.bib b/heteropar10/camera_ready/biblio.bib new file mode 100644 index 0000000..314a481 --- /dev/null +++ b/heteropar10/camera_ready/biblio.bib @@ -0,0 +1,164 @@ +@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", + 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", + 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 = "NASA Advanced Supercomputing (NAS) Division", + 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}, + } + +@article{fec, + title = {A simple and efficient automatic fem domain decomposer}, + journal = {Computers \& Structures}, + volume = {28}, + number = {5}, + pages = {579 - 602}, + year = {1988}, + note = {}, + issn = {0045-7949}, + author = {C. Farhat} +} \ No newline at end of file diff --git a/heteropar10/camera_ready/heteropar10.pdf b/heteropar10/camera_ready/heteropar10.pdf new file mode 100644 index 0000000..fdc9f1b Binary files /dev/null and b/heteropar10/camera_ready/heteropar10.pdf differ diff --git a/heteropar10/camera_ready/heteropar10.tex b/heteropar10/camera_ready/heteropar10.tex new file mode 100644 index 0000000..fa91744 --- /dev/null +++ b/heteropar10/camera_ready/heteropar10.tex @@ -0,0 +1,732 @@ +\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} +\usepackage{multirow} +\DeclareGraphicsExtensions{.pdf,.jpeg,.png} + + +\title{MAHEVE: An Efficient Reliable Mapping of Asynchronous Iterative + Applications on Volatile and 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{\vspace{-0.2cm} + 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. In this paper we + present 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 computing nodes failures. Our experiments show gains on a + typical AIAC application execution time of about $55\%$, executed + on distributed clusters architectures containing more than 400 + computing cores with the JaceP2P-V2 environment. +\end{abstract} + +\section{Introduction} +\label{sec:intro} + +Nowadays, scientific applications require a great computation power to +solve large problems. Though personal computers are becoming 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,bcvc06:ij}. + + +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 the Conjugate +Gradient\cite{cg} methods are examples of such methods. To parallelize +them, one of the most used methods is the message passing paradigm +which provides efficient mechanisms 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 + Iterations -- Asynchronous Communications}). + +\begin{figure}[h!] + \vspace{-0.4cm} + \centering + \includegraphics[width=7.4cm]{images/AIAC} + \caption{Two processors computing in the Asynchronous Iterations -- Asynchronous Communications (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 the implementation of +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 significantly reducing the application execution +time. These experiments were performed by using the fully fault +tolerant JaceP2P-V2 environment, described in next section. +%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. As architecture heterogeneity +continually evolves according to computing nodes volatility, we have +to take care more precisely 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 up to $65\%$ on application +execution time, with faults during executions, which is about 10 +points better than AIAC-QM and about 25 points better than F-EC, and +MAHEVE also outperforms them in experiments with no fault during executions. + + +The rest of this paper is organized as +follows. Section~\ref{sec:jacep2p} presents the JaceP2P-V2 middleware +by describing its architecture and briefly presenting its fault +tolerance mechanisms. 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 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 are 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 monitors them. If one of them fails, it requires a + replacing one to a super-node; + +\item The ``daemon'', first 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 AIAC applications, JaceP2P-V2 has an +asynchronous messaging mechanism, and to resist daemons failures, it +implements a checkpoint/restart mechanism by using 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, as we suppose that there are +enough available free nodes. Moreover, to resist supervisors failures +and for scalability, some extra nodes are reserved. 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}) model is the most +appropriate 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. As a reminder, +during an iteration in the AIAC model, each task computes its job and +sends its results to its neighbors, and immediately starts the next +iteration. + + +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{N}^+$} 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 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{N}^+$} +gives the amount of available computing nodes (not involved in +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$, \mbox{$C_{\overline{P}i} = \frac{C_{Pi}}{C_{Ni}}$} +%as the average computation power of cluster $C_i$, and +$C_{\overline{P}fi}$ as the average power of available resources of +cluster $C_i$. + +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. + +\vspace{-0.1cm} +\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 $V_i$ and $V_j$ are mapped. As described in +this formula, the execution time of a task depends on the task weight +and on the communications which may occur between this task and 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 have thus to be efficiently 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 +correct 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 performances 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 in a waste of computation +time. Nevertheless, to benefit from multi-cores processors, we use a +task level parallelism by multi-threaded sequential solvers 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 restart a task faster. + + +\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 the Farhat's algorithm\cite{fec}, and +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 at minimizing the whole +application 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 only basically by applying the same policy. As explained 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 at taking the best part of each +category mentioned in Section \ref{sec:pbrw}, the edge-cuts +minimization and the application execution time optimization +algorithms. + + +This new algorithm can be divided into two parts. The first part aims +at performing 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. + + +%\begin{algorithm}[H] +% \SetLine +% \KwIn{GT (app. graph), CL (clusters), hd (heterogeneity degree)} +% \KwOut{Mp (the mapping done)} +% +% \BlankLine +% +% nodes $\leftarrow$ sortingClusters(GG, hd)\; +%% nodes $\leftarrow$ searchNodes(lt, nbTasks)\; +% +%% \BlankLine +% +% tasks $\leftarrow$ sortingTasks(GT, hd)\; +%% tasks $\leftarrow$ orderTasks(st, hd)\; +% +%% \BlankLine +% +% \For{$i = 0$ \KwTo $size(tasks)$} +% { +% Mp.add(tasks($i$), nodes($i$))\; +% } +% +%% \KwRet(Mp) +% +% \caption{General algorithm simplified} +%\end{algorithm} + + +\vspace{-0.15cm} +\subsubsection{Sorting clusters} +\label{sec:maheve_sort_clusters} + +The first step of the initial mapping is to sort clusters according to +the executing platform heterogeneity degree $hd$. The main principles +are that a cluster obtains a better mark when $hd < 0.5$ and it +contains more computing nodes than other clusters ($C_{Fi}$, the +number 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 free 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 number of nodes. As the number of nodes, $C_{Fi}$, and the +average free computing power, $C_{\overline{P}fi}$, are not in the +same order of magnitude, we normalize them with two functions, $normN$ +and $normP$. +%They are defined with \mbox{$normN\left(C_{Fi}\right) = +% C_{Fi} \times 100 \div \sum_{j=1}^{|C|}C_{Fj}$}, which is the rate +%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 of the average power, both +%representing the cluster in the architecture. +We note $normN\left( C_{Fi} \right) = NC_{Fi}$ and +$normP(C_{\overline{P}fi}) =NC_{\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} + 1$ and +$\lim_{hd \rightarrow 1} M_i = NC_{\overline{P}fi} + 1$, 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 according to the heterogeneity +degree of the executing platform. This sorting 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 the 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 $hd$. %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 +nodes. As clusters and tasks have been sorted accordingly to the +executing platform heterogeneity degree, ordered from the highest mark +to the lowest, this function maps tasks on almost all available +computing nodes of clusters, in their respective order in lists (for +example a task classified first in the tasks list is mapped on an +available node of the cluster classified first in the clusters list). +The idea here is not to fulfill each cluster, but to preserve some +computing nodes in each cluster. These conserved nodes will be used to +replace failed nodes. + + +Here we can mentioned that the whole mapping process (the three steps) +has a complexity of $O( |V| log(|V|) )$, where |V| is the number of tasks. + + +\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 shown in the previous section, during the initial mapping some +computing nodes in each cluster have been preserved. 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 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, as 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, which supports the asynchronous +iterative model. More details about this method can be found in +\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 size, between 8 and 20 neighbors +per tasks. This application was executed on 64 nodes. + + +The platform used for our tests, called Grid’5000\cite{g5k}, is a +French nationwide experimental set of clusters which provides us with +distributed clusters architectures (28 heterogeneous clusters spread +over 9 sites). We used three distributed clusters architectures, 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 +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 did not have 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 execution time, given in brackets. It presents +both the executions with faults (WF) and the fault free (FF) +executions. + +\vspace{-0.25cm} + +\renewcommand{\arraystretch}{1.6} +\begin{table}[h!] + \centering + \begin{tabular}{|c|c|c|c|c|c|c|c|c|} + \hline + \multirow{2}{*}{ ~$hd$~ }&\multicolumn{2}{c|}{ ~Default~ }&\multicolumn{2}{c|}{ ~FT-AIAC-QM~ }&\multicolumn{2}{c|}{ ~FT-FEC~ }&\multicolumn{2}{c|}{ ~MAHEVE~ }\\ + \cline{2-9} + + & ~FF~ & ~WF~ & ~FF~ & ~WF~ & ~FF~ & ~WF~ & ~FF~ & ~WF~ \\ + \hline + ~$0.08$~ & ~80~ & ~229~ & ~63 (21\%)~ & ~178 (22\%)~ & ~61 (23\%)~ & ~154 + (33\%)~ & ~60 (25\%)~ & ~113 (50\%)~ \\ + + ~$0.50$~ & ~67~ & ~242~ & ~61 (9\%)~ & ~118 (51\%)~ & ~63 (6\%)~ & ~133 + (45\%)~ & ~54 (20\%)~ & ~85 (65\%)~ \\ + + ~$0.72$~ & ~67~ & ~192~ & ~59 (12\%)~ & ~99 (45\%)~ & ~65 (3\%)~ & ~121 + (33\%)~ & ~52 (22\%)~ & ~86 (53\%)~\\ + + \hline + \end{tabular} + \vspace{0.15cm} + \caption{Application execution time in seconds and corresponding gains on various + platforms using different mapping algorithms, with fault free (FF) executions + and with 2 node failures each 20 seconds (WF) executions.} + \label{tab:results} + \vspace{-0.7cm} +\end{table} + + +First of all, we can note that all mapping algorithms provide an +enhancement of the application performances by considerably reducing +its execution time, especially for executions with node failures, with +an average gain of about $45\%$ in general in comparison to the +default policy. If we focus on executions with node failures (WF), +FT-FEC is efficient on architectures with a low heterogeneity degree +(\mbox{$hd = 0.08$}) by providing gains of about $33\%$, and gains are +roughly 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 of about +$45\%$, whereas it is not so efficient on homogeneous architectures +(\mbox{$hd = 0.08$}) by providing gains of 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\%$. Here we point out that in fault free executions (FF), both +algorithms also provide gains on their respective favorite +architectures, though gains are less great than in executions with +faults (WF). + + +Now if we focus on 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}}, in executions with faults +(WF), it reduces the application's execution time by about $50\%$ on +homogeneous architectures (here of $0.08$ heterogeneity degree) which +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 execution time by about $53\%$ which is +almost 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 once again better than its two +comparative mapping algorithms by reducing the application 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 execution time of about $55\%$. In fault free executions (FF), it outperforms once again +the two other algorithms. + +\vspace{-0.15cm} +\section{Conclusion and future works} +\label{sec:conclu} + +In this paper we have presented a new mapping algorithm, called +MAHEVE, to address the AIAC mapping issue on heterogeneous and +volatile environments. It aims at doing an efficient mapping of tasks +on distributed clusters architectures by taking the best part of the +two known approaches, application execution time optimization and +edge-cuts minimization. Experiments, though using a single +application, show that it is the most efficient mapping algorithm on +all kinds of architectures, as it takes into account 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, since their +locality has not yet been taken into consideration. This would favor +tasks locality, which would reduce communications delays and provide a +much better convergence rate. We also have to validate the algorithm +performance with other AIAC applications. + + +%% Acknolegdement + +\section*{Acknowledgement} +\label{ack} + +Experiments presented in this paper were carried out using the +Grid'5000 experimental testbed\cite{g5k}, being developed under the +INRIA ALADDIN development action with support from CNRS, RENATER and +several Universities as well as other funding bodies. + +%%% + + +\bibliographystyle{unsrt} + +\bibliography{biblio} + + +\end{document} + diff --git a/heteropar10/camera_ready/images/AIAC.fig b/heteropar10/camera_ready/images/AIAC.fig new file mode 100644 index 0000000..a88b743 --- /dev/null +++ b/heteropar10/camera_ready/images/AIAC.fig @@ -0,0 +1,97 @@ +#FIG 3.2 Produced by xfig version 3.2.5b +Landscape +Center +Inches +Letter +100.00 +Single +-2 +1200 2 +6 525 2550 7800 2775 +2 1 0 1 0 7 50 0 -1 0.000 0 0 -1 1 0 2 + 2 1 2.00 47.08 94.16 + 1176 2691 7766 2691 +4 0 0 50 0 18 12 0.0000 4 150 465 527 2751 Time\001 +-6 +6 2625 1350 6600 1875 +2 1 0 1 0 7 50 0 -1 0.000 0 0 -1 1 0 2 + 2 1 3.00 22.50 46.50 + 6000 1404 6375 1812 +2 1 0 1 0 7 50 0 -1 0.000 0 0 -1 1 0 2 + 2 1 3.00 22.50 46.50 + 4350 1812 5025 1392 +2 1 0 1 0 7 50 0 -1 0.000 0 0 -1 1 0 2 + 2 1 3.00 22.50 46.50 + 3822 1388 4200 1824 +2 1 0 1 0 7 50 0 -1 0.000 0 0 -1 1 0 2 + 2 1 3.00 22.50 46.50 + 2925 1392 3900 1812 +2 1 0 1 0 7 50 0 -1 0.000 0 0 -1 1 0 2 + 2 1 3.00 22.50 46.50 + 2691 1812 3225 1392 +2 1 0 1 0 7 50 0 -1 0.000 0 0 -1 1 0 2 + 2 1 3.00 22.50 46.50 + 3672 1823 3968 1388 +2 1 0 1 0 7 50 0 -1 0.000 0 0 -1 1 0 2 + 2 1 3.00 22.50 46.50 + 4800 1388 5042 1823 +2 1 0 1 0 7 50 0 -1 0.000 0 0 -1 1 0 2 + 2 1 3.00 22.50 46.50 + 5323 1823 5448 1388 +2 1 0 1 0 7 50 0 -1 0.000 0 0 -1 1 0 2 + 2 1 3.00 22.50 46.50 + 6225 1800 6600 1392 +-6 +6 4800 900 7575 1425 +2 1 1 1 0 7 50 0 -1 4.000 0 0 -1 0 0 2 + 6588 1396 7532 1396 +2 1 1 1 0 7 50 0 -1 4.000 0 0 -1 0 0 2 + 6663 900 7547 900 +2 2 0 1 0 7 50 0 8 0.000 0 0 -1 0 0 5 + 4800 900 6000 900 6000 1396 4800 1396 4800 900 +-6 +6 1425 900 6675 1425 +6 1425 900 6600 1425 +6 1950 1073 6600 1223 +4 0 0 49 0 18 12 0.0000 4 150 525 4050 1223 Iter. 3\001 +4 0 0 49 0 18 12 0.0000 4 150 525 5100 1223 Iter. 4\001 +4 0 0 49 0 18 12 0.0000 4 150 525 1950 1223 Iter. 1\001 +4 0 0 49 0 18 12 0.0000 4 150 525 3150 1223 Iter. 2\001 +4 0 0 49 0 18 12 0.0000 4 150 525 6075 1223 Iter. 5\001 +-6 +2 2 0 1 0 7 50 0 17 0.000 0 0 -1 0 0 5 + 1485 900 2925 900 2925 1396 1485 1396 1485 900 +-6 +2 2 0 1 0 7 50 0 14 0.000 0 0 -1 0 0 5 + 6000 900 6675 900 6675 1396 6000 1396 6000 900 +-6 +6 1875 1992 6880 2142 +4 0 0 49 0 18 12 0.0000 4 150 525 1875 2142 Iter. 1\001 +4 0 0 49 0 18 12 0.0000 4 150 525 3764 2142 Iter. 3\001 +4 0 0 49 0 18 12 0.0000 4 150 525 5530 2142 Iter. 5\001 +4 0 0 49 0 18 12 0.0000 4 150 525 6355 2142 Iter. 6\001 +4 0 0 49 0 18 12 0.0000 4 150 525 2925 2142 Iter. 2\001 +4 0 0 49 0 18 12 0.0000 4 150 525 4575 2142 Iter. 4\001 +-6 +2 1 1 1 0 7 50 0 -1 4.000 0 0 -1 0 0 2 + 7001 1810 7532 1810 +2 1 1 1 0 7 50 0 -1 4.000 0 0 -1 0 0 2 + 7001 2325 7532 2325 +2 2 0 1 0 7 50 0 15 0.000 0 0 -1 0 0 5 + 3825 900 4800 900 4800 1396 3825 1396 3825 900 +2 2 0 1 0 7 50 0 12 0.000 0 0 -1 0 0 5 + 2925 900 3825 900 3825 1396 2925 1396 2925 900 +2 2 0 1 0 7 50 0 12 0.000 0 0 -1 0 0 5 + 2700 1810 3704 1810 3704 2325 2700 2325 2700 1810 +2 2 0 1 0 7 50 0 10 0.000 0 0 -1 0 0 5 + 6225 1810 7001 1810 7001 2325 6225 2325 6225 1810 +2 2 0 1 0 7 50 0 15 0.000 0 0 -1 0 0 5 + 3675 1810 4350 1810 4350 2325 3675 2325 3675 1810 +2 2 0 1 0 7 50 0 14 0.000 0 0 -1 0 0 5 + 5325 1810 6225 1810 6225 2325 5325 2325 5325 1810 +2 2 0 1 0 7 50 0 8 0.000 0 0 -1 0 0 5 + 4350 1810 5325 1810 5325 2325 4350 2325 4350 1810 +2 2 0 1 0 7 50 0 17 0.000 0 0 -1 0 0 5 + 1500 1810 2704 1810 2704 2325 1500 2325 1500 1810 +4 0 0 50 0 18 12 0.0000 4 150 1110 225 1200 Processor 1\001 +4 0 0 50 0 18 12 0.0000 4 150 1110 225 2175 Processor 2\001 diff --git a/heteropar10/camera_ready/images/AIAC.pdf b/heteropar10/camera_ready/images/AIAC.pdf new file mode 100755 index 0000000..b7abe32 Binary files /dev/null and b/heteropar10/camera_ready/images/AIAC.pdf differ diff --git a/heteropar10/camera_ready/llncs.cls b/heteropar10/camera_ready/llncs.cls new file mode 100644 index 0000000..1ee2791 --- /dev/null +++ b/heteropar10/camera_ready/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