Electrical computers and digital processing systems: processing – Processing architecture – Array processor
Reexamination Certificate
1999-06-03
2002-07-16
Ellis, Richard L. (Department: 2653)
Electrical computers and digital processing systems: processing
Processing architecture
Array processor
C712S016000
Reexamination Certificate
active
06421772
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to a parallel computer having a plurality of processing elements and more particularly to a parallel computer suitable for performing the image processing operation.
Conventionally, as the construction of the parallel computer, a local memory type and shared memory type are known.
In the parallel computer of local memory type, a local memory is provided for each processing element. Therefore, each of the processing elements can make access to the local memory which belongs thereto independently from the other processing elements. However, the parallel computer has a disadvantage that each processing element cannot make direct access to the local memory which belongs to the other processing element.
In the parallel computer of shared memory type, all of the processing elements share a memory. Therefore, each of the processing elements can make direct access to the shared memory. However, the parallel computer has a disadvantage that memory access contention between a plurality of processing elements occurs and the parallel operation will be easily disturbed.
As another type of parallel computer for solving the above problems, there is provided a parallel computer having a local cache memory for each processing element and a main memory shared by all of the processing elements. Further, as s till another type of parallel computer, there is provided a parallel computer which shares information between processing elements by use of crossbar switches. However, the above types of parallel computers are complicated in construction, the hardware amount increases and the control operation becomes difficult.
As one of the application fields of the parallel computer, an image processing operation is provided.
For example, in a case where the image processing operation is effected by use of a parallel computer having processing elements connected in a matrix form, a method for assigning portions of an image to the respective processing elements and causing the processing elements to process the partial images assigned thereto in parallel, thereby enhancing the speed of the image processing operation is considered. In the case of application to the image processing operation, since most memory accesses are localized to relatively nearby memory areas, it is considered effective to utilize the parallel computation in order to attain th e high processing speed.
However, in order to enhance the image processing speed, the conventional parallel computer of local memory type is insufficient. The reason is that it is necessary for each processing element to use the partial image assigned to the adjacent processing element in the computation for the end portion (boundary) of the partial image assigned to itself when the image processing such as the filtering process is effected, for example. That is, since access from a processing element to a memory which belongs to the adjacent processing element is made by use of communication between the elements via the adjacent processing element, a problem that the access speed becomes low occurs.
Also, in the shared memory type parallel computer is insufficient. This is because memory accesses simultaneously occur to cause memory access contention, the parallel operation cannot be effectively performed, and the practically high operation speed cannot be attained.
Further, the parallel computer using the cache memory is not effective since the image data size is large and the hit ratio is low. In addition, the parallel computer using the crossbar switch is not effective since the hardware becomes excessively complicated.
As described above, in the conventional parallel computer, it takes a long time for memory access in the local memory type and memory access contention occurs and a satisfactory parallel operation cannot be effected in the shared memory type. Further, in the parallel computer using the cache memory or crossbar switch, a problem occurs in the hardware amount and control operation.
BRIEF SUMMARY OF THE INVENTION
This invention has been made in order to solve the above problems and an object of this invention is to provide a parallel computer capable of effecting the parallel processing operation at higher speed and making efficient memory access without increasing the hardware amount and making the control operation complicated.
That is, in order to attain the above object, a parallel computer according to a first aspect of this invention comprises a plurality of memory elements which are logically arranged in a first arrangement pattern and store data; a plurality of processing elements which are logically arranged in a second arrangement pattern corresponding to the first arrangement pattern and process the data of the memory elements; and a connecting system which logically connects each of the processing elements to associated memory elements included among the memory elements.
Preferably, the processing elements are logically arranged in a matrix as the first arrangement pattern and the memory elements are logically arranged in a matrix as the second arrangement pattern, and the connecting system includes a connection section which connects each of the processing elements to memory elements included in the memory elements and logically arranged around the each of the processing elements.
Preferably, the processing elements and the memory elements are equal in number to each other and are alternately arranged to form a logical matrix array pattern, and the connecting system includes a connection section which connects peripheral processing elements included among the processing elements and logically arranged in a periphery of the matrix array pattern to associated peripheral memory elements included in the memory elements to form a logical closed loop in an array of the processing elements and the memory elements.
Preferably, each of the processing elements has a function capable of performing a direct access only to the associated memory elements which are connected by the connecting system.
Preferably, each of the memory elements has a function capable of being directly accessed only by those of the processing elements that are connected thereto by the connecting system.
Preferably, the connecting system includes a plurality of processing element buses respectively and exclusively provided for the processing elements, a plurality of memory element buses respectively and exclusively provided for the processing elements, and a plurality of switching elements connected between each of the processing element buses and associated element buses included among the memory element buses.
Preferably, only one of the switching elements is selectively made conductive.
Preferably, the memory elements are connected in a matrix via the processing elements to construct an image frame buffer.
Preferably, the parallel computer further comprises an access system which accesses each of the memory elements from an exterior.
Preferably, the parallel computer further comprises local memories respectively and exclusively provided for the processing elements.
A parallel computer according to a second aspect of this invention comprises n×m (n and m are integral numbers) processing elements which process data; n×m processing element buses respectively provided for the processing elements; (n+1)×(m+1) memory element buses respectively provided for (n+1)×(m+1) memory elements to be accessed; and a plurality of switching elements which connect one of the processing element buses which is connected to one of the processing elements which corresponds to a logical position (i, j) (i is an integral number from 0 to (n−1) and j is an integral number from 0 to (m−1)) to the memory element buses connected to those of the memory elements which correspond to a plurality of logical positions (i, j), (i, j+1), (i+1, j and (i+1, j+1).
Preferably, in the parallel computer the processing elements are equal to (n+1)×(m+1) in number, and t
Maeda Ken-ichi
Okamoto Yasukazu
Takeda Nobuyuki
Ellis Richard L.
Patel Gautam R.
LandOfFree
Parallel computer with improved access to adjacent processor... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Parallel computer with improved access to adjacent processor..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallel computer with improved access to adjacent processor... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2901837