SU1287172A1 - Device for generating message route in uniform computer system - Google Patents

Abstract

The invention relates to computing and can be used in the construction of high-performance systolic, pipeline and other processors, in which during the solution of the problem there is a movement of data on the computational medium. The purpose of the invention is to increase

Description

1 :: m.28.1

(f С

YA25.2

tc

(X

n

device speed. The device contains a group of blocks 1.1, ..., 1.8 of the buffer memory, three registers 2,3,4, trigger 5, counter 6, comparison block 7, direction selection block 8 clock pulses 9, key group 10.1, .., 10.8, multiplexer 11, decoder 12, two elements And 13, 14, a group of elements And 15.1, ..., 15.8, three elements OR 16, 17, 18, three single-oscillators 19, 20, 21 and two delay elements 22, 23. The essence of the invention is as follows. Each processor element (PE) in an array has its own address (row and column number) by which it can be identified with respect to other PEs in the array. Transit transfers between PEs in an array in eight directions are possible. The proposed device allows the exchange of information between the PE in the array, taking into account the shortest geometrical path and the minimum time delay due to the selection and modification of the transmission address in each transit PE array. If the UE to which the address of the transmitted information is J-adjacent, then the transfer of information occurs directly without modification, which takes into account the loading of the directions of the transmission sector. Thus, the sectorization of the transmission space and the simultaneous analysis of the loading of transmission directions makes it possible, with the help of the proposed device, to increase the productivity and expand the area of its expedient use. 6 Il.

The invention relates to computing and can be used in the construction of high-performance matrix, pipeline, systolic, vector and other processors, in which the data is processed in a computing environment during information processing.

The purpose of the invention is to increase the speed of the device.

FIG. 1 shows a functional diagram of the proposed device; in fig. 2-4 are functional diagrams of a comparison block, a direction selection block and a buffer memory block, respectively; in fig. 5 - time diagrams of the device; in fig. 6 illustrates examples of possible data paths between arbitrary processor elements (PEs) in an array using the proposed devices.

The device (Fig. 1) contains a group of blocks 1 .1, ..., 1 .8 of the buffer memory of the type first entered, first. First register 2, second register 3, third register 4, trigger 5, counter 6, block 7 comparisons, direction selection unit 8, clock generator 9, demultiplexer performed on the key group 10.1, ..., 10.8

multiplexer 11, the decoder 12, the first and second elements And 13 and 14, group 15 .1,. . ., 15.8 elements AND, first, second and third elements OR

16, 17 and 18, the first one-shot 19 on the front of the pulse, the second 20 and the third 21 one-shot on the cut-off pulse and the first and second delay elements 22 and 23. In addition, in FIG. 1 shows the input 24 to set the device address, information inputs 25.1, ..., 25.8 from neighboring devices, reset input 26 and start input 27, as well as outputs 28.1, ..., 28.8 to neighboring devices and output 29 to PE.

Comparison unit 7 (Fig. 2) contains a group of circuits 30.1 ,,. . , 30.16 comparisons, the first and second groups of elements OR 3 1. 1, ..., 31. 16 and 32.1, ..., 32.16,

The direction selection unit 8 (FIG. 3) contains a constant memory unit 33, the first and second subtractors 34 and 35,

from the first to the fourth circuits 36-39 comparisons, the decoder performed on the first and second groups of elements And 40.1, ..,, 40.9 and 41 .1, ..., 41.8, group of blocks of elements And 42.1, ...,

42.8, the group of elements OR 43.1 ,, .., 43.8 and the first to third elements AND 44 - 46, the element OR 47 and

312

element 48 delay. Each block 1.1,. . ., 1 .8 buffer memory group contains a group of registers 49.1, .., 49. p, reversible counter 50 load, the first and second groups of keys 51.1, ..., 51. p and 52.1, ..., 52.P, a group of blocks of elements OR 53.1, ..., 53.n-1, the first and second groups of elements OR 54.1, ..., 54.n and 55.1, ..., 55.p, a group of elements And 56.1 , ..., 56.p, from the first to the fourth elements And 57 60.

Group blocks 1.1, ..., 1.8 is intended for queuing data from eight neighboring devices and indicating the load factor of these queues. The first 2 and second 3 registers are intended for storing the address and operating part of information, respectively, during the selection of the direction of information transfer. The third register 4 is used to store information addressed to the PE of this device. Trigger 5 is designed to indicate the availability of information in blocks 1.1, ..., 1.8. Counter 6, the decoder 12, and the associated relations serve for sequential cycling of the polling blocks 1. 1, ... , 1 8. Block 7 is intended to determine the least loaded direction in each of the eight sectors of possible information transmissions. The block 8 serves to select and modify the direction of the transmission of the received information. The generator 9 is designed to specify two antiphase pulse sequences that determine the synchronization of the device. The key group 10.1, ... 1p.8 is intended for issuing the incoming information to neighboring devices of a regular homogeneous structure. The multiplexer 11, the group of elements And 15.1, ..., 15.8, the third element OR 18 and the relations connected with them define the recording of information in registers 2 and 3 from eight possible sources of information - neighboring similar devices. The first element And 13 serves to enable polling of blocks 1.1, ..., 1.8 if their queues are not empty. The second element of And 14 is designed to allow the output of information in the selected direction, if the queues of blocks 1.1,. .. 1.8 are not empty. The first element OR .16 is used to assemble signals

724

zeroing the counter 6. The second element OR 17, the first one-shot 19 on the front of the pulse, the second one-shot 20 by the cut-off of the pulse and the connections due to them are used to set the single and zero state of the trigger 5. The third one-shot of the cut-off of the pulse is used to set the operation of the counter 6 modulo eight for the purpose of cyclic polling of blocks 1. one, . . ., 1.8. The first delay element 22 serves to delay the closure of the AND 14 element with a zero signal from the forward run of the trigger 5 at the time of issuing the received information on the outputs 28.1,. . . , 28.8 devices on adjacent, devices of regular structure.

The second delay element 23 is due to the transitions of the counter 6, the decoder 12 and the multiplexer 11 and serves to correctly write the received information to the registers 2 and 3 of the device.

The synchronization of the operation of the proposed device occurs through pulses that are formed at the first and second output of the generator 9 and are two antiphase-pulse sequences. The operating cycle of the device consists of the first and second clock pulses, respectively, taken from the first and second outputs of the generator 9 (Fig. 5). On the first clock pulse, the received information is recorded from blocks 1.1 ,. .., 1.8 through 11V multiplexer registers 2 and 3 devices. On the second clock pulse, the direction and further transmission of the received information is selected and modified. The timing diagrams of the operation of the basic elements of the proposed device, without taking into account delays that are not essential for its operation, are shown in FIG. five.

The operation of the proposed device for the formation of the route of communication in the regulator of homogeneous structures is considered.

Information transfer between lyubyg.1I PE in a regular homogeneous structure is carried out in a transit way through other PE array, for example, in eight possible directions using the proposed device. Each PE in the system (proposed device) is assigned a certain

512

address is. (row number and table number in the matrix of processor elements) by which it can be identified with respect to other PE arrays. Transmitting with -information consists of two parts - operational and address. The address part is the address code of the PE to which this operation part is intended. The choice of the direction of transmission of the received information in the proposed | device is as follows. The address portion of the incoming information is compared with the address of this device by the row and column numbers and one of the nine POSSIBLE 5 directions of transmission is determined (eight directions - to neighboring PEs, ninth - to processing this PE). At the same time, the comparison unit 1 determines the least loaded directions for all eight data transmission sectors, the information from which modifies the selected data transfer direction in the direction selection block 8. For example, for the direction East, three directions of this sector (Fig. 1) are analyzed for loading: Southeast (SE), East (C) and Northeast (e-B), for direction SE, directions B, SE and South (S), etc. The algorithm for choosing the minimum load direction in each of the eight sectors is considered using the example of the East direction sector. Let the load factors of the directions of this sector be as follows: for the C-B direction is early A, for the B-B direction, for the SE-B-C direction (by the load factor of the direction is the queue length in block 1.i in the neighboring PE in the corresponding direction) . If (B 5 A) A (in 6C) 1, then the transmission direction in this sector is c, if (A B) L (A

and c) - 1, then the direction of transmission in sector B is determined by the direction C-B, if (C A) L (A i B) 1, then the direction of transfer in this sector is determined by the direction SE-B This information is modified in block 8 direction of the selected sector

data transmission. Thus, the achievement of the 55 OR 17 and the one-shot 19 is established. The choice of the direction of the transfer doesn’t trigger the 5 in a single connection in the array of processor elements. A single unit of uromeit on the shortest path with a minimum of signal at the direct output of the trigger

. No O 5 0 35 45

50

0

delayed. A feature of the sectorization algorithm is the transmission space, which takes into account both the choice of the direction of transmission and the time factor, is the mandatory achievement of the addressed information of the required PE in the array (Figs. 1 and 2). Elimination of the deadlock situation when the PE address is adjacent to the maximum delay in this direction is achieved by introducing funds into block 8, which do not allow modifying the transmission direction depending on the load of directions, if the difference between the row and column indices of the compared addresses does not exceed one . i Before starting work, a single pulse is applied to the device input 26, which zeroes all the dynamic memory elements of the device. At the same time, the address code (row code and column code) of this device relative to other devices in a regular uniform structure is set at the input 24 of the device (FIG. 6).

At the device input 27, a single signal level is set, which triggers the 9-clock pulse generator, at the first and second outputs of which the anti-phase pulse sequences are generated. If there is no information in blocks 1.1, ..., 1.8 (input request queues are empty), zero signals are displayed at the outputs of the load signs of these blocks, which do not change the zero state of trigger 5, and the zero signal from its direct output prohibits the passage of clock pulses , from the generator 9 through the elements And 13 and 14, thereby prohibiting the shift of the queues in blocks 1.1, ..., 1.8 and the choice of the direction of information transfer in block 8.

Upon receipt of information from the co. of the homogenous units of a homogeneous structure (for example, when transferring data between the processor elements in the systolic array), a single signal appears at the output of the sign of loading at least one of the blocks 1.1, ..., 1 .8, which through ele

Gera 5 opens elements 13 and 14 to pass clock pulses from generator 9. The first clock pulse of generator 9, passing through open element 13, increases the contents of counter 6 by one, with the result that a second signal is displayed at the second output of decoder 12, and multiplexer 11 is being prepared for work on the second inlet. If the queue in block 1.2 of the group buffer memory is not empty, then a single signal from the output of the load indication of this block enters the input of the AND 15.2 group element, opening it and setting the multiplexer 11 to the open state through the OR 18 element (otherwise the multiplexer 11 remains in the closed state). The first clock pulse delayed by the element 23 of the delay for the transients of counter 6, decoder 12 and multiplexer 11V is fed to the synchronization inputs of blocks 1. 1, ... 1.8 and the synchronization inputs of registers 2 and 3 and records them block 1.1, .l, 1.85 at the input of the reading of which one is present

signal from the corresponding output

decoder 12. In a similar way, sequential cyclic polling of blocks 1.1, ..., 1.8 and reading information from them into registers 2 and 3 by the first clock pulses takes place. The read information from blocks 1.1, ..., 1.8 consists of two parts — address and operational, which are respectively entered in registers 2 and 3. At the same time, block 7 for each sector of eight possible directions determines the least loaded direction and causes the corresponding signals block 8 ..

The second clock pulse arriving through the open element I 14 to block 8 selects and modifies the direction of information transfer, as a result of which block 8 generates a unitary code corresponding to a specific direction of information transfer (either to one of the eight neighboring devices or to PE processing of this devices). Depending on the unitary code, during the second clock pulse, the received information on the transmission or to the neighbor

eight

-5 o

five

0

5 o 5

0 5

her device through a certain key. And 10, 1,. . ., 10.8 groups, or on the PE of this device, rewrites the received information from registers 2 and 3 into register 4, from the output of which it is sent to the output 29 of the device directly to the processing of this PE.

Information outputs of keys 10.1, ..., 10.8 and outputs of load factors of the corresponding blocks 1. one, . . ., 1 .8, which determine the load factors of these blocks, form information outputs 28.1, ..., 28.8 devices, which are connected to the corresponding eight neighboring devices in a regular uniform structure.

If all information transmissions from neighboring devices are serviced, then the output of the OR element 17 is set to a zero level, which, through the one-shot 20, resets the trigger 5 to the zero state. Elements 13 and 14 are closed with a zero signal from the direct output of flip-flop 5, and the device enters the mode of waiting for the arrival of the following information in blocks 1 .1,. . ., 18 . When the next information is received from neighboring devices, the operation of the proposed device for forming the route of communication in regular homogeneous structures proceeds similarly to the indicated one.

The operation of comparison unit 7 (Fig. 2) is considered.

The information inputs of block 7 receive load factors of the corresponding directions from neighboring similar devices. The output of signs of block 7 consists of forty-eight lines so that each of the eight directions corresponds to three tires from two double lines for each sector consisting of three directions, single ones are formed signals on the lines of the second bus, if the condition (B A) (/ $: C) 1 is satisfied, on the lines of the first tire - under the condition (A c) A (A 6 C) 1 and on the lines of the third bus - in If (C A) L (A B) 1, where A, B, and C are the coeff. the loadings of the corresponding three directions in the sector. The information from the output of block 7 is used to modify the choice of transmission direction with regard to the loading of directions in s

912

torus, what happens in block 8 direction selection.

The operation of block 8 is considered (Fig. 3).

The second clock pulse from the second output of the generator 9 initiates the process of selecting and modifying the direction of data transmission (if the trigger 5 is in the one state, which opens And 14). This pulse from the output of the element 14 is fed to the gating inputs of the first 34 and second 35 subtractors, allowing them to work, and to the input of the reading gates of the node 33, which permanently stores (without information) the unit code. The readers 34 and 35 calculate the absolute difference (the output bit of the loan is not taken into account) between the codes of the rows and columns of the own and the forward address, respectively. Using circuits 36 and 37, the second inputs of which are supplied with the unit code from the output of node 33, as well as using elements AND 44, 45 and 46, a single signal is generated at the output of the OR element 47, indicating that the incoming operand is intended. one of eight adjacent devices. This signal serves to prohibit modifying the transmission of information, taking into account the ITOM of directional load factors, if the addressed device is adjacent.

At the same time, circuits 38 and 39 generate signals comparing their own and incoming addresses to rows and columns, respectively. These signals, acting accordingly on the elements And 40.1, ..., 40.8 and 41.1, ..., 41.8, organize the transmission directions, respectively, without modification and with a modification that takes into account the loading of directions. Element AND 40.9 serves for issuing a single impulse when the addresses match, if the incoming information is intended for this device. Modification information taking into account the loading of directions comes from block 7 to block 8, thereby specifying a modification of the transfer of information depending on the loading of directions. The second clock pulse delayed by the delay element 48 at the time of the possible formation at the output OR 47 of a single signal of the prohibition of modification, arrives at the third input

ten

five

0

five

dy elements 41.1, ..., 41.

0

five

0

five

0

55

And, 40.1, ..., 40.9 and 3. Depending on whether the current address is intended for the neighboring device or not, a direction signal is output to one of the elements of the OR group 43.1, ..., 43.8 or directly from the output of the corresponding element AND 40.1 , ..., 40.8, mine a group of blocks of elements And modifications 42. 1, ..., 42.8 (if the operand is addressed to the neighboring PE), or from the output of the corresponding element And 41 .1, ..., 41.8 through the group of elements of the blocks And modification 42.1,. . ., 42.8 (if the information is not addressed to the neighboring and not to this device). If the analysis of directions in schemes 38 and 39. corresponds, for example, to the direction TZostok (c) and. if the operand is addressed to a non-neighboring PE5To, depending on the load of directions B, C-B and SE-B, the direction of issuance of the operand can be modified and the direction B replaced by the direction SE-B or C-B for this sector of directions. A similar modification depending on the load direction can occur in all eight sectors of information transmission. If the operand is addressed to a neighboring device, then it is transmitted to it directly without modification. Thus, on the second clock pulse of the generator 9, the block generates at its outputs a signal for transmitting information in one of nine possible directions (eight neighboring devices and its own processing facilities (PE)) Information on the device can be received simultaneously from eight neighboring devices and entered in the corresponding blocks 1. 1,..., 1 .8.,

The operation of the memory block 1.1, ..., 1.8 is considered (FIG. 4).

Before the operation of the device, a single signal arriving at the input of the address of the block 1-. 1, ..., 1.8, set the registers 49.1, ..., 49.p and counter 50. When information arrives at the information input of the unit 1.1, ..., 1.8, the recording input of this block from the corresponding input 25.1 ,. .., 25.8 devices receive a single impulse to enter the information, the passage through the open element And 58, produces the following actions: entering through the open zero signal

P1

at the output of the element OR 55.1, the element And 56.1 and the element OR 54.1 at the synchronous input of the register 49.1 synchronize into it the recording of information passing through the public key 51.1 and the block of the elements OR 53.1 to the information input of the register 49.1; acting through the open zero signal from the output of the element OR 55.p element And 59 to the summing input of the counter 50, increases its content by one. Counter 50 indicates, at its output, the load factor of the memory block.

The recording and reading of information in registers 49.1, ..., 49.n. is organized according to the principle of the first to come, first in the following way. Well, the left state of the i-ro (i 1, - n) register with the help of the group of elements OR 55.1, ..., 55.P and the element group AND 56.1, ..., 56.p allows the recording of information in this register and prohibits recording information in (1-1) -and register of the group 49.1, ..., 49. p. Information is entered sequentially in registers 49.1, ..., 49.p according to the recording signals received at the recording input of block 1.1, ..., 1.8 with the help of the And 56.1, group of elements. . . , 56.p, groups of elements OR 54.1, ..., 54.p, groups of keys and groups of blocks of elements OR 53.1, ..., 53.p. The reading of information takes place sequentially on the first clock pulse itself, arriving at the synchronization input of the block 1.1, ..., 1.8. If the queue is not empty, the output of the OR element 55.1 is indicated by a single signal, which prepares the elements 57 and 60 for opening. When reading the information on the read input of block 1.1, ..., 1.8, a single signal is set that opens the element 57 for passing the first tact pulses, which is the movement of the queue in registers 49.1, ..., 49. p. The first clock pulse, entering the synchronization input of the block 1.1, ..., 1.8, prohibits using the AND 58 element to enter information into this block and pass through the open AND 57 element and through the OR elements 54.1, ..., 54.n. register syncs 49.1, ..., 49. p synchronize the information recording in them. The pulse from the output of the And .57 element reduces the contents of the counter 50 by

72

12

0

five

5 o

 -5 DA 35 0 5 0 5

the unit and, entering the control INPUTS of the keys 52.1, ..., 52, p, opens them and organizes the promotion of the queue in registers 49.1, ..., 49.p and issuing information from register 49.1 to the information input of block 1.1, ..., 1.8, from the output of the load factor of which information is given on the load factor from the output of counter 50, and the output of the sign of the load is the readiness signal of this block for issuing information.

When the work is completed, the signal level at the device input 27 is set to zero and it stops its operation (Fig. 3). The operation of the proposed device for the formation of a message route in regular homogeneous structures is illustrated by the example of arbitrary five cycles per game. five.

The selection of the least loaded direction of the transmission sector in the prototype for a regular orthogonal structure occurs sequentially in three cycles of operation of the device, while in the proposed device a similar choice is made in one cycle.

Claims (1)

Invention Formula A message route shaping device in a homogeneous computing system containing a group of buffer memory blocks, three registers, a clock generator, a counter, a multiplexer, a decoder, a multiplexer, a trigger, a group of elements And, three elements IL, two elements And two elements delays, the first output of the clock pulse generator is connected to the first input of the first element And, the output of which is connected to the counting input of the counter and the input of the second delay element, the second input of the first element And is connected to the output trig EPA informa-. The first input of the 1st block of the buffer memory of the group (k 1,.,., n, where n is the number of exchange directions) is the kM information input of the device, the output of the third register is the output for connection to the input of the processor element of the device, the first inputs the first and second elements OR are connected to the reset input of the device, characterized 131 TOM that, in order to increase speed, three single vibrators, a comparison unit and a direction selection unit are included in it, which contains four comparison circuits j two subtractors, a constant memory node, a delay element and a decoder, outputs of transmission direction indications which are connected to the control inputs of the demultiplexer, the information inputs of which are connected to the outputs of the bits of the first and second registers and with the information inputs of the third register, the outputs of the bits of the first and second groups of the second register are connected respectively Initially, to the first information inputs of the third and fourth comparison circuits and to the inputs of the first and second subtracted subtractors, the first and second groups of inputs for specifying the device address are connected respectively to the inputs of the decreasing first and second subtractors and to the second information inputs of the third and fourth comparison circuits, outputs of signs the third and fourth comparison circuits are connected to the information inputs of the first group of the decoder of the direction selection block; the information inputs of the second group of this decoder are connected Signs of the first and second comparison circuits, the first information inputs of which are connected to the outputs of the first and second subtractors, respectively, and the second information (HH), i.e., the inputs are bitwise combined and connected to the output of the memory node of a constant, the device start input, the second clock generator output is connected to the first input of the second element I, the second input of which is under-, the keys through the first delay element to the trigger output, and the output connected to the strobe inputs In order to match the memory node of the constant, the first and second subtractors, and through the delay element of the block for selecting directions to the gate input of the decoder of the same block, the output of the sign of coincidence five 0 five 172 1 addresses of which are connected to the input synchronization of the third register, attributes outputs and information inputs of the comparison unit are connected to 1, information inputs of the third group of the decoder of the direction selection block and the corresponding inputs of load factors of the device, the reset input of which is connected to the reset inputs of the first to third registers and buffer blocks the memory of the group, the outputs of the load attributes of which are connected to the inputs of the second element OR, and to the first inputs of the corresponding elements AND of the group whose outputs are connected to the inputs the third OR element, the output of which is connected to the gating input of the multiplexer, the information inputs of which are connected to the information outputs of the buffer memory blocks of the group, the output of the counter is connected to the information. to the address input of the multiplexer, the outputs of the bits of the first and second groups of which are connected to the information inputs of the first and second registers, respectively, the outputs of the bits of the decoder connected to the second inputs of the corresponding elements AND of the group and the readings of the corresponding; the buffer memory of the group, the output of the second delay element is connected to the synchronization inputs of the first and second registers and blocks of the buffer memory of the group, the output of the second element SH is connected via the first o novibrator to the trigger setup input, and through the second one-shot to the reset trigger input, the output of the corresponding decoder bit is connected via the third one-shot to the second input of the first OR element, the output of which is connected to the reset input of the counter, the write input and the output of the k-ro load factor The buffer memory of the group is the kM input for data navigation and the k-output for the load direction of the device, respectively. 0 five 0 five Faal ti-f fwti r -wf "l Shig.5 viXi axixi i ix -a i UCH at UCH / t x at j at I A, P I, / L GL GL. R. r - “-  vOrx / T XXT sXT X / T f HCCH HH / H HCH / H XV X “: X  eСхххх СС 1х  11/1 I G 3 P -. SHLVI- - -mJ fIP- -, ... Xi5 Txn xixii x TXTXTXTXTXTXr .AT : If f Ji T sXT X / T / H XV X i "- with : -