| The Gaudi Framework v28r2-patches (bc4ad17a)

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

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