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, Universitaetstrasse 6, CH-8092 Zurich. Attn: Systems Group.
8%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
9
10% :-include("data_sbrinz1.txt").
11
12:-lib(ic).
13:-lib(branch_and_bound).
14
15% parallelapp(string name, int max-usable-threads, bool morecores_better?, bool synchronization_intensive).
16
17%parallelapp(a, 10, true, true).
18%parallelapp(b, 10, true, false).
19%parallelapp(c, 10, true, true).
20%parallelapp(d,  2, true, true).
21
22%parallelapp(a, 6, true, true).
23%parallelapp(b, 12, true, false).
24%parallelapp(c, 8, true, true).
25%parallelapp(d,  7, true, false).
26
27:-dynamic(parallelapp/4).
28
29scheduler_add_app(Name, MaxUsableThreads, MoreCoresBetter, SyncIntensive) :-
30    assert(parallelapp(Name, MaxUsableThreads, MoreCoresBetter, SyncIntensive)).
31
32scheduler_remove_app(Name) :-
33    retract(parallelapp(Name, _, _, _)).
34
35
36schedule(S) :-
37% make sure that the CoreIDs are sorted according to which package they belong
38%    findall(CoreID, cpu(CoreID,_), CoreIDs),
39    findall(cpu_thread(CPU, Pkg), cpu_thread(CPU, Pkg, _, _), CPUThreads),
40    sort(2, =<, CPUThreads, CPUThreadsSorted),
41    maplist(get_core_id, CPUThreadsSorted, CoreIDs),
42    length(CoreIDs, NrCores),
43    findall(Name, parallelapp(Name, _, _, true), SyncThreadNames),
44    findall(thread(Name, C, B1, false), parallelapp(Name, C, B1, false), NoSyncThreads),
45    % set the max #cores a sync thread can use to the max #hwcores available
46    setmaxcores(NrCores, SyncThreadNames, SyncThreads),
47    maplist(maxthreads, SyncThreads, SyncNrThreads),
48    maplist(maxthreads, NoSyncThreads, NoSyncNrthreads),
49    sum(SyncNrThreads,SyncS),
50    sum(NoSyncNrthreads, NoSyncS),
51    length(SyncThreads, Len1),
52    length(NoSyncThreads,Len2),
53    NrApps is Len1 + Len2,
54    ( NrApps > 0 ->
55        NrThreads is SyncS + NoSyncS,
56        virtcores(NrCores, NrCores, NrThreads, NrVCores),
57        R is NrVCores mod NrApps,
58        T1 is NrVCores - R,
59        NrVCoresPerThreadF is T1 / NrApps,
60        integer(NrVCoresPerThreadF, NrVCoresPerThread),
61        nl,write(NrVCoresPerThread),nl,write(R),nl,
62        count_to_distr_cores(NrVCoresPerThread, SyncThreads, SyncDistrCores),
63        count_to_distr_cores(NrVCoresPerThread, NoSyncThreads, NoSyncDistrCores),
64        DistrCores is SyncDistrCores + NoSyncDistrCores,
65        adjust_nr_cores(NrVCoresPerThread, DistrCores, SyncThreads, SyncThreadsAdj, NewDistrCores),
66        adjust_nr_cores(NrVCoresPerThread, NewDistrCores, NoSyncThreads, NoSyncThreadsAdj, _),
67        create_schedule(NrCores, NrVCores, NrThreads, CoreIDs, SyncThreadsAdj, NoSyncThreadsAdj, 0, S);
68        S=[]
69    ),
70    write(S),nl.
71
72
73get_core_id(cpu_thread(CPU, _), CPU).
74
75setmaxcores(_, [], []).
76setmaxcores(NrCores, [N|Threads], [TM|ThreadMax]) :-
77    parallelapp(N, M, B1, B2),
78    min(NrCores, M, Min),
79    TM = thread(N, Min, B1, B2),
80    setmaxcores(NrCores, Threads, ThreadMax).
81
82maxthreads(thread(_, M, _, _), M).
83
84virtcores(NrCoresOrig, NrCores, NrThreads, NrVCores) :-
85    N is NrCores + NrCoresOrig,
86    ( N =< NrThreads ->
87        virtcores(NrCoresOrig, N, NrThreads, NrVCores);
88        NrVCores = NrCores
89    ).
90
91
92count_to_distr_cores(AvailableCores, Threads, DistrCores) :-
93    maplist(to_distr_cores(AvailableCores), Threads, L),
94    sum(L,DistrCores).
95
96to_distr_cores(AvailableCores, thread(_, M, _, _), C) :-
97    ( M < AvailableCores ->
98        C is AvailableCores - M;
99        C is 0
100    ).
101
102adjust_nr_cores(_, NewDistrCores, [], [], NewDistrCores).
103adjust_nr_cores(AvailableCores, DistrCores, [thread(N, M, B1, B2)|Inp], [thread(N, C, B1, B2)|Outp], NewDistrCores) :-
104    M =< AvailableCores,
105    C = M,
106    adjust_nr_cores(AvailableCores, DistrCores, Inp, Outp, NewDistrCores).
107adjust_nr_cores(AvailableCores, DistrCores, [thread(N, M, B1, B2)|Inp], [thread(N, C, B1, B2)|Outp], NewDistrCores) :-
108    M > AvailableCores,
109    Tmp is AvailableCores + DistrCores,
110    min(M, Tmp, C),
111    RemC is Tmp - C,
112    adjust_nr_cores(AvailableCores, RemC, Inp, Outp, NewDistrCores).
113
114
115
116
117create_schedule(_, _, _, _, [], [], _, []).
118create_schedule(NrCores, NrVCores, NrThreads, CoreIDs, SyncThreads, NoSyncThreads, Time, S) :-
119    minimize(add_sync(SyncThreads, NrCores, Threads, RemSync, RemCores),RemCores),
120    construct_plan(Threads, Time, SubPlan),
121    write(remocres),write(RemCores),nl,
122    add_nosync(NoSyncThreads, RemCores, NoSyncPlan, NoSyncRem),
123    construct_plan(NoSyncPlan, Time, NoSyncSubPlan),
124    append(SubPlan, NoSyncSubPlan, SP),
125
126%% uncomment one of the next two lines and use append or permutation in
127%% assign_coreids/3
128
129%    assign_coreids(SP, CoreIDs, SPC),
130    minimize((assign_coreids(SP, CoreIDs, SPC),assigned_coreids_cost(SPC,Cost)), Cost),
131
132    write(Threads),write(RemCores),nl, write(SubPlan),nl,
133    NextTime is Time + 1,
134    create_schedule(NrCores, NrVCores, NrThreads, CoreIDs, RemSync, NoSyncRem, NextTime, SPNC),
135    append(SPC, SPNC, S).
136
137
138add_sync(SyncThreads,NrCores,L,R,C) :-
139    ( not SyncThreads == [] ->
140        permutation(SyncThreads,P),
141        append(L,R,P),
142        maplist(maxthreads, L, MaxT),
143        sum(MaxT,SumT),
144        SumT =< NrCores,
145        C is NrCores - SumT;
146        L = [],
147        R = [],
148        C = NrCores
149    ).
150
151permutation([], []).
152permutation(SyncThreads, List) :-
153    member(T, SyncThreads),
154    append([T],M,List),
155    subtract(SyncThreads,[T],RemainingSync),
156    permutation(RemainingSync, M).
157
158add_nosync(NoSyncThreads, NrCores, L, RemTNext) :-
159    ( not NoSyncThreads == [] ->
160        minimize(add_nosync_block(NoSyncThreads, NrCores, Threads, RemT, RemCores), RemCores),
161        write(nosync),write(Threads),nl,
162        add_nosync_part(RemT, RemCores, ThreadsPart, RemTNext),
163        append(Threads, ThreadsPart, L);
164        L = [],
165        RemTNext = []
166    ).
167
168add_nosync_block(NoSyncThreads, NrCores, L, R, C) :-
169    append(L,R,NoSyncThreads),
170    maplist(maxthreads, L, MaxT),
171    sum(MaxT,SumT),
172    SumT =< NrCores,
173    C is NrCores - SumT.
174
175add_nosync_part([T|NoSyncThreads], RemCores, [TP], [PartT|NoSyncThreads]) :-
176    thread(N, M, B1, B2) = T,
177    TP = thread(N, RemCores, B1, B2),
178    MissingThreads is M - RemCores,
179    PartT = thread(N, MissingThreads, B1, B2).
180add_nosync_part([], _, [], []).
181
182
183construct_plan([], _, []).
184construct_plan([T|Threads], Time, [P|Plan]) :-
185    P = exec(Time, T),
186    construct_plan(Threads, Time, Plan).
187
188
189assign_coreids([], _, []).
190assign_coreids([exec(T, Thread)|Plan], CoreIDs, [exec(T, Cores, Thread)|Schedule]) :-
191    thread(_, M, _, _) = Thread,
192    length(Cores, M),
193
194%% either the next line or the two lines after the next
195%    append(Cores, Rem, CoreIDs),
196%    permutation(CoreIDs, CoreIDsPerm),
197%    append(Cores, Rem, CoreIDsPerm),
198    rotation(CoreIDs, CoreIDsRot),
199    append(Cores, Rem, CoreIDsRot),
200
201    assign_coreids(Plan, Rem, Schedule).
202
203assigned_coreids_cost([], 0).
204assigned_coreids_cost([exec(_, _, thread(_, _, _, false))|L], C) :-
205    assigned_coreids_cost(L, C).
206assigned_coreids_cost([exec(_, CoreIDs, thread(_, _, _, true))|L], C) :-
207    maplist(coreid_to_packageid, CoreIDs, PackageIDs),
208    no_dups(PackageIDs, Pkgs),
209    length(Pkgs, CTmp),
210    assigned_coreids_cost(L, CSub),
211    C is CTmp + CSub.
212
213coreid_to_packageid(CoreID, PackageID) :-
214    cpu_thread(CoreID, PackageID, _, _).
215
216
217no_dups([], []).
218no_dups([H|T1],[H|T2]) :-
219    no_dups(T1, T2),
220    not member(H, T2).
221no_dups([H1|T1],L) :-
222    no_dups(T1, L),
223    member(H1,L).
224
225
226rotation(L1,L2) :-
227    length(L1, Len),
228    rotationimp(L1, L2, Len).
229
230rotationimp([], [], _).
231rotationimp([H|T],L, Len) :-
232    L = [H|T];
233    Len > 1,
234    append(T,[H],Tmp),
235    LenNew is Len - 1,
236    rotationimp(Tmp, L, LenNew).
237
238