Electrical computers and digital data processing systems: input/ – Input/output data processing – Direct memory accessing
Reexamination Certificate
2001-05-14
2002-09-17
Shin, Christopher B. (Department: 2182)
Electrical computers and digital data processing systems: input/
Input/output data processing
Direct memory accessing
C711S203000
Reexamination Certificate
active
06453367
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to improvements in array processing, and more particularly to advantageous techniques for providing improved mechanisms of data distribution to, and collection from multiple memories often associated with and local to processing elements within an array processor.
BACKGROUND OF THE INVENTION
Various prior art techniques exist for the transfer of data between system memories or between system memories and I/O devices.
FIG. 1
shows a conventional data processing system
100
comprising a host uniprocessor
110
, processor local memory
120
, direct memory access (DMA) controller
160
, system memory
150
which is usually a larger memory store than the processor local memory, having longer access latency, and input/output (I/O) devices
130
and
140
.
The DMA controller
160
provides a mechanism for transferring data between processor local memory and system memory or I/O devices concurrent with uniprocessor execution. DMA controllers are sometimes referred to as I/O processors or transfer processors in the literature. System performance is improved since the host uniprocessor can perform computations while the DMA controller is transferring new input data to the processor local memory and transferring result data to output devices or the system memory. A data transfer is typically specified with the following minimum set of parameters: source address, destination address, and number of data elements to transfer. Addresses are interpreted by the system hardware and uniquely specify I/O devices or memory locations from which data must be read or to which data must be written. Sometimes additional parameters are provided such as element size. One of the limitations of conventional DMA controllers is that address generation capabilities for the data source and data destination are often constrained to be the same. For example, when only a source address, destination address and a transfer count are specified, the implied data access pattern is block-oriented, that is, a sequence of data words from contiguous addresses starting with the source address is copied to a sequence of contiguous addresses starting at the destination address. Array processing presents challenges for data collection and distribution both in terms of addressing flexibility, control and performance. The patterns in which data elements are distributed and collected from processing element local memories can significantly affect the overall performance of the processing system. With the advent of the ManArray architecture it has been recognized that it will be advantageous to have improved techniques for data transfer which provide these capabilities and which are tailored to this new architecture.
SUMMARY OF THE INVENTION
As described in detail below, the present invention addresses a variety of advantageous methods and apparatus for improved data transfer control within a data processing system. In particular we provide improved techniques for: distributing data to, and collecting data from an array of processing elements (PEs) in a flexible and efficient manner; and PE address translation which allows data distribution and collection based on PE virtual IDs.
Further aspects of the present invention are related to a virtual-to-physical PE ID translation which works together with a ManArray PE interconnection topology to support a variety of communication models (such as hypercube and mesh) through data placement based upon a PE virtual ID. This result can be accomplished in a DMA controller by translation, through a VID-to-PID lookup table or through combinational logic, where the resulting PID becomes an addressing component on the DMA bus to PE local memories. This result can also be achieved at the PE local memories within the interface logic, where a VID available to the interface logic is compared to a VID presented on the DMA bus. A match at a particular memory interface allows that memory to accept the access. The present invention also addresses the provision of PE addressing modes based on generating data access patterns from logically nested parameterized loops. Varying assignments of loop parameters to nesting level allows flexible data access patterns to be generated. Providing varying mechanisms for updating loop parameters provides greater flexibility for generating complex-periodic access patters, such as select-index modes which provide a table of index-update values which are used when the index loop parameter is updated; select-PE modes which provide a table of bit-vector control values, each of which specifies the PEs to be accessed for an iteration through the “PE update loop” (i.e., the loop which PE update is assigned); and select-index-PE modes which provide both select-index and select-PE update capability and combine to form the most flexible mode for generating complex-periodic data access patterns. Further, the invention addresses the design of a looping mechanism to be reentrant thereby allowing any addressing mode to be restarted after completing a specific number of element transfers, by just loading or reloading a new transfer count and continuing the transfer. This result is accomplished by initializing addressing parameters at instruction load time, and only updating them after a loop exits.
These and other advantages of the present invention will be apparent from the drawings and the Detailed Description which follow.
REFERENCES:
patent: 4538241 (1985-08-01), Levin et al.
patent: 5165023 (1992-11-01), Gifford
patent: 5301287 (1994-04-01), Herrell et al.
patent: 5418970 (1995-05-01), Gifford
patent: 5655151 (1997-08-01), Bowes et al.
patent: 5659798 (1997-08-01), Blumrich et al.
patent: 5696913 (1997-12-01), Gove et al.
patent: 5758182 (1998-05-01), Rosenthal et al.
patent: 5784706 (1998-07-01), Oberlin et al.
patent: 5802554 (1998-09-01), Caceres et al.
patent: 5802604 (1998-09-01), Stewart et al.
patent: 5828856 (1998-10-01), Bowes et al.
patent: 5828903 (1998-10-01), Sethuram et al.
patent: 5860025 (1999-01-01), Roberts et al.
patent: 5864876 (1999-01-01), Rossum et al.
patent: 5890201 (1999-03-01), McLellan et al.
patent: 6047307 (2000-04-01), Radko
patent: 6058437 (2000-05-01), Park et al.
patent: 6081854 (2000-06-01), Priem et al.
patent: 6256683 (2001-07-01), Barry
patent: 6260082 (2001-07-01), Barry et al.
BOPS, Inc.
Priest & Goldstein PLLC
Shin Christopher B.
LandOfFree
Methods and apparatus for providing direct memory access... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for providing direct memory access..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for providing direct memory access... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2831420