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

3D Kirchhoff depth migration algorithm: A new scalable approach for parallelization on multicore CPU based cluster

COMPUTERS & GEOSCIENCES 2017年 100卷 67-75页

作者： Rastogi, Richa Londhe, Ashutosh Srivastava, Abhishek Sirasala, Kirannmayi M. Khonde, Kiran Savitribai Phule Pune Univ Campus Ctr Dev Adv Comp Pune 411007 Maharashtra India

In this article, a new scalable 3D Kirchhoff depth migration algorithm is presented on state of the art multicore CPU based cluster. Parallelization of 3D Kirchhoff depth migration is challenging due to its high demand of compute time, memory, storage and I/O along with the need of their effective management. The most resource intensive modules of the algorithm are traveltime calculations and migration summation which exhibit an inherent trade off between compute time and other resources. The parallelization strategy of the algorithm largely depends on the storage of calculated traveltimes and its feeding mechanism to the migration process. The presented work is an extension of our previous work, wherein a 3D Kirchhoff depth migration application for multicore CPU based parallel system had been developed. Recently, we have worked on improving parallel performance of this application by re-designing the parallelization approach. The new algorithm is capable to efficiently migrate both prestack and poststack 3D data. It exhibits flexibility for migrating large number of traces within the available node memory and with minimal requirement of storage, I/O and inter-node communication. The resultant application is tested using 3D Overthrust data on PARAM Yuva II, which is a Xeon E5-2670 based multicore CPU cluster with 16 cores/node and 64 GB shared memory. Parallel performance of the algorithm is studied using different numerical experiments and the scalability results show striking improvement over its previous version. An impressive 49.05X speedup with 76.64% efficiency is achieved for 3D prestack data and 32.00X speedup with 50.00% efficiency for 3D poststack data, using 64 nodes. The results also demonstrate the effectiveness and robustness of the improved algorithm with high scalability and efficiency on a multicore CPU cluster.

关键词： LAPLACIAN matrices parallelizing compilers compilers (Computer programs) SCALABILITY (Systems engineering) SYSTEMS design

来源：评论

学校读者我要写书评

暂无评论

Symbolic communication set generation for irregular parallel applications

引用

JOURNAL OF SUPERCOMPUTING 2003年第3期25卷 199-214页

作者： Guo, MY Pan, Y Liu, Z Univ Aizu Dept Comp Software Fukushima 9658580 Japan Georgia State Univ Dept Comp Sci Atlanta GA 30303 USA Nagasaki Inst Appl Sci Dept Environm & Cultural Sci Nagasaki 8510193 Japan

Communication set generation significantly influences the performance of parallel programs. However, studies seldom give attention to the problem of communication set generation for irregular applications. In this paper, we propose communication optimization techniques for the situation of irregular array references in nested loops. In our methods, the local array distribution schemes are determined so that the total number of communication messages is minimized. Then, we explain how to support communication set generation at compile-time by introducing some symbolic analysis techniques. In our symbolic analysis, symbolic solutions of a set of symbolic expression are obtained by using certain restrictions. We introduce symbolic analysis algorithms to obtain the solutions in terms of a set of equalities and inequalities. Finally, experimental results on a parallel computer CM-5 are presented to validate our approach.

关键词： parallelizing compilers irregular array references communication optimization symbolic analysis distributed memory multicomputers compile-time optimization

来源：评论

学校读者我要写书评

暂无评论

Memetic algorithms for parallel code optimization

引用

INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING 2007年第1期35卷 33-61页

作者： Oezcan, Ender Onbasioglu, Esin Yeditepe Univ TR-34755 Istanbul Turkey

Discovering the optimum number of processors and the distribution of data on distributed memory parallel computers for a given algorithm is a demanding task. A memetic algorithm (MA) is proposed here to find the best number of processors and the best data distribution method to be used for each stage of a parallel program. Steady state memetic algorithm is compared with transgenerational memetic algorithm using different crossover operators and hill-climbing methods. A self-adaptive MA is also implemented, based on a multimeme strategy. All the experiments are carried out on computationally intensive, communication intensive, and mixed problem instances. The MA performs successfully for the illustrative problem instances.

关键词： distributed memory parallel computers memetic algorithms parallelizing compilers search methods

来源：评论

学校读者我要写书评

暂无评论

Efficient loop partitioning for parallel codes of irregular scientific computations

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2003年第9期E86D卷 1825-1834页

作者： Guo, MY Univ Aizu Dept Comp Software Aizu Wakamatsu 9658580 Japan

In most cases of distributed memory computations, node programs are executed on processors according to the owner computes rule. However, owner computes rule is not best suited for irregular application codes. In irregular application codes, use of indirection in accessing left hand side array makes it difficult to partition the loop iterations, and because of use of indirection in accessing right hand side elements, we may reduce total communication by using heuristics other than owner computes rule. In this paper, we propose a communication cost reduction computes rule for irregular loop partitioning, called least communication computes rule. We partition a loop iteration to a processor on which the minimal communication cost is ensured when executing that iteration. Then, after all iterations are partitioned into various processors, we give global vs. local data transformation rule, indirection arrays remapping and communication optimization methods. The experimental results show that, in most cases, our approaches achieved better performance than other loop partitioning rules.

关键词： parallelizing compilers irregular scientific application communication optimization owner computes rule loop partitioning distributed memory multicomputers

来源：评论

学校读者我要写书评

暂无评论

EXTRACTING TASK-LEVEL PARALLELISM

引用

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS 1995年第4期17卷 600-634页

作者： GIRKAR, M POLYCHRONOPOULOS, CD UNIV ILLINOIS CTR SUPERCOMP RES & DEVURBANAIL 61801

Automatic detection of task-level parallelism (also referred to as functional. DAG, unstructured, or thread parallelism) at various levels of program granularity is becoming increasingly important for parallelizing and back-end compilers. parallelizing compilers detect iteration-level or coarser granularity parallelism which is suitable For parallel computers;detection of parallelism at the statement- or operation-level is essential for most modern microprocessors, including superscalar and VLIW architectures. In this article we study the problem of detecting, expressing, and optimizing task-level parallelism where ''task'' refers to a program statement of arbitrary granularity. Optimizing the amount of functional parallelism (by allowing synchronization between arbitrary nodes) in sequential programs requires the notion of precedence in terms of paths in graphs which incorporate control and data dependences. Precedences have been defined before in a different context;however, the definition was dependent on the ideas of parallel execution and time. We show that the problem of determining precedences statically is NP-complete. Determining precedence relationships is useful in finding the essential data dependences. We show that there exists a unique minimum set of essential data dependences;finding this minimum set is NP-hard and NP-easy. We also propose a heuristic algorithm for finding the set of essential data dependences. Static analysis of a program in the Perfect Benchmarks was done, and we present some experimental results.

关键词： CODE GENERATION CONTROL AND DATA DEPENDENCE parallelizing compilers SYNCHRONIZATION

来源：评论

学校读者我要写书评

暂无评论

Lock coarsening: Eliminating lock overhead in automatically parallelized object-based programs

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 1998年第2期49卷 218-244页

作者： Diniz, PC Rinard, MC Univ So Calif Inst Informat Sci Marina Del Rey CA 90292 USA MIT Cambridge MA 02139 USA

Atomic operations are a key primitive in parallel computing systems. The standard implementation mechanism for atomic operations uses mutual exclusion locks. In an object-based programming system, the natural granularity is to give each object its own lock. Each operation can then make its execution atomic by acquiring and releasing the lock for the object that it accesses. But this fine lock granularity may have high synchronization overhead because it maximizes the number of executed acquire and release constructs. To achieve good performance it may be necessary to reduce the overhead by coarsening the granularity at which the computation locks objects. In this article we describe a static analysis technique--lock coarsening-designed to automatically increase the lock granularity in object-based programs with atomic operations. We have implemented this technique in the context of a parallelizing compiler for irregular, object-based programs and used it to improve the generated parallel code. Experiments with two automatically parallelized applications show these algorithms to be effective in reducing the lock overhead to negligible levels. The results also show, however, that an overly aggressive lock coarsening algorithm may harm the overall parallel performance by serializing sections of the parallel computation. A successful compiler must therefore negotiate a trade-off between reducing lock overhead and increasing the serialization. (C) 1998 Academic Press.

关键词： parallelizing compilers atomic operation Locks AUTOMATIC object orientation Coarsening

来源：评论

学校读者我要写书评

暂无评论

Analyzing reference patterns in automatic data distribution tools

引用

INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING 1995年第6期23卷 515-535页

作者： Ayguade, E Labarta, J Garcia, J Girones, M Valero, M Computer Architecture Department Polytechnic University of Catalunya Barcelona Spain

Most of the approaches for automatic data distribution are based on the analysis of array reference patterns within loop nests. From this analysis, a graph recording preferences and conflicts in alignment is built. This graph is partitioned deciding the reference patterns that lead to local memory accesses and the ones that require access to remote data. The estimation of this data movement cost is usually performed by matching these nonaligned reference patterns with a collection of data movement primitives. In this paper, we show the main results of a set of experiments performed to analyze the complexity of the graph used to solve alignment and the chances for finding regular data distributions among processors. Three optimizations have been performed to increase the amount of reference patterns analyzed and the information that can be obtained from their analysis: expression substitution, subscript substitution, and induction variable detection. We also evaluate the effectiveness of these transformations.

关键词： parallelizing compilers automatic data distribution distributed-memory multiprocessors array accesses communication

来源：评论

学校读者我要写书评

暂无评论

Evaluating automatic parallelization in SUIF

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2000年第1期11卷 36-49页

作者： Moon, S So, B Hall, MW Univ So Calif Inst Informat Sci Marina Del Rey CA 90292 USA

This paper presents the results of an experiment to measure empirically the remaining opportunities for exploiting loop-level parallelism that are missed by the Stanford SUIF compiler, a state-of-the-art automatic parallelization system targeting shared-memory multiprocessor architectures. For the purposes of this experiment, we have developed a run-time parallelization test called the Extended Lazy Privatizing Dealt (ELPD) test, which is able to simultaneously test multiple loops in a loop nest. The ELPD test identifies a specific type of parallelism where each iteration of the loop being tested accesses independent data. possibly by making some of the data private to each processor. For 29 programs in three benchmark suites, the ELPD test was executed at run time for each candidate loop left unparallelized by the SUIF compiler to identify which of these loops could safely execute in parallel for the given program input. The results of this experiment point to two main requirements for improving the effectiveness of parallelizing compiler technology: incorporating control flow tests into analysis and extracting low-cost run-time parallelization tests from analysis results.

关键词： parallelizing compilers shared-memory multiprocessors data dependence analysis array privatization run-time parallelization

来源：评论

学校读者我要写书评

暂无评论

COMPILE-TIME SCHEDULING AND ASSIGNMENT OF DATA-FLOW PROGRAM GRAPHS WITH DATA-DEPENDENT ITERATION

引用

IEEE TRANSACTIONS ON COMPUTERS 1991年第11期40卷 1225-1238页

作者： HA, SH LEE, EA Dept. of Electr. Eng. & Comput. Sci. California Univ. Berkeley CA USA

Scheduling of data-flow graphs onto parallel processors consists in assigning actors to processors, ordering the execution of actors within each processor, and firing the actors at particular times. Many scheduling strategies do at least one of these operations at compile time to reduce run-time cost. In this paper, we classify four scheduling strategies: 1) fully dynamic, 2) static-assignment, 3) self-timed, and 4) fully static. These are ordered in decreasing run-time cost. Optimal or near-optimal compile-time decisions require deterministic, data-independent program behavior known to the compiler. Thus, moving from strategy 1) toward 4) either sacrifices optimality, decreases generality by excluding certain program constructs, or both. This paper proposes scheduling techniques valid for strategies 2), 3), and 4). In particular, we focus on data-flow graphs representing data-dependent iteration;for such graphs, although it is impossible to deterministically optimize the schedule at compile time, reasonable decisions can be made. For many applications, good compile-time decisions remove the need for dynamic scheduling or load balancing. We assume a known probability mass function for the number of cycles in the data-dependent iteration and show how a compile-time decision about assignment and/or ordering as well as timing can be made. The criterion we use is to minimize the expected total idle time caused by the iteration;in certain cases, this will also minimize the expected makespan of the schedule. We will also show how to determine the number of processors that should be assigned to the data-dependent iteration. The method is illustrated with a practical programming example, yielding preliminary results that are very promising.

关键词： DATA FLOW DATA-DEPENDENT ITERATION PARALLEL PROCESSORS parallelizing compilers QUASI-STATIC SCHEDULING SCHEDULING

来源：评论

学校读者我要写书评

暂无评论

Enhanced look-ahead scheduling technique to overlap communication with computation

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 1998年第11期E81D卷 1205-1212页

作者： Li, DC Iwahori, Y Hayashi, T Ishii, N Nagoya Inst Technol Educ Ctr Informat Proc Nagoya Aichi 4668555 Japan

Reducing communication overhead is a key goal of program optimization for current scalable multiprocessors. A well-known approach to achieving this is to map tasks (indivisible units of computation) to processors so that communication and computation overlap as much as possible. In an earlier work, we developed a look-ahead scheduling heuristic for efficiently reducing communication overhead with the aim of decreasing the completion time of a given parallel program. In this paper, we report on an extension of the algorithm, which fills in the idle time slots created by interprocessor communication without increasing the algorithm's time complexity. The results of experiments emphasize the importance of optimally filling idle time slots in processors.

关键词： parallelizing compilers interprocessor communication program optimization compile-time scheduling heuristics directed acyclic graphs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：