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

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年第2期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 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 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 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

来源：评论

学校读者我要写书评

暂无评论

Unconditional Lower Bounds for Adaptive massively parallel computation 20

Unconditional Lower Bounds for Adaptive Massively Parallel C...

引用

32nd ACM Symposium on parallelism in Algorithms and Architectures (SPAA)

作者： Charikar, Moses Ma, Weiyun Tan, Li-Yang Stanford Univ Stanford CA 94305 USA

ISBN: (纸本)9781450369350

We consider unconditional lower bounds in the Adaptive massively parallel computation (AMPC) model introduced by Behnezhad et al. (SPAA 19), which is an adaptive variant of the massively parallel computation (MPC) model. Our first contribution is an optimal lower bound on the round complexity of distinguishing whether an input graph is a cycle of length n or two cycles of length n/2. This problem, 1v2-Cycle, has emerged as a central problem in the study of modern massively parallel computation. We prove that any AMPC algorithm for the 1v2-Cycle problem with I/O capacity O(n(epsilon)) per machine requires Omega(1/epsilon) rounds, matching the upper bound of Behnezhad et al. More generally, we develop an abstract framework for proving lower bounds in the AMPC model using techniques from Boolean function complexity. Our framework extends the polynomial method of Roughgarden et al. (JACM 18) for the MPC model in two dimensions: Adaptivity, where machines can write to and adaptively read from shared memory throughout the execution of the computation. Promise problems, where the algorithm only has to succeed on certain inputs. These inputs may have special structure that is of particular interest, or they may be representative of hard instances of the overall problem.

关键词： massively parallel computation adaptive massively parallel computation round complexity lower bounds one cycle vs. two cycles problem

来源：评论

学校读者我要写书评

暂无评论

On the Hardness of massively parallel computation 20

On the Hardness of Massively Parallel Computation

引用

32nd ACM Symposium on parallelism in Algorithms and Architectures (SPAA)

作者： Chung, Kai-Min Ho, Kuan-Yi Sun, Xiaorui Acad Sinica Taipei Taiwan Univ Texas Austin Austin TX 78712 USA Univ Illinois Chicago IL 60680 USA

ISBN: (纸本)9781450369350

We investigate whether there are inherent limits of parallelization in the (randomized) massively parallel computation (MPC) model by comparing it with the (sequential) RAM model. As our main result, we show the existence of hard functions that are essentially not parallelizable in the MPC model. Based on the widely-used random oracle methodology in cryptography with a cryptographic hash function h : {0, 1}(n) -> {0, 1}(n) computable in time t(h), we show that there exists a function that can be computed in time O(T center dot t(h)) and space S by a RAM algorithm, but any MPC algorithm with local memory size s < S/c for some c > 1 requires at least (Omega) over tilde (T)(1) rounds to compute the function, even in the average case, for a wide range of parameters n <= S <= T <= 2(n1/4). Our result is almost optimal in the sense that by taking T to be much larger than t(h), e.g., T to be sub-exponential in t(h), to compute the function, the round complexity of any MPC algorithm with small local memory size is asymptotically the same (up to a polylogarithmic factor) as the time complexity of the RAM algorithm. Our result is obtained by adapting the so-called compression argument from the data structure lower bounds and cryptography literature to the context of massively parallel computation.

关键词： lower bound of communication rounds massively parallel computation random oracle model

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：