Ceng 471 parallel Computing
Final
Jan 18, 2006 15.00-17.00
Good Luck!

1 (40 Pts) Summation of numbers is performed both in serial and parallel ways. For parallel computation, the environment is the networked workstations and the sequential computation is also done in the same cluster. The following table is obtained;

TIME	$nproc=1$	$nproc=2$	$nproc=3$	$nproc=4$	$nproc=5$	$nproc=6$
100	0.013541	0.015713	0.015420	0.017393	0.018216	0.025741
200	0.018175	0.018387	0.019951	0.022900	0.026010	0.030067
500	0.036738	0.027887	0.032696	0.041647	0.433383	0.049059
1000	0.072881	0.047775	0.060789	0.093839	0.097799	0.113722
2000	0.145120	0.078808	0.111233	0.188817	0.143317	0.211288
5000	0.365731	0.197714	0.269206	0.313151	0.371891	0.347993
10000	0.749948	0.390106	0.507074	0.636745	0.665334	0.705855
20000	1.571937	0.865633	1.086707	1.225067	1.273847	1.338983

i

Fill the following tables.

Speed-Up	$nproc=2$	$nproc=3$	$nproc=4$	$nproc=5$	$nproc=6$
100	0.86177050849615	0.878145265888456	0.778531593169666	0.743357487922705	0.526047939085506
200	0.98847011475499	0.910981905668889	0.793668122270742	0.698769703960015	0.604483320584029
500	1.317388030265	1.12362368485442	0.882128364588086	0.084770284021293	0.748853421390571
1000	1.52550497121926	1.19891756732304	0.776660024083803	0.74521211873332	0.640869840488208
2000	1.84143741752106	1.30464880026611	0.768574863492164	1.01258050335969	0.686835030858355
5000	1.84979819334999	1.35855441557766	1.16790621776715	0.983436006786935	1.05097228967249
10000	1.92242108555111	1.4789715110615	1.17778388522878	1.12717522327132	1.06246750394911
20000	1.81593931839475	1.4465141017772	1.28314369744675	1.23400769480165	1.17397831040424

Efficiency	$nproc=2$	$nproc=3$	$nproc=4$	$nproc=5$	$nproc=6$
100	0.430885254248075	0.292715088629485	0.194632898292416	0.148671497584541	0.0876746565142509
200	0.494235057377495	0.303660635222963	0.198417030567686	0.139753940792003	0.100747220097338
500	0.658694015132499	0.374541228284806	0.220532091147021	0.0169540568042586	0.124808903565095
1000	0.762752485609629	0.399639189107678	0.194165006020951	0.149042423746664	0.106811640081368
2000	0.920718708760532	0.434882933422036	0.192143715873041	0.202516100671937	0.114472505143059
5000	0.924899096674995	0.452851471859221	0.291976554441787	0.196687201357387	0.175162048278749
10000	0.961210542775553	0.492990503687167	0.294445971307195	0.225435044654264	0.177077917324852
20000	0.907969659197373	0.482171367259068	0.320785924361688	0.24680153896033	0.19566305173404

ii

Analyze the tables in detail.

iii

How many processor should be used for a specific value of $N$? Why?

iv

Fill the following table.

TIME/N	$nproc=2$	$nproc=3$	$nproc=4$	$nproc=5$	$nproc=6$
100	0.00013541	0.00015713	0.0001542	0.00017393	0.00018216
200	0.000090875	0.000091935	0.000099755	0.0001145	0.00013005
500	0.000073476	0.000055774	0.000065392	0.000083294	0.000866766
1000	0.000072881	0.000047775	0.000060789	0.000093839	0.000097799
2000	0.00007256	0.000039404	0.0000556165	0.0000944085	0.0000716585
5000	0.0000731462	0.0000395428	0.0000538412	0.0000626302	0.0000743782
10000	0.0000749948	0.0000390106	0.0000507074	0.0000636745	0.0000665334
20000	0.00007859685	0.00004328165	0.00005433535	0.00006125335	0.00006369235

Can we estimate the $N$ values for each column that communication time overheads computation time?

2 (30 Pts) Answer the following questions, choose only 5 of them.

v

Describe the Flynn's classification for computers. Which type of the computer we have made use of?

vi

Is it possible to have a system efficiency (E) of greater than %100? Discuss.

vii

Describe Blocking and Nonblocking Message-Passing.

viii

Compare the point-to-point and collective communications.

ix

What is embarrassingly parallel computations? Explain by an example.

x

What could be the possible advantageous of Divide-and-Conquer approach over the other partitioning strategies?

xi

Describe the pipelined computations technique by drawing a space-time diagram. Can this technique be applicable to today's computer architectures?

xii

What is the data parallel computations? Example it.

xiii

Describe load balancing.

xiv

What could be your criteria to choose a shared- or distributed-memory programming technique.

3 (30 Pts) Discuss the parallel programming/computing aspects of your presentation topic.