Data queuing apparatus

• US 5,649,119 A
• Filed: 12/28/1994
• Issued: 07/15/1997
• Est. Priority Date: 12/28/1993
• Status: Expired due to Term

• Current Assignee: Renesas Electronics Corporation
• Original Assignee: Mitsubishi Denki Kabushiki Kaisha (Mitsubishi Electric Corporation)
• Inventors: Ishiwaki, Masahiko, Yamanaka, Hideaki, Notani, Hiromi, Kondoh, Harufusa
• Primary Examiner(s): Harrell, Robert B.
• Application Number:
  US08/365,637
• Time in Patent Office: 930 Days
• Field of Search: 364/DIG. 1 MS File, 364/DIG. 2 MS File, 370/41, 370/43, 370/58.1, 370/58.2, 370/60, 370/61, 395/200.01, 395/200.17, 395/250, 395/849, 395/850
• US Class Current: 710/29
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 49/108 using shared central buffer
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04L 49/405 Physical details, e.g. power supply, mechanical construction or backplane of ATM switches

Abstract

A plurality of shift memories shifting data are connected in series, destination indicating bits indicative of data destination are stored in destination indicating bit memories corresponding to the shift memories respectively, and a searching circuit is provided adjacent to each of the destination indicating bit memories, which searching circuit searches data by searching the destination indicating bits.

Claims

1. A data queuing apparatus, comprising

a plurality of stages of cascade-connected data queuing portions, each including a plurality of data shift means each shifting while holding data, a plurality of destination indicating bit storing means provided corresponding to said respective data shift means for storing destination indicating bits indicative of destinations of said data, and searching means for searching said plurality of destination indicating bits and for outputting the searched data;

wherein

each data queuing portion receives data and destination indicating bit from a succeeding stage, and when a preceding stage is empty, outputs the data and the destination indicating bit to said empty preceding stage.

2. The data queuing apparatus according to claim 1, further comprising

a bus for commonly connecting data reading outputs of said respective data queuing portions.

3. The data queuing apparatus according to claim 2, wherein

of said plurality (N) of stages of data queuing portions, kth (k<

N) and subsequent stages are used as first in first out memories which do not perform searching or reading.

4. The data queuing apparatus according to claim 3, wherein

said kth and subsequent stages of data queuing portions do not provide read output to data queuing portion of the stage prior to kth stage.

5. The data queuing apparatus according to claim 3, wherein

a search input signal indicating the validity is applied to said kth and subsequent stages of data queuing portions.

6. The data queuing apparatus according to claim 1, further comprising

AND means responsive to application of an instruction for disposing data with priority, for providing an AND of the instruction and said priority bit and for clearing data of the corresponding data queuing portion.

7. The data queuing apparatus according to claim 6, further comprising

a counter provided for each data queuing portion, incremented every time data is input to the corresponding data queuing portion and decremented every time data is output from the corresponding data queuing portion, wherein data with low priority is disposed when count value of the counter reaches a prescribed value.

8. The data queuing apparatus according to claim 7, wherein

said counter is provided for each bit of said data shift means.

9. The data queuing apparatus according to claim 1, further comprising

priority storing means for storing priority, wherein

said searching means includes means for searching in accordance with an AND output of the priority stored in said priority storing means and said destination indicating bit.

10. The data queuing apparatus according to claim 9, further comprising

a counter provided corresponding to each stage of the data queuing portions, incremented every time a priority data is input to the corresponding data queuing portion and decremented every time priority data is output from the corresponding data queuing portion;

wherein

said searching means searches when count value of said counter reaches a prescribed value.

11. The data queuing apparatus according to claim 9, wherein

said counter includes a plurality of counters provided corresponding to a plurality of different priorities, for each stage of said data queuing portions,

said apparatus further comprising

AND means for selecting an output having higher priority from outputs of said respective counters, providing an AND of the selected output and said destination indicating bit and for applying the result to the searching means.

12. The data queuing apparatus according to claim 9, further comprising

means for clearing said priority storing means at a prescribed ratio for reading data with lower priority at a prescribed ratio.

13. The data queuing apparatus according to claim 1, wherein

of said respective data queuing portions, a data queuing portion having valid data detected in a preceding stage and valid data with higher priority detected in the next stage transmits an invalidating signal to the preceding stage, and

when priority of the data held by said data queuing portion of the preceding stage is not high, said data queuing portion of the preceding stage stops transmission of a detecting signal.

14. The data queuing apparatus according to claim 13, wherein

said data queuing portion of the preceding stage stops transmission of said detecting signal when the priority of the data held therein is lower than the priority according to the invalidating signal applied from the data queuing portion of the succeeding stage.

15. The data queuing apparatus according to claim 1, further comprising

a data input portion for inputting data at a head portion of each of said stages of data queuing portions.

16. The data queuing apparatus according to claim 15, further comprising

means for activating only that searching means which corresponds to the data queuing portion of a used stage, out of said stages of said data queuing portions.

17. The data queuing apparatus according to claim 1, further comprising

gate means provided between each of said stages of data queuing portions for stopping shifting operation of a data queuing portion which is not storing valid data.

18. A data queuing apparatus, comprising:

a plurality of data shift means each for shifting while holding data;

a plurality of destination indicating bit storing means provided corresponding to said respective data shift means; and

searching means arranged adjacent to said destination bit indicating means for searching said destination indicating bit and outputting searched data.

19. The data queuing apparatus according to claim 18, wherein

said searching means is arranged along a central portion of said plurality of destination indicating bit storing means.

20. The data queuing apparatus according to claim 19, further comprising

a bus for performing time division of indicating bits from said plurality of destination indicating bit storing means and for guiding the bits to said searching means.

21. The data queuing apparatus according to claim 20, wherein

said searching means searches, in pipelined manner, each said destination indicating bit.

22. The data queuing apparatus according to claim 18, wherein

said destination indicating bit storing means includes latch means for latching said destination indicating bit, and

control means for letting, when said latch means does not hold any destination indicating bit, said latch means hold a destination indicating bit from a succeeding stage, and when latch means of a preceding stage does not hold any destination indicating bit, letting the destination indicating bit of said latch means be shifted to the preceding stage.

23. A data queuing apparatus including a plurality of data shift means each shifting while holding data, a plurality of destination indicating bit storing means provided corresponding to said respective data shift means for storing destination indicating bits indicative of destinations of respective data, and searching means for searching said destination indicating bits and outputting searched data, wherein

said destination indicating bits are divided into a plurality of groups each including a plurality of destination indicating bits as a unit,

said data queuing apparatus comprising

a preceding stage data queuing circuit provided in a preceding stage for outputting data and destination indicating bits for each of said plurality of groups, and

a plurality of succeeding stage data queuing circuits provided for each of said plurality of groups and receiving the data and the destination indicating bits output from said preceding stage data queuing circuit.

24. The data queuing apparatus according to claim 23, wherein

said destination indicating bits divided into a plurality of groups include a destination indicating bit and a bit for identifying a group to which the destination indicating bit belongs,

data shift means of said preceding stage data queuing circuit and plurality of data queuing circuits of the succeeding stage each include an area for holding said data and said destination indicating bit,

said destination indicating bit storing means includes control means responsive to said identifying bit for letting said data shift means hold said data and said destination indicating bit,

data output from the data shift means of the preceding stage is applied to the data shift means of each of said data queuing circuits of the succeeding stage, and input to the area of said destination indicating bit being grounded, and

control means of said succeeding stage includes means responsive to the destination indicating bit applied from the data shift means of the preceding stage for letting the data shift means of said succeeding stage hold the data from the preceding stage.

25. The data queuing apparatus according to claim 23, wherein

said destination indicating bits divided into a plurality of groups include a destination indicating bit and a bit for identifying a group to which destination indicating bit belongs,

said data shift means and said destination indicating bit storing means are provided corresponding to each of said plurality of groups, said apparatus further comprising

address filter means for applying destination indicating bit corresponding to each said group and said data to the corresponding data shift means and the destination indicating bit storing means.