# Dynamic fault-tolerant VLIW processor with heterogeneous Function Units

Rafail Psiakis, Angeliki Kritikakou, Olivier Sentieys

► To cite this version:

Rafail Psiakis, Angeliki Kritikakou, Olivier Sentieys. Dynamic fault-tolerant VLIW processor with heterogeneous Function Units. Microprocessors and Microsystems: Embedded Hardware Design, 2022, 93, pp.104564. 10.1016/j.micpro.2022.104564. hal-03885490

HAL Id: hal-03885490

https://inria.hal.science/hal-03885490

Submitted on 6 Dec 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Dynamic Fault-Tolerant VLIW Processor with Heterogeneous Function Units

Rafail Psiakis, Angeliki Kritikakou, and Olivier Sentieys

Univ Rennes, Inria, IRISA, Rennes, France

## Abstract

Instruction Level Parallelism (ILP) of applications is typically limited and variant in time, thus during application execution some processor Function Units (FUs) may not be used all the time. Therefore, these idle FUs can be used to execute replicated instructions, improving reliability. However, existing approaches either schedule the execution of replicated instructions based on compiler schedule or consider processors with identical FUs, able to execute any instruction type. The former approach has a negative impact on performance, whereas the later approach is not applicable on processors with heterogeneous FUs. This work presents a hardware mechanism for processors with heterogeneous FUs that dynamically replicates instructions and schedules both original and replicated instructions considering space and time scheduling. The proposed approach uses a small scheduling window of two cycles, leading to a hardware mechanism with small hardware area. In order to perform such a flexible dynamic instruction scheduling, switches are required, which, however, increase the hardware area. To reduce the area overhead, a cluster-based approach is proposed, enabling scalability for larger hardware designs. The proposed mechanism is implemented on VEX VLIW processor. The obtained results show an average speed-up of 24.99% in performance with an almost 10% area and power overhead, when time scheduling is also considered on top of space scheduling. Compared to the unprotected version, the instruction reliability has increased by 2.2×.

## 1 Introduction

Modern systems follow technology and voltage scaling trends in order to meet industry's demands in increasing performance, area minimization and energy consumption reduction. However, decreasing transistors size and voltage makes processors more susceptible to reliability violations [1, 2]. Common sources leading to reliability violations, such as radiation-induced Single-Event Upsets (SEUs) and Single-Event Transients (SETs) [3], and electromagnetic interference [4], can cause faults leading to temporary errors (soft errors), permanent errors (hard errors) or semi-permanent (intermittent errors) [5]. To provide protection, systems are extended with error detection/correction capabilities.

The majority of existing works has mostly focused on protecting the storage components of a system, e.g., memories, register file, and pipeline registers, considering the impact on the combinational logic negligible. However, this is not true for technologies of 130nm and beyond [6]. The probability of a component to be affected by faults is highly related to its area. As shown by our experimental results, Function Units (FUs) occupy the largest combinational area (more details in Table 6 - Section 5), making FUs the most vulnerable combinational components of the processor.

To protect these components, either Hardware (HW) or Software (SW) redundancy is used. HW redundancy inserts additional FUs to the original processor, in order to execute in parallel the same instruction and to compare the obtained results [7]. Although small performance overhead is normally ob-
served (due to comparison of the results), the area overhead is significant. SW redundancy modifies the program by inserting replicated instructions to be executed on the original processor. Although the area is not increased, the impact on the execution time is significant [8]. A better area and performance trade-off for fault tolerance can be achieved, when processors with several FUs are used. Very Long Instruction Word (VLIW) processors is an example, where several issues exist that can process instructions in parallel. Depending on the configuration, VLIW issues consist of complex FUs, able to execute all operation types, and simpler FUs, which, however, cannot execute sophisticated operations, such as multiplications and divisions. The set of instructions, executed in parallel, is called instruction bundle. Due to the limited application's Instruction Level Parallelism (ILP) and the different type of FUs, concurrent utilisation of all FUs is not always possible. As shown in the experimental results, the average ILP of ten benchmarks on a VLIW processor having 4 issues is 2.15 (more details in Table 7 - Section 5). Therefore, the idle FUs can be used to execute the replicated instructions, reducing the negative impact of SW redundancy on the execution time.

The exploitation of the idle FUs, to execute redundant instructions, can be achieved statically or dynamically. Static approaches are usually implemented by the compiler, which duplicates or triplicates and schedules the instructions at compile time in the instruction memory and extends the Instruction Set Architecture (ISA) to include special comparison instructions [9]. Although the obtained schedule can theoretically be as dense as possible, code size is significantly increased, increasing the required storage size. To remove this drawback, dynamic approaches have been proposed, implemented by hardware mechanisms. Dynamic hardware approaches reschedule the instructions at run-time despite compilers scheduling, in order to exploit idle slots and achieve fault tolerance.

Existing dynamic approaches, such as [10, 11], couple the VLIW issues, removing the need of a dynamic scheduler. Duplicated instructions are executed on the coupled pipelines, following the schedule of the original instructions, provided by the compiler. How-

ever, due to the lack of dynamic scheduling, there is a negative impact on the performance. Approaches with dynamic scheduler are designed for homogeneous VLIW, i.e., each issue includes all FU types, in order to be able to execute any instruction [12, 13]. However, such approaches are not applicable when the VLIW issues have different types of FUs, because the scheduler does not take into account the constraints over the type of FUs in an issue. Extending a heterogeneous VLIW to a homogeneous VLIW by inserting all FU types to each issue significantly increases area, especially when floating-point FUs are used.

To address these limitations, a hardware mechanism is proposed that enhances VLIW processors with heterogeneous FUs with fault tolerant capabilities. The proposed mechanism dynamically replicates instructions and reschedules original and replicated instructions both in the current bundle (space scheduling - S) and in the next upcoming bundle (time scheduling - T), improving performance, with reduced complexity and area overhead. To achieve this, a scheduling exploration window of two instruction bundles is used. In this way, new opportunities are created for optimizing the schedule during execution, while the scheduling complexity remains low. Within this window, the instruction rescheduling is only restricted by the FUs type and any dependency among the instructions within the scheduling window. This work extends the idea of dynamic instruction rescheduling of [14], where only the concept and some preliminary performance results, based on simulations, were presented. More precisely, this work presents the implementation of proposed mechanism consisting of i) a hardware dependency analyzer, ii) a hardware replication scheduler, and iii) a hardware voting scheduler. The dependency analyzer identifies dependent instructions between two concurrent bundles. The replication scheduler dynamically reschedules original and replicated instructions, avoiding the insertion of additional time slots, by postponing the execution of independent instructions to the next bundle. The voting scheduler synchronises original and replicated instruction in order to compare their outputs, masking any occurring error. Due to dynamic rescheduling, switches have to be inserted in
the VLIW pipeline. To reduce the area and critical delay overhead, we propose a switch hardware design that simplifies the complexity of the scheduler, compared to commonly used switches. Last, but not least, to enable scalability, we propose a novel cluster-based approach; a large VLIW is divided in several clusters, each consisting of a smaller VLIW. The proposed dynamic hardware mechanism is applied within a cluster (intra-cluster), providing significant gains in area, with small performance loss. To support our contributions, we implemented on the VEX VLIW processor and compare the proposed approach that applies instruction triplication, considering space scheduling (TMR-S) and space and time scheduling based on clusters (TMR-S+T+CB), with typical hardware FUs triplication methods and the unprotected baseline VLIW. We performed extensive experimental results, providing performance, area, power and reliability metrics for ten benchmarks.

The remaining of this paper is organized as follows. Section 2 presents the proposed approach through an illustrative example. Section 3 describes the intra-cluster dynamic mechanism. Section 4 describes the proposed cluster-based version. Section 5 presents the experimental results. Section 7 discusses the related work on fault tolerant VLIW processors. Finally, Section 8 concludes this work and summarizes its contributions.

## 2 Illustrative Example

In this section, we provide an example to illustrate the proposed approach. Our example is depicted in Fig. 1 and it will be used throughout the manuscript as a running example. For simplicity reasons and without loss of generality, we assume an 4-issue VLIW, as the one in Fig. 2. The VLIW configuration has one Arithmetic Logic Unit (ALU) and one Branch unit (BR) in the Issue[0], one ALU and one Memory FU (MEM) in the Issue[1] and one ALU and one Multiplication unit (MUL) in Issue[2] and Issue[3]. Fig. 1a provides (on the left) the schedule given by the compiler and (on the right) the corresponding assembly instructions, with the destination and source registers. For instance, $ADD_1$ is an

<figure><img src="image_2.png" /><figcaption>(a) Original schedule obtained by the compiler.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>(b) Dynamic schedule obtained by the proposed approach.</figcaption></figure>

<caption>Figure 1: Illustration example for an 4-issue VLIW.</caption>

instruction that adds the values of the registers $r1$ and $r3$ and stores the result to the register $r2$. The compiler has scheduled these instructions to three instruction bundles, $B_{i-1}$, $B_i$ and $B_{i+1}$. $B_{i-1}$ has two instructions ($ADD_1$, $MUL_1$) and two idle slots ($NOP$), $B_i$ has two instructions ($SUB_2$, $ADD_2$) and two idle slots, and $B_{i+1}$ has one instruction ($OR_3$) and three idle slots.

The proposed approach replicates instructions and dynamically schedules original and replicas on the FUs, within a scheduling window of two instruction bundles. Fig. 1b shows the schedule obtained by the proposed dynamic mechanism, when instruction triplication is applied. The light (dark) blue boxes represent original (replicated) instructions.

To obtain this schedule, a *dependency analysis* initially takes place between the instructions of two consecutive bundles (implementation in Sections 3.2.1 and 3.2.2). The goal is to identify dependent instructions, i.e., an instruction in bundle $B_{i-1}$ that uses, as destination register, a destination or source register of an instruction in bundle $B_i$. Parallel execution of the dependent instructions is forbidden. Independent instructions of $B_{i-1}$ can be postponed and scheduled at
any idle FUs of the next bundle. In Fig. 1, *MUL*<sub>1</sub> of bundle *B*<sub>*i*−1</sub> is independent, since none instruction of bundle *B*<sub>*i*</sub>(*SUB*<sub>1</sub>, *ADD*<sub>2</sub>) uses the destination register of *MUL*<sub>1</sub> as destination or source register. However, *SUB*<sub>2</sub> and *ADD*<sub>2</sub> of bundle *B*<sub>*i*</sub> both depend on *ADD*<sub>1</sub>, since they read register *r*2, updated by *ADD*<sub>1</sub>. In a similar way, the instruction *OR*<sub>3</sub> of *B*<sub>*i*+1</sub> reads registers *r*5 and *r*6, which are used as destination registers by *SUB*<sub>1</sub> and *ADD*<sub>2</sub> of *B*<sub>*i*</sub>.

The results of the dependency analysis are used by
the *replication scheduler*, responsible for the dynamic
scheduling of original and replicated instructions (im-
plementation details in Section 3.2.3). The scheduler
operates according to three priorities, applied in the
following order: ① instructions of a previous bundle
have a higher priority than instructions of the
current bundle, ② the dependent instructions have
a higher priority than the independent instructions,
and ③ instances of different instructions of the same
bundle have higher priority than the replicated in-
stances of the same instruction. These priorities re-
duce the negative impact on performance, because
of the execution of replicated instructions to provide
fault tolerance. By scheduling first the dependent
instructions, the remaining instructions are indepen-
dent and can be potentially scheduled in the next
bundle. Fig. 1b depicts which of the three priorities
the hardware scheduler uses each time in order to
obtain the schedule. At the time slot *t*<sub>*i*−1</sub>, the origi-
nal, the first replica and the second replica of *ADD*<sub>1</sub>
are scheduled, due to priority ②. Then, the orig-
nal *MUL*<sub>1</sub> is scheduled, due to priority ③. Since
the remaining instructions from bundle *B*<sub>*i*−1</sub> are in-
dependent, they are allowed to be scheduled along-
side with the instructions of the upcoming bundle *B*<sub>*i*</sub>.
Due to priority ①, the first and second replica of the
*MUL*<sub>1</sub> of bundle *B*<sub>*i*−1</sub> are scheduled at the time slot
*t*<sub>*i*</sub>. Then, each of the original *SUB*<sub>2</sub> and *ADD*<sub>2</sub> are
scheduled, due to priorities ② and ③. However, the
remaining unscheduled instructions of *B*<sub>*i*</sub> are depen-
dent, and thus, they cannot be executed with the
upcoming bundle *B*<sub>*i*+1</sub>. Hence, a new time slot has
to be added. At this new time slot *t*<sub>*i*+1</sub>, the remain-
ing dependent and redundant instructions of *B*<sub>*i*</sub> are
scheduled based on priority ① and ③. At *t*<sub>*i*+2</sub>, no
instruction remains from the previous bundle, thus

original and replicated *OR*<sub>3</sub> are scheduled, according
to priority ③.

Last, but not least, after the execution of the sched-
uled instruction, the *voting scheduler* is responsible
for synchronizing and grouping the original and the
replicated instructions in order to compare their re-
sults and mask any occurred error (implementation
details in Section 3.2.4).

3 Intra-cluster Dynamic Mechanism

The proposed approach is applied over a VLIW pro-
cessor, which has a fixed issue-width during execu-
tion, defined at design-time, running a single appli-
cation. Dynamically reconfigurable and fault tol-
erant VLIWs, such as [15], where several applica-
tions are executed in parallel, is left as future work.
Fig. 2 depicts the original VLIW datapath consist-
ing of a 3-stage pipeline with Fetch (F), Decode
(DC) and Execute/Memory-WriteBack (EX/M-WB)
in blue color. The yellow color highlights the hard-
ware components that implement the proposed intra-
cluster dynamic approach. These hardware compo-
nents are categorized as follows: i) processing type
(the *replication switch*, the *voting switch*, and the
*voters*), ii) control type (the *information extraction
unit*, the *dependency analyzer*, the *replication sched-
uler*, and the *voting scheduler*) and iii) storage type
(the *ReplicRes* register and the *VotingRes* register).

The information extraction unit performs an early
decoding in the F stage, providing the necessary in-
formation to the dependency analyzer and the repli-
cation scheduler. The dependency analyzer is the
component responsible for analyzing two subsequent
bundles in order to identify potential dependencies.
The replication switch propagates previously decoded
instructions (stored at the ReplicRes register) and the
currently decoded instructions to the pipeline DC-
toEX register, following the dynamic schedule pro-
vided by the replication scheduler. The voting switch
propagates the results of the previously executed in-
structions (stored at the VotingRes register), as well
as the results of currently executed instructions to the
<figure><img src="image_4.png" /><figcaption>Figure 2: Original VLIW data-path (blue) enhanced with the proposed fault tolerant mechanism (yellow).</figcaption></figure>

voters for correction, following the dynamic schedule provided by the voting scheduler. The objective of our approach is to reduce the negative impact on performance, due to the execution of replicated instructions to provide fault tolerance. Therefore, the hardware components, that do not necessarily require to be placed inside the VLIW data-path, are designed to run in parallel and to have a smaller critical path than the VLIW pipeline stages, in order to not affect the clock frequency. The remaining components, that must obligatory added in the VLIW data-path to support the functionality of the proposed approach, are designed with reduced critical path and are placed in different pipeline stages, so as to reduce the impact on the overall clock frequency. For instance, the replication switch is added in the DC stage, which has a smaller critical path than the EX/M-WB stage. Through the information provided by the voting scheduler, the voting switch is significantly simplified, as described in the following paragraphs. We leave as future work the extension of the proposed approach to VLIW processors that support long immediate and multi-cycle instructions. For the rest of the manuscript, let $n$ represent the number of VLIW issues.

# 3.1 Processing and Storage Components

## 3.1.1 Replication Switch and ReplicRes Register

The replication switch selects which, among the $2 \times n$ possible inputs (i.e., $n$ outputs of the decoders, one per issue, and $n$ positions from the ReplicRes register) will be propagated and become the $n$ inputs of the pipeline register DCtoEX. Each input/output of the switch is a decoded instruction. For instance, Table 1 depicts the structure of the decoded instruction of the VEX VLIW processor [16], used in the experimental section. The switch input signal has a width of $2 \times n \times Size_{Dec}$ bits. To avoid a full switch $2n$-to-$2n$, which decreases the clock frequency, the replication switch is placed in the DC stage. Due to this positing, an exact copy of output of the decoders of the previous cycle is stored to the ReplicRes register. In this way, the replication switch implementation is simplified, reducing its complexity, area and impact on clock frequency. The switch output has a width of $n \times Size_{Dec}$ bits. To implement the replication switch, $n \times (2n$-to-1) multiplexers are required with a selection signal of $n \times log_2(2n)$ bits. Fig. 3 illustrates the replication switch for the 4-issue VEX VLIW processor; the input signal has a width of $2 \times 4 \times 109 = 872$ bits, the circuit has $4 \times 8$-to-1 multiplexers and a selection signal of $4 \times 3$ bits.

## 3.1.2 Voting Switch and VotingRes Register

The voting switch is placed after the FUs. It is responsible for grouping correctly the results of the original and replicated instructions: a) into the VotingRes register, and b) into the voters. For instance, Table 2 shows the structure of the result, after the execution of an instruction, for the VEX VLIW processor. When replicas of one instruction remain to

<table><caption>Table 1: Decoded instruction ($Size_{Dec} = 109$ bits).</caption><thead><tr><th>Data from RF</th><th>Data from RF/Immediate</th><th>Data for Store instruction</th><th>Dest. addr.</th><th>Opcode</th></tr></thead><tbody><tr><td>32 bits</td><td>32 bits</td><td>32 bits</td><td>6 bits</td><td>7 bits</td></tr></tbody></table>
<figure><img src="image_5.png" /><figcaption>Figure 3: *Replication switch* implementation.</figcaption></figure>

be executed, the results of the already executed instances of this instruction need to be temporarily stored. This storing takes place at the VotingRes register. Therefore, the VotingRes register has $2 \times n$ entries to store the results of up to two instances of one instruction per issue.

<table><caption>Table 2: Instruction's result ($Size_{res} = 78$).</caption><thead><tr><th>FU result</th><th>Data to store in memory</th><th>Dest. addr.</th><th>Opcode</th><th>WB Enable</th></tr></thead><tbody><tr><td>32 bits</td><td>32 bits</td><td>6 bits</td><td>7 bits</td><td>1 bit</td></tr></tbody></table>

Typical symmetrical designs for switches have high complexity, which will lead to increased overheads if used by the proposed approach. To reduce complexity, we propose an asymmetrical design for the voting switch reducing the number of required 2-to-1 muxes. The improved design uses 44 2-to-1 muxes, comparing to 132 2-to-1 muxes used by typical designs, reading to 66% gain. The voting scheduler groups upfront the results of the same instruction instances to the VotingRes register. Then, each such group is attached to a specific voter. To perform this grouping, the results of the two instances of the same instruction are stored in adjacent entries of VotingRes register, i.e., in the even entry for the first instance and in the odd entry for the second instance. More precisely, the voting switch has $n$ inputs (coming from the FU output at each issue), which will be stored at

the register VotingRes, following the grouping provided by the voting scheduler through a select signal of $log_2(n) \times 2n$ bits. Fig. 4 presents the implementation of the voting switch considering the 4-issue VLIW. Fig. 4a depicts the part related to the grouping of the results. It has 4 inputs to be stored at the register VotingRes with 8 entries ($VotingRes[0]$ to $VotingRes[7]$). The select signal is 16 bits. Due to

<figure><img src="image_6.png" /><figcaption>(a) Part for grouping to VotingRes register.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>(b) Part for connecting a voter to an issue.</figcaption></figure>

<caption>Figure 4: *Voting switch* implementation.</caption>

this grouping of results, the switch is simplified, i.e., it is not required to connect all the inputs of the voters with all the FUs and all the entries of VotingRes register. More precisely, the three inputs of a voter, belonging to an issue $i$, are connected as follows: 1) the first input $0$, Voter[i][0], requires to be connected only to the outputs of the FUs, 2) the second input 1, Voter[i][1], requires to be connected either to the FUs or to the entry VotingRes[i], and 3) the third input 2, Voter[i][2], requires to be connected to either
the FUs or the entry VotingRes[i+1]. Fig. 4b depicts the part of the switch related to the connection of one voter. It has $n + 2 = 6$ inputs ($n$ from the FU outputs and 2 from the VotingRes register outputs), which have to be connected to the 3 inputs of a voter. Finally, the select signal is $\log_2(n) \times 3 + 2 = 8$ bits.

### 3.1.3 Voters

The Voting switch provides to the voters the results, already grouped, after the execution of the three instances of one instruction. The voters compare and select which is the correct value to be provided at the output. Note that, the proposed approach replicates the complete decoded instruction, i.e., all the fields shown in Table 1. Since the address for the memory operations is also calculated in the execution stage by the FUs and it is available in the FU result field, we partially protect also the memory operations.

## 3.2 Control Logic Components

### 3.2.1 Information Extraction Unit

The information extraction unit is depicted in Fig. 5. It reads each instruction from the F stage and extracts the opcode, the destination, and the source registers. To reduce the cost of the Voting scheduler and Replication scheduler, each instruction, currently in the pipeline, is associated with an Instruction Identifier (ID) and the number of instruction instances that need to be executed (Rem). This early decoded information is stored in an intermediate internal register (Info register). The register outputs are read by the dependency analyzer and the replication scheduler.

An ID value has a size of $Size_{IDvalue} = n + 1$ bits. The first $\log_2(n)$ Least Significant Bits (LSBs) show the type of the instruction. The next $\log_2(n)$ bits show the original position of the instruction inside a bundle, which corresponds to the issue where the instruction has been scheduled by the compiler. The Most Significant Bit (MSB) indicates whether the instruction belongs to the previous ($MSB = 0$) or to the current bundle ($MSB = 1$). The coding of the ID for the 4-issue VLIW is depicted in Table 3. Bit $b_4$ indicates the bundle where the instruction belongs to

<figure><img src="image_8.png" /><figcaption>Figure 5: Information extraction unit and Dependency analyzer.</figcaption></figure>

($b_4 = 0$ for previous bundle, $b_4 = 1$ for current bundle). Bits $b_3$ and $b_2$ show the original position of the instruction inside a bundle. Bits $b_1$ and $b_0$ carry the information about the instruction type.

<table><caption>Table 3: ID encoding in the information extraction unit.</caption><thead><tr><th colspan="4">B<sub>i-1</sub></th><th colspan="4">B<sub>i</sub></th><th></th></tr><tr><th>Bundle</th><th>No.Issue</th><th>Inst/ons</th><th>Bundle</th><th>No.Issue</th><th>Inst/ons</th><th>Instr. Type</th><th></th></tr><tr><th>b<sub>4</sub></th><th>b<sub>3</sub></th><th>b<sub>2</sub></th><th>b<sub>1</sub></th><th>b<sub>0</sub></th><th>b<sub>4</sub></th><th>b<sub>3</sub></th><th>b<sub>2</sub></th><th></th></tr></thead><tbody><tr><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>NOP</td></tr><tr><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>MEM</td></tr><tr><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>MUL</td></tr><tr><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>ALU</td></tr></tbody></table>

Each of the four registers, that is considered as an input and an output of the two switches (FtoDC, ReplicRes, DCtoEX and VotingRes), is associated with an array of IDs, as depicted in Fig. 6. The size of each array is $Size_{ID} = n \times Size_{IDvalue}$. Two additional arrays (Rem) are associated with FtoDC and ReplicRes registers, i.e., FtoDC\_Rem and ReplicRes\_Rem, used for the replication of an instruction. These arrays indicate the number of instances of the instruction that remain to be scheduled. When a bundle is in the DC stage, the values of the FtoDC\_Rem are initialized to 3, since instruction triplication is applied as fault tolerance method. At the next time slot, some of these instructions are potentially executed on the FUs. Therefore, the values of the ReplicRes\_Rem are updated to depict the num-
③ among the remaining instructions, instances of different instructions have higher priority than the replicas of a single instruction. Three groups are created to depict these scheduling priorities: 1) *ReplicRes* for the previous instructions, 2) *FtoDC_Dep* for the dependent current instructions, and 3) *FtoDC* for the independent current instructions. To design a hardware scheduler with low complexity, the scheduler should use simple logic. To achieve that, the IDs are transformed to occupation vectors, enabling the scheduler implementation through simple bitwise logic.

**Occupation vectors** Each aforementioned group has three entries, since triplication is used as fault tolerant method. Each group entry includes two vectors: 1) *instr*, where each bit corresponds to an issue and indicates if an instruction exists (occupies the issue), and 2) *mul*, where each bit indicates if the instruction of the issue is a multiplication (e.g., in the 3rd and 4th issue of the VLIW configuration of our running example). Table 4 shows how to obtain the *instr* vector. More precisely, the bit *i* is set if at least one of the LSBs of *ID[i]* is not zero and instruction instances remain to be scheduled (*Rem[i]*). *i* represents the issue number and *j* ∈ [0, 2] represents the original instruction, the first replica and the second replica, respectively. Especially, the instructions must be dependent (*Dep[i]*), for the *FtoDC_Dep* group and independent (!*Dep[i]*), for the *FtoDC* group. The bits in the *mul* vector are set, when the IDs in the issues with a multiplication unit have a multiplication instruction, e.g., *i* ∈ {2, 3} in the 4-issue VLIW of Fig. 2 with an *ID[i]*[1:0] = 10.

Fig. 7 depicts the occupation vectors of Fig. 1b at time $t_i$. The instruction in issue 2 (third entry in *ReplicRes*) needs to be executed two more times (*ReplicRes_Rem*|2|=2). Therefore,

<table><caption>Table 4: Creation of *instr* vector.</caption><thead><tr><th>Group</th><th>instr[i]</th></tr></thead><tbody><tr><td>ReplicRes</td><td>(ID[i][0] || ID[i][1]) &amp; (Rem[i] &ge; 3 &minus; j)</td></tr><tr><td>FtoDC_Dep</td><td>(ID[i][0] || ID[i][1]) &amp; (Rem[i] &ge; 3 &minus; j) &amp; Dep[for of the issues (issues_up), 2) the vector with the scheduled instructions (fit) and 3) the vector with</td></tr><tr><td>FtoDC</td><td>(ID[i][0] || ID[i][1]) &amp; (Rem[i] &ge; 3 &minus; j) &amp; !Dep[i]</td></tr></tbody></table>

the 3rd bit of the *ReplicRes[1]* and *ReplicRes_ instr[2]* is set. The instruction is a multiplication, thus the vector *mul* is set to 10 to all the entries of *ReplicRes mul*. The *FtoDC_Dep_ instr*, *FtoDC_Dep_ mul*, *FtoDC_ instr* and *FtoDC_ mul* are constructed in a similar way.

<figure><img src="image_9.png" /><figcaption>Figure 7: Occupation vectors of the running example.</figcaption></figure>

**Bitwise Scheduler** Following the scheduling priorities, the groups and the occupation vectors are explored in the order depicted by Fig. 7 (latin numbers). For an occupation vector, the scheduler applies three phases: i) scheduling through *direct assignment*, ii) scheduling through *circular exploration*, and iii) decision for time-slot insertion.

i) *Direct assignment:* During this phase, only the issue, where the instruction is originally scheduled by the compiler, is checked for scheduling. Hence, no verification of the issue's FU type is required. The scheduler has two inputs: 1) the occupation vector for the instructions to be scheduled (*instr*), and 2) the current occupation of the issues (*issues*) (with bit 3 corresponding to issue 0 and bit 0 to issue 4). Three outputs are created: 1) the updated occupation vector of the issues (*issues_up*), 2) the vector with the scheduled instructions (*fit*) and 3) the vector with
the instructions to be scheduled (*rest*). As shown in Eq. 1, the scheduling is performed through a bitwise OR operation between the *instr* and *issues* vectors. The *issues\_up* is compared (bitwise XOR) with the initial output vector *issues* to decide which of the instructions can be mapped directly to the output (*fit*), and thus, to be scheduled for execution. To reflect the scheduling decision, the *ID* and *Rem* arrays are modified as follows: a) if *fit[i] = 1*, then *Rem[i] = Rem[i] - 1*, and b) *DCtoEX_ID[i] = ID[i]*. The *sel\_r* vector signal is updated to reflect the scheduling decision to the *replication switch*: *sel\_r[i] = i + n*, when a vector from the *ReplicRes* group is scheduled, and *sel\_r[i] = i* for the vectors of the other groups. To obtain the instructions, that could not be scheduled directly (*rest*), the vector *fit* is compared with the initial input vector *instr*. If the result is zero, this phase has scheduled all instructions, and the next input vector is explored. Otherwise, the circular exploration phase is applied to schedule the *rest* instructions to the empty FUs.

$$
\begin{align*}
\text{issues\_up} = \text{instr} \parallel \text{issues}, \\
\text{fit} = \text{issues\_up} \oplus \text{issues}, \\
\text{rest} = \text{instr} \oplus \text{fit}. \tag{1}
\end{align*}
$$

Before describing the next scheduling phase, we
illustrate how the direct assignment is applied to the
running example. Initially, the *issues* vector equals
to zero. Following the priorities, the first group to be
scheduled is *ReplicRes*. The first vector of the group
is zero, thus no instruction exists for scheduling.
The second vector is *instr* = 0010. The output *fit* is
the same as the input *instr*, thus all instructions can
be scheduled (*rest* = 0000). To depict the scheduling
decisions, the *ID* and *Rem* arrays are modified
as follows: a) *ReplicRes\_Rem[2] = Rem[2] - 1*,
b) *DCtoEX_ID[2] = ReplicRes\_ID[2]*, and
*sel\_r[2] = 2*. The next vector is *instr* = 0010, while
the *issues* is initialised with the previously calculated
*issues\_up*. Now, the output *fit* is different than the
input *instr*, implying that some instructions could
not be scheduled through direct assignment (*rest* =
0010).

ii) *Circular exploration:* During this phase, the
type of FU per issue is verified. This mechanism

takes three inputs: 1) the occupation vector for the
instructions to be scheduled (*instr*), which is equal
to the vector *rest* provided by the direct assignment,
2) the *mul* occupation vector for these instructions,
and 3) the current occupation of the issues (*issues*),
which is equal to the *issues\_up* provided by the di-
rect assignment. The output is the assignment signal
*assign*, which holds the configuration of the *replica-
tion switch* to adequately propagate the instructions
that have been scheduled for execution.

<caption>**Algorithm 1:** Representative cases of the circular exploration phase.</caption>

Input: instr, issues_up, mul
Output: assign array
1 switch instr do
2 ...
3 case 1000 do
4 if (issues_up[2] = 0) then assign[1] ← 0;
5 else if (issues_up[1] = 0) then
assign[2] ← 0;
6 else if (issues_up[0] = 0) then
assign[3] ← 0;
7 case 0010 do
8 if (issues_up[0] = 0) then assign[3] ← 2;
9 else if (mul[1] = 0) then
10 if (issues_up[2] = 0) then
assign[1] ← 2;
11 else if (issues_up[3] = 0) then
assign[0] ← 2;
12 case 0011 do
13 if (mul = 10) then
14 if (issues_up[2] = 0) then
assign[1] ← 3;
15 else if (issues_up[3] = 0) then
assign[0] ← 3;
16 else if (mul = 01) then
17 if (issues_up[2] = 0) then
assign[1] ← 2;
18 else if (issues_up[3] = 0) then
assign[0] ← 2;
19 else if (mul = 00) then
20 if (issues_up[3] = 0) then
assign[0] ← 2;
21 else if (mul = 01) then
22 if (issues_up[2] = 0) then
assign[1] ← 2;
23 else if (issues_up[3] = 0) then
assign[0] ← 2;
24 if (issues_up[2] = 0) then
assign[1] ← 3;
25 ...
Algorithm 1 presents some representative cases of the circular exploration phase. In the first two cases, only one instruction needs to be scheduled. When instr = 1000, the instruction cannot be a multiplication. When instr = 0010, the instruction can be a multiplication. This is because the issue, where the instruction is original scheduled, has a multiplication FU. In the former case (line 3), the instruction can be potentially scheduled in any available issue. In the latter case (line 7), two possibilities exist: a) whatever the value of mul[1], the instruction can be potentially executed in issues_up[0] (corresponding to the 4^th^ issue), and b) otherwise, if mul[1] = 0, the instruction can be potentially executed in any possible issue. The third case (line 13) has two instructions for scheduling (case 0011). Since these instructions are originally scheduled in issues with the multiplication FU, we have to check if the instructions are multiplications. Three possibilities exist: a) mul[1] = 1 and mul[0] = 0, b) mul[1] = 0 and mul[0] = 1, and c) mul[1] = mul[0] = 0. No available scheduling exists when both instructions are multiplications, due to FU restrictions. For a) and b) cases, the multiplication instruction cannot be scheduled, since the remaining idle issues do not have a multiplication FU. Only the non-multiplication instruction can be scheduled. For c) case, no multiplication instruction exists, thus both instructions can be scheduled in any available issue. When three instructions need to be scheduled (case 1101, 1110, etc.), this has the least complexity. All three instructions have been tested for direct scheduling and failed. The only legitimate action is to potentially schedule the non-multiplication instructions (instr[2], instr[3]) (e.g. 1101 → 1011). The signal assign[i] is updated with the new issue, where the instruction is now dynamically scheduled. For instance, if instr is 1000 and is scheduled to 0100, then assign[2] equal to 0, to show that instruction of issue 0 is now scheduled to issue 1. The assign[i] signal is used to update the issues_up vector, the ID arrays and the signal sel_r.

In our running example, after the direct assignment
of *ReplicRes* group, *rest* = 0010. Since *issues_up* =
0010, the condition of line 8 in Algorithm 1 is met.
Therefore, *assign*[3] ← 2. Consequently we have:
a) *issues_up* = 0011, *Rem*[2] = *Rem*[2] − 1 and b)

DCtoEX_ID[3] = FtoDC_ID[2]. The sel_r vector
signal is updated to sel_r[3] = 2.

iii) *Time-slot insertion decision:* If no appropriate FU is available for scheduling and there are still instructions from the previous bundle (*ReplicRes*\_rem ≠ 0) or dependent instructions (*FtoDC*\_rem ≠ 0), an additional time slot must be inserted. Instructions from the previous bundle, that have not managed to be scheduled in the current bundle, will need in any case an additional time slot, since there are not enough FUs to schedule them in the current bundle, while the instructions of the current bundle have to be also replicated and scheduled. Pending dependent instructions require also an additional time slot, as they cannot be scheduled in parallel with instructions from the upcoming bundle. The additional time slot is achieved by stalling the fetch and decode stages for one cycle.

3.2.4 Voting Scheduler

This scheduler is responsible for the grouping of:
i) the results of currently executed instructions at
the *VotingRes* register, and ii) previous and current
results to the *voters* and the *commit/memory*
phase. To perform the grouping, we use the array *unGrouped_ID*,
created by concatenation of the
two inputs of the voting switch, i.e., *DCtoEX_ID*
and *VotingRes_ID*. A comparison-based sorting algorithm
groups the instructions with the same *IDs*
in order to form triplets. The output is a sorted array (*Grouped_ID*).
Each triplet in the *Grouped_ID* is linked with the voter of one issue.
Based on this sorted array, the values of the signal *sel_v*
are defined and used to configure the *voting switch*.
For instance, the triplet formed in the three first
places of the *Grouped_ID* array, i.e., *Grouped_ID[0]*,
*Grouped_ID[1]* and *Grouped_ID[2]*, sends the corresponding
instructions to the first voter. In case
the triplet is not formed yet, e.g., IDs exist only
in *Grouped_ID[0]* and/or in *Grouped_ID[1]*, the results
of the corresponding instructions are stored
to the *VotingRes[0]* and *VotingRes[1]* registers. In
this phase, the constraints on memory operations
must be respected. Therefore, memory instructions
are allowed to be grouped only in positions linked
with issues that have a MEM FU, e.g., the entries *Grouped_ID[3]*, *Grouped_ID[4]* and *Grouped_ID[5]*, for the 4-issue VLIW of Fig.2, since they are linked to the voter of the second issue, where a memory FU exists.

## 4 Cluster-Based Approach

By analysing the area overhead of the components of the intra-cluster dynamic mechanism (as shown in Table 8 of the experimental section), we observe that the costliest components, in terms of area, are the switches. Switches also decrease maximum clock frequency. It should be stressed that this holds true for any approach that performs dynamic re-scheduling of the instructions, since this type of techniques requires to dynamically dispatch the instructions to different issues. We have carefully designed the switches of the proposed approach in order to achieve simpler complexity (as explained in Section 2). However, with the increase of the number of issues, the complexity of the switches is also increased, affecting the area overhead and clock frequency. Table 5 presents the number of inputs, outputs and the complexity of the proposed replication and voting switches, in numbers of required 2-to-1 muxes, considering in a single cluster, with respect to the number of VLIW issues. To address this limitation, we propose a cluster-based approach that reduces the area and time overhead, when the number of issues increases.

<table><caption>Table 5: Comparison of number of inputs, number of outputs and complexity for replication switch and original and improved voting switch (Section 3.1.2) in numbers of required 2-to-1 muxes.</caption><thead><tr><th rowspan="2">Issue</th><th colspan="4">Replication switch</th><th colspan="4">Voting switch</th></tr><tr><th>In</th><th>Out</th><th>Single Cluster</th><th>Cluster based</th><th>In</th><th>Out</th><th>Single Cluster (Orig. Switch)</th><th>Single Cluster (Impr. Switch)</th></tr></thead><tbody><tr><td>4</td><td>8</td><td>4</td><td>28</td><td>28</td><td>12</td><td>12</td><td>132</td><td>44</td></tr><tr><td>8</td><td>16</td><td>8</td><td>120</td><td>56</td><td>24</td><td>24</td><td>552</td><td>100</td></tr><tr><td>16</td><td>32</td><td>16</td><td>496</td><td>112</td><td>48</td><td>48</td><td>2256</td><td>212</td></tr><tr><td>32</td><td>64</td><td>32</td><td>1952</td><td>224</td><td>96</td><td>96</td><td>9120</td><td>436</td></tr></tbody></table>

Instead of having a single large VLIW applying directly the intra-cluster dynamic mechanism of Section 2, we combine several clusters, i.e., instances of

a VLIW with a smaller number of issues, and apply the dynamic mechanism of Section 2 inside each cluster. For instance, Fig. 8 shows how the cluster-based approach is applied; to obtain an 8-issue VLIW, two parallel 4-issue VLIWs are used. Table 5 shows the benefits of using the proposed cluster-based approach in terms of number of inputs, outputs and complexity. The complexity of the switches with the cluster-based approach increases in a linear way. For a VLIW with $m \times n$ issues, the switch overhead in area equals to the number of clusters $m$, times the switch overhead, used internally in the $n$-issue VLIW. Since the clusters work in parallel, no further delay is inserted, no matter how much we scale the design. In this way, the complexity of the schedulers remains the same, i.e. equal to the schedulers complexity for $n$-issue VLIW. However, with the proposed cluster-based approach, the dynamic scheduling can be applied only within a cluster.

<figure><img src="image_10.png" /><figcaption>Figure 8: 8-issue VLIW with cluster-based $2 \times 4$ approach.</figcaption></figure>

Considering that the compiler usually schedules
the instructions as dense as possible to occupy less area in the memory, it first tries to schedule the instructions in the first issues. Therefore, when the configuration of the large VLIW is provided to the compiler, it will first schedule the instructions to the first cluster, while the rest of the clusters may remain empty. This original schedule can lead to a negative impact on the performance of the proposed cluster-based approach. Instructions are gathered in the first cluster and the potential idle issues of the remaining clusters cannot be exploited, resulting in unnecessary stalls of the VLIW processor. To address this problem, we combine the cluster-based approach with a virtual VLIW configuration. The configuration of the FUs in the overall VLIW is done offline by shuffling FUs randomly. Then, instead of asking the compiler to generate code with the real VLIW configuration, we provide this virtual configuration. The goal is that the compiler generates the corresponding code, achieving a more balanced distribution of the instructions and NOPs into the clusters. In order to keep the area overhead low, a static de-shuffling of the instructions is applied during execution (during the fetch stage), providing the correct instructions to the clusters, based on the real FU configuration. Fig. 8 depicts such an offline shuffling of FUs (green box) and the static de-shuffling occurring during a global fetch, that distributes the 8 instructions from the virtual scheduling to the corresponding issues of the two 4-issue clusters. This static de-shuffling choice might have a negative impact to the benefits of the proposed approach. In order to not negatively affect the proposed approach, the minimum required number of same FUs in a cluster should be aligned with the fault tolerance method. For instance, when the instructions are triplicated, at least three FUs of the same type should belong to the same cluster, if possible. In this way, an instruction can be triplicated and executed in parallel within a bundle. It is our future work to explore methods to identify a near-optimal configuration of the clusters and the shuffling/de-shuffling, based on the available FUs, the fault tolerance approach and the application instructions. The stall signal (stall) of each cluster has to be global for the whole architecture; the fetch and de-code stages of all clusters are stalled, if at least one

needs an extra time slot.

# 5 Experimental Results

## 5.1 Experimental set-up

As a case study, we use as baseline processor an in-house VLIW, which is compatible with the VEX compiler of HP [16] and is described by a high-layer C++ model. This C++ model can be synthesized to the gate level using Mentor Graphics Catapult High Level Synthesis (HLS) and Synopsys Design Compiler. The single cluster VLIW configuration used in the experimental section is the 1 × 4-issue, consisting of 4 ALU, 2 MUL, 1 MEM, 1 BR. Larger cluster VLIW configurations are multiples of the basic configuration, e.g. 2 × 4-issue consists 2 × the 1 × 4-issue configuration, except for the BR unit (i.e., 8 ALU, 4 MUL, 2 MEM, 1 BR). Table 6 depicts the combinational logic area of each FU type. As the execute stage has the largest combinational logic, it is more exposed and susceptible to faults, which motivates the focus of our approach to protect FUs.

<table><caption>Table 6: Combinational logic area of FU types (μm²).</caption><thead><tr><td>DC</td><td>DC with BR</td><td>ALU</td><td>MUL</td><td>MEM/WB</td></tr></thead><tbody><tr><td>250</td><td>2,530</td><td>1,533</td><td>3,843</td><td>358</td></tr></tbody></table>

To evaluate our approach, we have used ten basic media benchmark kernels with different characteristics from the MediaBench suite [17]. We selected Mediabench as a workload to evaluate the behavior of the proposed approach as it is the one of the popular multimedia benchmark suite. The behavior of the proposed approach depends on the number of idle issues left by the application and the compiler. We present the results for ten applications with different characteristics, e.g., as Table 7 shows we have low ILP and several multiple dependencies (adp_dec, adp_denc), high ILP and different dependencies (bcnt, dct, fft32x22s, matrix_mmul) and low ILP and less multiple dependencies (huff_ac_dec, motion,fir, crc). We expect that applications from other benchmarks suites will have a similar behavior
if their benchmark analysis is similar to the analysed ones. We compare the following VLIW processor architectures:

1. Original version, i.e., the unprotected processor.

2. TMR-3FUs version, i.e., a fault tolerant processor where the FUs of the execution stage are tripli-cated and concurrently execute the same instruc-tion.

3. TMR-S version, i.e., a fault tolerant processor that triplicates instructions and dynamically schedules original and redundant instructions only in the current bundle, called Space scheduling. Extra bundles are added if instructions cannot fit in the current bundle. Such an approach is inspired by [10, 11], considering instruction triplication, in-stead of duplication, and leveraged in order to be applicable for heterogeneous VLIW processors.

4. TMR-S+T+CB version, i.e., a fault tolerant pro-cessor with the proposed approach, that triplicates instructions and dynamically schedules original and redundant instructions within a scheduling window of two instruction bundles, called Space & Time Cluster-Based scheduling.

The aforementioned architectures have been devel-
oped in C++ and synthesized using the Catapult
High-Level Synthesis (HLS) tool (University Version
10.0b/273613). Following this approach, we are capa-
ble of both simulating the processor and synthesizing
a functional RTL design. Note that the presented re-
sults provide an upper bound in the area and power
overhead, since HLS tools are not yet capable to pro-
duce the same high quality results as hand written
RTL code [18]. However, since all the aforementioned
vliw processor variations have been implemented us-
ing HLS, the comparative results should not be signif-
icantly different from hand written RTL code results.
The generation of the gate-level netlist was handled
by Design Compiler (Version J-2014.09-SP5-7) from
Synopsys using a 28-nm ASIC library. The power
analysis is given by Design Compiler, based on a sta-
tistical activity factor estimation assuming that every
net toggles 10% of the time.

Section 5.2 analyses the benchmarks in order to
motivate the proposed approach. Section 5.3 presents
the evaluation results with respect to performance,
area, and power consumption for the proposed intra-
cluster dynamic mechanism, i.e., for the single clus-
ter VLIW configuration, consisting of 4-issues. Sec-
tion 5.4 evaluates the cluster-based approach for sev-
eral clusters. Section 5.5 computes the reliability for
the proposed approach.

5.2 Benchmark analysis

We analyze the binaries of the benchmarks to mea-
sure the i) possibility to execute instructions in paral-
lel, by computing the average number of instructions
per bundle (Instruction Level Parallelism - ILP), and
ii) number of dependent instructions between two
concurrent bundles.

Table 7 illustrates the obtained results for the sin-
gle cluster configuration. We observe that 1.51 ≤
ILP ≤ 2.85 (4-issue configuration), 1.75 ≤ ILP ≤ 4.46
(2 × 4-issue configuration), 1.89 ≤ ILP ≤ 5.58 (4 × 4-
issue configuration) and 1.89 ≤ ILP ≤ 7.4 (8 × 4-issue
configuration). This implies that, in several bundles,
there is a sufficient number of idle issues. We also ob-
serve that by doubling the number of issues, the ILP
is not doubled. This behavior is due to the limited
parallelization capability of the applications and to
the heterogeneity of the FUs. Through the ILP met-
ric, we can conclude that there are idle issues inside
one bundle that can be explored for fault tolerance.
Such an exploration is achieved by space scheduling
(TMR-S).

To see if we can explore the next bundle (through
time scheduling), we compute the percentage of the
dependency occurrences, i.e., zero, one, two and three
or more instructions are dependent between two con-
current bundles. For the majority of the benchmarks,
in more than 50% of the total instruction bundles,
two consecutive bundles have zero dependencies. It
is quite frequent to have only one dependent instruc-
tion. Last, but not least, the case of multiple con-
current dependencies is rare. We can conclude that
the proposed approach will affect less negatively the
performance, since it can schedule the independent
instructions to the next upcoming bundle, avoiding
<table><caption>Table 7: Benchmark analysis</caption><thead><tr><th rowspan="3">Benchmark</th><th colspan="5">1x4-issue</th><th colspan="5">2x4-issue</th><th colspan="5">4x4-issue</th><th colspan="5">8x4-issue</th></tr><tr><th colspan="4">Dep. Occurrence%</th><th rowspan="2">ILP</th><th colspan="4">Dep. Occurrence%</th><th rowspan="2">ILP</th><th colspan="4">Dep. Occurrence%</th><th rowspan="2">ILP</th><th colspan="4">Dep. Occurrence%</th></tr><tr><th>0</th><th>1</th><th>2</th><th>3+</th><th>0</th><th>1</th><th>2</th><th>3+</th><th>0</th><th>1</th><th>2</th><th>3+</th><th>0</th><th>1</th><th>2</th><th>3+</th></tr></thead><tbody><tr><td>adpcm dec</td><td>1.77</td><td>60.6</td><td>35.2</td><td>4.1</td><td>0</td><td>2.28</td><td>50.3</td><td>37.7</td><td>9.6</td><td>2.3</td><td>2.93</td><td>64</td><td>33</td><td>3</td><td>0</td><td>3.31</td><td>76.075</td><td>22.5</td><td>1.425</td><td>0</td></tr><tr><td>adpcm enc</td><td>1.82</td><td>58.7</td><td>35.9</td><td>4.9</td><td>0.5</td><td>2.41</td><td>48.6</td><td>39</td><td>9</td><td>3.3</td><td>3.04</td><td>63.05</td><td>32</td><td>4.05</td><td>0.9</td><td>3.44</td><td>68.6</td><td>26.675</td><td>4.725</td><td>0</td></tr><tr><td>bcnt</td><td>2.49</td><td>36</td><td>54</td><td>10</td><td>0</td><td>3.62</td><td>27</td><td>43.5</td><td>5.1</td><td>24.3</td><td>4.91</td><td>55.1</td><td>37.6</td><td>3.9</td><td>3.35</td><td>7.4</td><td>56.9</td><td>23.45</td><td>19.65</td><td>0</td></tr><tr><td>dct</td><td>2.22</td><td>53.9</td><td>30.1</td><td>7.7</td><td>8.3</td><td>3.31</td><td>45.4</td><td>28.1</td><td>7.1</td><td>19.4</td><td>4.62</td><td>50.55</td><td>20.7</td><td>18.95</td><td>9.85</td><td>4.91</td><td>60.525</td><td>30.9</td><td>7.975</td><td>0.625</td></tr><tr><td>fft32x32s</td><td>2.85</td><td>62.6</td><td>17.2</td><td>20.2</td><td>0</td><td>4.19</td><td>60.8</td><td>6.8</td><td>6.5</td><td>26</td><td>5.3</td><td>51.7</td><td>32</td><td>5.85</td><td>10.45</td><td>6.37</td><td>58.175</td><td>31.35</td><td>10.475</td><td>0</td></tr><tr><td>huff ac dec</td><td>1.51</td><td>59.9</td><td>36.1</td><td>3.6</td><td>0.5</td><td>1.75</td><td>40.7</td><td>50.7</td><td>7.9</td><td>0.7</td><td>2.14</td><td>70</td><td>29.75</td><td>0.2</td><td>0</td><td>2.17</td><td>84.075</td><td>15.925</td><td>0</td><td>0</td></tr><tr><td>motion</td><td>1.94</td><td>57</td><td>29.1</td><td>11.6</td><td>2.3</td><td>2.39</td><td>47.1</td><td>30</td><td>18.6</td><td>4.3</td><td>2.84</td><td>57.95</td><td>39.2</td><td>2.85</td><td>0</td><td>2.86</td><td>78.575</td><td>21.425</td><td>0</td><td>0</td></tr><tr><td>fir</td><td>2.09</td><td>62.3</td><td>29.8</td><td>7.9</td><td>0</td><td>2.5</td><td>51.6</td><td>36.8</td><td>11.6</td><td>0</td><td>2.55</td><td>77.75</td><td>22.25</td><td>0</td><td>0</td><td>2.56</td><td>83.15</td><td>16.85</td><td>0</td><td>0</td></tr><tr><td>crc</td><td>1.76</td><td>29.8</td><td>65.6</td><td>4.5</td><td>0.1</td><td>1.8</td><td>28.2</td><td>64.8</td><td>6.9</td><td>0.1</td><td>1.89</td><td>70.85</td><td>29.15</td><td>0</td><td>0</td><td>1.89</td><td>86.55</td><td>13.45</td><td>0</td><td>0</td></tr><tr><td>matrix mul</td><td>2.61</td><td>51.5</td><td>32.2</td><td>16.4</td><td>0</td><td>4.46</td><td>21.1</td><td>62.7</td><td>16.2</td><td>0</td><td>5.58</td><td>41.1</td><td>58.9</td><td>0</td><td>0</td><td>5.6</td><td>63.675</td><td>36.325</td><td>0</td><td>0</td></tr><tr><td>Average</td><td>2.15</td><td>53.1</td><td>36.1</td><td>9.75</td><td>1.06</td><td>2.85</td><td>42.9</td><td>39.3</td><td>10.4</td><td>7.31</td><td>3.57</td><td>60.205</td><td>33.455</td><td>3.88</td><td>2.455</td><td>4.041</td><td>71.63</td><td>23.885</td><td>4.425</td><td>0.1</td></tr></tbody></table>

stalling the pipeline.

<caption>Table 8: Area and delay of intra-cluster components.</caption>

## 5.3 Intra-cluster Dynamic Mechanism

### 5.3.1 Analysis of mechanism components

Table 8 presents the area and the delay of each component of the proposed dynamic mechanism. The switches dominate the additional area inserted by the proposed mechanism (76.2% of the total area overhead). It should be clarified that such switches are required by any approach that performs dynamic instruction scheduling. However, it should be stressed that the proposed implementation of the voting switches results in significantly less area overhead than the original switch implementations, as presented in Section 3.1.2 and depicted in Table 5. The voters contribute to 9.7% of the area overhead. Voters and detectors are required by any fault tolerant approach to compare redundant instructions. Then, the specific control components, inserted by the proposed approach, contribute to the remaining 14.2%. Concerning the delay, the processor frequency is affected only by the components inserted inside the VLIW pipeline (*replication switch* in the DC stage with 0.16 ns) and *voting switch* and *voters* in the EX/M-WB stage with 0.33 ns and 0.27 ns, respectively). For the control parts, the largest observed delay is 2.19 ns for the *replication scheduler*, which, however, does not affect the clock frequency, since the critical path is given by the EX/M-WB stage and is equal to 2.62 ns.

<table><thead><tr><th rowspan="2">Component</th><th colspan="3">Area</th><th rowspan="2">Delay (ns)</th></tr><tr><th>No. cells</th><th>%</th><th>%of total CPU</th></tr></thead><tbody><tr><td>Replication Switch</td><td>3,917.78</td><td>18.9</td><td>6.24</td><td>0.16</td></tr><tr><td>Voting Switch</td><td>11,891.57</td><td>57.3</td><td>18.93</td><td>0.33</td></tr><tr><td>Voters</td><td>2,007.68</td><td>9.7</td><td>3.20</td><td>0.27</td></tr><tr><td>Info extr. unit</td><td>88.13</td><td>0.4</td><td>0.14</td><td>0.12</td></tr><tr><td>Dep. Analyzer</td><td>303.55</td><td>1.5</td><td>0.48</td><td>0.13</td></tr><tr><td>Replic. scheduler</td><td>1,720.78</td><td>8.3</td><td>2.74</td><td>2.19</td></tr><tr><td>Voting scheduler</td><td>822.85</td><td>4.0</td><td>1.31</td><td>1.36</td></tr></tbody></table>

### 5.3.2 Performance

**Execution cycles** Table 9 depicts the execution cycles required to execute the benchmarks for the 4-issue configuration for all approaches. These values provide the impact on execution time, when all approaches are using the same frequency. We compute the Overhead (O) of TMR-S and TMR-S+T+CB, compared to the original/TMR-3FUs versions, and the Speed-Up (SU) of TMR-S+T+CB compared to TMR-S. The SU metric shows the impact on performance, when the scheduling window is extended from the current to the next instruction bundle. The overhead of TMR-S is similar among most of the benchmarks (except *crc* benchmark), with an average of 152.95%. The overhead of TMR-S+T+CB depends on the benchmark. The minimum overhead is 21.34% (*huff\_ac\_dec* benchmark) up to 139.16% (*matrix\_mul* benchmark), with an average of 77.52%. Last, but not least, the speed-up of TMR-S+T+CB compared to TMR-S.
S is from 13.47% (*matrixMul* benchmark) up to 43.68% (*huffAcDec* benchmark), with an average of 29.93%.

Note that the low number of execution cycles in some of the benchmarks is due to the following factors: a) the compiler schedules instructions in parallel to exploit as many idle slots as possible and, b) the architectures use a scratchpad memory with memory access of 1 cycle.

<table><caption>Table 9: Execution cycles (1 × 4-issue).</caption><thead><tr><th rowspan="2"></th><th rowspan="2">Orig./TMR-3FUs</th><th colspan="2">TMR-S</th><th colspan="2">TMR-S+CB</th></tr><tr><th>Cycles</th><th>O (%)</th><th>Cycles</th><th>O (%)</th></tr></thead><tbody><tr><td>adpcm_dec</td><td>386</td><td>998</td><td>158.55</td><td>613</td><td>58.81</td></tr><tr><td>adpcm_enc</td><td>409</td><td>1,066</td><td>160.64</td><td>652</td><td>59.41</td></tr><tr><td>bcnt</td><td>478</td><td>1,264</td><td>164.44</td><td>976</td><td>104.19</td></tr><tr><td>dct</td><td>1,288</td><td>3,779</td><td>193.40</td><td>2,404</td><td>86.65</td></tr><tr><td>fft32x32s</td><td>569</td><td>1,654</td><td>190.69</td><td>1,282</td><td>125.31</td></tr><tr><td>huff Ac dec</td><td>1,101</td><td>2,372</td><td>115.44</td><td>1,336</td><td>21.34</td></tr><tr><td>motion</td><td>344</td><td>821</td><td>138.66</td><td>546</td><td>63.95</td></tr><tr><td>fir</td><td>6,852</td><td>16,890</td><td>146.50</td><td>11,714</td><td>70.96</td></tr><tr><td>crc</td><td>12,228</td><td>22,601</td><td>84.83</td><td>17,823</td><td>45.76</td></tr><tr><td>matrixMul</td><td>11,142</td><td>30,795</td><td>176.39</td><td>26,647</td><td>139.16</td></tr><tr><td>Average</td><td></td><td></td><td>152.95</td><td></td><td>77.55</td></tr></tbody></table>

**Maximum frequency** The insertion of components to the VLIW datapath, in order to provide fault tolerance capabilities, increases the critical path. The upper part of Table 10 provides the critical path and the overhead (O), compared to the unprotected original processor. The critical path in all approaches is

<table><caption>Table 10: Execution time at maximum frequency (1 × 4-issue).</caption><thead><tr><th rowspan="2"></th><th rowspan="2">Orig.</th><th colspan="2">TMR-3FUs</th><th colspan="2">TMR-S</th><th colspan="2">TMR-S+CB</th></tr><tr><th>[ns]</th><th>[ns]</th><th>O (%)</th><th>[ns]</th><th>O (%)</th><th>[ns] and [O (%)]</th><th>Delay ^2</th></tr></thead><tbody><tr><td>Critical path</td><td>2.62</td><td>2.88</td><td>9.92</td><td>3.22</td><td>22.09</td><td>3.22</td><td>22.09</td></tr><tr><td>adpcm_dec</td><td>1,011.32</td><td>1,111.68</td><td>9.92</td><td>3,213.56</td><td>217.76</td><td>1,973.86</td><td>95.18</td><td>38.58</td></tr><tr><td>adpcm_enc</td><td>1,071.58</td><td>1,177.92</td><td>9.92</td><td>3,432.52</td><td>220.32</td><td>2,099.41</td><td>95.92</td><td>38.84</td></tr><tr><td>bcnt</td><td>1,252.36</td><td>1,376.64</td><td>9.92</td><td>4,070.08</td><td>224.99</td><td>3,142.09</td><td>99.99</td><td>38.99</td></tr><tr><td>dct</td><td>3,377.56</td><td>3,709.44</td><td>9.92</td><td>12,168.38</td><td>260.59</td><td>7,740.88</td><td>129.39</td><td>36.39</td></tr><tr><td>fft32x32s</td><td>1,490.78</td><td>1,638.72</td><td>9.92</td><td>5,325.88</td><td>257.25</td><td>4,128.01</td><td>116.90</td><td>22.39</td></tr><tr><td>huff Ac dec</td><td>2,884.62</td><td>3,170.88</td><td>9.92</td><td>7,637.84</td><td>164.78</td><td>4,301.00</td><td>100.00</td><td>39.00</td></tr><tr><td>motion</td><td>901.28</td><td>990.72</td><td>9.92</td><td>2,643.62</td><td>193.32</td><td>1,816.08</td><td>101.00</td><td>38.00</td></tr><tr><td>fir</td><td>17,952.24</td><td>19,733.36</td><td>9.92</td><td>54,385.8</td><td>202.95</td><td>37,719.08</td><td>110.11</td><td>30.65</td></tr><tr><td>crc</td><td>32,037.36</td><td>35,216.64</td><td>9.92</td><td>72,775.22</td><td>127.16</td><td>57,396.00</td><td>180.00</td><td>39.00</td></tr><tr><td>matrixMul</td><td>29,192.04</td><td>32,088.96</td><td>9.92</td><td>99,159.9</td><td>239.68</td><td>85,802.34</td><td>193.00</td><td>39.00</td></tr><tr><td>Average</td><td></td><td></td><td>9.92</td><td></td><td>210.18</td><td></td><td></td><td>18.20</td></tr></tbody></table>

given by the EX/M-WB stage. The delay impact of the TMR-3FUs approach is 0.27 ns due to the need to insert voters for comparison in this stage. The delay impact of TMR-S and TMR-S+CB approaches is increased to 0.33 ns due to the voting switch required to correctly group the results for comparison. The replication switch is placed in the DC stage and does not increase the critical path. Then, the lower part of Table 10 depicts the worst case impact in execution time (in ns) for the different benchmarks, when each approach runs with its maximum possible frequency for the 4-issue configuration. TMR-3FUs has the least impact in execution time, i.e., on averaged.

### 5.3.3.14 Area and Power

Table 11 depicts the inserted area (number of required cells) and the power (in mW) results, compared to the unprotected original version. The TMR-3FUs approach has the maximum area and power, i.e., 44.60% and 35.96%, respectively. The TMR-S has the lower overhead, with an area increase of 15.56% and a power increase of 23.61%. The TMR-S+CB, compared to the unprotected processor, has an area increase of 23.54% and a power overhead of 32.87%.

### 5.3.4 Overall hardware architecture comparison

Table 11 also depicts the Power×Delay×Area (PDA) Delay ^2 products of the different hardware architectures. The power is based on static activity and the delay on the maximum frequency. The PDA architecture can achieve that the TMR-3FUs has the highest overhead, mainly due to the area overhead. TMR-S has a higher PDA than TMR-S, because it has a smaller power and area increase, in order to reduce the execution cycles of the benchmarks.
has the lowest overhead, making TMR-3FUs the best candidate when performance is the most important metric, sacrificing area and power. Although TMR-S+T+CB has the largest PD^2 overhead as architecture, this approach significantly reduces the number of cycles, compared to TMR-S. Taking into account also the time required to execute the benchmarks, the estimated average PD^2 for all benchmarks is 50% less compared with TMR-S.

<table><caption>Table 11: Area, Power, PDA and PD^2 product results (1 × 4-issue).</caption><thead><tr><th rowspan="2">Approach</th><th colspan="2">Area</th><th colspan="2">Power</th><th colspan="2">PDA</th></tr><tr><th>Cells</th><th>O(%)</th><th>mW</th><th>O(%)</th><th>mW*ns*cells</th><th>O(%)</th></tr></thead><tbody><tr><td>Original</td><td>50,844</td><td>-</td><td>6.48</td><td>-</td><td>863209</td><td>-</td></tr><tr><td>TMR-3FUs</td><td>73,523</td><td>44.60</td><td>8.81</td><td>35.96</td><td>1865484</td><td>116</td></tr><tr><td>TMR-S</td><td>58,819</td><td>15.68</td><td>8.01</td><td>23.61</td><td>1517071</td><td>76</td></tr><tr><td>TMR-S+T+CB</td><td>62,812</td><td>23.54</td><td>8.61</td><td>32.87</td><td>1741412</td><td>102</td></tr></tbody></table>

# 5.4 Cluster-based approach

## 5.4.1 Impact of clustering

First of all, we quantify how much the clustering impacts the proposed approach. To achieve that, we compare the obtained results of the proposed approach between 1 × 8-issue and 2 × 4-issue configurations. Regarding area, we estimate that the voting switch for 1 × 8-issue configuration requires 49,730 cells, leading to, at least, a total area 129,391 cells, increasing the critical path by 0.11 ns. This area overhead (62.43%) between the voting switch for 1 × 8-issue and 1 × 4-issue motivated the proposal of the cluster-based approach. Table 12 compares the number of execution cycles required to execute the benchmarks. The proposed cluster-based approach TRADE-offs performance improvement and area overhead, providing fault tolerance capabilities.

<table><caption>Table 12: Execution cycles of TMR-S+T+CB (1 × 8-issue and 2 × 4-issue).</caption><thead><tr><th>Benchmark</th><th>2 × 4 VLIW</th><th>1 × 8 VLIW</th><th>Overhead (%)</th></tr></thead><tbody><tr><td>adpcm_dec</td><td>443</td><td>388</td><td>14.18</td></tr><tr><td>adpcm_enc</td><td>493</td><td>426</td><td>15.73</td></tr><tr><td>bcnt</td><td>700</td><td>555</td><td>26.13</td></tr><tr><td>dct</td><td>1,623</td><td>1,519</td><td>6.85</td></tr><tr><td>fft32x32s</td><td>856</td><td>722</td><td>18.56</td></tr><tr><td>huff_ac_dec</td><td>1,090</td><td>1,029</td><td>5.93</td></tr><tr><td>motion</td><td>383</td><td>367</td><td>4.36</td></tr><tr><td>fir</td><td>8,291</td><td>6,969</td><td>18.97</td></tr><tr><td>crc</td><td>14,745</td><td>11,986</td><td>23.02</td></tr><tr><td>matrixMul</td><td>14,053</td><td>12,196</td><td>15.23</td></tr><tr><td>Average</td><td></td><td></td><td>14.89</td></tr></tbody></table>

## 5.4.2 Performance

Table 13 depicts the execution cycles for two, four and eight clusters, i.e., 2 × 4-issue, 4 × 4-issue and 8 × 4-issue. For the 2 × 4-issue configuration, TMR-S has an average overhead of 102.01% and TMR-S+T+CB of 69.31%, compared to the original version. These overheads are reduced to 51.27% and 32.36% respectively, for the 4 × 4-issue configuration, 102 and 89.17% and 13.60%, respectively, for the 8 × 4-issue configuration. Regarding the speed-up of TMR-S+T+CB compared to TMR-S, the average speed-up is 19.84% for the 2 × 4-issue configuration, 11.65% for the 4 × 4-issue configuration and 9.26% for the 8 × 4-issue configuration. Overall, as the number of issues is increased, the obtained speed-up, compared to the TMR-S, and the overhead compared, to the original VLIW, are decreased. This behaviour is explained due to the low application ILP and the large number of idle issues. In several cases, the instruction replication is done within the current bundle, explored by both TMR-S and TMR-S+T+CB.

We observe that, in general, the speed-up of the single cluster is slightly higher compared to the speed-up of the configuration with two or more clusters. This behavior is explained due to:

1. The average ILP, compiled for the two-or-more cluster configuration, is low and, thus, there are more idle issues in the current bundle than the idle issues of the single cluster configuration. These are exploited by both TMR-S+T+CB and TMR-S. When the instructions are triplicated, the threshold (after which we need to add an extra time slot) is one instruction (for the single-cluster configuration), two instructions (for the two-cluster configuration), etc. For the single cluster, the ILP is almost 2, and thus, additional time slots are
<table><caption>Table 13: Execution cycles (2 × 4-issue, 4 × 4-issue and 8 × 4-issue).</caption><thead><tr><th rowspan="3"></th><th colspan="6">2 x 4-issue</th><th colspan="6">4 x 4-issue</th><th colspan="6">8 x 4-issue</th></tr><tr><th colspan="2">Orig.</th><th colspan="3">TMR-S</th><th colspan="3">TMR-S+T+CB</th><th colspan="2">Orig.</th><th colspan="3">TMR-S</th><th colspan="3">TMR-S+T+CB</th><th colspan="2">Orig.</th><th colspan="3">TMR-S</th><th colspan="3">TMR-S+T+CB</th></tr><tr><th>Cycles</th><th>Cycles</th><th>O (%)</th><th>Cycles</th><th>O (%)</th><th>SU (%)</th><th>Cycles</th><th>Cycles</th><th>O (%)</th><th>Cycles</th><th>O (%)</th><th>SU (%)</th><th>Cycles</th><th>Cycles</th><th>O (%)</th><th>Cycles</th><th>Cycles</th><th>Cycles</th><th>O (%)</th><th>Cycles</th><th>O (%)</th><th>SU (%)</th></tr></thead><tbody><tr><td>adpcm dec</td><td>302</td><td>612</td><td>102.65</td><td>443</td><td>46.69</td><td>27.61</td><td>258</td><td>385</td><td>49.22</td><td>309</td><td>19.77</td><td>19.74</td><td>232</td><td>292</td><td>25.86</td><td>248</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>adpcm enc</td><td>323</td><td>662</td><td>104.95</td><td>493</td><td>52.63</td><td>25.53</td><td>280</td><td>413</td><td>47.50</td><td>344</td><td>22.86</td><td>16.71</td><td>252</td><td>317</td><td>25.79</td><td>273</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>bcnt</td><td>333</td><td>764</td><td>129.43</td><td>700</td><td>110.21</td><td>8.38</td><td>252</td><td>483</td><td>91.67</td><td>421</td><td>67.06</td><td>12.84</td><td>171</td><td>288</td><td>68.42</td><td>231</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>dct</td><td>872</td><td>2,144</td><td>145.87</td><td>1,623</td><td>86.12</td><td>24.30</td><td>670</td><td>1,118</td><td>66.87</td><td>999</td><td>49.10</td><td>10.64</td><td>636</td><td>811</td><td>27.52</td><td>718</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>fft32x32s</td><td>400</td><td>1,006</td><td>151.50</td><td>856</td><td>114.00</td><td>14.91</td><td>332</td><td>653</td><td>96.69</td><td>523</td><td>57.53</td><td>19.91</td><td>280</td><td>377</td><td>34.64</td><td>335</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>huff ac dec</td><td>951</td><td>1,525</td><td>60.36</td><td>1,090</td><td>14.62</td><td>28.52</td><td>925</td><td>1,025</td><td>10.81</td><td>966</td><td>4.43</td><td>5.76</td><td>912</td><td>938</td><td>2.85</td><td>917</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>motion</td><td>280</td><td>500</td><td>78.57</td><td>383</td><td>36.79</td><td>23.40</td><td>253</td><td>326</td><td>28.85</td><td>284</td><td>12.25</td><td>12.88</td><td>251</td><td>277</td><td>10.36</td><td>263</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>fir</td><td>6,709</td><td>10,877</td><td>62.13</td><td>8,291</td><td>23.58</td><td>23.77</td><td>6,007</td><td>7,031</td><td>17.05</td><td>6,728</td><td>12.00</td><td>4.31</td><td>6,007</td><td>6,549</td><td>9.02</td><td>6,247</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>crc</td><td>11,955</td><td>15,962</td><td>33.52</td><td>14,745</td><td>23.34</td><td>7.62</td><td>11,699</td><td>12,215</td><td>4.41</td><td>11,971</td><td>2.32</td><td>2.00</td><td>11,699</td><td>11,955</td><td>2.19</td><td>11,699</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>matrix mul</td><td>6,533</td><td>16,408</td><td>151.16</td><td>14,053</td><td>115.11</td><td>14.35</td><td>5,236</td><td>10,453</td><td>99.64</td><td>9,227</td><td>76.22</td><td>11.73</td><td>5,236</td><td>8,116</td><td>55.00</td><td>7,532</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>Average</td><td></td><td></td><td>102.01</td><td></td><td></td><td>62.31</td><td>19.84</td><td></td><td></td><td>51.27</td><td></td><td>32.36</td><td>11.65</td><td></td><td></td><td>13.60</td><td></td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>

<table><caption>Table 14: Area, Power, PDA and PD^2 product results (measurement method: (+) complete design, (†) all additional components, (*) estimation).</caption><thead><tr><th rowspan="2">Approach</th><th colspan="4">2 x 4-issue</th><th colspan="4">4 x 4-issue</th><th colspan="4">8 x 4-issue</th></tr><tr><th>Area</th><th>Power</th><th>PDA</th><th>PD^2</th><th>Area</th><th>Power</th><th>PDA</th><th>PD^2</th><th>Area</th><th>Power</th><th>PDA</th><th>PD^2</th></tr></thead><tbody><tr><td>Original (+)</td><td>79.661</td><td>124.137</td><td>55.83</td><td>7.36</td><td>1,536.119</td><td>198.610</td><td>13.94</td><td>3235.581</td><td>12.84</td><td>8.436.305</td><td>58.14</td><td>19.2</td></tr><tr><td>TMR-3FUs (+)</td><td>79.661</td><td>124.137</td><td>55.83</td><td>11.88</td><td>4,247.273</td><td>229.889</td><td>68.28</td><td>18.38</td><td>103.22</td><td>12.169.036</td><td>36.1</td><td>257.29</td></tr><tr><td>TMR-S (*)</td><td>95.258</td><td>19.58</td><td>9.03</td><td>22.69</td><td>2,769.779</td><td>95</td><td>95</td><td>13.13</td><td>15.26</td><td>7.118.871</td><td>120</td><td>21.225.022</td></tr><tr><td>TMR-S+T+CB (†)</td><td>103.598</td><td>30.05</td><td>9.77</td><td>32.74</td><td>3,259.131</td><td>112</td><td>101.30</td><td>101</td><td>184.484</td><td>35.05</td><td>13.73</td><td>51.85</td><td>8.156.148</td><td>152</td><td>23.800.101</td><td>182</td><td>221.16</td></tr></tbody></table>

needed in most cases. However, for two clusters, the ILP is almost 3, decreasing the probability of needing an extra time slot. For instance, the *crc* benchmark has the lowest speed-up in the two-cluster configuration, because the *crc* ILP changes slightly from the single-cluster to the two-cluster configuration and that is due to its high amount of one dependency occurrences. Hence, the required idle slots are available in the current bundle (both approaches explore them).

2. The application's code structure. For instance, an application with consecutive bundles without NOPs has similar behavior in both TMR-S and TMR-S+T+CB, since no idle slots exist to exploit. Such an example is *matrixMul*, which achieves the lowest speed-up for the single-cluster case.

3. A high number of dependencies. If idle slots exist in next bundle, but instructions are dependent, they cannot be exploited. However, there are usually less than two dependent instructions (see Table 7). Thus, the remaining independent instructions can use the idle slots. That is why the

*crc* benchmark (for single cluster) has high performance speed-up, even though 70% of the bundles have one or two dependent instructions.

### 5.4.3 Area and Power

Table 14 depicts the area and power for two, four and eight clusters (i.e., 2 × 4-issue, 4 × 4-issue and 8 × 4-issue), compared to the unprotected original version. For the original and the TMR-3FUs, the complete design has been implemented. For the TMR-S and TMR-S+T+CB, the additional components have been synthesized, all together, and added to the original design area/power. Estimated area and power results are provided for the TMR-S, based on the fact that TMR-S needs replication and voting switches, voters, simpler scheduling logic and no shadow registers. As the number of issues is increased, the area and power of the approaches are also increased. For the 8 × 4-issue configuration, the TMR-3FUs approach has the maximum area overhead of 73.56% and a power overhead of 141.60%. On the contrary, the TMR-S+T+CB, compared to the unprotected pro-
cessor, has an area overhead of 38.18% and a power overhead of to 66.09%. This overhead is ~ 50% less than the TMR-3FUs and ~ 10% more than the TMR-S. The TMR-S has the lower overhead, with an area increase of 26.80% and a power increase of 61.45%.

### 5.4.4 Overall architecture comparison

Table 14 depicts Power×Delay×Area (PDA) and the Power×Delay^2 products for two, four and eight clusters (i.e., 2 × 4-issue, 4 × 4-issue and 8 × 4-issue), compared to the unprotected original version. Similar to the 1x4-issue, the PDA product shows that the TMR-3FUs has the highest overhead, while the TMR-S+T+CB has higher PDA than TMR-S. The PD^2 product shows that, as the number of issues is increased, the PD^2 overhead is also increased for TMR-3FUs, strengthening the fact that a significant power penalty has to be paid in order to get the best possible performance. TMR-S+T+CB has bigger PD^2 overhead than TMR-S as an architecture. However, TMR-S+T+CB significantly reduces the number of execution cycles of the benchmarks. The estimated average PD^2 for all the benchmarks is reduced 33%, 26% and 23% in comparison with TMR-S for the 2 × 4-issue, 4 × 4-issue and 8 × 4-issue configurations, respectively.

## 5.5 Instruction Reliability Factor

In this work, we check the complete ISA of the VLIW by performing reliability measurements at the instruction level. We compute the Instruction Reliability Factor (IRF) for the original and the TMR-S+T+CB VLIW, defined as the probability of a fault in a processor's register to not lead to an error in the instruction output. IRF depicts the impact of a fault occurring in FtoDC, DCtoEx, Register File and PC. The IRFs of TMR-3FUs, TMR-S, TMR-S+T+CB are the same, they have the same protection sphere and apply instruction triplication.

To compute the IRF, the VLIW processors are extended with fault injection capabilities. We perform an exhaustive fault injection campaign at the microarchitecture level, for all valid opcodes of the Instruction Set Architecture (ISA) of VLIW processor. For

each opcode, we flip all the bits of a pipeline register and all pipeline registers. For the input data of each instruction, we repeated the fault injection experiments 1,000 with random data. Hence, 14,100 total fault injections are performed per instruction (1,000 × 141 bits), which corresponds to confidence interval of 98.25%, considering an error margin of 0.01% [19]. For each experiment, a fault-free execution is performed to obtain the golden references. Then, a fault is injected by flipping one bit of a pipeline register. The process is repeated for all bits within a register and for all pipeline registers. After comparing the output with the golden reference, the result is categorized as: (i) Crash, the execution finishes unexpectedly, an exception is raised and the processor crashes; (ii) Correct, the instruction output and the processor state (registers, stack memory, PC, etc.) match the golden references; (iii) Output mismatch, the instruction output does not match the golden reference (but the processor state does); (iv) Processor state failure, the processor state does not match the golden reference (but instruction output does). Depending on this output, the bit where the fault is injected is categorized as Correct Instruction Output (CIO) (Cases ii and iv) and Faulty Instruction Output (FIO) (Cases i and iii). Then, the IRF<sub>i</sub> in pipeline stage i is:

$$IRF_i = \frac{\text{CIO bits of pipeline register i}}{\text{Total bits of processor pipeline registers}} \quad (2)$$

Table 15 depicts the average IRF among similar instructions. The most vulnerable instructions of the original unprotected processor are the arithmetic and logic operations. With TMR-S+T+CB, they become up to 2.2x less vulnerable, compared to the original processor. The IRFs depend on the fault tolerance approach used (triplication) and the comparison that the voter performs (data result). As an exhaustive fault injection takes place, faults are inserted in other fields of the instruction than the data. Thus, IRFs are increased, but they are not equal to 1. This is due to the fact that the voters compare only the arithmetic result of the logical/arithmetic operations (FU result field in Table 2). If the voters are extended to check errors in the opcode and destination registers, instead
<table><caption>Table 15: Average IRF per instruction group.</caption><thead><tr><th>Opcode</th><th>Orig.</th><th>Prop.</th><th>Opcode</th><th>Orig.</th><th>Prop.</th></tr></thead><tbody><tr><td colspan="3"><strong>Logic Operations</strong></td><td colspan="3"><strong>Arithmetic Operations</strong></td></tr><tr><td>CMPx</td><td>0.832</td><td>0.974</td><td>MPYx</td><td>0.707</td><td>0.974</td></tr><tr><td>CMPxi</td><td>0.899</td><td>0.974</td><td>ADD/SUB</td><td>0.447</td><td>0.974</td></tr><tr><td>AND/OR/NORx</td><td>0.667</td><td>0.974</td><td>ADD/SUBi</td><td>0.445</td><td>0.974</td></tr><tr><td>ANDC/ORCx</td><td>0.734</td><td>0.978</td><td>SHx</td><td>0.762</td><td>0.974</td></tr><tr><td>NOTx</td><td>0.679</td><td>0.974</td><td>SHxi</td><td>0.765</td><td>0.974</td></tr><tr><td>XORx</td><td>0.447</td><td>0.974</td><td>SHADD</td><td>0.456</td><td>0.974</td></tr><tr><td colspan="3"><strong>Memory Operations</strong></td><td colspan="3"><strong>SHADDi</strong></td></tr><tr><td>LDx</td><td>0.442</td><td>0.973</td><td>EXT</td><td>0.699</td><td>0.974</td></tr><tr><td>STx</td><td>0.346</td><td>0.975</td><td>EXTi</td><td>0.778</td><td>0.980</td></tr><tr><td colspan="3"><strong>Control Operations</strong></td><td colspan="3"><strong>MOVI</strong></td></tr><tr><td>BR/CALL/RT</td><td>1.000</td><td>1.000</td><td>NOP</td><td>0.950</td><td>1.000</td></tr><tr><td>CALLR/GOTOR</td><td>1.000</td><td>1.000</td><td></td><td></td><td></td></tr><tr><td>BRF</td><td>1.000</td><td>1.000</td><td></td><td></td><td></td></tr><tr><td>STOP</td><td>1.000</td><td>1.000</td><td></td><td></td><td></td></tr></tbody></table>

of only the output results, the IRF would be close to 1. This extension is estimated to increase the size of the voters by approximately 22%. The delay is expected to be almost unaffected since the comparisons will occur in parallel. Note that, NOPs are never replicated in our design. Their IRF is improved due to the fact that TMR-S+T+CB uses a flag (sel_v), which is set by the Voting scheduler only when three instances of the same instruction are ready for commit. Hence, when a NOP is "executed", no instruction is committed. For this reason, NOPs never passes to the commit stage, and, in the IRF calculation, these faults are always masked.

## 5.6 Reliability of introduced hardware mechanisms

The probability of radiation hitting the hardware components, and thus introducing transients, depends on the component area. Thus, the larger the area the more possible it is for an exposed component to be affected by transient faults. In the proposed approach, the voting and replication switches have the biggest area among all added components, i.e. 76,2% of the proposed approach (and 25.17% of the total processor) as shown in Table 8. However, faults occurring in these hardware components are mitigated. Faults in the voting and replication switches will be detected by the voters, since faults will affect either the values passed to the voters or mix the values that will be voted. Therefore, the

critical part of the proposed approach is the voters (3.20% area of the processor) which is the case for all fault tolerant approaches. Another part that is critical for the proposed approach is the scheduling (i.e. the replication and voting schedulers, the info extraction unit and the dependency analyser). If a fault occurs in this part, the pipeline may be corrupted and wrong instructions may be issued. However, all of these components occupy around 14% of the mechanisms inserted by the proposed approach (4.67% of the processor). In this work, we do not present any countermeasures for these critical components, since their area is small compared to the overall design, and thus, the probability of radiation affecting this part is low. A typical countermeasure that can be applied is to triplicate the critical parts, since they have low area overhead. Last, error correction codes is required as well for the register file and the memory, and this is an assumption for all the analysed approaches of this study.

## 6 Further discussions and limitations

Regarding the target VLIW processor, the proposed approach has been implemented considering a baseline VLIW processor of a pipeline depth equal to 3. The baseline VLIW processor with heterogeneous FUs is inspired by commercial VLIWs having large pipelines, e.g., Intel Itanium [20], but it is a simplified version with small pipeline depth. Such an implementation provides the worst case delay that the proposed approach can insert, since no pipelined version of the schedulers can occur with this 3-stage baseline processor without modifying its pipeline. Note that, increasing the VLIW pipeline depth will not impact the functionality of the proposed approach, since it will still exploit two instruction bundles, regardless the pipeline depth of the processor. Exploiting larger instruction windows will insert high overhead. The proposed approach has as goal to combine the benefits of VLIW and dynamic scheduling keeping the overhead low. To achieve that, the size of the instruction window has to remain as low as possible.
ble, which, however, provides some important gains. From the benchmark analysis, we have seen that already a high percentage of instructions between the current bundle and the next bundle are independent. Thus, the replication of instructions of the current and next bundle creates enough instructions to fill the VLIW issues.

Regarding the VLIW processor frequency, the worst delay of the proposed approach is given by the replication and voting schedulers, which are placed in parallel to the decode and execution stage of the baseline VLIW processor. The current implementation can be applied to a processor up to 456 MHz, without affecting the processor pipeline. Note that, for processors achieving higher frequencies, larger pipeline depths are required. In this case, more stages exist, and thus, more opportunities are provided to optimise the proposed implementation, e.g., taking advantage of the processor pipeline stages in order to divide and also pipeline the schedulers.

Regarding the target applications, the proposed approach focuses on applications that allow the existence of idle slots during their execution. Hence, applications with high ILP limit the advantages of the proposed approach, since most of the slots are occupied by original instructions, and thus, the proposed approach degrades to a typical triple execution of instruction bundles. Note that, this is the case for any approach that exploits idle slots. However, as other benchmark analysis have shown, high ILPs are not common and the number of NOPs is usually significantly large [21].

# 7 Related Work

Static and dynamic approaches have been proposed to replicate instructions and execute them on idle FUs of VLIW processors, in order to provide fault tolerance.

Static approaches are usually implemented by software. They replicate and schedule the instructions at design-time and additional instructions are inserted for comparison of the results. For instance, the approach presented in [22, 23] applies full duplication and full comparison in the compiled code,

whereas the approach of [24] reduces the number of compared instructions. CASTED [25] proposes a compiler-based technique to distribute error detection overhead across core/clusters, which is applicable to tightly coupled cores and clustered VLIWs. Although static approaches do not require additional hardware, the code size, storage and energy consumption are increased. To reduce the additional instructions inserted in the code, approaches do not duplicate all instructions or implement the comparisons in hardware. For instance, a packing-oriented duplication is proposed, compared to the common sequential order, to maximize the number of duplicated instructions within the same performance overhead bound [26]. Instruction duplication and scheduling is performed by the compiler, while the comparison is performed by the hardware [27, 9]. In [28], the compiler encodes information in the instructions and a hardware mechanism decodes the information to runtime duplicate the instructions. In [13], instruction duplication and scheduling is done by the compiler and the comparison of results is done by the hardware. If an error is detected, the hardware adds a time slot and re-executes the instruction to another FU.

Dynamic approaches eliminate the need for high storage requirements and additional instructions. They are usually implemented through hardware that replicates and schedules the instructions during execution. A recent approach proposes dynamic recompilation, but this work addresses aging degradation [29]. Some dynamic approaches based on hardware avoid the need of dynamic scheduling. In [30, 10, 11], one-to-one coupling of the VLIW issues is applied, and thus, the duplicated instructions can use the schedule of the original instructions, given by the compiler. Partial instruction duplication is applied [30]. When no idle issue exists, the corresponding instruction is not duplicated. When an error is detected, instruction re-execution is applied. Full instruction duplication is applied in [10, 11]. When an instruction bundle has more instructions than the half of its issue-width, the bundle is divided into two, and a time slot is added. However, due to the lack of dynamic scheduling, there is a more-than-necessary negative impact on performance.
The remaining hardware dynamic approaches apply dynamic scheduling, assuming that VLIW issues include all FUs, thus can execute any instruction. However, when the VLIW consists of issues with different type of FUs, the existing schedulers are not applicable, as they ignore the type of FUs. To remove this limitation, existing approaches transform a heterogeneous VLIW to a homogeneous one, by inserting the missing FUs at each issue, e.g., [12]. With increasing number of VLIW issues and considering floating point FUs, these approaches lead to VLIW processors with significant area overhead. In [31, 32], the instructions are partitioned in groups in order their results to be directly compared after execution. However, one or two idle cycles are inserted for each instruction bundle. To reduce the negative impact, the use of spare FUs is explored.

Compared to the aforementioned approaches, this work proposes a hardware mechanism that replicates and schedules the instructions on heterogeneous VLIWs during execution, taking into account the number and the type of the FUs, and the algorithmic dependencies of the instructions, improving performance, while keeping area overhead low.

## 8 Conclusion

Due to application's ILP, the available resources of a VLIW processor are not always used. A cluster-based dynamic fault tolerant approach is proposed for heterogeneous VLIW data-paths. The intra-cluster hardware mechanism explores the idle slots in current bundle (space scheduling) and in the next bundle (time scheduling). To keep the hardware cost low, a hardware instruction scheduler is proposed. To enable scalability, a cluster-based approach is proposed, avoiding area and power overhead at the cost of a small decrease in performance. The processor behavior is explored with ten media benchmarks, with an average speed-up of 24.99% in performance and area and power overheads to be almost 10% with respect to existing approaches. Fault injection experiments show up to 2.2x instruction reliability improvement.

## References

[1] J. W. McPherson, Reliability challenges for 45nm and beyond, in: IEEE/ACM Design Automation Conference, 2006, pp. 176–181.

[2] P. Shivakumar, M. Kistler, S. W. Keckler, D. Burger, L. Alvisi, Modeling the effect of technology trends on the soft error rate of combinatorial logic, in: IEEE/IFIP Int'l Conf. Dependable Systems and Networks, 2002, pp. 389–398.

[3] R. C. Baumann, Radiation-induced soft errors in advanced semiconductor technologies, IEEE Transactions on Device and Materials Reliability 5 (3) (2005) 305–316. doi:10.1109/TDMR.2005.853449.

[4] T. Sudo, H. Sasaki, N. Masuda, J. L. Drewniak, Electromagnetic Interference (EMI) of System-on-Package (SOP), IEEE Transactions on Advanced Packaging 27 (2) (2004) 304–314. doi:10.1109/TADVP.2004.828817.

[5] V. Castano, I. Schagaev, Resilient Computer System Design, Springer Publishing Company, 2015.

[6] T. Heijmen, Radiation-induced soft errors in digital circuits – a literature survey (2002).

[7] J. Klecka, W. Bruckert, R. Jardine, Error self-checking and recovery using lock-step processor pair architecture, U.S. Patent 6,393,582 B1 (2002).

[8] G. A. Reis, J. Chang, N. Vachharajani, R. Rangan, D. I. August, Swift: Software implemented fault tolerance, in: Int'l Symp. Code Generation and Optimization, 2005, pp. 243–254.

[9] J. S. Hu, et al., Compiler-directed instruction duplication for soft error detection, in: IEEE/ACM Conference on Design, Automation & Test in Europe, 2005.

[10] A. L. Sartor, et al., Adaptive ilp control to increase fault tolerance for vliw processors, in: IEEE Int'l Conf. Application-specific Systems, Architectures and Processors, 2016, pp. 9–16.
[11] A. L. Sartor, et al., Exploiting idle hardware to provide low overhead fault tolerance for vliw processors, ACM Transactions on Journal on Emerging Technologies in Computing 13 (2) (2017) 13:1–13:21.

[12] A. L. Sartor, A. F. Lorenzon, S. Kundu, I. Koren, A. C. Beck, Adaptive and polymorphic vliw processor to optimize fault tolerance, energy consumption, and performance, in: ACM Int’l Conf. Computing Frontiers, 2018.

[13] M. Schözel, Hw/sw co-detection of transient and permanent faults with fast recovery in statistically scheduled data paths, in: IEEE/ACM Design, Automation and Test in Europe Conference, 2010, pp. 723–728.

[14] R. Psiakis, A. Kritikakou, O. Sentieys, NEDA: NOP Exploitation with Dependency Awareness for Reliable VLIW Processors, in: IEEE Computer Society Annual Symposium on VLSI, 2017, pp. 391–396. doi:10.1109/ISVLSI.2017.75.

[15] F. Anjam, S. Wong, Configurable fault-tolerance for a configurable vliw processor, in: Int’l Conf. Reconfigurable Computing: Architectures, Tools, and Applications, Springer-Verlag, 2013, p. 167–178.

[16] J. A. Fisher, P. Faraboschi, C. Young, Embedded computing: a VLIW approach to architecture, compilers and tools, Elsevier, 2005.

[17] C. Lee, et al., MediaBench: a tool for evaluating and synthesizing multimedia and communications systems, in: IEEE Int’l Symp. Microarchitecture, 1997, pp. 330–335.

[18] S. Rokicki, E. Rohou, S. Derrien, Hardware-accelerated dynamic binary translation, in: IEEE/ACM Conference on Design, Automation & Test in Europe, 2017, pp. 1062–1067.

[19] I. Tuzov, D. de Andrés, J. Ruiz, Accurate robustness assessment of hdl models through iterative statistical fault injection, in: European Dependable Computing Conference, 2018, pp. 1–8.

[20] H. Sharangpani, H. Arora, Itanium processor microarchitecture, IEEE MICRO 20 (5) (2000) 24–43.

[21] G. Li, Y. Hou, J. Zhu, An efficient and fast vliw compression scheme for stream processor, IEEE Access 8 (2020) 224817–224824.

[22] C. Bolchini, A software methodology for detecting hardware faults in vliw data paths, IEEE Transactions on Reliability 52 (4) (2003) 458–468. doi:10.1109/TR.2003.821935.

[23] D. M. Blough, A. Nicolau, Fault tolerance in super-scalar and vliw processors, in: IEEE Workshop on Fault-Tolerant Parallel and Distributed Systems, 1992, pp. 193–200.

[24] J. G. Holm, P. Banerjee, Low cost concurrent error detection in a vliw architecture using replicated instructions, in: Int’l Conf. Parallel Processing, 1992.

[25] K. Mitropoulou, V. Porpodas, M. Cintra, CASTED: Core-Adaptive Software Transient Error Detection for Tightly Coupled Cores, in: IEEE Int’l Parallel and Distributed Processing Symp., 2013.

[26] Y. Ko, S. Kim, H. Kim, K. Lee, Selective code duplication for soft error protection on vliw architectures, Electronics 10 (15) (2021).

[27] J. Hu, F. Li, V. Degalahal, M. Kandemir, N. Vijaykrishnan, M. J. Irwin, Compiler-assisted soft error detection under performance and energy constraints in embedded systems, ACM Transactions on Embedded Computing Systems 8 (4) (2009) 27:1–27:30. doi:10.1145/1550987.1550990.

[28] J. Lee, Y. Ko, K. Lee, J. M. Youn, Y. Paek, Dynamic code duplication with vulnerability awareness for soft error detection on vliw architecture, ACM Transactions on Architecture and Code Optimization 9 (4) (2013) 48:1–48:24.

[29] A. Rahimi, R. K. Gupta, Hardware/Software Codesign for Energy Efficiency and Robustness:
From Error-Tolerant Computing to Approximate Computing, Springer International Publishing, 2021, pp. 527–543.

[30] A. L. Sartor, et al., A novel phase-based low overhead fault tolerance approach for vliw processors, in: IEEE Computer Society Annual Symposium on VLSI, 2015, pp. 485–490.

[31] Y.-Y. Chen, et al., An integrated fault-tolerant design framework for vliw processors, in: IEEE Int'l Symp. Defect and Fault Tolerance in VLSI Systems, 2003, pp. 555–562.

[32] Y.-Y. Chen, K.-L. Leu, Reliable data path design of VLIW processor cores with comprehensive error-coverage assessment, Microprocessors and Microsystems: Embedded Hardware Design 34 (1) (2010) 49 – 61.