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 /** 31 * Operations used in parallel reductions and scans 32 **/ 33 34 #ifndef _OPERATIONS_H_ 35 #define _OPERATIONS_H_ 36 37 #include <iostream> 38 #include <functional> 39 #include <cmath> 40 #include <limits> 41 #include "psort/MersenneTwister.h" 42 43 namespace combblas { 44 45 template<typename T1, typename T2> 46 struct equal_first 47 { operatorequal_first48 bool operator()(std::pair<T1,T2> & lhs, std::pair<T1,T2> & rhs){ 49 return lhs.first == rhs.first; 50 } 51 }; 52 53 54 55 template<typename T> 56 struct myset: public std::unary_function<T, T> 57 { mysetmyset58 myset(T myvalue): value(myvalue) {}; 59 /** @returns value regardless of x */ operatormyset60 const T& operator()(const T& x) const 61 { 62 return value; 63 } 64 T value; 65 }; 66 67 68 template<typename T> 69 struct identity : public std::unary_function<T, T> 70 { 71 /** @returns x itself */ operatoridentity72 const T operator()(const T& x) const 73 { 74 return x; 75 } 76 }; 77 78 79 // Because identify reports ambiguity in PGI compilers 80 template<typename T> 81 struct myidentity : public std::unary_function<T, T> 82 { 83 /** @returns x itself */ operatormyidentity84 const T operator()(const T& x) const 85 { 86 return x; 87 } 88 }; 89 90 91 template<typename T> 92 struct totality : public std::unary_function<T, bool> 93 { 94 /** @returns true regardless */ operatortotality95 bool operator()(const T& x) const 96 { 97 return true; 98 } 99 }; 100 101 102 template<typename T> 103 struct safemultinv : public std::unary_function<T, T> 104 { operatorsafemultinv105 const T operator()(const T& x) const 106 { 107 T inf = std::numeric_limits<T>::max(); 108 return (x == 0) ? inf:(1/x); 109 } 110 }; 111 112 113 template<typename T> 114 struct sel2nd: public std::binary_function<T, T, T> 115 { operatorsel2nd116 const T& operator()(const T& x, const T & y) const 117 { 118 return y; 119 } 120 }; 121 122 template<typename T1, typename T2> 123 struct bintotality : public std::binary_function<T1, T2, bool> 124 { 125 /** @returns true regardless */ operatorbintotality126 bool operator()(const T1& x, const T2 & y) const 127 { 128 return true; 129 } 130 }; 131 132 133 134 /** 135 * binary_function<Arg1, Arg2, Result> 136 * This is left untemplated because pow() only makes sense for 137 * <double, int, double> , <double, double, double> , <float, float, float> 138 * and C++ can automatically upcast each case to <double, double, double> 139 */ 140 struct exponentiate : public std::binary_function<double, double, double> 141 { operatorexponentiate142 double operator()(double x, double y) const { return std::pow(x, y); } 143 }; 144 145 146 /** 147 * @brief Compute the maximum of two values. 148 * 149 * This binary function object computes the maximum of the two values 150 * it is given. When used with MPI and a type @c T that has an 151 * associated, built-in MPI data type, translates to @c MPI_MAX. 152 */ 153 template<typename T> 154 struct maximum : public std::binary_function<T, T, T> 155 { 156 /** @returns the maximum of x and y. */ operatormaximum157 const T operator()(const T& x, const T& y) const 158 { 159 return x < y? y : x; 160 } 161 }; 162 163 164 /** 165 * @brief Compute the minimum of two values. 166 * 167 * This binary function object computes the minimum of the two values 168 * it is given. When used with MPI and a type @c T that has an 169 * associated, built-in MPI data type, translates to @c MPI_MIN. 170 */ 171 template<typename T> 172 struct minimum : public std::binary_function<T, T, T> 173 { 174 /** @returns the minimum of x and y. */ operatorminimum175 const T operator()(const T& x, const T& y) const 176 { 177 return x < y? x : y; 178 } 179 }; 180 181 /** 182 * @brief With 50/50 chances, return a one of the operants 183 */ 184 template<typename T> 185 struct RandReduce : public std::binary_function<T, T, T> 186 { 187 /** @returns the minimum of x and y. */ operatorRandReduce188 const T operator()(const T& x, const T& y) 189 { 190 return (M.rand() < 0.5)? x : y; 191 } RandReduceRandReduce192 RandReduce() 193 { 194 #ifdef DETERMINISTIC 195 M = MTRand(1); 196 #else 197 M = MTRand(); // generate random numbers with Mersenne Twister 198 #endif 199 } 200 MTRand M; 201 }; 202 203 /** 204 * @brief Returns a special value (passed to the constructor of the functor) when both operants disagree 205 */ 206 template<typename T> 207 struct SetIfNotEqual : public std::binary_function<T, T, T> 208 { operatorSetIfNotEqual209 const T operator()(const T& x, const T& y) 210 { 211 if(x != y) 212 { 213 return valuetoset; 214 } 215 else 216 { 217 return x; 218 } 219 } SetIfNotEqualSetIfNotEqual220 SetIfNotEqual(T value):valuetoset(value) { }; 221 T valuetoset; 222 }; 223 224 225 /** 226 * @brief Compute the bitwise AND of two integral values. 227 * 228 * This binary function object computes the bitwise AND of the two 229 * values it is given. When used with MPI and a type @c T that has an 230 * associated, built-in MPI data type, translates to @c MPI_BAND. 231 */ 232 template<typename T> 233 struct bitwise_and : public std::binary_function<T, T, T> 234 { 235 /** @returns @c x & y. */ operatorbitwise_and236 T operator()(const T& x, const T& y) const 237 { 238 return x & y; 239 } 240 }; 241 242 243 /** 244 * @brief Compute the bitwise OR of two integral values. 245 * 246 * This binary function object computes the bitwise OR of the two 247 * values it is given. When used with MPI and a type @c T that has an 248 * associated, built-in MPI data type, translates to @c MPI_BOR. 249 */ 250 template<typename T> 251 struct bitwise_or : public std::binary_function<T, T, T> 252 { 253 /** @returns the @c x | y. */ operatorbitwise_or254 T operator()(const T& x, const T& y) const 255 { 256 return x | y; 257 } 258 }; 259 260 /** 261 * @brief Compute the logical exclusive OR of two integral values. 262 * 263 * This binary function object computes the logical exclusive of the 264 * two values it is given. When used with MPI and a type @c T that has 265 * an associated, built-in MPI data type, translates to @c MPI_LXOR. 266 */ 267 template<typename T> 268 struct logical_xor : public std::binary_function<T, T, T> 269 { 270 /** @returns the logical exclusive OR of x and y. */ operatorlogical_xor271 T operator()(const T& x, const T& y) const 272 { 273 return (x || y) && !(x && y); 274 } 275 }; 276 277 /** 278 * @brief Compute the bitwise exclusive OR of two integral values. 279 * 280 * This binary function object computes the bitwise exclusive OR of 281 * the two values it is given. When used with MPI and a type @c T that 282 * has an associated, built-in MPI data type, translates to @c 283 * MPI_BXOR. 284 */ 285 template<typename T> 286 struct bitwise_xor : public std::binary_function<T, T, T> 287 { 288 /** @returns @c x ^ y. */ operatorbitwise_xor289 T operator()(const T& x, const T& y) const 290 { 291 return x ^ y; 292 } 293 }; 294 295 } 296 297 298 299 #endif 300 301 302