Jonathan Chappelon

On the multiplicative order of a n modulo n

Keywords: 2000 Mathematics Subject Classifications: 11A05, 11A07, 11A25 multiplicative order, projective multiplicative order, balanced Steinhaus triangles, Steinhaus triangles, Molluzzo's Problem

Let n be a positive integer and α n be the arithmetic function which assigns the multiplicative order of a n modulo n to every integer a coprime to n and vanishes elsewhere. Similarly, let β n assign the projective multiplicative order of a n modulo n to every integer a coprime to n and vanishes elsewhere. In this paper, we present a study of these two arithmetic functions. In particular, we prove that for positive integers n 1 and n 2 with the same square-free part, there exists an exact relationship between the functions α n 1 and α n 2 and between the functions β n 1 and β n 2 . This allows us to reduce the determination of α n and β n to the case where n is square-free. These arithmetic functions recently appeared in the context of an old problem of Molluzzo, and more precisely in the study of which arithmetic progressions yield a balanced Steinhaus triangle in Z/nZ for n odd.

Introduction

We start by introducing some notation relating to the order of certain elements modulo n. For every positive integer n and every prime number p, we denote by v p (n) the padic valuation of n, i.e., the greatest exponent e 0 for which p e divides n. The prime factorization of n may then be written as n = p∈P p vp (n) , where P denotes the set of all prime numbers. We denote by rad(n) the radical of n, i.e., the largest square-free divisor of n, namely rad(n) = p∈P p|n p.

For every positive integer n and every integer a coprime to n, we denote by O n (a) the multiplicative order of a modulo n, i.e., the smallest positive integer e such that a e ≡ 1 (mod n), namely O n (a) = min {e ∈ N * | a e ≡ 1 (mod n)} and we denote by R n (a) the multiplicative remainder of a modulo n, i.e., the multiple of n defined by R n (a) = a On(a) -1.

The multiplicative order of a modulo n also corresponds with the order of the element π n (a), where π n : Z -։ Z/nZ is the canonical surjective morphism, in the multiplicative group (Z/nZ) * , the group of units of Z/nZ. Note that O n (a) divides ϕ(n), ϕ being the Euler's totient function.

For every positive integer n, we define and denote by α n the arithmetic function

α n : Z -→ N a -→ O n (a n ) , for all gcd(a, n) = 1; 0, otherwise,
where gcd(a, n) denotes the greatest common divisor of a and n, with the convention that gcd(0, n) = n. Observe that, for every a coprime to n, the integer α n (a) divides ϕ(n)/ gcd(ϕ(n), n). This follows from the previous remark on O n (a) and the equality

α n (a) = O n (a n ) = O n (a)/ gcd(O n (a), n).
For every positive integer n and every integer a coprime to n, we denote by PO n (a) the projective multiplicative order of a modulo n, i.e., the smallest positive integer e such that a e ≡ ±1 (mod n), namely

PO n (a) = min {e ∈ N * | a e ≡ ±1 (mod n)} .
The projective multiplicative order of a modulo n also corresponds with the order of the element π n (a) in the multiplicative quotient group (Z/nZ) * /{-1, 1}.

For every positive integer n, we define and denote by β n the arithmetic function

β n : Z -→ N a -→ PO n (a n ) , for all gcd(a, n) = 1; 0, otherwise.
Observe that we have the alternative

α n = β n or α n = 2β n .
In this paper, we study in detail these two arithmetic functions. In particular, we prove that, for every positive integers n 1 and n 2 such that rad(n 1 )|n 2 and

n 2 |n 1 , if v 2 (n 1 ) 1; 2 rad(n 1 )|n 2 and n 2 |n 1 , if v 2 (n 1 ) 2, the integer α n 1 (a) (respectively β n 1 (a)) divides α n 2 (a) (resp. β n 2 (a)
), for every integer a. More precisely, we determine the exact relationship between the functions α n 1 and α n 2 and between β n 1 and β n 2 . We prove that we have

α n 1 (a) = α n 2 (a) gcd α n 2 (a), gcd(n 1 ,Rn 2 (a)) n 2
for all gcd(a, n 1 ) = 1 in Theorem 2.5 of Section 2 and that we have

β n 1 (a) = β n 2 (a) gcd β n 2 (a), gcd(n 1 ,Rn 2 (a)) n 2
for all gcd(a, n 1 ) = 1 in Theorem 3.3 of Section 3. Thus, for every integer a coprime to n, the determination of α n (a) is reduced to the computation of α rad(n) (a) and

R rad(n) (a) if v 2 (n) 1 and of α 2 rad(n) (a) and R 2 rad(n) (a) if v 2 (n) 2.
These theorems on the functions α n and β n are derived from Theorem 2.6 of Section 2, which states that

O n 1 (a) = O n 2 (a) • n 1 gcd(n 1 , R n 2 (a)) ,
for all integers a coprime to n 1 and n 2 . This result generalizes the following theorem of Nathanson which, in the above notation, states that for every odd prime number p and for every positive integer k, we have the equality

O p k (a) = O p (a) • p k gcd(p k , R p (a))
for all integers a not divisible by p. Theorem 3.6 of [START_REF] Nathanson | Elementary Methods in Number Theory[END_REF]. Let p be an odd prime, and let a = ±1 be an integer not divisible by p. Let d be the order of a modulo p. Let k 0 be the largest integer such that a d ≡ 1 (mod p k 0 ). Then the order of a modulo p k is d for k = 1, . . . , k 0 and dp k-k 0 for k k 0 .

For every finite sequence S = (a 1 , . . . , a m ) of length m 1 in Z/nZ, we denote by ∆S the Steinhaus triangle of S, that is the finite multiset of cardinality m+1 2 in Z/nZ defined by

∆S = i k=0 i k a j+k 0 i m -1 , 1 j m -i .
A finite sequence S in Z/nZ is said to be balanced if each element of Z/nZ occurs in its Steinhaus triangle ∆S with the same multiplicity. For instance, the sequence (2, 2, 3, 3) of length 4 is balanced in Z/5Z. Indeed, as depicted in Figure 1, its Steinhaus triangle is composed by each element of Z/5Z occuring twice. Note that, for a sequence S of length m 1 in Z/nZ, a necessary condition on m for S to be balanced is that the integer n divides the binomial coefficient m+1 . In 1976, John C. Molluzzo [START_REF] Molluzzo | Steinhaus graphs[END_REF] posed the problem to determine whether this necessary condition on m is also sufficient to guarantee the existence of a balanced sequence. In [START_REF] Chappelon | On a problem of Molluzzo concerning Steinhaus triangles in finite cyclic groups[END_REF], it was proved that, for each odd number n, there exists a balanced sequence of length m for every m ≡ 0 or -1 (mod α n (2) • n) and for every m ≡ 0 or -1 (mod β n (2) • n). This was achieved by analyzing the Steinhaus triangles generated by arithmetic progressions. In particular, since β 3 k (2) = 1 for all k 1, the above result implies a complete and positive solution of Molluzzo's Problem in Z/nZ for all n = 3 k .

The arithmetic function α n

The table depicted in Figure 2 gives us the first values of α n (a) for every positive integer n, 1 n 20, and for every integer a, -20 a 20. n\a 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 3 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 0 1 2 4 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 5 1 4 4 2 0 1 4 4 2 0 1 4 4 2 0 1 4 2 0 6 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 7 1 3 6 3 6 2 0 1 3 6 3 6 2 0 1 3 3 6 2 8

1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 9 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 0 1 2 10 1 0 2 0 0 0 2 0 1 0 1 0 2 0 0 0 0 1 0 11 1 10 5 5 5 10 10 10 5 2 0 1 10 5 5 5 10 10 10 5 12 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 13 1 12 3 6 4 12 12 4 3 6 12 2 0 1 12 3 4 12 12 14 1 0 3 0 3 0 0 0 3 0 3 0 1 0 1 0 0 3 0 15 1 4 0 2 0 0 4 4 0 0 2 0 4 2 0 1 0 2 0 16 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 17 1 8 16 4 16 16 16 8 8 16 16 16 4 16 8 2 1 8 16 18 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 19 1 18 18 9 9 9 3 6 9 18 3 6 18 18 18 9 2 0 1 20 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 0 1 0 The positive integer α n (a) seems to be difficult to determine. Indeed, there is no general formula known to compute the multiplicative order of an integer modulo n but, however, we get the following helpful propositions. Lemma 2.1. Let n 1 and n 2 be two positive integers such that rad(n 1 ) = rad(n ). Then, an integer a is coprime to n 1 if, and only if, it is also coprime to n 2 .

Proof. This follows from the definition of the greatest common divisor of two integers and from the definition of the radical of an integer. Proposition 2.2. Let n 1 and n 2 be two positive integers such that rad(n 1 )|n 2 and n 2 |n 1 . Then, for every integer a, the integer α n 1 (a) divides α n 2 (a).

Proof. If a is not coprime to n 1 and n 2 , then, by definition of the functions α n and α n 2 and by Lemma 2.1, we have

α n 1 (a) = α n 2 (a) = 0.
Suppose that a is coprime to n 1 and n 2 . If v p (n 1 ) = 1 for all prime factors p of n 1 , then n 2 = n 1 . Otherwise, let p be a prime factor of n 1 such that v p (n 1 ) 2. We shall show that α n 1 (a) divides α n 1 /p (a). By definition of α n 1 /p (a), there exists an integer u such that

a α n 1 /p (a)• n 1 p = 1 + u • n 1 p .
Therefore, by the binomial theorem, we have

a α n 1 /p (a)•n 1 = a α n 1 /p (a)• n 1 p p = 1 + u • n 1 p p = 1 + u • n 1 + p k=2 p k • u k • n 1 p k .
Since v p (n 1 ) 2, it follows that (n 1 /p) k is divisible by n 1 for every integer k 2 and so

a α n 1 /p (a)•n 1 ≡ 1 (mod n 1 ).
Hence α n 1 (a) divides α n 1 /p (a). This completes the proof.

An exact relationship between α n 1 (a) and α n 2 (a), for every integer a coprime to n 1 and n 2 , is determined at the end of this section. We first settle the easy prime power case.

Proposition 2.3. Let p be a prime number and let a be an integer. Then we have

α p k (a) = O p (a)
for every positive integer k.

Proof. Let k be a positive integer. If a is not coprime to p, then we have α p k (a) = α p (a) = 0. Suppose now that a is coprime to p. By Proposition 2.2, the integer α p k (a) divides α p (a). It remains to prove that α p (a) divides α p k (a). The congruence

a α p k (a)•p k ≡ 1 (mod p k ) implies that a α p k (a)•p k ≡ 1 (mod p),
and hence, by Fermat's Little Theorem, it follows that

a α p k (a)•p ≡ a α p k (a)•p k ≡ 1 (mod p).
Therefore α p (a) divides α p k (a). Finally, we have

α p k (a) = α p (a) = O p (a p ) = O p (a).
This completes the proof.

Remark. If p = 2, then, for every positive integer k, we obtain

α 2 k (a) = O 2 (a) =
0, for a even; 1, for a odd.

Proposition 2.4. Let n 1 and n 2 be two coprime numbers and let a be an integer. Then α n 1 n 2 (a) divides lcm(α n 1 (a), α n 2 (a)), the least common multiple of α n 1 (a) and α n 2 (a).

Proof. If gcd(a, n 1 n 2 ) = 1, then gcd(a, n 1 ) = 1 or gcd(a, n 2 ) = 1 and so

α n 1 n 2 (a) = lcm(α n 1 (a), α n 2 (a)) = 0.
Suppose now that gcd(a, n 1 n 2 ) = 1 and hence that the integers a, n 1 and n 2 are coprime pairwise. Let i ∈ {1, 2}. The congruences

a αn i (a)•n i ≡ 1 (mod n i )
imply that a n 1 n 2 lcm(αn 1 (a),αn 2 (a)) ≡ 1 (mod n i ).

Therefore

α n 1 n 2 (a) divides lcm(α n 1 (a), α n 2 (a)
) by the Chinese remainder theorem.

Let By definition, we know that α n 1 (a) = α n 2 (a) = 0 for every integer a not coprime to n 1 and n 2 . We end this section by determining the exact relationship between α n 1 (a) and α n 2 (a) for every integer a coprime to n 1 and n 2 .

n
Theorem 2.5. Let n 1 and n 2 be two positive integers such that

rad(n 1 )|n 2 and n 2 |n 1 , if v 2 (n 1 ) 1; 2 rad(n 1 )|n 2 and n 2 |n 1 , if v 2 (n 1 ) 2.
Then, for every integer a coprime to n 1 and n 2 , we have

α n 1 (a) = α n 2 (a) gcd α n 2 (a), gcd(n 1 ,Rn 2 (a)) n 2
This result is a corollary of the following theorem.

Theorem 2.6. Let n 1 and n 2 be two positive integers such that

rad(n 1 )|n 2 and n 2 |n 1 , if v 2 (n 1 ) 1; 2 rad(n 1 )|n 2 and n 2 |n 1 , if v 2 (n 1 ) 2.
Then, for every integer a coprime to n 1 and n 2 , we have

O n 1 (a) = O n 2 (a) • n 1 gcd(n 1 , R n 2 (a))
.

The proof of this theorem is based on the following lemma.

Lemma 2.7. Let n be a positive integer and let a be an integer coprime to n. Let m be an integer such that rad(m)| rad n. Then, there exists an integer u m , coprime to n if m is odd, or coprime to n/2 if m is even, such that

a On(a)•m = 1 + u m • R n (a) • m.
Proof. We distinguish different cases based upon the parity of m. First, we prove the odd case by induction on m. If m = 1, then, by definition of the integer R n (a), we have

a On(a) = 1 + R n (a).
Therefore the assertion is true for m = 1. Now, let p be a prime factor of m and suppose that the assertion is true for the odd number m/p, i.e., there exists an integer u m/p , coprime to n, such that

a On(a)• m p = 1 + u m/p • R n (a) • m p .
Then, we obtain

a On(a)•m = a On(a)• m p p = 1 + u m/p • R n (a) • m p p = 1 + u m/p • R n (a) • m + p-1 k=2 p k u m/p • R n (a) • m p k + u m/p • R n (a) • m p p = 1 + u m/p + p-1 k=2 p k p • (u m/p ) k • R n (a) k-1 • m p k-1 + +(u m/p ) p • R n (a) p-1 p • m p p-1 • R n (a) • m = 1 + u m • R n (a) • m. Since n divides R n (a) which divides u m -u m/p = p-1 k=2 p k p • (u m/p ) k • R n (a) k-1 • m p k-1 + (u m/p ) p • R n (a) p-1 p • m p p-1
, it follows that gcd(u m , n) = gcd(u m/p , n) = 1. This completes the proof for the odd case. Suppose now that n and m are even. We proceed by induction on v 2 (m). If v 2 (m) = 1, then m/2 is odd and by the first part of this proof,

a m 2 •On(a) = 1 + u m/2 • m 2 • R n (a)
where u m/2 is coprime to n and hence to n/2. Now assume that v 2 (m) > 1 and that

a m 2 •On(a) = 1 + u m/2 • m 2 • R n (a)
with u m/2 coprime to n/2. Then, we obtain

a On(a)•m = a On(a)• m 2 2 = 1 + u m/2 • R n (a) • m 2 2 = 1 + u m/2 • R n (a) • m + u m/2 • R n (a) • m 2 2 = 1 + u m/2 + (u m/2 ) 2 • R n (a) 2 • m 2 • R n (a)m = 1 + u m • R n (a) • m.
Since n/2 divides R n (a)/2 which divides u m -u m/2 , it follows that gcd(u m , n/2) = gcd(u m/2 , n/2) = 1. This completes the proof.

We are now ready to prove Theorem 2.6.

Proof of Theorem 2.6. The proof is by induction on the integer n 1 /n 2 . If n 1 = n 2 , then we have

n 1 gcd(n 1 , R n 2 (a)) = n 1 gcd(n 1 , R n 1 (a)) = n 1 n 1 = 1, since R n 1 (a)
is divisible by n 1 , and thus the statement is true. Let p be a prime factor of n 1 and n 2 such that n 2 divides n 1 /p and suppose that

O n 1 /p (a) = O n 2 (a) • n 1 /p gcd(n 1 /p, R n 2 (a))
.

First, the congruence a On 1 (a) ≡ 1 (mod n 1 )

implies that a On 1 (a) ≡ 1 (mod

n 1 p )
and so O n 1 /p (a) divides O n 1 (a). We consider two cases.

First Case: v p (n 1 ) v p (R n 2 (a)). Since n 2 divides n 1 /p, it follows that O n 2 (a) divides O n 1 /p (a). Let r = O n 1 /p (a)
On 2 (a) . Hence

R n 1 /p (a) = a O n 1 /p (a) -1 = a On 2 (a)•r -1 = a On 2 (a) -1 r-1 k=0 a kOn 2 (a) = R n 2 (a) r-1 k=0 a kOn 2 (a)
and so R n 1 /p (a) is divisible by R n 2 (a). This leads to

v p (n 1 ) v p (R n 2 (a)) v p R n 1 /p (a) .
Therefore R n 1 /p (a) is divisible by n 1 and hence we have

a O n 1 /p (a) = 1 + R n 1 /p (a) ≡ 1 (mod n 1 ). This implies that O n 1 (a) = O n 1 /p (a). Moreover, the hypothesis v p (n 1 ) v p (R n 2 (a)) implies that gcd(n 1 /p, R n 2 (a)) = gcd(n 1 , R n 2 (a))/p. Finally, we obtain O n 1 (a) = O n 1 /p (a) = O n 2 (a) • n 1 /p gcd(n 1 /p, R n 2 (a)) = O n 2 (a) • n 1 gcd(n 1 , R n 2 (a))
.

Second Case: v p (n 1 ) > v p (R n 2 (a)). If v 2 (n 1 ) 1, then (n 1 /p)/ gcd(n 1 /p, R n 2 (a)) is odd. Otherwise, if v 2 (n 1 ) 2, then v 2 (n 2 )
2 and every integer coprime to n 2 /2 is also coprime to n 2 . In both cases, v 2 (n 1 ) 1 or v 2 (n 1 ) 2, we know, by Lemma 2.7, that there exists an integer u, coprime to n 2 , such that

a O n 1 /p (a) = a On 2 (a)• n 1 /p gcd(n 1 /p,Rn 2 (a)) = 1 + u • R n 2 (a) • n 1 /p gcd(n 1 /p, R n 2 (a)) = 1 + u • R n 2 (a) gcd(n 1 /p, R n 2 (a)) • n 1 p . As v p (R n 2 (a)) v p (n 1 /p), it follows that R n 2 (a)/ gcd(n 1 /p, R n 2 (a)
) is coprime to p, and hence

O n 1 /p (a) is a proper divisor of O n 1 (a) since a O n 1 /p (a) ≡ 1 (mod n 1 ).
Moreover, by Lemma 2.7 again, there exists an integer u p such that

a O n 1 /p (a)•p = 1 + u p • R n 1 /p (a) • p ≡ 1 (mod n 1 ).
This leads to

O n 1 (a) = O n 1 /p (a) • p = O n 2 (a) • n 1 gcd(n 1 /p, R n 2 (a)) = O n 2 (a) • n 1 gcd(n 1 , R n 2 (a))
.

This completes the proof of Theorem 2.6.

We may view Theorem 2.6 as a generalization of Theorem 3.6 of [START_REF] Nathanson | Elementary Methods in Number Theory[END_REF], where n 2 = p is an odd prime number and n 1 = p k for some positive integer k. Note that the conclusion of Theorem 2.6 fails in general in the case where v 2 (n 1 ) 2 and n 2 = rad(n 1 ). For instance, for n 1 = 24 = 3 • 2 3 , n 2 = 6 = 3 • 2 and a = 7, we obtain that O n 1 (a) = 2 while O n 2 (a)n 1 / gcd(n 1 , R n 2 (a)) = 24/ gcd(24, 6) = 4.

We now turn to the proof of the main result of this paper.

Proof of Theorem 2.5. From Theorem 2.6, we obtain

α n 1 (a) = O n 1 (a n 1 ) = O n 1 (a) gcd(O n 1 (a), n 1 ) = O n 2 (a) • n 1 gcd(n 1 ,Rn 2 (a)) gcd O n 2 (a) • n 1 gcd(n 1 ,Rn 2 (a)) , n 1 = O n 2 (a) gcd(O n 2 (a), n 1 , R n 2 (a))
.

Thus,

α n 2 (a) α n 1 (a) = On 2 (a) gcd(On 2 (a),n 2 ) On 2 (a) gcd(On 2 (a),n 1 ,Rn 2 (a)) = gcd(O n 2 (a), n 1 , R n 2 (a)) gcd(O n 2 (a), n 2 ) = gcd O n 2 (a) gcd(O n 2 (a), n 2 ) , n 2 gcd(O n 2 (a), n 2 ) • gcd(n 1 , R n 2 (a)) n 2 .
Finally, since we have

gcd O n 2 (a) gcd(O n 2 (a), n 2 ) , n 2 gcd(O n 2 (a), n 2 ) = gcd(O n 2 (a), n 2 ) gcd(O n 2 (a), n 2 ) = 1, it follows that α n 2 (a) α n 1 (a) = gcd O n 2 (a) gcd(O n 2 (a), n 2 ) , gcd(n 1 , R n 2 (a)) n 2 = gcd α n 2 (a), gcd(n 1 , R n 2 (a)) n 2 .
Thus, the determination of α n is reduced to the case where n is square-free.

Corollary 2.8. Let n be a positive integer such that v 2 (n) 1. Then, for every integer a, coprime to n, we have

α n (a) = α rad(n) (a) gcd α rad(n) (a), gcd(n,R rad(n) (a)) rad(n)
.

Corollary 2.9. Let n be a positive integer such that v 2 (n) 2. Then, for every integer a, coprime to n, we have for every integer a coprime to n. There is no general formula known to compute α n (a)/β n (a) but, however, we get the following proposition.

α n (a) = α 2 rad(n) (a) gcd α 2 rad(n) (a), gcd(n,R 2 rad(n) (a)) 2 rad(n) . 3
Proposition 3.1. Let n 1 and n 2 be two positive integers such that rad(n 1 ) = rad(n 2 ).

Let a be an integer coprime to n 1 and n 2 . If v 2 (n 1 ) 1, then we have

α n 1 (a) β n 1 (a) = α n 2 (a) β n 2 (a) .
If v 2 (n 1 ) 2, then we have α n 1 (a) = β n 1 (a).

Proof. Let n 1 be a positive integer such that v 2 (n 1 ) 1 and a be an integer coprime to n 1 . Let p be an odd prime factor of n 1 such that v p (n 1 ) 2. We will prove that

α n 1 (a) β n 1 (a) = α n 1 /p (a) β n 1 /p (a) . If α n 1 (a) = 2β n 1 (a), then a βn 1 (a)•n 1 ≡ -1 (mod n 1 )
and thus

a βn 1 (a)•p• n 1 p ≡ -1 (mod n 1 p ).
This implies that α n 1 /p (a) = 2β n 1 /p (a). Conversely, if α n 1 /p (a) = 2β n 1 /p (a), then we have

a β n 1 /p (a)• n 1 p ≡ -1 (mod n 1 p ).
Since v p (n 1 ) 2, it follows that

a β n 1 /p (a)• n 1 p ≡ -1 (mod p)
and thus

a β n 1 /p (a)•n 1 +1 = 1--a β n 1 /p (a)• n 1 p p = 1 + a β n 1 /p (a)• n 1 p p-1 k=0 -a β n 1 /p (a)• n 1 p k ≡ 0 (mod n 1 ).
This implies that α n 1 (a) = 2β n 1 (a). Continuing this process we have

α n 1 (a) β n 1 (a) = α rad(n 1 ) (a) β rad(n 1 ) (a)
and since rad(n 1 ) = rad(n 2 ), α n 1 (a)

β n 1 (a) = α n 2 (a) β n 2 (a) .
Now, let n 1 be a positive integer such that v 2 (n 1 ) 2, and let a be a non-zero integer. Suppose that we have α n 1 (a) = 2β n 1 (a). Since

a βn 1 (a)•n 1 ≡ -1 (mod n 1 ) it follows that a βn 1 (a)• n 1 4 4 ≡ -1 (mod 4) in contradiction with a βn 1 (a)• n 1 4 4 ≡ 1 (mod 4). Thus α n 1 (a) = β n 1 (a).
If n is a prime power, then β n = β rad(n) , in analogy with Proposition 2.3 for α n .

Proposition 3.2. Let p be a prime number and let a be an integer. Then we have

β p k (a) = β p (a)
for every positive integer k.

Proof. This result is trivial for every integer a not coprime to p. Suppose now that a is coprime to p. For p = 2, then, by Proposition 3.1, we have

β 2 k (a) = α 2 k (a) = 1
for every positive integer k. For an odd prime number p 3, Proposition 3.1 and Proposition 2. for every positive integer k. This completes the proof.

Let Let a be an integer coprime to n 1 and n 2 . Then, we have Thus, as for α n , the determination of β n is reduced to the case where n is square-free. .

β

Figure 1 :

 1 Figure 1: The Steinhaus triangle of a balanced sequence in Z/5Z

2

 2

Figure 2 :

 2 Figure 2: The first values of α n (a)

  The arithmetic function β n First, we can observe that, by definition of the functions α n and β n , we have α n (a) = β n (a) = 0 for every integer a not coprime to n and α n (a) β n (a) ∈ {1, 2}

  3 lead toβ p k (a) = α p k (a) α p (a) • β p (a) = β p (a)

2 . 2 . 2 .

 222 n 1 (a) = β n 2 (a) gcd β n 2 (a), gcd(n 1 ,Rn 2 (a)) nProof. If v 2 (n 1 ) 1, then Theorem 2.5 and Proposition 3.1 lead toβ n 2 (a) β n 1 (a) = α n 2 (a) α n 1 (a) = gcd α n 2 (a), gcd(n 1 , R n 2 (a)) n Since v 2 (n 2 ) = v 2 (n 1 )1, it follows that gcd(n 1 , R n 2 (a))/n 2 is odd and hence, we haveβ n 2 (a) β n 1 (a) = gcd α n 2 (a), gcd(n 1 , R n 2 (a)) n 2 = gcd β n 2 (a), gcd(n 1 , R n 2 (a)) n If v 2 (n 1 ) 2, then β n 1 (a) = α n 1 (a)and β n 2 (a) = α n 2 (a) by Proposition 3.1 and the result follows from Theorem 2.5.

Corollary 3 . 4 .

 34 Let n be a positive integer such that v 2 (n) 1. Then, for every integer a, coprime to n, we haveβ n (a) = β rad(n) (a) gcd β rad(n) (a), gcd(n,R rad(n) (a)) rad(n).Corollary 3.5. Let n be a positive integer such that v 2 (n) 2. Then, for every integer a, coprime to n, we haveβ n (a) = β 2 rad(n) (a) gcd β 2 rad(n) (a),gcd(n,R 2 rad(n) (a)) 2 rad(n)

  1 and n 2 be two positive integers such that rad(n 1 )|n 2 and n 2 |n 1 , if v 2 (n 1 ) 1; 2 rad(n 1 )|n 2 and n 2 |n 1 , if v 2 (n 1 ) 2.

  n 1 and n 2 be two positive integers such that rad(n 1 )|n 2 and n 2 |n 1 , if v 2 (n 1 ) 1; 2 rad(n 1 )|n 2 and n 2 |n 1 , if v 2 (n 1 ) 2. It immediately follows that β n 1 (a) = β n 2 (a) = 0 for every integer a not coprime to n 1 and n 2 . Finally, we determine the relationship between β n 1 (a) and β n 2 (a) for every integer a coprime to n 1 and n 2 . Theorem 3.3. Let n 1 and n 2 be two positive integers such that rad(n 1 )|n 2 and n 2 |n 1 , if v 2 (n 1 ) 1; 2 rad(n 1 )|n 2 and n 2 |n 1 , if v 2 (n 1 ) 2.

Acknowledgments

The author would like to thank Shalom Eliahou for his help in preparing this paper. He also thanks the anonymous referee for its useful remarks.


Keywords: Array-OL, parallelism, data parallelism, multidimensional signal processing, mapping Array-OL, parallélisme, parallélisme de données, traitement de signal multidimensionnel, placement

This paper presents the Array-OL specification language. It is a high-level visual language dedicated to multidimensional intensive signal processing applications. It allows to specify both the task parallelism and the data parallelism of these applications on focusing on their complex multidimensional data access patterns. This presentation includes several extensions and tools developed around Array-OL during the last few years and discusses the mapping of an Array-OL specification onto a distributed heterogeneous hardware architecture.

Introduction

Computation intensive multidimensional applications are predominant in several application domains such as image and video processing or detection systems (radar, sonar). In general, intensive signal processing applications are multidimensional. By multidimensional, we mean that they primarily manipulate multidimensional data structures such as arrays. For example, a video is a 3D object with two spatial dimensions and one temporal dimension. In a sonar application, one dimension is the temporal sampling of the echoes, another is the enumeration of the hydrophones and others such as frequency dimensions can appear during the computation. Actually, such an application manipulates a stream of 3D arrays.

Dealing with such applications presents a number of difficulties:

• Very few models of computation are multidimensional.

• The patterns of access to the data arrays are diverse and complex.

• Scheduling these applications with bounded resources and time is challenging, especially in a distributed context.

When dealing with parallel heterogeneous and constrained platforms and applications, as it is the case of embedded systems, the use of a formal model of computation (MoC) is very useful. Edwards et al. [START_REF] Edwards | Design of embedded systems: Formal models, validation, and synthesis[END_REF] and more recently Jantsch and Sander [START_REF] Jantsch | Models of computation and languages for embedded system design[END_REF] have reviewed the MoCs used for embedded system design. These reviews classify the MoCs with respect to the time abstraction they use, their support for concurrency and communication modeling. In our application domain there is little need for modeling state as the computations are systematic, the model should be data flow oriented. On the contrary, modeling parallelism, both task and data parallelism, is mandatory to build efficient implementations. More than a concrete representation of time, we need a way to express precedence relations between tasks. We focus on a high level of abstraction where the multidimensional data access patterns can be expressed. We do not look for a programming language but for a specification language allowing to deal with the multidimensional arrays easily. The specification has to be deadlock free and deterministic by construction, meaning that all feasible schedules compute the same result. In their review of models for parallel computation [START_REF] Skillicorn | Models and languages for parallel computation[END_REF] Skillicorn and Talia classify the models with respect to their abstraction level. We aim for the second most abstract category which describes the full potential parallelism of the specification (the most abstract category does not even express parallelism). We want to stay at a level that is completely independent on the execution platform to allow reuse of the specification and maximal search space for a good schedule.

As far as we know, only two MoCs have attempted to propose formalisms to model and schedule such multidimensional signal processing applications: MDSDF (MultiDimensional Synchronous Dataflow) [START_REF] Chen | Design and implementation of a multidimensional synchronous dataflow environment[END_REF][START_REF] Lee | Multidimensional streams rooted in dataflow[END_REF][START_REF] Praveen | Multidimensional synchronous dataflow[END_REF][START_REF] Kumar | Scheduling Techniques for Synchronous and Multidimensional Synchronous Dataflow[END_REF] and Array-OL (Array Oriented Language) [START_REF] Demeure | An Array Approach for Signal Processing Design[END_REF][START_REF] Demeure | Array-OL : Proposition d'un formalisme tableau pourle traitement de signal multi-dimensionnel[END_REF] . MDSDF and its follow-up GMDSDF (Generalized MDSDF) have been proposed by Lee and Murthy. They are extensions of the SDF model proposed by Lee and Messerschmitt [START_REF] Lee | Static scheduling of synchronous data flow programs for digital signal processing[END_REF][START_REF] Lee | Synchronous Data Flow[END_REF]. Array-OL has been introduced by Thomson Marconi Sonar and its compilation has been studied by Demeure, Soula, Dumont et al. [START_REF] Amar | Projection of the Array-OL specification language onto the Kahn process network computation model[END_REF][START_REF] Demeure | Array-OL : Proposition d'un formalisme tableau pourle traitement de signal multi-dimensionnel[END_REF][START_REF] Dumont | Spécification Multidimensionnelle pour le traitement du signal systématique[END_REF][START_REF] Soula | Principe de Compilation d'un Langage de Traitement de Signal[END_REF][START_REF] Soula | Compilation principle of a specification language dedicated to signal processing[END_REF]. Array-OL is a specification language allowing to express all the parallelism of a multidimensional application, including the data parallelism, in order to allow an efficient distributed scheduling of this application on a parallel architecture. The goals of these two propositions are similar and although they are very different on their form, they share a number of principles such as:

• Data structures should make the multiple dimensions visible.

• Static scheduling should be possible with bounded resources.

• The application domain is the same: intensive multidimensional signal processing applications.

A detailed comparison of these two models is available in [START_REF] Dumont | Another multidimensional synchronous dataflow: Simulating Array-OL in ptolemy II[END_REF]. An other language worth mentioning is Alpha, proposed by Mauras [START_REF] Mauras | Alpha : un langage équationnel pour la conception et la programmation d'architectures parallèles synchrones[END_REF], a functional language based on systems of recurrent equations [START_REF] Karp | The organization of computations for uniform recurrence equations[END_REF]. Alpha is based on the polyhedral model, which is extensively used for automatic parallelization and the generation of systolic arrays. Alpha shares some principles with Array-OL:

• Data structures are multidimensional: union of convex polyhedra for Alpha and arrays for Array-OL.

• Both languages are functional and single assignment.

With respect to the application domain, arrays are sufficient and more easily handled by the user than polyhedra. Some data access patterns such as cyclic accesses are more easily expressible in Array-OL than in Alpha. And finally, Array-OL does not manipulate the indices directly. In the one hand that restricts the application domain but in the other hand that makes it more abstract and more focused on the main difficulty of intensive signal processing applications: data access patterns.

The purpose of this paper is to present in the most comprehensive and pedagogical way the Array-OL model of specification. Departing from the original description of Array-OL (only available in French), we present an integrated view of the language including the various extensions that were made over the years and a more "modern" vocabulary. Section 2 will define the core language. Its projection to an execution model will be discussed in section 3 and we will present a number of extensions of Array-OL in section 4.

Core language

As a preliminary remark, Array-OL is only a specification language, no rules are specified for executing an application described with Array-OL, but a scheduling can be easily computed using this description.

INRIA

Principles

The initial goal of Array-OL is to give a mixed graphical-textual language to express multidimensional intensive signal processing applications. As said before, these applications work on multidimensional arrays. The complexity of these applications does not come from the elementary functions they combine, but from their combination by the way they access the intermediate arrays. Indeed, most of the elementary functions are sums, dot products or Fourier transforms, which are well known and often available as library functions. The difficulty and the variety of these intensive signal processing applications come from the way these elementary functions access their input and output data as parts of multidimensional arrays. The complex access patterns lead to difficulties to schedule these applications efficiently on parallel and distributed execution platforms. As these applications handle huge amounts of data under tight real-time constraints, the efficient use of the potential parallelism of the application on parallel hardware is mandatory.

From these requirements, we can state the basic principles that underly the language:

• All the potential parallelism in the application has to be available in the specification, both task parallelism and data parallelism.

• Array-OL is a data dependence expression language. Only the true data dependences are expressed in order to express the full parallelism of the application, defining the minimal order of the tasks. Thus any schedule respecting these dependences will lead to the same result. The language is deterministic.

• It is a single assignment formalism. No data element is ever written twice. It can be read several times, though. Array-OL can be considered as a first order functional language.

• Data accesses are done through sub-arrays, called patterns.

• The language is hierarchical to allow descriptions at different granularity levels and to handle the complexity of the applications. The data dependences expressed at a level (between arrays) are approximations of the precise dependences of the sub-levels (between patterns).

• The spatial and temporal dimensions are treated equally in the arrays. In particular, time is expanded as a dimension (or several) of the arrays. This is a consequence of single assignment.

• The arrays are seen as tori. Indeed, some spatial dimensions may represent some physical tori (think about some hydrophones around a submarine) and some frequency domains obtained by FFTs are toroidal.

The semantics of Array-OL is that of a first order functional language manipulating multidimensional arrays. It is not a data flow language but can be projected on such a language.

As a simplifying hypothesis, the application domain of Array-OL is restricted. No complex control is expressible and the control is independent of the value of the data. This is realistic in the given application domain, which is mainly data flow. Some efforts to couple control flows and data flows expressed in Array-OL have been done in [START_REF] Labbani | Introducing control in the gaspard2 data-parallel metamodel: Synchronous approach[END_REF] but are outside the scope of this paper.

Boulet

The usual model for dependence based algorithm description is the dependence graph where nodes represent tasks and edges dependences. Various flavors of these graphs have been defined. The expanded dependence graphs represent the task parallelism available in the application. In order to represent complex applications, a common extension of these graph is the hierarchy. A node can itself be a graph. Array-OL builds upon such hierarchical dependence graphs and adds repetition nodes to represent the data-parallelism of the application.

Formally, an Array-OL application is a set of tasks connected through ports. The tasks are equivalent to mathematical functions reading data on their input ports and writing data on their output ports. The tasks are of three kinds: elementary, compound and repetition. An elementary task is atomic (a black box), it can come from a library for example. A compound is a dependence graph whose nodes are tasks connected via their ports. A repetition is a task expressing how a single sub-task is repeated.

All the data exchanged between the tasks are arrays. These arrays are multidimensional and are characterized by their shape, the number of elements on each of their dimension1 . A shape will be noted as a column vector or a comma-separated tuple of values indifferently. Each port is thus characterized by the shape and the type of the elements of the array it reads from or writes to. As said above, the Array-OL model is single assignment. One manipulates values and not variables. Time is thus represented as one (or several) dimension of the data arrays. For example, an array representing a video is three-dimensional of shape (width of frame, height of frame, frame number). We will illustrate the rest of the presentation of Array-OL by an application that scales an high definition TV signal down to a standard definition TV signal. Both signals will be represented as a three dimensional array.

Task parallelism

The task parallelism is represented by a compound task. The compound description is a simple directed acyclic graph. Each node represents a task and each edge a dependence connecting two conform ports (same type and shape). There is no relation between the shapes of the inputs and the outputs of a task. So a task can read two two-dimensional arrays and write a three-dimensional one. The creation of dimensions by a task is very useful, a very simple example is the FFT which creates a frequency dimension. We will study as a running example a downscaler from high definition TV to standard definition TV. Here is the top level compound description. The tasks are represented by named rectangles, their ports are squares on the border of the tasks. The shape of the ports is written as a t-uple of positive numbers or ∞. The dependences are represented by arrows between ports.

Horizontal Filter

(1920, 1080, ∞) (720, 1080, ∞) Vertical Filter (720, 1080, ∞) (720, 480, ∞)
There is only one limitation on the dimensions: there must be at most one infinite dimension by array. Most of the time, this infinite dimension is used to represent the time, so having only one is quite sufficient.

Each execution of a task reads one full array on its inputs and writes the full output arrays. It's not possible to read more than one array per port to write one. The graph is a dependence graph, not a data flow graph.

So it is possible to schedule the execution of the tasks just with the compound description. But it's not possible to express the data parallelism of our applications because the details of the computation realized by a task are hidden at this specification level.

Data parallelism

A data-parallel repetition of a task is specified in a repetition task. The basic hypothesis is that all the repetitions of this repeated task are independent. They can be scheduled in any order, even in parallel2 . The second one is that each instance of the repeated task operates with sub-arrays of the inputs and outputs of the repetition. For a given input or output, all the sub-array instances have the same shape, are composed of regularly spaced elements and are regularly placed in the array. This hypothesis allows a compact representation of the repetition and is coherent with the application domain of Array-OL which describes very regular algorithms.

As these sub-arrays are conform, they are called patterns when considered as the input arrays of the repeated task and tiles when considered as a set of elements of the arrays of the repetition task. In order to give all the information needed to create these patterns, a tiler is associated to each array (ie each edge). A tiler is able to build the patterns from an input array, or to store the patterns in an output array. It describes the coordinates of the elements of the tiles from the coordinates of the elements of the patterns. It contains the following information:

• F : a fitting matrix.

• o: the origin of the reference pattern (for the reference repetition).

• P : a paving matrix.

Boulet

Visual representation of a repetition task. The shapes of the arrays and patterns are, as in the compound description, noted on the ports. The repetition space indicating the number of repetitions is defined itself as an multidimensional array with a shape. Each dimension of this repetition space can be seen as a parallel loop and the shape of the repetition space gives the bounds of the loop indices of the nested parallel loops. An example of the visual description of a repetition is given below by the horizontal filter repetition from the downscaler. The tilers are connected to the dependences linking the arrays to the patterns. Their meaning is explained below.

Horizontal filter

(1920, 1080, ∞) (720, 1080, ∞) (240, 1080, ∞) Hfilter (13) (3)
F =   1 0 0   o =   0 0 0   P =   8 0 0 0 1 0 0 0 1   F =   1 0 0   o =   0 0 0   P =   3 0 0 0 1 0 0 0 1  
Building a tile from a pattern. From a reference element (ref) in the array, one can extract a pattern by enumerating its other elements relatively to this reference element. The fitting matrix is used to compute the other elements. The coordinates of the elements of the pattern (e i ) are built as the sum of the coordinates of the reference element and a linear combination of the fitting vectors as follows

∀ i, 0 ≤ i < s pattern , e i = ref + F • i mod s array (1)
where s pattern is the shape of the pattern, s array is the shape of the array and F the fitting matrix.

In the following examples of fitting matrices and tiles, the tiles are drawn from a reference element in a 2D array. The array elements are labeled by their index in the pattern, i, illustrating the formula ∀ i, 0 ≤ i < s pattern , e i = ref + F • i. The fitting vectors constituting the basis of the tile are drawn from the reference point.

INRIA ( 0 ) ( 1 ) ( 2 )
F = 3 0 s pattern = 3
There are here 3 elements in this tile because the shape of the pattern is (3). The indices of these elements are thus (0), ( 1) and (2). Their position in the tile relatively to the reference point are thus

F • (0) = 0 0 , F • (1) = 3 0 , F • (2) = 6 0 . 1 0 0 1 1 1 0 2 1 2 0 0 F = 1 0 0 1 s pattern = 2 3
The pattern is here two-dimensional with 6 elements. The fitting matrix builds a compact rectangular tile in the array.

1 0 0 1 1 1 0 2 1 2 0 0 F = 2 1 0 1 s pattern = 2 3
This last example illustrates how the tile can be sparse, thanks to the 2 0 fitting vector, and non parallel to the axes of the array, thanks to the 1 1 fitting vector.

A key element one has to remember when using Array-OL is that all the dimensions of the arrays are toroidal. That means that all the coordinates of the tile elements are computed modulo the size of the array dimensions. The following more complex examples of tiles are drawn from a fixed reference element (o as origin in the figure) in fixed size arrays, illustrating the formula

∀ i, 0 ≤ i < s pattern , e i = o + F • i mod s array . Boulet 0 5 0 3 F = 2 0 0 1 s pattern = 3 2 o = 0 0 s array = 6 4
A sparse tile aligned on the axes of the array.

0 5 0 3 F = 1 1 s pattern = 6 o = 2 0 s array = 6 4
The pattern is here mono-dimensional, the fitting builds a diagonal tile that wraps around the array because of the modulo.

0 5 0 5 F = 1 0 1 -1 1 0 1 1 1 -1 s pattern =        2 2 3 2 2        o = 1 2 s array = 6 6
This is an extreme case of a five-dimensional pattern fitted as a two-dimensional tile. Most of the elements of the tile are read several times to build the 48 pattern elements.

Paving an array with tiles. For each repetition, one needs to design the reference elements of the input and output patterns. A similar scheme as the one used to enumerate the elements of a pattern is used for that purpose.

The reference elements of the reference repetition are given by the origin vector, o, of each tiler. The reference elements of the other repetitions are built relatively to this one. As above, their coordinates are built as a linear combination of the vectors of the paving matrix as follows

∀ r, 0 ≤ r < s repetition , ref r = o + P • r mod s array (2)
INRIA where s repetition is the shape of the repetition space, P the paving matrix and s array the shape of the array. Here are some examples.

P = 0 3 1 0 s repetition = 3 3
The tiles can overlap and the array is toroidal.

Summary.

We can summarize all these explanations with two formulas:

• ∀ r, 0 ≤ r < s repetition , ref r = o+P •r mod s array gives all the reference elements of the patterns,

• ∀ i, 0 ≤ i < s pattern , e i = ref r + F • i mod s array enumerates all the elements of a pattern for repetition r, where s array is the shape of the array, s pattern is the shape of the pattern, s repetition is the shape of the repetition space, o is the coordinates of the reference element of the reference pattern, also called the origin, P is the paving matrix whose column vectors, called the paving vectors, represent the regular spacing between the patterns, F is the fitting matrix whose column vectors, called the fitting vectors, represent the regular spacing between the elements of a pattern in the array. Some constraints on the number of rows and columns of the matrices can be derived from their use. The origin, the fitting matrix and the paving matrix have a number of rows equal to the dimension of the array; the fitting matrix has a number of columns equal to the dimension of the pattern 3 ; and the paving matrix has a number of columns equal to the dimension of the repetition space.

Linking the inputs to the outputs by the repetition space. The previous formulas explain which element of an input or output array one repetition consumes or produces. The link between the inputs and outputs is made by the repetition index, r. For a given repetition, the output patterns (of index r) are produced by the repeated task from the input patterns (of index r). These pattern elements correspond to array elements through the tiles associated to the patterns. Thus the set of tilers and the shapes of the patterns and repetition space define the dependences between the elements of the output arrays and the elements of the input arrays of a repetition. As stated before, no execution order is implied by these dependences between the repetitions.

To illustrate this link between the inputs and the outputs, we show below several repetitions of the horizontal filter repetition. In order to simplify the figure and as the treatment is made frame by frame, only the first two dimensions are represented 4 . The sizes of the arrays have also been reduced by a factor of 60 in each dimension for readability reasons. 3 Thus if the pattern is a single element viewed as a zero-dimensional array, the fitting matrix is empty and noted as (). The only element of a tile is then its reference element. This can be viewed as a degenerate case of the general fitting equation where there is no index i and so no multiplication F • i. 4 Indeed, the third dimension of the input and output arrays is infinite, the third dimension of the repetition space is also infinite, the tiles do not cross this dimension and the only paving vector having a non null third element is

Enforcing determinism by construction

The basic design decision that enforces determinism is the fact that Array-OL only expresses data dependences. To ease the manipulation of the values, the language is single assignment. Thus each array element has to be written only once. To simplify the verification of this, the constraint that each task produces all the elements of its output arrays is built into the model. An array has to be fully produced even if some elements are not read by any other task. Enforcing this rule for all the tasks at all the levels of the hierarchy also allows to compose tasks easily. A direct consequence of this full production rule is that a repetition has to tile exactly its output arrays. In other words each element of an output array has to belong to exactly one tile. Verifying this can be done by using polyhedra computations using a tool like SPPoC5 [START_REF] Boulet | SPPoC : manipulation automatique de polyèdres pour la compilation[END_REF].

Boulet

To check that all the elements of an output array have been produced, one can check that the union of the tiles spans the array. The union of all the tiles can be built as the set of points e (r,i) verifying the following system of (in)equations

       0 ≤ r < s repetition ref r = o + P • r mod s array 0 ≤ i < s pattern e (r,i) = ref r + F • i mod s array . ( 3
)
Building the difference between the array and this set is done in one operation (polyhedral difference from the Polylib6 that is included in SPPoC) and testing if the resulting set is empty is done by looking for an element in this set using a call to the PIP7 [START_REF] Feautrier | Parametric integer programming[END_REF] solver that is also included in SPPoC. These operations are possible because, as the shapes are known values, the system of inequations is equivalent to a system of affine equations.

To check that no point is computed several times in an output array, one builds the following set of points, e, (intersection of two tiles) verifying the following system of (in)equations

                         0 ≤ r < s repetition ref r = o + P • r mod s array 0 ≤ i < s pattern e = ref r + F • i mod s array 0 ≤ r ′ < s repetition ref r ′ = o + P • r ′ mod s array 0 ≤ i ′ < s pattern e = ref r ′ + F • i ′ mod s array . ( 4
)
If this set is empty, then no two tiles overlap and each computed element is computed once. To check the emptiness of this set, the same technique as above can be used: to call PIP. As above, the above system of inequations is equivalent to a system of affine equations, thus solvable by PIP. With these two checks, one can ensure that all the elements of the output arrays are computed exactly once and so that the single assignment is respected.

We have defined in this section the Array-OL language, its principles and how it allows to express in a deterministic way task and data parallelism. The most original feature of Array-OL is the description of the array accesses in data parallel repetitions by tiling. As this language make no assumption on the execution platform, we will study in the next section how the projection of an Array-OL specification to such an execution platform can be made.

Projection onto an execution model

The Array-OL language expresses the minimal order of execution that leads to the correct computation. This is a design intension and lots of decisions can and have to be taken when mapping an Array-OL specification onto an execution platform: how to map the various repetition dimensions to time and space, how to place the arrays in memory, how to schedule parallel tasks on the same processing element, how to schedule the communications between the processing elements?

Space-time mapping

One of the basic questions one has to answer is: What dimensions of a repetition should be mapped to different processors or to a sequence of steps? To be able to answer this question, one has to look at the environment with which the Array-OL specification interacts. If a dimension of an array is produced sequentially, it has to be projected to time, at least partially. Some of the inputs could be buffered and treated in parallel. On the contrary, if a dimension is produced in parallel (e.g. by different sensors), it is natural to map it to different processors. But one can also group some repetitions on a smaller number of processors and execute these groups sequentially. The decision is thus also influenced by the available hardware platform.

It is a strength of Array-OL that the space-time mapping decision is separated from the functional specification. This allows to build functional component libraries for reuse and to carry out some architecture exploration with the least restrictions possible.

Mapping compounds is not specially difficult. The problem comes when mapping repetitions. This problem is discussed in details in [START_REF] Amar | Projection of the Array-OL specification language onto the Kahn process network computation model[END_REF] where the authors study the projection of Array-OL onto Kahn process networks [START_REF] Kahn | The semantics of a simple language for parallel programming[END_REF][START_REF] Kahn | Coroutines and networks of parallel processes[END_REF]. The key point is that some repetitions can be transformed to flows. In that case, the execution of the repetitions is sequentialized (or pipelined) and the patterns are read and written as a flow of tokens (each token carrying a pattern).

Transformations

A set of Array-OL code transformations has been designed to allow to adapt the application to the execution, allowing to choose the granularity of the flows and a simple expression of the mapping by tagging each repetition by its execution mode: data-parallel or sequential.

These transformations allow to cope with a common difficulty of multidimensional signal processing applications: how to chain two repetitions, one producing an array with some paving and the other reading this same array with another paving? To better understand the problem, let us come back to the downscaler example where the horizontal filter produces a (720, 1080, ∞) array row-wise 3 by 3 elements and the vertical filter reads it column-wise 14 elements by 14 elements with a sliding overlap between the repetitions as shown on the following figure.

Boulet

Horizontal filter In order to be able to project this application onto an execution platform, one possibility is to make a flow of the time dimension and to allow pipelining of the space repetitions. A way to do INRIA that is to transform the application by using the fusion transformation to add a hierarchical level. The top level can then be transformed into a flow and the sub-level can be pipelined. Here is the transformed application.

(1920, 1080, ∞) (720, 1080, ∞) (240, 1080, ∞) Hfilter (13) (3)
F =   1 0 0   o =   0 0 0   P =   8 0 0 0 1 0 0 0 1   F =   1 0 0   o =   0 0 0   P =   3
Hfilter

F = 0 1 o = 0 0 P = 1 0 F = 1 0 o = 0 0 P = 0 1 (13) (3)
Vertical filter

(3, 14) (3, 4) (3)
Vfilter (14) (4)
F = 0 1 o = 0 0 P = 1 0 F = 0 1 o = 0 0 P = 1 0
A hierarchical level has been created that is repeated (240, 120, ∞) times. The intermediate array between the filters has been reduced to the minimal size that respects the dependences.

If the inserted level is executed sequentially and if the two filters are executed on different processors, the execution can be pipelined.

This form of the application takes into account internal constraints: how to chain the computations. Now, the environment tells us that a TV signal is a flow of pixels, row after row. We can now propose a new form of the downscaler application taking that environment constraint into account by extending the top-level patterns to include full rows. Here is what such an application could look like.

Vfilter (14) (4)
F = 0 1 o = 0 0 P = 3 1 0 0 F = 0 1 o = 0 0 P = 3 1 0 0
The top-level repetition now works with tiles containing full rows of the images. Less parallelism is expressed at that level but as the images arrive in the system row by row, the buffering mechanism is simplified and the full parallelism is still available at the lower level.

A full set of transformations (fusion, tiling, change paving, collapse) described in [START_REF] Dumont | Spécification Multidimensionnelle pour le traitement du signal systématique[END_REF] allows to adapt the application to the execution platform in order to build an efficient schedule compatible with the internal computation chaining constraints, those of the environment and the possibilities of the hardware. A great care has been taken in these transformations to ensure that they do not modify the semantics of the specifications. They only change the way the dependences are expressed in different hierarchical levels but not the precise element to element dependences.

Extensions

Around the core Array-OL language, several extensions have been proposed recently. We will give here the basic ideas of these extensions and pointers to references where the reader can go into details.

Inter-Repetition dependences

To be able to represent loops containing inter-repetition dependencies, we have added the possibility to model uniform dependencies between tiles produced by the repeated component and INRIA tiles consumed by this repeated component. The simplest example is the discrete integration shown below.

Integrate (∞) (∞) 0 () (∞) + () () () F = o = 0 P = 1 F = o = 0 P = 1 def d = 1
Here the patterns (and so the tiles) are single points. The uniform dependence vector d = (1) tells that repetition r depends on repetition rd(= r -(1)) by adding the result of the addition of index r-(1) to the input tile r. This is possible because the output pattern and input pattern linked by the inter-repetition dependence connector have the same shape. To start the computation, a default value of 0 is taken for repetition 0.

Formally an inter-repetition dependence connects an output port of a repeated component with one of its input ports. The shape of these connected ports must be identical. The connector is tagged with a dependence vector d that defines the dependence distance between the dependent repetitions. This dependence is uniform, that means identical for all the repetitions. When the source of a dependence is outside the repetition space, a default value is used. This default value is defined by a connector tagged with "def".

Control modeling

In order to model mixed control flow, data flow applications, Labbani et al. [START_REF] Labbani | UML2 profile for modeling controlled data parallel applications[END_REF][START_REF] Labbani | Introducing control in the gaspard2 data-parallel metamodel: Synchronous approach[END_REF]have proposed to use the mode automata concept. An adaptation of this concept to Array-OL is necessary to couple an automaton and modes described as Array-OL components corresponding to the states of that automaton.

A controlled component is a switch allowing to select one component according to a special "mode" input. All the selectable components must have the same interface (same number and types of ports). An automaton component produces a 1D array of values that will be used as mode inputs of a controlled component. A repetition component allows to associate the mode values to a repetition of a controlled component.

Both the inter-repetition and the control modeling extensions can be used at any level of hierarchy, thus allowing to model complex applications. The Array-OL transformations still need to be extended to deal with these extensions.

Tools

Several tools have been developed using the Array-OL language as specification language. Gaspard Classic8 [START_REF] Dekeyser | Video kills the radio stars[END_REF] takes as input an Array-OL specification, allows the user to apply transformations to it, and generates multi-threaded C++ code allowing to execute the specification on a shared memory multi-processor computer.

The Gaspard29 co-modeling environment [START_REF] Boulet | From MDD concepts to experiments and illustrations, chapter Model Driven Engineering for System-on-Chip Design[END_REF] aims at proposing a model-driven environment to co-design intensive computing systems-on-chip. It proposes a UML profile to model the application, the hardware architecture and the allocation of the application onto the architecture. The application metamodel is based on Array-OL with the inter-repetition dependence and control modeling extensions. The hardware metamodel takes advantage of the repetition mechanism proposed by Array-OL to model repetitive hardware components such as SIMD units, multibank memories or networks-on-chip. The allocation mechanism also builds upon the Array-OL constructs to express data-parallel distributions. The Gaspard2 tool is built as an Eclipse10 plugin and mainly generates SystemC code for the co-simulation of the modeled system-on-chip. It also includes an improved transformation engine.

Two smaller tools are also available11 : a simulation [START_REF] Dumont | Another multidimensional synchronous dataflow, simulating Array-OL in PtolemyII[END_REF] of Array-OL in PtolemyII [START_REF] Lee | Overview of the Ptolemy Project[END_REF] and Array-OL example, a pedagogical tool helping to visualize repetitions in 3D. And to be complete, we have to mention that Thales has developed its own internal tools using Array-OL to develop radar and sonar applications on multiprocessor platforms.

Acknowledgment

The author would like to thank all the members of the west team of the laboratoire d'informatique fondamentale de Lille who have worked on the definition and compilation of Array-OL or used it as a tool for their work. They have also made some very useful comments on drafts of this paper.

Conclusion

We have presented in this paper the Array-OL language. This language is dedicated to specify intensive signal processing applications. It allows to model the full parallelism of the application: both task and data parallelisms. Array-OL is a single assignment first order functional language manipulating multidimensional arrays. It focuses on the expression of the main difficulty of the intensive signal processing applications: the multidimensional data accesses. It proposes a mechanism able to express at a high level of abstraction the regular tilings of the arrays by dataparallel repetitions. The original Array-OL language has been extended to support inter-repetition dependences and some control modeling.

As an Array-OL specification describes the minimal order of computing, its space-time mapping has to be done taking into account constraints that are not expressed in Array-OL: architectural and environmental constraints. A toolbox of code transformations allows to adapt the application to its deployment environment. Future works include extending this toolbox to handle the control extensions and automating the allocation process of an application on a distributed heterogeneous platform in the Gaspard2 co-modeling environment.

= 5

 5 This figure represents the tiles for all the repetitions in the repetition space, indexed by r. The paving vectors drawn from the origin o indicate how the coordinates of the reference element ref r of the current tile are computed. Here the array is tiled row by row.



  The interesting array is the intermediate (720, 1080, ∞) array that is produced by tiles of 3 elements aligned along the first dimension and consumed by tiles of 13 elements aligned on the second dimension. of the first two-dimensions and suppression of the infinite dimension of the intermediate (720, 1080, ∞) array.

RR n°6113

A point, seen as a 0-dimensional array is of shape (), seen as a 1-dimensional array is of shape (1), seen as a

2-dimensional array is of shape[START_REF] Amar | Projection of the Array-OL specification language onto the Kahn process network computation model[END_REF] 1 , etc.INRIA

This is why we talk of repetitions and not iterations which convey a sequential semantics.RR n°6113

http://www.lifl.fr/west/sppoc/ RR n°6113

http://icps.u-strasbg.fr/polylib/

http://www.piplib.org/ INRIA

http://www2.lifl.fr/west/gaspard/classic.html

http://www2.lifl.fr/west/gaspard/

http://www.eclipse.org/

http://www2.lifl.fr/west/aoltools/ INRIA