Reliable computational time measurement for benchmarking trackers and controllers

[bconvens]

Hi,

In one of your papers on the MPC tracker (https://ieeexplore.ieee.org/document/8594266) the authors wrote: “the current implementation of the MPC tracker relies on the CVXGEN to solve the quadratic program. A single iteration of the MPC tracker takes between 2 to 10 ms using only a single core of the Core-i7 processor, with a maximum of 30 iterations of the CVXGEN solver. “

My questions below are for the purpose of comparing the compute time between algorithms:

1. Does this measurement report only the time of a single iteration of the QP solver or the full time of the update function of the mpc_tracker's ROS nodelet? So, I understand you always break the solver after 1 iteration to save compute time, or could you easily run more iterations on the NUC? If so how many?
2. What’s the reason you observe such high variability in the compute time, from as low as 2ms to as high as 10ms? Is it due to the specific QP solver or is there another reason for this stochasticity?
3. How did you reliably measure the computational time of the tracker? I have seen various functions being used, for example:

• ros::Time::now()
• ros::WallTime::now()
• std::chrono::system_clock::now()
• std::chrono::time_point<std::chrono::system_clock>
• std::chrono::duration<double>
• std::chrono::high_resolution_clock::now()
• std::clock_t c_start = std::clock()
  but I am not sure what you would consider the most reliable and correct way to benchmark computational times of control algorithms.

4. How did you set a single core of the Core-i7 processor and undo it afterward to the default number of cores? If so, why do you think it is better to benchmark with only a single core?
5. Would there be any difference when the computational time is measured during a Gazebo simulation or onboard the real UAV?

Thanks a lot for the discussion!
Bryan

[matemat13]

Hello, I will try to address some of your questions, but most of this discussion is best answered by Tomáš (@klaxalk) himself, who is the main author of both the paper and the related implementation.

1. From the quoted part of the paper, I'd say that the interpretation is a bit unclear, but this is how I'd interpret it (Tomáš will probably clarify this): One iteration of the MPC tracker runs the CVXGEN solver which is an iterative optimizer, so to get one solution (for one iteration of the MPC tracker), the CVXGEN runs several iterations of the optimization. The number of optimization iterations of CVXGEN is limited to 30 to ensure the maximal total computational time of 10ms for the MPC tracker. Therefore:

   • A single iteration of the MPC tracker takes from 2ms to 10ms and consists of up to 30 iterations of CVXGEN.
   • A single iteration of the CVXGEN optimizer (which takes several iterations to find a good solution) is max. 10ms/30 long.

2. Again, Tomáš knows the precise answer, but here's my take. There are two main reasons that I see for the variation:

   • The CVXGEN optimizer can find a suitable solution in a lower number of iterations than is the maximum of 30. Then, it will finish sooner, and therefore the whole iteration of the MPC tracker will be shorter.
   • There are other processes running on the CPU that may preempt the thread with the MPC tracker while it's running. The OS will return the processor to the MPC thread later, enabling it to finish. This will cause delays that are more probable if the CPU has a high load because then there is more need for preemption (many processes share the same CPU).

3. The correct way of measuring time intervals for the purposes of benchmarking would be the std::chrono::steady_clock which is the only one that guarantees monotonicity and a constant time between ticks (the ROS analogue should be ros::SteadyTime if I'm reading the documentation correctly). To measure the timing of our code, we typically use the mrs_lib::ScopeTimer helper tool (that is currently using std::chrono::system_clock which is kinda wrong, so we should fix that :D). Of course keep in mind that when benchmarking, you should run the algorithm many times and get the mean to ensure you've not measured an outlier (possibly also the deviation).

4. I'm not sure how Tomáš did the benchmark for the paper, but if I were doing it now, I'd separate just the relevant part of the code I'm trying to measure to a specialized program, run it with synthetic or pre-recorded data a few thousand times, and measure the durations of each run. Then, I'd calculate the statistics. This way, you minimize the impact of preemption by other processes that are part of the control pipeline, possible delays due to mutex locking etc.

5. This is related to the previous answer. If your computer is on its knees (meaning that you have many other processes running and the CPU has a high load) when you try to measure the timing, there is a larger probability that your optimizer will get interrupted by the OS due to preemption or that you'll have to wait for another thread to release a mutex. When you're simulating, the computer needs to calculate the whole simulation and the control pipeline (including the thing you're trying to measure) in parallel, so I'd expect longer measured computation durations of the optimization (unless you have a really good processor that can run the simulation on another cores without affecting the other calculations). To avoid this, see my answer to 4.

It's nice seeing that someone in the robotics community is taking the science seriously and is comparing his contribution to real SotA, good luck with the research and the paper! :)

[DanHert]

Hello, I can elaborate on some of the points:

1. The MPC optimization problem is separated per axes into 4 different problems - X, Y, Z and heading. Each axis has its own CVXGEN solver (as they can have different constraints), and they are running sequentially (this part could be parallelized). Each solver for each axis has a set maximum number of iterations (30). The 2-10ms time interval refers to the entire process of updating the mpc tracker, so in this time, all 4 axes are solved, with up to 30 CVXGEN iterations per axis.
2. Exactly as matemat13 writes, CVXGEN will not require the 30 iterations with simple problems, so it can finish e.g. only after 5 iterations. So the run time is dependant on the given reference trajectory.

[klaxalk]

Hi,

Hey Bryan, good to hear from you! I think most of the questions were already answered. Nevertheless, I will try to answer as well.

In one of your papers on the MPC tracker (https://ieeexplore.ieee.org/document/8594266) the authors wrote: “the current implementation of the MPC tracker relies on the CVXGEN to solve the quadratic program. A single iteration of the MPC tracker takes between 2 to 10 ms using only a single core of the Core-i7 processor, with a maximum of 30 iterations of the CVXGEN solver. “

I admit, the paper could be written better. Luckily, not that much has changed from the time of publication, so we relate to the current implementation.

My questions below are for the purpose of comparing the compute time between algorithms:

1. Does this measurement report only the time of a single iteration of the QP solver or the full time of the update function of the mpc_tracker's ROS nodelet? So, I understand you always break the solver after 1 iteration to save compute time, or could you easily run more iterations on the NUC? If so how many?

The time that actually matters is the total computational time of a single iteration of the MPC tracker across all the axes, i.e., X, Y, Z, heading. If the total time is larger than 1 / execution rate, then the tracker does not run in real time. Currently, we execute the tracker at 100 Hz, so the complete iteration must take under 10 ms. And the complete iteration consists of calculation of the LCQP by CVXGen for each axis: X, Y, Z and heading. The solver itself uses an iterative algorithm, which can need tens of iterations to converge to the global optimum, we limit that to max 25 iterations, which we found both enough for finding a good solution and not too much for exceeding the desired computational time. In this, we sortoff rely on the solver to spit out solutions in a consistent way. If the solver were "inconsistent" in finding the solution, we would probably not use it, or we would add an explicit time limiter on it.

2. What’s the reason you observe such high variability in the compute time, from as low as 2ms to as high as 10ms? Is it due to the specific QP solver or is there another reason for this stochasticity?

As @DanHert said, it varies according to the input and, by fact, on whether the solution is LCQP constrained or not. Solutions that are not constrained can be found quite easily (theoretically in closed form). Constrained solutions require an iterative approach.

3. How did you reliably measure the computational time of the tracker? I have seen various functions being used, for example:


* `ros::Time::now()`

* `ros::WallTime::now()`

* `std::chrono::system_clock::now()`

* `std::chrono::time_point<std::chrono::system_clock>`

* `std::chrono::duration<double>`

* `std::chrono::high_resolution_clock::now()`

* `std::clock_t c_start = std::clock()`
  but I am not sure what you would consider the most reliable and correct way to benchmark computational times of control algorithms.

check @matemat13 response. In that time, we measured using the WallTime.

1. How did you set a single core of the Core-i7 processor and undo it afterward to the default number of cores? If so, why do you think it is better to benchmark with only a single core?

The execution of the CVXGen is single core. There is no way around that, the code itself is C99, so no threading :-).

2. Would there be any difference when the computational time is measured during a Gazebo simulation or onboard the real UAV?

It depends. We always try to fly with the onboard computer having some spare power, i.e., having the CPU load < number of cores. However, for most people, it is difficult to run simulations like that, because a generic laptop struggles with the additional load caused by the simulation. In my case, I simulate on Core I9-9900k or i7, so when it matters, I don't push the PC to the limits.

Thanks a lot for the discussion! Bryan

Sincerely, Tomas

[matemat13]

Now I see that these "Discussions" are probably meant to work more like StackExchange, so there can only be one correct answer to one question (which doesn't sound much like a discussion to me :D). Also, I can't comment under the original question for some reason but only under one of the answer-candidates, so I'm writing here. @bconvens please consider choosing one of the answer-candidates and mark it as an answer to close this "discussion" if you feel like your question was answered :)