Parallel Computer Architecture

86

CHAPTER

2 Parallel Programs

FIGURE

2.4

Illustration

of

the impact

of

limited concurrency:

(a)

one processor; (b)

p

proces-

sors,

n

2

operations serialized; (c)

p

processors,

p

operations serialized. The x-axis is time, and

the

y-axis is

the

amount

of

work available (exposed by the decomposition)

to be

done

in

parallel

at

a given

time,

(a)

shows

the

profile

for a

single processor,

(b)

shows

the

original case

in the

example, which

is

divided into

two

phases: one fully concurrent and

one

fully serialized,

(c)

shows

the

improved version,

which

is

divided into three phases:

the

first

two

fully concurrent and

the

last fully serialized

but

with

a ...