# Efficiency of Flexible Rerouting Scheme for Maximizing Logical Arrays

Guiyuan Jiang, Jigang Wu, Jizhou Sun

► To cite this version:

Guiyuan Jiang, Jigang Wu, Jizhou Sun. Efficiency of Flexible Rerouting Scheme for Maximizing Logical Arrays. 10th International Conference on Network and Parallel Computing (NPC), Sep 2013, Guiyang, China. pp.194-206, 10.1007/978-3-642-40820-5_17. hal-01513763

HAL Id: hal-01513763

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

Submitted on 25 Apr 2017

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
Efficiency of Flexible Rerouting Scheme for
Maximizing Logical Arrays

Guiyuan Jiang¹, Jigang Wu², and Jizhou Sun¹

¹ School of Computer Science & Technology, Tianjin University,
Tianjin 300072, China

² School of Computer Science & Software Engineering, Tianjin Polytechnic University, Tianjin 300387, China
{jguiyuan,asjgwu}@gmail.com, jzsun@tju.edu.cn

**Abstract.** In a multiprocessor array, some processing elements (PEs) fail to function normally due to hardware defects or soft faults caused by overheating, overload or occupancy by other running applications. Fault-tolerant reconfiguration considered in this paper is to reorganize fault-free PEs from a processor array with faults to a logical array of regular mesh topology by changing the interconnections among PEs. This paper presents the efficiency of the flexible rerouting scheme to maximize the usage of the fault-free PEs, by developing an efficient reconfiguration algorithm without backtracking. The proposed algorithm constructs each logical columns from left to right on candidate PE sets. It updates the candidate sets by excluding the PEs which cannot be used, once a logical column is formed. Also, it is proved that the proposed heuristic algorithm is able to generate the maximum-size logical array in linear time. Experimental results show that 123 logical columns can be constructed on 256 × 256 host arrays with fault density of 30%, resulting in an improvement of 51% in comparison to the previous algorithm by which only 82 logical columns can be produced. Furthermore, our algorithm is able to generate target arrays with harvest over 56% on host arrays with fault density of 50%, while the previous work cited in this paper fails to construct any target array in this case.

**Key words:** Interconnection network, reconfiguration, rerouting scheme, fault tolerant, algorithm.

# 1 Introduction

The quest for high-performance and low-power leads to design multi-core architectures where an increasing number of processing elements (PEs) are integrated on a single chip in a tightly coupled fashion. In order to fully exploit the processing capabilities offered by the integration of an increasing number of PEs, on-chip communication networks play a critical role in developing high-performance embedded computing system. The option of reconfiguring the interconnect topology using optical circuit switches, which are of low-cost, low-power and high-bandwidth, opens up new possibilities for improving not only the computing performance but also the reliability of multiprocessor systems.
To fully exploit the processing capabilities, many works have investigate
application-aware topology reconfiguration techniques which try to customize
the multiprocessor array to a topology that matches the traffic pattern of the
application in order to reduce the power consumption and message latency etc.
Optimizing network topology and mapping cores to network are two important
application-specific reconfiguration methods. Topology determines the connec-
tivity of the Network-on-Chip (NoC) nodes, while the core mapping tries to
place the processing cores communicating more frequently near each other. The
problem of topology selection and core mapping on NoC nodes have been ex-
plored to optimize an interconnection network based on a set of communication
constraints by many researchers [1][2]. Reconfiguring the topology on NoC to
reduce power consumption has been studied in [3]. And the work in [4] extends
the paper [3] by proposing a more flexible and efficient structure and by provid-
ing extensive evaluations to thoroughly investigate the power, latency, and area
of the reconfigurable NoC.

Since these fully customized topologies are designed and optimized for some
specific applications, they give the best performance and power results only for
that applications. The fault-tolerant reconfiguration considered in this paper is
to re-organize the fault-free PEs in the multiprocessor array to a regular topol-
ogy (standard structured) which ensuring well-controlled electrical parameters.
Generally, two distinct types of fault-tolerant approaches, i.e. the redundancy
approach and the degradation approach, are mostly investigated for processor ar-
ray reconfiguration. The redundancy approach tolerates faulty PEs by replacing
them with spare PEs [5][6], and if these PEs cannot replace all the faulty ones,
the chip has to be discarded. In degradation approach, [7] studied the problem
of 2D mesh reconfiguration under three different routing constraints. They have
shown that most problems that arise under these constraints are NP-complete
and they also proposed some heuristic reconfiguration algorithms for these prob-
lems. An algorithm, namely GCR, was proposed in [8] to find a maximal logical
array (MLA) that contains a set of the selected rows. The techniques performing
row-exclusion and compensation were proposed and combined with GCR into
a heuristic algorithm to generate an approximate MLA [9]. Recently, the pow-
er dissipation of a logical array was reduced in [10] by reducing the number of
long-interconnects utilizing a dynamic programming approach. In [11], a genetic
algorithm (GA) for the reconfiguration of degradable mesh arrays is present-
ed to evolve rerouting strategies for constructing logical rows/columns. In [12],
novel techniques are presented to accelerate reconfiguration by employ flexible
upper and lower bounds for the maximum logical array (MLA). The degradable
reconfiguration approach for three-dimensional mesh-connected processor arrays
is investigated in [13][14].

In a logical array, two neighboring PEs are interconnected through a group
of physical links and these physical links form a interconnect path (interconnect
for short) between the two PEs. Note that this architecture implements recon-
figuration using simple switches, thus overlap of physical links is not allowed
between any two interconnects, i.e., no physical link is shared by any two inter-
connects of a feasible logical array. In order to generate logical arrays without
overlap, most previous works develop reconfiguration algorithms under rerout-
ing schemes with limitation on the routing distance *d* (see section 2.1 for formal
definition), which means that if the distance between two PEs exceeds *d*, then
the two PEs are not allowed to connect to form a logical array. This has brought
convenience for designing reconfiguration algorithms, but it leads to large num-
ber of unused fault-free PEs, which is a serious waste of computing resources.
This motivates us to increase the utilization of fault-free PEs by adopting flexi-
ble rerouting scheme. In this paper, we first investigate the performance loss of
previous works in terms of utilization of fault-free PEs, then we adopt a flexi-
ble rerouting scheme in reconfiguration resulting in an efficient nonbacktracking
algorithm, to produce maximum logical arrays under the rerouting scheme.

2 Preliminaries

## 2.1 Fault-tolerant Architecture and Rerouting Schemes

Let $H$ denotes the physical (host) array on which some of the elements are de-
fective due to hardware/circuit defects or soft faults which means temporary un-
availability caused by overheating, overload or occupancy by other applications.
Assume the fault density of the physical array is $\rho$, then there are $N = (1-\rho) \cdot m \cdot n$
fault-free PEs in a $m \times n$ physical array. The rows and columns in physical array
are called physical rows and columns respectively. A logical subarray which con-
tains no faulty PEs constructed by changing states of reconfiguration switches
is called a logical array (target array), denoted as $T$. The rows and columns in
logical target array are called logical rows and columns respectively. Throughout
this paper, $e_{i,j}(e'_{i,j})$ indicates the PE located at the position of $(i,j)$ of the host
(logical) array, where $i$ is its row index and $j$ is its column index. $row(u)(col(u))$
denotes the physical row (column) index of the PE $u$. $u=v$ denotes that $u$ is
identical to $v$.

Fig. 1 shows the fault-tolerant architecture for a 4×4 host array. The fault-
tolerant reconfiguration is achieved by inserting several reconfiguration switches
in the network allowing the network to flexibly change the connections among
PEs. Each square box in the host array represents a processing element (PE),
whereas each circle represents a reconfiguration switch. In all figures in this
paper, the gray shaded boxes represent faulty PEs while unshaded ones represent
the fault-free PEs. There are 4 states for each switch.

In order to generate logical arrays without overlaps among interconnects,
two software control schemes, i.e. bypass and rerouting schemes, are utilized to
guide reconfiguration algorithms. In particular, row bypass and column rerouting
schemes are mostly employed in previous works. As shown in Fig.1, if PE $e_{i,j}$
is faulty, then PE $e_{i,j-1}$ can communicate with PE $e_{i,j+1}$ and data will bypass
$e_{i,j}$ through an internal bypass link. This scheme is called *row bypass*. In *column
rerouting* scheme, PE $e_{i,j}$ could connect to $e_{i+1,j'}$ by changing states of
related switches where $|j - j'| \le d$ and $d$ is called the compensation distance
[8][9]. If $d$ is limited to 1, then PE $e_{i,j}$ can connect to one of the three PEs,
<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Switch functions and rerouting manners on a 4 × 4 mesh linked by four-port switches</figcaption></figure>

i.e. $e_{i+1,j-1}$, $e_{i+1,j}$ and $e_{i+1,j+1}$, to form a logical column. The three PEs are called neighbors of $e_{i,j}$, and set of the three PEs is denoted as $\mathcal{Adj}(e)$. **column bypass** and **row rerouting** schemes can be similarly defined. Generally, in order to reduce the complexity of the switching mechanisms and keep low cost of physical implementation, it is necessary to keep $d$ small.

## 2.2 Construct Target Arrays on Selected Rows

**Problem R.** Given an $m \times n$ mesh-connected processor array in which some of its elements are faulty, find a maximum target array that contains the selected rows under the row bypass and column rerouting scheme.

Let $R_1, R_2, \dots, R_m$ be the rows of the given host array. Assume $R_{r_1}, R_{r_2}, \dots, R_{r_s}$ are the $s$ selected rows to construct a target array, where $1 \le r_s \le m$. Logical columns can be constructed under column rerouting scheme on selected rows, and interconnecting these logical columns under row bypass scheme forms a target array. A logical array $T$ is said to contain $R_{r_1}, R_{r_2}, \dots, R_{r_s}$ if each logical column in $T$ contains exactly one fault-free PE from each of the selected rows. Note that, if a physical row is not selected for inclusion into target array, all PEs in the row will be bypassed.

Suppose $C_p$ and $C_q(C_p \neq C_q)$ are two logical columns constructed on the $s$ selected rows, thus each of them is consists of $s$ PEs such that one and only one PE lies on each selected row. Let $C_p(i)$ denotes the PE lying in the $i$-th selected row of column $C_p$ and $C_q(i)$ denotes the PE lying in the $i$-th selected row of column $C_q$, for $1 \le i \le s$.

1. We say that $C_p < C_q$ if PE $C_p(i)$ in $C_p$ lies to the left-side of PE $C_q(i)$ in $C_q$, for $1 \le i \le s$.

2. We say that $\bar{C}_p \le C_q$ if PE $C_p(i)$ in $C_p$ lies to the left-side of, or is identical to, the PE $C_q(i)$ in $C_q$, for $1 \le i \le s$.
3. We say that $C_p$ and $C_q$ are **independent** of each other if $C_p < C_q$ or $C_q < C_p$.

4. We say that $C_p$ and $C_q$ are **overlap** with each other if neither $C_p < C_q$ nor $C_q < C_p$ is satisfied.

We define that a logical column, say column $C_l$, as the left-most column related to column set $A$ if $C_l \in A$ and $C_l \preceq C_p$ for any $C_p \in A$.

The problem $\mathcal{R}$ is proved to be optimally solved by an algorithm named *Greedy Column Rerouting* (GCR)[9]. In fact, the target array produced by GCR is maximum-size under the constraint that the compensation distance $d$ of column-s rerouting scheme is limited to 1, instead of the maximum-size target array for the problem $\mathcal{R}$. All operations in GCR are carried out on the adjacent sets of each fault-free PE $u$ in row $R_{r_i}$, defined as $\text{Adj}(u)=\{v : v \in R_{r_{i+1}}, v$ is unused fault-free PE and $|\text{col}(u) - \text{col}(v)| \le 1\}$. $\text{Adj}(u)$ consists of PEs that PE $u$ can directly connect to in the next selected row. The PEs in $\text{Adj}(u)$ are ordered in increasing columns index. The PE with the minimum column index in $\text{Adj}(u)$ is called the leftmost connectable PE for $u$.

## 2.3 Flexible Rerouting Schemes

As we have discussed before, two types of software rerouting schemes, i.e. bypass and rerouting schemes, are employed to guide reconfiguration algorithms. In previous work, the compensation distance $d$ of column rerouting scheme is limited to 1 to keep low cost of hardware implementation, thus 4-port switches are effective for reconfiguration. Rerouting schemes provides convenience for designing algorithms and guarantees that target arrays can be easily implemented using 4-port switches. However, there are considerable *un-connectable* PEs which are fault-free but cannot be used in forming a logical target array. Fig.2 shows two logical arrays constructed from a 5 × 5 host array. Fig.2(a) shows an logical array of two logical columns constructed by algorithm GCR under column rerouting scheme with $d=1$. The target array formed under flexible rerouting scheme contains 3 logical columns as shown in Fig.2(b). There are 7 un-connectable PEs in the first target array, but only 2 un-connectable PEs is generated by adopting flexible rerouting scheme as shown in the second array.

Experimental results show that, under fixed column rerouting scheme with $d = 1$, the proportions of un-connectable PEs are up to 17.1%, 34.75% and 52.45% on 64 × 64 host array with fault densities are 10%, 20% and 30%, respectively. In order to to improve the *harvest* by reducing the number of un-connectable PEs, we adopt the *flexible column rerouting scheme* which is formed as follows. Assume that row $R_{r_i}$ and $R_{r_{i+1}}$ are the $i$-th and $(i+1)$-th selected rows, and set $E_i$ and $E_{i+1}$ contain fault-free PEs in $R_{r_i}$ and $R_{r_{i+1}}$ respectively, then a PE in $E_i$ can connect directly to any PE in $E_{i+1}$ by reconfigure relative switch status.
<figure><img src="image_3.png" /><figcaption>**Fig. 2.** (a) only 2 logical columns are formed under column rerouting scheme with compensation distance *d*=1, (b) 3 logical columns can be constructed under flexible rerouting scheme.</figcaption></figure>

### 3 Maximum-size Target Array under Flexible Rerouting Scheme

In this section, we solve problem $\mathcal{R}$ under flexible rerouting scheme to further increase target array size. In another word, given an $m \times n$ mesh-connected processor array $H$ in which some of its elements are faulty, let $R_{r_1}, R_{r_2}, \dots, R_{r_s}$ be the selected rows, find a target array which consists of the maximum number of independent logical columns under the row bypass and flexible column rerouting scheme such that each logical column contains the selected rows. We first present a heuristic algorithm, denoted as FLX, which is capable of solving problem $\mathcal{R}$ in linear time. Then we prove that the target array constructed by FLX is maximum-size target array, and the target arrays constructed in this paper is much larger than that in previous works.

We model the problem $\mathcal{R}$ as follows. Suppose that set $S$ contains all logical columns that can be construct on the selected rows of host array $H$. Formally, $S=\{C|C$ is a logical column on selected rows and $|C \cap E_i|=1$ for $1 \le i \le s\}$. Any column $C$ in $S$ contains exactly one PE from each selected rows. In problem $\mathcal{R}$, we wish to find a maximum-size subset, say $A$, of independent logical columns.

We shall solve this problem in several steps, in each step we make choice of selecting one column for inclusion into $A$, and we are left with the subproblem $S'$: finding a maximum-size subset on subproblem $S'$. We observe that we need only to consider the greedy choice, the left-most logical column, in making each choice. Theorem 1 verifies that the greedy way of making choice leads to optimal solution, the verification is based on Theorem 2 which indicates that the greedy choice is always part of some optimal solution. Let $S_k = \{C_i|C_i \in S$ and $C_k < C_i\}$ be the set of logical columns that lie to the right-side of column $C_k$. If we make the choice of selecting the left-most column $C_1$, then $S_1$ remains as the only subproblem to solve. Since $C_1$ is in some optimal solution, we can construct an optimal solution to the original problem consists of column $C_1$ and all logical columns in an optimal solution to the subproblem $S_1$. In another word, $\{C_1\} \cup A'$
<figure><img src="image_4.png" /><figcaption>**Fig. 3.** $C_1=<e_1, e_2, e_3>$ is the left-most column, $u_1$ and $u_2$ become un-connectable after column $C_1$ is constructed.</figcaption></figure>

is an optimal solution to original problem *S* if *A'* is an optimal solution to subproblem *S*₁.

After constructing the leftmost column, some PEs becomes unconnectable due to overlap of interconnects. Rerouting on the unconnectable PEs leads to backtracking, such as in previous algorithm GCR. In order to improve the efficiency, we adopt the following technique to avoid backtracking. We identify unconnectable PEs so that columns containing unconnectable PEs will not be considered in the next stage selection. To exclude these un-connectable PEs out of sets $E_i$ for $1 \le i \le s$, two type of situations are examined as follows, according to the newly constructed column $C_k$. Let $C_k(i)$ and $C_k(i+1)$ denote two PEs which lie in the *i*th selected row and the $(i+1)$th selected row of column $C_k$.

- case 1: $col(C_k(i+1)) > col(C_k(i))$, then PE *u* is invalid if $row(u) = r_i$, $col(u) > col(C_k(i))$ and $col(u) < col(C_k(i+1))$.

- case 2: $col(C_k(i)) > col(C_k(i+1))$, then PE *u* is invalid if $row(u) = r_{i+1}$, $col(u) > col(C_k(i+1))$ and $col(u) < col(C_k(i))$.

An example is shown in Fig.3. $u_1$ is un-connectable according to case 1 and $u_2$ is un-connectable according to case 2. Thus, after constructing each left-most column, un-connectable PEs must be excluded from candidate PEs set.

We implement the algorithm FLX in a iterative way instead of a recursive manner. The algorithm takes host array *H* with size of *m*×*n* in which some of its elements are faulty, and the indexes $r_1, r_2, ..., r_s$ that defines the selected rows as input. It returns a maximum-size subset of independent logical columns which form a logical target array *T*. The algorithm works as follows. The variable *k* indexes the most resent constructed left-most column, corresponding to the $C_k$ in algorithm FLX. Then the **for** loop initialize $E_i$ as the set of fault-free PEs in row $R_{r_i}$ for $1 \le i \le s$. PEs in $E_i$ are sorted initially by increasing column index. In **while** loop, the algorithm construct left-most column $C_k$ one by one and adds $C_k$ into target array *T*. In each iteration, the algorithm first construct a left-most column $C_k$, then update candidate set $E_i(1 \le i \le s)$ by excluding un-connectable PEs according to $C_k$. To see which PEs are un-connectable, two type of cases are examined as described above.

Now we analyze the complexity of the proposed greedy algorithm. Initialize candidate set $E_i(1 \le i \le s)$ runs in $O(m \cdot n)$. In the **while** loop, each PE is
**Algorithm 1: FLX(H, r<sub>1</sub>, r<sub>2</sub>, ..., r<sub>s</sub>) /* Flexible Column Rerouting Algorithm */

**Input:** host array *H* with size of *m*×*n*; indexes of selected rows: r<sub>1</sub>, r<sub>2</sub>, ..., r<sub>s</sub>;

**Output:** maximum-size target array *T*.

1 **begin**
2   **for** *i* ← 1 **to** *s* **do**
3     **if** (*E*<sub>*i*</sub> ≠ *φ*) **then**
4     **else**
5     **while** (*E*<sub>1</sub> ≠ *φ*) **do**
6       /* construct C<sub>*k*</sub> from candidate sets ⋃<sub>*i*=1</sub><sup>*s*</sup> *E*<sub>*i*</sub> */
7       **for** *i* ← 1 **to** *s* **do**
8         **if** (*E*<sub>*i*</sub> ≠ *φ*) **then**
9           **else**
10         **while** (*E*<sub>1</sub> ≠ *φ*) **do**
11           /* construct C<sub>*k*</sub> from candidate sets ⋃<sub>*i*=1</sub><sup>*s*</sup> *E*<sub>*i*</sub> */
12         **for** *i* ← 1 **to** *s* **do**
13           **if** (*E*<sub>*i*</sub> ≠ *φ*) **then**
14             /* exclude unconnectable PEs out of E<sub>*i*</sub> (1 ≤ *i* ≤ *s*−1) according to case 1 */
15             **for** *i* ← 1 **to** *s*−1 **do**
16               **if** col(C<sub>*k*</sub>(*i* + 1)) − col(C<sub>*k*</sub>(*i*)) > 1 **then**
17               **for** *j* ← col(C<sub>*k*</sub>(*i*)) + 1 **to** col(C<sub>*k*</sub>(*i* + 1)) − 1 **do**
18                 **if** e<sub>*i*,*j*</sub> ∈ *E*<sub>*i*</sub> **then**
19                 **else**
20               /* exclude unconnectable PEs out of E<sub>*i*</sub> (2 ≤ *i* ≤ *s*) according to case 2 */
21               **for** *i* ← 2 **to** *s* **do**
22                 **if** col(C<sub>*k*</sub>(*i* − 1)) − col(C<sub>*k*</sub>(*i*)) > 1 **then**
23                 **for** *j* ← col(C<sub>*k*</sub>(*i*)) + 1 **to** col(C<sub>*k*</sub>(*i* − 1)) − 1 **do**
24                   **if** e<sub>*i*,*j*</sub> ∈ *E*<sub>*i*</sub> **then**
25                 **else**
26               **while** (*E*<sub>1</sub> ≠ *φ*) **do**
27               **while** (*E*<sub>1</sub> ≠ *φ*) **do**
28             **return** *T*;
29 **end**
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
29 end
examined only once, either to include into a left-most column or excluded out of candidate set $E_i$, thus the while loop runs in $O(m \cdot n)$. Therefore, the algorithm FLX construct a maximum-size target array under flexible rerouting schemes in $O(m \cdot n)$ time.

**Theorem 1.** *Algorithm FLX produces maximum-size target array for problem $\mathcal{R}$.*

*Proof.* Let $C_1$ be the left-most logical column in $S$, thus for any $C_p \in S$ we have $C_1 \le C_p$. Then, based on theorem 2, there always exist an optimal solution, say $A$, whose left-most column is $C_1$. Once the greedy choice $C_1$ is made, the problem $S$ is reduced to find an optimal solution for subproblem $S_1 = \{C_x | C_x \in S$ and $C_1 < C_x\}$ without have to consider any logical columns that overlap with $C_1$ in $S_1$. This is because for any $C_p \in S$, we have $C_1 \le C_p$, and $C_1$ is the left-most column. Thus, all logical columns that are independent with logical column $C_1$ must not overlap with $C_1$, i.e. they certainly belong to $S_1$. Therefore, we can first construct the left-most column $C_1$, and then try to find an optimal solution, say $A_1$, for sub-problem $S_1$, thus one optimal solution for the original problem $S$ could be $\{C_1\} \cup A_1$. In this way, we could find a maximum-size target array by making greedy choice at each step. In another word, algorithm FLX produces maximum-size target array for problem $\mathcal{R}$.

**Theorem 2.** *Consider any nonempty subproblem $S_k$, and let $C_m$ be the left-most logical column on selected rows in $S_k$. Then $C_m$ is included in some maximum-size subset of independent logical columns of $S_k$.*

*Proof* Let $A_k$ be a maximum-size subset of independent logical columns in $S_k$, and let $C_j$ be left-most logical column in $A_k$. If $C_j=C_m$, we are done, since we have shown that $C_m$ is in some maximum-size subset of independent logical columns of $S_k$. If $C_j \ne C_m$, let the set $A'_k = A_k - \{C_j\} \cup \{C_m\}$ be $A_k$ but substituting $C_m$ for $C_j$. The logical columns in $A'_k$ are independent, which follows because the columns in $A_k$ are independent, $C_j$ is the left-most column in $A_k$, and $C_m \le C_j$. Since $|A'_k| = |A_k|$, we conclude that $A'_k$ is a maximum-size subset of independent logical columns in $S_k$, and it includes $C_m$. Therefore, $C_m$ is included in some maximum-size subset of independent logical columns of $S_k$.

# 4 Experimental Results and Analysis

In this section, we investigate the efficiency of flexible rerouting scheme by evaluating performance of algorithm FLX in comparison with algorithm GCR. To evaluation metrics, i.e., *harvest* and *degradation*, as formulated in [8-10,13-14], were calculated. The *harvest* indicates how effectively the non-faulty elements are utilized in constructing a target array from a host array with fault elements, whereas the *degradation* measures the degree of potential performance loss due to a smaller target array than the original host array.

$$harvest = \frac{\text{Size of Target Array}}{\text{Total number of Nonfaulty PEs in Host Array}} \times 100\%$$
$$degradation = \frac{\text{Size of Host Array} - \text{Size of Target Array}}{\text{Size of Host Array}} \times 100\%$$

For the simplicity, we denote target arrays constructed by algorithms GCR and FLX as *GCRA* and *FLXA*, respectively. The improvement in *harvest* of the FLX over algorithm GCR, is calculated by

$$impr = \frac{\text{harvest of FLXA} - \text{harvest of GCRA}}{\text{harvest of FLXA}} \times 100\%$$

<table><caption>**Table 1.** The performance comparison of the algorithms GCR and FLX for random faults of uniform distribution, averaged over 20 random instances for each case.</caption><thead><tr><th colspan="2">Host Array</th><th colspan="6">Target array</th></tr><tr><th rowspan="2">Size</th><th rowspan="2">Fault density</th><th colspan="2">Array size</th><th colspan="2">harvest (%)</th><th colspan="2">degradation (%)</th><th rowspan="2">impr (%)</th></tr><tr><th>GCR</th><th>FLX</th><th>GCR</th><th>FLX</th><th>GCR</th><th>FLX</th></tr></thead><tbody><tr><td rowspan="4">64×64</td><td>0.05</td><td>64×54</td><td>64×55</td><td>89.23</td><td>89.64</td><td>15.23</td><td>14.84</td><td>0.46</td></tr><tr><td>0.10</td><td>64×48</td><td>64×49</td><td>82.91</td><td>84.56</td><td>25.39</td><td>23.91</td><td>2.00</td></tr><tr><td>0.20</td><td>64×33</td><td>64×38</td><td>65.25</td><td>73.85</td><td>47.81</td><td>40.94</td><td>13.25</td></tr><tr><td>0.30</td><td>64×21</td><td>64×30</td><td>47.55</td><td>66.08</td><td>66.72</td><td>53.75</td><td>39.46</td></tr><tr><td rowspan="4">128×128</td><td>0.05</td><td>128×110</td><td>128×111</td><td>90.71</td><td>91.16</td><td>13.83</td><td>13.40</td><td>0.50</td></tr><tr><td>0.10</td><td>128×96</td><td>128×98</td><td>83.29</td><td>85.20</td><td>25.04</td><td>23.32</td><td>2.30</td></tr><tr><td>0.20</td><td>128×68</td><td>128×77</td><td>66.55</td><td>75.64</td><td>46.76</td><td>39.49</td><td>13.74</td></tr><tr><td>0.30</td><td>128×41</td><td>128×61</td><td>46.21</td><td>67.75</td><td>67.66</td><td>52.58</td><td>46.94</td></tr><tr><td rowspan="4">256×256</td><td>0.05</td><td>256×222</td><td>256×224</td><td>91.41</td><td>92.06</td><td>13.16</td><td>12.54</td><td>0.72</td></tr><tr><td>0.10</td><td>256×193</td><td>256×198</td><td>83.57</td><td>86.07</td><td>24.79</td><td>22.54</td><td>2.99</td></tr><tr><td>0.20</td><td>256×137</td><td>256×157</td><td>66.82</td><td>76.83</td><td>46.54</td><td>38.54</td><td>14.99</td></tr><tr><td>0.30</td><td>256×82</td><td>256×123</td><td>45.65</td><td>68.75</td><td>68.05</td><td>51.88</td><td>50.75</td></tr></tbody></table>

In order to make a fair comparison, we keep the same assumptions as in [8-14]. Faults are only associated with PEs and communication infrastructure is assumed to be fault free. This assumption can be justified since the switches and links use much less hardware resources when compared to the processors and are thus less vulnerable to defects. Both random fault model and clustered fault model were considered [7-10,12]. In a random fault model, the faults of a host array were generated by a uniform random generator. The fault density $\rho$ of the host array is set from 5% to 30% for the experiments. On the other hand, without loss of generality, we model the clustered faults as a subarray that has 80% random faults in the host array. In order to focus on the clustered fault distribution, the fault density out of the subarray is set to 5%, which is far less than that in the subarray. The location of the subarray is generated randomly in the host array. Both algorithms were implemented in C++ language running on a computer with 2.1GHz CPU and 2GB RAM and are compared with each other on the same input instances. For each case, all physical rows are selected for inclusion into target array for experiments.

Table 1 shows the performance comparison of algorithms FLX and GCR. For the case of constructing target array on 64×64 host array with fault density
<figure><img src="image_5.png" /><figcaption>**Fig. 4.** Comparison of FLX and GCR in terms of target array size and harvest, on host arrays of 256 × 256 with random faults, averaged over 20 instances for each case.</figcaption></figure>

10%, the *harvest* of target array produced by GCR is 82.91%, while it is 84.56% by algorithm FLX, thus resulting in the improvement of 2% in *harvest*. When the fault density increases to 30%, FLX improves GCR by 39.46% on *harvest*. It is because, with the increasing fault densities, more PEs become un-connectable in algorithm GCR while they can be used in FLX to form logical columns. It is also worth pointing out that, if the fault density exceeds a certain point, i.e. 50% for host arrays with size of 256 × 256, algorithm GCR fails to form any logical columns as shown in Fig. 4(a). However, algorithm FLX is still capable of constructing target arrays with no less than 70 columns which corresponding to a harvest of 56%, as shown in Fig. 4(b). On the other hand, on host arrays with large fault densities, the improvement in harvest is more significant on large target arrays than on the relatively small ones. For examples, with fault density of 30%, the improvements of FLX over GCR are 39.46%, 46.94% and 50.75% for host arrays with sizes of 64 × 64, 128 × 128 and 256 × 256, respectively. It is because, the increasing size increases the difficulty of forming a logical column thus leads to decrease in the number of logical columns and results in increase in the number of un-connectable PEs. This provides more chance for algorithm FLX to improve the target arrays using flexible column rerouting scheme.

Table 2 shows performance gain of algorithms FLX over GCR for the case of the clustered faults on 512×512 host arrays with fault density 5%. Our investigations reveal that, the harvest improvement increased with the increasing number of clustered fault areas. For example, on host array with 24×24 clustered fault areas, the improvement of harvest is 5.15% for the case of 8 clustered fault areas, while it increased to 13.22% and 19.77% on host arrays with 24 and 32 clustered fault areas, respectively. This is because, as the number of clustered fault areas increases, fewer logical columns can be constructed by algorithm GCR, thus leads to more un-connectable PEs which provide more chance for optimization by FLX. In addition, the improvement for harvest decreases is more significant on relatively large clustered fault area. This is because logical columns constructed by GCR cannot go through clustered fault areas, thus large scale clustered fault areas decreases the area of PEs that can be used for constructing target arrays by algorithm GCR. On the other hand, large clustered fault areas increase the
<table><caption>**Table 2.** The performance comparison of the algorithms GCR and FLX for clustered faults of uniform distribution on 512×512 host array, averaged over 20 random instances for each case.</caption><thead><tr><th colspan="2">Host Array</th><th colspan="6">Target array</th></tr><tr><th colspan="2">Cluster Distribution</th><th colspan="2">Array size</th><th colspan="2">harvest (%)</th><th colspan="2">degradation (%)</th><th>impr (%)</th></tr><tr><th>size</th><th>number</th><th>GCR</th><th>FLX</th><th>GCR</th><th>FLX</th><th>GCR</th><th>FLX</th><th></th></tr></thead><tbody><tr><td rowspan="4">16×16</td><td>8</td><td>512×419</td><td>512×431</td><td>86.12</td><td>88.58</td><td>18.18</td><td>15.85</td><td>2.87</td></tr><tr><td>16</td><td>512×400</td><td>512×419</td><td>82.25</td><td>86.09</td><td>21.87</td><td>18.21</td><td>4.72</td></tr><tr><td>24</td><td>512×381</td><td>512×409</td><td>78.42</td><td>84.06</td><td>25.50</td><td>20.15</td><td>7.23</td></tr><tr><td>32</td><td>512×369</td><td>512×401</td><td>75.81</td><td>82.41</td><td>27.98</td><td>21.71</td><td>8.73</td></tr><tr><td rowspan="4">24×24</td><td>8</td><td>512×395</td><td>512×416</td><td>81.29</td><td>85.44</td><td>22.77</td><td>18.83</td><td>5.15</td></tr><tr><td>16</td><td>512×363</td><td>512×396</td><td>74.69</td><td>81.49</td><td>29.04</td><td>22.59</td><td>9.17</td></tr><tr><td>24</td><td>512×330</td><td>512×374</td><td>67.86</td><td>76.82</td><td>35.54</td><td>27.02</td><td>13.32</td></tr><tr><td>32</td><td>512×294</td><td>512×351</td><td>60.40</td><td>72.13</td><td>42.62</td><td>31.47</td><td>19.77</td></tr><tr><td rowspan="4">32×32</td><td>8</td><td>512×364</td><td>512×392</td><td>74.83</td><td>80.59</td><td>28.92</td><td>23.44</td><td>7.84</td></tr><tr><td>16</td><td>512×318</td><td>512×364</td><td>65.40</td><td>74.79</td><td>37.87</td><td>28.95</td><td>14.78</td></tr><tr><td>24</td><td>512×251</td><td>512×322</td><td>51.54</td><td>66.27</td><td>51.04</td><td>37.04</td><td>28.80</td></tr><tr><td>32</td><td>512×226</td><td>512×315</td><td>46.48</td><td>64.69</td><td>55.84</td><td>38.54</td><td>40.37</td></tr></tbody></table>

fault density of the host array, thus provide more chance for optimization by algorithm FLX.

## 5 Conclusions

Many previous works discuss the reconfiguration problems under column rerouting scheme with fixed compensation distance, resulting in great lose of harvest. This paper investigate the efficiency of flexible rerouting scheme by developing an efficient algorithm to reconfigure an multiprocessor array with faults. The proposed algorithm FLX is able to reduce the number of un-connectable PEs caused by the interconnection overlaps. It is capable of producing maximum-size target arrays, resulting in a significant improvement in comparison to the algorithm GCR. Experimental results show that the size of target array can be significantly increased. The algorithm FLX is scalable with the array size, as it is more efficient on large host arrays than on relatively small ones. In addition, its harvest tends to decrease slowly with the increasing fault density, that is superior to algorithm GCR whose harvest value decreases rapidly.

## Acknowledgments.

This work was supported by the National Science Foundation of China under Grant No. 61070136 and No. 61173032, and the Doctoral Fund of Ministry of Education of China under Grant No. 20100032110041.
References

1. S. Murali, G. De Micheli. :SUNMAP: A tool for automatic topology selection and generation for NoCs. In: Proc. of the 41st Design Automation Conference (DAC’04), pp.914-919. ACM Press, San Diego, USA, (2004)

2. D. Bertozzi, A. Jalabert, S. Murali, R. Tamahankar, S. Stergiou, L. Benini, G. De Micheli.:NoC synthesis flow for customized domain specific multiprocessor systems-on-chip. IEEE Transactions on Parallel and Distributed System, 16(2), 113-129, (2005)

3. M. Modarressi, H. Sarbazi-Azad.:Power-aware mapping for reconfigurable NoC architectures. In: Proc. of the 25th International Conference on Computer Design. pp.417-422. IEEE Press, California, (2007)

4. Modarressi, M. Tavakkol, A. Sarbazi-Azad. :Application-Aware Topology Reconfiguration for On-Chip Networks. IEEE Transactions on Very Large Scale Integration (VLSI) Systems. 19(11), 2010-2022, (2011)

5. Y. Y. Chen, S. J. Upadhyaya and C. H. Cheng. :A comprehensive reconfiguration scheme for fault-tolerant VLSI/WSI array processors. IEEE Transactions Computers. 46(12), pp. 1363-1371, (1997)

6. T. Horita and I. Takanami. :Fault-tolerant processor arrays based on the 1.5-track switches with flexible spare distributions. IEEE Transactions on Computers. 49(6), 542-552, 2000.

7. S. Y. Kuo and I. Y. Chen. :Efficient reconfiguration algorithms for degradable VLSI/WSI arrays. IEEE Transactions Computer-Aided Design. 11(10), 1289-1300, (1992).

8. C. P. Low and H. W. Leong. On the reconfiguration of degradable VLSI/WSI arrays. IEEE Transactions Computer-Aided Design of integrated circuits and systems. 16(10), 1213-1221, (1997)

9. C. P. Low. :An efficient reconfiguration algorithm for degradable VLSI/WSI arrays. IEEE Transactions on Computers. 49(6), 553-559, (2000)

10. J. Wu and T. Srikanthan. :Reconfiguration Algorithms for Power Efficient VLSI Subarrays with 4-port Switches. IEEE Transactions on Computers. 55(3), 243-253, (2006)

11. M. Fukushi, Y. Fukushima, and S. Horiguchi. :A genetic approach for the reconfiguration of degradable processor arrays. In: Proc. of 20th IEEE International Symposium on Defect Fault Tolerance VLSI System. pp. 63-71. IEEE Press, Ohio, (2005)

12. J. Wu, T. Srikanthan, and X. Han. :Preprocessing and Partial Rerouting Techniques for Accelerating Reconfiguration of Degradable VLSI Arrays. IEEE Transactions on Very Large Scale Intergration (VLSI) Systems. 18(2), 315-319, (2010)

13. G. Jiang, J. Wu and J. Sun. :Non-Backtracking Reconfiguration Algorithm for Three-dimensional VLSI Arrays. In: Proc. of 2012 IEEE 18th International Conference on Parallel and Distributed Systems. pp.362-367, IEEE Press, Singapore. (2012)

14. G. Jiang, J. Wu and J. Sun. :Efficient Reconfiguration Algorithm for Three-dimensional VLSI Arrays. In: Proc. of 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum. pp.254-258. IEEE Press, Shanghai, (2012)