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

Real Time Systems | 5 min | 4657

Table of contentShow## 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, 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.

If you are looking for a tutorial or performance results for**kernel 4.19.y**or you have a**Raspberry Pi 4B**check this article:

#Raspberry Pi 4B: Preempt-RT Kernel 4.19.y - Performance TestMany 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-TestsFor 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.

**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

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!

**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

Fig. 7a: Comparison Mean Time to find all Solutions

Standard Raspbian KernelFig. 7b: Comparison Mean Temperature

Standard Raspbian KernelFig. 8a: Comparison Mean Time to find all Solutions

Preempt-RT Raspbian KernelFig. 8b: Comparison Mean Temperature

Preempt-RT Raspbian KernelThe 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 EthernetFig. 9b: Multi-thread Configuration on Model B

with Preempt-RT Raspbian Kernel

receiving Data over EthernetFig. 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.

## Mike 02.20.2020

If you're going to show side-by-side graphs, it'd make it MUCH easier to visually compare if you used the same scale on both. For example, on your last pair for the ethernet transfer, at a glance they look the same. But if they were both scaled so they went 0-80, then you'd see the one going most of the way to the top and the other would only go about 1/3 the way up, thus showing the difference at a quick glance and without needing to read the specific numbers. IMHO, using different scales pretty much makes the graphs useless.