Network for determining route through nodes by directing searching path signal arriving at one port of node to another port receiving free path signal

Abstract

A large number of processor cells 11, the majority of which are standard cells 12 and others special cells 13, are connected to a communication network 14 in the form of several binary trees. The cells 11 are connected at the leaf positions of the binary trees, and the nodes of the binary trees are formed by switching circuits that allow individual cells to control the formation of signal paths through the nodes. In operation, cells may be in a waiting state, a free state, a calling state, searching state, a communicating state, or an internal operation state. Cells 12 in the free state transmit a free signal into the network 14. Cells 12 or 13 in a searching state transmit a searching signal into the network 14 where, on meeting a free signal at a node, a route is formed from the searching state cell to a free state cell. A calling state cell 12 establishes, with a calling signal, a route through the network 14 to another cell identified by destination information in the calling signal. Cells 11 in the waiting state are waiting to be called by a cell 12 in the calling state. Expressions, in the form of lambda expressions, to be reduced to a final result are so distributed through groups of the cells 11 that only primitive operations and communication need be carried out by the cells 11.

Claims

What is claimed is:

1. Apparatus for performing parallel processing, comprising: a plurality of processor cells, and a communication network, each of a majority of the processor cells having a plurality of operating states comprising at least a searching state in which the cell transmits into the network a searching signal, and a free state in which the cell transmits into the network a free signal, the network including a plurality of nodes for transmitting searching signals and free signals, such that the network is adapted to provide a partial route in response to a searching signal supplied thereto by a processor cell in a searching state, and a partial route in response to a free signal supplied thereto by another processor cell in a free state, each such partial route extending through at least one of said nodes, each node further being adapted to direct a searching signal in the node onto a partial route provided in response to a free signal in the node and thus extend a partial route provided in response to a searching signal along a partial route provided in response to a free signal, the network being adapted to form a completed route to a processor cell in a free state from a processor cell in a searching state, said completed route extending through at least one node at which said directing occurs, the network being such that a plurality of completed routes therethrough can co-exist, each completed route interconnecting a respective pair of the cells and being established by operation of at least one of the pair of cells and permitting transmission of data between the pair of cells, and each cell being adapted to execute reduction operations in which the cell transforms data therein in accordance with rules for reducing expressions stored as data in groups of the cells.

2. Apparatus according to claim 1, wherein each of at least some of the processor cells has a plurality of operating states comprising the searching state and a waiting state, and transmits into the network a searching signal when in the searching state.

3. Apparatus according to claim 1, wherein each of at least said majority of cells has a calling state and transmits into the network a calling signal when in the calling state, and the network is adapted to route a calling signal in accordance with destination information included in the calling signal and indicative of a route extending from the calling state cell that originates the calling signal to another of the cells.

4. Apparatus according to claim 1, wherein each said route interconnecting a respective pair of the cells is formed as a monotonically progressing path through the network.

5. Apparatus according to claim 4, wherein said monotonically progressing path progresses by discrete segments.

6. Apparatus according to claim 1, wherein the network is such that a route being formed therein from a processor cell can meet a route already formed or partially formed therein from another processor cell and completion of the route being formed be delayed until said already formed or partially formed route is disestablished.

7. Apparatus according to claim 1, wherein each said route interconnecting a respective pair of the cells is disestablished by operation of said one of said pair of cells.

8. Apparatus according to claim 1, wherein the network includes one or more tree arrangements for providing routes between the cells, and the cells are at leaf positions of the tree arrangement or arrangements.

9. Apparatus according to claim 8, wherein the one or more tree arrangements are binary tree arrangements.

10. Apparatus according the claim 1, wherein each cell is adapted to execute communication operations, command operations in which the cell transmits command signals into the network to another of the cells, and slave operations in which the cell executes commands transmitted thereto by another of the cells through the network, the communication operations including operations in which the cell receives data from another of the cells through the network, and operations in which the cell transmits data to another of the cells through the network.

11. Apparatus according to claim 1, wherein the rules for reducing expressions are consistent with pure Church lambda calculus.

12. Apparatus according to claim 1, wherein the expressions are lambda expressions.

13. Apparatus according to claim 1, wherein the network is such that any one of the cells can be connected to any other one of the cells by a route through the network.

14. Apparatus according to claim 1, wherein each pair of cells can be interconnected by a plurality of routes through the network.

15. Apparatus according to claim 1, wherein each cell has a calling state and transmits into the network a calling signal when in the calling state, and each node is adapted to route a calling signal in accordance with destination information included in a calling signal and indicative of a route extending from a calling cell that originates the calling signal to another of the cells and including said node.

16. Apparatus according to claim 15, wherein destination information is stored in the network.

17. Apparatus according to claim 15, wherein the network comprises a plurality of path segments and each of at least a majority of the nodes forms a junction between three of said path segments.

18. Apparatus according to claim 1, wherein each cell has a waiting state in which the cell stores expression information.

19. Apparatus according to claim 18, wherein stored expression information includes destination information indicative of a route extending from the cell in the waiting state to another of the cells.

20. Apparatus according to claim 19, wherein destination information is stored in the network.

21. Apparatus according to claim 1, wherein each cell is adapted to test first data stored within the cell to determine whether a reduction operation can be executed on said first data and, if the result of the test is negative, to set the cell in a state such that the cell continues to store said first data until the cell receives from at least one other of the cells further data which when substituted for or combined with at least part of said first data creates data giving a positive result to said test, whereupon the cell executes the reduction operation.

22. Apparatus according to claim 1, wherein each individual cell is adapted to execute primitive operations in said rules for reducing expressions.

23. Apparatus according to claim 1, wherein said rules include rules for the execution of concurrent beta-reduction of functional expressions.

24. Apparatus according to claim 23, wherein each of at least some of the processor cells has a plurality of operating states comprising the searching state and a waiting state, and transmits into the network a searching signal when in the searching state.

25. Apparatus according to claim 24, wherein the network includes one or more tree arrangements for providing routes between the cells, and the cells are at leaf positions of the tree arrangement or arrangements.

26. Apparatus according to claim 23, wherein each individual cell is adapted to execute primitive operations in said rules for reducing expressions.

27. A communication network for forming a partial route for a searching signal supplied to the network at a first point, forming a partial route for a free signal supplied to the network at a second point, and forming a complete route for said searching signal from said first point to said second point with said partial routes, said network comprising a plurality of path segments for free signals and searching signals and a plurality of nodes, each of at least a majority of said nodes forming a junction between at least three of said path segments, and each node being adapted to select a path through the node for a searching signal in response to presence of a free signal at the node, said path connecting a path segment through which said searching signal entered the node to a path segment through which said free signal entered the node.

28. Apparatus for performing parallel processing, comprising:

(a) a communication network for forming a partial route for a searching signal supplied to the network at a first point, forming a partial route for a free signal supplied to the network at a second point, and forming a complete route for said searching signal from said first point to said second point with said partial routes, said network comprising a plurality of path segments for free signals and searching signals and a plurality of nodes, each of at least a majority of said nodes forming a junction between at least three of said path segments, and each node being adapted to select a path through the node for a searching signal in response to presence of a free signal at the node, said path connecting a path segment through which said searching signal entered the node to a path segment through which said free signal entered the node; and

(b) a plurality of processor cells each having at least a searching state and a free state, and transmitting into the network a searching signal when in the searching state and a free signal when in the free state.

29. Apparatus according to claim 28, wherein the apparatus includes a further plurality of processor cells each of which has a searching state and a waiting state, and transmits into the network a searching signal when in the searching state.

30. Apparatus according to claim 28, wherein each of at least said cells having a free state has a calling state and transmits into the network a calling signal when in the calling state, and the network is adapted to route a calling signal in accordance with destination information included in the calling signal and indicative of a route extending from the calling state cell that originates the calling signal to another of the cells.

31. Apparatus according to claim 30, wherein each cell is adapted to execute reduction operations in which the cell transforms data, stored in the cell, in accordance with rules for reducing expressions stored as data in groups of cells, said reduction operations of each individual one of said cells being primitive operations in said rules for reducing expressions.

32. Apparatus according to claim 31, wherein the rules for reducing expression are consistent with pure Church lambda calculus.

33. Apparatus according to claim 32, wherein the expressions are lambda expressions.

34. Apparatus according to claim 30, wherein destination information is stored in the network.

35. Apparatus according to claim 28, wherein each of at least some of the cells has a calling state and transmits into the network a calling signal when in the calling state, each node is adapted to route a calling signal in accordance with destination information included in the calling signal and indicative of a route extending from the calling state cell that originates the calling signal to another of the cells and including said node, and the network including a plurality of binary tree arrangements of said path segments, said cells being at leaf positions of each binary tree arrangement and said nodes being at nodal positions of the binary tree arrangements, each cell occupying a different leaf position in at least two binary tree arrangements, such that two routes respectively provided in said two binary tree arrangements between two cells contain different numbers of nodes.

36. Apparatus according to claim 35, wherein destination information is stored in the network.

37. Apparatus according to claim 35 wherein the cells are arranged to form a planar array in which a unit pattern of four cells in a square is repeated to form a square array of the cells with the number of cells along any side of the array being an integer power of two.

38. Apparatus according to claim 37, wherein each cell occupies a different leaf position in four binary tree arrangements.

39. Apparatus according to claim 28, wherein each processor cell comprises storage means for storing a plurality of different categories of data, means for determining what categories of data are stored in the storage means and selecting one of a plurality of processes of said cell in dependence upon the categories of data determined to be stored in the storage means, at least one of said processes including a computation step utilizing data stored in the storage means, computation means for executing said computation step, means for receiving data for storage in the storage means, and means for outputting data resulting from said processes of the cell, the means for determining the categories of data including means responsive to presence of data in a category incompatible with said computation step to inhibit operating of the computation means on such data, and each of at least a majority of said plurality of cells having means for outputting into the communication network a status signal indicative of whether or not said selected process is a predetermined resting process constituting a free state of the cell, the status signal when indicative of the free state serving as a free signal.

40. Apparatus for performing parallel processing, comprising a plurality of processor cells and a communication network, said cells being connected to the communication network, the communication network including a plurality of nodes, each of at least some of the cells having a plurality of operating states comprising at least a searching state and a free state and transmitting into the network a searching signal when in the searching state and a free signal when in the free state, and each node being adapted to transmit through the node a searching signal and a free signal and to direct a searching signal at the node when a free signal is present at the node, and the network being adapted to establish a communication route between a cell in the searching state and another cell in the free state through one or more nodes at which said directing occurs.

41. Apparatus according to claim 40, wherein the network includes at least one binary tree arrangement of path segments, said nodes being at nodal positions of the binary tree, and the processor cells being at leaf positions of the binary tree.

42. Apparatus according to claim 41, wherein the network includes a plurality of binary tree arrangements of path segments, each of the cells being at leaf positions of each binary tree arrangement, and the nodes being at nodal positions of the binary tree arrangements.

43. Apparatus according to claim 42, wherein each cell occupies a different leaf position in at least two binary tree arrangements, such that routes containing different numbers of nodes in the said two binary tree arrangements can be established between two cells.

44. Apparatus according to claim 41, wherein the cells are arranged to form a planar array in which a unit pattern of four cells in a square is repeated to form a square array of the cells with the number of cells along any side of the array being an integer power of two.

45. Apparatus according to claim 44, wherein each cell occupies a different leaf position in four binary tree arrangements of path segments.

46. Apparatus according to claim 41, wherein the or at least one of the binary tree arrangements is an incomplete binary tree.

47. Apparatus according to claim 46, wherein the incomplete binary tree is coupled to means for simulating at least part of the remainder of the binary tree, including the nodes thereof, and the cells at the leaf positions in that part.

48. Apparatus according to claim 40, wherein each cell has a calling state and transmits into the network a calling signal when in the calling state, and each node is adapted to route a calling signal in accordance with destination information included in the calling signal and indicative of a route extending from the calling state cell that originates the calling signal to another of the cells and including said node.

49. Apparatus according to claim 48, wherein destination information is stored in the network.

50. Apparatus according to claim 40, wherein each cell is adapted to execute predetermined operations with predetermined categories of data only when such predetermined categories of data are present therein, transmit data to and receive data from others of the cells through the network, and respond to presence of data representing an inhibit command by inhibiting execution of operations on predetermined categories of data.

51. Apparatus according to claim 50, wherein the predetermined operations include reduction operations, the categories of data include symbolic data and pointers, and the cell is adapted to determine whether symbolic data and pointers are present in the cell and to inhibit one or more reduction operations if the determination is affirmative.

52. Apparatus according to claim 51, wherein the cell is adapted to respond to presence of symbolic data and pointers by transmitting in accordance with a pointer.

53. Apparatus according to claim 50, wherein each of at least some of the cells is adapted to transmit into the network a status signal indicating whether or not the cell contains data for further processing, and said free signal comprises said status signal indicating that a cell does not contain data for further processing.

54. Apparatus according to claim 53, wherein each of said cells is responsive to the inclusion of a pointer in a predetermined combination of categories of data in the cell to transmit an acquire signal into the network, and each said node is adapted to provide in response to an acquire signal received in the node a path for the acquire signal through the node without dependence on presence or absence of said free signal.

55. Apparatus according to claim 50, wherein the network includes one or more tree arrangements for providing said communication routes between the cells, and the cells are at leaf positions of the tree arrangement or arrangements.

56. Apparatus according to claim 55, wherein the one or more tree arrangements are binary tree arrangements.

57. Apparatus according to claim 50, wherein each cell is adapted to execute a plurality of operations including a set of operations including communication operations, command operations in which the cell transmits command signals into the network to another of the cells, slave operations in which the cell executes commands transmitted thereto by another of the cells through the network, and internal operations in which the cell processes data stored in the cell, the communication operations including operations in which the cell receives data from another of the cells through the network, and operations in which the cell transmits data to another of the cells through the network.

58. Apparatus according to claim 57, wherein at least some of the internal operations of the cell are reduction operations in which the cell transforms data, present in the cell, in accordance with rules for reducing expressions stored as data in groups of the cells.

59. Apparatus according to claim 58, wherein the rules for reducing expressions are consistent with pure Church lambda calculus.

60. Apparatus according to claim 58, wherein the expressions are lambda expressions.

61. Apparatus according to claim 57, wherein one of said operating states is a calling state in which the cell transmits into the network a calling signal, and the network is adapted to route a calling signal in accordance with destination information included in the calling signal and indicative of a route extending from the calling state cell that originates the calling signal to another of the cells.

62. Apparatus according to claim 61, wherein destination information is stored in the network.

63. Apparatus according to claim 57, wherein each cell is adapted to test first data stored in the cell to determine whether an internal operation can be executed on said first data and, if the result of the test is negative, to set in a state such that the cell continues to store said first data until the cell receives from one or more others of the cells further data which, when substituted for or combined with at least part of said first data, creates data giving a positive result to the test, whereupon the cell executes the internal operation.

64. Apparatus according to claim 63, wherein said cell determines the result of the test on the basis of the categories of the data tested.

65. Apparatus according to claim 64, wherein said cell is responsive to presence of destination information data in designated storage means in the cell to provide a negative result to said test.

66. Apparatus according to claim 65, wherein destination information data is stored in the network.

67. Apparatus according to claim 63, wherein the test includes testing at least one flag.

68. Apparatus according to claim 67, wherein the test includes ascertaining what categories of data are present in the cell.

69. Apparatus according to claim 40, wherein each of at least some of the cells has a calling state and transmits into the network a calling signal when in the calling state, each node is adapted to route a calling signal in accordance with destination information included in the calling signal and indicative of a route extending from the calling state cell that originates the calling signal to another of the cells and including said node, and the network including a plurality of binary tree arrangements in which the cells are at leaf positions of each binary tree arrangement and the nodes are at nodal positions of the binary tree arrangements, each cell occupying a different leaf position in at least two binary tree arrangements, such that routes containing different numbers of nodes in the two binary tree arrangements can be established between two cells.

70. Apparatus according to claim 40, wherein each cell is adapted to execute a plurality of operations, said operations including communication operations, command operations in which the cell transmits command signals into the network to another of the cells, slave operations in which the cell executes commands transmitted thereto by another of the cells through the network, and reduction operations in which the cell transforms data, stored in the cell, in accordance with rules for reducing expressions stored as data in groups of the cells, the communication operations including operations in which the cell receives data from another of the cells through the network and operations in which the cell transmits data to another of the cells through the network, said reduction operations of each individual cell being primitive operations in said rules for reducing expressions.

71. Apparatus according to claim 40, wherein each cell is adapted to execute a plurality of operations, said operations including communication operations, command operations in which the cell transmits command signals into the network to another of the cells, slave operations in which the cell executes commands transmitted thereto by another of the cells through the network, and internal operations in which the cell processes data stored in the cell, the communication operations including operations in which the cell receives data from another of the cells through the network, and operations in which the cell transmits data to another of the cells through the network, the cell further being adapted to store data in a plurality of categories, and to detect what categories of data are concurrently stored therein and to select one of a plurality of operative states of said cell in dependence upon what combination of categories of data is detected by said cell.

72. Apparatus according to claim 40, wherein each cell comprises a store for storing data, said data comprising a plurality of categories of data, logic for detecting what categories of data which are stored therein, logic for executing predetermined operations with predetermined categories of data only when such predetermined categories of data are present therein, and a transmitter/receiver for transmitting data to and receiving data from others of the cells through the communication network, said logic for detecting what categories of data being responsive to presence of data representing an inhibit command to inhibit operation of the executing logic on predetermined categories of data.

73. Apparatus according to claim 72, wherein the predetermined operations include reduction operations, the categories of data include symbolic data and pointers, and the executing logic is adapted to determine whether symbolic data and pointers are present in the cell and inhibit one or more reduction operations if the determination is affirmative.

74. A communication network comprising: a plurality of nodes, and a larger plurality of path segments connected to said nodes, each of at least a majority of said nodes forming a junction between at least three of said path segments, each path segment being adapted to transmit therethrough a searching signal and a free signal, and each node comprising a signal path. selector for selecting paths through the node for searching signals, said signal path selector being responsive to presence of a free signal entering the node from a first one of said path segments connected to the node and a searching signal entering the node from a second one of said path segments connected to the node to select through the node for said searching signal a path by which said searching signal exits the node through said first path segment.

75. A communication network according to claim 74, wherein each node is responsive to an acquire signal entering the node from a path segment connected thereto for providing a path for the acquire signal through the node to a selected other one of said path segments connected to the node, without dependence on presence or absence of said free signal.

76. A communication network according to claim 75, wherein each of at least a majority of the nodes forms a junction between only three path segments, and is responsive to a binary value signal to select another of said three path segments when said binary value signal is received in the node from the same path segment as the acquire signal, said selection being made in dependence upon said binary value.

Description

This invention relates to apparatus for performing parallel processing.

BACKGROUND OF THE INVENTION

Many of the known types of apparatus for performing parallel processing are reviewed and discussed in Parallel Computers 2, Architecture, Programming and Algorithms, by R. W. Hockney and C. R. Jesshope, published in 1988 by Adam Hilger, Bristol, England, and Philadelphia, U.S.A., and a number of experimental computers are compared in an article entitled "A Survey of Proposed Architectures for the Execution of Functional Languages" by Steven R. Vegdahl, published in IEEE Transactions on Computers, Vol. C-33, No. 12, Dec. 1984, pages 1050 to 1071.

In a classical von Neumann computer architecture processing is carried out in a strictly sequential manner, the architecture having a single control unit, a single arithmetic and logic unit, and a memory in which program instructions and other data are stored in a sequence of addressable locations. During execution of a program, one instruction is called up at a time and executed. The address of the next instruction must either be provided by an instruction counter that simply counts through a regular numerical sequence of addresses, or by data supplied from the memory in the execution of the current program step. Such strictly sequential processing is a disadvantage in many circumstances, and attempts have been made to develop architectures which are not so limited. Attempts to avoid the sequential restrictions imposed by sequential programs have resulted in new memory structures which are to be operated on by one or more control units each having its own arithmetic and logic unit. Two examples of the latter development are described in U.S. Pat. Nos. 3,646,523 and 4,075,689 issued to Klaus Berkling. It is sometimes implied that designing a central control unit that operates without an instruction counter will lead to the elimination of the so-called von Neumann bottleneck, but in fact the bottleneck exists in processing apparatus which has a central control unit without an instruction counter, as can be seen from pages 34 and 35 of Automatic Digital Calculators, by A. D. and K. H. V. Booth, published in 1956 by Butterworths Scientific Publications, London, where it is pointed out that if each instruction contains the memory location of the next, the effect on the design of the central control unit is to eliminate the instruction counter.

The two United States patents mentioned hereinbefore, U.S. Pat. Nos. 3,646,523 and 4,075,689, both issued to Klaus Berkling, described early examples of reduction machines. A more recent example of a reduction machine architecture in which processing and memory are separate is described in U.S. Pat. No. 4,591,971, issued to John Darlington et al., and in an article entitled "Declarative languages and program transformation for programming parallel systems; a case study" by J. Darlington, M. Reeve, and S. Wright, in Concurrency: Practice and Experience, Vol. 2(3), pages 149 to 169, Sep. 1990.

A further attempt to avoid the disadvantages of strictly sequential processing has been the development of systems which have a plurality of von Neumann processors, each with its own central processing unit (CPU) and local memory, interconnected by a specially designed bus or network. Since each processor is inherently an independent processing entity, considerable effort is required in designing interfacing between the individual processor and the network and in the control and organisation of data transfer between the processors. Also, because of the so-called contention problem, the design of the interconnecting network has an effect on the efficiency of cooperation between the processors and hence on the extent to which the processing capabilities of the individual processors can be utilized. An example of such a system is described in an article entitled "Hierarchical Routing Bus" by T. Sueyoshi and I. Arita, in Systems and Computers in Japan, Vol. 16, No. 6, 1985, at pages 10 to 19, and in an article entitled "Performance Evaluation of the Binary Tree Access Mechanism in MIMD Type Parallel Computers" by T. Sueyoshi, K. Saisho, and I. Arita in Systems and Computers in Japan, Vol. 17, No. 9, 1986, at pages 47 to 57. The latter articles describe a shared-memory parallel processing system in which processor modules, each comprising a processor unit and a memory unit, are interconnected by a binary tree access mechanism. Each module has a system address. The address space of the system is represented by a two-dimensional address composed of the system address and a location in the module having that system address, so that a single address space is formed. Each processor unit can access any memory unit via the binary tree access mechanism. However, an instruction fetch can be made only from the memory unit within the module that contains the processor unit carrying out the instruction fetch. Thus each memory unit is the local memory for its own processor unit, and global memory for the other processor units. Another tree-type routing network for parallel processing is described in an article entitled "Fat-Trees: Universal Networks for Hardware Efficient Supercomputing" by C. E. Leiserson, at pages 393 to 402 of the Proceedings of the 1985 International Conference on Parallel Processing, published by IEEE Computer Society Press, and a tree-type local network is described in IBM Technical Disclosure Bulletin, Vol. 25, No. 11B, Apr. 1983, at pages 5974 to 5977, by P. A. Franaszek.

Several parallel processing architectures are outlined in Byte, Nov. 1988, at pages 275 to 349. Amongst those mentioned there is a hypercube architecture known as the connection machine, which is also described in "The Connection Machine" by W. D. Hillis at pages 86 to 93 in Scientific American, Vol. 256, No. 6, Jun. 1987, and in U.S. Pat. Nos. 4,598,400 and 4,814,973 issued to W. D. Hillis. In the connection machine, hypercube architecture is employed in the structure of an array of 32768 identical integrated circuits each containing 32 identical processor/memories, so that there are 1,048,576 identical processor/memories. Each processor/memory is connected to its four nearest neighbours. The direction of data flow through the array is controlled by a microcontroller of conventional design. Also, each integrated circuit is provided with logic circuitry to control the routing of messages through a Boolean n-cube of fifteen dimensions into which the integrated circuits are organised. Within each integrated circuit, bus connections are provided to the thirty-two processor/memories so that each processor/memory can send a message to every other processor/memory in that integrated circuit. To permit communication through the Boolean 15-cube, the connection machine is operated so that it has both processing cycles and routing cycles. Computations are performed during the processing cycles. During the routing cycles, the results of the computation are organised in the form of message packets, and these packets are routed from one integrated circuit to the next by routing circuitry in each integrated circuit in accordance with address information that is part of the packet. In the packet, the integrated circuit address information is relative to the address of the destination integrated circuit. The routing circuitry in all the integrated circuits is identical and operates in synchronism using the same routing cycle. Passage of a message packet from a source integrated circuit to a destination integrated circuit is effected by the routing circuits of the integrated circuits. Each routing circuit comprises a line assigner, a message detector, a buffer and address restorer, and a message injector. The line assigner comprises a fifteen by fifteen array of substantially identical routing logic cells. Each column of the array of routing logic cells controls the output of message packets in one dimension of the Boolean 15-cube. Each row of this array controls the storage of one message packet in the routing circuit. The message detector, buffer and address restorer, and message injector of each routing circuit comprises fifteen sets of processing and storage means corresponding to the fifteen rows of routing logic cells. Thus the connection machine, although having a large plurality of processor/memories instead of separate areas of processing and memory, relies on complex auxiliary routing control arrangements. A further aspect of routing in such a machine is described in international patent application publication no. WO89/07299 of Thinking Machines Corporation (inventor W. D. Hillis) which describes an array of processors and an interconnection network controlled by a control unit in the form of a Symbolics 3600 Series LISP machine and a microcontroller. Another example of a processor array with interconnection controlled by a separate control unit is described in international patent application publication no. WO87/01485 of The University of Southampton (inventors C. R. Jesshope, P. S. Pope, A. J. Hey, and D. A. Nicole) and uses transputers as processors. Cube networks for MIMD and SIMD processing in distributed systems are discussed generally in an article entitled "The Multistage Cube: A Versatile Interconnection Network" by H. J. Siegel and R. J. McMillen, at pages 65 to 76, Computer, Dec. 1981.

Another approach to parallel processing has been that of providing an interconnected array of processors where the interconnection is designed to correspond to a distribution of tasks into which a computation is to be resolved. Such an approach has as its background the development of programming languages known as applicative or functional programming languages, which was in particular stimulated by an article entitled "Can programming be liberated from the Von Neumann Style?. A functional style and its algebra of programs" by J. Backus at pages 613 to 641 in Communications of ACM (1978), No. 21. The functional programming languages are closely based on a formal notation known as the lambda calculus. Lambda calculus was originally described in the Calculi of Lambda-Conversion by Alonzo Church, first published in 1941 by Princeton University Press, with second printing in 1951. The pure Church Lambda calculus is described in Introduction to Combinators and .lambda.-Calculus by J. Roger Hindley and Jonathan P. Seldin, published in 1986 by Cambridge University Press, Cambridge, England, and New York, U.S.A. The significance of the lambda calculus in relation to functional programming is discussed in Functional Programming by Anthony J. Field and Peter G. Harrison, published in 1988 by Addison-Wesley Publishing Company, Wokingham, England, Reading, Massachusetts, U.S.A., and Tokyo, Japan. A particular feature of the lambda calculus is a form of reduction known as Beta reduction, which is explained in section 1C of Introduction to Combinators and .lambda.-Calculus, and section 6.2 of Functional Programming. A functional program for a computation can be resolved recursively into a tree structure of sub-tasks, and the final result of the program be independent of the order in which these sub-tasks are evaluated. One example of the design of an array of processors corresponding to a distribution of tasks into which a functional program can be resolved is described in an article entitled "A Reduction Architecture for the Optimal Scheduling of Binary Trees" by K. Ravikanth, P. S. Sastry, K. R. Ramakrishnan, and Y. V. Ventatesh, at pages 225 to 233 in Future Generations Computers Systems, No. 4, 1988, published by Elsevier Science Publishers B. V. (North Holland). In the latter article there is described an array of eight processors so interconnected that a binary tree of computing tasks can be mapped onto the array. The interconnections conform to the relationships expressed by

L(Pi)=P2imodN and R(Pi)=P(2i+1)modN for i=0, 1 . . . , N-1,

where N=8, Pi is the (i+1)th processor of N identical processors, L means left-hand child, and R means right-hand child. It is assumed that the computation decomposes itself recursively into identical subproblems (tasks), and that every task down loads the two subtasks it spawns onto its immediate neighbours. Each processor in the network has four neighbours, two connected to paths coming into the processor, and two connected to paths going out from the processor. The memory of each processor is divided into three banks: a left-memory; a right-memory; and a local-memory. The local-memory is local to its own processor and contains all programs, relevant tables, etc. Each processor communicates with its left child through its own left-memory, and with its right child through its own right-memory. Thus a rigid system of communication between processors, which moreover is limited to communication with immediate neighbours, is imposed. Other tree arrays of processors with rigid systems of communication are also described in "A Network of Microprocessors to Expedite Reduction Languages", by G. A. Mag, at pages 349 to 385 and 435 to 471, in International Journal of Computer and Information Sciences, Vol. 8, 1979, "A Cellular Computer Architecture for Functional Programming", by G. A. Mago, at pages 179 to 187, 1980, IEEE, "Making Parallel Computation Simple: The FFP Machine", by G. Mago, 1985, IEEE, and U.S. Pat. Nos. 4,251,861 (issued to G. A. Mago) and 4,583,164 (issued to D. M. Tolle). Also, in "Comparing Production System Architectures" by M. Lease and M. Lively, of Computer Science Department, Texas A&M University, College Station, Texas 77843, reference is made to an array of 1023 processors connected to form a complete binary tree designed and built at Columbia University in the City of New York and known as DAD02. Such an array of processors is described in U.S. Pat. No. 4,843,540 issued to S. J. Stolfo and again relies on communication between nearest neighbours in the binary tree.

SUMMARY OF THE INVENTION

According to a first principal aspect of the invention there is provided apparatus for performing parallel processing, the apparatus having a plurality of processor cells, and a communication network, the network being such that a plurality of routes therethrough can co-exist, each such route interconnecting a respective pair of the cells and being established by operation of at least one of the said pair of cells and permitting transmission of data between the pair of cells, and each cell being capable of executing reduction operations in which the cell transforms data therein in accordance with rules for reducing expressions stored as data in groups of the cells. Preferably the communication network has means for forming a partial route in response to a searching signal supplied thereto by a processor cell, and a partial route in response to a free signal supplied thereto by another processor cell, and means to complete the partial route of a searching signal to the point at which a free signal is supplied to the network when the partial route of the said free signal and the partial route of the said searching signal meet. Preferably also, the said rules including rules for the execution of concurrent beta-reduction of functional expressions.

According to a second principal aspect of the invention there is provided a communication network having means for forming a partial route in response to a searching signal supplied thereto, and a partial route in response to a free signal supplied thereto, and means to complete the partial route of a searching signal to the point at which a free signal is supplied to the network when the partial route of the said free signal and the partial route of the said searching signal meet.

According to a third principal aspect of the invention there is provided a processor cell having storage means loadable with a plurality of different categories of data, means for determining the categories of data stored in the storage means and setting the processor in a selected one of a plurality of operative processes thereof in dependence upon the categories of data determined to be stored in the storage means, at least one of the operative processes including a computation step utilizing data stored in the storage means, the processor cell having computation means for executing the said computation step, means for receiving data for storage in the storage means, means for outputting data resulting from operative processes of the processor cell, the means determining the categories of data including means responsive to the presence of data in a category incompatible with the said computation step to inhibit operating of the executing means on such data, and means for outputting a status signal indicative of whether or not the selected operative process is a predetermined resting process.

According to another aspect of the invention there is provided apparatus for performing parallel processing, the apparatus having a plurality of processor cells, and a communication network, the said cells being connected to the communication network, the communication network including a plurality of nodes, each of at least some of the cells being settable, in use, at least in a searching state and in a free state and transmitting into the network a searching signal when in the searching state and a free signal when in the free state, and each node including means for so intercepting a searching signal that reaches the node when a free signal is present at the node that a communication route is established between a cell in the searching state and another cell in the free state through one or more nodes at which such interception occurs.

According to a further aspect of the invention there is provided apparatus for performing parallel processing, the apparatus having a plurality of processor cells, and a communication network, the said cells being connected to the communication network, the communication network including a plurality of nodes, each of at least some of the cells being settable, in use, in a calling state and transmitting into the network a calling signal when in its calling state, each node including means for routing a calling signal in accordance with destination information included in the calling signal and indicative of a route extending from the calling state cell that originates the calling signal to another of the cells and including the said node, and the network including a plurality of binary tree arrangements in which the cells are at leaf positions of each binary tree arrangement and the nodes are at nodal positions of the binary tree arrangements, each cell occupying a different leaf position in at least two binary tree arrangements, such that routes containing different numbers of nodes in the said two binary tree arrangements can be established between two cells.

Preferably the cells are arranged to form a planar array in which a unit pattern of four cells in a square is repeated to form a square array of the cells with the number of cells along any side of the array being an integer power of two.

According to a yet further aspect of the invention there is provided apparatus for performing parallel processing, the apparatus having a plurality of processor cells, and a communication network, the network being such that a plurality of routes therethrough can coexist, each such route interconnecting a respective pair of the cells, each cell being capable of executing a plurality of operations including a set of operations including communication operations, command operations in which the cell transmits command signals into the network to another of the cells, slave operations in which the cell executes commands transmitted thereto by another of the cells through the network, and reduction operations in which the cell transforms data, stored in the cell, in accordance with rules for reducing expressions stored as data in groups of the cells, the communication operations including operations in which the cell receives data from another of the cells through the network, and operations in which the cell transmits data to another of the cells through the network, the number of cells being sufficiently large for the reduction operations of each individual cell to be primitive operations in the rules for reducing expressions. Preferably the rules for reducing expressions are consistent with pure Church lambda calculus. Also preferably each cell includes means for testing data stored within the cell to determine whether a reduction operation can be executed on that data and, if the result of the test is negative, for setting the cell in a state such that the cell continues to store the said data until the cell receives from one or more other of the cells further data which when substituted for or combined with at least part of the first said data creates data giving a positive result to the said test, whereupon the cell executes the reduction operation.

According to another aspect of the invention there is provided apparatus for performing parallel processing, the apparatus having a plurality of processor cells, and a communication network, the network being such that a plurality of routes therethrough can coexist, each such route interconnecting a respective pair of the cells, each cell being capable of executing a plurality of operations including a set of operations including communication operations, command operations in which the cell transmits command signals into the network to another of the cells, slave operations in which the cell executes commands transmitted thereto by another of the cells through the network, and internal operations in which the cell processes data stored in the cell, the communication operations including operations in which the cell receives data from another of the cells through the network, and operations in which the cell transmits data to another of the cells through the network, the cell having a plurality of operative states, and being loadable with data in a plurality of categories, and the cell further including means for determining what categories of data are present therein and for setting the cell in a selected one of its plurality of operative states in dependence upon the combination of categories of data detected as being present in the cell.

According to a further aspect of the invention there is provided a communication network comprising a plurality of nodes and a larger plurality of path segments, each of at least a majority of the nodes forming a junction between at least three path segments, and each node having signal input means and signal output means at the connection of the node to each path segment connected thereto, means for transmitting signals from the input means at any one of the path segment connections thereto to the output means at at least one other path segment connection thereto, and means, responsive to the presence of a conditioning signal at the node received from at least one of the input means, for selecting a path through the node to the output means at the connection of the node to a predetermined one of the path segments for a further signal received in the node after arriving at the respective input means of another path segment at the node. Preferably each node has means responsive to an acquire signal received in the node from a path segment connected thereto for providing a path for the acquire signal through the node to the output means at the connection of the node to a selected other one of the path segments without dependence on the presence or absence of the said conditioning signal.

According to a yet further aspect of the invention there is provided apparatus for performing parallel processing, the apparatus including a plurality of processor cells and communication means for enabling communication between the cells, each cell having means for storing data and being loadable with a plurality of categories of data, and having means for determining the categories of data which are stored therein, means for executing predetermined operations with predetermined categories of data only when such predetermined categories of data are present therein, and means for transmitting data to and receiving data from others of the cells through the communication means, and the means for determining the categories of data including means responsive to the presence of data representing an inhibit command to inhibit operation of the executing means on predetermined categories of data. Preferably the predetermined operations include reduction operations, the categories of data include symbolic data and pointers, and the executing means includes means for determining whether symbolic data and pointers are present in the cell and for inhibiting one or more reduction operations if the determination is affirmative.

Preferred embodiments of the invention are defined hereinafter in appendant claims.

In a particular embodiment of the invention having a communication network as defined by claim 41, each node has means responsive to an acquire signal received in the node from a path segment connected thereto for providing a path for the acquire signal through the node to the output means to a selected other one of the path segments without dependence on the presence or absence of the said conditioning signal. The means responsive to an acquire signal is responsive to the state of a further signal, referred to hereinafter as an address/data signal, to select one or the other of the other path segments when the said further signal is received in the node from the same path segments as the acquire signal. The network is, in this embodiment, in the form of four binary tree arrangement with the nodes of the network at the nodal positions of the binary tree arrangements, and the processor cells at the leaf positions of the binary tree arrangements. Each of a majority of the cells is settable in a free state and has status signal transmitting means which transmits a status signal, indicative of whether the cell is in the free state or not, into the network. When the status signal indicates that the cell is in the free state, the status signal, referred to hereinafter as a free signal, acts as a conditioning signal along a partial route in the network. Each of a majority of the cells is also settable in a calling state in which it transmits into the network a calling signal which includes destination information indicative of a route, to another cell, from the calling cell. The calling signal includes, as a component, the said acquire signal. The said further signal, i.e. the address/data signal, constitutes the component of the calling signal containing the destination information. This embodiment has processor cells which have means for carrying out reduction operations and other operations on categories of data that include symbolic data and pointers. Data on which the apparatus as a whole operates, in this embodiment, constitute lambda expressions, and the reduction operations are based on the pure Church lambda calculus.

Briefly, a preferred embodiment of the present invention in the form of an apparatus for performing parallel processing comprises a large number of processor cells, the majority of which are standard cells which, in a free or resting state, transmit into a communication network a free signal, and others are special cells which are adapted to be coupled to peripheral sources and sinks for data; each cell includes means for storing data; the cells are connected to the communication network; the communication network is in the form of several binary trees having the cells connected at the leaf positions of the binary trees, and having the nodes of the trees formed by switching circuits that allow individual cells to control the formation of signal paths through the nodes; in operation, cells may be in a waiting state, a calling state, a searching state, a communicating state, an internal operation state, or the free state; any standard cell or special cell in a searching state transmits a searching signal into the network where, if the searching signal meets a free signal at a node, a route may be formed, through the network, from the searching state cell to a free state cell; any standard or special cell in a calling state establishes, with a calling signal, a route through the network to another one of the cells which is identified by destination information in the calling signal; any standard or special cell in the waiting state is waiting to be called by a cell in the calling state; and each standard cell is capable, by passing through a sequence of the said states, of copying a configuration of data stored in another of the cells. In a preferred method of operating the preferred apparatus, a functional expression, preferably in the form of at least one lambda expression, which is to be reduced to a final result, is so distributed in groups of the cells that individual cells need only carry out communication, in which data is transmitted between cells, arrangement and discarding of data within cells, and execution of primitive operations within cells. At least initially in the evaluation of a functional expression, at least one of the groups of cells consists of cells each of which is in a waiting state such that the respective group of cells serves as a passive definition of an expression. Furthermore each standard cell in the preferred embodiment includes means for detecting the presence therein of data representing a symbolic name for a defined expression and means which responds to detection of such symbolic data by setting the cell in a communicating state wherein the cell locates a definition of the defined expression constituted by a group of cells, and thereupon enters a sequence of states whereby the cell copies a configuration of data stored in one of the said group of cells and initiates copying by other cells of configurations of data stored in the remaining cells of the said group. Such copying is carried out in a manner that results in those cells which have copied the said configurations of data proceeding to process the data to produce a result contributing to the production of or constituting the said final result. Destination information used by cells in the calling state is in the form of pointers. Destination information may be stored in the cells or in the network, and each cell preferably includes means for computing pointers from destination information. In the preferred embodiment, transmission of a pointer to a cell which has entered a communicating state in response to the cell receiving, whilst in the free state, a searching signal, results in initiation of a procedure in which the cell copies a configuration of data stored in another cell to which the formerly free cell is related by the said pointer.

A preferred communication network according to the invention comprises:

means for forming a partial route in response to a searching signal supplied to the network, and a partial route in response to a free signal supplied to the network; and

means to complete the partial route of a searching signal to the point at which a free signal is supplied to the network when the partial route of the said free signal and partial route of the said searching signal meet, a partial route formed in response to a free signal effecting a conditioning of the said means to complete within a portion of the network. Preferably the network is formed by a plurality of nodes interconnected by a larger plurality of path segments, and the said forming means and means to complete are incorporated in the nodes.

The invention will now be described by way of example with reference to the accompanying drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a block diagram schematically representing an embodiment of the invention;

FIG. 2 is a block diagram of a processor cell of the embodiment of FIG. 1;

FIG. 3 is a schematic representation of a simple network and processor cell apparatus embodying the invention;

FIG. 4 is a schematic representation of part of the embodiment of FIG. 1;

FIG. 5 is a block diagram of a network node of the embodiment of FIG. 1;

FIG. 6 is a circuit diagram of part of a node of FIG. 5.

FIG. 7 is a circuit diagram of part of a node of FIG. 5.

FIG. 8 is a circuit diagram of part of a node of FIG. 5.

FIG. 9 is a circuit diagram of part of a node of FIG. 5.

FIG. 10 is a circuit diagram of part of a node of FIG. 5.

FIG. 11 is a circuit diagram of part of a node of FIG. 5.

FIG. 12 is a circuit diagram of part of a node of FIG. 5.

FIG. 13 is a diagram illustrating the formation of a route from a processor cell issuing a calling signal to a destination processor cell through the network in the embodiment of FIG. 1;

FIGS. 14A and B are diagrams illustrating the formation of a network route from a processor cell issuing a search signal that is intercepted by a free signal from a processor cell in the free state in the embodiment of FIG. 1;

FIG. 15 is a diagram illustrating the use of multiple binary trees in an embodiment of the invention;

FIG. 16 is a schematic representation of a preferred planar array of processor cells interconnected by a binary tree in accordance with the invention;

FIG. 17 is a schematic representation of part of the array of FIG. 16 on a larger scale;

FIG. 18 is a schematic representation of a simple embodiment of the invention having the processor cells disposed in a preferred planar array arrangement and interconnected by two binary trees;

FIG. 19 is a diagram of a preferred planar array of processor cells illustrating a preferred scheme of interconnection of the cells by two binary trees;

FIG. 20 is a diagram illustrating a preferred scheme of interconnection of a preferred planar array of processor cells by four binary trees in accordance with the invention;

FIG. 21 is a diagram illustrating a simple embodiment of the invention having a preferred planar array of processor cells interconnected by four binary trees;

FIG. 22 is a schematic representation of a planar pattern formed by part of an embodiment having four binary trees forming the network;

FIG. 23 is a schematic representation of an embodiment similar to that of FIG. 21 but having 256 processor cells;

FIG. 24 is a diagram illustrating alternative means of providing input and output in an embodiment of the invention;

FIG. 25 is a diagram illustrating the use of lexical arrangements in an embodiment of the invention;

FIGS. 26A, 26B, 26C, 26D, 26F, and 26G are circuit diagrams of parts of communications circuitry in a processor cell of the embodiment of FIG. 1;

FIG. 26E is a graphical representation of signals appearing in the operation of the circuit of FIG. 26D;

FIG. 27 is a graphical representation of a communication operation of a processor cell of the embodiment of FIG. 1;

FIG. 28 is a diagram representing registers in a processor cell of the embodiment of FIG. 1;

FIG. 29 is a diagram illustrating a stage in the use of the embodiment of FIG. 1 to evaluate a lambda expression.

FIG. 30 is a diagram illustrating a stage in the use of the embodiment of FIG. 1 to evaluate a lambda expression.

FIG. 31 is a diagram illustrating a stage in the use of the embodiment of FIG. 1 to evaluate a lambda expression.

FIG. 32 is a diagram illustrating a stage in the use of the embodiment of FIG. 1 to evaluate a lambda expression.

FIG. 33 is a diagram illustrating a stage in the use of the embodiment of FIG. 1 to evaluate a lambda expression.

FIG. 34 is a diagram illustrating a stage in the use of the embodiment of FIG. 1 to evaluate a lambda expression.

FIG. 35 is a diagram illustrating a stage in the use of the embodiment of FIG. 1 to evaluate a lambda expression.

FIG. 36 is a diagram illustrating a stage in the use of the embodiment of FIG. 1 to evaluate a lambda expression.

FIGS. 37A and 37B are diagrams illustrating definitions of function symbols NPLUS1 and NMINUS1 for the domain 0 to 6;

FIG. 37C is a diagram of an alternative starting state for the evaluation represented by FIGS. 29 to 36;

FIG. 37D, is a diagram illustrating loading of cells of the embodiment of FIG. 1 to compute a function NMINUSM for parameters n=4, m=2;

FIG. 38 is a block diagram of a special processor cell of the embodiment of FIG. 1;

FIG. 39 is a block diagram of connections between a peripheral computer used as an input and output device and special cells of the embodiment of FIG. 1;

FIG. 40 is a graphical representation of steps and decisions in executive logic processes in a processor cell of the embodiment of FIG. 1.

FIG. 41 is a graphical representation of steps and decisions in executive logic processes in a processor cell of the embodiment of FIG. 1.

FIG. 42 is a graphical representation of steps and decisions in executive logic processes in a processor cell of the embodiment of FIG. 1.

FIG. 43 is a graphical representation of steps and decisions in executive logic processes in a processor cell of the embodiment of FIG. 1.

FIG. 44 is a gaphical representation of steps and decisions in executive logic processes in a processor cell of the embodiment of FIG. 1.

FIG. 45 is a graphical representation of steps and decisions in executive logic processes in a processor cell of the embodiment of FIG. 1.

FIGS. 46 and 47 are graphical representations of steps and decisions in executive logic processes in a processor cell of the embodiment of FIG. 1.

FIG. 48 is a graphical representation of steps and decisions in executive logic processes in a processor cell of the embodiment of FIG. 1.

FIG. 49 is a graphical representation of steps and decisions in executive logic processes in a processor cell of the embodiment of FIG. 1.

FIG. 50 is a graphical representation of steps and decisions in executive logic processes in a processor cell of the embodiment of FIG. 1.

FIG. 51 is a graphical representation of steps and decisions in executive logic processes in a processor cell of the embodiment of FIG. 1.

FIG. 52 is a graphical representation of steps and decisions in executive logic processes in a processor cell of the embodiment of FIG. 1.

FIG. 53 is a graphical representation of steps and decisions in executive logic processes in a processor cell of the embodiment of FIG. 1.

FIG. 54 is a graphical representation of steps and decisions in executive logic processes in a processor cell of the embodiment of FIG. 1.

FIG. 55 is a graphical representation of steps and decisions in executive logic processes in a processor cell of the embodiment of FIG. 1.

FIG. 56 is a graphical representation of steps and decisions in executive logic processes in a processor cell of the embodiment of FIG. 1.

FIG. 57 is a graphical representation of steps and decisions in executive logic processes in a processor cell of the embodiment of FIG. 1.

FIG. 58 is a graphical representation of steps and decisions in executive logic processes in a processor cell of the embodiment of FIG. 1.

FIG. 59 is a graphical representation of steps and decisions in executive logic processes ina processor cell of the embodiment of FIG. 1.

FIG. 60 is a graphical representation of steps and decisions in executive logic processes in a processor cell of the embodiment of FIG. 1.

FIG. 61 is a graphical representation of steps and decisions in executive logic processes in a processor cell of the embodiment of FIG. 1.

FIG. 62 is a graphical representation of steps and decisions in executive logic processes in a processor cell of the embodiment of FIG. 1.

FIG. 63 is a graphical representation of steps and decisions in executive logic processes in a processor cell of the embodiment of FIG. 1.

FIG. 64 is a graphical representation of steps and decisions in executive logic processes in a processor cell of the embodiment of FIG. 1.

FIGS. 65 is a block diagram of an alternative network node of an embodiment of the invention;

FIGS. 66, 67, and 68 are circuit diagrams of parts of the node of FIG. 65;

FIG. 69 is a schematic representation of part of a modification of the embodiment of FIG. 1;

FIGS. 70 and 71 are schematic circuit diagrams of parts of a modification of the node of FIGS. 5 to 12;

FIG. 72 is a schematic circuit diagram of cell communication circuitry for use with a network having the modified nodes of FIGS. 70 and 71;

FIGS. 73 and 74 are schematic circuit diagrams of parts of another modification of the node of FIGS. 5 to 12;

FIGS. 75, 76A, 76B, 77A, 77B, 78A, and 78B are diagrams illustrating the formation of routes between two cells using a network having nodes with the modification of FIGS. 73 and 74;

FIG. 79 is a diagram illustrating primitive instructions CONS, HEAD, and TAIL; and

FIG. 80 is a state diagram of executive logic of a standard cell of the embodiment of FIG. 1.

FIG. 81 is a state diagram of executive logic of a standard cell of the embodiment of FIG. 1.

FIG. 82 is a state diagram of executive logic of a standard cell of the embodiment of FIG. 1.

FIG. 83 is a state diagram of executive logic of a standard cell of the embodiment of FIG. 1.

FIG. 84 is a state diagram of executive logic of a standard cell of the embodiment of FIG. 1.

FIG. 85 is a state diagram of executive logic of a standard cell of the embodiment of FIG. 1.

FIG. 86 is a state diagram of executive logic of a standard cell of the embodiment of FIG. 1.

FIG. 87 is a state diagram of executive logic of a standard cell of the embodiment of FIG. 1.

FIG. 88 is a state diagram of executive logic of a standard cell of the embodiment of FIG. 1.

FIG. 89 is a state diagram of executive logic of a standard cell of the embodiment of FIG. 1.

FIG. 90 is a state diagram of executive logic of a standard cell of the embodiment of FIG. 1.

FIG. 91 is a state diagram of executive logic of a standard cell of the embodiment of FIG. 1.

FIG. 92 is a state diagram of executive logic of a standard cell of the embodiment of FIG. 1.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

FIG. 1 represents in block form a first example of a digital processing apparatus 10 embodying the invention. The apparatus 10 has a large plurality of processing cells 11. Most of the processing cells 11 have identical structure, and are therefore referred to herein as standard cells 12. Some of the processing cells 11 have a structure which includes some of the structure of a standard cell and additional structure, and such cells are referred to herein as special cells 13. One standard cell 12 and one special cell 13 are indicated in FIG. 1.

The apparatus 10 also has a communication network 14. Each processing cell 11 is connected to the communication network 14, and can establish a communication path to any other cell 11 through the network 14 if required to do so.

The apparatus 10 carries out the functions of data processing and main memory. The additional structure provided in the special cells 13 enables them to act as interfaces between the apparatus 10 and peripheral apparatus (not shown) such as input and output equipment and backing memory. In this first example, the apparatus 10 is the central processing and memory apparatus of a computer that carries out reduction of expressions.

When the apparatus 10 is in operation, each cell 11 is in one of a number of states. These states are referred to herein as the free state, the searching state, the calling state, the communication state, the waiting state, and the internal operation state. The free state is the resting state of a cell 11. A cell 11 automatically switches into the free state whenever it is not required to enter or remain in any other state.

FIG. 2 is a schematic functional diagram of a standard cell 12. The standard cell 12 contains a decoding and control unit 16, network interfacing circuitry, and a small amount of storage in the form of registers 15. A pulse source (not shown) provides pulses for driving the elements of the cell 12, since the cell 12 is constructed mainly of serial circuitry, and communication through the network 14 is serial.

The network interfacing circuitry has four principals functions: status transmission, data transmission, control signal transmission and reception, and data reception.

The status of each standard cell 12 is transmitted into the network 14 by a signal which is high, represented here by F, whenever the cell 12 is in the free state, and is low, represented here by NOT-F or F, whenever the cell 12 is not in the free state. Consequently each cell 12 transmits either F or NOT-F.

In use, some of the processing cells 11 are initially loaded with binary data. A loading operation may be carried out through a special cell 13 which communicates through the network 14 with those cells 11 which are to be loaded by that special cell 13. Such a special cell 13 has input interface structure through which it communicates with a source (not shown) of the binary data. The structure of a special cell 13 is shown in FIG. 38 and will be described hereinafter.

In an initial loading of the cells 11 of the apparatus 10, many such special cells 13 may be used to load different groups of the cells 11 at the same time.

At start up, before any initial loading is carried out, all the cells 11 are set in the free state. This can be effected by circuitry (not shown) of a known kind which generates a pulse at power up of the apparatus 10.

A special cell 13 thus operating as an input cell communicates in turn with each cell 11 which it is to load. A standard cell 12 receives data from an input cell 13 through a communication path established in the network 14 from the input cell 13 to the standard cell 12. Data loaded into a cell 11 represents one or more instructions or one or more names or one or more values, one or more addresses or combinations of such data. Various types of names are used in the present example and will be explained hereinafter.

Address data loaded into a cell 11 represent numerical addresses of one or more other cells 11. A numerical address of a cell 11 is a number uniquely identifying that cell 11 by its point of connection in the communication network 14.

A standard cell 12, and a special cell 13, in the searching state transmits control signals which, in cooperation with the free signals F transmitted by standard cells 12 in the free state, can establish a communication path through the network 14 to a cell 12 in the free state. A searching state ends when such a communication path is established, and it is followed immediately by a communication state in the searching cell 11, and by a communication state in the formerly free state cell 12 now connected through the communication path.

In the communication state, a cell 11 transmits at least control signals to another cell 11 to which it is connected by a communication path through the network 14. The communication state ends when the one cell 11 in this state senses that the other cell 11 has received the whole transmission from the one cell 11, and the other cell 11 has completed any transmission back to the one cell 11.

In the calling state, a standard cell 12, and a special cell 12, carries out operations involving the transmission of control signals and data. The cell 11 in the calling state uses the address of another cell 11, which is to be called, to establish a communication path through the communication network 14 to the cell 11 being called. The calling state ends when the required communication path is established and is immediately followed, in the calling cell 11, by the communication state if the called cell 11 acknowledges the call. If the cell 11 being called is in an appropriate waiting state at least immediately before calling cell 11 completes the communication path to it, the waiting state in the cell 11 called is followed by the communication state.

In the waiting state the cell 11 is not carrying out any internal operation involving the processing of data. Additionally, the cell 11 is not carrying out any operation involved in the transmission of either control signals or addresses and other data. However, the cell 11 does store data ready for use when the cell 11 is called by a cell 11 in the calling state. Also, the waiting cell 11 transmits the not free signal NOT-F, since it is not in the free state, if the cell is a standard cell 12.

In the internal operation state, a cell 11 is carrying out operations involving the decoding and control unit 16. These operations include certain operations on data stored in the registers 15 of the cell 11.

At any particular time during an overall operation of the apparatus 10, any cell 11 that is not in the free state or in the waiting state can, if required to do so, access any other cell 11 that is in the free state or in the waiting state. Cells 11 in the free state serve collectively as spare processing power with available memory space into which data and addresses can be written by other cells 11. Cells 11 in the waiting state may act collectively as a loaded area of memory, and in some cases a cell 11 in the calling state may in effect be carrying out a memory access operation.

A cell 11 in the communication state is writing in or reading from the cell 11 to which it is connected by the established communication path.

A cell 11 in the searching state can be regarded as attempting to find a standard cell 12 that is not currently in use.

The capacity of the memory formed by the cells 11 collectively depends primarily on the number of cells 11 in the system 10. If there are 2.sup.16 cells 11, i.e. 65536 cells 11, a complete numerical address of any cell 11 will, in binary representation, require 16 digits, i.e. 16 bits.

When a cell 12 reverts to the free state it becomes a location in the free, i.e. available, memory space, and is a location with processing power.

The standard cells 12 do not need a program counter. Although it is possible to construct the decoding and control unit 16 as a microprogrammed control and decoding processor, it is more economic to construct the unit 16 of a standard cell 12 as a hard-wired decoder-controller with an instruction register, referred to here as the primitive register. A microprogrammed control and decoding processor requires a source of accurate clock pulses. This source can be a clock pulse bus supplying the unit 16 from a crystal controlled clock pulse generator circuit. Such a microprogrammed processor would typically include a microprogram stored in an area of ROM, and a microprogram counter. The microprogram counter would not otherwise be required in the operations of the cell. It may be preferable to construct the unit 16 of a special cell 13 as a microprogrammed control and decoding processor.

Processing activity in the apparatus 10 creates intermediate results and final results which must be output from the apparatus 10. Such a result must be placed in a special cell 13 having output interface structure. In the present example, each special cell has both input and output interface structure, and it may be arranged that intermediate and final results occur at a respective special cell 13 that served initially as the input cell for some of the data that gave rise to the relevant intermediate or final result. A complex computing problem is solved by solving a large number of simple problems. Each such simple problem involves only a primitive operation. By a primitive operation is meant an operation that is not broken up into a number of simpler operations. Each cell 11 is designed to carry out primitive operations. The apparatus is intended to be used on problems in which the principle of referential transparency holds, so that a complex expression can be evaluated by substitution and the execution of primitive operations.

A complex operation, i.e. an operation requiring the use of a plurality of primitive operations, is given a name which is stored as a bit pattern in one of the registers 15 of a cell 11.. That cell 11 also stores a pointer to one of a group of other cells 11 which includes cells 11 loaded with instructions for executing the pattern of primitive operations which make up the complex operation. The cells loaded with these instructions thus constitute the function body of the complex operation, and together with the name cell and possibly one or more cells that link the function body to the name cell by pointers form the definition of the complex operation. Other data, such as values, which are required in connection with an execution of the complex operation may be stored in the cells another group of cells 11, a further cell 11 storing the complex operation name and also storing a pointer to one cell 11 in this other group. Such groups of cells 11 thus store data structures. Each cell 11 in such a group stores at least a pointer to one other cell 11 in that group. Such stored pointers linking the cells 11 of the group are formed by or from addresses of the cells.

If a primitive operation instruction is stored together with one or more pointers in a cell 11 in which the operation is to be executed, the execution of the primitive operation is inhibited until the stored pointer or pointers have been replaced by the intended values. Such a situation occurs where the values are themselves the results of other operations.

Where a particular complex operation is used more than once in a complex problem, it is essential to ensure that the form of the complex operation and the availability to it of values are not corrupted or destroyed by its use. It is therefore arranged that a cell 11 storing a name representing a complex operation does not directly use the cells 11 storing the primitive operation instructions and values defining the complex operation. Instead, a cell 11 storing the name initiates a process in which those cells are linked to free state cells, the various instructions and values and the pointers needed to enable required communication paths to be established are written into the free state cells, and the cell 11 storing the name has written into it a pointer to at least one of those free state cells written in. The cell 11 storing the name may itself be transformed, by a copying process, into the head of the active definition thus established. Thus the required definition and values for the name are copied from the cells 11 in which they are stored into available memory space. The data in the `copy` cells can be modified, where necessary, by the execution of the complex operation.

To avoid confusion of pointers with instructions, names, and values, some bits of their respective bit patterns are dedicated to characterising the pattern as being (i) a pointer, or (ii) an instruction, or (iii) a name or a value, and the decoding and control unit 16 includes means for identifying each of the three types of pattern.

The communication network 14 is formed of path segments and nodes. The nodes interconnect path segments and are active in determining the communication paths formed between pairs of cells 11. In particular, each node incorporates a means enabling a control signal, referred to here as a search signal, from a cell in a searching state to so interact with a free signal present at the node that the search signal is directed to a cell 11 that has established or contributed to the presence of the free signal at the node.

In the present example, the network 14 consists of four binary trees. The cells 11 are at the leaf positions of the trees, and the nodes referred to hereinbefore are situated at the nodal positions of the trees. Each cell 11 has four ports 18, 19, 20, and 21 (FIG. 2) at which it is connected to the four binary trees respectively.

FIG. 3 illustrates schematically one binary tree 30 of the network 14, with the cells 11 at the leaf positions, but is greatly simplified in that in total only thirty-two cells 11 are shown whereas in practice a tree with thousands of cells 11, and hence as many leaf positions, would be implemented. Five bit binary addresses can be allocated to the cells 11 of FIG. 3 in such a way that each bit in the address of a cell 11 identifies a path segment in the route down the tree from its root node 31. The two lower path segments from any node are distinguished by one being associated with the binary digit `1` and the other being associated with the binary digit `0`. For example, if the cells 11 in FIG. 3 are numbered from right to left: 00000, 00001, . . . 11110, 11111, then every right hand lower path segment is associated with binary digit `0`, and every left hand lower path segment is associated with binary digit `1`. A route interconnecting a pair of cells can be defined by selecting those bits of the respective addresses of the cells which constitute the respective parts of their addresses which differ.

For example, if the complete addresses of two cells are 11100 and 11010, then a route from the cell with address 11100 to the cell with address 11010 is defined by the three least significant bits of the first address, i.e. 100, taken in reverse order, followed by the three least significant bits of the second address, i.e. 010, taken in that order (from most to least significant). The three least significant bits of the first address define the upward or ascending branch of the route, and the three least significant bits of the second address define the downward or descending branch of the route. The part of the two complete addresses which is common to both, in this case the two most significant bits, which are 11, defines the position of the node at which the ascending and descending branches of the route meet. This example is illustrated in FIG. 3. In general, the address of any one cell at a leaf position of a binary tree differs from the address of any other cell at a leaf position of the tree by at least one bit, which is the least significant bit, and if two cells have part of their addresses in common, that part will include at least the most significant bit, and will consist of only the most significant bit or bits of their addresses. The terms upward and ascending are here used in relation to a binary tree arrangement to mean in the direction towards the root node of the tree, and similarly the terms downward and descending are used to mean in the direction away from the root node. The terms upper and lower and higher and lower are also used herein in relation to positions nearer and further away from the root node.

It will be seen from FIG. 3 that each node, except the root node 31, is the junction between three path segments: an upper segment, a left hand lower segment, and a right hand lower segment. The upper segment at any node is of course either a left hand lower segment or a right hand lower segment of the next higher node.

FIG. 4 illustrates, for a binary tree 40 of sixteen leaf positions, the logic of the free signal transmission from the cells 11. The tree of FIG. 4 may be regarded as part of a larger binary tree. As shown, at each node position there is a two input OR gate 41 for free signals being transmitted into the tree from cells 11 in the free state. Each OR gate at the lowest level of the tree has its inputs 42 supplied by the two cells 11 connected to the lower segments from the node. The output from an OR gate supplies one input of the OR gate at the next higher level. The signals at the inputs to an OR gate are also supplied to the remainder of the node, represented in FIG. 4 by a square such as at 43, through connections such as those indicated at 44. As a result of this arrangement, the presence of a free signal at a high level node of the tree can be established by any one or more of the cells 11 at the leaf positions depending from that node. For example, the presence of a free signal at the highest node, 45, in FIG. 4 indicates that at least one of the sixteen cells 11 in FIG. 4 is in the free state. Furthermore, the free signal from any cell 11 conditions the nodes in the route from that cell 11 to the root node of the tree, unless intercepted by a search signal, as will be explained hereinafter.

FIG. 5 illustrates schematically in block form one example of a preferred structure for a node of the network 14. The OR gate 41 and its connections 42 and 44 are shown again. The left hand lower path segment includes a left hand lower upwards channel 51, and a left hand lower downwards channel 52. Similarly the right hand lower path segment includes a right hand lower upwards channel 53 and a right hand lower downwards channel 54. The upper segment includes an upwards channel 55 and a downwards channel 56.

The lower upwards channels 51 and 53 and the free signal connections 44 enter an upwards arbiter 57 that supplies an upwards/crossover selector 58 that supplies the upwards channel 55 and a crossover channel 59. The upper downwards channel 56 and the crossover channel 59 supply a downwards arbiter 60 that supplies a downwards left/right selector 61 from which the left hand and right hand downwards channels 52 and 54 extend. The free signal connections 44 are also connected to the left/right selector 61.

The upwards arbiter 57 allows control signals on only one of the upwards channels 51 and 53 to pass to the upwards/crossover selector 58. As will be explained, the arbiter 57 ensures that the first active control signal to reach it from the channels 51 and 53 is the one that is passed to the selector 58. The later signal is merely blocked until the transaction initiated by the first signal has ended, whereupon the arbiter 57 passes the later signal to the selector 58.

The upwards/crossover selector 58 determines, in response to control signals that it receives from the arbiter 57, whether it is to the upwards channel 55 or to the crossover channel 59 that the arbiter 57 is connected.

The downwards arbiter 60 allows control signals on only one of the downwards channel 56 and the crossover channel 59 to pass to the left/right selector 61. Again the first active signal to arrive is the one passed to the selector 61, and the later signal is merely blocked.

The left/right selector 61 determines, in response to control signals that it receives from the arbiter 60 or in response to an active free signal on one of the connections 44, whether it is to the left hand lower channel 51 or to the right hand lower channel 54 that the arbiter 60 is connected.

The output from the OR gate 41 is supplied through a line 62 to a connection corresponding to one connection 44 and one input to the OR gate of the next higher node. Similarly, the pairs of connections 42 and 44 at the inputs to the OR gate 41 shown in FIG. 5 are supplied through corresponding lines 62L and 62R from the respective OR gates of the two lower nodes, or, if the node of FIG. 5 represents a lowest node, from a pair of adjacent cells 11.

It will be seen from FIG. 5 that the upper path segment from a node consists of a free signal line 62, an upward channel 55, and a downward channel 56, the left hand lower path segment consists of a free signal line 62L, an upward channel 51, and a downward channel 52, and the right hand lower path segment consists of a free signal line 62R, an upward channel 53, and a downward channel 54. The upper line 62 and channels 55 and 56 become either the left hand line 62L and channels 51 and 52 or the right hand line 62R and channels 53 and 54 of the next higher node.

Upward and downward channels 55 and 56 are physically distinct and do not interfere with one another.

Each of the channels 51 to 56 contains three lines: an acquire signal line, an address/data signal line, and an acknowledge signal line.

As shown in FIG. 2, each port 18, 19, 20, or 21 of a standard cell 12 is the origin of a free signal line 62, an outgoing acquire signal line 63, an outgoing address/data signal line 64, and an outgoing acknowledge signal line 65, and the destination of an incoming acquire line 66, an incoming address/data line 67, and an incoming acknowledge line 68. The outgoing acquire and address/data signal lines 63 and 64 together with the incoming acknowledge line 68 make up an upwards channel 55 from the cell 12, and the incoming acquire and address/data signal lines 66 and 67 together with the outgoing acknowledge signal line 65 make up a downwards channel 56 to the cell 11. Since in the present example the cell 12 is at a leaf position in four binary trees, there are four ports and therefore four such groups of lines 62 to 68.

Each network port of a special cell 13 is the origin of an outgoing acquire signal line 63, an outgoing address/data signal line 64, and an outgoing acknowledge signal line 65, and the destination of an incoming acquire line 66, an incoming address/data line 67, and an incoming acknowledge line 68. A special cell 13 provides a connection to a free signal line 62L or 62R of the node to which a network port of the cell 13 is connected directly, but does not transmit the free signal, the said connection being held permanently low.

The arbiter 57 and the selector 58 are shown in detail in FIG. 6, in which the connections 44 and the inputs 42 to the OR gate 41 are distinguished by a letter L to indicate those connected to the left hand path segment free signal line 62L and a letter R to indicate those connected to the right hand path segment free signal line 62R. Similarly, the outgoing and incoming lines for other signals are allocated L and R where necessary to indicate whether they belong to a left hand lower path segment (L) or a right hand lower path segment (R). The exchange of positions of the channels 51 and 52 implied by FIG. 6 is, for simplicity, omitted from FIG. 5.

At output from a cell 11 in the calling state, the outgoing acquire and address/data signals are used as control signals for establishing the route from the calling cell 11 to the desired destination cell 11. Initially, in the calling state, the cell 11 sets the acquire signal high, corresponding to logic 1, and the address/data signal low, corresponding to logic 0. Assuming that FIG. 6 represents the first node above the calling cell 11, and that the other cell 11 that is coupled to this node is not attempting to seize the node, if the calling cell is at the end of the left hand lower path segment (left cell), an OR gate 71 and two AND gates 72 and 73 receive signals from the calling cell and determine the operation of the node. The high output from the OR gate 71 sets a left/right latching circuit 74 so that a high signal appears at the output of an OR gate 75, and the AND gate 73 and two line switches 76 and 77 are enabled by the latching circuit 74. Since the cell at the end of the right hand lower path segment (right cell) is supplying a low signal on its outgoing acquire and address/data lines 63R and 64R, the corresponding OR gate 78 and AND gates 79 and 80 receive low inputs, and the AND gate 80 and the two corresponding line switches 81 and 82 are not enabled by the latching circuit 74.

It should be noted that in FIG. 6 and other gate circuit diagrams of the accompanying drawings, a convention is used in which an input connection for an enabling signal to a gate or a switch is represented by a dot at approximately the centre of the graphical symbol representing the gate or switch, and it is to be understood that if the enabling signal applied there is high, the output signal from the gate of switch is determined by the state(s) of the other input signal or signals to the gate or switch and the logical nature of the gate or switch, and if the enabling signal applied is low, the output signal from the gate or switch is low.

Each of the line switches 76, 77, 81 and 82 is a circuit which has one signal input, one signal output, and an enabling input. When the line switch receives a high signal at its enabling input, the input signal at its signal input appears at its signal output. When the line switch receives a low signal at its enabling input, the signal at its signal output is low, regardless of the state of the signal at its signal input. For example, the output signal from the AND gate 72 passes through the line switch 77 if the signal applied to the enabling input, represented by a central dot in item 77 in FIG. 6, is high, whereas if the signal applied to the enabling input is low, the output signal from the line switch 77 is low. Further line switches are used in the circuitry of the node.

Since the AND gate 72 receives a low input at its address/data input, its output is low. The outputs from the line switches 77 and 82 are therefore both low and an OR gate 83 fed by these two outputs supplies a low input to an inverter at one input of an AND gate 84 supplying the outgoing upward acquire signal line 63 of the node. The gate 84 is thus enabled to apply whatever signal appears at its other input to the line 63.

The low outputs from the AND gate 72 and the line switch 82 also set low the outputs of two AND gates 85 and 86 that supply two of the inputs of an OR gate 87. The other two inputs to the gate 87 are from the AND gates 73 and 80 and are therefore also low. Consequently the two inputs to an OR gate 88 that supplies the outgoing upward address/data signal line 64 are also low.

Two AND gates 89 and 90 receive respective low inputs from the AND gate 72 and the line switch 82, so that an OR gate 91 that ORs their outputs supplies a low signal to an upwards/crossover latching circuit 92. When the latching circuit 92 receives low inputs from the OR gates 87 and 91 and a high input from the OR gate 75, the upwards/crossover latching circuit 92 supplies a high output to the AND gate 84, and enables the OR gate 88 and a line switch 93, and triggers a monostable 94. The AND gate 84 makes the line 63 high in this case since it is enabled, and the OR gate 88 sets the line 64 low, so that the respective high and low signals at the lines 63L and 64R now appear at the upper outgoing lines 63 and 64 respectively. The enabling of the line switch 93 couples the incoming acknowledge line 68 of the upper path segment through an OR gate 95 to the line switches 81 and 76. The triggering of the monostable 94 causes an acknowledge pulse to be emitted from the monostable 94 through the OR gate 95 and the line switch 76 to the left hand acknowledge signal line 68L and thus to the left cell, which is the calling cell.

Since the circuitry is symmetrical, a corresponding operation can be effected from the right hand cell if the left hand cell is not attempting to seize the node.

If both cells attempt to seize the node, the left/right latching circuit 74 enables the cell whose signals arrive first to seize the node. FIG. 7 shows the left/right latching circuit 74 in detail. Inputs from the left cell are supplied to input and output AND gates 96 and 97, and inputs from the right cell are supplied to input and output AND gates 98 and 99, from input connections 100 and 101 respectively. In higher nodes, the signals supplied to the connections 100 and 101 originate from the respective left and right lower nodes. The input signals are supplied through delay elements 102 and 103 to the AND gates 97 and 99.

Starting from the condition in which there are low input signals at 100 and 101 and low output signals at the outputs 104 and 105 of the AND gate 97 and 99, it will be seen that an intermediate latch formed by two cross-coupled NAND gates 106 and 107 may be in any state. As soon as the signal at 100 or 101 changes to high, a high signal appears at the output of the corresponding input AND gate 96 or 98 since both AND gates 96 and 98 are enabled by their other inputs, which have inverters for this purpose. The appearance of a high signal at the output of either AND gate 96 or 98 forces the corresponding NAND gate of the latch to produce a high output, and the other NAND gate to produce a low output. For example, if 100 goes high, gates 96 and 106 produce high outputs, and gate 107 produces a low output. The high and low outputs from the latch correspondingly enable and disable the output AND gates. A high output at an output AND gate disables the input AND gate of the other side of the circuit. For example, if the gate 97 produces a high output, the inverter at the corresponding input to the input AND gate 98 ensures that the gate 98 produces a low output. Consequently, if for example, the signal at 101 goes high after the signal at 100 has gone high, the high signal at 101 has no effect on the output signals at 104 and 105.

The purpose of the delay elements 102 and 103 is to ensure that, following any change in the signals at the inputs 100 and 101, the latch NAND gates have time to operate in accordance with the new input signals and condition the output AND gates 97 and 99 before the new input signals are applied to the AND gates 97 and 99.

The output 104 is connected at 108 to the enable inputs of the gate 73 and switches 76 and 77, and the output 105 is connected at 109 to the enable inputs of the gate 80 and switches 81 and 82, as indicated in FIG. 6. Thus the set of one AND gate 73 or 80 and two line switches 76 and 77 or 81 and 82 associated with the input signal at 100 or 101 that arrives first is the set that is enabled, the other set of gate and switches remaining or becoming disabled.

The outputs 104 and 105 are connected to the inputs of the OR gate 75 so that seizure of the node through the operation of the latching circuit 74 in response to a high input signal at either 100 or 101 results in a high input to the upwards/crossover latching circuit 92.

It will be seen that the latching circuit 74 is symmetrical except for a third, inverted input to the gate 96, with a connection 110 to the input connection 101. The presence of the connection 110 and the third, inverted input to the gate 96 ensures that if high signals appear simultaneously following low signals, at both 100 and 101, one of the input gates, in this example the gate 98 connected to the input connection 101, will be driving gate and the other input gate, in this example the gate 96, will be inhibited. Thus the response of the latching circuit 74 is predictable for all input signal logic conditions.

FIG. 8 shows the detail of the upwards/crossover latching circuit 92. The circuit 92 receives the output from the OR gate 75 at an input connection 111, the output from the OR gate 87 at an input connection 112, and the output from the OR gate 91 at an input connection 113. The signal at 111 is applied directly to two input AND gates 114 and 115, and through delay elements 116 and 117 to two output AND gates 118 and 119. The outputs from the gates 118 and 119 are coupled through an OR gate 120 to inverted inputs of the input gates 114 and 115 so that the presence of a high output signal at either output gate 118 or 119 inhibits both input gates 114 and 115, thereby rendering the circuit 92 unable to respond to signal changes at the input connection 112.

The input connection 113 is connected to one inverted input of one NAND gate 121 of a latch, the other NAND gate 122 of which has only two inputs. When the signal on the input connection 113 is low, the latch NAND gates 121 and 122 operate between the input gates 114 and 115 and the output gates 118 and 119 in the same manner that the latch gates 106 and 107 operate in the context of the circuit 74.

In the present example of operation in which one of the left and right cells is in the calling state and the other is not attempting to seize the node, the signals at the input connections 112 and 113 are both low, so that, in response to a high signal appearing at the input connection 111 and assuming that both output AND gates 118 and 119 were before that time producing low output signals, the input AND gate 114 produces a high output signal, and the gate 115 produces a low output signal. The output signals from the NAND gates 121 and 122 are therefore respectively high and low, and the output AND gate 118 produces a high output signal on a connection 123 after the delay introduced by the delay element 116, and the OR gate 120 supplies an inhibiting signal to the input gates 114 and 115. The circuit 92 will become responsive again if the signal at 111 goes low for longer than the relaxation time of the elements 116 and 117.

This inhibition of the input AND gates 114 and 115 is needed since high signals are subsequently to be transmitted through the gates 87 and 88 (FIG. 6) to the outgoing address/data line 64 from, in this example of operation, the left hand outgoing address/data line 64L.

The connection 123 supplies the output signal of the gate 118 to the AND gate 84 that feeds the outgoing acquire signal line 63, as indicated in FIG. 6, from which it will also be seen that this signal determines whether the gate 88 and switch 93 are enabled, and whether the monostable 94 is triggered. The monostable 94 is of the type that is triggered by a rising edge, so that an acknowledge pulse is generated whenever the signal on the connection 123 goes from low to high.

The gate 119, in the present example of operation, applies a low signal to a connection 124.

If the calling cell, in this example the left cell, applies a high address/data signal with a high acquire signal to the OR gate 71 (FIG. 6), the circuitry as described so far operates as described except in the following respects.

Since the gate 73 is open, a high signal from the address/data signal line 64L reaches the OR gate 87 which therefore applies high signals to the gate 88 and the input connection 112 of the circuit 92. The signal at 112 is supplied by a connection 125 to an inverted input of the gate 114, so that the high signal closes the gate 114 and opens the gate 115. Thus the NAND GATE 122 receives a high input signal at its inverting input, and the gate 121 has a low input signal at both of its inverting inputs. Consequently the output AND gate 119 produces a high output signal on the connection 124, and the AND gate 118 produces a low output signal on the connection 123. As a result, the signal on the outgoing acquire line 63 from gate 84 is low, the gate 88 and switch 93 remain disabled, and the monostable 94 is not triggered. It will be seen from FIG. 6 that the high output from the AND gate 73 also appears on a connection 126.

FIG. 9 shows in more detail the selector 58 and the arbiter 60 of FIG. 5.

From FIG. 9 it will be seen that the connection 124 from the latching circuit 92 supplies an input to a downward/crossover latching circuit 127, and the connection 126, from the AND gate 73 of FIG. 6, supplies one input of an AND gate 128 having an enable input controlled by one output connection 129 from the latching circuit 127. The AND gate 128 also has an inverted input supplied by a connection 130 from the OR gate 83. The output signal from the OR gate 83 is low whenever the node is seized by a high acquire signal on either line 63L or 63R, as can be seen from the operation of the gates 72 and 79 (FIG. 6).

The latching circuit 127 also receives input signals from the incoming acquire signal line 66 and the incoming address/data signal line 67 of the channel 56 through an OR gate 131. The circuit 127 is identical to the latching circuit 74 of FIG. 7, as can be seen from FIG. 10 which shows the circuit 127 in detail. Starting from a condition in which the signal on the connection 124 and the output signal from the OR gate 131 are both low, if the signal on the connection 124 goes high first, a high output signal is produced at the output connection 129 of the circuit 127, and a low output signal at its other output connection 132. These two output signals are ORed by an OR gate 133 which in this operation produces a high output signal. The high signal at 129 enables the AND gate 128, another AND gate 134, and three line switches 135, 136, and 137. The low signal at 132 holds three further line switches 138, 139, and 140 closed. Disabling of the switch 138 blocks any incoming high signals on the incoming address/data line 67. Disabling of the switch 140 ensures that any high output signals from an AND gate 141 supplied by the line 67 and, through an inverting input, any low signals on the incoming acquire line 66, are blocked.

FIG. 11 shows the arbiter 60 and the selector 61 of FIG. 5 in detail.

Address/data signals on the connection 126 from the gate 73 (FIG. 6) pass, in the present mode of operation, through the gate 128 to an OR gate 142. This OR gate 142 also has an input from the line switch 137, which is supplied through a connection 143 from the AND gate 85 (FIG. 6), which in this case is low as a result of the low signal from the gate 72, and an input from an OR gate 144. The gate 144 has an input from the line switch 138 which, in this case, is disabled and therefore supplies a low signal, and inputs from the AND gate 134 and the line switch 136. The gate 134 is open because there is a low signal on the connection 130. The other input to the gate 134 is supplied on a connection 145 from the gate 80 (FIG. 6) which in the present case is supplying a low output signal, so that the gate 134 supplies a low signal to the OR gate 143. The switch 136, which is in this case enabled, supplies, from a connection 146, the output signal from the AND gate 86 (FIG. 6) which in this case is low because the line switch 82 is disabled. Consequently the address/data signals on the connection 126 are able to pass through the gate 142 to a line switch 147 controlled by a downward left/right latching circuit 148.

The line switch 140, being disabled, supplies a low signal to two NAND gates 149L and 149R which as a result enable both sides of the latching circuit 148. Both sides of the latching circuit 148 receive input signals from the OR gate 144,at input connections 150 and 151, which in this case are both low. The circuit 148 is thereby conditioned to couple the high input signal it receives from the OR gate 133 to a right hand output connection 152, and to set its left hand output connection 153 low. The signals on the connections 152 and 153 are supplied as inputs to respective right and left AND gates 154 and 155 with inverted control inputs from an OR gate 156. In the present case, the OR gate 156 receives low inputs from the line switches 140, 136, and 137 so that the AND gates 154 and 155 are open to allow a high signal to appear on the right hand incoming acquire signal line 66R to the right cell, and a low signal to appear on the left hand incoming acquire signal line 66L to the left cell. Also, since the right side of the circuit 148 is enabled, the line switch 147 is enabled by a signal on a connection 157 from the circuit 148 so that the address/data signals on the connection 126 appear on a right hand incoming address/data signal line 67R to the right cell.

If the circuit 127 had been seized by a signal crossing over from the right cell, the right cell being in the calling state and the left cell in the waiting state, a high signal would have been applied to the connection 145, resulting in the left hand side of the circuit 148 being enabled and the right hand side disabled. The line switch 147 would then be disabled and a line switch 158 enabled. A high signal would appear on the left hand incoming acquire signal line 66L to the left cell, and a low signal on the line 66R. Address/data signals would be transmitted to the left cell on the line 67L.

Acknowledge signals are applied by the left and right cells on outgoing acknowledge signal lines 65L and 65R respectively that are coupled through an OR gate 159 to the line switches 139 and 135. The circuit 148 has means for generating an acknowledge pulse that is supplied through a connection 160 to the gate 159.

It will be seen from FIG. 4 that if the node is a higher node, and therefore has its lower path segments connected to two lower nodes rather than to two cells, free signals may be present on either or both of the free signal lines 62L and 62R when an acquire signal from a calling cell seizes the latching circuit 74. However since the outputs from the gates 85 and 86 are then both low, the free signals have no effect on the latching circuit 92 and no effect on the gate 88. Furthermore, if the acquire signal crosses over and seizes the latching circuit 127, the signals on the connections 143 and 146 are both low for the same reason, and the signals applied by the line switch 140 to the gates 149L and 149R are both low so that these two gates enable both sides of the latching circuit 148 whether or not there are free signals present at lines 62L and 62R. Thus the passage of an ascending acquire signal that seizes the node is unaffected by the presence or absence of free signals at the node.

A high signal that crosses over from the latching circuit 92 on the connection 124 to the latching circuit 127 is in competition with high signals output by the OR gate 131. FIG. 10 shows that the output from the OR gate 131 is supplied to an input connection 161 of the circuit 127 that supplies an input directly to one input AND gate 162 and through an inverter to an input of the other input AND gate 163. Consequently if high signals appear simultaneously at the input connections 124 and 161, the circuit 127 is seized by the high signal from the OR gate 131.

When an acquire signal on the incoming line 66 seizes the latching circuit 127, a high signal appears at the output connection 132 and a low signal appears at the output connection 129. As a result, the gates 134, 128, and switches 135, 136 and 137 are disabled, and the switches 138, 139 and 140 are enabled. The high signal at line 66 establishes a low output from the AND gate 141 and hence from the gate 140. The NAND gates 149L and 149R therefore enable both sides of the latching circuit 148, so that the circuit 148 is unaffected by the presence or absence of free signals on the lines 62L and 62R. The high output signal from the OR gate 133 is transmitted to either the connection 152 or to the connection 153 in dependence upon the state of the signal on the address/data line 67 passed through the OR gate 144 to the connections 150 and 151. This signal is then passed either to the right address/data line 67R or to the left address/data line 67L depending on which of the two line switches 147 and 158 is enabled. The OR gate 156 receives only low inputs, so that the AND gates 154 and 155 are enabled.

FIG. 12 shows the latching circuit 148 in detail.

In the circuit 148, the output from the OR gate 133 is supplied through a connection 170 directly to two input AND gates 171 and 172, and through delay elements 173 and 174 to output AND gates 175 and 176. The outputs of the AND gates 175 and 176 are supplied respectively through connections 152 and 153 to the gates 154 and 155, to an OR gate 177, and through connections 157 and 178 to the enable inputs of the line switches 147 and 158. The output from the gate 177 is supplied to inverting inputs of the input AND gates 171 and 172 and to the triggering input of a monostable 179, the output of which is applied to the connection 160.

The output of the OR gate 156 is applied through a connection 180 to an inverter at an enable input to the monostable 179, so that the monostable 179 is enabled unless the gate 156 outputs a high signal.

The outputs from the NAND gates 149L and 149R are supplied respectively through connections 181 and 182 to two AND gates 183 and 184 that respectively control the steering inputs to the output AND gates 175 and 176 through connections 185 and 186.

The AND gates 183 and 184 are incorporated in a NAND gate latch with NAND gates 187 and 188 supplied respectively with the outputs from the input AND gates 171 and 172, so that the output of the AND gate 183 is supplied directly to the one input of the NAND gate 188, and the output of the AND gate 184 is supplied directly to one input of the NAND gate 187. When high signals are present on both connections 181 and 182 from the NAND gates 149L and 149R, the latch 183, 184, 187, 188 operates as though the AND gates 183, 184 were transparent. If a high signal is present on only one of the connections 181 and 182, only the corresponding AND gate 183 or 184 may supply a high signal to its output AND gate 175 or 176.

It will be seen from FIGS. 11 and 12 that if the output on connections 150 and 151 from the OR gate 144 is high, a high signal is applied to the gate 171 and low signal to the gate 172, so that if there is a high signal on the connection 170, and the gates 183 and 184 are transparent, the gate 175 will supply a high signal to the gate 155, and the gate 176 will supply a low signal to, the gate 154. Similarly, a low signal from the OR gate 144 when there is a high signal at 170 and the gates 183 and 184 are transparent will produce a high signal from the gate 176 and a low signal from the gate 175. Thus the state of the signal on the address/data signal line 67 can steer the route through the node to the left lower path segment or to the right lower path segment, the left segment being selected by a high address/data signal and the right segment being selected by a low address/data signal. This arrangement makes it possible to use the address of a cell, or part of its address, as the control data that selects the downwards part of the incoming route to the cell.

The appearance of a high signal at the output of the OR gate 177 when there is a low signal on the connection 180 triggers the monostable 179, which is triggered by a rising edge, thereby generating an acknowledge pulse that is transmitted through the connection 160 and the OR gate 159. The reception of an acknowledge pulse by the calling cell from the line 65 causes the cell to apply the next steering bit to the address/data line 67.

When an acquire signal crosses over from the left lower segment to the right lower segment, the address/data signal crosses over on the connection 126 and does not affect the circuit 148, which is steered by the low signals from the switch 136, gate 134, and switch 138. However, when an acquire signal crosses over from the right lower segment to the left lower segment the address/data signal crosses over on the connection 145 and therefore is supplied through the OR gate 144 to the input connections 150 and 151 of the circuit 148. The address/data signal is set high to cause the latching circuit 92 to select the crossover connection 124, and to ensure that the latching circuit 148 is steered to produce a high output at the left output connection 153 and a low output at the right output connection 152. Left to right crossover is not distinguished from right to left crossover by the calling cell, which sets its address/data line 64 high for any crossover in order to provide a high signal at the input connection 112 of the upwards/crossover latching circuit 92.

A cell in the searching state produces a high address/data signal and a low acquire signal on its outgoing lines 64 and 63. The response of a node will now be described, starting with FIG. 6, to an outgoing search reaching the node from the lower left segment. For simplicity it is first assumed that the signals on the lines 63R and 64R are both low, and that there are no free signals at the node, i.e. the signals on lines 62L and 62R are both low.

The OR gate 71 produces a high output that seizes the latching circuit 74 and results in the gate 73, and switches 76 and 77 being enabled, the gate 80, and switches 81 and 82 remaining disabled, and a high output from the OR gate 75. The AND gate 72 also produces a high output because the lines 63L and 64L are respectively low and high, so that a high signal passes to the OR gate 83, and the AND gate 84 provides, as a result, a low signal on the acquire line 63. The AND gate 85 produces a low output signal because there is no free signal at 44R. Therefore the AND gate 89 supplies a high signal through the OR gate 91 to the inverting input of the NAND gate 121 of the latching circuit 92 (FIG. 8). This ensures that the AND gate 118 supplies a high signal on the connection 123, and that the AND gate 119 supplies a low signal on the crossover connection 124. The high output from the AND gate 72 is also applied to an inverting input of the AND gate 73 which therefore produces a low output signal. The low signal from the AND gate 73 passes through the OR gate 87 to the connection 112 where it is applied to the input AND gate 115 of the circuit 92, and to the OR gate 88 which receives a high input from the OR gate 83. Hence a high signal is supplied to the outgoing address/data line 64. The signals supplied to the gates 134, 128, and switches 135, 136 and 137 on the crossover connections 145, 126, 146 and 143 are all low so that the activity of the circuitry of FIG. 6 does not affect the circuitry of FIG. 11. The signal supplied to the gates 134 and 128 on the crossover connection 130 is high.

Since the circuitry of FIG. 6 is symmetrical for a combination of a high address/data signal on line 64R and a low acquire signal on line 63R in the absence of free signals, such a combination is passed in the same way to the outgoing line 64 and 63 of the upper path segment.

Competition between combinations of high address/data signals and low acquire signals arriving simultaneously at the lines 64L, 63L, 64R, and 63R is resolved by the latching circuit 74 as described for high acquire signals, since the OR gates 71 and 78 mask the difference between high acquire and high address/data signals.

If when a combination of a high address/data signal on line 64L and a low acquire signal on line 63L seizes the latching circuit 74 there is a free signal present on the line 62R, a high signal is supplied to the AND gate 85 through the connection 44R, and a high signal is therefore applied by the gate 85 to the inverted input of the AND gate 89, which therefore outputs a low signal. The line switch 82 is disabled, so that the AND gate 90 outputs a low signal. The signal on the connection 113 from the OR gate 91 is therefore low and the NAND gate 121 is enabled to respond to inputs from the AND gate 114 and the NAND gate 122. The high output from the gate 85 is also supplied through the connection 143 to the OR gate 87 which therefore enables the AND gate 115 and disables the AND gate 114. Consequently the latch 121, 122 supplies a high signal to the gate 119 and a low signal to the gate 118, thereby transmitting the high signal on the connection 111 to the crossover connection 124, and establishing a low signal on the connection 123. Thus the outgoing lines 63 and 64 are set low, the monostable 94 is not triggered, and a high signal is supplied to the gate 163 of the circuit 127 (FIG. 10).

If the high signal at 124 seizes the circuit 127, a high signal appears at the connection 129 and a low signal at the connection 132, and the circuit 148 receives a high input on the connection 170. The high signal on the connection 143 from gate 85 passes through the line switch 137 to the OR gate 142. The signals to the OR gate 144 from switch 138, gate 134, and switch 136 are low, and the signals to the NAND gates 149L and 149R are low, so that the circuit 148 selects the connections 152 and 157 to be high, and connections 153 and 178 to be low. The high signal from connection 143 also passes through the OR gate 156 and therefore disables the monostable 179 and the AND gates 154 and 155. Hence a high signal appears on the address/data line 67R, and low signals remain on the acquire line 66R, and the address/data line 67L and the acquire line 66L.

It will be appreciated from the foregoing description that the presence of the free signal on the line 62R has resulted in the combination of the high address/data signal on line 64L and the low acquire signal on line 63L producing a high signal on the connection 143 that ensures that the same combination crosses over to proceed down the right hand path segment. Similarly, a free signal on line 62L can intercept and cause crossing over of a high address/data signal, low acquire signal combination on the lines 64R and 63R that seizes the latching circuit 74.

For the communication state, the address/data lines must be able to transmit both high and low signals. Therefore after a route has been established between a searching cell and a free cell, the acquire signal from the searching cell is set high while the address/data signal is still high, and the nodes along the route maintain the route and allow data to be transmitted as the address/data signal. The OR gates 71, 78 (FIG. 6), and 131 (FIG. 11) ensure that the change from high address/data to high acquire has no effect on the routes established. The AND gates 72 and 79 respectively supply low output signals as soon as the corresponding acquire signal, on line 63L and 63R, goes high, so that data can be transmitted through the AND gate 73 or 80, and, if there has been crossover, through AND gate 128 or 134. The high output from the OR gate 120 isolates the latch 121, 122 from data on the connection 112. Similarly, the latch 183, 184, 187, 188 of circuit 148 (FIG. 12) is isolated from data on the connections 150 and 151 by the OR gate 177.

When a high address/data signal and a low acquire signal on the incoming lines 67 and 66 from the upper path segment seize the latching circuit 127, a high signal is supplied from the AND gate 141 (FIG. 11) through the line switch 140 to the NAND gates 149L and 149R, which are thereby enabled to respond to the presence or absence of free signals on the lines 62L and 62R. The high address/data signal on line 67 passes through the line switch 138 and the OR gate 144 to the connections 150 and 151. If there are no free signals present, the NAND gates 149L and 149R apply low signals to the AND gates 183 and 184 (FIG. 12), thereby preventing the high signal on connections 150 and 151 from seizing the circuit 148. Thus high signals produced on the connections 181 and 182 in the absence of free signals at the node are changed by the occurrence of the high address/data signal and low acquire signal at the lines 67 and 66 t