检索结果-内蒙古大学图书馆

international Symposium on parallel and distributed Processing (IPDPS)

作者： K. Kothapalli C. Scheideler M. Onus C. Schindelhauer Department of Computer Science Johns Hopkins University Baltimore MD USA Computer Science Department Technische Universität München Garching Germany Department of Computer Science Arizona State University Tempe AZ USA Heinz Nixdorf Institute and Computer Science Department University of Paderborn Paderborn Germany

We consider the well-known vertex coloring problem: given a graph G, find a coloring of the vertices so that no two neighbors in G have the same color. It is trivial to see that every graph of maximum degree Delta can be colored with Delta + 1 colors, and distributed algorithms that find a (Delta + 1)-coloring in a logarithmic number of communication rounds, with high probability, are known since more than a decade. This is in general the best possible if only a constant number of bits can be sent along every edge in each round. In fact, we show that for the n-node cycle the bit complexity of the coloring problem is Omega(log n). More precisely, if only one bit can be sent along each edge in a round, then every distributed coloring algorithm (i.e., algorithms in which every node has the same initial state and initially only knows its own edges) needs at least Omega(log n) rounds, with high probability, to color the cycle, for any finite number of colors. But what if the edges have orientations, i.e., the end-points of an edge agree on its orientation (while bits may still flow in both directions)? Does this allow one to provide faster coloring algorithms? Interestingly, for the cycle in which all edges have the same orientation, we show that a simple randomized algorithm can achieve a 3-coloring with only O(radic(log n)) rounds of bit transmissions, with high probability (w.h.p.). This result is tight because we also show that the bit complexity of coloring an oriented cycle is Omega(radic(log n)), with high probability, no matter how many colors are allowed. The 3-coloring algorithm can be easily extended to provide a (Delta + 1)-coloring for all graphs of maximum degree Delta in O(radic(log n)) rounds of bit transmissions, w.h.p., if Delta is a constant, the edges are oriented, and the graph does not contain an oriented cycle of length less than radic(log n). Using more complex algorithms, we show how to obtain an O(Delta)-coloring for arbitrary oriented graphs of

关键词： Computer science distributed computing distributed algorithms Wireless networks Contracts Large-scale systems Information systems Processor scheduling resource management Routing

来源：评论

学校读者我要写书评

暂无评论

A desired load distribution model for scheduling of unrelated parallel machines

引用

international JOURNAL OF PRODUCTION RESEARCH 2005年第23期43卷 5033-5046页

作者： Li, Y Shen, WM Ghenniwa, H Wang, C Natl Res Council Canada Integrated Mfg Technol Inst London ON Canada Univ Western Ontario Dept Elect & Comp Engn London ON Canada

scheduling problems concern the allocation of limited resources over time among both parallel and sequential activities. Load balancing has been adopted as an optimization criterion for several scheduling problems. However, in many practical situations, a load-balanced solution may not be feasible or attainable. To deal with this limitation, this paper presents a generic mathematical model of load distribution for resource allocation, called desired load distribution (DLD). The objective is to develop a DLD model for scheduling of unrelated parallel machines that can be used both in centralized resource management settings and in agent-based distributed scheduling systems. The paper describes the proposed DLD model in details, presents a dynamic programming based optimization algorithm for the proposed model, and then discusses its application to agent-based distributed scheduling.

关键词： scheduling unrelated parallel machines load balancing dynamic programming agent-based scheduling

来源：评论

学校读者我要写书评

暂无评论

DGMonitor: A performance monitoring tool for sandbox-based desktop grid platforms

引用

JOURNAL OF SUPERCOMPUTING 2005年第2期34卷 113-133页

作者： Cicotti, P Taufer, M Chien, AA Univ Calif San Diego Dept Comp Sci & Engn La Jolla CA 92093 USA Scripps Res Inst Dept Mol Biol La Jolla CA 92037 USA Univ Texas Dept Comp Sci El Paso TX 79968 USA

Accurate, continuous resource monitoring and profiling are critical for enabling performance tuning and scheduling optimization. In desktop grid systems that employ sandboxing, these issues are challenging because (1) subjobs inside sandboxes are executed in a virtual computing environment and (2) the state of this virtual environment within the sandboxes is reset to an initial empty state after a subjob completion. DGMonitor is a monitoring tool which builds a global, accurate, and continuous view of real resource utilization for desktop grids with sandboxing. Our monitoring tool measures performance unobtrusively and reliably, uses a simple performance data model, and is easy to use. Our measurements demonstrate that DGMonitor can scale to large desktop grids (up to 12000 PCs) with low monitoring overhead in terms of resource consumption (less than 0.1% per machine). Though we originally developed DGMonitor with the Entropia DCGrid platform, our tool is easily portable and integrated into other desktop grid systems. In all of these systems, DGMonitor data can support existing and novel information services, particularly for performance tuning and scheduling. In this paper, the high scalability and monitoring power of DGMonitor are demonstrated with the Entropia DCGrid platform and the BOINC platform respectively.

关键词： performance monitoring and profiling sandboxing techniques distributed computing

来源：评论

学校读者我要写书评

暂无评论

An investigation into the application of different performance prediction methods to distributed enterprise applications

引用

JOURNAL OF SUPERCOMPUTING 2005年第2期34卷 93-111页

作者： Bacigalupo, DA Jarvis, SA He, LG Spooner, DP Dillenberger, DN Nudd, GR Univ Warwick High Performance Syst Grp Coventry CV4 7AL W Midlands England IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA

Response time predictions for workload on new server architectures can enhance Service Level Agreement-based resource management. This paper evaluates two performance prediction methods using a distributed enterprise application benchmark. The historical method makes predictions by extrapolating from previously gathered performance data, while the layered queuing method makes predictions by solving layered queuing networks. The methods are evaluated in terms of: the systems that can be modelled;the metrics that can be predicted;the ease with which the models can be created and the level of expertise required;the overheads of recalibrating a model;and the delay when evaluating a prediction. The paper also investigates how a prediction-enhanced resource management algorithm can be tuned so as to compensate for predictive inaccuracy and balance the costs of SLA violations and server usage.

关键词： performance prediction distributed enterprise application layered queuing modelling historical performance data resource management service level agreement

来源：评论

学校读者我要写书评

暂无评论

DGMonitor: A performance monitoring tool for sandbox-based desktop grid platforms

DGMonitor: A performance monitoring tool for sandbox-based d...

引用

3rd international workshop on Performance Modelling, Evaluation, and Optimization of parallel and distributed systems held in Conjunction with the 18th international parallel and distributed Processing Symposium

ISBN: (纸本)0769521320

关键词： performance monitoring and profiling sandboxing techniques distributed computing

来源：评论

学校读者我要写书评

暂无评论

Co-scheduling with user-settable reservations

Co-scheduling with user-settable reservations

引用

11th international workshop Job scheduling Strategies for parallel Processing

作者： Yoshimoto, K Kovatch, P Andrews, P Univ Calif San Diego San Diego Supercomp Ctr La Jolla CA 92093 USA

ISBN: (纸本)354031024X

As grid computing becomes more commonplace, so does the importance of coscheduling these geographically distributed resources. Negotiating resource management and scheduling decisions for these resources is similar to making travel arrangements: guesses are made and then remade or confirmed depending on the availability of resources. This "Travel Agent Method" serves as the basis for a production scheduler and metascheduler suitable for making travel arrangements for a grid. This strategy is more easily implemented than centralized metascheduler because arrangements can be made without requiring control over the individual schedulers for each resource: the reservations are set by users or automatically by negotiating with each local scheduler's user settable interface. The Generic Universal Remote is a working implementation of such a system and proves that a user-settable reservation facility on local schedulers in a grid is sufficient to enable automated metascheduling.

关键词： Human computer interaction

来源：评论

学校读者我要写书评

暂无评论

Adaptive resource management in peer-to-peer middleware

Adaptive resource management in peer-to-peer middleware

引用

19th IEEE international parallel and distributed Processing Symposium, IPDPS 2005

作者： Repantis, Thomas Drougas, Yannis Kalogeraki, Vana Department of Computer Science and Engineering University of California Riverside Riverside CA 92521

ISBN: (纸本)0769523129

Supporting distributed real-time applications in large-scale and heterogeneous distributed environments has attracted much attention recently. However, the decentralized and dynamic characteristics of the systems present a number of challenges in managing the processor and networking resources and scheduling the application execution across multiple peers. In this paper, we address these problems with a novel resource management architecture for scheduling soft real-time applications in overlay networks. Key to our approach is that nodes maintain a partial view of resource availability of their peers in local profiles, keep track of the urgency of the requests and balance application execution across multiple nodes. Our techniques are entirely decentralized and use only local knowledge considering unpredictable latencies and changing resource availability.

关键词： Middleware

来源：评论

学校读者我要写书评

暂无评论

A model for usage policy-based resource allocation in grids

A model for usage policy-based resource allocation in grids

引用

6th IEEE international workshop on Policies for distributed systems and Networks

作者： Dumitrescu, CL Wilde, M Foster, I Univ Chicago Dept Comp Sci Chicago IL 60637 USA

ISBN: (纸本)0769522653

Challenging usage policy issues can arise within virtual organizations (VOs) that integrate participants and resources spanning multiple physical institutions. Participants may wish to delegate to one or more VOs the right to use certain resources subject to local policy and service level agreements;each VO then wishes to use those resources subject to VO policy. How are such local and VO policies to be expressed, discovered, interpreted, and enforced? As a first step to addressing these questions, we develop and evaluate policy management solutions within a specialized context, namely scientific data grids within which the resources to be shared are computers and storage. We propose an architecture and recursive policy model, and define roles and functions, for scheduling resources in grid environments while satisfying resource owner and VO policies.

关键词： distributed computer systems

来源：评论

学校读者我要写书评

暂无评论

Characterization of bandwidth-aware meta-schedulers for co-allocating jobs across multiple clusters

引用

JOURNAL OF SUPERCOMPUTING 2005年第2期34卷 135-163页

作者： Jones, WM Ligon, WB Pang, LW Stanzione, D Clemson Univ Dept Elect & Comp Engn Parallel Architecture Res Lab Clemson SC 29634 USA Arizona State Univ Fulton Sch Engn Ctr High Performance Comp Tempe AZ 85287 USA

In this paper, we present a bandwidth-centric job communication model that captures the interaction and impact of simultaneously co-allocating jobs across multiple clusters. We compare our dynamic model with previous research that utilizes a fixed execution time penalty for co-allocated jobs. We explore the interaction of simultaneously co-allocated jobs and the contention they often create in the network infrastructure of a dedicated computational multi-cluster. We also present several bandwidth-aware co-allocating meta-schedulers. These schedulers take inter-cluster network utilization into account as a means by which to mitigate degraded job run-time performance. We make use of a bandwidth-centric parallel job communication model that captures the time-varying utilization of shared inter-cluster network resources. By doing so, we are able to evaluate the performance of multi-cluster scheduling algorithms that focus not only on node resource allocation, but also on shared inter-cluster network bandwidth.

关键词： parallel job scheduling multiple clusters bandwidth-aware network contention job co-allocation multi-site scheduling simulation

来源：评论

学校读者我要写书评

暂无评论

Heterogeneous resource selection with portfolio optimization in grid

Heterogeneous resource selection with portfolio optimization...

引用

6th international Conference on parallel and distributed Computing, Applications and Technologies, PDCAT 2005

作者： Hua, Yu Wu, Chanle Zhang, Huyin Wu, Libing School of Computer Wuhan University Wuhan China

ISBN: (纸本)0769524052

The problem of resource management and scheduling has always been the main challenge in grid. Grid economy is looked on as a good solution for obtaining better performance than other methods for resource management in dynamic grid environments. But, the decision making about resources selection with portfolio optimization has been paid little attention to in grid economy. This paper introduced the concept and methods with portfolio optimization in grid economy. © 2005 IEEE.

关键词： resource allocation

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：