1 |
Explorations in grid workflow schedulingZheng, Wei January 2010 (has links)
Aiming at aggregating numerous distributed resources to provide immense computing power, Grid computing has emerged as a promising paradigm to run complex composite applications such as workflows. However, the inherent uncertainties of grid systems as well as the structural complexity of workflow applications make it extremely challenging to schedule workflows in an efficient way, regardless of whether the objective is to minimize execution time or meet specific user and/or system Quality of Service (QoS) requirements. For both these cases, this thesis considers scheduling problems motivated by grid uncertainties and advances the state-of-the-art by developing new techniques to address these problems.First, based on existing scheduling heuristics, a Monte-Carlo approach is developed to minimize the average makespan (i.e., the overall execution time) in the presence of task estimates exhibiting limited uncertainty in the form of (controlled) random behaviour. Next, a scenario where performance prediction is difficult to obtain and resource availability may vary over time, is considered. A low-cost efficient just-in-time heuristic is proposed to cope with grid uncertainties.After addressing these performance-driven scheduling problems, a QoS-driven problem, which considers not only the aforementioned uncertainties but also the uncertainty caused by queue-based scheduling, is examined. In order to tackle all these uncertainties, an integrated scheduling model consisting of three supportive techniques is developed. Extensive evaluation using simulation shows that the proposed techniques can achieve substantial improvements towards the ultimate goal of providing a good solution for QoS-driven workflow scheduling on the Grid.
|
2 |
A framework for grid-enabling scientific workflow systems : architecture and application case studies on interoperability and heterogeneity in support for grid workflow automationAzam, Nabeel Adeem January 2010 (has links)
Since the early 2000s, Service Oriented Architectures (SOAs) have played a key role in the development of complex applications within a virtual organization (VO) context. Grids and workflows have emerged as vital technologies for addressing the (SOA) paradigm. Given the variety of Grid middleware, scientific workflow systems and Grid workflows available, bringing the two technologies together in a flexible, reusable and generalized way has been largely overlooked, particularly from a scientific end user perspective. The lack of domain focus in this area has led to a slow uptake of Grid technologies. This thesis aims to design a framework for Grid-enabling workflows, which identifies the essential technological components, how these components fit together in layered architecture and the interactions between them. To produce such a framework, this thesis first investigates the definition of a Grid-workflow architecture and mapping Grid functionality to workflow nodes, focusing on striking a balance between performance, usability and the Grid functionality supported. Next, it presents an examination of framework extensions for supporting various forms of Grid heterogeneity, essential for ii VO based collaboration. Given the complex nature of Grid technologies, the work presented here investigates abstracting Grid based workflows through high-level definitions and resolution using semantic technologies. Finally, this thesis presents a way to resolves abstract Grid workflows using semantic technologies and intelligent, autonomous agents. The frameworks presented in this thesis are tested and evaluated within the context of domain-based case studies defined in the SIMDAT, BRIDGE and ARGUGRID EU funded research projects.
|
3 |
Towards effective and efficient temporal verification in grid workflow systemsChen, Jinjun, n/a January 2007 (has links)
In grid architecture, a grid workflow system is a type of high-level grid middleware
which aims to support large-scale sophisticated scientific or business processes in a
variety of complex e-science or e-business applications such as climate modelling,
disaster recovery, medical surgery, high energy physics, international stock market
modelling and so on. Such sophisticated processes often contain hundreds of
thousands of computation or data intensive activities and take a long time to
complete. In reality, they are normally time constrained. Correspondingly, temporal
constraints are enforced when they are modelled or redesigned as grid workflow
specifications at build-time. The main types of temporal constraints include upper
bound, lower bound and fixed-time. Then, temporal verification would be conducted
so that we can identify any temporal violations and handle them in time.
Conventional temporal verification research and practice have presented some
basic concepts and approaches. However, they have not paid sufficient attention to
overall temporal verification effectiveness and efficiency. In the context of grid
economy, any resources for executing grid workflows must be paid. Therefore, more
resources should be mainly used for execution of grid workflow itself rather than for
temporal verification. Poor temporal verification effectiveness or efficiency would
cause more resources diverted to temporal verification. Hence, temporal verification
effectiveness and efficiency become a prominent issue and deserve an in-depth
investigation.
This thesis systematically investigates the limitations of conventional temporal
verification in terms of temporal verification effectiveness and efficiency. The
detailed analysis of temporal verification effectiveness and efficiency is conducted
for each step of a temporal verification cycle. There are four steps in total: Step 1 -
defining temporal consistency; Step 2 - assigning temporal constraints; Step 3 -
selecting appropriate checkpoints; and Step 4 - verifying temporal constraints.
Based on the investigation and analysis, we propose some new concepts and develop
a set of innovative methods and algorithms towards more effective and efficient
temporal verification. Comparisons, quantitative evaluations and/or mathematical
proofs are also presented at each step of the temporal verification cycle. These
demonstrate that our new concepts, innovative methods and algorithms can
significantly improve overall temporal verification effectiveness and efficiency.
Specifically, in Step 1, we analyse the limitations of two temporal consistency
states which are defined by conventional verification work. After, we propose four
new states towards better temporal verification effectiveness. In Step 2, we analyse
the necessity of a number of temporal constraints in terms of temporal verification
effectiveness. Then we design a novel algorithm for assigning a series of finegrained
temporal constraints within a few user-set coarse-grained ones. In Step 3, we
discuss the problem of existing representative checkpoint selection strategies in
terms of temporal verification effectiveness and efficiency. The problem is that they
often ignore some necessary checkpoints and/or select some unnecessary ones. To
solve this problem, we develop an innovative strategy and corresponding algorithms
which only select sufficient and necessary checkpoints. In Step 4, we investigate a
phenomenon which is ignored by existing temporal verification work, i.e. temporal
dependency. Temporal dependency means temporal constraints are often dependent
on each other in terms of their verification. We analyse its impact on overall
temporal verification effectiveness and efficiency. Based on this, we develop some
novel temporal verification algorithms which can significantly improve overall
temporal verification effectiveness and efficiency. Finally, we present an extension
to our research about handling temporal verification results since these verification
results are based on our four new temporal consistency states.
The major contributions of this research are that we have provided a set of new
concepts, innovative methods and algorithms for temporal verification in grid
workflow systems. With these, we can significantly improve overall temporal
verification effectiveness and efficiency. This would eventually improve the overall
performance and usability of grid workflow systems because temporal verification
can be viewed as a service or function of grid workflow systems. Consequently, by
deploying the new concepts, innovative methods and algorithms, grid workflow
systems would be able to better support large-scale sophisticated scientific and
business processes in complex e-science and e-business applications in the context
of grid economy.
|
Page generated in 0.2757 seconds