A New Formula Can Test the Efficiency of Parallel Algorithms without Supercomputers

D. Sc., Professor Leonid Sokolinsky has derived a formula to evaluate the effectiveness of parallel algorithms. For four years, the scientist worked at the Supercomputer Simulation Laboratory at South Ural State University. The research was published in the highly-rated Journal of Parallel and Distributed Computing (Q1).

Parallel algorithms for a supercomputer

Based on complex numerical algorithms programs are used in many areas of life. They track changes in stock prices of companies on the largest stock exchanges, solve complex logistic problems while building routes for goods delivery and storage, make an optimal schedule of air travel. Even a very productive computer cannot do such tasks, so supercomputers solve them. Parallel algorithms are created that can simultaneously use multiple processors. The more processor cores an algorithm uses efficiently, the more scalability it has.

― Modern science, economics, and industry require the solution of optimization problems of enormous computational complexity. For example, optimizing the operation of all traffic lights in the city to avoid traffic congestion and traffic jams as much as possible. To achieve this, a mathematician and a programmer need to write a complex algorithm and divide it into parallel parts to be executed on different processors. And this is not an easy task. The more processors in a supercomputer, the more difficult it is to come up with an algorithm that these thousands, tens of thousands, and millions of processors can effectively use. However, if the parallel algorithm is not well designed, it will prove ineffective even on a supercomputer ― Professor Sokolinsky says.

Well-scalable parallel algorithms are necessary for science. For example, in physics, to solve problems related to Bell's theorem.

Save time and money

A programmer needs to run a ready-made program on the computer to assess the new algorithm's scalability. But often, after so much effort, it turns out that the algorithm is ineffective. The scientist proposed a new parallel computing model, which allows you to test a new algorithm before programming. The approach reduces the time for software development and allows changing the algorithm before writing the program.

― My goal was to create a parallel computing model that would allow concluding whether it can effectively use the supercomputer or not at the earliest stage of the program development, without spending time and money. Using the formula I have proposed, one will be able to understand whether this or that algorithm will be effective when executed on a supercomputer. One needs only a pencil, a sheet of paper, and a calculator, the scientist says. ― There are some parallel computing models, but none offers a ready-made formula that would give an accurate estimate of the predicted algorithm scalability. In my model, for the first time in the world, such a formula has been derived. Moreover, its effectiveness is confirmed in practice in solving many problems.

In the future, based on the developed model, it is planned to create a "software framework", a template using which other mathematicians and programmers will be able to quickly make parallel programs for solving optimization problems of high computational complexity.

More information:
www.sciencedirect.com/science/ … 0743731520304251?via%3Dihub

Provided by South Ural State University