Abstract:
The invention provides a method of transmitting data via a bus system coupling a plurality of bus participants with an arbitration procedure for the plurality of bus participants. The invention further enables bus arbitration during a first transmission since that the bus can be granted for a second transmission following the first transmission without wasting bus cycles. This is accomplished by determining the number of cycles remaining for the first transmission according to memory boundary and transmission packet boundary conditions.

Description:
FIELD OF THE INVENTION  
       [0001]     The present invention relates to field of arbitration methods for interruptionless utilization of a data transmission system, such as an arbitrary data bus, a bus bridge or a network controller.  
       BACKGROUND OF THE INVENTION  
       [0002]     Various computer components request access to a common communication platform in order to share the usage of various peripheral devices or memory. The common communication platform is typically provided by a bus system for data transfer operations. When several components (hereinafter referred to as participants) request grant to the bus system simultaneously, an arbitration procedure determines which of the requesting participants receives grant to the bus.  
         [0003]     A simple arbitration procedure can be realised with a round robin arbitration algorithm, in which the participants receive grant to the bus in a fixed cyclic order. This algorithm has the disadvantage, that access to the bus is granted irrespectively from the fact whether a participant requested for access or not. Thus, the idle time of the bus can increase to a large number of bus cycles.  
         [0004]     Another common arbitration procedure is based on priority scheduling. Here, each data transfer operation is assigned with a distinct priority label. Depending on this priority label, which may be static or dynamic, the corresponding participant receives grant to the bus. A danger of priority scheduling is starvation, in which operations with low priority are not given the opportunity to receive a grant.  
         [0005]     Various improvements and modifications under round robin and the priority algorithm have been made and implemented, in order to optimize the arbitration procedure. Nevertheless, most arbitration procedures have the disadvantage that the arbitration of a participant needs a certain amount of bus cycles.  
         [0006]     In U.S. Pat. No. 5,255,373 a method to eliminate the arbitration delay when the system bus is idle is suggested. Furthermore, it describes a system which detects when a system bus is idle and which keeps the system bus in an arbitration state. Therefore, each participant detects autonomously whether the bus is idle or not.  
         [0007]     When the bus is idle, it is kept in an arbitration state, to allow a subsequent arbitration to take place immediately. A disadvantage of this invention is, that all data transfer operations have to be equal in size. Therefore, various data transfer operations that are different in size cannot be processed in an effective way with this invention.  
         [0008]     U.S. Pat. No. 6,094,692 describes a method to minimize the transmit underflow and packet latency of data packets transmitted between a host computer and a network. Here, the byte length of each received packet is determined and the time needed to fill a FIFO buffer is measured. Furthermore, the output transmission rate of the FIFO buffer is determined. Depending on the byte length of each received packet, the output transmission rate and the fill time for the FIFO buffer, a transmit start point is set. In particular when the output transmission rate is larger than the input transmission rate of the FIFO buffer, the transmit start point is delayed in order to prevent transmit underflow. The method comprises the calculation of the removal and the fill time of the FIFO buffer, but it does not include any kind of arbitration procedure.  
         [0009]     The present invention aims to provide an improved arbitration method and arbitration apparatus for the interruptionless utilization of a bus transmitting data between a plurality of participants.  
       SUMMARY OF THE INVENTION  
       [0010]     The present invention provides an improved method for an arbitration procedure for continuous utilization of a bus transmitting data between a plurality of participants. A distinct arbitration time which is needed by an arbitration unit to arbitrate one of the pluralities of participants is given by an amount of bus cycles. When a participant receives grant from an arbitration unit it starts to transmit a command over the bus. Preferably, this command either belongs to a transfer operation or to a Direct Memory Access (DMA) operation. The command is analyzed by a timing module, which determines the size of the data transfer or the DMA operation, hence the number of cycles needed for processing the entire operation.  
         [0011]     The timing module initiates a timer with a start value being equal to the number of cycles needed to process the entire operation. A predefined threshold value of the timer equals the number of cycles needed by the arbitration procedure. When the timer has reached this predefined threshold value, the timing module activates the arbitration unit which starts immediately with the arbitration of a subsequent operation. Consequently, the transmission of the subsequent operation immediately starts after the last transfer cycle of the first data transfer operation has been processed. In this way the generation of a gap in the operation stream is effectively prevented and the bus can be used in its most effective hence interruptionless way. In accordance with a preferred embodiment of the invention the arbitration of a subsequent data transfer operation takes place even before the actual operation has been processed.  
         [0012]     In accordance with a further preferred embodiment of the invention, the plurality of bus participants can receive or transmit data transfer or DMA operations. The operations further consist of a command and a data packet of variable size. The command contains information about the size of the data packet and the address of the data packet.  
         [0013]     In accordance with a further preferred embodiment of the invention, the bus is connected via a bridge module to a second bus which is connected to a memory module. The first and the second bus are characterised by the same data transfer rate. Thus, the clock frequency and the width of the first bus may differ from the clock frequency and the width of the second bus, as long as the product of clock frequency and width of the bus is equal for each bus.  
         [0014]     In accordance with a further preferred embodiment of the invention a safety gap is generated between successive operations in the operation stream to eliminate potential driving conflicts. Therefore, a safety margin is subtracted from the threshold value of the timer. Since the threshold value is now decreased, the arbitration of a successive operation is delayed by a number of cycles that correspond to the safety margin.  
         [0015]     In accordance with a further preferred embodiment of the invention the timer value which is equal to the number of cycles needed to process an operation is determined by the timing module by taking into account the size of the DMA operation, the width of the system bus to which the DMA operation has been transmitted by a participant and a start address inside a memory module which is connected to a second bus, which in turn is connected to the first bus via a bridge module. The memory module is divided in memory blocks each containing a certain number of bytes. The timer value is calculated by the timing module depending on whether the start address matches the first byte of a memory block inside the memory module and whether the size of the data packet can be divided by the width of the bus without rest.  
         [0016]     The present invention is particularly advantageous for eliminating gaps in a data or operation stream that are due to an arbitration procedure. The method of the present invention is not restricted to a distinct arbitration procedure. Moreover, it can be applied to numerous bus systems and arbitration procedures, such as priority decoded and/or round robin procedures. Furthermore, the invention is not restricted to computer systems, but can universally be applied to bus bridges, network controllers and any other device requiring an arbitration procedure in the framework of modern communication systems. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0017]     In the following, preferred embodiments of the invention will be described in greater detail by making reference to the drawings in which:  
         [0018]      FIG. 1  shows a block diagram of a bus system and an arbitration system;  
         [0019]      FIG. 2  is illustrative of a flow chart for performing a method of the invention;  
         [0020]      FIG. 3  shows a block diagram of a preferred embodiment of the invention; and  
         [0021]      FIG. 4  is illustrative of a flow chart for calculating the timer value. 
     
    
     DETAILED DESCRIPTION  
       [0022]      FIG. 1  schematically shows an integrated circuit system  100 , that contains a timing module  102  and an arbitration unit  104 . Furthermore, it shows three mutually independent participants  108 ,  110  and  112 , that are each connected to a bus  120  via a data connection  126 . Each participant  108 ,  110  and  112  is independently connected to the arbitration unit via a request line  122  and a grant line  124 . The timing module  102  is connected with the bus  120  with a connection  127  and with a line  128  to the arbitration unit  104 .  
         [0023]     The participant  108  wishing to transmit a data transfer operation to the bus  120  sends a request to the arbitration unit  104  via the request line  122 . The request line  122  is two bits wide which allows for three different priorities of the data transfer operation. When access to the bus is granted by the arbitration unit  104  a grant is passed to the participant  108  via the grant line  124 , which is one bit wide. The participant  108  then starts to transmit the data transfer operation to the system bus  120  via the data connection  126 , which is four byte wide. As soon as the transmission of the data transfer operation has been started, the command of the operation is detected by the timing module  102  via the connection  127 .  
         [0024]     From the information given by the command of the data transfer operation the timing module  102  calculates the number of bus cycles needed in order to process the transmission of the operation from the participant  108  to the system bus  120 . It initiates a timer with a start value being equal to the number of cycles needed for the entire transmission. The timer value is decremented step wise with each bus cycle. When the timer has reached a predefined threshold value it activates the arbitration unit via the line  128  and the arbitration of another participant begins. A threshold value is chosen in such a way that it equals the number of bus cycles needed by an arbitration procedure including the initialization for sending of the next data transfer operation. In this way, a successive operation can be arbitrated while the actual operation is still being processed and an interruptionless operation stream can be generated on the bus.  
         [0025]     In a further embodiment, the threshold value is modified in order to generate a gap in the operation stream on the bus between successive operations. The size of the safety gap is chosen arbitrarily and it may consist of one or more bus cycles.  
         [0026]      FIG. 2  illustrates a corresponding flow chart. In step  200  a grant is issued to a participant. In step  202  the timing module is waiting for a valid data transfer operation to be transmitted onto the bus. When the command of the operation has been transmitted to the bus it is analyzed in step  204 . Furthermore depending on the start address and the size of the data packet a start value of the timer is determined. In step  206  the clock of the bus is monitored and with each bus cycle the timer is decremented.  
         [0027]     Step  208  checks whether the timer has reached the predefined threshold value. If the threshold value has not yet been reached, the procedure returns to step  206 . If in step  208  the threshold value has been reached then in step  210  the next arbitration is started. Then step  212  checks whether another request is pending. If there is no other request pending, the method continues with step  210 . If in step  212  another request is pending then the method continues with step  200  and issues a new grant to a new participant.  
         [0028]      FIG. 3  schematically shows a further embodiment of the invention illustrated in  FIG. 1 . It shows an integrated circuit system  300  consisting of a timing module  302  an arbitration unit  304  and a bridge module  306 . It further illustrates three mutually independent participants  308 ,  310  and  312 . The figure further depicts a first bus  320 , a second bus  332  and a host system  334  that contains a memory module  336 . Every single participant  308 ,  310  and  312  is connected to the first bus  320  via a data connection  326 . Furthermore, every participant  308 ,  310  and  312  is independently connected to the arbitration unit  304  via a request line  322  and a grant line  324 . The timing module  302  is connected to the first bus  320  via a connection  327  and it is connected to the arbitration unit  304  via a line  328 . The bridge module  306  is connected to the first bus  320  via a data connection  329  and it is also connected to the second bus  332  via a data connection  330 . The memory module  336  located inside a host system  334  is connected to the second bus  332  via a data connection  331 .  
         [0029]     The timing module  302 , the arbitration unit, the single participants  308 ,  310  and  312 , as well as the first bus  320  have the same function as the corresponding modules depicted in  FIG. 1 . In the present embodiment of the invention, the bridge module  306  connects the first bus  320  to the second bus  332 . Here, the two busses can differ in clock frequency and bus width, as long as their data transfer rates are equal. In a preferred embodiment of the invention the width of the bus  320  is four byte and the width of the second bus  332  is one byte. As a consequence, the clock frequency of the second bus  332  is four times larger than the clock frequency of the first bus  320 . The corresponding data connections  329  and  330 ,  331  have a width of four byte and one byte, respectively. The memory module  336  contains memory blocks with a size of a multiple of four byte.  
         [0030]     If one of the participants  308 ,  310  or  312  wants to transmit a DMA operation via the bus  320 , it sends a request to the arbitration unit  304  via the request line  322 . Transmission of the operation begins when the participant  308  receives grant from the arbitration unit  304  via the grant line  324 , the timing module  302  detects the beginning of a transmission via the connection  327  and determines the number of cycles needed for processing the DMA operation. The timing module  302  activates the arbitration unit  304  when the decremented timer equals the predefined threshold value.  
         [0031]     The arbitration unit  304  arbitrates for the next participant  310  or  312  requesting access to the bus  320 . The operation stream on the bus  320  is directed to the bridge module  306  via the data connection  329 . The bridge module converts the four byte wide DMA operation to a one byte wide DMA operation and passes this one byte wide DMA operation to the bus  332  via the data connection  330 . The bus  332 , which is characterised by a four times larger clock frequency than bus  320  passes the DMA operation to the memory module  336  via the data connection  331 .  
         [0032]      FIG. 4  shows a corresponding flow chart for the calculation of the timer value T for a given size S and a given address A of the data packet. The width of the bus W is given in number of bytes and the timer value T is given in number of bus cycles. The address A of a data packet is compared to the starting address of the memory blocks in steps  402 .  
         [0033]     If A matches the starting address of a memory block in step  402  then in step  408  the size of a data packet S is divided by the width of a system bus W.  
         [0034]     If the division can be performed without rest, then the timer value is given by the ratio of S and W. If the division in step  408  cannot be performed without rest the timer value T is given by the ratio of S divided by W and incremented by one.  
         [0035]     When in step  402  the address A of a data packet does not match the start address of a memory block then in step  404  a reduced size of the data packet SR is determined. The reduced size SR is obtained by subtracting the difference of the start address of the next memory block and the start address of the data packet A from the size S of the data packet.  
         [0036]     Then in step  406  the reduced size SR is divided by the width of the bus W. If the division in step  406  can be performed without rest then in step  414  the timer value is given by the ratio of SR and W and incremented by one.  
         [0037]     If the division in step  406  cannot be performed without rest, the tiner value is given in step  416  by the ratio of SR and W and incremented by two.  
         [0038]     List of Reference Numbers: 
     100  integrated circuit system      102  timing module      104  arbitration unit      108  participant      110  participant      112  participant      120  bus      122  request line      124  grant line      126  data connection      127  connection      128  line      300  integrated circuit system      302  timing module      304  arbitration unit      306  bridge module      308  participant      310  participant      312  participant      320  bus      322  request line      324  grant line      326  data connection      327  connection      328  line      329  data connection      330  data connection      331  data connection      332  bus      334  host system      336  memory module    
 
         [0070]     While the preferred embodiment of the invention has been illustrated and described herein, it is to be understood that the invention is not limited to the precise construction herein disclosed, and the right is “reserved” to all changes and modifications coming within the scope of the invention as defined in the appended claims.