计算机体系结构-hw10
前言
中国科学院大学张科老师的计算机体系结构的课后作业，不保证正确，请辩证看待。
SIMD Processing
Q1
阵列处理器的功能单元可以做很多的操作(MUL、ADD等)，在同一时间做相同操作，在同一空间做不同操作(并行)。对功能单元的要求高，硬件更加复杂，成本高，效率高（相比向量处理器）。
向量处理器的功能单元只会做特定的操作，在同一时间做不同的操作，在同一空间做相同操作（流水线方式）。对功能单元的要求低（相比阵列处理器），硬件简单，成本低，效率低（相比阵列处理器）。
一个array processor 需要16个功能单元（并行），但是一个vector processor 只需要1个功能单元即可（流水线工作）。
因此，选择：The traditional array processor
Q2
由于这道题要求fully piplined,即每一个时钟周期都可以开启一个新的运算，因此我们假设功能单元的数量为4.
For a vector length of 1:
The traditional vector processor: 5 cycles
The traditional array processor: 5 cycles
For a vector length of 4:
The traditional vector processor: 8 cycles(第一个元素需要5个cycles，剩余元素需要3个cycles即可完成)
The traditional array processor: 5 cycles
For a vector length of 16:
The traditional vector processor: 20 cycles(第一个元素需要5个cycles，剩余元素需要15个cycles即可完成)
The traditional array processor: 5 cycles
GPUs and SIMD I
Q1
warps = N / 32（结果需要向上取整）
Q2
线程需要执行的总指令个数：32/*2 = 60
由于第一条指令，每个线程都会执行，因此已执行的指令数：32
第二条指令，由于A的数据分布：24个1，8个0。因此，只会有8个线程执行第二条指令。因此，已执行的指令数：32+8 = 40
因此，SIMD利用率 = 40 / 64 = 0.625
Q3
YES,可以使SIMD利用率达到100%，只需要保证A中的连续32个元素要么都可以被3整除，要么都不可以被3整除即可
由于条件语句跟B数组无关，因此B数组内容无需改动。（B可以为任意整数）
Q4
YES,可以使SIMD利用率达到56.25%，只需要保证A中的元素，每32个元素有4个元素可以被3整除（值为0），剩余28个元素不可以被3整除（值为1）即可。（即：36 / 64 = 0.5625）
由于条件语句跟B数组无关，因此B数组内容无需改动。（B可以为任意整数）
Q5
NO,不可以使SIMD利用率达到50%。因为，当每32个元素中只有一个元素可以被3整除，此时SIMD利用率为：33 / 64 = 51.5625%（至少为51.5625%）
Q6
采用dynamic warp formation,我们可以得到如下的答案：
X' = {11000000000...000011}
Y' = {10000000000...000000}
Z' = {00000000000...000000}
Q7
由于分支条件与B无关，因此不考虑B
对于A的数据分布，每32个线程中，都有24个1，8个0。
由于这些数据都是重复排列的，线程无法跨lane，因此无法进行动态的warp合并。
因此，即使采用dynamic warp formation，也无法提高SIMD利用率。
除非，A的数据分布发生变化，每64个线程中，都有24个1，8个0，24个0，8个1。这样的话，warp之间可以进行合并,可以提高SIMD利用率。
GPUs and SIMD II
Q1
the number of warps = 1024 / 64 = 16
Q2
最大可能的SIMD利用率为100%。
Q3
对于B数组中的每连续的64个元素，要么全为0，要么全为正数，要么全为负数。（此时利用率就是100%）
- 全为0，所有线程只会执行第一条和第二条指令。
- 全为正数，所有线程都不会执行第5条指令。
- 全为负数，所有线程都会执行这6条指令。
Q4
要想获得最小的SIMD利用率，确保只会有一个线程进入到每一个分支语句。使得每一个分支语句后的指令的SIMD利用率为1/64。
具体来说，前两条指令，每一个线程都会执行，我们要保证每个warp中，只会有一个线程通过指令2（第一个分支）和指令4（第二个分支），确保以下指令只会有一个线程执行。
- C[i] = A[i] /* B[i]
- if(C[i] < 0)
- A[i] = A[i] + 1
- A[i] = A[i] - 2
因此，最小的SIMD利用率：(64/2 + 4) / 64/6 = 132 / 384
Q5
要想保证B数组中只会有一个元素可以同时通过指令2和指令4，B数组的数据分布为：每64个元素中，只会有一个元素为负数，其余必须为0（此时SIMD利用率最小）
致谢
[1] 以上图片来自于计算机体系结构刘珂老师的课程