!14/05 %endoflist %owninteger upper bound= 0 %integerfn LONGEST PATH(%integer dir,inc decs,mark lp) %record(NODELIST) stack= 0 %record(NODELIST)%name stacktop== stack %record(NODE)%name current,next,reverse,end %record(ARCC)%name arc %integer temp %byte finished= no %routine PUSH STACK(%record(NODE)%name new) %record(NODELIST)%name lister== NEW NODELIST !printstring("push");write(new_x,0);write(new_y,0);newline lister_node== new lister_next== stacktop_next stacktop_next== lister %end %record(NODE)%map POP STACK %record(NODELIST)%name remove== stacktop_next %record(NODE)%name node== remove_node !printstring("pop");write(node_x,0);write(node_y,0);newline stacktop_next== remove_next DISPOSE NODE LIST(remove) %result== node %end %routine CC TEST(%record(NODE)%name nodde,%integer dir) %ownbyte free= 1 %ownbyte grouping= 1 %byte k,j,i= 1 %byte stackgroup= no %integer np1,np2 %bytearray empty(1:20) %ownbytearray cc (1:20) %ownbytearray group(1:20) %ownbytearray reqd(0:20) %integer removed= 0 %ownrecord(NODE)%namearray test(1:20) %ownrecord(ARCC)%namearray ptr (1:20,1:40) %record(ARCC)%name arc== nodde_cons(dir) %record(NODE)%name nexx %routine TEST PL(%integer a,b,c,%byte which,all) %integer i,m %for i= a,b,c %cycle %for j= 1,1,test(i)_cc(dir) %cycle %if ptr(i,j)_next node== test(which) %start np1= test(i)_path length(dir) + ptr(i,j)_length %if np1 > test(which)_path length(dir) %start test(which)_path length(dir)= np1 test(which)_backtrack== test(i) test(which)_on lp== ptr(i,j) %finish %for k= 1,1,test(which)_cc(dir) %cycle %if ptr(which,k)_next node== test(i) %start np2= test(which)_path length(dir) + ptr(which,k)_length %if np2 > test(i)_path length(dir) %start test(i)_path length(dir)= np2 test(i)_backtrack== test(which) test(i)_on lp== ptr(which,k) %finish %finish %repeat %if all= yes %start cc(i)= cc(i)-1 cc(which)= cc(which)-1 %if group(i)= 0 %and group(which)= 0 %start group(i)= grouping group(which)= grouping reqd(grouping)= cc(i) + cc(which) grouping= grouping + 1 %else %if group(which)= 0 group(which)= group(i) reqd(group(i))= reqd(group(i))+ cc(which)-1 %else %if group(i)= 0 group(i)= group(which) reqd(group(i))= reqd(group(i))+cc(i)-1 %else %if group(which)# group(i) %for m=1,1,which-1 %cycle %if group(m)=group(which) %start reqd(group(i))= %c reqd(group(i))+reqd(group(m)) group(m)=group(i) %finish %repeat reqd(group(i))= reqd(group(i))-2 group(which)= group(i) grouping= grouping-1 %else %if group(which)= group(i) reqd(group(i))= reqd(group(i))-2 %finish %if reqd(group(i))= 0 %then stack group= group(i) %finish %finish %repeat %repeat %end %while arc## nil %cycle %if arc_next node_class# notional %start ptr(free,i)== arc i= i+1 %finish arc== arc_another arcc %repeat cc(free)= nodde_cc(dir) test(free)== nodde group(free)= 0 TEST PL(1,1,free-1,free,yes) %if stack group# no %start %for i=1,1,free %cycle %if group(i)= stack group %then TEST PL(free-1,-1,1,i,no) %repeat PUSH STACK(test(free)) %for i= 1,1,free-1 %cycle %if group(i)= stack group %start PUSH STACK(test(i)) free= free-1 %for j= 1,1,test(free)_cc(dir) %cycle ptr(i,j)== ptr(free,j) %repeat cc(i)= cc(free) test(i)== test(free) group(i)= group(free) %finish %repeat grouping= grouping-1 %finish %else free= free + 1 %end %if dir= ydir %start PUSH STACK(left edge) %elseif dir = xdir PUSH STACK(bottom edge) %finish %while stacktop_next## nil %cycle current== POP STACK arc== current_arccs(dir) %while arc## nil %cycle next== arc_next node next_checked= next_checked + 1 %if arc_include= yes %and (arc_dec= no %or inc decs= yes) %start temp= current_path length(dir) + arc_length %if temp > next_path length(dir) %start next_path length(dir)= temp next_backtrack== current next_on lp== arc %finish %finish %if next_checked= next_in arc count(dir) %start %if next== right edge %or next== top edge %then %c finished= yes %and %exit %if next_cc(dir)# 0 %then %c CC TEST(next,dir) %c %else %c PUSH STACK(next) %finish arc== arc_another arcc %repeat %if finished= yes %then %exit %repeat %if stacktop_next## nil %then printstring(" STACK NOT EMPTY") %if finished# yes %then printstring(" LP NOT FOUND ! ") %if dir= xdir %then end== top edge %else end== right edge %if mark lp= yes %start reverse== end %while reverse## left edge %and %c reverse## bottom edge %cycle reverse_on lp_lp route= yes reverse== reverse_back track %repeat %finish %result= end_path length(dir) %end !_______________________________________________________________________________ %owninteger abort= no %owninteger %array optimal decisions(1:1000) !____________________________________________________________________________ %routine USE OPTIMAL DECISIONS %integer i %for i= 1,1,dec count-1 %cycle %if optimal decisions(i)= not set %start %else dec arc(i,Xdir)_include= optimal decisions(i) dec arc(i,Ydir)_include= yes-dec arc(i,Xdir)_include %finish %repeat CLEAN CONSTRAINT GRAPH(no) i= LONGEST PATH(Xdir,yes,yes) CLEAN CONSTRAINT GRAPH(yes) i= LONGEST PATH(Ydir,yes,yes) %end !____________________________________________________________________________ %routine INDICATE SIZE(%integer lambda) %ownreal allred= 0 %real reduct enable reg= any colour set colour(black) FILL(mouse display x+ 40,screen y + 10, %c mouse display x+ 120,screen y + 20) DISPLAY(itos(lambda,0)." L~",mouse display x + 40,screen y+ 10,cyan) gotoxy(20,20) reduct= -100*(1-(upperbound/lambda)) printstring("last reduction:");print(reduct,3,2) printstring("%") allred= allred+reduct gotoxy(22,22) printstring("Total Reduction:");print(allred,3,2) printstring("%") upper bound= lambda goto xy(15,5) printstring("Best Solution:");write(upper bound,2) %end !___________________________________________________________________________ %routine ADD ORDERED(%record(ORDERED)%name find, %integer dec index,area,order) %record(ORDERED)%name new== NEW ORDERED %while find_next## nil %cycle %if find_next_area > area %then %exit find== find_next %repeat new_next== find_next find_next== new new_area= area new_dec index= dec index new_start= order %end !__________________________________________________________________________ %integerfn FIND AREA(%integer mark path) %integer i CLEAN CONSTRAINT GRAPH(no) i = LONGEST PATH(Xdir,yes,yes) { finds dec arc restricting CLEAN CONSTRAINT GRAPH(yes) %result= i * LONGEST PATH(Ydir,yes,yes) { compaction %end !__________________________________________________________________________ %ownintegerarray lpr(1:100,Xdir:Ydir) %owninteger next area1, next area2 !____________________________________________________________________________ %routine BRANCH and BOUND(%integer which graph,other path,level) %record(ORDERED) orderxx= 0 %record(ORDERED)%name ordering== orderxx %record(ORDERED)%name order is %integer Xpath length, Ypath length, lower bound, i, this area, found dec arc, order abort= yes %if abort= no %and testsymbol# -1 %if abort= no %start gotoXy(2,10) printstring(" level:: ");write(level,2) CLEAN CONSTRAINT GRAPH(no) %if which graph=xdir %start X path length = LONGEST PATH(Xdir,no,no) Y path length = other path %else Y path length = LONGEST PATH(Ydir,no,no) X path length = other path %finish lower bound= Xpath length * Y path length ! finds decs on lp %if lower bound < upper bound %start this area= FIND AREA(yes) gotoxy(17,17) printstring("This Level Area");write(this area,2) found dec arc = no lpr(i,Xdir)= dec arc(i,Xdir)_lp route %for i=1,1,dec count-1 lpr(i,Ydir)= dec arc(i,Ydir)_lp route %for i=1,1,dec count-1 %for i=1,1,dec count-1 %cycle %if (lpr(i,Xdir)=yes %or lpr(i,Ydir)= yes) %and %c dec arc(i,Xdir)_include=yes %and %c dec arc(i,Ydir)_include=yes %start found dec arc= yes dec arc(i,Xdir)_include= no next area1= FIND AREA(no) dec arc(i,Xdir)_include= yes dec arc(i,Ydir)_include= no next area2= FIND AREA(no) dec arc(i,Ydir)_include= yes %if next area1 < next area2 %start ADD ORDERED(ordering,i,next area1,Xdir) goto Xy(10,14) printstring("Next Level Option");write(next area1,2) %else ADD ORDERED(ordering,i,next area2,Ydir) gotoxy(10,14) printstring("Next Level Option");write(nextarea2,2) %finish %finish %repeat %if found dec arc= yes %start order is== ordering_next %while order is## nil %cycle %exit %if abort= yes i= order is_dec index order= order is_start dec arc(i,order)_include =no BRANCH and BOUND(xdir,Ypath length,level+1) dec arc(i,order)_include = yes %exit %if abort= yes dec arc(i,1-order)_include = no BRANCH and BOUND(Ydir,Xpath length,level+1) dec arc(i,1-order)_include = yes order is== order is_next %repeat %finish %if found dec arc =no %start {=> no more dec arc on longest paths i.e. { a (sub)optimal solution has been found %if this area < upper bound %start INDICATE SIZE(this area) %for i=1,1,dec count-1 %cycle optimal decisions(i) = dec arc(i,Xdir)_include %repeat %finish %finish %finish %else %start {calculate % rejected printstring(" rejected !") %finish %else DISPLAY("TERMINATING",mouse display x + 5,screen y + 44,yellow) %finish %end %routine initial heuristic %integer i,found dec arc %cycle ! finds decs on lp found dec arc = no CLEAN CONSTRAINT GRAPH(no) upper bound=LONGEST PATH(Xdir,yes,yes) CLEAN CONSTRAINT GRAPH(yes) i= LONGEST PATH(Ydir,yes,yes) upper bound= upper bound * i INDICATE SIZE(upper bound) %for i=1,1,dec count-1 %cycle %if dec arc(i,Xdir)_include= yes %and %c dec arc(i,Ydir)_include= yes %start %if dec arc(i,Xdir)_lp route= yes %and dec arc(i,Ydir)_lp route= yes %start %if dec arc(i,Xdir)_length > dec arc(i,Ydir)_length %start dec arc(i,Xdir)_include= no optimal decisions(i)= no %else dec arc(i,Ydir)_include= no optimal decisions(i)= yes %finish found dec arc= yes %finish %if dec arc(i,Xdir)_lp route=yes %and %c dec arc(i,Ydir)_lp route =no %start optimal decisions(i)= yes dec arc(i,Ydir)_include = no found dec arc =yes %finish %if dec arc(i,Xdir)_lp route= no %and %c dec arc(i,Ydir)_lp route= yes %start optimal decisions(i)= no dec arc(i,Xdir)_include =no found dec arc= yes %finish %finish %repeat %repeat %until found dec arc= no {removed all dec arc from longest path %for i=1,1,dec count-1 %cycle dec arc(i,Xdir)_include=yes dec arc(i,Ydir)_include= yes %repeat %end !_____________________________________________________________________________ %routine DO COMPILE %integer a %onevent(10) %Start CLEAN COMPARTMENTS CLEAN DATA(no) CLEAN DECS error count= yes %return %finish error count= 0 SPLIT and JOIN(no) EXAMINE CIRCUIT(poly and diff layers) EXAMINE CIRCUIT(metal layers) scan4 %end !___________________________________________________________________________ %routine COMPILE %integer a DO COMPILE %if error count= no %start compiled= yes OUT(".......OK!") DRAW(screen top) offset(0,-screen top) DRAW(0) offset(0,0) %else compiled= no %finish %end !____________________________________________________________________________ %routine COMPACT %integer a %if error count= 0 %and compiled= yes %start clearframe goto xy(12,2) printstring(" Compacting") goto xy(12,3) printstring(" ~~~~~~~~~~") goto xy(20,8) printstring("Hit Space Bar for Early Termination") optimal decisions(i)= not set %for i= 1,1,dec count-1 CHANGE TOGGLE(yes,yes,yes,"") DISPLAY("AREA>>",mouse display x-40,screen y + 10,white) DISPLAY("COMPACTING !",mouse display x + 10,screen y + 25,yellow) initial heuristic CLEAN CONSTRAINT GRAPH(no) a= testsymbol %until a= -1 branch and bound(Xdir,LONGEST PATH(ydir,no,no),0) USE OPTIMAL DECISIONS compacted= yes simple help %else OUT("Compaction cannot proceed until Compilation is successful") %finish change toggle(yes,yes,yes,"") set colour(black) FILL(mouse display x,screen y+40,mouse display x+120,screen y + 65) change toggle(no,no,no,"") %end %list %endoffile