Logo Search packages:      
Sourcecode: heaplayers version File versions

sim.cxx

// main.c
// ------
//          Copyright 1988 D.C. Lindsay at Carnegie Mellon University
//
// Part of Hyperswitch simulation.
// Contains main() and the scheduled actions.

// 5nov88: variant that assumes that intermediate nodes have setup logic
// per-link, so needn't check for node-busy except @ source, dest.

#include <stdlib.h>
#include <iostream>
#include "node.h"
#include "statistics.h"
#include "measure.h"
#include "choose.h"
#include "chart.h"
#include "xrand.h"
#include "message.h"

#ifdef REFGC
#include "Ref.h"
#endif

using namespace std;

extern chooseclass choose;    // Only instance

extern void xgen();

// CODING CONVENTIONS
// All pointers have a leading p, ie the l'th thing is found @pl.
//
// A link# is 0,1,2,3,4,5.. as opposed to a dimension which is the bitmask 
// representation, ie 0, 1, 2, 4, 8...   A linkset is the OR of bitmasks.
//
// At each node, the link having data come in, is lin. Data out, is lout.
// The prev node is the one sending data to you: his lout has the same
// link# as your lin. Pointer plin points to the local one: pprevlout points
// to the one sending to plin.
// Similarly, the next node is the one I send data to: his lin has the 
// same link# as my lout. Pointer plout points to the local one: pnextlin
// points to the one my lout is sending to.
//
// "here" is the node# we're at. Prev and next are upstream and downstream.
// "source" is where the message started and "dest" is where it's going.
//
// phin -> the header that was sent here. Readonly, since it is stored in
//    the lout of prev.
// phout -> the header that we are sending out. If we change lout, it has
//    to be copied.
// pm-> the message. You may store statistics here. Each lout keeps a copy
//    of pm, so the same message is referenced from all places in the path.
//
// All messages indicating out-of-normal events print "ERROR" so that
// "fgrep ERROR" will find all of them.

//=============================================
// predeclarations
void incoming( const int );   
void messagerestart( const SMessagePtr pm );
void thread_generator( nodenum );

//    DATA
// For an unknown reason, this blows the optimizer away.
//schedulerclass scheduler;

schedulerclass* scheduler;
//node nodes[ MAX_CUBE_SIZE ];
node* nodes;
measureclass measure;
chartclass nodemax(1);

// the following are settable from scripts
int k_ness = 2;                     // default is k(k-1)
int ram_port_limit = 1;             // # of ports to/from RAM at once
int retry_count = 0;
float ensemble_interarrival = 0.0;        // mean time for dist'n
float node_interarrival = 0.0;
float thread_interarrival = 0.0;
int random_seed = 505;
int cube_size = MAX_CUBE_SIZE;
int cube_order = MAX_CUBE_ORDER;
int thread_count = 0;               // # of threads on each node
                              // 0 == infinite.
int message_length = DEFAULT_MESG_LEN;
bool call_xgen = false;
bool pull_piggyback = false;        // pull header in k(k-1) hdr or sep?
int pulled_message_length = 0;            // nonzero puts in pull mode
int pull_time = QUEUE_LATENCY;
int message_trace_switch = 0;       // nonzero causes verbose
                              // if makefile defines DOMESG

extern const int bitmask[];
const int bitmask[] = {       //bitmask[i] is 2**i
   0x1,           0x2,        0x4,        0x8,
   0x10,          0x20,       0x40,       0x80,
   0x100,         0x200,            0x400,            0x800,
   0x1000,        0x2000,           0x4000,           0x8000,
   0x10000, 0x20000,    0x40000,    0x80000 };

// counts not tied to message postmortem
int sourcebusycount = 0;      // had to wait until source wasn't busy
int sourcelinksbusy = 0;      // had to wait until source had free links
int collisioncount = 0;       // had to nak a probe: collision on link

//===============================
//===============================
void fatal( nodenum here, char *formatstring, int insertedarg ) {
  cout << "ERROR at " << here << ": " ;
  //  cout << "ERROR at " << hex(here) << ": " ;
  printf (formatstring, insertedarg);
  //  << form( formatstring, insertedarg )
  cout NL;
   exit(1);
}

//===============================
void noderangecheck( nodenum n ) {
   if( n < 0 || n >= cube_size ) 
      fatal( 0, "out of range node number: %x", n );
}

//===============================
void linkrangecheck( linknum l ) {
   if( l < 0 || l >= cube_order ) 
      fatal( 0, "out of range link number %d", l );
}

#define hex(X) X

//===============================
void printheader( header& h ) {
   cout     << " header[ dest "     << hex( h.dest )
        << " distance "       << ( h.distance )
        << " historytag "     << hex( h.historytag ) << " ]";
}
//===============================
void display( nodenum here, SMessagePtr pm, char *string ) {
   cout     << "Mesg from " << hex(pm->source)
      << " at node " << hex(here)
      << " Time " << (unsigned long) scheduler->clock
      << " "      << string;
   
}
//===============================
//
// sidesum returns the count of the 1 bits in arg.
// Only examines the low cube_order bits.

int sidesum( int arg ) {
   int sum = 0;
   for( int i=0; i < cube_order; i++ ) {
      if( arg & 1 ) sum++;
      arg >>= 1;
   }
   return sum;
}
//===============================
//
// Enqueue an action on a node

void nodepost( node* n, IntAction act, int i ) {
   LinkedListPtr pnew;
#ifdef REFGC
   pnew.New();
#else
   pnew = new linkedlist;
#endif
   pnew-> thisevent.tag = INT;
   pnew-> thisevent.iact = act;

   pnew-> thisevent.arg.i = i;

   LinkedListPtr prear = n-> eventq;
   if( prear == NULLO ) prear = pnew;
   pnew-> next = prear-> next;
   prear-> next = pnew;
   n-> eventq = pnew;
   n-> eventqcount++;
   if( n-> eventqmax < n-> eventqcount ) n-> eventqmax = n-> eventqcount;
}

void nodepost( node* n, PMAction act, SMessagePtr pm ) {
   LinkedListPtr pnew;
#ifdef REFGC
   pnew.New();
#else
   pnew = new linkedlist;
#endif
   pnew-> thisevent.tag = PM;
   pnew-> thisevent.pmact = act;
   pnew-> thisevent.arg.pm = pm;
   
   LinkedListPtr prear = n-> eventq;
   if( prear == NULLO ) prear = pnew;
   pnew-> next = prear-> next;
   prear-> next = pnew;
   n-> eventq = pnew;
   n-> eventqcount++;
   if( n-> eventqmax < n-> eventqcount ) n-> eventqmax = n-> eventqcount;
}

//===============================
//
// Expects this node just became non-busy.
// Checks for any actions waiting for that, schedules one of them.

void nodewakeup( node *n ) {
   if( n-> eventq != NULLO ) {      // work to schedule
      n-> eventqcount--;
      LinkedListPtr prear = n-> eventq;   
      LinkedListPtr pfront = prear-> next;
      prear-> next = pfront-> next; // link front out
      if( prear == pfront ) n-> eventq = NULLO;
      
      switch (pfront->thisevent.tag) {
       case INT:
       scheduler->post(pfront->thisevent.iact,
                   pfront->thisevent.arg.i,
                   QUEUE_LATENCY );
       break;
       case PM:
       scheduler->post(pfront->thisevent.pmact,
                   pfront->thisevent.arg.pm,
                   QUEUE_LATENCY );
       break;
      }
#ifndef REFGC
      delete pfront;
#endif
   }
}
//===============================
//
// Action: a node receives an ack from a node he sent a header to.
// Arg is node/link that the header went out.
// Time is the trailing edge of the ack logic, that is, it is OK to become
// free now, rather than after some further delay.

void ackresponse ( const int arg ) {
   nodenum here = NODE(arg);
   linknum lout = LINK(arg);

   struct node *phere = &nodes[here];
   struct link *plout = &phere->links[lout];
   SMessagePtr pm = plout-> pm;

   choose.noteack( here, lout, pm );      // record the ack

   if( here == pm-> source ) {
      // We are the message source, and the setup is OK.
      // The dest will wake up when the data flow is over.
      if( phere-> status == nodefree )
       fatal( here, "ack found not-busy", 0 );
      // become not-busy, and wake up anyone waiting for that
      // The RAM port has already been allocated & stays that way.
      phere-> status = nodefree;
      nodewakeup( phere );

      if( TRACE ) display( here, pm, "setup complete\n" );
      return;     
   }
   // We are an intermediate, and the setup is OK.
   // Propagate the ack
   linknum lin = plout-> lin;             
   nodenum prev = here ^ bitmask[ lin ];
   scheduler->post(&ackresponse, NODELINK(prev,lin),
               XBAR_LATENCY + LINK_LATENCY );
   if( TRACE ) display( here, pm, "setup ack'd\n" );
}
//===============================
//
// Action: a node receives a nak response from a node he sent a header to.
// Arg is node/link that the header went out.

void nakresponse ( const int arg ) {
   nodenum here = NODE(arg);
   linknum lout = LINK(arg);
   
   struct node *phere = &nodes[here];
   struct link *plout = &phere->links[lout];
   struct header *phout = &plout-> head;
   SMessagePtr pm = plout-> pm;
   linknum lin = plout-> lin;             // RAM, if this is source
   
   // free up the current lout and search for an untried one.
   // If none, then check if we are the source or intermediate.
   if( plout-> busy == false )
      fatal( here, "nak over unbusy link %d", lout );
   plout-> busy = false;
   choose.notenak( here, lout, pm );      // record the nak
   
   int linkset = here ^ (pm->dest); // including already used
   (phere-> historytag) ^= bitmask[ lout ];     // turn off failed
   linkset ^= bitmask[ lout ];                  // turn off failed
   
   int in_distance = (phout-> distance) + 1;
   
   if( (in_distance-1) > sidesum( phere-> historytag )) 
      phere-> historytag = 0;  //give up
   
   lout = choose.outlink( here, linkset, phere-> historytag );
   if( lout < 0 ) {
      // no available link except one(s) that nak'd.
      // The message must be nak'd or killed or retried.
      nodewakeup( phere );
      if( here == pm-> source ) {
       // The node is no longer doing setup, and becomes free
       phere-> status = nodefree;
       
       
       // The message came from here, so a RAM port was
       // allocated and must be freed.
       phere-> ram_port_count--;
       if( phere-> ram_port_count < 0 ) fatal( here,
                                     "nak to source with no RAM port", 0 );
       if( pm-> retrycount < retry_count ) {
          // message attempt is dead. However, we
          // are going to try again (exactly), after
          // some delay.
          pm-> retrycount++;
          if(TRACE)display(here,pm,"no paths, retry\n");
          PMAction arg_zero = &messagerestart;
          scheduler->post(arg_zero, pm, QUEUE_LATENCY );
//    scheduler->post(&messagerestart, pm, QUEUE_LATENCY );
          return;
       }
       // message is dead - no path found. Stats & done.
       if( TRACE ) display( here, pm, "no paths, failure\n");
       
       if( thread_count > 0 )       // thread can go again
          thread_generator( pm-> truesource );  
       measure.note( pm, nopaths );
       return;
      }
      // probing from this intermediate link has failed. Free,nak
      nodenum prev = here ^ bitmask[lin];
      phere-> links[lin].busy = false;          // free lin
      scheduler->post( &nakresponse, NODELINK( prev, lin ),
                   XBAR_LATENCY + LINK_LATENCY );
      if( TRACE ) display( here, pm, "propagating nak\n" );
      return;
   }
   // We have an untried lout. Probe over it.
   struct link *oldplout = plout;
   plout = &phere-> links[ lout ];
   plout-> busy = true;
   plout-> lin = lin;
   if( lin != RAM ) phere-> links[ lin ].lout = lout;
   pm-> probecount++;
   plout-> pm = pm;
   plout-> head.dest     = oldplout-> head.dest;
   plout-> head.distance = oldplout-> head.distance;
   plout-> head.historytag = phere-> historytag;      // note  bit now off
   if( TRACE ) {
      display( here, pm, "reprobing\n" );
      printheader( plout-> head );
      cout << " out dimension " << bitmask[ lout ] NL;
   }
   scheduler->post(&incoming, NODELINK( here, lout ),
               SWITCH_LATENCY + HEADER_LATENCY );
}
//===============================
//
// Action: a node receives a failure response from a node he sent a header to.
// Arg is node/link that the header went out.

void failureresponse ( const int arg ) {
   nodenum here = NODE(arg);
   linknum lout = LINK(arg);

   struct node *phere = &nodes[here];
   struct link *plout = &phere->links[lout];
   SMessagePtr pm = plout-> pm;
   nodenum next = here ^ bitmask[ lout ];

   // Message is dead. Free up, ripple nak back to source.
   if( plout-> busy == false )
      fatal( here, "failure nak over unbusy link %d", lout );
   plout-> busy = false;
   choose.notenak( here, lout, pm );      // record the nak
   nodewakeup( phere );

   if( here == pm-> source ) {
      phere-> status = nodefree;

      // The message came from here, so a RAM port was
      // allocated and must be freed.
      phere-> ram_port_count--;
      if( phere-> ram_port_count < 0 ) fatal( here,
                                    "failure to source with no RAM port", 0 );
      if( pm-> retrycount < retry_count ) {
       // measure would be dead, but will try again,
       // after some delay.
       pm-> retrycount++;
       if( TRACE ) display( here, pm, "failure, retry\n" );
       PMAction arg_zero = &messagerestart;
       scheduler->post(arg_zero,
                   pm, QUEUE_LATENCY );
//                scheduler->post(&messagerestart,
//                            pm, QUEUE_LATENCY );
       return;
      }
      // we are the source of a failed message.
      // Hardware is free, so just dispose of message.
      if( TRACE ) display( here, pm, "failure\n" );

      if( thread_count > 0 )        // thread can go again
       thread_generator( pm-> truesource );
      measure.note( pm, failure );
      return;
   }
   // message is dead, prev exists to be nak'd.
   linknum lin = plout-> lin;
   phere-> links[ lin ].busy = false;
   nodenum prev = here ^ bitmask[ lin ];
   if( TRACE ) display( here, pm, "propagating failure\n" );
   scheduler->post( &failureresponse, NODELINK( prev, lin ),
                XBAR_LATENCY + LINK_LATENCY );
}
//===============================
//
// Action: a message has completed. 
// The arg gives the node/link which is previous to someone who says so.
// Does teardown.

void sendfree( const int arg ) {
   nodenum here = NODE( arg );
   linknum lout = LINK( arg );

   struct node *phere = &nodes[here];
   struct link *plout = &phere->links[lout];
   if( plout-> busy == false ) 
      fatal( here, "teardown found lout %d not busy", lout );
   plout-> busy = false;
   if( plout-> lin == RAM ) {
      // This is the node getting the message from RAM,
      // i.e. teardown has reached the sender.
      // Free up the port to RAM.
      phere-> ram_port_count--;
      if( phere-> ram_port_count < 0 ) fatal( here,
                                    "teardown to source with no RAM port", 0 );

      // The extra RAM port may allow something to be started.
      if( phere-> status == nodefree ) nodewakeup( phere );

      // dispose of the message, if it's not still alive
      SMessagePtr pm = plout-> pm;
      if( pm-> reuse == false ) {
       if( thread_count > 0 )       // thread can go again
          thread_generator( pm-> truesource );
       measure.note( pm, completeOK );
      }
      else pm-> reuse = false;      // prevents 2nd use from
      // being un-measure-d. Guaranteed that this
      // assignment happens in the right order: the 2nd use
      // can't probe to its dest before the ack ripple
      // gets to this logic.
      if( TRACE ) display( here, pm, "teardown complete\n" );
   }else{
      // This is an intermediate node, and we must propagate the
      // teardown further. Assumed that this is a very low-level
      // hardware function (can be done in a few gate delays, even
      // when the node is busy with high-level activities).
      // Also, nobody waits for links, so no wakeup logic.
      linknum lin = plout -> lin;
      struct link *plin = &phere-> links[lin];
      if( plin-> busy == false ) 
       fatal( here, "teardown found lin %d not busy", lin );
      plin-> busy = false;
      nodenum prev = here ^ bitmask[ lin ];
      scheduler->post(&sendfree, NODELINK( prev, lin ),
                  XBAR_LATENCY + LINK_LATENCY );
      if( TRACE ) {
       SMessagePtr pm = plout-> pm;
       display( here, pm, "teardown\n" );
      }
   }
}
//===============================
//
// Action: a node becomes free (a message being received is over).
// An ack must be propagated backwards to cause teardown.
// The arg is the node/link of the destination.

void destfree ( const int arg ) {
   nodenum here = NODE( arg );
   linknum lin = LINK( arg );

   struct node *phere = &nodes[here];
   struct link *plin = &phere->links[lin];
   if( plin-> busy == false ) 
      fatal( here, "data termination but inlink wasn't busy", 0 );
   plin-> busy = false;

   // free up the port to RAM
   phere-> ram_port_count--;
   if( phere-> ram_port_count < 0 ) fatal( here,
                                 "message end with no RAM port", 0 );

   // we have a free port to RAM, so we may be able to become busy.
   // (If we are busy, the wakeup will happen after that.)
   if( phere-> status == nodefree ) nodewakeup( phere );

   nodenum prev = here ^ bitmask[ lin ];        // immediate sender
   scheduler->post( &sendfree, NODELINK( prev, lin ),
                XBAR_LATENCY + LINK_LATENCY );
   SMessagePtr pm = nodes[prev].links[lin].pm;
   if( TRACE ) display( here, pm, "teardown started\n" );

   // record the message's elapsed time
   pm-> lastbittime = scheduler->clock;

   // if the message wants to be executed, schedule his action
   if( pm->arrival != NULL ) {
      (pm->arrival)(pm);
   }
}
//===============================
//
// Action: a node should be marked not-busy.

void switchfree( const int arg ) {
   struct node *phere = &nodes[arg];
   if (phere->status == nodefree)
      fatal( arg, "switchfree found free node", 0 );
   phere-> status = nodefree;
   nodewakeup( phere );
}
//===============================
//
// Action: a message has arrived over a nonbusy link.
// The argument is the node/link# at the other end of that free link.
// Expects the sending node/link contains the message and header.
// Expects that this is the destination node.

void incomingdest( int arg ) {
   nodenum prev = NODE( arg );
   linknum lin = LINK( arg );       // same # there and here
   struct link *pprevlout = &nodes[prev].links[lin];
   SMessagePtr pm = pprevlout-> pm;
   nodenum here = prev ^ bitmask[ lin ];
   struct node *phere = &nodes[here];                 // this node
   struct link *plin = &phere->links[ lin ];          // this node

   // This is where the message is going.
   if( TRACE ) display( here, pm, "incoming probe" );

   if( phere-> status == nodebusy ) {
      // the addressing logic is busy, we can't know to send ack.
      scheduler->post( &nakresponse, arg, 
                   XBAR_LATENCY + LINK_LATENCY );
      if( TRACE ) cout << ": rejected, dest is busy\n";
      return;
   }
   if( phere-> ram_port_count >= ram_port_limit ) {
      // there isn't anywhere to put the data, so nak
      scheduler->post( &nakresponse, arg,
                   XBAR_LATENCY + LINK_LATENCY );
      if( TRACE ) cout << ": rejected, dest has no ports\n";
      return;
   }

   // we can accept the message. Sieze the hardware.
   plin-> busy = true;        
   phere-> status = nodebusy;
   phere-> ram_port_count++;

   scheduler->post(&ackresponse, arg, 
               SWITCH_LATENCY + LINK_LATENCY + XBAR_LATENCY );
   if( TRACE ) cout << ": accepted at dest\n";

   // Node stops being busy after one switch time.
   scheduler->post(&switchfree, here, SWITCH_LATENCY );

   // RAM port and link stop being busy after message ends.
   // This is computed as transit-times for ACK,
   // plus transit times for the leading data bit,
   // plus the bit times.
   delta messagetime =  // time until end of mesg
      SWITCH_LATENCY 
      // plus the time for data flow in to here
      + ((pm-> length) * LINK_BANDWIDTH );
   if( pulled_message_length == 0 ) messagetime +=      
      // Data is being pushed (sent to dest).
      // Add turnaround here, + a link time back,
      // + turnaround at source, + a link to here,
      // + that much again for each intermediate
      // (of which there were hopcount-1)
      // == s + 2(x+l) + (h-1)2(x+l) == s + (h)2(x+l)
      ((pm->hopcount) * 2 * (XBAR_LATENCY + LINK_LATENCY));
   else if( pull_piggyback == true ) messagetime +=
      // Data is being pulled ( sent to source ).
      // The length was extra header length, piggybacked into
      // the normal k(k-1) header.
      // Add time for MMU inspection (etc), plus the time
      // to shove the pulled data out the link.
      pull_time + (pulled_message_length * LINK_BANDWIDTH);
   else messagetime +=
      // Data is being pulled ( sent to source ).
      // The header specifying what to be pulled, must be
      // transferred as normal message data would be.
      ((pm->hopcount) * 2 * (XBAR_LATENCY + LINK_LATENCY)) +
      // Then, add time for building a response and sending.
      pull_time + (pulled_message_length * LINK_BANDWIDTH);
   scheduler->post( &destfree, NODELINK(here,lin), messagetime );
}
//===============================
//
// Action: a message has arrived over a free link.
// The argument is the node/link# at the other end of that free link.
// Expects the sending node/link contains the message and header.
// Expects that this is not the destination.

void incomingintermediate( int arg )
{
   nodenum prev = NODE( arg );
   linknum lin = LINK( arg );       // same # there and here
   struct link *pprevlout = &nodes[prev].links[lin];
   SMessagePtr pm = pprevlout-> pm;
   struct header *phin = &pprevlout-> head;
   nodenum here = prev ^ bitmask[ lin ];
   nodenum dest = pm-> dest;
   struct node *phere = &nodes[here];                 // this node
   struct link *plin = &phere->links[ lin ];          // this node
   if( TRACE ) display( here, pm, "incoming probe" );


   // intermediate. Seize hardware and propagate further
   plin-> busy = true;

   int linkset = here ^ dest;
   phere-> historytag = phin-> historytag ^ bitmask[lin];
   if( phin-> distance <= 1 ) phere-> historytag = linkset; // forget

   linknum lout = choose.outlink( here, linkset, phere-> historytag );
   if( lout < 0 ) {
      // no free outlink. Send nak, free the node and inlink.

      if( phere-> status == nodefree ) nodewakeup( phere );

      plin-> busy = false;
      scheduler->post( &nakresponse, arg,
                   SWITCH_LATENCY + LINK_LATENCY );
      if( TRACE ) cout << ": nak'd, no free links\n";
      return;
   }

   // intermediate probing further. Have found a free link.
   // The node remains busy during the path setup phase.

   struct link *plout = &phere->links[ lout ];
   plout-> busy = true;             // sieze the out link
   plout-> lin = lin;
   phere-> links[lin].lout = lout;
   pm-> hopcount++;
   pm-> probecount++;
   plout-> pm = pm;
   plout-> head.dest       = dest;
   plout-> head.distance   = phin-> distance - 1;
   plout-> head.historytag = phere-> historytag;
   if( TRACE ) {
      cout << ": forwarded\n";
      printheader( plout->head );
      cout << " out dimension " << bitmask[lout] NL;
   }
   scheduler->post(&incoming, NODELINK( here,lout ),
               SWITCH_LATENCY + HEADER_LATENCY );     
}
//===============================
//
// Action: a message has arrived over a link that was free very recently.
// The argument is the node/link# at the other end of that free link.
// Expects the sending node/link contains the message and header.

void incoming( const int arg ) {
   nodenum prev = NODE( arg );
   linknum lin = LINK( arg );       // same # there and here

   struct link *pprevlout = &nodes[prev].links[lin];
   SMessagePtr pm = pprevlout-> pm;
   nodenum here = prev ^ bitmask[ lin ];

   if (nodes[here].links[lin].busy == true ) {
      // Amazing! Link was seized during the wire time!
      collisioncount++;
      scheduler->post(&nakresponse, arg, 
                  XBAR_LATENCY + LINK_LATENCY );
      if( TRACE ) {
       display( here, pm, "incoming probe" );
       cout << ": link collision, nakking\n";
      }
      return;
   }
   if( here == pm->dest ) incomingdest( arg );
   else incomingintermediate( arg );
}
//===============================
//
// Action to start the message @arg.
// Expects the source node, and a RAM port, are free: siezes them.
// Expects the message to have a source, dest, length, starttime, retrycount.

void messagestartlink( SMessagePtr pm ) {
   pm-> hopcount = 1;
   pm-> probecount = 1;
   pm-> activetime = scheduler->clock;
   nodenum source = pm-> source;
   nodenum dest = pm-> dest;
   if( TRACE ) display( source, pm, "starting\n" );
   struct node *phere = &nodes[source];

   phere-> status = nodebusy;       //successfully siezed


   // compute set of possible outgoing links
   int linkset = source ^ dest;                 // exclusive or
   
   pm-> distance = sidesum( linkset );
   linknum lout = choose.outlink( source, linkset, linkset );
   if( lout < 0 ) {
      if( TRACE ) display( source, pm, "all links busy, waiting" );

      // The node becomes free in one switch time.
      scheduler->post( &switchfree, source, SWITCH_LATENCY );

      sourcelinksbusy++;
      nodepost( phere, &messagerestart, pm );
      //measure.note( pm, sourcequit );
      return;
   }
   struct link *plout = &phere-> links[lout];
   phere-> ram_port_count++;  // successfully siezed
   plout-> busy = true;       // successfully siezed
   plout-> lin = RAM;
   plout-> pm = pm;
   plout-> head.dest = dest;

   plout-> head.distance = pm-> distance - k_ness;
   phere-> historytag = linkset;          // remember the sent value
   plout-> head.historytag = linkset;
   if( TRACE ) {
      printheader( plout->head );
      cout << " sent on dimension " << bitmask[lout] NL;
   }

   // immediate dest should happen after one header transit time
   // ( == wire time + bandwidth time )
   // + the switch latency of setting up the output.
   scheduler->post( &incoming, NODELINK(source,lout), 
                SWITCH_LATENCY + HEADER_LATENCY );
}
//===============================
//
// Action: message @arg is woken up when source comes unbusy & can start.
// Expects the message to have a source, dest, length, starttime, retrycount,
// arrival, reuse.

void messagerestart( const SMessagePtr pm ) {
   nodenum source = pm->source;
   struct node *psource = &nodes[source];
   // seize source node if not busy, else re-sleep on node's queue
   if(( psource-> status == nodebusy ) ||
      ( psource-> ram_port_count >= ram_port_limit)) {
      sourcebusycount++;
      if( TRACE ) display( source, pm,
                     "restarting:  source busy, pause.\n" );
      nodepost( psource, &messagerestart, pm );
   }else{
      messagestartlink( pm );
   }
}
//===============================
//
// Action: cause the message @arg to be started up.
// Expects the message to have a source, dest, length, arrival, reuse.
// Ignores requests if source = dest, or if source or dest are broken.

void messagestart( const SMessagePtr pm ) {
   pm-> starttime = pm-> activetime = scheduler->clock;
   pm-> retrycount = 0;
   nodenum source = pm-> source;
   nodenum dest = pm-> dest;
   struct node *psource = &nodes[source];
   if( (source == dest) || (psource-> broken == true) 
       || (nodes[dest].broken == true) ) {
      measure.note( pm, ignored );
      if( thread_count > 0 )              // thread can now..
       thread_generator( source );  // have next message.

      if( TRACE ) display( source, pm, "starting: IGNORED.\n" );
      return;
   }
   // sieze source node if not busy, else sleep on node's queue
   if(( psource-> status == nodebusy ) ||
      ( psource-> ram_port_count >= ram_port_limit)) {
      sourcebusycount++;
      if( TRACE ) display( source, pm,
                     "starting:  source busy, pause.\n" );
      nodepost( psource, &messagerestart, pm );
   }else{
      messagestartlink( pm );
   }
}
//===============================
void initcube()
{
   for( nodenum n = 0; n < cube_size; n++ ) {
      nodes[n].status = nodefree;
      nodes[n].ram_port_count = 0;
      nodes[n].broken = false;
      nodes[n].eventq = NULLO;
      nodes[n].eventqcount = 0;
      nodes[n].eventqmax = 0;
      for( linknum l = 0; l < cube_order; l++ ) {
       nodes[n].links[l].busy = false;
       nodes[n].links[l].broken = false;
      }
   }

}
//===============================
void sanitycheck()      // check cube has no "busy" links or nodes
{
   cout << "[Sanity check: ";
   for( nodenum n = 0; n < cube_size; n++ ) {
      if((nodes[n].broken == true  && nodes[n].status != nodebusy)||
       (nodes[n].broken == false && nodes[n].status != nodefree)||
       (nodes[n].ram_port_count ) ||
       (nodes[n].eventq ))
       cout << " node " << hex(n);
      if(nodes[n].eventq != NULLO ) cout << " nodelist " << hex(n);
      bool nodeprinted = false;
      for( linknum l = 0; l < cube_order; l++ ) {
       if( nodes[n].links[l].broken != 
           nodes[n].links[l].busy ) {
          if( nodeprinted == false )
             cout << "\n[node " << hex(n) 
                << " dims ";
          nodeprinted = true;
          cout << hex(bitmask[l]);
       }
      }
      if( nodeprinted == true ) cout << "]";
   }
   cout << "]\n";
}
//===============================
#define E   if(cin.rdstate() != 0) goto fail

void inventwork() // post some work to be done
{
   cout << "[Reading stdin for initial work:\n";
   bool havework = false;
   char string[ 256 ];
   while( cin >> string ) {         // stops on EOF
      switch( string[0] ) {
       case 'm':{       // message <source> <dest>
          nodenum num;
          SMessagePtr pm = measure.generate();
          cin >> num;E;noderangecheck(num); pm-> source = num;
          
          cin >> num;E;noderangecheck(num); pm-> dest   = num;
          pm-> truesource = pm-> source;
          pm-> length = message_length;
          pm-> arrival = &messagebody;
          pm-> reuse = false;
          PMAction arg_zero = &messagerestart;
          scheduler->post( arg_zero, pm, 0 );
//                scheduler->post( &messagestart, pm, 0 );
          cout << " Message from " << hex(pm->source)
             << " to " << hex(pm->dest) NL;
          havework = true;
          break;
       }
       case 's': {            // size <message length in bits>
          cin >> message_length; E;
          if(message_length < 32 || message_length > 100000000)
             fatal( 0, "illegal message length", 0 );
          cout << " Message length now " << message_length 
             << " bits.\n";
          break;
       }
       case 'c': {            // cube <cube order>
          cin >> cube_order; E;
          if( cube_order < 2 || cube_order > MAX_CUBE_ORDER ) 
             fatal( 0, "illegal cube order.", 0 );
          cout << " Cube order now " << cube_order NL;
          cube_size = bitmask[ cube_order ];
          break;
       }
       case '#': {                  // comment: just echo.
          cout << " " << string;
          cin.get( string, 255 );         // read rest of line
          cout << string NL;
          break;
       }
       case 'v': {                  // toggle verbose
          message_trace_switch ^= 1;
          cout << " Verbose mode now " << 
             (message_trace_switch? "on\n" : "off\n" );
          break;
       }
       case 'l': {            // linkbreak <node> <link>
          nodenum n;
          cin >> n; E; noderangecheck(n);
          linknum l;
          cin >> l; E; linkrangecheck(l);
          nodes[n].links[l].busy = true;
          nodes[n].links[l].broken = true;
          cout << " Marking link broken, node " << hex(n)
             << " link " << l << ".\n";
          break;
       }
       case 'n': {            // nodebreak <node#>
          nodenum n;
          cin >> n; E; noderangecheck(n);
          nodes[n].status = nodebusy;
          nodes[n].broken = true;
          cout << " Marking node " << hex(n) << " broken.\n";
          break;
       }
       case 'p': 
          if( string[1] == 'o') {         // ports <num>
             cin >> ram_port_limit; E;
             if((ram_port_limit < 1)||(ram_port_limit > 10))
              fatal( 0, "out of range RAM port %d",
                   ram_port_limit );
             cout << "Now "<< ram_port_limit 
                << " ports to RAM.\n";
             break;
          }else if( string[1] == 'u' ) {  // pull <hsize> <t>
             pulled_message_length = message_length;
             cin >> message_length; E;
             if( message_length < 0 ) {
                              // piggyback pull info on header
              message_length = - message_length;
              pull_piggyback = true;
             }
             if( message_length < 32 || 
               message_length > 200 )
              fatal( 0, "illegal header size", 0);
             cin >> pull_time; E;
             if( pull_time < QUEUE_LATENCY ||
               pull_time > RECEIVE_LATENCY )
              fatal( 0, "illegal pull latency", 0 );
             cout << " Now pulling messages of length "
                << pulled_message_length
                << " by sending header of length "
                << message_length
                << "\n\tand waiting "
                << pull_time
                << " nanoseconds on RAM/MMU.\n";
             if( pull_piggyback == true ) 
              cout << " Pull header piggybacked into ";
             else cout << " Pull header separate from ";
             cout << "the switching header.\n";
             break;
          }else goto fail;
       case 'r': {            // retry <num>
          cin >> retry_count; E;
          if((retry_count < 0) || (retry_count > 1000 )) 
             fatal( 0, "Retry count %d: out of range", 
                  retry_count);
          cout << "Failed messages now retry " << retry_count
             << " times.\n";
          break;
       }
       case 't': {            // threads <n>
          cin >> thread_count; E;
          if(( thread_count < 0) || (thread_count > 10 ))
             fatal( 0, "Thread count %d: out of range",
                  thread_count );
          cout << "Thread count per node now "
             << thread_count NL;
          thread_interarrival = node_interarrival *thread_count;
          break;
       }
       case 'g': {            // generate <mean> <seed> <cnt><cnt>
          int mean;
          cin >> mean; E;
          if((mean < 0 ) || (mean > 1000000000)) 
             fatal( 0, "Interarrival time %d: range",
                  mean);
          cin >> random_seed; E;
          if( random_seed == 0 ) random_seed = (int)&mean;
          rnd_init( random_seed );
          int initial; cin >> initial; E;
          int useful;  cin >> useful;  E;
          if( initial < 0 || useful < 1 ) 
             fatal( 0, "Message counts: out of range",0);
          measure.runsize( initial, useful );   //set them
          if( mean == 0 ) {
             ensemble_interarrival = 0.0;
             node_interarrival = 0.0;
             thread_interarrival = 0.0;
             cout << " Message generator disabled.";
          }else{
             havework = true;
             node_interarrival = (float)mean;
             thread_interarrival = node_interarrival 
              * thread_count;
             ensemble_interarrival =
              node_interarrival / cube_size;
             cout << " Generating messages with inter"
                << "arrival mean of " << mean
                << " nanoseconds per node.\n"
                << " Stats will ignore the initial "
                << initial << " messages "
                << "\n  and will be based on the "
                << "subsequent " << useful
                << " messages.\n";
          }
          cout    << " Random seed " << random_seed << ".\n";
          break;
       }
       case 'x': {
          call_xgen = true;
          cout << "Xternal generator will be called.\n";
          havework = true;
          break;
       }
       case 'k': {
          cin >> k_ness; E;
          if( k_ness < 1 || k_ness > 20 )
             fatal( 0, "illegal k_ness", 0 );
          cout << " K-ness now " << k_ness NL;
          break;
       }
       case 'q': goto done;
          fail:         default:
          cout    << "SYNTAX ERROR in stdin, quitting.\n"
                  << "TRY:"
                  << "\tcubeorder <number>\n"
                        // d for distributed generator
                  << "\tgenerate <meantime> <seed>"
                  << " <initial#> <useful#>\n"
                  << "\tkness <k>\n"
                  << "\tlinkbreak <node#> <link#>\n"
                  << "\tnodebreak <node#>\n"
                  << "\tmessage <source> <dest>\n"
                  << "\tports <number>\n"
                  << "\tpull <headersize> <pausetime>"
                  << "   (-ve header is piggybacked)\n"
                  << "\tretry  <number>\n"
                  << "\tsize <message size in bits>\n"
                  << "\tthreads <n>      per node\n"
                  << "\tquit\n"
                  << "\tverbose\n"
                  << "\txternalgenerator\n"
                  << "\t#comment\n";
          exit(1);
       }
   }
   done:
   cout << "]\n";
   if( havework == false ) {
      cout << "ERROR: Script specified no work. Quitting.\n";
      exit(0);
   }
}
//===============================
void computenodemax()
{
   for( nodenum n = 0; n < cube_size; n++ ) 
      nodemax.note( nodes[n].eventqmax );
}
//===============================
void printsummary()
{
   cout << "Assuming message size " << (message_length/8) << " bytes"
      << " and a " << cube_order << "-cube.\n"
      << " Random seed " << random_seed 
      << ".\n";
   if( ensemble_interarrival == 0.0 ) 
      cout  << "Message generator suppressed.\n";
   else     cout  << " Mean interarrival time " 
            << node_interarrival
            << " ns/node, "
            << thread_interarrival
            << " ns/thread, "
            << ensemble_interarrival
            << " ns/ensemble\n";

   if( retry_count == 0 )     cout << "Retry suppressed.\n";
   else                 cout << "Retry count " << retry_count NL;

   cout << ram_port_limit << " ports to/from RAM.\n";
   cout << thread_count << " threads per node.\n";

   scheduler->print( "nanoseconds" );
   cout NL;

   cout << " Source busy,waited " << sourcebusycount;
   cout << " Links collisions " << collisioncount;
   cout NL;
   cout << " Source no free links, waited " << sourcelinksbusy;
   cout NL;

   measure.finalize();
   computenodemax();    // does note's
   nodemax.print( "Node eventq highwater:" );
}
//===============================
//
// Creates a message and starts it.
// Is given source. Uses equiprobable random for dest ( source != dest ).
// If message.generate returns NULLO, just returns.

void launch( const int arg ) {
   nodenum source = arg;

   SMessagePtr pm = measure.generate();
   if( pm == NULLO ) choose.sanitycheck();
   else{
      // We are supposed to continue generating.

      // Generate random dest != source
      pm-> source = source;
      pm-> truesource = source;
      for(;;) {
       pm-> dest = rnd_ri( cube_size );
       if( pm-> source != pm-> dest ) break;
      }
      // launch the message
      pm-> length = message_length;
      pm-> arrival = &messagebody;
      pm-> reuse = false;
      messagestart( pm );
   }
}
//===============================
//
// Called to schedule a (future) message launch.
// Uses negative exponential distribution for time between messages,
// with mean of "thread_interarrival" (which is assumed > 0.0).
// RECEIVE_LATENCY happens before dist'n is applied.
// Is given source. Uses equiprobable random for dest ( source != dest ).

void thread_generator( nodenum source )
{
   double ddelta = rnd_nexp( thread_interarrival );   
   scheduler->post( &launch, source, ((delta)ddelta) + RECEIVE_LATENCY );
}
//===============================
//
// Runs thread_count thread_generator's (see) per node. 

void node_generate()
{
   for( int i = 0; i < thread_count; i++ ) 
      for( nodenum n = 0; n < cube_size; n++ ) 
       thread_generator( n );
}
//===============================
//
// Action: is called, once, and reschedules itself.
// Each time, will insert a message into the system.
// Uses negative exponentiontial distribution for time between messages,
// with mean of "ensemble_interarrival" (which is assumed > 0.0).
// Uses equiprobable randoms for source & dest ( source != dest ).
// If message.generate returns NULLO, just returns.

void ensemble_generator( const int dummyarg ) {
   SMessagePtr pm = measure.generate();
   if( pm == NULLO ) choose.sanitycheck();
   else{
      // We are supposed to continue generating.

      // Generate random source & dest (not equal )
      pm-> source = rnd_ri( cube_size );
      pm-> truesource = pm-> source;
      for(;;) {
       pm-> dest = rnd_ri( cube_size );
       if( pm-> source != pm-> dest ) break;
      }
      // launch the message
      pm-> length = message_length;
      pm-> arrival = &messagebody;
      pm-> reuse = false;
      messagestart( pm );

      // generate a time delta until the next message
      double ddelta = rnd_nexp( ensemble_interarrival );
      scheduler->post( &ensemble_generator, 0, (delta)ddelta );
   }  
}
//===============================
main()
{
   int s;
   scheduler = new schedulerclass;
   nodes = new node[ MAX_CUBE_SIZE ];
#ifdef REFGC
   RefAny::heap.SetStackHigh(&s);
#endif  


   cout << 
      "Dynamic routing simulation 1.0 - Copyright 1988 Archons/CMU\n";
   initcube();
   rnd_init( random_seed );
   inventwork();
   sanitycheck();
   if( thread_count > 0 ) node_generate();
   else if( ensemble_interarrival > 0.0 ) ensemble_generator(0);
   else if( call_xgen == true ) xgen();
   choose.start();                              // may post
   scheduler->run();
   cout << "--------- Done ------------------------\n";
   choose.sanitycheck();
   sanitycheck();
   printsummary();
   delete scheduler;
   delete nodes;
   exit(0);
}

Generated by  Doxygen 1.6.0   Back to index