Workflow scheduling is a well-known NP-complete problem with broad applications and increasing importance. In this paper, we present a heuristic-based algorithm, called FPPTS, which uses a new ranking method in the task ranking phase, prioritizing tasks according to their full paths from the entry task to the exit task. Experimental results show that FPPTS excels at workflows of high CCR running in heterogeneous computing environments, significantly outperforming HEFT and IPPTS. For example, in experiments with 30-task and 10-CCR workflows running on 10 processors, FPPTS shows an average performance improvement of 15.93% compared to IPPTS. The excellent performance of FPPTS indicates a promising direction for future workflow scheduling research.

Workflow computing has become an essential part of many scientific and engineering fields, while workflow scheduling has long been a well-known NP-complete research problem. Major previous works can be classified into two categories: heuristic-based and guided random-search-based workflow scheduling methods. Monte Carlo Tree Search (MCTS) is a recently proposed search methodology with great success in AI research on game playing, such as Computer Go. However, researchers found that MCTS also has potential application in many other domains, including combinatorial optimization, task scheduling, planning, and so on. In this paper, we present a new workflow scheduling approach based on MCTS, which is still a rarely explored direction. Several new mechanisms are developed for the major steps in MCTS to improve workflow execution schedules further. Experimental results show that our approach outperforms previous methods significantly in terms of execution makespan.

Summary This paper presents a Platform of Extensible Workflow Simulation Service (Pewss), which we have developed to provide a cloud service for aiding research work in workflow scheduling. The simulation has been a major tool for performance evaluation and comparison in workflow scheduling research. However, researchers usually have to develop their own simulation programs with limited functionality, simply outputting summarized performance results. Pewss has been developed for easing and improving current practices in conducting performance simulations during studying of existing workflow scheduling algorithms or designing of new scheduling algorithms. Pewss has been designed based on the Software as a Service (SaaS) model, adopting a multiuser Web‐based client/server architecture. Conducting simulation experiments on Pewss, researchers simply have to implement the scheduling algorithm under study instead of a whole simulation environment, allowing them to focus on their research work without spending unnecessary efforts on the simulation implementation details. Pewss provides the visualization of a workflow execution schedule based on simulation results, offering a convenient way for researchers to gain an insight into the effectiveness, characteristics, and performance bottleneck of scheduling algorithms. As a multiuser environment, Pewss also provides functionality for researchers to facilitate comparative performance analysis and collaborative research works effectively. Pewss has been used in our research work on task‐parallel workflow scheduling and has been planned to be extended to support other types of workflow scheduling research problems, eg, mixed‐parallel workflows.

Cloud computing has caused a revolution in our way of developing and using software. Software development and deployment based on the new models of Software as a Service (SaaS) and Service-Oriented Architecture (SOA) are expected to bring a lot of benefits for users. However, software developers and service providers have to address new challenging issues before such benefits can be realized. This paper explores one of the critical issues, service deployment, for reducing execution time of composite SaaS applications, and proposes an integrated approach to the service deployment problem which takes not only inter-service communication costs but also the potential parallelism among services into consideration. In the approach, two types of graphs are developed to model the communication costs between services, Service Dependency Graph (SDG), and potential parallelism among services, Service Concurrence Graph (SCG), respectively. Then, these two graphs are integrated into a single Service Relationship Graph (SRG) and the service deployment problem is transformed into a minimum k-cut problem for solution. A series of experiments were conducted to evaluate the proposed approach. The experimental results indicate that our approach outperforms previous deployment methods significantly in terms of service response time.

Cloud computing has caused a revolution in our way of using software. Software development and deployment based on the new models of Software as a Service (SaaS) and Service-Oriented Architecture (SOA) are expected to bring a lot of benefits for users. However, software developers and software service providers will have to address new challenging issues before such benefits can be realized. The issues mainly arise from two characteristics of service-based applications: software based on distributed service flows and online concurrent user access. This paper deals with one of the important issues concerning resource allocation and dynamic provisioning for the deployed services in a cloud environment. We propose a service deployment strategy based on the structural property of application service flows and a dynamic resource provisioning mechanism utilizing the estimation of future service requests. A series of experiments were conducted on the CloudSim platform to evaluate the proposed mechanisms. The experimental results indicate that the proposed methods significantly outperform the commonly used primitive approaches, achieving up to 79.9% performance improvement.

Most previous workflow scheduling research focused on scheduling a single workflow on parallel systems. Recent researches show that utilizing idle time slots between scheduled tasks is a promising direction for efficient multiple workflow scheduling. Stavrinides and Karatza proposed a list scheduling approach to efficient utilization of the idle time slots through bin packing techniques. In this paper, we elaborate on this direction and develop a new approach to further improve multiple workflow scheduling performance through two techniques. The first, in contrast with the list scheduling approach, is clustering the tasks within workflows into groups before allocation. This can reduce inter-task communication cost and thus improve workflow execution performance. The second technique tries to make a balance between tasks' start time and the fitness of idle time slots when allocating task groups. The proposed approach has been evaluated with a series of simulation experiments and compared to the previous method. The results show that our approach outperforms the previous method significantly, up to 51% performance improvement in terms of average makespan.

This paper proposes a processor allocation technique named temporal look-ahead processor allocation (TLPA) that makes allocation decision by evaluating the allocation effects on subsequent jobs in the waiting queue. TLPA has two strengths. First, it takes multiple performance factors into account when making allocation decision. Second, it can be used to optimize different performance metrics. To evaluate the performance of TLPA, we compare TLPA with best-fit and fastest-first algorithms. Simulation results show that TLPA has up to 32.75% performance improvement over conventional processor allocation algorithms in terms of average turnaround time in various system configurations.

With the notion of virtual servers, peers participating in a heterogeneous, structured peer-to-peer (P2P) network may host different numbers of virtual servers, and by migrating virtual servers, peers can balance their loads proportional to their capacities. The existing and decentralized load balance algorithms designed for the heterogeneous, structured P2P networks either explicitly construct auxiliary networks to manipulate global information or implicitly demand the P2P substrates organized in a hierarchical fashion. Without relying on any auxiliary networks and independent of the geometry of the P2P substrates, we present, in this paper, a novel load balancing algorithm that is unique in that each participating peer is based on the partial knowledge of the system to estimate the probability distributions of the capacities of peers and the loads of virtual servers, resulting in imperfect knowledge of the system state. With the imperfect system state, peers can compute their expected loads and reallocate their loads in parallel. Through extensive simulations, we compare our proposal to prior load balancing algorithms.

Unstructured peer-to-peer (P2P) file-sharing networks are popular in the mass market. As the peers participating in unstructured networks interconnect randomly, they rely on flooding query messages to discover objects of interest. Empirical measurement studies indicate that the peers in P2P networks have similar preferences, and recently proposed unstructured P2P networks intend to organize the participating peers in a small-world (SW) fashion by exploiting the knowledge of contents stored in peers. As existing algorithms for constructing SW-based unstructured P2P networks may not precisely reveal the object sharing patterns, the resultant networks thus may not perform searches efficiently and effectively by exploiting the common interests among peers. In this paper, we suggest a novel P2P network formation algorithm to construct SW-based unstructured networks. We validate our proposal in simulations with an empirical data set, and the simulation results prove that our proposal greatly outperforms existing algorithms in terms of search efficiency and effectiveness.

Many parallel computer systems installed in computing centers worldwide, which adopts backfilling based job scheduling policies, require that users should provide estimated job execution time when submitting a job to the system. This paper presents an approach, taking advantage of the estimated job execution time, to effectively allocating processors to jobs submitted to a heterogeneous computing grid. The proposed adaptive processor allocation approach was evaluated with simulation studies under various workload and processor speed conditions. The results indicate that the adaptive processor allocation approach can effectively improve the overall system performance, in terms of jobspsila average turnaround time, from two to four times under different conditions, compared to currently used methods.

Grid computing systems integrate geographical computing resources across virtual organizations. In grid systems, one of the most important challenges is how to efficiently exploit shared computing resources. This study addresses the job migration policies for exploiting computing resources in grid computing systems. In this study, we propose two job migration policies, the load barrier policy and the minimal job turnaround time policy. By adopting the P2P technique, we construct a job migration mechanism to improve the utilization of idle computing resources across virtual organizations in P2P Grid systems. We quantify the performance of our job migration mechanism using several influencing parameters such as the job migration policy, load barrier, job size, and data transfer rate. Experimental results show that our job migration mechanism could efficiently distribute load in P2P Grid systems.

Most workflow management systems nowadays are based on centralized client/server architecture. Under this architecture, the response time of request might increase unacceptably when the number of users who login to the system increase quickly and a large amount of requests are sent to the centralized server within a short time period. Parallel server architecture could help to resolve the performance bottleneck of a single server. However, a static parallel architecture with a fixed number of servers is not efficient at resource utilization because the numbers of users and their requests usually change time by time, especially for big and fast changes. This paper presents an effective architecture of dynamic resource-provisioning and then the implementation for a parallel workflow management system. There are a series of experiments conducted and the results indicate that it is an effective approach to handling the time-varying workloads in real world WfMS.

This work proposes an approach to generate weighted random patterns which can maximally excite a circuit during its burn-in testing. The approach is based on a probability model and a maximization procedure to obtain signal transition probability distribution for primary inputs and to generate weighted random patterns according to the obtained probability distribution. It can especially generate weighted random patterns to excite particularly selected "weak nodes" of the circuit in order to expose the early failure of these nodes. Experimental results show that this approach can increase the power dissipation of the total circuit nodes up to 26.68% and the switching activity of particularly selected nodes up to 41.51% respectively.

Cache performance in modern computers is important for program efficiency. A cache is thrashing if a significant amount of time is spent moving data between the memory and the cache. This paper presents two cache thrashing examples, one in scientific computing and one in image processing, both of which involve several one-dimensional arrays that are accessed sequentially, i.e., with unit strides. Accessing arrays in unit strides was considered very efficient on cache-based computer systems. However, the existence of cache thrashing is demonstrated by significant increases in computing speed in the equivalent programs tuned for cache locality. This shows that accessing several arrays sequentially may cause cache thrashing. Thus, to improve cache performance, it is important that the compiler or the programmer takes all arrays inside a loop into consideration. © 1997 by John Wiley & Sons, Ltd.

Parallel BLAS libraries have recently shown promise as a means of taking advantage of parallel computing in solving scientific problems. However, little work has been done on providing such a parallel library in LAN-connected workstations. Our motivation for this research lies in the strong belief that since LAN-connected workstations are highly cost-effective, it is important to study the issues in such environments. Dynamic load balancing is a method that allows parallel programs to run efficiently in LAN-connected workstations. Introducing dynamic load balancing leads to new design concerns for data distribution, sequential implementation, and library interfaces. Through a series of experiments, we investigate the influence of these factors. We also propose a set of guidelines for developing an efficient parallel Level 3 BLAS library.>