6.823计算机系统及结构 V1IW,向量数据处理和 顺序一致性 习题集#5 春季2002 我强烈建议，学生每三人分成一个小组合作完成作亚。每组只需要交一份该寸圈集的各案。 学生夜该在决定时间的课前费交作业。为了便于评分，各种习应该分类，而月每个学生最终 所在组编号必须填写在每道习题后面〔如果你更换了小组，请说明，我们会为你指定一个新的 组编号)。·旦参考容案己经发放，我们将不冉按收州：业。为了完成下面的习题，可能端安做· 些程设。请在你的答案中明确典说明这些行设。 习题1：断定 Ben Bitdiddle写了如下的C循环，对向量中的每个元素玖绝对作。 for《i-0:i. 对于这个化环来说，如果假设数据元素是正数和负量的餐率一样，每处理一个元素平均需要多 少制周期：很设我的机器使用简单的、带见务两的核序5受DLX水线(L6-36),使用的 存储器由MAGIC RAM构成. 习想1.B 重写汇编代码，晨开你来的循环，项在在向回跳转之前要执行两次祈环巾的送代。当N很天 的时候，处理母个元素平均需要多少时钟周期？籍环展开是否减少了每次选代所耗费的时钟司 期？析虫的循不展开是什么？ 习恩1.C Alyssa P.Hacker洗她能通过使用断定米则除汇编代码中的数花相关转移(data-dependemt branches)妹提出了一个新的DLX断定指令集，如下所示： 1)扩晨1SA.使用32个断定位P0一P31。 2)每个标准非控钊指令逐如一个断定刷本，活法如下：
6．823 计算机系统及结构 VLIW，向量数据处理和 顺序一致性 习题集 #5 春季 2002 我们强烈建议，学生每三人分成一个小组合作完成作业。每组只需要交一份该习题集的答案。 学生应该在决定时间的课前提交作业。为了便于评分，各种习题应该分类，而且每个学生最终 所在组编号必须填写在每道习题后面（如果你更换了小组，请说明，我们会为你指定一个新的 组编号）。一旦参考答案已经发放，我们将不再接收作业。为了完成下面的习题，可能需要做一 些假设，请在你的答案中明确地说明这些假设。 习题 1：断定 Ben Bitdiddle 写了如下的 C 循环，对向量中的每个元素取绝对值。 习题 1.A 将 Ben 的 C 循环语句改写成 DLX 指令，假设在 A 和 N 中的元素是 32 位有符号整型数。最初， R1 存储 N 并且 R2 指向 A[0]。你不需要保存这些寄存器的值。假设 DLX 有标准的单个延迟槽。 说明你的代码，并优化提高其性能，但是不要展开循环（loop unrolling）,不要使用软件流水线 （software pipelining）。 对于这个循环来说，如果假设数据元素是正数和负数的概率一样，每处理一个元素平均需要多 少时钟周期？假设我们的机器使用简单的、带泉旁通的按序 5 段 DLX 流水线（L6-36），使用的 存储器由 MAGIC RAM 构成。 习题 1.B 重写汇编代码，展开你原来的循环，现在在向回跳转之前要执行两次循环中的迭代。当 N 很大 的时候，处理每个元素平均需要多少时钟周期？循环展开是否减少了每次迭代所耗费的时钟周 期？折衷的循环展开是什么？ 习题 1.C Alyssa P.Hacker 说她能通过使用断定来删除汇编代码中的数据相关转移（data-dependent branches）。她提出了一个新的 DLX 断定指令集，如下所示： 1） 扩展 ISA，使用 32 个断定位 P0—P31。 2） 每个标准非控制指令添加一个断定副本，语法如下：
(pbit)DLX INSTRUCTION execute the DIX instruction if pbit is true 3)引入一个比较指令集，用来有条件的设置断定位： CMPLTZ pbit,reg set poit it reg o CMPCE&pbit,reg ；8etp01t1treg>-0 CMPEQ2 pbit,reg 1 set pbit if reg =0 CMPNEZ pbit,reg set poit ir reg !0 使用新的DLX断定指令改写Bm的循环。请为你的代码添如注解，使它尽可使的可读。优化 你的代码，但龙不斐使川软件流水线，不安提开花环 对新的面环，处理每个元素需发多少时钟尚期？假设转移设置比较蓄装一个时钟城期（也或是 和正常ALU指令养不多) 习题1D 见在考感一个有断定VLW战本的DLX机，它一个时钟网期可以做两个快作。整烨上面的面 定循环休，以共得最大的执行效率，不准展开循环或使用饮件流水线。现在每个元紫平均需因 E费多少时钟明？程设VLJW五水线和署通D儿X的一样有标准的5段流术结构，但是VL 有两个ALU,存偏器有两个★口、两个写端口，并且奇存器组有4个读端口和两个写端口。 虽然有两个操作，但廷迟槽仍然只是一个， 习恩1E 肢开V.W猫坏体，使其能本间问防转之前完成两次你：宗猫环里的达代，整理代码以获得蚊闺 性能。对于N比较大的情况，处理一个元素平均雷要多少时钟周期？ 习恩1F 加果B知道N有多大，这样他就能有较件蔬水我彻底延开葡环，现在处理一个元素，最少平 均需买多少时钟网期？解释你的答案。（提示：回答月圆时，你不必写出完整的代码.）
3)引入一个比较指令集，用来有条件的设置断定位： 使用新的 DLX 断定指令改写 Ben 的循环。请为你的代码添加注解，使它尽可能的可读。优化 你的代码，但是不要使用软件流水线，不要展开循环。 对新的循环，处理每个元素需要多少时钟周期？假设转移设置比较需要一个时钟周期（也就是 和正常 ALU 指令差不多） 习题 1.D 现在考虑一个有断定 VLIW 版本的 DLX 机，它一个时钟周期可以做两个操作。整理上面的断 定循环体，以获得最大的执行效率，不准展开循环或使用软件流水线。现在每个元素平均需要 耗费多少时钟周期？假设 VLIW 流水线和普通 DLX 的一样有标准的 5 段流水结构，但是 VLIW 有两个 ALU，存储器有两个读端口、两个写端口，并且寄存器组有 4 个读端口和两个写端口。 虽然有两个操作，但延迟槽仍然只是一个。 习题 1.E 展开 VLIW 循环体，使其能在向回跳转之前完成两次原来循环里的迭代，整理代码以获得最佳 性能。对于 N 比较大的情况，处理一个元素平均需要多少时钟周期？ 习题 1.F 如果 Ben 知道 N 有多大，这样他就能有软件流水线彻底展开循环，现在处理一个元素，最少平 均需要多少时钟周期？解释你的答案。（提示：回答问题时，你不必写出完整的代码。）
习题2：VLIW编程 .叫使T理器 h ,他们正在设计一种新的处理 法器 有冠精。其转定准确率为100 中的 金个功能华元有二个专用的回端 所以本 Ben己经将点积从DLX变换到TitaniumISA 8 e8￥ cemp F3.0R15 F4,0(R2 ADDI R5,R5,#-1 :A8；4E3R5,1o
习题 2：VLIW 编程 Ben Bitdiddle 和 Louis Reasoner 开了一家新公司，叫做 Transbeta®，他们正在设计一种新的处理 器 Titanium™。Titanium 是一个单发射按序完成的 VLIW 处理器，有： z 两个读写单元。没有 Cache。一个读单元会造成 4 个周期的延迟，但是它是完全流水结构 的。 z 1 个整型 ALU。一个周期 z 1 个浮点乘法器。3 个周期，流水结构 z 1 个浮点加法器。2 个周期，流水结构 z 1 个跳转单元，没有延迟槽，其转移断定准确率为 100% z 128GPRs,128FPRs 一条 Titanium 指令可同时发射到上述所有单元。我们定义，Titanium 指令中的操作是相互独立 的。其中的每个操作读取一个操作数就同时发射。这样如果一个操作等待先前的 Titanium 指令， 整个 Titanium 指令就会停留在解码阶段。 所有部件是全旁通的，每个功能单元有一个专用的回写端口，所以根本不会发生冲突。在同一 指令中向同一寄存器多次进行写操作在 Titanium ISA 中是不允许的。WAW 故障也会造成指令 执行停止。Titanium ISA 类似于 DLX，只是每行最多可以 6 条指令，用分号分开。 现在你被雇来完成一些数学库程序的手动优化工作。其中最重要的就是点积运算，由 ∑Xn ×Yn 来给定。 Ben 已经将点积从 DLX 变换到 TitaniumISA 每次迭代需要 9 个时钟周期，但在程序中每处理一个向量元素平均需要 8 个时钟周期。Alyssa P.Hacker 说在长向量中，每处理一个元素只需要一个时钟周期。给 Ben 和 Louis 看看，什么样 的代码可以达到这种效果。Louis 不是很聪明，所请为你的代码写清楚注释
习题3：向量化的strepy 9.9 */ 新用下香约方式大了：买种青存香起和心分别存线以和餐凉有起 put ength in vecto length registes ；subtract elements any ors to 习题3M 指令和 有重的地方 习愿3.B 个eot四teingigaing o and seturn5 repy角memepyf的不同之处就是scy在拷贝过程中碰到字符0'就终止，而memepy按给定的长
习题 3：向量化的 strcpy Ben Bitdiddle 买了一个 state-of-the-art 向量机，Zirconium™，它有一个向量寄存器，最多可以存 储 32 个元素，他决定将原来的 C 库函数向量化。最为开始，他将 C 函数 memcpy 向量化了。 关于 memcpy 的说明如下： Ben 用下面的方式实现了 memcpy，其中寄存器 R1,R2 和 R3 分别存储 s,ct 和 n。假设没有延迟 槽。 习题 3.A Zironium处理器有一个读写单元，该单元只有一个完全流水结构的通路（lane），会有10个周期 的延迟和10个周期的停滞（dead-time）。指令不要多余的时钟周期来回写值。所有的标量指令 执行在带完全旁路的一个5级流水线上。因此，标量指令和向量指令的执行可能会有重叠的地方。 在稳定状态下，如果拷贝了一个很长的向量，那么每拷贝一个元素需要多少周期？ 习题 3.B Ben的下一个目标就是strcpy： strcpy和memcpy的不同之处就是strcpy在拷贝过程中碰到字符’\0’就终止，而memcpy按给定的长
度进行见。 面不醒商被贸代克量华行并代不向商 帮助Ben为Zire 处理器写向量化代码。假设存器R1和2分别行 习愿3.C 在使月
度进行拷贝。 Ben尝试了很多方法，想将这段代码向量化，但是都放弃了，并认为这段代码不可向量化。然而， Alyssa告诉Ben这个函数可以被向量化，不过需要用到一些附加的向量指令，如下所示： CLZM R1, VM 计算向量屏蔽（vector-mask）寄存器VM中开头0的个数并将结果放入R1。 例如，如果VM中数据是0001010…000，那么CLZM R1, VM就将3存入R1。 S—V V1，V2 比较（EQ,NE,GT,LT,GE,LE）在V1和V2种的元素。如果条件为 S——V F0，V1 真，在相关的位向量里写1；否则写0。然后将向量位放入向量屏蔽 （vector-mask）寄存器VM。S——SV指令执行相同的比较，只不过使用标 量值作为一个操作数。 使用上述附加指令，帮助Ben为Zirconium处理器写向量化代码。假设寄存器R1和R2分别存储s 和ct。Zirconium处理器不支持虚拟存储器，并且对向量内存装入时的内存保护冲突它也不能处 理。同样假设字符串是按字拷贝的。结束字符必须从一个字的边界开始，在结束字符后剩下的3 个字节必须是0x0。（提示：ASCII码中’\0’的值是0） 习题 3.C 对于向量化后的 memcpy 和 strcpy，在使用向量链（vector chaining）和不使用向量链两种情况 下比较其性能。对于每种情况，在稳定的状态下，传输一个元素需要多少时钟周期？假设只有 一个向量比较单元且该单元只有一条通路（lane）；比较两个值是否相等需要一个时钟周期
习题4：向量机的性能 向量处理卷Germanium有一个向量如法单元和一个向量乘法单元，其属性如下： 1)向量寄存器有32个元素，向量寄存器组对于每个加法和乘法单元支持2个读端口和1 个写端。 2)向量加法单元是完全的流水结构。会产生2个时钟周期的延退。 )向量乘法单元是光全的流水结构。会产生3个封钟周期的延迟。 4)向量机的流水结构如下： F D R XX...X W (F:取指令，D:解码，R:向量寄存墨读，W:写日) 现在你有如下代码： I1:ADDV V3,V2,V1 I2:ADDV V4,V2,V1 I3:MULTV V5,V4,V3 注：所有向量长度都是32个元素。 习题4，A 画出运行上述代码的Ge「m台n1um处理器流水图，假设流水线有8条通路，两个时钟 周期的停滞期。没有向量链接。执行上述代码需要多少时钟周期？计算从第一次写结果到最 后一次写结果（包括）的执行时间，以时钟周期为单位。 例如，ADDV V3,V2,V1的流水图如下，其中向量长24个元素。因为我们需 要用8条通路做24个操作，所以应该读取向量寄存器组3次。X1是加法单元的第一段， X2是第二段。在周期6，前8个操作的结果回写，这条指令需要三个时钟周期米执行， Time Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycles F D R XI 2 W XI X2 W XI 2X2 习愿4B 画出运行上述代码的Gc「m。n!um处理器流水图，假设流水线有8条通路。没有停海 期，没有向量统接。向量歧通过路存器组完成。一个向量单元可以在目写的同一时钟周期内 从寄存器组读一个元素，执行上述代码需要多少时钟周期？ 习题4.C 画出运行上述代码的Ge「m自n1um处理答流水阁，假设流水线有】6条通路，设有停 滞期，没有向量链接。执行上述代码需要多少时钟周期？
习题 4：向量机的性能 向量处理器 Germanium™有一个向量加法单元和一个向量乘法单元，其属性如下： 1) 向量寄存器有 32 个元素。向量寄存器组对于每个加法和乘法单元支持 2 个读端口和 1 个写端。 2) 向量加法单元是完全的流水结构，会产生 2 个时钟周期的延迟。 3) 向量乘法单元是完全的流水结构，会产生 3 个时钟周期的延迟。 4) 向量机的流水结构如下： Ｆ Ｄ Ｒ Ｘ Ｘ．．．Ｘ Ｗ （Ｆ：取指令，Ｄ：解码，Ｒ：向量寄存器读，Ｗ：写回） 现在你有如下代码： 注：所有向量长度都是３２个元素。 习题４．Ａ 画出运行上述代码的Ｇｅｒｍａｎｉｕｍ处理器流水图，假设流水线有８条通路，两个时钟 周期的停滞期，没有向量链接。执行上述代码需要多少时钟周期？计算从第一次写结果到最 后一次写结果（包括）的执行时间，以时钟周期为单位。 例如，ＡＤＤＶ Ｖ３，Ｖ２，Ｖ１的流水图如下，其中向量长２４个元素。因为我们需 要用８条通路做２４个操作，所以应该读取向量寄存器组３次。Ｘ１是加法单元的第一段， Ｘ２是第二段。在周期６，前８个操作的结果回写。这条指令需要三个时钟周期来执行。 习题４.B 画出运行上述代码的Ｇｅｒｍａｎｉｕｍ处理器流水图，假设流水线有８条通路，没有停滞 期，没有向量链接。向量链通过寄存器组完成。一个向量单元可以在回写的同一时钟周期内 从寄存器组读一个元素。执行上述代码需要多少时钟周期？ 习题４.C 画出运行上述代码的Ｇｅｒｍａｎｉｕｍ处理器流水图，假设流水线有１６条通路，没有停 滞期，没有向量链接。执行上述代码需要多少时钟周期？
习题5：同步和连续一致性 CyD.Ft希望能在处理器P1和P2上运行下列代码。开始的时候，M[A].M[B], M[C]和M[D]都是0. P1 P2 ADDI R1,RO,#1 ADDI R1,RO,#1 SW A(R0),R1 SW B(R0),R1 LW R2,B(R0) LW R2,A(R0) SW C(R0),R2 SW D(R0),R2 习题5A 如果Cy的代码在一个有顺序一政性存储模型的系统上运行，那么可能的执行结果是什么？ 列出所有的可能性，用MC和MD的值来表示。 习题5B 现在如果Cy的代码在一个不能保证顺序一致性的的系统上运行，但是任何单个处理器的访 问没有破坏存储器的相关性。系统有一条存储器屏蔽指令MEMBAR,这条指令确保，在其 执行之前执行的所有存储器番令对于在其后的指令来说都是全局可见的。 向Cy的代码添加MEMBAR指令，要求结果和以前一样，就好像系统是顺序一致性的。尽 量少使用MEMBAR指令
习题５：同步和连续一致性 Cy D.Fect 希望能在处理器Ｐ１和Ｐ２上运行下列代码。开始的时候，Ｍ［Ａ］，Ｍ［Ｂ］， Ｍ［Ｃ］和Ｍ［Ｄ］都是０。 习题 5.A 如果 Cy 的代码在一个有顺序一致性存储模型的系统上运行，那么可能的执行结果是什么？ 列出所有的可能性，用 M[C]和 M[D]的值来表示。 习题 5.B 现在如果 Cy 的代码在一个不能保证顺序一致性的的系统上运行，但是任何单个处理器的访 问没有破坏存储器的相关性。系统有一条存储器屏蔽指令 MEMBAR，这条指令确保，在其 执行之前执行的所有存储器指令对于在其后的指令来说都是全局可见的。 向 Cy 的代码添加 MEMBAR 指令，要求结果和以前一样，就好像系统是顺序一致性的。尽 量少使用 MEMBAR 指令