COMBINATORIAL_BLAS  1.6
auction.cpp
Go to the documentation of this file.
1 #include "../CombBLAS.h"
2 #include <mpi.h>
3 #include <sys/time.h>
4 #include <iostream>
5 #include <functional>
6 #include <algorithm>
7 #include <vector>
8 #include <string>
9 #include <sstream>
10 
11 
12 using namespace std;
13 using namespace combblas;
14 
15 bool prune, mvInvertMate, randMM, moreSplit;
16 int init;
17 bool randMaximal;
18 bool fewexp;
19 
20 
21 template <typename PARMAT>
22 void Symmetricize(PARMAT & A)
23 {
24  // boolean addition is practically a "logical or"
25  // therefore this doesn't destruct any links
26  PARMAT AT = A;
27  AT.Transpose();
28  A += AT;
29 }
30 
31 
32 
33 struct VertexType
34 {
35 public:
36 
37  // careful: secondMaxProfit should be -\max wij by default
38  // how can we pass that info to static VertexType id() so that SpMV can use it?
39  VertexType(int64_t oi=-1, double p = 0, double smp=-9999999)
40  {
41  objID = oi;
42  price = p;
43  secondMaxProfit = smp;
44  };
45 
46 
47  friend bool operator<(const VertexType & vtx1, const VertexType & vtx2 ){return vtx1.price < vtx2.price;};
48  friend ostream& operator<<(ostream& os, const VertexType & vertex ){os << "(" << vertex.objID << ", " << vertex.price << ", " << vertex.secondMaxProfit << ")"; return os;};
49 
50  // variables for the object
51  int64_t objID; // ultimately it will be the object with the max profit for a bidder
52  double price; //ultimately it will be the max profit for a bidder
53  double secondMaxProfit; //it will be the 2nd max profit for a bidder
54 
55 
56 };
57 
58 
59 // return the maximum and second maximum profits
60 struct max2 : public std::binary_function<VertexType, VertexType, VertexType>
61 {
62  const VertexType operator()(const VertexType& x, const VertexType& y) const
63  {
64  VertexType ret;
65  if(x.price > y.price)
66  {
67  ret = x;
68  if(x.secondMaxProfit < y.price) ret.secondMaxProfit = y.price;
69  }
70  else
71  {
72  ret = y;
73  if(y.secondMaxProfit < x.price) ret.secondMaxProfit = x.price;
74  }
75 
76  return ret;
77  }
78 };
79 
80 
81 
82 struct SubMaxSR
83 {
84  static VertexType id(){ return VertexType(); };
85  static bool returnedSAID() { return false; }
86  static MPI_Op mpi_op() { return MPIOp<max2, VertexType>::op(); };
87 
88 
89 
90  // addition compute the maximum and second maximum profit
91  static VertexType add(const VertexType & arg1, const VertexType & arg2)
92  {
93  return max2()(arg1, arg2);
94  }
95 
96  // multiplication computes profit of an object to a bidder
97  // profit_j = cij - price_j
98  static VertexType multiply(const double & arg1, const VertexType & arg2)
99  {
100  // if the matrix is boolean, arg1=1
101  return VertexType(arg2.objID, arg1 - arg2.price, arg2.secondMaxProfit);
102  }
103 
104  static void axpy(const double a, const VertexType & x, VertexType & y)
105  {
106  y = add(y, multiply(a, x));
107  }
108 };
109 
110 
111 
112 typedef SpParMat < int64_t, bool, SpDCCols<int64_t,bool> > PSpMat_Bool;
113 typedef SpParMat < int64_t, bool, SpDCCols<int32_t,bool> > PSpMat_s32p64;
114 typedef SpParMat < int64_t, int64_t, SpDCCols<int64_t,int64_t> > PSpMat_Int64;
115 typedef SpParMat < int64_t, float, SpDCCols<int64_t,float> > PSpMat_float;
116 void maximumMatching(PSpMat_s32p64 & Aeff, FullyDistVec<int64_t, int64_t>& mateRow2Col,
117  FullyDistVec<int64_t, int64_t>& mateCol2Row);
118 void auction(PSpMat_s32p64 & A, FullyDistVec<int64_t, int64_t>& mateRow2Col,
119  FullyDistVec<int64_t, int64_t>& mateCol2Row);
120 template <class IT, class NT>
121 bool isMaximalmatching(PSpMat_Int64 & A, FullyDistVec<IT,NT> & mateRow2Col, FullyDistVec<IT,NT> & mateCol2Row,
122  FullyDistSpVec<int64_t, int64_t> unmatchedRow, FullyDistSpVec<int64_t, int64_t> unmatchedCol);
123 
124 
125 
126 
127 /*
128  Remove isolated vertices and purmute
129  */
130 void removeIsolated(PSpMat_Bool & A)
131 {
132 
133  int nprocs, myrank;
134  MPI_Comm_size(MPI_COMM_WORLD,&nprocs);
135  MPI_Comm_rank(MPI_COMM_WORLD,&myrank);
136 
137 
138  FullyDistVec<int64_t, int64_t> * ColSums = new FullyDistVec<int64_t, int64_t>(A.getcommgrid());
139  FullyDistVec<int64_t, int64_t> * RowSums = new FullyDistVec<int64_t, int64_t>(A.getcommgrid());
140  FullyDistVec<int64_t, int64_t> nonisoRowV; // id's of non-isolated (connected) Row vertices
141  FullyDistVec<int64_t, int64_t> nonisoColV; // id's of non-isolated (connected) Col vertices
142  FullyDistVec<int64_t, int64_t> nonisov; // id's of non-isolated (connected) vertices
143 
144  A.Reduce(*ColSums, Column, plus<int64_t>(), static_cast<int64_t>(0));
145  A.Reduce(*RowSums, Row, plus<int64_t>(), static_cast<int64_t>(0));
146 
147  // this steps for general graph
148  /*
149  ColSums->EWiseApply(*RowSums, plus<int64_t>()); not needed for bipartite graph
150  nonisov = ColSums->FindInds(bind2nd(greater<int64_t>(), 0));
151  nonisov.RandPerm(); // so that A(v,v) is load-balanced (both memory and time wise)
152  A.operator()(nonisov, nonisov, true); // in-place permute to save memory
153  */
154 
155  // this steps for bipartite graph
156  nonisoColV = ColSums->FindInds(bind2nd(greater<int64_t>(), 0));
157  nonisoRowV = RowSums->FindInds(bind2nd(greater<int64_t>(), 0));
158  delete ColSums;
159  delete RowSums;
160 
161 
162  {
163  nonisoColV.RandPerm();
164  nonisoRowV.RandPerm();
165  }
166 
167 
168  int64_t nrows1=A.getnrow(), ncols1=A.getncol(), nnz1 = A.getnnz();
169  double avgDeg1 = (double) nnz1/(nrows1+ncols1);
170 
171 
172  A.operator()(nonisoRowV, nonisoColV, true);
173 
174  int64_t nrows2=A.getnrow(), ncols2=A.getncol(), nnz2 = A.getnnz();
175  double avgDeg2 = (double) nnz2/(nrows2+ncols2);
176 
177 
178  if(myrank == 0)
179  {
180  cout << "ncol nrows nedges deg \n";
181  cout << nrows1 << " " << ncols1 << " " << nnz1 << " " << avgDeg1 << " \n";
182  cout << nrows2 << " " << ncols2 << " " << nnz2 << " " << avgDeg2 << " \n";
183  }
184 
185  MPI_Barrier(MPI_COMM_WORLD);
186 
187 
188 }
189 
190 
191 
192 
193 
194 int main(int argc, char* argv[])
195 {
196 
197  // ------------ initialize MPI ---------------
198  int provided;
199  MPI_Init_thread(&argc, &argv, MPI_THREAD_SERIALIZED, &provided);
200  if (provided < MPI_THREAD_SERIALIZED)
201  {
202  printf("ERROR: The MPI library does not have MPI_THREAD_SERIALIZED support\n");
203  MPI_Abort(MPI_COMM_WORLD, 1);
204  }
205  int nprocs, myrank;
206  MPI_Comm_size(MPI_COMM_WORLD,&nprocs);
207  MPI_Comm_rank(MPI_COMM_WORLD,&myrank);
208  if(argc < 3)
209  {
210  //ShowUsage();
211  MPI_Finalize();
212  return -1;
213  }
214 
215 
216  // ------------ Process input arguments and build matrix ---------------
217  {
218 
219  PSpMat_Bool * ABool;
220  PSpMat_s32p64 ALocalT;
221  ostringstream tinfo;
222  double t01, t02;
223  if(string(argv[1]) == string("input")) // input option
224  {
225  ABool = new PSpMat_Bool();
226 
227  string filename(argv[2]);
228  tinfo.str("");
229  tinfo << "**** Reading input matrix: " << filename << " ******* " << endl;
230  SpParHelper::Print(tinfo.str());
231  t01 = MPI_Wtime();
232  ABool->ParallelReadMM(filename, false, maximum<bool>());
233  t02 = MPI_Wtime();
234  ABool->PrintInfo();
235  tinfo.str("");
236  tinfo << "Reader took " << t02-t01 << " seconds" << endl;
237  SpParHelper::Print(tinfo.str());
238  //GetOptions(argv+3, argc-3);
239 
240  }
241  else if(argc < 4)
242  {
243  //ShowUsage();
244  MPI_Finalize();
245  return -1;
246  }
247  else
248  {
249  unsigned scale = (unsigned) atoi(argv[2]);
250  unsigned EDGEFACTOR = (unsigned) atoi(argv[3]);
251  double initiator[4];
252  if(string(argv[1]) == string("er"))
253  {
254  initiator[0] = .25;
255  initiator[1] = .25;
256  initiator[2] = .25;
257  initiator[3] = .25;
258  cout << "ER ******** \n";
259  }
260  else if(string(argv[1]) == string("g500"))
261  {
262  initiator[0] = .57;
263  initiator[1] = .19;
264  initiator[2] = .19;
265  initiator[3] = .05;
266  cout << "g500 ******** \n";
267  }
268  else if(string(argv[1]) == string("ssca"))
269  {
270  initiator[0] = .6;
271  initiator[1] = .4/3;
272  initiator[2] = .4/3;
273  initiator[3] = .4/3;
274  cout << "ER ******** \n";
275  }
276  else
277  {
278  if(myrank == 0)
279  printf("The input type - %s - is not recognized.\n", argv[2]);
280  MPI_Abort(MPI_COMM_WORLD, 1);
281  }
282 
283  SpParHelper::Print("Generating input matrix....\n");
284  t01 = MPI_Wtime();
285  DistEdgeList<int64_t> * DEL = new DistEdgeList<int64_t>();
286  DEL->GenGraph500Data(initiator, scale, EDGEFACTOR, true, true);
287  ABool = new PSpMat_Bool(*DEL, false);
288  delete DEL;
289  t02 = MPI_Wtime();
290  ABool->PrintInfo();
291  tinfo.str("");
292  tinfo << "Generator took " << t02-t01 << " seconds" << endl;
293  SpParHelper::Print(tinfo.str());
294 
295  Symmetricize(*ABool);
296  //removeIsolated(*ABool);
297  SpParHelper::Print("Generated matrix symmetricized....\n");
298  ABool->PrintInfo();
299 
300  //GetOptions(argv+4, argc-4);
301 
302  }
303 
304 
305  // randomly permute for load balance
306  SpParHelper::Print("Performing random permutation of matrix.\n");
307  FullyDistVec<int64_t, int64_t> prow(ABool->getcommgrid());
308  FullyDistVec<int64_t, int64_t> pcol(ABool->getcommgrid());
309  prow.iota(ABool->getnrow(), 0);
310  pcol.iota(ABool->getncol(), 0);
311  prow.RandPerm();
312  pcol.RandPerm();
313  (*ABool)(prow, pcol, true);
314  SpParHelper::Print("Performed random permutation of matrix.\n");
315 
316 
317  PSpMat_s32p64 A = *ABool;
318 
319 
320  FullyDistVec<int64_t, int64_t> mateRow2Col ( A.getcommgrid(), A.getnrow(), (int64_t) -1);
321  FullyDistVec<int64_t, int64_t> mateCol2Row ( A.getcommgrid(), A.getncol(), (int64_t) -1);
322 
323  auction(A, mateRow2Col, mateCol2Row);
324 
325 
326 
327  }
328  MPI_Finalize();
329  return 0;
330 }
331 
332 
333 
334 
335 
336 
337 
338 void auction(PSpMat_s32p64 & A, FullyDistVec<int64_t, int64_t>& mateRow2Col,
339  FullyDistVec<int64_t, int64_t>& mateCol2Row)
340 {
341 
342  int nprocs, myrank;
343  MPI_Comm_size(MPI_COMM_WORLD,&nprocs);
344  MPI_Comm_rank(MPI_COMM_WORLD,&myrank);
345 
346  int64_t nrow = A.getnrow();
347  int64_t ncol = A.getncol();
348  FullyDistSpVec<int64_t, VertexType> fringeRow(A.getcommgrid(), nrow);
349  FullyDistSpVec<int64_t, int64_t> umFringeRow(A.getcommgrid(), nrow);
350  FullyDistVec<int64_t, int64_t> leaves ( A.getcommgrid(), ncol, (int64_t) -1);
351 
352  vector<vector<double> > timing;
353  vector<int> layers;
354  vector<int64_t> phaseMatched;
355  double t1, time_search, time_augment, time_phase;
356 
357  bool matched = true;
358  int phase = 0;
359  int totalLayer = 0;
360  int64_t numUnmatchedCol;
361 
362 
363 
364  FullyDistVec<int64_t, VertexType> objects ( A.getcommgrid(), ncol, VertexType());
365  // set index to value
366  objects.ApplyInd([](VertexType vtx, int64_t idx){return VertexType(idx, vtx.price, vtx.secondMaxProfit);});
367  FullyDistVec<int64_t, VertexType> bidders ( A.getcommgrid(), nrow, VertexType());
368 
369  // future: I need an SPMV that could return a dense vector of type other than the input
370  bidders = SpMV<SubMaxSR>(A, objects);
371 
372 
373  // Remove bidders without any profitable objects
374  FullyDistSpVec<int64_t, VertexType> activeBidders ( bidders, [](VertexType bidder){return bidder.price>0;});
375 
376  // remove matched bidders
377  // we have done unncessary computation for already matched bidders
378  // option1: bottom up style
379  // option2: masked SpMV
380 
381  activeBidders = EWiseApply<VertexType>(activeBidders, mateRow2Col,
382  [](VertexType vtx, int64_t mate){return vtx;},
383  [](VertexType vtx, int64_t mate){return mate==-1;},
384  false, VertexType());
385 
386 
387  // compute bid
388  activeBidders.Apply([](VertexType bidder){return VertexType(bidder.objID, bidder.price - bidder.secondMaxProfit);}); // I don't care secondMaxProfit anymore
389 
390 
391  // place bid
392  // objects need to select the best bidder
393  activeBidders.DebugPrint();
394  FullyDistSpVec<int64_t, VertexType> bidObject =
395  activeBidders.Invert(ncol,
396  [](VertexType bidder, int64_t idx){return bidder.objID;},
397  [](VertexType bidder, int64_t idx){return VertexType(idx, bidder.price);},
398  [](VertexType bid1, VertexType bid2){return bid1.price>bid2.price? bid1: bid2;}); // I don't care secondMaxProfit anymore
399 
400  bidObject.DebugPrint();
401 
402  // just creating a simplified object with the highest bidder
403  // mateCol2Row is used just as a mask
404  FullyDistSpVec<int64_t, int64_t> successfullBids = EWiseApply<int64_t>(bidObject, mateCol2Row,
405  [](VertexType vtx, int64_t mate){return vtx.objID;},
406  [](VertexType vtx, int64_t mate){return true;},
407  false, VertexType());
408 
409 
410  //mateCol2Row.DebugPrint();
411  // bidders previously matched to current successfull bids will become unmatched
412  FullyDistSpVec<int64_t, int64_t> revokedBids = EWiseApply<int64_t>(successfullBids, mateCol2Row,
413  [](int64_t newbidder, int64_t mate){return mate;},
414  [](int64_t newbidder, int64_t mate){return mate!=-1;},
415  false, (int64_t)-1);
416 
417 
418  mateCol2Row.Set(successfullBids);
419 
420  //cout << " djkfhksjdfh \n";
421  //successfullBids.DebugPrint();
422  //revokedBids.DebugPrint();
423 
424  // previously unmatched bidders that will be matched
425  FullyDistSpVec<int64_t, int64_t> successfullBidders = successfullBids.Invert(nrow);
426 
427  // previously matched bidders that will be unmatched
428  FullyDistSpVec<int64_t, int64_t> revokedBidders = revokedBids.Invert(nrow);
429  // they are mutually exclusive
430  successfullBidders.DebugPrint();
431  revokedBidders.DebugPrint();
432 
433  mateRow2Col.Set(successfullBidders);
434  revokedBidders.Apply([](int64_t prevmate){return (int64_t)-1;});
435 
436  //mateRow2Col.Set(revokedBidders);
437 
438 
439 
440 
441 
442  //objects.DebugPrint();
443 
444 }
445 
combblas::FullyDistVec
Definition: FullyDistSpVec.h:53
combblas::FullyDistVec::Set
void Set(const FullyDistSpVec< IT, NT > &rhs)
Definition: FullyDistVec.cpp:1040
combblas::FullyDistVec::RandPerm
void RandPerm()
Definition: FullyDistVec.cpp:795
combblas::FullyDistVec::FindInds
FullyDistVec< IT, IT > FindInds(_Predicate pred) const
Return the indices where pred is true.
Definition: FullyDistVec.cpp:405
combblas
Definition: CCGrid.h:4
maximumMatching
void maximumMatching(PSpMat_s32p64 &Aeff, FullyDistVec< int64_t, int64_t > &mateRow2Col, FullyDistVec< int64_t, int64_t > &mateCol2Row)
PSpMat_Int64
SpParMat< int64_t, int64_t, SpDCCols< int64_t, int64_t > > PSpMat_Int64
Definition: auction.cpp:114
VertexType::operator<<
friend ostream & operator<<(ostream &os, const VertexType &vertex)
Definition: auction.cpp:48
isMaximalmatching
bool isMaximalmatching(PSpMat_Int64 &A, FullyDistVec< IT, NT > &mateRow2Col, FullyDistVec< IT, NT > &mateCol2Row, FullyDistSpVec< int64_t, int64_t > unmatchedRow, FullyDistSpVec< int64_t, int64_t > unmatchedCol)
max2
Definition: auction.cpp:60
EDGEFACTOR
#define EDGEFACTOR
Definition: DirOptBFS.cpp:81
moreSplit
bool moreSplit
Definition: auction.cpp:15
int64_t
long int64_t
Definition: compat.h:21
combblas::FullyDistVec::iota
void iota(IT globalsize, NT first)
Definition: FullyDistVec.cpp:928
SubMaxSR::returnedSAID
static bool returnedSAID()
Definition: auction.cpp:85
combblas::FullyDistVec::ApplyInd
void ApplyInd(_BinaryOperation __binary_op)
Definition: FullyDistVec.h:188
combblas::SpParMat::getcommgrid
std::shared_ptr< CommGrid > getcommgrid() const
Definition: SpParMat.h:275
VertexType::VertexType
VertexType(int64_t oi=-1, double p=0, double smp=-9999999)
Definition: auction.cpp:39
randMaximal
bool randMaximal
Definition: auction.cpp:17
PSpMat_s32p64
SpParMat< int64_t, bool, SpDCCols< int32_t, bool > > PSpMat_s32p64
Definition: auction.cpp:113
mvInvertMate
bool mvInvertMate
Definition: auction.cpp:15
combblas::FullyDistSpVec
Definition: FullyDistSpVec.h:73
combblas::SpParMat::getncol
IT getncol() const
Definition: SpParMat.cpp:694
combblas::multiply
SpDCCols< IT, NT > * multiply(SpDCCols< IT, NT > &splitA, SpDCCols< IT, NT > &splitB, CCGrid &CMG, bool isBT, bool threaded)
Definition: Multiplier.h:11
combblas::FullyDistSpVec::Apply
void Apply(_UnaryOperation __unary_op)
Definition: FullyDistSpVec.h:237
combblas::SpParMat
Definition: BFSFriends.h:47
SubMaxSR::multiply
static VertexType multiply(const double &arg1, const VertexType &arg2)
Definition: auction.cpp:98
combblas::SpParMat::getnrow
IT getnrow() const
Definition: SpParMat.cpp:685
combblas::SpParMat::ParallelReadMM
void ParallelReadMM(const std::string &filename, bool onebased, _BinaryOperation BinOp)
Definition: SpParMat.cpp:3417
combblas::DistEdgeList::GenGraph500Data
void GenGraph500Data(double initiator[4], int log_numverts, int edgefactor, bool scramble=false, bool packed=false)
Definition: DistEdgeList.cpp:223
A
double A
SubMaxSR::mpi_op
static MPI_Op mpi_op()
Definition: auction.cpp:86
combblas::MPIOp
Definition: MPIOp.h:68
prune
bool prune
Definition: auction.cpp:15
combblas::maximum
Compute the maximum of two values.
Definition: Operations.h:154
removeIsolated
void removeIsolated(PSpMat_Bool &A)
Definition: auction.cpp:130
PSpMat_Bool
SpParMat< int64_t, bool, SpDCCols< int64_t, bool > > PSpMat_Bool
Definition: auction.cpp:112
fewexp
bool fewexp
Definition: auction.cpp:18
combblas::DistEdgeList
Definition: DistEdgeList.h:81
randMM
bool randMM
Definition: auction.cpp:15
combblas::Column
@ Column
Definition: SpDefs.h:114
SubMaxSR::add
static VertexType add(const VertexType &arg1, const VertexType &arg2)
Definition: auction.cpp:91
VertexType::price
double price
Definition: auction.cpp:52
max2::operator()
const VertexType operator()(const VertexType &x, const VertexType &y) const
Definition: auction.cpp:62
VertexType::operator<
friend bool operator<(const VertexType &vtx1, const VertexType &vtx2)
Definition: auction.cpp:47
Symmetricize
void Symmetricize(PARMAT &A)
Definition: auction.cpp:22
init
int init
Definition: auction.cpp:16
SubMaxSR::axpy
static void axpy(const double a, const VertexType &x, VertexType &y)
Definition: auction.cpp:104
combblas::Row
@ Row
Definition: SpDefs.h:115
auction
void auction(PSpMat_s32p64 &A, FullyDistVec< int64_t, int64_t > &mateRow2Col, FullyDistVec< int64_t, int64_t > &mateCol2Row)
Definition: auction.cpp:338
combblas::VertexType
Definition: RestrictionOp.h:48
VertexType::secondMaxProfit
double secondMaxProfit
Definition: auction.cpp:53
SubMaxSR::id
static VertexType id()
Definition: auction.cpp:84
SubMaxSR
Definition: auction.cpp:82
combblas::FullyDistSpVec::DebugPrint
void DebugPrint()
Definition: FullyDistSpVec.cpp:1694
combblas::SpParMat::PrintInfo
void PrintInfo() const
Definition: SpParMat.cpp:2387
combblas::FullyDistSpVec::Invert
FullyDistSpVec< IT, NT > Invert(IT globallen)
Definition: FullyDistSpVec.cpp:1901
PSpMat_float
SpParMat< int64_t, float, SpDCCols< int64_t, float > > PSpMat_float
Definition: auction.cpp:115
main
int main(int argc, char *argv[])
Definition: auction.cpp:194