The Parallel Algorithm

  The mechanical example is presented in section 2 is very simple and the number of dimension is small (n=2). A complex problem involves bigger phase space and the number of dimension grows rapidly with the complexity of the problem. The CPU and memory requirements of the algorithm grow exponentially with the number of dimensions. In order to solve the equation system with prescribed precision we have to choose sufficiently small grid-size ( ), so the number of cubes can be very large if the precision requirements are tight. Supposing that the number of points on each coordinate axis is N and the number of dimensions is n, the numbers of points where we have to evaluate each function will be . This exponential expression can yield huge numbers, justifying the parallelization of the algorithm. To design the parallel algorithm we have examined the simplex algorithm. The main statements are:

a.

Every simplex is independent from the results of the calculations in the other simplices.

b.

Since adjacent simplices have common vertices, the function values should not be re-computed for each simplex.

c.

We assume that the computation time for the the functions is not negligible and could be different at different points.

d.

We only expect solution points in a few simplices and most of the simplices do not contain any solution points. (In the limit where the size of the simplices goes to zero we expect solution points "almost nowhere", on a subset of measure zero.)

Considering the first statement, i.e. that the computation in every simplex is independent suggests that the simplex could be the element of the parallelization, however the computation steps could be also parallelized in a simplex e.g. by solving the linearized functions and the n different equations of the simplex facets in parallel method. The main disadvantage of the parallelization inside the simplex is that the cost of the communication between two processes in PVM is very high. With respect to statements 'c', and 'd', the load-balancing is also important thing in our case, however, the capacity of the computers of the virtual machine may also also different.

The implemented parallel program is based on a master-slave structure, where the master program distributes the phase space to smaller pieces (domains) and the slaves figure out the equation system in these domains. The major functions of the master program:

• reading the configuration files
• starting and stopping the slaves
• collecting the results from slaves
• load-balancing

Files are handled only by the master program thus the slaves never compete for accessing files in the NFS server. The slave program essentially contains the serial version of the described Simplex Algorithm and solves the equations in the domain given by the master. The values of the functions are computed once by the slave, when the slave gets a new domain from the master program. In this manner the function values are multiply computed only on the boundary points between the domains. To minimize the number of boundary points the master program tries to create domains with approximately equal orthogonal sizes.

The load-balancing is provided by the master, because the phase space is divided into more domains than the number of processors. When the computation in any domain has been finished, the master sends the next domain to the next free slave. In this way the faster processors will get more jobs then the slower processors.