In a multiprocessor system where the number of processors composing the system is increased, and the memory utilization is raised by improving the execution rate of each processor, the reduction of system throughput caused by the memory access conflicts has to be considered substantially. This paper describes the discussion on such an approach that implements a conflict-free data mapping by the use of some sophisticated address translation between logical and physical addresses. This new addressing scheme of a reorganizable memory structure provides the function that allows each processor easily to distribute the operands to be accessed to completely different memory modules, by interlaying the address translation mechanism called address organizer between logical and physical addresses. This approach permits the memory structure to reorganize so as to make it adaptive to the parallelism contained in the problems themselves, and thus also to accomplish the suppression of memory access conflicts spontaneously. Furthermore, conflict-free data mapping being eventually accomplished through an interface of such a hardware as address translation mechanism, this approach has an advantage that the user's logical address space will not be affected in the least.

In this paper, an algorithm for implementing a high-speed FFT processor and the memory structure relating with it are mainly discussed. The problem to be considered when implementing a hard-wired high-speed FFT processor will be as follows: (1) How to simplify the decision of data addresses to be accessed. (2) How to avoid the memory access conflict when introducing the parallelization of memory. New method presented in this paper gives a drastic solution to them. Namely, utilizing the proposed memory structure allows any number of butterfly computations as well as single one to be carried out substantially in only one memory cycle. Furthermore, there is no theoretical restriction in any level of parallelization. Therefore, it is easy to implement the FFT processor having a reasonable throughput for particular application. The discussion in this paper is primarily proceeded from the hardware standpoint of implementation. However, there is no essential disparity between the proposed organization and that of conventional computers. The only difference between them is a conceptual one with respect to memory structure. Thus the presented method is useful enough for implementation of the algorithm on a conventional computer system such as multi-processors, and for its implementation by hardware as well.

It is well known in a multiprocessor system that the reduction of the system throughput is chiefly attributable to its memory access conflicts. A new method has been proposed which can avoid the memory access conflicts by means of realizing a conflict-free data mapping through a new technique of reorganizable memory structure. On the other hand, whether or not a parallel processing system is successful does deeply depend on the software design. Most of the algorithms for numeric computations are not suitable for the parallel processing, but usually for the sequential one; accordingly, it is important to develop such an algorithm that takes account of its parallelism. This paper describes some examples of parallel processing algorithms suitable for the proposed multiprocessor system with reorganizable memory structure. The application problems described in this paper involve the fast Fourier transform and the matricx processing, but these are only an example or two out of many application problems. By the use of algorithms as mentioned in this paper, the multiprocessor system with reorganizable memory system can demonstrate its effectiveness and perform the parallel processing without any memory access conflicts.

A so-called pipeline FFT achieves parallel processing among the stages, and its very high-performance and relatively simple control mechanism make it an extremely useful architecture for high-speed applications. Processing rate of the pipeline FFT processor, however, depends on the processing speed of a computation element of each stage, since the pipeline FFT architecture achieves an amount of parallelism only equal to logr N or the number of stages. Two important FFT architectures are described in this paper. The first architecture achieves a great amount of parallelism compared with the conventional pipeline FFT. Based on the constant-geometry pipeline FFT, the algorithm is extended to the multi-pipeline constant-geometry FFT of an arbitrary number of pipes. This architecture also realizes homogeneous structure and a simple control mechanism compared with the conventional pipeline FFT architecture. The second architecture described allows contiguous data blocks to be processed continuously by only a single set of FIFO buffers instead of a double buffering and switching mechanism. By this modified multi-pipeline constant-geometry FFT architecture, overall system efficiency can reach 100% by only using a single set of buffers for each stage even though an architecture based on the not-in-place algorithm.