Alain Thomas
email: thomas@cmi.univ-mrs.fr

INFINITE PRODUCTS OF NONNEGATIVE 2 × 2 MATRICES BY NONNEGATIVE VECTORS

Keywords:

Given a finite set {M 0 , . . . , M d-1 } of nonnegative 2 × 2 matrices and a nonnegative column-vector V , we associate to each (ω n ) ∈ {0, . . . , d -1} N the sequence of the column-vectors M ω1 . . . M ωn V M ω1 . . . M ωn V . We give the necessary and sufficient condition on the matrices M k and the vector V for this sequence to converge for all (ω n ) ∈ {0, . . .

Introduction

Let M = {M 0 , . . . , M d-1 } be a finite set of nonnegative 2×2 matrices and V = v 1 v 2 a nonnegative column-vector. We use the notation Y n = Y ω n := M ω 1 . . . M ωn and give the necessary and sufficient condition for the pointwise convergence of

Y n V Y n V , (ω n ) ∈ {0, . . . , d -1} N
such that Y n V = 0 0 for any n, where • is the norm-sum. The idea of the proof is that, if the conditions are satisfied, either both columns of Y n tends to the same limit, or they tend to different limits with different orders of growth, so in case V is positive the limit points of Y n V Y n V only depend on the limit of the dominant column. This problem is obviously very different from the one of the convergence of Y n Y n , or the convegence of the Y n itselves, see the intoduction of [START_REF] Olivier | Asymptotic properties of the columns in the products of nonnegative matrices[END_REF] for some counterexamples and [8, Proposition 1.2] for the infinite products of 2 × 2 stochastic matrices.

The conditions for the pointwise convergence of Y n V Y n V also differ from the conditions for its uniform convergence, see [START_REF] Olivier | Infinite products of 2 × 2 matrices and the Gibbs properties of Bernoulli convolutions[END_REF]. The uniform convergence can be used for the multifractal analysis of some continuous singular measures called Bernoulli convolutions (see [START_REF] Peres | Sixty years of Bernoulli convolutions[END_REF] for the Bernoulli convolutions and [START_REF] Feng | Multifractal analysis of weak Gibbs measures and phase transition -application to some Bernoulli convolutions[END_REF] for their multifractal analysis). We study such measures in [START_REF] Olivier | Infinite products of 2 × 2 matrices and the Gibbs properties of Bernoulli convolutions[END_REF], [START_REF] Olivier | Infinite Convolution of Bernoulli Measures, PV numbers and related problems in the dynamics of Fractal Geometry[END_REF] and [START_REF] Olivier | How to prove that some Bernoulli convolution is weak Gibbs[END_REF]. The Birkhoff's contraction coefficient [START_REF] Seneta | Non-negative matrices and Markov chains[END_REF]Chapter 3] that we use in [START_REF] Olivier | Infinite Convolution of Bernoulli Measures, PV numbers and related problems in the dynamics of Fractal Geometry[END_REF] and [START_REF] Olivier | Asymptotic properties of the columns in the products of nonnegative matrices[END_REF] but not here, is really not of great help to solve the main difficulties. Moreover the theorem that gives the value of this coefficient is difficult to prove (see [7, §3.4]) even in the case of 2 × 2 matrices. In [START_REF] Olivier | Infinite products of 2 × 2 matrices and the Gibbs properties of Bernoulli convolutions[END_REF] we use some other contraction coefficient quite more easy to compute ([2, Proposition 1.3]).

Condition for the pointwise convergence of

Y n V Y n V Proposition 1.1. The sequence Y n V Y n V converges for any ω ∈ {0, . . . , d -1} N such that ∀n, Y n V = 0 0 , if
A n = A ω n :=          M ωn if det Y n-1 > 0 (or n = 1) and det M ωn > 0 M ωn ∆ if det Y n-1 > 0 (or n = 1) and det M ωn < 0 ∆M ωn if det Y n-1 < 0 and det M ωn < 0 ∆M ωn ∆ if det Y n-1 < 0 and det M ωn > 0.
We set also

a n b n c n d n := A n and p n q n r n s n := A 1 . . . A n = Y n if det Y n > 0 Y n ∆ if det Y n < 0.
The matrices A n belong to the set

M + := {M ; ∃i, j, k, M = ∆ i M k ∆ j and det M > 0}.
Since det A n > 0 we have a n d n p n s n = 0. If {n; A n not diagonal} is infinite we index this set by an increasing sequence n 1 < n 2 < . . . . We have b n 1 = 0 or c n 1 = 0; both cases are equivalent because, using the set of matrices M ′ = ∆M∆ and defining similarly Y ′ n and

A ′ n = a ′ n b ′ n c ′ n d ′ n from this set, we have Y ′ n = ∆Y n ∆, A ′ n = ∆A n ∆ and b ′ n 1 = c n 1 .
So we can suppose b n 1 = 0; we deduce q n = 0 by induction on n ≥ n 1 . The sequences defined for any n ≥ n 1 by

u n = r n p n , v n = s n q n , w n = q n p n , x n = v 2 /v 1 if det Y n > 0 v 1 /v 2 if not and λ n = (1 + w n x n ) -1 satisfy 0 ≤ u n < v n < ∞, 0 < w n < ∞ and if the entries of V are positive, 0 < x n < ∞ and 0 < λ n < 1 if not, x n ∈ {0, ∞} and λ n ∈ {0, 1} according to the sign of det Y n .
Since we have assumed that

Y n V = 0 0 , the ratio (Y n V ) 2 (Y n V ) 1
exists in [0, ∞] and we have to prove that it has a finite or infinite limit when n → ∞.

If A n is not eventually diagonal we have for n ≥ n 1 (1) (Y n V ) 2 (Y n V ) 1 = λ n u n + (1 -λ n )v n ∈ I n := [u n , v n ] and I n ⊇ I n+1 .
An immediate consequence is the following lemma:

Lemma 1.1. Suppose A n is not eventually diagonal, then (i) the sequences (u n ) and (v n ) converge in R and the sequence (Y n V ) 2 (Y n V ) 1 is bounded; (ii) (Y n V ) 2 (Y n V ) 1 converges if lim n→∞ |I n | = 0; (iii) if V has positive entries, (Y n V ) 2 (Y n V ) 1 converges if w n has limit 0 or ∞;
(iv) if V has a null entry, the necessary and sufficient condition for the convergence of

(Y n V ) 2 (Y n V ) 1 is that lim n→∞ |I n | = 0 or the sign of det Y n is eventually constant.
We also define for n > n 1

α n = 1 + c n a n w n-1 -1 , β n = 1 + b n d n (w n-1 ) -1 -1 , γ n = 1 - c n a n b n d n
that belong to ]0, 1] and satisfy

(2)

|I n | = α n β n γ n |I n-1 | w n = d n a n α n β n w n-1 so n>n 1 α n β n γ n = lim n→∞ |I n | |I n 1 | is positive if
|I n | > 0 ⇔ c n a n w n-1 < ∞, b n d n (w n-1 ) -1 < ∞ and c n a n b n d n < ∞.
The set of indexes {n; A n not diagonal} is the union of

L ω = {n; c n = 0} and U ω = {n; b n = 0}.
Moreover, since A n belongs to the finite set M + there exists K > 0 such that

L ω = n; 1 K ≤ c n a n ≤ K and U ω = n; 1 K ≤ b n d n ≤ K .
We deduce a simpler formulation of (3):

(4) lim n→∞ |I n | > 0 ⇔ n∈L ω w n-1 < ∞, n∈U ω (w n-1 ) -1 < ∞ and L ω ∩ U ω is finite.
In view of Lemma 1.1 we may suppose from now that lim

n→∞ |I n | > 0. Since L ω ∩ U ω = {n ; A n positive} is finite, for n large enough the matrix A n is lower triangular if n ∈ L ω , upper triangular if n ∈ U ω , diagonal if n ∈ L ω ∪ U ω . When A n is diagonal
w n w n i = n i <j≤n d j a j .
Moreover if L ω is infinite, (4) implies that w n-1 has limit to 0 when L ω ∋ n → ∞, and

w n also has limit 0 because w n = d n w n-1 a n + c n w n-1
for any n ∈ L ω \ U ω . We have a similar

property if U ω is infinite, so (6) if L ω is infinite, w n-1 → 0 and w n → 0 for L ω ∋ n → ∞; if U ω is infinite, w n-1 → ∞ and w n → ∞ for U ω ∋ n → ∞.
First case: Suppose that (i) holds. Then the diagonal matrices of M are collinear to the unit matrix. If at least one matrix of M has the form

M k = 0 b c 0 with bc = 0, its nonnegative eigenvalue -namely √ b √ c -is collinear to V = v 1 v 2 hence there exists λ ∈ R such that M k = λ 0 v 2 1 v 2 2 0 .
Notice that if A n is diagonal from a rank N, the matrix M ωn has the form a 0 0 d or 0 b c 0 hence it has V as eigenvector; consequently

(Y n V ) 2 (Y n V ) 1 converges because it is (Y N V ) 2 (Y N V ) 1 for any n ≥ N.
Suppose now A n is non-diagonal for infinitely many n. We apply (5) on each interval ]n i , n i+1 [ (if non empty), for i large enough. Among the integers n ∈]n i , n i+1 [ we consider the ones for which det M ωn < 0. For such n the matrix A n is alternately M ωn ∆ and ∆M ωn , hence alternately proportional to

v 2 1 0 0 v 2 2 and to v 2 2 0 0 v 2 1
and, according to ( 5), ( 7)

n i ≤ n < n i+1 ⇒ w n w n i ∈ v 2 1 v 2 2 , v 2 2 v 2 1 , 1 .
In particular this relation holds for n = n i+1 -1. One deduce -according to (6) -that there do not exist infinitely many i such that n i ∈ L ω and n i+1 ∈ U ω . Thus n i ∈ L ω for i large enough (resp. n i ∈ U ω for i large enough) and, according to ( 6) and ( 7), lim

n→∞ w n = 0 (resp. lim n→∞ w n = ∞). In view of Lemma 1.1(iii), (Y n V ) 2 (Y n V ) 1 converges.
Second case: Suppose that (ii) holds (if (iii) holds the proof is similar). Suppose first the M ωn are diagonal from a rank N. From the hypothesis (ii) there exists

δ n , δ ′ n such that M ω N . . . M ωn V = δ n v 1 δ ′ n v 2 and δ n ≥ δ ′ n .
Since the M ω i belong to a finite set we have lim

n→∞ δ n δ ′ n = ∞, or δ n δ ′
n is eventually constant in case M ωn is eventually the unit matrix, or δ ′ n = 0 = δ n for n large enough. Denoting by

p q r s the matrix M ω 1 . . . M ω N-1 , we have (Y n V ) 2 (Y n V ) 1 = rδ n v 1 + sδ ′ n v 2 pδ n v 1 + qδ ′ n v 2 hence (Y n V ) 2 (Y n V ) 1
converges in all the cases.

Suppose now M ωn is non-diagonal for infinitely many n. There exists from [START_REF] Peres | Sixty years of Bernoulli convolutions[END_REF] an integer κ such that

(8) i ≥ κ ⇒ w n i -1 < 1 and w n i < 1 if n i ∈ L ω w n i -1 > 1 and w n i > 1 if n i ∈ U ω
and such that the A n are diagonal for n ∈]n i , n i+1 [, i ≥ κ. According to (ii), for such values of n the matrix M ωn is diagonal and

A n = M ωn with a n ≥ d n , or A n = ∆M ωn ∆ with a n ≤ d n .
If there exists i ≥ κ such that n i ∈ L ω and n i+1 ∈ U ω , det Y n i is necessarily negative:

otherwise A n should be equal to M ωn for n ∈]n i , n i+1 [, d n a n ≤ 1 and, by ( 5), w n i+1 -1 ≤ w n i < 1 in contradiction with [START_REF] Thomas | Can an infinite left-product of nonnegative matrices be expressed in terms of infinite left-products of stochastic ones?[END_REF]. Now M ωn i+1 has positive determinant, otherwise it should have the form a b c 0 and

A n i+1 = ∆M ωn i+1 = c 0 a b in contradiction with n i+1 ∈ U ω .
We have again

d n a n ≥ 1 for n ∈]n i+1 , n i+2 [ and consequently w n i+2 -1 ≥ w n i+1 > 1; so, by
induction, n j ∈ U ω and det Y n j < 0 for any j ≥ i + 1. From [START_REF] Olivier | Asymptotic properties of the columns in the products of nonnegative matrices[END_REF] w n lies between w n j and w n j+1 -1 for any n ∈]n j , n j+1 [ and j large enough, and from (6) its limit is infinite. Distinguishing the cases where V has positive entries or V has a null entry,

(Y n V ) 2 (Y n V ) 1 converges by Lemma 1.1.
The conclusion is the same if there do not exist i ≥ κ such that n i ∈ L ω and n i+1 ∈ U ω , because in this case n i ∈ L ω for i large enough, or n i ∈ U ω for any i ≥ κ.

Third case: Suppose (iv) holds. As we have seen, from (4) A n is eventually triangular or diagonal, and M ωn also is because -by (iv) -M do not contain invertible matrices of the form 0 b c d or a b c 0 . We deduce that the sign of det Y n is eventually constant. If

A n is not eventually diagonal the sequence (Y n V ) 2 (Y n V ) 1
converges by Lemma 1.1(iv) and, if

A n is, the sequence (Y n V ) 2 (Y n V ) 1 is eventually constant.
Fourth case: Suppose that the set M do not satisfy (i), (ii), (iii) nor (iv), and that at least one matrix of this set, let M k , has the form

M k = 0 b c 0 with bc = 0; let us prove that (Y n V ) 2 (Y n V ) 1 diverges.
Suppose first there exists a matrix M k of this form that do not have V as eigenvector;

we chose as counterexample the constant sequence defined by ω n = k for any n: Y 2n is collinear to the unit matrix, hence

Y 2n V is collinear to V and Y 2n+1 V to M k V , so (Y n V ) 2 (Y n V ) 1 diverges.
Suppose now that all the matrices of M of the form 0 b c 0 with bc = 0 have V as

eigenvector that is, V is collinear to √ b √ c
for all such matrix. Since (i) do not hold, at least one matrix M h of M is diagonal with nonnull and distinct diagonal entries. In this case M h M k has the form 0 b c 0 but do not have V as eigenvector. We recover the previous case; more precisely the counterexample is defined by ω 2n-1 = h and ω 2n = k for any n ∈ N.

Fifth case: Suppose that M do not satisfy (i), (ii), (iii) nor (iv), and that no matrix of the form 0 b c 0 with bc = 0 belongs to M. Since (i) do not hold, at least one matrix of this set has the form M k = a 0 0 d with ad = 0 and a = d. We suppose that a > d and we use the negation of (ii) (in case a < d we use similarly the negation of (iii)). According to the negation of (ii) there exists in M at least one matrix of the form M h = 0 β γ δ with βγδ = 0, or one of the form M ℓ = α 0 0 δ with 0 < α < δ.

Consider first the case where M contains some matrices M k and M h as above. Let (n i ) i∈N be an increasing sequence of positive integers with n 1 = 1, and ω the sequence defined by ω n = h for n ∈ {n 1 , n 2 , . . . } and ω n = k otherwise.

For i odd,

A n i is lower-triangular and ∀n ∈]n i , n i+1 [, A n = d 0 0 a , a n = d and d n = a.
For i even, A n i is upper-triangular and ∀n ∈]n i , n i+1 [, A n = a 0 0 d , a n = a and d n = d.

Using [START_REF] Olivier | Asymptotic properties of the columns in the products of nonnegative matrices[END_REF] for n = n i+1 -1 and choosing n i+1 -n i large enough one has w n i+1 -1 ≥ 2 i if i is odd, w n i+1 -1 ≤ 2 -i if i is even, so the three conditions in (4) are satisfied and the interval ∩I n is not reduced to one point. If the entries of V are positive, the first relation in [START_REF] Feng | Multifractal analysis of weak Gibbs measures and phase transition -application to some Bernoulli convolutions[END_REF] and the definition of λ n imply that lim inf In case M contains some matrices M k and M ℓ as above, one defines ω from a sequence i 1 = 1 < i 2 < i 3 < . . . by setting, for j ≥ 1 and i j ≤ n < i j+1 ,

n→∞ (Y n V ) 2 (Y n V ) 1 is
ω n = k if j even ℓ if j odd.
The diagonal matrix Y n can be easily computed, and (Y n V ) 2 (Y n V ) 1 obviously diverges if one choose the i j+1 -i j large enough.

If V has a null entry, since (iv) do not hold M contains at least one matrix of the form M h = 0 β γ δ , βγδ = 0 or M h ′ = α β γ 0 , αβγ = 0, or M h ′′ = 0 β γ 0 , βγ = 0. We already know that (Y n V ) 2 (Y n V ) 1 diverges if M contains M k and M h . Similarly it diverges if M contains M ℓ and M h ′ . If M contains M k and M h ′′ the counterexample is given -from a sequence i 1 = 1 < i 2 < i 3 < . . . -by ω i j = h ′′ and ω n = k for n ∈]i j , i j+1 [, j ∈ N:

(Y n V ) 2 (Y n V ) 1
is alternately 0 and ∞ because Y i j has the form 0 q r 0 for j odd and p 0 0 s for j even.

  and only if at least one of the following conditions holds: (i) V has positive entries and it is an eigenvector of any invertible matrix of the form a 0 0 d or 0 b c 0 that belongs to M. (ii) Any invertible matrix a b c d ∈ M satisfies a > 0 and, if b = c = 0, a ≥ d. (iii) Any invertible matrix a b c d ∈ M satisfies d > 0 and, if b = c = 0, d ≥ a. (iv) V has a null entry and all the invertible matrices a b c d ∈ M satisfy ad > 0. Proof. Let ω ∈ {0, . . . , d-1} N . If there exists N such that det M ω N = 0, the column-vectors Y N V, Y N +1 V, . . . are collinear and Y n V Y n V is constant for n ≥ N. So we look only at the ω ∈ {0, . . . , d -1} N such that ∀n, det M ωn = 0. In order to use only matrices with positive determinant we set ∆ :

  and only if lim n→∞ |I n | > 0. Using the equivalents of log α n , log β n and log γ n ,

	(3)	lim n→∞

  (Y n V ) 1 its upper bound, so the sequence (Y n V ) 2 (Y n V ) 1 diverges. If V has a null entry, the divergence of (Y n V ) 2 (Y n V ) 1results from Lemma 1.1(iv).

the lower bound of this interval and lim sup n→∞ (Y n V ) 2


Boris Grot

Stephen W Keckler

Onur Mutlu

Topology-aware Quality-of-Service Support in Highly Integrated Chip Multiprocessors

Current design complexity trends, poor wire scalability, and power limitations argue in favor of highly modular onchip systems. Today's state-of-the-art CMPs already feature up to a hundred discrete cores. With increasing levels of integration, CMPs with hundreds of cores, cache tiles, and specialized accelerators are anticipated in the near future. Meanwhile, server consolidation and cloud computing paradigms have emerged as profit vehicles for exploiting abundant resources of chip-multiprocessors. As multiple, potentially malevolent, users begin to share virtualized resources of a single chip, CMP-level quality-of-service (QOS) support becomes necessary to provide performance isolation, service guarantees, and security. This work takes a topology-aware approach to on-chip QOS. We propose to segregate shared resources, such as memory controllers and accelerators, into dedicated islands (shared regions) of the chip with full hardware QOS support. We rely on a richly connected Multidrop Express Channel (MECS) topology to connect individual nodes to shared regions, foregoing QOS support in much of the substrate and eliminating its respective overheads. We evaluate several topologies for the QOSenabled shared regions, focusing on the interaction between network-on-chip (NOC) and QOS metrics. We explore a new topology called Destination Partitioned Subnets (DPS), which uses a light-weight dedicated network for each destination node. On synthetic workloads, DPS nearly matches or outperforms other topologies with comparable bisection bandwidth in terms of performance, area overhead, energyefficiency, fairness, and preemption resilience.

Introduction

Complexities of scaling single-threaded performance have pushed processor designers in the direction of chiplevel integration of multiple cores. Today's state-of-theart commercial general-purpose chips integrate anywhere from four to one hundred cores [START_REF] Wendel | The implementation of POWER7: A highly parallel and scalable multicore high-end server processor[END_REF][START_REF] Shin | A 40nm 16-core 128-thread CMT SPARC SoC processor[END_REF][START_REF] Tilera | [END_REF], while GPUs and other specialized processors often contain hundreds of execution resources [START_REF]NVIDIA Fermi architecture[END_REF]. In addition to the main processors, these chips typically integrate cache memories, specialized accelerators, memory controllers, and other func-tional entities. As the degree of integration increases with each technology generation, chips containing hundreds and even thousands of discrete execution and storage resources will be likely in the near future.

The abrupt emergence of multi-core chips and their rapid proliferation have left researchers and industry scrambling for ways to exploit them. Two notable paradigms have arisen for monetizing CMPs -server consolidation and cloud computing. The former allows businesses to reduce server costs by virtualizing multiple servers on a single chip, thereby eliminating dedicated hardware boxes for each individual server. The latter enables delivery of various client services from remote (i.e., "cloud") servers. Since a single CMP can serve multiple users concurrently, hardware, infrastructure, and management costs are reduced relative to a model where each user requires a dedicated CPU.

Unfortunately, these novel usage models create new system challenges and vulnerabilities. For instance, in a consolidated server scenario, different priorities may be assigned to different servers. Thus, web and database servers for external customers could have a higher priority than intranet servers. But as multiple virtualized servers may be executing concurrently on a multi-core chip, traditional OSlevel preemptive scheduling policies can fail at properly enforcing priorities of different VMs competing for shared resources.

In a cloud setting, multiple users may be virtualized onto a common physical substrate, creating a number of new concerns, including inadvertent interference among the different users, deliberate denial-of-service attacks, and sidechannel information leakage vulnerabilities. Researchers have recently demonstrated a number of such attacks in a real-world setting on Amazon's EC2 cloud infrastructure, highlighting the threat posed by chip-level resource sharing on a public cloud [START_REF] Ristenpart | you, get off of my cloud: exploring information leakage in third-party compute clouds[END_REF].

Today's CMPs lack a way to enforce priorities and ensure performance-level isolation among the simultaneouslyexecuting threads. Inter-thread interference may occur in any of the shared resources present on a CMP, including caches, memory controllers, and the on-chip network. Researchers have suggested using on-chip hardware qualityof-service (QOS) mechanisms to enforce priorities, limit the extent of interference, and provide guarantees for threads sharing a substrate [START_REF] Iyer | CQoS: a framework for enabling QoS in shared caches of CMP platforms[END_REF][START_REF] Lee | Globallysynchronized frames for guaranteed quality-of-service in on-chip networks[END_REF][START_REF] Mutlu | Stall-time fair memory access scheduling for chip multiprocessors[END_REF]. While various shared resources have been studied as potential targets for QOS protection, little attention has been paid to the scalability of these techniques in CMPs with hundreds of cores, cache banks, and other discrete entities. In these highly-integrated CMPs, shared caches and the on-chip network emerge as potential scalability bottlenecks for chip-wide QOS support. Both are latency-sensitive distributed structures with a large number of nodes, requiring a light-weight, coordinated approach to fair capacity and bandwidth allocation.

In this work, we take a network-centric, topology-aware approach to chip-level quality-of-service. To reduce performance, area, and energy overheads of network-wide QOS support, we propose to isolate shared resources, such as memory controllers and accelerator units, into dedicated regions of the chip. Hardware QOS support in the network and at the end-points is provided only inside these regions. As shown in Figure 1(b), a richly-connected MECS topology [START_REF] Grot | Express cube topologies for on-chip interconnects[END_REF] is used to connect each node to the shared region via a dedicated point-to-multipoint channel, ensuring physical isolation of memory traffic outside of the QOS-protected shared region. The majority of nodes on the chip, encompassing cores and cache memories, have no QOS support and enjoy significant savings in router cost and complexity.

The focal point of this paper is the organization of the shared region. Specifically, we consider the interaction between network topology and quality-of-service -a first such study, to the best of our knowledge. We evaluate three network topologies with preemptive QOS support [START_REF] Grot | Preemptive virtual clock: a flexible, efficient, and cost-effective qos scheme for networks-on-chip[END_REF] to understand their respective performance, fairness, and overheads. The topologies are mesh, MECS, and Destination Partitioned Subnets (DPS), a new topology we propose in this work. DPS uses a dedicated subnetwork for each destination node, enabling complexity-effective routers with low delay and energy overhead. All topologies show good fairness and experience little slowdown in the face of adversarial workloads with high preemption rates. On synthetic workloads, DPS consistently matches or outperforms mesh-based topologies in terms of performance, energyefficiency, and preemption resilience. MECS has lower latency and better energy efficiency on long-distance communication patterns, but is inferior to DPS on shorter transfers.

In the remainder of this paper, Section 2 describes our proposed system architecture; Section 3 focuses on the organization of the shared region from the network perspective; Section 4 details the evaluation methodology; Section 5 presents the experimental results; Sections 6 and 7 describe related work and conclude the paper.

2 Topology-aware Quality-of-Service

Preliminaries

Our target system is a 256-tile CMP. Figure 1(a) shows the baseline organization, scaled down to 64 tiles for clarity. To reduce the number of network nodes, we employ fourway concentration as proposed by Balfour and Dally [START_REF] Balfour | Design tradeoffs for tiled CMP on-chip networks[END_REF]. This organization reduces the number of network nodes to 64 by integrating four terminals1 at a single router via a fast crossbar switch. The nodes are interconnected via a richly connected MECS topology [START_REF] Grot | Express cube topologies for on-chip interconnects[END_REF]. MECS uses point-tomultipoint channels that fully connect a given node to other nodes along each of four cardinal directions. The topology leverages abundant wire resources found on a chip and is further aided by concentration, as the bandwidth across a concentrated node edge is greater than across a single tile.

In the figure, shaded nodes correspond to shared on-chip memory controllers (MCs). The rest of the nodes integrate core and cache tiles. Cores can be identical or heterogeneous, and the ratio of core to cache tiles can vary. Assuming private last-level caches (an assumption we will later relax), the memory controllers and the on-chip network are the only shared resources in the figure. To ensure fair access to memory bandwidth for all tiles, each of the 64 on-chip routers needs to provide some QOS support, in addition to a QOS mechanism at the memory controllers. Assuming XY dimension-order routing, the routers must fairly provision row link bandwidth among the four terminals and regulate access to the shared column links, which become a contended resource as multiple tiles in a given row send packets to the same MC tile.

Unfortunately, per-hop QOS support is a weighty proposition. Traditional network QOS schemes require per-flow buffering at each router, which is undesirable in an onchip setting due to the associated area and energy overheads. Recent work in on-chip QOS proposed relaxing the buffer requirements by using preemption to guarantee freedom from priority inversion [START_REF] Grot | Preemptive virtual clock: a flexible, efficient, and cost-effective qos scheme for networks-on-chip[END_REF]. While the scheme, called Preemptive Virtual Clock (PVC), significantly reduces cost over prior work, it nevertheless incurs certain overheads and preemption-induced performance degradations that may limit its ability to scale to large on-chip networks.

Topology-aware Architecture

In this work, we take a topology-aware approach to onchip QOS. We observe that network QOS support is required to ensure fairness of only the shared links. In a Supporting efficient on-chip data sharing requires internode communication, which again raises the possibility of interference among the different network streams. To avoid re-introducing QOS support outside of the shared resource regions, we require the operating system (hypervisor) to place all threads of a given application (VM) in a convex region, called a domain, also shown in Figure 1(b). The resulting organization permits data sharing among the set of nodes making up the domain, as the convex shape ensures that all cache traffic stays within the allocated region. The scheme combines the benefits of increased capacity of a shared cache with physical isolation that precludes the need for cache-level hardware QOS support. An access to the shared region, such as a cache miss traveling to a memory controller, first traverses a non-shared MECS channel along the row in which the access originated before switching to a QOS-protected column containing shared resources.

Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q (a) Baseline QOS-enabled CMP Q Q Q Q VM #1 VM #2 VM #3 (
Summarizing, our approach to chip-wide quality-ofservice requires three components: a richly-connected topology that eliminates the need for QOS in non-shared regions, hardware QOS logic inside the shared regions, and operating system support. We now provide additional details on the role of each of these.

Topology: A topology with a high degree of connectivity is integral to our scheme, as it provides physical isolation for traffic between non-adjacent routers. We exploit the connectivity to limit the extent of hardware QOS support to a few confined regions of the chip, which can be reached from any node without going through any other node. With XY dimension-order routed MECS topology, the shared resource regions must be organized as columns in the twodimensional grid of nodes to maintain the single-hop reachability property. We chose the MECS topology due to its attractive scalability properties and low router complexity; other topologies, such as the flattened butterfly [START_REF] Kim | Flattened butterfly topology for on-chip networks[END_REF], could also be employed.

Shared regions:

The one or more regions containing shared resources serve two purposes. The first is to ensure fair access to shared resources, which requires hardware QOS support at both routers and end-points within each column. The second is to support inter-process or inter-VM communication, which also necessitates QOS protection at the routers, and is easily accommodated by our scheme.

To understand why inter-process/VM traffic must flow through shared regions, consider the case of VM #1 and VM #3 in Figure 1(b) sharing content. If the data originates at the top-left node of VM #1 and is destined for the bottomright node of VM #3, packets will route in dimension-order toward VM #2, switching dimensions at its top node. With no QOS support at the turn node, inter-VM traffic can cause considerable interference with respect to local traffic of VM #2. To avoid such scenarios, we require all inter-process and inter-VM communication to transit via the QOS-equipped shared columns. While the requirement may result in nonminimal routes, as is the case in the example above, the expected frequency of such transfers is relatively low and they are typically not performance critical. As such, we anticipate latency and energy overheads incurred by additional network hops of inter-domain transfers to be modest.

OS support:

We rely on the operating system to provide the following three services:

• Schedule threads from only the same application or virtual machine to run on a given node.

• Allocate compute and storage resources (core and cache tiles) to an application or virtual machine, ensuring that the domain complies with the convex shape property.

• Assign bandwidth or priorities to flows, defined at the granularity of a thread, application, or virtual machine, by programming memory-mapped registers at QOS-enabled routers and resources in shared regions.

As existing operating systems already provide scheduling services and support different process priorities, the additional requirements are very modest, requiring little developer effort and negligible run-time overhead.

Shared Region Organization

QOS support

Historically, high-performance network QOS schemes have required per-flow queues at each router node to isolate and schedule packets from different flows [START_REF] Golestani | Congestion-free communication in high-speed packet networks[END_REF][START_REF] Kim | Rotating combined queueing (RCQ): bandwidth and latency guarantees in low-cost, highperformance networks[END_REF][START_REF] Demers | Analysis and simulation of a fair queueing algorithm[END_REF][START_REF] Zhang | Virtual clock: a new traffic control algorithm for packet switching networks[END_REF]. As a result, these schemes had considerable router buffer requirements and scheduling complexity in larger network configurations, resulting in area, energy, and latency overheads that are undesirable in an on-chip setting. In response, researchers have recently proposed new approaches that try to address QOS requirements of on-chip networks [START_REF] Lee | Globallysynchronized frames for guaranteed quality-of-service in on-chip networks[END_REF][START_REF] Grot | Preemptive virtual clock: a flexible, efficient, and cost-effective qos scheme for networks-on-chip[END_REF].

In this work, we adopt Preemptive Virtual Clock (PVC) as our preferred QOS mechanism [START_REF] Grot | Preemptive virtual clock: a flexible, efficient, and cost-effective qos scheme for networks-on-chip[END_REF]. PVC does not require per-flowing queuing, necessitating just enough virtual channels to cover the round-trip credit latency of a link. PVC features a light-weight packet prioritization function evolved from the Virtual Clock scheme [START_REF] Zhang | Virtual clock: a new traffic control algorithm for packet switching networks[END_REF]. Routers track each flow's bandwidth consumption, which is scaled by a flow's assigned rate of service to yield packet priority. To limit the extent to which a flow's present priority is affected by its past bandwidth consumption, all bandwidth counters are periodically cleared. The interval between two successive flushes is called a frame, whose duration determines the granularity of the scheme's guarantees.

Since routers in a PVC network do not have dedicated buffer resources for each flow, lower priority packets may block packets with higher dynamic priority, a situation termed priority inversion. PVC detects priority inversion situations and resolves them through preemption of lowerpriority packets. Discarded packets require retransmission, which is supported through a combination of a per-source window of outstanding packets and a dedicated ACK network used to acknowledge every delivered and discarded packet. In addition to the low-bandwidth, low-complexity ACK network, PVC requires per-flow state at each router node, whose size is proportional to the number of nodes on a chip and the number of router ports. Key limitation to PVC's performance scalability is its preemptive nature, which can reduce throughput at high packet discard rates. Although our work targets large CMP configurations, we only require QOS support in shared resource columns, thereby limiting resource and potential performance overheads of PVC.

Topologies

MECS is a natural consideration for the shared region as it is already deployed in the rest of the chip. To reduce complexity, MECS employs asymmetric routers with the number of row or column inputs equal to the number of nodes in a dimension (eight, in our case), but just two network outputs per dimension (one in each direction). Multiple input ports share a crossbar port, thereby reducing switch degree and arbitration complexity.

Figure 2(a) shows a PVC-enabled MECS router. While the MECS topology is a good fit for the main network, it may be less than ideal in the shared region. The reason is the increased complexity of a MECS router once QOS support is added to it. Long channel spans and the need to segregate flows necessitate considerable buffer and virtual channel (VC) resources to cover large round-trip credit latencies, even in the absence of per-flow queuing. In addition, scheduling complexity is quite high due to the presence of multiple VCs at each input port, multiple input ports from each direction, and multiple directions that may all be competing for a given output port.

In comparison, a mesh router has fewer input ports and short channel spans, leading to lower buffer requirements and simpler arbitration than its MECS counterpart. However, a basic mesh topology does not fully leverage the rich wire resources available on a chip, motivating researchers

North Inputs Local inputs

Preemption logic

East output

Preemption logic

West output

Preemption logic

South output

Preemption logic to propose replicated networks [START_REF] Balfour | Design tradeoffs for tiled CMP on-chip networks[END_REF]. Replication increases the channel count by the degree of replication at the cost of additional router resources. Although prior work argues that full replication that requires new router instances for the additional channels can significantly reduce crossbar complexity, it ignores the buffering, wire, and arbitration overhead of bypass paths to and from the terminals [START_REF] Grot | Express cube topologies for on-chip interconnects[END_REF][START_REF] Balfour | Design tradeoffs for tiled CMP on-chip networks[END_REF]. In this work, we consider a variant of the approach that replicates the channels and associated router ports, but maintains a single monolithic crossbar at each node. Figure 2(b) shows an example network with twice the channel count of a basic mesh.

North output

In addition to mesh and MECS topologies, we also consider a new network organization called Destination Partitioned Subnets (DPS). DPS uses a dedicated lowcomplexity network for each destination node; a 4-node DPS topology is shown in Figure 2(c). The motivation behind DPS is to combine low router complexity of the mesh topology with improved wire utilization and long-distance communication efficiency found in MECS.

A packet in a DPS network goes through routing, priority computation, and crossbar traversal only at source and destination nodes. Because each subnet maps to a unique destination node, once a packet enters a subnet, it does not need to be routed or switched to a different output port with respect to other packets until it reaches the destination -a subnet's end-point. Intermediate hops require only two input ports (network and local) and a single output port; as a result, a simple 2:1 mux suffices as a switch (Figure 2(c)). Flow tracking and priority computation are not required at intermediate hops either, eliminating the overheads of flow state queries and updates. In all, these simplifications enable a single-cycle router traversal for packets at intermediate DPS hops.

DPS source and destination nodes look similar to those in a mesh. Source-side, a larger number of output ports in a DPS router (one port per subnet) results in increased crossbar complexity. Tables containing flow state also have to be scaled up, since bandwidth utilization is maintained for each output port separately. Arbitration complexity is not affected, since the different output arbiters operate independently. Destination-side, DPS and mesh routers are virtually identical.

Experimental Methodology

We use an in-house simulator to evaluate the different topologies for the QOS-enabled shared region, which is embodied within a single column of an 8x8 grid of nodes in a large scale CMP. Figure 1(b) shows a diagram of a scaled down 4x4 grid with a similar organization. One column in the middle of the grid is devoted to shared resources with one terminal per node; the rest of the network employs 4way concentration and a MECS interconnect. To focus our study, we examine only the network within the shard column. Our target is 32-nm process technology with on-chip voltage of 0.9 V.

Each router in the shared region has some topologydependent number of column inputs, in addition to a terminal port and seven row inputs from MECS channels in east and west directions. Up to four MECS inputs (those arriving from the same direction) share a single crossbar port. Similarly, three ports are devoted to east, west, and terminal outputs, in addition to the north/south ports.

Table 1 summarizes the simulated configurations, consisting of mesh, MECS, and DPS topologies. We consider three mesh variants with 1x (baseline), 2x, and 4x replication. In all cases, we assume 128-bit channel width; thus, MECS, DPS, and mesh x4 have equal bisection bandwidth, while mesh x1 and mesh x2 topologies feature more com- We faithfully model all aspects of each topology's router pipeline, which consists of virtual channel allocation (VA) and crossbar traversal (XT). We use virtual cut-through flow control [START_REF] Kermani | Virtual cut-through: a new computer communication switching technique[END_REF], transferring an entire packet upon its acquisition of a virtual channel, and eliminating the crossbar arbitration stage as a result. Arrival of higher-priority packets does not interrupt an on-going transfer, but a preemption does. Due to the large number of ports and virtual channels, MECS routers require 2 cycles for arbitration; mesh and DPS arbitrate in a single cycle. All topologies enjoy a single-cycle crossbar traversal. As explained in Section 3.2, intermediate hops in a DPS network have just one cycle of router latency due to elimination of crossbar traversal. In all topologies, source hops require an additional cycle for route and priority computation; look-ahead routing and priority reuse [START_REF] Grot | Preemptive virtual clock: a flexible, efficient, and cost-effective qos scheme for networks-on-chip[END_REF] are subsequently employed to remove these stages from the critical path.

We assume two packet sizes, corresponding to request and reply traffic classes, but do not specialize the input buffers. With virtual cut-through switching, each virtual channel needs to hold the largest possible packet, which is four flits in our network. Worst-case traffic consists of a stream of single-flit request packets, each of which requires a separate VC. We use this as a guideline for provisioning the number of VCs at each input port based on the topologyspecific round-trip credit latency; Table 1 lists the buffer organizations for each topology. In a MECS network, we do not employ location-dependent buffer sizing, provisioning buffers uniformly in all routers. In all topologies, we reserve one VC at each network port for rate-compliant traffic to reduce preemption incidence [START_REF] Grot | Preemptive virtual clock: a flexible, efficient, and cost-effective qos scheme for networks-on-chip[END_REF].

For area and energy evaluation, we use a combination of analytical models, Orion [START_REF] Kahng | ORION 2.0: A fast and accurate NoC power and area model for early-stage design space exploration[END_REF], and CACTI [START_REF] Muralimanohar | Optimizing NUCA organizations and wiring alternatives for large caches with CACTI 6.0[END_REF]. We modify Orion to more accurately model our crossbar configurations. In CACTI, we add support for modeling small SRAM arrays with data flow typical of a NOC router. We assume both input buffers and flow state tables are SRAM-based.

Evaluation Results

We evaluate the different topologies for the shared region (column) on area efficiency, latency and throughput, fairness, susceptibility to preemptions, and energy efficiency.

Area

Our area model accounts for three primary components of overhead: input buffers, crossbar switch fabric, and flow state tables. Figure 3 shows the router area overhead of different topologies. The dotted line shows buffer capacity allocated to row inputs, identical across all topologies.

Mesh x1 is the most area-efficient topology as its routers have fewer ports than those in other organizations, leading to a compact crossbar and small buffer overhead. Mesh x4, on the other hand, has the largest footprint, mostly due to a crossbar that is roughly four times larger than that in a baseline mesh. Crossbar area is proportional to the product of input and output port counts, which is 5x5 in mesh x1 and 11x11 in mesh x4, explaining the overhead of the 4way replicated mesh. As expected, the MECS topology has the largest buffer footprint, but a compact crossbar thanks to just one switch port per direction (Figure 2(a)). DPS router's area overhead is comparable to that of MECS, as DPS has smaller buffer requirements but a larger crossbar due to the large number of column outputs at each node. Mesh x2 has a similar router footprint to MECS and DPS but supports just half the bisection bandwidth. In all networks, PVC's per-flow state is not a significant contributor to area overhead.

Performance

Figure 4 shows the performance of different schemes on two traffic patterns: uniform random and tornado. The former is benign, with different sources stochastically spreading traffic across different destinations, while the latter is a challenge workload for rings and meshes which concentrates the traffic from each source on a destination half-way across the dimension [START_REF] Dally | Principles and Practices of Interconnection Networks[END_REF]. While these workloads are not directly correlated to expected traffic patterns in the shared region of a CMP, they stress the network in different ways and provide insight into the behavior of different topology options. Each curve corresponds to a topology and shows the load on the X axis and average packet latency on the Y axis.

Not surprisingly, the baseline mesh and mesh x2 topologies show the worst throughput due to lower bisection bandwidth relative to the other network configurations. Mesh x4 has competitive performance on random traffic, but is unable to load balance the tornado pattern. Both MECS and DPS show good scalability on tornado thanks to their ability to isolate traffic between each source-destination pair. On both workloads, DPS matches the throughput of MECS with just a fraction of the latter's buffer resources. In general, throughput is constrained in these topologies by asymmetry between the number of input and output ports at each node. Adding switch ports would improve throughput at the cost of additional switch area and energy.

On both traffic patterns, MECS and DPS enjoy lower average packet latency than mesh topologies. Meshes are slower due to the multi-cycle router traversals at each intermediate hop. A MECS network has deeper router pipelines than a mesh, but avoids all intermediate hops. The DPS topology has shallow mesh-like router pipelines at source and destination nodes with single-cycle intermediate hop traversals. On random traffic, MECS and DPS have nearly identical latency and are 13% faster than any mesh variant. On tornado, the longer communication distance fa-vors MECS, as it is able to amortize larger router delay over longer flight time for a 7% latency advantage over DPS (24% versus mesh). While longer path lengths favor MECS, shorter communication distances favor DPS, which has lower router delay.

Preemptions rate (not shown) was measured to be quite low for all topologies. In saturation, the baseline mesh had the highest discard rate with nearly 7% of all packets replayed under random traffic; MECS had the lowest rate of just 0.04%. Mesh x2, mesh x4, and DPS replayed 5%, 0.1%, and 2% of their packets, respectively. By comparison, tornado traffic generated fewer preemptions for each topology. In general, topologies with greater channel resources show better immunity to preemptions on these permutations.

QOS and Preemption Impact

To measure the impact of the topology on fairness, we first use a hotspot traffic pattern, following the methodology of Grot et al. [START_REF] Grot | Preemptive virtual clock: a flexible, efficient, and cost-effective qos scheme for networks-on-chip[END_REF]. The terminal port of node 0 acts as a hotspot to which all injectors (including the row inputs at node 0) stream traffic. Prior work showed that without QOS support, sources closer to the hotspot get a disproportionately large share of the bandwidth, while distant nodes are essentially starved [START_REF] Lee | Globallysynchronized frames for guaranteed quality-of-service in on-chip networks[END_REF][START_REF] Grot | Preemptive virtual clock: a flexible, efficient, and cost-effective qos scheme for networks-on-chip[END_REF].

Table 2 shows the results of the experiment. In general, all topologies provide good fairness on this workload, and the results are in line with the original PVC work. The maximum deviation from the mean across the topologies is 1.9%, corresponding to the DPS network. MECS has the strongest fairness with a maximum deviation of just 0.3% and standard deviation of 0.1%. Unlike performance results in the previous section, fairness seems to correlate with network buffer capacity, as topologies with more buffering provide better fairness.

Preemption rate is very low, as preemption-throttling mechanisms built into PVC are quite effective here. Key among these is the reserved flit quota that each source is allocated. In each frame interval, the first N flits from each source are non-preemptable, where N is a function of the rate assigned to the source and the frame duration. With all sources transmitting, virtually all packets fall under the reserved cap, throttling preemptions.

To measure the impact of preemptions on fairness and performance, we crafted two adversarial workloads. Both are based on the hotspot traffic pattern, but with only a subset of sources communicating, ensuring that the reserved quota is exhausted early in the frame, triggering preemptions thereafter.

In Workload 1, only the terminal port at each of the eight nodes sends traffic toward the hotspot. With eight sources, the average injection rate must not exceed 12.5% to prevent saturation. We provision the sources with equal priorities, but widely different rates, ranging from 5% to 20%; the average is around 14%, guaranteeing high network contention. Under max-min fairness, a standard definition for fairness [START_REF] Dally | Principles and Practices of Interconnection Networks[END_REF], sources with average injection rate under 12.5% should get their full requested share of network bandwidth; the rest of the bandwidth must be iteratively partitioned among the remaining communicating sources. In a PVC-enabled network operating in saturation, the arrival of a new packet at a source with a low injection rate will often trigger a sequence of preemptions as the packet travels toward the destination. Preemptions occur because the new packet has a higher priority relative to others, and when buffers are scarce, PVC discards lower priority packets to ensure forward progress by higher priority ones.

Figure 5(a) shows the percentage of all packets that experience a preemption and the total number of hop traversals that are wasted and need to be replayed. To normalize the comparison, we convert the hop count in a MECS network to the corresponding number of hops in a mesh based on the communication distance. Note that a single packet may be preempted multiple times; each such occurrence is counted as a separate event. In general, we see that the fraction of preempted packets is greater than the fraction of replayed hops, which occurs because most preemptions occur close to or right at the source node, before all of the victim's flits have been transferred. The sole exception to this trend is the MECS topology, whose fraction of discarded hops is equal to that of discarded packets. We believe this occurs due to the topology's rich buffer resources, which greatly diminish the likelihood of a packet being preempted in the middle of a transfer. Since replayed hops reduce network throughput and increase energy consumption, reducing hop-level replay is more important than lowering the packet discard metric. The mesh x1 and DPS topologies incur the fewest number of replayed hops (9%), closely followed by MECS (10%). In DPS, all of the traffic is concentrated on a single subnet, mimicking the behavior and performance of the baseline mesh topology. The mesh x2 and mesh x4 topologies show the worst preemption rates, with over 28% of all messages (24% hops) replayed. The reason behind such poor performance is the thrashing that results as flows traveling on parallel networks converge at the destination node.

Figure 6(a) shows the impact of preemptions on the performance of different topologies by measuring the slowdown compared to preemption-free execution in the same topology with per-flow queuing. The slowdown is less than 5%, demonstrating that preemptions have small impact on the completion time of the workload. The figure also shows the deviation from the expected throughput based on maxmin fairness; the thick blue bar shows the average across all nodes while the error bars plot the range of deviation for individual sources. All topologies show comparable behavior with the average deviation across all nodes under 1%. DPS enjoys the smallest range of deviations among individual sources, indicating good throughput fairness.

In constructing Workload 2, we attempted to stress the MECS topology, as it has significantly larger buffer resources compared to meshes and DPS. The general approach is identical to that of Workload 1; the only difference is in the set of injectors. For this workload, we activated all eight injectors at node 7 (the farthest from the hotspot) to pressure one downstream MECS port and one additional injector at node 6 to ensure contention at the destination output port. nificantly, with few preemptions past the source nodes. The replicated mesh topologies, however, continue to experience high incidence of preemption, as packets that diverge at the source and travel on different networks can trigger preemptions once they reach the destination and compete for the same output port.

Energy efficiency

We evaluate the energy efficiency of different topologies by deriving the energy expended accessing the input buffers, traversing the crossbar, as well as querying and updating flow state at each network hop. We break down router energy overhead of different topologies based on the type of network hop -source, intermediate, or destinationsince the cost of each varies. We also show the energy expended for a 3-hop packet traversal, roughly equivalent to the average communication distance on random traffic.

Figure 7 summarizes our findings. Although mesh topologies have modest per-hop energy overhead, they are least efficient on a 3-hop route requiring four router traversals. In contrast, MECS has energy-hungry routers that are undesirable with intra-node or nearest-neighbor traffic. Despite a small crossbar footprint, MECS has the most energy-hungry switch stage among the evaluated topologies due to the long input lines feeding the crossbar (see Figure 2(a)). However, MECS achieves good efficiency on 3-hop traffic by avoiding intermediate hops. DPS combines meshlike efficiency at source and destination nodes with low energy expense at intermediate hops due to elimination of crossbar traversals, resulting in 17% energy savings over mesh x1 and 33% over mesh x4. On the 3-hop pattern, MECS and DPS have nearly identical router energy consumption. Longer communication distances improve the efficiency of the MECS topology, while near-neighbor patterns favor mesh and DPS configurations.

Related Work

A number of researchers have studied cache-level quality-of-service with the objective of reducing the impact of inter-application interference on performance [START_REF] Suh | A new memory monitoring scheme for memory-aware scheduling and partitioning[END_REF][START_REF] Iyer | CQoS: a framework for enabling QoS in shared caches of CMP platforms[END_REF][START_REF] Nesbit | Virtual private caches[END_REF]. We take a different view of QOS in this work, as our goal is providing cost-effective support for service-level agreement (SLA) guarantees and improved security through isolation of cache resources. Previous work in cache QOS also ignores the shared on-chip interconnect that is used to access the cache.

Recent work examining fairness and interference reduction in memory controllers [START_REF] Mutlu | Stall-time fair memory access scheduling for chip multiprocessors[END_REF][START_REF] Mutlu | Parallelism-aware batch scheduling: Enhancing both performance and fairness of shared dram systems[END_REF] is complementary to ours, since a comprehensive on-chip QOS solution requires quality-of-service support at shared end-points, including memory controllers. Other researchers proposed coordinated policies to partition cache space and memory bandwidth [START_REF] Ebrahimi | Fairness via source throttling: a configurable and high-performance fairness substrate for multi-core memory systems[END_REF][START_REF] Bitirgen | Coordinated management of multiple interacting resources in chip multipro-cessors: A machine learning approach[END_REF]. None of these efforts consider the on-chip interconnect and its impact on end-to-end quality-of-service.

At the on-chip interconnect level, application-aware prioritization mechanisms [START_REF] Das | Application-aware prioritization mechanisms for on-chip networks[END_REF] can improve performance metrics of multiple applications sharing a substrate, but do not provide hard guarantees. Rijpkema et al. proposed a router that combines guaranteed and best-effort service levels through a combination of circuit and wormhole switching [START_REF] Rijpkema | Trade offs in the design of a router with both guaranteed and best-effort services for networks on chip[END_REF]. This approach requires explicit segregation of memory traffic based on the expected service level, provides no guarantees to best effort traffic, and fails to take topology into account.

Finally, Marty and Hill advocate mapping VMs to dedicated regions on a chip to facilitate data sharing while reducing interference across VMs [START_REF] Marty | Virtual hierarchies to support server consolidation[END_REF]. Our work relies on a similar approach, but goes farther by providing low-cost QOS support that could be used to provide service-level guarantees at the chip level. Coherence optimizations described by Marty and Hill are orthogonal to our work and may potentially benefit from efficient broadcast and multicast enabled by MECS.

Conclusion

The industry is on a trend of increasing the degree of integration in chip multiprocessors, with parts containing hundreds of cores, cache tiles, and other resources likely to appear in the near future. Meanwhile, increasing reliance on server consolidation and cloud-based services raises the possibility that multiple workloads, users, or even competing businesses will share resources on a common execution substrate. To enable performance isolation, security, and SLA guarantees on a die, CMPs must incorporate hardware QOS mechanisms. Unfortunately, quality-of-service support at each node of a highly-integrated CMP may be expensive due to area, energy, and performance overheads associated with today's QOS schemes.

In this work, we propose reducing the various costs of chip-wide QOS support via a topology-aware approach. Our scheme isolates shared resources in dedicated, QOSenabled regions of the chip, allowing designers to forego QOS hardware in the larger part of the die containing cores and caches. We leverage the richly-connected MECS topology to provide single-hop access from any source node to the QOS-protected shared region with physical isolation from memory traffic of other nodes.

We evaluated several topologies as potential interconnect candidates inside the shared region with PVC-based QOS support. All topologies show good fairness, but differ widely in their preemptive behavior, performance, area overhead, and energy efficiency. The most promising configurations are based on MECS and Destination Partitioned Subnets (DPS), a new topology explored in this work. DPS uses a light-weight dedicated network for each destination node, combining low router complexity of mesh topologies with MECS-like energy and delay efficiency on multihop transfers. On synthetic traffic, DPS matches or outperforms mesh-based topologies in terms of performance, energy efficiency and preemption resilience. Compared to MECS, DPS has better energy efficiency and lower latency on shorter transfers, while MECS is superior on longer routes. These initial results are promising and motivate further research into the interaction between topology and onchip quality-of-service.

Acknowledgement

We wish to thank Naveen Muralimanohar for his help with CACTI, and Emmett Witchel for clarifying the mechanics of inter-process communication.

This research is supported by NSF CISE Infrastructure grant EIA-0303609 and NSF grant CCF-0811056.

Figure 2 .

 2 Figure 2. Shared region details.

Figure 3 .

 3 Figure 3. Router area overhead.

Figure 4 .

 4 Figure 4. Latency and throughput on synthetic traffic.

Figures 5 ( 2 Figure 5 .

 525 Figure5. Fraction of all packets that experience preemption events and hop traversals that are wasted as a result of preemptions.

Figure 6 .

 6 Figure 6. Slowdown due to preemptions and deviation from the expected throughput.

Figure 7 .

 7 Figure 7. Router energy expended per flit for different topologies.

Figure 1. 64-tile CMP with 4-way concentration and MECS interconnect. Light nodes integrate core and cache tiles; shaded nodes show memory controllers; 'Q' indicates hardware QOS support at the node.

  b) Topology-aware QOS approach

	MECS network, most sharing occurs within the column
	links, as row links are shared by just the four terminals of
	a source node. We can eliminate row-link QOS support by
	co-scheduling only "friendly" threads (i.e., those belonging
	to the same application or virtual machine) onto a node. To
	reduce the extent of QOS support in columns, we propose to
	isolate shared resources by placing them into one or more
	dedicated columns, called shared regions, and only provi-
	sion QOS support inside these regions, eliminating cost and
	performance overheads of QOS in the rest of the network.
	Our approach relies on richly-connected MECS channels to
	ensure single-hop access into shared regions, thereby by-
	passing intermediate nodes and eliminating them as sources
	of interference in unprotected regions of the network. Fig-
	ure 1(b) shows the proposed scheme.

Table 1 . Shared region topology details

 1

	Network	8 nodes (one column), 16-byte links,
		1 cycle wire delay between adjacent routers,
		DOR routing, virtual cut-through flow control
	QOS	Preemptive Virtual Clock (50K cycle frame)
	Benchmarks hotspot, uniform random, and tornado;
		1-and 4-flit packets, stochastically generated
	Topologies	mesh x1, mesh x2, mesh x4, MECS, DPS
	mesh	6 VCs per network port,
		2 stage pipeline (VA, XT)
	MECS	14 VCs per network port,
		3 stage pipeline (VA-local, VA-global, XT)
	DPS	5 VCs per network port,
		2 stage pipeline as source/dest (VA, XT),
		1 stage pipeline at intermediate hops
	common	4 flits/VC; 1 injection VC, 2 ejection VCs,
		1 reserved VC at each network port
	pact routers in exchange for less bisection bandwidth. Wire
	delay is one cycle between adjacent routers. All topologies
	use PVC for QOS support.

Table 2 .

 2 Relative throughput of

different QOS schemes, in flits (%).

		mean min (% of mean) max (% of mean) std dev (% of mean)
	mesh x1 4,184	4,134 (98.8%)	4259 (101.8%)	39.1 (0.9%)
	mesh x2 4,197	4,148 (98.8%)	4256 (101.4%)	27.6 (0.7%)
	mesh x4 4,221	4,167 (98.7%)	4278 (101.4%)	30.1 (0.7%)
	MECS	4,193	4,180 (99.7%)	4203 (100.2%)	4.9 (0.1%)
	DPS	4,188	4,125 (98.5%)	4266 (101.9%)	44.4 (1.1%)

A node refers to a network node, while a terminal is a discrete system resource, such as a core, cache tile, or memory controller, that has a dedicated port at a network node.


Sébastien Krut
email: krut@lirmm.fr.

M Benoit

E Dombre

F Pierrot

Keywords: Exoskeleton, orthosis, passive force balancer

This paper presents MoonWalker, a lower limb exoskeleton able to sustain part of a user's bodyweight. This orthosis can be used for rehabilitation, to help people having weak legs, or to help those suffering from a broken leg, to walk. It can also be used as an assistive device helping people carrying heavy loads. Its main characteristic is that a passive force balancer provides the force to sustain bodyweight. An actuator is also required, but is used only to shift that force the same side as the leg in stance. Consequently, MoonWalker requires very low energy to work on flat terrains. That motor can provide also a part of the energy to climb stairs or slopes. We believe that this approach can help improving energetic autonomy of lower limb exoskeletons.

I. INTRODUCTION

ESEARCH in actuated exoskeleton devices began truly in the late 1960s [START_REF] Dollar | Lower Extremity Exoskeletons and Active Orthoses: Challenges and State-of-the-Art[END_REF]. Exoskeletons are defined as standalone anthropomorphic active mechanical devices that are "worn" by an operator and work in concert with the operator's movements. This paper will focus on lower-limb exoskeletons only. Exoskeletons are mainly used to increase performance of able-bodied wearer [START_REF] Zoss | Biomechanical design of the Berkeley lower extremity exoskeleton (BLEEX)[END_REF] (e.g. for military applications), and to help disabled people to retrieve some motion abilities [START_REF] Goffer | Gait-locomotor Apparatus[END_REF] (such exoskeletons are called "active ortheses" in the medical field). The Lokomat [START_REF] Colombo | Treadmill Training of Paraplegic Patients using a Robotic Orthosis[END_REF], used in gait-recovery therapies, constitutes another category of exoskeletons, as it is neither portable nor stand-alone. Let's cite the most famous lower-limbs exoskeletons up-todate and discuss their features: -The BLEEX from U.C. Berkeley [START_REF] Zoss | Biomechanical design of the Berkeley lower extremity exoskeleton (BLEEX)[END_REF] was designed to help soldiers to carry heavy packs. Each leg is actuated by three hydraulic cylinders and can provide upwards and forward/reverse assistance. The control approach is based on feet pressure signals.

-ReWalk [START_REF] Goffer | Gait-locomotor Apparatus[END_REF] developed at Haifa University, Israel, is a fully actuated electrical exoskeleton, allowing paraplegic people to walk using crutches. It follows a gait pattern copied by the patient limbs.

-HAL-3 [START_REF] Kawamoto | Power assist system HAL-3 for gait disorder person[END_REF] developed at Tsukuba University is targeted for both performance augmenting and rehabilitative purposes. Actuation is electrical. Its control is based on EMG signals that are processed for the exoskeleton to copy legs motions and to amplify forces.

-The Walking-Assist from Honda [START_REF] Ashihara | Walking Assistant Device[END_REF] looks like an ergonomic stool equipped with robotized legs. It helps by supporting bodyweight to reduce the load on the user's legs while walking, going up and down stairs, and in semicrouching positions. It uses electrical actuators and control relies on feet pressure signals. Assistance is only provided in the upward direction, and users have to move their leg forward to make the device walk. This choice resulted form a compromise: keeping the device simple while offering enough assistance to reduce user's muscular fatigue for daily tasks. In this paper a new exoskeleton, called MoonWalker, is presented (see Fig. 1). Contrary to all above mentioned exoskeletons, MoonWalker is quasi-passive, requiring very low energy to work. In this sense, it is very comparable with the elastic exoskeleton presented in [START_REF] Cherry | An Elastic Exoskeleton for Assisting Human Running[END_REF] that only uses friction-lock clutches for control. However this elastic exoskeleton uses one controlled spring per leg whereas MoonWalker uses a single force balancer coupled for the two legs.

MoonWalker, a Lower Limb Exoskeleton able to Sustain Bodyweight using a Passive Force Balancer

Sébastien Krut, Michel Benoit, Etienne Dombre and François Pierrot R It offers the same kind of assistance the Walking-Assist from Honda does: it exerts an upward force on the user's pelvis to reduce the forces supported by his legs. The main difference consists in the way it is actuated: weight is compensated using a passive force balancer, and a lowpower actuator is used for control, loading the exoskeleton on the side where the user's leg is in stance, and lowering it on the side where the user's leg is in swing. This strategy allows increasing energy autonomy, which is the weak point of most actual active exoskeletons.

Section II describes the concept of MoonWalker. Section III is about control. Section IV describes the prototype, and shows some experimental results. Some possible improvements for that device are proposed in the conclusion.

II. DESIGN CONCEPT

A. Main concept The main idea, when designing MoonWalker, was to propose an exoskeleton able to exert an upward vertical force on the user's pelvis in order to lighten the forces in his/her legs due to bodyweight. Doing that would reduce the load on his/her leg muscles and joints in the hip, knee, and ankle (another approach to achieve this goal is that in [START_REF] Banala | A Gravity Balancing Leg Orthosis for Robotic Rehabilitation[END_REF] which uses a gravity balancing leg orthosis connected to a trolley). Hence, it could benefit disabled persons with weak legs, or suffering from a broken leg. It could also benefit able-bodied people that must remain in uncomfortable semicrouching positions for long times, or wiling to carry heavy loads, by supporting that extra load. Its name, MoonWalker, was chosen as the user's legs feel only a part of body weight, giving the impression that gravity is reduced, such as on the Moon. Another important idea when designing MoonWalker was that, to offer that assistance on flat terrains, a passive device could be used as the gravitational potential energy of the bodyweight remains almost the same. This idea is illustrated on Fig. 2, where the user is connected to a trolley via a force balancer which exerts a constant upwards vertical force on the pelvis, lightening the forces due to his bodyweight on his legs. A force balancer is inserted between the trolley and user's pelvis, instead of a rigid link, to allow some vertical motion, the one naturally generated when walking. That device is very similar to baby jumpers. The only difference is that, baby jumpers use classical springs or rubber bands, whereas on that device, a force balancer is used (acting like a spring exerting the same reaction force whatever its extension is). This results in a smooth assistance that avoids bouncing inconsiderately. Next step is to find a solution to get rid of the trolley. We thought of a way to replace it by two sticks running along each leg (see Fig. 3) in order to provide an exoskeleton, that is to say, a mechanical device that is "worn" by the patient. The difficulty is that the force balancer has to be connected to the stick running on the side of the leg in stance only, in order to let the other leg swing freely with the other stick being disconnected from the force balancer. To achieve this goal, a driven device able to share the force produced by the balancer on the two sticks in a continuous manner (from 0% to 100% right/left leg force repartition) was imagined. It consists in a beam connected at its ends to the two sticks using passive Universal joints (U). The beam is actuated to slide from right to left using an actuated Prismatic joint (P). The linear actuator is connected using a passive Revolute joint (R) to a vertical cart. That cart is guided relatively to user's pelvis using a passive P joint, and is connected to the force balancer attached to user's pelvis.

Rigid frame running the long of the leg in stance

The sticks are connected to rigid shoes in order to transmit the forces passing through the sticks to the ground using Spherical joints (S). U and S joints where selected for the sticks ends in order to transmit the balancer force to the ground and to allow the shoes to move freely. Note that, with such a device, the forces transmitted to the ground are not purely vertical, but are lined up with the line going from the center of the spherical joints to the center of the universal joints. In practice, this is not a big issue while the main components of these forces remain vertical. This phenomenon also occurs on the Walking-Assist from Honda [START_REF] Ashihara | Walking Assistant Device[END_REF]. However, thanks to the use of arc-shaped guide tracks located below user's seat, the assisting forces are always directed toward the user's pelvis, which corresponds roughly to the user's centre of gravity. Fig. 5 shows the force sharing device in two different configurations. When the two legs are in stance, the beam is centered sharing the balancer force equally on both sticks.

When the left leg is in stance and the right leg is in swing, the beam needs to be shifted to the right. Hence, for that configuration, the force balancer does not exert any force on the right stick, which allows the right leg to move freely. Additionally, the left stick transmits all the force delivered by the balancer to the ground. The opposite configuration (beam shifted to the left) allows the opposite walking pattern: right leg in stance and left leg in swing. ) on the system. O is its application point. Note that, as the force delivered by the balancer is not transmitted directly to the beam, but through the serial chain made with the passive R-P-R joints, only the component of that force being lined-up with v , the vector perpendicular to the direction u of the P joint that guides the beam, is transmitted to the beam:

cart beam balancer cart ( ) F F v v → → = ⋅ (1)
where ⋅ denotes the scalar product.

As sticks are very long, it is assumed that they won't tilt much in the coronal plane, and that they remain lined up with the force balancer. Consequently, the forces they can transmit always remain in the same direction: left stick l F F j = and right stick r F F j =

. L and R are their application points (see Fig. 6). x , the displacement of the center C of the beam satisfies OC x u = , where [ , ] x l l ∈and 2l is the beam length. Consequently, OL ( ) l x u =and OR ( )

l x u = + .
The force actuator F provided by the actuator for the system to remain in static equilibrium, is collinear with u , the direction vector of the prismatic joint that guides the beam:

F F F F + + + = (2) left right stick stick OL OR 0 F F × + × = (3)
where × denotes the cross-product. This leads to: ). Note that relations (5) do not depend on the value of θ , meaning that the way the beam is tilted does not modify force repartition.

a b sin( ) F F θ = - (4)

D. Power consumption estimation

To estimate power consumption, the mechanical energy required by the actuator to move the beam is computed:

actuator a b sin( ) W F dx F dx F dx δ θ = - ⋅ = - = (6)
where W δ denotes the infinitesimal work that the actuator needs to provide a small displacement of dx length.

Assuming that when the beam is moved, θ remains constant, integrating relation (6) for x going from left to right leads to:

b x l x l W W F h δ = =- = = Δ ∫ (7)
with 2 sin( ) h l θ Δ = being the vertical elevation of the cart. Note that this computation does witness mechanical energy only. Energy consumption estimation might be quite different from this value, as system efficiency is not taken into account, and as the power system might not be able to benefit from regenerative energy coming from the actuator. However the interpretation of result [START_REF] Ashihara | Walking Assistant Device[END_REF] shows that: (i) When the users walk of flat terrains, a transition from one foot to the other does not modify vertical the elevation of the cart the height ( 0 h Δ ). Hence power consumption is very low, as the power supply as to deliver only the energy to overcome friction and dynamics effects. (ii) When the user climbs a slope or a stair of height h Δ , the power supply has to provide the energy corresponding to b E F h = Δ only. During descents, regenerative energy provided by the actuator can be sent back to the power supply.

The rest of the energy required to sustain part of the user bodyweight, is delivered by the passive force balancer, and does not require any energy coming from the power supply.

III. CONTROL

Control of MoonWalker is very simple: it consists in measuring the way the user shares his reaction force on the ground between his two legs and to drive the force sharing device accordingly to distribute the balancer force between the two sticks in the same proportion.

Measuring the way the user shares his reaction force on the ground between his two legs is done using pressure sensors located below his two feet. Driving the force sharing device is done controlling an actuator that can move the main beam right and left. The global control scheme is given in Fig. 7. Three pressure sensors where placed in each shoe below user's feet: one under the heel and two on front. As we encountered some practical difficulties with the FSR (Force Sensing Resistors) raw signals had to be preprocessed (normalized and filtered) in order to obtain acceptable data. G s s

A. Preprocessing raw pressure sensors data

ω ω = + : 0 ˆˆ[ ] ( [ ] [ 1]
)

i e i i p k a T p k p k ω = + - (9)
where Doing this preprocessing step led to ˆi p being reliable measures of the pressures exerted by the users legs on he ground. ). Achieving our goal (that is to say, moving the device the proper way according to user's force repartition) can be done easily by choosing ε η = , and computing the reference d θ of the PID controller using (13). However, to be sure that the leg in swing would be totally unloaded even if some small signals are measured by the pressure sensors of the leg in swing, a symmetrical monotonic function f , ( )

B. Generating the input value for the beam position

f ε η = ,
with two steps of length τ at its ends, was built. The part of the function between 1 τ -+ and 1 τ

was chosen to be a degree-3 polynomial that would join the two steps in a tangent manner (see Fig. 8), leading to a continuously differentiable 1 C function for f :

if 1 η τ ≤ -+ , then 1 ε = - (14) 1 1
τ η τ -+ < < -, then

IV. PROTOTYPE DESCRIPTION AND EXPERIMENTS

A prototype of MoonWalker was built to test the effectiveness of the concept (see Fig. 1). A harness was chosen to interface the force sharing device with the user's pelvis. A simple spring balancer was selected for the force balancer (6080B from Prevost). However, due to its force limitation (8 kgF maximum only), a hoist was built using a set of pulleys, to amplify to force by four (see the cable running from the vertical cart to the harness four times, in Fig. 9). The maximum force that can be compensated on user's leg is than 32 kgF (~320 N), which correspond to a ratio between a third an a half of a normal's user bodyweight.

A rotary motor (EC-powermax 30 from Maxon Motor) equipped with a gear reducer (GP 42C from Maxon Motor) and an absolute encoder (AD36 from Hengstler) was selected to drive the beam thanks to a pinion and a rack. The motor, the reduction ratio of the gear box, and the diameter of the pinion were chosen in order for the beam to be able to deliver a force up to 400 N, a force higher than the one provided by the force balancer. The force sharing device was implemented as close as possible from user's body in order to limit as much as possible disturbing torques due to the lever arms between user's center of mass and the application points of the forces transmitted by the sticks. The sticks were curved in order not to interfere with the user's legs. The length of the beam was chosen to be 300 mm, in order to be long enough to allow the user to climb stairs, and short enough not to collide with user's arms. Control hardware was not embedded at this stage of the project. It consists in a PC running a real time OS (RTX from Ardence), a homemade PCI IO board and a mains-powered amplifier (Accelus ASP-055-18 from Copley Controls) connected to MoonWalker using an extension lead.

Early tests demonstrate qualitatively the effectiveness of the proposed concept (see the corresponding video). The ablebodied user was able to walk easily without feeling uncomfortable due to the device. Assistance was really noticeable, when standing in semi-crouching positions, and when walking up-stairs.

V. CONCLUSION AND FURTHER WORK

The whole report here is the first phase of a research project aiming at offering an exoskeleton requiring very low powerconsumption. So far, conceptual design has been proven up to the functional level only. Assessment of its usefulness for patient related purposes will be done in the next future. It will be verified that the device reduces load on leg muscles and joints (in the hips, knees, and ankles) by supporting a portion of the user's bodyweight. The main characteristic of Moonwalker is that a passive force balancer provides the force to sustain bodyweight. It is controlled using an actuator that requires very low energy to work on flat terrains, as it is used only to shift that force the same side as the leg in stance. That motor is able also to provide a part of the energy to climb stairs or slopes. We believe that this approach can help improving energetic autonomy of lower limb exoskeletons.

Fig. 1 .

 1 Fig. 1. Pictures of MoonWalker, a lower-limb exoskeleton able to sustain part of user's weight based on passive gravity compensation

Fig. 2 .

 2 Fig. 2. Bodyweight compensation principle illustrated with a trolley equipped with a force balancer

Fig. 3 .

 3 Fig. 3. Bodyweight compensation principle illustrated with two poles running along each leg

  sharing device descriptionThe force sharing device, able to share the force exerted by the balancer between the two sticks in a continuous manner, is depicted in Fig.4.

Fig. 4 .

 4 Fig. 4. Kinematic and implementation schemes of MoonWalker. S, U, P, R stand for Spherical, Universal, Prismatic and Revolute joints, respectively.

Fig. 5 .

 5 Fig. 5. Illustration of the force sharing device for two different configurations: two legs in stance (beam centered), left leg in stance (beam shifted to the right)

Fig. 6 .

 6 Fig. 6. Scheme of the force sharing device: the force produced by the balancer is shared between the right and the left sticks depending on x. Pr. and Rev. stand for Prismatic and Revolute joints, respectively.

  equilibrium principle on the beam at point O leads to:

Fig. 7 .

 7 Fig. 7. Control scheme of MoonWalker

  was done using a simple digital filter, computed applying the classical Z-transformation to the first order

  way force is shared between the two legs, was built this way: meaning that all pressure is exerted on the left foot, and 1 η = that all pressure is exerted on the right foot.Driving the force sharing device is done based on the value of η .The force sharing device is controlled in position using a simple PID acting on the actuator joint coordinate d θ .

Fig. 8 .

 8 Fig. 8. Illustration of the function linking feet pressure repartition and the position of the beam of the force sharing device.

Fig. 9 .

 9 Fig. 9. CAD view of the practical implementation of the force sharing device

  Normalizing of pressure signals was done to get the very same response from every sensor:

				min min i i p p max ˆi i i p p p -= -	(8)
	where i p ,	i ∈	{1,..., 6}	represents the signals recorded from
	FSR number i, min i p and max i p	represent their extreme values
	obtained during a calibration phase, ˆi p represent the
	normalized values ( ˆ[0, 1]

  Next step was to compute the "global" pressures exerted by the left and right foot on the ground, left

					p and right p	. That
	step was not investigated much and the mean value of the
	sensors for each foot was taken:
	left p	=	1 p p p 2 3 ˆˆ( + +	) / 3	(10)
	right p	=	4 p p p 5 6 ˆˆ( + +	) / 3	(11)
	where 1 p , 2 p , 3 p correspond to the left foot and 4 p , 5 p ,
	6 p , to the right foot.
	The linear function	[ 1,1]