并行計(jì)算機(jī)體系結(jié)構(gòu)-改卷系統(tǒng)設(shè)計(jì)

1、精品文檔并行計(jì)算機(jī)閱卷系統(tǒng)模型學(xué)號(hào)：L2101901 姓名：許平一：要求：1.MIMD并行計(jì)算機(jī)模型；2.實(shí)現(xiàn)多人同時(shí)閱卷，任務(wù)分配與組合，提高系統(tǒng)性能；二：模型分析：PCAM設(shè)計(jì)過程，即：任務(wù)劃分(Partitioning )、通信(Communication )分析、任務(wù)組合(Agglomeration )、處理器映射(Mapping )。這是一種設(shè)計(jì)方法學(xué)，是實(shí)際設(shè)計(jì)并行算法或程序的自然過程， 其基本要點(diǎn)是：首先盡量開拓算法的并發(fā)性和滿足算法的可擴(kuò)放性；然后著重優(yōu)化算法的通 信成本和全局執(zhí)行時(shí)間。并行計(jì)算的PCAM設(shè)計(jì)方法中的任務(wù)劃分和通信分析階段主要考慮如并發(fā)性和可擴(kuò)放性等與機(jī)器無關(guān)的

2、特性， 尋求開發(fā)出具有這些特性的并行算法， 基本 上與底層體系結(jié)構(gòu)和編程模型無關(guān)；而到任務(wù)組合和處理器映射階段才開始將注 意力轉(zhuǎn)移到局部性和別的與性能有關(guān)的問題上。OOOOOOOOOOOOOOOOOOOOOOOOOOOO精品文檔圖為，算法的PCAM 設(shè)計(jì)過程如圖所示，PCAM 設(shè)計(jì)方法的四個(gè)階段可以簡述如下：劃分：將整個(gè)計(jì)算分解為一些小的任務(wù)，其目的是盡量開拓并行執(zhí)行的機(jī)會(huì)；通信：確定諸任務(wù)執(zhí)行中所需交換的數(shù)據(jù)和協(xié)調(diào)諸任務(wù)的執(zhí)行，由此可檢測(cè)上述劃分的合理性；組合：按性能要求和實(shí)現(xiàn)的代價(jià)來考察前兩階段的結(jié)果，必要時(shí)可將一些小的任務(wù)組合成更大的任務(wù)以提高性能或減少通信開銷；映射：將每個(gè)任務(wù)分配到一

3、個(gè)處理器上，其目的是最小化全局執(zhí)行 時(shí)間和通信成本以及最大化處理器的利用率。三算法分析假設(shè)考卷分為：選擇題（20 題） ，填空題（20 題） ，問答題（20 題） ， （有兩類：文學(xué)類，小說類）。總共有15 個(gè)老師加一個(gè)領(lǐng)導(dǎo)，領(lǐng)導(dǎo)負(fù)責(zé)收集各部分成績并計(jì)算總分。1 . 選出 5 個(gè)最適合選擇題的老師讓他們負(fù)責(zé)選擇題，其中文學(xué)類由兩位老師負(fù)責(zé)（分別從頭和尾同時(shí)改卷，各做一半），小說類由另兩位老師負(fù)責(zé)（分別從頭和尾同時(shí)改卷，各做一半），還有一個(gè)老師為組長負(fù)責(zé)通信，收集成績和統(tǒng)計(jì)選擇題的得分，并把成績交給領(lǐng)導(dǎo)。選出 5 個(gè)最適合填空題的老師讓他們負(fù)責(zé)填空題，文學(xué)類由兩位老師負(fù)責(zé)（分別從頭和尾同時(shí)改卷，

4、各做一半），小說類由另兩位老師負(fù)責(zé)（分別從頭和尾同時(shí)改卷，各做一半），還有一個(gè)老師為組長負(fù)責(zé)通信，收集成績和統(tǒng)計(jì)選擇題的得分，并把成績交給領(lǐng)導(dǎo)。選出 5 個(gè)最適合問答題的老師讓他們負(fù)責(zé)問答題，文學(xué)題由兩位老師負(fù)責(zé)（分別從頭和尾同時(shí)改卷，各做一半），小說題由另兩位老師負(fù)責(zé)（分別從頭和尾同時(shí)改卷，各做一半），還有一個(gè)老師為組長負(fù)責(zé)通信，收集成績和統(tǒng)計(jì)選擇題的得分，并把成績交給領(lǐng)導(dǎo)。2 選擇題，填空題，問答題中，文學(xué)題的兩位老師相互之間要通信，小說題的兩位老師也要相互通信，已確定各自的進(jìn)度。這些通信都是由小組長完成的。領(lǐng)導(dǎo)負(fù)責(zé)選擇題，填空題，問答題之間的通信。3 .把選擇題，填空題，問答題中的文學(xué)類

5、組合，把選擇題，填空題，問答題中的小說類也組合，例如選擇題文學(xué)類里的一個(gè)老師完成了任務(wù)，那他先幫另一個(gè)老師完成任務(wù)，然后去看填空題，問答題中文學(xué)類是否還有未完成的任務(wù)。這時(shí)領(lǐng)導(dǎo)的任務(wù)是查看文學(xué)類（或者小說類）里面哪幾個(gè)老師空閑，哪幾個(gè)老師忙，然后讓閑的老師去幫忙的老師。4 處理機(jī)映射問題，文學(xué)類和小說類可以并發(fā)執(zhí)行，應(yīng)該放在不同的處理機(jī)上；如果只用兩個(gè)處理器來分別處理文學(xué)類和小說類，雖然使通信達(dá)到了最小值，但是并發(fā)度很差?？紤]到通信和并發(fā)性的需要，我們可以把選擇題里的文學(xué)類和小說類分別給兩個(gè)處理機(jī)（處理機(jī) 1 和處理機(jī)2） ，把填空題里的文學(xué)類和小說類分別給兩個(gè)處理機(jī)（處理機(jī) 3 和處理機(jī)4） ，把問答題里的文學(xué)類和小說類分別給兩個(gè)處理機(jī)（處理機(jī) 5 和處理機(jī)6） ?？梢钥紤]把3 個(gè)組長和一個(gè)領(lǐng)導(dǎo)映射為一個(gè)處理機(jī)（處理機(jī) 0） 。四具體處理機(jī)執(zhí)行過程假如， 處理機(jī) 1 （選擇題的文學(xué)類）完成了任務(wù)，這時(shí)處理機(jī)1 空閑。 處理機(jī)0（ 3 個(gè)組長和一個(gè)領(lǐng)導(dǎo)）發(fā)現(xiàn)處理機(jī) 1 空閑，而處理機(jī) 3（填空題的文學(xué)類）和處理機(jī) 5（問答題的文學(xué)類）很忙，并且處理機(jī) 1 和處理機(jī)3