• Next message: Joe Guest: "Esim and Crystal"
• Previous message: Andrew Lines: "Magic select bug -- and proposed (fairly tricky) fix."
• In reply to: Andrew Lines: "Magic select bug -- and proposed (fairly tricky) fix."
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

Andrew Lines writes:
 > This is a multi-part message in MIME format.
 > --------------47273CA1EE5B5A355250B474
 > Content-Type: text/plain; charset=us-ascii
 > Content-Transfer-Encoding: 7bit
 > 
 > We've been using "half-generic" contacts for a while now.   We even
 > taped out a 650,000 transistor test chip with them.  These contacts are
 > simply "paint" that lives in one plane and has electrical connectivity
 > to the plane above.  Unlike Magic's actual contacts, they can be
 > arbitrarily stacked.  They are somewhat harder to edit, as the top metal
 > layer is not strictly associated with the contact, but merely caps it.
 > This is similar to the MOSIS generic contacts, but at least they plow
 > and interact nicely in the lower plane.
 > 
 > However, this approach has lead me to discover a very obscure bug in
 > Magic, probably one which nobody else has ever seen.  The bug is in
 > DBconnect.c, which recursively selects electrically connected tiles and
 > copies them to a destination buffer.  The non-heirarchical algorithm,
 > DBSrConnect, uses two passes with a mark and clear algorithm to avoid
 > infinite loops in circular connections.  So does the extractor
 > (I hope...).
 > 
 > However, the heirarchical select, DBTreeCopyConnect, uses a one-pass
 > algorithm which performs a rather tricky and convoluted test to decide
 > when to terminate the recursive search.  Given the current tile, it
 > checks the destination buffer to see if there is already connected paint
 > in the same plane as the tile which completely covers the area of the
 > tile.  If so, it assumes all connected stuff from there on has already
 > been handled.  There is special case code which checks that if the tile
 > is a contact, the destination buffer is already painted with the image
 > of that contact (not just electrically connected material in the same
 > plane).
 > 
 > Therin lies the problem.  With the half-generic contacts, the special
 > case code isn't triggered, so Magic might see that the area is already
 > covered by m2, paint an m3c on top of it, and terminate the recursion.
 > It fails to reach any m3 connected to the m3c.  The MOSIS generic
 > contacts aren't affected by the bug because they lie on their own
 > planes.
 > 
 > OK, so how do I fix this?
 > 
 > 1) A simple mark and clear algorithm won't work well, because the same
 > tiles may be used in different subcells.  (I tried this and it won't
 > work).
 > 
 > 2) Storing all visited subcell/tile pairs and searching for every new
 > tile would be slow, even if we kept a sorted set.  And it wastes memory.
 > 
 > 3) I could declare these half-generic contacts as a new type of
 > "contact" which would trigger the special case code.  This is pretty
 > silly, considering you could still screw this up in the techfile.

actually i'd go for this approach, since you can easily infer the new
type of contact without it being in the 'contact' section, since it's
in the 'connect' section and the layers it connects reside in >1
planes, thus it's a 'half-generic contact', and can then invoke the
contact special case code.

 > 
 > 4) Use a more sophisticated test for termination.  It should terminate
 > the recursive search if and only if painting the new tile is vacuous.
 > This of course relies on the compose rules, so that you can declare a
 > rule like "paint m2 m3c m3c" and have it figure things out.

i'm not sure this type of paint command should always indicate a
'half-generic' contact.

 > 
 > So if I try approach 4, does anybody have a good suggestion on how to
 > paint a new rectangle and return an indication of wheather the data
 > structure was actually modified?  This would be the best all around
 > solution, avoiding both the special case contact code and fixing the
 > bug.
 > 
 > 
 > --------------47273CA1EE5B5A355250B474
 > Content-Type: text/x-vcard; charset=us-ascii;
 >  name="lines.vcf"
 > Content-Transfer-Encoding: 7bit
 > Content-Description: Card for Andrew Lines
 > Content-Disposition: attachment;
 >  filename="lines.vcf"
 > 
 > begin:vcard 
 > n:Lines;Andrew
 > tel;fax:(626) 844-2951
 > tel;home:(626) 568-4928
 > tel;work:(626) 844-2941
 > x-mozilla-html:FALSE
 > url:www.avlsi.com
 > org:Asynchronous Digital Design Inc.
 > adr:;;1010 E. Union #202;Pasadena;CA;91106;USA
 > version:2.1
 > email;internet:lines AT avlsi DOT com
 > title:Founder
 > x-mozilla-cpt:;11936
 > fn:Andrew Lines
 > end:vcard
 > 
 > --------------47273CA1EE5B5A355250B474--

• Next message: Joe Guest: "Esim and Crystal"
• Previous message: Andrew Lines: "Magic select bug -- and proposed (fairly tricky) fix."
• In reply to: Andrew Lines: "Magic select bug -- and proposed (fairly tricky) fix."
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]