Cloud service providers are distributing data centers geographically to minimize energy costs through intelligent workload distribution. With increasing data volumes in emerging cloud workloads, it is critical to factor in the network costs for transferring workloads across data centers. For geo-distributed data centers, many researchers have been exploring strategies for energy cost minimization and intelligent inter-data-center workload distribution separately. However, prior work does not comprehensively and simultaneously consider data center energy costs, data transfer costs, and data center queueing delay. In this paper, we propose a novel game theory-based workload management framework that takes a holistic approach to the cloud operating cost minimization problem by making intelligent scheduling decisions aware of data transfer costs and the data center queueing delay. Our framework performs intelligent workload management that considers heterogeneity in data center compute capability, cooling power, interference effects from task co-location in servers, time-of-use electricity pricing, renewable energy, net metering, peak demand pricing distribution, and network pricing. Our simulations show that the proposed game-theoretic technique can minimize the cloud operating cost more effectively than existing approaches.

In this article, we investigate limitations in the traditional value-based algorithms for a power-constrained HPC system and evaluate their impact on HPC productivity. We expose the trade-off between allocating system-wide power budget uniformly and greedily under different system-wide power constraints in an oversubscribed system. We experimentally demonstrate that, under the tightest power constraint, the mean productivity of the greedy allocation is 38 percent higher than the uniform allocation whereas, under the intermediate power constraint, the uniform allocation has a mean productivity of 6 percent higher than the greedy allocation. We then propose a new algorithm that adapts its behavior to deliver the combined benefits of the two allocation strategies. We design a methodology with online retraining capability to create application-specific power-execution time models for a class of HPC applications. These models are used in predicting the execution time of an application on the available resources at the time of making scheduling decisions in the power-aware algorithms. We evaluate the proposed algorithm using emulation and simulation environments, and show that our adaptive strategy results in improving HPC resource utilization while delivering a mean productivity that is almost the same as the best performing algorithm across various system-wide power constraints.

Cloud computing has enabled entirely new business models for high-performance computing. Having a dedicated local high-performance computer is still an option for some, but more are turning to cloud computing resources to fulfill their high-performance computing needs. With cloud computing it is possible to tailor your computing infrastructure to perform best for your particular type of workload by selecting the correct number of machines of each type. This paper presents an efficient algorithm to find the best set of computing resources to allocate to the workload. This research is applicable to users provisioning cloud computing resources and to data center owners making purchasing decisions about physical hardware. Studies have shown that cloud computing machines have measurable variability in their performance. Some of the causes of performance variability include small changes in architecture, location within the datacenter, and neighboring applications consuming shared network resources. The proposed algorithm models the uncertainty in the computing resources and the variability in the tasks in a many-task computing environment to find a robust number of machines of each type necessary to process the workload. In addition, reward rate, cost, failure rate, and power consumption can be optimized, as desired, to compute Pareto fronts.

With the increases in complexity and number of nodes in large-scale high performance computing (HPC) systems over time, the probability of applications experiencing runtime failures has increased significantly. Projections indicate that exascale-sized systems are likely to operate with mean time between failures (MTBF) of as little as a few minutes. Several strategies have been proposed in recent years for enabling systems of these extreme sizes to be resilient against failures. This work provides a comparison of four state-of-the-art HPC resilience protocols that are being considered for use in exascale systems. We explore the behavior of each resilience protocol operating under the simulated execution of a diverse set of applications and study the performance degradation that a large-scale system experiences from the overhead associated with each resilience protocol as well as the re-computation needed to recover when a failure occurs. Using the results from these analyses, we examine how resource management on exascale systems can be improved by allowing the system to select the optimal resilience protocol depending upon each application's execution characteristics, as well as providing the system resource manager the ability to make scheduling decisions that are “resilience aware” through the use of more accurate execution time predictions.

The recent proliferation and associated high electricity costs of distributed data centers have motivated researchers to study energy-cost minimization at the geo-distributed level. The development of time-of-use (TOU) electricity pricing models and renewable energy source models has provided the means for researchers to reduce these high energy costs through intelligent geographical workload distribution. However, neglecting important considerations such as data center cooling power, interference effects from task co-location in servers, net-metering, and peak demand pricing of electricity has led to sub-optimal results in prior work because these factors have a significant impact on energy costs and performance. We propose a set of workload management techniques that take a holistic approach to the energy minimization problem for geo-distributed data centers. Our approach considers detailed data center cooling power, co-location interference, TOU electricity pricing, renewable energy, net metering, and peak demand pricing distribution models. We demonstrate the value of utilizing such information by comparing against geo-distributed workload management techniques that possess varying amounts of system information. Our simulation results indicate that our best proposed technique is able to achieve a 61 percent (on average) cost reduction compared to state-of-the-art prior work.

Computer manufacturers, software developers, and service providers spend significant time and resources to ensure that they can optimally support one class of applications. However, they cannot cope with the dynamic and continuous changes in applications and workload types, and consequently their offered services become unstable, fragile, and cannot guarantee the required Quality of Service (QoS). Furthermore, it becomes prohibitively expensive to build data centers (DCs) that are optimized for fixed types of workloads and businesses or to scale up for accommodating new growth in heterogeneous workload demands. Consequently, it is critically important that the architecture of next generation DCs is dynamically customizable to support a wide range of application types or businesses under constrained resources. In this paper, we present some design concepts for our Just In Time Architecture (JITA), a novel data center design to overcome the composable DC challenges by dynamically interconnecting DC components into a virtual DC (VDC) that is optimized to the service level objectives for each class of applications. We present how we can use optical waveguide links to build a passive crossbar that directly interconnects all DC resources at the required throughput and latency.

Resource management for large-scale high performance computing systems pose difficult challenges to system administrators. The extreme scale of these modern systems require task scheduling algorithms that are capable of handling at least millions of tasks and thousands of machines. These large computing systems consume vast amounts of electricity leading to high operating costs. System administrators try to simultaneously reduce operating costs and offer state-of-the-art performance; however, these are often conflicting objectives. Highly scalable algorithms are necessary to schedule tasks efficiently and to help system administrators gain insight into energy/performance trade-offs of the system. System administrators can examine this trade-off space to quantify how much a difference in the performance level will cost in electricity, or analyze how much performance can be expected within an energy budget. In this study, we design a novel linear programming based resource allocation algorithm for a heterogeneous computing system to efficiently compute high quality solutions for simultaneously minimizing energy and makespan. These solutions are used to bound the Pareto front to easily trade-off energy and performance. The new algorithms are highly scalable in both solution quality and computation time compared to existing algorithms, especially as the problem size increases.

The dominance of the Cloud paradigm and the proliferation of Cloud services are resulting in increasing scales of Cloud hosting infrastructures and associated complexities that are making their sustainability a growing concern. Cloud data centers are growing in size to millions of nodes. Furthermore, Clouds are being used to support mission critical support for many industries. Finally, the environmental impact of Cloud data centers is becoming an increasing concern. How can this mass migration to Clouds best be sustained? This panel will explore issues and challenges related to the sustainability of very large-scale cloud infrastructures from multiple perspectives.

Many of today’s data centers experience physical limitations on the power needed to run the data center. The first problem that we study is maximizing the performance (quantified by the reward collected for completing tasks by their individual deadlines) of a data center that is subject to total power consumption (of compute nodes and CRAC units) and thermal constraints. The second problem that we study is how to minimize the power consumption in a data center while guaranteeing that the overall performance does not drop below a specified threshold. For both problems, we develop novel optimization techniques for assigning the performance states of cores at the data center level to optimize the operation of the data center. The resource allocation (assignment) techniques in this paper are thermal aware as they consider effects of performance state assignments on temperature and power consumption by the CRAC units. Our simulation studies show that in some cases our assignment technique achieves about 17% average improvement in the reward collected, and about 9% reduction in power consumption compared to an assignment technique that only considers putting a core in the performance state with the highest performance or turning the core off.

We model an oversubscribed heterogeneous computing system where tasks arrive dynamically and a scheduler maps the tasks to machines for execution. The environment and workloads are based on those being investigated by the Extreme Scale Systems Center at Oak Ridge National Laboratory. Utility functions that are designed based on specifications from the system owner and users are used to create a metric for the performance of resource allocation heuristics. Each task has a time-varying utility (importance) that the enterprise will earn based on when the task successfully completes execution. We design multiple heuristics, which include a technique to drop low utility-earning tasks, to maximize the total utility that can be earned by completing tasks. The heuristics are evaluated using simulation experiments with two levels of oversubscription. The results show the benefit of having fast heuristics that account for the importance of a task and the heterogeneity of the environment when making allocation decisions in an oversubscribed environment. The ability to drop low utility-earning tasks allow the heuristics to tolerate the high oversubscription as well as earn significant utility.

Today’s data centers face the issue of balancing electricity use and completion times of their workloads. Rising electricity costs are forcing data center operators to either operate within an electricity budget or to reduce electricity use as much as possible while still maintaining service agreements. Energy-aware resource allocation is one technique a system administrator can employ to address both problems: optimizing the workload completion time (makespan) when given an energy budget, or to minimize energy consumption subject to service guarantees (such as adhering to deadlines). In this paper, we study the problem of energy-aware static resource allocation in an environment where a collection of independent (non-communicating) tasks (“bag-of-tasks”) is assigned to a heterogeneous computing system. Computing systems often operate in environments where task execution times vary (e.g., due to cache misses or data dependent execution times). We model these execution times stochastically, using probability density functions. We want our resource allocations to be robust against these variations, where we defineenergy-robustnessas the probability that the energy budget is not violated, andmakespan-robustnessas the probability a makespan deadline is not violated. We develop and analyze several heuristics for energy-aware resource allocation for both energy-constrained and deadline-constrained problems.

With the advent of energy-aware scheduling algorithms, it is now possible to find solutions that trade-off performance for decreased energy usage. There are now efficient algorithms to find high quality Pareto fronts that can be used to select the desired balance between make span and energy consumption. One drawback of this approach is that it still requires a system administrator to select the desired operating point. In this paper, a market-oriented technique for scheduling is presented where the high performance computing system administrator is trying to maximize the return on investment. A model is developed where the users pay a given price to have a bag-of-tasks processed. The cost to the system administrator for processing this bag-of-tasks is strongly related to the energy consumption for executing these tasks. A novel algorithm is designed that efficiently finds the maximum profit resource allocation and tightly bounds the optimal solution. In addition, this algorithm has very desirable runtime and solution quality properties as the number of tasks and machines become large.

The creation of a Massive Multi-Player On-line Game (MMOG) has significant costs, such as maintenance of server rooms, server administration, and customer service. The capacity of servers in a client/server MMOG is hard to scale and cannot adjust quickly to peaks in demand while maintaining the required response time. To handle these peaks in demand, we propose to employ users’ computers as secondary servers. The introduction of users’ computers as secondary servers allows the performance of the MMOG to support an increase in users. Here, we consider two cases: first, for the minimization of the response times from the server, we develop and implement five static heuristics to implement a secondary server scheme that reduces the time taken to compute the state of the MMOG. Second, for our study on fairness, the goal of the heuristics is to provide a “fair” environment for all the users (in terms of similar response times), and to be “robust” against the uncertainty of the number of new players that may join a given system configuration. The number of heterogeneous secondary servers, conversion of a player to a secondary server, and assignment of players to secondary servers are determined by the heuristics implemented in this study.

In a heterogeneous environment, uncertainty in system parameters may cause performance features to degrade considerably. It then becomes necessary to design a system that is robust. Robustness can be defined as the degree to which a system can function in the presence of inputs different from those assumed. In this research, we focus on the design of robust static resource allocation heuristics suitable for a heterogeneous compute cluster that minimize the energy required to complete a given workload. In this study, we mathematically model and simulate a heterogeneous computing system that is assumed part of a larger warehouse scale computing environment. Task execution times/energy consumption may vary significantly across different data sets in our heterogeneous cluster; therefore, the execution time of each task on each node is modeled as a random variable. A resource allocation is considered robust if the probability that all tasks complete by a system deadline is at least 90%. To minimize the energy consumption of a specific resource allocation, dynamic voltage frequency scaling (DVFS) is employed. However, other factors, such as system overhead (spent on fans, disks, memory, etc.) must also be mathematically modeled when considering minimization of energy consumption. In this research, we propose three different heuristics that employ DVFS to minimize energy consumed by a set of tasks in our heterogeneous computing system. Finally, a lower bound on energy consumption is provided to gauge the performance of our heuristics.

This work considers the satellite data processing portion of a space-based weather monitoring system. It uses a heterogeneous distributed processing platform. There is uncertainty in the arrival time of new data sets to be processed, and resource allocation must be robust with respect to this uncertainty. The tasks to be executed by the platform are classified into two broad categories: high priority (e.g., telemetry, tracking, and control), and revenue generating (e.g., data processing and data research). In this environment, the resource allocation of the high-priority tasks must be done before the resource allocation of the revenue generating tasks. A two-part allocation scheme is presented in this research. The goal of first part is to find a resource allocation that minimizes makespan of the high-priority tasks. The robustness for the first part of the mapping is defined as the difference between this time and the expected arrival of the next data set. For the second part, the robustness of the mapping is the difference between the expected arrival time and the time at which the revenue earned is equal to the operating cost. Thus, the heuristics for the second part find a mapping that minimizes the time for the revenue (gained by completing revenue generating tasks) to be equal to the cost. Different resource allocation heuristics are designed and evaluated using simulations, and their performance is compared to a mathematical bound.

We study the problem of efficiently allocating incoming independent tasks onto the resources of a Grid system. Typically, it is assumed that the estimated time to compute each task on every machine is known. We are making the same assumption in this work, but we allow the existence of inaccuracies in these values. Our schedule will be robust versus such inaccuracies, ensuring that even when the estimated time to compute all the tasks is increased by a given percentage, the makespan of the schedule (i.e., the time when the last machine finishes its tasks) will not grow behind that percentage. We propose a new multi-objective definition of the problem, optimizing at the same time the makespan of the schedule and its robustness. Four well-known multi-objective evolutionary algorithms are used to find competitive results to the new problem. Finally, a new population initialization method for scheduling problems is proposed, leading to more efficient and accurate algorithms.

The environment considered in this research is a massive multiplayer online gaming (MMOG) environment. Each user controls an avatar (an image that represents and is manipulated by a user) in a virtual world and interacts with other users. An important aspect of MMOG is maintaining a fair environment among users (i.e., not give an unfair advantage to users with faster connections or more powerful computers). The experience (either positive or negative) the user has with the MMOG environment is dependent on how quickly the game world responds to the user's actions. This study focuses on scaling the system based on demand, while maintaining an environment that guarantees fairness. Consider an environment where there is a main server (MS) that controls the state of the virtual world. If the performance falls below acceptable standards, the MS can off-load calculations to secondary servers (SSs). An SS is a user's computer that is converted into a server. Four heuristics are proposed for determining the number of SSs, which users are converted to SSs, and how users are assigned to the SSs and the MS. The goal of the heuristics is to provide a "fair" environment for all the users, and to be "robust" against the uncertainty of the number of new players that may join a given system configuration. The heuristics are evaluated and compared by simulation.

This research investigates the problem of robust dynamic resource allocation for heterogeneous distributed computing systems operating under imposed constraints. Often, such systems are expected to function in an environment where uncertainty in system parameters is common. In such an environment, the amount of processing required to complete an application may fluctuate substantially. Determining a resource allocation that accounts for this uncertainty-in a way that can provide a probability that a given level of service is achieved-is an important area of research. We define a mathematical model of stochastic robustness appropriate for a dynamic environment that can be used during resource allocation to aid heuristic decision making. In addition, we design a novel technique for maximizing stochastic robustness in this environment. Our performance results for this technique are compared with several well known resource allocation techniques in a simulated environment that models a heterogeneous distributed computing system.

Creating replicas of frequently accessed data objects across a read-intensive content delivery network (CDN) can result in reduced user response time. Because CDNs often operate under volatile conditions, it is of the utmost importance to study replica placement techniques that can cope with uncertainties in the system parameters. We propose four CDN replica placement heuristics that guarantee a robust performance under the uncertainty of arbitrary CDN server failures. By robust performance we mean the solution quality that a heuristic guarantees given the uncertainties in system parameters. The simulation results reveal interesting characteristics of the studied heuristics. We report these characteristics with a detailed discussion on which heuristics to utilize for robust CDN data replication given a specific scenario.

The problem of finding efficient workload distribution techniques is becoming increasingly important today for heterogeneous distributed systems where the availability of compute nodes may change spontaneously over time. Therefore, the resource-allocation policy must be designed to be robust with respect to absence and re-emergence of compute nodes so that the performance of the system is maximized. Such a policy is developed in this work, and its performance is evaluated on a model of a dedicated system composed of a limited set of heterogeneous Web servers. Assuming that each HTML request results in a rdquorewardrdquo if completed before its hard deadline, the goal is to maximize a cumulative reward obtained in the system. A failure rate for each server is set relatively high to simulate its operation under harsh conditions. The results demonstrate that the proposed approach based on the concepts of the Derman-Lieberman-Ross theorem outperforms other policies compared in our experiments for inconsistent, processor-consistent, and task-processor-consistent types of heterogeneity.

The creation of a virtual world environment (VWE) has significant costs, such as maintenance of server rooms, server administration, and customer service. The initial development cost is not the only factor that needs to be considered; factors such as the popularity of a VWE and unexpected technical problems during and after the launch can affect the final cost and success of a VWE. The capacity of servers in a client/server VWE is hard to scale and cannot adjust quickly to peaks in demand while maintaining the required response time. To handle these peaks in demand, we propose to employ users' computers as secondary servers. The introduction of users' computers as secondary servers allows the performance of the VWE to support an increase in users. In this study, we develop and implement five static heuristics to implement a secondary server scheme that reduces the time taken to compute the state of the VWE. The number of heterogeneous secondary servers, conversion of a player to a secondary server, and assignment of players to secondary servers are determined by the heuristics implemented in this study. A lower bound of the performance is derived to evaluate the results of the heuristics.

Adaptive replication of data items on servers of a mobile ad hoc network can alleviate access delays. The selection of data items and servers requires solving a constrained optimization problem, that is in general NP-complete. The problem is further complicated by frequent partitions of the ad hoc network. In this paper, a mathematical model for data replication in ad hoc networks is formulated. We treat the mobile servers in the ad hoc network as self-interested entities, hence they have the capability to manipulate the outcome of a resource allocation mechanism by misrepresenting their valuations. We design a game theoretic "truthful" mechanism in which replicas are allocated to mobile servers based on reported valuations. We sketch the exact properties of the truthful mechanism and derive a payment scheme that suppresses the selfish behavior of the mobile servers. The proposed technique is extensively evaluated against three ad hoc network replica allocation methods: (a) extended static access frequency, (b) extended dynamic access frequency and neighborhood, and (c) extended dynamic connectivity grouping. The experimental results reveal that the proposed approach outperforms the three techniques in solution quality and has competitive execution times.

We present a decentralized market-based approach to resource allocation in a heterogeneous overlay network. The presented resource allocation strategy assigns overlay network resources to traffic dynamically based on current utilization, thus, enabling the system to accommodate fluctuating demand for its resources. We present a mathematical model of our resource allocation environment that treats the allocation of system resources as a constrained optimization problem. Our presented resource allocation strategy is based on solving the dual of this centralized optimization problem. The solution to the dual of our centralized optimization problem suggests a simple decentralized algorithm for resource allocation that is extremely efficient. Our results demonstrate the near optimality of the proposed approach through extensive simulation of a real-world environment. That is, the conducted simulation study utilizes components taken from a real-world middleware application environment and clearly demonstrates the practicality of the approach in a realistic setting.

This paper summarizes some of our research in the area of robust static resource allocation for distributed computing systems operating under imposed quality of service (QoS) constraints. Often, these systems are expected to function in a physical environment replete with uncertainty, which causes the amount of processing required over time to fluctuate substantially. Determining a resource allocation that accounts for this uncertainty in a way that can provide a probabilistic guarantee that a given level of QoS is achieved is an important research problem. The stochastic robustness metric described in this research is based on a mathematical model where the relationship between uncertainty in system parameters and its impact on system performance are described stochastically.

An ad hoc grid is a wireless heterogeneous computing environment without a fixed infrastructure. This study considers wireless devices that have different capabilities, have limited battery capacity, support dynamic voltage scaling, and are expected to be used for eight hours at a time and then recharged. To maximize the performance of the system, it is essential to assign resources to tasks (match) and order the execution of tasks on each resource (schedule) in a manner that exploits the heterogeneity of the resources and tasks while considering the energy constraints of the devices. In the single-hop ad hoc grid heterogeneous environment considered in this study, tasks arrive unpredictably, are independent (i.e., no precedent constraints for tasks), and have priorities and deadlines. The problem is to map (match and schedule) tasks onto devices such that the number of highest priority tasks completed by their deadlines during eight hours is maximized while efficiently utilizing the overall system energy. A model for dynamically mapping tasks onto wireless devices is introduced. Seven dynamic mapping heuristics for this environment are designed and compared to each other and to a mathematical bound.

Recently we proposed algorithms for concurrent execution on multiple clusters [11]. In this case, data partitioning is done at two levels; first, the data is distributed to a collection of heterogeneous parallel systems with different resources and startup time, then, on each system the data is evenly partitioned to the available nodes. In this paper, we report on a simulation study of the algorithms.

Heterogeneous computing (HC) is the coordinated use of different types of machines, networks, and interfaces to maximize the combined performance and/or cost effectiveness of the system. Heuristics for allocating resources in an HC system have different optimization criteria. A common optimization criterion is to minimize the completion time of the last to finish machine (makespan). In some environments, it is useful to minimize the finishing times of the other machines in the system, i.e., those machines that are not the last to finish. Consider a production environment where a set of known tasks are to be mapped to resources off-line before execution begins. Minimizing the finishing times of all the machines will provide the earliest available ready time for these machines to execute tasks that were not initially considered. In this study, we examine an iterative approach that decreases machine finishing times by repeatedly running a resource allocation heuristic. The goal of this study is to investigate whether this iterative procedure can reduce the finishing time of some machines compared to the mapping initially generated by the heuristic. We show that the effectiveness of the iterative approach is heuristic dependent and study the behavior of the iterative approach for each of the chosen heuristics. This work which identifies heuristics can and cannot attain improvements in the completion time of non-make span machines using this iterative approach.

This is an overview of the robust resource allocation research efforts that have been and continue to be conducted by the CSU robustness in computer systems group. Parallel and distributed computing systems, consisting of a (usually heterogeneous) set of machines and networks, frequently operate in environments where delivered performance degrades due to unpredictable circumstances. Such unpredictability can be the result of sudden machine failures, increases in system load, or errors caused by inaccurate initial estimation. The research into developing models and heuristics for parallel and distributed computing systems that create robust resource allocations is presented.

Heterogeneous distributed computing systems often must operate in an environment where system parameters are subject to uncertainty. Robustness can be defined as the degree to which a system can function correctly in the presence of parameter values different from those assumed. We present a methodology for quantifying the robustness of resource allocations in a dynamic environment where task execution times are stochastic. The methodology is evaluated through measuring the robustness of three different resource allocation heuristics within the context of a stochastic dynamic environment. A Bayesian regression model is fit to the combined results of the three heuristics to demonstrate the correlation between the stochastic robustness metric and the presented performance metric. The correlation results demonstrated the significant potential of the stochastic robustness metric to predict the relative performance of the three heuristics given a common objective function.

Often, parallel and distributed computing systems must operate in an environment replete with uncertainty. Determining a resource allocation that accounts for this uncertainty in a way that can provide a probabilistic guarantee that a given level of quality of service (QoS) is achieved is an important research problem. This paper defines a stochastic methodology for quantifiably determining a resource allocation's ability to satisfy QoS constraints in the midst of uncertainty in system parameters. Uncertainty in system parameters and its impact on system performance are modeled stochastically. This stochastic model is then used to derive a quantitative expression for the robustness of a resource allocation. The paper investigates the utility of the proposed stochastic robustness metric by applying the metric to resource allocations in a simulated distributed system. The simulation results are then compared with deterministically defined metrics from the literature

In this paper we discuss the role of a broker in a market-oriented resource allocation model for large-scale heterogeneous systems. The simplified model is based upon a three party system, provider-broker-consumer. The allocation of resources is determined by their price, their utility to the consumer, and by the satisfaction of the consumer. The role of the broker is to add societal objectives to resource allocation algorithms and to mediate between greedy consumers and selfish providers. A simulation experiment was conducted to study the transient and the steady-state behavior of several performance measures, including the average consumer satisfaction, the average utility, and the hourly revenue.

The execution of a complex task in any environment requires planning. Planning is the process of constructing an activity graph given by the current state of the system, a goal state, and a set of activities. If we wish to execute a complex computing task in a heterogeneous computing environment with autonomous resource providers, we should be able to adapt to changes in the environment. A possible solution is to construct a family of activity graphs beforehand and investigate the means of switching from one member of the family to another when the execution of one activity graph fails. In this paper, we study the conditions when plan switching is feasible. Then we introduce an approach for plan switching and report the simulation results of this approach

Minimization of the execution time of an iterative application in a heterogeneous parallel computing environment requires an appropriate mapping scheme for matching and scheduling the subtasks of a given application onto the processors. Often, some of the characteristics of the application subtasks are unknown a priori or change from iteration to iteration during execution-time based on the inputs being processed. In such a scenario, it may not be feasible to use the same off-line-derived mapping for each iteration of the application. One possibility is to employ a semi-static methodology that starts with an initial mapping but dynamically performs remapping between application iterations by observing the effects of the changing characteristics of the application's input data, called dynamic parameters, on the application's execution time. A contribution in this paper is to implement and evaluate a semi-static methodology involving the on-line use of off-line-derived mappings. The off-line phase is based on a genetic algorithm (GA) to generate high-quality mappings for a range of values for the dynamic parameters. A dynamic parameter space partitioning and sampling scheme is proposed that partitions the parameter space into a number of hyper-rectangles, within which the “best” mapping for each hyper-rectangle is stored in a mapping table. During the on-line phase, the actual dynamic parameters are observed and the off-line-derived mapping table is referenced to choose the most suitable mapping. Experimental results indicate that the semi-static approach outperforms a dynamic on-line approach and performs reasonably close to an infeasible on-line GA approach. Furthermore, the semi-static approach considerably outperforms the method of using the same mapping for all iterations.

THE last decade has seen a dramatic increase in the deployment of heterogeneous distributed computing platforms, in particular, those consisting of heterogeneous clusters, and multiple heterogeneous collections of clusters aggregated over wide-area networks into grids. The software infrastructures and mechanisms to deploy such platforms have been well studied and implementations are already used in production, so that heterogeneous platforms represent a significant, and growing, fraction of the computational power delivered by parallel platforms today. In spite of these successes, many research challenges remain, including those pertaining to distributed algorithms and scheduling algorithms, which are critical for ensuring that these platforms are used effectively. In this context, the goal of this special section on “Algorithm Design and Scheduling Techniques (Realistic Platform Models) for Heterogeneous Clusters” is to gather papers that further our understanding of the impact of platform heterogeneity on the design and evaluation of new such algorithms. In the paper entitled “Allocating Non-Real-Time and Soft Real-Time Jobs in Multiclusters,” Ligang He, Stephen A. Jarvis, Daniel P. Spooner, Hong Jiang, Donna N. Dillenberger, and Graham R. Nudd introduce two workload allocation strategies for large-scale heterogeneous platforms. The first strategy achieves an optimized mean response time for jobs having no real-time requirements. The second strategy obtains an optimized mean miss rate for jobs having soft real-time requirements (i.e., a fraction of jobs are permitted to miss the real-time constraints). Both strategies take into account average system behaviors (such as the mean arrival rate of jobs) to calculate the workload proportions for individual clusters, and update on-the-fly the workload allocation when the change in the mean arrival rate reaches a certain threshold. The allocation schemes are combined with two job dispatching strategies (weighted random and weighted round-robin) to generate new job scheduling algorithms for multicluster environments. In their paper “On the Distribution of Sequential Jobs in Random Brokering for Heterogeneous Computational Grids,” Vandy Berten, Joel Goossens, and Emmanuel Jeannot study resource brokering for scheduling sequential jobs onto a grid platform that consists of heterogeneous sets of homogeneous processors, such as a set of clusters. Resources in each cluster are managed by a local scheduler that maintains a job queue. The paper studies a centralized “metascheduler” that uses a randomized strategy to share available resources among competing jobs. This research considers two cases depending on whether the platform is heavily loaded or lightly loaded. For each case, it obtains both analytical and experimental characterizations of the queue lengths at each local scheduler, CPU utilization, and average job slowdowns. Furthermore, the paper presents a discussion of the system’s behavior when it transitions between a heavily loaded state and a lightly loaded one. All presented theoretical results are corroborated by simulations and provide a thorough description of randomized resource brokering. The research in “Multiple Job Scheduling in a Connection-Limited Data Parallel System” presents a new method for scheduling jobs in a distributed system where the critical resource is the bandwidth to access the stored data. The authors, Alessandro Amoroso and Keith Marzullo, describe an approach that supports the master-worker scheme and can be applied to data parallel computation. They consider a typical wide-area data grid that is comprised of a set of sites, where each site has one or more local area networks. The platform model used is based on the Nile data grid. This paper uses a set of synthetic jobs to compare three schedulers: Greedy, Maxfow, and Hybrid. They tested their new approach under various circumstances and measured its performance by means of several metrics. The new Hybrid scheduler is never worse than either of the other two schedulers, and in 20 percent of the simulated runs, it produced runs that were at least 20 percent better. The paper entitled “Capacity-Aware Multicast Algorithms on Heterogeneous Overlay Networks,” coauthored by Zhan Zhang, Shigang Chen, Yibei Ling, and Randy Chow, addresses the problem of multicast for group IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 17, NO. 2, FEBRUARY 2006 97

In a distributed heterogeneous computing system, the resources have different capabilities and tasks have different requirements. Different classes of machines used in such systems typically vary in dollar cost based on their computing efficiencies. Makespan (defined as the completion time for an entire set of tasks) is often the performance feature that is optimized. Resource allocation is often done based on estimates of the computation time of each task on each class of machines. Hence, it is important that makespan be robust against errors in computation time estimates. The dollar cost to purchase the machines for use can be a constraint such that only a subset of the machines available can be purchased. The goal of this study is to: (1) select a subset of all the machines available so that the cost constraint for the machines is satisfied, and (2) find a static mapping of tasks so that the robustness of the desired system feature, makespan, is maximized against the errors in task execution time estimates. Six heuristic techniques to this problem are presented and evaluated

This research investigates two distinct issues related to a resource allocation: its robustness and the failure rate of the heuristic used to determine the allocation. The target system consists of a number of sensors feeding a set of heterogeneous applications continuously executing on a set of heterogeneous machines connected together by high-speed heterogeneous links. There are number of quality of service (QoS) constraints that must be satisfied. A heuristic failure occurs if the heuristic cannot find an allocation that allows the system to meet its QoS constraints. The system is expected to operate in an uncertain environment where the workload, i.e., the load presented by the set of sensors, is likely to change unpredictably, possibly invalidating a resource allocation that was based on the initial workload estimate. The focus of this paper is the design of a static heuristic that: (a) determines a robust resource allocation, i.e., a resource allocation that maximizes the allowable increase in workload until a run-time reallocation of resources is required to avoid a QoS violation, and (b) has a very low failure rate. This study proposes a heuristic that performs well with respect to the failure rates and robustness to unpredictable workload increases. This heuristic is, therefore, very desirable for systems where low failure rates can be a critical requirement and where unpredictable circumstances can lead to unknown increases in the system workload.

Most previous schemes for survivable routing assume that the maximum number of simultaneous link failures is known. In this paper, we take an alternative approach by introducing link failure probabilities to the routing problem, and allowing each link to be used for several channels. Based on these assumptions, we formulate a survivable multipath routing problem for point-to-point communications. We then develop two heuristic multipath routing schemes for this problem: CPMR (conditional-penalization multipath routing) and SPMR (successive-penalization multipath routing). To deal with the difficulty that link-sharing causes, our schemes use "link penalization" methods to control (but not prohibit) link-sharing. We show via simulation that our schemes have significantly higher routing success rates than a routing scheme that searches for disjoint paths.

Summary form only given. An ad hoc computing grid is characterized not only by constraints on the available energy and communications bandwidth associated with each participating device, but also by the dynamic nature of the grid itself. This is caused by the mobile nature of the assets connected to the grid (computing devices, sensors, and users), plus the fragility of interconnecting communication links. The challenge, therefore, is to efficiently and robustly manage both computational and communication resources in this dynamic, unpredictable environment. We report on one potential solution that combines Lagrangian techniques with the receding horizon concept used in modern robust control systems.

Summary form only given. An ad hoc grid is a heterogeneous computing and communication system without a fixed infrastructure; all of its components are mobile. Energy management is a major concern in an ad hoc grid. One important aspect of energy management is to minimize the energy consumption during a mission. In an ad hoc grid, communication and computations are deeply intertwined, and any energy optimization must consider both types of activities together rather than separately. The mapping (defined as matching and scheduling) of tasks onto machines with varied computational capabilities has been shown, in general, to be an NP-complete problem. Therefore, heuristic techniques are required to efficiently map tasks to machines in an ad hoc grid so as to minimize the energy consumed due to communication and computation. This research evaluates and compares energy management issues for resource allocation in ad hoc grids using six static heuristics.

Parallel and distributed systems may operate in an environment that undergoes unpredictable changes causing certain system performance features to degrade. Such systems need robustness to guarantee limited degradation despite fluctuations in the behavior of its component parts or environment. This research investigates the robustness of an allocation of resources to tasks in parallel and distributed systems. The main contributions are 1) a mathematical description of a metric for the robustness of a resource allocation with respect to desired system performance features against multiple perturbations in multiple system and environmental conditions, and 2) a procedure for deriving a robustness metric for an arbitrary system. For illustration, this procedure is employed to derive robustness metrics for three example distributed systems. Such a metric can help researchers evaluate a given resource allocation for robustness against uncertainties in specified perturbation parameters.

A novel certified e-mail protocol that is particularly suitable for mobile environments is described. Our protocol uses an off-line trusted third party (TTP). Protocols with an off-line TTP-also known as optimistic protocols-have numerous practical advantages over protocols with an on-line TTP. Nonetheless, many protocols adopt an on-line TTP primarily because optimistic protocols often entail intricate cryptographic primitives that incur considerable overhead. By using a novel signature paradigm, which we call gradational signatures, we show that it is possible to construct optimistic protocols that are comparable to on-line protocols in terms of computation and communication overhead. This makes our scheme especially desirable in the mobile setting.

We introduce ad hoc grids as a hierarchy of mobile devices with different computing and communication capabilities. An ad hoc grid allows a group of individuals to accomplish a mission, often in a hostile environment; examples of applications of ad hoc grids are disaster management, wild-fire prevention, and peacekeeping operations. We are concerned with the interplay between computing and communication in the power-constrained environment of an ad hoc grid.

Applications such as e-commerce payment protocols, elec-tronic contract signing, and certified e-mail delivery require that fair exchange be assured. A fair-exchange protocol al-lows two parties to exchange items in a fair way so that either each party gets the other's item, or neither party does. We describe a novel method of constructing very ef-ficient fair-exchange protocols by distributing the computa-tion of RSA signatures. Specifically, we employ multisig-natures based on the RSA-signature scheme. To date, the vast majority of fair-exchange protocols require the use of zero-knowledge proofs, which is the most computationally intensive part of the exchange protocol. Using the intrinsic features of our multisignature model, we construct protocols that require no zero-knowledge proofs in the exchange proto-col. Use of zero-knowledge proofs is needed only in the pro-tocol setup phase--this is a one-time cost. Furthermore, our scheme uses multisignatures that are compatible with the underlying standard (single-signer) signature scheme, which makes it possible to readily integrate the fair-exchange fea-ture with existing e-commerce systems.

We describe a novel method for authenticating multicast packets that is robust against packet loss. Our focus is to minimize the size of the communication overhead required to authenticate the packets. Our approach is to encode the hash values and the signatures with Rabin's Information Dispersal Algorithm (IDA) to construct an authentication scheme that amortizes a single signature operation over multiple packets. This strategy is especially efficient in terms of space overhead, because just the essential elements needed for authentication (i.e., one hash per packet and one signature per group of packets) are used in conjunction with an erasure code that is space optimal. Using asymptotic techniques, we derive the authentication probability of our scheme using two different bursty loss models. A lower bound of the authentication probability is also derived for one of the loss models. To evaluate the performance of our scheme, we compare our technique with four other previously proposed schemes using empirical results.

We describe a novel method for authenticating multicast packets that is robust against packet loss. Our main focus is to minimize the size of the communication overhead required to authenticate the packets. Our approach is to encode the hash values and the signatures with Rabin's Information Dispersal Algorithm (IDA) to construct an authentication scheme that amortizes a single signature operation over multiple packets. This strategy is especially efficient in terms of space overhead, because just the essential elements needed for authentication (i.e., one hash per packet and one signature per group of packets) are used in conjunction with an erasure code that is space optimal. To evaluate the performance of our scheme, we compare our technique with four other previously proposed schemes using analytical and empirical results. Two different bursty loss models are considered in the analyses.

Bandwidth allocation is a fundamental problem in communication networks. The problem of bandwidth allocation is further intensified when the requested bandwidth exceeds the available unused bandwidth and so not all requests can be completely served. This research examines on-line bandwidth allocation, where the decision for acceptance or rejection of the request has to be made when future requests and their arrival statistics are not known. A request can be defined as a flow of information from a source to a destination with a certain amount of bandwidth, a priority level, a utility function that is based on the bandwidth received and a worth that is based on the utility function and the priority level. The goal of this research is to develop a scheduling heuristic for an overloaded system that attempts to schedule the requests such that the sum of the worths of the requests satisfied in a fixed interval of rime is the maximum. The scheduling heuristic can preempt or degrade already-scheduled requests. Three different types of utility functions (step, linear, and concave) are examined. Other parameters being considered include network loading and the relative weights of the different priority levels. The heuristic variations developed are shown to perform well compared to a complete sharing policy and an upper bound.

When user's tasks in a distributed heterogeneous computing environment are allocated resources, and the total demand placed on system resources by the tasks, for a given interval of time, exceeds the resources available, some tasks will receive degraded service, receive no service at all, or may be dropped from the system. One part of a measure to quantify the success of a resource management system (RMS) in such an environment is the collective value of the tasks completed during an interval of time, as perceived by the user, the application, or the policy maker. For the case where a task may be a data communication request, the collective value of data communication requests that are satisfied during an interval of time is measured. The Flexible Integrated System Capability (FISC) measure defined here is one way of obtaining a multi-dimensional measure for quantifying this collective value. While the FISC measure itself is not sufficient for scheduling purposes, it can be a critical part of a scheduler or a scheduling heuristic. The primary contribution of this work is providing a way to measure the collective value accrued by an RMS using a broad range of attributes and to construct a flexible framework that can be extended for particular problem domains.

Providing up-to-date input to users' applications is an important data management problem for a distributed computing environment, where each data storage location and intermediate node may have specific data available, storage limitations, and communication links available. Sites in the network request data items and each request has an associated deadline and priority. This work concentrates on solving a basic version of the data staging problem in which all parameter values for the communication system and the data request information represent the best known information collected so far and stay fixed throughout the scheduling process. The network is assumed to be oversubscribed and not all requests for data items can be satisfied. A mathematical model for the basic data staging problem is given. Then, three multiple-source shortest-path algorithm based heuristics for finding a near-optimal schedule of the communication steps for staging the data are presented. Each heuristic can be used with each of four cost criteria developed. Thus, twelve implementations are examined. In addition, two different weightings for the relative importance of different priority levels are considered. The performance of the proposed heuristics is evaluated and compared by simulations. The proposed heuristics are shown to perform well with respect to upper and lower bounds. Furthermore, the heuristics and a complex cost criterion allow more highest priority messages to be received than a simple-cost-based heuristic that schedules all highest priority messages first.

parallel concepts that I can think of grew from analogs in every-day life. Examples include divide and conquer, cloning, load balancing, and synchronization. Even those that do not seem to arise from examples in everyday life, like scalable communication interconnects, can be seen after some thought to have strong analogs outside the world of computing. This leads us to ask the question: Are these concepts influential because they capture the familiar, or are they familiar because they are uniquely powerful concepts? When the panel has disposed of this issue, perhaps it can finally resolve the primacy of the chicken or the egg.

Providing up-to-date input to users' applications is an important data management problem for a distributed computing environment, where each data storage location and intermediate node may have specific data available, storage limitations, and communication links available. Sites in the network request data items and each request has an associated deadline and priority. In a military situation, the data staging problem involves positioning data for facilitating a faster access time when it is needed by programs that will aid in decision making. This work concentrates on solving a basic version of the data staging problem in which all parameter values for the communication system and the data request information represent the best known information collected so far and stay fixed throughout the scheduling process. The network is assumed to be oversubscribed and not all requests for data items can be satisfied. A mathematical model for the basic data staging problem is introduced. Then, three multiple-source shortest-path algorithm-based heuristics for finding a near-optimal schedule of the communication steps for staging the data are presented. Each heuristic can be used with each of four cost criteria developed. Thus, 12 implementations are examined. In addition, two different weightings for the relative importance of different priority levels are considered. The performance of the proposed heuristics are evaluated and compared by simulations. The proposed heuristics are shown to perform well with respect to upper and lower bounds. Furthermore, the heuristics and a complex cost criterion allow more highest priority messages to be received than a simple-cost-based heuristic that schedules all highest priority messages first.

By considering electromagnetic scattering problems as examples, a study of the performance and scalability of the conjugate gradient squared (CGS) algorithm on two MIMD machines is presented. A modified CGS (MCGS) algorithm, where the synchronization overhead is effectively reduced by a factor of two, is proposed in this paper. This is achieved by changing the computation sequence in the CGS algorithm. Both experimental and theoretical analyses were performed to investigate the impact of this modification on the overall execution time.

In a dedicated, mixed-machine, heterogeneous computing (HC) system, an application program may be decomposed into subtasks, then each subtask assigned to the machine where it is best suited for execution. Data relocation is defined as selecting the sources for needed data items. It is assumed that multiple independent subtasks of an application program can be executed concurrently on different machines whenever possible. A theoretical stochastic model for HC Is proposed, in which the computation times of subtasks and communication times for intermachine data transfers can be random variables. The optimization problem for finding the optimal matching, scheduling, and data relocation schemes to minimize the total execution time of an application program is defined based on this stochastic HC model. The global optimization criterion and search space for the above optimization problem are described. It is validated that a greedy algorithm-based approach can establish a local optimization criterion for developing data relocation heuristics. The validation is provided by a theoretical proof based on a set of common assumptions about the underlying HC system and application program. The local optimization criterion established by the greedy approach, coupled with the search space defined for choosing valid data relocation schemes, can help developers of future practical data relocation heuristics.

Motion tracking using an active camera is a very computationally complex problem. Existing serial algorithms have provided frame rates that are much lower than those desired, mainly because of the lack of computational resources. Parallel computers are well suited to image processing tasks and can provide the computational power that is required for real-time motion tracking algorithms. This paper develops a parallel implementation of a known serial motion tracking algorithm, with the goal of achieving greater than real-time frame rates, and to study the effects of data layout, choice of parallel mode of execution, and machine size on the execution time of this algorithm. A distinguishing feature of this application study is that the portion of each image frame that is relevant changes from one frame to the next based on the camera motion. This impacts the effect of the chosen data layout on the needed inter-processor data transfers and the way in which work is distributed among the processors. Experiments were performed to determine for which image sizes and number of processors which data layout would perform better. The parallel computers used in this study are the MasPar MP-1, Intel Paragon, and PASM. Different modes are examined and it is determined that mixed mode is faster than SIMD or MIMD implementations.

As an example of a task that processes complex visual information to generate control signals for a system, an existing feature-based visual tracking algorithm for a static camera was mapped onto two parallel machines representing the MIMD execution model. The algorithm is described and a version suitable for mapping onto parallel machines is developed. Timing results for the implementation on the Intel Paragon and the IBM SP2 are presented, using real image data for all experiments. For each subtask of the algorithm, its performance is measured as a function of data layout. In addition, the impact of the time required to distribute image data across processing elements on the performance is considered. For the subtask of finding the best match of a feature in an image, load balancing approaches dependent on machine characteristics and submachine size are discussed. This type of matching is used in many vision tasks.

In a heterogeneous computing (HC) environment consisting of different types of machines, an application program is decomposed into subtasks, each of which is computationally homogeneous. The goal is to execute subtasks on the machines in such a way that the total program execution time is minimized. A mathematical framework is presented that models the matching of subtasks to machines, scheduling of subtasks' computation, scheduling of intermachine communication steps, and selection of sources of shared data items for intermachine communication (data relocation). The goal of this work is to generate a provably optimal scheme for communicating shared data among subtasks as an enhancement to any given matching and scheduling. Initially, it is assumed that at any instant in time, only one machine is being used for program execution and only one subtask is being executed. Based on this assumption, a polynomial algorithm is introduced to optimize scheduling and data relocation with respect to any given matching of subtasks to machines. The data relocation scheme is then extended to reduce intermachine data communication time in an HC environment with a given matching and scheduling of subtasks' computation where: multiple subtasks' computations can be performed concurrently on different machines; subtask computation steps can be overlapped with other subtasks' communication steps for intermachine data transfers; and machines in the HC suite are interconnected by a shared-bus type of network.

A method to migrate a task dynamically from a virtual SIMD machine to a virtual SPMD machine is proposed. It is assumed that the SIMD and SPMD virtual machine models only differ to support the different modes of parallelism, and that the program was coded in a mode-independent programming language. The difficulty of performing an SIMD to SPMD migration arises from the fact that some SIMD PEs may be disabled at the point in the program at which the migration occurs. Furthermore, each of the disabled PEs may need to be re-enabled at different points in the SPMD program. The compiler information that should be furnished to the task migration procedure is given. The time and memory space complexities of the task migration procedure are also presented. The work solves part of the general problem of task migration in SIMD/SPMD mixed-machine heterogeneous systems.

One type of interconnection network for a medium to large-scale parallel processing system (i.e., a system with 2/sup 6/ to 2/sup 16/ processors) is a buffered packet-switched multistage interconnection network (MIN). It has been shown that the performance of these networks is satisfactory for uniform network traffic. More recently, several studies have indicated that the performance of MIN's is degraded significantly when there is hot spot traffic, that is, a large fraction of the messages are routed to one particular destination. A multipath MIN is a MIN with two or more paths between all source and destination pairs. This research investigates how the Extra Stage Cube multipath MIN can reduce the detrimental effects of tree saturation caused by hot spots. Simulation is used to evaluate the performance of the proposed approaches. The objective of this evaluation is to show that, under certain conditions, the performance of the network with the usual routing scheme is severely degraded by the presence of hot spots. With the proposed approaches, although the delay time of hot spot traffic may be increased, the performance of the background traffic, which constitutes the majority of the network traffic, can be significantly improved.>

Parallel processing has been a subject of extensive research for over 20 years, especially in the last 10 years, with many commercial parallel machines becoming available, from small scale parallel machines to massively parallel machines. At one time, it was claimed that parallel machines will become the mainstream computers. However, more recently, some parallel computer vendors have gone out of business and some others are struggling. Some pessimists even claimed that this is a dying field. So, what’s wrong? Five distinguished panelists are invited to share their views on this issue. The panelists are also expected to address what could be done and could be done in order to make parallel computers truly mainstream computers. Panelists

The transmission of digitized images over limited bandwidth channels motivates the use of data compression techniques. Many data compression techniques are not suitable for such applications because compression ratios of more than 20:1 are often required. One technique that can provide this level of compression is vector quantization. The processes of codebook generation and, especially, encoding and decoding are tasks well suited for execution on a massively parallel machine. For codebook generation, an SIMD algorithm is developed whose control flow is based on sequencing through the training data, rather than the tree structure, to achieve improved performance. Results from execution on the 16384 processor MasPar MP-1 SIMD machine are presented. The approaches taken could be adapted for other SIMD as well as MIMD machines.

A mixed-mode parallel machine's processing elements are capable of operating in and switching between the SIMD and MIMD modes of parallelism. This paper analyzes various mappings of image correlation algorithms onto a mixed-mode parallel processing system. The trade-offs that exist between the SIMD and MIMD modes are the primary basis employed in comparing different mappings of a parallel algorithm onto a mixed-mode system. The scalability of the image correlation algorithms discussed here is shown to be impacted by the mode of parallelism used. The analytical results are supported by experiments on the PASM prototype.

A method to migrate a task dynamically from a virtual SPMD machine to a virtual SIMD machine is proposed. It is assumed that the SIMD and SPMD virtual machine models only differ to support the different modes of parallelism, and that the program was coded in a mode-independent programming language. The migration procedure does not require the SPMD PEs to be at the same location in the SPMD program at the time of the migration. This work is directly applicable to mixed-mode hybrid SIMDISPMD systems and part of the general problem of task migration in SIMDISPMD mixed-machine heterogeneous systems.

Methods for enhancing multistage interconnection network simulators running on massively parallel SIMD computers are presented. Aspects of parallel simulation of interconnection networks are discussed and different strategies of mapping the architecture of the network to be simulated onto the parallel machine are studied and compared. As case studies, two strategies of mapping synchronous multistage cube networks onto the MasPar MP-1 SIMD machine are explored and their implementations are compared. The methods result in an efficient simulator which can process 10^9 data packets in 40 minutes.

If a processor develops a permanent fault during the execution of a task on a dynamically reconfigurable parallel machine, three recovery options are task migration to a fault-free subdivision, task migration to another submachine, and task redistribution. Quantitative models of these three reconfiguration schemes are analyzed, together with the cost of making the wrong choice, to develop guidelines for selecting among these methods in a practical dynamic reconfiguration implementation. A multistage cube or hypercube inter-processor network is assumed. The PASM and nCUBE 2 parallel machines are used as vehicles for studying the model parameters.

Is it possible to create one idealized parallel com puter model to provide an interface between hardware and software performance that supports a machineindependent framework for specifying various compu tational costs? Is it necessary to have more than one? What attributes should this model(s) have? Does such a model(s) exist today? How can we create such a model(s)? Is it important to have such a model(s)?

Parallel implementations of the computationally intensive task of solving multiple quadratic forms (MQFs) have been examined. Coupled and uncoupled parallel methods are investigated, where coupling relates to the degree of interaction among the processors. Also, the impact of partitioning a large MQF problem into smaller non-interacting subtasks is studied. Trade-offs among the implementations fo various data-size/machine-size ratios are categorized in terms of complex arithmetic operation counts, communicatino overhead, and memory storage requirements.

One type of interconnection network for a medium to large-scale parallel processing system (i.e., a system with 26 to 216 processors) is a buffered packet-switched multistage interconnection network (MIN). It has been shown that the per formance of these networks is satisfactory for uniform network traffic. More recently, several studies have indicated that the performance of MINs is degraded significantly when there is hot spot traffic, that is, a large fraction of the messages are routed to one particular destination. A multipath MIN is a MIN with two or more paths between all source and destination pairs. This research investigates how the Extra Stage Cube multipath MIN can reduce the detrimental effects of tree satura tion caused by hot spots. Simulation is used to evaluate the per formance of the proposed approach. The objective of this evaluation is to show that, under certain conditions, the perfor mance of the network with the usual routing scheme is severely degraded by the presence of hot spots. With the proposed approach, although the delay time of hot spot traffic may be increased, the performance of the background traffic, which constitutes the majority of the network traffic, can be significantly improved.

Features of an explicitly parallel programming language targeted for reconfigurable parallel processing systems, where the machine's N processing elements (PEs) are capable of operating in both the SIMD and SPMD modes of parallelism, are described. The SPMD (single program-multiple data) mode of parallelism is a subset of the MIMD mode where all processors execute the same program. By providing all aspects of the language with an SIMD mode version and an SPMD mode version that are syntactically and semantically equivalent, the language facilitates experimentation with and exploitation of hybrid SIMD/SPMD machines. Language constructs (and their implementations) for data management, data-dependent control-flow, and PE-address-dependent control-flow are presented. These constructs are based on experience gained from programming a parallel machine prototype and are being incorporated into a compiler under development. Much of the research presented is applicable to general SIMD machines and MIMD machines.>

A 'state model' is proposed for solving the problem of routing and rerouting messages in the inverse augmented data manipulator (IADM) network. Necessary and sufficient conditions the reroutability of messages are established using this model, and destination tag schemes are derived. These schemes are simpler, more efficient, and require less complex hardware than previously proposed routing schemes. Two destination tag schemes are proposed. A universal rerouting algorithm is constructed based on one of the schemes. It finds a blockage-free path for any combination of multiple blockages if there exists such a path, and indicates the absence of such a path if there exists none. In addition, the state model is used to derive constructively a lower bound on the number of subgraphs which are isomorphic to the indirect binary n-cube network in the IADM network. This knowledge can be used to characterize properties of the IADM networks and for permutation routing in the IADM networks.>

Language constructs (and their implementations) for execution mode management and achieving the overlap of control unit and processor operations in an explicitly parallel programming language are described. These are targeted to reconfigurable parallel processing systems, where the machine's processors are capable of operating in both the single-instruction-multiple data (SIMD) and single program-multiple data (SPMD) modes of parallelism. The SPMD mode of parallelism is a subset of the multiple instruction-multiple data (MIMD) mode where all processors execute the same program. By providing all aspects of the language with an SIMD and an SPMD version that are syntactically and semantically equivalent, the language facilitates experimentation with and exploitation of hybrid SIMD/SPMD machines.>

A discussion of how three algorithms can map onto parallel processing systems is presented. Issues addressed are single instruction multiple data (SIMD)/multiple instruction multiple data (MIMD) tradeoffs, mixed-mode parallelism, the impact of partitioning the system for subtask parallelism, the effect on execution time of increasing the number of processors used, and the advantages of a flexible interprocessor communications network.>

The problem of using the idle cycles of a number of high-performance workstations, interconnected by a high-speed network, for solving computationally intensive tasks is discussed. The classes of distributed applications examined require some form of synchronization among the sub-tasks, hence the need for coscheduling to guarantee that sub-tasks start at the same time and execute at the same pace on a group of workstations. A model of the system that allows the definition of an objective function to be maximized is presented. Then a quadratic time and linear space algorithm is derived for computing the optimal coscheduling.>

No abstract available.

Efficient data layout is an important aspect of the compilation process. A model for the creation of perfect memory maps for large-scale parallel machines capable of user-controlled partitionable single-instruction-multiple data/single-program-multiple data (SIMD/SPMD) operation is developed. The term perfect implies that no memory fragmentation occurs and ensures that the memory map size is kept to a minimum. A major constraint on solving this problem is based on the single program nature of both the SIMD and SPMD modes of parallelism. It is assumed that all processors within the same submachine used identical addresses to access corresponding data items in each of their local memories. Necessary and sufficient conditions are derived for being able to create perfect memory maps, and results are applied to several partitionable interconnection networks.>

The design of a debugging and performance analysis system that includes a specification language for process-level events and hardware for nonintrusive identification of these events during the execution of parallel and distributed application for a nonshared memory system is presented. The design is based on a formal event/action model and a layered architecture model that have been previously presented. Background, related work, and specification, and identification of events are discussed.>

Experimentation aimed at determining the potential benefit of mixed-mode SIMD/MIMD (single instruction, multiple data/multiple instruction, multiple data) parallel architectures is reported. The experimentation is based on timing measurements made on the PASM (Partitionable SIMD/MIMD) system prototype utilizing carefully coded synthetic variations of a well-known algorithm. The synthetic algorithms used to measure and evaluate this system were based on bitonic sorting of sequences stored in the processing elements. This computation was mapped to both the hybrids of the SIMD and MIMD modes. The computations were coded in these four ways and experiments were performed that explore the tradeoffs among them. The results of these experiments are presented and discussed, with special consideration of the effects of the system's architecture. The goal is to obtain implementation-independent analyses of the attributes of mixed-mode parallel processing with respect to the computational characteristics of the application being examined.>

A distributed scheme for dynamic partitioning is investigated. Distributed procedures to split a subsystem and to combine subsystems are presented. The correctness of each of these two procedures is shown, and the complexity is analyzed. The procedures are applicable to parallel computers that use interconnection networks, such as hypercube, omega, multistage cube, and extra-stage cube networks.>

Several aspects of the multidimensional problem of providing monitoring support for the debugging and performance analysis of distributed and parallel systems and parallel applications are presented. The key elements of the solution to the problem are a formal event-action model at the process level and a layered architectural model. The application of the event-action model to the development of the abstract layered architectural model is shown, as well as a proposed implementation sketch of a nonintrusive monitor for the PASM parallel processing system.>

Systems that have the capability of executing tasks with various sizes and computation structures simultaneously are considered. When some of the tasks are completed, part of the system becomes idle and is reconfigured for new tasks. Inappropriate reconfiguration strategies can create resource fragments and result in a loss of computation power. This problem can be alleviated by partitioning the system dynamically. Partitioning consists of two processes: splitting the system or a subsystem into smaller subsystems, and combining unallocated subsystems into larger subsystems. These two processes are investigated analytically for a lattice model that uses a special partial ordering relation on a set. The complexities of these two processes are also analyzed. The method can be applied to any system that can be modeled by a lattice.>

A state model is proposed for solving the problem of routing and rerouting messages in the inverse augmented data manipulator (IADM) network. Using this model, necessary and sufficient conditions for the reroutability of messages are established, and two then destination tag schemes are derived. For one of the schemes, rerouting is totally transparent to the sender of the message and any blocked line of a given type can be avoided. The spatiotemporal complexity is reduced from O(log N) (for previous techniques) to O(1). For the other scheme, rerouting is possible for any type of link blockage. A universal rerouting algorithm is constructed based on the second scheme, which finds a blockage-free path for any combination of multiple blockages if there exists such a path, and indicates absence of such a path if none exists. In addition, the state model is used to constructively derive a lower bound on the number of subgraphs which are isomorphic to the indirect binary n-cube network in the IADM network. This knowledge can be used to characterize properties of the IADM networks and for permutation routing in the IADM networks.>

The dynamic redundancy (DR) network is investigated in relation to fault-tolerant design for multistage interconnection network (MIN) based systems. The DR network can tolerate faults in the network and support a system to tolerate processing element (PE) faults without degradation by adding spare PEs, while retaining the full capability of a multistage cube network. A variation of the DR network, the reduced DR network, is also considered, that can be implemented more cost effectively than the DR while retaining most of the advantages of the DR. The reliabilities of DR-based systems with one spare PE and the reliabilities of systems with no spare PEs are estimated and compared, and the effect of adding multiple spare PEs is analyzed.>

One class of reconfigurable parallel processing systems is based on the use of a large number of processing elements which can be partitioned into multiple virtual machines. Each virtual machine is controlled by one or more control units. The multiple control units in such a system share a common secondary storage for programs. The control units use paging to transfer programs to their primary memories. One design problem is determining the optimal service rate for the secondary storage of the control units, where the "optimal" is characterized by maximum processor utilization. The PASM parallel processing system is used as a example system to study this problem. The implementation of virtual memory on the PASM control system memory hierarchy is discussed and a queueing network model for the memory hierarchy is developed. Based on assumed values for parameters that characterize the expected task environment, an optimal service rate is derived from the model. The values of the parameters in the model can be varied to determine the impact these changes would have on system performance. Simulation results verifying various aspects of the model are presented and the results are generalized.

An integral part of any parallel processing system is its interconnection network.These networks have been the objects of intense research in recent years.Existing Markov chain analysis techniques for circuit switched, generalized cube interconnection networks will be extended to allow the performance modeling of partitionable SIMD/MIMD systems.Based on both analysis and simulation data, the relationship between the network performance, the partitioning scheme employed, and the conflict resolution algorithm used within the network will be enumerated.It will be shown that "input partitioning" coupled with the use of the "hold" conflict algorithm produces the best network operation in terms of the time to establish a circuit switched path through the network.Additionally, it will be shown that the performance of partitioned subnetworks is generally better than the performance of comparable sized random groupings of network resources.

article Models for use in the design of macro-pipelined parallel processors Share on Authors: Bradley Warren Smith PASM Parallel Processing Laboratory, School of Electrical Engineering, Purdue University, West Lafayette, IN PASM Parallel Processing Laboratory, School of Electrical Engineering, Purdue University, West Lafayette, INView Profile , Howard Jay Siegel PASM Parallel Processing Laboratory, School of Electrical Engineering, Purdue University, West Lafayette, IN PASM Parallel Processing Laboratory, School of Electrical Engineering, Purdue University, West Lafayette, INView Profile Authors Info & Claims ACM SIGARCH Computer Architecture NewsVolume 13Issue 3June 1985 pp 116–123https://doi.org/10.1145/327070.327140Online:01 June 1985Publication History 0citation294DownloadsMetricsTotal Citations0Total Downloads294Last 12 Months4Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

One class of networks suitable for use in parallel processing systems is the multistage cube network. The authors focus on fault location procedures suitable for use in networks that use distributed routing control through the use of routing tags and message transmission protocols. Faults occurring in the data lines can corrupt message routing tags transmitted over them and thereby cause misrouting of messages. Protocol lines (used in handshaking between network sources and destinations), if faulty, can prevent a message path from being established or can cause the path to `lock up' once transmission of data has begun. These faults have more pronounced effects on the network performance than faults previously considered for centralized routing control systems. The single-fault location procedures presented form a logical superset to those of the centralized control systems (where message routing is dictated by the actions of a global control unit) and can be adapted for use in both circuit and packet switching networks.

In order to program SIMD (single instruction stream-multiple data stream) parallel machines used for tasks such as speech and image processing, a language with explicit parallel constructs is often desirable. The language Ada, developed by the Department of Defense, is used here as a basis for such a language. Extensions of Ada, which allow the user to specify such operations as interprocessor communications and activation of processors, are proposed. These features are demonstrated by showing their use in a common speech processing algorithm, the parallel FFT.

PASM is a proposed large-scale distributed/parallel processing system which can be partitioned into independent SIMD/MIMD machines of various sizes. One design problem for systems such as PASM is task scheduling. The use of multiple FIFO queues for nonpreemptive task scheduling is described. Four multiple-queue scheduling algorithms with different placement policies are presented and applied to the PASM parallel processing system. Simulation of a queueing network model is used to compare the performance of the algorithms. Their performance is also considered in the case where there are faulty control units and processors. The multiple-queue scheduling algorithms can be adapted for inclusion in other multiple-SIMD and partitionable SIMD/MIMD systems that use similar types of interconnection networks to those being considered for PASM.

Recent progress in integrated circuit technology has made parallel processing a practical method for dealing with large-scale computational problems. A wide variety of parallel architectures have been proposed. Many different languages have been developed for use on these architectures, with various conventional languages being the base language. The ways in which these parallel languages approach the problem of data management are discussed. Methods of data transferrai and their relationship to the underlying architectures are examined. Transferrai among processor memories and between primary and secondary memory will both be discussed. Data allocation among processor memories will also be described.

Two SIMD single-stage interconnection networks which have been proposed and studied in the literature are the Illiac type and PM2I. The ability of the Illiac and PM2I networks to perform the shuffle data permutation in an SIMD machine with N processors is examined. Two algorithms for an SIMD or multiple-SIMD machine with the PM2I network to perform the shuffle are given. One algorithm is used in the event that the SIMD machine is of the same size (in terms of number of processors) as the shuffle to be emulated. The other algorithm is used when the shuffle to be performed is of smaller size than the given machine with the PM2I network. It is proven that both algorithms require only one more network transfer than the previously published lower bound (which is log2S for a shuffle on S elements). Using the PM2I algorithm as a basis, an algorithm for the Illiac to emulate the shuffle is given. Its performance is 2√N - 1 transfers which is only three transfers more than the previously published lower bound of 2√N - 4.

One class of reconfigurable parallel processing systems is based on the use of a large number of processing elements where each processing element consists of a processor and a primary memory. To efficiently employ the processing elements, it is desirable to overlap the operation of the secondary storage with computations being performed by the processors. Due to the dynamically reconfigurable architecture of such systems, the processors which will execute a new task may not be selected until they are ready to run the task. That is, a task must be preloaded prior to the final selection of the processors on which it will execute. Two schemes which allow for the secondary storage to preload input data and programs into the primary memories so that processor utilization can be increased and system response time decreased are presented. PASM is used as an example system for comparing the performance of the schemes by simulation studies. Results show that both methods are effective techniques. These schemes can be applied to reconfigurable parallel processing systems which use a centralized scheduling policy.

The Inverse Augmented Data Manipulator (IADM) is a multistage interconnection network based on the Augmented Data Manipulator (ADM) and Feng's data manipulator. It is designed to be used in large-scale parallel/distributed processing systems for communication among processors, memories, and other system devices. Two aspects of IADM network design are discussed: performance and fault tolerance. A single stage look-ahead scheme for predicting blockage is presented to enhance performance. Next, one method of adding some links to the network to enable it to tolerate one link failure is described. Finally, a different method of adding links is shown that both improves performance and allows the network to tolerate two switching element or two link failures. Included is a new routing tag scheme that accommodates the new links.

The Augmented Data Manipulator (ADM) network has been proposed as an interconnection network for SIMD machines. As one measure for comparing the ADM network to multistage cube networks, the number of distinct data permutations performable in a single pass through the ADM is examined. Techniques are given to count the number of settings of any stage of the network which are permutations. Upper and lower bounds on the number of distinct permutations performable by the network are proven.

The Extra Stage Cube (ESC) interconnection network, a fault-tolerant structure, is proposed for use in large-scale parallel and distributed supercomputer systems. It has all of the interconnecting capabilities of the multistage cube-type networks that have been proposed for many supersystems. The ESC is derived from the Generalized Cube network by the addition of one stage of interchange boxes and a bypass capability for two stages. It is shown that the ESC provides fault tolerance for any single failure. Further, the network can be controlled even when it has a failure, using a simple modification of a routing tag scheme proposed for the Generalized Cube. Both one-to-one and broadcast connections under routing tag control are performable by the faulted ESC. The ability of the ESC to operate with multiple faults is examined. The ways in which the ESC can be partitioned and permute data are described.

There have been many multistage interconnection networks proposed in the literature for interconnecting the processors that comprise large parallel processing systems. In this paper, the use of the Augmented Data Manipulator and Inverse Augmented Data Manipulator multistage networks in the MIMD mode of operation is considered. A tag based routing scheme which allows distributed control of either network is proposed. Rerouting schemes that allow a message blocked by a busy or known faulty node in its present path to dynamically make use of a nonbusy node and continue, when possible, are described for both networks. Finally, a tag based broadcasting scheme for the networks is introduced that allows one processor to send messages to a subset of the other processors.

Image correlation is representative of a wide variety of window-based image processing tasks. The way in which multimi-croprocessor systems (e.g., PASM) can use SIMD parallelism to perform image correlation is examined. Two fundamental algorithm strategies are explored. In one approach, all of the data that will be needed in a processor are transferred to the processor and operated on there. In the other, each processor performs all possible operations on its local data, generating partial results which are then transferred to the processor in which they are needed. The "time/space/inter-processor-transfer" complexities of the two algorithm approaches are analyzed in order to quantify the differences resulting from the two -strategies. For both approaches, the asymptotic time complexity of the N-processor SIMD algorithms is (1/N)th that of the corresponding serial algorithms.

This paper examines measures for evaluating the performance of algorithms for single instruction stream–multiple data stream (SIMD) machines. The SIMD mode of parallelism involves using a large number of processors synchronized together. All processors execute the same instruction at the same time; however, each processor operates on a different data item. The complexity of parallel algorithms is, in general, a function of the machine size (number of processors), problem size, and type of interconnection network used to provide communications among the processors. Measures which quantify the effect of changing the machine-size/problem-size/network-type relationships are therefore needed. A number of such measures are presented and are applied to an example SIMD algorithm from the image processing problem domain. The measures discussed and compared include execution time, speed, parallel efficiency, overhead ratio, processor utilization, redundancy, cost effectiveness, speed-up of the parallel algorithm over the corresponding serial algorithm, and an additive measure called "sprice" which assigns a weighted value to computations and processors.

PASM, a large-scale multimicroprocessor system being designed at Purdue University for image processing and pattern recognition, is described. This system can be dynamically reconfigured to operate as one or more independent SIMD and/or MIMD machines. PASM consists of a parallel computation unit, which contains N processors, N memories, and an interconnection network; Q microcontrollers, each of which controls N/Q processors; N/Q parallel secondary storage devices; a distributed memory management system; and a system control unit, to coordinate the other system components. Possible values for N and Q are 1024 and 16, respectively. The control schemes and memory management in PASM are explored. Examples of how PASM can be used to perform image processing tasks are given.

There have been many multistage interconnection networks proposed in the literature for interconnecting the processors that comprise large parallel processing systems. In this paper, the use of a multistage network in the MIMD mode of operation is considered. A tag based routing scheme is proposed for the Augmented Data Manipulator network. Also included is a rerouting scheme that allows a message blocked by a busy link in its present path to dynamically make use of a non-busy link and continue, when possible. Finally, a tag based broadcasting scheme is introduced that allows one processor to send messages to a power of two other processors.

The age of the microcomputer has made feasible large-scale multiprocessor systems. In order to use this parallel processing power in the form of a flexible multiple-SIMD (MSIMD) system, the interconnection network must be partitionable and dynamically reconfigurable. The theory underlying the partitioning of MSIMD system permutation networks into independent subnetworks is explored. Conditions for determining if a network can be partitioned into independent subnetworks and the ways in which it can be partitioned are presented. The use of the theory is demonstrated by applying it to the Cube, Illiac, PM2I, and Shuffle-Exchange SIMD machine interconnection networks. Both recirculating (single stage) and multistage network implementations are considered.

The emulator network, a single stage interconnection network, can be used to simulate a wide variety of single stage and multistage SIMD interconnection networks. These include the STARAN, the omega, the data manipulator, and the Illiac networks. A hardware design for the emulator network is presented. It is shown how the emulator network can be used to test different network control schemes. Its performance in a partitioned machine environment is discussed. It is well suited for use in SIMD system prototypes being built to study the effectiveness of various design parameters.

A formal mathematical model of single instruction stream-multiple data stream (SIMD) machines is defined. It is used as a basis for analyzing various types of interconnection networks that have been discussed in the literature. The networks are evaluated in terms of the lower and upper bounds on the time required for each of the networks discussed to simulate the other networks. SIMD machine algorithms are presented as proofs of the upper time bounds on these simulation tasks. These simulations are used to demonstrate techniques for proving the correctness of SIMD machine algorithms, i.e., analyzing the simultaneous flow of N data items among N processors. Processor address masks, a concise notation for activating and deactivating processors, are used in the algorithms. The methods used to prove the lower bounds and to construct (and prove correct) simulation algorithms to show the upper bounds can be generalized and applied to the analysis of other networks.

Four SIMD multistage networks - Feng's data manipulator, STARAN flip network, omega network, and indirect binary n-cube—are analyzed. Three parameters - topology, interchange box, and control structure—are defined. It is shown that the latter three networks use equivalent topologies and differences in their capabilities result from the other parameters. An augmented data manipulator network using a modified control structure to perform more single pass interconnections than the other networks is presented. Some problems may be solved more efficiently if the 2n processing elements of an SIMD machine can be partitioned into submachines of size 2r. Single and multiple control partitioning are defined. The capabilities of these multistage networks to perform in these partioned environments are discussed.

SIMD machine architects must choose an interconnection network to provide interprocessor communication. The universality of a network is its ability to simulate arbitrary interconnections of the processing elements. We examine the universality of five particular networks which cover the types used in the Illiac IV, STARAN, Omen, SIMDA, and RAP machines. They also cover the types discussed by Feng, Lang, Lawrie, Orcutt, Siegel, and Stone. We give O((log2N)2) algorithms, where N is the number of processing elements, for the Perfect Shuffle, PM21, WPM21, and Cube networks to simulate arbitrary interconnections (Orcutt has given an O(N1/2log2N) algorithm for the Illiac network). We analyze Batcher's bitonic sorting method and show how each network can implement it on an SIMD machine. We discuss how sorting destination tags is equivalent to simulating interconnections.

Various techniques for evaluating and comparing interconnection networks for SIMD machines are presented. These techniques are demonstrated by using them to analyze the networks that have been proposed in the literature. The model of SIMD machines used in the first part of the paper requires all data transfers between processing elements to be representable as permutations on the processing element addresses. We use the theory of permutation groups to aid in the analysis of the cycle structures of the different interconnection networks and discuss the importance of the cycle structure to the SIMD machine architect. A processing element address masking scheme, to determine which processing elements will be active, is introduced. The effects of this masking system when used with different networks are examined. Model independent techniques for proving lower bounds on the time required for a network to simulate a particular interconnection are presented. These techniques are used to prove a lower time bound on the simulation of each network by each of the other networks.