mirror of
https://github.com/RTimothyEdwards/magic.git
synced 2026-09-04 08:33:55 +02:00
R. Timothy Edwards
21b8579734
one place as ohms and another as milliohms. Changed it to be milliohms always, except when written as output to the lumped resistance file or as diagnostic output. The result makes more sense, but now has the issue that the maximum resistance is always an over-estimate and may need to account for resistances in parallel.
1193 lines
33 KiB
C
1193 lines
33 KiB
C
/*
|
|
*-------------------------------------------------------------------------
|
|
*
|
|
* ResSimplify -- contains routines used to simplify signal nets.
|
|
*
|
|
*
|
|
*
|
|
*-------------------------------------------------------------------------
|
|
*/
|
|
|
|
#ifndef lint
|
|
static char rcsid[] __attribute__ ((unused)) = "$Header: /usr/cvsroot/magic-8.0/resis/ResSimple.c,v 1.1.1.1 2008/02/03 20:43:50 tim Exp $";
|
|
#endif /* not lint */
|
|
#include <stdio.h>
|
|
#include <stdlib.h> /* for qsort() */
|
|
#include <string.h>
|
|
#include <ctype.h>
|
|
#include <math.h>
|
|
|
|
#include "utils/magic.h"
|
|
#include "utils/geometry.h"
|
|
#include "utils/geofast.h"
|
|
#include "tiles/tile.h"
|
|
#include "utils/hash.h"
|
|
#include "utils/heap.h"
|
|
#include "database/database.h"
|
|
#include "utils/malloc.h"
|
|
#include "textio/textio.h"
|
|
#include "extract/extract.h"
|
|
#include "extract/extractInt.h"
|
|
#include "windows/windows.h"
|
|
#include "dbwind/dbwind.h"
|
|
#include "utils/stack.h"
|
|
#include "utils/tech.h"
|
|
#include "textio/txcommands.h"
|
|
#include "resis/resis.h"
|
|
|
|
#define MILLIOHMSPEROHM 1000
|
|
|
|
/* Forward declarations */
|
|
void ResSetPathRes();
|
|
void resPathNode();
|
|
void resPathRes();
|
|
Heap ResistorHeap;
|
|
|
|
/* Forward declarations */
|
|
|
|
extern void ResMoveDevices();
|
|
extern void ResAddResistorToList();
|
|
|
|
/*
|
|
*-------------------------------------------------------------------------
|
|
*
|
|
* ResSimplifyNet- Reduces complete (?) net produced by ResProcessTiles into
|
|
* something a little less chaotic.
|
|
*
|
|
* Results: none
|
|
*
|
|
* Side Effects: Can eliminate nodes and resistors, and move devices from
|
|
* one node to another.
|
|
*
|
|
*-------------------------------------------------------------------------
|
|
*/
|
|
|
|
void
|
|
ResSimplifyNet(nodelist, biglist, reslist, tolerance)
|
|
resNode **nodelist, **biglist;
|
|
resResistor **reslist;
|
|
float tolerance;
|
|
|
|
{
|
|
resElement *resisptr;
|
|
resNode *node, *otherNode, *node1, *node2;
|
|
resResistor *resistor1 = NULL, *resistor2 = NULL;
|
|
int numdrive = 0, numreceive = 0;
|
|
int MarkedReceivers, UnMarkedReceivers;
|
|
int NumberOfDrivers, PendingReceivers;
|
|
|
|
if (*nodelist == NULL) return;
|
|
node = *nodelist;
|
|
node->rn_status |= RES_MARKED | RES_FINISHED;
|
|
*nodelist = node->rn_more;
|
|
if (node->rn_more != NULL)
|
|
node->rn_more->rn_less = (resNode *) NULL;
|
|
|
|
node->rn_more = *biglist;
|
|
if (*biglist != (resNode *) NULL)
|
|
(*biglist)->rn_less = node;
|
|
|
|
*biglist = node;
|
|
|
|
/*
|
|
* Walk though resistors. Mark uninitialized ones and assign them
|
|
* a direction. Keep track of the number of resistors pointing in
|
|
* each direction.
|
|
*/
|
|
for (resisptr = node->rn_re; resisptr != NULL; resisptr = resisptr->re_nextEl)
|
|
{
|
|
if (((resisptr->re_thisEl->rr_status & RES_MARKED) == RES_MARKED) &&
|
|
(resisptr->re_thisEl->rr_connection2 == node))
|
|
{
|
|
if (resistor1 == NULL)
|
|
resistor1 = resisptr->re_thisEl;
|
|
else
|
|
resistor2 = resisptr->re_thisEl;
|
|
|
|
numdrive++;
|
|
}
|
|
else
|
|
{
|
|
/*
|
|
* Resistor direction is from node1 to node2. If the resistor
|
|
* is not marked, mark it and make sure the direction is
|
|
* set properly.
|
|
*/
|
|
|
|
if ((resisptr->re_thisEl->rr_status & RES_MARKED) != RES_MARKED)
|
|
{
|
|
if (resisptr->re_thisEl->rr_connection2 == node)
|
|
{
|
|
resisptr->re_thisEl->rr_connection2 =
|
|
resisptr->re_thisEl->rr_connection1;
|
|
resisptr->re_thisEl->rr_connection1 = node;
|
|
}
|
|
resisptr->re_thisEl->rr_status |= RES_MARKED;
|
|
}
|
|
if (resistor1 == NULL)
|
|
resistor1 = resisptr->re_thisEl;
|
|
else
|
|
resistor2 = resisptr->re_thisEl;
|
|
|
|
numreceive++;
|
|
}
|
|
}
|
|
|
|
/*
|
|
* Is the node reached by one resistor? If it is, check the resistor's
|
|
* other end. Check the number of drivers at the other end. If it is
|
|
* more than 1, delete the current resistor to break the deadlock.
|
|
*/
|
|
|
|
if (numreceive == 0 && numdrive == 1 &&
|
|
!(node->rn_why & (RES_NODE_ORIGIN | RES_NODE_SINK)))
|
|
{
|
|
resistor1->rr_status |= RES_DEADEND;
|
|
if (resistor1->rr_value < tolerance)
|
|
{
|
|
otherNode = (resistor1->rr_connection1 == node) ?
|
|
resistor1->rr_connection2 : resistor1->rr_connection1;
|
|
MarkedReceivers = 0;
|
|
UnMarkedReceivers = 0;
|
|
NumberOfDrivers = 0;
|
|
PendingReceivers = 0;
|
|
resistor2 = resistor1;
|
|
for (resisptr = otherNode->rn_re; resisptr != NULL;
|
|
resisptr = resisptr->re_nextEl)
|
|
{
|
|
if (resisptr->re_thisEl->rr_connection1 == otherNode)
|
|
{
|
|
if ((resisptr->re_thisEl->rr_connection2->rn_status & RES_MARKED)
|
|
!= RES_MARKED)
|
|
{
|
|
PendingReceivers++;
|
|
}
|
|
if (resisptr->re_thisEl->rr_status & RES_DEADEND ||
|
|
resisptr->re_thisEl->rr_value > tolerance)
|
|
{
|
|
MarkedReceivers++;
|
|
resistor2 = (resisptr->re_thisEl->rr_value >=
|
|
resistor2->rr_value) ? resisptr->re_thisEl : resistor2;
|
|
}
|
|
else
|
|
UnMarkedReceivers++;
|
|
}
|
|
else
|
|
NumberOfDrivers++;
|
|
}
|
|
/* other recievers at far end? If so, reschedule other node;
|
|
* deadlock will be settled from that node.
|
|
*/
|
|
if ((MarkedReceivers + UnMarkedReceivers + NumberOfDrivers == 2) ||
|
|
(UnMarkedReceivers == 0 && MarkedReceivers > 1 &&
|
|
resistor2 == resistor1 && PendingReceivers == 0))
|
|
{
|
|
if (otherNode->rn_status & RES_MARKED)
|
|
{
|
|
otherNode->rn_status &= ~RES_MARKED;
|
|
ResRemoveFromQueue(otherNode, biglist);
|
|
otherNode->rn_less = NULL;
|
|
otherNode->rn_more = *nodelist;
|
|
if (*nodelist != NULL)
|
|
(*nodelist)->rn_less = otherNode;
|
|
|
|
*nodelist = otherNode;
|
|
}
|
|
return;
|
|
}
|
|
|
|
/*
|
|
* Break loop here. More than one driver indicates a loop;
|
|
* remove deadend, allowing drivers to be merged
|
|
*/
|
|
else if (UnMarkedReceivers == 0 && ((MarkedReceivers == 1 &&
|
|
NumberOfDrivers > 1) || resistor2 != resistor1))
|
|
|
|
{
|
|
otherNode->rn_float.rn_area += resistor1->rr_float.rr_area;
|
|
otherNode->rn_status &= ~RES_DONE_ONCE;
|
|
ResDeleteResPointer(resistor1->rr_connection1, resistor1);
|
|
ResDeleteResPointer(resistor1->rr_connection2, resistor1);
|
|
ResEliminateResistor(resistor1, reslist);
|
|
ResMergeNodes(otherNode, node, nodelist, biglist);
|
|
if (otherNode->rn_status & RES_MARKED)
|
|
{
|
|
otherNode->rn_status &= ~RES_MARKED;
|
|
ResRemoveFromQueue(otherNode, biglist);
|
|
otherNode->rn_less= NULL;
|
|
otherNode->rn_more = *nodelist;
|
|
if (*nodelist != NULL)
|
|
(*nodelist)->rn_less = otherNode;
|
|
|
|
*nodelist = otherNode;
|
|
}
|
|
ResDoneWithNode(otherNode);
|
|
}
|
|
}
|
|
}
|
|
/*
|
|
* Two resistors in series? Combine them and move devices to
|
|
* appropriate end.
|
|
*/
|
|
else if (numdrive + numreceive == 2 && (resistor1->rr_value < tolerance &&
|
|
resistor2->rr_value < tolerance))
|
|
{
|
|
if ((resistor1->rr_status & RES_MARKED) == 0 &&
|
|
(resistor1->rr_connection2 == node))
|
|
{
|
|
resistor1->rr_connection2 = resistor1->rr_connection1;
|
|
resistor1->rr_connection1 = node;
|
|
}
|
|
resistor1->rr_status |= RES_MARKED;
|
|
if ((resistor2->rr_status & RES_MARKED) == 0 &&
|
|
(resistor2->rr_connection2 == node))
|
|
{
|
|
resistor2->rr_connection2 = resistor2->rr_connection1;
|
|
resistor2->rr_connection1 = node;
|
|
}
|
|
resistor2->rr_status |= RES_MARKED;
|
|
node1 = (resistor1->rr_connection1 == node) ? resistor1->rr_connection2 :
|
|
resistor1->rr_connection1;
|
|
node2 = (resistor2->rr_connection1 == node) ? resistor2->rr_connection2 :
|
|
resistor2->rr_connection1;
|
|
otherNode = (resistor1->rr_status & RES_DEADEND &&
|
|
resistor1->rr_value < tolerance / 2) ||
|
|
((resistor2->rr_status & RES_DEADEND) == 0 &&
|
|
resistor1->rr_value < resistor2->rr_value) ? node1 : node2;
|
|
/*
|
|
* Make one big resistor out of two little ones, eliminating
|
|
* the current node. Devices connected to this node are
|
|
* moved to either end depending on their resistance.
|
|
*/
|
|
ResMoveDevices(node,otherNode);
|
|
otherNode->rn_noderes = MIN(node->rn_noderes, otherNode->rn_noderes);
|
|
node2->rn_float.rn_area += resistor1->rr_value * node->rn_float.rn_area /
|
|
(resistor1->rr_value + resistor2->rr_value);
|
|
node1->rn_float.rn_area += resistor2->rr_value * node->rn_float.rn_area /
|
|
(resistor1->rr_value + resistor2->rr_value);
|
|
resistor1->rr_value += resistor2->rr_value;
|
|
resistor1->rr_float.rr_area +=resistor2->rr_float.rr_area;
|
|
if (resistor1 == *reslist)
|
|
*reslist = resistor1->rr_nextResistor;
|
|
else
|
|
resistor1->rr_lastResistor->rr_nextResistor = resistor1->rr_nextResistor;
|
|
|
|
if (resistor1->rr_nextResistor != NULL)
|
|
resistor1->rr_nextResistor->rr_lastResistor = resistor1->rr_lastResistor;
|
|
|
|
ResAddResistorToList(resistor1, reslist);
|
|
ResDeleteResPointer(node, resistor1);
|
|
ResDeleteResPointer(node, resistor2);
|
|
ResDeleteResPointer(node2, resistor2);
|
|
if (resistor1->rr_connection1 == node)
|
|
resistor1->rr_connection1 = node2;
|
|
else
|
|
resistor1->rr_connection2 = node2;
|
|
|
|
resisptr = (resElement *)mallocMagic((unsigned)(sizeof(resElement)));
|
|
resisptr->re_thisEl = resistor1;
|
|
resisptr->re_nextEl = node2->rn_re;
|
|
node2->rn_re = resisptr;
|
|
ResEliminateResistor(resistor2, reslist);
|
|
otherNode->rn_status |= (node->rn_status & RES_MAXTDI);
|
|
ResCleanNode(node, TRUE, biglist, nodelist);
|
|
node1->rn_status &= ~RES_DONE_ONCE;
|
|
if (node1->rn_status & RES_MARKED)
|
|
{
|
|
node1->rn_status &= ~RES_MARKED;
|
|
ResRemoveFromQueue(node1, biglist);
|
|
node1->rn_less = NULL;
|
|
node1->rn_more = *nodelist;
|
|
if (*nodelist != NULL)
|
|
(*nodelist)->rn_less = node1;
|
|
*nodelist = node1;
|
|
}
|
|
node2->rn_status &= ~RES_DONE_ONCE;
|
|
if (node2->rn_status & RES_MARKED)
|
|
{
|
|
node2->rn_status &= ~RES_MARKED;
|
|
ResRemoveFromQueue(node2, biglist);
|
|
node2->rn_less = NULL;
|
|
node2->rn_more = *nodelist;
|
|
if (*nodelist != NULL)
|
|
(*nodelist)->rn_less = node2;
|
|
*nodelist = node2;
|
|
}
|
|
ResDoneWithNode(node1);
|
|
}
|
|
|
|
/*
|
|
* Last resort- keep propagating down the tree. To avoid looping,
|
|
* mark each node when it is reached. Don't reschedule node if
|
|
* none of the connections to it have changed since it was marked
|
|
*/
|
|
else if (numreceive > 0 && (node->rn_status & RES_DONE_ONCE) == 0)
|
|
{
|
|
node->rn_status |= RES_DONE_ONCE;
|
|
for (resisptr = node->rn_re; resisptr != NULL; resisptr = resisptr->re_nextEl)
|
|
{
|
|
if (resisptr->re_thisEl->rr_connection1 == node)
|
|
{
|
|
/*
|
|
* Elements with a resistance greater than the
|
|
* tolerance should only be propagated past once-
|
|
* loops may occur otherwise.
|
|
*/
|
|
if (resisptr->re_thisEl->rr_status & RES_DONE_ONCE)
|
|
continue;
|
|
|
|
if (resisptr->re_thisEl->rr_connection2->rn_status & RES_MARKED)
|
|
{
|
|
/*
|
|
* Mark big resistors so we only process them
|
|
* once.
|
|
*/
|
|
if (resisptr->re_thisEl->rr_value > tolerance)
|
|
resisptr->re_thisEl->rr_status |= RES_DONE_ONCE;
|
|
|
|
resisptr->re_thisEl->rr_connection2->rn_status &= ~RES_MARKED;
|
|
ResRemoveFromQueue(resisptr->re_thisEl->rr_connection2, biglist);
|
|
resisptr->re_thisEl->rr_connection2->rn_less= NULL;
|
|
resisptr->re_thisEl->rr_connection2->rn_more = *nodelist;
|
|
if (*nodelist != NULL)
|
|
(*nodelist)->rn_less = resisptr->re_thisEl->rr_connection2;
|
|
|
|
*nodelist = resisptr->re_thisEl->rr_connection2;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
/*
|
|
*-------------------------------------------------------------------------
|
|
*
|
|
* ResMoveDevices-- move devices from one node (node1) to anther (node2)
|
|
*
|
|
* Results: none
|
|
*
|
|
* Side Effects: Changes device connections and node tElements.
|
|
*
|
|
*-------------------------------------------------------------------------
|
|
*/
|
|
|
|
void
|
|
ResMoveDevices(node1, node2)
|
|
resNode *node1, *node2;
|
|
|
|
{
|
|
tElement *devptr, *oldptr;
|
|
resDevice *device;
|
|
|
|
devptr = node1->rn_te;
|
|
while (devptr != NULL)
|
|
{
|
|
device = devptr->te_thist;
|
|
oldptr = devptr;
|
|
devptr = devptr->te_nextt;
|
|
if (device->rd_fet_gate == node1)
|
|
device->rd_fet_gate = node2;
|
|
else if (device->rd_fet_subs == node1)
|
|
device->rd_fet_subs = node2;
|
|
else if ((device->rd_nterms > 2) && (device->rd_fet_source == node1))
|
|
device->rd_fet_source = node2;
|
|
else if ((device->rd_nterms > 3) && (device->rd_fet_drain == node1))
|
|
device->rd_fet_drain = node2;
|
|
else
|
|
TxError("Missing Device connection in squish routines"
|
|
" at %d, %d\n", node1->rn_loc.p_x, node1->rn_loc.p_y);
|
|
oldptr->te_nextt = node2->rn_te;
|
|
node2->rn_te = oldptr;
|
|
}
|
|
node1->rn_te = NULL;
|
|
}
|
|
|
|
/*
|
|
*-------------------------------------------------------------------------
|
|
*
|
|
* qrescompare ---
|
|
*
|
|
* Sort routine for qsort() to be used by ResScrunchNet(). Sorts in
|
|
* order of the resistor value, smallest to largest.
|
|
*-------------------------------------------------------------------------
|
|
*/
|
|
|
|
int
|
|
qrescompare(const void *one, const void *two)
|
|
{
|
|
int cval;
|
|
|
|
resResistor *r1 = *((resResistor **)one);
|
|
resResistor *r2 = *((resResistor **)two);
|
|
|
|
if (r1->rr_value < r2->rr_value) return -1;
|
|
else if (r1->rr_value == r2->rr_value) return 0;
|
|
else return 1;
|
|
}
|
|
|
|
/*
|
|
*-------------------------------------------------------------------------
|
|
*
|
|
* ResScrunchNet-- Last ditch net simplification. Used to break deadlocks
|
|
* in ResSimplifyNet. Resistors are sorted by value. The smallest
|
|
* resistor is combined with its smallest neighbor, and ResSimplifyNet
|
|
* is called. This continues until the smallest resistor is greater
|
|
* than the tolerance.
|
|
*
|
|
* Results:none
|
|
*
|
|
* Side Effects: Nodes and resistors are eliminated.
|
|
*
|
|
*-------------------------------------------------------------------------
|
|
*/
|
|
|
|
void
|
|
ResScrunchNet(reslist, pendingList, biglist, tolerance)
|
|
resResistor **reslist;
|
|
resNode **pendingList, **biglist;
|
|
float tolerance;
|
|
|
|
{
|
|
resResistor *current, *working;
|
|
resNode *node1, *node2;
|
|
resElement *rcell1;
|
|
int c1, c2, count = 0;
|
|
|
|
/* Method used to sort resistors by size depends on list length */
|
|
for (current = *reslist; current; current = current->rr_nextResistor)
|
|
{
|
|
count++;
|
|
if (count >= 10) break;
|
|
}
|
|
|
|
/* Sort resistors by size */
|
|
|
|
if (count >= 10)
|
|
{
|
|
int i;
|
|
resResistor **resSortList;
|
|
|
|
/* For long lists, sort using qsort() */
|
|
/* NOTE: It might be better to use the same merge sort used for
|
|
* MergeSortBreaks() in ResMakeRes.c, as it does not incur the
|
|
* overhead of allocating memory and populating the array.
|
|
*/
|
|
count = 0;
|
|
for (current = *reslist; current; current = current->rr_nextResistor)
|
|
count++;
|
|
|
|
resSortList = (resResistor **)mallocMagic(count * sizeof(resResistor *));
|
|
|
|
count = 0;
|
|
for (current = *reslist; current; current = current->rr_nextResistor)
|
|
{
|
|
resSortList[count] = current;
|
|
count++;
|
|
}
|
|
|
|
/* Sort the list */
|
|
|
|
qsort(resSortList, count, sizeof(resResistor *), qrescompare);
|
|
|
|
/* Regenerate links on sorted list */
|
|
for (i = 0; i < count; i++)
|
|
{
|
|
current = resSortList[i];
|
|
current->rr_nextResistor = (i == count - 1) ? NULL : resSortList[i + 1];
|
|
current->rr_lastResistor = (i == 0) ? NULL : resSortList[i - 1];
|
|
}
|
|
*reslist = resSortList[0];
|
|
|
|
freeMagic(resSortList);
|
|
}
|
|
else
|
|
{
|
|
/* Original method: Walk the linked list and re-sort by size. */
|
|
|
|
resResistor *locallist = NULL;
|
|
|
|
current = *reslist;
|
|
while (current != NULL)
|
|
{
|
|
working = current;
|
|
current = current->rr_nextResistor;
|
|
if (working == *reslist)
|
|
*reslist = current;
|
|
else
|
|
working->rr_lastResistor->rr_nextResistor = current;
|
|
|
|
if (current != NULL)
|
|
current->rr_lastResistor = working->rr_lastResistor;
|
|
|
|
ResAddResistorToList(working, &locallist);
|
|
}
|
|
*reslist = locallist;
|
|
}
|
|
|
|
while (*reslist != NULL && (*reslist)->rr_value < tolerance)
|
|
{
|
|
current = *reslist;
|
|
if (current->rr_nextResistor == NULL)
|
|
break;
|
|
|
|
working = NULL;
|
|
c1 = 0;
|
|
c2 = 0;
|
|
|
|
/* Search for next smallest adjoining resistor */
|
|
for (rcell1 = current->rr_connection1->rn_re; rcell1 != NULL;
|
|
rcell1 = rcell1->re_nextEl)
|
|
{
|
|
if (rcell1->re_thisEl != current)
|
|
{
|
|
c1++;
|
|
if (working == NULL)
|
|
{
|
|
working = rcell1->re_thisEl;
|
|
node1 = current->rr_connection1;
|
|
}
|
|
else
|
|
{
|
|
if (working->rr_value > rcell1->re_thisEl->rr_value)
|
|
{
|
|
node1 = current->rr_connection1;
|
|
working = rcell1->re_thisEl;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
for (rcell1 = current->rr_connection2->rn_re; rcell1 != NULL;
|
|
rcell1 = rcell1->re_nextEl)
|
|
{
|
|
if (rcell1->re_thisEl != current)
|
|
{
|
|
c2++;
|
|
if (working == NULL)
|
|
{
|
|
working = rcell1->re_thisEl;
|
|
node1 = current->rr_connection2;
|
|
}
|
|
else
|
|
{
|
|
if (working->rr_value > rcell1->re_thisEl->rr_value)
|
|
{
|
|
node1 = current->rr_connection2;
|
|
working = rcell1->re_thisEl;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
/*
|
|
* If the current resistor isn't a dead end, add its value and
|
|
* area to that of the next smallest one. If it is a dead end,
|
|
* simply add its area to its node.
|
|
*/
|
|
if (c1 != 0 && c2 != 0)
|
|
{
|
|
working->rr_value += current->rr_value;
|
|
working->rr_float.rr_area += current->rr_float.rr_area;
|
|
}
|
|
else
|
|
{
|
|
node1->rn_float.rn_area += current->rr_float.rr_area;
|
|
}
|
|
/*
|
|
* Move everything from from one end of the ressistor to the
|
|
* other and eliminate the resistor.
|
|
*/
|
|
node2 = (current->rr_connection1 == node1) ? current->rr_connection2 :
|
|
current->rr_connection1;
|
|
ResDeleteResPointer(current->rr_connection1, current);
|
|
ResDeleteResPointer(current->rr_connection2, current);
|
|
working->rr_lastResistor->rr_nextResistor = working->rr_nextResistor;
|
|
if (working->rr_nextResistor != NULL)
|
|
working->rr_nextResistor->rr_lastResistor = working->rr_lastResistor;
|
|
|
|
ResEliminateResistor(current, reslist);
|
|
ResAddResistorToList(working, reslist);
|
|
if (node2->rn_why & (RES_NODE_ORIGIN | RES_NODE_SINK))
|
|
{
|
|
ResMergeNodes(node2, node1, pendingList, biglist);
|
|
node1 = node2;
|
|
}
|
|
else
|
|
ResMergeNodes(node1, node2, pendingList, biglist);
|
|
|
|
/*
|
|
* Try further simplification on net using ResDoneWithNode and
|
|
* ResSimplifyNet.
|
|
*/
|
|
ResRemoveFromQueue(node1, biglist);
|
|
ResAddToQueue(node1, pendingList);
|
|
node1->rn_status &= ~(RES_DONE_ONCE | RES_FINISHED);
|
|
ResDoneWithNode(node1);
|
|
while (*pendingList != NULL)
|
|
ResSimplifyNet(pendingList, biglist, reslist, tolerance);
|
|
}
|
|
}
|
|
|
|
/*
|
|
*-------------------------------------------------------------------------
|
|
*
|
|
* ResAddResistorToList-- Adds resistor to list according to its value
|
|
* (smallest first).
|
|
*
|
|
* Results:none
|
|
*
|
|
* Side Effects: modifies locallist.
|
|
*
|
|
*-------------------------------------------------------------------------
|
|
*/
|
|
|
|
void
|
|
ResAddResistorToList(resistor, locallist)
|
|
resResistor *resistor, **locallist;
|
|
|
|
{
|
|
resResistor *local, *last = NULL;
|
|
|
|
for (local = *locallist; local != NULL; local = local->rr_nextResistor)
|
|
{
|
|
if (local->rr_value >= resistor->rr_value)
|
|
break;
|
|
last = local;
|
|
}
|
|
if (local != NULL)
|
|
{
|
|
resistor->rr_nextResistor = local;
|
|
resistor->rr_lastResistor = local->rr_lastResistor;
|
|
if (local->rr_lastResistor == NULL)
|
|
*locallist = resistor;
|
|
else
|
|
local->rr_lastResistor->rr_nextResistor = resistor;
|
|
|
|
local->rr_lastResistor = resistor;
|
|
}
|
|
else
|
|
{
|
|
if (last != NULL)
|
|
{
|
|
last->rr_nextResistor = resistor;
|
|
resistor->rr_lastResistor = last;
|
|
resistor->rr_nextResistor = NULL;
|
|
}
|
|
else
|
|
{
|
|
resistor->rr_nextResistor = NULL;
|
|
resistor->rr_lastResistor = NULL;
|
|
*locallist = resistor;
|
|
}
|
|
}
|
|
}
|
|
|
|
/*
|
|
*-------------------------------------------------------------------------
|
|
*
|
|
* ResdistributeSubstrateCapacitance--
|
|
*
|
|
* Results:
|
|
* None.
|
|
*
|
|
* Side Effects:
|
|
* takes total capacitance to VDD or GND in a node and distributes
|
|
* it onto the new nodes.
|
|
*
|
|
*-------------------------------------------------------------------------
|
|
*/
|
|
|
|
void
|
|
ResDistributeCapacitance(nodelist, totalcap)
|
|
resNode *nodelist;
|
|
float totalcap;
|
|
|
|
{
|
|
float totalarea = 0, capperarea;
|
|
resNode *workingNode;
|
|
resElement *rptr;
|
|
|
|
for (workingNode = nodelist; workingNode != NULL; workingNode = workingNode->rn_more)
|
|
{
|
|
for (rptr = workingNode->rn_re; rptr != NULL; rptr = rptr->re_nextEl)
|
|
if (rptr->re_thisEl->rr_float.rr_area != 0.0)
|
|
TxError("Nonnull resistor area\n");
|
|
|
|
totalarea += workingNode->rn_float.rn_area;
|
|
}
|
|
if (totalarea == 0)
|
|
{
|
|
TxError("Error: Node with no area.\n");
|
|
return;
|
|
}
|
|
capperarea = totalcap / totalarea;
|
|
|
|
for (workingNode = nodelist; workingNode != NULL; workingNode = workingNode->rn_more)
|
|
workingNode->rn_float.rn_area *= capperarea;
|
|
}
|
|
|
|
/*
|
|
*-------------------------------------------------------------------------
|
|
*
|
|
* ResCalculateChildCapacitance-- calculates capacitance of this node and
|
|
* all downstream nodes.
|
|
*
|
|
* Results: Returns capacitance of this node and children nodes if connected
|
|
* to a tree- returns -1 If the subtree contains loops.
|
|
*
|
|
* Side Effects: Adds RCDelayStuff fields to nodes.
|
|
*
|
|
*-------------------------------------------------------------------------
|
|
*/
|
|
|
|
float
|
|
ResCalculateChildCapacitance(me)
|
|
resNode *me;
|
|
|
|
{
|
|
RCDelayStuff *myC;
|
|
resElement *workingRes;
|
|
resDevice *dev;
|
|
float childcap;
|
|
tElement *tptr;
|
|
int t;
|
|
ExtDevice *devptr;
|
|
|
|
if (me->rn_client != (ClientData) NULL) /* we have a loop */
|
|
return(-1);
|
|
|
|
myC = (RCDelayStuff *) mallocMagic((unsigned) (sizeof(RCDelayStuff)));
|
|
me->rn_client = (ClientData) myC;
|
|
|
|
/* This following assumes that ResDistributeCapacitance has been run */
|
|
/* and the the resulting capacitance value is stored in the area field */
|
|
myC->rc_Cdownstream = me->rn_float.rn_area;
|
|
myC->rc_Tdi = 0.0;
|
|
|
|
/* get capacitance for all connected gates */
|
|
for (tptr = me->rn_te; tptr != NULL; tptr = tptr->te_nextt)
|
|
{
|
|
dev = tptr->te_thist;
|
|
/* Hack for non-Manhattan geometry. Only one side of a split */
|
|
/* tile should correspond to a device type. */
|
|
if (IsSplit(dev->rd_tile))
|
|
{
|
|
t = TiGetLeftType(dev->rd_tile);
|
|
if (ExtCurStyle->exts_device[t] == NULL)
|
|
t = TiGetRightType(dev->rd_tile);
|
|
}
|
|
else
|
|
t = TiGetType(dev->rd_tile);
|
|
if (dev->rd_fet_gate == me)
|
|
{
|
|
devptr = ExtCurStyle->exts_device[t];
|
|
myC->rc_Cdownstream += dev->rd_length * dev->rd_width *
|
|
devptr->exts_deviceGateCap +
|
|
(dev->rd_width + dev->rd_width) *
|
|
devptr->exts_deviceSDCap;
|
|
|
|
}
|
|
}
|
|
|
|
/* Calculate child Capacitance */
|
|
for (workingRes = me->rn_re; workingRes != NULL; workingRes = workingRes->re_nextEl)
|
|
{
|
|
if (workingRes->re_thisEl->rr_connection1 == me &&
|
|
(workingRes->re_thisEl->rr_status & RES_TDI_IGNORE) == 0)
|
|
{
|
|
childcap = ResCalculateChildCapacitance(workingRes->re_thisEl->rr_connection2);
|
|
if (childcap == -1)
|
|
return(-1);
|
|
|
|
myC->rc_Cdownstream += childcap;
|
|
}
|
|
}
|
|
return (myC->rc_Cdownstream);
|
|
}
|
|
|
|
/*
|
|
*-------------------------------------------------------------------------
|
|
*
|
|
* ResCalculateTDi- Calculates TDi numbers for all the nodes in the circuit.
|
|
*
|
|
* Results: none
|
|
*
|
|
* Side Effects: sets the rc_Tdi fields of the RCDelayStuff fields of the
|
|
* nodes.
|
|
*
|
|
*-------------------------------------------------------------------------
|
|
*/
|
|
|
|
void
|
|
ResCalculateTDi(node, resistor, resistorvalue)
|
|
resNode *node;
|
|
resResistor *resistor;
|
|
int resistorvalue;
|
|
|
|
{
|
|
resElement *workingRes;
|
|
RCDelayStuff *rcd = (RCDelayStuff *)node->rn_client;
|
|
RCDelayStuff *rcd2;
|
|
|
|
ASSERT(rcd != NULL, "ResCalculateTdi");
|
|
if (resistor == NULL)
|
|
rcd->rc_Tdi = rcd->rc_Cdownstream * (float)resistorvalue;
|
|
else
|
|
{
|
|
rcd2 = (RCDelayStuff *)resistor->rr_connection1->rn_client;
|
|
ASSERT(rcd2 != NULL, "ResCalculateTdi");
|
|
rcd->rc_Tdi = rcd->rc_Cdownstream * (float)resistor->rr_value +
|
|
rcd2->rc_Tdi;
|
|
}
|
|
|
|
for (workingRes = node->rn_re; workingRes != NULL; workingRes = workingRes->re_nextEl)
|
|
{
|
|
if (workingRes->re_thisEl->rr_connection1 == node &&
|
|
(workingRes->re_thisEl->rr_status & RES_TDI_IGNORE) == 0)
|
|
ResCalculateTDi(workingRes->re_thisEl->rr_connection2,
|
|
workingRes->re_thisEl,
|
|
workingRes->re_thisEl->rr_value);
|
|
}
|
|
}
|
|
|
|
/*
|
|
*-------------------------------------------------------------------------
|
|
*
|
|
* ResPruneTree-- Designed to be run just after ResCalculateTDi to prune all
|
|
* branches off the tree whose end node value of Tdi is less than the
|
|
* tolerance. This eliminates many resistors in nets with high fanout.
|
|
*
|
|
* Results: none
|
|
*
|
|
* Side Effects: May Eliminate Resistors and Merge Nodes
|
|
*
|
|
*-------------------------------------------------------------------------
|
|
*/
|
|
|
|
void
|
|
ResPruneTree(node, minTdi, nodelist1, nodelist2, resistorlist)
|
|
resNode *node, **nodelist1, **nodelist2;
|
|
float minTdi;
|
|
resResistor **resistorlist;
|
|
|
|
{
|
|
resResistor *currentRes;
|
|
resElement *current;
|
|
|
|
current = node->rn_re;
|
|
while(current != NULL)
|
|
{
|
|
currentRes = current->re_thisEl;
|
|
current = current->re_nextEl;
|
|
/* Ignore previously found loops */
|
|
if (!(currentRes->rr_status & RES_TDI_IGNORE))
|
|
/* If branch points outward, call routine on subtrees */
|
|
if (currentRes->rr_connection1 == node)
|
|
ResPruneTree(currentRes->rr_connection2, minTdi, nodelist1,
|
|
nodelist2, resistorlist);
|
|
}
|
|
|
|
/* We eliminate this branch if:
|
|
* 1. It is a terminal node, i.e. it is the connected
|
|
* to only one resistor.
|
|
* 2. The direction of this resistor is toward the node
|
|
* (This prevents the root from being eliminated
|
|
* 3. The time constant TDI is less than the tolerance.
|
|
*/
|
|
|
|
if (node->rn_re != NULL &&
|
|
node->rn_re->re_nextEl == NULL &&
|
|
node->rn_re->re_thisEl->rr_connection2 == node)
|
|
{
|
|
if (node->rn_client == (ClientData)NULL)
|
|
{
|
|
TxError("Internal Error in Tree Pruning: Missing TDi value.\n");
|
|
}
|
|
else if (((RCDelayStuff *)(node->rn_client))->rc_Tdi < minTdi)
|
|
{
|
|
currentRes = node->rn_re->re_thisEl;
|
|
ResDeleteResPointer(currentRes->rr_connection1, currentRes);
|
|
ResDeleteResPointer(currentRes->rr_connection2, currentRes);
|
|
ResMergeNodes(currentRes->rr_connection1, currentRes->rr_connection2,
|
|
nodelist2, nodelist1);
|
|
ResEliminateResistor(currentRes, resistorlist);
|
|
}
|
|
}
|
|
}
|
|
|
|
/*
|
|
*-------------------------------------------------------------------------
|
|
*
|
|
*-------------------------------------------------------------------------
|
|
*/
|
|
|
|
int
|
|
ResDoSimplify(resisdata)
|
|
ResisData *resisdata;
|
|
|
|
{
|
|
resNode *node, *slownode;
|
|
float bigres = 0.0;
|
|
float totalcap;
|
|
resResistor *res;
|
|
|
|
ResSetPathRes(resisdata);
|
|
|
|
for (node = ResNodeList; node != NULL; node = node->rn_more)
|
|
bigres = MAX(bigres, node->rn_noderes);
|
|
|
|
resisdata->rg_maxres = bigres;
|
|
|
|
#ifdef PARANOID
|
|
ResSanityChecks("ExtractSingleNet", ResResList, ResNodeList, ResDevList);
|
|
#endif
|
|
|
|
/* Is extracted network still greater than the tolerance? */
|
|
/* Even if it isn't, we still let the next section run if */
|
|
/* we're calculating lumped values so that the capacitance */
|
|
/* values get calculated correctly. */
|
|
|
|
(void) ResDistributeCapacitance(ResNodeList, resisdata->rg_nodecap);
|
|
|
|
if (((ResOptionsFlags & ResOpt_Simplify) == 0) &&
|
|
((ResOptionsFlags & ResOpt_DoLumpFile) == 0))
|
|
return 0;
|
|
|
|
res = ResResList;
|
|
while (res)
|
|
{
|
|
resResistor *oldres = res;
|
|
|
|
res = res->rr_nextResistor;
|
|
oldres->rr_status &= ~RES_HEAP;
|
|
}
|
|
|
|
if (ResNodeAtOrigin == NULL)
|
|
{
|
|
TxError("Error: Network simplification: Failed to to get origin node.\n");
|
|
resisdata->rg_Tdi = 0;
|
|
}
|
|
else if (resisdata->mindelay > 0)
|
|
{
|
|
if ((resisdata->rg_nodecap != -1) &&
|
|
(totalcap = ResCalculateChildCapacitance(ResNodeAtOrigin)) != -1)
|
|
{
|
|
RCDelayStuff *rc = (RCDelayStuff *) ResNodeList->rn_client;
|
|
|
|
resisdata->rg_nodecap = totalcap;
|
|
ResCalculateTDi(ResNodeAtOrigin, (resResistor *)NULL, 0);
|
|
if (rc != (RCDelayStuff *)NULL)
|
|
resisdata->rg_Tdi = rc->rc_Tdi;
|
|
else
|
|
resisdata->rg_Tdi = 0;
|
|
|
|
slownode = ResNodeList;
|
|
for (node = ResNodeList; node != NULL; node = node->rn_more)
|
|
{
|
|
rc = (RCDelayStuff *)node->rn_client;
|
|
if ((rc != NULL) && (resisdata->rg_Tdi < rc->rc_Tdi))
|
|
{
|
|
slownode = node;
|
|
resisdata->rg_Tdi = rc->rc_Tdi;
|
|
}
|
|
}
|
|
slownode->rn_status |= RES_MAXTDI;
|
|
}
|
|
else
|
|
resisdata->rg_Tdi = -1;
|
|
}
|
|
else
|
|
resisdata->rg_Tdi = 0;
|
|
|
|
/* Simplify network */
|
|
|
|
if (ResOptionsFlags & ResOpt_Simplify)
|
|
{
|
|
/*
|
|
* Start simplification at driver (R=0). Remove it from the done list
|
|
* and add it to the pending list. Call ResSimplifyNet as long as
|
|
* nodes remain in the pending list.
|
|
*/
|
|
for (node = ResNodeList; node != NULL; node = node->rn_more)
|
|
{
|
|
if (node->rn_noderes == 0)
|
|
ResNodeAtOrigin = node;
|
|
|
|
node->rn_status |= RES_FINISHED;
|
|
}
|
|
if (ResNodeAtOrigin != NULL)
|
|
{
|
|
/* if Tdi is enabled, prune all branches whose end nodes */
|
|
/* have time constants less than the tolerance. */
|
|
|
|
if ((resisdata->rg_Tdi != -1) && (resisdata->mindelay > 0))
|
|
ResPruneTree(ResNodeAtOrigin, resisdata->mindelay,
|
|
&ResNodeList, &ResNodeQueue, &ResResList);
|
|
|
|
ResNodeAtOrigin->rn_status &= ~RES_MARKED;
|
|
if (ResNodeAtOrigin->rn_less == CLIENTDEFAULT)
|
|
{
|
|
TxError("ResSimplify: Bad resptr at node %s origin.\n",
|
|
ResNodeAtOrigin->rn_name);
|
|
return 0;
|
|
}
|
|
else if (ResNodeAtOrigin->rn_less == NULL)
|
|
ResNodeList = ResNodeAtOrigin->rn_more;
|
|
else
|
|
ResNodeAtOrigin->rn_less->rn_more = ResNodeAtOrigin->rn_more;
|
|
|
|
if (ResNodeAtOrigin->rn_more != NULL)
|
|
ResNodeAtOrigin->rn_more->rn_less = ResNodeAtOrigin->rn_less;
|
|
|
|
ResNodeAtOrigin->rn_more = NULL;
|
|
ResNodeAtOrigin->rn_less = NULL;
|
|
ResNodeQueue = ResNodeAtOrigin;
|
|
while (ResNodeQueue != NULL)
|
|
ResSimplifyNet(&ResNodeQueue, &ResNodeList, &ResResList,
|
|
resisdata->minres);
|
|
|
|
/*
|
|
* Call ResScrunchNet to eliminate any remaining under-tolerance
|
|
* resistors.
|
|
*/
|
|
ResScrunchNet(&ResResList, &ResNodeQueue, &ResNodeList, resisdata->minres);
|
|
}
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
/*
|
|
*-------------------------------------------------------------------------
|
|
*
|
|
*-------------------------------------------------------------------------
|
|
*/
|
|
|
|
void
|
|
ResSetPathRes(ResisData *resisdata)
|
|
{
|
|
HeapEntry he;
|
|
resNode *node;
|
|
static int init = 1;
|
|
|
|
if (init)
|
|
{
|
|
init = 0;
|
|
HeapInit(&ResistorHeap, 128, FALSE, FALSE);
|
|
}
|
|
|
|
for (node = ResNodeList; node != NULL; node = node->rn_more)
|
|
{
|
|
if (node->rn_noderes == 0)
|
|
{
|
|
ResNodeAtOrigin = node;
|
|
node->rn_status |= RES_FINISHED;
|
|
}
|
|
else
|
|
{
|
|
node->rn_noderes = RES_INFINITY;
|
|
node->rn_status &= ~RES_FINISHED;
|
|
}
|
|
}
|
|
if (ResNodeAtOrigin == NULL)
|
|
{
|
|
resDevice *res = ResGetDevice(resisdata->rg_devloc, resisdata->rg_ttype);
|
|
if (res == (resDevice *)NULL)
|
|
{
|
|
TxError("Error: No device type %s found at location %s %s\n",
|
|
DBTypeLongNameTbl[resisdata->rg_ttype],
|
|
DBWPrintValue(resisdata->rg_devloc->p_x, (MagWindow *)NULL, TRUE),
|
|
DBWPrintValue(resisdata->rg_devloc->p_y, (MagWindow *)NULL, FALSE));
|
|
return;
|
|
}
|
|
ResNodeAtOrigin = res->rd_fet_source;
|
|
ResNodeAtOrigin->rn_why = RES_NODE_ORIGIN;
|
|
ResNodeAtOrigin->rn_noderes = 0;
|
|
}
|
|
ASSERT(ResNodeAtOrigin != NULL, "ResDoSimplify");
|
|
resPathNode(ResNodeAtOrigin);
|
|
while (HeapRemoveTop(&ResistorHeap,&he))
|
|
resPathRes((resResistor *)he.he_id);
|
|
}
|
|
|
|
/*
|
|
*-------------------------------------------------------------------------
|
|
* resPathNode ---
|
|
*
|
|
* Given node "node", add every resistor connected to the node, and
|
|
* for which the node on the other side has not been processed, to
|
|
* the heap. Node is marked with RES_FINISHED to prevent going 'round
|
|
* and 'round loops.
|
|
*-------------------------------------------------------------------------
|
|
*/
|
|
|
|
void
|
|
resPathNode(node)
|
|
resNode *node;
|
|
|
|
{
|
|
resElement *re;
|
|
|
|
node->rn_status |= RES_FINISHED;
|
|
for (re = node->rn_re; re; re = re->re_nextEl)
|
|
{
|
|
resResistor *res = re->re_thisEl;
|
|
resNode *node2;
|
|
|
|
if (res->rr_status & RES_HEAP) continue;
|
|
if ((node2 = res->rr_node[0]) == node) node2 = res->rr_node[1];
|
|
if ((node2->rn_status & RES_FINISHED) == 0)
|
|
HeapAddInt(&ResistorHeap, node->rn_noderes + res->rr_value,
|
|
(char *)res);
|
|
}
|
|
}
|
|
|
|
/*
|
|
*-------------------------------------------------------------------------
|
|
*
|
|
* resPathRes ---
|
|
*
|
|
* Given resistor "res" pulled from the heap (in heap order, which
|
|
* is the highest valued resistor currently in the heap):
|
|
*
|
|
* If both ends of the resistor have been processed, then we have
|
|
* a loop, and should return.
|
|
*
|
|
* Otherwise, call resPathNode() on the node of whichever end of
|
|
* the resistor has not yet been processed, thus continuing through
|
|
* the path from the origin.
|
|
*
|
|
*-------------------------------------------------------------------------
|
|
*/
|
|
|
|
void
|
|
resPathRes(res)
|
|
resResistor *res;
|
|
|
|
{
|
|
resNode *node0, *node1;
|
|
int flag0, flag1;
|
|
|
|
res->rr_status |= RES_HEAP;
|
|
res->rr_status &= ~RES_MARKED;
|
|
node0 = res->rr_node[0];
|
|
node1 = res->rr_node[1];
|
|
flag0 = node0->rn_status & RES_FINISHED;
|
|
flag1 = node1->rn_status & RES_FINISHED;
|
|
if (flag0 && flag1)
|
|
{
|
|
res->rr_status |= RES_TDI_IGNORE;
|
|
/* Loop found---return without calling resPathNode() */
|
|
}
|
|
else if (flag0)
|
|
{
|
|
node1->rn_noderes = node0->rn_noderes + res->rr_value;
|
|
resPathNode(node1);
|
|
}
|
|
else
|
|
{
|
|
ASSERT(flag1, "ResPathRes");
|
|
res->rr_node[0] = node1;
|
|
res->rr_node[1] = node0;
|
|
node0->rn_noderes = node1->rn_noderes + res->rr_value;
|
|
resPathNode(node0);
|
|
}
|
|
}
|