Scheglov Maxim

Abstract

1. Introduction
2. Actuality of the subject
3. Purpose and tasks of development and research
4. Subject of development and research
5. Practical value of the received results
6. Parallel multistage block methods of the numerical decision of the Koshi problem for the ODE
• Thee Description of parallel multistage block methods of the numerical decision of a problem of Koshi for the ODE
• The Estimation of efficiency of parallel multistage block methods of the numerical decision of a problem of Koshi for the ODE
7. Conclusions
8. References

The Analysis and Estimation of Efficiency of Block Multistep Parallel Difference Methods of Solution the ODE on a Cluster

Introduction

            One of the most important directions of the development of computing technologies is parallel calculations. Last years the productivity of existing parallel computing systems has essentially grown. The technological base and architecture has considerably changed. But the main obstacle to introduction of almost all parallel architecture is absence of parallel algorithms. It is necessary to search for absolutely new methods for the decision of various problems which are focused on an effective using in multiprocessing systems, or to modernise existing algorithms.
            In turn by means of the differential equations and systems of the differential equations it is possible to describe a considerable quantity physical, mechanical, biological, economic etc phenomena. The received models, as a rule, represent the differential equations which decision on uniprocessor computers for comprehensible time is impossible. It has led to creation of parallel methods of the solution the Koshi problem.

Actuality of the subject

            Using the differential equations and systems of the differential equations it is possible to describe a considerable quantity physical, mechanical, biological, economic etc phenomena. The received models represent the differential equations which decision on uniprocessor computers for comprehensible time is impossible. From this it follows that working out of parallel methods of the decision of a problem of Koshi is an actual problem.

Purpose and tasks of development and research

            The purpose of work is analysis of the decision of the Koshi problem, using multistage parallel block method on computing cluster, realisation of the program system, allowing to receive the decision of the given problem.
            The main tasks of researches is studying of multistage parallel block methods of the decision of the Koshi problem, solving the Koshi problem on the computing cluster with Microsoft Visual Studio 2005 and technologies Message Passing Interface (MPI).

Subject of development and research

            The Subject of researches are parallel block methods of the decision of the Koshi problem on the Microsoft Windows Compute Cluster Server 2003.

Practical value of the received results

            The Received results will give the chance to estimate efficiency of parallel block methods of the decision of the Koshi problem on the computing cluster. The developed program system can be used for the decision of the Koshi problem with multistage parallel block method.

Parallel multistage block methods of the numerical decision of the Koshi problem for the ODE

            In the given chapter bases parallel multistage algorithms of the decision of the Koshi problem for the ODE are considered. We will deduce formulas and we will find the approached decision of the Koshi problem for the differential equation of the first order:
which satisfies to the entry condition
            We will break set of the M points of a uniform grid t _m , m =1,2, …, M and t _M = T with step τ on N blocks containing k points,s kN ≥ M. Let:

• i =0,1, …, k   - number of a point for each block;
• t _{n , i} - a point n th block with number i ;
• a point t _{n , 0}   - the block beginning n , and t _{n , k} – the block end;
• t _{n , k} = t _{n +1,0} . ;
• the index point does not join in the block.

            At the numerical decision of a problem of Koshi for each subsequent block new k values of function are calculated simultaneously. This feature of methods will be co-ordinated with architecture of parallel computing systems, and also allows to calculate factors of formulas not in the course of integration, and at a method development cycle that considerably increases efficiency of the account[3,5].

The Description of parallel multistage block methods of the numerical decision of the Koshi problem for the ODE

            In case of a multistage block method the initial block will contain grid points in which initial values of the approached decision are necessary for continuation of calculations.
            the Scheme of splitting into blocks for a m-step-by-step k-dot method is presented on picture 1.1.



            Generally multistage difference methods for the block from k points at use of the calculated values of the approached decision in m knots previous the block, taking into account entered above about designations it is possible to write down the equation of multistage methods in a kind:

            For calculation of the approached values of the decision of the Koshi problem with multistage difference block method it is necessary to solve nonlinear system of the equations (1.3). It is possible to use the following iterative process for this purpose:

            We will fix each processor element to a point of n th block which is calculated. Then each of k processors will calculate at first values of an initial vector on Adams-Bashforta method. Further each processor will find corresponding a vector with values of the right parts f _{n, j} =f (t _n +j τ, u _{n, j} )) .
            On each step of calculations the exchange of the found values for a current step of calculations between processors is made. For realisation of calculations on knot presence of the following data is necessary:

• a vector of the initial approached values of function U _{i, j} ;
• a vector of values the ODE for net functions in knots of previous block F _{i, j} ;
• a vector of values of elements ψ i, j which is i th column of a matrix Ψ;
• a vector of values of elements φ i, j which is i th column of a matrix Φ;
• a vector of values of elements F i, j which is i th line of matrix F.

The Estimation of efficiency of parallel multistage block methods of the numerical decision of a problem of Koshi for the ODE

            As criteria of an estimation of parallel algorithms two sizes, as a rule, act:

• acceleration S _p
• efficiency E _p

            Time of performance of consecutive algorithm in all k knots:

            Time of parallel calculation of the approached values of the decision for a ruler from processors:

            It is necessary to notice that parallelism dynamic characteristics influence latency and time of transfer of one word. The received dependence factor efficiency from латентности is обратнопропорциональной (at size reduction латентности increases эффективнность algorithm of the decision of a problem) and is resulted on picture 1.2.
            Dependence of factors of acceleration and efficiency on time of calculation of right member of equation Tf and numbers of points of the block k are resulted in drawings 1.3, 1.4.

It is possible to consider acceleration of k-dot multistage parallel algorithm approximately equal

            and efficiency will be equal

            Thus parallelism characteristics in systems with ring structure appear worse, than in systems with topology a hypercube and tor that data exchange time between processors in parallel computing systems testifies about strong influence. Between time of calculation of the right part and efficiency there is a direct dependence: at increase in labour input of calculations of the right parts, efficiency of the considered methods increases. Also it is necessary to notice that because the number of points of the block is connected with number of used processors, at increase in number of points in the block возростает the factor of acceleration S and decreases effectiveness ratio E [4].

Conclusions

            In the given section multistage block methods of the decision of the Koshi problem for the ordinary differential equations have been considered, estimations of efficiency of the given methods are resulted.
            Further the program system will be developed for the decision of the Koshi problem by a multistage parallel block method. Use of developed program system will allow to estimate indicators of efficiency and accuracy of the parallel decision of the Koshi problem with an investigated method.

References

1. Гергель В.П., Стронгин Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем. - Н.Новгород, ННГУ, 2001

http://window.edu.ru/window_catalog/pdf2txt?p_id=6579

2. Хайрер Э., Нёрсетт С., Ваннер Г. Решение обыкновенных дифференциальных уравнений. Нежесткие задачи: Пер. с англ. – М.: Мир, 1990. – 512с.
3. Фельдман Л.П. Сходимость и оценка погрешности параллельных одношаговых блочных методов моделирования динамических систем с сосредоточенными параметрами // Научные труды ДонНТУ. Серия: Информатика, моделирование и вычислительные методы, (ИКВТ-2000), выпуск 15: Донецк: ДонНТУ, 2000, с. 34-39.

   scg.donntu.ru/2005/scg_2005.pdf

4. Дмитриева О.А. Модели отображения многошаговых алгоритмов на параллельные вычислительные системы с топологией гиперкуб//Науковi працi Донецького державного технiчного унiверситету. Серiя: Проблеми моделювання та автоматизації проектування динамічних систем, випуск 46: – Донецк:, 2002. с. 154-161.
5. Фельдман Л.П., Дмитриева О.А. Разработка и обоснование параллельных блочных методов решения обыкновенных дифференциальных уравнений на SIMD-структурах. //Научн. тр. Донецкого государственного технического университета. Серия: Проблемы моделирования и автоматизации проектирования динамических систем, выпуск 29. – Севастополь: «Вебер», 2001. – с. 70-79.
6. Kazufumi OZAWA, Susumu YAMADA “Parallel block methods for solving nonstiff equations with stepsize control“,Graduate school of information science, Tohoku University, 2006

http://repository.kulib.kyoto-u.ac.jp/dspace/bitstream/2433/60205/1/0944-2.pdf

7. Воеводин В.В.,"Вычислительная математика и структура алгоритмов.".-М.: Изд-во МГУ, 2006.-112 с.

http://www.parallel.ru/info/parallel/voevodin/

8. van der Houwen P.J.,“Parallel Step-by-Step Methods”, CWI Amsterdam, 1991

http://ftp.cwi.nl/CWIreports/1991/NM-R9116.pdf

9. Самарский А.А., Гулин А.В. Численные методы.- М.: Гл. ред. физ.-мат. лит., 1989.– 432 с.
10. Воеводин В.В. Математические основы параллельных вычислений. - М.: Изд-во МГУ, 1991. - 345 с.