Parent Directory | 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)

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 |