53 #define EDGEFACTOR 5 // For MIS 55 #define PERCENTS 4 // testing with 4 different percentiles 61 template <
typename PARMAT>
72 struct DetSymmetricize:
public std::binary_function<TwitterEdge, TwitterEdge, TwitterEdge>
80 if(((g.latest + t.latest) & 1) == 1)
82 toret.latest = std::min(g.latest, t.latest);
86 toret.latest = std::max(g.latest, t.latest);
118 time_t mylatest =
static_cast<int64_t>(GlobalMT.
rand() * 10000);
138 struct randGen :
public std::unary_function<double, double>
142 return GlobalMT.
rand();
147 int main(
int argc,
char* argv[])
152 int provided, flag, claimed;
153 MPI_Init_thread(&argc, &argv, MPI_THREAD_FUNNELED, &provided );
154 MPI_Is_thread_main( &flag );
156 SpParHelper::Print(
"This thread called init_thread but Is_thread_main gave false\n");
157 MPI_Query_thread( &claimed );
158 if (claimed != provided)
159 SpParHelper::Print(
"Query thread gave different thread level than requested\n");
161 MPI_Init(&argc, &argv);
162 int cblas_splits = 1;
165 MPI_Comm_size(MPI_COMM_WORLD,&nprocs);
166 MPI_Comm_rank(MPI_COMM_WORLD,&myrank);
171 cout <<
"Usage: ./FilteredMIS <Scale>" << endl;
179 shared_ptr<CommGrid> fullWorld;
180 fullWorld.reset(
new CommGrid(MPI_COMM_WORLD, 0, 0) );
186 SpParHelper::Print(
"Using synthetic data, which we ALWAYS permute for load balance\n");
187 SpParHelper::Print(
"We only balance the original input, we don't repermute after each filter change\n");
188 SpParHelper::Print(
"BFS is run on UNDIRECTED graph, hence hitting CCs, and TEPS is bidirectional\n");
190 double initiator[4] = {.25, .25, .25, .25};
191 double t01 = MPI_Wtime();
194 unsigned scale =
static_cast<unsigned>(atoi(argv[1]));
196 outs <<
"Forcing scale to : " << scale << endl;
197 SpParHelper::Print(outs.str());
201 SpParHelper::Print(
"Generated renamed edge lists\n");
205 ostringstream loopinfo;
206 loopinfo <<
"Converted to Boolean and removed " << removed <<
" loops" << endl;
207 SpParHelper::Print(loopinfo.str());
212 double t02 = MPI_Wtime();
214 tinfo <<
"Generation took " << t02-t01 <<
" seconds" << endl;
215 SpParHelper::Print(tinfo.str());
219 ABool->
Reduce(oudegrees,
Column, plus<int64_t>(), static_cast<int64_t>(0));
220 ABool->
Reduce(indegrees,
Row, plus<int64_t>(), static_cast<int64_t>(0));
231 degrees.
EWiseApply(oudegrees, plus<int64_t>());
232 SpParHelper::Print(
"All degrees calculated\n");
237 outlb <<
"Load balance: " << balance << endl;
238 SpParHelper::Print(outlb.str());
244 SpParHelper::Print(
"Symmetricized\n");
249 SpParHelper::Print(
"Symmetricized Rands\n");
254 SpParHelper::Print(
"Found (and permuted) non-isolated vertices\n");
256 A(*nonisov, *nonisov,
true);
257 SpParHelper::Print(
"Dropped isolated vertices from input\n");
259 indegrees = indegrees(*nonisov);
260 oudegrees = oudegrees(*nonisov);
261 degrees = degrees(*nonisov);
272 outs <<
"Load balance of " <<
static_cast<float>(keep[i])/100 <<
"% filtered case: " << balance << endl;
273 SpParHelper::Print(outs.str());
276 BBool.
Reduce(degrees_filt[i],
Column, plus<int64_t>(), static_cast<int64_t>(0));
280 ostringstream outs_former;
281 outs_former <<
"Load balance: " << balance_former << endl;
282 SpParHelper::Print(outs_former.str());
284 for(
int trials =0; trials <
PERCENTS; trials++)
295 SpParHelper::Print(outs.str());
297 for(
int sruns = 0; sruns <
ITERS; ++sruns)
299 double t1 = MPI_Wtime();
329 SpMV<LatestRetwitterMIS>(
A,
C, min_neighbor_r,
false);
331 min_neighbor_r.PrintInfo(
"Neighbors");
335 min_neighbor_r.DebugPrint();
344 new_S_members = EWiseApply<uint8_t>(min_neighbor_r,
C,
return1_uint8(),
is2ndSmaller(),
true,
false, (double) 2.0, (
double) 2.0,
true);
349 new_S_members.PrintInfo(
"New members of the MIS");
353 new_S_members.DebugPrint();
360 C.PrintInfo(
"Entries to be removed from the Candidates set");
365 SpMV<LatestRetwitterSelect2nd>(
A, new_S_members, new_S_neighbors,
false);
372 C.PrintInfo(
"Candidates set after neighbors of MIS removed");
378 S.PrintInfo(
"The current MIS:");
380 double t2 = MPI_Wtime();
383 ositr <<
"MIS has " << S.getnnz() <<
" vertices" << endl;
384 SpParHelper::Print(ositr.str());
386 ostringstream ositr2;
387 ositr <<
"MIS time: " << t2-t1 <<
" seconds" << endl;
388 SpParHelper::Print(ositr.str());
390 TIMES[sruns] = t2-t1;
391 MISVS[sruns] = S.getnnz();
395 os <<
"Per iteration communication times: " << endl;
399 sort(MISVS, MISVS+ITERS);
400 os <<
"--------------------------" << endl;
401 os <<
"Min MIS vertices: " << MISVS[0] << endl;
402 os <<
"Median MIS vertices: " << (MISVS[(ITERS/2)-1] + MISVS[ITERS/2])/2 << endl;
403 os <<
"Max MIS vertices: " << MISVS[ITERS-1] << endl;
404 double mean = accumulate( MISVS, MISVS+ITERS, 0.0 )/
ITERS;
405 vector<double> zero_mean(ITERS);
406 transform(MISVS, MISVS+ITERS, zero_mean.begin(), bind2nd( minus<double>(), mean ));
408 double deviation = inner_product( zero_mean.begin(),zero_mean.end(), zero_mean.begin(), 0.0 );
409 deviation = sqrt( deviation / (ITERS-1) );
410 os <<
"Mean MIS vertices: " << mean << endl;
411 os <<
"STDDEV MIS vertices: " << deviation << endl;
412 os <<
"--------------------------" << endl;
414 sort(TIMES,TIMES+ITERS);
415 os <<
"Filter keeps " <<
static_cast<double>(keep[trials])/100.0 <<
" percentage of edges" << endl;
416 os <<
"Min time: " << TIMES[0] <<
" seconds" << endl;
417 os <<
"Median time: " << (TIMES[(ITERS/2)-1] + TIMES[ITERS/2])/2 <<
" seconds" << endl;
418 os <<
"Max time: " << TIMES[ITERS-1] <<
" seconds" << endl;
419 mean = accumulate( TIMES, TIMES+ITERS, 0.0 )/
ITERS;
420 transform(TIMES, TIMES+ITERS, zero_mean.begin(), bind2nd( minus<double>(), mean ));
421 deviation = inner_product( zero_mean.begin(),zero_mean.end(), zero_mean.begin(), 0.0 );
422 deviation = sqrt( deviation / (ITERS-1) );
423 os <<
"Mean time: " << mean <<
" seconds" << endl;
424 os <<
"STDDEV time: " << deviation <<
" seconds" << endl;
425 os <<
"--------------------------" << endl;
426 SpParHelper::Print(os.str());
double cblas_alltoalltime
FullyDistVec< IT, NT > Reduce(Dim dim, _BinaryOperation __binary_op, NT id, _UnaryOperation __unary_op) const
std::shared_ptr< CommGrid > getcommgrid() const
void Symmetricize(PARMAT &A)
void Apply(_UnaryOperation __unary_op)
void GenGraph500Data(double initiator[4], int log_numverts, int edgefactor, bool scramble=false, bool packed=false)
TwitterEdge operator()(const TwitterEdge &g, const TwitterEdge &t)
FullyDistVec< IT, IT > FindInds(_Predicate pred) const
Return the indices where pred is true.
float LoadImbalance() const
SpParMat< int64_t, TwitterEdge, SpDCCols< int64_t, TwitterEdge > > PSpMat_Twitter
void EWiseApply(const FullyDistVec< IT, NT2 > &other, _BinaryOperation __binary_op, _BinaryPredicate _do_op, const bool useExtendedBinOp)
void SymmetricizeRands(PSpMat_Twitter &A)
int main(int argc, char *argv[])
const TwitterEdge operator()(const TwitterEdge &x) const
SpParMat< int64_t, bool, SpDCCols< int64_t, bool > > PSpMat_Bool
double cblas_allgathertime
void Apply(_UnaryOperation __unary_op)
const double operator()(const double &ignore)
SpParMat< IT, NT, DER > Prune(_UnaryOperation __unary_op, bool inPlace=true)