class Pwrake::GraphGroup
Public Class Methods
new(loc_list, weight_list, vertex_depth, grviz)
click to toggle source
# 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
Public Instance Methods
average(a)
click to toggle source
# 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()
click to toggle source
# 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)
click to toggle source
# 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()
click to toggle source
# 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)
click to toggle source
# 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()
click to toggle source
# 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 = Pwrake.clock 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 = Pwrake.clock 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)
click to toggle source
# 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)
click to toggle source
# 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)
click to toggle source
# 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()
click to toggle source
# 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()
click to toggle source
# 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)
click to toggle source
# File lib/pwrake/misc/mcgp.rb, line 160 def summation(a) s = 0 a.each{|x| s+=x} s end