Techniques to manage virtual classes for statistical tests

Techniques to manage virtual classes for statistical tests are described. An apparatus may comprise a simulated data component to generate simulated data for a statistical test, statistics of the statistical test based on parameter vectors to follow a probability distribution, a statistic simulator component to simulate statistics for the parameter vectors from the simulated data with a distributed computing system comprising multiple nodes each having one or more processors capable of executing multiple threads, the simulation to occur by distribution of portions of the simulated data across the multiple nodes of the distributed computing system, and a distributed control engine to control task execution on the distributed portions of the simulated data on each node of the distributed computing system with a virtual software class arranged to coordinate task and sub-task operations across the nodes of the distributed computing system. Other embodiments are described and claimed.

BACKGROUND

In some cases, a computer system may be used to perform statistical tests. This decision is normally a function of, in part, a size of a data set needed to perform a given statistical test. Even a moderately complex statistical test may require a massive data set, sometimes on the order of terabytes for example, to produce sufficiently accurate results.

SUMMARY

Various embodiments are generally directed to techniques to perform automated statistical testing. Some embodiments are particularly directed to techniques to determine statistical significance of test results from a statistical test using a distributed processing system. In one embodiment, for example, an apparatus may comprise processor circuitry, and a simulated data component operative on the processor circuitry to generate simulated data for a statistical test, statistics of the statistical test based on parameter vectors to follow a probability distribution. The apparatus may further comprise a statistic simulator component operative on the processor circuitry to simulate statistics for the parameter vectors from the simulated data with a distributed computing system comprising multiple nodes each having one or more processors capable of executing multiple threads, the simulation to occur by distribution of portions of the simulated data across the multiple nodes of the distributed computing system. The apparatus may further comprise a distributed control engine operative on the processor circuitry to control task execution on the distributed portions of the simulated data on each node of the distributed computing system with a virtual software class arranged to coordinate task and sub-task operations across the nodes of the distributed computing system. Other embodiments are described and claimed.

DETAILED DESCRIPTION

In statistics, a result is considered statistically significant if, for example, it has been predicted as unlikely to have occurred by chance alone, according to a pre-determined threshold probability, referred to as a significance level. A statistical test is used in determining what outcomes of a study would lead to a rejection of a null hypothesis for a pre-specified level of significance. A null hypothesis refers to a default position, such as there is no relationship between two measured phenomena, for example, that a potential medical treatment has no effect. Statistical significance is instructive in determining whether results contain enough information to cast doubt on the null hypothesis.

Various embodiments described and shown herein are generally directed to techniques to perform enhanced automated statistical testing. Some embodiments are particularly directed to an automated statistical test system arranged to determine statistical significance of test results from a statistical test. In one embodiment, for example, the automated statistical test system may include a simulation subsystem and a statistical test subsystem. The simulation subsystem may, among other features, generate an approximate probability distribution for the statistics of a statistical test. The statistical test subsystem may, among other features, generate statistical significance values for results of a statistical test using an approximate probability distribution. Embodiments are not limited to these subsystems.

A procedure is here, and generally, conceived to be a self-consistent sequence of operations leading to a desired result. These operations are those requiring physical manipulations of physical quantities. Usually, though not necessarily, these quantities take the form of electrical, magnetic or optical information capable of being stored, transferred, combined, compared, and otherwise manipulated. It proves convenient at times, principally for reasons of common usage, to refer to this “information” as bits, values, elements, symbols, characters, terms, numbers, or the like. It should be noted, however, that all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to those quantities.

FIG. 1illustrates a block diagram for an automated statistical test system100. In one embodiment, the automated statistical test system100may be implemented as a computer system having a simulation subsystem120and a statistical test subsystem140. The subsystems120,140may each be implemented as a separate or integrated software application comprising one or more components, such as components122-aas shown for the simulation subsystem120inFIG. 1. Although the automated statistical test system100shown inFIG. 1has a limited number of elements in a certain topology, it may be appreciated that the automated statistical test system100may include more or less elements in alternate topologies as desired for a given implementation.

It is worthy to note that “a” and “b” and “c” and similar designators as used herein are intended to be variables representing any positive integer. Thus, for example, if an implementation sets a value for a=4, then a complete set of components122-amay include components122-1,122-2,122-3and122-4. The embodiments are not limited in this context.

In various embodiments, portions of the automated statistical test system100may be implemented as software components comprising computer executable instructions implemented in a given programming language. In one embodiment, for example, the computer executable instructions may be implemented in a specific programming language as developed by SAS® Institute, Inc., Cary, N.C. For instance, the computer executable instructions may be implemented in a procedure referred to herein as HPSIMULATE, which is a procedure suitable for execution within a SAS programming language and computing environment. In such embodiments, the computer executable instructions may follow syntax and semantics associated with HPSIMULATE, as described in more detail with reference toFIG. 34, infra. However, embodiments are not limited to HPSIMULATE, and further, do not need to necessarily follow the syntax and semantics associated with HPSIMULATE. Embodiments are not limited to a particular type of programming language.

As shown inFIG. 1, the automated statistical test system100may include two subsystems, a simulation subsystem120and a statistical test subsystem140. The simulation subsystem120may generate a computational representation130arranged to generate approximate probability distribution132for a statistical test114. The statistical test subsystem140may generate statistical significance values for results of the statistical test114using an approximate probability distribution132generated by the computational representation130.

The simulation subsystem120may be generally arranged to perform a statistical simulation for a variety of statistical tests114. The statistical test114may include any known statistical test as represented by the statistical test function112. Some examples for the statistical test114may include without limitation median test, mode test, R test, means test, t-test for single means, independent t-test, dependent t-test, Wald-Wolfowitz runs test, Kolmogorov Smirnov test, Mann-Whitney U test, sign test, Wilcoxon matched pairs test, alternative to one-way between-groups analysis of variance (ANOVA) test, one-way ANOVA test, Kruskal-Wallis ANOVA test, repeated measures ANOVA test, Friedman ANOVA test, Kendall Concordance test, Pearson product moment correlation test, Spearman correlation test, linear regression test, data mining decision tree tests, neural network tests, nonlinear estimation test, discriminant analysis test, predictor importance test, KPSS unit root test, Shin cointegration test, ERS unit root test, Bai and Perron's multiple structural change tests (e.g., maxF, UDmaxF, WDmaxF, supFl+1|l, etc.), Im, Pesaran and Shin (2003) panel unit root test, Bhargava, Franzini and Narendranathan (1982) test, generalized Durbin-Watson statistics, generalized Berenblut-Webb statistics for first-order correlation in a fixed effects model, Gourieroux, Holly and Monfort (1982) test for random effects (two way), Johansen's cointegration rank test, and many others. Embodiments are not limited in this context.

The simulation subsystem120may be arranged to generate an approximate probability distribution, probability distribution function, or distribution function (collectively referred to herein as an “approximate probability distribution”) for the statistics of a statistical test114. A probability distribution assigns a probability to each measurable subset of possible outcomes of a random experiment, survey, or procedure of statistical inference. A probability distribution can either be univariate or multivariate. A univariate distribution gives the probabilities of a single random variable taking on various alternative values. A multivariate distribution gives probabilities of a random vector (e.g., a set of two or more random variables) taking on various combinations of values.

More particularly, a statistical test114is normally based on a “test statistic.” In statistical hypothesis testing, a hypothesis test is typically specified in terms of a test statistic, which is a function of the sample. A test statistic is considered as a numerical summary of a data-set that reduces the data to one value that can be used to perform a hypothesis test. In general, a test statistic is selected or defined in such a way as to quantify, within observed data, behaviors that would distinguish the null from the alternative hypothesis where such an alternative is prescribed, or that would characterize the null hypothesis if there is no explicitly stated alternative hypothesis.

An important property of a test statistic is that its sampling distribution under the null hypothesis must be calculable, either exactly or approximately, which allows p-values to be calculated. A test statistic is a function of associated data and a model. Under the assumptions of a null hypothesis and the model the test statistic has an associated “sampling distribution.” A sampling distribution refers to a probability distribution for values of the test statistic over hypothetical repeated random samples of the data, for random data samples having the probability distribution assumed for the data by the model and null hypothesis.

In one embodiment, for example, the simulation subsystem120attempts to determine and approximate a sampling distribution of a test statistic under an assumed null hypothesis to generate an approximate probability distribution. The simulation subsystem120determines an approximate probability distribution for a given set of statistics of a statistical test114. It is worthy to note that in some embodiments when an approximate probability distribution is said to be associated with a given statistical test114, it implies that the approximate probability distribution is associated with a set of statistics for the statistical test114rather than the statistical test114alone.

In various embodiments, a probability distribution may have a “known form” and/or an “unknown form.” A probability distribution of a “known form” means that the analytical formula of the cumulative distribution function (CDF) of the distribution can be efficiently computed, for example, the CDF is a closed-form expression, or the CDF can be well approximated in a numerical method. A probability distribution of an “unknown form” means that the analytical formula of the CDF of the distribution is unavailable, or cannot be efficiently computed or approximated by any known numerical method. Accordingly, the probability distribution of an “unknown form” is to be evaluated through simulation.

In various embodiments, the simulation subsystem120may be arranged to generate a probability distribution for the statistics of a given statistical test having a known form and/or an unknown form. In one embodiment, for example, a probability distribution for the statistics of a given statistical test114is a known form, such as a Gaussian distribution, a log-normal distribution, a discrete uniform distribution, a continuous uniform distribution, and many others. However, the statistics of some statistical tests114may follow a probability distribution of unknown form. In such cases, a probability distribution of unknown form may be approximated through empirical measure. An empirical measure is a random measure arising from a particular realization of a (usually finite) sequence of random variables. As such, in another embodiment, the simulation subsystem120may generate an approximate probability distribution132for the statistics of a given statistical test114where a probability distribution for the statistics of the statistical test is an unknown form. This may be particularly useful in those cases where the statistics of a statistical test114follow a probability distribution for which no known mathematical formula is available to compute its values and which therefore can only be evaluated through simulation.

The simulation subsystem120may receive as input a simulated data function110arranged to generate simulated data for a given statistical test114. The simulation subsystem120may further receive as input a statistical test function112arranged to perform the statistical test114. The simulation subsystem120may execute the simulated data function110to generate simulated data for the statistical test114, and the statistical test function112to simulate statistics from the simulated data, and create a computational representation130to generate an approximate probability distribution132from the simulated statistics. The computational representation130may, for example, be used by another software program at some future time to perform an actual statistical test114, such as a statistical test subsystem140. The statistical test subsystem140may, for example, perform the statistical test114on actual data sets (e.g., organization data, business data, enterprise data, etc.), and generate statistical significance values utilizing one or more approximate probability distributions132generated by the computational representation130.

Examples for an approximate probability distribution132may include without limitation an empirical distribution function or empirical CDF. An empirical CDF is a cumulative distribution function associated with an empirical measure of a sample. The simulation subsystem120may generate other approximate probability distributions132as well using the techniques described herein. The embodiments are not limited in this context.

The simulation subsystem120may generate an approximate probability distribution132for the statistics of a statistical test114where an actual probability distribution for the statistics of the statistical test114is of a known or unknown form. For example, when a statistical test114has a probability distribution of a known form, the approximate probability distribution132may be useful to evaluate or refine the known probability function. In another example, when the statistics of a statistical test114follow a probability distribution of an unknown form, the approximate probability distribution132may be useful to generate statistical significance values for a statistical test114. The latter example may be particularly useful in those cases where a statistical test114has a level of complexity that makes manual estimation of an approximate probability distribution132untenable.

The simulated subsystem120may comprise a simulated data component122-1. The simulated data component122-1may be generally arranged to generate simulated data for a statistical test114utilizing the simulated data function110. The simulated data function110may be stored as part of a software library. In this way, the simulated data component122-1may generate many different types of simulated data for a given statistical test114, without having to alter or modify instructions for the simulated data component122-1. Alternatively, the simulated data function110may be integrated with the simulated data component122-1. The simulated data component122-1may be described in more detail with reference toFIG. 3, infra.

The simulated subsystem120may comprise a statistic simulator component122-2. The statistic simulator component122-2may be generally arranged to simulate statistics for the statistical test114from the simulated data utilizing the statistical test function112. As with the simulated data function110, the statistical test function112may be stored as part of a software library. In this way, the statistic simulator component122-2may simulate many different types of statistical tests114with a given set of simulated data, without having to alter or modify instructions for the statistic simulator component122-2. Alternatively, the statistical test function112may be integrated with the statistical simulator component122-2. The statistic simulator component122-2may be described in more detail with reference toFIG. 4, infra.

The simulated data function110and the statistical test function112may be dependent or independent with respect to each other. In one embodiment, the simulated data function110and the statistical test function112may be complementary, where a simulated data set is specifically tuned for a given statistical test114. In one embodiment, the simulated data function110and the statistical test function112may be independently designed.

The statistic simulator component122-2may include a simulation control engine124. In one embodiment, the simulation control engine124may be generally arranged to control simulation operations across a distributed computing system. A distributed computing system may comprise, for example, multiple nodes each having one or more processors capable of executing multiple threads, as described in more detail with reference toFIG. 6, infra.

The use of a distributed computing system to generate simulated statistics may be useful for statistical tests114that need a larger data set. While simulating a statistic for one specific parameter vector may be relatively easy, simulating statistics for all possible parameter vectors could be computational intensive. As such, a distributed computing system may reduce simulation time.

The simulation control engine124may distribute portions of simulated data or simulated statistics across multiple nodes of the distributed computing system in accordance with a column-wise or a column-wise-by-group distribution algorithm, for example. The use of a distributed computing system in general, and the column-wise or column-wise-by-group distribution algorithm in particular, substantially reduces an amount of time needed to perform the simulation. In some cases, an amount of time needed to perform a simulation may be reduced by several orders of magnitude (e.g., years to days or hours), particularly with larger data sets (e.g., terabytes) needed for even moderately complex statistical tests. The simulation control engine124may be described in more detail with reference toFIG. 5, infra.

The simulation subsystem120may comprise a code generator component122-3. The code generator component122-3may be generally arranged to create a computational representation130. The computational representation130may be arranged to generate an approximate probability distribution132for the statistics of a statistical test114on a parameter vector from the simulated statistics. The code generator component122-3may be described in more detail with reference toFIG. 19, infra.

The computational representation130may be created as any software component suitable for execution by a processor circuit. Examples for the computational representation130may include without limitation a function, procedure, method, object, source code, object code, assembly code, binary executable file format, simple executable (COM) file, executable file (EXE), portable executable (PE) file, new executable (NE) file, a dynamic-link library (DLL), linear executable (LX) file, mixed linear executable (LE) file, a collection of LE files (W3) file, a compressed collection of LE files (W4) file, or other suitable software structures. The computational representation130may be generated in any computer programming language. Embodiments are not limited in this context.

The simulated subsystem120may comprise an evaluation component122-4. The evaluation component122-4may be generally arranged to evaluate a computational representation130for performance. For instance, the evaluation component122-4may receive a computational representation130arranged to generate an approximate probability distribution132for the statistics of the statistical test114on a parameter vector from the simulated statistics. The computational representation130may include a simulated data structure with information for one or more estimated CDF curves. The evaluation component122-4may perform at least two kinds of evaluations on the computational representation130.

A first type of evaluation is a performance evaluation. The direct evaluation attempts to determine whether the computational representation130performs according to a defined set of criteria. If the computational representation130does not meet one or more of the defined set of criteria, the evaluation component122-4may determine whether points should be added to the simulated data structure to improve performance of the computational representation130.

A second type of evaluation is a reduction evaluation. As with the performance evaluation, the reduction evaluation may attempt to determine whether the computational representation130performs according to a defined set of criteria. If the computational representation130does meet one or more of the defined set of criteria, the evaluation component122-4may further determine whether points can be removed from the simulated data structure to give a same or similar level of performance. Removing points from the simulated data structure may reduce a data storage size for the simulated data structure, and a data storage size for a corresponding computational representation130having the reduced simulated data structure.

When reduction is possible, the evaluation component122-4may attempt to reduce a data storage size for a computational representation130. The evaluation component122-4may evaluate the simulated data structure to determine whether any points in the grid of points is removable from the simulated data structure given a target level of precision. The evaluation component122-4may reduce the simulated data structure in accordance with the evaluation to produce a reduced simulated data structure, the reduced simulated data structure to reduce a data storage size for the computational representation130. In some cases, the reduced simulated data structure may be obtained by lowering a level of precision for the reduced simulated data structure relative to the original simulated data structure. The evaluation component122-4may be described in more detail with reference toFIG. 22, infra.

FIG. 2illustrates one example of a logic flow200. The logic flow200may be representative of some or all of the operations executed by one or more embodiments described herein, such as the simulation subsystem120of the automated statistical test system100.

In the illustrated embodiment shown inFIG. 2, the logic flow200may generate simulated data for a statistical test, the statistics of the statistical test based on parameter vectors to follow a probability distribution of a known or unknown form at block202. For example, the simulated data component122-1may generate simulated data for a statistical test114, while the statistics of the statistical test114based on parameter vectors follow a probability distribution of a known or unknown form. The simulated data component122-1may generate the simulated data with a simulated data function110. In one embodiment, for example, the simulated data function110may be designed to generate simulated data for a multiple structural change (maxF) test.

The logic flow200may simulate statistics for the parameter vectors from the simulated data, each parameter vector to be represented with a single point in a grid of points at block204. For example, the statistic simulator component122-2may receive simulated data from the simulated data component122-1, and simulate statistics for a statistical test114with a statistical test function112. In one embodiment, for example, the statistical test function112may be designed to implement a multiple structural change (maxF) test.

The statistic simulator component122-2may simulate statistics for one or more parameter vectors of the statistical test, each parameter vector to comprise a single point in a grid of points. The statistic simulator component122-2may simulate statistics for all given parameter vectors (p) for a statistical test (T) from the simulated data. The statistics of the statistical test T based on a given parameter vector p follow some probability distribution (D). The simulation subsystem120may approximate D with simulation. For any given parameter vector p, the statistic simulator component122-2can randomly draw a sample X={Xi}i=1Nfrom D and construct an approximate probability distribution132in the form of an empirical CDF {tilde over (T)}(p,x). The empirical CDF {tilde over (T)}(p,x) may have a level of precision as measured by a Kolmogorov-Smirnov statistic shown in Equation (1) as follows:

N⁢supx⁢T~⁡(p,x)-T⁡(p,x)∼KEquation⁢⁢(1)
where T(p,x) represents a true unknown CDF, and distribution K is a Kolmogorov distribution and a table of the distribution shows K(3) of almost 1. In accordance with Equation (1), the empirical CDF {tilde over (T)}(p,x) may have a precision of approximately 1/√{square root over (N)} and in almost all cases below 3/√{square root over (N)}, where N is the sample size, or the number of simulated statistics, for the given parameter vector p. For example, when N=1,000,000, the precision is about 0.001.

As the statistic simulator component122-2may utilize various interpolation techniques to generate approximate probability distributions132for one or more parameter vectors for a statistical test114, each parameter vector may be referred to as a “point” in a grid of points (M) used for interpolation. In this context, for example, the term “point” is a mathematical point within a defined problem space. In one embodiment, for instance, the problem space may comprise a “parameter space” for a statistical test114, with the parameter space made up of a given set of parameter vectors for the statistical test114. In other words, a specific value of a parameter vector is a point in the “parameter space” of a mathematical problem. If elements of one or more parameter vectors (e.g., the parameters of the problem) are plotted on Cartesian coordinates, then the parameter vector may be mapped to a point on a graph in a conventional manner.

The logic flow200generates quantiles for each point in the grid of points at block208. For example, the statistic simulator component122-2may generate quantiles for each point in the grid of points. Quantiles may refer to data values taken at regular intervals from the cumulative distribution function (CDF) of a random variable. The data values may mark boundaries between consecutive data subsets of an ordered set of data.

The logic flow200involves fitting an estimated CDF curve for each point in the grid of points independently from other points in the grid of points using a number of curve parameters to provide a given level of precision at block210. For example, the statistic simulator component122-2may fit an estimated CDF curve for each point in the grid of points independently from other points in the grid of points using a number of curve parameters to provide a given level of precision. Fitting an estimated CDF curve for each point independently can significantly reduce computational resources needed for curve-fitting operations. For instance, in a simple case, the dimension of the point, p, is only 1; that is to say, p is a real number. Rather than fitting estimated CDF curves for all points in the grid of points simultaneously to build an actual three-dimensional surface, (p,x,{tilde over (T)}(p,x)), the statistic simulator component122-2fits an estimated curve, (x,{tilde over (T)}(p,x)), for each point p in sequence or parallel, and then combines the estimated curves to form an approximate three-dimensional surface. Although the approximate three-dimensional surface may have a reduced level of precision relative to the actual three-dimensional surface, curve-fitting operations are greatly accelerated and may consume fewer computational resources. Reducing latency may be of particular importance with larger data sets or multi-dimensional parameter vectors needed for some statistical tests.

The statistic simulator component122-2may fit an estimated CDF curve for each point in the grid of points using various types of curve-fitting techniques. For instance, the statistic simulator component122-2may utilize, for example, a Gaussian mixture model (EM algorithm), a Bernstein-Polynomials mixture model (EM algorithm), or a monotone cubic spline technique. In one embodiment, the statistic simulator component122-2may perform curve-fitting utilizing a monotonic cubic spline interpolation technique with beta transformation, as described in more detail with reference toFIG. 18, infra. Embodiments are not limited to this example.

The logic flow200may generate a computational representation as source code to interpolate an estimated CDF curve for any point of the statistical test at block212. For example, the code generator component122-3may generate a computational representation130as source code to interpolate an estimated CDF curve for any given point of the statistical test114. In one embodiment, the point may be within the grid of points. In one embodiment, the point may be outside the grid of points. In one embodiment, the point may be entirely disassociated from the grid of points.

In one embodiment, the computational representation130may be generated in computer programming language, such as C or C++ for example. However, embodiments are not limited to these particular computer programming languages.

The logic flow200may reduce a data storage size for the computation representation at block214. For example, the evaluation component122-4may reduce a data storage size for the computational representation130through reduction of various components of the computational representation130, with a corresponding loss in precision. In one embodiment, the data reduction operations may be described in more detail with reference toFIG. 22, infra. Embodiments are not limited to this example.

The logic flow200involves controlling task execution of a distributed computing system using a virtual software class at block216. For example, the simulation control engine124of the statistic simulator component122-2may control task execution of a distributed computing system using a virtual software class. In addition, a virtual software class may also be used for other operations of the logic flow200, including without limitation blocks202,208,210,212and214, for example. A virtual software class may be described in more detail with reference toFIG. 5, infra.

FIG. 3illustrates an example of an operational environment300. The operational environment300may illustrate operation of portions of the automated statistical test system100, such as the simulated data component122-1, for example.

As shown inFIG. 3, the simulated data component122-1may have a simulated data generator320. In addition to, or as an alternative of, receiving a simulated data function110, the simulated data generator320may receive a structured input file310and a randomizer function312. The structured input file310may have definitions to generate simulated data330. The randomizer function312may generate seeds or random numbers (e.g., a random number generator) for the simulated data330. The simulated data generator320may utilize the simulated data function110, the structured input file310, and/or the randomizer function312to generate the simulated data330. The simulated data generator320may store the simulated data330in a simulation database340. In one embodiment, for example, the simulated data330may be stored in the simulation database340in accordance with definitions provided by the structured input file310.

The structured input file310may generally comprise one or more input files with data generation specifications and definitions useful for the simulated data component122-1to automatically producing simulated data330. The specifications and definitions may be in addition to, or replacement of, specifications and definitions used by the simulated data function110. The structured input file310may utilize any format as long as the input files are structured in a known and well-defined manner. The structured input file310provides information about the simulated data330and the simulation database340, among other types of information. For instance, the structured input file310may provide information about a computing environment in which the simulation subsystem120will run, a database to store the simulated data330, data structures for the simulated data330, table space (e.g., table, columns, rows, indices, etc.), the type of simulated data330required by each column of output tables in the simulation database340, how to generate each type of simulated data330, relationships between columns in a same table and columns in different tables, and other information pertinent to generating simulated data330.

A particular number of data sets for the simulated data330may be dependent, in part, on a particular type of statistical test114. In one embodiment, for example, assume the statistical test function112is designed to implement a multiple structural change (maxF) test. For example, in order to have a 3-digit precision, the simulated data generator320may need to generate a sufficient number of data sets to calculate approximately 1,000,000 statistics for each point in a defined grid of points.

FIG. 4illustrates an example of an operational environment400. The operational environment400may illustrate the operation of portions of the automated statistical test system100, such as the statistic simulator component122-2, for example.

As shown inFIG. 4, the statistic simulator component122-2may include a simulated statistic generator420. The simulated statistic generator420may receive simulated data330generated by the simulated data component122-1, and use (e.g., call) the statistical test function112to generate a set of simulated statistics430for a statistical test114with the simulated data330. As with the simulated data330, the simulated statistics430may be stored in the simulation database340, or a separate database entirely.

The statistic simulator component122-2may generate the simulated statistics430in different ways using various types of computer systems, including a centralized computing system and a distributed computing system. The statistic simulator component122-2may specify and control a particular computer system used for simulation through the simulation control engine124.

The statistic simulator component122-2may generate the simulated statistics using an exemplary procedure, as follows:

FIG. 5illustrates an example of an operational environment500. The operational environment500may illustrate operation of portions of the automated statistical test system100, such as the simulation control engine124of the statistical simulator component122-2, for example.

As shown inFIG. 5, the simulation control engine124may include a message interface520. The message interface520may receive the simulated data330from the simulated data component122-1, or retrieve the simulated data330from the simulation database340, and generate a simulation request530. The simulation request530may be a request to generate simulated statistics430from the simulated data330using the statistical test function112.

The simulation request530may include various types of information about the statistical test114, as well as information about a computing environment suitable for generating the simulated statistics430. Examples of computing environment information may include without limitation a name, description, speed requirements, power requirements, operating system requirements, database requirements, computing parameters, communications parameters, security parameters, and so forth. Depending on a particular statistical test114, the computing environment information may specify a configuration for a computer system having different combinations of computation resources, such as a number of servers, server types, processor circuits, processor cores, processing threads, memory units, memory types, and so forth. For example, the computer environment information may request a single computer with a single processor and a single thread, a single computer with a single processor and multiple threads, a single computer with multiple processors (or processing cores) each with a single thread, a single computer with multiple processors (or processing cores) each with multiple threads, multiple computers each with a single processor and a single thread, multiple computers each with a single processor and multiple threads, multiple computers with multiple processors each with a single thread, and multiple computers with multiple processors each with multiple threads, or any combination thereof.

A computing environment for a statistical test simulation may be particularly important when a simulation for a particular statistical test needs a larger set of data, such as in the gigabyte or terabyte range. Enumeration of all possible points could lead to a relatively large grid of points M. Continuing with our previous example of a multiple structural change (maxF) test, in order to have 3-digit precision, the simulated data generator320may need to generate a sufficient number of data sets to simulate approximately 1,000,000 statistics for each point in a defined grid of points. Assuming a number of variables is limited to less than 20, a possible number of structural changes is limited to less than 19, and a number of observations is 2,000 to approximate an asymptotic case, a defined grid of points for the maxF test would contain approximately 103,780 points (parameter vectors). To simulate 1,000,000 statistics for each of 103,780 points on a single processor, at roughly 0.001 seconds per statistic, would take approximately 1,200 days. Alternatively, executing 1,000,000 statistics for each of 103,780 points on 1200 processors, at roughly 0.001 seconds per statistic, would take approximately 1 day. For a computational task of this size, the message interface520may generate a simulation request530with computer environment information specifying a need for distributed computations in a distributed computing environment having multiple computers with multiple processors each with multiple threads operating in a parallel processing manner.

In one embodiment, the simulation control engine124may distribute portions of the simulated data330across various parts of a distributed computing environment, and control generation of simulated statistics430within the distributed computing environment, through use of one or more software classes522-v. In object-oriented programming, a software class may be referred to as an extensible template for creating objects, providing initial values for state (e.g., member variables) and implementations of behavior (e.g., member functions, methods). In many computer programming languages, a class name may be used as a name for a class (e.g., the template itself), the name for the default constructor of the class (e.g., a subroutine that creates objects), and as the type of objects generated by the type. Typically, when an object is created by a constructor of the class, the resulting object may be called an instance of the class, and the member variables specific to the object may be called instance variables, to contrast with the class variables shared across the entire class.

As shown inFIG. 5, the software classes522-vare specifically designed to perform simulations of a statistical test114in a distributed computing environment. The software classes522-vmay include at least a base software class522-1for a statistical test114and a virtual software class522-2for managing the simulation of a statistical test. In one embodiment, for example, a base software class522-1may be implemented as a TK-extension class. In one embodiment, for example, a virtual software class522-2may be implemented as a virtual TK-extension class (TKVRT). Embodiments, however, are not limited to these examples.

The base software class522-1may include an extensible template to create objects, provide initial values for states, and implementations of behavior for use by a software module to perform a statistical test. The virtual software class522-2may include an extensible template to create objects, provide initial values for states, and implementations of behavior for use by the separate software module having a base software class522-1for the statistical test, the base software class522-1to comprise a child of the virtual software class522-2. The virtual software class522-2may be used to extend the base software class522-1when used with a particular computing system, such as a distributed computing system. This allows standard statistical test code using the base software class522-1to take advantage of parallel processing algorithms implemented by the distributed computing environment, without having to make modifications to the base software class522-1. The software classes522-vmay be described in more detail with reference toFIGS. 8-11, infra.

FIG. 6illustrates a diagram for a computing system600. The computing system600may be representative of a computing system suitable for implementing the automated statistical test system100.

As shown inFIG. 6, the computing system600includes a computing environment606designed for processing large amounts of data for many different types of applications, such as for scientific, technical or business applications that require a greater number of computer processing cycles. The computing environment606may include different types of computing systems, such as a centralized computing system608and a distributed computing system610. Client devices602-1,602-2, through602-ecan interact with the computing environment606through a number of ways, such as over a network604, where e may be any positive integer. The network604may comprise a public network (e.g., the Internet), a private network (e.g., an intranet), or some combination thereof.

One or more data stores660are used to store the data to be processed by the computing environment606as well as any intermediate or final data generated by the computing system in non-volatile memory. However in certain embodiments, the configuration of the computing environment606allows its operations to be performed such that intermediate and final data results can be stored solely in volatile memory (e.g., RAM), without a requirement that intermediate or final data results be stored to non-volatile types of memory (e.g., disk).

This can be useful in certain situations, such as when the computing environment606receives ad hoc queries from a user and when responses, which are generated by processing large amounts of data, need to be generated on-the-fly (e.g., in real time). In this non-limiting situation, the computing environment606is configured to retain the processed information within memory so that responses can be generated for the user at different levels of detail as well as allow a user to interactively query against this information.

A client device602-emay implement portions of the automated statistical test system100, such as the simulation subsystem120, for example. When the simulation subsystem120executes, and the statistic simulator component122-2initiates simulation operations, the simulation control engine124of the statistic simulator component122-2may generate a simulation request530and send the simulation request530to the computing environment606via the network604. The computing environment606may receive the simulation request530, and when the simulation request530indicates a need for centralized computations, the computing environment606may forward the simulation request to the centralized computing system608for simulation operations. When the simulation request530indicates a need for distributed computations (e.g., parallel processing operations), the computing environment606may forward the simulation request530to the distributed computing system610for simulation operations. The computing systems608,610may be integrated with, or capable of interaction with, a database management system (DBMS)612used to control and manage interaction with the data stores660. The data stores660may include, for example, the simulation database340, as well as other data needed for a given simulation.

FIG. 7illustrates a diagram of a distributed computing system610. The distributed computing system610may include one or more client devices, such as client device602, control node702and one or more work nodes704-1through704-f, where f may be any positive integer. The control node702and worker nodes704-1through704-fmay have any of the computer system configurations as described with reference toFIG. 5.

The statistic simulator component122-2may simulate statistics with the distributed computing system610via the simulation control engine124. In one embodiment, the distributed computing system610may comprise multiple data processing nodes each having multi-core data processors, with at least one of the data processing nodes designated as a control data processing node (“control node”) and multiple data processing nodes designated as worker data processing nodes (“worker node”).

The client device602may couple to a central process, or control node702, which, in turn, is coupled to one or more worker nodes704-1through704-f. In general, each of the nodes of the distributed computing system610, including the control node702, and worker nodes704-1through704-f, may include a distributed computing engine (DCE)706that executes on a data processor associated with that node and interfaces with buffer memory708also associated with that node. The DCE706may comprise an instance of the distributed computing engine124of the statistical simulator component122-2of the simulation subsystem120. Each of the nodes may also optionally include an interface to the DBMS612and the data stores660, or local implementations of both (not shown).

In various embodiments, the control node702may manage operations in one or more of the worker nodes704-1through704-f. More particularly, the control node702may be arranged to receive and process a simulation request530from the client device602when distributed computations are to be performed with data stored in one or more of the worker nodes704-1through704-f.

In various embodiments, one or more of the components of distributed computing system610may be collocated, including the client device602, control node702, and one or more worker nodes704-1through704-f. However, more generally, none of the components of distributed computing system610need be collocated. Furthermore, in some embodiments, more than one node of the distributed computing system610may be arranged to assume the role of the control node. Thus, in some scenarios, the component designated as the control node702may assume the role of a worker node, while one of the worker nodes704-1to704-fmay assume the role of the control node702.

In various embodiments, in operation a simulation request530may be received by the control node702to simulate data and/or statistics for a statistical test, as described previously with respect toFIG. 1. For example, the client device602may generate a simulation request530to perform a statistical test simulation, which is processed by the control node702to construct work requests to be performed by one or more worker nodes704-1through704-f.

In particular embodiments, a simulation request530generated by client device602may be received with a name for the distributed computing system610to process the simulation request530. Accordingly, when the distributed computing system610is designated, the simulation request530is transmitted to control node702.

Consistent with the present embodiments, when the control node702receives a simulation request530sent from the client device602, the control node702may unpack the simulation request530, parse the simulation request530, and establish a flow of execution steps to perform an operation such as an simulating statistics using one or more worker nodes704-1through704-fof the distributed computing system610.

As illustrated inFIG. 7, the distributed computing system610may further include a communication protocol such as the message passing interface (MPI)710. When the control node702establishes a flow of execution for a simulation request530, the control node702may distribute the execution steps to worker nodes704-1to704-fvia the message passing interface710. Subsequently, results may be returned from one or more worker nodes704-1to704-fto the control node702via the message passing interface710.

In various embodiments, each of multiple worker nodes704-1to704-fmay contain a respective partition of data to be processed according to the compute request. The control node702may establish an execution flow in which messages are sent to multiple different worker nodes704-1to704-f. Each worker node704-1to704-fmay subsequently load and execute a specified simulation function for the partition of data contained by that worker node.

When each of the worker nodes704-1to704-f, that receives a message to execute a simulation function from control node702, completes execution of its specified simulation function on its partition of data, the one or more worker nodes704-1through704-fmay return results to the control node702through the message passing interface710. The results may subsequently be returned from the control node702to the client device602that generated the simulation request530.

AlthoughFIG. 7illustrates a distributed database network that comprises a control node702and multiple worker nodes704-f, more general embodiments include any network in which an interface is provided so that a client device may initiate the execution of a compute request within a group of foreign machines, utilize resources of the foreign machines, including memory, input/output functionality, loading of images, launching of threads, and/or utilize a distributed database structure to send and receive message instructions and results.

FIG. 8illustrates one example of a logic flow800. The logic flow800may be representative of some or all of the operations executed by one or more embodiments described herein, such as the statistical simulator component122-2of the simulation subsystem120of the automated statistical test system100.

In the illustrated embodiment shown inFIG. 8, the logic flow800may generate simulated data for a statistical test, the statistics of the statistical test based on parameter vectors to follow a probability distribution of a known or unknown form at block802. For example, the simulated data component122-1may generate simulated data330for a statistical test114, the statistical test114based on parameter vectors (points) to follow a probability distribution.

The logic flow800may simulate statistics for the parameter vectors from the simulated data with a distributed computing system comprising multiple nodes each having one or more processors capable of executing multiple threads, the simulation to occur by distribution of portions of the simulated data across the multiple nodes of the distributed computing system at block804. For example, the simulated data generator320of the statistic simulator component122-2may simulate statistics for parameter vectors from the simulated data330, where each parameter vector to comprise a single point in a grid of points. The simulation may be performed using a distributed computing system610comprising a control node702and one or more worker nodes704-1through704-f, each having one or more processors capable of executing multiple threads. The simulation may occur by distribution of portions of the simulated data330across the control node702and the one or more worker nodes704-1through704-fof the distributed computing system610.

The logic flow800may control task execution on the distributed portions of the simulated data on each node of the distributed computing system with a virtual software class arranged to coordinate task and sub-task operations across the nodes of the distributed computing system at block806. For example, the simulation control engine124of the statistical simulator component122-2may control task execution to simulate statistics430from the distributed portions of the simulated data330on each control node702and one or more worker nodes704-1through704-fof the distributed computing system610with a virtual software class522-2arranged to assist in coordinating task and sub-task operations across the control node702and the one or more worker nodes704-1through704-fof the distributed computing system610.

FIG. 9illustrates one example of a logic flow900. The logic flow900may be representative of some or all of the operations executed by one or more embodiments described herein, such as the simulation control engine124of the statistical simulator component122-2of the simulation subsystem120of the automated statistical test system100, on the distributed computing system610. More particularly, logic flow900illustrates the simulation control engine124creating an instance of a virtual software class522-2on one or more nodes of the distributed computing system610.

In some cases, simulation tasks may be implemented by control node702and one or more worker nodes704-1through704-farranged in soloist architecture or a general/captain architecture. In a soloist architecture, simulations may be performed by a centralized computing system608. In a general/captain architecture, simulations may be performed by a distributed computing system610, where a control node702is designated as a general node, and one or more worker nodes704-1through704-fmay be designated as captain nodes.

As shown inFIG. 9, the logic flow900may perform initializing and parsing operations at block902. A call to an instance of software class tksimDoAnalysis may be made to initiate task analysis at block904. A subroutine named DoAnalysis(.) to perform the task analysis may be executed at block906. Control is passed at point A.

When in a general/captain mode, control is passed at point B to the general node, a subroutine for task initialization may be executed at block910. At general start, a subroutine named ManageInformation(.): Message Loop may be executed at block912. A test whether the task is analysis is performed at diamond914. If the test is not passed, various clean up procedures are called and general processing terminates. If the test is passed, subroutines TaskManager(.), Zathread(.), Launcher(.) and DoAnalysis(.) are executed in a recursive manner at block916. Control is passed at point C. Control is returned to the general node at point D.

The ManageInformation(.): Message Loop executed at block912may broadcast instructions to one or more captain nodes. The captain nodes perform operations similar to the general node for portions of the simulation. For instance, at captain start, an initialization may be executed at block918and a subroutine named ManageInformation(.): Message Loop may be executed at block920. A test whether the task is analysis is performed at diamond922. If the test is not passed, various clean up procedures are called and captain processing terminates. If the test is passed, subroutines TaskManager(.), Zathread(.), Launcher(.) and DoAnalysis(.) are executed in a recursive manner at block924. Control is passed at point E. Control is returned to the captain node at point F.

FIG. 10illustrates one example of a logic flow1000. The logic flow1000may be representative of some or all of the operations executed by one or more embodiments described herein, such as the simulation control engine124of the statistical simulator component122-2of the simulation subsystem120of the automated statistical test system100. More particularly, the logic flow1000interoperates with the logic flow900at the various control locations A-F.

As shown in the logic flow1000, when control is passed at control location A from the logic flow900, a determination is made as to whether task analysis is to be performed in a soloist architecture or a general/captain architecture at diamond1032. If a soloist architecture, then subroutines CreateParentTKVRTInstance(.) and tkvrtGridInitialize(.) are executed at block1036. A loop starts to execute subroutines ExecuteTheThreads(str, TASK_ANALYSIS) and tkvrtGridSummarize(.) at block1038. Control is passed at point A. If not a soloist architecture, then a determination is made as to whether task analysis is to be performed in a general/captain architecture at diamond1034. If a general/captain architecture, then control is passed at control location B to the logic flow900.

When control is passed at control location C from the logic flow900, the general node may execute a subroutine GridTask(str, TASK_ANALYSIS) at block1040, a subroutine MPI_Bcast(TASK_ANALYSIS) at block1042, and a CreateParentTKVRTInstance(.) and tkvrtGridInitialize(.) at block1044. A loop starts to execute subroutines ExecuteTheThreads(str, TASK_ANALYSIS) and tkvrtGridSummarize(.) at block1046. Once the loop completes, the general node executes a subroutine MPI_Bcast(TASK_LOCALSTOP,.) at block1048. Parameters TASK_ANALYSIS and/or TASK_LOCALSTOP are passed to the block1050, and control is passed at control location D to the logic flow900.

Certain subroutines executed by the general node are designed to interoperate with subroutines executed by the captain node to coordinate completion of tasks and sub-tasks. For instance, when the general node executes subroutines CreateParentTKVRTInstance(.) and tkvrtGridInitialize(.) at block1044, and the loop at block1046, messages and parameters may be exchanged in similar subroutines executed by the captain node at corresponding blocks1056,1058, respectively, to coordinate task and sub-task completion. Such communication between general node and captain nodes may be necessary for some complex algorithms; however, for algorithms in which the tasks and sub-tasks are independent, no such communication is needed and execution cost is saved.

When control is passed at control location E from the logic flow900, the captain node may start a loop to execute subroutines GridTask(str, TASK_UNKNOWN) and MPI_Bcast(task,.) at block1050. A determination is made as to whether analysis is complete at diamond1052using the TASK_ANALYSIS parameter. If the TASK_ANALYSIS parameter is evaluated as TRUE, the subroutines at blocks1056,1058are executed, and control is passed back to block1050. If the TASK_ANALYSIS parameter is evaluated as FALSE, a determination is made as to whether a local stop has occurred at diamond1054using the TASK_LOCALSTOP parameter. If the TASK_LOCALSTOP parameter is evaluated as TRUE, control is passed at control location F. If the TASK_LOCALSTOP parameter is evaluated as FALSE, control is passed back to block1050.

FIG. 11illustrates one example of a logic flow1100, which shows how to finish the tasks and sub-tasks in parallel in the multithread environment. The logic flow1100may be representative of some or all of the operations executed by one or more embodiments described herein, such as the simulation control engine124of the statistical simulator component122-2of the simulation subsystem120of the automated statistical test system100. More particularly, the logic flow1100illustrates certain operations for subroutines executed at blocks1038,1046and1058of the logic flow1000.

As shown in the logic flow1100, when the subroutine ExecuteTheThreads(.) is executed at blocks1038,1046and1058of the logic flow1000, thread execution1170executes subroutines InitializeParentThread(.) and tkvrtInitialize(parentInst) at block1172. The thread execution1170then starts a Loop for all child to execute subroutines threadsInitializeChildThreads(.) and tkvrtInitialize(childInst) at block1174. The thread execution1170then starts an event loop to execute subroutines InitializeChildThreads(.) and tkvrtInitialize(childInst) at block1176. The thread execution1170then executes subroutines AccumulateChildThreads(.) and tkvrtSummarize(parentInst) at block1178.

In one embodiment, the simulation control engine124may control thread execution1170for each control node702and worker nodes704-1through704-fof the distributed computing system610with a various instances of a virtual software class522-2. The virtual software class522-2may be arranged to control task operations across the control node702and worker nodes704-1through704-fof the distributed computing system610while reducing dependency between tasks and sub-tasks. The logic flow1100illustrates an example for a virtual software class522-2called TKVRT extension1180.

In various embodiments, the simulation control engine124may pass or receive one or more virtual software class parameters for each instance of a virtual software class, the one or more parameters comprising at least one of input/output parameters, input/output tables, or a pointer to list all instances of virtual software class parameters. For instance, with respect to TKVRT extension1180, the simulation control engine124may pass or receive one or more virtual software class parameters for each instance of TKVRT, including tkvrtParmsPtr, input/output parameters, input/output tables, and a pointer to list all instances of tkvrtParmPtrs at block1182. The TKVRT extension1180may also include several subroutines as used in logic flow900,1000.

In one embodiment, the simulation control engine124may initialize a parent thread with parent parameters with a first instance of the virtual software class TKVRT extension1180, which includes tkvrtinitialize(parentinst) as shown in block1184.

In one embodiment, the simulation control engine124may initialize a child thread with child parameters with a first instance of the virtual software class TKVRT extension1180, which includes tkvrtinitialize(childinst) as also shown in block1184.

In one embodiment, the simulation control engine124may analyze work results of a child thread with a second instance of the virtual software class TKVRT extension1180, which includes tkvrtAnalyze(childInst) as shown in block1186.

In one embodiment, the simulation control engine124may summarize work results of a child thread to a parent thread with a third instance of the virtual software class TKVRT extension1180, which includes tkvrtSummarize(parentInst) as shown in block1188.

In one embodiment, the simulation control engine124may initialize a grid with parent parameters with a fourth instance of the virtual software class TKVRT extension1180, which includes tkvrtGridInitialize(parentInst) as shown in block1190.

In one embodiment, the simulation control engine124may summarize a grid with parent parameters with a fifth instance of the virtual software class TKVRT extension1180, which includes tkvrtGridSummarize(parentInst) as shown in block1192.

It may be appreciated that these are merely a few example subroutines for the TKVRT extension1180, and others exist as well. Embodiments are not limited in this context.

FIG. 12illustrates one example of a logic flow1200. The logic flow1200may be representative of some or all of the operations executed by one or more embodiments described herein, such as the simulation control engine124of the statistical simulator component122-2of the simulation subsystem120of the automated statistical test system100. More particularly, the logic flow1200illustrates distribution algorithms for use with the distributed computing system610.

As shown inFIG. 12, the logic flow1200may generate simulated data for a statistical test, the statistics of the statistical test based on parameter vectors to follow a probability distribution at block1202. For example, the simulated data component122-1may generate simulated data330for a statistical test114, the statistics of the statistical test114based on parameter vectors to follow a probability distribution of a known or unknown form.

The logic flow1200may simulate statistics for the parameter vectors from the simulated data, each parameter vector to comprise a single point in a grid of points, with a distributed computing system comprising multiple nodes each having one or more processors capable of executing multiple threads, the simulation to occur through distribution of portions of the simulated data or simulated statistics across the multiple nodes of the distributed computing system in accordance with a column-wise or column-wise-by-group distribution algorithm at block1204. For example, the simulated statistic generator420of the statistic simulator component122-2may simulate statistics for the parameter vectors from the simulated data330. Each parameter vector for the statistical test114may comprise a single point in a grid of points, with the grid of points to be used for interpolation. The simulation may be performed with a distributed computing system610comprising control node702and worker nodes704-1through704-f. Each of control node702and worker nodes704-1through704-fmay have one or more processors capable of executing multiple threads. The simulation control engine124of the statistic simulator component122-2may control simulation of the statistical test114by distributing portions of the simulated data330and/or simulated statistics430across the control node702and worker nodes704-1through704-fof the distributed computing system610in accordance with a column-wise or column-wise-by-group distribution algorithm. A column-wise or column-wise-by-group distribution algorithm may be described in more detail with reference toFIGS. 13-17, infra.

The logic flow1200may create a computational representation arranged to generate an approximate probability distribution for each point in the grid of points from the simulated statistics, the approximate probability distribution to comprise an empirical cumulative distribution function (CDF) at block1206. For example, the code generator component122-3may create a computational representation130, such as a DLL file. The computational representation130may be arranged to generate an approximate probability distribution132for each point in the grid of points from the simulated statistics430. The approximate probability distribution132may comprise an empirical CDF, for example.

FIG. 13illustrates an example of a simulated data structure1300. The simulated data structure1300may be a software data structure arranged to store simulated data330and/or simulated statistics430in the simulation database340.

The statistic simulator component122-2may generate the simulated data structure1300. In one embodiment, the statistic simulator component122-2may generate the simulated data structure1300as a table. The simulated data structure1300may include an ordered arrangement of rows1302-gand columns1304-hto form multiple cells1306-i, where g, h and i may be any positive integer. A cell1306-imay contain a simulation of a simulated statistic430(or simulated data330) for a point in the grid of points, where each row1302-grepresents a simulation of the simulated statistic430(or simulated data330), and each column1304-hrepresents a point in the grid of points.

When populated, the simulated data structure1300may have a defined data storage size for a given statistical test114. For instance, with the maxF test, the simulated data structure1300may comprise 1,000,000 rows and 103,780 columns, which gives the simulated data structure1300a data storage size of approximately 800 Gigabytes (GB).

FIG. 14illustrates an example of an operational environment1400. The operational environment1400shows distributing portions of the simulated data structure1300as column-based work units for the distributed computing system610.

The simulation control engine124of the statistic simulator component122-2may control simulation of the statistical test114by distributing portions of the simulated data structure1300across the control node702and worker nodes704-1through704-fof the distributed computing system610in accordance with a column-wise distribution algorithm. For instance, the simulation control engine124may distribute the simulated data structure1300by column across multiple worker nodes704-1through704-fof the distributed computing system610.

The DCE706of the control node702may distribute one or more columns1304-hof the simulated data structure1300to one or more worker nodes704-1through704-fvia the message passing interface710. As shown inFIG. 14, the DCE706may distribute columns1304-1,1304-2. . .1304-hof the simulated data structure1300as work units to the worker nodes704-1,704-2. . .704-f, respectively. A worker node may process its assigned work unit, such as sorting each column1304-hand/or calculating quantiles for the statistical test114. The worker nodes704-1through704-fmay pass their processed work units, or pointers to the processed work units, to the DCE706via the message passing interface710. The DCE706may reassemble the processed work units into an output file to form a new version of the simulated data structure1300.

In one embodiment, the new version of the simulated data structure1300may include an ordered arrangement of rows and columns, each row to represent a point in the grid of points and each column to represent a quantile for each point in the grid of points. In the case where the worker nodes704-1through704-fare tasked to calculate quantiles for the statistical test114, the worker nodes704may pass back a defined number of quantiles as established for the statistical test114. For instance, with the maxF test, the original simulated data structure1300may comprise 1,000,000 rows and 103,780 columns, which gives the original simulated data structure1300a data storage size of approximately 800 Gigabytes (GB). Assume the worker nodes704-1through704-fare to calculate 10,001 quantiles for the maxF test. In this case, the new simulated data structure1300may comprise 10,001 columns and 103,780 rows, which gives the new simulated data structure1300a reduced data storage size of approximately 8 GB.

In one embodiment, the statistic simulator component122-2may generate quantiles using the distributed computing system610in accordance with an exemplary procedure, as follows:

FIG. 15illustrates an example of a simulated data structure1500. The simulated data structure1500may be a software data structure arranged to store simulated data330and/or simulated statistics430in the simulation database340.

The statistic simulator component122-2may generate the simulated data structure1500. In one embodiment, the statistic simulator component122-2may generate the simulated data structure1500as a table. The simulated data structure1500may include an ordered arrangement of rows1502-jand columns1504-kto form multiple cells1506-m, where j, k and m may be any positive integer. A cell1506-mmay contain a simulation of a simulated statistic430(or simulated data330) for a point in the grid of points, where each row1502-jrepresents a simulation of the simulated statistic430(or simulated data330), and each column1504-krepresents a point in the grid of points. Additionally, the simulated data structure1500may be organized into column groups1508-n, where n may be any positive integer. For instance, a first column group1508-1may include six columns for parameter vector4, and a second column group1508-2may include five columns for parameter vector5, and so forth.

As with simulated data structure1300, the simulated data structure1500may have a defined data storage size for a given statistical test114. For instance, with the maxF test, the simulated data structure1500may comprise 1,000,000 rows and 103,780 columns, which gives the simulated data structure1500a data storage size of approximately 800 Gigabytes (GB).

FIG. 16illustrates an example of an operational environment1600. The operational environment1600shows distributing portions of the simulated data structure1500as column-group-based work units for the distributed computing system610.

The simulation control engine124of the statistic simulator component122-2may control simulation of the statistical test114by distributing portions of the simulated data structure1500across the control node702and worker nodes704-1through704-fof the distributed computing system610in accordance with a column-wise-by-group distribution algorithm. For instance, the simulation control engine124may distribute the simulated data structure1500by groups of columns (or column groups) across multiple worker nodes704-1through704-fof the distributed computing system610. Distributing the simulated data structure1500may make it easier to calculate the simulated statistic430for each point in the grid of points relative to the column-wise distribution algorithm.

The simulation control engine124may perform column group distribution according to column groups1508-ndefined in a control row of the simulated data structure1500. The control row may include various identifiers or parameters to control distribution. In one embodiment, for example, the control row may include a group identifier to identify corresponding columns in a group, a restriction identifier to identify corresponding columns that do not need to be distributed, and a universal identifier to identify corresponding columns that need to be distributed across all worker nodes. It may be appreciated that other identifiers and parameters may be used as desired for a given implementation. Embodiments are not limited in this context.

The DCE706of the control node702may distribute one or more column groups1508-nof the simulated data structure1500to one or more worker nodes704-1through704-fvia the message passing interface710. As shown inFIG. 16, the DCE706may distribute columns1508-1,1508-2. . .1508-nof the simulated data structure1500as work units to the worker nodes704-1,704-2. . .704-f, respectively. A worker node may process its assigned work unit, such as calculating the statistics for the statistical test114, based on the column groups, and then calculating quantiles for the statistical test114. The worker nodes704-1through704-fmay pass their processed work units, or pointers to the processed work units, to the DCE706via the message passing interface710. The DCE706may reassemble the processed work units into an output file to form a new version of the simulated data structure1500.

In one embodiment, the new version of the simulated data structure1500may include an ordered arrangement of rows and columns, each row to represent a point in the grid of points and each column to represent a quantile for each point in the grid of points. In the case where the worker nodes704-1through704-fcalculate quantiles for the statistical test114, as with the simulated data structure1300, the worker nodes704-1through704-fmay pass back a defined number of quantiles as established for the statistical test114. For instance, with the WDmaxF test, the original simulated data structure1500may comprise 1,000,000 rows and 103,780 columns of maxF test statistics, which gives the original simulated data structure1500a data storage size of approximately 800 Gigabytes (GB). Assume the worker nodes704-1through704-fare to calculate 10,001 quantiles for the WDmaxF test. In this case, the new simulated data structure1500may comprise 10,001 columns and 103,780 rows, which gives the new simulated data structure1500a reduced data storage size of approximately 8 GB.

FIG. 17illustrates an example of a simulated data structure1700. The simulated data structure1700may illustrate an example of the new versions of the simulated data structures1300,1500. As described with reference toFIGS. 13-16, new versions of the simulated data structures1300,1500may each include an ordered arrangement of rows1702-pand columns1704-q, where p and q may be any positive integer. Each row1702-pto represent a point in the grid of points and each column1704-qto represent a quantile of the grid of points. In various embodiments, cell1706-rmay contain a simulation of a simulated statistic for a point in the grid of structure1700. Simulated data structure1700is transposed relative to the simulated data structures1300,1500, in that the simulated data structures1300,1500have columns representing points in a grid of points, while the simulated data structure1700has columns representing quantiles.

FIG. 18illustrates one example of a logic flow1800. The logic flow1800may be representative of some or all of the operations executed by one or more embodiments described herein, such as the statistic simulator component122-2of the simulation subsystem120of the automated statistical test system100. More particularly, the logic flow1800illustrates curve fitting algorithms for use with a grid of points.

As shown inFIG. 18, the logic flow1800may generate simulated data for a statistical test, statistics of the statistical test based on parameter vectors to follow a probability distribution at block1802. For example, the simulated data component122-1may generate simulated data330for a statistical test114, the statistical test114based on parameter vectors to follow a probability distribution of known or unknown form. Alternatively, the simulated data component122-1may receive simulated data330for a statistical test114from an external source.

The logic flow1800may simulate statistics for the parameter vectors from the simulated data, each parameter vector to comprise a single point in a grid of points at block1804. For instance, the statistic simulator component122-2may generate simulated statistics430for the parameter vectors from the simulated data330, each parameter vector to comprise a single point in a grid of points.

The logic flow1800may calculate quantiles for the parameter vectors from the simulated data at block1806. For instance, the statistic simulator component122-2may calculate quantiles saved in the simulated data structure1700for the parameter vectors from the simulated data330.

The logic flow1800may fit an estimated CDF curve to quantiles for each point in the grid of points using a monotonic cubic spline interpolation technique in combination with a transform to satisfy a defined level of precision at block1808. For instance, the statistic simulator component122-2may construct an estimated CDF curve for each point in the grid of points using a monotonic cubic spline interpolation technique in combination with a transform to interpolate quantiles in the simulated data structure1700in order to satisfy a precision level of interest.

Once the simulation control engine124generates the simulated data structure1700with quantiles for the statistical test114, the statistic simulator component122-2may use the quantiles to fit an estimated CDF curve for each point in the grid of points. The statistic simulator component122-2may fit an estimated CDF for each point according to a given level of precision. In general, reducing a level of precision results in a corresponding reduction in a number of curve parameters needed to fit the estimated CDF curve.

As previously described with reference toFIG. 2, the statistic simulator component122-2may simulate statistics for all given parameter vectors (p) for a statistical test (T) from the simulated data330. In accordance with Equation (1), the empirical CDF {tilde over (T)}(p,x) may have a precision of approximately 1/√{square root over (N)}, where N is the sample size, or the number of simulated statistics, for the given parameter vector p. For example, when N=1,000,000, the precision is about 0.001. However, the statistic simulator component122-2may generate an estimated CDF curve with much fewer curve parameters than N.

The statistic simulator component122-2may select a number of curve parameters to fit an estimated CDF curve for each point in the grid of points to provide a given level of precision. For instance, assume that a precision level is set as 0.0005, and that a monotonic cubic spline interpolation technique is used to fit the curve. On average, approximately 20 curve parameters can achieve a curve C(c(p),.) as set forth in Equation (2), as follows:

In some cases, however, a number of curve parameters may be reduced through combination of a monotonic cubic spline interpolation technique and a transform. In one embodiment, for example, the statistic simulator component122-2may combine a monotonic cubic spline interpolation technique with a beta transformation. A beta transformation is a transform performed in accordance with a normalized incomplete beta function, the normalized incomplete beta function comprising a nonnegative function whose derivative is completely positive. In one embodiment, a beta function may comprise a CDF of a beta distribution. A beta distribution is a family of continuous probability distributions defined on the interval [0, 1] parameterized by two positive shape parameters, denoted by α and β, that appear as exponents of the random variable and control the shape of the distribution.

Assume the monotonic cubic spline interpolation technique fits a first estimated CDF curve with a first number of knots to give a first level of precision (0.0005), each knot comprising an x value and a y value for a two-dimensional coordinate system. The monotonic cubic spline interpolation technique spaces the x values at regular intervals along the x-axis as it is monotonic. As such, more knots are needed to accurately fit the curve. The monotonic cubic spline interpolation technique may be combined with a beta transformation to transform the x values to reduce the first number of knots to a second number of knots that gives approximately the first level of precision (0.0005), where the second number of knots is lower than the first number of knots. Applying the beta transformation causes the x values to be placed at irregular intervals, which reduces the number of knots.

Combining a monotonic cubic spline interpolation technique with a transform, such as the beta transformation, results in fewer curve parameters needed for a same or similar level of precision. For instance, in the previous example, the use of the monotonic cubic spline interpolation technique reduced a number of curve parameters from 1,000,000 simulated statistics to approximately 20 curve parameters. By combining the monotonic cubic spline interpolation technique with a beta transformation, the number of curve parameters may be further reduced from 20 curve parameters to 12 curve parameters, for a same or similar level of precision (e.g., 0.0005).

Once a number of curve parameters are selected, the statistic simulator component122-2may fit an estimated CDF curve for each point in the grid of points independently from other points in the grid of points using the selected number of curve parameters to provide a given level of precision. Fitting an estimated CDF curve for each point independently significantly reduces computational resources needed for curve-fitting operations. For instance, in a simple case that the point is one dimensional, rather than fitting estimated CDF curves for all points in the grid of points simultaneously to build an actual three-dimensional surface, the statistic simulator component122-2fits an estimated curve for each point in sequence or parallel, and then combines the estimated curves to form an approximate three-dimensional surface.

Once curve-fitting operations are finished, the statistic simulator component122-2may generate a simulated data structure with information for a set of fitted CDF curves for the grid of points. Continuing with the maxF test example, the simulated data structure may have a data storage size calculated as 8 GB/10,001*12=10 megabytes (MB). As indicated with the maxF test example, a data storage size for each version of a simulated data structure reduces from 800 GB to 8 GB to 10 MB. This results in a significantly smaller data storage size needed for the computational representation130.

In one embodiment, the statistic simulator component122-2may perform curve-fitting operations in accordance with the following exemplary procedure:

FIG. 19illustrates an operational environment1900. The operational environment1900shows operations for the code generator component122-3to generate interpolation code to interpolate statistics for a statistical test114.

The simulated data component122-1may generate simulated data330for a statistical test114, the statistics of the statistical test114based on parameter vectors to follow a probability distribution of a known or unknown form. The statistic simulator component122-2may generate simulated statistics430for the parameter vectors from the simulated data330, each parameter vector to comprise a single point in a grid of points. The code generator component122-3may remove selective points from the grid of points to form a subset of points, and generate interpolation code to interpolate a statistic of the statistical test114on any point.

As shown inFIG. 19, the code generator component122-3may receive a simulated data structure1910. The simulated data structure1910may include information for a set of fitted CDF curves for the grid of points, as described with reference toFIG. 18. The code generator component122-3may include an interpolation code generator1920to execute an interpolation function1922.

In various embodiments, the interpolation code generator1920may generate interpolation source code1930from the simulated data structure1910and a pair of interpolation functions1922,1924.

The first interpolation function1922may be arranged to call a second interpolation function comprising an instance of the virtual software class. The interpolation function1922may be an instance of a base software class522-1designed to call an instance of a virtual software class522-2, where the base software class522-1is a child of the virtual software class522-2. In one embodiment, for example, a base software class522-1may be implemented as a TK-extension class for interpolating statistics of the statistical test114, and a virtual software class522-2may be implemented as a virtual TK-extension class (TKICDF). Embodiments, however, are not limited to this example.

The second interpolation1924may be an instance of the virtual software class522-2. In one embodiment, the interpolation function1924may implement a monotonic cubic spline interpolation technique. In one embodiment, the interpolation function1924may implement a monotonic cubic spline interpolation technique in combination with a transform, such as the beta transformation, for example. The beta transformation may comprise a transform with a normalized incomplete beta function (the cumulative distribution function of beta distribution), the normalized incomplete beta function to comprise a nonnegative function whose derivative is completely positive.

Alternatively, the interpolation code generator1920may utilize a single interpolation function with some or all of the characteristics of both interpolation functions1922,1924. Embodiments are not limited in this context.

In some cases, the interpolation code generator1920may have an integrated compiler1932. The interpolation code generator1920may generate the interpolation source code1930, and use the compiler1932to compile the interpolation source code1930in order to generate an interpolation executable code1940. Alternatively, the compiler1932may be separate from the code generator component122-3(e.g., part of an operating system).

In one embodiment, the interpolation code generator1920may generate the interpolation source code1930in accordance with the following exemplary procedure:

FIG. 20illustrates one example of a logic flow2000. The logic flow2000may be representative of some or all of the operations executed by one or more embodiments described herein, such as the code generator component122-3of the simulation subsystem120of the automated statistical test system100. More particularly, the logic flow2000illustrates code generation operations for use with a grid of points.

As shown inFIG. 20, the logic flow2000may generate simulated data for a statistical test, statistics of the statistical test based on parameter vectors to follow a probability distribution, at block2002. For instance, the simulated data component122-1may generate simulated data330for a statistical test114, the statistical test114based on parameter vectors to follow a probability distribution of a known or unknown form.

The logic flow2000may simulate statistics for the parameter vectors from the simulated data, each parameter vector to comprise a single point in a grid of points, at block2004. For instance, the statistic simulator component122-2may generate simulated statistics430for the parameter vectors from the simulated data330, each parameter vector to comprise a single point in a grid of points.

The logic flow2000may remove selective points from the grid of points to form a subset of points at block2006. For instance, the code generator component122-3may remove selective points from the grid of points to form a subset of points. The code generator component122-3may receive a simulated data structure1910with information for estimated CDF curves of the subset of points.

The logic flow2000may generate interpolation code to interpolate a statistic of the statistical test on any point at block2008. For instance, the code generator component122-3may generate interpolation source code1930or interpolation executable code1940to interpolate a statistic of the statistical test114on any point in the grid of points to form an estimated CDF curve. The interpolation code may include, among other types of information, the simulated data structure1910, index tables for the simulated data structure1910, and a first interpolation function1922designed to call a second interpolation function1924.

The interpolation source code1930may be used to interpolate a CDF for any given point p for a statistical test114. Assume the simulation subsystem120is executed to simulate and fit CDFs on M points. Those M points construct a grid (or mesh), which is contained in the interpolation source code1930as generated by the code generator component122-3of the simulation subsystem120. The compiler1932may compile the interpolation source code1930into interpolation executable code1940, such as a DLL, for example. The DLL may be used to interpolate a CDF for any given point p of the statistical test, regardless of whether p is a point within the grid of points M or outside of the grid of points M.

FIG. 21Aillustrates an operational environment2100. The operational environment2100shows operations for the code generator component122-3to generate a computational representation130for a statistical test114.

As shown inFIG. 21A, the code generator component122-3may include a CDF code generator2120. The CDF code generator2120may receive a simulated data structure1910and interpolation source code1930from the interpolation code generator1920. The simulated data structure1910and the interpolation source code1930may be integrated or separate from each other. The simulated data structure1910may include information for a set of fitted CDF curves for the grid of points, as described with reference toFIG. 18. The interpolation source code1930may interpolate a statistic of the statistical test114on any point.

The CDF code generator2120may create a computational representation130arranged to generate an approximate probability distribution132for each point in the grid of points from the simulated data structure1910. For instance, the CDF code generator2120may generate CDF source code2130and/or CDF executable code2140via the compiler2132. The compiler2132may be integrated with, or separate from, the CDF code generator2120. The computational representation130may include the interpolation source code1930. The computational representation130may also include a set of H files, data C files, function C files, and a build script.

FIG. 21Billustrates one example of a logic flow2150. The logic flow2150may be representative of some or all of the operations executed by one or more embodiments described herein, such as the CDF code generator2120of the code generator component122-3of the simulation subsystem120of the automated statistical test system100. More particularly, the logic flow2150illustrates code generation operations to generate a computational representation130.

As shown inFIG. 21B, the logic flow2150may receive a simulated data structure1910with information for a set of fitted CDF curves for the grid of points as input2160. A process2170may generate source code for a computational representation130, as implemented in generating source code2172by incorporating template files, data, and instructions into the corresponding type of files. For instance, the CDF code generator2120may generate CDF source code2130with the simulated data structure1910and interpolation source code1930. The logic flow2150may output various types of source code files and logic as output2180. For instance, the CDF code generator2120may generate source code files for CDF source code2130.

The CDF source code2130may include, for example, one or more H files2182. An H file2182may contain data structures and interface functions for the usage of a set of data and the interpolation based on the set of data. The CDF source code2130may include, for example, one or more data C files2184. A data C file2184may contain all fitted CDF curves saved in a data structure and functions of using such data structure. The CDF source code2130may include, for example, one or more function C files2186. A function C file contains a function for the interpolation based on a given set of data, such as data in the simulated data structure1910, for example, the set of fitted CDF curves.

The CDF source code2130may also include logic implemented in the form of one or more scripts2188. For instance, the CDF source code2130may include a build script or make file that specifies how to build a software library.

FIG. 22illustrates an operational environment2200. The operational environment2200shows operations for the evaluation component122-4to reduce a data storage size for a computational representation130.

As shown inFIG. 22, the evaluation component122-4may comprise a data reduction generator2220. The data reduction generator2220may receive as input a computational representation130arranged to generate an approximate probability distribution132for each point in a grid of points from simulated statistics430for a statistical test114. The computational representation130may include a simulated data structure1910with information for estimated CDF curves.

The data reduction generator2220may evaluate the simulated data structure1910to determine whether any points in the grid of points is removable from the simulated data structure1910given a target level of precision. The data reduction generator2220may reduce the simulated data structure in accordance with the evaluation to produce a reduced simulated data structure2210. The reduced simulated data structure may reduce a data storage size for the computational representation130.

The data reduction generator2220may implement a parallel adaptive grid enhancement (PAGE) function2222arranged to implement a PAGE algorithm. In one embodiment, the data reduction generator2220may receive selection of a precision parameter to represent a target level of precision for the simulated data structure1910. The data reduction generator2220may remove points from the simulated data structure1910in accordance with the selected level of precision utilizing the PAGE algorithm. The PAGE algorithm may be described in more detail with reference toFIGS. 24-27, infra.

FIG. 23illustrates one example of a logic flow2300. The logic flow2300may be representative of some or all of the operations executed by one or more embodiments described herein, such as the data reduction generator2220of the evaluation component122-4of the simulation subsystem120of the automated statistical test system100. More particularly, the logic flow2300illustrates data reduction operations to reduce a data storage size for a computational representation130.

As shown inFIG. 23, the logic flow2300may receive a computational representation arranged to generate an approximate probability distribution for statistics of a statistical test, the computational representation to include a simulated data structure with information for estimated cumulative distribution function (CDF) curves for one or more parameter vectors of the statistical test, each parameter vector to comprise a single point in a grid of points, at block2302. For instance, the data reduction generator2220may receive as input a computational representation130arranged to generate an approximate probability distribution132for each point in a grid of points from simulated statistics430for a statistical test114. The computational representation130may include a simulated data structure1910with information for estimated CDF curves.

The logic flow2300may evaluate the simulated data structure to determine whether any points in the grid of points are removable from the simulated data structure given a target level of precision at block2304. For example, the data reduction generator2220may evaluate the simulated data structure1910to determine whether any points in the grid of points are removable from the simulated data structure1910given a target level of precision.

The logic flow2300may reduce the simulated data structure in accordance with the evaluation to produce a reduced simulated data structure having a smaller data storage size relative to the simulated data structure, the reduced simulated data structure to reduce a data storage size for the computational representation at block2306. For example, the data reduction generator2220may reduce the simulated data structure1910in accordance with the evaluation to produce a reduced simulated data structure2210, where the simulated data structure2210has a smaller data storage size as compared to the simulated data structure1910. The reduced simulated data structure may in turn reduce a data storage size for the computational representation130.

FIG. 24illustrates one example of a logic flow2400. The logic flow2400may be representative of some or all of the operations executed by one or more embodiments described herein, such as the data reduction generator2220of the evaluation component122-4of the simulation subsystem120of the automated statistical test system100. More particularly, the logic flow2400illustrates data reduction operations to reduce a data storage size for a computational representation130utilizing a PAGE algorithm.

In general, the logic flow2400may receive a computation representation130with a simulated data structure1910containing information for estimated CDF curves, and evaluate the simulated data structure1910to determine whether any points in the grid of points are removable from the simulated data structure given a target level of precision. The logic flow2400may perform the evaluation using a PAGE algorithm. The logic flow2400may then reduce the simulated data structure1910using evaluation results to produce a reduced simulated data structure2210.

As shown inFIG. 24, the logic flow2400may receive various inputs for a PAGE algorithm, such as an interpolation grid G0with M points at2402, an interpolation grid G2with N points at2404, and an input table of N rows at2406. Each row of the input table may contain K keys and Q quantiles. The interpolation grid G0and/or the interpolation grid G2may be examples of an interpolation executable code1940. The input table at2406may be an example of a simulated data structure1910.

The logic flow2400may receive selection of a precision parameter to represent a target level of precision for the simulated data structure. The precision parameter may be automatically selected by the data reduction generator2220based on a defined set of rules. Alternatively, the precision parameter may be selected by a user. Once selected, the PAGE algorithm may receive as input the precision parameter, along with other control parameters, for example, the type of interpolation method, as indicated at2408.

The logic flow2400may remove points from the simulated data structure in accordance with a selected level of precision utilizing the PAGE algorithm. The PAGE algorithm may be used to identify a set of candidate points for potential removal from a simulated data structure. In one embodiment, for instance, the PAGE algorithm may execute at2410and output a candidate reduction data set using the interpolation grids G0, G2, the input table, and the one or more control parameters. The candidate reduction data set may be stored in a first output table1as indicated at2412. The output table1may include evaluation information. The evaluation information may include, for example, a defined number of rows N, with each row to include one or more each of K keys, Q explanation errors on quantiles, one or more evaluation criteria, F fit parameters, and/or one or more flags to indicate if a point p is to remain in an interpolation grid G1.

The logic flow2400may perform a DATA operation2414to extract one or more rows from the output table1at2412based on the evaluation information to construct a second output table2at2416. For instance, output table2is a subset of output table1, and it contains the rows that should be included in the interpolation grid G1and columns of keys and fit parameters. Output table2may be an example of a reduced simulated data structure2210. The logic flow2400may utilize the code generator component122-3at2418to generate the interpolation grid G1at2420based on the output table2at2416. The interpolation grid G1may be an example of an interpolation executable code1940.

In one embodiment, the PAGE algorithm may be arranged to generate the candidate reduction data set using a “jackknife” evaluation technique. A jackknife evaluation technique provides information regarding whether a point may be approximated by its neighbors for a given level of precision. This information may be used to determine those points that cannot be removed from the grid of points for the given level of precision. Once needed points are identified, the remaining points may be stored in the candidate reduction data set. For instance, the jackknife operation may provide information on a relationship between precision and grid size. Table 1 illustrates results from a jackknife evaluation technique on all 103,780 points on the grid of points, with each point having 10,001 quantiles, for a maxF test:

TABLE 1QuantileJackknife Result100%0.44572151099%0.00745806595%0.00065085290%0.00059654375%0.00053289150%0.00047793625%0.00043549910%0.0004013775%0.0003821481%0.0003467800%0.000270918
Table 1 illustrates that less than 1% points cannot be explained well by its neighbors when the precision requirement is 0.0075.

In one embodiment, a jackknife evaluation technique may be performed in accordance with the following exemplary procedure:

The PAGE algorithm may use results from the jackknife evaluation technique as a basis for selectively removing points from the grid of points, estimating an approximation error for interpolation, and storing the removed points in the candidate reduction data set based on the approximation error. The PAGE algorithm may then evaluate each point in the candidate reduction data set against a set of evaluation criterion until a precision parameter is satisfied.

In general, the PAGE algorithm determines, given some target level of precision, whether an original interpolation grid G2could be reduced into a smaller interpolation grid G1, without deleting any points from an interpolation grid G0. The smaller interpolation grid may result in a smaller data storage size for the computational representation130(e.g., DLL). An example for reducing a data storage size for the computational representation130may be illustrated with the following exemplary procedure:

After using a PAGE algorithm according to different precisions, a grid size with corresponding levels of precision for the maxF test may be shown in Table 2 as follows:

TABLE 2Precision0.00500.00250.00100.00070.0005Grid Size (# Points)7,8689,77813,76617,202103,780% of Original Grid7.6%9.4%13.3%16.6%100.0%
Note that the original grid (e.g., simulated data structure1910) had 103,780 points for a precision level of 0.0005 (≧max|•−{tilde over (T)}). As indicated by Table 2, a data storage size for the simulated data structure1910may be substantially reduced when a level of precision is reduced. For instance, at a precision level of 0.0050, the number of points may be reduced from 103,780 points to 7,868 points, which is 7.6% of the simulated data structure1910. In this manner, an informed design decision may be made for the interpolation source code1930and/or the computational representation130regarding tradeoffs between a level of precision and data storage size, as desired for a given implementation. Embodiments are not limited in this context.

In some cases, it may take significant time and computational resources to simulate all points with an original set of statistics (e.g., 1 million statistics for the maxF test). To reduce time and conserve computational resources, a reduced number of statistics (e.g., 20,000 statistics for the maxF test) could be used for a single point, and then the PAGE algorithm may be used on the simulated points to find final grid points. The original set of statistics (e.g., 1,000,000) may then be simulated for only the final grid points. This could be accomplished using a defined set of criteria.

For the maxF test, for example, 20,000 statistics on each of 103,780 points may be simulated, and 10,001 quantiles on each of 103,780 points may be generated. Assume CDFs are fitted with a precision of 0.0020. The average number of curve parameters for different precisions are shown in Table 3, as follows:

Code and a DLL may be generated, and the PAGE algorithm may be applied to the DLL to generate Table 4, as follows:

TABLE 4Precision0.00500.00450.00400.00350.00300.00250.0020Percentage of Points10.6%12.2%14.9%19.2%27.3%46.1%87.7%

Using the results shown in Table 4, assume the points corresponding to precision of 0.0030 are selected. The original set of statistics (e.g., 1,000,000 statistics) may be simulated on each of the selected points. The defined number of quantiles (e.g., 10,001 quantiles) on each of selected points may be generated. The CDFs may be fitted with a precision of 0.0005. Finally code and DLL may be generated for the selected points.

Since all points with 1,000,000 statistics are available, the PAGE algorithm can do another evaluation, the results of which are shown in Table 5 as follows:

Various aspects of the evaluation component122-4in general, and the data reduction generator2220and PAGE algorithm in particular, may be described with reference toFIGS. 25-27, infra.

FIG. 25illustrates one example of a logic flow2500. The logic flow2500may be representative of some or all of the operations executed by one or more embodiments described herein, such as the data reduction generator2220of the evaluation component122-4of the simulation subsystem120of the automated statistical test system100.

The logic flow2500illustrates evaluation operations performed in accordance with an exemplary PAGE algorithm. In general, the PAGE algorithm determines, given some target level of precision, whether an original interpolation grid G2could be reduced into a smaller interpolation grid G1, without deleting any points from an interpolation grid G0. In this example, the PAGE algorithm is implemented by the distributed computing system610utilizing a general/captain architecture.

As shown inFIG. 25, the logic flow2500may initialize an output table on a captain node at block2502. The output table may store a candidate reduction data set. The logic flow2500may perform a jackknife operation on interpolation grid G2with N points to find the P points not meeting the control parameters at2504.

The logic flow2500may call a subroutine MPI_Allgatherv for execution by a general node and the captain node at block2506. The logic flow2500may form an interpolation grid G1and update flags at2508. The interpolation grid G1may include the interpolation grid G0plus P points.

The logic flow2500may interpolate all quantiles through the interpolation grid G1against a set of evaluation criterion until the precision parameter is satisfied. For instance, the logic flow2500may evaluate N points on the interpolation grid G1at2510. The logic flow2500may call subroutines MPI_Reduce and MPI_Bcast on the general node and/or the captain node to broadcast a maximum criterion and the points V to achieve a maximum criterion at2512. The logic flow2500may test whether the maximum criterion is less than or equal to a defined precision level at2514. If the maximum criterion is less than or equal to the defined precision level, then the general node may call the subroutine MPI_Bcast to indicate a parameter qDONE is set to a value of 1 at2516. The PAGE algorithm then terminates.

If the maximum criterion is greater than the defined precision level, then the general node and/or the captain node may call the subroutine MPI_Bcast to indicate a parameter qDONE is set to a value of 0 and the point V at2518. The captain node may update the interpolation grid G1to include the interpolation grid G1plus the points V and update the flag at2520. Operations at2510,2512,2514,2518and2520may be repeated until the maximum criterion is less than or equal to a defined precision level at2514. The PAGE algorithm then terminates.

FIG. 26illustrates one example of a logic flow2600. The logic flow2600may be representative of some or all of the operations executed by one or more embodiments described herein, such as the simulation subsystem120of the automated statistical test system100. More particularly, the logic flow2600illustrates procedure for the simulation subsystem120to generate a computational representation130.

As shown inFIG. 26, the logic flow2600may simulate statistics by repeating, for p equals 1 to P, simulating S statistics on point p, where S is set to 20,000 and P equals a number of all potential points (or parameter vectors), at block2602. Block2602may output S by P statistics at2614.

The logic flow2600may generate quantiles by repeating, for p equals 1 to P, generating Q quantiles on point p, where Q is set to 10,001, at block2604. Block2604may output Q by P quantiles at2626.

The logic flow2600may fit CDFs by repeating, for p equals 1 to P, fitting a curve to Q quantiles on point p with at most F curve parameters, where F is set to 128, at block2606. Block2606may output F by P curve parameters at2618.

The logic flow2600may generate C code using all P points for grid G2and selected points for grid G0at block2608. Block2608may output two C files, four H files and two build scripts, at2620.

The logic flow2600may build a TK-Extension using a SDSGUI to build two DLLs at block2610. Block2610may output a tkGrid2.dll and a tkGrid0.dll at2622.

The logic flow2600may run PAGE algorithm for different levels of precisions. Block2612outputs a table of number of points versus a given level of precision at2624. Control is then passed to control location G.

FIG. 27illustrates one example of a logic flow2700. The logic flow2700may be representative of some or all of the operations executed by one or more embodiments described herein, such as the simulation subsystem120of the automated statistical test system100. More particularly, the logic flow2700illustrates procedure for the simulation subsystem120to reduce a data storage size for a computational representation130.

As shown inFIG. 27, the logic flow2700may receive control from control location G, and select a proper number of points for the computational representation130at2702. The proper number of points may be selected by data reduction generator2220, and it may be an example of a reduced simulated data structure2210.

The logic flow2700may simulate statistics by repeating, for p equals 1 to B, simulating S statistics on point p, where S is set to 1,000,000 and B equals the number of selected points (or parameter vectors), at block2704. Block2704may output S by B statistics at2714.

The logic flow2700may generate quantiles by repeating, for p equals 1 to B, generating Q quantiles on point p, where Q is set to 10,001, at block2706. Block2706may output Q by B quantiles at2716.

The logic flow2700may fit CDFs by repeating, for p equals 1 to B, fitting a curve to Q quantiles on point p with at most F curve parameters, where F is set to 128, at block2708. Block2708may output F by P curve parameters at2718.

The logic flow2700may generate C code using all B points for grid G1at block2710. Block2710may output one C file, two H files and one build script, at2720.

The logic flow2700may build a TK-Extension using a SDSGUI to build one DLL at block2712. Block2712may output a tkGrid1.dll at2722. The tkGrid1.dll may be an example of an interpolation executable code1940.

FIG. 28Aillustrates a block diagram for a statistical test subsystem140. The statistical test subsystem140is part of the automated statistical test system100. The statistical test subsystem140may, for example, generate statistical significance values for results of a statistical test using an approximate probability distribution.

As shown inFIG. 28A, the statistical test subsystem140may include a statistical test application2820having various components2822-s. The statistical test application2820may include a data handler component2822-1, a statistical test component2822-2, and a significance generator component2822-3. The statistical test application2820may include more or less components2822-sfor other implementations.

The data handler component2822-1may be generally arranged to handle data sets for use in a statistical test114. For instance, the data handler component2822-1may receive a real data set2810from a client device602. The real data set2810may represent actual data for analysis by the statistical test114, such as sets of collected business or enterprise data, as opposed to simulated data330used to generate approximate probability distributions132for the statistical test114. In one embodiment, for example, the real data set2810may comprise data representing one or more physical phenomena, such as occurrences of heads or tails in a coin flip, sales of a number of shoes in Asia, or a percentage increase or decrease in a financial portfolio. In one embodiment, for example, the real data set2810may comprise data representing one or more measurable phenomena, which may include both physical and non-physical phenomena. An example of non-measurable phenomena may include without limitation digital data from an electronic device, such as a sensor, computer, or characters on a display. Embodiments are not limited in this context.

The statistical test component2822-2may be generally arranged to perform the statistical test using the real data set2810. The statistical test component2822-2may receive a computation representation130from, for example, the simulation subsystem120. The statistical test component2822-2may also receive the statistical test function112for the statistical test114. As previously described, the computational representation130may be arranged to generate an approximate probability distribution132for each point in a grid of points from simulated statistics430for the statistical test114, statistics of the statistical test114to follow a probability distribution of a known or unknown form. The approximate probability distribution function132may comprise an empirical CDF, the empirical CDF to have a first level of precision relative to the probability distribution of the known or unknown form based on a sample size of the simulated statistics.

The statistical test component2822-2may generate a set of statistics2824for the statistical test114using the real data set2810and the statistical test function112.

The significance generator component2822-3may be generally arranged to generate a set of statistical significance values2830for the statistics2824generated by the statistical test component2822-2using the approximate probability distribution132of the computational representation130. The set of statistical significance values may be in the form of one or more p-values2832.

A p-value2832may generally represent a probability of obtaining a given test statistic from observed or measurable data, such as a test statistic obtained or evaluated from the real data set2810. More particularly, a p-value2832may represent a probability of obtaining a test statistic evaluated from the real data set2810that is at least as “extreme” as one that was actually observed, assuming the null hypothesis is true. For instance, assume a statistical test114involves rolling a pair of dice once and further assumes a null hypothesis that the dice are fair. An exemplary test statistic may comprise “the sum of the rolled numbers” and is one-tailed. When the dice are rolled, assume a result where each rolled dice finally lands and presents a side with a number 6. In this case, the test statistic is the sum of the rolled numbers from both dice, which would be 12 (6+6=12). A p-value2832for this particular result or outcome is a probability of 1/36, or approximately 0.028. The p-value2832of 0.028 represents the highest test statistic out of 6×6=36 possible outcomes. If a significance level of 0.05 is assumed, then this result would be deemed significant since 0.028 is lower (or more extreme) value than 0.05. As such, the observed result of 12 from the rolled dice would amount to evidence that could be used to reject the null hypothesis that the dice are fair.

Once p-values2832are generated, the significance generator component2822-3may use the p-values2832in a number of different ways. For instance, the significance generator component2822-3may present the p-values2832in a user interface view on an electronic display, an example of which is described with reference toFIG. 28B, infra. A user may then determine whether a null hypothesis for the statistical test114is rejected based on the p-values2832.

Additionally or alternatively, this determination may be automatically made by the statistical application2820. For instance, the significance generator component2822-3may compare a p-value2832to a defined threshold value. The significance generator component2822-3may then determine whether a null hypothesis for the statistical test114is rejected based on a comparison of a p-value2832to a defined threshold value. The significance generator component2822-3may then display a conclusion from the results on the electronic display.

FIG. 28Billustrates a user interface view2850. The user interface view2850illustrates an exemplary user interface presenting output of a statistical test114in the form of a Bai and Perron's multiple structural change test as executed by the statistical test application2820.

This example illustrates how to use Bai and Perron's multiple structural change tests and the p-values generated from a HPSIMULATE procedure. It uses the following notations:t: a time indexy: a dependent variablex: an independent variableε: an innovationi.i.d.: independent and identically distributedN(0,1): a standard normal distribution with mean 0 and variance 1H0: a null hypothesisH1: an alternative hypothesism: a number of break points in the datasupFl+1|l: a sequential test for multiple structural change proposed by Bai and Perron, where l is the number of break points in the null hypothesis and l+1 in the alternative hypothesis

As shown in a DATA operation2852, labeled in the user interface view as “data one,” the data generating process (DGP) has two break points at time indices60and140. Precisely, the structural change model is as follows:

In a PROC operation2854, labeled in the user interface view2850as “proc autoreg,” a BP=(M=3) option is set in the AUTOREG procedure to apply Bai and Perron's multiple structural change tests on the data. The user interface view2850shows the result of supFl+1|ltests in a table2856annotated as “Bai and Perron's Multiple Structural Change Tests, supF(l+1|l) Tests,” which sequentially checks the null hypothesis H0: m=l versus the alternative null hypothesis H1: m=l+1 for l=0, 1, 2, 3, where m is the number of break points in the data. A statistic for each test is shown in a column2858and a corresponding p-value, interpolated from the DLL generated by the HPSIMULATE procedure, is shown in a column2860. If 15% is selected as a defined threshold value (e.g., a significance threshold), by comparing p-values to 15%, the null hypothesis H0: m=0 and H0: m=1; are rejected. However, the null hypothesis of H0: m=2 cannot be rejected. According to one interpretation of these tests, there exists at least 2 break points in the data.

For the supFl+1|l test, in literature, critical values for only four significance levels, namely 1%, 2.5%, 5%, and 10%, are available on some parameter vectors. Hence, a user can only make decision at those four significance levels on the finite parameter vectors by comparing the test statistics, based on the real data set, with the critical values available in literature. However, with the support of HPSIMULATE system and the DLL generated from it, the user can make decision at any significance level of interest (e.g., 15% here) on any parameter vector.

FIG. 29illustrates one example of a logic flow2900. The logic flow2900may be representative of some or all of the operations executed by one or more embodiments described herein, such as the statistical test subsystem140of the automated statistical test system100.

As shown inFIG. 29, the logic flow2900may receive a computational representation arranged to generate an approximate probability distribution for statistics of a statistical test based on a parameter vector, statistics of the statistical test to follow a probability distribution at block2902. The probability distribution, for example, may comprise a probability distribution of a known or an unknown form. The logic flow2900may receive a real data set from a client device, the real data set to comprise data representing at least one measurable phenomenon or physical phenomenon at block2904. The logic flow2900may generate statistics for the statistical test using the real data set on the parameter vector at block2906. The logic flow2900may generate the approximate probability distribution of the computational representation on the parameter vector at block2908. The logic flow2900may generate a set of statistical significance values for the statistics through interpolation at block2910by using the approximate probability distribution of the computational representation, the set of statistical significance values comprising one or more p-values, each p-value to represent a probability of obtaining a given test statistic from the real data set, at block2906.

FIG. 30illustrates a block diagram of a centralized system3000. The centralized system3000may implement some or all of the structure and/or operations for the automated statistical test system100in a single computing entity, such as entirely within a single device3020.

The device3020may comprise any electronic device capable of receiving, processing, and sending information for the automated statistical test system100. Examples of an electronic device may include without limitation an ultra-mobile device, a mobile device, a personal digital assistant (PDA), a mobile computing device, a smart phone, a telephone, a digital telephone, a cellular telephone, eBook readers, a handset, a one-way pager, a two-way pager, a messaging device, a computer, a personal computer (PC), a desktop computer, a laptop computer, a notebook computer, a netbook computer, a handheld computer, a tablet computer, a server, a server array or server farm, a web server, a network server, an Internet server, a work station, a mini-computer, a main frame computer, a supercomputer, a network appliance, a web appliance, a distributed computing system, multiprocessor systems, processor-based systems, consumer electronics, programmable consumer electronics, game devices, television, digital television, set top box, wireless access point, base station, subscriber station, mobile subscriber center, radio network controller, router, hub, gateway, bridge, switch, machine, or combination thereof. The embodiments are not limited in this context.

The device3020may execute communications operations or logic for the automated statistical test system100using communications component3040. The communications component3040may implement any well-known communications techniques and protocols, such as techniques suitable for use with packet-switched networks (e.g., public networks such as the Internet, private networks such as an enterprise intranet, and so forth), circuit-switched networks (e.g., the public switched telephone network), or a combination of packet-switched networks and circuit-switched networks (with suitable gateways and translators). The communications component3040may include various types of standard communication elements, such as one or more communications interfaces, network interfaces, network interface cards (NIC), radios, wireless transmitters/receivers (transceivers), wired and/or wireless communication media, physical connectors, and so forth. By way of example, and not limitation, communication media3012,3042include wired communications media and wireless communications media. Examples of wired communications media may include a wire, cable, metal leads, printed circuit boards (PCB), backplanes, switch fabrics, semiconductor material, twisted-pair wire, co-axial cable, fiber optics, a propagated signal, and so forth. Examples of wireless communications media may include acoustic, radio-frequency (RF) spectrum, infrared and other wireless media.

The device3020may communicate with other devices3010,3050over a communications media3012,3042, respectively, using communications information3014,3044, respectively, via the communications component3040. The devices3010,3050may be internal or external to the device3020as desired for a given implementation. An example for the devices3010may be one or more client devices used to access results from the automated statistical test system100.

FIG. 31illustrates a block diagram of a distributed system3100. The distributed system3100may distribute portions of the structure and/or operations for the automated statistical test system100across multiple computing entities. Examples of distributed system3100may include without limitation a client-server architecture, a S-tier architecture, an N-tier architecture, a tightly-coupled or clustered architecture, a peer-to-peer architecture, a master-slave architecture, a shared database architecture, and other types of distributed systems. The embodiments are not limited in this context.

The distributed system3100may comprise a client device3110and a server device3150. In general, the client device3110and the server device3150may be the same or similar to the client device3020as described with reference toFIG. 30. For instance, the client device3110and the server device3150may each comprise a processing component3130and a communications component3140which are the same or similar to the processing component3030and the communications component3040, respectively, as described with reference toFIG. 30. In another example, the devices3110,3150may communicate over a communications media3112using communications information3114via the communications components3140.

The client device3110may comprise or employ one or more client programs that operate to perform various methodologies in accordance with the described embodiments. In one embodiment, for example, the client device3110may implement a client application3116to configure, control or otherwise manage the automated statistical test system100. The client application3116may also be used to view results from the automated statistical test system100, such as statistical significance values or null hypothesis results. The client application3116may be implemented as a thin-client specifically designed to interoperate with the automated statistical test system100. Alternatively, the client application3116may be a web browser to access the automated statistical test system100via one or more web technologies. Embodiments are not limited in this context.

The server device3150may comprise or employ one or more server programs that operate to perform various methodologies in accordance with the described embodiments. In one embodiment, for example, the server device3150may implement the automated statistical test system100, and any interfaces needed to permit access to the automated statistical test system100, such as a web interface. The server device3150may also control authentication and authorization operations to enable secure access to the automated statistical test system100via the media3112and information3114.

FIG. 32illustrates an embodiment of an exemplary computing architecture3200suitable for implementing various embodiments as previously described. In one embodiment, the computing architecture3200may comprise or be implemented as part of an electronic device. Examples of an electronic device may include those described with reference toFIG. 31, among others. The embodiments are not limited in this context.

As shown inFIG. 32, the computing architecture3200comprises a processing unit3204, a system memory3206and a system bus3208. The processing unit3204can be any of various commercially available processors, including without limitation an AMD® Athlon®, Duron® and Opteron® processors; ARM® application, embedded and secure processors; IBM® and Motorola® DragonBall® and PowerPC® processors; IBM and Sony® Cell processors; Intel® Celeron®, Core (2) Duo®, Itanium®, Pentium®, Xeon®, and XScale® processors; and similar processors. Dual microprocessors, multi-core processors, and other multi-processor architectures may also be employed as the processing unit3204.

The computer3202may include various types of computer-readable storage media in the form of one or more lower speed memory units, including an internal (or external) hard disk drive (HDD)3214, a magnetic floppy disk drive (FDD)3216to read from or write to a removable magnetic disk3218, and an optical disk drive3220to read from or write to a removable optical disk3222(e.g., a CD-ROM or DVD). The HDD3214, FDD3216and optical disk drive3220can be connected to the system bus3208by a HDD interface3224, an FDD interface3226and an optical drive interface3228, respectively. The HDD interface3224for external drive implementations can include at least one or both of Universal Serial Bus (USB) and IEEE 1394 interface technologies.

The drives and associated computer-readable media provide volatile and/or nonvolatile storage of data, data structures, computer-executable instructions, and so forth. For example, a number of program modules can be stored in the drives and memory units3210,3212, including an operating system3230, one or more application programs3232, other program modules3234, and program data3236. In one embodiment, the one or more application programs3232, other program modules3234, and program data3236can include, for example, the various applications and/or components of the automated statistical test system100.

A monitor3244or other type of display device is also connected to the system bus3208via an interface, such as a video adaptor3246. The monitor3244may be internal or external to the computer3202. In addition to the monitor3244, a computer typically includes other peripheral output devices, such as speakers, printers, and so forth.

The computer3202may operate in a networked environment using logical connections via wire and/or wireless communications to one or more remote computers, such as a remote computer3248. The remote computer3248can be a workstation, a server computer, a router, a personal computer, portable computer, microprocessor-based entertainment appliance, a peer device or other common network node, and typically includes many or all of the elements described relative to the computer3202, although, for purposes of brevity, only a memory/storage device3250is illustrated. The logical connections depicted include wire/wireless connectivity to a local area network (LAN)3252and/or larger networks, for example, a wide area network (WAN)3254. Such LAN and WAN networking environments are commonplace in offices and companies, and facilitate enterprise-wide computer networks, such as intranets, all of which may connect to a global communications network, for example, the Internet.

When used in a LAN networking environment, the computer3202is connected to the LAN3252through a wire and/or wireless communication network interface or adaptor3256. The adaptor3256can facilitate wire and/or wireless communications to the LAN3252, which may also include a wireless access point disposed thereon for communicating with the wireless functionality of the adaptor3256.

When used in a WAN networking environment, the computer3202can include a modem3258, or is connected to a communications server on the WAN3254, or has other means for establishing communications over the WAN3254, such as by way of the Internet. The modem3258, which can be internal or external and a wire and/or wireless device, connects to the system bus3208via the input device interface3242. In a networked environment, program modules depicted relative to the computer3202, or portions thereof, can be stored in the remote memory/storage device3250. It will be appreciated that the network connections shown are exemplary and other means of establishing a communications link between the computers can be used.

FIG. 33illustrates a block diagram of an exemplary communications architecture3300suitable for implementing various embodiments as previously described. The communications architecture3300includes various common communications elements, such as a transmitter, receiver, transceiver, radio, network interface, baseband processor, antenna, amplifiers, filters, power supplies, and so forth. The embodiments, however, are not limited to implementation by the communications architecture3300.

As shown inFIG. 33, the communications architecture3300comprises includes one or more clients3302and servers3304. The clients3302may implement the client device3110. The servers3304may implement the server device3150. The clients3302and the servers3304are operatively connected to one or more respective client data stores3308and server data stores3310that can be employed to store information local to the respective clients3302and servers3304, such as cookies and/or associated contextual information.

The clients3302and the servers3304may communicate information between each other using a communication framework3306. The communications framework3306may implement any well-known communications techniques and protocols. The communications framework3306may be implemented as a packet-switched network (e.g., public networks such as the Internet, private networks such as an enterprise intranet, and so forth), a circuit-switched network (e.g., the public switched telephone network), or a combination of a packet-switched network and a circuit-switched network (with suitable gateways and translators).

FIG. 34illustrates an embodiment of a storage medium3400. The storage medium3400may comprise an article of manufacture. In one embodiment, the storage medium3400may comprise any non-transitory, physical, or hardware computer readable medium or machine readable medium, such as an optical, magnetic or semiconductor storage. The storage medium may store various types of computer executable instructions3402, such as instructions to implement one or more of the logic flows as described herein. Examples of a computer readable or machine readable storage medium may include any tangible media capable of storing electronic data, including physical memory, hardware memory, volatile memory or non-volatile memory, removable or non-removable memory, erasable or non-erasable memory, writeable or re-writeable memory, and so forth. Examples of computer executable instructions may include any suitable type of code, such as assembly code, source code, compiled code, interpreted code, executable code, static code, dynamic code, object-oriented code, visual code, compressed code, uncompressed code, and the like. The embodiments are not limited in this context.

The computer executable instructions3402may be implemented using one or more different types of programming languages. A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms. Many programming languages have computation specified in an imperative form (e.g., as a sequence of operations to perform), while other languages utilize other forms of program specification such as the declarative form (e.g., the desired result is specified, not how to achieve it). The description of a programming language is usually split into the two components of syntax (form) and semantics (meaning). Some languages are defined by a specification document (e.g. the C programming language is specified by an ISO Standard), while other languages (e.g., Perl) have a dominant implementation that is treated as a reference.

In one embodiment, for example, the computer executable instructions3402may be implemented in a specific programming language as developed by SAS Institute, Inc., Cary, N.C. For instance, the computer executable instructions3402may be implemented in a procedure referred to as HPSIMULATE, which is a procedure suitable for execution within a SAS programming language and computing environment. In such embodiments, the computer executable instructions3402may follow syntax and semantics associated with HPSIMULATE. However, embodiments are not limited to HPSIMULATE, and further, do not need to necessarily follow the syntax and semantics associated with HPSIMULATE. Embodiments are not limited to a particular type of programming language.

The HPSIMULATE procedure dynamically loads a TK-extension to perform statistical simulation and other tasks, such as post-processing, optimization, and other tasks. In one embodiment, the HPSIMULATE procedure may perform statistical simulation in distributed computing and multi-thread environment.

The HPSIMULATE may have a syntax as follows:

OUTPUT

PERFORMANCE

The options in gray font are some unnecessary options to run the HPSIMULATE procedure, or reserved for future usage.

A set of statements and options used with the HPSIMULATE procedure are summarized in the following Table 6:

TABLE 6DescriptionStatementOptionData Set OptionsSpecify the input data setHPSIMULATEDATA=Specify how the data areHPSIMULATEDATADIST=distributed on gridWrite results to an output data setOUTPUTOUT=Grid Control OptionsSpecify the number of captainsPERFORMANCENODES=Specify the number of threadsPERFORMANCENTHREADS=Task Control OptionsSpecify the TK-extension toMODULEEXT=execute the tasksSpecify the task ID to be executedMODULETASK=Specify whether the task needs toMODULEDEPENDENTcontrol communication betweenthreads and between nodesSpecify the variable names in inputMODULETASKPARMV=data setSpecify the number parametersMODULETASKPARMN=Specify the string parametersMODULETASKPARMS=Specify the name of the moduleMODULENAME=

The HPSIMULATE procedure may use the following statement:PROC HPSIMULATE options.

The HPSIMULATE statement may use a first option, as follows:DATA=SAS-data-set.
The DATA option specifies the input data set containing parameters for simulation or data for other tasks. If the DATA option is not specified, PROC HPSIMULATE uses the most recently created SAS data set.

The HPSIMULATE statement may use a second option, as follows:DATADIST=(options)
The second option specifies how data is distributed on a distributed computing system. The second option may have a set of options as shown in Table 7, as follows:

TABLE 7OptionDescriptionCOPYONGENERALMake a copy on general.COPYTONODESMake a copy of data set to each captainso that each captain has all data. Thisis the default option.ROUNDROBINDistribute the data to captains row-wiselyaccording to round-robin rule.DEFAULTDistribute the data to captains row-wiselyaccording to first-come-first-serve rule.INSLICESDistribute the data to captains in slices.COLUMNWISEDistribute the data to captains column-wisely and evenly.COLUMNWISEBYDistribute the data to captains column-wisely according to the groups defined inthe first row of data: (1) the group IDmust be integer; (2) negative ID indicatingthe corresponding columns need not bedistributed; and (3) zero ID indicating thecolumns must be distributed to all captains.

The HPSIMULATE procedure may have a module statement as follows:MODULE options.
The MODULE statement specifies the TK-extension and parameters for the task to be executed. The MODULE statement may use seven options, as follows:

The EXT option specifies the name of the TK-extension to execute the task. The TK-extension can focus on the task-oriented calculation since the data I/O, communication between client and grid and on grid, and multi-threading are all left to the HPSIMULATE procedure. The TK-extension is dynamically loaded in the procedure. The EXT=option must be specified. The TK-extension must follow some protocol defined in a virtual TK-extension which includes the structures of instance and factory of functions; in other words, any user specified TK-extension is the “child” of that virtual TK-extension which is called TKVRT and introduced later in the Details section.

The TASK option specifies the task ID to be executed. The TK-extension understands the task ID and executes the right task. By default, TASK=option is set to zero.

The DEPENDENT|CONTROLPARALLEL option specifies whether the task needs to control communication between threads and between nodes.

The NAME option specifies a name of the module.

The HPSIMULATE procedure may include an output statement, as follows:OUTPUT OUT=SAS-data-set
The OUTPUT statement creates an output SAS data set as specifies by the following OUT option:OUT=SAS-data-set
The OUT option names the output SAS data set containing the task-dependent results which might be simulated statistics or the quantiles.

The HPSIMULATE procedure may include a performance statement, called PERFORMANCE. The PERFORMANCE statement is a common statement supported in a high performance architecture (HPA) bridge. Only some options used in the HPSIMULATE procedure are listed as follows:NODES=number
The NODES option specifies a number of captains. If NODES=0 is specified, the procedure is executed on client side and no distributed computing environment computers are involved.NTHREADS=number
The NTHREADS option specifies the number of threads to be used in each computer.

The HPSIMULATE procedure is based, in part, on the HPLOGISTICS procedure. The framework of the HPLOGISTICS procedure may implement all data input/output, communication between client devices602-eand the distributed computing system610, or general and captain nodes of the distributed computing system610, and multi-threading details. A framework extended on the framework of the HPLOGISTICS procedure is shown inFIGS. 9-11. The framework is flexible to support any simple and complex algorithm. In this manner, a client application may plug-in its own tasks, like simulation or estimation. A user's TK-extension should follow some protocol defined in a virtual TK-extension which includes structures of instance and factory of functions. In other words, any user specified TK-extension is a “child” of that virtual TK-extension which is called TKVRT.

For the virtual TK-extension TKVRT, the user-specified TK-extension should be a “child” of the TKVRT TK-extension. The TKVRT defines the following public structures related to input parameters and output result:

struct TKVRT_COLUMN/* Column name element */{inttype;intnamelencharname[TKVRT_MAXNAME];tkvrtColumnPtrnext;};struct TKVRT_DATA/* Matrix in memory orutility file on diskwith column names*/{TKBooleanQinMemory;int 64_tnRow;int64_tcurRow;int64_tnColumn;tkvrtColumnPtrcolHead;tkvrtColumnPtrcolTail;double*mat;tkrecUtFilePtrfid;TKPoolhPool;};struct TKVRT_PARMS/* Parameters */{longnCaptains;/* is the number ofcaptains */longcaptainID;/* is the current captainID */longnThreads;/* is the number of threads*/longthreadID;/* is the current thread ID*/longtask;/* is the task id */chartaskFlag[5];/* is the task flag */longnTaskParm;//* is the number of inputnumber parameters */double*taskParmList;/* is the list of inputnumber parameters */longnTaskParmStr;/* is the number of inputstring parameters */char**taskParmStrList;/* is the list of inputstring parameters */long*taskParmStrLenList;/* is the list of the lengthof input string parameters */longnInputData;/* is the number of inputdata sets */tkvrtDataPtrinputDataList;/* is the list of inputdata sets */longnOutputParm;/* is the number of outputnumber parameters */int64_tsOutputParm;/* is the size of allocatedmemory for output numberparameters */double*outputParmList;/* is the list of outputnumber parameters */longnOutputInt64Parm;/* is the number of outputinteger parameters */int64_tsOutputInt64Parm;/* is the size of allocatedmemory for output integerparameters */int64_t*outputInt64ParmList;/* is the list of outputinteger parameters */longnOutputParmStr;/* is the number of outputstring parameters */char**outputParmStrList;/* is the list of outputstring parameters */long*outputParmStrLenList;/* is the list of the lengthof output string parameters*/longnOutputData;/* is the number of outputdata sets */tkvrtDataPtroutputDataList;/* is the list of outputdata sets */TKPoolhtaskPool;/* is the memory Pool */TKMemPtruserPtr;/* is the pointer toanything else */TKMemPtruserPtr1;/* is the pointer toanything else */TKMemPtruserPtr2;/* is the pointer toanything else */TKMemPtruserPtr3;/* is the pointer toanything else */TKMemPtruserPtr4;/* is the pointer toanything else */
The function Set up Thread Work(.) in tksimt.c may provide details on how the parameter structures are initialized.

The TKVRT also declares following public functions:

Some systems may use an open-source framework for storing and analyzing big data in a distributed computing environment. For example, some systems may use Hadoop® for applications in which the simulated functions depend on given fixed data that are supplied externally to the algorithm, and that these data can be read from distributed file systems, such as Hadoop®. This could apply, for example, if subsets of the data on different nodes correspond to different cases to be simulated. In that case, different nodes can do the simulations for the subcases corresponding to the data that they read locally, without need to pass data across the network. To help make that process work, the system could adopted a map-reduce-like pattern for controlling which nodes do which simulations.

Some systems may use cloud computing, which can enable ubiquitous, convenient, on-demand network access to a shared pool of configurable computing resources (e.g., networks, servers, storage, applications and services) that can be rapidly provisioned and released with minimal management effort or service provider interaction. Some grid systems may be implemented as a multi-node cluster. Some systems may use a massively parallel processing (MPP) database architecture. Some systems may be used in conjunction with complex analytics (e.g., high-performance analytics, complex business analytics, and/or big data analytics) to solve complex problems quickly.