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

49th Annual acm-SIGACT symposium on theory of Computing (STOC)

作者： Im, Sungjin Moseley, Benjamin Sun, Xiaorui Univ Calif Elect Engn & Comp Sci 5200 N Lake Rd Merced CA 95344 USA Washington Univ Dept Comp Sci & Engn 1 Brookings Dr St Louis MO 63130 USA Univ Calif Berkeley Simons Inst Theory Comp Berkeley CA 94702 USA Simons Inst Theory Comp Berkeley CA USA

ISBN: (纸本)9781450345286

Modern science and engineering is driven by massively large data sets and its advance heavily relies on massively parallel computing platforms such as Spark, MapReduce, and Hadoop. theoretical models have been proposed to understand the power and limitations of such platforms. Recent study of developed theoretical models has led to the discovery of new algorithms that are fast and efficient in both theory and practice, thereby beginning to unlock their underlying power. Given recent promising results, the area has turned its focus on discovering widely applicable algorithmic techniques for solving problems efficiently. In this paper we make progress towards this goal by giving principles for simulating a large class of sequential dynamic programs in the distributed setting. In particular, we identify two key properties, monotonicity and decomposibility, which allow us to derive efficient distributed algorithms for problems possessing the properties. We showcase our framework by considering several core dynamic programming applications, Longest Increasing Subsequence, Optimal Binary Search Tree, and Weighted Interval Selection. For these problems, we derive algorithms yielding solutions that are arbitrarily close to the optimum, using O(1) rounds and (O) over tilde (n/m) memory on each machine where n is the input size and m is the number of machines available.

关键词： Massively parallel computing Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Reaching bandwidth saturation using transparent injection parallelization

引用

INTERNATIONAL JOURNAL OF HIGH PERFORMANCE COMPUTING APPLICATIONS 2017年第5期31卷 405-421页

作者： Chaimov, Nicholas Ibrahim, Khaled Z. Williams, Samuel Iancu, Costin Univ Oregon Eugene OR 97403 USA Lawrence Berkeley Natl Lab Computat Res Div Berkeley CA USA Lawrence Berkeley Natl Lab Performance & Algorithms Res Grp Berkeley CA USA

Although logically available, applications may not exploit enough instantaneous communication concurrency to maximize network utilization on HPC systems. this is exacerbated in hybrid programming models that combine single program multiple data with OpenMP or CUDA. We present the design of a multi-threaded runtime able to transparently increase the instantaneous network concurrency and to provide near saturation bandwidth, independent of the application configuration and dynamic behavior. the runtime offloads communication requests from application level tasks to multiple communication servers. the servers use system specific performance models to attain network saturation. Our techniques alleviate the need for spatial and temporal application level message concurrency optimizations. Experimental results show improved message throughput and bandwidth by as much as 150% for 4 KB messages on InfiniBand and by as much as 120% for 4 KB messages on Cray Aries. For more complex operations such as all-to-all collectives, we observe as much as 30% speedup. this translates into 23% speedup on 12,288 cores for a NAS FT implemented using FFTW. We observe as much as 76% speedup on 1500 cores for an already optimized UPC+OpenMP geometric multigrid application using hybrid parallelism. For the geometric multigrid GPU implementation, we observe as much as 44% speedup on 512 GPUs.

关键词： Communication concurrency multi-threaded runtime one sided communication parallel injection UPC

来源：评论

学校读者我要写书评

暂无评论

JParEnt: parallel entropy decoding for JPEG decompression on heterogeneous multicore architectures 7

JParEnt: Parallel entropy decoding for JPEG decompression on...

引用

Euro-Par Conference / 7th International Workshop on programming Models and Applications for Multicores and Manycores (PMAM) held in conjunction with the 21st SIGPLAN symposium on principles and practice of parallel programming (PPoPP)

作者： Sodsong, Wasuwee Jung, Minyoung Park, Jinwoo Burgstaller, Bernd Yonsei Univ Dept Comp Sci Seoul South Korea

ISBN: (纸本)9781450341967

the JPEG format employs Huffman codes to compress the entropy data of an image. Huffman codewords are of variable length, which makes parallel entropy decoding a difficult problem. To determine the start position of a codeword in the bitstream, the previous codeword must be decoded first. We present JParEnt, a new approach to parallel entropy decoding for JPEG decompression on heterogeneous multicores. JParEnt conducts JPEG decompression in two steps: (1)an efficient sequential scan of the entropy data on the CPU to determine the start-positions (boundaries) of coefficient blocks in the bitstream, followed by (2)a parallel entropy decoding step on the graphics processing unit (GPU). the block boundary scan constitutes a reinterpretation of the Huffman-coded entropy data to determine codeword boundaries in the bitstream. We introduce a dynamic workload partitioning scheme to account for GPUs of low compute power relative to the CPU. this configuration has become common with the advent of SoCs with integrated graphics processors (IGPs). We leverage additional parallelism through pipelined execution across CPU and GPU. For systems providing a unified address space between CPU and GPU, we employ zero-copy to completely eliminate the data transfer overhead. Our experimental evaluation of JParEnt was conducted on six heterogeneous multicore systems: one server and two desktops with dedicated GPUs, one desktop with an IGP, and two embedded systems. For a selection of more than 1000JPEG images, JParEnt outperforms the SIMD-implementation of the libjpeg-turbo library by up to a factor of 4.3x, and the previously fastest JPEG decompression method for heterogeneous multicores by up to a factor of 2.2x. JParEnt's entropy data scan consumes 45% of the entropy decoding time of libjpeg-turbo on average. Given this new ratio for the sequential part of JPEG decompression, JParEnt achieves up to97% of the maximum attainable speedup (95% on average). On the IGP-based desktop platform,

关键词： JPEG decoding entropy decoding prefix codes heterogeneous multicores GPU programming

来源：评论

学校读者我要写书评

暂无评论

Proceedings of the acm SIGPLAN symposium on principles and practice of parallel programming, PPOPP

Proceedings of the ACM SIGPLAN Symposium on Principles and P...

引用

20th acm SIGPLAN symposium on principles and practice of parallel programming, PPoPP 2015

ISBN: (纸本)9781450332057

the proceedings contain 44 papers. the topics discussed include: predicate RCU: an RCU for scalable concurrent updates;automatic scalable atomicity via semantic locking;a framework for practical parallel fast matrix multiplication;PLUTO+: near-complete modeling of affine transformations for parallelism and locality;distributed memory code generation for mixed irregular/regular computations;performance implications of dynamic memory allocators on transactional memory systems;low-overhead software transactional memory with progress guarantees and strong semantics∗;barrier elision for production parallel programs;scalable and efficient implementation of 3D unstructured meshes computation: a case study on matrix assembly;and diagnosing the causes and severity of one-sided message contention.

关键词：

来源：评论

学校读者我要写书评

暂无评论

parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures 16

Parallel Algorithms for Constructing Range and Nearest-Neigh...

引用

35th acm SIGMOD-SIGACT-SIGART symposium on principles of Database Systems (PODS)

作者： Agarwal, Pankaj K. Fox, Kyle Munagala, Kamesh Nath, Abhinandan Duke Univ Durham NC 27706 USA

ISBN: (纸本)9781450341912

With the massive amounts of data available today, it is common to store and process data using multiple machines. parallel programming platforms such as MapReduce and its variants are popular frameworks for handling such large data. We present the first provably efficient algorithms to compute, store, and query data structures for range queries and approximate nearest neighbor queries in a popular parallel computing abstraction that captures the salient features of MapReduce and other massively parallel communication (MPC) models. In particular, we describe algorithms for kd-trees, range trees, and BBD-trees that only require O(1) rounds of communication for both preprocessing and querying while staying competitive in terms of running time and workload to their classical counterparts. Our algorithms are randomized, but they can be made deterministic at some increase in their running time and workload while keeping the number of rounds of communication to be constant.

关键词： computational geometry

来源：评论

学校读者我要写书评

暂无评论

Proceedings of the 18th International symposium on principles and practice of Declarative programming, PPDP 2016

Proceedings of the 18th International Symposium on Principle...

引用

18th International symposium on principles and practice of Declarative programming, PPDP 2016

ISBN: (纸本)9781450341486

the proceedings contain 16 papers. the topics discussed include: description and evaluation of a generic design to integrate CLP and tabled execution;higher-order logic programming: an expressive language for representing qualitative preferences;a framework for easing the development of applications embedding answer set programming;proving inductive validity of constrained inequalities;analysis of access control policy updates through narrowing;strand spaces with choice via a process algebra semantics;reducing the overhead of assertion run-time checks via static analysis;and iterated process analysis over lattice-valued regular expressions.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Multi-track programming competitions with scratch 16

Multi-track programming competitions with scratch

引用

47th acm Technical symposium on Computing Science Education, SIGCSE 2016

作者： Arnold, Jason Bort, Heather Naugle, Ryan O'Hare, Casey Brylow, Dennis Department of Mathematics Statistics and Computer Science Marquette University 1313 West Wisconsin Avenue MilwaukeeWI53201-1881 United States

ISBN: (纸本)9781450338561

High school programming competitions often follow the traditional model of collegiate competitions, exemplified by the acm International Collegiate programming Contest (ICPC). this tradition has been reinforced by the nature of Advanced Placement Computer Science (AP CS A) for which ICPC-style problems are considered an excellent practice regimen. As more and more students in high school computer science courses approach the field from broader starting points, such as Exploring Computer Science (ECS), or the new AP CS principles course an analogous structure for high school outreach events becomes of greater importance. this paper describes our work on developing a Scratch-based alternative competition for high school students, that can be run in parallel with a traditional morning of ICPC-style problems. © 2016 acm.

关键词： Curricula

来源：评论

学校读者我要写书评

暂无评论

Sustainable Software Development through Overlapping Pair Rotation 16

Sustainable Software Development through Overlapping Pair Ro...

引用

10th acm/IEEE International symposium on Empirical Software Engineering and Measurement (ESEM)

作者： Sedano, Todd Ralph, Paul Peraire, Cecile Pivotal 3495 Deer Creak Rd Palo Alto CA 94304 USA Univ Auckland Auckland New Zealand Carnegie Mellon Unveristy Silicon Valley Campus Moffett Field CA 94035 USA

ISBN: (纸本)9781450344272

Context: Conventional wisdom says that team disruptions (like team churn) should be avoided. However, we have observed software development projects that succeed despite high disruption. Objective: the purpose of this paper is to understand how to develop software effectively, even in the face of team disruption. Method: We followed Constructivist Grounded theory. the primary researcher conducted participant-observation of several projects at Pivotal (a software development company), and interviewed 21 software engineers, interaction designers, and product managers. the researcher iteratively sampled and analyzed the collected data until achieving theoretical saturation. Results: this paper introduces a descriptive theory of Sustainable Software Development. the theory encompasses principles, policies, and practices aiming at removing knowledge silos and improving code quality (including discoverability and readability), hence leading to development sustainability. Limitations: While the results are highly relevant to the observed projects at Pivotal, the outcomes may not be transferable to other software development organizations with different software development cultures. Conclusion: the theory refines and extends the understanding of Extreme programming by adding a few principles, policies, and practices (like the unique Overlapping Pair Rotation practice) and aligning these principles, policies, and practices towards the business goal of sustainability.

关键词： Extreme programming Grounded theory Code ownership Sustainable software development

来源：评论

学校读者我要写书评

暂无评论

PPoPP 2014 - Proceedings of the 2014 acm SIGPLAN symposium on principles and practice of parallel programming

PPoPP 2014 - Proceedings of the 2014 ACM SIGPLAN Symposium o...

引用

2014 19th acm SIGPLAN symposium on principles and practice of parallel programming, PPoPP 2014

ISBN: (纸本)9781450326568

the proceedings contain 43 papers. the topics discussed include: predator: predictive false sharing detection;concurrency testing using schedule bounding: an empirical study;trace driven dynamic deadlock detection and reproduction;efficient search for inputs causing high floating-point errors;portable, MPI-interoperable coarray Fortran;eliminating global interpreter locks in ruby through hardware transactional memory;leveraging hardware message passing for efficient thread synchronization;well-structured futures and cache locality;time-warp: lightweight abort minimization in transactional memory;beyond parallel programming with domain specific languages;a decomposition for in-place matrix transposition;in-place transposition of rectangular matrices on accelerators;and parallelizing dynamic programming through rank convergence.

关键词： FORTRAN (programming language)

来源：评论

学校读者我要写书评

暂无评论

Tiles: A new language mechanism for heterogeneous parallelism 2015

Tiles: A new language mechanism for heterogeneous parallelis...

引用

20th acm SIGPLAN symposium on principles and practice of parallel programming, PPoPP 2015

作者： Chen, Yifeng Cui, Xiang Mei, Hong HCST Key Lab. School of EECS Peking University Beijing100871 China

ISBN: (纸本)9781450332057

this paper studies the essence of heterogeneity from the perspective of language mechanism design. the proposed mechanism, called tiles, is a program construct that bridges two relative levels of computation: an outer level of source data in larger, slower or more distributed memory and an inner level of data blocks in smaller, faster or more localized memory.

关键词： parallel programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：