A recent development in multicore technology has enabled development of hundreds or thousands core processor. However, on such multicore processor, an efficient hardware cache coherence scheme will become very complex and expensive to develop. This paper proposes a parallelizing compiler directed software coherence scheme for shared memory multicore systems without hardware cache coherence control. The general idea of the proposed method is that an automatic parallelizing compiler analyzes the control dependency and data dependency among coarse grain task in the program. Then based on the obtained information, task parallelization, false sharing detection and data restructuration to prevent false sharing are performed. Next the compiler inserts cache control code to handle stale data problem. The proposed method is built on OSCAR automatic parallelizing compiler and evaluated on Renesas RP2 with 8 SH-4A cores processor. The hardware cache coherence scheme on the RP2 processor is only available for up to 4 cores and the hardware cache coherence can be completely turned off for non-coherence cache mode. Performance evaluation is performed using 10 benchmark program from SPEC2000, SPEC2006, NAS Parallel Benchmark (NPB) and Mediabench II. The proposed method performs as good as or better than hardware cache coherence scheme. For example, 4 cores with the hardware coherence mechanism gave us speed up of 2.52 times against 1 core for SPEC2000 "equake", 2.9 times for SPEC2006 "lbm", 3.34 times for NPB "cg", and 3.17 times for MediaBench II MPEG2 Encoder. The proposed software cache coherence control gave us 2.63 times for 4 cores and 4.37 for 8 cores for "equake", 3.28 times for 4 cores and 4.76 times for 8 cores for lbm, 3.71 times for 4 cores and 4.92 times for 8 cores for "MPEG2 Encoder".

CAP Introduction. Presents the introductory welcome message from the conference proceedings. May include the conference officers' congratulations to all involved with the conference event and publication of the proceedings record.

A serializer/deserializer (SerDe) is necessary to serialize a data object into a byte array and to deserialize in reverse direction. A SerDe that is used worldwide and runs quickly is the Protocol Buffer (ProtoBuf), which serializes a tree-structured data object into the Type-Length-Value (TLV) format. Acceleration of SerDe processing is beneficial because SerDes are used in various fields. This paper proposes a new method that accelerates the tree-to-TLV serialization through 2-way parallel processing called “parallelized serialization” and “parallelization with streaming”. Experimental results show that parallelized serialization with 4 worker threads achieves a 1.97 fold shorter serialization time than when using a single worker thread, and the combination of 2-way parallel processing achieves a 2.11 fold shorter output time than that for ProtoBuf when 4 worker threads, FileOutputStream and trees of 10,080 container nodes are used.

This paper proposes a fast AND/OR tree search algorithm using a multiple-paths concurrent search method. Conventional heuristic AND/OR tree search algorithms expand nodes in only a descending order of heuristic evaluation values. However, since the evaluation values are heuristic, a solution node group sometimes includes nodes with lower evaluation values. The tree which has a solution node group including nodes with lower evaluation values requires a long time to be solved by the conventional algorithms. The proposed algorithm allows us to search paths including nodes with lower evaluation values and paths including nodes with higher evaluation values concurrently. For searching various paths concurrently, the proposed algorithm uses pseudo-threads and a pseudo-thread scheduler managed by a user program with low overhead compared with the OS thread management. The pseudo-thread scheduler can weight the amount of search on each path and schedule the pseudo-threads. The proposed algorithm can solve trees which have solutions including nodes with lower evaluation values also quickly. For performance evaluation, the proposed algorithm was applied to a Tsume-Shogi (Japanese chess problem) solver as a typical AND/OR tree search problem. In tsume-shogi, players can reuse captured pieces. Performance evaluation results on 385 problems show that the proposed algorithm is 1.67 times faster on the average than the previous algorithm df-pn.

We are developing a software-execution framework based on an octo-core chip multiprocessor named RP2 and an automatic multigrain-parallelizing compiler named OSCAR. The main purpose of this framework is to maintain good speed scalability and power efficiency over the number of processor cores under severe hardware restrictions for embedded use. Key to the speed scalability is reduction of a communication overhead with parallelized tasks. A data-categorization scheme enables small-overhead cache-coherency maintenance by using directives and instructions from the compiler. In this scheme, the number of cache-flushing time is minimized and parallelized tasks are quickly synchronized by using flags in local memory. As regards power efficiency, to reduce power consumption, power supply to processor cores waiting for other cores is timely and frequently cut off, even in the middle of an application, by using a timely-power- gating scheme. In this scheme, to achieve quick mode transition between "NORMAL" mode and "RESUME POWEROFF" mode, register values of the processor core are stored in core-local memory, which is active even in "RESUME POWEROFF" mode and can be accessed in one or two clock cycles. Measured speed and power of an application show good speed scalability in execution time and high power efficiency, simultaneously. In the case of a secure AAC-LC encoding program, execution speed when eight processor cores are used can be increased by 4.85 times compared to that of sequential execution. Moreover, power consumption under the same condition can be reduced by 51.0% by parallelizing and timely-power gating. The time for mode transition is less than 20 micro seconds, which is only 2.5% of the "RESUME POWER-OFF" period.

A heterogeneous multi-core processor (HMCP) architecture, which integrates general purpose processors (CPU) and accelerators (ACC) to achieve high-performance as well as low-power consumption with the support of a parallelizing compiler, was developed. The evaluation was performed using an MP3 audio encoder on a simulator that accurately models the HMCP. It showed that 16-frame encoding on the HMCP with four CPUs and four ACCs yielded 24.5-fold speed-up of performance against sequential execution on one CPU. Furthermore, power saving by the compiler reduced energy consumption of the encoding to 0.17 J, namely, by 28.4%.

Multicore processors have been adopted for consumer electronics like portable electronics, mobile phones, car navigation systems, digital TVs and games to obtain high performance with low power consumption. The OSCAR automatic parallelizing compiler has been developed to utilize these multicores easily. Also, a new consumer electronics multicore application program interface (API) to use the OSCAR compiler with native sequential compilers for various kinds of multicores from different vendors has been developed in NEDO (New Energy and Industrial Technology Development Organization) "Multicore Technology for Realtime Consumer Electronics" project with Japanese 6 IT companies. This paper evaluates the parallel processing performance of multimedia applications using this API by the OSCAR compiler on the FR1000 4 VLIW cores multicore processor developed by Fujitsu Ltd, and the RP1 4 SH-4A cores multicore processor jointly-developed by Renesas Technology Corp., Hitachi Ltd. and Waseda University. As the results, the parallel codes generated by the OSCAR compiler using the API give us 3.27 times speedup on average using 4 cores against 1 core on the FR1000 multicore, and 3.31 times speedup on average using 4 cores against 1 core on the RP1 multicore.

This paper proposes a data-localization compilation scheme for macro-dataflow computation, in which coarse-grain tasks such as loops, subroutines and basic blocks in a Fortran program are automatically processed in parallel on a multiprocessor system.The data-localization scheme reduces data transfer overhead for passing shared data among coarsegl ain tasks composed of Doall loops and sequential loops by using local memory effectively.In this scheme, a compiler partitions coarse-grain tasks, or loops, having data dependence among them into multiple groups by a loop aligned decomposition so that data transfer among groups can be minimum, generates dynamic scheduling routine with partial static task assignment to assign decomposed tasks in a group to the same processor at run-time, and generates parallel machine code to pass shared data inside the group through local memory.A compiler has been implemented for an actual multiprocessor system OSCAR having centralized shared memory and distributed shared memory in addition to local memory on each processor.Performance evaluation OIL OSCAR shows that macro-dataflow computation with the proposed data-localization scheme can reduce the execu tion time by 10% to 20% average compared with ordinary macro-dataflow computation using centralized shared memory.

The authors propose a compilation scheme for parallel processing near fine-grain tasks, each of which consists of several instructions or a statement, on a multiprocessor system called OSCAR. The scheme allows one to minimize synchronization and data transfer overheads and to optimally use registers of each processor by employing a static scheduling algorithm considering data transfer. This scheme can effectively be combined with macro-dataflow computation and with making the loop concurrent. A compiler using the proposed scheme has been implemented on OSCAR, which has been designed to take full advantage of the static scheduling. A performance evaluation of the scheme on OSCAR is also described.>

A parallel-processing scheme is described for robot-arm control computation on any number of parallel processors. The scheme employs two multiprocessor scheduling algorithms called, respectively, depth first/implicit heuristic search (DF/IHS) and critical path/most immediate successors first (CP/MISF); these were recently developed by the authors. The scheme is applied to the parallel processing of dynamic control computation for the Stanford manipulator. In particular, the proposed algorithms are applied to the computation of the Newton-Euler equations of motion for the Stanford manipulator and implemented on a multimicroprocessor system. The test result was so successful that the use of six processor pairs in parallel could attain the processing time of 5.37 ms. It is also shown that the proposed parallel-processing scheme is applicable to an arbitrary number of processors.

This paper describes practical optimization/ approximation algorithms for scheduling a set of partially ordered computational tasks onto a multiprocessor system so that the schedule length will be minimized. Since this problem belongs to the class of ''strong'' NP-hard problems, we must foreclose the possibility of constructing not only pseudopolynomial time optimization algorithms but also fully polynomial time approximation schemes unless P = NP. This paper proposes a heuristic algorithm named CP/MISF (critical path/most immediate successors first) and an optimization/approximation algorithm named DF/IHS (d thfirst/implicit heuristic search). DF/IHS is an excellent scheduling method which can reduce markedly space complexity and average computation time by combining the branch-and-bound method with CP/MISF; it allows us to solve very large scale problems with a few hundred tasks. Numerical examples are included to demonstrate the effectiveness of the proposed algorithms.