From 7f49fe9feb174d34efc2a011bad79b38522a360b Mon Sep 17 00:00:00 2001
From: Dongdong Li <qqlddg@gmail.com>
Date: Thu, 8 Aug 2013 00:15:58 -0800
Subject: Intesim2 Integration Details: See Review 80001
 https://gpgpu-sim-code-review.appspot.com/80001/

[git-p4: depot-paths = "//depot/gpgpu_sim_research/fermi/distribution/": change = 16747]
---
 src/intersim2/networks/anynet.cpp | 501 ++++++++++++++++++++++++++++++++++++++
 1 file changed, 501 insertions(+)
 create mode 100644 src/intersim2/networks/anynet.cpp

(limited to 'src/intersim2/networks/anynet.cpp')

diff --git a/src/intersim2/networks/anynet.cpp b/src/intersim2/networks/anynet.cpp
new file mode 100644
index 0000000..4db1dfb
--- /dev/null
+++ b/src/intersim2/networks/anynet.cpp
@@ -0,0 +1,501 @@
+// $Id: anynet.cpp 5354 2012-11-07 23:51:49Z qtedq $
+
+/*
+ Copyright (c) 2007-2012, Trustees of The Leland Stanford Junior University
+ All rights reserved.
+
+ Redistribution and use in source and binary forms, with or without
+ modification, are permitted provided that the following conditions are met:
+
+ Redistributions of source code must retain the above copyright notice, this 
+ list of conditions and the following disclaimer.
+ Redistributions in binary form must reproduce the above copyright notice, this
+ list of conditions and the following disclaimer in the documentation and/or
+ other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
+ ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
+ ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
+ ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+/*anynet
+ *
+ *Network setup file format
+ *example 1:
+ *router 0 router 1 15 router 2
+ *
+ *Router 0 is connect to router 1 with a 15-cycle channel, and router 0 is connected to
+ * router 2 with a 1-cycle channel, the channels latency are unidirectional, so channel 
+ * from router 1 back to router 0 is only single-cycle because it was not specified
+ *
+ *example 2:
+ *router 0 node 0 node 1 5 node 2 5
+ *
+ *Router 0 is directly connected to node 0-2. Channel latency is 5cycles for 1 and 2. In 
+ * this case the latency specification is bidirectional, the injeciton and ejection lat
+ * for node 1 and 2 are 5-cycle
+ *
+ *other notes:
+ *
+ *Router and node numbers must be sequential starting with 0
+ *Credit channel latency follows the channel latency, even though it travels in revse
+ * direction this might not be desired
+ *
+ */
+
+#include "anynet.hpp"
+#include <fstream>
+#include <sstream>
+#include <limits>
+#include <algorithm>
+//this is a hack, I can't easily get the routing talbe out of the network
+map<int, int>* global_routing_table;
+
+AnyNet::AnyNet( const Configuration &config, const string & name )
+  :  Network( config, name ){
+
+  router_list.resize(2);
+  _ComputeSize( config );
+  _Alloc( );
+  _BuildNet( config );
+}
+
+AnyNet::~AnyNet(){
+  for(int i = 0; i < 2; ++i) {
+    for(map<int, map<int, pair<int,int> > >::iterator iter = router_list[i].begin();
+	iter != router_list[i].end();
+	++iter) {
+      iter->second.clear();
+    }
+  }
+}
+
+void AnyNet::_ComputeSize( const Configuration &config ){
+  file_name = config.GetStr("network_file");
+  if(file_name==""){
+    cout<<"No network file name provided"<<endl;
+    exit(-1);
+  }
+  //parse the network description file
+  readFile();
+
+  _channels =0;
+  cout<<"========================Network File Parsed=================\n";
+  cout<<"******************node listing**********************\n";
+  map<int,  int >::iterator iter;
+  for(iter = node_list.begin(); iter!=node_list.end(); iter++){
+    cout<<"Node "<<iter->first;
+    cout<<"\tRouter "<<iter->second<<endl;
+  }
+
+  map<int,   map<int, pair<int,int> > >::iterator iter3;
+  cout<<"\n****************router to node listing*************\n";
+  for(iter3 = router_list[0].begin(); iter3!=router_list[0].end(); iter3++){
+    cout<<"Router "<<iter3->first<<endl;
+    map<int, pair<int,int> >::iterator iter2;
+    for(iter2 = iter3->second.begin(); 
+	iter2!=iter3->second.end(); 
+	iter2++){
+      cout<<"\t Node "<<iter2->first<<" lat "<<iter2->second.second<<endl;
+    }
+  }
+
+  cout<<"\n*****************router to router listing************\n";
+  for(iter3 = router_list[1].begin(); iter3!=router_list[1].end(); iter3++){
+    cout<<"Router "<<iter3->first<<endl;
+    map<int, pair<int,int> >::iterator iter2;
+    if(iter3->second.size() == 0){
+      cout<<"Caution Router "<<iter3->first
+	  <<" is not connected to any other Router\n"<<endl;
+    }
+    for(iter2 = iter3->second.begin(); 
+	iter2!=iter3->second.end(); 
+	iter2++){
+      cout<<"\t Router "<<iter2->first<<" lat "<<iter2->second.second<<endl;
+      _channels++;
+    }
+  }
+
+  _size = router_list[1].size();
+  _nodes = node_list.size();
+
+}
+
+
+
+void AnyNet::_BuildNet( const Configuration &config ){
+  
+
+  //I need to keep track the output ports for each router during build
+  int * outport = (int*)malloc(sizeof(int)*_size);
+  for(int i = 0; i<_size; i++){outport[i] = 0;}
+
+  cout<<"==========================Node to Router =====================\n";
+  //adding the injection/ejection chanenls first
+  map<int,   map<int, pair<int,int> > >::iterator niter;
+  for(niter = router_list[0].begin(); niter!=router_list[0].end(); niter++){
+    map<int,   map<int, pair<int,int> > >::iterator riter = router_list[1].find(niter->first);
+    //calculate radix
+    int radix = niter->second.size()+riter->second.size();
+    int node = niter->first;
+    cout<<"router "<<node<<" radix "<<radix<<endl;
+    //decalre the routers 
+    ostringstream router_name;
+    router_name << "router";
+    router_name << "_" <<  node ;
+    _routers[node] = Router::NewRouter( config, this, router_name.str( ), 
+    					node, radix, radix );
+    _timed_modules.push_back(_routers[node]);
+    //add injeciton ejection channels
+    map<int, pair<int,int> >::iterator nniter;
+    for(nniter = niter->second.begin();nniter!=niter->second.end(); nniter++){
+      int link = nniter->first;
+      //add the outport port assined to the map
+      (niter->second)[link].first = outport[node];
+      outport[node]++;
+      cout<<"\t connected to node "<<link<<" at outport "<<nniter->second.first
+	  <<" lat "<<nniter->second.second<<endl;
+      _inject[link]->SetLatency(nniter->second.second);
+      _inject_cred[link]->SetLatency(nniter->second.second);
+      _eject[link]->SetLatency(nniter->second.second);
+      _eject_cred[link]->SetLatency(nniter->second.second);
+
+      _routers[node]->AddInputChannel( _inject[link], _inject_cred[link] );
+      _routers[node]->AddOutputChannel( _eject[link], _eject_cred[link] );
+    }
+
+  }
+
+  cout<<"==========================Router to Router =====================\n";
+  //add inter router channels
+  //since there is no way to systematically number the channels we just start from 0
+  //the map, is a mapping of output->input
+  int channel_count = 0; 
+  for(niter = router_list[0].begin(); niter!=router_list[0].end(); niter++){
+    map<int,   map<int, pair<int,int> > >::iterator riter = router_list[1].find(niter->first);
+    int node = niter->first;
+    map<int, pair<int,int> >::iterator rriter;
+    cout<<"router "<<node<<endl;
+    for(rriter = riter->second.begin();rriter!=riter->second.end(); rriter++){
+      int other_node = rriter->first;
+      int link = channel_count;
+      //add the outport port assined to the map
+      (riter->second)[other_node].first = outport[node];
+      outport[node]++;
+      cout<<"\t connected to router "<<other_node<<" using link "<<link
+	  <<" at outport "<<rriter->second.first
+	  <<" lat "<<rriter->second.second<<endl;
+
+      _chan[link]->SetLatency(rriter->second.second);
+      _chan_cred[link]->SetLatency(rriter->second.second);
+
+      _routers[node]->AddOutputChannel( _chan[link], _chan_cred[link] );
+      _routers[other_node]->AddInputChannel( _chan[link], _chan_cred[link]);
+      channel_count++;
+    }
+  }
+
+  buildRoutingTable();
+
+}
+
+
+void AnyNet::RegisterRoutingFunctions() {
+  gRoutingFunctionMap["min_anynet"] = &min_anynet;
+}
+
+void min_anynet( const Router *r, const Flit *f, int in_channel, 
+		 OutputSet *outputs, bool inject ){
+  int out_port=-1;
+  if(!inject){
+    assert(global_routing_table[r->GetID()].count(f->dest)!=0);
+    out_port=global_routing_table[r->GetID()][f->dest];
+  }
+ 
+
+  int vcBegin = 0, vcEnd = gNumVCs-1;
+  if ( f->type == Flit::READ_REQUEST ) {
+    vcBegin = gReadReqBeginVC;
+    vcEnd   = gReadReqEndVC;
+  } else if ( f->type == Flit::WRITE_REQUEST ) {
+    vcBegin = gWriteReqBeginVC;
+    vcEnd   = gWriteReqEndVC;
+  } else if ( f->type ==  Flit::READ_REPLY ) {
+    vcBegin = gReadReplyBeginVC;
+    vcEnd   = gReadReplyEndVC;
+  } else if ( f->type ==  Flit::WRITE_REPLY ) {
+    vcBegin = gWriteReplyBeginVC;
+    vcEnd   = gWriteReplyEndVC;
+  }
+
+  outputs->Clear( );
+
+  outputs->AddRange( out_port , vcBegin, vcEnd );
+}
+
+void AnyNet::buildRoutingTable(){
+  cout<<"========================== Routing table  =====================\n";  
+  routing_table.resize(_size);
+  for(int i = 0; i<_size; i++){
+    route(i);
+  }
+  global_routing_table = &routing_table[0];
+}
+
+
+//11/7/2012
+//basically djistra's, tested on a large dragonfly anynet configuration
+void AnyNet::route(int r_start){
+  int* dist = new int[_size];
+  int* prev = new int[_size];
+  set<int> rlist;
+  for(int i = 0; i<_size; i++){
+    dist[i] =  numeric_limits<int>::max();
+    prev[i] = -1;
+    rlist.insert(i);
+  }
+  dist[r_start] = 0;
+  while(!rlist.empty()){
+    //find min 
+    int min_dist = numeric_limits<int>::max();
+    int min_cand = -1;
+    for(set<int>::iterator i = rlist.begin();
+	i!=rlist.end();
+	i++){
+      if(dist[*i]<min_dist){
+	min_dist = dist[*i];
+	min_cand = *i;
+      }
+    }
+    rlist.erase(min_cand);
+
+    //neighbor
+    for(map<int,pair<int,int> >::iterator i = router_list[1][min_cand].begin(); 
+	i!=router_list[1][min_cand].end(); 
+	i++){
+      int new_dist = dist[min_cand] + i->second.second;//distance is hops not cycles
+      if(new_dist < dist[i->first]){
+	dist[i->first] = new_dist;
+	prev[i->first] = min_cand;
+      }
+    }
+  }
+  
+  //post process from the prev list
+  for(int i = 0; i<_size; i++){
+    if(prev[i] ==-1){ //self
+      assert(i == r_start);
+      for(map<int, pair<int, int> >::iterator iter = router_list[0][i].begin();
+	  iter!=router_list[0][i].end();
+	  iter++){
+	routing_table[r_start][iter->first]=iter->second.first;
+	//cout<<"node "<<iter->first<<" port "<< iter->second.first<<endl;
+      }
+    } else {
+      int distance=0;
+      int neighbor=i;
+      while(prev[neighbor]!=r_start){
+	assert(router_list[1][neighbor].count(prev[neighbor])>0);
+	distance+=router_list[1][prev[neighbor]][neighbor].second;//REVERSE lat
+	neighbor= prev[neighbor];
+      }
+      distance+=router_list[1][prev[neighbor]][neighbor].second;//lat
+
+      assert( router_list[1][r_start].count(neighbor)!=0);
+      int port = router_list[1][r_start][neighbor].first;
+      for(map<int, pair<int,int> >::iterator iter = router_list[0][i].begin();
+	  iter!=router_list[0][i].end();
+	  iter++){
+	routing_table[r_start][iter->first]=port;
+	//cout<<"node "<<iter->first<<" port "<< port<<" dist "<<distance<<endl;
+      }
+    }
+  }
+}
+
+
+void AnyNet::readFile(){
+
+  ifstream network_list;
+  string line;
+  enum ParseState{HEAD_TYPE=0,
+		  HEAD_ID,
+		  BODY_TYPE, 
+		  BODY_ID,
+		  LINK_WEIGHT};
+  enum ParseType{NODE=0,
+		 ROUTER,
+		 UNKNOWN};
+
+  network_list.open(file_name.c_str());
+  if(!network_list.is_open()){
+    cout<<"Anynet:can't open network file "<<file_name<<endl;
+    exit(-1);
+  }
+  
+  //loop through the entire file
+  while(!network_list.eof()){
+    getline(network_list,line);
+    if(line==""){
+      continue;
+    }
+
+    ParseState state=HEAD_TYPE;
+    //position to parse out white sspace
+    int pos = 0;
+    int next_pos=-1;
+    string temp;
+    //the first node and its type
+    int head_id = -1;
+    ParseType head_type = UNKNOWN;
+    //stuff that head are linked to
+    ParseType body_type = UNKNOWN;
+    int body_id = -1;
+    int link_weight = 1;
+
+    do{
+
+      //skip empty spaces
+      next_pos = line.find(" ",pos);
+      temp = line.substr(pos,next_pos-pos);
+      pos = next_pos+1;
+      if(temp=="" || temp==" "){
+	continue;
+      }
+
+      switch(state){
+      case HEAD_TYPE:
+	if(temp=="router"){
+	  head_type = ROUTER;
+	} else if (temp == "node"){
+	  head_type = NODE;
+	} else {
+	  cout<<"Anynet:Unknow head of line type "<<temp<<"\n";
+	  assert(false);
+	}
+	state=HEAD_ID;
+	break;
+      case HEAD_ID:
+	//need better error check
+	head_id = atoi(temp.c_str());
+
+	//intialize router structures
+	if(router_list[NODE].count(head_id) == 0){
+	  router_list[NODE][head_id] = map<int, pair<int,int> >();
+	}
+	if(router_list[ROUTER].count(head_id) == 0){
+	  router_list[ROUTER][head_id] = map<int, pair<int,int> >();
+	}  
+
+	state=BODY_TYPE;
+	break;
+      case LINK_WEIGHT:
+	if(temp=="router"||
+	   temp == "node"){
+	  //ignore
+	} else {
+	  link_weight= atoi(temp.c_str());
+	  router_list[head_type][head_id][body_id].second=link_weight;
+	  break;
+	}
+	//intentionally letting it flow through
+      case BODY_TYPE:
+	if(temp=="router"){
+	  body_type = ROUTER;
+	} else if (temp == "node"){
+	  body_type = NODE;
+	} else {
+	  cout<<"Anynet:Unknow body type "<<temp<<"\n";
+	  assert(false);
+	}
+	state=BODY_ID;
+	break;
+      case BODY_ID:
+	body_id = atoi(temp.c_str());	
+	//intialize router structures if necessary
+	if(body_type==ROUTER){
+	  if(router_list[NODE].count(body_id) ==0){
+	    router_list[NODE][body_id] = map<int, pair<int,int> >();
+	  }
+	  if(router_list[ROUTER].count(body_id) == 0){
+	    router_list[ROUTER][body_id] = map<int, pair<int,int> >();
+	  }
+	}
+
+	if(head_type==NODE && body_type==NODE){ 
+
+	  cout<<"Anynet:Cannot connect node to node "<<temp<<"\n";
+	  assert(false);
+
+	} else if(head_type==NODE && body_type==ROUTER){
+
+	  if(node_list.count(head_id)!=0 &&
+	     node_list[head_id]!=body_id){
+	    cout<<"Anynet:Node "<<body_id<<" trying to connect to multiple router "
+		<<body_id<<" and "<<node_list[head_id]<<endl;
+	    assert(false);
+	  }
+	  node_list[head_id]=body_id;
+	  router_list[NODE][body_id][head_id]=pair<int, int>(-1,1);
+
+	} else if(head_type==ROUTER && body_type==NODE){
+	  //insert and check node
+	  if(node_list.count(body_id) != 0 &&
+	     node_list[body_id]!=head_id){
+	    cout<<"Anynet:Node "<<body_id<<" trying to connect to multiple router "
+		<<body_id<<" and "<<node_list[head_id]<<endl;
+	    assert(false);
+	  }
+	  node_list[body_id] = head_id;
+	  router_list[NODE][head_id][body_id]=pair<int, int>(-1,1);
+
+	} else if(head_type==ROUTER && body_type==ROUTER){
+	  router_list[ROUTER][head_id][body_id]=pair<int, int>(-1,1);
+	  if(router_list[ROUTER][body_id].count(head_id)==0){
+	    router_list[ROUTER][body_id][head_id]=pair<int, int>(-1,1);
+	  }
+	}
+	state=LINK_WEIGHT;
+	break ;
+      default:
+	cout<<"Anynet:Unknow parse state\n";
+	assert(false);
+	break;
+      }
+
+    } while(pos!=0);
+    if(state!=LINK_WEIGHT &&
+       state!=BODY_TYPE){
+      cout<<"Anynet:Incomplete parse of the line: "<<line<<endl;
+    }
+
+  }
+
+  //map verification, make sure the information contained in bother maps
+  //are the same
+  assert(router_list[0].size() == router_list[1].size());
+
+  //traffic generator assumes node list is sequenctial and starts at 0
+  vector<int> node_check;
+  for(map<int,int>::iterator i = node_list.begin();
+      i!=node_list.end();
+      i++){
+    node_check.push_back(i->first);
+  }
+  sort(node_check.begin(), node_check.end());
+  for(size_t i = 0; i<node_check.size(); i++){
+    if(node_check[i] != i){
+      cout<<"Anynet:booksim trafficmanager assumes sequential node numbering starting at 0\n";
+      assert(false);
+    }
+  }
+  
+}
+
-- 
cgit v1.3