route.pl

PRl教学程序 PRl教学程序 PRl教学程序

%------------------------------------------------------------
%   File   : route.pl
%   Author : Neng-Fa ZHOU
%   Date   : 1996-1997
%   Purpose: A multi-layer channel router in CLP(FD)
%            written originally for B-Prolog (2.1)
%            should be easily ported to Eclipse and SICStus
/*********************************************************************
Problem Description:
VLSI layout design consists of two phases: the first phase, called
placement, determines the positions of the modules on the VLSI chip,
and the second phase, called routing, connects the modules with
wiring. Channel routing is a kind of routing where the routing area is
restricted to a rectangular channel. A channel consists of two
parallel rows with terminals on them. A connection requirement, called
a net, specifies the terminals that must be interconnected through a
routing path. A channel routing problem is to find routing paths for a
given set of nets in a given channel such that no paths overlap each
other.

Use:
   Vars in L..U    : declaration of domain variables
   Var notin L..U  : equal to (Var #<L; Var #> U)
   indomain(X)     : enumerate X
   X #\= Y         : inequality constraint
   freeze(X,G)     : delay G until X is instantiated

Acknowledgement:
Part of the work was supported by AITEC.

References:
Simonis, H., Channel Routing Seen as a Constraint Problem, Tech. Rep., 
TR-LP-51, ECRC, Munich, July, 1990. 

Huitoze, S.L. and Dechier D., Channel Routing with clp(FD), Proc. of 
2nd PACT, 1996.

Zhou, N.F., A Logic Programming Approach to Channel Routing, Proc. 
12th ICLP, Kanazawa, MIT Press, 159-173, 1995.

Zhou, N.F., Channel Routing with Constraint Logic Programming and Delay,
Proc. 9th IEA-AIE, Fukuoka, Gordon and Breach Pub. 383-388, 1996.
*********************************************************************/
go1:- % one horizontal layer channel 
    N=72, L=1, T=28, C=174, 
    main(N,L,T,C).

go2:- % two horizontal layer channel 
    N=72, L=2, T=10, C=174, 
    main(N,L,T,C).

go3:- % three horizontal layer channel 
    N=72, L=3, T=7, C=174, 
    main(N,L,T,C).

go4:- % four horizontal layer channel 
    N=72, L=4, T=5, C=174, 
    main(N,L,T,C).

main(N,L,T,C):-
    statistics(runtime,[Start|_]),
    route(N,L,T,C,Start,Vector),
    statistics(runtime,[End|_]),
    write(output),nl,
    output(N,L,T,C,Vector),
    Time is End-Start,
    write('%execution time go1='), write(Time), write(' milliseconds'),nl,
    told.
    
route(N,L,T,C,Start,Vector):-
    functor(Vector,nets,N),  % N<256 in some systems
    build_net_vector(1,N,Vector), 
    functor(G,graphs,N),      % generate constraint graphs Gv and Gh
    build_constraint_graphs(N,Vector,G),
    compute_depth(1,N,Vector,G),
    Vector=..[_|Nets],
    order_nets(Nets,OrdNets,G),
    extract_domain_vars(OrdNets,Vars),
    TotalTracks is L*T-1,
    Vars in 0..TotalTracks,
    generate_constraints(1,N,Vector,G,L,T), % generate constraints from Gv and Gh
    labeling_ff(Vars).

/*****************************************************************
Each net is represented as a term:

    net(N0,Head,Tail,Terminals,Track,Depth)

where N0 is the number of the net, Head is the left-most terminal 
Number, Tail is the right-most terminal Number, Terminals is a set 
of terminals in the net, and Track is a domain variable.
*****************************************************************/
build_net_vector(N0,N,Vector):-
    N0>N,!.
build_net_vector(N0,N,Vector):-
    net(N0,Terminals),
    net_head(Terminals,Head),
    net_tail(Terminals,Tail),
    Var=net(N0,Head,Tail,Terminals,Track,Depth),
    arg(N0,Vector,Var),
    N1 is N0+1,
    build_net_vector(N1,N,Vector).

compute_depth(N0,N,Vector,G):-
    N0>N,!.
compute_depth(N0,N,Vector,G):-
    arg(N0,G,Node),
    compute_depth_node(Node,Vector,G,_),
    N1 is N0+1,
    compute_depth(N1,N,Vector,G).

compute_depth_node(node(N,Tag,As,Bs,Hs),Vector,G,Dep):-
    arg(N,Vector,Net),
    depth_field(Net,Depth),
    nonvar(Depth),!,Dep=Depth.
compute_depth_node(node(N,Tag,[],Bs,Hs),Vector,G,Dep):-!,
    arg(N,Vector,Net),
    depth_field(Net,0),
    Dep=0.
compute_depth_node(node(N,Tag,As,Bs,Hs),Vector,G,Dep):-
    compute_depth_nodes(As,0,Depth,Vector,G),
    Depth1 is Depth+1,
    arg(N,Vector,Net),
    depth_field(Net,Depth1),
    Dep=Depth1.

compute_depth_nodes([],Depth0,Depth,Vector,G):-
    Depth=Depth0.
compute_depth_nodes([Node|As],Depth0,Depth,Vector,G):-
    compute_depth_node(Node,Vector,G,NodeDepth),
    (NodeDepth>Depth0->Depth1=NodeDepth; Depth1=Depth0),
    compute_depth_nodes(As,Depth1,Depth,Vector,G).

/*****************************************************************
Order nets based on the constraint graphs
*****************************************************************/
order_nets([],OrdNets,G):-!,
    OrdNets=[].
order_nets(Nets,OrdNets,G):-
    choose_net(Nets,Net,RestNets,G),
    remove_net(Net,G),
    OrdNets=[Net|OrdNets1],
    order_nets(RestNets,OrdNets1,G).

choose_net([Net|Nets],BestNet,Rest,G):-
    evaluate_net(Net,EValue,G),
    choose_net(Nets,Net,EValue,BestNet,Rest,G).

choose_net([],Net,EValue,BestNet,Rest,G):-
    BestNet=Net,
    Rest=[].
choose_net([Net|Nets],Net1,EValue1,BestNet,Rest,G):-
    evaluate_net(Net,EValue,G),
    compare_net(Net1,EValue1,Net,EValue,GoodNet,GoodEValue,BadNet),
    Rest=[BadNet|Rest1],
    choose_net(Nets,GoodNet,GoodEValue,BestNet,Rest1,G).

compare_net(Net1,EValue1,Net,EValue,GoodNet,GoodEValue,BadNet):-
    eval_ge(EValue1,EValue),!,
    GoodNet=Net1,
    GoodEValue=EValue1,
    BadNet=Net.
compare_net(Net1,EValue1,Net,EValue,GoodNet,GoodEValue,BadNet):-
    GoodNet=Net,
    GoodEValue=EValue,
    BadNet=Net1.

eval_ge([],[]):-!.
eval_ge([X|Xs],[Y|Ys]):-
    X>Y,!.
eval_ge([X|Xs],[Y|Ys]):-
    X=:=Y,!,
    eval_ge(Xs,Ys).

% 1: select first open nets, i.e., nets at the bottom of Gv
% 2: select first those nets lie deep in Gv
% 3: select first those nets with the greatest degree in Gv 
% 4: select first those nets with the greatest degree in Gh
evaluate_net(Net,EValue,G):-
    arg(1,Net,N),
    is_open(N,Open,G),
    depth_field(Net,Depth),
    gv_degree(N,G,Degree1),
    gh_degree(N,G,Degree2),
    EValue=[Open,Depth,Degree1,Degree2].

is_open(N,Open,G):-
    arg(N,G,node(_,Tag,As,Bs,Hs)),
    empty_nodes(Bs),!,
    Open=1.
is_open(N,Open,G):-
    Open=0.

empty_nodes([]).
empty_nodes([node(N,Tag,_,_,_)|Nodes]):-
    var(Tag),!,fail.
empty_nodes([Node|Nodes]):-
    empty_nodes(Nodes).

gv_degree(N,G,Degree):-
    arg(N,G,node(_,_,As,Bs,Hs)),
    degree(Bs,0,Degree).

gh_degree(N,G,Degree):-
    arg(N,G,node(_,_,As,Bs,Hs)),
    degree(Hs,0,Degree).

degree([],N0,N):-N=N0.
degree([node(_,Tag,_,_,_)|Nodes],N0,N):-
    var(Tag),!,
    N1 is N0+1,
    degree(Nodes,N1,N).
degree([Node|Nodes],N0,N):-
    degree(Nodes,N0,N).

/********************************************************************
The constraint graphs Gv and Gh are represented as a functor whose I'th
argument has the form:

    node(I,Tag,As,Bs,Hs)

where As is the list of nets lying directly above I and Bs is the list
of nets lying directly below I in Gv, Hs is a list of nets connected to
I in Gh, and Tag is used to indicate whether the net has been removed 
from the graphs.
*********************************************************************/
build_constraint_graphs(N,Vector,G):-
    build_constraint_graphs(1,N,Vector,G).

build_constraint_graphs(N0,N,Vector,G):-
    N0>N,!.
build_constraint_graphs(N0,N,Vector,G):-
    arg(N0,Vector,Net0),
    Node=node(N0,Tag,As,Bs,Hs),
    compute_As_Bs_Hs(N0,Net0,1,N,Vector,G,[],As,[],Bs,[],Hs),
    arg(N0,G,Node),
    N1 is N0+1,
    build_constraint_graphs(N1,N,Vector,G).

compute_As_Bs_Hs(N,Net,From,To,Vector,G,As0,As,Bs0,Bs,Hs0,Hs):-
    From>To,!,
    As=As0, Bs=Bs0, Hs=Hs0.
compute_As_Bs_Hs(N,Net,From,To,Vector,G,As0,As,Bs0,Bs,Hs0,Hs):-
    From=:=N,!,
    From1 is From+1,
    compute_As_Bs_Hs(N,Net,From1,To,Vector,G,As0,As,Bs0,Bs,Hs0,Hs).
compute_As_Bs_Hs(N,Net,From,To,Vector,G,As0,As,Bs0,Bs,Hs0,Hs):-
    arg(From,Vector,Net0),
    arg(From,G,Node),
    (above(Net0,Net)->As1=[Node|As0];As1=As0),
    (above(Net,Net0)->Bs1=[Node|Bs0];Bs1=Bs0),
    (h_overlap(Net,Net0)->Hs1=[Node|Hs0];Hs1=Hs0),
    From1 is From+1,
    compute_As_Bs_Hs(N,Net,From1,To,Vector,G,As1,As,Bs1,Bs,Hs1,Hs).

%%%%%%%%%%%%%%%%%%%%%%% generate constraints %%%%%%%%%%%%%%%%%%%%%%% 
generate_constraints(N0,N,Vector,G,MaxL,MaxT):-
    N0>N,!.
generate_constraints(N0,N,Vector,G,MaxL,MaxT):-
    arg(N0,G,node(_,_,As,Bs,Hs)),
    arg(N0,Vector,Net0),
    track_field(Net0,Track0),
    (MaxL=:=1->
     global_vertical_constraints(Track0,1,Bs,Vector)
      ;vertical_constraints(Track0,Bs,Vector,MaxT)),
    horizontal_constraints(Track0,Hs,Vector),
    N1 is N0+1,
    generate_constraints(N1,N,Vector,G,MaxL,MaxT).

% if X>Y and Y>Z then X>Z+1
global_vertical_constraints(Track0,I,[],Vector).
global_vertical_constraints(Track0,I,[Node|Nodes],Vector):-
    global_vertical_constraint(Track0,I,Node,Vector),
    global_vertical_constraints(Track0,I,Nodes,Vector).

global_vertical_constraint(Track0,I,node(N,_,As,Bs,Hs),Vector):-
    arg(N,Vector,Net),
    track_field(Net,Track),
    Track0#>=Track+I,