Memory controller scheduling requests according to scores

The present application claims priority under 35 U.S.C. §119(a) to Korean Patent Application Number 10-2015-0018016, filed on Feb. 5, 2015, in the Korean Intellectual Property Office, which is incorporated herein by reference in its entirety as set forth in full.

1. Technical Field

The present disclosure relates to a memory controller. Particularly, embodiments of the present disclosure relate to a memory controller capable of variably adjusting weights for determining scores with respect to a plurality of requests, calculating the scores using the weights, and determining a processing order of the requests according to the scores.

2. Related Art

A memory controller determines a processing order of a plurality of requests provided from an external device, e.g., a host, in order to control a memory device.

A conventional memory controller has used a scheduling method such as a First Come First Served (FCFS) method or First Ready First Come First Served (FR-FCFS) method in order to determine a processing order of a plurality of requests provided from a host.

The FCFS method is a scheduling method of firstly processing a request firstly received, and the FR-FCFS method is the same as the FCFS method except that it firstly processes a request for a row in an open state.

As described above, a conventional memory controller performs the request scheduling by a fixed reference.

Embodiments of the present disclosure are directed to a memory controller capable of improving its performance by variably controlling weights for various elements affecting scheduling performance in order to dynamically control a request scheduling rule.

In one embodiment of the present invention, a memory controller includes a request queue that stores requests provided from an external device, a scheduler that calculates a score for each request included in the request queue and determines a processing order of the requests based on the scores for the requests, and a weight generation circuit that generates a weight vector including weights used to calculated the scores.

According to the present technology, weights for various elements affecting scheduling performance are variably controlled to calculate scores, and request scheduling is performed according to the scores. As a result, it is possible to test performance for various scheduling rules in one memory controller, and an optimal scheduling rule is selected to thereby improve the scheduling performance.

Features, aspects, and embodiments are described in conjunction with the attached drawings, in which:

FIG. 1 is a block diagram of a memory system including a memory controller according to an embodiment of the present disclosure;

FIG. 2 is a block diagram of a weight generation circuit of FIG. 1 according to an embodiment of the present disclosure;

FIG. 3 is a detailed block diagram of the weight generation circuit of FIG. 1 according to an embodiment of the present disclosure;

FIG. 4 is a flowchart illustrating an operation of a control part of FIG. 3 according to an embodiment of the present disclosure;

FIG. 5 is a block diagram of a scheduler of FIG. 1 according to an embodiment of the present disclosure;

FIG. 6 is a detailed block diagram of a score calculation circuit of FIG. 5 according to an embodiment of the present disclosure; and

FIG. 7 is a table for explaining an operation scheme of a variable decision section of FIG. 6 according to an embodiment of the present disclosure.

Hereinafter, a memory controller according to embodiments of the present disclosure will be described in detail with reference to the accompanying drawings. In the following description, the same reference numerals are used to designate substantially the same elements.

FIG. 1 is a block diagram of a memory system 1 including a memory controller 100 according to an embodiment of the present disclosure.

The memory controller 100 receives a read or write request from a host 1 , and controls a memory device 20 in response to the request in order to perform a requested operation.

The memory controller 100 includes a request queue 110 , a scheduler 130 , and a command generation circuit 140 . The request queue 110 stores read and write requests provided by the host 1 . The scheduler 130 determines a processing order of the requests stored in the request queue 110 and outputs a request selected from the requests stored in the request queue 110 . The command generation circuit 140 generates commands for controlling the memory device 20 based on the selected request output from the scheduler 130 .

In an embodiment, the scheduler 130 calculates a score vector including scores for the requests stored in the request queue 110 and selects, among the requests, a request for performing an operation on the memory device 20 based on the calculated scores.

The memory controller 100 further includes a weight generation circuit 120 for generating a weight vector that includes one or more elements. Each element of the weight vector is multiplied by each variable value used when the scheduler 130 calculates the scores. The generation of the weight vector using the variable values will be described later.

The weight generation circuit 120 generates the weight vector with reference to a weight control signal and an operation state of the memory controller 100 . The operation state includes states for the requests stored in the request queue 110 .

The weight vector and score calculation scheme will be described in more detail below.

FIG. 2 is a block diagram illustrating the weight generation circuit 120 of FIG. 1 according to an embodiment.

The weight generation circuit 120 includes a state observation section 121 and a weight decision section 122 .

The state observation section 121 observes the operation state of the memory controller 100 including the request queue 110 as illustrated in FIG. 1 , recognizes a state of each request, and generates a state vector based on the states for the requests stored in the request queue 110 .

In an embodiment, the state vector may include one or more elements including a length of a read queue, a length of a write queue, a maximum execution time of a predetermined number, e.g., 128, of requests recently processed, a value indicating whether an operation being processed relates to a read request or a write request, a hit rate in a prefetch operation, and the like.

A prefetch operation performed in a memory controller indicates an operation for reading in advance data from the memory device 20 , the data being expected by the memory controller to be requested. A hit rate is a concept associated with probability that a read request is actually received to read the data that has been read in advance. Since the prefetch operation and the hit rate are concepts well-known in the related technology, a detailed description thereof will be omitted.

The weight decision section 122 may determine a weight vector with reference to the weight control signal or the state vector. The weight control signal may be generated in the memory controller 100 or provided by an external device, or may be provided by the host 10 . The weight control signal may directly designate each element of the weight vector.

FIG. 3 is a block diagram illustrating the weight generation circuit 120 of FIG. 1 according to an embodiment.

In the present embodiment, the state observation section 121 generates a state vector including, as elements, a length RQL of a read queue, a length WQL of a write queue, a maximum processing time MW of a predetermined number of requests recently processed, and a value RW indicating whether an operation selected by the scheduler 130 relates to a read request or a write request.

The weight decision section 122 includes a control part 1221 , first to third selection parts 1222 - 1 to 1222 - 3 , and first to third registers 1223 - 1 to 1223 - 3 . The weight decision section 122 outputs a weight vector including a first weight w 1 , a second weight w 2 , and a third weight w 3 as elements.

The control part 1221 generates and outputs first to third selection signals cw 1 to cw 3 for controlling the first to third selection parts 1222 - 1 to 1222 - 3 based on the weight control signal, the state vector, and values of weights w 1 to w 3 that are stored in the first to third registers 1223 - 1 to 1223 - 3 , respectively.

The first selection part 1222 - 1 selects a designated value (1, −1, or 0) or the value of the first weight w 1 stored in the first register 1223 - 1 according to the first selection signal cw 1 , and outputs the selected value as a new first weight w 1 .

The first weight w 1 is multiplied by a first variable value (yi 1 ) to output a first element used in calculating each score si of a score vector, i being in a range of 1 to N, the score vector including N scores. Accordingly, the first weight w 1 is a factor for determining the influencing power of the first element in calculating each score si of the score vector. This will be described in more detail with reference to FIG. 6 below.

In FIG. 3 , the designated values (1, −1, and 0) determined in advance are exemplary values, and may be changed according to an embodiment. For example, when the first weight w 1 has a value 0, the first element does not affect the calculation of the score si. When the first weight w 1 has a negative number, e.g., −1, the first element is considered as a negative factor in calculating the score si. When the first weight w 1 has a positive number, e.g., 1, the first element is considered as a positive factor in calculating the score si.

Since configurations and operations of the second selection part 1222 - 2 and the third selection part 1222 - 3 are substantially the same as those of the first selection part 1222 - 1 , a detailed description thereof will be omitted.

FIG. 4 is a flowchart illustrating an operation of the control part 1221 of FIG. 3 according to an embodiment

In the present embodiment, the weight control signal may directly designate values of the first to third weights w 1 to w 3 , and has higher priority than the state vector in determining the first to third weights w 1 to w 3 .

The control part 1221 performs an operation S 10 to S 14 for determining a value of the first selection signal cw 1 , an operation S 20 to S 28 for determining a value of the second selection signal cw 2 , and an operation S 30 to S 38 for determining a value of the third first selection signal cw 3 .

The first weight w 1 to the third weight w 3 are initialized to 0 by the weight control signal at S 1 . The first weight w 1 to the third weight w 3 in steps S 1 , S 10 , S 20 and S 30 represents those designated by the weight control signal.

Hereinafter, the operation for determining the value of the first selection signal cw 1 will be described.

If the weight control signal is input, the control part 1221 determines whether a value of the first weight w 1 designated by the weight control signal is 0 at S 10 .

When the value of the first weight w 1 designated by the weight control signal is 0, the control part 1221 sets the value of the first selection signal cw 1 to 11 at S 14 .

When the value of the first selection signal cw 1 is set to 11 at S 14 , the first selection part 1222 - 1 selects 0 as a new value of the first weight w 1 , and the selected value 0, i.e., the new value of the first weight w 1 is stored in the first register 1223 - 1 .

When the operation performed for the memory device 20 is determined to be a read request at S 11 , the control part 1221 sets the value of the first selection signal cw 1 to 10 at S 13 . Otherwise, the control part 1221 sets the value of the first selection signal cw 1 to 00 at S 12 .

When the value of the first selection signal cw 1 is set to 10 at S 13 , the first selection part 1222 - 1 selects the value of the first weight w 1 stored in the first register 1223 - 1 , and the selected value is stored in the first register 1223 - 1 as the new value of the first weight w 1 . When the value of the first selection signal cw 1 is set to 00, the first selection part 1222 - 1 selects 1, and the selected value 1 is stored in the first register 1223 - 1 as the new value of the first weight w 1 .

When the value of the first selection signal cw 1 is set at S 12 to S 14 as described above, the control part 1221 returns to step S 10 and repeats the aforementioned operation. Such repetition may be performed according to an information update cycle of the request queue 110 .

Next, the operation for determining the value of the second selection signal cw 2 will be described.

If the weight control signal is input, the control part 1221 determines whether a value of the second weight w 2 designated by the weight control signal is 0 at S 20 .

When the value of the second weight w 2 designated by the weight control signal is 0, the control part 1221 sets the value of the second selection signal cw 2 to 11 at S 28 . Otherwise, the control part 1221 determines whether an operation performed for the memory device 20 relates to a read request at S 21 .

When the operation performed for the memory device 20 relates to a read request, the control part 1221 determines whether the length RQL of the read queue exceeds a first threshold value TH 1 at S 22 . Otherwise, the control part 1221 sets the value of the second selection signal cw 2 to 10 at S 25 .

When the length RQL of the read queue exceeds the first threshold value TH 1 , the control part 1221 determines whether the maximum processing time WM exceeds a second threshold value TH 2 at S 23 . Otherwise, the control part 1221 sets the value of the second selection signal cw 2 to 10 at S 25 .

When the maximum processing time WM exceeds the second threshold value TH 2 , the control part 1221 sets the value of the second selection signal cw 2 to 00 at S 27 . Otherwise, the control part 1221 determines whether the maximum processing time WM is smaller than a third threshold value TH 3 at S 24 .

When the maximum processing time WM is smaller than the third threshold value TH 3 , the control part 1221 sets the value of the second selection signal cw 2 to 01 at S 26 . Otherwise, the control part 1221 sets the value of the second selection signal cw 2 to 10 at S 25 .

When the value of the second selection signal cw 2 is set at one of S 25 to S 28 as described above, the control part 1221 returns to step S 20 and repeats the aforementioned operation. Such repetition may be performed according to the information update cycle of the request queue 110 .

Finally, the operation for determining the value of the third selection signal cw 3 will be described.

If the weight control signal is input, the control part 1221 determines whether a value of the third weight w 3 designated by the weight control signal is 0 at S 30 .

When the value of the third weight w 3 designated by the weight control signal is 0, the control part 1221 sets the value of the third selection signal cw 3 to 11 at S 38 . Otherwise, the control part 1221 determines whether an operation performed for the memory device 20 relates to a read request at S 31 .

When the operation performed for the memory device 20 relates to a read request, the control part 1221 determines whether the length RQL of the read queue exceeds the first threshold value TH 1 at S 32 . Otherwise, the control part 1221 sets the value of the third selection signal cw 3 to 10 at S 35 .

When the length RQL of the read queue exceeds the first threshold value TH 1 , the control part 1221 determines whether the maximum processing time WM exceeds the second threshold value TH 2 at S 33 . Otherwise, the control part 1221 sets the value of the third selection signal cw 3 to 10 at S 35 .

When the maximum processing time WM exceeds the second threshold value TH 2 , the control part 1221 sets the value of the third selection signal cw 3 to 01 at S 37 . Otherwise, the control part 1221 determines whether the maximum processing time WM is smaller than the third threshold value TH 3 at S 34 .

When the maximum processing time WM is smaller than the third threshold value TH 3 , the control part 1221 sets the value of the third selection signal cw 3 to 00 at S 36 . Otherwise, the control part 1221 sets the value of the third selection signal cw 3 to 10 at S 35 .

When the value of the third selection signal cw 3 is set at one of S 35 to S 38 as described above, the control part 1221 returns to step S 30 and repeats the aforementioned operation. Such repetition may be performed according to the information update cycle of the request queue 110 .

The aforementioned first to third threshold values TH 1 to TH 3 are arbitrary constant values selectable by those skilled in the art.

FIG. 5 is a block diagram illustrating the scheduler 130 of FIG. 1 according to an embodiment.

In the present embodiment, the scheduler 130 may include a score calculation circuit 131 and a request selection circuit 132 .

The score calculation circuit 131 generates a score vector by using variable values, which are calculated based on information provided by the request queue 110 , and the weight vector provided by the weight generation circuit 120 .

The score vector includes, as elements, scores corresponding to the requests stored in the request queue 110 . The request selection circuit 132 selects a request corresponding to a maximum score among the scores included in the score vector, and outputs the selected request.

The score calculation circuit 131 calculates the variable values in order to calculate the scores corresponding to the requests, and calculates the scores by combining the variable values and the elements of the weight vector.

FIG. 6 is a block diagram illustrating the score calculation circuit 131 of FIG. 5 according to an embodiment.

The score calculation circuit 131 includes a variable decision section 1311 and operating sections 1312 - 1 to 1312 -N. The variable decision section 1311 determines variable values by using information provided by the request queue 110 in response to each request. The operating sections 1312 - 1 to 1312 -N calculate scores, e.g., s 1 to sN, by using the variable values, e.g., y 11 , y 12 , y 13 , . . . , yN 1 , yN 2 , and yN 3 , outputted from the variable decision section 1311 , and elements, e.g., first to third weights w 1 to w 3 , of the weight vector provided by the weight generation circuit 120 . Accordingly, the scores may be changed according to values of the first to third weights w 1 to w 3 . In this embodiment, the number N corresponds to the number of requests stored in the request queue 110 .

In the present embodiment shown in FIG. 6 , the variable values yi 1 , yi 2 , and yi 3 (i being in a range of 1 to N) are multiplied with the first, second, and third weights w 1 , w 2 , and w 3 , respectively, and then the multiplied values are summated. The summated value is output as a score si.

In the present embodiment, since three elements affecting scheduling performance are considered in scheduling a processing order of the requests, three variable values are determined for each request. As the number of elements affecting the scheduling performance to be considered in the request scheduling increases or decreases, the number of variable values and the number of weights may increase or decrease accordingly.

FIG. 7 is a table for explaining an operation of the variable decision section 1311 of FIG. 6 according to an embodiment.

In the present embodiment, a value of a variable y 1 is one of 0, 1, and a previous value of the variable y 1 . In an embodiment, when the length WQL of a write queue is smaller than a lower limit LW and a corresponding request is a read request, the value of the variable y 1 is set to 1, and when the length WQL of the write queue is smaller than the lower limit LW and the corresponding request is a write request, the value of the variable y 1 is set to 0.

Furthermore, when the length WQL of the write queue is equal to or greater than an upper limit HW and the corresponding request is a read request, the value of the variable y 1 is set to 0, and when the length WQL of the write queue is equal to or greater than the upper limit HW and the corresponding request is a write request, the value of the variable y 1 is set to 1.

Furthermore, when the length WQL of the write queue is equal to or greater than the lower limit LW and smaller than the upper limit HW, the value of the variable y 1 is set to the previous value of the variable y 1 .

The aforementioned upper limit HW and lower limit LW are constant values arbitrarily selectable by those skilled in the art.

In the present embodiment, the value of the variable y 2 is one of 0 and a standby cycle number WC, the standby cycle number WC corresponding to a period for which a corresponding request has waited.

In the present embodiment, when a command for processing a corresponding request is an active command ACT or a column command COL, the value of the variable y 2 is set to the standby cycle number WC, and when the command is a precharge command PRE, the value of the variable y 2 is set to 0.

In the present embodiment, the value of the variable y 3 is 0, 1, or 2.

When a command for processing a corresponding request is the active command ACT or the precharge command PRE, the value of the variable y 3 is set to 0. When the command is the column command COL, the value of the variable y 3 is set to 2 when the corresponding request is a read request, and is set to 1 when the corresponding request is a write request.

The variable decision section 1311 of FIG. 6 performs the aforementioned operations to decide variable values corresponding to respective requests, and provides the variable values to the operating sections 1312 - 1 to 1312 -N.

As described above, since scores for respective requests are obtained by multiplying the variable values with the corresponding weights, the scores of the respective requests are changed by adjusting the weights. As a result, it is possible to substantially and variably apply a scheduling rule.

In an embodiment, when the variable values are determined as illustrated in FIG. 7 , if the third weight w 3 is set to 0, the scheduler 130 performs a scheduling operation according to the FCFS rule. If the second weight w 2 is set to 0, the scheduler 130 performs the scheduling operation according to the FR-FCFS rule.

As described above, the embodiments of the present disclosure provide a technical solution that optimizes the performance of a system by freely changing a scheduling rule using a weight vector.

While certain embodiments have been described above, it will be understood to those skilled in the art that the embodiments described are only examples. Accordingly, the memory controller described herein should not be limited based on the described embodiments. Rather, the memory controller described herein should only be limited in light of the claims that follow when read in conjunction with the above description and accompanying drawings.