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

generic Functional Parallel Algorithms: Scan and FFT

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

作者： Elliott, Conal Target Minneapolis MN 55403 USA

Parallel programming, whether imperative or functional, has long focused on arrays as the central data type. Meanwhile, typed functional programming has explored a variety of data types, including lists and various forms of trees. generic functional programming decomposes these data types into a small set of fundamental building blocks: sum, product, composition, and their associated identities. Definitions over these few fundamental type constructions then automatically assemble into algorithms for an infinite variety of data types-some familiar and some new. This paper presents generic functional formulations for two important and well-known classes of parallel algorithms: parallel scan (generalized prefix sum) and fast Fourier transform (FFT). Notably, arrays play no role in these formulations. Consequent benefits include a simpler and more compositional style, much use of common algebraic patterns and freedom from possibility of run-time indexing errors. The functional generic style also clearly reveals deep commonality among what otherwise appear to be quite different algorithms. Instantiating the generic formulations, two well-known algorithms for each of parallel scan and FFT naturally emerge, as well as two possibly new algorithms.

关键词： generic programming parallel prefix computation fast Fourier transform

来源：评论

学校读者我要写书评

暂无评论

Algebraic Specialization of generic Functions for Recursive Types

引用

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE 2011年第5期229卷 57-74页

作者： Cunha, Alcino Pacheco, Hugo Univ Minho Dep Informat Ctr Ciencias Tecnol Computac Campus Gualta P-4710057 Braga Portugal

Defining functions over large, possibly recursive, data structures usually involves a lot of boilerplate. This code simply traverses non-interesting parts of the data, and rapidly becomes a maintainability problem. Many generic programming libraries have been proposed to address this issue. Most of them allow the user to specify the behavior just for the interesting bits of the structure, and provide traversal combinators to "scrap the boilerplate". The expressive power of these libraries usually comes at the cost of efficiency, since runtime checks are used to detect where to apply the type-specific behavior. In previous work we have developed an effective rewrite system for specialization and optimization of generic programs. In this paper we extend it to also cover recursive data types. The key idea is to specialize traversal combinators using well-known recursion patterns, such as folds or paramorphisms. These are ruled by a rich set of algebraic laws that enable aggressive optimizations. We present a type-safe encoding of this rewrite system in Haskell, based on recent language extensions such as type-indexed type families.

关键词： generic programming Recursion patterns Rewrite systems Specialization Type families

来源：评论

学校读者我要写书评

暂无评论

Software product line construction through modular concern composition

引用

WIRTSCHAFTSINFORMATIK 2007年第3期49卷 171-179页

作者： Kuttruff, Volker FZI Forschungszentrum Informat Bereich Software Engn D-76131 Karlsruhe Germany

In order to fulfil similar user requirements within a specific domain, one typically uses software product line engineering. In this article, we present an approach which allows a modular specification of concerns and their modular composition to construct software systems. The approach uses concepts from generic and aspect-oriented programming and adapts them to the requirements imposed by software product line engineering.

关键词： software product lines generative software engineering generic programming aspect-oriented programming

来源：评论

学校读者我要写书评

暂无评论

generic support of algorithmic and structural recursion for scientific computing

引用

INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND DISTRIBUTED SYSTEMS 2009年第6期24卷 479-503页

作者： Gottschling, Peter Wise, David S. Joshi, Adwait Tech Univ Dresden Inst Wissensch Rech D-01069 Dresden Germany Indiana Univ Dept Comp Sci Bloomington IN 47405 USA

Recursive algorithms, like quick-sort and recursive data structures, like trees, play a central role in programming. In the context of scientific computing, recursive algorithms and memory layouts are shown here to provide excellent cache and Translation Lookaside Buffer (TLB) locality independently of the platform. We show how, for the first time, generic programming and object-oriented programming allow us to abstract a multitude of dense-matrix memory layouts: from conventional rowmajor and column-major layouts over Z-and N-Morton orders to block-wise combinations of them. All are provided by a single class that is based on our new matrix abstraction. The algorithmic recursion is supported in generic fashion by classes modelling the new recursator, an analogue of the Standard Template Library iterator. Although this concept supports recursion in general, we focus again on matrix operations. Results are presented for matrix multiplication, on both conventional and tiled representations using both homogeneous and heterogeneous matrix representations. Reaching about 60% peak performance in portable C++ code establishes competitive performance without explicit prefetching and other platform-specific tuning. Comparisons with the manufacturers' libraries show superior locality. These new techniques are embedded in the Matrix Template Library, Version 4 (MTL4).

关键词： Matrix Template Library generic programming Morton-order dilated integers doppled integers

来源：评论

学校读者我要写书评

暂无评论

On the generic parallelisation of iterative solvers for the finite element method

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL SCIENCE AND ENGINEERING 2008年第1期4卷 56-69页

作者： Blatt, Markus Bastian, Peter Univ Stuttgart IPVS Universitatsstr 38 D-70569 Stuttgart Germany

The numerical solution of partial differential equations frequently requires solving large and sparse linear systems. When using the Finite Element Method these systems exhibit a natural block structure that is exploited for efficiency in the 'Iterative Solver Template Library' (ISTL). Based on existing sequential preconditioned iterative solvers we present an abstract parallelisation approach which clearly separates the parallelisation aspects from the data structures and solver algorithms by imposing an abstract consistency model onto the building blocks of the iterative solver components. This allows for supporting overlapping and non-overlapping domain decompositions as well as data parallel implementations of standard linear solvers.

关键词： iterative methods domain decomposition C++ generic programming parallel computing

来源：评论

学校读者我要写书评

暂无评论

Policies of System Level Pipeline Modeling

引用

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE 2009年第2期238卷 13-23页

作者： Harcourt, Ed St Lawrence Univ Dept Math Comp Sci & Stat Canton NY 13617 USA

Pipelining is a well understood and often used implementation technique for increasing the performance of a hardware system. We develop several SystemC/C++ modeling techniques that allow us to quickly model, simulate, and evaluate pipelines. We employ a small domain specific language (DSL) based on resource usage patterns that automates the drudgery of boilerplate code needed to configure connectivity in simulation models. The DSL is embedded directly in the host modeling language SystemC/C++. Additionally we develop several techniques for parameterizing a pipeline's behavior based on policies of function, communication, and timing (performance modeling).

关键词： pipeline system level design discrete-event simulation generic programming hardware modeling policies SystemC

来源：评论

学校读者我要写书评

暂无评论

The design of the Boost interval arithmetic library

引用

THEORETICAL COMPUTER SCIENCE 2006年第1期351卷 111-118页

作者： Brönnimann, H Melquiond, G Pion, S Polytech Univ CIS Brooklyn NY 11201 USA Ecole Normale Super Lyon F-69364 Lyon 07 France INRIA F-06902 Sophia Antipolis France

We present the design of the Boost interval arithmetic library, a C++ library designed to handle mathematical intervals efficiently and in a generic way. Interval computations are an essential tool for reliable computing. Increasingly a number of mathematical proofs have relied on global optimization problems solved using branch-and-bound algorithms with interval computations, it is therefore extremely important to have a mathematically correct implementation of interval arithmetic. Various implementations exist with diverse semantics. Our design is unique in that it uses policies to specify three independent variable behaviors: rounding, checking, and comparisons. As a result, with the proper policies, our interval library is able to emulate almost any of the specialized libraries available for interval arithmetic, without any loss of performance nor sacrificing the ease of use. This library is openly available at ***. (c) 2005 Elsevier B.V. All fights reserved.

关键词： interval arithmetic software library generic programming policy-based design robust computations floating-point filter

来源：评论

学校读者我要写书评

暂无评论

Introducing VAUCANSON

引用

THEORETICAL COMPUTER SCIENCE 2004年第1-2期328卷 77-96页

作者： Lombardy, S Régis-Gianas, Y Sakarovitch, J LTCI CNRS ENST UMR 5141 F-75634 Paris 13 France Univ Paris 07 LIAFA F-75251 Paris 05 France LRDE EPITA F-94276 Le Kremlin Bicetre France

This paper reports on a new software platform called VAUCANSON and dedicated to the computation with automata and transducers. Its main feature is the capacity of dealing with automata whose labels may belong to various algebraic structures. The paper successively describes the main features of the VAUCANSON platform, including the fact that the very rich data structure used to implement automata does not weigh too much on the performance, shows how VAUCANSON allows to program algorithms on automata in a way which is very close to the mathematical expression of the algorithm and finally explains the main choices of the programming design that enable to achieve both genericity and efficiency. (C) 2004 Elsevier B.V. All rights reserved.

关键词： automata implementation automata with multiplicity generic programming

来源：评论

学校读者我要写书评

暂无评论

generic Deriving of generic Traversals

引用

PROCEEDINGS OF THE ACM ON programming LANGUAGES-PACMPL 2018年第ICFP期2卷 1–30页

作者： Kiss, Csongor Pickering, Matthew Wu, Nicolas Imperial Coll London Dept Comp London England Univ Bristol Dept Comp Sci Bristol Avon England

Functional programmers have an established tradition of using traversals as a design pattern to work with recursive data structures. The technique is so prolific that a whole host of libraries have been designed to help in the task of automatically providing traversals by analysing the generic structure of data types. More recently, lenses have entered the functional scene and have proved themselves to be a simple and versatile mechanism for working with product types. They make it easy to focus on the salient parts of a data structure in a composable and reusable manner. This paper uses the combination of lenses and traversals to give rise to a library with unprecedented expressivity and flexibility for querying and modifying complex data structures. Furthermore, since lenses and traversals are based on the generic shape of data, this information is used to generate code that is as efficient as hand-optimised versions. The technique leverages the structure of data to produce generic abstractions that are then eliminated by the standard workhorses of modern functional compilers: miming and specialisation.

关键词： generic programming traversals lenses extensibility

来源：评论

学校读者我要写书评

暂无评论

Thriving in a Crowded and ChangingWorld: C++ 2006-2020

引用

PROCEEDINGS OF THE ACM ON programming LANGUAGES-PACMPL 2020年第HOPL期4卷 1–168页

作者： Stroustrup, Bjarne Morgan Stanley New York NY 10036 USA Columbia Univ New York NY 10027 USA

By 2006, C++ had been in widespread industrial use for 20 years. It contained parts that had survived unchanged since introduced into C in the early 1970s as well as features that were novel in the early 2000s. From 2006 to 2020, the C++ developer community grew from about 3 million to about 4.5 million. It was a period where new programming models emerged, hardware architectures evolved, new application domains gained massive importance, and quite a few well-financed and professionally marketed languages fought for dominance. How did C++ s an older language without serious commercial backing s manage to thrive in the face of all that? This paper focuses on the major changes to the ISO C++ standard for the 2011, 2014, 2017, and 2020 revisions. The standard library is about 3/4 of the C++20 standard, but this paper's primary focus is on language features and the programming techniques they support. The paper contains long lists of features documenting the growth of C++. Significant technical points are discussed and illustrated with short code fragments. In addition, it presents some failed proposals and the discussions that led to their failure. It offers a perspective on the bewildering flow of facts and features across the years. The emphasis is on the ideas, people, and processes that shaped the language. Themes include efforts to preserve the essence of C++ through evolutionary changes, to simplify its use, to improve support for generic programming, to better support compile-time programming, to extend support for concurrency and parallel programming, and to maintain stable support for decades' old code. The ISO C++ standard evolves through a consensus process. Inevitably, there is competition among proposals and clashes (usually polite ones) over direction, design philosophies, and principles. The committee is now larger and more active than ever, with as many as 250 people turning up to week-long meetings three times a year and many more taking part electroni

关键词： C++ programming language design and evolution standardization generic programming resource management concurrency and parallelism simplification of language use

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：