Public Interface

Detailed Description

This module defines the public interface, i.e., part of the library implementation intended for use by end-users and documented in detail at the following URL: http://bebop.cs.berkeley.edu/oski/oski-interface.pdf .

Our implementation requires users also to call oski_Init() before calling any of the routines in the public interface. Users may optionally call oski_Close() when the library is no longer needed by an application to free internal data structures.


Modules

 Error codes and error handling.
 Set explicit workload hints.
 Kernels (matrix type-independent implementations).
 Single- and multivector view creation.
 Vector views are wrappers around user-declared dense array matrix representations.

Data Structures

struct  oski_permstruct_t
 Generic row/column permutation structure. More...

Defines

#define INVALID_MAT   ((oski_matrix_t)NULL)
 Invalid (NULL) matrix handle.
#define INVALID_VEC   ((oski_vecview_t)NULL)
 Invalid (NULL) vector view handle.
#define OSKI_CHECK_COPYMODE(x)   IS_VAL_IN_RANGE(x, COPY_INPUTMAT, SHARE_INPUTMAT)
 Returns 1 <==> the specified copy mode x is legal.

Typedefs

typedef oski_permstruct_t * oski_perm_t
 Permutation handle.

Enumerations

enum  oski_copymode_t { COPY_INPUTMAT, SHARE_INPUTMAT }
 Input matrix copy modes. More...
enum  oski_storage_t { LAYOUT_COLMAJ, LAYOUT_ROWMAJ }
 Dense multiple-vector storage layout. More...
enum  oski_matop_t { OP_NORMAL, OP_CONJ, OP_TRANS, OP_CONJ_TRANS }
 Matrix transpose options. More...
enum  oski_ataop_t { OP_AT_A, OP_AH_A, OP_A_AT, OP_A_AH }
 Transpose options for matrix-transpose-times-matrix ($A^T\cdot A$) kernel. More...
enum  oski_inmatprop_t {
  INMATPROP_NULL = -1, MAT_GENERAL = 0, MAT_TRI_UPPER, MAT_TRI_LOWER,
  MAT_SYMM_UPPER, MAT_SYMM_LOWER, MAT_SYMM_FULL, MAT_HERM_UPPER,
  MAT_HERM_LOWER, MAT_HERM_FULL, MAT_DIAG_EXPLICIT, MAT_UNIT_DIAG_IMPLICIT,
  INDEX_ONE_BASED, INDEX_ZERO_BASED, INDEX_UNSORTED, INDEX_SORTED,
  INDEX_REPEATED, INDEX_UNIQUE, INMATPROP_MAX
}
 Input matrix properties. More...

Functions

oski_value_t oski_GetMatEntry (const oski_matrix_t A_tunable, oski_index_t row, oski_index_t col)
 Returns the value of a matrix element.
int oski_SetMatEntry (oski_matrix_t A_tunable, oski_index_t row, oski_index_t col, oski_value_t new_val)
 Changes the value of the specified matrix element.
int oski_GetMatClique (const oski_matrix_t A_tunable, const oski_index_t *rows, oski_index_t num_rows, const oski_index_t *cols, oski_index_t num_cols, oski_vecview_t vals)
 Returns a block of values, defined by a clique, from a matrix.
int oski_SetMatClique (oski_matrix_t A_tunable, const oski_index_t *rows, oski_index_t num_rows, const oski_index_t *cols, oski_index_t num_cols, const oski_vecview_t vals)
 Changes a block of values, defined by a clique, in a matrix.
int oski_GetMatDiagValues (const oski_matrix_t A_tunable, oski_index_t diag_num, oski_vecview_t vals)
 Extract the diagonal $d$ from $A$, that is, all entries $A(i,j)$ such that $j-i = d$.
int oski_SetMatDiagValues (oski_matrix_t A_tunable, oski_index_t diag_num, const oski_vecview_t vals)
 Sets the values along diagonal $d$ from $A$, that is, all entries $A(i,j)$ such that $j-i = d$.
oski_matrix_t oski_CreateMatCSR (oski_index_t *Aptr, oski_index_t *Aind, oski_value_t *Aval, oski_index_t num_rows, oski_index_t num_cols, oski_copymode_t mode, int k,...)
 Creates and returns a valid tunable matrix object from a compressed sparse row (CSR) representation.
oski_matrix_t oski_CreateMatCSC (oski_index_t *Aptr, oski_index_t *Aind, oski_value_t *Aval, oski_index_t num_rows, oski_index_t num_cols, oski_copymode_t mode, int k,...)
 Creates and returns a valid tunable matrix object from a compressed sparse column (CSC) representation.
oski_matrix_t oski_CopyMat (const oski_matrix_t A_tunable)
 Creates a copy of a matrix object.
int oski_DestroyMat (oski_matrix_t A_tunable)
 Frees object memory associated with a given matrix object.
int oski_IsMatPermuted (const oski_matrix_t A_tunable)
 Checks whether a matrix has been tuned by reordering.
const_oski_matrix_t oski_ViewPermutedMat (const oski_matrix_t A_tunable)
 Given a matrix $A$, possibly reordered during tuning to the form $\hat{A} = P_r\cdot A\cdot P_c^T$, returns a read-only object corresponding to $\hat{A}$.
const_oski_perm_t oski_ViewPermutedMatRowPerm (const oski_matrix_t A_tunable)
 Given a matrix $A$, possible reordered during tuning to the form $\hat{A} = P_r\cdot A\cdot P_c^T$, returns a read-only object corresponding to $P_r$.
const_oski_perm_t oski_ViewPermutedMatColPerm (const oski_matrix_t A_tunable)
 Given a matrix $A$, possible reordered during tuning to the form $\hat{A} = P_r\cdot A\cdot P_c^T$, returns a read-only object corresponding to $P_c$ (and NOT $P_c^T$).
int oski_PermuteVecView (const oski_perm_t P, oski_matop_t opP, oski_vecview_t x_view)
 Permute a vector view object, i.e., computes $x \leftarrow \mathrm{op}(P)x$, where $\matrm{op}(A) \in \{A, A^T\}$.
int oski_TuneMat (oski_matrix_t A_tunable)
 Tune the matrix object using all hints and implicit profiling data.
char * oski_GetMatTransforms (const oski_matrix_t A_tunable)
 Returns a string representation of the data structure transformations that were applied to the given matrix during tuning.
int oski_ApplyMatTransforms (const oski_matrix_t A_tunable, const char *xforms)
 Replace the current data structure for a given matrix object with a new data structure specified by a given string.
oski_vecview_t oski_CreateVecView (oski_value_t *x, oski_index_t length, oski_index_t inc)
 Creates a valid view on a single dense column vector $x$.
int oski_DestroyVecView (oski_vecview_t x)
 Destroy an existing vector view.
oski_vecview_t oski_CopyVecView (const oski_vecview_t x)
 Creates a copy of the given (multi)vector view.

Enumeration Type Documentation

enum oski_ataop_t
 

Transpose options for matrix-transpose-times-matrix ($A^T\cdot A$) kernel.

See also:
OSKI_CHECK_ATAOP

oski_MatTransMatMult

Enumerator:
OP_AT_A  Apply $A^T\cdot A$.
OP_AH_A  Apply $A^H\cdot A$.
OP_A_AT  Apply $A\cdot A^T$.
OP_A_AH  Apply $A\cdot A^H$.

enum oski_copymode_t
 

Input matrix copy modes.

On matrix handle creation, the library copies the user's input matrix arrays in one of two modes:

  • Copy mode (COPY_INPUTMAT): The library makes an explicit, deep copy of the input matrix. Thus, the user may free the input matrix arrays immediately on return from the creation routine call.

  • Shared mode (SHARE_INPUTMAT): The library shares the input matrix arrays with the user. Specifically, the library and the user agree to the following conditions:

    1. The user promises that the input matrix arrays will not be freed or reallocated before destroying the matrix handle.
    2. The user promises not to modify any of the values in these arrays, except through the BeBOP interface (e.g., changing non-zero values through the interface's set-value routines).
    3. The library promises not to modify the arrays containing non-zero pattern data.
    4. The library promises to keep the input matrix and its tuned copy (if any) synchronized.
Enumerator:
COPY_INPUTMAT  Copy mode.
SHARE_INPUTMAT  Share mode.

enum oski_inmatprop_t
 

Input matrix properties.

Properties are divided into subcategories:

  • Pattern properties: MAT_GENERAL (default), MAT_TRI_UPPER, MAT_TRI_LOWER, MAT_SYMM_UPPER, MAT_SYMM_LOWER, MAT_SYMM_FULL, MAT_HERM_UPPER, MAT_HERM_LOWER, MAT_HERM_FULL
  • Diagonal properties: MAT_DIAG_EXPLICIT (default), MAT_UNIT_DIAG_IMPLICIT
  • Index base: INDEX_ONE_BASED (default), INDEX_ZERO_BASED
  • Index ordering: INDEX_UNSORTED (default), INDEX_SORTED
  • Index repetition: INDEX_REPEATED (default), INDEX_UNIQUE

Properties within a given subcategory are mutually exclusive, with default values as marked.

Note:
If modifying these properties, please also make the corresponding modifications in inmatprop.h
Enumerator:
INMATPROP_NULL  "Undefined" property
MAT_GENERAL  General pattern [DEFAULT].
MAT_TRI_UPPER  Upper triangular.
MAT_TRI_LOWER  Lower triangular.
MAT_SYMM_UPPER  Symmetric ($A=A^T$), but only upper triangle stored.
MAT_SYMM_LOWER  Symmetric, but only lower triangle stored.
MAT_SYMM_FULL  Symmetric but full pattern stored.
MAT_HERM_UPPER  Hermitian ($A=A^H$), but only upper triangle stored.
MAT_HERM_LOWER  Hermitian, but only lower triangle stored.
MAT_HERM_FULL  Hermitian but full pattern stored.
MAT_DIAG_EXPLICIT  Diagonal elements, if any, stored explicitly [DEFAULT].
MAT_UNIT_DIAG_IMPLICIT  $A(i,i)=1$ for all diagonal elements.
INDEX_ONE_BASED  Array indices start at 1 (Fortran convention) [DEFAULT].
INDEX_ZERO_BASED  Array indices start at 0 (C convention).
INDEX_UNSORTED  Indices are unsorted [DEFAULT].
INDEX_SORTED  Indices are sorted.
INDEX_REPEATED  Values for repeated indices are summed [DEFAULT].
INDEX_UNIQUE  Indices are unique.
INMATPROP_MAX  Maximum property value.

enum oski_matop_t
 

Matrix transpose options.

The user may apply the transpose or conjugate transpose of a matrix $A$.

See also:
OSKI_CHECK_MATOP

oski_MatMult

oski_MatMultAndMatTransMult

oski_MatTrisolve

oski_MatPowMult

Enumerator:
OP_NORMAL  Apply $A$.
OP_CONJ  Applies the complex conjugate, $\bar{A}$.
OP_TRANS  Apply the transpose, $A^T$.
OP_CONJ_TRANS  Apply the complex conjugate transpose, $A^H=\bar{A}^T$.

enum oski_storage_t
 

Dense multiple-vector storage layout.

On creation of a dense multiple-vector (i.e., dense matrix), the layout parameter specifies how the data is stored. Let $A$ be a logical $m\times n$ matrix stored in a dense physical array X with stride $s$. Then,

  • Column major layout (LAYOUT_COLMAJ): Logical element $a_{ij}$ is stored in physical array element X[$(i-1) + (j-1)\cdot s$], where $1 \leq i \leq m \leq s$. This layout is the Fortran default for statically declared 2-D arrays, and is also the usual BLAS convention.

  • Row major layout (LAYOUT_ROWMAJ): Logical element $a_{ij}$ is stored in physical array element X[$(i-1)\cdot s + (j-1) s$], where $1 \leq j \leq n \leq s$. This layout is the C default for statically declared 2-D arrays.

Following the dense BLAS convention, we sometimes also refer to the stride parameter $s$ as the leading dimension.

Enumerator:
LAYOUT_COLMAJ  Column major layout.
LAYOUT_ROWMAJ  Row major layout.

Function Documentation

int oski_ApplyMatTransforms (  oski_matrix_t  A_tunable,
const char *  xforms
) 
 

Replace the current data structure for a given matrix object with a new data structure specified by a given string.

Parameters:
[in] A_tunable A valid matrix object.
[in] xforms A valid OSKI-Lua program describing the transformation to apply to the matrix.
Returns:
0 if the transformation was applied successfully.

oski_matrix_t oski_CopyMat (  const oski_matrix_t  A_tunable  ) 
 

Creates a copy of a matrix object.

Thus, A_copy exists independently of A_tunable and any data upon which A_tunable might depend.

  • Apply the same structural tuning hints to A_copy that were originally applied to A_tunable.
  • Execute oski_GetMatTransforms() on A_tunable and apply these to A_copy.

According to these steps, A_copy does not have any of A_tunable's workload hints or implicit workload gathered from implicit profiling.

Parameters:
[in] A_tunable Handle to a valid matrix $A$.
Returns:
A new, separate physical copy of $A$, or INVALID_MAT on error.

oski_vecview_t oski_CopyVecView (  const oski_vecview_t  x  ) 
 

Creates a copy of the given (multi)vector view.

Parameters:
[in] x (Multi)vector view to duplicate.
Returns:
A handle for a new multivector view object which is a duplicate of x, or INVALID_VEC on error.

oski_matrix_t oski_CreateMatCSC (  oski_index_t *  Aptr,
oski_index_t *  Aind,
oski_value_t *  Aval,
oski_index_t  num_rows,
oski_index_t  num_cols,
oski_copymode_t  mode,
int  k,
  ...
) 
 

Creates and returns a valid tunable matrix object from a compressed sparse column (CSC) representation.

Parameters:
[in] num_rows $m \geq 0$
[in] num_cols $n \geq 0$
[in] Aptr CSC row pointers.
[in] Aind CSC column indices.
[in] Aval CSC non-zero values.
[in] k Number of explicitly specified semantic properties of (Aptr, Aind, Aval).
Returns:
A valid, tunable matrix object, or INVALID_MAT on error. Any kernel operations or tuning operations may be called using this object.

oski_matrix_t oski_CreateMatCSR (  oski_index_t *  Aptr,
oski_index_t *  Aind,
oski_value_t *  Aval,
oski_index_t  num_rows,
oski_index_t  num_cols,
oski_copymode_t  mode,
int  k,
  ...
) 
 

Creates and returns a valid tunable matrix object from a compressed sparse row (CSR) representation.

Parameters:
[in] num_rows $m \geq 0$
[in] num_cols $n \geq 0$
[in] Aptr CSR row pointers.
[in] Aind CSR column indices.
[in] Aval CSR non-zero values.
[in] k Number of explicitly specified semantic properties of (Aptr, Aind, Aval).
Returns:
A valid, tunable matrix object, or INVALID_MAT on error. Any kernel operations or tuning operations may be called using this object.

oski_vecview_t oski_CreateVecView (  oski_value_t *  x,
oski_index_t  length,
oski_index_t  inc
) 
 

Creates a valid view on a single dense column vector $x$.

Parameters:
[in] x Vector data.
[in] length Logical vector length, >= 0.
[in] inc Physical stride between consecutive elements. inc must be >= 1.
Returns:
A vector view object (handle), or INVALID_VEC on error.

int oski_DestroyMat (  oski_matrix_t  A_tunable  ) 
 

Frees object memory associated with a given matrix object.

Parameters:
[in,out] A_tunable A valid matrix handle.
Returns:
0 if the object was successfully freed, or an error code otherwise.

int oski_DestroyVecView (  oski_vecview_t  x  ) 
 

Destroy an existing vector view.

Parameters:
[in,out] x (Multi)vector view to free.
Returns:
0 on success, or an error code on error.

int oski_GetMatClique (  const oski_matrix_t  A_tunable,
const oski_index_t *  rows,
oski_index_t  num_rows,
const oski_index_t *  cols,
oski_index_t  num_cols,
oski_vecview_t  vals
) 
 

Returns a block of values, defined by a clique, from a matrix.

Todo:
Test thoroughly!

int oski_GetMatDiagValues (  const oski_matrix_t  A_tunable,
oski_index_t  diag_num,
oski_vecview_t  diag_vals
) 
 

Extract the diagonal $d$ from $A$, that is, all entries $A(i,j)$ such that $j-i = d$.

Todo:
Test thoroughly!

oski_value_t oski_GetMatEntry (  const oski_matrix_t  A_tunable,
oski_index_t  row,
oski_index_t  col
) 
 

Returns the value of a matrix element.

Parameters:
[in] A_tunable The object representing an $m\times n$ matrix $A$.
[in] row Row index $i : 1 \leq i \leq m$ (1-based).
[in] col Column index $j : 1 \leq j \leq n$ (1-based).
Returns:
The element $A(i,j)$, or a NaN on error.

char* oski_GetMatTransforms (  const oski_matrix_t  A_tunable  ) 
 

Returns a string representation of the data structure transformations that were applied to the given matrix during tuning.

Parameters:
[in] A_tunable Valid matrix handle.
Returns:
A newly allocated string representing the transformation/data structure that has been applied to $A$.
Note:
The caller must free the returned string.

int oski_IsMatPermuted (  const oski_matrix_t  A_tunable  ) 
 

Checks whether a matrix has been tuned by reordering.

Parameters:
[in] A_tunable Matrix to check.
Returns:
1 <==> the matrix was permuted using a non-trivial permutation, or 0 otherwise.
Todo:
Update this routine when Ali Pinar's TSP reordering code is implemented.

int oski_PermuteVecView (  const oski_perm_t  P,
oski_matop_t  opP,
oski_vecview_t  x_view
) 
 

Permute a vector view object, i.e., computes $x \leftarrow \mathrm{op}(P)x$, where $\matrm{op}(A) \in \{A, A^T\}$.

Parameters:
[in] P Permutation matrix $P$.
[in] opP Transpose option.
[in,out] x_view Vector view to permute.
Returns:
0 on success, or an error code.

int oski_SetMatClique (  const oski_matrix_t  A_tunable,
const oski_index_t *  rows,
oski_index_t  num_rows,
const oski_index_t *  cols,
oski_index_t  num_cols,
const oski_vecview_t  vals
) 
 

Changes a block of values, defined by a clique, in a matrix.

Todo:
Test thoroughly!

int oski_SetMatDiagValues (  const oski_matrix_t  A_tunable,
oski_index_t  diag_num,
const oski_vecview_t  diag_vals
) 
 

Sets the values along diagonal $d$ from $A$, that is, all entries $A(i,j)$ such that $j-i = d$.

Todo:
Test thoroughly!

int oski_SetMatEntry (  const oski_matrix_t  A_tunable,
oski_index_t  row,
oski_index_t  col,
oski_value_t  new_val
) 
 

Changes the value of the specified matrix element.

Parameters:
[in] A_tunable The object representing an $m\times n$ matrix $A$.
[in] row Row index $i : 1 \leq i \leq m$ (1-based).
[in] col Column index $j : 1 \leq j \leq n$ (1-based).
[in] new_val New value for element $A(i,j)$.
Returns:
Assigns logical element $A(i,j)$ to new_val and returns 0. If $A(i,j)$ specifies an invalid or structural zero element, then this routine returns an error code.
If the matrix is symmetric (or Hermitian), then this routine also assigns $A(j,i)$ to the new value (or conjugated value) accordingly.

int oski_TuneMat (  oski_matrix_t  A_tunable  ) 
 

Tune the matrix object using all hints and implicit profiling data. 

WHILE
    !IsTuned(A)
    AND tuning_time_left > 0
    AND i_heur <= NUM_HEURISTICS
DO
    LET heur = GetHeuristic( i_heur );
    LET results = NULL

    IF GetTotalCostEstimate(heur, A) <= tuning_time_left THEN
        LET t0 = GetTimer();
        results = EvaluateHeuristic( heur, A );
            // results == NULL if heuristic does not apply to A
        LET elapsed_time = GetTimer() - t0;
        tuning_time_left -= elapsed_time;
    ENDIF

    IF results THEN
        LET t0 = GetTimer();
        A_tuned = ApplyHeuristic( heur, results, A );
            // convert A to new data structure
        LET elapsed_time = GetTimer() - t0;
        tuning_time_left -= elapsed_time;

        A = ChooseFastest( A, A_tuned, A->trace );
    ENDIF

    i_heur = i_heur + 1;
DONE

Todo:
The current implementation does not try to re-tune if already tuned.

Check that the new data structure really is faster than the old.

const_oski_matrix_t oski_ViewPermutedMat (  const oski_matrix_t  A_tunable  ) 
 

Given a matrix $A$, possibly reordered during tuning to the form $\hat{A} = P_r\cdot A\cdot P_c^T$, returns a read-only object corresponding to $\hat{A}$.

Parameters:
[in] A_tunable Matrix to check.
Returns:
The permuted matrix $\hat{A}$, or INVALID_MAT on error.
Todo:
Update this routine when Ali Pinar's TSP reordering code is implemented.

const_oski_perm_t oski_ViewPermutedMatColPerm (  const oski_matrix_t  A_tunable  ) 
 

Given a matrix $A$, possible reordered during tuning to the form $\hat{A} = P_r\cdot A\cdot P_c^T$, returns a read-only object corresponding to $P_c$ (and NOT $P_c^T$).

Todo:
Update this routine when Ali Pinar's TSP reordering code is implemented.

const_oski_perm_t oski_ViewPermutedMatRowPerm (  const oski_matrix_t  A_tunable  ) 
 

Given a matrix $A$, possible reordered during tuning to the form $\hat{A} = P_r\cdot A\cdot P_c^T$, returns a read-only object corresponding to $P_r$.

Todo:
Update this routine when Ali Pinar's TSP reordering code is implemented.

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