 Algorithm Use
Analysis |
MST(Minimum Spanning Tree Finding)
Professor : Chang-Biau Yang (楊昌彪)
Student : 8724607 Shu-yuan Lin (林淑媛)
 Algorithm UseUsing EREW MST Algorithm, each processor process the same nodes (N = # of processors). Then each processor compair data parallel-ly, and using Tree algorithm for global compair and broadcast. With time complexity O(n2/N).
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Analysis (1) Total cpu time for each # of processor and for each kind of data..
At this table, we see that mult-processores maybe not faster than 1-processor. And we don't draw the graph for this table, since its data with large difference, and we cannot see the different when data small. (2) Compair find local min node..
At those tables and graphs, we see the each cpu send datas for compair and broadcast datas need much time. And our data-structure use file for input, It needs large size memory for store. So, In this case we cannot see the efficient of mult-processor. But, we still see that mult-processor can distract working.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Question
Discuss
Although SP2 with mult-processor, but each cpu with its own memory, not share the memory. Than, each time we need to broadcast datas to each processor and need wait each processor ready to send data, this step use time more than ten times of processor doing commands. Thus, if we can change data structure for saving our inilization data, maybe can saving more time. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Source Program |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
