东大并行程序设计考试真题解析

"这是一份关于东大计算机研究生研一并行程序设计课程的期末考试真题总结，包含了对并行任务粒度与并行执行时间关系的解释，以及共享存储器多处理机系统与消息传递多计算机系统的比较，还有非阻塞通信例程在消息传递编程中的应用及其安全性讨论。" 详细说明: 1. 并行任务粒度与并行执行时间的关系: - 并行任务粒度指的是将任务分解成可以同时执行的子任务的大小。粒度有粗粒度、细粒度和中粒度之分。 - 粗粒度并行中，每个进程包含大量指令，需要较长的执行时间，减少创建进程和通信的时间，但过多的粒度增大可能导致并发进程减少，增加并行执行时间。 - 细粒度并行则相反，进程内指令少，执行快，可以提高并行度，但频繁的通信会增加开销，需要在粒度选择上找到平衡。 2. 共享存储器多处理机系统与消息传递多计算机系统的比较: - 内存使用：共享存储器系统所有处理器共享同一地址空间，而消息传递系统中每个处理器有独立的本地存储器，仅能访问本地存储。 - 规模扩展：共享存储器系统扩展性较差，特别是在多核环境下，而消息传递系统扩展性强，易于构建大规模分布式系统。 - 编程考虑：共享存储器系统编程可通过并行编程语言、库方法或线程等方式，而消息传递系统要求程序员显式处理消息传递，增加了编程复杂性。 3. 非阻塞通信例程: - 非阻塞通信例程在语义上可能存在风险，因为它们可能导致程序在等待消息时陷入停滞。 - 使用非阻塞通信的理由包括避免死锁、提高通信速度和整体效率。 - 为了保证语义安全性，可以利用并发原语如CAS（Compare and Swap）来代替锁，确保线程安全。 - 阻塞与非阻塞的比较在于，阻塞例程会等待消息完成，而非阻塞例程允许程序继续执行其他任务。 - 非阻塞例程适用于需要高效利用处理器资源和避免等待的情况，而必须阻塞的情形通常涉及依赖特定消息的同步点，例如确保数据一致性。 这份考试真题总结涵盖了并行计算的关键概念，对于理解并行程序设计的原理和实践具有很高的价值。学习者可以通过深入研究这些知识点来提升自己在并行计算领域的理论基础和实践能力。