RPI BPlus

#Raspberry Pi: The N-queens Problem (benchmark) Preempt-RT vs. Standard Kernel


N-Queens Problem: A Benchmarking Solver for Raspberry Pi

The N-Queens Problem/Puzzle is a well-known problem that consists of placing N chess queens on an N × N chessboard so that no two queens attack each other. For example, one possible solution to the N-queens problem for N = 4 is the following:

N-queens problem (N=4)
Fig. 1: N-queens problem example (N = 4). Source: Google Optimization Tools

As you can see, no two queens are on the same row, column or diagonal. Usually the problem consists to find all possible solutions, rather than one optimal solution.

I wrote a script in Python that calculates the number of all possible solutions. This script can be used as Benchmark for e.g. the Raspberry Pi.

Many people use the N-queens problem to test the performance of a defined solver. But this can be cheated. In my case, the solver (script) is not optimal (I implemented the backtracking way based on this solution), but it works, and it helps me to compare different configurations of the Raspberry Pi (kernel, model B & B+ etc.). I solved the N-queens problem for N=12, in single (ST) and multi-thread (MT) configurations and repeated the tests 45 (ST) / 100 (MT) to check the result variances.

All the data, scripts and notebooks are available here:

Python Code: https://github.com/lemariva/rPI-Tests

For the following Benchmark tests, I used the following hardware:

  • Raspberry Pi 3 Model B
  • Raspberry Pi 3 Model B+

Both boards with the following heatsink: Heatsink Raspberry Pi On the Model B+, I cut a litle bit a corner to not cover the hole of the new SoC packaging.

Kernels:

  • Standard Raspbian Kernel 4.14.27-v7+ (c841df752a7f9c2638678bb9f87b09f7459b41bc)
  • Preempt-RT Raspbian Kernel 4.14.27-rt21-v7+ (*)

(*) The repository was updated yesterday, while I was making the tests and writing this post!: now it is version 4.14.29-rt25-v7+

Standard Raspbian Kernel 4.14.27-v7+

Single Thread & Multi-thread solution

Multi-thread

Model B+ Multi-thread Configuration Model B Multi-thread Configuration
Fig. 2a: Multi-thread Configuration on Model B+ Fig. 2b: Multi-thread Configuration on Model B

Single-thread

Model B+ Single-thread Configuration Model B Single-thread Configuration
Fig. 3a: Single-thread Configuration on Model B+ Fig. 3b: Single-thread Configuration on Model B

Solving the N-queens problem in multi-thread configuration was about 3.41 times faster than on single-thread using Model B+. On Model B the factor increases up to 3.57 times. The Model B+ was 13% faster on multi-thread than the Model B on the same configuration. On single-thread configuration this percentage increases up to 18%. Temperature is a factor here. The Raspberry Pi decreases its performances when it reached 70°C. In multi-thread configuration both Raspberry Pi went really hot! It was possible to see the cooling improvement of Model B+. The maximal reached temperature was about 68.78°C on Model B+ while on Model B was 78.69°C. The ambient temperature was almost constant 19°C.

Model B+ Model B
Avg. Multi-Thread Solving Time 62.66 s 70.85 s
Multi-Thread Max. Temperature 68.78 °C 78.69 °C
Avg. Single-Thread Solving Time 213.34 s 251.30 s
Single-Thread Max. Temperature 54.22 °C 52.61 °C

Preempt-RT Raspbian Kernel 4.14.27-rt21-v7+

Single Thread & Multi-thread solution

Multi-thread

Model B+ Multi-thread Configuration Model B Multi-thread Configuration
Fig. 4a: Multi-thread Configuration on Model B+ Fig. 4b: Multi-thread Configuration on Model B

Single-thread

Model B+ Single-thread Configuration Model B Single-thread Configuration
Fig. 5a: Single-thread Configuration on Model B+ Fig. 5b: Single-thread Configuration on Model B

Solving the N-queens problem using the Preempt-RT Raspbian Kernel in multi-thread configuration was 3.43 times faster on the Model B+ than using single-thread configuration. This factor increases slightly on Model B (3.48 times). Model B+ was 14% faster in multi-thread configuration and 16% in single-thread configuration. The maximal reached temperature was in multi-thread configuration being 69.55°C on Model B+ and 78.22°C on Model B. Again, the new SoC packaging works great!

Model B+ Model B
Avg. Multi-Thread Solving Time 70.38 s 79.90 s
Multi-Thread Max. Temperature 69.55 °C 78.72 °C
Avg. Single-Thread Solving Time 235.75 s 274.67 s
Single-Thread Max. Temperature 56.91 °C 56.66 °C

Preempt-RT vs. Standard Raspbian Kernel Performance

Mean Time all Solutions - Standard Raspbian Kernel Mean temperature - Standard Raspbian Kernel
Fig. 7a: Comparison Mean Time to find all Solutions
Standard Raspbian Kernel
Fig. 7b: Comparison Mean Temperature
Standard Raspbian Kernel
Mean Time all Solutions - Preempt-RT Raspbian Kernel Mean temperature - Preempt-RT Raspbian Kernel
Fig. 8a: Comparison Mean Time to find all Solutions
Preempt-RT Raspbian Kernel
Fig. 8b: Comparison Mean Temperature
Preempt-RT Raspbian Kernel

The Raspberry Pi 3 Model B+ using standard Raspbian kernel is 12% faster than using Preempt-RT kernel in multi-thread operations. In single-thread operations, this percentage reduces to 11%. Same relation can be seen on the Model B: The standard Raspbian kernel is 12% in multi-thread configuration while only 9% in single-thread.

As I said in my last posts. The IRQ related with the USB/Network chip interrupts often, this takes about 5%-15% of CPU performance (reported using top). Almost same percentages are obtained on these analysis. Temperature is the main problem, the CPU reaches faster 68°C and reduces its performance.

Preempt-RT vs. Standard Raspbian Kernel Performance with Network/USB Load

The USB/Network IRQ interruption reduces the performance of the Preempt-RT kernel up to 12%. To test if its influence is greater if the network/ethernet or USB ports are used, I made the following test: I run the N-queens problem solver in multi-thread configuration and on a separated thread a webserver that received POST requests, and saved these requests (in my case: images) on a USB-driver. On my computer, I run a web client and send images in a loop. For this test, I used only the Raspberry Pi 3 Model B+, and repeated the solver 100 times using Standard and Preempt-RT Patched Raspbian Kernel.

Model B+ Multi-thread Configuration with Standard Raspbian Kernel Model B+ Multi-thread Configuration with Preempt-RT Raspbian Kernel
Fig. 9a: Multi-thread Configuration on Model B+
with Standard Raspbian Kernel
receiving Data over Ethernet
Fig. 9b: Multi-thread Configuration on Model B
with Preempt-RT Raspbian Kernel
receiving Data over Ethernet
Mean Time all Solutions - Standard vs Preempt-RT Raspbian Kernel Mean temperature - Standard vs Preempt-RT Raspbian Kernel
Fig. 7a: Comparison Mean Time to find all Solutions Fig. 7b: Comparison Mean Temperature

The solver on the standard kernel was 17% faster than on Preempt-RT kernel! The IRQ influence increases while using the USB and network ports! The maximal temperature using Preempt-RT kernel was 70.64°C while using standard kernel was 69.81°C.

Transfer rate - Standard Raspbian Kernel Transfer rate - Preempt-RT Raspbian Kernel
Fig. 7a: Client Transfer Rate - Standard Raspbian Kernel Fig. 7b: Client Transfer Rate - Preempt Raspbian Kernel

I measured also the transfer data rate from the client: It was reduced up to 34% (mean) using the Preempt-RT Raspbian kernel!

Conclusions

The Preempt-RT patched Raspbian kernel (4.14.y-rt) offers a solution to reduce the kernel latency (see results here). But, you lose a lot of CPU and communication performance. The data transfer over Ethernet is reduced to 34% and the CPU performance up to 12%. If your application is sampling sensors really fast and it doesn't do a lot of "math" or/and data transfers, probably you need to patch the Raspberry Pi kernel. Otherwise, you should use the standard kernel.

{{ message }}

{{ 'Comments are closed.' | trans }}