1 package Analysis.Scheduling;
3 import java.util.Random;
4 import java.util.Vector;
6 public class CombinationUtil {
7 static CombinationUtil cu;
9 public CombinationUtil() {
12 public static CombinationUtil allocateCombinationUtil() {
14 cu = new CombinationUtil();
19 public static RootsGenerator allocateRootsGenerator(Vector<Vector<ScheduleNode>> snodevecs,
21 return CombinationUtil.allocateCombinationUtil().new RootsGenerator(snodevecs, rootNum);
24 public static CombineGenerator allocateCombineGenerator(Vector<Vector<ScheduleNode>> rootnodes,
25 Vector<Vector<ScheduleNode>> node2combine) {
26 return CombinationUtil.allocateCombinationUtil().new CombineGenerator(rootnodes, node2combine);
29 public static RandomGenerator allocateRandomGenerator(Vector<Vector<ScheduleNode>> snodevecs,
31 return CombinationUtil.allocateCombinationUtil().new RandomGenerator(snodevecs, rootNum);
34 public class RootsGenerator {
35 Vector<Vector<ScheduleNode>> sNodeVecs;
36 Vector<Vector<ScheduleNode>> node2Combine;
37 Vector<Vector<ScheduleNode>> rootNodes;
40 public RootsGenerator(Vector<Vector<ScheduleNode>> snodevecs,
42 this.sNodeVecs = snodevecs;
43 this.rootNum = rootNum;
44 this.node2Combine = null;
45 this.rootNodes = null;
49 this.sNodeVecs = null;
50 this.node2Combine.clear();
51 this.node2Combine = null;
52 this.rootNodes.clear();
53 this.rootNodes = null;
57 public boolean nextGen() {
58 boolean trial = false;
59 if(this.rootNodes == null) {
60 int num2choose = this.rootNum;
61 this.rootNodes = new Vector<Vector<ScheduleNode>>();
62 this.rootNodes.add(new Vector<ScheduleNode>());
63 Vector<ScheduleNode> toadd = this.sNodeVecs.elementAt(0);
64 for(int i = 0; i < toadd.size(); i++) {
65 // should be only one element: startup object
66 this.rootNodes.elementAt(0).add(toadd.elementAt(i));
70 trial = trial(num2choose, next);
73 if(this.rootNodes.size() == 1) {
76 int next = this.rootNodes.lastElement().elementAt(0).getCid() + 1;
78 while(next == this.sNodeVecs.size()) {
80 num2choose = this.rootNodes.lastElement().size();
81 this.rootNodes.removeElementAt(this.rootNodes.size() - 1);
82 if(this.rootNodes.size() == 1) {
83 // only startup object left, no more choices
86 next = this.rootNodes.lastElement().elementAt(0).getCid() + 1;
89 // reduce one from the last one
90 this.rootNodes.lastElement().removeElementAt(this.rootNodes.lastElement().size() - 1);
91 if(this.rootNodes.lastElement().size() == 0) {
92 this.rootNodes.removeElementAt(this.rootNodes.size() - 1);
95 trial = trial(num2choose, next);
98 // remaining nodes are all to be combined
99 this.node2Combine = new Vector<Vector<ScheduleNode>>();
102 for(int i = 1; i < this.rootNodes.size(); i++) {
103 int tmp = this.rootNodes.elementAt(i).elementAt(0).getCid();
105 Vector<ScheduleNode> toadd = this.sNodeVecs.elementAt(next);
107 this.node2Combine.add(new Vector<ScheduleNode>());
108 for(index = 0; index < toadd.size(); index++) {
109 this.node2Combine.lastElement().add(toadd.elementAt(index));
113 this.node2Combine.add(null);
117 Vector<ScheduleNode> toadd = this.sNodeVecs.elementAt(tmp);
118 if(toadd.size() > this.rootNodes.elementAt(i).size()) {
119 this.node2Combine.add(new Vector<ScheduleNode>());
120 for(index = this.rootNodes.elementAt(i).size(); index < toadd.size(); index++) {
121 this.node2Combine.lastElement().add(toadd.elementAt(index));
127 while(next < this.sNodeVecs.size()) {
128 Vector<ScheduleNode> toadd = this.sNodeVecs.elementAt(next);
130 this.node2Combine.add(new Vector<ScheduleNode>());
131 for(index = 0; index < toadd.size(); index++) {
132 this.node2Combine.lastElement().add(toadd.elementAt(index));
136 this.node2Combine.add(null);
144 private boolean trial(int num2choose,
147 boolean first = true;
148 while(num2choose > 0) {
150 if(next == this.sNodeVecs.size()) {
151 // no more nodes available to add
155 if(this.sNodeVecs.elementAt(next) != null) {
157 this.rootNodes.add(new Vector<ScheduleNode>());
160 this.rootNodes.lastElement().add(this.sNodeVecs.elementAt(next).elementAt(index));
163 if(index == this.sNodeVecs.elementAt(next).size()) {
176 public Vector<Vector<ScheduleNode>> getNode2Combine() {
180 public Vector<Vector<ScheduleNode>> getRootNodes() {
185 public class Combine {
186 public ScheduleNode node;
190 public Combine(ScheduleNode n) {
197 public class CombineGenerator {
198 Vector<Vector<ScheduleNode>> rootNodes;
199 Vector<Vector<int[]>> rootNStates;
200 Vector<Vector<ScheduleNode>> node2Combine;
201 Vector<Vector<Combine>> combine;
203 boolean first4choice;
208 public CombineGenerator(Vector<Vector<ScheduleNode>> rootnodes,
209 Vector<Vector<ScheduleNode>> node2combine) {
210 this.rootNodes = rootnodes;
211 this.node2Combine = node2combine;
212 this.rootNStates = new Vector<Vector<int[]>>();
214 for(int i = 0; i < this.rootNodes.size(); i++) {
215 this.rootNStates.add(new Vector<int[]>());
216 for(int j = 0; j < this.rootNodes.elementAt(i).size(); j++) {
217 this.rootNStates.elementAt(i).add(new int[this.node2Combine.size()]);
218 for(int k = 0; k < this.node2Combine.size(); k++) {
219 this.rootNStates.elementAt(i).elementAt(j)[k] = 0;
224 this.combine = new Vector<Vector<Combine>>();
226 for(int i = 0; i < this.node2Combine.size(); i++) {
227 if(this.node2Combine.elementAt(i) == null) {
228 this.combine.add(null);
230 this.combine.add(new Vector<Combine>());
231 for(int j = 0; j < this.node2Combine.elementAt(i).size(); j++) {
232 this.combine.elementAt(i).add(new Combine(this.node2Combine.elementAt(i).elementAt(j)));
237 this.lastchoices = null;
238 this.first4choice = false;
239 this.rand = new Random();
241 this.limit = (tomapnum-1)/rootnum+1;
242 this.rootLoads = null;
245 public void clear() {
246 this.rootNodes = null;
247 this.rootNStates.clear();
248 this.rootNStates = null;
249 this.node2Combine = null;
250 this.combine.clear();
252 this.lastchoices = null;
253 this.first4choice = false;
256 public Vector<Vector<Combine>> getCombine() {
260 // generate next mapping randomly evenly
261 public boolean randomGenE() {
262 this.rootLoads = new int[this.rootNodes.size()][];
263 for(int i = 0; i < this.rootNodes.size(); i++) {
264 this.rootLoads[i] = new int[this.rootNodes.elementAt(i).size()];
266 int rootx = this.rootNodes.size();
267 for(int i = 0; i < this.node2Combine.size(); i++) {
268 for(int j = 0; j < this.node2Combine.elementAt(i).size(); j++) {
269 Combine tmp = this.combine.elementAt(i).elementAt(j);
271 int x = Math.abs(rand.nextInt()) % rootx;
272 int y = Math.abs(rand.nextInt()) % this.rootNodes.elementAt(x).size();
273 if(this.rootLoads[x][y] < this.limit) {
276 this.rootLoads[tmp.root][tmp.index]++;
285 public boolean randomGen() {
286 int rootx = this.rootNodes.size();
287 for(int i = 0; i < this.node2Combine.size(); i++) {
288 for(int j = 0; j < this.node2Combine.elementAt(i).size(); j++) {
289 Combine tmp = this.combine.elementAt(i).elementAt(j);
290 tmp.root = Math.abs(rand.nextInt()) % rootx;
291 tmp.index = Math.abs(rand.nextInt()) % this.rootNodes.elementAt(tmp.root).size();
297 public boolean nextGen() {
298 boolean trial = false;
299 if(this.lastchoices == null) {
301 this.lastchoices = new int[this.node2Combine.size()];
302 for(int i = 0; i < this.lastchoices.length; i++) {
303 this.lastchoices[i] = 0;
305 this.first4choice = true;
310 // no more available combination under this choice
311 // choose another choice
312 int next = this.node2Combine.size() - 1;
313 boolean iter = false;
315 if(this.node2Combine.elementAt(next) != null) {
316 this.lastchoices[next]++;
317 if((this.lastchoices[next] == this.rootNodes.size() ||
318 (this.rootNodes.elementAt(this.lastchoices[next]).elementAt(0).getCid() >
319 this.node2Combine.elementAt(next).elementAt(0).getCid()))) {
320 // break the rule that a node can only be combined to nodes with smaller colorid.
321 // or no more buckets
332 } while(iter && !(next < 0));
336 for(next += 1; next < this.node2Combine.size(); next++) {
337 this.lastchoices[next] = 0;
339 this.first4choice = true;
346 private boolean trial() {
348 if(this.first4choice) {
349 // first time for each choice
350 // put all the objects of one color into the first bucket indicated by the choice
352 suc = firstexpand(next, this.first4choice);
353 this.first4choice = false;
355 int next = this.node2Combine.size() - 1;
357 suc = innertrial(next, layer);
362 private boolean firstexpand(int next,
364 for(int i = next; i < this.node2Combine.size(); i++) {
365 if(this.node2Combine.elementAt(i) != null) {
366 int choice = this.lastchoices[i];
367 for(int j = 0; j < this.node2Combine.elementAt(i).size(); j++) {
368 Combine tmp = this.combine.elementAt(i).elementAt(j);
370 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
375 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
379 this.rootNStates.elementAt(choice).elementAt(0)[i] = this.node2Combine.elementAt(i).size();
380 for(int j = 1; j < this.rootNodes.elementAt(choice).size(); j++) {
381 this.rootNStates.elementAt(choice).elementAt(j)[i] = 0;
389 private boolean innertrial(int next,
391 if((this.combine.elementAt(next) == null) ||
392 (this.combine.elementAt(next).size() < 2)) {
393 // skip over empty buckets and bucket with only one obj ( make sure
394 // at least one obj is existing in the chosen bucket)
398 return innertrial(next - 1, ++layer);
401 Combine tmp = this.combine.elementAt(next).lastElement();
402 // try to move it backward
404 int index = tmp.index;
406 if(index == this.rootNodes.elementAt(root).size()) {
407 // no more place in this color bucket
410 } else if(this.rootNStates.elementAt(root).elementAt(index - 1)[next] <
411 this.rootNStates.elementAt(root).elementAt(index)[next] + 2) {
412 // break the law of non-increase order inside one color bucket
413 // try next bucket of another color
417 if(root == this.rootNodes.size()) {
422 int t = this.combine.elementAt(next).size() - 2;
425 tmp = this.combine.elementAt(next).elementAt(t);
426 if ((tmp.root != root) || (tmp.index != index)) {
432 // try the bucket in node2combine before
436 return innertrial(next - 1, ++layer);
438 } else if(tmp.root != root) {
439 if((tmp.root == this.lastchoices[next]) &&
440 (this.rootNStates.elementAt(this.lastchoices[next]).elementAt(0)[next] == 1)) {
441 // only 1 obj left in the chosen bucket
442 // can not move this one
443 // try the bucket in node2combine before
447 return innertrial(next - 1, ++layer);
450 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
452 int newroot = tmp.root + 1;
455 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
456 // make all left things in this color bucket reset
457 for(t++; t < this.combine.elementAt(next).size(); t++) {
458 tmp = this.combine.elementAt(next).elementAt(t);
459 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
462 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
465 return firstexpand(next+1, this.first4choice);
468 } else if(tmp.index != index) {
469 if(this.rootNStates.elementAt(root).elementAt(tmp.index)[next] ==
470 this.rootNStates.elementAt(root).elementAt(index)[next]) {
471 // break the law of non-increase order inside one color bucket
472 // go on search forward
474 } else if(this.rootNStates.elementAt(root).elementAt(tmp.index)[next] <
475 this.rootNStates.elementAt(root).elementAt(index)[next] + 2) {
476 // break the law of non-increase order inside one color bucket
477 // and now they only differ by 1
478 // propagate this difference to see if it can fix
479 boolean suc = propagateOne(next, root, index, t, tmp);
483 // go on search forward
487 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
488 int tmproot = tmp.root;
489 int tmpindex = tmp.index;
492 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
493 int desroot = tmp.root;
494 int desindex = tmp.index;
495 // make all left things in this color bucket reset
497 boolean first = true;
498 while(t < this.combine.elementAt(next).size()) {
504 for(; (k < this.rootNStates.elementAt(tmproot).elementAt(tmpindex)[next]) && (t < this.combine.elementAt(next).size()); t++) {
505 tmp = this.combine.elementAt(next).elementAt(t);
506 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
508 tmp.index = desindex;
509 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
511 if(k == this.rootNStates.elementAt(tmproot).elementAt(tmpindex)[next]) {
516 return firstexpand(next+1, this.first4choice);
523 if((tmp.root != this.lastchoices[next]) ||
524 (this.rootNStates.elementAt(this.lastchoices[next]).elementAt(0)[next] > 1)) {
525 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
528 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
530 return firstexpand(next+1, this.first4choice);
534 // only 1 obj with the color next exist on the chosen bucket this time,
535 // can not move it, try objs in forward color bucket
539 return innertrial(next - 1, ++layer);
545 private boolean propagateOne(int next,
553 int rootbk = tmp.root;
554 int indexbk = tmp.index;
555 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
558 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
561 if(this.rootNStates.elementAt(root).elementAt(index - 1)[next] <
562 this.rootNStates.elementAt(root).elementAt(index)[next]) {
563 // need to continue propagate
564 while(t < this.combine.elementAt(next).size()) {
565 tmpt = this.combine.elementAt(next).elementAt(t);
566 if ((tmpt.root != root) || (tmpt.index != index)) {
571 if(t == this.combine.elementAt(next).size()) {
572 // last element of this color bucket
573 if(index + 1 < this.rootNodes.elementAt(root).size()) {
574 // there is available place inside the same color bucket
575 Combine tmpbk = this.combine.elementAt(next).elementAt(t - 1);
576 boolean suc = propagateOne(next, root, index + 1, t - 1, tmpbk);
579 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
582 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
585 } else if(root+1 < this.rootNodes.size()) { // check if there are another bucket
587 this.rootNStates.elementAt(tmpt.root).elementAt(tmpt.index)[next]--;
588 tmpt.root = root + 1;
590 this.rootNStates.elementAt(tmpt.root).elementAt(tmpt.index)[next]++;
591 return firstexpand(next+1, this.first4choice);
594 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
597 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
600 } else if(tmpt.root != root) {
601 Combine tmpbk = this.combine.elementAt(next).elementAt(t - 1);
602 this.rootNStates.elementAt(tmpbk.root).elementAt(tmpbk.index)[next]--;
603 tmpbk.root = tmpt.root;
605 this.rootNStates.elementAt(tmpbk.root).elementAt(tmpbk.index)[next]++;
608 // make all left things in this color bucket reset
609 for(t += 1; t < this.combine.elementAt(next).size(); t++) {
610 tmpt = this.combine.elementAt(next).elementAt(t);
611 this.rootNStates.elementAt(tmpt.root).elementAt(tmpt.index)[next]--;
614 this.rootNStates.elementAt(tmpt.root).elementAt(tmpt.index)[next]++;
616 return firstexpand(next+1, this.first4choice);
617 } else if(tmpt.index != index) {
618 Combine tmpbk = this.combine.elementAt(next).elementAt(t - 1);
619 boolean suc = propagateOne(next, root, tmpt.index, t - 1, tmpbk);
622 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]--;
625 this.rootNStates.elementAt(tmp.root).elementAt(tmp.index)[next]++;
629 // won't reach here, only to avoid compiler's complain
637 public class RandomGenerator {
638 Vector<Vector<ScheduleNode>> sNodeVecs;
639 Vector<Vector<ScheduleNode>> mapping;
643 public RandomGenerator(Vector<Vector<ScheduleNode>> snodevecs,
645 this.sNodeVecs = snodevecs;
646 this.rootNum = rootNum;
648 this.mapping = new Vector<Vector<ScheduleNode>>();
649 for(int i = 0; i < this.rootNum; i++) {
650 this.mapping.add(null);
652 this.rand = new Random();
655 public void clear() {
656 this.sNodeVecs = null;
661 public boolean nextGen() {
663 this.mapping = new Vector<Vector<ScheduleNode>>();
664 for(int i = 0; i < this.rootNum; i++) {
665 this.mapping.add(null);
668 // randomly choose a core for each node in sNodeVecs
669 for(int i = 0; i < this.sNodeVecs.size(); i++) {
670 Vector<ScheduleNode> sNodes = this.sNodeVecs.elementAt(i);
671 for(int j = 0; j < sNodes.size(); j++) {
672 ScheduleNode snode = sNodes.elementAt(j);
673 int core = Math.abs(rand.nextInt()) % this.rootNum;
674 if(this.mapping.elementAt(core) == null) {
675 this.mapping.setElementAt(new Vector<ScheduleNode>(), core);
677 this.mapping.elementAt(core).add(snode);
683 public Vector<Vector<ScheduleNode>> getMapping() {