Abstract: «The investigation of efficiency of parallel single-step methods of the decision of problem Koshi for the ODE»

Introduction

The idea of paralleling of calculations is based on the fact that the many tasks could be divided on some smaller tasks that could be decided simultaneously. The parallel computing have been used for many years basically in high-performance computing, but in these latter days they became more popular owing to physical restraint for growth of processor speed.

The appearance of lump of rather cheap cluster parallel computing in the last few years was resulted the mushroom growth of parallel computing technologies including the spheres of high-performance computing. Recently the situation in the area of parallel computing technologies started to cardinally change due to the fact that the majority of key producers of microprocessors begin to transfer to multinuclear Scalable Processor Architecture (SPA). The modification of the apparatus base leads to change also the approaches to the parallel algorithms construction. For the realization of the processing power of the multinuclear SPA the development of new parallel algorithms is required that would consider the new technologies. The efficiency of the computer power application that new generation clusters would possess will depend directly on the quality of the software applications, as well as on special numerical algorithms libraries oriented on multinuclear SPA.

The actuality of the graduation work: Continual researches in the sphere of development and creation of high-power computing facilities provide a means of solving of fundamental and application tasks. The productivity of modern computer is inadequate to secure the required decision of many tasks. One of the most effective methods of productivity growth is paralleling of calculations in multiprocessor and parallel-banded structures. In consequence of which the application of parallel computing systems is the rather important trend of computer engineering development. Modelling of the real economic, engineering and other processes described by systems of the ordinary differential equations (SODA) of the big dimension, represents an extensive class of problems for which solution application of high-efficiency computer facilities not only is justified, but also it is necessary.

In these latter days, a great number of numerical methods of differential equations integrating appeared that are oriented on computing systems with parallel architecture. Still the common use of majority of such methods is not always reasonable, because many of them have numerically variability or have a high complex structure that leads to effectiveness loss. To the methods lack of such shortages the block methods could be referred. The block method is a method where for the block from k points the new k values of function are calculated simultaneously. It’s a specific feature of the method, firstly it’s coordinated with the architecture of the parallel computing systems, secondly it’ll allow calculating the coefficients of difference formula not in the process of integration but on the stage of method development, that increase greatly the counting efficiency. Nevertheless, in spite of all the advantages these methods are examined rather few. The information mainly is protected and inaccessible without registration or payment.

Purpose and tasks: The researches, comparison, improvement and determination of optimal parallel single-stage solution Cauchy algorithms for single-stage differential equations for definite type of computing circuit. It should be noticed that the method has to possess numerical stability, has optimal structure for effectiveness keeping structure, decision time and time for modeling accordingly. To make conclusion about the practicability and profitability of the realization of parallel method, it is essential to know its speeding-up and parallelism ratio.

Consecutive method

In general, methods Runge-Kutta record in the form

Here:

– consts.

The number p, indicating the number of subsidiary points kj, used for calculating the main point of ki, called the method order.

Parallel one-step methods

Let's consider a Cauchy problem solution

by a k-pointwise block difference method. Set M of points of a uniform grid {t_m}, m = 1,М and t_m=T with step , divide on N the blocks containing on k of points, N<=M.

In each block we work in point number i=0.
t_n,i – a point of n block with number i.
t_n,0 – starting n-block point.
t_n,k – the end of the block.

If for calculating values in the new block is used only last point of preceding block – the block method is considered one-step, and if all points of the previous block – multistep.

Evaluating the effectiveness

To draw a conclusion on appropriateness of realisation and the advantage received at application of a parallel method it is necessary to know its acceleration and parallelism factor.[10]

Introduce the symbols:

t_f – time to calculate value of function f(t,x);
t_сл – time to perform addition operation;
t_ум – time to perform multiplication operation;
t_об – time of transmission one number to the next processor.

Evaluation time for one processor with accuracy O(t^k+1) in all k nodes of block by Runge-Kutta formulas k+1 an accuracy order is equal
T₁=k(k+1)t_f+k²(t_сл+t_ум)

Time of a parallel evaluation on k processors of the approached values of a solution in all k nodes of block equals
T_k=(k+1)t_f+k²(t_сл+t_ум)+k(k+1)t_об.

Then acceleration of parallel one-step k-point algorithm equals
W(k)=T₁/_k=(k+1)²/k=k.

The effectiveness ratio of parallel algorithm is calculated by the formula
E(k)=W(k)/N_проц

Here N_проц – an amount of used processor elements. In our case
N_проц=k Therefore E(k) roughly equal 1.

Conclusions

The common use of majority of such methods is not always reasonable, because many of them have numerically variability or have a high complex structure that leads to effectiveness loss. To the methods lack of such shortages the block methods could be referred. The k-block method is a method where for the block from k points the new k values of function are calculated simultaneously. It’s a specific feature of the method, firstly it’s coordinated with the architecture of the parallel computing systems, secondly it’ll allow calculating the coefficients of difference formula not in the process of integration but on the stage of method development, that increase greatly the counting efficiency. In my next work I am planning to solve the ordinary differential systems by block methods.

Remark

When writing this paper master's work is not yet complete. Final completion: December 2009. Full text and materials on the topic can be obtained from the author or the head after that date.

Литература

1. Воеводин В.В. Математические основы параллельных вычислений. – М.: МГУ, 1991. – 345 с.
2. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ – Петербург, 2002. – 540 c.
3. Информационно-аналитический центр по параллельным вычислениям www.parallel.ru
4. Хокни Р., Джессхоуп К. Параллельные ЭВМ: Архитектура, программирование и алгоритмы. – М.: Радио и связь, 1986. – 392 с.
5. Гергель В.П., Стронгин, Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем. Учебное пособие – Нижний Новгород: Изд-во ННГУ им. Н.И. Лобачевского, 2003. – 184 с.
6. Фельдман Л.П. Сходимость и оценка погрешности параллельных одношаговых блочных методов моделирования динамических систем с сосредоточенными параметрами //Науковi працi Донецького державного технiчного унiверситету. Серiя: Проблеми моделювання та автоматизації проектування динамичних систем, випуск 15: – Донецк: ДонГТУ, 2000. – с. 12 – 16.
7. Фельдман Л.П., Святный В.А. Параллельные алгоритмы моделирования динамических систем, описываемых обыкновенными дифференциальными уравнениями. // Научн. тр. ДонГТУ, вып. 6.– Донецк: ДонГТУ, 1999. – 330 с.
8. Ортега Дж., Пул У. Введение в численные методы решения дифференциальных уравнений: пер. с англ.; под ред. Абрамова А.А. – М.: Наука. Гл. ред. физ.-мат. лит., 1986. – 288 с.
9. Хайрер Э., Нёрсетт С., Ваннер Г. Решение обыкновенных дифференциальных уравнений. Нежесткие задачи: пер. с англ. – М.: Мир, 1990. – 512 с.
10. Фельдман Л.П., Дмитриева О.А. Эффективные методы распараллеливания численного решения задачи Коши для обыкновенных дифференциальных уравнений // Математическое моделирование. – М.: 2001. – Т.13, № 7. – с. 66-72.
11. Самарский А.А., Гулин А.В. Численные методы. – М.: Наука. Гл. ред. физ.-мат. лит., 1989. – 432 с.