TW527798B - A scaleable low-latency switch for usage in an interconnect structure - Google Patents

Abstract

A scalable low-latency switch extends the functionality of a multiple level minimum logic interconnect structure for usage in computers of all types, networks and communication systems. The multiple level minimum logic Interconnect structure employs a data flow technique based on timing and positioning of messages moving through the structure. The scalable low-latency switch is distributed throughout multiple nodes in the structure so that a supervisory controller providing a global control function and complex logic structures are avoided while the interconnect structure operates as a ""deflection"" or ""hot potato"" system in which processing and storage overhead at each node is reduced. The interconnect structure using the scalable low-latency switch employs a method of achieving wormhole routing through an integrated circuit chip by a novel procedure for inserting messages into the chip. Rather than simultaneously inserting a message into each unblocked node on the outer cylinder at every angle, messages are inserted simultaneously into two columns A and B only if an entire message fits between A and B. Messages are inserted into column 0 at time 0. Messages are inserted into column 1 at time t0+tc, where time tc is the time for a first bit of a message to move from column 0 to column 1 on the top level. Messages are inserted into column 2 at time t0+2tc, and so forth. The strategy prevents the first bit of one message from colliding with an interior bit of another message already in the switch. Contention between entire messages is addressed by resolving the contention between the first bit only so that messages wormhole through many cells.

Description

527798 A7 _______ B7 V. Description of the Invention () This case is about the interconnection structure of computing and communication systems. In particular, this case is about a scalable low-latency switch for a multilayer interconnection structure. A long-standing and unresolved problem in the field of computer science is the lack of a scalable low-latency interconnect structure that can still withstand high throughput (high cross-bandwidth) at full load. Existing interconnect designs such as the banyon, omega, and fat-tree networks, multi-layer grids, torus, and hypercube networks lack the ability to infinitely scale and support communication loads to varying degrees. Low latency and high turnover rate. The geometry of these networks was developed by 19th-century mathematicians and earlier geographers, but never attempted to support a method of sending messages. What we need is an interconnect structure and a suitable switch for forming an interconnect structure that is practically infinitely scalable and supports low latency and high throughput. An interconnect structure and switch having these advantages are used in many electronic design environment applications including super computer networks and network switch architecture environments such as LAN / Internet switch architecture and telephone switch architecture. useful. : The purpose of various electronic design environments is different. For example, the main purpose of designing a supercomputer is low latency. In contrast, the main purpose of LAN / Internet switch architecture design is scalability, not latency. In addition, the main purpose of the telephone central office switch is high scalability and low cost, but the consideration of latency and bandwidth is less. Open relationships for supercomputer design are made using expensive silicon manufacturing technology. The design parameters are specially defined and consistently applied to supercomputers. In particular, the character size, address structure, size, and capacity are generally in a supercomputer. ___2 This paper follows the Chinese National Standard (CNS) A4 specification (210X 297 mm) (诮 Please read the precautions on the back before filling this page)

527798 A7 ___ ^ B7 5. The description of the invention () is unchanged. The principle design of a single compiler and the definition and requirements of the operating system are generally used in supercomputers. Similarly, supercomputer systems include a single defined operating speed and voltage. Supercomputers use compatible components, memory, processors, power supplies, and the like. Although the size of the network varies greatly, a supercomputer is generally designed to have a smaller maximum size than a local area network (LAN) / Internet. The design of a supercomputer usually has a size ranging from hundreds to thousands of ports, while a network capacity ranges from hundreds to thousands or more ports. A supercomputer system uses a highly parallel switch design with the use of multiple identical stacked integrated circuits. Generally, the nodes providing a supercomputer network are on a single integrated circuit chip with only a few nodes fabricated on the circuit board. The nodes are interconnected by a number of high-speed cables sold. The supercomputer design extends to address and control issues and packaging in parallel to achieve reduced latency and increased bandwidth per port. In contrast to the implementation of supercomputer switches, switches used in a network design such as LAN / Internet design typically utilize multiple integrated circuits that may have different design parameters. Generally speaking, the design parameters of small networks are essentially different from the design parameters of large networks. For example, large networks sometimes use a twisted cubic or quadratic design. Ultra-large networks with hundreds of thousands of ports usually use a three-dimensional or four-dimensional topology, which is formed by interconnecting or cascading multiple switch circuits to a meta-topology of an ultra-large switch. Different implementations of switching circuits are needed to effectively build a LAN / Internet with different meta-topologies, and in particular to provide suitable input and output signal timing. Network bit rates are usually slower and significantly different than the bit rates of supercomputers. Example __3_ State of Chinese Standard (CNS) A4 (210X297 mm) of this paper size (read the precautions on the back before filling this page)

527798 A7 B7 V. Description of the invention (eg, Ethernet uses 10 Mbit / s rate. A token ring network has a rate of 12 Mbit / s. A fast Ethernet network reaches 100 Mbit The speed of A / s and the speed of ATM reaching 25 Mbit / s to 62 2 Mbit / s. There are many gaps in the support of traditional switch technology in the interconnect structure technology. First of all, no switch architecture or technology can support more than 12 to a reasonable price. 24 ports. For example, an eight-port marker ring network switch costs about $ 10,000. An eight- to sixteen-port Ethernet switch price range is $ 4,000. $ 2,000 The second deficiency in interconnect switch technology Designing for a single switch cannot support multiple different contact methods. Pin-constrained designs easily support only contact methods with a small packet length, such as ATM. Different packet sizes directly affect the design of integrated circuit chip, making a wide range of packet sizes As a result, there is a large difference in the design of the switch specifications. For example, a switch buffers the entire maximum packet size for each of the integrated circuit switches at least once. Therefore, the defined ATM packet size is 53 bytes, so that the small payload of the ATM design will cause the effective use of the gate in the integrated circuit. The packet size of the Ethernet is variable and the range can reach about 2Kbytes It requires a lot of sniffers to buffer a message. Similarly, the packet size range of the token ring network can reach about 4 Kbytes, and the size of the fiber channel is virtually unlimited. It uses a large circuit area for message buffering. This is a general switching circuit for local area network use, and more common is a general switching circuit used to build a network that provides IEEE network specifications. 4 This paper size applies to China National Standard (CNS) A4 specification (210X297) (%) (That is, read the note on the back ^ 11 ^ before filling out this page)-Order 527798 Α7 Β7 V. Description of the invention () (掮 Read the notes on the back before filling out this page) A very useful interconnect structure for all Types of computers, networks, and contact systems that use a data flow technology based on the timing and location of messages communicated through interconnected structures. Switch control distribution The multiple nodes in this structure can avoid the provision of an overall control function and a management and control device with a complex logical structure. The interconnected structure is operated with a "deviation" or "hot potato" system, which can reduce the number of nodes at each node Processing and storage. The removal of the overall control device and the buffering at the nodes greatly reduce the number of control and logical structures in the interconnect structure, simplify the entire control element and network interconnect elements, and improve the speed performance of the information connection. Scalable low-latency switches extend the use and benefits of interconnect structures and include a novel set of structures that accompany a novel message sending method to avoid the limitations of previously existing networks. As the size of the interconnect structure approaches infinity, the throughput of a simple embodiment of an interconnect structure using a scalable low-latency switch can be 20% more. The flight time (latency) generally does not exceed twice the time it takes for the header to enter the network, even when the interconnect is under full load. Another embodiment of an interconnect structure using a scalable low latency switch, called a "flat latency interconnect structure", has two or more downward paths at each node, and when the scale approaches infinite Improve its throughput by more than 40%. According to one idea of the present invention, the scalable low-latency switch design meets the purpose of taking an offensive at the height of multiple interconnect design types. This scalable low-latency switch meets the layout of many different integrated circuits in multiple markets for multiple design variants. The scalable low latency switch is made up of many very simple control units 5

Standards: 7 national standards (CNS) A4 specifications (210X 297 male thin T 527798 A7 ___ B7) V. Description of the invention () (Xu first read the notes on the back before filling this page) (node). The control unit is arranged in Array mode. The number of control units in an array is a design parameter, generally ranging from 64 to 1024 and usually a power of two. The array is arranged in layers and rows. The general number of rows is 4 to 20 or more. When each array contains W control units, the number of layers is generally J + 1. The scalable low-latency switch is designed according to multiple design parameters that determine switch size, performance, and type. Switches with hundreds of thousands of control units The layout in a single chip makes the useful size of the switch limited by the number of pins, not the size of the network. The multiple design parameters of this scalable low-latency switch determine the circuit layout used to construct the switch. Except for each The number of array control units and the total number of arrays can be selected for other designs. In a basic design, the control unit has two data input ports and two data output ports. Miscellaneous design is a "paired unit" design, which combines the elements of the basic unit to form a larger control unit. The larger control unit forms more complex nodes. For example, the advantages of the mixed unit designed by "paired unit" are to have Lower overall latency and reduced latency differences. Compared to this basic design, the hybrid unit can be referred to as a "flat latency" switch due to reduced latency differences. This paired unit design includes more gates than two separate units, but because of the flattening period, it can be applied to supercomputers and switch structures that are fast networks such as Gigabit Ethernet and ATM switches.

The design parameters also include the timing type, which includes a basic timing diagram and a pipeline logic diagram. This pipeline logic “ripples” in the network, so it is called a ripple type design. Ripple-type pipeline logic transmits messages over the network in fewer clock cycles. In contrast, the basic timing design is based on the fastest possible I / O 6 paper size] Chinese National Standard (CNS) A4 specification (210X 297 mm) 527798 A7 — B7 V. Description of the invention () Speed operation An integrated circuit chip. Messages generally enter the array of interconnect structures from the top (Layer L) and leave from the bottom (Layer 0). Messages such as "worm holes" pass through the control unit in the chip, and the data bits move from left to right and from top to bottom. In a simple timing diagram, the header bits move between units in a given layer in two periods (two clock cycles), and move between nodes in different layers in a short time. The payload bit ', like the header bit, uses two short times to move from one unit to another in the same layer, and instantly and effectively moves from one layer down to another. The header and payload bits use only a short time to move between nodes in a given layer in a ripple-like timing diagram. The payload bit effectively passes from one layer down through another. In this paired unit design, messages will only move between units on a given level when they deviate. Therefore, the non-deviated message has a payload bit that moves directly from the input pin to the output pin. Use timing diagrams that allow messages to pass through like holes in insects to achieve pin-to-pin connection. After the Ministry of Shanghai ’s decision i ..- ^-XJh-T elimination cooperation cooperation ^ (may read the precautions on the back before filling out this page) Some embodiments of the switch include a multicasting option, One can perform one-to-all or one-to-many message propagation. With the use of multiple broadcast options, any input port can optionally send messages to many or all output ports. This message is duplicated in the switch, producing a duplicate for each output port. Multicast is suitable for ATM and LAN / WAN switches and supercomputers. Multicast is performed in straight forward mode, which uses another control line to increase the integrated circuit logic by about 20% to 30%. A multiple broadcast switch combined with ripple-type logic can increase timing complexity, especially when the design includes a flat latency operation. 7 This paper size: China National Standards (CNS) A4 specification (210X297 mm) 527798 A7 B7 V. Description of the invention () (Read the notes on the back before filling this page) In an actual implementation, The silicon switch of the topology is restricted by pins. In other words, the minimum number of logic gates required to make the switch is substantially smaller than the number obtained. As the integrated circuit chip size increases, the area increases in square and the perimeter increases linearly. Therefore, a larger integrated circuit chip has more gates than are guaranteed by the number of I / O pins. According to some embodiments of the invention, too many logic gates are used to achieve low latency. According to other embodiments of the present invention, LAN messages of 2 Kbytes or more include many dynamic first-in-first-out (FIFO) buffers to consume too many logic gates.

US Patent Application No. 08/5 05,513, filed by Coke S · Reed on July 21, 995, entitled "MULTIPLE LEVEL MINIMUM LOGIC NETWORK", discloses a multi-layer minimum logic (MLML) network. All the references in this article are for reference. The optical embodiment of the multilayer minimum logic network has a structure in which a node of the outermost cylinder (top layer) has an input port to receive a message. In a short time of the entire clock, the message It is inserted into the unlocked node of the outermost cylinder (top layer). The optical interconnection lines (fiber optics) between the nodes transmit the message so that the entire message is suitable for adjacent nodes. Warp Ministry Zhongrong ir ^ -XJmJ. Elimination of cooperation ii 卬 f Although the multilayer minimum logical network does not use electronic storage such as memory or buffers for transmitting messages, in the implementation of the electronic design of the multilayer minimum logical network, the interconnections between nodes can be first-in-first-out. -in, First-out, FIFO) buffer. For example, one of the possible embodiments of an electronic version of a multi-layer minimum logic network is mainly composed of FIFO, and at least between nodes in the chip The number of contacts multiplied by the length of the message multiplied by the clock rate of the circuit. There is a maximum of 8_ This paper size is suitable for China National Standard (CNS) A4 ^ (210X297 mm) 527798 A7 B7 5. Description of the invention () Small latency. Remove FIFO The electronic design of the buffer will cause the number of node transfers times the minimum latency of the clock rate of the circuit. Furthermore, removing the FIFO buffer allows the chip to be composed mainly of cells or nodes rather than FIFO components, which is beneficial Allows larger networks to fit on a chip and take advantage of the borehole path of the worm to greatly reduce latency. The interconnect structure using a scalable low latency switch is achieved using a novel process by inserting messages into the chip The wormhole's hole-shaped path passes through the integrated circuit chip. If the entire message fits between lines A and B, the message will be inserted at lines A and B at the same time, instead of inserting the message at each angle at the same time. In each unlocked node of the cylinder. The message is inserted into line 0 at time 0. The message is inserted into line 1 at time U + t. The time t. Is the first bit of the message at the top level. by The time from line 0 to line 1. The message is inserted into line 2 at time% + 2 and so on. This method is helpful to avoid the first bit of a message and another one that is already in the switch. One of the bits of the message collided. Therefore, the competition between all messages is handled by the first bit that has only the message such as the bug hole through the desired result of many units. In many instances, The first bit of the payload leaves the chip before the tail bit of the payload enters. According to one aspect of the present invention, the use of two to four times as many rows as guaranteed by the number of input and output pins or Too many logic gates with more rows of switches to achieve a lower latency design. There is no input link in the line with too many input pins, which effectively reduces the possibility of a message being deviated from another 'message by passing through the switch to reduce competition in the switch. The latency increases with each deviation. Supply other not connected to the input line_ _9 This paper is suitable for size / 1] Chinese National Standard (CNS) Α4 size (210X297 mm) (ti read the precautions on the back before filling this page), 1T 527798 A7 ____ _ B7__ V. Description of the invention () (Read the precautions on the back and then fill out this page) The line will substantially reduce the density of message circulation in the switch and will help reduce the latency. In various embodiments of the present invention, different input port and row configurations are defined to adjust and coordinate message flow density, and utilize more internal logic than I / O connections. According to another concept of the present invention, different output ports and row configurations are defined to support different interconnection purposes. The two main types of interconnect structures are supercomputer and network (LAN / Internet) design structures. The output of a supercomputer: The configuration ignores the row address of an output signal and immediately draws a message from the switch. A message has multiple exit targets, i.e. a set of external buffers. The size of the switch is equal to the number of columns, although many rows are included in this design. In contrast, a 'network' (LAN) output signal may use a special row address associated with a special message destination of one of a plurality of destinations. The size of the output structure is the number of columns multiplied by the number of external rows. An output configuration is essentially the opposite of the output configuration of a supercomputer. All in all, the output design of one applicable supercomputer provides a maximum bandwidth and the lowest latency t. The second design applicable to the network provides the maximum number of ports possible. According to various embodiments of the invention, a scalable low latency switch supports a wide range of interconnect targets for many interconnect applications. The scalable low latency switch supports flat latency control units and single-row control units. The switch supports a single short-term timing and ripple-logic timing. In some embodiments, the scalable low latency switch supports multicasting, while in other embodiments the scalable low latency switch does not support multicast. Various embodiments of the scalable low-latency switch support _______ 10 H Min Zhang scale shift Chinese National Standard (CNS) A4 specifications (210X297 mm) 527798 A7 B7 V. Description of the invention () Different input port structures to achieve various Set the message flow density and support different output port structures for applications ranging from low-latency supercomputers to multi-port LANs. The switch supports everything from small supercomputer messages to huge LAN messages. According to another concept of the present invention, the scalable low-latency switch can be used as an optical embodiment. In addition to the borehole path, it has several advantages over the MLML network patent. In addition, in some embodiments, A message header is processed in an electronic network. The electronic network sets the gate in a "slave" optical network and carries only the payload. This electric / optical hybrid switch is beneficial to take advantage of the excellent features of each technology. In some embodiments, the scalable low-latency switch can be fabricated on a single chip. Traditionally, a traditional network is a collection station that acts as an independent node, interconnected with circuit boards and multiple cables. This traditional implementation is expensive and requires many wafers, circuit boards, and high-speed cables. This traditional implementation has a latency, ideally a few microseconds or even a few hundred microseconds with very low message density. In contrast, using the current ASIC technology, the full-load 5 12- 璋 scalable low-latency switch's latency is easily in the 20-1 00 nanosecond range. -------------- 1T ------ (Please read the notes on the back before filling out this page) The benefits of scalable low-latency switches are described in the following table, which compares the interconnect design features of today's traditional networks and architectures using scalable low-latency switches: Traditional networks implement scalable low-latency The switch uses cables to interconnect multiple separate nodes in the circuit board, resulting in a large use of today's ASIC method to place all control units (nodes) in a low-cost integrated circuit crystal. 11 This paper size applies to Chinese national standards (CNS) Λ4 Regulations (210X29? Exchange) 527798 A7 B7 V. Description of the Invention () The printed on-chip node of the Consumer Cooperatives of the Central Standards Bureau of the Ministry of Economic Affairs is a complex J, and its package nodes are provided with Less than a dozen dozen logic cell chips including simple cell bits and routing flags for checking all address gates, and support for multiple inputs 丄m Hundreds of thousands of units y Bai Ren (--generally receive four or more input inputs to any output to provide input signals) for a considerable number of simultaneous message paths i-path nodes generally include can retain only one message or one whole The message KI Green 1 punches two bits in one of the unit's dynamic displacement registers. The message is always: On the move. 0 Enter — Multiple messages from the node. The first unit is transmitted to the first brother. Leaving one of the two units "occupied the signal path number" PT strong L causes the possibility of the second unit: Collision When _. Or more messages do not collide, because it is always desirable to compete for the same path for each unit There is a "collision" where it has to-leave the path. A brother will deal with it later. The unit that received the dispute will receive an occupation signal and be refused to use it. With this path, a node must check the message. A unit only checks the two bits of the message address and other routing flags and an occupancy to determine how to handle the [message signal to determine the path. It can be easily processed in a single-clock cycle. In a traditional network, a collision has never occurred. 9 A collision will cause the message to be replaced. A message can be re-sent through the network. Y Direction—adjacent units, which can waste all the obtained progressive distances to reach the giant. Bid 0 to reach a goal, the turning process will only consume (please read the notes on the back before filling this page), 1T 12 This paper size is applicable to China National Standard (CNS) Λ4 gauge (210X297) ^ 7798 A7 B7 1'Invention description () Printed by the Consumer Cooperatives of the Central Standards Bureau of the Ministry of Economic Affairs ^ —. --- a — some clock cycles in ----_ ibb traditional network 1 no more than-* or two Bit collision will cause the entire message to be temporarily retained in a motion that will be buffered or stored in the-* state shift register unit node, so the message in the slow-down stage never stops moving in. 5 Reduce the latency and activate the The node's logical complexity ft 'does not support as many messages as one of the other messages on a 7Z broadcast path. One embodiment of the scalable low latency switch supports one • for all and — for multiple message sending | ( (Multicast) messages will not pass through the network element like worm messages across the holes of multiple control orders and through the network like worm holes so that the header of the payload even enters the chip at the end. Immediately after leaving the tir, the size of the full-load network is scalable when the full load is increased: the low latency is increased to a few Or when the size of several thousand switches is increased to M port, the effective input volume is limited. The preferred embodiment has a near zero input and the latency is increased by more than 40% and the length of i is accepted by the 4nr method. The distribution of the waiting period is still narrow. Today's network design cannot be reduced: lower the waiting period and open 5 to see it. It can support thousands of ports at the same time. Bureau J supports thousands of ports and low throughput; High throughput and low latency: For examples of the structure and operation method of this case, please refer to the description of the attached drawings for a deeper understanding. Use the same reference numerals in different figures. Table 13 This paper size applies to Chinese National Standards (CNS) Λ4 specifications (210X 297) (please read the precautions on the back before filling out this page, \\ 5 f Staff Consumption of the Central Standards Bureau of the Ministry of Economy Printed by the cooperative 527798 A7 B7___ 5. The description of the invention () shows similar or identical items. Figure 1A illustrates the basics of a scalable low-latency switch that can be applied to several embodiments of the present invention in overview form. Block diagram of the structure of the element and interconnecting the basic element. Figure 1B is a right-to-left connection diagram in one layer of the block diagram. Figure 1C is a schematic diagram of a generalized embodiment of the interconnect structure. It explains how the control unit becomes a component of a group, how to interconnect groups, how data flows from one unit to another, and how to connect control signals. Figure 1D is a general example of moving data through the interconnection structure in the form of messages. A schematic view of the method. Figures 2A, 2B, and 2C are schematic diagrams illustrating the layout of messages transmitted through the switch shown in Figure 1A; Figure 2A contains information about a column of headers. Figure 2B is a message with column and row headers; Figure 2C is a message for multicasting. Figure 3 is a schematic interconnection diagram illustrating the interconnection of switch arrays, which includes detailed information Switch array interconnection relationship, such as the connection of data and occupancy signals. Figure 4 is a timing diagram illustrating the timing of the input signal and the timing of the output signal, which describes the timing and timing of the information entering and leaving the switch in a simplified embodiment of a communication technology. Fig. 5A is a schematic diagram showing the connection of a tri-state input terminal connected to the switch; Fig. 5B is a timing diagram of control timing signals applied to the switch shown in Fig. 5A, which uses tri-state timing To allow only a single pin to be used for control (output) and data (input), because the control and data 14 This paper size applies the Chinese National Standard (CNS) AAim (210X291 (read the precautions on the back before filling this page) )

527798 Printed by the Consumer Cooperatives of the Central Standards Bureau of the Ministry of Economic Affairs A7 B7 V. Description of Invention () The signals are generated at different times. Figures 6A and 6C are 8-list and 16-list, respectively, and Figure 6B is a schematic diagram illustrating a method of generating a sequence of positions for assigning control units to switches. Figure 7A illustrates how to use a binary tree transmission technique to send a message through the switch shown in Figure 1A, where the message has multiple paths to its target column. Figure 7B illustrates an embodiment in which the lower layer has an increased number of columns to help reduce message congestion before the message reaches its target. Figure 8A is a schematic block diagram illustrating a technique for moving a message from one layer to the next lower layer message on a path to a predetermined target. Figure 8B shows that one of the messages in a lower layer can block the message of the next higher layer immediately to the lower layer, and the blocked message has another opportunity to move to the lower layer using the technique illustrated in Figure 8A . Figure 9 is a diagram of transmission interconnection, which illustrates the connection relationship between a message path in one column and the column in the lower layer, and emphasizes the sequence of locations of the interconnection methods described in the 8-list shown in Figure 6B to achieve the A subsequent process has the advantage that the probability that one of the messages of the interconnect structure is blocked by the same message is very low. Figure 10 is a schematic diagram illustrating that when a message passes the switch, a message header passes the switch and the length of the message header is shortened, so that the entire header is removed before the message reaches the bottom of the switch, which is beneficial to cause Lower latency and simpler logic processing. Figure 11A is a series of FIFO buffers that are successively extended. 15 Applicable to China National Standard (CNS) A4 specifications (210X 297 public garbage) (Please read the precautions on the back before filling this page),- ° .1 CC 79 27 b Printed by the Central Bureau of Standards of the Ministry of Economic Affairs and Co-operative Society f. A7 _ B7 _ V. Description of the invention () Delay element, Figure ΠB is a dynamic FIFO buffer composed of delay elements, and 11C is an optical FIFO structure. Figure 12A is a relative timing diagram showing the control logic of different quasi-layers in the same row of the interconnect. Figure 12B is a relative timing diagram showing the control logic of different layers in the same column of the interconnect. Figure 13A is a schematic diagram of the state of the control unit for a downwardly moving message. The status of the unit is stored in a latch. It also shows the delay elements for logic processing and the interconnections up, down, left, and right. Figure 13B is a schematic diagram of the state of a control unit, one of the messages for moving to the right. The status of the unit is stored in a latch. Fig. 14 is a flow chart of general logic elements required for controlling message flow through a control unit. If this message is present, the result is to set the state of the control unit to send a downward or rightward message. Fig. 15A is a detailed explanatory diagram of a logic gate of an embodiment of a control unit of some layers higher than the 0th layer. This is a complete description of Figs. 13A and 13B, and the processing procedure described in the flowchart of Fig. 14 is performed. Fig. 15B is a detailed explanatory diagram of the logic gate of the embodiment of the control unit at the 0th layer, which is used in combination with the address of the row address shown in Fig. 2B. Figure 16A is a timing diagram of the high-speed timing (no inter-layer delay) switch and its control unit. Processing of all layers occurs at the same clock cycle, thus reducing latency. Figure 16B is a detailed illustration of two high-speed control units connected to the same row, discussing the high-speed "ripple" logic. 16 (Read the notes on the back before filling in this page)

This paper size applies to the Chinese National Standard (CNS) Λ4 specification (210X297). 527798 A7 B7 Printed by the Consumer Cooperatives of the Central Standards Bureau of the Ministry of Economic Affairs. 5. Description of the invention A switch diagram showing the layout and interconnection of all control units in all switch arrays. The switch array constitutes a complete embodiment of a switch. Fig. 18A shows the seven states of a flat latency control unit, that is, the interconnection of two input and two input and output units. Figure 18B is a table describing how the combination of many inputs to a flat latency control unit 値 determines which state it is in. This state is used to control the circulation of 0, 1, 2, 3 or 4 messages entering the unit. Fig. 18C is a detailed schematic diagram of a flat latency control unit, which uses the state determined by the table of Fig. 18B to set the logic gate and thus sends a message through the unit. Fig. 18D is a concise symbol representing a flat latency control unit used in one of the following drawings. Figure 19 illustrates the complete interconnection and layout of a 64-port flat latency switch with 16 columns by 4 rows, which forms a complete embodiment of a flat latency switch. It shows the location and interconnection of all control units in all switch arrays, and discusses how to place them. Figures 20A, 20B, and 20C show another embodiment of the top layer of a single path and flat latency switch. Compared to the maximum possible number of inputs, it is beneficial to reduce the number of inputs to the switch, thus reducing the message density and the number of switches. Congestion. Figures 21A, 21B, and 21C show different right-to-left interconnections at one level and each level for a variety of advantageous design requirements. 17 (Please read the notes on the back before filling this page)

This paper scale applies Chinese National Standard (CNS) Λ4 specification (21〇X29D > ^) 527798 A7 ΒΊ Printed by the Consumer Cooperatives of the Central Standards Bureau of the Ministry of Economic Affairs 5. Description of the invention () Figure 22A is a low-latency output circuit The block diagram is used for the information described in Figure 2A and intended for the lowest possible latency, such as for a supercomputer; Figure 22B is a detailed diagram of one of the components shown in Figure 22A. Figure 23A is a block diagram of the switch output using one of the column and row addressing described in Figure 2B, and is intended for use with a large capacity switch, such as an ATM or telephone switch with one of the many ports; Figure 23B and Figure 23C details the elements of Figure 23A. Figure 24A is a block diagram of components of a multi-cast control unit using one of the messages described in Figure 2C to achieve the purpose of transmitting a message from an input to an output, or to broadcast (multi-cast) a message to many Output or all output ports. Figures 24B, 24C, and 24D illustrate the state of one multiplex broadcast control unit when a multiplex broadcast message moves to the right along a column. Figures 25A, 25B, and 25C depict the message header layout of a multi-chip switch formed with a one-dimensional topology. Figure 26A is a schematic diagram illustrating how multiple chips are interconnected to produce a switch with many input and output ports. Fig. 26B is a symbol representing the interconnecting switch system of Fig. 2D, which means "twisted cube". Figure 27 is a schematic diagram illustrating how multiple chips are interconnected in a three-dimensional structure to produce a switch with a considerable number of I / O ports. Figure 28 is a schematic diagram illustrating how to interconnect multiple chips in a quaternary structure to produce a switch ("4D switch") with a very large number of I / O ports. (Read the precautions on the back before you fill out this page) Μ 18 This paper size is applicable to China National Standards (CNS) Mim (210X 297 ^ 1 " 527798 A7 B7 Printed by the Staff Consumer Cooperative of the Central Standards Bureau of the Ministry of Economic Affairs () Figure 29A shows how to divide a message into two half of the original size to enter a low latency switch. Figure 2B is a block diagram of a split header switch, which has a master-slave switch. The relationship switch uses the segmented message of Fig. 29A to reduce the low latency by about twice. Fig. 30A shows the layout of an optical message processed by an electronic optical switch. Fig. 30B shows the processing of 30A. One of the messages described in the figure is an electro-optical control unit. Figure 30C is the top or input control unit for the optical message described in Figure 30A. Figure 30D is the optic used to process an optical message Amplifier / regenerator symbol. Figure 3 0E is a complete electronic optical switch, which shows the interconnection of the control unit described in Figures 30B and 30C and the optical fiber interconnection of the unit. Figure 3 Figure 1 is composed of an electronic control unit connected to a simplified optical control unit in a master-slave relationship. A hybrid control device is used to significantly reduce the latency and achieve very high bandwidth. Figure 32 It is a hybrid electronic optical switch that uses part of the two types of control units described in Figure 31 and its interconnection method. The same symbols used in different drawings represent similar or identical items. Used for high-bandwidth communications and computer networks Road application of low-latency scale 19 This paper size applies Chinese National Standards (CNS) Λ4 Regulations (210X297 public power) (Read the precautions on the back before filling this page) .0

, 1T 527798 A7 B7 Printed by the Consumers' Cooperative of the Central Standards Bureau of the Ministry of Economic Affairs 5. Description of the invention () The Guan has many interactive structures to perform many types of functions and a wide range of capacity and performance characteristics. The first embodiment describes a switch-derived power-of-two design rule that supports the information bug hole path, only handles a single message length, point-to-point message transmission, each layer has a fixed number of columns, and is not suitable for a flat latency distribution. The description of the first embodiment of the switch 100 forms the basis for establishing the desired additional functions and features. Additional functions and features generally include multi-cast (one-to-many) transmission capabilities, switching of messages of various lengths, low-latency transmission, multi-chip implementation, and control of a fiber switch. Different embodiments of this interconnect structure are discussed in detail in Reed's U.S. Patent Application No. 08 / 505,5 1 3. Referring to FIG. 1A, one embodiment of the scalable low-latency switch 100 includes multiple columns of serial data transmission devices arranged in multiple rows 160, 162, and 164 and on multiple layers 130, 132, 134, and 136. The layers are interconnected in each row with the structure of a data bus 122 and a control bus 124. The L + 1 layer is listed as the 0th layer 130, the 1st layer 132, and the Lth layer 136. These layers include a plurality of columns R 170. The column performs a serial data transmission 126, interconnects a sequence of switch arrays 120 and an optical first-in-first-out (FIFO) serial delay element 114 along each column or layer. The concatenated data in the form of a message passes through all the data input buses 102 or enters the switch 100 from many lines. The data input bus 102 includes a plurality of serial data input ports 104. The serial data leaves the switch 1 00 by the data output line 1 5 8 in each row. The data bus includes a plurality of serial data output ports 154. Please also refer to Figure 2A, which is beneficial for a message entering any input port 104 and leaving the output specified by the message header. 20 The paper scale is applicable to the Chinese National Standard (CNS) Λ4 specification (210/297 cm) (read first (Please read the notes on the back and fill in this page) 527798 Central Standard of the Ministry of Economic Affairs>?-Bureau Beigong Cooperative Co., Ltd. Printing A7 B7 V. Description of Invention () Port 154. In one embodiment, the switch 100 is implemented by a semiconductor chip. In the chip, the input port 104 includes an input pin connection point, and an output port 154 includes an output pin connection point. In another embodiment designed for high-speed operation, a plurality of pins serve as a single input port or output port connection point. Multiple wafers operate in parallel to produce a large, high speed, very low latency switch. In yet another embodiment designed for a very large number of I / O ports, a plurality of specially interconnected chips constitute a single implementation of the switch 100. In the embodiment of the switch 100, the κ row is listed as 0, 1, .., K-1, and each row connection including R serial data transmission lines 1 70 generates R multiplied by K input ports 104, and reaches R times K output ports 154. The number of data lines R is preferably equal to or smaller than the number of layers, where L + 1 is the number of layers of the switch 100. In one embodiment of the switch 100, R 170 is equal to 2L and K is preferably an even number to achieve a favorable minimum message blocking, which will be discussed later. In one embodiment of the switch 1000, the number of columns in a lower j-th layer 170 is greater than the number of columns in the j + l layer above; in this example, R170 means the number of columns in the bottom layer. Table 1 gives an example of a 1000 size switch for a wide range of preferred K and L 値. In some embodiments of the switch 1000, the number of address ports is the same as the number of columns, and this port advantageously provides a substantial increase in bandwidth. One layer of the table (L + 1) Row (K) Column (2l) Port (column * κ) 4 4 8 32 4 6 8 48 21 This paper size applies to Chinese National Standard (CNS) / \ 4 蚬 梠 (210X29D >#_ ) (Read the precautions on the back before filling this page) Order 527798 — B7 V. Description of the invention () Printed by the Consumer Cooperatives of the Central Bureau of Standards, Ministry of Economic Affairs 5 8 16 128 6 8 32 256 6 10 32 320 7 12 64 768 8 16 128 2,048 9 16 256 4,096 11 28 1,024 28,672 15 24 16,384 393,216 19 32 262,144 8,388,608 21 36 1,048,576 37,748,736 Please refer to Figure 1A, each row timing control line is connected to rows 1 60, 1 62 and 164, multiple The row timing control line 108 signals that the individual row is ready to receive data from an external device. A plurality of 璋 acquisition lines 106 in each line, in conjunction with the line timing-control line 108, are issued to obtain a corresponding series of input signals 104 to receive data signals. In one embodiment shown in the structure 116, a plurality of buffers 112 concatenate the information and store it for subsequent injection into the switch array 120 of the top L 136. The selected input structure 116 cooperates with the input buffer 112 to control the timing of the message 200 entering the switch 100, and to control subsequent buffering and injection of the series of messages into a switch array 120 on the top layer 136 of the switch 100. In another embodiment of the switch 100, the structure 1 16 is omitted and the data is immediately moved from the input port 104 to the switch array 120. A plurality of output control lines 156 in each row receive a device preparation signal from an external device. The signal indicates that the external device is ready to receive a message 200 from a corresponding serial output port j54. · Applicable to Chinese National Standards (CNS) / Grid (210X 297 ^^ 1) in the 22 paper sizes shown on the output. Please read the precautions on the back before filling out this page), 11 f, 527798 kl B7 i, invention description ( An embodiment of the structure 180. After sending a message through the switch 100, a plurality of output buffers 152 store the message. In another embodiment of the switch 100, the structure 180 is omitted. In this embodiment, a switch array 120 on the bottom layer is directly connected to the output port 154. In addition, the output control line 156 is also connected to the switch array 120 at the bottom. The information in the form of serial data enters from the input port 104 to the uppermost layer 136 of the switch array 120. In one implementation, the message then moves right to the next switch array. The next switch array determines whether the message should be transmitted down to the next lower layer 134, or if it should be transmitted to the right and still be on the same layer 136. After a message moves right to the switch array 120 in the next row, the message still on the same layer may have a chance to move down to v the next lower layer. A message that has always fallen to the next lower layer 134 enters the switch array on that layer, where it can immediately move right to a switch array 120 below the same layer 134. A message that enters a switch array 12 from the upper layer always leaves the switch array to the right. Messages entering a switch array 120 from the left leave the switch array and go right or down. Printed by the Consumer Standards Cooperative of the Central Standards Bureau of the Ministry of Economic Affairs (please read the precautions on the back before filling this page) Enter the selectable serial FIFO delay element 114. After leaving the FIFO, the message is passed to the column exit point 172. In one embodiment, the exit point 172 is connected to the input port 104. In another embodiment, the point is internally connected to the entry point 174 in the same row on the same layer, or externally connected to the other port The point 174 of the same layer. Whenever a message goes to the right and enters the next row of the switch array 120 'still on one of the special layers, the message may have a chance to fall to the next lower 23 This paper size applies Chinese National Standard (CNS) A4 ^ 枋210X 297 exchange) 527798 A7 B7 The Central Standards Bureau of the Ministry of Economic Affairs, Consumer Cooperatives, Cooperative Cooperatives, Fifth, Invention Description (). In one embodiment, the length of the FIFO 144 is fixed; in another embodiment, the length of the FIFO 144 is different to allow efficient processing of various lengths of information; in yet another embodiment, the FIFO is omitted. The structure and function of this FIFO will be discussed later. The timing of the message 200 entering the switch 100 is adjusted by the line preparation signal 108 and the port occupancy signal 106, so that the first bit of the signal enters the switch at the time determined by the timing control structure 142. This structure is controlled externally by a clock signal 140 and a message length control signal 144. All messages entering one of the output ports 104 on the same line enter at the same time. Enter a line and the message to the right of that line enters later 'so that the header bits of all messages in the same layer can be arranged, even if these messages enter layers in different lines. In contrast, in the MLML network discussed in Reed's U.S. Patent Application No. 08 / 505,5 1 3, messages enter all lines simultaneously. In the illustrated embodiment of the switch 100, only one bit extends between the lines, instead of all bits of the entire message in the conventional technology are called the message "worm hole". The timing between lines is adjusted by delay element 148, which will be discussed later. In one embodiment of the switch 1000, the timing of entering a message of a switch array 120 of a given layer is different from the timing of entering a message of another switch array in the same row in a different layer. In this embodiment, the timing between layers is adjusted by the delay element 146. In another embodiment, the entire clock timing is the same for many or all layers, and the delay element 146 is omitted. The connection in one layer is shown in FIG. 1B and cooperates with FIG. 1A. 24 This paper size applies Chinese National Standard (CNS) A4 Regulations 210M 297cm (Please read the precautions below and then fill out this page)-1 527798 Printed by the Central Bureau of Standards, Ministry of Economic Affairs A7 __B7 V. Description of the invention () Connect to the left column. The exit point 172 on the right hand side is connected backwards to the left and enters the point 1 74 in a column of the same level. In some embodiments, a row 166 may be used in which a message leaving one of the right-hand side is sent to a different column of a left-hand side of the same layer. In other embodiments, one connection point on the right-hand side is connected to the same column. Figures 21A, 21B, and 21C also show other ways of connecting the left and right points. Generalized Embodiment FIG. 1C is a general diagram of the switch 100. As shown in FIG. In this figure, for the sake of clarity, many components such as the control unit and the interconnection structure between the control units are omitted (the terms "left" and "right" in this figure mean the units connected to the same layer, respectively An input path and an output path). The control unit 186 is an element of one or more group units of the same layer. A group 192 contains one or more data loops 184. In Figure 1C, the top layer includes a group G [2, l] 192, where the first parameter (2) represents the layer and the second parameter (2) represents a special group of the layer. Cell B 186 in group G [l, l] is connected to other cells to form a continuous data loop 184 together. Data in the form of messages circulating through loop 184 moves through units A, B, C, D, E and beyond. In some embodiments where the message length is long, a FIFO is included in the data loop 184. One of the loops in a data loop has the opportunity to move down to any unit in the lower-level connection group, such as from G [2, l] to G [l, l] or to G [l, 2]. In some embodiments, two groups are connected under each group to form several groups of multiple "binary tree" type connection paths. One of the messages entering unit B 186 has the opportunity to fall down to group G [l, 2] on the first level. In the next unit (in this example, unit C) 25 This paper size applies to the Chinese national standard (CNsTa4 specification (210X 297 cm)) (Read the precautions on the back before filling in this page)

527798 Α7 Β7 Printed by the Diaobei Central Standards Bureau Shellfish Consumer Cooperative 5. V. Description of the invention () The message has the opportunity to fall to another group G [l, 2], and this message can be connected to the target 1 54 of a different group. In some embodiments, a message need not move through more than two cells in a group before it has the opportunity to fall to any group in the lower layer. A message entering unit B 186 can be preferentially moved down to interconnect structure 188 and to unit J at a lower level because unit J is on a path connecting unit B and message destination N 154. Unit L (at the lower level) is also connected to unit J. If a message is moved from cell L to cell J, then cell L at the lower level has priority. The priority is signaled by the unit L, which sends the occupancy signal 190 to the above unit B to inform the unit B not to send a message downward. In some embodiments, the switch 194 on the down path 188 is also activated by the occupancy signal 190 to avoid any message from the signalling unit colliding with the message on the shared path on the lower level. When an external device such as an input 104 cannot give an occupancy signal 190, the switch 194 can help avoid collision. All units have a leaving path 196 to another unit in the unit group (or to a FIFO), and all units have an occupied signal connection point 190 to one of the other units, which can share a common path. If for any reason a unit cannot transmit a message downward, the unit transmits the message in the interconnect structure 196 to another unit in the same group 192 at the same layer. A significant benefit of the occupancy signal 190 is that an entry path 196 is obtained by entering a message from another unit in the unit group. Messages that are still in a layer cannot lose the opportunity to move forward to move forward to the message target. The message immediately faces other orders connected to the same layer of the lower group on the path to the target of the message. 26 This paper size applies the Chinese National Standard (CNS) (210X 297ϋ " Τ (¾ Read the notes on the back first) (Fill in this page again)

Printed by the Consumer Cooperatives of the Central Standards Bureau of the Ministry of Economic Affairs 527798 A7 _ B7___ V. Description of Invention () Yuan. One of the message paths of the entry unit A and the exit unit N is shown by a thick line in Fig. 1C. The inspection of Figure 1A shows that many paths exist in any input to any output 154. Method Overview Figure 1D is a perspective view of the method for sending a message through switch 100. Please also refer to Figures 1A, 1C, and 2A. Generally speaking, the message enters the interconnect structure 100 at the top layer and moves down to the right, where the message is sent in the message target column of the bottom layer. The target column address is encoded in the header of the message. In a preferred embodiment, the most significant bit of the target address appears first and the least significant bit appears last. The payload continues the header (discussed in Figures 2A and 2B). The message is moved through the switch 100 from one control unit to another. The structure of the switch 1000 has a close relationship with how the message is controlled and will be discussed in detail below. A control unit is located in each column at the intersection between each row and each layer, and therefore in each control array. All processing is performed in this simple control unit. No additional message sending components are required. A control unit contains only one or two storage bits, which in the exemplary embodiment is in the form of a shift register. Advantageously, a control unit contains no more than two bits of the message to reduce logic requirements and speed up the passage of a message through the unit. Once the control unit decides where to send the message, the unit sets the internal gate and sends the message down to the target or right to one of the units in the same group. Generally speaking, when the bits of the message pass through the interconnection in a unit-to-unit manner in a process called the wormhole path method, this paper standard applies the Chinese National Standard (CNS) Λ4 Regulations (210 '乂 297). (Published) (Read the precautions on the back before filling in this page)

, 1T

Her 527798 Printed by the Consumer Cooperatives of the Central Bureau of Standards of the Ministry of Economic Affairs A7 B7 V. Description of Invention () The structure allows the message to cross multiple control units. A control unit always has an available exit path to the right 196 to ensure that messages entering a control unit from the left have an available exit. As expected, a message is never buffered or retained in a control unit, which helps reduce the time (latency) through a control unit. The unit only checks some header bits and an occupation signal 190 from one or more neighboring control units to decide where to send the message. This decision can be easily implemented in a single clock cycle. If the control unit has a connection point down to a group on the path connected to the message target and the connection point is available, the message is sent downward to move the message closer to the target. Otherwise, it is always possible to pass the message to the right to another control unit in the path where the process is repeated. When a message is sent down and the most significant address bit is removed to facilitate shortening the length of the header and reducing the number of bits, the next unit must be prepared to determine the direction of the message. This next unit can effectively access the appropriate header bit because no other address bits are consecutively ahead of the appropriate header bit. The removal of the most significant bit is advantageous because the removed header bits have been used to determine the message path through the current portion of the interconnect structure and are no longer needed. When a message is sent to a unit in the same group, the message will not lose forward completion across the interconnect structure to the message destination. The next unit to the right attempts to send the message to the target. One message sent to the right can be delayed by one or two clock cycles as needed. A message that reaches the right-hand side of the interconnect structure is sent back to the unit on the left side of the same layer, as described in Figure ic (read the precautions on the back before filling this page) 28 This paper size applies the Chinese national standard (CNS ) / \ 4 specifications (210X 297 gong) 527798 Printed by the Central Standards Bureau of the Ministry of Economic Affairs and Consumer Cooperatives 1i A7 B7 1. Discussed in the description of the invention (). A control unit monitors only some bits of the message header and a signal from another control unit to decide how to send the message. This decision is performed during a clock cycle. The message moved down is directly connected to the unit below to move over the internal displacement register of the transfer unit. The payload is delayed no more than one clock cycle. In an embodiment (not shown), one of the control units has multiple downward paths, and an unblocked message always has a connection point to the message target. In the multi-path embodiment, the time elapsed from the first bit of the message leaving the switch 100 is one clock period of each header bit plus one or two times the number of turns. Occurs when passing through this interconnect structure. The message passes through the switch 100 in a wormhole manner so that the first bit of the payload can leave as expected before the tail of the payload enters the switch. General messages reach one of a thousand columns with less than 12 turns. The first bit of the payload quickly leaves a 1000-port switch in less than 15 or 20 clock cycles. For the message layout, please refer to FIG. 2A. A serial message entering the switch 100 includes a traffic bit 202 which always has a ONE; a column header 204 to identify the target column at the bottom of the switch; and A payload consisting of concatenated data bits 206. The column header 204 is a binary encoding of an underlying target column. This mode causes the most significant bit (MSB) 208 of the target column address to appear first and the least significant bit (LSB) 210 to appear last. The payload 206 includes a data packet within the switch that is intended to be transmitted from any input port to any input port or output port group. Some implementations of the switch 1 00 29 This paper is long-range applicable to the Chinese National Standard (CNS) Λ4 gauge (210X297) (read the precautions on the back before filling this page)

1T 527798 A7 B7__V. Description of the invention () In the example, the payload 206 can be of various lengths' which is controlled by the dynamic timing structure 142. Referring to FIG. 2B, in another embodiment of the switch 100, the bottom target column is determined by the column header 204 as described above, and the target row is determined by the row header 2 1 2. The line header contains a binary encoding of the number of lines. In this embodiment, the first header 204 determines the target column in the pattern described in FIG. 2A, and the second header represents the target row. In this embodiment, the message can be looped at the bottom level until it reaches the target behavior. In another embodiment, the message immediately moves down to the first available buffer 152, which will be discussed later. The total length 214 of the message 200 includes the communication bit 202, the headers 204 and 212, and the payload 206. Please refer to FIG. 2C. In another embodiment of the switch 100, the switch 100 supports point-to-multipoint broadcasting. A multiplex broadcast bit 220 indicates whether the message 23 0 will be transmitted to an output port 154. Or to many output ports, or to all outputs 璋. When the multiplex broadcast bit 220 is set to ZERO, the message accurately points to an output frame, and the continuous bits in the message are processed into the column header 204, and the row header 212 and the payload 206 can be selected, that is, as in section 2A. Same definition as described in Figure 2B. When the multiplex broadcast bit 220 is set to ONE, the lower two bit positions are used as the "upper half" 224 and, and the lower half "226" marks, that is, using them as a pair of single bit registers (in the (Inside the message header) to indicate the message status when the message moves through the switch. The remaining bits constitute a row of bit flags, 228. The details of the multi-bit broadcast process will be discussed later. On the switch 100 In another embodiment, the 'multicast broadcast message uses the column entry. Point 1 74 to enter the special features of any layer (read the precautions on the back before filling this page) Order ___________ This paper size is suitable for China National Standards (CNS) Specification of Λ4 (210X297 mm) 527798 A7 ____ B7 V. Description of the invention () The Ministry of Economic Affairs and the Ministry of Commerce won the award of the bidder. T consumer cooperation private printing W wood fixed column switch. This message is directed to a specific subset of the bottom column. Figures 2A, 2B, and 2C describe the layout of the message from input 璋 104 or column entry point 174 to switch 100. When the message passes through the switch, the length and other characteristics of the message can be changed. A suitable combination is shown in section 2A , As described in Figures 2B and 2C Information is the responsibility of an external device connected to input port 104. For the layout of the switch array, please refer to Figure 3 and cooperate with Figure 1. Each switch array 120 includes R control devices 300. A switch array 120 is located in the switch 100. The intersection of each row and each layer. In one embodiment of the switch 100, each switch array 120 includes exactly one control unit on any vertical data line 3 1 6 and exactly one control unit on any horizontal column 360 In some switch arrays, the control units are arranged in a "unit configuration" manner, that is, along the diagonal from left to top right, where the vertical position in the switch array is the same as the horizontal coordinate. The unit configuration is based on switches Array 340 is shown. In other switch array layouts, the control units are arranged in different configurations, as shown in switch array 342. The special arrangement of control units in a given switch array is one of the keys to proper operation of switch 100. It will be discussed later. In another embodiment of the switch 100, there is a control unit (not shown) in every two columns 360. In one embodiment of the switch 100, the 130th to 13th Each of the 6 layers contains R concatenated data rows 126, numbered from 0 306 to R-1 308 from bottom to top. Each of rows 160 to 164 contains R concatenated data from the top and bottom. Line 122 and R control (occupied signal) line 124 from the lower layer. An output port number 318. Controlled by the switch array below it (words read the notes on the back before filling this page) ________________________ 31 a 4 ~ Paper Size Chengzhou China Store Standard Cold (CNS) Λ4 Specification (210X 297 mm) 527798 A7 B7 printed by the Consumer Cooperatives of the Central Standards Bureau of the Ministry of Economic Affairs 5. The location of the unit is determined. In the 0th row, the L-level switch array 120 includes a control unit 300 in the first column. The position of the unit [1, 0, L] is determined by the number of columns, rows and layers of the control unit. Therefore, input port 3 1 8 is numbered 1 to match the number of rows of control units connected to it. Similarly, the output port 3 20 is numbered 2 because the position of the port connected to the control unit 322 in the second row is [2,0,0]. The input port 330 is numbered 0 because it is connected to the control unit 324 at position [0, K-1, L]. Output port 344 is numbered 1 because it is connected to control unit 328 at position [1, K-1, 0]. A path 316 is a control unit in a switch array connected to a lower layer through a series of transmission lines. The path is a component of the data bus 120. The path 360 is a series of transmission lines for transmitting a message to the right to a line below the same layer, and it is an element of the data bus 126. Path 33 0 is an occupation signal from a lower layer and is a component of the bus 124. In some embodiments, the switch 100 constitutes an internal network to interconnect multiple processors of a supercomputer. In this structure, the device 350 is one of the processors. In another embodiment of the switch 100, the device 350 represents a connection point from one of the inputs of a switch network, such as within an ATM switch, where this embodiment is used as the switch fiber of the ATM switch. FIG. 3 illustrates the connection between the external device 350 and the switch 100. The external device 3 50 is in the second column, and the 160th row is the 160th. The external device 358 is connected to a different .164 and receives a different travel preparation signal. Similarly (not shown), the external device 3 50 is connected to the output port 3 72, and the occupant signal 3 74 (please read the precautions on the back before filling this page)

32 This paper size applies to the Chinese National Standard (CNS) Λ4 specification (210X297 gong) 527798 Α7 Β7 Printed by the Consumer Cooperatives of the Central Standards Bureau of the Ministry of Economic Affairs 5. Description of invention () and preparation output signal 168. The output address of the external device 350 is the 2nd column and 0th row, which is the same as the input address. The input port 104 of the switch 100 is located at the L-th layer 136, and the output port 154 is located at the 0-th layer 130, or the lowest layer of an embodiment in which the 0-layer switch 100 is omitted. When a message 200 passes the switch 100 completely, there is no inherent indication of the entry of columns and rows for that message. If the application or use of the switch 1000 is to obtain the "source address", then the source address or confirmation is included in the payload of the message. Figure 3 shows a sparse form of the control unit to illustrate the connection. This layout and numbering method is also used to simplify subsequent descriptions. In the implementation of an integrated circuit chip, the control unit is arranged on silicon, which in this way makes the package logic gate closer than shown in the figure. I / O and control timing The input interface to the switch 100 is completed by the line timing and the control signal, and the control signal management enters the line port. Figure 4 shows the timing of one of the messages entering the 402 and leaving the 420 switch 100, as well as the control and line preparation signals that control it. Referring also to FIGS. 1A, 2A and 3, a message 200 enters the switch 100 from the input port 104 and the message leaves the switch from the output port 154. The entry timing of the message is controlled by the bank preparation signal 1 08. The first bit 202 of the message preferably enters the port 104 one cycle after the line preparation signal 108 is activated. If the port occupancy signal 304 associated with the input port 104 reaches the high state, the message 200 will be restricted from entering the input port. The line preparation signal 108 controls all input ports located on a specific line 102, but the port occupation signal 304 is only related to one input port 104. The external device 350 must check the line preparation signal 108 and the port occupancy signal 304 to decide whether the input port 104 can receive 33. This paper size is applicable to China National Standards (CNS) Λ4% 彳 Μ 210X29? Comm.) (Please read the back first (Notes on this page, please fill out this page), νδ 丁

527798 A7 B7 V. Description of the invention () A message. The timing of the row preparation signal 108 and the port occupancy signal 304 is preferably entered into the switch at a clock cycle of 43 before the timing 410 of the first bit 202. In the switch embodiment incorporating the input buffer structure UI 6, the relative timing 410 of the first message bit 202 may be greater than a clock period after the timing signal 408. This embodiment is beneficial to simplify the timing requirements. The first bit 202 of the message 420 leaving the switch reaches the output port 154 at time 428, which is a clock period after the line preparation 156. In the earlier period 426, an external signal is issued by the line output preparation signal 156. The switch can accept an output device occupation signal 376 from an external device, which indicates that the external device cannot accept a message. For example, the external device is a full buffer. When the message of attempting to leave is blocked by the outside, it remains at the switch and attempts to leave later. Printed by the Central Laboratories of the Ministry of Economic Affairs, Consumer Cooperatives (please read the precautions on the back, and then fill out this page) In the embodiment of the switch 100 with the output control structure 180, the timing of the output preparation signal 156 and the first message 420 Bit arrival is delayed by the one shown in Figure 4. In these embodiments, the time between cycles 426 and 428 increases to facilitate the timing requirements of externally connected devices. In another embodiment of the switch 100, the external occupancy signal 3 76 is omitted, and when the message reaches its target port, the message always leaves the switch. Please refer to FIG. 3 for the three-state I / O and timing. In one embodiment of the switch 100, each input connection point is related to a message input connection point from an external device 3 to 50 and a port occupation signal 304 to an external device. even. In this embodiment, each 34

This paper size applies to the Chinese National Standard (CNS) Λ4 specification (210X 297 ^ " T 527798 Printed by the Consumer Cooperatives of the Central Standards Bureau of the Ministry of Economic Affairs 5. Description of the invention () The input port connection point requires two external connection points or pins Similarly, in the same embodiment, two external connection points 372 and 374 are required to support one output connection point. Please refer to Figs. 4 and 5B, the port preparation signal 3 04 is issued at time 408, which is the first of message 200 at time 410. A bit 202 enters the previous clock cycle. Because of the non-overlapping timing condition, the single tri-state connection 504 can adjust the two signals. The external connection 504 is controlled by the tri-state input structure 502, and the external connection 504 At time 408, the output port prepares a signal 3 04, and then receives a message 200 for input. That is, at time 408, the tri-state input structure 502 receives a preparation signal 404 from the sequence signal line 108. At time 404, the external connection 504 Connected to the port occupying signal line 304 for a clock cycle. At time 410, the external connection 504 is connected to the input 璋 104 until the timing signal 408 is received again 514. The tri-state output The input connection replaces the input port 104 and the port occupation connection 304, which is beneficial to replace two external connections with a single pin. Similarly, a three-state output structure (not shown) is an output port 372 and an external port occupation connection The 374 provides a single external connection. This tri-state output facilitates doubling the number of output pins. In the preferred embodiment of the switch 1000, all external input and output connections use tri-state I / O. Tri-state control 504 It will not be pointed out in any subsequent discussions, instead, ports 104 and 174 are used as I / Os to understand that the tri-state I / Os can optionally be obtained. Configuration sequence method The layout completion message of the control unit 300 within the switch array 120 The arrangement of circulation (discussed later) has the advantage of achieving the successful operation and execution of switch 100. Please refer to Figure 3, the switch at a predetermined level and line. 35 This paper size applies to China National Standard (CNS) Λ4 specifications (21〇 × 297ϋ " Τ (Please read the notes on the back before filling in this page)

527798 A7 B7 Printed by the Consumer Cooperatives of the Central Standards Bureau of the Ministry of Economic Affairs 5. Description of the Invention () The layout of the control unit 300 in the array 120 is determined by the configuration sequence. The configuration sequence is generated in accordance with the rule that consecutive units along a given row 360 are preferably alternately located above and below the next row (not shown). In other words, the layout is in the order of up, down, up, down, etc. Furthermore, when any other unit is in the same switch array 120, the switch array layout is always 360 or vertical with no control unit in the same column. The mode of path 316 is performed and there is always a control unit 300 in each column 360 of each switch array 120. Figure 6A illustrates the eight-column configuration generation method. Use zero-based numbering to divide .8 positions (0,1,2,3,4,5,6,7) 602 into an upper half sequence (4,5,6,7) 604 and a lower half sequence ( 0,1,2,3) 606. The final configuration sequence 608 is formed by alternating and combining the upper and lower half sequences. See Figure 63, which shows the configuration sequence 608 in area 632. Line 63 0 divides the area into upper and lower parts, and the display sequence alternates from top to bottom-up-down. Any permutation of the upper and lower sequences can be used to generate a configuration sequence, which facilitates the use of a rule to generate an arrangement, where R is the number of columns in a layer and N = R / 4, each N 値 is selected, if necessary Repeatable. For example, for 8 歹 丨 J 602, 8/4 = 2 so from (4,5,6,7) 604 and (0,1,2,3) 606 select each second 値 to obtain ( 4,6,5,7) 610 and (〇, 2,1,3) 612. These two arrangements are combined into an alternating sequence to form the configuration sequence (0,4,2,6,1,5,3,7) 614. This sequence is illustrated in area 634. Another rule is to use descending sequences (7,6,5,4) 620 and (3,2,1,0) 622, which are combined to form a configuration sequence 624, which is shown in area 636. This alternating-combining operation ensures that the final sequence crosses the upper and lower dividing lines of each position. 36 This paper size applies to the Chinese National Standard (CNS) Λ4 Regulations 210 210X29? (犮) (Read the precautions on the back first) (Fill in this page again),-mouth 527798 A7 B7 Printed by the Central Standards Bureau of the Ministry of Economic Affairs, Consumer Cooperatives, V. Invention Description (630). Generally, any permutation of the number (4,5,6,7) 604 above and any permutation of the following sequence (0,1,2,3) 606 combine to produce an 8-column configuration sequence. Any sequence can be selected and used to place a switch. The preferred embodiment of switch 100 uses the configuration sequence generated by the "Nth" rule just given. One of the configuration sequences used has no limit in length and can be repeated as needed. For example, the sequence 歹 ίΐ 614 can be (0,4,2; 6,1,5,3,7,0,4,2,6,1,5,3,7,0). FIG. 6C illustrates an example of 16 columns 640, which is composed by combining the upper 642 and lower 644 ascending sequences to generate the final sequence 646. In another example 650 uses the "Nth" rule, using each fourth field from 642 and 644 to generate the upper 652 and lower 654 sequences, respectively, which are combined to generate the configuration sequence [J 65 8. This method can be extended to any even array of columns. The sequence of the number of divided columns is two equal divisions: up and down, as shown in the example in Fig. 6A, forming each division and alternately combining the arrangement into a single configuration arrangement. A 4-column sequence can be generated by combining the upper (2,3) and lower (0,1) sequences to generate (0,2,1,3). The only two-column sequence is (0,1). In the example of an odd-numbered column, the sequence of the number of divided columns is an upper and lower sequence with a middle unitary, and can be arbitrarily designated as one of them. The two sequences are then arranged and combined, starting with an arrangement with multiple units. For example, given 7 columns (0,1,2,3,4,5,6), divided into upper (3,4,5,6) and lower (0,1,2) sections, in this example, the upper The sequence has more 値, so the combined sequence becomes (3,0,4,1,5,2,6). The preferred embodiment of the switch 100 does not include a column group consisting of odd columns. Message flow 37 This paper size is applicable to Chinese National Standards (CNS) Λ4 specification (210 × 297 mm) (Please read the precautions below and fill out this page for ordering 527798 A7 B7 Printed by the Staff Consumer Cooperative of the Central Standards Bureau of the Ministry of Economic Affairs V. Description of the invention () Enter a message 200 of the switch to follow a path similar to the path guided by a binary tree group to reach the target column defined by the header 204. Figure 7A illustrates entering the top layer and reaching the bottom target Column A of message A. The address of message A is the second column, that is, the (H1, H2, H3) message header 204 is (0, 1, 0), which means (bottom, top, bottom). Simplify the description of the message flow. Only one data path 3 1 6 is displayed between the selected layers. There is no need to display it in a vertical line and only some representative columns are displayed. Message A 730 surface moving to the right in column 702 Pairs of control units 704 that are connected down to 720 on one of the second layers 762. The second layer is logically divided into two pairs of columns: (1) the columns in the upper column group 710, and (2) the following Columns of group 7 1 2. The indications "up" and "down" do not indicate The positions of the columns of the other layers are directed to the columns of the columns connected downwards. In Figures 7A and 7B, the column 710 of the top portion of the second layer is connected to the column of the top 716 of the first layer. Similarly, the second layer The bottom column 7 1 2 is connected to the bottom half 718 of the first layer. A column group is the same in topology as one group 192 discussed in Figure 1C. The most significant bit of message A is ZERO, which is represented as The target column of the lower column group, however, cell 704 is connected to a column 720 in the higher column group 710. Message A remains in column 702 and moves right to cell 706 in the next row. Cell 706 is connected down to the lower column Column 722 of group 712. Unit 706 sends a message A down to column 722. Therefore, a message that moves right through only one or two control units has a better chance to fall to its target. If (as discussed later Reason) The control unit 706 cannot send the message A downwards, so the message continues to the right of column 702, and it is also connected to the lower column group. 38 This paper size applies the Chinese National Standard (CNS) Λ4 specification (210 × 297). ) Please read the notes on the back before filling this page)

1T 527798 A7 B7 V. The unit 708 of the description of the invention () 712, the message has a chance to fall to the lower group. The first layer 764 is logically divided into two pairs of upper and lower groups 7 1 6 and 7 1 8. A column 720 on the second layer is connected to the pair of groups at the top 716 of the first layer, and a column 722 is connected to the pair of groups at the bottom 718. The address bit ONE below the header 204 represents a group above. On the second level, message A moves to the right in column 722 to the cell 724 connected to column group 712 above the first layer. Unit 724 sends a message down to column 734 of the first layer 764. Level 0 766 is logically divided into four pairs of column groups. The 0th layer is the final destination layer and each column group includes exactly one upper and one lower. The last address bit in the header 204 represents one of the following groups. Message A moves to the right in column 722 and passes through upper connection unit 73 6 to lower connection unit 73 8. Unit 738 sends the message down to the final target column, which is the second column 744. In one embodiment of the switch 1000, the message A moves to the right in the bottom column 742 until the message faces a cell located at the line designated by the message line header 212. On this line, the message is sent down to output port 154 or output structure 1 50. In another embodiment where row addressing is not used, the message is immediately passed down to the next unit 746. The header address "010" is a binary mark '2 ", so message A leaves the second column 742. Printed by the Consumer Cooperatives of the Central Standards Bureau of the Ministry of Economic Affairs ^ (Read the precautions on the back before filling in this page #« <. Move one message to the right in any column has multiple opportunities to move down to the target column group at the next lower level. One message to the right moves in one column to the left (not shown) to the same The entry point 1 74 of the leftmost control unit of the column group. The information in any column in the top layer facilitates any target column with multiple paths to the bottom layer. In each layer, there is only one bit in the message header 204. The element is one The control unit checks to determine the direction of the message: downward or to the right. 39 This paper size applies the Chinese National Standard (CNS) Λ4 gauge (210X297 ^^) 527798 A7 ______B7____ 5. Description of the invention () (Please read the Note: Please fill in this page again) At the bottom level, a message without a line header immediately leaves the switch; a message with a line header 2 1 2 moves to the right until the message reaches the specific behavior, or the message leaves immediately Column to control the structure of one of the row headers 1 50. To increase the number of columns, please refer to Figure 7B and cooperate with Figures 1 and 7A. In one embodiment of the switch 100, the number of columns in each layer can be different, starting from the top In another embodiment, the number of columns R 1 70 related to the size of the switch 1000 is the number of the bottom layer. In a preferred embodiment of the switch 100, the number of columns R in each layer is the same. R Is a power of 2. Figure 7B shows the three layers of the embodiment of the switch 100, where the top layer has four columns 774, the next layer has eight columns 776 and the bottom layer has sixteen columns 778. The number of columns in each layer need not be different For example, in one embodiment, the number of columns from the upper level may be 8, 8, 16, 16, 32, and 64. Another example embodiment has a number of columns of 32, 32, 32, 64, 64, 128, and 128. The Central Standards Bureau of the Ministry of Economic Affairs's Consumer Cooperatives printed a column positioned on layer 776, the number of columns is greater than the number of columns on the previous layer 774. This column has the control unit alternately connected 770 and not connected 772 to a unit to the upper level. See also Figure 3, a switch array 120 always has a control unit in each row of 3 60. See also Figures 20A, 20B, and 20C. One embodiment of the switch 100 is not an output connection point that is possible on the top layer of an external device. In this embodiment, there is less congestion in the information flow on the top layer. To be sufficient Using logic gates available in the chip, the top layer has fewer columns than the lower layer. Message flow and message blocking When two messages in different layers compete for the same data path, 40 paper standards in the lower layer apply Chinese national standards (CNS ) Λ4 specification (210 × ^ 97 male i) 527798 A7 B7 The employees of the Central Standards Bureau of the Ministry of Standards and Consumers Co-operative Air Co., Ltd. V. Invention Information () has priority. The method described here gives priority to lower messages because the latter may stay in the switch longer. The structures and techniques used to implement this priority are illustrated in Figures 8 A and 8B. Figures 8A and 8B show a simplified control unit interconnection. All the units in Figures 8A and 8B have different positions in the switch array. They are in two layers 830 and 832 and four rows. Referring also to Figures 1A, 2, 3 and 7A, the control unit 804 is located in the switch array 120, one of the third layers 832. The control unit is connected to the right by a column 3 60 to the control unit 806 in a row below the same layer. The message A 802 with the header 812 enters the control unit 804 from the upper layer. The message A communication bit 202 is ONE, which indicates that a message is in the unit 804. When a message enters a control unit from the upper layer, the message remains in column 360 and immediately moves right to the control unit in the next row. Message A proceeds right in column 360 to cell 806. The most significant bit of the A header of the message is ONE, which indicates that the message is directed to one of the bottom 850 columns. The control unit 806 checks the communication bit 202 and the most significant bit 208, and decides that the target layer below the message A is listed as a top group. The control unit 806 is connected down to the control unit 820, which occurs in the group 850 above. Therefore, message A is sent down to the control unit 820 in a series of paths 316. Following the rules for messages entering from the upper layer, message A is immediately sent right in column 822 to the next unit 824 in the second layer. The flow of message A802 is described in FIG. 8A. Message A enters the third layer from the upper layer, moves to the right to the next line, and is immediately sent to the desired paper size of 41. This paper applies the Chinese National Standard (CNS) M specification (210X 297 mm) (Please read the back Note: Please fill in this page again) 527798 A7 B7 Printed by the Employees' Cooperatives of the Central Bureau of Standards of the Ministry of Economic Affairs ^ V. Description of the invention () A unit of the group 85 0 listed above. Message A is directed from unit 806 to unit 820 because the most significant bit 208 of message A indicates that it falls into an upper group and the message is not blocked by another message from below. This description indicates that in this example, a message A is allowed to be moved to the next lower layer without delay. Messages moving to the right in a layer pass down the connection point to the control unit. The connection alternates between 850 above and 852 below the next lower group. In another example (not shown), a different message E enters the control unit 806 from the left. The most significant bit of message E is ZERO, which indicates that the message is directed to one of the following groups 852. The control unit 806 is connected to the upper group 850, so the control unit 806 sends a message E to the right to the next line to unit 808. Referring to FIG. 8B, in another example, the same message A 802 enters the control unit 804 from the upper layer and is sent to the control unit 806 to the right, as described above. While message A enters control unit 806, message B on the second level enters control unit 820 from the left. Message B has priority over messages from upper layers using shared path 822. Message B continues right to cell 824 in column 822, thus preventing message A from moving downward through cell 820 and to the right in column 822. Because the column 822 is immediately occupied by the message B, the control unit 820 cannot receive the message from the upper layer (that is, from the control unit 806). To avoid the collision of messages A and B, the unit 820 sends the occupied signal upward to the unit 806 on the signal path 330. The control unit 806 is therefore blocked by the occupation signal 842 and cannot transmit the message A downward. Therefore, unit 806 sends message A to the right of unit 808 on the next line. Unit 806 sends the occupancy signal 842 upwards to protect message A from the same. 42 This paper size applies the Chinese National Standard (CNS) Λ4 specification (21〇 / 297). (Please read the precautions on the back before filling this page)

527798 Printed by the Consumers' Cooperative of the Central Standards Bureau of the Ministry of Economic Affairs A7 ________ V. Description of the invention () Message C may collide in the upper layer. The control unit 808 checks the header 812 of the message A and determines that the message A is directed to the group 850 on one of the second layers. Because unit 808 is connected to a group, unit 808 is forced to send message A to unit 810 to the right again. In order to avoid the possible collision mentioned above, the unit 808 also transmits an occupation signal to the upper layer. It is possible to prevent a message D, which may be above the cell 808, from falling to the cell 808. Finally, the control unit 810 in the next row is connected to an upper group 850. Because the message A in the unit 810 is not blocked below, the unit 810 sends the message A down to the control unit 826 in the second layer. The circulation of message A is depicted in Figure 8B, where the message is blocked by another message B that moves directly to the right at the same time and cannot be moved down immediately. Before message A moves down to one of the upper group on the second level, message A enters and exits more than two lines and goes to the right. Whenever a message moves right through a control unit, the unit always sends an occupancy signal up to the unit above it, which prevents the latter from sending the message down. Message circulation relationship Figure 8B illustrates that message B blocks message A from moving downward. Similarly, message B may be blocked by a message or the following messages and become forced to remain on the second floor for an extended period of time. It is beneficial to avoid message B in a position where message A is once blocked by the interconnect structure. The control unit 806 on the third layer is connected to the unit 820 on the second layer through the data channel 316, and the control unit 810 on the same row as the unit 806 is connected to the unit 826 on the second layer through the data channel 848. Unit 826 is not on the same column as unit 820 in the hope that message B will block message A twice, and it is beneficial to 43 paper standards that apply the Chinese National Standard (CNS) A4 specification (21〇X 297 ^ > i.) (Please read the notes on the back before filling this page)

527798 Printed by the Consumers' Cooperative of the Central Bureau of Standards of the Ministry of Economic Affairs A7 B7 -----------5.-Description of the invention () Eliminate the possibility of repeated blocking. The configuration sequence produced by the method described in Figures 6A and 6C can avoid multiple blocking for a single message. Fig. 9 illustrates the connection relations of the units on the third layer 902, the second layer 904 and the first layer 906, respectively. The configuration sequence at layer 3 (0,4,2,6,1,5,3,7,0, ...) 614, the sequence below layer 2 (0,2,1,3,0, ···) 910 and the above sequence (4,6,5,7,4, ...) 912 and the sequence of the first layer (0,1, 〇, ...) 918 are shown graphically. Message path A 634 shows the interconnection relationship between the third layer and the second layer. Note that messages starting in any column, such as column 0, remain in that column. The message path A starts from the 0th column of the first row 95 2, and the first row 952 goes down to 920 to a cell that is also at the 0th column 962. In the next row 954, column 0 is connected downward to 924 to one of the cells in column 4 964, and then in 956 to one of the cells in column 2 966 and so on, according to the sequence 614. The message path B 934 on the second layer shows the connection sequence between the second layer 904 and the first layer 906. The message path B starts from the 0th column of the first row 962 and goes down to a cell which is also at the 0th column 972. In the next row, column 0 is connected down to one of the cells in column 974, and then to one of the cells in column 966, etc., according to sequence 910. The message connection paths A 634 and B 93 4 illustrate two important properties of this configuration sequence. First, path A and path B are alternately connected downward to the following group 944 and the above group 942, which conform to the message transmission path described in FIG. 7A. Second, path A is no longer connected to path B until it has traversed the eighth line. The difference is that path A is connected down to path B at positions 962 and 920 (the full range of eight rows). Similarly, the second line 954 is connected to the path A 63 starting at 964 (not shown). The news on this paper 44 applies to the Chinese National Standard (CNS) (210X 297 public power) (please first Read the notes on the reverse side and fill in this page), 1T 527798, printed by the staff of the Central Standards Bureau of the Ministry of Economic Affairs, A7, B7, and F5. Invention Description () The information is no longer connected with path D, until it has crossed eight lines. Furthermore, the message moving in any column of layer 3 is not connected to the path of layer 2 below 934 until the message has moved through eight lines. That is, some of the connections shown between the paths A 634 and B 934 are reserved for any path starting at any row and column of the third layer. It is important that before the 920 blocking situation reoccurs, the message starting on path A 952 is blocked by 3 other messages on the second layer and the message starting on path B 962 is 4 or 5 on the first layer at the same time Blocked by other messages. It is therefore statistically impossible for multiple barriers to occur for any message at the lower levels. The relationship between path B 934 on the second level and path C 936 on the first level is that the information of path B will not face path C until it has crossed four rows 962 to 968. Figure 9 compares the individual connection relationships between message path A and message path B. The message on path 962 is initially located on the message blocked on path 952. It is important, however, that message B is not in a position to block message A during the next eight sequence moves of each message. Figure 9 also illustrates that the message of path C 936 on the first layer blocks the message of path 962. The message of path C will not be located at the position of blocking the message of path B again until the message has crossed four lines. This relationship is reserved for messages entering any column and any row of the Zambian layer. Furthermore, each message in any layer except the 0th layer can always be transmitted alternately in the upper group and the lower group, and transmitted on each line. Other embodiments of switch 1000 use other sequences, such as described in the discussion of Figures 6A, 6B, and 6C. Any sequence can be used to allow a message 45 This paper size applies to the Chinese National Standard (CNS) (210 × 29ϋΓΤ (Please read the precautions on the back before filling this page)

527798 A7 B7 Printed by the Consumer Cooperatives of the Central Bureau of Standards of the Ministry of Economic Affairs 5. Description of the invention () 200 At least one cycle is connected to the above and the following groups. The sequence of all columns does not have to be the same, and the sequence does not have to repeat cycles related to the number of levels or any other design rules. This sequence need not have the statistical nature of fair information flow generated by using the "Nth Value" rule discussed in Figure 6A, with minimal blocking and low latency. Reduced header length When messages are transmitted between layers, the header length is shortened by removing the most significant header bit in each layer. Referring to FIG. 10, in the third layer, the target column address of the message is defined as a message header 204 including three bits HI, H2, and H3. H1 208 is the most significant bit of the address, and H2 1054 is the next most significant bit. When the message 200 moves down to the lower layer below, the most significant bit H1 208 is removed from the message, although the communication bit 202 is always reserved. At the second level, H2 1 054 thus becomes the most significant bit. The expected side effect of changing the header length is that the message length is reduced by one bit per layer. When the message 200 reaches layer 0, all bits of the header 204 are removed, thereby reducing the total time for the payload bits to pass through the switch (latency). Because the MSB 208 of this layer always follows the communication bit 202, the design of all control units in all layers (at layer 0) is the same, which can simplify the chip layout. Another advantage of removing the current MSB when sending a message downward is that a control unit only needs to buffer a bit that is close to the previous two bits of the message. Alternatively, if the MSB has not been removed, the lower-level cells will have to wait until the entire header enters before the appropriate address bits are checked by the cell. In this unfavorable situation, an 8-bit header needs to enter _____ every time the message 46 This paper size applies Chinese National Standard (CNS) / \ 4 坭 掐 (210X297 public place) (Please read the note on the back first (Fill in this page again)

527798 Employees of the Central Bureau of Standards of the Ministry of Economic Affairs printed A7 __________ B7_ V. Description of the invention () Nine bits are buffered in each unit when the unit, and the control unit of the preferred embodiment of the switch 100 only needs to be Compared to one or two clock cycles, each unit will take nine clock cycles. Synchronous Delay Element Refer to Figure 11A and cooperate with Figures 1B and 3 to move right through a column of 360 messages to encounter a proper FIFO structure 114 and loop back to the first row. In order to avoid the first bit of the first message colliding with one of the internal bits of the second message, a message is generated to match one row of each layer. For this reason, in addition to using a register along one row, another can be used. Delay device. The FIFO array includes a plurality of independent synchronous delay devices 1 1 00 arranged in parallel, each connected to a column 3 60. The synchronous delay device 1100 includes serially connected delay elements 1 102. The function of a clock delay element 1 102 is like a one-bit shift register or a D flip-flop, so that one bit of the delay element is entered in one clock period and the output of the delay element in the next clock period appear. The entire transmission time of a message bit through the serially connected delay element device 1100 is the number of delay elements included in the structure 1100 times the clock period. A message 200 enters the FIFO structure 1 100 from the left side of the serial output terminal 1106 and leaves at the output terminal 1 108. The clock 1 1 10 is used to synchronize the delay element 1 102. A reset signal (not shown) initializes all delay elements and other logic elements. Figure 1 1B shows the use of a dual-phase clock 1116 to shift the data bits through one of the FIFO structures dynamically. When compared to a flip-flop or similar delay element, a dynamic shift register has the benefit of reducing the number of transistors. Figure lie. Fig. 1 shows an optical embodiment 1114 of a synchronous delay device. 47 This paper size applies the Chinese National Standard (CNS) Λ4 & grid (210X2077 > i " 7 ---------______ 丁 ______. 0 Μ (翱 Please read the precautions on the back before filling this page) Printed by the Central Standards Bureau of the Ministry of Economic Affairs, Consumer Cooperative ¾ 527798 A7 B7 V. Description of the invention () The adjustable fiber delay can be achieved by using a piezoelectric material structure to physically extend the fiber and change the fiber length. It is driven by a pulsed light source An optical fiber 1116 transmits the message 200 through the length of the optical fiber and is terminated by an optical detector 1120, which converts the optical signal into a form that can be further processed by the switch 100. For layer and line timing, see sections 8B and 12A In the figure, the message A 802 entering the control unit 806 on the third layer 832 can attempt to fall to the control unit 820 on the second layer, where the message A moves to the right in the serial path 822. However, the second layer Message B 840, which is moving to the right, has higher priority than message A using path 822. To force priority, control unit 820 sends an occupation signal 842 up to control unit 806 in a timely manner to prevent the latter from being transmitted down Therefore, specifying the timing of message circulation allows the occupied signal 842 to reach the control unit 806, which is enough time for the latter unit to act on the signal. Therefore, in one embodiment of the switch 100, the communication bit of message B 202 Arrive at unit 82 0 before communication bit 2 2 of message A reaches unit 8 0. All control units in a given switch array 120 operate synchronously so that the communication bits of the message reach the units in the switch array at the same time. All units in the same switch array 1 20 receive the same timing signal. Please refer to Figure 12A and cooperate with Figure 11A. Clock 1110 controls the delay element in the control unit 300. Compared to clock 111, the latch setting The signal 1204 is delayed by 1210 so that the unit's latch (discussed later) is set later in the clock cycle. In one embodiment, the control unit in the lower layer is the same as the upper layer. ____ 48 paper dimensions Applicable to Chinese National Standard Li (CNS) Λ4 gauge (210X 297 Gong " 7 (Please read the precautions on the back before filling this page)

527798 A7 B7 V. Description of the Invention (1) A control unit receives message 200 first. The relative timing of messages on the same line at different levels is shown in Figure 12A. The latch setting signal 1204 of the layer 0 occurs one clock cycle earlier than the latch setting signal 1206 of the layer 1. The first layer signal is one cycle before the second layer 1 208, and so on to the higher layer. The latch setting signal is used for timing and control of message flow. The timing signals 1110, 12 04, 12 06, and 1208 for all layers and lines are generated by the timing unit in cooperation with the delay elements 146 and 148. Figure 12B depicts the relative timing of adjacent rows in the same layer. A message 200 enters one of the j-th control units at the same clock cycle 1110, where the latch setting signal 1220 of the row is high. A message moving to the right in a row 360 passes a certain number of delay elements before the message reaches the next row j + 1 1232. In some embodiments, the delay element is a FIFO buffer between lines. In other embodiments, the delay element is part of a control unit. The time period of a single delay element is one clock period 1202 or two periods. The line-to-line time% 1240 is the time it takes for the message to reach the next control unit on the next line. The time t. Is the sum of the delays of all the delay elements between the two lines. Therefore, the latch setting signal of the next line 1230 is time t. The latch set signal of the first line 1220 delayed by 1242. Printed by the Central Bureau of Standards, Ministry of Economic Affairs, Shellfish Consumer Cooperatives ^ (Read the precautions on the back before filling out this page) A message 200 has a predetermined maximum length of Lmsg 214 and each bit takes a clock cycle to move through a given Point. The time for the message to pass through the control unit on line j is represented by interval 1222, and the next line is represented by interval 1232. The time between messages tm1 242 is not less than the time that messages pass through a control unit, that is, tm ^ Lmsg.tD. Immediately after a message passes a control unit, a subsequent message is allowed to enter the unit. Therefore, time tm 49 This paper size applies Chinese National Standards (CNS) Rule 8 (2l0x29D > ^) 527798 A7 B7 Printed by the Central Consumers Bureau of the Ministry of Economic Affairs and Consumer Cooperatives V. Invention Description () Decide when to send the next A latch sets the signal 1224. At any given level, the messages in different columns move to the right in parallel, so that the communication bits 202 and the following bits of all messages move to the right in a "vertical alignment". In vertical alignment, each communication bit enters a control unit at the same time, while all other units are in the same switch array. In the same way, in the same switch array, the message from the control unit to the falling together moves down in a horizontal alignment. Time t. Less than the time tm between messages, the message will traverse more than one control unit. The message therefore passes through the switch in a wormhole path. In a general embodiment of the switch 100, time t. For one or two clock cycles, it turns out that the area bits before the payload leave the interconnect structure before the tail end of the payload enters. The timing of the latch setting signal for a particular control unit is determined by the row and layer positions of the units in the switch array. Figure 12A depicts the inter-layer relationship of the message timing in a single row and multiple layers. Figure 12B illustrates the relative timing of the latch setting signals of adjacent rows in a single layer. In the discussion of Figs. 12A and 12B, the terms "layer latch setting" and "row latch setting" mean the same signal ', which is based on the description. Please refer to Fig. 1A, the main signal is provided at the timing of the switch array of the 0th row and the 0th row. The layer above the switch array of layer 0 and row 0 is delayed by one clock cycle 146, which completely determines the timing of the first row of all layers. At each layer, each of the signals from the right to the consecutive rows to the right is delayed by the delay element 148 for a period of t 1240, thus determining the timing of the remaining switch arrays to the right at the same layer. Control unit status Figures 13A and 13B show the control unit components and the passing control unit -------------------- 1 ) 50 This paper size applies Chinese National Standards (CNS) Λ4 ruling (210X 297 ^^.) Printed by the Central Standards Bureau of the Ministry of Economic Affairs, Shellfish Consumer Cooperative, printed 527798 A7 ____ B7__ 5. Block diagram of the message sending mechanism of the description of the invention () . From the left, enter one of the control units 1 300 in line W 1302. Message 200 is (1) sent down through line S 1312 to the next layer, as shown in Figure 13A, or (2) sent to the right through the message. Line E 1304 goes to the next line, as shown in Figure 13B. A control unit 1 300 has a message entry point from the upper level of line N 1310, a message entry point from the left of line W 1 302, a message exit point to the right of line E 1 304, and a message exit down to line S 13 12 Point, one to the occupancy signal output terminal of the upper layer BN 13 03 and one to the occupancy signal input terminal of the lower line BS 1 306. In the figure, the terms "north", "south", "east" and "west" mean the directions of "up", "down", "right" and "left", respectively. Referring to Figs. 3, 13A and 13B, the serial path 360 connects the lines E and W of the control units in adjacent rows and the same column. The serial path 316 connects the lines N and S, and the serial path 3 30 connects the lines BN and BS of the control units in the same row. A latch setting signal 1204 is connected to the control unit at 1 32 8. The delay elements D0 and D1 1102 are provided as means for "looking forward" to specific message header bits or as means for adjusting the timing of message flow. In Fig. 13A, the message C enters the control unit 1 300 from the left side of the line W 1 302. The two message bits (ie, the MSB 208 of line W and the communication bit 202 in D1) and the occupied signal line BS 1 3 06 are checked by the control unit and the unit determines that the message is to be sent down through line S 13 12. The input line W 1 302 is connected to the line S so that the message is two bits before the relative timing 1 322. Because message C moves down, line L is not connected to input line W from the left. Instead, the line E is connected from the upper layer to the input line N 1 3 1 0. The state of the unit in Figure 13A is indicated by ZERO, which is stored in the latch 51

This paper size applies to Chinese National Standard (CNS) / \ 4 坭 格 (21〇X 297 ^ > ^ T (Please read the precautions on the back before filling this page)

527798 A7 B7 Printed by the Consumers' Cooperative of the Central Standards Bureau of the Ministry of Economic Affairs V. Invention Description () 1316 (—bit register). The occupancy signal passes a ZER0 up to line BN 1 3 08, which is connected to the latch output. This means that the unit is free to send messages down to line N 3 1 0 of the interconnect structure. The latch 1 3 1 6 is also used to control the flow of subsequent data bits through the unit. As previously discussed, when a signal is sent from left to down, another message from the upper layer of line N 1310 is allowed to enter the unit, where the signal is sent to the right on line E 1304. In Fig. 13B, the message enters the control unit 1 3 00 from the left of the line W 1302. The most significant bit 208 of the header and the occupancy signal on the lower line BS are checked by the control unit. The message MSB 208 indicates that the message cannot be dropped, or the occupied signal on the online BS 1 306 is the signal 値 ONE indicates that the message is blocked below. In the example of Figure 13B, one or both of these cases are true. The message D is transmitted to the right through the delay elements D1 and D0 to the output line E 1 3 04. Latch 13 16 is set to ONE. The occupied signal 1308 of the online BN is connected to the latch 1316 of the signal ONE. The occupation signal 1 308 is transmitted to the upper unit to indicate that it is blocked from transmitting the signal downward. The output line S 1312 is set to ZERO, which is equivalent to not transmitting a signal downward. Detailed description and flowchart of the control unit Fig. 14 is a flowchart illustrating a method of controlling message flow through a control unit 1300. Fig. 15A is a detailed explanatory diagram of a preferred embodiment of the control unit described in the flowchart of Fig. 14; Referring to Figures 13A and 13B, the two states of the control unit 1 300 are shown in separate block diagrams. Figure 13A shows the message moving down from the left

52 This paper size applies Chinese National Standard (CNS) Λ4 疋 台 (210X297々i " T (Please read the precautions on the back before filling this page)

79 7 2 5 Printed by the Employees' Cooperatives of the Central Bureau of Standards of the Ministry of Economic Affairs A7 __ 一 ___B7 V. Description of the invention () Move to the bottom level. Figure 1 3B shows the state where the message moves from left to right on the same layer. Fig. 13A also shows a state where there is no message from the left. Refer to Figure 14 and match Figures 12A, 13A and 13B. When the latch setting signal 1 328 reaches the high state 1404, the necessary information required to determine the message direction 1406 can be obtained in the delay element of the control unit, as well as the input line W 1 302 and the blocking signal line BS 1 306. In particular, when the latch setting signal reaches the high state, the message communication bit 202 is retained on the delay element D1 1324 and the most significant bit of the header exists on the input line W 1 3 02. Three possible results 1408, 1410, and 1412 are due to tests that determine the direction of the message. First, the message from the left is present and blocked by the lower layer, or the message header indicates that the message must be moved to the right by 1 408. Second, there is no message 1 4 1 0 from the left. Third, the message from the left exists and is not blocked by the lower layer, and the message header indicates that the message must be moved downward by 1412 ° The latter two cases (that is, there is no message from the left 1410 or when the message is downward Move 1 4 1 2 to deal with the single case of occupying the signal to the upper layer. In one of these two cases, the latch 1 3 1 6 is set to ZERO and the latch output is sent upward to the upper unit. That is, the control output BN 1 3 08 is always connected to 1402 to latch 1316. In other cases where the message is present and must be moved to the right 1 408, the latch is set to ONE. This latch can be used to store the control state of the unit and subsequent controls are individual The unit logic gate of the message cycle. Please refer to Figure 14 and cooperate with Figure 10. When the message exists and move to the right 53 This paper size applies Chinese National Standard (CNS) Λ4 Regulations (210 × 297々 ^) (Xu Xian read the back (Notes for filling in this page)

、 1T f, 527798 A7 __ ^ printed by the Consumers ’Cooperative of the Central Bureau of Standards of the Ministry of Economic Affairs V. The special case of the invention (the most significant bit 208 is removed from the header, so it is one bit below the header address Element 1 054 then becomes the most significant bit in the lower layer. The signal 値 ONE is transmitted downward 1412 for a clock period 1414, so that the signal on line S 13 12 is set to ONE to generate a communication bit 202 of a downward message. In the next clock cycle 1414, the desired new most significant bit 204 (previous bit 1 054) is transmitted to the unit below the output line N 1310. When the cycle 1414 is completed, the output line W is downwardly connected through the line S 1416 to allow other messages to flow through the control unit 'until the interrogation signal again reaches the state 1404. The next most significant bit 1 054 immediately follows the communication bit 202, thus removing the current most significant bit 208 and helping to allow the message timing to jump before the message in this layer to match the timing of the message in the lower layer. Pulse cycle. The control unit 1 500 is initialized by setting all delay elements and latches to one of the ZERO start or reset signals 1420. The flowchart of Figure 14 describes controlling a cell with a single downward path and to the right. One of the flat latency units described in Figures 18A, 18B, and 18C is controlled by a generalized flowchart in which multiple input paths are checked together and the priority of the same layer is additionally considered. The relative timing of the latch setting signal shown in Figures 12A and 12B is shown in the lower layer 1204 message one clock cycle ahead of the upper layer 1206 message. Therefore, a downward message jumps to a clock cycle before the current timing of the message. Furthermore, the shortening of the header length causes another jump to the previous clock cycle. The effect of steps 1412, 1414, and 1416 shown in Figure 13A is to perform the desired reduction of the header length and change the communication bit of the downward message (please read the precautions on the back before filling this page). Order 54 paper sizes Applicable to Chinese National Standards (CNS) Λ4 regulation (210X 297 public welfare) 527798 A7 B7 V. Description of the invention (Printed by the Bayer Consumer Cooperative of the Central Standardization Bureau of the Ministry of Economic Affairs and synchronized with the timing of the lower layer. Input line W 1302 is directly connected Line S 13 12 enables the two delay elements D1 and DO to be crossed to achieve the desired effect of two clock cycles in advance of the timing of the message. Please refer to FIG. 15A and cooperate with FIGS. 11 and 13A, which further describe the control unit in more detail. 1 300, such as control unit example 1 500. Unit 1 500 is a gate diagram showing two delay elements D1 1510 and D0 1512, latches 1 3 1 6, output and input connection lines and logic gates to control messages Many logic gates are controlled by latch 1316. When the latch is set to ONE, messages from left on line W 1 302 circulate from left to right and leave from line E 1 304. Switch 194 can avoid coming from the connection On line N 1310 The message from the above unit leaves the line E. When the latch is set to ZERO, the message from the left flows downwards and leaves the line S 1 3 1 2. The 値 of the latch 1 3 1 6 is always transmitted upward through the line BN 1 308 to indicate whether the above unit can send messages downwards. One message from the upper layer of line N 1 3 1 0 is allowed to flow to the right through line E 1 304. See Figure 2 and Figure 7, a message enters Connect to a control unit in one of the groups listed below or one of the following groups. The communication bit 202 indicates whether a message exists. If the communication bit is ZERO, no message exists and the control path is the same as the actual downward message .The most significant bit of the header 208 indicates the designated destination. In particular, 値 ONE indicates the target in the above group, and 値 ZERO indicates the target in the following group. This paper size is suitable for China National Standards (CNS) Λ4 specification (210X297 mm) (¾Read the precautions on the back before filling this page)

5277% A7 B7 Five invention description () Table 21 Control unit status header Most significant bit (online W) Communication bit (at D1) Control unit connected to the upper group Control unit connected to the upper group 0 0 Down (South) downwards 0 (to the bottom) 1 right (east) downwards _ U to the top) 1 | downwards to the right, printed by Manchuria Central Standards Bureau Ordnance and Consumer Cooperatives, table 2 combines two types of message bits To determine which direction the message passes through the unit. When the latch setting signal 1 328 reaches the high state, the message bit is at the delay element D1 15 10 and the most significant bit 208 is on line W 1 302. In the case where the message with the most significant bit set to ZERO (the location of the unit below) enters an upper connection unit, the message is sent to the right and a signal is sent to the unit to the upper layer. Do not send the message down. Or, if the same message enters the connection unit and is not blocked below, the message is sent downward. Therefore, relative to the highest significant bit of the header, the control gates of the lower and upper connection units are complementary. In the case of using unit 1 500 connected to the above group, gate 1 576 is used. In the case of units connected to the following groups, gate 1 576 is used. It should be noted that because the upper link unit seeks ZERO to determine whether the message should move to the right, the communication bit 202 in the delay element D1 must be used to distinguish between the actual right message and the absence of the message. In some embodiments of switch 1000, timing is used to decide when a message leaves layer 0. In other embodiments, the row header 212 is used. Figure 15B shows the special control unit that processes the header of this row at level 0. Please refer to Figure 15B in conjunction with Figures 2B and 12, when the line number coded in the header of the line is 7, the paper rule Chinese storehouse standard pool ((, NS)) M specifications (210X 297 mm) (read first read Note on the back, please fill in this page again.) Order 527798 A7 ____B7 V. Description of the invention () When the number of rows of the control unit printed by the Department of Economics' Central Standards Bureau Bingye Consumer Cooperative, a message including a header 2 1 2 200 leaves the control unit 1 550 of the 0th level. When the latch setting signal 1 328 goes high, the header logic 1 5 68 simultaneously checks all bits of the control bit 202 and the row header. If the header bit The number of lines that match the location of the unit and the message is not blocked by 1 556 below, then the message is sent down 1 562. To avoid the output of the row header 212, the line S to the lower layer 15 62 is connected to the first payload bit Element 206. The latch 1 566 stores the state of the unit and controls the message flow to the latch 1316 of the unit 1 500 in a similar form. _ High-speed timing and birch Figure 12A is a timing diagram of an embodiment of the switch 100, in which the message header Bits go down at a rate of 1202 per time period Move through the switch. Figure 13B shows the message moving to the right in a column through two delay elements 1102, so that it uses two time periods to move right to the next unit. Figure 16A is designed to reduce latency Timing diagram of another embodiment of the switch 100. In this embodiment, all layers in a given row receive the same latch setting signals 16Ό4, 1 606, 1608, etc. In this embodiment, the message flag The header and the message payload bits moving to the right in a row pass only one delay element, and therefore use only a time period of 1110 to move to the right. The header bits use one time period to move down to the next layer. The payload bit is directly connected to the lower-level cell with a delay of less than one clock period. The delay refers to the propagation delay of a few gates in the cell. See Figure 16B, which shows two high-speed peers in adjacent layers. Control unit 1 620 and 1 622. At the beginning of time period 1202 and the latch setting signal 1 604 reaches the high state, the message entered from left 1 302 (please read the precautions on the back before filling this page) ), \ One 5 This paper is the standard state of China in China (('NS) Λ4 specification (210X29 * 7mm) 527798 A7 B7 V. Description of the invention () Communication bits 202 and MSB 208 are online W 1302 and delay respectively Element DO 1618. The three gates of circuit 1612 process these bits with the occupation signal BS 1 306 値 and immediately transfer the result to circuit 1314. Similarly, the circuit 1614 transmits its output 13 08 to the upper layer. The lowest circuit 1614 stabilizes, first transmitting the output upward and setting the above circuit in a ripple manner. The propagation delay of circuit 1614 multiplied by the number of layers is less than one clock cycle 1202. When the latch setting signal 1604 reaches the high state and the state of the capture control unit 1620, all the circuits stabilize. 32-port switch Refer to Figure 17 and in conjunction with Figure 1A, an embodiment of a 32-port switch has four layers 1702, 1 704, 1 706 and 1 708 and four rows 1780, 1782, 1 784 and 1 786. One layer consists of 8-columns 3 to 60. The number of ports in the embodiment is the number of columns (8) per row multiplied by the number of rows (4). Therefore, the illustrated switch includes 8 * 4 = 32 input ports 104 and 32 output ports 154. To simplify the description of the switch 1700, some components of FIG. 17 such as the FIFO buffer 114 and selected input and output control structures 110 and 150 are omitted. Printed by the Central Standards Bureau of the Ministry of Economic Affairs and Consumer Cooperatives ^. (¾Please read the notes on the back before filling out this page) Please refer to Figure 17 and cooperate with Figure 3. The easy way to arrange the control units includes selecting a single row first, and the row The control units are configured with the same configuration on each floor. In this example, the leftmost row is selected, and the 0th row is 1780. In the 0th row 1708, the 3rd layer 1 702 switch array 120 has control units arranged in the same configuration. The control unit numerical designation at line 0 is defined as the number of columns of the unit. A control unit 1712 on the third layer 1 702 from 0 to 1710 is located in the first row 1 780, and the number in the unit is marked as "0". Similarly, the same configuration and markings are placed on line 0 of 1780. The paper size is suitable for Sichuan National Standard Cold (CNS) Λ4 specification (210X297 mm) 527798 A7 B7 i. Description of the invention () All layers. After finishing the 0th row, select a layer in the switch layout for the next step. You can choose any layer, but it is most convenient to select the top layer first, which is the third layer 1702 in this example. The control units are arranged in the same configuration across the 3rd floor. The digital designation in the control unit is derived from a configuration sequence. Referring to Figures 6A and 9, select an 8-column configuration sequence 614 for switch 1700. Other 8-column sequences such as sequence 60 8 or 624 can also be selected. Using sequence 614, the third column 010 1710 has a first control unit at position 0. The control unit 1 300 or the ripple unit 1620 can be used in the switch array 120. In the illustrated embodiment, all units that are switched above the 0th layer are switches of the same type. The cell number in column 0 comes from the sequence 614 (0,4,2,6,1,5,3,7,0, ...), which determines the column 634 connected downwards. Therefore, the unit numbers in column 0 (1712, 1714, 1 71 6 and 1718) are 0, 4, 2 and 6, respectively. The first cell in column 1720 is at position 1, so that the cells in columns (1722, 1724, 1 726 and 1 728) are numbered 1, 5, 3, 7. The same left-to-right layout method is used to number the control units of the remaining columns of layer 1702. The next step in the layout of the switch 1700 is to configure the control unit, which is the second layer 1704, below the layer just completed. The control unit number on the third floor 1702 indicates the place where the control unit on the second floor is arranged. On the third layer, the 0th column 1710, the first row 1 782, and the control unit 1714 are numbered 4, which indicates that the unit located in the lower layer 1 744 is arranged in the U column. Continued from left to right, the unit 1716 is numbered "2", which means that the unit on the second layer relative to the lower layer 1744 is arranged in the second column. All the control units under the top layer are in accordance with the Chinese National Standards (CNS) Λ4 specification (210X297 mm) (read the precautions on the back before filling in the purchase). Cooperative print 527798 A7 B7___ 5. The column position of the description of the invention () is determined by the number of units in the upper layer. The next step is the numbering of the units arranged on the second layer 1 704. Level 2 1704 includes two column groups 1 750. The following group sequence is (0,2,1,3,0, ...) 910. The sequence of the above group is obtained by adding 4, and the sequence (4,6,5,7,4, ...) is 912. The above method is used to number the third layer, and the unit numbers in the 0th column 1 730 of the second layer are 0, 2, 1 and 3, and the rest of the lower columns use the same sequence and method number. The unit numbers of column 1740 in column 4 are 4,6,5 and 7, which are also used in the rest of the above group in layer 2. Units on layer 1 1706 are also configured using the number of the unit above them. Cell numbering on level 1 uses four 2-column sequences (0,1,0, ...), (2,3,2, ..), (4,5,4, ..) and (6, 7,6, ..) 918. The 0th layer 1708 (lowest layer) has the same layout, that is, the control units are arranged in the appropriate columns with the numbers of the above units. On the 0th layer 1708, the number of the control unit is the number of columns, which also determines the number of the output ports 154. I?. ^-XJh industrial and consumer cooperation shirt in the warp section ^ (^ read the precautions on the back before writing this page) In short, the number of the embodiment of the switch 100 is determined by the number of rows per layer 164 and the number of columns. The number of columns R is preferably, where L + 1 is the number of layers. It is most convenient to lay out the cells first with the same configuration, starting from the leftmost row 1 7 80, line 0 and spanning the topmost 1 702. The number of cells in row 0 is the same as the number of columns. The remaining cells in the switch array 120 are arranged in a left-to-right top-to-bottom sequence. The unit numbers in a row are determined by the arrangement sequence of the layer. The configuration of the units below the top layer is determined by the number of units going up. The number on the 0th layer is the same as the number of rows and is defined as the number of output ports. The flat-latency control unit status is shown in Figures 18A, 18B, and 18C. There are two from 1 802 to 60 from the left. This paper size applies to China National Standard (CNS) A4 (210X297 mm) 527798. ^ i?. ^ * XJh.T eliminates the cooperation and private printing father A7 B7 V. Description of the invention () Inputs from the two, two inputs from the upper layer 1804, two outputs to the right 1806 and two down 1 A control unit 1 800 output from 808 is called a flat-latency control unit. Input lines from left 1802 are labeled lines W1 and W2, input lines from top 1 804 are labeled lines N1 and N2, and output lines to right 1 806 are labeled lines E1 and E2, and down 1 808. The output lines are labeled as lines S1 and S2. The control unit 1 800 also has two occupied signal output lines 1810 to the upper layer, such as the marked line BN in FIG. 18A; and receives two occupied signal output lines 1812 from the lower layer, such as the marked line BS in FIG. 18A. In the example of state 7 in Fig. 18A, only one occupied signal output line BS 1812 is displayed. Seven permitted connection states (numbered from 1 to 7) 1 830 are due to the operation of the flat-latency control unit 1 800. Input line W2 can be connected to downward output line S 1 1 820, downward output line S2 1822, or rightward output line E2 1 824 in the same column. Similarly, the input line W1 may be connected to the downward output line S 1 1 826, the downward output line S2 1 822, or the right output line E1 in the same column. The downward output line S 1 1 820 is connected to the upper group of the lower layer, and the output line S2 is connected to the following group of the lower layer. Input lines W1 and W2 connected to the same downward output line are not allowed 1 828. When the line W1 is not connected to the line E1, the input line N1 from the upper layer is connected to the output line E1 1 834 to the right. When line W2 is not connected to line E2, input line N2 is connected to output line E2 1 836. That is, the line W1 has priority over the use of the output line E1 over the input line N1, and similarly, the line W2 has priority over the use of the output line E2. It takes precedence over the input line N2. When the input line W1 is connected to the output line E1, an appropriate signal B18 is transmitted upward to the upper layer through a suitable connection line BN, and 61 paper standards are applicable to the Chinese National Standard (CNS) A4 specification (210X297 mm) (read first) (Notes on the back then fill out this page)

527798 A7 B7 V. Description of the invention () (Read the precautions on the back before filling this page) The same happens when the input line W2 is connected to the output line E2. When a downward output line is not connected to an input line from the left, such as line S1, it means that no message exists. ZERO transmits 1 832 downwards. Flat-latency control table Please refer to FIG. 18B and cooperate with FIG. 18A to display the status of the flat-latency control unit 1 800 1 830, which is derived from the status of the items shown in the first four blocks of control table 1 840 or 値. The header address of the message that enters the control unit 1 800 from line W1 1 842 determines that the message moves downwards, through line S1 to the upper layer group below, or through line S2 to the following group. The header address operates in the same way to bring the message into line W2 1 844. If the two messages point to the upper half or the lower half of the column, then the message on line W1 has priority over the message on line W2, and the latter is not allowed to move down but to the right. The direction of the message entering line W1 is determined by checking its header MSB 204, as indicated by the first block 1 842, and the second column is used for the message of line W2. When there is no message on line W1 or W2, it is marked with "none". The flat-latency i control unit 1 800 is always connected to the upper and lower groups. Please also refer to Figure 3, which can block the path to the lower layer 316, as indicated by the corresponding occupation signal 33 0. In Fig. 18A, the two paths to the lines S1 and S2 1 808 to the lower layer 316 are controlled by two occupancy signals on the line BS 1812. In Table 1 840, the states of the two occupied signals 1 8 1 2 are shown in the third column 1846 and the fourth column 1 848, respectively. The output line S1 of the group above the lower layer is "1" in the third column 1846 for occupation (blocking), or "0" for no occupation, and is also used for the line S2 in column 4 of 1848. Use "na" to indicate "not applicable" to indicate that a message does not point to a specific or --- 62_ This paper size applies to China National Standard (CNS) A4 specifications (210X297 mm) 527798 A7 B7 V. Description of invention () The following group . The first column of Table 1 840 describes the information on the lines wr and W2. It is preferred to move down to the above group 1 842, 1 844 and the path to the above column is not blocked, and is indicated by "0" in column 1 846. Online W1 The message has priority, so it is connected to the output line S1 to the above group, as shown in column 1 850. The message on line W2 points to the right via line E2, as shown in column 1 852. This connection status is shown in table 1 840 The fifth column and the state of Figure 18A are 5 1 830. The column below Table 1 840 describes the same situation as the first column, except that line S1 is blocked by the lower layer, so the two messages go to the right to each column, and this is the state 71830 means. When there is no message on the line W1 or W2, the individual input lines are connected to a known downward output line S1 or S2 to prevent the message from being transmitted downwards 1 832 and to prevent the individual input lines from being blocked by the upper layer 1 804 . Similarly, the down output is directly connected to the signal 値 ZERO 1 832. Table 1 842 shows the items in the four columns before Table 1 840. Determines the status of the flat-latency control unit 1 800. The control unit 1 800 State 1 830 determines which of the latches T1 and B1 is set, such as the sixth The seven columns are shown in 1854, and the settings set for determining the latches T1 and B2 are shown in columns 9 and 10 1 8 5 6. For a detailed description of the flat-latency logic, please refer to Figure 18C and cooperate with Figure 18B. An example of the logic of the flat-latency control unit is shown. Omitting the logic for setting the latches numbered in Table 1 840. Latches T1 and B 1 1 854 and latches T1 and B2 1856 control come from input port W 1, Send any message of W2, N 1 and N2. In addition, the output of the occupancy signal on the online BN 1 1 875 and BN2 1 877 ______ 63 This paper size applies the Chinese National Standard (CNS) A4 specification (210X297 mm) ( (阅读 Read the notes on the back before filling out this page)

1T 527798 A7 B7 V. Description of the invention () 値 Derived from the latch. When output line E1 is occupied by message transmission, the occupied signal on line BN1 1 8 75 is set to signal 讯 ONE, which means that column E1 is occupied, and it is also used for output and occupied signal BN2 1 877 of column E2. When the message 200 has entered the flat-latency control unit 1 800 so that the communication bit 202 is stored in the delay element D0, a latch setting signal (not shown) starts the procedure defined in Table 1 840 to achieve four latches. Lock setting. Executing the program in a clock cycle helps to send consecutive bits of message 200 down or to the right. As described in FIG. 13A, the most significant bit 208 of the header is removed from the message moving downward. The control unit A 1 800 is connected to the upper unit B 1 800, so that the line BN1 and the line N1 of the unit A are respectively connected to the line BS1 and the line S1 of the unit B, and the lines BN2 and N2 of the unit A are respectively connected to the other upper layer. Line BS2 and line S2 of a unit C (not shown). In another example, as in the cell D in the Q layer, the four connection lines BN1, N1, BN2, and N2 of the cell D are connected to the lines BS1, SI, BS2, and S2 to the cell F in the upper layer, respectively. Cell A is always connected to a single cell G such that the lines E1 and E2 of cell A are connected to the right and lines W1 and W2 of cell G, respectively. See Figures 18B and 18D for flat latency control unit symbols. Messages on line W1 take precedence over messages on line W2, that is, if these two messages point to the same unblocked column below line S1 or S2 Group target, then the message on line W1 has priority and is sent down to the output of line S1 or S2, and the message on line W2 is sent to line E2. In an alternative version of the control unit 1 800, the message on line W2 takes precedence over the message on line W1. Instead, the ___64 ^^ scale applies to China's national standard ((: Can) 8 4 specifications (210/297 mm j (please read the precautions on the back before writing this page))

527798 A7 _B7__ 5. Description of the invention () (Please read the notes on the back before writing this page) The logic of the switching control unit is defined by the exchange lines W1 and W2 and exchange lines E1 and E2 in Table 1 When the line W1 has priority over the line W2, the figure 18D shows that the symbol of the flat latency control unit 1800 represents 1 880, and the solid black 18 82 represents the priority. In the replacement version, the line W2 takes precedence over the line W1, and the bottom square is solid black. In any type of symbol 1 880, for the sake of clarity, the occupation signals connected to the upper layer and from the lower layer are omitted. This concise symbol is used to simplify the description of the entire layout of the flat latency switch, as illustrated in Figure 19. In an alternative priority method, which is not illustrated, W1 has the priority of connecting upwards and W2 has the priority of connecting downwards in the even rows, and the opposite is the priority in the odd rows. 16 by 4 flat latency switch

Please refer to Figure 19 in conjunction with Figures 1, 3, 6A, 6C, 18A, 18C, and 18D, which depict flat-latency switches 1900 for four rows and four layers. Each floor contains 16 columns of 1 902, numbered from 0 to 15. The flat-latency control unit 1800 connects two columns and two pairs of vertical connecting lines, as shown in Figs. 18A and 18C. A method of controlling the layout unit 1 800 in the array 120 will now be described, and other elements of the switch 100 are omitted in this description and illustration. The number of input ports 104 of the switch 1900 is the number of columns (16) times the number of rows (4) or 64. The number of output ports 154 is the same as the number of input ports. See Figures M8A and 18C. The flat-latency control unit 1800 has two outputs to the lower layers of the online S1 18 70 and S2 18 72. Because of the "dual output" characteristic of unit 1 800, the control unit of layer 0 is not used for the operation of the flat-latency switch. The flat-latency control unit 1 800 of ___________65 is arranged in the switch array 120. This paper size is applicable to the Chinese National Standard (CNS) A4 specification (210X297 mm) 527798 A7 B7 V. Description of the invention () (Read the words on the back first Note before filling out this page) The method involves first configuring the hive with the same configuration at the lowest level (the first level of all lines). Therefore, the control unit is arranged along a diagonal line extending from the lower left of the switch array 120 to the upper right. Each layer 1902 gives 16 columns and each cell 1800 gives 2 columns, so a switch array uses 16/2 or 8 cells. The control unit 1 880 having the priority 1 882 at the top of the pair is arranged along the diagonal of the control array 120 of the 0th row 1910. In the next row (line 1), the control units with priority in the bottom column are used to fill the control array. The method of changing the priority from one row to the next is used for the rest of the switch 1900 layout. The other control array for the 0th row of all layers above the 1st layer contains the same layout as the 1st layer, that is, the equivalent configuration of the top priority unit 1882. This completes the leftmost row and the bottommost layer of the switch 1 900 Layout. Starting from the second layer, the remaining switch arrays are arranged in each layer in a left-to-right sequence, and move up one layer at a time until the top layer is completed. The number in the box area 1916 indicates the lowest number of output ports connected to the control unit 1 800 to one of the lower pairs of port 154. The display unit 1910 is connected to port 0, and is also connected to port 1. The number "1" is omitted in Figure 19 because space is limited and no number is needed during layout. The number 1916 in the box area is used to help configure the upper control unit. Please also refer to Figure 9, on the second layer, the information moving to the right along column 0 follows the connection specified by the sequence (0,2,1,3,0, ...). The first unit 1924 is connected to columns 0 and 2 below. Units below 1 926 on the right are connected to columns 1 and 3. A vertical interconnection pattern between layers 1 and 2. Pattern 1922 forms a connection in accordance with sequence 910. Units 1924 are connected to the lower layer to the 0th and 2nd columns, respectively. In the next line (2_66 this paper is in accordance with Chinese National Standards (CNS) A4 specifications (210X29-7 mm) 527798 A7 B7 V. Description of the invention () layer), unit 1 926 is connected to the lower layer to the first column and Cell in column 3. The number of the vertical box area 1 928 between the switch arrays indicates the configuration sequence 1920 (for the sake of clarity, only the first number of the pair is shown). Checking the 0th column of the 2nd level shows that the control unit is continuously above the unit with 0, 1, 0 and 1 digits to the lower level. The sequence (0, 1, 0, 1) appears as the lowest Arabic numeral in the continuous box-shaped area 1 928 of the control unit on the second floor, and establishes the bottom row position on the second floor. On the second level, the column below the unit is arranged along the second and third columns. The cells in columns 2 and 3 of row 0 are connected to other connection pairs 1 and 3. The lowest number of columns to the lower level is 0, but to avoid ambiguity in the layout process, the horizontal box area 1916 (between the first and second layers) does not repeat 0. Instead, use 値 1. That is, each frame in the box-shaped region 1916 indicates the lowest number of rows of the pair of cells connected to the lower layer. Because two cells use four column numbers, the lowest column is used unless it is already used in a sequence. In the latter example, the next lowest number is used. So the sequence 0,1,4,5,8,9,13,14 is used on layer 1 (instead of 0,0,4,4,8,8,13,3) to help the upper layer Of the unit configuration. The box-shaped area 1 9 1 6 above the second layer is filled using the described rules, and the illustrated ones are used to lay out the units of the third layer. A configuration sequence (〇, 4,2,6,1,5,3,7,0, ...) 614 is used for the third layer to configure the control unit in a layout. The vertical interconnect pattern 1932 between layers 2 and 3 matches the connections required for sequence 6 1 4. In Figure 19A, the first Arabic numerals of each pair in 6 1 4 are shown in bold type, because only the first Arabic numerals of this pair are used for configuration. Unit 1930 is connected to columns 0 and 67 of the lower paper size. Applicable to China National Standard (CNS) A4 size (210X297 mm).

8 79 7 2 5 Λ A7 B7 " 一-...--Description of the invention () 4 歹 [J. In the 0th row, the next unit in the diagonal line connects the 1st and 5th columns: the next unit connects the 2nd and 6th columns, and the fourth unit in the diagonal line connects the 3 and 7 columns. That is, the first Arab numeral of four pairs forms the sequences M, 2 and 3. From the sequence (0,4,2,6,1,5,3,7,0, ...) 6 14 instead of the Arabi number generation sequence (0,2,1,3,0, ... ) For the layout of the columns. Along the 0th and 1st columns, the unit 18 00 is arranged at the connections 0, 1, 2 and 3 to the lower layer. This sequence is shown in Arabic numerals under 1 928 in a series of vertical box sections on the third floor. Along the second and third columns, the cells are arranged above the connections 1, 3, 0 and 2. The control unit on the 3rd floor is arranged from the right to the 0th line to the intersection of similar numbers in the vertical box-shaped area 1928 to the box-shaped area 1916 between the left and the lower layers. The inter-layer box area 1 928 above the third layer is filled using the rules described in the second layer. The configuration sequence (〇, 8,4,12,1,9,5,13,2,10,6,14,3,1 1,7,15, ...) 658 is used to lay out layer 4 1950. Unit 1 940 is connected to columns 0 and 8 below, continuing the diagonal, ¥ units are connected to columns 1 and 9, and then the next unit is connected to columns 2 and 10, And so on. The interconnection pattern 1942 meets this connection requirement. The rest of the fourth layer uses the sequence of the first Arab numerals from each pair of 65 8 which is 0,4,1,5,2,6,3,7,0, ~, first Full vertical box area to layout. This sequence is used to fill the vertical box area 1944 on the fourth floor. The control unit is located at the intersection of similar numbers from the box area to the left and below each switch array. FIG. 19A illustrates the application of the rules described herein for the control unit 1 800 for laying out the flat latency switch 1 900. (掮 Please read the notes on the back before filling this page)

68

527798 A7 B7 i. Description of the invention () The private seal of the Central Standard Offensive Bureau of the Ministry of Economic Affairs, the second cooperation of the private seal, if the message entered by line W2 into unit 1910 is not blocked by another message on line W1 with priority and has priority Move to the same row at level 0, and if the target row is not blocked by the lower level, the message at row 0 is immediately sent down to the message target. Therefore, the unblocked message on line W2 or line W2 always moves downward. During the implementation and use of the flat latency switch 1 900, it is very unlikely that the information entering the control unit 1 800 will be blocked. Therefore, each time the message enters the control unit from the left, it generally moves downward. Please also refer to Figure 17, the latency of switch 1700 is 50% chance of the message moving to the next line before the message moves down. Therefore, half of the time that a falling message arrives is usually in the "wrong" column group. In contrast, for the switch 1900, the falling message is always good for connecting to the upper and lower groups. Under the given similar load conditions, the average latency of switch 1 700 is more than 50% higher than switch 1 900. In addition, the circulation time allows the difference in latency between a single message to pass through the switch 1 900 from 100% to 200%, so the latency of a single message through the switch 1 900 is almost constant for all messages. , And the same as the minimum latency of the single path switch 1 700. Please refer to Figure 8B for the input port. In the lower layer, one message b 840 can block the other message A 802 in the upper layer 842. As a result, message a is blocked. The other messages C 844 and D 846 are the same. Message a is blocked. Assuming that message A is blocked in the first case, messages c and D will not be blocked either. As the number of messages in the switch increases, the likelihood of individual messages being blocked increases. Please also refer to Figure 4, allowing the message 200 to enter 69 pages. This paper size is based on the Chinese national standard ((, NS) Λ4 specification (210X 297 mm) (read the precautions on the back before filling this page) 527798 A7 B7 V. Description of the invention () After the Ministry of Zhang ’s final bid, the Beibei-T Consumer Cooperative Co., Ltd. printed 100, no matter when the line ready signal 404 reached a high state and the output port was not blocked 4 0. Switch 1 0 0 of Statistical analysis is not apparent during any of the embodiments that pass through the switch. Decreasing the rate at which messages are input to the switch can significantly reduce the likelihood of messages being blocked. The maximum rate (100%) input to the switch is defined when all ports 104 A situation where a message is received at an unblocked time 406. If the size and special embodiment of the switch 1000 are reduced depending on the size of the switch, the blocking and negative effects of the message dispersed during the latency period can be reduced. Greatly reduced, even insignificant. One of the methods of low input rate is to specify the port 104 meter or other external device to reduce the frequency of the injected signal. Unfortunately, this technology assumes the external equipment of the switch. Responsibility for reducing the rate. Another alternative method is to reduce the transmission rate of the line preparation signal. Unfortunately, the external device must wait a long time to inject the signal. No matter which way to reduce the rate, the effect is to increase the effective latency. And reduce the total output of the switch 1000. Please refer to FIGS. 17 and 20A, which show that the top layer 1702 of the eight by four switch 1700 has 32 input ports 104. In another embodiment of the switch 1700, The same top layer 2010 has less than half of the input lines. The control unit 300 on the top layer can be connected to an input port or not connected to 2112. The first two lines of Figure 20A show that the rate can be reduced without the unexpected effect of increasing latency. To 50% method. The specific input unit 2114 to output 104 may not be connected to further reduce and adjust the input rate. In one embodiment of the switch 1700, the mode corresponding to the omitted input port (not shown) is also omitted. The output is connected to 1 54. Therefore, the switches have the same number of inputs (the first read the precautions on the back before filling this page) --------- 70 — this paper size House standard rate ((, NS) Λ4 specification (21 × X 297 mm) 527798 A7 B7 V. Description of the invention () Ministry of Economic Affairs and the Ministry of Economic Affairs decided the standard bureau Jr. Consumer Reports Agency printed port and output card. In another embodiment, 32 input ports can be operated. Therefore, another embodiment of the switch 1 700 can have 32 input ports and 32 output ports, or 16 input ports and 16 input ports, or 16 Input ports and 32 output ports. In other embodiments, other connection numbers can be selected, depending on load factor and performance considerations. The number and arrangement of the input 104 and the total possible number determine the maximum message flow density in the switch. Message flow density is defined as the actual number of messages in the switch, not the maximum possible number. Refer to Figures 18D, 19, and 20B to reduce the input rate of the flat latency switch to 50% in the same manner as described in the previous two rows of Figure 20A. That is, there is no input connection 2024 in unit 1 880 in another row. In FIG. 20C, another method includes connecting only one of the two upward input lines 1874 and 1 876 of the unit 1880 to the input port 104. Input 104 is preferably connected to the columns without priority 2072 and 2074, because in the same column, the cell to the left gives priority to the column, so the column is less likely to contain messages that block input 04. To further reduce and fine-tune the switching input rate, use the method combination shown in Figures 20B and 20C. In particular, some rows have only one input per cell 2072, and other rows have no 2024, similar to the output connections in Figure 20A. The number of input (and output) ports implemented by the silicon integrated circuit chip of one embodiment of the switch 100 is limited by the pins. That is, the number of input and output connections available in the chip determines the size of the switch. This situation arises from the relatively small number of logic gates used to implement the control unit. Given this set of technical decisions and the use of a unique number of gates, use more logic capacity than pin capacity to reduce latency and message flow density. One way to use logical capacity is to read the notes on the back and then fill out this page. ^ The paper size is described in Chinese national standard f ((, NS) Λ4 specification (210X297 mm) 79 27 5 Central Bureau of Standards, Ministry of Economic Affairs A7 printed by the employee's cooperative. ___ ^ V. Description of the invention () The more complicated flat latency unit 1 800 costs extra logic available. Another method is to reduce the input and output port connections 2112 and combine more rows to form Difference. The two methods can be combined, as shown in Figures 20B and 20C. Actually, the available I / O connections or pins determine the capacity of the switch. The implementation of this description uses a power of 2 to 4 or more The minimum required number of lines. For example, using the input connection method of Figure 20C or the combination of Figures 20B and 20C, the 64-port switch 1 900 has 8 to 12 internal rows (compared to the four rows of Figure 19). Compare) to right. The right to left connection is shown in Figures 21A, 21B, and 21C, which illustrates the implementation of different east to west (or left to right) connections. Please refer to Figure 21A and cooperate with Figures 1 and 3, rightmost row Message 164 passes through the selected FIFO buffer 114 and reaches a list Point 172. The exit point 172 is the rightmost position of the message moving from left to right along a row of 360. The message at point 172 cannot be successfully moved down to the lower layer or output port. In some embodiments of the switch 1000 In the path 2104, the message is transmitted left to the exit point 174 in the same column and connected to the control unit 12 of the switch array 1 20 in the 0th row. The message in the 0th row immediately has the opportunity to move down and Continue towards the message target row. Refer to Figures 7, 20A and 21B. Another embodiment of the switch has a message reaches the row exit point 1 72, which forwards 2 1 06 to an input port 104 that is not externally connected. FIFO 2108 adjustment The timing of this message is in line with the timing requirements of the row. The unused entry point 2120 can be connected to the outside and used as an input port 104, but the message entering the switch from point 1 74 below the top layer does not have to reach all the possibilities of the bottom layer. For example, from the 2nd (please read the notes on the back before filling out this page) 72 This paper size applies the Chinese National Standard (CNS) Λ4 Regulations (210X 297 public power) 527798 A7 B7 Central Standard of the Ministry of Economic Affairs Printed by the Consumers ’Cooperative Cooperative V. Description of the Invention () The messages entering the switches in the upper group of the upper layer cannot reach any of the columns 7 1 6 in the lower group of the first layer. Information entering the top layer is more conducive to obtaining a lower latency, but is limited to the range of possible targets that the message can reach. In yet another embodiment (not shown), it is shown in Figures 21A and 21B. For a combination of these connections, some exit points 172 connect 2104 to entry point 174, while other exit points connect 2106 to unused input port 104. Please refer to FIG. 21C. Another embodiment of the switch 100 includes an exit point 172, which is connected to the entry point 174 of a different column 2110, which is conducive to the messages that are continuously blocked in one column. Column. Referring to Figures 2A, 2B, and 2C, message 200 generally includes a header portion and a payload 206 with a total length 214. The length of the individual messages entering any of the embodiments of the switch 100 is different. The switch can accept any message length up to a pre-specified maximum size. For a given embodiment of the switch 100, the format and size of the header are fixed according to the implementation of the switch, but the length of the payload can be different, thus causing the total message length 214 to be different. According to the discussion in Figures 8B and 21A, the information entering the control unit from the upper layer of any row can be repeatedly blocked, so that the message loops back to the entry point 174 in the same column 2104. When the message is continuously blocked, the message reaches the control unit of the row, where the message enters the column first from the upper layer. That is, the message is in the case where the "header" or the communication bit 202 catches up with the "tail" or the last bit of the payload 206. Therefore, the storage capacity of a row is enough to accommodate all the bits 2 1 4 of the message. Please refer to the drawings of 11A, 13A, 15A, 16B, 17 and 18C and check 73. This paper size is applicable to Chinese national standard (€?) / \ 4 坭 台 (210 乂 297 乂) Please read the precautions on the back before (Fill in this page), 口 口 527798 Printed by the Central Standards Bureau of the Ministry of Economic Affairs, Tung Kee Consumer Cooperative, A7 ____ B7 V. Description of the invention () Check the control units 1300, 1500, 1620, and 1800, from left to right of the passing unit In the path, a control unit includes one or more delay elements 1102. These delay elements participate in the address decoding and message transmission of the unit. All the delay elements 1 1 02 are gathered in all the control units along a column from the first row to the last row. The aggregation of the delay elements can also be used as a FIFO storage device. For example, the control unit 1 300 includes two delay elements. The switch 1700 has four rows, so the storage capacity of four control units in one column is 2 by 4, or 8 bits. In fact, the message length 214 is much larger than 8, so FIF01 14 can be used to expand the storage capacity of the row to the message size 2 1 4. Take the message length of 32 bits as an example, and the length of each FIFO 114 is (32-8) or 24 bits. Please refer to Figures 20A, 20B, and 20C. Compared to the total number of inputs 104, increasing the number of lines helps to reduce the coarse block of messages in the switch and improve the latency. Another benefit of increasing the number of rows is that the storage capacity of a column can be relatively increased. For example, in another example with 16 rows of switches, 32-bit messages do not use FIFO 114 at all. 16 rows can generate a 32-bit delayed aggregation, which means that a 32-bit message can be cycled in a column, with the header and The tails do not collide. Compared to I / O connections, the use of too many logic gates in technology, in addition to helping reduce the data flow density as discussed earlier, logic gates can be used in many control units because of the increased message storage capacity per row. In the illustrative embodiment of the switch 100, the logic gate can be used to generate as many paths as possible, i.e., to generate additional rows not connected to the input 104. In one embodiment where the message length 214 associated with the available gates is large, FIFO 1 1 4 is used in each column. 74 This paper size applies Chinese National Standard (CNS) Λ4 gauge (210X 297 public power) (Please read the notes on the back before filling this page),-0 527798 A7 B7 Printed by the Central Standards Bureau of the Ministry of Economic Affairs and Consumer Cooperatives V. Description of the invention () Low-latency output Figure 2 A shows a low-latency output structure, which can reduce the barrier of the bottom layer. Referring to FIG. 2A, a message 200 includes a header address 204 'which specifies a target column at the bottom of the switch. The switch 100 embodiment having the output structure of Fig. 22A does use the row header 212. The target specified by the header 204 is listed as the final destination of the message, and when the message reaches the bottom layer, the physical behavior of the message is invisible. Messages that reach any of the bottom columns are collected in parallel from all rows and supplied to the final output device 176. In fact, multiple rows are used to increase bandwidth and reduce latency to target 2206, as well as reduce barriers to higher levels. Because the message that reaches the bottom moves immediately down, the message never moves to the right at level 0 in an attempt to block the message at the upper level. The described output method helps to obtain the information of the switch 1000 at the fastest possible rate, thus reducing the latency and congestion in the upper layers. Referring to FIGS. 1 and 2A, in the embodiment of the switch 100, the output structure 180 includes a plurality of external devices or message targets 2206. The number of these devices is the same as that of the bottom row. One of the buffers 2210 in the buffer array 152-serially receives the message 200 from the control unit 2202 of the bottom layer of the switch. This embodiment can be used for low-latency applications, because the buffer 2210 is always ready to receive data, so that the unit 2202 does not have an occupied signal output. The unit 2202 always sends the message immediately downwards. Referring to Figures 4, 12B and 22B, the communication bit 202 of the message reaches the buffer 22 1 0 at the time indicated by the line preparation signal 422. The minimum amount of time between messages is the time between messages tm1242. Buffer 2210-Receives serial communication bits 202 and payload 206 in series. As shown in Figure 10. Figure 75 of this paper is applicable to Chinese National Standards (CNS) Λ4 Regulations (210X 297 public §) (Please read the precautions on the back before filling this page) 527798 A7 ____ B7 V. Description of the invention () The Central Bureau of Standards of the Ministry of Industry, Hegong Cooperative Co., Ltd. printed the discussion, and the header 204 was removed from the message. The contents of the buffer 2210 are removed by a parallel bus 178 and delivered to a target 176, such as a processor or control unit of a supercomputer. The buffer 2210 is then reset to zero to indicate that no message exists. The presence of a message in the buffer 2210 is indicated by the communication bit 202 in the buffer. This communication bit indicates that the payload is in the buffer and will be removed before the next cycle 422. Referring to Figures 1, 12B, 22A, and 22B, the output timing of the buffer 2210 in the structure 2206 is different for each FIFO 1102 because these buffers are connected to the control units 2202 in different rows. The time difference is derived from the delay element in the control unit and is equal to time t. 1240. The timing signal of this line is available externally from timing port 1 68. Column and Row Addresses Refer to Figures 1, 2B, and 15B. Messages with a row address header 200 are directed to output ports in specific rows and rows. In the embodiment of the switch 100, if the address matches the row position of the control unit, the control unit 1550 of the 0th layer reads the row address 2 1 2 and transmits the message downward. In an interconnected structure with many rows, the message has the opportunity to move through a number of cells 1 550 before reaching the destination row, and to avoid doing so by layer 1 messages that fall preferentially to layer 0. Therefore, the embodiment of the switch 100 using the 0th-level control unit 1 550 cannot always effectively extract the message from the switch ', thereby increasing the possibility that the message is blocked by the upper layer. < Please refer to Figures 1, 23A, 23B, and 23C. The output structure 180 at layer 0 immediately forwards the unblocked and column and row addresses 2308 (please read the precautions on the back before filling this page) _____76 > The paper size is suitable ifl Chinese National Standard (, NS) Λ4 specification (210X297 mm) 527798 A7 B7 V. Description of the invention () Printed from 200 to output port 176 by the Consumers Cooperative of the Central Bureau of Standards of the Ministry of Yi. Message A at level 0 is located at column 0 and line 2. Message A enters read 23 14 line address 212 and sends the message down on path 2312 to the control unit 2310 of output control 23 22, where the message moves to the right on path 2326 to the FIFO buffer 1112 connected to the target output port 176 . The other message 200 of the layer 1 unit above the unit 2316 and which fell first to the unit 23 16 of the next row is not blocked by the message transmitted to the right from the unit 23 10 of the layer 0 as expected. The message that the unit 23 16 moves to the right in the path 23 30 transmits the occupation signal 2316 to the control unit 23 10 of the 0th layer upward to block the unit 2316 from transmitting the message downward to the same address 23 08. Another message addressed in the same row and in a different row in cell 23 16 will not be blocked by the cell on path 23 30. Therefore, in the embodiment of the switch 100 using the units 23 10 and 23 22, simultaneous occurrence of messages directed to the same column but different rows does not cause blocking, which occurs in the embodiment using the control unit 1 550 of the 0th layer. Dongyuan Broadcasting Control The desired feature of the large switch is the multi-casting transmission capability, that is, sending a single message to many or all output ports. In another embodiment, the single switch 100 supports one-to-all message sending and one-to-one message sending simultaneously. The method of this embodiment is to copy a multiplex broadcast message whenever the message falls to the bottom layer. The expected result is to produce a copy for each column of the switch when the message finally reaches layer 0. The multi-cast message then moves to the right along each column of the 0th level, and a copy is received down to all output ports 1 54 of each row 'to receive a copy of the message. Figure 24A shows the control unit for multicast message 230 (Please read the precautions on the back before filling this page)

、 1T This paper is suitable in size / fl China National Standard Net ((, NS) Λ4 specification (210X 297 Gongchu) 527798 Ministry of Economic Affairs, China Standards Bureau, A7 B7 printed by Consumer Cooperatives V. Description of invention () 2400, And Figures 24B, 24C, and 24D show different states of the multiplex control unit 2400. The multiplex broadcasting capabilities described here and shown in Figures 24A, 24B, 24C, and 24D are consistent with all other embodiments, allowing additional control units to be used The cost of logic can optionally be multiplexed in any embodiment. See Figure 24A and in conjunction with Figures 2, 10, 12A, 12B, 13A and 13B, the multiplexed message 230 includes a second bit in the header, It is called the multiplex broadcast bit 220 of the continuation communication bit 202. When the multiplex broadcast bit is set to ZERO, the message is transmitted to a single frame determined by the column header 204 and the row header 2 12. It is used for The technology for controlling the peer-to-peer transmission is the same as that described in Figures 12, 13, 14 and 15. Another delay element is included in the control unit 2400 to maintain the multicast bit 220. When the communication bit 202 is ONE and the The multiplex broadcast bit is ZERO. For point-to-point transmission, the control unit 2400 checks the most significant bit 208 and the occupation signal BS 2406 to determine whether the message is sent down or to the right. When the message 230 is sent down, the communication bit (ONE) and the multicast bit ( ZERO) is continuously transmitted down to line S 2412. After completing two cycles, connecting the delay element D1 and line S, it is beneficial to obtain the result that the bit 1004 that continues the most significant bit 20 8 becomes the most significant bit of the next layer The message is advanced 2 bits in advance to maintain the inter-layer timing requirements, as shown in Figures 12A and 12B. When the multiplex broadcast bit 220 is ONE, the message 230 is sent to the right until the upper layer of the lower layer and the following have received the message. A copy of the message. When the message 230 moves to the right, the message will fall to the top and bottom ranks 10 15 and 10 106 below. Refer to Figure 24B, "up" bit 224 and "down" bit 226 The starting point is to set 78 paper sizes to the Chinese national standard ((, NS) Λ4 specifications (210X297 mm) (Please read the precautions on the back before filling this page)

527798 Seal of the Consumers' Cooperative of the Central Standards Bureau of the Ministry of Economic Affairs A7 B7 5. Description of the invention () is set to ONE, which means that the message has not been transmitted to any of the columns below. In Fig. 24B, the message F enters the control unit without being blocked, so that the blocking signal on the line BS is ZERO. A copy of message F is sent 2432 down and right. The control unit is located below, so the "down" bit 226 of the copy to the right is set to ZERO to record that the branch has met 2434. When the copy of the multiplex broadcast message is transmitted down to 2412, the "up" bit 224 and "down" bit 226 of the down copy are reset to ONE, so that the message is copied again in the lower layer. Referring to Figures 24C and 24D, message F moves right to one of the units connected to the unit above. This unit is blocked below 2436 and the message continues to the right. The copy of message F finally reaches the unblocked control unit connected to the above unit. In this unit, the message F is finally sent 243 8 downwards and the "up" bit 224 of the header to the right is set to ZERO 2440. The up and down flag bits are now set to ZERO to indicate that the message has been copied in the lower layer, so the message is no longer transmitted to the right. Figures 24B, 24C and 24D describe a message with a multiplexed broadcast bit set to ZERO. The message moves to the right until the message falls twice to the appropriate column in the lower level. When the message drops, the flag bits 224 and 226 are set to ONE. This copy is continued in this switch until reaching level 0. Because the interconnect structure includes L layers, replicating L, which results in 2L columns containing a copy of the message. Whenever the message falls, one of the two columns in the lower layer is in the upper half and the other is in the lower half <. This method ensures that all branches of the quadratic tree described in Figure 7 can be used. The end result is that all columns of layer 0 receive a copy of the message. The size of this paper is suitable for the national standard of Sichuan ((, NS) Λ4 specification (210X297 mm) (read the precautions on the back before filling in this page)

527798 A7 B7 Printed by the Central Bureau of Standards, Shellfish Consumer Cooperative, i. Description of the invention () When the message originates from outside the switch, a selectable bit mask 228 is generated. The bit mask is a series of k-bits, each representing a row in the switch. When one bit of the bit mask is set to ONE, the message is directed to all columns of the corresponding row. In order to complete a pair of all-multicast, all the bits of the bit mask of the row are initially set to ZERO. As a result, all the rows and columns receive the message. Alternatively, select only a subset of the bit mask components as ONE to select a subset of rows. This omitted line is set to ZERO. This method provides one-to-many multicast capabilities, where all columns and only selected rows receive the message. Alternatively, if only one of the upper 224 and lower 226 flag bits is initially set to ONE and the other is set to ZERO, then only the message above or below the layer 0 is received. Therefore, individually setting the upper 224 and lower 226 flag bits and the row bit mask 228 to ZERO or ONE will be beneficial to directing the multi-cast message to a subset of the target. At layer 0, the multicast message moves right in each column, loops left, and finally traverses all rows. For a given column of p, each bit of the bit mask is used to mark whether the message has been transmitted downward in an individual row. If the message is not blocked below and the representative bit is 1, then a copy of the message (preferably without a bit mask) is transmitted down. As shown in Figure 15B, only the communication bit 202 and the payload 206 leave the switch. At the same time, a copy of the message is also transmitted to the right and the position of the in-place mask is set to ZERO, which indicates that the line goal has been met. If the message is blocked from falling, the message moves to the right and the mask is not changed. A blocked message cycles and finally passes through the blocked unit again. When all the bits of the bit mask are ZERO to indicate that all target rows have received the message, the > paper size is suitable for the China National Standard ((, NS) Λ4 specification (210 > < 297 mm) ) (Please read the notes on the back before filling this page), 11 527798 A7 ___B7 V. Description of Invention () The messages printed by the Central Bureau of Standards of the Ministry of Economic Affairs-Industrial and Consumer Cooperatives will not be transmitted to the right in the 0th layer. The structure and technology of multiplexing a message from an input port to all columns of layer 0 and from each column of layer 0 to all rows, thus satisfying the desired requirements of a pair of all transmissions. Also describes a pair of many transmissions to Select all the rows of the row. Furthermore, multicast and non-multicast messages can be sent in the same switch at the same time. The topology and methods of 2D, 3D, and 4D system message flow control are controlled in an unlimited way, so that The usable output and efficiency of the switch 100 embodiment are not determined by the upper limit of the switch size. When the switch size reaches infinite, the input port is for all possible inputs (as shown in Figures 20A, 20B and 20C). The preferred ratio may be in the range of 1: 3 to 1: 6. In fact, the limit on the maximum size of any embodiment of the switch 1000 is the number of pins of the device. Therefore, a single integrated circuit chip is implemented The maximum size is limited by the pins. It is expected that the manufactured switch will have much more I / O than the technical limit. The multi-chip implementation accepts the structure and technology of increasing the number of ports without implementing restrictions. Below Three methods are provided, called 2D, 3D, and 4D interconnection methods. See Figures 25A, 25B, and 25C for a message layout for "nD" multichip switches . Message for 2D switch 25 02 has two headers 208 and 2508. Message for 3D switch 2504 has three headers 208, 2508 and 25 10. Message for 4D switch lacks 25 06 with four headers 208, 2508, 2510 and 2512. Please refer to Figure 26A in conjunction with Figures 1, 3 and 25A, 2D switch 2600 (Please read the precautions on the back before filling this page)

This paper is suitable for China's national standard rate ((, NS) Λ4 specification (210X 297 Gongchu) 527798 A7 ---- --- B7 V. Description of the invention () (Read the precautions on the back before filling this page ) It is formed by connecting two stacked storages 2610 and 2612, each stacked storage contains a plurality of C switches 100 single chip implementation 2602. One of the preferred embodiments of the 2D switch 2600, C is the 0th level column The two stacked storages are connected in a special arrangement of bus connection 2604. Each output 2604 of the wafer 2620 in the first stacked storage 2610 is connected to each of the chips 2632 in the second stacked storage, Input one of 2634, 2636 and 2638. The header 208 of message 25 06 determines where to output the message 2604. The message entering any input port 2622 is transmitted to the input port of any chip in the second stack storage 2612. As discussed in FIG. 10, when the message 2502 passes through the chip 2620 of the first stacker 2610, the header 208 will be removed 208. The stamp is printed by the staff consumer cooperative of the Bureau of Standards and Standards of the Ministry of Economic Affairs. The body circuit chip 2630 message 25 02 ends with the header 208 The header 2508 is processed in exactly the same way. Therefore, the header 2508 is the same as the header 208 discussed previously for the message entering the second stacker 2612. Any input message entering the connection bus 2604 is expected to be Teleport to target output 2640. See also Figure 26B. The resulting structure of the two stacked storages 2610 and 2612 (interconnected as described above) here means a "twisted cube", which means a stacked The memory is twisted 90 degrees relative to the other. In a suitable 2D embodiment of the switch 100, the connection bus 2604 includes all 154 sets of output ports and the individually occupied signal port 376 at the same column address 2206, and the FIFO buffer 152 is omitted To simplify timing considerations, the output port 154 of the flash memory 2610 is connected to the input port 104 of the same row of the second stack memory 2612, and is also used to connect the occupation signal 376 to the same port-- ----- Ώ,-This paper size is suitable for Chinese storehouses in Shizhou ((, NS) Λ4 size (210X 297mm) 527798 Once the Ministry of Standards and Construction Co-operative Consumer Cooperatives printed A7 B7 invention description () Occupy signal 30 4. Given two stacked memories containing multiple C integrated circuit chips, the total number of output addresses 2620 is C2. Please refer to Figure 27 and cooperate with Figure 25B, which shows the 3D interconnect switch. Application 27 The figure illustrates the same interconnection method used to connect the bus 2604 described in this layout. Those skilled in the art can assemble higher-dimensional switches. The 3D switch includes three layers of 2710, 2720, and 2730, and each layer includes C products. C stacks of bulk circuit wafers. In the preferred embodiment of the 3D switch 27 00, C is the number of columns of the 0th layer of the wafer. The three column headers 208, 250 8 and 25 10 of the message 25 04 determine the output address 2720 of the message. The total number of output addresses is C3. Refer to Figure 28 and Figure 25C, which shows the 4D interconnect switch. Using the same interconnection method described in Figure 28 for connecting the bus 2604 in the layout, those skilled in the art can assemble higher-dimensional switches. The 4D switch includes two square matrices 2810 and 2820, each matrix including C2 twisted cubes 2600. In one embodiment of the 4D switch 2800, C is the number of columns of the 0th layer of the wafer. The 4 column headers 208, 25 08, 2510, and 25 12 of the message 25 06 determine the output address 2220 of the message. The total number of output addresses is C4. Split header switch The main design purpose of switches for high-speed systems such as supercomputer networks is low latency. 18A, 18B, 18C, and 19 The flat latency system of the control and topology discussed in FIGS. 18A and 16'B, and the high-speed timing control discussed in FIGS. 16A and 16'B, and an embodiment combining the two for reducing message passing through the switch 100 Latency or transit time. In the examples currently discussed, the paper size of this message is suitable for the Chinese National Standards (CNS) Λ4 specification (2 丨 0X297 mm) (Please read the precautions on the back before filling this page) 527798 A7 B7 V. Description of the invention (The embodiment where all header bits printed by J-Consumer Cooperative Co., Ltd. of the Central Bureau of Didi enter the switch 100 before the first payload bit enters, which indicates the length of the header (for a given I / O speed) determines the absolute minimum latency. Figures 29A and 29B describe an example of a split header that reduces the time by two times and the time it takes the payload to pass through the switch by twice. See Figure 29A, Message 200 is "separated" externally into two messages 2902 and 2904, each message having half its original length. In addition, the header bits 204 are formed as individual headers of the split message. The header bits at the even position 2910 Becomes the header of message A 2902, and likewise the odd bit 2912 becomes the header of message B 2902. The payload 204 is divided into two halves, which respectively form the payloads 2914 and 2916 of the two messages. See FIG. 29B In conjunction with Figures 1 and 20A, it shows a split header switch. The switch includes two sections T 2924 and U 2926. Each section is formed in alternating layers of the main 29 30 and the 2032 control array. Except for the control unit Except for the internal detailed description, a part is equal to the switch 100 shown in the first figure. The main control array layer 2930 includes the control array 120 described above, which is added to control the circulation bus 2922. The control bus 2922 contains R paths, where R It is the number of the layer. The input line of each control path is connected to the layout output of each master control unit and the latch of the slave control unit that is set or transmitted in the same situation on the same layer. The control circulation bus 2922 is transmitted on one layer All latch settings of all master control units in the system. An output line of a control path is connected to the latch of the slave control unit. The logic gates in the master control unit handle and set the latches in the unit. The slave control unit is Omit the logic gate of this header and remove the first header bit (please read the precautions on the back before filling this page) This paper size applies to Chinese national standard (CNS) A4 ^ (210X29 ^ t) 527798 A7 _____B7 V. Description of the invention () Logic element printed by the Cargo Workers and Consumers Cooperatives of the Central Standards Bureau of the Ministry of Economic Affairs. At the same time that the message B 2904 is entered into the part U2926 and entered into U2926 , Message A 2902 enters the top of part T2924 of switch 2900 at input port 2926. When the message moves down to the bottom layer, the first header bit 29 1 0 is removed from message A. The message B and the Message A moves synchronously, so while message A moves, message B moves down or right. In the bottom layer, the message B enters the master control unit and its movement is copied by the message A, which is set from the master to the slave copy latch. When the message B moves down, the first header bit 2912 is removed. Please also refer to Figure 12A. The timing of switch 2900 allows these two bits to move in a single clock cycle Π10. Therefore, each clock cycle bit moves down at a rate of two levels. In the bottom layer, the message A enters the main control unit again. When the message moves down to the bottom, message A and message B pass through the main control unit and lose the header bit. Each message loses one bit in every two layers and every clock cycle. The idea of replicating all latch states of all control units in a layer can be extended to more than two parts. For example, if the message 200 is split into 3 or 4 or more messages in the pattern described in FIG. 29A, the flow time setting used to split the message is divided by the number of messages obtained. Each layer has only one master control part, and the other parts are slaves. In the lower layer the main part rotates in all parts. Optical Message Layout Figure 30A shows the layout of an optical message. The first bit 202 announces the existence of a message and acts as a timing bit. Header bits (Η 1, H2, ·., (Please read the precautions on the back before filling out this page) Do · Line · ι ________- This paper size is applicable to China's national standard ((, milk) 8 4 specifications ( 210 Father 297 mm) 527798 Α7 Β7 Printed by the Military Industrial Cooperative of the Central Standards Bureau of the Baptist Ministry i. Invention Description ()

Hu) 3 002 has the same function as the electronic message 202 in the optical message. In one embodiment, the header bits 3002 are spaced apart from each other in the optical header in a manner similar to that in the electronic header 204. In another embodiment, all header bits occupy the same physical space in the fiber and therefore occur simultaneously, but using n different colors. This technique is called wavelength division multiplexing (WDM). In this way, n differently obtained wavelengths (I, h, ..., ln) are used. The presence of light at the wavelength slot lk conveys the same information as the existence of the light at the time slot Hk. In another embodiment, a hybrid approach is used. For example, two time positions can be occupied using the n / 2 wavelength. The optical payload 3010 carries data and provides in the optical message the same purpose as the electronic payload 206 for the electronic message 200. Figure 30A illustrates payload data carried at multiple time and wavelength positions. A dead time of 3 008 is provided to allow electrons to catch up to photons and calculate jitter of optical signals transmitted in the fiber. Optical Control Unit Refer to FIG. 30B and cooperate with FIG. 30A, which shows an embodiment of the electronic optical control unit 3030. Data in the form of optical signal 3000 enters unit 3030 via input lines NW3036 and S303 8. The data leaves the unit via the output lines SE3034 and N3032. If the unit 3030 is not at the top level, the message M leaving the unit through output port N3 034 will directly enter the unit's input port S303 8 from above. If the chapter element is at the lowest level, then the data leaving the output N3032 will leave the switch. If the unit 3030 is not at the lowest level, then the paper leaving the unit through the input line SE3034 will adjust the paper size to the national standard of China ((, NS) Λ4 specifications (210 × 297 mm) (Please read the precautions on the back first) (Fill in this page again), 11 527798 A7 B7, Central Standards Bureau of the Ministry of Economic Affairs β <Printed by Industrial and Consumer Cooperatives, Invention Description () Enter another unit through input port NE3 036. The operation of unit 3030 is similar to that of unit 1 300 Operation. Unit 3030 is a unit of layer J of the switch. AND gate 3 040 has only ONE output, which is where timing bit 202 reaches AND gate 3040 during time window, where the latch setting 3002 is high. Timing bit Element 202 is the first bit of the message header that enters the unit through input port 3 03 6. The timing bit 202 passes through the fiber connector 3066 and is converted into an electron by the 0 / E element 3062. The latch setting pulse 3002 Since the timing source 3042 reaches the gate 3 040. When the AND gate 3 04 0 changes from ZERO to ONE, the delay element 3044 sets the latch L3046 to ONE after a time delay of dh 3016, the time delay dh is the timing bit 202 and the header Bits 3 to 002 The latch 3046 is a positive-edge (sample-and-hold circuit) (in conjunction with the gates 3040 and 3050), which captures and holds the header bit 3002. Therefore, the latch 3046 can As a static one-bit register. At present, a small part of the optical signal entering the unit 3030 from the input line S3038 is guided by the passive fiber tap 3064 to the 0 / E conversion element 3048. Element 3 048 has Two functions, one function is to detect the optical first header bit 202 by entering the information of the switch through input 3038. If no bit is detected, the element 3048 has an output 値 ZERO. If the header bit 202 is detected The element 3048 generates a high electronic signal (ONE) for a period of dh 3008. This period is the time for the entire optical head to pass a given point. The latch 3046 is only at the timing of entering the message passing the input 3 03 8 The bit size is ONE or the header of layer J. The bit size is ONE. The size of this paper is applicable to the Chinese National Standard Rate (CNS) Λ4 specification (210X297 mm) (Please read the precautions on the back before filling this page)

1T 527798 A7 B7 V. Description of the invention () A high pulse (ONE) will only be generated in the case of the Ministry of Economic Affairs * Standards Bureau's M-industrial cooperation $ printing. The unit 3030 is one of the upper group 716 of the units connected to the lower layer. One of the following groups 718 connected to the lower layer has a gate 3052 replaced by a gate 3050. During the conversion of the header bits into the electronic and electronic device setting electro-absorption modulators 3054 and 3056, the message M is stored in the delay circuit 3060. The message M advances from the delay loop 3060 to a 3dD splitter 3058. The resolver 3058 delivers the same copy as the message M to the electroabsorption tuners 3054 and 3056. Only one of the electro-absorption tuners 3054 and 3056 is transparent at a given time. Therefore, light is allowed to leave the unit 3030 through one of the output ports 3032 and 3034. The components 3054 and 3056 remain in the fixed state set by the latch L3 046 until the latch 3046 changes state, at least until the next latch setting signal 3002 arrives. The unit 3030 is constructed using an electro-absorption tuner. Those skilled in the art can modify the unit to replace the electro-absorption tuner with a semiconductor optical amplifier or lithium niobate gate. Optical input unit See also Fig. 30E. The control unit 3030 is located on all layers of the switch 3070 except the top layer or the input layer. FIG. 30C illustrates an electronic optical input unit 3092, which is located only on the input layer of the switch 3070. The optical signal E3000 is externally composed when the communication bit 202 is synchronized with other messages and entered by the input unit 3 091. Especially ~, the sequence is if the external message E enters the unit 3092 by input 303 7 and at the same time another message B enters the unit by the line S3 03 8 and the electronic optical switch 3054 is set (please read the precautions on the back before filling (This page) --------- ^-This paper size applies to the Chinese National Standards (CNS) Λ4 specification (210X 297 mm) 527798 A7 _______B7 V. Description of the invention () Staff consumption of the Central Bureau of Standards, Ministry of Economic Affairs The cooperative prints 'transparent' so that the communication bits of each message reach the optical fiber 3034 at the same time. In the electronic message target to a clock displacement register 1100, the nature of the data stream or message 3000 in the optical fiber is that the data will not remain static until the data is released at a later time. An optical signal 3000 is always moving. Therefore, the input unit 3092 always receives an appropriate timing message 3000 at input 3037. In the case of the message B 3000 from the downward direction 3038, the message B is detected by the previously discussed element, and the latch 3046 is set to ONE before the external message E reaches the tuner 3054. After message B enters unit 3092, the tuner 3054 is set to be non-transparent and absorbs external message E, and the electronic occupancy signal on line BN3033 is transmitted upward to the external device, which indicates that the message is not received by switch 3037. The external device then constructs another message E to inject into the next latch setting 3002 cycle. Alternatively, when the external signal E 3000 enters the unit 3092 from the input 3037 and no message reaches the line S 303 8, the message E passes the electronic optical switch 3054 to leave the unit on the upper layer and enter the control unit 3030 on the third layer. The occupancy signal on line BN 3033 indicates that the message to the external device is not received by the switch. In one embodiment, the layer 0 unit of the switch 3070 receives the optical control signal, which indicates that there is space in the output device for a message. In this embodiment, the cells of the 0th layer are the same as the cells 3030 of other layers. In another embodiment, the 0th level control unit of the switch receives an electronic control signal to indicate the output device. A message 200 cannot be received. In this embodiment, the unit of layer 0 is slightly different from the unit of layer 1. Among them, the optical fiber output 3038 (Please read the precautions on the back before filling in the order-line ________-This paper standard applies to China National Standard (CNS) A4 specifications (210X297 mm) 527798 A7 B7 V. Description of the invention (Printed by the Consumer Cooperative of the Central Standards Bureau of the Ministry of Economic Affairs and the related 0 / E converter 4048 is replaced by a separate electronic connection. Figure 30E of the optical switch shows the optical fiber, control The interconnection structure of the unit and other components of the optical switch 3070. This figure is similar to Figure 17, in addition, the switch 3070 may have other rows (not shown). And not all rows must be equally spaced, so that in a pair of phases The length of the optical fiber 3086 between adjacent rows is not the same in all the rows. The message enters from the top 3072 and leaves from the bottom 3076. See also Figure 17. Messages moving to the right in a column can be dropped down preferentially or Continue to the right until the message reaches a control unit to allow the message to finally move downwards. Leave the control unit A 3030 and the optical signal M 3000 that preferentially moves to the right from line N 308 0 leaves cell A, where the line N is connected to the cell B on the line S 303 8 and above. The optical signal always leaves the cell B along the diagonal path 3082 from the line SE 3034. The cell B is connected to the line SE The following unit C goes down, so that unit C goes directly to the right of unit A. Obviously the purpose of the circular movement is that the message M can provide information immediately to block another message of unit B from moving preferentially from unit B to unit C. In the lower layer The message M takes precedence over the messages in the upper layers, as discussed in Figures 8A and 8B. In fact, the flow of messages, the sequence of movement, and the blocking that occurs in the optical switch 3070 and the electronic message 200 move through the same configured switch 1 The situation is the same for 700. The 3dD splitter of each control unit combines the small loss of optical energy of the optical fiber connectors 3066 and 3064 to cause the attenuation of the optical signal amplitude. To adjust the signal loss, the amplifier and regenerator 3090 are inserted between some rows The regenerator 3090 performs two functions: the optical signal 3000 is enlarged. Please read the precautions on the back first and then fill in the m thread. The paper size applies to Chinese national standards. CNS) A4 specification (210X297 mm) 527798 A7 __B7 V. Invention description () The Consumer Cooperative of the Central Standards Bureau of the Ministry of Economic Affairs prints sufficient strength for further processing, and changes or regenerates the binary information carried by the optical fiber to improve the signal And noise quality. In another embodiment using a semiconductor optical amplifier or lithium iron gate, the signal will be weakened by the system and needs to be regenerated. Message M can span more than one line at a given time. In fact, the message is in front of it The element can leave the switch after the message enters the switch after the message. In one embodiment of the switch 3070, the output line from the right is directly connected to the input line of the same layer on the left. In this embodiment, the entire message fits perfectly in one layer to ensure that the first bit of the message does not surround a row and collide with another part of the message. This feature can be applied to electronic and optical implementations. It should be noted that all messages are generally not the same length. The timing control of the switch 3070 enables the message to reach all units of a given layer and row at the same time. As an example for illustration, consider the embodiment of the 30E diagram with three rows, the four layers with the control unit, and the other layer with the output unit. The distance between the 0th line and the 1st line is equal to the distance between the 1st line and the 2nd line, but smaller than the distance between the 2nd line and the 0th line. The switch is designed to carry two lengths of messages, short message S and long message M. The output port 3085 on the right-hand side is directly connected to the input port 3083 in the same row. In addition, the short message S is suitable for two nodes in the same column. Therefore, for cell A in column R, W, and C, and cell B in column U, W, and C + 1, if the message moves from cell A to cell B, then At the time t when the first header bit of message S arrives at cell B, the last header bit of message S is already to the left of the node of cell A. (Please read the precautions on the back before filling in, -ιτ line-:-^ 4- This paper size applies to China National Standard (CNS) A4 specifications (210X297 mm) 527798 A7 __B7 V. Description of the invention () Central of the Ministry of Economy Printed by the Standards Bureau Consumer Cooperative In another example, a message stays long enough at a given level to pass four nodes. A clock X is irregularly ticked and states 0, 1 and 2. Appear at a reference time t (0), the clock X starts and reads 0. The short message is inserted into the input unit of the first line at time 0 3 03 0. A short message is inserted into the switch of line 0 at time 0. The message does not deviate and has the first A header bit, which arrives at the unit on the first line and the third layer at time ^. The message S is still on the third layer and has the first header bit, which arrives on the second line at the time t2 Layer of the unit. The message S is still on the third layer and has the first header bit, which arrives at the unit of the third layer of the 0th row at time t3. A delay time D1 is defined as. A delay time D2 is defined as t3-t2 The clock X changes from state ZERO to state ONE at time D1, and 2 * D1 changes from state ONE at time D1 State TWO and change from state TWO to state ZERO at time 2 * D1 + D2. This period extends in this way, so that the clock X will change from state ZERO to state ONE at time 2 * D1 + D2. Use simple rules to insert messages To the switch. The clock changes to state t, and the short message is inserted into the input control unit in line t. If the short message can be inserted in the input control unit in line C at time t, then the long message can be inserted at time t + D 1 is inserted in the input control unit of line C. Therefore, the short message can be aligned and the long message can also be aligned. The rest of the switching timing depends on the fiber length and delay between the units. The length of the loop. The length of the optical fiber and the delay loop can be adjusted so that the message reaches a predetermined unit 3030 to the input ports NW3036 and S3 038, in this way the electronic can accurately operate the switch. The delay loop 3060 is made appropriately Size so that after the switch is switched, the message through this circuit will reach the electricity (please read the precautions on the back before filling the order line _92_ This paper size applies to China National Standard (CNS) A4 specifications (210X297 mm) 527798 A7 ______ B7 V. Description of the invention () The sub-optical switches 3054 and 3056 are printed by the Consumer Cooperative of the Central Standards Bureau of the Ministry of Economic Affairs. Finally, the delay loop 3068 is adjusted so that messages arriving from any port leave the unit at the same time. For hybrid electronic / optical control, please refer to Figure 29B. A master / slave relationship can effectively move data through a switch. A switch 2900 performs the control function, in which the master and slave implement the same topology and information circulation system so that the main part can be driven. Dependent part. The slave part acts passively based on the passage of the message. The flow of information between the master and the slave is functionally the same but different in timing. The timing difference can be adjusted to provide a successful master-slave embodiment of the switch 100. In particular, based on the purpose of the lowest possible latency of a message with a longer payload 206, benefits are obtained by controlling a fast and very high bandwidth optical switch with an electronic switch that only processes the message header. This hybrid electronic / optical combination helps to take advantage of the best features of both technologies to produce an ultra-low latency and very high bandwidth switch. Please refer to FIGS. 30A and 30B. An optical message 3000 has a longer dark time 3008 and a long header 3004, and includes a “fat” (longer period) optical bit 3002, which can be an optical / Electronic device processing. In other words, the 3010 portion of the payload of the optical message 3000 is a fraction of the entire message length. The wide header bit and dark time 3008 are necessary to consider the jitter in the optical timing. Avoiding the use of expensive high-speed detectors and electronic optical switches can reduce the cost of each control unit 3030. The time for the header and control processing is adjusted by the delay circuits 3060 and 3068, which are on the order of one meter in length. Furthermore, the ungenerated delay loop delay is repeated in each control unit. On the other hand, when entering the optical payload 3010 (please read the precautions on the back before filling and aligning; _____ 93- This paper size applies to China National Standard (CNS) A4 specification (210X297 mm) 527798 A7 B7 Description of the invention () When the consumer cooperative of the Central Standards Bureau of the Ministry of Economy reset all the latches 3046 in the switch 3070 before printing, no delay loop was used and the control units were arranged adjacent to each other. Reduce the flow time or latency of the optical payload through the switch. See Figures 30B and 31. The high-speed electronic optical converters 3048 and 3 062 of the control unit 3030 are expensive and suitable for quickly switching electroabsorption tuners. High. An optical slave unit 3100 removes these two E / 0 converters and uses a low-speed electronic optical switch 3124. The unit 3100 is one level lower in cost and one level higher in speed. Electronic switches with the same topology and information flow only process Message header including communication bit 202 and column header 204. Because there is no payload to handle, no information is used in the electronic switch Output port 154. Using the fast logic described in the discussion of Figure 16B, after the last header bit has entered the switch, all latches of the established electronic switch 1620 are set to a clock cycle. For example, it is executed at 500 Hz The 10th layer switch with 11 header bits uses about 20 nanoseconds to set the latch 3 1 1 6. Please refer to the split header switch in Figure 29B and use high-speed technology to reduce the set time to 10 nanometers Seconds. While the header bit moves down through the electronic switch, the state of each latch 1616 is externally copied to the optical slave unit 3100. It should be noted that because of the The sequence is set from left to right, so the setting of one or more columns is transmitted by a single output pin 3114. A timing strobe signal 3110 for each control array including each column and row crossing is used to generate Latch status signal and copy the signal 3 1 24 to the optical slave unit latch 3 1 28. Latch (Please read the precautions on the back before filling ^ page)

、 1T line --- 94- This paper size is applicable to Chinese National Standard (CNS) A4 specification (210X297mm) 527798 A7 B7 V. Description of invention () (Please read the precautions on the back before filling-Lock 3128 setting electronic optics The switch 3130 or 3132 is transparent and the other is non-transparent. The electro-optical switch 3 130 or 3 132 has enough time to change the state before the optical payload arrives, so a cheaper device can be used. Figure 32. In one embodiment of the hybrid electronic / optical switch 3200, the same layout rules used in Figure 17 are used for the electronic and optical parts. In order to consider the difference in timing, the electronic header first enters the electronic switch and Transmit the latched state to the optical part 3 1 00. When all the latches are set, the transmitting optical payload passes, and because the optical fibers other than the delay loops 3060 and 3 068 are very short, the payload is moving through Very short total path length to leave after. If regeneration is used, add additional path length. As long as the trailing end of the optical payload has entered the top layer of the optical section, then The new electronic header is immediately transmitted to the electronic part. Based on the relative latency of each part, it is expected that there will be some overlap in the electronic and optical processing, thus reducing the pause time between messages entering the faster part. Printed by the Bureau of Standards Consumer Cooperatives, please refer to Figures 31 and 32, which show the interconnected way of controlling circulation, for two layers and two rows of hybrid electronic / optical switches 3200 derived from switch 1700 of Figure 17. Along the electronics department The latch setting d 3 1 06 of each row is transmitted through the control line 3114 to the latch 3100 in the possible position of the optical part. Using the timing flash 3112, the latch setting is multiplexed from one output pin. When the electronic main part When the timing synchronization of the part = is different from the timing of the optical slave part, a buffer can be used to store the switch settings provided by the electronics until the optical slave part needs the setting. What is related to each optical unit is Two long displacement registers with two compartments A and B. This paper size applies to Chinese National Standard (CNS) A4 (210X297 mm) 527798 A7 B7 V. Description of the invention (in the Ministry of Economic Affairs The CCB employee consumer cooperative prints the main part of the optics to send data to compartment A. If compartment B is empty, the bits flow from compartment A to compartment B. When the optical unit is ready for the data The optical unit obtains data from compartment B. Three different applications are discussed here. The first application discusses the situation where only one message bit is suitable for the shortest row of an optical switch. When one of the input devices to the switch transmits data to When aiming, the device injects the header into the electronic main switch. Because of the blocking condition, the device must wait for the data to be injected. When the first bit of the header is received by the electronic main part, the optical message immediately follows The gate is set and constructed. When the optical message enters the switch array, all switches are set. As messages pass through the switch array, other messages are converted from electronic to optical form before being injected. Also reproduces other messages. Other messages leave the switch and convert from optical to electronic form. Therefore, all the time through the optical switch is completely hidden by the simultaneous processing. The second application utilizes parallel electronic replication and is used when several messages occupy a single column of one layer of the optical switch. An extra buffer can be used for the latch setting. In the second form of the switch, each column of the optical switch contains K messages. This optical switch cannot perform the moth hole method. The optical switch contains K lines. The electronic part of the circuit includes K electronic copies of the optical switch. Each copy is executed as a wormhole. The rows of the optical switch are labeled CQ, C! '..., Cw. The electronic switch is labeled N. , K, ..., N ^. At time 0, the electronic switch n transmits data to the optical line n of an optical switch. At time t, the electronic switch n transmits data to the optical switch t + n mod K. This latch setting enables buffering. Please read the precautions on the back before ordering. The paper size is in accordance with Chinese National Standard (CNS) A4 (210X297 mm) 79 27 5 A7 _____B7 V. Description of the invention The application supports several messages on each layer of the optical switch. Use wormhole sending methods and buffering in switches to meet timing needs. The switch includes copies of K electronic switches NQ, K, ..., N η and a row C with K. , Q, ..., optical switches. The electronic switch Nj has a set of two long buffers which are connected to each unit of the optical switch. A wormhole transmission method of a header occurs in each electronic switch. At time 0, switch N. Start processing the header and transfer switch set to the optical unit. At time D, the switcher starts processing the header and the transfer switch is set to the optical unit. Generally, at time JD, switch N; starts processing data and transmitting settings to the optical switch. Whenever the electronic switch starts processing the header, the optical message starts processing the structure. At time K (D + 1), the optical information related to electronic switch N, is released, and this process will continue when a data wave is transmitted through the optical switch. The examples in this case have been described in detail, and the above description should not be used to limit the scope of patent application in this case. This case may be modified by anyone who is familiar with the art, but it is not inferior to those who want to protect the scope of the patent application. In addition, the switch is described in terms of “leftward”, “rightward”, “upward” and “downward” directions, and the terms included are only for consistency with the illustrated embodiments, and do not imply actuality. Directionality. In addition, many different types of devices can be connected, and the interconnection structures used include, but are not limited to, workstations, computers, terminals, ATM switches, telephone central office equipment, Ethernet and IP switches, and so on. This description and the scope of patent applications sometimes mean an interconnect structure in a multidimensional arrangement. This direction is helpful to understand the shape of the interconnect structure (Please read the notes on the back before filling in.

、 1T line-^-This paper size is applicable to China National Standard (CNS) A4 specification (210X297mm)

Claims (1)

527798 A8 B8 C8 D8 VI. Patent application scope NCm, where m is greater than k, or from a device Dc and a direct data output interconnection point outside the interconnect structure to a device Dc outside the interconnect structure; or It is a direct data output interconnection point to a node NEi on the Lk layer, where k is greater than i, so that the Li layer is closer to the destination layer U in the class organization. 3. The interconnection device according to item 2 of the scope of patent application, wherein in the device having a direct connection point to the node NAk, there is a priority relationship to transmit data to the node NAk, so that: at the Lk layer The previous node NBk has a direct interconnection point to the node NAk on a device Dc, where the device Dc is a ~ node N ci on the Lth layer or a device D c outside the interconnection structure. This priority relationship causes a message Mb to be sent from the node NBk to the node NAk, and causes a message Mc to be sent from the device Dc to the node NAk within the same time interval, causing the message Mb to be sent out to prevent the message Mc from being Submit. 4. The interconnection device according to item 丨 in the scope of patent application, wherein the interconnection structure carries information and control signals, the interconnection structure includes a node NE, and the node NE includes: the Consumer Cooperative of the Central Standards Bureau of the Ministry of Economic Affairs Printed (Please read the notes on the back before filling this page) A direct message input interconnection point for receiving a message Mα from a node Na; and a direct message input interconnection point for receiving a node from a node A message MF of one of NF; and the node Na has a control gate and a control output interconnection point for receiving a control signal CA from the node NF. The control signal CA forces the direct signal from the node NF to the node NE. The message input interconnection point has priority over the direct message input interconnection point from the node NA to the node NE, so that the node NF sends a message MF to the node NE and sends out a control _ 100 _ This paper standard applies to Chinese national standards (CNS) A4 specification (210X297 mm) 527798 A8 B8 C8 D8 VI. Patent application (Please read the notes on the back before filling this page) Signal CA to specify a blocking condition to The node Na and the node na control gate receive and specify the control signal CA of the blocking condition and block the transmission of the message Ma and the message MF reach the node NE at the same time corresponding to the control signal CA, resulting in the blocked message MA In another way, it is sent to a node ND, where the node ND is different from the node NE, and the node Nd is different from the node Na. 5. The interconnection device according to item 1 of the scope of patent application, wherein the interconnection structure carries information and control signals, the interconnection structure includes a node N ε, and the node NE includes: a direct message input interconnection point For receiving a message M A from a node Nα, the message M A having a header; and a direct message input interconnection point for receiving a message MF from a node NF; and the node Na has a control gate and a control output interconnection point for receiving a control signal CA from the node NF. The control signal CA forces the direct message input interconnection point from the node NF to the node NE to take precedence over the The direct message input interconnection point from the node Na to the node NE. When the selection device is the node NE and the message Ma is sent to the node NE, a message Ma caused by the lack of blocking control signal CA to reach the node Na is caused at the same time interval. The node NA control gate uses the header of the message Ma to determine the selection device for transmitting the message Ma. Printed by the Consumer Cooperatives of the Central Standards Bureau of the Ministry of Economic Affairs 6. The interconnection device described in item 5 of the scope of patent application, where: The node NAk control gate determines: In the first state, whether the node NAk has a direct output interconnection point to In the hierarchical organization, the node NE1 of the i-th layer that is closer to the destination layer Lo than the Lk layer, where the node NEi has a path to a designated output port designated by the message Ma; and in the second state, whether the node NEi has been The message is blocked; and ______101__ This paper size is applicable to Chinese National Standard (CNS) A4 specification (210X: 297 mm) 527798 A8 B8 C8 D8 6. Scope of patent application When the status of Brother 1 and Brother 1 is met, the node NA k controls The message NA is sent to the node NEi; and when the first and second states are not satisfied, the node NAk controls to gate the message Mα to the node ND, where the node NAk is different from the node NDk, and the node NEi is different from the node ND. 7. The interconnection device according to item 1 of the scope of the patent application, further comprising: a plurality of output ports, including a plurality of access outputs for accessing the Lk layer node NAk, which are stored through the interconnection nodes through paths. Each access output port accesses the node NAk, and also accesses the node NEi of the Li layer closer to the destination layer L0 than the Lk layer in the hierarchical organization, and the node NAk has a direct output Interconnect point to node NEi. 8. The interconnection device according to item 1 of the scope of patent application, wherein: a node NE has a first data input interconnection point from a node Na and a second data input interconnection point from a node NF And a control interconnection point between the node Na and the node NF to resolve the competition for transmitting a message to the node NE. 9. The interconnection device according to item 1 of the scope of patent application, further comprising: a node Nck at the Lk layer, with a direct data output interconnection point to be closer to the destination layer than the Lk layer in the class organization The node Nai at the Li layer of L0 has a priority relationship with respect to a message Mc, which moves to the node NC and is preferentially sent to the node NA in time T, but the message Mβ is blocked by the node Na, so Message Mc is skewed to an Lk-layer node different from node NCk; a node NGk at the Lk layer has a direct message output interconnection point to a node NDi at the Li layer, and the node NDi has a The path passes through the interconnection node to an access output port to access the message Mc. The message _____ 102_ ^ The paper size applies the Chinese National Standard (CNS) A4 specification (210X297 mm) --------- — (Please read the precautions on the back before filling out this page) Printed by the Consumer Standards Cooperative of the Central Standards Bureau of the Ministry of Economic Affairs and printed by the Consumer Standards Cooperative of the Central Standards Bureau of the Ministry of Economic Affairs and printed by the Consumer Standards of the Central Standards Bureau of the Ministry of Economic Affairs 527798 A8 B8 C8 _ D8 Τ 'is diverted The node NGk is a time τ from the first time step to the point where the message Me is directed to a lower layer; wherein the interconnect structure does not allow the message Mb at the time τ to block the message Mc . 10. An interconnection device comprising: a plurality of nodes; and a plurality of interconnection lines in an interconnection structure, and selectively connecting the nodes in a structure; the interconnection structure transmits the plurality in an unclassified manner The multiple messages entering the interconnected structure pass through multiple inputs; 阜, one of the multiple messages. The individual message M uses the wormhole path to send itself and move through the node, and only a part of the multiple bits During the transport of meta-messages between two nodes, the multi-bit meta-messages extend to multiple nodes. The interconnection structure includes: a node NE, having a first data input interconnection point from a node Nα, and from a node One of NF's second data input interconnection points; and a control interconnection point between the node Na and the node Nf to resolve the competition and send a message to the node NE. 11 · The interconnection device described in item 10 of the scope of patent application, wherein the mutual construction structure carries messages and control signals, the interconnection structure includes a node NE, and the node NE includes: a direct message input interconnection point To receive a message Mα from a node Na; and a direct message input interconnection point to receive a message MF from a node NF; and the node Na has a control gate and a control output interconnection point. In order to receive a control signal CA from the node NF, the control signal CA forces the direct message input interconnection point from the node NF to the node NE to take precedence over the direct message input interconnection from the node Na to the node NE. Point, so that the node NF sends a message MF to the node NE, and transmits ~ ________ 103_ _ _ This paper size applies the Chinese National Standard (CNS) A4 specification (210 X 297 mm) -------- -41 ^-(Please read the precautions on the back before filling in this page) Order 527798 A8 B8 C8 D8 VI. The scope of patent application specifies a control signal cA of the blocking condition to the node na, and the control gate of the node Na receives the specified signal. Barrier The control signal Ca corresponds to the control signal CA by blocking the transmission of the message Ma and the message Mf reaching the node NE at the same time, resulting in the blocked message MA being sent to a node ND in another way, where the nodes ND and The node NE is different, and the node Nd is different from the node Na. 12. The interconnection device according to item 11 of the scope of patent application, wherein the interconnection structure carries messages and control signals, the interconnection structure includes a node NE, and the node NE includes: a direct message input interconnection point, For receiving a message MA from a node NA, the message Mα has a header; and a direct message input interconnection point for receiving only MF from a node NF g; and the node NA A control signal and a control output interconnection point are used to receive a control signal CA from the node Nf, the control signal cA forces the direct message input interconnection point from the node NF to the node NE to take precedence over the node from the node The direct message input interconnection point from Na to the node NE makes a message Ma reach the node Na at the same time interval in the absence of a blocking control signal CA, which causes the node Na's control gate to use the message MA as a target. The header determines a selected device to transmit the message μα. In this case, the selected device is the node NE, and then sends the message MA to the node NE. 13. A method for moving messages through an interconnection structure, comprising: interconnecting a plurality of devices with a structure, the device having a plurality of message input terminals and a plurality of message output terminals, and a plurality of interconnection lines for transmission by one One of the device's message output terminal is connected to one of the receiving device's message input terminal in a way of connecting to the device; the message with multiple output message terminals connected to a single receiving device ________104 _ This paper standard is applicable to the Chinese National Standard (CNS ) Α4 specification (210 × 297 mm) ----------- (Please read the precautions on the back before filling this page), 1T printed by the Consumer Cooperatives of the Central Standards Bureau of the Ministry of Economic Affairs 527798 Α8 Β8 C8 D8 6 A patent application assigns a priority in the transmission device of the input terminal; input a message to the interconnect structure to be forwarded to one or more designated output ports; the wormhole path sends a message through the device, so that only A part of the multi-bit message is in transit between the two devices, and the multi-bit message is extended to multiple devices. Way to transmit a message from a transmitting device to a receiving device, and on the way to one or more designated outputs, the transmitting device does not need a command from the receiving device or receives a command from the receiving device to allow the message to be transmitted To the receiving device; contacting a plurality of transmitting devices to send a message to a single receiving device, a transmitting device having priority to send a message to the single receiving device, the single receiving device having a control signal output terminal, and an interconnection Line to a control signal input of a transmission device with no priority, the transmission device with priority transmits a control signal to the transmission device without priority; and from a transmission device originally transmitted to The message of the desired transmitting device is diverted, and the diverted message is diverted to another transmitting device which is on its way to the one or more output ports. 14. A method for moving messages through an interconnection structure, comprising: interconnecting a plurality of devices D to a node NE using a plurality of direct node NE input interconnection methods; and having a direct input interconnection point to a node NE Device D forces a priority relationship to send a message to the node NE; the wormhole path sends a message MA through the device D, so that only a part of the multi-bit message is in transit between the two devices. The bit information Mα extends to multiple devices; 105 paper sizes are applicable to the Chinese National Standard (CNS) A4 specification (210 × 297 mm) ----------- (Please read the precautions on the back before filling (This page) Order printed by the Consumer Standards Cooperative of the Central Bureau of Standards of the Ministry of Economic Affairs 527798 A8 B8 C8 D8 6. Scope of patent application (please read the precautions on the back before filling this page) In a time period τ will be a message from a node NA It is transmitted to the node Ne. At the time period τ, a message MA moves to the node NE through the node Na with a direct input interconnection method, and the message MA is directly sent to the node within the time period T. NE; and at the time period T, no message Mf is sent directly to the node NE or turned to the node Ne and moves through a node Nf with a direct input interconnection point to the node Ne, where the node Nf takes precedence over the node Na sends a message to the node NE. 1 5 · The method as described in item 14 of the scope of patent application, further comprising: if the node NF sends a message MF to the node Ne at the cycle time T, the message Ma is suspended at the cycle time T to The node na. 16. The method as described in item 15 of the scope of patent application, further comprising: transmitting the message MA that has been suspended to the node Nα to a node nd, which is different from the node NA and the node NE. 17. The method according to item 16 of the scope of patent application, further comprising: transmitting a control signal to the node na by the node NF, causing the message MA to be suspended and sent to the node Nα, and forcing the priority relationship . 18. A method for mobile information M to pass through an interconnection structure, the interconnection structure including a plurality of nodes N and a plurality of interconnection lines L to a plurality of output buffers B, the method includes: the Central Bureau of Standards of the Ministry of Economic Affairs The employee consumer cooperative prints the plurality of nodes N selectively connected by the plurality of interconnection lines L to obtain an interconnection line L (p, q) that directly carries data from a node ρ to a node q; a message Μ determines a group of nodes 0 (M), so that the output buffer B, which is the target of the message M, is connected to the group of nodes 0 (Μ); the wormhole path sends the message M through the node N, so that only a part The multi-bit message is in transit between two nodes, and the multi-bit message Mα extends to multiple nodes; ____106 _ This paper size applies to the Chinese National Standard (CNS) A4 specification (210 × 297 mm) 527798 A8 B8 C8 D8 6. Scope of patent application If the first part of one of the messages M is located at the node p at time t, then the message M is moved on an interconnection line L (p, s) at time t so that At time t + 1, the message M is located at a node s, where the The node s and the node ρ are different nodes; if the first part of the message M is located at the node ρ at the time t, and the shortest path from the node P to a node in the group of nodes 0 (M) Includes the cross reed interconnecting line L, which determines one interconnecting line L (p, q) such that the shortest path from the node q to one of the set of nodes 0 (M) includes the crossing H -1 interconnect line L; if at time t, the message M is not blocked by other messages, the interconnect line L (p, q) is used, so it is transmitted on the interconnect line L (p, q) at time t The message M such that at time t + 1, the first part of the message M is located at the node q; and if at time t, the message M is blocked by other messages using the interconnect L (p, q), then The message M is transmitted on an interconnection line L (p, r) at time t, where the node r and the node ρ are different nodes, and the node r and the node q are different nodes, and from the node The shortest path from node r to a node in the group of nodes 0 (M) includes no more than the crossbar L crossing. 19. A method for a mobile message M to pass through an interconnection structure, the interconnection structure including a plurality of nodes N and a plurality of interconnection lines L to a plurality of output buffers B, the method comprising: by the plurality of interconnection lines L selectively connects the plurality of nodes N, so that an interconnect line L (p, q) directly carries data from a node ρ to a node q; determines a group of nodes 0 (M) for a message M, so that The output buffer B of the message M target is connected to the group of nodes 0 (M); the wormhole path sends the message M through the node N, so that only a part of the multi-bit message is in transit between the two nodes The multiple newsletters _LQ2___ This paper is suitable for Chinese National Standard (CNS) A4 (210 X 297 mm) ______________%! (Please read the precautions on the back before filling this page) ·-丨 Line-Economy Printed by the Ministry of Intellectual Property Bureau's Consumer Cooperatives 527798 Printed by the Consumer Standards of the Central Standards Bureau of the Ministry of Economic Affairs I Α8 Β8 C8 D8 6. The scope of the patent application is extended to multiple nodes; if one of the messages M starts at a time t at Point ρ, and then move the message M on an interconnection line L (p, s) at time t, so that the message M is located at a node s at time t + 1, where the node s and the node P are different If the initial part of the message M is located at the node p at the time t, and the shortest path from the node P to a node in the group of nodes 0 (M) includes the cross-connected purlins Line L, which determines an interconnect line L (p, q) such that the shortest path from the node q to a node in the set of nodes 0 (M) includes the crossing Η-1 interconnect lines L; if At time t, the message M is not blocked by other messages using the interconnection line L (p, q), so the message M is transmitted on the interconnection line L (p, q) at time t, so that at time t +1, the beginning of the message M is located at the node q; and if at time t, the message M is blocked by other messages using the interconnect L (p, q), then the message M is transmitted at time t On an interconnect line L (p, r;), where the node r and the node p are different nodes, and the node Γ and the node q are different nodes, the message M is then time t + 1 Teleport On the line L (r, s), where the node s and the node ρ are different nodes, and the node s and the node q are different nodes, from the node r to the node in the group 0 (M) The shortest path of a node includes no more than the cross interconnection L. 2 0. — A method for transmitting a message, comprising: providing an interconnection device including a plurality of nodes N and a plurality of interconnection lines L, the plurality of interconnection lines L connecting the plurality of nodes N in a predetermined manner; Use the plurality of interconnection lines L to connect the plurality of nodes N for packing: A node Nα, which has a direct message input interconnection point to receive a message ___ 108 _ — This paper standard is applicable to China National Standard (CNS) Α4 specification (210X297 mm) ----------- (Please read the precautions on the back before filling this page), 1T 527798 A8 B8 C8 D8 VI. Patent Application Scope (Please read the precautions on the back first (Please fill in this page again for information) and have a direct message output interconnection point to transmit the message Mα to a plurality of nodes, the plurality of nodes including a priority node NP; which has the highest priority to receive the message Mα, the The priority node NP is determined by the sending message in one of the headers of the message Mα and the position of the node Να within the plurality of interconnection lines L; the priority node NP has a plurality of direct message input interconnection points to receive From One of the plurality of nodes is a message MP. The plurality of nodes includes a preferred node NB, which is preferably used to transmit a message to the priority node NP. The preferred node NB is included in the plurality of interconnection lines L. The position of the node NB is determined; the wormhole path sends the message MA through the node N, so that only a part of the multi-bit message is in transit between two nodes, and the multi-bit message MA is extended to multiple nodes If the node NA is the same as the node NB, transmitting the message Mα as if the message MP was transmitted from the node NA to the node NP; and if the node NA and the node NB are not the same and the node NB directs a message MB To the node NP, then the message MP is transmitted from the node vβ to the node NP. 21. —A method for transmitting messages, including: Printed by the Consumer Cooperatives of the Central Standards Bureau of the Ministry of Economic Affairs to provide an Internet for carrying multiple messages M at the same time, including: multiple output ports P; multiple nodes N Each of the plurality of nodes ν includes a plurality of direct message input interconnection points and a plurality of direct message output interconnection points, and the individual node N is configured to transmit a message M to a predetermined output port of the plurality of output ports P, The predetermined output port P is designated by the message M; and a plurality of interconnection lines L of an interconnection structure; ____109___ The mound paper size is applicable to the Chinese National Standard (CNS) A4 specification (210X297 mm) ^ 527798 A8 B8 C8 D8 Sixth, the scope of patent application (please read the notes on the back before filling in this page) The hierarchical structure of the hierarchical organization is used to selectively connect the nodes to include a plurality of J + 1 layers, where J is an integer greater than 0, and the layers are The class organization method consists of a minimum goal level L. Arrange to the highest level L: in the hierarchical organization, the most local layer L; the farthest distance from the lowest destination layer Lo, the output p is connected to the lowest destination layer L. The node includes one node NA of the plurality of nodes N in the Internet; the wormhole path sends a message M through the node N, so that only a part of the multiple bits of information is between two points. During transportation, the multi-bit message Mα extends to multiple nodes; limiting the number of messages allowed to enter the direct message input interconnection point of the node Nα to eliminate the congestion of the predetermined output port of the node Na, So that the message M is transmitted through the multiple direct message input interconnection points of the node Na to the node N 其, which is the Lth layer not higher than the layer of the node Nα, and the node NΗ forms the predetermined output to the message M The path of port P. 2 2-A method for transmitting a message through an interconnected structure of a class organization, the interconnected structure includes a plurality of nodes and a plurality of interconnected lines, the method includes ... The node is connected to include a plurality of J +1 layers, where J is an integer greater than 0, and a minimum destination layer L is formed in a layered organization. Ranked to the highest level Lj; The Consumer Cooperative of the Central Standards Bureau of the Ministry of Economic Affairs prints and inputs multiple messages to the interconnected structure through multiple input ports in an unclassified way; uses the wormhole path to send and move one of the multiple messages by itself The message passes through the node, and only a part of the multi-bit message is in transit between the two nodes. The multi-bit message extends to multiple nodes. The message M moves in multiple ways, including four ways. In order to allow the message M to leave the interconnection structure through an output port, the four methods include: _no___ This paper wave standard applies the Chinese National Standard (CNS) A4 specification (210X297 mm) — 527798 A8 B8 C8 D8 VI. Application Patent scope (1) The message M is input to a node in the interconnect structure from a device external to the interconnect structure, and the message M specifies one or more designated output ports; (2) moves without buffering The message M passes through a node in the interconnect structure to a designated output; (3) The message M passes through the interconnect structure without passing through the buffer. A node on the Lk layer to a different node on the same Lk layer; and (4) the message M is moved through a node on the Lk layer of the interconnect structure to the class organization without buffering Is closer to the target layer L than the Lk layer. Nodes on the Li layer. 2 3. — A method for transmitting information in an interconnected structure, comprising: arranging a plurality of nodes in a structure including a plurality of class organization layers, from a highest class organization layer to a lowest class organization layer, a plurality of A node crosses a cross section of a layer, and a plurality of nodes cross a cross section. The node has an input message connection point in the same layer and an input message connection point in a higher-level organizational layer. The layer has an output message connection point and an output message connection point on a lower-level organization layer; at least one target node is designated to receive a message; one node in the interconnect structure initiates a first message; The hole path sends a message through the plurality of nodes, so that only a portion of the multi-bit message is in transit between the two nodes, and the multi-bit% thunder only extends to multiple nodes; in the interconnect structure The step of transmitting the first message from one node to another node includes the steps of: determining at a first node whether a second node in a lower layer is: at 111 pages Zhang scale is applicable to Chinese national standard (CNS> A4 specification (210X297mm)) ----------- (Please read the precautions on the back before filling this page) Printed by the Consumer Standards Cooperative of the Central Standards Bureau of the Ministry of Economic Affairs System 527798 8 888 ABCD 6. In the process of applying for a scope of a destination node; at the first node, determine whether the second node is blocked by a second message; (Please read the precautions on the back before filling this page) When the second node is on the way to a destination node and the second message is not blocked, the first message is advanced to the second node in an unbuffered manner; otherwise, the first message is traversed to the second node in an unbuffered manner. A third node in the same layer as the first node, and the third node is on its way to a destination node. 24. The interconnection device described in item 1 of the scope of patent application, further comprising: nodes B and C in On a layer of Ljq, it is a node that can directly receive a message from a node A on a layer of Lj; devices D and E, each of which is a node on a layer of Lj.N, where N is greater than 1, or Devices outside the network The node B can directly send a message to the device D, the node C can directly send a message to the device E, the device D cannot directly or indirectly send a message to the device E, and the device E cannot directly or indirectly send a Message to the device. 25. — A method for transmitting a message using a wormhole path between multiple nodes in a network, where the message spans multiple nodes, the method includes: selecting multiple nodes can directly Send a message to a node D, the node has a relative position within the network; and the employee consumer cooperative of the Central Standards Bureau of the Ministry of Economic Affairs prints a number of nodes to establish a priority relationship for directly sending messages to the node D, the priority relationship end depends on the relative positions of the plurality of nodes. 26. The method as described in item 25 of the scope of patent application, further comprising: establishing the priority relationship within the network based only on the relative positions of the plurality of nodes. 27. The method as described in item 25 of the scope of patent application, further comprising: defining a plural number for a node A which can directly send a message to the node D __ 112__ This paper size applies the Chinese National Standard (CNS) A4 specification (210X297 mm) 527798 A8 B8 C8 D8 Six, apply for a patent range of nodes to directly receive messages from one of that node A; (Please read the precautions on the back before filling this page) Corresponds to one of the node A that arrived Message M. The node arranging the plurality of nodes is enabled to directly receive a message from the node A. According to a demand, the plurality of nodes are arranged as an accepting node to receive the message μ from the node A. Message M needs as a receiving node. 28. The method according to item 27 of the scope of patent application, further comprising: arranging to receive the information from the relative positions of the individual nodes of the plurality of nodes within the network and the information in one of the headers of the message M. The node a needs the message M. 29. The method as described in item 28 of the scope of patent application, further comprising: arranging the need to receive the message M from the node A from a most needed recipient to a least needed recipient. 30. The method according to item 29 of the scope of patent application, further comprising: determining whether the node D of the plurality of nodes that can directly receive a message from the node A is the highest of the message μ from the node A Recipients are required; it is determined whether the point A has the highest priority to send a message to the node D; and the employee consumer cooperative of the Central Standards Bureau of the Ministry of Economic Affairs prints that the point D is from the point A Message] y [is the most needed recipient and the point A has the highest priority to send a message to the section concession D, then send the message M to the node D. 3 1 · The method as described in item 27 of the scope of the patent application, further comprising: determining whether the node D of the plurality of nodes that can directly receive the message from the node A is the highest of the message M from the node A Recipients are required; and a relative priority is determined to include one or more of the nodes A to send a message to the node D; ___ 113 This paper size applies the Chinese National Standard (CNS) A4 specification (210 X 297 mm) 527798 A8 B8 C8 D8 VI. Scope of patent application (please read the notes on the back before filling this page) where if the node D is the most needed recipient of the message M from the node A and the message M is not by the node A transmits to the node D, and then has priority over the node A to transmit a message to a node F of the node d, and simultaneously transmits a message and the message M from the node a. 3 2 · The method as described in item 25 of the patent application scope, further comprising: for the node A and the node G that can directly send a message to a device D, the device D is outside the network or Is a node within the network; determines whether the node A has priority over the node G to send a message directly to the node D; and establishes a transmission path for the node A to send a control signal to the node G, the control signal indicates the higher priority of the node A. 3 3. The method according to item 32 of the scope of patent application, further comprising: designating the node A to have priority over the node G to directly send a message to the device D, and sending a message from the node G to the device D The time of device D is less than the time to send a message from the node A to the device D. 34. The method of claim 32, further comprising: using a message header and a control signal message at a node to send a message to other nodes in the network. Printed by the Employees' Cooperative of the Central Bureau of Standards of the Ministry of Economic Affairs 3 5-A network that uses a wormhole path to connect multiple nodes to send a message, where a message spans multiple nodes. The network includes: A node A; one or more nodes can directly receive messages from the node A; one or more nodes can send a control signal to the node A; and a node F can send a control signal to the node A but Cannot directly receive messages from this node A. 3 6 · The network described in item 35 of the scope of patent application, which further includes: _ 114____ This paper size applies to China National Standard (CNS) A4 specification (210X297 mm) 527798 A8 B8 C8 D8 A first connector is connected to the node A and a node e, the first connector can send a message to the node E; and a logic on the node A, the logic can determine to which node a message M is transmitted, The logic corresponds to a control signal received by the node A and an address message at the message M. 37. The network according to item 36 of the scope of patent application, further comprising: a second connector connecting the node F to the node A, the second connector can transmit a control signal to the node A; and The third link connects the node F to the node E, and the third link can send a message to the node E. 38. The network as described in item 36 of the scope of patent application, further comprising: a node A 'that can receive a message M', the node a can receive the message M; one or more nodes can directly Receiving a message from the node A; a connector from the node A to the node A ', the connector can transmit a control message; a logic on the node A', the logic corresponding to the transmission from the node a to The control message of the node A ', and the message M is sent according to the control message; Printed by the Consumer Cooperative of the Central Standards Bureau of the Ministry of Economic Affairs ---------- (Please read the precautions on the back first (Fill in this page) A node B can receive a message from the node a, the node A sends the message M to the node B; and a node B 'can receive a message from the node A, the node A 'Send the message M' to the node B '. 39. The network according to item 38 of the scope of patent application, further comprising: one or more nodes can receive a message from the node B; one or more nodes can receive a message from the node B, A message; a connector, from the node B ′ to the node β, the connector can pass 527798 A8 B8 C8 D8 VI. Patent application scope sends control message to the node B; and a logic on the node B, the logic corresponds to the control message from the node B ', and sends the message M according to the control message . 40. The network as described in claim 35, wherein: the one or more nodes that can directly receive a message from the node A include a node B and a node D, and the node A has a copy of a message M's ability to send a first copy of the message M to the node B and a second copy of the message M to the node D. '41. An interconnect structure S for transmitting information between a plurality of nodes using a wormhole path, wherein the message spans multiple nodes, and the interconnect structure includes: a plurality of nodes including nodes NA, ND, and NE A plurality of interconnecting lines, which are selectively coupled to the node of the interconnecting structure S; a plurality of devices in a device group I, and each other does not include the plurality of nodes; and the device in the device group I The device may be used to transmit data to one or more of the plurality of nodes; and the plurality of devices in a device group Z, and the plurality of nodes are not included in each other 'and the device in the device group Z may be used to receive-' at most Data of the plurality of nodes, wherein the device group Z includes a plurality of secondary device groups, and the plurality of secondary device groups further include: a primary device group TA, which is composed of the device tA, so as to transmit a message One device in the device group I is transmitted to the device tA via the node Nα; the primary device group TD is composed of the device tD, and a message is passed from one device in the device group I to the node Nd and teleport to The device tc &gt; and the primary device group TE are composed of the device tE, so that a message __116 This paper size applies the Chinese National Standard (CNS) A4 specification (210 X 297 mm) (Please read the back first Please note this page, please fill in this page again) Order · Line · Intellectual Property Bureau of the Ministry of Economic Affairs Printed by the Consumer Cooperative 527798 A8 B8 C8 D8, the patent application scope information is transmitted from one device in the device group I to the node NE through the node NE Device tE; where the Consumer Cooperative of the Central Bureau of Standards of the Ministry of Economic Affairs reports that the node Nα can send data to the node Nd; the node Na can send data to the node Ne; the device in the secondary device group TA is included In the secondary device group TD; and the set t A is included in the secondary device group TA and is excluded from the secondary device group τΕ. 42. A network with a plurality of unbuffered node arrangements, which use wormhole paths to support the connection of messages, where a message spans multiple nodes. The network includes: one or more output ports; one or more inputs璋, for receiving messages, a message M arriving at one of the one or more input ports is designated to leave the network at one or more predetermined output ports; a first connector is located at an unbuffered node A To move the message M from the unbuffered node A to an unbuffered node b through the network; and a second link is located at an unbuffered node E for receiving directly or indirectly from the unbuffered node A The message M cannot receive the message from the unbuffered node B. ..f 43. As claimed in item 42 of the scope of patent application, it further includes: a third link is located at the unbuffered node A, the third link is used to send a message to an unbuffered node C; the node A cannot Receive messages directly or indirectly from Node B; Node A cannot receive messages directly or indirectly from Node C; Node C cannot receive messages directly or indirectly from Node B; (CNS) A4 specification (210 X 297 mm) (Please read the precautions on the back before filling out this page) Printed by the Employees' Cooperatives of the Central Standards Bureau of the Ministry of Economic Affairs 527798 A8 B8 C8 D8 VI. Patent application scope This node B cannot Receive the message directly or indirectly from the node c. 44. A scalable low-latency switch, comprising: a plurality of switch array elements selectively connected to a plurality of input ports and a plurality of output ports, and using a bug hole path and passing the plurality of switch array elements Send a message from an input port to a predetermined output port. Only a part of the multi-bit message is in transit between two array elements. The multi-bit message extends to multiple array elements. The plurality of switch array elements are connected to a plurality of rows C1 + 1 and a plurality of layers Lj + 1, the input port is connected to an individual switch array element of a highest layer Lj and when the highest individual switch array element is available, Constitutes an individual switch array element linking the message to the highest level; (a) an individual switch array element at a lower level directs the message to the predetermined output port and (b) obtains an individual switch at the lower level In the case of an array element, the switch array element in one layer constitutes transmitting the message to an individual switch array element in a lower layer, otherwise transmitting the message to a switch array in the same layer Components; and the predetermined output port is connected to a lowest layer L. An individual switch array element, and when the predetermined output port is available, the predetermined output port is configured to receive the message from the individual switch array element at the lowest level. 45. The switch as described in item 44 of the scope of patent application, wherein: (a) the individual switch array element at a lower level directs the message to the predetermined output port and (b) obtains a signal at the lower level For the individual switch array elements, the switch array elements in one layer constitute to transmit the message to a different switch array element in the same row in a lower layer; otherwise, the message is transmitted to a switch array element in the same layer. 4 6. The switch as described in item 4 of the scope of patent application 'where: ____ Π8 ____——_ This paper size applies to China National Standard (CNS) A4 size (210x297 mm) (Please read the precautions on the back before filling in this Page), 1T 527798 A8 B8 C8 D8 6. The patent application scope of the switch array element includes an input control line to an individual switch array element of a higher layer. When the switch array element is not available, notify the higher layer. The individual switch array element. (Please read the precautions on the back before filling this page) 47. The switch as described in item 44 of the scope of patent application, which further includes: a register, which is selectively placed between at least two switch array elements in one layer . 48. The switch according to item 44 of the scope of patent application, wherein the message is a self-directed message including a message about the predetermined output. 49. The switch according to item 44 of the scope of patent application, wherein the message is a multi-bit message including a header portion and a payload portion, and wherein the switch array element sends the message according to the header portion . 50. The switch according to item 44 of the scope of patent application, wherein the message is a multi-bit message including a header portion and a payload portion, and wherein the switch array element sends the header according to the header portion. Message and remove one bit from the header section. 51. The switch according to item 44 of the scope of patent application, wherein the message is a multi-bit message, and wherein: the switch array element contributes a transmission path for the message; and the message is distributed along the transmission path of the dedication A plurality of switch array elements. 52. The switch described in item 44 of the scope of patent application, wherein the number of switch array elements at the highest level is greater than the number of input ports. 53. The switch according to item 44 of the scope of patent application, wherein the switch array element can copy the message as a duplicate message and transmit the duplicate message to a plurality of predetermined output ports. 54. The switch as described in item 44 of the scope of patent application, wherein: the switch array element is arranged in a row, and the individual switch array in a higher layer _______ 119 &gt; The paper size is applicable to China National Standard (CNS) A4 · ( 210X297 male D 527798 A8 B8 C8 D8 6. The patent application scope column element is located above the individual switch array element in a lower layer; the row includes a sub row and the layer includes a sub layer; and the switch array element includes a plurality of controls Unit, wherein the control unit is connected to one of the sub-lines and one of the sub-layers. 55. The switch as described in item 44 of the scope of patent application, wherein a plurality of control units of a single layer correspond to a different sub-line And the other control unit of the single layer corresponds to a non-individual sub-row. 56. The switch as described in item 44 of the scope of patent application, wherein: the switch array element includes a plurality of message paths including a first line Receive a first return message; an occupied signal exit port, when the first frame is occupied, it receives a first occupied signal; a second port is used to transmit a first A outward message; a third port for receiving a second return message; a second occupied port that transmits a second occupied signal when the third port is occupied; a fourth port used to transmit a first Two outbound messages, and a processor that processes the first return message to generate the first outbound message, and processes the second return message to generate a second outbound message. 57. As described in item 44 of the scope of patent application The switch, wherein the switch array element includes an electronic optical control unit. 58. The switch according to item 44 of the scope of the patent application, wherein the message is an optical message, and wherein the switch array element includes a hybrid electronic optical control unit. 59. The switch according to item 44 of the scope of patent application, further comprising a plurality of second switch array elements, selectively connected to the plurality of second input ports and the plurality of second outputs, and sending one and one from a first The news of the second input port _120_ — This paper size applies to the Chinese National Standard (CNS) A4 specification (210 X 297 mm) ----------- (Please read the precautions on the back before filling (This page), 1T Printed by the Consumer Standards Cooperative of the Central Standards Bureau of the Ministry of Economic Affairs 527798 A8 B8 C8 D8 VI. A second message related to the scope of patent application to a predetermined second input port, where: the second switch array element is connected to a plurality of Rows Ck + 1 and multiple layers Lj + i; (Please read the notes on the back before filling this page) The second input port is connected to an individual switch array element of the highest layer Lj and the highest layer can be obtained When the individual switch array element is an individual switch array element, it transmits the second message to the highest individual switch array element; when (a) the individual switch array element at a lower level guides the second message to the predetermined second output port and (B) When the individual switch array elements in the lower layer are available, the second switch array element in one layer transmits the second message to an individual second switch array element in a lower layer, otherwise the second switch array element is transmitted. Messages to a switch array element in the same layer; and the second output port is connected to a lowest layer L. An individual second switch array element, and when the predetermined second output port is available, the predetermined second output port receives the second message from the individual second switch array element at the lowest level. 60. The switch according to item 44 of the scope of patent application, further comprising a plurality of second switch array elements selectively connected to the plurality of second input ports and the plurality of second output ports and sending one and one from a first The second message related to the second input port to a predetermined second output port, wherein: the second switch array element is connected to a plurality of rows Ck + i and a plurality of layers printed by the staff consumer cooperative of the Central Bureau of Standards of the Ministry of Economic Affairs Lj + i; the switch array element is connected to a second switch array element; the second input port is connected to an individual second switch array element of the highest level Lj and when the individual second switch array element of the highest level is available When it transmits the second message to the individual second switch array element at the highest level; when (a) the individual second switch array element at the lower level guides the second message to the predetermined second output port and ( b) Individuals in the lower layer can be obtained. 121 This paper size is applicable to the Chinese National Standard (CNS) A4 specification (210X297 public envy T 527798 A8 B8 C8 D8. VI. Patent application scope second switch array Element, the second switch array element in one layer transmits the second message to an individual second switch array element in a lower layer, otherwise transmits the second message to a switch array element in the same layer; and (please first Read the notes on the back and fill in this page) The second output port is connected to a lowest level L. An individual second switch array element, and when the predetermined second output port is available, the predetermined second output port receives The second message from the individual second switch array element at the lowest level. 61. A switch array element for a scalable low-latency switch, comprising: a first port for receiving a return A message; a processor to process the return message to generate an outgoing message; an occupied signal exit port that transmits an occupied signal when the first port is occupied; and a second port structure to transmit the outgoing 62. The switch array element according to item 61 of the patent application scope, further comprising: a third port for receiving a second return message, wherein the processor processes the second return message. Return the message to generate a second outbound message; a second occupied port, when the third port is occupied, it transmits a second occupied 5 5 tigers, and a fourth port printed by the staff consumer cooperative of the Central Standards Bureau of the Ministry of Economic Affairs For transmitting the second outbound message. 63. The switch array element according to item 61 of the scope of patent application, wherein the message includes a header portion and a payload portion, and wherein the processor is based on the header portion Send the message. 64. The switch array element according to item 61 of the scope of patent application, wherein the message is a multi-bit message including a header portion and a payload portion, and wherein the processor is based on the standard. This message is sent in the header and from ------122_ This paper size applies to China National Standards (CNS) A4 secret (21〇 × 297 mm) 527798 Printed by the Consumer Cooperative of the Central Standards Bureau of the Ministry of Economic Affairs 123 A8 B8 C8 D8 Patent Application Scope This header part is removed by one bit. 65. The switch array element according to item 61 of the scope of patent application, wherein the processor is a switch to send the message. 66. The switch array element according to item 61 of the scope of patent application, wherein the message is an optical message, and the switch array element includes an electronic optical control unit. ^ 67. As described in item 61 of the scope of patent application, the message is an optical image, and the switch array element includes a hybrid electronic optical control unit. 68. A switch array element for a scalable low-latency switch, comprising: a plurality of row ports and a plurality of layer ports; and a plurality of control units, wherein a control unit is connected to a row port and a layer port, and A first port is used to receive a return message, a processor is used to process the return message to generate an outgoing message, an occupied signal exit port, when the first port is occupied, it transmits an occupied signal, and a second port The organization transmits the outgoing message. 69. A method for transmitting a message from an output port to a predetermined output port using a scalable to low latency switch. The scalable low latency switch includes a plurality of switch array elements selectively connected to a plurality of switch array elements. An input port and a plurality of output ports, the switch array element is connected to a plurality of rows C1 + 1 and a plurality of layers Lj + i, and the method includes: when the individual switch array elements of the highest layer are available, the transmission is from a highest layer A message of the input port of a switch array element of an individual switch array element of Lj; when (a) the individual switch array element of a lower layer guides the message to the predetermined output port and (b) the lower In the case of individual switch array elements, the size of the paper is applicable to the Chinese National Standard (CNS) M specifications (21〇 &gt; &lt; 297mm (please read the precautions on the back before filling this page) 527798 A8 B8 C8 D8 Six The scope of the patent application is to send the message to an individual switch array element in a lower layer, otherwise transmit the message to a switch array element in the same layer; when the predetermined output port is available, transmit The message is from a switch array element of a lower layer to the predetermined output port; and using a wormhole path and sending a message to the input port to the predetermined output port through the plurality of switch array elements, only one of which is The multi-bit message is in transit between the two array elements, and the multi-bit message extends to multiple nodes. (Please read the precautions on the back before filling out this page.) Employee Consumer Cooperatives, Central Bureau of Standards, Ministry of Economic Affairs Printed_124 This paper size is applicable to China National Standard (CNS) A4 specification (210X297 mm)