In the Massively Parallel Systems NEC Laboratory, there are three main research themes: architecture, programming techniques, and applications. The objective is to develop an adaptive massively parallel system which can change its structure flexibly according to problems, and thus exploits the optimum parallelism intrinsic to the problem and increase execution speed.
Current computers build up a complicated large system by accumulating logic by software on relatively simple hardware with fixed functions (CPU) . Since the logical functions provided by the CPU are fixed, they do not allow efficient execution in some cases. If we had an architecture which allowed these functions to change, execution could be made more efficient. It would also allow us to derive the parallelism intrinsic to problems from fine grains to large grains, thus enabling a variety of parallel processing paradigms from data parallelism to pipelines to be optimally implemented to suit the structure of each problem, and thus afford high-speed execution.
In recent years, new types of devices such as the FPGA (field programmable gate array) and PLD (programmable logic device) have emerged. These were originally designed to allow low-cost rapid development of logic circuits for equipments manufactured in small lots. But due to their flexibility, attempts have been made to extend not only logic circuits but also programs and algorithms for high-speed execution, thus expanding applications as the speed and integration density of the devices rise.
However, FPGA has some problems when used in adaptive massively parallel systems. First, it is not sufficiently functional for mapping large programs or algorithms on it. For instance, the speed of an ALU constructed in FPGA would be only one tenth of the most recent high-speed CPUs. Since a large number of gates would also be required, a sufficient number of ALUs required for deriving the parallelism intrinsic to problems may not be provided.
Another problem concerns how to deal with large quantities of data. To deal with such data, external memory is usually added to the FPGA. When accessing external memory, there will be the Neumann bottleneck as with traditional CPUs.
We have proposed an SOP (sea of processors) architecture as shown in Fig. 1 for adaptive massively parallel systems and are designing logic, memory, and connection devices suitable for mapping programs. We are considering an architecture for logic devices with 1-bit full-adders as basic elements to allow efficient composition of ALUs, and for memory devices, an architecture based on associative memory to allow SIMD-like parallel processing and search and list operations for maximum and minimum values.
Because the SOP architecture attempts to map the algorithm directly to the hardware rather than executing it sequentially, the mapping technique is very important. We are developing a compiler for extracting the data and control dependencies of programs from the C-language based description, and thus exploiting the maximum parallelism from the algorithm.
We have prototyped the 0-th version of a compiler which only supports the basic control structure of C and generates an XNF format (a net list format for FPGA from Xilinx, Inc.) from descriptions excluding arrays and complicated data structures. This compiler analyzes source code, and expands function calls and operations (such as arithmetic operations) according to control and data flows to generate gate-level net lists as shown in Fig. 2. With this technique, we can exploit the parallelism intrinsic to the problem easily as data flow machines do. And because the control and data flows are directly mapped to the hardware, packet generation as with data flow machines is not required, thus enabling more efficient execution. We have also newly developed a method of analyzing the dependencies among variables to derive higher degree of parallelism.
We are also studying application problems with much parallelism to verify the validity of the SOP architecture. In addition, we are studying gene information processing as a significant application problem by itself rather than TOY programs. We have developed a technique for extracting important features called motives from a sequence of amino acids in protein using the hidden Markov model (HMM) and achieved a high accuracy of extraction. Currently, we are mapping the HMM algorithm used in this study to FPGA. By representing sparse matrices as list vectors and passing them through a pipelined process, a processing speed reaches as high as 10 times that of a RISC CPU R4400 (150 MHz) with Xilinx FPGA. We are clarifying problems with FPGA by mapping actual applications to reflect the results on the SOP architecture.
Henceforth, we will start the detail design of functional elements of the SOP architecture while mapping the actual applications; the goal is to implement this as a chip in the latter half of the RWC Program.
The compiler will be extended to allow users to describe data structures and thread-level parallelism, aiming to create a development environment which enables the maximum parallelism intrinsic to the algorithm to be extracted and mapping to the SOP architecture.
