Module: CompTree::Algorithm

Defined in:
lib/comp_tree/algorithm.rb

Class Method Summary collapse

Class Method Details

.compute_parallel(root, max_threads) ⇒ Object 



6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
# File 'lib/comp_tree/algorithm.rb', line 6

def compute_parallel(root, max_threads)
  workers = []
  from_workers = Queue.new
  to_workers = Queue.new

  node = master_loop(root, max_threads, workers, from_workers, to_workers)

  workers.size.times { to_workers.push(nil) }
  workers.each { |t| t.join }
  
  if node.computed.is_a? Exception
    raise node.computed
  end
  node.result
end

.find_node(node) ⇒ Object 



60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
 
# File 'lib/comp_tree/algorithm.rb', line 60

def find_node(node)
  if node.computed
    #
    # already computed
    #
    nil
  elsif node.free? and node.children_results
    #
    # Node is not computed, not locked, and its children are
    # computed; ready to compute.
    #
    node
  else
    #
    # locked or children not computed; recurse to children
    #
    node.children.each { |child|
      found = find_node(child) and return found
    }
    nil
  end
end

.master_loop(root, max_threads, workers, from_workers, to_workers) ⇒ Object 



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
 
# File 'lib/comp_tree/algorithm.rb', line 31

def master_loop(root, max_threads, workers, from_workers, to_workers)
  num_working = 0
  node = nil
  while true
    if num_working == max_threads or !(node = find_node(root))
      #
      # maxed out or no nodes available -- wait for results
      #
      node = from_workers.pop
      node.unlock
      num_working -= 1
      if node == root or node.computed.is_a? Exception
        return node
      end
    else
      #
      # not maxed out and found a node -- compute it
      #
      if (!max_threads.nil? and workers.size < max_threads) or
          (max_threads.nil? and num_working == workers.size)
        workers << new_worker(from_workers, to_workers)
      end
      num_working += 1
      node.lock
      to_workers.push(node)
    end
  end
end

.new_worker(from_workers, to_workers) ⇒ Object 



22
23
24
25
26
27
28
29
 
# File 'lib/comp_tree/algorithm.rb', line 22

def new_worker(from_workers, to_workers)
  Thread.new {
    while node = to_workers.pop
      node.compute
      from_workers.push(node)
    end
  }
end