Electrical computers and digital processing systems: processing – Processing architecture – Array processor
Reexamination Certificate
2000-10-25
2002-03-12
Treat, William M. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing architecture
Array processor
C712S022000
Reexamination Certificate
active
06356993
ABSTRACT:
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
N/A
BACKGROUND OF THE INVENTION
The present invention relates generally to SIMD array processors, and more particularly to SIMD array processors that can efficiently process multi-dimensional node meshes that are elongated in at least one coordinate direction.
Single-Instruction Multiple-Data (SIMD) array processors are known which comprise multi-dimensional arrays of interconnected Processing Elements (PE's) executing the same instruction simultaneously on a plurality of different data samples. For example, a conventional SIMD array processor may include a two-dimensional “North, East, West, and South (NEWS) array” of PE's. The PE's of the NEWS array may be implemented on an Application Specific Integrated Circuit (ASIC) to simplify data I/O connections with dimensionally adjacent (“neighboring”) PE's in the array. Further, the PE's that are conceptually located along respective “edges” of the two-dimensional NEWS array comprise suitable North, East, West, and South data I/O paths for connecting these PE's with PE's that are physically located on either the same ASIC or a different ASIC.
Such conventional SIMD array processors can be used to solve a set of partial differential equations with associated boundary conditions that describe the nature of a physical environment over a finite volume of space. For example, a particular set of partial differential equations and boundary conditions may be approximated by a corresponding set of finite difference equations that describe values of dependent variables at a finite number of points or “nodes” distributed within a problem space (commonly known as a “node mesh”). After assigning each processing element in the NEWS array to at least one node in the mesh, the SIMD array processor can be used to calculate the dependent variable values at the finite number of nodes.
One drawback of such SIMD array processors is that they are frequently inefficient at solving problems having elongated node geometry. For example, in problems involving models of electromagnetic wave propagation through long wave-guides or models of fluid flow through long conduits, the number of nodes in the mesh distributed along the transverse cross-sectional coordinate directions may be smaller than the number of PE's in each coordinate direction of the NEWS array. As a result, when a node mesh for such a problem is mapped onto the NEWS array, communication distances between PE's that perform processing for adjacent nodes may be long enough to significantly increase the time required to solve the problem. To avoid such long communication distances between PE's, the node mesh may be mapped onto a rectangular subset of the NEWS array. However, when only a subset of the NEWS array is used, respective PE's in the subset may be called upon to handle the processing for more nodes in the mesh. This can also significantly increase the time required to solve the problem.
It would therefore be desirable to have an SIMD array processor that can efficiently adapt itself to process multi-dimensional node meshes that are elongated in at least one coordinate direction. Such an SIMD array processor would efficiently process node meshes of varying geometry without switching data I/O connections between PE's in the array.
BRIEF SUMMARY OF THE INVENTION
In accordance with the present invention, an SIMD array processor is provided that can efficiently process multi-dimensional node meshes that are elongated in at least one coordinate direction. The SIMD array processor includes a plurality of small processor arrays interconnected to form a larger N-dimensional array. Each small processor array can access 2N data I/O paths which it can use to communicate with 2N other small processor arrays in the larger N-dimensional array. Each small processor array conceptually located at an interior point of the larger N-dimensional array can communicate with 2N dimensionally adjacent small processor arrays. Each processor array conceptually located at one (1) of at least one pair of dimensionally opposite boundaries of the larger N-dimensional array is communicably coupleable to fewer than 2N dimensionally adjacent small processor arrays and at least one small processor array conceptually located at the dimensionally opposing boundary.
Other features, functions, and aspects of the invention will be evident from the Detailed Description of the Invention that follows.
REFERENCES:
patent: 4270169 (1981-05-01), Hunt et al.
patent: 4270170 (1981-05-01), Reddaway
patent: 4621339 (1986-11-01), Wagner et al.
patent: 4720780 (1988-01-01), Dolecek
patent: 4727503 (1988-02-01), McWhirter
patent: 4985832 (1991-01-01), Grondalski
patent: 4992933 (1991-02-01), Taylor
patent: 5038386 (1991-08-01), Li
patent: 5133073 (1992-07-01), Jackson et al.
patent: 5157785 (1992-10-01), Jackson et al.
patent: 5165023 (1992-11-01), Gifford
patent: 5179714 (1993-01-01), Graybill
patent: 5193202 (1993-03-01), Jackson et al.
patent: 5212777 (1993-05-01), Gove et al.
patent: 5239654 (1993-08-01), Ing-Simmons et al.
patent: 5253308 (1993-10-01), Johnson
patent: 5371896 (1994-12-01), Gove et al.
patent: 5410727 (1995-04-01), Jaffe et al.
patent: 5450604 (1995-09-01), Davies
patent: 5457789 (1995-10-01), Dietrich, Jr. et al.
patent: 5471627 (1995-11-01), Means et al.
patent: 5535410 (1996-07-01), Watanabe et al.
patent: 5577262 (1996-11-01), Pechanek et al.
patent: 5581773 (1996-12-01), Glover
patent: 5588152 (1996-12-01), Dapp et al.
patent: 5590356 (1996-12-01), Gilbert
patent: 5630162 (1997-05-01), Wilkinson et al.
patent: 5673396 (1997-09-01), Smolansky et al.
patent: 5717943 (1998-02-01), Barker et al.
patent: 5752068 (1998-05-01), Gilbert
patent: 5809292 (1998-09-01), Wilkenson et al.
patent: 5822608 (1998-10-01), Dieffenderfer et al.
patent: 5842031 (1998-11-01), Barker et al.
patent: 5892962 (1999-04-01), Cloutier
patent: 5963746 (1999-10-01), Barker et al.
patent: 6038580 (2000-03-01), Yeh
patent: 6085304 (2000-07-01), Morris et al.
A Reconfigurable Processor Array with Routing LSIs and General Purpose DSPs; Jacob Levison, et al.; pp. 102-116; IEEE 1992.
A Single-Chip, 1.6 Billion, 16-b MAC/s Multiprocessor DSP; B. Ackland, et al.; pp. 412-424; IEEE Journal of Solid-State Circuits; vol. 35 No. 3; Mar. 2000.
A 450-MHz RISC Microprocessor with Enhanced Instruction Set and Copper Connect; Carmine Nicoletta; et al.; pp. 1478-1491; IEEE Journal of Sold-State Circuits; vol. 34 No. 11; Nov. 1999.
Pyxsys Corporation
Treat William M.
Weingarten Schurgin, Gagnebin & Lebovici LLP
LandOfFree
Dual aspect ratio PE array with no connection switching does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Dual aspect ratio PE array with no connection switching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dual aspect ratio PE array with no connection switching will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2876355