WO1991011770A1

WO1991011770A1 - Circuit arrangement of a cellular processor

Info

Publication number: WO1991011770A1
Application number: PCT/HU1991/000004
Authority: WO
Inventors: Tamás LEGENDI; József TÓTH; Antal ZSÓTÉR
Original assignee: Cellware Kft.
Priority date: 1990-02-01
Filing date: 1991-02-01
Publication date: 1991-08-08
Also published as: HU900629D0; AU7188191A

Abstract

The present invention refers to a circuit arrangement of a cellular processor of homogeneous structure and inhomogeneous operation comprising a cellular field (1) consisting of a regular arrangement of cells (3) interconnected by a control bus (24) and a switching network (2) connected to the cells (3) arranged at the edges (N, E, S, W) of the cellular field (1) and to a system bus (23), wherein each cell (3) comprises a maskable equality comparator (10) for associative addressing of other cells (3), the switching network (2) includes inputs and outputs (NI, NO, EI, EO, SI, SO, WI, WO) connectable to respective switching networks (2) of adjacent circuit arrangements (100), means for receiving and processing microcommands (4, 56) and a by-pass circuit (16) for determining and storing a by-pass path between the cells (3), the by-pass circuit (16) consisting of at least four by-pass circuit modules (161, 162, 163, 164) being assigned to the edges (N, E, S, W) and comprising each means for storing and determining (17, 18, 19, 20, 21) a by-pass route forming a part of the by-pass path. It refers also to a cell (3) for realizing the cellular field (1) of the circuit arrangement (100), the cell (3) including an internal state storage, a multiplexer, a maskable equality comparator, having a masking input and a first comparison input, an activating storage, a J-K logic having a J-input and a K-input, a next state storage, and an active layer storage for storing present state connected by the respective inputs to the control bus (24).

Description

CIRCUIT ARRANGEMENT OF A CELLULAR PROCESSOR

FIELD OF INVENTION

The invention refers from one side to a circuit ar¬ rangement of a cellular processor of homogeneous structure and inhomogeneous operation comprising a cellular field created by regular interconnection of cells and a switching network connected to the edges of the cellular field and to a system bus, and from the other side to a cell as a basic building element for realizing the circuit arrangement, comprising control inputs coupled with a control bus, inputs and outputs connectable with adjacent cells wherein in the cell an internal state storage, a multiplexer, a maskable equality comparator, a next state storage, an activating storage, a J-K logic and an active layer storage as a pres¬ ent state storage are connected to the control bus, further the output of the maskable equality comparator is connected to an enable and preferably a passive layer storage input of the next state storage, the output of the J-K logic is con¬ nected to the data input of the next state storage, the out¬ put of the next state storage is connected with the input of the internal state storage, further the outputs of the pres¬ ent state storage constitute the outputs of the cell.

The circuit arrangement of the invention can con¬ stitute the basis of realizing a new kind of the processor systems on a chip and by the application thereof cellular fields of processors for parallel computers of MIMD (multiple instruction multiple data) system can be created.

BACKGROUND OF THE INVENTION

From the literature of the art many kinds of pro¬ cessor systems have become known comprising a large number of uniform and uniformly connected processors and/or cells. These systems are capable of high performance solving tasks characterized by inherent parallelity.

The known systems can be basically divided into two groups according to their principle of operation. The first group contains the systems wherein the principle of the operation and thereby the structure is determined by the task (class of tasks) to be solved or an algorithm (class of algorithms) . The computers of such kind are called "algo¬ rithm structured computers". The state of the art of the present invention is determined by such systems comprising typically cells operating on 1 to 16 bits wherein the cells are arranged in a square grid or eventually in a hexagonal system. A computer of this structure has become known e.g. from D. Parkinson: "The ICL Distributed Array Processor" (ϊnfotech Future Systems, Vol. 2, pp. 389 - 402, INFOTECH International, Maidenhead, Berkshire, 1977) , re K. E. Batcher: "MPP - A Massively Parallel Processor" (Proceedings of the International Conference on Parallel Processing, August 1979, IEEE Catalog No 79CH1433-2C) or T. J. Fountain: The Development of the CLIP-7 Image Processing System (Pat- tern Recognition Letters, 1 /1983/, pp. 331 — 339, North Holland) . One of the common important features of the sol¬ utions depicted in the literature cited above is that the construction of the cells applied therein corresponds to and reflects the class of the special tasks to be solved (for example image processing), further the control, organization and function of the cells are partly determined by the data structure of the tasks.

The second group contains the systems the operation of which is based on the theory of the self reproducing (cellular) automata introduced by Janos Neumann and can be considered as the model of the parallel computers (John von Neumann: The Theory of Self Reproducing Automata, ed. by A. W. Burks, University of Illinois Press, Illinois, Urbana, 1966) . The literature of the art applies the expression "cellular computers" to this kind of arrangements.

The mentioned two groups are not characterized by features sharply differing one from another, neither the terminology is uniform and overlapping, there are systems which may be listed up in both groups. A solution belonging to the second group analyzed above and equipped with a control bus is disclosed by T. Kondo et al in the publication: An LSI Adaptive Array Pro¬ cessor (IEEE Journal of Solid-State Circuits, Vol. 18., No 2.. pp. 147 - 156, 1983). The solution shown in this article includes an 8 * 8 array of cells of Conway-neighbourhood and respective switching networks. Each cell comprises two reg¬ isters, one arithmetic—logic unit equipped with a carry bit and two data forwarding units. The operation to be executed by the cell is basically determined by a command (broadcast by a control bus) . On the basis of the contents of one of the registers applied in the cell, further with regard to the "programmability" of the data forwarding units it is possible to construct groups consisting of a higher number of the cells and executing complex functions. The circuit is of single instruction multiple data (SIMD) system and not of the previously mentioned MIMD system. The SIMD system is very effective when it is necessary to carry out "homogene¬ ous" vector and matrix operations.

The common disadvantage of the solutions constituting the art and depicted above lies in that they are capable only of homogeneous operating and thereby of implementing a limited number of the transition functions, namely, exclus¬ ively the transition functions to which the corresponding combination logic is included therein.

SUMMARY OF THE INVENTION

The object of the present invention is to provide a circuit arrangement free of the disadvantage mentioned above, wherein by connecting the elementary cells a cellular field of homogeneous structure of any dimensions but of tem¬ poral and spatial inhomogeneity in the operation can be realized, which is capable of implementing any transition function and wherein it is possible to quickly broadcast the data to a limited distance.

The invention is based on the recognition that ele¬ mentary cells comprising maskable equality comparators for evaluating the transition function should be applied which are capable of associative addressing of the cells, i.e. wherein exclusively those cells can be activated which have the identical predetermined internal state and all other cells stay unactivated (passive) . A further recognition is that the elementary processor built up from the cells and thereby the complex system offers increased performance if the capacity of storing the present state data of the cells of the elementary processor is increased. It is also a very important recognition that by sequential forwarding the data the performance will not remarkably decrease and a re¬ markable structural simplification can be gained, further it is possible to implement a programmable neighbourhood for the cells of the cellular field.

Hence, the present invention is a circuit arrangement of a cellular processor of homogeneous structure and in- homogeneous operation, comprising a cellular field consist- ing of a regular arrangement of cells interconnected by local connections and a control bus and a switching network connected to the cells at the edges of the cellular field and to a system bus, wherein each cell comprises a maskable equality comparator for associative addressing of the cells, the switching network includes inputs and outputs con- nectable to respective switching networks of adjacent cellu¬ lar fields, means for receiving and processing microcommands and a by-pass circuit for determining and storing a by-pass path between the cells, the by-pass circuit consisting of at least four by-pass circuit modules assigned to the edges, each by—pass circuit module comprising means for storing and implementing a by-pass route forming a part of the by-pass paths.

The invention concerns further a circuit arrangement, comprising a cellular field consisting a regular arrangement of cells, each cell being connected to adjacent cells and a control bus, further comprising a switching network con¬ nected to the edges of the cellular field and to a system bus, the essence of which lies in that each cell of the cel- lular field includes a multiplexer and a next state storage storing an accumulator bit, the switching network comprises a microcommand register coupled with the system bus, a microcommand decoder, an internal system bus joining the microcommand register with the microcommand decoder and a by—pass circuit consisting of at least one module at each edge of the cellular field and having local data inputs and outputs, each by—pass circuit module including a by—pass route memory, an outer edge register, an inner edge regis¬ ter, an input multiplexer and an output multiplexer, wherein the data inputs of the by—pass route memory are connected to the outputs of the outer edge register, the data outputs thereof are tied to the selecting inputs of the input multi¬ plexer and to those of the output multiplexer, further the parallel data inputs of the outer edge register are con- nected to the respective local outputs of the cells arranged on the same edge of the cellular field, its sequential data input is linked with an output of the input multiplexer, its parallel data outputs are connected to the inputs of the inner edge register, its sequential data output is linked with the input multiplexers and the output multiplexers, further the output of the inner edge register is connected to the respective local data inputs of the cells lying at the same edge of the cellular field, the data inputs of the input multiplexers are connected to the local data inputs of the by—pass circuit and to the sequential data outputs of the outer edge registers, the local data inputs and the sequential data output of the outer edge register are linked with the data inputs of the output multiplexer determining the local data outputs of the by—pass circuit. Preferably, the cellular field consists of sixty-four cells in an eight by eight array because this is advantageous with regard to programming the cells.

The time equilibrum of the operations executed in different layers can ensured in a simple way if the by-pass route memory of the proposed circuit arrangement comprises four locations of sequential access.

When the circuit arrangement according to the inven¬ tion forms the basis of complex system, the propagation time of the signals can be the source of side effects and this disadvantageous feature can be restricted in an especially preferred embodiment of the invention, wherein the circuit is realized in the form of a synchronous sequential network operated by a non-overlapping two phase clock signal, and the circuit arrangement includes master—slave type storage elements except the cell, the outer microcommand register and the inner microcommand register.

The inhomogeneity of the operation in a complex system realized by the circuit arrangements according to the invention can be improved, if the microcommand register in the circuit arrangement includes an outer and inner micro- command register equipped with respective loading inputs for receiving clock signals of first and second phase from the system bus, a phase multiplexer having a selecting input, a phase storage and a phase circuit, wherein in the micro- command register the system bus is connected to a group of the data inputs of the phase multiplexer, the outputs of the outer microcommand register are connected to another group of the data inputs of the phase multiplexer, the outputs of the phase multiplexer are connected to the input of the inner microcommand register, the selecting input of the phase multiplexer is coupled through the phase circuit with outputs of the phase storage, further the phase storage includes four locations of sequential access each based on two bits, and the phase circuit is implemented by a two-bit circular shift register to be loaded in a parallel way. The output of the next state storage is preferably coupled with the outer edge register because this is advantageous with regard to the neighbourhood to be realized from more adjacent circuit arrangements. The circuit arrangement of the invention can be built up from different kind of cells. However, it is very advan¬ tageous when a cell is. applied which comprises a control bus, inputs and outputs connected to adjacent cells, and ac¬ cording to the invention it includes an internal state stor- age, a multiplexer, a maskable equality comparator, having a masking input and a first and a second comparison inputs, an activating storage, a J-K logic having an input, a J-input, a K-input and an output, a next state storage, and an active layer storage for storing present state connected by the respective inputs to the control bus, further the output of the maskable equality comparator is connected to an enable input of the next state storage, the output of the J-K logic is connected to the data input of the next state storage, the output of the next state storage is coupled with a data input of the internal state storage, further the outputs of the active layer storage constitute the outputs of the cell, wherein the output of the internal state storage is con¬ nected through the multiplexer to the second comparison in¬ put of the maskable equality comparator, the inputs are con- nected to the inputs of the multiplexer, the next state storage is equipped with a another enable input connected to enable inputs of the internal state storage, the maskable equality comparator is coupled by its output to the activat¬ ing storage connected by its control input to the control bus, wherein the output of the activating storage is con¬ nected to the common enable inputs of the next state storage and the internal state storage and the output of the next state storage is connected over the active layer storage forming a present state storage to the input of the J-K logic.

In a preferred embodiment of the cell according to the invention a passive layer storage forming a buffer stor¬ age means is inserted between the next state storage and the active layer storage, and further advantageously the output of the next state storage is connectable with the outer edge registers.

The circuit arrangement of the invention offers the possibility of realizing a processor and a cell constituting a^' basic building element of this processor which are capable of solving the task of the present invention, are char¬ acterized by homogeneous structure, further by temporal and spatial inhomogenity of operation, by the capability of im¬ plementing any transition function. The proposed circuit ar¬ rangement can be manufactured by existing microelectronics technologies and the structure fits well to the requirements of the manufacturing process.

The circuit arrangement of the invention gives the unexpected advantage of rendering an interfunctional optimi¬ zation possible, thereby it is capable of implementing dual commands and this results in an increase of the speed of the transition steps. From the structure of the cell further advantages follow, namely, it is possible to broadcast J-K commands and activating commands on the same control bus and in consequence to reduce the number of the wires. This is especially advantageous with regard to the manufacture of the chips. It is also unexpected that the increase of the performance is very high without remarkable increase of the number of the devices, only by applying a passive layer storage which results in a great decrease of the operating time when executing similar tasks.

BRIEF DESCRIPTION OF THE DRAWINGS

The circuit arrangement of the invention will be shown further in more detail on the basis of drawings illustrating respective preferred embodiments of the circuit arrangement and the cell of the invention by the way of an example only. In the drawings Figure 1 is the block diagram of the circuit arrangement of the invention as implemented with a cellular field constructed from cells, Figure 2 shows the block diagram of a cell proposed by the invention which is applicable in the novel circuit arrangement realized according to Fig. 1, Figure 3 illustrates the block diagram of a module of a by- —pass circuit of the proposed circuit arrangement connected to one edge of the cellular field, Figure 4 shows the block diagram of a microcommand register of the proposed circuit arrangement, and Figure 5 illustrates a possibility of constructing a com¬ plex computing field from the circuit arrangements shown in Fig. 1. DETAILED DESCRIPTION OF THE INVENTION AND THE PREFERRED EMBODIMENTS

As it is illustrated in Fig. 1, the invention is realized in the form of a circuit arrangement 100 comprising a regularly structured system of interconnected cells 3 and a switching network 2. The cells 3 determine a cellular field 1 having edges N, E, S and W determined from each side by cells 3 of the cellular field 1 (not marked specially) . The cellular field 1 is coupled with the switching network 2 which comprises a by-pass circuit 16 surrounding the edges N, E, S and W of the cellular field 1 and means for receiv¬ ing and decoding microcommands. If more cellular fields 1 are interconnected, a complex system of processors can be realized as the basis of a computer of MIMD system.

The switching network 2 is inserted between a system bus 23 and the cellular field 1 and includes, over the by- —pass circuit 16, a microcommand register 56 as an input unit and a microcommand decoder 4. The microcommand register 56 is connected by an internal system bus 26 to an input of the microcommand decoder 4 having first and second output groups 01 and 02. The internal system bus 26 is divided into two parts, first of them coupled with the input of the microcommand decoder 4 and the second to a control bus 24 of the cellular field 1 having connections to each cell 3. The first output group 01 forwards signals to internal control points of the circuit arrangement 100 of a complex system, the second output group 02 drives a bus joined with the second part of the internal system bus 26 and thereby with the control bus 24. In the cellular field 1 the interconnec¬ tion of the cells 3 is realized by outputs and inputs CNI, CNO, CEI, CEO, CSI, CSO, CWI and CWO in the direction of the edges N, E, S and W, respectively. The by—pass circuit shown partly in more detail in Fig. 3 consists of by-pass circuit modules 161, 162, 163 and 164 of similar construction as- signed to the edges E, N, W and S of the cellular field 1. At each edge of the cellular field 1 one or more by-pass circuit modules are applied. The microcommand register 56 can be implemented e.g. in the form of a latch register. The cell 3 which constitutes the basis of the cel¬ lular field 1 of Fig. 1 can be constructed e.g. according to Fig. 2. In this cell 3 the control bus 24 is connected by respective outputs to an enable input EN of an internal state storage 12, a select input S of a multiplexer 13, a masking input M and a first comparison input Cl of a mask¬ able equality comparator 10, and by a gating input G to an activating storage 14, by a J-input and a K-input to a J-K logic 11, further by respective gating inputs G to a next state storage 9, a preferably applied passive layer storage 15 and an active layer storage 8, the latter two constitut¬ ing if necessary, means for storing data referring to the present state of the cell 3. The activating storage 14, the J-K logic 11, the next state storage 9, the passive layer storage 15 and the active layer storage 8 have respective data inputs D and outputs Q, they, except the activating storage 14 are arranged one after another. The active layer storage 8 is connected to outputs 81 applicable as the out¬ puts CNO, CEO, CSO and CWO shown in Fig. 1. A further enabl¬ ing input EN of the internal state storage 12 (this enabling ionput EN is common for all the bits of the internal state storage 12) is connected to the output Q of the activating storage 14 and all its data inputs D are tied to the output Q of the next state storage 9. The output of the internal state storage 12 is linked with an input of the multiplexer 13 having an input 131 (i.e. inputs CNI, CEI, CSI, CWI) for receiving signals from the by—pass circuit 16. The output of the multiplexer 13 is linked with a second comparison input C2 of the maskable equality comparator 10 forwarding res¬ pective signals by output O to the data input D of the acti- vating storage 14 and a first enable input EN2 of the next state storage 9. The output Q of the activating storage 14 is connected to a second enable input ENl of the next state storage 9. The output Q of the active layer storage 8 is fed-back to the input D of the J-K logic 11. As mentioned, the J-K logic 11, the next state storage 9, the passive layer storage 15 and the active layer storage 8 are arranged one after another, the respective data inputs D and outputs Q are connected to one another. The next state storage 9, the active and the passive layer storages 8, 15 can be im- plemented as gated transparent latch storages and the inter¬ nal state storage 12 a two— to ten—bit register forming also a gated transparent latch. The first and second enable in¬ puts EN2 and ENl should rather be characterized by an AND operation. The J-K logic 11 is a combination network having one date input, two control inputs and an output. It is charac¬ terized by a Boolean function of three variables, especially by the function Q = J*D + K*D (here D is the signal of the data input, J and K means the signals of the control J- and K-inputs and the output is Q) . The J-K logic 11 can be iden¬ tified also as a part of the known J-K flip-flops.

The particulars of the by—pass circuit 16 of the proposed circuit arrangement 100 can be seen in Fig. 3 wherein for the purposes of better understanding the module 161 of this circuit is illustrated only. The by—pass circuit 16 is built up from at least four similar modules. The module 161 belongs to the edge E of the cellular field 1 and it is built up of a by—pass route memory 17, an outer edge register 18 (implemented as a parallel loadable shift regis- ter), an inner edge register 19, an input multiplexer 20 and an output multiplexer 21. The by—pass route memory 17 is coupled by its data inputs DI with an output Q₇_₀ of the outer edge register 18 receiving at its input DI₇_₀ the out¬ puts 81 belonging to the cell 3 and its output O with selecting inputs SO, SI and S2 of the input multiplexer 20 receiving at data inputs D₀, Ω D₂, D₃, D₄, D₅, D₆, D₇ signals of the inputs El, SI, WI, NI, EDF and logic signals "1", "0", respectively further with selecting inputs SO, SI and S2 of the output multiplexer 21 receiving at data inputs D₀, D*,, D₂, D₃, D₄, D₅, D₆, D₇ the inputs WI and NI, logic signal "0" the inputs SI and data signals DOE, DOS, DOW, DON (EDF, SDF, WDF, NDF) , respectively produced by outputs SO of the outer edge registers 18 of the by-pass circuit modules belonging to the edges E, S, W, N of the circuit arrangement 100. The output DO of the input multiplexer 20 is connected to an input SI of the outer edge register 18 forwarding the data signal EDF, and the output DO of the output multiplexer 21 forwards the output signal EO of the edge E.

The input DI₇_₀ of the inner edge register 19 is con- nected to the output Q₇_₀ of the outer edge register 18 and its output Q₇_₀ is connected to the inputs 131 of the res¬ pective multiplexer 13 of the cells 3. In the module 161 function control signals and control input signals are applied, the function control signals being the shift, load and hold signals for the outer edge register 18 and load and hold signals for the inner edge register 19.

Preferably the by-pass route memory 17 is implemented rather by a sequential accessible memory than by a random access memory (RAM) . The connections of the inputs and outputs of the in¬ put and output multiplexers 20 and 21 of the different by- —pass circuit modules and that shown in Figure 3 are prefer¬ ably realized according to Table I. (see next page) .

The block diagram of Fig. 4 shows an advantageous im- plementation of the microcommand register 56. Between the system bus 23 and the internal system bus 26 an outer micro¬ command register 5 having a loading input CP, an input I and an output O, a phase multiplexer 22 having inputs II and 12, a select input S and an output 0, further an inner micro- command register 6 having an input I, a loading input CP and Table I .

Connections of the inner and outer multiplexers

an output 0 are inserted. The microcommand register 56 includes further a phase storage 7 - preferably a sequantial accesible memory rather than a RAM - having an input CI for receiving control input -signal, data inputs DI1 and DI2 and data outputs DOl and D02, the latter connected through a phase circuit 25 to the select input S of the phase multiplexer 22. The system bus 23 is connected by wires forwarding clock signals of first phase FI1 and clock signals of second phase FI2, respectively, to the loading inputs CP of the outer and inner microcommand registers 5 and 6, further it is connected to the input 12 of the phase multiplexer 22. The output O of the outer microcommand reg¬ ister 5 is coupled with the input II of the phase multi¬ plexer and the output 0 of the latter with the input I of the inner microcommand register 6 having the output O con¬ nected to the internal system bus 26. In this unit the phase storage 7 is a two—bit wide memory which consists of four sequentially accessible locations. The phase circuit 25 is realized preferably by a circular shift register which is loaded in parallel and is in feed-back connection with itself, the number of bits of the register corresponds to the number of the phases applied, i.e. in this embodiment it is a two-bit register. The clock signals of first and second phases FI1 and FI2 are the clock signals forwarded by the system bus 23.

As it can be seen in Fig. 5, as many pieces of the circuit arrangements 100 as required can be connected in a homogeneous way, wherein the circuit arrangements 100 are equipped with the inputs and outputs NI, NO (north) , SI, SO (south), El, EO (east) and WI, WO (west). The way of the interconnection of the adjacent circuit arrangements 100 is clearly shown in this Figure and it requires no specific comments. Each circuit arrangement 100 is in parallel con¬ nection with the system bus 23.

When analyzing the way of operation of the circuit arrangement of the invention, the novel features are the following, when the particulars commonly applied in this field of industry and obvious for the skilled artisan are not presented in detail:

When evaluating a transition function the neighbours of the cell 3 should all time sense the present state of the cell 3, independently on the fact whether during this evaluating process the next state of the cell 3 has been written to the next state storage 9 or not. This is ensured in cell 3 by the active layer storage 8 and the next state storage 9. The contents of the next state storage 9 constitute the accumulator bit. The active layer storage 8 stores the present (actual) state of the cell 3 and the ad¬ jacent cells 3 sens the contents of this storage, i.e. this storage is connected to the respective local data inputs CNI, CWI, CEI, CSI of the adjacent cell(s) 3. The contents of these active layer storages 8 remain unchanged during evaluating the transition function. The next state of the cell 3 is computed in the accumulator bit. After the tran¬ sition step a closing step is executed when all the cells 3 forming the cellular field 1 take up in the same moment the next state being sensed by the adjacent cells 3, i.e. the value of the accumulator bit is written into the active layer storage 8. The closing step executed in the cell(s) 3 is assigned thereby to the operation of the layer swap. A special advantage of this circuit arrangement 100 is that in spite of serial evaluation of the transition function the operation of the cellular field 1 remains basically paral¬ lel, because in the same transition step all the cells 3 can operate which have the same neighbourhood combination.

The determination of the next state of the cell 3 is ensured by executing the J-K microcommands. The J-K micro¬ command comprises a J-K statement, a four-bit mask and a four—bit comparison value. The mask and comparison value together constitute a masked pattern. The mask assigns some neighbours of the cell 3. If the state of the assigned ad- jacent cells 3 is identical with the comparison value, i.e. the output of the maskable equality comparator 10 is logic "1", and the cell 3 is activated, i.e. the activating stor¬ age 14 has the contents of logic "1", then the next state storage 9 (accumulator bit) of the cell 3 is written over with a value determined by the J-K statement and the present (actual) state of the cell 3, i.e. by the contents of the active layer storage 8.

The temporal inho ogeneity of the cellular field 1 in the circuit arrangement 100 is ensured by broadcasting the transition functions by a central unit over the system bus 23 and thereby in different transition steps of the cellular field 1 the of different transition functions can be prescribed for cells 3. The spatial inhomogeneity is imple¬ mented by the internal state storage 12 of the cell 3 because the transition function broadcast by the central unit is executed exclusively by the cells 3 which have a predetermined internal state.

Both the associative addressing of the cells and the evaluation of the transition function are implemented by the maskable equality comparator 10. From among the state of the adjacent cells 3 and bits of the internal state storage 12 the selection is made by the multiplexer 13. The activating process of the cell 3 is based on storing the result of the comparison of the broadcast pattern with the internal state bits in the activating storage 14. If the contents of the activating storage 14 is logic "1" the cell 3 is activated. The contents of the activating storage 14 serves as an enable signal when executing the J-K microcommand(s) and the microcommand of writing internal state to be presneted later in more detail. The activation is realized by executing the activating microcommand(s) . The activating microcommand is constructed from a mask and a comparison value. The mask assigns those of the bits of the internal state storage 12 which should be compared with the respective bits of the comparison value. If the value of the assigned bits of the internal state storage 12 is equal to the value broadcast, the activating storage 14 will be set to logic "1", else its contents will be set to logic "0".

An important recognition of the present invention is that in a cell 3 built up according to the invention the activating process can be generalized without extra hard¬ ware. The activation is possible on the basis of the state of the adjacent cells 3, as well as on the basis of the internal state of the cell 3. In the former case the mask in the activating microcommands assigns adjacent cells 3 and the comparison value is compared with the state of the neighbours assigned. On the basis of the internal state of the cell 3 the J-K microcommand can be executed too, if the J-K microcommand includes a mask assigning internal state bits and the comparison value is compared with the pre- determined internal state bits. In this way a complete dual microcommand set can be created for computing transition functions and this set renders possible to implement inter- functional optimization. The bits of the cells 3 of the circuit arrangements 100 of the invention can be organized in layers. The passive layer constitutes a data structure consisting of the contents of the passive layer storages 15, similarly, the active layer is a data structure of the contents of the active layer storages 8 and the by-pass layer is created by the contents of the identical locations of the by-pass route memories 17. Each layer is formed by the same bits of the different cells 3.

Overlapping of the computation of the next state of the cells 3 and the by—passing process is implemented by alteration of operating the two layers of the cellular field 1 on the transition step level. In one of the layers of the cellular field 1 forming the active layer the cells 3 are computing their next state and in the same time in the second layer constituting the passive layer the process of by—passing takes place. After taking up the next state by the cells 3 of the active layer and completing the part of by— ass in the passive layer related to the transition step the two layers of the cellular field swap their layer func- tion.

The neighbourhood of the cellular fields 1 applied in every circuit arrangement 100 is realized by the by—pass circuits 16 in a desired order. In this way it can be en¬ sured that the cells 3 arranged at the edge N, E, S, W of a cellular field 1 in a circuit arrangement 100 - the cells 3 at the edge are called further border cells - have neigh¬ bours not only among the border cells of the neighbouring (e.g. adjacent according to Fig. 5) circuit arrangements directly connected to the arrangement concerned, but also among the border cells of the circuit arrangements 100 detached with a greater distance. This is ensured thereby that by the means of the by-pass network the signal propagated to the local data input WI, NI, El, SI of circuit arrangement 100, which is an elementary processor, can jump over the cellular field 1, i.e. this signal can be present without any change at one or more local data output WO, NO, EO, SO of the circuit arrangement 100.

At the overlapping of the by—passing process and thereby at overlapping of the computation of the next state of the cells 3 on this basis the output situation is that the by-pass route memory 17 is loaded with the corresponding by—pass network routes and in the active layer storage 8 of the cells 3 the present state of the active layer is stored, further the inner edge registers 19 contain the state of the border cells of the circuit arrangement 100 and the states of the adjacent cells 3 in the active layer being eventually on longer distance in the space, the passive layer storage 15 stores the present state of the passive layer in the cells 3, and the outer edge registers 18 contain the value of the passive layer storage 15 of the border cells 3 con¬ nected therewith. In this situation the next state of the cells 3 in the active layer is computed, because the local data input CNI, CEI, CSI, CWI of all of the cells 3 is con¬ nected to the value of the neighbour. By the computation of the next state of the cells 3 in the accumulator bit of the cells 3 the next state of the cells in the active layer is created. Simultaneously the process of by—pass is started. During this by addressing the by—pass route memory 17 the by—pass network routes in the by—pass layer concerned is created and this network begins to propagate the value of the serial output of the outer edge register 18 arranged at the beginning (root point) of the by-pass path concerned. (In the terms of the theory of graphs the by—pass path can be considered as a tree on the level of the system. This tree consists of the by-pass routes defined in the circuit arrangements 100.) After elapsing a predetermined time this value is rippled through the by—pass path and is stabilized at the serial input(s) of the outer edge register(s) 18 arranged at the end(s) of the by-pass path. Thereafter by executing a microcommand ensuring shifting step of the outer edge registers 18 the propagation of the state of the cell in the passive layer, and more exactly for as many cells in the passive layer as many by—pass paths are present in the layer, is finished. By repeating the operation as described the present state of the cells in the passive layer concerned is forwarded to the respective outer edge regis¬ ters 18. Thereafter the address of the by—pass route memory 17 is incremented and this results in creating the network of by—pass paths for the next by—pass layer. In the latter the state of the cells in the passive layer can be trans¬ ferred according to the above process. This process is carried out for all by—pass layers which are necessary and this results in containing the present state of the cells of the neighbour in the passive layer by the border cells 3 of the circuit arrangement 100, wherein the neighbours can be adjacent and remote cells 3.

After computing both the next state of the cells in the active layer and the part of the by—passing process of the actual transition step the operation of closing and swapping layer follows. During this operation in each cell 3 the contents of the passive layer storage 15 are loaded into the active layer storage 8, the inner edge register 19 of each circuit arrangement 100 forming an elementary processor circuit receives the contents of all corresponding outer edge registers 19, thereafter the passive layer storage 15 in each cell 3 and the outer edge register 18 of each cir¬ cuit arrangement 100 is loaded with the accumulator bit, i.e. with the contents of the connected next state storage 9. It can be seen that this closing microcommand resulting in layer swap controls both the cell(s) 3 and the switching network 2. During the closing and swapping step the two layers of the cellular fields 1 changes function and because in this way the conditions prescribed for the start of the process depicted above are ensured, the further steps are the same as previously described.

In order to increase the spatial inhomogeneity the internal state of each circuit arrangement 100 can be intro¬ duced in a similar manner. During this operation the circuit arrangement 100 executes the microcommand present in the in- ner microcommand register 6 and in the same time one or more microcommands are forwarded over the system bus 23. The microcommand to be executed by the circuit arrangement is selected on the basis of the contents of the phase storage 7. The selected microcommand is loaded into the outer micro- command register 5. After executing the microcommand the contents of the outer microcommand register 5 are loaded into the inner microcommand register 6. Because in different circuit arrangements 100 connected to the common system bus 23 the phase storages 7 may have different contents, the circuit arrangements can execute different microcommands, i.e. the inhomogeneity on circuit arrangement level is given. It is an important feature of the phase storage 7 that it contains several locations. The selection of the respective locations of the phase storage 7, their read and write operations are implemented by microcommands. The phase storage 7 has several locations because in this way the in¬ homogeneity on circuit arrangement level (its spatial inho¬ mogeneity) may be higher than the value derived from the ratio of the speed of microcommand execution and the speed of the system bus 23, because the contents of the locations of the phase storage 7 can be different and the selection among the locations is possible during the operation of the circuit arrangement 100, the computation of the next state of the cell. During microcommand execution in the arrange- ment of Fig. 4 the system bus transfers two microcommands, because of the clock skew it is advantageous to apply a first clock signal of first phase FI1 and a second clock signal of second phase FI2, wherein the two microcommands arriving in the same clock signal cycle are advantageously forwarded synchronized with the phases of the two clock sig¬ nals. The process of loading the outer microcommand register 5 is synchronized by the second clock signal FI2. The micro¬ command received in phase with the first clock signal FI1 is loaded into the outer microcommand register 5. Depending on the control of the phase multiplexer 22 in the phase of the second clock signal FI2 either the microcommand broadcast in the system bus 23 in this phase or the microcommand stored in the outer microcommand register 5, i.e. the microcommand broadcast in the first phase is loaded into the inner micro- command register 6. The circuit arrangement 100 executes the microcommand stored in the inner microcommand register 6. The phase multiplexer 22 can be serially controlled and the locations of the phase storage 7 comprising the two bit lo¬ cations are accesible in a serial manner. Each location of the phase storage 7 includes the two phase bits for the two layers of the cellular field. When executing the operation of layer swap the two phase bits are also swapped. This is implemented by the phase circuit 25 which is a circular shift register loadable in parallel. This operation ensures the spatial inhomogeneity of the two layers of the phase circuit 25, which differs from the spatial inhomogeneity of the cell 3. The phase storage 7 can be loaded from an outer edge register similarly to the by—pass route memory.

Claims

WHAT WE CLAIM IS

1. A circuit arrangement of a cellular processor of homogeneous structure and inhomogeneous operation comprising a cellular field (1) consisting a regular arrangement of cells (3) , each cell (3) being connected to adjacent cells (3) and a control bus (24) , further comprising a switching network (2) connected to the edges (N, E, S, W) of the cellular field (1) and to a system bus (23) , characterized in that each cell (3) of the cellular field (1) includes a multiplexer (13) and a next state storage (9) storing an accumulator bit, the switching network (2) comprises a microcommand register (56) coupled with the system bus (23), a microcommand decoder (4) , an internal system bus (26) joining the microcommand register (56) with the microcommand decoder and a by—pass circuit (16) consisting of at least one module (161, 162, 163, 164) at each edge (N, E, S, W) of the cellular field (1) and having local data inputs and out- puts (NI, NO, El, EO, SI, SO, WI, WO), each by—pass circuit module (161, 162, 163, 164) including a by—pass route memory (17), an outer and an inner edge registers (18, 19), an in¬ put multiplexer (20) and an output multiplexer (21) , wherein the data inputs (DI) of the by-pass route memory (17) are connected to the outputs (Q₇.₀) of the outer edge register (18) , the data outputs (0) thereof are coupled with the se¬ lecting inputs (SO, SI, S2) of the input multiplexer (20) and with those of the output multiplexer (21) , further the parallel data inputs (DI₇.₀) of the outer edge register (18) are connected to the next state storage (9) of the cells (3) arranged on the same edge (N, E, S, W) of the cellular field (1) , its serial data input is linked with an output (DO) of the input multiplexer (20) , its parallel data outputs (Q₇.₀) are connected to the inputs (DI₇.₀) of the inner edge regis- ter (19) , its serial data output (EDF) is tied to the input multiplexers (20) and the output multiplexers (21) , further the output (Q₇-₀) of the inner edge register (19) is con¬ nected to the input (131) of multiplexers (13) arranged in the cells (3) lying at the same edge (N, E, S, W) of the cellular field (1) , the data inputs of the input multi¬ plexers (20) are tied to the local data inputs (WI, NI, El, SI) of the by-pass circuit (16) and to the serial data out¬ puts of the outer edge registers (18) , the local data inputs (WI, NI, El, SI) and the serial data output (EDF) of the outer edge register (18) are linked with the data inputs (D₀, D-*, D₂, D₃, D₄, D₅, D₆, D₇) of the output multiplexer (21) determining the local data outputs (NO, EO, SO, WO) of the by—pass circuit (16) .

2. The circuit arrangement according to claim 1, characterized in that the cellular field (1) consists of sixty-four cells (3) in an eight by eight arrangement.

3. The circuit arrangement according to claim 1 or 2, characterized in that the by-pass route memory (17) fco - prises four sequentially accessible locations.

4. The circuit arrangement according to any of claims 1 to 3, characterized in that the circuit (100) is imple¬ mented in the form of a synchronous sequential network oper¬ ated by a non—overlapping two phase clock signal (FI1, FI2) , and it includes master—slave type storage elements except the cell (3) , the outer microcommand register (5) and the inner microcommand register (6) .

5. The circuit arrangement according to any of claims 1 to 4, characterized in that the microcommand register (56) includes an outer and an inner microcommand registers (6, 5) having respective loading inputs (CP) for receiving clock signals of first and second phase (FI1, FI2) from the system bus (23), a phase multiplexer (22) having a selecting input (S) , a phase storage (7) and a phase circuit (25) , wherein in the microcommand register (56) the system bus (23) is tied to a group of the data inputs (12) of the phase multi- plexer (22) , the outputs (O) of the outer microcommand reg¬ ister (5) are connected to another group of the data inputs (II) of the phase multiplexer, the outputs (O) of the phase multiplexer (22) to the input (I) of the inner microcommand register (6) , the selecting input (S) of the phase multi¬ plexer (22) is coupled through the phase circuit (25) with outputs (DOl, D02) of the phase storage (7) , further the phase storage (7) includes four sequentially accessible locations each based on two bits, and the phase circuit (25) is constituted by a two-bit circular shift register to be loaded in a parallel way.

6. A cell for realizing the circuit arrangement ac¬ cording to any of claims 1 to 5, comprising a control bus (24) , inputs (131) and outputs (81) connected to adjacent cells (3) , characterized in including a multiplexer (13) , an internal state storage (12) , a maskable equality comparator (10) , having a masking input (M) , a first and a second com¬ parison inputs (Cl, C2) , an activating storage (14) , a J-K logic (11) having an input (D) , a J-input (J) , a K-input (K) and an output (Q) , a next state storage (9) , and an active layer storage (8) for storing present state connected by the respective lines of the control bus (24) , further the output (O) of the maskable equality comparator (10) is connected to an enable input (EN2) of the next state storage (9) , the output (Q) of the J-K logic (11) is connected to the data input (D) of the next state storage (9) , the output of the next state storage (9) is coupled with a data input (D) of the internal state storage (12) , further the output of the active layer storage (8) forms the outputs (81) , wherein the output (Q) of the internal state storage (12) is connected over the multiplexer (13) to the second comparison input (C2) of the maskable equality comparator (10) , the inputs (131) are tied to the inputs of the multiplexer (13) , the next state storage (9) is equipped with a another enable in- put (ENl) connected to enable inputs (EN) of the internal state storage (12), the maskable equality comparator (10) is coupled by its output (0) to the activating storage (14) connected by its control input to the control bus (24) , fur¬ ther the output (Q) of the activating storage (14) is con- nected to the common enable inputs (ENl, EN) of the next state storage (9) and the internal state storage (12) and the output of the next state storage (9) over the active layer storage (8) forming a present state storage to the in¬ put (D) of the J-K logic (11) .

7. The cell according to claim 6, characterized in comprising a passive layer storage (15) forming a buffer storage means inserted between the next state storage (9) and the active layer storage (8) .

8. The cell according to claim 6 or 7, characterized in that the output of the next state storage (9) is con¬ nectable to the outer edge registers (18) .

9. A circuit arrangement of a cellular processor of homogeneous structure and inhomogeneous operation, compris¬ ing a cellular field (l) consisting of a regular arrangement of cells (3) interconnected by local connections and a con¬ trol bus (24) and a switching network (2) connected to the cells (3) at the edges.(N, E, S, W) of the cellular field (1) and to a system bus (23) , wherein each cell (3) com¬ prises a maskable equality comparator (10) for associative addressing of the cells (3) , the switching network (2) in¬ cludes inputs and outputs (NI, NO, El, EO, SI, SO, WI, WO) connectable to respective switching networks (2) of adjacent circuit arrangements (100) , means for receiving and process¬ ing microcommands (4, 56) and a by-pass circuit (16) for de- termining and storing a by-pass path between the cells (3) , the by-pass circuit (16) consisting of at least four by-pass circuit modules (161, 162, 163, 164) being assigned to the edges (N, E, S, W) and comprising each means for storing and implementing (17, 18, 19, 20, 21) a by-pass route forming a part of the by-pass paths.