1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214
|
//------------------------------------------------------------------------------
// GB_enumify_mxm: enumerate a GrB_mxm problem
//------------------------------------------------------------------------------
// SuiteSparse:GraphBLAS, Timothy A. Davis, (c) 2021, All Rights Reserved.
// SPDX-License-Identifier: Apache-2.0
//------------------------------------------------------------------------------
#include "GB.h"
#include "GB_stringify.h"
// dot3: C<M>=A'*B, no accum
// saxpy
// inplace C_in is full/bitmap
// C_in <M> += A*B monoid ztype doesn't cast (= accum->ytype)
// C_in <M> = A*B monoid ztype casts to C_in->type
// ...
// accum is not present. Kernels that use it would require accum to be
// the same as the monoid binary operator.
void GB_enumify_mxm // enumerate a GrB_mxm problem
(
// output: // future: may need to become 2 x uint64
uint64_t *scode, // unique encoding of the entire semiring
// input:
// C matrix:
bool C_iso, // if true, semiring is ignored
int C_sparsity, // sparse, hyper, bitmap, or full
GrB_Type ctype, // C=((ctype) T) is the final typecast
// M matrix:
GrB_Matrix M, // may be NULL
bool Mask_struct, // mask is structural
bool Mask_comp, // mask is complemented
// semiring:
GrB_Semiring semiring, // the semiring to enumify
bool flipxy, // multiplier is: mult(a,b) or mult(b,a)
// A and B:
GrB_Matrix A,
GrB_Matrix B
)
{
//--------------------------------------------------------------------------
// handle the C_iso case
//--------------------------------------------------------------------------
if (C_iso)
{
semiring = GxB_ANY_PAIR_BOOL ;
flipxy = false ;
}
//--------------------------------------------------------------------------
// get the semiring
//--------------------------------------------------------------------------
// GxB_print (semiring, 3) ;
GrB_Monoid add = semiring->add ;
GrB_BinaryOp mult = semiring->multiply ;
GrB_BinaryOp addop = add->op ;
//--------------------------------------------------------------------------
// get the types
//--------------------------------------------------------------------------
GrB_Type atype = A->type ;
GrB_Type btype = B->type ;
GrB_Type mtype = (M == NULL) ? NULL : M->type ;
GrB_Type xtype = mult->xtype ;
GrB_Type ytype = mult->ytype ;
GrB_Type ztype = mult->ztype ;
GB_Opcode mult_opcode = mult->opcode ;
GB_Opcode add_opcode = addop->opcode ;
GB_Type_code xcode = xtype->code ;
GB_Type_code ycode = ytype->code ;
GB_Type_code zcode = ztype->code ;
// these must always be true for any semiring:
ASSERT (mult->ztype == addop->ztype) ;
ASSERT (addop->xtype == addop->ztype && addop->ytype == addop->ztype) ;
//--------------------------------------------------------------------------
// rename redundant boolean operators
//--------------------------------------------------------------------------
// consider z = op(x,y) where both x and y are boolean:
// DIV becomes FIRST
// RDIV becomes SECOND
// MIN and TIMES become LAND
// MAX and PLUS become LOR
// NE, ISNE, RMINUS, and MINUS become LXOR
// ISEQ becomes EQ
// ISGT becomes GT
// ISLT becomes LT
// ISGE becomes GE
// ISLE becomes LE
if (zcode == GB_BOOL_code)
{
// rename the monoid
add_opcode = GB_boolean_rename (add_opcode) ;
}
if (xcode == GB_BOOL_code) // && (ycode == GB_BOOL_code)
{
// rename the multiplicative operator
mult_opcode = GB_boolean_rename (mult_opcode) ;
}
//--------------------------------------------------------------------------
// determine if A and/or B are value-agnostic
//--------------------------------------------------------------------------
// These 1st, 2nd, and pair operators are all handled by the flip, so if
// flipxy is still true, all of these booleans will be false.
bool op_is_first = (mult_opcode == GB_FIRST_binop_code ) ;
bool op_is_second = (mult_opcode == GB_SECOND_binop_code) ;
bool op_is_pair = (mult_opcode == GB_PAIR_binop_code) ;
bool A_is_pattern = op_is_second || op_is_pair ;
bool B_is_pattern = op_is_first || op_is_pair ;
//--------------------------------------------------------------------------
// enumify the multiplier
//--------------------------------------------------------------------------
int mult_ecode ;
GB_enumify_binop (&mult_ecode, mult_opcode, xcode, true) ;
//--------------------------------------------------------------------------
// enumify the monoid
//--------------------------------------------------------------------------
int add_ecode, id_ecode, term_ecode ;
GB_enumify_monoid (&add_ecode, &id_ecode, &term_ecode, add_opcode, zcode) ;
//--------------------------------------------------------------------------
// enumify the types
//--------------------------------------------------------------------------
int acode = A_is_pattern ? 0 : atype->code ; // 0 to 14
int bcode = B_is_pattern ? 0 : btype->code ; // 0 to 14
int ccode = C_iso ? 0 : ctype->code ; // 0 to 14
int A_iso_code = A->iso ? 1 : 0 ;
int B_iso_code = B->iso ? 1 : 0 ;
//--------------------------------------------------------------------------
// enumify the mask
//--------------------------------------------------------------------------
int mtype_code = (mtype == NULL) ? 0 : mtype->code ; // 0 to 14
int mask_ecode ;
GB_enumify_mask (&mask_ecode, mtype_code, Mask_struct, Mask_comp) ;
//--------------------------------------------------------------------------
// enumify the sparsity structures of C, M, A, and B
//--------------------------------------------------------------------------
int M_sparsity = GB_sparsity (M) ;
int A_sparsity = GB_sparsity (A) ;
int B_sparsity = GB_sparsity (B) ;
int csparsity, msparsity, asparsity, bsparsity ;
GB_enumify_sparsity (&csparsity, C_sparsity) ;
GB_enumify_sparsity (&msparsity, M_sparsity) ;
GB_enumify_sparsity (&asparsity, A_sparsity) ;
GB_enumify_sparsity (&bsparsity, B_sparsity) ;
//--------------------------------------------------------------------------
// construct the semiring scode
//--------------------------------------------------------------------------
// total scode bits: 62 (2 unused bits)
(*scode) =
// range bits
// monoid (4 hex digits)
// GB_LSHIFT (0 , 63) | // unused 1
GB_LSHIFT (add_ecode , 58) | // 0 to 22 5
GB_LSHIFT (id_ecode , 53) | // 0 to 31 5
GB_LSHIFT (term_ecode , 48) | // 0 to 31 5
// A and B iso properties, flipxy (1 hex digit)
// GB_LSHIFT (0 , 47) | // unused 1
GB_LSHIFT (A_iso_code , 46) | // 0 or 1 1
GB_LSHIFT (B_iso_code , 45) | // 0 or 1 1
GB_LSHIFT (flipxy , 44) | // 0 to 1 1
// multiplier, z = f(x,y) or f(y,x) (5 hex digits)
GB_LSHIFT (mult_ecode , 36) | // 0 to 139 8
GB_LSHIFT (zcode , 32) | // 0 to 14 4
GB_LSHIFT (xcode , 28) | // 0 to 14 4
GB_LSHIFT (ycode , 24) | // 0 to 14 4
// mask (one hex digit)
GB_LSHIFT (mask_ecode , 20) | // 0 to 13 4
// types of C, A, and B (3 hex digits)
GB_LSHIFT (ccode , 16) | // 0 to 14 4
GB_LSHIFT (acode , 12) | // 0 to 14 4
GB_LSHIFT (bcode , 8) | // 0 to 14 4
// sparsity structures of C, M, A, and B (2 hex digits)
GB_LSHIFT (csparsity , 6) | // 0 to 3 2
GB_LSHIFT (msparsity , 4) | // 0 to 3 2
GB_LSHIFT (asparsity , 2) | // 0 to 3 2
GB_LSHIFT (bsparsity , 0) ; // 0 to 3 2
}
|