JPH0619762B2 - Node circuit for network system - Google Patents

Description

TECHNICAL FIELD The present invention relates to a node circuit for a network system.

(Prior Art) A system using multiple computers has been added to a system that has been considered by persons engaged in this technical field since the advent of a highly reliable type of electronic computer (electronic computer). There is a system in which those computers operate in a mutually related manner so that a given task is entirely executed. In some of such multiprocessor systems, one large computer utilizes its own superior speed and capacity to execute complex parts of the program, while performing less complex tasks. For less urgent and less urgent tasks, some have delegated it to a smaller, slower satellite processor, which reduces the burden on this large computer and the amount of requests to this large computer. . In this case, the large computer is responsible for allocating subtasks, keeping the small processors (= satellite processors above) in a working state at all times, and confirming the availability and operating efficiency of these small processors. Must be responsible for achieving the desired results.

Among other types of multiprocessor systems that employ different schemes than those described above, there are systems that use a large number of processors and a common bus system, and the plurality of processors are essentially equal to each other. There are systems that have functions. In such systems, control computers or control systems that are independent of other parts are often used to monitor the availability and throughput of individual processors for a given subtask, and Controlling the transfer path of tasks and information is performed. In addition, there are some in which the configuration and operation of each processor are set so that the processor itself can monitor the status and availability of other processors and determine the transfer route of messages and programs. . A significant drawback common to these various systems is that software is required and operating time is consumed to perform the overhead and maintenance functions, thereby performing the intended purpose. Will be affected. The amount of work involved in determining and monitoring transfer paths increases with a quadratic function of the total number of processors involved in those work, until an unreasonable amount of effort is expended on overhead functions. There is also.

The following several patent publications show examples of the prior art.

Since the early days of Binac (“Binac”: two processors connected in parallel to each other) and various similar systems, the multiprocessor approach already provided redundant execution capabilities. It has been recognized that such provisions can significantly improve the overall reliability of a working system. There have been considerable restrictions so far on actually configuring a multiprocessor system, but those restrictions are mainly due to the enormous amount of software. is there. Nevertheless, multi-processor operation is particularly advantageous in various situations where system downtime cannot be tolerated, such as in real-time applications, etc. Various multiprocessor systems have been developed,
These systems performed well on their own, but due to overhead they had to devote a significant amount of software and operating time. Such conventional systems are described in U.S. Pat. Nos. 3,445,822 and 3,56.
Specific examples are given in No. 6,363 and No. 3,593,300. Each of these patent publications relates to a system in which a plurality of computers access a single main memory shared among them.
In this system, the processing capacity and the processing request amount are compared so that the tasks can be appropriately allocated to the individual processors.

As yet another example of the prior art, U.S. Pat.No. 4,099,
There is number 233. In the system of this publication, a plurality of processors share a single bus, and a control unit containing a buffer register is used to form a data block between a transmitting miniprocessor and a receiving miniprocessor. Is transferred. The concept of this system is used in Europe for decentralized mail classification systems.

U.S. Pat.・
The controller monitors the status of data transmission and determines the priority of a plurality of data transfers between processors. Also, each processor is connectable to control one of a plurality of peripheral devices.

An "Ethernet" system co-promoted by Xerox, Hewlett-Packard, and Intel (US Pat. No. 4,063,220).
And U.S. Pat. No. 4,099,024) present yet another method for dealing with the problem of intercommunication between multiple processors and peripherals. All units (= processors, peripherals, etc.) are connected to a multiple access network shared between them, and they will compete with each other for priority. Collision detection is performed by the time priority method, and for that purpose, controlling the global processing capacity,
Coordinating and understanding clearly
It's not easy.

A thorough analysis of the various systems described above in their details requires a detailed analysis of the patent publications and other related references referred to above. However, when tasks are shared, all of these systems require enormous amounts of mutual communication and management control in order to determine the priority of data transfer and to select a processor. Only will be understood by a brief overview. The problems that occur when a system is expanded to include more processors are different because different systems are different, but none of the above systems Such extensions would complicate system software, applied programming, hardware, or all three. Also, as will be understood by some consideration, due to the fact that one or two logically passive ohmic buses are employed, its inherent constraints are the size and capacity of a multiprocessor system. Is imposed on and. There are various techniques that can be employed to facilitate intercommunication, one example of which is shown in the recently issued U.S. Pat.No. 4,240,143:
There are techniques such as grouping subsystems into global resources, but of course, when a large number of processors are used, the amount of available traffic naturally reaches its limit, and The fact that the delay time takes various values causes a problem that is difficult to overcome. Occasionally, one or more processors may go into a lockout or deadlock situation, and coping with such situations requires additional circuitry and software to solve the problem. Needed. From the above, the number of processors is
Obviously, it has not been practical in the past to greatly expand the number to 1024, for example.

In many different applications, it is desirable to escape from the limitations of the existing techniques described above and utilize the latest techniques as the source of maximum. The lowest cost technique currently available is based on mass-produced microprocessors and large-capacity rotating disk storage devices, and as an example of such storage devices. Is
There are devices made by Winchester Technology, etc., in which the distance between the head and the disk is made very small inside the sealed case. When expanding a multiprocessor system, it is desired that the system can be expanded without unduly complicating the software, and further, the software will not be complicated at the same time. It is even desired to be able to extend it. Still further, there is a need for the ability to handle computer problems with features that have a distributed structure in which the overall functionality can be dynamically subdivided into multiple processing tasks that are either limited or iteratively executed. . Almost all database machines belong to such problem areas, and this problem area further includes sort processing, pattern recognition and correlation calculation processing, digital filtering processing, large matrix calculation processing. , Simulation of physical systems, etc. and other typical examples of problems are also included. In any of these situations, it is required that the tasks to be processed individually should be relatively simple, and the tasks should be widely distributed, resulting in a large instantaneous task load. Will be things. Such situations have added considerable difficulty to traditional multiprocessor systems because they increase the time spent on overhead and the amount of software for overhead. If there is a tendency to cause it, there is a practical obstacle in configuring the system. For example, when a passive shared bus is adopted, the propagation speed and the time required for data transfer form an absolute barrier to the possible processing speed in processing a transaction.

Database machines are thus a good example of where improvements in multiprocessor systems are needed.
Up to now, three types of methods have been proposed as basic methods for constructing a large-scale database machine, which are a hierarchical method, a network method, and a relational method. Among them, the relational database machine allows a user to easily access given data in a complex system by using a table showing relations. Machines are recognized as having strong potential. Representative publications describing this prior art include, for example, page 28 of the March 1979 issue of IEEE Computer Magazine, D.P. C. P. Smith and J. M. Article entitled "Relational Data Base M" by Smith
achine ", published by DCPSmith and jM Smith, i
n the March 1979 issue of IEEE Computer magazine,
p.28), US Pat. No. 4,221,003, and various articles cited therein.

The sorting machine is a computing machine.
It is a good example of the need for architectural improvements. For an overview of sorting machine theory, see D. E.
"Searching and Sorting" by Knuth
Pages 220-246 ("Searching and Sorting" by
DEKnuth, pp.220-246, published (1973) by AddisonWes
ley Publishing Co., Reading, Massachusetts). Various networks and algorithms are disclosed in this document, which must be considered in detail in order to understand the constraints associated with each of them, but the general statement about them is that All of them are characteristically complicated methods aimed only at the specific purpose of sorting. As yet another example, L.S. A. Moller (LAMollaa
r) is presented by
EEE Transaction on Computer ", C
Volume 28, Issue 6 (June 1979), 406-41
Article entitled "A Structure of List-Merging Networks" on page 3 (article entitled "A
Design for a List Merging Network ", in the IEEE Tra
nsactions on Computers, Vol.C-28 No.6, June 1979 at
pp.406-413). In the network proposed in this paper, a method of externally controlling the merge element of the network is adopted, and this network requires programming to perform a special function.

Functions that a general-purpose multiprocessor system must be able to perform include the ability to distribute subtasks in various ways, the status of the processors executing the subtasks, message merging and sorting. Function to perform, function to correct and change data,
It also has the ability to see when and how resources have changed (e.g., when a processor went off-line and returned online). In order to execute the above functions, it has been necessary to use excessive software and hardware for overhead so far.

For example, in a multiprocessor system such as a database machine, when a message transfer route between processors is specified,
One processor is selected as the transfer destination, or multiple processors belonging to one class are selected. Furthermore, instead of specifying the processor itself, the part of the database distributed to the processors by the hash method or the like. It is often necessary to select a destination processor by specifying the. Some known systems utilize pre-communication sequences to establish linkage between the sending processor and one or more specific receiving processors. Requests and acknowledgments must be sent repeatedly to establish this linkage, and additional hardware and software must be used to overcome possible deadlock conditions. . In a system that does not use the pre-communication sequence, control is performed by one processor or by the controller. This control means that the transmitting processor is ready for transmission and the receiving processor receives It is to confirm that it is ready, that the other processors are locked out of the linkage between these processors, and that no extraneous transmissions are taking place. Again, maintenance functions are added as the system expands (eg, 16 processors or more) by relying on overhead and having to be complicated to avoid deadlocks. Will expand to an inappropriate degree.

Yet another example of the requirements of modern multiprocessor systems relates to how the system can reliably determine the status of subtasks being executed by one or more processors. is there. The basic requirement is that a given processor must be capable of inquiring about the status of that processor, and that status is affected by the inquiry. That is, the inquiry must be made so that there is no ambiguity in the content of the response. The term "semaphore" is currently used in the art as a term for characterizing the function of performing a test and a set of status indications as an uninterrupted series of operations. It is desirable to have this semaphore feature, but when incorporating this feature, it must be done without lowering execution efficiency or increasing overhead load. Such status determination is extremely important when performing sort / merge operations in a multiprocessor system, but it is the result of each processing of multiple subtasks included in a large task. This is because the subtasks cannot be combined into one until the subtasks have been properly processed. As yet another requirement, the processor must be able to report its "current" status, and the execution of subtasks is done only once, even if interrupts and changes are repeated to the operating sequence of the multiprocessor. There are some things that must be done.
In most existing systems, the execution routines of the processor can be interrupted, which presents a significant problem in this regard. That is, as will be easily understood, when a plurality of processors are executing a plurality of subtasks that are related to each other, the degree of readiness state of each of those processors (= what kind of operation The operational sequence involved in querying and responding to requests for a large amount of overhead may require enormous overhead, and the dedicated overhead for doing so may increase as the number of processors increases. It finally increases to an inappropriate level.

(Problems to be Solved by the Invention) A conventional multiprocessor that shows the above-mentioned examples
A typical disadvantage of the system relates to the so-called "distributed update" problem, which means that each of the multiple processing units needs to update the information whose copy is stored. is there. The information referred to here may be information consisting of data records,
It may also be information used to control the operation of the system. Controlling the operation of this system means, for example, that the necessary steps are not accidentally executed in duplicate or not executed at all, and the processing is started, stopped, restarted, suspended, or It is control such as roll back or roll forward. In conventional systems, the various solutions to the distributed update problem have all come with considerable constraints. Some of those solutions are
Some only target two processors at a time. There are still some other solutions that use intercommunication protocols, but they are so complex that they still have a mathematical rigor. Proving with is very difficult.

The reason for the complexity of these protocols is that they make up the "global semaphore", uninterrupted1.
It is necessary to provide control bits that have the external property of being "tested and set" in all processors by a single operation. Since such control bits are provided inside each of a plurality of separate processors, and the delay times associated with the communication between the processors are different, noise is inevitably caused by a communication channel which can inevitably be incomplete. Is generated, and the error rate is further increased. Therefore, the provision of the feature of "one operation without interruption" means that each of the plurality of parts constituting the operation is diverse and interruptible, and Can be accessed at the same time, and if they are prone to inconveniences between accesses, it is difficult.
Those skilled in the art will readily understand.

SUMMARY OF THE INVENTION In summary, the present invention is a node in a bidirectional network, comprising a branch circuit having one upstream port and two downstream ports, the ports of which are: Are all bidirectional and each of them contains parallel data lines and collision lines,
Further, logic is included to give a priority to an upstream message and to send a signal indicating that the priority is given to another location to the collision line that cannot obtain the priority. The node that is being provided is provided.

Embodiment An embodiment of the present invention will be described below with reference to the drawings.

(Database Management System) The system generally shown in FIG. 1 is an example in which the concept of the present invention is applied to database management. More specifically, this system comprises one or more host computer systems 1
0, 12 and their host computer system is, for example, an IBM 370.
A computer system or the like belonging to the family or the DEC-PDP-11 family, which operates on an existing general operating system and application software so as to meet the purpose of this example. According to the IBM terminology, a host computer
The main interconnection network between a computer and a database computer is called a channel, and the same is DEC.
According to the terminology of, it is called "unibus" or "mass bass" or a term slightly modified from those terms. Whether any of the above computer systems are used or mainframe computers from other manufacturers are used, this channel, or bus, is where the database tasks and subtasks are dispatched. Is an ohmic transfer path, that is, a logically passive transfer path.

The embodiment of FIG. 1 shows a backend processor complex associated with a host system 10,12. The system in this figure accepts tasks and subtasks from the host system, looks up the appropriate portion of the vast database storage information, and returns the appropriate processed or reply messages, and their actions. Irrespective of the configuration of this back-end processor complex, it is executed in a manner not required by the host system, except for less sophisticated software management. Therefore, it is possible to configure the user's database as a new type of multiprocessor system, and in this multiprocessor system, the data can be stored in a relational database file that can greatly expand the capacity. This extension can be done without the need to modify the operating system or existing application software contained within the user's host system. A specific example configured as an independent system (stand-alone system) will be described below with reference to FIG.

As will be appreciated by those skilled in the art, operational functions related to relational database management may divide an entire operational function into processing tasks that can be processed, at least temporarily, independently of the other. It is an operation function that can be performed. The reason is that in relational databases the stored data entries are not interdependently linked by address pointers. Further, as will be appreciated by those skilled in the art, other than relational database management, a method of dynamically subdividing a limited task or a repetitively executed task may be used. Many data processing environments exist. Therefore, in describing the embodiments of the present invention, the description will be made in connection with the processing problem in database management, which is particularly strongly requested and frequently asked, however, the novel method and the method disclosed in the present specification will be described. The configuration has a wide range of other uses.

Large-scale data management systems will have both the potential advantages and the attendant difficulties of using multiple processors. An enormous number of entries (descriptions) of hundreds of millions
It must be kept in storage for easy and quick access. On the other hand, the format of a relational database allows a wide range of data entry and information retrieval operations to be executed concurrently.

However, in the overwhelming majority of database systems, maintaining database integrity is as important as rapidly processing transaction data. Data integrity is
It must be maintained before and after hardware failures, power outages, and other disasters related to system operation. Furthermore, the database system
It must have the ability to restore the database to a previously known state in order to clean up user errors, including bugs in the application software code. Moreover, the data must not be accidentally lost or entered, and whether the event is related to new data or correction of past errors, Depending on whether it is related to the calibration of a part of the database, all of the part of the database related to a particular entry must be modified.

Therefore, for completeness, in addition to the operations of data rollback and recovery, the detection and correction of errors, and the detection and compensation of changes in the status of individual parts of the system, and to a certain extent The redundancy of is also necessary for the database system. To achieve these ends, it is possible that the system must be used in many different specialized modes.

Moreover, modern systems have discretionary queries whose format tends to be complex.
It is required to have the ability to accept and, if necessary, respond in an interactive manner. Even if the query is complex, it should not be required that the people trying to access the system be skilled in the system.

Examples of arbitrary queries that may occur in connection with large-scale production operations include:

A. The manager who manages production not only requests a list for one of the in-stock items, but also exceeds the monthly production of parts whose production has decreased by at least 10% compared to the same month of the previous year. You may request an inventory list that clearly lists all parts in stock.

B. Marketing managers not only inquire whether a particular account is 90 days past due, but evenly for customers who have been in the recession for more than 120 days in the past. May request a day receivable.

C. Not only does the HR executive require that all employees who have been sick for more than two weeks in a given year be listed, but for more than two of the last five years,
You may want to list all long-term employees who have been sick for more than a week during the fishing season, for more than 10 years.

In each of the above examples, the user seeks to determine the real problem faced in the business by associating the information stored on the computer in ways not previously possible. A database system capable of handling complex queries by an untrained computer expert, provided that the user has experience in the field causing the problem, and therefore has intuition and imagination. Can be used freely.

Modern multiprocessor systems seek to address these many, and often conflicting, requirements by using carefully crafted overhead and maintenance software systems. I'm trying,
Those software systems are inherently a hindrance to easy system expansion. However, the concept of extensibility is strongly demanded because, as the business or business grows, it is desirable to expand the existing database management system and continue to use it. In this case, we would not like to be forced to adopt new systems and software.

Multiprocessor Array Referring to FIG. 1, a message of one exemplary embodiment of the present invention includes a large number of microprocessors, of which there are two important types that are important. Are referred to herein as an interface processor (IFP) and an access module processor (AMP), respectively. Two IFPs 14 and 16 are shown in the figure, each of which is connected to the input / output device of another host computer 10-12. Multiple access modules
Processors 18-23 are also multiprocessors
It is included in what should be called an array. The term "array" is used herein to refer to a set of processors arranged in a generally linear or matrix arrangement.
It is used in a general sense to refer to a unit, an aggregated processor unit, or a plurality of processor units, and is therefore more recently an "array processor".
It does not mean what has come to be called. Although only eight microprocessors are shown in the figure to show a simplified example of the concept of this system,
Much more IFPs and AMPs can and will normally be used.

The IFPs 14, 16 and AMPs 18-23 have an Intel 8086 that has an internal bus and a main memory for direct memory access to the peripheral controller.
Built-in 16-bit microprocessor. Any of a wide variety of microprocessors and microprocessor system products from various manufacturers can be utilized. This "microprocessor" is only one specific example of one type of computer or processor that can be used in this array because the concept of this system is that the computing power required by the application is a minicomputer or If it is a large computer, it can be used successfully with them. This 16-bit microprocessor has considerable data processing power, yet is in a standard replaceable configuration that can replace a wide variety of available hardware and software options, low cost. Is an advantageous example of the device.

The IFP and AMP employ circuits similar to each other, including active logic, control logic, and interface, a microprocessor, a memory, and an internal bus, which are respectively referred to FIGS. 1 and 8. While explaining later. However, the two processor types differ in the nature of the peripheral devices associated with each processor type and the control logic for those peripheral devices.
As will be readily appreciated by those skilled in the art, other processor types with different peripheral controllers and different functional tasks may be readily incorporated into the present invention.

Each microprocessor is provided with a high speed random access memory 26 (described in connection with FIG. 8) which, in addition to providing buffering of input and output messages, It manages messages by collaborating with other parts of the system in unique ways. Briefly, this fast random access memory 26 acts as a circular buffer for variable length input messages (referred to as "receive" for this input) and for sequential message output (this output Function as memory), incorporates table index portions for use in hash mapping mode and other modes, and stores control information to handle incoming and outgoing messages in an orderly manner. To do. The memory 26 is further used to play a unique role in multiprocessor mode selection and in handling traffic of data, status, control, and response messages. As will be explained in more detail below, these memories also allow local and global status determination and control functions to be processed and communicated in a highly efficient manner based on the transaction identity in the message. It has been configured. IFP14, 16 and AMP1
The control logic 28 provided in each of 8 to 23 (described later in connection with FIG. 13) is used for data transfer and execution of an overhead function in the module.

The IFPs 14 and 16 are respectively interface control circuits 30.
And the interface control circuit 30 has an I
The FP is connected to the channels or buses of the host computers 10-12 associated with that IFP. On the other hand, in the AMPs 18 to 23, the device corresponding to the interface control circuit is the disk controller 32, and the disk controller 32 may have a general structure.
To interface with the respective magnetic disk drives 38-43 individually associated therewith.

The magnetic disk drives 38 to 43 provide a secondary storage device, that is, a mass storage device, to the database management system. In the present embodiment, those magnetic disk drives shall be composed of proven commercial products such as Winchester technology, so that the cost per byte is extremely low, and the capacity and reliability are high. The storage device is available.

A relational database is stored in the disk drives 38 to 43 in a distributed storage system, which is shown in a simplified form in FIG. Each processor and its associated disk drive is assigned a plurality of records that form a subset of the database, which subset is a "primary" subset and those primary subsets. Is a disjoint subset and constitutes a complete database as a whole. Therefore, each of the n storage devices holds 1 / n of the database. Each processor is further assigned a subset of backup data, which backup subsets are also disjoint subsets, each constituting 1 / n of this database. As can be seen from FIG. 22, each of the primary files is duplicated by a backup file contained in a processor different from the processor containing the primary file, which makes them different from each other. A complete database is obtained for each of the two distributed in a distributed manner.
In this way, the integrity of the database is protected by the redundancy of the primary data subset and the backup data subset, and the reason is that a single failure occurs. If so, it is impossible to have a substantial effect on a plurality of data in a large number of blocks and a plurality of relations forming a plurality of groups.

The distribution of the database has implications for the hashing behavior of the various files, also shown in Figure 22, and also for embedding the hash mapping data in the message. ing. The files contained on each processor are simple hash buckets (hash b), which are represented as groups of binary sequences.
ucket). Therefore, based on the relational table specified by those buckets, the relational database
Relations and Tables in the system
The place where the tuple) should be placed can be determined. The hashing algorithm is used to request bucket allocation from the key inside the relay database system, and therefore the database system can be easily expanded and modified.

The size of the storage capacity to be selected depends on the database management needs, the amount of transactions, and the processing power of the microprocessor associated with the storage device. It is possible to connect multiple disk drives to one AMP, or one disk file device to multiple AMPs, but such modifications are usually limited to special applications. Ah The database expansion is typically done by expanding the number of processors (and the number of disk drives associated with the processors) in a multiprocessor array.

Active Logic Networks The purpose of providing an orderly flow of message packets and facilitating the performance of tasks is to provide a unique system architecture centered around a new active logic network construct 50. It is achieved by adopting a message structure. The active logic network structure 50 has a plurality of bidirectional active logic nodes (i.e., an ascending hierarchy) in which outputs of a plurality of microprocessors are converged while climbing the hierarchy. logic
node) 54. The nodes 54 consist of a bidirectional circuit with three ports, which is a tree network.
network: a network with a dendritic structure), in which case the microprocessors 14, 16 and 18 in the base part of the tree structure
~ 23 connected.

As will be appreciated by those skilled in the art, a node can be provided when the number of logic sources is greater than 2, eg 4 or 8, while at the same time also increasing the number of source inputs. This problem can also be converted to the problem of adding combination logic.

For ease of reference in the figure, of all the nodes (N), those belonging to the first layer are represented by the prefix "I", and those belonging to the second layer are prefixed with it. Expressed as "II", and so on. Individual nodes belonging to the same hierarchy are represented by subscripts " ₁ , ₂
... ", and therefore, for example, the fourth node of the first hierarchy can be expressed as" IN ₄ ". One port named "C port" is provided on the up tree side (that is, the upstream side) of the node, and two down tree nodes of nodes belonging to a higher hierarchy adjacent to this C port are provided. Connected to one of the ports,
The down tree ports are named "A Port" and "B Port" respectively. The plurality of layers converge to the top node, that is, the vertex node 54a, and the vertex node 54a reverses the direction of the flow of the message (up tree message) directed to the upstream, and the downstream direction ( It functions as a means for convergence and turning in the down tree direction). Two sets of tree networks 50a, 50b are used, with the nodes in the two sets of networks and their interconnections placed in parallel with each other, thereby providing the redundancy desired for large systems. ing.
Since nodes 54 and their networks are identical to each other, it is sufficient to describe only one of those networks.

For the sake of clarity, the first thing to understand is that a large number of message packets, which are in the form of serial signal trains, are connected to the active logic network 50 by a large number of microprocessor connections. That is, it is possible to simultaneously send the data to, or to send at the same time. Each of the plurality of active logic nodes 54 operates on a binary basis to make a priority decision between two conflicting message packets in a conflicting relationship with each other, the priority decision being made to those message packets. This is done using the data content of itself. Furthermore, all nodes 54 in a network are under the control of one clock source 56, which synchronizes the sequence of message packets towards vertex node 54a. Are combined with those nodes 54 in such a way that they can proceed. In this way, in the serial signal train,
Incremental segments, such as each successive byte, are advanced to the next level, with the progression of this byte being the byte corresponding to that byte in another message.
This is done at the same time as another route is followed in the same way.

Sorting to give priority among competing signal sequences is performed on the message packets moving in the up tree direction, which ultimately leads to
A single message sequence is selected to be redirected downstream from vertex node 54a. Since the system is configured as described above, it is not necessary to make a final priority determination at one specific point in the message packet. The transfer of messages can be continued without the need for anything other than a binary-based decision between two collision packets. As a result, the system is spatially and temporally capable of message selection and data transfer, provided that it takes control of the bus and identifies the sending or receiving processor. There is no delay in message transmission for the purpose of performing handshaking operations between processors.

Furthermore, it is important to note that if several processors send the exact same bucket at the same time, and if they succeed, then all of their sending processors succeed. That is the case. This property saves time and overhead and is extremely useful for effective control of large multiprocessor complexes.

The node 54 also operates in a bidirectional manner, allowing undisturbed downstream distribution of message packets. At a given node 54, downstream messages received at port C on the up tree side are distributed to both port A and port B on the down tree side of this node,
Further, it is transferred to both of the two adjacent nodes belonging to the lower hierarchy connected to this node. Under the control of the common clock circuit 56, the message packet is synchronously advanced down the tree and is simultaneously broadcast to all microprocessors, thereby allowing one or more of them to be broadcast. Allows the processor to perform desired processing tasks or accept responses.

The data transfer rate of the network 50 is higher than the data transfer rate of the microprocessor, and is typically twice as high as or higher than the data transfer rate of the microprocessor. In this embodiment, the network 50 has a 120 nanosecond byte clock interval and its data transfer rate is five times that of a microprocessor. Each node 54 has its three ports each connected to a port of a node belonging to an adjacent hierarchy connected to that node, or to a microprocessor, which is connected to a set of data lines (books). In the example, 10
Main line) and control lines (two lines in this embodiment), and the two control lines are assigned to the clock signal and the collision signal (collision signal), respectively. The data line and the clock line are wired so as to form a pair, and are set as separate lines in the up tree direction and the down tree direction. collision·
The line propagates only in the down tree direction. The above connection structure forms a full-duplex data path, and the drive direction is "inverted" for any line.
It doesn't require a delay to do so.

Referring now to FIG. 3, the ten data lines include an 8-bit byte represented by bits 0-7, which represent eight of the ten data lines. is occupying. Another line, represented by C, is the control line, which carries the control sequence used to identify different parts of the message packet in a particular way. The tenth bit is used for odd parity in this embodiment. As will be appreciated by those skilled in the art, the system may increase or decrease the number of bits in the data path above and may easily operate with such changes in the number of bits.

A byte sequence (a sequence of bytes) is arranged into a series of fields, basically divided into a command field, a key field, a destination selection field, and a data field. . As will be explained in more detail below, the message may use only one field and is terminated with a detectable "end of message" code. The "idle field" between the messages is C
Represented by an uninterrupted sequence of "1's" on lines as well as lines 0-7, they are being forwarded whenever no message packet is available. The parity line is also used to convey changes in the status of individual processors in a unique way.

An "idle state" is an intervening state between messages and is not part of a message packet. Message packets usually start with a 2-byte command word containing a tag, which is in the form of a transaction number (TN) if the message is a data message, and the message is a response. If it is a message, it is in the form of a source processor ID (OPID). Transaction numbers have different levels of significance in the system and serve as the basis for many types of functional communication and control. The packet may include a variable length key field and / or a fixed length destination selection word (DSW) after the command word, which may be variable length data. -It forms the beginning of the field. The key field serves the purpose of providing a criterion for sorting between messages when the messages are otherwise identical to each other in other parts of the key field. DSW
Provides the basis for a number of special features, and deserves special attention in conjunction with TN.

The system is designed to operate with a word-synchronized interface so that all processors attempting to send packets will
Network the first bytes of a word simultaneously with each other
It is designed to be sent to. The network uses the data content of the fields that follow it to sort on a binary basis at each node, with this sorting being done in such a way that the smallest numerical value is given priority. If bit C is considered to be the largest quantity and bit 0 is considered to be the smallest quantity among the consecutive data bits, the sorting priority is as follows.

1. First sent to the network 50, 2. A command code (command word) having a minimum value. 3. The key field has the minimum value. The shortest key field, 5. 5. The data field (including the transfer destination selection word) has the minimum value; The shortest data field.

In view of the purpose of giving an overview here, it should be noted that if the node 54 determines the priority, a collision display (= collision display, hereinafter referred to as Acol or Bcol) is given. Is sent back to the route that received the transmission of the one who was defeated in this priority determination. By this collision display,
The transmitting microprocessor is aware that the network 50 has been aborted because it is being used for higher priority transmissions and therefore will have to try again later. You can

A simplified embodiment is shown in various schemes in FIG. In this embodiment, the network 50 is operated in cooperation with a high speed random access memory arranged in a tree structure using four separate microprocessors. In more detail, IFP14 and three AMP1
8, 19 and 20. Subfigure 2A, 2
Each of B, ... 2J corresponds to one of 10 consecutive time samples from t = 0 to t = 9,
And at each of those times, a different simplified (4 letter) serial number sent by each of the microprocessors in this network.
It shows aspects of message distribution and the state of communication between the port and the microprocessor at their various times. The drawing, which is merely labeled as FIG. 2, shows the state of the system before the start of the transmission of signals. In each of the above figures, the null state (null stat
e: Zero state) In other words, to be in the idle state,
It is assumed that the transmission represented by "□" must be performed. The message packet "EDDV" sent from the AMP 19 in FIG. 2A is the first message packet transmitted through this system because of the agreement that the data content taking the minimum value has priority. Each message in the figure is held within a high speed random access memory (sometimes referred to as H.S.RAM) in a microprocessor, as described in more detail below. H. S. RAM2
6 has an input area and an output area which are schematically shown in FIG. 2, and the packet has a FIFO (first-in first-out) in this output area at the time of t = 0. They are arranged vertically side by side according to the H.264 system, so that the H.264 in the figure is used for transfer. S. It can be taken out as instructed by the cursor arrow written in the RAM 26. At this point, all transmissions in network 50 exhibit a null or idle state (□).

On the other hand, at the time of t = 1 shown in FIG. 2B, the leading bytes of the respective message packets are simultaneously transmitted to the network 50, and at this time, all the nodes 54 still display the idle state indication. In addition, all transfer states above the first layer are also in the idle state. During the first clock interval, the first byte of each message is set inside the lowest layer nodes IN ₁ and IN ₂ , and at t = 2 (FIG. 2C) the conflict is settled, and Both upstream transmission and downstream transmission are performed successively. Node IN ₁ has received an "E" on both of its input ports and is forwarding it upstream to the next layer, and downstream to both sending processors undecided. The status is displayed. However, the node IN ₂ that belongs to the same hierarchy as this determines the priority of “E” when the collision occurs between “E” from the processor 19 and “P” from the processor 20. And port B to port C on the up tree side while returning a Bcol signal to microprocessor 20. When the Bcol signal is returned to the microprocessor 20, the IN ₂ node is effectively
The A input port is locked to the C output port, so that the serial signal train from the microprocessor 19 is transmitted to the vertex node IIN1.

In the IN ₁ node, the first two characters are both “ED”, so that it is impossible to make a decision at time t = 2 in this node, as shown in FIG. 2C. . Furthermore, three microprocessors 1
The common leading letter "E" sent from 4, 15 and 19 reaches the IIN1 vertex node at time t = 3 (Fig. 2D), and this letter "E" is also present in all those messages. When the common second letter "D" is transferred to this vertex node IIN1, the direction of the transfer is reversed and directed to the downstream direction. At this point, the node IN ₁ is still in a state where it cannot make a decision. However, at this time, a series of microprocessors 14, 18
And the respective third letter "F", "E" and "D" from 19 is being sent to this node IN ₁ . The fact that the microprocessor 20 receives the Bcol signal means that this processor 20 has been defeated in the race for priority and therefore this processor 2
When 0 receives the Bcol signal, it sends an idle indication (□), and thereafter sends only this idle (□). The respective cursor arrows written in their respective output buffers indicate that the microprocessor 20 has been returned to its initial state while the other microprocessors continue to send a continuous series of characters. Therefore t
= 4 (Fig. 2E), the important event is that the determination regarding the port of the node IN ₁ is made, and that the leading character ("E") is passed through all the lines in the first layer. It is to be inverted and transmitted toward the node hierarchy. At the time of t = 5 (FIG. 2F), the second collision is displayed, and in this case, the B port of the node IIN ₁ wins the competition and Acol is generated.

During the following several clock times, the downstream broadcast of the serial signal train is intermittently performed, and t
= 6 (Fig. 2G), the first character of the message is the H. S. It is set in the input area of the RAM 26. Another point to note here is that the priority determination made earlier in the node IN ₁ is invalidated at this point, because the processor 18 sends it. When the third character ("E") loses the contention with the third character ("D") sent from the microprocessor 19, one Acol is displayed from the node IIN1 of the higher hierarchy. Is done. As indicated by the cursor arrows in FIG. 2H, the microprocessors 14, 1
8 and 20 have been returned to their initial state, and
The winning microprocessor 19 has already completed all its transmissions at time t = 4. 2H, 2I
As can be seen from the figure and FIG. 2J, priority messages “EDDV” are loaded one after another into all the input buffers. At t = 8 (FIG. 2I), this message has already flowed out of the first hierarchy, and the vertex node IIN ₁ is already reset at t = 7, but it is This is because only the idle signals are already competing with each other when the last downstream character is transferred towards. t = 9
At the time of (Fig. 2J), the nodes IN ₁ and IN ₂ belonging to the first hierarchy are reset, and all the defeated microprocessors 14, 18 and 20 are
Sending the first character of the message when the network again indicates idle will cause the race to regain priority on the network. In fact, as will be explained later, an acknowledgment signal is transmitted to the winning microprocessor, but this is not essential for the most generalization of the invention.

After the message has been broadcast to all microprocessors in this way, this message is utilized by either or all of those microprocessors as needed. How many microprocessors are used depends on the operation mode and the function to be executed, and there are various variations in the operation modes and functions.

(Global Intercommunication and Control) The specific example described above as a method of giving priority to one message of a group of mutually competing messages is related to the transfer of a primary data message. is there. However, complex multiprocessor systems need to utilize many other types of communications and commands in order to provide the good efficiencies and versatility required today. The main functions that must be provided include, in addition to the transfer of primary data, what can be broadly referred to as a multiprocessor mode, acknowledgment of messages, status indication, and control signals. There is. The following chapters discuss how different modes and messages cooperate with a sorting communication network for sorting and communication for prioritization, from a global perspective, namely multiprocessor It presents the overview described from a system perspective. For a more detailed understanding, please refer to FIGS. 8 and 13 and the following description of those figures.

In the broadcast or broadcast mode, the message is delivered to all processors simultaneously, without explicitly identifying the particular receiving processor or processors. This mode is used for replies, status inquiries, commands, and control functions, to give a typical example.

If the receiving processor needs to be specified,
The destination selection information contained within the message packet itself now provides the criteria for locally (= in individual processors) accepting or rejecting the packet. There is. By way of example, the interface logic within the receiving processor module may be configured so that according to the map information stored in the high speed RAM 26, the data for that packet is within the range involved by the particular processor in which the interface lodge is incorporated. Identify whether it is included.
The criteria for the various selection schemes can be easily set by variously setting the map bits in the high speed RAM, such as, for example, selecting a particular receiving processor, ("hashing"). There is a selection of a portion of the stored database, a selection of logical process types ("classes"), and so on. The use of broadcasting with local access control (= access control performed on individual processors) is especially beneficial for database management systems, which require widely distributed, low overhead software. Access to any portion of a relational database or distributed local copy of any of a plurality of globally known logical processes. Therefore, this system can specify and select one transfer destination processor as a transfer destination of a message, and can also specify and select a plurality of resources belonging to one class.

Furthermore, high-level database queries often require cross-references between different parts of the database and consistent references for a given task. The transaction number (TN) embedded in the message has various qualities, among other things, it provides the identity and reference of such a global transaction. A large number of tasks can be concurrently processed by local processor modules (local processor modules) that operate asynchronously with each other, and each task or subtask can be processed by an appropriate TN. Is to have. By using various combinations of TN, DSW (transfer destination selection word) and commands, virtually unlimited flexibility is achieved. Extensive sort / merge operations (sort / merge) for a large number of tasks whose allocation and processing are done asynchronously.
operation) can be applied. For TN, it is possible to allocate and abandon it, and for merge operation,
It can be started and stopped. Certain messages, such as continuation messages, may have priority over the transmission of other messages. By utilizing a TN and a local processor that updates the status for that TN, it is possible to determine the status of the global resource for a given TN with only one query. Distributed updates can also be accomplished with a single communication. The system of the present invention enables all of the above functions to be executed without expanding the software or significantly increasing the overhead burden.

The use of the present invention, as a result, makes a multiprocessor system with a much higher number of microprocessors than is normally found in the prior art operate very effectively for problem tasks. Will be possible. Nowadays, microprocessors are low-priced, so a system that has high performance in the problem domain can be simply "low" power ("raw" po
wer) is not only a high-performance system,
Can be realized.

A consistent priority protocol covering all message types and various subtypes is defined to cover all of the various messages supplied to the network. Reply messages, status messages, and control messages are different types of messages from the primary data messages, but they too have network conflict / merge behavior (c
ontention / merge operation) and thereby receive priority while being transferred. The response message in this system is an acknowledgment (ACK)
Or a negative acknowledgment (NAK), or an indication that the processor does not have the resources to do meaningful processing for the message ("not applicable processor" -NAP). is there. N
The AK response may be of any of several different types indicating a lock condition, an error condition, or an overrun condition. There may be only one source processor or multiple source processors,
Since the originating processor needs such a response after it finishes sending the message, the response message is given a higher priority than the primary data message.

The system also uses a SACK message (status acknowledgment message), which is the readiness state of a local processor for a particular task or transaction. It shows the readiness state. The content of this SACK response is local (= in individual processor, ie in local processor)
It is updated and kept accessible from the network. Such a SACK response is combined with a network merge operation to provide a single query global status report for a given task or transaction. Since the status response follows the priority protocol, the response with the least data content among the responses related to one transaction number automatically gets the priority, whereby the lowest readiness state is the global system state. , And this is done in a single, uninterrupted operation. Furthermore, such SA
The CK indication may also be used with some sort of primary message, which sets various protocols, such as system initialization and lockout operations.

The priority protocol for the various message types is first defined for a command code, which is the command word that precedes each message and response as shown in FIG.
It uses the first 6 bits. This allows for sufficient distinction between message types and subtypes, but it is also possible to have more levels of distinction. As can be seen from FIG. 11, SACK is used in this embodiment.
The response is said to be representative of seven different status levels (and also provide criteria for priority determination). In case of response message, above 6
The bit is followed by a tab in the form of a 10-bit OPID (see Figure 3). Both TN and OPID can serve as further criteria for sorting, because these TN and OPID have different data contents inside the tag area.

After each primary message has been transmitted over the network, the interface part of all processors, regardless of whether it is a NAP, will generate a reply message anyway. The reply messages also compete with each other on the network, thereby broadcasting a single or common winning reply message to all processors. Lost message packets will later be attempted to be retransmitted at the same time, but this retransmitted transmission will occur after a very short delay, thereby ensuring that the network is in continuous use. . If multiple processors send ACK responses, those ACK responses will be sorted based on the OPID.

With the invention, the result is that tasks can be started, stopped, suppressed, and queried for tasks by a very large number of physical processors with little overhead. This allows the raw power of a large number of processors to be used effectively for handling problem conditions, because of this low power system coordination and control. This is because the amount that is split into is extremely small. Coordination and control overheads are a fundamental constraint on the efficiency of any distributed processing system.

Various types of control communication are used for the purpose of global control (that is, control of the network).
Therefore, the "merge stop", "status request", and "merge start" messages, the message for allocating a task, and the message for abandoning a task have the same format as the data message. Therefore, those messages will also be referred to herein as primary messages. Those control messages also include the TN and are positioned at appropriate places in the priority protocol. This will be explained later with reference to FIGS. 10 and 11.

The term "global semaphore buffer system" was used earlier because the high speed random access memory 26 and control logic 28 shown in FIG. This is due to the fact that it plays an important role both in the two-way communication of instructions. The global semaphore buffer system provides access duality, which means that both the fast-running network structure 50 and the slower-running microprocessor have memory 26. The messages, replies, controls, or status indications within can be referenced without delay and without the need for direct communication between the network and the microprocessor. To accomplish this, control logic 28 plugs memory 26 into a word
It is connected to the network 50 and the microprocessor in a time-multiplexed manner in a cycle (interleaved woed cycle), and as a result, the memory 26 and the different ports that can be commonly accessed Is supposed to be created. The global resource, network 50 and the multiple microprocessors, utilize the transaction number as an address locator that locates to the portion of memory 26 that is allocated to store the status of the transaction. can do. At the local level (= individual processor level),
The status of subtasks for a given transaction, including any kind of available state, is updated inside the memory 26 under the control of the microprocessor and locked by the control logic 28 into the buffer system. . By using one of seven different ready states, entries can be conveniently retrieved from different dedicated portions of memory 26. When an inquiry is received from the network, the status of the processor is communicated (ie the "semaphore" is read) and a priority decision is made in the network, with a degree of completion. The lowest readiness state has gained priority. With the above configuration, a quick hardware response from one of the processors to one inquiry can be obtained. Therefore, it is possible to know whether all of the distributed sub-tasks regarding a given task have been completed, without delay and without using software. In addition, in this system, any of the communicating processor modules can assign a transaction number, and this transaction number assignment uses the available transaction number for the message. Or each global semaphore
An operation that is allocated for use within the buffer system.

The preferred embodiment of the combined use of transaction identity and status indication is that each of a plurality of processors sends out all messages related to a given criterion in order. Is required, there is a complex merge operation.
In the case of the prior art system, each processor first receives its task and completes its processing, after which the result of that processing is a kind of "master" that performs the final merge operation. It would have to take the form of transfer to the processor. Therefore, the master processor is a significant bottleneck to the efficiency of the system.

If the global readiness state establishes that all of the affected processors are in a ready state, the messages with the highest priority in the memory 26 provided in each processor will be sent to the network simultaneously with each other. The messages are then prioritized during the merge as described above. Successive attempts to retransmit several groups of messages will result in multiple messages being ordered from highest priority to lowest with respect to the transaction number, with the lowest priority at the end. A serial message string is generated, with objects coming in. According to a special command message, this system allows the merge operation to be stopped midway and restarted midway, so that multiple merge operations that are in the middle of execution at the same time can be executed. There is a possibility that the network 50 is shared, which makes it possible to use the resources of the system extremely effectively.

Therefore, at any time, this network 5
All of the active processors connected to 0 are capable of performing operations on multiple messages associated with different transaction numbers asynchronously to each other. If the same transaction number or "current" transaction number is referenced by one status query, all processors respond synchronously to each other with one of the available status levels. . For example,
The "START MEBRGE" message causes a test (= investigation) of the global semaphore specified by a particular transaction number, and if the global state resulting from this test is "ready". If it is in a state (that is, in either "SEND READY" or "RECEIVE READY"), the current transaction number (present transa)
ction number (PTN) is set equal to the value of TN transmitted in the "merge start" message. (If the test result shows that the global state is not "ready", the value of PTN is "TN0
(This means that the transaction number (TN) is "0") ".

Furthermore, the "STOP MERGE" message also resets the current transaction number to "0".
In this way, "TN0" is a message from one processor to another processor (point.
It is used as the "default" value transaction number used for two-point messages). In other words, this "TN0" specifies the operation of the "non-merge" mode.

This global intercommunication system is shown in FIGS. 3A, 3B, 3C, and 11 for the structure of the message and FIG. 8 for the structure of the high speed random access memory 26. And the one shown in FIG. 10 is adopted. A more detailed description will be given later in Section 5,
This will be done in connection with FIGS. 7, 9, and 13.

As can be seen from FIGS. 3A to 3C and FIG. 11, the command code used for the response is 00 to OF (hexadecimal number).
And the command codes used for the primary message range from 10 (hex) to higher values. Therefore, the response has priority over the primary message, and the smallest value comes first in the arrangement order shown in FIG.

One dedicated storage area (“Transaction number” in the figure) inside the high-speed RAM memory 26 ″ (FIG. 8)
12) is used to store the word format of FIG. 12 (7 types of readiness state, TN assigned state, and TN unassigned state described above). Among other dedicated parts of this memory 26 "are circular buffers for input (received messages) and storage space for output messages. Another separate part of this memory 26" The separation area is used as a message completion vector area, and this area enables the pointer to be placed in the output message that has been sent, so that the storage space of the output message can be effectively used. It has become.

As will be appreciated, for memory 26 and control logic 28, their queuing and data buffering functions are certainly important, but with them, global transactions are not Multiple co-operation, which is distributed and processing with respect to the processor, has a unique importance.

(Active Logic Node) In each of the two networks arranged with redundancy, the plurality of active logic nodes 54 of FIG. 1 are configured to be the same as each other, with the exception of Only the direction reversal node 54 at the top of each network does not have an upstream port, instead:
A simple signal direction reversal path for reversing the direction downstream is provided. As shown in FIG. 4, one node 54
Can be roughly divided into two groups based on function. One of these functional groups relates to the transmission of messages and collision signals (collision numbers) and the other to the generation and retransmission of common clock signals. The clock signals are synchronized such that there is no skew between the clock signals at the different nodes, ie zero skew. The above two functional groups are not independent of each other, because
This is because the skew clock circuit forms an important part of the signal transmission system. Both the word clock (consisting of two serial bytes) and the byte clock are used. It should be particularly noted here that when setting or resetting the state of this active logic node 54 and also when setting different operating modes.
No external control of this active logic node 54 is required, and no such control is actually performed. Moreover, since each node 54 has the same structure as each other, it is possible to mass-produce those nodes using modern IC technology, which improves reliability and at a considerable cost. Can be realized.

Each of the "ports" of A, B and C referred to above each comprises 10 input data lines and 10 output data lines. For example, in the A port, the input line is represented by AI and the output line is represented by A0. One "collision" line (or "collision" line) is used for each port, along with an upstream clock line and a downstream clock line (for example, Acol is used for A port). ). The respective data lines of the A port and the B port are connected to a multiplexer 60, which
One of the two words competing with each other, whichever has a higher priority, or its common word (when the competing words are the same as each other) is connected to the upstream port (C port) as the data signal C0. The switch is connected to the up register 62 which is open. At the same time, the downstream data sent from the higher hierarchy nodes and received at the C port is shifted into and out of the down register 64 to give A
It occurs as an output on both port and B port.

One of the serial upstream signal streams of bytes can be blocked, however, this does not cause any additional upstream or downstream delay, and multiple words Under the control of the word clock and byte clock, they are advanced through up register 62 and down register 64 in a continuous sequence.

The competing bytes supplied to the A port and the B port at the same time are detected by the first and second parity detectors 6
6, 67 and also to a comparator 70, which is based on 8 data bits and 1 control bit, whereby the lowest value data content gets priority. To determine priority. In the protocol for determining the priority, the "idle" signal, that is, the signal when there is no message is a string of "1" that continues without interruption. Parity errors are typical causes, such as the presence of excessive noise, and other
It can be caused by some factor that affects signal transmission or circuit operation. However, in the system of this embodiment, the parity error indication is also used for another important purpose. That is, each time a microprocessor goes into an inoperable state, the transition is marked each time that all output lines, including the parity line, go high (i.e., its value is "1"). , Which results in an odd parity error condition. This parity error indication is transmitted as a "marker" in the network if one error occurs, and this marker causes
The system is capable of initiating a procedure to identify when a change has occurred in global resources and to determine what the change is.

The pair of parity detectors 66 and 67 and the comparator 70 supply signals to the control circuit 72.
Includes a priority message switching circuit 74 and also locks the multiplexer 60 in one of two states in response to the output of the comparator 70 if the priority is determined. Is configured, and further,
It is configured to generate and propagate a collision signal in the downstream direction. Transition parity error propagation circuit 76
The circuit is forcibly created in the network by the circuit described above, in which the parity error condition described above, in which all lines are simultaneously "1" s, is created.
The reset circuit 78 is for returning this node to the initial state, and the end of message (end of message)
message: EOM) detector 80 is included.

In order to perform the functions described above as well as the functions described below, each active logic node may use a microprocessor chip to perform those functions. However, it can be more easily implemented by having these functions performed in accordance with the state diagram of FIG. 5 and the logical equations described below. In the state diagram of FIG. 5, the state S0 represents an idle state, and since the competing messages are the same, the state in which one port is prioritized over the other port is not determined. It represents. The S1 state and the S2 state are the state in which the A port is prioritized and the B state, respectively.
The port has priority. Therefore, if the data content of BI is larger than the data content of AI and there is no parity error in AI, or if there is a parity error in BI (there is a parity error in these AIs). The condition that the parity error is not present and the condition that the parity error is present in the BI are denoted by ▲ ▼ and BIPE, respectively, and the flip
Port (represented by the state of the flop) has priority. The opposite logical states (logical conditions) of AI and BI exist as states (conditions) in which this device should shift to the S2 state. If a higher hierarchy node issues an indication that a collision has occurred in that hierarchy, that indication will be sent back as COLIN in the downstream signal. The device transitions to the S3 state, whether it is in the S0 state, the S1 state, or the S2 state, and sends this collision signal downstream to Acol and
Transfer as Bcol. When in the S1 state or the S2 state, since this node has already made a decision, the collision signal is sent in the downstream direction to the (two) nodes in the lower hierarchy in the same manner. When
The priority message switching circuit 74 is locked to the A port or the B port depending on the situation.

The reset circuit 78 includes an EOM detector 80, which is used to reset the node from S3 to S0 (FIG. 5). The first reset mode utilizes the end of message (EOM) field which terminates the data field in the primary message as shown in FIG.
Using a group of flip-flops and a plurality of gates, the following logic states are created.

URINC · URC · URCDLY where URC represents the control bit in the up register, URINC represents the value of the control bit in the input signal input to the up register, and UR
CDLY represents a C value (= value of control bit) in the up register delay flip-flop.

As shown in FIG. 6, a bit pair (bit pair) in which two consecutive bits in the sequence of control bits are one set.
, But also specifies certain fields and the transition from one field to the next. For example, "1" used when idle
From the control bit state that is followed only by "0, 1" bit
The transition to a sequence (= bit pair) marks the beginning of the field. This sequence of "0,1" is used to identify the start of the data field. The string of "1,0" control bits that follows it indicates an internal field or subfield, and is an end of message (EOM).
Are identified by a control bit pair of "0,0".
A string of bit pairs of "1,0" followed by "0,0"
The state in which the bit pair of is comes is a state that there is no other and can be easily identified. The URINC signal, URC signal, and URCDLY signal are collectively ANDed (logical product).
, And each of these signals is in a relationship of being delayed by one byte clock from each other. The resulting waveform of the ANDed signal is high until the beginning of the message packet, turns low at this beginning, and while this data (= message packet) continues, The waveform remains at a low level. This waveform returns to a high level two byte clocks after the EOM is generated. The EOM is detected by this transition in which the waveforms URINC, URC, and URCDLY turn to positive. As shown in FIG. 5, S1 or S2 is caused by this positive transition.
The operation of returning from S0 to S0 is triggered.

When a node in a higher hierarchy is reset, it becomes a ▲ ▼ state, which means that the collision state has disappeared. This logic state initiates a return operation from S3 to S0, which is the ground state. Please note that this ▲ ▼ state is the end of
That is, as a message “runs through” the layers of network 50 one after another, it propagates downward to those layers. As described above, each node can reset itself regardless of the length of the message. It should be further noted that, regardless of the initial state of the network, all nodes will be reset to the S0 state if an idle signal is provided.

The collision signal is returned to multiple processor modules. The modules store this collision state information and revert to the operation of sending an idle sequence, which is performed throughout the duration of the winning processor in the race. There is. The processor is COLIN ▲
New transmission can be started as soon as the transition to ▼ is detected. In addition to this, the processor is 2N, where N is the number of hierarchies in the network.
It is designed so that a new transmission can be started if the idle signal is continuously received for the number of byte clocks, which is the same as the former situation. , Because it indicates that no previous transmission has remained in this network. The latter of these new ways of enabling transmissions allows a processor joining the network for the first time to enter a message synchronization state with the network, as long as the traffic is small. Participating processors do not have to wait for polling from another processor to initiate intercommunication with other processors on this network.

The parity error state is shown in the state diagram of FIG. 5 and is set according to the following logical equation.

PESIG = AIPE ・ ▲ ▼ ＋ BIPE ＋ ▲
▼ BIPEDLY Up if the logical state of this PESIG is true.
The input signal URIN to the register is (URIN 0 ... URIN 7,
C, P = 1 ... 1, 1, 1). To satisfy the above equation, the transition parity error propagation circuit 76
Flip-flop for PE, that is, parity error of A input, and delay flip-flop (AIPEDY)
Includes and. The latter flip-flop is an AIP
According to the setting state of E, the state is set one byte clock later than that. Therefore, regarding the A input, when the flip flop for AIPE is set by a parity error, the PESIG value becomes high level for one byte clock, so that this PESIG signal becomes a parity error. Is propagated only once when the first display of is made. The same situation occurs when multiple data bits, control bits, and parity bits all have a value of "1", which results in the previously described transition of global resource states. It is a state that occurs when you do. This causes all lines to go high, forcing a state of all '1's to establish a total number of even states (odd parity states), resulting in the AIPE flip states described above. The flop and the AIpedly flip flop will be set to indicate a parity error. The above arrangement operates in a similar manner even if the message packet received at the B port contains a parity error or a forced parity indication to indicate a status change.

Parity errors caused by noise effects and other variables usually do not affect the operation of the processor because they use redundant dual networks. Is. For monitoring and maintenance, an indicator light (= indicator light: not shown) is used to indicate the occurrence of a parity error. However, for a one-time-propagating parity error that indicates a change in status, it initiates a routine to evaluate the significance of the change.

The clocking system used in this node 54, as shown in FIG. 4, is a skew between clocks at all node elements, regardless of the number of hierarchies used in the network. ) Is zero, that is, to maintain the zero skew condition. The clock circuit 86 includes a first and second exclusive OR gate 88,
The outputs of their exclusive OR gates, which include 89 and are designated A and B, respectively, are such that an adder circuit 92 performs a subtraction therebetween (ie, a "BA" operation). The combined output of the adder circuit 92, after being passed through a low pass filter 94, controls the phase of the output from the oscillator (PLO) 96, which is a phase locked loop. The inputs to the first exclusive-OR gate 88 are the output of this PLO 96 and the downstream clock supplied from the adjacent higher hierarchy node element through the isolation drive circuit 97. The line of this clock is labeled "Word Clock", which is obtained from a neighboring higher hierarchy after a known delay τ, and this same clock signal is now By way of one isolation drive circuit 98, it is returned to the adjacent node in the higher hierarchy. The input to the second exclusive-OR gate 89 consists of this word clock and clock feedback from the adjacent lower hierarchy, which in turn receives the signal from this PLO 96. .

The word clock line above is the third exclusive OR
It is connected to the two inputs of gate 100, both of which are directly connected and those connected through τc delay line 101. As a result, a byte clock signal having a frequency twice that of the word clock and having a timing matched with the word clock is obtained.

The operation of the clock circuit 86 described above can be better understood by referring to the timing diagram of FIG. The clock out signal (clock output signal) is the output of PLO 96. Of course, the main purpose of this clocking system is to maintain a zero time skew condition between the clock output signals for all nodes in the network, so of course those clock outputs The signals must also have the same nominal frequency as each other. The delay τ due to the transmission line between the nodes is set to a substantially constant value, but this delay value itself can be set to a long time. If the method disclosed here is adopted, the byte clock speed of the network and the node will be as long as 28 feet (8.53 m) when the speed (nominal 120 ns) used in the actual system is adopted. It is possible to As will be readily appreciated by those skilled in the art, networks that are not fully populated with the maximum possible number of processor modules can be provided with additional layers to increase the length of this 28-foot integral multiple. Can easily be obtained. In that case, the latency, i.e. the transmission time of the transmission carried out through the network, is correspondingly increased.

As shown by the waveform just below the clock out signal in FIG. 7, the word clock from the adjacent higher hierarchy has a waveform similar to the clock out signal, except that τ Just late. This word clock forms the underlying timing reference common to all nodes, but it is possible to control the leading edge of each clock out signal within the circuit. , And by leading their leading edge to the word clock, all nodes can be kept in sync. As can be seen by referring to waveforms A and B, the pulse A generated by the first OR gate 88 ends at the position of the leading edge of the word clock, while the second
Pulse B generated by the OR gate 89 of FIG. 1 has its leading edge coincident with the leading edge of the word clock. The trailing edge of this B pulse is located at the beginning of the feedback pulse from the adjacent module in the lower hierarchy, which is delayed by τ so that the B pulse has a constant duration. Has become. The clock circuit 86 acts to keep the duration of the pulse A the same as the duration of the pulse B, the reason for doing so is to advance the phase of the PLO 96 so that the synchronization state is established. This is because the output signal of the adder circuit 92 (the signal obtained by performing the subtraction “BA”) approaches zero as it goes along. In practice, adjustments are made to the leading edge of the A signal, which may either lead or lag the preferred position as indicated by the dashed line, so that the leading edge of the A signal is the word. It should be at a position that precedes the leading edge of the clock by time τ. If the leading edge of the clock out signal is located at this preferred nominal position at all nodes, then there will be a zero skew condition between the word clocks. Thus, each processor connected to the network is relieved of the constraint on the total length of the path from one processor to another, which means that the delay does not accumulate and the propagation time is different. This is because it does not occur.

Word line delayed by delay time τc by delay line 101 to generate a double frequency byte clock.
The clock is duplicated and this delay line 101 also supplies a signal to the gate 100. Therefore, as can be seen from the waveform labeled Byte Clock in FIG. 7, byte clock pulses of duration .tau.c are generated at both the leading and trailing edges of the word clock. .
The generation of this pulse occurs twice during each word clock interval, and, moreover, all of the nodes occur in synchronization with the word clock. In the above description, the delays caused by the transmission lines between the nodes are almost the same no matter which direction the transmission is from layer to layer, so that virtually all delays in this system are It is a natural premise that the word clock and byte clock of the above are kept in a stable phase relationship with each other. Therefore, the byte clock generated locally (= inside an individual node) is 2 bytes of the message at each node.
It provides a clocking function for a word (= word of 2 bytes) for that individual byte.

The above active logic nodes have potential advantages whenever they try to settle contention between simultaneously sent message packets based on their data content. On the other hand, for example, 1
U.S. Pat. No. 4,251, issued Feb. 17, 981
No. 879, "Speed Independent Arbi Switch for Digital Communication Networks"
ter Switch for Digital Communication Nbiworks) "
The majority of known systems, including those shown in, aim at determining which signal is first received in time, and require external processing circuitry or control. It is supposed to use a circuit.

(Processor Module) The individual processors shown in the schematic diagram of the entire system of FIG. 1 are interface processors (IFPs) 14 and 16 and access module processors (AMP) 18 to 18 respectively. 23, and the processors are roughly subdivided into a number of major components. A more detailed example of the construction of these processor modules (IFP and AMP) has a correspondence with, but not limited to, the functional rough subdivision of FIG. , Will also show a great deal of further subdivision.
As used herein, the term "processor module" refers to the entire assembly illustrated in Figure 8 by including optional elements described below. , IFP or AMP. Further, the term "microprocessor system" refers to a system 103 including a microprocessor 105, and here, the microprocessor 1
05 is, for example, Intel 8086 type (Intel 8086) 1
It is a 6-bit microprocessor or the like. The address path and data path of the microprocessor 105 are connected to a general peripheral system such as the main RAM 107 and the peripheral device controller 109 inside the microprocessor system 103. This peripheral device controller 109 is a processor
The module is AMP and the peripheral device is a disk.
This is shown as an example of what can be used in the case of the drive 111. On the other hand, if the processor module is to act as an IFP, then the controller or interface may be replaced, for example, by a channel interface, as shown in the dashed rectangle. IFP of such a specific example
Is responsible for communication with the host system channel or bus. Since conventional general controllers and interfaces can be used in the microprocessor system 103, these controllers and interfaces do not need to be described in further detail.

It should be noted that the use of one disk drive per microprocessor can be shown to have both cost and performance advantages. The advantage of such a scheme is generally true for databases, but sometimes it is necessary to configure the microprocessor such that one microprocessor can access multiple secondary storage devices. Can be beneficial. In the schematic diagram, other commonly used subsystems are incorporated and omitted for clarity.
This omitted subsystem is, for example, an interrupt controller or the like, and the interrupt controller is supplied by a manufacturer of semiconductors for use in combination with an in-house system. One of ordinary skill in the art will also appreciate the importance of taking appropriate measures to power the processor modules that can maximize the redundancy and reliability that the present invention can provide. Be understood.

Peripheral controller 109 and channel interface, shown as optional elements in microprocessor system 103, correspond to the IFP interface and disk controller in FIG. On the other hand, the high speed RAM 26 shown in FIG.
In practice, the first H.264. S. RAM 26 'and the second H.V.
S. RAM 26 "and each of them is
With time multiplexing,
From a functional point of view, it is effectively a 3-port device, and through one of those ports (the port marked as “C” in the figure), it becomes a microprocessor bus system. It is connected. H. S. RAM 26 ',
Each of the 26 "cooperates with a respective first or second network interface 120, 120 ', whereby each of the first and second networks 50a and 50b (these networks are shown in FIG. 8). Is not shown), and communication is performed via the input (reception) port A and the output (transmission) port B. Since there are two systems having redundancy with each other, The second network interface 120 'and the second HS RAM 26 "need only be described in detail. Network interface 120, 120 '
Although shown and described in greater detail in connection with FIG. 13, they can be divided into the following four main parts if subdivided into large sections.

The ten input lines from the second network 50b are connected to the H.264 via the interface data bus as well as the interface address bus. S. RAM26 "
Input register array / control circuit 122 connected to the A port of the.

The output line to the second network 50b is connected to the interface data bus as well as the interface address bus and to the second H.264. S. Output register array / control circuit 124 connected to the B port of RAM 26 ".

An interface address bus and an interface data bus; S. A microprocessor bus interface / control circuit 126 connected to the A and B ports of RAM 26 ".

Receives a word clock from the network, and
A clock generation circuit 128 that generates a plurality of clocks that are synchronous with each other and in the proper phase relationship for controlling the interface 120 '.

The second network interface 120 'and H.264.
S. RAM 26 "cooperates with microprocessor system 103 to coordinate the transfer of data between a fast-running network and a slower-running processor, as compared to it. It also serves the function of queuing messages exchanged between different systems (= network system and processor system) The microprocessor bus interface / control circuit 126 cooperates with the microprocessor system. (Read / write function: R / W function), and the microprocessor system (at least if it is an Intel 8086 type) has a H.S. The ability to write data directly to RAM 26 "and this H.264. S. And the ability to receive data from RAM 26 ".

The structure of IFP and the structure of AMP are similar to each other in their actions, however, H. S.
Regarding the size of the input message storage area and the output message storage area inside the RAM 26 ″,
There can be considerable differences between P and AMP.
In relational database systems,
In order to constantly utilize the network to meet the demands of the host computer, the IFP requires H.264. S.
Inside the RAM 26 "there is a large input message storage space for receiving new messages from the high speed network. More storage space must be available for packets.
H. S. RAM 26 "also operates in cooperation with main RAM 107 in microprocessor system 103, which includes a message buffer section for each network.

The manner of allocating system address space within main RAM 107 for microprocessor system 103 is shown in FIG. 9 and will be briefly described. According to a general method, an address allocated to the system random access function by leaving a space for expansion used when the storage capacity for random access is increased, and an I / O address space And an address space allocated for the functions of ROM and PROM (including EPROM). Further, some portions of the system address space are allocated to the first and second high speed RAMs 26 ', 2', respectively.
It is allocated for the message packets coming from the 6 "and for those message packets going to their high speed RAM. This allows a great deal of flexibility in the operation of the system, which is a microprocessor. Even if 105 can address the HS RAM 26 ″, the function of the main RAM 107 can prevent the mutual dependency between software and hardware.

Again referring to FIG. 8, as already mentioned, 2
It is possible to access H.264 from one direction. S. RAM
26 "is configured to perform the core functions of controlling multiprocessor motes, distributed updates, and managing message packet flow. To achieve these and further objects. For the H.S.R.
The AM 26 "is divided into a number of different internal sectors. The relative placement aspect of the various sectors shown in Figure 8 is employed in all of the individual processor modules in this system. Also, the specific addresses that specify the boundaries of those sectors are the addresses that are actually used in a certain system. It is to be noted that the size of these memory sectors and their relative placement can vary greatly depending on the specific system situation, a 16-bit memory word is employed in the illustrated example. The selection map and response directory are dedicated lookup tables of the kind that need to be written only once during initialization, while transactions Who number section provides a (the to be able to change the content many times while = work) look-up table dynamically revised freely.

The memory section of the selection map starts at location 0, but in the present example, basically four different maps are used within this memory section, and these maps are mutually exclusive. It is used in a method related to. Destination selection word (destinat) included in the message packet
Ion selection word (DSW) is H.264. S. RAM2
It is used in conjunction with a dedicated selection map within 6 ". This destination selection word consists of 16 bits in total, of which the map address and other bits occupy 12 bit positions. Map selection data occupying 4 bits.
S. The first 1024 16-bit memories in RAM
The words each contain four map address values. According to the address value specified in DSW, H.264. S. A single memory access to RAM will give the map bits for all four maps, while the map select bits contained in that DSW should use which map to use. To decide.

FIG. 15 shows the conceptual structure of the above map section, in which each map is as if it were composed of physically separate 4096 × 1 bit RAM. It is shown. Taking into consideration the convenience of implementation, as shown in FIG.
All map data is H.264. S. It is convenient to be stored in a single part of RAM. The DSW management section 190 (FIG. 13) is used by H.264. S. It controls the multiplexing operation for the four bits from each of the four maps of FIG. 15 resulting from one 16-bit word in RAM. As will be appreciated by those skilled in the art, the advantages of this scheme are: S. Using the same means used to access the rest of the RAM,
The processor is able to initialize the map.

Further, three different classes of destination selection words are used, and correspondingly, the storage locations of the selection map are hash selection portion, class selection portion, and destination processor identification information (destination proc).
essor identification (DPID) is divided into select parts. This DPID clearly indicates whether or not the processor 105 is a specific processor intended as a transfer destination of the message packet. In contrast, the class selection portion is whether the processor is one of a plurality of processors belonging to a particular processing class that should receive the message packet, that is, a member of the processor group. It clearly indicates whether or not. Hash values are relational
It is stored according to the distribution method when the database is distributed inside the database system. This distribution method follows the algorithm for the specific relation and the distributed storage method adopted in the system. It becomes a thing. When specifying a processor, the hash value in this specific example can be specified so that the processor has either primary responsibility for the data or backup responsibility. ing. Therefore, according to the plurality of selection maps described above, the H.264 standard is selected. S. The RAM 26 ″ is directly addressed to determine whether or not the processor is a transfer destination. This function sends a message to which priority is given to all the network interfaces 120. It is a complementary function that complements the broadcasting method, and it also allows local access to the status of the microprocessor 105 without interrupts.

H. S. One section of RAM 26 ", independent of the rest, serves as the central means for checking and controlling globally distributed activities. As already mentioned. , And as shown in Figure 3, a transaction number (TN) is assigned to each of the various operations sent to and received from network 50b. The reason why the TN is included is that each processor system 103 has a global transaction identity (transaction identification information) when executing the subtasks accepted by each processor system 103 independently of each other. .. A dedicated block for storing the addresses of multiple available transaction numbers in RAM 26 ". But houses the (entry for = Status) the status entries that are locally controlled and updated by the microprocessor system 103 in performing their subtasks.
TN is used in a variety of different uses, both locally and globally, when performing intercommunication functions. Transaction numbers are used to identify subtasks, to call data, to give commands, to control the flow of messages, and to identify the type of global processing dynamics. The transaction number can be assigned, abandoned, or modified during the execution of the global communication. These features will be explained in more detail in the following description.

Among the features of TN, the most complex but perhaps the most effective feature is that by cooperating with a sorting network (a network having a sorting function), the local processor (= Its ability to allow distributed updates of the status of individual processor modules). Each control process (ie task or multiprocessor activity)
Has its own TN.

The value of the readiness state (state in which the processor is ready for operation) is H.264. S. RAM2
It is designed to be held in a 6 ″ transaction number section, and this readiness state value is modified locally (= inside individual processor modules) under the control of the microprocessor system 103. The microprocessor system 103 includes a tenth
Appropriate entry (eg S
ACK / Busy) (address is “050D (hexadecimal)”), and by transferring the image as duplicated by it, H.264 of this SACK / Busy status. S.
Input to the RAM 26 ″. An entry input to a certain TN address (= storage location corresponding to transaction number) is input via the A and B ports of the HS RAM 26 ″ and to the interface 120 ′.
It is possible to access from the network 50b via. Inquiries are made using a "status request" message containing the command code (see FIG. 11) of the status request (status request) and the TN. The interface 120 'is
The contents stored in the TN address of the designated TN are used to refer to the response directory which stores the response message written in the appropriate format. If the second network interface 120 'receives a global status inquiry for a given TN, it elicits a direct response that is only under hardware control. No pre-communication is required and the microprocessor system 103 is neither interrupted nor affected. However, the "lock" indication is displayed on interface 1
If the status is set by transfer to the microprocessor 20 ', the microprocessor system 10
3 disables interrupts and interface 120 '
Keeps communicating the lock word obtained from the address "0501 (hexadecimal)" until the exclusion is performed later.

The word format of the readiness state is shown in seven types of states from "busy (busy: state during operation execution)" to "initial (initial: initial state)" in FIG. 12, and this FIG. It illustrates one useful example employed in some practical systems. Although it is possible to make modifications such as classifying the readiness state into more types and smaller types, it is suitable for many applications by using the seven types of states shown in FIG. Extensive control is possible. H. S.
The status level of each TN in the RAM 26 ″ (= the level of readiness status represented by the entry stored at each TN address) is continuously updated, thereby making the availability of the subtask and the subtask It is the responsibility of the microprocessor system to keep track of the progress of the process, and such an update may be performed by using the format shown in FIG.
S. It can be easily executed by writing to the TN address in the RAM 26 ″.

In Fig. 10, each status response (status response)
For "05" to "0D" (hexadecimal number), the leading part of each is a status acknowledgment command code.
de: SACK). Those SACK responses sent to the network actually consist of the command code of Figure 10, the numeric portion of the word format of Figure 12, and the originating processor ID (OPID), This is as shown in FIG. Therefore, those SACK responses form a group of priority subgroups within the overall priority convention shown in FIG. OPID
Is meaningful with respect to priority conventions, for example, if multiple processors are working with one TN, but both of them are in a "busy" state, they are broadcasted. This is because the highest priority message is determined based on this OPID. Transfer and system coordination can also be performed based on this data (OPID).

Priority rules are set for SACK messages (= SACK responses), responses are sent simultaneously from a plurality of microprocessor systems 103, and dynamic (= transmission) in the network 50b. The priority determination is performed so that the determination of the status of the global resource for a given task is performed in a significantly improved manner compared to conventional systems. It has become. The resulting response is unambiguous and never represents an unspecified condition, nor does it require any software or time-consuming local processor (= individual processor module). . Thus, for example, deadlocks never occur due to frequent status requests that interfere with task execution. Many optional operations of multiprocessors are available at various status levels. Local processors can continue to operate independently of each other, and with a single query, 1
It is unprecedented that one global, prioritized response is elicited.

It may be helpful to explain the sequence of states shown in FIG. 12 in some detail here.
The “busy” state and the “waiting” state are states in which the assigned or delegated subtasks will gradually progress to a stage closer to completion.
The state indicates the state that requires further communication or event. These "busy" and "waiting" states are the levels at which the status of a TN rises to a higher level until it reaches a status level at which it can send or receive message packets for that TN. It shows an example of a rise.

On the other hand, when transmitting or receiving a message packet, the TN capability in message control, which is another characteristic of the TN, is exerted. When the microprocessor system 103 has a message to send, the status display changes to "send ready". The microprocessor system 103, in addition to updating the status display,
Using the word format of FIG.
The value of “message vector” is set to H.264. S. Input to the RAM 26 ″. The input entry specifies from which location in the HS RAM 26 ″ the corresponding output message should be retrieved. This vector connects multiple output messages related to a certain TN into one (= chain),
It is used internally in the network interface 120 '.

The functions related to the above functions are "Ready to receive (receiv
e ready) ”state. In this “ready for reception” state, the storage location of the TN (= TN
Address) holds an input message count value obtained from the microprocessor system 103, and this input message count value is
A value related to the number of messages that can be received associated with a given TN. This count value is decremented as the incoming messages are transferred in succession, and may eventually reach zero. If it reaches zero, no further messages can be received and an indication of an overrun condition will be made. As described above, the network 5 using the TN
The speed of transmission between 0b and the microprocessor system 103 can be adjusted.

Explaining the local (= individual processor) aspect, in each processor, the TN is a constant reference that is valid in the entire system in the transmission message and the reception message while the processing is executed. Is held as. The "TN0" state, or default state, also serves as a local command to demonstrate the fact that the message should be used in non-merge mode.

From a global perspective, "TN0" and "T0"
By distinguishing various values with “N> 0” as those having different properties from each other, one command function of a plurality of command functions using the TN is defined. That is, by distinguishing the TNs in this way, a characteristic description (characterization) representing either "merge / non-merge" is attached to each message packet, and thereby, a plurality of messages are included. On the other hand, a powerful system operation method of determining priority and sorting is obtained. Similarly, "Assigned (assigned state)", "Unassigned (unassigned state)", "non-participating processor (No
n-Participant) "as well as the status" initial "are used to perform the functions of global intercommunication and control. The "unassigned" state is the state in the case where the processor previously abandoned the TN, so it is the state in which it needs to receive a new primary message to reactivate the TN. If the processor is displaying "Unassigned" when the status display should be "Assigned", this is T
Corrective action must be taken because it indicates that N was not properly entered. If the TN is "unassigned" when it should be "unassigned", this means that an incomplete transfer is occurring or there is a conflict between the two processors for a new TN. May be an indication of what is being done. Neither "Assigned" nor "Unassigned" is treated as a readiness state because the processor is not yet working on the TN at the stage when they are displayed. Is.

Furthermore, the "initial" and "non-participating processor" states are also important in the context of global resources. The processor that is going on-line, i.e., the processor that has to be subscribed to this system, is in the "initial" state, which is an administrative step to bring this processor online. It means that you need to step on. A processor that is in the "non-participating processor" state for a given task does not need to perform any processing locally, however, by tracking this TN, it is inadvertently improperly used by this TN. It is necessary to prevent it from being done.

Referring again to FIG. S. RAM2
The 6 "dedicated directory or reference section also contains a number of other types of prioritized messages used in the hardware to generate responses, in addition to the types described above. NA (no
The entry “t assigned:“ not assigned ”) is prepared for future use and is held in a usable state. 3 different types of NAK
The responses (overrun, TN error, Locked NAK responses) have the lowest data content and therefore have the highest priority, which means that their NAK responses indicate an error condition. Because it is a thing. Multiple SACK responses followed by ACK response and NA
P responses (non-corresponding processor responses) follow, and they are arranged in order of decreasing priority. In the configuration of this specific example, the two response command codes have no function assigned (that is, NA), and are ready for future use. Since the directories described above can be initialized by software and are used by hardware, any of a wide variety of response message texts can be generated quickly and flexibly. You can

Using one independent part of the above directory that is independent of the other parts, TOP, GET, P
The respective addresses of the UT as well as the BOTTOM are stored, i.e. a pointer to the function of the circular buffer for the input message and a pointer to the complete output message. These pointers are respectively assigned to the management of the input message and the management of the output message in the H.264 standard. S. It functions in cooperation with each dedicated sector of RAM 26 ". A circular buffer scheme is used for incoming messages, in this case H.264.
S. The "TOP" stored in the directory section of RAM 26 "is a variable address that specifies the upper address location for the incoming message. The PUT address stored in the same directory section specifies the address location where the circuit should store the next received message. GE
The T address is set and updated by software so that the software can recognize at the address location where the software is blanking the buffer.

Input message buffer management sets PUT to the buffer's bottom address and then GETs
This is done by starting with the address equal to TOP. The operating rule defined by the software is that GET must not be set equal to PUT, and if so, an undefined state (ambiguous condition) will occur. It will be. The input message is H.264. S. When input to the input message buffer in RAM 26 ", the message length value contained in the message itself determines the starting point of the next incoming message and is then stored in the directory. The PUT address is changed to display the storage location in the buffer that should receive the next incoming message. Can retrieve input messages when is allowed.

H. S. The data stored in the output message storage space in the RAM 26 ″ includes the output message completion vector held in a circular buffer independent of other parts, and the next message in the HS RAM 26 ″. Used with vectors. Editing (assembling) and storing of individual messages can be performed at any location, and a plurality of messages related to each other can be connected (chained) to be sent to the network. You can do it. H. S. In the RAM 26 ″ directory section, TOP, BOTTOM, P
The respective addresses of the UT and the GET have been entered and updated as described above, whereby
A dynamic current indicator of the location in the output message completion buffer is maintained. The message completion vector constitutes an index address for pointing to a message stored in the output message storage space, which is indicated by the received response indicating that the transfer has already been properly performed. is doing. As will be explained later, this system allows the microprocessor system 103 to easily input outgoing messages, while it allows complex concatenated vector sequences to be organized in an orderly manner. So that you can handle it,
The output message storage space is used efficiently, allowing the transfer of message chains.

The protocol of FIG. 11 described above for the response is also defined for the primary message following the response. A plurality of types of response messages are arranged in succession with each other, and hexadecimal command codes are shown in ascending order. Within the group of primary messages, the merge stop message (which is also a non-merge control message, which is the basic control message) has the lowest data content and therefore the highest priority. is there. This message constitutes a control communication that terminates the merge mode in the network as well as in the processor module.

A large number of different types of primary data messages can be utilized in ascending priority order, and they are related to priority based on application requirements and system requirements. Classification can be added. As mentioned earlier, continuation messages that follow other messages can be given high priority in order to maintain their continuity from the preceding message packet. it can.

The bottom group in FIG. 11, consisting of four types of primary messages, is the only type of status message that requires a status response from higher priority to lower priority. status·
It includes a request message, respective control messages requesting "TN Abandonment" and "TN Assignment", and a lower priority "Start Merge" control message.

The configuration described above enables operations that can be used for many purposes, as will be apparent from more detailed specific examples described later. The processor module is currently present transaction number (PT).
N), and in this case,
Whether the PTN is externally specified by a command from the network, or internally generated while performing a sequence of operations,
Same thing. When a merge operation is being performed, the processor module uses the global reference,
That is, the operation is executed by utilizing the transaction identity (= information for identifying the transaction), and this transaction identity is defined by the TN. Starting, stopping, and resuming the merge operation is done using only simple message changes. If the subtask does not need to merge the messages, or if a message packet is generated that has no special relation to other messages, those messages will be output to "TNO". Queue to do
And the transfer occurs while the basic or default state (which is 0), currently defined by the transaction number, remains true. This "TN0" state allows messages to be queued for transfer when the merge mode is not used.

(Network Interface System) Referring now to FIG. 13, which shows one specific example of an interface circuit suitable for use in the system of the present invention in more detail. Although the description in this "Network Interface System" chapter contains a number of detailed features that are not necessary for an understanding of the present invention, these features are not incorporated into the actual system. Therefore, it is included in the description for clarifying the positioning of various embodiments with respect to the gist of the present invention. Regarding various specific configurations and structures for gating, which are not the subject of the present invention and are related to known means, a wide variety of alternative configurations can be adopted, and therefore description thereof will be omitted. Or decided to simplify. FIG. 13 shows the second network interface 120 'shown in FIG. S. 3 is a detailed view of the RAM 26 ". The respective interfaces 120, 120 'for the two networks function in a similar manner to one another, so it is sufficient to describe only one.

In FIG. 13A, the input from the active logic network 50, which is connected to the interface shown in FIG. 13A, is supplied to the network message management circuit 140 via the multiplexer 142 and the well-known parity check circuit 144. ing. Multiplexer 142
Is also connected to the data bus of the microprocessor system, which allows access to the message management circuit 140 via this data bus. This feature allows the microprocessor system to operate the interface in step-by-step test mode, and whether this interface is connected to the network as if it were on-line. As described above, data transfer is performed. Input from the network is provided to the receive network data register 146, with byte data input directly to the first section of this register 146 and via the receive byte buffer 148. Byte data to be input to the register 146, and the receiving byte buffer 148 stores its own byte data after the byte data is input to the first section.
The data is input to another section of this register 146. This will cause both of the two bytes that make up each word received to be input to and held available in the receive network data register 146.

The output message to be transmitted is input to the transmission network data register 150, and a parity bit is added inside the normal parity generation circuit 132. The message is sent from the network message management circuit 140 to the network connected to it, or (if test mode is used) to the microprocessor system data bus. For the purpose of message management inside this interface, the format of the transmission message stored in the random access memory 168 is supposed to include identification data as well as message data. As can be seen in Figure 21A, any of the commands, tags, keys, and DSWs can be combined with the primary data to be transmitted.

The configuration shown in FIG. 13A is essentially the same as the configuration shown in FIG. 8, except that in FIG. 8 the interface data bus as well as the interface address bus is H.264. S. RAM 26 "is shown separately connected to input port A and input port B, and the address and data buses of microprocessor system 103 are shown connected to independent C ports. However, in reality, the 13A
As can be seen from the figure, such access from two directions independent of each other is carried out in the H.264 standard inside this interface. S. This is accomplished by time division multiplexing of the input and output address functions in RAM 26 ". The microprocessor data and address buses are gates 145 and 14, respectively.
9 and 9 to the respective buses of the interface, which enable the microprocessor to operate asynchronously on the basis of its own internal clock.

The timing scheme used is based on clock pulses, phase control waveforms, and phase subdivision waveforms, which are
It is generated by the clock circuit 156 (Fig. 13) and has the timing relationship shown in Fig. 14 (Fig. 14 will also be described later). Interface clock circuit 156 receives the network word clock from the nearest node, and phase lock clock source 157 provides zero time skew as described above in connection with FIG. Includes means to maintain. The nominal network word clock speed in the 240 ns network is subdivided in time within the interface clock circuit 156 by the frequency divider held in the phase locked state (details). Not shown), but a high-speed clock (shown as PLCLK in FIG. 14) that defines a reference period of 40 ns in duration.
Is provided. What defines the basic word period is a periodic signal, labeled CLKSRA in the figure, which has a total period of 240 ns and is inverted every half cycle. Two other signals having the same frequency and duration as CLSRA, the frequency divider 158 based on PLCLK
These signals are generated by CLK
It is generated at the time delayed by one cycle and two cycles of PLCLK from SA.
It is given the names SRB and CLKSRC.

Based on the above various signals, the control logic 159
A timing waveform (hereinafter also referred to as a gate signal) called "IO GATE", "RECV GATE", and "SEND GATE" is created, and these timing waveforms are divided into three equal parts of word periods. It displays each interval. Corresponding names such as "IO phase", "reception phase", and "transmission phase" are given to these intervals. These phases, defined by the gate signal, each further include an "IO CLK" signal,
"RECV CLK" signal and "SEND CL
It is subdivided by the "K" signal into two equally divided half-intervals, which subdivide the second half of each phase. The byte clocking function uses the "BYTE CTRL" signal and "BYTE CL
K ”signal.

The IO phase, RECV phase (reception phase), and SEND phase (transmission phase) described above are performed by the random access memory 168 and the microprocessor.
It provides the basis for enabling the system bus to perform time-division multiplexed operations. The interface can only receive or transmit one word per word period with the high speed network, and obviously, the receiving and the transmitting never occur simultaneously. The transfer rate to and from the microprocessor system is much lower than the transfer rate to and from this network, but even if they are of equal speed, it is too large for the capability of the interface circuit. There is no burden. The system configuration of this interface is such that most operations are performed by direct access to the random access memory 168, so that internal processing or software is rarely required. It has become. Therefore, as the system cycles through successive phases within each word period, the words are determined by the number of words specified for each word one after the other, without colliding with each other. Are followed along the signal path in order to perform various functions. By way of example, the sending of messages to the bus should occur between receipts of messages from the microprocessor, and each of them should alternate using different portions of memory 168. You can

Intercommunication between the data bus of the microprocessor system and the network interface is accomplished by the IO management circuit 160 (reading / writing this IO).
/ Write) sometimes called). A bus for the microprocessor and a bus for the network interface, with a write gate 162 for gating the word coming from the microprocessor system and a system read register 164 for sending the word to the microprocessor system.・
The interface is connected.

In addition, a memory address register 165 and a parity generator / check circuit 166 are incorporated into the network interface subsystem. In this specific example, the high-speed memory (= HS.RAM) is composed of a random access memory 168 of 4K words × 17 bits. The usage of the plurality of dedicated memory area portions that have been described is as described above.
Size of this random access memory (= capacity)
Can be easily reduced or expanded to suit the needs of a particular individual application.

A receive message buffer management circuit 170 is connected to the microprocessor's data bus and also to the memory 168's address bus. The term "received messages" refers to
Input from the network and press "P" in the circular buffer.
It may also be used to point to a message that is entered into a storage location called "UT", and after this entry, the message thus entered into the circular buffer is forwarded to the microprocessor. Sometimes used to indicate that. When a transfer to this microprocessor occurs,
The value "GET" specifies from which location the system should perform successive fetch operations when performing fetching of received messages to be forwarded to the microprocessor system. Random access memory 168
, A plurality of address values used for the access are input to the GET register 172, the TOP register 174, the PUT counter 175, and the BOTTM register 176, respectively. The PUT counter 175 is updated by incrementing by 1 from the initial position designated by the BOTTOM register 176. The TOP register 174 provides an index of the boundary on the other side. Both the TOP value and the BOTTM value are
It can be manipulated by software control, whereby the size of the receive message buffer and the H.264 standard. S.
It is possible to change both the absolute storage location in RAM. The content of the PUT register is T
When it equals the contents of the OP register, the PUT register is reset to equal the contents of the BOTTM register, thereby making this buffer available as a circular buffer. Above GET register, TOP register, BOTTOM register, and P
The UT counter is used to manage both the input message circular buffer and the output message complete circular buffer.

Input to the GET register 172 is performed under the control of software, because the next address (next address) is determined according to the length of the message currently handled in the buffer. . Comparing circuits 178 and 179 connected to the respective outputs of GET register 172, PUT counter 175, and TOP register 174 are used to detect and indicate overrun conditions. Overrun state is GET
If the value of PUT and the value of PUT are set to the same value, G
This is a situation that occurs when an attempt is made to set the value of ET to a value larger than the value of TOP. In either of these cases, an overrun status indication will be sent, and this status indication will continue to be sent until the overrun condition is corrected.

The above continuous scheme in constructing and operating the "received message" circular buffer is particularly suitable for this system. By enabling mutual checks to avoid conflicts,
The "UT" can manage the hardware, and the "GET" can be managed dynamically. However, it is also possible to adopt a buffer system of a method other than this. However, in that case, it will probably add some extra burden on the circuit and software. Referring now to FIG. 21B, the format of the received message stored inside memory 168 further includes map result, data length,
It also contains identification data in the form of key lengths, which will be explained later on.

DSW management section 1 inside this interface
90 includes a transfer destination selection word register 192. The transfer destination selection word register 192 has a transfer destination selection word (D) to be transferred to the address bus.
SW) is input. When a dedicated DSW section of memory 168 is addressed using DSW, this memory 1
The output sent from the 68 onto the data bus returns the data on the basis of which the DSW management section 190
However, it is possible to determine whether or not the message bucket has the processor as the transfer destination. As can be seen from FIG. 13A, the transfer destination selection word is a 2-bit map nibble (nybl) address.
It consists of a 10-bit map word address and 4 bits for map selection. Of these, the "nibble" address is used to describe a subsection of words from memory 168. The 4 bits for map selection are provided to map result comparator 194, which receives the associated map data from memory 168 via multiplexer 196. Multiplexer 196 receives 16 bits of data, the 16 bits of which are four different maps stored at the address specified by the 10 bits of the map word address contained in the DSW. -Represents a data nibble. Memory 168
Has its dedicated map section arranged in a form particularly suitable for comparison, so that the comparisons made here are easy. The remaining 2 bits in the DSW, which are provided to the multiplexer 196 for its control, select the appropriate one of the four map nibbles. A comparison is made and the map code resulting from the comparison is entered into the map result register 197 and inserted into the input message entered into memory 168. If the result of this comparison reveals that there is no "1" bit in any of the selected maps, then a "distance" signal is generated and the processor module is It is displayed that it was not intended to receive the message bucket.

Referring to FIG. 15, the memory 168 is shown in FIG.
A preferred method for subdividing the dedicated destination selection section of the and yet for making a comparison of the map results is schematically illustrated. Each map is 4
It is composed of 096 words × 1 bit, and is further subdivided into individual processor ID sectors, class ID sectors, and hashing sectors (see FIG. 8). 1
Two address bits (10-bit map address and 2-bit nibble) are used to select a common map address, which results in a 1-bit output from each map. (The multiplexer of FIG. 13 and its nibbles are not shown in FIG. 15 for clarity). The four parallel bit outputs can be compared with four bits for map selection in an AND gate group 198 consisting of four AND gates, resulting in one or more matches. If so, the output of OR gate 199 will be in the "true" state. This map result can be entered into map result register 197 of FIG. 13A, which causes the message to be accepted into memory 168.
If not, the message is rejected,
NAK will be sent.

The command word management section 200
It includes a command register 202 that receives a word. The TN field of the command word can be used to access the address bus, which accesses the indexed received TN to determine the appropriate response message (see Figure 18). ).
Further, when the "merge start" command is being executed, a data transfer path from the TN field to the PTNR (current transaction number register) 206 is secured, which corresponds to the "merge start" command. This is so that the value of PTN (currently the transaction number) can be changed.

The input message input to the memory 168, as described with respect to FIG. 21, is the length of the data and key fields, if used, to make the address vector available. It also includes the value. These length values are received data length counter 210 and reception key length counter 21.
, And each of these counters is adapted to count the sequence of words contained in those fields as they are provided by the input source to the respective counters. .

In addition, an outgoing message management section 220 is used, which includes an acceptance function for storing processed buckets in memory 168, and a function for sending those stored buckets to the network at a later time. is doing. This section 220 includes a send transaction vector counter 222, a send data length counter 224, and a send key length counter 226, which are bidirectionally connected to the data bus. The transmit transaction vector counter 222 is connected to the address bus, while the transmit data length counter 224 is the address generator 2
28, and this address generator 228 is further connected to the address bus. Messages are sent using both the output buffer section and the circular buffers that make up the output message completion vector section of FIG. However, in this specific example, after a plurality of message buckets are sequentially input, they are taken out in the order determined by the vector.

Inside this interface, the independent operation phases are executed at mutually exclusive times, and by adopting such a time division method, the memory 168 is configured so that the network clock speed is To receive and supply message buckets from the network, to perform internal operations at high efficient speeds, and to operate microprocessor systems asynchronously at their own slow clock speeds. It is possible to communicate between them. A phase control circuit, which controls the gating operation of messages to various counters and registers, operates in response to control bits.
It provides the data and other signals that indicate the individual fields within the message. Transmit state control circuit 250, receive state control circuit 260, and R / W (read / write) state control circuit 270 receive clock pulses, identify fields in the data, and transmit, receive, and processor It controls the sequencing of the data stream during the clock operation.

Control of this interface is performed by three finite state machines (FSMs), each of which has a transmit phase, a receive phase, and a processor (R
/ W) It is for the phase. Their FSM
Is configured in a general fashion using a programmable logic array (PLA), status register, and action ROM. Each FSM is advanced to the next state once every network clock cycle. Since there are many control signals to be generated, PL
The output of A is further encoded by the action ROM. As will be readily appreciated by those skilled in the art, a translation of a control sequence written for the FSM mode, and thus of general detail structure and operation, which is necessary for the operation of the network, is It's a simple task with a lot of work.

The inclusion of the state diagram of FIGS. 17 and 19 and the matrix diagram of FIG. 18 in the accompanying drawings is a comprehensive list of internal structural design features that can be employed in fairly complex systems. This is to present specific details. FIG. 17 is a diagram relating to the reception phase, and FIG. 19 is a diagram relating to the transmission phase. The notation used in these figures corresponds to the notation used elsewhere in this specification and the drawings. is doing. For example, the following terms are:

RKLC = Receive Key Length Counter RDLA = Receive Data Length Counter RNPR = Receuve Network Data Word Register PUTC = Put Counter ) GETR = Get Register (GET register) Therefore, the state diagram can be understood without any explanation by contrasting it with FIG. 13 and the specification. These state diagrams detail various sequences and conditional statements involved in complex message management and interprocessor communication. FIG. 17 (first
7A), the states in which the labels "generate response" and "decrypt response" are written, and the respective conditional statements indicated by the dashed rectangles are as shown in FIG. It complies with the specified responses and actions described in the matrix diagram. FIG. 18 shows both the response generated and the action performed for any combination of primary message and readiness state for a given TN. Obviously, when the system is operating normally,
Although some messages are rejected, error conditions rarely occur.

In both FIG. 17 and FIG. 19, many of the condition judgments can simultaneously execute complicated judgments, while the state step is It is being changed one by one. In either case, the sending operation and the receiving operation are operations that proceed at a predetermined speed without the need for external control, and the message structure and network operation method have already been explained. This is because it has been done.

Many of the features employed in typical processor and multiprocessor systems are not germane to the present invention and are therefore not specifically described. Among those features are:
There are validity error circuits, interrupt circuits, and various means for monitoring activities such as watchdog timers and a wide variety of test functions.

(Specific Example of Operation of System) The following describes that the system that integrates FIG. 1, FIG. 8 and FIG. S. RAM
9 is a number of examples showing how it works internally in various modes of operation in cooperation with the. Examples of those are:
An indication of how the interrelationships between priority rules, addressing schemes employed here, and transaction identities provide both local control and global intercommunication capabilities. Is.

Sending and Receiving Primary Data Messages Although FIG. 16 is further described in addition to other figures, FIG. 16 shows a simplified state diagram of the states involved in the final acceptance of a primary message. Is. When a message is received in a buffer or memory but the logical state shown is not met,
Acceptance has not been achieved. Although it is shown as a serial sequence of events in the figure, it is supposed that multiple determinations are made in parallel, that is, at the same time. Alternatively, the circuit skips an intermediate step to reach a certain operation step.

The message on the network of FIG. 1 is sent in the receive network data register 146 of FIG.
It is passed until the EOM state is identified, and when the state is identified, it is recognized that the message is complete. If a "LOCK" condition exists, the system will proceed to H.264 of FIG. S. The NAK / LOCK reject message is sent out by referring to the response directory in the RAM 26 ″.

If not, ie, there is no "lock" condition, the system moves to a map comparison check, which is performed inside the DSW management section 190 in the interface shown in Figure 13A. .
If there is an appropriate comparison result, represented by "map output = 1", the system can continue to receive the message. If no such comparison result exists, the message is rejected and a NAP is sent.

If the appropriate map is determined, then the system is ready to check the TN status, which is checked by looking up the directory of the TN shown in FIG. (Here the TN status is strictly the status of the processor for a given TN, and therefore the
S. Readiness state represented by the entry stored at the TN address in RAM). More specifically, this TN status check is performed to determine whether the local status (= status of individual processor module) is "ready for reception". Here, it is assumed that the TN has already been assigned by some preceding primary message.

If this check reveals that the TN is in either a "done" state, a "non-participating processor" state, or an "initial" state,
A "NAP" reject message is sent out (strictly speaking, TN is the entry stored at the TN address in the HS RAM.
This entry is also simply TN unless confused
Will be called). If this found status is any other non-specified condition, the reject message sent is a "NAK / TN error" and the above 2
One type of reject message is also retrieved from the response directory of FIG. If the status was "ready for reception," yet another determination would be made.

This other determination is related to the "input overrun", and this determination is performed by the GET address and the PUT address inside the input / output management buffer section 170 of FIG. Is done by comparing. In addition, the transaction number is also checked for a non-zero received message count value, and if this count value is zero, it is also indicative of an input overrun. If an overrun condition exists,
A "NAK / Input Overrun" is sent and the message is rejected.

If all the above conditions are satisfied, H.264. S. R
An "ACK" message (acknowledgement message) is fetched from the response directory in the AM 26 "and sent out on the network, so that the priority is argued with other processor modules. Some of those other processor modules may have similarly sent an acknowledgment to the received message. At this point, if the common response message received from the network (this "common" means merged) is the "ACK" message and thus "all" selected as the receiving processor module. If it is explicitly indicated that the processor module can accept a previously received message, then the received message is accepted. If this response is of any form other than "ACK", then the previous received message is rejected by "all" processors.

Receiving and Responding It should be noted that in this embodiment, all processors generate any one of ACK, NAK and NAP responses after the primary message is received. The processor can attempt to transmit the primary message immediately after receiving any one of these response messages. (The processor may also make this transmission attempt after a delay equal to or greater than the delay corresponding to the total latency for traversing the network, which was already discussed in the Active Logic Nodes chapter. As I did). Another thing to note is that if several processors send "identical" messages to each other, then all of those messages have won the race on the network. Is also possible. In that case, "all" of those sending processors
Will receive an ACK response. This will be explained in detail in a specific example below, which is broadcast (broadcast transmission).
And with respect to the operation of the global semaphore mode.

The actual implementation of the present invention includes many more types of responses in addition to those described so far and is adapted to perform various operations. FIG. 18 shows their responses and actions, including LOCK, TN error, and overrun interrupt conditions, nine different pre-identified status levels, and acknowledge (AC
K) and non-corresponding processor responses are indicated by the items arranged in columns.

When a processor module is ready to send a message, the PTN value stored in the PTN register 206 of FIG. 13 is ready for use,
Therefore, all that is required is confirmation that the TN status is in the "ready to send" state. As can be seen from FIG. 12, the entry (entry) of “ready for transmission” is
It contains the next message vector address for the output message. The assembled output message is sent out on the network, and if the race is lost, unless the PTN is changed in the middle,
This sending operation will be repeated until the transmission is successful, and if successful, a response will be received. If the transmission is successful and an acknowledgment is received, the address vector is changed. The next message vector is fetched from the second word (FIG. 21A) in the current message and this word is transferred from transmit transaction vector counter 222 to random access memory 168. If the output message section is not in the overrun condition, the PUT counter 175 is advanced by "1" and this overrun condition is indicated by the PUT becoming equal to GET. The transmission transaction vector counter 22
The next message vector transferred from 2 is
H. S. Current transaction number in RAM
Input to the transaction number address specified by register 206. If this new TN is in the "ready to send" state, the value of this input vector is again the storage location of the next message (next message) related to this transaction identity. Pointing to. H.
S. See FIG. 21 for the format of the output message stored in RAM.

However, message management when sending a message can include many different forms of operation, including internal or external modification of the PTN. An error condition, an overrun condition, or a lock condition can cause the system to shift the transaction number to "TN0", which causes the system to return to non-merge mode and "TN0". Checking the status at will continue until a "ready to send" condition is identified or a new TN is assigned. See the flow chart of FIG. 19 (FIG. 19A) as an illustration of the conditions and conditions that can be employed in a rather complex embodiment.

Example of Output Message Completion Buffer If the completion of the transmission of the message was indicated by any other response message except "LOCK", the pointer to the newly completed output message buffer is H.264. S. The output message complete circular buffer section of RAM (see FIG. 8) is stored.
This pointer is simply a 16-bit word that represents the address of the output message buffer. (The format of the output message buffer is shown in Figure 21. Note that the output message buffer contains a place to record response messages received from the network).

The output message completion circular buffer is between the network interface hardware 120 and the supervisor located on the microprocessor 105.
It fulfills the function of communication. A program provided in this microprocessor sends a message to be output to the H.264 standard. S. Store in RAM. This will be explained in more detail in the next example, where multiple output messages are chained together (chained) together,
The TN can be made to act as a pointer at the beginning of this chain, which can form a complex sequence of work. Other features include:
Since the network can be multiplexed or time-divisioned (multiplexed) between multiple TNs, which will also be described in detail later, it can be in different orders depending on the different events existing in various parts of the network. A message can be output.

Furthermore, H.264 occupied by successfully transmitted buckets. S. It is important to quickly recover the storage space in RAM so that it can be reused for another output bucket to be output. The output message complete circular buffer serves this function.

If the transmission of a data message is completed successfully and a response other than a "lock" response is received, the network interface may send an H.264 message. S. "0510" in RAM
(Hexadecimal) ”stored in the PUT pointer (first
(See FIG. 0) is advanced by "1", and the address of the first word of the output message which has just been transmitted is stored in the address in the PUT register. (When the value of the PUT pointer becomes larger than the value of the TOP pointer stored in "0512 (hexadecimal number)", the PUT pointer is the same as the BOT pointer (= BOTTOM pointer) stored in "0513 (hexadecimal number)". Will be reset first to be). If the PUT pointer becomes larger than the GET pointer (storage location "0511 (hexadecimal)"), then the circular buffer is overrun, so an "error interrupt" is generated towards the microprocessor.

Software executing inside the microprocessor asynchronously examines the output message buffer pointed to by the GET pointer. If the processor completes any processing that it is requested to execute,
The GET pointer is advanced by "1" (when the GET value becomes larger than the TOP value, it is reset to the BOT value). If GET = PUT then there are no more output messages to process. If this is not the case, then further output messages have been successfully sent and must be processed. For this processing, H.264. S.
It involves returning storage space in the output buffer of RAM to free space, so that this space can be reused for other buckets.

It is important to note here that the output message completion circular buffer and the input message circular buffer are separate from each other, so that these two circular buffers each have different PUT, GET, TOP, and B
That is, it is managed by each pointer of the OT. Depending on the configuration, both of these circular buffers could share the circular buffer management hardware 170, as shown in FIG.
Such a configuration is not mandatory.

Initialization Procedure Each processor module has a function of accessing the TN inside the high-speed random access memory 168 (FIG. 13) of the processor module itself, and this memory 168 potentially has this function. Contains the directory of available TNs. However, the unassigned TN is clearly displayed by the transaction number value stored in the storage location associated with the TN. Therefore, the microprocessor system 103
Identifies unassigned transaction numbers and selects one of them for use in initiating communication with other processor modules for a given transaction identity. be able to.

The transaction number is locally allocated and updated under the control of the local microprocessor (= microprocessor in the processor module), but global control throughout the network is
It is performed using the primary control messages "TN Relinquish Command" and "TN Assign Command". Multiple processors competing with each other that may require the same TN
Deadlock conditions never occur between modules because the network gives priority to the lower numbered processors. Of the processors that tried to obtain the TN, the remaining processors that did not get the priority are "NAK /
You will receive a "TN Error" response, which is an indication that the processors must try to reserve another TN. Thus, full flexibility is gained in ensuring and verifying their transaction identities both internally and locally in the system.

It should be noted that the repeated use of TN is "T
It is performed by shifting between a basic transmission mode which is "N0" and a merge mode in which TN is greater than zero. Therefore, this system can change not only the focus of its operation but also the nature of its operation by a single broadcast transmission of TN.

Yet another, and particularly useful, scheme for communicating changes in global status is the propagation of forced validity errors, which has already been described with reference to FIG. This unique display system, when sandwiched between other transmissions,
Suspended system resources will be investigated and appropriate action will be taken.

Processor-to-processor communication There are two special types of processor communication, one of which is communication to a specific one destination processor, and the other of which is a plurality of processors belonging to one class. This is communication performed as a transfer destination. Both of these types of transmission utilize DSW, and both of these transmissions are performed by broadcasting in non-merge mode.

In particular, when performing communication between one source processor and one transfer destination processor, the transfer destination processor identification information (destination processor identification information) is included in the DSW.
Ion: DPID) is used. This will be described with reference to FIG. 8. This DPID value is used to determine the H.264 signal of each receiving processor module. S. When the selection map portion of RAM 26 "is addressed, only the particular processor module intended as the destination will generate a positive response to accept the message. If successfully received, both processors are ready to perform any of the requested future operations.

When a message should be received by multiple processors belonging to a class related to a control process, the map nibble and map
H. S. The corresponding section in the selection map portion of RAM is designated. All receiving processors then send their own acknowledgments, which continue the competition for reaching the originating processor module until the round trip for this communication is finally completed. become.

Global-broadcast mode processor communication can be used to communicate each of the primary data messages, status messages, control messages, and response messages. The inherent capabilities of the priority protocol and the network with the ability to grant priority make it easy to insert such messages into sequences of other message types.

Hashing mode processor selection is by far the most widely used processor selection scheme when performing data processing tasks in relational database systems. Disjoint (= main data that is not for backup) primary data (=
Multiple data subsets (not sharing the same element) and disjoint data subsets of backup data are distributed to different secondary storage devices according to an appropriate algorithm. There is. A message about the primary data if two processors respond at the same time because one processor shares a subset of the primary data and another processor shares the subset of the backup data. Will be given priority. In order to compensate for this condition, a command code with a higher priority (see FIG. 12) may be selected. The reliability and integrity of the database can be maintained by using the various multiplexers mentioned above.
It is achieved by making use of the modes, in which case they are applied in the most advantageous way for the particular situation in which they occur. By way of example, if a secondary storage device that shares some subset of the primary data fails, then special processor-to-processor communication can be used to update it. Also, error correction and rollback of a part of the database can be performed in the same manner as this or by operating in class mode.
Can be done.

Transaction Number Example The concept of transaction number provides a new and powerful hardware mechanism for controlling microprocessor systems. In the present system, the transaction number constitutes a "global semaphore", and the transmission / reception of a message to / from the network and the confirmation of the readiness state of a given task distributed to a plurality of processors are performed. Each plays an important role.

The transaction number (TN) is H.264. S. RAM
It is physically implemented as a 16-bit word in 26. This word has various functions,
The format is as shown in FIG. TN
H. S. Since it is stored in RAM, it can be accessed by both the microprocessor 105 and the network interface 120.

Global Semaphore The term "semaphore" has become commonly used in computer science literature as a term to refer to variables used to control multiple processes that are executed asynchronously to each other. ing. Semaphores have the property that they can be "tested and set" in a single, uninterrupted operation.

As an example, "unassigned (UNASSIGNED: unassigned)" and "ASSIGNED:
Let us consider a semaphore variable that can take on two states, "allocated state". In this case, the test-and-set behavior is defined as follows: If the semaphore was in the "unassigned" state, set the semaphore to the "assigned" state and indicate success; Conversely, if the semaphore was already in the "Assigned" state, leave the semaphore in the "Assigned" state and display "Failure".
Therefore, with this semaphore, a process that successfully tests and sets the semaphore can continue its task, while a process that fails it resets the semaphore to the "unassigned" state. , Or try to test and set another semaphore that controls another resource of equality. It is easy to understand that if a test-and-set operation could be interrupted, it would be possible for two processes to access the same resource at the same time, which would There is a risk of producing erroneous results that cannot be done.

Any multiprocessor system actually embodies in hardware a concept that can be equated with a semaphore to control access to the system's resources. However, the conventional system can maintain only one copy of a semaphore (= a semaphore having one copy, that is, a semaphore provided at only one place). Therefore, if a plurality of copies of semaphores (= semaphores having a plurality of copies, that is, semaphores provided at a plurality of places) are provided and maintained for each processor, one copy at a time,
It is desirable both for the purpose of reducing the number of times a conflict occurs due to access of a semaphore that is merely tested, and for the purpose of using a polyvalent semaphore variable for other purposes described later. The problem is that you have to do a fully synchronized operation on multiple copies of the semaphore, and if this wasn't the case, there are semaphores to enhance it. , The integrity of access to resources will be lost.

Multiple copies of semaphores, or "global" semaphores, are provided by the system. The following table compares the behavior for global semaphores with single semaphores (one copy semaphore).

In the system of the present embodiment, the "TN assignment (ASSIGN T
The "N)" command and the "RELIN-QUISH TN" command are respectively responsible for the test and set function and the reset function for the transaction number used as a global semaphore. Referring to FIG. 12, the "NAK / TN error" response indicates failure while the "SACK / Assigned" response indicates success.

The characteristics of this network are the global semaphore, including the synchronous clocking scheme used to clock multiple nodes synchronously and the broadcast operation that transmits the highest priority packets to all processors simultaneously. It forms the basis for actually embodying the concept of. Because of the implementation of this concept, the system simply assigns TN to its resources, controlling its allocation, deallocation, and access of multiple copies of the desired system resource. You can do it by doing. What is important to note here is that distributed resource control can be performed with a small software overhead, which is almost the same as in the case of a single semaphore. This is a great advance over traditional systems because they either cannot manage distributed resources or require complex software prototyping and create a hardware bottleneck. This is because either of them will end up.

Readiness status "BUSY", "WAITING",
"READY" (preparation for sending and receiving), "DONE", and "non-participating processor (NON-P)"
ARTICIPANT) ", consisting of a set of values (see Fig. 12)
Provides the ability to quickly confirm the readiness status of a task given a TN. In this system, the meaning of each of the above states is shown in the following table.

The TN is assigned to the task dynamically by using the "TN allocation" command. Success indication ("T
"SACK / Assigned" for N-allocation "message
Response) is that all operational processors successfully
Indicates that the assignment of N to the task has been completed. It should be noted with respect to FIG. 11 that the “NAK / TN error” response has a high priority (small value), so that the network interface 1 of either processor
If 20 detects a collision on the use of TN, all processors will receive a failure response. Furthermore, the OPI of this failure response transmitted on the network
The D (source processor ID) field will indicate the first (lowest numbered) processor of the conflicting processors. This fact is used in diagnostic routines.

Each processor processes the task by the operation of the software, and the TN is “busy”, “waiting”, “ready for transmission”, “ready for reception”, “end”.
Or set to the appropriate one of the "non-participating processors". The first of any processor, including the processor that issued the "TN assignment", any time, "Status
By issuing the "request" command or the "merge start" command, it is possible to easily confirm the status of the completion of the task (TN).

A "status request" is the same as a single test of a multi-valued (= multi-valued) global semaphore. As can be seen in FIG. 11, the highest priority status response (SACK) message wins the race on the network, resulting in the lowest readiness state being displayed. In addition, the OPID field will indicate the identity of the first (least numbered) processor of the lowest readiness processors.

This latter property is used to provide a "non-busy" for "waiting" for completion of tasks distributed across multiple processors.
The form of "(non-bysy)" is defined. The processor that first issued the "TN allocation" is said to be the first "wait master". This processor then designates any other processor as the new "wait master" based on any criteria. This new "weight
The "master" interrogates all processors by issuing either a "merge start" or a "status request" when it has reached the desired readiness state. If all of the other processors were ready, SACK would indicate so. If some processors were not yet in the ready state, the OPID field of the SACK response would indicate the first of the lowest processors in readiness.
The "wait master" commands its processor to become the new "wait master". Eventually all processors will be ready, but in the meantime, this system will attempt to query the status every time at least one processor is notified that it is ready. Only. Therefore, the system is not burdened with periodic status inquiries that consume resources without producing results. Further, this scheme ensures that the system knows that all processors have completed their work at exactly the time the last completed process was completed. As will be appreciated by those skilled in the art, a wide variety of other "standby" configurations may be employed within the scope of the inventive concept.

The "start merge" command is one special type of test and set instruction. If the status of the global semaphore is "ready to send" or "ready to receive", the current transaction number register (PTNR) 206 (see FIG. 13) is "merge start".
It is set to the value of the transaction number in the message (see Figure 3), which sets the PTNR register. One of the working processors
When in a lower readiness state, the value of PTNR is unchanged.

The "merge stop" command is a reset operation corresponding to the above operation, and is a PT of all active processors.
The NR is unconditionally reset to "TN0".

As will be explained later, only the messages relating to the current global task specified by the PTNR are network interface 1
It is designed to be output from 20. Thus, the "merge start" and "merge stop" commands provide the ability to time multiplex or time multiplex the network between multiple tasks, and thus Tasks can be stopped and / or resumed at will.

An important feature of the detail of the present invention is that the network interface 120 ensures that the TN access by command from the network and the TN access by the microprocessor 105 are never simultaneous. is there. In this embodiment,
This is accomplished by a signal being sent from the receive status control circuit 260 to the read / write status control circuit 270, which has been processed for commands from the network that may change the TN. Whenever there is a "positive" state. This signal is "affirmative"
During a short period of time in the state, the processor is in H.264. S. R
Access to the AM is prohibited by the control circuit 270. As will be appreciated by those skilled in the art, a wide variety of alternative configurations to the above configurations may be employed within the scope of the present invention.

Receiving Control Another function of the TN is controlling incoming messages.
By using the "Assign TN" command, it is possible to associate input message streams in multiple processors for a given task. When the TN assigned to the task in a given processor is set to "ready to receive", the TN also includes a count value representing the number of packets the processor is willing to accept. It is displayed (12th
Figure). The network interface 120 decrements this count each time it successfully receives an individual packet (this decrementing is done by arithmetically subtracting "1" from the word in TN).
This decrement continues until this count reaches zero. When the count value reaches zero, "NA
A "CK / overrun" response is generated, which causes this NACK to the processor sending the packet.
It is signaled that the responding processor must wait until it is ready to accept more incoming packets. Furthermore, as can be seen from FIG.
At this time, the PTNR is also reset to "TN0".

With the above operation mechanism, the flow of packets flowing through the network can be directly controlled. It also ensures that one processor does not get overwhelmed with outstanding packets and that processor does not become a bottleneck to the system.

Transmission Control As shown in FIG. 21, as shown in FIG.
H. S. Each message stored in RAM is a new T
It contains a field for accommodating the value of the N vector (= next message vector). Once the message has been sent and the response to it has been successfully received, the new TN vector contained in the message just sent will be H.264. S. Current transaction in RAM
It is stored (transferred from the PTNR) at the address for storing the number. Therefore, it is possible to update the TN each time an individual message is sent, and to automatically set the TN to a desired state when the message is successfully transmitted. .

Referring to FIG. 12, the TN of “ready for transmission”
The format of H.264 is 14 bits. S. It contains an address in RAM, which is used to point to the next packet to output for a given task (TN). Therefore, H. S. The TN, which is stored in RAM, also serves as a head pointer to the head of a first in, first out (FIFO) queue of messages for various tasks.
Therefore, as far as one given task (TN) is concerned, each processor will attempt to send packets in the order defined by the chain of new TN vectors.

By combining with the mechanism described above for high speed multiplexing of the network between multiple TNs (tasks), it is possible to combine many sets of complexity distributed among many processors. Obviously, it will be possible to manage tasks with very small software overhead. The configuration provided by the co-operation of networks, interfaces and processors can distribute its copy among hundreds of processors, and even among thousands of processors. This is a suitable configuration for allocating and deallocating resources, suspending and resuming tasks, and other controls for resources and tasks that can be performed.

Example of DSW (transfer destination selection word) The transfer destination selection word (FIG. 3) is the DSW logic 190.
(FIG. 13) and H.I. S. DS of RAM26 (Fig. 8)
Working with the W section, it provides multiple modes that allow: That is, those modes determine whether the network interface 120 of each receiving processor is intended for the message being received to be processed by the microprocessor 105 associated with that network interface. There are multiple modes that allow you to make quick decisions. As described above, the DSW included in the received message is H.264. S. RA
The nibble stored in the DSW section of M is selected and compared to that nibble.

Processor Address As shown in FIG. S. RAM DSW
One part of the section is dedicated to the storage of processor address selection nibbles. In this system,
For each of the 1024 processors that can be installed,
H. S. Associated is one of the bit addresses contained in this portion of RAM. The bit of the bit address associated with the processor's ID is set to "1", while all other bits in this section are "0".
Has been Therefore, each processor has only one bit in this section set to "1".

Hash Map H. S. Another portion of the DSW section of RAM is devoted to hash map storage.
In this system, two of the map selection bits are devoted to their hash map,
It gives us two complete sets containing all 4096 possible values. Hashed mode
mode), the keys for the records stored in secondary storage are set according to the hashing algorithm, which results in a "bucket" assignment between 0 and 4095. The processor responsible for the records contained in a given "bucket"
The "1" bit is set in the map bits whose address corresponds to the bucket number of the bucket. The other bits are set to "0". A given processor can be responsible for multiple buckets simply by setting multiple map bits.

In the structure of this embodiment, as will be easily understood, the setting of the map bit can be performed by the following method. That is, the method is given 1
Regarding one map selection bit, each bit address is set to "1" in only one processor, and any bit address is always set to "1" in any processor. Is. As a direct result of adopting this scheme, each processor (AMP) shares a distinct and disjoint subset of the records in the database, yet the system as a whole contains a complete set of records. There is a large set.

Although the above specific examples are described by taking the problem of a relational database as an example, it will be easily understood by those skilled in the art that the disjoint subsets of the problems can be divided into individual parts in the multiprocessor complex. The same method can be applied to any task area that can be shared by the processors.

Yet another thing to note is that by providing two complete maps, the scheme described above can be used to map the buckets assigned to a given processor according to one map to the other map. Is that it can be configured to be assigned to a different processor. Where one map is "primary"
If the other map is "for backup", the direct consequence is to ensure that records that are primary on one given processor are backed up on another. Can be Furthermore, there are no restrictions on the number of processors that back up a given one processor.

As will be appreciated by those skilled in the art, the number of separate maps that can be implemented within the scope of the present invention can be three or more, and the number of buckets can be any number.

In both the case of the processor address and the hash map described above, if we examine the given one bit address for all processors, the bit
It can be seen that the address is set to "1" in only one processor and the corresponding bit address in all other processors is set to "0". However, a scheme in which the corresponding bit address is set to "1" in multiple processors is also possible and useful. This method is called "class address" mode.

A class address can be thought of as the name of a procedure or function whose copy exists in multiple processors. The "1" bit is set in the corresponding bit address of any processor having the corresponding processing procedure or function.

To send a message to a class address, the appropriate class address in DSW (Fig. 3) is set. H. S. All operational processors that are shown to "belong" to the class by having the bit in that location in RAM set to "1" will have their message bucket sent Will be responded with "ACK". Processors that do not belong to the class respond with NAP.

The DSW therefore allows the routing computations necessary to control the flow of messages in a multiprocessor system to be performed by the hardware. Also, the program can be independent of knowledge of in which processor the various functions of the system are provided. Furthermore, the map is H.264. S. R
Being part of the AM and thus accessible to the microprocessor 105, it is possible to dynamically relocate certain functions from one processor to another.

Merging Examples In complex multiprocessor systems, tasks may require the execution of a series of interrelated operations. This is especially true for relational database systems that deal with complex queries, where such data systems assemble the data into files and, after being assembled, use multiple methods in a particular way. It may be necessary to reference multiple secondary storage devices to form a file that can be redistributed to other processors. The examples below show the first, eighth, and first
3 briefly describes how the system of FIG. 3 can easily perform such functions by manipulating TNs, DSWs, and global semaphores. .

First of all, the merge coordinator (typically the merge coordinators are IFPs 14 to 16, but not necessarily limited thereto) will merge and form one file ( That is, it identifies (among the AMPs 18-23) a plurality of AMPs that belong to one class (which function as data sources). One unassigned TN is selected and assigned to identify the data source function. The second major function of distributing or hashing this file to another set of AMPs (which may be the processor of the original data source) was not assigned until then. Another TN
Are assigned.

The coordinator for this merge function is the first TN.
Using the DSW, a plurality of processors belonging to a class that will perform the merging work of the file related to the above are identified. The participating processors involved in this merging task raise the level of the status of their TN to a "busy" or "waiting" status, after which the control of the merge operation controls the participating processors involved in the merge operation. Handed over to one of them (ie the coordinator's work is delegated). Each of these multiple participating processors (all other processor modules are non-participating processors for that transaction) receives and affirms a message bucket for the task of the merge thus defined. After sending the response, execution of the subtask of the processor itself proceeds while appropriately updating its status level. Then, when a processor delegated to the task of the merge coordinator has completed its own task, that processor informs all other participating processors of the status of the transaction number. It is possible to send out a request and thereby receive a response indicating which of the participating processors has the lowest readiness state. Control of the merge operation is passed to the processor with the lowest readiness state,
After this, this processor will be able to bowl all other participating processors when it has finished its work. If desired, the above process can be continued until a response is received indicating that all participating processors are ready. The processor, which was acting as the coordinator at the time such a response was received, then proceeds to D
While identifying the participating processor belonging to the class using the SW, the H.S. S. The transfer of the message to the RAM 26 is started, and with the transfer of this message, the status level is updated to "ready for transmission" by the corresponding output message vector information. If subsequent boring reveals that all participating AMPs are ready for transmission, the coordinator issues a start merge command for that particular TN.

While the merge operation is being performed, the processed data buckets are forwarded to multiple processor modules belonging to a class for distributing the results to secondary storage according to a relational database. It will be. Regardless of whether or not the plurality of receiving processors are the same as the plurality of processors which are origins at this time, the participating processor (that is, the receiving processor) belonging to the class involved in this distribution is D
It is identified by SW and the transaction is identified by the new TN. All of the participating processors involved in this new transaction will be assigned this new TN, and those participating processors will raise their readiness state level to "ready to receive". become. This DSW
Can be hashing-selective rather than class-specified, but in either case, all participating processors must be in a state where they can receive broadcasted messages while the merge is in progress. It is set. When "merge start" is issued, multiple message packets are sent from each of the sending involved processors that should be involved in the sending operation, and simultaneously from the respective processors to each other on the network. On the other hand, the priority is dynamically determined (= during transmission). If each sending participating processor completes sending its own set of messages, then each of those sending participating processors has a defined "End of File". Attempts to send a message, this "end of file"
The message has a lower priority than the various data messages. This "end of file" message will continue to fail in contention with the data message until all of the participating processors have sent "end of file" messages, and sent by all participating processors. Finally, the transfer of the "end of file" message is achieved.
Once this transfer is achieved, the coordinator
An "End of Merge" message can be sent, followed by a "TN Abandon",
This "TN abandon" ends this transaction. Overrun conditions, error conditions, or lock conditions can be handled appropriately by redoing the merge or transmission from the beginning.

When the merge operation for one TN is completed,
This system uses the next next T in the sequence of TNs.
Can be shifted to N. Once each processor module has created a queue of message packets for this new TN, those processor modules will re-initiate the network to perform the merge operation. It becomes possible. Due to the efficient use of in-network merging operations in addition to the individually performed in-processor merging operations, this system is significantly superior to conventional systems and has a very large sort. /
You can now perform merge tasks. When the present invention is adopted, the time required to sort a certain file in the system can be expressed by the following formula, where n is the number of records and m is the number of processors. .

In this equation, C ₂ is a constant and for this example is estimated to be about 10 microseconds if 100 byte messages are used, and C ₁ is a typical 16-bit microprocessor. Is a constant estimated to be about 1 millisecond when is used. Rough sources for various combinations of n and m
The merge times are shown in seconds in the table below,
Those values are the values when 100 byte records are used.

It is not easy to evaluate the numbers of the specific examples shown in the above table in comparison with the conventional system. The reason is that two kinds of sort processing sequences (sort by processor and sort by network) which are related to each other are involved, and in the first place, there is almost no system having such capability. Because. Furthermore, in this system, messages whose length is long and variable are sorted and merged.
In general, many sort capabilities are evaluated in terms of bytes or words.

Another important factor is that the system is a multiprocessor itself and not a dedicated system for sort / merge processing. The system is capable of local and global shifts with full flexibility between merge and non-merge operations, and this shift causes software disadvantages. And without loss of system efficiency.

Example Task Request / Task Response Cycle Referring to FIG. 1, any processor 14, 16, or 18-23 connected to the network 50 may cause another processor or processors to perform the task. Of the task request is formed in an appropriate format in the form of a message packet. In a relational database system, most of these tasks are host computer 1
The source is 0, 12 and is input into the system through the interface processors 14, 16, but this is not a requirement. This message packet, formed in the proper format, is thrown into a race on the network that is contended with packets from other processors, and the priority level of other tasks as well as the operating status on this processor. Depending on your level, you will sometimes get priority. A task may have its contents specified by one message packet, or may be specified by multiple continuation packets, but the continuation packet that follows is a group of data messages (11th (See figure), a relatively high priority level is assigned, so that the delay in receiving the following parts is as short as possible.

The message packet contains a transaction identity (= transaction identification information) in the form of a transaction number. This transaction number is a non-merge mode, ie, a default mode (“TN0”), which is a mode-related mode for extracting the processing result, and a merge mode (“TN”).
It is inherently provided with the property of distinguishing all TNs other than 0 "according to the selection. In addition, the message packet contains the DSW. The DSW substantially designates a transfer destination processor and a mode of multiprocessor operation. This designation is designation of a specific processor, designation of a class composed of a plurality of processors,
Alternatively, the hashing is performed by specifying the hashing, and in the present embodiment, the hashing is a hashing to a part of the relational database. The message packet broadcast to the target processor (designated destination processor) via the network 50 is
It is locally accepted at the processor (= the processor determines that it is appropriate to accept itself), and the reception is authenticated by an acknowledgment (ACK). All of the processors 14, 16 and 18-23 are EOM
Following (end of message), the ACKs sent by the designated destination processor are sent to the network 50 simultaneously, but the ACK sent by the designated destination processor gets priority and is received by the originating processor. It will be.

Subsequently, the designated transfer destination processor determines that the received message is a local H.264 message. S. This request packet (when transferred to the local microprocessor via the RAM (= HSRAM provided in each processor module) and the interface 120 (FIGS. 8 and 13). The process requested by the (sent message) is executed asynchronously (= out of synchronization with elements other than the processor module in question). When tasks related to relational databases are performed,
The DSW typically specifies a portion of a disjoint data subset (which is stored on the disk drive for that subset), but sometimes it is Sometimes tasks are performed that do not require browsing the existing database. A specific operation or algorithm may be executed by each processor, and when multiple processors are designated as designated transfer destination processors, each of those processors is a disjoint subset of the entire task. About to be able to do the job. The variable length message packet is configured so that the request message can specify the operation to be executed and the file to be referred to in the database system. It is important to note here that there may be a large number of message packets for a given task, in which case the discrimination for sorting done inside the network. Keys that can be arbitrarily adopted in order to give appropriate characteristics as a reference
It means that the field (Fig. 3) becomes important.

The task response packet generated by each processor attempting to respond is
Local H.264 via the control logic 28 of FIG. S. RAM
26, where the task response packet is stored in the outgoing message format of Figure 21A. If the task response is one that requires the use of a continuation packet, then such a continuation packet is sent after the first packet, but given a higher priority for continuation. It If the system is operating in merge mode and each processor is generating a large number of packets for a transaction number, those packets are first locally (= It can be chained in sort order (internally) and then merged on the network 50 to put them in global sort order.

The task result packet is sent to the processors 14, 16 and 18
~ 23 to the network 50 to form a group of packets to be sent simultaneously, and one high priority message
Packets are broadcast back to all processors after a certain network delay. Depending on the nature of the task, the transfer of these task result packets may be performed with the source processor that first issued the request message as its transfer destination, and one or more other processors. May be performed as the transfer destination, and further, the transfer can be performed in any of the plurality of multiprocessor modes described above. The most common case in relational database systems is to use hashing to select destinations,
The merge and the redistribution are executed at the same time.
Therefore, as can be understood from that, in the cycle of "task request / task response", each processor acts as a source processor, a coordinator processor, and a responding processor. It is also possible to operate as a combination of all three. Due to the involvement of many "task request / task response" cycles, the processors 14, 16 and 18-23 and the network 50 are multiplexed (multiplexed) between their tasks, This multiplexing is done on a time basis and also on a priority basis.

Complex Query Example In a relational database system,
Utilizing the host computers 10, 12, and further, the relational database is stored in a plurality of disk drives 38-38 according to an algorithm that defines tuples and disjoint data subsets of primary and backup data. A complex query is entered from the host computer 10 or 12 via the IFP 14 or 16 into the system using a distribution method adapted to distribute among 43. This input inquiry message packet is first sent to the IFP 14 or 16
Parsed in detail by this analysis, which is performed to convert a message from the host computer into a plurality of task requests for requesting the AMPs 18 to 23 to execute the task. IFP1
4-16, when initiating its operation, sends out a request packet to retrieve information from one or more specific AMPs, whereby the host
It may be necessary to obtain the in-system data needed for detailed analysis of the message from the computer. When the data necessary for processing the request from the host computer is obtained, the IFPs 14 to 16 send the AMP 18 to
It is possible to perform several "task request / task response" cycles to and from 23 and to actually process the data to satisfy the request from the host computer. In the above processing sequence, the cycle composed of the task request and the task response mentioned above is used, and the cycle can be continued for an arbitrary length. Then IF
P14-16 communicate with the host computer via the IFP interface. This response to the host computer may simply be to provide the data that the host computer 10 or 12 needs to generate the next complex query.

Independent Multiprocessor System The basic embodiment of the system according to the invention described above in connection with FIG. 1 is combined with a host computer as well as a software package for the host computer currently in use. It shows an example of a post-processor (back-end processor) that can be used. However, as already mentioned, the present invention finds application in a wide variety of processing applications, and in particular in those types of processing applications where processing tasks can be easily subdivided and distributed without the need for large central processing capabilities. , With special advantages. FIG. 20 shows an embodiment of a simple configuration of a stand-alone type multiprocessor system according to the present invention. 20th
In the figure, a plurality of processors 300 are all connected to an active logic network 304 via an interface 302, which is a network similar to that already described. An active logic network 304 with redundancy may be employed to enhance data integrity. In this embodiment as well, processor 300 can use a 16-bit microprocessor chip, and
A main RAM memory having a sufficient capacity can be incorporated. This figure shows nine processors 300
Are shown, and different types of peripherals are connected to each of those processors, to show the versatility of the system. In practice, this system would be much more efficient by having more processors in the network, however, even with relatively few processors, system reliability and It offers particular advantages in terms of data integrity.

In this embodiment, multiple processors 300 may be physically separated from each other by a sufficient distance that is not inconvenient, which may occur if the data transfer rate is the speed described in the previous embodiment. The maximum interval between is 28
Since it will be a foot (5.5 m), a large array of multiple processors can be installed on one floor of a building or on several adjacent floors so that it will not be crowded. This is because it can be used.

In a stand-alone system, far more varieties are used for the peripheral controller as well as the peripheral itself, as compared to the post processor embodiment described above. Here, for convenience, each input / output device is assumed to be connected to a separate processor.
For example, the input / output terminal device 310 including the keyboard 312 and the display 314 is a terminal controller 320.
Via the processor 300 for the terminal device 310
It is connected to the. However, in the case of a terminal device operating at a relatively low speed, it is not impossible to control a terminal network of a considerable size with a single 16-bit processor. The illustrated input / output terminal device is merely an example of how a manually operated input processing device such as a manually operated keyboard is connected to the system. The processing power of the processor 300 can be used to configure the terminal device 310 as a word processor, and the word processor can be used for data base or other word processor via the network 304.
Alternatively, it may be possible to communicate with various output devices. A large capacity secondary storage device, such as a rigid disk drive 322, for example, may be connected via the disk controller 324 to the processor for that storage device. Also, as will be readily appreciated, larger systems may use more disk drives or different forms of mass storage. Output devices such as printer 326 and plotter 330 interface via printer controller 328 and plotter controller 332 to processor 300 for those output devices, respectively. Interactions with other systems not shown occur via communication controller 338 and via communication system 336, which may be, for example, a teletype network (TTY), or even a larger system. One of the networks (eg Ethernet (E
thernet)) and the like are used. Some of the processors 300 may simply be connected to the network 304 without connecting peripherals (not shown).

Bidirectional data transfer may occur in the tape drive (tape drive) 340 and the tape drive.
If the drive controller 342 is used,
For example, when the floppy disk drive 344 to which the controller 346 is connected is used. In general, tape drives not only provide a large storage capacity when used while connected online,
It can also be used to back up disk drives. For the purpose of this backup, tape is used to store data stored up to a point in a sealed rigid disk drive. Such backup operations are typically performed during periods of low load (eg, nights or weekends), thus allowing long “streaming” transfers using network 304. In addition, the floppy disk drive 344 may be used for program input during system initialization, so that some of the network usage time will be spent in this "streaming" mode. It can also transfer a considerable amount of data. The optical character reader 350 functions as a source of further input data, and the input data is input to the system via the controller 352. In addition, the peripheral device simply described as “another device 354” is connected to the system through the controller 356,
It is possible to perform other functions as needed.

Each message from a separate processor module
Packets are sent simultaneously to each other, and priority determination is performed on those message packets so that one or a common top priority message packet is simultaneously sent to all processor modules within a predetermined fixed time. The use of a broadcasted scheme ensures that any individual processor that is online has equal access to the other processor modules in the system. This global semaphore system, which utilizes prioritized transaction number and readiness status indications and destination selection entries contained in the message, allows any processor to act as a controller. Therefore, the system can operate in a hierarchical manner and a non-hierarchical manner. It is also very important that the system can be scaled up or down without requiring software scrutiny or modification.

Even if access is required to a message that is significantly longer than the message length already described, but is still of relatively limited length, such access can be performed. For example, for complex computer graphics devices (not shown), where it is necessary to access only certain parts of a vast database to create sophisticated 2D and 3D graphics. There is. Also, with word processor systems, only a small sequence of data may be needed at a time from the database due to the slow operation speed of the operator. In these situations, and similar situations, the system's ability to handle variable length messages, as well as the ability to grant continuous message priority, would be beneficial. The situations that require intensive processing power and the transmission of extremely long messages limit the use of this system, but in other situations, the system works very well. To do.
The dynamic situations involving the manipulation of various different data formats and the associated sorting or merging functions all correspond to situations in which the present invention can be used to advantage. Business decision making, which involves collecting, collating, and analyzing complex data, is an example of such a situation, and also the creation and biasing of video and graphic inputs for periodicals, This is an example.

(Conclusion) As will be apparent to those skilled in the art, the system of FIG. 1 does not require any software modification and can include any number of processors (provided that it is determined by the data transfer capacity). It can be extended (up to the practical limit). Furthermore, it is also clear that the system shown in the figure is for confirming the status of each processing device, setting the priority of the tax and the processor, and ensuring the efficient use of the processing capacity of the processor. It significantly reduces the need for management and overhead software.

The obvious benefits are database systems and other systems where, like database systems, it is appropriate to subdivide an entire task into multiple subtasks that can be processed independently of each other. And so on. For example, in relation to relational databases, even if the capacity of secondary storage devices increases significantly, it is only necessary to properly integrate additional databases into the data structure of primary and backup data. is there. In other words, the network can be expanded infinitely, which is possible because standardized intersection devices or nodes are connected by a binary evolving connection method. This is because the functions executed in those individual nodes do not change due to expansion. Furthermore, a setting processing sequence for the operation of the node and external control are unnecessary. Therefore, when the system according to the present invention is connected to function as a back-end processor for one or more host computers, as shown in FIG. Arbitrarily expand (or shrink) the database without changing operating system software or application software
can do. Host processor system (=
From the point of view of the host computer, this back-end processor is "transparent" regardless of its configuration, because this back-end processor and host This is because there is no change in the manner of interaction with the processor system. This backend processor has another host
To switch to work for the processor system, one simply needs to have the IFP properly talk to the channel or bus of the new host processor system.

According to the configuration of the network in a specific example of a real machine, there is no significant delay in message transfer in the network, and there is no inadequate delay due to contention between processors.
Up to four microprocessors can be included and used. It will be apparent to those skilled in the art how to extend the embodiments described herein to include more than 1024 processors. When 1024 processors are used in one system, it is known that the maximum line length between active nodes is 28 feet in the concrete example of the actual machine, and this line length is useful for constructing an array. There is no problem. The total length of the garden caused by the network is a constant time 2τN for any message, where τ
Is the byte clock interval, and N is the number of layers in the hierarchical structure. Obviously, doubling the number of processors by adding one more layer will only increase latency slightly. Since data messages are inevitably long messages (about 200 bytes long), the determination of priority for all competing messages involves transferring the data along the network. Since this is done while the network is in progress, the data message transfer is much more efficient than conventional systems.

Among the important economic and operational features of the system are the fact that standardized active logic circuits are used in place of software, and even firmware in network systems. There is a feature. That is, due to this fact, it is possible to incorporate a highly reliable circuit at a relatively low cost with respect to the total cost including the cost of the processor and the cost of the peripheral device by using the technology of modern LSI and VLSI. It is possible to do.

The only time software has to spend time and money is on the critical parts, such as those involved in problem domain tasks such as database management. For example, the configuration of the system allows all the functions necessary for maintaining the integrity of the database to be performed within the range based on the configuration of the message packet and the configuration of the network. ing. Functions such as polling, status change, and data recovery are performed inside the system.

Yet another important consideration is that the network of the present invention is such that its high speed data transfer performance is sufficiently comparable to conventional ohmic wiring buses. Since multiple message packets are sent simultaneously to each other and priority is determined while they are being transmitted, the status request and the response to it are sent in the conventional method, and the priority is determined. This is because the delay that had been avoided has been avoided.
Furthermore, even if the number of processors is enormous, the length of the connection structure between nodes can be suppressed to a predetermined length or less, so that the propagation time in the bus is a constraint on the data transfer rate. Never.

The system has been found to be optimal in terms of microprocessor and network utilization. The important thing about these points is that
Keeping all microprocessors busy and ensuring that the network is fully utilized. "IFP-Network-AM
The configuration of "P" effectively allows them,
The reason for this is that a microprocessor whose message packet it has sent out in contention for priority wins only needs to try again at an appropriate time as soon as possible, which results in a high bus duty cycle level. Because it is maintained at. Fast Random Access Memory also contributes to this effect, because it has both internal message packets to process and outgoing message packets to send. This is because each processor can always obtain a backlog of work, and the network can also obtain a backlog of message packets. When all input buffers are full, the processor sends an indication on the network indicating that fact. Also, if the input buffer used by the IFP for receiving messages from the host computer is full, an indication is sent out on the channel to indicate this. Therefore, the system is self-starting both internally and externally.

By utilizing the architecture and message organization as described above, the system is also configured to perform many other functions required by a general purpose multiprocessor system. For example, in the prior art, great attention was paid to schemes for assessing and monitoring changes in the status of global resources. In contrast, in accordance with the present invention, only the parity channel is provided and used as a means of communicating both the occurrence of parity errors and the fact of changing processor availability. If one or more processors shut down, the shut down is propagated into the system at about the same time that it occurs, thereby allowing the execution of the interrupt sequence to begin. There is. Since a method of sorting multiple responses according to priority is adopted,
When a change in global capability occurs, it becomes possible to identify what kind of property the change is by a circuit and system overhead that are much smaller than conventional ones. There is.

The global response, which is achieved by adopting the global semaphore and the active logic network and obtained through the priority determination by one inquiry, has a very deep systematic meaning. By broadcasting a query in this way, unambiguous, unambiguous global results are obtained, thus eliminating the need for complex software and overhead. A status setting operation such as distributed update can be executed even when many simultaneous operations are executed by a plurality of different processors.

Further, the present system exerts an excellent ability regarding work distribution and processing result collection in a multiprocessor system by using the above network, transaction number and transfer destination selection word. Different multiprocessor modes and control messages are available, and different levels of priority can be easily set and changed by simply manipulating the priority protocol. . The combination of the ability to broadcast to all processors at the same time, and the ability to sort messages in a network, allows the forwarding of any processor group or any individual processor. It is also possible to pull out the processing results in an appropriate order. Therefore,
When a complex query to a relational database system is entered, it initiates any processing sequence required for database operation.

Yet another advantage of this system is that it can be used in multiprocessor systems such as relational database systems.
Redundancy can be easily introduced. Having a dual network and dual interfaces provides redundancy so that the system can continue to operate if one network fails for any reason. Since the databases are distributed in disjoint temporary and backup subsets, the probability of data loss is reduced to a minimum level. In the event of a failure or modification, the versatility of the control functions are available to maintain the integrity of the database.

[Brief description of drawings]

FIG. 1 is a block diagram of a system according to the present invention including a novel bidirectional network. 2 and 2A to 2J show a continuous series over time showing the manner of transmission of data and control signals in the network of the embodiment of the simple structure shown in FIG. FIG. 2 is a diagram showing a state before the start of signal transmission, and FIGS. 2A to 2J show 10 consecutive states from t = 0 to t = 9, respectively.
It is a figure corresponding to one of the time samples at the time point of a place. FIG. 3 is an explanatory diagram illustrating the structure of a message packet adopted in the system shown in FIG. FIG. 4 is a block diagram showing a further detailed structure of the novel bidirectional network shown in FIG. 1 relating to the active logic nodes and clock circuits used in the network. FIG. 5 is a state diagram showing various operating states within the active logic node. FIG. 6 is a timing diagram for explaining an end-of-message detection operation performed inside the active logic node. FIG. 7 is a timing waveform diagram for explaining the operation of the clock circuit shown in FIG. FIG. 8 is a block diagram of a processor module including high speed random access memory that may be used in the system shown in FIG. FIG. 9 is a diagram showing an internal address allocation state of the main RAM of the microprocessor system shown in FIG. FIG. 10 is a block diagram showing the arrangement of data inside one reference portion of the high speed random access memory shown in FIG. FIG. 11 is a chart showing a message priority protocol used in the system. FIG. 12 is an explanatory diagram illustrating the word format of the transaction number. 13 and 13A are block diagrams of the interface circuit used in each processor module provided in the system shown in FIGS. 1 and 8, and the right side of FIG. FIG. 13B is a diagram in which FIG. FIG. 14 is a timing diagram illustrating various clock and phase waveforms used in the interface circuit of FIG. FIG. 15 is a block diagram illustrating further details of the memory structure and one mapping method for performing mapping based on the transfer destination selection word. FIG. 16 is a simplified flow chart showing changes in status upon receipt of an input data message. FIGS. 17 and 17A are flowcharts showing changes in status when a message is being received, and are diagrams in which FIG. 17 is connected to the upper edge of FIG. Is. FIG. 18 illustrates the relationship between various primary messages and the various responses that are generated to them, as well as the relationship between the various primary messages and the actions performed in response to them. It is a table shown. 19 and 19A are flow charts showing changes in status when a message is being transmitted, and a diagram in which FIG. 19 is arranged in contact with the upper edge of FIG. Is. FIG. 20 is a block diagram of a stand-alone type system according to the present invention. FIG. 21 is composed of FIGS. 21A and 21B and is a diagram showing a message stored in the high speed random access memory. FIG. 22 is a simplified schematic diagram showing one possible distribution scheme for distributing portions of a database among different processors in a database system. 10, 12 ... Host computer, 14, 16 ... Interface processor, 18-23 ... Access module processor, 24 ... Microprocessor, 26 ... High speed random access memory, 28 ... Control logic , 32 ... Disk controller, 38-43 ... Disk drive, 50 ... Active logic network structure, 54 ... Node, 56 ... Clock source, 120, 120 '... Network interface, 103 ... … Microprocessor system.

 ─────────────────────────────────────────────────── ─── Continuation of the front page (72) Inventor Martin Kyameron Watson United States North Lithuania Cabriol Avenyu 11112 California (U.S.A.) 11112 (72) Inventor David Kronshio 5635 (72) Inventor Trans Towers Street, Calif. Jack Everd Siemer 270 Los Angeles Oceano Drive, California, United States

Claims (6)

[Claims] 1. A bidirectional branch node circuit for a network system receiving a plurality of messages that are simultaneously sent to each other and competing with each other, wherein the bidirectional upstream port circuit and two bidirectional downstream port circuits. And each of the port circuits includes a parallel data line and a collision line, and comprises logic means connected to the downstream port circuit, the logic means at the downstream port. To forward one of the two competing upstream messages received to an upstream port by prioritizing it according to a predetermined priority convention defined by the contents of those messages. Means for connecting the upstream port circuit and the downstream port circuit and receiving a message at the upstream port. In response to the transmission of the message to both downstream ports, comprising the logic means, the upstream port circuit, and the control means connected to the downstream port circuit, the control means, In response to granting priority between two upstream messages, the defeated collision line sends a signal indicating that the message not received by the port has been granted priority. A node circuit, which is a means for doing so and also for transferring the signal received on the collision line of the upstream port of this node circuit. 2. Each of said port circuits includes a clock line for input to said port circuit and a clock line for output from said port circuit, said node circuit further comprising their clocks. A node circuit as claimed in claim 1, including clock timing means connected to the line. 3. Each of the logic means sets a transmission path through the logic means to one of two possible states in response to a priority selection made in the logic means. A node circuit according to claim 2 including means for: 4. The node circuit of claim 3, further including means for resetting the logic means to an initial state in which there are two possible transmission paths. 5. The node circuit of claim 2 wherein said control means further comprises means for resetting said control means in response to the end of the message. 6. The node circuit includes, for each of its ports, a plurality of upstream and downstream data lines and at least one parity line, and said upstream port collision·
A node circuit according to claim 5, wherein a line is connected to reset said control means upon termination of a collision signal from said upstream port.