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

An incremental basic block instruction scheduler

JOURNAL OF SYSTEMS ARCHITECTURE 1998年第3期45卷 179-203页

作者： Venugopal, R Srikant, YN Indian Inst Sci Bangalore 560012 Karnataka India

Incremental methods for the earlier phases of compilation such as lexical analysis, parsing, semantic analysis and machine independent optimization have been well studied. In this paper, we describe an approach towards incremental machine dependent optimization, in particular, basic block instruction scheduling. First we describe a simple algorithm for the incremental construction of the dependency directed acyclic graph (DDAG). We then target basic block scheduling based on the longest path length criterion. In this context, we apply an existing incremental shortest path algorithm for computing the lengths of the longest paths incrementally. The techniques described have been implemented in the form of an incremental basic block instruction scheduler for the IBM RISC System/6000 processor. Compile-time measurements on a few sample programs indicate that this approach results in significant reduction in the time taken for instruction scheduling when compared with that taken by the non-incremental approach. (C) 1998 Elsevier Science B.V. All rights reserved.

关键词： integrated programming environments incremental compilation instruction scheduling compiler optimization

来源：评论

学校读者我要写书评

暂无评论

Vectorizing programs with IF-statements for processors with SIMD extensions

引用

JOURNAL OF SUPERCOMPUTING 2020年第6期76卷 4731-4746页

作者： Sun, Huihui Gorlatch, Sergei Zhao, Rongcai Univ Munster Munster Germany Natl Digital Switching Syst Engn & Technol Res Ct Zhengzhou Henan Peoples R China

Vectorization of programs is crucial for achieving high performance on modern processors with SIMD (Single Instruction Multiple Data) extensions. Programs with IF-statements suffer from control flow divergence that seriously complicates automatic vectorization. Therefore, contemporary compilers employ the IF-conversion approach to convert control flow to data flow, which relies on using predicated execution techniques (i.e., masked or select SIMD instructions). In this paper, we enhance the compiler's capabilities to generate efficiently vectorized code for processors without masked instructions. We improve the state of the art in program vectorization by developing a novel approach-IF-select transformation-which is applicable to arbitrarily nested IF-statements. We implement our approach in the open-source Open64 compiler and evaluate its performance on the SW26010 processor used in the Sunway TaihuLight supercomputer (currently #3 in the TOP500 list) that does not support masked instructions. We extend our vectorization approach by providing an additional LLVM optimization pass to reduce the amount of masked memory accesses on processors without masked instructions, e.g., IBM Power8 and ARMCortex-A8. Experimental results demonstrate the performance advantages of the suggested vectorization techniques.

关键词： compiler optimization SIMD extensions IF-conversion Masked instructions Select instructions

来源：评论

学校读者我要写书评

暂无评论

Array organization in parallel memories

引用

INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING 2004年第2期32卷 123-163页

作者： Al-Mouhamed, M King Fahd Univ Petr & Minerals Coll Comp Sci & Engn Dept Comp Engn Dhahran 31261 Saudi Arabia

The bandwidth mismatch between processor and main memory is one major throughput limiting problem. Although streamed computations have predictable access patterns their references have little temporal locality and are generally too long to cache. A memory and compiler co-optimization aimed at reducing low-level memory accesses using software and hardware locality optimizations is presented. We propose a scalable and predictable parallel memory based on a compiler synthesis of storage schemes for multi-dimensional arrays that are accessed by an arbitrary but known set of data access patterns. Using algebra of non-singular Boolean matrices, we present analysis of conflict-free access to (1) parallel memories, and (2) alignment networks. Finding a multi-pattern storage scheme is one NP-complete problem. An effective compiler heuristic is proposed for finding a storage matrix that minimizes overall memory access time. This applies to arbitrary linear patterns and arbitrary alignment networks. It is shown that the proposed storage scheme finds an optimal storage scheme for parallel (1) FFT, and (2) bitonic sorting. The proposed storage scheme outperforms statically optimized storages in the case of power-of-2 multi-stride access. The case of non power-of-2 strides is also addressed. The performance and scalability of the proposed parallel memory and its predictable access time are presented using numerical and multimedia algorithms. It is shown that a memory utilization above 83% is achieved by our storage scheme for 64 memories, which largely outperforms previous proposals. Our approach provides a tool for matching the storage pattern with the data access patterns needed for embedded systems running streamed computations with predictable data access patterns.

关键词： access patterns embedded systems compiler optimization parallel memory streamed computations

来源：评论

学校读者我要写书评

暂无评论

Symbolic Analysis for Data Plane Programs Specialization

引用

ACM TRANSACTIONS ON ARCHITECTURE AND CODE optimization 2022年第1期20卷 1-21页

作者： Luinaud, Thomas Langlois, J. M. Pierre Savaria, Yvon Polytech Montreal 2500 Chemin Polytech Montreal PQ H3T 1J4 Canada

Programmable network data planes have extended the capabilities of packet processing in network devices by allowing custom processing pipelines and agnostic packet processing. While a variety of applications can be implemented on current programmable data planes, there are significant constraints due to hardware limitations. One way to meet these constraints is by optimizing data plane programs. Program optimization can be achieved by specializing code that leverages architectural specificity or by compilation passes. In the case of programmable data planes, to respond to the varying requirements of a large set of applications, data plane programs can target different architectures. This leads to difficulties when developers want to reuse the code. One solution to that is to use compiler optimization techniques. We propose performing data plane program specialization to reduce the generated program size. To this end, we propose to specialize in programs written in P4, a Domain Specific Language (DSL) designed for specifying network data planes. The proposed method takes advantage of key aspects of the P4 language to perform a symbolic analysis on a P4 program and then partially evaluate the program to specialize it. The approach we propose is independent of the target architecture. We evaluate the specialization technique by implementing a packet deparser on an FPGA. The results demonstrate that program specialization can reduce the resource usage by a factor of 2 for various packet deparsers.

关键词： compiler optimization program specialization P4 language network data plane FPGA packet deparsers

来源：评论

学校读者我要写书评

暂无评论

Exploiting locality for irregular scientific codes

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2006年第7期17卷 606-618页

作者： Han, H Tseng, CW Korea Adv Inst Sci & Technol Div Comp Sci Taejon 305701 South Korea Univ Maryland Dept Comp Sci College Pk MD 20742 USA

Irregular scientific codes experience poor cache performance due to their irregular memory access patterns. In this paper, we present two new locality improving techniques for irregular scientific codes. Our techniques exploit geometric structures hidden in data access patterns and computation structures. Our new data reordering (GPART) finds the graph structure within data accesses and applies hierarchical clustering. Quality partitions are constructed quickly by clustering multiple neighbor nodes with priority on nodes with high degree and repeating a few passes. Overhead is kept low by clustering multiple nodes in each pass and considering only edges between partitions. Our new computation reordering (Z-SORT) treats the values of index arrays as coordinates and reorders corresponding computations in Z-curve order. Applied to dense inputs, Z-SORT achieves performance close to data reordering combined with other computation reordering but without the overhead involved in data reordering. Experiments on irregular scientific codes for a variety of meshes show locality optimization techniques are effective for both sequential and parallelized codes, improving performance by 60-87 percent. GPART achieved within 1-2 percent of the performance of more sophisticated partitioning algorithms, but with one third of the overhead. Z-SORT also yields the performance improvement of 64 percent for dense inputs, which is comparable with data reordering combined with computation reordering.

关键词： compiler optimization cache memories inspector/executor data reordering computation reordering

来源：评论

学校读者我要写书评

暂无评论

Ablego:: a function outlining and partial inlining framework

引用

SOFTWARE-PRACTICE & EXPERIENCE 2007年第5期37卷 465-491页

作者： Zhao, Peng Amaral, Jose Nelson Univ Alberta Dept Comp Sci Edmonton AB Canada IBM Corp Toronto Lab Markham ON Canada

Frequently invoked large functions are common in non-numeric applications. These large functions present challenges to modern compilers not only because they require more time and resources at compilation time, but also because they may prevent optimizations such as function inlining. Often large portions of the code in a hot function integral host are executed much less frequently than integral host itself. Partial inlining is a natural solution to the problems caused by including cold code segments that are seldom executed into hot functions that are frequently invoked. When applying partial inlining, a compiler outlines cold statements from a hot function integral host. After outlining,integral host becomes smaller and thus can be easily inlined. This paper presents Ablego, a framework for function outlining and partial inlining that includes several innovations: (1) an abstract-syntax-tree-based analysis and transformation to form cold regions for outlining;(2) a set of flexible heuristics to control the aggressiveness of function outlining;(3) several possible function outlining strategies;(4) explicit variable spilling, a new technique that overcomes negative side-effects of function outlining. With the proper strategy, partial inlining improves performance by up to 5.75%. A performance study also suggests that partial inlining's effect on enabling more aggressive inlining is limited. The performance improvement from partial inlining actually comes from better code placement and better code generation. Copyright (C) 2006 John Wiley & Sons, Ltd.

关键词： compiler optimization inlining partial inlining outlining function splitting code locality Itanium

来源：评论

学校读者我要写书评

暂无评论

Using integer linear programming for instruction scheduling and register allocation in multi-issue processors

引用

COMPUTERS & MATHEMATICS WITH APPLICATIONS 1997年第9期34卷 1-14页

作者： Chang, CM Chen, CM King, CT Department of Computer Science National Tsing Hua University Hsinchu Taiwan 300 R.O.C.

Instruction scheduling and register allocation are two very important optimizations in modern compilers for advanced processors. These two optimizations must be performed simultaneously in order to maximize the instruction-level parallelism and to fully utilize the registers [1]. In this paper, we solve register allocation and instruction scheduling simultaneously using integer linear programming (ILP). We have successfully worked out the ILP formulations for the problem with and without register spilling. Two kinds of optimizations are considered: (1) fix the number of free registers and then solve the minimum number of cycles to execute the instructions, or (2) fix the maximum execution cycles for the instructions and solve the minimum number of registers needed. Besides being theoretically interesting, our solution serves as a reference point for other heuristic solutions. The formulations are also applicable to high-level synthesis of ASICs and designs for embedded processors. In these application domains, the code quality is more important than the compilation time.

关键词： integer linear programming compiler optimization instruction scheduling register allocation processor architecture

来源：评论

学校读者我要写书评

暂无评论

A computational study of heuristic and exact techniques for superblock instruction scheduling

引用

JOURNAL OF SCHEDULING 2012年第6期15卷 743-756页

作者： Chase, Michael Malik, Abid M. Russell, Tyrel Oldford, R. Wayne van Beek, Peter Univ Waterloo Cheriton Sch Comp Sci Waterloo ON N2L 3G1 Canada Univ Waterloo Dept Stat & Actuarial Sci Waterloo ON N2L 3G1 Canada

compilers perform instruction scheduling to improve the performance of code on modern computer architectures. Superblocks-a straight-line sequence of code with a single entry point and multiple possible exit points-are a commonly used scheduling region within compilers. Superblock scheduling is NP-complete, and is done suboptimally in production compilers using a greedy algorithm coupled with a heuristic. Recently, exact schedulers have also been proposed. In this paper, we perform an extensive computational study of heuristic and exact techniques for scheduling superblocks. Our study extends previous work in using a more realistic architectural model, in not assuming perfect profile information, and in systematically investigating the case where profile information is not available. Our experimental results show that heuristics can be brittle and what looks promising under idealized (but unrealistic) conditions may not be robust in practice. As well, for the case where profile information is not available, some methods clearly dominate. Notably, a much inferior method is deployed in at least one existing compiler.

关键词： Superblock scheduling Instruction scheduling compiler optimization Profile-directed optimization

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：