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

Efficient automatic simulation of parallel computation on networks of workstations

DISCRETE APPLIED MATHEMATICS 2006年第10期154卷 1500-1509页

作者： Kaklamanis, Christos Krizanc, Danny Montangero, Manuela Persiano, Giuseppe Univ Modena & Reggio Emilia Dipartimento Ingn Informaz I-41100 Modena Italy Univ Patras Inst Comp Technol GR-26500 Patras Greece Univ Patras Dept Comp Engn & Informat GR-26500 Patras Greece Wesleyan Univ Dept Math & Comp Sci Middletown CT 06459 USA Univ Salerno Dipartimento Informat & Applicaz I-84081 Baronissi Italy

Andrews et al. [Automatic method for hiding latency in high bandwidth networks, in: proceedings of the acm symposium on Theory of Computing, 1996, pp. 257-265;Improved methods for hiding latency in high bandwidth networks, in: proceedings of the Eighth annual acm symposium on parallel algorithms and architectures, 1996, pp. 52-61] introduced a number of techniques for automatically hiding latency when performing simulations of networks with unit delay links on networks with arbitrary unequal delay links. In their work, they assume that processors of the host network are identical in computational power to those of the guest network being simulated. They further assume that the links of the host are able to pipeline messages, i.e., they are able to deliver P packets in time O(P + d) where d is the delay on the link. In this paper we examine the effect of eliminating one or both of these assumptions. In particular, we provide an efficient simulation of a linear array of homogeneous processors connected by unit-delay links on a linear array of heterogeneous processors connected by links with arbitrary delay. We show that the slowdown achieved by our simulation is optimal. We then consider the case of simulating cliques by cliques;i.e., a clique of heterogeneous processors with arbitrary delay links is used to simulate a clique of homogeneous processors with unit delay links. We reduce the slowdown from the obvious bound of the maximum delay link to the average of the link delays. In the case of the linear array we consider both links with and without pipelining. For the clique simulation the links are not assumed to support pipelining. The main motivation of our results (as was the case with Andrews et al.) is to mitigate the degradation of performance when executing parallel programs designed for different architectures on a network of workstations (NOW). In such a setting it is unlikely that the links provided by the NOW will support pipelining and it is quite probab

关键词： parallel computation distributed computation automatic simulation

来源：评论

学校读者我要写书评

暂无评论

The FG programming environment: good and good for you 06

The FG programming environment: good and good for you

引用

proceedings of the eighteenth annual acm symposium on parallelism in algorithms and architectures

作者： Elena Riccio Davidson Dartmouth College

No abstract available.

ISBN: (纸本)9781595934529

No abstract available.

关键词： usability human factors parallel programming

来源：评论

学校读者我要写书评

暂无评论

An envolutionary path towards virtual shared memory with random access 06

An envolutionary path towards virtual shared memory with ran...

引用

proceedings of the eighteenth annual acm symposium on parallelism in algorithms and architectures

作者： Jonathan L. Brown Sue Goudy Mike Heroux Shan Shan Huang Zhaofang Wen Sandia National Laboratories Albuquerque NM

No abstract available.

ISBN: (纸本)9781595934529

No abstract available.

关键词： parallel programming programming models

来源：评论

学校读者我要写书评

暂无评论

Introducing the hydra parallel programming system 06

Introducing the hydra parallel programming system

引用

proceedings of the eighteenth annual acm symposium on parallelism in algorithms and architectures

作者： Franklin E. Powers Gita Alaghband University of Colorado at Denver and Health & Sciences Center Denver CO

ISBN: (纸本)9781595934529

Hydra PPS is a collection of annotations, classes, a runtime, and a compiler designed to provide Java programmers with a fairly simple method of producing programs for Symmetric Multiprocessing (SMP) architectures. This paper introduces the basics of this new system including the basic constructs for this new programming language and the relationship between the Java VM, the compiler, the runtime, and the parallel program. Hydra will exploit parallelism when the underlying architecture supports it and will run as normal sequential Java program when the architecture does not have support for parallelism. parallelism is expressed through events in Hydra, it is easy to use, and programs run efficiently on parallel architectures.

关键词：

来源：评论

学校读者我要写书评

暂无评论

On the price of heterogeneity in parallel systems 06

On the price of heterogeneity in parallel systems

引用

proceedings of the eighteenth annual acm symposium on parallelism in algorithms and architectures

作者： P. Brighten Godfrey Richard M. Karp UC Berkeley Berkeley CA

ISBN: (纸本)9781595934529

Suppose we have a parallel or distributed system whose nodes have limited capacities, such as processing speed, bandwidth, memory, or disk space. How does the performance of the system depend on the amount of heterogeneity of its capacity distribution? We propose a general framework to quantify the worst-case effect of increasing heterogeneity in models of parallel systems. Given a cost function g(C,W) representing the system's performance as a function of its nodes' capacities C and workload W (such as the completion time of an optimum schedule of jobs W on machines C), we say that g has price of heterogeneity α when for any workload, cost cannot increase by more than a factor α if node capacities become arbitrarily more heterogeneous. We give constant bounds on the price of heterogeneity of several well-known job scheduling and graph degree/diameter problems, indicating that increasing heterogeneity can never be much of a disadvantage. On the other hand, with the introduction of timing constraints such as release times or precedence constraints on the jobs, the dependence on node capacities becomes more complex, so that increasing heterogeneity may be quite detrimental.

关键词： majorization scheduling heterogeneity

来源：评论

学校读者我要写书评

暂无评论

An empirical study to compare two parallel programming models 06

An empirical study to compare two parallel programming model...

引用

proceedings of the eighteenth annual acm symposium on parallelism in algorithms and architectures

作者： Lorin Hochstein Victor R. Basili University of Maryland College Park MD

ISBN: (纸本)9781595934529

While there are strong beliefs within the community about whether one particular parallel programming model is easier to use than another, there has been little research to analyze these claims empirically. Currently, the most popular paradigm is message-passing, as implemented by the MPI library [1]. However, MPI is considered to be difficult for developing programs, because it forces the programmer to work at a very low level of abstraction. One alternative parallel programming model is the PRAM model, which supports fine-grained parallelism and has a substantial history of algorithmic theory [2]. It is not possible to program current parallel machines using the PRAM model because modern architectures are not designed to support such a model efficiently. However, current trends towards multicore chips suggest that large-scale, fine-grained uniform-memory access parallel machines may soon be feasible. XMT-C is an extension of the C language that supports parallel directives to provide a PRAM-like model to the programmer. A prototype compiler exists that generates code which runs on a simulator for an XMT architecture [3].To better understand how much benefit a PRAM-like model could provide over a message-passing model, we conducted a feasibility study in an academic setting to compare the effort required to solve a particular problem. The questions under study were: can we measure the effort in developing a program using these two programming models and can we differentiate the amount of effort for each model?.The subjects participating in the study were divided up into two groups. One group solved a problem using the MPI library in either C,C++, or Fortran, and the other group solved the problem using XMT-C. The task was to write a function to multiply a sparse matrix with a dense vector. To obtain subjects, we leveraged existing graduate-level parallel programming courses at two different universities: University of California, Santa Barbara (UCSB), and Universit

关键词： HPC message-passing PRAM XMT empirical study productivity effort parallel programming MPI

来源：评论

学校读者我要写书评

暂无评论

An implementation report for parallel triangular decompositions 06

An implementation report for parallel triangular decompositi...

引用

proceedings of the eighteenth annual acm symposium on parallelism in algorithms and architectures

作者： Marc Moreno Maza Yuzhen Xie University of Western Ontario (UWO) London Ontario Canada

ISBN: (纸本)9781595934529

Since the discovery of Gröbner bases, the algorithmic advances in Commutative Algebra have made possible to tackle many classical problems in Algebraic Geometry that were previously out of reach. However, algorithmic progress is still desirable, for instance when solving symbolically a large system of algebraic non-linear equations. For such a system, in particular if its solution set consists of geometric components of different dimension (points, curves, surfaces, etc) it is necessary to combine Gröbner bases with decomposition techniques, such as triangular decompositions. Ideally, one would like each of the different components to be produced by an independent processor, or set of processors. In practice, the input polynomial system, which is hiding those components, requires some transformations in order to split the computations into sub-systems and, then, lead to the desired components. The efficiency of this approach depends on its ability to detect and exploit geometrical information during the solving *** work addresses two questions: How to discover geometrical information, at an early stage of the solving process, that would be favorable to parallel execution? How to ensure load balancing among the processors? We answer these questions in the context of triangular decompositions [2] which are a popular way of solving polynomial systems symbolically. These methods tend to split the input polynomial system into subsystems and, therefore, are natural candidate for parallel implementation. However, the only such method which has been parallelized so far is the Characteristic Set Method of Wu [5], as reported in [1, 6]. This approach suffers from several limitations. For instance, the solving of the second component cannot start before that of the first one is completed; this is a limitation in view of coarse-grain *** [4] an algorithm, called Triade, for TRIAngular DEcompositions, provides a good management of the intermediate computat

关键词： parallel execution polynomial system solver

来源：评论

学校读者我要写书评

暂无评论

parallel depth first vs. work stealing schedulers on CMP architectures 06

Parallel depth first vs. work stealing schedulers on CMP arc...

引用

proceedings of the eighteenth annual acm symposium on parallelism in algorithms and architectures

作者： Vasileios Liaskovitis Shimin Chen Phillip B. Gibbons Anastassia Ailamaki Guy E. Blelloch Babak Falsafi Limor Fix Nikos Hardavellas Michael Kozuch Todd C. Mowry Chris Wilkerson Carnegie Mellon University Intel Research Pittsburgh Carnegie Mellon University and Intel Research Pittsburgh Intel Microprocessor Research Lab

ISBN: (纸本)9781595934529

In chip multiprocessors (CMPs), limiting the number of off-chip cache misses is crucial for good performance. Many multithreaded programs provide opportunities for constructive cache sharing, in which concurrently scheduled threads share a largely overlapping working set. In this brief announcement, we highlight our ongoing study [4] comparing the performance of two schedulers designed for fine-grained multithreaded programs: parallel Depth First (PDF) [2], which is designed for constructive sharing, and Work Stealing (WS) [3], which takes a more traditional *** of schedulers. In PDF, processing cores are allocated ready-to-execute program tasks such that higher scheduling priority is given to those tasks the sequential program would have executed earlier. As a result, PDF tends to co-schedule threads in a way that tracks the sequential execution. Hence, the aggregate working set is (provably) not much larger than the single thread working set [1]. In WS, each processing core maintains a local work queue of readyto-execute threads. Whenever its local queue is empty, the core steals a thread from the bottom of the first non-empty queue it finds. WS is an attractive scheduling policy because when there is plenty of parallelism, stealing is quite rare. However, WS is not designed for constructive cache sharing, because the cores tend to have disjoint working *** configurations studied. We evaluated the performance of PDF and WS across a range of simulated CMP configurations. We focused on designs that have fixed-size private L1 caches and a shared L2 cache on chip. For a fixed die size (240 mm2), we varied the number of cores from 1 to 32. For a given number of cores, we used a (default) configuration based on current CMPs and realistic projections of future CMPs, as process technologies decrease from 90nm to *** of findings. We studied a variety of benchmark programs to show the following *** several application classes, PDF enable

关键词： scheduling chip multiprocessors caches

来源：评论

学校读者我要写书评

暂无评论

SPAA 2005 - Seventeenth annual acm symposium on parallelism in algorithms and architectures

SPAA 2005 - Seventeenth Annual ACM Symposium on Parallelism ...

引用

Seventeenth annual acm symposium on parallelism in algorithms and architectures

The proceedings contain 39 papers. The topics discussed include: randomized queue management for DiffServ;randomization does not reduce the average delay in parallel packet switches;dynamic circular work-stealing deque;coloring unstructured radio networks;name independent routing for growth bounded networks;windows scheduling of arbitrary length jobs on parallel machines;parallel scheduling of complex dags under uncertainty;on distributed smooth scheduling;scheduling malleable tasks with precedence constraints;an adaptive power conservation scheme for heterogeneous wireless sensor networks with node redeployment;irrigating ad hoc networks ion constant time;and constant density spanners for wireless ad-hoc networks.

关键词： Computer architecture

来源：评论

学校读者我要写书评

暂无评论

On competitive online read-many parallel disks scheduling 05

On competitive online read-many parallel disks scheduling

引用

proceedings of the seventeenth annual acm symposium on parallelism in algorithms and architectures

作者： Rahul Shah Peter J. Varman Jeffrey Scott Vitter Purdue University West Lafayette IN Rice University Houston TX Purdue University West Lafayatte IN

ISBN: (纸本)9781581139860

We consider the natural extension of the single disk caching problem to parallel disk I/O model. We close the existing gap between lower and upper bounds and achieve optimal competitive ratio of O(√D) when lookahead is more than the memory size M. When lookahead is smaller, we derive various upper bounds and lower bounds on the competitive ratio under various adversarial models.

关键词： online algorithms parallel disk model

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：