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

massively parallel computation in a heterogeneous regime

DISTRIBUTED COMPUTING 2025年 1-22页

作者： Fischer, Orr Horowitz, Adi Oshman, Rotem Bar Ilan Univ Dept Comp Sci Rehovot Israel Tel Aviv Univ Blavatnik Sch Comp Sci Tel Aviv Israel

massively-parallel graph algorithms have received extensive attention over the past decade, with research focusing on three memory regimes: the superlinear regime, the near-linear regime, and the sublinear regime. The sublinear regime is the most desirable in practice, but conditional hardness results point towards its limitations. In this work we study a heterogeneous model, where the memory of the machines varies in size. We focus mostly on the heterogeneous setting created by adding a single near-linear machine to the sublinear MPC regime, and show that even a single large machine suffices to circumvent most of the conditional hardness results for the sublinear regime: for graphs with n vertices and m edges, we give (a) an MST algorithm that runs in O(loglog(m/n)) rounds;(b) an algorithm that constructs an O(k)-spanner of size O(n(1+1/k)) in O(1) rounds;and (c) a maximal-matching algorithm that runs in O(root log(m/n)log log(m/n)) rounds. We also observe that the best known near-linear MPC algorithms for several other graph problems which are conjectured to be hard in the sublinear regime (minimum cut, maximal independent set, and vertex coloring) can easily be transformed to work in the heterogeneous MPC model with a single near-linear machine, while retaining their original round complexity in the near-linear regime. If the large machine is allowed to have superlinear memory, all of the problems above can be solved in O(1) rounds.

关键词： massively parallel computation Graph algorithms

来源：评论

学校读者我要写书评

暂无评论

massively parallel computation of large-scale spatial price equilibrium models with discriminatory ad valorem tariffs

引用

ANNALS OF OPERATIONS RESEARCH 1996年第0期68卷 281-300页

作者： Nagurney, A Nicholson, CF Bishop, PM UNIV MASSACHUSETTS SCH MANAGEMENT AMHERST MA 01003 USA CORNELL UNIV DEPT AGR RESOURCE & MANAGERIAL ECON ITHACA NY 14853 USA

In this paper, we develop a perfectly competitive spatial equilibrium model in price and quantity variables in the presence of discriminatory ad valorem tariffs, a widely used trade policy instrument. We derive the equilibrium conditions and formulate them as a variational inequality problem. An algorithm is then proposed for the computation of the equilibrium pattern and convergence results established. The algorithm resolves the problem into very simple subproblems, each of which can be solved simultaneously and in closed form. Finally, the algorithm is implemented on the massively parallel Thinking Machines CM-2 and CM-5 architectures, known as the Connection Machines, and numerical results presented.

关键词： spatial price equilibria discriminatory ad valorem tariffs variational inequalities massively parallel computation

来源：评论

学校读者我要写书评

暂无评论

massively parallel computation via Remote Memory Access 19

Massively Parallel Computation via Remote Memory Access

引用

31st ACM Symposium on parallelism in Algorithms and Architecturess (SPAA)

作者： Behnezhad, Soheil Dhulipala, Laxman Esfandiari, Hossein Lacki, Jakub Mirrokni, Vahab Schudy, Warren Univ Maryland College Pk MD 20742 USA CMU Pittsburgh PA USA Google New York NY USA

ISBN: (纸本)9781450361842

We introduce the Adaptive massively parallel computation (AMPC) model, which is an extension of the widely popular massively parallel computation (MPC) model. At a high level, the AMPC model strengthens the MPC model by storing all messages sent within a round in a distributed data store. In the following round all machines are provided with random read access to the data store, subject to the same constraints on the total amount of communication as in the MPC model. Our model is inspired by the previous empirical studies of distributed graph algorithms [9, 28] using MapReduce and a distributed hash table service [17]. This extension allows us to give new graph algorithms with much lower round complexities compared to the best known solutions in the MPC model. In particular, in the AMPC model we show how to solve maximal independent set in O(1) rounds, and connectivity/minimum spanning tree in O(log log(m/n) n) rounds, which is an exponential improvement upon the best known algorithms in the MPC model with sublinear space per machine. Our results imply that the 2-Cycle conjecture, the most popular hardness conjecture in the MPC model, does not hold in the AMPC model.

关键词： distributed algorithms graph algorithms massively parallel computation remote memory access

来源：评论

学校读者我要写书评

暂无评论

massively parallel computation in a Heterogeneous Regime 22

Massively Parallel Computation in a Heterogeneous Regime

引用

ACM Symposium on Principles of Distributed Computing (PODC)

作者： Fischer, Orr Horowitz, Adi Oshman, Rotem Tel Aviv Univ Blavatnik Sch Comp Sci Tel Aviv Israel

ISBN: (纸本)9781450392624

massively-parallel graph algorithms have received extensive attention over the past decade, with research focusing on three memory regimes: the superlinear regime, the near-linear regime, and the sublinear regime. The sublinear regime is the most desirable in practice, but conditional hardness results point towards its limitations. In this work we study a heterogeneous model, where the memory of the machines varies in size. We focus mostly on the heterogeneous setting created by adding a single near-linear machine to the sublinear MPC regime, and show that even a single large machine suffices to circumvent most of the conditional hardness results for the sublinear regime: for graphs with n vertices and m edges, we give (a) an MST algorithm that runs in.. (log log(m/n)) rounds;(b) an algorithm that constructs an O(k)-spanner of size O(n(1+1/k)) in O( 1) rounds;and (c) a maximal-matching algorithm that runs in O(root log(m/n) log log(m/n)) rounds. We also observe that the best known near-linear MPC algorithms for several other graph problems which are conjectured to be hard in the sublinear regime (minimum cut, maximal independent set, and vertex coloring) can easily be transformed to work in the heterogeneous MPC model with a single near-linear machine, while retaining their original round complexity in the near-linear regime. If the large machine is allowed to have superlinear memory, all of the problems above can be solved in O( 1) rounds.

关键词： massively parallel computation Heterogeneous Memory Regime

来源：评论

学校读者我要写书评

暂无评论

massively parallel computation of Matching and MIS in Sparse Graphs 19

Massively Parallel Computation of Matching and MIS in Sparse...

引用

38th ACM Symposium on Principles of Distributed Computing (PODC)

作者： Behnezhad, Soheil Brandt, Sebastian Derakhshan, Mahsa Fischer, Manuela Hajiaghayi, MohammadTaghi Karp, Richard M. Uitto, Jara Univ Maryland College Pk MD 20742 USA Swiss Fed Inst Technol Zurich Switzerland Univ Calif Berkeley Berkeley CA USA Univ Freiburg Freiburg Germany

ISBN: (纸本)9781450362177

The massively parallel computation (MPC) model serves as a common abstraction of many modern large-scale parallel computation frameworks and has recently gained a lot of importance, especially in the context of classic graph problems. In this work, we mainly consider maximal matching and maximal independent set problems in the MPC model. These problems are known to admit efficient MPC algorithms if the space available per machine is near-linear in the number n of nodes. This is not only often significantly more than what we can afford, but also allows for easy if not trivial solutions for sparse graphs-which are common in real-world large-scale graphs. We are, therefore, interested in the low-memory MPC model, where the space per machine is restricted to be strongly sublinear, that is, n(delta) for any constant 0 < delta < 1. We parametrize our algorithms by the arboricity lambda of the input graph. Our key ingredient is a degree reduction technique that reduces these problems in graphs with arboricity lambda to the corresponding problems in graphs with maximum degree poly(lambda, logn) in O(log(2) logn) rounds, giving rise to O(root log lambda . log log lambda + log(2) log n)-round algorithms. Our result is particularly interesting for graphs with poly logn arboricity as for such graphs, we get O(log(2) log n)-round algorithms. This covers most natural families of sparse graphs and almost exponentially improves over previous algorithms that all required log(Omega(1)) n rounds in this regime of MPC. Finally, our maximal matching algorithm can be employed to obtain a (1 + epsilon)-approximate maximum cardinality matching, a (2 + epsilon)-approximate maximum weighted matching, as well as a 2-approximate minimum vertex cover in essentially the same number of rounds.

关键词： sublinear memory arboricity maximal independent set matching massively parallel computation sparse graphs approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

massively-parallel computation OF SPATIAL PRICE EQUILIBRIUM PROBLEMS AS DYNAMICAL-SYSTEMS

引用

JOURNAL OF ECONOMIC DYNAMICS & CONTROL 1995年第1-2期19卷 3-37页

作者： NAGURNEY, A TAKAYAMA, T ZHANG, D UNIV WESTERN AUSTRALIA DEPT ECONNEDLANDSWA 6009AUSTRALIA UNIV MASSACHUSETTS DEPT IND ENGN & OPERAT RESAMHERSTMA 01003

In this paper we introduce a dynamical system for the formulation and computation of spatial price equilibrium problems in quantity variables. The set of stationary points of the system corresponds to the set of solutions of the variational inequality problem governing the problem. We propose the Euler-type method for the computation of the equilibrium pattern and provide convergence results. We then demonstrate that the algorithm can be implemented on a massively parallel architecture and illustrate its performance on the Thinking Machine's CM-2 architecture. This research represents the first implementation of a massively parallel approach for the computation of either dynamical systems or variational inequality problems arising in economics.

关键词： SPATIAL PRICE EQUILIBRIUM DYNAMICAL SYSTEMS VARIATIONAL INEQUALITIES massively parallel computation

来源：评论

学校读者我要写书评

暂无评论

Component stability in low-space massively parallel computation

引用

DISTRIBUTED COMPUTING 2024年第1期37卷 35-64页

作者： Czumaj, Artur Davies-Peck, Peter Parter, Merav Univ Warwick Comp Sci Coventry CV4 7AL England Univ Warwick Ctr Discrete Math & Applicat DIMAP Coventry CV4 7AL England Univ Durham Comp Sci Durham DH1 3LE England Weizmann Inst Sci Comp Sci IL-7610001 Rehovot Israel

In this paper, we study the power and limitations of component-stable algorithms in the low-space model of massively parallel computation (MPC). Recently Ghaffari, Kuhn and Uitto (FOCS 2019) introduced the class of component-stable low-space MPC algorithms, which are, informally, those algorithms for which the outputs reported by the nodes in different connected components are required to be independent. This very natural notion was introduced to capture most (if not all) of the known efficient MPC algorithms to date, and it was the first general class of MPC algorithms for which one can show non-trivial conditional lower bounds. In this paper we enhance the framework of component-stable algorithms and investigate its effect on the complexity of randomized and deterministic low-space MPC. Our key contributions include: 1. We revise and formalize the lifting approach of Ghaffari, Kuhn and Uitto. This requires a very delicate amendment of the notion of component stability, which allows us to fill in gaps in the earlier arguments. 2. We also extend the framework to obtain conditional lower bounds for deterministic algorithms and fine-grained lower bounds that depend on the maximum degree Delta\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta $$\end{document}. 3. We demonstrate a collection of natural graph problems for which deterministic component-unstable algorithms break the conditional lower bound obtained for component-stable algorithms. This implies that, in the context of deterministic algorithms, component-stable algorithms are conditionally weaker than the component-unstable ones. 4. We also show that the restriction to component-stable algorithms has an impact in the randomized setting. We present a natural problem which can be solved in O(1) rounds by a component-unstable MP

关键词： Component stability massively parallel computation Lower bounds

来源：评论

学校读者我要写书评

暂无评论

Graph Sparsification for Derandomizing massively parallel computation with Low Space

引用

ACM TRANSACTIONS ON ALGORITHMS 2021年第2期17卷 1–27页

作者： Czumaj, Artur Davies, Peter Parter, Merav Univ Warwick Comp Sci Dept Coventry CV4 7AL W Midlands England Univ Warwick Ctr Discrete Math & Its Applicat DIMAP Coventry CV4 7AL W Midlands England IST Austria A-3400 Klosterneuburg Austria Weizmann Inst Sci IL-7610001 Rehovot Israel

The massively parallel computation (MPC) model is an emerging model that distills core aspects of distributed and parallel computation, developed as a tool to solve combinatorial (typically graph) problems in systems of many machines with limited space. Recent work has focused on the regime in which machines have sublinear (in n, the number of nodes in the input graph) space, with randomized algorithms presented for the fundamental problems of Maximal Matching and Maximal Independent Set. However, there have been no prior corresponding deterministic algorithms. A major challenge underlying the sublinear space setting is that the local space of each machine might be too small to store all edges incident to a single node. This poses a considerable obstacle compared to classical models in which each node is assumed to know and have easy access to its incident edges. To overcome this barrier, we introduce a new graph sparsification technique that deterministically computes a low-degree subgraph, with the additional property that solving the problem on this subgraph provides significant progress towards solving the problem for the original input graph. Using this framework to derandomize the well-known algorithm of Luby [SICOMP'86], we obtain O(log Delta + log logn)-round deterministic MPC algorithms for solving the problems of Maximal Matching and Maximal Independent Set with O(n(epsilon)) space on each machine for any constant epsilon > 0. These algorithms also run in O(log Delta) rounds in the closely related model of CONGESTED CLIQUE, improving upon the state-of-the-art bound of O(log(2) Delta) rounds by Censor-Hillel et al. [DISC'17].

关键词： massively parallel computation sparsification derandomization maximal independent set maximal matching

来源：评论

学校读者我要写书评

暂无评论

Three pillars for achieving quantum mechanical molecular dynamics simulations of huge systems: Divide-and-conquer, density-functional tight-binding, and massively parallel computation

引用

JOURNAL OF computationAL CHEMISTRY 2016年第21期37卷 1983-1992页

作者： Nishizawa, Hiroaki Nishimura, Yoshifumi Kobayashi, Masato Irle, Stephan Nakai, Hiromi Inst Mol Sci Dept Theoret & Computat Mol Sci Okazaki Aichi 4448585 Japan Waseda Univ Res Inst Sci & Engn Tokyo 1698555 Japan Hokkaido Univ Dept Chem Fac Sci Sapporo Hokkaido 0600810 Japan Kyoto Univ ESICB Kyoto 6158520 Japan Japan Sci & Technol Agcy PRESTO Kawaguchi Saitama 3320012 Japan Nagoya Univ Dept Chem Grad Sch Sci Nagoya Aichi 4648602 Japan Nagoya Univ Inst Transformat Biomol WPI ITbM Nagoya Aichi 4648602 Japan Waseda Univ Sch Adv Sci & Engn Dept Chem & Biochem Tokyo 1698555 Japan Japan Sci & Technol Agcy CREST Kawaguchi Saitama 3320012 Japan

The linear-scaling divide-and-conquer (DC) quantum chemical methodology is applied to the density-functional tight-binding (DFTB) theory to develop a massively parallel program that achieves on-the-fly molecular reaction dynamics simulations of huge systems from scratch. The functions to perform large scale geometry optimization and molecular dynamics with DC-DFTB potential energy surface are implemented to the program called DC-DFTB-K. A novel interpolation-based algorithm is developed for parallelizing the determination of the Fermi level in the DC method. The performance of the DC-DFTB-K program is assessed using a laboratory computer and the K computer. Numerical tests show the high efficiency of the DC-DFTB-K program, a single-point energy gradient calculation of a one-million-atom system is completed within 60 s using 7290 nodes of the K computer. (c) 2016 Wiley Periodicals, Inc.

关键词： quantum mechanical molecular dynamics linear-scaling divide-and-conquer method density-functional tight-binding method massively parallel computation

来源：评论

学校读者我要写书评

暂无评论

Algorithms for a Topology-aware massively parallel computation Model 21

Algorithms for a Topology-aware Massively Parallel Computati...

引用

40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS)

作者： Hu, Xiao Koutris, Paraschos Blanas, Spyros Duke Univ Durham NC 27706 USA UW Madison Madison WI USA Ohio State Univ Columbus OH 43210 USA

ISBN: (纸本)9781450383813

Most of the prior work in massively parallel data processing assumes homogeneity, i.e., every computing unit has the same computational capability and can communicate with every other unit with the same latency and bandwidth. However, this strong assumption of a uniform topology rarely holds in practical settings, where computing units are connected through complex networks. To address this issue, Blanas et al. [9] recently proposed a topology-aware massively parallel computation model that integrates the network structure and heterogeneity in the modeling cost. The network is modeled as a directed graph, where each edge is associated with a cost function that depends on the data transferred between the two endpoints. The computation proceeds in synchronous rounds and the cost of each round is measured as the maximum cost over all the edges in the network. In this work, we take the first step into investigating three fundamental data processing tasks in this topology-aware parallel model: set intersection, cartesian product, and sorting. We focus on network topologies that are tree topologies, and present both lower bounds as well as (asymptotically) matching upper bounds. Instead of assuming a worst-case distribution as in previous results, the optimality of our algorithms is with respect to the initial data distribution among the network nodes. Apart from the theoretical optimality of our results, our protocols are simple, use a constant number of rounds, and we believe can be implemented in practical settings as well.

关键词： query processing massively parallel computation topology-aware

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：