Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
memory.c
Go to the documentation of this file.
1 /*
2  * Copyright 1997, Regents of the University of Minnesota
3  *
4  * memory.c
5  *
6  * This file contains routines that deal with memory allocation
7  *
8  * Started 2/24/96
9  * George
10  *
11  * $Id: memory.c,v 1.2 1998/11/27 18:16:18 karypis Exp $
12  *
13  */
14 
15 #include <metis.h>
16 
17 
18 /*************************************************************************
19 * This function allocates memory for the workspace
20 **************************************************************************/
21 void AllocateWorkSpace(CtrlType *ctrl, GraphType *graph, int nparts)
22 {
23  ctrl->wspace.pmat = NULL;
24 
25  if (ctrl->optype == OP_KMETIS) {
26  ctrl->wspace.edegrees = (EDegreeType *)GKmalloc(graph->nedges*sizeof(EDegreeType), "AllocateWorkSpace: edegrees");
27  ctrl->wspace.vedegrees = NULL;
28  ctrl->wspace.auxcore = (idxtype *)ctrl->wspace.edegrees;
29 
30  ctrl->wspace.pmat = idxmalloc(nparts*nparts, "AllocateWorkSpace: pmat");
31 
32  /* Memory requirements for different phases
33  Coarsening
34  Matching: 4*nvtxs vectors
35  Contraction: 2*nvtxs vectors (from the above 4), 1*nparts, 1*Nedges
36  Total = MAX(4*nvtxs, 2*nvtxs+nparts+nedges)
37 
38  Refinement
39  Random Refinement/Balance: 5*nparts + 1*nvtxs + 2*nedges
40  Greedy Refinement/Balance: 5*nparts + 2*nvtxs + 2*nedges + 1*PQueue(==Nvtxs)
41  Total = 5*nparts + 3*nvtxs + 2*nedges
42 
43  Total = 5*nparts + 3*nvtxs + 2*nedges
44  */
45  ctrl->wspace.maxcore = 3*(graph->nvtxs+1) + /* Match/Refinement vectors */
46  5*(nparts+1) + /* Partition weights etc */
47  graph->nvtxs*(sizeof(ListNodeType)/sizeof(idxtype)) + /* Greedy k-way balance/refine */
48  20 /* padding for 64 bit machines */
49  ;
50  }
51  else if (ctrl->optype == OP_KVMETIS) {
52  ctrl->wspace.edegrees = NULL;
53  ctrl->wspace.vedegrees = (VEDegreeType *)GKmalloc(graph->nedges*sizeof(VEDegreeType), "AllocateWorkSpace: vedegrees");
54  ctrl->wspace.auxcore = (idxtype *)ctrl->wspace.vedegrees;
55 
56  ctrl->wspace.pmat = idxmalloc(nparts*nparts, "AllocateWorkSpace: pmat");
57 
58  /* Memory requirements for different phases are identical to KMETIS */
59  ctrl->wspace.maxcore = 3*(graph->nvtxs+1) + /* Match/Refinement vectors */
60  3*(nparts+1) + /* Partition weights etc */
61  graph->nvtxs*(sizeof(ListNodeType)/sizeof(idxtype)) + /* Greedy k-way balance/refine */
62  20 /* padding for 64 bit machines */
63  ;
64  }
65  else {
66  ctrl->wspace.edegrees = (EDegreeType *)idxmalloc(graph->nedges, "AllocateWorkSpace: edegrees");
67  ctrl->wspace.vedegrees = NULL;
68  ctrl->wspace.auxcore = (idxtype *)ctrl->wspace.edegrees;
69 
70  ctrl->wspace.maxcore = 5*(graph->nvtxs+1) + /* Refinement vectors */
71  4*(nparts+1) + /* Partition weights etc */
72  2*graph->ncon*graph->nvtxs*(sizeof(ListNodeType)/sizeof(idxtype)) + /* 2-way refinement */
73  2*graph->ncon*(NEG_GAINSPAN+PLUS_GAINSPAN+1)*(sizeof(ListNodeType *)/sizeof(idxtype)) + /* 2-way refinement */
74  20 /* padding for 64 bit machines */
75  ;
76  }
77 
78  ctrl->wspace.maxcore += HTLENGTH;
79  ctrl->wspace.core = idxmalloc(ctrl->wspace.maxcore, "AllocateWorkSpace: maxcore");
80  ctrl->wspace.ccore = 0;
81 }
82 
83 
84 /*************************************************************************
85 * This function allocates memory for the workspace
86 **************************************************************************/
88 {
89  GKfree(&ctrl->wspace.edegrees, &ctrl->wspace.vedegrees, &ctrl->wspace.core, &ctrl->wspace.pmat, LTERM);
90 }
91 
92 /*************************************************************************
93 * This function returns how may words are left in the workspace
94 **************************************************************************/
96 {
97  return ctrl->wspace.maxcore - ctrl->wspace.ccore;
98 }
99 
100 
101 /*************************************************************************
102 * This function allocate space from the core
103 **************************************************************************/
105 {
106  n += n%2; /* This is a fix for 64 bit machines that require 8-byte pointer allignment */
107 
108  ctrl->wspace.ccore += n;
109  ASSERT(ctrl->wspace.ccore <= ctrl->wspace.maxcore);
110  return ctrl->wspace.core + ctrl->wspace.ccore - n;
111 }
112 
113 /*************************************************************************
114 * This function frees space from the core
115 **************************************************************************/
116 void idxwspacefree(CtrlType *ctrl, int n)
117 {
118  n += n%2; /* This is a fix for 64 bit machines that require 8-byte pointer allignment */
119 
120  ctrl->wspace.ccore -= n;
121  ASSERT(ctrl->wspace.ccore >= 0);
122 }
123 
124 
125 /*************************************************************************
126 * This function allocate space from the core
127 **************************************************************************/
128 float *fwspacemalloc(CtrlType *ctrl, int n)
129 {
130  n += n%2; /* This is a fix for 64 bit machines that require 8-byte pointer allignment */
131 
132  ctrl->wspace.ccore += n;
133  ASSERT(ctrl->wspace.ccore <= ctrl->wspace.maxcore);
134  return (float *) (ctrl->wspace.core + ctrl->wspace.ccore - n);
135 }
136 
137 /*************************************************************************
138 * This function frees space from the core
139 **************************************************************************/
140 void fwspacefree(CtrlType *ctrl, int n)
141 {
142  n += n%2; /* This is a fix for 64 bit machines that require 8-byte pointer allignment */
143 
144  ctrl->wspace.ccore -= n;
145  ASSERT(ctrl->wspace.ccore >= 0);
146 }
147 
148 
149 
150 /*************************************************************************
151 * This function creates a CoarseGraphType data structure and initializes
152 * the various fields
153 **************************************************************************/
155 {
156  GraphType *graph;
157 
158  graph = (GraphType *)GKmalloc(sizeof(GraphType), "CreateCoarseGraph: graph");
159 
160  InitGraph(graph);
161 
162  return graph;
163 }
164 
165 
166 /*************************************************************************
167 * This function creates a CoarseGraphType data structure and initializes
168 * the various fields
169 **************************************************************************/
171 {
172  graph->gdata = graph->rdata = NULL;
173 
174  graph->nvtxs = graph->nedges = -1;
175  graph->mincut = graph->minvol = -1;
176 
177  graph->xadj = graph->vwgt = graph->adjncy = graph->adjwgt = NULL;
178  graph->adjwgtsum = NULL;
179  graph->label = NULL;
180  graph->cmap = NULL;
181 
182  graph->where = graph->pwgts = NULL;
183  graph->id = graph->ed = NULL;
184  graph->bndptr = graph->bndind = NULL;
185  graph->rinfo = NULL;
186  graph->vrinfo = NULL;
187  graph->nrinfo = NULL;
188 
189  graph->ncon = -1;
190  graph->nvwgt = NULL;
191  graph->npwgts = NULL;
192 
193  graph->vsize = NULL;
194 
195  graph->coarser = graph->finer = NULL;
196 
197 }
198 
199 /*************************************************************************
200 * This function deallocates any memory stored in a graph
201 **************************************************************************/
203 {
204 
205  GKfree(&graph->gdata, &graph->nvwgt, &graph->rdata, &graph->npwgts, LTERM);
206  free(graph);
207 }
208 
EDegreeType * edegrees
Definition: struct.h:102
NRInfoType * nrinfo
Definition: struct.h:190
#define idxwspacefree
Definition: rename.h:165
VEDegreeType * vedegrees
Definition: struct.h:103
#define HTLENGTH
Definition: defs.h:26
int ccore
Definition: struct.h:100
idxtype * pwgts
Definition: struct.h:176
idxtype * cmap
Definition: struct.h:172
idxtype * adjwgtsum
Definition: struct.h:168
int optype
Definition: struct.h:222
VRInfoType * vrinfo
Definition: struct.h:187
idxtype * ed
Definition: struct.h:181
idxtype * id
Definition: struct.h:181
void fwspacefree(CtrlType *ctrl, int n)
Definition: memory.c:140
#define FreeGraph
Definition: rename.h:169
int mincut
Definition: struct.h:175
idxtype * bndptr
Definition: struct.h:178
idxtype * core
Definition: struct.h:99
idxtype * rdata
Definition: struct.h:157
#define idxwspacemalloc
Definition: rename.h:164
struct graphdef * coarser
Definition: struct.h:198
struct graphdef * finer
Definition: struct.h:198
HitTile_Vector graph
idxtype * where
Definition: struct.h:176
#define LTERM
Definition: defs.h:18
float * npwgts
Definition: struct.h:196
int idxtype
Definition: struct.h:19
#define AllocateWorkSpace
Definition: rename.h:161
#define fwspacemalloc
Definition: rename.h:166
#define OP_KVMETIS
Definition: defs.h:94
idxtype * label
Definition: struct.h:170
idxtype * adjwgt
Definition: struct.h:166
RInfoType * rinfo
Definition: struct.h:184
int maxcore
Definition: struct.h:100
#define WspaceAvail
Definition: rename.h:163
void GKfree(void **ptr1,...)
Definition: util.c:121
int ncon
Definition: struct.h:194
#define CreateGraph
Definition: rename.h:167
#define GKmalloc
Definition: rename.h:387
idxtype * auxcore
Definition: struct.h:106
idxtype * bndind
Definition: struct.h:178
#define NEG_GAINSPAN
Definition: defs.h:24
#define OP_KMETIS
Definition: defs.h:90
struct ListNodeType ListNodeType
Definition: struct.h:46
#define FreeWorkSpace
Definition: rename.h:162
idxtype * vwgt
Definition: struct.h:163
#define PLUS_GAINSPAN
Definition: defs.h:23
int minvol
Definition: struct.h:175
int nedges
Definition: struct.h:161
#define idxmalloc
Definition: rename.h:383
idxtype * pmat
Definition: struct.h:108
idxtype * gdata
Definition: struct.h:157
int nvtxs
Definition: struct.h:161
WorkSpaceType wspace
Definition: struct.h:227
#define ASSERT(expr)
Definition: macros.h:130
float * nvwgt
Definition: struct.h:195
idxtype * vsize
Definition: struct.h:164
idxtype * adjncy
Definition: struct.h:165
idxtype * xadj
Definition: struct.h:162
#define InitGraph
Definition: rename.h:168