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.