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

Types for Complexity of parallel Computation in Pi-Calculus 1

30th European symposium on programming (ESOP) Held as Part of the 24th European Joint Conferences on theory and practice of Software (ETAPS)

作者： Baillot, Patrick Ghyselen, Alexis Univ Claude Bernard Lyon 1 LIP Univ Lyon CNRSENS Lyon F-69342 Lyon 07 France

ISBN: (数字)9783030720193

ISBN: (纸本)9783030720193;9783030720186

Type systems as a technique to analyse or control programs have been extensively studied for functional programming languages. In particular some systems allow to extract from a typing derivation a complexity bound on the program. We explore how to extend such results to parallel complexity in the setting of the pi-calculus, considered as a communication-based model for parallel computation. Two notions of time complexity are given: the total computation time without parallelism (the work) and the computation time under maximal parallelism (the span). We define operational semantics to capture those two notions, and present two type systems from which one can extract a complexity bound on a process. the type systems are inspired both by size types and by input/output types, with additional temporal information about communications.

关键词： Type Systems Pi-calculus Process Calculi Complexity Analysis Implicit Computational Complexity Size Types

来源：评论

学校读者我要写书评

暂无评论

Accelerating CUDA Graph Algorithms at Maximum Warp 11

Accelerating CUDA Graph Algorithms at Maximum Warp

引用

16th ACM symposium on principles and practice of parallel programming

作者： Hong, Sungpack Kim, Sang Kyun Oguntebi, Tayo Olukotun, Kunle Stanford Univ Comp Syst Lab Stanford CA 94305 USA

ISBN: (纸本)9781450301190

Graphs are powerful data representations favored in many computational domains. Modern GPUs have recently shown promising results in accelerating computationally challenging graph problems but their performance suffers heavily when the graph structure is highly irregular, as most real-world graphs tend to be. In this study, we first observe that the poor performance is caused by work imbalance and is an artifact of a discrepancy between the GPU programming model and the underlying GPU architecture. We then propose a novel virtual warp-centric programming method that exposes the traits of underlying GPU architectures to users. Our method significantly improves the performance of applications with heavily imbalanced workloads, and enables trade-offs between workload imbalance and ALU underutilization for fine-tuning the performance. Our evaluation reveals that our method exhibits up to 9x speedup over previous GPU algorithms and 12x over single thread CPU execution on irregular graphs. When properly configured, it also yields up to 30% improvement over previous GPU algorithms on regular graphs. In addition to performance gains on graph algorithms, our programming method achieves 1.3x to 15.1x speedup on a set of GPU benchmark applications. Our study also confirms that the performance gap between GPUs and other multi-threaded CPU graph implementations is primarily due to the large difference in memory bandwidth.

关键词： Algorithms Performance parallel graph algorithms CUDA GPGPU

来源：评论

学校读者我要写书评

暂无评论

30th European symposium on programming, ESOP 2021 Held as Part of the European Joint Conferences on theory and practice of Software, ETAPS 2021

30th European Symposium on Programming, ESOP 2021 Held as Pa...

引用

30th European symposium on programming, ESOP 2021 Held as Part of the European Joint Conferences on theory and practice of Software, ETAPS 2021

ISBN: (纸本)9783030720186

the proceedings contain 24 papers. the special focus in this conference is on programming. the topics include: Sound and Complete Concolic Testing for Higher-order Functions;strong-Separation Logic;types for Complexity of parallel Computation in Pi-Calculus;checking Robustness Between Weak Transactional Consistency Models;verified Software Units;an Automated Deductive Verification Framework for Circuit-building Quantum Programs;nested Session Types;coupled Relational Symbolic Execution for Differential Privacy;graded Hoare Logic and its Categorical Semantics;coupled relational symbolic execution for differential privacy;graded hoare logic and its categorical semantics;etaps foreword;preface;For a Few Dollars More: Verified Fine-Grained Algorithm Analysis Down to LLVM;run-time Complexity Bounds Using Squeezers;complete trace models of state and control;session Coalgebras: A Coalgebraic View on Session Types and Communication Protocols;correctness of Sequential Monte Carlo Inference for Probabilistic programming Languages;densities of Almost Surely Terminating Probabilistic Programs are Differentiable Almost Everywhere;graded Modal Dependent Type theory;automated Termination Analysis of Polynomial Probabilistic Programs;bayesian strategies: probabilistic programs as generalised graphical models;data Flow Analysis of Asynchronous Systems using Infinite Abstract Domains.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Constraint programming Model for Assembly Line Balancing and Scheduling with Walking Workers and parallel Stations 30

Constraint Programming Model for Assembly Line Balancing and...

引用

30th International Conference on principles and practice of Constraint programming, CP 2024

作者： Pucel, Xavier Roussel, Stéphanie ONERA ONERA DTIS Université de Toulouse Toulouse France

ISBN: (纸本)9783959773362

In the context of aircraft assembly lines, increasing the production rate and decreasing the operating costs are two important, and sometimes contradictory, objectives. In small assembly lines, sharing production resources across workstations is a simple and efficient way to reduce operating costs. therefore, workers are not assigned to a unique workstation but can walk between them. On the other side, paralleling workstations is an efficient way to increase the production rate. However, the combination of both strategies create complex conditions for tasks to access the production resources. this paper addresses the problem of allocating tasks to workstations and scheduling them in an assembly line where workers can freely walk across workstations, and where workstations can be organized in parallel. We model this novel problem with Constraint programming. We evaluate it on real world industrial use cases coming from aircraft manufacturers, as well as synthetic use cases adapted from the literature. © Xavier Pucel and Stéphanie Roussel.

关键词： Constraint programming

来源：评论

学校读者我要写书评

暂无评论

ParLS-PBO: A parallel Local Search Solver for Pseudo Boolean Optimization 30

ParLS-PBO: A Parallel Local Search Solver for Pseudo Boolean...

引用

30th International Conference on principles and practice of Constraint programming, CP 2024

作者： Chen, Zhihan Lin, Peng Hu, Hao Cai1, Shaowei State Key Laboratory of Computer Science Institute of Software Chinese Academy of Sciences Beijing China School of Computer Science and Technology University of Chinese Academy of Sciences Beijing China

ISBN: (纸本)9783959773362

As a broadly applied technique in numerous optimization problems, recently, local search has been employed to solve Pseudo-Boolean Optimization (PBO) problem. A representative local search solver for PBO is LS-PBO. In this paper, firstly, we improve LS-PBO by a dynamic scoring mechanism, which dynamically strikes a balance between score on hard constraints and score on the objective function. Moreover, on top of this improved LS-PBO, we develop the first parallel local search PBO solver. the main idea is to share good solutions among different threads to guide the search, by maintaining a pool of feasible solutions. For evaluating solutions when updating the pool, we propose a function that considers both the solution quality and the diversity of the pool. Furthermore, we calculate the polarity density in the pool to enhance the scoring function of local search. Our empirical experiments show clear benefits of the proposed parallel approach, making it competitive with the parallel version of the famous commercial solver Gurobi. © Zhihan Chen, Peng Lin, Hao Hu, and Shaowei Cai.

关键词： Local search (optimization)

来源：评论

学校读者我要写书评

暂无评论

CP for Bin Packing with Multi-Core and GPUs 30

CP for Bin Packing with Multi-Core and GPUs

引用

30th International Conference on principles and practice of Constraint programming, CP 2024

作者： Tardivo, Fabio Michel, Laurent Pontelli, Enrico Department of Computer Science New Mexico State University Las CrucesNM United States Synchrony Chair in Cybersecurity School of Computing University of Connecticut StorrsCT United States

ISBN: (纸本)9783959773362

the BinPacking constraint models the requirements of many logistics, resource allocation, and production scheduling applications. this paper explores new avenues based on the impressive computational power of modern GPUs to propagate the BinPacking constraint. this work showcases how the perspective of massive parallelization can lead to novel approaches, such as the use of a portfolio of lower bounds, to enhance the pruning of the BinPacking constraints. It delivers insights into the design choices and challenges presented by GPU platform for constraint propagation. the paper evaluates a GPU-accelerated propagator against both sequential and parallel CPU versions, as well as state-of-the-art approaches. Comparisons across various benchmarks from the literature show strong performances with respect to both CPU versions and the standard pruning approach. When compared to techniques based on Linear programming, our approach proves valuable for large instances or when spending extensive time to obtain the best possible bound is not convenient. © Fabio Tardivo, Laurent Michel, and Enrico Pontelli.

关键词： Linear programming

来源：评论

学校读者我要写书评

暂无评论

A Scalable Hybrid Total FETI Method for Massively parallel FEM Simulations 23

A Scalable Hybrid Total FETI Method for Massively Parallel F...

引用

28th ACM SIGPLAN Annual symposium on principles and practice of parallel programming, PPoPP 2023

作者： Lin, Kehao Zhou, Chunbao Zeng, Yan Nie, Ningming Wang, Jue Li, Shigang Feng, Yangde Wang, Yangang Yao, Kehan Yao, Tiechui Zhang, Jilin Wan, Jian Hangzhou Dianzi University Hangzhou China Computer Network Information Center Chinese Academy of Sciences Beijing China University of Chinese Academy of Sciences Beijing China School of Computer Science Beijing University of Posts and Telecommunications Beijing China

ISBN: (纸本)9798400700156

the Hybrid Total Finite Element Tearing and Interconnecting (HTFETI) method plays an important role in solving large-scale and complex engineering problems. this method needs to handle numerous matrix-vector multiplications. Directly calling the vendor-optimized library for general matrix-vector multiplication (gemv) on GPU leads to low performance, since it does not consider optimizations for different matrix sizes in HTFETI, i.e. different row and column sizes. In addition, state-of-the-art graph partitioning methods cannot guarantee load balancing for HTFETI, since the matrix size is determined by the length of the subdomain boundary. To solve the problems above, we first port gemv to the multi-stream pipeline scheme and develop a new batched kernel function on GPU, which brings 15%∼30% throughput improvement and 37% average GFLOPs improvement, respectively. We also propose a multi-grained load-balancing scheme based on graph repartitioning and work-stealing, and the load imbalance ratio is down to 1.05∼1.09 from 1.5. We have successfully applied the scalable HTFETI method to simulate the whole core assembly of China Experimental Fast Reactor (CEFR) for steady-state analysis, and the efficiencies of weak scalability and strong scalability reach 78% and 72% on 12,288 GPUs, respectively. As far as we know, this is the first time that HTFETI has been used in large-scale and high-fidelity whole core assembly simulation. © 2023 Owner/Author.

关键词： Scalability

来源：评论

学校读者我要写书评

暂无评论

Turbocharging Boosted Transactions or: How I Learnt to Stop Worrying and Love Longer Transactions

引用

ACM SIGPLAN NOTICES 2009年第4期44卷 307-308页

作者： Kulkarni, Chinmay Unsal, Osman Cristal, Adrian Ayguade, Eduard Valero, Mateo Birla Inst Technol & Sci Pilani Rajasthan India Tech Univ Catalunya Catalunya Spain

Boosted transactions offer an attractive method that enables programmers to create larger transactions that scale well and offer deadlock-free guarantees. However, as boosted transactions get larger, they become more susceptible to conflicts and aborts. We describe a linear-time algorithm to detect transactions that cannot make progress, which transactions need to be aborted, and when. the algorithm guarantees zero false positives with minimal aborts. Our proposals, as implemented in DSTM2, increase the transactional throughput of the system, often by more than 30%.

关键词： Algorithms Performance Concurrency parallel programming transactional memory deadlocks deadlock-detection

来源：评论

学校读者我要写书评

暂无评论

Preliminary Results on NB-FEB, a Synchronization Primitive for parallel programming

引用

ACM SIGPLAN NOTICES 2009年第4期44卷 295-296页

作者： Ha, Phuong Hoai Tsigas, Philippas Anshus, Otto J. Univ Tromso N-9001 Tromso Norway Chalmers Univ Technol Gothenburg Sweden

We introduce a non-blocking full/empty bit primitive, or NB-FEB for short, as a promising synchronization primitive for parallel programming on may-core architectures. We show that the NB-FEB primitive is universal, scalable and feasible. NB-FEB, together with registers, can solve the consensus problem for an arbitrary number of processes (universality). NB-FEB is combinable, namely its memory requests to the same memory location can be combined into only one memory request, which consequently mitigates performance degradation due to synchronization "hot spots" (scalability). Since NB-FEB is a variant of the original full/empty bit that always returns a value instead of waiting for a conditional flag, it is as feasible as the original full/empty bit, which has been implemented in many computer systems (feasibility).

关键词： Algorithms Reliability theory many-core architectures non-blocking synchronization full/empty bit universal primitives combinability

来源：评论

学校读者我要写书评

暂无评论

parallel k-Core Decomposition with Batched Updates and Asynchronous Reads 24

Parallel k-Core Decomposition with Batched Updates and Async...

引用

29th ACM SIGPLAN Annual symposium on principles and practice of parallel programming, PPoPP 2024

作者： Liu, Quanquan C. Shun, Julian Zablotchi, Igor Yale University United States MIT CSAIL United States Mysten Labs Switzerland

ISBN: (纸本)9798400704352

Maintaining a dynamic k-core decomposition is an important problem that identifies dense subgraphs in dynamically changing graphs. Recent work by Liu et al. [SPAA 2022] presents a parallel batch-dynamic algorithm for maintaining an approximate k-core decomposition. In their solution, both reads and updates need to be batched, and therefore each type of operation can incur high latency waiting for the other type to finish. To tackle most real-world workloads, which are dominated by reads, this paper presents a novel hybrid concurrent-parallel dynamic k-core data structure where asynchronous reads can proceed concurrently with batches of updates, leading to significantly lower read latencies. Our approach is based on tracking causal dependencies between updates, so that causally related groups of updates appear atomic to concurrent readers. Our data structure guarantees linearizability and liveness for both reads and updates, and maintains the same approximation guarantees as prior work. Our experimental evaluation on a 30-core machine shows that our approach reduces read latency by orders of magnitude compared to the batch-dynamic algorithm, up to a (4.05 · 105 ) -factor. Compared to an unsynchronized (non-linearizable) baseline, our read latency overhead is only up to a 3.21-factor greater, while improving accuracy of coreness estimates by up to a factor of 52.7. © 2024 Copyright held by the owner/author(s).

关键词： Data structures

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：