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

An adaptive algorithm selection framework for reduction parallelization

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2006年第10期17卷 1084-1096页

作者： Yu, Hao Rauchwerger, Lawrence IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA Texas A&M Univ Dept Comp Sci College Stn TX 77843 USA

Irregular and dynamic memory reference patterns can cause performance variations for low level algorithms in general and for parallel algorithms in particular. In this paper, we present an adaptive algorithm selection framework which can collect and interpret the characteristics of a particular instance of parallel reduction algorithms and select the best performing one from an existing library. The framework consists of the following components: 1) an offline systematic process for characterizing the input sensitivity of parallel reduction algorithms and a method for building corresponding predictive performance models, 2) an online input characterization and algorithm selection module, and 3) a small library of parallel reduction algorithms, which represent the algorithmic choices made available at runtime. We also present one possible integration of this framework in a restructuring compiler. We validate our design experimentally and show that our framework 1) selects the most appropriate algorithms in 85 percent of the cases studied, 2) overall, delivers 98 percent of the optimal performance, 3) adaptively selects the best algorithms for dynamic phases of a running program (resulting in performance improvements otherwise not possible), and 4) adapts to the underlying machine architectures (evaluated on IBM Regatta and HP V-Class systems).

关键词： runtime parallelization adaptive optimization reduction parallelization compiler optimization

来源：评论

学校读者我要写书评

暂无评论

IMPROVING MEMORY UTILIZATION IN CACHE COHERENCE DIRECTORIES

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1993年第10期4卷 1130-1146页

作者： LILJA, DJ YEW, PC UNIV ILLINOIS CTR SUPERCOMP RES & DEVURBANAIL 61801

Efficiently maintaining cache coherence is a major problem in large-scale shared memory multiprocessors. Hardware directory coherence schemes have very high memory requirements, while software-directed schemes must rely on imprecise compile-time memory disambiguation. Recently proposed dynamically tagged directory schemes allocate pointers to blocks only as they are referenced, which significantly reduces their memory requirements, but they still allocate pointers to blocks that do not need them. We present two compiler optimizations that exploit the high-level sharing information available to the compiler to further reduce the size of a tagged directory by allocating pointers only when necessary. Trace-driven simulations are used to show that the performance of this combined hardware-software approach is comparable to other coherence schemes, but with significantly lower memory requirements. In addition, these simulations suggest that this approach is less sensitive to the quality of the memory disambiguation and interprocedural analysis performed by the compiler than software-only coherence schemes.

关键词： CACHE COHERENCE compiler optimization DIRECTORY DYNAMIC POINTER ALLOCATION MEMORY OVERHEAD SHARED MEMORY MULTIPROCESSOR VERSION CONTROL

来源：评论

学校读者我要写书评

暂无评论

Efficient and safe-for-space closure conversion

引用

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS 2000年第1期22卷 129-161页

作者： Shao, Z Appel, AW Yale Univ Dept Comp Sci New Haven CT 06520 USA Princeton Univ Dept Comp Sci Princeton NJ 08544 USA

Modern compilers often implement function calls (or returns) in two steps: first, a "closure" environment is properly installed to provide access for free variables in the target program fragment;second, the control is transferred to the target by a "jump with arguments (or results)." Closure conversion-which decides where and how to represent closures at runtime-is a crucial step in the compilation of functional languages. This paper presents a new algorithm that exploits the use of compile-time control and data-flow information to optimize function calls. By extensive closure sharing and allocating as many closures in registers as possible, our new closure-conversion algorithm reduces heap allocation by 36% and memory fetches for local and global variables by 43%;and improves the already efficient code generated by an earlier version of the Standard NIL of New Jersey compiler by about 17% on a DECstation 5000. Moreover, unlike most other approaches, our new closure-allocation scheme satisfies the strong safe-for-space-complexity rule, thus achieving good asymptotic space usage.

关键词： algorithms languages performance theory closure conversion closure representation compiler optimization space safety callee-save registers flow analysis heap-based compilation

来源：评论

学校读者我要写书评

暂无评论

Tsoa: a two-stage optimization approach for GCC compilation options to minimize execution time

引用

AUTOMATED SOFTWARE ENGINEERING 2024年第2期31卷 1-36页

作者： Ni, Youcong Du, Xin Yuan, Yuan Xiao, Ruliang Chen, Gaolin Fujian Normal Univ Coll Comp & Cyber Secur Fuzhou Peoples R China Beihang Univ Beijing Peoples R China

The open-source compiler GCC offers numerous options to improve execution time. Two categories of approaches, machine learning-based and design space exploration, have emerged for selecting the optimal set of options. However, they continue to face challenge in quickly obtaining high-quality solutions due to the large and discrete optimization space, time-consuming utility evaluation for selected options, and complex interactions among options. To address these challenges, we propose TSOA, a Two-Stage optimization Approach for GCC compilation options to minimize execution time. In the first stage, we present OPPM, an Option Preselection algorithm based on Pattern Mining. OPPM generates diverse samples to cover a wide range of option interactions. It subsequently mines frequent options from both objective-improved and non-improved samples. The mining results are further validated using CRC codes to precisely preselect options and reduce the optimization space. Transitioning to the second stage, we present OSEA, an Option Selection Evolutionary optimization Algorithm. OSEA is grounded in solution preselection and an option interaction graph. The solution preselection employs a random forest to build a classifier, efficiently identifying promising solutions for the next-generation population and thereby reducing the time spent on utility evaluation. Simultaneously, the option interaction graph is built to capture option interplays and their influence on objectives from evaluated solutions. Then, high-quality solutions are generated based on the option interaction graph. We evaluate the performance of TSOA by comparing it with representative machine learning-based and design space exploration approaches across a diverse set of 20 problem instances from two benchmark platforms. Additionally, we validate the effectiveness of OPPM and conduct related ablation experiments. The experimental results show that TSOA outperforms state-of-the-art approaches significantly in both

关键词： compiler optimization GCC Option selection Pattern mining Evolutionary algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient synthesis of out-of-core algorithms using a nonlinear optimization solver

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2006年第5期66卷 659-673页

作者： Krishnan, S Krishnamoorthy, S Baumgartner, G Lam, CC Ramanujam, J Sadayappan, P Choppella, V Ohio State Univ Dept Comp Sci & Engn Columbus OH 43210 USA Louisiana State Univ Dept Comp Sci Baton Rouge LA 70803 USA Louisiana State Univ Dept Elect & Comp Engn Baton Rouge LA USA Indian Inst Informat Technol & Management Thiruvananthapuram 695581 Kerala India

We address the problem of efficient out-of-core code generation for a special class of imperfectly nested loops encoding tensor contractions arising in quantum chemistry computations. These loops operate on arrays too large to fit in physical memory. The problem involves determining optimal tiling of loops and placement of disk I/O statements. This entails a search in an explosively large parameter space. We formulate the problem as a nonlinear optimization problem and use a discrete constraint solver to generate optimized out-of-core code. The solution generated using the discrete constraint solver consistently outperforms other approaches by up to a factor of four. Measurements on sequential and parallel versions of the generated code demonstrate the effectiveness of the approach. (c) 2005 Published by Elsevier Inc.

关键词： data locality optimization out-of-core algorithms program transformation compiler optimization discrete constrained search tensor contractions

来源：评论

学校读者我要写书评

暂无评论

compiler-based I/O prefetching for out-of-core applications

引用

ACM TRANSACTIONS ON COMPUTER SYSTEMS 2001年第2期19卷 111-170页

作者： Brown, AD Mowry, TC Krieger, O Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA

Current operating systems offer poor performance when a numeric application's working set does not fit in main memory. As a result, programmers who wish to solve "out-of-core" problems efficiently are typically faced with the onerous task of rewriting an application to use explicit I/O operations (e.g., read/write). In this paper, we propose and evaluate a fully automatic technique which liberates the programmer from this task, provides high performance, and requires only minimal changes to current operating systems. In our scheme the compiler provides the crucial information on future access patterns without burdening the programmer;the operating system supports nonbinding prefetch and release hints for managing I/O;and the operating system cooperates with a run-time layer to accelerate performance by adapting to dynamic behavior and minimizing prefetch overhead. This approach maintains the abstraction of unlimited virtual memory for the programmer, gives the compiler the flexibility to aggressively insert prefetches ahead of references, and gives the operating system the flexibility to arbitrate between the competing resource demands of multiple applications. We implemented our compiler analysis within the SUIF compiler, and used it to target implementations of our run-time and OS support on both research and commercial systems (Hurricane and IRIX 6.5, respectively). Our experimental results show large performance gains for out-of-core scientific applications on both systems: more than 50% of the I/O stall time has been eliminated in most cases, thus translating into overall speedups of roughly twofold in many cases.

关键词： performance design experimentation virtual memory compiler optimization prefetching

来源：评论

学校读者我要写书评

暂无评论

compiler controlled prefetching for multiprocessors using low-overhead traps and prefetch engines

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2000年第5期60卷 585-615页

作者： Skeppstedt, J Dubois, M Univ Lund Dept Comp Sci S-22100 Lund Sweden Univ So Calif Dept Elect Engn Syst Los Angeles CA 90089 USA

In this paper we propose and evaluate a new data-prefetching technique for cache coherent multiprocessors. Prefetches are issued by a functional unit called a prefetch engine which is controlled by the compiler. We let second-level cache misses generate cache miss traps and start the prefetch engine in a trap handler. The trap handler is fast (40-50 cycles) and does not normally delay the program beyond the memory latency of the miss. Once started, the prefetch engine executes on its own and causes no instruction overhead. The only instruction overhead in our approach is when a trap handler completes after data arrives. The advantages of this technique are (1) it exploits static compiler analysis to determine what to prefetch, which is hard to do in hardware, (2) it uses prefetching with very little instruction overhead, which is a limitation for traditional software-controlled prefetching, and (3) it is accurate in the sense that it generates very little useless traffic while maintaining a high prefetching coverage. We also study whether one could emulate the prefetch engine in software, which would not require any additional hardware beyond support for generating cache miss traps and ordinary prefetch instructions. In this paper we present the functionality of the prefetch engine and a compiler algorithm to control it. We evaluate our technique on six parallel scientific and engineering applications using an optimizing compiler with our algorithm and a simulated multiprocessor. We find that the prefetch engine removes up to 67% of the memory access stall time at an instruction overhead less than 0.42%. The emulated prefetch engine removes in general less stall time at a higher instruction overhead, (C) 2000 Academic Press.

关键词： multiprocessors memory latency data prefetching compiler optimization

来源：评论

学校读者我要写书评

暂无评论

PMU Guided Structure Data-Layout optimization

引用

Tsinghua Science and Technology 2011年第2期16卷 145-150页

作者：闫家年陈文光郑纬民 Department of Computer Science and Technology Tsinghua University

Existing methods of obtaining runtime feedback for structure data-layout optimization have several drawbacks, such as large overhead and difficulty composing training sets. As a result, structure data-layout optimization is not widely used. To overcome these drawbacks, a performance monitoring unit （PMU） sampling method was developed with much less overhead and better portability and usability. An algorithm was developed to correct incomplete and inaccurate PMU sampling. With the corrected PMU feedback, a structure data-layout optimizer achieved a 45.1% performance improvement compared to a design without data-layout optimization, which is 97.6% of the performance improvement achieved with instrumented feedback. Calculation of the PMU feedback increased the execution time by 12.3%, compared to the overhead for the instrumented feedback of 341.5%. Tests show that the PMU feedback is efficient and effective for structure data-layout optimization.

关键词： structure data layout performance monitoring unit (PMU) compiler optimization program locality

来源：评论

学校读者我要写书评

暂无评论

Allo: A Programming Model for Composable Accelerator Design

引用

PROCEEDINGS OF THE ACM ON PROGRAMMING LANGUAGES-PACMPL 2024年第PLDI期8卷 593-620页

作者： Chen, Hongzheng Zhang, Niansong Xiang, Shaojie Zeng, Zhichen Dai, Mengjia Zhang, Zhiru Cornell Univ Ithaca NY 14853 USA Univ Sci & Technol China Hefei Peoples R China

Special-purpose hardware accelerators are increasingly pivotal for sustaining performance improvements in emerging applications, especially as the benefits of technology scaling continue to diminish. However, designers currently lack effective tools and methodologies to construct complex, high-performance accelerator architectures in a productive manner. Existing high-level synthesis (HLS) tools often require intrusive source-level changes to attain satisfactory quality of results. Despite the introduction of several new accelerator design languages (ADLs) aiming to enhance or replace HLS, their advantages are more evident in relatively simple applications with a single kernel. Existing ADLs prove less effective for realistic hierarchical designs with multiple kernels, even if the design hierarchy is flattened. In this paper, we introduce Allo, a composable programming model for efficient spatial accelerator design. Allo decouples hardware customizations, including compute, memory, communication, and data type from algorithm specification, and encapsulates them as a set of customization primitives. Allo preserves the hierarchical structure of an input program by combining customizations from different functions in a bottom-up, type-safe manner. This approach facilitates holistic optimizations that span across function boundaries. We conduct comprehensive experiments on commonly-used HLS benchmarks and several realistic deep learning models. Our evaluation shows that Allo can outperform state-of-the-art HLS tools and ADLs on all test cases in the PolyBench. For the GPT2 model, the inference latency of the Allo generated accelerator is 1.7x faster than the NVIDIA A100 GPU with 5.4x higher energy efficiency, demonstrating the capability of Allo to handle large-scale designs.

关键词： Hardware accelerators schedule language accelerator design language compiler optimization

来源：评论

学校读者我要写书评

暂无评论

STATIC SCHEDULING FOR BARRIER MIMD ARCHITECTURES

引用

JOURNAL OF SUPERCOMPUTING 1992年第4期5卷 263-289页

作者： DIETZ, HG ZAAFRANI, A OKEEFE, MT UNIV MINNESOTA DEPT ELECT ENGNMINNEAPOLISMN 55455

In a SIMD or VLIW machine, conceptual synchronizations are accomplished by using a static code schedule that does not require run-time synchronization. The lack of run-time synchronization overhead makes these machines very effective for fine-grain parallelism, but they cannot execute parallel code structures as general as those executed by MIMD architectures, and this limits their utility. In this paper we present a timing analysis that allows a compiler for a MIMD machine to eliminate a large fraction of the run-time synchronization by making efficient use of static code scheduling. Although these techniques can be adapted to be applied to most MIMD machines, this paper centers on the analysis and scheduling for barrier MIMD machines. Barrier MIMDs are asynchronous multiple instruction stream/multiple data stream architectures capable of parallel execution of variable execution-time instructions and arbitrary control flow (e.g., while loops and calls). However, they also incorporate a special hardware barrier synchronization mechanism that facilitates static scheduling by providing a mechanism which the compiler can use to enforce precise timing constraints. In other words, the compiler tracks relative timing between processors and uses static code scheduling until the timing imprecision becomes too large, at which point the compiler simply inserts a barrier to reduce that timing imprecision to zero (or a small constant). This paper describes new scheduling and barrier placement algorithms for barrier MIMDs that are based loosely on the list scheduling approach employed for VLWs [Ellis 1985]. In addition, the experimental results from scheduling thousands of synthetic benchmark programs for a parameterized barrier MIMD machine are presented.

关键词： BARRIER MIMD CODE SCHEDULING TIMING ANALYSIS compiler optimization BARRIER SYNCHRONIZATION

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：