The CMG'14 conference was a blast! The presentation of our paper that we wrote with my colleague Brian Eck was very well accepted. Thank you!
Showing posts with label Monte-Carlo. Show all posts
Showing posts with label Monte-Carlo. Show all posts
Saturday, October 25, 2014
2015 Update about CMG'14 presentation:
The CMG'14 conference was a blast! The presentation of our paper that we wrote with my colleague Brian Eck was very well accepted. Thank you!
Tuesday, July 6, 2010
More on Monte-Carlo simulations and scalability
In one of my earlier posts (May 22, 2010), I talked about using Monte-Carlo simulation for evaluating system capacity using the Universal Scalability Law. This post is an extension of that train of thought.
A very important and convenient feature of the USL model is that its parameters α and β can be evaluated by running a controlled experiment, passing a number of instructions through the system of different numbers of parallel processors and measuring the time it took the system to process these instructions.
(Disclaimer: All charts, diagrams, and values in this post are not based on actual collected data and are provided for illustrative purposes only. All the data were generated and processed using the R programming language)
When we run a controlled experiment, we have a fixed number of processors and a fixed set of tasks, and we measure the throughput. Everything is fixed, and we can quickly calculate the parameters.
However, when we are in a production mode, we may not have such luxury. That will definitely have a negative effect on our ability to get the α and β as deterministic numbers.
We are measuring from the production system whatever we can get, and as a result, we get a distribution of possible αs and a distribution of possible βs of the Universal Scalability Law model.
In this case, we can measure the throughput of a group of processors (a server, or a server pool) over time, collecting the data on throughput and the number of processors in operation on this group of processors at the time that such throughput was measured.
Then from these data, we can estimate the α and β parameters, by using, e.g., the (modified to fit the formula) Multivariate Least-Squares method, or Max-Likelihood Estimation, or any other suitable way to do that. These stochastic methods allow estimating the significance of the model parameters, but more importantly, their distributions.
Once we have these parameters – as probabilistic values – and the number of processors – as a random value with a (uniform?) distribution– we can run the Monte-Carlo simulation and identify the likeliest values of the system throughput, as well as potential pitfalls.
Generally, a regression cannot be extended beyond the range over which it was built. But the universal part of the Universal Scalability Law implies that it can be used with the same parameters for systems whose size and complexity extend beyond the system on which these parameters were calculated.
Thus, keeping the same α and β distributions, and running a Monte-Carlo simulation on a number of processors P extended beyond the original 4-40 range to a range of 32-400 gives the following USL curve:
By running the Monte-Carlo simulation, we can also get the distribution of the Throughput. In the particular example considered here, we have a distribution very strongly skewed to the right (higher end of the throughputs).
We also see that the throughput will have a range of achievable values, which is determined by the α and β distributions calculated above, as well as the distribution of the number of processors running simultaneously on the system under consideration.
It is interesting to look at the throughput curves at various distributions assumed for the numbers of processors running. The plots above described a uniform distribution, meaning that there is a range of numbers of processors, and at any time, each of this numbers has an equal chance of being operational; in other words, the load balancers are working properly.
Alternatively, we may consider a binomial model, wherein a given fraction of the pool of processors is operational at any time. It is a discreet equivalent of the normal distribution, and it is intuitively obvious that the system will behave differently in this model.
Monte-Carlo simulation shows that, indeed, for a binomial distribution of the number of processors running in the group, USL describes a very different behavior:
Here we have 400 processors, of which 25% (100 processors) are operational at any time. All other parameters are the same as in the uniform case analyzed above.
Interestingly enough, replacing that with 110 processors, of which 90% are operational at any time (again the same 100 processors), gives an even different behavior:
It is important to understand that, even if the data behavior doesn’t seem to support the Universal Scalability Law model, it only means that the distribution of the number of servers is non-uniform: these pictures were obtained by using the USL equation.
These last two plots do not mean that it is very difficult to get the USL model parameters by using data obtained from a non-uniform distribution of the number of servers in operation: we assume that the uncertainty in the α and β values comes from us not knowing the exact numbers and not from any inherent indeterminacy of the contention and coherency terms.
In the case of binomial distribution of parallel servers running on the task, we have a nearly normal distribution of throughput (Compare it with the earlier throughput histogram for uniform model of the running processors on the right)
It seems reasonable to theorize that the shape of distribution of a multi-processor system throughput is determined by the way system is operating, and we can, by looking at the historical histogram of throughput for a system, determine the model describing the system’s load balancing operation.
As a side note, if the α and β distributions are not normal, we will have a different shape of throughput distributions.
A very important and convenient feature of the USL model is that its parameters α and β can be evaluated by running a controlled experiment, passing a number of instructions through the system of different numbers of parallel processors and measuring the time it took the system to process these instructions.
(Disclaimer: All charts, diagrams, and values in this post are not based on actual collected data and are provided for illustrative purposes only. All the data were generated and processed using the R programming language)
When we run a controlled experiment, we have a fixed number of processors and a fixed set of tasks, and we measure the throughput. Everything is fixed, and we can quickly calculate the parameters.
However, when we are in a production mode, we may not have such luxury. That will definitely have a negative effect on our ability to get the α and β as deterministic numbers.
We are measuring from the production system whatever we can get, and as a result, we get a distribution of possible αs and a distribution of possible βs of the Universal Scalability Law model.
In this case, we can measure the throughput of a group of processors (a server, or a server pool) over time, collecting the data on throughput and the number of processors in operation on this group of processors at the time that such throughput was measured.
Then from these data, we can estimate the α and β parameters, by using, e.g., the (modified to fit the formula) Multivariate Least-Squares method, or Max-Likelihood Estimation, or any other suitable way to do that. These stochastic methods allow estimating the significance of the model parameters, but more importantly, their distributions.
Once we have these parameters – as probabilistic values – and the number of processors – as a random value with a (uniform?) distribution– we can run the Monte-Carlo simulation and identify the likeliest values of the system throughput, as well as potential pitfalls.
Generally, a regression cannot be extended beyond the range over which it was built. But the universal part of the Universal Scalability Law implies that it can be used with the same parameters for systems whose size and complexity extend beyond the system on which these parameters were calculated.
Thus, keeping the same α and β distributions, and running a Monte-Carlo simulation on a number of processors P extended beyond the original 4-40 range to a range of 32-400 gives the following USL curve:
By running the Monte-Carlo simulation, we can also get the distribution of the Throughput. In the particular example considered here, we have a distribution very strongly skewed to the right (higher end of the throughputs).
It is interesting to look at the throughput curves at various distributions assumed for the numbers of processors running. The plots above described a uniform distribution, meaning that there is a range of numbers of processors, and at any time, each of this numbers has an equal chance of being operational; in other words, the load balancers are working properly.
Alternatively, we may consider a binomial model, wherein a given fraction of the pool of processors is operational at any time. It is a discreet equivalent of the normal distribution, and it is intuitively obvious that the system will behave differently in this model.
Monte-Carlo simulation shows that, indeed, for a binomial distribution of the number of processors running in the group, USL describes a very different behavior:
Here we have 400 processors, of which 25% (100 processors) are operational at any time. All other parameters are the same as in the uniform case analyzed above.
Interestingly enough, replacing that with 110 processors, of which 90% are operational at any time (again the same 100 processors), gives an even different behavior:
It is important to understand that, even if the data behavior doesn’t seem to support the Universal Scalability Law model, it only means that the distribution of the number of servers is non-uniform: these pictures were obtained by using the USL equation.
These last two plots do not mean that it is very difficult to get the USL model parameters by using data obtained from a non-uniform distribution of the number of servers in operation: we assume that the uncertainty in the α and β values comes from us not knowing the exact numbers and not from any inherent indeterminacy of the contention and coherency terms.
In the case of binomial distribution of parallel servers running on the task, we have a nearly normal distribution of throughput (Compare it with the earlier throughput histogram for uniform model of the running processors on the right)
It seems reasonable to theorize that the shape of distribution of a multi-processor system throughput is determined by the way system is operating, and we can, by looking at the historical histogram of throughput for a system, determine the model describing the system’s load balancing operation.
As a side note, if the α and β distributions are not normal, we will have a different shape of throughput distributions.
Tuesday, May 25, 2010
More on Monte-Carlo simulation: if we don't know the equation
In my previous post, I was discussing the beauty of using Monte-Carlo simulation when we can describe the world by a formula. Sadly, more often than not, we can't. The beauty of Monte-Carlo analysis is in its suitability for such cases. If we can describe the world in a set of nodes and links (aka states and events), and if we know the probability distribution of the states, or the timing and magnitude of the events, and we want to know the maximum-likelihood of an outcome, we do not have to use an analytical model: the node-and-link grid has all the solutions in it. Some of these solutions are expressed as an equation or set of simultaneous equations (again); others, a parsing algorithm (akin to the parsing algorithm for an N-ary tree).
Any node-and-link model involves activities (akin to decision making) on nodes, connected by links. In some cases, such links will be physical; e.g., traffic simulation, where the highways will be represented by links, and nodes will correspond to intersections, stores, towns, etc. Traffic density, delays, link traversal times, link and node capacities would be the independent variables for the "provider" nodes and links and dependent variables for the "receiver" nodes and links.
In other cases, links are logical, belonging to the "IF...THEN...ELSE" category. Probability distributions of decisions at each node will be the metrics of interest in this case, along with the other parameters, like retention time at the node, link delay, etc.
A Closer Look at the Node-and-Link Model Structure from the Monte-Carlo Standpoint.
A fragment of a traffic network represented by nodes and links is shown in Figure 1 (left). "Vehicles" (anything from cars to messages) traverse the nodes via links, each node and link having their intrinsic properties, like retention time; capacity; throughput, reliability, etc.
A traffic network model can just as well simulate a decision grid by introducing a virtual “crawler” parsing the network. By sending multiple crawlers down the network and simulating each crawler's retention times and decisions at each node, we will build the total distribution of the network latency.
The diagram on the right illustrates the concept. Nodes are decision-making points, where the crawlers are detained for time periods that can be described by known distribution (see the histograms). At decision nodes (e.g., N2_2 in this diagram), each link is associated with a given frequency of selection (the binary histogram next to it).
The beauty of Monte-Carlo simulation is that it can do fast-time modeling, simulating the time faster than it happens in the model's real-world protagonist system.
It can be achieved in a number of ways, most popular of which are:
1. Real-time: when running human-in-the-loop simulations, with actual humans making some of the decisions, as well as in psychology and social sciences research, real-time Monte-Carlo situation is irreplaceable, as it allows subjects to make decisions in the actual tempo of the world they are used to. It is also very popular in the game business, with SimCity and Earthquake being among the earliest adopters of this approach, where the user is in control of the simulated world.
Interactive online games are the next step in the evolution of the real-time Monte-Carlo simulation, approach, where users are in control, and all the hundreds (thousands?) of users, by virtue of playing the game, become the simulation. The downside of using interactive-game environment in any research is that the number of users varies, and that will likely make any data collected from such a setup too noisy to be useful.
2. Time-scale: the simulated time delays are actually waited out on a scale by the modeling computer. This method allows building very high-fidelity event-and-process models; however, it may not be very efficient for modeling situations that take a long time to complete without much happening; e.g., a simulation of a day of operations of a police station in a quiet neighborhood of Beverly Hills, CA would be too boring to analyze and it would take way too long for any analyst's liking, even if the scale is 1:24, allowing a day in simulated time to pass in 1 hour or the simulation's runtime. Another drawback of time-scale simulations is in their dependency on the simulator running: a stoppage in the operation of the program software or hardware will cause a disconnect between the simulated time and real time, which time-scale modeling developers need to be aware of and account for in their disaster recovery and exception handling practices.
3. Fast-time: this is yet another change of paradigm with regard to what the nodes and links represent. (See illustration below)
Each crawler (aka Agent) knows what the timestamp of its next event will be. The event may be any change of the crawler's current state (spatial location, heading on the compass, number of friends on Facebook, job status, citizenship, oil pressure, speed, funding status, etc).
A master controller keeps the simulation time and a sorted collection of agents in the order of next event times. All agents act independently or in interaction with each other via the rules defined for them in the simulation program or configuration files. Each agent only exposes its functionality and fields that it needs other agents to be aware of. In addition, each agent may have a list of agents that need to be updated with it, in an Observer type of design pattern.
The inherent flexibility of this simulation, as well as its ability to run faster than real time while the same time making more productive use of the hardware than does the time-scale or real-time simulation makes it the key to efficient discrete-event simulation and the paradigm of choice for many analyses.
Any node-and-link model involves activities (akin to decision making) on nodes, connected by links. In some cases, such links will be physical; e.g., traffic simulation, where the highways will be represented by links, and nodes will correspond to intersections, stores, towns, etc. Traffic density, delays, link traversal times, link and node capacities would be the independent variables for the "provider" nodes and links and dependent variables for the "receiver" nodes and links.
In other cases, links are logical, belonging to the "IF...THEN...ELSE" category. Probability distributions of decisions at each node will be the metrics of interest in this case, along with the other parameters, like retention time at the node, link delay, etc.
A Closer Look at the Node-and-Link Model Structure from the Monte-Carlo Standpoint.
A traffic network model can just as well simulate a decision grid by introducing a virtual “crawler” parsing the network. By sending multiple crawlers down the network and simulating each crawler's retention times and decisions at each node, we will build the total distribution of the network latency.
The beauty of Monte-Carlo simulation is that it can do fast-time modeling, simulating the time faster than it happens in the model's real-world protagonist system.
It can be achieved in a number of ways, most popular of which are:
1. Real-time: when running human-in-the-loop simulations, with actual humans making some of the decisions, as well as in psychology and social sciences research, real-time Monte-Carlo situation is irreplaceable, as it allows subjects to make decisions in the actual tempo of the world they are used to. It is also very popular in the game business, with SimCity and Earthquake being among the earliest adopters of this approach, where the user is in control of the simulated world.
Interactive online games are the next step in the evolution of the real-time Monte-Carlo simulation, approach, where users are in control, and all the hundreds (thousands?) of users, by virtue of playing the game, become the simulation. The downside of using interactive-game environment in any research is that the number of users varies, and that will likely make any data collected from such a setup too noisy to be useful.
2. Time-scale: the simulated time delays are actually waited out on a scale by the modeling computer. This method allows building very high-fidelity event-and-process models; however, it may not be very efficient for modeling situations that take a long time to complete without much happening; e.g., a simulation of a day of operations of a police station in a quiet neighborhood of Beverly Hills, CA would be too boring to analyze and it would take way too long for any analyst's liking, even if the scale is 1:24, allowing a day in simulated time to pass in 1 hour or the simulation's runtime. Another drawback of time-scale simulations is in their dependency on the simulator running: a stoppage in the operation of the program software or hardware will cause a disconnect between the simulated time and real time, which time-scale modeling developers need to be aware of and account for in their disaster recovery and exception handling practices.
3. Fast-time: this is yet another change of paradigm with regard to what the nodes and links represent. (See illustration below)
Each crawler (aka Agent) knows what the timestamp of its next event will be. The event may be any change of the crawler's current state (spatial location, heading on the compass, number of friends on Facebook, job status, citizenship, oil pressure, speed, funding status, etc).
A master controller keeps the simulation time and a sorted collection of agents in the order of next event times. All agents act independently or in interaction with each other via the rules defined for them in the simulation program or configuration files. Each agent only exposes its functionality and fields that it needs other agents to be aware of. In addition, each agent may have a list of agents that need to be updated with it, in an Observer type of design pattern.
The inherent flexibility of this simulation, as well as its ability to run faster than real time while the same time making more productive use of the hardware than does the time-scale or real-time simulation makes it the key to efficient discrete-event simulation and the paradigm of choice for many analyses.
Subscribe to:
Posts (Atom)