Dynamic load balancing is a key methodology that is used to speed up computing clusters nowadays. The work sharing and the work stealing are two opposite algorithms with various implementations based on predefined metrics like performance, response time, fault tolerance, resource utilization, and scalability. For the heterogeneous soft-/hardware in the Raspberry Pi MPICH cluster, weight-based load balancing is the most efficient approach since different parameters such as the type of CPU and OS, RAM, workload, microSD card capacity, power consumption, and OS release date can be taken into consideration. These parameters are described numerically and linguistically, and hence the fuzzy logic is employed to estimate the performance weights of the cluster nodes. Then, this information is used to distribute the workload among the cluster nodes to minimize the execution time. In this project, fuzzification, formation of fuzzy rules, fuzzy inference, and defuzzification are applied to find the performance weights. The defuzzification is based on the multiplication operation. In the cluster with two Raspberry Pi 4B boards with 2 GB RAM and Raspberry Pi 64-bit OS with desktop and one Raspberry Pi 3B board with 1 GB RAM and Raspberry Pi 32-bit OS Lite, recommended performance weights are (5, 5, 1), respectively. The Python program for the prime numbers finding algorithm implements the proposed weight-based load balancing approach that is approximately five times faster than the basic algorithm with equal loading for the maximum integer number 300000. Weight-based load balancing, MPICH cluster, fuzzy logic, Raspberry Pi ICTERI-2021, Vol I: Main Conference, PhD Symposium, Posters and Demonstrations, September 28 - October 2, 2021, Kherson, Ukraine
MPICH is a free high-performance implementation of the Message Passing Interface (MPI) standard [1]. It has been tested on several platforms such as Linux, Mac OS, Solaris, and Windows. As of June 2016, this technology was exclusively used on nine of the top ten supercomputers, including Sunway TaihuLight which is ranked third in the TOP500 list as of November 2018. Concerning power consumption and performance, the Raspberry Pi MPICH cluster [2-4] is one of the most efficient approaches nowadays. Because of the heterogeneous soft-/hardware, e.g., Raspberry Pi 32/64-bit and Ubuntu operating systems (OSs) and Raspberry Pi 3B/3B+/4B boards with 1/2/4/8 GB RAM, the dynamic load balancing is one of the main challenges that require to distribute the workload across all the nodes to minimize the execution time.
The work sharing and the work stealing are two opposite algorithms in dynamic load balancing [5] that can be split up into various implementations based on predefined metrics such as throughput, response time, overhead, performance, fault tolerance, migration time, resource utilization, and
2021 Copyright for this paper by its authors. scalability [6]. Biased random sampling, active clustering, honeybee foraging, join idle queue, load balance min-min, and ant colony optimization are examples of these implementations [6]. Since the soft-/hardware configuration of the MPICH cluster is not fixed, active clustering is the most suitable approach, where the master node analyzes the performance of existing nodes and then distributes the workload in accordance with that. This approach is implemented in Oracle clusters as the weight-based load balancing [7]. For the initial phase, when existing nodes start communicating with each other, the Python software development is a trivial task: two blocking, send and recv, and two non-blocking, isend and irecv, communication methods send and receive data, respectively [8]. Hence, the key problem is the calculation of the performance weights associated with the cluster nodes. Concerning the processor performance, this problem is solved by the Exploitation of the Fastest Processor method which is a centralized algorithm for dynamic load distribution of parallel applications based on the Single Program Multiple Data paradigm [9]. However, other parameters, e.g., OS and RAM, are not taken into consideration in [9].
Performance weights are calculated based on heterogeneous parameters such as processor, OS, RAM, capacity of MicroSD card, current workload on the node. These parameters can be described numerically, e.g., 1 GB RAM, and linguistically, e.g., processor ARM Cortex-A53 1.2 GHz is “significantly below norm”, and hence the fuzzy logic [10-19] is proposed to estimate the performance weights associated with the cluster nodes.
This paper presents an approach of the performance weights assessment using fuzzy logic to optimize the workload distribution on the nodes in the Raspberry Pi MPICH heterogeneous cluster. The prime numbers funding algorithm is proposed to demonstrate a common technique used in parallel programming – solving a smaller case to speed up the solution of the full problem [20]. The modified version of the Python program to find prime numbers [4] was developed to speed up the Raspberry Pi MPICH heterogeneous cluster.
The paper is organized as follows: In Section 2, a basic implementation of the prime numbers finding algorithm with equal load balancing and its performance evaluation is presented, as well as Mamdani, Sugeno, and Tsukamoto fuzzy inference systems are compared and analyzed for the performance weights assessment. In Section 3, the fuzzy inference for the performance weights assessment of the Raspberry Pi MPICH heterogeneous cluster nodes is implemented, as well as equal and weight-based load balancing approaches are compared using the prime numbers finding algorithm. Conclusions are summarized in Section 4.
Python program [4] generates the first prime number 1, but it must be 2; other values are correct.
The Raspberry Pi rack mount and the router DIR-300A with a built-in 4-port switch are shown in Figure 2. Master, second, and third nodes have IP addresses 192.168.0.92, 192.168.0.41, and 192.168.0.13, respectively. Boards are connected only by Ethernet cables via the router DIR-300A and the power supply since they are remotely controlled by the Secure Shell (SSH) protocol, as well as the standard VNC (Virtual Network Computing) server was installed on the master node to control the Raspberry Pi 4B through the RealVNC remote access software [21]. The cluster has a two-dimensional mesh topology [22].
Execution times for one (data series 1, performance weights (
Figure 4 represents the Raspberry Pi command top [26] showing the list of processes currently running on the cluster nodes with equally distributed workload: the processor’s share of the CPU time is close to 0 % for the second node (finished its part), it is usually around 10 % for the first node (finished its part and waiting to gather data), and it is around 25 % for the third node, i.e., the first and the second nodes finish their parts and then they wait for the third node to accomplish its work.
The fuzzy logic theory was introduced by Dr. Lotfi Zadeh in 1965 and was advanced by many other researchers since that time, e.g., [11-18]. In fuzzy logic, four main stages are fuzzification, formation of fuzzy rules, fuzzy inference, and defuzzification. Fuzzy inference methods that are generally used are Mamdani, Sugeno, and Tsukamoto. Concerning the defuzzification, they can be differentiated as follows: fuzzy Tsukamoto uses the centralized mean algorithm, fuzzy Mamdani uses the centroid method [17], fuzzy Sugeno generates fuzzy singleton values [19]. Many other defuzzification methods have been proposed, but none of them generates the output for the common sense of knowledge modeling [19]. The computational results of defuzzification often conflict [13-18], as well as they do not have a uniform framework [19].
In this project, the approach [10-12], where the defuzzification is based on the multiplication operation, is proposed to estimate the performance weights of the cluster nodes. The cluster node j, j[1,N] and N is the general number of cluster nodes, is described by the vector = { 1, 2, … , }, K is the general number of soft-/hardware characteristics. Fuzzy set gi, i[1,M] and M is the general number of the cluster parameters zi such as processor/OS/RAM, contains the requirements to the cluster parameters zi. Components gi, G={g1,g2,…,gM}, are specified by the membership functions i(zi)→[0,1]. Finding vector G is the solution represented by the fuzzy set V={vj} that is the intersection of {Xj} and G. Estimation of the performance weights includes the following steps: 1. Determine set {Xj}, j[1,N].
2. Calculate membership functions i(zi) as follows (zij must be positive since the cluster soft/hardware are described by positive numbers in this project): = = { }
, if the best characteristic equals max{zij};
{ }, if the best characteristic equals min{zij}.
(
Membership functions (
4. Find vector V as follows: 3. Convert the vector {Xj} to the vector {zi} of the cluster characteristics, and then to the fuzzy where i – weights that represent the ranks of requirements {zi}.
5. Calculate the performance weights of the cluster nodes using vector V.
3.1.
Linguistic and numeric variables zij and weights i are shown in Table 1 for the Raspberry Pi MPICH heterogeneous cluster soft-/hardware. Data presented in Table 1 is the authors' subjective view based on the practical experience with respect to the performance.
Performance weights of the cluster nodes are calculated in Table 2. Analysis of the fuzzy set V shows
that the calculated output variable for the third node is approximately five times less compared with the
first and the second nodes: 0.975/0.2294.258 and 0.985/0.2294.301, i.e., the closest larger integer
number is 5. Hence, recommended performance weights are (
The prime numbers finding algorithm with the weight-based load balancing using recommended
performance weights for the Raspberry Pi MPICH cluster nodes can schematically be represented as
the pseudocode in Figure 5. This algorithm loads all the working cluster nodes in accordance with their
performance weights. If end_number equals 100 and the performance weights are (
1. Master node, Raspberry Pi 4B board, my_rank_new={6, 7, 8, 9, 10}: 13, 35, 57, 79, 15, 37, 59, 81, 17, 39, 61, 83, 19, 41, 63, 85, 21, 43, 65, 87. The master node is loaded less than the second node that compensates the additional workload related to acquiring and gathering data from other nodes.
2. Second node, Raspberry Pi 4B board, my_rank_new={0, 1, 2, 3, 4}: 1, 23, 45, 67, 89, 3, 25, 47, 69, 91, 5, 27, 49, 71, 93, 7, 29, 51, 73, 95, 9, 31, 53, 75, 97.
3. Third node, Raspberry Pi 3B board, my_rank_new={5}: 11, 33, 55, 77, 99.
The developed Python program was executed on the Raspberry Pi MPICH cluster with the
abovementioned three nodes. The execution times for performance weights (
1.5 GHz (“norm”; z11=5)
(“norm”; z21=5)
(“norm”; z31=5)
worker load (“above norm”; z41=3) 8 GB (z51=8) 6.4 W (z61=6.4)
August 24, 2020 August 24, 2020 (“below norm”; z71=3) (“below norm”; z72=3) January 11, 2021 (“norm”; z73=5)
1.5 GHz (“norm”; z12=5) 1.2 GHz (“significantly below norm”; z13=1)
(“norm”; z22=5) (“significantly below norm”; z23=1)
(“norm”; z32=5) (“below norm”; z33=3) Worker node (“norm”; Worker node (“norm”; z42=5) z43=5) 8 GB (z52=8) 6.4 W (z62=6.4) 4 GB (z53=4)
Analysis of the execution times for equal and weight-based load balancing implementations of the
prime numbers finding algorithm, Figure 3 and Figure 6 respectively, shows the following outcomes:
1. The value of speedup for the weight-based load balancing implementation with performance
weights (
2. The weight-based load balancing implementation with performance weights (
Weight-based load balancing in the Raspberry Pi MPICH heterogeneous cluster was implemented using the fuzzy estimating of performance weights. Fuzzy variables are the type of CPU and OS, RAM, workload, microSD card capacity, power consumption, and OS release date. Four main stages of fuzzification, formation of fuzzy rules, fuzzy inference, and defuzzification are applied to calculate the performance weights of the cluster nodes. In this project, the defuzzification is based on the multiplication operation.
The cluster consists of two Raspberry Pi 4B boards with 2 GB RAM and Raspberry Pi 64-bit OS
with desktop and one Raspberry Pi 3B board with 1 GB RAM and Raspberry Pi 32-bit OS Lite. The
Python program for the prime numbers finding algorithm is a test example of the developed approach:
1. Recommended weight-based load balancing with performance weights (
2. The value of speedup for the weight-based load balancing implementation with performance
weights (
Since load balancing is an important task not only for the considered Raspberry Pi MPICH heterogeneous cluster but also for distributed computing systems in general, obtained results may be used in a wide spectrum of parallel programming applications.
The most likely prospect of the presented weight-based load balancing method is the development of a multithread Python application.
This paper and the research behind it could be much complicated without the support of universities where authors have been conducting the presented project. Authors sincerely appreciate the management and colleagues of the University of Central Asia (Kyrgyzstan) and the Kryvyi Rih National University (Ukraine) for all their patience and kind assistance in the completion of this work.
[11] M.M. Gupta, Soft Computing and Intelligent Systems: Theory and Applications, N.K. Sinha (Ed.),
Academic Press, San Diego, CA, USA, 2000. doi: 10.1016/B978-012646490-0/50011-1. [12] N.L. Prokhorov, Supervisory Computer Control Systems, Finances & Statistics Press Inc.,
Moscow, 2003.
[13] A. Saepullah, R.S. Wahono, Comparative Analysis of Mamdani, Sugeno And Tsukamoto Method
of Fuzzy Inference System for Air Conditioner Energy Saving, J. of Intelligent Systems 2(
Biomass, J. Sustainability 7, 2015, pp. 12359-12371. doi: 10.3390/su70912359.
[17] E. Sonalitha, B. Nurdewanto, S. Ratih, N.R. Sari, A.B. Setiawan, P. Tutuko, Comparative
Analysis of Tsukamoto and Mamdani Fuzzy Inference System on Market Matching to Determine
the Number of Exports for MSMEs. In: Proceedings of the 9th EECCIS Electrical Power,
Electronics, Communications, Controls, and Informatics Seminar, IEEE, Batu, East Java,
Indonesia, 2018, pp. 440-445. doi: 10.1109/EECCIS.2018.8692989.
[18] Adriyendi, Fuzzy Logic using Tsukamoto Model and Sugeno Model on Prediction Cost,
International J. of Intelligent Systems and Applications 6(
URL: https://stars.library.ucf.edu/etd/4005. [26] Geek University: List Processes in Real-time, n.d. URL: https://geek-university.com/raspberrypi/list-processes-in-real-time/. [27] Power Consumption Benchmarks: Drupal 9 on a cluster of Raspberry Pis, n.d. URL: https://www.pidramble.com/wiki/benchmarks/power-consumption.