SU1425671A1 - Device for distributing tasks among processors - Google Patents

Description

The invention relates to computing and can be used in the organization of a computing processor in a multiprocessor: (MPS) or in a multi-machine (MMS) system:

I The purpose of the invention is to expand the functional capabilities of the device 1 by ensuring that the tasks of the ICOPOM process are distributed evenly over time.

The drawing shows the proposed device.

..

Device Contains shift registers 1, elements NOT 2, elements AND 3, elements AND 4, elements OR 5, elements AND 6, triggers 7, triggers 8 elements AND 9, elements AND 10, elements OR 11, comparison circuits 12, elements OR NOT 13, first elements NOT | 14,. elements OR 15, element OR 16, Log 17, block of elements AND 18, | c; counter 19, element NOT 20, shifting Log register 21, block 22 memory, counter P, decoder 24, block 25 of registers rynchronizing inputs 26,27,28 and 29 devices, inputs 30 of the control code of the device, input 31 of the installation of the device |: tva, outputs 32 of the device. The operation of the device begins with the reduction of the initial state of the circuit elements,

: In block 22, control codes are written down in advance: the MOSPD diagnostics system (MMC) sets up to 30 moves 30 the read address of block 22, which corresponds to the number of healthy processors, resulting in a working control code in the register 21; from the first synchronization input 26, the triggers 8j are set to the zero state; from the synchronization input 27, the information bits of the register 17 are reset to the zero state; reset (zero) counters 19 and 23; from input 29, via elements AND 10 and OR, the triggers 7 are set to one; from input 29, a signal is sent to the shift input of control register 21, as a result of which the first bit of the control code appears at its information output; From the fourth clock input 29, a signal is sent to the counter: IR 23, as a result of which the first code number is read from it.

0

five

5 o

five

0

five

0

five

decryption of which leads to excitation of the first output bus of the decoder 24; from input 31 to registers 1, the codes corresponding to the duration of problem solving in MLS (MMS) are entered in such a way that the numbering of the tasks corresponds to the numbering of register 1, the number of tasks M,

The device operates in two modes: search for the minimum execution time code. Tasks and search for the maximum execution time code (hereinafter referred to as the minimum and maximum code, respectively), the number of bits of the control code corresponds to the number of tasks performed on the MLS (MMS), contains H processors and the number of control codes is H-2 (cases where they are not considered, since the assignment is unique and there is no optimization problem). Thus, with a fixed number of tasks performed on the MLS, in the event of processor failures, H-2 procedures appear to optimize the processor load by execution time. And therefore, in block 22, H-2 codes are written, the matching of which occurs when the device is fed to the device 30 input from the diagnostic system (SD) of the IPU address corresponding to the state of the ICP (according to the number of healthy processors). The control travel is written to control register 21. In a sequential reading from the output of the register of 21 bits of the control code, the device operates in the mode of searching for the minimum code or the maximum one. If O is read from register 21, then the minimum code search mode is set. At the same time, a single signal appears at the output of the element 20 allowing the inverse code to pass from the register 1 through the element 2 and the second input of the second element 3 and then the second element SH 5 at the first element AND 6. If register 1 reads 1, then the search mode of the maximum code is set. In this case, a single signal is fed to the third element 4, thereby permitting the passage of the direct code to the first element of the SLC 5.

As mentioned, the type of control code is determined by the number of healthy processors in the MPS (MC) and

its formation is considered - the following ratios between the number of processors and the number of tasks M:

M N I;

.

N 2.

To describe the control code generation algorithm, consider the information field of the ROM in the form of a table

The value of each bit of the string j (O and 1) corresponds to one of the modes of operation of the device. To search only for the maximum code, you must fill in line 3 with all units. If it is necessary to work only in the minimum code search mode, the string j is filled with zeros. In order to optimally distribute tasks to the MPS processors (MMS), the mode control code should be generated as follows:

Case 1. M H &.

t

Position number i is determined

lines j, beginning with which alternating zero and one are written (in the direction of decreasing the numbers of tasks)

i m - (n - J)

2

The remaining positions are filled with units.

Case 2. H 2.

The number i of the position of the line j is determined, beginning with which alternating ones and zero are written (in the direction of decreasing the numbers of tasks):

i 2 (n - j).

The remaining positions are filled with zeros.

Case 3. H 2.

Starting with the highest number of the task, alternating ones and zero are put in the line.

. According to the indicated algorithm, the table of records of the block 22 is for one. A fixed number of tasks. In the same way, tables are compiled for various numbers of problems solved on the IPU. In view of the above, for reading from block 22 to register 21

15

ten

20 5

zo

35

40

45

0

five

The operating line address supplied to the device input 30 must take into account the number of tasks to be solved (table number). and the number of healthy processors.

The device works as follows.

When reading the control code 21 from the first digit of the control code, the mode of searching for the minimum or maximum code is set by allowing the inverse code to pass from register 1 to the first element AND 6 through the elements NOT 2 ,. And 3, OR 5 (in the case of a zero first bit) or a direct code through the elements AND 4 and OR S (in the case of a single first bit). Since in the initial state at the outputs of all the triggers 7 there is a high potential, the signal from the trigger output of the high bit (these triggers are not shown) of register 1; (i 1, M) through the first element AND 6 enters the input of the element OR 16, at the output of which a signal arises if at least one of the codes has a unit in the compared bits. This signal arrives at the first inputs of each comparison circuit 12, at the outputs of which a reset signal of the corresponding trigger 7 is generated, in the event that the information in the compared bit coincides with zero. From trigger 7, the first element AND 6 receives the inhibitory (low) potential before comparing the next bits of the code (inverse or direct).

After the Comparison Procedure of the upper bits of the inverse or direct codes, a shift pulse is applied to the third synchronization input 28 of the device i, as a result of which shift codes 1 shifts the codes by one bit, and the comparison process of the next bits continues, etc. until the number of such shifts and comparisons is equal to the number M, as indicated by the overflow signal of the counter 19. The overflow signal of the counter 19 is fed to the first input of the block And 18, whose outputs are connected to the inputs of the register 17. By the time the signal appears the overflow at the output of the counter 19 ends the process of determining the maximum code (or codes, if there are several of them). In fact, if the device works

in the minimum code search mode, the given, found inverse maximum code corresponds to the minimum code - recorded in the corresponding register 1, In the maximum code search mode, this is the maximum code. At the same time, a single state of several triggers 7 in register 17 and at its outputs one single signal is input, i.e. preference is given to the task, the sequence number of which is the largest among those having the same required time to solve. This is achieved by the presence of elements 13-15.

Thus, the position code of the minimum or maximum code is recorded in register 17 and fed to the information inputs of register block 25, and also ensures that the corresponding second trigger 8 is reset to the zero state I. .

When the device is reset to lioe, the state at the output of the counter 23 is set to provide I, after decrypting on the decoder 24, the i signal of the code write enable signal to the first register of the register block 25. In the future, each time: the signal to the input 29 at the output of the counter JKa is set such a code, which ensures the activation of the second: the third, ..., etc. outputs decipher-; rator 24. As a result, the subsequent | subsequent position codes of numbers of the task; respectively, are entered in the second,; third, ... registers of the block 25 of registers.

After block 2 of the position code registers in the register of the selected task number, input 27 sends a reset signal to register 17 to the initial zero state, and input 29 sets the trigger 7 to single state, to which channel trigger 8 is still in single state (there was no choice of the corresponding task). Starting from the input 29 of the sine-g synchronizing signal, the control code is shifted by one bit in the register 21 (setting the next search mode) and the next code is set on the counter 23, as a result of which the next bus is activated at the output of the decoder 24, from which the write enable signal is received at

0 5

about

five

five

0

five

0

the next register of register 25 block Next, at input 28, supplies a series of shift signals, as a result of which a process of determining the number of the next task is provided for recording in register block 25 and subsequent assignment. Since the trigger 7 of the channel, where the task was selected, was transferred to the zero state by the signal from input 29 (through elements AND 10 and OR 11), the task code recorded in the corresponding register 1 does not participate in the further comparison process. Thus, as a result of the operation of the proposed device, in block 25 of registers position codes of numbers of all tasks intended for execution on the MPS are recorded, the execution times of which (minimum or maximum) alternate in the order of zeroes and ones in the control code. When choosing the first maximum code, the code that follows it becomes the maximum. Similarly for the minimum code. The order in which the task number codes are written, and having in mind that they are also recorded in block 25 of registers as convenient for assignment, we will establish a simple algorithm for distributing tasks among processors, which can be implemented by the MSC control processor. The reading of the number codes of the selected tasks is carried out from the outputs 32 of the device.

Claims (1)

Formula of o bre en and A device for assigning tasks to processors, containing an OR element, a register, a block of AND elements, the first counter, m channels (m is the number of tasks to be solved), each of which, except the first and th channels, contains a .., shift register, first the element I, the first trigger, the comparison circuit, the element, the SH-NON element, the first element NOT and the first element OR, the first channel contains the shift register, the first element AND, the first trigger, the comparison circuit and the element S1I-NOT, and channel contains a shift register, the first element And, the first trigger and the comparison circuit, and the formation inputs of the shift registers of each channel are connected to their outputs, the shift inputs of the shift registers of all channels are connected to the first synchronizing input of the device and the counting input of the first counter, the direct output of the first trigger of each channel is connected to the first input of the first element I, the output of which is connected to the first the input of the comparison circuit and through the first element NOT - with the first input of the element OR — NO of the same channel and with the corresponding input of the element OR whose output is connected to the second inputs of the circuits cf each channel, the first input of the first element AND channels from the second to) (in-1) -ro is connected to the first input of the first element OR of its channel, the second input of the first element OR and the element OR NOT of each channel except (t-1) th, is connected to the output of the first element OR of the next channel, the second input of the first element OR and the element OR NONE (ml) -ro channel is connected to the first input of the first element II of the first channel and the first control input of the block of elements AND, The main control panel of the inputs of which are connected to the outputs of the elements OR NOT a group of information The inputs of the block of elements I are connected to the outputs of the first counter, the outputs of the block of elements I are connected to the inputs of the register, the reset input of which is connected to the second synchronizing input of the device, characterized in that, in order to extend the functionality by processors, it contains the element NOT, the shift register, the memory block, the second counter, the decoder, the register block, and the second element is NOT, the second, third, fourth and fifth elements are And, the second and third th elements OR, the second trigger, and the output of the shift register of each channel is connected to the first input of the second element AND and through the second element NOT to the first inputs of the third elements AND channels, the second inputs to the second; elements And channels are connected to the output of the shift register and the input element NOT, the output of which is connected to the second inputs of the third elements AND channels, the outputs of the second and third elements And each channel. .- except for the first, are connected respectively Q 20 25, 35 45 50 55 with the first and second inputs of the second OR element and the first channel outputs of the second and third elements AND are connected respectively to the first and second inputs of the first OR element, whose outputs and outputs of the second OR elements of the other channels are connected to the second inputs of the first AND elements of their channels, the unit input of the first trigger is connected to the output of the fourth element AND of its channel, the reset input of the first channel trigger, except the first, is connected to the output of the third element SH of its channel, the first input of which is connected to the output house of the p element and its channel, the second input of the second element OR, | the first and third elements OR of the remaining channels are connected to the output of the comparison circuit, the reset input of the second flip-flop of each channel is connected to the register register of the same name and the corresponding information inputs of the register block whose outputs are device outputs, the single input of the second flip-flop of each channel is connected to the third sync the device input, the direct output of the second trigger is connected to the first input of the fourth element And its channel, the inverse output of the second trigger is connected to the first input The second element of its channel, the second inputs of the fourth and fifth elements of the channels are connected to the fourth synchronizing input of the device, the shift input of the shift register and the counting input of the second counter, the information outputs of which are connected to the inputs of the decoder, the outputs of which are connected to the recording resolution inputs the register block, the information inputs of the shift register are connected to the information outputs of the memory block, the address inputs of which are connected to the control code inputs of the device, are parallel inputs information recording shifting registers of each channel are connected to the setting input device, resetting the first flip-flop of the first channel input connected to an output of the second member I.PI whose input is -soedinen yield fifth AND gate its channel. Number of processors Task numbers .l-ii-i ::: lll ::: t n - 1 n - 2 Pe, qn-z.i PP - (, g CL-g, 7 n -. J  4n-j, 7  2 field j, (, 2.2 one. Control Code Field  Note. j 1, K is the number of serviceable food processors, Editor. G. Gerber Compiled by M. Kudr seam Tehred A, Kravchuk Proofreader A. Obruchar Order 4771/47 Circulation 704 VNIIPI USSR State Committee PS cases of inventions and discoveries 113035, Moscow, Zh-35, Raushsk nab., 4/5 m I-l.i PE-7; CP-1, GO CP-D, 1P Jn-j, tn one.  2 m Subscription