/*************************************************************************/
/*                                                                       */
/*  Copyright (c) 1994 Stanford University                               */
/*                                                                       */
/*  All rights reserved.                                                 */
/*                                                                       */
/*  Permission is given to use, copy, and modify this software for any   */
/*  non-commercial purpose as long as this copyright notice is not       */
/*  removed.  All other uses, including redistribution in whole or in    */
/*  part, are forbidden without prior written permission.                */
/*                                                                       */
/*  This software is provided with absolutely no warranty and no         */
/*  support.                                                             */
/*                                                                       */
/*************************************************************************/

#include <stdio.h>

#define FitsInCache 2048

#define MAX_PROC 1024
#define PAGE_SIZE 4096

typedef struct {
	long n, m, *col, *startrow, *row;
	double *nz;
	} SMatrix;

struct Pair {
	long block_num;
	struct Pair *next;
	};

typedef struct {
        long i, j, owner, remaining, nmod;
	long length; /* number of full rows in block */
	long parent; /* block number of parent block */
	double checksum;
	volatile unsigned long done;
	long *structure, *relative;
	double *nz;
	struct Pair *pair;
      } Block;

typedef union {
        Block *block;
	double nz;
      } Entry;
       
typedef struct {
        long n, *col, *row, n_blocks, n_entries, entries_allocated;
	long *partition_size, *renumbering, *mapI, *mapJ;
	long *domain, *domains, n_domains, *proc_domains;
	long n_partitions, max_partition;
	double **proc_domain_storage;
	Entry *entry;
      } BMatrix;

#define BLOCK(bl_no) (LB.entry[bl_no].block)
#define BLOCKROW(bl_no) (BLOCK(bl_no)->i)
#define BLOCKCOL(bl_no) (BLOCK(bl_no)->j)
#define OWNER(bl_no) (BLOCK(bl_no)->owner)

struct Update {
	long i, j, src, remaining;
	long dimi, dimj, *structi, *structj;
	double *update;
	struct Update *next;
      };

struct Task {
  long block_num, desti, destj, src;
  struct Update *update;
  struct Task *next;
  };

struct GlobalMemory {
	BARDEC(start)
	LOCKDEC(waitLock)
	LOCKDEC(memLock)
	unsigned long runtime[MAX_PROC];
	};

struct BlockList {
	long theBlock, row, col, length;
	long *structure;
	double *nz;
	struct BlockList *next;
	};

struct LocalCopies {
       double *blktmp;
       long max_panel;
       long *link;
       long *first;
       double *storage;
       double *updatetmp;
       long *relative;
       struct Update *freeUpdate;
       struct Task *freeTask;
       unsigned long rs;
       unsigned long rf;
       unsigned long us;
       unsigned long uf;
       unsigned long ss;
       unsigned long sf;
       unsigned long runtime;
       unsigned long runs;
       };

#define DISTRIBUTED 888

#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))

#define LB_DOMAINS 2

#define EMBED 1

#define NO_PERM 1

#define FAN_OUT 2

/*
 * amal.C
 */
long OpsFromSuper(long size, long nz);
long CountSupers(long cols, long *node);
void Amalgamate2(long join, SMatrix M, long *T, long *nz, long *node, long *domain, long target_size);
void ConsiderMerge(long join, long super, SMatrix M, long *nz, long *node, long *domain, long target_size, long traversal_order);
void JoinTwoSupers2(long *nz, long *node, long child, long parent);
void ReorderMatrix(SMatrix M, long super, long *node, long *counter, long *PERM);
void FixNodeNZAndT(SMatrix M, long *PERM, long *node, long *nz, long *T);
void InvertPerm(long n, long *PERM, long *INVP);
double PathLength(long cols, long rows, long target_panel_size);

/*
 * assign.C
 */
void PDIV(long src_col, long src_nz, double *ops, double *misses, double *runtime);
void PMOD(long src_col, long dest_col, long dest_nz, double *ops, double *misses, double *runtime);
void PADD(long cols, long rows, double *misses, double *runtime);
void AssignBlocksNow(void);
void EmbedBlocks(void);

/*
 * bfac.C
 */
void BFac(long diag, struct LocalCopies *lc);
void OneFac(double *A, long n1, long n2);
void BDiv(long n1, long n3, double *diag_nz, double *below_nz, struct LocalCopies *lc);
void OneDiv(double *A, double *B, long n1, long n3, long n4);
void BMod(long n1, long n2, long n3, double *top_nz, double *bend_nz, double *dest_nz, struct LocalCopies *lc);
void CopyBlock(double *B, double *dest, long n3, long is, long ks, long il, long kl);
void CopyBlockBack(double *B, double *src, long n3, long is, long ks, long il, long kl);
void OneMatmat(double *B, double *A, double *C, long n1, long n2, long n3, long n4, long n5);
void BLMod(long n1, long n2, double *left_nz, double *dest_nz, struct LocalCopies *lc);
void OneLower(double *A, double *C, long n1, long n2, long n3);
void FindBlockUpdate(long domain, long blj, long bli, double **update, long *stride);

/*
 * bksolve.C
 */
double *TriBSolve(BMatrix LB, double *b, long *PERM);
double ComputeNorm(double *x, long n);
double *CreateVector(SMatrix M);

/*
 * block2.C
 */
void CreateBlockedMatrix2(SMatrix M, long block_ub, long *T, long *firstchild, long *child, long *PERM, long *INVP, long *domain, long *partition);
long FindNumPartitions(long set_size, long piece_size);
void ComputeBlockParents(long *T);
void FillInStructure(SMatrix M, long *firstchild, long *child, long *PERM, long *INVP);
void FillInNZ(SMatrix M, long *PERM, long *INVP);
void FindDomStructure(long super, long *nz, long n_nz);
void FindDummyDomainStructure(long which_domain);
void CheckColLength(long col, long n_nz);
void FindBlStructure(SMatrix M, long super, long *PERM, long *INVP, long *firstchild, long *child, long *structure, long *nz);
void FindSuperStructure(SMatrix M, long super, long *PERM, long *INVP, long *firstchild, long *child, long *structure, long *nz, long *n_nz);
void FindDetailedStructure(long col, long *structure, long *nz, long n_nz);
void AllocateNZ(void);
void FillIn(SMatrix M, long col, long *PERM, long *INVP, double *scatter);
void InsSort(long *nz, long n);
long BlDepth(long col);
void SortByKey(long n, long *blocks, long *keys);
void DumpSizes(BMatrix LB, long *domain, long *sizes);
void ComputePartitionNumbering(long *numbering);
void FindMachineDimensions(long P);
long EmbeddedOwner(long block);

/*
 * fo.C
 */
void PreProcessFO(long MyNum);
void PreAllocate1FO(void);
void PreAllocateFO(long MyNum, struct LocalCopies *lc);
void BNumericSolveFO(long MyNum, struct LocalCopies *lc);
void DriveParallelFO(long MyNum, struct LocalCopies *lc);
long HandleTaskFO(long MyNum, struct LocalCopies *lc);
void DiagReceived(long diag, long MyNum, struct LocalCopies *lc);
void BlockReceived(long block, long MyNum, struct LocalCopies *lc);
struct BlockList *CopyOneBlock(long block, long MyNum);
void FreeColumnListFO(long p, long col);
void DecrementRemaining(long dest_block, long MyNum, struct LocalCopies *lc);
void PerformUpdate(struct BlockList *above_bl, struct BlockList *below_bl, long MyNum, struct LocalCopies *lc);
void DistributeUpdateFO(long which_domain, long MyNum, struct LocalCopies *lc);
void HandleUpdate2FO(long which_domain, long bli, long blj, long MyNum, struct LocalCopies *lc);
void FindRelativeIndices(long *src_structure, long src_len, long *dest_structure, long *relative);
void BlockReadyFO(long block, long MyNum, struct LocalCopies *lc);
void BlockDoneFO(long block, long MyNum, struct LocalCopies *lc);
void CheckRemaining(void);
void CheckReceived(void);
void ComputeRemainingFO(void);
void InitRemainingFO(long MyNum);
void ComputeReceivedFO(void);
void InitReceivedFO(long MyNum);
void ScatterUpdateFO(long dimi, long *structi, long dimj, long *structj, long destdim, double *oldupdate, double *newupdate);
void ScatterUpdateFO2(long dimi, long *structi, long dimj, long *structj, long stride, long destdim, double *oldupdate, double *newupdate);

/*
 * malloc.C
 */
void MallocInit(long P);
void InitOneFreeList(long p);
void MallocStats(void);
long FindBucket(long size);
char *MyMalloc(long size, long home);
void MigrateMem(long *start, long length, long home);
void MyFree(long *block);
void MyFreeNow(long *block);

/*
 * mf.C
 */
void InitTaskQueues(long P);
long FindBlock(long i, long j);
void Send(long src_block, long dest_block, long desti, long destj, struct Update *update, long p, long MyNum, struct LocalCopies *lc);
long TaskWaiting(long MyNum);
void GetBlock(long *desti, long *destj, long *src, struct Update **update, long MyNum, struct LocalCopies *lc);

/*
 * numLL.C
 */
void FactorLLDomain(long which_domain, long MyNum, struct LocalCopies *lc);
void CompleteSupernodeB(long super);
void CompleteColumnB(long j);
void FindRelativeIndicesLeft(long *src_structure, long rows_in_update, long offset, long *indices, long *relative);
void ScatterSuperUpdate(double *update, long cols_in_update, long rows_in_update, double *dest_nz, long dest_len, long *relative);
void ModifySuperByColumn(double *src_nz, long cols_in_update, long rows_in_update, double *dest_nz, long dest_len, long *relative);
void SetDestIndices(long super, long *indices);
void SetDomainIndices(long super, long *indices);
void ModifySuperBySuper(long src, long theFirst, long theLast, long length, double *dest);
void ModifyTwoBySupernodeB(long super, long lastcol, long theFirst, double *destination0, double *destination1);
void ModifyBySupernodeB(long super, long lastcol, long theFirst, double *destination);

/*
 * parts.C
 */
void Partition(SMatrix M, long parts, long *T, long *assigned_ops, long *domain, long *domains, long *proc_domains);
void MarkSubtreeAsDomain(long *domain, long root);
void NumberPartition(long parts, long *assigned_ops, long distribute);
long MaxBucket(long *assigned_ops, long parts);
long MinBucket(long *assigned_ops, long parts);
struct Chunk *NewChunk(void);
struct Chunk *GetChunk(void);

/*
 * seg.C
 */
void ComputeTargetBlockSize(SMatrix M, long P);
void FindMaxHeight(SMatrix L, long root, long height, long *maxm);
void NoSegments(SMatrix M);
void CreatePermutation(long n, long *PERM, long permutation_method);

/*
 * solve.C
 */
void Go(void);
void PlaceDomains(long P);
void ComposePerm(long *PERM1, long *PERM2, long n);

/*
 * tree.C
 */
void EliminationTreeFromA(SMatrix A, long *T, long *P, long *INVP);
void ParentToChild(long *T, long n, long *firstchild, long *child);
void ComputeNZ(SMatrix A, long *T, long *nz, long *PERM, long *INVP);
void FindSupernodes(SMatrix A, long *T, long *nz, long *node);
void ComputeWorkTree(SMatrix A, long *nz, double *work_tree);

/*
 * util.C
 */
SMatrix NewMatrix(long n, long m, long nz);
void FreeMatrix(SMatrix M);
double *NewVector(long n);
double Value(long i, long j);
SMatrix ReadSparse(char *name, char *probName);
void DumpLine(FILE *fp);
void ParseIntFormat(char *buf, long *num, long *size);
void ReadVector(FILE *fp, long n, long *where, long perline, long persize);
SMatrix LowerToFull(SMatrix L);
void ISort(SMatrix M, long k);