SU1434451A1 - Arrangement for planning computing process in multiprocessor system - Google Patents

Abstract

The device relates to computing technology and is intended for functioning as part of a multiprocessor computer for automatic selection of the next task from a variety of tasks with a structure defined by an acyclic oriented graph, and for automatic synthesis of work schedules. The aim of the invention is to enhance the functionality of the device by reassigning tasks in fixed time slots. The device contains a trigger matrix, two groups of OR-NOT elements, five groups of AND elements, three groups of counters, two groups of triggers, a register of selected vertices, a priority register, an encoder, a control unit consisting of a clock generator, an AND element, a circuit the initial start-up, the OR element and the trigger, the register of current tasks being processed, the OR element, the counter j) clock pulses, the quantum register, the clock pulse generator, the inputs-outputs. 1 il.

Description

The invention relates to computing and is intended for operation in a multiprocessor computer for automatic selection of a regular program from a set of programs with a structure specified by an acyclic oriented graph, as well as for automatic synthesis of work schedules.

The aim of the invention is to expand the functionality of the device by reassigning the execution of tasks through fixed time slots.

The drawing shows the functional diagram of the device.

The device contains the matrix I of triggers 2, the group of Elements OR-NOT 3, by the number of rows of the matrix, the group of elements AND 4 by the number of columns of the matrix, the group of counters 5, the group of triggers 6, the group of elements I 7, the number of counters 8, the group triggers 9, group of elements AND 10, register of 11 selected vertices, implemented on triggers 1 If, register 12 of priority, group of elements AND 13, encoder 14, control unit consisting of generator 15 clocks, element 16, circuit 17 initial nycKaj element OR 18, trigger 19, input 20 start device, input 21 entries in reg device 11, information output 22 of the device, control unit 23 in the junction of the specified circuits 15 - 19 group of elements AND 24, group of counters 25, group of elements of the IPI-NE 26, register 27 of current processed tasks, element OR 28, counter 29 clock them - pulses, quantum register 30, generator 31 clock pulses, input 52 of the device task being processed, input 33 of writing to counter 29, start input 34 of generator 31, outputs 35, 36 of the device interrupt request. Input 21 and one of inputs 32 are used for writing to registers 12, 27, respectively. The encoder 14 represents a combinational circuit that provides the excitation of one or more of its outputs, corresponding to the maximum code stored in the counters of the same name.8

The device works as follows.

Initially, information on the topology of the simulated graph is entered into matrix I. In this case, triggers 2; (i.

j - 1, n), which are arc formers, are set to one state if there is an information link from the i-th vertex to j th The corresponding trigger 2 is determined by the intersection of the i-th row and the j-ro column. Other triggers 2 j:,, as well as triggers 6,9,19, counters 8, registers 12, 27 are in the zero state (installation chains to the initial states and entries in the registers and triggers are not shown). Counters 5 and 25 of the corresponding vertices of the graph add pulses to the weight of the peaks to the total capacity of the counters; code 30 is added to the register 30 that complements the time quantum to the full capacity of the counter 29. After the initial information is entered at the outputs of the WL-HE 3 elements, the connecting outputs of flip-flops 2 in the lines corresponding to the final vertices of the graph} will be high potentials, since the graph is assumed to be acyclic and for the final vertices the corresponding flip-flops 2 are zeroed. Initially, the device determines the values of the maximum paths connecting the given vertices with the final ones (the values of the levels of the women are formed). In this case, the start signal at the input 20 of the initial start circuit 17 starts the generator 15, from the output of which the pulses go to the inputs of the elements 4 and 7, and then to all the counters 8, since in the initial state all the triggers 6 are in the zero state The control inputs of the And 7 elements are connected to the inverse of the outputs of the flip-flops 6: In addition, the counting pulses flow through the And 4 elements to those counters 5 for which the flip-flops 2 of the same row of the matrix 1 are in the zero state. Therefore, a high potential appears at the output of the corresponding elements of ILY-HE 3, so that there is a high potential at the controlled input of the element of the same name And 4.

By counting the number of pulses proportional to the weight of the simulated vertex, counter 5 overflows, the overflow signal sets the corresponding trigger 6 to the one state, and all the 2 triggers in this column of the matrix model. The network 1 returns to the zero state. Transferring the trigger 6 to a single state ensures excellent

increasing the supply of counting pulses through element 7 to the input of registering counter 8, in which the code of the maximum path from this vertex to the final vertex of the interpreting graph is recorded,

The considered actions are repeated until the low potentials are present at the outputs of all the flip-flops 6. At the output of the element OR 18 there will be a low potential, as a result of which the supply of counting pulses from the output of the generator 15 through the element 16 to the information inputs of the elements AND 4.7 stops. From the output of the trigger 19 high potential is given to the input of the warning, computer and. the control input of the I4 encoder, which provides high potential on one or more of its outputs, which correspond to the maximum code stored in the same counter 8, provided that the first controlled input of the And 10 elements is supplied with a high potential from the outputs of the elements SH-NOT 26 As a result, register 12 sets up a code defining the tasks, if any, that can be performed. If in register 12 there is at least one unit, this means that the task, determined by the number of the given bit, can be assigned to processing. The information from register 12 is fed to output 22 and further to the input of the computer-dispatcher. If the code in register 12 is zero, then in the absence of actual tasks, this means that the processing of the graph is complete (it is assumed that the computer-manager keeps information about the current tasks, which allow to recognize such situations).

tion). In addition, in the presence of several 45 elements and 13 there will be a high potential, according to which the trigger 9 goes into a single state; feeding the code of the given task from counter 8 to the inputs of the encoder 14 discontinuous units in register 12 requires sequential sampling of tasks for processing (for example, the task with the minimum number of bits in register 12 is executed first), and after Toro, 5Q write- as the choice of the current task is made, the computer- with another code, by which the computer-dispatcher for the inputs 32 of the device sets the code in the register 27 of the current processed tasks, the presence of 1 in the iM bit of which determines, gg that i - the task is being processed. At the same time, the installation of such a code should not destroy the previously installed ones; the picker chooses unimplemented tasks.

Claims (1)

Formula inveni.ni A device for planning a computational process in a multiprocessor system containing a matrix (php prostrate corresponding to those selected for 0 five 0 five processing in the current quantum tasks. In view of the state of register 27, a zero level is set at the output. de those elements OR-NOT 26 of the additional group that correspond to the tasks being processed, thereby these tasks are temporarily excluded from the field of the dispatcher computer. After the finished tasks are assigned to the processors, the dispatcher computer loads into the counter 29 time to the full capacity of the counter from the register 30 quantum control signal applied to the input 33 of the device, and starts the generator 31 clock pulses by applying a pulse to the input 34 of the device. The signals from the generator 31 are fed to the input of the counter 29, as well as through the elements AND 24 to the inputs of those counters 25 and the subtractive inputs of those counters 8 for which the corresponding register bits 27 are set to 1. When the time slice ends (the counter 29 overflows) or upon completion of one or several tasks (the corresponding counter 25 overflows), the corresponding overflow signal through the OR element 28 resets the register 27 of the currently processed tasks and the generator 31, and also enters output 35 of the device and then goes to A request for the termination of a computer controller, signaling the need to select the following tasks. Next, a new cycle is made, assignments. As soon as one of the tasks is completed, the corresponding counter 25 overflows, and the overflow signal sets the corresponding register register of the selected vertices to one. As a result, 0 the potential over which the trigger 9 goes into a single state; The supply of the code of the level of the given task from the counter 8 to the inputs of the encoder 14 stops and on the register 12 it records from another code by which the computer-disk It also registers on register 12 with another code, according to which the computer disk Pekcher chooses unrealized tasks. Formula inveni.ni It also registers on register 12 with another code, according to which the computer disk Device for planning a computational process in a multiprocessor system containing a matrix (php) five  triggers, control unit, a group of elements OR NOT, two groups of counters, two groups of triggers, register. the selected vertices, the priority register is four groups of AND elements, the encoder, the control output of the control unit is connected to the gate input of the encoder and is the first output of the device interrupt request, the output of the encoder is connected to the information input of the priority register, the output of which is the information output of the device, the bits of the output of the priority register are connected to the first inputs of the elements AND of the first group, the second inputs of which are connected to the bits of the output of the register of the selected vertices, the outputs of the elements the first group are connected to respective inputs of a zero setting of the first group of flip-flops, the input priority register write enable is, input Confirm Oden ready computer 6 functional capabilities due to reassignment of tasks through fixed time quanta, the fifth group of elements AND, a third group of counters, an additional group of elements OR-NOT, the register of current tasks being processed, the element OR, the counter of clock pulses of the quantum register, clock generator, moreover, the information input of the register of current processed tasks is the input of a sign of the device task being processed, the output of the register of the current task being processed are connected to the first inputs of the elements of an OR NOT additional group and the first inputs of the elements of the fifth group, the second inputs of the elements of the OR NOT of an additional group are connected to the direct outputs of the first group of flip-flops, the outputs of the elements of the OR-NOT additional group are connected to the second inputs of the elements devices, the outputs of the elements And the second 25 And the second group, the generator output the groups are connected to the information inputs of the encoder, the outputs of the elements AND of the third group are connected to the information inputs of the counters of the first group, the outputs of which are connected to the first inputs of the elements AND of the second group, the inputs of the OR-NOT groups are connected to the outputs of the triggers of the corresponding matrix rows, the outputs of the elements OR NO groups are connected to the first inputs of elements AND of the fourth group, the synchronization output of the control unit is connected to the second inputs of elements AND of the fourth group and the first inputs of elements AND of the third group The element outputs of the fourth group are connected to the information inputs of the second group counter, the overflow outputs of which are connected to the reset inputs of the matrix triggers and the zero installation inputs of the second group triggers, the inverse outputs of which are connected to the second inputs of the control unit j the start input of which is the start input of the device, characterized by the fact that, in order to expand five clock pulses are connected to the information input of a clock counter and second inputs of elements And a fifth group, the outputs of which are connected to the subtractive inputs of the counters of the first group respectively and the counting inputs of the counters of the third group respectively, the overflow outputs of the counters of the third group are connected to the bits of the information input of the register of the selected peaks and the corresponding inputs of the OR element, the overflow output of the clock counter is connected to the corresponding The Q input of the OR element, the output of which is connected to the reset input of the clock generator, the reset input of the register of current tasks to be processed and is the second output of the request for g interrupt the device, the initial setup input of the clock counter is connected to the output of the i-KBaHTa register, the start input of the clock generator is connected to the start input of the device, and the control input by entering the information of the counter of clock pulses is the same as the input of the device. 0