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

divide-and-conquer parallel programming with Minimally Synchronous Parallel ML

7th International Conference on Parallel Processing and Applied Mathematics

作者： Benheddi, Radia Loulergue, Frederic Univ Orleans LIFO F-45067 Orleans France

ISBN: (纸本)9783540681052

Minimally Synchronous Parallel ML (MSPML) is a functional parallel programming language. It is based on a small number of primitives on a parallel data structure. MSPML programs are written like usual sequential ML program and use this small set of functions. MSPML is deterministic and deadlock free. The execution time of the programs can be estimated. divide-and-conquer is a natural way of expressing parallel algorithms. MSPML is a flat language: it is not possible to split the parallel machine in order to implement divide-and-conquer parallel algorithms. This paper presents an extension of MSPML to deal with this kind of algorithms: a parallel composition primitive.

关键词： functional programming divide-and-conquer parallelism parallel composition

来源：评论

学校读者我要写书评

暂无评论

Automatic inversion generates divide-and-conquer parallel programs 07

Automatic inversion generates divide-and-conquer parallel pr...

引用

Conference on Programming Language Design and Implementation

作者： Morita, Kazutaka Morihata, Akimasa Matsuzaki, Kiminori Hu, Zhenjiang Takeichi, Masato Univ Tokyo Grad Sch Informat Sci & Technol Tokyo Japan

ISBN: (纸本)9781595936332

divide-and-conquer algorithms are suitable for modern parallel machines, tending to have large amounts of inherent parallelism and working well with caches and deep memory hierarchies. Among others, list homomorphisms are a class of recursive functions on lists, which match very well with the divide-and-conquer paradigm. However, direct programming with list homomorphisms is a challenge for many programmers. In this paper, we propose and implement a novel system that can automatically derive cost-optimal list homomorphisms from a pair of sequential programs, based on the third homomorphism theorem. Our idea is to reduce extraction of list homomorphisms to derivation of weak right inverses. We show that a weak right inverse always exists and can be automatically generated from a wide class of sequential programs. We demonstrate our system with several nontrivial examples, including the maximum prefix sum problem, the prefix sum computation, the maximum segment sum problem, and the line-of-sight problem. The experimental results show practical efficiency of our automatic parallelization algorithm and good speedups of the generated parallel programs.

关键词： algorithms design languages divide-and-conquer parallelism inversion program transformation third homomorphism theorem

来源：评论

学校读者我要写书评

暂无评论

Counting cliques in parallel without a cluster: Engineering a fork/join algorithm for shared-memory platforms

引用

INFORMATION SCIENCES 2019年 496卷 553-571页

作者： Coppa, Emilio Finocchi, Irene Garcia, Renan Leon Sapienza Univ Rome Comp Sci Dept Rome Italy

In this paper we develop simple and fast multicore parallel algorithms for counting the number of k-cliques in large undirected graphs, for any small constant k >= 4. Clique counting is an important problem in a variety of network analytics applications. Differently from existing solutions, which mainly target distributed memory settings (e.g., MapReduce), our algorithms work on off-the-shelf shared-memory multicore platforms. We assess the effectiveness of our approach through an extensive experimental analysis on a variety of real-world graphs, considering different clique sizes and scalability on different numbers of cores. The experimental results show that our parallel algorithms largely outperform the running times of highly optimized sequential solutions and gracefully scale to non-trivial values of k even on medium/large graphs. For instance, computing hundreds of billions of cliques for rather demanding Web graphs and social networks requires about 15 min on a 32-core machine. As a by-product of our experimental analysis, we also compute the exact number of k-cliques with at most 20 nodes in many real-world networks from the SNAP repository. (C) 2018 Elsevier Inc. All rights reserved.

关键词： Clique counting divide-and-conquer parallelism Fork/join Subgraph enumeration

来源：评论

学校读者我要写书评

暂无评论

Automatic inversion generates divide-and-conquer parallel programs

引用

ACM SIGPLAN NOTICES 2007年第6期42卷 146-155页

作者： Morita, Kazutaka Morihata, Akimasa Matsuzaki, Kiminori Hu, Zhenjiang Takeichi, Masato Univ Tokyo Grad Sch Informat Sci & Technol Tokyo Japan

关键词： algorithms design languages divide-and-conquer parallelism inversion program transformation third homomorphism theorem

来源：评论

学校读者我要写书评

暂无评论

A Short Cut to Parallelization Theorems 13

A Short Cut to Parallelization Theorems

引用

18th ACM SIGPLAN International Conference on Functional Programming

作者： Morihata, Akimasa Tohoku Univ Sendai Miyagi 980 Japan

ISBN: (纸本)9781450323260

The third list-homomorphism theorem states that if a function is both foldr and foldl, it has a divide-and-conquer parallel implementation as well. In this paper, we develop a theory for obtaining such parallelization theorems. The key is a new proof of the third list-homomorphism theorem based on shortcut deforestation. The proof implies that there exists a divide-and-conquer parallel program of the form of h (x 'merge' y) = h(1) x circle dot h(2) y, where h is the subject of parallelization, merge is the operation of integrating independent substructures, h1 and h2 are computations applied to substructures, possibly in parallel, and circle dot merges the results calculated for substructures, if (i) h can be specified by two certain forms of iterative programs, and (ii) merge can be implemented by a function of a certain polymorphic type. Therefore, when requirement (ii) is fulfilled, h has a divide-and-conquer implementation if h has two certain forms of implementations. We show that our approach is applicable to structure-consuming operations by catamorphisms (folds), structure-generating operations by anamorphisms (unfolds), and their generalizations called hylomorphisms.

关键词： divide-and-conquer parallelism Shortcut Deforestation Third List-homomorphism Theorem

来源：评论

学校读者我要写书评

暂无评论

A Short Cut to Parallelization Theorems

引用

ACM SIGPLAN NOTICES 2013年第9期48卷 245-256页

作者： Morihata, Akimasa Tohoku Univ Sendai Miyagi 980 Japan

关键词： divide-and-conquer parallelism Shortcut Deforestation Third List-homomorphism Theorem

来源：评论

学校读者我要写书评

暂无评论

Balanced Trees Inhabiting Functional Parallel Programming 11

Balanced Trees Inhabiting Functional Parallel Programming

引用

16th ACM SIGPLAN International Conference on Functional Programming (ICFP 11)

作者： Morihata, Akimasa Matsuzaki, Kiminori Tohoku Univ Sendai Miyagi 980 Japan Kochi Univ Technol Kochi Japan

ISBN: (纸本)9781450308656

divide-and-conquer is an important technique in parallel programming. However, algebraic data structures do not fit divide-and-conquer parallelism. For example, the usual pointer-based implementation of lists cannot efficiently be divided at their middle, which prevents us from developing list-iterating divide-and-conquer parallel programs. Tree-iterating programs possibly face a similar problem, because trees might be ill-balanced and list-like shapes. This paper examines parallel programming based on balanced trees: we consider balanced-tree structures and develop recursive functions on them. By virtue of their balancing nature, either bottom-up or top-down recursive functions exploit divide-and-conquer parallelism. Our main contribution is to demonstrate the promise of this approach. We propose a way of systematically developing balanced trees from parallel algorithms, and then, we show that efficient parallel programs on them can be developed by equational reasoning powered by Reynolds' relational parametricity. We consider functions that operate either lists or binary trees, and show that our methods can uniformly deal with both cases. The developed parallel programs are purely functional, correct by construction, and sometimes even simpler than known algorithms.

关键词： Theory Algorithms Balanced Tree divide-and-conquer parallelism Equational Reasoning Parametric Polymorphism

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：