DE19754466A1 - Multiprocessor system with data cell- or packet exchange, for topology-invariant communication - Google Patents

Abstract

The cell-switching exchange (CS), enables data packet transmission, as fixed length cells, from a functional unit (FE0) to one or more, other functional units (FE1, FE2). Each functional unit is allocated its own exchange input and output. Dedicated input and output are each coupled directly to the corresponding local processor bus of the functional unit. To send a data packet, a functional unit engages the exchange directly via the local processor bus. The exchange nominates the functional unit to receive a transmitted cell, sending out an interrupt signal. This receiver then reads the cell directly from the local processor bus. Functional unit and exchange are integrated mechanically and electrically, occupying the same board and having a common power supply. In addition, all components of the multiprocessor system are hardwired together. The cellular exchange is self-routing, with a routing header prescribed for the cells or with a self-routing header integrated into the cells.

Description

2.1 Field of technology

The techniques, methods and procedures presented in this document are organized on the one hand in the field of communication and computer networks, on the other hand they concern the area computer architectures, especially the methods used in parallel computing systems for interprocessor communication.

2.2 State of the art classifications

The presentation of the prior art requires a prior detailed delimitation of Terms from communication technology and computer architecture as described below is led.

2.2.1 Access procedures in communication technology

In data communication between two functional units A and B (as presented in claim 1), the following technical framework conditions can be distinguished:

• 1. Immediate coupling: A and B are directly through an exclusive communication line connected and can communicate in this way.
• 2. Indirect coupling A: and B are only indirect via an interposed comm communication unit connected. Communication units can be reduced in their function classify the underlying access method. For reasons of generalization (the classification scheme should also apply to ≧ 2 functional units) who which only considers multiple access methods at this point.
• (a) Buses: Buses provide a common, shared by each bus participant (communication partner) is a medium used for data communication. Bus architectures usually use a time-division multiplex method to enable multiple accesses. The for individual communication partners available bus bandwidth is divided over time the number of participants on the bus.
• (b) Switching units: Switching units are technical connection units that transmit messages via parallel, independent data paths (connection channels) between communication partners. For this purpose, a switching unit establishes connection channels between pairs of nodes from input / output end points (so-called input / output ports), so one or more ports are exclusively assigned to a communication partner. The guaranteed (maximum) transmission bandwidth for the switching duration of a connection channel and the possibility of dynamically configuring connection channels between different communication partners is further characteristic of switching units. In the underlying switching process, a distinction is made between the so-called circuit switching and the packet / cell switching.
  • i. Circuit switching: For the duration of a communication connection, input and output ports are electrically connected to each other. Parallel switching exchanges are ensured by space division multiplexing in the switching unit.
  • ii.) Packet and cell switching: Before the start of a message transfer, the messages are either divided by the sender itself or a fragmentation level between the sender and the switching unit into data packets. The data packets, in turn, are mediated indirectly and mostly memory-based between dedicated input and output ports. The switching unit usually works according to the space and time division multiplex method. Furthermore, the switching units can be divided according to the addressing and routing procedure used. A distinction is made between two methods, the external configuration of the switching route and the self-routing of the data packets.
    • A. External configuration of the switching route: The switching unit is programmed externally before establishing a communication channel. This configuration remains stable for the duration of the transmission and possibly until the channels are reconfigured.
    • B. Self-routing of the data packets: Data packets are provided with routing headers by the sender or an intermediary instance and can independently use this header to get from the input to the output port. In this method, a differentiation is again made between the switching of data packets of fixed length (cell switching) and variable length (packet switching).

2.2.2 Computer system technology

In the area of computer communication, the following system-technical distinctions can be made:
Board Area Network (board-level communication): All processors involved are on the same board, i.e. they form an electrical and mechanical unit with galvanic coupling.

System Area Network: All processors involved (functional units) are located in the same parallel computer system. This can be done using a backplane coupling, for example whose boards can be realized in a subrack. For communication between the Functional units are usually neither a physical implementation of the messages, nor routing is required because all communication partners are known a priori.

Local Area Network (LAN), Metropolitan Area Network (MAN), Wide Area Net work (WAN): The functional units involved are located in different housings or in different racks within a rack and communicate via one external network. There is at least one physical implementation of the message in LANs (OSI layer 1), as well as the addressing and segmentation of the message (OSI layer 2) not agile. In the case of inhomogeneous network structures, further tasks are performed (e.g. routing, protocol settlement etc.).

2.2.3 Communication procedures in MIMD architectures

According to Flynn [5], multiprocessor and multicomputer systems belong to the multiple instruction stream, multiple data stream (MIMD) architectures. MIMD systems can be distinguished and classified using a variety of architectural features (see, for example, [6]). With regard to the communication methods used for interprocessor communication, the following basic approaches can be distinguished:
Communication via a common memory: The memory serves as a common basis for indirect data exchange.

Communication through message transmission: With the so-called message passing procedure Ren communicate functional units by addressing and sending messages on the basis of a given communication and switching network.

2.3 State of the art

In this section, we will first look at common switching units, including their type fields of application. Then a classification of the switching units in existing multiprocessor systems made.

2.3.1 Crossbar distributors and their application

Crossbar distributors are among the classic representatives of the switching units construction of board and system area networks. You establish communication paths via a fold switches in an N × N connection matrix and are suitable due to their clear structure Chen architecture and the easy handling to build local multiprocessor / multi computer systems. Often, N processors are used via an N × M crossbar with M memory Memory units (memory banks) connected. The crossbar distributor is established in one centrally controlled connection interval a physical channel between one out chose {processor, memory bank} pair of nodes. This allows N processors in parallel and with full bandwidth to access a maximum of M memory banks without blocking. That in cross shooting Switching principle used is the switching circuit (circuit switching). In this method, a physical connection channel is used for the duration of the entire transmission in the crossbar distributor. Routing decisions become too The start of each connection is made centrally and the crossbar distributor is configured accordingly riert.

As the number of switching elements in a crossbar distributor increases with the connection The number is growing disproportionately and the production of large switching matrices is expensive busbar trunking as poorly scalable. This is also the reason why crossbar distributors with more than 16 × 16 connection ports are practically not used.

Example application: Ultrasound signal processing apparatus: The Ultrasound signal processing apparatus [9] uses a crossbar distributor around 4 (6) DSPs with 4 (6) memory banks to connect. The system is for processing real-time tasks such as B. Picture processing, determined. The crossbar distributor used is non-blocking in one stage and has a 6 × 6 switching matrix for establishing physical channels. It becomes central configured and does not offer automatic routing or buffering capabilities.

Example application: Sun UltraSPARC Workstation: Sun Microsystems Inc. used in the new generation of UltraSPARC I and II crossbar distributors [7], for parallel data access from N units (one or more SPARC-V9 processors and the UPA management module for the I / O subsystem) on the existing DRAM memory enable benches. The integrated crossbar distributor works asynchronously Circuit switching and also has an N: 1 multiplexer.  

Note: For the use of crossbar distribution based solutions in the environment of multiprocessor systems it is particularly characteristic that cross busbar trunking always only as a connection between processor and memory cher / peripheral units serve.

2.3.2 Packet and cell switching units and their application

The packet and cell switching units are - mostly as an integrated construction realized stones - switch-like interconnections, which operate on the principle of packet or Cell switching work on the basis of a message fragmentation, cf. section 2.2.1. They are used in the construction of medium and large telecommunications and Computer networks, but recently there are also fields of application in the area of local and sy stem area networks. Such mediation units are mostly crossbar in the literature switches.

Example application: Cray Y-MP 816: The supercomputer Cray Y-MP 816 implemented an architecture in which 8 CPUs via a 2-stage crossbar switch to 256 memory banks access. The crossbar architecture [4] consists of 2-stage cascades made of 4 × 4 and 8 × 8 Packet switching units with 1 × 8 demultiplexers - realizes a scalable packet-oriented Link mechanism, the data packets of variable length on the basis of preceding control bits (self-routing procedure) between any connected CPUs and memory banks without internal blockage mediated. The outputs are buffered via FIFO queues.

In many technical fields of application, however, packet and cell switching units can be found in separate (ie external) connection networks. Optionally, they can be connected in more cascades to form more complex topologies. This creates networks with widely differing switching properties with regard to fault tolerance, number of connection paths, freedom from blocking, signal propagation times, etc. Examples include omega, banyan, benes, clos, delta and hypercube networks. In contrast to solutions with crossbar distributors and circuit switching, the topologies achieved in this way are much cheaper, more flexibly configurable, but above all scalable as desired. In particular, ATM switches are used as packet and cell switching units to support the ATM (Asynchronous Transfer Mode) standard, which in turn are used to set up larger ATM switching networks (ATM switching network modules) (see, for example, [2] ). The basic properties of an ATM switch module can be represented as follows.

• - Packet switching (packet switching) of logical data packets via physical cells fixed size
• - Self-routing of the data packets divided into cells via non-blocking variable paths
• - Memory-based switching (packet cell memory) with FIFO output buffering
• - Physical (1: 1 and 1: M) channels (on-chip), virtual channels (external)
• - Variable transfer rates of logical packets by controlling the cell rate.

Define interface specifications of the ATM Forum, starting with layer 1 (physical layer) of the OSI reference model upwards, electrical and logical properties of interfaces to  Inputs / outputs of ATM switches via electrical or optical connections to each other connect and build networks of any size.

Note: Although there are already many technologies for building cell switching units such as ATM switches and factories are patented averaging units in no single computer architecture as board area net work (see section 2.2.2) for local interprocessor communication.

2.3.3 Use of communication units in multiprocessor and multi-computers systems and their disadvantages

At this point, architectural features of multiprocessor and multicomputer systems described, which relate to the organization of the units for interprocessor communication and co refer to operation. In particular, it refers to the classification introduced in Chapter 2.2 referred to the prior art.

Shared memory multiprocessor (SMP) systems

SMP systems enable interprocessor communication only via a common logical (but possibly physically distributed) memory. According to section 2.2.3, these systems therefore belong to the group of functional units with memory-based communication. According to the subdivision made in section 2.2.2, SMPs are practically represented in all areas. The access procedures used (according to section 2.2.1) as well as the technical implementation of the common logical memory can be very different in these so-called tightly coupled systems.

• - Common bus (time-multiplexed bus): Here, processors, if necessary with private buffers, form autonomous functional units. The resulting functional units communicate on the basis of a multiple access procedure with bus coupling (see section 2.2.1). Defined groups of functional units from the overall system are combined into small clusters. A cluster then consists of N functional units, a common bus and M local, shared memory banks. Within a cluster, the N functional units access the local physical memory banks via the common bus. Access to remote physical memory banks (ie, memory banks in other clusters) is provided by constructing a bus hierarchy (including the transitions between the buses). In this way, a common logical memory can be addressed. An example of such systems are Futurebus + systems [1].
  Disadvantages: The limitations of the SMPs with bus coupling lie on the one hand in the synchronization ploblematics caused by the close meshing of all the functional units involved. The synchronization of the accesses must be ensured both by hardware arbitration and by software-side synchronization means. When using fast, local buffers (caches) in the functional units, memory coherence problems also occur. Furthermore, bottlenecks in the transmission bandwidth (in bus-like interconnectors, the individually available bus bandwidth is divided by the number of participants on the bus) lead to massive scaling problems. The use of bus transitions also results in high runtime delays (memory latencies) for remote access.
• - Crossbar distributors: In newer architectures, crossbar distributors replace buses for access to local and remote memory banks. Multiprocessors based on the UMA, NUMA and COMA models are known [6]. The systems set up in this way communicate on the basis of a multiple access procedure with circuit switching (see section 2.2.1). The use of crossbar distributors prevents the bandwidth limitation that is characteristic of bus couplings, since each processor (functional unit) receives an exclusive channel with guaranteed bandwidth when accessing the memory.
  Disadvantages: Crossbar distributor-based solutions entail high configuration and hardware costs for larger topologies and thus limit the scalability of these systems. Further disadvantages, such as the delay delays under consideration as well as the coherence and synchronization problems, are also retained here.
• - Ring topology: The latest SMP architectures work according to the scalable coherent interface (SCI) model. Clusters are made up of 4-6 functional units, which are connected internally via a unidirectional high-speed ring. On the hardware side, the SCI model provides a logical, global address space into which each participant (processor, functional unit) can choose to view it. SCI-based systems communicate (according to the classification in Section 2.2.1) on the basis of a multiple access method with bus coupling. The scalability of SCI-based parallel computers is ensured through the use of additional gateways to bridge cluster boundaries. The SCI hardware continues to solve the memory coherency problem that occurs with such systems.
  Disadvantages: One limitation of these architectures is the different access times for read / write operations on remote memories. Read operations are orders of magnitude slower than write operations. Furthermore, there is a loss of performance in the case of local memory accesses within the functional units, since according to the SCI standard, messages or data which are visible within the global address space may not be stored in the processor-local cache memory.

Message passing systems

In multiprocessor / multicomputer systems that work according to the message passing procedure (see classification in Section 2.2.3), processors no longer communicate via a common memory, but through direct or indirect message exchange via logical or physical connection channels. According to the subdivision made in section 2.2.2, message passing systems are practically represented in all areas. The access methods used (according to section 2.2.1), as well as the technical provision of message channels, are very different in these arrangements, which are also known as loosely coupled systems.

• - On chip communication links: Special processor families such as the TMS320C4x generation [8] or representatives of the new ADSP-2106x series [3] have their own communication interfaces (links) that can be used directly for message exchange between processors in a multiprocessor network . Systems of this type communicate according to the classification in Section 2.2.1 on the basis of an access method with direct coupling. If there is a need here for processors to communicate with one another that are not directly connected to one another, then a software-based solution for the routing of the message must be implemented. Since the number of integrated links is physically limited (typically 2-6 links per processor), the topologies that can be achieved in this way are limited.
  Disadvantages: Due to the electrically limited spatial expansion of a link connection, only systems with board or system area networks can be built on this basis. The lack of a (physical) full meshing of the network also significantly limits the scalability of these systems. In these cases, software protocol layers take over the mediation between remote processors without a direct connection channel. This leads to additional tasks such as software switching of the transmitted messages. Furthermore, there are high delays, which depend on the topology and the computing load of the switching nodes.
• - Communication and computer networks: This category includes all (multi) computer systems that are used in accordance with Section 2.2.2 to set up LAN, MAN and WAN-like structures. The communication units used can be divided into two broad categories in accordance with the classification in Section 2.2.1. On the one hand, there are bus-based solutions (such as Ethernet LANs) that work according to the multiple access method on the basis of a common medium (shared medium). On the other hand, there are cell-based switching units with packet switching (for example ATM switches) that set up exclusive message channels and can thus transmit data using the message passing method. There are also hybrid solutions from both categories (e.g. packet-switching FastEthernet switches). Characteristic for all processes of message communication via such (computer) networks is the strict hardware and software separation between a functional unit (processor, memory etc.) as an electrical / physical unit on the board and an external communication unit (switch, LAN segment). Before a message can be transferred via the communication unit, this first requires bus-coupled access to a peripheral message converter (media adapter card, network interface card), which processes the message (corresponding to OSI layers 1 and 2a).
  Disadvantages: Viewed from the hardware side, this leads to the fact that adapted peripheral adapter cards are necessary for the respective external communication unit and network transitions are necessary for the coupling of different, inhomogeneous network structures. On the one hand, this increases material costs and effort when scaling such systems and, on the other hand, leads to high delays in communication between individual nodes in the system. If you look at this from the software side, the boundaries of the different components (media adapter card, interconnection, network transitions) within a logical message channel must be overcome by appropriate protocol hierarchies. This in turn increases the complexity of a realized logical channel and leads to significant fluctuations in the runtime of the messages at the usage level for channels with different protocol frames.

2.4 Advantages of the new approach

The new approach to interprocessor communication presented in this document offers the following technical advantages compared to the techniques described in Chapter 2.3:

• 1. Guaranteed bandwidths: The transmission bandwidth for a point-to-point com Communication between any two processors in the system is constant, independent depending on the number of processors and - by suitable Walil a standard Cell switching unit - definable within wide limits.
• 2. Scalability: The consistently homogeneous organization of the cell switching unit for interprocessor communication allows processors, regardless of their the actual physical positioning (on the same or different Boards), can be connected in the same way and according to the same Chen (homogeneous) procedures can operate message communication. This enables illuminates the simple construction of systems of any size based on smaller clusters (Boards). Even with distant communication (several km) there is no need for inhomo genes (i.e. technically differentiated) hurdles to be overcome. The through the Cell-based switching resulting delay delays move for small and large systems in a narrow tolerance range.
• 3. Minimal effort: The technical (hardware-side) effort for both the Reali sation of local communication on an example presented in this document Board as well as in the implementation of message communication across board boundaries is minimal and comparable to a ring or bus based solution, at deut better framework conditions in the performance of the system. The software side Auf wall is limited to the initial configuration of the cell switching unit and the Dynamic management of packets / cells necessary for realizing virtual channels. The self-routing property of the switching system eliminates the need for one dynamic configuration of the cell switching unit.
• 4. Technical integration: By combining the cells shown in this document switching technology with the framework conditions and standards specified in the ATM forum large distributed systems can be developed that can be homogeneously integrated into existing tech Embedding systems and integrating them seamlessly from the point of view of message communication leave. This partially eliminates the switching units (network transitions) that are used by Coupling of specialized computing systems to standardized computers and communication networks become necessary. By integrating a homogeneous procedure for booting and initializing the functional units, the maintainability of large systems becomes essential simplified.

2.5 How it works 2.5.1 Technical problem

The problem underlying this invention is to build a multi-processor system from several functional units so that

• 1. each functional unit consisting of the processor, its assigned working memory and, if applicable Peripheral units exist,
• 2. The functional units exchange data with one another according to the message passing principle can (local communication),
• 3. N ≧ 3 of these functional units each have a mechanically and electrically common one Have structure (i.e., are built on a common circuit board, common Own power supply, etc.) and thus form a board,
• 4. Any number of boards with each other via external interfaces and switching units which can be connected so that functional units on different boards if they can communicate with each other via message passing (remote communicati on),
• 5. Local and remote communication from the point of view of the function on the processors running software are handled identically, and
• 6. starting from a master functional unit, all functional units on one board can load their initial operating software using the message passing functionality, d. H. do not need their own read-only memory.

2.5.2 Definition of terms

Functional unit (FE): is an independent processor, possibly with local RAM and assigned peripheral units such as timers, direct memory access (DMA) controllers etc. For the purposes of this document, it is immaterial whether local RAM and peripheral on units with the processor partially or completely integrated on a chip, or as separate components are attached to a common circuit board. Characteristic for a VU is the dedicated electrical and logical assignment of RAM and peripheral Units to the processor. A computer made up of several modules is not an FE in this sense.

Communication: is the transfer of a digital message from one VU to another. Usually, certain areas are transferred from the memory of the sending VU to the Memory of the receiving VU copied. For the purposes of this document, it is irrelevant whether this copying process from the processors to the FEs or special peripherals Units (DMA) of the respective FE'en is executed.

Package: is the unit into which messages from the sending VU are broken down before being sent the. The receiving VU expects messages as a sequence of packets. The size of the Packages are usually not specified and are e.g. B. before exchanging messages agreed between sender and receiver by exchanging special control packages.  

Switching unit (VE): A VE allows N electrically or optically connected FEs communication with each other. Allows the VE to communicate from N / 2 disjoint pairs of FEs with full transmission rate (message flow), it is called non-blocking.

Cell switching unit (CS): A CS is a VE, the messages only in Units of fixed length (e.g. 53 octets), so-called cells. To do this, packages, before being passed to the CS, broken down into cells (segmentation). The CS treats each cell of a packet individually, and usually without belonging to know the cell about a package.

A routing header in front of or behind the cell, which is used for the CS information about the treatment of the cell (e.g. the output port to which the cell is to be switched) contains is not part of the cell in the sense of this definition; especially then not if the routing header itself - changed or unchanged - to the initial Port of the CS is conveyed.

Cell: is the mediated unit of a CS. All cells in a system have the same fixed length. Let the length of a cell (in bytes) be N _C.

Port: is an input and output of a CS.

Routing: is the process of getting the correct one for a cell arriving at an input port Determine output port. A CS recognizes the output port from one to the cell attached routing header is called the CS self-routing.

Header: is a field in a cell that contains information about the cell, e.g. B. Information about the destination of the cell, the way to get there, its priority or a checksum. The length of the header is N _H.

Payload: is the user data portion of a cell, i.e. the cell without a header. Let the length of the payload be N _U.

Routing header (RHeader): is a field that exists outside of the cell that is used when entering of a cell in a CS defines the output port of the CS to which the cell mediates shall be. In addition, the RHeader can also provide information about the handling of the Cell, e.g. B. their priority or type. An RHeader in the sense of this definition is also a value that is only temporarily contained in a register with the value set out above Meaning that the cell logically (meaningfully), but not necessarily spatially (im Meaning of adjacent storage, etc.).

Segmentation and Reassembly (SAR): is the process of breaking a packet into cells (segmentation), and the subsequent assembly of a number of cells into one Package (reassembly). This can either be done by the processor of an VU through its operation software (soft SAR), or by a dedicated peripheral unit FE (hard SAR).

Local: are all FE's called to each other, which are on the same device according to this document are building. FE'en on different devices are called remote or remote.  

2.5.3 Elementary communication functions

This section describes the individual functions that are used to communicate two FE'en in the FE'en themselves and in the CS are required.

Segmentation, segmentation: breaking down a packet into cells and providing the cells with a header.

Addressing, addressing: Providing a cell with an RHeader.

(Cell) switching: copying a cell from an input port to one or more, output port (s) defined by the cell's RHeader.

Channel routing (CR): Replace the address information in the header of a cell with the Address information of the next CS on the way to the final destination, immediately before or after a CS on the way. This replacement happens under control The operating software by the processor of an FE, it is called soft-CR, is in hardware realized, it is called hard CR.

Reassembly, reassembling: assembling all originally by segmentation one The resulting cells form a package that is identical to the original one. Doing so the header of each cell is discarded.

2.5.4 Minimal system

The tasks 1 to 3 defined in section 2.5.1 are solved by a minimal system according to claim 1. The minimal system consists of N ≧ 3 FEs and a CS, see Fig. 1.

In the minimal system, only the functions segmentation, addressing, switching and reas are sembly included. A complete communication process consists of sending one Packet as a result of cells by the transmitter, the switching of the cells by the CS, and the recipient receiving the packet as a result of cells.

Basic procedure for sending a packet: The sending of a packet of length N _P from the memory of the functional unit FEm (transmitter) to the functional unit FEn (receiver) takes place in the following steps:

• 1. Reading the first N _C bytes of the packet in the memory of the FEm results in the payload of the first cell.
• 2. Provide the payload with a header. A cell is created.
• 3. Provide the cell with an RHeader. The RHeader contains (if necessary in coded form) the Number n of the target VU.
• 4. Transfer the cell extended by the RHeader to the CS (set the signal data Write request).
• 5. If the packet has not yet been completely transferred, accept the next N _C bytes of the packet as the payload of the next cell and continue with step 2.

Fig. 3 illustrates the steps 1 to 3.
Basic procedure for receiving a packet: If a cell is available at the output port of the CS, this generally triggers an interrupt (setting the interrupt signal) for the receiving VU. The receiving process takes place in the following steps:

• 1. Read a cell, possibly additional RHeader, from the output port of the CS.
• 2. Determine the associated reception area in the VU's memory using the header.
• 3. Copy the payload into the reception area of the memory of the package FE.
• 4. Discard header and (if applicable) RHeader.
• 5. Repeat all steps until the packet is completely in the receiving area of memory is present.

Essential for the results shown in Fig. 1 construction, the interface is fs for connecting the local bus of the FE with the associated input and output ports of the CS according to Fig. 2. As tenbus associated with the processor of the FE and the FE, inputs and the output port of the CS are coupled via an octet register or -FIFO for each direction (send / receive).

Clock signals: A sequence control generates

• - The clock signals synchronized to the cell clock of the CS
  • for writing received data from the CS into the cell / octet register (CS receive clock),
  • - to read data to be sent from the CS from the cell / octet register (CS send clock),
• - The clock signals synchronous to the processor clock (FE clock)
  • - for reading received data from the cell / octet register via the data bus of the FE (FE receive clock),
  • - For writing data to be sent from the data bus of the VU to the cell / octet register (VU transmit clock).

The cell clock f _{CS, c of} the CS marks the beginning of the transmission of a cell for all ports of the CS. n _wCS the word length of the ports of the CS (in bit), N _c the length of a cell (in octets), N _RH the length of the routing header, then applies to the CS receive clock f _{CS , e} and CS send clock f _{CS , s} :

f _{CS, e} = f _{CS, s} = (N _c + N _RH ) f _{CS, c} / n _wCS .

CS-side synchronization: CS send clock and CS receive clock are only during the Transfer of a cell between CS and cell / octet register active. To recognize this The following signal lines are used:

Cell-ready display: The CS thus signals the sequential control system that, starting with the next cell cycle (f _{CS, c} ), a complete cell, possibly with RHeader, ((N _c + N _RH ) octets) is read from the output port of the CS can be.

Send request: With this, the sequential control signals to the CS that, starting with the next cell cycle (f _{CS, c} ), a complete cell with RHeader ((N _c + N _RH ) octets) is to be written into the input port of the CS.

VU-side synchronization: The VU can write to the cell / octet register by itself and sets the signal data write request, or read from the cell / octet register and sets the signal data read request.

• - If the VU sets the data write request signal in the send direction and then writes to the cell / octet register, the sequencer sets the send request signal to indicate to the CS the presence of a cell to send.
• - If the signal sets the cell ready display in the receiving direction of the CS, the sequence sets control the interrupt signal.
• - If the interrupt signal is set, the CPU of the VU interrupts its normal program execution and jumps to a service routine which then reads a complete cell from the cell / octet register and writes it to the VU memory.
  Note: In general, the sender and recipient must know the length of the packet. This information can e.g. B. can be replaced by protocol cells before the packet is transmitted.
  Note: The header usually contains a description of the virtual connection, so that several virtual connections that can be clearly distinguished by the operating software can originate from an VU or arrive at an VU. The unique identification in the RHeader enables the operating software to assign each incoming cell to the associated virtual connection. The RHeader, on the other hand, is used by the CS to forward cells taken over at an input port to the correct output port. This information is also implicitly contained in the header, but the use of an additional RHeader with the explicit destination port number allows the hardware of the CS to be executed more easily. In principle, the RHeader can also be omitted, step 3 is then omitted.
  Note: The transfer of the cell extended by the RHeader to the CS can e.g. B. in the address space of the FE mapped registers of the CS or with the help of a special I / O address area, under the control of the CPU or a DMA integrated on the FE or in the CS.

A cell arriving at the input port m of the CS is either identified using the header implicit target information or based on the explicit target contained in the RHeader provides information on the output port n, d. H. physically copied.

Note: The delay between the incoming cell at the input port and Appearance of the cell at the corresponding output port of the CS is implementation dependent.

Note: An existing RHeader can use the cell to the output port mediated or removed from the CS.  

2.5.5 Possible solutions for SAR

The decomposition of a logical packet present in the memory of the PE into cells of the same size is carried out by a device according to claim 4 or claim 8.

Breaking down a package into payload units, providing associated (i.e. to correspond to) corresponding header and possibly RHeader on the transmitter side (seg mentation), and vice versa extracting the payload from incoming cells and anein rows of these payloads to received packets according to the connection information in the header (reassembly) can be controlled by the operating software according to claim 4 CPUs of the respective FEs are made (soft SAR), or as hardware function according to claim 8 through a special peripheral unit of the FEE (hard SAR).

Soft SAR: A possible implementation of soft SAR is shown in Fig. 4. The complete package and a field with prepared headers and RHeaders are stored at separate locations in the VU memory. Cells are successively formed in that are copied into a cell buffer to be next to the next header / RHeader from the prepared field, the next N _u octets from the package. Then the pointer to the header / RHeader field is incremented by the size of a header / RHeader, the pointer to the packet by the size N _{u of} a payload. The cell buffer is then written word by word to the cell / octet register.

When a packet is received, the process is reversed. The main differences are:

• - The address information of the header is used to determine the storage address of the packet determine.
• - Header and RHeader are discarded.

Hard SAR: FIG. 5 shows a possible solution for hard SAR. Part of the VU is a SAR unit consisting of a DMA (Direct Memory Access) controller, cell register, header / RHeader register and modification register. The sequence is as follows:

• 1. The CPU initializes the registers of the DMA controller with the address and length of the packet, and the header / RHeader register with the header / RHeader of the first cell.
• 2. The SAR unit copies the header / RHeader register into the cell register, and then fills it up with N _u octets from the memory of the VU.
• 3. The SAR writes the contents of the cell register to the input port of the CS.
• 4. The modification register is added to the content of the header / RHeader register.
• 5. Steps 2 through 4 are repeated until the packet is completely transmitted.

To receive a packet, the reverse steps are followed accordingly.

2.5.6 FIFO coupling

By expanding the cell / octet register to the FIFO according to claim 5, the temporal Processes of FE and CS decoupled.

In addition to the functions described so far, the sequence control monitors the validity of the data stored in the FIFOs. It applies the following rules:  

2.5 How it works

• - Complete cells contained in the receive FIFO are always valid.
• - If a receive FIFO overflows, ie the receiving VU reads the FIFO more slowly than the CS describes for a certain period of time
  • the interrupt signal of the sending VU is set at the time assigned to the first cell that causes the receive FIFO to overflow,
  • - the transmit FIFO memory of the sending VU is invalidated, ie deleted,
  • - All cells affected by the invalidation in the transmit FIFO memory are rewritten by a handling routine of the transmitting FE for the interrupt signal in the transmit FlFO memory.

The larger the receive FIFO memory chosen, the stronger the decoupling and the more the reaction of the CPU to an interrupt signal may take longer without losing cells go.

Is according to claim 6, the receive FIFO memory (from CS to FE) much larger ge selects as the transmit FIFO memory (from the VU to the CS), on the one hand becomes the decoupling improved, on the other hand the number of lost cells in the event of a receive FIFO overflow minimized.

2.5.7 Booting the FEs

Booting is the first loading of the operating software of the processors of the FE'en into their local memory or in the internal memory of the processors after a system start (reset) Understood.

A boot function in the fs interface (see Fig. 1) allows this operating software (boot) to be loaded from a master VU on the board or from an EPort (for the definition of an EPort, see section 2.5.8.).

A network boot ability in the above sense and according to the problem No. 6 leaves can basically be implemented in the following ways:

Boot cell mode: according to claim 2. Here, the entire device including CS is operated during booting in a special boot mode. In this boot mode, the entire cell consists of N _C user data, ie N _{U, boot} = N _C. From a receiving VU, these boot cells can be written directly into memory (using DMA) and then executed by the processor. The fs interface may have to remove RHeader copied from the CS to the output port from the boot cells. After booting all VUs, the device changes to the operating mode with the usual division of a cell into header and payload.

FE boot mode: according to claim 3. Here only the fs interface of the FE to be booted put into boot mode. In this boot mode, received cells are directly (using DMA) is written to memory in immediate succession and then output by the processor leads. The fs interface must be the header of the cells and possibly from the CS to the output port Remove copied RHeader from the boot cells. After booting, the fs interface changes in operating mode, in which cells, as described in the previous sections, be treated.  

2.5.8 Scalable system

The device described so far in the following board (B) - is scalable and solves there with the problems No. 4 and 5, if - according to claims 9 and 10 - any many boards while maintaining the communication properties (i.e. the logical view of the Communication functions) can be connected to a larger system.

A basic requirement for this is the existence of free ports on the CS, i.e. H. the CS must have more ports than there are FEs on the board. These ports have in egress Direction (leaving the board) at least PHY functionality, in ingress direction (from au incoming) at least PHY, meaningfully also addressing and CR functionality.

PHY functionality: implementation of voltage levels and data format based on the Board used in an electrical or optical line code, the transmission allowed over longer distances on symmetrical copper wires or optical fibers, and vice versa.

Addressing functionality: see definition in section 2.5.3.

CR functionality: see definition in section 2.5.3

In particular, PHY functionality allows the connection of boards that are not common all electrical and / or mechanical structures are marked, d. H. connection of Boards over longer distances, floors or even - if the PHY interface con form to a telecommunications standard - in worldwide networks.

Addressing functionality for ingress traffic basically performs the same function as for in-board traffic: reduction of the hardware complexity of the CS by adding a cell with an explicit routing address (RHeader, number of the intended for this cell output ports) based on the implicit address of the recipient contained in the cell header. In principle, the addressing functionality could also be integrated in the CS.

CR functionality for ingress traffic enables the renewal or exchange of the implicit target information contained in the cell header for cells that are not intended for a receiver on the board. The address information of incoming cells is used to determine the new address information up to the next switching unit on the way to the final destination and to replace the old address information with the new one. Before the actual transmission of packets, this method requires the establishment of a connection by occupying corresponding routing tables in the switching units. In the configuration of FIG. 7, CR functionality enables e.g. B. sending cells from a VU to B0 via the CS from B1 to a receiving VU on B2.

The construction of larger networks of boards with good scaling properties, ie with the number of boards in the system increasing total communication bandwidth, requires a construction as shown in FIG. 8. Here, several boards are connected by switching units which consist of a CS with, at least the number of connected boards corresponding number of EPorts. The above applies to the functionality of the EPorts.

In addition, two of these switching units can be connected directly to one another via EPorts become what enables the construction of networks of any size.  

2.5.9 Embodiment

Fig. 9 shows an embodiment of a device according to this document with the following egg properties:

• - 6 FEs with one digital signal processor (DSP) on each board.
• - Integrated ATM switch as CS.
• - Soft SAR.
• - Entire board bootable from the master FE.
• - Scalable through reports.

The essential components of the exemplary embodiment are explained below.

DSP master unit: This VU contains a signal processor (DSP), local working memory (RAM), read-only memory for the boot process (EPROM), some not further here written peripheral units (VMEC - VME bus controller, JTAGC - JTAG test bus Controller) and an interface dsm to the CS (SWITCH).

DSP slave unit: This FE is available five times on the board and differs differs from the DSP master unit in particular due to the lack of a read-only memory (EPROM) for booting. The interface dss to the switch is except for the boot functionality and missing control functions identical to the dsm interface.

SWITCH: This is the CS with a total of eight 16-bit wide input / output ports. The whole SWITCH is a single integrated circuit. Two of the eight ports are used for EPort Functionality used.

BNI: The BNI contains PHY functionality in the egress direction and PHY, addressing and CR functionality in the ingress direction. At the bb interface between BNI and the Connectors for connecting to other boards and / or dedicated intermediaries All relevant ATM specifications are met. The sb interface is essentially UTOPIA-1/2 compliant.

dss interface: The dss interface consists of two FIFO memories (one for Sen and receive), the FIFO memory for sending significantly fewer entries includes as the one for receiving, and one implemented as a finite state machine (FSM) running control. The FSM ensures the synchronization of the DSP bus with the cell Cycles of the SWITCH, for the correct handling of FIFO overflows (backpressure to SWITCH, interrupt to DSP), and for removing the RHeader at boot (Boot cell mode).

dsm interface: The dsm interface consists of a dss interface without boot cell Support, as well as an additional bit serial interface for programming the SWITCH control register and query of its status information.

sb interface: The sb interface sets the electrical and logical port format of the SWITCH to an ATM-UTOPIA-2 compliant format.  

bb interface: The bb interface is ATM-UTOPIA-1/2 compliant and allows direct Connection of ATM-compliant transmission modules for the physical layer, e.g. B. OC-3 (optical, glass fiber, 155 Mbit / s).  

literature

[1] Futurebus +. IEEE standard 896.1-1991.
[2] ALCATEL NV AMSTERDAM: Switching network and switching network module for an ATM system. US Patent # 5091903.
[3] ANALOG DEVICES: ADSP-2106x SHARC User's Manual, 1st edition, March 1995.
[4] CRAY RESEARCH INC .: Memory interconnect network having separate routing networks for inputs and outputs using switches with FIFO queues and message steering bits. U.S. Patent # 5623698.
[5] FLYNN, MJ: Some Computer Organizations and Their Effectiveness. IEEE Transactions on Computers, 21 (9), 1972.
[6] HWANG, KAI: Advanced Computer Architecture - Parallelism, Scalability, Programmability. McGraw-Hill Series in Computer Science, 1993.
[7] SPARC TECHNOLOGY BUSINESS INC .: STP2230SOP Crossbar Switch (XB1) User's Guide. 1995.
[8] TEXAS INSTRUMENTS INC .: TMS320C4x User's Guide. 1991.
[9] UNIVERSITY OF WASHINGTON: Ultrasound Signal Processing Apparatus. U.S. Patent # 5492125.

Reference list 3 drawings 3.1 List of reference symbols 3.1.1 Reference numerals for FIG. 1

1

processor

2nd

local RAM
CS Cell Switch
FE0 functional unit No. 0
FE1 functional unit No. 1
FE2 functional unit no.2
fs switchgear for connecting the processor bus of the VU with an input and an output port of the cell switch

3.1.2 Reference numerals for FIG. 2

1

processor

2nd

local RAM

3rd

Interface fs

4th

flow control

5

Cell switch

6

CS input port (sending direction)

7

CS output port (receive direction)

8th

Cell clock of the CS

9

Cell ready display

10th

CS receive clock

11

CS send clock

12th

FE receive clock

13

FE transmit clock

14

Cells / octet register / FIFO

15

FE data bus

16

Interrupt signal

17th

Data read request

18th

Data write request

16

Interrupt signal

19th

Functional unit

20th

Send request

3.1.3 Reference numerals for FIG. 3

1

package

2nd

Payload 3rd cell

3rd

3rd cell header

4th

RHeader 3rd cell

3.1.4 Reference symbols for FIG. 4

1

Functional unit

2nd

Header (RHeader)

3rd

local memory

4th

package

5

Payload

6

Cell buffer

7

CS input port

8th

Header / RHeader field

9

Pointer to package

10th

Pointer to header / RHeader field

3.1.5 Reference numerals for FIG. 5

1

Functional unit

2nd

local memory

3rd

SAR unit

4th

package

5

Header (RHeader) register

6

Cell register

7

Input port

8th

Modification register / cell counter

3.1.6 Reference numerals for FIG. 6

1

EPort0

2nd

Eport1

3rd

board

3.1.7 Reference symbols for FIG. 7

1

EPort

2nd

board

3rd

external copper or fiber optic connection

3.1.8 Reference numerals for FIG. 8

1

EPort

2nd

board

3rd

external copper or fiber optic connection

3.1.9 Reference numerals for FIG. 9

1

DSP master unit

2nd

DSP slave unit

3rd

JTAG port

4th

VME port

5

ATM network interface port

Claims (10)

1. A device, hereinafter called a multiprocessor system, consisting of a plurality, at least three, each of a processor, at least one local processor bus, possibly external memory, possibly further peripheral units, functional units and an assigned cell switching unit, characterized in that that

• the cell switching unit enables the transmission of data packets in the form of cells of fixed length from one functional unit to one or one or more other functional units,
• each function unit is assigned its own input and output of the cell switching unit, with dedicated inputs and outputs each being coupled directly to the corresponding local processor bus of the associated function unit,
• a functional unit for sending a data packet can access the cell switching unit directly via the local processor bus,
• the notification of the functional unit addressed as the receiver of a transmitted cell is carried out by the cell switching unit by triggering an interrupt signal,
• the notified functional unit reads the cell addressed to it directly from the cell switching unit via the local processor bus,
• - The functional units and the cell switching unit form a mechanical and electrical unit (build on a common board, common power supply), with the result that all components of the multiprocessor system are galvanically connected to one another,
• - The cell switching unit is self-routing using a routing header preceding the cells or using a header integrated in the cells.

2. Device according to claim 1, characterized in that

• - The multiprocessor system can be operated in two operating modes, in the one of whose cells consist of a header containing address, error protection, operating mode or other operating information and a data field containing user data, in the other cells of which exclusively consist of user data and thus, written directly into the working memory of a functional unit, can serve as the initial operating software for this functional unit.

3. Device according to claim 1, characterized in that

• - between the cell switching unit and one or more functional units, a circuit in one operating mode rejects all octets of a cell flowing from the cell switching unit to the puncture unit, which does not contain useful data, but rather address, error protection, operating mode or other operating information, and only contains the useful data Transfers octets to the functional unit, thus filling part of the memory of the functional unit with initial operating software for the processor, but in another operating mode the address, error protection, operating mode or other operating information together with the useful data remains unchanged passes to the functional unit.

4. The device according to claim 1, characterized in that

• - The segmentation of logical, to be sent data packets of any length in the address space of the processor of the sending functional unit into physical, transmitted by the cell switching unit, fixed length cells, and the reassembly of cells received by the cell switching unit, to logical data packets in the address space of the processor the receiving functional unit, is carried out in the memory of the respective processor by operating software of the processor.

5. The device according to claim 1, characterized in that

• - Between the functional unit and the cell switching unit one or more cells in the receive and / or transmit direction by means of a FIFO memory, which is directly coupled to the local processor bus, temporarily stored for each transmission direction.

6. The device according to claim 5, characterized in that

• - The receive FIFO memory (from the cell switching unit to the functional unit) has greater storage capacity than the transmit FIFO memory (from the functional unit to the cell switching unit).

7. The device according to claim 5, characterized in that

• - The transmit FIFO memory is automatically reset in the event of an overflow or an error state of the receive FIFO memory or the cell switching unit by a notification signal.

8. The device according to claim 1, characterized in that

• - The segmentation of logical, to be sent data packets of any length in the address space of the processor of the sending functional unit in physical, transmitted by the cell switching unit, fixed length cells, and the reassembling of, received by the cell switching unit, cells to logical data packets in the address space of the Processor of the receiving functional unit is carried out by a segmentation and reassembly device located between the processor and the cell switching unit.

9. The device according to claim 1, characterized in that

• - The cell switching unit in addition to the inputs / outputs for each functional unit provides free input / output pairs (external ports), so that two or more devices according to claim 1 can be connected directly by electrical or optical connections.

10. The device according to claim 9, characterized in that

• - The external ports according to claim 9 of two or more multiprocessor systems according to claim 9 with an external cell switching unit, the functioning of which is essentially the same as the cell switching unit on the device, or a network constructed from such cell switching units by interconnection with one another, can be transparently connected to one another.