1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2% Copyright (c) 2009, 2011, ETH Zurich.
3% All rights reserved.
4%
5% This file is distributed under the terms in the attached LICENSE file.
6% If you do not find this file, copies can be found by writing to:
7% ETH Zurich D-INFK, Haldeneggsteig 4, CH-8092 Zurich. Attn: Systems Group.
8%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
9
10% this file is used for the ASPLOS11 paper to compute the padding overhead for
11% different algorithms. the script "mach" loads the algorihtm and this file into
12% eclipse_language-clp and outputs these values.
13
14
15compute_required_resources(Plans, ResList, Name) :-
16    ( foreach(Plan, Plans),
17      foreach(res(minrealbase(Min), maxrealbase(Max), realres(RealRes), devicesum(ResWithoutPadding), paddingoverhead(PaddingOverhead),
18                  rootrange(RootMinMem, RootMaxMem), rootsize(RootSize), rootoverflow(ROMin, ROLimit), rootdifference(BaseDiff, LimitDiff),
19                  fillrate(FillRate, FillPercent), consumptionrate(ConsumptionRate, ConsumptionPercent)), ResList)
20      do
21        compute_required_resource_for_plan(Plan, Min, Max, ResWithoutPadding, RealRes, PaddingOverhead, RootMinMem,
22                                           RootMaxMem, RootSize, ROMin, ROLimit, BaseDiff, LimitDiff,
23                                           FillRate, FillPercent, ConsumptionRate, ConsumptionPercent)
24    ),
25% this would output the data for all buses, but we only want to consider one
26% because our gnuplotscript would otherwise merge the two values into one bus...
27%    ( foreach(Res, ResList)
28%      do
29%        write_gnuplot_data(Res)
30%    ),
31
32% consider only the biggest bus
33    sort(7, >=, ResList, ResListSorted),
34    [Hres|_] = ResListSorted,
35    write_gnuplot_data(Hres),
36
37    nl,
38    ( foreach(Plan, Plans)
39      do
40        write_full_tree(Plan)
41    ),
42    tell(Name),
43    ( foreach(Plan, Plans)
44      do
45        plan_to_dot(Plan)
46    ),
47    told.
48
49compute_required_resource_for_plan(BusElements, Min, Max, ResWithoutPadding, RealRes, PaddingOverhead, RootMinMem, RootMaxMem, RootSize,
50                                   ROMin, ROLimit, BaseDiff, LimitDiff, FillRate, FillPercent, ConsumptionRate, ConsumptionPercent) :-
51    maplist(base, BusElements, Base),
52    maplist(high, BusElements, High),
53    eclipse_language:min(Base, Min),
54    eclipse_language:max(High, Max),
55    RealRes is Max - Min,
56    compute_unpadded_size(BusElements, ResWithoutPadding),
57    PaddingOverhead is RealRes - ResWithoutPadding,
58    find_rootbridge_range(BusElements, RootMinMem, RootMaxMem),
59    RootSize is RootMaxMem - RootMinMem,
60    FillRate is ResWithoutPadding / RootSize,
61    FillPercent is FillRate * 100,
62    ConsumptionRate is RealRes / RootSize,
63    ConsumptionPercent is ConsumptionRate * 100,
64    BaseDiff is RootMinMem - Min,
65    LimitDiff is Max - RootMaxMem - 1,
66    ( BaseDiff < 0 ->
67        ROMin is 0;
68        ROMin is BaseDiff
69    ),
70    ( LimitDiff < 0 ->
71        ROLimit is 0;
72        ROLimit is LimitDiff
73    ).
74
75
76
77compute_unpadded_size([], 0).
78compute_unpadded_size([H|BusElements], UnpaddedSize) :-
79    buselement(bridge,_,_,_,_,_,_,_, _, _) = H,
80    compute_unpadded_size(BusElements, UnpaddedSize).
81
82compute_unpadded_size([H|BusElements], UnpaddedSize) :-
83    buselement(_,_,_,_,_,_,io,_, _, _) = H,
84    compute_unpadded_size(BusElements, UnpaddedSize).
85
86compute_unpadded_size([H|BusElements], UnpaddedSize) :-
87    buselement(device,Addr,BAR,_,_,_,mem,_, _, _) = H,
88    bar(Addr,BAR,_,S,_,_,_),
89    compute_unpadded_size(BusElements, S1),
90    UnpaddedSize is S1 + S.
91
92compute_unpadded_size_alt(BusElements, UnpaddedSize) :-
93    findall(S, (
94                member(El, BusElements),
95                buselement(device,Addr,BAR,_,_,_,mem,prefetchable, _, _) = El,
96                bar(Addr,BAR,_,S,mem,prefetchable,_)
97               ), PrefetchSize),
98    findall(S, (
99                member(El2, BusElements),
100                buselement(device,Addr,BAR,_,_,_,mem,nonprefetchable, _, _) = El2,
101                bar(Addr,BAR,_,S,mem,nonprefetchable,_)
102               ), NonPrefetchSize),
103    append(NonPrefetchSize, PrefetchSize, Sizes),
104    sum(Sizes, UnpaddedSize).
105
106
107
108find_rootbridge_range([H|_], MinMem, MaxMem) :-
109    buselement(_,addr(Bus,_,_),_,_,_,_,_,_, _, _) = H,
110    rootbridge(_, childbus(MinBus, MaxBus), mem(MinMem, MaxMem)),
111    Bus >= MinBus,
112    Bus =< MaxBus.
113
114
115write_gnuplot_data(Result) :-
116     res(minrealbase(Min), maxrealbase(Max), realres(RealRes), devicesum(ResWithoutPadding), paddingoverhead(PaddingOverhead),
117                   rootrange(RootMinMem, RootMaxMem), rootsize(RootSize), rootoverflow(ROMin, ROLimit), rootdifference(BaseDiff, LimitDiff),
118                   fillrate(FillRate, FillPercent), consumptionrate(ConsumptionRate, ConsumptionPercent)) = Result,
119
120     write("res"),
121     write("\t"),
122     write(Min),write("\t"),
123     write(Max),write("\t"),
124     write(RealRes),write("\t"),
125     write(ResWithoutPadding),write("\t"),
126     write(PaddingOverhead),write("\t"),
127     write(RootMinMem),write("\t"),
128     write(RootMaxMem),write("\t"),
129     write(RootSize),write("\t"),
130     write(ROMin),write("\t"),
131     write(ROLimit),write("\t"),
132     write(BaseDiff),write("\t"),
133     write(LimitDiff),write("\t"),
134     write(FillRate),write("\t"),
135     write(FillPercent),write("\t"),
136     write(ConsumptionRate),write("\t"),
137     write(ConsumptionPercent).
138
139
140
141
142write_full_tree(BusElements) :-
143    maplist(base, BusElements, Base),
144    maplist(high, BusElements, High),
145    eclipse_language:min(Base, Min),
146    eclipse_language:max(High, Max),
147    Size is Max - Min,
148%root bridge information
149    write("treedata"),
150    write("\t"),
151    write("base\t"),
152    write("\""),
153    write("b("),
154    write("0"),write(","),
155    write("0"),write(","),
156    write("0"),write(")"),
157    write("\"\t"),
158    write("-1"),write("\t"),
159    write(Min),write("\t"),
160    write(Size),write("\t"),
161    write("1\t"),
162    write("root bridge\t"),
163    write("0"),write("\t"),
164    write("mem"),write("\t"),
165    write("both"),write("\t"),
166    write("pcie"),write("\n"),
167    write("treedata"),
168    write("\t"),
169    write("high\t"),
170    write("\""),
171    write("b("),
172    write("0"),write(","),
173    write("0"),write(","),
174    write("0"),write(")"),
175    write("\"\t"),
176    write("-1"),write("\t"),
177    write(Max),write("\t"),
178    write(Size),write("\t"),
179    write("1\t"),
180    write("root bridge\t"),
181    write("0"),write("\t"),
182    write("mem"),write("\t"),
183    write("both"),write("\t"),
184    write("pcie"),nl,
185    write_tree(BusElements).
186
187write_tree([]).
188write_tree([buselement(bridge,addr(Bus,Dev,Fun),secondary(Sec),Base,High,Size,Type,Prefetch, PCIe, 0)|BusElements]) :-
189    write("treedata"),
190    write("\t"),
191    write("base\t"),
192    write("\""),
193    write("b("),
194    write(Bus),write(","),
195    write(Dev),write(","),
196    write(Fun),write(")"),
197    write("\"\t"),
198    write(Bus),write("\t"),
199    write(Base),write("\t"),
200    write(Size),write("\t"),
201    write("1\t"),
202    write(Bus),write("\t"),
203    write(Sec),write("\t"),
204    write(Type),write("\t"),
205    write(Prefetch),write("\t"),
206    write(PCIe),write("\n"),
207    write("treedata"),
208    write("\t"),
209    write("high\t"),
210    write("\""),
211    write("b("),
212    write(Bus),write(","),
213    write(Dev),write(","),
214    write(Fun),write(")"),
215    write("\"\t"),
216    write(Bus),write("\t"),
217    write(High),write("\t"),
218    write(Size),write("\t"),
219    write("1\t"),
220    write(Bus),write("\t"),
221    write(Sec),write("\t"),
222    write(Type),write("\t"),
223    write(Prefetch),write("\t"),
224    write(PCIe),nl,
225    write_tree(BusElements).
226
227write_tree([buselement(device,addr(Bus,Dev,Fun),BAR,Base,High,Size,Type,Prefetch, PCIe, Pin)|BusElements]) :-
228    write("treedata"),
229    write("\t"),
230    write("base\t"),
231    write("\""),
232    write("d("),
233    write(Bus),write(","),
234    write(Dev),write(","),
235    write(Fun),write(")"),
236    write("\"\t"),
237    write(Bus),write("\t"),
238    write(Base),write("\t"),
239    write(Size),write("\t"),
240    write("0\t"),
241    write(Bus),write("\t"),
242    write(BAR),write("\t"),
243    write(Type),write("\t"),
244    write(Prefetch),write("\t"),
245    write(PCIe),write("\n"),
246    write("treedata"),
247    write("\t"),
248    write("high\t"),
249    write("\""),
250    write("d("),
251    write(Bus),write(","),
252    write(Dev),write(","),
253    write(Fun),write(")"),
254    write("\"\t"),
255    write(Bus),write("\t"),
256    write(High),write("\t"),
257    write(Size),write("\t"),
258    write("0\t"),
259    write(Bus),write("\t"),
260    write(BAR),write("\t"),
261    write(Type),write("\t"),
262    write(Prefetch),write("\t"),
263    write(PCIe),nl,
264    write_tree(BusElements).
265
266
267
268
269
270
271
272%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
273% dot
274%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
275
276buses(buselement(_, addr(Bus,_,_), _, _, _, _, _, _,_,_),Bus).
277
278plan_to_dot(BusElements) :-
279    maplist(base, BusElements, Base),
280    maplist(high, BusElements, High),
281    eclipse_language:min(Base, Min),
282    eclipse_language:max(High, Max),
283    Size is Max - Min,
284    maplist(buses, BusElements, Buses),
285    eclipse_language:min(Buses,B),
286    eclipse_language:max(Buses,H),
287
288    writeln('digraph G {'),
289    writeln('\tedge[style=solid,color=black];'),
290    writeln('\tnode[color=lightblue,style=filled];'),
291    write('\t"Node'),write(B),writeln('" ['),
292    write('\t\tlabel="rootbridge: '),
293    write(Addr),write('\\l'),
294    write('childbuses: ['),write(B),write(', '),write(H),write(']\\l'),
295    write('mem: ['),printf("%x",Min),write(', '),printf("%x",Max),write(']\\l'),
296%    write('prefetchable: ['),printf("%x",PMin),write(', '),printf("%x",PMax),write(']\\l'),
297%    write('non-prefetchable: ['),printf("%x",NPMin),write(', '),printf("%x",NPMax),write(']'),
298    writeln('"'),
299    writeln('\t\tshape="hexagon"'),
300    writeln('\t\tcolor="yellow"'),
301    writeln('\t];'),
302    plan_to_dot_process_list(BusElements, B),
303    writeln('}').
304
305plan_to_dot_process_list([], _).
306plan_to_dot_process_list([buselement(bridge, addr(Bus,Dev,Fun), secondary(Sec), L, H, S, Type, Prefetch,_,_)|T], RootSecondary) :-
307    write('\t"Node'),
308    write(Sec),
309    write(Type),
310    write(Prefetch),
311    writeln('" ['),
312    write('\t\tlabel="bridge\\l'),
313    write('addr('),write(Bus),write(','),write(Dev),write(','),write(Fun),write(')'),
314    write('\\lsecondary: '),write(Sec),
315    write('\\l'),write(Type),write(':\\l['),printf("%x",L),write(',\\l '),printf("%x",H),write(']\\l'),
316    write('size: '),printf("%x",S),write('\\l'),
317    write(Prefetch),writeln('"'),
318    writeln('\t\tshape="hexagon"'),
319    ( Prefetch = prefetchable ->
320        writeln('\t\tcolor=orange');
321        true
322    ),
323    writeln('\t];'),
324    write('\t"Node'),write(Sec),write(Type),write(Prefetch),write('" -> "Node'),
325    write(Bus),
326    ( not Bus =:= RootSecondary ->
327        write(Type),
328        write(Prefetch);
329        true
330    ),
331    ( Prefetch = prefetchable ->
332        writeln('" [color=red, style=bold];');
333        writeln('" [color=blue, style=bold];')
334    ),
335    plan_to_dot_process_list(T,RootSecondary).
336
337plan_to_dot_process_list([buselement(device, addr(Bus,Dev,Fun), BAR, L, H, S, Type, Prefetch,_,_)|T], RootSecondary) :-
338    write('\t"Node'),
339    write(Bus),write(Dev),write(Fun),write(BAR),
340    writeln('" ['),
341    write('\t\tlabel="device\\l'),
342    write('addr('),write(Bus),write(','),write(Dev),write(','),write(Fun),write(')'),
343    write('\\lBAR '),write(BAR),
344    write('\\l'),write(Type),write(':\\l['),printf("%x",L),write(',\\l '),printf("%x",H),write(']\\l'),
345    write('size: '),printf("%x",S),write('\\l'),
346    write(Prefetch),writeln('"'),
347    writeln('\t\tshape="ellipse"'),
348    ( Prefetch = prefetchable ->
349        writeln('\t\tcolor=orange');
350        true
351    ),
352    writeln('\t];'),
353    write('\t"Node'),write(Bus),write(Dev),write(Fun),write(BAR),write('" -> "Node'),
354    write(Bus),
355    ( not Bus =:= RootSecondary ->
356        write(Type),
357        write(Prefetch);
358        true
359    ),
360    ( Prefetch = prefetchable ->
361        writeln('" [color=red];');
362        writeln('" [color=blue];')
363    ),
364    plan_to_dot_process_list(T,RootSecondary).
365
366
367