|
Execution time estimation It is quite impossible to exactly compute the execution time of a computer program on a specific computational resource. Even though the program complexity may be known, it only provides a bound function (depending on the input data size), which is independent of the underlying hardware. In addition, the computational power (in CPU cycles) of any processor depends on many structural components, so an exact value cannot be achieved without considering several design issues. Approximation methods shall be used to estimate the execution time of any given program on a specific processor. Execution time estimation, often also called performance estimation, is a common technique applied to model the execution time of tasks on a computer, and it has been used in HC static scheduling since the early 1990s [Yang et al., 1993; Singh and Youssef, 1996]. This technique relies on estimation methods such as task profiling (used to predict the computational requirements of a given task), machine benchmarking (used to determine an estimation of the computational power of a machine) and statistical analysis, in order to provide an accurate estimation of the execution time of a given task in a specific machine. The estimation scenario is a feasible and realistic one, with only a few assumptions, since that the computational capacity of machines are quite easy to estimate, and the computational requirements (workload) of each task can be estimated using some specifications provided by the users, analyzing historic data, and/or using more advanced prediction models. Researchers have stated that the prediction of task execution times are useful to guide the resource selection performed by a scheduling method and also to achieve load balancing on heterogeneous environments [Li et al. 2004]. Expected time to compute In 2000, Ali et al. presented the Expected Time to Compute (ETC) performance estimation model, which has been widely used in the last eight years. ETC provides an estimation for the execution time of a collection of tasks in a set of heterogeneous machines, taking into account three key properties: machine heterogeneity, task heterogeneity and consistence. • Machine heterogeneity evaluates the variation of execution times for a given task across the resources in the HC system. An environment comprised of similar computing resources (i.e. parallel systems and almost-homogeneous clusters of workstations) will be represented by low machine heterogeneity values, while machine high heterogeneity values will represent generic HC systems, composed by many computational resources of different types and power (e.g. workstations, supercomputers, distributed environments and grid systems). • Task heterogeneity represent the degree of variation among the tasks execution times for a given machine. High task heterogeneity values models those scenarios in which tasks of different types are submitted to execute in the HC system, from simple programs which demands very little computational effort, to large and complex tasks which require high CPU times to perform. On the other side, when the complexity and so the computation requirements of the tasks are quite similar, those tasks can be performed in rather similar execution times for a given machine, a situation modeled by low task heterogeneity values. The HC model by Ali et al. also considered a second classification for ETC models, trying to reflect the characteristics of realistic scenarios. In a consistent ETC model, whenever a given machine mj executes any task ti faster than other machine mk, then machine mj executes all tasks faster than machine mk. This situation corresponds to an ideal case of high machine heterogeneity and very low task heterogeneity (or even identical tasks complexity) , where the execution time of each task is mainly determined for the computational power of each machine, since tasks are supposed to perform at the same rate in all machines (and without requiring large amount of remote data or communications). Although such structured scenario seems to be unrealistic for general purpose applications, it captures the reality of many SPMD applications executing with local input data. An inconsistent ETC model lacks of any structure among the tasks computational requirements and machines computational power, and this absence of relationships means that a given machine mj may be faster than machine mk when executing some tasks and slower for others. This category comprises the most general scenario for a distributed infrastructure composed of highly heterogeneous resources which receive any kind of tasks, from easy-to-solve programs to very complex parallel models. In addition, a third category of partially consistent ETC models is included, to define those inconsistent ETC systems that include a consistent ETC subsystem. In this last category, even though there is not a predefined structure on the whole sets of tasks and machines in the HC system, some of them behave like a consistent HC system. In order to effectively model real-life HC systems, the ETC prediction does not only account for the explicit running time of a task in a certain machine. Other relevant factors in parallel and distributed computing are also included in the performance estimation, such as the time needed to move the executable files to the target machine, the time needed to gather and transfer the input data for the computation, and eventual short communications. All these overheads are supposed to be included in the ETC estimation. |
|
HCSP |
|
Heterogeneous Computing Scheduling Problem |
|
Execution time estimation |