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

acm sigplan conference on programming language design and implementation

作者： Tony Nowatzki Michael Sartin-Tarm Lorenzo De Carli Karthikeyan Sankaralingam Cristian Estan Behnam Robatmili University of Wisconsin-Madison Broadcom Qualcomm Research Silicon Valley

ISBN: (纸本)9781450320146

Specialized execution using spatial architectures provides energy efficient computation, but requires effective algorithms for spatially scheduling the computation. Generally, this has been solved with architecture-specific heuristics, an approach which suffers from poor compiler/architect productivity, lack of insight on optimality, and inhibits migration of techniques between architectures. Our goal is to develop a scheduling framework usable for all spatial architectures. To this end, we expresses spatial scheduling as a constraint satisfaction problem using Integer Linear programming (ILP). We observe that architecture primitives and scheduler responsibilities can be related through five abstractions: placement of computation, routing of data, managing event timing, managing resource utilization, and forming the optimization objectives. We encode these responsibilities as 20 general ILP constraints, which are used to create schedulers for the disparate TRIPS, DySER, and PLUG architectures. Our results show that a general declarative approach using ILP is implementable, practical, and typically matches or outperforms specialized schedulers.

关键词： Spatial Architectures Spatial Architecture Scheduling Integer Linear programming

来源：评论

学校读者我要写书评

暂无评论

P: Safe Asynchronous Event-Driven programming 13

P: Safe Asynchronous Event-Driven Programming

引用

acm sigplan conference on programming language design and implementation

作者： Ankush Desai Vivek Gupta Ethan Jackson Shaz Qadeer Sriram Rajamani Damien Zufferey Microsoft IST Austria

ISBN: (纸本)9781450320146

We describe the design and implementation of P, a domain-specific language to write asynchronous event driven code. P allows the programmer to specify the system as a collection of interacting state machines, which communicate with each other using events. P unifies modeling and programming into one activity for the programmer. Not only can a P program be compiled into executable code, but it can also be tested using model checking techniques. P allows the programmer to specify the environment, used to "close" the system during testing, as nondeterministic ghost machines. Ghost machines are erased during compilation to executable code; a type system ensures that the erasure is semantics preserving. The P language is designed so that a P program can be checked for responsiveness-the ability to handle every event in a timely manner. By default, a machine needs to handle every event that arrives in every state. But handling every event in every state is impractical. The language provides a notion of deferred events where the programmer can annotate when she wants to delay processing an event. The default safety checker looks for presence of unhandled events. The language also provides default liveness checks that an event cannot be potentially deferred forever. P was used to implement and verify the core of the USB device driver stack that ships with Microsoft Windows 8. The resulting driver is more reliable and performs better than its prior incarnation (which did not use P); we have more confidence in the robustness of its design due to the language abstractions and verification provided by P.

关键词： Domain-specific language Device driver Event-driven programming State machine Verification Systematic testing state machines Computer personnel event-driven programming Verification device drivers Phosphorus Executable code Device Programmer Component application-specific language language Microsoft Windows(software)

来源：评论

学校读者我要写书评

暂无评论

Static Analysis for Probabilistic Programs: Inferring Whole Program Properties from Finitely Many Paths 13

Static Analysis for Probabilistic Programs: Inferring Whole ...

引用

acm sigplan conference on programming language design and implementation

作者： Sriram Sankaranarayanan Aleksandar Chakarov Sumit Gulwani University of Colorado Microsoft Research

ISBN: (纸本)9781450320146

We propose an approach for the static analysis of probabilistic programs that sense, manipulate, and control based on uncertain data. Examples include programs used in risk analysis, medical decision making and cyber-physical systems. Correctness properties of such programs take the form of queries that seek the probabilities of assertions over program variables. We present a static analysis approach that provides guaranteed interval bounds on the values (assertion probabilities) of such queries. First, we observe that for probabilistic programs, it is possible to conclude facts about the behavior of the entire program by choosing a finite, adequate set of its paths. We provide strategies for choosing such a set of paths and verifying its adequacy. The queries are evaluated over each path by a combination of symbolic execution and probabilistic volume-bound computations. Each path yields interval bounds that can be summed up with a "coverage" bound to yield an interval that encloses the probability of assertion for the program as a whole. We demonstrate promising results on a suite of benchmarks from many different sources including robotic manipulators and medical decision making programs.

关键词： Probabilistic programming Program Verification Volume Bounding Symbolic Execution Monte-Carlo Sampling

来源：评论

学校读者我要写书评

暂无评论

EXOCHI: Architecture and programming environment for a heterogeneous multi-core multithreaded system

引用

acm sigplan NOTICES 2007年第6期42卷 156-166页

作者： Wang, Perry H. Collins, Jamison D. Chinya, Gautham N. Hong Jiang Xinmin Tian Girkar, Milind Yang, Nick Y. Lueh, Guei-Yuan Wang, Hong Intel Corp Microprocessor Technol Labs Microarchitecture Res Lab Santa Clara CA 95051 USA Intel Corp Chipset Grp Santa Clara CA 95051 USA Intel Corp Software Solut Corp Intel Compiler Lab Santa Clara CA 95051 USA

Future mainstream microprocessors will likely integrate specialized accelerators, such as GPUs, onto a single die to achieve better performance and power efficiency. However, it remains a keen challenge to program such a heterogeneous multi-core platform, since these specialized accelerators feature ISAs and functionality that are significantly different from the general purpose CPU cores. In this paper, we present EXOCHI: (1) Exoskeleton Sequencer (EXO), an architecture to represent heterogeneous accelerators as ISA-based MIMD architecture resources, and a shared virtual memory heterogeneous multithreaded program execution model that tightly couples specialized accelerator cores with general purpose CPU cores, and (2) C for Heterogeneous Integration (CHI), an integrated C/C++ programming environment that supports accelerator-specific inline assembly and domain-specific languages. The CHI compiler extends the OpenMP pragma for heterogeneous multithreading programming, and produces a single fat binary with code sections corresponding to different instruction sets. The runtime can judiciously spread parallel computation across the heterogeneous cores to optimize performance and power. We have prototyped the EXO architecture on a physical heterogeneous platform consisting of an Intel (R) Core (TM) 2 Duo processor and an 8-core 32-thread Intel (R) Graphics Media Accelerator X3000. In addition, we have implemented the CHI integrated programming environment with the Intel (R) C++ Compiler, runtime toolset, and debugger. On the EXO prototype system, we have enhanced a suite of production-quality media kernels for video and image processing to utilize the accelerator through the CHI programming interface, achieving significant speedup (1.41X to 10.97X) over execution on the IA32 CPU alone.

关键词： performance design languages heterogeneous multi-cores GPU OpenMP

来源：评论

学校读者我要写书评

暂无评论

TRANSIT: Specifying Protocols with Concolic Snippets 13

TRANSIT: Specifying Protocols with Concolic Snippets

引用

acm sigplan conference on programming language design and implementation

作者： Abhishek Udupa Sela Mador-Haim Arun Raghavan Milo M. K. Martin Jyotirmoy V. Deshmukh Rajeev Alur University of Pennsylvania Toyota Technical Center

ISBN: (纸本)9781450320146

With the maturing of technology for model checking and constraint solving, there is an emerging opportunity to develop programming tools that can transform the way systems are specified. In this paper, we propose a new way to program distributed protocols using concolic snippets. Concolic snippets are sample execution fragments that contain both concrete and symbolic values. The proposed approach allows the programmer to describe the desired system partially using the traditional model of communicating extended finite-state-machines (EFSM), along with high-level invariants and concrete execution fragments. Our synthesis engine completes an EFSM skeleton by inferring guards and updates from the given fragments which is then automatically analyzed using a model checker with respect to the desired invariants. The counterexamples produced by the model checker can then be used by the programmer to add new concrete execution fragments that describe the correct behavior in the specific scenario corresponding to the counterexample. We describe TRANSIT, a language and prototype implementation of the proposed specification methodology for distributed protocols. Experimental evaluations of TRANSIT to specify cache coherence protocols show that (1) the algorithm for expression inference from concolic snippets can synthesize expressions of size 15 involving typical operators over commonly occurring types, (2) for a classical directory-based protocol, TRANSIT automatically generates, in a few seconds, a complete implementation from a specification consisting of the EFSM structure and a few concrete examples for every transition, and (3) a published partial description of the SGI Origin cache coherence protocol maps directly to symbolic examples and leads to a complete implementation in a few iterations, with the programmer correcting counterexamples resulting from underspecified transitions by adding concrete examples in each iteration.

关键词： Program Synthesis Distributed Protocol Synthesis Cache Coherence Protocols programming by Example

来源：评论

学校读者我要写书评

暂无评论

General Data Structure Expansion for Multi-threading 13

General Data Structure Expansion for Multi-threading

引用

acm sigplan conference on programming language design and implementation

作者： Hongtao Yu Hou-Jen Ko Zhiyuan Li Department of Computer Science Purdue University

ISBN: (纸本)9781450320146

Among techniques for parallelizing sequential codes, privatization is a common and significant transformation performed by both compilers and runtime parallelizing systems. Without privatization, repetitive updates to the same data structures often introduce spurious data dependencies that hide the inherent parallelism. Unfortunately, it remains a significant challenge to compilers to automatically privatize dynamic and recursive data structures which appear frequently in real applications written in languages such as C/C++. This is because such languages lack a naming mechanism to define the address range of a pointer-based data structure, in contrast to arrays with explicitly declared bounds. In this paper we present a novel solution to this difficult problem by expanding general data structures such that memory accesses issued from different threads to contentious data structures are directed to different data fields. Based on compile-time type checking and a data dependence graph, this aggressive extension to the traditional scalar and array expansion isolates the address ranges among different threads, without struggling with privatization based on thread-private stacks, such that the targeted loop can be effectively parallelized. With this method fully implemented in GCC, experiments are conducted on a set of programs from well-known benchmark suites such as Mibench, MediaBench II and SPECint. Results show that the new approach can lead to a high speedup when executing the transformed code on multiple cores.

关键词： Parallelization Privatization Multithreading Algorithms languages Performance Privatisation Multithreading Data structures language parallelization data dependency compilers algorithms type checking

来源：评论

学校读者我要写书评

暂无评论

Fast RMWs for TSO: Semantics and implementation 13

Fast RMWs for TSO: Semantics and Implementation

引用

acm sigplan conference on programming language design and implementation

作者： Bharghava Rajaram Vijay Nagarajan Susmit Sarkar Marco Elver University of Edinburgh University of St Andrews

ISBN: (纸本)9781450320146

Read-Modify-Write (RMW) instructions are widely used as the building blocks of a variety of higher level synchronization constructs, including locks, barriers, and lock-free data structures. Unfortunately, they are expensive in architectures such as x86 and SPARC which enforce (variants of) Total-Store-Order (TSO). A key reason is that RMWs in these architectures are ordered like a memory barrier, incurring the cost of a write-buffer drain in the critical path. Such strong ordering semantics are dictated by the requirements of the strict atomicity definition (type-1) that existing TSO RMWs use. Programmers often do not need such strong semantics. Besides, weakening the atomicity definition of TSO RMWs, would also weaken their ordering - thereby leading to more efficient hardware implementations. In this paper we argue for TSO RMWs to use weaker atomicity definitions - we consider two weaker definitions: type-2 and type-3, with different relaxed ordering differences. We formally specify how such weaker RMWs would be ordered, and show that type-2 RMWs, in particular, can seamlessly replace existing type-1 RMWs in common synchronization idioms - except in situations where a type-1 RMW is used as a memory barrier. Recent work has shown that the new C/C++11 concurrency model can be realized by generating conventional (type-1) RMWs for C/C++11 SC-atomic-writes and/or SC-atomic-reads. We formally prove that this is equally valid using the proposed type-2 RMWs; type-3 RMWs, on the other hand, could be used for SC-atomic-reads (and optionally SC-atomic-writes). We further propose efficient microarchitectural implementations for type-2 (type-3) RMWs - simulation results show that our implementation reduces the cost of an RMW by up to 58.9% (64.3%), which translates into an overall performance improvement of up to 9.0% (9.2%) on a set of parallel programs, including those from the SPLASH-2, PARSEC, and STAMP benchmarks.

关键词： Read-Modify-Write (RMW) Total-Store-Order (TSO) Atomics design Performance Experimentation

来源：评论

学校读者我要写书评

暂无评论

CLAP: Recording Local Executions to Reproduce Concurrency Failures 13

CLAP: Recording Local Executions to Reproduce Concurrency Fa...

引用

acm sigplan conference on programming language design and implementation

作者： Jeff Huang Charles Zhang Julian Dolby Hong Kong University of Science and Technology IBM Thomas J. Watson Research Center

ISBN: (纸本)9781450320146

We present CLAP, a new technique to reproduce concurrency bugs. CLAP has two key steps. First, it logs thread local execution paths at runtime. Second, offline, it computes memory dependencies that accord with the logged execution and are able to reproduce the observed bug. The second step works by combining constraints from the thread paths and constraints based on a memory model, and computing an execution with a constraint solver. CLAP has four major advantages. First, logging purely local execution of each thread is substantially cheaper than logging memory interactions, which enables CLAP to be efficient compared to previous approaches. Second, our logging does not require any synchronization and hence with no added memory barriers or fences; this minimizes perturbation and missed bugs due to extra synchronizations foreclosing certain racy behaviors. Third, since it uses no synchronization, we extend CLAP to work on a range of relaxed memory models, such as TSO and PSO, in addition to sequential consistency. Fourth, CLAP can compute a much simpler execution than the original one, that reveals the bug with minimal thread context switches. To mitigate the scalability issues, we also present an approach to parallelize constraint solving, which theoretically scales our technique to programs with arbitrary execution length. Experimental results on a variety of multithreaded benchmarks and real world concurrent applications validate these advantages by showing that our technique is effective in reproducing concurrency bugs even under relaxed memory models; furthermore, it is significantly more efficient than a state-of-the-art technique that records shared memory dependencies, reducing execution time overhead by 45% and log size by 88% on average.

关键词： Concurrency Bug Reproduction Local Execution Constraint Solving Algorithms design Performance Theory

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：