Device for redistribution of tasks among processors

 

(57) Abstract:

The invention relates to computer technology and may find application in fault-tolerant multiprocessor systems for load balancing between processors during faults. An object of the invention is to reduce the time of searching the permissible redistribution of tasks by analyzing the current state of the computing system. The mentioned technical problem is solved due to the fact that the device contains a block of memory elements, two decoder, the block read / write block definition lookup and storage unit codes task. 1 C.p. f-crystals, 7 Il.

The invention relates to computer technology and may find application in fault-tolerant multiprocessor systems for load balancing between processors.

A device containing a group of memory elements, the decoder, the block-busting lookup and item. However, when large numbers of processors n and solve their problems n significantly increases the time of determining the allowable distribution, since the number of all possible substitutions is equal to n! [1].

Closest to the technical nature of the items to memory, the decoder block shifts codes task, block loop counters and the element.

However, this device is characterized by a large time specify a valid lookup [2].

Indeed, at a certain variant of the current state of the computational system (cs) that contains n processors, each of which is able to perform one of the n tasks, the unit shifts codes task should generate all n! possible substitution, which for large n is characterized by a significant time cost.

An object of the invention is to reduce the time of searching the permissible redistribution of tasks by appropriate analysis of the current state of the aircraft.

The current state of the aircraft is defined by a matrix of the current state [ij], the element whichij= 1 if the i-th processor capable of performing the j-th task, andij= 0 otherwise. The specified technical task is solved through a faster determination of the non-zero diagonal matrix works the current state, which consists in the following. In the matrix specified by the i-th row and j-th column, containing the largest number of zeros, the element located at the crossroads of them must have n and column are excluded from the matrix, and the same operations are performed on the matrix of dimension (n-1)(n-1). In each subsequent step, the next processor is assigned to perform the next task. If in the process of sorting Podiatric one of them will be zero, then the potential allocation of tasks does not exist, which corresponds to the failure of the entire aircraft. Thus, a gradual transition from the matrix dimension nn to matrix dimension 11 determines the possible redistribution of n tasks to n processors. Obviously, this will require nnn=n3steps instead of n!, the implemented prototype. Starting with n=6, the time required to search a valid redistribution device that implements the method, is significantly reduced in comparison with prototype: 63= 216 < 6! = 720 [3].

To solve this technical problem in a device for redistribution of tasks among processors, containing a block of memory elements and the first decoder, the first group of input devices is a group of inputs of the first decoder, the group of n outputs of which are connected with the first group of n inputs of the block of memory elements, input a second decoder, the block read / write block definition lookup and storage unit codes task, and the second group is administered by a group of n inputs of the block of memory elements, the first group of n outputs of which are connected with the first group of inputs, a second group of n outputs from the second group of inputs and a third group of two outputs from the third group of inputs of the block definition lookup, the first output of which is connected to the first input, the second output to the second input of block read and write and is the first output device, and the first group of n outputs of the block read and write connected with the third group of inputs, a second group of n outputs from the fourth group of inputs of the block of memory elements, the third and fourth groups of m (where m= ] log2n[) outputs block reading and writing are connected respectively with the first and second group of inputs of the storage unit codes task group of the n m-bit output which is the second output, the second output is connected to the third input of the block read and write, the third group of m inputs connected to the group of inputs of the second decoder, and a fourth group of n inputs with a group of respective outputs of the first decoder.

The introduction of the proposed device mentioned blocks and their relations with the mentioned set are the essential feature because they help to reduce the search time of topoptropica, in Fig.2 is an embodiment of the block of memory elements of Fig. 3 is an embodiment of the memory element of Fig.4 is an embodiment of the block read and write, in Fig.5 - implementation option definition block substitution, in Fig.6 - implementation option storage unit codes task, Fig. 7 is an embodiment of the groups of input elements And.

Device for redistribution of tasks among processors includes (see Fig. 1) block of the memory elements 1, block read and write 2, two decoder 31, 32unit definition lookup 4, the storage unit codes task 5.

The block of memory elements 1 (see Fig. 2) contains a group of memory elements 61. ..6ngroup n-vchodove elements OR 71...7nn-input accumulating element, OR 8, two n-vchodove element OR 91, 92, input element, And 10.

The memory element 6 (see Fig. 3) contains a group of triggers 111...11ngroup of input elements AND 121...12ngroup of input elements AND 131...13ngroup of input elements AND 141...14n, two-item And 15, the n-input accumulating element OR 7.

Block reading and writing 2 (see Fig.4) contains a pulse generator 16, group m-rasra now And m elements in each 191, 192two m-bit decoder 201, 202two m-bit decoder 211, 212two groups of triggers 221...22nand 231...23ntwo groups of input elements AND 241. ..24nand 251...25n, input element And 26, two two-input element OR 271, 272, input element And 28, two-element OR 29, the trigger 30.

Unit definition lookup 4 (see Fig. 5) contains two m-bit encoder 311, 311m-bit multiplier 32, 2m-bit register 33, the comparison circuit 34, 2m-input accumulating element OR 35, the input element And 36, the delay line 37, the input element And 38.

The storage unit codes task 5 (see Fig.6) contains the m-bit decoder 39, the group of m-bit registers 401...40nn groups of two-input elements And m elements in each 411...41nthe comparison circuit 42.

A group of input elements And 19 (41) (see Fig.7) has m input elements And.

The set of input can be performed on the chips of any series, having in its composition logic elements: counters, registers, decoders, and so on (for example, the IC series 133, 155, 106, 500 etc).

After the n3steps all processors are configured to perform their respective tasks, if a valid distribution exists. If at any step, you will read a zero row and / or column (not counting the already excluded), the block definition lookup 4 outputs a signal about the failure of the entire sun and stops the block read and write 2, since in this case a possible option pogatsa in a single state, i.e., each processor can perform any of the n tasks. Write "0" in the cell of the memory element 6 (see Fig.3) occurs when the loss of the i-th processor's ability to perform the j-th task. When "0" is set at the output of the trigger 11jthe memory element 6i. At the same time the code of the j-th task is sent to the input of the comparison circuit (SS) 42 (see Fig.6), which opens with a group of input elements AND 41ithe storage unit codes task 5. If code j-th problem corresponds to the current setting of the i-th processor, the output SS 42 will be set to "1", which will set Tg 30 block read and write 2 in one state (see Fig.4), than open the key And 28 of the pulse generator 16. The pulse generator start to arrive at the counting input m-bit counter 171. The output of the counter overflow 171connected across the input element OR 272with a counter input is similar to the counter 172in turn, the output of the counter overflow 172connected to the counting input of the counter 173. United thus the counters 171...173form 3m-bit counter or counter to n3(m=]log2n[). Feedback output overflow counter 171, 172with a counter input through br CLASS="ptx2">

The counters 171and 172connected information outputs to the inputs of the decoders 201and 202. Each i-th output of the decoder 201through the key 24iconnected to bus miblock of the memory elements 1 (see Fig.2), similarly, each i-th output of the decoder 202through the key 25iconnected to bus m1i. Sequential excitation of the outputs of the decoders 201and 202lets iterate over the elements of the memory 6 (row of the matrix of the current state of the decoder 201and the same triggers 11 at the same time all of the memory elements 6 (columns of the matrix of the current state of the decoder 202). And in each moment of time the selected one row and one column. Line items are formed from the outputs of the elements AND 141...14nthe selected memory element 6, the elements of the column are formed at the outputs of the same elements And 13 all memory elements 61...6n. n-input elements OR 7 is required for decoupling of the outputs of the And elements 13 and 14.

Unit definition lookup 4 works as follows (see Fig.5). In the register 33 is initially stored the number of n2. To the input of the encoder 311receives n-bit code, each discharge kotorogo2do elements of the selected column. From the outputs of the encoders 311, 312the inputs of the multiplier 32 receives the amount of units in the selected row and column, respectively. From the output of the multiplier 32 is the product of the number of units in row and column arrives at SS 34, where it is compared with the contents of the register 33 (initially with the number of n2). SS 34 outputs a signal at the first input of two-input element And 36, if the contents of register 33 more incoming work. To the second input element And 36 of the block of memory elements 1 a signal that the intersection of the selected row and the selected column is "1". If there are two of these signals "1" from the output element And 36 through the delay line (LPA) 37 is fed to the input of the write-enable register 33, which is written a new work units in the selected row and column. At the same time in the unit of read and write 2 given the signal to remember the numbers in this row and this column. Work units also fed to the inputs of the element OR NOT 35, the output of which appears if the product is zero, i.e., set to zero row or zero column. The output of the element OR NOT 35 is connected to the first input of two-input element And 38. "1" to the second input of the and of these two signals from the output element 38 receives the signal on the stop block read and write 2 and report the Refusal SU", because the permissible redistribution of tasks between processors does not exist.

For each signal block definition lookup 4 code line number and the code column number are recorded in the registers 181, 182block reading and writing 2 (see Fig. 4). Thus, n2steps in registers 181, 182will store the codes of the i-th row and j-th column, which contains the least number of units that defines a new configuration of the i-th processor - it is required to perform the j-th task. Through the n2steps output element And 26 opens group input elements AND 191, 192and stored in registers 181, 182codes go on the record in the storage unit codes task 5, and inputs the corresponding decoder 211, 212. Horny i-th output of the decoder 211install Tg 22iin the "0" state, closes the key 24ibus miblock of the memory elements 1 are set to "0" state. In the next cycle of operation of block read and write 2 when you have selected bus mi(i-th line), its contents will not be disclosed in block definition lookup 4, because the zero state bus miwill close all the elements AND 141...14n(see the "crossed out" j-th column.

A new version of the distribution of tasks in the form of pairs of numbers (the processor number and the number of tasks) every n2steps sequentially recorded in the storage unit codes task 5 (see Fig.6). Code line number (processor number) of the block read and write 2 to the input of the decoder 39, code column number (number of tasks) is supplied in parallel to the inputs of all the registers 401... 40n. The decoder 39 gives permission to write code only tasks that case, the number of which corresponds to the received number of the processor. Obviously, through the n3steps in all registers 401...40nwill store the new setting sun, if possible.

The memory element 6 operates as follows (see Fig.3). In good condition armed forces all processors can perform any of the n tasks, so all triggers 111. ..11ninstalled in one state. With the loss of the i-th processor's ability to perform the j-th task on the tyres liand l1jappear logical unit that receives the first and second inputs of two-input element AND 12ilocated at the intersection of these tires. "1" at the output of the element AND 12isets the trigger 11iin the zero state.

When with whom B> block of the memory elements 1. The contents of the string excited by a bus miformed at the outputs of i1, i2,...inthat column brought a bus m1jformed at the outputs of j1I , j2,...jn(see Fig.2). n-input elements OR 71...7nrequired for decoupling of the outputs of the And elements 13, 14. "1" at the output of kithe memory element 6 shows that at the intersection of the selected row and the selected column is non-zero matrix element current status: "1" at the first input of two-input element And 15 appears when the excitation bus mi(row selection), "1" on the second entry appears if Tg 11j, Horny bus m1j, (select column) is in the "1" state. The outputs of the kiall memory elements 6 are combined n-shadowy element OR 8. Bus m1, m2,...,mncombined element OR 91tires m11, m12,..., m1ncombined element OR 92. "1" at the output of the element And 10 indicates that the current bus miand m1jare in the excited state, i.e. the i-th row and j-th column is not removed from the matrix condition.

Stop block reading and writing 2 (see Fig.4) produced by the overflow of the counter 173through the element OR 29 sets Tg 30 in the "0" state, the key 28 is closed and prevents the passage of pulses from generator 16. If possible variant redistribution does not exist, the signal to another input of the OR element 29 is supplied from the block definition lookup 4.

Technical and economic efficiency of the proposed device is to reduce the search time option redistribution of tasks among processors. A possible case of failures of processors, when the prototype to search for redistribution would require the enumeration of all n! possible options. In the proposed device in case of any failures will require only n3steps, and if such an option does not exist, the device stops and issues a report "the Refusal of the armed forces" immediately, as soon as in a matrix state is detected zero pediatrica. At sufficiently large values of n (n 6), the gain in time compared to the prototype appears to be significant.

This device can be used when designing fault-tolerant computing systems, in which the recovery after a failure is achieved by the redistribution of functions assigned to the processors.

the 2023292, G 06 F 9/46, 1994

3. Handbook of mathematics for scientists and engineers. Korn G., Korn T. - M. : Nauka. The main edition of physico-mathematical literature, 1984.

1. Device for redistribution of tasks among processors, containing a block of memory elements and the first decoder, the first group of input devices is a group of inputs of the first decoder, a group of n (n is the number of processors in the computing system and the number of tasks that can solve each processor outputs of which are connected with the first group of n inputs of the block of memory elements, characterized in that it comprises a second decoder, the block read / write block definition lookup and storage unit codes task, and the second group of input devices is a group of inputs of the second decoder, group of n outputs of which are connected with the second group of n inputs of the block of memory elements, the first group of n outputs of which are connected with the first group of inputs, a second group of n outputs from the second group of inputs and a third group of two outputs from the third group of inputs of the block definition lookup, the first output of which is connected to the first input, the second output from the second input unit citybanan with the third group of inputs, the second group of n outputs from the fourth group of inputs of the block of memory elements, the third and the fourth group of m (where m = ]log2n[) outputs block reading and writing are connected respectively with the first and second groups of inputs of the storage unit codes task group of the n m-bit output which is the second output, the second output is connected to the third input of the block read and write, the third group of m inputs connected to the group of inputs of the second decoder, and a fourth group of n inputs with a group of respective outputs of the first decoder.

2. The device under item 1, characterized in that the block read and write contains a pulse generator, three m-bit counter, two m-bit register, two groups of two-input elements And m elements each, four m-bit decoder, two groups of n triggers, two groups of two-input elements And n elements each, two two-element And three two-input element, OR trigger, and the first input unit is a single input trigger, direct the output of which is connected to a second input of the first input element And first input connected to the generator output and the output with the first input of the first two-the odes of which is connected to the information input of the first m-bit register, the outputs of which are connected to the second inputs of the respective input elements And the first group of elements And containing m elements, and to the inputs of the first m-bit decoder, each of the n outputs of which are connected to the first input of the corresponding input element And the first group of input elements And containing n elements, and n-th output is connected also to the first input of the second input element And the second input is connected to the n-th output of the second m-bit decoder, and the return to the first inputs of two-input elements And the first and second groups of input elements And m elements each, the outputs of which form the third and fourth groups of outputs of the block and connected to the inputs respectively of the third and fourth m-bit decoders, each of the n outputs are connected to the corresponding zero input triggers the first and second groups, individual inputs are connected to the bus the initial installation, and direct the output to the second inputs of the respective input elements And, respectively, the first and second groups of input elements And m elements each, and the first inputs of two-input elements And the second group are connected to the corresponding output is vtorogo are the outputs of two-input elements And the first group of input elements And, containing n elements, and its third input is the enable input of the first m-bit register connected to the input of the recording resolution of the second m-bit register whose outputs are connected to the second inputs of two-input elements And the second group containing m elements, and the information inputs to the inputs of the second m-bit decoder and data outputs of the second m-bit counter, the counting input of which is connected to the output of the second input element OR the first input of which is connected to the second input of the first input element OR the output of the overflow of the first m-bit counter, the second input to the output of the overflow of the second m-bit counter and the counting input of the third m-bit counter, the output of the overflow which is connected to the second input of the third two-input element OR the output of which is connected to the zero input of the trigger, and the first entrance is the second entrance to the block.

 

Same patents:

The invention relates to a corresponding system, that is able to work in real time and is tolerant to errors system for signal processing, with many blocks of data that are connected to each other through the blocks of data

The invention relates to the field of computer engineering and can be applied in communication systems

The invention relates to a method of congestion control messages elementary program in the electronic switching system

The invention relates to computer technology and is intended for use in a local area network with bus topology to control the transmission of data packets through a common channel

The invention relates to computing and can be used to provide machine-to-machine exchange in distributed computer systems and computer networks

The invention relates to computer technology and can be used for accessing a shared resource

The invention relates to automation and computing, and more specifically to the priority data processing, and is intended for use in multiprocessor systems, local area networks and distributed control systems

The invention relates to computer technology and can be used in distributed information processing systems for the organization of exchange between the Central computer and subscribers of the system on a shared line

The invention relates to computer technology, automatic control and can be used in devices interrupt programs, control data flows and the formation of an Executive address data banks in logical processors

FIELD: computer science.

SUBSTANCE: device has n-byte query register, query limits location systems, each of which consists of counting timer and OR element, OR element, AND element, keys cascade.

EFFECT: higher reliability and speed of operation.

1 dwg

FIELD: method and device for processing data for preserving recurrent status in data processing device.

SUBSTANCE: device has data processing block, having multiple functioning modes, for each of which special memory stack is present. Method describes operation of this device. Data carrier contains program, configuring data processing device for performing stages of method.

EFFECT: decreased size of code and decreased interruption processing delay.

3 cl, 16 dwg

FIELD: engineering of information processing systems.

SUBSTANCE: system contains master-system for processing information, interface, central communication device, client system for processing information, object model. In accordance to method each master system sends to central communication device elements of its data array determined in appropriate master-representation, while in master-representation of connected master system elements of data array are contained, for which system has data priority.

EFFECT: simplified specification and development of interfaces between technical applications.

2 cl, 6 dwg

FIELD: engineering of interrupt processing mechanisms in computer systems.

SUBSTANCE: system contains processor with multiple contexts for execution of commands stored in memory. In response to common interrupt logical processors of processor with multiple contexts compete for receiving access to jointly utilized register. First logical processor gaining access to aforementioned jointly utilized register processes common interrupt. Remaining logical processors return from interrupt.

EFFECT: increased productiveness of system.

4 cl, 5 dwg

FIELD: computer engineering, possible use in data exchange systems and local computing networks.

SUBSTANCE: device contains N≥2 client blocks, clock impulse generator, N client time controllers, OR element, AND-NOT element, selector-multiplexer, two N-input AND-NOT elements, two priority encoders, main wait time controller.

EFFECT: increased probability of timely servicing of clients under conditions of real functioning process of data exchange systems, with continuous dynamics of change of modes of different priority requests from clients.

4 cl, 7 dwg

FIELD: engineering of computers for controlling memory, in particular, external memory controllers.

SUBSTANCE: memory control device for operation in memory controller network contains memory controller being an owner unit, capable of controlling the blocking of certain data area during execution of input-output outputs, and component for exchanging messages, providing for transmission of at least one message with blocking request, permission of blocking, blocking removal request and blocking removal signal, and also input-output component, while any image of aforementioned data area, received by instant copying thereof, is maintained as coherent relatively to data area itself, and input-output component may position previous direct confirmation, that this data area remains coherent to any such image, to cash-memory, and may perform input-output operations on basis of aforementioned previous direct confirmation. Method describes operation of aforementioned device. Software product for computer is realized on machine-readable carrier and contains a program recorded thereon, realizing operations of aforementioned method.

EFFECT: expanded functional capabilities.

3 cl, 3 dwg

FIELD: engineering of means for pausing execution of a stream until certain memory access occurs.

SUBSTANCE: in one variant of realization, processor contains a set of executive devices, capable of executing a set of streams. First stream includes a command, which determines the address being tracked. Logical pausing means pause execution of first stream, and monitor causes renewal of first flow as reaction to access of given address being tracked.

EFFECT: increased processor productiveness.

5 cl, 14 dwg

FIELD: methods for automatic execution of a program, connected to data file, when data file and program being executed are positioned on different computer units.

SUBSTANCE: in methods, program being executed is accessed through graphic image of data file type, realized in the network, which includes client system and a set of server systems. Client system receives the scheme, which determines connection between the set of programs being executed and corresponding set of data file types. Graphic image of data files is displayed, information about selection of graphic image of data file is received from server system, on basis of it program to be executed is selected and executed.

EFFECT: increased productivity of system due to distributed execution of programs.

9 cl, 19 dwg, 3 tbl

FIELD: method and system for providing user interface information to client.

SUBSTANCE: in accordance to the invention, access system contains registration mechanism. Client environment for automatic processing of user interface receives registration information from the client and transmits user interface information after receipt. Server for automatic processing of user interface receives registration information from client environment for automatic processing of user interface and notifies processor of user interface about registration, and also receives user interface information from user interface processor. The server contains filtration device for filtering out information of no interest to client, and notification device for notifying the client about information which is of interest to the client.

EFFECT: ensured capacity for filtration and coordination of excessive and disorienting notifications.

2 cl, 11 dwg

FIELD: telecommunications.

SUBSTANCE: device contains a set of central processor units, which are assigned a common external up address in telecommunication network which allows packet data. IP messages, addressed to a network element, are received, and received IP messages which contain first messages are identified. First value is identified in first message and first message is transmitted to central processor unit on basis of identified first value, if identified first value is not equal to zero.

EFFECT: ensured load balancing for central processor when using several types of traffic.

3 cl, 3 dwg

Up!