#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:

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

As you can see, there aren't two queens 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:

	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:

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

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

Single-thread

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.

Preempt-RT Raspbian Kernel 4.14.27-rt21-v7+

Single Thread & Multi-thread solution

Multi-thread

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

Single-thread

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!

Preempt-RT vs. Standard Raspbian Kernel Performance

Fig. 7a: Comparison Mean Time to find all Solutions Standard Raspbian Kernel	Fig. 7b: Comparison Mean Temperature Standard 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.

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

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.

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.