CPU usage time, simulation time and determinism

[bergerch]

As far as I understood Shadow can simulate the OS Kernel CPU usage and can capture processing time. For example consider an application process that creates 100 signatures (which consumes some time) then sends a messages to other processes.

This amount of time can be captured by Shadow's simulated OS Kernel, e.g. by to pushing back causally-depending events in the event queue by exactly this amount (correct me if I am wrong, but that was my impression on the influence of CPU usage on simulation time).

I was wondering how this time can be captured without disturbing the determinism of the simulation given that time measurements usually are a source of randomness?

[jtracey]

To the best of my knowledge, Shadow doesn't currently support CPU time simulation, so all computations in the simulation essentially take 0 sim time. If you need to run an experiment that requires taking CPU time into account, you have two options:

1. Use an emulator like mininet or netmirage instead, but be sure you have hardware that can handle running the full experiment in real time (so some kind of compute cluster with many CPUs).
2. First benchmark the computation time externally somehow (e.g., time how long it takes to generate 100 signatures many times, then take the median or mean), then model that extra computation by using something like sleep calls in the appropriate parts of the application code.

The first option has the advantage of modeling the actual, dynamic usage under deployment, the second option has the advantage of being deterministic (and running on cheaper hardware).

[bergerch]

I see.

The CPU time simulation was explained in an older talk about Shadow:
https://youtu.be/oIrkFVTRNKs?t=2371
(note timestamp)
But I assume this has then changed by now?

I guess your second solution is a possible (but a little inconvenient) workaround to preserve the determinism while enabling to simulate cpu usage.

[robgjansen]

The Shadow v1.x design has a preliminary cpu modeling feature that attempted to take into account CPU usage of the plugins running in Shadow. It works roughly as follows:

• Shadow starts a timer before it jumps over to the plugin stack to continue running it.
• When the plugin executes a blocking syscall that requires us to jump back to the Shadow stack and continue progressing simulation time, we stop the timer.
• The delay time is the difference between the timer start and stop time.
• Shadow adds the delay time to a CPU model for the host.
• If the cumulative delay is greater than a threshold, then the CPU is considered blocked and will become unblocked again after the simulation time advances by at least the delay time.
• Any event that would occur while the CPU is blocked gets pushed back and is handled when the CPU becomes unblocked again.

This CPU model was disabled by default, and could be enabled by setting --cpu-threshold=N to a positive value. As @bergerch points out, this causes simulations to become non-deterministic. We added a second feature to round the delay times to the nearest factor set by --cpu-precision to try to mitigate non-determinism, but this was a heuristic and does not guarantee determinism.

The problems with this CPU modeling approach is:

• It causes non-determinism as @bergerch points out, because different host CPUs will take different amounts of time to run the same workload.
• Does not model hosts with multiple CPUs operating in parallel (i.e., threads).
• The algorithm we used when a CPU entered the blocked state, i.e., pushing all events backward in the queue until the CPU returned to the unblocked state, destroyed the performance of the simulation. Basically, most of the simulation consisted in us moving events backward in the event queue rather than performing useful work.

So we disable the algorithm by default in Shadow v1.x, though the v1.15.0 release does still allow you to turn on the algorithm as described above. (We do not have much experience with using the feature, so beware of that.)

Also, we have temporarily removed the feature altogether in Shadow v2.x. We hope one day to bring back CPU modeling with a much better design, but we've been busy with moving to the 2.0 architecture and have not made it that far yet. In the meantime, if you are using Shadow v2.x then @jtracey recommendation of making blocking sleep calls in your application would be a reasonable workaround.

[lifeoftomi]

@robgjansen, trying to wrap my head around this and the original question. Is it correct to say that one could run an intensive application on Shadow and the host machine wouldn't feel a thing in terms of CPU usage? Also, how did the shadow-plugin-bitcoin experiment scale?

[bergerch]

@lifeoftomi

• In terms of real-time (time that executing the simulation takes): it would be be quite time consuming and lead to a long simulation run as your CPU will be busy for quite some time.
• In terms of simulated-time (time that passes within the simulation): it wont be affected.

[lifeoftomi]

Thanks @bergerch, so could I run an application that would normally be CPU-intensive within Shadow and not experience heavy resource consumption on my host machine?

[bergerch]

@lifeoftomi No since Shadow runs the real application binaries. You would need to change the source code of your application (e.g. commenting out costly operations) and re-compile. But this might easily break the application (consider the generation of signatures: if you leave that away then meassages can not authenticate succesfully and will not be processed at the receiving side). Proof-of-Work might be an exception here, because it is not doing something "useful". In a simulation, PoW mechanics could be easily replaced by just wating for a random amount of time instead of hashing and verifying the found nonces. But you would need to change the source code of the PoW protocol in the first place..

edit: I did not read the paper about the Bitcoin simulation, but I can not imagine that they would actually execute the hashing of PoW on a host because this can be easily modeled by some stochastic process and thus abstracted away from the application, saving CPU time

[robgjansen]

Let's redirect discussion about bitcoin scalability to #1753.

[alrevuelta]

This CPU model was disabled by default, and could be enabled by setting --cpu-threshold=N to a positive value. As @bergerch points out, this causes simulations to become non-deterministic. We added a second feature to round the delay times to the nearest factor set by --cpu-precision to try to mitigate non-determinism, but this was a heuristic and does not guarantee determinism.

Can see cpu-threshold flag was removed in https://github.com/shadow/shadow/pull/1263/files, @robgjansen is there a way to configure this in > v3.0.0? Or more in general, any new updates on how to run in the latest versions taking CPU consumption time into account?

[robgjansen]

With all of the work involved with migrating to Rust, we have not been able to implement a proper CPU modeling system yet. It is still on our list of things we want to get funded.

Some people still have some particular function(s) inside of an application that you expect to take a lot of CPU time and you would like to account for it when running inside of Shadow. In this case, as a workaround we have been recommending that some measurements of the CPU-intensive functions be taken outside of Shadow on bare-metal if possible, and then those measurements could be converted into periodic calls to sleep() or nanosleep() in your application. Those syscalls will cause shadow to block your application thread for the given amount of time.

Sorry, I realize it would be much nicer if this was just handled automatically on the Shadow side so that every application didn't have to go through this extra step. We just haven't quite gotten there yet.

In any case, hope that helps you understand the current situation.