The 15 th HIPS workshop, to be held as a full-day meeting at the IPDPS 2010 conference in Atlanta, focuses on high-level programming of multiprocessors, compute clusters, and massively parallel machines. Like previou...
详细信息
The 15 th HIPS workshop, to be held as a full-day meeting at the IPDPS 2010 conference in Atlanta, focuses on high-level programming of multiprocessors, compute clusters, and massively parallel machines. Like previous workshops in the series, which was established in 1996, this event serves as a forum for researchers in the areas of parallel applications, language design, compilers, runtime systems, and programming tools.
The influence of on-chip metal interconnections, power grids, heat sink together with packaging, and metal dummy fills on the transmission characteristics of a 2mm-long integrated dipole antenna pair has been investig...
详细信息
This paper investigates scheduling loosely coupled task-bundles in highly heterogeneous distributed systems. Two allocation quality metrics are used in pay-per-service distributed applications: efficiency in terms of ...
详细信息
ISBN:
(纸本)9781424464425
This paper investigates scheduling loosely coupled task-bundles in highly heterogeneous distributed systems. Two allocation quality metrics are used in pay-per-service distributed applications: efficiency in terms of social welfare, and fairness in terms of envy-freeness. The first contribution of this work is that we build a unified hypergraph scheduling model under which efficiency and fairness are compatible with each other. Second, in the scenario of budget-unawareness, we formulate a strategic algorithm design for distributed negotiations among autonomous self-interested computing peers and prove its convergence to complete local efficiency and envy-freeness. third, we add budget limitation to the allocation problem and propose a class of hill-climbing heuristics in favor of different performance metrics. Finally we conduct extensive simulations to validate the performance of all the proposed algorithms. The results show that the decentralized hypergraph scheduling method is scalable, and yields desired allocation performance in various scenarios.
We investigate the problem of maintaining a topology with small degree as well as small diameter in a dynamic distributed system such that the system always stays connected and processes that wish to leave the system ...
详细信息
ISBN:
(纸本)9781424464425
We investigate the problem of maintaining a topology with small degree as well as small diameter in a dynamic distributed system such that the system always stays connected and processes that wish to leave the system can do so quickly. Perpetual system connectivity is necessary to solve many important problems in dynamic distributed systems, including atomic broadcast and stable property detection, that need strict (deterministic) guarantees about system connectivity to be solvable. To our knowledge, in all existing topology maintenance algorithms for asynchronous distributed systems that provide perpetual system connectivity, either: (i) the topology has large worst-case degree and/or diameter (ii) a process may experience high worst-case delay when leaving the system, or (iii) processes cannot join and/or leave concurrently. In this paper, we present a spanning tree maintenance algorithm that satisfies the following desirable properties. First, the spanning tree has small maximum degree of O(1) and small maximum diameter of O(log N), where N denotes the maximum size of the system. Second, any process can leave the system within O(log N) time even in the presence of concurrent arrivals and departures. third, the system always stays connected. We show using a simple knowledge-based argument that, in any algorithm that maintains perpetual connectivity such that the topology has either worst-case diameter of ¿(log N) or worst-case degree of O(1), the departure of a process may be delayed by ¿(log log N) time in the worst-case.
The proceedings contain 461 papers. The topics discussed include: how to make discretionary access control secure against trojan horses;random number generation for serial, parallel, distributed, and grid-based financ...
详细信息
ISBN:
(纸本)9781424416943
The proceedings contain 461 papers. The topics discussed include: how to make discretionary access control secure against trojan horses;random number generation for serial, parallel, distributed, and grid-based financial computations;mobility control schemes with quick convergence in wireless sensor networks;design and implementation of a tool for modeling and programming deadlock free meta-pipeline applications;analytic performance models for bounded queuing systems;on the construction of paired many-to-many disjoint path covers in hypercube-like interconnection networks with faulty elements;a scalable configurable architecture for the massively parallel GCA model;state management for distributed python applications;a fault-tolerant system for Java/CORBA objects;and improving data availability for a cluster file system through replication.
SRAM (static random access memory)-based pipelined algorithmic solutions have become competitive alternatives to TCAMs (ternary content addressable memories) for high-throughput IP lookup. Multiple pipelines can be ut...
详细信息
SRAM (static random access memory)-based pipelined algorithmic solutions have become competitive alternatives to TCAMs (ternary content addressable memories) for high-throughput IP lookup. Multiple pipelines can be utilized in parallel to improve the throughput further. However, several challenges must be addressed to make such solutions feasible. First, the memory distribution over different pipelines, as well as across different stages of each pipeline, must be balanced. Second, the traffic among these pipelines should be balanced. third, the intra-flow packet order (i.e. the sequence) must be preserved. In this paper, we propose a parallel SRAM-based multi-pipeline architecture for IP lookup. A two-level mapping scheme is developed to balance the memory requirement among the pipelines as well as across the stages in each pipeline. To balance the traffic, we propose an early caching scheme to exploit the data locality inherent in the architecture. Our technique uses neither a large reorder buffer nor complex reorder logic. Instead, a flow-aware queuing scheme exploiting the flow information is used to maintain the intra-flow sequence. Extensive simulation using real-life traffic traces shows that the proposed architecture with 8 pipelines can achieve a throughput of up to 10 billion packets per second, i.e. 3.2 Tbps for minimum size (40 bytes) packets, while preserving intra-flow packet order. (c) 2009 Elsevier Inc. All rights reserved.
暂无评论