Statistics
| Branch: | Revision:

grapes / src / Scheduler / sched.c @ 41012841

History | View | Annotate | Download (11.2 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
#include<stdio.h>
12

    
13
#define MAX(A,B)    ((A)>(B) ? (A) : (B))
14
#define MIN(A,B)    ((A)<(B) ? (A) : (B))
15

    
16
struct iw {
17
  int index;
18
  double weight;
19
};
20

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

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

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

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

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

    
56
  *bests_len = MIN(*bests_len, nmemb);
57

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

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

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

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

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

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

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

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

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

    
150

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

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

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

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

    
214
  size_t filtered_len=peers_len;
215
  schedPeerID filtered[filtered_len];
216

    
217
  filterPeers2(peers, peers_len, chunks,chunks_len, filtered, &filtered_len, filter);
218
        //fprintf(stderr,"[DEBUG] Filtered peers for offer: %d\n",filtered_len);
219

    
220
  selectPeers(ordering, filtered, filtered_len, evaluate, selected, selected_len);
221
}
222

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

    
228
  size_t filtered_len=chunks_len;
229
  schedChunkID filtered[filtered_len];
230

    
231
  filterChunks2(peers, peers_len, chunks,chunks_len, filtered, &filtered_len, filter);
232

    
233
  selectChunks(ordering, filtered, filtered_len, evaluate, selected, selected_len);
234
}
235

    
236

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

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

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

    
271
/*----------------- scheduler_la implementations --------------*/
272

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

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

    
285
  toPairsPeerFirst(p,p_len,c,c_len,selected,selected_len);
286
}
287

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

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

    
300
  toPairsChunkFirst(p,p_len,c,c_len,selected,selected_len);
301
}
302

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

    
315

    
316
peerEvaluateFunction peer_ev;
317
chunkEvaluateFunction chunk_ev;
318
double2op peerchunk_wc;
319

    
320
double combinedWeight(struct PeerChunk* pc){
321
  return peerchunk_wc(peer_ev(&pc->peer),chunk_ev(&pc->chunk));
322
}
323

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

    
338
}