Abstract:
A priority encoder and a processing device having the priority encoder. The priority encoder includes a port selector for generating a plurality of prioritized read requests based on a plurality of write requests from a plurality of processing devices and a predetermined priority assigned to each of the plurality of processing devices, one of the plurality of processing devices being selected based on the plurality of prioritized read requests; and a port latch for holding the values of the prioritized read requests to enable one of a plurality of communication ports unless the prioritized read requests are changed, each communication port for communicating with one of the processing devices to read data from the processing device.

Description:
COPYRIGHT STATEMENT 
       [0001]    A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever. 
       FIELD OF THE INVENTION 
       [0002]    The present invention relates to priority encoders, and is particularly concerned with assigning priority to a plurality of processing devices. 
       BACKGROUND OF THE INVENTION 
       [0003]    Referring to  FIG. 1 , a system is shown which includes an array of processing devices that are connected to each other by using a plurality of interconnecting buses. The computer array  100  has a plurality of processing devices  105   aa ,  105   ab ,  105   ac  through  105   an  in first row,  105   ba ,  105   bb ,  105   bc  through  105   bn  in second row,  105   ca ,  105   cb ,  105   cc  through  105   cn  in third row, and  105   ma ,  105   mb ,  105   mc  through  105   nm  in the row m. Each of the processing devices ( 105   aa  through  105   nm ) are connected to each other by a plurality of bidirectional data bus  110  which are explained in further detail in  FIG. 2 . One skilled in the art will recognize that there may be additional components in the computer array  100  that are excluded from the view of  FIG. 1  for the sake of clarity. For example, as shown in  FIG. 1  the processing device  105   bb  is connected to the processing devices  105   ab ,  105   ba ,  105   bc  and  105   cb  orthogonally and to processing devices  105   aa ,  105   ac ,  105   ca  and  105   cc  diagonally. Conflicts relating to multiple write and read requests are unavoidable, when more than one of the processing device communicates and sends a write request to the processing device  105   bb  at the same time. As such, requests to the processing device  105   bb  tend to accumulate, simultaneous write requests exemplify the problem, since it is clear that choices must be made between the several write requests. The processing device  105   bb  should choose between one of those requests to prevent a system crash. Thus, pending read and write requests should generally be prioritized so that the most urgent request is answered first. 
         [0004]      FIG. 2  is a more detailed view of a portion of  FIG. 1 , showing only some of the processing devices in the computer array  100  and in particular, processing devices  105   a  through  105   i . The view of  FIG. 2  also reveals that the data buses  110  each have a read line, a write line and a plurality of data lines (a thick line is used to demonstrate the plurality of data lines). In this embodiment, the read and write requests are communicated via a read line and a write line included in the communication bus interconnecting two processing devices. The processing core  105   e  is connected with multiple processing devices  105   a ,  105   b ,  105   c ,  105   d ,  105   f ,  105   g ,  105   h  and  105   i , either orthogonally or diagonally using the write lines ( 205   ae ,  205   be ,  205   ce ,  205   de ,  205   ef ,  205   eg ,  205   eh , and  205   ei ), read lines ( 210   ae ,  210   be ,  210   ce ,  210   de ,  210   ef ,  210   eg ,  210   eh , and  210   ei ) and plurality of data lines ( 215   ae ,  215   be ,  215   ce ,  215   de ,  215   ef ,  215   eg ,  215   eh , and  215   ei ) respectively. If more than one of the processing devices  105   a ,  105   b ,  105   c ,  105   d ,  105   f ,  105   g ,  105   h  and  105   i  sends a write request to the processing device  105   e , reading data from more than one direction port can, in some circumstances, result in corruption of data, in particular when data from more than one interconnecting bus is simultaneously gated to the same register. The undesirable possibility of more than one direction port getting connected to a register can be prevented by including a priority circuit in the computers of the array, which can avoid simultaneous presentation of write requests to the direction ports of a computer. 
         [0005]    In practice, some methods exist to prioritize read and write requests, but they typically involve a time-consuming process of binary encoding and decoding the binary output to evaluate the priority. For example, in the scenario shown in  FIG. 2  where the processing device can receive more than one write request from the eight processing devices, an 8:3 priority bit encoder is used in the prior art systems. Depending on how many active requests are received, the processing device will generate a three bit binary output, and the three bit binary output needs to be decoded to enable only one of the neighbouring processing devices. This two-step process may add a significant delay to the response time of the processing device, especially when speed is considered as a critical performance parameter. 
         [0006]    Thus, taking the limitations of the prior art systems into consideration, there remains a need for a priority encoder that can handle multiple write requests from the neighbouring processing devices. 
       SUMMARY OF THE INVENTION 
       [0007]    An object of the present invention is to provide a priority encoder to obviate or mitigate at least some of the aforementioned disadvantages. 
         [0008]    In accordance with an aspect of the present invention, there is provided a priority encoder which includes a port selector for generating a plurality of prioritized read requests based on a plurality of write requests from a plurality of processing devices, and a predetermined priority assigned to each of the plurality of processing devices. One of the plurality of processing devices is selected based on the plurality of prioritized read requests. The priority encoder includes a port latch for holding the values of the prioritized read requests to enable one of a plurality of communication ports, unless the prioritized read requests are changed, for each communication port communicating with one of the processing devices to read data from the processing device. 
         [0009]    In accordance with an aspect of the present invention, there is provided a processing device having the priority encoder having the port selector and the port latch. 
         [0010]    Some apparatus for automatically identifying the processing device with highest priority from a plurality of processing devices trying to communicate with the same processor core at the same time is described. 
         [0011]    In one embodiment, the apparatus includes a priority selector to monitor the active write requests from the neighbouring processing devices and determine the write request with highest priority. The apparatus also includes plurality of port latch circuits that are coupled to the priority selector and neighbouring devices through the communication ports. The plurality of port latch circuits are used to retain the values of the prioritized read requests at a given state unless one of the inputs changed. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0012]    The present invention will be further understood from the following detailed description with reference to the drawings in which: 
           [0013]      FIG. 1  illustrates in a block diagram, a known computer array with multiple processing cores; 
           [0014]      FIG. 2  illustrates in a block diagram, known processing devices interconnected to multiple processing devices using multiple data buses; 
           [0015]      FIG. 3  illustrates in a block diagram, a processing system in accordance with an embodiment of the present invention; 
           [0016]      FIG. 4  illustrates in a block diagram, the N-port priority encoder of  FIG. 3 ; 
           [0017]      FIG. 5  schematically illustrates an exemplary circuit diagram of the N port selector of  FIG. 4 ; 
           [0018]      FIG. 6  schematically illustrates an exemplary circuit diagram of the 4-port selector of  FIG. 4 ; and, 
           [0019]      FIG. 7  schematically illustrates an exemplary circuit diagram of one of the latches of the N port latch of  FIG. 4 . 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
       [0020]      FIG. 3  illustrates a processing device  300 , including a dual stack processor  305  coupled to N-port priority encoder  310  according to one embodiment of the proposed invention. The processing device  300  is, for example, used as an element of an array of multiple processing devices where the multiple processing devices are connected each other. The dual stack processor  305  is generally a self-contained computer, having its own RAM  315  and RAM  320 . Other basic components of the dual stack processor  305  include a control logic circuit  325 , a decode logic circuit  330 , an arithmetic logic unit  335 , a data stack  340 , a return stack  345 , an instruction register  350  and an inter-processor status register (IOCS)  355 . The dual stack processor  305  also includes ‘N’ communication ports; Direction Port-A  360 A, Direction Port-B  360 B through Direction Port-N  360 N via which the processor core  300  can communicate with neighbouring processing devices. 
         [0021]    Each of Direction port-A  360 A, Direction port-B  360 B, through Direction port-N  360 N is assigned to one of the processing devices that can send write requests to the processing device  300 , as explained in detail below. 
         [0022]    In one embodiment, the N-port priority encoder  310  monitors inter processor communication by reading the IOCS register  355  and determines one of the neighbouring processing devices to accept one write request from one of the neighbouring processing devices only, and activates the communication channel through one of the communication ports, Direction Port-A  360 A, Direction Port-B  360 B through Direction Port-N  360 N, to read data from one of neighbouring processing devices. The functionality of the N-port priority encoder  310  is explained in further detail hereinbelow with reference to  FIG. 4 . 
         [0023]    Referring to  FIG. 4 , the N-Port priority encoder  310  for N neighbouring processing devices are connected to one of the processing devices. The N-port priority encoder  310  includes an N-port selector  405  that is used to select one of the N multiple processing devices based on the predetermined priority and their write requests, and an N-port latch  410  having a series of N latches that are coupled to the N-port selector  405 . The N-port selector  405  reads the write request bits WR_A, WR_B through WR_N ( 415 A,  415 B through  415 N) respectively, from the IOCS register  355  and generates prioritized read requests Pri_A, Pri_B through Pri_N ( 420 A,  420 B through  420 N) respectively. For example, if the processing device  300  receives four pending write requests from four multiple processing devices, the N-port selector  405  (in this case N is equal to four) provides a read request to one of the multiple processing devices with the highest priority. The CMOS circuit of the N-Port selector  405  is discussed in further detail hereinbelow with reference to  FIG. 5 . The N-port latch  410  is an array of N latches, Latch-A, Latch-B through Latch-N ( 410 A,  410 B through  410 N) that receives prioritized read requests Pri_A, Pri_B through Pri_N ( 420 A,  420 B through  420 N) from the N-port selector  405 . The array of N latches, Latch-A, Latch-B through Latch-N ( 410 A,  410 B through  410 N) are used to retain the values of the prioritized read requests Pri_A, Pri_B through Pri_N ( 420 A,  420 B through  420 N) and provide outputs RD_A, RD_B through RD_N ( 425 A,  425 B through  425 N). The CMOS design of the N-port latch  410  is explained in further detail hereinbelow with reference to  FIG. 6 . 
         [0024]    Direction port-A  360 A, Direction port-B  360 B through Direction port-N  360 N of  FIG. 3  are connected to RD_A, RD_B through RD_N, respectively. RD_A, RD_B through RD_N determine the priority of Direction port-A  360 A, Direction port-B  360 B through Direction port-N  360 N and thus determine which neighboring processing device can send data. 
         [0025]      FIG. 5  illustrates an exemplary circuit diagram of the N-port selector  405 . As shown in  FIG. 5 , the CMOS circuit design of the N-port selector  405  utilizes a series of AND and OR gates to generate prioritized read requests Pri_A, Pri_B through Pri_N ( 420 A,  420 B through  420 N) based on the multiple write requests WR_A, WR_B through WR_N ( 415 A,  415 B through  415 N) received from neighbouring processing devices. A series of AND gates ( 515 A,  515 B through  515 N) receive inverted control bits ( 525 A,  525 B through  525 N) and write requests WR_A, WR_B through WR_N ( 415 A,  415 B through  415 N) and generate the prioritized read requests Pri_A, Pri_B through Pri_N ( 420 A,  420 B through  420 N). A series of inverters ( 510 A,  510 B through  510 N) are used to generate inverted values ( 525 A,  525 B through  525 N) of selection control bits Cntrl_A, Cntrl_B through Cntrl_N ( 505 A,  505 B through  505 N). The selection control bit Cntrl_A  505 A is always fixed at a logical value of ‘0’. A series of OR gates ( 520 A,  520 B and so on) are utilized to generate the control bits Cntrl_B through Cntrl_N ( 505 B through  505 N) from the inputs Cntrl_A, Cntrl_B through Cntrl_N−1 ( 505 A,  505 B and so on) and write requests WR_A, WR_B through WR_N−1 ( 415 A,  415 B and so on) respectively. Cntrl_N−1 (not shown) is a selection control bit and is one of inputs provided to OR gate (not shown) for outputting Cntrl_N. WR_N−1 (not shown) is a write request bit and is an input to the OR gate for outputting Cntrl_N. 
         [0026]    In  FIG. 5 , the N-port selector  405  includes N AND gates ( 515 A,  515 B through  515 N), N inverters ( 510 A,  510 B through  510 N), and N−1  0 R gates ( 520 A,  520 B and so on) where N is the number of communication ports ( 360 A,  360 B through  360 N of  FIG. 3 ). Each of the N AND gates outputs a corresponding prioritized read request (e.g., Pri_A, Pri_B . . . ) based on an output from a corresponding inverter and a write request (e.g., WR_A, WR_B . . . ). The (N−1) OR gates generate selection control bits (e.g., Cntrl_B . . . ) except Cntrl_A. 
         [0027]    Based on the predetermined priority, a communication port (e.g.,  360 B) with the highest priority is connected to AND gate  515 A and OR gate  520 A, a communication port (e.g.,  360 N) with the next highest priority is connected to AND gate  515 B and OR gate  520 B, and a communication port (e.g.,  360 A) with the lowest priority is connected to AND gate  515 N and OR gate for generating Cntrl_N. 
         [0028]    Referring to  FIG. 6 , there is schematically illustrated an exemplary circuit diagram of the 4-port selector  405 . To simplify the description for explanation purposes, N is given a value of four, hence the 4-Port selector  405 ′ can receive a maximum of four write requests WR_A, WR_B, WR_C and WR_D ( 415 A,  415 B,  415 C and  415 D) from the multiple processing devices (e.g,  105 A,  105 B,  105 C and  105 D). Also, assume that the processing device  105 A has the highest priority followed by the processing devices  105 B,  105 C and  105 D ( 105 A&gt; 105 B&gt; 105 C&gt; 105 D). The different possible scenarios based on the active write requests of the multiple processing devices are classified into four scenarios, Condition-1, Condition-2, Condition-3 and Condition-4, as shown in Table 1. 
         [0029]    A Condition-1 will occur when the write request WR_A  415 A is active (logic value of ‘1’) and the logic state of the rest of the write requests WR_B, WR_C and WR_D ( 415 B,  415 C and  415 D) can be active or inactive. Condition-2 is detected when the write request WR_A  415 A is inactive (logic value of ‘0’) and WR_B  415 B is active (logic value of ‘1’), and the logic state of the write requests WR_C and WR_D ( 415 C and  415 D) can be active or inactive. Condition-3 will occur when the write request WR_A and WR_B ( 415 A and  415 B) are inactive (logic value of ‘0’), WR_C  415 C is active (logic value of ‘1’), and the logic state of the write request WR_D  415 D can be active or inactive. Condition-4 is detected when the write request WR_A, WR_B and WR_C ( 415 A,  415 B and  415 C) are inactive (logic value of ‘0’) and write request WR_D is active. 
         [0000]    
       
         
               
             
               
               
               
             
               
               
               
               
               
             
               
               
               
               
               
               
             
           
               
                 TABLE 1 
               
             
             
               
                   
               
               
                 Assumption: 105A &gt; 105B &gt; 105C &gt; 105D 
               
             
          
           
               
                   
                 Write Requests 
                   
               
             
          
           
               
                   
                 WR_A 
                 WR_B 
                 WR_C 
                 WR_D 
               
               
                   
                   
               
             
          
           
               
                   
                 Condition-1 
                 Active 
                 Don&#39;t care 
                 Don&#39;t care 
                 Don&#39;t care 
               
               
                   
                 Condition-2 
                 Inactive 
                 Active 
                 Don&#39;t care 
                 Don&#39;t care 
               
               
                   
                 Condition-3 
                 Inactive 
                 Inactive 
                 Active 
                 Don&#39;t care 
               
               
                   
                 Condition-4 
                 Inactive 
                 Inactive 
                 Inactive 
                 Active 
               
               
                   
                   
               
             
          
         
       
     
         [0000]    
       
         
               
               
               
               
               
               
               
               
             
           
               
                 TABLE 2 
               
               
                   
               
               
                 Condition 
                 Pri_A 
                 Cntrl_B 
                 Pri_B 
                 Cntrl_C 
                 Pri_C 
                 Cntrl_D 
                 Pri_D 
               
               
                   
               
             
             
               
                 Condition-1 
                 1 
                 1 
                 0 
                 1 
                 0 
                 1 
                 0 
               
               
                 Condition-2 
                 0 
                 0 
                 1 
                 1 
                 0 
                 1 
                 0 
               
               
                 Condition-3 
                 0 
                 0 
                 0 
                 0 
                 1 
                 1 
                 0 
               
               
                 Condition-4 
                 0 
                 0 
                 0 
                 0 
                 0 
                 1 
                 1 
               
               
                   
               
             
          
         
       
     
         [0030]    Table 2 shows the values of prioritized read requests and control bits based upon the conditions shown in Table 1. During Condition-1 the inputs to the first AND gate  515 A are write request WR_A  415 A of logic value ‘1’ and the inverted value of control bit Cntrl_A  510 A of logic value ‘1’ (as mentioned earlier in  FIG. 4 , the value of control bit Cntrl_A  505 A is fixed at logic value of ‘0’), the value of the prioritized read request Pri_A  420 A is ‘1’. The inputs to the OR gate  520  A is the control bit Cntrl_A  505 A of logic value ‘0’ and write request WR_A  415 A, making the output control bit Cntrl_B  505 B of logic value ‘1’. Applying the same logic as above, the inputs to the second AND gate  515 B are write request WR_B  415 B and the inverted value of control bit Cntrl_B  510 B of logic value ‘0’, thus making the value of the prioritized read request Pri_B  420 B ‘0’. One of the inputs (Cntrl_B  505 B) to the successive OR gate  520 B is a ‘1’, regardless of the logic value of WR_B  415 B, the value of the control bit Cntrl_C  505 C is ‘1’. Similarly, the inputs to the third AND gate  515 C are write request WR_C  415 C and the inverted value of control bit Cntrl_C  510 C of logic value ‘0’, thus making the value of the prioritized read request Pri_C  420 C ‘0’. One of the inputs (Cntrl_C  505 C) to the successive OR gate  520 B is a ‘1’, so regardless of the logic value of WR_C  415 C the value of the control bit Cntrl_D  505 D is ‘1’. Finally, the inputs to the last AND gate  515 D are write request WR_D  415 D and the inverted value of control bit Cntrl_D  510 D of logic value ‘0’, thus making the value of the prioritized read request Pri_D  420 D ‘0’. For one skilled in the art, it will be obvious from the above discussion that if the write request WR_A  415 A from the processing device  105   a  with highest priority is active, the read request Pri_A  420 A to that processing device  105   a  is activated, regardless of the state of the write requests from the rest of the processing devices. Applying the same logic, the outputs for the other conditions such as condition-2, condition-3 and condition-4, the same can be derived by one skilled in the art. 
         [0031]    Referring to  FIG. 7 , there is illustrated embodiment of circuit diagram of the latch, Latch-A  410 A of the array of the latches in the N Port Latch  410 . The latch Latch-A  410 A is a simple SR latch with the NOR gates  620 A and  625 A, which are cross coupled with each other and receive inputs S 1    605 A and Pri_A  420 A, and input R 1    615 A, respectively. The input R 1    615 A is generated by ORing the prioritized read requests Pri_B through Pri_N ( 420 B through  420 N) using the OR gate  610 A. If both the values of S 1    605 A and R 1    615 A are zero, the outputs of the latch RD_A  425 A and NOT (RD_A)  630 A remain unchanged. If the input value of S 1    605 A is a ‘0’ and the input value of the R 1   615 A is a ‘1’, then the output value of RD_A  425 A becomes a ‘0’ and the output NOT (RD_A)  630 A will be a ‘1’. If the input value of S 1    605 A is a ‘1’ and the input value of the R 1   615 A is a ‘0’, then the output value of RD_A  425 A becomes a ‘1’ and the output NOT (RD_A)  630 A will be a ‘0’. For S 1    605 A to be a ‘1’, the prioritized read request Pri_A  420 A has to be a ‘1’ and for R 1    615 A to be a ‘1’, at least one of the prioritized read requests Pri_B through Pri_N ( 420 B through  420 N) has to be a ‘1’. For one skilled in the art, it is obvious that at any given time, only one of the prioritized read requests Pri_A through Pri_N ( 420 A through  420 N) can be at a logic value of ‘1’. Thus, using S 1    605 A and R 1    615 A as the inputs of the SR latch, where at most only one of them can be at a logic value of ‘1’, the unstable condition of the SR latch can be avoided. Similarly, inputs to Latch-B, S 2   605 B and R 2   615 B are Pri_B  420 B and the output generated by ORing prioritized read requests Pri_A  420 A and Pri_C through Pri_N ( 420 C through  420 N) the unstable condition of the SR latch can be avoided. 
         [0032]    The processing device  300  of  FIG. 3  can be used in the computer array of  FIGS. 1-2  in which each of the processing devices (e.g.,  105   aa  to  105   nm  of  FIG. 1 ,  105   a  to  105   i  of  FIG. 2 ) is replaced with the processing device  300 . One skilled in the art will appreciate that the array structure for the processing device  300  of  FIG. 3  is not limited to those of  FIGS. 1-2 . 
         [0033]    Numerous modifications, variations and adaptations may be made to the particular embodiments described above without departing from the scope patent disclosure, which is defined in the claims.