ModFEM: lsd_mkb/lsd_mkb_superlu/superlu_threads/pdsp

00001 
00002 /*
00003  * -- SuperLU MT routine (version 2.0) --
00004  * Lawrence Berkeley National Lab, Univ. of California Berkeley,
00005  * and Xerox Palo Alto Research Center.
00006  * September 10, 2007
00007  *
00008  * Sparse matrix types and function prototypes.
00009  *
00010  */
00011 
00012 #ifndef __SUPERLU_dSP_DEFS /* allow multiple inclusions */
00013 #define __SUPERLU_dSP_DEFS
00014 
00015 /*
00016  * File name:           pdsp_defs.h
00017  * Purpose:             Sparse matrix types and function prototypes
00018  * History:
00019  */
00020 
00021 /****************************
00022   Include thread header file
00023   ***************************/
00024 #if defined ( _SOLARIS )
00025 #include <thread.h>
00026 #include <sched.h>
00027 #elif defined( _DEC )
00028 #include <pthread.h>
00029 #include <unistd.h>
00030 #include <sys/mman.h>
00031 #elif defined ( _OPENMP )
00032 #include <omp.h>
00033 #elif defined ( _PTHREAD )
00034 #include <pthread.h>
00035 #elif defined ( _CRAY )
00036 #include <fortran.h>
00037 #include <string.h>
00038 #endif
00039 
00040 /* Define my integer type int_t */
00041 typedef int int_t; /* default */
00042 
00043 #include "slu_mt_machines.h"
00044 #include "slu_mt_Cnames.h"
00045 #include "supermatrix.h"
00046 #include "slu_mt_util.h"
00047 #include "pxgstrf_synch.h"
00048 
00049 
00050 /*
00051  * *************************************************
00052  *  Global data structures used in LU factorization
00053  * *************************************************
00054  * 
00055  *   nsuper: number of supernodes = nsuper+1, numbered between 0 and nsuper.
00056  *
00057  *   (supno, xsup, xsup_end):
00058  *      supno[i] is the supernode number to which column i belongs;
00059  *  xsup[s] points to the first column of supernode s;
00060  *      xsup_end[s] points to one past the last column of supernode s.
00061  *  Example: supno  0 1 2 2 3 3 3 4 4 4 4 4   (n=12)
00062  *            xsup  0 1 2 4 7
00063  *            xsup_end  1 2 4 7 12
00064  *  Note: dfs will be performed on supernode rep. relative to the new 
00065  *        row pivoting ordering
00066  *
00067  *   (lsub, xlsub, xlsub_end):
00068  *      lsub[*] contains the compressed subscripts of the supernodes;
00069  *      xlsub[j] points to the starting location of the j-th column in
00070  *               lsub[*]; 
00071  *      xlsub_end[j] points to one past the ending location of the j-th
00072  *               column in lsub[*].
00073  *  Storage: original row subscripts in A.
00074  *
00075  *      During the course of sparse LU factorization, we also use
00076  *  (lsub, xlsub, xlsub_end, xprune) to represent symmetrically 
00077  *      pruned graph. Contention will occur when one processor is
00078  *      performing DFS on supernode S, while another processor is pruning
00079  *      supernode S. We use the following data structure to deal with
00080  *      this problem. Suppose each supernode contains columns {s,s+1,...,t},
00081  *      with first column s and last column t.
00082  *
00083  *      (1) if t > s, only the subscript sets for column s and column t
00084  *          are stored. Column t represents pruned adjacency structure.
00085  *
00086  *                  --------------------------------------------
00087  *          lsub[*]    ... |   col s    |   col t   | ...
00088  *                  --------------------------------------------
00089  *                          ^            ^           ^
00090  *                       xlsub[s]    xlsub_end[s]  xlsub_end[s+1]
00091  *                                   xlsub[s+1]      :
00092  *                                       :           :
00093  *                                       :         xlsub_end[t]
00094  *                                   xlsub[t]      xprune[t] 
00095  *                                   xprune[s]    
00096  *
00097  *      (2) if t == s, i.e., a singleton supernode, the subscript set
00098  *          is stored twice:
00099  *
00100  *                  --------------------------------------
00101  *          lsub[*]    ... |      s     |     s     | ...
00102  *                  --------------------------------------
00103  *                          ^            ^           ^
00104  *                       xlsub[s]   xlsub_end[s]  xprune[s]
00105  *
00106  *      There are two subscript sets for each supernode, the last column
00107  *      structures (for pruning) will be removed after the numerical LU
00108  *      factorization phase:
00109  *        o lsub[j], j = xlsub[s], ..., xlsub_end[s]-1
00110  *          is the structure of column s (i.e. structure of this supernode).
00111  *          It is used for the storage of numerical values.
00112  *    o lsub[j], j = xlsub[t], ..., xlsub_end[t]-1
00113  *      is the structure of the last column t of this supernode.
00114  *      It is for the purpose of symmetric pruning. Therefore, the
00115  *      structural subscripts can be rearranged without making physical
00116  *      interchanges among the numerical values.
00117  *
00118  *       DFS will traverse the first subscript set if the supernode
00119  *       has not been pruned; otherwise it will traverse the second
00120  *       subscript list, i.e., the part of the pruned graph.
00121  *
00122  *   (lusup, xlusup, xlusup_end):
00123  *      lusup[*] contains the numerical values of the supernodes;
00124  *      xlusup[j] points to the starting location of the j-th column in
00125  *                storage vector lusup[*]; 
00126  *      xlusup_end[j] points to one past the ending location of the j-th 
00127  *                column in lusup[*].
00128  *  Each supernode is stored in column-major, consistent with Fortran
00129  *      two-dimensional array storage.
00130  *
00131  *   (ucol, usub, xusub, xusub_end):
00132  *      ucol[*] stores the numerical values of the U-columns above the
00133  *              supernodes. 
00134  *      usub[k] stores the row subscripts of nonzeros ucol[k];
00135  *      xusub[j] points to the starting location of column j in ucol/usub[]; 
00136  *      xusub_end[j] points to one past the ending location column j in
00137  *                   ucol/usub[].
00138  *  Storage: new row subscripts; that is indexed intp PA.
00139  *
00140  */
00141 typedef struct {
00142     int     *xsup;    /* supernode and column mapping */
00143     int     *xsup_end;
00144     int     *supno;   
00145     int     *lsub;    /* compressed L subscripts */
00146     int     *xlsub;
00147     int     *xlsub_end;
00148     double  *lusup;   /* L supernodes */
00149     int     *xlusup;
00150     int     *xlusup_end;
00151     double  *ucol;    /* U columns */
00152     int     *usub;
00153     int     *xusub;
00154     int     *xusub_end;
00155     int     nsuper;   /* current supernode number */
00156     int     nextl;    /* next position in lsub[] */
00157     int     nextu;    /* next position in usub[]/ucol[] */
00158     int     nextlu;   /* next position in lusup[] */
00159     int     nzlmax;   /* current max size of lsub[] */
00160     int     nzumax;   /*    "    "    "      ucol[] */
00161     int     nzlumax;  /*    "    "    "     lusup[] */
00162     /* ---------------------------------------------------------------
00163      *  Memory managemant for L supernodes 
00164      */
00165     int  *map_in_sup;  /* size n+1 - the address offset of each column
00166                         * in lusup[*], which is divided into regions 
00167             * by the supernodes of Householder matrix H.
00168             * If column k starts a supernode in H,
00169             * map_in_sup[k] is the next open position in
00170             * lusup[*]; otherwise map_in_sup[k] gives the
00171             * offset (negative) to the leading column
00172             * of the supernode in H.
00173             */
00174     int  dynamic_snode_bound;
00175     /* --------------------------------------------------------------- */
00176 } GlobalLU_t;
00177 
00178 
00179 /* 
00180  * *********************************************************************
00181  * The pxgstrf_shared_t structure contains the shared task queue and
00182  * the synchronization variables to facilitate parallel factorization. 
00183  * It also contains the shared L and U data structures.
00184  * *********************************************************************
00185  */
00186 typedef struct {
00187     /* ----------------------------------------------------------------
00188      * Global variables introduced in parallel code for synchronization.
00189      */
00190     volatile int tasks_remain; /* number of untaken panels */
00191     int          num_splits;   /* number of panels split at the top */
00192     queue_t      taskq;        /* size ncol - shared work queue */
00193     mutex_t      *lu_locks;    /* 5 named mutual exclusive locks */
00194     volatile int *spin_locks;  /* size ncol - mark every busy column */
00195     pan_status_t *pan_status;  /* size ncol - panel status */
00196     int          *fb_cols;     /* size ncol - mark farthest busy column */
00197     /* ---------------------------------------------------------------- */
00198     int        *inv_perm_c;
00199     int        *inv_perm_r;
00200     int        *xprune;
00201     int        *ispruned;
00202     SuperMatrix *A;
00203     GlobalLU_t *Glu;
00204     Gstat_t    *Gstat;
00205     int        *info;
00206 } pxgstrf_shared_t;
00207 
00208 /* Arguments passed to each thread. */
00209 typedef struct {
00210     int  pnum; /* process number */
00211     int  info; /* error code returned from each thread */       
00212     superlumt_options_t *superlumt_options;
00213     pxgstrf_shared_t  *pxgstrf_shared; /* shared for LU factorization */
00214 } pdgstrf_threadarg_t;
00215 
00216 
00217 /* *********************
00218    Function prototypes
00219    *********************/
00220 
00221 #ifdef __cplusplus
00222 extern "C" {
00223 #endif
00224 
00225 
00226 /* ----------------
00227    Driver routines 
00228    ---------------*/
00229 extern void
00230 pdgssv(int, SuperMatrix *, int *, int *, SuperMatrix *, SuperMatrix *, 
00231        SuperMatrix *, int *);
00232 extern void
00233 pdgssvx(int, superlumt_options_t *, SuperMatrix *, int *, int *,  
00234     equed_t *, double *, double *, SuperMatrix *, SuperMatrix *,
00235     SuperMatrix *, SuperMatrix *, 
00236     double *, double *, double *, double *, superlu_memusage_t *, 
00237     int *);
00238 
00239 /* ---------------
00240    Driver related 
00241    ---------------*/
00242 extern void dgsequ (SuperMatrix *, double *, double *, double *,
00243                     double *, double *, int *);
00244 extern void dlaqgs (SuperMatrix *, double *, double *, double, 
00245             double, double, equed_t *);
00246 extern void dgscon (char *, SuperMatrix *, SuperMatrix *,
00247             double, double *, int *);
00248 extern double dPivotGrowth(int, SuperMatrix *, int *,
00249                SuperMatrix *, SuperMatrix *);
00250 extern void dgsrfs (trans_t, SuperMatrix *, SuperMatrix *, SuperMatrix *,
00251             int *, int *, equed_t, double *, double *, SuperMatrix *,
00252             SuperMatrix *, double *, double *, Gstat_t *, int *);
00253 extern int  sp_dtrsv (char *, char *, char *, SuperMatrix *, SuperMatrix *,
00254               double *, int *);
00255 extern int  sp_dgemv (char *, double, SuperMatrix *, double *,
00256               int, double, double *, int);
00257 extern int  sp_dgemm (char *, int, int, int, double, SuperMatrix *, 
00258               double *, int, double, double *, int);
00259 
00260 /* ----------------------
00261    Factorization related
00262    ----------------------*/
00263 extern void pxgstrf_scheduler (const int, const int, const int *,
00264                    int *, int *, pxgstrf_shared_t *);
00265 extern int  dParallelInit (int, pxgstrf_relax_t *, superlumt_options_t *,
00266               pxgstrf_shared_t *);
00267 extern int  ParallelFinalize ();
00268 extern void pdgstrf_StackFree ();
00269 extern int  queue_init (queue_t *, int);
00270 extern int  queue_destroy (queue_t *);
00271 extern int  EnqueueRelaxSnode (queue_t *, int, pxgstrf_relax_t *,
00272                   pxgstrf_shared_t *);
00273 extern int  EnqueueDomains(queue_t *, struct Branch *, pxgstrf_shared_t *);
00274 extern int  Enqueue (queue_t *, qitem_t);
00275 extern int  Dequeue (queue_t *, qitem_t *);
00276 extern int  NewNsuper (const int, pxgstrf_shared_t *, int *);
00277 extern int  lockon(int *);
00278 extern void PartDomains(const int, const float, SuperMatrix *, int *, int *);
00279 
00280 extern void
00281 dCreate_CompCol_Matrix(SuperMatrix *, int, int, int, double *,
00282               int *, int *, Stype_t, Dtype_t, Mtype_t);
00283 void
00284 dCreate_CompCol_Permuted(SuperMatrix *, int, int, int, double *, int *,
00285              int *, int *, Stype_t, Dtype_t, Mtype_t);
00286 extern void
00287 dCopy_CompCol_Matrix(SuperMatrix *, SuperMatrix *);
00288 extern void
00289 dCreate_Dense_Matrix(SuperMatrix *, int, int, double *, int,
00290              Stype_t, Dtype_t, Mtype_t);
00291 extern void
00292 dCreate_SuperNode_Matrix(SuperMatrix *, int, int, int, double *, int *, int *,
00293             int *, int *, int *, Stype_t, Dtype_t, Mtype_t);
00294 extern void
00295 dCreate_SuperNode_Permuted(SuperMatrix *, int, int, int, double *, 
00296                int *, int *, int *, int *, int *, int *, 
00297                int *, int *, Stype_t, Dtype_t, Mtype_t);
00298 extern void
00299 dCopy_Dense_Matrix(int, int, double *, int, double *, int);
00300 
00301 extern void Destroy_SuperMatrix_Store(SuperMatrix *);
00302 extern void Destroy_CompCol_Matrix(SuperMatrix *);
00303 extern void Destroy_CompCol_Permuted(SuperMatrix *);
00304 extern void Destroy_CompCol_NCP(SuperMatrix *);
00305 extern void Destroy_SuperNode_Matrix(SuperMatrix *);
00306 extern void Destroy_SuperNode_SCP(SuperMatrix *);
00307 
00308 extern void dallocateA (int, int, double **, int **, int **);
00309 extern void StatAlloc (const int, const int, const int, const int, Gstat_t*);
00310 extern void StatInit  (const int, const int, Gstat_t*);
00311 extern void StatFree  (Gstat_t*);
00312 extern void get_perm_c(int, SuperMatrix *, int *);
00313 extern void dsp_colorder (SuperMatrix *, int *, superlumt_options_t *,
00314              SuperMatrix *);
00315 extern int  sp_coletree (int *, int *, int *, int, int, int *);
00316 extern int  dPresetMap (const int, SuperMatrix *, pxgstrf_relax_t *, 
00317                superlumt_options_t *, GlobalLU_t *);
00318 extern int  qrnzcnt (int, int, int *, int *, int *, int *, int *, int *,
00319              int *, int *, int *, int *);
00320 extern int  DynamicSetMap(const int, const int, const int, pxgstrf_shared_t*);
00321 extern void pdgstrf (superlumt_options_t *, SuperMatrix *, int *, 
00322              SuperMatrix *, SuperMatrix *, Gstat_t *, int *);
00323 extern void pdgstrf_init (int, fact_t, trans_t, yes_no_t, int, int, double, yes_no_t, double,
00324               int *, int *, void *, int, SuperMatrix *,
00325               SuperMatrix *, superlumt_options_t *, Gstat_t *);
00326 extern pdgstrf_threadarg_t*
00327 pdgstrf_thread_init (SuperMatrix *, SuperMatrix *, SuperMatrix *,
00328              superlumt_options_t*, pxgstrf_shared_t*, Gstat_t*, int*);
00329 extern void
00330 pdgstrf_thread_finalize (pdgstrf_threadarg_t *, pxgstrf_shared_t *,
00331              SuperMatrix *, int *, SuperMatrix *, SuperMatrix *);
00332 extern void pdgstrf_finalize(superlumt_options_t *, SuperMatrix *);
00333 extern void pxgstrf_finalize(superlumt_options_t *, SuperMatrix *);
00334 extern void pdgstrf_relax_snode (const int, superlumt_options_t *,
00335                  pxgstrf_relax_t *);
00336 extern int
00337 pdgstrf_factor_snode (const int, const int, SuperMatrix *, const double,
00338               yes_no_t *, int *, int *, int*, int*, int*, int*,
00339               double *, double *, pxgstrf_shared_t *, int *);
00340 extern void
00341 pxgstrf_mark_busy_descends (int, int, int *, pxgstrf_shared_t *, int *, int *);
00342 extern int  pdgstrf_snode_dfs (const int, const int, const int, const int *,
00343                    const int *, const int *, int*, int *, int *,
00344                    pxgstrf_shared_t *);
00345 extern int  pdgstrf_snode_bmod (const int, const int, const int, const int,
00346                 double *, double *, GlobalLU_t*, Gstat_t*);
00347 extern void pdgstrf_panel_dfs (const int, const int, const int, const int,
00348                    SuperMatrix *, int*, int*, int*, int*, int*, 
00349                    int*, int*, int*, int*, int*, int*, int*, int*,
00350                    double*, GlobalLU_t *);
00351 extern void pdgstrf_panel_bmod (const int, const int, const int, const int,
00352                 const int, int*, int*, int*, int*, int*, int*,
00353                 int*, int*, double*, double*, 
00354                 pxgstrf_shared_t *);
00355 extern void pdgstrf_bmod1D (const int, const int, const int, const int, 
00356                 const int, const int, const int, int, int,
00357                 int *, int *, int *, int *, double *, double *, 
00358                 GlobalLU_t *, Gstat_t *);
00359 extern void pdgstrf_bmod2D (const int, const int, const int, const int,
00360                 const int, const int, const int, int, int,
00361                 int *, int *, int *, int *, double *, double *,
00362                 GlobalLU_t *, Gstat_t *);
00363 extern void pdgstrf_bmod1D_mv2 (const int, const int, const int, const int, 
00364                 const int, const int, const int, int, int,
00365                 int *, int *, int *, int *, double *, 
00366                 double *, GlobalLU_t *, Gstat_t *);
00367 extern void pdgstrf_bmod2D_mv2 (const int, const int, const int, const int,
00368                 const int, const int, const int, int, int,
00369                 int *, int *, int *, int *, double *, double *,
00370                 GlobalLU_t *, Gstat_t *);
00371 extern void pxgstrf_super_bnd_dfs (const int, const int, const int, 
00372                    const int, const int, SuperMatrix*,
00373                    int*, int*, int*, int *, int *, int *,
00374                    int *, pxgstrf_shared_t *);
00375 extern int  pdgstrf_column_dfs(const int, const int, const int, const int,
00376                    int*, int*, int*, int, int*, int*, int*, int*,
00377                    int *, int *, int *, int *, pxgstrf_shared_t *);
00378 extern int  pdgstrf_column_bmod(const int, const int, const int, const int, 
00379                 int*, int*, double*, double*,
00380                 pxgstrf_shared_t *, Gstat_t *);
00381 extern int  pdgstrf_pivotL (const int, const int, const double, yes_no_t*,
00382                 int*, int*, int*, int*, GlobalLU_t*, Gstat_t*);
00383 extern int  pdgstrf_copy_to_ucol (const int, const int, const int, const int *,
00384                   const int *, const int *, double*,
00385                   pxgstrf_shared_t*);
00386 extern void pxgstrf_pruneL (const int, const int *, const int, const int,
00387                 const int *, const int *, int*, int *,
00388                 GlobalLU_t *);
00389 extern void pxgstrf_resetrep_col (const int, const int *, int *);
00390 extern void countnz (const int, int*, int *, int *, GlobalLU_t *);
00391 extern void fixupL (const int, const int *, GlobalLU_t *);
00392 extern void compressSUP (const int, GlobalLU_t *);
00393 extern int  spcoletree (int *, int *, int *, int, int, int *);
00394 extern int  *TreePostorder (int, int *);
00395 extern void dreadmt (int *, int *, int *, double **, int **, int **);
00396 extern void dreadhb (int *, int *, int *, double **, int **, int **);
00397 extern void dGenXtrue (int, int, double *, int);
00398 extern void dFillRHS (trans_t, int, double *, int, 
00399               SuperMatrix *, SuperMatrix *);
00400 extern void dgstrs (trans_t, SuperMatrix *, SuperMatrix*, 
00401             int*, int*, SuperMatrix*, Gstat_t *, int *);
00402 extern void dlsolve (int, int, double *, double *);
00403 extern void dusolve (int, int, double *, double *);
00404 extern void dmatvec (int, int, int, double *, double *, double *);
00405 
00406 
00407 /* ---------------
00408    BLAS 
00409    ---------------*/
00410 extern int dgemm_(char*, char*, int*, int*, int*, double*,
00411                   double*, int*, double*, int*, double*,
00412                   double*, int*);
00413 extern int dtrsm_(char*, char*, char*, char*, int*, int*, double*,
00414                   double*, int*, double*, int*);
00415 extern int dtrsv_(char*, char*, char*, int*, double*, int*,
00416                   double*, int*);
00417 extern int dgemv_(char*, int*, int*, double*, double*, 
00418            int*, double*, int*, double*, double*, int*);
00419 
00420 /* ---------------
00421    Memory related 
00422    ---------------*/
00423 extern float pdgstrf_MemInit (int, int, superlumt_options_t *,
00424             SuperMatrix *, SuperMatrix *, GlobalLU_t *);
00425 extern float pdgstrf_memory_use(const int, const int, const int);
00426 extern int  pdgstrf_WorkInit (int, int, int **, double **);
00427 extern void pxgstrf_SetIWork (int, int, int *, int **, int **, int **,
00428               int **, int **, int **, int **);
00429 extern void pdgstrf_SetRWork (int, int, double *, double **, double **);
00430 extern void pdgstrf_WorkFree (int *, double *, GlobalLU_t *);
00431 extern int  pdgstrf_MemXpand (int, int, MemType, int *, GlobalLU_t *);
00432 
00433 extern int  *intMalloc (int);
00434 extern int  *intCalloc (int);
00435 extern double *doubleMalloc(int);
00436 extern double *doubleCalloc(int);
00437 extern int  memory_usage ();
00438 extern int  superlu_dQuerySpace (int, SuperMatrix *, SuperMatrix *, int, 
00439                  superlu_memusage_t *);
00440 extern int  Glu_alloc (const int, const int, const int, const MemType,
00441                int *, pxgstrf_shared_t *);
00442 
00443 /* -------------------
00444    Auxiliary routines
00445    -------------------*/
00446 extern double  SuperLU_timer_();
00447 extern int     sp_ienv(int);
00448 extern double  dlamch_();
00449 extern int     lsame_(char *, char *);
00450 extern int     xerbla_(char *, int *);
00451 extern void    superlu_abort_and_exit(char *);
00452 extern void    ifill(int *, int, int);
00453 extern void    dfill(double *, int, double);
00454 extern void    dinf_norm_error(int, SuperMatrix *, double *);
00455 extern void    dstat_allocate(int);
00456 extern void    snode_profile(int, int *);
00457 extern void    super_stats(int, int *, int *);
00458 extern void    panel_stats(int, int, int *, Gstat_t *);
00459 extern void    PrintSumm(char *, int, int, int);
00460 extern void    dPrintPerf(SuperMatrix *, SuperMatrix *, superlu_memusage_t *,
00461              double, double, double *, double *, char *,
00462              Gstat_t *);
00463 extern void    dCompRow_to_CompCol(int m, int n, int nnz, 
00464                            double *a, int *colind, int *rowptr,
00465                            double **at, int **rowind, int **colptr);
00466 
00467 
00468 /* -----------------------
00469    Routines for debugging
00470    -----------------------*/
00471 extern void    print_lu_col(int, char *, int, int, int, int *, GlobalLU_t *);
00472 extern void    print_panel_seg(int, int, int, int, int *, int *);
00473 extern void    dcheck_zero_vec(int, char *, int, double *);
00474 extern void    check_repfnz(int, int, int, int *);
00475 
00476 #ifdef __cplusplus
00477        }
00478 #endif
00479 
00480 
00481 #endif /* __SUPERLU_DSP_DEFS */
00482
lsd_mkb/lsd_mkb_superlu/superlu_threads/pdsp_defs.h
