|
A parallel program can use these distributed computing
resources efficiently, and a good parallelized program depends
on the good designing and analyzing rocesses. In this thesis, we
use Ian Foster''s designing method of parallel program and
analyze through the four steps of decomposition, communication,
agglomeration and mapping. We use a case study on analytical
solution for Stochastic Timed Petri Nets which use three
algorithms to solve the problems, they are, Gauss elimination
method, Jacobi method and Gauss-siedel method. The
computations often stop because of the page faults. Here we
analysis the Embedded Markov Model matrices from two different
ways: Depth Search First and Breadth Search First. Through the
comparison, we find that breadth search first will be better for
overcoming the insufficient computation resource problem. If the
embedded Markov model matrix has been existed, we also provide a
method for translating the original matrix into a simpler one.
Under limited computation resource, this algorithm will execute
concurrently and be able to process bigger matrices. In the
second and third, we use breadth search first or those matrix
has been translated, such that each task can acquire the data
just from itself. And this will decrease the communication
amount and message length, so as to ease the communication cost
and increase the concurrency. After all of these, we also
implement these parallel versions of the algorithms in practice.
Here, we done these in Parallel Virtual Machine environment,
where it is easy to change the amount of computational resources
so as to know the difference of the parallelized algorithm in
efficiency. After that, we can review the designing steps and
adjust it.
|