From: lilia <lilia@amazigh.bordeaux.inria.fr>
Date: Thu, 24 Apr 2014 12:02:50 +0000 (+0200)
Subject: 24-04-2014
X-Git-Tag: hpcc2014_submission~78
X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hpcc2014.git/commitdiff_plain/3759ae5b129885d1156e0f04719879d1ebc481b9?ds=inline

24-04-2014
---

diff --git a/hpcc.tex b/hpcc.tex
index d5be4d4..d9fe798 100644
--- a/hpcc.tex
+++ b/hpcc.tex
@@ -322,19 +322,7 @@ is solved independently by a cluster and communications are required to update t
 \label{algo:01}
 \end{figure}
 
-Algorithm on Figure~\ref{algo:01} shows the main key points of the
-multisplitting method to solve a large sparse linear system. This algorithm is
-based on an outer-inner iteration method where the parallel synchronous GMRES
-method is used to solve the inner iteration. It is executed in parallel by each
-cluster of processors. For all $l,m\in\{1,\ldots,L\}$, the matrices and vectors
-with the subscript $l$ represent the local data for cluster $l$, while
-$\{A_{lm}\}_{m\neq l}$ are off-diagonal matrices of sparse matrix $A$ and
-$\{X_m\}_{m\neq l}$ contain vector elements of solution $x$ shared with
-neighboring clusters. At every outer iteration $k$, asynchronous communications
-are performed between processors of the local cluster and those of distant
-clusters (lines~\ref{algo:01:send} and~\ref{algo:01:recv} in
-Figure~\ref{algo:01}). The shared vector elements of the solution $x$ are
-exchanged by message passing using MPI non-blocking communication routines.
+Algorithm on Figure~\ref{algo:01} shows the main key points of the multisplitting method to solve a large sparse linear system. This algorithm is based on an outer-inner iteration method where the parallel synchronous GMRES method is used to solve the inner iteration. It is executed in parallel by each cluster of processors. For all $l,m\in\{1,\ldots,L\}$, the matrices and vectors with the subscript $l$ represent the local data for cluster $l$, while $\{A_{lm}\}_{m\neq l}$ are off-diagonal matrices of sparse matrix $A$ and $\{X_m\}_{m\neq l}$ contain vector elements of solution $x$ shared with neighboring clusters. At every outer iteration $k$, asynchronous communications are performed between processors of the local cluster and those of distant clusters (lines~\ref{algo:01:send} and~\ref{algo:01:recv} in Figure~\ref{algo:01}). The shared vector elements of the solution $x$ are exchanged by message passing using MPI non-blocking communication routines.
 
 \begin{figure}[!t]
 \centering
@@ -343,21 +331,7 @@ exchanged by message passing using MPI non-blocking communication routines.
 \label{fig:4.1}
 \end{figure}
 
-The global convergence of the asynchronous multisplitting solver is detected
-when the clusters of processors have all converged locally. We implemented the
-global convergence detection process as follows. On each cluster a master
-processor is designated (for example the processor with rank 1) and masters of
-all clusters are interconnected by a virtual unidirectional ring network (see
-Figure~\ref{fig:4.1}). During the resolution, a Boolean token circulates around
-the virtual ring from a master processor to another until the global convergence
-is achieved. So starting from the cluster with rank 1, each master processor $i$
-sets the token to \textit{True} if the local convergence is achieved or to
-\text\it{False} otherwise, and sends it to master processor $i+1$. Finally, the
-global convergence is detected when the master of cluster 1 receives from the
-master of cluster $L$ a token set to \textit{True}. In this case, the master of
-cluster 1 broadcasts a stop message to masters of other clusters. In this work,
-the local convergence on each cluster $l$ is detected when the following
-condition is satisfied
+The global convergence of the asynchronous multisplitting solver is detected when the clusters of processors have all converged locally. We implemented the global convergence detection process as follows. On each cluster a master processor is designated (for example the processor with rank 1) and masters of all clusters are interconnected by a virtual unidirectional ring network (see Figure~\ref{fig:4.1}). During the resolution, a Boolean token circulates around the virtual ring from a master processor to another until the global convergence is achieved. So starting from the cluster with rank 1, each master processor $i$ sets the token to {\it True} if the local convergence is achieved or to {\it False} otherwise, and sends it to master processor $i+1$. Finally, the global convergence is detected when the master of cluster 1 receives from the master of cluster $L$ a token set to {\it True}. In this case, the master of cluster 1 broadcasts a stop message to masters of other clusters. In this work, the local convergence on each cluster $l$ is detected when the following condition is satisfied
 \begin{equation*}
   (k\leq \MI) \text{ or } (\|X_l^k - X_l^{k+1}\|_{\infty}\leq\epsilon)
 \end{equation*}
@@ -398,7 +372,7 @@ study that the results depend on the following parameters:
   experimentation of the simulation in having an execution time in asynchronous
   less than in synchronous mode (i.e. speed-up less than 1).
 \end{itemize}
-\LZK{Propositions pour changer le terme ``speedup'': acceleration ratio ou relative gain}
+\LZK{Propositions pour remplacer le terme ``speedup'': acceleration ratio ou relative gain}
 
 A priori, obtaining a speedup less than 1 would be difficult in a local area
 network configuration where the synchronous mode will take advantage on the
@@ -409,14 +383,45 @@ configuration, degrading the inter-cluster network performance will
 This action simulates the case of clusters linked with long distance network
 like Internet.
 
+In this paper, we solve the 3D Poisson problem whose the mathematical model is 
+\begin{equation}
+\left\{
+\begin{array}{l}
+\nabla^2 u = f \text{~in~} \Omega \\
+u =0 \text{~on~} \Gamma =\partial\Omega
+\end{array}
+\right.
+\label{eq:02}
+\end{equation}
+where $\nabla^2$ is the Laplace operator, $f$ and $u$ are real-valued functions, and $\Omega=[0,1]^3$. The spatial discretization with a finite difference scheme reduces problem~(\ref{eq:02}) to a system of sparse linear equations. The general iteration scheme of our multisplitting method in a 3D domain using a seven point stencil could be written as 
+\begin{equation}
+\begin{array}{ll}
+u^{k+1}(x,y,z)= & u^k(x,y,z) - \frac{1}{6}\times\\
+               & (u^k(x-1,y,z) + u^k(x+1,y,z) + \\
+               & u^k(x,y-1,z) + u^k(x,y+1,z) + \\
+               & u^k(x,y,z-1) + u^k(x,y,z+1)),
+\end{array}
+\label{eq:03}
+\end{equation} 
+where the iteration matrix $A$ of size $N_x\times N_y\times N_z$ of the discretized linear system is sparse, symmetric and positive definite. 
+
+The parallel solving of the 3D Poisson problem with our multisplitting method requires a data partitioning of the problem between clusters and between processors within a cluster. We have choose the 3D partitioning instead of the row-by-row partitioning in order to reduce the data exchanges at sub-domain boundaries. Figure~\ref{fig:4.2} shows an example of the data partitioning of the 3D Poisson problem between two clusters of processors, where each sub-problem is assigned to a processor. In this context, a processor has at most six neighbors within a cluster of in distant clusters with which it shares data at sub-domain boundaries. 
+
+\begin{figure}[!t]
+\centering
+  \includegraphics[width=80mm,keepaspectratio]{partition}
+\caption{Example of the 3D data partitioning between two clusters of processors.}
+\label{fig:4.2}
+\end{figure}
+
+
 As a first step, the algorithm was run on a network consisting of two clusters
 containing 50 hosts each, totaling 100 hosts. Various combinations of the above
 factors have providing the results shown in Table~\ref{tab.cluster.2x50} with a
 matrix size ranging from $N_x = N_y = N_z = \text{62}$ to 171 elements or from
 $\text{62}^\text{3} = \text{\np{238328}}$ to $\text{171}^\text{3} =
 \text{\np{5211000}}$ entries.
-\CER{Voir ma remarque plus si nécessaire de décrire en détail le partitionnement 3D}
-\LZK{Je pense qu'il faut donner ici le type du problème traité (Poisson 3D). Le partitionnement 3D permet juste de définir le schéma de dépendances (1 proc a au max 6 voisins dans le cluster local ou dans les clusters distants)}
+
 % use the same column width for the following three tables
 \newlength{\mytablew}\settowidth{\mytablew}{\footnotesize\np{E-11}}
 \newenvironment{mytable}[1]{% #1: number of columns for data
diff --git a/partition.eps b/partition.eps
new file mode 100644
index 0000000..1f78d84
--- /dev/null
+++ b/partition.eps
@@ -0,0 +1,383 @@
+%!PS-Adobe-3.0 EPSF-3.0
+%%Title: partition.fig
+%%Creator: fig2dev Version 3.2 Patchlevel 5e
+%%CreationDate: Thu Apr 24 13:53:32 2014
+%%BoundingBox: 0 0 550 346
+%Magnification: 1.0000
+%%EndComments
+%%BeginProlog
+/$F2psDict 200 dict def
+$F2psDict begin
+$F2psDict /mtrx matrix put
+/col-1 {0 setgray} bind def
+/col0 {0.000 0.000 0.000 srgb} bind def
+/col1 {0.000 0.000 1.000 srgb} bind def
+/col2 {0.000 1.000 0.000 srgb} bind def
+/col3 {0.000 1.000 1.000 srgb} bind def
+/col4 {1.000 0.000 0.000 srgb} bind def
+/col5 {1.000 0.000 1.000 srgb} bind def
+/col6 {1.000 1.000 0.000 srgb} bind def
+/col7 {1.000 1.000 1.000 srgb} bind def
+/col8 {0.000 0.000 0.560 srgb} bind def
+/col9 {0.000 0.000 0.690 srgb} bind def
+/col10 {0.000 0.000 0.820 srgb} bind def
+/col11 {0.530 0.810 1.000 srgb} bind def
+/col12 {0.000 0.560 0.000 srgb} bind def
+/col13 {0.000 0.690 0.000 srgb} bind def
+/col14 {0.000 0.820 0.000 srgb} bind def
+/col15 {0.000 0.560 0.560 srgb} bind def
+/col16 {0.000 0.690 0.690 srgb} bind def
+/col17 {0.000 0.820 0.820 srgb} bind def
+/col18 {0.560 0.000 0.000 srgb} bind def
+/col19 {0.690 0.000 0.000 srgb} bind def
+/col20 {0.820 0.000 0.000 srgb} bind def
+/col21 {0.560 0.000 0.560 srgb} bind def
+/col22 {0.690 0.000 0.690 srgb} bind def
+/col23 {0.820 0.000 0.820 srgb} bind def
+/col24 {0.500 0.190 0.000 srgb} bind def
+/col25 {0.630 0.250 0.000 srgb} bind def
+/col26 {0.750 0.380 0.000 srgb} bind def
+/col27 {1.000 0.500 0.500 srgb} bind def
+/col28 {1.000 0.630 0.630 srgb} bind def
+/col29 {1.000 0.750 0.750 srgb} bind def
+/col30 {1.000 0.880 0.880 srgb} bind def
+/col31 {1.000 0.840 0.000 srgb} bind def
+/col32 {0.757 0.745 0.718 srgb} bind def
+/col33 {0.608 0.608 0.608 srgb} bind def
+
+end
+
+/cp {closepath} bind def
+/ef {eofill} bind def
+/gr {grestore} bind def
+/gs {gsave} bind def
+/sa {save} bind def
+/rs {restore} bind def
+/l {lineto} bind def
+/m {moveto} bind def
+/rm {rmoveto} bind def
+/n {newpath} bind def
+/s {stroke} bind def
+/sh {show} bind def
+/slc {setlinecap} bind def
+/slj {setlinejoin} bind def
+/slw {setlinewidth} bind def
+/srgb {setrgbcolor} bind def
+/rot {rotate} bind def
+/sc {scale} bind def
+/sd {setdash} bind def
+/ff {findfont} bind def
+/sf {setfont} bind def
+/scf {scalefont} bind def
+/sw {stringwidth} bind def
+/tr {translate} bind def
+/tnt {dup dup currentrgbcolor
+  4 -2 roll dup 1 exch sub 3 -1 roll mul add
+  4 -2 roll dup 1 exch sub 3 -1 roll mul add
+  4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb}
+  bind def
+/shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul
+  4 -2 roll mul srgb} bind def
+/reencdict 12 dict def /ReEncode { reencdict begin
+/newcodesandnames exch def /newfontname exch def /basefontname exch def
+/basefontdict basefontname findfont def /newfont basefontdict maxlength dict def
+basefontdict { exch dup /FID ne { dup /Encoding eq
+{ exch dup length array copy newfont 3 1 roll put }
+{ exch newfont 3 1 roll put } ifelse } { pop pop } ifelse } forall
+newfont /FontName newfontname put newcodesandnames aload pop
+128 1 255 { newfont /Encoding get exch /.notdef put } for
+newcodesandnames length 2 idiv { newfont /Encoding get 3 1 roll put } repeat
+newfontname newfont definefont pop end } def
+/isovec [
+8#055 /minus 8#200 /grave 8#201 /acute 8#202 /circumflex 8#203 /tilde
+8#204 /macron 8#205 /breve 8#206 /dotaccent 8#207 /dieresis
+8#210 /ring 8#211 /cedilla 8#212 /hungarumlaut 8#213 /ogonek 8#214 /caron
+8#220 /dotlessi 8#230 /oe 8#231 /OE
+8#240 /space 8#241 /exclamdown 8#242 /cent 8#243 /sterling
+8#244 /currency 8#245 /yen 8#246 /brokenbar 8#247 /section 8#250 /dieresis
+8#251 /copyright 8#252 /ordfeminine 8#253 /guillemotleft 8#254 /logicalnot
+8#255 /hyphen 8#256 /registered 8#257 /macron 8#260 /degree 8#261 /plusminus
+8#262 /twosuperior 8#263 /threesuperior 8#264 /acute 8#265 /mu 8#266 /paragraph
+8#267 /periodcentered 8#270 /cedilla 8#271 /onesuperior 8#272 /ordmasculine
+8#273 /guillemotright 8#274 /onequarter 8#275 /onehalf
+8#276 /threequarters 8#277 /questiondown 8#300 /Agrave 8#301 /Aacute
+8#302 /Acircumflex 8#303 /Atilde 8#304 /Adieresis 8#305 /Aring
+8#306 /AE 8#307 /Ccedilla 8#310 /Egrave 8#311 /Eacute
+8#312 /Ecircumflex 8#313 /Edieresis 8#314 /Igrave 8#315 /Iacute
+8#316 /Icircumflex 8#317 /Idieresis 8#320 /Eth 8#321 /Ntilde 8#322 /Ograve
+8#323 /Oacute 8#324 /Ocircumflex 8#325 /Otilde 8#326 /Odieresis 8#327 /multiply
+8#330 /Oslash 8#331 /Ugrave 8#332 /Uacute 8#333 /Ucircumflex
+8#334 /Udieresis 8#335 /Yacute 8#336 /Thorn 8#337 /germandbls 8#340 /agrave
+8#341 /aacute 8#342 /acircumflex 8#343 /atilde 8#344 /adieresis 8#345 /aring
+8#346 /ae 8#347 /ccedilla 8#350 /egrave 8#351 /eacute
+8#352 /ecircumflex 8#353 /edieresis 8#354 /igrave 8#355 /iacute
+8#356 /icircumflex 8#357 /idieresis 8#360 /eth 8#361 /ntilde 8#362 /ograve
+8#363 /oacute 8#364 /ocircumflex 8#365 /otilde 8#366 /odieresis 8#367 /divide
+8#370 /oslash 8#371 /ugrave 8#372 /uacute 8#373 /ucircumflex
+8#374 /udieresis 8#375 /yacute 8#376 /thorn 8#377 /ydieresis] def
+/Times-Roman /Times-Roman-iso isovec ReEncode
+/Times-Italic /Times-Italic-iso isovec ReEncode
+/$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def
+/$F2psEnd {$F2psEnteredState restore end} def
+
+/pageheader {
+save
+newpath 0 346 moveto 0 0 lineto 550 0 lineto 550 346 lineto closepath clip newpath
+-203.1 457.3 translate
+1 -1 scale
+$F2psBegin
+10 setmiterlimit
+0 slj 0 slc
+ 0.06299 0.06299 sc
+} bind def
+/pagefooter {
+$F2psEnd
+restore
+} bind def
+%%EndProlog
+pageheader
+%
+% Fig objects follow
+%
+% 
+% here starts figure with depth 50
+% Polyline
+0 slj
+0 slc
+15.000 slw
+n 9000 2700 m 10350 2700 l 11250 1800 l 9450 1800 l 8550 1800 l 7650 2700 l
+
+ cp gs col32 1.00 shd ef gr gs col0 s gr 
+% Polyline
+n 10350 4095 m 10350 5400 l 11250 4500 l 11250 1800 l 10350 2700 l 10350 5400 l
+
+ cp gs col32 1.00 shd ef gr gs col0 s gr 
+% Polyline
+n 7650 2700 m 10350 2700 l 10350 5400 l 7650 5400 l
+ cp gs col32 1.00 shd ef gr gs col0 s gr 
+% Polyline
+n 7650 3600 m
+ 10350 3600 l gs col0 s gr 
+% Polyline
+n 7650 4500 m
+ 10350 4500 l gs col0 s gr 
+% Polyline
+n 8550 2700 m
+ 8550 5400 l gs col0 s gr 
+% Polyline
+n 9450 2700 m
+ 9450 5400 l gs col0 s gr 
+% Polyline
+n 8550 2700 m
+ 9450 1800 l gs col0 s gr 
+% Polyline
+n 9450 2700 m
+ 10350 1800 l gs col0 s gr 
+% Polyline
+n 10350 3600 m
+ 11250 2700 l gs col0 s gr 
+% Polyline
+n 10350 4500 m
+ 11250 3600 l gs col0 s gr 
+% Polyline
+n 10800 2250 m
+ 10800 4950 l gs col0 s gr 
+% Polyline
+n 8100 2250 m
+ 10800 2250 l gs col0 s gr 
+% Polyline
+n 7695 4365 m 7695 3465 l 7245 3915 l 7245 4815 l
+ cp gs col33 1.00 shd ef gr gs col0 s gr 
+% Polyline
+n 8595 4365 m 7695 4365 l 7245 4815 l 8145 4815 l
+ cp gs col33 1.00 shd ef gr gs col0 s gr 
+% Polyline
+n 7695 3465 m 8595 3465 l 8595 4365 l 7695 4365 l
+ cp gs col33 1.00 shd ef gr gs col0 s gr 
+% Polyline
+n 9045 3015 m 8145 3015 l 7695 3465 l 8145 3465 l 8595 3465 l
+ cp gs col32 1.00 shd ef gr gs col0 s gr 
+% Polyline
+n 9045 3915 m 9045 3015 l 8595 3465 l 8595 4365 l
+ cp gs col32 1.00 shd ef gr gs col0 s gr 
+% Polyline
+n 9045 3915 m 8145 4815 l 8145 6615 l 9045 5715 l 9045 4815 l
+ cp gs col32 1.00 shd ef gr gs col0 s gr 
+% Polyline
+n 8145 5715 m
+ 9045 4815 l gs col0 s gr 
+% Polyline
+n 8595 4365 m
+ 8595 6165 l gs col0 s gr 
+% Polyline
+n 8145 3015 m 7290 3015 l 6345 3015 l 5445 3915 l 7245 3915 l
+ cp gs col32 1.00 shd ef gr gs col0 s gr 
+% Polyline
+n 5895 3465 m
+ 7695 3465 l gs col0 s gr 
+% Polyline
+n 6367 3893 m
+ 7245 3015 l gs col0 s gr 
+% Polyline
+n 5445 3915 m 7245 3915 l 7245 6615 l 5445 6615 l
+ cp gs col32 1.00 shd ef gr gs col0 s gr 
+% Polyline
+n 7245 4815 m 8145 4815 l 8145 6615 l 7245 6615 l
+ cp gs col32 1.00 shd ef gr gs col0 s gr 
+% Polyline
+n 5445 5715 m
+ 8145 5715 l gs col0 s gr 
+% Polyline
+n 5445 4815 m
+ 7245 4815 l gs col0 s gr 
+% Polyline
+n 6345 3915 m
+ 6345 6615 l gs col0 s gr 
+% Polyline
+gs  clippath
+8188 4122 m 8061 3948 l 7940 4037 l 8067 4211 l 8067 4211 l 8022 4022 l 8188 4122 l cp
+eoclip
+n 8010 4005 m 9495 6030 l
+ 10125 6030 l gs col0 s gr gr
+
+% arrowhead
+n 8188 4122 m 8022 4022 l 8067 4211 l  col0 s
+% Polyline
+gs  clippath
+7664 4051 m 7513 3896 l 7405 4001 l 7557 4156 l 7557 4156 l 7485 3975 l 7664 4051 l cp
+eoclip
+n 9495 6030 m
+ 7470 3960 l gs col0 s gr gr
+
+% arrowhead
+n 7664 4051 m 7485 3975 l 7557 4156 l  col0 s
+% Polyline
+gs  clippath
+7987 4659 m 7820 4522 l 7725 4638 l 7892 4775 l 7892 4775 l 7801 4603 l 7987 4659 l cp
+eoclip
+n 9540 6030 m
+ 7785 4590 l gs col0 s gr gr
+
+% arrowhead
+n 7987 4659 m 7801 4603 l 7892 4775 l  col0 s
+% Polyline
+gs  clippath
+7724 2340 m 7877 2493 l 7983 2387 l 7830 2234 l 7830 2234 l 7905 2415 l 7724 2340 l cp
+eoclip
+n 7920 2430 m 7470 1980 l
+ 6795 1980 l gs col0 s gr gr
+
+% arrowhead
+n 7724 2340 m 7905 2415 l 7830 2234 l  col0 s
+% Polyline
+gs  clippath
+5530 3521 m 5683 3674 l 5789 3568 l 5636 3415 l 5636 3415 l 5711 3596 l 5530 3521 l cp
+eoclip
+n 5726 3611 m 5276 3161 l
+ 4601 3161 l gs col0 s gr gr
+
+% arrowhead
+n 5530 3521 m 5711 3596 l 5636 3415 l  col0 s
+% Polyline
+n 8505 3915 m 9405 3915 l 9405 4815 l 8505 4815 l
+ cp gs col32 1.00 shd ef gr gs col0 s gr 
+% Polyline
+n 9405 3915 m 9585 3735 l 9855 3465 l 9405 3465 l 8955 3465 l 8516 3902 l
+
+ cp gs col32 1.00 shd ef gr gs col0 s gr 
+% Polyline
+n 9405 4815 m 9855 4365 l 9855 3915 l 9855 3465 l 9405 3915 l 9405 4365 l
+
+ cp gs col32 1.00 shd ef gr gs col0 s gr 
+% Polyline
+gs  clippath
+8880 6292 m 8880 6105 l 8760 6105 l 8760 6292 l 8760 6292 l 8820 6142 l 8880 6292 l cp
+eoclip
+n 8820 6120 m
+ 8820 7020 l gs col0 s gr gr
+
+% arrowhead
+n 8880 6292 m 8820 6142 l 8760 6292 l  col0 s
+% Polyline
+gs  clippath
+9191 6733 m 9323 6601 l 9238 6516 l 9106 6648 l 9106 6648 l 9255 6585 l 9191 6733 l cp
+eoclip
+n 8820 7020 m
+ 9270 6570 l gs col0 s gr gr
+
+% arrowhead
+n 9191 6733 m 9255 6585 l 9106 6648 l  col0 s
+% Polyline
+gs  clippath
+9548 7080 m 9735 7080 l 9735 6960 l 9548 6960 l 9548 6960 l 9698 7020 l 9548 7080 l cp
+eoclip
+n 8820 7020 m
+ 9720 7020 l gs col0 s gr gr
+
+% arrowhead
+n 9548 7080 m 9698 7020 l 9548 6960 l  col0 s
+/Times-Roman-iso ff 349.25 scf sf
+9630 5085 m
+gs 1 -1 sc (P21) col0 sh gr
+/Times-Roman-iso ff 349.25 scf sf
+9630 3285 m
+gs 1 -1 sc (P27) col0 sh gr
+/Times-Roman-iso ff 349.25 scf sf
+9855 4185 m
+gs 1 -1 sc (24) col0 sh gr
+/Times-Roman-iso ff 349.25 scf sf
+7830 4050 m
+gs 1 -1 sc (P18) col0 sh gr
+/Times-Roman-iso ff 349.25 scf sf
+5670 6300 m
+gs 1 -1 sc (P1) col0 sh gr
+/Times-Roman-iso ff 349.25 scf sf
+6615 6300 m
+gs 1 -1 sc (P2) col0 sh gr
+/Times-Roman-iso ff 349.25 scf sf
+7515 6300 m
+gs 1 -1 sc (P3) col0 sh gr
+/Times-Roman-iso ff 349.25 scf sf
+5670 5400 m
+gs 1 -1 sc (P4) col0 sh gr
+/Times-Roman-iso ff 349.25 scf sf
+6570 5400 m
+gs 1 -1 sc (P5) col0 sh gr
+/Times-Roman-iso ff 349.25 scf sf
+7470 5400 m
+gs 1 -1 sc (P6) col0 sh gr
+/Times-Roman-iso ff 349.25 scf sf
+5670 4545 m
+gs 1 -1 sc (P7) col0 sh gr
+/Times-Roman-iso ff 349.25 scf sf
+6570 4590 m
+gs 1 -1 sc (P8) col0 sh gr
+/Times-Roman-iso ff 349.25 scf sf
+10080 5850 m
+gs 1 -1 sc (Sub-domain) col0 sh gr
+/Times-Roman-iso ff 349.25 scf sf
+10215 6165 m
+gs 1 -1 sc (boundaries) col0 sh gr
+/Times-Roman-iso ff 349.25 scf sf
+5400 2070 m
+gs 1 -1 sc (Cluster 2) col0 sh gr
+/Times-Roman-iso ff 349.25 scf sf
+3240 3240 m
+gs 1 -1 sc (Cluster 1) col0 sh gr
+/Times-Roman-iso ff 349.25 scf sf
+8730 4500 m
+gs 1 -1 sc (P9) col0 sh gr
+/Times-Italic-iso ff 317.50 scf sf
+8595 6705 m
+gs 1 -1 sc (y) col0 sh gr
+/Times-Italic-iso ff 317.50 scf sf
+9225 6885 m
+gs 1 -1 sc (z) col0 sh gr
+/Times-Italic-iso ff 317.50 scf sf
+9090 7245 m
+gs 1 -1 sc (x) col0 sh gr
+% here ends figure;
+pagefooter
+showpage
+%%Trailer
+%EOF
diff --git a/partition.fig b/partition.fig
new file mode 100644
index 0000000..5beded0
--- /dev/null
+++ b/partition.fig
@@ -0,0 +1,137 @@
+#FIG 3.2  Produced by xfig version 3.2.5c
+Landscape
+Center
+Metric
+A4      
+100.00
+Single
+-2
+1200 2
+0 32 #c1beb7
+0 33 #9b9b9b
+6 3240 1755 11925 6660
+6 7605 1755 11295 5445
+2 3 0 2 0 32 50 -1 20 0.000 0 0 0 0 0 7
+	 9000 2700 10350 2700 11250 1800 9450 1800 8550 1800 7650 2700
+	 9000 2700
+2 3 0 2 0 32 50 -1 20 0.000 0 0 0 0 0 7
+	 10350 4095 10350 5400 11250 4500 11250 1800 10350 2700 10350 5400
+	 10350 4095
+2 2 0 2 0 32 50 -1 20 0.000 0 0 -1 0 0 5
+	 7650 2700 10350 2700 10350 5400 7650 5400 7650 2700
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 7650 3600 10350 3600
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 7650 4500 10350 4500
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 8550 2700 8550 5400
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 9450 2700 9450 5400
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 8550 2700 9450 1800
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 9450 2700 10350 1800
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 10350 3600 11250 2700
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 10350 4500 11250 3600
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 10800 2250 10800 4950
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 8100 2250 10800 2250
+4 0 0 50 -1 0 22 0.0000 4 255 585 9630 5085 P21\001
+4 0 0 50 -1 0 22 0.0000 4 255 585 9630 3285 P27\001
+4 0 0 50 -1 0 22 0.0000 4 255 360 9855 4185 24\001
+-6
+6 5400 2970 9090 6660
+6 5400 2970 9090 6660
+2 3 0 2 0 33 50 -1 20 0.000 0 0 0 0 0 5
+	 7695 4365 7695 3465 7245 3915 7245 4815 7695 4365
+2 3 0 2 0 33 50 -1 20 0.000 0 0 0 0 0 5
+	 8595 4365 7695 4365 7245 4815 8145 4815 8595 4365
+2 2 0 2 0 33 50 -1 20 0.000 0 0 -1 0 0 5
+	 7695 3465 8595 3465 8595 4365 7695 4365 7695 3465
+2 3 0 2 0 32 50 -1 20 0.000 0 0 0 0 0 6
+	 9045 3015 8145 3015 7695 3465 8145 3465 8595 3465 9045 3015
+2 3 0 2 0 32 50 -1 20 0.000 0 0 0 0 0 5
+	 9045 3915 9045 3015 8595 3465 8595 4365 9045 3915
+2 3 0 2 0 32 50 -1 20 0.000 0 0 0 0 0 6
+	 9045 3915 8145 4815 8145 6615 9045 5715 9045 4815 9045 3915
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 8145 5715 9045 4815
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 8595 4365 8595 6165
+2 3 0 2 0 32 50 -1 20 0.000 0 0 0 0 0 6
+	 8145 3015 7290 3015 6345 3015 5445 3915 7245 3915 8145 3015
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 5895 3465 7695 3465
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 6367 3893 7245 3015
+2 2 0 2 0 32 50 -1 20 0.000 0 0 -1 0 0 5
+	 5445 3915 7245 3915 7245 6615 5445 6615 5445 3915
+2 2 0 2 0 32 50 -1 20 0.000 0 0 -1 0 0 5
+	 7245 4815 8145 4815 8145 6615 7245 6615 7245 4815
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 5445 5715 8145 5715
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 5445 4815 7245 4815
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 6345 3915 6345 6615
+4 0 0 50 -1 0 22 0.0000 4 255 585 7830 4050 P18\001
+4 0 0 50 -1 0 22 0.0000 4 255 405 5670 6300 P1\001
+4 0 0 50 -1 0 22 0.0000 4 255 405 6615 6300 P2\001
+4 0 0 50 -1 0 22 0.0000 4 255 405 7515 6300 P3\001
+4 0 0 50 -1 0 22 0.0000 4 255 405 5670 5400 P4\001
+4 0 0 50 -1 0 22 0.0000 4 255 405 6570 5400 P5\001
+4 0 0 50 -1 0 22 0.0000 4 255 405 7470 5400 P6\001
+4 0 0 50 -1 0 22 0.0000 4 255 405 5670 4545 P7\001
+4 0 0 50 -1 0 22 0.0000 4 255 405 6570 4590 P8\001
+-6
+-6
+6 7425 3915 11925 6165
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 1 3
+	0 0 2.00 150.00 180.00
+	 8010 4005 9495 6030 10125 6030
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
+	0 0 2.00 150.00 180.00
+	 9495 6030 7470 3960
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
+	0 0 2.00 150.00 180.00
+	 9540 6030 7785 4590
+4 0 0 50 -1 0 22 0.0000 4 255 1815 10080 5850 Sub-domain\001
+4 0 0 50 -1 0 22 0.0000 4 255 1620 10215 6165 boundaries\001
+-6
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 1 3
+	0 0 2.00 150.00 180.00
+	 7920 2430 7470 1980 6795 1980
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 1 3
+	0 0 2.00 150.00 180.00
+	 5726 3611 5276 3161 4601 3161
+4 0 0 50 -1 0 22 0.0000 4 255 1335 5400 2070 Cluster 2\001
+4 0 0 50 -1 0 22 0.0000 4 255 1335 3240 3240 Cluster 1\001
+-6
+6 8460 3420 9900 4860
+2 2 0 2 0 32 50 -1 20 0.000 0 0 -1 0 0 5
+	 8505 3915 9405 3915 9405 4815 8505 4815 8505 3915
+2 3 0 2 0 32 50 -1 20 0.000 0 0 0 0 0 7
+	 9405 3915 9585 3735 9855 3465 9405 3465 8955 3465 8516 3902
+	 9405 3915
+2 3 0 2 0 32 50 -1 20 0.000 0 0 0 0 0 7
+	 9405 4815 9855 4365 9855 3915 9855 3465 9405 3915 9405 4365
+	 9405 4815
+4 0 0 50 -1 0 22 0.0000 4 255 405 8730 4500 P9\001
+-6
+6 8595 6075 9765 7245
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 1 2
+	0 0 2.00 120.00 150.00
+	 8820 6120 8820 7020
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
+	0 0 2.00 120.00 150.00
+	 8820 7020 9270 6570
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
+	0 0 2.00 120.00 150.00
+	 8820 7020 9720 7020
+4 0 0 50 -1 1 20 0.0000 4 225 135 8595 6705 y\001
+4 0 0 50 -1 1 20 0.0000 4 150 120 9225 6885 z\001
+4 0 0 50 -1 1 20 0.0000 4 150 135 9090 7245 x\001
+-6
diff --git a/partition.fig.bak b/partition.fig.bak
new file mode 100644
index 0000000..82f9aef
--- /dev/null
+++ b/partition.fig.bak
@@ -0,0 +1,135 @@
+#FIG 3.2  Produced by xfig version 3.2.5c
+Landscape
+Center
+Metric
+A4      
+100.00
+Single
+-2
+1200 2
+0 32 #c1beb7
+0 33 #9b9b9b
+6 1530 8730 2700 9900
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 1 2
+	0 0 2.00 120.00 150.00
+	 1755 8775 1755 9675
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
+	0 0 2.00 120.00 150.00
+	 1755 9675 2205 9225
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
+	0 0 2.00 120.00 150.00
+	 1755 9675 2655 9675
+4 0 0 50 -1 1 20 0.0000 4 225 135 1530 9360 y\001
+4 0 0 50 -1 1 20 0.0000 4 150 120 2160 9540 z\001
+4 0 0 50 -1 1 20 0.0000 4 150 135 2025 9900 x\001
+-6
+6 7605 1755 11295 5445
+2 3 0 2 0 32 50 -1 20 0.000 0 0 0 0 0 7
+	 9000 2700 10350 2700 11250 1800 9450 1800 8550 1800 7650 2700
+	 9000 2700
+2 3 0 2 0 32 50 -1 20 0.000 0 0 0 0 0 7
+	 10350 4095 10350 5400 11250 4500 11250 1800 10350 2700 10350 5400
+	 10350 4095
+2 2 0 2 0 32 50 -1 20 0.000 0 0 -1 0 0 5
+	 7650 2700 10350 2700 10350 5400 7650 5400 7650 2700
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 7650 3600 10350 3600
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 7650 4500 10350 4500
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 8550 2700 8550 5400
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 9450 2700 9450 5400
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 8550 2700 9450 1800
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 9450 2700 10350 1800
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 10350 3600 11250 2700
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 10350 4500 11250 3600
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 10800 2250 10800 4950
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 8100 2250 10800 2250
+4 0 0 50 -1 0 22 0.0000 4 255 585 9630 5085 P21\001
+4 0 0 50 -1 0 22 0.0000 4 255 585 9630 3285 P27\001
+4 0 0 50 -1 0 22 0.0000 4 255 360 9855 4185 24\001
+-6
+6 5400 2970 9090 6660
+6 5400 2970 9090 6660
+2 3 0 2 0 33 50 -1 20 0.000 0 0 0 0 0 5
+	 7695 4365 7695 3465 7245 3915 7245 4815 7695 4365
+2 3 0 2 0 33 50 -1 20 0.000 0 0 0 0 0 5
+	 8595 4365 7695 4365 7245 4815 8145 4815 8595 4365
+2 2 0 2 0 33 50 -1 20 0.000 0 0 -1 0 0 5
+	 7695 3465 8595 3465 8595 4365 7695 4365 7695 3465
+2 3 0 2 0 32 50 -1 20 0.000 0 0 0 0 0 6
+	 9045 3015 8145 3015 7695 3465 8145 3465 8595 3465 9045 3015
+2 3 0 2 0 32 50 -1 20 0.000 0 0 0 0 0 5
+	 9045 3915 9045 3015 8595 3465 8595 4365 9045 3915
+2 3 0 2 0 32 50 -1 20 0.000 0 0 0 0 0 6
+	 9045 3915 8145 4815 8145 6615 9045 5715 9045 4815 9045 3915
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 8145 5715 9045 4815
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 8595 4365 8595 6165
+2 3 0 2 0 32 50 -1 20 0.000 0 0 0 0 0 6
+	 8145 3015 7290 3015 6345 3015 5445 3915 7245 3915 8145 3015
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 5895 3465 7695 3465
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 6367 3893 7245 3015
+2 2 0 2 0 32 50 -1 20 0.000 0 0 -1 0 0 5
+	 5445 3915 7245 3915 7245 6615 5445 6615 5445 3915
+2 2 0 2 0 32 50 -1 20 0.000 0 0 -1 0 0 5
+	 7245 4815 8145 4815 8145 6615 7245 6615 7245 4815
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 5445 5715 8145 5715
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 5445 4815 7245 4815
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 6345 3915 6345 6615
+4 0 0 50 -1 0 22 0.0000 4 255 585 7830 4050 P18\001
+4 0 0 50 -1 0 22 0.0000 4 255 405 5670 6300 P1\001
+4 0 0 50 -1 0 22 0.0000 4 255 405 6615 6300 P2\001
+4 0 0 50 -1 0 22 0.0000 4 255 405 7515 6300 P3\001
+4 0 0 50 -1 0 22 0.0000 4 255 405 5670 5400 P4\001
+4 0 0 50 -1 0 22 0.0000 4 255 405 6570 5400 P5\001
+4 0 0 50 -1 0 22 0.0000 4 255 405 7470 5400 P6\001
+4 0 0 50 -1 0 22 0.0000 4 255 405 5670 4545 P7\001
+4 0 0 50 -1 0 22 0.0000 4 255 405 6570 4590 P8\001
+-6
+-6
+6 8460 3375 9900 4815
+2 2 0 2 0 32 50 -1 20 0.000 0 0 -1 0 0 5
+	 8505 3870 9405 3870 9405 4770 8505 4770 8505 3870
+2 3 0 2 0 32 50 -1 20 0.000 0 0 0 0 0 7
+	 9405 3870 9585 3690 9855 3420 9405 3420 8955 3420 8516 3857
+	 9405 3870
+2 3 0 2 0 32 50 -1 20 0.000 0 0 0 0 0 7
+	 9405 4770 9855 4320 9855 3870 9855 3420 9405 3870 9405 4320
+	 9405 4770
+4 0 0 50 -1 0 22 0.0000 4 255 405 8730 4455 P9\001
+-6
+6 7425 3915 11925 6165
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 1 3
+	0 0 2.00 150.00 180.00
+	 8010 4005 9495 6030 10125 6030
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
+	0 0 2.00 150.00 180.00
+	 9495 6030 7470 3960
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
+	0 0 2.00 150.00 180.00
+	 9540 6030 7785 4590
+4 0 0 50 -1 0 22 0.0000 4 255 1815 10080 5850 Sub-domain\001
+4 0 0 50 -1 0 22 0.0000 4 255 1620 10215 6165 boundaries\001
+-6
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 1 3
+	0 0 2.00 150.00 180.00
+	 2542 7155 2092 6705 1417 6705
+2 1 0 2 0 7 50 -1 -1 0.000 0 0 -1 0 1 3
+	0 0 2.00 150.00 180.00
+	 3600 7425 3150 6975 2475 6975
+4 0 0 50 -1 0 22 0.0000 4 255 1335 2160 8550 Cluster 1\001
+4 0 0 50 -1 0 22 0.0000 4 255 1335 945 6390 Cluster 2\001
diff --git a/partition.pdf b/partition.pdf
new file mode 100644
index 0000000..fadaa54
Binary files /dev/null and b/partition.pdf differ