| /*************************************************************************/ |
| /* */ |
| /* 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. */ |
| /* */ |
| /*************************************************************************/ |
| |
| EXTERN_ENV |
| |
| #include "matrix.h" |
| #include <math.h> |
| |
| double max_block_size; |
| extern long *node; |
| long *boundary, *next_in_segment, *next_segment, *sets_affected, n_affected; |
| long *partition; |
| long *segment_perm; |
| |
| void ComputeTargetBlockSize(SMatrix M, long P) |
| { |
| long max_ht; |
| double total_ops; |
| extern double *work_tree; |
| |
| max_ht = 0; |
| FindMaxHeight(M, M.n, 0, &max_ht); |
| |
| total_ops = work_tree[M.n]; |
| |
| max_block_size = sqrt(total_ops/(3*max_ht)/P); |
| |
| printf("%ld max height, %.0f ops, %.2f conc, %.2f bl for %ld P\n", |
| max_ht, total_ops, total_ops/(3*max_ht), max_block_size, P); |
| |
| } |
| |
| void FindMaxHeight(SMatrix L, long root, long height, long *maxm) |
| { |
| long i; |
| extern long *firstchild, *child; |
| |
| if (height > *maxm) |
| *maxm = height; |
| |
| for (i=firstchild[root]; i<firstchild[root+1]; i++) |
| FindMaxHeight(L, child[i], height+1, maxm); |
| } |
| |
| |
| void NoSegments(SMatrix M) |
| { |
| long i; |
| |
| partition = (long *) MyMalloc(M.n*sizeof(long), DISTRIBUTED); |
| for (i=0; i<M.n; i++) |
| partition[i] = node[i]; |
| } |
| |
| |
| void CreatePermutation(long n, long *PERM, long permutation_method) |
| { |
| long j; |
| |
| PERM[n] = n; |
| if (permutation_method == NO_PERM) { |
| for (j=0; j<n; j++) |
| PERM[j] = j; |
| } |
| } |
| |