The Monte Carlo (MC) method is the most common technique used for un- certainty quanti cation, due to its simplicity and good statistical results. However, its computational cost is extremely high, and, in many cases, pro- hibitive. Fortunately, the MC algorithm is easily parallelizable, which allows its use in simulations where the computation of a single realization is very costly. This work presents a methodology for the parallelization of the MC method, in the context of cloud computing. This strategy is based on the MapReduce paradigm, and allows an ecient distribution of tasks in the cloud. This methodology is illustrated on a problem of structural dynamics that is subject to uncertainties. The results show that the technique is ca- pable of producing good results concerning statistical moments of low order. It is shown that even a simple problem may require many realizations for convergence of histograms, which makes the cloud computing strategy very attractive (due to its high scalability capacity and low-cost). Additionally, the results regarding the time of processing and storage space usage allow one to qualify this new methodology as a solution for simulations that require a number of MC realizations beyond the standard. Keywords: uncertainty quanti cation, cloud computing, Monte Carlo method, parallel algorithm, MapReduce Corresponding author. Tel.:+55-21-3527-1500; e-mail: lopes@inf.puc-rio.br 1. Introduction Most of the predictions that are necessary for decision making in engineer- ing, economics, actuarial sciences, and so on., are made based on computer models. These models are based on assumptions that may or may not be in accordance with reality. Thus, a model can have uncertainties on its predic- tions, due to possible wrong assumptions made during its conception. This source of variability on the response of a model is called model uncertainty [1]. In addition to modeling errors, the response of a model is also subject to variabilities due to uncertainties on model parameters, which may be due to measurement errors, imperfections in the manufacturing process, and other factors. This second source of randomness on the models response is called data uncertainty [1]. One way to take into account these uncertainties is to use the theory of probability, to describe the uncertain parameters as random variables, ran- dom processes, and/or random elds. This approach allows one to obtain a model where it is possible to quantify the variability of the response. For instance, the reader can see from [2, 3] where techniques of stochastic model- ing are applied to describe the dynamics of a drillstring. Other applications in structural dynamics can be seen in [4, 5]. It is also worth mentioning the contributions of [6], in the context of hydraulic fracturing, [7], for estimation of nancial reserves, and in [8] for the analysis of structures built by heteroge- neous hyperelastic materials. For a deeper insight into stochastic modeling, with an emphasis in structural dynamics, the reader is encouraged to read [1, 9, 10]. To compute the propagation of uncertainties of the random parameters through the model, the most used technique in the literature is the Monte Carlo (MC) method [11]. This technique generates several realizations (sam- ples) of the random parameters according to their distributions (stochastic model). Each of these realizations de nes a deterministic problem, which is solved (processing) using a deterministic technique, generating an amount of data. Then, all of these data are combined through statistics to access the response of the random system under analysis [12, 13, 14]. A general overview of the MC algorithm can be seen in the Figure 1. The MC method does not require that one implements a new computer code to simulate a stochastic model. If a deterministic code to simulate a similar deterministic model is available, the stochastic simulation can be per- formed by running the deterministic program several times, changing only the 2 Monte Carlo method samples generation stochastic modelprocessing deterministic modeloutput data statisticsresponseFigure 1: General overview of Monte Carlo algorithm. parameters that are randomly generated. This nonintrusive characteristic is a great advantage of MC when compared with other methods for uncertainty quanti cation, such as generalized Polynomial Chaos (gPC), [15], which de- mands a new code for each new random system that one wants to simulate. Additionally, if the MC simulation is performed for a large number of sam- ples, it completely describes the statistical behavior of the random system. Unfortunately, MC is a very time-consuming method, which makes unfea- sible its use for complex simulations, when the processing time of a single realization is very large or the number of realizations to an accurate result is huge [12, 13, 14]. Meanwhile, the MC method algorithm can easily be parallelized because each realization can be done separately and then aggregated to calculate the statistics. The parallelization of the MC algorithm allows one to obtain sig- ni cant gains in terms of processing time, which can enable the use of the MC method in complex simulations. In this context, cloud computing can be a very fruitful tool to enable the use of the MC method to access complex stochastic models because it is a natural environment for implementation of parallelization strategies. Moreover, in theory, cloud computing o ers almost in nite scalability in terms of storage space, memory and processing capa- bility, with a nancial cost signi cantly lower than the one that is necessary to acquire a traditional cluster with the same capacity. In this spirit, this work presents a methodology for implementing the MC method in a cloud computing setting, which is inspired by the MapReduce 3 paradigm [16]. This approach consists of splitting, among several instances of the cloud environment, the MC calculation, processing each one of these tasks in parallel, and nally merging the results into a single instance to compute the statistics. As an example, the methodology is applied to a simple problem of stochastic structural dynamics. The use of cloud in not new in the context of engineering and sciences [17]. We would like to mention the work of Ari and Muhtaroglu [18] that proposes a cloud computing service for nite element analysis, the work of Jorissen et al. [19] that proposes a scienti c cloud computing platform that o ers high performance computation capability for materials simulations, and the work of Wang et al. [20] that discusses the Cumulus cloud based project with its applications to scienti c computing, just to cite a few. This paper is organized as follows. Section 2 makes a brief presentation of the cloud computing concept. Section 3 presents a parallelization strategy for the MC method in the context of cloud computing. Section 4 describes the case of study in which the proposed methodology is exempli ed. Section 5 presents and discusses the statistics done with the data and the convergence of the results. Finally, section 6 presents the conclusions and highlights the main contribution of this work. 2. Cloud computing Traditionally, the term cloud is a metaphor about the way the Internet is usually represented in network diagrams. In these diagrams, the icon of the cloud represents all the technologies that make the Internet work, ignor- ing the infrastructure and complexity that it includes. Likewise, the term cloud has been used as an abstraction for a combination of various computer technologies and paradigms, e.g., virtualization, utility computing, grid com- puting, service-oriented architecture and others, which together provide com- putational resources on demand, such as storage, database, bandwidth and processing [21]. Therefore, cloud computing can be understood as a style of computing where information technology capabilities are elastic, scalable, and are pro- vided as services to the users via the Internet [22, 23]. In this style of comput- ing, the computational resources are provided for the users on demand, as a pay-as-you-go business model, where they only need to pay for the resources that were e ectively used. Due to its great potential for solving practical problems of computing, it is recognized as one of the top ve emerging tech- 4 nologies that will have a major impact on the quality of science and society over the next 20 years [24]. The reader can see from [25] a detailed comparison between three cloud providers (Amazon EC2, Microsoft Azure and Rackspace) and a traditional cluster of machines. These experiments were done using the well-known NAS parallel benchmarks as an example of general scienti c application. That article demonstrates that the cloud can have a higher performance and cost eciency than a traditional cluster. Furthermore, a traditional cluster require huge investments in hardware and in their maintenance and one can not \turn o resources contracts", while they are unnecessary, to save money. Then, traditional clusters are almost prohibitive for scienti c research without large nancial resources. In a cloud computing environment one pays only per hour of use of one virtual machine. Other costs of this platform are the shared/redundant stor- age and data transfers. For the data transfer, all inbound data transfers (i.e., data going to the cloud) are free and the price for outbound data transfers (i.e., data going out of the cloud) is a small cost that depends on the volume of data transferred. Given these characteristics, it is easy to imagine a situation where compu- tational resources can be turned on and o according to demand, providing unprecedented savings compared with acquisition and maintenance of a tra- ditional cluster. In addition, if it is possible to parallelize the execution, the total duration of the process can be minimized using more virtual machines of the cloud. 3. Parallelization of Monte Carlo method in the cloud The strategy to run the MC algorithm in parallel, as proposed in this work is in uenced by the MapReduce paradigm [16], which was originally presented to support the processing of large collections of data in parallel and distributed environments. This paradigm consists in two phases: the rst (Map) divides the computational job into several partitions and each partition is executed in parallel by di erent machines; the second phase (Re- duce) collects the partial results returned by each machine, aggregates partial results and computes a response to the computational job. We propose a MapReduce strategy for parallel execution in the cloud of the MC method that is composed of three steps: split,process , and merge . The split and the process steps correspond to the Map, while the merge 5 corresponds to the Reduce step. This strategy of parallelization was im- plemented in a cloud computing setting called McCloud [26, 27], which runs on the Microsoft Windows Azure platform (http://www.windowsazure.com). A general overview of the strategy can be seen in Figure 2, and a detailed description of each step is made below. Figure 2: General overview of Monte Carlo parallelization strategy in the cloud. 3.1. Split First of all, the split step establishes the number of cloud virtual machines to be used and turns then on. Then, it divides a MC simulation with NMC realizations into tasks and puts them into a queue. Each one of these tasks is composed of an ensemble of Nserial realizations to be simulated. Thus, it is necessary to process a number of tasks equal to Ntasks =NMC=Nserial. These tasks are distributed in a uniform manner (approximately) among the virtual machines [26, 27]. It is important to note that the number of tasks and virtual machines in uences directly in the total simulation processing time and the nancial expenses of the cloud computing service. In the simulations above, the realizations of the random parameters are obtained by the use of a pseudorandom numbers generator. This generator deterministically constructs sequences of numbers indexed by the value of a seed, which emulates a set of random numbers. It happens that, if two instances of tasks have the same seed, they will generate the same sequence of random numbers. In this case, part of these results will be redundant at the end of the simulation. To avoid the possibility of repeated seeds, it is necessary to adopt a strategy of seed distribution among the virtual machines. This strategy must 6 generate one seed for each virtual machine, and guarantee that the sequence of random numbers generated in each one of these machines is di erent from the sequences generated on the other machines. There are several ways to de ne a distribution strategy and we will not discuss this in detail because it is quite simple. To see the strategy adopted in the example of section 5, the reader may consult [26, 27]. 3.2. Process The process step uses the available virtual machines to pick and process, in an asynchronous way, task by task in the queue. Thus, in theory, the execution is as fast as the number of virtual machines used. In practice, there is a limit to eciency gain because of the existence of overhead, such as input/output of data and managing parallelization. Thus, one of the challenges that must be solved for an ecient simulation, at a low-cost, is the determination of an optimal number of virtual machines to be used [26, 27]. Currently, this optimization process occurs empirically. However, in future works, we will seek to rationalize it, according to the nature of the simulations involved. At this step, there is a criterion of tolerance against failures. When a task is caught from the queue by a virtual machine, it has a time limit to be executed. If it is not performed in this time, it is put back into the queue for another virtual machine to try and run it. Thus, a hardware or machine communication problem does not overtake the execution of MC simulation. The output data generated by each executed task is saved onto the hard disk for subsequent post-processing. The total amount of storage space used by a MC simulation is proportional to the number of realizations. Therefore, this step also requires attention in terms of storage space usage because the demand for hard disk space may become unfeasible for a simulation with a large number of realizations. To reduce the storage space usage in the example of section 5, we chose to calculate the mean and standard deviation using the strategy of pair- wise parallel and incremental updates of the statistical moments described in [28], which uses the Welford-Knuth algorithm [29, 30]. Thus, for each executed task, instead of saving all the simulation data for subsequent cal- culation of the statistical moments, we save only the mean and the centered sum of squares. For the calculation of the histograms, the random variables of interest were identi ed before the processing step, and their realizations 7 were saved for being used in the histogram construction, during the post- processing step. This strategy is exempli ed in Figure 3, which shows the parallelization of a MC simulation, with 16 realizations, that aims to calcu- late the square of an integer random number between 0 and 9. Figure 3: Exempli cation of the strategy for parallel calculation of statistics. 3.3. Merge The merge step starts when the last task in a virtual machine nishes. This can occur in any virtual machine. This step reads, from the hard disk, all the information contained in the output data from the simulations, and combines them through statistics to obtain relevant information about the problem under analysis. At the end of this stage, the saved data are discarded and only the merged result is stored, to reduce future costs of data storage. 8 4. Case of study 4.1. Physical system The system of interest in this study case is an elastic bar xed at a rigid wall, on the left side, and attached to a lumped mass and two springs (one linear and one nonlinear), on the right side, such as illustrated in Figure 4. The stochastic nonlinear dynamics of this system was investigated in [31, 32, 33, 34], where the reader can see more details about the modeling procedure presented below. For simplicity, from now on, this system will be called the xed-mass-spring bar or simply the bar. xu(x, t) Lk kNLm Figure 4: Sketch of a bar xed at one end and attached to two springs and a mass on the other end. 4.2. Model equation The physical quantity of interest is the bar displacement eld u, which depends on the position xand the time t, and evolves, for all ( x;t)2(0;L) (0;T), according to the following hyperbolic partial di erential equation A@2u @t2+c@u @t=@ @x EA@u @x +f(x;t); (1) whereis mass density, Ais the cross section area, cis the damping coe- cient,Eis the elastic modulus, and fis a distributed external force, which depends on xandt. The boundary conditions for this problem are given by 9 u(0;t) = 0; (2) and EA@u @x(L;t) =ku(L;t)kNL u(L;t)3m@2u @t2(L;t); (3) wherekis the sti ness of the linear spring, kNLis the sti ness of the nonlinear spring, and mis the lumped mass. The initial position and the initial velocity of the bar are u(x;0) =u0(x); (4) and @u @t(x;0) =v0(x); (5) whereu0andv0are known functions of x, de ned for 0xL. 4.3. Discretization of the model equation To approximate the solution of the initial/boundary value problem given by Eqs.(1) to (5), we employ the Galerkin method [35]. This results in the following system of ordinary di erential equations [M]u(t) + [C]_u(t) + [K]u(t) =f(t) +fNL_u(t) ; (6) supplemented by the following pair of initial conditions u(0) = u0 and _ u(0) = v0; (7) where u(t) is the vector of RNin which the n-th component is the un(t), [M] is the mass matrix, [ C] is the damping matrix, and [ K] is the sti ness matrix. Additionally, f(t),fNL u(t) ,u0, and v0are vectors of RN, which respectively represent the external force, the nonlinear force, the initial po- sition, and the initial velocity. The initial value problem de ned by Eqs.(6) and (7) has its solution approximated by the Newmark method [36, 35]. 10 4.4. Stochastic model To introduce randomness in the bar model, we assume that the external forcefis a random eld proportional to a normalized Gaussian white noise. Moreover, the elastic modulus is assumed to be a random variable. The probability distribution of Eis characterized by its probability den- sity function (PDF) pE:(0;1)!R, which is speci ed, based only on the known information about this parameter, by the maximum entropy principle [37, 38, 39, 40]. The maximum entropy principle says that, among all the probability distributions consistent with the current known information of E, to choose the one that maximizes its entropy. Thus, to specify pE, it is necessary to maximize the entropy function S[pE] =Z1 0pE() ln pE() d; (8) subjected to the constraints (known information) imposed by Z1 0pE()d= 1; (9) E[E] =E<1; (10) and E ln (E) <1; (11) where E[] is the expected value operator, and Eis the mean value of E. Regarding the known information, the Eq.(9) is the normalization condi- tion of the random variable, the Eq.(10) means that the mean value of Eis known, and the Eq.(11) is a sucient condition to ensure that Uhave nite variance [37]. The desired distribution is the gamma, whose PDF is given by pE() =1(0;1)1 E 1 2 E! 1 2 E! 1 (1=2 E) E 1 2 E1! exp  2 EE! ; (12) 11 where the symbol 1(0;1)denotes the indicator function of the interval (0 ;1), Eis a dispersion factor, and the  indicates the gamma function. Due to the randomness of FandE, the displacement of the bar becomes a random eld U, which evolves according to the following stochastic partial di erential equation A@2U @t2+c@U @t=@ @x E()A@U @x +F(x;t; ): (13) The boundary conditions now read as U(0;t;) = 0; (14) and EA@U @x(L;t; ) =kU(L;t; )kNL U(L;t; )3m@2U @t2(L;t; );(15) for 0<t<T and2, while the initial conditions are U(x;0;) =u0(x); (16) and @U @t(x;0;) =v0(x); (17) for 0xLand2, where  denotes the sample space in which we are working. 5. Numerical experiments We employ the MC method in the cloud to approximate the solution of the stochastic initial/boundary value problem de ned by Eqs.(13) to (17). This procedure uses a sampling strategy with the number of realizations always being equal to a power of four. In this procedure, each realization of the random parameters de nes a new initial value problem given by Eqs.(6) and (7), which is solved deterministically as described in section 4.3. Then, these results are combined through statistics. The implementation of the MC method was conducted in MATLAB, with the aid of two executable les. The rst one, which is executed in each one 12 of the virtual machines, generates realizations of the random parameters and performs the determinist calculations to solve the associated variational problem. The other executable computes the statistics of the output data generated by the rst executable. 5.1. Probability density function A random variable is completely characterized by its PDF. The knowledge of the PDF allows us to obtain all the statistical moments of the random variable and to calculate the probability of any event associated with it. So, we start our analysis with the PDF estimation. The estimations for the PDF of the (normalized1) bar right extreme dis- placement for a xed instant of time, is shown in Figure 5 for di erent values of the total number of realizations in MC simulations. We can note that as the number of samples in the MC simulation increases, small di erences may be noted on the peaks of successive estimations of the PDF. We use a convergence criterion based on a residue of the random vari- ableU(L;T; ), de ned as the absolute value of the di erence between two successive approximations of pU(L;T;), i.e., RU(L;T;)= p4n U(L;T;)pn U(L;T;) ; (18) where the superscript nindicates the number of realizations in the MC sim- ulation. In this case, we say that the MC simulation reached a satisfactory result if this residue is less than a prescribed tolerance , i.e.,RU(L;T;)<  for all2. For instance, = 0:05. The reader can observe the distribution of the residue of U(L;T; ), for several values of MC realizations, in the Figure 6. Note that although the residue decreases with the increase of the MC realizations, only one simula- tion with 1;048;576 samples was able to ful ll the convergence criterion. Therefore, despite the number of samples used in the MC simulation is very high and the problem is relatively simple, the tolerance achieved was relatively low. It is common to observe in the literature some works that analyze problems much more complex, for instance [41, 42, 43], among many others, using some hundreds of samples. This example leads us to re ect about the number of realizations required to obtain statistical independence of the results. In this context, the use of 1By normalized we mean a random variable with zero mean and unit standard deviation 13 −4 −2 0 2 400.20.40.60.81 norm. displacement at x=Land t=Tprobability density function(a) 16 ;384 realizations −4 −2 0 2 400.20.40.60.81 norm. displacement at x=Land t=Tprobability density function (b) 65 ;536 realizations −4 −2 0 2 400.20.40.60.81 norm. displacement at x=Land t=Tprobability density function (c) 262 ;144 realizations −4 −2 0 2 400.20.40.60.81 norm. displacement at x=Land t=Tprobability density function (d) 1;048;576 realizations Figure 5: This Figure illustrates estimations for the PDF of the (normalized) random vari- ableU(L;T;), for di erent values of the total number of realizations in MC simulations: (a) 16;384 realizations, (b) 65 ;536 realizations, (c) 262 ;144 realizations and (d) 1 ;048;576 realizations. MC in a cloud computing setting appears to be a viable solution, able to make the work feasible at a low-cost. 5.2. Mean and standard deviation Figure 7 shows the evolution of the bar right extreme displacement mean (blue line) and an envelope of reliability (grey shadow) around it, obtained by adding and subtracting one standard deviation around the mean. This gure shows these graphs for di erent values of the total number of realizations in MC simulations. The rst conclusion we can draw from these results is that the low-order statistics, from the qualitative point of view, do not undergo major changes 14 −4 −2 0 2 400.050.10.150.20.250.3 norm. disp. at x=Land t=Tresidue of displ. PDF 65 536 262 144 1 048 576Figure 6: This gure illustrates the residue of the U(L;T;) PDF. when the total number of realizations is higher than 16 ;384. However, based on a purely visual analysis, we can not conclude anything quantitatively. To investigate the quantitative di erences on the results, we de ne the residue ofU(L;;) mean or standard deviation similarly to the one de ned to Eq.(18), by changing the PDF for the mean or standard deviation of U(L;;) only. Figure 8 illustrates the evolution of several residues of the U(L;;) mean, and Figure 9 illustrates the evolution of several residues of the U(L;;) stan- dard deviation. We note that, the logarithm of the mean value residues are almost always less than O(106), for the case of statistics with larger sam- ples, and presents an alternate behavior between large drops and climbs, (as seen in Figure 8). On the other hand, the logarithm of the standard devi- ation residue is greater than O(106) in the initial instants. This behavior is not maintained after 2 ms, when the residue curves keep their alternate behavior, but almost always below O(106), as shown in Figure 9. These results show that statistics of rst and second order may be obtained with great accuracy using the methodology presented in this work. 5.3. Costs analysis for the processing time In what follows we will present an evaluation of the time spent by MC simulations based on the number of realizations. All the simulations were performed only once, without discarding any samples. Also, 20 virtual ma- 15 0246810−600−400−2000200400600 time ( ms)displacement at x=L(µ m ) mean value mean ±std. dev.(a) 16 ;384 realizations 0246810−600−400−2000200400600 time ( ms)displacement at x=L(µ m ) mean value mean ±std. dev. (b) 65 ;536 realizations 0246810−600−400−2000200400600 time ( ms)displacement at x=L(µ m ) mean value mean ±std. dev. (c) 262 ;144 realizations 0246810−600−400−2000200400600 time ( ms)displacement at x=L(µ m ) mean value mean ±std. dev. (d) 1;048;576 realizations Figure 7: This Figure illustrates the mean value (blue line) and a con dence interval (grey shadow) with one standard deviation, of the random process U(L;;), for di erent values of the total number of realizations in MC simulations: : (a) 16 ;384 realizations, (b) 65 ;536 realizations, (c) 262 ;144 realizations and (d) 1 ;048;576 realizations. chines were used for the experiment, one for control and the other 19 for processing. Each task runned uses Nserial = 256. A comparison between the computational time spent by each one of the MC simulations in the cloud, and the corresponding speed-up factors com- pared with a serial simulation can be seen in the Table 1. In this table the columnNMCrepresents the total number of realizations of the experiment; the column tasks represents the number of tasks to be processed; the columns split,process andmerge represent the time, in milliseconds, consumed in each stage of our parallelization strategy; the column total represents, in minutes, the total time spent by the parallel MC simulation (split + process + merge); the column serial shows, in minutes, the processing time of a MC simulation 16 024681010−1210−1010−810−610−4 time ( ms)residue of disp. mean 65 536 262 144 1 048 576Figure 8: This gure illustrates the evolution of residue of the U(L;;) mean. 024681010−1210−1010−810−610−4 time ( ms)residue of disp. std. dev. 65 536 262 144 1 048 576 Figure 9: This gure illustrates the evolution of the residue of the U(L;;) standard deviation. for the same problem executed in serial; and the column speed-up shows a metric of the parallel simulation performance, de ned as the ratio between the serial and the total time of simulation. Before discussing the analysis of the results, we should indicate that the serial time, shown in the rst line of the Table 1, was obtained by extrapola- tion of the average processing time spent to run a single task in two virtual machines of the cloud. To obtain this average time the task was repeated 10 times (5 times in each VM). 17 Table 1: Comparison between the computational time spent (using 19 VMs) by each one of the MC simulations in the cloud, and the corresponding speed-up factors compared to a serial simulation. NMC tasks split process merge total serial speed-up (ms) (ms) (ms) (min) (min) 256 1 | 111 998 2 250 1.9 1.9 1.0 16 384 64 500 451 397 11 875 7.7 127.3 16.5 65 536 256 2 328 1 576 711 27 031 26.7 509.3 19.0 262 144 1024 7 609 6 078 757 89 450 102.9 2 037.0 19.8 1 048 576 4096 37 766 24 422 238 336 799 413.3 8 148.1 19.7 The rst thing that we can note in the Table 1 is that the computational cost of the split and merge tasks are almost negligible when compared to the time spent by the process. Hence the importance of adopting a strategy of parallelism for the processing step. Also, we can see that, in all of the experiments, the strategy of parallelism in the cloud provided performance gains, and such gains are greater as the number of realizations increases. This shows the eciency of our parallelization strategy in the case of study analyzed. Moreover, the speed-up observed is close to the number of virtual machines used, which indicates that the implementation of the McCloud setting is good. In order to evaluate the eciency of the parallelization done in the cloud, we studied how the processing time of the MC simulation, with 1 ;048;576 realizations, varies as a function of the number of virtual machines used to perform the task. As can be seen in the Table 2, the processing time decays monotonically as the number of VMs increases. This decreasing behavior is almost linear in logarithmic scale, as shown in the Figure 10, and indicates the e ectiveness of the parallelization of MC tasks in the cloud. The small deviations from the theoretical curve of parallelization, that can be seen in the Figure 10, are due to the management of tasks by the cloud. However, in the range analyzed, between 4 and 99 virtual machines, these performance losses are negligible and do not compromise the eciency of parallelization strategy. 18 Table 2: Comparison between the computational time spent (using 19 VMs) by each one of the MC simulations in the cloud, and the corresponding speed-up factors compared to a serial simulation. VMs split process merge total speed-up cost (ms) (ms) (ms) (min) (US$) 4 37 734 117 637 861 431 691 1968.5 4.0 17.15 5 34 062 99 041 631 354 791 1657.2 4.7 18.23 6 37 923 78 040 047 343 105 1307.0 6.0 17.39 7 36 982 66 989 658 348 603 1122.9 7.0 17.63 8 27 390 58 431 244 349 099 980.1 8.0 18.11 9 29 407 51 818 238 343 720 869.9 9.0 18.11 10 28 015 46 564 270 332 119 782.1 10.0 18.83 11 28 734 42 192 535 334 432 709.3 11.0 17.99 12 27 687 38 611 499 341 308 649.7 12.0 18.11 13 34 874 36 039 896 334 806 606.8 12.9 19.55 14 36 359 33 412 517 338 696 563.1 13.9 19.31 15 36 499 31 199 806 343 874 526.3 14.8 18.83 16 38 576 29 215 641 338 014 493.2 15.8 20.03 17 40 484 27 406 752 340 522 463.1 16.8 19.19 18 39 015 25 800 653 335 214 436.3 17.9 20.27 19 37 766 24 422 238 336 799 413.3 18.9 19.07 29 29 282 16 000 466 343 036 272.9 28.6 21.71 39 29 547 11 927 263 346 594 205.1 38.0 24.23 60 31 547 7 891 904 327 392 137.5 56.7 29.63 80 25 328 5 900 347 33 709 99.3 78.5 29.63 99 29 578 4 834 623 340 015 86.7 89.9 36.47 Table 2 also shows that the speed-up increases monotonically as the num- ber of VMs grows. This behavior can be better appreciated in the Figure 11, where the reader can verify that the values obtained for the speed-up are very close to the theoretical values, that would be obtained if there were no delays due to cloud management. The reader can note, also, that the mea- sured values The corresponding to larger numbers of VMs (60, 80 and 99) are farther away from the theoretical reference. This occurs by the accumulation 19 100101102101102103104 number of virtual machinesCPU time (min) cloudtheoreticalFigure 10: CPU time of a MC simulation, with 1 048 576 realizations, as function of the numbers of virtual machines. of management delays, which are larger for a higher amount of VMs. 5.4. Costs analysis for the storage space A comparison between the storage space used by each one of the MC sim- ulations in the cloud, and the nancial cost associated with each simulation can be seen in Table 3. In this table the column space represents the total storage space, in MB, temporarily used by the simulation, and the column cost represents the cost of this experiment in US dollars. Observing the data in Table 3 we can see that our parallelization strategy used fairly little storage space, even for a large number of MC realizations. Additionally, the nancial cost, even for the most complex simulation, is very small; which is a major advantage when compared to the costs of acquiring and maintaining a traditional cluster. 20 100101102100101102 number of virtual machinesSpeed-up measuredtheoreticalFigure 11: Speed-up of a MC simulation, with 1 048 576 realizations, as function of the numbers of virtual machines. Table 3: Comparison between the storage space used by each one of the MC simulations in the cloud, and the nancial cost associated with each simulation. NMC space cost (MB) (US$) 16 384 12.4 5.39 65 536 49.0 5.39 262 144 195.2 7.67 1 048 576 780.8 19.07 6. Concluding remarks We present a strategy for parallelizing the Monte Carlo method in the context of cloud computing, using the fundamental idea of the MapReduce 21 paradigm. This strategy is described in detail and illustrated in the simula- tion of a simple problem of stochastic structural dynamics. The simulation results show good accuracy for low-order statistics, low storage space usage, and that the performance gains increase with the number of Monte Carlo realizations. It was also illustrated that even a simple problem can require many realizations for the convergence of histograms, which makes the cloud computing strategy very attractive, due to its high scalability capacity and low-cost. Thus, this article demonstrates that the advent of cloud comput- ing can become an important enabler for the adoption of the MC method to compute the propagation of uncertainty in complex stochastic models. Acknowledgments The authors are indebted to the Brazilian agencies CNPq, CAPES, and FAPERJ for the nancial support given to this research. By the free use of the Windows Azure platform, the authors are very grateful to Microsoft Corporation. Also, they wish to thank the anonymous referee, for useful comments and suggestions.