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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Improved massively parallel computation Algorithms for MIS, Matching, and Vertex Cover 18

Improved Massively Parallel Computation Algorithms for MIS, ...

引用

37th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)

作者： Ghaffari, Mohsen Gouleakis, Themis Konrad, Christian Mitrovic, Slobodan Rubinfeld, Ronitt Swiss Fed Inst Technol Zurich Switzerland MIT Cambridge MA 02139 USA Univ Bristol Bristol Avon England Ecole Polytech Fed Lausanne Lausanne Switzerland Tel Aviv Univ Tel Aviv Israel

ISBN: (纸本)9781450357951

We present O(log log n)-round algorithms in the massively parallel computation (MPC) model, with a(n) memory per machine, that compute a maximal independent set, a 1 + epsilon approximation of maximum matching, and a 2 + epsilon approximation of minimum vertex cover, for any n-vertex graph and any constant epsilon > 0. These improve the state of the art as follows: Our MIS algorithm leads to a simple O(log log A)-round MIS algorithm in the CONGESTED-CLIQUE model of distributed computing, which improves on the (O) over tilde(root log Delta)-round algorithm of Ghaffari [PODC'17]. Our O(log log(2) n)-round (1 + epsilon)-approximate maximum matching algorithm simplifies or improves on the following prior work: O(log2 log n)-round (1 + epsilon)-approximation algorithm of Czumaj et al. [STOC'18] and O(log log n)-round (1 + epsilon) approximation algorithm of Assadi et al. [arXiv'17]. Our O(log log n)-round (2 + epsilon)-approximate minimum vertex cover algorithm improves on an O(log log n)-round O(1)-approximation of Assadi et al. [arXiv'17].

关键词： Maximal Independent Set Maximum Matching Vertex Cover massively parallel computation Congested Clique

来源：评论

学校读者我要写书评

暂无评论

Graph Sparsification for Derandomizing massively parallel computation with Low Space 20

Graph Sparsification for Derandomizing Massively Parallel Co...

引用

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

作者： Czumaj, Artur Davies, Peter Parter, Merav Univ Warwick Coventry W Midlands England IST Austria Klosterneuburg Austria Weizmann Inst Sci Rehovot Israel

ISBN: (纸本)9781450369350

massively parallel computation (MPC) is an emerging model which distills core aspects of distributed and parallel computation. It was developed as a tool to solve (typically graph) problems in systems where input is distributed over many machines with limited space. Recent work has focused on the regime in which machines have sublinear (in. n, number of nodes in the input graph) space, with randomized algorithms presented for the fundamental problems of Maximal Matching and Maximal Independent Set. There are, however, no prior corresponding deterministic algorithms. A major challenge in the sublinear space setting is that the local space of each machine may be too small to store all the edges incident to a single node. To overcome this barrier we introduce a new graph sparsification technique that deterministically computes a low-degree subgraph with additional desired properties: degrees in the subgraph are sufficiently small that nodes' neighborhoods can be stored on single machines, and solving the problem on the subgraph provides significant global progress towards solving the problem for the original input graph. Using this framework to derandomize the well-known randomized algorithm of Luby [SICOMP'86], we obtain O(log Delta + log log n)-round deterministic MPC algorithms for solving the fundamental problems of Maximal Matching and Maximal Independent Set with O(n(epsilon)) space on each machine for any constant epsilon > 0. Based on the recent work of Ghaffari et al. [FOCS'18], this additive O(log log n) factor is conditionally essential. These algorithms can also be shown to 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 Derandomization Maximal Independent Set Maximal Matching Low Space

来源：评论

学校读者我要写书评

暂无评论

The Complexity of (Δ+1) Coloring in Congested Clique, massively parallel computation, and Centralized Local computation 19

The Complexity of (Δ+1) Coloring in Congested Clique, Massi...

引用

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

作者： Chang, Yi-Jun Fischer, Manuela Ghaffari, Mohsen Uitto, Jara Zheng, Yufan Univ Michigan Ann Arbor MI 48109 USA Swiss Fed Inst Technol Zurich Switzerland Univ Freiburg Freiburg Germany

ISBN: (纸本)9781450362177

In this paper, we present new randomized algorithms that improve the complexity of the classic (Delta + 1)-coloring problem, and its generalization (Delta + 1)-list-coloring, in three well-studied models of distributed, parallel, and centralized computation: Distributed Congested Clique: We present an O(1)-round randomized algorithm for (Delta + 1)-list-coloring in the congested clique model of distributed computing. This settles the asymptotic complexity of this problem. It moreover improves upon the O(log*Delta)-round randomized algorithms of Parter and Su [DISC'18] and O((log log.) center dot log*Delta-round randomized algorithm of Parter [ICALP'18]. massively parallel computation: We present a randomized (Delta + 1)-list-coloring algorithm with round complexity O(root log logn) in the massively parallel computation (MPC) model with strongly sublinear memory per machine. This algorithm uses a memory of O(n(alpha)) per machine, for any desirable constant alpha > 0, and a total memory of (O) over tilde (m), where m is the number of edges in the graph. Notably, this is the first coloring algorithm with sublogarithmic round complexity, in the sublinear memory regime of MPC. For the quasilinear memory regime of MPC, anO(1)-round algorithm was given very recently by Assadi et al. [SODA'19]. Centralized Local computation: We show that (Delta + 1)-listcoloring can be solved by a randomized algorithm with query complexity Delta O(1) center dot O(log n), in the centralized local computation model. The previous state of the art for (Delta + 1)-list-coloring in the centralized local computation model are based on simulation of known LOCAL algorithms. The deterministic O(root Delta poly log Delta + log* n)-round LOCAL algorithm of Fraigniaud et al. [FOCS'16] can be implemented in the centralized local computation model with query complexity Delta(O(root Delta poly log) (Delta)) center dot O(log* n);the randomized Delta O(log*Delta) + 2(O(root log log n))-round LOCAL algorithm

关键词： coloring congested clique centralized local computation massively parallel computation

来源：评论

学校读者我要写书评

暂无评论

Component Stability in Low-Space massively parallel computation 21

Component Stability in Low-Space Massively Parallel Computat...

引用

40th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)

作者： Czumaj, Artur Davies, Peter Parter, Merav Univ Warwick Coventry W Midlands England IST Austria Klosterneuburg Austria Weizmann Inst Sci Rehovot Israel

ISBN: (纸本)9781450385480

In this paper, we study the power and limitations of componentstable 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 M PC algorithms, which are, informally, defined as 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: 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. 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. We demonstrate a collection of natural graph problems for which non-component-stable algorithms break the conditional lower bound obtained for component-stable algorithms. This implies that, for both deterministic and randomized algorithms, component-stable algorithms are conditionally weaker than the non-component-stable ones. Altogether our results imply that component-stability might limit the computational power of the low-space MPC model, paving the way for improved upper bounds that escape the conditional lower bound setting of Ghaffari, Kuhn, and Uitto.

关键词： massively parallel computation Lower bounds Derandomization

来源：评论

学校读者我要写书评

暂无评论

Combinatorial Optimization on Massive Datasets: Streaming, Distributed, and massively parallel computation

Combinatorial Optimization on Massive Datasets: Streaming, D...

引用

作者： Assadi, Sepehr University of Pennsylvania

学位级别：Ph.D.

With the emergence of massive datasets across different application domains, there is a rapidly growing need to solve various optimization tasks over such datasets. This in turn raises the following fundamental question: How well can we solve a large-scale optimization problem on massive datasets in a resource-efficient manner? The focus of this thesis is on answering this question for various problems in different modern computational models for processing massive datasets, in particular, streaming, distributed, and massively parallel computation (such as MapReduce) models. The first part of this thesis is focused on graph optimization, in which we study several fundamental graph optimization problems including matching, vertex cover, and connectivity. The main results in this part include a tight bound on the space complexity of the matching problem in dynamic streams, a unifying framework for achieving algorithms that improve the state-of-the-art for matching and vertex cover problems in all the mentioned models, and the first massively parallel algorithm for connectivity on sparse graphs that improve upon the classical parallel PRAM algorithms for a large family of graphs. In the second part of the thesis, we consider submodular optimization and in particular two canonical examples of set cover and maximum coverage problems. We establish tight bounds on the space complexity of approximating set cover and maximum coverage in both single- and multi-pass streams, and build on these results to address the general problem of submodular maximization across all aforementioned models. In the last part, we consider resource constrained optimization settings which require computation over data which is not particularly large but still imposes restrictions of similar nature. Examples include optimization over data which can only be accessed with limited adaptivity (e.g. in crowdsourcing applications), or corresponds to private information of agents and is not available in

关键词： Combinatorial Optimization Communication Complexity Distributed Computing massively parallel computation Streaming

来源：评论

学校读者我要写书评

暂无评论

Coloring Sparse Graphs with 3 Colors in the massively parallel computation (MPC) Model Using Strongly Sublinear Memory

Coloring Sparse Graphs with 3 Colors in the Massively Parall...

引用

作者： Latypov, Rustam Aalto University

学位级别：硕士

The question of what problems can be solved, and how efficiently, has always been at the core of theoretical computer science. One such fundamental problem is graph coloring; it is well researched and has numerous applications in areas of computer science such as scheduling and pattern matching. The challenges faced when designing graph coloring algorithms are dictated by the underlying graph family, the number of colors allowed, and the model of computation. In this work we consider the graph family of trees and the distributed massively parallel computation (MPC) model, introduced by Karloff et al. \cite{karloff}. Our contribution to the field of distributed computing is a deterministic strongly sublinear MPC algorithm for 3-coloring unbounded degree trees with $n$ nodes in $O(\log \log n)$ time. To the best of our knowledge, this is the current state-of-the-art algorithm, improving on the work of Ghaffari et al. \cite{ghaffari}. It is loosely based on two previous works by Brandt et al. \cite{sparce,sirocco}. Before computing a 3-coloring, our algorithm partitions the input tree into disjoint node sets $H_1,H_2,\dots,H_l$, in $O(\log \log n)$ time. For each node $v \in H_i$, it holds that $v$ has at most two neighbors in the set $\bigcup_{j=i}^l H_j$. We consider this partitioning in and of itself an important contribution, since it has the potential of being a useful subroutine in future algorithms. For example, a similar technique was used by Chang et al. \cite{chang} in their seminal paper to establish an important time hierarchy theorem for the distributed LOCAL model on trees.

关键词： graph problems trees 3-coloring distributed computing massively parallel computation strongly sublinear memory

来源：评论

学校读者我要写书评

暂无评论

Explainable graph clustering via expanders in the massively parallel computation model

引用

INFORMATION SCIENCES 2024年 677卷

作者： Aghamolaei, Sepideh Ghodsi, Mohammad Sharif Univ Technol Dept Comp Engn Azadi Ave Tehran *** Iran Inst Res Fundamental Sci IPM Sch Comp Sci Lavasani Av Tehran *** Iran

Explainable clustering provides human-understandable reasons for decisions in black -box learning models. In a previous work, a decision tree built on the set of dimensions was used to define ranges of values for k-means clusters. For explainable graph clustering, we use expander graphs instead of dense subgraphs since powering an expander graph is guaranteed to result in a clique after at most a logarithmic number of steps. Consider a set of multi-dimensional points labeled with k labels. We introduce the heat map sorting problem as reordering the rows and columns of an input matrix (each point is a column and each row is a dimension) such that the labels of the entries of the matrix form connected components (clusters). A cluster is preserved if it remains connected, i.e., if it is not split into several clusters and no two clusters are merged. In the massively parallel computation model (MPC), each machine has a sublinear memory and the total memory of the machines is linear. We prove the problem is NP-hard. We give a fixed -parameter algorithm in MPC and an approximation algorithm based on expander decomposition. We empirically compare our algorithm with explainable k-means on several graphs of email and computer networks.

关键词： Explainable clustering massively parallel computation Fixed-parameter algorithms Expander graphs DBSCAN

来源：评论

学校读者我要写书评

暂无评论

Multithread Execution Mechanisms on RICA-1 for massively parallel computation 96

Multithread Execution Mechanisms on RICA-1 for Massively Par...

引用

Proceedings of the 1996 Conference on parallel Architectures and Compilation Techniques

作者： K. Okamato S. Sakai H. Matsuoka T. Yokota H. Hirono

Abstract: This paper presents a multithreaded processor architecture for massively parallel computers, and presents RICA-1 multithreaded processor based on it. RICA-1 provides fairly efficient mechanisms of message reception, thread invocation, message generation/transmission and synchronization. It provides simple communication pipelines. computation pipelines and communication pipelines are highly fused within a processor architecture. parallel primitives such as remote memory access, remote procedure call and synchronizations are efficiently performed by RICA-1. The first version of RICA-1 is being implemented by a CMOS standard cell chip with 200 K random gates and 13 KB internal RAMs. It is packed into the 527 pin CPGA package and will operate with a 50 MHz clock in August 1996. In RICA-1, communication pipelines and the RISC-type execution pipelines are highly fused by a simple sequencer and three sets of register files substantially reduces the thread switch overhead.

关键词： RISC RICA-1 multiprogramming multithread execution mechanisms internal RAM clock synchronization thread invocation 50 MHz register files random gates multithreaded processor architecture massively parallel computation message generation communication pipelines CPGA package CMOS 13 KB message transmission thread switch overhead message reception computation pipelines remote procedure call remote memory access

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：