Work stealing is a well-known technique for dynamic load balancing; however, manually writing work-stealing protocols is error-prone. We can use the Tascell parallel programming language for the correct and portable implementation of work stealing; the implementation combines polling and adequate mutual exclusion. In Tascell, we can express on-demand concurrency for backtracking-based load balancing where a worker performs a sequential computation with its own execution stack unless it is requested to spawn a task. To spawn a larger task by temporarily backtracking, nested functions can be used for legitimate execution stack access. As nested functions for extended C languages, we can use GCC’s heavyweight implementation with runtime code generation or lightweight implementations by enhancing GCC; however, compiler-based implementations are poor in portability. In this study, we implement and evaluate more portable Tascell frameworks called “Tascell/SC” by using transformation-based portable implementations of nested functions. In addition, we propose Tascell-inspired portable frameworks only in C++ called “Tascell++” by using lambda expressions in C++11 for legitimate execution stack access.

This paper presents a new approach to fault-tolerant language systems without a single point of failure for irregular parallel applications. Work-stealing frameworks provide good load balancing for many parallel applications, including irregular ones written in a divide-and-conquer style. However, work-stealing frameworks with fault-tolerant features such as checkpointing do not always work well. This paper proposes a completely opposite "work omission" paradigm and its more detailed concept as a "hierarchical omission"-based parallel execution model called HOPE. HOPE programmers' task is to specify which regions in imperative code can be executed in sequential but arbitrary order and how their partial results can be accessed. HOPE workers spawn no tasks/threads at all; rather, every worker has the entire work of the program with its own planned execution order, and then the workers and the underlying message mediation systems automatically exchange partial results to omit hierarchical subcomputations. Even with fault tolerance, the HOPE framework provides parallel speedups for many parallel applications, including irregular ones.

The growing complexity of underlying systems such as memory hierarchies and speculation mechanisms are making it difficult to perform proper performance evaluations. This is a serious problem especially when we want to know the overheads of adding new functionality to existing languages (or systems/applications), or to know small changes in performance caused by small changes to programs. A problem is that equivalent executable programs, which only differ in their instruction addresses (code placement), often exhibit significantly different performance. This difference can be explained by the fact that code placement affects the underlying branch predictors and instruction cache subsystems. By taking into account such code placement effects, this paper proposes a proper evaluation scheme that cancels accidental factors in code placement by statistically summarizing the performance of a sufficient number of artificial programs that differ from the evaluation target program (almost) only in their code placement. We developed a system, called Code Shaker, that supports performance evaluations based on the proposed scheme.

Parallel programming/execution frameworks for multicore platforms should support as many applications as possible. In general, work-stealing frameworks provide efficient load balancing even for irregular parallel applications. Unfortunately, naive parallel programs for ``general computations'' governed by rewriting rules over configurations (system states) cause stack overflow or unacceptable load imbalance. In this study, we develop parallel programs to perform probabilistically balanced divide-and-conquer graph traversals. We propose a programming technique for accumulating overflowed calls for the next iteration of repeated parallel stages. In an emerging backtracking-based work-stealing framework called "Tascell," which avoids excessive concurrency, we propose a programming technique for long-term use of workspaces, leading a similar technique in the Cilk framework.

High-productivity languages for parallel computing become more important as parallel environments including multicores become more common. Cilk is such a language. It provides good load balancing for many applications including irregular ones; that is, it keeps all workers busy by creating plenty of "logical" threads and adopting the oldest-first work stealing strategy. This paper proposes a "logical thread"-free framework called Tascell, which achieves a higher performance and supports a wider range of parallel environments including clusters without loss of productivity. A Tascell worker spawns a "real" task only when requested by another idle worker. The worker performs the spawning by temporarily "backtracking" and restoring its oldest task-spawnable state. Our approach eliminates the cost of spawning/managing logical threads. It also promotes the reuse of workspaces and improves the locality of reference since it does not need to prepare a workspace for each concurrently runnable logical thread. Furthermore, Tascell enables elegant and highly-efficient backtrack search algorithms with delayed workspace copying. For instance, our 16-queens problem solver is 1.86 times faster than Cilk on a system with two dual-core processors. Our approach also enables a single program to run in both shared and distributed memory environments with reasonable efficiency and scalability.

We propose an incremental compaction algorithm. Our compactor selects a continuous area of the heap and evacuates it by incrementally copying all objects in the area to the rest of the heap. After all objects have been copied, our compactor incrementally updates pointers pointing into the evacuated area. During these processes, each original object and its copy are kept consistent. We implemented the compactor together with a snapshot garbage collector in the KVM. Our measurements show that (1) the largest free chunk is almost always more than 20% as large as the entire heap when the heap is twice as large as the maximum amount of live objects, (2) the runtime overhead is less than 20%, and (3) the maximum pause time caused by the compactor is comparable to that caused by the snapshot collector.

Runtime systems for applications written in certain languages such as Java/spl trade/ and Lisp usually have a garbage collection (GC) feature to make efficient use of memory. With this feature, the system, before running out of memory space, automatically reclaims unnecessary fragments of memory at one burst and recycles them for use by applications. In conventional implementations, however, the system has to suspend the execution of applications while carrying out GC, which renders GC generally unsuitable for real-time processing systems. As a solution to this problem, Yuasa, et al. of Kyoto University developed the return-barrier method based on snapshot GC. Return-barrier enhances real-time GC processing over the original snapshot GC. Some reports have been published on the evaluation of the return-barrier method in the Lisp environment such as Kyoto Common Lisp (KCL). In this paper, we report the implementation of the return-barrier method for JeRTy/spl trade/VM, which is a real-time environment for embedded Java applications developed by OMRON Corporation, and its performance improvement over the conventional GC in JeRTyVM.

The trend towards object-oriented software construction is becoming more and more prevalent, and parallel programming cannot be an exception. In the context of parallel computation, it is often natural to model the computation as message passing between autonomous, concurrently active objects. The problem was, as some previous studies had indicated, that the overhead from message reception to dynamic method dispatching consumes a significant amount of execution time (e.g., as much as 4000 machine cycles or 500 μseconds at 8 MHz block for some language/hardware combination). Our ABCL/onEM-4, a software/hardware implementation architecture for a concurrent object-oriented language, overcomes this problem with technologies such as address-specifiable reactive packet-driven architecture, zero-overhead context switching, and packet-driven allocation of message boxes. Preliminary performance measurements on a real hardware EM-4 confirm our claim, achieving the performance of up to nearly 10 μseconds (130 clocks) total for a remote object-creation followed by a request message send to the created object and a reply reception from the object, for a 12.5 MHz clock speed. Our results indicate that the concurrent object-oriented computational model and languages are highly viable with proper implementational software/hardware architectures.