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

international Conference on parallel Architecture and Compilation Techniques (PACT)

作者： R. Rajamony A.L. Cox Dept. of Electr. & Comput. Eng. Rice Univ. Houston TX USA Computer Science Rice University Houston TX USA

We present two algorithms to minimize the amount of synchronization added when parallelizing a loop with loop-carried dependences. In contrast to existing schemes, our algorithms add lesser synchronization, while preserving the parallelism that can be extracted from the loop. Our first algorithm uses an interval graph representation of the dependence "overlap" to find a synchronization placement in time almost linear in the number of dependences. Although this solution may be suboptimal, it is still better than that obtained using existing methods, which first eliminate redundant dependences and then synchronize the remaining ones. Determining the optimal synchronization is an NP-complete problem. Our second algorithm therefore uses integer programming to determine the optimal solution. We first use a polynomial-time algorithm to find a minimal search space that must contain the optimal solution. Then, we formulate the problem of choosing the minimal synchronization from the search space as a set-cover problem, and solve it exactly using 0-1 integer programming. We show the performance impact of our algorithms by synchronizing a set of synthetic loops on an 8-processor Convex Exemplar. The greedily synchronized loops ran between 7% and 22% faster than those synchronized by the best existing algorithm. Relative to the same base, the optimally synchronized loops ran between 10% and and 22% faster.

关键词： parallel processing Linear programming Radio access networks Random access memory Computer science Automatic logic units NP-complete problem Polynomials Optimizing compilers

来源：评论

学校读者我要写书评

暂无评论

Locality analysis for parallel C programs

Locality analysis for parallel C programs

引用

international Conference on parallel Architecture and Compilation Techniques (PACT)

作者： Yingchun Zhu L.J. Hendren School of Computer Science McGIll University Montreal QUE Canada

Many parallel architectures support a memory model where some memory accesses are local, and thus inexpensive, while other memory accesses are remote, and potentially quite expensive. In order to achieve good parallel performance, it is often necessary to reduce the number of remote memory accesses. This can be done by the programmer, the compiler, or a combination of both. The overall goal is to minimize the work required by the programmer, and have the compiler automate the process as much as possible. The paper reports on compiler techniques for decreasing the number of remote memory accesses using locality analysis for a parallel dialect of C called EARTH-C. The locality analysis uses an algorithm inspired by type inference algorithms for fast points-to analysis. The algorithm estimates when an indirect reference via a pointer can be safely assumed to be a local access. The locality inference algorithm is also used to guide the automatic specialization of functions in order to take advantage of locality scientific to particular calling contexts. The locality analysis and automatic specialization has been implemented in the EARTH-C compiler which produces low level threaded code for the EARTH-C multithreaded architecture. Experimental results are presented for a set of benchmarks that operate on irregular, dynamically allocated data structures. The techniques give moderate to significant speedups and they do lessen the burden on the programmer.

关键词： programming profession Program processors Inference algorithms Algorithm design and analysis Earth Data structures Yarn Computer science parallel architectures parallel processing

来源：评论

学校读者我要写书评

暂无评论

Three-dimensional orthogonal tile sizing problem : mathematical programming approach

Three-dimensional orthogonal tile sizing problem : mathemati...

引用

international Conference on Application Specific Systems (ASAP), architectures and Processors

作者： R. Andonov N. Yanev H. Bourzoufi LIMAV Université de Valenciennes Valenciennes France Faculty of Mathematics and Informatics University of Sofia Sofia Bulgaria

We discuss in this paper the problem of finding the optimal tiling transformation of three-dimensional uniform recurrences on a two-dimensional torus/grid of distributed-memory general-purpose machines. We show that even for the simplest case of recurrences which allows for such transformation, the corresponding problem of minimizing the total running time is a non-trivial non-linear integer programming problem. For the later we derive an O(1) algorithm for finding a good approximation solution. The theoretical evaluations and the experimental results show that the obtained solution approximates the original minimum sufficiently well in the context of the considered problem. Such analytical results are of obvious interest and can be successfully used in parallelizing compilers as well as in performance tuning of parallel codes.

关键词： Tiles Mathematical programming Shape Mathematics Informatics Linear programming Approximation algorithms Performance analysis Optimizing compilers Message passing

来源：评论

学校读者我要写书评

暂无评论

NGEN: A massively parallel reconfigurable computer for biological simulation: Towards a self-organizing computer 1st

引用

1st international Conference on Evolvable Systems, ICES 1996

作者： McCaskill, John S. Maeke, Thomas Gemm, Udo Schulte, Ludger Tangen, Uwe Institut für Molekulare Biotechnologie Beutenbergstr. 11 JenaD-07745 Germany Resedaweg 3 Göttingen-Nikolausberg Germany Max Planck Institut für Biophys. Chemie Am Faßberg GöttingenD37077 Germany

ISBN: (纸本)3540631739

NGEN is a flexible computer hardware for rapid custom-circuit simulation of fine grained physical processes via a massively parallel architecture. It is optimized to implement dataflow architectures and systolic algorithms for large problems. High speed distributed SRAM on the chip-to chip interconnect enables a transparent extension of problem size beyond the limits posed by the number of available processors. For simulated evolution tasks for example, this takes the effective population sizes up into the range of millions of strings without computational bottlenecks. Using FPGA technology, multiple processors per chip may be configured down to the level of individual gates if need be. 144 agent FPGAs are grouped in blocks of 4 and connected with one another via one of several possible broad band electronic frontplanes (36 channels per chip) which implement 2D, 3D or higher geometries. The communication of the parallel computation with a UNIX host workstation via VME-bus is mediated also by configurable interface FPGAs allowing problem specific communication needs to be respected. A separate 100 Mhz clock card frees the machine from the 16 MHz VME clock and allows designs to run at their optimum speed. Configuration files may be downloaded in series or parallel from the host workstation in less than a second. They may be created by user programs or commercial schematic entry or VHDL products. A run-time library for writing simulations in which use the configurable hardware has been completed including a graphical interface allowing parallel symbolic debugging and display. The machine is a logical consequence of the shift of programming effort to effective communication in massively parallel applications. Its flexible structure also admits applications to real-time intelligent data acquistion tasks. © Springer-Verlag Berlin Heidelberg 1997.

关键词： Clocks

来源：评论

学校读者我要写书评

暂无评论

The effect of optimizing compilers on architecture and programs

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 1997年第4期E80D卷 403-408页

作者： Wolfe, M OREGON GRAD INST PORTLANDOR 97291

The first optimizing compiler was developed at IBM in order to prove that high level language programming could be as efficient as hand-coded machine language. Computer architecture and compiler optimization interacted through a feedback loop, from the high-level language computer architectures of the 1970s to the RISC machines of the 1980s. In the supercomputing community, the availability of effective vectorizing compilers delivered easy-to-use performance in the 1980s to the present. These compilers were successful at least in part because they could predict poor performance spots in the program and report these to users. This fostered a feedback loop between programmers and compilers to develop high performance programs. Future optimizing compilers for high performance computers and supercomputers will have to take advantage of both feedback loops.

关键词： optimizing compilers parallel computers

来源：评论

学校读者我要写书评

暂无评论

Vienna Fortran and the path towards a standard parallel language

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 1997年第4期E80D卷 409-416页

作者： Chapman, BM Mehrotra, P Zima, HP Institute for Software Technology and Parallel Systems University of Vienna A-1090 Vienna Liechtensteinstr. 22 Austria

Highly parallel scalable multiprocessing systems (HMPs) are powerful tools for solving large-scale scientific and engineering problems. However, these machines are difficult to program since algorithms must exploit locality in order to achieve high performance. Vienna Fortran was the first fully specified data-parallel language for HMPs that provided features for the specification of data distribution and alignment at a high level of abstraction. In this paper we outline the major elements of Vienna Fortran and compare it to High Performance Fortran (HPF), a de-facto standard in this area. A significant weakness of HPF is its lack of support for many advanced applications, which require irregular data distributions and dynamic load balancing. We introduce HPF+, an extension of HPF based on Vienna Fortran, that provides the required functionality.

关键词： high performance computing distributed-memory architectures data distribution, parallelization Fortran extensions

来源：评论

学校读者我要写书评

暂无评论

Geometric data structures on a reconfigurable mesh, with applications

Geometric data structures on a reconfigurable mesh, with app...

引用

international symposium on parallel Processing

作者： A. Datta Department of Mathematics Statistics and Computing Science University of New England Armidale NSW Japan

We present several geometric data structures and algorithms for problems for a planar set of rectangles and bipartitioning problems for a point set in two dimensions on a reconfigurable mesh of size n/spl times/n. The problems for rectangles include computing the measure, contour perimeter and maximum clique for the union of a set of rectangles. The bipartitioning problems for a two dimensional point set are solved in the L/sub /spl infin// and L/sub 1/ metrics. We solve all these problems in O(log n) time.

关键词： Data structures Tree data structures Very large scale integration Pattern recognition parallel architectures Computer architecture Mathematics Statistics Spatial databases Concurrency control

来源：评论

学校读者我要写书评

暂无评论

Two techniques for static array partitioning on message-passing parallel machines

Two techniques for static array partitioning on message-pass...

引用

international Conference on parallel Architecture and Compilation Techniques (PACT)

作者： Eric Hung-Yu Tseng J.-L. Gaudiot EE systems University of Southern California Los Angeles CA USA

We present two techniques for partitioning arrays in parallel DoAll loops for message-passing parallel machines. (1) Communication-free array partitioning: a general solution of communication-free partitioning is derived for arrays in a DoAll loop. The derivation is based on the Smith normal form decomposition of the matrix which characterizes the array references in a DoAll loop. (2) One block-communication partitioning: when communication-free partitioning is not possible, we derive the partitioning equations which allocate all remote data to a unique processor. Thus, at most one block-communication is required for each processor to obtain the remote data it needs during computation.

关键词： parallel machines Equations Concurrent computing High performance computing Matrix decomposition Computational efficiency Data structures programming profession Partitioning algorithms Costs

来源：评论

学校读者我要写书评

暂无评论

Generating communication sets efficiently on data-parallel programs

Generating communication sets efficiently on data-parallel p...

引用

IEEE international Conference on algorithms and architectures for parallel Processing (ICAP)

作者： Tsung-Chuan Huang Liang-Cheng Shiu Cherng-Haw Yu Department of Electrical Engineering National Sun Yat-Sen University Kaohsiung Taiwan

ISBN: (纸本)0780342291

Generating local memory access sequences and communication sets efficiently is an important issue while compiling a data-parallel language into a SPMD (Single Program Multiple Data) code. Recently, several approaches have been presented; they are based on the case in which array references are distributed across arbitrary number of processors with arbitrary block sizes using block-cyclic distribution. Typically, in order to generate explicit communication sets, each node program has to scan over the local memory access sequences. In this paper, we focus on two cases. First, array references are aligned to a common template and this template is distributed across processors using block-cyclic distribution. Second, array references are distributed across the same number of processors with same block size. The first case is further classified into one-level and two-level mappings. We construct a block state graph to generate communication sets by scanning only a portion of local memory access sequence. In one-level mappings and the second case, we only need to scan the active elements among the first s local active blocks; while in two-level mappings, only need to scan the active elements among the first /spl alpha/*s local active blocks, where s is the stride of regular section and a is the stride of alignment function. As a result, the efficiency can be greatly improved.

关键词： Sun Electronic mail Postal services programming profession Aggregates Runtime

来源：评论

学校读者我要写书评

暂无评论

Architecture design of motion estimation for ITU-T H.263

Architecture design of motion estimation for ITU-T H.263

引用

1997 Conference on Visual Communications and Image Processing

作者： Ku, CW Lin, GS Chen, LG Lee, YP National Taiwan Univ. (Taiwan)

ISBN: (纸本)0819424358

Digitalized video and audio system has become the trend of the progress in multimedia, because it provides great performance in quality and feasibility of processing. However, as the huge amount of information is needed while the bandwidth is limitted, data compression plays an important role in the system. Say, for a 176 x 144 monochromic sequence with 10 frames/sec frame rate, the bandwidth is about 2Mbps. This wastes much channel resource and limits the applications. MPEG (moving picttre ezpert groip) standardizes the video codec scheme, and it performs high compression ratio while providing good quality. MPEG-i is used for the frame size about 352 x 240 and 30 frames per second, and MPEG-2 provides scalibility and can be applied on scenes with higher definition, say HDTV (high definition television). On the other hand, some applications concerns the very low bit-rate, such as videophone and video-conferencing. Because the channel bandwidth is much limitted in telephone network, a very high compression ratio must be required. ITU-T announced the H.263 video coding standards to meet the above requirements.8 According to the simulation results of TMN-5,22 it outperforms 11.263 with little overhead of complexity. Since wireless communication is the trend in the near future, low power design of the video codec is an important issue for portable visual telephone. Motion estimation is the most computation consuming parts in the whole video codec. About 60% of the computation is spent on this parts for the encoder. Several architectures were proposed for efficient processing of block matching algorithms. In this paper, in order to meet the requirements of 11.263 and the expectation of low power consumption, a modified sandwich architecture in21 is proposed. Based on the parallel processing philosophy, low power is expected and the generation of either one motion vector or four motion vectors with half-pixel accuracy is achieved concurrently. In additi

关键词： Motion estimation Video Video compression Computer programming parallel processing Video coding Visualization Data compression Multimedia Video processing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：