Nowadays heterogeneous architectures formed by multicore and manycore systems have become attractive solutions to cope with the data booming in genomic-based studies. Our work explores the efficient usage of heterogeneous architectures in such area. In particular, we have studied the use of manycore components like the Xeon Phi accelerator, which has proved to be a convenient choice because it allows an easy migration of applications developed for multicore servers based on the × 86 architecture. Our study also focuses on the problem of sequence alignment, which is one of the fundamental and most costly computational stages in most genome variant studies. We concentrate our attention on BWA, one of the most popular sequence aligners, and we have focused our attention on three types of heterogeneous systems, one containing Intel multi-core CPUs and accelerators, one that are made up of several multi-core servers, and one large-scale system. Each with different characteristics in terms of number of CPUs, number of cores and system organization memory. Although the problem of alignment of sequences fits in the embarrassingly parallel pattern, achieving good performance and good scalability in heterogeneous environments can be complex. We have analyzed different strategies based on the distribution of data and the replication of certain data structures and we found that MDPR (Multi-level Data Parallelization and Replication) strategy has shown the best results in all the heterogeneous platforms tested. Its results have surpassed other strategies proposed in the literature and have shown its malleability to be used in different heterogeneous environments without the need to apply specific adjustments according to the underlying architecture. In the design of MDPR, different static and dynamic data distribution strategies have also been evaluated. The best results were obtained by the static strategy, which has a significant preprocessing cost. However, the dynamic strategy of data distribution using a round-robin mechanism obtained similar times without the need for the preprocessing stage. Although our proposal was applied to BWA using human genome data samples, this strategy can be easily applied to other sequence datasets and alignment tools that have similar operating principles with those of BWA aligner.

International audience

Nowadays distributed applications, including MPI implementations, are executed on computer clusters managed by a batch queue system. Users take advantage of monitoring tools to detect run-time problems on their applications running on those environments. But it is a challenge to use monitoring tools on a cluster controlled by a batch queue system. This is due to the fact that batch queue systems and monitoring tools do not coordinate the management of the resources they share, when executing a distributed application. We name this problem lack of interoperability and to solve it we have developed a framework called TDP-Shell. This framework supports different batch queue systems such as Condor and SGE, and different monitoring tools such as Paradyn, Gdb and Total view, without any changes on their source code. In this paper we describe how our basic design of TDP-Shell for sequential applications was re-designed to support the monitoring of MPI applications that are executed on a cluster controlled by a batch queue system.

Workflow applications exhibit both high computation times and data transfer rates. For this reason, the completion time of the workflow is high. To reduce completion time, the tasks of a workflow ought to run on different machines interconnected by a network. Correct assignment of tasks to machines within the runtime environment is an important aspect in the completion time or make span. The manager making the assignment is the scheduler. The main problem of a static scheduler is that it ignores the changes that occur in the execution environment during DAG execution. To solve this problem, we developed a new dynamic scheduler. This dynamic scheduler monitors the behavior of the tasks executed as well as the execution environment, and it reacts to the changes detected by adapting the scheduling of the rest of pending tasks. The objective is to reduce the overhead incurred by excessive self-adaptations, without affecting the make span. To reduce overhead, the algorithm self-adapts only when an improvement in make span is expected. The proposed policies have been simulated and then executed in a real environment. These executions have achieved a reduction of the overhead of greater than 20%.

A fundamental problem in large scale Grids is the need for efficient and scalable techniques for resource discovery and scheduling. In traditional resource scheduling systems a single scheduler handles information about all computing resources and schedules jobs. This centralized approach has a serious scalability problem, since it introduces a bottleneck, as well as a single point of failure. Some decentralized scheduling systems have been proposed to improve scalability. However, the main contributions in this area are generally carried out under the assumption of several coordinated schedulers. Nevertheless this approach leads to high communication costs. Such costs are mainly caused by the strong dependency on negotiation among scheduler-to-scheduler and scheduler-to-resource communication. Current approaches to decentralized resource management - in particularly approaches based on Random Early Detection (RED) - are non-coordinated since these schedulers make scheduling related decisions in an independent way. This paper introduces a collaborative model of decentralized scheduling that improves resource scheduling based on RED strategies via gossiping. With this approach, schedulers can receive information from other schedulers without creating a high communication overhead and continue scheduling jobs in an independent way. The simulation results shows that our proposal is scalable and it handles large resources efficiently on large scale Grids.

Most recent grid middleware technologies have been aimed at the execution of sequential batch jobs. However, some users require interactive access when running jobs on grid sites. Execution of these applications on a grid environment is a challenging problem that requires the cooperation of several middleware tools and services. Additional problems arise when this interactive support is intended for parallel applications, which may run remotely across several sites. We provide transparent and reliable support for such applications. Our solution, based on the notion of split execution and interposition agents, allows running applications on a remote machine while some I/O operations are sent back to a home machine. The paper describes how we have applied interposition agents transparently to interactive applications and also describes a simple multiprogramming mechanism that is used to start interactive applications as fast as possible even under heavy occupancy of resources. We provide a performance evaluation of the key elements involved in the execution of interactive jobs

Scheduling is an important factor for the efficient execution of computational workflows on grid environments. A large number of static scheduling heuristics has been presented in the literature. These algorithms allocate tasks before job execution starts and assume a precise knowledge of timing information, which may be difficult to obtain in general. To overcome this limitation of static strategies, dynamic scheduling strategies may be needed for a changing environment such as the grid. While they incur runtime overheads, they may better adapt to timing changes during job execution. In this work, we analyse five well-known heuristics (min-min, max-min, sufferage, HEFT and random) when used as static and dynamic scheduling strategies in a grid environment in which computing resources exhibit congruent performance differences. The analysis shows that non-list based heuristics are more sensitive than list-based heuristics to inaccuracies in timing information. Static list-based heuristics perform well in the presence of low or moderate inaccuracies. Dynamic versions of these heuristics may be needed only in environments where high inaccuracies are observed. Our analysis also shows that list-based heuristics significantly outperform non-list based heuristics in all cases and, therefore, constitute the most suitable strategies by which to schedule workflows either statically or dynamically

Run-time tools are crucial to program development. In our desktop computer environments, we take for granted the availability of tools for operations such as debugging, profiling, tracing, checkpointing, and visualization. When programs move into distributed or Grid environments, it is difficult to find such tools. This difficulty is caused by the complex interactions necessary between application program, operating system and layers of job scheduling and process management software. As a result, each run-time tool must be individually ported to run under a particular job management system; for m tools and n environments, the problem becomes an m \times n effort, rather than the hoped-for m + n effort. Variations in underlying operating systems can make this problem even worse. The consequence of this situation is a paucity of tools in distributed and Grid computing environments. In response to the problem, we have analyzed a variety of job scheduling environments and run-time tools to better understand their interactions. From this analysis, we isolated what we believe are the essential interactions between the run-time tool, job scheduler and resource manager, and application program. We are proposing a standard interface, called the Tool Dæmon Protocol (TDP) that codifies these interactions and provides the necessary communication functions. We have implemented a pilot TDP library and experimented with Parador, a prototype using the Paradyn Parallel Performance tools profiling jobs running under the Condor batch-scheduling environment.

We investigate the scheduling problem that arises in parallel applications executing on a network of machines by using a mode of cycle-stealing. In this mode of execution a parallel application executes its tasks in several machines whenever they are idle. When the user reclaims the machine, tasks must relinquish control immediately. In this case, the parallel application has the risk of losing work in progress on reclaimed machines and, therefore, the total execution time of the parallel application will be affected by the need for rescheduling the pre-empted task. We first evaluate the impact on the performance of an application when it runs on two different scenarios: a set of N dedicated machines, and a set of N non-dedicated machines (in which pre-emption may occur). This study shows that losing machines may have a considerable impact on the execution time of the application and therefore, we propose and evaluate three simple strategies to alleviate this problem. All strategies are based on the use of additional machines, but they differ in the way that these extra machines are used. In the first strategy additional machines are added to the common pool of machines used by the application. The other two are based on task replication, in which the additional machines are used to execute certain tasks that are already running in other machines.

We present a new fully distributed dynamic load balancing algorithm called DASUD (Diffusion Algorithm Searching Unbalanced Domains). Since DASUD is iterative and runs in an asynchronous way, a mathematical model that describes DASUD behaviour has been proposed and has been used to prove DASUD's convergence. DASUD has been evaluated by comparison with another well known strategy from the literature, namely, the SID (Sender Initiated Diffusion) algorithm. The comparison was carried out by considering a large set of load distributions which were applied to ring, torus and hypercube topologies, and the number of processors ranged from 8 to 128. From these experiments we have observed that DASUD outperforms the SID strategy as it provides the best trade-off between the global balance degree obtained at the final state and the number of iterations required to reach such a state.