[324] in netbsd-help mailing list archive
CPU time again..
daemon@ATHENA.MIT.EDU (I-Lin Wang)
Wed Sep 13 02:19:50 1995
From: I-Lin Wang <ilin@MIT.EDU>
To: netbsd-help@MIT.EDU
Date: Wed, 13 Sep 1995 02:19:29 EDT
Hi,
Now I enclose the major part of my code in which you can see many
times() function. It's because I have to use it to calculate the CPU time
spent for different procedures(find_in_arc(), update_tree1(),
find_out_arc(), update_tree2(), update_pi()). Also, there are many loops
in my code, so I have to add the CPU time up respectively.
Originally, sometimes I may get a strange CPU time like:
CPU time in find_in_arc is -26310255.216667
CPU time in find_out_arc is -17441363.666667
CPU time in update_tree is -33224456.366667
CPU time in update_pi is -21061797.133333
CPU time in total is 559.566667
in which, the last one(CPU time in total) was always reasonable
although others were not reasonable. But today I just got another one:
CPU time in find_in_arc is -2367670.916667
CPU time in find_out_arc is 28581729.966667
CPU time in update_tree is -22823949.200000
CPU time in update_pi is 16444961.316667
CPU time in total is -31915290.983333
which is very strange, even the total CPU time is so wrong.
By the way, I use the same code, the same data, and I don't have
any strange output like above if I run it on SUN or DEC. I use gcc.(when I
run it on my NetBSD, I use the gcc in my machine; when I run it on SUN or
DEC, I use the gcc in the locker.) The output should be something like:
CPU time in find_in_arc is 54.166667
CPU time in find_out_arc is 3.100000
CPU time in update_tree is 2.850000
CPU time in update_pi is 389.750000
CPU time in total is 459.183333 --->(this is aboout the sum of the above)
So, please check my code, and feel free to give me any advice.
Thanks.
---------------
NOTE!! this is not the main function, this is just the function which
invoke times() the most.
=======================================================================
/*
** This file includes
**
** min_cost_flow(), find_in_arc(), find_out_arc(),
** update_flow(), update_tree1(), update_tree2(), update_pi(), percolate()
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/types.h>
#include <sys/times.h>
#include "premulti3.h"
/*---------------------- min_cost_flow() ----------------------------------*/
/*
** MIN_COST_FLOW
** (pivots1, pivots2, pi_updates, eligibles,--, nodes_on_path,
arcs_per_cycle, nodes_scanned, arcs_scanned1, arcs_scanned2,
EN, arcs_scanned3)
** starting point of the core part of network simplex
*/
void min_cost_flow(int *pivots1, int *pivots2, int *pi_updates, int *eligibles,
int *nodes_on_path, int *arcs_per_cycle, int *nodes_scanned,
int *arcs_scanned1, int *arcs_scanned2, int *EN,
int *arcs_scanned3)
{
int in_arc, /* pivot-in arc */
out_arc, /* pivot-out arc */
root, /* the index of the root node */
new_root;
int empty;
int in_direction, /* the direction of pivot-in arc
1: original, 0: reversal */
out_direction; /* the direction of pivot-out arc
1: original, 0: reversal */
int child;
int i, flag=1;
int cp, tin, tout, ttree, tpi, tper;
/* double dtin, dtout, dttree, dtpi, dtper;*/
struct tms x;
int arcs_scanned0;
arcs_scanned0=0;
root=0;
tin=0; tout=0; ttree=0; tpi=0; tper=0;
mode=0; /* mode=0, we have to compute delta2 from the beginning
mode=1, we can get new delta2 by subtracting previous delta */
n_d1=0; n_d2=0; /* # iteratons for method2(n_d2) & method1,3(n_d1) */
eps=max_cpij(); /* find the max reduced cost of arcs */
for (i=0;i<n_node;i++) /* all nodes are awake in the beginning */
{
star_node[i].in_N=1; /* all in N* */
star_node[i].sleep=0; /* all awake */
}
n_N=0; /* # nodes in N=0 ????????*/
empty=0; /* N is full now */
times(&x);
cp=x.tms_utime;
method=1; /* this method is to scan from FirstArc(i) in find_in_arc() */
in_arc=find_in_arc(root, &in_direction, arcs_scanned1, eligibles,
&arcs_scanned0);
times(&x);
tin+=(x.tms_utime-cp);
do{ /* 1st loop for total scaling phases,
it ends when eps < 1/n */
do{ /* 2nd loop is for current scaling phase */
while(in_arc != -1) /* loop when there is an admissble arc in this
iteration */
{
times(&x);
cp=x.tms_utime;
/* update tree1, change the tree structure */
update_tree1(root, in_arc, in_direction, arcs_scanned2, nodes_on_path)
;
times(&x);
ttree+=(x.tms_utime-cp);
times(&x);
cp=x.tms_utime;
/* in the circuit, find the pivot out arc */
out_arc=find_out_arc(in_arc, in_direction, &out_direction,
arcs_per_cycle, nodes_scanned, pivots1, pivots2,
eligibles);
times(&x);
tout+=(x.tms_utime-cp);
if(out_direction==1) /* the out arc has same direction as circuit */
{
new_root=star_arc[circuit[out_arc]].from;
child=star_arc[circuit[out_arc]].to;
}
else /* the out arc has opposite direction as circuit */
{
new_root=star_arc[circuit[out_arc]].to;
child=star_arc[circuit[out_arc]].from;
}
times(&x);
cp=x.tms_utime;
/* update the tree structure after pivot */
update_tree2(new_root, child, arcs_scanned2);
times(&x);
ttree+=(x.tms_utime-cp);
star_arc[in_arc].tree=1; /* in_arc is in the tree */
star_arc[circuit[out_arc]].tree=0; /* out_arc is out of the tree */
root=new_root;
times(&x);
cp=x.tms_utime;
method=3; /* this method scans arc from CurrentArc, not FirstArc */
in_arc=find_in_arc(root, &in_direction, arcs_scanned1, eligibles,
&arcs_scanned0);
times(&x);
tin+=(x.tms_utime-cp);
mode=0; /* set to be mode 0, so that in the update_pi, it has to
compute delta2 from the beginning */
}
/* now, in_arc==-1, we have to update_pi */
(*pi_updates)++;
(*arcs_scanned3)+=(*arcs_scanned1)-(arcs_scanned0);
/* get # arcs scanned to go to update_pi */
times(&x);
cp=x.tms_utime;
/* update pi */
flag=update_pi(root, EN, eligibles, &empty);
times(&x);
tpi+=(x.tms_utime-cp);
if (flag!=0) /* delta1!=INFTY, we did update delta2 */
{
times(&x);
cp=x.tms_utime;
/* go to find pivot in arc now */
in_arc=find_in_arc(root, &in_direction, arcs_scanned1, eligibles,
&arcs_scanned0);
times(&x);
tin+=(x.tms_utime-cp);
if ((in_arc==-1)&&(method==2)) /* i.e. no in_arc & the previous 2nd
iteration was updating delta2 */
mode=1; /* in such case, we can use the mode 1 to update pi, since
we don't need to compute the new delta2 from the begin*/
else
mode=0; /* either we found an in_arc or the previous 2nd iteraton
was updating delta1, we had better compute the new
delta2 from the beginning */
}
}while (empty==0); /* if N* is not empty, we go on this scaling phase */
/* now go to next scaling phase, at this moment, empty=1, flag=0 or 1 */
for (i=0;i<(n_arc+n_node-1);i++) /* get all reduced cost to get eps later*/
{
star_arc[i].redu_cost=star_arc[i].cost-star_node[star_arc[i].from].pi+
star_node[star_arc[i].to].pi;
}
eps=max_cpij();
for (i=0;i<n_node;i++) /* all nodes are awake */
{
star_node[i].in_N=1;
star_node[i].sleep=0;
star_node[i].current_arc=0;/* set CurrentArc=FirstArc */
}
n_N=0; /*?????????*/
empty=0; /* now N is full */
times(&x);
cp=x.tms_utime;
method=1; /* when find_in_arc, we have to scan from FirstArc */
in_arc=find_in_arc(root, &in_direction, arcs_scanned1, eligibles,
&arcs_scanned0);
times(&x);
tin+=(x.tms_utime-cp);
mode=0;
/* if (in_arc==-2) originally, I set in_arc=-2 if I found N* bedome empty
empty=1; in find_in_arc, so I don't need to go to update_pi to
check if N* is empty or not, but I found this way is not
good enough, so, I don't use it now.
*/
}while(eps>1./n_node); /* finish all scaling phase once eps < 1/n_node */
dtin=((double)tin)/60;
dtout=((double)tout)/60;
dttree=((double)ttree)/60;
dtpi=((double)tpi)/60;
dtper=((double)tper)/60;
/*printf("n_d1=%d n_d2=%d\n",n_d1,n_d2);*/
printf("CPU time in find_in_arc is %f\n", dtin);
/* fprintf(summary,"CPU time in find_in_arc is %f\n", dtin);*/
printf("CPU time in find_out_arc is %f\n", dtout);
/* fprintf(summary,"CPU time in find_out_arc is %f\n", dtout);*/
printf("CPU time in update_tree is %f\n", dttree);
/* fprintf(summary,"CPU time in update_tree is %f\n", dttree);*/
printf("CPU time in update_pi is %f\n", dtpi);
/* fprintf(summary,"CPU time in update_pi is %f\n", dtpi);*/
}
