BookSim 用户手册Brian Towles 和 William J. Dally2004 年 9 月 10 日目录引言 1入门 22.1 下载和构建模拟器 22.2 运行仿真 22.3 仿真输出 2示例 4配置参数 44.1 拓扑 44.2 路由算法 84.3 流控 94.4 路由器组织 94.4.1 输入排队路由器 94.4.2 事件驱动路由器 104.5 分配器 104.6 流量 104.7 仿真参数 11A. 随机数生成 121 引言本文档描述 BookSim 互连网络模拟器的使用。该模拟器设计为 Morgan Kaufmann 出版的教科书《互连网络原理与实践》PPINISBN: 0122007514的配套工具并假定读者熟悉该教材所涵盖的内容。本用户指南相当简短因为与大多数模拟器一样学习和理解模拟器的最佳方式是研究代码。模拟器的大多数组件都设计为模块化因此添加新的路由算法、拓扑或路由器微架构等任务不需要完全重新设计代码。下载代码、编译并运行一个简单示例第 2 节后第 3 节中更详细的示例将很好地概述模拟器的能力。第 4 节提供了配置选项列表以供参考。2 入门2.1 下载和构建模拟器最新版本的模拟器可从 http://cva.stanford.edu 【译注新地址https://github.com/booksim/booksim/tree/master】 以压缩 tar 归档文件形式获得。UNIX/Linux 用户可以使用 tar 工具解压该归档文件tarxvfx booksim-1.0.tar.gzWindows 用户可以使用 WinZip 等压缩程序解压归档文件。模拟器本身使用 C 编写并且特别使用 GNU 的 G 编译器版本 3进行了测试。此外还需要 LEX 和 YACC 工具也称为 FLEX 和 BISON来创建配置解析器。这些是任何 UNIX/Linux 开发环境中的标准工具。建议 Windows 用户下载这些 UNIX 开发工具的 CYGWIN 版本http://www.cygwin.com以简化编译过程。应编辑 Makefile使其前几行给出工具路径。例如在斯坦福大学编译器、YACC 和 LEX 存储在/usr/pubsw/bin目录中。Makefile 反映了这一点CPP /usr/pubsw/bin/g YACC /usr/pubsw/bin/byacc -d LEX /usr/pubsw/bin/flex然后可以通过在包含 Makefile 的目录中运行make来编译模拟器。2.2 运行仿真模拟器的语法很简单booksim[configfile]可选参数configfile是包含模拟器配置信息的文件。因此例如要在均匀流量下模拟一个简单的 8×8 环面8 元 2 立方体网络的性能可以使用如图 1 所示的配置。这个特定配置存储在examples/torus88中。除了指定拓扑之外配置文件还包含有关路由算法、流控和流量的基本信息。这个简单示例使用维序路由并且为了确保该路由函数在环面中的无死锁性需要两个虚拟通道。添加injection_rate参数以告诉模拟器每个节点每个仿真周期注入 0.15 个微片。由于模拟器在微片级别运行大多数参数都以微片为单位指定injection_rate也是如此。此外配置中以//开头的任何行都被视为注释模拟器会忽略。第 4 节给出了详细的配置参数列表。2.3 仿真输出继续我们的示例运行环面仿真会产生如图 2 所示的输出。每个仿真都有三个基本阶段预热、测量和排空。预热和测量阶段的长度是基本采样周期由配置中的sample_period定义的倍数。如图所示当前延迟和吞吐率已接受数据包的速率在每个采样周期后打印。总体吞吐率由网络中所有目的地的最低吞吐率决定但也会显示平均吞吐率。在预热阶段过去后模拟器打印 “Warmed up” 消息并重置所有仿真统计信息。然后测量阶段开始统计信息在每个采样周期后继续报告。一旦测量阶段过去所有测量数据包都会从网络中排空然后报告最终延迟和吞吐率数字。用于控制仿真阶段长度的配置参数细节见第 4.7 节。图 1用于模拟 8 元 2 立方体网络的示例配置文件。// 拓扑 topology torus; k 8; n 2; // 路由 routing_function dim_order; // 流控 num_vcs 2; // 流量 traffic uniform; injection_rate 0.15;图 2运行examples/torus88配置文件时的模拟器输出。% % Average latency 6.02008 % Accepted packets 0.11 at node 52 (avg 0.147094) % latency change 1 % throughput change 1 ... % Warmed up ... % % Average latency 6.0796 % Accepted packets 0.119 at node 5 (avg 0.148266) % latency change 0.00562457 % throughput change 0.00379387 ... % Draining all recorded packets ... % Draining remaining packets ... Traffic class 0 Overall average latency 6.09083 (1 samples) Overall average accepted rate 0.149475 (1 samples) Overall min accepted rate 0.138551 (1 samples)3 示例互连网络最基本的性能指标之一是其延迟与提供负载的关系。图 3 显示了一个简单配置文件用于在转置流量模式下测量 8 元 2 网格网络的这一指标。该配置用于生成 PPIN 中的图 25.2。该特定配置考虑了输入排队路由器的一些小延迟和流水线并引入了一个小的输入加速比以弥补分配中的任何低效。通过对注入率的许多增量运行仿真可以找到平均延迟曲线。然后例如为了比较维序路由与其他几种路由算法的性能可以更改routing_function选项。图 4 显示了一个配置文件可用于确定使用基于年龄的仲裁的 2 元 6 蝶形网络中数据包延迟的分布。注意priority配置参数与select分配器一起使用以考虑数据包优先级。模拟器默认不输出延迟分布但通过编辑trafficmanager.cpp、将配置变量DISPLAY_LAT_DIST设置为true并重新编译分布将在仿真结束时显示。该技术用于生成 PPIN 图 25.12 中所示的分布。作为最后一个示例图 5 显示了使用特殊单节点拓扑来测试交换机分配器性能——在本例中为 iSLIP 分配器。in_ports和out_ports选项设置了一个 8×8 交叉开关的仿真。图 3一个典型配置文件examples/mesh88_lat用于为 8 元 2 网格网络创建延迟与提供负载曲线。// 拓扑 topology mesh; k 8; n 2; // 路由 routing_function dim_order; // 流控 num_vcs 8; vc_buf_size 8; wait_for_tail_credit 1; // 路由器架构 vc_allocator islip; sw_allocator islip; alloc_iters 1; credit_delay 2; routing_delay 1; vc_alloc_delay 1; input_speedup 2; output_speedup 1; internal_speedup 1.0; // 流量 traffic transpose; const_flits_per_packet 20; // 仿真 sim_type latency; injection_rate 0.1;图 4一个配置文件examples/fly26_age用于使用基于年龄的仲裁寻找数据包延迟分布。// 拓扑 topology fly; k 2; n 6; // 路由 routing_function dest_tag; // 流控 num_vcs 8; vc_buf_size 8; wait_for_tail_credit 1; // 路由器架构 vc_allocator select; sw_allocator select; alloc_iters 1; credit_delay 2; routing_delay 1; vc_alloc_delay 1; input_speedup 2; output_speedup 1; internal_speedup 1.0; // 流量 traffic uniform; const_flits_per_packet 20; priority age; // 仿真 sim_type latency; injection_rate 0.1;图 5一个单节点配置文件examples/single用于测试交换机分配器的性能。// 拓扑 topology single; in_ports 8; out_ports 8; // 路由 routing_function single; // 流控 vc_allocator islip; sw_allocator islip; alloc_iters 2; num_vcs 8; vc_buf_size 1000; wait_for_tail_credit 0; // 仿真 sim_type latency; injection_rate 0.1;4 配置参数用于配置仿真的所有信息都通过配置文件传递如第 2.2 节示例所示。本节列出已有的配置参数——用户可以通过修改booksim_config.cpp文件来加入额外选项。4.1 拓扑topology参数决定网络的底层拓扑模拟器支持四种基本拓扑flyk 元 n 蝶形butterfly拓扑。k参数决定网络的基数n参数决定网络的维数。meshk 元 n 网格mesh拓扑。k参数决定网络的基数n参数决定网络的维数。single具有单个节点的网络用于测试单路由器性能。节点的输入和输出端口数分别由in_ports和out_ports参数决定。torusk 元 n 立方体torus拓扑。k参数决定网络的基数n参数决定网络的维数。mesh和torus拓扑都支持通过link_failures参数添加随机链路故障。link_failures的值决定从拓扑中随机移除的通道数因此这些通道不再可用于转发数据包。此外故障通道的随机化通过为fail_seed参数选择一个整数值来控制——固定种子会给出固定的故障通道集合独立于仿真中的其他随机化。另请注意只有某些路由函数支持此功能见第 4.2 节。4.2 路由算法routing_function参数为拓扑选择一种路由算法。许多路由算法需要多个虚拟通道来实现无死锁VcDF。路由函数描述dim_order维序路由。适用于 mesh 拓扑1 VcDF和 torus 拓扑2 VcDF。dim_order_bal用于 torus 拓扑的维序路由使用更平衡的 VC 使用以避免死锁2 VcDF。dim_order_ni维序路由的非干扰版本。适用于 torus 或 mesh 拓扑每个网络终端需要一个 VC。min_adapt用于 mesh 拓扑2 VcDF和 torus 拓扑3 VcDF的最小自适应路由算法。planar_adapt用于 mesh 拓扑的平面自适应路由2 VcDF。支持绕过故障通道进行路由。romm用于 mesh 的 ROMM 路由2 VcDF。负载通过两阶段路由来平衡第一阶段从源到最小象限中的随机中间节点第二阶段从中间节点到目的地。romm_ni用于 mesh 的 ROMM 路由的非干扰版本每个网络终端需要一个 VC。single用于 single 拓扑的哑路由函数。valiant用于 mesh 拓扑2 VcDF和 torus 拓扑4 VcDF的 Valiant 随机路由算法。valiant_ni用于 torus 的 Valiant 算法非干扰版本每个网络终端需要 4 个 VC。此外模拟器代码的结构使得可以以最小的整体模拟器改动来添加额外的路由算法参见模拟器源代码中的routefunc.cpp文件。4.3 流控模拟器支持带有基于信用的背压的基本虚拟通道流控。num_vcs每个物理通道的虚拟通道数。vc_buf_size每个虚拟通道的深度以微片为单位。voq如果非零则使用虚拟输出排队。使用虚拟输出排队时为网络中的每个目的地分配一个单独的虚拟通道。此选项与无干扰路由算法第 4.2 节一起使用时最有用。wait_for_tail_credit如果非零则在尾部微片离开该虚拟通道之前不重新分配虚拟通道。这种保守方法可防止连续共享同一虚拟通道的两个数据包之间形成依赖关系。4.4 路由器组织模拟器还支持两种不同的路由器微架构。输入排队路由器遵循 PPIN 中描述的一般组织而事件驱动路由器则仿照 Avici TSR 中使用的路由器并在美国专利 6,370,145 中描述。微架构通过router选项选择。此外两种路由器共享一小组选项。credit_delay信用的处理延迟以周期为单位。不包括传输信用的线路延迟。internal_speedup路由器内部相对于通道传输速率的任意加速比。例如加速比 1.5 意味着平均而言在单个微片通过通道传输所需的时间内路由器可以转发 1.5 个微片。此外配置解析器期望此字段为浮点数因此整数加速比也应包含小数点例如2.0。output_delay路由器输出队列中产生的处理延迟。4.4.1 输入排队路由器输入排队路由器router iq遵循 PPIN 中描述的路由计算、虚拟通道分配、交换机分配和交换机遍历流水线。有几个选项特定于输入排队路由器。input_speedup输入端口在空间上的整数加速比。例如加速比为 2 时每个输入有两个进入交叉开关的输入端口。对这些端口的访问基于虚拟通道号静态分配对于输入加速比s输入i上的虚拟通道v连接到端口i·s (v mod s)。output_speedup输出端口在空间上的整数加速比。类似于input_speedup。routing_delay路由计算的延迟以周期为单位。4.4.2 事件驱动路由器事件驱动路由器router event是一种微架构专门设计用于高效支持大量虚拟通道VC。与输入排队路由器中持续轮询虚拟通道状态不同它只跟踪 VC 状态的变化。因此其效率来自每个周期的状态变化数量是恒定的并且与 VC 数量无关。4.5 分配器模拟器中使用的许多分配器都是可配置的参见第 4.4.1 节中的输入排队路由器并且有几种分配算法可用。max_size最大规模匹配。islipiSLIP 可分离分配器。pim并行迭代匹配可分离分配器。loa孤独输出分配器。wavefront波前匹配。select基于优先级的分配器。分配方式与 iSLIP 中相同但偏好较高优先级的数据包参见第 4.6 节中的priority选项。还可以通过执行算法的多次迭代来改进分配迭代次数由alloc_iters参数控制。4.6 流量微片注入模拟器的速率使用injection_rate选项设置。模拟器的周期时间是微片周期即单个微片在源端注入所需的时间注入率以微片/微片周期为单位指定。例如设置injection_rate 0.25意味着每个源每四个模拟器周期注入一个新微片。注入过程也可以指定为伯努利过程injection_process bernoulli或开-关过程injection_process on_off。后一种注入过程的突发性由burst_alpha和burst_beta参数控制。有关开-关过程及其参数的描述请参见 PPIN 第 24.2.2 节。注入单位是数据包数据包可能由许多微片组成。每个数据包的微片数使用const_flits_per_packet选项设置。每个数据包还可以具有关联的优先级由priority选项指定可以是基于年龄的age或无none。模拟器还支持几种不同的流量模式使用traffic选项指定。为了描述这些模式我们使用 PPIN 第 3.2 节中的相同符号(s_i)(d_i)表示源目的地地址的第 (i) 位而 (s_x)(d_x)表示源目的地地址的第 (x) 个基数为 (k) 的数字。地址的位长度为 (b \log_2 N)其中 (N) 是网络中的节点数。uniform每个源向每个目的地发送等量流量traffic uniform。bitcomp位补。(d_i \neg s_i)bitrev位反转。(d_i s_{b - i - 1})shuffle混洗。(d_i s_{i - 1} \bmod b)transpose转置。(d_i s_{i b/2} \bmod b)tornado龙卷风。(d_x s_x \lfloor k/2 \rfloor - 1 \bmod k)neighbor邻居。(d_x s_x 1 \bmod k)random随机排列。从所有排列的集合中均匀随机地选择一个固定排列流量模式。用于生成此排列的种子由perm_seed选项设置。因此随机选择perm_seed值可以得到排列的随机采样而固定的perm_seed值允许在多个实验中使用相同的排列。4.7 仿真参数仿真的持续时间和其他方面通过一组仿真参数控制。sim_type仿真可以侧重于吞吐率或延迟。这两种类型的关键区别在于延迟仿真会等待所有测量数据包排空后才结束仿真以确保准确的延迟测量。在吞吐率仿真中消除了最后的排空步骤以允许模拟运行超过饱和点的网络。sample_period采样周期以模拟器周期表示并在指定仿真的预热长度和最大样本数时用作乘数。此外中间统计信息每sample_period个周期显示一次。warmup_periods预热长度表示为采样周期的倍数。预热后所有统计计数器都会重置。max_samples仿真总长度表示为采样周期的倍数。latency_thres如果当前仿真的采样延迟超过latency_thres仿真立即结束。sim_count针对给定配置连续运行的仿真次数。用于创建特定统计量的集成平均值。seed仿真的随机种子。reorder非零值表示应保持数据包顺序并且重排序时间计入总体延迟。A 随机数生成模拟器使用 Knuth 的整数和浮点伪随机数生成器。这些算法及其解释出现在《计算机程序设计艺术半数值算法》中。