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

staged Abstract Interpreters Fast and Modular Whole-Program Analysis via Meta-programming

PROCEEDINGS OF THE ACM ON programming LANGUAGES-PACMPL 2019年第OOPSLA期3卷 1–32页

作者： Wei, Guannan Chen, Yuxuan Rompf, Tiark Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

It is well known that a staged interpreter is a compiler: specializing an interpreter to a given program produces an equivalent executable that runs faster. This connection is known as the first Futamura projection. It is even more widely known that an abstract interpreter is a program analyzer: tweaking an interpreter to run on abstract domains produces a sound static analysis. What happens when we combine these two ideas, and apply specialization to an abstract interpreter? In this paper, we present a unifying framework that naturally extends the first Futamura projection from concrete interpreters to abstract interpreters. Our approach derives a sound staged abstract interpreter based on a generic interpreter with type-level binding-time abstractions and monadic abstractions. By using different instantiations of these abstractions, the generic interpreter can flexibly behave in one of four modes: as an unstaged concrete interpreter, a staged concrete interpreter, an unstaged abstract interpreter, or a staged abstract interpreter. As an example of abstraction without regret, the overhead of these abstraction layers is eliminated in the generated code after staging. We show that staging abstract interpreters is practical and useful to optimize static analysis, all while requiring less engineering effort and without compromising soundness. We conduct three case studies, including a comparison with Boucher and Feeley's abstract compilation, applications to various control-flow analyses, and a demonstration for modular analysis. We also empirically evaluate the effect of staging on the execution time. The experiment shows an order of magnitude speedup with staging for control-flow analyses.

关键词： multi-stage programming abstract interpreters control-flow analysis

来源：评论

学校读者我要写书评

暂无评论

CONVEX INFINITE HORIZON PROGRAMS

引用

MATHEMATICAL programming 1983年第1期25卷 64-82页

作者： GRINOLD, R School of Business Administration University of California 94720 Berkeley CA USA

We establish conditions under which a sequence of finite horizon convex programs monotonically increases in value to the value of the infinite program; a subsequence of optimal solutions converges to the optimal solution of the infinite problem. If the conditions we impose fail, then (roughtly) the optimal value of the infinite horizon problem is an improper convex function. Under more restrictive conditions we establish the necessary and sufficient conditions for optimality. This constructive procedure gives us a way to solve the infinite (long range) problem by solving a finite (short range) problem. It appears to work well in practice.

关键词： Convex programming End Effects Approximation to Optimality multi-stage programming

来源：评论

学校读者我要写书评

暂无评论

staged Generic programming

引用

PROCEEDINGS OF THE ACM ON programming LANGUAGES-PACMPL 2017年第ICFP期1卷 1-29页

作者： Yallop, Jeremy Univ Cambridge Cambridge England

Generic programming libraries such as Scrap Your Boilerplate eliminate the need to write repetitive code, but typically introduce significant performance overheads. This leaves programmers with the regrettable choice between writing succinct but slow programs and writing tedious but efficient programs. Applying structured multi-stage programming techniques transforms Scrap Your Boilerplate from an inefficient library into a typed optimising code generator, bringing its performance in line with hand-written code, and so combining high-level programming with uncompromised performance.

关键词： multi-stage programming generic programming metaprogramming partial evaluation

来源：评论

学校读者我要写书评

暂无评论

Mat2Stencil: A Modular Matrix-Based DSL for Explicit and Implicit Matrix-Free PDE Solvers on Structured Grid

引用

PROCEEDINGS OF THE ACM ON programming LANGUAGES-PACMPL 2023年第OOPSLA期7卷 686–715页

作者： Cao, Huanqi Tang, Shizhi Zhu, Qianchao Yu, Bowen Chen, Wenguang Tsinghua Univ Beijing Peoples R China Peking Univ Beijing Peoples R China Pengcheng Lab Shenzhen Peoples R China

Partial differential equation (PDE) solvers are extensively utilized across numerous scientific and engineering fields. However, achieving high performance and scalability often necessitates intricate and low-level programming, particularly when leveraging deterministic sparsity patterns in structured grids. In this paper, we propose an innovative domain-specific language (DSL), Mat2Stencil, with its compiler, for PDE solvers on structured grids. Mat2Stencil introduces a structured sparse matrix abstraction, facilitating modular, flexible, and easy-to-use expression of solvers across a broad spectrum, encompassing components such as Jacobi or Gauss-Seidel preconditioners, incomplete LU or Cholesky decompositions, and multigrid methods built upon them. Our DSL compiler subsequently generates matrix-free code consisting of generalized stencils through multi-stage programming. The code allows spatial loop-carried dependence in the form of quasi-affine loops, in addition to the Jacobi-style stencil's embarrassingly parallel on spatial dimensions. We further propose a novel automatic parallelization technique for the spatially dependent loops, which offers a compile-time deterministic task partitioning for threading, calculates necessary inter-thread synchronization automatically, and generates an efficient multi-threaded implementation with fine-grained synchronization. Implementing 4 benchmarking programs, 3 of them being the pseudo-applications in NAS Parallel Benchmarks with 6.3% lines of code and 1 being matrix-free High Performance Conjugate Gradients with 16.4% lines of code, we achieve up to 1.67x and on average 1.03x performance compared to manual implementations.

关键词： domain-specific language multi-stage programming compiler finite difference method stencil structured grid polyhedral compilation performance optimization

来源：评论

学校读者我要写书评

暂无评论

Forge: Generating a High Performance DSL Implementation from a Declarative Specification 13

Forge: Generating a High Performance DSL Implementation from...

引用

12th International Conference on Generative programming: Concepts and Experiences

作者： Sujeeth, Arvind K. Gibbons, Austin Brown, Kevin J. Lee, HyoukJoong Rompf, Tiark Odersky, Martin Olukotun, Kunle Stanford Univ Stanford CA 94305 USA Oracle Labs Columbus OH USA Ecole Polytech Fed Lausanne Lausanne Switzerland

ISBN: (纸本)9781450323734

Domain-specific languages provide a promising path to automatically compile high-level code to parallel, heterogeneous, and distributed hardware. However, in practice high performance DSLs still require considerable software expertise to develop and force users into tool-chains that hinder prototyping and debugging. To address these problems, we present Forge, a new meta DSL for declaratively specifying high performance embedded DSLs. Forge provides DSL authors with high-level abstractions (e.g., data structures, parallel patterns, effects) for specifying their DSL in a way that permits high performance. From this high-level specification, Forge automatically generates both a naive Scala library implementation of the DSL and a high performance version using the Delite DSL framework. Users of a Forge-generated DSL can prototype their application using the library version, and then switch to the Delite version to run on multicore CPUs, GPUs, and clusters without changing the application code. Forge-generated Delite DSLs perform within 2x of hand-optimized C++ and up to 40x better than Spark, an alternative high-level distributed programming environment. Compared to a manually implemented Delite DSL, Forge provides a factor of 3-6x reduction in lines of code and does not sacrifice any performance. Furthermore, Forge specifications can be generated from existing Scala libraries, are easy to maintain, shield DSL developers from changes in the Delite framework, and enable DSLs to be retargeted to other frameworks transparently.

关键词： Code Generation multi-stage programming Domain-Specific Languages Parallel programming

来源：评论

学校读者我要写书评

暂无评论

Tagless staged interpreters for typed languages

Tagless staged interpreters for typed languages

引用

7th International Conference on Functional programming

作者： Pasalic, E Taha, W Sheard, T Oregon Hlth & Sci Univ OGI Sch Sci & Engn Portland OR 97201 USA Rice Univ Dept Comp Sci Houston TX 77251 USA

multi-stage programming languages provide a convenient notation for explicitly staging programs. Staging a definitional interpreter for a domain specific language is one way of deriving an implementation that is both readable and efficient. In an untyped setting, staging an interpreter "removes a complete layer of interpretive overhead", just like partial evaluation. In a typed setting however, Hindley-Milner type systems do not allow us to exploit typing information in the language being interpreted. In practice, this can mean a slowdown cost by a factor of three or more. Previously, both type specialization and tag elimination were applied to this problem. In this paper we propose an alternative approach, namely, expressing the definitional interpreter in a dependently typed programming language. We report on our experience with the issues that arise in writing such an interpreter and in designing such a language. To demonstrate the soundness of combining staging and dependent types in a general sense, we formalize our language (called Meta-D) and prove its type safety. To formalize Meta-D, we extend Shao, Saha, Trifonov and Papaspyrou's lambdaH language to a multi-level setting. Building on X,H allows us to demonstrate type safety in a setting where the type language contains all the calculus of inductive constructions, but without having to repeat the work needed for establishing the soundness of that system.

关键词： languages performance multi-stage programming definitional interpreters calculus of constructions domain-specific languages

来源：评论

学校读者我要写书评

暂无评论

Lightweight Modular Staging: A Pragmatic Approach to Runtime Code Generation and Compiled DSLs 10

Lightweight Modular Staging: A Pragmatic Approach to Runtime...

引用

9th International Conference on Generative programming and Component Engineering

作者： Rompf, Tiark Odersky, Martin Ecole Polytech Fed Lausanne CH-1015 Lausanne Switzerland

ISBN: (纸本)9781450301541

Software engineering demands generality and abstraction, performance demands specialization and concretization. Generative programming can provide both, but developing high-quality program generators takes a large effort, even if a multi-stage programming language is used. We present lightweight modular staging, a library-based multi-stage programming approach that breaks with the tradition of syntactic quasi-quotation and instead uses only types to distinguish between binding times. Through extensive use of component technology, lightweight modular staging makes an optimizing compiler framework available at the library level, allowing programmers to tightly integrate domain-specific abstractions and optimizations into the generation process. We argue that lightweight modular staging enables a form of language virtualization, i.e. allows to go from a pure-library embedded language to one that is practically equivalent to a stand-alone implementation with only modest effort.

关键词： Design Languages Code Generation multi-stage programming Domain-specific languages Language Virtualization

来源：评论

学校读者我要写书评

暂无评论

Staging Generic programming 16

Staging Generic Programming

引用

ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation (PEPM)

作者： Yallop, Jeremy Univ Cambridge Cambridge CB2 1TN England

ISBN: (纸本)9781450340977

Generic programming libraries such as Scrap Your Boilerplate eliminate the need to write repetitive code, but typically introduce significant performance overheads. This leaves programmers with the unfortunate choice of writing succinct but slow programs or writing tedious but efficient programs. We show how to systematically transform an implementation of the Scrap Your Boilerplate library in the multi-stage programming language MetaOCaml to eliminate the overhead, making it possible to combine the benefits of high-level abstract programming with the efficiency of low-level code.

关键词： multi-stage programming generic programming ML MetaOCaml partial evaluation

来源：评论

学校读者我要写书评

暂无评论

Combinators for Impure yet Hygienic Code Generation 14

Combinators for Impure yet Hygienic Code Generation

引用

ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation (PEPM)

作者： Kameyama, Yukiyoshi Kiselyov, Oleg Shan, Chung-chieh Univ Tsukuba Tsukuba Ibaraki Japan Indiana Univ Bloomington IN 47405 USA

ISBN: (纸本)9781450326193

Code generation is the leading approach to making high-performance software reusable. Effects are indispensable in code generators, whether to report failures or to insert let-statements and if guards. Extensive painful experience shows that unrestricted effects interact with generated binders in undesirable ways to produce unexpectedly unbound variables, or worse, unexpectedly bound ones. These subtleties hinder domain experts in using and extending the generator. A pressing problem is thus to express the desired effects while regulating them so that the generated code is correct, or at least correctly scoped, by construction. We present a code-combinator framework that lets us express arbitrary monadic effects, including mutable references and delimited control, that move open code across generated binders. The static types of our generator expressions not only ensure that a well-typed generator produces well-typed and well-scoped code. They also express the lexical scopes of generated binders and prevent mixing up variables with different scopes. For the first time ever we demonstrate statically safe and well-scoped loop exchange and constant factoring from arbitrarily nested loops. Our framework is implemented as a Haskell library that embeds an extensible typed higher-order domain-specific language. It may be regarded as 'staged Haskell.' To become practical, the library relies on higher-order abstract syntax and polymorphism over generated type environments, and is written in the mature language.

关键词： multi-stage programming mutable state and control effects binders CPS higher-order abstract syntax lexical scope

来源：评论

学校读者我要写书评

暂无评论

Generate and Offshore: Type-Safe and Modular Code Generation for Low-Level Optimization 4

Generate and Offshore: Type-Safe and Modular Code Generation...

引用

4th ACM SIGPLAN Workshop on Functional High-Performance Computing (FHPC)

作者： Takashima, Naoki Sakamoto, Hiroki Kameyama, Yukiyoshi Univ Tsukuba Tsukuba Ibaraki Japan

ISBN: (纸本)9781450338073

We present the Asuna system which supports implicitly heterogeneous multi-stage programming based on MetaOCaml, a multi-stage extension of OCaml. Our system allows programmers to write code generators in a high-level language, and generated code can be translated to a program in low-level languages such as C and LLVM. The high-level code generators can make use of all the features of MetaOCaml such as algebraic data types and higher-order functions while the generated code may include low-level CPU instructions such as vector (SIMD) operations. One can write programs in a modular and type-safe programming style and can directly represent low-level optimizations. Asuna is a multi-target system, that means a single code generator can generate code in C and LLVM, without changing the generator. The translation by Asuna preserves typing and all generated code is guaranteed to be well typed and well scoped. In this paper, we explain the practical aspect of Asuna, using examples taken from high-performance computing.

关键词： Code Generation multi-stage programming Type safety Low-level optimization High-performance computing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：