
#Raspberry Pi: The Nqueens Problem (benchmark) PreemptRT vs. Standard Kernel
Real Time Systems  5 min  2834
nqueen problemperformancepreemptrtraspberry pistandard kernelTable of content ShowNQueens Problem: A Benchmarking Solver for Raspberry Pi
The NQueens Problem/Puzzle is a wellknown 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 Nqueens problem for N = 4 is the following:
Fig. 1: Nqueens 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: PreemptRT Kernel 4.19.y  Performance TestMany people use the Nqueens 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 Nqueens problem for N=12, in single (ST) and multithread (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/rPITests 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.27v7+ (c841df752a7f9c2638678bb9f87b09f7459b41bc)
 PreemptRT Raspbian Kernel 4.14.27rt21v7+ (*)
(*) The repository was updated yesterday, while I was making the tests and writing this post!: now it is version 4.14.29rt25v7+
Standard Raspbian Kernel 4.14.27v7+
Single Thread & Multithread solution
Multithread
Fig. 2a: Multithread Configuration on Model B+ Fig. 2b: Multithread Configuration on Model B Singlethread
Fig. 3a: Singlethread Configuration on Model B+ Fig. 3b: Singlethread Configuration on Model B Solving the Nqueens problem in multithread configuration was about 3.41 times faster than on singlethread using Model B+. On Model B the factor increases up to 3.57 times. The Model B+ was 13% faster on multithread than the Model B on the same configuration. On singlethread configuration this percentage increases up to 18%. Temperature is a factor here. The Raspberry Pi decreases its performances when it reached 70°C. In multithread 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. MultiThread Solving Time 62.66 s 70.85 s MultiThread Max. Temperature 68.78 °C 78.69 °C Avg. SingleThread Solving Time 213.34 s 251.30 s SingleThread Max. Temperature 54.22 °C 52.61 °C PreemptRT Raspbian Kernel 4.14.27rt21v7+
Single Thread & Multithread solution
Multithread
Fig. 4a: Multithread Configuration on Model B+ Fig. 4b: Multithread Configuration on Model B Singlethread
Fig. 5a: Singlethread Configuration on Model B+ Fig. 5b: Singlethread Configuration on Model B Solving the Nqueens problem using the PreemptRT Raspbian Kernel in multithread configuration was 3.43 times faster on the Model B+ than using singlethread configuration. This factor increases slightly on Model B (3.48 times). Model B+ was 14% faster in multithread configuration and 16% in singlethread configuration. The maximal reached temperature was in multithread 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. MultiThread Solving Time 70.38 s 79.90 s MultiThread Max. Temperature 69.55 °C 78.72 °C Avg. SingleThread Solving Time 235.75 s 274.67 s SingleThread Max. Temperature 56.91 °C 56.66 °C PreemptRT 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
PreemptRT Raspbian KernelFig. 8b: Comparison Mean Temperature
PreemptRT Raspbian KernelThe Raspberry Pi 3 Model B+ using standard Raspbian kernel is 12% faster than using PreemptRT kernel in multithread operations. In singlethread operations, this percentage reduces to 11%. Same relation can be seen on the Model B: The standard Raspbian kernel is 12% in multithread configuration while only 9% in singlethread.
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.PreemptRT vs. Standard Raspbian Kernel Performance with Network/USB Load
The USB/Network IRQ interruption reduces the performance of the PreemptRT 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 Nqueens problem solver in multithread configuration and on a separated thread a webserver that received POST requests, and saved these requests (in my case: images) on a USBdriver. 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 PreemptRT Patched Raspbian Kernel.
Fig. 9a: Multithread Configuration on Model B+
with Standard Raspbian Kernel
receiving Data over EthernetFig. 9b: Multithread Configuration on Model B
with PreemptRT 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 PreemptRT kernel! The IRQ influence increases while using the USB and network ports! The maximal temperature using PreemptRT 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 PreemptRT Raspbian kernel!
Conclusions
The PreemptRT patched Raspbian kernel (4.14.yrt) 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.
Comments
Empty