1 #ifdef _MSC_VER
2 #define inline __inline
3 #endif
4
5 #include <stdlib.h>
6 #include <assert.h>
7
8 #include "decode.h"
9 #include "lib.h"
10 #include "librcps.h"
11
12 #include <stdio.h>
13
14 #define UNSCHEDULED -1
15
16 // XXX this sizing might make sense on 32-bit platforms, but not on 64 bit?
17 struct edge {
18 int time;
19 int amount;
20 struct edge *next;
21 };
22
23 struct decoding_state {
24 int *res_load;
25 struct edge **res_edges;
26 };
27
28 /* XXX we already search the lists to find the place where to add the edge, it's
29 * stupid to search the lists again. addedge should also get an edge from which
30 * to search from */
addedge(struct rcps_resource * r,const int time,const int duration,const int amount,struct decoding_state * state)31 static inline void addedge(struct rcps_resource *r, const int time,
32 const int duration, const int amount, struct decoding_state *state) {
33 struct edge *cedge;
34 struct edge *nedge;
35 struct edge *last = NULL;
36 cedge = state->res_edges[r->index];
37 while ((cedge != NULL) && (cedge->time < time)) {
38 last = cedge;
39 cedge = cedge->next;
40 }
41 if ((cedge != NULL) && (cedge->time == time)) {
42 cedge->amount += amount;
43 assert(cedge->amount >= 0);
44 last = cedge;
45 cedge = cedge->next;
46 }
47 else {
48 // XXX perhaps do not malloc, but take from list. might be faster and
49 // cache-aligned
50 nedge = (struct edge*)malloc(sizeof(struct edge));
51 nedge->time = time;
52 nedge->next = cedge;
53 last->next = nedge;
54 nedge->amount = last->amount + amount;
55 assert(nedge->amount >= 0);
56 last = nedge;
57 }
58
59 while ((cedge != NULL) && (cedge->time < (time + duration))) {
60 cedge->amount += amount;
61 last = cedge;
62 cedge = cedge->next;
63 }
64 if (cedge == NULL) {
65 // XXX perhaps do not malloc, but take from list. might be faster and
66 // cache-aligned
67 nedge = (struct edge*)malloc(sizeof(struct edge));
68 nedge->time = time + duration;
69 nedge->amount = 0;
70 nedge->next = NULL;
71 last->next = nedge;
72 }
73
74 // set the load to the maximum
75 if (state->res_load[r->index] < amount) {
76 state->res_load[r->index] = amount;
77 }
78
79 assert(state->res_edges[r->index]->time == 0);
80 }
81
82 /* find the first time >= start where the job can be scheduled without
83 * exceeding any resource limitations
84 * */
postpone(struct rcps_solver * solver,struct rcps_problem * problem,struct rcps_genome * genome,struct rcps_job * job,int start,struct decoding_state * state,struct rcps_phenotype * pheno)85 int postpone(struct rcps_solver *solver, struct rcps_problem *problem,
86 struct rcps_genome *genome, struct rcps_job *job, int start,
87 struct decoding_state *state, struct rcps_phenotype *pheno) {
88 int i;
89 int max_load;
90 int ltime;
91 int max_ltime;
92 int duration = 0;
93 struct rcps_request *crequest;
94 struct rcps_resource *cresource;
95 struct rcps_mode *cmode;
96 struct edge *cedge;
97 struct rcps_alternative *calternative;
98 assert(start >= 0);
99
100 max_ltime = start;
101 cmode = job->modes[
102 job->genome_position != -1
103 ? genome->modes[job->genome_position]
104 : 0
105 ];
106 duration = cmode->duration;
107 if (solver->duration_callback) {
108 duration = solver->duration_callback(DURATION_FORWARD, start,
109 cmode->duration, cmode->cb_arg);
110 //printf("postpone: %s direction=%d, start=%d = duration=%d\n", job->name, DURATION_FORWARD, start, duration);
111 }
112
113 for (i = 0; i < cmode->request_count; i++) {
114 int pos = 0;
115 if (cmode->requests[i]->genome_position != -1) {
116 pos = genome->alternatives[cmode->requests[i]->genome_position];
117 }
118 }
119
120 /* find the first possible start time */
121 for (i = 0; i < cmode->request_count; i++) {
122 ltime = start;
123 calternative = cmode->requests[i]->alternatives[
124 cmode->requests[i]->genome_position != -1
125 ? genome->alternatives[cmode->requests[i]->genome_position]
126 : 0
127 ];
128 crequest = cmode->requests[i];
129 cresource = crequest->alternatives[
130 crequest->genome_position != -1
131 ? genome->alternatives[crequest->genome_position]
132 : 0
133 ]->resource;
134 /* ignore requests which go to a non-renewable resource */
135 if (calternative->resource->type == RCPS_RESOURCE_NONRENEWABLE) {
136 break;
137 }
138 /* try at start time */
139 /* get the maximum resource usage during the interval */
140 max_load = 0;
141 cedge = state->res_edges[calternative->resource->index];
142 while ((cedge != NULL) && (cedge->time < (start + duration))) {
143 if (cedge->time <= start) {
144 max_load = cedge->amount;
145 }
146 else if (cedge->time < (start + duration)) {
147 max_load = kpt_max(max_load, cedge->amount);
148 }
149 cedge = cedge->next;
150 }
151 if ((max_load > (calternative->resource->avail
152 - calternative->amount))
153 // for resource requests which are greater than the amount
154 // available
155 && (max_load != 0)) {
156 cedge = state->res_edges[calternative->resource->index];
157 start = start + 1;
158 while (cedge != NULL) {
159 if ((cedge->time >= start) && (cedge->amount < max_load)) {
160 start = cedge->time;
161 break;
162 }
163 cedge = cedge->next;
164 }
165 // return postpone(problem, genome, job, start + 1);
166 return postpone(solver, problem, genome, job, start, state, pheno);
167 }
168 }
169 /* ok, do it at that time */
170 pheno->job_start[job->index] = start;
171 pheno->job_duration[job->index] = duration;
172 /* add the edges */
173 for (i = 0; i < cmode->request_count; i++) {
174 crequest = cmode->requests[i];
175 cresource = crequest->alternatives[
176 crequest->genome_position != -1
177 ? genome->alternatives[crequest->genome_position]
178 : 0
179 ]->resource;
180 if (cresource->type == RCPS_RESOURCE_NONRENEWABLE) {
181 state->res_load[cresource->index] += crequest->alternatives[
182 crequest->genome_position != -1
183 ? genome->alternatives[crequest->genome_position]
184 : 0
185 ]->amount;
186 }
187 else if (cresource->type == RCPS_RESOURCE_RENEWABLE) {
188 addedge(cresource, pheno->job_start[job->index], duration,
189 crequest->alternatives[
190 crequest->genome_position != -1
191 ? genome->alternatives[crequest->genome_position]
192 : 0
193 ]->amount, state);
194 }
195 else {
196 /* this should never happen */
197 assert(1 == 0);
198 }
199 }
200 return start;
201 }
202
203
decode(struct rcps_solver * solver,struct rcps_problem * problem,struct rcps_genome * genome)204 struct rcps_phenotype *decode(struct rcps_solver *solver,
205 struct rcps_problem *problem, struct rcps_genome *genome) {
206 int i, j;
207 int s;
208 int duration;
209 int cmi;
210 struct rcps_job *cjob;
211 struct rcps_job *pjob;
212 struct rcps_phenotype *pheno;
213 struct decoding_state state;
214 struct edge *cedge, *tedge;
215
216 /* init the state */
217 state.res_load = (int*)malloc(sizeof(int) * problem->resource_count);
218 state.res_edges = (struct edge**)malloc(
219 sizeof(struct edge*) * problem->resource_count);
220 for (i = 0; i < problem->resource_count; i++) {
221 state.res_load[i] = 0;
222 // XXX perhaps do not malloc, but take from list. might be faster and
223 // cache-aligned
224 state.res_edges[i] = (struct edge*)malloc(sizeof(struct edge));
225 state.res_edges[i]->time = 0;
226 state.res_edges[i]->amount = 0;
227 state.res_edges[i]->next = NULL;
228 }
229
230 pheno = (struct rcps_phenotype*)malloc(sizeof(struct rcps_phenotype));
231 pheno->overuse_count = 0;
232 pheno->overuse_amount = 0;
233 pheno->job_start = (int*)malloc(sizeof(int) * problem->job_count);
234 for (i = 0; i < problem->job_count; i++) {
235 pheno->job_start[i] = UNSCHEDULED;
236 }
237 pheno->job_duration = (int*)malloc(sizeof(int) * problem->job_count);
238 for (i = 0; i < problem->job_count; i++) {
239 pheno->job_duration[i] = 0;
240 }
241
242 /* now take every job in turn and schedule it */
243 for (i = 0; i < problem->job_count; i++) {
244 cjob = problem->jobs[genome->schedule[i]];
245 /* find the first possible start time through the predeccessors */
246 s = cjob->earliest_start;
247 for (j = 0; j < cjob->predeccessor_count; j++) {
248 int rel_type = 0;
249 int result = 0;
250 pjob = cjob->predeccessors[j];
251 rel_type = cjob->predeccessor_types[j];
252 // get the start time of the pjob, use genome_position here
253 result = pheno->job_start[pjob->index];
254 assert(result != UNSCHEDULED);
255 if (rel_type == SUCCESSOR_FINISH_START) {
256 cmi = pjob->genome_position != -1
257 ? genome->modes[pjob->genome_position]
258 : 0;
259 duration = pjob->modes[cmi]->duration;
260 if (solver->duration_callback) {
261 duration = solver->duration_callback(
262 DURATION_FORWARD,
263 pheno->job_start[pjob->index],
264 duration, pjob->modes[cmi]->cb_arg);
265 //printf("decode: %s direction=%d, start=%d = duration=%d\n", pjob->name, DURATION_FORWARD, pheno->job_start[pjob->index], duration);
266 }
267 s = kpt_max(s, pheno->job_start[pjob->index] + duration);
268 }
269 else if (rel_type == SUCCESSOR_START_START) {
270 s = kpt_max(s, pheno->job_start[pjob->index]);
271 }
272 else if (rel_type == SUCCESSOR_FINISH_FINISH) {
273 int d2;
274 cmi = pjob->genome_position != -1
275 ? genome->modes[pjob->genome_position]
276 : 0;
277 duration = pjob->modes[cmi]->duration;
278 if (solver->duration_callback) {
279 duration = solver->duration_callback(
280 DURATION_FORWARD,
281 pheno->job_start[pjob->index],
282 duration, pjob->modes[cmi]->cb_arg);
283 }
284 cmi = cjob->genome_position != -1
285 ? genome->modes[cjob->genome_position]
286 : 0;
287 d2 = cjob->modes[cmi]->duration;
288 if (solver->duration_callback) {
289 //printf( "duration callback backward: %s\n", cjob->name );
290 d2 = solver->duration_callback(
291 DURATION_BACKWARD,
292 pheno->job_start[pjob->index] + duration,
293 d2, cjob->modes[cmi]->cb_arg);
294 }
295 s = kpt_max(s, pheno->job_start[pjob->index]
296 + duration
297 - d2);
298 }
299 }
300 /* now we need to postpone it until all requests can be satisfied */
301 postpone(solver, problem, genome, cjob, s, &state, pheno);
302 }
303 // check for overloaded nonrenewable resources
304 for (i = 0; i < problem->resource_count; i++) {
305 if (state.res_load[i] > problem->resources[i]->avail) {
306 pheno->overuse_count++;
307 pheno->overuse_amount += state.res_load[i];
308 }
309 }
310 // free the internal state
311 free(state.res_load);
312 for (i = 0; i < problem->resource_count; i++) {
313 cedge = state.res_edges[i];
314 while (cedge) {
315 tedge = cedge;
316 cedge = cedge->next;
317 free(tedge);
318 }
319 }
320 free(state.res_edges);
321
322 return pheno;
323 }
324
325