SCM

SCM Repository

[matrix] Annotation of /pkg/src/Metis/memory.c
ViewVC logotype

Annotation of /pkg/src/Metis/memory.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 10 - (view) (download) (as text)

1 : bates 10 /*
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.1 2003/12/31 21:32:30 bates 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 :     **************************************************************************/
87 :     void FreeWorkSpace(CtrlType *ctrl, GraphType *graph)
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 :     **************************************************************************/
95 :     int WspaceAvail(CtrlType *ctrl)
96 :     {
97 :     return ctrl->wspace.maxcore - ctrl->wspace.ccore;
98 :     }
99 :    
100 :    
101 :     /*************************************************************************
102 :     * This function allocate space from the core
103 :     **************************************************************************/
104 :     idxtype *idxwspacemalloc(CtrlType *ctrl, int n)
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 :     **************************************************************************/
154 :     GraphType *CreateGraph(void)
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 :     **************************************************************************/
170 :     void InitGraph(GraphType *graph)
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 :     **************************************************************************/
202 :     void FreeGraph(GraphType *graph)
203 :     {
204 :    
205 :     GKfree(&graph->gdata, &graph->nvwgt, &graph->rdata, &graph->npwgts, LTERM);
206 :     free(graph);
207 :     }
208 :    

root@r-forge.r-project.org
ViewVC Help
Powered by ViewVC 1.0.0  
Thanks to:
Vienna University of Economics and Business Powered By FusionForge