Source: https://patents.google.com/patent/CN102449965B/en
Timestamp: 2020-06-03 01:20:24
Document Index: 533904919

Matched Legal Cases: ['art 707', 'art 707', 'art 707', 'art 707', 'art 707', 'art 707', 'art 707', 'art 1401', 'art 1401', 'art 1401', 'art 1601', 'art 1601', 'art 1601', 'art 1601', 'arts\n708', 'arts\n1402', 'arts\n2801']

CN102449965B - Relay device - Google Patents
Relay device Download PDF
CN102449965B
CN102449965B CN201180002247.1A CN201180002247A CN102449965B CN 102449965 B CN102449965 B CN 102449965B CN 201180002247 A CN201180002247 A CN 201180002247A CN 102449965 B CN102449965 B CN 102449965B
CN201180002247.1A
CN102449965A (en
2010-03-05 Priority to JP2010-049108 priority Critical
2010-03-05 Priority to JP2010049108 priority
2011-01-07 Application filed by 松下电器产业株式会社 filed Critical 松下电器产业株式会社
2011-01-07 Priority to PCT/JP2011/000034 priority patent/WO2011108174A1/en
2012-05-09 Publication of CN102449965A publication Critical patent/CN102449965A/en
2015-01-14 Publication of CN102449965B publication Critical patent/CN102449965B/en
238000004064 recycling Methods 0 claims description 26
Disclosed is a relay device that controls traffic flow quantities to alleviate increases in latency or jitter, as well as decreases in throughput, of integrated circuits as a whole. A relay device comprises a switch that changes combinations of inputs that receive traffic data and of outputs that transmit traffic data; a congestion information processing unit that acquires congestion information that denotes the degree of congestion for all traffic from adjacent relay devices that collectively handle a plurality of traffic, and congestion information for all traffic in the present relay device; a congestion information comparison device that derives a degree of congestion that quantitatively denotes the difficulty in flow for all traffic upon a transmission path, on the basis of the congestion information obtained from the adjacent relay devices and the congestion information of the present relay device; a transmission schedule adjustment unit that allocates bus transmission bandwidth for all traffic on the basis of the degree of congestion; and a switch allocation unit that changes the switch on the basis of the results of the allocation of the bus transmission bandwidth.
The present invention relates to the technology adjusting the transmission scheduling in the multiple business (traffic) being connected to the multiple inter-repeater flowings between bus in the semiconductor integrated circuit possessing decentralized bus.
Fig. 1 (a) illustrates the example of the bus marco of concentrated.In the existing integrated circuit of bus marco carrying out concentrated, be connected between multiple bus master controller (bus master) and memory mainly through a bus, mediated from the access of each bus master controller to memory by moderator (arbiter).But due to multifunction, the multiple-core of integrated circuit, circuit scale increases, also intricately variation is while flow through bus for business, and the design based on the integrated circuit of concentrated bus marco becomes more and more difficult.
On the other hand, in recent years, add there is the interconnection technique of parallel computer, the exploitation of semiconductor integrated circuit of bus of the decentralized of network control technology is developed.Fig. 1 (b) shows the example of the bus marco of decentralized.The semiconductor integrated circuit with the bus of decentralized is configured to connect multiple repeater by multiple bus.In recent years, by adopting the bus of decentralized such shown in Fig. 1 (b), there is the framework business in the integrated circuit of large-scale being dispersed in the network-on-chip (Network on Chip) that multiple bus carries out transmitting.
But, for the bus of decentralized, between the bus master controller separated by repeater, do not utilize mutual transmission to mediate.Therefore, in the repeaters, produce interference due to the change of the quantity at business interflow, the throughput of business, cause the increase of time of delay and shake (jitter), the reduction etc. of throughput, transmission quality reduces.
As the technology of reduction of transmission quality avoiding the business flowing through decentralized bus, present known following technology: in the repeaters, by adjusting the transmission scheduling of every business, suppress the interference (for example, referring to patent documentation 1) between business in the repeaters.
Fig. 2 illustrates the existing formation of repeater and the transmit path of business A ~ C controlling to send scheduling described in patent documentation 1.Business A sends to memory D from bus master controller A via repeater E and repeater F.Business B sends to memory D from bus master controller B via repeater E and repeater F.Business C sends to memory D from bus master controller C via repeater F.
Repeater shown in Fig. 2 has multiple transmission buffer.In addition, be attached with in the packet (packet) sent from bus master controller A ~ C for determining that this packet is the information of the packet of which business.
Each repeater, when receiving packet, carries out distinguishing according to each business thus each packet is stored into different buffers.And, when sending packet to next repeater, becoming fair mode according to the transmission quality (time of delay, throughput) of each business, sending the packet in each buffer.This process is called as " Dispatching adjustment process ".
In the figure 2 example, in the repeater E at business A and business B interflow, when to each business of repeater 2 relaying, adjust according to the mode of each 50% allocated frequency band liberally and send scheduling.And then in the repeater F at business A, business B, business C interflow, similarly according to the mode of frequency band of each business being distributed liberally to each 33%, adjustment sends scheduling.
Accordingly, distribute transmission band liberally to from 3 bus master controllers to each business of memory D, so the reduction of transmission performance that the interference between can suppressing by business causes.
Patent documentation 1:JP JP 2008-541647 publication
In existing repeater, by each repeater, only adjust according to the state by the business of itself and send scheduling, and control according to making transmission performance become fair mode partly.In other words, each repeater adjustment transmission scheduling egoistically independently.Thus, the condition that higher business etc. flows through the business of circuit is set according to priority, the adjustment of the transmission scheduling undertaken by each repeater and the competition that produces between business, make the transmission performance (time of delay, throughput) of circuit integrity reduce on the contrary.
Below, this problem is specifically described.
Fig. 3 illustrates business A ~ C when to there occurs competition between business.
In figure 3, business A sends to memory G via repeater E and repeater F by bus master controller A, and business B sends to memory D via repeater E and repeater F by bus master controller B, and business C sends to memory D via repeater F by bus master controller C.
And, in figure 3, suppose that business C sends when urgent, be set relatively high priority.To this business C, repeater F priority allocation is to whole transmission bands (100%) of the bus of memory D.This result, becomes the frequency band of the bus of business B not being divided to orientation memory D.
If as in the past, each repeater only carries out the adjustment of the transmission scheduling in repeater E and repeater F according to the state by the business of itself, although then the repeater F of the sending destination of business B is not to the frequency band of business B distribution bus, repeater E also respectively distributes the transmission band of 50% liberally to business A and business B.This is for circuit integrity, and the transmission scheduling controlling that repeater E performs can make to reduce from repeater E to the utilization ratio of the bus of repeater F on the contrary.
The present invention develops to solve above-mentioned problem, its object is to control the service traffics in repeater, with the increase of time of delay or shake suppressing circuit integrity, the reduction etc. of throughput.
Repeater of the present invention, connects multiple bus in the integrated circuit possessing decentralized bus, and described repeater comprises: switch, and it switches the combination of the input receiving business datum and the output sending described business datum; Congestion information handling part, it obtains the congestion information represented from the described each business in the congestion information of the degree of crowding of each business of the adjacent repeater of the multiple business of co-treatment and this repeater; Congestion information comparing section, it, according to the described congestion information the described congestion information obtained from described adjacent repeater and this repeater, obtains the information of the crowding of the flowing difficulty of each business represented quantitatively on the transmit path; Send Dispatching adjustment portion, it is according to described crowding, by described each traffic assignments bus transmission band thus adjustment send scheduling; With switch dispenser, it switches described switch according to the allocation result of the transmission band of described bus.
Described congestion information represents that the business datum of each business in this repeater is by the time of delay required for this repeater, described congestion information comparing section according to the time of delay of each business in the time of delay of each business obtained from described adjacent repeater and this repeater, can obtain the information of the crowding of the flowing difficulty of each business represented quantitatively on the transmit path.
Described crowding is the numerical value of the flowing difficulty of each business represented on the transmit path, business more easily flows and gives less numerical value, more being difficult to flows gives larger numerical value, and described transmission Dispatching adjustment portion the business relatively little to described crowding can preferentially distribute the transmission band of described bus.
Described transmission Dispatching adjustment portion the business relatively little to described crowding can relatively broadly guarantee the transmission band of described bus, the transmission band of described bus is first utilized, or pass through the utilized time of the transmission band guaranteeing described bus relatively longly, thus preferentially distribute the transmission band of described bus.
The business datum of each business is split into bag and transmits on the bus, and described repeater can also comprise: bag waste part, and it discards the bag of the described crowding business larger than predetermined threshold value from input buffer; With repeat requests portion, it retransmits to the buffer request as transmission source the bag gone out of use.
The business datum of each business is split into bag and transmits on the bus, and described repeater can also comprise: multiple output buffer, and it is connected to the multiple outputs sending data to different buses; With route recycling notification unit, it, to the continuous print bag of the described crowding business larger than predetermined threshold value, distributes identical output buffer, and the recycling of setting to next repeater notice route that business is sent to.
The Action clock of described bus can change, described repeater can also comprise: Action clock control part, described Action clock control part, when the business that described crowding is larger than predetermined threshold value is sent out, makes the Action clock of the bus being connected to described output improve.
Described repeater can also comprise: cooperation control stop, the Delay time larger than predetermined threshold value is there occurs in this repeater, described cooperation control stop only passes through the time of delay required for this repeater according to the described business datum in this repeater, decides described crowding.
Other repeaters of the present invention, connect multiple bus in the integrated circuit possessing decentralized bus, and described repeater comprises: switch, and it switches the combination of the input buffer receiving business datum and the output buffer sending described business datum; Congestion information handling part, it obtains the congestion information represented from the described each business in the congestion information of the degree of crowding of each business of the adjacent repeater of the multiple business of co-treatment and this repeater; Congestion information comparing section, it, according to the described congestion information the described congestion information obtained from described adjacent repeater and this repeater, obtains the information of the crowding of the flowing difficulty of each business represented quantitatively on the transmit path; Send Dispatching adjustment portion, it is using the crowding of the crowding of each business as the input buffer of the business datum of each business of storage, according to the crowding of described input buffer, determine the value of weight of the output buffer storing described business datum, according to the value of determined weight to the transmission band of described each traffic assignments bus thus adjustment sends scheduling; With switch dispenser, it switches described switch according to the allocation result of the transmission band of described bus.
Described transmission Dispatching adjustment portion can to have received the input buffer sent request, by the probability connecting valve corresponding with the value of the weight giving each output buffer.
Described transmission band can be divided into multiple time slot by described transmission Dispatching adjustment portion in time, distributes the time slot of the quantity specified by the value of described weight to each output buffer.
Described transmission Dispatching adjustment portion can utilize by the preassigned ratio of value of described weight, selects described output buffer probabilityly.
According to repeater of the present invention, according to the congestion information in the congestion information obtained from adjacent repeater and this repeater, obtain the information of the crowding of the flowing difficulty of each business represented quantitatively on the transmit path.And, according to this crowding, to the transmission band of each traffic assignments bus thus adjustment sends scheduling.Accordingly, the reduction of the transmission quality (time of delay, throughput etc.) caused due to the interference between business on the transmit path of each business can be suppressed.By improving the utilization ratio of decentralized bus entirety, thus the raising (low delay, high-throughput) of the transmission performance of integrated circuits integral can be realized.
(a) of Fig. 1 is the figure of the example of the bus marco representing concentrated, and (b) is the figure of the example of the bus marco representing decentralized.
Fig. 2 represents that existing control theed record in patent documentation 1 sends the formation of repeater of scheduling and the figure of the transmit path of business A ~ C.
Fig. 3 is the figure of the business A ~ C represented when to there occurs competition between business.
Fig. 4 is the figure of the action summary representing repeater of the present invention.
Fig. 5 is the pie graph of the bus of the decentralized represented in execution mode 1.
Fig. 6 is an example of the transformat representing bag 60 and bag 60 is divided into the figure of example of multiple microplate (flit).
Fig. 7 is the pie graph of the repeater 700 represented in execution mode 1.
Fig. 8 is the flow chart of the motion flow of the repeater 700 illustrated in execution mode 1.
Fig. 9 illustrates the figure that by each transmission path, the flowing difficulty of the bag data of each business can be carried out quantitatively the object measured as congestion information.
Figure 10 is the congestion state illustrated by comparing repeater itself 700 and adjacent repeater 711, the figure of the method for the crowding of computing service A and business B in this repeater 700.
Figure 11 is the figure of the distribution method illustrated based on the output buffer 703 sending Dispatching adjustment portion 709 and buffer dispenser 705.
Figure 12 be to illustrate based on the business being assigned with output buffer of switch dispenser 706 between the figure of method of transmission scheduling.
Figure 13 illustrates by Weighted Round Robin, the figure of the distribution method of weight during diverter switch.
Figure 14 is the figure of each transmission path of the business A ~ C represented in the multistage connection network of Fig. 5.
Figure 15 is the figure of the example of the time of delay of each repeater on the transmission path of business A when representing simultaneously mobile service A and business B.
Figure 16 is the figure of the example of the time of delay of business in each repeater when representing simultaneously mobile service A, business B and business C.
Figure 17 represents the definition as crowding, as the alternative figure employing the example of difference of the ratio of the congestion information of this repeater and adjacent relays.
Figure 18 illustrates that basis, being in the time of delay of repeater R0 of upstream side of Business Stream and the time of delay at repeater R2, is assigned to the figure of the transmission band of the bus of repeater R10 to business A and business C in repeater R6.
Figure 19 represents figure repeater being arranged as cancellate various topology.
Figure 20 is the pie graph of the pie graph of repeater 800 in execution mode 2.
Figure 21 represents the bag and the microplate group thereof that send from bus master controller in execution mode 2 and is documented in the figure of the information a microplate.
Figure 22 is the figure of the action of the repeater 800 illustrated in execution mode 2.
Figure 23 is the pie graph of the repeater 810 in execution mode 3.
Figure 24 is the figure of the action of the repeater 810 illustrated in execution mode 3.
Figure 25 is the pie graph of the repeater 820 in execution mode 4.
Figure 26 is the figure of the action of the repeater 820 illustrated in execution mode 4.
Figure 27 is the figure of the formation of the repeater 830 represented in execution mode 5.
Figure 28 is the figure of the action of the repeater 830 illustrated in execution mode 5.
Figure 29 is the different figure that packet system and circuit switching mode are described.
Figure 30 is the figure of the formation of the repeater 840 of the circuit switching mode represented in execution mode 6.
Before explanation the embodiments of the present invention, first the operating principle of repeater of the present invention is described.
Fig. 4 illustrates the action summary of repeater of the present invention.
In the diagram, in the same manner as Fig. 3, suppose that bus master controller A sends business A, bus master controller B via repeater E and repeater F to memory G and sends business B, bus master controller C via repeater F to memory D transmission business via repeater E and repeater F to memory D.
Business A and business B is sent to repeater F by repeater E of the present invention.When determining the transmission band of business A and business B, repeater E sends request to adjacent repeater F, to the value of the flowing difficulty (stream れ To く さ) of the packet of the business A in repeater F notice quantitatively expression repeater F and business B.In the execution mode of following explanation, this value is called " congestion information ".In this manual, by the packet of each business respectively by the time (" time of delay " hereinafter referred to as each business) required for each repeater as congestion information.
The repeater E of congestion information is received for each business, the time of delay in the time of delay relatively in this repeater E and adjacent repeater F from repeater F.Then repeater E calculates the information of the flowing difficulty of the packet represented quantitatively on path by each business.In this manual, also this information is called " crowding ".When obtaining the crowding of each business, repeater E adjusts the transmission scheduling of each business, makes the transmission band of the bus of dividing orientation repeater F according to the size of this value.
Suppose the situation of priority business C when sending urgent from bus master controller C to memory D in the diagram.Now, the transmission band from repeater F to the bus of memory D in repeater F is occupied by business C temporarily.Because due to the generation of priority business C time urgent, the packet of business B can not send to memory D, so the time of delay of business B in repeater F is elongated.
Each time of delay of business A and business B is informed to repeater E as the congestion information of itself by repeater F.Repeater E compared from the time of delay of repeater F notice and the time of delay at this repeater.Its result, repeater E can determine that the packet of business B in repeater F becomes and be difficult to flowing than business A.Therefore repeater E adjusts and sends scheduling, makes preferentially to be assigned as the transmission band of the bus arriving repeater F from 50% to 100% for business A.On the other hand, adjustment sends scheduling, makes to be reduced to the transmission band of bus from 50% to 0% for business B.
In addition, in present specification, the transmission band of so-called " preferentially distributing " bus, is not limited to expression and relatively broadly guarantees transmission band as described above.In addition, also can represent and can first utilize the mode of the transmission band of bus carry out discharging thus relatively first transmit this business according to this business, the utilized time (allowed time) of guaranteeing this transmission band can also be represented relatively longly.
In the present invention, the business that prioritised transmission priority is high, studies the problem of the business current control each other of how to carry out the low business of priority or not setting priority simultaneously.
Below, the execution mode of repeater of the present invention is described with reference to accompanying drawing.
Fig. 5 is the pie graph of the bus of decentralized in present embodiment.
In the present embodiment, be described for the structure (multistage connection network: MIN (Multistage Interconnection Network)) connecting multiple bus control unit (BM) and memory and multiple repeater with bus multistage.
Shown in Figure 5, the mode of circuit of 8 bus master controllers (BM0 ~ BM7), 12 repeaters (R0 ~ R11) and 8 memories (memory 0 ~ 7) is connected by bus.It is 3 groups by 12 every 4 components of repeater.3 groups are connected to the group (R0, R1, R2, R3) of 8 bus master controllers, the group (R8, R9, R10, R11) being connected to 8 memories and the group (R4, R5, R6, R7) coupled together by the repeater being connected to bus master controller or memory.
The each repeater forming multistage connection network possesses intersection (crossbar) switch of 2 inputs 2 outputs.As shown in Fig. 5 (b), changed the combination of input and output by diverter switch, thus Business Stream can be switched to 2 kinds of transmission paths and send.In addition, if the transmission path exporting destination is different, then 2 business can be outputted to each transmission path by repeater simultaneously.
In multistage connection network, by switching the switch of each repeater, more than one transmission path must be built between full bus master controller and full memory.
Generally, in order to be connected whole N number of bus master controller and M memory by cross bar switch, switch needs N × M.And the quantity with bus master controller or memory increases, and the quantity of switch sharply increases.In contrast, there is following feature for multistage connection network (MIN): by hierarchically connecting the few cross bar switch of input and output quantity, can with being connected between less switching over bus master controller with memory.
In addition, be described for multistage connection network in the present embodiment, but this is only an example.Even if the structure of integrated circuit is other topologys also can apply the present invention.In addition, in the present embodiment, the situation that the data transfer from bus master controller to memory is carried out via multiple repeater by packet system is described.
As shown in Fig. 5 (a), bag is split into the size being called as microplate (flit), is sent to adjacent repeater.
Fig. 6 illustrates an example of the transformat of bag 60 and bag 60 is divided into the example of multiple microplate.
Bag 60 comprises a field (field) 61, data field 62 and control code field 63.
In head field 61, such as, describe the information of the address of sending destination, the address of transmission source, the priority of expression business.The description method of priority is arbitrary, can show with many-valued.When with many-valued description, to the process needed compared with the user interface of high responsiveness, can distribute higher numerical value must be higher by priority level initializing.On the other hand, the decoding (transcode) for the image can tackled in background process processes, and can distribute lower numerical value must be lower by priority level initializing.After these information, describe the data that will transmit.
In data field 62, such as, describe image data, voice data.In control code field 63, such as, describe the end code of the bag 60 predetermined.
According to the address of sending destination in the data of above-mentioned head field 61 and the address of transmission source, carry out the relay process of bag 60 and the reception process at receiver side.
The bus master controller of transmitter side transmits after bag 60 being decomposed into the less bag unit being referred to as microplate.1 microplate is the data using bus can be transmitted by 1 cycle (cycle), and its size is decided by the size of highway width.The microplate of the initial transmission in the microplate split bag 60 is referred to as a microplate (header flit).In head microplate, additional representation is the address information of the label information of the beginning of bag and the sending destination of bag.
In addition, do not have to store the address information for determining sending destination in each microplate after a microplate.This reason is that the microplate after a microplate is sent to the destination identical with head microplate.Determine destination by head microplate, after determining the output buffer of the microplate exporting this business, utilize the output buffer identical with head microplate, follow-up microplate is transmitted the destination to the end shown in microplate.
The microplate be transmitted, when detecting the end code described in control code field 63, according to this end code, is reconstructed into bag by the memory of receiver side.
Such as, the size of 1 bag is 128 bytes (byte), and the size of 1 microplate is 32 bits (bit) or 64 bits.But the size of 1 bag and the size of 1 microplate can be different according to application difference, so should note an above-mentioned size only example.The length of microplate, can using the length of the control datas such as the address of the address and transmission source that can describe sending destination as benchmark.
In each repeater, prepare for accumulating the buffer being sent out the microplate come.After microplate is temporarily accumulated in this buffer, by the switching of switch, be sent to and connect the repeater of destination path or the memory of destination.
Fig. 7 is the pie graph of the repeater 700 in present embodiment.
The repeater 700 of Fig. 7 is connected with adjacent repeater group 710,711 by bus, in order to the microplate sent from adjacent repeater group 710 being relayed to the adjacent relays 711 groups connecting correct destination, and diverter switch, control the transmission scheduling of microplate.
Repeater 700 has input buffer 701, switch 702, output buffer 703, route processing portion 704, buffer allocation portion 705, switch dispenser 706, congestion information handling part 707, congestion information comparing section 708 and sends Dispatching adjustment portion 709.
Below, the function of each inscape is described.
Input buffer 701 is the temporary buffers accumulated the microplate sent from adjacent repeater (or bus master controller).Form the temporary buffer of input buffer 701, one can be arranged by the input of each repeater 700, or carry out respectively accumulating according to the bag that difference destination is different and can carry out sending the mode of scheduling controlling respectively, multiple temporary buffer can be set by each input.In the present embodiment, as shown in Figure 7,2 input buffers are respectively possessed to each input.
Switch 702 is cross bar switches of the connection combination of constrained input for switching repeater 700.
Output buffer 703 is the temporary buffers utilized when adjacent repeater 711 sends microplate.Output buffer 703 is provided with the quantity identical with the input buffer of adjacent repeater 711.Between each output buffer and each input buffer of repeater 711 of repeater 700, define 1 to 1 corresponding relation.From the microplate that the output buffer of repeater 700 sends, be accumulated in the input buffer of the adjacent repeater 711 corresponding with this output buffer 703.Therefore, repeater 700, by selecting the output buffer for sending microplate, can specify the input buffer of adjacent repeater 711.
Route processing portion 704, when sending new head microplate in input buffer 701, receives this microplate, and according to the destination information described in head microplate, determines the repeater next will paid.
Buffer allocation portion 705 divides the special output buffer being used in and sending microplate to the input buffer that have accumulated microplate, make microplate be relayed to suitable path.
For buffer allocation portion 705, when head microplate arrives input buffer, from the output buffer 703 be connected with the transmit path determined by route processing portion 704, selecting the output buffer be not utilized at this time point, distributing an output buffer 703 as the private buffer for sending microplate.
By buffer allocation portion 705, until a bag is overall by repeater, maintain the combination of input buffer and output buffer.
Switch dispenser 706 is from the combination of the input buffer 701 determined by buffer allocation portion 705 and output buffer 703, determine the actual combination adjacent repeater 711 being sent to microplate, switch the switch 702 between input buffer 701 and output buffer 703.
The repeater group 710,711 of the vicinity of congestion information handling part 707 pairs of multiple business of co-treatment sends request, obtains the congestion information of the expression degree of crowding by each business.In addition, congestion information handling part 707 is when receiving the request of congestion information from contiguous repeater group 710,711, this repeater is obtained to the congestion information of the flowing difficulty representing packet by the business of each transmission path quantitatively by measuring, and acquired congestion information is exported to this repeater.
In addition, as congestion information, the such as time of delay of measurement data bag by spending till repeater, use this value.
More be difficult to flowing because packet on the transmit path becomes, then be more difficult to send microplate to bus in repeater 700, the time of delay of packet is elongated, so can according to the flowing difficulty of the packet determined quantitatively time of delay on each transmission path.
Congestion information comparing section 708 compares the congestion information of each business notified from contiguous repeater 710,711, the congestion information with the repeater 700 of each business determined by the sending destination described head itself, calculates the crowding of the flowing difficulty on the path representing each business quantitatively.
Send Dispatching adjustment portion 709 according to the crowding obtained by congestion information comparing section 708, to the distribution of the transmission band of each business reorganization bus.
In the adjustment of the distribution of the transmission band in repeater 700, comprise the adjustment of the adjustment of the scheduling how being distributed temporary buffer by buffer allocation portion 705 in output buffer 703 and the switch dispenser 706 how scheduling of diverter switch 702.
Below, the action of each repeater 700 is described.
Fig. 8 is the flow chart of the flow process of the action of the repeater 700 illustrated in present embodiment.
This microplate, when sending microplate from contiguous repeater 710, is accumulated the given buffer (step 801) in input buffer 701 by repeater 700.The system of selection of the buffer of accumulation microplate can consider various method.Such as previously described like that, the microplate that the output buffer of the repeater 710 from prime sends can be accumulated in the input buffer of the adjacent repeater 711 corresponding with this output buffer 703.There is not the repeater of prime, directly sending microplate from bus master controller, can specify the input buffer of accumulation microplate in bus master controller side, microplate is accumulated in the input buffer of specifying in bus master controller side by repeater 700.In addition, the buffer of sky can also be accumulated when microplate is microplate, the buffer of the head microplate that accumulation is corresponding with this microplate when not being microplate.Also can distinguish by the microplate of the identical bag of each formation, select different input buffers.
Input buffer 701 judges whether the microplate by accumulating is a microplate (step 802).
When being microplate by the microplate accumulated, enter the process that step 803 transfers to next sending destination for determining data, when not being microplate, enter step 807, using the path identical with the head microplate corresponding to this microplate as sending destination.
Route processing portion 704, when being sent to the microplate in input buffer and being microplate, according to the address information of destination subsidiary in head microplate, determines the repeater (step 803) that next will send.
When the multistage connection network shown in Fig. 5, to the 2 system number allocation address of each memory with 3, the address of the memory becoming destination is given to the 2 system numbers of 3 in the head microplate of each bag.
The route test portion 704 of each repeater reads the numeral of the position identical with the progression of repeater from the address of 3 giving a microplate.Then determine path, if make this value be 0, the repeater to the upper right in Fig. 5 sends microplate, if value is 1, the repeater to the bottom right in Fig. 5 sends microplate.
Such as, from bus master controller BM2 to memory 5 (address: when 101) sending data, according to the numeral of 3 that record in address, first in repeater R1, microplate is sent to the repeater R7 of bottom right, then in repeater R7, send microplate to the repeater R10 of upper right, finally send microplate at repeater R10 to the memory 5 of bottom right.Accordingly, microplate is transmitted from bus master controller BM5 to memory 2.
In addition, as the method that the route (path) in route processing portion 704 controls, as long as according to the topology of decentralized bus, suitably microplate being sent to the method for destination, also can be method other than the above.
When determining the adjacent repeater sending microplate, repeater 700 to be obtained and with reference to congestion information (step 804) from adjacent repeater 711 and repeater 710 by congestion information handling part 707.
Fig. 9 is the figure that the object can measuring the flowing difficulty of the bag data of each business by transmission path is quantitatively described.Measured result is used as congestion information.Congestion information in repeater 700 (1) packet by the idle frequency band etc. of remaining microplate number, (3) bus in time of delay of spending till repeater 700, (2) input buffer.
In integrated circuits, based on the problem such as erection space, cost, mostly wish the size reducing the buffer on circuit as much as possible.Therefore, when the size of input buffer is less, when being used as to measure the index of the degree of crowding by the microplate number (2) in input buffer, precision reduces.In addition, when measuring idle frequency band (3) of bus, need to record the memory (buffer) of state of preset time, bus.On the other hand, using the time of delay (1) of the microplate in repeater as when measuring the index of the degree of crowding, even if utilize less buffer sizes also can measure crowded degree accurately.
In addition, in the present embodiment, as the bus (3) being connected to inter-repeater, be assumed to be the bus transmitting the signal of telecommunication, but also can be in addition, transmit the wired bus of data by light signal, utilize the wireless bus of magnetic or electromagnetic wave transmission signal.And then, for the communication utilizing light signal or Electricity magnetic wave to carry out, different wavelength or frequency can be used in a bus simultaneously.Therefore, crowding can be defined according to utilize number or the vacant number of the wavelength utilized in bus or frequency.
In the following description, the situation that the buffer sizes in suppose relay device 700 is less, is described as congestion information by the time of delay spent till repeater 700 (1) packet.In addition, if can buffer be guaranteed, then also can adopt above-mentioned (2) or (3).This congestion information is obtained by congestion information handling part 707.
Next, by congestion information comparing section 708, congestion information relatively between repeater 700 and adjacent repeater 710 (repeater 711), obtains the crowding (step 805) of the flowing of the expression by each business difficulty on path.
Figure 10 be the congestion state that compares repeater itself 700 and adjacent repeater 711 is described thus in this repeater 700 figure of the method for the crowding of computing service A and business B.
In the present embodiment, for the value of crowding, by congestion information comparing section 706, by each business by the time of delay of the packet notified from the repeater 711 being in downstream be defined as crowding at the ratio of the time of delay of the packet of this repeater 700.
Such as, in Fig. 10, if for business A, by there is the delay in 10 cycles till repeater 700, there is the delay in 5 cycles in packet by the repeater 711 in downstream.Now, the crowding of business A can calculate as described below.
The crowding of business A: 5/10=0.5
On the other hand, for business B, if packet used for 12 cycles by repeater 700, used for 15 cycles by repeater 711.Now, the crowding of business A can calculate as described below.
The crowding of business B: 15/12=1.25
Here, if the value of crowding is larger, packet is more difficult to flowing, for the vicinity of repeater 700, can determine the flowing easness of business A packet compared with business B quantitatively.
In Fig. 10, crowding is defined as the ratio of the time of delay of repeater 1 and the time of delay of repeater 2, but in addition, such as the value after the comparing of the congestion information at time of delay and the difference of the time of delay at repeater 2 or the summation of time of delay etc. of repeater 1, this repeater 700 and adjacent repeater 711 can also be defined as crowding, and use this value.
In addition, can also exist and the corresponding relation of the value of the time of delay of inter-repeater and the value of crowding is defined previously as table information, and reference table information calculates the method for the crowding corresponding with the time of delay notified.
Next, in the step 806 of Fig. 8, send Dispatching adjustment portion 709 according to the crowding of business, determine the priority being used for the input buffer obtaining crowding being sent to microplate.So-called " obtaining the input buffer of crowding ", identical with the crowding of each business.That is, when existence has the business t of crowding x, the crowding inputting the input buffer of the microplate of this business t becomes x.And buffer allocation portion 705 distributes output buffer according to the priority of input buffer.
Figure 11 is the figure of the distribution method that the output buffer 703 sending Dispatching adjustment portion 709 and buffer dispenser 705 execution is described.
For input buffer in repeater, carry out difference to accumulate microplate according to each business, and sent to next repeater by output buffer.
In fig. 11, to from the traffic grooming input buffer 0 of input 0 and input buffer 1, to from the traffic grooming input buffer 2 of input 1 and input buffer 3.And, if obtaining crowding respectively by congestion information comparing section 708 pairs of input buffers 0, input buffer 1, input buffer 2 is 1.0,0.25,0.5.
Which transmit path input buffer, to which output buffer request dispatching, as previously described above, utilizes be sent to memory to determine by the microplate of each business accumulated in input buffer.Because there is different input buffers to 2 the output buffer request dispatching being connected to identical output, so need the distribution determining output buffer.
Send Dispatching adjustment portion 709 according to the information of the crowding obtained by congestion information comparing section 708, give the priority of distributing output buffer to each input buffer.In the example of fig. 11, suppose the crowding of each input buffer is directly used as the situation of the priority of distributing output buffer and is explained.In addition, the value that the priority of output buffer is set as the crowding of the input buffer storing the microplate sent from this output buffer is distributed more little more preferential.
When determining the priority of each input buffer, each input buffer is to the distribution of the output buffer request output buffer be not utilized in the output buffer of the outlet side connected to next repeater determined by route processing portion 704.
Buffer allocation portion 705 is from carrying out each output buffer distributing the decision distributed the input buffer notice that crowding is minimum the input buffer of request.
In the example of fig. 11, input buffer 0, input buffer 1, input buffer 2 are to the output buffer of output 0 side request dispatching respectively.And, by the output buffer respectively having request, the decision that the input buffer 0 minimum to crowding and input buffer 2 distribute.
Determine the distribution of output buffer when delivery header microplate, until the whole microplates forming the bag corresponding with this microplate are sent out, continue the state that output buffer is assigned with.
Next, switch dispenser 706 connects the switch between input buffer and output buffer successively from the input buffer that crowding is little, and the microplate in input buffer is sent to adjacent repeater (step 807).
Figure 12 illustrates be assigned with by switch dispenser 706 figure adjusting the method sending scheduling between the business of output buffer.
The scheduling of the transmission at repeater in present embodiment is switched by the connection of the switch between input buffer and output buffer and carries out.
In fig. 12, whole input buffer is completed to the distribution of output buffer.Output buffer 0 is assigned with to input buffer 0, output buffer 3 is assigned with to input buffer 1.In addition, output buffer 1 is assigned with to input buffer 2, output buffer 2 is assigned with to input buffer 3.
Switch dispenser 706, exports input buffer connecting valve little to crowding in the input buffer of the output buffer be connected with each being connected to, and permits to send microplate to adjacent repeater.If input and the group that exports different, then switch dispenser 706 can to this different group connecting valve side by side simultaneously.
If study the output buffer 0 be connected with output 0 shown in Figure 12 and output buffer 1, then the crowding 0.5 being assigned with the input buffer 2 of output buffer 1 is less than the crowding 1.0 of the input buffer 0 being assigned with output buffer 0.Therefore, between input buffer 2 and output buffer 1, carry out the connection of switch.When the content of the input buffer being connected to switch becomes empty, at the end of the transmission of this microplate, between input buffer 0 and output buffer 0, carry out the connection of switch, send microplate.
Similarly, if study the output buffer 2 be connected with output 1 and output buffer 3, then the crowding 0.25 being assigned with the input buffer 1 of output buffer 3 is less than the crowding 2.0 of the input buffer 3 being assigned with output buffer 2.Therefore, between input buffer 3 and output buffer 2, carry out the connection of switch.When the content of the input buffer being connected to switch becomes empty, at the end of the transmission of this microplate, between input buffer 1 and output buffer 3, carry out the connection of switch, send microplate.Its result, each microplate is sent to adjacent different repeater.
So, by the value of the crowding according to each business, the priority of the distribution of adjustment switch, can to each business reorganization transmission band to the sendout of the bus of outlet side.
In addition, as the changing method of switch, except the connection of diverter switch the input buffer little from crowding, the content of input buffer is made to be beyond empty method successively, such as, also there is the method using Weighted Round Robin (Weighted Round Robin:WRR).
Figure 13 is the figure of the distribution method illustrated by weight during Weighted Round Robin diverter switch.
For Weighted Round Robin, being the whole input buffers sent request to there is microplate, when often sending 1 microplate, utilizing (proportional) probability corresponding with the value of the weight giving each output buffer to carry out the method for connecting valve.The weight below illustrated calculate process, allocation process by send Dispatching adjustment portion 709 perform.
In the example in figure 13, for the weight of each output buffer, according to the crowding of input buffer being assigned with this output buffer, it is reciprocally used as weight.Specifically, the weight giving output buffer 0 is the inverse of the crowding 1.0 of input buffer 0 is 1.0.The weight giving output buffer 1 is the inverse of the crowding 0.5 of input buffer 2 is 2.0.The weight giving output buffer 2 is the inverse of the crowding 2.0 of input buffer 3 is 0.5.The weight giving output buffer 3 is the inverse of the crowding 0.25 of input buffer 1 is 4.
When using Weighted Round Robin diverter switch, export 0 according to output buffer 0 and the respective weight of output buffer 1, utilize 1 to 2 ratio send microplate via each output buffer.In addition export 1 according to output buffer 2 and the respective weight of output buffer 3, utilize about 1 to 8 ratio send microplate via each output buffer.
So, for utilizing the transmission of Weighted Round Robin to dispatch, by the value of weight, between output buffer, the allocation proportion of transmission band can be adjusted to the bus of outlet side.
In addition, in the step 806 and 809 of Fig. 8, be illustrated for the situation value of crowding being directly used in the distribution of output buffer and the distribution of switch.But, as long as reflect the value of crowding, then other also can be used to define.In addition, although describe the input buffer to the distribution wanting preferential output buffer and switch, make the example that the value of priority diminishes, also can give larger value, from the input buffer that value is large, give output buffer and switch.
In addition, as the transmission band based on Weighted Round Robin to the concrete method of adjustment of the distribution of each output buffer, exist: transmission band is divided into multiple time slot in time, each output buffer is distributed to the method for the time slot of the quantity specified by the value of weight; And utilize by the value of weight preassigned ratio, select the method etc. of output bus (output buffer) probabilityly.
When microplate beyond delivery header microplate, do not carry out the distribution of the route of step 803 and the output buffer of step 806.Congestion information handling part 707 carries out obtaining of the congestion information of adjacent repeater and with reference to (step 807), congestion information comparing section 708 only carries out comparing (step 808) of the crowded state mutual with contiguous repeater.Identical with the process of (step 805) with (step 804) respectively with the comparative approach (step 808) of the congestion information mutual with contiguous repeater for the obtaining of the congestion information/reference method (step 807) of adjacent repeater, so omit the description.
Microplate in input buffer, when determining the distribution of switch 702 by switch dispenser 706, is passed through distributed output buffer and sends to adjacent repeater 711 (step 810) by repeater 700.
The congestion information of the repeater after microplate sends by congestion information handling part 707 informs to contiguous repeater 710,711 (step 811).
Below, Figure 14, Figure 15, Figure 16 is used to explain the action of the repeater in present embodiment.
Figure 14 illustrates each transmission path of the business A ~ C in the multistage connection network of Fig. 5.Business A transmits from bus master controller BM0 to memory 4.Business B transmits from bus master controller BM1 to memory 6.Business C transmits from bus master controller BM5 to memory 5.
At the same time during mobile service A and business B, disturbing from repeater R0 to the bus of repeater R6.In addition, at the same time during mobile service A and business C, disturbing from repeater R6 to the bus of repeater R10.
The example of the time of delay of each repeater on the transmission path of business A while that Figure 15 illustrating during mobile service A and business B.
In fig .15, the business A in repeater R0 and the time of delay of business B, be set to for 10 cycles respectively owing to mutually disturbing.In addition, the business A in repeater R6 and the time of delay of business B are because flow to different paths respectively, so be set to for 5 cycles respectively.So become 0.5 in the crowding of the business A of repeater R0, the crowding of business B becomes 0.5, the flowing difficulty on transmission path is all identical to each business.Therefore, repeater R0 adjusts the scheduling sent, and makes the transmission band of the bus to repeater R6 respectively distribute 50% equably to business A and business B.So-called scheduling means the distribution of output buffer and the distribution of switch.Below too.
Next, the example of the time of delay of the business in each repeater while that Figure 16 illustrating and goes back except business A and business B during mobile service C.
In figure 16, the business A in repeater R0 and the time of delay of business B were set to for 10 cycles respectively owing to mutually disturbing.In addition, in repeater R6, because business A and business C disturbs mutually, time of delay was set to for 10 cycles respectively.On the other hand, to the business B of other path flow, because do not disturb with other business, be then set to for 5 cycles time of delay.So, become 1 in the crowding of the business A of repeater R0, the crowding of business B become 0.5, determine business A and be difficult to flowing on the transmit path compared with business B.
Repeater R0, according to the size of the crowding of business A and business B, divides the transmission band of the bus of orientation repeater R6.Such as, when the transmission band that repeater R1 has utilized Weighted Round Robin to each traffic assignments and the value of crowding is inversely proportional, repeater R0 adjusts the scheduling sent, and makes to business A distribution transmission band 33%, distributes 66% of transmission band to business B.
In addition, if tailed off by the distribution of the transmission band of repeater R0 business A, then in repeater R0, the interference of business A and business B dies down, so the time of delay of business B is cut down.In addition, because the interference of business A and business C dies down in R6, so cut down the time of delay of business C.
So, for the change of business number, flow, by reducing the transmission band that the business C disturbed occurs with multiple business on the transmit path, increase the transmission band that business B and the business C disturbed does not occur mutually, preferentially mobile service B and business C, the reduction of the utilization ratio of circuit integrity can be prevented thus, suppress the increase of delay, the reduction of throughput.
Figure 17 illustrates the definition as crowding, as the alternative example employing difference of the ratio of the congestion information of this repeater and adjacent relays.
In fig. 17, by each business, by deduct from the time of delay at this repeater sending destination adjacent relay time of delay gained value be defined as crowding.In addition, in the formula of Figure 17, in order to by Weighted Round Robin process crowding, constant α can be added.Accordingly, crowding can be processed as positive number.As the occurrence of constant α, in order to crowding does not become negative value, the method for the value of the maximum being set in the time of delay can allowed in relaying can be considered.
In addition, in the present embodiment, describe the congestion information of the repeater in the downstream according to mobile service, adjustment sends the example of scheduling (distribution of output buffer, the distribution of switch).But the congestion information of the repeater of the upstream side that also can come from its flowing according to business adjusts and sends scheduling.
Figure 18 illustrates according to being in the time of delay of repeater R0 of upstream side of Business Stream and the time of delay at repeater R2, and how repeater R6 divides the figure of the transmission band of the bus of orientation repeater R10 to business A and business C.
In figure 18, the business A in repeater R0 and the time of delay of business B, be set to for 10 cycles respectively owing to mutually disturbing.In addition, in repeater R6, business A and business C disturbs mutually, and time of delay was set to for 10 cycles respectively, in repeater R2, because flow only through business C so be set to for 5 cycles time of delay.
Repeater R6 obtains the time of delay of business A and business B by repeater R0, is obtained the time of delay of business C by repeater R2, according to comparing of the time of delay with each business in this repeater, calculates crowding.Here, calculate in the same manner as the situation of crowding with use from the time of delay that the repeater in the downstream of mobile service notifies, as the definition of crowding, be used in the time of delay of this repeater R6 being in its downstream to the value of the ratio of the time of delay of the repeater of the upstream side at mobile service.
The crowding obtaining business A is 1 (=10 ÷ 10), the crowding of business B is 0.5 (=5 ÷ 10).
When obtaining crowding, such as, Weighted Round Robin is used at repeater R1, with the value of crowding inversely proportional to each traffic assignments transmission band when, repeater R6 carries out the adjustment of the scheduling sent, make to business A distribute transmission band 33%, to business C distribute transmission band 66%.
In addition, in repeater R6, not only use the congestion information of the repeater of the upstream side from mobile service, also use the congestion information of the repeater from downstream, obtain crowding on the transmit path, and use it for the adjustment sending scheduling.
Such as, can obtain the crowding of upstream side and the crowding in downstream by every business, be crowding by its mean value definition.
As described above, by using the structure that Fig. 7 illustrates and the process illustrated with Fig. 8, each repeater on transmission path exchanges congestion information at adjacent inter-repeater, and based on showing the crowding of flowing difficulty of business on the transmit path according to this comparison sheet, adjust the transmission scheduling of each business.Accordingly, the increase of the delay that the interference between can suppressing by business causes.
In addition, although in the present embodiment, be illustrated for the situation that the topology of integrated circuit is multistage connection network, but as shown in figure 19, even repeater is arranged as clathrate thus reticular pattern, toroidal type, the topology hierarchically connecting bus etc., by repeater, switch via the topology of multiple bus, also can similarly be suitable for.
In execution mode 1, exchange congestion information at adjacent inter-repeater, by the crowding of every business based on the flowing difficulty of the packet represented on the transmit path, the transmission of each business is adjusted.
On the other hand, the crowding that the repeater of present embodiment is relatively more calculated, the bag being difficult to a side of flowing of TA packet, and again to the re-transmission of the bus master requests bag of the transmission source as discarded bag.Accordingly, the increase of the time of delay of business that crowding is little can be suppressed.Should be noted in addition, be not directly ask the re-transmission of wrapping to bus master controller, but be the buffer that the microplate of the repeat requests of this bus master controller sends to the adjacent repeater once sending this bag by comprising destination.This repeat requests is sent to repeater or this bus master controller of upstream by adjacent repeater again.
Repeater can utilize 1 microplate as the data volume that can send in 1 cycle to send repeat requests.But microplate number also can be more than 2.Or, repeat requests can be sent with bag.The transmission path that can flow in common business sends repeat requests, the special transmission path of repeat requests also can be set.
In the network control of internet or WLAN etc., as the method suppressed crowded (congested) of repeater, the general method adopting discarded bag.But, higher to the requirement of reliability in integrated circuits, so when flowing through the loss of data of the business in circuit, need again to retransmit bag discarded when crowded from transmission source.
Figure 20 is the pie graph of the repeater 800 in present embodiment.For formation identical with Fig. 7 in the inscape of Figure 20, mark identical reference marks and omit the description.
When bag waste part 1401 exceedes the business of given threshold value in the crowding detecting each business obtained by congestion information comparing section 708, delete the bag of corresponding business from input buffer 701.
The repeat requests of the bag that repeat requests portion 1402 is deleted to the bus master controller notice as transmission source by described bag waste part.
Figure 21 illustrates the information recorded the bag and microplate group thereof and head microplate sent from bus master controller in the present embodiment.In head microplate, except labeling head, destination-address, also describe the address of transmission source and the ID of bag.The situation of the discarded bag of defence bag waste part 1401, prestores the information (at least the address of transmission source and the ID of bag) of the head microplate of this bag when the every microplate right overhead in repeat requests portion 1402 arrives.And, according to this kept information, there is to the bus master requests as transmission source the re-transmission of the bag of specific ID.
Go out of use the bus master controller of bag in order to avoid crowded, standby preset time, again to have started the transmission of wrapping.
Figure 22 is the figure of the action of the repeater 800 illustrated in present embodiment.
For the action same with Fig. 8, mark identical reference marks and omit the description.
Repeater 800 and adjacent repeater 710 exchange mutual congestion information, by the flowing difficulty of the business of each service computation on path as crowding, and judge whether this value closes at (step 2401) within given threshold value.If the value of crowding is below threshold value, then transfer to step 809, carry out the allocation process of switch in order to the microplate sent in input buffer.
In step 2401, when being judged as that crowding has exceeded given threshold value, the bag waste part 1401 of repeater 800 discards the whole microplates in corresponding input buffer, and in addition, the output buffer (step 2402) of this input buffer is distributed in release.
If the microplate that crowding exceedes in the input buffer of more than given threshold value goes out of use, then transmission source request retransmission from the repeat requests portion 1402 in repeater to discarded bag the bag (step 2403) discarded.
As the method that the notice from repeat requests portion 1402 to transmission source retransmits, can be set forth in flow through business transmission path on pass on round about the bag transmitting repeat requests method and use for notifying the method for dedicated control signal line retransmitted between repeater 800 and transmission source.
By increasing above formation and process, the bag of the crowding business higher than given threshold value discarded by the repeater 800 in present embodiment, so can suppress the reduction of the transmission performance of the circuit integrity caused by the business being difficult to flow of bag data.
In the present embodiment, when the bag common to the continuous sending destination of next repeater, identical output buffer is utilized to send to next repeater, and notify that the bag be continuously transmitted is the bag of the destination that whereabouts is identical to next repeater, omit the distribution (step 806) of route processing (step 803) and the output buffer that follow-up bag is carried out thus, shorten the time of delay in repeater.
Figure 23 is the pie graph of the repeater 810 in present embodiment.To formation identical with Fig. 7 in the inscape of Figure 23, mark identical reference marks and omit the description.
Route recycling notification unit 1501 be by identical output buffer to the bag that next repeater 711 transmission destination is common time, notify that the bag be continuously transmitted is the handling part of the bag of the destination that whereabouts is identical to next repeater 711.In addition, identical input buffer is sent to by identical output buffer to wrapping in next repeater 711 of sending of next repeater 711.
Figure 24 is the figure of the action of the repeater 810 illustrated in present embodiment.
When the bag sent continuously is the bag being sent to identical destination, the route recycling notification unit 1501 of repeater 810 sends the notice of the recycling for carrying out route processing to next repeater 711.Below, the process of the repeater 810 carrying out this process is described.
When sending microplate from adjacent repeater 710, microplate is accumulated in the given input buffer in the input buffer 701 of oneself (step 801) by repeater 810.
In step 802, when received microplate is microplate, route processing portion 701 is confirmed whether recycling notice (step 2601) that have received route from repeater 710.
When there is no the recycling notice of route, need to determine next sending destination.Therefore, route processing portion 704 carries out route processing (step 803).
On the other hand, when there is the recycling notice of route, route processing portion 704 omits route processing, and judge whether the result of the route used when can utilize the transmission of previous bag, in other words, whether the recycling judging output buffer can (step 2602).
The output buffer that buffer allocation portion 705 utilizes when continuing to utilize the input buffer and the transmission of previous bag that have received recycling notice is not assigned with by the request from other input buffers, be judged as that the recycling of output buffer is fine.Now, buffer allocation portion 705 omits the decision (step 806) of the distribution of output buffer, the output buffer used when recycling the transmission of previous bag.And route recycling notification unit 1501 notifies the recycling (step 2603) of route to next repeater 711.
When not continuing the output buffer utilized when utilizing the transmission of previous bag, process enters step 804, and buffer allocation portion 705 determines the output buffer that will utilize again.
In step 806, when distributing output buffer by 705 pairs, buffer allocation portion input buffer, route recycling notification unit 1501 judges the destination whether identical with the destination of previous bag (step 2604) of the bag in input buffer.When the bag identical to identical output buffer continuous dispensing destination, route recycling notifies that 1501 do not need route processing (step 2605) to next repeater notice of bag being carried out to relaying.
So, the repeater 810 of present embodiment by route recycling notification unit 1501 judge the recycling of route could, when recycling, notify that the recycling of route is fine to next repeater 711.And, be omitted in the route processing (step 803) of next repeater 711 and the distribution (step 806) of output buffer.Accordingly, the time of delay in repeater can be cut down.
In addition, in buffer allocation portion 705, when distributing output buffer to each input buffer, according to congestion information, identical output buffer can be given by bag continuous dispensing identical for destination.
Such as, in the quantity of the business with respect to repeater, during the negligible amounts of inputoutput buffer, have to alternately utilize inputoutput buffer between business.Therefore, only low to crowding business preferentially distributes identical inputoutput buffer, the bag of identical destination is continued through identical output buffer and is sent to next repeater.Accordingly, the time of delay of the low business of crowding can be cut down further.
By adding above formation and process, the repeater 810 in present embodiment can omit the process needed for the route processing of the low business of crowding and the distribution of output buffer, so can suppress the reduction of the transmission performance at circuit integrity.
In addition, in description of the present embodiment, the situation of preferentially distributing identical output buffer for the business low to crowding is illustrated.But, also the business high to crowding can preferentially distribute identical output buffer on the contrary, thus suppress the time of delay of the business that crowding is high.Accordingly, the improvement of transmission delay can also be carried out.
In addition, in the present embodiment, by route recycling notice, route processing is eliminated.For route processing computing and recycling could judge all subsistence level 1 cycles.Therefore, do not carry out route by the repeater oneself that have received business, can the processing time be improved.
Route recycling notice " judging process " such as can carry out with " judging to process " of head microplate side by side.Therefore, the processing time can not be made to increase.
Therefore, by the route results of the repeater in prime being transferred sequentially to next repeater thus omitting identical process, the processing time can be cut down.
In the present embodiment, suppose by repeater, individually can change the situation of the Action clock of decentralized bus, improve the Action clock of the bus flow through on the path of the large business of crowding, send microplate quickly than other buses, suppress transmission delay thus.
Figure 25 is the pie graph of the repeater 820 in present embodiment.For the formation identical with Fig. 7 in the inscape of Figure 25, mark identical reference marks and omit the description.
When Action clock adjustment part 1601 detects by sending Dispatching adjustment portion 709 business that crowding is large, priority is low, improve the Action clock of the bus of the side of outgoing traffic.
Figure 26 is the figure of the action of the repeater 820 illustrated in present embodiment.
For the action identical with Fig. 8, mark identical reference notation merging and omit the description.
Action clock adjustment part 1601, when determining the distribution of the switch between each input buffer and output buffer by switch dispenser 706, judges the crowding whether high than given threshold value (step 2701) of buffer.
If there is not the input buffer that crowding exceedes threshold value, then the responsiveness (step 2702) in advance set when the responsiveness of the bus of correspondence is set as supposing common utilization by Action clock adjustment part 1601.
When there is crowding and exceeding the input buffer of threshold value, the responsiveness (step 2703) of quick action in advance set when the responsiveness of the bus of correspondence is set as utilize more common than hypothesis by Action clock adjustment part 1601.
By adding above formation, business high for crowding can be sent to next repeater by the repeater 820 of present embodiment rapidly, cuts down time of delay.Therefore, it is possible to suppress the reduction of the transmission performance of circuit integrity.
In present embodiment 1 ~ 4, at adjacent inter-repeater by every operation exchange time of delay, by the flowing difficulty relatively coming to obtain on path by every business of mutual time of delay, and adjust according to this value the transmission of each business is dispatched.Therefore, for the repeater of execution mode 1 ~ execution mode 4, adjacent repeater coordination with one another, carries out the transmission scheduling controlling coordinated.
In the transmission scheduling controlling that this inter-repeater is coordinated, in certain repeater, the time of delay that there is certain business becomes the situation larger than given threshold value.Even if suppress the time of delay of this business, be also that the transmission coordinated with adjacent repeater is dispatched by preferentially, the delay of business occurs immediately in this repeater.
On the other hand, in the present embodiment, when the crowding of this repeater is higher than given threshold value, the transmission not carrying out coordinating with adjacent repeater is dispatched, only according to the crowded situation in this repeater, carry out egoistic transmission scheduling, suppress the delay in this repeater.
Figure 27 is the figure of the formation of the repeater 830 represented in present embodiment.For the formation identical with Fig. 7 in the inscape of Figure 27, mark identical reference notation merging and omit the description.
Inner congestion information monitoring unit 2801 judges the handling part that time of delay whether exceed given threshold value of business at this repeater 830.
Cooperation control stop 2802 be in business when exceeding given threshold value the time of delay of this repeater 830, stop the calculating based on the crowding compared of the time of delay with adjacent repeater 711, replace it, only according to the handling part determining crowding in the time of delay of this repeater.
Figure 28 is the figure of the action of the repeater 830 illustrated in present embodiment.
The inside crowding monitoring unit 2801 of repeater 830 judges whether the time of delay of the input buffer in this repeater 830 is greater than given threshold value (step 2801).
The time of delay of the input buffer in this repeater 830 is when being less than given threshold value, cooperation control stop 2802 indicates congestion information comparing section 708, by comparing in the time of delay of adjacent repeater 711 and obtaining crowding in the time of delay of this repeater 830, and crowding is conveyed to transmission Dispatching adjustment portion 709 (step 2802).
On the other hand, the time of delay of the input buffer in this repeater 830 is when being greater than given threshold value, cooperation control stop 2802 replaces congestion information comparing section 708 only to utilize size in the time of delay of this repeater 830 to obtain crowding, and crowding is conveyed to and send Dispatching adjustment portion 709 (step 2802).
By adding above formation, the time of delay that the repeater 830 of present embodiment occurs in this repeater is higher than given threshold value, do not match with the crowded situation of adjacent repeater, and by egoistic transmission scheduling controlling, the reduction override of the time of delay in this repeater can be made, therefore, it is possible to suppress the reduction of the transmission performance of circuit integrity, the reduction of the transmission performance of local can also be suppressed simultaneously.
In execution mode 6, illustrate that the repeater adjustment of circuit switching mode sends the process of scheduling.
The chart of Figure 29 (a), (b) represents the type of flow of the data under exchanged form respectively, and the longitudinal axis of chart represents the position of data, the passage of horizontal axis representing time.
In packet system, as shown in Figure 29 (a), business sends from bus master controller to repeater successively with microplate unit.
On the other hand, in circuit switching mode, as shown in Figure 29 (b), the signal at first for circuit switched is sent to destination by repeater successively from bus master controller.Accordingly, circuit is switched, and afterwards, sends data.
Figure 30 represents the formation of the repeater 840 of the circuit switching mode of present embodiment.In repeater 840, as shown in figure 30, as long as input buffer 701 has the size of 1 microplate amount of the switching signal for accumulating switch.In addition identical with the formation of the packet system of Fig. 7, so omit the description.
Due in circuit switching mode, after guaranteeing circuit, do not disturb between business, so only dispatch for the switching signal adjustment transmission of the switch before transmission data, this adjustment can utilize the method identical with the head microplate of packet system to adjust.
Above, the embodiments of the present invention are described.In this manual, suppose that the inscape of the repeater of each execution mode is all realized by hardware and is illustrated.Hardware can be arranged by each inscape, also can arrange as the circuit etc. incorporating multiple inscape.By arranging as hardware, the process high speed of each repeater can be made, internal processing delay is suppressed to Min..In addition, when can carry out at high speed processing make internal processing delay can not become problem, also can pass through microcomputer executive software, thus on software, realize one or more functions of above-mentioned inscape.
Because repeater involved in the present invention can suppress the increase of delay or the shake caused by the interference of multiple business in the integrated circuit possessing decentralized bus, so it is useful for occurring in the decentralized bus control of the SoC (System on Chip, SOC (system on a chip)) of multiple business transmission etc. in real time in media processes etc.
In addition, by suppression hangover time thus shorten the processing time, the power saving for integrated circuit is also useful.
700 repeaters
701 input buffers
702 switches
703 output buffers
704 route processing portions
705 buffer allocation portions
706 switch dispenser
707 congestion information handling parts
708 congestion information comparing sections
709 send Dispatching adjustment portion
710 adjacent repeaters (receiver side)
711 adjacent repeaters (transmitter side)
1401 bag waste parts
1402 repeat requests portions
1501 route recycling notification units
1601 Action clock adjustment parts
2801 inner congestion information monitoring units
2802 cooperation control stops
1. a repeater, connects multiple bus in the integrated circuit possessing decentralized bus, and described repeater comprises:
Switch, it switches the combination of the input receiving business datum and the output sending described business datum;
Congestion information handling part, it obtains the congestion information represented from the described each business in the congestion information of the degree of crowding of each business of the adjacent repeater of the multiple business of co-treatment and this repeater;
Congestion information comparing section, it, according to the described congestion information the described congestion information obtained from described adjacent repeater and this repeater, obtains the information of the crowding of the flowing difficulty of each business represented quantitatively on the transmit path;
Send Dispatching adjustment portion, it is according to described crowding, and the business relatively little to described crowding preferentially distributes the transmission band of described bus thus adjustment sends scheduling; With
Switch dispenser, it switches described switch according to the allocation result of the transmission band of described bus.
2. repeater according to claim 1, wherein,
Described congestion information represents that the business datum of each business in this repeater is by the time of delay required for this repeater,
Described congestion information comparing section, according to the time of delay of each business in the time of delay of each business obtained from described adjacent repeater and this repeater, obtains the information of the crowding of the flowing difficulty of each business represented quantitatively on the transmit path.
3. repeater according to claim 1, wherein,
Described crowding is the numerical value of the flowing difficulty of each business represented on the transmit path, and business more easily flows and gives less numerical value, and being more difficult to flow gives larger numerical value.
4. repeater according to claim 3, wherein,
The described transmission Dispatching adjustment portion business relatively little to described crowding relatively broadly guarantees the transmission band of described bus, the transmission band of described bus is first utilized, or pass through the utilized time of the transmission band guaranteeing described bus relatively longly, thus preferentially distribute the transmission band of described bus.
5. repeater according to claim 1, wherein,
The business datum of each business is split into bag and transmits on the bus,
Described repeater also comprises:
Bag waste part, it discards the bag of the described crowding business larger than predetermined threshold value from input buffer; With
Repeat requests portion, it retransmits to the buffer request as transmission source the bag gone out of use.
6. repeater according to claim 1, wherein,
Multiple output buffer, it is connected to the multiple outputs sending data to different buses; With
Route recycling notification unit, it, to the continuous print bag of the described crowding business larger than predetermined threshold value, distributes identical output buffer, and the recycling of setting to next repeater notice route that business is sent to.
7. repeater according to claim 1, wherein,
The Action clock of described bus can change,
Described repeater also comprises: Action clock control part, and described Action clock control part, when the business that described crowding is larger than predetermined threshold value is sent out, makes the Action clock of the bus being connected to described output improve.
8. repeater according to claim 1, wherein,
Described repeater also comprises: cooperation control stop, the Delay time larger than predetermined threshold value is there occurs in this repeater, described cooperation control stop only passes through the time of delay required for this repeater according to the described business datum in this repeater, decides described crowding.
9. a repeater, connects multiple bus in the integrated circuit possessing decentralized bus, and described repeater comprises:
Switch, it switches the combination of the input buffer receiving business datum and the output buffer sending described business datum;
Send Dispatching adjustment portion, it is using the crowding of the crowding of each business as the input buffer of the business datum of each business of storage, according to the crowding of described input buffer, determine the value of weight of the output buffer storing described business datum, according to the value of determined weight to the transmission band of described each traffic assignments bus thus adjustment sends scheduling; With
Switch dispenser, it switches described switch according to the allocation result of the transmission band of described bus,
Described transmission Dispatching adjustment portion to have received the input buffer sent request, by the probability connecting valve corresponding with the value of the weight giving each output buffer.
10. a repeater, connects multiple bus in the integrated circuit possessing decentralized bus, and described repeater comprises:
Described transmission band is divided into multiple time slot by described transmission Dispatching adjustment portion in time, distributes the time slot of the quantity specified by the value of described weight to each output buffer.
11. 1 kinds of repeaters, connect multiple bus in the integrated circuit possessing decentralized bus, and described repeater comprises:
Described transmission Dispatching adjustment portion utilizes the preassigned ratio of value by described weight, selects described output buffer probabilityly.
CN201180002247.1A 2010-03-05 2011-01-07 Relay device CN102449965B (en)
JP2010-049108 2010-03-05
JP2010049108 2010-03-05
PCT/JP2011/000034 WO2011108174A1 (en) 2010-03-05 2011-01-07 Relay device
CN102449965A CN102449965A (en) 2012-05-09
CN102449965B true CN102449965B (en) 2015-01-14
ID=44541846
CN201180002247.1A CN102449965B (en) 2010-03-05 2011-01-07 Relay device
US (1) US8670327B2 (en)
JP (2) JP4856790B2 (en)
CN (1) CN102449965B (en)
WO (1) WO2011108174A1 (en)
WO2013054497A1 (en) 2011-10-14 2013-04-18 パナソニック株式会社 Repeater, repeater control method, and computer program
WO2013073172A1 (en) * 2011-11-17 2013-05-23 パナソニック株式会社 Relay device, method for controlling relay device, and computer program
JP5024493B1 (en) * 2012-03-01 2012-09-12 富士ゼロックス株式会社 Integrated circuit and electronic equipment
CN103828312B (en) 2012-07-24 2017-06-30 松下知识产权经营株式会社 bus system and repeater
TWI531187B (en) * 2014-11-24 2016-04-21 財團法人工業技術研究院 Noc timing power estimating device and method thereof
US10355978B2 (en) 2017-06-19 2019-07-16 Hewlett Packard Enterprise Development Lp Calculating times to live for transaction requests
CN1516412A (en) * 2002-12-23 2004-07-28 阿尔卡特公司 Congestion control in optical burst exchange network
JP3716238B2 (en) * 2002-08-21 2005-11-16 エヌイーシーコンピュータテクノ株式会社 Arbitration control method for crossbar switch and arbitration control method for crossbar switch
FI92361C (en) * 1992-12-14 1994-10-25 Nokia Telecommunications Oy Procedure for controlling overload situations in a frame switching network and a node for a frame switching network
KR0133409B1 (en) * 1994-12-22 1998-04-27 Korea Electronics Telecomm Compensated upc/npc algorithm to generate qos in atm networks
US8005097B2 (en) * 2005-05-18 2011-08-23 Koninklijke Philips Electronics N.V. Integrated circuit and method of arbitration in a network on an integrated circuit
JP2007251777A (en) * 2006-03-17 2007-09-27 Toshiba Corp Ip communication method and ip communication system
KR100922965B1 (en) * 2006-10-10 2009-10-22 삼성전자주식회사 Network-on-chip apparatus and method for controlling dynamic frequency of the same
JP4757770B2 (en) * 2006-10-23 2011-08-24 株式会社Ｋｄｄｉ研究所 Communication route selection control device, wireless device, and communication route selection method
2011-01-07 JP JP2011532372A patent/JP4856790B2/en active Active
2011-01-07 WO PCT/JP2011/000034 patent/WO2011108174A1/en active Application Filing
2011-01-07 CN CN201180002247.1A patent/CN102449965B/en active IP Right Grant
2011-08-18 JP JP2011178907A patent/JP5400109B2/en active Active
2011-09-08 US US13/227,740 patent/US8670327B2/en active Active
JP5400109B2 (en) 2014-01-29
WO2011108174A1 (en) 2011-09-09
JP2011229192A (en) 2011-11-10
JPWO2011108174A1 (en) 2013-06-20
JP4856790B2 (en) 2012-01-18
US8670327B2 (en) 2014-03-11
US20120057467A1 (en) 2012-03-08
CN102449965A (en) 2012-05-09
Le et al. 2015 Decentralized signal control for urban road networks
US9391913B2 (en) 2016-07-12 Express virtual channels in an on-chip interconnection network
US20140105023A1 (en) 2014-04-17 System and Method for Assigning Paths for Data Flows Through a Wide-Area Network
US20120213230A1 (en) 2012-08-23 Pipeline scheduler with fairness and minimum bandwidth guarantee
EP1850538B1 (en) 2012-02-15 Radio communication device, communication route control device, communication route control method, and communication system