Manage cookies

We use cookies to improve our services. Read more about how we use cookies and how you can refuse them.

The necessary cookies help to make the website work properly.

Anonymous statistical cookies help to understand how visitors use the website.

  • Real Time Systems
    5 min | 14075

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

    Real Time Systems | 5 min | 14075


    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, 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.

    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 Test

    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:

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

    Model B+ Multi-thread ConfigurationModel 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 ConfigurationModel 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 Time62.66 s70.85 s
    Multi-Thread Max. Temperature68.78 °C78.69 °C
    Avg. Single-Thread Solving Time213.34 s251.30 s
    Single-Thread Max. Temperature54.22 °C52.61 °C

    Preempt-RT Raspbian Kernel 4.14.27-rt21-v7+

    Single Thread & Multi-thread solution

    Multi-thread

    Model B+ Multi-thread ConfigurationModel 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 ConfigurationModel 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 Time70.38 s79.90 s
    Multi-Thread Max. Temperature69.55 °C78.72 °C
    Avg. Single-Thread Solving Time235.75 s274.67 s
    Single-Thread Max. Temperature56.91 °C56.66 °C

    Preempt-RT vs. Standard Raspbian Kernel Performance

    Mean Time all Solutions - Standard Raspbian KernelMean 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 KernelMean 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 KernelModel 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 KernelMean temperature - Standard vs Preempt-RT Raspbian Kernel
    Fig. 7a: Comparison Mean Time to find all SolutionsFig. 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 KernelTransfer rate - Preempt-RT Raspbian Kernel
    Fig. 7a: Client Transfer Rate - Standard Raspbian KernelFig. 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.


    Comments

    Empty