Electrical computers and digital data processing systems: input/ – Intrasystem connection
Reexamination Certificate
2000-02-23
2002-07-23
Coleman, Eric (Department: 2183)
Electrical computers and digital data processing systems: input/
Intrasystem connection
C712S011000
Reexamination Certificate
active
06425026
ABSTRACT:
BACKGROUND
The present invention relates to parallel computing, more particularly to mesh connected computing, and even more particularly to the distribution, processing and reconstruction of images by means of a mesh connected computer having fewer processing elements than the size of the image.
In a number of technological fields, such as digital signal processing of video image data, it is necessary to perform substantially identical logical or arithmetic operations on large amounts of data in a short period of time. Parallel processing has proven to be an advantageous way of quickly performing the necessary computations. In parallel processing, an array of processor elements, or cells, is configured so that each cell performs logical or arithmetic operations on its own data at the same time that all other cells are processing their own data. Machines in which the logical or arithmetic operation being performed at any instant in time is identical for all cells in the array are referred to by several names, including Single Instruction-Multiple Data (SIMD) machines.
A common arrangement for such a machine is as a rectangular array of cells, with each interior cell being connected to its four nearest neighboring cells (designated north, south, east and west) and each edge cell being connected to a data input/output device. In this way, a mesh of processing elements is formed. Accordingly, the term “Mesh Connected Computer” (MCC) is often applied to this architecture.
In a MCC, each cell is connected as well to a master controller which coordinates operations on data throughout the array by providing appropriate instructions to the processing elements. Such an array proves useful, for example, in high resolution image processing. The image pixels comprise a data matrix which can be loaded into the array for quick and efficient processing.
Although SIMD machines may all be based upon the same generic concept of an array of cells all performing the same function in unison, parallel processors vary in details of cell design. For example, U.S. Pat. No. 4,215,401 to Holsztynski et al. discloses a cell which includes a random access memory (RAM), a single bit accumulator, and a simple logical gate. The disclosed cell is extremely simple and, hence, inexpensive and easily fabricated. A negative consequence of this simplicity, however, is that some computational algorithms are quite cumbersome so that it may require many instructions to perform a simple and often repeated task.
U.S. Pat. No. 4,739,474 to Holsztynski et al., represents a higher level of complexity, in which the logic gate is replaced by a full adder capable of performing both arithmetic and logical functions. This increase in the complexity of the cell's computational logic allows fewer cells to provide higher performance.
U.S. patent application Ser. No. 08/112,540, which was filed on Aug. 27, 1993 now U.S. Pat. No. 6,073,185, in the name of Meeker, and U.S. patent application Ser. No. 09/057,482, which was filed on Apr. 9, 1998 now U.S. Pat. No. 6,173,388, in the name of Andrew P. Abercrombie et al. each describe still further improvements in SIMD architecture computers.
As mentioned above, MCCs prove especially useful in applications such as high resolution image processing. Various types of sensors are capable of producing large quantities of data signals (henceforth referred to simply as “data”) that, when taken together, constitute an “image” of the sensed object or terrain. The term “image” is used broadly throughout this specification to refer not only to pictures produced by visible light, but also to any collection of data, from any type of sensor, that can be considered together to convey information about an object that has been sensed. In many applications, the object or terrain is sensed repeatedly, often at high speed, thereby creating many images constituting a voluminous amount of data. Very often, the image data needs to be processed in some way, in order to be useful for a particular application. While it is possible to perform this processing “off-line” (i.e., at a time after all of the data has been collected), the application that mandates the collection of image data may further require that the images be processed in “real-time”, that is, that the processing of the image data keep up with the rate at which it is collected from the sensor. Further complicating the image processing task is the fact that some applications require the sensing and real-time processing of images that are simultaneously collected from two or more sensors.
Examples of the need for high-speed image processing capability can be found in both military and civil applications. For example, future military weapon platforms will use diverse suites of high-data-rate infrared, imaging laser, television, and imaging radar sensors that require real-time automatic target detection, recognition, tracking, and automatic target handoff-to-weapons capabilities. Civil applications for form processing and optical character recognition, automatic fingerprint recognition, and geographic information systems are also being pursued by the government. Perhaps the greatest future use of real-time image processing will be in commercial applications like medical image enhancement and analysis, automated industrial inspection and assembly, video data compression, expansion, editing and processing, optical character reading, automated document processing, and many others.
Consequently, the need for real-time image processing is becoming a commonplace requirement in commercial and civil government markets as well in the traditional high-performance military applications. The challenge is to develop an affordable processor that can handle the tera-operations-per-second processing requirement needed for complex image processing algorithms and the very high data rates typical of video imagery.
One solution that has been applied to image processing applications with some success has been the use of high-performance digital signal processors (DSP), such as the Intel i860 or the Texas Instruments (TI) TMS320C40, which have architectures inspired by high-performance military vector processing algorithms, such as linear filters and the fast Fourier transform. However, traditional DSP architectural characteristics, such as floating point precision and concurrent multiply-accumulate (vector) hardware components, are less appropriate for image processing applications since they process with full precision whether it is needed or not.
New hardware architectures created specifically for image processing applications are beginning to emerge from the military aerospace community to satisfy the demanding requirements of civil and commercial image processing applications. Beyond the high input data rates and complex algorithms, the most unique characteristics of image processing applications are the two-dimensional image structures and the relatively low precision required to represent and process video data. Sensor input data precision is usually only 8 to 12 bits per pixel. Shape analysis edge operations can be accomplished with a single bit of computational precision. While it is possible that some other operations may require more than 12 bits, the average precision required is often 8 bits or less. These characteristics can be exploited to create hardware architectures that are very efficient for image processing.
Both hard-wired (i.e., algorithm designed-in hardware) and programmable image processing architectures have been tried. Because of the immaturity of image processing-algorithms, programmable image processing architectures (which, by definition, are more flexible than hard-wired approaches) are the most practical. These architectures include Single Instruction Single Data (SISD) uniprocessors, Multiple Data Multiple Instruction (MIMD) vector processors, and Single Instruction Multiple Data (SIMD) two-dimensional array processors.
Massively parallel SIMD operating architectures, having two-dimensional arrays of processing elements (PE), each opera
Del Fava Howard
Dennis Kevin
Morris Carl
Burns Doane , Swecker, Mathis LLP
Coleman Eric
TeraNex Inc.
LandOfFree
Distribution, processing, and reconstruction of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Distribution, processing, and reconstruction of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distribution, processing, and reconstruction of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2834169