Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

16

Debugging DVM-program performance

User's guide

October 1999

Keldysh Institute of Applied Mathematics

Russia Academy of Sciences

Table of contents

1 Introduction 3

2 Characteristics of program execution 3

2.1 Main characteristics of program execution 3

2.2 Components of the main characteristics 5

2.3 Program execution characteristics on each processor 6

3 Methodology of performance debugging 6

3.1 Representation of program as a hierarchy of intervals 6

3.2 Recommendations on characteristics analysis 7

4 Start of execution with statistics 9

5 Start of performance analyzer 10

6 Representation of characteristics 10

7 Appendix. The list of characteristics 15

7.1 Main characteristics and their components 15

7.2 Characteristics of program execution on each processor 15

1Introduction

The performance of parallel program execution on multiprocessor computers with the distributed memory is determined by the following major factors:

• program parallelism - a part of parallel calculations in total volume of calculations;

• balance of processor load during parallel calculations;

• time of interprocessor communications;

• degree of overlapping of interprocessor communications and calculations.

Methods and tools of parallel program performance debugging essentially depend on the system which are used for parallel program.

An essential advantage of DVM-system is that at any moment it is known whether sequential or parallel part of the program is executed on any processor. Besides, all synchronization operations of the program are known. Therefore there is an opportunity to quantify the influence of four above factors on the program execution performance.

Special tools were developed for analysis and debugging of performance of DVM-program execution. They work as following. During a program execution on multiprocessor computer (or uniform computer network) the support system stores time characteristic information in processor memory and writes the data into a file upon the program completion. Then the file is processed on workstation using a special performance visualizer.

The performance visualizer allows the user to get time characteristics of the program execution in more or less detail.

2Characteristics of program execution

2.1Main characteristics of program execution

The opportunity to distinguish sequential and parallel parts of the program during its execution on the multiprocessor computer allows to predict a productive time required for the program execution on serial computer. So the main characteristic of parallel execution (efficiency coefficient) can be calculated: it is a ratio of the productive time to the total processor time. The total processor time is calculated as a product of execution time on the multiprocessor computer (execution time – maximum of program execution times on all processors used) by number of processors. The lost time is the total processor time of parallel execution subtracted by the productive time. If the programmer is not satisfied with the efficiency coefficient value he should analyze components of the lost time and their origin.

There are following components of the lost time:

• Losses because of insufficient parallelism that cause replication of execution on several processors (insufficient parallelism); the losses are possible in two cases: first, sequential parts of the program execute on all processors; second, some parallel loop iterations can be replicated on all or several processors according to user prescription.

• Losses because of execution of interprocessor communication (communication);

• Losses because of idle time of the processors on which the program execution has been completed earlier than on others (idle).

Time of interprocessor communications includes the time of data transfer from one processor to another and also includes a time lost because of message receive operation on one processor starting earlier than the corresponding send message operation on another one (dissynchronization losses).

Since the DVM user does not deal with low level operations as message passing the information should be represented in form convenient to him.

During DVM-program execution interprocessor message exchanges are generated by the following collective operations:

• global reduction (reduction operation with reduction variable local values, calculated on different processors);

• shadow edges renewing;

• loading remote access buffers;

• data redistribution;

• input/output operations (they are executed on one dedicated processor which receives data from and sends to others);

There are two modes of collective operation execution: synchronous and asynchronous. To execute a collective operation in asynchronous mode which provide a simultaneous execution of interprocessor communications and calculations, functions of start and waiting operation are served. If one of the operations listed above starts not simultaneously on different processors (in synchronous or asynchronous mode) then dissynchronization losses may occur. To estimate such losses the dissynchronization losses for each collective operation are calculated that is a time spent on synchronization by all processors as if any collective operation starts with processors synchronization. Overhead losses on synchronization message exchange are not taking into account.

A special characteristic –synchronization – is used to estimate total potential losses because non-simultaneous start of collective operations on different processors.

The user should pay attention to the main origin of dissynchronization losses – processor loading imbalance. The loading imbalance is caused by non-uniform distribution of parallel loop calculations between processors.

If processor synchronization (interprocessor communication) would be performed upon each entering and exiting of parallel loop then processor loading imbalance would inevitably lead to dissynchronization losses. However as such synchronization is performed not for all loops then imbalances on different program segments can be compensated and real losses can be insignificant or even absent. To estimate possible imbalance losses the user is given a generalized characteristic- imbalance. To minimize overhead losses for calculation of this characteristic it is assumed that processor synchronization is performed only once – upon exiting the program. So a total load of each processor is calculated first and then imbalance losses due to dissynchronization are predicted. However in real program processor synchronization is performed not only upon the exiting but more often, so the real losses will be higher. The real dissynchronization losses will be still higher than imbalance value in case when processor load is strongly varies from one execution of parallel loop to another execution of the same loop.

Dissynchronization can occur not only due to imbalance but also because of different moments of collective operation completion caused by characteristics of its realization on a parallel computer. To evaluate the potential dissynchronization the user is provided with a special characteristic – time variation of collective operation completion. As the imbalance time this characteristic is an integral one. It allows user to quite accurately estimate possible losses due to dissynchronization in case when different execution time of collective operations are not random but are determined by network topology or processor specialization ( input/ output processor, processor for reduction operations etc.).

An important characteristic showing potential reducing of communications by overlapping interprocessor exchanges and computations is time of overlapping.

The main characteristics of effectiveness are integral characteristics allowing user to estimate parallelization degree and potential of its increase. However to estimate the effectiveness of complex programs the integral characteristics can be not sufficient. In this case more detail information on execution of the whole program and it parts can be provided for user.

2.2Components of the main characteristics

Some of the above main characteristics consist of several components and its values can be given to user.

Productive time consists of productive processor time, system processor time and input/output operation tine (not taking into account message exchange).

Insufficient parallelism loses consist of two components giving a possibility to distinguish losses in user program and corresponding system overheads.

Communication time includes time of dissynchronization loses and time used for start asynchronous collective operations, this time should be too small as compared with communication time, if communication libraries (MPI,PVM) work correctly .

To refine the communication time it is decomposed into following components:

1. time of reduction operation

2. time of renewing shadow edges;

3. time of loading remote access buffers;

4. time of data redistribution;

5. time of message exchange during input/output operations.

Real and potential dissynchronization losses and the losses due to variation in time of collective operation completion are decomposed in the same manner.

The time of exchanges and computations overlap is calculated for all asynchronous collective operations.

2.3Program execution characteristics on each processor

The calculation of the main integral characteristics and its components are based on program execution characteristics on each processor. These characteristics can be useful for more detail analysis of parallel program execution effectiveness. Besides the values of these characteristics its average, maximal and minimal values and the corresponding processor are given.

3Methodology of performance debugging

For effectiveness analysis of complex parallel program execution it is not sufficient to have characteristics of the whole program execution but detail characteristics of chosen program parts are needed. The execution of DVM-program can be represented as a hierarchy of intervals and the tools to do that and recommendations on characteristic analysis are described below.

3.1Representation of program as a hierarchy of intervals

Program execution is considered as an interval of the highest level (zero level). This interval can include several intervals on the next (first) level. Such intervals can be parallel loops, sequential loops as well as any sequence of operations marked by user for which the execution starts from the first operator and completes with the last operator. The intervals of the first level can in turn include intervals of the second level etc.

All above characteristics are computed not only for the whole program but for each its interval. Multiple interval execution can be considered as unrolled sequence of interval operators on the same processors as during real execution of the parallel program. In fact the characteristics of the interval executed several times are added up after each execution. The intervals included into the interval of higher level are identified by the source file name and a line number in it corresponding to the beginning of the interval and may be user defined integer number.

User controls program splitting into intervals during compilation. There are the following options:

• -e1 – the intervals are all parallel loops and sequential loops embedding them;

• -e2 – the intervals are all parallel loops and marked sequences of operators;

• -e3 – concatenation of the first two options ( e1 and e2);

• -e4 – the intervals are all parallel and sequential loops and marked sequences of operators.

To mark sequence of operators as an interval two special C-DVM or FORTRAN-DVM instructions are used:

In C-DVM the interval is defined as follows:

DVM(INTERVAL[integer expression ])<operator>,

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов учебной работы