Minimum maximum reconfiguration cost problem

Minimum maximum reconfiguration cost problem Raouf Senhadji-Navarro · Ignacio Garcia-Vargas Abstract This paper discusses the problem of minimizing the reconfiguration cost of some types of reconfigurable systems. A formal definition of the problem and a proof of its NP-completeness are provided. In addition, an Integer Linear Programming formulation is proposed. The proposed problem has been used for optimizing a design stage of Finite Virtual State Machines. Keywords Combinatorial optimization · Computational complexity · NP-completeness · Graph · Integer Linear Programming · Reconfigurable computing 1 Introduction The concept of reconfigurable computing goes back to 1960 when Gerald Estrin proposed a computer made of a standard processor and an array “reconfigurable” hardware [3]. However, the lack of adequate reprogrammable logic chips has delayed its devel-opment for more than three decades. Nowadays, the increasing performance (in terms of logic density, speed and power consumption) of the current programmable devices, like Field Programmable Gate Arrays (FPGAs), has allowed the development of a wide range of reconfigurable applications. The conventional computing architectures based on application specific integrated circuits and programmable general purpose processors suffer for the lack of flexibility of the dedicated hardware and limited performance of the software solutions, respec- tively. Reconfigurable computing is a promising approach to overcome the traditional trade-off between flexibility and performance [5,7]. However, there are some challenges that must be overcome to develop efficient applications for reconfigurable computing systems. One of these challenges is the lack of formal models and methodologies for design automation of dynamically reconfigurable systems [1,2]. One of the most critical problems that the designer faces is to minimize the reconfiguration cost with the goal to achieve an optimal performance [10]. In this paper, we have modeled the problem of minimizing the reconfiguration cost of some types of reconfigurable systems. We prove that this problem is NP-complete. We also propose an Integer Linear Programming (ILP) formulation for this problem. We have used the proposed problem for optimizing a design stage of Finite Virtual State Machines (FVSMs) [11]. The remainder of this letter is organized as follows. We provide a formal definition of the proposed problem in Sect. 2 and its NP-Completeness is proved in Sect. 3.The Integer Linear Programming (ILP) formulation is presented in Sect. 4. Experimental results of the ILP formulation is shown in Sect. 5. Finally, a practical application is shown in Sect. 6. 2 Problem statement A reconfigurable system is composed of a set of reconfigurable elements (REs) whose functional behavior can be changed in order to adapt the functionality of the system to different execution contexts. Let us call functionality the functional behavior that can be implemented in a single RE. Each execution context can be modeled as a set of functionalities. The functionalities implemented by all REs of the system for an execution context is called an instance of the reconfigurable system. Given a reconfigurable system with n REs, the set of instances related to the different execution contexts is called n-implementation. The changes of execution contexts can be modeled as an undirected graph, called execution context graph, where vertices represent execution contexts and edges connect execution contexts adjacent in time. We define an Homogeneous Reconfigurable System (HRS) as a reconfigurable system composed by a set of identical REs that verify the following three properties. First, all REs can implement the same functionalities. Second, the behavior of the HRS only depends on the functionalities of their REs but not on the particular assignment of functionalities to REs. Third, those REs that are not required by a particular execution context can implement any functionality without affecting the behavior of the HRS. In a HRS, when the execution context changes, those REs that already implement a functionality required by the new execution context do not need to be reconfigured. So, the reconfiguration cost is calculated as the number of REs that must be modified. The reconfiguration cost in the worst case determines the performance of the HRS; so, the maximum reconfiguration cost must be minimized. When an execution context requires less REs than available, the reconfiguration cost can be reduced if the unused REs are exploited for implementing some functionalities of the next execution context. A classical reconfigurable computing architecture composed by a general-purpose processor and a set of identical Coarse-Grained Reconfigurable Processing Elements (CGRPEs) connected by a bus is a HRS. The general-purpose processor also acts as reconfiguration controller [7]. FPGA devices (or different areas of a same FPGA device when dynamic partial reconfiguration [8] is used) are classical examples of CGRPE. Computer applications require the reconfiguration of CGRPEs for accelerating computationally intensive tasks. For this purpose, CGRPEs implement different functionalities such as digital filter banks, floating-point coprocessors, cryptographic coprocessors, etc. The functionalities required by the application in each period of time are the different execution contexts. In each execution context, the general-purpose processor reconfigures and uses the needed CGRPEs. The reconfiguration process requires to transfer the reconfiguration data of the modified CGRPEs. The reconfiguration latency (i.e., the transfer time of the reconfiguration data) directly depends on the number of modified CGRPEs. In reconfigurable real-time applications, the reduction of the reconfiguration latency is key to improve the response time of the system. In order to meet timing constraints, the reconfiguration latency in the worst case must be minimized. A HRS is modeled as a 3-tuple (F,G,R)where Fis a set of functionalities; G=(V,E), an execution context graph; and R={R1,R2,...,R|V|}, a collection of execution contexts where Rj⊆Ffor all Rj∈R. Each vertex vj∈Vrepresents the execution context Rj.LetS=(F,G,R)be a HRS. Let us define an n-implementation of Sas a collection of instances I={I1,I2,...,I|V|}where Ij⊆Fsuch that Rj⊆Ij and |Ij|=nfor all Ij∈I. Given an n-implementation I, let us define the reconfiguration cost between two instances Ii,Ij∈Ias δ(Ii,Ij)=n−|Ii∩Ij|. Note that δ(Ii,Ij) represents the number of functionalities in which Iidiffers from Ij(or Ijfrom Ii). Let us define the maximum reconfiguration cost of Ias (I)=max{vi,vj}∈Eδ(Ii,Ij). The Minimum Maximum Reconfiguration Cost (MMRC) problem consists in finding an n-implementation Iof a HRS with a minimum (I). 3 NP-completeness In order to proof the NP-completeness of the MMRC problem, we formulate the related decision problem as follows. Minimum Maximum Reconfiguration Cost Decision Problem (MMRCDP) INSTANCE: Reconfigurable system S=(F,G,R), positive integer n, positive integer K≤n. QUESTION: Is there an n-implementation of Swith a maximum reconfiguration cost less or equal to K? It is easy to see that MMRCDP ∈NP since a nondeterministic algorithm needs only to guess an n-implementation and check in polynomial time if its maximum reconfiguration cost is less or equal to K. We prove that MMRCDP ∈NP-complete by a reduction from 3SAT [4,9]. The 3SAT can be enunciated as follows. 3Satisfiability (3SAT) INSTANCE: Collection C={c1,c2,... cm}of clauses on a finite set Uof boolean variables such that |ci|=3for1≤i≤m. QUESTION: Is there a truth assignment for Uthat satisfies all clauses in C ? Given an arbitrary instance of 3SAT with a collection C={c1,c2,... cm}of clauses on a finite set Uof boolean variables, we shall construct a HRS S=(F,G,R) such that there exists a 4-implementation of Swith a maximum reconfiguration cost less or equal to K=2 if and only if Cis satisfiable. We construct the HRS by performing the following steps: 1. Given a collection of clauses C, let us define H(C)as a maximal subset of clauses of Cwhich verifies that no pair of clauses of H(C)are defined over exactly the same set of variables. Note that the clauses in H(C)can not share three variables. Let us define h:C→Z+in such a way that for any ck∈C,ch(ck)is the clause of H(C)defined over exactly the same variables that ck. 2. Let us define the set of functionalities F={X,Y,Z}∪|U| i=1{Ti,Fi}. The functionalities Tiand Fiare called truth functionalities of the variable uiand represent a truth-setting for uiwhere Tiand Fidenote the setting of true (T) and false (F) values, respectively. The functionalities X,Y, and Zwill be used to impose restrictions on the reconfiguration cost between instances. 3. Let us construct the collection of execution contexts Ras follows: (a) An execution context RV jis created for each cj∈C. Given a clause cj={l1,l2,l3}∈Cwhere liis a literal over uwi∈Ufor i=1,2,3, let us define RV j={X,f1,f2,f3}, where fi=Twiif li=uwi Fwiif li=¯uwi (1) Note that RV jcontains the truth functionalities that represent the truth-setting for the variables of cjthat satisfies the literals of cj. (b) Execution contexts RC1 j,RC2 j, and RC3 jare created for each cj∈H(C).Given a clause cj={l1,l2,l3}∈H(C), where liis a literal over uwi∈Ufor i=1,2,3, let us define RCk j={Tw1,Fw1,Tw2,Fw2,Tw3,Fw3}\{Twk,Fwk} for k=1,2,3. (c) An execution context RU j={X}is created for each cj∈H(C).Inany4implementation Iof Swith (I)≤2, the instance related to RU jwill contain the truth functionalities that represent a truth-setting for the variables of cjthat satisfies C. (d) Execution contexts RU j,kand RC j,kare created for each {cj,ck}∈H(C)×H(C) with j= ksuch that cjand ckshare two variables. Let upand uqbe the shared variables. Let us define RU j,k={Y,Z}and RC j,k={Tp,Fp,Tq,Fq}.Inany4implementation Iof Swith (I)≤2, the instance related to RU j,kwill contain the truth functionalities that represent a truth-setting for the shared variables that satisfies C. 4. Let us construct the execution context graph G=(V,E)as follows. For each created execution context, a vertex v∈Vis created. The vertices denoted by VV j, VC1 j,VC2 j,VC3 j,VU j,VU j,k, and VC j,krepresent the execution contexts RV j,RC1 j,RC2 j, RC3 j,RU j,RU j,k, and RC j,k, respectively. The set of edges Eis created as follows: (a) Edges {VC1 j,VU j},{VC2 j,VU j}and {VC3 j,VU j}are created for each cj∈H(C). In any 4-implementation Iof Swith (I)≤2, these edges allow to ensure that the instance related to RU jwill contain a truth functionality of each variable of cj. (b) An edge {VU j,VU k}is created for each {cj,ck}∈H(C)×H(C)with j= k such that cjand ckshare exactly one variable. In any 4-implementation Iof Swith (I)≤2, this edge allows to ensure that the instances related to RU j and RU kwill contain the same truth functionality of the shared variable. (c) Edges {VU j,VU j,k},{VU j,k,VU k}, and {VU j,k,VC j,k}are created for each RU j,k∈R. In any 4-implementation Iof Swith (I)≤2, these edges allow to ensure that the instances related to RU jand RU kwill contain the same truth functionalities of the two shared variables (note that RU j,kis created only if cjand ck share two variables). (d) For each cj∈Cwith h(cj)=k, an edge {VV j,VU k}is created. In any 4implementation Iof Swith (I)≤2, this edge allows to ensure that instance related to RU kwill contain at least one truth functionality that represent a truthsetting that satisfies cj. Figure 1shows an example of the proposed transformation. Figure 1ashowsthe given instance of 3SAT; Fig. 1b, the execution contexts (steps from 1 to 3 described above); and Fig. 1c, the execution context graph (step 4). It is easy to see how the construction can be accomplished in polynomial time. Supposing that mrepresents the number of clauses of C, the time complexity of the procedure is O(m2)due to the fact that it only needs to consider the different pairs of clauses of C. All that remains to be shown is that Cis satisfiable if and only if there exists a 4-implementation Iof Swith (I)≤2. Firstly, we will prove that there exists a 4-implementation Iof Swith (I)≤2 if Cis satisfiable. Given any satisfying truth assignment t:U→{T,F}, let us create the collection of instances Ifrom Ras follows. The instances denoted by IV j, IC1 j,IC2 j,IC3 j,IU j,IU j,k, and IC j,kare created from the execution contexts RV j,RC1 j, RC1 j,RC2 j,RC3 j,RU j,RU j,k, and RC j,k, respectively. Initially, these instances contain the same functionalities as the related execution contexts. Let us define b:U→Fas follows: b(ui)=Tiif t(ui)=T Fiotherwise (2) Let us add {b(up), b(uq), b(us)}⊂Fto each IU j∈Iwhere up,uq, and usare the variables of cj. Let us add {b(up), b(uq)}⊂Fto each IU j,k∈Iwhere upand uqare the variables shared between cjand ck. For all Ri∈R, the related instance Ii∈I verifies that Ri⊆Iiand |Ii|=4. Thus, Iis a 4-implementation. We must prove that δ(Ii,Ij)≤2 for each pair of instances Ii,Ij∈Isuch that Ii and Ijare related to adjacent execution contexts in G. Each edge of Gbelongs to one of the following categories: C={c1,c 2,c 3,c 4};U={u1,u 2,u 3,u 4,u 5,u 6} c1={u1,u 2,¯u3};c2={¯u1,u 2,u 3};c3={¯u1,¯u2,¯u4};c4={u4,u 5,u 6} (a) Step 1:H(C)={c1,c 3,c 4} Step 2:F={X, Y, Z, T1,F 1,T 2,F 2,T 3,F 3,T 4,F 4,T 5,F 5,T 6,F 6} Step 3:R=RV 1,R V 2,R V 3,R V 4,R C1 1,R C2 1,R C3 1,R C1 3,R C2 3,R C3 3,R C1 4,R C2 4,R C3 4,R U 1,R U 3,R U 4,R U 1,3,R U 1,3 Step 3a:RV 1={X, T1,T 2,F 3};RV 2={X, F1,T 2,T 3};RV 3={X, F1,F 2,F 4};RV 4={X, T4,T 5,T 6} Step 3b:RC1 1={T2,F 2,T 3,F 3};RC2 1={T1,F 1,T 3,F 3};RC3 1={T1,F 1,T 2,F 2} RC1 3={T2,F 2,T 4,F 4};RC2 3={T1,F 1,T 4,F 4};RC3 3={T1,F 1,T 2,F 2} RC1 4={T5,F 5,T 6,F 6};RC2 4={T4,F 4,T 6,F 6};RC3 4={T5,F 5,T 6,F 6} Step 3c:RU 1={X};RU 3={X};RU 4={X} Step 3d:RU 1,3={Y,Z};RC 1,3={T1,F 1,T 2,F 2} (b) VU 1 VC3 4 VU 3 VC3 1VU 4 VC3 3 VC2 3 VC2 1 VC2 4 VC1 4 VC1 3 VC1 1 VC 1,3VV 4 VV 1VV 2VV 3 VU 1,3 (c) t(u1)=t(u2)=t(u5)=t(u6)=T t(u3)=t(u4)=F (d) IU 1={X, T1,T 2,F 3};IU 3={X, T1,T 2,F 4} IU 4={X, F4,T 5,T 6};IU 1,3={Y, Z, T1,T 2} (e) Fig. 1 Example of transformation from 3SAT to MMRCDP: aclauses, bexecution contexts, cexecution context graph, da satisfying truth assignment for C,andethe equivalent 4-implementation (only the instances that differ to the related execution contexts are shown) –{VU j,VV j}∈E. By construction, IV jcontains Xand three truth functionalities each one representing a truth-setting that satisfies a different literal of cj. The instance IU jcontains Xand at least one truth functionality that represent a truth-setting that satisfies cj.AsCis satisfiable, at least one of the literal of cjis satisfiable; so, |IU j∩IV j|≥2 and thus δ(IU j,IV j)≤2. –{VU j,VCi j}∈Efor i=1,2,3. By construction, each ICi jcontains all possible truth functionalities of two variables of cj. The instance IU jcontains Xand the truth functionalities given by the function bfor the three variables of cj. So, |IU j∩ICi j|=2 and thus δ(IU j,ICi j)=2fori=1,2,3. –{VU j,VU k}∈E. This edge is created when cjand ckshare a unique variable. The instances IU jand IU konly share Xand the truth functionality given by the function bfor the shared variable. So, |IU j∩IU k|=2, and thus, δ(IU j,IU k)=2. –{VU j,VU j,k}∈E. This edge is created when cjand ckshare exactly two variables. The instances IU jand IU j,konly share the truth functionalities given by the function bfor the shared variables. So, |IU j∩IU j,k|=2 and thus, δ(IU j,IU j,k)=2. –{VC j,k,VU j,k}∈E. By construction, IC j,kcontains all possible truth functionalities of the two shared variables. The instance IU j,kcontains the truth functionalities given by the function bfor the two shared variables. So, |IC j,k∩IU j,k|=2 and thus δ(IC j,k,IU j,k)=2. We conclude that (I)=2. Conversely, we will prove that Cis satisfiable if there exists a 4-implementation Iof Swith (I)≤2. Previously, we prove some lemmas. Lemma 1 Let S =(F,G,R)be a HRS obtained from a 3SAT instance and let I be a 4-implementation of S with (I)≤2. Then, for all IU j∈I, there do not exist Tr,Fr∈Fsuch that {Tr,Fr}⊂IU j. Proof By contradiction, let us assume that there exit Tr,Fr∈Fsuch that {Tr,Fr}⊆ IU j; so, as X∈RU jand RU j⊆IU j,{X,Tr,Fr}⊆IU j. By construction, there exist RCi j∈Rsuch that {X,Tr,Fr}∩RCi j=∅and |RCi j|=4. Therefore, {X,Tr,Fr}∩ICr j=∅and so IU j∩ICr j⊆IU j\{X,Fr,Tr}. Then |IU j∩ICi j|≤ |IU j\{X,Fr,Tr}| = 1 and therefore δ(IU j,ICi j)>2 which implies a contradiction.  Lemma 2 Let S =(F,G,R)be a HRS obtained from a 3SAT instance with a collection C of clauses on a finite set U of boolean variables and let I be a 4implementation of S with (I)≤2.Ifc j∈H(C)is defined over u p,uq,us∈U then IU j={X,fp,fq,fs}where fi∈{Ti,Fi}. Proof Since (I)≤2, δ(IU j,ICi j)≤2fori=1,2,3; therefore, |IU j∩ICi j|≥2for i=1,2,3. By construction, there exists a RCi j∈Rsuch that RCi j={Tp,Fp,Tr,Fr} where r=qor r=sand so, ICi j={Tp,Fp,Tr,Fr}. By contradiction, let us assume that {Tp,Fp}∩IU j=∅;so,IU j∩ICi j⊆ICi j\{Tp,Fp}={Tr,Fr}.As|IU j∩ICi j|≥2, {Tr,Fr}⊆IU jwhich implies a contradiction by Lemma 1. So, fr∈IU jfor all variables ur∈cjwhere fr={Tr,Fr}. Since RU j={X}by construction, IU j={X,fp,fq,fs}.  Lemma 3 Let S =(F,G,R)be a HRS obtained from a 3SAT instance and let I be a 4-implementation of S with (I)≤2. For each pair IU j,IU k∈I with j = k, there do not exist Tr,Fr∈Fsuch that {Tr,Fr}⊂IU j∪IU k. Proof Let cjand ckbe the clauses of a 3SAT instance related to IU jand IU k, respectively. The proof is divided into the following cases: –cjand ckdo not share variables. Let upbe a variable of cj. By Lemma 1, {Tp,Fp} ⊂ IU j.Ascjand ckdo not share variables, ckis not defined over up. So, it is follows from Lemma 2that {Tp,Fp}∩IU k=∅. So, {Tp,Fp} ⊂ IU j∪IU kfor any non-shared variable up. –cjand ckshare a unique variable up.Letup,uq, and urbe the variables of cjand let up,us, and utbe the variables of ckwhere s= q,rand t= q,r. By contradiction, let us assume that Tp∈IU jand Fp∈IU k. By Lemma 2,IU j={X,Tp,fq,fs} and IU k={X,Fp,fr,ft}where fi∈{Ti,Fi}, then IU j∩IU k={X}. Since |IU j∩IU k|<2, we have δ(IU j,IU k)>2 which implies a contradiction because (I)≤2. So, {Tp,Fp} ⊂ IU j∪IU k. –cjand ckshare two variables upand uq. Firstly, we prove that X/∈IU j,k.By construction, RU j,k={Y,Z},{X,Y,Z}∩RC j,k=∅, and |RC j,k|=4. Therefore, {Y,Z}⊂IU j,kand {X,Y,Z}∩IC j,k=∅;so,IC j,k∩IU j,k⊆IU j,k\{Y,Z}. Since (I)≤2, we have 2 =|IU j,k\{Y,Z}| ≥ |IC j,k∩IU j,k|≥2 which implies IC j,k∩IU j,k=IU j,k\{Y,Z}. Then X/∈IU j,kbecause X/∈IC j,k. By Lemma 2,IU j={X,fp,fq,fr}and IU k={X,f p,f q,fs}where fi,f i∈ {Ti,Fi}and r= s.As{Y,Z}∩IU j=∅,IU j∩IU j,k⊆IU j,k\{Y,Z}. Similarly, as {Y,Z}∩IU k=∅,IU k∩IU j,k⊆IU j,k\{Y,Z}. Since (I)≤2, |IU j∩IU j,k|≥2 and |IU j,k∩IU k|≥2 which implies that IU j∩IU j,k=IU j,k∩IU k=IU j,k\{Y,Z}. Therefore, if X/∈IU j,kthen IU j,k\{Y,Z}⊂IU j∩IU k;so,|IU j∩IU k|>|IU j,k\{Y,Z}| = 2 which implies that {fp,fq}={f p,f q}. So, {Tp,Fp} ⊂ IU j∪IU kand {Tq,Fq} ⊂ IU j∪IU k. Note that the case of three shared variables is not considered because, by construction, RU j(and so IU j) is created only if cj∈H. The above lemmas allow us to define a truth assignment function t:U→{T,F} as follows: t(uj)=Tif Tj∈IU kfor all IU k∈Isuch that uj∈ck Fif Fj∈IU kfor all IU k∈Isuch that uj∈ck (3) All that remains to be shown is that tsatisfies C. By construction, each truth functionality of RV jrepresents a truth-setting that satisfies cjand, since |RV j|=4, IV j=RV j. For all cj,wehaveδ(IU h(cj),IV j)≤2, then we have |IU h(cj)∩IV j|≥2, hence there exists at least a fp∈{Tp,Fp}⊂Fsuch that fp∈IU h(cj)∩IV j. Then f p ∈ I j V which implies that the truth value t (u p) satisfies c j . So, t satisfies C. It is proved that C is satisfiable if and only if there exists a 4-implementation I of S with (I ) ≤ 2. In the example of transformation, Fig. 1d, and e show a satisfying truth assignment for C and the equivalent 4-implementation I , respectively. We conclude that MMRC problem is NP-complete. 4 Integer Linear Programming formulation Let S = (F, G, R) be a HRS where F ={f1, f2,..., f p} is a set of functionalities; G = (V, E), an execution context graph; and R ={R1, R2,..., R|V |}, a collection of execution contexts. Let I ={I1, I2,..., I|V |} be a n-implementation of S. We define the sets of binary variables xi, j ∈{0, 1} and yi, j,k ∈{0, 1} as follows: xi,j=1iffi∈Ij, 0 otherwise.i=1,...,p;j=1,...,|V|(4) yi,j,k=1iffi∈Ij∩Ik, 0 otherwise. i=1,...,p;j,k=1,...,|V|(5) Then, the MMRC problem can be formulated in the following way: minimize m(6) s.t. xi,j=1∀i,j|fi∈Rj(7) p  i=1 xi,j=nj=1,...,|V|(8) 2yi,j,k≤xi,j+xi,k≤1+yi,j,ki=1,...,p;j,k=1,...,|V|(9) m≥n− p  i=1 yi,j,k∀j,k|{vj,v k}∈E(10) The constraint (7) and (8) ensure that the Iis a n-implementation of S. The constraint (9) ensures that the variable yis consistent with the definition (5). The reconfiguration cost δ(Ij,Ik)can be calculated as n−p i=1yi,j,k. So, the constraint (10) ensures that mis an upper bound for the reconfiguration cost between any pair of instances corresponding to adjacent execution contexts. So, the minimum maximum reconfiguration cost of Ican be obtained by minimizing m,asshownin(6). 5 Experimental results The proposed ILP formulation has been solved using the solver Gurobi 4.6 [6]. The experiments have been executed in an Intel Xeon X5660 (4 cores) at 2.80 GHz with 16 GB of RAM running Linux 64 bits (Red Hat Enterprise Linux 6). The test data set consists on 50 randomly generated MMRC instances. The experiments have been executed with a time limit of 7200 s. Table 1summarizes the obtained results. We refer to the problem instances solved to optimality as “solved instances”; on the other hand, we refer to the instances that could not be solved within the imposed time limit as “non-solved instance”. For each problem instance, the table shows the size of the n-implementation (n), the number of functionalities (|F|), the number of edges of the execution context graph (|E|), the number of vertices of the execution context graph (|V|), the mean of the cardinality of the execution contexts (“C-mean”), the standard deviation of the cardinality of the execution contexts (“C-std”), the number of the average final percentage optimality gap (“Gap”), and the amount of time in seconds spent by solved instances (“Time”). The rows of the table are sorted in increasing order of |E|. As can be observed, there is a trend of increasing the time with the increasing of the number of edges. The ILP formulation found an optimal solution in the 76 % of the cases (38 instances). The average time for these cases was 605 s.