Loading [MathJax]/extensions/tex2jax.js
The Gaudi Framework  v36r16 (ea80daf8)
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Modules Pages
graphanalysis.py
Go to the documentation of this file.
1 
11 from __future__ import print_function
12 
13 from pygraph.algorithms.accessibility import connected_components
14 from pygraph.algorithms.critical import critical_path
15 from pygraph.algorithms.cycles import find_cycle
16 from pygraph.classes.digraph import digraph
17 
18 
19 def read_graph_from_json(filename):
20  data = open(filename).read()
21  workflow = eval(data)
22  gr = digraph()
23  # create all nodes
24  for algo in workflow["algorithms"]:
25  # to differentiate algos from equally named products
26  name = algo["name"] + "_algo"
27  gr.add_nodes([name])
28  for input in algo["inputs"]:
29  if input == "":
30  input = "dummy"
31  if not gr.has_node(input):
32  gr.add_nodes([input])
33  if not gr.has_edge((input, name)):
34  gr.add_edge((input, name), wt=0)
35  for output in algo["outputs"]:
36  if output == "":
37  output = "dummy"
38  if not gr.has_node(output):
39  gr.add_nodes([output])
40  if not gr.has_edge((name, output)):
41  # the output edge gets the weigth corresponding to the runtime
42  gr.add_edge((name, output), wt=algo["runtimes_wall"][0] * 100)
43  return gr
44 
45 
47  has_loop = True
48  n_cycles = 0
49  while has_loop:
50  cycle = find_cycle(gr)
51  if len(cycle) == 0:
52  has_loop = False
53  continue
54  n_cycles += 1
55  print(cycle)
56  print("Removed loop by deleting edge (%s,%s)" % (cycle[-1], cycle[0]))
57  gr.del_edge((cycle[-1], cycle[0]))
58  print("\nIN TOTAL %i CYCLES\n" % (n_cycles))
59  return n_cycles > 0 # whether it needed to fix cycles
60 
61 
63  cc = connected_components(gr)
64  cc_size = {}
65  for i in cc.values():
66  cc_size[i] = 0
67  for k, v in cc.iteritems():
68  cc_size[v] = cc_size[v] + 1
69  print("Connected components have the following size:")
70  # for k,v in cc_size.iteritems():
71  # print "%i : %i" %(k,v)
72  print("NUMBER OF CONNECTED COMPONENTS: %i" % (len(cc_size.keys())))
73 
74 
76  total_time = 0
77  critical_time = 0
78  cp = critical_path(gr)
79  # calculate total time
80  for edge in gr.edges():
81  total_time += gr.edge_weight(edge)
82 
83  # calculate time of critical path
84  edges = [tuple(cp[i : i + 2]) for i in range(0, len(cp))]
85  for edge in edges:
86  critical_time += gr.edge_weight(edge)
87 
88  print("Total time : %s" % total_time)
89  print("Critical path: %s" % critical_time)
90  print("POSSIBLE SPEEDUP: %s" % (total_time / critical_time))
91 
92 
93 def print_graph_to_json(gr, filename):
94  algorithms = {} # still make it known to workflow
95  known_names = set()
96  for edge in gr.edges():
97  if edge[0].endswith("_algo"):
98  algoname = edge[0].rstrip("_algo")
99  product = edge[1]
100  reading = False
101  else:
102  algoname = edge[1].rstrip("_algo")
103  product = edge[0]
104  reading = True
105 
106  if algoname not in known_names:
107  algorithms[algoname] = {
108  "name": algoname,
109  "inputs": [],
110  "outputs": [],
111  "runtimes": [1000], # TODO dummy
112  "runtimes_wall": [1000], # TODO dummy
113  }
114  known_names.add(algoname)
115  if reading:
116  algorithms[algoname]["inputs"].append(product)
117  else:
118  algorithms[algoname]["outputs"].append(product)
119  algorithms[algoname]["runtimes_wall"] = [
120  gr.edge_weight(edge) / 100,
121  ]
122  out = open(filename, "w")
123  algorithm_list = [item for item in algorithms.values()]
124  workflow = {"algorithms": algorithm_list}
125  out.write(workflow.__repr__())
126  out.close()
127 
128 
129 
130 if __name__ == "__main__":
131  filename = "Athena.json"
132  gr = read_graph_from_json(filename)
133 
134  # let's analysis and fix for loops:
135  had_to_fix_cycles = analyze_and_fix_cycles(gr)
136  # write file with fixed graph
137  if had_to_fix_cycles:
138  print_graph_to_json(gr, filename.replace(".json", "_loopfixed.json"))
139 
140  # see how many disconnected components are there
142 
143  # let's check the minimum time required
144  # and print achievable speedup
graphanalysis.analyze_connected_componets
def analyze_connected_componets(gr)
Definition: graphanalysis.py:62
graphanalysis.print_graph_to_json
def print_graph_to_json(gr, filename)
Definition: graphanalysis.py:93
graphanalysis.analyze_critical_path
def analyze_critical_path(gr)
Definition: graphanalysis.py:75
graphanalysis.analyze_and_fix_cycles
def analyze_and_fix_cycles(gr)
Definition: graphanalysis.py:46
hivetimeline.read
def read(f, regex=".*", skipevents=0)
Definition: hivetimeline.py:33
graphanalysis.read_graph_from_json
def read_graph_from_json(filename)
Definition: graphanalysis.py:19
Gaudi::Functional::details::zip::range
decltype(auto) range(Args &&... args)
Zips multiple containers together to form a single range.
Definition: FunctionalDetails.h:102