Class: Pwrake::GraphGroup

Inherits:
Object
  • Object
show all
Defined in:
lib/pwrake/misc/mcgp.rb

Instance Method Summary collapse

Constructor Details

#initialize(loc_list, weight_list, vertex_depth, grviz) ⇒ GraphGroup

Returns a new instance of GraphGroup.



176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
 
# File 'lib/pwrake/misc/mcgp.rb', line 176

def initialize(loc_list, weight_list, vertex_depth, grviz)
  if loc_list.size != weight_list.size
    raise ArgumentError, "array size mismatch"
  end
  @n_part = loc_list.size
  a = [loc_list, weight_list].transpose
  a.sort_by!{|x| x[1]}
  b = a.transpose
  @loc_list = b[0]
  @tpwgts = normalize(b[1])

  b = @tpwgts[0]
  a = @tpwgts[-1]-b
  if a/b > 1e-3
    @host_wgts = @tpwgts.map{|x| (((x-b)/a*0.45+1)*1000).to_i}
  else
    @host_wgts = @tpwgts.map{|x| 1000}
  end

  @vertex_name2id = {}
  @vertex_id2name = []
  @edges = []
  @file_sizes = []
  @loc_files = {}
  @count = 0

  @vertex_depth = vertex_depth
  @grviz = grviz

  @loc_list.each do |loc|
    push_vertex(loc)
    @vertex_depth[loc] = 0
  end
end

Instance Method Details

#average(a) ⇒ Object 



171
172
173
174
 
# File 'lib/pwrake/misc/mcgp.rb', line 171

def average(a)
  s = summation(a).to_f
  (a.empty?) ? nil : s/a.size
end

#count_partition ⇒ Object 



370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
 
# File 'lib/pwrake/misc/mcgp.rb', line 370

def count_partition
  locs = Array.new(@n_part,nil)
  @n_part.times do |i|
    i_part = @part[i]
    locs[i_part] ||= []
    locs[i_part] << @vertex_id2name[i]
  end
  # p locs
  sum = []
  @vertex_id2name.each_with_index do |name,idx|
    y = @vertex_depth[name]
    x = @part[idx]
    sum[y] ||= Array.new(@n_part,0)
    sum[y][x] += 1
  end
  s = "partition count: \n"
  s += sum.each_with_index.map do |row,idx|
    " d=#{idx} "+row.inspect
  end.join("\n")
  #puts s
  Log.info s
  Log.info "@part[0:#{@n_part-1}]=#{@part[0...@n_part].inspect}"
  sum[0].each{|i| raise RuntimeError,"Unequal partitioning" if i!=1}
end

#count_partition2(part) ⇒ Object 



396
397
398
399
400
401
402
403
404
405
406
407
 
# File 'lib/pwrake/misc/mcgp.rb', line 396

def count_partition2(part)
  sum = Array.new(0,0)
  part.each do |x|
    sum[x] ||= 0
    sum[x] += 1
  end
  s = sum.each_with_index.map do |x,i|
    "#{i}:#{x}"
  end
  puts "n_nodes=[ "+s.join(", ")+" ]"
  puts "@part[0:#{@n_part-1}]=#{part[0...@n_part].inspect}"
end

#make_loc_list ⇒ Object 



409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
 
# File 'lib/pwrake/misc/mcgp.rb', line 409

def make_loc_list
  rest = []
  loc_list = []
  @n_part.times do |i|
    i_part = @part[i]
    loc = @loc_list[i]
    if loc_list[i_part]
      rest << loc
    else
      loc_list[i_part] = loc
    end
  end
  @n_part.times do |i|
    unless loc_list[i]
      loc_list[i] = rest.pop
    end
  end
  loc_list
end

#normalize(a) ⇒ Object 



166
167
168
169
 
# File 'lib/pwrake/misc/mcgp.rb', line 166

def normalize(a)
  s = summation(a).to_f
  (s==0) ? a : a.map{|x| x/s}
end

#part_graph ⇒ Object 



244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
 
# File 'lib/pwrake/misc/mcgp.rb', line 244

def part_graph
  @xadj = [0]
  @adjcny = []
  @adjwgt = []
  @vwgt = []

  depth_hist = []
  @vertex_id2name.each do |name|
    depth = @vertex_depth[name]
    # puts "name=#{name}, depth=#{depth}"
    depth_hist[depth] = (depth_hist[depth] || 0) + 1
  end

  map_depth = []
  ubv = []
  c = 0
  depth_hist.each do |x|
    if x and x>=@n_part
      map_depth << c
      c += 1
      ubv << 1 + 0.5*@n_part/x
      #ubv << ((x >= @n_part) ? 1.05 : 1.5)
    else
      map_depth << nil
    end
  end
  ubv[0] = 1.0005

  Pwrake::Log.info "loc_list=#{@loc_list}"
  Pwrake::Log.info "partition_weights=#{@tpwgts}"
  Pwrake::Log.info "ncon=#{c}"
  Pwrake::Log.info "depth_hist=#{depth_hist.inspect}"
  Pwrake::Log.info "ubvec=#{ubv.inspect}"

  if @file_sizes.empty?
    @edge_weight = 1
  else
    @edge_weight = average(@file_sizes).to_i*3
  end
  Pwrake::Log.info "default_edge_weight=#{@edge_weight}"

  @vertex_id2name.size.times do |i|
    if edg = @edges[i]
      edg.sort_by!{|x| x[0]}
      @adjcny.concat(edg.map{|x| x[0]})
      @adjwgt.concat(edg.map{|x| x[1] || @edge_weight})
      # @adjwgt.concat(edg.map{|x| x[1] ? 0 : @edge_weight})
    end
    @xadj.push(@adjcny.size)
  end

  @vertex_id2name.each_with_index do |name,i|
    w = Array.new(c,0)
    if i < @n_part
      w[0] = @host_wgts[i]
      # puts "name=#{name}, w=#{w.inspect}"
    else
      depth = @vertex_depth[name]
      if depth and (j = map_depth[depth])
        w[j] = 1
      end
    end
    @vwgt.concat(w)
  end

  #  puts "@vertex_id2name[#{i}]=#{@vertex_id2name[i]}, depth=#{depth}, edges="+@edges[i].map{|x| @vertex_id2name[x[0]]}.join("|")

  t1 = Time.now
  if false
    puts "@vertex_id2name.size=#{@vertex_id2name.size}"
    if $debug2
      @vertex_id2name.each_with_index{|x,i|
        puts "#{i} #{x} #{@edges[i].inspect}"
      }
    end
    puts "@edges.size=#{@edges.size}"
    puts "ncon=#{c}"
    puts "@n_part=#{@n_part}"
    puts "@xadj.size=#{@xadj.size}"
    puts "@adjcny.size/2=#{@adjcny.size/2}"
    puts "@adjwgt.size/2=#{@adjwgt.size/2}"
    puts "@vwgt.size=#{@vwgt.size}"
    puts "@vwgt.size/ncon=#{@vwgt.size/c}"
    puts "depth_hist=#{depth_hist.inspect}"
    puts "ubv=#{ubv.inspect}"
    if $debug
      puts "@xadj=#{@xadj.inspect}"
      puts "@adjcny=#{@adjcny.inspect}"
      puts "@adjwgt=#{@adjwgt.inspect}"
      puts "@vwgt=#{@vwgt.inspect}"
    end
    #exit
  end
  if defined? RbMetis
    hw = normalize(@host_wgts)
    tpw = []
    s = "tpwgts=[\n"
    @tpwgts.each_with_index do |x,i|
      a = [hw[i]]+[x]*(c-1)
      tpw.concat(a)
      s += " ["+a.map{|x|"%.5f"%x}.join(", ")+"]\n"
    end
    s += "]"
    Log.info s
    options = RbMetis.default_options
    options[RbMetis::OPTION_NCUTS] = 30
    options[RbMetis::OPTION_NSEPS] = 30
    options[RbMetis::OPTION_NITER] = 10
    @part = RbMetis.part_graph_recursive(
              @xadj, @adjcny, @n_part,
              ncon:c, vwgt:@vwgt, adjwgt:@adjwgt,
              tpwgts:tpw, ubvec:ubv, options:options)
  else
    puts "tpw=#{tpw.inspect}"
    @part = Metis.mc_part_graph_recursive2(
              c,@xadj,@adjcny,@vwgt,nil,@tpwgts)
  end
  t2 = Time.now
  Pwrake::Log.info "Time for Graph Partitioning: #{t2-t1} sec"
  count_partition
  if $debug
    puts "Time for Graph Partitioning: #{t2-t1} sec"
    p @part
  end
end

#push_edge(name, target, weight) ⇒ Object 



232
233
234
235
236
237
238
239
240
241
242
 
# File 'lib/pwrake/misc/mcgp.rb', line 232

def push_edge(name, target, weight)
  if target and (weight.nil? or weight>0)
    push_vertex(name)
    push_vertex(target)
    v1 = @vertex_name2id[name]
    v2 = @vertex_name2id[target]
    (@edges[v1] ||= []).push [v2, weight]
    (@edges[v2] ||= []).push [v1, weight]
    @grviz.push_edge(name, target) if @grviz
  end
end

#push_loc_edge(locs, name, target, fsz) ⇒ Object 



211
212
213
214
215
216
217
218
219
220
221
 
# File 'lib/pwrake/misc/mcgp.rb', line 211

def push_loc_edge(locs, name, target, fsz)
  locs.each do |loc|
    if @loc_list.include?(loc)
      push_edge(loc, target, fsz)
      @loc_files[loc] ||= []
      @loc_files[loc] << name
    end
  end
  @file_sizes << fsz
  #p [object_id,target,fsz]
end

#push_vertex(name) ⇒ Object 



223
224
225
226
227
228
229
230
 
# File 'lib/pwrake/misc/mcgp.rb', line 223

def push_vertex(name)
  if !@vertex_name2id.has_key?(name)
    @vertex_name2id[name] = @count
    @vertex_id2name[@count] = name
    @grviz.push_vertex(name) if @grviz
    @count += 1
  end
end

#set_group ⇒ Object 



430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
 
# File 'lib/pwrake/misc/mcgp.rb', line 430

def set_group
  loc_list = make_loc_list()
  @vertex_id2name.each_with_index do |name,idx|
    if idx >= @n_part
      i_part = @part[idx]
      tw = Rake.application[name].wrapper
      tw.group_id = loc_list[i_part]
      #puts "task=#{task.inspect}, i_part=#{i_part}, host=#{host}"
    end
  end
  @loc_files.each do |gid,files|
    files.each do |f|
      tw = Rake.application[f].wrapper
      tw.group_id = gid
      # puts "gid=#{gid}, task=#{f}"
    end
  end
end

#set_node ⇒ Object 



450
451
452
453
454
455
456
457
458
459
460
461
 
# File 'lib/pwrake/misc/mcgp.rb', line 450

def set_node
  loc_list = make_loc_list()
  @vertex_id2name.each_with_index do |name,idx|
    if idx >= @n_part
      i_part = @part[idx]
      tw = Rake.application[name].wrapper
      host = loc_list[i_part]
      tw.suggest_location = [host]
      #puts "task=#{task.inspect}, i_part=#{i_part}, host=#{host}"
    end
  end
end

#summation(a) ⇒ Object 



160
161
162
163
164
 
# File 'lib/pwrake/misc/mcgp.rb', line 160

def summation(a)
  s = 0
  a.each{|x| s+=x}
  s
end