Franc ¸ois Guay
email: francois.guay.2@ulaval.ca

Philippe Cardou
email: pcardou@gmc.ulaval.ca

Ana Lucia Cruz Ruiz
email: ana-lucia.cruz-ruiz@eleves.ec-nantes.fr

Stéphane Caro
email: stephane.caro@irccyn.ec-nantes.fr

Measuring How Well a Structure Supports Varying External Wrenches

Keywords: Kinematic index, dexterity, manipulability, kinematic sensitivity, grasping, stability, cable-driven robot, wire-driven robot, Gough-Stewart platform

An index is introduced, the minimum degree of constraint satisfaction, which quantifies the robustness of the equilibrium of an object with a single scalar. This index is defined under the assumptions that the object is supported by forces of known lines of action and bounded amplitudes, and that the external perturbation forces and moments vary within a known set of possibilities. A method is proposed to compute the minimum degree of constraint satisfaction by resorting to the quickhull algorithm. The method is then applied to two examples chosen for their simplicity and diversity, as evidence of the broad spectrum of applications that can benefit from the index. The first example tackles the issue of fastening a workpiece, and the second, the workspace of a cable-driven parallel robot. From these numerical experiments, the minimum degree of constraint satisfaction proves useful in grasping, cable-driven parallel robots, Gough-Stewart platforms and other applications.

Introduction

In mechanism and structure design, the definition of a sound and meaningful performance index that would apply to a wide variety of situations would be of tremendous help. Such a concept would allow the automation of a part of the design process, enabling a systematic scan of the possible solutions. With this objective in mind, several researchers have proposed indices-see the excellent review by Merlet [START_REF] Merlet | Jacobian, manipulability, condition number, and accuracy of parallel robots[END_REF].

Among the most popular indices, we find the manipulability, originally proposed by Yoshikawa [9]. This index represents the volume of the ellipsoid obtained by mapping the unit-sphere through the Jacobian matrix of a robotic manipulator. Hence, the manipulability represents a geometric average of the kinematic sensitivity of the robot. If the kinematic sensitivity is null in one direction of motion, then the ellipsoid becomes flat, and its volume zero. This implies that the robot cannot support an object in this direction of motion. The drawback of this approach is that a manipulator may be very close to instability while retaining a large manipulability if its associated ellipsoid is thin along one dimension and thick along the others.

Another widely used index is the dexterity, as defined by Salisbury and Craig [START_REF] Salisbury | Articulated hands: Force control and kinematic issues[END_REF]. Geometrically, this index measures the distortion of the ellipsoid associated with the Jacobian matrix of a manipulator by taking the ratio of its largest semi-axis to its smallest. The problem with this approach is that it does not account for the size of the ellipsoid. Thus, the concept of capacity is occluded by that of evenness.

Another drawback of dexterity is that it is ill-defined when the Jacobian matrix is not dimensionally-homogeneous, a problem that has been noted by several authors. Workarounds have been proposed [START_REF] Angeles | The design of isotropic manipulator architectures in the presence of redundancies[END_REF][START_REF] Tandirci | Characteristic point and the characteristic length of robotic manipulators[END_REF][START_REF] Khan | The kinetostatic optimization of robotic manipulators: The inverse and the direct problems[END_REF], but all of them entail some arbitrariness, and, perhaps for this reason, have not generally received acceptance from the robotics community. In this paper, we propose a normalisation that is no less arbitrary than those proposed previously, but that has the merit of being simple and straightforward. In any case, as was pointed out by Park and Kim [START_REF] Park | Kinematic manipulability of closed chains[END_REF], "arbitrariness is an unavoidable consequence of the geometry of SE [START_REF] Gouttefarde | Interval-analysis-based determination of the wrenchfeasible workspace of parallel cable-driven robots[END_REF]."

Most importantly, the dexterity and the manipulability do not account for the varying force and moment capabilities of the actuators, nor for the external forces and moments that the object has to support. In general, the designer can and must evaluate these constraints during the design process.

In this paper, we take into account the actuator capacities, as well as the set of expected external forces and moments, and incorporate them into the definition of our performance index. These assumptions are formally explained in section 2. In section 3, we define the proposed index, various examples of increasing complexities are presented in sections 4 and 5, and a summary is given in section 6.

Mechanical Model of a Structure Supporting an Object

We start from a rigid body in space, whose free-body diagram is shown in Fig. 1. This object is subjected to a system of external forces (e.g., gravity or air friction), which we represent by their resulting force at E and moment, f e and n e . The location of point E generally depends on the application considered, and experience shows that the choice of E is usually straightforward. The external wrench is to be balanced by the forces f i , i = 1, . . . , m, applied by the supporting structure on the object at the corresponding points C i , i = 1, . . . , m. We assume that the directions of these forces are known and given by unit vectors u i , i = 1, . . . , m. When the supporting forces come from physical contacts between the object and the structure, this implies the absence of friction, and vectors u i pointing towards the object. When the object is suspended by a cable, then u i points in the direction opposite to the object.

From Fig. 1, the equations of static equilibrium are

Wf + w e = 0 6 , (1)
where

E n e f e C 1 f 1 • • • C i f i • • • C m f m r i
Fig. 1 Free-body diagram of an object in space

W ≡ u 1 • • • u m 1 r r 1 × u 1 • • • 1 r r m × u m , f ≡    f 1 . . . f m    , w e ≡ f e (1/r)n e ,
f i is the amplitude of the i th force, 0 3 is the three-dimensional zero vector, and

r 2 = (1/m) ∑ m i=1 r i 2
2 is used to render the equations dimensionally homogeneous. One may see a problem occuring when r = 0 m, that is when all points C i , i = 1, . . . , m, are located at E. In such a case, all forces are concurrent at E, so that the rigid body becomes a particle, and a sum of moments is no longer needed.

We assume that the external wrenches w e that could be applied on the object by its environment form a known polytope, the set of task wrenches T , or

T = {w e ∈ R 6 : w e = n ∑ j=1 α j w e, j , n ∑ j=1 α j = 1, α j ≥ 0, j = 1, . . . , n}. (2)
The designer generally has an approximate idea of the wrenches that will be applied by the environment, which he or she can approximate with the polytope T . We also work under the assumption that the structure can only withstand forces f i within given ranges, e.g., the limited resistance of the contact surface, the inability of cables to push, or the limited capacities of actuators. These ranges of forces form the set F of feasible forces, a box (a.k.a. orthotope) in m-dimensional space, namely,

F = {f ∈ R m : f ≤ f ≤ f}, (3)
where f and f are the lower and upper bounds on the force array f.

A Measure of the Structure Capacity

For the object to remain in equilibrium, it must not only satisfy the static equilibrium equations ( 1), but also have supporting forces f within the allowed ranges for any of the task wrenches w e . These conditions can be symbolically expressed as

∀w ∈ T , ∃f ∈ F : w e = -Wf. (4)
This condition can also be understood graphically. The two sets F and T are defined in different spaces, which are connected through the linear relationship of the equation of static equilibrium. In Fig. 2, the box F of allowed forces is mapped onto the wrench space through the linear transformation w = -Wf. The resulting set is labelled W , and is a special type of polytope called a zonotope [START_REF] Bouchard | On the ability of a cable-driven robot to generate a prescribed set of wrenches[END_REF]. From the feasibility condition (4), we conclude that the system is in equilibrium if and only if Our measure should be a function indicating how far set T is from being partly outside of W . It should be positive when the structure can support the task wrenches, and negative otherwise. It should be as smooth as possible to ease its optimisation.

T ⊆ W . (5)
As an indicator of the degree of inclusion of T within W , we propose an index that we call the minimum degree of constraint satisfaction, and which we define as s = min j=1,...,n ( min l=1,...,p s j,l ),

where the degree of constraint satisfaction s j,l is the signed distance from vertex w e, j of T to the l th face of W . We take s j,l to be positive when the constraint is satisfied, and negative otherwise. With this definition, the minimum degree of constraint satisfaction s remains negative as long as at least one of the vertices of T remains outside of W ; becomes zero whenever T ⊆ W and a vertex of T lies on the boundary of W ; and is positive when T is in the interior of W . The computation of the proposed indicator function is performed in five steps:

(i) Compute the vertices of F , f k , k = 1, . . . , q, q = 2 m , through the formula f k = (1 m×m -diag(β k ))f + diag(β k )f
, where β k is the array of m bits giving the binary representation of k.

(ii) Map the vertices onto the wrench space as w k = -Wf k , k = 1, . . . , q.

(iii) Compute the convex hull of W from w k , k = 1, . . . , q. Fortunately, several routines are readily-available for this purpose. Here, we use the quickhull algorithm implemented in the qhull package for Matlab. This returns the polytope W in the form W = {w ∈ R 6 : a T l w ≤ b l , l = 1, . . . , p}.

(iv) Compute the degree of constraint satisfaction s j,l associated with the j th vertex of T , w e, j , and the l th face of W , a T l w = b l . This is done by projecting a vector from w e, j to the hyperplane of the l th face of W onto its normal a l / a l 2 , which gives s j,l = (b l -w T e, j a l )/ a l 2 . (v) Compute the closeness of T to being completely included in W as the minimum s of the degrees of constraint satisfaction, as per eq. ( 6).

Example: Holding a Workpiece

In this example, we consider the problem of clamping a metal block having dimensions 150 mm × 100 mm for a polishing run. The polisher consists of a rotating circular brush following a strip pattern, applying a moment of 500 and a force of 100 N in the direction of the brush motion. We are to determine the optimal four-contact-point pattern that provides the most robust equilibrium.

A free-body diagram of our metal block is shown in Fig. 3. We assume that each contact point is on a distinct edge of the rectangle and that friction is negligible. We parameterise the positions of the forces f 1 and f 2 with x and y and assume that the remaining forces are symmetric to f 1 and f 2 with respect to the origin.

The weight of the metal block is ignored, so that the task wrench set T is solely determined by the forces and moments applied by the tool. The force-moment system (f e , n e ) equivalent to each possible position and direction of motion of the brush is computed as The minimum degree of constraint satisfaction s is computed for all possible positions of f 1 and f 2 , which results in the graph of Fig. 4. In this figure, recall that the x-axis represents the positions of f 1 on the upper edge, while the y-axis represents that of f 2 on the right edge. Figure 4 shows that the metal block is best held in place by choosing the contact points at x = 100 mm and y = 95 mm. Interestingly, the contour s = 0 N corresponds to the stability frontier, so that we must have |x| ≥ 40 mm and |y| ≥ 40 mm for the workpiece to be stable. Let us use the index s to trace the WFW of a cable-driven parallel robot CDPR.

T = {f e ∈ R 2 , n e ∈ R : f e ∞ ≤ 100 N, |n e | ≤ 15 N m}.
A cable-driven parallel robot is a parallel robot that utilizes cables instead of rigid links. This particular characteristic provides CDPRs with advantages such as high dynamics and a large workspace, however their workspace is greatly reduced by the fact that eq. ( 4) can only be satisfied with non-negative forces or feasible cable tensions (the cables can pull but not push). For such robots, the set of feasible forces F defined in eq. ( 3) becomes the set of feasible cable tensions. The sets W and T in Fig. 2 define the available and required wrench sets of the robot. The available wrench set represents the ability of the cables to generate forces and moments on the moving platform, while the required wrench set represents the forces and moments that are applied by the environment on the platform for a specific task.

The WFW is the set of mobile platform poses for which the required wrench set is contained in the available wrench set. This implies that a pose belonging to the WFW must satisfy eq. ( 5) and that the tensions along each cable should be nonnegative and respect a tension range subject to the capabilities of the actuators. This workspace can be traced along a given area by using the minimum degree of constraint satisfaction to measure the degree of inclusion of the required wrench set polytope in the available wrench set polytope for each pose. The condition s = 0 defines the stability frontier, that is, the boundary of the WFW of the CDPR, and the positive values of s correspond to poses inside the WFW.

We used this observation to revisit the example of Fig. 5 of Gouttefarde et al. [START_REF] Gouttefarde | Interval-analysis-based determination of the wrenchfeasible workspace of parallel cable-driven robots[END_REF]. In this example, the geometry of the CDPR is as illustrated in Fig. 5,

F = {f ∈ R 4 :
f ∞ ≤ 50 N}, and T = {f e ∈ R 2 , n e ∈ R : f e ∞ ≤ 10 N, |n e | ≤ 0.5 N m}. We compute the minimum degree of constraint satisfaction s for each pose along a three dimensional grid. The robot is displaced along the XY plane and rotated through a range of orientations from -36 • to 36 • . The top and 3D views of the resulting WFW are shown in Fig. 5, and correspond to those obtained in [START_REF] Gouttefarde | Interval-analysis-based determination of the wrenchfeasible workspace of parallel cable-driven robots[END_REF]. The computed surface defines the stability frontier, therefore the platform must be kept within this boundary in order to remain stable. In order to obtain a more quantitative view of the capacity of the robot to withstand the required wrench set, the minimum degree of constraint satisfaction was also used to compute the constant orientation WFW. Figure 6 shows the resulting workspaces for fixed orientations of 0 • and 45 • , which also correspond to those obtained in [START_REF] Gouttefarde | Interval-analysis-based determination of the wrenchfeasible workspace of parallel cable-driven robots[END_REF]. The contour where s = 0 defines the stability frontier. We note that the workspace is contained inside the convex hull formed by the base anchor points and that its shape and size are altered by the 45 • rotation of the platform. We also note that in both cases the CDPR has a higher capacity to balance the required wrench set at the center of the workspace, and that this capacity is gradually reduced as the platform is shifted away from the center. In summary, we have defined a new kinetostatic index that is quite general, as demonstrated by the variety of the presented examples. In short, this index informs the designer of the closeness to instability, in Newtons. A negative value of the index indicates an unstable design, and a positive value, a stable one. We believe the index to be an interesting alternative to the manipulability and the dexterity, as it takes into account not only the geometry of the device, but also the forces and moments required by the task or allowed by the actuators or support members. Moreover, the minimum degree of constraint satisfaction represents the worst-case scenario, unlike manipulability and dexterity, which is thought more useful to the designer. The index is not flawless, however, and we are currently exploring alternative solutions to the dimensional homogeneity problem and to the associated computational burden.

Fig. 2

 2 Fig. 2 An analog representation of the mapping of F onto the wrench space

Fig. 3

 3 Fig. 3 Free-body diagram of the workpiece

Fig. 4

 4 Fig. 4 Isocontours of the proposed index s in Newtons as a function of the contact-point positions

Fig. 5

 5 Fig.5Boundary of the total-orientation WFW for the example proposed by Gouttefarde et al.[START_REF] Gouttefarde | Interval-analysis-based determination of the wrenchfeasible workspace of parallel cable-driven robots[END_REF]

Fig. 6

 6 Fig. 6 Isocontours of the proposed index s in Newtons as a function of the pose


Rafail Psiakis
email: rafail.psiakis@inria.fr

Angeliki Kritikakou
email: angeliki.kritikakou@inria.fr

Olivier Sentieys
email: olivier.sentieys@inria.fr

Fine-Grained Hardware Mitigation for Multiple Long-Duration Transients on VLIW Function Units

Technology scaling makes hardware more susceptible to radiation, which can cause multiple transient faults with long duration. In these cases, the affected function unit is usually considered as faulty and is not further used. To reduce this performance degradation, the proposed hardware mechanism detects the faults that are still active during execution and reschedules the instructions to use the fault-free components of the affected function units. The results show multiple long-duration fault mitigation with low performance, area, and power overhead.

I. INTRODUCTION

As technology size decreases, the hardware becomes more and more susceptible to radiation. Although multiple simultaneous faults have been neglected for a long time, [START_REF] Lisboa | Using built-in sensors to cope with long duration transient faults in future technologies[END_REF], they can no longer be negligible for technologies of 130nm and beyond [START_REF] Heijmen | Radiation-induced soft errors in digital circuits -a literature survey[END_REF]. The system clock period and the duration of the transient faults do not scale uniformly [START_REF] Simionovski | A bulk built-in current sensor for set detection with dynamic memory cell[END_REF]. The fault duration is proportionally increasing compared to clock period, and, thus, the occurring faults can last for several clock cycles [START_REF] Velamala | Design sensitivity of single event transients in scaled logic circuits[END_REF]. These Long-Duration Transient (LDT) faults have a much higher probability of creating system failures. Approaches to deal with LDTs are mask-based, spatial redundancy and sensors. Mask-based approaches have massive performance degradation [START_REF] Koser | A long duration transient resilient pipeline scheme[END_REF], as the execution is stopped until the two mask inputs become equal. Spatial redundancy inserts spare resources [START_REF] Klecka | Error self-checking and recovery using lock-step processor pair architecture[END_REF] having high area overhead.Built-In Current Sensors (BICS) monitor the induced transient currents to detect single and multiple LDTs with a significantly small cost [START_REF] Viera | Validation of Single BBICS Architecture in Detecting Multiple Faults[END_REF]. However, the execution is stalled as long as the faults are active [START_REF] Lisboa | Using built-in sensors to cope with long duration transient faults in future technologies[END_REF] inserting high performance overhead.

For better trade-off between area and performance overhead for fault tolerance, systems include several Function Units (FUs). Very Long Instruction Word (VLIW) processors usually consist of complex FUs able to execute all types of operations and simpler ones that cannot execute sophisticated operations, such multiplications and divisions. As the Instruction Level Parallelism (ILP) of the applications does not usually lead to full utilization of the FUs, the idle FUs can be used to mitigate faults occurring on the system. When not enough idle FUs exist, new time slots have to be added. However, the state-of-the-art approaches for VLIW processors focus on: 1) short duration transient faults and 2) permanent faults. As the first category assumes a fault duration smaller than the system clock cycle, these approaches do not apply the required restrictions during instruction execution to support LDTs [START_REF] Psiakis | Neda: Nop exploitation with dependency awareness for re-liable vliw processors[END_REF]. The second category permanently excludes the faulty FUs, when a fault is detected. Approaches that detect the faulty units before execution cannot be applied for LDTs [START_REF] Karri | Computer aided design of fault-tolerant application specific programmable processors[END_REF].

Few approaches detect the faulty FUs during execution, and, thus, they could be used for LDTs. However, they perform coarse-grained exploration, i.e. the faulty complex FUs can still be used as simple FUs, whereas the faulty part is permanently excluded for the rest of the execution [START_REF] Psiakis | Run-time instruction replication for permanent and soft error mitigation in vliw processors[END_REF].

To deal with LDTs, we propose a hardware mechanism to detect the active faults during execution and temporally exclude only the faulty components of the affected FUs for as long as it is necessary. Our main contributions are: i) the fine-grained micro-architectural solution that partitions an FU into components, where each component is enhanced with a BICS to identify occurring faults, ii) the online finegrained instruction scheduling mechanism that reschedules the instructions onto the healthy FU components, and iii) an evaluation analysis of the proposed hardware mechanism.

The organization of this paper is as follows. Section II presents an overview of the proposed mitigation mechanism, Section III and Section IV present the architecture details of the proposed mechanism, Section V presents the experimental results and Section VI concludes this work.

II. OVERVIEW AND MOTIVATION EXAMPLE

The target domain is VLIW processors. In the remaining sections, we use the 4-issue heterogeneous VLIW data-path of Fig. 2 to schematically illustrate our approach. The components in blue color correspond to the basic architecture, whereas we highlight the hardware components added or modified by our approach with yellow color. The VLIW consists of a 3-stage pipeline with Fetch (F), Decode (DC) and Execute/Memory-WriteBack (EX/MEM/WB). A number of instructions, named as instruction bundle is issued and executed in parallel by the FUs of the processor. The proposed approach focuses on LDT faults occurring in the arithmetic FUs, as they have the largest area footprint of the system combinatorial components based on our experiments in Table III. The faults in the storage components, e.g., register file, memory and pipeline registers, are assumed to be protected (e.g. using Error Correction Codes (ECC)). We illustrate through an example the main idea of this work. Fig. 1-i depicts the original schedule of two consecutive instruction bundles, B k-1 and B k , obtained by the compiler. Based on the instruction type, the instructions are assigned to different FU components, as depicted in Fig. 1-ii. Assume that, Reserve_DC

A 1 k k-1 FU[0] FU[1] FU[2] FU[3] C 1 C 2 A 2 A 1 B k-1 A 1 C 1 C 2 A 2 B k A 3 B 1 B 2 Comp 3 Comp 2 Comp 1 A 1, A 2, A 3 B 1, B 2 C 1, C 2
f[0] sel_EX/MEM f[1] f[2] NOP NOP NOP f[3]

III. FAULT CHECKER

The fault checker keeps the faulty status of the FU components, identifies new fault occurrences and takes care of miscalculated results. To achieve a fine-grained use of the components of an FU, each FU is internally enhanced with BICS. Both complex and simple FU types are analyzed in gatelevel to identify the individual circuits. In our architecture, we considered a complex FU as a simple FU enhanced with a multiplication operator. The complex (simple) FU has 15 (14) different FU operations and 8 [START_REF] Lisboa | Using built-in sensors to cope with long duration transient faults in future technologies[END_REF] individual circuits. The circuits are grouped based on the instruction opcode. For instance, the circuit that performs the addition of two registers (ADD operation) is partially shared with the circuit that calculates the address of a memory operation (MEM operation) and the circuit that performs ADDSHIFT operations. As they partially share the same execution path, they are grouped to the same individual component. Table I depicts the final obtained individual components for the complex FU. The individual components for the simple FU are the same without component 5. Each individual component and the final multiplexer (comp 0), which selects the result of the executed operation according to the opcode, is an FU component that is enhanced with a BICS sensor [START_REF] Lisboa | Using built-in sensors to cope with long duration transient faults in future technologies[END_REF]. The output of each BICS sensor is combined into a fault status signal, signal f, with a size of 9 (8) bits for complex FU (simple FU). The f signals of each FU are combined to a global signal, status, with a size equal to the number of the VLIW issues. The signal status represents which components of the FUs are currently affected by a fault, if the corresponding bit is set. In case of one or more active faults at cycle k-1, the results of corresponding instructions -currently residing in the execution stage -are miscalculated, and, thus, they must not be committed. For this purpose, each VLIW issue is enhanced with a multiplexer controlled by the signal sel_EX/Mem (size equal to the number of VLIW issues) computed by the fault checker. When a bit in sel_EX/Mem is set, the corresponding multiplexer passes a NOP result (instead of the miscalculated result) and the WB and MEM enable of the corresponding issue is disabled. The fault checker stores the status signal at cycle k -1 to be compared with the status signal at cycle k. The comparison identifies the just occurred faults (one bit signal occur). Both status and occur signals pass to the online fine-grained scheduler to be used for the instruction re-scheduling decisions.

IV. ONLINE FINE-GRAINED SCHEDULER

The instructions in the F/DC register are decoded at cycle k -1 and the scheduler at cycle k -1 decides the instructions to be executed at cycle k based on the status of the faulty FU components. The decoded instructions that couldn't be scheduled at cycle k, due to insufficient FUs or instruction dependencies, are stored to the Reserve DC shadow register. At the same time instance, the EX/MEM/WB stage executes the instructions scheduled for execution at cycle k-1 (scheduling decision occurred at cycle k -2). The Reserve DC/EX shadow register keeps the instructions executed at cycle k -1 in case a fault occurs during their execution. The instructions to be scheduled at cycle k -1 can potentially come from three sources: 1) the decoded instructions at cycle k -1 (DC) 2) the remaining instructions not scheduled at cycle k -2 (Reserve DC register) and 3) the executed instructions at cycle k -1 (Reserve DC/EX register).

In order to allow the scheduling of the instructions in different issues than the ones defined by the compiler's original schedule, a switch has to be inserted to the VLIW datapath. However, if the switch implemented all combinations between the three instruction inputs (DC, Reserve DC, and Reserve DC/EX) to the VLIW issues, the switch complexity would increase significantly. In contrast, the design of our online hardware mitigation mechanism reduces this overhead. A 2n to n switch, DC/EX switch, passes the instructions from one of the shadow registers and the decoded instructions DC to the main pipeline DC/EX register. A 2n to n multiplexer is used to decide which shadow register to be used as an input to the switch (signal sel_MUX).

The online fine-grained hardware scheduler is implemented by three components. The first one extracts the required information (info signal) from the F stage and calculates the dependencies between consecutive bundles (dep signal), similar to the resource and dependency analyzers of [START_REF] Psiakis | Neda: Nop exploitation with dependency awareness for re-liable vliw processors[END_REF].

The second component is the scheduler processing part that schedules the input (one of the three potential instruction inputs) to the output of the DC/EX switch using bit masks, called IDentifiers (IDs) and taking into account the status of the faulty components. I) required for the instruction execution, b) bit 1: when it is set, it is a remaining instruction, i.e. it has not been scheduled yet, and c) bit 0: when it is set, the instruction has a dependency with at least one of the instructions of the next bundle. For instance, the ID="00000001110" is decoded as: the operation requires the FU component 1, i.e. it can be a MEM/ADD/ADDSHIFT operation (bit 3=1), the final multiplexer (comp 0) is required (bit 2=1) and the instruction has not been scheduled yet (bit 1=1). The status of all FUs components is represented by the table Status ID, where each bit is the f signal of a FU enhanced by with an additional bit that is set when the FU is occupied.

The scheduling procedure is as follows: For all the instructions i of an input ID, i.e. the Res DC/EX ID, the Res DC ID and the DC ID and for each issue j described by Status ID, if the instruction i has not been scheduled and the FU in the j issue is unoccupied, we check if the required component is available. If it is available, the occupied bit of the corresponding Status ID is set, the remaining bit of the corresponding input ID is cleared, since the instruction is scheduled, and the signal sel DC/EX instructs the switch to pass the instruction currently at issue i to issue j. After that, a new instruction is explored.

The third component is the scheduler control part that controls the inputs and the execution of the scheduler processing part depending on the fault occurrence (occur signal) and the type of the scheduled instructions (signal flag). The state machine diagram of Fig. 4 describes its functionality, where i ∈ [0, n] and n is the number of issues.

C1:(Res_DC/EX_ID[i][1]==0)&&(DC_ID[i][0]==0) C4:(Res_DC_ID[i][1]==1)||(DC_ID[i][0]==1) C2:(Res_DC_ID[i][1]==0)&&(DC_ID[i][0]==0) C3:Res_DC/EX_ID[i][1]==0

Condi.ons hold i [0,n]: at cycle k, and, then, the current decoded instructions. If instructions still reside in the Reserve DC and/or if there is any dependent instruction in the current decoded instructions DC that cannot be scheduled (condition C4), the F/DC_stall signal is set to stall the F and the DC stage for one cycle in order the mechanism to schedule these instructions.

V. EVALUATION RESULTS

For the experimental results two heterogeneous VLIW configurations are used: i) 4-issue configured with 2 complex FUs, 2 simple FUs, 1 memory FU (MEM) and 1 branch unit (BR), and ii) 8-issue configured with 4 complex FUs, 4 simple FUs, 2 MEM and 1 BR. The processor has been enhanced with the proposed approach. Both the original unprotected VLIW processor and the VLIW with the proposed online fine-grained mitigation mechanism have been developed in C++ and synthesized using the Catapult High Level Synthesis (HLS) tool to obtain the RTL design. The gate-level netlist was generated by the Design Compiler of Synopsys using 28 nm ASIC technology. To evaluate our approach, we use ten benchmarks from the MediaBench suite. The benchmarks are compiled with VEX compiler for each configuration.

We compare the performance with existing online coarsegrained approaches, such as [START_REF] Psiakis | Run-time instruction replication for permanent and soft error mitigation in vliw processors[END_REF]. In contrast to the proposed fine-grained approach, the coarse-grained approach neither 1) explores the FUs in fine-grained way nor 2) applies temporal exclusion. For fare comparison, we randomly injected multiple faults (i.e. as many as the coarse grained approach can sustain) during the benchmarks' execution and we consider them as persistent, i.e. they last for the rest of the execution. Table II shows the cycles required to execute the ten benchmarks considering: i) 0 faults (Original), ii) 1 up to 4 multiple faults for the 4-issue configuration and iii) 2 up to 10 multiple faults for the 8-issue configuration. When no faults occur, both approaches have the same performance, i.e. the original execution cycles. We observe that: 1) the proposed approach inserts significantly lower overhead than the coarse-grained approach, and 2) in several benchmarks our performance is very close to the original one, i.e. without faults, even for several multiple faults. In contrast to the coarse-grained approach, our gain is achieved because whenever a persistent fault is detected, the proposed approach exploits the healthy FU components in the current and the next bundle execution.

We also present the logic area of each FU of a pipeline stage in Table III, which motivates the focus of the proposed approach on the execute stage, since it covers more area, and, thus, it is more exposed to faults. Table IV shows the area/power implementation results of the proposed mechanism with a target frequency of 200MHz. System's clock frequency is not affected because the critical path still resides in the EX/MEM/WB stage, while the only unit inserted in the pipeline (DC/EX switch) is strategically placed in the DC stage. Compared to the unprotected version, the proposed approach implies an area and a power overhead of up to 34% and 33%, respectively. The overhead of existing approaches is expected to be comparable, since both techniques require a switching mechanism and a re-scheduling logic, which are the costliest components of the design.

VI. CONCLUSION

Radiation can cause LDT failures. A hardware mechanism is proposed that, during execution, characterizes the FUs in a fine-grained way and reschedules the faulty instructions to the healthy FU components. Results show that multiple LDT mitigation is achieved with significant performance reduction.

Fig. 1 :

 1 Fig. 1: Illustration example of the proposed mechanism at cycle k-1, one fault that lasts at least two cycles affects the first and the third FU components of the first issue, FU[0], as depicted in Fig. 1-iii. The proposed mechanism decides the instruction rescheduling at cycle k-1 so as the instructions to be executed at cycle k. In the example of Fig. 1-iii, the scheduling of the B k-1 instructions is decided at cycle k -2. As no fault is detected during execution at cycle k -2, the VLIW executes the compiler's original schedule. During execution at cycle k-1, the mechanism detects two -just occurred -faults.To ensure a correct execution, the faulty B k-1 instructions must be re-executed at the next cycle avoiding the currently faulty FU components. Therefore, the A 1 instruction must be stored in order to be re-executed at cycle k. At cycle k, although the LDTs persist and the corresponding components have not yet recovered, the mechanism succeeds in executing the remaining instruction A 1 thanks to the re-scheduling of the B k instructions. This action is allowed if the instruction A 1 is independent from the B k instructions.

Fig. 2 :

 2 Fig. 2: VLIW enhanced with the proposed mechanism.

Fig. 3 :

 3 Fig. 3: ID coding follows: a) bits 10 to 2: when a bit is set, its position shows the FU component (TableI) required for the instruction execution, b) bit 1: when it is set, it is a remaining instruction, i.e. it has not been scheduled yet, and c) bit 0: when it is set, the instruction has a dependency with at least one of the instructions of the next bundle. For instance, the ID="00000001110" is decoded as: the operation requires the FU component 1, i.e. it can be a MEM/ADD/ADDSHIFT operation (bit 3=1), the final multiplexer (comp 0) is required (bit 2=1) and the instruction has not been scheduled yet (bit 1=1). The status of all FUs components is represented by the table Status ID,

Fig. 4 :

 4 Fig. 4: State machine diagram of the control part. (S1-S2) One (more) faults occurred at cycle k -1 (occ = 1): The executed instructions on the faulty FU components at cycle k -1 (which reside in Reserve DC/EX register) are not committed and they must be scheduled again for execution at cycle k. Whether or not the Fetch and Decode stages must be stalled (F/DC_stall) depends on whether the faulty instructions are decoded instructions at cycle k -2 (flag=0) or at cycle k -3 (flag=1). In the first case (S1), no stall is required and these instructions are the first to be executed at cycle k (Input ID=Res DC/EX ID). Then, the decoded instructions at cycle k-1 are explored (Input ID=DC ID). An example of this case is Fig. 1, where two faults occur during the execution of the instructions of bundle B k-1 at cycle k-1. During the scheduler decision for execution at cycle k, the remaining instruction A 1 is scheduled at issue 1 and, then, the decoded instructions of B k are scheduled. In the second case (S2), the stall signal is activated (F/DC_stall=1) and a new cycle is inserted for the re-execution of the Reserve DC/EX instructions. The process is repeated until no instructions are left in the Reserve DC/EX (guaranteed by condition C2). S3-S4) No fault occurred at cycle k -1 (occ=0): If no FU component is affected by a new fault at cycle k -1, the mechanism schedules first the remaining decoded instructions from cycle k-2 (that now reside in Reserve DC) for execution

TABLE I :

 I Component groups of a complex FU.

	Comp 0	Comp 1	Comp 2
	SELECT	MEM/ADD/ADDSHIFT	AND/NAND/ZEROEXT
	Comp 3	Comp 4	Comp 5
	OR/NOR/XOR	CMP/SUB	MUL
	Comp 6	Comp 7	Comp 8
	SRL	SRA	SLL

TABLE II :

 II Performance comparison (execution cycles) under several multiple faults and average performance overhead (%).

	Benchmarks					4-issue										8-issue
		Original	Fine-grained mechanism	Coarse-grained mechanism	Original		Fine-grained mechanism			Coarse-grained mechanism
	Num. faults	0	1	2	3	4	1	2	3	4	0	2	4	6	8	10	2	4	6	8	10
	adpcm dec	386	388	390	391	397	412	436	464	571	302	304	311	335	393	401	314	366	442	471	566
	adpcm enc	409	413	413	425	426	462	469	504	614	323	324	326	412	415	420	339	437	483	494	633
	bcnt	478	479	480	480	482	479	784	785	1159	333	335	336	338	339	397	335	527	545	580	1,085
	fft32x32	569	580	587	591	669	667	775	930	1371	400	402	403	439	447	483	424	520	728	835	1,428
	motion	344	350	350	358	368	391	392	407	598	280	281	282	285	287	302	282	284	363	377	619
	huff	1,101	1,111	1,117	1,119	1,158	1,136	1,137	1,176	1,488	951	952	954	957	958	990	959	961	1,072	1,074	1,466
	dct	1,288	1,314	1,315	1,456	1,458	1,353	1,627	1,846	2,606	872	877	912	953	954	992	951	1,322	1,369	1,544	2,578
	fir	6,852	6,853	6,854	6,901	7,333	7,693	8,593	8,714	11,599	5,709	5,710	5,712	6,012	6,235	6,740	6,070	7,092	7,213	8,105	11,820
	crc	12,228	12,229	12,229	12,231	12,232	12,274	12,275	14,851	20,969	11,955	11,956	11,959	11,960	11,989	12,245	11,956	11,958	12,217	15,107	20,964
	mat mul	11,142	11,143	12,423	13,010	15,011	15,015	16,039	16,358	21,593	6,533	6,535	6,538	6,539	7,102	8,112	6,534	10,951	11719	20,333	20,373
	Average overhead %	0.8	2.2	4.6	9.3	10.6	24.1	33.5	82.7		0.3	1.1	6.7	10.3	17.3	3.3	29.1	44.9	69.7	110.6

TABLE III :

 III Logic Area of pipeline stages (µm 2 ).

	DC	DC Br	Simple FU	Complex FU	MEM/WB
	250	2,530	1,533	3,843	358

TABLE IV :

 IV Area footprint and power estimation.

	Approach	4-issue area(µm 2 ) power(mW)	8-issue area(µm 2 ) power(mW)
	Unprotected	50,844	6.48	79,661	7.36
	Proposed	62,314	7.92	107,258	9.89


Mael Gueguen
email: mael.gueguen@irisa.fr

Olivier Sentieys

Alexandre Termier

Accelerating Itemset Sampling using Satisfiability Constraints on FPGA

Finding recurrent patterns within a data stream is important for fields as diverse as cybersecurity or e-commerce. This requires to use pattern mining techniques. However, pattern mining suffers from two issues. The first one, known as "pattern explosion", comes from the large combinatorial space explored and is the result of too many patterns outputed to be analyzed. Recent techniques called output space sampling solve this problem by outputing only a sampled set of all the results, with a target size provided by the user. The second issue is that most algorithms are designed to operate on static datasets or low throughput streams. In this paper, we propose a contribution to tackle both issues, by designing an FPGA accelerator for pattern mining with output space sampling. We show that our accelerator can outperform a state-of-the-art implementation on a server class CPU using a modest FPGA product.

I. INTRODUCTION

When analyzing data, an important task is to discover correlations. Such correlations can be that Amazon customers that buy a laptop often buy a mouse simultaneously, or that a set of files are often accessed simultaneously in a cloud storage context. These correlations give powerful insights on the contents of the data, that may be used to take actions. For example Amazon will immediately show mouses to customers having put a laptop in their cart, and the cloud storage operator will position the files often accessed together on the same physical machine.

Discovering potentially complex correlations is handled by Pattern Mining algorithms, whose goal is to explore a huge combinatorial space efficiently. Most of them have been designed for an offline data analysis setting: a static dataset is input to the algorithm which performs pattern extraction (runtime varying from a few seconds to several days depending on the data and parameters). The results are then manually reviewed by a data analyst. However, many modern settings require an online loop, where the data is continuously arriving. In this context, patterns are extracted in few seconds at most, and are used to take automated decisions. For example, Amazon needs to be able to adapt quickly to changes in customer behavior or arrival of new products, and file access patterns will change upon completion of projects using those files.

There exist some pattern mining algorithms that handle data streams, however they have two limitations: 1) they are likely to output thousands of results of mixed interest and 2) they are not designed to cope with a high throughput. The first limitation is shared by most pattern mining algorithms: they extract patterns that are repeated frequently in the data, and in practice there are many of such repeated patterns. A large portion of these patterns contain redundant information. There are several ways to reduce the number of patterns output to a manageable size, one of the most drastic being pattern sampling. The idea is to only compute a set of frequent patterns, and to have statistical guarantees that these patterns are a "good" sample of the complete set of patterns. Pattern sampling algorithms are a promising approach for performing a pattern-based analysis of data streams.

Our contribution is to show that pattern sampling can be performed extremely efficiently on an FPGA. This paves the way for future pattern sampling hardware accelerators, able to extract on the fly patterns from data streams with a very high throughput. More precisely, we adapted the state-of-the-art algorithm Flexics [START_REF] Dzyuba | Flexible constrained sampling with guarantees for pattern mining[END_REF] for execution on an FPGA. We explain how to sample randomly itemsets while keeping a control flow applicable for FPGA logic.

The paper is organized as follows. Section II introduces the pattern mining problem, the Eclat algorithm, and pattern sampling. Section III describes the state of the art Flexics algorithm for pattern sampling, as well as our algorithmic contribution to adapt Flexics to FPGA. Section IV presents the architecture of our approach. Results are presented in Section V. Last, Section VI concludes the paper and hints at future works.

II. BACKGROUND AND RELATED WORK

We first introduce the general pattern mining problem, as well as the Eclat algorithm for mining frequent itemsets. We then present existing approaches for accelerating pattern mining algorithms on FPGA and expose pattern sampling approaches.

A. Pattern mining

Consider an alphabet A = {X i }, with i ∈ 1, N . The elements of A are called items, and any subset I ⊆ A is called an itemset. A database D is a multiset of transactions, each transaction being an itemset of A. The support of an itemset I ⊆ A in D corresponds to the number of transactions of D containing I. An itemset is frequent in D if its support is above a user-defined frequency threshold t. There is a vast literature on algorithms for mining frequent itemsets. In this paper, we focus on the Eclat algorithm [START_REF] Zaki | New algorithms for fast discovery of association rules[END_REF]. Like most pattern mining algorithms, Eclat follows a "generate and test" approach: potentially frequent itemsets are generated, then their frequency is tested in the database. Eclat explores the search space of candidate itemsets in a depth-first manner, starting with small itemsets and augmenting them one item at a time. An example of a search tree is given in Figure 1. Note that the tree is asymmetric to avoid exploring twice the same itemset.

ECLAT relies on the Apriori principle [START_REF] Agrawal | Fast algorithms for mining association rules in large databases[END_REF] to prune the search space. If an itemset is infrequent in the database, any itemset that contains it will have a lower frequency and it will be infrequent too.

With the search space of Figure 1, consider the database D = {abc, bd, abd, acd} and t = 0.5. The itemset ab is present twice, thus has a frequency of 0.5 ≥ t, and is frequent: its children in the tree will be tested. On the other hand, the itemset abc is present only once, thus has a frequency of 0.25 < t and is infrequent. Its children in the tree do not need to be generated nor tested.

B. Itemset mining on FPGA

Two families of methods are described in the literature for itemset mining on FPGA. A first method is to use a controller like a CPU allowing for complex controls, and restrict the FPGA to accelerate the support counting of the itemsets [START_REF] Prost-Boucle | Efficient and versatile fpga acceleration of support counting for stream mining of sequences and frequent itemsets[END_REF]. The other methods accelerate the whole application on hardware [START_REF] Shi | Accelerating intersection computation in frequent itemset mining with fpga[END_REF], [START_REF] Zhang | An fpga-based accelerator for frequent itemset mining[END_REF]. The main difficulty is to streamline the exploration of the tree-shaped search space for an efficient execution on FPGA. The asymetry of the tree is a first problem. The second one is that pruning by the Apriori property, while strictly mandatory for performance, makes the search tree unpredictably irregular. The approach proposed by [START_REF] Zhang | An fpga-based accelerator for frequent itemset mining[END_REF] elegantly solves both problems, and we used it as a starting point in the design of our approach for FPGA-based pattern sampling.

C. Pattern Sampling

Output space sampling is tailored to return a bounded number of patterns without altering the database. Most approaches provide statistical guarantees that the distribution of the sampled patterns is similar to the distribution of the complete set of patterns. Earlier works have adapted standard statistical sampling methods to the case of frequent itemsets [START_REF] Hasan | Output Space Sampling for Graph Patterns[END_REF], or exploit simple statistical observations on the structure of the pattern space [START_REF] Boley | Linear Space Direct Pattern Sampling Using Coupling from the Past[END_REF].

More recently, Dzyuba et al. [START_REF] Dzyuba | Flexible constrained sampling with guarantees for pattern mining[END_REF] proposed the Flexics framework. Inspired by sampling strategies used in SAT (Boolean satisfiability) solvers, this approach is built on top of standard (non-sampling) frequent itemset mining algorithms. Flexics adds random XOR constraints that exclude some frequent itemsets from the result. These constraints have the property to partition the frequent itemset space in "cells", where the distribution of itemsets inside each cell is similar to the distribution of the complete space. Given an expected number of frequent itemsets in the output, Flexics will add as many random XOR constraints as necessary to get to a cell containing this number of frequent itemsets (within a small margin of approximation).

The Flexics framework is one of the most efficient for principled pattern sampling. Furthermore, the original paper shows how to build it above Eclat, an FPGA-friendly algorithm (compared to other frequent itemset miners). And the approach is based on XOR constraints, which are well handled by hardware. It thus seems especially relevant to base an FPGAbased pattern sampling method on the Flexics framework. To the best of our knowledge, this is the first pattern sampling accelerator on FPGA architectures. This is our contribution in this paper, presented in the next sections.

III. FLEXICS ALGORITHM FOR FPGA

This section explains our algorithmic contribution to adapt Flexics for FPGA, while the hardware architecture of our solution will be explained in the following section. We first explain how constraints are generated by Flexics. The two step approach proposed in software cannot be used on FPGA, we thus present our first improvement that allows dynamic generation of constraints on the FPGA. We then show how a major improvement of the constraint system can also be used with our approach. Finally, we explain how the constraints can be exploited in an FPGA version of Eclat.

A. Sampling Itemsets with a System of Binary Constraints

As introduced in the previous section, the main idea of Flexics is to use random XOR constraints to cut the itemset space in regions of equivalent size and distribution. The original Flexics algorithm is a two step process, where first the Weightgen oracle is called, followed by the actual itemset mining step. The Weightgen oracle, described in [START_REF] Chakraborty | Distribution-Aware Sampling and Weighted Model Counting for SAT[END_REF], estimates the weight of the solution (related to the number of results found) of a SAT problem. Weightgen can also be used to generate random arbitrary constraints on the variables of the SAT problem that will reduce the number of results, until the estimated weight is lower than or equal to a user specified threshold. In the case of Flexics, the SAT problem given to Weightgen is finding frequent itemsets in the database. The random constraints generated to sample the results are XOR constraints using the alphabet A of size N from the database. Generated XOR constraints have the form

i∈ 1,N b i .X i = b 0 , (1)
where b i are randomly generated independent variables in 0, 1 with a uniform distribution. For any i ∈ 1, N , a b i dictates if the item X i will be present in the XOR constraint (1 if present, 0 otherwise). The b 0 coefficient is called the parity bit, as a XOR with multiple inputs returns the parity of the sum of its boolean inputs. These XOR constraints acts as a system of boolean equations, where a given pattern can either satisfy all the equations for the system, or not satisfy at least one of them.

For example, with a database using an alphabet A = {a, b, c, d, e, f }, and given two randomly generated XOR constraints a ⊕ c ⊕ e = 1 and b ⊕ e ⊕ f = 0, we can check if two frequent candidate itemsets abde and abdf are to be outputed in the samples. For abde, the first XOR constraint gives

(1 ⊕ 0) ⊕ 1 = 1 ⇐⇒ (1) ⊕ 1 = 1 ⇐⇒ 0 = 1,
which is false. Thus, abde does not satisfy all XOR constraints and is not part of the subspace to be be outputed. For abdf , the first XOR constraint gives (1 ⊕ 0) ⊕ 0 = 1 ⇐⇒ (1) ⊕ 0 = 1, which is true, and the second one gives (1 ⊕ 0) ⊕ 1 = 0 ⇐⇒ (1) ⊕ 1 = 0 ⇐⇒ 0 = 0, which is true. Thus, the frequent itemset abdf satisfies all XOR constraints and will be outputed as a sample.

The two step approach (Weightgen then mining) is not relevant on an FPGA. First, implementing Weightgen would require a lot of estate, that would be unused most of the time. Second, in a streaming context one would like to be able to quickly react to changes in the pattern distribution, which is difficult to do when pre-computing the number of constraints. Our first contribution is thus to propose a single step approach for pattern sampling, that does not use Weightgen. Instead, the mining starts immediately, and during the mining, our approach dynamically generates new XOR constraints if the potential output size goes above the user-given threshold.

This way, the number of interesting patterns does not need to be estimated in advance, but the list of interesting patterns discovered has to be maintained when new constraints are generated by dynamically pruning patterns than do not satisfy the newly added constraints. The principles of our dynamic constraint generation is as follows. First, new XOR constraints are generated randomly. Our algorithm ensures that no constraint in the system of equations can be derived from a linear combination of the other constraints. If a newly generated XOR constraint causes the system of equations to be unsolvable, it is rejected. If it is equal to a linear combination of already generated constraints, the new constraint is also rejected. After a constraint is rejected, new constraints are randomly generated, until a generated random XOR constraint respects the criteria. In practice, however, there is a probability of 1 2 N -K for a new random XOR constraint to be rejected in a system already holding K XOR constraints. Thus, this process of rejecting constraints does not impact significantly average performance.

B. Rewriting the Constraints with Gauss-Jordan Elimination

The problem we try to solve is the following: scan the depthfirst tree with the ECLAT algorithm, but skip the itemsets that do not satisfy the generated XOR constraints. However, when scanning the sparse samples in the tree, there is no simple relation like the prefix/suffix separation used in [START_REF] Zhang | An fpga-based accelerator for frequent itemset mining[END_REF] between a sample and the next.

It is harder to compute what is the next sample to test given any position in the tree, and subsequently, to know if there exist satisfying itemsets down its branch or if the branch is finished. We developed a solution to reduce the problem of mining satisfying itemsets randomly distributed in the tree to a simpler yet equivalent problem that uses ECLAT on a reduced tree that represents at least all frequent satisfying itemsets.

At any given time with K generated XOR constraints, for an alphabet of size N , the corresponding system of equations would be in the form of

∀k ∈ 1, K ,   i∈ 1,N b i,k .X i   = b 0,k , (2)
where b i,k ∈ 0, 1 , ∀k ∈ 1, K and ∀i ∈ 1, N . With this notation, the b i,k can be considered as matrix coefficients for an array of size K × (N + 1). The parameter K is dynamic and data dependant (it increases as new samples are found) and is only theoretically bounded by N . Using linear combinations, the matrix corresponding to the system of equations can be transformed using Gauss-Jordan elimination, to generate a row echelon matrix. The solutions of the original system of equations and after the Gauss-Jordan elimination are strictly the same. The Gauss-Jordan elimination is a variant of Gaussian elimination which results in a unique normalized row echelon matrix. This unique matrix has two types of rows: one type can contain any value, while the other type of row contains exactly one 1 that delimits the echelon and 0 everywhere else. After a Gauss-Jordan elimination, our algorithm rewrites the system of equations in the form of

∀k ∈ 1, K , X c k =   i∈ 1,N -K ,fi>c k b fi,k .X fi   ⊕ b 0,k (3)
where {c i } i∈ 1,K denote the indexes of the rows corresponding to the echelons. There are K indexes c i as there are K rows in the Gauss-Jordan matrix. We refer to the items X ci as constrained items. All the other indexes corresponding to rows with any values allowed are noted as {f i } i∈ 1,N -K . There are N -K indexes f i as there are N indexes in total. The items with indexes X fi are called free items.

C. Scanning sample space with a bijective transformation

For any system of equations resulting from XOR constraints, our approach is to cut the alphabet into two parts:

• the set of constrained items X c k that appear in only one XOR constraint after Gauss Jordan elimination and • the set containing the rest of the alphabet, denoted free alphabet, whose items X fi can appear in any XOR constraint.

In this way, there are two complementary alphabets, that can be non-contiguous, splitting items from the initial alphabet in two categories. Then, the right hand of Equation 3 is computed using the b fi,k in the Gauss-Jordan Matrix and the X fi are equal to 1 if the f i are present in the free itemset and to 0 otherwise. This formula dictates if the items X c k are present in the constrained itemset or not. For two different itemsets constructed from A that satisfy the XOR constraints, their free itemsets are necessarily different. Reciprocally, there exists a single itemset constructed from A that satisfies the XOR constraints for each free itemset. Thus, there is a bijection between the pattern space of the database alphabet and the subspace of patterns satisfying the XOR constraints: a scan of all free itemsets can be used to scan all satisfying itemsets. Furthermore, a sample constructed from the full alphabet A will always be a super-set of its reduced free itemset. Thus, the Apriori principle dictates that if a sample itemset is frequent, its corresponding free itemset is also frequent. Thus, a scan of all frequent free itemsets can be used to scan all frequent satisfying itemsets. Frequent free itemsets can lead to infrequent satisfying itemsets, but the algorithm is guaranteed to find all samples.

Finding all frequent free itemsets can be done using ECLAT on the reduced free alphabet, and for each frequent free itemset, the algorithm will test its satisfying counterpart. For each itemset in the "reduced" depth-first tree, the accelerator tests the frequency of two itemsets. The free itemset has to be tested to allow pruning with the Apriori principle, and the sample itemsets have to be tested since they will be returned as the final result.

IV. ACCELERATOR ARCHITECTURE

This section presents the architecture of our accelerator on an actual FPGA board, and gives details on how the solution is implemented.

A. Overview

Figure 2 shows an overview of the accelerator architecture implemented in the programmable logic fabric of a Zynq FPGA from Xilinx. The zc702 evaluation board used for the experiments holds a System on Chip, containing two Cortex A-9 CPUs and a XC7Z020-CLG484-1 FPGA, connected to an off-chip 1GB DDR3 memory. Our design uses communications between the FPGA and the CPUs only when the hardware application starts and stops, in order to interface with the user. All accesses from the accelerator in the FPGA to the main memory are achieved using the High Performance AXI port, without cache coherency protocols. This section details the support counting acceleration of Figure 2 and an additional feature we called correspondence list. The candidate generation mechanism is based on [START_REF] Zhang | An fpga-based accelerator for frequent itemset mining[END_REF], improved to support XOR constraints, and will not be detailed here.

B. Support Counting

The support counting loop of the architecture takes most of the execution time, given the finite memory bandwidth. The Fig. 2. Overview of the accelerator architecture loop takes in transactions from the database, checks if the current candidate is present, and if so, increments a counter. Given a transaction bitvector and a candidate itemset bitvector, for the candidate to be present in the transaction, all bits set to 1 in the candidate have to be set to 1 in the transaction too. If we call the current candidate itemset to test c, and the current transaction from the database t, one way to implement this proposition with FPGA logic is

c ⊂ t ⇐⇒ t& c = c. (4)
This proposition can be simplified, since all bits set to 1 are set to 0 in t. Thus for all items in c, they have to be absent from t for c to be present in t:

c ⊂ t ⇐⇒ t & c = 0. (5)
Since this feature only uses simple logic gates and a counter increment, its impact on the area cost is very low.

C. Correspondence List Address Cache

Many dataset reduction techniques have been developed for pattern mining in order to exclude redundant or unnecessary operations. Several of them can be seen as preprocessing techniques to optimize the ensuing pattern mining, such as removing non-frequent items from the database, or grouping identical transactions together. Some others aim to optimize the mining of patterns using knowledge discovered during the pattern mining.

In the special case of a depth-first algorithm like ECLAT, if the set of transactions containing a frequent itemset is registered in the memory of the FPGA, it is guaranteed the next candidate itemset is a child of the itemset (when it is not a leaf of the tree), and its own set of transactions is contained in the registered set of transactions. By allocating in memory the addresses of transaction containing an itemset, the accelerator is able to scan a reduced portion of the database, as illustrated in Figure 3. If the set of addresses cannot fit in the allocated memory, the accelerator scans the whole database.

This technique can only work if the dataset uses a frequency threshold sufficiently low to fit in the FPGA memory. If the accelerator is tasked to find itemsets present in at least 90% of a large database, the correspondence list would not fit in the FPGA. The pattern explosion implies that a regular itemset miner could spend the majority of its execution scanning for itemsets with very low support (sometimes less than thousands or hundred of transactions depending on the database). Our proposition is to speedup the computation of these itemsets with low support, but with support still superior to the frequency threshold, when the density of the dataset favors it.

If we allow to register only the set of transactions of several frequent itemsets, it is possible to store the histories of frequent itemsets at different depths in the tree. this reduces the number of transactions accessed in memory. In order to only keep track of set of transactions of itemsets that can be reused by future candidate itemsets, the addresses of transactions of an itemset is evicted from memory depending on its depth in the tree.

D. Parameters' Influence on the Accelerator

In order to analyze the theoretical performance of the accelerator, we introduce two parameters: DB SIZE, the number of transactions in the database, and N B BLOCK, the number of memory accesses to get a transaction. During the support counting, the accelerator processes chunks of N N B BLOCK bits wide data in a pipelined fashion. If the memory is able to feed the accelerator without bandwidth limitation, the pipeline can process a chunk every four cycles at 100MHz. The number of cycles needed to compute the support of an itemset is 4 × DB SIZE × N B BLOCK.

If we consider an example where the memory has to deliver chunks of size N /NB BLOCK = 128 bits, the internal logic of the FPGA can process 128/4×100M b/s = 400M B/s. Thus, the accelerator will be stalled by the memory if it is unable to reach this throughput. This is often the case in I/O bound applications such as data mining. A simple way to tackle this issue is to encode the transactions inside the memory, and decode it back to bit vectors once in the FPGA. The naive approach to store potentially long bit vectors can be a huge waste of space and bandwidth, especially with sparse datasets containing many zeroes.

Figure 4 shows the amount of resources allocated on the XC7Z020 SoC for different values of N . An accelerator with a fixed value N can process any database with an alphabet of size less or equal to N . At the moment only rather small alphabets can be processed because of the high usage of Look-Up Tables (LUT), as nearly all of the slices are allocated for an alphabet of size 128. For the same alphabet size, only half of the available RAM and register slices are used. The parameter N is thus linked to two limiting factors: the allocated logic and the memory bandwidth. It is however noteworthy that the FPGA used in our experiments is rather small and our approach will scale efficiently with larger FPGA devices.

V. EXPERIMENTS

The dataset used for the performance analysis of our accelerator is available publicly from [START_REF] Dheeru | UCI machine learning repository[END_REF]. This dataset uses an alphabet of size 32. We impose N/N B BLOCK = 32 bits. The FPGA thus processes 100M B/s, which is close to the bandwidth between the memory and the FPGA. The dataset consists of around 13000 transactions, and the frequency threshold used is 1%. This fits very well the use case of a low-frequency support, and allows for our design to be tested with a wide range of correspondence list sizes.

A. Impact of Sampling on Execution Time

Figure 5 shows the effects of the sampling on the execution time. In this scenario, the accelerator can return any number of samples (no user bound), but the number of random XOR constraints is fixed at compilation. Each new constraint

B. Impact of Correspondence List Size

Figure 6 compares the execution time of the accelerator with and without a correspondence list. The correspondence list brings a very noticeable speedup with rather low amounts of memory allocated. Allocating memory to store 300 addresses (roughly twice the support threshold in this case) results in a speedup of 2.1. The maximum speedup corresponding to 3000 addresses reaches 4.7. Figure 6 also displays the amount of memory allocated in the FPGA for the tested values. The relation is not stricly linear because only fixed amounts of block RAM can be used. The correspondence list with a size of 3000 results in all the BRAM (140) being allocated.

C. Comparison Against Flexics

Table I shows results taken from [START_REF] Dzyuba | Flexible constrained sampling with guarantees for pattern mining[END_REF], where EFlexics (the fastest implementation of Flexics) is tasked to return 1000 samples. These results were obtained on an Intel Xeon CPU running at 3.2GHz and with 32Gb of RAM on the CP4IM dataset [START_REF] Guns | Itemset mining: A constraint programming perspective[END_REF]. We compare the execution of our accelerator running on the zc702 board when tasked to return a thousand samples to the software execution time, without allocating a correspondence table. Our accelerator achieves a speedup between 2 and 10, except for the kr-vs-kp dataset. The accelerator performs best with small alphabet sizes, as these problems require a lot less memory bandwidth.

VI. CONCLUSION

We proposed a first approach for performing pattern sampling on FPGA. This approach is promising: despite running on a modest FPGA clocked at 100 MHz, it can be up to an order of magnitude faster than a software version running on a server class Xeon CPU clocked at 3.2 GHz. We also proposed a dataset reduction technique applicable to depthfirst algorithms as ECLAT to improve execution time, at the cost of allocated memory on the FPGA.

The current approach is sequential: an exciting research direction is to parallelize the implementation in order to explore several branches of the search space simultaneously. Since itemsets access to the same database, the transactions can be used for the support counting of multiple itemsets. These two properties allow to divide the whole tree in subtrees that can be processed in parallel without requiring more communication between the FPGA and the memory.

This parallel extension of the proposed accelerator will allow to make good use of higher-end FPGA and reach throughputs compatible with real-time analysis on demanding streaming data. The current paper focused on the FPGA algorithm and its performance. In order to process actual streams, another important element is to have efficient communications between the RAM holding the data and the FPGA. In this regard, a solution is to compress the database in RAM, which will cost a small allocation of resources on the FPGA to decode the transactions, but will allow a much better use of the bus bandwidth.

Fig. 1 .

 1 Fig. 1. Example of a depth-first tree for the alphabet {a, b, c, d} in ECLAT

Fig. 3 .

 3 Fig. 3. Example of dataset reduction using correspondence list

Fig. 4 .Fig. 5 .

 45 Fig. 4. Execution time wrt. correspondence list size

Fig. 6 .

 6 Fig. 6. Execution time wrt. correspondence list size

TABLE I TIME

 I NEEDED (IN SECONDS) TO COMPUTE 1000 SAMPLES

		EFlexics (CPU)	Our FPGA
	german	25	11,7
	heart	45	11,6
	kr-vs-kp	9	12,7
	primary	10	1,2
	vote	19	5,8


Simon Rokicki

Erven Rohou

Steven Derrien

Aggressive Memory Speculation in HW/SW Co-Designed Machines

Single-ISA heterogeneous systems (such as ARM big.LITTLE) are an attractive solution for embedded platforms as they expose performance/energy trade-offs directly to the operating system. Recent works have demonstrated the ability to increase their efficiency by using VLIW cores, supported through Dynamic Binary Translation (DBT) to maintain the illusion of a single-ISA system. However, VLIW cores cannot rival with Outof-Order (OoO) cores when it comes to performance, mainly because they do not use speculative execution. In this work, we study how it is possible to use memory dependency speculation during the DBT process. Our approach enables fine-grained speculation optimizations thanks to a combination of hardware and software. Our results show that our approach leads to a geo-mean speed-up of 10% at the price of a 7% area overhead.

I. INTRODUCTION

The need for performance and energy efficiency has led to hardware platforms where energy/performance trade-off can be adjusted dynamically (e.g through Dynamic Voltage and Frequency Scaling (DVFS)). However, with the end of Dennard's scaling, the efficiency of DVFS has been decreasing, restricting the trade-off spectrum. This has led to the emergence of single-ISA heterogeneous multi-processor systems, where the use of different types of core exposes even more energy/performance trade-offs. For example, the ARM big.LITTLE architecture features low-power in-order cores and high-performance Out-of-Order processors [START_REF] Greenhalgh | Big.LITTLE Processing with ARM Cortex-A15 & Cortex-A7[END_REF]. In such systems, dynamic adaptation is made possible through a same single instruction set for all cores, enabling quasitransparent dynamic code migration between cores.

It is possible to enrich these platforms with VLIW cores, which offer excellent energy/performance trade-off for certain types of workloads (compute intensive loops with predictable control-flow). However because VLIW processors expose parallelism directly in their instruction set, transparent code migration is not possible. This restriction can be overcome through Dynamic Binary Translation (DBT) techniques, which can be used to maintain the illusion of a single-ISA system. This approach was followed by Transmeta with the Code Morphing Software (CMS) to allow the execution of x86 binaries on a VLIW core [START_REF] Dehnert | The Transmeta Code Morphing TM Software: Using Speculation, Recovery, and Adaptive Retranslation to Address Real-Life Challenges[END_REF] and more recently with NVidia's Denver architecture for the ARM ISA [START_REF] Boggs | Denver: Nvidia's First 64-bit ARM Processor[END_REF]. Because the DBT process is directly managed by the hardware (and thus transparent to the user), we will refer to such architecture as codesigned machines.

In a codesigned machine, the DBT involves additional computation at run-time to translate and optimize the binaries, which negatively impacts the performance. In the meantime, taking advantage of the VLIW core implies costly compiler optimizations (instruction scheduling, etc.). Because of this, designing an efficient DBT is very challenging, yet little is known about existing commercial implementations.

As of today, the performance of codesigned machines falls behind that of an OoO core. There is empirical evidence [START_REF] Mcfarlin | Discerning the Dominant Out-of-order Performance Advantage: Is It Speculation or Dynamism?[END_REF] that this performance gap is mostly due to speculative execution abilities in OoO cores. To close this performance gap, the DBT process must, therefore, use similar techniques.

In this work, we study how memory speculation can be implemented in codesigned machines. The proposed system dynamically identifies speculation groups and generates speculative code, along with support for rollback. Misspeculations are dynamically detected through a light-weight hardware mechanism which shares similarity with OoO Load-Store Queues (LSQ). Because the speculation process is managed by the DBT engine, it offers a fine grain control, enabling iterative continuous optimization. Our flow was implemented within Hybrid-DBT [START_REF] Rokicki | Hybrid-DBT: Hardware/Software Dynamic Binary Translation Targeting VLIW[END_REF], an open-source codesigned machine aimed at supporting research on the topic. More specifically, our contributions are the following:

• An complete open-source implementation of memory dependence speculation in a codesigned machine, including modifications to the host VLIW core and to the hardware accelerated DBT. • A quantitative analysis of the performance benefits and area overhead of the approach, along with a comparison against reference RISC-V implementations. The remaining of this document is organized as follows : section II presents the hardware and software modifications on Hybrid-DBT and Section III presents the experimental study we conducted.

II. PROPOSED APPROACH

In this section, we describe how we support speculative memory accesses in the Hybrid-DBT framework. Our approach builds on the notion of memory instruction groups, which consists of a set of load/store operations where load instruction can be speculatively executed before stores. In the following, we summarize how misspeculated operations are detected and corrected by our modified DBT flow depicted in Figure 1.

whether speculation should be activated (or not). A more detailed description of this stage is provided in Section II-A.

A. Overview of the speculation process

The speculation process is executed during the second optimization level in Hybrid-DBT. At this stage, the CFG of hot procedures has been built and inter-block optimizations have been applied. The first step consists of building speculation groups on frequently executed blocks. A speculation group is a set of store and load operations, where the loads are scheduled after the stores in the original machine code. We allow a given store instruction to be present in only one speculation group, as the group ID is explicitly encoded in the instruction. While building the speculation groups, we have to handle the limited size of the PLSQ: if the DBT finds more memory accesses than what can be stored in a single bank of the PLSQ, it creates another speculation group, which is assigned to another bank. The number of speculation groups inside a single block of binaries cannot be greater than the number of bank in the PLSQ.

Once speculation groups have been built by software DBT, instructions are scheduled without speculation, and profiling is activated. During profiling, the PLSQ keep tracks of how many time memory operations were executed, but also how often they alias with other accesses. This profiling information is stored within the spec Info memory.

In the meantime, the software DBT regularly checks all active speculation groups, and based on the profiling information, decides whether speculation (for a given group) should be triggered or not. When speculation is activated, the store to load dependencies in the target speculation group are removed from the Intermediate Representation. The block is then re-scheduled. In this version, speculative loads are flagged with a rollback mask (stored within the spec Info memory), which specifies the ID of the speculation group to which it is associated (these instructions will have to be re-executed when misspeculating).

During execution, addresses are checked by the PLSQ. Whenever aliasing is detected, the PC is reset back to the faulty load operation and the basic block is re-executed using the speculation mask. This ensures a coherent machine state when reaching the speculative store.

A key issue is how to choose the threshold that controls the activation/deactivation of the speculation process. In our implementation, speculation is activated when a speculation group has been used more than 70 times with an aliasing rate below 10%. In contrast, speculation is deactivated whenever the aliasing rate increases above 15%. Deactivating/reactivating speculation for the same group too frequently would trigger the scheduling process too often. Similarly, using a higher aliasing rate threshold would increase the cost of rollbacks. It is to note that to obtain the best possible performance this aliasing rate threshold should be chosen on a per-application basis, as rollback cost is not always the same.

B. Partitioned Load Store Queue

In order to dynamically check that the memory dependency speculation is correct, the VLIW core is extended with a Partitioned Load Store Queue (PLSQ). Whereas traditional Load Store Queues check and record every memory operation, our PLSQ is used in a software controlled environment. Consequently, we opted for a partitioned load/store queue, where smaller banks are built to handle a single speculation group. This design reduces the area cost of the PLSQ. The list of memory operations to check is built by the software optimizer and is finely controlled to fit into one bank. The number of bank in the PLSQ defines the number of concurrent speculation groups. The organization of the PLSQ is depicted in Figure 2 with three banks. It embeds a small memory block specInfo which contains information on speculation groups: the number of use, of aliasing and the rollback mask. When a specInit instruction is executed, the 8-bit address contained in the instruction is used to load this information from the memory and initialize the bank identified by specId. The software controlled PLSQ interacts with the VLIW processor through different custom instructions:

Spec info

#use #fail mask

• Instruction specInit is used to bind a given bank of the PLSQ with a speculation group. It uses an 8-bit address to refer to the correct speculation group in spec Info memory and a specId field to identify the bank to use.

• Instruction specClear resets a bank of the PLSQ, identified by the specId field and increments the number of use of the associated speculation group. • Speculative loads and stores have a field specId to identify the speculation bank to use and a bit set to specify if the incoming address should be added in the PLSQ or if the address should be checked. The internal organization of a given bank is shown in Figure 3. Each bank contains (i) two counters (for the number of aliasing and the number of uses), (ii) a set of registers to store the hashed addresses along with the ages of previous speculative instructions and (iii) parallel compare units to check if a given address conflicts with a stored address.

When a speculative memory operation occurs, the add bit is used to indicate if the new address has to be added to the queue or if it has to be checked. If this add bit is set, the hashed address is pushed to the queue. Note that we use the PLSQ for two purposes: detecting aliasing during speculation but also monitor addresses to detect speculation group candidates. During the speculation phase, memory loads are kept in the PLSQ and verified against the store instructions. During the profiling step, memory stores are kept in the PLSQ and verified against memory loads. Its age bit is then set. If the add bit is unset, the hashed address is compared with all the hashed addresses stored in the queue, whose age bit is equal to one. If any of these hashes matches, the rollback signal is set to one. On a clear instruction, all ages stored in the queue are set to zero. The bank also uses two registers to count the number of time a speculation area is used (i.e. the number of clear instruction on the bank) and the number of times rollback is triggered.

III. EXPERIMENTAL RESULTS

This section provides a quantitative and comparative analysis of the benefit for our memory speculation technique. Our aim is to evaluate both performance gain and area overhead, but also to compare our results against other types of micro-These benchmarks have been compiled using the RISC-V GCC tool-chain, with the O3 optimization flag. The generated binaries have been used for all the experiments, with different cycle accurate models. To measure the hardware area, we synthesized the different components with Design Compiler, targeting STMicroelectronics 28 nm technology.

A. Performance results

The first experiment conducted is focused on the performance of our system. We try to highlight i) the performance improvement of our system coming from the new speculation process, ii) how the system compares to a platform similar to the big.LITTLE. To answer those two questions, we measured the performance of all benchmarks using the different simulators. For Hybrid-DBT results, we made the first experiment without the speculation process and another with it.

Figure 4 shows the results obtained during this experiment. Our results show that our memory speculation leads to a geomean speed-up of 10% compared with the Hybrid-DBT framework without speculation. We can observe that our approach brings speed-up from most of Polybench applications. Indeed, the speculation was correctly applied to the most critical loops of the system. However, we notice several applications where no improvements were observed (from deriche to seidel). Figure 4 also provide a comparison with other micro-architectures. It is interesting to note that, for several kernels, Hybrid-DBT can outperform an OoO core.

B. Area overhead

The first experiment demonstrated that the speculation process brought a speed-up in the execution of benchmark applications. However, our approach also has a cost in hardware. We measured the size of the different hardware components added or modified in the system.

As a baseline, we provide the size of the VLIW core as well as the size of in-order and out-of-order cores. We also synthesized BOOM load/store queue alone.

Area results are displayed in Figure 5. The first observation to do is the difference between the LSQ and the PLSQ, which is around 7× smaller. This is mainly because we do not use store and data queue and because our queue is partitioned, which reduces the number of address comparisons address to do in parallel. We can also observe that the combination of the PLSQ, the extra memory Spec Info and the IR Scheduler only represents 17% of the VLIW size and the combination is smaller than the BOOM LSQ. It is important to remind that an LSQ in an OoO core cannot work properly without the reorder buffer. As a comparison, OoO core is around 5× larger than the VLIW core, with comparable execution units.

IV. RELATED WORK

In this section, we discuss prior work on memory dependency speculation in the context of DBT toolchains.

A. Dynamic Binary Translation

Previous work on Dynamic Binary Translation mainly focused on executing legacy binaries on an in-order VLIW processor [START_REF] Dehnert | The Transmeta Code Morphing TM Software: Using Speculation, Recovery, and Adaptive Retranslation to Address Real-Life Challenges[END_REF], [START_REF] Boggs | Denver: Nvidia's First 64-bit ARM Processor[END_REF]. Transmeta Code Morphing Software (CMS) is used to execute x86 binaries on custom VLIW cores, which are called Crusoe and Efficeon [START_REF] Dehnert | The Transmeta Code Morphing TM Software: Using Speculation, Recovery, and Adaptive Retranslation to Address Real-Life Challenges[END_REF]. NVidia's Denver architecture is a 7-issue in-order core capable of translating and executing ARM instructions [START_REF] Boggs | Denver: Nvidia's First 64-bit ARM Processor[END_REF]. Those two processors claim a form of memory dependency speculation. Transmeta's Crusoe processor has access to special load and store operations, which check if an aliasing occurred. However, there is no detailed information on the actual organization of the table used to keep these addresses. Crusoe and Efficeon architectures both have access to a shadow register file with special commit and rollback instructions, which facilitate rollback in case of misspeculation [START_REF] Dehnert | The Transmeta Code Morphing TM Software: Using Speculation, Recovery, and Adaptive Retranslation to Address Real-Life Challenges[END_REF]. NVidia's Denver architecture would use mechanisms similar to those done for the EPIC architecture, that is a mechanism similar to the memory conflict buffer [START_REF] Huang | Speculative Disambiguation: A Compilation Technique for Dynamic Memory Disambiguation[END_REF], [START_REF] August | Integrated Predicated and Speculative Execution in the IMPACT EPIC Architecture[END_REF]. Again, there is no detailed information on the actual implementation and its effectiveness. The only open codesign machine framework we are aware of is Hybrid-DBT [START_REF] Rokicki | Hybrid-DBT: Hardware/Software Dynamic Binary Translation Targeting VLIW[END_REF], which does not support speculative execution. In addition to being open-source, we provide precise result on performance and area overhead.

B. Memory dependency speculation

The emergence of EPIC architectures (e.g. Itanium) in the late 90's raised the issue of efficient speculative execution for in-order processors [START_REF] August | Integrated Predicated and Speculative Execution in the IMPACT EPIC Architecture[END_REF], [START_REF] Sharangpani | Itanium Processor Microarchitecture[END_REF]. For example, Gallagher et al. proposed to use a Memory Conflict Buffer (MCB) to record the address of speculative load in order to check for an potential aliasing. This approach has strong similarities with our approach, but with a few key differences. MCB is based on a set-associative structure that assigns load to a given bank. If this bank is full when a load is executed, a previous one has to be removed. This triggers the rollback process to ensure that the execution is safe. Of course, the table has to be large enough to reduce the number of unnecessary rollbacks, which is not the case in our approach. The second difference lies in the way rollback is handled: the MCB approach relies on compiler generated correction code to handle these situations, leading to an increased binary size. In their experimental study, the geometric mean of this augmentation is 10%. On the contrary, our approach is based on rollback masks, which are generated by the IR Scheduler without code size overhead.

The most obvious difference lies in their use of a static compilation. Indeed, the MCB approach relies on the static compiler to detect eligible load instructions, to schedule instructions and to generate correction code [START_REF] Huang | Speculative Disambiguation: A Compilation Technique for Dynamic Memory Disambiguation[END_REF]. Relying on the compiler implies that the technique cannot be applied to legacy code. In contrast, our technique is based on DBT and, consequently, is totally transparent to the end-user.

V. CONCLUSION In this work, we proposed a technique to support speculative memory access in a codesigned machine framework. Our approach uses a mix of software and hardware to enable aggressive speculation while minimizing overheads. Our results show that performance improvements of 10% can be achieved on compute intensive kernels with regular control flow for an area overhead below 7%. They also suggest that the impact of memory speculation on performance is severely limited by the lack of support for traces/hyperblocks [START_REF] Mahlke | Effective Compiler Support for Predicated Execution Using the Hyperblock[END_REF]. As a future work, we will investigate the possibility of building traces based on dynamic information, as in [START_REF] Yourst | Incremental Commit Groups for Non-Atomic Trace Processing[END_REF].

Fig. 1 .

 1 Fig.1. Overview of the HW/SW co-designed system. It is composed of the DBT processor assisted by a hardware scheduler, the VLIW core with additional support for speculation: Partitioned Load/Store Queue and execution mask.

Fig. 2 .

 2 Fig. 2. Global view of the Partitioned Load Store Queue with three banks

Fig. 3 .

 3 Fig. 3. Organization of a single bank of the PLSQ.

Fig. 4 .Fig. 5 .

 45 Fig.4. Speed-up for the different applications, using the non-speculative Hybrid-DBT as a baseline (higher is better)

• The whole speculation process is managed by the software optimizer, running on the DBT processor. It is in charge of building speculation groups and deciding