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

Quasi-fully dynamic algorithms for two-connectivity and cycle equivalence

ALGORITHMICA 2002年第2期33卷 168-182页

作者： Korupolu, MR Ramachandran, V Univ Texas Dept Comp Sci Austin TX 78712 USA

We introduce a new class of dynamic graph algorithms called quasi-fully dynamic algorithms, which are much more general than backtracking algorithms and are much simpler than fully dynamic algorithms. These algorithms are especially suitable for applications in which a certain core connected portion of the graph remains fixed, and fully dynamic updates occur on the remaining edges in the graph, We present very simple quasi-fully dynamic algorithms with O(log n) worst-case time per operation for edge connectivity and O(log n) amortized time per operation for cycle equivalence, The former is deterministic while the latter is Monte-Carlo-type randomized. For 2-vertex connectivity, we give a deterministic quasi-fully dynamic algorithm with O(log(3)n) amortized time per operation. The quasi-fully dynamic algorithm we present for cycle equivalence (which has several applications in optimizing compilers) is of special interest since the algorithm is quite simple, and no special-purpose incremental or backtracking algorithm is known for this problem.

关键词： dynamic algorithms graph algorithms cycle equivalence connected graphs edge and vertex connectivity randomized algorithms compiler optimization

来源：评论

学校读者我要写书评

暂无评论

Meld scheduling: A technique for relaxing scheduling constraints

引用

INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING 1998年第4期26卷 349-381页

作者： Abraham, SG Kathail, V Deitrich, BL Hewlett Packard Labs Palo Alto CA 94304 USA Univ Illinois Ctr Reliable & High Performance Comp Urbana IL 61801 USA

Meld scheduling melds the schedules of neighboring scheduling regions to respect latencies of operations issued in one region but completing after control transfers to the other. In contrast, conventional schedulers ignore latency constraints from other regions leading to potentially avoidable stalls in an interlocked (superscalar) machine or incorrect schedules for noninterlocked (VLIW) machines. Alternatively, schedulers that conservatively require all operations to complete before the branch takes effect produce inefficient schedules. In this paper, we present general data structures for maintaining latency constraint information at region boundaries. We present a meld scheduling algorithm for noninterlocked processors that generates latency constraints at the boundaries of scheduled regions and utilizes this information during the scheduling of other regions. We present a range of design options and describe the reasons behind our particular choices. We evaluate the performance of meld scheduling an a range of machine models on a set of SPEC92 and UNIX benchmarks.

关键词： instruction scheduling global scheduling latency constraint propagation instruction-level parallel processors compiler optimization

来源：评论

学校读者我要写书评

暂无评论

THE POTENTIAL OF COMPILE-TIME ANALYSIS TO ADAPT THE CACHE COHERENCE ENFORCEMENT STRATEGY TO THE DATA SHARING CHARACTERISTICS

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1995年第5期6卷 470-481页

作者： MOUNESTOUSSI, F LILJA, DJ UNIV MINNESOTA FAC GRADDEPT COMP SCIMINNEAPOLISMN 55455

Cache coherence schemes that dynamically adapt to memory referencing patterns have been proposed to improve coherence enforcement in shared-memory multiprocessors. By using only run-time information, however, these existing schemes are incapable of looking ahead in the memory referencing stream. We present a combined hardware-software strategy that uses the predictive capability of the compiler to select updating or invalidating for each write reference. To determine the potential performance improvement that can be achieved with this optimization, three different levels of compiler capabilities are examined. Simulations using memory traces show that with an ideal compiler, this optimization can potentially reduce the miss ratio by 0.4% to 15% compared to an invalidating-only scheme, while reducing the generated network traffic by 13% to 94 % compared to an updating-only scheme. In addition, this optimization can potentially reduce the miss ratio by up to 13%, while reducing the generated network traffic by up to 92%, compared to a dynamic adaptive scheme. Furthermore, performance can be potentially improved even with a compiler capable of performing only imprecise array subscript analysis and no interprocedural analysis.

关键词： compiler optimization UPDATE INVALIDATE DIRECTORY CACHE COHERENCE SHARED-MEMORY MULTIPROCESSOR

来源：评论

学校读者我要写书评

暂无评论

A constant propagation algorithm for explicitly parallel programs

引用

INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING 1998年第5期26卷 563-589页

作者： Lee, J Midkiff, SP Padua, DA Univ Illinois Dept Comp Sci Urbana IL 61801 USA IBM Corp Thomas J Watson Res Ctr Yorktown Heights NY 10598 USA

In this paper, we present a constant propagation algorithm for explicitly parallel programs, which we call the Concurrent Sparse Conditional Constant propagation algorithm. This algorithm is an extension of the Sparse Conditional Constant propagation algorithm. Without considering the interaction between threads, classical optimizations lead to an incorrect program transformation for parallel programs. To make analyzing parallel programs possible, a new intermediate representation is needed. We introduce the Concurrent Static Single Assignment (CSSA) form to represent explicitly parallel programs with interleaving semantics and synchronization. The only parallel construct considered in this paper is cobegin/coend. A new confluence function, the pi-assignment, which summarizes the information of interleaving statements between threads, is introduced. The Concurrent Control Flow Graph, which contains information about conflicting statements, control flow, and synchronization, is used as an underlying representation for the CSSA from.

关键词： compiler optimization constant propagation, control flow graph explicit parallelism intermediate representation static single assignment form

来源：评论

学校读者我要写书评

暂无评论

THE POWER TEST FOR DATA DEPENDENCE

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1992年第5期3卷 591-601页

作者： WOLFE, M TSENG, CW RICE UNIV DEPT COMP SCIHOUSTONTX 77251

This paper introduces a data dependence decision algorithm called the Power Test;the Power Test is a combination of the extended GCD algorithm and the Fourier-Motzkin method to eliminate variables in a system of inequalities. This is the first test that can generate the information needed for some advanced transformations, and that can handle complex simultaneous loop limits. This paper briefly reviews previous work in data dependence decision algorithms, and describes the Power Test. Some examples which motivated the development of this test are examined, including those which demonstrate the additional power of the Power Test. Although it may be too expensive for use as a general purpose dependence test in a compiler, the Power Test has proven useful in an interactive program restructuring environment.

关键词： compilerS compiler optimization DATA DEPENDENCE PARALLELIZATION

来源：评论

学校读者我要写书评

暂无评论

Mapping stream programs onto multicore platforms by local search and genetic algorithm

引用

COMPUTER LANGUAGES SYSTEMS & STRUCTURES 2016年 46卷 182-205页

作者： Farhad, S. M. Nayeem, Muhammad Ali Rahman, Md. Khaledur Rahman, M. Sohel BUET Dept CSE Dhaka 1000 Bangladesh

This paper presents a number of novel metaheuristic approaches that can efficiently map stream graphs on multicores. A stream graph consists of a set of actors performing different functions communicating through edges. Orchestrating stream graphs on multi cores can be formulated as an Integer Linear Programming (ILP) problem but ILP solver takes exponential time to provide an optimal solution. We propose metaheuristic algorithms to achieve near optimal solutions within a reasonable amount of time. We employ six different variants of the Hill-Climbing (HC) algorithm employing different tweak operators that produce excellent result extremely quickly. We also propose six different variants of Genetic Algorithm (GA) to examine how effective these variants can be in escaping the local optima. We finally combine HC and GA techniques (which is also known as 'memetic algorithm') to produce hybrid techniques that outperform the individual performance of HC and GA techniques. We compare our results with the results generated by the CPLEX optimization tool. Our best technique has achieved a geometric mean speedup of 7.42 x across a range of StreamIt benchmarks on an eight-core processor. (C) 2016 Elsevier Ltd. All rights reserved.

关键词： Stream programming Metaheuristics Local search operator compiler optimization Parallel programming Genetic algorithm Hybrid genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

Reducing memory penalty by a programmable prefetch engine for on-chip caches

引用

MICROPROCESSORS AND MICROSYSTEMS 1997年第2期21卷 121-130页

作者： Chen, TF NATL CHUNG CHENG UNIV DEPT COMP SCI CHIAYI TAIWAN

Prefetching has been shown to be one of several effective approaches that can tolerate large memory latencies. Hardware-based prefetching schemes handles prefetching at run-time without compiler intervention, whereas software-directed prefetching inserts prefetch instructions in the code by performing static data analysis. In this paper, we consider a prefetch engine called Hare, which handles prefetches at run time and is built in addition to the data pipelining in the on-chip data cache for high-performance processors. The key design is that it is programmable by the user code so that techniques of software prefetching can be also employed in exploiting the benefits of prefetching. The engine launches prefetches ahead of current execution, which is controlled by the program counter. We evaluate the proposed scheme by trace-driven simulation and consider area and cycle time factors for the evaluation of cost-effectiveness. Our performance results show that the prefetch engine can significantly reduce data access penalty with only little prefetching overhead. (C) 1997 Elsevier Science B.V.

关键词： data prefetch programmable engine software prefetch compiler optimization

来源：评论

学校读者我要写书评

暂无评论

Transforming complex loop nests for locality

引用

JOURNAL OF SUPERCOMPUTING 2004年第3期27卷 219-264页

作者： Yi, Q Kennedy, K Adve, V Rice Univ Houston TX 77005 USA Univ Illinois Urbana IL 61801 USA

Over the past 20 years, increases in processor speed have dramatically outstripped performance increases for standard memory chips. To bridge this gap, compilers must optimize applications so that data fetched into caches are reused before being displaced. Existing compiler techniques can efficiently optimize simple loop structures such as sequences of perfectly nested loops. However, on more complicated structures, existing techniques are either ineffective or require too much computation time to be practical for a commercial compiler. To optimize complex loop structures both effectively and inexpensively, we present a novel loop transformation, dependence hoisting, for optimizing arbitrarily nested loops, and an efficient framework that applies the new technique to aggressively optimize benchmarks for better locality. Our technique is as inexpensive as the traditional unimodular loop transformation techniques and thus can be incorporated into commercial compilers. In addition, it is highly effective and is able to block several linear algebra kernels containing highly challenging loop structures, in particular, Cholesky, QR, LU factorization without pivoting, and LU with partial pivoting. The automatic blocking of QR and pivoting LU is a notable achievement - to our knowledge, few previous compiler techniques, including theoretically more general loop transformation frameworks [1, 21, 23, 27, 31], were able to completely automate the blocking of these kernels, and none has produced the same blocking as produced by our technique. These results indicate that with low compilation cost, our technique can in practice match the effectiveness of much more expensive frameworks that are theoretically more powerful.

关键词： compiler optimization loop transformation complex loop structure linear algebra kernels

来源：评论

学校读者我要写书评

暂无评论

Compile time barrier synchronization minimization

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2002年第6期13卷 529-543页

作者： O'Boyle, M Stöhr, E Univ Edinburgh Div Informat Edinburgh EH9 3JZ Midlothian Scotland Univ Manchester Dept Comp Sci Manchester M13 9PL Lancs England

This paper presents a new compiler approach to minimizing the number of barriers executed in parallelized programs. A simple procedure is developed to reduce the complexity of barrier placement by eliminating certain data dependences, without affecting optimality. An algorithm is presented which, provably, places the minimal number of barriers in perfect loop nests and in certain imperfect loop nest structures. This scheme is generalized to accept entire, well-structured control-flow programs containing arbitrary nesting of IF constructs, loops, and subroutines. It has been implemented in a prototype parallelizing compiler and applied to several well-known benchmarks where it has been shown to place significantly fewer synchronization points than existing techniques. Experiments indicate that on average the number of barriers executed is reduced by 70 percent and there is a three fold improvement in execution time when evaluated on a 32-processor SGI Origin 2000.

关键词： compiler optimization synchronization reduction efficient parallelization barrier minimization graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Walk-time address adjustment for improving the accuracy of dynamic branch prediction

引用

IEEE TRANSACTIONS ON COMPUTERS 1999年第5期48卷 457-469页

作者： Chen, CM King, CT Natl Tsing Hua Univ Dept Comp Sci Hsinchu 300 Taiwan

Dynamic branch prediction has been an effective technique for boosting the performance of modern high performance microprocessors. Since hardware predictors only have a limited number of 2-bit counters but programs often have a large, variable number of branches, two branches in the programs may thus be mapped to the same 2-bit counter. Predictions for these two branches may interfere with each other. This, in turn, reduces the prediction accuracy. In this paper, we discuss how a pre-run-time optimization technique, called address adjustment, can help to reduce branch interference. The technique adjusts the addresses of conditional branches in the given program by inserting NOP instructions at appropriate locations. In this way, the mapping between the conditional branches and the 2-bit counters can be controlled and branch interference can be minimized. Address adjustment can be applied at compile or link time, and the latter makes it a walk-time transformation technique [4]. Three possible address adjustment schemes are investigated: constrained address adjustment, relaxed address adjustment, and branch classification. Experimental results show that address adjustment can reduce branch misprediction ratios on existing hardware predictors. Among the three methods, branch classification has the most improvement.

关键词： branch prediction address adjustment computer architecture compiler optimization superscalar processor

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：