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:-dynamic(route_child/2). 11 12:- set_flag(print_depth, 500). 13 14% make groups of numbers to be able to do a breadth-first search 15route_listgroups(NrGroups,L,G) :- 16 length(L,Len), 17 T1 is Len / NrGroups, 18 ceiling(T1,T2), 19 integer(T2,GLen), 20 route_listgroupsimpl(L,GLen,G). 21 22route_listgroupsimpl([],_,[]). 23route_listgroupsimpl(L,GLen,[G1|G]) :- 24 length(L,Len), 25 M is min(Len,GLen), 26 M > 0, 27 length(G1, M), 28 append(G1,Rem,L), 29 route_listgroupsimpl(Rem,GLen,G). 30 31% construct the tree 32route_tree(Radix, Root, L, T) :- 33 route_listgroups(Radix, L, G), 34 ( foreach(El, G), 35 foreach(ST, SubTrees), 36 param(Radix) 37 do 38 [R|C] = El, 39 route_tree(Radix, R, C, ST) 40 ), 41 T = node(Root, SubTrees). 42 43% construct the routing table out of the tree 44route_postorder(Tree, L, CurrRoutes) :- 45 node(Root, Children) = Tree, 46 ( foreach(C, Children), 47 foreach(E, Elements), 48 foreach(SubRoute, SubRoutes), 49 foreach(Ne, Neighbours) 50 do 51 route_postorder(C, E, SubRoute), 52 node(Ne, _) = C 53 ), 54 flatten(Elements,FE), 55 flatten(SubRoutes, SubRoutesF), 56 append(FE,[Root],L), 57 append(SubRoutesF, [route(Root,FE, Neighbours)],CurrRoutes). 58 59% construct routing table for all cores 60route_allcores_alt(Radix,Root,Routes,L) :- 61 subtract(L,[Root],L2), 62 route_tree(Radix, Root, L2, T), 63 route_postorder(T, _, Routes). 64 65 66%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 67% new code 68%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 69 70route_neighbours(S, L) :- 71 findall(C, route_child(S, C), L). 72 73route_reach(S, L) :- 74 route_neighbours(S, R), 75 ( foreach(El, R), 76 foreach(REl, SubRoutes) 77 do 78 route_reach(El, REl) 79 ), 80 flatten(SubRoutes,SubRoutesF), 81 append(R, SubRoutesF, L). 82 83 84% create the route_child(Source, Dest) facts 85route_create_facts(_, _, _, []). 86route_create_facts(Radix, 0, [_|NodeList], L) :- 87 route_create_facts(Radix, Radix, NodeList, L). 88route_create_facts(Radix, N, [Root|NodeList], [H|T]) :- 89 N > 0, 90 assert(route_child(Root, H)), 91 M is N - 1, 92 append([Root|NodeList],[H],LL), 93 route_create_facts(Radix, M, LL, T). 94 95 96% root has to be partd of the CoreList 97route_create_routing(Radix, Root, CoreList, Routes) :- 98 member(Root, CoreList), 99 subtract(CoreList, [Root], CoreListWORoot), 100 retractall(route_child(_,_)), 101 route_create_facts(Radix, Radix, [Root], CoreListWORoot), 102 ( foreach(El, [Root|CoreListWORoot]), 103 foreach(R, Routes) 104 do 105 route_reach(El, Reach), 106 route_neighbours(El, Neighbours), 107 R = route(El, Reach, Neighbours) 108 ). 109 110% construct routing table for all cores 111route_allcores(Radix,Root,Routes, L) :- 112 route_create_routing(Radix, Root, L, Routes). 113 114% construct dot output for pretty diagrams 115% to use: eclipse -b route_tree_radix.pl -e 'route_demo(4,16)' | dot -Tpdf -o route.pdf 116route_demo(Radix,NCores) :- 117 Root is 0, 118 (for(I,0,NCores - 1), foreach(I,CoreList) do true), 119 120 route_create_routing(Radix, Root, CoreList, _), 121 ( foreach(C,CoreList), 122 foreach(L,Links) 123 do 124 route_neighbours(C, Neighbours), 125 L = neigh(C,Neighbours) 126 ), 127 128 writeln("digraph G {"), 129 writeln(" node [shape=circle,width=.6,fixedsize=true];"), 130 ( foreach(L,Links) 131 do 132 neigh(C,Neighbours) = L, 133 ( foreach(N,Neighbours), param(C) 134 do 135 printf(" %d -> %d;\n", [C, N]) 136 ) 137 ), 138 writeln("}"). 139