/[ascend]/trunk/ascend4/solver/model_reorder.h
ViewVC logotype

Contents of /trunk/ascend4/solver/model_reorder.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1 - (show annotations) (download) (as text)
Fri Oct 29 20:54:12 2004 UTC (17 years, 6 months ago) by aw0a
File MIME type: text/x-chdr
File size: 8907 byte(s)
Setting up web subdirectory in repository
1 /*
2 * Model-based Reordering Routines
3 * by Benjamin Andrew Allan
4 * 6/22/96
5 * Version: $Revision: 1.5 $
6 * Version control file: $RCSfile: model_reorder.h,v $
7 * Date last modified: $Date: 1997/07/18 12:14:44 $
8 * Last modified by: $Author: mthomas $
9 * Copyright(C) 1996 Benjamin Andrew Allan
10 *
11 * This file is part of the ASCEND IV math programming system.
12 * These functions are part of a new design for feeding
13 * solvers from the ASCEND compiler.
14 *
15 * File to play MODEL-relation based reordering games.
16 * We're starting with a basic RBBD implementation.
17 * Assumptions:
18 * - If the MODELs are hierarchical, then they have been indexed in a
19 * tree bottom-up fashion.
20 * - Input is a square block that needs tearing and not a rectangle.
21 *
22 * The ASCEND IV math programming system is free software; you can redistribute
23 * it and/or modify it under the terms of the GNU General Public License as
24 * published by the Free Software Foundation; either version 2 of the
25 * License, or (at your option) any later version.
26 *
27 * The ASCEND IV math programming system is distributed in hope that it will be
28 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
29 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
30 * General Public License for more details.
31 *
32 * You should have received a copy of the GNU General Public License along with
33 * the program; if not, write to the Free Software Foundation, Inc., 675
34 * Mass Ave, Cambridge, MA 02139 USA. Check the file named COPYING.
35 * COPYING is found in ../compiler.
36 */
37 #ifndef _model_reorder_h_seen_
38 #define _model_reorder_h_seen_
39 /* requires #include "base.h" */
40 /* requires #include "slv_types.h" */
41 /* requires #include "mtx.h" */
42
43 #define MRDEBUG 0
44 /* if !=0, generate spew while working */
45 #define CUTOFFDEFAULT 1000
46 /* tuning parameter in need of investigation */
47
48 typedef struct mr_bisection_structure {
49 /* data spaces */
50 slv_system_t slv;
51 mtx_matrix_t mtx;
52 int32 *local; /* MODEL indexed array of counts of relations */
53 char *active; /* in block flags for models */
54 int32 *tmpmodlist; /* a unique list of indices of models found so far */
55 int32 tmpmodused; /* currently used length of tmpmodlist */
56 int32 activelen; /* length of active,local and tmpmodlist arrays */
57
58 /* control parameters */
59 int32 cutoff;
60 int32 maxtears;
61 double maxtearfraction;
62
63 /* miscellaneous statistics */
64 int32 ntears;
65 int32 nblts;
66 } mr_reorder_t;
67 /************************************************************************\
68 The mr_reorder_t is a workspace structure containing most of the items
69 needed for the recursive function mr_bisect_partition and any similar
70 functions. mr_reorder_create and destroy are provided to set up
71 a mr_reorder_t.
72 - The mtx herein should correspond to the solvers_rel/var lists of the
73 slv_system_t here.
74 - The pointers local, tmpmodlist, and active should contain arrays of
75 size activelen and these arrays should be (re)initialized to 0
76 for each call of mr_bisect_partition.
77 - Activelen should be the number of models in the slv_system_t. In
78 particular array[rel_model(rel)] should exist for all rel in the
79 solvers_rel_list.
80 - Cutoff is the smallest block the user wants us to try to tear.
81 - Maxtears is the largest number of tears user wants to allow in any
82 single block. IT IS IGNORED.
83 - Maxtearfraction is the largest percentage of any single block the
84 user wants us to try to tear. IT IS IGNORED.
85 - Ntears is the number of tear columns we find.
86 - Nblts is the number of BLT permutations we do.
87 \************************************************************************/
88
89 extern mr_reorder_t *mr_reorder_create(slv_system_t, mtx_matrix_t, int32);
90 /************************************************************************\
91 mrsys = mr_reorder_create(slvsys,mtx,nmodels);
92 Returns a mr_reorder_t all set up with cutoff set to CUTOFFDEFAULT
93 for a problem that has nmodels models in it.
94 The arrays are initialized to 0.
95 rel_model(rel) of any rel in slvsys should return a number 0..nmodels-1.
96 Returns NULL if insufficient memory.
97 \************************************************************************/
98
99 extern void mr_reorder_destroy(mr_reorder_t *);
100 /************************************************************************\
101 mr_reorder_destroy(mrsys);
102 Deallocate a mr_reorder_t *.
103 \************************************************************************/
104
105 typedef int (MRBlockReorderF)(slv_system_t,mtx_matrix_t,mtx_region_t *);
106 /************************************************************************\
107 This is a user supplied function that will be applied called
108 with sys->slv,sys->mtx, and regions that fall below sys->cutoff
109 in size. The user may do any sort of logic they care to,
110 including ignoring reordering blocks below a certain size. It
111 must be supplied, even if it does nothing.
112
113 This function could be dumb and just apply SPK1-like things, or
114 be very smart and reorder based on the number and type of models
115 found in the region. This function should be the subject of some
116 experimentation since mr_bisect_partition just identifies tears
117 and subregions.
118
119 This function is also the one called on blocks bigger than the
120 cutoff size that however contain equations from exactly 1 MODEL.
121
122 We don't (yet, anyway) check the return value.
123 \************************************************************************/
124
125 extern int mr_bisect_partition(mr_reorder_t *, mtx_region_t *, int,
126 MRBlockReorderF);
127 /************************************************************************\
128 stat = mr_bisect_partition(sys, reg, top, rfunc);
129 mr_reorder_t *sys;
130 mtx_region_t *reg;
131 int top;
132 MRBlockReorderF rfunc;
133
134 This function is recursive and produces a sys->mtx reordered to be
135 recursive block bordered diagonal (RBBD).
136
137 If top is 1, the region given in block should be (within itself)
138 a strongly connected square block. If top is 0, we will do a BLT
139 permutation on the region first assuming the region is square
140 and has a full diagonal. The normal mode of externally calling
141 this function should be with top==1 and we then recurse with
142 top==0.
143
144 One the outermost call, the relations in reg should have all
145 their REL_TORN flag bits set to 0. On return from the outermost
146 call, the columns identified as tears will have the REL_TORN
147 flag bits set to 1. It turns out we don't use the REL_PARTITION
148 flag.
149
150 The mr_reorder_t * given must be filled in completely before
151 calling this function. Anything amiss will cause us to return
152 immediately without doing anything. Returns 0 if ok, > 0 if
153 anything else wrong. Basically, the only thing that can go
154 wrong is, if during one of our blt permutations, we run out
155 of memory. Nonzero return value will be the number of times
156 we encountered malloc failure.
157
158 The values in reg may be messed with, so if the data in
159 reg is needed after this function call, keep it elsewhere.
160 \************************************************************************/
161
162 extern int mr_bisect_partition2(mr_reorder_t *, mtx_region_t *, int,
163 MRBlockReorderF);
164 /************************************************************************\
165 stat = mr_bisect_partition2(sys, reg, top, rfunc);
166 mr_reorder_t *sys;
167 mtx_region_t *reg;
168 int top;
169 MRBlockReorderF rfunc;
170
171 This is the function most similar to the algorithm described/tested
172 in the Abbott thesis.
173
174 This function is recursive and produces a sys->mtx reordered to be
175 recursive block bordered diagonal (RBBD) with borders roughly twice
176 the size of those in mr_bisect_partition because of a simple idiocy
177 in the way it locates tears. The relative performance of the two
178 versions is not clear.
179
180 If top is 1, the region given in block should be (within itself)
181 a strongly connected square block. If top is 0, we will do a BLT
182 permutation on the region first assuming the region is square
183 and has a full diagonal. The normal mode of externally calling
184 this function should be with top==1 and we then recurse with
185 top==0.
186
187 One the outermost call, the relations in reg should have all
188 their REL_TORN flag bits set to 0. On return from the outermost
189 call, the columns identified as tears will have the REL_TORN
190 flag bits set to 1. It turns out we don't use the REL_PARTITION
191 flag.
192
193 The mr_reorder_t * given must be filled in completely before
194 calling this function. Anything amiss will cause us to return
195 immediately without doing anything. Returns 0 if ok, > 0 if
196 anything else wrong. Basically, the only thing that can go
197 wrong is, if during one of our blt permutations, we run out
198 of memory. Nonzero return value will be the number of times
199 we encountered malloc failure.
200
201 The values in reg may be messed with, so if the data in
202 reg is needed after this function call, keep it elsewhere.
203 \************************************************************************/
204 #endif /* _model_reorder_h_seen_ */

john.pye@anu.edu.au
ViewVC Help
Powered by ViewVC 1.1.22