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 arra...
详细信息
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 di...
详细信息
Writing correct and efficient concurrent programs still remains a challenge. Explicit concurrency is difficult, error prone, and creates code which is hard to maintain and debug. This type of concurrency also treats m...
详细信息
ISBN:
(纸本)9781450301541
Writing correct and efficient concurrent programs still remains a challenge. Explicit concurrency is difficult, error prone, and creates code which is hard to maintain and debug. This type of concurrency also treats modular program design and concurrency as separate goals, where modularity often suffers. To solve these problems, we are designing a new language that we call Panini. In this paper, we focus on Panini's asynchronous, typed events which reconcile the modularity goal promoted by the implicit invocation design style with the concurrency goal of exposing potential concurrency between the execution of subjects and observers. Since modularity is improved and concurrency is implicit in Panini, programs are easier to reason about and maintain. The language incorporates a static analysis to determine potential conflicts between handlers and a dynamic analysis which uses the conflict information to determine a safe order for handler invocation. This mechanism avoids races and deadlocks entirely, yielding programs with a guaranteed deterministic semantics. To evaluate our languagedesign and implementation we show several examples of its usage as well as an empirical study of program performance. We found that not only is developing and understanding Panini programs significantly easier compared to standard concurrent object-oriented programs, but also performance of Panini programs is comparable to their equivalent hand-tuned versions written using Java's fork-join framework.
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 pro...
详细信息
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.
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 execut...
详细信息
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 programminglanguage. 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
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 mech...
详细信息
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 languagedesign 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.
We present an online lightweight auto-tuning system for shared-memory parallel programs. We employ an online adaptive tuning algorithm that is based on performance measurements, to adapt to performance variability tha...
详细信息
This tutorial will provide an introduction to Ptolemy. Ptolemy is a programminglanguage whose goals are to improve a software engineer's ability to separate conceptual concerns, while preserving encapsulation of ...
详细信息
ISBN:
(纸本)9781450305563
This tutorial will provide an introduction to Ptolemy. Ptolemy is a programminglanguage 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 programminglanguage. 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.
This paper explores the feasibility of implementing pattern matching for the Go programminglanguage. The design of pattern matching is taken from Scala, and reimplemented using Go's constructs and new language ex...
详细信息
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 pr...
详细信息
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 programminglanguage 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.
暂无评论