Enhanced π Approximation Through MIMD Parallel Computing: An Efficiency Analysis Utilizing Raspberry Pi

Parallel computing, a process that enables the simultaneous execution of computations across multiple computers, has been widely recognized as an effective method for processing large tasks [1]. These tasks are subdivided into smaller components, each comprising a series of instructions executed concurrently across various processors [2]. Flynn’s taxonomy, proposed by Michael J. Flynn in the 1970s, offers a simplified and categorized framework for understanding parallel computing [3]. The taxonomy delineates four categories based on the behavior of systems in instruction and data flow: Single Instruction Single Data (SISD), Multiple Instruction Single Data (MISD), Single Instruction Multiple Data (SIMD), and Multiple Instruction Multiple Data (MIMD) [4].

SISD corresponds to the conventional von Neumann architecture where a singular data stream is processed by a single sequential processing unit [5]. In contrast, MISD involves the execution of multiple instructions on a single data stream [6]. SIMD allows for multiple threads to execute the same operation across multiple data elements, and can be implemented at various levels, including core, thread, and instruction [7]. MIMD, on the other hand, maps multiple instructions to multiple data points, with each processing core handling its unique set of instructions and data points [8]. This category is often employed in the creation of parallel architectures, including parallel machines such as workstation clusters and computer clusters [3]. Cluster computers, which enhance processing capability through the simultaneous operation of multiple computing units, exemplify this approach [9].

The mathematical constant π, defined as the ratio of a circle's circumference to its diameter, has long captivated mathematicians [10]. Physical measurements of a circle's circumference and diameter to determine the value of π are prone to errors and hence, not considered the most precise method [11]. Mathematicians James Gregory and Gottfried Wilhelm Leibniz proposed several formulas to approximate the value of π [12]. While neither used exhaustion as π was not the value being calculated, their shared series for π/4 can be utilized to determine π's value through the inverse tangent function, specifically arctan(1). The relevance of π extends beyond geometry into engineering, as noted by several authors [13].

The application of computational tools for π estimation based on fundamental mathematical principles has emerged as a compelling topic within the domain of applied scientific computing [14]. The requirement for processing vast volumes of data necessitates innovative computational methods aimed at accelerating the process [15]. Parallel computing offers one such technique, promising enhanced computational capacity [16]. However, the construction of cost-effective parallel computing architectures from personal computers presents challenges due to their high costs and substantial space requirements.

Multi-node communication in large-scale parallel computing applications is typically facilitated through the Message-Passing Interface (MPI) [17]. The MPI standard, established by the MPI Forum, provides a foundation for message-passing libraries [16]. Since its introduction in 1994 as a method for code parallelization, MPI has remained a cornerstone of parallel code execution on high-performance computing platforms [18]. MPICH, an implementation of MPI, serves as the basis for the majority of MPI implementations [19]. Mpi4py, a Python binding for MPI, complies with the MPI standard [19]. In this study, the MPI implementation will rely on MPICH and mpi4py.

The Raspberry Pi, a highly popular single-board computer (SBC) developed by the Raspberry Pi Foundation at the University of Cambridge, UK, was first introduced in February 2012 [20]. The Raspberry Pi employs a system on a chip (SoC) from Broadcom BCM2387, eschewing a hard disk in favor of an SD card for boot processes and long-term data storage [21]. The relatively low cost and small dimensions of the Raspberry Pi 3B suggest that constructing a cluster of Pis could be more cost-effective and space-efficient than using conventional computers [9, 22, 23].

By addressing these issues, this study seeks to explore the potential of MIMD parallel computing on a Raspberry Pi for the concurrent approximation of π. The ultimate objective of this research is to utilize MIMD parallel computing on a Raspberry Pi for the parallel approximation of π.

This step refers to the outcome of each step that came before it and was performed successfully. The test results will include details on the execution of sequential and parallel programs, the time required for each program to complete, and performance improvement metrics like speedup and efficiency. These are the outcomes of the research’s conclusions.

3.1 Analysis

Insofar as necessary, the study will touch on current events. Tables 2 and 3 show that the needs analysis stage calls for supporting tools in order to do research on the subjects that will be covered.

Table 2. Hardware

Table 3. Software

3.2 Design

The design phase entails setting up a study setting that will support the goals and duties of the analysis phase while facilitating data collecting. In the design draft, the network topology and the MIMD parallel computing system are both described in general terms. An overview of the physical topology, high-level design, and low-level design are intended to be given at this design stage. The list appears below:

3.2.1 Network topology design

The routers, laptop clients, servers, and access points used in this study are depicted below.

The admin laptop has a dynamic IP address, whereas the Raspberry Pi that is linked has a static one. The access point router and the attached device communicate using a class C IP address.

2.png

Figure 2. Network topology design

Based on Figure 2, it is shown that the physical topology describes the design of the computer network structure within the scope of this research. Mikrotik RB951 series used with switch mode and access point as admin laptop access to the Raspberry Pi. Raspberry Pi node master is connected to the Mikrotik on port eth2. Raspberry Pi node slave1 is connected to the Mikrotik on port eth3. Raspberry Pi node slave2 is connected to the Mikrotik on port eth4. While connecting with the admin laptop, the Mikrotik is used in access point mode.

3.2.2 High level design

The system’s overall design is covered in this phase of the research process.

3.png

Figure 3. High level design

In Figure 3, the Multiple Instruction form carried out on the Raspberry Pi Node Master will have three instructions for each data processed, namely sending data, receiving data, and processing data again. Meanwhile, the Raspberri Pi Node Slave1 and Slave2 will receive data from the Node Master, process it, and send it back to the Node Master.

3.2.3 Low level design

This stage covers a thorough explanation of the system design, including how to use MIMD parallel computing to parallelize an π value calculation application.

4.png

Figure 4. Low level design

Figure 4 describes the design of the MIMD parallel computing structure applied to the Raspberry Pi. On the Raspberry Pi Node Master, the first instruction stage is to send the slice value to be processed on the Raspberry Pi Nodes Slave 1 and Slave 2. On Raspberry Pi Nodes Slave1 and Slave 2, the first instruction performed on the data is to receive data from the Node Master. After the data is received, the second instruction is to process the data according to the Gregory-Leibniz calculation method, and the last instruction is to send the processed data to the Raspberry Pi Node Master. The second instruction on the Raspberry Pi Node Master is to receive data that has been processed from the Raspberry Pi Node Slave 1 and Slave 2, then the third instruction is that the data received will be processed again so that the Pi value is obtained, and the last instruction is to display the Pi value obtained on the terminal.

3.3 Implementation

The analytical and design stages that were completed earlier continue with the implementation step. Researchers have broken this stage down into various sections.

3.3.1 Operating system installation

BalenaEtcher program is used to install the operating system, which in this case is Raspberry Pi OS, into the SD Card.

5.png

Figure 5. Operating system installation

Figure 5 shows the process of BalenaEtcher installing the operating system on the SD card. To install the operating system onto the SD card, download the operating system file from the official Raspberry Pi page, then select the target SD card that will be used as the operating system storage medium, and finally click the Flash button and wait until the Flash process is complete.

6.png

Figure 6. Setting display

Figure 6 shows when the Raspberry Pi first boots with the operating system successfully installed on the SD card. The Raspberry Pi must then be turned on until the first setup display appears, at which point users can change the factory-set password and enter information for the current location, language, and time zone.

3.3.2 MPICH installation

In order to enable message carrying interfaces in MIMD parallel computing, Message passing Interface (MPICH) was built as part of this research [18].

7.png

Figure 7. MPICH installation

Figure 7 shows the steps of MPICH installation. Installing MPICH is done by typing sudo apt install mpich on the terminal, then confirming by typing Y, then pressing the enter.

3.3.3 MPI4Py installation

Researchers employ the Python programming language, which necessitates the use of a library initially. MPI4Py serves as the Python programming language’s Message Passing Interface binding. Any Python application can leverage many processors with the aid of MPI bindings [19]. Install the Python MPI library first by running sudo apt install python-pip python-dev libopenmpi-dev in the terminal and pressing enter. Once you’re done, execute sudo pip install mpi4py and hit enter.

8.png

Figure 8. MPI library installation

Figure 8 shows the steps of installing the Python MPI library by running sudo apt install python-pip python-dev libopenmpi-dev in the terminal and pressing enter.

9.png

Figure 9. MPI4Py installation

Figure 9 shows the steps of installing the MPI4Py by running sudo apt install mpi4py in the terminal and pressing enter

3.3.4 Sequential program implementation

The Gregory-Leibniz formula is adjusted in this study to account for the estimated value of Pi. James Gregory and Gottfried Wilhelm Leibniz, two prominent mathematicians from the 16th century, are known as Gregory-Leibniz. They developed the method for computing the value of π using an infinite series [10]. The arctan formula, developed by Gregory-Leibniz, is as follows:

$\arctan x=x-\frac{x^3}{3}+\frac{x^5}{5}-\frac{x^7}{7}+\cdots$               (3)

By using x=1 in the formula above, the Gregory-Leibniz π value formula is obtained as follows:

$\frac{\pi}{4}=1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\cdots$                 （4）

Thus, an approximate value of π is obtained:

$\pi=4\left(1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\cdots\right)$               (5)

To approximate the value of π with a sequential program, the calculation is carried out by one processing unit sequentially based on each term of repetition of the calculation performed [24]. Table 4 shows the several Iteration of terms were carried out in this study.

Table 4. Sequential program test scenarios

3.3.5 Parallel program implementation

This study utilizes MIMD parallel computing to do a parallel calculation of the estimated value of π using the Gregory-Leibniz formula. The phases of parallelization are as follows:

10.png

Figure 10. Parallelization phases

Figure 10 shows the phases of parallel π estimation. Parallelization is done by dividing the calculation task of each iteration among the slave nodes.

Table 5 shows the numerous scenarios were carried out according to the iteration/terms [24] to estimate the value of π with a parallel program

Table 5. Parallel program test scenarios

3.4 Testing

The output of the program used to estimate π value in sequential and parallel runs will now be discussed.

3.4.1 Sequential approximation and time recording

Utilizing the python gregory_leibniz-serial.py command, a sequential program may be run. The outcomes of running the program sequentially are showed in Figure 11.

11.png

Figure 11. Sequential program

The program is run nine times in accordance with the preset Terms, and the results are as follows:

Table 6 shows the recorded program execution time for each scenario. It can be seen that as the number of terms increases, the more time it takes to execute the program.

Table 6. Sequential program test results

To make the comparison of program execution times simpler to grasp, Figure 12 shows a chart created using the previous table.

3.4.2 Parallel approximation and time recording

The mpi4py-n xx-machinefile machinefile gregory_leibniz-parallell.py command enables the execution of a parallel program. The outcomes of the parallel program execution are showed in Figure 13.

12.png

Figure 12. Sequential program time chart

13.png

Figure 13. Parallel program

The program is run nine times in accordance with the preset terms, and the results are as follows:

Table 7. Parallel program test results

Table 7 shows the documented program execution time for each parallel program execution scenario. It can be seen that as the number of Rapsberry Pi used increases, the less time it takes to execute the program.

To help with comprehension of the comparison of program execution times, Figure 14 shows chart may be created using the created table:

14.png

Figure 14. Comparison of program execution time

3.4.3 Speedup and efficiency testing

In order to compare the performance gain achieved, here is the speedup graph:

15.png

Figure 15. Speedup comparison chart

Figure 15 shows how speedup compares. On one Raspberry Pi running a parallel program. At 100,000 terms, the best speedup reached is 2. The best speedup in a parallel program running on two Raspberry Pis is 3.884416925 at 20,000,000 terms. The best speedup in a parallel program running on three Raspberry Pis is 6.295302013 at 5,000,000 terms. This means that when five million terms are calculated using three Raspberry Pis, the best speedup is obtained. The more Raspberry Pis and the more processing core is used the better speedup will be obtained.

16.png

Figure 16. Efficiency comparison chart

Based on Figure 16 The efficiency corresponse to the speedup can be seen as follows: The best efficiency at the level of efficiency attained in the parallel program with one Raspberry Pi is 0.5 at 100,000 iterations. At the 20,000,000th iteration, the parallel program running on two Raspberry Pis achieved an efficiency level of 0.485552116. The best efficiency gained is 0.524608501 at the level of efficiency attained in the parallel program using three Raspberry Pis, and at iteration 5,000,000. The Raspberry Pi requires less electricity consumption than regular-sized desktop computers. This means sustainable energy sources, such as solar power [31] or wind power [32], could also be employed to provide electricity.