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

13th annual symposium on parallel algorithms and architectures (SPAA 2001)

作者： Gibbons, P.B. Tirthapura, S. Information Sciences Research Center Bell Laboratories Murray Hill NJ 07974 United States

ISBN: (纸本)9781581134094

Massive data sets often arise as physically distributed, parallel data streams. We present algorithms for estimating simple functions on the union of such data streams, while using only logarithmic space per stream. Each processor observes only its own stream, and communicates with the other processors only after observing its entire stream. This models the set-up in current network monitoring products. Our algorithms employ a novel coordinated sampling technique to extract a sample of the union;this sample can be used to estimate aggregate functions on the union. The technique can also be used to estimate aggregate functions over the distinct "labels" in one or more data streams, e.g., to determine the zeroth frequency moment (i.e., the number of distinct labels) in one or more data streams. Our space and time bounds are the best known for these problems, and our logarithmic space bounds for coordinated sampling contrast with polynomial lower bounds for independent sampling. We relate our dis tributed streams model to previously studied non-distributed (i.e., merged) streams models, presenting tight bounds on the gap between the distributed and merged models for deterministic algorithms.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

New spectral bounds on k-partitioning of graphs

New spectral bounds on k-partitioning of graphs

引用

13th annual symposium on parallel algorithms and architectures (SPAA 2001)

作者： Elsässer, R. Lücking, T. Monien, B. University of Paderborn Fürstenallee 11 33102 Paderborn Germany

When executing processes on parallel computer systems they encounter as a major bottleneck inter-processor communication. One way to address this problem is to minimize the communication between processes that are mapped to different processors. This translates to the k-partitioning problem of the corresponding process graph, where k is the number of processors. The classical spectral lower bound of |v|2k 4∑ ik=1 λ for the k-section width of a graph is well-known. We show new relations between the structure and the eigenvalues of a graph and present a new method to get tighter lower bounds on the k-section width. This method makes use of the level structure defined by the k-section. We define some global expansion property and prove that for graphs with the same k-section width the spectral lower bound increases with this global expansion. We also present examples of graphs for which our new bounds are tight up to a constant factor.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

Low-contention depth-first scheduling of parallel computations with write-once synchronization variables 01

Low-contention depth-first scheduling of parallel computatio...

引用

13th annual symposium on parallel algorithms and architectures (SPAA 2001)

作者： Fatourou, P. Department of Computer Science University of Toronto Toronto Ont. Canada

ISBN: (纸本)9781581134094

We present an efficient, randomized, online, scheduling algorithm for a large class of programs with write-once synchronization variables. The algorithm combines the work-stealing paradigm with the depth-first scheduling technique, resulting in high space efficiency and good time complexity. By automatically increasing the granularity of the work scheduled on each processor, our algorithm achieves good locality, low contention and low scheduling overhead, improving upon a previous depth-first scheduling algorithm [6] published in SPAA'97. Moreover, it is provably efficient for the general class of multithreaded computations with write-once synchronization variables (as studied in [6]), improving upon algorithm DFDeques (published in SPAA'99 [24]), which is only for the more restricted class of nested parallel computations. More specifically, consider such a computation with work T1, depth T∞ and σ synchronization, and suppose that space S1 suffices to execute the computation on a single-processor computer. Then, on a P-processor shared-memory parallel machine, the expected space complexity of our algorithm is at most S1 + O(PT∞ log(PT∞)), and its expected time complexity is O(T1/P+σlog(PT∞)/P+T∞ log(PT∞)). Moreover, for any Ε > 0, the space complexity of our algorithm is S1 + O(P(T∞ + ln(1/Ε))log(P(T∞ + ln(P(T∞ + ln(1/Ε))/Ε)))) with probability at least 1 - Ε. Thus, even for values of Ε as small as e -T∞, the space complexity of our algorithm is at most S1 + O(PT∞ log(PT∞)) with probability at least 1 - e-T∞. These bounds include all time and space costs for both the computation and the scheduler.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

Scheduling best-effort and real-time pipelined applications on time-shared clusters 01

Scheduling best-effort and real-time pipelined applications ...

引用

13th annual symposium on parallel algorithms and architectures (SPAA 2001)

作者： Zhang, Y. Sivasubramaniam, A. Dept. of Computer Sci./Engineering Pennsylvania State University University Park PA 16802 United States

ISBN: (纸本)9781581134094

Two important emerging trends are influencing the design, implementation and deployment of high performance parallel systems. The first is on the architectural end, where both economic and technological factors are compelling the use of off-the-shelf computing elements (workstations/PCs and networks) to put together high performance systems called clusters. The second is from the user community that is finding an increasing number of applications to benefit from such high performance systems. Apart from the scientific applications that have traditionally needed supercomputing power, a large number of graphics, visualization, database, web service and e-commerce applications have started using clusters because of their high processing and storage requirements. These applications have diverse characteristics and can place different Quality-of-Service (QoS) requirements on the underlying system (low response time, high throughput, high I/O demands, guaranteed response/throughput etc.). Further, clusters run ning such applications need to cater to potentially a large number of users (or other applications) in a time-shared manner. The underlying system needs to accommodate the requirements of each application, while ensuring that they do not interfere with each other. This paper focuses on the CPU resources of a cluster and investigates scheduling mechanisms to meet the responsiveness, throughput and guaranteed service requirements of different applications. Specifically, we propose and evaluate three different scheduling mechanisms. These mechanisms have been drawn from traditional solutions on parallel systems (gang scheduling and dynamic coscheduling), and have been extended to accommodate the new criteria under consideration. These mechanisms have been investigated using detailed simulation and workload models to show their pros and cons for different performance metrics.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

Improved fast integer sorting in linear space

引用

INFORMATION AND COMPUTATION 2001年第1期170卷 81-94页

作者： Han, Y Univ Missouri Comp Sci Telecommun Program Kansas City MO 64110 USA

We present a fast deterministic algorithm for integer sorting in linear space. Our algorithm sorts n integers in the range {0, 1, 2...., m-1} in linear space in O(n log log n log log log n) time. When log m greater than or equal to log(2+epsilon) n, epsilon > 0, we can further achieve O(n log log n) time. This improves the O(n(log log n)(2)) time bound given in M. Thorup (1998) in "Proc, 1998 acm-SIAM Symp. on Discrete algorithms (SODA'98)," pp. 550-555). This result is obtained by combining our new technique with that of Thorup's. Signature sorting (A. Andersson, T. Hagerup, S. Nilsson, and R. Raman, 1995, in "Proc. 1995 symposium on Theory of Computing," pp. 427-436), A. Andersson's result (1996, in "Proc. 1996 IEEE Symp. on Foundations of Computer Science" pp. 135-141), R. Raman's result (1996, Lecture Notes in Computer Science, Vol. 1136, pp. 121-137, Springer-Verlag Berlin/New York), and our previous result (Y. Han and X. Shen, 1999, in "Proc. 1999 Tenth annual acm-SIAM symposium on Discrete algorithms (SODA:99)," Baltimore, MD, January, pp. 419-428) are also used for the design of our algorithms. We provide an approach and techniques which are totally different from previous approaches and techniques for the problem. As a consequence our technique can he extended to apply to nonconservative sorting and parallel sorting. Our nonconservative sorting algorithm sorts a integers in {0, 1,..., m-1} in time O(n(log log n)(2)/(log k + log log log n)) using word length k log(m + n), where k < log n. Our EREW parallel algorithm sorts n integers in {0 1,...,m-1} in O((log n)(2)) time and O(n(log log n)(2)) log log log n) operations provided log m Omega((log n)(2)). (C) 2001 Academic Press.

关键词： algorithms bucket sorting integer sorting linear space parallel sorting

来源：评论

学校读者我要写书评

暂无评论

Statistical scalability analysis of communication operations in distributed applications 01

Statistical scalability analysis of communication operations...

引用

8th acm SIGPLAN symposium on the Principles and Practice of parallel Computing

作者： Vetter, JS McCracken, MO Lawrence Livermore Natl Lab Ctr Appl Sci Comp Livermore CA 94551 USA

ISBN: (纸本)9781581133462

Current trends in high performance computing suggest that users will soon have widespread access to clusters of multiprocessors with hundreds, if not thousands, of processors. This unprecedented degree of parallelism will undoubtedly expose scalability limitations in existing applications, where scalability is the ability of a parallel algorithm on a parallel architecture to effectively utilize an increasing number of processors. Users will need precise and automated techniques for detecting the cause of limited scalability. This paper addresses this dilemma. First, we argue that users face numerous challenges in understanding application scalability: managing substantial amounts of experiment data, extracting useful trends from this data, and reconciling performance information with their application's design. Second, we propose a solution to automate this data analysis problem by applying fundamental statistical techniques to scalability experiment data. Finally, we evaluate our operational prototype on several applications, and show that statistical techniques offer an effective strategy for assessing application scalability. In particular, we find that non-parametric correlation of the number of tasks to the ratio of the time for communication operations to overall communication time provides a reliable measure for identifying communication operations that scale poorly.

关键词： Scalability Experimental data statistical techniques Consumers Communication Research Automated recording parallel architectures Surgery Multiprocessor High Performance Computing parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Scheduling precedence-constrained jobs with stochastic processing times on parallel machines

Scheduling precedence-constrained jobs with stochastic proce...

引用

2001 Operating Section Proceedings, American Gas Association

作者： Skutella, Martin Uetz, Marc Technische Universität Berlin Fachbereich Mathematik Sekr. MA 6-1 Straße des 17 Juni 136 10623 Berlin Germany

ISBN: (纸本)0898714907

We consider parallel machine scheduling problems where the jobs are subject to precedence constraints, and the processing times of jobs are governed by independent probability distributions. The objective is to minimize the weighted sum of job completion times σ, w, C, in expectation, where w, 0. Building upon an LP-relaxation from [3] and an idle time charging scheme from [1], we derive the first approximation algorithms for this model. Copyright © 2009 acm, Inc.

关键词： algorithms Theory Verification

来源：评论

学校读者我要写书评

暂无评论

XtremWeb:: A generic Global Computing system

XtremWeb:: A generic Global Computing system

引用

1st IEEE/AMC International symposium on Cluster Computing and the Grid

作者： Fedak, G Germain, C Néri, V Cappello, F Univ Paris 11 Rech Informat Lab Orsay France

ISBN: (纸本)0769510116

Global Computing achieves high throughput computing by harvesting a very large number of unused computing resources connected to the Internet. This parallel computing model targets a parallel architecture defined by a very high number of nodes, poor communication performance and continuously varying resources. The unprecedented scale of the Global Computing architecture paradigm requires to revisit many, basic issues related to parallel architecture : programming models, performance models, and class of applications or algorithms suitable to this architecture, XtremWeb is an experimental Global Computing platform dedicated to provide a tool for such studies. This paper presents the design of XtremWeb. Two essential features of this design are multi-applications and high-performance. Accepting multiple applications allows institutions or enterprises to setup their own Global Computing applications or experiments. High-performance is ensured by scalability, fault tolerance, efficient scheduling and a large base of volunteer PCs. We also present an implementation of the first global application running on XtremWeb.

关键词： parallel architectures

来源：评论

学校读者我要写书评

暂无评论

Reconciling simplicity and realism in parallel disk models

Reconciling simplicity and realism in parallel disk models

引用

2001 Operating Section Proceedings, American Gas Association

作者： Sanders, Peter Max Planck Institut für Informatik Saarbrücken Germany

ISBN: (纸本)0898714907

For the design and analysis of algorithms that process huge data sets, a machine model is needed that handles parallel disks. There seems to be a dilemma between simple and flexible use of such a model and accurate modelling of details of the hardware. This paper explains how many aspects of this problem can be resolved. The programming model implements one large logical disk allowing concurrent access to arbitrary sets of variable size blocks. This model can be implemented efficienctly on multiple independent disks even if zones with different speed, communication bottlenecks and failed disks are allowed. These results not only provide useful algorithmic tools but also imply a theoretical justification for studying external memory algorithms using simple abstract models. The algorithmic approach is random redundant placement of data and optimal scheduling of accesses. The analysis generalizes a previous analysis for simple abstract external memory models in several ways (Higher efficiency, variable block sizes, more detailed disk model). As a side effect, an apparently new Chernoff bound for sums of weighted 0-1 random variables is derived. Copyright © 2009 acm, Inc.

关键词： algorithms Experimentation Management Measurement Performance Theory Verification

来源：评论

学校读者我要写书评

暂无评论

parallel processor scheduling with delay constraints

Parallel processor scheduling with delay constraints

引用

2001 Operating Section Proceedings, American Gas Association

作者： Engels, Daniel W. Feldman, Jon Karger, David R. Ruhl, Matthias MIT Laboratory for Computer Science Cambridge MA

ISBN: (纸本)0898714907

We consider the problem of scheduling unit-length jobs on identical parallel machines such that the makespan of the resulting schedule is minimized. Precedence constraints impose a partial order on the jobs, and both communication and precedence delays impose relative timing constraints on dependent jobs. The combination of these two types of timing constraints naturally models the instruction scheduling problem that occurs during software compilation for state-of-the-art VLIW (Very Long Instruction Word) processors and multiprocessor parallel machines. We present the first known polynomial-time algorithm for the case where the precedence constraint graph is a forest of in-trees (or a forest of out-trees), the number of machines m is fixed, and the delays (which are a function of both the job pair and the machines on which they run) are bounded by a constant D. Our algorithm relies on a new structural theorem for scheduling jobs with arbitrary precedence constraints. Given an instance with many independent dags, the theorem shows how to convert, in linear time, a schedule S for only the largest dags into a complete schedule that is either optimal or has the same makespan as S. Copyright © 2009 acm, Inc.

关键词： algorithms Reliability Theory Verification

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：