Abstract:
A method of ordering commands includes receiving a set of related commands that have a predetermined execution sequence, the commands being received in an arbitrary order that may be different from the execution sequence and releasing a later received command of the set for execution before an earlier received command from the set based on the execution sequence.

Description:
TECHNICAL FIELD 
     This invention relates to command ordering. 
     BACKGROUND 
     Computer processing systems often include several logic blocks that operate concurrently. Logic blocks may share a bus that is used to send commands to another logic block, such as a memory or memory controller. 
    
    
     DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a block diagram of computer hardware on which a command ordering process may be implemented. 
    
    
     DESCRIPTION 
     Referring to FIG. 1, a network processing system  10  operates as a data packet cross-bar that receives packets (through I/O buses  14   a - 14   n  from external devices, not shown), stores the packets temporarily, interprets header (address) information contained in each packet, and transmits each packet to a destination indicated by its header when an appropriate I/O bus  14   a - 14   n  is available. System  10  may include connections to thousands of I/O buses and may need to simultaneously store and track tens of thousands of data packets of various sizes before each packet is transmitted out of system  10 . The storage, and the input and output of data packets to and from I/O buses  14   a - 14   n , is controlled by several processors  12   a - 12   n.    
     System  10  includes a first memory  16  to store the received data packets in a set of data buffers  18   a - 18   n . Because the data buffers  18   a - 18   n  need not be located contiguously in first memory  16 , each data buffer is indexed by a buffer descriptor address (BDA) that indicates the location and size of the buffer. As each packet is received from one of the I/O buses and stored by one of the processors in one of the buffers of the first memory  16 , the processor identifies one of a set of I/O ports  20   a - 20   n  (each associated with one of the I/O buses) for transmitting the packet in the data buffer  18   a - 18   n  out of system  10 . Because the I/O port chosen for transmitting a packet stored in a buffer is often busy receiving or sending packets for other buffers, system  10  includes a second memory  24 . Second memory  24  stores a queue array, that is, a set of queue entries  24   a - 24   n  that contains BDAs for packets that are stored in buffers  18   a - 18   n  of first memory  16  and are waiting for a chosen I/O port  20   a - 20   n  to become available. Each queue entry  24   a - 24   n  corresponds to one of the I/O ports  20   a - 20   n . To reduce the time required to access the queue entries  24   a - 24   n  stored in second memory  24 , system  10  also includes a queue manager  30  that includes a queue array cache  26  for storing a sub-set of the most recently used queue entries. The contents of queue array entries  24   a - 24   n  in second memory  24  or queue array cache  26  may be changed by the execution of queue commands sent from a processor  12   a - 12   n  to the queue manager  30 . Queue commands include write-back commands (also called writes) that causes the contents of a queue entry from queue array cache  26  to be written out to second memory  24 , read commands that causes a queue entry to be read from second memory  24  and stored in queue array cache  26 , and enqueue and de-queue commands (“EDQ” commands) that cause the storing and retrieving, respectively, of a BDA in or from an entry in the queue array cache  26 . 
     Queue commands may be “related”, that is directed to the same queue entry in queue array cache  26  and/or memory  24 . Therefore, related queue commands must be executed in the proper order to maintain coherency between the entries in queue array cache  26  and second memory  24 . For example, a write back command of a first queue entry in queue array cache  26  must be executed before a read command is executed to the same queue entry in queue array cache  26 . Similarly, a read command of a queue entry from second memory  24  to queue array cache  26  must be executed before an EDQ command is executed that specifies the same queue entry in queue array cache  26 . However, queue commands sent from a processor  12   a - 12   n  may not arrive at queue manager  30  in the order in which they must be performed because processors  12   a - 12   n  send queue commands on a shared command bus  28  to queue manager  30 . Shared command bus  28  includes a command bus arbiter  29  that allows only a single processor  12   a - 12   n  at a time to send queue commands on bus  28 . The arbitration for shared bus  28  by processors  12   a - 12   n  may cause related queue commands from a processor  12   a - 12   n  to arrive at queue manager  30  out of the order in which they must be executed. 
     Queue manager  30  receives queue commands from processors  12   a - 12   n , sorts the queue commands into separate command FIFO&#39;s and then releases the sorted commands for execution in the proper execution sequence. In more detail, queue manager  30  receives queue commands from shared command bus  28  and stores the commands in a command inlet FIFO  31 . Queue manager  30  then sorts and stores the received queue commands from inlet FIFO  31  into separate command FIFOs: a Write FIFO  32  for storing Write commands, a Read FIFO  34  for storing Read commands and an EDQ FIFO  36  for storing Enqueue and Dequeue commands. As commands reach the front of each respective FIFO, queue manager  30  determines the release sequence of stored queue commands that may be related. 
     Write commands may always be performed before related Reads commands, therefore, queue manager  30  releases write commands for execution whenever a Write command reaches the front of the Write FIFO  32 . 
     To determine when a Read command may be released for execution from Read FIFO  34 , queue manager  30  includes a first set of counters  32   a  and  32   b , a RD_TAG FIFO  33  and a RD TAG COMPARE block  33   a . The first set of counters  32   a  and  32   b  includes a WR_IN counter  32   a  that is incremented every time a Write command is loaded into Write FIFO  32 , and a WR_OUT counter  32   b  that is incremented every time a Write command is removed from Write FIFO  32 . As each Read command is loaded into Read FIFO  34 , the value of WR_IN count  32   a  is tagged to that Read Command by storing the WR_IN count  32   a  in RD_TAG FIFO  33 . The RD_TAG FIFO  33  and RD Command FIFO  34  are controlled to advance the stored Tags  33  and Read Commands  34  together to the output of the respective FIFOs. Read commands are released when the RD_TAG COMPARE logic  33   a  determines that the RD_TAG that corresponds to the Read command at the front of READ FIFO  33  is less than or equal to the WR_OUT count  32   b . This determination ensures that a Read command is released only after an equal or greater number of Write commands have already been released and executed. Therefore, a Write command to a first queue entry is executed before a Read command that may relate to the same first queue entry, even if the Read command was received before the Write command by queue manager  30 . 
     To determine when an EDQ command may be released for execution, queue manager  30  includes a second set of counters  34   a  and  34   b , an EDQ TAG FIFO  35  and an EDQ TAG COMPARE logic block  35   a . The second set of counters  34   a  and  34   b  includes a RD_IN counter  34   a  that is incremented every time a Read command is loaded into Read FIFO  34 , and a RD_OUT counter  34   b  that is incremented every time a Read command is removed from Read FIFO  34 . As each EDQ command is loaded into EDQ Command FIFO  36 , the value of RD_IN counter  34   a  is tagged to that Queue Command by storing the value from RD_IN counter  34   a  in EDQ TAG FIFO  35 . The EDQ TAG FIFO  35  and Queue_Command FIFO  36  are controlled to advance the stored EDQ Tags and Queue Commands together to the output of the respective FIFOs  35  and  36 . An EDQ command is released for execution from the front of EDQ FIFO  36  only when EDQ_Tag compare logic  35   a  determines that the corresponding EDQ_TAG from EDQ TAG FIFO  35  is less than or equal to the value in RD_OUT counter  34   b . This determination ensures that an EDQ command is released only after an equal or greater number of Read commands have been released and executed. Therefore, a Read command that may relate to the same queue array entry is executed before an EDQ command, even where the EDQ command was received first by queue manager  30 . 
     The process of sorting related commands, hereafter referred to as “process  100 ”, is not limited to use with the hardware shown in FIG.  1 . Process  100  may find applicability in any computing or processing environment, and may be implemented in hardware, software, or a combination of the two. Process  100  may be implemented in computer programs that include executable instructions that are executed on programmable computers or other machines that each include a processor and a storage medium readable by the processor. 
     Other embodiments not described herein are also within the scope of the following claims.