System for resolving memory access conflicts among processors and minimizing processor waiting times for access to memory by comparing w

What is claimed is:

1. In combination,

a plurality of processors,

a corresponding plurality of logic circuits,

at least one memory device,

a bus connecting each of said processors with said memory device,

a request line from each of said processors to one of said corresponding plurality of logic circuits for making thereover a memory device use request,

a memory status bus connecting said memory device with each of said logic circuits for simultaneous signalling thereto whether said memory device is available,

waiting time measuring means within each of said corresponding plurality of logic circuits for signalling the length of time a respective processor has been waiting,

a waiting time bus for applying to all said logic circuits the longest available processor waiting time,

comparator means in each said logic circuit to compare the waiting time of its respective processor with that on said waiting time bus,

means in each said logic circuit to provide a rank signal different from that in each other logic circuit to break ties, and

means to cause functioning of said logic circuits within coincident periods of time,

each logic circuit being adapted to connect its respective processor to said memory device when there is coincidence of a request for said memory device by said respective processor over a respective request line, an availability signal over said memory bus, and its waiting time line signal is equal to the signal of said waiting time bus and one of greater than any other waiting time line signal or equal to the largest other waiting time line signal and of higher rank signal, whereby no processor can reach said memory device twice before another that interveningly has requested it reaches it once, to minimize maximum waiting time.

2. The combination of claim 1 wherein when a said logic circuit has determined that its processor is ready to be connected to said memory device, it emits a disabling signal to the logic circuits of lower rank, said combination further comprising means connected to said logic circuits for communicating said disabling signal to said logic circuits of lower rank, said means to provide a rank signal including disabling output and disabling input connections for said logic circuits for respectively emitting and receiving said disabling signal, the logic circuit of highest rank having no such disabling input connections, the logic circuit of lowest rank having no such disabling output connection, and the logic circuits of decreasing rank having correspondingly increasing numbers of disabling input connections, corresponding to the logic circuits of higher rank, and means in each said logic circuit for disabling said circuit upon receipt of said disabling signal at a disabling input connection.

3. The combination of claim 2 further comprising means for providing a constant dummy logic value, said value being of opposite sense from that of said disabling signal, said means to provide a rank signal including enabling input connections for said logic circuits for receiving said dummy logic value, the sum of said enabling and disabling input connections for each said logic circuit being equal to said sum for any other logic circuit, the logic circuit of lowest rank thereby having no such enabling input connections, and the logic circuits of increasing rank having correspondingly increasing numbers of enabling input connections.

4. The combination of claim 1 wherein said means to cause functioning of said logic circuits within coincident periods of time is a clock.

5. The combination of claim 1 further including in each said logic circuit means for disabling the respective logic circuit when its said comparator means shows that the waiting time bus signal exceeds its waiting time line signal.

6. The combination of claim 5 wherein each logic circuit includes a shift register, means to maintain said shift register clear during intervals when said logic circuit's corresponding processor is not making a memory device use request, means to accumulate in said shift register a set of consecutive ones corresponding to the number of periods of time said processor has been making said memory device use request, and means to apply during each of said periods of time said set of ones to corresponding inputs to said waiting time bus, whereby the highest order one on said waiting time bus represents the longest waiting time of any processor.

7. The combination of claim 6 wherein said waiting time bus comprises a plurality of waiting time bus lines and each stage of each shift register is respectively connected to one of said waiting time bus lines by means of a first logic device implementing the wired OR function, whereby a logical true in any such stage forces the corresponding value to appear on its respective waiting time bus line regardless of the value of any other input to said waiting time bus line.

8. The combination of claim 7 wherein each said first logic device is an open collector NAND gate having as one input a stage of said shift register and as the other input said memory availability signal from said memory status bus.

9. The combination of claim 8 wherein said comparator means has as a first set of inputs the stages of said shift register and as a second set of inputs the corresponding lines of said waiting time bus and emits an enabling comparison signal when and only when there is identity in the two sets of inputs.

10. The combination of claim 9 including a second logic device in each said logic circuit, said second logic device having a third set of inputs comprising said comparison signal, said memory availability signal, and a set of signals from higher ranked logic circuits representing that no higher ranked circuit is tied, said second logic device emitting a bus grant signal when all the inputs of said third set are enabling.

11. The combination of claim 10 further comprising means for applying said bus grant signal to lower ranked logic circuits for disabling corresponding second logic devices in said lower ranked logic circuits.

12. The combination of claim 1 wherein there are a plurality of memory devices, said bus connecting each of said processors with each of said memory devices is an address/data bus for carrying memory device address request information and data, there are a plurality of lines connecting each processor to said address/data bus, some of said lines carrying memory device address request information and others carrying data, said memory status bus comprises a plurality of lines, and there are means defining the address of each of said memory devices on an interleaved basis modulo n where n is a number equal to or greater than the number of said memory devices, each of said logic circuits has a data selector having as inputs the lines of said memory status bus and selected lines connecting said processor to said address/data bus and carrying memory device address request information, those lines selected being the lowest significant lines of the lines carrying the memory device address requested by the said respective processor to give the modulo n value of the requested address, said data selector producing a memory available enabling signal when said modulo n value corresponds to a memory status bus line giving an availability signal.

13. The combination of claim 12 further comprising a bus grant output device in each said logic circuit and wherein the output of said data selector is connected as an enabling signal to said bus grant output device.

14. The combination of claim 12 wherein each logic circuit includes a waiting time shift register, and a memory device use request signal from said processor, when said processor has a data transfer requirement, is connected as a start signal of said waiting time shift register.

15. The combination of claim 12 further comprising an input-output bus for connection to a multiplicity of real time data ports and connectable via a selected processor to said address/data bus, said logic circuits speeding the processing of data to enable real time operation without interruption.

16. The combination of claim 1 wherein said bus connecting each of said processors with said memory device is an address/data bus, said combination further comprises an input/output bus for connecting said processors to a plurality of data ports, said data ports communicate with said memory device through said processors, said combination is of modular construction, said processors are processor modules, and said modular construction enables change in the number of processor modules to conform said combination to the level of data traffic at the point of use, each said logic circuit determining for its processor module when access can be had to said address/data bus for the purposes of transferring a character of data between a data port and said memory device and performing functions ancillary thereto, and a first wiring system interconnecting said memory device and the processor modules to enable function of said logic circuits, said first wiring system including said memory status bus and said waiting time bus.

17. The combination of claim 16 including means for receiving an additional processor module and a second, priority wiring system automatically connected to an additional processor module by insertion of said module, to provide priority interconnection from said additional processor module to the rest of said processor modules, with disabling input connections from any processor module of higher rank signal and a disabling output connection to any processor module of lower rank signal.

18. The combination of claim 17 wherein said means for receiving comprises a plurality of processor positions into which said processor modules with their respective logic circuits may be inserted, each logic circuit having a set of input connections corresponding to one less than the maximum number of processor modules that can be inserted into said processor positions, said second, priority wiring system applying a permanent enabling value to all of said input connections to the logic circuit of highest rank and descendingly fewer of said input connections for logic circuits of correspondingly descending rank, each logic circuit producing a bus grant signal when it has determined that its processor module is ready to be connected to said memory device, said second, priority wiring system connecting the disabling output connection of each logic circuit to a respective disabling input connection of each logic circuit of lower rank, disabling means in each logic circuit to disable said circuit upon receipt of a said bus grant signal from any logic circuit of higher rank, and when a processor module is absent from its said processor position, said second, priority wiring system applies a permanent enabling value to the lower ranked logic circuits' input connections that were connected to the disabling output connection of the absent processor module whereby insertion or removal of a processor module into or from its processor position automatically enters or removes the processor module from contention for access to said memory device.

19. The combination of claim 18 further comprising means for enabling any additional processor module inserted into a processor position to automatically connect its logic circuit to said waiting time bus.

20. The combination of claim 19 wherein said waiting time bus is automatically connected to receive a waiting time line signal from and deliver the waiting time bus signal to any additional processor module upon insertion of said processor module into a said processor position.

21. The combination of claim 18 further comprising means for enabling any additional processor module inserted into a said processor position to automatically connect its logic circuit to said memory status bus.

22. The combination of claim 16 wherein there are a plurality of memory devices, said memory devices are memory modules, said memory status bus comprises a plurality of memory status bus lines, and said memory modules allocate all of said memory status bus lines among themselves.

23. The combination of claim 22 further comprising wiring means and means on said memory modules engageable therewith for causing each memory module to sense the presence and location of additional memory modules in said combination, and responsive thereto to assign to themselves respective memory status bus lines.

24. The combination of claim 23 further comprising logic devices on each of said memory modules responsive to the presence and location of additional memory modules to automatically assign to themselves a range of addresses.

25. The combination of claim 16 wherein said memory device has two data memory resources, there are four memory status bus lines communicating to said logic circuits, and two of said memory status bus lines are assigned to each memory resource, both signalling busy to the requesting logic circuit when the respective memory resource is busy.

26. The combination of claim 25 wherein said memory device is a memory module, a second said memory module is inserted into said combination, and insertion of said second memory module causes allocation of one memory status bus line associated with each memory resource of the first memory module to a respective resource of the second module, and said memory modules include means for sensing the position of each other and for selecting particular memory status bus lines in accordance with the relative position of said memory modules.

27. The combination of claim 26 wherein said memory modules include means to shift themselves from a modulo 2 interleave address mode of operation when only one memory module is present to a modulo 4 interleave address mode of operation when two memory modules are present, said logic circuits being unaffected thereby.

28. The combination of claim 22 wherein insertion of an additional memory module is effective to connect it to a memory status bus line to which another memory module is assigned, said two memory modules thereby effectively constituting a single independent memory for the function of said logic circuits.

29. The combination of claim 12 wherein said processors are processor modules and further comprising means for enabling any additional processor module inserted in said combination to automatically connect to said memory status bus to enable production of said memory available enabling signal in response to a memory device address requested by said additional processor module.

30. The combination of claim 29 further including means on each of said memory devices for causing each of said devices to sense the presence and location of additional memory devices in said combination, and responsive thereto to assign to itself a respective memory status bus line.

31. The combination of claim 22 wherein each of said memory modules includes means to shift itself from a first to a second address mode of operation in response to the presence of another of said memory modules, said second mode being an interleave mode.

32. The combination of claim 31 wherein each of said memory modules has two data memory resources, each of said memory modules includes means to shift itself from a modulo (2) interleave address mode in which successively addressed data words are allocated to said two memory resources on each of said modules to a modulo (4) interleave mode shared with another of such memory modules, in the manner that in the set of four successive addresses, two are directed to each of said modules.

Description Submit all comments and votes

BACKGROUND OF THE INVENTION

This invention relates to a bus allocation system for a computer that has multiple processors and a common set of independent memory resources accessed by all of the processors over a common bus, to a data network processor unit which utilizes such a system to meet various needs of a data network, and to a modularized unit which enables ready expansion of the processor and memory capabilities, e.g., to tailor the unit to the level of traffic encountered at a particular data network node to which the unit is assigned.

SUMMARY OF THE INVENTION

The invention employs the combination of distributed contention logic, enabling use of identical logic on each contending module; parallel contention for fast priority resolution and bus allocation; contention based on availability of requested system resources; and contention based on priority that is a function of waiting time. The invention also employs memory modules which resolve among themselves the nature of the interleaving to be employed and the assignment of memory busy lines which communicate with the contention logic, all in a manner which requires no change to the contention logic.

Among the benefits achievable by use of the invention are no wasted bus cycles if any module is requesting any available resource; equal servicing with no lock-outs possible (FIFO); very fast contention resolution due to parallelism that does not require "daisy" chain selection; and use of simplified hardware mechanisms that are distributed on each processor and memory module, with no straps, etc. or centralized control required.

According to the invention, for use in a computer or data communications processor unit comprising multiple processors and a common set of independent memory resources accessed by all of the processors over a common bus, and controlled by a common clock, a logic circuitry is provided for allocating the processors to the individual memory resources which comprises a set of individual contention logic circuits, one associated with each processor, enabling all to operate in parallel time, to be combinatoric in nature and to require no sequential states of operation, or logic signals sequentially propagated through the set of logic circuits, and, in their joint functioning enabling one allocation per clock interval. The individual contention circuit for each processor features: input from each independent memory resource denoting its availability, interconnection with the other contention circuits to provide the longest length of time any other processor of the set has waited for access, priority interconnection with the other contention circuits, ranking these circuits according to a pre-determined priority rule to break ties between the circuits in case of equality of all other criteria, and connection with its own respective processor indicating need of the processor for access over the bus and the identity of the memory resource required by the processor. Each contention circuit is constructed to compare independently its length of time of waiting for the bus to that of the other circuits and is adapted to connect its own respective processor automatically to the bus when signals over the respective inputs and connections establish, that, for the respective processor: (a) it requires access to a memory resource, (b) and the memory resource it requires is available, (c) and it has waited as long or longer than any other processor, (d) and there is no processor with higher rank meeting conditions (a) through (c) (i.e., no processor with higher rank is "tied").

In preferred embodiments disabling inputs are provided for the set of contention circuits, the contention circuit of highest rank having no such effective input, and the circuits of decreasing rank having correspondingly increasing numbers of effective inputs, corresponding to the contention circuits of higher rank, each contention circuit being constructed to generate a discrete signal based upon satisfaction to the contention circuit of all of the criteria (a), (b) and (c) which is connected to a respective input of each contention circuit of lower rank. Preferably each contention logic circuit has a set of identical input lines corresponding to one less than the number of contention logic circuits in the set, those not needed being provided a constant dummy or false logic value, the contention circuit of highest rank having such value on all of its inputs and the contention logic circuits of descending rank having descendingly fewer of such inputs, the last circuit having none. Each contention logic circuit except that of lowest rank has an effective output which signals a true priority value when its logic circuit satisfies all criteria (a), (b) and (c). Each such output is connected to a respective input of each circuit of lower rank to disable the circuit.

Also, in preferred embodiments, the system includes means to provide a composite indication of the longest waiting time of all contention logic circuits on a wait bus to which all contention circuits are connected. Preferably each contention logic circuit places upon the wait bus its waiting time value. Each contention circuit has a comparator for comparing its waiting time value with the time value on the bus and means to disable the respective contention logic circuit when the comparison shows that the wait bus value is greater. Preferably too, each contention logic circuit includes a shift register started by a bus request signal from the processor, and means are provided: to maintain the shift register clear during intervals when the corresponding processor and contention circuit are not waiting, to accumulate in the shift register a set of consecutive ones corresponding to the number of intervals the processor and contention circuit have been waiting, and, during each cycle when it is contending, to apply the set of ones to corresponding inputs of the wait bus, whereby the highest order "one" applied to the wait bus represents the longest waiting time of any contention logic circuit in the system.

In preferred embodiments each stage of a waiting time shift register is connected to the respective wait bus line through a logic device implementing the wired OR function, whereby a logical true is forced on the respective line regardless of the value of any other input to the line, preferably each device being an open collector NAND gate having as inputs a stage of the shift register, and a signal indicating availability of the memory sought by the corresponding processor.

Preferred embodiments also employ a comparator comparing the stages of the shift register with corresponding lines of the wait bus, adapted to emit a true signal when and only when there is identity in the two sets of inputs. Preferably a logic device has as inputs the comparison signal, a signal indicative of availability of the memory sought by the corresponding processor and a set of signals from higher ranked contention circuits, representing no higher ranked circuit is tied, this logic device being adapted to emit a bus grant signal when all of the inputs are of true value, the bus grant signal preferably also being emitted to disable lower ranked contention circuits.

Also in preferred embodiments a memory busy bus is provided having one line associated with each memory resource, carrying a busy or not busy signal, means defining the address of the computer on an interleaved basis modulo n where n is a number equal to (or in some instances greater) than the number of independent memory resources, each of the contention circuits having a data selector whose inputs are the lines of the memory busy bus and the lowest significant lines of the address request of the respective processor, the data selector adapted to produce a positive indication when the modulo n value corresponds to a memory busy line having a "not busy" signal. Preferably the output of the selector is connected as an enable signal to a bus grant output device. In preferred embodiments a data network processor unit is provided incorporating the before-described contention logic circuitry and having an input/output bus connected to a multiplicity of real time data ports, and connectable via a selected processor to the address/data bus, the contention logic circuitry adapted to speed the processing of the data to enable real time operation without interruption.

In preferred embodiments the data communications processor unit includes blank spaces and appropriate connectors for receiving additional processor modules. Insertion of a processor establishes disabling inputs from any processor of higher rank and disabling outputs to any processor of lower rank, preferably accomplished by an identical set of connectors at each position with disabling inputs and dummy (constant false) inputs distributed as described above. The modules also provide a constant false signal to all of its priority inputs that would receive inputs from the absent processor. By these various connections, insertion or removal of a processor automatically enters or removes it from the bus contention system. (Insertion of the processor also automatically connects its contention logic to the memory busy bus and the wait bus.)

In the modularized data communications processor the memory busy bus preferably has a plurality of lines and interconnect connectors for engagement by inserted memory modules. Identical logic circuits can be provided on the memory modules themselves, according to the invention, by which, by merely sensing the absence or presence and the position of adjoining modules, each memory module allocates to itself the appropriate interleave format, address response and memory busy line for the contention logic. In a preferred embodiment, a single memory module carries two memory sections. If it senses no module present with which it can perform modulo 4 interleave, it shifts itself to a modulo 2 interleave mode, assigns even addresses to one and odd addresses to the other memory section, and assigns two of the four memory busy lines to each memory section, so that both show busy to the contention logic when the respective memory section is busy.

On the other hand if a module senses the presence of another available module, both modules automatically conform to a modulo 4 interleave mode, each assigning to its two memory sections two of the four possible interleave addresses depending whether it is left or right, and correspondingly assigns its two memory sections respectively to two memory busy lines. In this particular embodiment, modulo 4 operation may occur for the address ranges of each pair of neighboring modules, and a modulo 2 mode may occur for the possibly remaining module, over its address range.

These and other features and advantages of the invention will be understood from the following description of a preferred embodiment taken in conjunction with the drawings wherein:

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a block diagram of a multiprocessor, multimemory computer incorporating logic contention circuitry according to the invention.

FIG. 2 is a block diagram of a single processor No. 2 of FIG. 1;

FIG. 3 is a schematic diagram of the logic contention circuit of the processor of FIG. 2;

FIG. 4 traces certain events over time on the circuit of FIG. 3;

FIGS. 5 and 6 are block diagrams similar to FIG. 1 of data network processors incorporating the invention, while FIG. 7 is a schematic and table illustrating interaction of the memory modules relative to the address lines. FIG. 8 shows a circuit by which a memory module of FIGS. 6 and 7 responds to the presence of others, and allocates to itself an appropriate section of the address range and memory busy bus.

DESCRIPTION OF THE PREFERRED EMBODIMENTS

Description of the Embodiment of FIGS. 1-4

FIG. 1 illustrates a computer system embodying the invention. The computer system has four processor modules 20 (a, b, c, d) and four memory modules 22(a,b,c,d). The processors share the memory modules on a time shared basis. Bidirectional data transfers between memories and processors are accomplished by using a group of common signal lines called the address/data bus I, which supplies the addresses to the memory and transfers the data. The auxiliary busses II-IV shown are employed in the contention logic 30 (see FIG. 2). Each processor may independently attempt to access a given memory module. Since these access attempts are independent, conflicts for use of the time shared address/data bus and the memory modules will occur. It is the function of the contention logic associated with each processor to determine when it may use the bus to access a memory module.

The memory modules also operate independently. In this embodiment they are organized to respond to interleaved addresses; the interleaving here corresponds to the modulo 4 value of the address, chosen because the memory cycle time is typically longer than a memory access time and a memory module recently accessed may not be available when a processor wishes to access it.

The contention logic 30 on each processor must know the memory status of each independent section of memory. For this purpose a unidirectional memory busy bus II is provided for each independent memory, upon which the respective memory module indicates its busy status by asserting a "memory busy" signal when appropriate, for each master clock interval. There is one "memory busy" signal for each independent section of memory; hence a total of 4 lines comprise the "memory busy" bus for the embodiment of FIG. 1. This "memory" bus is routed to each processor, as shown.

To ensure fairness of service in cases of conflicting requests for the address/data bus, certain criteria are applied by the contention logic associated with each processor. The first criteria is that the memory module it wishes to access must be available before it can be granted bus access. This can be determined from the `memory busy` bus. The next criteria is that no other processsor has waited for a longer period of time than this processor has. To evaluate this criteria each contention logic maintains a record of how long its processor has been waiting. Each contention logic compares the value on the "wait time" bus(bidirectional bus III, connecting all processors) with the value it has maintained for its processor.

A final criteria is necessary if more than one processor has met all the previously stated criteria, namely has been waiting for the same period of time and the memory modules they seek to address are available. In case of this kind of tie a strict priority ordering criteria is applied. In this embodiment this is achieved by a distributed priority function using the priority bus lines IV as shown in FIG. 1 in conjunction with priority circuitry in each contention logic. Simply stated this last criteria is met if all the priority inputs to the contention logic are logical false.

When the contention logic on any processor module has determined that all the criteria for bus access have been met, it will automatically assert a signal on a bus priority line to disable all lower priority processors. As shown in FIG. 1 this output line becomes one of the priority inputs to all lower-ranked processor module contention logics.

FIG. 2 illustrates a processor module with contention logic 30. The processing element 32 of the module determines when the memory access needs to be made. In this embodiment the processing element, when requiring access to the memory, asserts a "bus request" signal which is connected to the contention logic. The processinc element also supplies to the contention logic the address of the memory module being requested. In this embodiment the address input consists of the two lowest order address lines to specify which of the four possible interleaved memory modules is being accessed, according to the modulo 4 value of the address appearing in the address/data bus. The contention logic applies the contention algorithm as described above and supplies to the processing element the "bus grant" signal 24 at the appropriate time. The processor module will then be able to use the system bus on the next clock cycle to carry address and data information to the memory modules by emitting a bus enable signal 26 for enabling its bus drivers 28 and receivers to the respective busses as shown in FIG. 2.

FIG. 3 illustrates the elements of the contention logic 30. The "memory busy" bus from the memory modules is connected to the four-to-one data selector 35. The two low order address lines from the processing element are used as inputs to the data selector to select the appropriate "memory busy" line. The "bus request" line from the processing element is also connected to the data selector as the output enable condition. The output from the data selector indicating the state of the selected "memory busy" line is connected to various elements of the contention logic, as shown.

Operation of the Preferred Embodiment of FIGS. 1-4

The entire system illustrated in FIG. 1 operates from a master system clock. This implies that all state changes throughout the system are synchronous with respect to a particular instant in time. Thus all processor requests for memory are synchronized to some particular point in time.

The contention logic circuits associated with each processor operate such that after every state transition each will resolve any outstanding request for the memory and the bus before the next clock transition. The result will be that one and only one processor will grant itself access to the address/data bus on the next clock cycle, if in fact any processor is requesting a memory unit that is available.

Since all state changes occur on a clock edge, all signals will stabilize after some propagation delay time before the next clock edge. This applies to all signals being received by the contention logic and of course therefore all signals output by the contention logic.

A processor requiring a memory access will supply the `bus request` signal to its contention logic circuit. This signal will enable the data selector output. The output of this data selector will be one of the `memory busy` lines from the memory as shown in FIG. 3. The particular `memory busy` line will be selected by the two low order address lines supplied by the processing element. The sense of the `memory busy` lines on the system bus is inv