Search

There has been an increasing interest in running High Performance Computing (HPC) applications in the cloud, mainly due to rapid resource provisioning and significant reduction of operational costs. Biological sequence comparison is an important HPC application that compares sequences in search of similarities. MASA-OpenMP is a highly optimized sequence comparison tool that obtains optimal results. Yet, it can take a long time, depending on the number of sequences compared and their lengths. The Covid-19 pandemic study is of particular interest nowadays, and the comparison of SARS-CoV-2 sequences is crucial to understanding this disease. In this paper, we compare SARS-CoV-2 sequences with MASA-OpenMP in the Amazon Elastic Compute Cloud (Amazon EC2), using both spot and on-demand instances. To efficiently execute a MASA-OpenMP application composed of more than 22,000 tasks on EC2 respecting a given deadline, we propose an execution modeling for MASA-OpenMP on top of the Burst-HADS framework. Burst-HADS is a spot instance-based dynamic scheduler for Bag-of-Tasks applications in the cloud, which minimizes both execution time and financial costs regarding a given deadline even in the presence of spot interruptions. Performance results reveal that, by using spots, our Burst-HADS strategy considerably reduces the monetary cost for executing 22,600 SARS-CoV-2 sequence comparisons with MASA-OpenMP when contrasted to the on-demand only approach. We also show that our strategy can meet the deadlines, even in scenarios with several spot interruptions.

The adoption of container technology to deploy a diverse variety of applications in clusters, cloud data centers, and even cloudlets at the edge has steadily increased. Efficient resource utilization and throughput maximization are just two important objectives for service providers trying to reduce operating costs. While containers consume CPU, memory, and I/O resources elastically, orchestration frameworks must still allocate containers according to resource availability and limit the amount of resources that each can use to avoid interference. While the practice of reserving the maximum amount of required memory for the entire execution of a container is prevalent, this paper investigates the benefits of managing container memory allocations dynamically. By frequently adjusting the amount of memory reserved for each container during execution, this autonomous approach aims to increase the average number of containers that can be hosted on a server. Results show that through careful adjustments of container limits, manipulation of pages between memory and swap, and container preemption, improvements in memory utilization, cloud costs, and job throughput can be achieved without prejudicing container performance.

Optimization tasks are often complex, CPU-time consuming and usually deal with finding the best (or good enough) solution among alternatives for a given problem. Parallel metaheuristics have been used in many real-world and scientific applications to efficiently solve these kind of problems. Local Search (LS) is an essential component for some metaheuristics and, very often, represents the dominant computational effort accomplished by an algorithm. Several metaheuristic approaches try to adapt traditional LS models to parallel platforms without considering the intrinsic features of the available architectures. In this work, we present a novel local search strategy, so-called Distributed Variable Neighborhood Descent (DVND), specially designed for CPU and multi-GPU environment. Furthermore, a new neighborhood search strategy, so-called Multi Improvement, is introduced, taking advantage of GPU massive parallelism in order to boost up LS procedures. A hard combinatorial problem is considered as case of study, the Minimum Latency Problem (MLP). For tackling this problem, a hybrid metaheuristic algorithm is considered, which combines good quality initial solutions, generated by a Greedy Randomized Adaptive Search Procedures, with a flexible and powerful refinement procedure, inside the scope of an Iterated Local Search. The DVND was compared to the classic local search procedures, producing results that outperformed the best known sequential algorithm found in the literature. The speedups ranged from 7.3 to 13.7, for the larger MLP instances with 500 to 1000 clients. Results demonstrate the effectiveness of the proposed techniques in terms of solution quality, performance and scalability.

Among the methods to deal with optimization tasks, parallel metaheuristics have been used in many real-world and scientific applications to efficiently solve these kind of problems. This paper presents a novel Multi Improvement strategy for dealing with the Minimum Latency Problem (MLP), an extension the classic Traveling Salesman Problem. This strategy is embedded in a Graphics Processing Unit (GPU) local search procedure, in order to take advantage of the highly parallel processors from this architecture. In order to explore multiple neighborhoods simultaneously in a CPU/GPU heterogenous and distributed environment, a variant of the classic Variable Neighborhood Descent (VND) is also proposed, named Distributed VND (DVND). The DVND was inspired by a randomized version of the VND (called RVND) and a comparison was made, achieving competitive results in terms of solution quality. The variant of the DVND using two processes succeeded in achieving superlinear speedups up to 2.85, demonstrating that the DVND scalability and capability to explore both GPUs and CPUs. Finally, experiments demonstrate that the Multi Improvement is capable of finding better quality solutions in shorter computational times, when compared the classic Best Improvement strategy, motivating future applications in other hard optimization problems.

Server consolidation and resource elasticity are among two of the most important resource management features in cloud and edge computing. One of two forms of elasticity is often adopted. While horizontal elasticity is concerned with the acquisition and release of computational nodes in accordance with demand, vertical elasticity focuses on the distribution of a node's resources among its hosted virtual machines (VMs) or containers, by adjusting the capacity of the resource types allocated to each individual VM in accordance with its respective application's needs. In the case of vertical elasticity, when insufficient resources are available to allocate to a given VM, its application's performance may suffer degradation. For online applications, the only alternative is to live-migrate the VM to another server. On the other hand, when running batch jobs, the resource-constrained VM could also be suspended or saved to disk and revived elsewhere or on the same host, when resources become available. Given that memory availability has a significant influence on performance and system throughput, this paper investigates the viability of integrating VM migration, pausing and suspension schemes as part of a VM scheduling strategy to support the execution of both online and batch applications in a virtualized infrastructure employing memory elasticity. Results show that combining such schemes can provide utilization benefits for cloud service providers when memory is scarce.

The latest trends in high performance computing systems show an increasing demand on the use of a large scale multicore system in an efficient way so that high compute-intensive applications can be executed reasonably well. However, the exploitation of the degree of parallelism available at each multicore component can be limited by the poor utilization of the memory hierarchy. Actually, the multicore architecture introduces some distinct features that are already observed in shared memory and distributed environments. One example is that subsets of cores can share different subsets of memory. In order to achieve high performance, it is imperative that a careful allocation scheme of an application is carried out on the available cores, based on a scheduling specification that considers not only processors characteristics but also memory contention. This paper proposes a multicore cluster representation that captures relevant performance characteristics in multicores systems such as the influence of memory hierarchy and contention on application performance. Improved performance was achieved by a branch-and-bound application applied to the partitioning sets problem that incorporated a memory aware load balancing strategy based on the proposed multicore cluster representation. An in-depth analysis on this application execution showed its applicability to modern systems. Copyright ©2014 John Wiley & Sons, Ltd.

The dynamic nature of application and service requirements has lead the cloud community to invest in the study and development of elasticity features that have the ability to re-dimension resource capacities dynamically. Both online applications under unpredictable workloads or scientific workflows with different datasets require autonomic scaling in order to avoid either performance degradation due to an insufficient resource capacity or paying for additional, sub-utilized and possibly unnecessary capacity. In an effort to improve utilization, focus has recently turned to vertical elasticity where the processing, memory or storage capacity of a single virtual machine (VM) is adjusted in accordance with the application's needs. Given the increasing influence of memory availability on performance, this work presents the main features of the Memory Elasticity Controller (MEC). This VM allocation tool aims to improve the throughput of jobs or workflow tasks by continuously and judiciously calibrating the amount of host memory allocated to each VM in accordance with that VM's respective job's changing run time requirements while, at the same time, trying to avoid compromising the job's performance. This paper presents the tool's architecture and describes the functionality adopted to manage and provide vertical memory elasticity to concurrently executing VMs on a server. Results show that MEC is able to provide both resource providers and applications with an additional opportunity to improve throughput and performance.

In combinatorial optimization problems, the neighborhood search (NS) is a fundamental component for local search based heuristics. It consists of selecting a solution from a high cardinality set of neighbor solutions, by means of operations called moves. To perform this search, NS algorithms usually adopt two main approaches: selecting the first or best improving move. The Multi Improvement (MI) strategy is a recently proposed method that consists in exploring simultaneously multiple move operations during the NS phase aiming to reach good quality solutions with shorter computational steps. This paper presents a benchmark for MI strategies in hybrid CPU/GPU systems. This technique efficiently explores the CPU processing power together with the massive parallelism achieved by modern GPUs, emerging as an efficient alternative for classic CPU neighborhood search strategies. The advantage of this approach depends heavily on finding the best tradeoff between CPU and GPU processing, as well as minimizing the memory transfers involved in the process. In the experiments, several MI configurations were tested in a hybrid CPU/GPU environment presenting better results than classical neighborhood search strategies for the Minimum Latency Problem, a hard combinatorial optimization problem.

The adoption of the same cluster-based programming strategies for grid applications, although requiring minimal effort from a programmer’s point of view, does not always take ad vantage of the available computational resources to their fullest extent. This paper investigates on the impact of a distributed and hierarchical autonomic strategy on the performance of parallel metaheuristics to solve hard combinatorial optimization problems on grids. Two problems, the mirrored traveling tournament problem and the bounded diameter minimum spanning tree problem, for which high quality sequential heuristics based on the paradigms of the GRASP and ILS metaheuristics already exist, are employed as case-studies. The computational results obtained on a grid by the novel autonomic strategy show that outstanding performance improvements over the traditional master-worker parallelization approach can be achieved.

This paper proposes the Makespan and Reliability Cost Driven (MRCD) heuristic, a static scheduling strategy for heterogeneous distributed systems that not only minimizes the makespan, but also maximizes the reliability of the application. The MRCD scheduling decisions are guided by a weighted function that considers both objectives simultaneously, instead of prioritizing one of them. This work also introduces a classification of the solutions produced by weighted bi-objective schedulers to aid users to tune the weighting function such that an appropriate solution can be selected in accordance with their needs. In comparison with the related work, MRCD produced schedules with makespans that were significantly better then those produced by the other strategies at expense of an insignificant deterioration in reliability.

The execution of distributed applications on the Grid is already a reality. However, as both the number of applications grow and Grids increase in scale, the efficient utilization of the available but shared heterogeneous resources will become increasingly essential to the Grid's successful maturity. Furthermore, it is unclear whether existing Grid management systems are capable of meeting this challenge. The EasyGrid middleware is a hierarchically distributed application management system (AMS) that is embedded into MPI applications to autonomously orchestrate their execution efficiently in computational Grids. The overhead of employing a distinct AMS to make each application system aware brings at least two benefits. First, the adopted policies can be tailored to the specific needs of each application, leading to improved performance. Second, distributing the management effort among executing applications makes Grid management more scalable. This article focuses on scheduling policies of an AMS for a particular class of application, describing a low intrusion implementation of a hybrid scheduling strategy designed to elicit good performance even in dynamic environments such as Grids. Using application-specific scheduling policies, near-optimal runtimes highlight the advantages of self-scheduling when executing one or more system aware applications on a Grid. Copyright © 2006 John Wiley & Sons, Ltd.

Parallel applications composed of a set of tasks that follow a partial precedence order represent an important class of scientific applications. In high performance computing, environments dedicated to scientific applications are composed of clusters of multicore machines, which consist typically of a set of processing cores that partially share a hierarchy of cache memory. Harnessing the available memory is crucial to achieve good performance in these clusters. This paper proposes strategies based on the list scheduling framework to schedule application tasks on individual cores of multicore clusters. Our idea is to minimize the execution time of the application, by taking into consideration cache contention. Experiments with a representative set of applications show that the scheduling algorithms with contention-aware mechanisms can improve significantly the application performance.

One of the goals of the Grid is to aggregate collections of shared, heterogeneous, and distributed resources to provide computational ‘power’ to parallel applications. However, designing applications capable of exploiting this potential with ease remains a challenge. This paper outlines the EasyGrid methodology for the efficient and robust execution of (legacy) MPI programs across distributed computing clusters. The principal objective of this work is to identify the application-oriented middleware necessary for, as well as to develop a framework to automatically generate, system-aware applications capable of executing in dynamic, unstable, distributed environments such as computational Grids. Copyright © 2004 John Wiley & Sons, Ltd.

Task scheduling is a key element in achieving high performance from multicomputer systems. Efficient scheduling algorithms reduce the interprocessor communication and improve processor utilization. To do so effectively, such algorithms must be based on a communication cost model appropriate for computing systems in use. The optimal scheduling of tasks is NP-hard, and a large number of heuristic algorithms have been proposed for a range of differing scheduling conditions (graph types, granularities and cost or architectural models). Unfortunately, due both to the variety of systems available and the rate at which these systems evolve, an appropriate representative cost model has yet to be established. In this paper we study the problem of task scheduling under a LogP-type model and we present both theoretical and experimental results for a cluster-based, task duplication methodology. The model is not only representative of parallel systems but also incorporates the traditional model used by the scheduling community. Results show that, for this model, an algorithm based on this LogP scheduling methodology can generate good makespans.

While the task scheduling problem under the delay model has been studied extensively, relatively little research exists for more realistic communication models such as the LogP model which considers, in addition to latency, the cost of sending and receiving messages, and the network or link capacity. The task scheduling problem is known to be NP-complete even under the delay model (a special case of the LogP model). This paper investigates the similarities and differences between task-clustering algorithms for the delay and LogP models, and describes task-scheduling algorithm for the allocation of arbitrary task graphs to fully connected networks of processors under the LogP model. The strategy exploits the replication and clustering of tasks to minimize the ill effects of communication overhead on the makespan. A number of restrictions are presented which are used to simplify the design of the new algorithm. The quality of the schedules produced by the algorithm compare favorably with two well-known delay model-based algorithms and a previously existing LogP strategy.

In general, scheduling models only consider the message delay or latency as the dominant communication parameter. However, in many of the current generation of parallel systems, latency is negligible compared to the CPU penalties for the communication-related activities that are incurred whenever pairs of dependent tasks on distinct processors need to communicate. This work considers a model where the CPU penalty , which is associated with sending and receiving, communication events , is an additional (potentially dominant) communication parameter. A multi-stage scheduling approach (MSA) is proposed which takes both of these types communication parameters into account. This scheduling approach can be customised to classes of parallel systems according to their communication performance characteristics by varying the order in which the rules (which guide the strategy) are applied.

During their execution, a significant number of applications often sub utilize the capacity of the resources to which they are allocated or require more. Furthermore, with the current scale up trend in server design, effective utilization can only be achieved by applications sharing such resources. Cluster management systems already support static resource partitioning at job submission time and given that application utilization more than often varies during the execution, it will become increasingly more important to permit applications to harness all available spare capacity. This paper investigates the feasibility of malleable evolving versions of applications to improve performance and system efficiency. Extending a previous classification, we show that improvements can be achieved for a real astrophysics application.

Multicore architectures are an important contribution in computing technology since they are capable of providing more processing power with better cost-benefit than single-core processors. Cores execute instructions independently but share critical resources such as L2 cache memory and data channels. Clusters using multicore architectures or multiprocessors chips (MPC's) suggest a hierarchical memory environment. Parallel applications should take advantage of such memory hierarchy to achieve high performance. This paper presents a performance analysis of a synthetic application in a multicore cluster and introduces a preliminary architecture model that considers communication through both shared memory and data channels and its impact on the application performance.

This paper proposes the Makespan and Reliability Cost Driven (MRCD) heuristic, a static scheduling strategy for heterogeneous distributed systems that not only minimizes the makespan but also maximizes the reliability of the application. The scheduling decisions made by MRCD are guided by a weighted function that considers both objectives simultaneously instead of prioritizing only one of the objectives. This work also introduces a classification of the solutions produced by weighted bi-objective schedulers to aid users to tune the weighting function in order to generate an appropriate solution in accordance with their needs. In comparison with related work, MRCD produced schedules with makespans that were significantly better then those produced by other strategies at expense of an insignificant deterioration in reliability.

Grid and Internet Computing have proved their worth executing large-scale bag-of-task class applications. Numerous middlewares have been developed to manage their execution in either dedicated environments or opportunistic and shared ad-hoc grids. While job dependencies are now being resolved by middleware capable of scheduling workflows, these environments have yet to be shown beneficial for message passing parallel applications. Obtaining high performance in these widely available environments without rewriting existing parallel applications is of up most importance to e-Science . The key to an efficient solution may be an alternative execution model and the efficient dynamic scheduling of application processes. This paper presents a hierarchical scheme for dynamically scheduling parallel DAG applications across a set of non-dedicated heterogeneous resources. In order to efficiently tackle process dependencies and adapt to varying system characteristics, dynamic schedulers are distributed within the application and operate in a collaborative and pro-active fashion to keep overheads low.

As grids are in essence heterogeneous, dynamic, shared and distributed environments, managing these kinds of platforms efficiently is extremely complex. Few transparent grid management systems have been developed to cope with these characteristics simultaneously and therefore both new and existing applications must be modified to execute efficiently. A promising scalable approach to deal with these intricacies is the design of self-managing or autonomic applications. Autonomic applications adapt their execution accordingly by considering knowledge about their own behaviour and environmental conditions. This paper focuses on the dynamic scheduling that provides the self-optimizing ability in autonomic applications. Being distributed, collaborative and pro-active, the proposed hierarchical scheduling infrastructure addresses important issues to enable an efficient execution in a computational grid. Unlike other approaches, the cooperative, hybrid and application-specific strategy deals effectively with task dependencies. Several experiments have been analyzed in real grid environments highlighting the efficiency and scalability of the proposed infrastructure. This paper presents an intra-site dynamic scheduling heuristic for tightly coupled parallel applications represented by DAGs.

This paper addresses the challenge of how to permit tightly coupled parallel applications, optimised for uniform, stable, static environments, execute equally efficiently in environments which exhibit the complete opposite characteristics. Using the N-body problem as a case study, both the traditional and proposed grid enabled MPI implementations of the popular ring algorithm are analysed. Results with respect to performance show the latter approach to be competitive on a cluster and significantly more effective in heterogeneous and dynamic environments.

Metaheuristics are general high-level procedures that coordinate simple heuristics and rules to find good approximate solutions to computationally difficult combinatorial optimization problems. Parallel implementations of metaheuristics appear quite naturally as an effective approach to speedup the search for approximate solutions. Besides the accelerations obtained, parallelization also allows solving larger problems or finding better solutions. We present in this work four slightly differing strategies for the parallelization of an extended GRASP with ILS heuristic for the mirrored traveling tournament problem, with the objective of harnessing the benefits of grid computing. Computational experiments on a dedicated cluster illustrate the effectiveness and the scalability of the proposed strategies. In particular, we show that the parallel strategy implementing cooperation through a pool of elite solutions scales better than the others and is able to find solutions that cannot be reached by the others. Computational grids are distributed high latency environments which offer significantly more computing power than traditional clusters. The best parallel strategy was also implemented and tested using a true grid platform. We report original results from pioneer computational experiments on a shared computational grid formed by 82 machines distributed over four clusters in three cities, illustrating the potential of the application of computational grids in the fields of metaheuristics and combinatorial optimization.

This paper proposes an algorithm for the adaptive adjustment of the transmission rate of VoIP sources based on the voice quality estimated at the receiver. This adjustment is achieved through the appropriate use of differing voice codecs, as the conditions of the network change, in order to maintain an efficient utilization of the available resources. To validate our proposal realistically, we have made an effort to simulate VoIP calls using sources that follow Brady's model of human conversations. We investigate the effects of the proposed model on the aggregate network traffic and compare the results with existing related work. Simulation results show that the proposed algorithm makes better use of the available bandwidth, achieving superior performance in comparison to similar works.

The MPI message passing library is used extensively in the scientific community as a tool for parallel programming. Even though improvements have been made to existing implementations to support execution on computational grids, MPI was initially designed to deal with homogeneous, fault- free, static environments such as computing clusters. The typical programming approach is to execute a single MPI process on each resource. However, this may not be appropriate for heterogeneous, non-dedicated and dynamic environments such as grids. This paper aims to show that programmers can implement parallel MPI solutions to their problems in an architectural independent style and obtain good performance on a grid by transferring responsibility to an application management system (AMS). A comparison of program implementations under a traditional MPI execution model and a fine-grain model highlight the advantages of using the latter.

This paper proposes an algorithm for the adaptive adjustment of the transmission rate of VoIP sources based on the voice quality estimated at the receptor. This adjustment is achieved through the appropriate use of differing voice codecs as the conditions of the network change, with the aim at maintaining an efficient utilization of the available resources. In order to validate our proposal, we have made an effort to simulate more realistic VoIP calls using sources that follow Brady's model of human conversations. We investigate the effect of the proposed model on the aggregate network traffic and compare the results with existing related work, most of which employ simplified models. Simulation results show that the proposed algorithm makes efficient use of the available bandwidth, achieving superior performance in comparison to similar works from the literature.Este artigo propoe um algoritmo para o ajuste adaptativo da taxa de transmissao de fontes VoIP com base na qualidade da voz estimada pelo receptor. O ajuste e realizado atraves da utilizacao de diferentes codificadores, dependendo das condicoes da rede, visando fazer uso de forma eficaz dos recursos disponiveis. Na validacao de nossa proposta, realizamos simulacoes buscando modelar os ambientes de chamadas VoIP de uma forma realistica. Para isso utilizamos fontes VoIP baseadas no modelo de Brady de uma conversacao humana. Os efeitos da modelagem e do algoritmo proposto sobre o tr´fego agregado de uma rede de dados foram analisados, atraves da comparacao dos resultados obtidos com trabalhos relacionados que utilizam modelos simplificados. Esses resultados mostram que o algoritmo proposto consegue aproveitar de forma eficaz a banda disponivel, e apresenta um desempenho superior a trabalhos similares da literatura.

Computational grids aim to aggregate significant numbers of resources to provide sufficient, but low cost, computational power to an ever growing variety applications. Writing applications capable of executing efficiently in these grid environments is however extremely difficult for inexperienced users. The grid's geographically distributed resources are typically heterogeneous, non-dedicated, and are offered without any performance or availability guarantees. This work investigates an alternative approach (based on smarter system-aware applications) to solve the problem of developing and managing the execution of grid applications efficiently. Results show that these system-aware MPI applications are indeed faster than their conventional implementations and easily grid enabled.

The execution of distributed applications on the grid is already a reality. As both the number of applications grow and grids scale, efficient utilization of the available but shared heterogeneous resources will be essential. The EasyGrid middleware is a hierarchically distributed Application Management System embedded into MPI applications to facilitate their efficient execution in computational grids. The overhead of employing a distinct AMS to make each application system aware does however bring at least two benefits. First, the (scheduling) policies adopted can be tailored to the specific needs of each application leading to improved performance. Second, distributing the management effort amongst the applications themselves makes grid management more scalable. This paper describes a low intrusion implementation of a hybrid scheduling strategy designed to cope with the dynamic behaviour of grid environments. Using application-specific scheduling policies, near-optimal runtimes highlight the advantages of self-scheduling when executing one or more system aware applications on a grid.

Efficient task scheduling is fundamental for parallel applications to achieve good performance on distributed systems. While extensive work exists for scheduling tasks on homogeneous processors, fewer algorithms exist for the more common problem of scheduling in heterogeneous processor environments. In this paper, we propose coupling a replication-based clustering heuristic for homogeneous processors, with a mechanism to map the generated clusters to the heterogeneous environment. Experimental results show that this strategy compares favourably in terms of the makespan with traditional list scheduling approaches to this problem, particularly when communication costs are high.

Researchers are constantly looking for ways to improve the execution time of parallel applications on distributed systems. Although compile-time static scheduling heuristics employ complex mechanisms, the quality of their schedules are handicapped by estimated run-time costs. On the other hand, while dynamic schedulers use actual run-time costs, they have to be of low complexity in order to reduce the scheduling overhead. We investigate the viability of integrating these two approaches into a hybrid scheduling framework. The relationship between static schedulers, dynamic heuristics and scheduling events are examined. The results show that a hybrid scheduler can indeed improve the schedules produced by good traditional static list scheduling algorithms.

One of the objectives of computational grids is to offer applications the collective computational power of distributed but typically shared heterogeneous resources. Unfortunately, efficiently harnessing the performance potential of such systems (i.e. how and where applications should execute on the grid) is a challenging endeavor due principally to the distributed, shared and heterogeneous nature of the resources involved. This paper presents a tool to aid the design and evaluation of scheduling policies suitable for efficient execution of parallel applications on computational grids.

Task scheduling is a key element in achieving high performance from multicomputer systems. To be efficient, scheduling algorithms must be based on a cost model appropriate for computing systems in use. The optimal scheduling of tasks is NP-hard, and a large number of heuristic algorithms have been proposed for a variety of scheduling conditions (graph types, granularities or cost models). This paper studies the problem of task scheduling under the LogP model and presents both theoretical and experimental results for a cluster-based, task duplication methodology.

While the NP-complete problem of scheduling weighted arbitrary directed acyclic graphs under the delay model has been studied extensively, comparatively little work exists for this problem under more realistic models such as the LogP model. Recently, a number of LogP-based scheduling heuristics and related works have appeared in the literature, including a task clustering algorithm design methodology which identifies four crucial design issues (Boeres et al., 1997). Through the use of five task replication-based scheduling heuristics based on this design methodology, this paper investigates the effect of various implementations of these design issues on the schedules produced for the allocation of arbitrary task graphs to fully connected networks of processors under a LogP-type model. The quality of the schedules produced by these algorithms are also compared with good, well-known delay model-based algorithms and an existing LogP strategy.

While the task scheduling problem under the delay model has been studied extensively, relatively little research exists for more realistic communication models such as the LogP model. The task scheduling problem is known to be NPcomplete even under the delay model (a simplified instance of the LogP model). This chapter describes the LogP model and the influence of its communication parameters on task scheduling. The similarities and differences between clustering algorithms under the delay and LogP models are discussed and a design methodology for clustering-based scheduling algorithms for the LogP model is presented. Using this design methodology, a task scheduling algorithm for the allocation of arbitrary task graphs to fully connected networks of processors under LogP model is proposed. The strategy exploits the replication and clustering of tasks to minimize the ill effects of communication on the makespan.

This paper briefly describes the mechanisms used to reduce the number of processors required by a class of task replication-based scheduling heuristics for the LogP model. These heuristics, which are based on the task clustering algorithm design methodology [3], are known to generate schedules with good makespans [3,5]. Results in this paper show that a significant reduction, on average, in the number of processors required can be obtained without degrading the makespan. These mechanisms can also be used to tradeoff quality in terms of an increase in the makespan for quantity in terms of a further reduction in the number of processors required.

While the problem of scheduling weighted arbitrary DAGs under the delay model has been studied extensively, comparatively little work exists for this problem under a more realistic model such as LogP. This paper investigates the similarities and differences between task clustering algorithms for the delay and LogP models. The principles behind three new algorithms for tackling the scheduling problem under the LogP model are described. The quality of the schedules produced by the algorithms are compared with good delay model-based algorithms and a previously existing LogP strategy.

This paper investigates the effect of communication overhead on the scheduling problem. We present a scheduling algorithm, based on LogP-type models, for allocating task graphs to networks of processors. The makespans of schedules produced by our multi-stage scheduling approach (MSA) are compared with other well-known scheduling heuristics. The results indicate that new classes of scheduling heuristics are required to generate efficient schedules for realistic abstractions of today’s parallel computers. The scheduling strategy of MSA can also be used to generate BSP-structured programs from more abstract representations. The performance of such programs are compared with “conventional” versions.

In general, scheduling models only consider message latency as the sole dominant communication parameter. However, in many parallel systems, latency is negligible when compared to the CPU penalties associated with sending and receiving communication events. Our work considers a model in which this CPU penalty can also be a significant communication parameter. This paper focusses on analysing the effect of such a model on the scheduling of Full Binary Trees. We briefly describe a versatile, multi-stage scheduling approach that can be customised to classes of parallel systems according to their communication performance characteristics and which produces better makespans when compared with traditional techniques.

Superficially, the Earliest Task First (ETF) heuristic [1] is attractive because it models heterogeneous messages passing through a heterogeneous network. On closer inspection, however, this is precisely the set of circumstances that can cause ETF to produce seriously sub-optimal schedules. In this paper we analyze the scope of applicability of ETF. We show that ETF has a good performance if messages are short and the links are fast and a poor performance otherwise. For the first application we choose the Diamond DAG with unit execution time for each task and the multiprocessor system in the form of the fully connected network. We show that ETF partitions the DAG into lines each of which is scheduled on the same processor. The analysis reveals that if the communication times between pairs of adjacent tasks in a precedence relation are all less than or equal to unit then the schedule is optimal. If the communication time is equal to the processing time needed to evaluate a row then the completion time is O(√n) times more than the optimal one for an n×n Diamond DAG. For the second application, we choose the join DAG evaluated by two connected processors.

Effective tools for the design of parallel algorithms must be based on a computational model for parallel computing that is a trade-off between realism and simplicity. Where the underlying programming model requires the mapping and scheduling of tasks, the computational model should incorporate some notion of interprocessor communication delay. If the target architecture is massively parallel then a more complex model, including some notion of locality, may be required.

Computational grids aim to aggregate significant numbers of resources to provide sufficient, but low cost, computational power to various applications. Writing applications capable of executing efficiently in grids, is however extremely difficult. Their geographically distributed resources are typically heterogeneous, non-dedicated, and offer no performance or availability guarantees. This makes the collective management of resources and application both complex and arduous. This work investigates an alternative approach (based on system-awareness) to solve the problem of developing and managing the execution of grid applications efficiently. Results show that these system-aware applications are indeed faster than their conventional implementations and easily grid enabled.

The complexity of the static scheduling problem on heterogeneous resources has motivated the development of low complexity heuristics such as list scheduling. However, the greedy characteristic of such heuristics can, in many cases, generate poor results. This work proposes the integration of list scheduling heuristics with search mechanisms based on both genetic algorithms and GRASP, to efficiently schedule tasks on distributed systems. The results show that the hybrid approach is robust and can converge quickly to good quality solutions.