دانلود مقاله ISI انگلیسی شماره 22014
ترجمه فارسی عنوان مقاله

DDS:الگوریتم زمان بندی تشخیص محور بلاتکلیفی برای محاسبات جریان کاری در سیستم HPC با محدودیت های ذخیره سازی

عنوان انگلیسی
DDS: A deadlock detection-based scheduling algorithm for workflow computations in HPC systems with storage constraints
کد مقاله سال انتشار تعداد صفحات مقاله انگلیسی
22014 2013 15 صفحه PDF
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Parallel Computing, Volume 39, Issue 8, August 2013, Pages 291–305

ترجمه کلمات کلیدی
جریان کاری محاسباتی - برنامه ریزی جریان کاری - همزمانی - محدودیت منابع ذخیره ساز تشخیص بن بست
کلمات کلیدی انگلیسی
Computational workflow, Workflow scheduling, Concurrency, Storage resource constraints, Deadlock detection
پیش نمایش مقاله
پیش نمایش مقاله  DDS:الگوریتم زمان بندی تشخیص محور بلاتکلیفی برای محاسبات جریان کاری در سیستم HPC با محدودیت های ذخیره سازی

چکیده انگلیسی

Workflow-based workloads usually consist of multiple instances of the same workflow, which are jobs with control or data dependencies, to carry out a well-defined scientific computation task, with each instance acting on its own input data. To maximize throughput performance, a high degree of concurrency is achievable by running multiple instances simultaneously. However, deadlock is a potential problem when storage is constrained. To address this problem, we design and evaluate a deadlock detection-based scheduling (DDS) algorithm that can achieve high performance by making the best use of the available storage resources. Our algorithm takes advantages of the dataflow information of the workflow to speculatively schedule each instance if the instant storage is sufficient for some constituent jobs, but not necessarily for the whole workflow instance. Whenever deadlock or a performance anomaly is detected, some selected in-progress workflow instances are required to be rollbacked to release storage for other blocked jobs. We develop a suite of strategies to select the victims and beneficiaries (instances or jobs) and evaluate their performance via a simulation-based study. Our results show that the DDS algorithm can adapt the job concurrency to the available storage resources and achieve higher performance than some deadlock avoidance methods in our synthetic and real workflow computations.

مقدمه انگلیسی

Many high-performance computing (HPC) and scientific workloads (i.e., the set of computations to be completed), such as those in bioinformatics [1] and [2], biomedical informatics [3], cheminformatics [4] and geoinformatics [5], are developed as a complex workflow that combines a variety of standalone application components (e.g., jobs) based on control or data dependencies. A particular workflow typically carries out a well-defined scientific computation. For example, the Proteome Analyst (PA) web service [2] has a multistage pipeline-like workflow that classifies a proteome in terms of its molecular function and subcellular localization. In reality, a scientific workload is often composed of multiple instances of the same workflow, with each instance acting on independent input files or different initial parameters [6], [7] and [8]. In our example, analyzing a proteome (i.e., all of the proteins in a given organism) may require one instance of the workflow (e.g., pipeline) for each protein in the proteome. Ideally, all of the workflow instances should be scheduled concurrently if their computations are inherently independent. However, in practice, there are a variety of resource constraints on, and challenges for, the scheduling policies. For example, simply maximizing the degree of concurrency (i.e., the number of jobs or processes that can be run during any moment in time) does not guarantee better performance if the number of processors is limited. In this paper, we consider the storage constraints. Although typical storage capacities at datacentres are rapidly increasing, the size of the data sets of the workflow-based computations is growing dramatically as well since a workflow-based task usually consists of a large number of independent instances of the same workflow for parameter space studies, and each instance may require a large amount of storage. For example, the Sextractor pipeline workflow1 has 2611 instances on the DPOSS dataset [9], with each pipeline instance accessing a different 1.1 GB image to search for bright galaxies. Another example is related to so-called Grid Data Streaming applications, such as the LIGO (Laser Interferometer Gravitational-Wave Observatory) workflow runs [10] at the Grid Physical Network, which produce data on the scale of terabytes per day, used to study cosmic gravitational waves. In these applications, most computational sites (e.g. Open Science Grid2) are processor-rich but storage-limited. Also, there are practical or system policy limits in some situations. For example, some queueing systems (e.g., NQE) provide users with options to specify multiple resource limits, including per-job and per-process limits on the permanent file size. Another example can be found in cloud-based scientific computing systems where the storage and other resources are typically provided as a service based on a principle of “pay-as-you-go” [11], [12] and [13]. This implies that inefficient storage utilization is not economical to the users of clouds. Consequently, storage management remains important [14] and [10], and storage-aware resource scheduling problem is still a major area of research [15] and [16]. In some cases, storage constraints are addressed by admission control to prevent deadlock which, in the most primitive sense, is a simple practice to discriminate which job or workflow instance can be admitted into execution in the first place [17]. More specifically, whenever the required storage space is available for a job or a workflow instance, the job or the instance is admitted to execution. However, this strategy is only feasible to schedule independent jobs and can be inefficient with storage utilization. For example, given a storage capacity of 3, the scheduler based on admission control might incur a deadlock when it schedules the two workflow instances shown in Fig. 1. The deadlock happens when the storage is allocated to X and Y (unit file sizes), the output files of Job A in the first workflow instance and Z, one of the output files of Job A in the second workflow instance. After Job A is completed in the first instance, Job B and Job C in the first instance cannot proceed because no storage resources are available for their outputs. The same happens to Job Ain the second instance.Since the job scheduler cannot, in general, control the amount of the storage for each workflow instance, the required maximal storage space is usually assumed. In our example, during a workflow instance execution, the storage resources for the intermediate files are not always reclaimed in time, and thus the maximal storage capacity 6 is used. However, the reservation of such an amount of storage for each workflow instance is not necessary and under-utilizes the storage to achieve high performance for the whole workload. In the example, the minimal number of 3 is sufficient for a workflow instance execution and 6 storage units can enable two instances to execute concurrently. To address this problem, one way is to require user or system administrator to pre-define the minimal storage requirements for each workflow instance in the workload. However, determining such minimal storage capacity is difficult and puts a substantial burden on the user or administrator. Our goal in this paper is to improve the scheduler’s performance, but still meet the given storage constraints. To this end, we present a workflow scheduling policy (algorithm), named deadlock detection-based scheduling (DDS), that can achieve high performance by making the best use of the available storage space. Our algorithm takes advantage of the dataflow information of the workflow to speculatively schedule each workflow instance whenever the instantaneous storage space is sufficient for some job executions (but not sufficient for the whole workflow instance). Whenever deadlock or a performance anomaly is observed, some selected in-progress workflow instances will be rollbacked to release the occupied storage for other discriminated blocked jobs. We develop a suite of strategies to select the victims and beneficiaries (workflow instances or jobs) and evaluate their performance via a simulation-based study. Although the basic idea of this algorithm is simple, the results can partially answer a less-noticed yet important practical question in workflow scheduling with storage constraints. We therefore believe that it will be particularly interesting for users in clouds and other HPC systems to strike a balance between the cost of storage resources and CPU resources to minimize the total budget while respecting the Service Level Agreement (SLA). The remainder of this paper is structured as follows: In the next section, we discuss some related work. Section 3 covers our workflow model. We present the DDS algorithm in Section 4 and its simulation results in Section 5. We conclude the paper in the last section.

نتیجه گیری انگلیسی

In this paper, we developed and optimized a deadlock detection and recovery algorithm named DDS for workflow-based batch scheduling. The detection component is based on the matrix-based algorithm and the essence of the recovery is reflected in two aspects: how much storage needs to be available for the recovery and how to choose the victims. Through simulation studies on three representative benchmark workloads, we investigated the impact of different amounts of available storage (i.e., from 0.25Bgt0.25Bgt to 1.00Bgt1.00Bgt) and different victim selection policies (i.e., LDF and Rnd) on the makespan performance, and found that the DDS algorithm with the overall best performance is the combination of 0.5Bgt_LDF0.5Bgt_LDF, meaning that half of the storage budget needs to be available after a deadlock has been detected and choosing the victim instances in the recovery is based on the well known LDF strategy. To evaluate the performance of the optimized DDS algorithm, we further compared it with two major deadlock avoidance algorithms, the classic Banker’s algorithm and its variant, Lang’s algorithm. Our simulation results show that the DDS algorithm is more efficient than deadlock avoidance algorithms in deadlock problem for workflow-based computations in HPC systems under storage constraints. Now that we have simulation-based evidence to support the DDS approach, the substantial work required to implement the full systems for representing, monitoring, and scheduling such workflow instances can be the subject of future work.