Electrical computers and digital processing systems: processing – Processing architecture – Array processor
Reexamination Certificate
1998-04-09
2001-02-06
Donaghue, Larry D. (Department: 2783)
Electrical computers and digital processing systems: processing
Processing architecture
Array processor
C712S013000, C712S014000, C712S022000
Reexamination Certificate
active
06185667
ABSTRACT:
BACKGROUND
The present invention relates to parallel computing, and more particularly to (Single Instruction-Multiple-Data) SIMD mesh connected computing.
In certain types of parallel processing, an array of processor elements (PEs), or cells, is configured so that each PE performs logical or arithmetic operations on its own data at the same time that all other PEs are processing their own data. This can reduce the amount of time required to process the data. As such, these arrays are particularly well suited for real-time processing tasks, such as processing image data collected by one or more sensors. Parallel processors are used in both military and civilian applications.
A typical parallel processor of the above-mentioned type includes a rectangular array of PEs, with each interior PE being connected to its four nearest neighboring PEs (designated north, south, east and west) and each edge PE being connected to a data input/output device. As a result of this configuration, a mesh of processing elements is formed. The term “Mesh Connected Computer” (MCC) is often used to describe this architecture.
In a MCC, each PE is also connected to a master controller which coordinates operations on data throughout the array by providing appropriate instructions to the PEs. Machines in which the logical or arithmetic operation being performed at any instant in time is identical for all PEs in the array are referred to by several names, including Single Instruction-Multiple Data (SIMD) machines. U.S. patent application Ser. No. 08/112,540 (the '540 Application), which was filed on Aug. 27, 1993 in the name of Meeker, describes one example of a SIMD architecture computer. The '540 Application is incorporated by reference herein in its entirety. On the other hand, machines that issue different instructions to different PEs (which may contain different data) are referred to as Multiple Instruction-Multiple Data (MIMD) machines.
Because the PEs in SIMD machines are all issued the same instruction, the complexity of the SIMD PEs and supporting hardware can be reduced. This is typically an important factor, because the PE will be repeated many times, so that any increase in the size, processing, and power requirements for each PE will be multiplied many times. It is often desirable to minimize the size of the parallel processor to accommodate limited space within housings, and other environmental limitations.
While SIMD machines offer a number of benefits, they also present a number of challenges. First, a SIMD architecture designer must address the challenge of moving information into and out of the array in a timely manner. This task can be a complex matter because many PEs in the array are connected to only neighboring PEs, rather than directly connected to an input/output interface.
The processor disclosed in the '540 Application accomplishes this task, in part, by using a CM (communication) plane. The CM plane interfaces with one row of the array, such as the “southern-most” row in the array. The information provided by the CM plane is then shifted northward via an internal CM bus from one row of PEs to the next. This process continues with each row of PEs shifting data to their northern neighbors while the rows receive new data from the south. Output data is transferred from the parallel processor array in an analogous manner.
The '540 Application also includes a mechanism for extracting particular values from an entire image plane using a global OR (or “GLOR”) function. In the global OR processing function, signals from each respective PE in the array are OR-ed together (e.g., CHIP_GLOR=glor_pe(0)+glor_pe(1)+glor_pe(2)+ . . . glor_pe(n), where glor_pe(i) denotes a signal generated by the i
th
PE). The CHIP_GLOR signal, through output to external circuitry, can then be used to extract “target” data.
While the above-described techniques are effective in moving information into and out of the array, there remains room for improvement regarding this aspect of the parallel processor. For instance, the above-identified inventors determined that it would be desirable to increase the number of options in which information can be extracted from the array, and also provide a mechanism by which information can be more efficiently globally broadcast back into the array (or broadcast into part of the array).
Second, once the image data is stored within the array, the system designer must address the issue of how to shift the data within the array so that each PE receives its proper operands in a timely manner. One technique for accomplishing this task described in the '540 Application is to shift the image data row-by-row in the north-south direction, or shift the data column-by-column in the east-west direction. For instance, in response to a clock signal, a particular PE could transfer information from its north input (i.e., its “ni” input) and store this information into a north-south register (ns_reg).
While the above shift operation is effective, there again remains room for improvement regarding this aspect of the parallel processor. The above-identified inventors determined that it would be desirable to increase the versatility in which image information can be shifted within the array, so as to ultimately increase the speed at which information can be shifted within the array, and also to facilitate certain types of image operations, such as image shuffling and histogram processing.
Any increase in the versatility of the parallel processor may also increase its complexity. As described above, the complexity of each PE may be directly proportional to its size, processing and power requirements. Accordingly, the designer must carefully balance the goal of improving the versatility of the parallel processor with the potential negative consequences of making the array too complex. Needless to say, this is a difficult design challenge.
Furthermore, the principal design paradigm of a SIMD processor dictates that all PE's within the array carry out the same instruction at the same time. In certain circumstances, the above-identified inventors determined that it might be desirable to increase the versatility of the processing array by making one or more PEs “behave” in a manner which differs from other PEs. But this divergence in function is seemingly at odds with the SIMD design philosophy. This too presents another dimension to an already difficult design challenge.
SUMMARY
It is therefore a general object of the invention to improve the versatility of a Mesh Connected Computer so that information can be more efficiently and quickly input into the processing array, manipulated within the array, and subsequently output from the array.
It is a further object of the invention to improve the versatility of a Mesh Connected Computer in an efficient manner which does not unduly increase the complexity of the mesh connected computer, or deviate from the Single Instruction-Multiple Data design paradigm.
These objects are satisfied by the present invention, which, according to one exemplary embodiment, comprises an apparatus including a rectangular array of processing elements (PEs) and a controller. The apparatus offers a number of techniques for shifting image data within the array. A first technique, the ROLL option, simultaneously shifts image planes in opposite directions within the array, in a manner analogous to the rolling tread of a tank. A second technique, the gated shift option, makes a normal shift of an image plane to neighboring PEs conditional, for each PE, upon a value stored in a mask register of each PE. A third technique, the carry propagate option, combines the computations from multiple selected PEs in order to complete an n-bit operation in fewer than n clocks by forming “supercells” within the array.
The apparatus also includes a multi-bit X Pattern register and a multi-bit Y Pattern register. These registers have bit values corresponding to respective columns (for the X Pattern register) and rows (for the Y Pattern register) of
Abercrombie Andrew P.
Holsztynski Wlodzimierz
Sutha Surachai
Burns Doane , Swecker, Mathis LLP
Donaghue Larry D.
Nguyen Dzung C.
TeraNex Inc.
LandOfFree
Input/output support for processing in a mesh connected... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Input/output support for processing in a mesh connected..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Input/output support for processing in a mesh connected... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2611128