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

CSR-to-CB format conversion routines. More...

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <oski/config.h>
#include <oski/common.h>
#include <oski/matcreate.h>
#include <oski/modloader.h>
#include <oski/matrix.h>
#include <oski/tune.h>
#include <oski/CSR/format.h>
#include <oski/CB/format.h>
#include <oski/CB/module.h>
#include <oski/xforms_internal.h>

Defines

#define MIN(a, b)   ((a) < (b) ? (a) : (b))
 Return the minimum of two values.

Functions

static int ExpandSymm (const oski_matCSR_t *mat, const oski_matcommon_t *props, oski_matCSR_t **p_mat_full)
static oski_index_t CountZeroRows (oski_index_t m, const oski_index_t *ptr)
 Returns the number of rows of the CSR matrix A that are structurally zero.
static oski_index_t FindFirstNonzeroRow (oski_index_t m, const oski_index_t *ptr, int has_unit_diag, oski_index_t i_min)
 Returns the index of the first row $i \geq i_0$ containing at least one structural non-zero, and returns $i \geq m$ if no such row can be found.
static oski_index_t FindMinColIndex (oski_index_t m, oski_index_t n, const oski_index_t *ptr, const oski_index_t *ind, oski_index_t b, oski_index_t has_unit_diag, oski_index_t i_start, oski_index_t i_max, oski_index_t j_min)
 Returns the smallest column $j \geq j_0$ of any structural non-zero in the $r$ consecutive rows beginning at row $i_0$, $j \geq n$ if no such non-zero can be found.
static oski_index_t FindFirstNzRowInSubmat (oski_index_t m, const oski_index_t *ptr, const oski_index_t *ind, oski_index_t b, int has_unit_diag, oski_index_t i0, oski_index_t j0, oski_index_t i_max, oski_index_t j_max)
static oski_index_t FindNextZeroRowInSubmat (oski_index_t m, const oski_index_t *ptr, const oski_index_t *ind, oski_index_t b, int has_unit_diag, oski_index_t i0, oski_index_t j0, oski_index_t i_max, oski_index_t j_max)
static int FindSubblock (oski_index_t m, const oski_index_t *ptr, const oski_index_t *ind, oski_index_t b, int has_unit_diag, oski_index_t i_min, oski_index_t j_min, oski_index_t i_max, oski_index_t j_max, oski_index_t *p_i_start, oski_index_t *p_i_max)
static void SetupBlockRowPtrs (const oski_index_t *ptr, const oski_index_t *ind, oski_index_t b, int has_unit_diag, oski_index_t i_start, oski_index_t j_min, oski_index_t R, oski_index_t j_max, oski_index_t *bptr)
static void CopyValues (const oski_index_t *ptr, const oski_index_t *ind, const oski_value_t *val, oski_index_t b, int has_unit_diag, oski_index_t i_start, oski_index_t j_min, oski_index_t R, oski_index_t j_max, const oski_index_t *bptr, oski_index_t *bind, oski_value_t *bval)
static int ConvertSubblock (const oski_index_t *ptr, const oski_index_t *ind, const oski_value_t *val, oski_index_t b, int has_unit_diag, oski_index_t i_start, oski_index_t j_min, oski_index_t i_max, oski_index_t j_max, simplelist_t *cache_blocks)
static int MakeSparseSubblocks (oski_index_t m, oski_index_t n, const oski_index_t *ptr, const oski_index_t *ind, const oski_value_t *val, oski_index_t b, int has_unit_diag, oski_index_t i0, oski_index_t j0, oski_index_t i_max, oski_index_t j_max, simplelist_t *cache_blocks)
 Recursive procedure to convert a specified submatrix of a CSR matrix into a sequence of CSR subblocks consisting of consecutive non-zero rows.
static int MakeBlock (oski_index_t m, oski_index_t n, const oski_index_t *ptr, const oski_index_t *ind, const oski_value_t *val, oski_index_t b, int has_unit_diag, oski_index_t i0, oski_index_t j0, oski_index_t i_max, oski_index_t j_max, simplelist_t *cache_blocks)
 Convert a specified submatrix of a CSR matrix into a single cache block.
static int ConvertToCSR (oski_index_t m, oski_index_t n, const oski_index_t *ptr, const oski_index_t *ind, const oski_value_t *val, oski_index_t b, int has_unit_diag, oski_index_t min_row, oski_index_t min_col, oski_index_t R, oski_index_t C, simplelist_t *cache_blocks)
 Recursive procedure to compute a cache block partitioning of an $m\times n$ matrix $A$, stored in CSR format.
static oski_index_t FindMinColsBegin (oski_index_t n, const oski_index_t *ptr, const oski_index_t *ind, oski_index_t b, int has_unit_diag, oski_index_t i_start, oski_index_t i_max, oski_index_t j_min, oski_index_t *k_begin)
static void FindMaxCols (const oski_index_t *ptr, const oski_index_t *ind, oski_index_t b, int has_unit_diag, oski_index_t i_start, oski_index_t i_max, oski_index_t j_start, oski_index_t j_max, const oski_index_t *k_begin, oski_index_t *k_end)
static oski_index_t FindMinColsContinue (oski_index_t n, const oski_index_t *ptr, const oski_index_t *ind, oski_index_t b, int has_unit_diag, oski_index_t i_start, oski_index_t i_max, oski_index_t j_min, oski_index_t *k_begin)
static void SetupBlockRowPtrs_Sorted (const oski_index_t *ptr, const oski_index_t *ind, oski_index_t b, int has_unit_diag, oski_index_t i_start, oski_index_t j_min, oski_index_t R, oski_index_t j_max, const oski_index_t *k_begin, const oski_index_t *k_end, oski_index_t *bptr)
static void CopyValues_Sorted (const oski_index_t *ptr, const oski_index_t *ind, const oski_value_t *val, oski_index_t b, int has_unit_diag, oski_index_t i_start, oski_index_t j_min, oski_index_t R, oski_index_t j_max, const oski_index_t *k_begin, const oski_index_t *k_end, const oski_index_t *bptr, oski_index_t *bind, oski_value_t *bval)
static int ConvertSubblock_Sorted (const oski_index_t *ptr, const oski_index_t *ind, const oski_value_t *val, oski_index_t b, int has_unit_diag, oski_index_t i_start, oski_index_t j_min, oski_index_t i_max, oski_index_t j_max, const oski_index_t *k_begin, const oski_index_t *k_end, simplelist_t *cache_blocks)
static int MakeBlock_Sorted (const oski_index_t *ptr, const oski_index_t *ind, const oski_value_t *val, oski_index_t b, int has_unit_diag, oski_index_t i0, oski_index_t j0, oski_index_t i_max, oski_index_t j_max, const oski_index_t *k_begin, const oski_index_t *k_end, simplelist_t *cache_blocks)
 Convert a specified submatrix of a CSR matrix into a single cache block, assuming sorted column indices.
static int ConvertToCSR_Sorted (oski_index_t m, oski_index_t n, const oski_index_t *ptr, const oski_index_t *ind, const oski_value_t *val, oski_index_t b, int has_unit_diag, oski_index_t min_row, oski_index_t min_col, oski_index_t R, oski_index_t C, simplelist_t *cache_blocks)
 Faster but less memory-efficient implementation of ConvertToCSR() which assumes sorted column indices.
void * oski_CreateMatReprFromCSR (const oski_matCSR_t *mat, const oski_matcommon_t *props,...)
 Example usage:
oski_matCSR_t * oski_ConvertMatReprToCSR (const void *mat, const oski_matcommon_t *props)
 Method: Convert to CSR format.
int oski_CreateLuaMatReprFromCSR (lua_State *L)
 The CB implementation expects the following arguments on the stack:

Detailed Description

CSR-to-CB format conversion routines.

Define Documentation

#define MIN (   a,
  b 
)    ((a) < (b) ? (a) : (b))

Return the minimum of two values.

Referenced by ConvertToCSR(), and ConvertToCSR_Sorted().

Function Documentation

static int ConvertToCSR ( oski_index_t  m,
oski_index_t  n,
const oski_index_t *  ptr,
const oski_index_t *  ind,
const oski_value_t *  val,
oski_index_t  b,
int  has_unit_diag,
oski_index_t  min_row,
oski_index_t  min_col,
oski_index_t  R,
oski_index_t  C,
simplelist_t *  cache_blocks 
) [static]

Recursive procedure to compute a cache block partitioning of an $m\times n$ matrix $A$, stored in CSR format.

Parameters:
[in]mTotal number of rows in the matrix.
[in]nTotal number of columns in the matrix.
[in]ptrRow pointers for the CSR input matrix.
[in]indColumn indices for the CSR input matrix.
[in]valNon-zero values for the CSR input matrix.
[in]bIndex base of the input matrix (0 or 1).
[in]has_unit_diagZero only if the input matrix stores the diagonal elements explicitly.
[in]min_rowMinimum row index $i_0$ to consider for the current cache block (0-based index).
[in]min_colMinimum column index $j_0$ to consider for the current cache block (0-based index).
[in]RMaximum row block size.
[in]CMaximum column block size.
[in,out]cache_blocksCurrent list of cache blocks.
Returns:
This routine scans $A$, beginning at position $(i_0, j_0)$, for a non-zero cache block of maximum size $R\times C$. If such a cache block is found, it is appended to cache_blocks, and this procedure calls itself recursively to process the rest of the matrix. When no such cache blocks remain, this routine returns 0. This routine returns a non-zero error code on error.

References FindFirstNonzeroRow(), FindMinColIndex(), MakeBlock(), MakeSparseSubblocks(), and MIN.

Referenced by oski_CreateMatReprFromCSR().

static int ConvertToCSR_Sorted ( oski_index_t  m,
oski_index_t  n,
const oski_index_t *  ptr,
const oski_index_t *  ind,
const oski_value_t *  val,
oski_index_t  b,
int  has_unit_diag,
oski_index_t  min_row,
oski_index_t  min_col,
oski_index_t  R,
oski_index_t  C,
simplelist_t *  cache_blocks 
) [static]

Faster but less memory-efficient implementation of ConvertToCSR() which assumes sorted column indices.

This algorithm reverts to ConvertToCSR() on error.

References ERR_OUT_OF_MEMORY, FindFirstNonzeroRow(), MakeBlock_Sorted(), MIN, oski_CopyMem, oski_FreeAll(), oski_MultiMalloc(), and oski_ZeroMem().

Referenced by oski_CreateMatReprFromCSR().

static oski_index_t CountZeroRows ( oski_index_t  m,
const oski_index_t *  ptr 
) [static]

Returns the number of rows of the CSR matrix A that are structurally zero.

Todo:
This routine duplicates the functionality of oski_CountZeroRowsCSR(), and could be eliminated.
static oski_index_t FindFirstNonzeroRow ( oski_index_t  m,
const oski_index_t *  ptr,
int  has_unit_diag,
oski_index_t  i_min 
) [static]

Returns the index of the first row $i \geq i_0$ containing at least one structural non-zero, and returns $i \geq m$ if no such row can be found.

Parameters:
[in]mTotal number of rows $m$ in the matrix.
[in]ptrRow pointers.
[in]has_unit_diagNon-zero <==> the diagonal is all ones and not stored explicitly.
[in]i_minMinimum desired row index, $i_0$.

Referenced by ConvertToCSR(), and ConvertToCSR_Sorted().

int oski_CreateLuaMatReprFromCSR ( lua_State *  L)

The CB implementation expects the following arguments on the stack:

Matrix-type specific method to convert from a CSR matrix, with arguments passed on the Lua stack.

  1. Destination matrix type ('MBCSR')
  2. Source matrix ('CSR')
  3. Row block size ('r')
  4. Column block size ('c')
Generated on Sun Aug 12 2012 08:24:19 for BeBOP Optimized Sparse Kernel Interface Library by   doxygen 1.7.6.1