面向片上网络模拟器booksim的分析
摘要：Booksim是一个采用C++实现的面向片上互连网络的开源模拟器。本文的主要目的是分析该模拟器的原理和实现方法，作为设计面向可重构NoC的模拟器的技术探索。该模拟器大多数组件设计为模块，因此，当需要增加新型路由器算法、拓扑或者路由器微结构时，只需要增加新模块，不需要重新设计。
1. 背景
片上网络的重要性。片上网络模拟器的现状。
2009国际半导体路线图
评估片上网络的性能的手段主要有分析、模拟和试验。设计网络模拟器有两种方法：基于周期(cycle-bad)的方法和事件驱动(event-dirven)的方法。
Dally在[1]中将模拟层次分成4个级别：接口级、容量级、微片级和硬件级。接口级的模拟建模网络接口，提供包传递，并且仅仅根据距离生成包近似延时信息；容量级的模拟增加了
资源容量约束，比如沟道带宽或者飞行中包的最大数量等等；微片级的模拟，包延时以微片时间或者路由器周期的形式被精确建模；硬件级的模拟增加了硬件的实现细节，比如面积和时序信息，延时能够以绝对时间表示，因此更加精确。
动态可重构技术引入NoC中的必要性和好处。选择booksim烤麸是什么做的作为面向可重构片上网络模拟器原型的原因。文献[4]采用SystemC建立了三种通信结构的模型：总线、异步NoC和同步NoC。SystemC是一种基于C++库的硬件描述语言。
本文的主要贡献是解析booksim的使用方法，以及如何改变流水线和增加新的路由算法等等。我们采用一种新的流水线，提高了片上网络的性能。
2. Booksim介绍
该模拟器在flit级建模网络，支持多种拓扑和路由算法，可以配置路由器的缓存、加速比和流水线时序。该模拟器采用周期精确(two-pha cycle-bad)的两阶段模拟方法。所谓两阶段，是指读全局状态阶段和写全局状态阶段。在模拟周期的开始阶段，包到达结点，读取全局状态。任何读取全局状态的函数，比如ReadInputs函数，必须向模拟器注册，并且在第一个阶段中被调用。
我们可以通过斯坦福的网站[3]下载最新的模拟器代码。将源代码解压缩，为Makefile文件中的CPP、YACC和LEX的指定路径，在终端中输入make即可完成安装。在配置文件中设置拓扑、路由算法、流控、路由器结构、通信模式、报文格式以及模拟类型等等。在终端中输入booksim [configfile]海洋生物资源即可运行[2]。
拓扑：参数topology代表拓扑类型，模拟器支持四种基本拓扑，分别是fly、mesh、single和torus。参数k表示网络的基数，而参数n代表网络的维数。
路由算法：参数routing_function代表路由算法。为了避免死锁，许多路由算法需要多个虚拟沟道(VCDF, virtual channels for deadlock freedom)。该模拟器总共实现了5种路由算法：维序路由、自适应路由、ROMM路由算法、哑元路由和Valiant路由。
流控：模拟器支持基本虚通道流控，采用credit-bad 反馈策略。配置流控时需要设置4个参数：num_vcs、企业授权委托书模板vc_buf_size、voq和wait_for_tail_credit。其中，前两个参数分别表示每个物理沟道中虚通道的数目和每个虚通道的深度。参数voq (virtual-output queuing)非零表示给网络的每个目的指派一个单独的虚拟沟道。该选项对于无干扰(non-interfering)路由算法是有用的。如果参数wait_for_tail_credit的数值不是0，那么不会重新分配虚拟沟道，直
到尾flit已经离开虚拟沟道。该保守方法可以阻止共享相同虚拟沟道的两个报文形成依赖。
路由器：参数router表示路由器的类型，模拟器支持两种不同的路由器微结构：输入排队的路由器(router=iq)与事件驱动的路由器(router=event)。参数credit_delay表示处理一个信用的延时周期，不包括传输信用的线延时。Internal_speedup表示在通过一个沟道传输单个微片的时间内，路由器可以转发的微片数。如果加速比是2，意味着平均在单个微片通过一个沟道传播的时间里，路由器可以转发2个微片。Output_delay表示路由器的输出排队导致的延时。输入排队路由器的参数包括输入加速（整数，表示每个输入端口进入Crossbar的端口数量）、输出加速（整数，表示Crossbar到每个输出端口的端口数量）、路由计算延时、交叉开关分配延时、交叉开关延时、虚通道分配延时、虚通道延时等等。
分配器：支持多种分配算法，比如max_size、islip、pim、loa、wavefront、lect。
通信模式：injection_rate 。injection_process有两个选择：bernoulli和on-off。对于on-off的突发特性由两个参数设置：burst_alpha和burst_beta。
模拟参数：模拟类型，采样周期、升温周期、最大采样、延时阈值、模拟周期、随机种子
和记录统计数据。模拟器采用knuth的整数和浮点伪随机数生成器，具体算法和描述可以查阅文献[4]。
模拟类型分为两种：吞吐量和延时。二者的主要不同在于，延时模拟类型等待所有包排空才结束模拟以获得精确延时信息。采样周期用模拟器周期来表示。每个采样周期更新一次统计数据。升温周期和最大采样表示为采样周期的倍数。升温之后，清空统计计数器。如果当前模拟的采样延时超过延时阈值，模拟立即终止。如果重排序时间非零，那么必须维持包的顺序。重排序时间计入总延时。
3. 模拟器源码
代码中大量使用引用操作符&和指针操作符*，以及const操作符。引用型变量是其他实际变量的逻辑别名，通常用于传递参数和返回值，在声明时必须用一个实际对象进行初始化，初始化之后不可改变。在C++中，私有数据成员只能被该类中的成员函数访问；公有成员既可以被该类中的成员访问，还可以被任何其他类的成员访问；受保护的数据成员可以被该类和该类的子类中的函数访问。
3.1类层次结构
模拟器源代码中大量使用C++ 标准模版库中的容器和迭代器等数据结构。
Map类型是健-值对的集合，通常称之为关联数组，可以使用键作为下标来获取数值，而不是通过元素在数组中的位置类获取数据；链表(List)和向量(Vector)类型是基本序列容器，完全按照存入的顺序保存数据。Vector类模板将其存储内容作为一个连续的数组来维护，因此，具有数组风格的索引方式。这意味着，除了在最后一个元素后插入新元素的操作，其他插入操作均不可接受。当预分配的存储空间用完后，必须重新分配更大的存储空间，并且把原来的对象拷贝到新的存储空间中。List类模板采用双向链表数据结构来实现，因此，可以快速在序列的任何地方插入或者删除元素。对list随机访问的速度非常慢。Queue数据结构实现了先进先出操作。输入buffer就是采用Queue数据结构。
分析一下该模拟器哪些变量适合用这些数据结构
Booksim中的类的层次结构，如图1所示。Module类是是很多类的基类。
图1. 类层次结构
获取配置文件：booksim模拟器设立configuration类处理配置参数。该类拥有两个私有数据成员：一个静态数据成员指向configuration类实例的指针theConfig，另一个用于指向配置文件的实例指针_config_file。此外还包括三个受保护的数组数据成员：_str_map、_int_map和_float_map，分别用于存储字符串、整形和浮点类型的配置数据。BookSimConfig类是configuration类的子类。值得关注的是，BookSimConfig类的构造函数大量初始化配置参数。
建模源队列[1，p489]：迟缓的注入过程(a lagging injection process)。基于age的优先权(age-bad priorities)。
3.2网络拓扑
Network类是拓扑的基类。如图1所示，网络类有三个子类，分别是KNCube、KNFly和SingleNet，分别代表Mesh/torus、蝶形和单结点网络。下面以KNCube类为例，分析如何构造和使用拓扑类。该类有怎么刷机3个私有数据成员：整型变量_k和_n分别表示网络的基数和维数，布尔型变量_mesh表示究竟网络拓扑是mesh还是torus。
函数ComputeSize()的作用是从配置文件中读取网络的k和n的数值，并且计算网络中的结点数(size)和沟道数量(channels)，计算公式如下：
size = kn, channels = 2*n*size
函数LeftChannel()和函数RightChannel()分别返回结点编号node在维度dim上左、右输出沟道编号。每个节点与2*n个输出沟道相连，编号node的结点的左输出沟道编号是2*n*node+2*dim+1，右输出沟道编号是2*n*node+2*dim，由此可见，输出沟道的编号顺序是从右至左。函数碧海蓝线LeftNode()和函数RightNode()分别返回结点node在维度dim上左、右节点的编号。通过如下公式计算结点node的编号：
node = an-1kn-1+an-2kn-2+…+a1k+a0如何刻录光盘
其中，ai是小于k的整数，表示结点node在维度i上的编号。结点node还可以用n维向量表示： node = (an-1,an-2,…,a1,a0)陶广生
如果结点node是维度dim上编号最小的结点，那么node的左结点编号是node+(k-1)*kdim; 否则node的左结点编号是node-kdim。Node的右结点的计算方法类似。
函数BuildNet的功能是初始化网络，包括路由器、左沟道、右沟道和本地沟道。
3.3路由器模型
在分析路由器之前，首先简单分析一下Flit结构体、Credit类、VC类、BufferState类、Allocator类和PipelineFIFO模板类。
Flit结构体包含18个数据域，它们分别记录微片需要的虚通道数量、是否头微片、是否尾微片、是否真尾、生成时间、序号、重定序时间、ID、是否记录、源结点编号、目的结点编号、优先权、跳步数量、是否监察、为多阶段算法和避免死锁而准备的变量。
Credit类包含4个公有数据成员，其中vc是指向整数的指针，用以记录每个虚拟通道可用缓存的数量；整型变量vc_cnt记录虚拟通道数量；布尔变量意识英语head和tail分别记录该信用是否头和尾；整型变量id记录信用的编号。
在分析VC类前，首先分析OutputSet类(输出集合类)。它定义了一个结构体sSetElement(集合元素)，并且拥有两个私有数据成员，其中整型变量_num_outputs记录输出端口的数量，list<sSetElement> *_outputs则用于记录真实数据。VC类内部定义了一种枚举数据类
型eVCState，用以表示虚通道的状态。虚通道共四种状态：空闲(idle), 路由(routing), 分配(vc_alloc)和活动(active)。该类拥有12私有数据成员，其中，_size记录VC中buffer的深度；_buffer记录存放在该VC中的微片；_state表示该VC的状态；_state_time记录VC处于当前状态的时间；OutputSet *_route_t;
