Homework1第1頁，共15頁。Explain

theConcepts系統(tǒng)結(jié)構(gòu)(CA:Computer

Architectute)、高級(jí)系統(tǒng)結(jié)構(gòu)(Advanced

CA)、Amdahl

law、SCALAR

PROCESSING、LOOK-AHEAD、PVP、SMP、MPP、DSM、COW、GCE、CISC、RISC、VMM、SUPERCOMPUTER、SVM、MAINFRAME、COMPUTER

SYSTEM

ON

CHIP、PARALLELARCHITECTURE

INTO

SINGLE

CHIP、MOORE定律、UMA、NUMA、COMA、CC-NUMA、NORMA、SHELL

ARCHITECTURE,

PRAM,BSP,

Log

PExplain

the

Flynn

classify

and

its

semantics.Where

are

the

difficulties

of

Parallel

Processing?What

is‘Parallel(并行)、concurrent(并發(fā))and

Simultaneous’(同時(shí))separately?Assume

that

a

system

component

be

speeded

to

10

times,

itspast

processing

time

accounts

for

40%

of

the

system,

how

muchwill

be

the

system

performance

improved?Please

draw

the

memory

Hierarchy

chart.第2頁，共15頁。homework24Explaining

ConceptionsRISC,

CISC,

VLIW,

SUPER-SCALAR,

SUPER-PIPELINE,SUPER-SCALAR-SUPER-PIPELINE,

IPC,

SINGLEISSUE,MULTIPLE

ISSUE,

OOO,

Multi-ThreadingIn

ideal

case,

please

give

the

performances

for

SUPER-SCALAR, SUPER-PIPELINE,

SUPER-SCALAR-SUPER-PIPELINE,

and

give

N=8examples

and

their

average

IPC.Please

describe

the

CPU

technology

in

recent

years,

and give

an

example

to

illustrate

their

technical

parameters.Please

give

computing

trace

ofa[i+7]=b[j+1]+c[k+8]+d[m+10]

for

T9000How

to

solve

the

multicore

memory

wall

problem?6

Simple

computer

design

test:Supposed

there

are

a

simple

CPU

with

A15-A0,D7-D0,read

andwrite,

an

register

and

Tri-state

buffers

for

I/O

device,

a8k*8

ROM

with

A12-A0,D7-D0,CE

and

OE,

and

a

8k*8

RAM

with

A12-A0,D7-D0,CE,RD

and

WR.

Please

you

design

the

circuit

of

asimple

computer.第3頁，共15頁。Homework§

1)

There

is

a

program

in

a

40MHz

processor，its

numberof

integer

arithmetic

instructions

is

45000

and

the

clockis

1.The

number

of

instructions

with

data

operations

is32000

and

the

clock

is

2.

The

number

of

floatinstructions

is

15000

and

its

clock

2.

The

number

ofinstructions

such

as

JMP

etc

is

8000

and

its

clock

is2.Please

give

its

CPI、MIPS

and

the

CPU

execution

time.§

2)

If

the

communication

cost

in

a

SP2

machine

is

t（m）=46+（0.035）m,please

give

its(漸進(jìn)帶寬)r∞and

its(半峰值信息長度)m1/2.§

3)

If

a

N*N

matrix

A

is

multiplied

by

a

N*N

matrix

B,its

time

is

T1=CN3

s,

but

the

execution

time

in

amachine

with

n

nodes

is

Tn=(CN3/n+bN2/square-root(N))

s，here,C,N

and

b

is

a

constant.

Please

you

give

itsSpeedup

under

fix-workload,

fix-time

and

fix-memory

usage.第4頁，共15頁。§

4)(等效率)see

:kumar

V,Rao

V

N.Parallel

depth

–firsh

search,part

ii:Analysis.Int’I

J

of

Parallel

Programming,1987,16(6):501-519§

5)(等速度)see:Sun

X

H,etc.scalability

of

parallel

algorithm-machine

combina-tions.IEEE

transaction

on

parallel

and

distributed

system,1994,5(6):519-613§

6)(等延遲)see:Zhang

X

D,etc.latency

metric:an

experimental

methodfor

measuring

and

evaluating

parallel

program

and

architecturescalability.J

of

parallel

and

distributed

Computing,1994,22:392-410.HOMEWORK1解釋Concepts

State

network(靜態(tài)網(wǎng)絡(luò))、Daymic

network(動(dòng)態(tài)網(wǎng)絡(luò))、crossbar(交叉開關(guān))、Multi-buses(多總線)2

Draw

N=25

MESH

3寫出用混洗交換網(wǎng)絡(luò)模擬單級(jí)立方體網(wǎng)絡(luò)的互連

函數(shù)表達(dá)式please

give

the

single

cube

function

byusing

SHUFFLE-EXCHANGE

NETWORK

4

How

much

have

the

different

bus

ArbitrateAlogrithms?What

is

its

merit

and

demerit?總線仲裁有幾種，各有何優(yōu)缺點(diǎn)？第5頁，共15頁。2023-08-015第6頁，共15頁。HOMEWORK1

THERE

ARE

P1,P2,P3,P4

AND

M1,M2,M3,M4,PLEASE

USE

2*2

CROSSBAR

SWITCH

BOX

TO

DESIGN

A

CONNECTIONNETWORK

OF

P1~M2,P2~M4,P3~M1,P4~M3.2

WHAT

IS

DS-LINK?3

WHAT

IS

DIFFERENCE

BETWEEN

MESSAGE-PASSINGAND

SHARED

MEMORY?4

WHAT

ARE

WORMHOLE

COMMUNICATION

AND

ITSPERFORMANCE?5

Explaining

that

Myrinet,HiPPI,FDDI,ATM,SCI,and

100BaseT。第7頁，共15頁。

6采用蟲洞尋徑的超立方體多機(jī)系統(tǒng)中，如果相鄰節(jié)點(diǎn)間有一對(duì)方向相反的單向通道，試證明在該系統(tǒng)上實(shí)現(xiàn)立方體編碼下的尋徑不會(huì)死鎖。(In

a

supercube

network

withwormhole

communication,if

there

is

a

pairopposite

one-way

link

between

any

two

neighbournodes,please

try

to

proof

that

the

network

can

notbe

deadlocked

when

looking

for

path)第8頁，共15頁。自由任選（課外大作業(yè)）任選一個(gè)具有代表性的BENCHMARK小程序,要求:請(qǐng)分析其源程序,寫出其中的數(shù)據(jù)執(zhí)行流程(包括:數(shù)據(jù)類型、具體值和時(shí)序關(guān)系);在1)的基礎(chǔ)上,對(duì)其目標(biāo)代碼再進(jìn)行數(shù)據(jù)流分析，寫出其中的數(shù)據(jù)執(zhí)行流程(包括:數(shù)據(jù)類型、具體值和時(shí)序關(guān)系);觀察并寫出與1）中間結(jié)果的差別表。3）在1）和2）基礎(chǔ)上，對(duì)其數(shù)據(jù)執(zhí)行的流程進(jìn)行數(shù)據(jù)預(yù)取優(yōu)化,并在具有CACHE的計(jì)算機(jī)上進(jìn)行實(shí)際求解。要求給出具體數(shù)據(jù)預(yù)取的優(yōu)化方法和改進(jìn)的測試時(shí)間效果表。（可加5-10分）第9頁，共15頁。用PVM或MPI并行軟件工具編寫一個(gè)并行程序，要求至少有2或3個(gè)并行任務(wù)進(jìn)行協(xié)同求解某問題。Key

Tech

and

Theory？What

are

Architecture？What

areWhat

are

Meeting

Problems？1、Earth-Simulator2、Blue

Gene3、Beowulf

With

PoPC

Cluster4、Grid

Computing5、Pervasive

Computing6、P2P

Computing7、Special

PoPC

Cluster

Such

as

Web

Cache

Cluster第10頁，共15頁。作業(yè)homework11

H0(n)=nmH0(Hc(n)=nmH0(-n

)/(-n

)/(-

)+n(1-m)H0;please

delete

theand-

)+n(1-m)H0by

using,then

draw=0.2(畫出其函數(shù)the

function

figure

when

m=0.5,關(guān)系圖)Homework2事件狀態(tài)A狀態(tài)B說明初始無效無效（I）數(shù)據(jù)未裝入CPU

A讀獨(dú)占無效（I）讀操作cache失效，裝入CPU

B讀共享共享（S）讀操作cache失效，裝入后共享CPU

A寫修改無效（I）寫操作命中CPU

B讀共享共享（S）讀操作失效，裝入CPU

B寫無效修改（M）寫操作命中MESI

ProtocolCan

you

fill

thestates?第11頁，共15頁。關(guān)于可用性中的檢查點(diǎn)問題

CHECKPOINT(a,b,c)?可在內(nèi)核、庫、應(yīng)用a程序三級(jí)發(fā)生；bdcxyzPQRProcess第12頁，共15頁。一致性快照Checkpoint

Consistency

Snapshot（a--Consistency一致;b---No

Consistency不一致）

如果進(jìn)程之間不存在一個(gè)進(jìn)程的檢查點(diǎn)已接收了消息，而另一進(jìn)程的檢查點(diǎn)還未發(fā)送這個(gè)消息。稱一致性快照。abxyzPQC

?第13頁，共15頁。RIf

there

is

not

the

process

which

receives

a

message

at

checkpoint

and

anotherprocess

has

not

sent

the

message

at

checkpoint,

then

we

say

that

the

relatedcheckpoints

are

the

Consistency

Snapshot第14頁，共15頁。homework¨

1.

What