#!/bin/bash 

# ---------------------------------------------------------------------
#
#                      process's mapping
#                      ***********************
# 
#   PURPOSE :
#   ---------
#             The execution time si also influenced by the internode 
#             communications and by the memory contention between parallel MPI tasks. 
#             This program aims at creating a suitable map of the MPI processes 
#             to the computing NODE according to different mapping strategies. 
#             It acts only on the local scheduler configuration and does not modify 
#             the parallel algorithm neither the domain decomposition.
#             The following strategies have been implemented:

#                - com:  the mapping will reduce the internode communications. The 
#                        communication pattern defines a graph where each vertex 
#                        represents an MPI task and an edge is a communication between 
#                        two tasks. The mapping is obtained by partitioning the graph 
#                        in a number of subgraph equal to the number of computing nodes; 
#                        the partitioning minimizes the total number of cutting edges.

#                - mem:  the mapping will reduce the memory contention between processes 
#                        by evenly distributing the total amount of allocated memory 
#                        among the computing nodes. The amount of memory allocated in a 
#                        computing node is equal to the memory allocated in the other 
#                        nodes.

#                - away: a process will not be mapped to the same node of any of 
#                        its neighbours

#   INPUT :
#   -------------

#        This script requires the following external package: 
#         - scotch library: http://www.labri.fr/perso/pelegrin/scotch/ (for the com mapping)
#         - the file "background.png" (that can be extracted from the bathimetry) to visualize the mapping
         
#        npart: number of partitions i.e. number of nodes  
         
#        processes layout: the file reports how the MPI processes are disposed on the 
#                          parallel subdomains. This file is an output of the 
#                          "cmcc_mppopt_showproc" script (matrix.in)
                           
#        processes coordinates: the file reports the cartesian coordinates of the 
#                               processes subdomain. It is used for the visualization. 
#                               The file is an output of the 
#                               "cmcc_mppopt_showproc" script ( typical name: <confname>-<decomposition>_<num_sub_domain> example: nemo025-019x045_672 )

#        number of ocean points: this file reports for each subdomain the number of ocean points 
#                                and an estimation of the amount of memory required for 
#                                each subdomain. The file is an output of the 
#                                "cmcc_mpp_optimizer" script with extension *.layout
                 

#    MODIFICATIONS:
#    --------------
#        v1.0: Nov 2014 (I.Epicoco, F.Macchia - CMCC)
# ----------------------------------------------------------------------


#Warning !!!
# check $procxnode variable that must be set to the number of cores per node. 
# It also represents the cardinality of each partition

procxnode=16


echo "Usage: partition.sh <proc layout file> <num partitions> <coordinates file> <num ocean point file> <type_of_mapping: {mem, comm, away}>"

matrix=$1
#matrix="matrix.in"

#check for the processes layout file 
if [ ! -f $matrix ]; then
  echo "file with process layout not found"
  exit 1
fi

maptype=$5
if [ -z $maptype ]; then
  maptype="comm"
fi
npart=$2
#npart=21

gridfile=$3
#gridfile="./nemo116-019x045_672"

#check the process coordinate file
if [ ! -f $gridfile ]; then
  echo "processes coordinates file not found"
  exit 1
fi

layoutfile=$4
#layoutfile="./0672_CMCC.layout"

#check the .layout
if [ ! -f $layoutfile ]; then
  echo "num ocean points file not found"
  exit 1
fi

#output file for the for the mapping
parmetisfile=$maptype.mapping.$npart

#output file with the TASK GEOMETRY definition
geometry_var=$maptype.geometry.$npart

#output file for BG/Q settings
bg_geometry=$maptype.bggeometry.$npart

#Extract the number of rows and columns of the domain decomposition
nline=$(cat $matrix | wc -l) 
echo "rows= $nline"
ncol=$(($(cat $matrix | wc -w)/$nline))
echo "columns= $ncol"

dim=$((procxnode * npart))
decomp="$ncol x $nline" #Be aware of the white spaces
#decomp="8 x 37" #be aware of the white spaces

#############################################################
# mapping based on cardinal order 
#############################################################

if [ $maptype = "card" ]; then

rm $parmetisfile >& /dev/null

for i in `seq 0 $((npart - 1))`; do
	for j in `seq 1 $procxnode`; do
		echo $i >> $parmetisfile
	done
done
fi

#############################################################
# mapping based on calc2 strategy
#############################################################

if [ $maptype = "calc2" ]; then

	grep -A $((dim+1)) "$decomp" $layoutfile | grep -v Total | awk '{print $2 " - " $1}' | sort -n -r > oceanpt.def
	rm mapping.tmp >& /dev/null
	for i in `seq 0 $((dim-1))`; do
		line=`sed -n "$((i+1)),$((i+1)) p" oceanpt.def`
		echo "$((i % npart)) - $line" >> mapping.tmp
	done
	
	cat mapping.tmp | awk '{print $5 " " $1}' | sort -n | cut -d " " -f 2 > $parmetisfile

fi

#############################################################
# mapping based on memory 
#############################################################
if [ $maptype = "calc" -o $maptype = "mem" ]; then

rm oceanpt.* >& /dev/null

#reading the ocean points memory usage
if [ $maptype = "calc" ]; then
	grep -A $((dim+1)) "$decomp" $layoutfile | grep -v Total | awk '{print $2 " - " $1}' | sort -n -r > oceanpt.def
else
	grep -A $((dim+1)) "$decomp" $layoutfile | grep -v Total | awk '{print $3 " - " $1}' | sort -n -r > oceanpt.def
fi

i=0
for node in `cat oceanpt.def | cut -d "-" -f 1 | sed -e "s/\.//" -e "s/^0*//"`; do 
	ocnpnt[i]=$node
	((i++))
done;

i=0
for node in `cat oceanpt.def | cut -d "-" -f 2`; do 
        rank[i]=$node
        ((i++))
done;

rm weight* mapp_* >& /dev/null


for i in `seq 0 $(($npart-1))`; do
   echo "0 - $i" >> weight 
done

for i in `seq 0 $(($dim - 1))`; do
   minrow="`sort -n weight| head -1`"
   minocn=`echo $minrow | cut -d "-" -f 1 | sed -e "s/ //g"`
   minnode=`echo $minrow | cut -d "-" -f 2 | sed -e "s/ //g"`

   printf "\r Processing node $((i+1)) of $dim \t"

   echo "${rank[$i]}" >> mapp_$minnode
   newvalue=$(($minocn + ${ocnpnt[$i]}))
   if [ `wc -l mapp_$minnode | cut -d " " -f 1` -eq $procxnode ]; then
       grep -v "${minrow}$" weight > weight.new
       echo "$newvalue - $minnode" >> weight.final
   else
       sed -e "s/${minrow}$/$newvalue - $minnode/" weight > weight.new
   fi 
   mv weight.new weight 
done
echo " "

for i in `ls mapp_*`; do 
   idx=`echo $i|cut -d "_" -f 2`
   sed -e "s/^\(.*\)/\1 $idx/" $i >> metis.part.memory.temp
done

rm $parmetisfile >& /dev/null

sort -n metis.part.memory.temp | cut -d " " -f 2 >> $parmetisfile
rm metis.part.memory.temp

rm oceanpt.* weight* mapp_* >& /dev/null

fi

#############################################################
# Creation of the graph file in parmetis format
#############################################################


el=0
#for i in `tail -r $matrix`; do 
for i in `tac $matrix`; do 
	m[el]=$(($i+1))
	((el++))
done;


if [ $el -ne $(($nline*$ncol)) ] ; then
	echo "ERROR"
	exit 1
fi

for((i=0;i<${#m[@]};i++)) ; do
	if [ ${m[$i]} -ne 0 ] ; then
		
		up=${m[(($i+$ncol))]} ; if [[ $up -ne 0 ]] ; then echo -n "$up   " >> $outdir"parmetis.part"; fi 
		
		if [ $((i - ncol )) -ge 0 ]; then
			down=${m[(($i-$ncol))]} ; if [[ $down -ne 0 ]] ; then echo -n "$down   " >> $outdir"parmetis.part"; fi 
		fi
		
		#left boundary
		if [[ $(($i%$ncol)) -eq 0 ]] ; then  
			left=${m[(($i+$ncol-1))]}
		else 
			left=${m[(($i-1))]}
		fi
		if [[ $left -ne 0 ]] ; then echo -n "$left   " >> $outdir"parmetis.part"; fi 
		
		#right boundary
		if [[ $(($(($i+1))%$ncol)) -eq 0 ]] ; then 
			right=${m[(($i-$ncol+1))]}
		else 
			right=${m[(($i+1))]} ; 
		fi
		if [[ $right -ne 0 ]] ; then echo -n "$right   " >> $outdir"parmetis.part"; fi 
		
		#north pole domains
		if [[ $i -ge $(($nline*$ncol-$ncol)) ]] ; then
			near1=${m[(($ncol*((2*$nline-1))-$i-2))]} ; if [[ ( $near1 != 0 ) && ( $near1 != $up ) && ( $near1 != $down ) && ( $near1 != $left ) && ( $near1 != $right ) && ( $near1 != ${m[$i]} ) ]] ; then echo -n "$near1   " >> $outdir"parmetis.part"; fi
			near2=${m[(($ncol*((2*$nline-1))-$i-1))]} ; if [[ $near2 -ne 0  && ( $near2 != $up ) && ( $near2 != $down ) && ( $near2 != $left ) && ( $near2 != $right ) && ( $near2 != $near1 ) && ( $near2 != ${m[$i]} ) ]] ; then echo -n "$near2   " >> $outdir"parmetis.part"; fi
			near3=${m[(($ncol*((2*$nline-1))-$i))]} ; if [[ $near3 -ne 0 && ( $near3 != $up ) && ( $near3 != $down ) && ( $near3 != $left ) && ( $near3 != $right ) && ( $near3 != $near1 ) && ( $near3 != $near2) && ( $near3 != ${m[$i]} ) ]] ; then echo -n "$near3   " >> $outdir"parmetis.part"; fi
		fi
		
		echo "" >> $outdir"parmetis.part"
	fi
done;

node=$(cat $outdir"parmetis.part" | wc -l)
edge=$(cat $outdir"parmetis.part" | wc -w)
edge=$(($edge/2))

echo "$node $edge"> $outdir"parmetis.in"
while read line; do
	echo "${line}" >> $outdir"parmetis.in"
done < $outdir"parmetis.part"

rm $outdir"parmetis.part"

#############################################################
# mapping based on communication
#############################################################

if [ $maptype = "comm" ]; then
#execution of scotch (gpart num_part [input graph file] [output map file] -b0)

#translate the parmetis format file into the scotch format file
gcv parmetis.in scotch.in -ic -os

#partitioning with scotch
gpart $npart scotch.in scotch.map -b0

#translate the output file format
sed -n "s/\t/ /p" scotch.map | cut -d " " -f 2 > $parmetisfile

rm scotch.map scotch.in

#lancia metis (gpmetis [options] graphfile nparts)

#gpmetis -ptype=kway -objtype=vol parmetis.in $npart
#gpmetis -contig -ufactor=1 -ncuts=50 -niter=200 -ptype=kway -objtype=cut parmetis.in $npart

fi # end maptype==comm


#############################################################
# Mapping based on neighbour-away algorithm
#############################################################

if [ $maptype = "away" ]; then

# the script partitions the input nodes of the graph into "npart" sets. One node is requested to belong
# to a partition different from each of its neighbours 

#input file describing the dependency graph. Format used is ParMetis adiacency list file
graphfile="parmetis.in"

# create npart temporary files
for i in `seq 0 $((npart - 1))`; do
        p_filename=`printf "p_%04d" $i`
        rm $p_filename >& /dev/null
        touch $p_filename
done
num_nodes=`sed -n "1,1 s/[0-9]*$//p" $graphfile`
for i in `seq 1 $num_nodes`; do
        # processing node $i
        printf "\r Processing node $i of $num_nodes \t"
        # sort the current partitions 
        ordered_file="p_ordered"
        wc -l p_*[0-9] | sed -n "1,$npart s/^ *//p" | sort -n > $ordered_file

        # insert the current node $i into a partition where none of its neighbours is present
        neighbour_list=`sed -n "$((i+1)),$((i+1)) p" $graphfile`
        placed=0
        for j in `seq 1 $npart`; do
                p_filename=`sed -n "$j,$j p" $ordered_file | cut -d " " -f 2`
                insert=1
                for k in $neighbour_list; do
                        flag=`grep "^$k$" $p_filename | wc -l`
                        if [ $flag != 0 ]; then
                                insert=0
                                break
                        fi
                done
                if [ $insert == 0 ]; then
                        continue
                fi
                echo $i >> $p_filename
                placed=1
                break
        done
        if [ $placed == 0 ]; then
                echo "Error node $i can not be placed in any of the partitions"
                exit 1
        fi
done
printf "\n"

rm $ordered_file

# merging of the entire temporary partions files
rm $parmetisfile >& /dev/null
for i in `seq 1 $num_nodes`; do
        part=`grep "^$i$" p_*[0-9] | cut -d "_" -f 2 | cut -d ":" -f 1 | sed "s/^0*//"`
        if [ x$part == "x" ]; then
                part=0
        fi
        printf "%d\n" $part >> $parmetisfile
done

rm p_*[0-9]

fi # end maptype = "away"

#############################################################
# Check for correctness
#############################################################

#check if each partition has the same number of elements
for i in `eval echo {0..$(($npart-1))}`; do
	n=`grep "^$i$" $parmetisfile | wc -l`
	if [ $n -ne $procxnode ] ; then 
		echo "ERROR! Node $i has $n proc!"
	fi
done

#############################################################
# Diagnostic
#############################################################

# Memory needed for each partitions
echo "*******************"
echo "Memory Distribution"
echo "*******************"
grep -A $((dim+1)) "$decomp" $layoutfile | grep -v Total | awk '{print $3}' > oceanpt.tmp

for i in `seq 1 $dim`; do
	p=`sed -n "$i,$i p" $parmetisfile`
	weight=`sed -n "$i,$i p" oceanpt.tmp`
	w[p]=`echo 0${w[$p]} + $weight | bc`
done

rm oceanpt.tmp

max=${w[0]}
min=${w[0]}
tot=${w[0]}
min_p=0
max_p=0
echo "0 - ${w[0]} GB"
for i in `seq 1 $((npart-1))`; do
	echo "$i - ${w[$i]} GB"
	t=`echo "${w[$i]} > $max" | bc`
	if [ $t == 1 ]; then max=${w[$i]}; max_p=$i; fi
	t=`echo "${w[$i]} < $min" | bc`
	if [ $t == 1 ]; then min=${w[$i]}; min_p=$i; fi
	tot=`echo "$tot + ${w[$i]}" | bc`
done
mean=`echo "scale = 3; $tot/$npart"|bc `
echo "Max memory  $max GB on partition $max_p"
echo "Min memory  $min GB on partition $min_p"
echo "Mean memory $mean GB"
echo "Memory unbalance (Max/Mean)" `echo "scale = 2; $max/$mean" |bc` "%" 

# Number of interconnection (intra- and inter- node) between processes
echo "*********************************"
echo "Interconnection between processes"
echo "*********************************"

com=0
comtot=0

i=1
while read p; do
	part[i]=$p
	((i++))
done < $parmetisfile

l=0
while read line; do
	if [[ l -ne 0 ]] ; then
		for i in `echo $line`; do
			if [[ ${part[$i]} -ne ${part[$l]} ]] ; then
				((com++))
			fi
			((comtot++))
		done
	fi		
	((l++))
done < $outdir"parmetis.in"

echo "Tot comunicazioni: $comtot"
echo "Tot comunicazioni internodo: $com"


#############################################################
#writing the TASK_GEOMETRY
#############################################################

number_of_groups=`cat $parmetisfile | sort -u | wc -l`

echo -n 'export LSB_PJL_TASK_GEOMETRY="{' > $geometry_var
#for j in `seq 0 $((number_of_groups - 1))`; do
for j in `eval echo {0..$((number_of_groups - 1))}`; do
 echo -n "(" >> $geometry_var
   for i in `grep -n "^$j$" $parmetisfile | cut -d : -f 1`; do
     echo -n $((i-1)), 
   done | sed s/.$// >> $geometry_var
echo -n ")" >> $geometry_var
done;
echo '}"' >> $geometry_var

#cat $geometry_var


#############################################################
#writing the geometry for BG/Q architecture
#############################################################

# each row contains the position of the process in the torus 
# the shape of the torus is defined by the 6 parameters A, B, C, D, E, T

tor_a=2
tor_b=2
tor_c=4
tor_d=4
tor_e=2
tor_t=16

cat -n $parmetisfile | awk '{print $2 " " $1}'| sort -n | cat -n | awk -v val=$tor_t '{print $3 " " $2 " " ($1-1) % val}' | sort -n | awk -v val_a=$tor_a -v val_b=$tor_b -v val_c=$tor_c -v val_d=$tor_d -v val_e=$val_e '{print int($2/(val_b*val_c*val_d*val_e)) " " int($2/(val_c*val_d*val_e)) % val_b " " int($2/(val_d*val_e)) % val_c " " int($2/val_e) % val_d " " $2 % val_e  " " $3}' > $bg_geometry


#############################################################
#writing svg
#############################################################
#load the mapping file

i=1
for node in `cat $parmetisfile`; do 
	map[i]=$node
	((i++))
done;

#loading of the number of ocean points and memory usage
decomp=`grep "Decomp" $gridfile | cut -d : -f 3`
k=0
for oceanpt in `grep -A ${#map[*]} "$decomp" $layoutfile | grep -v Total | awk '{print $2}'` ; do
	oceanptvett[k]=$oceanpt
	((k++))
done;
k=0
for mempt in `grep -A ${#map[*]} "$decomp" $layoutfile | grep -v Total | awk '{print $3}'` ; do
	memptvett[k]=$mempt
	((k++))
done;

#creation of the color map

num_col=$npart
for((i=0;i<$num_col;i++))  ; do
	colourvett[i]="rgb($(($RANDOM%256)),$(($RANDOM%256)),$(($RANDOM%256)))"
done;

outfile=$maptype.display.$npart.svg

#extract the grid dimension
width=0 ; height=0;
for i in `grep -A4 "# [ 0-9]" $gridfile | grep -v \- | grep -v \# | sed "s/^[ \t]*//;s/[ \t]*$//" | sed "s/  */ /g" |sed "s/ /,/g" | cut -f 1 -d ,`; do
   if [[ $i -gt $width ]]; then
      width=$i
   fi
done;
for i in `grep -A4 "# [ 0-9]" $gridfile | grep -v \- | grep -v \# | sed "s/^[ \t]*//;s/[ \t]*$//" | sed "s/  */ /g" |sed "s/ /,/g" | cut -f 2 -d ,`; do
   if [[ $i -gt $height ]]; then
      height=$i
   fi
done;

#writing the header
echo "<?xml version=\"1.0\" encoding=\"iso-8859-1\" standalone=\"no\"?> " > $outfile
echo "<!DOCTYPE svg PUBLIC \"-//W3C//Dtd SVG 1.1//EN\" \"http://www.w3.org/Graphics/SVG/1.1/Dtd/svg11.dtd\">" >> $outfile 
echo "<svg width=\"$(($width+150))\" height=\"$(($height+100))\" version=\"1.1\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">" >> $outfile

#background image. It can be derived from the bathimetry
echo "<image x=\"0\" y=\"0\" width=\"$width\" height=\"$height\" xlink:href=\"background.png\"/>" >> $outfile

#writing the subdomain rectangles with additional information about process ID and color
j=0;
for i in `grep -A4 "# [ 0-9]" $gridfile | grep -v \- | sed "s/#/ /g" | sed "s/^[ \t]*//;s/[ \t]*$//" | sed "s/  */ /g" |sed "s/ /,/g" | sed '1d'`; do
	case $j in
	0)
		proc=$(($i-1));
		nodeid=node_$proc
		col_index=${map[$i]}
		echo -n "<polygon id=\"$nodeid\" points=\"" >> $outfile
		((j++));
                printf "\rGenerating SVG ... %3d%%  " $(( (($proc + 1 ) * 100) / $dim ))
	;;
	1)
		((j++));
		x=$(echo $i | cut -f 1 -d ,);
		y=$(($height-$(echo $i | cut -f 2 -d ,)));
		xtxt=$(($x+3))
		ytxt=$(($y-3))
		echo -n "$x,$y "  >> $outfile
	;;
	[2-3])
		((j++));
		x=$(echo $i | cut -f 1 -d ,);
		y=$(($height-$(echo $i | cut -f 2 -d ,)));
		echo -n "$x,$y "  >> $outfile
	;;
	4)
		j=0;
		x=$(echo $i | cut -f 1 -d ,);
		y=$(($height-$(echo $i | cut -f 2 -d ,)));
		echo "$x,$y\" style=\"stroke:white;fill:${colourvett[$col_index]};fill-opacity:0.7\" />" >> $outfile
		echo "<text x=\"$xtxt\" y=\"$ytxt\" fill=\"white\" >$proc</text>" >> $outfile
		echo "<g visibility=\"hidden\" font-family =\"sans-serif\" fill=\"black\" font-size = \"12\">" >> $outfile
		echo "<rect x=\"$xtxt\" y=\"$ytxt\" rx=\"2\" ry=\"2\" width=\"175\" height=\"95\" style=\"stroke:black;fill:lightgray\">" >> $outfile
		echo "<set attributeName=\"visibility\" from=\"hidden\" to=\"visible\" begin=\"$nodeid.mousedown\" end=\"$nodeid.mouseout\"/></rect>" >> $outfile
		echo "<text x=\"$(($xtxt+10))\" y=\"$(($ytxt+20))\" font-weight=\"bold\">Ocean Sub-domain : $proc<set attributeName=\"visibility\" from=\"hidden\" to=\"visible\" begin=\"$nodeid.mousedown\" end=\"$nodeid.mouseout\"/></text> " >> $outfile
		echo "<text x=\"$(($xtxt+10))\" y=\"$(($ytxt+40))\">Total ocepts : ${oceanptvett[$proc]}<set attributeName=\"visibility\" from=\"hidden\" to=\"visible\" begin=\"$nodeid.mousedown\" end=\"$nodeid.mouseout\"/></text> " >> $outfile
		echo "<text x=\"$(($xtxt+10))\" y=\"$(($ytxt+60))\">Memory in Gb : ${memptvett[$proc]}<set attributeName=\"visibility\" from=\"hidden\" to=\"visible\" begin=\"$nodeid.mousedown\" end=\"$nodeid.mouseout\"/></text> " >> $outfile
		echo "<text x=\"$(($xtxt+10))\" y=\"$(($ytxt+80))\">Color : $col_index<set attributeName=\"visibility\" from=\"hidden\" to=\"visible\" begin=\"$nodeid.mousedown\" end=\"$nodeid.mouseout\"/></text> " >> $outfile
		echo "</g>" >> $outfile
	;;
	*) 
		echo "ERROR"
	;;
	esac;
done;

#chiudo il file svg
echo "</svg>" >> $outfile
 
printf " Done\n"
