Veri cation of BSF Parallel Computational Model

Abstract

The article is devoted to the veri cation of the BSF parallel computing model. The BSF-model is an evolution of the \master-slave" model and SPMD-model. The BSF-model is oriented to iterative algorithms that are implemented in cluster computing systems. The article brie y describes the basics of the BSF-model and its cost metrics. The structure of the BSF program is shown in the form of a UML activity diagram. The simulator of BSF-programs, implemented in C++ language using the MPI-library, is described. The results of computational experiments con rming the adequacy of the cost metrics of the BSF-model are presented.

Keywords

• parallel computational model
• BSF
• Bulk Synchronous
• Farm
• scalability
• parallel e
• ciency
• distributed memory multiproces- sors
• simulation
• validation

Introduction

The Sunway TaihuLight is the fastest supercomputer in the world according to the TOP500 List (edition of June 2017) [ 1 ]. It uses 40,960 processors, each of which contains 260 processing cores. The total system memory is 1.3 Petabytes; the peak performance exceeds 120 peta ops. Analysis of the growth dynamics of the performance of supercomputers (see Fig. 1) shows that in 8-9 years the most powerful supercomputer becomes an ordinary system, and that in 56 years we can expect the appearance of exascale computing. The emergence of such powerful multiprocessor computing systems brings to the fore issues related to the development of frameworks (templates) that allow creating highly scalable parallel programs oriented to systems with distributed memory. In this context, the most important problem is the development of parallel computation models allowing to estimate the scalability of the algorithm at an early stage of implementing. In paper [ 2 ], a new parallel computation model called BSF (Bulk-Synchronous Farm) was proposed. The BSF-model is an evolution of the \master-slave" model and focused on iterative algorithms executing on the cluster computing systems. In this paper, the issue concerning to a veri cation of the BSF model is discussed. The paper has the following structure. Section 2 is the description of the BSF-model. In Section 3, a cost metric of BSF-model is given. In Section 4, the simulator of BSF-programs is described and computational experiments con rming the adequacy of the cost metrics of the BSF-model are presented. In Section 5, the results are summarized and directions for further research are outlined. Parallel computation model BSF (Bulk Synchronous Farm) was proposed in [ 2 ]. It extends the \Master-slave" paradigm [3{5] and the BSP computational model [ 6 ]. The BSF-model is oriented on multiprocessor systems. BSF-computer is a set of homogeneous processor nodes with private memory connected by the network that provides data transfer from one node to another. Among the processor nodes, there is one called a master node. The remaining K nodes are called slaves. BSF-computer must have at least one master node and one slave node (K 1). The architecture of the BSF-computer is shown in Fig. 2.

Network M . . .

WK

BSF-computer works according to the SPMD programming model [ 4, 7 ]. BSF-program consists of a sequence of macro-steps and global barrier synchronizations. Each macro-step is divided into sections of two types: master sections and slave sections. The order of such sections within the macro-step is not signi cant. The data processed by the particular slave is determined by the number of its node. BSF-program includes the following sequential sections (see Fig. 3):

Iterative process

Master Sections Slave Sections

Master Slave

Initialization Initialization

Barrier Synchronization

Begin of Iterative Process

Sending Receiving

Orders Order

Processing

Sending

Result

Receiving

Results

Output

Finalizing

Master

Barrier synchronization

Evaluating

Results

End of Iterative Process

Finalizing Slave

Initialization is a macro-step, during which the master and slaves read or generate input data. The initialization is completed by a barrier synchronization. The iterative process repeatedly performs its body until the exit condition checked by the master becomes true. In the nalization macro-step, the master outputs the results and ends the program. Body of the iterative process includes the following macro-steps: 1. sending the order (from master to slaves); 2. processing the order (slaves); 3. receiving the results (from slaves to master); 4. evaluating the results (master).

In the rst macro-step, the master sends the same orders to all the slaves. Then, the slaves execute the received orders (the master is idle at that time). All the slaves execute the same program code but act on the di erent data with the base address depending on the slave-node number.

It means that all slaves spend the same time for calculating. During processing the order, there are no data transfers between nodes. The last is an important property of the BSF-model. In the third macro-step, all slaves send the results to the master. After that, global barrier synchronization is performed. During the last macro-step of iterative process, the master evaluates received results. The slaves are idle at that time. After result evaluations, the master checks the exit condition. If the exit condition is true then iterative process is nished, otherwise the iterative process is continued. The outline of the BSF-program in form of UML activity diagram is shown in Fig. 4.

The BSF-model was designed for the scalable iterative numerical methods that have a high computational complexity of iteration with relatively low cost of communications. A scalable iterative method is a method that allows iteration to be splitted into subtasks that do not require data exchanges. An example of such a method can be found in [ 8 ]. 3

Cost Metric of BSF-Model

The BSF-model provides an analytical estimation of the scalability of a BSFprogram. The main parameters of the model are [ 2 ]: K: the number of slave-nodes; L: an upper bound on the latency, or delay, incurred in communicating a message containing one byte from its source node to its target node; ts: time that the master-node is engaged in sending one order to one slave-node excluding the latency; BSF program

Master

Start Reading Input data Sending Orders tv: time that a slave-node is engaged in execution an order within one iteration (BSF-model assumes that this time is the same for all the slave-nodes and it is a constant within the iterative process; tr: total time that the master-node is engaged in receiving the results from all the slave-nodes excluding the latency; tp: total time that the master-node is engaged in evaluating the results received from all the slave-nodes.

Let s denote tw = K tv - summarized time which is spent by slave-nodes for order executions (without taking into account the e ect of parallelization). Then, the upper bound of a BSF-program scalability can be estimated by the following inequality [ 2 ]:

The speedup of BSF-program can be calculated by the following equation [ 2 ]: K r

tw 2L + ts a =

K(2L + ts + tr + tp + tw) K2(2L + ts) + K(tr + tp) + tw : (1) (2) (3)

One more important property of a parallel program is the parallel e ciency. The parallel e ciency of a BSF-program can be calculated by the following approximate equation [ 2 ]: e

1 1 + (K2(2L + ts) + K(tr + tp))=tw : 4

Veri cation of BSF-Model

To verify the cost metrics of the BSF-model, a simulator of BSF-programs was designed and implemented in C++ with MPI-library. The source code of the simulator is freely available on Github, at https://github.com/nadezhdaezhova/BSF-simulator. The simulator uses SPMD-model and includes both the master and slave sections. The master section is performed if MPI_Comm_rank returns 0. The slave section is performed if MPI_Comm_rank returns a value greater than 0. The order is an arbitrary string of speci ed length transferring from the master to slave by the MPI_Isend command. The slave reads the order by the MPI_Irecv command. The order processing is simulated by calling the usleep(tv) function which causes the slave MPI-process to be suspended from execution until the speci ed number of real-time microseconds has elapsed. After processing, the master and all the slaves perform global barrier synchronization by using MPI_Barrier command. As a result, the slave sends to the master an arbitrary string of speci ed length using MPI_Send command. The master reads the results of all the slaves by MPI_Recv command. The synchronization is performed by MPI_Waitall command. Then, the master simulates evaluation of the results by calling the usleep(tp) function which causes the master MPIprocess to be suspended from execution until the speci ed number of real-time microseconds has elapsed.

To verify the equation (2) determining the speedup, the parameter v = lg (tw=ts ) connecting the values of tw and ts was introduced. The following values of the parameter were studied: 4, 4.5 and 6. The speedup curves plotted using the equation (2), were compared with the curves obtained as a result of numerical simulations performed via the BSF-simulator. Parameters of the experiments are given in Table (1).

Parameter tr tp tw L

Semantics time that the master-node is engaged in sending one order to one slave-node

excluding the latency total time that the master-node is engaged in evaluating the results received from all the slave-nodes total time that slave-nodes are engaged in execution of an orders an upper bound on the latency, or delay, incurred in communicating a message containing one byte from its source node to its target node

The latency value L was obtained experimentally as the transfer time of the message in 1 byte using the functions MPI_Send and MPI_Recv. The value of tr corresponds to sending a message with a length of 14 MB. The values of the parameter ts depends on v and tw. This dependence is determined by the equation ts = 10 vtw. The corresponding values of the parameter were obtained by varying the length of the order (see Table (2)).

All the numerical experiments were conducted on the supercomputer \Tornado SUSU" [ 9 ]. The veri cation results of equation (2), shown in Fig. 5, show that the cost metrics of the BSF-model quite well predict the results produced by the BSF-simulator. In this case, the accuracy of the analytical estimates of the speedup increases with increasing of the parameter v value.

To verify the equation (3) determining the parallel e ciency, the parameter q = tp + tr connecting the values of tp and tr was introduced. The following parameter q values were studied: 0.02, 2 and 20. The parameter tr value was a constant equal to 0.01, and the parameter tp took values 0.01, 1.99 and 19.99. The parameter ts was also a constant equal to 0.005. This corresponds to a value of v equal to 5. The veri cation results of equation (3), shown in Fig. 6, show that the cost metrics of the BSF-model quite well predict the results produced by the BSF-simulator. At the same time, the accuracy of analytical estimates of parallel e ciency increases with increasing parameter q value.

80 70 60 50 p u ed40 e p S 30 20 10 0 50 In the paper, the issue of the adequacy of the BSF parallel computing model was studied. To verify the model, a simulator of BSF-programs in C++ language was developed using the MPI library. The emulator is implemented on the basis of the \master-slave" model. As orders, the master sends slaves messages of a certain length with arbitrary symbols. As a result, slaves are send to the master message of a certain length with arbitrary symbols. Calculations are simulated using the usleep() function. Via the simulator, computational experiments were carried out for various parameters of the BSF-model. The experimental and analytical 0.2 0

100 150 200 Number of processor nodes 250

300 1. design a skeleton for the rapid creation of BSF-applications and implement this framework in C++ using the MPI library; 2. construct a (construct) dialog editor for fast creation of BSF-applications based on BSF-skeleton; 3. implement some numerical methods using BSF-skeleton.

References

1. TOP500 Supercomputer Sites . https://www.top500.org/

2. Sokolinsky L .B.: Analytical study of the \master-worker" framework scalability on multiprocessors with distributed memory . arXiv:1704 .05816 [cs.DC]. 2017 . P. 15 . http://arxiv.org/abs/1704.05816

3. Sahni S.: Vairaktarakis G. The master-slave paradigm in parallel computer and industrial settings . J. Glob. Optim . 1996 . Vol. 9 , 3 {4. P. 357 { 377 .

4. Silva L.M. , Buyya R. : Parallel programming models and paradigms . High Performance Cluster Computing: Architectures and Systems . Vol. 2 . 1999 . P. 4 { 27 .

5. Leung J.Y.-T. , Zhao H. : Scheduling problems in master-slave model . Ann. Oper. Res . 2008 . Vol. 159 , 1. P. 215 { 231 .

6. Valiant L.G. : A bridging model for parallel computation . Commun. ACM . 1990 . Vol. 33 , 8. P. 103 { 111 .

7. Darema F . et al.: A single-program-multiple-data computational model for EPEX/FORTRAN . Parallel Comput. 1988 . Vol. 7 , 1. P. 11 { 24 .

8. Sokolinskaya I. , Sokolinsky L.B.: On the Solution of Linear Programming Problems in the Age of Big Data . Parallel Computational Technologies - 11th International Conference, PCT 2017 , Kazan, Russia, April 3- 7 , 2017 , Proceedings (to be published in Communications in Computer and Information Science , vol. 753 ). arXiv:1706.10030 [cs.DS] . 2017 . P. 15 .

9. Kostenetskiy P.S. , Safonov A.Y. : SUSU Supercomputer Resources . Proceedings of the 10th Annual International Scienti c Conference on Parallel Computing Technologies (PCT 2016 ). CEUR Workshop Proceedings . Vol. 1576 . 2016 . P. 561 { 573 .