In this paper we propose a quantum-based solution to the problem of counting the cache hits, an important issue when analyzing real-time embedded applications. This field has already seen the development of “quantum-inspired” classical algorithms which are competitive with the state of the art. We designed a polynomial-time dynamic programming algorithm for computing the lowest number of cache hits realized by a deterministic sequence of memory accesses, in the presence of preemptions. Our contribution consists in porting that algorithm to the quantum framework, improving the complexity of the algorithm from ( 3) to ( 2 + ).
precision and eficiency) with state-of-the-art approaches. Furthermore, the problems arising in
WCET evaluation cover a wide-range of complexity classes, from undecidability in the general
case down to -hardness and polynomial-time solvability in some restricted cases [
In this direction, in this paper, we tackle only a restricted setup with the most simple program model: the evaluation of the worst-case number of cache misses of programs performing deterministic sequences of memory accesses, in case of arbitrary preemptions. A preemption is the act of interrupting one task to allow the execution of another task on a machine. There is indeed a strong connection between the number of cache misses done by program and its execution time, as uncached memory accesses are highly time-consuming on modern processors. In other words, we consider a single path program (linear sequences of instructions) and the complexity of the model comes from the arbitrary-placed interruptions, due to other programs running on the same system, which create interferences in the cache memory. For our model, we consider preemption points and they can occur at any time in the sequence, making the cache behaviour non-predictable.
In this paper, we propose a dynamic programming classical algorithm, with polynomialtime complexity, to compute the minimal number of cache hits in the sequence of memory accesses, as a proxy measure of the WCET for the considered program. Although our model is standard the WCET community, we consider it, as well as the classical polynomial-time algorithm solving it, as the basis to derive a lower complexity (still polynomial-time) hybrid quantum-classical algorithm. In doing so, we demonstrate a first benefit of explicitly using the quantum computing paradigm to the field of WCET calculations, albeit in simplified setting.
Dynamic programming is an algorithmic technique to solve a problem consisting in
finding one optimal solution by solving a family of easier sub-problems. We designed a dynamic
programming algorithm to compute the minimal number of cache hits while executing a
deterministic sequence with preemptions. This technique to solve WCETs is consistent with
others classical solutions in the literature [
This paper is organized as follows: Section II provides a brief overview about cache memories and preemptions. Then, Section III places the paper in the context of the state-of-the-art, and presents our program model. In Section IV we propose a dynamic programming algorithm for evaluating WCET. Section V then contains the quantum version of that algorithm. Lastly, in Section VI we compare the complexity of the two algorithms and in Section VII we provide some perspectives for future works.
Cache memories impact the variability of execution times, since the access time between an element stored in the cache memories and an element which is not, can be up to two orders of magnitude. As cache memories are limited in size, the hardware uses the history of previous accesses in the cache to decide which currently stored elements should be replaced when a new one must be stored in the cache memory. For instance, LRU (Least Recently Used) cache policy privileges, as replacement candidate, the oldest used line of memory in a set. In the general case, when an access to an element in memory performed by a program is already in the cache, we call it a “cache hit”, otherwise we say that a “cache miss” occurred. Cache misses impact on the execution time because the missing element needs to be fetched from the main memory, which induces additional delays.
The advantage of preemptions is the possibility to make optimal utilization of the computing
power. In particular, in fully preemptive systems, as the one we present in this paper, the
running task can be interrupted at any time by another task with higher priority and be resumed
to continue when all higher priority tasks have completed [
We consider programs that perform deterministic accesses to the memory, that can be
interrupted at any time, using the count of cache misses as a first proxy evaluation of the WCET
(or as the literature calls it, the Cache memory preemption delay). A “dual” approach has
already been explored in the literature, with papers about applying static analysis techniques
to quantum algorithms to evaluate their performance and formally analyze their functional
properties [
As model case, we take into consideration the problem of evaluating the WCET of a deterministic sequence of memory accesses, in case of preemptions. We denote the sequence of memory accesses as 0, 1, … , −1 and we are supposed to know if each of them is a cache miss or a cache hit in an execution without preemptions (this is done in linear time as a pre1Whilst it is possible that, for a given set of tasks, preemption would preserve some cache lines, the situation when one wants to calculate WCET of a task in the general case requires the hypothesis that no useful cache line would be retained by a preemption. processing step). We denote [ ] the -th access of the sequence and 1 if cache miss 0 if cache hit. is the set of possible contents of those memory accesses 0, … , −1. The number of preemptions interrupting the program is a fixed number . Preemption can happen at any time, this leads to non-predictability of the model. We suppose also that when a preemption occurs, all the content of the cache is flushed from it.
We designed a dynamic programming algorithm to compute the minimal number of cache hits while executing a deterministic sequence with preemptions. The minimal number of cache hits corresponds to the maximal number of cache misses.
First at all, we scan the sequence of memory accesses, as it would be without any point of preemption, and we store the information of being a cache hit or miss into an array : if the considered access is cache miss [ ] = 1, [ ] = 0 otherwise. We compute also the [ ] > , the table of indexes of the first access to the object , after the -th access, into the sequence of memory access. If there is no other access to , we write ∞.
We suppose to know the solution of the problem for all the sequence +1, ⋯ , −1 and the number of preemptions ′, where 0 < ′ < . In other words, it is known: • ( + 1, ,
′): the smallest number of cache hits for the object and ′ preemptions; • ( + 1, ′) > + 1 : index of the next preemption in this solution.
Algorithm 1 describes how to determine (, , ′) and (, ′) from the previous data, in case of cache miss (i.e if [ ] = 1)
Now, Algorithm 2 describes how to determine (, , ′) and (, ′) from the previous data, in case of cache hit (i.e if [ ] = 0).
After performing the algorithm we obtain the smallest number of cache hits for each object , when preemptions occur, in symbols (0, , ). ∑ (0, , ) is the solution for the problem of computing the smallest number of cache hits for the sequence of memory accesses.
As example, we take into consideration a cache of size 2, with = 2 (i.e two preemptions occur). The set of possible contents of the cache is = { 0, 1, 2} = {, , }. The sequence of memory accesses is 0 1 2 3 4 = . The first two accesses and the last one are cache misses, while the third and fourth accesses are cache hits. It is simple to see that the worst scenario is when the two points of preemption happen immediately before the two cache hits, because in this case the content of the cache is flushed and and has to be restored into the cache when re-called lately. In this scenario the algorithm returns 0 = 0 as minimal number
Result: The choice between A and B, for a fixed ′, is the one that minimize ∑ ′ (, , ′) index in the sequence 0 < ′ < number of preemptions; case A no preemption for all in P for all ′ if = then (, , ′) = 1 + ( + 1, , ′) (, , ′) = ( + 1, , ′) (, ′) = ( + 1, ′) end case B preemption for all in P for all ′ if [ [ ]] = 0 and ( + 1, ′ − 1) > [ ] then = 1 = (, , ′) = ( + 1, , ′ − 1) − 1 else = 2 = (, , ′) = ( + 1, , ′ − 1) (, ′) = of cache hits, meaning that all the accesses of the sequence are cache misses. If a preemption happens before a cache miss it does not impact in the performances.
After the algorithm performs the first scan of the sequence of memory accesses we have = 11001. The table is: ∞ ∞ ∞ ∞ ∞ ∞
We give below the details only of the two first iterations, being the most representative. In order to obtain the final result, it sufices to execute again the algorithm, until the sequence of accesses is completed. index in the sequence ∑ ′ (,
, ′) case A no preemption 0 <
′ < number of preemptions; for all in P for all ′ if = = (, , ′) = 1 + ( + 1, , ′) = (, , ′) = ( + 1, , ′)
′) = ( + 1, ′) case B preemption for all in P
for all ′
Result: The choice between A and B, for a fixed ′, is the one that minimize = 1 = (, , ′) = ( + 1, ,
′ − 1) − 1 if ( [ [ ]] = 0 and ( + 1, ′ − 1) > [ ]and ≠ ) (,
′) = (, , ′) = ( + 1, , ′ − 1) = 2 = (, , ′) = ( + 1, , ′ − 1) else (,
else • a4=C • a3=B t \k’ 0 0 (A) (B) 2 (C) k’ 0 0 0 1 0 0 0 2 0 0 0 0 ∞ 1 4 2 4 ( = 4, , ′) = 1 ( = 4, ′) = Without preemption:
Here, note that "-" is equivalent to 0 for our purpose. Final table: t \k’ 0 0 0 (A) ′) = 1 1 (B) 2 0 (C) = ( = 3, , t \k’ 0 0 (A) = ( = 3, , ′) = 1 (B) 2 (C)
In this section we present the “quantum version” of the previous algorithm. We suppose to already know the behaviour of the cache in case of program’s execution without preemptions (i.e the array ) and the table , both deterministic. While searching for the minimal number of cache miss, in the classic algorithm, we perform three nested loops: • over the sequence memory accesses ( iterations) • over all the possible objects that can be into the cache ( iterations) • over all the ′ with 0 < ′ < ( iterations) To compute the solution (i.e. the number of cache hits corresponding to preemption and the last memory access) the algorithm needs all the number of cache hits corresponding to ′ with 0 < ′ < . We reformulated the dynamic programming classic algorithm into an hybrid quantum-classical algorithm in which the third loop (the one over the number of preemptions) is suitable to be executed on a quantum computer.
In particular, we will give below the details of the first case (when cache miss happens) of our quantum algorithm, being the second case (when cache hit happens) similar. We build a superposed state represented as | ′, ⟩ where ′ is the number of considered preemptions and the corresponding number of cache hits. In other words, for each number of preemptions ′, it is known the minimum possible number of cache hits while performing the sequence of memory accesses. Considering, for simplicity of notation, the case of our example, can be either 0 or 1 so we build the superposed state ∑ ′ | ′, 0⟩ + | ′, 1⟩, for each ∈ . We recall that is the set of possible contents of the memory slots. Since each block (a ′ iteration) is independent from the others, we can consider them one by one. Therefore we perform a projection on the ′, so we represent the qubits as = |0⟩ + |1⟩, with , ∈ {0, 1} and + = 1. If the considered memory access is a cache miss (i.e [ ] = 1), a preemption may (case B) or may not (case A) occur before accessing it. When a preemption does not occur (case A), we simply apply the identity matrix to the superposed state. When a preemption occurs (case B) the situation is more complex and we need to define two diferent operators, and . Those operators are made of the sub-operators 02, 2, 2, applied to the single blocks.
0 0 1 0 0 1
02 = [0 0] 2 = [0 1] 2 = [
In order to maintain reversibility we need to compute all the more outputs of the algorithm respect to the classical algorithm and keep track of them. Starting from the superposed state, we will apply the identity operator to obtain , we apply to obtain 1 and to obtain 2
The first oracle 1 has to choose between 1 and 2, always block by block: where: 1 ∶ | 1, 2, ⋯ , , +1, +2, ⋯ , 2 , , ⟩ ⟶ | 1 ⊕ +1( ⊕ 1), 2 ⊕ +2( ⊕ 1), ⋯ , ⊕ 2 ( ⊕ 1), 1(1 ⊕ ) ⊕ +1 ,
2(1 ⊕ ) ⊕ +2 , ⋯ , (1 ⊕ ) ⊕ 2 , ⊕ , ⟩ = |0⟩ + |1⟩ and a boolean. We have also:
= 0 |∞⟩ + 1 |1⟩ + ⋯ + | ⟩ .
Now, calling the result of the choice between 1 and 2, we need to choose between and , picking the option that minimizes the number of cache hits. The oracle 2 is an oracle choosing between A and B.
where and is a boolean. Then, we have: 2 ∶ | 1, 2, ⋯ , , +1, +2, ⋯ , 2 , ⟩ ⟶ | 1 ⊕ +1( ⊕ 1), 2 ⊕ +2( ⊕ 1), ⋯ ,
⊕ 2 ( ⊕ 1), 1(1 ⊕ ) ⊕ +1 ,
2(1 ⊕ ) ⊕ +2 , ⋯ , (1 ⊕ ) ⊕ 2 , ⊕ ⟩
with condition true if: 1 + ⋯ + < +1 + ⋯ + 2
where "+" is the usual sum over qubits, executable by a Quantum Adder [
In Fig. 1 it is represented the quantum algorithm’s flow.
In this section we give a glimpse of the functioning of our algorithm though a simple example. We suppose to have a sequence of memory accesses of length = 3: . We have = {, }, then = 2. The choice of this simplified example comes from the fact that the number of qubits needed to perform the quantum algorithm increases quickly with the number of memory accesses. That being said, with such a low and consequently low , it is not possible to appreciate the advantage of the quantum algorithm in terms of complexity. We suppose that the cache has one line. This means that in the best scenario the number of cache hits is 1, while in the worst scenario, if a preemption occurs before the third access, the number of cache hits is 0. Finally, we suppose = 1. We can build the deterministic tables and : i \t 0 = 1 2
We build the superposition representing all possible number of cache hits and all possible number of preemption | ′, ⟩ with ′ = {0, 1} and = {0, 1} for one object in :
0 |0, 0⟩ + 1 |0, 1⟩ + 2 |1, 0⟩ + 3 |1, 1⟩ .
In this superposition we have that either = 0 either +1 = 0, with even. Then, and
In order to build a quantum circuit, we can express the matrices and as boolean expression on the qubits , :
Now, the oracle 2 has to choose between the case and the case , where is the result of the first oracle 1.
case A 0 |0, 0⟩ + 1 |0, 1⟩ + 2 |1, 0⟩ + 3 |1, 1⟩ case B 0′ |0, 0⟩ + 1′ |0, 1⟩ + 2′ |1, 0⟩ + 3′ |1, 1⟩
The answer of the 2 oracle is if 1 + 3 < 1′ + 3′, otherwise.
After applying the previous quantum-algorithm, for each block (i.e. for each ′), we have a superposed state ∑ ′ | ′, 0⟩ where 0 is the minimal number of cache hits if ′ preemptions occur and 0 < ′ < . From this superposed state we need to extrapolate the 0 corresponding to preemption. The idea is to use a Grover-style searching algorithm over the superposed state to isolate the solution (i.e 0 for ′ = ). In particular, we expect to have as input for the oracle the superposition: 0 |0, 0⟩ + 0 |0, 1⟩ + ⋯ + 0 |0, 0⟩ + ⋯ +0 | ′, − 1⟩ + 0 | ′, 0⟩ + 0 | ′, 1⟩ + ⋯ + ′ | ′, 0⟩ + ⋯ + 0 | ′, − 1⟩ + ⋯ +0 | , 0⟩ + 0 | , 1⟩ + ⋯ + + | , 0⟩ + ⋯ + 0 | , − 1⟩ coeficients the result is |,
should apply again the algorithm.
We suppose then to build an oracle that selects the qubits with "index" corresponding to . We suppose that implements, in a Grover-style, an Amplitude Amplifier that amplifies and leaves to zero the zeros coeficients, see Fig.4. If at the end of the algorithm ⟩ where
≠ , it means that the searching algorithm didn’t worked and we
In Fig. 5 we can see that the oracle takes as input superposed state of the results of the circuit access in case of preemptions. for each ′ in Fig. 1 and returns the minimal number of cache hits in the sequence of memory
the number of cache hits when to In order to compute the final solution, at each iteration of the first loop, we create a table of dimensions with 0 <
× , containing the number of the cache hits, for each item in and each ′, ′ ≤ . Each iteration of the second loop is independent from the others, meaning that we can compute any row of the next table independently from the others rows. Then, the complexity of "updating" a row (most inner loop) is ( ). Therefore the dynamic programming classical algorithm has a complexity of ( × × ) (see Fig 6a). In the context of porting classical applications to quantum computing, we designed a “hybrid quantum-classical version” of the previous algorithm, whose output is the number of cache hits corresponding preemption. We consider a row in one table as a superposition of states representing all where < the numbers of preemptions ′ and all the possible values of the number of cache hits. In this way, the complexity of the act of "updating" a row becomes (1) (see Fig. 6b). Therefore the complexity of the resulting quantum algorithm becomes ( × ). As a drawback, we need to post-process the result we obtained at the previous step: superpositions of dimension × , is the maximum number of cache hits. However, we only need the value of preemptions occur (i.e. only one value per row in the last set of rows). Therefore, for each row, we can use Grover’s algorithm to extract the value of interest in the associated superposition. This means that this post-processing has complexity √ decreased to ( 2 + ) compared to ( 3) for the classical algorithm.
2 = . Hence, the complexity of the whole quantum algorithm is
In this paper, as a first step to deal with WCET-related problems by means of quantum-classic hybrid algorithms, we worked on a highly simplified program model since we just considered single-path programs, yet in the presence of arbitrary preemptions. A natural perspective would be to attempt to generalize this approach to more complex program models allowing for some non-determinism in the control-flow. However, such a generalisation would require a careful control of the size of the quantum state representing the cache hit counters array in order to avoid a complexity blow up at the post-processing amplification step.
Also, in this paper, we have ported a polynomial-time dynamic programming algorithm to the quantum framework. In essence, most such algorithms follow the same regular pattern of several nested loops updating an array data structure with the final result obtained in only one of the entries of the last array. As such, the approach in this paper, consists in turning the inner loop of our algorithm in a “quantum parallel for” associated to a Grover-style amplification on the single result of interest. As a consequence, the approach in this paper may potentially be generalized to other (exponential-time or polynomial-time) dynamic programming algorithms in order to derive (polynomial-only) quantum speedups.