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

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