src/truesim/truesimMain.c

Go to the documentation of this file.

#include "truesimInt.h"

/*---------------------------------------------------------------------------*/
/* Constant declarations                                                     */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Type declarations                                                         */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Structure declarations                                                    */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Variable declarations                                                     */
/*---------------------------------------------------------------------------*/

static long numEvents;

extern int truesimVerbose;
extern int truesimRptHeader;

/*---------------------------------------------------------------------------*/
/* Macro declarations                                                        */
/*---------------------------------------------------------------------------*/

/*---------------------------------------------------------------------------*/
/* Static function prototypes                                                */
/*---------------------------------------------------------------------------*/

static void InsertInputEvents(st_table *nodeToSimTable, EventQueue *queue, array_t *inputArray, char *vector);
static void SinglePatternSimulate(Ntk_Network_t *network, EventQueue *queue);
static void HouseKeeping(EventQueue *queue, Event *threshevent);
static void InsertFanouts(Ntk_Node_t *node, st_table *fanoutTable);
static void PerformSecondPass(Ntk_Network_t *network, EventQueue *queue, st_table *fanoutTable);
static void ScheduleEvent(EventQueue *queue, Ntk_Node_t *node, TrueSim_t *sim, char value);
static void RescheduleEvent(EventQueue *queue, Ntk_Node_t *node, TrueSim_t *sim, char value);
static void CancelEvent(EventQueue *queue, TrueSim_t *sim);
static void InsertInBin(Event **wheel, Event *event);
static EventQueue * InitQueue(void);
static void NewPage(EventQueue *queue);
static enum st_retval stTrueSimFree(char *key, char *value, char *arg);

/*---------------------------------------------------------------------------*/
/* Definition of exported functions                                          */
/*---------------------------------------------------------------------------*/

int
Truesim_RealDelayPatternSimulate(
  Ntk_Network_t *network,
  array_t *inputArray,
  array_t *patternArray)
{
  Ntk_Node_t *node;
  int numVectors = array_n(patternArray);
  int i;
  EventQueue *queue;
  st_table *nodeToSimTable = TruesimNetworkReadSimTable(network);
  lsGen gen;

  if (nodeToSimTable == NIL(st_table)) {
    (void) fprintf(vis_stderr,
                   "** truesim error: Simulation structures not initialized\n");
    (void) fprintf(vis_stderr,
                   "** truesim error: Call Truesim_InitializeSimulation before ");
    (void) fprintf(vis_stderr,"calling this function.\n");
    return -1;
  }

  /* Initialize the converging list data structure */
  queue = InitQueue();

  /* Initialize node simulation data structures */
  TruesimInitializeActivityFields(network,nodeToSimTable);

  /* Warmup simulation. Simulate the first vector to initialize internal nodes
     in the network. */
  TruesimWarmUpPatternSimulate(network,inputArray,
                               array_fetch(char *,patternArray,0));
  
  /* Performs simulation of all the vectors */
  for (i = 1; i < numVectors; i++) {
    char *stimulus;
    stimulus = array_fetch(char *,patternArray,i);
    InsertInputEvents(nodeToSimTable,queue,inputArray,stimulus);
    SinglePatternSimulate(network,queue);

    if (truesimVerbose) {
      if (truesimRptHeader != -1) {
        if (i % truesimRptHeader == 0) 
          TruesimPrintNameHeader(network);
      }
      TruesimPrintNetworkNodeLogicState(network);
    }
  }

  /* Free the queue */
  if (queue != NIL(EventQueue)) {
    while (queue->freeList != NIL(Event *)) {
      Event **next;
      next = (Event **) queue->freeList[0];
      FREE(queue->freeList);
      queue->freeList = next;
    }
    FREE(queue->wheel);
    FREE(queue);
  }
  
  /* Update the statistics for each node */
  Ntk_NetworkForEachNode(network,gen,node) {
    TrueSim_t *sim;
    if (!st_lookup(nodeToSimTable,(char *)node,&sim)) {
      (void) fprintf(vis_stderr,
                     "** truesim fatal:In Truesim_RealDelayPatternSimulate\n");
      (void) fprintf(vis_stderr,"        Sim. structure missing for %s\n",
                     Ntk_NodeReadName(node));
      
      assert(0);
    }
    /* Get the switching probability and the signal probability */
    sim->switching /= ((float) array_n(patternArray));
    sim->prob /= ((float) array_n(patternArray));
  }

  return 1;

} /* End of Truesim_RealDelayPatternSimulate */


void
Truesim_InitializeSimulation(
  Ntk_Network_t *network,
  char *delayFile,
  boolean truedelay,
  int header,
  int verbose,
  st_table *nodeDelayTable)
{
  Truesim_Info_t *simInfo;
  st_table *nodeToSimTable;
  lsGen gen;
  Ntk_Node_t *node;
  TrueSim_t *sim;
  float delay,load;
  float *delayPtr;

  delay = -1.0; /* To keep the compiler happy */
  /* Allocate the Truesim_Info_t * structure */
  simInfo = ALLOC(Truesim_Info_t,1);
  Ntk_NetworkAddApplInfo(network,TRUESIM_NETWORK_APPL_KEY,
                         (Ntk_ApplInfoFreeFn)TruesimEndSimulation,
                         (void *)simInfo);
  simInfo->depthArray = NIL(array_t);
  simInfo->nodeToSimTable = NIL(st_table);

  /* Allocate simulation structure for each node in the network and
     put it in a table.*/
  nodeToSimTable = st_init_table(st_ptrcmp,st_ptrhash);

  if (delayFile) {
    TruesimReadDelayFile(network,delayFile,nodeToSimTable);
  } else { /* Read from nodeDelayTable */
    Ntk_NetworkForEachNode(network,gen,node) {
      sim = ALLOC(TrueSim_t,1);
      /* I assume inputs to have zero delay. */
      if (Ntk_NodeTestIsPrimaryInput(node)) {
        delay = 0;
      }
      if (nodeDelayTable == NIL(st_table) ||
          !st_lookup(nodeDelayTable,(char *)node,&delayPtr)) {
        if (Ntk_NodeTestIsPrimaryInput(node)) {
          load = (float) Ntk_NodeReadNumFanouts(node);
        } else if (Ntk_NodeTestIsPrimaryOutput(node)){
          /* Sometimes primary outputs can fanout to other internal nodes */
          load = (float) Ntk_NodeReadNumFanouts(node);
          load = load ? load : 1.0;
          delay = load;
        } else {
          delay = load = (float) Ntk_NodeReadNumFanouts(node);
        }
      } else { /* if you do find it */
        delay = load = *delayPtr;
      }
      sim->delay = delay;
      sim->load = load;
      st_insert(nodeToSimTable, (char *)node, (char *)sim);
    }
  }
  
  /* Set the global variables truesimRptHeader, truesimVerbose */
  simInfo->trueDelay = truedelay;
  simInfo->repeatHeader = truesimRptHeader = header;
  simInfo->truesimVerbose = truesimVerbose = verbose;
  simInfo->nodeToSimTable = nodeToSimTable;
  
  /* Fill in depth field for each node */
  Truesim_NetworkUpdateNodeTopologicalDepth(network);

  return;
} /* End of Truesim_InitializeSimulation */


void
Truesim_QuitSimulation(Ntk_Network_t *network)
{
  Ntk_NetworkFreeApplInfo(network,TRUESIM_NETWORK_APPL_KEY);
  
} /* End of Truesim_QuitSimulation */


/*---------------------------------------------------------------------------*/
/* Definition of internal functions                                          */
/*---------------------------------------------------------------------------*/
void
TruesimEndSimulation(void *data)
{
  st_table *nodeToSimTable;
  array_t *depthArray,*tempArray;
  Truesim_Info_t *dataBody;
  int i;
  
  nodeToSimTable = ((Truesim_Info_t *)data)->nodeToSimTable;
  depthArray = ((Truesim_Info_t *)data)->depthArray;
  
  if (nodeToSimTable) {
    st_foreach(nodeToSimTable,stTrueSimFree,NIL(char));
    st_free_table(nodeToSimTable);
  }

  arrayForEachItem(array_t *,depthArray,i,tempArray) {
    array_free(tempArray);
  }
  array_free(depthArray);
  
  dataBody = (Truesim_Info_t *)data;
  FREE(dataBody);
  
} /* End of TruesimEndSimulation */


/*---------------------------------------------------------------------------*/
/* Definition of static functions                                            */
/*---------------------------------------------------------------------------*/
static void
InsertInputEvents(
  st_table *nodeToSimTable,
  EventQueue *queue,              
  array_t *inputArray,
  char *vector)
{
  Ntk_Node_t *node;
  TrueSim_t *sim;
  int i;
  char prev;

  arrayForEachItem(Ntk_Node_t *,inputArray,i,node) {
    if (!st_lookup(nodeToSimTable,(char *)node,&sim)) {
      (void) fprintf(vis_stderr,"** truesim fatal: In InsertInputEvents\n");
      (void) fprintf(vis_stderr,"        Sim. structure missing for %s\n",
                     Ntk_NodeReadName(node));
      assert(0);
    }
    prev = sim->value;
    if (prev != vector[i]) {
      ScheduleEvent(queue,node,sim,vector[i]);
    }
  }
  
} /* End of InsertInputEvents */


static void
SinglePatternSimulate(
  Ntk_Network_t *network,                     
  EventQueue *queue)
{
  Event *currentEvent;
  Event **wheel;
  long currbin,halfPeriodBin;
  Ntk_Node_t *gate;  /* Node being simulated/evaluated */
  st_table *fanoutTable; /* Nodes in the fanout */
  st_table *nodeToSimTable = TruesimNetworkReadSimTable(network);
  TrueSim_t *simInfo;
  long eventType;

  /* No events to start with */
  if (numEvents == 0)
    return;

  wheel = queue->wheel;
  halfPeriodBin = WHEEL_POS(HALF_PERIOD - 1);

  currbin = 0;

  /* Find the first sim, th2, th3 event */ 
  /* Events th2 and th3 are control events. They help in housekeeping of the
     event queue. When a th2 event is reached, the time ranges for each slot in
     the wheel is increased. The threshold events are different from the
     simulation events in that they are not related to simulation. They help in
     the timely update of the wheel. */
  do {
    fanoutTable = st_init_table(st_ptrcmp,st_ptrhash);

    do { /* examine each bin */
      currentEvent = wheel[currbin];
      eventType = TYPE(currentEvent);   

      switch (eventType) {
      case SIM_EVENT_C :
        /* Simply cancel the event as this is a cancel event */
        wheel[currbin] = NEXT_VER(currentEvent); 
        /* free current event and obtain next */
        EVENT_FREE(queue, currentEvent);
        numEvents--;
        break;
      case SIM_EVENT_0 :        
        wheel[currbin] = NEXT_VER(currentEvent); 
        queue->time = TIME(currentEvent);
        gate = GATE(currentEvent); 
        if (!st_lookup(nodeToSimTable,(char *)gate,&simInfo)) {
          (void) fprintf(vis_stderr,"** truesim fatal: In case SIM_EVENT_0\n");
          (void) fprintf(vis_stderr,"        Sim. structure missing for %s\n",
                         Ntk_NodeReadName(gate));

          assert(0);
        }
        (simInfo->switching)++;
        simInfo->value = '0';
        /* Collect the fanouts that may need to be scheduled. This is used for
           the second pass */
        InsertFanouts(gate,fanoutTable);
        /* free current event and obtain next */
        EVENT_FREE(queue, currentEvent);
        simInfo->event = NIL(Event);
        numEvents--;
        break;
      case SIM_EVENT_1 :        
        wheel[currbin] = NEXT_VER(currentEvent); 
        queue->time = TIME(currentEvent);
        gate = GATE(currentEvent);
        if (!st_lookup(nodeToSimTable,(char *)gate,&simInfo)) {
          (void) fprintf(vis_stderr,"** truesim fatal: In case SIM_EVENT_1\n");
          (void) fprintf(vis_stderr,"        Sim. structure missing for %s\n",
                         Ntk_NodeReadName(gate));
          assert(0);
        }
        (simInfo->switching)++;
        simInfo->value = '1';
        (simInfo->prob)++;
        /* Collect the fanouts that may need to be scheduled. This is used for
           the second pass */
        InsertFanouts(gate,fanoutTable);                                
        /* free current event and obtain next */
        EVENT_FREE(queue, currentEvent);
        simInfo->event = NIL(Event);
        numEvents--;
        break;
      case THRESHOLD_1 :        
        currbin++; 
        currbin &= ((1 << LOG_WHEEL_SIZE) - 1);
        break;
      case THRESHOLD_2 :        
        HouseKeeping(queue, currentEvent);
        currbin = halfPeriodBin + 1;
        break;
      case THRESHOLD_3 :        
        HouseKeeping(queue, currentEvent);
        currbin = 0;
        break;
      default:
        (void) fprintf(vis_stderr,"** truesim fatal: Unknown event %ld\n",
                       eventType);
        assert(0);
      } 
    } while (NEXT_BOT(currentEvent) != currentEvent);

    if (truesimVerbose > 2) {
      (void) fprintf(vis_stdout,"Simulation time tick %ld",queue->time);
      TruesimPrintNetworkNodeLogicState(network);
    }
    
    /* We are finished processing a vertical list. A vertical list has events
       scheduled for the same time. Now perform the second pass of the
       simulation. */
    PerformSecondPass(network,queue,fanoutTable);
    st_free_table(fanoutTable);
  } while (numEvents > 0);

  /* End of simulation for one pattern */
  /* Reset the queue */
  queue->current = NIL(Event);
  queue->time = 0;
  TIME(queue->th1) = PERIOD - 1;
  TIME(queue->th2) = PERIOD - 1;
  TIME(queue->th3) = PERIOD - 1;

} /* End of SinglePatternSimulate */


static void
HouseKeeping(
  EventQueue *queue,
  Event *threshevent)
{
  Event **wheel;
  Event *event, *threshold1;
  Event *temp;
  long threshold1_time;

  wheel = queue->wheel;

  /* add T/2 to all threshold events */
  threshold1 = queue->th1;
  TIME(threshold1) += HALF_PERIOD;
  TIME(queue->th2) += HALF_PERIOD;
  TIME(queue->th3) += HALF_PERIOD;

  threshold1_time = TIME(threshold1);
  event = NEXT_HOR(threshold1);
  while(TIME(event) <= threshold1_time) {
    NEXT_HOR(threshold1) = NEXT_HOR(event);
    temp = event;
    while (NEXT_BOT(temp) != temp) {
      InsertInBin(wheel,temp);
      temp = NEXT_VER(temp);
    }
    InsertInBin(wheel,temp);
    event = NEXT_HOR(threshold1);
  }

} /* End of HouseKeeping */


static void
InsertFanouts(
  Ntk_Node_t *node,
  st_table *fanoutTable)
{
  int i;
  Ntk_Node_t *fanout;
  
  Ntk_NodeForEachFanout(node,i,fanout) {
    st_insert(fanoutTable,(char *)fanout,(char *)0);
  }

} /* End of InsertFanouts */


static void
PerformSecondPass(
  Ntk_Network_t *network,
  EventQueue *queue,
  st_table *fanoutTable)
{
  bdd_manager *ddManager = Ntk_NetworkReadMddManager(network);
  graph_t *partition = Part_NetworkReadPartition(network);
  st_table *nodeToSimTable = TruesimNetworkReadSimTable(network);
  st_generator *stGen;
  Ntk_Node_t *node,*dummy;
  char next,prev;

  st_foreach_item(fanoutTable,stGen,&node,&dummy) {
    TrueSim_t *sim;

    /* Lookup the simtable to extract the sim struct for the gate. */
    if (!st_lookup(nodeToSimTable,(char *)node,&sim)) {
      (void) fprintf(vis_stderr,"** truesim fatal: In PerformSecondPass\n");
      (void) fprintf(vis_stderr,"        Sim. structure missing for %s\n",
                     Ntk_NodeReadName(node));
      assert(0);
    }

    next = TruesimEvaluateNode(node,partition,ddManager,
                               nodeToSimTable);
    prev = sim->value;
    if (prev != next) {
      /* Check if an event already exists. If true, then reschedule the event */
      if (sim->event) {
        RescheduleEvent(queue,node,sim,next);
      } else {
        ScheduleEvent(queue,node,sim,next);
      }
    } else {
      /* Check if an event already exists. If true, then cancel that event */
      if (sim->event)
        CancelEvent(queue,sim);
    }
  }

} /* End of PerformSecondPass */


static void
ScheduleEvent(
  EventQueue *queue,
  Ntk_Node_t *node,
  TrueSim_t *sim,
  char value)
{
  Event *event;

  EVENT_ALLOC(queue, event);
  TIME(event) = queue->time + (long) sim->delay;
  GATE(event) = node;
  TYPE(event) = (value == '1') ? SIM_EVENT_1 : SIM_EVENT_0;
  NEXT_HOR(event) = NIL(Event);
  NEXT_VER(event) = NIL(Event);
  NEXT_BOT(event) = NIL(Event);

  InsertInBin(queue->wheel, event);

  /* Cross pointer to the event, in case of cancellation or rescheduling */
  sim->event = event;
  numEvents++;

} /* End of ScheduleEvent */


static void
RescheduleEvent(
  EventQueue *queue,
  Ntk_Node_t *node,
  TrueSim_t *sim,
  char value)
{
  Event *event;

  event = sim->event;
  TYPE(event) = SIM_EVENT_C;

  ScheduleEvent(queue,node,sim,value);

} /* End of RescheduleEvent */


static void
CancelEvent(
  EventQueue *queue,
  TrueSim_t *sim)
{
  Event *event;

  event = sim->event;
  TYPE(event) = SIM_EVENT_C;

  sim->event = NIL(Event);

} /* End of CancelEvent */


static void
InsertInBin(
  Event **wheel,
  Event *event)
{
  Event *prev,*curr;
  long  pos;

  pos = WHEEL_POS(TIME(event)); 

  if (TIME(wheel[pos]) >= TIME(event)) { /* to insert as first element */
    if (TIME(wheel[pos]) > TIME(event)) {
      NEXT_BOT(event) = event;
      NEXT_HOR(event) = wheel[pos];
      NEXT_VER(event) = wheel[pos];
      wheel[pos] = event;

    } else {
      NEXT_VER(event) = wheel[pos];
      NEXT_BOT(event) = NEXT_BOT(NEXT_VER(event));
      NEXT_HOR(event) = NEXT_HOR(wheel[pos]);
      wheel[pos] = event;

    }
  } else {
    prev = curr = wheel[pos];

    /* Assumption : the last element in the converging list always has
       a time greater than event. This is true by construction. */
    while(TIME(curr) < TIME(event)) {
      prev = curr;
      curr = NEXT_HOR(curr);
    }

    if (TIME(curr) == TIME(event)) {
      NEXT_VER(event) = curr;
      NEXT_BOT(event) = NEXT_BOT(NEXT_VER(event));
      NEXT_HOR(event) = NEXT_HOR(curr);
      NEXT_HOR(prev) = event;
      NEXT_VER(NEXT_BOT(prev)) = event;
    } else {
      NEXT_BOT(event) = event;
      NEXT_HOR(event) = curr;
      NEXT_VER(event) = curr;
      NEXT_HOR(prev) = event;
      NEXT_VER(NEXT_BOT(prev)) = event;
    }
  }     

} /* End of InsertInBin */


static EventQueue *
InitQueue(void)
{
  EventQueue *queue; 
  Event **wheel,*threshold; 
  int i;

  queue = ALLOC(EventQueue, 1); 
  queue->wheel = ALLOC(Event *, WHEEL_SIZE); 
  queue->current = NIL(Event);
  queue->time = 0;
  queue->freeList = NIL(Event *);
  queue->nextFree = NIL(Event);;

  /* Allocate control events, th1, th2 and th3 and thi (infinity)*/
  EVENT_ALLOC(queue, threshold);
  queue->thi = threshold;
  TYPE(threshold)  = THRESHOLD_I;
  TIME(threshold) = MAX_TIME;
  NEXT_HOR(threshold) = NIL(Event);
  NEXT_VER(threshold) = NIL(Event);
  NEXT_BOT(threshold) = threshold;

  EVENT_ALLOC(queue, threshold);
  queue->th1 = threshold;
  TYPE(threshold)  = THRESHOLD_1;
  TIME(threshold) = PERIOD -1;
  NEXT_HOR(threshold) = queue->thi;
  NEXT_VER(threshold) = queue->thi;
  NEXT_BOT(threshold) = threshold;

  EVENT_ALLOC(queue, threshold);
  queue->th2 = threshold;
  TYPE(threshold)  = THRESHOLD_2;
  TIME(threshold) = PERIOD -1;
  NEXT_HOR(threshold) = queue->th1;
  NEXT_VER(threshold) = queue->th1;
  NEXT_BOT(threshold) = threshold;

  EVENT_ALLOC(queue, threshold);
  queue->th3 = threshold;
  TYPE(threshold)  = THRESHOLD_3;
  TIME(threshold) = PERIOD-1;
  NEXT_HOR(threshold) = queue->th1;
  NEXT_VER(threshold) = queue->th1;
  NEXT_BOT(threshold) = threshold;

  wheel = queue->wheel;
  threshold = queue->th1;
  for (i = 0; i < WHEEL_SIZE; i++) {
    wheel[i] = threshold;
  }

  wheel[WHEEL_POS(HALF_PERIOD - 1)] =  queue->th2;
  wheel[WHEEL_POS(PERIOD - 1)] =  queue->th3;

  return (queue);

} /* End of InitQueue */


static void
NewPage(EventQueue *queue)
{
  Event **mem,*list;
  int i;

  mem = (Event **) ALLOC(char,MEM_CHUNK * sizeof(Event) + sizeof(Event *));

  mem[0] = (Event *) queue->freeList;
  queue->freeList = mem;

  list = (Event *) &mem[1];

  i = 0;
  do {
    list[i].horizontal = &list[i + 1];
  } while (++i < MEM_CHUNK -1);

  list[MEM_CHUNK - 1].horizontal = NIL(Event);

  queue->nextFree = list;

} /* End of NewPage */


static enum st_retval
stTrueSimFree(
  char *key,
  char *value,
  char *arg)
{
  TrueSim_t *sim;
  sim = (TrueSim_t *)value;

  if (sim)
    FREE(sim);

  return (ST_CONTINUE);
} /* End of stTrueSimFree */