跳到主要内容

2019-2020学年下学期期末

2019-2020学年下学期期末试卷（A）​

一、不定项选择题（选择一个或多个正确选项，20 分，每题 4 分）​

  1. 对并行程序描述正确的是（ ）。

    A. 减少所有系统开销

    B. 要求资源共享

    C. 提高系统运行速度和处理能力

    D. 电源管理能力更强

  2. 以下属于读后写的数据依赖关系的是（ ）。

    A. a=2a=2；b=20b=20

    B. a=b+1a=b+1；a=4a=4

    C. b=ab=a；b=2b=2

    D. a=b+1a=b+1；b=4b=4

  3. 对于共享内存系统描述不正确的是（ ）。

    A. 处理器拥有自己独特的地址空间

    B. 处理器间以隐式的通信完成数据共享

    C. 线程间的协调通过共享变量的锁和屏障实现

    D. 每个处理器可以访问每个内存空间

  4. 在 OpenMP 中，下列哪些是共享的（ ）。

    A. shared variables

    B. loop index

    C. static variables

    D. private variables

  5. 以下关于消息传递的描述中，正确的是（ ）。

    A. 消息传递是共享内存并行编程的主要替代方案

    B. 消息传递没有数据竞争

    C. 消息传递是不可移植的

    D. 对消息传递库的调用在单处理器上运行

二、简答题（30 分，每小题 10 分）​

  1. 请简述什么是死锁？

  2. 请简述 cache 映射的三种方式的原理。

  3. 请简述指令级并行的流水线和多发射机制，及其两种多发射方法。

三、分析题（30 分，每小题 15 分）​

  1. 某个程序需要运行 101210^{12} 条指令来解决一个特定问题，一个单处理器系统可以在 10610^6 秒（大约 11.6 天）内完成。所以，一个单处理器系统平均每秒运行 10610^6 条指令。现在假设程序已经实现并行化，可以在分布式内存系统上运行。该并行程序使用 pp 个处理器。每个处理器执行 1012/p10^{12}/p 条指令并必须发送 109(p−1)10^9(p-1) 条消息。执行该程序时，不会有额外的开销，即每个处理器执行完所有的指令并发送完所有的消息之后，程序就完成了，而不会有由诸如等待消息等事件所产生的延迟。那么，

    1. 假设发送一条消息需要耗费 10−910^{-9} 秒。如果程序使用 1000 个处理器，每个处理器的速度和单个处理器运行串行程序的速度一样，那么该程序的运行需要多少时间？

    2. 假设发送一条消息需要耗费 10−310^{-3} 秒。如果程序使用 1000 个处理器，那么该程序的运行需要多少时间？

  2. 假定 comm_sz=8，n=16。

    1. 画一张图来说明进程 0 要分发 nn 个元素的数组，怎样使用拥有 comm_sz 个进程的树形结构的通信来实现 MPI_Scatter。

    2. 画一张图来说明原先分布在 comm_sz 个进程间的 nn 个数组元素由进程 0 保存，怎样使用树形结构的通信来实现 MPI_Gather。

四、程序题（20 分）​

  1. 使用 OpenMP 实现生产者-消费者程序，其中一些线程是生产者，另外一些线程是消费者。它们将读出的文本行插入到一个共享的队列中。消费者从队列中取出文本行，并对文本行进行分词。符号是被空白符分开的单词，当消费者发现一个单词后，它将该单词输出到 stdout。（要求：输出的单词需要给出是哪个线程输出的）