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