Search

Using multiple independent networks (also known as rails) is an emerging technique which is being used to overcome bandwidth limitations and enhance fault tolerance of current high-performance parallel computers. In this paper, we present and analyze various algorithms to allocate multiple communication rails, including static and dynamic allocation schemes. An analytical lower bound on the number of rails required for static rail allocation is shown. We also present an extensive experimental comparison of the behavior of various algorithms in terms of bandwidth and latency. We show that striping messages over multiple rails can substantially reduce network latency, depending on average message size, network load and allocation scheme. The methods compared include a static rail allocation, a basic round-robin rail allocation, a local-dynamic allocation based on local knowledge and a dynamic rail allocation that reserves both communication endpoints of a message before sending it. The last method is shown to perform better than the others at higher loads: up to 49% better than local-knowledge allocation and 37% better than the round-robin allocation. This allocation scheme also shows lower latency and it saturates at higher loads (for long enough messages). Most importantly, this proposed allocation scheme scales well with the number of rails and message size. In addition we propose a hybrid algorithm that combines the benefits of the local-dynamic allocation for short messages with those of the dynamic algorithm for large messages. Copyright © 2003 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Fog computing is a novel, decentralized and heterogeneous computing environment that extends the traditional cloud computing systems by facilitating task processing near end‐users on computing resources called fog nodes. These diverse and resource‐constrained fog devices process a large volume of tasks generated by various fog applications. These tasks are generated by various applications, some of which may be latency‐sensitive, while others may tolerate some degree of delay in their normal functions. Task scheduling determines when a task should be allocated to a computing resource and how long that task can occupy the assigned resource. The majority of task scheduling algorithms focus on prioritizing the latency‐sensitive tasks only, which results in the long waiting time for the other type of tasks. Hence, these priority‐based schedulers cause task starvation for less important tasks while achieving delay‐optimal results for latency‐sensitive tasks. As a result, in this paper, we propose MQP, a multi‐queue priority‐based preemptive task scheduling approach that achieves a balanced task allocation for those applications that can tolerate a certain amount of processing delay and the latency‐sensitive fog applications. At run‐time, the MQP algorithm categorizes tasks as short and long based on their burst time. MQP algorithm maintains a separate task queue for each task category and dynamically updates the time slot value for preemption. The proposed technique's major purpose is to reduce response time for those data‐intensive applications in the fog computing environment, which include both latency‐sensitive tasks and tasks which are less latency‐sensitive, thereby addressing the starvation problem for less latency‐sensitive tasks. A smart traffic management case study is created to model a scenario with both latency‐sensitive short and less latency‐sensitive long tasks. We implement the MQP algorithm using iFogSim and confirm that it reduces the service latencies for long tasks. Simulation results show that the MQP algorithm allocates tasks to a fog device more efficiently and reduces the service latencies for long tasks. The average value of percentage reduction in the latency across all experimental configurations achieved is 22.68% and 38.45% in comparison to First Come‐First Serve and shortest job first algorithms. [ABSTRACT FROM AUTHOR]

Summary: Due to the growth of applications and the integration of new customers into the world of computing systems, computing needs to be changed and to become more powerful and flexible than before. Meanwhile, cloud computing is presented as a model beyond a system that is currently capable of answering most request needs. Flexible infrastructure for cloud computing and virtualization technology provide new features to support business activities. Clouds are a very important topic that used secure management tools for storage, security and securing data centers in a flexible manner. One of the important matters in cloud technologies is virtual machine migration (VMM). There are different ways to implement the VMM, but because of the limitation of resources' energy, energy management is also very important and challenging. Due to the NP‐hard nature of this problem, this paper presents an energy‐aware VMM engine for cloud computing using the discrete bacterial foraging algorithm as a new collective behavior‐based metaheuristics algorithm. The CloudSim simulator is employed to investigate the efficiency of this method. The obtained results have shown that the proposed method improves the energy consumption and the migration count. [ABSTRACT FROM AUTHOR]

To verify fixed-time constraints in Grid workflow systems, consistency and inconsistency conditions have been defined in conventional verification work. However, with a view of the run-time uncertainty of activity completion duration, we argue that, although the conventional consistency condition is feasible, the conventional inconsistency condition is too restrictive and covers several different states. These states, which are handled conventionally by the same exception handling, should be handled differently for the purpose of cost saving. Therefore, in this paper, we divide conventional inconsistency into weak consistency, weak inconsistency and strong inconsistency and treat conventional consistency as strong consistency. Correspondingly, we develop some algorithms on how to verify them. Based on this, for weak consistency we present a method on how to adjust it to strong consistency by using mean activity time redundancy and temporal dependency between fixed-time constraints. For weak inconsistency, we analyse briefly why it can be handled by simpler and more cost-saving exception handling while for strong inconsistency, the conventional exception handling remains deployed. The final quantitative evaluation demonstrates that our research can achieve better cost-effectiveness than the conventional work. Copyright © 2006 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper presents an optimization approach for decentralized Quality of Service (QoS)-based scheduling based on utility and pricing in Grid computing. The paper assumes that the quality dimensions can be easily formulated as utility functions to express quality preferences for each task agent. The utility values are calculated by the user-supplied utility function that can be formulated with the task parameters. The QoS constraint Grid resource scheduling problem is formulated into a utility optimization problem. The QoS-based Grid resource scheduling optimization is decomposed into two subproblems by applying the Lagrangian method. In the Grid, a Grid task agent acts as a consumer paying for the Grid resource and the resource providers receive profits from task agents. A pricing-based QoS scheduling algorithm is used to perform optimally decentralized QoS-based resource scheduling. The experiments investigate the effect of the QoS metrics on the global utility and compare the performance of the proposed algorithm with other economical Grid resource scheduling algorithms. Copyright © 2006 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

A major challenge facing software libraries for scientific computing is the ability to provide adequate flexibility to meet sophisticated, diverse, and evolving application requirements. Object-oriented design techniques are valuable tools for capturing characteristics of complex applications in a software architecture. In this paper, we describe certain prominent object-oriented features of the SAMRAI software library that have proven to be useful in application development. SAMRAI is used in a variety of applications and has demonstrated a substantial amount of code and design re-use in those applications. This flexibility and extensibility is illustrated with three different application codes. We emphasize two important features of our design. First, we describe the composition of complex numerical algorithms from smaller components which are usable in different applications. Second, we discuss the extension of existing framework components to satisfy new application needs. Published in 2002 by John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Summary: With the increase in size and complexity of high‐performance computing systems, the probability of failures, and the cost of recovery grow. Parallel applications running on these systems should be able to continue running in spite of node failures at arbitrary times. Collective operations are essential for many parallel MPI applications, and are often the first to detect such failures. This work presents tree‐based fault‐tolerant collective operations, which combine fault detection and recovery as an integral part each operation. We do this by extending existing tree‐based algorithms, to allow for a collective operation to succeed despite failing nodes before or during its run. This differs from other approaches, where recovery takes place after a failure of such operations have failed. The article includes a comparison between the performance of the proposed algorithm and other approaches, as well as a simulator‐based analysis of performance at scale. [ABSTRACT FROM AUTHOR]

Summary: Clusters based on hybrid architectures combining ARM CPUs and FPGA fabric, such as the Xilinx Zynq SoC, not only are energy‐efficient platforms with strong processing power but also have the advantages of distributed computing systems balancing the workload between cores, processors, and nodes. This paper employs a 48‐node cluster infrastructure based on the Xilinx Zynq SoC to accelerate classical cryptographic algorithms, including hash functions, AES, and RSA. In this design, we leverage the flexibility of the software to implement node‐to‐node communication through the message passing interface (MPI), and we offload the compute‐intensive tasks to the FPGA to accelerate complex calculations with the parallelizability of specific reconfigurable coprocessors. In addition, we study several parallel cryptography optimizations based on FPGA to evaluate this cluster. Finally, using a comparison with a multi‐core desktop (Intel i7‐3770) and a many‐core server (288 cores), the efficiency of the implementations of the selected data encryption and decryption algorithms is presented to illustrate the performance of our system; we also gain up to 3.6× increase in energy efficiency. [ABSTRACT FROM AUTHOR]

In this paper attention is concentrated on the mapping of computationally intensive multi-task applications onto shared computational grids. This problem, already known to be as NP-complete in parallel systems, becomes even more arduous in such environments. To find a near-optimal mapping solution a parallel version of a Differential Evolution algorithm is presented and evaluated on different applications and operating conditions of the grid nodes. The purpose is to select for a given application the mapping solutions that minimize the greatest among the time intervals which each node dedicates to the execution of the tasks assigned to it. The experiments, effected with applications represented as task interaction graphs, demonstrate the ability of the evolutionary tool to perform multisite grid mapping, and show that the parallel approach is more effective than the sequential version both in enhancing the quality of the solution and in the time needed to get it. Copyright © 2011 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Grid computing emerges as an infrastructure for large-scale data processing, resource sharing, and scientific computing. In this paper we propose a Grid scheduling algorithm using multi-attribute utility theory and multi-objective optimization (MOO). The algorithm makes the optimal decisions based on the available set of objectives. By comparing with a deadline-and-budget algorithm with three objectives, we show that the proposed MOO scheduling algorithm is capable of obtaining a broader set of non-dominated solutions. The obtained solutions are also of higher quality, which are in close proximity to the Pareto optimal front. Copyright © 2009 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

As a widely used fault-tolerance technique, checkpointing can be divided into three categories: independent checkpointing, coordinated checkpointing, and communication-induced checkpointing (CIC). Independent checkpointing and coordinated checkpointing have been widely used in the design of fault-tolerant mobile agent systems, but CIC has not attracted much attention. CIC is flexible, efficient, and scalable, which is desirable for mobile agent (MA) systems. Furthermore, CIC can be well integrated with independent checkpointing for reliable MA migrations. In this paper, we propose two CIC-based checkpointing algorithms for MA systems. The Basic-CIC algorithm is developed by applying the classic CIC technique to MA systems, while the deferred message processing-based CIC (DM-CIC) improves the time efficiency by deciding when to make the forced checkpointing. Simulation results show that DM-CIC is stable and can help the system recover fast from failures. Copyright © 2007 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

An important component of Semantic Grid services is the support for dynamic service discovery. Dynamic service discovery requires the provision of rich and flexible metadata that is not supported by current registry services such as UDDI. We present a framework to facilitate reputation-based service selection in Semantic Grids. Our framework has two key features that distinguish it from other work in this area. First, we propose a dynamic, adaptive, and highly fault-tolerant reputation-aware service discovery algorithm. Second, we present a service-oriented distributed reputation assessment algorithm. In this paper, we describe the main components of our framework and report on our experience of developing the prototype. Copyright © 2005 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

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 very distributed, shared and heterogeneous nature of the resources involved. A crucial step towards solving this problem is the need to identify both an appropriate scheduling model and scheduling algorithm(s). This paper presents a tool to aid the design and evaluation of scheduling policies suitable for efficient execution of system-aware parallel applications on computational Grids. Copyright © 2005 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The growing gap between sustained and peak performance for scientific applications is a well-known problem in high-performance computing. The recent development of parallel vector systems offers the potential to reduce this gap for many computational science codes and deliver a substantial increase in computing capabilities. This paper examines the intranode performance of the NEC SX-6 vector processor, and compares it against the cache-based IBM Power3 and Power4 superscalar architectures, across a number of key scientific computing areas. First, we present the performance of a microbenchmark suite that examines many low-level machine characteristics. Next, we study the behavior of the NAS Parallel Benchmarks. Finally, we evaluate the performance of several scientific computing codes. Overall results demonstrate that the SX-6 achieves high performance on a large fraction of our application suite and often significantly outperforms the cache-based architectures. However, certain classes of applications are not easily amenable to vectorization and would require extensive algorithm and implementation reengineering to utilize the SX-6 effectively. Copyright © 2005 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper presents a stochastic dynamic load balancing algorithm for Internet computing, which is a new type of distributed computing involving heterogeneous workstations from different organizations on the Internet. To realize the practical environment, we assume the system to be comprised of heterogeneous, untrusted and non-dedicated workstations connected by a non-dedicated network. Our algorithm uses the product of the average processing time and the queue length of system jobs as the load index. Dynamic communication delay is included in the execution cost calculation. The transfer policy and the location policy are combined in a stochastic algorithm. State information exchange is done via information feedback and mutual updating. Simulations demonstrate that our algorithm outperforms conventional approaches over a wide range of system parameters. These results are reconfirmed by empirical experiments after we have implemented the algorithms on the Distributed Java Machine global virtual machine. Copyright © 2003 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Despite extensive research, optimal performance has not easily been available previously for matrix multiplication (especially for large matrices) on most architectures because of the lack of a structured approach and the limitations imposed by matrix storage formats. A simple but effective framework is presented here that lays the foundation for building high-performance matrix-multiplication codes in a structured, portable and efficient manner. The resulting codes are validated on three different representative RISC and CISC architectures on which they significantly outperform highly optimized libraries such as ATLAS and other competing methodologies reported in the literature. The main component of the proposed approach is a hierarchical storage format that efficiently generalizes the applicability of the memory hierarchy friendly Morton ordering to arbitrary-sized matrices. The storage format supports polyalgorithms, which are shown here to be essential for obtaining the best possible performance for a range of problem sizes. Several algorithmic advances are made in this paper, including an oscillating iterative algorithm for matrix multiplication and a variable recursion cutoff criterion for Strassen's algorithm. The authors expose the need to standardize linear algebra kernel interfaces, distinct from the BLAS, for writing portable high-performance code. These kernel routines operate on small blocks that fit in the L1 cache. The performance advantages of the proposed framework can be effectively delivered to new and existing applications through the use of object-oriented or compiler-based approaches. Copyright © 2002 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Current methods for object-oriented software development provide notation for the specification of models, yet do not sufficiently relate the different model types to each other, nor do they provide support for transformations from one model type to another. This makes transformations a manual activity, which increases the risk of inconsistencies among models and may lead to a loss of information. We have developed and implemented an algorithm supporting one of the transitions from analysis to design, the transformation of scenario models into behavior models. This algorithm supports the Unified Modelling Language (UML), mapping the UML's collaboration diagrams into state transition diagrams. We believe that CASE tools implementing such algorithms will be highly beneficial in object-oriented software development. In this paper, we provide an overview of our algorithm and discuss all its major steps. The algorithm is detailed in semi-formal English and illustrated with a number of examples. Furthermore, the algorithm is assessed from different perspectives, such as scope and role in the overall development process, issues in the design of the algorithm, complexity, implementation and experimentation, and related work. Copyright © 2001 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The article discusses various reports published within the issue, including one on a dispatching framework that dispatches requests to servers through virtual machines, one on combining the virtualization technology in computers and one on the theoretical model and the implementation of two relaying algorithms, dynamic relaying and fixed relaying.

Performance engineering of parallel and distributed applications is a complex task that iterates through various phases, ranging from modeling and prediction, to performance measurement, experiment management, data collection, and bottleneck analysis. There is no evidence so far that all of these phases should/can be integrated into a single monolithic tool. Moreover, the emergence of computational Grids as a common single wide-area platform for high-performance computing raises the idea to provide tools as interacting Grid services that share resources, support interoperability among different users and tools, and, most importantly, provide omnipresent services over the Grid. We have developed the ASKALON tool set to support performance-oriented development of parallel and distributed (Grid) applications. ASKALON comprises four tools, coherently integrated into a service-oriented architecture. SCALEA is a performance instrumentation, measurement, and analysis tool of parallel and distributed applications. ZENTURIO is a general purpose experiment management tool with advanced support for multi-experiment performance analysis and parameter studies. AKSUM provides semi-automatic high-level performance bottleneck detection through a special-purpose performance property specification language. The PerformanceProphet enables the user to model and predict the performance of parallel applications at the early stages of development. In this paper we describe the overall architecture of the ASKALON tool set and outline the basic functionality of the four constituent tools. The structure of each tool is based on the composition and sharing of remote Grid services, thus enabling tool interoperability. In addition, a data repository allows the tools to share the common application performance and output data that have been derived by the individual tools. A service repository is used to store common portable Grid service implementations. A general-purpose Factory service is employed to create service instances on arbitrary remote Grid sites. Discovering and dynamically binding to existing remote services is achieved through registry services. The ASKALON visualization diagrams support both online and post-mortem visualization of performance and output data. We demonstrate the usefulness and effectiveness of ASKALON by applying the tools to real-world applications. Copyright © 2005 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Summary: Energy efficiency in heterogeneous computing systems has attracted increasing interests due to its economic and environmental impacts during recent decades. Based on power‐aware hardware techniques, such as dynamic voltage frequency scaling, efforts have been made through task scheduling to reduce the total energy consumption for executing a parallel application while maintaining its time efficiency. In this case, energy conscious task scheduling refers to a bi‐objective optimization that aims to minimize the overall completion time (makespan) and the total energy consumption, simultaneously. Existing energy conscious scheduling algorithms conduct energy optimization by means of slack reclamation or a trade‐off function. However, the performance of slack reclamation has been proved to be upper‐bounded and methods relying on trade‐off functions cannot guarantee bi‐objective optimization. In this article, an energy conscious task scheduling algorithm is proposed to tackle the above issues based on the framework of variable neighborhood search. Two neighborhood structures are designed to reduce makespan and the total energy consumption, respectively. Furthermore, a pruning technique is incorporated into the algorithm to accelerate the searching process. Extensive experimental results on both randomly generated and real‐world applications demonstrate that the proposed algorithm improves the time‐efficient schedules on average by 22.4% for the energy consumption and 1.2% for the makespan. [ABSTRACT FROM AUTHOR]

Summary: In order to realize green society, it is critical to reduce electric energy consumed by servers in clusters. In our previous studies, these types of algorithms are proposed to select an energy‐efficient server to perform an application process issued by a client. In this paper, we newly discuss a migration approach to reducing the electric energy consumption of servers where virtual machines with application processes migrate to more energy‐efficient servers. We propose a new algorithm called ISEAM2 to reduce the electric energy consumption of servers. Here, a pair of a host server and a virtual machine on the host server are first selected to perform a process issued by an application. In addition, a target virtual machine on a host server and a guest server to which the target virtual machine migrates are selected so that the electric energy consumption of the host and guest servers can be minimized. Thus, virtual machines with application processes migrate to more energy‐efficient servers. We also propose a simple way to estimate the termination time of every process on each server. In the evaluation, we show the total electric energy consumption and total active time of servers, and the average execution time of processes can be reduced in the ISEAM2 algorithm compared with other algorithms. [ABSTRACT FROM AUTHOR]

Scientific workflow is emerging as a promising scientific computing paradigm to offer the convenience for the scientists to resolve complex scientific problems. To successfully execute a scientific workflow, the workflow creation by depending on service discovery techniques should be made in the first place. Particularly, semantics have been proposed as a key to automatically solve service discovery issue for facilitating users to create a workflow. However, most of the semantic service discovery methods still remain at a low-efficiency stage because they generally involve a large number of ontology reasoning that is often time consuming. To address this issue, we present an efficient service discovery method by building Quick Service Query list (QSQL) to support automated service discovery for creating a workflow. QSQL based on graph storage theory is an efficient service index list that is dynamically built by service publication algorithm. In QSQL, semantic relationships between the published services and all related ontology concepts can be processed in advance so that a large number of ontology reasoning can be avoided during service discovery. Further, our proposed discovery algorithm can efficiently select service models from QSQL to match a user query. The final experiments further demonstrate the feasibility and the efficiency of our proposed method. Copyright © 2009 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This work describes a parallel divide-and-conquer Delaunay triangulation scheme. This algorithm finds the affected zone, which covers the triangulation and may be modified when two sub-block triangulations are merged. Finding the affected zone can reduce the amount of data required to be transmitted between processors. The time complexity of the divide-and-conquer scheme remains O(n log n), and the affected region can be located in O(n) time steps, where n denotes the number of points. The code was implemented with C, FORTRAN and MPI, making it portable to many computer systems. Experimental results on an IBM SP2 show that a parallel efficiency of 44–95% for general distributions can be attained on a 16-node distributed memory system. Copyright © 2006 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Improvements in performance modeling and identification of computational regimes within software libraries is a critical first step in developing software libraries that are truly agile with respect to the application as well as to the hardware. It is shown here that Pareto ranking, a concept from multi-objective optimization, can be an effective tool for mining large performance datasets. The approach is illustrated using software performance data gathered using both the public domain LAPACK library and an asynchronous communication library based on IBM LAPI active message library. Copyright © 2005 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

For the Protein Threading Problem (PTP) we propose a network-flow like formulation. We also show its equivalence with a generalization of the shortest path problem on a graph with a very particular structure. The underlying Mixed Integer Programming (MIP) model proves to be very appropriate for the PTP—large real-life instances have been solved much faster by using only the MIP solver CPLEX instead of a known special-purpose branch and bound algorithm. The properties of the MIP model permit a decomposition of the main problem into a large number of subproblems (tasks). We show that a branch and cut strategy can be efficiently applied for solving these tasks in a parallel manner, which leads to a significant reduction in the total running time. Computational experiments with large problem instances are presented. Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The best approach to parallelize multidimensional FFT algorithms has long been under debate. Distributed transposes are widely used, but they also vary in communication policies and hence performance. In this work we analyze the impact of different redistribution strategies on the performance of parallel FFT, on various machine architectures. We found that some redistribution strategies were consistently superior, while some others were unexpectedly inferior. An in-depth investigation into the reasons for this behavior is included in this work. Copyright © 2001 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]