并行计算机体系结构-改卷系统设计.doc

并行计算机阅卷系统模型学号：L2101901 姓名：许丰平一：要求：1.MIMD并行计算机模型； 2.实现多人同时阅卷，任务分配与组合，提高系统性能；二：模型分析：PCAM设计过程，即:任务划分（Partitioning）、通信（Communication）分析、任务组合（Agglomeration）、处理器映射（Mapping）。 这是一种设计方法学，是实际设计并行算法或程序的自然过程，其基本要点是： 首先尽量开拓算法的并发性和满足算法的可扩放性；然后着重优化算法的通信成本和全局执行时间。 并行计算的PCAM设计方法中的任务划分和通信分析阶段主要考虑如并发性和可扩放性等与机器无关的特性，寻求开发出具有这些特性的并行算法，基本上与底层体系结构和编程模型无关；而到任务组合和处理器映射阶段才开始将注意力转移到局部性和别的与性能有关的问题上。图为，算法的PCAM设计过程如图所示，PCAM设计方法的四个阶段可以简述如下：划分：将整个计算分解为一些小的任务，其目的是尽量开拓并行执行的机会；通信：确定诸任务执行中所需交换的数据和协调诸任务的执行，由此可检测上述划分的合理性；组合：按性能要求和实现的代价来考察前两阶段的结果，必要时可将一些小的任务组合成更大的任务以提高性能或减少通信开销；映射：将每个任务分配到一个处理器上，其目的是最小化全局执行时间和通信成本以及最大化处理器的利用率。三算法分析假设考卷分为：选择题（20题），填空题（20题），问答题（20题），（有两类：文学类，小说类）。总共有15个老师加一个领导，领导负责收集各部分成绩并计算总分。1. 选出5个最适合选择题的老师让他们负责选择题，其中文学类由两位老师负责（分别从头和尾同时改卷，各做一半），小说类由另两位老师负责（分别从头和尾同时改卷，各做一半），还有一个老师为组长负责通信，收集成绩和统计选择题的得分，并把成绩交给领导。 选出5个最适合填空题的老师让他们负责填空题，文学类由两位老师负责（分别从头和尾同时改卷，各做一半），小说类由另两位老师负责（分别从头和尾同时改卷，各做一半），还有一个老师为组长负责通信，收集成绩和统计选择题的得分，并把成绩交给领导。选出5个最适合问答题的老师让他们负责问答题，文学题由两位老师负责（分别从头和尾同时改卷，各做一半），小说题由另两位老师负责（分别从头和尾同时改卷，各做一半），还有一个老师为组长负责通信，收集成绩和统计选择题的得分，并把成绩交给领导。2选择题，填空题，问答题中，文学题的两位老师相互之间要通信，小说题的两位老师也要相互通信，已确定各自的进度。这些通信都是由小组长完成的。领导负责选择题，填空题，问答题之间的通信。3.把选择题，填空题，问答题中的文学类组合，把选择题，填空题，问答题中的小说类也组合，例如选择题文学类里的一个老师完成了任务，那他先帮另一个老师完成任务，然后去看填空题，问答题中文学类是否还有未完成的任务。这时领导的任务是查看文学类（或者小说类）里面哪几个老师空闲，哪几个老师忙，然后让闲的老师去帮忙的老师。4处理机映射问题，文学类和小说类可以并发执行，应该放在不同的处理机上；如果只用两个处理器来分别处理文学类和小说类，虽然使通信达到了最小值，但是并发度很差。考虑到通信和并发性的需要，我们可以把选择题里的文学类和小说类分别给两个处理机（处理机1和处理机2），把填空题里的文学类和小说类分别给两个处理机（处理机3和处理机4），把问答题里的文学类和小说类分别给两个处理机（处理机5和处理机6）。可以考虑把3个组长和一个领导映射为一个处理机（处理机0）。四具体处理机执行过程假如，处理机1（选择题的文学类）完成了任务，这时处理机1空闲。处理机0（3个组长和一个领导）发现处理机1空闲，而处理机3（填空题的文学类）和处理机5（问答题的文学类）很忙，