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

The tao of parallelism in algorithms 11

32nd acm conference on programming language design and implementation, PLDI 2011

作者： Pingali, Keshav Nguyen, Donald Kulkarni, Milind Burtscher, Martin Hassaan, M. Amber Kaleem, Rashid Lee, Tsung-Hsien Lenharth, Andrew Manevich, Roman Méndez-Lojo, Mario Prountzos, Dimitrios Sui, Xin Department of Computer Science University of Texas Austin TX United States Electrical and Computer Engineering University of Texas Austin TX United States Institute for Computational Engineering and Sciences University of Texas Austin TX United States Department of Computer Science Texas State University San Marcos TX United States School of Electrical and Computer Engineering Purdue University United States

ISBN: (纸本)9781450306638

For more than thirty years, the parallel programming community has used the dependence graph as the main abstraction for reasoning about and exploiting parallelism in "regular" algorithms that use dense arrays, such as finite-differences and FFTs. In this paper, we argue that the dependence graph is not a suitable abstraction for algorithms in new application areas like machine learning and network analysis in which the key data structures are "irregular" data structures like graphs, trees, and sets. To address the need for better abstractions, we introduce a data-centric formulation of algorithms called the operator formulation in which an algorithm is expressed in terms of its action on data structures. This formulation is the basis for a structural analysis of algorithms that we call tao-analysis. Tao-analysis can be viewed as an abstraction of algorithms that distills out algorithmic properties important for parallelization. It reveals that a generalized form of data-parallelism called amorphous data-parallelism is ubiquitous in algorithms, and that, depending on the tao-structure of the algorithm, this parallelism may be exploited by compile-time, inspector-executor or optimistic parallelization, thereby unifying these seemingly unrelated parallelization techniques. Regular algorithms emerge as a special case of irregular algorithms, and many application-specific optimization techniques can be generalized to a broader context. These results suggest that the operator formulation and tao-analysis of algorithms can be the foundation of a systematic approach to parallel programming. © 2011 acm.

关键词： Parallel programming

来源：评论

学校读者我要写书评

暂无评论

language-independent sandboxing of just-in-time compilation and self-modifying code 11

引用

32nd acm conference on programming language design and implementation, PLDI 2011

作者： Ansel, Jason Marchenko, Petr Erlingsson, Ulfar Taylor, Elijah Chen, Brad Schuff, Derek L. Sehr, David Biffle, Cliff L. Yee, Bennet Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology United States University College London United Kingdom Google Inc. United States

ISBN: (纸本)9781450306638

When dealing with dynamic, untrusted content, such as on the Web, software behavior must be sandboxed, typically through use of a language like JavaScript. However, even for such specially-designed languages, it is difficult to ensure the safety of highly-optimized, dynamic language runtimes which, for efficiency, rely on advanced techniques such as Just-In-Time (JIT) compilation, large libraries of native-code support routines, and intricate mechanisms for multi-threading and garbage collection. Each new runtime provides a new potential attack surface and this security risk raises a barrier to the adoption of new languages for creating untrusted content. Removing this limitation, this paper introduces general mechanisms for safely and efficiently sandboxing software, such as dynamic language runtimes, that make use of advanced, low-level techniques like runtime code modification. Our language-independent sandboxing builds on Software-based Fault Isolation (SFI), a traditionally static technique. We provide a more flexible form of SFI by adding new constraints and mechanisms that allow safety to be guaranteed despite runtime code modifications. We have added our extensions to both the x86-32 and x86-64 variants of a production-quality, SFI-based sandboxing platform;on those two architectures SFI mechanisms face different challenges. We have also ported two representative language platforms to our extended sandbox: the Mono common language runtime and the V8 JavaScript engine. In detailed evaluations, we find that sandboxing slowdown varies between different benchmarks, languages, and hardware platforms. Overheads are generally moderate and they are close to zero for some important benchmark/platform combinations. © 2011 acm.

关键词： Dynamics

来源：评论

学校读者我要写书评

暂无评论

Secure Distributed programming with Value-Dependent Types 11

Secure Distributed Programming with Value-Dependent Types

引用

16th acm sigplan International conference on Functional programming (ICFP 11)

作者： Swamy, Nikhil Chen, Juan Fournet, Cedric Strub, Pierre-Yves Bhargavan, Karthikeyan Yang, Jean Microsoft Res Redmond WA 98052 USA

ISBN: (纸本)9781450308656

Distributed applications are difficult to program reliably and securely. Dependently typed functional languages promise to prevent broad classes of errors and vulnerabilities, and to enable program verification to proceed side-by-side with development. However, as recursion, effects, and rich libraries are added, using types to reason about programs, specifications, and proofs becomes challenging. We present F-star, a full-fledged design and implementation of a new dependently typed language for secure distributed programming. Unlike prior languages, F-star provides arbitrary recursion while maintaining a logically consistent core;it enables modular reasoning about state and other effects using affine types;and it supports proofs of refinement properties using a mixture of cryptographic evidence and logical proof terms. The key mechanism is a new kind system that tracks several sub-languages within F-star and controls their interaction. F-star subsumes two previous languages, F7 and Fine. We prove type soundness (with proofs mechanized in Coq) and logical consistency for F-star. We have implemented a compiler that translates F-star to NET bytecode, based on a prototype for Fine. F-star provides access to libraries for concurrency, networking, cryptography, and interoperability with C#, F#, and the other .NET languages. The compiler produces verifiable binaries with 60% code size overhead for proofs and types, as much as a 45x improvement over the Fine compiler, while still enabling efficient bytecode verification. To date, we have programmed and verified more than 20,000 lines of F-star including (1) new schemes for multi-party sessions;(2) a zero-knowledge privacy-preserving payment protocol;(3) a provenance-aware curated database;(4) a suite of 17 web-browser extensions verified for authorization properties;and (5) a cloud-hosted multi-tier web application with a verified reference monitor.

关键词： Security type systems refinement types

来源：评论

学校读者我要写书评

暂无评论

Delegated Isolation 11

Delegated Isolation

引用

2011 acm International conference on Object Oriented programming Systems languages and Applications

作者： Lublinerman, Roberto Zhao, Jisheng Budimlic, Zoran Chaudhuri, Swarat Sarkar, Vivek Penn State Univ University Pk PA 16802 USA Rice Univ Houston TX 77251 USA

ISBN: (纸本)9781450309400

Isolation-the property that a task can access shared data without interference from other tasks-is one of the most basic concerns in parallel programming. In this paper, we present Aida, a new model of isolated execution for parallel programs that perform frequent, irregular accesses to pointer-based shared data structures. The three primary benefits of Aida are dynamism, safety and liveness guarantees, and programmability. First, Aida allows tasks to dynamically select and modify, in an isolated manner, arbitrary fine-grained regions in shared data structures, all the while maintaining a high level of concurrency. Consequently, the model can achieve scalable parallelization of regular as well as irregular shared-memory applications. Second, the model offers freedom from data races, deadlocks, and livelocks. Third, no extra burden is imposed on programmers, who access the model via a simple, declarative isolation construct that is similar to that for transactional memory. The key new insight in Aida is a notion of delegation among concurrent isolated tasks (known in Aida as assemblies). Each assembly A is equipped with a region in the shared heap that it owns-the only objects accessed by A are those it owns, guaranteeing race-freedom. The region owned by A can grow or shrink flexibly-however, when A needs to own a datum owned by B, A delegates itself, as well as its owned region, to B. From now on, B has the responsibility of re-executing the task A set out to complete. Delegation as above is the only inter-assembly communication primitive in Aida. In addition to reducing contention in a local, data-driven manner, it guarantees freedom from deadlocks and livelocks. We offer an implementation of Aida on top of the Habanero Java parallel programming language. The implementation employs several novel ideas, including the use of a union-find data structure to represent tasks and the regions that they own. A thorough evaluation using several irregular data-parallel bench

关键词： languages design Isolation programming abstractions Irregular parallelism Contention

来源：评论

学校读者我要写书评

暂无评论

Modularizing Crosscutting Concerns with Ptolemy 11

Modularizing Crosscutting Concerns with Ptolemy

引用

10th International conference on Aspect-Oriented Software Development (AOSD)

作者： Rajan, Hridesh Leavens, Gary T. Dyer, Robert Bagherzadeh, Mehdi Iowa State Univ Ames IA 50011 USA Univ Cent Florida Orlando FL 32816 USA

ISBN: (纸本)9781450305563

This tutorial will provide an introduction to Ptolemy. Ptolemy is a programming language whose goals are to improve a software engineer's ability to separate conceptual concerns, while preserving encapsulation of object-oriented code and the ability of programmers to modularly reason about their code. In particular, Ptolemy's features are useful towards modularization of cross-cutting concerns. A cross-cutting concern is a requirement whose implementation is spread across and mixed with the code of other requirements. There has been attempts to improve separation of cross-cutting concerns, e.g. by aspect-oriented and implicit-invocation languages, but none give software developers textual separation of concerns and modular reasoning at the same time. Ptolemy has both these properties important for scalable software engineering. Ptolemy's event types provide a well-defined interface between object-oriented code and cross-cutting code. This in turn enables separate type-checking and compilation. Ptolemy also provides a novel and practical specification mechanism that we call translucid contracts. A translucid contracts allows developers to reason about the control effects of the object-oriented code and cross-cutting code modularly. This tutorial will proceed by discussing the goals of the Ptolemy programming language. We will then discuss Ptolemy's programming features and its specification features by way of several hands-on exercises. We will conclude with pointers to ongoing work on design, implementation and verification of Ptolemy programs.

关键词： modular reasoning aspect-oriented programming languages implicit invocation translucid contracts aspect-oriented interfaces Ptolemy

来源：评论

学校读者我要写书评

暂无评论

EScala: Modular event-driven object interactions in scala 11

EScala: Modular event-driven object interactions in scala

引用

Proceedings of the tenth international conference on Aspect-oriented software development

作者： Gasiunas, Vaidas Satabin, Lucas Mezini, Mira Núñez, Angel Noyé, Jacques Software Technology Group Technische Universität Darmstadt Darmstadt Germany École des Mines de Nantes Nantes France

ISBN: (纸本)9781450305563

Event-driven programming style in OO languages based on imperatively triggered events does not support separate and more declarative event definitions by composition or transformation of other events. AO language mechanisms for defining events as declarative queries over implicitly available low-level events seem good candidates to approach these problems. However, being designed for modularizing mostly globally scoped, crosscutting concerns, AO mechanisms deliberately break with the OO design and modular reasoning style and are thus inappropriate for addressing modularity concerns related to event-based interactions in OO designs. The contribution of this paper is a language design that combines imperatively triggered events with AO-like mechanisms that are specifically designed to address modularity issues in event-driven object-oriented designs. In particular, they seamlessly integrate with OO-style encapsulation, late binding, and modular reasoning. We present an efficient and type-safe implementation of the proposed design as an extension to Scala.

关键词： Aspect oriented programming

来源：评论

学校读者我要写书评

暂无评论

Upcall dispatcher aspects: Combining modularity with efficiency in the CiAO IP stack

Upcall dispatcher aspects: Combining modularity with efficie...

引用

1st Workshop on Modularity in Systems Software, MISS 2011, Co-located with the 10th International conference on Aspect-Oriented Software Development, AOSD.11

作者： Streicher, Jochen Borchert, Christoph Spinczyk, Olaf Technische Universität Dortmund Computer Science 12 - Embedded System Software Germany

ISBN: (纸本)9781450306478

Network protocol stacks are an important ingredient of today's infrastructure software. For instance, all state-of-the-art operating systems for PCs and the server market come with a TCP/IP stack. The design of protocol stacks and their layered structure has been studied for decades. However, in practice, implementations often do not follow the clean textbook design consequently. This especially holds for the domain of embedded TCP/IP stacks where minimal resource consumption is crucial. In this work we present an analysis that explains the reason for this dilemma. We have also developed a very simple solution that is based on common aspect-oriented programming language features: Upcall Dispatcher Aspects. In a case study this concept has been repeatedly applied as an AspectC++ idiom in the implementation of the CiAO TCP/IP stack, which we compared to several traditional implementations. Besides reflecting a clean design at the implementation level, our protocol stack, which mainly targets the domain of resource-constrained embedded systems, even outperforms the other solutions with respect to resource consumption and various "-ilities". Copyright 2011 acm.

关键词： Aspect oriented programming

来源：评论

学校读者我要写书评

暂无评论

Lightweight Modular Staging: A Pragmatic Approach to Runtime Code Generation and Compiled DSLs

引用

acm sigplan NOTICES 2011年第2期46卷 127-136页

作者： Rompf, Tiark Odersky, Martin Ecole Polytech Fed Lausanne CH-1015 Lausanne Switzerland

Software engineering demands generality and abstraction, performance demands specialization and concretization. Generative programming can provide both, but developing high-quality program generators takes a large effort, even if a multi-stage programming language is used. We present lightweight modular staging, a library-based multi-stage programming approach that breaks with the tradition of syntactic quasi-quotation and instead uses only types to distinguish between binding times. Through extensive use of component technology, lightweight modular staging makes an optimizing compiler framework available at the library level, allowing programmers to tightly integrate domain-specific abstractions and optimizations into the generation process. We argue that lightweight modular staging enables a form of language virtualization, i.e. allows to go from a pure-library embedded language to one that is practically equivalent to a stand-alone implementation with only modest effort.

关键词： design languages Code Generation Multi-stage programming Domain-specific languages language Virtualization

来源：评论

学校读者我要写书评

暂无评论

Linearity and PCF: a Semantic Insight! 11

Linearity and PCF: a Semantic Insight!

引用

16th acm sigplan International conference on Functional programming (ICFP 11)

作者： Gaboardi, Marco Paolini, Luca Piccolo, Mauro Univ Bologna INRIA Focus Team Dip Sci Informaz I-40127 Bologna Italy Univ Turin Dipartimento Informat I-10149 Turin Italy

ISBN: (纸本)9781450308656

Linearity is a multi-faceted and ubiquitous notion in the analysis and the development of programming language concepts. We study linearity in a denotational perspective by picking out programs that correspond to linear functions between coherence spaces. We introduce a language, named SlPCF(star), that increases the higher-order expressivity of a linear core of PCF by means of new operators related to exception handling and parallel evaluation. SlPCF(star) allows us to program all the finite elements of the model and, consequently, it entails a full abstraction result that makes the reasoning on the equivalence between programs simpler. Denotational linearity provides also crucial information for the operational evaluation of programs. We formalize two evaluation machineries for the language. The first one is an abstract and concise operational semantics designed with the aim of explaining the new operators, and is based on an infinite-branching search of the evaluation space. The second one is more concrete and it prunes such a space, by exploiting the linear assumptions. This can also be regarded as a base for an implementation.

关键词： languages Theory design PCF Linear Logic Denotational Semantics Operational Semantics

来源：评论

学校读者我要写书评

暂无评论

Reactive Imperative programming with Dataflow Constraints

引用

acm sigplan NOTICES 2011年第10期46卷 407-426页

作者： Demetrescu, Camil Finocchi, Irene Ribichini, Andrea Sapienza Univ Rome Dept Comp & Syst Sci Rome Italy Sapienza Univ Rome Dept Comp Sci Rome Italy

Dataflow languages provide natural support for specifying constraints between objects in dynamic applications, where programs need to react efficiently to changes of their environment. Researchers have long investigated how to take advantage of dataflow constraints by embedding them into procedural languages. Previous mixed imperative/dataflow systems, however, require syntactic extensions or libraries of ad hoc data types for binding the imperative program to the dataflow solver. In this paper we propose a novel approach that smoothly combines the two paradigms without placing undue burden on the programmer. In our framework, programmers can define ordinary statements of the imperative host language that enforce constraints between objects stored in special memory locations designated as "reactive". Differently from previous approaches, reactive objects can be of any legal type in the host language, including primitive data types, pointers, arrays, and structures. Statements defining constraints are automatically re-executed every time their input memory locations change, letting a program behave like a spreadsheet where the values of some variables depend upon the values of other variables. The constraint solving mechanism is handled transparently by altering the semantics of elementary operations of the host language for reading and modifying objects. We provide a formal semantics and describe a concrete embodiment of our technique into C/C++, showing how to implement it efficiently in conventional platforms using off-the-shelf compilers. We discuss common coding idioms and relevant applications to reactive scenarios, including incremental computation, observer design pattern, and data structure repair. The performance of our implementation is compared to ad hoc problem-specific change propagation algorithms, as well as to language-centric approaches such as self-adjusting computation and subject/observer communication mechanisms, showing that the proposed approa

关键词： Algorithms design experimentation languages Reactive programming dataflow programming imperative programming constraint solving incremental computation observer design pattern data structure repair

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：