%include "ilap.inc" {#######################################################################} {# #} {# This program is part of the ILAP library, and was written #} {# by Alex R. Deas, at the University of Edinburgh #} {# (James Clerk Maxwell Building, Kings Buildings, Edinburgh) #} {# #} {# This software is available free to other educational establisments #} {# but the U.K.A.E.A. A.E.R.E., Harwell owns all commercial rights. #} {# It is a condition of having this software is that the sources are #} {# not passed on to any other site, and that Edinburgh University, #} {# Alex Deas and U.K.A.E.A. is #} {# given credit in any re-implementations of any of the algorithms #} {# used, or articles published which refer to the software. #} {# #} {# There is no formal support for this software, but any bugs should #} {# be reported to Gordon Hughes or David Rees at the above address, #} {# and these are likely to be fixed in a future release. #} {# #} {#######################################################################} %const %integer invalid = -1 %const %integer clean = 1 %const %integer dirty = 2 %const %integer infinity = -10 %const %integer path spacing = 7 %const %string (4) invisible = "NON" %own %record (channel port) ref channel port = 0 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !! !! !! << C H A N N E L R O U T E R >> !! !! !! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !! !! !! << Diagnostics >> !! !! !! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! %string (5) %function sside(%integer side) ! converts the side integer to a string %result = "left" %if side = left %result = "right" %end %external %routine print port index backwards %alias "ILAP_CR_PPIB" (%record (channel port) %name ahead) ! a routine to print the given list in reverse order %record (channel port) %name posn == ahead %if (ahead == nil) %start PRINT STRING("Head is empty."); NEWLINE %return %finish %while (posn_next ## nil) %cycle posn == posn_next %repeat PRINT STRING("Going backwards we find:"); NEWLINE %while (posn ## nil) %cycle PRINT STRING("offset " . itos(posn_offset,0) . %c ", " . sside(posn_side) . " side,"); NEWLINE posn == posn_prev %repeat %end %external %routine print port index %alias "ILAP_CR_PPI" (%record (channel port) %name lhead) ! provides a minimal diagnostic by dumping the port index %record (channel port) %name f ptr == lhead {for from ports} %record (channel port) %name t ptr == nil {for to ports} %integer counter = 1 %routine print type(%record (channel port) %name ptr) ! prints what type a port is, start or end of a net %if (ptr_from == nil) %then %c PRINT STRING(" (start net)") %if (ptr_to == nil) %then %c PRINT STRING(" (end net)") %end %routine print mix(%string (31) a, %integer n, %string (31) c) PRINT STRING (a) WRITE (n, 2) PRINT STRING (c) %end print port index backwards(lhead) %if (lhead == nil) %then %return ! first to clear out any marks and print summary PRINT STRING("From the following ports:") NEWLINE %while (f ptr ## nil) %cycle f ptr_mark = clean ! first the from port PRINT STRING(" ") print mix ("With offset ", f ptr_offset, "") PRINT STRING (" on " . sside(f ptr_side) . " side,") PRINT STRING (" layer " . f ptr_layer . "") print type(f ptr) NEWLINE f ptr == f ptr_next %repeat NEWLINE PRINT STRING ("the port index builds:" ); NEWLINE f ptr == lhead %while (f ptr ## nil) %cycle %if (f ptr_mark = clean) %start ! first the from port print mix (" With offset ", f ptr_offset, "") PRINT STRING (" on " . sside(f ptr_side) . " side,") PRINT STRING (" layer " . f ptr_layer . ":") print type(f ptr) NEWLINE ! now the list of connected to ports t ptr == f ptr_to %while (t ptr ## nil) %cycle t ptr_mark = dirty PRINT STRING (" ") print mix ("- offset ", t ptr_offset, "") PRINT STRING (" on " . sside(t ptr_side) . " side,") PRINT STRING (" layer " . t ptr_layer . ";") print type(t ptr) NEWLINE t ptr == t ptr_to %repeat NEWLINE %finish f ptr == f ptr_next counter = counter + 1 %repeat %end !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !! !! !! << Declare port >> !! !! !! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! %external %record (channel port) %map declare port %alias "ILAP_CR_DEC_PORT" ( %c %string (31) name, {for diagnostic purposes} %c %integer fside, {from side, either left or right} %c foffset, {from offset} %c %string (4) flayer, {from layer} %c %integer tside, {to side} %c toffset, {to offset} %c %string (4) tlayer, {to layer} %c %record (channel port) %name %c in port list {the port list} ) ! adds a connection to the port network given !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !! !! !! << Create struct >> !! !! !! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! %record (channel port) %map %c if necessary create(%integer aside, aoffset, %string (4) alayer, %c %record (channel port) %name previous, present port) ! if port does not exist, adds a port, else does nothing but check %record (channel port) %map %c new port(%integer lside, loffset, %string (4) llayer, %c %record (channel port) %name prev port, next port) ! returns a new port filled with the given details %record (channel port) %name port port == new(ref channel port) port_side = lside port_offset = loffset port_layer = llayer port_track = invalid port_mark = clean port_from == nil port_to == nil port_prev == prev port port_next == next port %if (next port ## nil) %start next port_prev == port %finish %if (prev port ## nil) %start prev port_next == port %finish %result == port %end ! << main create >> %if (present port == nil) %then %c %result == new port(aside, aoffset, alayer, %c previous, present port) %if (aoffset < present port_offset) %then %c %result == new port(aside, aoffset, alayer, %c previous, present port) %if (aoffset = present port_offset) %start ! three possibilities %if (aside = present port_side) %then %c {port exists} %c %result == present port %if (aside = right) %start {aport is on right} present port_next == if necessary create(%c aside, aoffset, alayer, present port, present port_next) %result == present port %finish %if (aside = left) %then %c {port does not exist and is on left} %c %result == new port(aside, aoffset, alayer, %c previous, present port) %finish %if (aoffset > present port_offset) %start present port_next == if necessary create(aside, aoffset, alayer, %c present port, present port_next) %result == present port %finish ! should never get here disaster("Flow error in channel router_create ") %result == nil %end {of create} !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !! !! !! << Find elts in struct >> !! !! !! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! %record (channel port) %map %c find(%integer aside, aoffset, %string (4) alayer, %c %record (channel port) %name present port) ! returns a ptr to a port in the given port list with the ! attributes given, always an existing port. Ports should ! be inserted into the port list using "create" first. ! Recursive. %record (channel port) %map %c checked port(%string (4) player, %record (channel port) %name port) ! checks that the port you've found is the same as the port ! you've declared with regard to layer %if (player <> port_layer) %then {complain} %c warning("Layer contradictions exist in routing channel """.name."""") %result == port %end ! << main find >> %if (present port == nil) %then %c disaster ("Please report a code error in the channel router -". %c "CREATE called before FIND") %if (aoffset < present port_offset) %then %c disaster ("Please report a code error in the channel router ". %c "CREATE called before FIND") %if (aoffset = present port_offset) %start ! three possibilities %if (aside = present port_side) %then {port exists} %c %result == {the only correct recurse terminator condition} %c checked port(alayer, present port) %if (aside = left) %then {port does not exist} %c disaster ("Please report a code error in the channel router :". %c "CREATE called before FIND") %if (aside = right) %then %c {port is on right} %c %result == find(aside, aoffset, alayer, present port_next) %finish %if (aoffset > present port_offset) %then %c %result == find(aside, aoffset, alayer, present port_next) ! should never get here disaster("Flow error in channel router_find") %result == nil %end {of find} !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !! !! !! << fix up connections >> !! !! !! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! %routine fix up connections(%record (channel port) %name from, to) ! places the "to" port in the correct place in the "from" port's ! "to" list ! << fix in connection >> %record (channel port) %map %c fix in connection(%record (channel port) %name elt before list posn, %c list posn, insert) ! given the start connection, will put insert in the correct place ! in the related connection list. Recursive. ! << insert in >> %record (channel port) %map %c insert in(%record (channel port) %name elt before insert, %c elt in front of insert, insert) ! inserts a port before the elt in front of insert insert_to == elt in front of insert insert_from == elt before insert %if (elt before insert ## nil) %then %c elt before insert_to == insert %if (elt in front of insert ## nil) %then %c elt in front of insert_from == insert %result == insert %end %if (list posn == nil) %then {plonk insert on end of list} %c %result == insert in(elt before list posn, list posn, insert) %if (insert_offset < list posn_offset) %then {insert} %c %result == insert in(elt before list posn, list posn, insert) %if (insert_offset > list posn_offset) %start {recurse} list posn_to == fix in connection(list posn, %c list posn_to, insert) %result == list posn %finish %if (insert_offset = list posn_offset) %start ! left sides come before right sides %if (insert_side <> list posn_side) %start list posn_to == fix in connection(list posn, %c list posn_to, insert) %result == list posn %else %result == list posn {insert is already in place} %finish %finish ! should never get here disaster("Flow error in channel route_fix in connection") %result == nil %end ! << main of fix up connections >> %record (channel port) %name tr from == from %record (channel port) %name tr to == to %record (channel port) %name temp == nil ! first, travel backwards to end of lfrom %while (tr from_from ## nil) %cycle tr from == tr from_from %repeat ! do same for lto %while (tr to_from ## nil) %cycle tr to == tr to_from %repeat ! move each elt in "to" into "from" list %while (tr to ## nil) %cycle temp == tr to tr to == tr to_to temp_from == nil temp_to == nil tr from == fix in connection(nil, tr from, temp) %repeat %end { of fix up connections } !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !! !! !! << main of DECLARE PORT >> !! !! !! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! %record (channel port) %name from port == nil %record (channel port) %name to port == nil %record (channel port) %name temp ptr == nil in port list == if necessary create(fside, foffset, flayer, nil, %c in port list) in port list == if necessary create(tside, toffset, tlayer, nil, %c in port list) from port == find(fside, foffset, flayer, in port list) to port == find(tside, toffset, tlayer, in port list) fix up connections(from port, to port) %result == in port list %end {of declare port} !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !! !! !! << Check a port list for loop or DRC errors >> !! !! !! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! %external %routine check out port list %alias "ILAP_CR_COPL" (%record (channel port) %name head) ! Does a simple check to make sure there are no looped terminals %record (channel port) %name tptr == head %integer unroutable = FALSE ! travel down port list checking for loop errors tptr == head %while (tptr ## nil) %cycle ! first loop errors %if (tptr_to == tptr) %start warning("Offset position " . itos(tptr_offset,0) . " on " . %c sside(tptr_side) . " side is connected to itself.") unroutable = TRUE %finish tptr == tptr_next %repeat %if (unroutable = TRUE) %then %c disaster("In the presence of terminal loops the channel is unroutable.") %end !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !! !! !! << Channel Routing Algorithm. Mostly D. N. Deutsch, 13th D. A. Conf. >> !! !! !! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! %external %routine channelr %alias "ILAP_CR" (%string (31) name, %record (channel port) %name head, %integer min number of consecutive terminals) %record (channel port) %name terminal index == nil {unplaced terminals} %record (channel port) %name placed terminal list == nil %record (channel port) %name start terminal == nil %record (channel port) %name intermediate terminal == nil %record (channel port) %name end terminal == nil %record (channel port) %name temp index == nil %integer number of consecutive terminals = 0 %integer filled = FALSE {set to TRUE if any terminals are placed} %integer extend = 0 {set to 1 if layer problems are encountered} %integer track = 0 %integer %function gap(%string (4) layera, layerb) ! returns the minimum spacing between layers a and b %result = 3 %if (layera = metal) %and (layerb = metal) %result = 1 %if (layera = metal) %and (layerb = poly) %result = 0 %if (layera = metal) %and (layerb = diffusion) %result = 1 %if (layera = poly) %and (layerb = metal) %result = 2 %if (layera = poly) %and (layerb = poly) %result = 1 %if (layera = poly) %and (layerb = diffusion) %result = 0 %if (layera = diffusion) %and (layerb = metal) %result = 1 %if (layera = diffusion) %and (layerb = poly) %result = 3 %if (layera = diffusion) %and (layerb = diffusion) %result = 0 {otherwise} %end ! << constrained >> %predicate constrained(%record (channel port) %name present term) ! returns true if the given terminal is vertically constrained ! deal with terminals on left side %if (present term_side = left) %and ( %c (placed terminal list == nil) %or %c (present term_offset >= placed terminal list_offset + %c gap(metal, metal)+4) %or %c (present term_offset <= placed terminal list_offset - %c gap(metal, metal)-4) ) %c %then %false ! deal with terminals on right side %if (present term_side = right) %and ( %c (present term_prev == nil) %or %c (present term_prev == present term_from) %or %c (present term_offset >= present term_prev_offset+ %c gap(metal, metal)+4) %or %c (present term_offset <= present term_prev_offset- %c gap(metal, metal)-4)) %c %then %false %true %end ! << delete from unplaced terminal list >> %record (channel port) %map %c delete from unplaced terminal list( %c %record (channel port) %name elt, lhead) ! deletes elt from wherever it is and puts it onto the placed terminal list. ! take elt out of from/to list %if (elt_from ## nil) %then %c elt_from_to == elt_to %if (elt_to ## nil) %then %c elt_to_from == elt_from elt_to == nil elt_from == nil %if (elt_prev == nil) %and (lhead ## elt) %then %c disaster("List links are confused in channel router") ! copy over prev/next elt_next_prev == elt_prev %if (elt_next ## nil) elt_prev_next == elt_next %if (elt_prev ## nil) %if (lhead == elt) %start lhead == elt_next %finish elt_prev == nil elt_next == placed terminal list placed terminal list == elt %result == lhead %end ! << delete all terminals between >> %record (channel port) %map %c delete all terminals between(%record (channel port) %name %c start, end, lhead) ! gets rid of intermediate terminals %record (channel port) %name ltptr == start %record (channel port) %name ltemp == nil %if (start == nil) %start disaster("Peculiar behaviour in channel router ") %result == nil %else ltptr == ltptr_to %finish %while (ltptr ## nil) %and %c (ltptr ## end) %cycle ltemp == ltptr_to lhead == delete from unplaced terminal list(ltptr, lhead) ltptr == ltemp %repeat %result == lhead %end ! << assign from >> %routine %c assign from(%record (channel port) %name start, end, %integer track) ! does the vertical tracks %record (channel port) %name current terminal == start %while (current terminal ## end) %cycle %if (current terminal_layer = poly) %then %c PM(5 + track * path spacing, current terminal_offset + 1) %if (current terminal_layer = diffusion) %then %c DM(5 + track * path spacing, current terminal_offset + 1) ! all empty layer terminals get ignored ! allocate track numbers so that doglegs are wired %if (current terminal_side = right) %start %if (current terminal_track = invalid) %then %c current terminal_track = track %else current terminal_track = track %finish current terminal == current terminal_to %repeat ! now put on end terminal %if (current terminal_layer = poly) %then %c PM(5 + track * path spacing, current terminal_offset + 1) %if (current terminal_layer = diffusion) %then %c DM(5 + track * path spacing, current terminal_offset + 1) %if (current terminal_side = right) %start %if (current terminal_track = invalid) %then %c current terminal_track = track %else current terminal_track = track %finish LAYER(metal) WIDTH(4) WIREY(3 + track * path spacing, start_offset, %c end_offset - start_offset) %end ! << wire up horizontal tracks from >> %routine %c wire up horizontal tracks from(%record (channel port) %name terminal list, %c %integer max track) %record (channel port) %name tptr == terminal list %while (tptr ## nil) %cycle %if (tptr_layer <> invisible) %start LAYER(tptr_layer) %if (tptr_mark = dirty) %start %if (tptr_side = left) %start WIREX(0, tptr_offset, path spacing * (max track + 1)) %else %if (tptr_layer = poly) %start PDCE(3 + path spacing *(max track + 1) - 2, %c tptr_offset + extend) %else PDCW(3 + path spacing *(max track + 1) - 1, %c tptr_offset + extend) %finish %finish %else %if (tptr_track = infinity) %start WIREX(0, tptr_offset, 3 + path spacing * (max track + 1) +%c extend) %else %if (tptr_side = left) %then %c WIREX(0, tptr_offset, 3 + tptr_track * path spacing + %c extend) %c %else %c WIREX(3 + tptr_track * path spacing, tptr_offset, %c (max track - tptr_track + 1)*path spacing + extend) %finish %finish %finish tptr == tptr_next %repeat %end ! << remove multiply defined ports from >> %record (channel port) %map %c remove multiply defined ports from(%record (channel port) %name lhead) ! goes down head, and where it finds a left hand port, it tests to ! see if there is also a right hand port connected to the left side. ! If the left port is the start of a net and the right port is the ! end, then both are deleted, else only the right. %record (channel port) %name tptr == lhead %record (channel port) %name temp == nil %record (channel port) %name left term == nil %record (channel port) %name right term == nil ! first clean out any marks %while (tptr ## nil) %cycle tptr_mark = clean tptr == tptr_next %repeat tptr == lhead %while (tptr ## nil) %cycle %if (tptr_side = left) %and %c (tptr_next ## nil) %and %c (tptr_next == tptr_to) %and %c (tptr_offset = tptr_next_offset) %start ! check for problems in layers %if (tptr_layer <> tptr_next_layer) %start extend = 1 tptr_mark = dirty tptr_next_mark = dirty tptr_next_layer = tptr_layer %finish ! we have a straight thro' horizontal wire left term == tptr right term == left term_to temp == tptr_next_next right term_from == nil %if (left term_from == nil) ! if right terminal is end of list, delete it %if (right term_to == nil) %start right term_track = infinity lhead == delete from unplaced terminal list %c (right term, lhead) left term_to == nil %finish ! delete left terminal left term_track = infinity lhead == delete from unplaced terminal list(left term, lhead) tptr == temp %else {consider next terminal} tptr == tptr_next %finish %repeat %result == lhead %end ! ! << main algorithm >> ! SYMBOL(name) check out port list(head) head == remove multiply defined ports from(head) ! 1: inits %if (min number of consecutive terminals < 3) %then %c min number of consecutive terminals = 3 filled = FALSE terminal index == head temp index == head track = 0 ! 2: %while (head ## nil) %cycle ! grab the next terminal and use it as the start %if (terminal index == nil) %start terminal index == head track = track + 1 ! check for unroutable cyclic constraint %if (filled = FALSE) %start warning("Total cyclic constraints exist. " . %c " Dump of constrained terminals follows:") print port index(head) warning("In the presence of totally constrained " . %c "terminals, the channel is unroutable.") head == nil %continue %finish filled = FALSE %else %if (temp index == nil) %then %c terminal index == terminal index_next %c %else %c terminal index == temp index %if (terminal index == nil) %then %c %continue %finish start terminal == terminal index temp index == nil ! 3: ! if start terminal constrained reject it and get another %if (constrained (start terminal)) %then %c %continue ! 4: number of consecutive terminals = 1 intermediate terminal == start terminal %while (intermediate terminal_to ## nil) %and %c (%not(constrained (intermediate terminal_to))) %cycle intermediate terminal == intermediate terminal_to number of consecutive terminals = %c number of consecutive terminals + 1 %repeat ! now terminal = end terminal for the current subnet end terminal == intermediate terminal %if (start terminal == end terminal) %then %continue ! 6: %if (min number of consecutive terminals > 2) %start %if (number of consecutive terminals {in subnet} < %c min number of consecutive terminals) %and %c ((start terminal_from ## nil) %or %c (end terminal_to ## nil)) %then %c %continue %finish ! 7: assign from(start terminal, {to} end terminal, {to} track) temp index == end terminal_next ! make sure you move onto a different offset) %if (temp index ## nil) %and %c (temp index_offset = end terminal_offset) %then %c temp index == temp index_next terminal index == temp index ! 8: filled = TRUE head == delete all terminals between(start terminal, %c end terminal, head) %if (start terminal_from == nil) %start head == delete from unplaced terminal list(start terminal, head) start terminal == nil %else ! turn start terminal into an end terminal start terminal_to == nil %finish %if (end terminal_to == nil) %start head == delete from unplaced terminal list(end terminal, head) end terminal == nil %else ! turn end terminal into a start terminal end terminal_from == nil %finish %repeat wire up horizontal tracks from (placed terminal list, track) ENDSYMBOL %end %endoffile