estfill.c File Reference

Detailed Description

BCSR fill ratio estimator.

#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_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.
void oski_DestroyBCSRFillProfile (oski_fillprofile_BCSR_t *fill)
 Free the memory associated with a fill profile.

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] ptr CSR row pointers.
[in] ind CSR column indices.
[in] base Index base (0-based or 1-based)
[in] m Logical number of matrix rows
[in] n Logical number of matrix columns
[in] r Desired row block size
[in] max_c Maximum desired column block size ($C$).
[in] prob_examine The desired probability of examining each block row.
[in,out] p_nnz_est Used to return the number of non-zeros actually examined. Must be non-NULL.
[in,out] p_nb_est Used 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.

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()

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] A Matrix in CSR format.
[in] props Properties of A.
[in] max_r Maximum row block size to consider.
[in] max_c Maximum column block size to consider.
[in] prob_examine Probability of examining a given block row.
[in,out] fill Structure 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.

void oski_DestroyBCSRFillProfile (  oski_fillprofile_BCSR_t *  fill  ) 
 

Free the memory associated with a fill profile.

Todo:
Does not need to be type-dependent.

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.

Generated on Wed Sep 19 16:41:22 2007 for BeBOP Optimized Sparse Kernel Interface Library by  doxygen 1.4.6