BeBOP Optimized Sparse Kernel Interface Library  1.0.1h
Defines | Functions
estfill.c File Reference

BCSR fill ratio estimator. More...

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <oski/common.h>
#include <oski/heur/estfill.h>

Defines

#define GET_BC(A, c, J)   (A)[((c)-1)*n + (J)]
#define INC_BC(A, c, J)   (A)[((c)-1)*n + (J)]++
#define ZERO_BC(A, c, J)   (A)[((c)-1)*n + (J)] = 0

Functions

static int EstimateBlockCounts (const oski_index_t *ptr, const oski_index_t *ind, oski_index_t base, oski_index_t m, oski_index_t n, oski_index_t r, oski_index_t max_c, double prob_examine, oski_index_t *p_nnz_est, oski_index_t *p_nb_est)
 Given an $m\times n$ CSR matrix $A$, estimates the fill ratio if the matrix were converted into $r\times c$ BCSR format.
static int CheckArgs (const oski_matspecific_t *A, const oski_matcommon_t *props, size_t max_r, size_t max_c, double prob_examine, const char *caller)
 Check input arguments to a function with a signature like oski_EstimateFillBCSR().
static int EstimateFillFromCSR (const oski_matCSR_t *A, const oski_matcommon_t *props, size_t max_r, size_t max_c, double prob_examine, oski_fillprofile_BCSR_t *fill)
 This routine is a wrapper around EstimateBlockCounts().
static int EstimateFillFromCSC (const oski_matCSC_t *A, const oski_matcommon_t *props, size_t max_r, size_t max_c, double prob_examine, oski_fillprofile_BCSR_t *fill)
 Estimate the fill ratio for a matrix initially in CSC format.
oski_fillprofile_BCSR_toski_EstimateFillBCSR (const oski_matspecific_t *mat, const oski_matcommon_t *props, size_t max_r, size_t max_c, double prob_examine)
 Estimate the fill ratio at a variety of block sizes for BCSR storage.
void oski_DestroyBCSRFillProfile (oski_fillprofile_BCSR_t *fill)
 Free the memory associated with a fill profile.

Detailed Description

BCSR fill ratio estimator.


Function Documentation

static int EstimateBlockCounts ( const oski_index_t *  ptr,
const oski_index_t *  ind,
oski_index_t  base,
oski_index_t  m,
oski_index_t  n,
oski_index_t  r,
oski_index_t  max_c,
double  prob_examine,
oski_index_t *  p_nnz_est,
oski_index_t *  p_nb_est 
) [static]

Given an $m\times n$ CSR matrix $A$, estimates the fill ratio if the matrix were converted into $r\times c$ BCSR format.

The caller supplies this routine with a maximum column block size $C$, and this routine returns the estimated fill ratios for all $1 \leq c \leq C$.

If the converted matrix has $n_b$ blocks, this implementation executes in $O(\mbox{stored non-zeros}) = O(n_b\cdot r\cdot c)$ time, but requires $O(C\cdot n)$ auxiliary storage space to store a dense copies of the block rows.

This routine assumes the CSR matrix uses full storage, but otherwise is flexible with regard to the following variations:

  • 0 or 1-based indexing
  • 'ptr[0]' does not have to start at 'base' (i.e., caller can pass a subset of rows of a larger matrix)
  • Column indices do not have to be sorted.
Parameters:
[in]ptrCSR row pointers.
[in]indCSR column indices.
[in]baseIndex base (0-based or 1-based)
[in]mLogical number of matrix rows
[in]nLogical number of matrix columns
[in]rDesired row block size
[in]max_cMaximum desired column block size ( $C$).
[in]prob_examineThe desired probability of examining each block row.
[in,out]p_nnz_estUsed to return the number of non-zeros actually examined. Must be non-NULL.
[in,out]p_nb_estUsed to return the number of $r\times c$ blocks that would be created for the non-zeros examined. Must be non-NULL array of length $C = $ max_c.
Returns:
On success, returns 0, sets *p_nnz_est to the number of non-zeros examined, and sets p_nb_est[c-1] to the number of non-zero blocks that are needed to store the examined non-zeros in $r \times c$ format. On error, returns an error code and leaves p_bptr, p_bind, and p_bval unchanged.

Get the block count for block column size c, block column J.

Increment the block count for block column size c, block column J.

Set the block count for block column size c, block column J, to zero.

References ERR_OUT_OF_MEMORY, oski_Free, oski_Malloc, and oski_ZeroMem().

Referenced by EstimateFillFromCSC(), and EstimateFillFromCSR().

static int EstimateFillFromCSC ( const oski_matCSC_t A,
const oski_matcommon_t props,
size_t  max_r,
size_t  max_c,
double  prob_examine,
oski_fillprofile_BCSR_t fill 
) [static]

Estimate the fill ratio for a matrix initially in CSC format.

This implementation exploits the fact that the CSC representation is based on the transpose of the CSR implementation.

See also:
EstimateFillFromCSR()

References oski_matCSR_t::base_index, ERR_OUT_OF_MEMORY, EstimateBlockCounts(), oski_matCSR_t::ind, oski_matCSC_t::mat_trans, oski_matcommon_t::num_cols, oski_matcommon_t::num_rows, oski_Free, oski_Malloc, oski_ZeroMem(), PROF_FILLBCSR_SET, and oski_matCSR_t::ptr.

Referenced by oski_EstimateFillBCSR().

static int EstimateFillFromCSR ( const oski_matCSR_t A,
const oski_matcommon_t props,
size_t  max_r,
size_t  max_c,
double  prob_examine,
oski_fillprofile_BCSR_t fill 
) [static]

This routine is a wrapper around EstimateBlockCounts().

Parameters:
[in]AMatrix in CSR format.
[in]propsProperties of A.
[in]max_rMaximum row block size to consider.
[in]max_cMaximum column block size to consider.
[in]prob_examineProbability of examining a given block row.
[in,out]fillStructure in which to store the fill ratio profile for A.
Note:
This routine does not have the property that setting prob_examine == 1.0 yields the exact fill ratio, because it ignores leftover rows.
Returns:
Returns a non-zero error code on error.

References oski_matCSR_t::base_index, ERR_OUT_OF_MEMORY, EstimateBlockCounts(), oski_matCSR_t::ind, oski_matcommon_t::num_cols, oski_matcommon_t::num_rows, oski_Free, oski_Malloc, oski_ZeroMem(), PROF_FILLBCSR_SET, and oski_matCSR_t::ptr.

Referenced by oski_EstimateFillBCSR().

Free the memory associated with a fill profile.

Todo:
Does not need to be type-dependent.

References oski_Free, and oski_fillprofile_BCSR_t::ratio.

oski_fillprofile_BCSR_t* oski_EstimateFillBCSR ( const oski_matspecific_t mat,
const oski_matcommon_t props,
size_t  max_r,
size_t  max_c,
double  prob_examine 
)

Estimate the fill ratio at a variety of block sizes for BCSR storage.

Returns:
If a fill estimate cannot be computed for the given matrix or matrix type, returns NULL and calls the error handler. Otherwise, returns a new fill profile.

References CheckArgs(), ERR_BAD_MAT, EstimateFillFromCSC(), EstimateFillFromCSR(), MACRO_TO_STRING, oski_fillprofile_BCSR_t::max_c, oski_fillprofile_BCSR_t::max_r, oski_Free, OSKI_IND_ID, oski_LookupMatTypeId(), oski_Malloc, OSKI_VAL_ID, oski_fillprofile_BCSR_t::ratio, oski_matspecific_t::repr, and oski_matspecific_t::type_id.