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% :-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