A List of Previous Talks (2010)

The 49th ToPS

November 26th (Fri) 2010, 15:00--17:00
Rm. 2208, 22F, National Institute of Informatics

1. Peter Thiemann (University of Freiburg)

Mnemonics: Type-safe Bytecode Generation at Run Time

Mnemonics is a Scala library for generating method bodies in JVM bytecode at run time. Mnemonics supports a large subset of the JVM instructions, for which the static typing of the generator guarantees the well-formedness of the generated bytecode.

The library exploits a number of advanced features of Scala's type system (type inference with bounded polymorphism, implicit parameters, and reflection) to guarantee that the compiler only accepts legal combinations of instructions at compile time. Additional instructions can be supported at the price of a check at run time of the generator. In either case, bytecode verification of generated code is guaranteed to succeed.

2. Annette Bieniusa (University of Freiburg)

Actions in the Twilight - Software Transactional Memory with Safe I/O and Typed Conflict Management

Software transactional memory (STM) is a promising approach for the development of concurrent software. It coordinates the potentially conflicting effects of concurrent threads on shared memory by running their critical regions isolated from each other in transactions. However, this automatic coordination is sometimes too restrictive: library calls such as I/O operations are disallowed in a transaction and some transactions fail for minor conflicts that could easily be resolved.

Twilight STM is an extension of the STM approach which addresses these restrictions. It separates a transaction into a functional transactional phase, and an imperative irrevocable phase, which supports a safe embedding of I/O operations as well as a repair facility to resolve minor conflicts.

This talk presents our Haskell implementation of Twilight STM and its formalization as an extension of a call-by-name lambda calculus. We use Haskell's type system to restrict operations to the phases of a transaction where they are safe to use. We also introduce a new, type-safe tagging facility to localize conflicts easily.

The 48th ToPS

November 15th (Mon) 2010, 15:00--17:00
Room 534, Bldg. 14th of Faculty of Engineering, Univ. of Tokyo.

1. Frederic Loulergue (Laboratoire d'Informatique Fondamentale d'Orleans, University of Orleans)

Revised Bulk Synchronous Parallel ML

Bulk Synchronous Parallel ML or BSML is a high-level language for programming parallel algorithms. Built upon the Objective Caml language, it provides a safe setting for implementing Bulk Synchronous Parallel (BSP) algorithms. It avoids concurrency related problems: deadlocks and non-determinism. BSML is based on a very small core of parallel primitives that extended functional sequential programming to functional BSP programming with a parallel data structure and operations to manipulate it. However, in practice the primitives for writing the parallel non-communicating parts of the program are not so easy to use. Thus we designed a new syntax that makes programs easier to write and read: Revised BSML. In this talk, Revised BSML is presented and its expressiveness and performance are illustrated through an application examples. We also designed a formal semantics and proved its properties using the Coq proof assistant.

2. Liu Yu (The Graduate University for Advanced Studies / National Institute of Informatics)

The implementation and optimization of the list homomorphisms on MapReduce

Google' MapReduce programming model is widely used in parallel/distributed programming, and has great success in industry. Meanwhile, list homomorphisms are a class of recursive functions on lists, also attractive in parallel programming. But somehow, list homomorphisms are thought to be too academical and seldom seen it practicing in the industry.

We propose an algorithmic model layer of list homomorphisms, which build upon MapReduce framework to help resolving some nontrivial problems such as "maximum prefix sum". Because list homomorphisms match very well with the divide-and-conquer paradigm, so it can make the parallel programming easier for users. We show that list homomorphisms can be efficiently implemented on MapReduce and the benchmark shows the well parallelism and scalability.The new system provide simple programming interfaces and can apply algebraic properties of list homomorphisms in a intuitive way.

This presentation will talk about the implementation and optimization of the list homomorphisms library/framework.

Back Back to the top page