Abstract:
The present invention describes a flexible routing scheme between masters and slaves in complex digital systems. The routing scheme is optimized for maximum versatility and configurability using switched resources in the form of configurable crossbar switches.

Description:
TECHNICAL FIELD OF THE INVENTION 
     The technical field of this invention is communication between master and slave devices. 
     BACKGROUND OF THE INVENTION 
     In conventional hardware systems, either system-on-chip (SOC) or discrete, there can be multiple master modules such as CPUs, DMAs, host processors or port interface elements that communicate with multiple slave peripherals. These peripherals include media and data ports and memory controllers. A single master can access many slave peripherals and a single peripheral needs to be accessed by many masters. The access route from a master to a slave may include multiple routing stages. These routing stages include address decoders, arbitration units, and frequency and width translation bridges. 
     This scheme works well for the applications that are well understood. However the application requirements are not always completely known when hardware system is being designed. The same hardware system can be used in multiple applications. In these situations fixed routes pose a limitation in achieving optimal performance. 
       FIG. 1  illustrates a prior art fixed routing scheme. Masters  101  through  105  control slaves  131 ,  132  and  139  via two crossbar switching networks SCR 1   115  and SCR 2   120 . Master requests M 1  through M 3  are decoded in respective decoders  106 ,  107  and  108 . These requests pass to arbitration unit  110 . Arbitration unit  110  selects one of the requests coming from the multiple decoders  106 ,  107  or  108  based on priority and directs it to the intermediate point  109 . Intermediate point  109  connects to a subsequent decoder  111 . Master requests M 4  and M 5  are decoded in respective decoders  112  and  113 . Arbitration units  121 ,  122  and  129  select one request signals from decoders  111 ,  112  and  113  for control of respective slaves  131 ,  132  and  139 . 
     A request M 1  to M 3  from any one of masters  101  to  103  has to pass through two stages of arbitration at arbitration unit  110  and one of arbitration units  121 ,  122  and  129  before it can reach any of the destination slaves  131 ,  132  and  139 . In contrast requests M 4  or M 5  from masters  104  or  105  see only one stage of arbitration at one of arbitration units  121 , or  122  and  129 . Clearly, the system illustrated in  FIG. 1  is optimized for access for master requests M 4  and M 5 . If the application requirement changes such that requests from any of the masters M 1  through M 3  need to be processed at a higher priority, or if these masters experience higher traffic than expected, then the system of  FIG. 1  cannot adjust to this new requirement. 
     If the precise requirements of traffic from a master and concurrency of traffic with other masters are not known before design implementation, the safe approach would be add extra hardware to allow as many parallel accesses as possible. In above example, if the request profiles of masters M 1  through M 4  were not known, one design solution adds a separate port for all the masters M 1  through M 4  on SCR 2 . This would mean that a similar path to all the slaves S 1  through S 9  would have to be included for all the masters M 1  through M 4  in SCR 2 . This results in a significantly larger hardware design and can cause speed limitations or extra pipelining latency. Ignoring M 5  since it represents any number of additional masters in the system, crossbar switching network SCR 2   120  becomes a 4:10 crossbar instead of 2:10, doubling its size. 
     SUMMARY OF THE INVENTION 
     Complex digital systems include both master and slave devices with versatile communication requirements. A single master can access many slave peripherals and a single slave peripheral needs to be accessed by many masters. The access route from a master to a slave can include multiple routing stages. The present invention is a flexible routing scheme optimized for maximum versatility and configurability while achieving acceptable chip size and complexity. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       These and other aspects of this invention are illustrated in the drawings, in which: 
         FIG. 1  illustrates the block diagram of a conventional network for communication between masters and slaves (Prior Art); 
         FIG. 2  illustrates the block diagram of the network connecting masters and slaves using a switched resource crossbar and flexible switching allowing for more versatile communication between masters and slaves; and 
         FIG. 3  illustrates the system of  FIG. 2 , configured to give priority to master M 1 . 
     
    
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS 
       FIG. 2  illustrates the flexible routing scheme of the present invention. This routing scheme provides maximum versatility and configurability while achieving acceptable chip size and complexity. Crossbar switching network  215  routes master requests M 1  through M 4  to either of two intermediate points,  216  or  217 . The protocol determining the selection priorities for master requests reaching  216  or  217  are configurable. 
     In the example of the invention illustrated in  FIG. 2 , any of the masters  201  through  204  have access to either of two ports  216  and  217 . Assuming the two ports  216  and  217  are identical, a subtle optimization lies in the possibility that one path for a given master could be deleted and while still permitting any possible grouping dividing all the masters between the two ports. 
     The bus infrastructure that lies beyond intermediate points  216  and  217  including crossbar switching network SCR 2   220  is identical to crossbar switching network  120  illustrated in  FIG. 1 . As a result, a request coming from masters M 1  through M 4  can pass through the bus infrastructure via two possible routes. This gives flexibility to better tune the system as necessary to a particular application. For example, the system can be configured such that master M 1  requests go to intermediate point  216  and masters M 2  through M 4  all send the requests to intermediate point  217 . 
     In  FIG. 2  crossbar switching network  215  is a complete crossbar capable of directing any master request to either intermediate point  216  or intermediate point  217 . Any combination of routing connecting one of the masters to only one of the two intermediate points  216  or  217  is acceptable. For example, one could connect M 1  to only P 1 , and M 2 , M 3 , M 4  to P 1  and P 11 . This still allows complete flexibility in terms of master grouping, while saving some hardware. 
     In the example of  FIG. 2  two ports connect crossbar switching network SCR 1   215  to crossbar switching network SCR 2   220 . This concept is scaleable to serve the total needed system bandwidth and latency requirements of all the masters on crossbar switching network SCR 1   215 . The concept is valid with 2 to n ports. The trade off between flexibility and size must be made and more flexibility moves the design closer to a full crossbar switching network. Optimum benefit results from using the minimal number of ports that gives the most added flexibility. 
       FIG. 3  illustrates the system of  FIG. 2 , configured to give priority to master M 1   301 . The request coming from master M 1   301  does not have to contend with any other master requests M 2   302 , M 3   303  or M 4   304  before it reaches crossbar switching network SCR 2   320 . Any other grouping of M 1  through M 4  is possible as required. Configuration is accomplished by: (1) software reprogramming all connections from decoders  307 ,  308 , and  309  to the arbitration unit  310 ; and (2) reprogramming the connection from decoder  306  to arbitration unit  310  exclusively. 
     In  FIG. 2  a request from master M 1   201  can reach slave S 1  either as M 1  to P 1  to P 2  to S 1  or as M 1  to P 11  to P 2  to S 1 . Most significant address bits are decoded to forward the request towards appropriate slave point or intermediate point. 
     Without any change in hardware, a request coming from a master is always forwarded to one of the possible points in the bus structure. Thus, for example in  FIG. 1 , crossbar switching network SCR 2   120  has nine endpoints P 2  through P 10 . The total address space is divided among the slaves S 1  through S 9 . Depending upon the request address, a request coming from any of the masters to crossbar switching network SCR 2   120  via intermediate point P 1   109 , master M 4   104  or master M 5   105  will go to one of the slaves  131  through  139 . 
     In  FIG. 2 , it is desirable to send a request from the masters served by crossbar switching network SCR 1   215  to either of the intermediate points P 1   216  or P 11   217 . This is achieved by extending the address space by one bit. The decoders then decode one extra bit of address. A most significant bit is added to the address bus of the request coming from each master. Configuration registers drive this bit. It  FIG. 2  including four masters, four configuration register bits are needed. If the MSB is 1 the decoders in crossbar switching network SCR 1  forward a request to intermediate point P 11   217 . If the MSB is 0, the request is forwarded to point intermediate point P 1   216 . 
     A second important modification that is sometimes necessary is master identification (ID). In some protocols the slave devices send read data and status as well as write status information back to the master. This information is routed to the master by the bus infrastructure using master ID information that traveled along with the request to the slave, sent back from the slave along with the information status and data information. As an example, suppose master M 1   201  did a read request to slave S 1 . The configuration bit for master M 1   201  is set such that all master M 1   201  requests are directed to intermediate point P 11 . Read data information reaching point P 2  from slave S 1 , will have to be sent to intermediate point P 11 , so that the return data travels a similar path as the request. This is necessary for consistency in the switch hardware states, apart from managing traffic. However, without any modification to the master ID, crossbar switching network SCR 2   220  would not know the difference between intermediate points P 1  and P 11 . Thus crossbar switching network SCR 2   220  would not know to which node it should send back the data. 
     For this reason, the master IDs of the masters M 1  to M 4  are also modified with the configuration bit. For example, if master ID for master M 1  was 001, then, the modified master ID looks like X001 where X can be either 0 or 1 based on the value in the configuration register for M 1 . With this addition the flexible routing scheme is complete. 
       FIG. 2  illustrates a flexible 4:2 router. This scheme can be easily generalized and expanded for greater flexibility. An m:n flexible router may be accommodated by appending additional bits to the most significant address bits. 
     Consider a system having m masters that need flexible connectivity to support access to n nodes with n&lt;m. This implies use of an m:n crossbar switching network to provide flexible connection that allows any partitioning of m masters into n disjoint subsets. Let M 1  to Mm be the masters and OutO 1  to Outn be the outputs of the flexible crossbar switching network. The number of extra address bits required to be decoded by the flexible crossbar switching network is
 
ceil(log 2 (N))
 
where: the ceil function is the nearest integer bigger than the log value; and log 2 (N) is the base 2 logarithm of N.
 
     The m:n scheme can be optimized for area without loss of generality such that: 
     1. One of the outputs, such as Out 01 , is connected to all the masters M 1  to Mm; 
     2. A second output, such as Out 02 , is connected to all but one of the masters, such as M 2  to Mm; 
     3. A third output, such as Out 03  is connected to all but two masters, such as M 3  to Mm; 
     4. Repeating for all outputs. 
     Consider the specific example of a 6:3 flexible connectivity scheme. Because there are three outputs, we have ceil(log 2 (3))=2 required extra bits. Note: ceil(log 2 (3))=ceil(1.585)=2. Thus two extra address bits are required to drive the master requests to the desired flexible output. In this manner one can create a flexible crossbar switching network with 6 inputs and 3 outputs, allowing any possible partitions of the 6 inputs to be connected to one of the outputs. This invention conserves chip area using this optimization without losing any flexibility. 
     Further analysis of the m:n case reveals that any possible partitioning of masters is allowable. Ideally, the m:n path optimization described above should be achieved in such a way that it should result in minimum change in software as well as minimum change in hardware protocol. The m:n case of this invention achieves both. First, there is minimal software change needed because it required programming just a few configuration bits. Secondly, there is no change to the hardware protocol. All the existing systems can benefit from this technique without any change. Thirdly, compared to the prior art that adds two extra decode points in crossbar switching network SCR 2  significantly increasing hardware cost, this invention is cheaper in terms of chip area. Fourthly, this invention is less likely to degrade system speed.