1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2% Copyright (c) 2009, 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, Universitaetstrasse 6, CH-8092 Zurich. Attn: Systems Group.
8%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
9
10% :-include("boardlayout.pl").
11% :-include("gruyere_rtt_facts.txt").
12
13:-lib(branch_and_bound).
14
15% filters out duplicates
16
17filter([], []).
18filter([H|T], L) :-
19    filter(T, M),
20    ( not member(H, M) ->
21        append(M, [H], L);
22        L = M
23    ).
24
25
26% sanity check: Check first that we have all the necessary information
27multicast_sanity_check :-
28    is_predicate(nr_running_cores/1),
29    is_predicate(cpu_thread/4),
30    is_predicate(message_rtt/6),
31    nr_running_cores(NrRunningCores),
32    findall(X,cpu_thread(X,_,_,_),L),
33    length(L,NrRunningCores),
34    ExpectedNrRTTMeasurements is NrRunningCores * (NrRunningCores - 1),
35    findall(X, message_rtt(X,_,_,_,_,_), L2),
36    length(L2, ExpectedNrRTTMeasurements).
37
38
39
40% construct links to all the neighbours of APIC_ID on the same package as it
41sendNeighbours(APIC_ID, Sends) :-
42    % find package containing APIC_ID
43    cpu_thread(APIC_ID, Package, _, _),
44    % construct links to all my neighbours
45    findall(sendto(APIC_ID,X),(cpu_thread(X,Package,_,_),X =\= APIC_ID),Sends).
46
47% creates a list with sendto(SrcCore, DstCore) to define which core should send
48% to which other core
49
50% sends(+StartCore, +PackageList, -SendsList)
51sends(_, [],[]).
52sends(StartAPIC_ID, [H|T],[HS|Sends]) :-
53    % find the lowest APIC ID on the package as APIC_ID
54    findall(X, cpu_thread(X, H, _, _), APICIDs),
55    sort(APICIDs, [APIC_ID|_]),
56    % construct a link to it from the start ID
57    HS = sendto(StartAPIC_ID, APIC_ID),
58    % recurse on other packages
59    sends(StartAPIC_ID, T, Sends2),
60    % find all the cores on the same package as APIC_ID, and add pairs for them
61    sendNeighbours(APIC_ID, M),
62    append(Sends2,M,Sends).
63
64
65% add the rtt number to every sendto tuple
66
67annotate_rtt([],[]).
68annotate_rtt([sendto(Src,Dst)|T1],[sendto(Src,Dst,Lat)|T2]) :-
69    message_rtt(Src,Dst,Lat1,_,_,_),
70    message_rtt(Dst,Src,Lat2,_,_,_),
71    Lat is Lat1 + Lat2,
72    annotate_rtt(T1,T2).
73
74
75% constructs the send list starting at StartCore
76
77multicast_tree_cost(StartCore,[SendH|SendList], Cost) :-
78    multicast_sanity_check,
79    % determine package of start core
80    cpu_thread(StartCore, StartPackage, _, _),
81    % construct list of other packages
82    findall(X, (cpu_thread(_,X,_,_), X =\= StartPackage), L),
83    filter(L,PackageList),
84    % compute possible links to those packages as SendList1
85    sends(StartCore, PackageList, SendList1),
86    % compute links from start core to its neighbours
87    sendNeighbours(StartCore, Neighbours),
88    append(SendList1, Neighbours, SendList2),
89    % annotate with RTT of each link
90    annotate_rtt(SendList2, SendList3),
91    % sort by decreasing RTT
92    sort(3, >=, SendList3, [SendH|SendList]),
93    % determine cost as maximum single-link RTT
94    % XXX: this is not quite right, we really care about maximum end-to-end RTT
95    sendto(_,_,Cost) = SendH.
96
97
98
99% goal to be called.
100% Construct a list of sendto/3 goals, sort them by latency in decreasing order and
101% minimize the value of the longest latency
102
103multicast_tree(StartCore,SendList) :-
104    minimize(multicast_tree_cost(StartCore, SendList, Cost), Cost).
105
106