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

QR FACTORIZATION OF A DENSE MATRIX ON A shared-memory multiprocessor

PARALLEL COMPUTING 1989年第1期11卷 55-71页

作者： CHU, E GEORGE, A OAK RIDGE NATL LAB MATH SCI SECTOAK RIDGETN 37831 UNIV TENNESSEE DEPT COMP SCIKNOXVILLETN 37996 UNIV TENNESSEE DEPT MATHKNOXVILLETN 37996

A new algorithm for computing an orthogonal decomposition of a rectangular m × n matrix A on a shared-memory parallel computer is described. The algorithm uses Givens rotations, and has the feature that its synchronization cost is low. In particular, for a multiprocessor having p processors, an analysis of the algorithm shows that this cost is O( n 2 / p ) if m/p ⪰ n , and O( mn / p 2 ) of m / p <. Note that in the latter case, the synchronization cost is smaller than O( n 2 / p ). Therefore, the synchronization cost of the algorithm proposed in this article is bounded by O( n 2 / p ) when m ⪰ n . This is important for machines where synchronization cost is high, and when m ⪢ n . Analysis and experiments show that the algorithm is effective in balancing the load and producing high efficiency (speedup).

关键词： Givens rotations numerical experiments Parallel linear algebra performance analysis QR factorization shared-memory multiprocessor

来源：评论

学校读者我要写书评

暂无评论

DYNAMIC-PROGRAMMING ON A shared-memory multiprocessor

引用

PARALLEL COMPUTING 1993年第1期19卷 9-22页

作者： EDMONDS, P CHU, E GEORGE, A UNIV WATERLOO DEPT COMP SCIWATERLOO N2L 3G1ONTARIOCANADA UNIV GUELPH DEPT MATH & STATGUELPH N1G 2W1ONTARIOCANADA UNIV GUELPH DEPT COMP & INFORMAT SCIGUELPH N1G 2W1ONTARIOCANADA UNIV TORONTO DEPT COMP SCITORONTO M5S 1A1ONTARIOCANADA

Three new algorithms for solving dynamic programming problems on a shared-memory parallel computer are described. All three algorithms attempt to balance work load, while keeping synchronization cost low. In particular, for a multiprocessor having p processors, an analysis of the best algorithm shows that the arithmetic cost is O(n3/6p) and that the synchronization cost is O(\log(C) n\) if p much less than n, where C = (2p - 1)/(2p + 1) and n is the size of the problem. The low synchronization cost is important for machines where synchronization is expensive. Analysis and experiments show that the best algorithm is effective in balancing the work load and producing high efficiency.

关键词： DYNAMIC PROGRAMMING shared-memory multiprocessor PERFORMANCE EVALUATION NUMERICAL EXPERIMENTS

来源：评论

学校读者我要写书评

暂无评论

HIGH-DIMENSIONAL HOMOTOPY CURVE TRACKING ON A shared-memory multiprocessor

引用

JOURNAL OF SUPERCOMPUTING 1992年第4期5卷 347-366页

作者： ALLISON, DCS IRANI, KM RIBBENS, CJ WATSON, LT 1. Department of Computer Science Virginia Polytechnic Institute & State University 24061-0106 Blacksburg VA USA

Results are reported for a series of experiments involving numerical curve tracking on a shared-memory parallel computer. Several algorithms exist for finding zeros or fixed points of nonlinear systems of equations that are globally convergent for almost all starting points, that is, with probability one. The essence of all such algorithms is the construction of an appropriate homotopy map and then the tracking of some smooth curve in the zero set of this homotopy map. HOMPACK is a mathematical software package implementing globally, convergent homotopy algorithms with three different techniques for tracking a homotopy zero curve, and has separate routines for dense and sparse Jacobian matrices. The HOMPACK algorithms for sparse Jacobian matrices use a preconditioned conjugate gradient algorithm for the computation of the kernel of the homotopy Jacobian matrix. a required linear algebra step for homotopy curve tracking. A parallel version of HOMPACK is implemented on a shared-memory parallel computer with various levels and degrees of parallelism (e.g.. linear algebra, function, and Jacobian matrix evaluation), and a detailed study is presented for each of these levels with respect to the speedup in execution time obtained with the parallelism, the time spent implementing the parallel code, and the extra memory allocated by the parallel algorithm.

关键词： NONLINEAR EQUATIONS HOMOTOPY ALGORITHM CURVE TRACKING shared-memory multiprocessor GLOBALLY CONVERGENT

来源：评论

学校读者我要写书评

暂无评论

Parallel processing of incremental ray tracing on a shared-memory multiprocessor

引用

The Visual Computer 1993年第7期9卷 371-380页

作者： Horiguchi, Susumu Katahira, Masayuki Nakada, Takeo Department of Information System Graduate School of Information Science Ishikawa 923-12 Jaist Tatsunokuchi Japan Department of Information Science Tohoku University Japan IBM Research Tokyo Research Laboratory Tokyo Japan

This paper presents a novel parallel-processing method for image synthesis using incremental ray tracing on a shared-memory multiprocessor workstation. The most efficient technique for image synthesis is ray tracing, proposed by Whitted in 1980. Ray-tracing algorithms are simple and can generate realistic images. However, they are time-consuming, since calculations of the intersections between objects and ray increase exponentially as the complexity of scenes increases. Fast image synthesis for animation is one of the most important topics in computer graphics. As the area of computer applications has broadened, the complexity of images to be synthesized has increased. Parallel processing of computer graphics is one way of achieving fast image synthesis. This paper describes a parallel processing technique for incremental ray tracing, which recalculates only the rays changed by moving objects in successive scenes of continuous image synthesis. The performance of parallel ray tracing was evaluated on the multiprocessor workstation TOP-1. Strategies for allocating pixels to processes under a multiprocess operating system on this workstation are discussed. © 1993 Springer-Verlag.

关键词： Incremental ray tracing Parallel processing shared-memory multiprocessor

来源：评论

学校读者我要写书评

暂无评论

A performance study of cache coherence protocols and write coaches for parallel-multithreaded shared-memory multiprocessors

引用

JOURNAL OF THE CHINESE INSTITUTE OF ENGINEERS 1998年第1期21卷 33-46页

作者： Wu, CC Chen, C Natl Chiao Tung Univ Dept Comp Sci & Informat Engn Hsinchu 300 Taiwan

According to published research results, no directory-based cache coherence protocol provides best performance for all application programs in conventional multiprocessor systems that use sequential consistency models. However, recently it has been claimed that competitive-update protocols are superior to other protocols under a relaxed consistency model. Moreover, incorporating write caches improves the system performance of clean and competitive-update protocols. In this paper, we examine the different effects that occur when processing elements are replaced by parallel-multithreaded processors. According to our simulation results, the clean protocol provided the best performance for five out of six SPLASH programs. After augmentation with write caches, the clean protocol outperformed others for all applications. Though competitive-update protocols have been improved, their performance is not better than that of write-invalidate protocols for most programs.

关键词： write cache multithreaded processor shared-memory multiprocessor cache coherence protocol

来源：评论

学校读者我要写书评

暂无评论

A high-performance MPI implementation on a shared-memory vector supercomputer

引用

PARALLEL COMPUTING 1997年第11期22卷 1513-1526页

作者： Gropp, W Lusk, E ARGONNE NATL LAB DIV MATH & COMP SCI ARGONNE IL 60439 USA

In this article we recount the sequence of steps by which MPICH, a high-performance, portable implementation of the Message-Passing Interface (MPI) standard, was ported to the NEC SX-4, a high-performance parallel supercomputer. Each step in the sequence raised issues that are important for shared-memory programming in general and shed light on both MPICH and the SX-4. The result is a low-latency, very high bandwidth implementation of MPI for the NEC SX-4, In the process, MPICH was also improved in several general ways.

关键词： Message-Passing Interface shared-memory multiprocessor NEC SX-4 MPICH performance implementation

来源：评论

学校读者我要写书评

暂无评论

A UNIFIED FORMALIZATION OF 4 shared-memory MODELS

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1993年第6期4卷 613-624页

作者： ADVE, SV Department of Computer Sciences University of Wisconsin Madison WI USA

This paper presents a shared-memory model, data-race-free-1, that unifies four earlier models: weak ordering, release consistency (with sequentially consistent special operations), the VAX memory model, and data-race-free-0. The most intuitive and commonly assumed shared-memory model, sequential consistency, limits performance. The models of weak ordering, release consistency, the VAX, and data-race-free-0 are based on the common intuition that if programs synchronize explicitly and correctly, then sequential consistency can be guaranteed with high performance. However, each model formalizes this intuition differently and has different advantages and disadvantages with respect to the other models. Data-race-free-1 unifies the models of weak ordering, release consistency, the VAX, and data-race-free-0 by formalizing the above intuition in a manner that retains the advantages of each of the four models. A multiprocessor is data-race-free-1 if it guarantees sequential consistency to data-race-free programs. Data-race-free-1 unifies the four models by providing a programmer's interface similar to the four models, and by allowing all implementations allowed by the four models. Additionally, data-race-free-1 expresses the programmer's interface more explicitly and formally than weak ordering and the VAX, and allows an implementation not allowed by weak ordering, release consistency, or data-race-free-0. The new implementation proposal for data-race-free-1 differs from earlier implementations mainly by permitting the execution of all synchronization operations of a processor even while previous data operations of the processor are in progress. To ensure sequential consistency, two synchronizing processors exchange information to delay later operations of the second processor that conflict with an incomplete data operation of the first processor.

关键词： DATA-RACE-FREE-0 DATA-RACE-FREE-1 memory MODEL RELEASE CONSISTENCY SEQUENTIAL CONSISTENCY shared-memory multiprocessor WEAK ORDERING

来源：评论

学校读者我要写书评

暂无评论

Data partitioning-based parallel irregular reductions

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2004年第2-3期16卷 155-172页

作者： Gutiérrez, E Plata, O Zapata, EL Univ Malaga Dept Comp Architecture E-29071 Malaga Spain

Different parallelization methods for irregular reductions on shared memory multiprocessors have been proposed in the literature in recent years. We have classified all these methods and analyzed them in terms of a set of properties: data locality, memory overhead, exploited parallelism, and workload balancing. In this paper we propose several techniques to increase the amount of exploited parallelism and to introduce load balancing into an important class of these methods. Regarding parallelism, the proposed solution is based on the partial expansion of the reduction array. Load balancing is discussed in terms of two techniques. The first technique is a generic one, as it deals with any kind of load imbalance present in the problem domain. The second technique handles a special case of load imbalance which occurs whenever a large number of write operations are concentrated on small regions of the reduction arrays. Efficient implementations of the proposed optimizing solutions for a particular method are presented, experimentally tested on static and dynamic kernel codes, and compared with other parallel reduction methods. Copyright (C) 2004 John Wiley Sons, Ltd.

关键词： irregular reductions data locality workload balancing shared-memory multiprocessor NUMA machines

来源：评论

学校读者我要写书评

暂无评论

IMPLEMENTATION AND EVALUATION OF UPDATE-BASED CACHE PROTOCOLS UNDER RELAXED memory CONSISTENCY MODELS

引用

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE 1995年第3期11卷 247-271页

作者： GRAHN, H STENSTROM, P DUBOIS, M UNIV SO CALIF DEPT ELECT ENGN SYST LOS ANGELES CA 90089 USA

Invalidation-based cache coherence protocols have been extensively studied in the context of large-scale shared-memory multiprocessors. Under a relaxed memory consistency model, most of the write latency can be hidden whereas cache misses still incur a severe performance problem. By contrast, update-based protocols have a potential to reduce both write and read penalties under relaxed memory consistency models because coherence misses can be completely eliminated. The purpose of this paper is to compare update- and invalidation-based protocols for their ability to reduce or hide memory access latencies and for their ease of implementation under relaxed memory consistency models. Based on a detailed simulation study, we find that write-update protocols augmented with simple competitive mechanisms - we call such protocols competitive-update protocols - can hide all the write latency and cut the read penalty by as much as 46% at the cost of some increase in the memory traffic. However, as compared to write-invalidate, update-based protocols require more aggressive memory consistency models and more local buffering in the second-level cache to be effective. In addition, their increased number of global writes may cause increased synchronization overhead in applications with high contention for critical sections.

关键词： shared-memory multiprocessor WRITE-UPDATE CACHE COHERENCE PROTOCOLS RELAXED memory CONSISTENCY MODELS LOCKUP-FREE CACHE DESIGN PERFORMANCE EVALUATION

来源：评论

学校读者我要写书评

暂无评论

TRAPEZOID SELF-SCHEDULING - A PRACTICAL SCHEDULING SCHEME FOR PARALLEL COMPILERS

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1993年第1期4卷 87-98页

作者： TZEN, TH NI, LM MICHIGAN STATE UNIV DEPT COMP SCIE LANSINGMI 48824 MICHIGAN STATE UNIV ADV COMP SYST LABE LANSINGMI 48824

In this paper, we present a new practical processor self-scheduling scheme, Trapezoid Self-Scheduling, for arbitrary parallel nested loops in shared-memory multiprocessors. Generally, loops are the richest source of parallelism in parallel programs. To dynamically allocate loop iterations to processors, one may achieve load balancing among processors at the expense of run-time scheduling overhead. By linearly decreasing the chunk size at run time, the best tradeoff between the scheduling overhead and balanced workload can be obtained in the proposed trapezoid self-scheduling approach. Due to its simplicity and flexibility, this approach can be efficiently implemented in any parallel compilers. The small and predictable number of chores also allow efficient management of memory in a static fashion. Out experiments conducted in a 96-node Butterfly GP-1000 clearly show the advantage of the trapezoid self-scheduling over other well-known self-scheduling approaches.

关键词： CHUNK SIZE CRITICAL SECTION LOAD BALANCING memory MANAGEMENT PARALLEL COMPILER PARALLEL LOOPS SCHEDULING OVERHEAD SELF-SCHEDULING shared-memory multiprocessor

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：