1 /****************************************************************/ 2 /* Parallel Combinatorial BLAS Library (for Graph Computations) */ 3 /* version 1.6 -------------------------------------------------*/ 4 /* date: 6/15/2017 ---------------------------------------------*/ 5 /* authors: Ariful Azad, Aydin Buluc --------------------------*/ 6 /****************************************************************/ 7 /* 8 Copyright (c) 2010-2017, The Regents of the University of California 9 10 Permission is hereby granted, free of charge, to any person obtaining a copy 11 of this software and associated documentation files (the "Software"), to deal 12 in the Software without restriction, including without limitation the rights 13 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 14 copies of the Software, and to permit persons to whom the Software is 15 furnished to do so, subject to the following conditions: 16 17 The above copyright notice and this permission notice shall be included in 18 all copies or substantial portions of the Software. 19 20 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 21 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 22 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 23 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 24 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 25 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 26 THE SOFTWARE. 27 */ 28 29 30 #ifndef _FULLY_DIST_VEC_H_ 31 #define _FULLY_DIST_VEC_H_ 32 33 #include <iostream> 34 #include <fstream> 35 #include <vector> 36 #include <utility> 37 #include <iterator> 38 #include <random> 39 #include "CombBLAS.h" 40 #include "CommGrid.h" 41 #include "FullyDist.h" 42 #include "Exception.h" 43 44 namespace combblas { 45 46 template <class IT, class NT> 47 class FullyDistSpVec; 48 49 template <class IT, class NT, class DER> 50 class SpParMat; 51 52 template <class IT> 53 class DistEdgeList; 54 55 template <class IU, class NU> 56 class DenseVectorLocalIterator; 57 58 // ABAB: As opposed to SpParMat, IT here is used to encode global size and global indices; 59 // therefore it can not be 32-bits, in general. 60 template <class IT, class NT> 61 class FullyDistVec: public FullyDist<IT,NT, typename combblas::disable_if< combblas::is_boolean<NT>::value, NT >::type > 62 { 63 public: 64 FullyDistVec ( ); 65 FullyDistVec ( IT globallen, NT initval); 66 FullyDistVec ( std::shared_ptr<CommGrid> grid); 67 FullyDistVec ( std::shared_ptr<CommGrid> grid, IT globallen, NT initval); 68 FullyDistVec ( const FullyDistSpVec<IT, NT> & rhs ); // Sparse -> Dense conversion constructor 69 FullyDistVec ( const std::vector<NT> & fillarr, std::shared_ptr<CommGrid> grid ); // initialize a FullyDistVec with a vector from each processor 70 71 72 template <class ITRHS, class NTRHS> 73 FullyDistVec ( const FullyDistVec<ITRHS, NTRHS>& rhs ); // type converter constructor 74 75 class ScalarReadSaveHandler 76 { 77 public: getNoNum(IT index)78 NT getNoNum(IT index) { return static_cast<NT>(1); } 79 80 template <typename c, typename t> read(std::basic_istream<c,t> & is,IT index)81 NT read(std::basic_istream<c,t>& is, IT index) 82 { 83 NT v; 84 is >> v; 85 return v; 86 } 87 88 template <typename c, typename t> save(std::basic_ostream<c,t> & os,const NT & v,IT index)89 void save(std::basic_ostream<c,t>& os, const NT& v, IT index) 90 { 91 os << v; 92 } 93 }; 94 95 template <class HANDLER> 96 void ParallelWrite(const std::string & filename, bool onebased, HANDLER handler, bool includeindices = true) 97 { 98 FullyDistSpVec<IT,NT> tmpSpVec = *this; // delegate 99 tmpSpVec.ParallelWrite(filename, onebased, handler, includeindices); 100 } 101 void ParallelWrite(const std::string & filename, bool onebased, bool includeindices = true) { ParallelWrite(filename, onebased, ScalarReadSaveHandler(), includeindices); }; 102 103 104 template <typename _BinaryOperation> ParallelRead(const std::string & filename,bool onebased,_BinaryOperation BinOp)105 void ParallelRead (const std::string & filename, bool onebased, _BinaryOperation BinOp) 106 { 107 FullyDistSpVec<IT,NT> tmpSpVec = *this; // delegate 108 tmpSpVec.ParallelRead(filename, onebased, BinOp); 109 *this = tmpSpVec; // sparse -> dense conversion 110 } 111 112 template <class HANDLER> 113 std::ifstream& ReadDistribute (std::ifstream& infile, int master, HANDLER handler); ReadDistribute(std::ifstream & infile,int master)114 std::ifstream& ReadDistribute (std::ifstream& infile, int master) { return ReadDistribute(infile, master, ScalarReadSaveHandler()); } 115 116 template <class HANDLER> 117 void SaveGathered(std::ofstream& outfile, int master, HANDLER handler, bool printProcSplits = false); SaveGathered(std::ofstream & outfile,int master)118 void SaveGathered(std::ofstream& outfile, int master) { SaveGathered(outfile, master, ScalarReadSaveHandler(), false); } 119 120 121 template <class ITRHS, class NTRHS> 122 FullyDistVec<IT,NT> & operator=(const FullyDistVec< ITRHS,NTRHS > & rhs); // assignment with type conversion 123 FullyDistVec<IT,NT> & operator=(const FullyDistVec<IT,NT> & rhs); //!< Actual assignment operator 124 FullyDistVec<IT,NT> & operator=(const FullyDistSpVec<IT,NT> & rhs); //!< FullyDistSpVec->FullyDistVec conversion operator 125 126 FullyDistVec<IT,NT> & operator=(NT fixedval) // assign fixed value 127 { 128 #ifdef _OPENMP 129 #pragma omp parallel for 130 #endif 131 for(IT i=0; i < arr.size(); ++i) 132 arr[i] = fixedval; 133 return *this; 134 } 135 FullyDistVec<IT,NT> operator() (const FullyDistVec<IT,IT> & ri) const; //<! subsref 136 137 FullyDistVec<IT,NT> & operator+=(const FullyDistSpVec<IT,NT> & rhs); 138 FullyDistVec<IT,NT> & operator+=(const FullyDistVec<IT,NT> & rhs); 139 FullyDistVec<IT,NT> & operator-=(const FullyDistSpVec<IT,NT> & rhs); 140 FullyDistVec<IT,NT> & operator-=(const FullyDistVec<IT,NT> & rhs); 141 bool operator==(const FullyDistVec<IT,NT> & rhs) const; 142 143 void SetElement (IT indx, NT numx); // element-wise assignment SetLocalElement(IT index,NT value)144 void SetLocalElement(IT index, NT value) { arr[index] = value; }; // no checks, local index 145 NT GetElement (IT indx) const; // element-wise fetch 146 NT operator[](IT indx) const // more c++ like API 147 { 148 return GetElement(indx); 149 } 150 151 void Set(const FullyDistSpVec< IT,NT > & rhs); 152 template <class NT1, typename _BinaryOperationIdx, typename _BinaryOperationVal> 153 void GSet (const FullyDistSpVec<IT,NT1> & spVec, _BinaryOperationIdx __binopIdx, _BinaryOperationVal __binopVal, MPI_Win win); 154 template <class NT1, typename _BinaryOperationIdx> 155 FullyDistSpVec<IT,NT> GGet (const FullyDistSpVec<IT,NT1> & spVec, _BinaryOperationIdx __binopIdx, NT nullValue); 156 157 void iota(IT globalsize, NT first); 158 void RandPerm(); // randomly permute the vector 159 FullyDistVec<IT,IT> sort(); // sort and return the permutation 160 161 using FullyDist<IT,NT,typename combblas::disable_if< combblas::is_boolean<NT>::value, NT >::type>::LengthUntil; 162 using FullyDist<IT,NT,typename combblas::disable_if< combblas::is_boolean<NT>::value, NT >::type>::TotalLength; 163 using FullyDist<IT,NT,typename combblas::disable_if< combblas::is_boolean<NT>::value, NT >::type>::Owner; 164 using FullyDist<IT,NT,typename combblas::disable_if< combblas::is_boolean<NT>::value, NT >::type>::MyLocLength; LocArrSize()165 IT LocArrSize() const { return arr.size(); } // = MyLocLength() once arr is resized 166 //TODO: we should change this function and return the vector directly GetLocArr()167 const NT * GetLocArr() const { return arr.data(); } // = MyLocLength() once arr is resized 168 169 170 template <typename _Predicate> 171 FullyDistSpVec<IT,NT> Find(_Predicate pred) const; //!< Return the elements for which pred is true 172 173 FullyDistSpVec<IT,NT> Find(NT val) const; //!< Return the elements val is found 174 175 template <typename _Predicate> 176 FullyDistVec<IT,IT> FindInds(_Predicate pred) const; //!< Return the indices where pred is true 177 178 template <typename _Predicate> 179 IT Count(_Predicate pred) const; //!< Return the number of elements for which pred is true 180 181 template <typename _UnaryOperation> Apply(_UnaryOperation __unary_op)182 void Apply(_UnaryOperation __unary_op) 183 { 184 std::transform(arr.begin(), arr.end(), arr.begin(), __unary_op); 185 } 186 187 template <typename _BinaryOperation> ApplyInd(_BinaryOperation __binary_op)188 void ApplyInd(_BinaryOperation __binary_op) 189 { 190 IT offset = LengthUntil(); 191 #ifdef _OPENMP 192 #pragma omp parallel for 193 #endif 194 for(size_t i=0; i < arr.size(); ++i) 195 arr[i] = __binary_op(arr[i], i + offset); 196 } 197 198 template <typename _UnaryOperation, typename IRRELEVANT_NT> 199 void Apply(_UnaryOperation __unary_op, const FullyDistSpVec<IT,IRRELEVANT_NT>& mask); 200 201 // extended callback versions 202 template <typename _BinaryOperation, typename _BinaryPredicate, class NT2> 203 void EWiseApply(const FullyDistVec<IT,NT2> & other, _BinaryOperation __binary_op, _BinaryPredicate _do_op, const bool useExtendedBinOp); 204 template <typename _BinaryOperation, typename _BinaryPredicate, class NT2> 205 void EWiseApply(const FullyDistSpVec<IT,NT2> & other, _BinaryOperation __binary_op, _BinaryPredicate _do_op, bool applyNulls, NT2 nullValue, const bool useExtendedBinOp); 206 207 // plain fallback versions 208 template <typename _BinaryOperation, typename _BinaryPredicate, class NT2> EWiseApply(const FullyDistVec<IT,NT2> & other,_BinaryOperation __binary_op,_BinaryPredicate _do_op)209 void EWiseApply(const FullyDistVec<IT,NT2> & other, _BinaryOperation __binary_op, _BinaryPredicate _do_op) 210 { 211 EWiseApply(other, 212 EWiseExtToPlainAdapter<NT, NT, NT2, _BinaryOperation>(__binary_op), 213 EWiseExtToPlainAdapter<bool, NT, NT2, _BinaryPredicate>(_do_op), 214 true); 215 } 216 template <typename _BinaryOperation, typename _BinaryPredicate, class NT2> EWiseApply(const FullyDistSpVec<IT,NT2> & other,_BinaryOperation __binary_op,_BinaryPredicate _do_op,bool applyNulls,NT2 nullValue)217 void EWiseApply(const FullyDistSpVec<IT,NT2> & other, _BinaryOperation __binary_op, _BinaryPredicate _do_op, bool applyNulls, NT2 nullValue) 218 { 219 EWiseApply(other, 220 EWiseExtToPlainAdapter<NT, NT, NT2, _BinaryOperation>(__binary_op), 221 EWiseExtToPlainAdapter<bool, NT, NT2, _BinaryPredicate>(_do_op), 222 applyNulls, nullValue, true); 223 } 224 225 226 template <typename T1, typename T2> 227 class retTrue { 228 public: operator()229 bool operator()(const T1& x, const T2& y) 230 { 231 return true; 232 } 233 }; 234 235 template <typename _BinaryOperation, class NT2> EWiseApply(const FullyDistVec<IT,NT2> & other,_BinaryOperation __binary_op)236 void EWiseApply(const FullyDistVec<IT,NT2> & other, _BinaryOperation __binary_op) 237 { 238 this->EWiseApply(other, __binary_op, retTrue<NT, NT2>()); 239 } 240 template <typename _BinaryOperation, class NT2> EWiseApply(const FullyDistSpVec<IT,NT2> & other,_BinaryOperation __binary_op,bool applyNulls,NT2 nullValue)241 void EWiseApply(const FullyDistSpVec<IT,NT2> & other, _BinaryOperation __binary_op, bool applyNulls, NT2 nullValue) 242 { 243 this->EWiseApply(other, __binary_op, retTrue<NT, NT2>(), applyNulls, nullValue); 244 } 245 PrintToFile(std::string prefix)246 void PrintToFile(std::string prefix) 247 { 248 std::ofstream output; 249 commGrid->OpenDebugFile(prefix, output); 250 std::copy(arr.begin(), arr.end(), std::ostream_iterator<NT> (output, " ")); 251 output << std::endl; 252 output.close(); 253 } 254 255 void PrintInfo(std::string vectorname) const; 256 void DebugPrint(); getcommgrid()257 std::shared_ptr<CommGrid> getcommgrid() const { return commGrid; } 258 259 std::pair<IT, NT> MinElement() const; // returns <index, value> pair of global minimum 260 261 262 template <typename _BinaryOperation> 263 NT Reduce(_BinaryOperation __binary_op, NT identity) const; //! Reduce can be used to implement max_element, for instance 264 265 template <typename OUT, typename _BinaryOperation, typename _UnaryOperation> 266 OUT Reduce(_BinaryOperation __binary_op, OUT default_val, _UnaryOperation __unary_op) const; 267 268 void SelectCandidates(double nver); 269 270 template <typename _BinaryOperation, typename OUT = typename std::result_of<_BinaryOperation&(NT,NT)>::type> 271 void EWiseOut(const FullyDistVec<IT,NT> & rhs, _BinaryOperation __binary_op, FullyDistVec<IT,OUT> & result); 272 273 using FullyDist<IT,NT,typename combblas::disable_if< combblas::is_boolean<NT>::value, NT >::type>::glen; 274 using FullyDist<IT,NT,typename combblas::disable_if< combblas::is_boolean<NT>::value, NT >::type>::commGrid; 275 276 private: 277 std::vector< NT > arr; 278 279 template <typename _BinaryOperation> 280 void EWise(const FullyDistVec<IT,NT> & rhs, _BinaryOperation __binary_op); 281 282 template <class IU, class NU> 283 friend class DenseParMat; 284 285 template <class IU, class NU, class UDER> 286 friend class SpParMat; 287 288 template <class IU, class NU> 289 friend class FullyDistVec; 290 291 template <class IU, class NU> 292 friend class FullyDistSpVec; 293 294 template <class IU, class NU> 295 friend class DenseVectorLocalIterator; 296 297 template <typename SR, typename IU, typename NUM, typename NUV, typename UDER> 298 friend FullyDistVec<IU,typename promote_trait<NUM,NUV>::T_promote> 299 SpMV (const SpParMat<IU,NUM,UDER> & A, const FullyDistVec<IU,NUV> & x ); 300 301 template <typename IU, typename NU1, typename NU2> 302 friend FullyDistSpVec<IU,typename promote_trait<NU1,NU2>::T_promote> 303 EWiseMult (const FullyDistSpVec<IU,NU1> & V, const FullyDistVec<IU,NU2> & W , bool exclude, NU2 zero); 304 305 template <typename IU, typename NU1, typename NU2, typename _BinaryOperation> 306 friend FullyDistSpVec<IU,typename promote_trait<NU1,NU2>::T_promote> 307 EWiseApply (const FullyDistSpVec<IU,NU1> & V, const FullyDistVec<IU,NU2> & W , _BinaryOperation _binary_op, typename promote_trait<NU1,NU2>::T_promote zero); 308 309 template <typename RET, typename IU, typename NU1, typename NU2, typename _BinaryOperation, typename _BinaryPredicate> 310 friend FullyDistSpVec<IU,RET> 311 EWiseApply (const FullyDistSpVec<IU,NU1> & V, const FullyDistVec<IU,NU2> & W , _BinaryOperation _binary_op, _BinaryPredicate _doOp, bool allowVNulls, NU1 Vzero, const bool useExtendedBinOp); 312 313 template <typename RET, typename IU, typename NU1, typename NU2, typename _BinaryOperation, typename _BinaryPredicate> 314 friend FullyDistSpVec<IU,RET> 315 EWiseApply_threaded (const FullyDistSpVec<IU,NU1> & V, const FullyDistVec<IU,NU2> & W , _BinaryOperation _binary_op, _BinaryPredicate _doOp, bool allowVNulls, NU1 Vzero, const bool useExtendedBinOp); 316 317 template <typename IU> 318 friend void RenameVertices(DistEdgeList<IU> & DEL); 319 320 template <typename IU, typename NU> 321 friend FullyDistVec<IU,NU> Concatenate ( std::vector< FullyDistVec<IU,NU> > & vecs); 322 323 template <typename IU, typename NU> 324 friend void Augment (FullyDistVec<int64_t, int64_t>& mateRow2Col, FullyDistVec<int64_t, int64_t>& mateCol2Row, 325 FullyDistVec<int64_t, int64_t>& parentsRow, FullyDistVec<int64_t, int64_t>& leaves); 326 template <class IU, class DER> 327 friend SpParMat<IU, bool, DER> PermMat (const FullyDistVec<IU,IU> & ri, const IU ncol); 328 329 330 friend void maximumMatching(SpParMat < int64_t, bool, SpDCCols<int64_t,bool> > & A, FullyDistVec<int64_t, int64_t>& mateRow2Col,FullyDistVec<int64_t, int64_t>& mateCol2Row); 331 }; 332 333 } 334 335 #include "FullyDistVec.cpp" 336 337 #endif 338