Macro-dataflow processing, which exploits the parallelism among coarse-grain tasks (macrotasks) such as loops and subroutines, is considered promising to break the performance limits of loop parallelism. To realize macro-dataflow processing on distributed memory systems, "data reaching conditions", a method to make the sender-receiver pair of a data transfer determined at runtime, has previously been proposed. However, irregular data accesses induce extra data transfers, which lead to performance deterioration. This paper proposes an implementation method using software distributed shared memory, which enables on-demand data fetching. This paper describes the implementation using two well-accepted, page-based software distributed shared memory systems, TreadMarks and JI-AJIA. Evaluation results on a PC cluster show the software distributed memory approach is as much as 25% faster than the data reaching conditions

Large-scale PC clusters, such as ACSI Lightning with 2,816 processors and the AIST supercluster with more than 3,000 processors, have been constructed. Although software distributed shared memory (S-DSM) provides an attractive parallel programming model, almost all S-DSM systems proposed are only useful on a cluster of less than or equal to 16 nodes. They lack scalability.

Mining the large Web based online distributed databases to discover new knowledge and financial gain is an important research problem. These computations require high performance distributed and parallel computing environments. Traditional data mining techniques such as classification, association, clustering can be extended to find new efficient solutions. The paper presents the scalable data mining problem, proposes the use of software DSM (distributed shared memory) with a new mechanism as an effective solution and discusses both the implementation and performance evaluation results. It is observed that the overhead of a software DSM is very large for scalable data mining programs. A new Log Based Consistency (LBC) mechanism, especially designed for scalable data mining on the software DSM is proposed to overcome this overhead. Traditional association rule based data mining programs frequently modify the same fields by count-up operations. In contrast, the LBC mechanism keeps up the consistency by broadcasting the count-up operation logs among the multiple nodes.

The paper presents the scalable data mining problem, proposes the use of software DSM (Distributed Shared Memory) with a new mechanism as an effective solution and discusses both the implementation and performance evaluation results. It is observed that the overhead of a software DSM is very large for scalable data mining programs. A new Log Based Consistency (LBC) mechanism, especially designed for scalable data mining on the software DSM is proposed to overcome this overhead. Traditional association rule based data mining programs frequently modify the same fields by count-up operations. In contrast, the LBC mechanism keeps up the consistency by broadcasting the count-up operation logs among the multiple nodes.

This paper describes the research activity on dataflow computing in Japan focusing on dataflow computer development at the Electrotechnical Laboratory (ETL). First, the history of dataflow computer development in Japan is outlined. Some distinguished milestones in the history are mentioned in detail. Second, two types of dataflow computing systems developed at ETL, SIGMA-1 and EM-4, are described with their research goals. The fundamental characteristics of the both systems are given and some comparisons are made. Finally, future problems toward new generation computer systems to meet the challenge of Tera FLOPS machines are discussed.

A highly parallel (more than a thousand) dataflow machine EM-4 is now under development. The EM-4 design principle is to construct a high performance computer using a compact architecture by overcoming several defects of dataflow machines. Constructing the EM-4, it is essential to fabricate a processing element (PE) on a single chip for reducing operation speed, system size, design complexity and cost. In the EM-4, the PE , called EMC-R, has been specially designed using a 50,000-gate gate array chip. This paper focuses on an architecture of the EMC-R. The distinctive features of it are: a strongly connected arc dataflow model; a direct matching scheme; a RISC-based design; a deadlock-free on-chip packet switch; and an integration of a packet-based circular pipeline and a register-based advanced control pipeline. These features are intensively examined, and the instruction set architecture and the configuration architecture which exploit them are described.

The authors compare dataflow computing models, languages, and dataflow computing machines for numerical and nonnumerical computations. The high-level-language-graph transformations that must be performed to achieve high performance for numerical and nonnumerical programs executed in a dataflow computing environment are described for Lisp, using the DCBL transformations. Some general problems of dataflow computing machines are discussed. Performance evaluation measurements obtained by executing benchmark programs in the ETL nonnumerical dataflow computing environment, the EM-3, are presented.>

In this paper, a Lisp-based data-driven machine with a novel parallel control mechanism and its performance evaluation are presented. The proposed control mechanism is the natural extension of a data-driven scheme to function evaluation and is achieved by packet communication architecture. First, the organization of the data-driven machine is described and, then the results of the simulation studies are shown which confirm the effectiveness of the control mechanism. The performance characteristics of the data-driven machine obtained by the software simulator are also given.

The construction problems of optimum sequence trees (or digital search trees) are considered in the following frameworks: 1. construction of optimum trees from a set of keys, 2. transformation of an arbitrary tree into an optimum one, 3. optimum insertions of keys into an optimum tree, 4. optimum deletions of keys from an optimum tree. Algorithms are shown. The number of operations needed for the algorithm in the framework 1 is at most $O(N^{2}L)$, and in the framework 2 it is at most $O(N^{3}L)$ both with $O(N)$ storage locations, where N and L are the number of keys and the length of coded keys respectively. Necessary and sufficient conditions for the optimality of sequence trees are also given.

In promoting the ETSS project a program simulator based on an idea of partial interpretation has been constructed, and its principle and design are described in the paper. This new approach has been introduced to provide the simulator with such features as high speed and high accuracy in simulation and simplification in implementation. The essence of the idea of partial interpretation is using direct execution of instructions by hardware and simulation of them by an interpreter in combination, wherewith the hardware interrupt mechanism intermediates the two phases of the whole simulation. An interruption takes place when executing a "privileged" instruction, which triggers the simulation of the instruction. The other type of instructions are normally rendered to direct execution by hardware. The simulation method for devices operating in parallel is also described with respect to the timing control and scheduling. A program simulator of this type provides a powerful tool for debugging "supervisor " programs and opens a new approach to system expansion.