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.

We have developed an incremental compacting garbage collector for embedded Java systems. The collector divides the heap into equal sized pages and uses the segregated free lists for fast allocation. Collectors that have such a heap layout have a problem of fragmentation in allocating objects larger than the page size. We solve this problem by using the replication-based incremental compaction. The compactor evacuates all objects in one area, the evacuation area, of the heap, thereby creating a large chunk of free space. We developed an algorithm for choosing the evacuation area that effectively cures fragmentation. The compactor does not use any read-barriers. Instead, it uses a technique similar to the replication-based incremental copying collection. This needs forwarding pointers for all evacuated objects. Rather than introducing an extra field for each object, we use a hash table to store forwarding pointers.

Our society depend on embedded and ubiquitous computing and the reliability of embedded software becomes more and more important. We have conducted a five years project with industries to develop software for realizing highly reliable embedded systems. We have tackled reliability issues from the following aspects. (1)Design environment: we have developed a UML design verification tool that apply model checking techniques to improve the design quality of application software. (2)Operating environment: we have developed operating system supports that realize multiple execution of real-time operating systems and also developed operating systems with enhanced resource management. Both technologies contribute the realization of robust run-time environment. (3) Real-time environment: we have developed real-time garbage collection techniques for Jave. They prevent the suspension of applications that violates the correct behavior of real-time applications. Also, they reduce the effort of application programmers to avoid garbage-collection during important execution timing. We have obtained fruitful results from these three research themes, and some of them are actually used in industries. Furthermore, we have integrated the results to make synergetic effect of them. In order to demonstrate the effectiveness, we have conduct an experiment. In this paper, we introduce the project and its results.

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.

A highly interactive programming system is presented which supports hierarchical and modular program development with abstraction mechanisms. By taking advantage of abstraction mechanisms, the system provides a "truly modular" environment, in which modules are constructed, debugged, verified, and compiled in a module-by-module fashion. Such an environment naturally requires system management of the information concerning ongoing program development, in the form of module databases. As a result, further problems arise as to how to modify the information in efficient and consistent ways. This paper discusses design objectives for modular programming systems by focusing on such issues as information management, interactive construction and modification of modules, separate processing, specification and verification, and supports for cooperative program development.