SU1367017A1 - Device for selecting replaced element - Google Patents

Abstract

The invention relates to the field of computer technology and is intended to select from the existing set of elements the one to be replaced by another. In this case, the choice of a replaceable element from a set consisting of m elements is made randomly from the group g-n of the most long-used elements of this set, for which, unlike the group of n most often used elements (), there is no chronology of their use. . The invention can be used in computers and computing systems, computing devices and digital automation devices. The purpose of the invention is to reduce the amount of equipment. The device contains a code converter 1, a memory 2, a register 3, a counter 6, a control unit 5 and a comparison unit 4. The device provides a selection of the item to be replaced among those m-n items for which it is not maintained. the chronology of their use, and reduces the number of code converter stages and word width memory and register. 6 Il. from 5 (L

Description

co o si

1 13

The invention relates to computing, is intended to select from an existing set of elements that must be replaced by another, and can be used in computers and in the numerical systems, computing devices and digital automation devices.

The purpose of the invention is to simplify the device by reducing the amount of equipment.

FIG. 1 is a block diagram of a device for selecting a replaceable element, in which FIG. 2 is a functional diagram of a code converter; FIG. 3 is a functional block diagram comparison; 4 is a functional block diagram of the control unit; figure 5 is a functional diagram of the counter; figure 6 - timing charts of the device.

A device for selecting a replaceable element contains a code converter 1, memory 2, register 3, comparison unit 4, control block 5 and counter 6, information input 7, address input 8, synchronization input 9, random number input 10, first 11 and 12 control inputs and output 13. The decoder 1 consists of 14-16 comparison circuits, AND elements 17-18 and three groups of AND-OR elements 19-21.

Comparison unit 4 is performed on comparison circuits 22-25 and the element OR 26, the output of which is denoted by W.

The control unit 5 contains elements AND 27-30, an element OR 31, the output of which is denoted C, and two RS flip-flops 32 and 33, the direct outputs of which are denoted, respectively, S, and S.

The second INPUT1 of the code converter 1 is connected to the information input 7 of the device, and the output of the code converter 1 is connected to the second memory input 2, the third input of which is connected to the address input 8 of the device, the fourth input to the first controlled input 11 of the device, and the output to the first input register 3, the output of which is connected to the first input of the encoder 1 and the first input of the control unit 5; the second input of which is connected to the second input of the register 3, the first input of the memory 2 and the input 9 of the device synchronization, the third input of the control connection unit 5 ene with a second councils

Q

50

5 o

0

five

five

72

The main input 12 of the device and the output from the first input of the counter 6, the second input of which is connected to the input 10 of a random number of the device, and the output to the second input of the comparison unit 4 and the output 13 of the device.

Code converter 1 is designed to form a new history code of using elements in accordance with the code of the element number of input 7 of the device and the current history code from the register 3 output, the second inputs of the comparison circuits 14-16 being connected to information input 7 of the device and the first group of outputs of the code converter 1, and the first inputs, respectively, with the first, second and third groups of outputs of the register 3. The first output of the comparison circuit 14 is connected to the second input of the group of AND-OR elements 19, the third input of which is connected n with the second (inverted) output of the comparison circuit 14, a first input of AND gate 18 and a first input of AND gate 17, a first output of which is coupled to the second input group of AND-OR 20, A third input. which is connected to the second (inversion) output of the element 17, the second input of which is connected to the inverse output of the comparison circuits 15 and to the second input of the element 18, the first output of which is connected to the second input of the group of elements AND-OR 21, the third the input of which is connected to the second (inverse) output of the element And 18, tre. This input is connected to the inverse output of the comparison circuit 16. The first inputs of groups of elements I-ШШ 19 and 20 are connected to the second group of outputs of register 3, the fourth entrance of the group of elements AND-OR 19 to the first group of outputs of register 3, the third group of outputs of which is connected to the fourth entrance of the group of elements AND-OR 20 and the first input of the group of elements, AND-OR 21, the fourth input of which is connected to the fourth group of outputs of the register 3. The group of outputs of the code converter 1 is connected to the input 7 of the device, and the groups of the outputs of the groups of elements AND-OR 19-21 are respectively connected to the second memory input 2

Memory 2 is designed to store the state of chronology of several group of elements, with the required group of elements being determined by

313

A resuser coming from the address input 8 of the device connected to the third memory input 2, the second input of which is connected to output groups of the code converter 1. The first memory input 2 is connected to the output CI of the synchronization input 9 of the devices, and is the recording input, the fourth the memory input 2 is connected to the first control input 11 of the device and is a recording enable input, and the memory output 2 is connected to the first input of the register 3.

Register 3 is designed to store the current state (code) of the history of the selected group of elements, the first input of register 3 is connected to memory 2, the second input is connected to the output SI1 of the device synchronization input 9, and the output to the first input of the code converter 1 and the first input of block 4 is a comparison, all the bits of the output of register 3 are divided into groups of inputs so that if the set of m elements contains chronologies of using n elements (), then the number of groups of outputs of register 3 is n, and the number of bits in the group equals llogjmL and for and m «8 and claim 4, there are therefore

4 groups of outputs, 3 bits in each group.

Comparison unit 4 is designed to compare the contents of counter 6 with the codes of output groups of register 3, with the first inputs of comparison circuits 22-25 connected to the first, second, third and fourth groups of outputs of register 3, respectively, the second inputs of comparison circuits 22-25 are connected to the output of the counter 6, and the outputs of the comparison circuits 22-25 are connected respectively to the first, second, third and fourth inputs of the OR element 26, the output of which is connected to the first input of the block.

5 controls

The control unit 5 is designed to generate synchronization signals and control the operation of the counter 6, with the S input of RS-trigger 33 connected to the S input of RS flip-flop 31, the second input of the OR element 31, the second control input 12 of the device, and the second (inverse ) the inputs of the elements 27 and 28, the first inputs of which are connected respectively with the outputs CI2 and CI1 of the input 9 of the device synchronization, the output of the element I 28 is connected to the R input of the RS flip-flop 32, the output S1

0

five

0 5 0

five

0

five

ABOUT

five

which is connected to the corresponding input of the counter 6, the input S2 of which is connected to the corresponding output of the RS flip-flop 33, the R-input of which is connected to the output of the element 30, the second input of which is connected to the output of the element 27 and the input of the element 29, whose first input connected to the first (inverse) input of the element 30 and the output W of the block 4 (Fig. 3), and the output of the element 29 and connected to the first input of the element OR 31, the output of which is connected to the corresponding input of the counter 6.

The counter 6 is designed to obtain the number of the element to be replaced and can be implemented, for example, on the elements 500IE136, where the inputs D1, D2 and DZ of the counter 6 are connected respectively to the bits of the input IO of the random number of the device, the synchronous input C of the counter 6 is connected to the corresponding output of the block 5 control, the outputs of which are connected to the corresponding inputs of the counter 6, and the output L of the counter 6 is connected to the corresponding input of the comparator unit 4 and the output 13 of the device.

A device for selecting a replaceable element can be connected to a computer processor, for example, to its buffer (CASH) memory to determine the number of the replaced block in the column when partially associating the buffer memory or to the fast forwarding buffer (TLB) to determine the number of the replaced record buffer in case of a page fault in the system with virtual memory. Therefore, all external control signals, synchronization signals, memory addresses 2, the number of the element used from input 7 come from the processor. The output 13 of the device is fed to the processor. The source of the random number arriving at the input 10 of the device can be the group of bits of a certain processor register, which is updated with a sufficient frequency.

The device works as follows.

The device maintains a chronology of the use of a group of n (n m) of the most frequently used (active) elements of a set of m elements. The least active (most recently used) are the remaining mn elements of this set and

the replacement element among them is randomly selected.

The operation of the device is illustrated by the example of a set of elements and a group of n 4 of the most active elements of this set. The chronology of the use of the group of the most active elements is maintained by code converter 1, memory

2 and register 3. The dialing elements are assigned numbers from 0 to t-1. The binary code of the element number has bits (for m 8 it has

3 yes. Since the chronology is maintained for n elements, the size of the memory slot 2 is equal to the size of register 3, is n-Hog mG bits, and for m 8 and n 4 it is 12 bits. These bits are divided into 4 groups (p 4) with 3 bits of Glog 8G each, and the code in the bits of the first group determines the number of the most active (last used) element of the set, the code in the bits of the second group is the number of the element used before the most active, etc .; finally code

in the fourth group, the number of the least active (most recently used) element in the group of the four most active elements of this set. Accordingly, the bits of register 3 are divided into 4 groups of bits, and the code in the bits of the first group determines the number after-. the last used element of the set, and the code in the bits of the fourth group is the number of the most recently used element of the group of four elements.

Memory 2 stores the state (codes) of the history of groups of elements of several sets of elements. The chronologists of the group of elements of the required set of elements are selected according to the number of the given set, coming from the address address 8 of the device to the third memory entry 2. The selected memory word 2 is entered into register 3 by the pulse SI1, coming from the input 9 of the device synchronization to the first memory input 2 .

Input 7 of the device to the second input of the code converter 1 receives a 3-bit code for the number of the element used. To the first input of the code converter 1, the outputs of register 3 are supplied, reflecting the chronology using not four of them

0

15

0

thirty

25

0

45

35

50

55

elements of a set of eight elements.

Code converter 1 generates codes at its outputs that reflect the new state of the history of using the four most active elements of this set of eight elements, the code in the bits of the first group of outputs. It determines the number of the last (most active) element of the set, the code in the second bits group of outputs - the number of the next by, activity of the element, etc., not the end, the code in the bits of the fourth group of outputs - the number of the least active (most recently used) element of the group of four elements Comrade

The word formed in this way enters the second information input of memory 2 and, if there is an enable signal from the first control input 11 of the device, which arrives at the fourth input of memory 2, is recorded into memory 2 via the sync signal CI2, coming from the synchronization input 9 of the device to the first memory 2, at the same address, at. Secondly, a selection was made of a memory of 2 words that preserved the old state of the chronology of using the group of elements of a given set of elements.

Suppose that the group consisting of the four most active elements of the set of eight elements with numbers from 0 to 7 includes 0,2,3,6 elements and the chronology of their use is as follows: 2; 6; 0; 3. At the same time, in such a record, the number of the most active element of the group occupies the leftmost place, the number of the next element by activity is indicated by the second left, etc., and the number of the most inactive element in the group is indicated in the extreme right position. Thus, the most active element in the group is 2, the least active is 3. Memory word 2, which determines the chronology of the use of this group of elements, is received by impulse SI1 into register 3, the bit of the first group of outputs containing code 2, the second groups, outputs - code 6, bit of the third group of outputs - code O, bits of the fourth group of outputs B4 - code 3V

Let the second code of the code converter 1 (FIG. 1) from the informational

Input 7 of the device receives a 3-bit code for the number of the element used, equal to 0. Then (Figure 2) the three bits of the first group of outputs of the code converter 1 contain a new code of the most active element equal to O. At the first output, the circuit 14 has no signal O, indicating that the incoming code (O) did not compare with the code of the most active element in the old chronology (2). From this it follows that the activity of element 2 in the new chronology should be less than in the old one. At the second (inverse) output of the comparison circuit 14, there is a signal and at the outputs of the group of AND-OR elements 19 there are bits of the first group of outputs of register 3. Thus, the code in three bits of the second group of outputs of code converter 1 becomes equal to 2. At the high signal (inverse a) comparison circuit 15 there is a signal

The outputs of the AND 18 element arrive at the inputs of the AND-OR 21 group of elements, and at its fourth outputs there are bits of the fourth group of outputs of register 3, i.e., the code in bits of the fourth group of outputs of code converter 1 is 3. Thus, the new chronology has view 0; 2; 6; 3

Q Let the second input of the code converter 1 from the information input 7 of the device receive the code of the number of the element used, equal to 5. The method described above at the outputs

5 code converter 1 with initial chronology of 0; 2; 6; 3 appear to be respectively codes 5; 0; 2; 6. Element number 3 is transferred to the group of four least active elements.

The random selection of an element for replacement among a group of m-n least active elements of a set of m elements is carried out by block 4

M, indicating noncompliance with 25, control unit 5 and counting code O with code 6 in the bits of the second group of outputs of the register 3 and, therefore, the first output of the AND 1 7 element contains a signal 1, and the second (inverse) output 30 of them elements of this set, co-element I 17 - signal O. This means that the code of the number of the element used, which is the most active in the new chronology, did not enter the code of the number of the first or the number of the second most active element in the old chronology, therefore, activity element 6 should be lowered. The outputs of the AND 17 element are fed to the inputs of three AND-OR elements from group 20, the outputs of this group contain bits of the second group of outputs of register 3, i.e. code in bits of the third group. code transducer outputs 1

becomes equal to 6. At the output (inverse of the pulse of the SI1 to the front edge of the layer) of the comparison circuit 16 there is a blowing SI1. On the front edge

signal oh that testifies

about comparing who came in on entry 7

device code O with code O in

The bits of the third group of outputs are regi-gQ, i.e. the reception signal information code P, E, the RS flip-flops 32 and 33 are set to one and the signal states and

page 3. Then on the first output of the element 18 there is a signal O, and on the second (inverse) output of the element 18 there is a signal 1. This means that the code of the number of the element used is contained among the four most active elements and, moreover, the activity remaining element (s) should not be changed.

In addition, the signal E is fed through the OR element 31 as a signal C to the synchronous input of counter 6 and the trailing edge of the signal E n eg the counter is entered into the 3-bit code from the input 10 of the random number of the device. Suppose, for example, this is code 2. In the same clock cycle (i.e. during the validity of the VIA signal of signal E) at address input 8

com. 6. The implementation of such a random choice is illustrated by the example of a set of 8 elements and a group of four that have been used most recently.

0

This is the element from the numbers 1, 4, 5, 7. The group of the most active elements, therefore, includes the elements with the numbers 0; 2; 3 and 6. Counter 6 (Fig. 5) performs the operations of receiving information, direct counting and storing, defined by codes 11, 01 and 00, respectively, received as signals S1 and S2 from the control unit 5 (Fig. 4). If it is necessary to determine the number of the element to be replaced, the signal E is fed through the second control input 12 of the device, which is extended from the leading edge of the E-signal. RS flip-flops 32 and 33 are set to one and the signal states and

gQ, i.e. The information reception code P is sent to counter 6. In addition, the signal E through the element OR 31 as a signal C is fed to the synchronous input of counter 6 and on the falling edge of the signal E n eg the counter is entered in the 3-bit code from input 10 of the random number of the device. Suppose, for example, this is code 2. In the same clock cycle (i.e. during the validity of the VIA signal of signal E) at address input 8

y1

the device to the third input of memory 2 received: the address of the set, one of the elements of which must be replaced. This address is retained at the input 8 of the device until the end of the operation of selecting the element to be replaced. The selected word of memory 2, containing the numbers of the four most active elements of this set, is stored in register 3 according to sync pulse SI1.

In the next cycle, after the end of the action of the signal E, the leading edge of the pulse CI1 RS-flip-flop 32 drops to zero with a single signal at the output of the element E28. Thus, the output of the RS-flip-flop 32 contains a signal i.e. Code 01 is generated, which sets up the direct account mode of counter 6.

The output bits of the counter 6 are fed to the second input of the comparator unit 4, the first input of which is fed to the output of the register 3. The bits of the output groups of the register 3 determine the number codes of the four most active elements of the set. Let, for example, the bits of the first Group contain code 2, the bits of the second group - code 6, the bits of the third group of OT - code O, the ranks of the fourth group - code 3. Since counter 6 is assigned random; code 2, signal 1 is present at the output of the comparison circuit 22. which causes the output signal OR 26 signal state. In block 5, the control signal permits the passage of the sync signal SI2 from the output of element AND 27 through element 29 to the input of element OR 31, the output of which in the form of signal C is inputted to the synchronous input of counter 6. On the falling edge of the CM2 pulse, the contents of counter 6 increased

The unit is equal to and equals g, as in the proposed device, the number 3. The new code stored in the counting transducer contains n-1 jam 6 is again compared in block 4 comparison with the four naibopen codes. The width of a single word in the memory of chronologies in the device-prototype is equal to η-Hog Г, and in the proposed

There are more active elements of the set stored in register 3. Since in the fourth-gQ device, there is m-llog bit patterns. If a

 If the bit group is set to code 3, then the output of the comparison circuit 25 is signal 1, which causes the signal state at the output of the OR 26 element. In block 5 of control (Fig. 4), the signal allows the passage of a sync pulse SI2 to the output from the element OR 31 and further to the input C of the counter 6. On the falling edge of the memory, it is necessary to store the usage histories of N sets of elements, then saving memory capacity in the proposed device compared gg with prototype is N (mn) llogm bits. The size of the output memory register in the prototype device and the proposed one is equal to the memory depth of the memory. Therefore, in proposing

ten

pulse

The CI2 counter content is incremented by one and becomes equal to 4. A new code equal to 4 comes from the output of counter 6 again to the input of comparison unit 4, where it is compared with the contents of register 3. This time, the outputs of comparison circuits 22-25 contain the signals D therefore, a signal is present at the output of the OR 26 element. The signal blocks in the control unit 5 the passage of the clock pulse CI2 through the element AND 29, therefore, at the output of the element OR 31 there is a signal O, i.e. synchronous input of counter 6 is blocked. Impulse SI2 passes through the element And 30 and, arriving at the R-input of R5-TpHrrepa 33, resets it

0 zero Then, at the outputs R5-TpHrrers 32 and 33, there are signals and, giving the code 00, which determines the storage operation in the counter 6. Thus, in the counter 6

5, code 4 does not coincide with any of the number codes of the four most active elements of the set. Consequently, the counter contains the code of the number of the element being replaced. This code is transmitted to the output 13 of the device (Fig. 5) as the number of the item to be replaced.

In the proposed device, a reduction in the number of equipment is achieved due to the introduction of a counter, a comparator unit and a control unit that selects a replaceable element among those m – n elements of a set of m elements for which there is no history of their use. In order to maintain a chronology of the use of all the elements of the set in the prototype device, (t − 1) step-wise code converter is used, while

five

0

m as in the proposed device, the co-converter contains p-1 st

stump. The width of a single word in the memory of chronologies in the device-prototype is equal to η-Hog Г, and in the proposed

In the memory, it is necessary to store the chronologies of using N sets of elements, then the saving of memory capacity in the proposed device compared to gg with the prototype is N (m-n) llogmf bits. The size of the output register of the memory in the device-prototype and the proposed one is equal to the word size of the memory. Therefore, in offer1

The device has a register of (tn) T bits less than the register in the prototype, and the bit value entered in the proposed device is always equal to llog tG. As a result of decreasing the number of code converter stages, the response time of the proposed device slightly exceeds the response time of the prototype device.

Claims (1)

Invention Formula A device for selecting a replacement element containing a code converter, a memory and a register, the first input of which is connected to the memory code, the first input of which is connected to the synchronization input of the device and the second input of the register, the output of which is connected to the first input of the code converter, the second input which is connected to the information input of the device, and the output of the code converter from Ulz 367017 12 connected to the second memory input, the third input of which is connected to the address input of the device, and the fourth input of which is connected to the first control input of the device, which, in order to simplify the device, contains counter, control unit and comparison unit, the first input of which is connected to the first input of the encoder and the register output, and the output of the comparison unit is connected to the first input of the control unit, the second input of which is connected to the second input of the register, In this case, the third input of the control unit is connected to the second control input of the device, and the output of the control unit is connected to the first input of the counter, the second input of which is connected to. the input of a random number of the device, and the output of the counter is connected to the second input of the comparator unit and the output of the device. ftuf.3 from.  {- ,, .. tpueS