toy-assign.co 3.25 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
/*
 * Toy version of assign, written in Comet
 * Robert Ricci <ricci@cs.utah.edu>
 * EMULAB-COPYRIGHT
 * Copyright (c) 2005 University of Utah and the Flux Group.
 * All rights reserved.
 */

string rcsid = "$Id: toy-assign.co,v 1.1 2005-12-17 00:46:45 ricci Exp $";

/*
 * Include some routines for a local solver
 */
include "LocalSolver";

/*
 * Declare the local solver
 */
LocalSolver m();

/*
 * Virtual nodes
 */
int n_vnodes = 100;
range VSize = 1..n_vnodes;
UniformDistribution vdistr(VSize);

/*
 * Physical nodes
 */
int n_pnodes = 100;
range PSize = 1..n_pnodes;
UniformDistribution pdistr(PSize);
range MaxSlots = 1..100;

/*
 * Mapping of virtual to physical
 */
var{int}[] mapping = new var{int}[VSize];
forall (i in VSize) {
    mapping[i] = new var{int}(m,PSize);
    // Start them on random pnodes
    mapping[i] := pdistr.get();
}

/*
 * Constraints
 */
ConstraintSystem S(m);

/*
 * All virtual nodes must be mapped to different physical nodes
 * Now done with slot counts - see below
 */
//S.post(alldifferent(mapping));

/*
 * Put a constraint on how many vnodes can be on each pnode
 */
int slots[PSize];
forall (k in PSize) {
    // For now, every pnode gets one slot
    slots[k] = 1;
}
/*
 * This line says:
 *   for every index i in the slots array:
 *     i must appear as a value in mapping no more than slots[i] timex
 *
 */
S.post(atmost(slots,mapping));

/*
 * Maintain a list of how many slots are used in each pnode. This will get
 * automatically updated for us by Comet
 */
var{int} pnodeSlotsUsed[node in PSize](m)
    <- sum(k in VSize) (mapping[k] == node);

/*
 * Maintain a set of empty pnodes.
 * Again, maintained incrementally by Comet
 */
var{set{int}} emptyPnodes(m) <- setof(k in PSize) (pnodeSlotsUsed[k] == 0);

/*
 * Let's get a set of nodes with remaining capacity too
 */
var{set{int}} pnodesWithSpace(m)
    <- setof(k in PSize) (pnodeSlotsUsed[k] < slots[k]);

/*
 * A simple objective function - minimize the number of pnodes used
 */
/*
Objective O = new MaxNbDistinct(slots, mapping);
*/

/*
 * This says we're done adding constraints to the solver
 */
m.close();

cout << "Starting" << endl;
int it = 0;
int max_it = 50 * n_vnodes;
/*
 * Termination condidtions
 */
while (S.violations() > 0
        &&
        it < max_it ) {
    /*
     * The actual search
     */
    /*
     * queens-style search
    selectMax(q in VSize)(S.getViolations(mapping[q])) 
        selectMin(v in VSize)(S.getAssignDelta(mapping[q],v)) 
        mapping[q] := v;      
        */
    /*
     * Purely random search
    select(vnode in VSize)
        select(pnode in mapping[vnode].getDomain())
            mapping[vnode] := pnode;
     */

    /*
     * Slightly smarter search
     */
    // Pick the most violated virtual node
    selectMax(vnode in VSize)(S.violations(mapping[vnode])) {
        // Put it on the first pnode with remaining capacity we find
        selectFirst(pnode in pnodesWithSpace) {
            mapping[vnode] := pnode;
        }
    }
    //cout << "On iteration " << it << endl;
    it++;
}

forall(i in VSize) {
    cout << "mapping[" << i << "] = " << mapping[i] << endl;
}

cout << "Done after " << it << " iterations" << endl;
cout << "Number of violations is " << S.violations() << endl;
// cout << "Objective functions returns " << O.evaluation() << endl;