:- lib(ic). :- lib(listut). :- lib(arrays). :- lib(branch_and_bound). :- local struct(nrofecu(n)). :- local struct(nrofsig(n)). :- local struct(signal(o, t, d, w)). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% solve(Signal_List_List, Frame_List_0, Frame_List_1) :- read_data(Signal_List_List), writeln("\tInput Data:"), (foreach(Signal_List, Signal_List_List) do writeln(Signal_List) ), writeln("#############################################"), once signal_packing(Signal_List_List, Frame_List_0, 0). %writeln("#############################################"), %once signal_packing(Signal_List_List, Frame_List_1, 1). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% read_data(Signal_List_List) :- open("C:\\Documents and Settings\\g-bogta\\Desktop\\rle_data.in", read, File), read(File, NrOfEcus), NrOfEcus = nrofecu(N), length(Signal_List_List, N), (foreach(Signal_List, Signal_List_List), param(File) do read(File, NrOfSignals), NrOfSignals = nrofsig(M), length(Signal_List, M), (foreach(Signal, Signal_List), param(File) do read(File, Signal) ) ), close(File). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% signal_packing(Signal_List_List, Frame_List_List, Flag) :- INF is 999999, TAU is 1 * 60 * 60 * 1000 * 1000, % us RHO is 1 - 10 ^ (-7), BER is 10 ^ (-7), BusFreq is 10 ^ 7, % 10 Mhz == 10 us SecToUs is 10 ^ 6, % us FC is 1000, % us SL is 256, % slot duration in bits SD is (SL * (SecToUs / BusFreq)), % slot duration in ms NS is fix(FC /SD), % number of slots in a cycle (FC) write(" SD: "), writeln(SD), write(" NS: "), writeln(NS), (foreach(Signal_List, Signal_List_List), foreach(Frame_List, Frame_List_List), foreach(Index_List_List, Index_List_List_List), foreach(EmptyFrame_List, EmptyFrame_List_List), foreach(O_List, O_List_List), foreach(T_List, T_List_List), foreach(D_List, D_List_List), foreach(W_List, W_List_List), foreach(K_List, K_List_List), foreach(FP_List, FP_List_List), foreach(SP_List, SP_List_List), foreach(Prod, Prod_List), param(INF, TAU, RHO, BER, FC, SL, SD, NS) do csp_per_ecu(INF, TAU, RHO, BER, FC, SL, SD, NS, Signal_List, Frame_List, Index_List_List, EmptyFrame_List, O_List, T_List, D_List, W_List, K_List, FP_List, SP_List, Prod) ), flatten(EmptyFrame_List_List, EmptyFrames), flatten(O_List_List, Offsets), flatten(T_List_List, Periods), flatten(D_List_List, Deadlines), flatten(W_List_List, Lengths), flatten(K_List_List, Rtxs), Obj #= sum(EmptyFrames) + Flag * sum(Rtxs), bb_min( complete_search(FC, SD, NS, Frame_List_List, EmptyFrames, Offsets, Periods, Deadlines, Rtxs, S_List_List, AllSlots, C_List_List, Rel_List_List_List, Index_List_List_List), Obj, bb_options{strategy : continue, from : 0, to : NS}), write(" Sig: "), writeln(Signal_List_List), write(" Fr: "), writeln(Frame_List_List), write(" Idx: "), writeln(Index_List_List_List), write("EmFr: "), writeln(EmptyFrame_List_List), write(" O: "), writeln(O_List_List), write(" T: "), writeln(T_List_List), write(" D: "), writeln(D_List_List), write(" W: "), writeln(W_List_List), write(" K: "), writeln(K_List_List), write(" S: "), writeln(S_List_List), write(" C: "), writeln(C_List_List), write(" AS: "), writeln(AllSlots), write(" Rel: "), writeln(Rel_List_List_List), write(" FP: "), writeln(FP_List_List), write(" SP: "), writeln(SP_List_List), write("Prod: "), writeln(Prod_List). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% complete_search(FC, SD, NS, Frame_List_List, EmptyFrames, Offsets, Periods, Deadlines, Rtxs, S_List_List, AllSlots, C_List_List, Rel_List_List_List, Index_List_List_List) :- (foreach(Frame_List, Frame_List_List) do %dim(Frame_List, [A, B]), %(count(I, 1, A), param(B, Frame_List) do % (count(J, 1, B), param(I, Frame_List) do % Bool is subscript(Frame_List, [I, J]), % search([Bool], 0, first_fail, indomain, complete, []) % ) % ) search(Frame_List, 0, first_fail, indomain, complete, []) ), search(Rtxs, 0, first_fail, indomain, complete, []), writeln(Index_List_List_List). % scheduling after computing the frames %(foreach(O, Offsets), % foreach(T, Periods), % foreach(D, Deadlines), % foreach(K, Rtxs), % foreach(Ef, EmptyFrames), % foreach(S_List, S_List_List), % foreach(C_List, C_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, % Ef, % O, T, D, K, % S_List, C_List, Rel_List_List) % ), % %diff_slots(S_List_List, AllSlots), %search(AllSlots, 0, first_fail, indomain_reverse_min, complete, []). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% csp_per_ecu(INF, TAU, RHO, BER, FC, SL, SD, NS, Signal_List, Frame_List, Index_List_List, EmptyFrame_List, O_List, T_List, D_List, W_List, K_List, FP_List, SP_List, Prod) :- % initially put each signal into one frame length(Signal_List, NrOfSignals), dim(Frame_List, [NrOfSignals, NrOfSignals]), Frame_List #:: [0 .. 1], % ROWS => FRAMES ARE EMPTY or NOT (count(I, 1, NrOfSignals), foreach(Index_List, Index_List_List), foreach(EmptyFrame, EmptyFrame_List), param(NrOfSignals, Frame_List) do Row is subscript(Frame_List, [I, 1 .. NrOfSignals]), EmptyFrame #= (sum(Row) > 0), % build the index list (count(J, 1, NrOfSignals), foreach(Index, Index_List), param(I, Frame_List) do Bool is subscript(Frame_List, [I, J]), Index #= Bool * J ) % avoid exploring simetric solutions %(fromto(Index_List, [Index_i | Tail], Tail, []) do % (foreach(Index_j, Tail), param(Index_i) do % Index_i * Index_j #=< Index_j * Index_j % ) % ) ), % 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, Signal_List, Frame_List) do % (O, T, _, W) of a frame (count(J, 1, NrOfSignals), foreach(Signal, 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]), 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(Signal, Signal_List), foreach(D_El, D_Row), param(INF, I, Frame_List, EmptyFrame, T) do Bool #= subscript(Frame_List, [I, J]), Signal = signal(_, T_Signal, D_Signal, _), Tmp_T #= Bool * T_Signal, Tmp_D #= Bool * D_Signal, compute_deadline(INF, EmptyFrame, Bool, Tmp_T, Tmp_D, T, D_El) ), D #= min(D_Row), D #> 0, % max nr of rtx K #=< D / SD ), % reliability constraint Prod $= ic_prod(SP_List), Prod $>= RHO, Prod $< 1. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% compute_deadline(INF, EmptyFrame, Bool, Tmp_T, Tmp_D, T, D_El) :- var(Tmp_T) -> suspend(compute_deadline(INF, EmptyFrame, Bool, Tmp_T, Tmp_D, T, D_El), 0, Tmp_T->inst) ; var(T) -> suspend(compute_deadline(INF, EmptyFrame, Bool, Tmp_T, Tmp_D, T, D_El), 0, T->inst) ; G #= gcd(T, Tmp_T), D_El #= (1 - Bool) * INF + Tmp_D - T + G. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% build_slot_list(FC, SD, NS, EmptyFrame, O, T, D, K, S_List, C_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(C, C_List), 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), %Start_Diff #= Start - Start_C * FC, %Stop_Diff #= Stop - Stop_C * FC, %Start_Slot #= div(Start_Diff, SD) + 1, %Stop_Slot #= div(Stop_Diff, SD) - 1, %write("("), write(Start_C), write(","), write(Start_Slot), write(")"), %write(" .. "), %write("("), write(Stop_C), write(","), write(Stop_Slot), writeln(")"), C #:: [Start_C .. Stop_C], (foreach(S, S_List), foreach(Rel, Rel_List), param(FC, SD, C, Start, Stop) do 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).