Statistics
| Branch: | Revision:

grapes / src / Scheduler / sched.c @ 2c07cb9d

History | View | Annotate | Download (11.1 KB)

1
/*
2
 *  Copyright (c) 2010 Csaba Kiraly
3
 *
4
 *  This is free software; see lgpl-2.1.txt
5
 */
6

    
7
#include <string.h>
8
#include <stdlib.h>
9
#include "scheduler_la.h"
10

    
11
#define MAX(A,B)    ((A)>(B) ? (A) : (B))
12
#define MIN(A,B)    ((A)<(B) ? (A) : (B))
13

    
14
struct iw {
15
  int index;
16
  double weight;
17
};
18

    
19
static int cmp_iw_reverse(const void *a, const void *b)
20
{
21
  const struct iw *a1 = (const struct iw *) a;
22
  const struct iw *b1 = (const struct iw *) b;
23
  return a1->weight==b1->weight ? 0 : (a1->weight<b1->weight ? 1 : -1);
24
}
25

    
26
/**
27
  * Select best N of K based using a given evaluator function
28
  */
29
void selectBests(size_t size,unsigned char *base, size_t nmemb, double(*evaluate)(void *),unsigned char *bests,size_t *bests_len){
30
  struct iw iws[nmemb];
31
  int i;
32

    
33
  // calculate weights
34
  for (i=0; i<nmemb; i++){
35
     iws[i].index = i;
36
     iws[i].weight = evaluate(base + size*i);
37
  }
38

    
39
  // sort in descending order
40
  qsort(iws, nmemb, sizeof(struct iw), cmp_iw_reverse);
41

    
42
  // ensure uniform random tie
43
  for (i=0; i<nmemb; i++){
44
    int j, k;
45
    for (j=i; j<nmemb && iws[i].weight == iws[j].weight; j++);
46
    for (k=i; k<j; k++){
47
      struct iw iwt = iws[k];
48
      int r = i + (rand() % (j-i));
49
      iws[k] = iws[r];
50
      iws[r] = iwt;
51
    }
52
  }
53

    
54
  *bests_len = MIN(*bests_len, nmemb);
55

    
56
  // copy bests in their place
57
  for (i=0; i<*bests_len; i++){
58
     memcpy(bests + size*i, base + size*iws[i].index, size);
59
  }
60
  
61
}
62

    
63
/**
64
  * Select N of K with weigthed random choice, without replacement (multiple selection), based on a given evaluator function
65
  */
66
void selectWeighted(size_t size,unsigned char *base, size_t nmemb, double(*weight)(void *),unsigned char *selected,size_t *selected_len){
67
  int i,j,k;
68
  double weights[nmemb];
69
  double w_sum=0;
70
  double selected_index[nmemb];
71
  int s=0;
72
  int s_max = MIN (*selected_len, nmemb);
73
  int zeros = 0;
74

    
75
  // calculate weights
76
  for (i=0; i<nmemb; i++){
77
     weights[i] = weight(base + size*i);
78
     // weights should not be negative
79
     weights[i] = MAX (weights[i], 0);
80
     if (weights[i] == 0) zeros += 1;
81
     w_sum += weights[i];
82
  }
83

    
84
  // all weights shuold not be zero, but if if happens, do something
85
  if (w_sum == 0) {
86
    for (i=0; i<nmemb; i++){
87
      weights[i] = 1;
88
      w_sum += weights[i];
89
    }
90
  } else { //exclude 0 weight from selection
91
    s_max = MIN (s_max, nmemb - zeros);
92
  }
93

    
94
  while (s < s_max) {
95
    // select one randomly
96
    double t = w_sum * (rand() / (RAND_MAX + 1.0));
97
    //search for it in the CDF
98
    double cdf = 0;
99
    for (j=0; j<nmemb; j++){
100
      cdf += weights[j];
101
      //printf("(%f <? %f\n",t,cdf);
102
      if (t < cdf) {
103
        int already_selected=0;
104
        for (k=0; k<s; k++) {
105
          if (selected_index[k] == j)  already_selected=1;
106
        }
107
        if (!already_selected){ 
108
          //printf("selected %d(%f) for %d\n",j,weights[j],k);
109
          memcpy(selected + size*s, base + size*j, size);
110
          selected_index[s++]=j;
111
        }
112
        break;
113
      }
114
    }
115
  }
116
  *selected_len=s;
117
}
118

    
119
/**
120
  * Select best N of K with the given ordering method
121
  */
122
void selectWithOrdering(SchedOrdering ordering, size_t size, unsigned char *base, size_t nmemb, double(*evaluate)(void *), unsigned char *selected,size_t *selected_len){
123
  if (ordering == SCHED_WEIGHTED) selectWeighted(size, base, nmemb, evaluate, selected, selected_len);
124
  else selectBests(size, base, nmemb, evaluate, selected, selected_len);
125
}
126

    
127
/**
128
  * Select best N of K peers with the given ordering method
129
  */
130
void selectPeers(SchedOrdering ordering, schedPeerID *peers, size_t peers_len, peerEvaluateFunction peerevaluate, schedPeerID *selected, size_t *selected_len ){
131
  selectWithOrdering(ordering, sizeof(peers[0]), (void*)peers, peers_len, (evaluateFunction)peerevaluate, (void*)selected, selected_len);
132
}
133

    
134
/**
135
  * Select best N of K chunks with the given ordering method
136
  */
137
void selectChunks(SchedOrdering ordering, schedChunkID *chunks, size_t chunks_len, chunkEvaluateFunction chunkevaluate, schedChunkID *selected, size_t *selected_len ){
138
  selectWithOrdering(ordering, sizeof(chunks[0]), (void*)chunks,chunks_len, (evaluateFunction)chunkevaluate, (void*)selected, selected_len);
139
}
140

    
141
/**
142
  * Select best N of K peer-chunk pairs with the given ordering method
143
  */
144
void selectPairs(SchedOrdering ordering, struct PeerChunk *pairs, size_t pairs_len, pairEvaluateFunction evaluate, struct PeerChunk *selected, size_t *selected_len ){
145
  selectWithOrdering(ordering, sizeof(pairs[0]), (void*)pairs, pairs_len, (evaluateFunction)evaluate, (void*)selected, selected_len);
146
}
147

    
148

    
149
/**
150
  * Filter a list of peers. Include a peer if the filter function is true with at least one of the given chunks
151
  */
152
void filterPeers2(schedPeerID *peers, size_t peers_len, schedChunkID *chunks, size_t chunks_len,
153
                     schedPeerID *filteredpeers, size_t *filtered_len,        //out, inout
154
                     filterFunction filter){
155
  int p,c;
156
  int f=0;
157
  for (p=0; p<peers_len; p++){
158
    for (c=0; c<chunks_len; c++){
159
      if (!filter || filter(peers[p],chunks[c])) {
160
        filteredpeers[f++]=peers[p];
161
        break;
162
      }
163
    }
164
    if (*filtered_len==f) break;
165
  }
166
  *filtered_len=f;
167
}
168

    
169
/**
170
  * Filter a list of chunks. Include a chunk if the filter function is true with at least one of the given peers
171
  */
172
void filterChunks2(schedPeerID *peers, size_t peers_len, schedChunkID *chunks, size_t chunks_len,
173
                     schedChunkID *filtered, size_t *filtered_len,        //out, inout
174
                     filterFunction filter){
175
  int p,c;
176
  int f=0;
177
  for (c=0; c<chunks_len; c++){
178
    for (p=0; p<peers_len; p++){
179
      if (!filter || filter(peers[p],chunks[c])) {
180
        filtered[f++]=chunks[c];
181
        break;
182
      }
183
    }
184
    if (*filtered_len==f) break;
185
  }
186
  *filtered_len=f;
187
}
188

    
189
/**
190
  * Filter a list of peer-chunk pairs (in place)
191
  */
192
void filterPairs(struct PeerChunk *pairs, size_t *pairs_len,
193
                     filterFunction filter){
194
  int pc;
195
  int f=0;
196
  for (pc=0; pc<(*pairs_len); pc++){
197
    if (!filter || filter(pairs[pc].peer,pairs[pc].chunk)) {
198
      pairs[f++]=pairs[pc];
199
    }
200
  }
201
  *pairs_len=f;
202
}
203

    
204
/**
205
  * Select at most N of K peers, among those where filter is true with at least one of the chunks.
206
  */
207
void selectPeersForChunks(SchedOrdering ordering, schedPeerID *peers, size_t peers_len, schedChunkID *chunks, size_t chunks_len,         //in
208
                     schedPeerID *selected, size_t *selected_len,        //out, inout
209
                     filterFunction filter,
210
                     peerEvaluateFunction evaluate){
211

    
212
  size_t filtered_len=peers_len;
213
  schedPeerID filtered[filtered_len];
214

    
215
  filterPeers2(peers, peers_len, chunks,chunks_len, filtered, &filtered_len, filter);
216

    
217
  selectPeers(ordering, filtered, filtered_len, evaluate, selected, selected_len);
218
}
219

    
220
void selectChunksForPeers(SchedOrdering ordering, schedPeerID *peers, size_t peers_len, schedChunkID *chunks, size_t chunks_len,         //in
221
                     schedChunkID *selected, size_t *selected_len,        //out, inout
222
                     filterFunction filter,
223
                     chunkEvaluateFunction evaluate){
224

    
225
  size_t filtered_len=chunks_len;
226
  schedChunkID filtered[filtered_len];
227

    
228
  filterChunks2(peers, peers_len, chunks,chunks_len, filtered, &filtered_len, filter);
229

    
230
  selectChunks(ordering, filtered, filtered_len, evaluate, selected, selected_len);
231
}
232

    
233

    
234
void toPairsPeerFirst(schedPeerID *peers, size_t peers_len, schedChunkID *chunks, size_t chunks_len,         //in
235
                     struct PeerChunk *pairs, size_t *pairs_len) {        //out, inout
236
  size_t p,c;
237
  size_t i=0;
238
  for (p=0; p<peers_len; p++){
239
    for (c=0; c<chunks_len; c++){
240
      pairs[i  ].peer  = peers[p];
241
      pairs[i++].chunk = chunks[c];
242
    }
243
    if (*pairs_len==i) break;
244
  }
245
  *pairs_len=i;
246
}
247

    
248
void toPairsChunkFirst(schedPeerID *peers, size_t peers_len, schedChunkID *chunks, size_t chunks_len,         //in
249
                     struct PeerChunk *pairs, size_t *pairs_len) {        //out, inout
250
  size_t p,c;
251
  size_t i=0;
252
  for (c=0; c<chunks_len; c++){
253
    for (p=0; p<peers_len; p++){
254
      pairs[i  ].peer  = peers[p];
255
      pairs[i++].chunk = chunks[c];
256
    }
257
    if (*pairs_len==i) break;
258
  }
259
  *pairs_len=i;
260
}
261

    
262
void toPairs(schedPeerID *peers, size_t peers_len, schedChunkID *chunks, size_t chunks_len,         //in
263
                     struct PeerChunk *pairs, size_t *pairs_len)        //out, inout
264
{
265
  toPairsChunkFirst(peers, peers_len, chunks, chunks_len, pairs, pairs_len);
266
}
267

    
268
/*----------------- scheduler_la implementations --------------*/
269

    
270
void schedSelectPeerFirst(SchedOrdering ordering, schedPeerID *peers, size_t peers_len, schedChunkID *chunks, size_t chunks_len,         //in
271
                     struct PeerChunk *selected, size_t *selected_len,        //out, inout
272
                     filterFunction filter,
273
                     peerEvaluateFunction peerevaluate, chunkEvaluateFunction chunkevaluate){
274

    
275
  size_t p_len=1;
276
  schedPeerID p[p_len];
277
  size_t c_len=*selected_len;
278
  schedChunkID c[c_len];
279
  selectPeersForChunks(ordering, peers, peers_len, chunks, chunks_len, p, &p_len, filter, peerevaluate);
280
  selectChunksForPeers(ordering, p, p_len, chunks, chunks_len, c, &c_len, filter, chunkevaluate);
281

    
282
  toPairsPeerFirst(p,p_len,c,c_len,selected,selected_len);
283
}
284

    
285
void schedSelectChunkFirst(SchedOrdering ordering, schedPeerID *peers, size_t peers_len, schedChunkID *chunks, size_t chunks_len,         //in
286
                     struct PeerChunk *selected, size_t *selected_len,        //out, inout
287
                     filterFunction filter,
288
                     peerEvaluateFunction peerevaluate, chunkEvaluateFunction chunkevaluate){
289

    
290
  size_t p_len=*selected_len;
291
  schedPeerID p[p_len];
292
  size_t c_len=1;
293
  schedChunkID c[c_len];
294
  selectChunksForPeers(ordering, peers, peers_len, chunks, chunks_len, c, &c_len, filter, chunkevaluate);
295
  selectPeersForChunks(ordering, peers, peers_len, c, c_len, p, &p_len, filter, peerevaluate);
296

    
297
  toPairsChunkFirst(p,p_len,c,c_len,selected,selected_len);
298
}
299

    
300
void schedSelectHybrid(SchedOrdering ordering, schedPeerID *peers, size_t peers_len, schedChunkID *chunks, size_t chunks_len,         //in
301
                     struct PeerChunk *selected, size_t *selected_len,        //out, inout
302
                     filterFunction filter,
303
                     pairEvaluateFunction pairevaluate)
304
{
305
  size_t pairs_len=peers_len*chunks_len;
306
  struct PeerChunk pairs[pairs_len];
307
  toPairs(peers,peers_len,chunks,chunks_len,pairs,&pairs_len);
308
  filterPairs(pairs,&pairs_len,filter);
309
  selectPairs(ordering,pairs,pairs_len,pairevaluate,selected,selected_len);
310
}
311

    
312

    
313
peerEvaluateFunction peer_ev;
314
chunkEvaluateFunction chunk_ev;
315
double2op peerchunk_wc;
316

    
317
double combinedWeight(struct PeerChunk* pc){
318
  return peerchunk_wc(peer_ev(&pc->peer),chunk_ev(&pc->chunk));
319
}
320

    
321
/**
322
  * Convenience function for combining peer and chunk weights
323
  * not thread safe!
324
  */
325
void schedSelectComposed(SchedOrdering ordering, schedPeerID *peers, size_t peers_len, schedChunkID *chunks, size_t chunks_len,         //in
326
                     struct PeerChunk *selected, size_t *selected_len,        //out, inout
327
                     filterFunction filter,
328
                     peerEvaluateFunction peerevaluate, chunkEvaluateFunction chunkevaluate, double2op weightcombine)
329
{
330
  peer_ev=peerevaluate;
331
  chunk_ev=chunkevaluate;
332
  peerchunk_wc=weightcombine;
333
  schedSelectHybrid(ordering,peers,peers_len,chunks,chunks_len,selected,selected_len,filter,combinedWeight);
334

    
335
}