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 _SEMIRINGS_H_ 31 #define _SEMIRINGS_H_ 32 33 #include <utility> 34 #include <climits> 35 #include <cmath> 36 #include "promote.h" 37 38 namespace combblas { 39 40 template <typename T> 41 struct inf_plus{ operatorinf_plus42 T operator()(const T& a, const T& b) const { 43 T inf = std::numeric_limits<T>::max(); 44 if (a == inf || b == inf){ 45 return inf; 46 } 47 return a + b; 48 } 49 }; 50 51 // This semiring is used in indexing (SpParMat::operator()) 52 template <class OUT> 53 struct BoolCopy2ndSRing 54 { idBoolCopy2ndSRing55 static OUT id() { return OUT(); } returnedSAIDBoolCopy2ndSRing56 static bool returnedSAID() { return false; } addBoolCopy2ndSRing57 static OUT add(const OUT & arg1, const OUT & arg2) 58 { 59 std::cout << "Add should not happen (BoolCopy2ndSRing)!" << std::endl; 60 throw std::string("Add should not happen!"); 61 std::exit(1); 62 return arg2; 63 } multiplyBoolCopy2ndSRing64 static const OUT& multiply(bool arg1, const OUT & arg2) 65 { 66 return arg2; 67 } axpyBoolCopy2ndSRing68 static void axpy(bool a, const OUT & x, OUT & y) 69 { 70 y = multiply(a, x); 71 } 72 mpi_opBoolCopy2ndSRing73 static MPI_Op mpi_op() 74 { 75 static MPI_Op mpiop; 76 static bool exists = false; 77 if (exists) 78 return mpiop; 79 else 80 { 81 MPI_Op_create(MPI_func, true, &mpiop); 82 exists = true; 83 return mpiop; 84 } 85 } 86 MPI_funcBoolCopy2ndSRing87 static void MPI_func(void * invec, void * inoutvec, int * len, MPI_Datatype *datatype) 88 { 89 if (*len > 0) 90 { 91 std::cout << "MPI Add should not happen (BoolCopy2ndSRing)!" << std::endl; 92 std::exit(1); 93 } 94 } 95 }; 96 97 // This semiring is used in indexing (SpParMat::operator()) 98 template <class OUT> 99 struct BoolCopy1stSRing 100 { idBoolCopy1stSRing101 static OUT id() { return OUT(); } returnedSAIDBoolCopy1stSRing102 static bool returnedSAID() { return false; } addBoolCopy1stSRing103 static OUT add(const OUT & arg1, const OUT & arg2) 104 { 105 std::cout << "Add should not happen (BoolCopy1stSRing)!" << std::endl; 106 throw std::string("Add should not happen!"); 107 std::exit(1); 108 return arg2; 109 } multiplyBoolCopy1stSRing110 static const OUT& multiply(const OUT & arg1, bool arg2) 111 { 112 return arg1; 113 } axpyBoolCopy1stSRing114 static void axpy(const OUT& a, bool x, OUT & y) 115 { 116 y = multiply(a, x); 117 } 118 mpi_opBoolCopy1stSRing119 static MPI_Op mpi_op() 120 { 121 static MPI_Op mpiop; 122 static bool exists = false; 123 if (exists) 124 return mpiop; 125 else 126 { 127 MPI_Op_create(MPI_func, true, &mpiop); 128 exists = true; 129 return mpiop; 130 } 131 } 132 MPI_funcBoolCopy1stSRing133 static void MPI_func(void * invec, void * inoutvec, int * len, MPI_Datatype *datatype) 134 { 135 if (*len > 0) 136 { 137 std::cout << "MPI Add should not happen (BoolCopy1stSRing)!" << std::endl; 138 std::exit(1); 139 } 140 } 141 }; 142 143 144 145 template <class T1, class T2, class OUT> 146 struct Select2ndSRing 147 { idSelect2ndSRing148 static OUT id() { return OUT(); } returnedSAIDSelect2ndSRing149 static bool returnedSAID() { return false; } mpi_opSelect2ndSRing150 static MPI_Op mpi_op() { return MPI_MAX; }; addSelect2ndSRing151 static OUT add(const OUT & arg1, const OUT & arg2) 152 { 153 return arg2; 154 } multiplySelect2ndSRing155 static OUT multiply(const T1 & arg1, const T2 & arg2) 156 { 157 // fragile since it wouldn't work with y <- x*A 158 return static_cast<OUT>(arg2); 159 } axpySelect2ndSRing160 static void axpy(T1 a, const T2 & x, OUT & y) 161 { 162 //y = add(y, multiply(a, x)); 163 y = multiply(a, x); 164 } 165 }; 166 167 template <class T1, class T2> 168 struct SelectMaxSRing 169 { 170 typedef typename promote_trait<T1,T2>::T_promote T_promote; idSelectMaxSRing171 static T_promote id() { return -1; }; returnedSAIDSelectMaxSRing172 static bool returnedSAID() { return false; } mpi_opSelectMaxSRing173 static MPI_Op mpi_op() { return MPI_MAX; }; addSelectMaxSRing174 static T_promote add(const T_promote & arg1, const T_promote & arg2) 175 { 176 return std::max(arg1, arg2); 177 } multiplySelectMaxSRing178 static T_promote multiply(const T1 & arg1, const T2 & arg2) 179 { 180 // we could have just returned arg2 but it would be 181 // fragile since it wouldn't work with y <- x*A 182 return (static_cast<T_promote>(arg1) * 183 static_cast<T_promote>(arg2) ); 184 } axpySelectMaxSRing185 static void axpy(T1 a, const T2 & x, T_promote & y) 186 { 187 y = std::max(y, static_cast<T_promote>(a*x)); 188 } 189 }; 190 191 192 // This one is used for BFS iteration 193 template <class T2> 194 struct SelectMaxSRing<bool, T2> 195 { 196 typedef T2 T_promote; 197 static T_promote id(){ return -1; }; 198 static bool returnedSAID() { return false; } 199 static MPI_Op mpi_op() { return MPI_MAX; }; 200 static T_promote add(const T_promote & arg1, const T_promote & arg2) 201 { 202 return std::max(arg1, arg2); 203 } 204 static T_promote multiply(const bool & arg1, const T2 & arg2) 205 { 206 return arg2; 207 } 208 static void axpy(bool a, const T2 & x, T_promote & y) 209 { 210 y = std::max(y, x); 211 } 212 }; 213 214 template <class T1, class T2> 215 struct PlusTimesSRing 216 { 217 typedef typename promote_trait<T1,T2>::T_promote T_promote; 218 static T_promote id(){ return 0; } 219 static bool returnedSAID() { return false; } 220 static MPI_Op mpi_op() { return MPI_SUM; }; 221 static T_promote add(const T_promote & arg1, const T_promote & arg2) 222 { 223 return arg1+arg2; 224 } 225 static T_promote multiply(const T1 & arg1, const T2 & arg2) 226 { 227 return (static_cast<T_promote>(arg1) * 228 static_cast<T_promote>(arg2) ); 229 } 230 static void axpy(T1 a, const T2 & x, T_promote & y) 231 { 232 y += a*x; 233 } 234 }; 235 236 237 template <class T1, class T2> 238 struct MinPlusSRing 239 { 240 typedef typename promote_trait<T1,T2>::T_promote T_promote; 241 static T_promote id() { return std::numeric_limits<T_promote>::max(); }; 242 static bool returnedSAID() { return false; } 243 static MPI_Op mpi_op() { return MPI_MIN; }; 244 static T_promote add(const T_promote & arg1, const T_promote & arg2) 245 { 246 return std::min(arg1, arg2); 247 } 248 static T_promote multiply(const T1 & arg1, const T2 & arg2) 249 { 250 return inf_plus< T_promote > 251 (static_cast<T_promote>(arg1), static_cast<T_promote>(arg2)); 252 } 253 static void axpy(T1 a, const T2 & x, T_promote & y) 254 { 255 y = std::min(y, multiply(a, x)); 256 } 257 }; 258 259 } 260 261 #endif 262