Buffered transfer of data blocks between memory and processors independent of the order of allocation of locations in the buffer

A data transfer system uses a data buffer and individual control of each storage location within the data buffer for improved control of data block transfers. The storage locations are assigned deallocate, active, or valid assignment bands to enable transfer control of the data blocks within the system. The deallocated storage locations are returned to an allocation pool for use as a future resource, where the active and valid assignment bands remain unavailable until deallocated. Error checking and depth control prohibit consecutive allocation or deallocation assignments as well as overflow.

FIELD OF THE INVENTION

The present invention relates in general to buffer control, and more particularly, to buffer control which facilitates data block transfer independently of the position of the data blocks within the buffer.

BACKGROUND OF THE INVENTION

Today's computing architectures are designed to provide the sophisticated computer user with increased Reliability, Availability, and Scalability (RAS). To that end, the rise of the Microsoft Windows NT/2000 operating environment has presented a relatively low cost solution to the traditional high-end computing environment. The introduction of the Enterprise Edition has extended the scalability and resilience of the NT Server to provide a powerful and attractive solution to today's largest and most mission critical applications.

The Cellular MultiProcessing (CMP) architecture is a software/hardware environment that is developing as the enabling architecture that allows the Windows NT/2000 based servers to perform in such mission critical solutions. The CMP architecture incorporates high performance Intel processors using special hardware and middleware components that build on standard interface components to expand the capabilities of the Microsoft Windows server operating systems. The CMP architecture utilizes a Symmetric MultiProcessor (SMP) design, which employs multiple processors supported by high throughput memory, Input/Output (IO) systems and supporting hardware elements to bring about the manageability and resilience required for enterprise class servers.

Key to the CMP architecture is its ability to provide multiple, independent partitions, each with their own physical resources and operating system. Partitioning requires the flexibility required to support various application environments with increased control and greater resilience. Multiple server applications can be integrated into a single platform with improved performance, superior integration and lower costs to manage.

The objectives of the CMP architecture are multifold and may consist at least of the following: 1.) to provide scaling of applications beyond what is normally possible when running Microsoft Windows server operating systems on an SMP system; 2.) to improve the performance, reliability and manageability of a multiple application node by consolidating them on a single, multi-partition system; 3.) to establish new levels of RAS for open servers in support of mission critical applications; and 4.) to provide new levels of interoperability between operating systems through advanced, shared memory techniques.

The concept of multiprocessors sharing the workload in a computer relies heavily on shared memory. True SMP requires each processor to have access to the same physical memory, generally through the same system bus. When all processors share a single image of the memory space, that memory is said to be coherent, where data retrieved by each processor from the same memory address is going to be the same. Coherence is threatened, however, by the widespread use of onboard, high speed cache memory. When a processor reads data from a system memory location, it stores that data in high speed cache. A successive read from the same system memory address results instead, in a read from the cache, in order to provide an improvement in access speed. Likewise, writes to the same system memory address results instead to writes to the cache, which ultimately leads to data incoherence. As each processor maintains its own copy of system level memory within its cache, subsequent data writes cause the memory in each cache to diverge.

A common method of solving the problem of memory coherence in SMP dedicated cache systems is through bus snooping. A processor monitors the address bus for memory addresses placed on it by other processors. If the memory address corresponds to an address whose contents were previously cached by any other processor, then the cache contents relating to that address are marked as a cache fault for all processors on the next read of that address, subsequently forcing a read of system memory. One major difficulty, however, in a multi-processor environment, is overloading the memory bus through the use of bus snooping, which results in a scalability limitation.

Another problem existing within SMP systems is the concept of data management between the multiple processors and their corresponding shared memory pool. Traditional methods of data transfer utilized First-In, First-Out (FIFO) buffers to temporarily store data until a particular processor or memory pool required the data. In an SMP environment, however, the distinct possibility exists that data required by one processor is blocked by the FIFO because other data preceding is not ready for transfer, thus blocking data transfer to the processor and thus slowing operation.

A need exists, therefore, to provide a non-blocking data management system and corresponding data management control to allow fully, non-blocking data transfer to exist and ultimately increase efficiency.

SUMMARY OF THE INVENTION

The present invention is directed to a method and apparatus for controlling access to a non-blocking buffer. One of three assignment bands are associated with each storage location within the non-blocking buffer to restrict read and write access. Individual read and write pointers are used to independently control data written to and data read from the non-blocking buffer.

In accordance with one embodiment of the invention, a method for controlling data block transfers is presented. The method comprises maintaining a pool of available storage locations within a buffer, allocating a storage location from the pool in response to a pending data block transfer, transferring a data block into the allocated storage location, and retrieving the data block from the allocated storage location, wherein retrieving the data block is independent of the position of the storage location within the buffer.

In accordance with another embodiment of the invention, a multiprocessor system is presented. The multiprocessor system comprises a plurality of multiprocessors sharing a common system bus with access to a common memory pool and a node controller coupled to each of the plurality of multiprocessors. The node controller comprises a plurality of buffers coupled to receive data blocks and coupled to provide the data blocks independently of a position of the data blocks within the plurality of buffers, and a buffer tracker coupled to the plurality of buffers to control data block transfer according to assignment bands associated with the data blocks.

In accordance with another embodiment of the invention, a method of maintaining an assignment band of a data block within a buffer to control access to the data block is presented. The method comprises establishing a first assignment band for the data block in response to receiving an allocation request, establishing a second assignment band for the data block when data is written to the data block in accordance with a first data pointer, and establishing a third assignment band for the data block when data is read from the data block in accordance with a second data pointer.

The above summary of the present invention is not intended to describe each illustrated embodiment or implementation of the present invention. This is the purpose of the figures and the associated discussion which follows.

DETAILED DESCRIPTION

FIG. 1illustrates an exemplary block diagram of a processing cell in accordance with the present invention. A typical processing cell, or sub-pod, is comprised of multiple Central Processing Units102–108and a corresponding Cache110. The processing units may be of the 128 bit McKinley processor family as produced by Intel Corp., the 64-bit, IA-64 Itanium family, also produced by Intel Corp., or may, for example, be of the 32-bit, Xeon processing family, also produced by Intel Corp. Each of processors102–108share Cache110through bus120, where bus120may serve up to, for example, four processors102–108. Memory Storage Units114provides a shared memory pool for Processors102–108through non-blocking cross-bar112. Direct IO Bridge116provides high-throughput access to Peripheral Component Interconnect devices118. It should be noted that the present invention is not limited for use with only those processors listed above, but may be used with any processor that is compatible within a multi-processing environment.

Memory Storage Unit114may consist of up to four main memory banks each of which may contain a maximum of 16 GigaBytes of Random Access Memory. Likewise, Cache110may comprise up to four banks of cache (not shown), each cache bank may contain up to 32 MegaByte of RAM, which is on the order of five times faster than Memory Storage Unit114RAM. Each cache bank has a dedicated, direct connection to each of Memory Storage Units114, each direct connection being supported by crossbar112. Memory Storage Unit114has a typical mainframe design, such that each Memory Storage Unit114may handle hundreds of access requests concurrently. Even higher performance may be realized by allowing interleaving between each Memory Storage Unit114. When interleaving is enabled, data may be spread across all Memory Storage Units114and may be accessed in parallel by any one of Processors102–108and/or Cache110. Crossbar112allows for fast, consistently low latency, high bandwidth transmissions between cache110and IO bridge116.

Multiple sub-pods, like the sub-pod illustrated inFIG. 1, may be combined to provide a highly scalable solution for today's demanding enterprise environments in accordance with the present invention. A single configuration of multiple sub-pods, for example, may include a total of 32 processors, along with eight cache modules, 64 GB of main memory, four cross-bars and eight direct I/O bridges to support a total of 96 PCI slots.

FIG. 2illustrates an exemplary block diagram illustrating bus components within Processors202and the associated bus controller required to negotiate bus access by Processors202to I/O210, Memory208, and Cache206. Processors202each contain Front Side Bus (FSB)212. Node Controller204provides the processor system Bus Interface214and cache controller chip for up to four Processors202operating on common system bus216. NC204resides on the sub-pod module and is the central agent on the processor system bus to allow interactions between Processors202, Cache206, Memory208, and I/O210.

NC204facilitates access to cache206providing quick access to commonly used cache lines that are requested on system bus216. The data portion of Cache206resides in Static RAM (SRAM) that is external to Node Controller204and a corresponding on-chip tag RAM keeps track of state and control information for the resident cache lines. In operation, copies of frequently accessed state and control information, called cache blocks or cache lines, are maintained in the SRAM portion of Cache206. Each cache block or line is marked with a block address, referred to as a tag, so that Cache206knows to which part of the SRAM memory space the cache line belongs. The collection of cache tags for each memory block contained within the SRAM is contained within the on-chip tag RAM. For example, if cache line Bjcontaining data entries Djis assigned to a portion of SRAM called M1, then Bjis in the on-chip tag RAM and Djis contained within the SRAM of Cache206. Cache206is a non-inclusive cache, meaning that not all cache lines resident in the processor's cache are necessarily resident within Cache206.

In operation, Node Controller204decodes Front Side Bus212transactions on system bus216into two main types: 1.) coherent memory requests; and 2.) non-coherent requests. Coherent memory requests are controlled under the MESI protocol throughout the system and Cache206. Memory within a multiprocessor system in which every memory read and every memory write is instantly known by each processor within the system is known as coherent memory. Coherent memory requests, therefore, must communicate the memory accessed by one processor to the other processors on the bus through the use of a bus snooping function, so that stale data is not used. Coherent memory requests on System Bus216are monitored by the bus snooping function and communicated to all Processors202on System Bus216. The non-coherent requests, on the other hand, correspond to requests such as memory-mapped I/O, interrupts, and other special transactions which do not use Cache206.

Communication between Node Controller204, I/O210, Memory208and Cache206is conducted via interface218, which is implemented using a crossbar similar to the crossbar discussed in relation toFIG. 1. The crossbar is a multi-input, multi-output, non-blocking electronic switch, where access from Node Controller204and external components is unimpeded, thus removing any potential bottlenecks. The number of Processors202operating in conjunction with Node Controller204is advantageously limited in order to avoid excessive bus contention on System Bus216, especially in consideration of the bus snooping function as discussed above.

Data transfer on System Bus216may be implemented on varying width buses to include 32, 64 and 128 bit buses and beyond. The clocking rate on bus216is usually in the range of several hundred MegaHertz (MHz) and data may be transferred on both the rising and falling edges for double-pumped operation of the system bus clock to achieve an effective System Bus216bandwidth of several GigaHertz (GHz). In addition, varying phases of the system bus clock may be used to implement even higher effective bus clock rates, such as providing two rising edges and two falling edges within a clock period for a quad-pumped operation of the system bus clock. Processors202are responsible for obeying any bus specification that may exist for System Bus216between Front Side Bus212and Bus Interface214.

Bus Interface214interfaces Node Controller204to Front Side Bus212for each of Processors202. Bus Interface214provides at least the following functions: 1.) a request queue that allows Node Controller204or Processors202to generate bus requests; 2.) an in-order queue to receive bus requests from processors202; 3.) a snoop interface to provide address and function information necessary to snoop Node Controller204tag RAM and then to provide the tag status to the snoop interface; 4.) response cycle generation to complete bus operations; 5.) generation of deferred phase operations; and 6.) a data transfer interface to provide the control and necessary data queues to transfer data bus reads, writes, interrupts and special transactions.

FIG. 3illustrates an exemplary block diagram of Node Controller300in accordance with the principles of the present invention and is interconnected as follows. Bus Interface Controller302connects to System Bus338, which is the system bus for the processors attached to the particular sub-pod of interest. Bus Interface Controller302interconnects through a data bus to Memory Port Interfaces320and330as well as to Data Cache Interface308. Transaction Processor318is comprised of Tag RAM316, Transaction Pipeline314and Local/Remote Trackers312. Tag RAM316, Transaction Pipeline314and Local/Remote Trackers312are each interconnected through a control bus and Transaction Pipeline314is interconnected to Bus Interface Controller302through a control bus. Transaction Pipeline314also provides control through a control bus to Address Map Registers324, Trace History326, Memory Port Interfaces330and320. A data bus interconnects Bus Interface Controller302and Non-Coherent Registers310and Data Cache Interface308. A data bus also interconnects Non-Coherent Registers310and Data Cache Interface308to Memory Port Interfaces320and330. Data Cache Interface308is interconnected to cache348that may be separately located, e.g. off-chip, from Data Cache Interface308. Maintenance Requestor322and I/O Port Interface328are interconnected by both a data bus and a control bus. A control bus interconnects Address Map Registers324to I/O Port Interface328. Data and control bus interfaces exist between I/O Port Interface328and Memory Port Interfaces320and330. Scalability Port Memory Controllers332,334, and336interconnect through a data bus to Memory Port Interface320, I/O Port Interface328, and Memory Port Interface330, respectively. Data buses342and346interconnect Scalability Port Memory Controllers336and332, respectively, to the respective Memory Storage Unit associated with the particular sub-pod assembly. It should be noted that dual data buses342and346are provided to Node Controller204to allow for fault tolerant functionality, parallel processing, etc. Scalability Port Memory Controllers344transfer data between I/O Port Interface328and PCI devices118as depicted inFIG. 1and I/O devices210as depicted inFIG. 2.

In operation, Node Controller300provides all the necessary functions required to facilitate processor bus operations on Bus Interface338. In particular, Node Controller300facilitates at least seven primary functions: 1.) Out-Going Queue for outgoing requests to be sent out to Bus Interface Controller302; 2.) In-Order Queue for incoming requests from Bus Interface Controller302; 3.) Response Control for all bus requests; 4.) Datapath for data transfer and control between Memory Storage Units; 5.) I/O interface module to facilitate access to PCI devices; 6.) History Stack for Bus Interface Controller302history capture; and 7.) Error Checking to collect and check all errors. The other major interfaces accommodated by Node Controller300include the Bus Interface Controller302to Transaction Pipeline314interface which handles control signals and address/function signals, data transfers between Bus Interface Controller302and Data Cache Interface308, data transfers between Bus Interface Controller302and Memory Storage Unit0(not shown) on interface342, data transfers between Bus Interface Controller302and Memory Storage Unit1on interface346and non-coherent data transfers between Bus Interface Controller302and Non-Coherent Registers310.

The Out-Going Queue function receives requests to be sent to Bus Interface Controller302from either Transaction Pipeline314, Memory Port Interface330, or Memory Port Interface320. The requests are individually strobed into a priority selection block which acknowledges and grants execution of the request according to a prioritized selection algorithm, or held for later processing within the Out-Going Request Queue. Each of the requesting entities places information concerning the request type, which may be represented by a 3–5 bit digital code identifying one of a number of possible request types. Likewise, an In-Order Queue is utilized to store requests received from the processor on Bus Interface Controller302pertaining to, for example, snoop requests or write transactions sent from the processor.

The request signals comprise, for example, an active low address field used to identify the recipient of the request as well as a parity field to maintain an even number of active low signals on the address bus. Likewise, the request field is maintained with even parity by an associated request parity bit. The lower three bits of the address field are mapped into byte enable signals, which allows for a programmable number of bytes to be transferred in a given transaction. The programmable number of bytes for transfer in a single clock transition is, for example, 0 to 8 bytes.

Response signals are generated in response to the requests received and provide status for the requests that have been received. Each response signal comprises a response status field, whose parity is held even by a response parity field. Additionally, a Target Ready bit is maintained within the response signal to allow the receiving party to signal its readiness for write data or writeback data, if a data write is appropriate for the particular request. For transactions with an implicit writeback, the Target Ready bit is asserted twice, first for the write data transfer and second for the implicit writeback data transfer.

Data response signals control the transfers of data on Bus Interface338. The agent responsible for transferring data on the data bus is responsible for indicating that data on the bus is valid and that the data should be latched. The data bus agent, for example, should assert a ready bit at both the rising edge and falling edge of the bus clock for double-pumped operation. Additionally, the ready bit may be deasserted by the transmitting entity in order to insert wait states into the data phase. Bus Interface338may represent, for example, a 32, 64, or 128 bit width and may be enabled for individual bytes within Bus Interface338. For example, if Bus Interface338is 64 bits wide, then the bus is capable of transferring 8 bytes of data at a time, where each byte equals 8 bits. A 3-bit byte enable field, for example, could then be used to provide information as to which bytes of data are valid on the 64-bit bus. Additionally, the data transferred on Bus Interface338may be Error Correction Coded regardless of which bytes are enabled.

FIG. 4illustrates an exemplary functional block diagram400of Bus Interface Controller302as illustrated inFIG. 3. Processor422may represent one of many processors adapted to contemporaneously interface with other modules/interfaces424of the system, such as to the memory interface, cache interface, pipeline, etc. Generally speaking, there exist five phases of operation of Bus Interface Controller302: 1.) Arbitration; 2.) Request; 3.) Snoop; 4.) Response; and 5.) Data. Arbitration phase operation of Bus Interface Controller302allows for one of Processors422to obtain control of Bus Interface338, or alternatively to allow other interfaces424to obtain control of Bus Interface338, during one or more bus clock cycles. Arbitration phase is entered when one of Processors422asserts a bus request signal or another interface424asserts the bus request signal. A number of agents may simultaneously arbitrate for the request bus, where Processors422represent symmetric agents and the other interfaces424represent priority agents. Owning the bus is a necessary pre-condition for initiating a transaction. The symmetric agents arbitrate for the bus based on a round-robin rotating priority scheme. Priority agent bus requests override symmetric agent bus requests, where the priority agent bus request is always the next bus owner. The response to the bus request signal is assertion of a bus priority signal to the requesting device having priority, thereby relinquishing control of the bus to either the symmetric agents or the priority agent. Bus blocking control may be asserted by any of the bus agents to block further transactions from being issued to the request bus, in such instances, for example, when system resources, such as address and data buffers, are about to become temporarily busy or filled and cannot accommodate another transaction.

The request phase of Bus Interface Controller302is entered when either Processors422or interface424modules have successfully arbitrated for bus control. With reference to bothFIGS. 3 and 4, request signals may be provided by Transaction Pipeline314, Memory Port Interface330, and Memory Port interface320via interfaces424, and bus request signals may be provided by Processor422in order to generate snoop requests. Assertion of an address strobe signal defines the beginning of the request transaction. An active low address is provided along with the address strobe signal as part of the request. The low three bits are mapped into byte enable signals to accommodate, for example, 0 through 8 byte transfers per clock cycle. Even parity is used to insure that an even number of active low signals exist throughout the entire request signal.

Outgoing Bus Request Queue402receives bus requests from one or more modules/interfaces424via interface426and provides the requests via Interface428to the addressed Processor422of the request. Likewise, In-Order Queue404receives bus requests from Processor422via interface432and provides the bus requests to the addressed recipient via bus430. Each of Outgoing Bus Request Queue and In-Order Queue is limited, for example, to a depth of 8 and are responsible for queuing up requests from interfaces424and Processor422, respectively. Handshake signals are used between Outgoing Bus Request Queue402and modules/interfaces424and also between In-Order Queue404and Processor422in order to throttle the number of requests received by each of Queues402and404. Additional signaling is provided by Outgoing Bus Request Queue402when the queue has been filled to a predetermined depth. If, for example, the predetermined depth is 5 and the overall queue depth is 8, then 3 extra slots are provided in Outgoing Bus Request Queue402to allow for potential requests that may be waiting in Transaction Pipeline ofFIG. 3. Each of Processors422monitors the In-Order Queue404and will stop sending requests when the queue is full.

Snoop phase operation is controlled through the combined operation of In-Order Queue404and Snoop Control406and is required to maintain cache coherency. With regard toFIGS. 2 and 3, Memory Port Interfaces330and320provide write and read access to, for example, Memory208. Memory reads are cached into Cache348by Data Cache Interface308, whereby subsequent access to the same memory space results in a memory read from Cache348instead of a memory read from Memory208, resulting in a shorter memory access time. Memory208, however, represents shared memory space to each Processor422. Data read from Memory208and subsequently cached during one clock cycle from a first Processor422may be invalidated by a subsequent write to the same address in Memory208by a second Processor422.

Snoop Control406is, therefore, used to provide snoop control of Cache348to Processors422, while In-Order Queue404receives snoop requests from Processors422. In operation, snoop signals from Snoop Control406allow Processors422to determine whether: 1.) an unmodified, requested cache line exists within Cache348, resulting in a cache hit; 2.) a modified, requested cache line exists within Cache348, resulting in a cache hit to a modified cache line; or 3.) no cache line exists within Cache348, resulting in a cache miss. The snoop signals from Snoop Control406are used to maintain cache coherency at the system level and, therefore, provide an indication that the on-chip cache line within the snooping agent, e.g., Processor422, is valid or invalid, whether the Cache348line is in a modified, or dirty, state or whether the transaction should be extended until such time that a valid snooping state may be determined.

The response phase of Bus Interface Controller302is controlled by Response Control Queue410and Response Control408and are responsive to requests received by In-Order Queue404. A responding agent within the modules/interfaces424is responsible for processing requests at the top of In-Order Queue404, where the responding agent is the agent being addressed by the request, e.g., Memory Port Interface330during a memory read of Memory208ofFIG. 2or alternately a memory read of Cache348, if cached memory is present. Each response contains a response identifier, which is used to provide a response code to be placed on Bus Interface338during the response phase of Bus Interface Controller302. The response code identifies, for example, a result of a bus snoop initiated by one of Processors422. The results of the bus snoop may indicate, for example, that normal data was found, that no data was found, that the request is to be deferred, or that the request is to be retried. It should be noted that if the response code indicates that either a retry or deferral is necessary and that Snoop Control406indicates that Cache348is in a modified state, then the retry or defer response code will be implicitly changed to an automatic writeback from Memory208ofFIG. 2, where Cache348will provide itself as a target to maintain data coherency between Cache348and Memory208.

The data phase of Bus Interface Controller302operates to transfer data between Memory Port Interface320and related Memory Port Interface0Write Data Queue412and Memory Port Interface0Read Data Queue416and between Memory Port Interface330and related Memory Port Interface1Write Data Queue414and Memory Port Interface1Read Data Queue418. Cache data may also be transferred from the Processor422to cache via the Cache Write Data Queue415, and to the Processor as shown on path419. Non-coherent Data Out Queue420operates to transfer data contained from local registers within interfaces424to Processors422. A byte enable field may be used to enable multiple data bytes on the data bus per transfer cycle.

Data may be transferred in a data up direction from Processors202ofFIG. 2to Memory208, or transferred from Memory208to Processors202in a data down direction. Data may be transferred in blocks, known as cache lines or cache blocks, using intermediary, non-blocking buffers. The buffers are said to be non-blocking because the cache lines may be stored anywhere within the buffers and the cache lines may be extracted from the buffers no matter what their position within the buffer. Such an arrangement is non-blocking because cache lines stored within the non-blocking buffer are not blocked by other cache lines stored within the buffer, as would be the case, for example, in a First-In, First-Out (FIFO) buffer arrangement. Such a non-blocking arrangement is an important feature of the present invention because cache lines are not transferred until they become valid and the rate of cache line validity varies from cache line to cache line. Accordingly, use of a blocking buffer would unnecessarily contribute to the delayed transmission of valid cache lines because cache lines having higher priority may not be in a valid state, thus blocking the transmission of lower priority cache lines that are in a valid state.

FIG. 5illustrates a block diagram of Data Controller500according to the present invention. Data Source502may represent a source of a cache line, whether it be from Processors202or Memory208ofFIG. 2and Data Destination514may represent the destination of the cache line, whether it be to Memory208or Processors202, respectively. Memory Controller504provides Address In control to determine which storage location of Buffers506–512is to be used to temporarily store cache lines from Data Source502. Separate Address Out control is used to determine from which storage location of Buffers506–512data is to be retrieved and subsequently supplied to Data Destination514. Buffer Tracker516maintains the operational state of each storage location in each of Buffers506–512. The capacity of Buffers506–512may be set, for example, to a 16 or 32 cache line depth, wherein a cache line may be inserted or retrieved from any of the 16 or 32 storage locations within Buffers506–512regardless of the state of storage locations existing in any of the other locations within Buffers506–512. It should be noted that any number of storage locations may be allocated to Buffers506–512as required and the exemplary 16–32 cache line depth is set forth merely for illustration purposes only.

The state, or band, of each cache line contained within Buffers506–512is maintained by Buffer Tracker516, where the band may assume any one of three assignments: active, valid, or deallocate. The initial assignment to a cache line, or equivalently to its corresponding storage location, is given when the cache line is to be allocated, or in other words, given a storage location within one of Buffers506–512. Once a storage location within one of Buffers506–512has been allocated for a cache line, it is assigned to the active band by Buffer Tracker516meaning that the particular storage location may no longer be used, but that the data at that particular storage location is not yet valid. Once a cache line has been placed into the storage location, that particular storage location is assigned to the valid band by Buffer Tracker516, meaning that the storage location has been allocated within one of Buffers506–512and that the storage location contains a valid cache line. Once the cache line is retrieved from the storage location, Buffer Tracker516deallocates the storage location and returns it to a pool from which the next required storage location is allocated.

It should be noted that Buffer Tracker516maintains the assignments of each storage location within Buffers506–512individually, such that three separate assignments may be maintained for each storage location at any given time, where storage location allocations are appropriated based on the individual assignments in accordance with a particular selection algorithm. If a storage location, for example, is in a deallocated stage, it is added to an allocation pool (not shown) within Buffer Tracker516. The allocation pool is maintained by Buffer Tracker516to facilitate the selection of the next available storage location to be used for the next cache line storage. The storage locations are unavailable to the allocation pool if their respective assignment bands indicate either an allocated or a valid state. The individual assignment tracking mechanism of Buffer Tracker516, therefore, allows cache lines to be allocated and deallocated in random order such that a non-blocking queue operation may be realized.

FIG. 6illustrates an exemplary block diagram of Data Up Controller600according to the present invention. Data Up Controller600resides within Bus Interface Controller302ofFIG. 3and controls data transfer from Processors202ofFIG. 2to Memory208ofFIG. 2during the data phase of Bus Interface Controller302. Data Register602is coupled to the data bus portion of Bus Interface338ofFIG. 3and latches data off of Bus Interface338when data meant for Memory208ofFIG. 2is valid and available. Buffer612and Buffer614receive the data from Data Register602as directed by Memory Controllers606and610. Buffer Trackers604and608maintain control of the apportionment of cache lines within Buffer612and Buffer614during the snoop phase of Bus Interface Controller302ofFIG. 3in preparation for the data transfer to take place during the data phase of Bus Interface Controller302ofFIG. 3. Buffer Trackers604and608work in combination with Transaction Pipeline314and Local/Remote Trackers312to allocate the buffer storage within Buffer612and Buffer614to accommodate the data transfer. The data storage, for example, may be allocated by Bus Interface Controller302ofFIG. 3, where pointers to the allocated memory blocks are forwarded to Transaction Pipeline314ofFIG. 3and then on to Memory Port Interfaces330and320ofFIG. 3. Once Memory Port Interface330and320are ready to receive streamed data from Buffer612or Buffer614, respectively, Memory Port Interface330and320present the pointer received from Transaction Pipeline314ofFIG. 3to Memory Controller606and610, respectively, as data pointer618or630. A buffer pointer is then transferred from Buffer Tracker604and608and is used to calculate Read/Write Address620and Read/Write Address632, within Buffer612or614, respectively, as the starting address of the cache line to be transferred to Memory Port Interface330and320ofFIG. 3.

Once stored, the cache lines may be retrieved in any order from Buffer612by Memory Port Interface330ofFIG. 3, or alternatively, the cache lines may be retrieved in any order from Buffer614by Memory Port Interface320ofFIG. 3. Further, only a portion of the cache line stored within Buffer612or Buffer614may be retrieved if, for example, a data hold is generated, which would ordinarily cause unnecessary delay during the data transfer. In this instance, for example, a data stream from Buffer612to Memory Port Interface330that is delayed may be temporarily postponed, while a data stream from Buffer614to Memory Port Interface320is allowed to complete. Once the data stream from Buffer614to Memory Port Interface320is completed, the temporarily postponed data stream from Buffer612to Memory Port Interface330may then be completed.

Interfaces624and626provides Buffer Tracker604and Buffer Tracker608, respectively, the control conduit necessary to maintain the deallocate, allocate, and valid assignments as necessary for each cache line contained within Buffer612and Buffer614. In the snoop phase, for example, Transaction Pipeline314ofFIG. 3may reserve a storage location within Buffer612or Buffer614using the allocate band assignment. Once allocated, the storage location is removed from the available storage location pool (not shown) maintained within Buffer Tracker604and608.

During the data phase of Bus Interface Controller302ofFIG. 3, a cache line is ready for transfer from one of Processors202ofFIG. 2, to Memory208ofFIG. 2. The cache line is first transferred into the storage location within Buffer612or Buffer614that was allocated during the snoop phase. Once the cache line is transferred to Buffer612or Buffer614, the assignment band for the storage location is changed from the allocate state to the valid state by Buffer Tracker604or Buffer Tracker608, respectively. The cache line is then ready for immediate extraction from Buffer612or Buffer614regardless of its position, thus making Buffer612and Buffer614behave as a non-blocking buffer. Once the cache line has been extracted from Buffer612or614, the storage location used to store the cache line is assigned to the deallocate state and returned to the allocation pool (not shown) within Buffer Tracker604or608for subsequent reallocation.

Buffer Tracker604and608maintain a Buffer Full signal, which is used as a throttling mechanism to prevent future cache line write access to Buffer612or614when the allocation pool (not shown) indicates that no further storage locations are in a deallocate state. Once Buffer Full is activated by Buffer Tracker604, for example, Buffer Tracker608, in combination with Buffer614, exclusively accommodates further data up transactions until such time that Buffer Tracker604deasserts its Buffer Full signal. It can be said, therefore, that Data Up Controller600provides a redundant data transfer system, such that when one data up path, including Memory Controller606, Buffer Tracker604, and Buffer612, becomes busy, the second data up path, including Memory Controller610, Buffer Tracker608, and Buffer614may be used.

It should be noted that a separate Data Down Controller (not shown) exists to handle, for example, cache line transfers from Memory208ofFIG. 2to Processors202ofFIG. 2. The details of the Data Down Controller are not illustrated, however, because the Data Down Controller substantially performs the same function as the Data Up Controller in similar fashion. That is to say, that Data Down Controller resides within Bus Interface Controller302ofFIG. 3and controls data transfer from Memory208ofFIG. 2to Processors202ofFIG. 2during the data phase of Bus Interface Controller302. A data register is coupled to the data bus portion of Bus Interface338ofFIG. 3and latches data onto Bus Interface338when data meant for Processors202ofFIG. 2is valid and available, where non-blocking buffers provide the data to the data register. Buffer trackers maintain control of the apportionment of cache lines within the non-blocking buffers during the snoop phase of Bus Interface Controller302ofFIG. 3in preparation for the data transfer to take place during the data phase of Bus Interface Controller302ofFIG. 3. The buffer trackers work in combination with Transaction Pipeline314and Local/Remote Trackers312to allocate the buffer storage within the non-blocking buffers to accommodate the data transfer.

FIG. 7illustrates a block diagram of Buffer Tracker700according to the present invention. Allocate Control702receives signal Allocate Request and provides signal Buffer Active to Allocation Pool712, Error Check708, Depth Counter710and externally. Validate Control704receives signal Set Buffer Valid and provides signal Buffer Valid. Deallocate Control706receives signal Deallocate Request and provides signal Deallocate to Error Check708, Depth Counter710, and Allocation Pool712. Depth Counter710receives signals Buffer Active and Deallocate and provides signal Buffer Full.

In operation, Buffer Tracker700maintains and controls band assignments to each individual storage location within its corresponding buffer. Buffer Tracker700, for example, may be used to maintain and control band assignments for all storage locations contained within Buffer612or Buffer614of Data Up Controller600. In addition, Buffer Tracker700may be used for the Data Down Controller (not shown) in substantially the same way as discussed for the Data Up Controller.

An allocate request may be received, for example, from Bus Interface Controller302during a data up transfer, or conversely, from Memory Port Interface320or330during a data down transfer. The Allocate Request signal is used to prepare a storage location within Buffer612or614in anticipation of its use during either data up or data down transfer, thus reducing the storage location to write only access. In response to the Allocate Request signal, Depth Counter710calculates the number of allocated storage locations remaining by subtracting the number of storage locations already allocated from the total number of storage allocations available in Buffer612or614. If no more storage locations are available for allocation within Buffer612, for example, Depth Counter710asserts signal Buffer Full to invoke the redundant operation of Data Up Controller600ofFIG. 6by allowing Buffer614, for example, to accommodate the allocation request.

Allocation Pool712also receives signal Buffer Active in order to generate signal Next Buffer ID, which is a signal sent to Memory Controller606or610ofFIG. 6for use in selecting the next storage location to be used, where Allocation Pool712maintains a list of the available storage locations for allocation. That is to say, that Allocation Pool712tracks those storage locations within, for example, Buffer612that have not been allocated to any other cache line storage request. Since Buffer612and614are non-blocking buffers, each storage location within each Buffer612or614is individually tracked by Allocation Pool712, such that the number of storage locations available for allocation is the number of storage locations whose assignment band is deallocate. Allocation Pool712generates signal Next Buffer ID to identify the address of the storage location to be used to store the next cache line within Buffer612or614. Memory Controller606and610receives Next Buffer ID in order to generate the necessary Read/Write Address signal to retrieve/store the next cache line.

Once the cache line is available from Bus Interface338ofFIG. 3in data up mode, or available from Memory Data Bus342or346ofFIG. 3in data down mode, it is transferred into the storage location previously allocated and identified by signal Next Buffer ID. Once the transfer is complete, Set Buffer Valid signal is transferred by either Bus Interface Controller302ofFIG. 3in data up mode or by Memory Port Interface320or330ofFIG. 3in data down mode, and received by Validate Control704, which is subsequently forwarded onto Memory Controller606and610ofFIG. 6to set the assignment band of the storage location within Buffer612or614ofFIG. 6to valid. The valid assignment band generates read only access rights for the storage location, thereby eliminating the possibility of overwriting the data just written, prior to reading it. Once the cache line is accessed from Buffer612or614ofFIG. 6during the data phase of Bus Interface Controller302ofFIG. 3, signal Deallocate Request is transferred by either Bus Interface Controller302ofFIG. 3in data up mode or by Memory Port Interface320or330ofFIG. 3in data down mode, and received by Deallocate Control706, which in turn provides signal Deallocate to Error Check708, Depth Counter710, and Allocation Pool712. Allocation Pool712, then adds the storage location identified by signal Deallocate back into the available storage location pool for future allocation. Similarly, Depth Counter710increments the total number of storage locations available within Buffer612or614, thus increasing the available capacity of Buffer612or614.

Error Check708receives signals Buffer Active and Deallocate. Once a Buffer Active signal is received for a particular storage location, Error Check708determines whether the last signal received for that particular storage location was a Buffer Active signal or a Deallocate signal. If a Buffer Active signal was received, error signal Buffer Error is generated denoting that two consecutive Buffer Active signals have been received for the same storage location. Conversely, once a Deallocate signal is received for a particular storage location, Error Check708determines whether the last signal received for that particular storage location was a Deallocate signal or a Buffer Active signal. If a Deallocate signal was received, error signal Buffer Error is generated denoting that two consecutive Deallocate signals have been received for the same storage location. Error Check708, in other words, verifies that each storage location of Buffers612and614ofFIG. 6are toggled back and forth between active and deallocate assignment bands to insure that a particular storage location is not allocated or deallocated more than once before it transitions to the opposite assignment band.

FIG. 8illustrates a flow chart presenting exemplary assignment band processing according to the present invention. An allocation request is received at step802during, for example, a snoop phase of Bus Interface Controller302ofFIG. 3. The allocation request for a particular storage location is compared in step804to any other allocation requests that may have been received for that same storage location. If the two allocation requests exist sequentially, with no deallocation request in between for that storage location, an error signal is issued in step806and then the operation completes. The storage location to be used during the next cache line storage is calculated in step808, based on an algorithm which sorts through an allocation pool containing both allocated and deallocated storage location pointers.

A depth calculation is then performed in step810, which calculates the remaining number of storage locations within a particular non-blocking buffer based on the total number of storage locations contained within the buffer as compared to the number of allocated storage locations contained within the buffer. If the buffer is calculated to be full as in step812, or if the buffer is near full such that the next transaction will overflow, then redundant processing is attempted in step814with the remaining paired buffer. For example, if Buffer612ofFIG. 6is full or near full, then redundant processing may divert to Buffer614ofFIG. 6to handle the cache line allocation request. Once the cache line has been retrieved from the non-blocking buffer, the storage location used for the cache line may be deallocated in step816and added back to the allocation pool to provide a future resource. The deallocation request for a particular storage location is compared in step818to any other deallocation requests that may have been received for that same storage location. If the two deallocation requests exist sequentially, with no allocation request in between for that storage location, an error signal is issued in step806and the operation completes.

In conclusion, a method and apparatus has been presented that allows for non-blocking data transfer operation to increase efficiency of operation. Since data required by one processor or memory unit is not blocked by data required by another processor or memory unit, data stalls caused by blocking buffers is substantially eliminated.