Electrical computers and digital processing systems: processing – Processing architecture – Array processor
Reexamination Certificate
2000-08-22
2004-06-22
Coleman, Eric (Department: 2183)
Electrical computers and digital processing systems: processing
Processing architecture
Array processor
C712S022000
Reexamination Certificate
active
06754801
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of computer memory devices and, more particularly to the interconnections between processing elements in a massively parallel processor array.
2. Description of the Related Art
The fundamental architecture used by all personal computers (PCs) and workstations is generally known as the von Neumann architecture, illustrated in block diagram form in FIG.
1
. In the von Neumann architecture, a main central processing unit (CPU)
10
is used to sequence its own operations using a program stored in a memory
12
. The memory
12
, referred to herein as “main memory”, also contains the data on which the CPU
10
operates. In modern computer systems, a hierarchy of cache memories is usually built into the system to reduce the amount of traffic between the CPU
10
and the main memory
12
.
The von Neumann approach is adequate for low to medium performance applications, particularly when some system functions can be accelerated by special purpose hardware (e.g., 3D graphics accelerator, digital signal processor (DSP), video encoder or decoder, audio or music processor, etc.). However, the approach of adding accelerator hardware is limited by the bandwidth of the link from the CPU/memory part of the system to the accelerator. The approach may be further limited if the bandwidth is shared by more than one accelerator. Thus, the processing demands of large data sets, such as those commonly associated with large images, are not served well by the von Neumann architecture. Similarly, as the processing becomes more complex and the data larger, the processing demands will not be met even with the conventional accelerator approach.
It should be noted, however, that the von Neumann architecture has some advantages. For example, the architecture contains a homogenous memory structure allowing large memories to be built from many smaller standard units. In addition, because the processing is centralized, it does not matter where the data (or program) resides in the memory. Finally, the linear execution model is easy to control and exploit. Today's operating systems control the allocation of system memory and other resources using these properties. The problem is how to improve processing performance in a conventional operating system environment where multiple applications share and partition the system resources, and in particular, the main memory.
One solution is to utilize active memory devices, as illustrated in
FIG. 2
, in the computer system. Put simply, active memory is memory that can do more than store data; it can process it too. To the CPU
10
the active memory looks normal except that it can be told to do something with the data contents and without the data being transferred to the CPU or another part of the system (via the system bus). This is achieved by distributing processing elements (PEs)
14
through out the memory structure, which can all operate on their own local pieces of memory in parallel. In addition, the PEs
14
typically communicate with each other, as illustrated in
FIG. 3
, to exchange data. Thus, active memory encourages a somewhat different view of the computer architecture, i.e., “memory centered” or viewed from the data rather than the processor.
In a computer system having active memory, such as illustrated in
FIG. 2
, the work of the CPU
10
is reduced to the operating system tasks, such as scheduling processes and allocating system resources and time. Most of the data processing is performed within the memory
12
. By having a very large number of connections between the main memory
12
and the processing resources, i.e., the PEs
14
, the bandwidth for moving data in and out of memory is greatly increased. A large number of parallel processors can be connected to the memory
12
and can operate on their own area of memory independently. Together these two features can provide very high performance.
There are several different topologies for parallel processors. One example topology is commonly referred to as SIMD (single instruction, multiple data). The SIMD topology contains many processors, all executing the same stream of instructions simultaneously, but on their own (locally stored) data. The active memory approach is typified by SIMD massively parallel processor (MPP) architectures. In the SIMD MPP, a very large number of processors (usually a thousand or more) of relatively simple PEs are closely connected to a memory and organized so that each PE has access to its own piece of memory. All of the PEs execute the same instruction together, but on different data. The instruction stream is generated by a controlling sequencer or processor.
The SIMD MPP has the advantage that the control overheads of the system are kept to a minimum, while maximizing the processing and memory access bandwidths. SIMD MPPs, therefore, have the potential to provide very high performance very efficiently. Moreover, the hardware consists of many fairly simple repeating elements. Since the PEs are quite small in comparison to a reduced instruction set computer (RISC), they are quick to implement into a system design and their benefit with respect to optimization is multiplied by the number of processing elements. In addition, because the PEs are simple, it is possible to clock them fast and without resorting to deep pipelines.
In a massively parallel processor array the interconnections between processing elements, as illustrated in
FIG. 3
, are an important feature for exchanging data during processing. In conventional MPPs, the mechanism for the PEs to communicate with one another is usually achieved by means of a simple network of wires, as illustrated in
FIG. 3
, which are used to transfer data from one PE to its neighbors using a shift instruction. Thus, each PE simultaneously drives the value of a register out on its interconnection wire, and loads a register from one of its interconnection inputs. Many SIMD MPP's have used single bit PE's so the interconnections between PEs are implemented using a single wire per PE and a bit serial mode of operation. Accordingly, a single bit interconnection between processing elements is natural in such an array. As wider processing elements have been developed, however, a bit serial method of inter-processor data exchange has not fit well with the storage of data in the processing elements
14
. For example, recent implementations of MPPs have used wider data paths, such as for example 8 bits, to speed the computational performance of the PEs and the MPP array. However, the level of usage of the interconnection network does not always warrant the use of a data channel as wide as the data width supported by the PEs, simply because data movement does not require as many cycles as computation in a typical application algorithm. In other words, the processor will spend more time dong calculations than moving data from one PE to another.
Because of this, even when the PE bandwidth in an MPP is quite wide, the interconnection paths between the PEs has remained only 1-bit wide. Recently it has become possible to connect a PE to its memory with a full data width connection, especially with the advent of single chip MPPs. Accordingly, there is a desire and need for a SIMD MPP main memory device that allows for the use of wider data paths within the PEs to speed the computational performance of the PEs and the MPP array while still allowing for use of the simple 1-bit interconnection network to transfer data between PEs in the MPP.
SUMMARY OF THE INVENTION
The present invention mitigates the problems of the conventional MPPs by providing a system and method for using wider data paths within the PEs to speed the computational performance of the PEs and the MPP array while still allowing for use of the simple 1-bit interconnection network to transfer data between PEs in the MPP.
The above and other features and advantages of the invention are achieved by providing a register having a data width equal to the data width of the PE
Coleman Eric
Dickstein , Shapiro, Morin & Oshinsky, LLP
LandOfFree
Method and apparatus for a shift register based... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for a shift register based..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for a shift register based... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3308280