:- lib(ic). :- lib(listut). :- lib(branch_and_bound). :- local struct(nrofsig(n)). :- local struct(signal(o, t, d, w)). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% solve(Signal_List, Frame_List) :- read_data(Signal_List), signal_packing(Signal_List, Frame_List). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% read_data(Signal_List) :- open("C:\\Documents and Settings\\g-bogta\\Desktop\\data.in", read, File), read(File, NrOfSignals), NrOfSignals = nrofsig(N), length(Signal_List, N), (foreach(Signal, Signal_List), param(File) do read(File, Tmp_Sig), Tmp_Sig = signal(Tmp_O, Tmp_T, Tmp_D, W), O is fix(Tmp_O * 1000), % ms to us T is fix(Tmp_T * 1000), % ms to us D is fix(Tmp_D * 1000), % ms to us Signal = signal(O, T, D, W) ), close(File). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% signal_packing(Signal_List, Frame_List) :- INF is 999999, TAU is 1 * 60 * 60 * 1000 * 1000, % us RHO is 1 - 10 ^ (-5), BER is 10 ^ (-7), BusFreq is 10 ^ 7, % 10 Mhz == 10 us SecToUs is 10 ^ 6, % us FC is 1200, % us SL is 250, % slot duration in bits SD is fix(SL * (SecToUs / BusFreq)), % slot duration in us NS is fix(FC /SD), % number of slots in a FlexRay cycle (FC) write(" SD: "), writeln(SD), write(" NS: "), writeln(NS), csp_per_ecu(INF, TAU, RHO, BER, FC, SL, SD, NS, Signal_List, NewSignal_List_List, Frame_List, EmptyFrame_List, O_List, T_List, D_List, W_List, K_List, FP_List, SP_List, Prod), Obj #= sum(K_List), bb_min( complete_search(FC, SL, SD, NS, Frame_List, EmptyFrame_List, O_List, T_List, D_List, K_List, S_List_List, AllSlots, Rel_List_List_List), Obj, bb_options{strategy : restart, from : 0, to : NS}), write(" Sig: "), writeln(Signal_List), write("NSig: "), writeln(NewSignal_List_List), write(" Fr: "), writeln(Frame_List), write("EmFr: "), writeln(EmptyFrame_List), write(" O: "), writeln(O_List), write(" T: "), writeln(T_List), write(" D: "), writeln(D_List), write(" W: "), writeln(W_List), write(" K: "), writeln(K_List), write(" S: "), writeln(S_List_List), write(" AS: "), writeln(AllSlots), write(" Rel: "), writeln(Rel_List_List_List), write(" FP: "), writeln(FP_List), write(" SP: "), writeln(SP_List), write("Prod: "), writeln(Prod). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% complete_search(FC, SL, SD, NS, Frame_List, EmptyFrame_List, O_List, T_List, D_List, K_List, S_List_List, AllSlots, Rel_List_List_List) :- flatten_array(Frame_List, Frame_ListVars), search(Frame_ListVars, 0, first_fail, indomain, complete, []), search(K_List, 0, first_fail, indomain, complete, []), % scheduling after computing the frames (foreach(O, O_List), foreach(T, T_List), foreach(D, D_List), foreach(K, K_List), foreach(EmptyFrame, EmptyFrame_List), foreach(S_List, S_List_List), foreach(Rel_List_List, Rel_List_List_List), param(FC, SD, NS) do % building the list of instances of each frame per on cycle build_slot_list(FC, SD, NS, EmptyFrame, O, T, D, K, S_List, Rel_List_List) ), diff_slots(S_List_List, AllSlots), search(AllSlots, 0, first_fail, indomain, complete, []). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% csp_per_ecu(INF, TAU, RHO, BER, FC, SL, SD, NS, Signal_List, NewSignal_List_List, Frame_List, EmptyFrame_List, O_List, T_List, D_List, W_List, K_List, FP_List, SP_List, Prod) :- % preprocess (foreach(Signal, Signal_List), foreach(NewSignal_List, NewSignal_List_List), param(FC) do Signal = signal(O, T, D, W), N is fix(ceiling(FC / T)), (count(I, 1, N), foreach(NewSignal, NewSignal_List), param(N, O, T, D, W) do New_O is O + (I - 1) * T, New_T is N * T, New_D is D, New_W is W, NewSignal = signal(New_O, New_T, New_D, New_W) ) ), flatten(NewSignal_List_List, F_Signal_List), length(F_Signal_List, NrOfSignals), dim(Frame_List, [NrOfSignals, NrOfSignals]), Frame_List #:: [0 .. 1], % ROWS => FRAMES ARE EMPTY or NOT (count(I, 1, NrOfSignals), foreach(EmptyFrame, EmptyFrame_List), param(NrOfSignals, Frame_List) do Row is subscript(Frame_List, [I, 1 .. NrOfSignals]), EmptyFrame #= (sum(Row) > 0) ), % COLUMNS => ONE SIGNAL in ONE FRAME (count(J, 1, NrOfSignals), param(NrOfSignals, Frame_List) do Col is subscript(Frame_List, [1 .. NrOfSignals, J]), sum(Col) #= 1 ), % (O, T, D, W) of a frame (count(I, 1, NrOfSignals), foreach(EmptyFrame, EmptyFrame_List), foreach(O, O_List), foreach(T, T_List), foreach(D, D_List), foreach(W, W_List), foreach(FP, FP_List), foreach(SP, SP_List), foreach(K, K_List), param(INF, TAU, RHO, BER, SL, NrOfSignals, F_Signal_List, Frame_List) do % (O, T, _, W) of a frame (count(J, 1, NrOfSignals), foreach(F_Signal, F_Signal_List), foreach(O_El, O_Row), foreach(T_El, T_Row), foreach(W_El, W_Row), param(INF, I, Frame_List) do Bool #= subscript(Frame_List, [I, J]), F_Signal = signal(O_Signal, T_Signal, _, W_Signal), O_El #= (1 - Bool) * INF + O_Signal, T_El #= (1 - Bool) * INF + T_Signal, W_El #= Bool * W_Signal ), T #= min(T_Row), suspend(nth1(Nth, T_Row, T), 0, T->inst), suspend(nth1(Nth, O_Row, O), 0, Nth->inst), W #= sum(W_Row), W #=< SL, K #>= 0, K #=< EmptyFrame * INF, FP $= (1 - (1 - BER) ^ W) * EmptyFrame, SP $= (1 - FP ^ (1 + K)) ^ (EmptyFrame * (TAU / T)), SP $> RHO, SP $=< 1, % (_, _, D, _) of a frame (count(J, 1, NrOfSignals), foreach(F_Signal, F_Signal_List), foreach(D_El, D_Row), param(INF, I, Frame_List, EmptyFrame, O, T) do Bool #= subscript(Frame_List, [I, J]), F_Signal = signal(O_Signal, T_Signal, D_Signal, _), Tmp_O #= Bool * O_Signal, Tmp_T #= Bool * T_Signal, Tmp_D #= Bool * D_Signal, compute_deadline(INF, EmptyFrame, Bool, Tmp_O, Tmp_T, Tmp_D, O, T, D_El) ), D #= min(D_Row), D #> 0, % max nr of rtx K #=< D / SD ), NrOfSignals + sum(K_List) #=< NS, % reliability constraint Prod $= ic_prod(SP_List), Prod $>= RHO, Prod $=< 1. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% compute_deadline(INF, EmptyFrame, Bool, Tmp_O, Tmp_T, Tmp_D, O, T, D_El) :- var(Tmp_T) -> suspend(compute_deadline(INF, EmptyFrame, Bool, Tmp_O, Tmp_T, Tmp_D, O, T, D_El), 0, Tmp_T->inst) ; var(T) -> suspend(compute_deadline(INF, EmptyFrame, Bool, Tmp_O, Tmp_T, Tmp_D, O, T, D_El), 0, T->inst) ; var(O) -> suspend(compute_deadline(INF, EmptyFrame, Bool, Tmp_O, Tmp_T, Tmp_D, O, T, D_El), 0, O->inst) ; G #= gcd(T, Tmp_T), O_Diff #= EmptyFrame * (O - Tmp_O), O_Mod #= mod(O_Diff, G), D_El #= (1 - Bool) * INF + Tmp_D - T + G - O_Mod. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% build_slot_list(FC, SD, NS, EmptyFrame, O, T, D, K, S_List, Rel_List_List) :- H #= EmptyFrame * lcm(FC, T), NrOf_T #= div(H, T), % retransmissions Len #= EmptyFrame * (K + 1), length(S_List, Len), S_List #:: [0 .. NS - 1], (count(I, 1, NrOf_T), foreach(Rel_List, Rel_List_List), param(FC, SD, O, T, D, S_List) do Start #= O + (I - 1) * T, Stop #= Start + D, Start_C #= div(Start, FC), Stop_C #= div(Stop, FC), (foreach(S, S_List), foreach(Rel, Rel_List), param(FC, SD, Start, Start_C, Stop, Stop_C) do C #:: [Start_C .. Stop_C], Rel #= C * FC + S * SD, Rel #>= Start, Rel #=< Stop ), % elements must be sorted (fromto(Rel_List, [Rel_i | Tail], Tail, []) do (foreach(Rel_j, Tail), param(Rel_i) do Rel_i #< Rel_j ) ) ). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% diff_slots(S_List_List, AllSlots) :- flatten(S_List_List, AllSlots), alldifferent(AllSlots). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% :- mode ic_prod(+, -). ic_prod(List, Rez) :- ic_prod(List, 1, Rez). ic_prod([], Rez, Rez). ic_prod([H | T], Prod, Rez) :- Prod1 $= H * Prod, ic_prod(T, Prod1, Rez).