/**CFile*********************************************************************** FileName [truesimMain.c] PackageName [truesim] Synopsis [Routines to perform full delay simulation.] Descriptin [Routines to perform full delay simulation. The main routine implements a levelized two-pass event driven simulator.] Author [Balakrishna Kumthekar] Copyright [This file was created at the University of Colorado at Boulder. The University of Colorado at Boulder makes no warranty about the suitability of this software for any purpose. It is presented on an AS IS basis.] ******************************************************************************/ #include "truesimInt.h" /*---------------------------------------------------------------------------*/ /* Constant declarations */ /*---------------------------------------------------------------------------*/ /*---------------------------------------------------------------------------*/ /* Type declarations */ /*---------------------------------------------------------------------------*/ /*---------------------------------------------------------------------------*/ /* Structure declarations */ /*---------------------------------------------------------------------------*/ /*---------------------------------------------------------------------------*/ /* Variable declarations */ /*---------------------------------------------------------------------------*/ static long numEvents; extern int truesimVerbose; extern int truesimRptHeader; /*---------------------------------------------------------------------------*/ /* Macro declarations */ /*---------------------------------------------------------------------------*/ /**AutomaticStart*************************************************************/ /*---------------------------------------------------------------------------*/ /* 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); /**AutomaticEnd***************************************************************/ /*---------------------------------------------------------------------------*/ /* Definition of exported functions */ /*---------------------------------------------------------------------------*/ /**Function******************************************************************** Synopsis [This routine performs real delay pattern simulation.] Description [This routine performs real delay pattern simulation. inputArray is an array of PI names. patternArray is a character array of pattern vectors. Pattern vectors are 0-1 bit-vectors whose length is equal to the number of primary inputs of the circuit. The length of inpuArray and patternArray should be equal. Successive patterns are applied to the circuit after the changes due to a previous pattern vector settle down. ] SideEffects [Simulation data structure associated with each network node is changed.] SeeAlso [Truesim_ZeroDelayPatternSimulate] ******************************************************************************/ 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 */ /**Function******************************************************************** Synopsis [Initialize the info structure associated with truesim package.] Description [Initialize the info structure associated with truesim package. Every 'header' number of patterns simulated, a line containing PI and PO names are output. In the absence of delay value for a node (from nodeDelayTable or the delayFile), the fanout count is used as the default delay value. Arrival times for PI are assumed to be 0. Simulation assumes that each node in the network has a local bdd associated with it in the partition. This can be ensured by using 'total' as the partition method.] SideEffects [The info data structure is hooked to the network.] SeeAlso [Truesim_QuitSimulation] ******************************************************************************/ 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 */ /**Function******************************************************************** Synopsis [Free the truesim info data structure.] SideEffects [The info data structure attached to the network is freed.] SeeAlso [optional] ******************************************************************************/ void Truesim_QuitSimulation(Ntk_Network_t *network) { Ntk_NetworkFreeApplInfo(network,TRUESIM_NETWORK_APPL_KEY); } /* End of Truesim_QuitSimulation */ /*---------------------------------------------------------------------------*/ /* Definition of internal functions */ /*---------------------------------------------------------------------------*/ /**Function******************************************************************** Synopsis [Free memory associated with Truesim_Info_t] SideEffects [None] SeeAlso [Truesim_QuitSimulation] ******************************************************************************/ 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 */ /*---------------------------------------------------------------------------*/ /**Function******************************************************************** Synopsis [Insert input events, i.e., PI events.] SideEffects [None] SeeAlso [] ******************************************************************************/ 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 */ /**Function******************************************************************** Synopsis [Simulate all the events in the queue.] Description [Simulate all the events in the queue.] SideEffects [Events are freed when the events are executed.] SeeAlso [optional] ******************************************************************************/ 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 */ /**Function******************************************************************** Synopsis [This function is called when control events (th1,th2 and th3) are encountered. The time frame represented in the queue is increased by half and the time stamps on the control events are updated to reflect the same. Events earlier beyond th1 are bow brought into the wheel.] SideEffects [None] SeeAlso [] ******************************************************************************/ 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 */ /**Function******************************************************************** Synopsis [Insert fanouts of currently simulated node into a table.] SideEffects [None] SeeAlso [] ******************************************************************************/ 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 */ /**Function******************************************************************** Synopsis [Fanouts of currently simulated events are scheduled to be simulated at a later time.] SideEffects [None] SeeAlso [] ******************************************************************************/ 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 */ /**Function******************************************************************** Synopsis [Schedule an event.] SideEffects [None] SeeAlso [] ******************************************************************************/ 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 */ /**Function******************************************************************** Synopsis [Reschedule an event.] SideEffects [None] SeeAlso [] ******************************************************************************/ 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 */ /**Function******************************************************************** Synopsis [Cancel an event.] SideEffects [None] SeeAlso [] ******************************************************************************/ 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 */ /**Function******************************************************************** Synopsis [Insert newly scheduled events to the event queue.] Description [Insert newly scheduled events to the event queue. The time stamp of the event is used to access the slot in the event table. If events already exist at the event's time stamp, this event is inserted in a vertical list.] SideEffects [Event queue is updated] SeeAlso [InsertInputEvents] ******************************************************************************/ 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 */ /**Function******************************************************************** Synopsis [Initialize the queue.] SideEffects [None] SeeAlso [] ******************************************************************************/ 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 */ /**Function******************************************************************** Synopsis [Increase memory for the freeList.] SideEffects [None] SeeAlso [] ******************************************************************************/ 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 */ /**Function******************************************************************** Synopsis [Free Truesim_t data structure stored in an st_table.] SideEffects [None] SeeAlso [None] ******************************************************************************/ 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 */