课程名称︰ 计算机结构 课程性质︰ 必修 课程教师︰ 洪士颢 开课学院： 电机资讯学院 开课系所︰ 资讯工程学系 考试日期（年月日）︰ 102.1.10 考试时限（分钟）： 150min 是否需发放奖励金： 是 （如未明确表示，则不予发放） 试题 : Undergraduated Computer Architecture, Fall 2012 Final Exam, 2013-01-10 If you agree, please sign your name below. I have not cheated nor have I received any help from other students in the exam. Student ID & name:______________________ 1. [15%] Branch Prediction. (a) [5%] Why is branch prediction important for processors with long pipelines? Draw a pipeline explain the problem(s) without branch prediction, and describe how branch prediction solves the problems(s). (b) [5%] A program consists of two nested loops, with a single branch instruction at the end of each loop and no other branch instruction anywhere. The outer loop is executed 20 times and their inner loop 10 times. What is the maximum accuracy of branch prediction if the branch predictor uses 2 bit of history for each branch to predict the outcome of the branches? (c) [5%] What are the software and hardware methods for improving the accuracy of branch prediction? What are the advantages and disadvantages of these methods? 2. [15%] Instruction-Level Parallelism (a) [5%] Given the following assembly code, if a pipeline processor can issue two instructions each cycle, what is the average cycle per instruction (CPI) without changing the code? Assuming the loop is repeated infinite times and the branch prediction is perfect. Loop: lw $t0, 0($s1) # $t0=array A[i] lw $t1, 1024($s1) # $t1=array B[i] addu $t0, $t0, $t1 # $t0=A[i]+B[i] sw $t0, 2048($s1) # store result to C[i] addi $s1, $s1, -4 # decrement pointer bne $s1, $zero, Loop # branch $s1!=0 (b) [5%] Could you rewrite/restructure the code to improve the CPI for the two-issue processor? (c) [5%] Suppose the processor has a SIMD instruction set extension: l4w can load four words from the memory to a 128-bit register, s4w can store four words a 128-bit register to the memory, and add4u can add two sets of four 32-bit integers in two 128-bit registers and put the results in the third 128-bit register. Please optimize the code with the SIMD instruction. 3. [20%] Memory Hierarchy (a) [5%] Consider a 4KB data cache. Each line (block) in the cache contains 8 words. Please draw the architecture of the cache for a direct-mapped configuration and a 2-way set-associative configuration. (b) [5%] A problem encountered with direct or even set-associate caches is thrashing , defined as execessive conflict misses resulting from the nature of particular memory address patterns. With the direct-mapped configuration mentioned in 3(a), a single-issue pipelined processor executes the code mentioned in 2(a). Calculate the CPI to show how thrashing impacts the performance. (c) [5%] Following 3(b), what if we change the data cache to 2-way set-associative, calculate the CPI to show how thrashing impacts the performance. (d) [5%] Following 3(b), if you can modify the code, what can you do to improve the performance? Show your modified code and calculate the CPI. 4. [10%] Virtual Machines (a) [5%] The notion of "virtual machine" is very popular these days. What is a virtual machine? What are virtual machine used for? (b) [5%] What is "virtual machine monitor"? List the functions of a virtual machine monitor. Describe how a virtual machine monitor works for each function. 5. [40%] Multicore Systems and Input/Output Please read this article before answering the following questions... 因为Nvidia早在1999年就推出第一款GPU绘图卡，2006年时更发表了GPU的开发框架CUDA（ Compute Unified Device Architecture），协助开发人员透过C语言或Fortran语言来运 用GPU的平行运算核心，2008年更推出专供高效能运算用的GPU绘图卡後，不只超级电脑， 许多HPC高运算伺服器也纷纷搭载Nvidia的GPU绘图卡，来提高运算效能。 ... 不过， Nvidia GPU绘图卡在平行运算领域的地位，开始受到了挑战。英特尔推出了Xeon Phi协 同处理器来对抗Nvidia的GPU。 英特尔推出超多核心架构的Xeon Phi协同处理器5110P，采用PCIe介面卡设计，可作为HPC 的运算加速卡，单颗处理器内建了60个运算核心，运算效能媲美1台1997年的超级电脑。 这款处理器采用22奈米制程，时脉1.053GHz，采用常见的PCIe介面卡设计，并搭配被动式 散热机制，功耗为225瓦，可搭载8GB的GDDR5记忆体。 除了5110P之外，另外还有还将推 出一款更低价的Xeon Phi 3100协同处理器，可支援6GB记忆体，同样采用22奈米制程，但 热设计功耗较高，达到300瓦特，预定明年上半年上市，售价将会低於2,000 美元。 英特尔亚太区暨大中华区高效能运算解决方案架构师Scott David表示，因为Xeon Phi协 同处理器延续了Xeon的x86架构，所以，可以沿用平行处理常用的开发语言如C、C++和 Fortran语言，也能沿用原有的平行运算模型，所以，在原有Xeon E5处理器环境中执行的 程式码，略作调整并重新编译，也可以在新的Xeon Phi处理器执行环境中，不需要重新改 写程式码，就可以提高效能。不过，台湾大学大资工系副教授洪士灏认为，虽然可以执行 ，但要充分发挥Xeon Phi的运算效能，还是得费心调校平行运算的程式。 若用核心数来比较，Nvidia的GPU绘图卡拥有高达2千多个运算核心，而Xeon Phi介面卡只 搭载一颗Xeon Phi，只有60核心。看起来GPU的核心数比Xeon Phi多很多，但是，洪士灏 认为，Nvidia的GPU绘图卡和Xeon Phi介面卡，同样都是可以用来加速HPC平行运算的效能 ，但两者适合的运算架构截然不同，对於平行运算的加速效果，不一定能放在同一个标准 上比较。 台湾大学大资工系副教授洪士灏表示，GPU类似SIMD架构，而Xeon Phi则是MIMD架构，两 者的运算架构截然不同，擅长的平行运算任务也不同。HPC常见高效能运算方式有两种， 第一种是资料平行化的运算方式，也就是Data Parallel，也可称为Stream计算。这种作 法适合处理大量资料，资料就像水流一样持续提供给处理器，处理器执行完运算指令後 ，处理过的资料不需保存在GPU加速卡中，而是继续提供下一笔资料给处理器，就像水 流一样持续流动。洪士灏表示，GPU擅长这种运算方式，运算量不大，也不用保留资料， 处理完就送走。 因为GPU擅长Stream风格的平行计算方式，接近是SIMD（Single Instruction, Multiple Data，单一指令多重资料）的运算模式，这是指所有运算核心都执行同一个指令，只是作 用在不同的资料上。而Xeon Phi则是MIMD架构（Multiple Instruction, Multiple Data ，多重指令多重资料）的运算模式，Xeon Phi中的60个核心，每个核心都可以处理不同的 指令和不同的资料。正因为如此，每个处理核心彼此需要许多同步和通讯的机制，所以， Xeon Phi处理核心的电路远比GPU的核心更复杂。 而SIMD架构的GPU，上千个处理核心会分群执行，例如一次使用256个核心，每个核心都是 同步执行相同的指令，所以，彼此之间不需复杂的通讯或同步机制，而且所有核心可以共 用同一个指令分派元件，所以，单一运算核心的电路可以简化，就很容易在单一晶片中设 计出大量的运算核心。但是，洪士灏认为，遇到蒙地卡罗模拟这类运算需求，例如汽车碰 撞模拟，要对同样的资料进行反覆大量运算的需求，GPU就不容易处理。 不过， Xeon Phi介面卡目前内建记忆体只有8GB，有些大型运算任务的资料量容易超过这 样的规模，程式得先切割资料後才能放入Xeon Phi中计算，这样作会影响运算效能，所以 ，Xeon Phi目前也不一定能满足这类大型运算的需求。 洪士灏表示，Xeon Phi的处理核心是x86架构，虽然复杂性相当於是十年前的处理器架构 ，只是现在集中到同一个晶片中，就像是在一张主机板上有60颗处理器一样，彼此组成运 算丛集。「若能找到适合这类处理器的应用，这种在单晶片中放入60核心的作法，能以更 低成本来取代现有的伺服器丛集或大型平行运算用的电脑。」他说。 (a) [5%] 以写作OpenMP程式为例，说明「充分发挥Xeon Phi的运算效能，还是得费心调 校平行运算的程式。」这句话所代表意义。此外，如果拿到的是nVidia的GPU，要怎 麽写平行程式？ (b) [5%] 假设你收到一台有Xeon Phi 5110P的机器，像要测试这台机器的计算能力，请 将2(a)的程式码转换成为C的程式，并且加入读进输入两个各自含有1 Tera笔资料的 档案和写出结果存档的部分，成为完整的C程式，然後将它改写为OpenMP的程式。 (c) [5%] 请分析以上这个OpenMP程式的效能。在此请先忽略读写档案的时间，假设A[] 和B[]皆已存在於频宽为320GB/s的DDR5的记忆体上，以文章中所提及的数据，估算 这个程式在Xeon Phi上所需要的执行时间，并指出效能的瓶颈。 (d) [5%] 要充分发挥Xeon Phi的运算效能，除了写OpenMP程式以外，还要使用到Xeon Phi每个核心上面所配备的Vector Engine。我们从Intel官网上找到以下的规格资料 ，请以此估算如果将你的OpenMP程式进一步作向量化(vectorize)之後，能够达到的 效能。 Intel® Xeon Phi™ coprocessor 5110P Specifications Ideal for: ‧Highly parallel applications using over 100 threads ‧Memory bandwidth‐bound applications ‧Applications with extensive vector use Key Specifications: ‧60 cores/1.053 GHz/240 threads ‧Up to 1 teraflops double-precision performance ‧8 GB memory and 320 GB/s bandwidth ‧Standard PCle* x16 form factor ‧Linux* operating system, IP addressable ‧Supported by the latest Intel® software development products ‧512-bit wide vector engine ‧32KB L1 1/D cache, 512KB L2 cache (per core) ‧8GB DDR5 memory (up to 320GB/s) ‧225W TDP ‧X16 PCle form factor (requires IA host) ‧Host OS: Red Hat Enterprise Linux 6.x, SuSE Linux 12+ (e) [5%] 承上题。现在，让我们考虑读取和写出资料所需的时间。假设输入的资料存放 在主机(Host)上的记忆体，而且输出的资料必须传送到主机的记忆体上。主机是一 台典型的伺服器，配备有一颗3GHz双核心的Intel Core i7处理器，50GB/s的DDR3 记忆体，而这张Xeon Phi 得加速卡装置在PCle x16的插槽上。假设这里的PCle其中 每一条通道(lane)的频宽是500MB/s，请计算程式的执行时间。 (f) [5%] 承上题。实际上，要处理大量资料，程式的输出入资料都必须放在硬碟或云端 储存空间上，假设主机上装置了一颗硬碟，其规格如下：512B sector, 10000rpm, 4ms average seek time, 100MB/s data transfer rate (I/O interface), 0.2ms controller overhead。请计算程式的执行时间，如果主机上可以加挂多颗硬碟， 以RAID5的方式建构，请问需要多少颗硬碟，才能让硬碟不至於成为效能的瓶颈？ (g) [5%] 承上题，假设我们有32台如上数配备有Xeon Phi的主机，如果A[]循序散布在 其中十六台主机的主记忆体中，B[]循序散布在另外16台主机的主记忆体中，每台 机器各自都有一个10Gigabit Ethernet，32台透过一个10Gigabit Ethernet Switch 连接在一起成为cluster。请计算这个cluster可以完成上述程式的最少时间(lower bound)。 (h) [5%] 承上题。如果我们把Xeon Phi换成nVidia的GPU卡，请说明： (1) 写作程式的方式有何不同？ (2) 程式的效能有何不同？ (3) 瓶颈会出现在哪里？ --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.30.136 修正标题 ※ 编辑: bztfir 来自: 140.112.30.136 (01/10 15:45)