Final Program.
| Time |
Description |
| 10:00 - 10:30 |
Automatically Inferring Sound Dataflow Functions from Dataflow Fact Schemas -- Sorin Lerner (UCSD / UW) |
| 10:30 - 11:00 |
Register Allocation via Coloring
of Chordal Graphs -- Fernando Magno Quintão Pereira
(UCLA)
|
| 11:00 - 11:30 |
Event-Driven Programming using ResponderJ -- Brian Chin (UCLA) |
| 11:30 - 12:00 |
Sneaking Existentials into Java -- Kim Bruce (Pomona College) |
| 12:00 - 12:30 |
TBA |
| 12:30 - 14:00 |
Lunch |
| 14:00 - 14:30 |
Software Defined Acoustic Modem -- Ryan Kastner (UCSB) |
| 14:30 - 15:00 |
Speculations:
Improving Performance and Reliability in Distributed Systems -- Cristian
Tapus (Caltech)
|
| 15:00 - 15:30 |
Enforcing Timing Policies with Code Certification -- Joseph C. Vanderwaart
(Pomona College) |
| 15:30 - 16:00 |
Break |
| 16:00 - 16:30 |
Distributed Sense and Respond System -- Agostino Capponi (Caltech) |
| 16:30 - 17:00 |
NavP: Multithreaded and Structured Distributed Parallel Programming --
Lei Pan ( JPL and UC Irvine) |
| 17:00 - 17:30 |
Scoped Component Adaptation with Expanders -- Alessandro Warth (UCLA) |
| 17:30 - 18:00 |
A Type System for Distributed Arrays
-- Christian Grothoff (UCLA) |
The list of abstracts is:
Distributed Sense and Respond System -- Agostino Capponi (Caltech)
Distributed sense and respond systems can be specified using a set of rules of the
form: when a predicate P begins to hold then execute action e,
where P is a predicate on the history of global states of the
system. The system initiates action e when the value of predicate P
changes from false to true. Processes in a distributed system do not have access to the global system state; they only have access to their local states. Nodes have to estimate the global state by fusing local state information received from messages sent by multiple nodes, each with information about its local state. Nodes can compute only certain types of predicates - namely stable predicates - on global states exactly.
We study the problem of responding to both unstable and
stable situations; therefore, we have to deal with estimation error.
Our problem may be formally stated as follows. Given a set of pairs (P, e), where P is a predicate on the history of global states of a system and e is an action; for
each pair we are given the benefits of executing action e correctly and the costs of executing e incorrectly. We study what strategies reduce message rates, and what are the effects of
these strategies on computation and bandwidth (bits/second) requirements.
Software Defined Acoustic Modem -- Ryan Kastner (UCSB)
The aquatic research community is rapidly equipping ecological sites with a broad range of sensors and instruments. However, the development of aquatic sensing networks is significantly lagging terrestrial counterparts. It is widely recognized that an aquatic counterpart to low cost, low power, wireless radios is needed to advance the state-of-the-art in underwater sensor networks. Unfortunately, there are few open-architecture, low power and low cost underwater acoustic modems. Existing modems either use proprietary hardware or digital signal processors for signal processing. While digital signal processors are sufficient for simple modulation, they cannot handle the computational complexity required by more complex modulation protocols.
This talk describes our alternative hardware platform for wireless underwater communication. We are using reconfigurable devices to create a software defined acoustic modem. In order to realize a software defined signal processing system, we must develop tools and methodologies to can automatically map communication protocols to hardware. I will describe some of our research aimed at providing signal processing application designers with basic tools that allow them to quickly map their protocols into reconfigurable hardware. I will present a design flow from high level application specification to a bitstream that can be used to program a modern, high performance FPGA. Our design flow is unique in that it treats the FPGA as a two dimensional array of configurable data paths. As such, the distribution of the application data plays a large role in the performance of the application mapping. I will discuss our optimizations for partitioning data across the complex memory hierarchy seen in modern reconfigurable architectures. To motivate our design flow, I will discuss our recent work on implementing underwater acoustic signal processing applications on a high performance FPGA.
Scoped Component Adaptation with Expanders -- Alessandro Warth (UCLA)
Integrating independently-developed software components in object
oriented programs can be both difficult and tedious. Researchers have
proposed several mechanisms to alleviate this problem. Some of them,
like AOP, are certainly powerful enough, but they are not modular:
they require the whole program to be available for typechecking,
making them very difficult to reason about. Others, including open
classes and retroactive abstraction, preserve modularity but
unfortunately have limited applicability. We have devised a simple
construct, the "expander", that combines the benefits of open classes
and retroactive abstraction, along with some important capabilities
from AOP, without sacrificing modularity. In order to validate our
design, we created eJava, a backward-compatible superset of the Java
programming language that includes this novel construct. In this talk,
we will introduce eJava and show how it can be used to solve several
problems that plague object oriented programmers.
Automatically Inferring Sound Dataflow Functions from
Dataflow Fact Schemas -- Sorin Lerner (UCSD / UW)
In this talk, I will describe our most recent work on the Rhodium
project. Rhodium is a domain-specific language for writing program
analyses and transformations that can be checked for correctness
automatically. In Rhodium, programmers declare dataflow facts that
represent useful information about a program, and then they write
declarative propagation rules, akin to flow functions, that state how
these dataflow facts propagate across statements. I will start with a
brief overview of the Rhodium language, after which I will present our
recent work on automatically inferring correct propagation rules given
only a set of dataflow fact declarations.
Register Allocation via Coloring
of Chordal Graphs -- Fernando Magno Quintão Pereira
(UCLA)
We present a simple algorithm for register allocation which is
competitive with the iterated register coalescing algorithm of
George and Appel.
We base our algorithm on the observation that 95\% of the methods
in the Java 1.5 library have chordal interference graphs
when compiled with the JoeQ compiler.
A greedy algorithm
can optimally color a chordal graph in time linear in the number of
edges, and we can easily add powerful heuristics for spilling and
coalescing. Our experiments show that the new algorithm
produces better results than iterated register coalescing for settings
with few registers and comparable results for settings with many
registers.
Event-Driven Programming using ResponderJ -- Brian Chin (UCLA)
Event-driven programming is used to implement many interactive pieces of
software, such as graphical user interfaces and real-time systems. It generally
simplifies programming logic by avoiding concurrency issues. Nonetheless,
event-driven programming can be tedious and error-prone to write. For each
event handled by the system, state has to be restored, processed, and then
saved back to the heap before returning to the main program flow. A programmer
must write the saving and restoring code in each case, and can easily forget to
save a value back into memory, causing hard to track down errors. In addition,
the execution flow of event-driven software tends to be complex, since standard
execution flow primitives (such as if and while statements) cannot be used
between independent events. This often makes event-driven code difficult to
understand. ResponderJ attempts to fix both of these problems by adding
language features to Java which allow the compiler to handle the saved state in
between events and simplify program flow. We introduce responders as an
extension of classes which act as an interface to what appears to be a separate
thread of execution. This language however preserves the deterministic nature
of event-driven programming, while greatly simplifying the code.
Enforcing Timing Policies with Code Certification -- Joseph C. Vanderwaart
(Pomona College)
In the many settings where third-party software is executed in the
context of a larger client program, it is usually necessary to prevent
the foreign code from behaving in ways that would disrupt the client,
corrupt data or destabilize the system. Certified code provides a
static means for controlling the behavior of untrusted programs or
components by bringing the power of type systems and formal logic to
bear on the problem. Code certification systems that prevent bad
memory accesses and enforce the abstractions provided by libraries and
runtime system interfaces have been well studied.
In this talk we present a system for certifying conformance to timing
requirements. Our approach is simple, comprising an incremental
change to an existing type system for assembly language, but flexible
in the set of policies it can enforce and, in principle, can be
extended to support arbitrarily complex coding idioms. Focusing on a
timing policy of particular interest, we describe a compiler that
produces certifiably compliant programs with no help from the
programmer and only a small impact on runtime performance.
Sneaking Existentials into Java -- Kim Bruce (Pomona College)
Existential types were introduced by Mitchell and Plotkin to model the sort
of abstraction found in abstract data types. Existential types also play
an important role in hiding the visibility of instance variables in
modeling objects in object-oriented languages, though they are used quite
differently in modeling objects compared to ADT's.
Theoretically, existential types are quite nice, forming a nice dual to
universal (polymorphic) types, and supporting the Curry-Howard isomorphism
between types and formulas of intuitionistic second-order propositional
logic.
Wild-card types were a last minute addition to Java 5. In fact, a minor
variant was rejected by the group controlling the evolution of the
language. In this talk we review the use of existential types and how they
explain some of the idiosyncracies of wild-card types. We also point out
how most of the uses of existential types could easily be eliminated from
the signatures of methods of Java libraries, though at some cost in verbosity.
NavP: Multithreaded and Structured Distributed Parallel Programming --
Lei Pan ( JPL and UC Irvine)
As cluster computers are becoming less expensive and increasingly
available, our ability to program this new generation of supercomputers
is lagging behind demand. Achieving scalability and ease of programming
simultaneously is a grand challenge. The state of the art for
implementing large-scale high-performance scientific and engineering
applications has been message passing (MP), despite the fact
that MP is widely considered to be hard to use. Studies reveal that
the two statements at the heart of MP -- Send() and Recv() -- change
the code like the goto statements, thus making structured programming
problematic. This reminds us of the software crisis of the 1960s
that was eventually ended by the suggestion from Dijkstra to abolish
the use of goto statements. This talk introduces a new methodology,
called Navigational Programming (NavP), that is based on the use of
computation mobility provided by self-migrating threads. NavP is
philosophically different because it describes the quantity of interest
-- a distributed computation along with the small data it requires --
following the movement of its locus. In contrast, all other approaches use
the SPMD (single program multiple data) view to describe computations
at stationary locations. Program transformations in NavP involves
the insertion of migration statements (hop(dest)), which, unlike the
Send() and Recv(), does not change the code structure. The steps of
the NavP code transformations will be described using simple examples.
Case studies of several important and non-trivial real-world applications
will be used to demonstrate that the multithreaded and structured NavP
is efficient and scalable.
A Type System for Distributed Arrays - Christian Grothoff (UCLA)
X10 is a new type-safe programming language for distributed high-performance
computing. Developed by Sarkar, Saraswat, and others, X10 supports
distributed objects and arrays, and notion of regions of array indices that
obviate the need for computation on individual indices. The X10 run-time
system checks that accesses to arrays are in-bounds and place-local, often
slowing down performance by several factors. We present an extension of the
X10 type system that uses region types to statically check array accesses.
Our type system embraces the spirit of X10, which is to use types to eliminate
dynamic checks. Our type system enables the programmer to provide concise
documentation that the compiler can use to eliminate safety checks, resulting
in faster, statically checked code.
Speculations: Improving Performance and Reliability in Distributed Systems -- Cristian Tapus (Caltech)
This talk examines the use of speculations, a form of distributed
transactions, to improve reliability of distributed applications. A
speculation is defined as a computation that is based on an assumption
that is not validated before the computation is started. If the
assumption is later found to be false, the computation is aborted and
the state of the program is rolled back; if the assumption is found to
be true, the results of the computation are committed. The primary
difference between a speculation and a transaction is that a speculation
is not isolated---for example, a speculative computation may send and
receive messages, and it may modify shared objects. As a result,
processes that share those objects may be absorbed into a speculation.
Speculations define safe recovery lines that can be used to roll back
distributed applications. I will discuss the syntax of
speculative constructs and the operational semantics for speculative
execution.