#!/bin/tcsh -f
#
# hierarchies_check_simulation <cpus> <recording> [<options>]
#
# Analyzes the given recursion tree and checks if it's profitable
# to desactivate lower recursion hierarchies (i.e. if potential
# parallelism measured by using the ALWAYS strategy yields enough
# units of work and no large sequential chunks are left over)
#
# REQUIREMENTS:
# - only procedures to be parallelized produce output (-autonostats)
# - first recursion tree in recording is the relevant one
# - there are just top-to-bottom calls, i.e. a->a,b and b->b but
#    not b->a,b (should be detected automatically)
# - only one new procedure is introduced at each layer, e.g.
#    a->a,b but not a->a,b,c
#
# Stefan U. Haenssgen  12-feb-98
#
# 12-feb-98	1st version
#
set simprog=simulation

if ($#argv < 2) then
  echo "$0 - need cpu number and file name of recorded tree for analysis"
  echo " (and optional simulation settings)"
  exit 1
endif

set cpus=$1
shift
set treefile="$1"
shift
set simoptions="$*"

if (! -f $treefile) then
  echo "$0 - could not open tree recording '$treefile'"
  exit 2
endif

echo "Analyzing recursion tree '$treefile' on $cpus CPUs"
echo "for potential non-parallelization of recursion hierarchies"
echo ""

set tmpfile=/tmp/hcs_$$

# Get procedure information from REAPAR output, e.g.:
#
#   BEGIN REAPAR TREES
#   Procedure number 2 = computesubtree
#
#   Recursion Tree for 'computesubtree', Number 2, iteration 0:
#
#   (2(2(2)(2)(2(...
#
awk '/BEGIN REAPAR TREES/,/Recursion Tree for/' $treefile | fgrep "Procedure number" > $tmpfile
set procnames=`cut -d' ' -f5 $tmpfile`		# Array of procedure names
set procnums=`cut -d' ' -f3 $tmpfile`		# Corresponding numbers
rm -f $tmpfile
set startname=`fgrep "Recursion Tree for" $treefile | head -1 | cut -d\' -f2`

echo "Recursion tree starts with procedure $startname"
set topnames=($startname)

# Check in the procedure call information which procedures are called
# recursively by the starting procedure until no more calls are encountered.
#
awk '/BEGIN REAPAR PROCINFO/,/END REAPAR PROCINFO/' $treefile > $tmpfile
set callsprocs="dummy"
set curname=$startname
while ($#callsprocs > 0)
  set callsprocs=`fgrep "Procedure (" $treefile | fgrep ") $curname " | tr ':' '\12' | fgrep -v "Procedure (" | fgrep -v $curname`
  if ($#callsprocs > 0) then
    if ($#callsprocs > 1) then
      echo "Error, cannot handle multiple new procedures in hierarchy (YET)"
      echo "(e.g. 'a calls a,b'  is ok, but 'a calls a,b,c' is not"
      exit 4
    endif
    echo "$curname calls $callsprocs"
    set topnames=($topnames $callsprocs)
  endif
  set curname=$callsprocs
end
rm -f $tmpfile

if ($#topnames < 2) then
  echo ""
  echo "Only one recursive procedure for parallelization, no hierarchies needed"
  echo ""
  exit 100
endif

echo ""
echo "$#topnames recursion hierarchies detected ($topnames)"
echo ""

# Find out the numbers corresponding to the procedure names
#
set topnums=($topnames)			# Make arrays of right size
set topchars=($topnames)
set pn=1
while ($pn <= $#topnames)
  set i=0
  set num=0
  while ($num == 0)			# Look for procedure's number
    set i=`expr $i + 1`
    if ($i > $#procnums) then
      echo "Error, could not find number of procedure '$topnames[$pn]'"
      exit 3
    endif
    if ($topnames[$pn] == $procnames[$i]) then
      set num=$procnums[$i]
      set topnums[$pn]=$num
      set topchars[$pn]=`echo $num | tr '0-9' '@A-J'`
    endif
  end
  echo "... Procedure $topnames[$pn] (number $num, char $topchars[$pn])"
  set pn=`expr $pn + 1`
end

# Filter first recursion tree for later processing
#
set filterfile=$treefile.filtered
awk "/Recursion Tree for '$startname'/,/END REAPAR TREES/" $treefile | tail +3 | head -1 > $filterfile
echo ""
echo "Filtered tree written to $filterfile"

# Simulate tree, starting with all procedures as parallel and reducing
# parallelization of hierarchies until only topmost procedure parallel.
#
set lastpar=$#topnames
while ($lastpar >= 1)
  set procstring=""
  set i=1
  while ($i <= $lastpar)	# Construct parallel-procedures-string for sim
    set procstring="$procstring$topchars[$i]"
    set i=`expr $i + 1`
  end
  set leftoutnames=""		# Collect names of procedures not parallelized
  set leftoutcount=0
  while ($i <= $#topnames)
    set leftoutnames="$leftoutnames '$topnames[$i]'"
    set leftoutcount=`expr $leftoutcount + 1`
    set i=`expr $i + 1`
  end
  echo ""
  if ($lastpar == $#topnames) then
    echo "Simulating with all $lastpar procedures parallel ($procstring)"
  else
    if ($lastpar == 1) then
      echo "Simulating with first procedure parallel ($procstring)"
    else
      echo "Simulating with first $lastpar procedures parallel ($procstring)"
    endif
  endif
  echo ""

  # Check if potential parallelism is OK by simulating ALWAYS
  # strategy
  #
  $simprog -q -t $procstring -A $simoptions -c $cpus < $filterfile > $tmpfile

  set nodeperc=`fgrep "Largest values:" $tmpfile | cut -d\( -f2 | cut -d\) -f1`
  set leafperc=`fgrep "Largest values:" $tmpfile | cut -d\( -f3 | cut -d\) -f1`
  set h1=`fgrep "Not less threads than CPUs" $tmpfile | cut -d':' -f2`
  set h2=`fgrep "Node percentage of largest" $tmpfile | cut -d':' -f2`
  set h3=`fgrep "Leaf percentage of largest" $tmpfile | cut -d':' -f2`
  set h4=`fgrep "Subnode percentage of largest" $tmpfile | cut -d':' -f2`
  set h5=`fgrep "Subleaf percentage of largest" $tmpfile | cut -d':' -f2`
  set h6=`fgrep "Each CPU used at least" $tmpfile | cut -d':' -f2`
  #echo $h1 $h2 $h3 $h4 $h5 $h6
  rm -f $tmpfile
  if ( ($h1 == "OK") && ($h2 == "OK") && \
       ($h3 == "OK") && ($h4 == "OK") ) then
    echo "-> Simulation predicts enough parallelism if"
    set ok=1
  else
    echo "-> Simulation predicts NOT enough parallelism if"
  set ok=0
  endif
  if ($leftoutcount == 0) then
    echo "   all procedures are parallelized"
  else
    if ($leftoutcount == 1) then
      echo "   the procedure$leftoutnames is executed sequentially"
    else
      echo "   the procedures$leftoutnames are executed sequentially"
    endif
  endif
  echo "   (largest sequential chunk: $nodeperc of all nodes"
  echo "    and $leafperc of all leafs)"
  if ( ($ok == 1) && ($leftoutcount > 0) ) then
    echo ""
    echo "   -> Recommend /* NOPARALLEL */ annotation for$leftoutnames"
  endif

#NOT:  # Check if depths are OK, too
#  #
#  set depth=1
#  while ($depth <= 5) #20)
#    echo -n "-----------"
#    $simprog -q -t $procstring -d $depth $simoptions < $filterfile
#    set depth=`expr $depth + 1`
#  end

  set lastpar=`expr $lastpar - 1`
end

echo ""
