Multiprocessor system device

Description: TECHNICAL FIELD [Detailed description of the invention]

【0001】

[Technical field to which the invention belongs]

The present invention relates to a multiprocessor system device using a plurality of processors, and more particularly to a multiprocessor system device having a configuration in which a large number of processors and memory modules are connected by a multistage switch (multistage coupling network).

【0002】

[Conventional technology]

In a multiprocessor system device having a configuration in which a large number of processors and memory modules are connected by switches, if multiple packets are concentrated and collide with one switch, it takes time to process data and the data processing performance deteriorates. was there. For this reason, non-blocking networks, rearrangeable networks, and blocking networks that can reduce packet collisions in switches have been proposed.

【0003】

Non-blocking networks include cross-bar networks and Clos networks, and if scheduling is used to avoid line-out conflicts, collisions will not occur within the switch. The rearrangeable network can also eliminate collisions by scheduling the settings of each switch component. On the other hand, in a blocking network, conflicts cannot be eliminated by scheduling in general, but conflicts can be eliminated by scheduling for a certain access pattern.

【0004】

[Problems to be Solved by the Invention]

However, in a non-blocking network, the amount of hardware increases significantly with respect to the number of processors and memory modules, so that the cost becomes enormous when used in a large-scale system. In addition, although the hardware cost of the rearrangeable network is smaller than that of the non-blocking network, the time required for scheduling is long, and it is difficult to use it with a multiprocessor. Furthermore, conventional blocking network scheduling is a method of making collision-free only for the rearrangement of a certain access pattern, and what can actually be used in a multiprocessor is that array elements are arranged in a certain order. It was limited to special cases.

【0005】

The present invention has been made to solve the above problems, and the compiler can easily perform static scheduling for a large-scale system using a large number of multiprocessors and memory modules. An object of the present invention is to obtain a multiprocessor system device capable of realizing non-collision packet transfer for a general simultaneous access pattern.

【0006】

[Means for solving problems]

The multiprocessor system device according to the present invention is a multiprocessor system device in which a plurality of processors are connected to each other via a predetermined network, and is a plurality of processors including a processor, a memory unit, and an interface unit that interfaces with the network. A multi-stage coupling network having a hierarchical structure composed of an element and a multi-stage switch for connecting each processor element is provided, and each processor element and the multi-stage coupling network have a hierarchical structure based on a predetermined number. It is clustered and transfers packets between processor elements based on a schedule statically scheduled in advance using a switch status table that shows the status of each switch in the multistage coupled network generated at each time. is there.

【0007】

Further, the multi-stage coupled network having the above-mentioned hierarchical structure includes an upstream coupled network that transfers packets from the lower layer to the upper layer and a downstream coupled network that transfers packets from the upper layer to the lower layer. You may do so.

【0008】

Specifically, the switch status table shows the packet information holding the output terminal, the packet information requesting the output terminal, and the status of the output terminal for each switch. It is made up of.

【0009】

Further, in each of the above processor elements and the multi-stage coupling network, when a plurality of packets request the output terminal of one switch at the same time, arbitration is performed by a predetermined method, and the packet that cannot hold the output terminal is released. Packets are transferred between processor elements according to a schedule scheduled to request the output terminal in the switch status table at another time.

【0010】

On the other hand, when the multi-stage coupled network is a cross network, each processor element and the multi-stage coupled network are predetermined when a plurality of packets request the output terminal of one switch at the same time at the time of packet transfer in one cross network. Packets that were arbitrated by the method described in the above method and could not hold the output terminal are forwarded with packets between processor elements according to a schedule scheduled to request the output terminal of another switch that does not request the packet. You may do it.

【0011】

Specifically, the compiler performs scheduling for each of the above packets in advance.

【0012】

BEST MODE FOR CARRYING OUT THE INVENTION

Next, the present invention will be described in detail based on the embodiments shown in the drawings. First Embodiment. FIG. 1 is a schematic block diagram showing an example of a multiprocessor system apparatus according to the first embodiment of the present invention. In FIG. 1, the multiprocessor system apparatus 1 is formed by connecting tens to thousands of processor elements PE by a multistage interconnect network (MIN) having a hierarchical structure. Note that FIG. 1 shows the case of three layers as an example.

【0013】

The multiprocessor system apparatus 1 is composed of clusters D0 to Dx (x is an integer of x> 0) and an interconnection network E0 that connects between the clusters D0 to Dx. Further, each cluster D0 to Dx is composed of clusters A0 to An (n is an integer of n> 0) and a coupling network C0 to Cx that connects the clusters A0 to An, respectively. Further, each cluster A0 to An is composed of processor elements PE0 to PEm (m is an integer of m> 0) and a coupling network B0 to Bn for connecting between the processor elements PE0 to PEm.

【0014】

That is, in the multiprocessor system device 1, the network is divided into a hierarchical structure in order to combine hundreds to thousands of processor element PEs, and dozens to dozens of processor element PEs are converted into a medium-sized multiprocessor system device. A plurality of switches called a multistage coupling network to be adopted are connected over several stages, and a transfer path is formed to the target processor element PE by switching the switches in the middle.

【0015】

Since the processor elements PE0 to PEm have the same configuration, the processor elements PEi (i = 0 to m) will be described as an example. FIG. 2 is a schematic block diagram showing a configuration example of the processor element PEi. In FIG. 2, the processor element PEi is composed of a processor PU, a memory ME, and a network interface NI. The processor PU and memory ME are connected, and the processor PU and memory ME are further connected to the corresponding coupled network Bi via network interface NI.

【0016】

In such a configuration, the configuration in which the processor elements in the same cluster in each cluster A0 to An are connected is set to level 0, the configuration in which the connection is made between each cluster A0 to An is set to level 1, and each cluster D0 to is set. Level 2 is the configuration for connecting between Dx. That is, each cluster A0 to An is level 0, each cluster D0 to Dx is level 1, and the connection network E0 is level 2, forming three layers of levels 0 to 2. In other words, each cluster D0 to Dx and the coupling network E0 can be cluster F0, and cluster F0 is level 2.

【0017】

Here, Fig. 3 shows an example of a Clos network, which is one of the common multi-stage coupling networks. In the cross network, the first stage is called the distributor, the second stage is called the exchanger, and the third stage is called the concentrator because of the role of the switch in each stage. Note that FIG. 3 shows an example in which a 4-input 4-output switch is used and each stage is configured by the four switches.

【0018】

A multi-stage coupled network consists of all processor element PEs depending on the number of connected nodes, that is, the number of processor element PEs (m + 1) in a multiprocessor system unit and the number of input or output terminals in the component switch. The number of stages in which a transfer path can be formed is log._kIt becomes (m + 1). In FIG. 3, the opposing processor element PEs indicate the same processor element, so m + 1 = 16 and k = 4.

【0019】

For this reason, a transfer path to all processor element PEs is formed by passing through the switch in two stages, but in order to obtain a larger transfer capacity and provide redundancy in the transfer path, a cross network is formed by the three-stage switch. It is configured. That is, one input terminal of the switch element forming the distributor and one output terminal of the switch element forming the concentrator are connected to one processor element PE correspondingly.

【0020】

Such a multi-stage coupling network can be classified into three types, non-blocking, rearrangeable, and blocking, according to the number of input / outputs and the number of stages of the constituent switches and the number of constituent switches. Non-blocking can statically set a transfer route that does not cause a collision of transferred data, and rearrangeable is a non-collision route by resetting the transfer route when a collision of transferred data occurs. Can be formed. In blocking, when a collision of transferred data occurs, a non-collision route cannot be formed even if the transfer route is reset. For example, in the cross network shown in FIG. 3, if the number of input terminals or output terminals of the constituent switches is k and the number of switches in the intermediate stage is p, non-blocking and p k when p> (2k-1). When is, it is rearrangeable, and when p <k, it is blocking.

【0021】

On the other hand, connecting hundreds to thousands of processor element PEs in a multi-stage coupled network is difficult and impractical in terms of hardware. Therefore, several processor element PEs are connected to a crossbar switch to form a level 0 network, and dozens to dozens of processor element PEs are connected by a multi-stage coupling network using the crossbar switch as an input. And make it a level 1 network. Further, an expansion stage for connecting the plurality of multi-stage coupling networks is formed by a plurality of switches to form a level 2 network.

【0022】

Similarly, scalability can be obtained by interconnecting large-scale system devices by adding hierarchical expansion stages according to the scale of the system devices and expanding to a hierarchical structure with a multi-stage coupled network as the basic network. Can be done. In this way, the network of each layer can be regarded as one subnetwork, so it is called the network NWs of level s (s is an integer of s> 0) according to each layer level.

【0023】

As such an example, a hierarchical network in which a cross network is used as a basic multi-stage connected network will be described. 4 and 5 are diagrams showing an example of a hierarchical sub-network in a cross network that is a basic network, FIG. 4 is an example of a level 0 network in the cross network, and FIG. 5 is a diagram in the cross network. Shows an example of a Level 1 network in. Note that FIGS. 4 and 5 show four clusters A0 to A3 having four processor elements PE0 to PE3 as an example.

【0024】

In FIGS. 4 and 5, switch elements SD0 to SD3 serve as cross-net distributors, switch elements SE0 to SE3 serve as cross-net exchangers, and switch elements SC0 to SC3 serve as cross-net concentrators. There is. The switch elements SD0 to SD3, SE0 to SE3, and SC0 to SC3 each form a switch element with 4 inputs and 4 outputs.

【0025】

Switch elements SD0 and SC0 form cluster A0 with each connected processor element PE0 to PE3, and switch elements SD1 and SC1 form cluster A1 with each connected processor element PE0 to PE3. Similarly, switch elements SD2 and SC2 form cluster A2 with each connected processor element PE0 to PE3, and switch elements SD3 and SC3 form cluster A3 with each connected processor element PE0 to PE3. ..

【0026】

When the switching elements SE0 to SE3 forming the coupling network C0 are switched straight to the same output terminal as the input terminal as shown by the arrow in FIG. 4, a level 0 network is formed and the same cluster in clusters A0 to A3 is formed. Data transfer within is realized. On the other hand, when the switching elements SE0 to SE3 forming the coupling network C0 are switched by crossing the input terminals to different output terminals as shown by the arrows in FIG. 5, the second stage switch forming an exchanger is formed. Elements SE0 to SE3 form a level 1 network, and data transfer between different clusters in clusters A0 to A3 is realized.

【0027】

In this way, the second-stage switch elements SE0 to SE3 that form the exchanger operate as a level 1 network when they serve as switches, and level 0 when they do not serve as switches. It works as a network. That is, there are two sub-networks, a level 0 network and a level 1 network, in one cross-network.

【0028】

Next, the expansion stage connecting the cross networks, that is, the coupling network E0 in FIG. 1 will be described. FIG. 6 is a diagram showing an example of the multiprocessor system apparatus 1 that realizes hierarchical clustering. Note that in FIG. 6, for the sake of clarity, a hierarchical clustering consisting of four radixes, that is, four clusters D0 to D3 having four clusters A0 to A3 having four processor elements PE0 to PE3. Is shown as an example, and the processor element is omitted.

【0029】

In FIG. 6, up to 16 processor elements are directly connected by a cross network to form clusters D0 to D3, respectively, and the cross networks, that is, clusters D0 to D3 are added to each other in a level 2 network, which is an expansion stage. Mutual coupling is performed using switch elements SEa0 to SEa3 that form an exchanger. The switch elements SEa0 to SEa3 each form a switch element having 4 inputs and 4 outputs, and form a coupling network E0 in FIG. In this case, the switch elements SE0 to SE3 in each cross network are added with 1 input and 1 output for connecting to the switch elements SEa0 to SEa3, resulting in 5 inputs and 5 outputs.

【0030】

When combining more processor elements, a level 3 exchanger is added as a level 3 network for interconnecting level 2 networks. That is, there are a plurality of clusters having all the configurations shown in FIG. 1, and a coupling network for connecting the clusters is provided to form four layers. In this way, when the number of layers is R, the number N of processor elements to be combined is calculated from the number of processor elements (m + 1) connected to the multi-stage combined network, which is the basic network, as shown in equation (1) below. Become. N = (m + 1) × k^(R-1)..................(1) 【0031】

Further, in the multiprocessor system device 1 of FIG. 6, since m + 1 = k × k, the above equation (1) becomes the following equation (2). N = k × k × k^(R-1)= k^{(R + 1)}..................(2) 【0032】

Next, a static scheduling method for a multi-stage connected network having the above-mentioned hierarchical structure will be described. As a prerequisite for static scheduling in a multi-stage coupled network with a hierarchical structure, it is known that all data transfers are completely statically analyzed by the scheduler in the compiler, and that packets are transferred at what timing and where. Data access shall be scheduled on the basis of the above.

【0033】

In order to schedule statically, it is necessary to grasp the state of the switch at each time, and for each output terminal of each switch element, "current time", "holding port", "holding clock", "waiting for port request". Create a switch state table consisting of items such as "matrix" and "state". The "holding port" is an input port number holding the output terminal, and the "holding clock" is the number of cycles (clocks) held. The "port request queue" is a queue for entering the input terminal number requesting this output terminal, and the "state" indicates the status of this output terminal and is released (RELEASED) and held (HOLD). ) There are two states.

【0034】

FIG. 7 is a diagram showing an example of a switch state table. Note that FIG. 7 shows an example of a 4-input 4-output switch element. FIG. 7 shows the state of each switch when the current time is 157843, and the output terminal # 0 is held by the input terminal # 3 for 2 clocks. Therefore, during these two clocks, packets at other input terminals cannot acquire output terminal # 0. Moreover, although the output terminal # 1 is open, each packet of the input terminals # 0 and # 2 issues a request for acquisition of the output terminal # 1. Although it is also open at output terminals # 2 and # 3, the packet at input terminal # 1 issues a request to acquire output terminal # 2.

【0035】

A switch status table as shown in FIG. 7 is created for all switches in each switch element, and the scheduler in the compiler performs scheduling based on the switch status table. When there are two or more acquisition requests in the port request queue as shown in output terminal # 1 in Fig. 7, the packets are arbitrated based on the priority of the packets, and the access of the packets that lost the arbitration is shifted to a later time. Is done.

【0036】

On the other hand, the packet that wins the arbitration is described in the holding port and the holding clock by acquiring the output terminal, and is described in the holding port until the holding clock becomes 1, and the state is held and the switch state table is created. To. For this reason, the switch status table for all access times is finally required, but the switch status table required when scheduling the access packet at a certain time is later than that time. Therefore, the switch status table of the time before the time can be discarded.

【0037】

Next, the static scheduling method using the switch state table performed by the compiler will be described. In addition, the set Uts of packets issued at a certain time Ts is expressed as Uts = p0, p1, ......, pN, and in each process of the static scheduling method below, all unless otherwise specified. It is done by the compiler.

【0038】

First, for the packet pj (j = 0 to N), which is an element of the packet set Uts, a switch status table in the switch element of the corresponding distributor is created according to the packet header (routing tag, etc.). Also, set the current time in the switch status table to Ts. Next, when the switch status table in the switch element of the distributor is created for all packets p1 to pN, arbitration is performed for the packets of the input terminal in the port request queue in the switch status table. Packets that have lost arbitration are excluded from the packet set Uts and added to the packet set Uts + 1 issued at the next time Ts + 1.

【0039】

On the other hand, for the packet that has won the arbitration, the switch status table of the acquired output terminal is created or rewritten for the number of holding clocks. When the status for all switches in each switch element is determined, the switch status table for the corresponding next-stage switch is created or rewritten according to the output. The switch status table at this time shows the switch status when the current time is advanced by one. Such processing is repeated, and the packet arriving at the destination is removed from the packet set Uts each time, and such processing is repeated until the packet set Uts becomes an empty set.

【0040】

Packets issued at a certain time Ts by the above operation are adjusted and scheduled without collision. Also, if there are two packets issued from the same node in the packet set by the above operation, one of them will be put in the packet set at the next time, so if the packet access is concentrated. , The packet set will shift one by one. Packet transfer can be completely scheduled statically by performing the same processing as the scheduled time Ts for all times.

【0041】

8 to 10 are flowcharts showing a static scheduling method using a switch state table, and the flow of static scheduling processing will be described in a little more detail with reference to FIGS. 8 to 10. In FIGS. 8 to 10, the set Uts of packets issued at a certain time Ts is represented as Uts = p0, p1, ......, pN. Further, the processing performed in each flow of FIGS. 8 to 10 is performed by the compiler unless otherwise specified.

【0042】

In FIG. 8, first, the packet set Uts issued at time Ts is entered into the input terminal of each switch in the first stage (step S1). As for the number of stages of the multi-stage coupling network, the numbers are assigned in ascending order from 1 from the input side. Next, set the number of stages STcur of the switch currently being focused on to 1, and set the highest number of layers Rcur currently being processed to 1 (step S2). After that, scheduling is performed for each switch with the number of stages STcur (step S3). Check whether each switch of the number of stages STcur has a link to the lower layer (step S4), and if it exists (YES), set the number of stages STcur to the number of stages in the lower layer and set the current time Tcur to 1. Proceed (step S5), then return to step S3.

【0043】

On the other hand, in step S4, if the link to the lower layer does not exist (NO), it is checked whether or not the link to the upper layer exists in each switch of the number of stages STcur (step S6), and it exists. If so (YES), increase the highest number of layers Rcur currently being processed by 1 and set the number of stages STcur of the switch currently being focused on to the same number as the number of layers Rcur (step S7), and then step S3. Return to. If the link to the upper layer does not exist in step S6 (NO), this flow ends.

【0044】

Here, the scheduling process shown in step S3 of FIG. 8 will be described in a little more detail using the flowchart of FIG. In FIG. 9, first, for all switch elements belonging to the number of stages STcur, input to the port request queue of the switch status table of the corresponding time Tcur based on the destination output terminal number of the packet entered in the input terminal. Enter the terminal number (step S11). Next, each switch element belonging to the number of stages STcur is numbered from 0 in order, and the switch element number SWcur of interest is set to 0 (step S12).

【0045】

After that, the switch element of SWcur is scheduled according to the switch status table (step S13), and it is checked whether or not the number of stages STcur currently being focused on is the final stage (step S14). In step S14, if it is the final stage (YES), the packet entered in the output terminal is deleted from the packet set Uts as an arrival packet (step S15). Further, the switch element number SWcur of interest is advanced by one (step S16), and it is examined whether or not the switch element number SWcur is less than the total number of switches Nst of the number of stages STcur (step S17).

【0046】

If the total number of switches is less than Nst in step S17 (YES), this flow ends and proceeds to step S4 in FIG. If the total number of switches is not less than Nst in step S17 (NO), the process returns to step S13. If the packet is not in the final stage in step S14 (NO), the packet entered in the output terminal is entered in the input terminal of the switch in the next stage to which the packet is connected (step S18), and the process proceeds to step S16.

【0047】

Here, the scheduling process shown in step S13 of FIG. 9 will be described in a little more detail using the flowchart of FIG. In FIG. 10, the output terminal number POcur of interest in the switch status table is set to 0 (step S21), and it is checked whether or not the output terminal number POcur has a port request queue (step S22). In step S22, if there is a port request queue (YES), arbitrate based on the priority in the packet header (step S23), select one packet from the port request queue (step S24), and Check whether the packet has won the arbitration (step S25).

【0048】

If the selected packet wins the arbitration in step S25 (YES), the time Th of the switch status table to write the packet is set to the time Tcur (step S26). After that, the input terminal number of the packet is written to the holding port of the output terminal number acquired in the switch status table at time Th (step S27), and the number of clocks required for the packet to pass is written to the holding clock (step). S28). Next, the number of clocks written to the holding clock is reduced by one, the current time Th is advanced by one (step S29), and it is checked whether or not the number of clocks written to the holding clock is 0 (step S30). In step S30, if it is not 0, it returns to step S27, if it is 0, it returns to (NO), and it returns to step S22.

【0049】

On the other hand, in step S25, when the extracted packet loses the arbitration (NO), the lost packet is removed from the packet set Uts, and in addition to the packet set Uts + 1 at the next time, the issuance of subsequent packets of the same node is duplicated. The packet set is shifted one by one until it disappears (step S31), and the process returns to step S22. Also, in step S22, if there is no port request queue (NO), advance the output terminal number POcur by one (step S32), and check whether the output terminal number POcur is less than the number of output terminals Nport of the switch. (Step S33). If the number of output terminals is less than Nport (YES) in step S33, the process returns to step S22, and if the number of output terminals is not less than Nport (NO), this flow ends and the process proceeds to step S14 in FIG.

【0050】

The above scheduling method will be described with reference to specific examples. For example, in the scheduling of packets at the access issue time Ts, a case where a switch belonging to a hierarchical network at time 15000 is in the situation shown in FIG. 11 will be described. In FIG. 11, a switch element having 5 inputs and 5 outputs constituting the exchanger is shown as an example. In FIG. 11, the output terminal # 2 is held by the input terminal # 4 for only two clocks. Packets at the input terminal enter the port request queue at the appropriate output terminal by means of a routing tag. The switch state table of FIG. 11 shows the state before scheduling is performed, and the compiler performs arbitration based on the switch state table of FIG. 11 and creates the switch state table shown in FIG.

【0051】

In FIG. 11, it is the output terminal # 1 that has line conflict, and in this case, the compiler arbitrates according to the priority in the header of the packet. If the packet at input terminal # 1 wins the arbitration, the packet at input terminal # 0 that loses arbitration is removed by the compiler from the packet set Uts element at the access issue time Ts, and the packet set at the next issue time. In addition to Uts + 1, packets at input terminal # 0 are removed from the entry for output terminal # 1 as shown in Figure 12. The packet of input terminal # 1 that has won the arbitration is put into the holding port of output terminal # 1 by the compiler, 1 is written to the holding clock of output terminal # 1, and then the packet of output terminal # 1 is written. The state is set to hold.

【0052】

Next, at the output terminal # 2, the state is already set to hold as shown in FIG. 11, and 2 clocks are held by the packet of the input terminal # 4. Therefore, the packet of the input terminal # 3 requesting the output terminal # 2 is removed from the elements of the packet set Uts by the compiler in the same way as the packet that lost the arbitration, and the packet set Uts of the next issue time is removed. In addition to +1 the packet at input terminal # 3 is removed from the entry for output terminal # 2 as shown in Figure 12. At output terminal # 4, the state is set to release as shown in Fig. 11, and there are no competing input terminal packets. Therefore, the packet at input terminal # 2 is determined by the compiler to be output terminal # as shown in Fig. 12. When it is put into the holding port of 4, 1 is written to the holding clock of output terminal # 4, and the state of output terminal # 4 is set to hold.

【0053】

In this way, when the arbitration is completed and the switch status table shown in FIG. 12 is created, the current time is advanced by one by the compiler, and the packet that has acquired the output terminal is the input of the switch connected to the output terminal. It is entered in the terminal, and the packet of output terminal # 4 is entered in the input terminal of the switch in the upper layer. The entered packet is entered into the port request queue by the compiler in the same manner as described above, and the arbitration and output terminal acquisition operations are repeated until the destination is reached. In the above description, a case where a cross network is used as a multi-stage connecting network having a hierarchical structure is shown as an example. However, the present invention is not limited to this, and a hierarchy is used by using a general multi-stage coupling network such as an Omega network, a Baseline network, a Delta network, and a "Generalized Cube". It can also be realized by structuring.

【0054】

Here, in the above scheduling method, the packet that lost the arbitration is added to the packet set at the next and subsequent times. On the other hand, when packet transfer is performed within one cross network, when scheduling is performed for the switch element of the level 1 exchanger, the packet that lost the arbitration is transferred to the other switch element of the level 1 exchanger. You may want to use a free switch to transfer. The scheduling method in this case will be described by taking one cross network in FIG. 13, that is, cluster D0 as an example.

【0055】

Due to the nature of the cross network, the route to the destination in the cross network is determined by the second stage exchanger and the third stage concentrator, so the first stage distributor may choose any output. Since the transfer performance of the cross network largely depends on the scheduling performance of the second-stage exchanger, the transfer is performed to the output terminal according to the scheduling result of the second-stage exchanger. Therefore, the second-stage exchanger is scheduled first, and then the first-stage distributor is scheduled.

【0056】

The transfer performance of the cross network is very important because it depends on the scheduling performance of the second stage exchanger. In addition to the switch status table as described above, the cluster-specific access list AL (Access List) and the cluster-specific free port counter VPC (Varid Port Counter) are used for scheduling in order to make effective use of the second-stage exchanger. Access list by cluster (hereinafter referred to as access list) AL is a list that records which level 0 cluster the packets output from each level 0 cluster are heading to, and is a free port counter by cluster (free port counter by cluster). The VPC (hereinafter referred to as the free port counter) is a counter that indicates how many output terminals are connected to each level 0 cluster.

【0057】

Here, a method of creating an access list AL and a free port counter VPC performed by the compiler will be described with reference to FIG. Also in FIG. 13, a case where a hierarchical structure clustering composed of four clusters D0 to D3 having four clusters A0 to A3 having four processor elements PE0 to PE3 is realized is taken as an example. Shown. Cluster D0 is composed of clusters A0 to A3 and switch elements SE0 to SE3 that form an exchanger. Further, the clusters A0 to A3 are formed from the corresponding switch elements SD0 to SD3 and SC0 to SC3 and the processor elements PE0 to PE3, respectively.

【0058】

In such a configuration, first, a method of creating an access list AL will be described. The compiler examines the headers of all packets transferred from the switch element SD0 to the switch elements SE0 to SE3, and writes the cluster number of the destination in each packet to the access list AL. For example, if each packet from switch element SD0 has two elements, clusters A1 and A3, as routing tags for switch elements SE0 to SE3, cluster A0 in the access list AL will have cluster numbers A1 and A3. Is written.

【0059】

Next, a method of creating a free port counter VPC will be described. Based on the created access list AL, the compiler calculates the count values CT0 to CT3, which indicate how many free output terminals are assigned to each cluster A0 to A3, by associating them with the following equation (3). CTg = (number of switches in the second stage)-(number of elements in the access list by cluster) ......... ......... (3) In the above equation (3), g = 0 to 3. For example, the count value CT0 for cluster A0 is CT0 = 4-2 = 2.

【0060】

Next, the scheduling algorithm performed by the compiler using the access list AL and the free port counter VPC will be described. However, the current access list is ALcur, and the access list after arbitration is ALnew. First, the compiler preferentially allocates packets in the cluster with the smallest number of elements in the current access list ALcur, starting with switch element SE0. Next, the compiler gives the lowest priority to the elements of one cluster (destination cluster number) in the access list ALcur that have the same destination as the packet sender, and if they are not the same, for example, the destination cluster. Assign in ascending order of number. It should be noted that the cluster numbers of the destinations may be assigned in ascending order.

【0061】

Further, when the free port counter corresponding to the element of the access list ALcur is 0, the compiler inevitably becomes unschedulable, removes the element from the packet set at the current time, and adds it to the packet set at the next time. When a conflict occurs in such packet allocation, the compiler mediates by packet priority, round robin method, or the like. The packet that wins the arbitration is removed from the elements of the access list ALcur by the compiler, and the count value indicating the number of terminals in the corresponding free port counter VPC is decremented. After this, the compiler enters the input terminal number of the packet that won the arbitration in the switch status table of the corresponding output terminal, and puts a processed check in the cluster that won the arbitration.

【0062】

The compiler then removes the packets that lost the arbitration and the packets that specify the same destination cluster as the packets that won the arbitration from the current time access list ALcur and moves them to the next time access list ALnew. Let me. The compiler performs such processing for all clusters A0 to A3 in the access list ALcur until it checks the processed status. When all clusters A0 to A3 in the access list ALcur are checked, the compiler moves all the elements of the access list ALcur to the access list ALnew, and uses the access list ALnew as ALcur to perform the above series of processing for each cluster. Do until all the elements are gone.

【0063】

FIG. 14 is a flowchart showing a scheduling method in the cross network using the access list AL and the free port counter VPC, and the flow of the scheduling process in the cross network will be described in a little more detail with reference to FIG. The processing performed in each flow of FIG. 14 is performed by the compiler unless otherwise specified. In FIG. 14, first, among the clusters UCL in which the access list AL is not empty among the level 0 clusters in the cross network, the cluster with the fewest elements is set to the cluster number CLcur currently being focused on (step S41). ). If there are multiple clusters with the smallest number of elements, select one and set it to the cluster number CLcur.

【0064】

Next, select one packet that is an element of the access list ALcur in the cluster with cluster number CLcur (step S42), and check whether the free port counter VPC of the destination cluster in the selected packet is 0 (step). S43). In step S43, if the free port counter VPC is 0 (YES), the selected packet is removed from the packet set Uts and the access list ALcur, shifted to the packet set Uts + 1 at the next time, and at a time after time Ts. The issued packet is shifted to a packet set at a later time until there is no duplication, and the process returns to step S42.

【0065】

Also, in step S43, if the free port counter VPC is not 0 (NO), the selected packet is assigned to the output terminal of the switch element with the lowest number among the switch elements SE0 to SE3 that have free output terminals ( Step S45). Next, in the cluster set UCL, the access list ALcur is checked for the existence of clusters having conflicting packets (step S46), and if there are clusters having conflicting packets (YES), the conflicting packets are removed from the access list ALcur. In addition to the access list ALnew (step S47), the process returns to step S46.

【0066】

Also, in step S46, if there are no clusters with conflicting packets (NO), the count value of the corresponding free port counter VPC is decremented by one, and the cluster number CLcur that is currently of interest is deleted from the cluster set UCL (step). S48). Next, it is checked whether or not the cluster set UCL is an empty set (step S49), and if it is not an empty set (YES), the process returns to step S41. Further, in step S49, in the case of an empty set (NO), all packets of the access list ALcur are moved to the access list ALnew, the access list ALnew is set as ALcur, and the cluster whose access list is not empty is set as an element of the cluster set UCL. (Step S50). Next, it is checked whether or not the cluster set UCL is an empty set (step S51), if it is an empty set (YES), this flow ends, and if it is not an empty set (NO), the process returns to step S41.

【0067】

The processing by such a compiler will be described with reference to a concrete example. FIG. 15 is a diagram showing an example of the initial state of the access list ALcur, and FIG. 16 is a diagram showing an example of the initial state of the free port counter VPC. The case shown in FIGS. 15 and 16 will be described as an example. First, the compiler processes the packet whose destination is cluster A2 in cluster A1 which has the smallest number of elements in the access list ALcur, and deletes it from the access list ALcur. In addition, the compiler reserves output terminal # 2 of switch element SE0, which forms a level 1 exchanger, and records it in the switch status table.

【0068】

Next, the compiler decrements the count value of output terminal # 2 in the free port counter VPC by 1, and puts a processed check in cluster A1 of the access list ALcur. On the other hand, since the counter value of output terminal # 2 in the free port counter VPC is 0, the compiler deletes the packet whose destination in cluster A3 is cluster A2 in the access list ALcur and re-forwards it. Move to the access list ALnew at the time of.

【0069】

Next, the compiler records the packet whose destination is cluster A0 in cluster A3, which has the next smallest number of elements in the access list ALcur, in the switch status table by securing output terminal # 0 of switch element SE0. Furthermore, the compiler decrements the count value of output terminal # 0 of the free port counter VPC by 1, and puts a checked check in cluster A3 of the access list ALcur.

【0070】

Similarly, in the access list ALcur, the compiler deletes packets destined for cluster A0 in cluster A2 and moves them to the access list ALnew at the next time for reforwarding. At this point, the number of elements in clusters A0 and A2 is both two, so the compiler shall arbitrate and process cluster A0 first. The compiler assigns a packet whose destination of cluster A0 in the access list ALcur is cluster A1 to output terminal # 1 of switch element SE0, records it in the switch status table, and deletes it from the access list ALcur.

【0071】

Furthermore, the compiler decrements the count value of output terminal # 1 in the free port counter VPC by 1, and puts a processed check in cluster A0 of the access list ALcur. After this, the compiler deletes the packet whose destination in cluster A2 is cluster A1 in the access list ALcur and moves it to the access list ALnew at the next time for reforwarding. Finally, the compiler processes packets destined for cluster A3 in cluster A2 that have been processed and unchecked in the same way.

【0072】

Furthermore, the compiler decrements the counter value of the output terminal # 3 of the free port counter VPC by 1, puts a checked check in cluster A2 of the access list ALcur, and finishes the processing for the access list ALcur. FIG. 17 shows the access list ALnew after processing each packet of clusters A0 to A3 one by one, and FIG. 18 shows the free port counter VPC after processing each packet of clusters A0 to A3 one by one. ing.

【0073】

Next, the compiler performs the same processing as above for the new access list ALcur. At this time, the packet is assigned to the output terminal of the switch element SE1 depending on the compiler. Therefore, each time the access list ALnew becomes ALcur, the switch element assigned by the compiler shifts by one. Finally, the route of the packet scheduled by the compiler is as shown by the arrow in FIG.

【0074】

In the scheduling by the above compiler, if multiple packets request the output terminal of one switch at the same time, arbitration is performed, and the packet for which the output terminal could not be secured is the switch status table at the next time. The case where the output terminal is requested has been described as an example, but this is an example, and the packet for which the output terminal could not be secured is of another time such as the switch status table of the previous time. The desired output terminal may be requested in the switch status table.

【0075】

As described above, in the multiprocessor system apparatus according to the first embodiment, each processor element is connected by a multistage coupling network having a hierarchical structure, and a compiler is previously used for each switch constituting the multistage coupling network. Static scheduling was performed to emulate a multi-stage coupled network with a hierarchical structure without collision. From this, it is possible to manage all packet waits that were dynamically performed at the time of packet collision at compile time, so it is possible to significantly reduce the hardware such as FIFO required for packet dynamic waits. It is possible to prepare a network environment for performing non-synchronous execution between processors. Further, since non-synchronous execution can be enabled in the multiprocessor system device, the hardware overhead for synchronization can be reduced, and the efficiency of parallel processing can be improved.

【0076】

In addition, when packet transfer is performed within one cross network using a cross network as the basic network of a multi-stage coupled network with a hierarchical structure, the arbitration was lost when scheduling for the switch element of the level 1 exchanger was performed. Packets may be forwarded using a free switch in another switch element of the level 1 exchanger. By doing so, the packet transfer efficiency can be improved.

【0077】

Second Embodiment. In the first embodiment described above, the second level level 1 exchanger for connecting the cross networks, that is, the respective switch elements SE0 to SE3 in each cross network in FIG. Since the structure is such that all packets are concentrated in, hot spots may be formed and the performance may be significantly reduced. For this reason, a level 1 concentrator may be added as a downstream switch for delivering from the upper layer to the lower layer, and such a switch is used as the second embodiment of the present invention. The schematic block diagram showing an example of the multiprocessor system apparatus in the second embodiment and the schematic block diagram showing the configuration example of the processor element are the same as those in FIGS. 1 and 2, and are omitted. To do.

【0078】

20 and 21 are diagrams showing an example of a multiprocessor system apparatus that realizes hierarchical clustering according to the second embodiment of the present invention. FIG. 20 shows the uplink connection between each cross network and the extended network, and FIG. 21 shows the downlink connection between each cross network and the extended network. Note that, in FIGS. 20 and 21, the same components as those in FIG. 6 are indicated by the same reference numerals, and the description thereof will be omitted here and only the differences from FIG. 6 will be described. Further, also in FIGS. 20 and 21, a case where a hierarchical structure cluster consisting of four clusters D0 to D3 having four clusters A0 to A3 having four processor elements PE0 to PE3 is realized. It is shown as an example, and the processor element is omitted.

【0079】

The difference from FIG. 6 in FIGS. 20 and 21 is that the level 1 exchanger has a packet delivery function (upstream) to the upper layer network and a packet delivery function (downstream) to the lower layer network. A level 1 concentrator consisting of switching elements SCb0 to SCb3 is added as a downstream switch that delivers packets from the upper layer to the lower layer, and the upstream that delivers packets from the lower layer to the upper layer is the first. Similar to the first embodiment, it is performed by a level 1 exchanger composed of switching elements SE0 to SE3 in each cluster D0 to D3.

【0080】

When a processor PU in a certain processor element exchanges data with a processor PU of another processor element PE, it communicates by writing data to the memory ME of the other processor element PE. The processor PU of the processor element in which the data is written in the memory ME establishes data communication by reading the data written in the memory ME.

【0081】

Hereinafter, the flow of data communication between processor elements will be described with reference to FIG. In FIG. 22, a case where data is transferred from the processor element PEa to the processor element PEb will be described as an example. First, in the processor element PEa, the address and the transfer data are sent from the processor PUa to the network interface NIa.

【0082】

Next, the network interface NIa generates a packet based on the input address and sends the packet to the hierarchical multi-stage network MIN. The input packet is input to the network interface NIb of the processor element PEb via the multi-stage coupling network MIN having a hierarchical structure, and the network interface NIb disassembles the input packet and writes it to the memory MEb. The processor PUb reads the data written in the memory MEb and completes the data communication.

【0083】

Here, a case where the packet sent to the level 1 exchanger is processed in the same cross network, that is, the destination is in the same cross network will be described with reference to FIG. In FIG. 3, a packet is sent from the processor element to the first-stage distributor, switched by the first-stage distributor, and sent to the second-stage level 1 exchanger. The packet sent to the level 1 exchanger is switched by the level 1 exchanger to the final level 0 concentrator and sent out.

【0084】

Further, the packet sent to the level 0 concentrator is appropriately switched by the level 0 concentrator and sent to the processor element of the destination to complete the data communication in the hierarchical multi-stage coupling network MIN. The packet sent to the destination processor element is stored in the memory of the processor element as described with reference to FIG.

【0085】

Next, the case where the packet sent to the level 1 exchanger is processed by another cross network, that is, the destination is another cross network will be described with reference to FIG. 23. In FIG. 23, a case where data is transferred from the processor element PEa to the processor element PEb will be described as an example. Packets sent to the switch element SE1 that forms the level 1 exchanger are switched to the output terminal to the expansion stage by the switch element SE1 and are switched to the upper layer exchanger until they enter the cluster of the same level, in this case the level. It is sent to the switch element SEa1 that forms the exchanger of 2.

【0086】

Packets that enter the same cluster are switched to the appropriate output and go down the hierarchy. For example, in the case of FIG. 23, the packet sent to the switch element SEa1 is forwarded by the switch element SEa1 to the switch element SCb1 which is a downstream level 1 concentrator. Packets forwarded to switch element SCb1 are properly switched by switch element SCb1 and sent to processor element PEb, which is the processor element of the destination. In this way, data communication in the hierarchical multi-stage coupled network MIN is completed. In such a configuration, the static scheduling method of the multi-stage coupled network having a hierarchical structure is the same as that of the first embodiment, and thus the description thereof will be omitted.

【0087】

As described above, the multiprocessor system apparatus according to the second embodiment adds a level 1 concentrator composed of switching elements SCb0 to SCb3 as a downstream switch for delivering from the upper layer to the lower layer, and starts from the lower layer. Upstream that delivers packets to the upper layer is performed by a level 1 exchanger consisting of switching elements SE0 to SE3. From this, it is possible to prevent the formation of hot spots by preventing all packets from being concentrated in the level 1 exchanger for connecting between cross networks, and to improve the performance of the multiprocessor system device.

【0088】

[Effect of the invention]

As is clear from the above description, according to the multiprocessor system apparatus of the present invention, each processor element and the multistage coupling network are clustered in a hierarchical structure based on a predetermined number, and are generated at each time. Packets are transferred between processor elements based on a schedule statically scheduled in advance using a switch status table that shows the status of each switch in a multistage coupled network. As a result, non-synchronous execution can be enabled in the multiprocessor system device, so that the hardware overhead for synchronization can be reduced, and the efficiency of parallel processing can be improved.

【0089】

Further, the multi-stage coupled network having the above-mentioned hierarchical structure includes an upstream coupled network that transfers packets from the lower layer to the upper layer and a downstream coupled network that transfers packets from the upper layer to the lower layer. I did. From this, it is possible to prevent the formation of hot spots by preventing all packets from being concentrated in the coupling network forming the exchanger for connecting the cross networks, and to improve the performance of the multiprocessor system device.

【0090】

Specifically, the above switch status table shows the information of the packet holding the output terminal, the information of the packet requesting the output terminal, and the information indicating the state of the output terminal for each switch. It consisted of and. From this, static scheduling can be easily performed for a large-scale system including each processor element and a multi-stage coupling network.

【0091】

Further, when a plurality of packets request the output terminal of one switch in the multi-stage coupling network at the same time, arbitration is performed by a predetermined method, and the packet that cannot hold the output terminal is in the switch state at another time. Packets are transferred between processor elements according to a schedule scheduled to request the output terminal in the table. From this, it is possible to realize non-collision packet transfer for a general simultaneous access pattern.

【0092】

On the other hand, when the multi-stage coupled network is a cross network, when a plurality of packets request the output terminal of one switch in the multi-stage coupled network at the same time at the time of packet transfer in one cross network, arbitration is performed by a predetermined method. Packets that have been executed and could not hold the output terminal may be packet-transferred between processor elements according to a schedule scheduled to request the output terminal of another switch that does not request the packet. Good. By doing so, the packet transfer efficiency can be improved, and the performance of the multiprocessor system device can be improved.

【0093】

Specifically, the compiler is used to schedule each packet in advance. From this, it is possible to manage all packet waits that were dynamically performed at the time of packet collision at compile time, so it is possible to significantly reduce the hardware such as FIFO required for packet dynamic waits. It is possible to prepare a network environment for performing non-synchronous execution between processors.

[Simple explanation of drawings]

[Figure 1]

It is a schematic block diagram which showed the example of the multiprocessor system apparatus in 1st Embodiment of this invention.

[Figure 2]

It is a schematic block diagram which showed the structural example of a processor element.

[Fig. 3]

It is a figure which showed the example of the cross net.

[Fig. 4]

It is a figure which showed the example of the level 0 network in a cross network.

[Fig. 5]

It is the figure which showed the example of the level 1 network in a cross network.

[Fig. 6]

It is a figure which showed the example of the multiprocessor system apparatus which realized the hierarchical structure clustering.

[Fig. 7]

It is a figure which showed the example of the switch state table.

[Fig. 8]

It is a flowchart which showed the static scheduling method using a switch state table.

[Fig. 9]

It is a flowchart which showed the static scheduling method using a switch state table.

[Fig. 10]

It is a flowchart which showed the static scheduling method using a switch state table.

[Fig. 11]

It is a figure which showed the example of the switch state table before arbitration.

[Fig. 12]

It is a figure which showed the example of the switch state table after arbitration.

[Fig. 13]

It is a figure which showed the example of the cross net.

[Fig. 14]

It is a flowchart which showed the scheduling method in a cross network using an access list AL and a free port counter VPC.

[Fig. 15]

It is the figure which showed the example of the initial state of the access list ALcur.

[Fig. 16]

It is a figure which showed the example of the initial state of a free port counter VPC.

[Fig. 17]

It is a figure which showed the example of the access list ALnew after processing each packet one by one.

[Fig. 18]

It is a figure which showed the example of the free port counter VPC after processing each packet one by one.

[Fig. 19]

It is a figure which showed the route of each packet after scheduling.

[Fig. 20]

It is a figure which showed the example of the multiprocessor system apparatus which realized the hierarchical structure clustering in the 2nd Embodiment of this invention.

[Fig. 21]

It is a figure which showed the example of the downlink connection of each cross network and an extended network in the multiprocessor system apparatus of FIG.

[Fig. 22]

It is a figure which showed the example of the flow of data communication between processor elements.

[Fig. 23]

It is a figure which showed the example of the flow of the packet transfer between the processor elements in the multiprocessor system apparatus 1a of FIG.

[Explanation of symbols]

1,1a Multiprocessor system unit PE, PE0 ~ PEm Processor element A0 ~ An Level 0 cluster B0 ~ Bn Level 0 coupled network C0 ~ Cx Level 1 coupled network D0 ~ Dx Level 1 cluster E0 Level 2 coupled network PU, PUa, PUb processor ME, MEa, MEb memory NI, NIa, NIb network interface SC0 ~ SC3 Concentrator (level 0) switch element SD0 ~ SD3 Distributor (Level 0) Switch Element Switch element of SE0 ~ SE3 exchanger (level 0,1) Switch element for SEa0 ~ SEa3 exchanger (level 2) SCb0 ~ SCb3 Concentrator (level 1) switch element