| #!/bin/bash |
| |
| ######################################################################################### |
| ##Software Implementation, Non-parametric Hierarchical Performance Testing (HPT) |
| ##Authors: Yue Wu (Email: wuyue@ict.ac.cn) and Tianshi Chen |
| ##Institute of Computing Technology, Chinese Academy of SCiences |
| ##Beijing 100190, China |
| ##Last Update: 17th June, 2013 |
| ##HPT on the web: http://novel.ict.ac.cn/tchen/hpt/ |
| ## |
| ##Reference: T. Chen, Y. Chen, Q. Guo, O. Temam, Y. Wu, and W. Hu, |
| ##"Statistical Performance Comparisons of Computers", |
| ##In Proceedings of HPCA-18, New Orleans, Louisiana, 2012. |
| ## |
| ##Provided for non-commercial research and educational use only. |
| ##Not for reproduction or distribution or commercial use. |
| ## |
| ## |
| ##Please retain the above information when you reuse the code in your own tool. |
| ######################################################################################### |
| |
| configfile=$1 |
| if [ -z "${configfile}" ]; then |
| configfile="parameter.cfg" |
| fi |
| ACC=20 # number of digits after the decimal point |
| acc_maxsu=2 |
| NCOL_BASELINE=5 |
| |
| select1_table_file=table_select1 |
| select2_table_file=table_select2 |
| |
| |
| ######################################################################### |
| # Math Part |
| ######################################################################### |
| |
| display_matrix() |
| { |
| # FUNCTION: display a data table |
| # FORMAT: display_matrix nrow ncol MTRX name |
| # OUTPUT: (None) |
| local i; local j; local mtrx |
| eval mtrx=(\${$3[@]}) |
| printf "\n========================================\n" |
| printf "Data matrix($4):\n" |
| for i in `seq 0 $(($1-1))`; do |
| for j in `seq 0 $(($2-1))`; do |
| printf "%12.3f " ${mtrx[$(($i*$2+$j))]} |
| done |
| printf "\n" |
| done |
| } |
| |
| combination() |
| { |
| # FUNCTION: return "n choose k", for example, `combination 4 2` equals to 6 |
| # FORMAT: combination n m |
| # OUTPUT: `combination n m` |
| local A=$1 |
| local B=1 |
| local RES=1 |
| local i |
| for i in `seq 1 $2` |
| do |
| RES=$(($RES*$A/$B)) |
| A=$(($A-1)) |
| B=$(($B+1)) |
| done |
| expr $RES |
| } |
| |
| cdfnorm() |
| { |
| # FUNCTION: an approximation of cumulative density function for standard norm distribution |
| # FORMAT: cdfnorm x |
| # OUTPUT: ret_cdf |
| local ACC=24 |
| local L=$1 |
| local a1=0.31938153; local a2=-0.356563782; local a3=1.781477937; local a4=-1.821255978 |
| local a5=1.330274429; local Pi=3.141592653589793238462643 |
| |
| if [ `echo "$L<0"|bc` -eq 1 ]; then |
| L=`echo "scale=$ACC;(-1)*$L"|bc` |
| fi |
| local K=`echo "scale=$ACC;1/(1+0.2316419*$L)"|bc` |
| local tmp=`echo "(((($a5*$K+$a4)*$K+$a3)*$K+$a2)*$K+$a1)*$K"|bc` |
| tmp=`echo "scale=$ACC;e(0-$L*$L/2)*$tmp/sqrt(2*$Pi)"|bc -l` |
| if [[ `echo "$1>0"|bc` -eq 1 ]]; then |
| tmp=`echo "scale=$ACC;1-$tmp"|bc` |
| fi |
| ret_cdf=`printf "%.${ACC}f" $tmp` |
| } |
| |
| qnorm() |
| { |
| # FUNCTION: quantile function of standard norm distribution |
| # FORMAT: qnorm p |
| # OUTPUT: ret_qnorm |
| local p=$1 |
| if [[ `echo "$p<=0"|bc` -eq 1 ]] || [[ `echo "$p>=1"|bc` -eq 1 ]]; then |
| echo "[Error][in function \"qnorm\"] the value of p is out of range." |
| unset ret_qnorm |
| return |
| fi |
| if [[ `echo "$p==0.5"|bc` -eq 1 ]]; then |
| ret_qnorm=0 |
| else |
| y=`echo "scale=$ACC;-l(4*$p*(1-$p))"|bc -l` |
| b=(1.570796288 0.03706987906 -0.0008364353589 -0.0002250947176 0.000006841218299 0.000005824238515 -0.00000104527497 0.00000008360937017 -0.000000003231081277 0.00000000003657763036 0.0000000000006936233982) |
| u=0 |
| pow=1 |
| for i in `seq 0 $((${#b[@]}-1))`; do |
| pow=`echo "scale=$ACC;$pow*$y"|bc` |
| u=`echo "scale=$ACC;$u+$pow*${b[$i]}"|bc` |
| done |
| u=`echo "scale=$ACC;sqrt($u)"|bc` |
| if [[ `echo "$p<0.5"|bc` -eq 1 ]]; then |
| u=`echo "scale=$ACC;$u*(-1)"|bc` |
| fi |
| ret_qnorm=$u |
| fi |
| } |
| |
| |
| get_rank() |
| { |
| # FUNCTION: get rank and repeating times of a sequence |
| # for example, seq_x=(22 33 11 22), then seq_rank=(2 4 1 2), seq_rep=(2 1 1 2) |
| # FORMAT: get_rank len seq_x seq_rank seq_rep |
| # OUTPUT: (seq_rank, seq_rep) |
| local i; local j; local tmp0; local tmp1; local tmp2; local cmpr; local gr_x |
| local len=$1 |
| eval gr_x=(\${$2[@]}) |
| |
| ##### CAUTION ####### |
| unset "$3" ### |
| unset "$4" ### |
| ##### CAUTION ####### |
| |
| for i in `seq 0 $(($len-1))`; do |
| tmp0=${gr_x[$i]} |
| tmp1=0 |
| tmp2=0 |
| for j in `seq 0 $(($len-1))`; do |
| cmpr=${gr_x[$j]} |
| if [[ `echo "$cmpr<$tmp0"|bc` -eq 1 ]]; then |
| tmp1=$(($tmp1+1)) |
| elif [[ `echo "$cmpr==$tmp0"|bc` -eq 1 ]]; then |
| tmp2=$(($tmp2+1)) |
| fi |
| done |
| eval $3[$i]=$(($tmp1+1)) |
| eval $4[$i]=$tmp2 |
| done |
| } |
| |
| get_ranksum() |
| { |
| # FUNCTION: get the rank-sum of a subsequence |
| # for example, if start=0, end=1, seq_rank=(2 4 1 2), rep=(2 1 1 2), then ret_ranksum=2.5+4=6.5 |
| # FORMAT: get_ranksum start end seq_rank seq_rep |
| # OUTPUT: $ret_ranksum |
| local i; local rk; local n; local grs_rank; local grs_rep |
| unset grs_rank; unset grs_rep |
| eval grs_rank=(\${$3[@]}) |
| eval grs_rep=(\${$4[@]}) |
| local w=0 |
| for i in `seq $1 $2`; do |
| eval rk=${grs_rank[$i]} |
| eval n=${grs_rep[$i]} |
| w=`echo "scale=1;$w+$rk+($n-1)/2"|bc` ## scale=1 is enough |
| done |
| ret_ranksum=$w |
| } |
| |
| |
| thexth() |
| { |
| # FUNCTION: return the "x"th smallest number in the sequence {x_0 x_1 x_2 ... x_(len-1)} |
| # the idea of "quick sort" is used in this implementation |
| # FORMAT: thexth len xth x_0 x_1 x_2 ... x_(len-1) |
| # OUTPUT: ret_thexth |
| local i; local tmp |
| local arr; local arr0; local arrl; local arrg |
| local len=$1 |
| local xth=$2 |
| local il=0 |
| local ig=0 |
| |
| eval arr0=(\$@) |
| for i in `seq 0 $(($len-1))`; do |
| tmp=$(($i+2)) |
| eval arr[$i]=${arr0[$tmp]} |
| done |
| local ref=${arr[0]} |
| |
| for i in `seq 1 $(($len-1))`; do |
| tmp=${arr[$i]} |
| if [[ `echo "$tmp<$ref"|bc` -eq 1 ]]; then |
| arrl[$il]=$tmp |
| il=$(($il+1)) |
| elif [[ `echo "$tmp>$ref"|bc` -eq 1 ]]; then |
| arrg[$ig]=$tmp |
| ig=$(($ig+1)) |
| fi |
| done |
| if [[ $(($len-$ig)) -lt $xth ]]; then |
| thexth $ig $((xth-$len+$ig)) ${arrg[@]} |
| elif [[ $il -lt $xth ]]; then |
| ret_thexth=$ref |
| else |
| thexth $il $xth ${arrl[@]} |
| fi |
| } |
| |
| get_median() |
| { |
| # FUNCTION: return the median of the subsequence of seq_x, from (start)th element to (end)th element |
| # FORMAT: get_median start end seq_x |
| # OUTPUT: ret_median |
| local tmp; local arr0; local arr; local i |
| local start=$1 |
| local end=$2 |
| eval arr0=(\${$3[@]}) |
| for i in `seq $start $end`; do |
| tmp=$(($i-$start)) |
| arr[$tmp]=${arr0[$i]} |
| done |
| local len=$(($end-$start+1)) |
| if [[ $(($len%2)) -eq 1 ]]; then |
| tmp=$(($len/2+1)) |
| thexth $len $tmp ${arr[@]} |
| ret_median=$ret_thexth |
| else |
| tmp=$(($len/2)) |
| thexth $len $tmp ${arr[@]} |
| ret_median=$ret_thexth |
| tmp=$(($len/2+1)) |
| thexth $len $tmp ${arr[@]} |
| ret_median=`echo "scale=$ACC;($ret_thexth+$ret_median)/2"|bc` |
| fi |
| } |
| |
| |
| prepare_one_row() |
| { |
| # FUNCTION: the length of seq_x is col1+col2. define seq_l as the subsequence containing the first col1 elements |
| # of seq_x, and seq_r as the subsequence containing the last col2 elements of seq_x. Return the median |
| # of seq_l and seq_r seperately(ml & mr), and the ranksum of the left part and the right part(wl & wr). |
| # FORMAT: prepare_one_row col1 col2 seq_x |
| # OUTPUT: ml,mr,wl,wr |
| local por_x; local por_rank; local por_rep |
| unset por_x; unset por_rank; unset por_rep |
| eval por_x=(\${$3[@]}) |
| get_rank $(($1+$2)) por_x por_rank por_rep ## get_rank has sentences "unset rank; unset rep" |
| get_ranksum 0 $(($1-1)) por_rank por_rep |
| wl=$ret_ranksum |
| get_ranksum $1 $(($1+$2-1)) por_rank por_rep |
| wr=$ret_ranksum |
| get_median 0 $(($1-1)) por_x |
| ml=$ret_median |
| get_median $1 $(($1+$2-1)) por_x |
| mr=$ret_median |
| } |
| |
| |
| select1() |
| { |
| # FUNCTION: return the number of subsets of set {1,2,...,n}, the sum of elements of which is no greater than target |
| # FORMAT: select1 n target |
| # OUTPUT: ret_select1 |
| |
| local n=$1 |
| local target=$2 |
| local tag=0 |
| local itg; local tmp; local tmp0; local HEAD; local CONTENT |
| |
| if [[ $n -lt 25 ]]; then |
| itg=`echo "scale=2;$target+1"|bc` |
| itg=${itg%.*} |
| itg=$(($itg-1)) |
| while read HEAD CONTENT; do |
| if [ "$HEAD" == [$n] ]; then |
| tag=1; |
| break; |
| fi |
| done <$select1_table_file |
| if [[ $tag -eq 1 ]]; then |
| CONTENT=`echo $CONTENT` |
| CONTENT=" $CONTENT" |
| if [[ `echo "$itg==$target"|bc` -eq 1 ]]; then |
| tmp=${CONTENT##* $itg:} |
| tmp0=${tmp%% *} |
| itg=$(($itg-1)) |
| if [[ $itg -lt 0 ]]; then |
| tmp=0 |
| else |
| tmp=${CONTENT##* $itg:} |
| tmp=${tmp0%% *} |
| fi |
| tmp=`echo "scale=2;$tmp0/2+$tmp/2"|bc` |
| else |
| tmp=${CONTENT##* $itg:} |
| tmp=${tmp%% *} |
| fi |
| else |
| echo "[Error][in function \"select1\"] Cannot find the entry." |
| tmp=-1 |
| fi |
| fi |
| ret_select1=$tmp |
| } |
| |
| |
| |
| ranksum_table() |
| { |
| # FUNCTION: calculate the upper and lower bound of rank-sum in a rank-sum test of a sequence with length "n" |
| # under the significant level "alpha". |
| # FORMAT: ranksum_table n alpha |
| # OUTPUT: ret_rst_n ret_rst_alpha ret_rst_upper ret_rst_lower |
| |
| local tag=0; local HEAD; local CONTENT; local pos; local value; local res; local tmp; local bound |
| local n=$1 |
| local alpha=$2 |
| local mu; local stddev |
| |
| if [[ `echo "$alpha<=0"|bc` -eq 1 ]] || [[ `echo "$alpha>=0.5"|bc` -eq 1 ]]; then |
| echo "[Error][in function \"ranksum_table\"] Alpha value($alpha) is out of range" |
| fi |
| |
| if [[ $n -eq $ret_rst_n ]] && [[ `echo "$alpha==$ret_rst_alpha"|bc` -eq 1 ]]; then |
| return |
| fi |
| |
| if [[ $n -le 12 ]] && [[ $n -ge 3 ]]; then |
| tag=0 |
| while read HEAD CONTENT; do |
| if [ "$HEAD" == [$n] ]; then |
| tag=1; |
| break; |
| fi |
| done <$select2_table_file |
| |
| if [[ tag -eq 0 ]]; then |
| echo "[Error][in function \"ranksum_table\"] Cannot find the entry." |
| ret_rst_upper=-1; ret_rst_lower=-1; ret_rst_n=-1; ret_rst_alpha=-1 |
| return |
| fi |
| bound=`combination $(($n*2)) $n` |
| bound=`echo "scale=$ACC;$bound*$alpha"|bc` |
| res=$CONTENT |
| while [[ 1 -eq 1 ]]; do |
| pos=${res%%:*} |
| res=${res#*:} |
| value=${res%% *} |
| res=${res#* } |
| if [[ `echo "$value<=$bound"|bc` -eq 1 ]]; then |
| tmppos=$pos |
| tmpvalue=$value |
| else |
| break |
| fi |
| done |
| if [[ `echo "$value+$tmpvalue<=2*$bound"|bc` -eq 1 ]]; then |
| ret_rst_lower=$pos |
| ret_rst_upper=$(($n*($n*2+1)-$ret_rst_lower)) |
| else |
| ret_rst_lower=`echo "scale=2;$tmppos+0.5"|bc` |
| ret_rst_upper=`echo "scale=2;$n*($n*2+1)-$ret_rst_lower"|bc` |
| fi |
| ret_rst_n=$n |
| ret_rst_alpha=$alpha |
| elif [[ $n -gt 12 ]]; then |
| qnorm $alpha |
| mu=`echo "scale=$ACC;$n*($n*2+1)/2"|bc` |
| stddev=`echo "scale=$ACC;sqrt((2*$n+1)/3)*$n/2"|bc` |
| tmp=`echo "scale=$ACC;$ret_qnorm*$stddev"|bc` |
| ret_rst_lower=`echo "scale=$ACC;$mu-($tmp)"|bc` |
| ret_rst_upper=`echo "scale=$ACC;$mu+($tmp)"|bc` |
| ret_rst_n=$n |
| ret_rst_alpha=$alpha |
| fi |
| |
| } |
| |
| |
| unibench() |
| { |
| # FUNCTION: the uni-bench level test for the sequence "seq_x" with length "n" under the significant level "alpha" |
| # if significant, return diff_median(=median_l-median_r); else return 0. |
| # FORMAT: unibench n alpha seq_x |
| # OUTPUT: ret_unibench |
| local n=$1 |
| local alpha=$2 |
| local ub_x |
| eval ub_x=(\${$3[@]}) |
| |
| prepare_one_row $n $n ub_x |
| local target=$wl |
| |
| ret_unibench=0 |
| if [[ $n -gt 2 ]]; then |
| ranksum_table $n $alpha |
| if [[ `echo "$target<=$ret_rst_lower"|bc` -eq 1 ]] || [[ `echo "$target>=$ret_rst_upper"|bc` -eq 1 ]]; then |
| ret_unibench=`echo "$ml-$mr"|bc` |
| fi |
| elif [[ $n -le 2 ]]; then |
| ret_unibench=`echo "$ml-$mr"|bc` |
| fi |
| } |
| |
| |
| |
| crossbench() |
| { |
| # FUNCTION: the cross-bench level test. "seq_x" represents the diff_median sequence with length "row" |
| # this function will return the reliability of the hypothesis "data_a is better than data_b". |
| # FORMAT: crossbench row seq_x |
| # OUTPUT: ret_crossbench ret_cb_wp ret_cb_wn |
| local row=$1 |
| local cb_x; local cb_rank; local cb_rep; local sign |
| eval cb_x=(\${$2[@]}) |
| local i; local tmp1; local tmp2 |
| local wp=0 |
| local wn=0 |
| |
| for i in `seq 0 $(($row-1))`; do |
| if [[ `echo "${cb_x[$i]}<0"|bc` -eq 1 ]]; then |
| sign[$i]=-1 |
| cb_x[$i]=`echo "scale=$ACC;${cb_x[$i]}*(-1)"|bc` |
| elif [[ `echo "${cb_x[$i]}>0"|bc` -eq 1 ]]; then |
| sign[$i]=1 |
| else |
| sign[$i]=0 |
| fi |
| done |
| get_rank $row cb_x cb_rank cb_rep |
| for i in `seq 0 $(($row-1))`; do |
| if [[ ${sign[$i]} -eq 1 ]]; then |
| wp=`echo "scale=$ACC;$wp+${cb_rank[$i]}+${cb_rep[$i]}/2-1/2"|bc` |
| elif [[ ${sign[$i]} -eq -1 ]]; then |
| wn=`echo "scale=$ACC;$wn+${cb_rank[$i]}+${cb_rep[$i]}/2-1/2"|bc` |
| else |
| wp=`echo "scale=$ACC;$wp+${cb_rank[$i]}/2+${cb_rep[$i]}/4-1/4"|bc` |
| wn=`echo "scale=$ACC;$wn+${cb_rank[$i]}/2+${cb_rep[$i]}/4-1/4"|bc` |
| fi |
| done |
| |
| if [[ -n "$ret_cb_wp" ]] && [[ -n "$ret_cb_wn" ]]; then ## not NULL |
| if [[ `echo "$ret_cb_wp==$wp"|bc` -eq 1 ]] && [[ `echo "$ret_cb_wn==$wn"|bc` -eq 1 ]]; then |
| return ## skip re-calculating |
| fi |
| fi |
| |
| ret_cb_wp=$wp |
| ret_cb_wn=$wn |
| |
| if [[ $row -lt 25 ]]; then |
| select1 $row $wp |
| tmp1=$ret_select1 |
| tmp2=$((2**$row)) |
| ret_crossbench=`echo "scale=$ACC;$tmp1/$tmp2"|bc` |
| else |
| tmp1=`echo "scale=$ACC;$wp-$row*($row+1)/4"|bc` |
| tmp2=`echo "scale=$ACC;sqrt($row*($row+1)*(2*$row+1)/24)"|bc` |
| tmp1=`echo "scale=$ACC;$tmp1/$tmp2"|bc` |
| cdfnorm $tmp1 |
| ret_crossbench=$ret_cdf |
| fi |
| |
| } |
| |
| |
| hpt_basic() |
| { |
| # FUNCTION: Do HPTest for the two data matrices(MTRX1' & MTRX2, MTRX1'=multi*MTRX1), using "alpha_uni" as the |
| # significant level in the uni-bench level test. The size of both matrices is row*col |
| # FORMAT: hpt_basic row col multi alpha_uni MTRX1 MTRX2 |
| # OUTPUT: ret_hpt_basic ret_hpt_wp ret_hpt_wn |
| local hpt_x |
| local seq_rank; local seq_rep; local MTRX1; local MTRX2; local meddiff |
| local i; local j; local k; local tmp1; local tmp2 |
| local row=$1 |
| local col=$2 |
| local multi=$3 |
| local alpha_uni=$4 |
| eval MTRX1=(\${$5[@]}) |
| eval MTRX2=(\${$6[@]}) |
| |
| for i in `seq 0 $(($row-1))`; do |
| unset upt_x |
| for j in `seq 0 $(($col-1))`; do |
| hpt_x[$j]=`echo "scale=$ACC;$multi*${MTRX1[$(($i*$col+$j))]}"|bc` |
| hpt_x[$(($j+$col))]=${MTRX2[$(($i*$col+$j))]} |
| done |
| unibench $col $alpha_uni hpt_x |
| meddiff[$i]=$ret_unibench |
| done |
| |
| # echo "hpt: meddiff(${#meddiff[@]}): ${meddiff[@]}" |
| crossbench $row meddiff |
| ret_hpt_basic=$ret_crossbench |
| ret_hpt_wp=$ret_cb_wp |
| ret_hpt_wn=$ret_cb_wn |
| |
| # echo ============ ret_hpt_basic=$ret_hpt_basic,wp=$ret_hpt_wp,wn=$ret_hpt_wn ============= |
| |
| } |
| |
| |
| maxspeedup() |
| { |
| # FUNCTION: return the maximum speedup value under reliability "reliability". Most of the parameters are the |
| # same as the function hpt_basic. |
| # FORMAT: maxspeedup row col reliability alpha_uni bool_wp_smaller MTRX1 MTRX2 |
| # OUTPUT: ret_maxspeedup |
| local row=$1 |
| local col=$2 |
| local reliability=$3 |
| local alpha=$4 |
| local bool_wp_smaller=$5 |
| local MMTRX1; local MMTRX2 |
| eval MMTRX1=(\${$6[@]}) |
| eval MMTRX2=(\${$7[@]}) |
| local su; local basesu; local myscale; local min; local max; local mid; local step; local reci |
| |
| |
| if [[ `echo "$reliability<0.5"|bc` -eq 1 ]]; then |
| echo "[Warning: Skip Calculating][in function \"maxspeedup\"] The reliability value($reliability), which is less than 0.5, will lead to a meaningless conclusion. Skip calculating." |
| ret_maxspeedup=-2 |
| return |
| elif [[ $bool_wp_smaller -eq 1 ]]; then |
| su=10 |
| hpt_basic $row $col $su $alpha MMTRX1 MMTRX2 |
| if [[ `echo "$ret_hpt_basic<1-$reliability"|bc` -eq 1 ]]; then |
| echo "[Error][in function \"maxspeedup\"] Overflow: the maximum_speedup is beyond the upper bound 10. Stop calculating." |
| ret_maxspeedup=-1 |
| return |
| else |
| step=-1 |
| myscale=1 |
| min=1 |
| max=10 |
| basesu=0 |
| while [[ $step -le $acc_maxsu ]]; do |
| mid=$((($max-$min)/2+$min)) |
| su=`echo "scale=$ACC;$basesu+$myscale*$mid"|bc` |
| hpt_basic $row $col $su $alpha MMTRX1 MMTRX2 |
| if [[ `echo "$ret_hpt_basic<1-$reliability"|bc` -eq 1 ]]; then |
| min=$mid |
| else |
| max=$mid |
| fi |
| |
| if [[ $min -eq $(($max-1)) ]]; then |
| basesu=`echo "scale=$ACC;$basesu+$min*$myscale"|bc` |
| myscale=`echo "scale=$ACC;$myscale/10"|bc` |
| step=$(($step+1)) |
| min=0 |
| max=10 |
| fi |
| done |
| ret_maxspeedup=`printf "%.${acc_maxsu}f" $basesu` |
| fi |
| else #elif [[ $bool_wp_smaller -ne 1 ]]; then |
| su=10 |
| reci=`echo "scale=$ACC;1/$su"|bc` |
| hpt_basic $row $col $reci $alpha MMTRX1 MMTRX2 |
| if [[ `echo "$ret_hpt_basic>$reliability"|bc` -eq 1 ]]; then |
| echo "[Error][in function \"maxspeedup\"] Overflow: the maximum_speedup is beyond the upper bound 10. Stop calculating." |
| ret_maxspeedup=-1 |
| return |
| else |
| step=-1 |
| myscale=1 |
| min=1 |
| max=10 |
| basesu=0 |
| while [[ $step -le $acc_maxsu ]]; do |
| mid=$((($max-$min)/2+$min)) |
| su=`echo "scale=$ACC;$basesu+$myscale*$mid"|bc` |
| reci=`echo "scale=$ACC;1/$su"|bc` |
| hpt_basic $row $col $reci $alpha MMTRX1 MMTRX2 |
| if [[ `echo "$ret_hpt_basic>$reliability"|bc` -eq 1 ]]; then |
| min=$mid |
| else |
| max=$mid |
| fi |
| |
| if [[ $min -eq $(($max-1)) ]]; then |
| basesu=`echo "scale=$ACC;$basesu+$min*$myscale"|bc` |
| myscale=`echo "scale=$ACC;$myscale/10"|bc` |
| step=$(($step+1)) |
| min=0 |
| max=10 |
| fi |
| done |
| ret_maxspeedup=`printf "%.${acc_maxsu}f" $basesu` |
| fi |
| fi |
| } |
| |
| ######################################################################### |
| # Math Part END |
| ######################################################################### |
| |
| |
| |
| |
| |
| |
| ######################################################################### |
| # Readfile Part |
| ######################################################################### |
| |
| |
| |
| read_config() |
| { |
| # FUNCTION: set all the key parameters by reading the config file. |
| # FORMAT: read_config cfg_file printinfo(display the config info when printinfo=1 and do not display when 0) |
| # OUTPUT: $? (1 for Error and 0 for No_error) |
| local cfgfile=$1 |
| local printinfo=$2 |
| |
| if [[ $# -ne 2 ]]; then |
| echo "[Error][in function \"read_config\"] Format error." |
| return 1 |
| fi |
| |
| current_status=0 |
| AutoCompareOff=0 |
| i3=0 |
| len_trineseq=-1 |
| |
| cnt=0 |
| matched=0 |
| ReadTriple=-1 |
| ReadDefaultMTRX=-1 |
| n_col_default=5 |
| |
| str_1_1=HaveCompareGroup |
| str_1_2=Name1 |
| str_1_3=LogGroup1 |
| str_1_4=Name2 |
| str_1_5=LogGroup2 |
| str_1_6=output_file |
| str_1_7=DefaultBaselineName |
| str_1_8=DefaultBaselineStatisticsLog |
| str_2_1=repeat |
| str_2_2=alpha_unibench |
| str_2_3=speedup |
| str_2_4=reliability |
| |
| printf "Reading NPT parameters at `date`...\n" |
| while read LINE; do |
| LINE=`echo $LINE` |
| if [[ "$LINE" == *"##"* ]]; then |
| LINE=${LINE%%##*} |
| LINE=`echo $LINE` |
| fi |
| if [[ "$LINE" == "" ]]; then |
| continue |
| fi |
| |
| if [[ "$LINE" == "[CONFIG FILE END]" ]]; then |
| current_status=-1 |
| break |
| elif [[ $current_status -eq 0 ]]; then |
| if [[ "$LINE" == "[Basic Info]" ]]; then |
| current_status=1 |
| elif [[ "$LINE" == "[HPT Parameters]" ]]; then |
| current_status=2 |
| elif [[ "$LINE" == "[Workload Settings]" ]]; then |
| current_status=3 |
| elif [[ "$LINE" == "[Default Baseline Statistics]" ]]; then |
| current_status=4 |
| fi |
| continue |
| elif [[ $current_status -eq 1 ]]; then |
| if [[ "$LINE" == "[Basic Info End]" ]]; then |
| current_status=0 |
| continue |
| elif [[ "${LINE:0:${#str_1_1}}" == $str_1_1 ]]; then |
| content=${LINE##HaveCompareGroup} |
| content=`echo $content` |
| content=${content##=} |
| content=`echo $content` |
| if [[ "$content" == "TRUE" ]] || [[ "$content" == "1" ]]; then |
| AutoCompareOff=1 |
| else |
| AutoCompareOff=0 |
| fi |
| elif [[ "${LINE:0:${#str_1_2}}" == $str_1_2 ]]; then |
| content=${LINE##Name1} |
| content=`echo $content` |
| content=${content##=} |
| name1=`echo $content` |
| elif [[ "${LINE:0:${#str_1_3}}" == $str_1_3 ]]; then |
| if [ -d loggroup1 ]; then |
| if [ -d loggroup1.old ]; then |
| rm -rf loggroup1.old |
| fi |
| mv loggroup1 loggroup1.old |
| fi |
| mkdir loggroup1 |
| content=${LINE##LogGroup1} |
| content=`echo $content` |
| content=${content##=} |
| content=`echo $content` |
| for file in `ls $content`; do |
| if [ -f $file ]; then |
| cp $file loggroup1/ |
| fi |
| done |
| elif [[ "${LINE:0:${#str_1_4}}" == $str_1_4 ]]; then |
| if [[ $AutoCompareOff -eq 1 ]]; then |
| content=${LINE##Name2} |
| content=`echo $content` |
| content=${content##=} |
| name2=`echo $content` |
| fi |
| elif [[ "${LINE:0:${#str_1_5}}" == $str_1_5 ]]; then |
| if [[ $AutoCompareOff -eq 1 ]]; then |
| if [ -d loggroup2 ]; then |
| if [ -d loggroup2.old ]; then |
| rm -rf loggroup2.old |
| fi |
| mv loggroup2 loggroup2.old |
| fi |
| mkdir loggroup2 |
| content=${LINE##LogGroup2} |
| content=`echo $content` |
| content=${content##=} |
| content=`echo $content` |
| for file in `ls $content`; do |
| if [ -f $file ]; then |
| cp $file loggroup2/ |
| fi |
| done |
| # eval loggroup2=(`ls $content`) |
| fi |
| elif [[ "${LINE:0:${#str_1_7}}" == $str_1_7 ]]; then |
| if [[ $AutoCompareOff -eq 0 ]]; then |
| content=${LINE##DefaultBaselineName} |
| content=`echo $content` |
| content=${content##=} |
| name2=`echo $content` |
| fi |
| elif [[ "${LINE:0:${#str_1_8}}" == $str_1_8 ]]; then |
| if [[ $AutoCompareOff -eq 0 ]]; then |
| content=${LINE##DefaultBaselineStatisticsLog} |
| content=`echo $content` |
| content=${content##=} |
| loggroup2=`echo $content` |
| fi |
| elif [[ "${LINE:0:${#str_1_6}}" == $str_1_6 ]]; then |
| content=${LINE##output_file} |
| content=`echo $content` |
| content=${content##=} |
| outputfile=`echo $content` |
| fi |
| elif [[ $current_status -eq 2 ]]; then |
| if [[ "$LINE" == "[HPT Parameters End]" ]]; then |
| current_status=0 |
| continue |
| elif [[ "${LINE:0:${#str_2_1}}" == $str_2_1 ]]; then |
| content=${LINE##repeat} |
| content=`echo $content` |
| content=${content##=} |
| repeat=`echo $content` |
| elif [[ "${LINE:0:${#str_2_2}}" == $str_2_2 ]]; then |
| content=${LINE##alpha_unibench} |
| content=`echo $content` |
| content=${content##=} |
| alpha_uni=`echo $content` |
| elif [[ "${LINE:0:${#str_2_3}}" == $str_2_3 ]]; then |
| content=${LINE##speedup} |
| content=`echo $content` |
| content=${content##=} |
| content=`echo $content` |
| eval speedup=(\$content) |
| elif [[ "${LINE:0:${#str_2_4}}" == $str_2_4 ]]; then |
| content=${LINE##reliability} |
| content=`echo $content` |
| content=${content##=} |
| content=`echo $content` |
| eval reliability=(\$content) |
| fi |
| elif [[ $current_status -eq 3 ]]; then |
| if [[ "$LINE" == "[Workload Settings End]" ]]; then |
| len_trineseq=$i3 |
| current_status=0 |
| continue |
| else |
| trine=${LINE%% *} |
| switch=${LINE##* } |
| if [[ $switch -eq 1 ]]; then |
| trineseq[$i3]=$trine |
| i3=$(($i3+1)) |
| fi |
| fi |
| fi |
| |
| done<$cfgfile |
| |
| if [[ $repeat -le 2 ]]; then |
| echo "[Warning] Then uni-bench level test will be skipped because of the small sample size(n_col<3)" |
| alpha_uni=NaN |
| elif [[ `echo "$alpha_uni!=0.1"|bc` -eq 1 ]] && [[ $repeat -lt 5 ]]; then |
| echo "[Warning] The alpha value of uni-bench level is set to 0.1 by force because of the small sample size(n_col<=5)" |
| alpha_uni=0.1 |
| fi |
| |
| printf "Complete reading NPT parameters at `date`\n\n" |
| |
| if [[ printinfo -eq 1 ]]; then |
| check_cfg_info |
| fi |
| |
| return 0 |
| } |
| |
| readmatrix() |
| { |
| # FUNCTION: fill the matrix "var_matrix" using the data from all the log file under the directory "filegroup_dir". |
| # Only data among the list "seq_trine" will be collected. The size of the matrix is row*col. |
| # FORMAT: readmatrix row col seq_trine filegroup_dir var_matrix |
| # OUTPUT: $? (1 for Error and 0 for No_error) (var_matrix) |
| local i; local j; local seq_trine; local seq_file; local cnt; local flag_break=0; local filename |
| local row=$1 |
| local col=$2 |
| eval seq_trine=(\${$3[@]}) |
| # eval seq_file=(\${$4[@]}) |
| local filegroup_dir=$4 |
| local matrixname=$5 |
| local gotcha=0 |
| local totalcnt=0 |
| |
| echo "Reading $filegroup_dir at `date`..." |
| grep -E '\[PARSEC\]\ \[==========\ Running\ benchmark\ |real' $filegroup_dir/* >loadmatrix.tmp |
| |
| local str1="[PARSEC] [========== Running benchmark " |
| if [[ ${#seq_trine[@]} -ne $row ]]; then |
| echo "[Error][in function \"readmatrix\"] Variant \"row\" does not match!" |
| return 1 |
| fi |
| for i in `seq 0 $(($row-1))`; do |
| cnt[$i]=0 |
| done |
| |
| #echo "trineseq(${#trineseq[@]}):${trineseq[@]}" |
| while read LINE; do |
| filename=${LINE%\.log*} |
| thread=${filename##*/} |
| thread=${thread#*run_} |
| thread=${thread%%_*} |
| inputsize=${filename##*/} |
| inputsize=${inputsize#*run_*_} |
| inputsize=${inputsize%%_*} |
| LINE=${LINE#*\.log:} |
| #echo thread=$thread, inputsize=$inputsize |
| #echo ${LINE:0:${#str1}} VS. $str1 |
| if [[ "${LINE:0:${#str1}}" == "$str1" ]]; then |
| |
| if [[ $gotcha -eq 1 ]]; then |
| echo "[Error][in function \"readmatrix\"] Incorrect log file format!" |
| return 1 |
| fi |
| |
| tmpstr=`expr match "$LINE" '.\+benchmark\ \(.\+\)\ \[.*'` |
| tmpstr="$tmpstr-$inputsize-$thread" |
| for j in `seq 0 $(($row-1))`; do |
| if [[ $tmpstr == ${seq_trine[$j]} ]] && [[ ${cnt[$j]} -lt $col ]]; then |
| pos=$(($col*$j+${cnt[$j]})) |
| jth=$j |
| gotcha=1 |
| break |
| fi |
| done |
| elif [[ `expr substr "$LINE" 1 4` == "real" ]] && [[ $gotcha -eq 1 ]]; then |
| LINE=`echo $LINE` |
| mvalue=`expr match "$LINE" '.\+\ \(.\+\)m.*'` |
| svalue=`expr match "$LINE" '.\+*m\(.\+\)s.*'` |
| timevalue=`echo "scale=3;$mvalue*60+$svalue"|bc` |
| eval $matrixname[$pos]=$timevalue |
| totalcnt=$((1+$totalcnt)) |
| cnt[$jth]=$((1+${cnt[$jth]})) |
| gotcha=0 |
| fi |
| if [[ $totalcnt -eq $(($row*$col)) ]]; then |
| flag_break=1 |
| break |
| fi |
| done <loadmatrix.tmp |
| rm loadmatrix.tmp |
| |
| # check: |
| for i in `seq 0 $(($row-1))`; do |
| if [[ ${cnt[$i]} -ne $col ]]; then |
| echo "[Error][in function \"readmatrix\"] Insufficient data!" |
| return 1 |
| fi |
| done |
| echo "Complete reading $filegroup_dir at `date`" |
| } |
| |
| read_default() |
| { |
| # FUNCTION: read the default baseline matrix from file "filename" to matrix "matrixname". |
| # FORMAT: read_default n_col seq_trine filename matrixname |
| # OUTPUT: (matrixname) |
| |
| local seq_trine; local trine; local numseq; local i; local tmp; local cnt=0; local val |
| #local j; local nt=12 |
| local n_col=$1 |
| eval seq_trine=(\${$2[@]}) |
| local filename=$3 |
| |
| if [[ -f $filename ]]; then |
| echo "Loading default baseline matrix..." |
| else |
| echo "[Error][in function \"read_default\"] Can not locate $filename!" |
| return |
| fi |
| |
| while read trine numseq; do |
| for i in `seq 0 $((${#seq_trine[@]}-1))`; do |
| if [ "${seq_trine[$i]}" == $trine ]; then |
| cnt=$(($cnt+1)) |
| tmp=0 |
| for val in $numseq; do |
| eval $4[$(($i*$n_col+$tmp))]=$val |
| tmp=$(($tmp+1)) |
| if [[ $tmp -ge $n_col ]]; then |
| break |
| fi |
| done |
| |
| break |
| fi |
| done |
| if [[ $cnt -eq ${#seq_trine[@]} ]]; then |
| return |
| fi |
| done <$filename |
| |
| echo "[Error][in function \"read_default\"] Can not locate all the workload when searching the baseline file." |
| } |
| |
| |
| ######################################################################### |
| # Readfile Part End |
| ######################################################################### |
| |
| |
| check_cfg_info() |
| { |
| # FUNCTION: print the config parameters. |
| # FORMAT: check_cfg_info |
| # OUTPUT: (None) |
| |
| echo "===========[Parameter Info Checklist]==========" |
| echo "HaveCompareGroup: $AutoCompareOff" |
| echo "Machine1: $name1" |
| echo "Machine2: $name2" |
| echo "DataLog1: `ls loggroup1`" |
| echo |
| if [ "$AutoCompareOff" == "1" ] || [ "$AutoCompareOff" == "TRUE" ]; then |
| echo "DataLog2: `ls loggroup2`" |
| else |
| echo "DataLog2: ${loggroup2}" |
| fi |
| echo "Outputfile: $outputfile" |
| echo "repeat: $repeat" |
| echo "alpha: $alpha_uni" |
| if [[ ${#speedup[@]} -eq 0 ]]; then |
| echo "Speedup: None" |
| else |
| echo "Speedup(${#speedup[@]}):${speedup[@]}" |
| fi |
| if [[ ${#reliability[@]} -eq 0 ]]; then |
| echo "Reliability: None" |
| else |
| echo "Reliability(${#reliability[@]}):${reliability[@]}" |
| fi |
| echo "Benchmark-Inputsize-Nthread(${#trineseq[@]} in total):" |
| echo ${trineseq[@]} |
| echo "================[Checklist End]================" |
| echo |
| } |
| |
| |
| main() |
| { |
| # FUNCTION: the whole HPTest, including reading config file, reading data matrices, reliability computing, |
| # and maximum speedup computing. |
| # FORMAT: |
| # OUTPUT: |
| |
| printf "\n=================================================================\n" |
| printf "========================= HPT ==============================\n" |
| printf "=================================================================\n\n" |
| if [[ $# -ne 1 ]]; then |
| echo "[Error][in function \"main\"] the standard format should be \"bash hpt.sh cfgfile\"" |
| return 1 |
| fi |
| |
| read_config $1 1 |
| if [[ $? -eq 1 ]]; then |
| return 1 |
| fi |
| echo "=================================================================" >$outputfile |
| echo "========================= HPT ==============================" >>$outputfile |
| echo "=================================================================" >>$outputfile |
| echo "" >>$outputfile |
| echo "[Date] `date`" >>$outputfile |
| echo "" >>$outputfile |
| check_cfg_info >>$outputfile |
| |
| row=${#trineseq[@]} |
| if [[ AutoCompareOff -eq 0 ]] && [[ $repeat -gt $NCOL_BASELINE ]]; then |
| echo "[Overflow] repeat times(which is $repeat) should be no larger than NCOL_BASELINE($NCOL_BASELINE) when using default baseline as comparison." |
| return |
| fi |
| |
| readmatrix ${#trineseq[@]} $repeat trineseq loggroup1 matrix_a |
| if [[ $? -eq 1 ]]; then |
| return |
| fi |
| if [[ AutoCompareOff -eq 1 ]]; then |
| readmatrix ${#trineseq[@]} $repeat trineseq loggroup2 matrix_b |
| if [[ $? -eq 1 ]]; then |
| return |
| fi |
| else |
| read_default $repeat trineseq $loggroup2 matrix_b |
| #read_default $repeat $loggroup2 matrix_b |
| fi |
| |
| display_matrix $row $repeat matrix_a $name1 |
| display_matrix $row $repeat matrix_b $name2 |
| display_matrix $row $repeat matrix_a $name1 >>$outputfile |
| display_matrix $row $repeat matrix_b $name2 >>$outputfile |
| echo "" >>$outputfile |
| |
| printf "\nAnalyzing and calculating, this may take a few minutes...\n\n" |
| # hpt_basic $row $repeat 1 $alpha_uni matrix_a matrix_b |
| time hpt_basic $row $repeat 1 $alpha_uni matrix_a matrix_b |
| |
| printf "===========================================================================================\n" |
| local n_mul=$((${#speedup[@]}+($acc_maxsu+1)*4*${#reliability[@]})) |
| printf "[Time estimating] The whole process will complete in about $n_mul times the above time.\n" |
| printf "===========================================================================================\n\n" |
| |
| if [[ `echo "$ret_hpt_wp<$ret_hpt_wn"|bc` -eq 1 ]]; then |
| tmp_reli=`echo "scale=4;1-$ret_hpt_basic"|bc` |
| t_name1="machine_A($name1)" |
| t_name2="machine_B($name2)" |
| better=1 |
| else |
| tmp_reli=`echo "scale=4;$ret_hpt_basic"|bc` |
| t_name1="machine_B($name2)" |
| t_name2="machine_A($name1)" |
| better=0 |
| fi |
| printf "[Comparison][original]\n$t_name1 is better than $t_name2 with reliability %.4f.\n\n" $tmp_reli |
| printf "[Comparison][original]\n$t_name1 is better than $t_name2 with reliability %.4f.\n\n" $tmp_reli >>$outputfile |
| |
| for i in `seq 0 $((${#speedup[@]}-1))`; do |
| su=${speedup[$i]} |
| if [[ $better -eq 1 ]]; then |
| hpt_basic $row $repeat $su $alpha_uni matrix_a matrix_b |
| tmp_reli=`echo "scale=4;1-$ret_hpt_basic"|bc` |
| else |
| hpt_basic $row $repeat $su $alpha_uni matrix_b matrix_a |
| tmp_reli=`echo "scale=4;1-$ret_hpt_basic"|bc` |
| fi |
| printf "[Comparison][speedup=%.4f]\n" $su |
| printf "The reliability of that $t_name1 outperforms $t_name2 with speedup %.4f is %.4f.\n\n" $su $tmp_reli |
| printf "[Comparison][speedup=%.4f]\n" $su >>$outputfile |
| printf "The reliability of that $t_name1 outperforms $t_name2 with speedup %.4f is %.4f.\n\n" $su $tmp_reli >>$outputfile |
| done |
| |
| for i in `seq 0 $((${#reliability[@]}-1))`; do |
| reli=${reliability[$i]} |
| maxspeedup $row $repeat $reli $alpha_uni $better matrix_a matrix_b |
| printf "[Comparison][reliability=%.4f]\n" $reli |
| printf "[Comparison][reliability=%.4f]\n" $reli >>$outputfile |
| if [[ `echo "$ret_maxspeedup>0"|bc` -eq 1 ]]; then |
| printf "The maximum speedup of $t_name1 over $t_name2 is %.${acc_maxsu}f with the given reliability %.4f.\n\n" $ret_maxspeedup $reli |
| printf "The maximum speedup of $t_name1 over $t_name2 is %.${acc_maxsu}f with the given reliability %.4f.\n\n" $ret_maxspeedup $reli >>$outputfile |
| else |
| printf "Skipped\n\n" |
| printf "Skipped\n\n" >>$outputfile |
| fi |
| done |
| |
| printf "\n\n[HPT COMPLETED] `date`\n" >>$outputfile |
| |
| if [[ -f loadmatrix.tmp ]]; then |
| rm loadmatrix.tmp |
| fi |
| } |
| |
| |
| main $1 |
| |
