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