多核系统的多应用任务映射方法研究*

在多核处理器系统中,多个计算任务映射到多核处理器内核的方式对于系统吞吐率至关重要。针对此问题提出一种新的多应用任务到多核的映射算法,该算法在应用到来之前预测应用的相关性能,并采用分支限界法提前为未来应用预留合适的内核几何位置。当应用真正到来时,根据预留的区域完成映射。实验结果表明,该算法相比其他传统算法,在多任务通信量的减少和多核系统的吞吐率等方面都收到了良好效果。     

Liana: a decentralized load-dependent scheduler for performance-cost optimization of grid service

This paper addresses the scheduling problem in decentralized grid systems. Such problem focuses on computing a large set of arbitrary tasks to optimize the system performance while minimizing the average system costs. The mainstream solution flourished in recent literatures is to maximize the total system throughput by modeling such systems in either a network flow or a tree. However, most of them neglect the movements of tasks and load-dependent system costs which, in fact, are crucial to the system performance in real situations. In this paper, a Service-Oriented Overlay Network (SOON) is presented, in which the service nodes encapsulate both computation and communication resources and the links are used to track the movements of tasks instead of describing communication. An analytical Cost-Charge (C²) model, in which both running cost and service charge are dependent on load, is proposed to describe the problem by incorporating degree-dependent task allocation into a closed queuing network model. The Infinitesimal Perturbation Analysis (IPA) is applied to solve C² theoretically. Following the theoretical analysis, a scalable decentralized scheduler named Liana (the movements of tasks in the proposed system like the growth and spread of evergreen liana, so we use Liana to name the proposed scheduler) is proposed. The major components of Liana are an autonomous scheduling algorithm and a Degree-Driven Protocol (DDP). Furthermore, trace based simulations on the test bed distributed widely across the world are implemented to compare the system performance by Liana with recent approaches. The proposed approach shows promising results that the close-to-optimal service utilization is achieved when taking system cost into account.

Task assignment using a problem-space genetic algorithm

The task assignment problem is one of assigning tasks of a parallel program among the processors of a distributed computing system in order to reduce the job turnaround time and to increase the throughput of the system. Since the task assignment problem is known to be NP-complete except in a few special situations, satisfactory suboptimal solutions obtainable in a reasonable amount of computation time are generally sought. In the paper we introduce a technique based on the problem-space genetic algorithm (PSGA) for the static task assignment problem in both homogeneous and heterogeneous distributed computing systems to reduce the task turnaround time and to increase the throughput of the system by properly balancing the load and reducing the interprocessor communication time among processors. The PSGA based approach combines the power of genetic algorithms, a global search method, with a simple and fast problem-specific heuristic to search a large solution space efficiently and effectively to find the best possible solution in an acceptable CPU time. Experimental results on test examples from the literature show considerable improvements in both the assignment cost and the CPU times over the previous work. The proposed scheme is also applied to a digital signal processing (DSP) system consisting of 119 tasks to illustrate its balancing properties and computational advantage on a large system. The proposed scheme offers 12–30% improvement in the assignment cost as compared to the previous best known results for the DSP example.     

一种基于综合匹配度的边缘计算系统任务调度方法

边缘计算模式满足数据的实时和低功耗处理需求,是缓解当前网络数据洪流实时处理问题的有效方法之一.但边缘设备资源的异构与多样性给任务的调度与迁移带来极大的困难与挑战.目前,边缘计算任务调度研究主要集中在调度算法的设计与仿真,这些算法和模型通常忽略了边缘设备的异构性和边缘任务的多样性,不能使多样化的边缘任务与异构的资源能力深...     

Performance estimation for real-time distributed embedded systems

Many embedded computing systems are distributed systems: communicating processes executing on several CPUs/ASICs. This paper describes a performance analysis algorithm for a set of tasks executing on a heterogeneous distributed system. Tight bounds are essential to the synthesis and verification of application-specific distributed systems, such as embedded computing systems. Our bounding algorithms are valid for a general problem model: The system can contain several tasks with hard real-time deadlines and different periods; each task is partitioned into a set of processes related by data dependencies. The periods of tasks and the computation times of processes are not necessarily constant and can be specified by a lower bound and an upper bound. Such a model requires a more sophisticated algorithm, but leads to more accurate results than previous work. Our algorithm both provides tighter bounds and is faster than previous methods     

Auditing Causal Relationships of Group Multicast Communications in Group-Oriented Distributed Systems

Auditability is a crucial aspect of distributed computing security. In a distributed computation environment, we may therefore want to prevent corrupt processes from denying or forging causal relationships between events. The audit of causal relationships of group multicast communications is an important component in achieving a solution to the problem of group-oriented distributed computing security. In this paper, a new approach to audit causal relationships of group multicast communications in group-oriented distributed systems is proposed. The goal of the auditing service is to collect, maintain, make available, and validate irrefutable evidence regarding causal relationships in group-oriented distributed systems. We affirm that the denial of existing causal relationships and the forgery of nonexistent causal relationships in group-oriented distributed systems can be correctly audited by our proposed approach. Also, auditing the causal delivery ordering for group multicast communications can actually be achieved. Moreover, we have validated the proposed auditing scheme to a moderately complex example. Experience indicates that the proposed scheme is indeed very useful.     

Peer-to-peer secure multi-party numerical computation facing malicious adversaries

We propose an efficient framework for enabling secure multi-party numerical computations in a Peer-to-Peer network. This problem arises in a range of applications such as collaborative filtering, distributed computation of trust and reputation, monitoring and other tasks, where the computing nodes are expected to preserve the privacy of their inputs while performing a joint computation of a certain function. Although there is a rich literature in the field of distributed systems security concerning secure multi-party computation, in practice it is hard to deploy those methods in very large scale Peer-to-Peer networks. In this work, we try to bridge the gap between theoretical algorithms in the security domain, and a practical Peer-to-Peer deployment. We consider two security models. The first is the semi-honest model where peers correctly follow the protocol, but try to reveal private information. We provide three possible schemes for secure multi-party numerical computation for this model and identify a single light-weight scheme which outperforms the others. Using extensive simulation results over real Internet topologies, we demonstrate that our scheme is scalable to very large networks, with up to millions of nodes. The second model we consider is the malicious peers model, where peers can behave arbitrarily, deliberately trying to affect the results of the computation as well as compromising the privacy of other peers. For this model we provide a fourth scheme to defend the execution of the computation against the malicious peers. The proposed scheme has a higher complexity relative to the semi-honest model. Overall, we provide the Peer-to-Peer network designer a set of tools to choose from, based on the desired level of security.     

Distributed Throughput Maximization in P2P VoD Applications

In peer-to-peer (P2P) video-on-demand (VoD) systems, a scalable source coding is a promising solution to provide heterogeneous peers with different video quality. In this paper, we present a systematic study on the throughput maximization problem in P2P VoD applications. We apply network coding to scalable P2P systems to eliminate the delivery redundancy. Since each peer receives distinct packets, a peer with a higher throughput can reconstruct the video at a higher quality. We maximize the throughput in the existing buffer-forwarding P2P VoD systems using a fully distributed algorithm. We demonstrate in the simulations that the proposed distributed algorithm achieves a higher throughput compared to the proportional allocation scheme or the equal allocation scheme. The existing buffer-forwarding architecture has a limitation in total upload capacity. Therefore we propose a hybrid-forwarding P2P VoD architecture to improve the throughput by combining the buffer-forwarding approach with the storage-forwarding approach. The throughput maximization problem in the hybrid-forwarding architecture is also solved using a fully distributed algorithm. We demonstrate that the proposed hybrid-forwarding architecture greatly improves the throughput compared to the existing buffer-forwarding architecture. In addition, by adjusting the priority weight at each peer, we can implement the differentiated throughput among different users within a video session in the buffer-forwarding architecture, and the differentiated throughput among different video sessions in the hybrid-forwarding architecture.      

A grid computing based approach for the power system dynamic security assessment

This paper addresses the problem of parallel dynamic security assessment applications from static homogeneous cluster environment to dynamic heterogeneous grid environment. Functional parallelism and data parallelism are supported by each of the message passing interface model and TCP/IP model. To consider the differences in heterogeneous computing resources and complexity of large-scale power system communities, a kernel-based multilevel algorithm is proposed for network partitioning. Since the bottleneck in distributed computation is low speed network communication, a bi-level latency exploitation technique is introduced for numerically solving system differential equations. The proposed grid-based implementation includes the core simulation engine, grid computing middleware, a Python interface and Python front-end utilities. Tests for a 39-bus network, a 4000-bus network and a 10,000-bus network are reported, and the results of these experiments demonstrate that the proposed scheme is able to execute the distributed simulations on computational grid infrastructure and provide efficient parallelism.     

Multiagent task allocation in social networks

This paper proposes a new variant of the task allocation problem, where the agents are connected in a social network and tasks arrive at the agents distributed over the network. We show that the complexity of this problem remains NP-complete. Moreover, it is not approximable within some factor. In contrast to this, we develop an efficient greedy algorithm for this problem. Our algorithm is completely distributed, and it assumes that agents have only local knowledge about tasks and resources. We conduct a broad set of experiments to evaluate the performance and scalability of the proposed algorithm in terms of solution quality and computation time. Three different types of networks, namely small-world, random and scale-free networks, are used to represent various social relationships among agents in realistic applications. The results demonstrate that our algorithm works well and also that it scales well to large-scale applications. In addition we consider the same problem in a setting where the agents holding the resources are self-interested. For this, we show how the optimal algorithm can be used to incentivize these agents to be truthful. However, the efficient greedy algorithm cannot be used in a truthful mechanism, therefore an alternative, cluster-based algorithm is proposed and evaluated.     

基于动态预测和任务流整形的网格调度算法

针对网格环境下计算节点的自治性、异构性、分布性等特征,提出一种基于任务响应时间的动态修正预测和任务流整形的网格调度算法,该调度方法依据历史数据和最近访问过计算节点的任务请求提交时间、任务完成时间、网络通信延迟等信息,预测计算节点的将来任务响应时间,将任务提交给预测的轻负载或性能较优的计算节点完成。通过使用动态修正算法和任务流整形算法降低预测误差,提高资源利用率。实验结果表明,该方法在任务响应时间、任务的吞吐率等方面优于随机调度等传统算法,具有较好的综合性能。     

Task allocation for maximizing reliability of distributed computing systems using honeybee mating optimization

This paper deals with the problem of task allocation (i.e., to which processor should each task of an application be assigned) in heterogeneous distributed computing systems with the goal of maximizing the system reliability. The problem of finding an optimal task allocation is known to be NP-hard in the strong sense. We propose a new swarm intelligence technique based on the honeybee mating optimization (HBMO) algorithm for this problem. The HBMO based approach combines the power of simulated annealing, genetic algorithms with a fast problem specific local search heuristic to find the best possible solution within a reasonable computation time. We study the performance of the algorithm over a wide range of parameters such as the number of tasks, the number of processors, the ratio of average communication time to average computation time, and task interaction density of applications. The effectiveness and efficiency of our algorithm are demonstrated by comparing it with recently proposed task allocation algorithms for maximizing system reliability available in the literature.     

Distributed Throughput Optimization for Large-Scale Scientific Workflows Under Fault-Tolerance Constraint

With the advent of next-generation scientific applications, the workflow approach that integrates various computing and networking technologies has provided a viable solution to managing and optimizing large-scale distributed data transfer, processing, and analysis. This paper investigates a problem of mapping distributed scientific workflows for maximum throughput in faulty networks where nodes and links are subject to probabilistic failures. We formulate this problem as a bi-objective optimization problem to maximize both throughput and reliability. By adapting and modifying a centralized fault-free workflow mapping scheme, we propose a new mapping algorithm to achieve high throughput for smooth data flow in a distributed manner while satisfying a pre-specified bound of the overall failure rate for a guaranteed level of reliability. The performance superiority of the proposed solution is illustrated by both extensive simulation-based comparisons with existing algorithms and experimental results from a real-life scientific workflow deployed in wide-area networks.     

Decentralized management of bi-modal network resources in a distributed stream processing platform

This paper presents resource management techniques for allocating communication and computational resources in a distributed stream processing platform. The platform is designed to exploit the synergy of two classes of network connections—dedicated and opportunistic. Previous studies we conducted have demonstrated the benefits of such bi-modal resource organization that combines small pools of dedicated computers with a very large pool of opportunistic computing capacities of idle computers to serve high throughput computing applications. This paper extends the idea of bi-modal resource organization into the management of communication resources. Since distributed stream processing applications demand large volume of data transmission between processing sites at a consistent rate, adequate control over the network resources is important to ensure a steady flow of processing. The system model used in this paper is a platform where stream processing servers at distributed sites are interconnected with a combination of dedicated and opportunistic communication links. Two pertinent resource allocation problems are analyzed in detail and solved using decentralized algorithms. One is mapping of the processing and the communication tasks of the stream processing workload on the processing and the communication resources of the platform. The other is the dynamic re-allocation of the communication links due to variations in the capacity of the opportunistic communication links. Overall optimization goal of the allocations is higher task throughput and better utilization of the expensive dedicated links without deviating much from the timely completion of the tasks. The algorithms are evaluated through extensive simulation with a model based on realistic observations. The results demonstrate that the algorithms are able to exploit the synergy of bi-modal communication links towards achieving the optimization goals.     

Precedence-constrained task allocation onto point-to-point networksfor pipelined execution

The problem of scheduling directed acyclic task flow graphs to multiprocessor systems using point-to-point networks is examined. An environment where the application has a strict throughput requirement is assumed. Pipelined parallelism is used to meet the throughput requirement. Communication and computation are completely overlapped. Each task and message has a periodic rate and deadline equal to the throughput requirement. A heuristic procedure based on preclustering, recursive mincut bipartitioning, and iterative improvement is proposed to reduce the maximum contention due to communication in the network, increasing the likelihood that messages meet their deadlines. The task assignment procedure takes into account the topology of the multiprocessor system and the distance between communicating tasks     

A Distributed Stream Query Optimization Framework through Integrated Planning and Deployment

This paper addresses the problem of optimizing multiple distributed stream queries that are executing simultaneously in distributed data stream systems. We argue that the static query optimization approach of "plan, then deployment” is inadequate for handling distributed queries involving multiple streams and node dynamics faced in distributed data stream systems and applications. Thus, the selection of an optimal execution plan in such dynamic and networked computing systems must consider operator ordering, reuse, network placement, and search space reduction. We propose to use hierarchical network partitions to exploit various opportunities for operator-level reuse while utilizing network characteristics to maintain a manageable search space during query planning and deployment. We develop top-down, bottom-up, and hybrid algorithms for exploiting operator-level reuse through hierarchical network partitions. Formal analysis is presented to establish the bounds on the search space and suboptimality of our algorithms. We have implemented our algorithms in the IFLOW [CHECK END OF SENTENCE] system, an adaptive distributed stream management system. Through simulations and experiments using a prototype deployed on Emulab [CHECK END OF SENTENCE], we demonstrate the effectiveness of our framework and our algorithms.     

An effective iterated greedy algorithm for reliability-oriented task allocation in distributed computing systems

This paper investigates the problem of allocating parallel application tasks to processors in heterogeneous distributed computing systems with the goal of maximizing the system reliability. The problem of finding an optimal task allocation for more than three processors is known to be NP-hard in the strong sense. To deal with this challenging problem, we propose a simple and effective iterative greedy algorithm to find the best possible solution within a reasonable amount of computation time. The algorithm first uses a constructive heuristic to obtain an initial assignment and iteratively improves it in a greedy way. We study the performance of the proposed algorithm over a wide range of parameters including problem size, the ratio of average communication time to average computation time, and task interaction density. The viability and effectiveness of our algorithm is demonstrated by comparing it with recently proposed task allocation algorithms for maximizing system reliability available in the literature.     

Game-theoretic static load balancing for distributed systems

In this paper, we present a game theoretic approach to solve the static load balancing problem for single-class and multi-class (multi-user) jobs in a distributed system where the computers are connected by a communication network. The objective of our approach is to provide fairness to all the jobs (in a single-class system) and the users of the jobs (in a multi-user system). To provide fairness to all the jobs in the system, we use a cooperative game to model the load balancing problem. Our solution is based on the Nash Bargaining Solution (NBS) which provides a Pareto optimal solution for the distributed system and is also a fair solution. An algorithm for computing the NBS is derived for the proposed cooperative load balancing game. To provide fairness to all the users in the system, the load balancing problem is formulated as a non-cooperative game among the users who try to minimize the expected response time of their own jobs. We use the concept of Nash equilibrium as the solution of our non-cooperative game and derive a distributed algorithm for computing it. Our schemes are compared with other existing schemes using simulations with various system loads and configurations. We show that our schemes perform near the system optimal schemes and are superior to the other schemes in terms of fairness.     

Active Robust Resource Management in Cluster Computing Using Policies

We present an implementation of a policy-based management architecture for emerging communications and computing paradigms such as Active Networks and the Grid. To manage such open, highly distributed and decentralized environments, an approach based on policy concepts is adopted, allowing support for active, dynamic adaptability in network elements, services and end-user applications, as well as achieving decentralization and distribution. We present our flexible, extensible policy and event specifications in XML, and describe our management architecture. One key feature of our approach is the distributed infrastructure: the Directory and the Management Information Distribution system. The second feature is the Resource and Security Management elements residing on the multi-node managed systems. These combine to provide a light-weight, self-organizing management architecture. As an applications example, we describe the implementation of our management system applied to the Application Level Active Networking (ALAN) environment, implemented in the European Commission Information Society Technologies (IST) project ANDROID.     

Content-aware optimization on rate-distortion and network traffic for scalable video multicast networks

This paper aims to optimize the content-aware prioritization of scalable video multicast, which is coupled with multipath streaming and network coding based routing. It constructs multiple layer distribution meshes for the scalable video stream to minimize the total video distortion at all the receivers, determines the base layer meshes with minimum costs to maintain application-layer QoS and the layer synchronization of SVC streaming, and improves the network throughput by encouraging path-overlapping transmissions and thus allowing bandwidth sharing among different receivers for the same video layer by utilizing network coding. The targeted problem is formulated into a minimization programming in which the quality variation between layers, the transmission cost of the base layer, as well as the efficient resource utilization are jointly considered. By decomposition and dual approach, the global convex problem is solved by a two-level decentralized iterative algorithm. The implementation of the distributed algorithm is discussed with regard to the communication overhead, and the convergence performance is validated by numerical experiments. Packet-level simulations demonstrate that the proposed algorithm could approximately achieve the maximum flow rates determined by Max-Flow Min-Cut Theorem and benefit the overall received video quality.