Dynamic data routing mechanism for a high speed memory cloner Number:7,069,394 from the United States Patent and Trademark Office (PTO) owispatent A method for enabling concurrent, overlapping data moves associated with separate data clone operations of different memory cloners. A first data is being moved from its source to a destination. The first data is tagged with the address of the first destination to identify the data, and the data is sent over the fabric with the destination tag. A second data is concurrently (or subsequently) routed over the fabric to a next destination, while the first data is still in on the fabric. The second data is also tagged with its specific destination tag, which is different from the destination tag of the first data routed. Thus, the two sets of data overlap on the on the fabric but are each uniquely identified by their respective destination tag. Both the first and second data may also be tagged with a respective unique identifier (ID) associated with the memory cloner that initiated the particular clone operation. The unique IDs are re-used, and the number of bits for the unique ID is selected so that the first sequentially-numbered clone operation completes prior to a new clone operation requiring a unique ID.<H mechanism, routing, Dynamic, data, ro, 7069394.html, Patent, pto, 7069394

Title: Dynamic data routing mechanism for a high speed memory cloner

Abstract: A method for enabling concurrent, overlapping data moves associated with separate data clone operations of different memory cloners. A first data is being moved from its source to a destination. The first data is tagged with the address of the first destination to identify the data, and the data is sent over the fabric with the destination tag. A second data is concurrently (or subsequently) routed over the fabric to a next destination, while the first data is still in on the fabric. The second data is also tagged with its specific destination tag, which is different from the destination tag of the first data routed. Thus, the two sets of data overlap on the on the fabric but are each uniquely identified by their respective destination tag. Both the first and second data may also be tagged with a respective unique identifier (ID) associated with the memory cloner that initiated the particular clone operation. The unique IDs are re-used, and the number of bits for the unique ID is selected so that the first sequentially-numbered clone operation completes prior to a new clone operation requiring a unique ID.

Patent Number: 7,069,394 Issued on 06/27/2006 to Arimilli, et al.

Inventors: Arimilli; Ravi Kumar (Austin, TX); Goodman; Benjiman Lee (Cedar Park, TX); Joyner; Jody Bern (Austin, TX)
Assignee: International Business Machines Corporation (Armonk, NY)

Appl. No.: 313293

Filed: December 5, 2002

Current U.S. Class: 711/148 ; 711/165

Current International Class: G06F 12/00 (20060101)

Field of Search: 711/141,144,146,147,148,150,151,152,165

References Cited [Referenced By]

U.S. Patent Documents


6128714	October 2000	Onodera
6393540	May 2002	Blumenau et al.
6529968	March 2003	Anderson
6665783	December 2003	Zahir
6813522	November 2004	Schwarm et al.
2003/0153306	August 2003	Study et al.

Primary Examiner: Verbrugge; Kevin
Attorney, Agent or Firm: Salys; Casimer K. Dillon & Yudell LLP

Parent Case Text

CROSS REFERENCE TO RELATED APPLICATIONS

The present application shares specification text and figures with the following co-pending applications, which were filed concurrently with the present application: application Ser. No. 10/313,328 "Data Processing System With Naked Cache Line Write Operations;" application Ser. No. 10/313,277 "High Speed Memory Cloning Facility Via a Lockless Multiprocessor Mechanism;" application Ser. No. 10/313,281 "High Speed Memory Cloning Facility Via a Coherently Done Mechanism;" application Ser. No. 10/313,295 "Dynamic Software Accessibility to a Microprocessor System With a High Speed Memory Cloner;" application Ser. No. 10/313,323 "High Speed Memory Cloner Within a Data Processing System;" application Ser. No. 10/313,296 "High Speed Memory Cloning Facility Via A Source/Destination Switching Mechanism;" application Ser. No. 10/313,288 "High Speed Memory Cloner With Extended Cache Coherency Protocols and Responses;" and application Ser. No. 10/313,322 "Imprecise Cache Line Protection Mechanism During a Memory Clone Operation." The contents of the co-pending applications are incorporated herein by reference.

Claims

What is claimed is:

1. A multi-chip, multiprocessor data processing system comprising: at least two processor chips including a first chip with an associated first processor and first memory cloner and a second chip with an associated second processor and second memory cloner; a memory coupled to both said first processor chip and said second processor chip via a switch fabric; means for routing a first set of data over the fabric by the first memory cloner; means for concurrently routing a second set of data over the fabric by the second memory cloner; and wherein the first set of data is uniquely identified as belonging to the first move and the second set of data is also uniquely identified as belonging to the second move so that said first and second moves overlap on the fabric and are routed to their correct respective destinations.

2. The data processing system of claim 1, wherein said means for routing and means for concurrently routing further include means for tagging each block of data within the first and second sets of data with respective unique identifiers representing which memory cloner initiated the particular move and to which destination the block of data is to be routed.

3. The data processing system of claim 2, wherein said unique ID includes a number of additional bits appended to a data write operation, wherein said additional bits are utilized to track the sequential number of the clone operation, wherein each clone operation is assigned a next available sequential number.

4. The data processing system of claim 3, wherein: said number of bits is a design parameter selected so that a first sequentially numbered clone operation completes prior to a generation of a new clone operation by a memory cloner, where the new clone operation is a larger sequentially numbered clone operation than may be tracked via said number of bits; and wherein said new clone operation is assigned a sequential number of the first sequentially numbered clone operation that has completed.

5. The data processing system of claim 2, wherein said means for tagging includes identifying said block of data by including a destination identifier (ID) with said data, said destination ID corresponding to a destination address of a memory buffer to which said block of data is being routed, wherein no two concurrently initiated clone operations have a same destination ID.

6. The data processing system of claim 3, wherein: said number of bits enables reuse of a number assigned to a first data clone operation; and said data processing system further comprises: means for assigning a first tag number to said first data clone operation; means for snooping when a second data clone operation is assigned a same tag number while the first data clone operation is still being completed; and means for retrying said second data clone operation until said first data clone operation is completed, wherein said second data clone operation proceeds only after said first data clone operation completes, and wherein further no two concurrently executing data clone operations are able to share a tag number.

7. A method within a data processing system for enabling concurrent, over-lapping data movement associated with separate data clone operations of separate memory cloners, said method comprising: issuing from a first memory cloner a first modified read operation to a source address of data to be moved to a first destination, wherein said modified read operation includes the address of the first destination in place of a processor routing address from which the modified read was issued; tagging a first set of data from said source address with said address of the first destination to identify said first set of data as being routed to said first destination; routing said first set of data from said source address to said first destination via a switch fabric of the data processing system; issuing from a second memory cloner, a second modified read operation to a source address of data to be moved to a second destination; tagging a second set of retrieved data from said source address with an address of the second destination to identify said second set of data as being routed to said second destination, wherein said address of said first destination is different from that of said second destination so that said first and second set of data are uniquely tagged; and routing said second set of data to said second destination over the fabric while said first set of data is still being routed.

8. The method of claim 7, wherein said tagging steps include placing a respective destination address into a routing address block of the respective set of data.

9. The method of claim 7, wherein said tagging steps include tagging each block of data within the first and second sets of data with respective unique identifiers representing which memory cloner initiated the particular read operation and to which destination the block of data is to be routed.

10. The method of claim 9, wherein: said number of bits enables reuse of a number assigned to a first data clone operation; and said method further comprises: assigning a first tag number to said first data clone operation; snooping when a second data clone operation is assigned a same tag number while the first data clone operation is still being completed; and retrying said second data clone operation until said first data clone operation is completed, wherein said second data clone operation proceeds only after said first data clone operation completes, and wherein further no two concurrently executing data clone operations are able to share a tag number.

11. The method of claim 10, wherein each of said unique IDs include a number of additional bits appended to a data write operation, wherein said additional bits are utilized to track the sequential number of the clone operation, where each next clone operation is assigned a next available sequential number.

12. The method of claim 10, wherein: said number of bits is a design parameter selected so that a first sequentially numbered clone operation completes prior to a generation of a new clone operation by a memory cloner, where the new clone operation is a larger sequentially numbered clone operation than may be tracked via said number of bits; and wherein said new clone operation is assigned a sequential number of the first sequentially numbered clone operation, that has completed.

Description

BACKGROUND OF THE INVENTION

1. Technical Field

The present invention relates generally to data processing systems and in particular to data operations within a processor of a data processing system. Still more particularly, the present invention relates to a method and system for enabling overlapping operations on the fabric of a data processing system.

2. Description of the Related Art

The need for faster and less hardware-intensive processing of data and data operations has been the driving force behind the improvements seen in the field of data processing systems. Recent trends have seen the development of faster, smaller, and more complex processors, as well as the implementation of a multiprocessor configuration, which enables multiple interconnected processors to concurrently execute portions of a given task. In addition to the implementation of the multiprocessor configuration, systems were developed with distributed memory systems for more efficient memory access. Also, a switch-based interconnect (or switch) was implemented to replace the traditional bus interconnect.

The distributed memory enabled data to be stored in a plurality of separate memory modules and enhanced memory access in the multiprocessor configuration. The switch-based interconnect enabled the various components of the processing system to connect directly to each other and thus provide faster/more direct communication and data transmission among components.

FIG. 1 is a block diagram illustration of a conventional multiprocessor system with distributed memory and a switch-based interconnect (switch). As shown, multiprocessor data processing system 100 comprises multiple processor chips 101A-101D, which are interconnected to each other and to other system components via switch 103. The other system components included distributed memory 105, 107 (with associated memory controllers 106, 108), and input/output (I/O) components 104. Additional components (not shown) may also be interconnected to the illustrated components via switch 103. Processor chips 101A-101D each comprise two processor cores (processors) labeled sequentially P1-PN. In addition to processors P1-PN, processor chips 101A-101D comprise additional components/logic that together with processors P1-PN control processing operations within data processing system 100. FIG. 1 illustrates one such component, hardware engine 111, the function of which is described below.

In a multiprocessor data processing system as illustrated in FIG. 1, one or more memories/memory modules is typically accessible to multiple processors (or processor operations), and memory is typically shared by the processing resources. Since each of the processing resources may act independently, contention for the shared memory resources may arise within the system. For example, a second processor may attempt to write to (or read from) a particular memory address while the memory address is being accessed by a first processor. If a later request for access occurs while a prior access is in progress, the later request must be delayed or prevented until the prior request is completed. Thus, in order to read or write data from/to a particular memory location (or address), it is necessary for the processor to obtain a lock on that particular memory address until the read/write operation is fully completed. This eliminates the errors that may occur when the system unknowingly processes incorrect (e.g., stale) data.

Additionally, with faster, more complex, multiprocessor systems, multiple data requests may be issued simultaneously and exist in varying stages of completion. Besides coherency concerns, the processors have to ensure that a particular data block is not changed out of sequence of operation. For example, if processor P1 requires data block at address A to be written and processor P2 has to read the same data block, and if the read occurs in program sequence prior to the write, it is important that the order of the two operations be maintained for correct results.

Standard operation of data processing systems requires access to and movement or manipulation of data by the processing (and other) components. The data are typically stored in memory and are accessed/read, retrieved, manipulated, stored/written and/or simply moved using commands issued by the particular processor executing the program code.

A data move operation does not involve changes/modification to the value/content of the data. Rather, a data move operation transfers data from one memory location having a first physical address to another location with a different physical address. In distributed memory systems, data may be moved from one memory module to another memory module, although movement within a single memory/memory module is also possible.

In order to complete either type of move in current systems, the following steps are completed: (1) processor engine issues load and store instructions, which result in cache line ("CL") reads being transmitted from processor chip to memory controller via switch/interconnect; (2) memory controller acquires a lock on destination memory location; (3) processor is assigned lock destination memory location (by memory controller); (4) data are sent to processor chip (engine) from memory (source address) via switch/interconnect; (5) data are sent from processor engine to memory controller of destination location via switch/interconnect; (6) data are written to destination location; and (7) lock of destination is released for other processors. Inherent in this process is a built in latency of transferring the data from the source memory location to the processor chip and then from the processor chip to the destination memory location, even when a switch is being utilized.

Typically, each load and store operation moves an 8-byte data block. To complete this move requires rolling of caches, utilization of translation look-aside buffers (TLBs) to perform effective-to-read address translations, and further requires utilization of the processor and other hardware resources to receive and forward data. At least one processor system manufacturer has introduced hardware-accelerated load lines and store lines along with TLBs to enable a synchronous operation on a cache line at the byte level.

FIG. 1 is now utilized to illustrate the movement of data by processor P1 from one region/location (i.e., physical address) in memory to another. As illustrated in FIG. 1 and the directional arrows identifying paths 1 and 2, during the data move operation, data are moved from address location A in memory 105 by placing the data on a bus (or switch 103) along data path 1 to processor chip 101A. The data are then sent from processor chip 101A to the desired address location B within memory 107 along a data path 2, through switch 103.

To complete the data move operations described above, current (and prior) systems utilized either hardware engines (i.e., a hardware model) and/or software programming models (or interfaces).

In the hardware engine implementation, virtual addresses are utilized, and the hardware engine 111 controls the data move operation and receives the data being moved. The hardware engine 111 (also referred to as a hardware accelerator) initiates a lock acquisition process, which acquires locks on the source and destination memory addresses before commencing movement of the data to avoid multiple processors simultaneously accessing the data at the memory addresses. Instead of sending data up to the processor, the data is sent to the hardware engine 111. The hardware engine 111 makes use of cache line reads and enables the write to be completed in a pipelined manner. The net result is a much quicker move operation.

With software programming models, the software informs the processor hardware of location A and location B, and the processor hardware then completes the move. In this process, real addresses may be utilized (i.e., not virtual addresses). Accordingly, the additional time required for virtual-to-real address translation (or historical pattern matching) required by the above hardware model cab be eliminated. Also in this software model, the addresses may include offsets (e.g., address B may be offset by several bytes).

A typical pseudocode sequence executed by processor P1 to perform this data move operation is as follows:

TABLE-US-00001 LOCK DST ; lock destination LOCK SRC ; lock source LD A (Byte 0) ; A.sub.B0 (4B or 8B quantities) ST B (Byte 0) ; B.sub.B0 (4B/8B) INC ; increment byte number CMP ; compare to see if done BC ; branch if not done SYNC ; perform synchronization RL LOCK ; release locks

The byte number (B0, B1, B2), etc., is incremented until all the data stored within the memory region identified by address A are moved to the memory region identified by address B. The lock and release operations are carried out by the memory controller and bus arbiters, which assign temporary access and control over the particular address to the requesting processor that is awarded the locks.

Following a data move operation, processor P1 must receive a completion response (or signal) indicating that all the data have been physically moved to memory location B before the processor is able to resume processing other subsequent operations. This ensures that coherency exists among the processing units and the data coherency is maintained. The completion signal is a response to a SYNC operation, which is issued on the fabric by processor P1 after the data move operation to ensure that all processors receive notification of (and acknowledge) the data move operation.

Thus, in FIG. 1, instructions issued by processor P1 initiate the movement of the data from location A to location B. A SYNC is issued by processor P1, and when the last data block has been moved to location B, a signal indicating the physical move has completed is sent to processor P1. In response, processor P1 releases the lock on address B, and processor P1 is able to resume processing other instructions.

Notably, since processor P1 has to acquire the lock on memory location B and then A before the move operation can begin, the completed signal also signals the release of the lock and enables the other processors attempting to access the memory locations A and B to acquire the lock for either address.

Although each of the hardware and software models provides different functional benefits, both possessed several limitations. For example, both hardware and software models have built in latency of loading data from memory (source) up to the processor chip and then from the processor chip back to the memory (destination). Further, with both models, the processor has to wait until the entire move is completed and a completion response from the memory controller is generated before the processor can resume processing subsequent instructions/operations.

The present invention therefore realizes that it would be desirable to provide a method and system for more efficient data move operations. A method and system that enables multiple, concurrent clone operations on a fabric of the data processing system would be a welcomed improvement. These and several other benefits are provided by the present invention.

SUMMARY OF THE INVENTION

Disclosed is a method within a data processing system for enabling concurrent, overlapping data clone operations of separate memory cloners. A first modified read operation from a first memory cloner is issued to the source of the data being moved. The data are being moved to a first destination and the modified read operation includes the address of the first destination as the routing address for the data. The data routed by the first read operation are tagged with the address of the first destination to identify the data, and the data are sent over the fabric with the destination tag.

A second data are concurrently or subsequently routed over the fabric to a next destination, while the first data are still being transmitted on the fabric. The second data are also tagged with a specific destination tag, which is different from the destination tag of the data routed by the first read operation. Thus, the two data clone operations overlap on the on the fabric but are each uniquely identified by their respective destination tags.

In another embodiment both the first and second data are tagged with a respective unique identifier (ID) associated with the memory cloner that initiated the particular clone operation in addition to the respective destination tags. The unique ID includes additional bits appended to a data transfer operation, which bits are utilized to track the sequential number of the clone operation. Each clone operation is assigned a next sequential number. The unique IDs are re-used, and the number of bits for the unique ID is selected so that the first sequentially numbered clone operation completes prior to a new clone operation requiring a unique ID.

BRIEF DESCRIPTION OF THE DRAWINGS

The novel features believed characteristic of the invention are set forth in the appended claims. The invention itself, however, as well as a preferred mode of use, further objectives, and advantages thereof, will best be understood by reference to the following detailed description of an illustrative embodiment when read in conjunction with the accompanying drawings, wherein:

FIG. 1 is a block diagram illustrating a multiprocessor data processing system with a hardware engine utilized to move data according to the prior art;

FIG. 2 is a block diagram illustrating an exemplary memory-to-memory clone operation within a processing system configured with a memory cloner according to one embodiment of the present invention;

FIG. 3 is a block diagram illustrating components of the memory cloner of FIG. 2 according to one embodiment of the present invention;

FIG. 4A is a block diagram representation of memory locations X and Y within main memory, which are utilized to store the source and destination addresses for a memory clone operation according to one embodiment of the present invention;

FIG. 4B illustrates the flow of memory address operands and tags, including naked writes, on the (switch) fabric of the data processing system of FIG. 2 according to one embodiment of the present invention;

FIG. 5A is a flow chart illustrating the general process of cloning data within a data processing system configured to operate in accordance with an exemplary embodiment of the present invention;

FIG. 5B is a flow chart illustrating the process of issuing naked writes during a data clone operation in accordance with one implementation of the present invention;

FIG. 5C is a flow chart illustrating process steps leading to and subsequent to an architecturally done state according to one embodiment of the present invention;

FIG. 5D is a flow chart illustrating the process of issuing read operations physically moving data by issuing read operations in accordance with one embodiment of the invention;

FIG. 6A illustrates a distributed memory subsystem with main memory, several levels of caches, and external system memory according to one model for coherently sourcing/storing data during implementation of the present invention;

FIG. 6B illustrates a memory module with upper layer metals, which facilitate the direct cloning of data from a source to a destination within the same memory module without utilization of the external switch;

FIG. 7A is a block illustration of an address tag that is utilized to direct multiple concurrent data clone operations to a correct destination memory according to one embodiment of the present invention;

FIG. 7B is a block illustration of a register utilized by the memory cloner to track when naked writes are completed and the architecturally done state occurs according to one embodiment of the present invention;

FIG. 8A is a flow chart illustrating a process of lock contention within a data processing system that operates according to one embodiment of the present invention;

FIG. 8B is a flow chart illustrating a process of maintaining data coherency during a data clone operation according to one embodiment of the present invention;

FIG. 9A illustrates an instruction with an appended mode bit that may be toggled by software to indicate whether processor execution of the instruction occurs in real or virtual addressing mode according to one embodiment of the invention; and

FIG. 9B illustrates the application code, OS, and firmware layers within a data processing system and the associated type of address operation supported by each layer according to one embodiment of the invention.

DETAILED DESCRIPTION OF AN ILLUSTRATIVE EMBODIMENT

A. OVERVIEW

The present invention provides a high speed memory cloner associated with a processor (or processor chip) and an efficient method of completing a data clone operation utilizing features provided by the high speed memory cloner. The memory cloner enables the processor to continue processing operations following a request to move data from a first memory location to another without requiring the actual move of the data to be completed.

The invention introduces an architecturally done state for move operations. The functional features provided by the memory cloner include a naked write operation, advanced coherency operations to support naked writes and direct memory-to-memory data movement, new instructions within the instruction set architecture (e.g., optimized combined instruction set via pipelined issuing of instructions without interrupts), and mode bits for dynamically switching between virtual and real addressing mode for data processing. Additional novel operational features of the data processing system are also provided by the invention.

The invention takes advantage of the switch topology present in current processing systems and the functionality of the memory controller. Unlike current hardware-based or software-based models for carrying out move operations, which require data be sent back to the requesting processor module and then forwarded from the processor module to the destination, the invention implements a combined software model and hardware model with additional features that allow data to be routed directly to the destination. Implementation of the invention is preferably realized utilizing a processor chip designed with a memory cloner that comprises the various hardware and software logic/components described below.

The description of the invention provides several new terms, key among which is the "clone" operation performed by the high speed memory cloner. As utilized herein, the clone operation refers to all operations which take place within the high speed memory cloner, on the fabric, and at the memory locations that together enable the architecturally done state and the actual physical move of data. The data are moved from a point A to a point B, but in a manner that is very different from known methods of completing a data move operation. The references to a data "move" refer specifically to the instructions that are issued from the processor to the high speed memory controller. In some instances, the term "move" is utilized when specifically referring to the physical movement of the data as a part of the data clone operation. Thus, for example, completion of the physical data move is considered a part of the data clone operation.

B. HARDWARE FEATURES

Turning now to the figures and in particular to FIG. 2, there is illustrated a multiprocessor, switch-connected, data processing system 200, within which the invention may be implemented. Data processing system 200 comprises a plurality of processor modules/chips, two of which, chip 201A and 201D, are depicted. Processor chips 201A and 201D each comprise one or more processors (P1, P2, etc.). Within at least one of the process chips (e.g., processor chip 201 for illustration) is memory cloner 211, which is described below with reference to FIG. 3. Processor chips 201A and 201D are interconnected via switch 203 to each other and to additional components of data processing system 200. These additional components include distributed memory modules, two of which, memory 205 and 207, are depicted, with each having respective memory controller 206 and 208. Associated with memory controller 208 is a memory cache 213, whose functionality is described in conjunction with the description of the naked write operations below.

During implementation of a data clone operation, data is moved directly from memory location A of memory 205 to memory location B of memory 207 via switch 203. Data thus travels along a direct path 3 that does not include the processor or processor module. That is, the data being moved is not first sent to memory cloner 211 or processor P1. The actual movement of data is controlled by memory controllers 206 and 208 respectively (or cache controllers based on a coherent by model described below), which also control access to the memory 205 and 207, respectively, while the physical move is completing.

The illustrated configuration of processors and memory within data processing systems are presented herein for illustrative purposes only. Those skilled in the art understand that various functional features of the invention are fully applicable to a system configuration that comprises a non-distributed memory and/or a single processor/processor chip. The functional features of the invention described herein therefore applies to different configurations of data processing systems so long as the data processing system includes a high speed memory cloner and/or similar component with which the various functional features described herein may be accomplished.

High Speed Memory Cloner

Memory cloner 211 comprises hardware and software components by which the processes of the invention are controlled and/or initiated. Specifically, as illustrated in FIG. 3, memory cloner 211 comprises controlling logic 303 and translation look-aside buffer (TLB) 319. Memory cloner 211 also comprises several registers, including SRC address register 305, DST address register 307, CNT register 309, Architecturally DONE register 313, and clone completion register 317. Also included within memory cloner is a mode bit 315. The functionality of each of the illustrated components of memory cloner 211 is described at the relevant sections of the document.

Notably, unlike a hardware accelerator or similar component, memory cloner receives and issues address only operations. The invention may be implemented with a single memory cloner per chip. Alternatively, each microprocessor may have access to a respective memory cloner.

TLB 319 comprises a virtual address buffer 321 and a real address buffer 323. TLB 319, which is separate from the I-TLBs and D-TLBs utilized by processors P1, P2, etc. is fixed and operates in concert with the I-TLB and D-TLB. Buffers 321 and 323 are loaded by the OS at start-up and preferably store translations for all addresses referenced by the OS and processes so the OS page table in memory does not have to be read.

SRC, DST, and CNT Registers

In the illustrative embodiment of FIG. 3, memory cloner 211 comprises source (SRC) address register 305, destination (DST) address register 307, and count (CNT) register 309. As their names imply, destination address register 307 and source address register 305 store the destination and source addresses, respectively, of the memory location from and to which the data are being moved. Count register 309 stores the number of cache lines being transferred in the data clone operation.

The destination and source addresses are read from locations in memory (X and Y) utilized to store destination and source addresses for data clone operations. Reading of the source and destination addresses is triggered by a processor (e.g., P1) issuing one or more instructions that together causes the memory cloner to initiate a data clone operation as described in detail below.

C. GENERAL PROCESSES FOR DATA CLONE OPERATION

FIG. 5A illustrates several of the major steps of the overall process completed by the invention utilizing the above described hardware components. The process begins at block 501 after which processor P1 executes instructions that constitutes a request to clone data from memory location A to memory location B as shown at block 503. The memory cloner receives the data clone request, retrieves the virtual source and destination addresses, looks up the corresponding real addresses, and initiates a naked WR operation as indicated at block 505. The naked WR operation is executed on the fabric, and the memory cloner monitors for an architecturally DONE state as illustrated at block 507. Following the indication that the clone operation is architecturally DONE, and as shown at block 509, the memory cloner signals the processor that the clone operation is completed, and the processor continues processing as if the data move has been physically completed. Then, the memory cloner completes the actual data move in the background as shown at block 511, and the memory cloner performs the necessary protection of the cache lines while the data is being physically moved. The process then ends as indicated at block 513. The processes provided by the individual blocks of FIG. 5A are expanded and described below with reference to the several other flow charts provided herein.

With reference now to FIG. 5B, there is illustrated several of the steps involved in completing block 505 of FIG. 5A. The process begins at block 521 and then moves to block 523, which illustrates the destination and source addresses for the requested data clone operation being retrieved from memory locations X and Y and placed in the respective registers in the memory cloner. The count value (i.e., number of cache lines of data) is also placed in the CNT register as shown at block 525. The source and destination token operations are then completed as shown at block 526. Following, naked CL WRs are placed on the fabric as shown at block 527. Each naked CL WR receives a response on the fabric from the memory controller. A determination is made at block 529 whether the response is a NULL. If the response is not a NULL, the naked CL WR operation is retried as shown at block 531. When the response is a NULL, however, the naked CL WR is marked as completed within memory cloner 211, as shown at block 533. The various steps illustrated in FIG. 5B are described in greater details in the sections below.

Move Operands and Retrieval of Move Addresses

To enable a clear understanding of the invention, implementation of a data clone operation will be described with reference to small blocks of program code and to cloning of data from a memory location A (with virtual address A and 0real address A1) to another memory location B (with virtual address B and real address B1). Thus, for example, a sample block of program code executed at processor P1 that results in the cloning of data from memory location A to memory location B is as follows:

TABLE-US-00002 ST X (address X holds virtual source address A) ST Y (address Y holds virtual destination address B) ST CNT (CNT is the number of data lines to clone) SYNC ADD

The above represents sample instructions received by the memory cloner from the processor to initiate a clone operation. The ADD instruction is utilized as the example instruction that is not executed by the processor until completion of the data clone operation. The memory cloner initiates a data clone operation whenever the above sequence of instructions up to the SYNC is received from the processor. The execution of the above sequence of instructions at the memory cloner results in the return of the virtual source and destination addresses to the memory cloner and also provides the number of lines of data to be moved. In the illustrative embodiment the value of CNT is equal to the number of lines within a page of memory, and the clone operation is described as cloning a single page of data located at address A1.

FIG. 4A illustrates memory 405, which can be any memory 205, 207 within the memory subsystem, with block representation of the X and Y memory locations within which the source and destination addresses, A and B, for the data clone operation reside. In one embodiment, the A and B addresses for the clone operation are stored within X and Y memory locations by the processor at an earlier execution time. Each location comprises 32 bits of address data followed by 12 reserved bits. According to the illustrated embodiment, the first 5 of these additional 12 bits are utilized by a state machine of the data processing system to select which one of the 32 possible pages within the source or destination page address ranges are being requested/accessed.

As shown in FIG. 4A, the X and Y addresses are memory locations that store the A and B virtual addresses, and when included in a store request (ST), indicates to the processor and the memory cloner) that the request is for a data clone operation (and not a conventional store operation). The virtual addresses A and B correspond to real memory addresses A1 and B1 of the source and destination of the data clone operation and are stored within SRC address register 305 and DST address register 307 of memory cloner 211. As utilized within the below description of the memory clone operation, A and B refer to the addresses, which are the data addresses stored within the memory cloner, while A1 and B1 refer to the real memory addresses issued to the fabric (i.e., out on the switch). Both A and A1 and B and B1 respectively represent the source memory location and destination memory location of the data clone operation.

In the illustrative embodiment, when memory cloner 211 receives the processor and sequence of ST commands followed by a SYNC, TLB 319 looks up the real addresses X1 and Y1, from the virtual addresses (X and Y) respectively. X1 and Y1 are memory locations dedicated to storage of the source and destination addresses for a memory clone operation. Memory cloner 211 issues the operations out to the memory via switch (i.e., on the fabric), and the operations access the respective locations and return the destination and source addresses to memory cloner 211. Memory cloner 211 receives the virtual addresses for source (A) and destination (B) from locations X1 and Y1, respectively. The actual addresses provided are the first page memory addresses.

The memory cloner 211 stores the source and destination addresses and the cache line count received from processor P1 in registers 305, 307, 309, respectively. Based on the value stored within the CNT register 309, the memory cloner is able to generate the sequential addresses beginning with the addresses within the SRC register 305 and DST register 307 utilizing the first 5 appended bits of the 12 reserved bits, numbered sequentially from 0 to 31.

For example, with a clone operation in which a 4 Kbyte page of data with 128-byte lines is being moved from memory address A1 (with 4K aligned addresses) to memory address B1 (also having 4K aligned addresses), a count value of 32 is stored in CNT register 309 corresponding to the state machine address extensions 00000 through 11111, which are appended to the source address in the first five bits. These address extensions are settable by the state machine (i.e., a counter utilized by the memory cloner) and identify which address blocks within the page are being moved.

Also, an additional feature of the invention enables cloning of partial memory pages in addition to entire pages. This feature is relevant for embodiments in which the move operation occurs between memory components with different size cache lines, for example.

In response to receipt of the virtual source and destination addresses, the memory cloner 211 performs the functions of (1) storing the source address (i.e., address A) in SRC register 305 and (2) storing the destination address (i.e., address B) in the DST register 307. The memory cloner 211 also stores the CNT value received from the processor in CNT register 309. The source and destination addresses stored are virtual addresses generated by the processor during prior processing. These addresses may then be looked up by TLB 319 to determine the corresponding real addresses in memory, which addresses are then used to carry out the data clone operation described below.

D. TOKEN OPERATIONS

Returning now to block 526, before commencing the write and read operations for a memory clone, the memory cloner issues a set of tokens (or address tenures) referred to as the source (SRC) token and destination (DST) token, in the illustrative embodiment. The SRC token is an operation on the fabric, which queries the system to see if any other memory cloner is currently utilizing the SRC page address. Similarly, the DST token is an operation on the fabric, which queries the system to see if any other memory cloner is currently utilizing the DST page address.

The SRC and DST tokens are issued by the memory cloner on the fabric prior to issuing the operations that initiate the clone operation. The tokens of each memory cloner are snooped by all other memory cloners (or processors) in the system. Each snooper checks the source and destination addresses of the tokens against any address currently being utilized by that snooper, and each snooper then sends out a reply that indicates to the memory cloner that issued the tokens whether the addresses are being utilized by one of the snoopers. The token operation ensures that no two memory cloners are attempting to read/write to the same location. The token operation also ensures that the memory address space is available for the data clone operation.

The use of tokens prevents multiple memory cloners from concurrently writing data to the same memory location. In addition to preventing multiple, simultaneous updates to a memory location by different operations, the token operations also help avoid livelocks, as well as ensure that coherency within the memory is maintained. The invention also provides additional methods to ensure that processors do not livelock, as discussed below.

Utilizing the token address operands enables the memory cloner to receive a clear signal with respect to the source and destination addresses before commencing the series of write operations. Once the memory cloner receives the clear signal from the tokens, the memory cloner is able to begin the clone operation by issuing naked cache line (CL) write (WR) operations and then CL read (RD) operations.

Token operations are then generated from the received source and destination addresses, and the tokens operations are issued to secure a clear response to access the respective memory locations. The SRC and DST token operations are issued on the fabric to determine if the requested memory locations are available to the cloner (i.e., not being currently utilized by another processor or memory cloner, etc.) and to reserve the available addresses until the clone operation is completed. Once the DST token and the SRC token operations return with a clear, the memory cloner begins protecting the corresponding address spaces by snooping other requests for access to those address spaces as described below.

Notably, in one embodiment, a clone operation is allowed to begin once the response from the DST token indicates that the destination address is clear for the clone operation (even without receiving a clear from the SRC token). This embodiment enables data to be simultaneously sourced from the same source address and thus allows multiple, concurrent clone operations with the same source address. One primary reason for this implementation is that unlike traditional move operations, the clone operation controlled by the memory cloner begins with a series of naked write operations to the destination address, as will be described in detail below.

An example of the possible data sourcing operations that are capable based on the utilization of tokens is now provided. In this example, "A" is utilized to represent the source address from which data is being sourced. "B" represents the address of the destination to which the memory clone is being completed, and "O" represents a memory address for another process (e.g., a clone operation) that may be attempting to access location A or B corresponding to address A or B, respectively. When data is being sourced from A to B, data may also concurrently be sourced from A to O. However, no other combinations are possible while a data clone is occurring. Among these other combinations are: A to B and O to B; A to B and B to O; and A to B and O to A. Note, in each combination, S is assumed to be the address from which the data is sourced. Thus, the invention permits multiple memory moves to be sourced from the same memory location. However, when the destination address is the same as the snooped source address, the snooper issues a retry to a conflicting SRC token and DST token, depending on which was first received.

E. NAKED WRITE OPERATIONS

Naked Writes

Referring now to block 527 of FIG. 5B, The invention introduces a new write operation and associated set of responses within the memory cloner. This operation is a cache line write with no data tenure (also referred to as a naked write because the operation is an address-only operation that does not include a data tenure (hence the term "naked"). The naked write is issued by the memory cloner to begin a data clone operation and is received by the memory controller of the memory containing the destination memory location to which the data are to be moved. The memory controller generates a response to the naked write, and the response is sent back to the memory cloner.

The memory cloner thus issues write commands with no data (interchangeably referred to as naked writes), which are placed on the fabric and which initiate the allocation of the destination buffers, etc., for the data being moved. The memory cloner issues 32 naked CL writes beginning with the first destination addresses, corresponding to address B, plus each of the 31 other sequential page-level address extensions. The pipelining of naked writes and the associated responses, etc., are illustrated by FIG. 4B.

The memory cloner issues the CL WR in a sequential, pipelined manner. The pipelining process provides DMA CL WR (B.sub.0-B.sub.31) since the data is written directly to memory. The 32 CL WR operations are independent and overlap on the fabric.

Response to Naked CL Write

FIG. 4B illustrates cache line (CL) read (RD) and write (WR) operations and simulated line segments of a corresponding page (i.e., A.sub.0-A.sub.31 and B.sub.0-B.sub.31) being transmitted on the fabric. Each operation receives a coherency response described below. As illustrated, the naked CL writes are issued without any actual data being transmitted. Once the naked CL WRs are issued, a coherency response is generated for each naked write indicating whether the memory location B is free to accept the data being moved. The response may be either a Null or Retry depending on whether or not the memory controller of the particular destination memory location is able to allocate a buffer to receive the data being moved.

In the illustrative embodiment, the buffer represents a cache line of memory cache 213 of destination memory 207. During standard memory operation, data that is sent to the memory is first stored within memory cache 213 and then the data is later moved into the physical memory 207. Thus, memory controller checks a particular cache line that is utilized to store data for the memory address of the particular naked CL WR operation. The term buffer is utilized somewhat interchangeably with cache line, although the invention may also be implemented without a formal memory cache structure that may constitute the buffer.

The coherency response is sent back to the memory cloner. The response provides an indication to the memory cloner whether the data transfer can commence at that time (subject to coherency checks and availability of the source address). When the memory controller is able to allocate the buffer for the naked CL WR, the buffer is allocated and the memory controller waits for the receipt of data for that CL. In addition to the Null/Retry Response, a destination ID tag is also provided for each naked CLWR as shown in FIG. 4B. Utilization of the destination ID is described with reference to the CLR operations described with reference to FIG. 5D.

F. ARCHITECTURALLY DONE STATE

FIG. 5C illustrates the process by which an architecturally DONE state occurs and the response by the processor to the architecturally DONE state. The process begins as shown at block 551 and the memory cloner monitors for Null responses to the issued naked CL WR operations as indicated at block 553. A determination is made at block 553 whether all of the issued naked CL Wrs have received a Null response from the memory controller. When the memory controller has issued a NULL response to all of the naked CL WR operations, the entire move is considered "architecturally DONE," as shown at block 557 and the memory cloner signals the requesting processor that the data clone operation has completed even though the data to be moved have not even been read from the memory subsystem. The process then ends at block 559. The processor resumes executing the subsequent instructions (e.g., ADD instruction following the SYNC in the example instruction sequence).

The implementation of the architecturally DONE state is made possible because the data are not received by the processor or memory cloner. That is, the data to be moved need not be transmitted to the processor chip or the memory cloner, but are instead transferred directly from memory location A to memory location B. The processor receives an indication that the clone operation has been architecturally DONE once the system will no longer provide "old" destination data to the processor.

Thus, from the processor's perspective, the clone operation may appear to be complete even before any line of data is physically moved (depending on how quickly the physical move can be completed based on available bandwidth, size of data segments, number of overlapping moves, and other processes traversing the switch, etc.). When the architecturally DONE state is achieved, all the destination address buffers have been allocated to receive data and the memory cloner has issued the corresponding read operations triggering the movement of the data to the destination address. From a system synchronization perspective, although not all of the data has began moving or completed moving, the processor is informed that the clone operation is completed and processor assumes that the processor-issued SYNC operation has received an ACK response, which indicates completion of the clone operation.

One benefit of the implementation of the architecturally done state is that the processor is made immune to memory latencies and system topologies since it does not have to wait until the actual data clone operation completes. Thus, processor resources allocated to the data clone operation and which are prevented from processing subsequent instructions until receipt of the ACK response are quickly released to continue processing other operations with minimal delay after the data clone instructions are sent to the memory cloner.

Register-Based Tracking of Architecturally Done State

In one embodiment, a software or hardware register-based tracking of the Null responses received is implemented. The register is provided within memory clone 211 as illustrated in FIG. 2. With a CNT value of 32, for example, the memory cloner 211 is provided a 32-bit software register 313 to track which ones of the 32 naked CL writes have received a Null response. FIG. 7B illustrates a 32-bit register 313 that is utilized to provide an indication to the memory cloner that the clone operation is at least partially done or architecturally done. The register serves as a progress bar that is monitored by the memory cloner. Instead of implementing a SYNC operation, the memory cloner utilizes 313 to monitor/record which Null responses have been received. Each bit is set to "1" once a Null response is received for the correspondingly numbered naked CL write operation. According to the illustrated embodiment, naked CL write operations for destination memory addresses associated with bits 1, 2, and 4 have completed, as evidenced by the "1" placed in the corresponding bit locations of register 313.

In the illustrative embodiment, the determination of the architecturally DONE state is completed by scanning the bits of the register to see if all of the bits are set (1) (or if any are not set). Another implementation involves ORing the values held in each bit of the register. In this embodiment, the memory cloner signals the processor of the DONE state after ORing all the Null responses for the naked writes. When all bit values are 1, the architecturally DONE state is confirmed and an indication is sent to the requesting processor by the memory cloner. Then, the entire register 313 is reset to 0.

In the illustrated embodiment, an N-bit register is utilized to track which of the naked writes received a Null response, where N is a design parameter that is large enough to cover the maximum number of writes issued for a clone operation. However, in some cases, the processor is only interested in knowing whether particular cache lines are architecturally DONE. For these cases, only the particular register location associated with those cache lines of interest are read or checked, and memory cloner signals the processor to resume operation once these particular cache lines are architecturally DONE.

G. DIRECT MEMORY-TO-MEMORY MOVE VIA DESTINATION ID TAG

Read Requests

Returning now to FIG. 4B, and with reference to the flow chart of FIG. 5D, the process of issuing read operations subsequent to the naked Write operations is illustrated. The process begins at block 571 and the memory cloner monitors for a NULL response to a naked CL WR as shown at block 573. A determination is made at block 575 whether a Null response was received. The memory cloner retries all naked CL WRs that do not receive a Null response until a Null response is received for each naked CL WR. As shown at block 577, when a Null response is received at the memory cloner, a corresponding (address) CL read operation is immediately issued on the fabric to the source memory location in which the data segment to be moved currently resides. For example, a Null response received for naked CL WR(B.sub.0) results in placement of CL RD(A.sub.0) on the fabric and so on as illustrated in FIG. 4B. The memory controller for the source memory location checks the availability of the particular address within the source memory to source data being requested by the CL read operation (i.e., whether the address location or data are not being currently utilized by another process). This check results in a Null response (or a Retry).

In one embodiment, when the source of the data being cloned is not available to the CL RD operation, the CL RD operation is queued until the source becomes available. Accordingly, retries are not required. However, for embodiments that provide retries rather than queuing of CL RD operations, the memory cloner is signaled to retry the specific CL RD operation.

Destination ID Tag on Fabric

As illustrated in FIG. 4B, a destination ID tag is issued by the memory controller of the destination memory along with the Null response to the naked CL WR. The generated destination ID tag may then be appended to or inserted within the CL RD operation (rather than, or in addition to, the ID of the processor). According to the illustrated embodiment, the destination ID tag is placed on the fabric with the respective CL RD request. The destination ID tag is the routing tag that is provided to a CL RD request to identify the location to which the data requested by the read operation is to be returned. Specifically, the destination ID tag identifies the memory buffer (allocated to the naked CL WR operation) to receive the data being moved by the associated CL RD operation.

FIG. 7A illustrates read and write address operations 705 along with destination ID tags 701 (including memory cloner tags 703), which are sent on the fabric. The two is utilized to distinguish multiple clone operations overlapping on the fabric. As shown in FIG. 7A, address operations 705 comprises 32 bit source (SRC) or destination (DST) page-level address and the additional 12 reserve bits, which include the 5 bits being utilized by the controlling logic 303 of memory cloner 211 to provide the page level addressing.

Associated with address operation 705 is the destination ID tag 701, which comprises the ID of the memory cloner that issued the operation), the type of operation (i.e., WR, RD, Token (SRC) or Token (DST)), the count value (CNT), and the ID of the destination unit to send the response/data of the operation. As illustrated, the Write operations are initially sent out with the memory cloner address in the ID field as illustrated in the WR tag of FIG. 7A. The SRC address is replaced in the RD operation with the actual destination memory address as shown in the RD tag of FIG. 7A.

Direct Source-to-Destination Move

In order to complete a direct memory-to-memory data move, rather than a move that is routed through the requesting processor (or memory cloner), the memory cloner replaces the physical processor ID in the tag of the CL RD operation with the real memory address of the destination memory location (B) (i.e., the destination ID). This enables data to be sent directly to the memory location B (rather than having to be routed through the memory cloner) as explained below.

In current systems, the ID of the processor or processor chip that issues a read request is included within the read request or provided as a tag to the read request to identify the component to which the data are to be returned. That is, the ID references the source of the read operation and not the final destination to which the data will be moved.

The memory controllers automatically routes data to the location provided within the destination tag. Thus, with current systems, the data are sent to the processor. According to the embodiment described herein, however, since the routing address is that of the final (memory) destination, the source memory controller necessarily routes the data directly to the destination memory. Data is transferred from source memory directly to destination memory via the switch. The data is never sent through the processor or memory cloner, removing data routing operations from the processor. Notably, in the embodiment where the data is being moved within the same physical memory block, the data clone may be completed without data being sent out to the external switch fabric.

Tracking Completion of Data Clone Operation

In one embodim