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

35th ACM Symposium on parallelism in algorithms and Architectures (SPAA)

作者： Haqi, Alireza Zarrabi-Zadeh, Hamid Sharif Univ Technol Tehran Iran

ISBN: (纸本)9781450395458

Clustering and diversification are two central problems with various applications in machine learning, data mining, and information retrieval. The k-center clustering and k-diversity maximization are two of the most well-studied and widely-used problems in this area. Both problems admit sequential algorithms with optimal approximation factors of 2 in any metric space. However, finding distributed algorithms matching the same optimal approximation ratios has been open for more than a decade, with the best current algorithms having factors at least twice the optimal. In this paper, we settle this open problem by presenting constant-round distributed algorithms for k-center clustering and k-diversity maximization in the massively parallel computation (MPC) model, achieving an approximation factor of 2 + epsilon in any metric space for any constant epsilon > 0, which is essentially the best possible considering the lower bound of 2 on the approximability of both these problems. Our algorithms are based on a novel technique for approximating vertex degrees and finding a so-called k-bounded maximal independent set in threshold graphs, using only a constant number of MPC rounds. Other applications of our general technique is also implied, including an almost optimal (3 + epsilon)-approximation algorithm for the k-supplier problem in any metric space in the MPC model.

关键词： k-center clustering diversity maximization maximal independent set massively parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

The derived-vector space framework and four general purposes massively parallel DDM algorithms

引用

ENGINEERING ANALYSIS WITH BOUNDARY ELEMENTS 2013年第3期37卷 646-657页

作者： Herrera, Ismael Rosas-Medina, Alberto A. Univ Nacl Autonoma Mexico Inst Geofis Mexico City 14000 DF Mexico

Ideally, DDMs seek what we call the DDM-paradigm: "constructing the global solution by solving local problems, exclusively". To achieve it, it is essential to disconnect the subdomain-problems. In FETI-DP such disconnection is achieved by formulating the method in a product function-space that contains discontinuous functions. However, FETI-DP uses an indirect formulation based on Lagrange-multipliers. BDDC uses instead a more direct formulation, but does not work directly in a space of discontinuous functions, either. Another fact difficult to overcome is: at present competitive algorithms need to incorporate constraints that prevent full disconnection of the subdomains. This paper is devoted to explain a direct (primal) approach to DDMs in which all the numerical work is done in a product-space (the derived-vector space), which supplies a unified setting for non-overlapping DDMs and can be used to formulate and discuss in a general and systematic manner the theory of DDMs for non-symmetric problems. Furthermore, in this realm four general-purposes preconditioned algorithms with constraints applicable to non-symmetric matrices, which achieve the DDM-paradigm, have been obtained. Two of them have been identified as DVS-versions of BDDC and FETI-DP. The uniformity of the matrix-formulas expressing such algorithms should be highlighted. (C) 2013 Elsevier Ltd. All rights reserved.

关键词： massively parallel algorithms parallel-computers Non-overlapping DDM DDM with constraints BDDC FETI-DP

来源：评论

学校读者我要写书评

暂无评论

DOMAIN DECOMPOSITION algorithms OF SCHWARZ TYPE, DESIGNED FOR massively parallel COMPUTERS

DOMAIN DECOMPOSITION ALGORITHMS OF SCHWARZ TYPE, DESIGNED FO...

引用

5TH INTERNATIONAL SYMP ON DOMAIN DECOMPOSITION METHODS FOR PARTIAL DIFFERENTIAL EQUATIONS

作者： BJORSTAD, PE SKOGEN, MD Univ of Bergen Bergen Norway

ISBN: (纸本)0898712882

We discuss implementation of additive Schwarz type algorithms on SIMD computers. A recursive, additive algorithm is compared with a two-level scheme. These methods are based on a subdivision of the domain into thousands of micro-patches that can reflect local properties, coupled with a coarser, global discretization where the `macro' behavior is reflected. The two-level method shows very promising flexibility, convergence and performance properties when implemented on a massively parallel SIMD computer.

关键词： DOMAIN DECOMPOSITION SCHWARZ ALGORITHM massively parallel algorithms ELLIPTIC PARTIAL DIFFERENTIAL EQUATIONS SIMD COMPUTERS

来源：评论

学校读者我要写书评

暂无评论

SOBB: Skewed Oriented Bounding Boxes for Ray Tracing

引用

COMPUTER GRAPHICS FORUM 2025年

作者： Kacerik, M. Bittner, J. Czech Tech Univ Fac Elect Engn Prague Czech Republic

We propose skewed oriented bounding boxes (SOBB) as a novel bounding primitive for accelerating the calculation of ray-scene intersections. SOBBs have the same memory footprint as the well-known oriented bounding boxes (OBB) and can be used with a similar ray intersection algorithm. We propose an efficient algorithm for constructing a BVH with SOBBs, using a transformation from a standard BVH built for axis-aligned bounding boxes (AABB). We use discrete orientation polytopes as a temporary bounding representation to find tightly fitting SOBBs. Additionally, we propose a compression scheme for SOBBs that makes their memory requirements comparable to those of AABBs. For secondary rays, the SOBB BVH provides a ray tracing speedup of 1.0-11.0x over the AABB BVH and it is 1.1x faster than the OBB BVH on average. The transformation of AABB BVH to SOBB BVH is, on average, 2.6x faster than the ditetrahedron-based AABB BVH to OBB BVH transformation.

关键词： CCS Concepts center dot Computing methodologies -> Ray tracing massively parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient GPU Computation of Large Protein Solvent-Excluded Surface

引用

IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS 2025年第4期31卷 2101-2113页

作者： Plateauholleville, Cyprien Maria, Maxime Merillou, Stephane Montes, Matthieu Univ Limoges XLIM Lab F-87000 Limoges France Hesam Univ GBCM Lab Genom Bioinformat & Chim Mol Conservatoire Natl Arts & Metiers F-75005 Paris France Inst Univ France IUF F-75005 Paris France

The Solvent-Excluded Surface (SES) is an essential representation of molecules which is massively used in molecular modeling and drug discovery since it represents the interacting surface between molecules. Based on its properties, it supports the visualization of both large scale shapes and details of molecules. While several methods targeted its computation, the ability to process large molecular structures to address the introduction of big complex analysis while leveraging the massively parallel architecture of GPUs has remained a challenge. This is mostly caused by the need for consequent memory allocation or by the complexity of the parallelization of its processing. In this paper, we leverage the last theoretical advances made for the depiction of the SES to provide fast analytical computation with low impact on memory. We show that our method is able to compute the complete surface while handling large molecular complexes with competitive computation time costs compared to previous works.

关键词： Synthetic aperture sonar Surface treatment Graphics processing units Rendering (computer graphics) Memory management Geometry Proteins Scientific visualization massively parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

DETERMINISTIC massively parallel CONNECTIVITY

引用

SIAM JOURNAL ON COMPUTING 2023年第5期52卷 1269-1318页

作者： Coy, Sam Czumaj, Artur Univ Warwick Dept Comp Sci Coventry CV4 7AL England Univ Warwick Ctr Discrete Math & Its Applicat Coventry CV4 7AL England

We consider the problem of designing fundamental graph algorithms on the model of massively parallel computation (MPC). The input to the problem is an undirected graph G with n vertices and m edges and with D being the maximum diameter of any connected component in G. We consider the MPC with low local space, allowing each machine to store only Theta(n(delta)) words for an arbitrary constant delta> 0 and with linear global space (which is the number of machines times the local space available), that is, with optimal utilization. In a recent breakthrough, Andoni et al. [parallel graph connectivity in log diameter rounds, 2018] and Behnezhad, Hajiaghayi, and Harris [Exponentially faster massively parallel maximal matching, 2019] designed parallel randomized algorithms that in O(logD+log log n) rounds on an MPC with low local space determine all connected components of a graph, improving on the classic bound of O(log n) derived from earlier works on PRAM algorithms. In this paper, we show that asymptotically identical bounds can be also achieved for deterministic algorithms: We present a deterministic MPC low local space algorithm that in O(log D+ log log n) rounds determines connected components of the input graph. Our result matches the complexity of state-of-the-art randomized algorithms for this task. We complement our upper bounds by extending a recent lower bound for the connectivity on an MPC conditioned on the 1-vs 2-cycles conjecture (which requires D >= log(1+Omega(1)) n) by showing a related conditional hardness of Omega (log D) MPC rounds for the entire spectrum of D, covering a particularly interesting range when D <= O(log n).

关键词： derandomization connectivity MapReduce MPC massively parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Cover or Pack: New Upper and Lower Bounds for massively parallel Joins 21

Cover or Pack: New Upper and Lower Bounds for Massively Para...

引用

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

作者： Hu, Xiao Duke Univ Durham NC 27706 USA

ISBN: (纸本)9781450383813

This paper considers the worst-case complexity of multi-round join evaluation in the massively parallel Computation (MPC) model. Unlike the sequential RAM model, in which there is a unified optimal algorithm based on the AGM bound for all join queries, worst-case optimal algorithms have been achieved on a very restrictive class of joins in the MPC model. The only known lower bound is still derived from the AGM bound, in terms of the optimal fractional edge covering number of the query. In this work, we make efforts towards bridging this gap. We design an instance-dependent algorithm for the class of alpha-acyclic join queries. In particular, when the maximum size of input relations is bounded, this complexity has a closed form in terms of the optimal fractional edge covering number of the query, which is worst-case optimal. Beyond acyclic joins, we surprisingly find that the optimal fractional edge covering number does not lead to a tight lower bound. More specifically, we prove for a class of cyclic joins a higher lower bound in terms of the optimal fractional edge packing number of the query, which is matched by existing algorithms, thus optimal. This new result displays a significant distinction for join evaluation, not only between acyclic and cyclic joins, but also between the fine-grained RAM and coarse-grained MPC model.

关键词： query processing massively parallel algorithms worst-case optimal

来源：评论

学校读者我要写书评

暂无评论

massively parallel Construction of Radix Tree Forests for the Efficient Sampling of Discrete or Piecewise Constant Probability Distributions 13th

Massively Parallel Construction of Radix Tree Forests for th...

引用

13th International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (MCQMC)

作者： Binder, Nikolaus Keller, Alexander NVIDIA Berlin Germany

ISBN: (纸本)9783030434656;9783030434649

We compare different methods for sampling from discrete or piecewise constant probability distributions and introduce a new algorithm which is especially efficient on massively parallel processors, such as GPUs. The scheme preserves the distribution properties of the input sequence, exposes constant time complexity on the average, and significantly lowers the average number of operations for certain distributions when sampling is performed in a parallel algorithm that requires synchronization. Avoiding load balancing issues of naive approaches, a very efficient massively parallel construction algorithm for the required auxiliary data structure is proposed.

关键词： Sampling Low discrepancy sequences massively parallel algorithms GPU

来源：评论

学校读者我要写书评

暂无评论

Dynamic Memory Management in massively parallel Systems: A Case on GPUs 22

Dynamic Memory Management in Massively Parallel Systems: A C...

引用

36th ACM International Conference on Supercomputing (ICS)

作者： Pham, Minh Li, Hao Yuan, Yongke Mou, Chengcheng Ramachandran, Kandethody Xu, Zichen Univ S Florida Tampa FL 33620 USA Beijing Univ Technol Beijing Beijing Peoples R China Jiaxing Neofelis Sci Inc Jiaxing Zhejiang Peoples R China

ISBN: (纸本)9781450392815

Due to the high level of parallelism, there are unique challenges in developing system software on massively parallel hardware such as GPUs. One such challenge is designing a dynamic memory allocator whose task is to allocate memory chunks to requesting threads at runtime. State-of-the-art GPU memory allocators maintain a global data structure holding metadata to facilitate allocation/deallocation. However, the centralized data structure can easily become a bottleneck in a massively parallel system. In this paper, we present a novel approach for designing dynamic memory allocation without a centralized data structure. The core idea is to let threads follow a random search procedure to locate free pages. Then we further extend to more advanced designs and algorithms that can achieve an order of magnitude improvement over the basic idea. We present mathematical proofs to demonstrate that (1) the basic random search design achieves asymptotically lower latency than the traditional queue-based design and (2) the advanced designs achieve significant improvement over the basic idea. Extensive experiments show consistency to our mathematical models and demonstrate that our solutions can achieve up to two orders of magnitude improvement in latency over the best-known existing solutions.

关键词： GPU dynamic memory management parallel computing massively parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Deterministic massively parallel Connectivity*† 2022

Deterministic Massively Parallel Connectivity*†

引用

54th Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Coy, Sam Czumaj, Artur Univ Warwick Coventry W Midlands England

ISBN: (纸本)9781450392648

We consider the problem of designing fundamental graph algorithms on the model of Massive parallel Computation (MPC). The input to the problem is an undirected graph G with n vertices and m edges, and with D being the maximum diameter of any connected component in G. We consider the MPC with low local space, allowing each machine to store only Theta(n(delta)) words for an arbitrary constant delta > 0, and with linear global space (which is the number of machines times the local space available), that is, with optimal utilization. In a recent breakthrough, Andoni et al. (FOCS'18) and Behnezhad et al. (FOCS'19) designed parallel randomized algorithms that in O (logD + log log n) rounds on an MPC with low local space determine all connected components of a graph, improving on the classic bound of O ( log n) derived from earlier works on PRAM algorithms. In this paper, we show that asymptotically identical bounds can be also achieved for deterministic algorithms: we present a deterministic MPC low local space algorithm that in O (log D + log log n) rounds determines connected components of the input graph. Our result matches the complexity of state of the art randomized algorithms for this task. The techniques developed in our paper can be also applied to several related problems, giving new deterministic MPC algorithms for problems like finding a spanning forest, minimum spanning forest, etc. We complement our upper bounds by extending a recent lower bound for connectivity on an MPC conditioned on the 1-vs-2-cycles conjecture (which requires D >= log1+Omega(1) n), by showing a related conditional hardness of Omega( log D ) MPC rounds for the entire spectrum of D, covering a particularly interesting range when D <= O( log n).

关键词： derandomization connectivity MapReduce MPC massively parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：