Method and System for Speculative Prediction in a Workflow System (02-Feb-2010)

Method and System for Speculative Prediction in a Workflow System

Disclosed is a method and system of speculatively predicting the time at which a process

produces output parameters and also to speculatively predict output parameter values of a

process in a workflow system.

A workflow consists of a set of processes that communicate by passing input parameters and output parameters among themselves. A runtime system dedicated to running these workflows is referred to as a workflow system. Typically, a process in a workflow system, such as a Tool Command Language (TCL)

process running Electronics Design Automation (EDA)

require different input parameters to be provided at different times. Until the input parameters for a process are provided, the process is stalled and the execution of a workflow is suboptimal.

Fig. 1 exemplarily illustrates a method of executing different processes speculatively. Consider a scenario where process "A"

produces an output parameter after "t1" seconds and process "B"

consumes the same after "t2" seconds. If the values of "t1" and "t2" are predicted in advance,

process "B" may be initialized "t1-t2" seconds after initializing process "A". By predicting the

time at which process B may be initialized, the execution of process "A" and process "B" may be overlapped to optimize the workflow system. Further, the length of the critical path and the time to execute the workflow may be decreased.

Figure 1

In an implementation, the method and system predicts the time at which a process produces an output parameter based on previous iterations of the process. The prediction may be performed by recording profiling information corresponding to the process from previous iterations. A four

1

jobs, may

tuple, for example, <

producing an output parameter during every iteration of the process. Similarly, a three tuple, for

example, <

paramete

different inputs share a common integer id.

Thereafter, a hash value corresponding to the four tuple is created. The hash value is then used for recording information corresponding to the process in a hash table. Hash values for subsequent processes may be computed and compared with the hash table to determine a matching entry from the hash table. If a matching entry is found, the information corresponding to the output generation time of the matched hash value is returned as illustrated in Fig.2.

Figure 2

Alternatively, the method and system may utilize artificial neural networks for predicting the time at which a process produces an output parameter. The artificial neural networks employ neural network based learners to predict the time at which a parameter is generated. Fig. 3 exemplarily illustrates a method of predicting the time at which a process produces an output

parameter utilizing artif...