John Gliksberg
email: john.gliksberg@uvsq.fr

Jean-Noël Quintin
email: jean-noel.quintin@atos.net

Pedro Javier García
email: pedrojavier.garcia@uclm.es

Node-type-based load-balancing routing for Parallel Generalized Fat-Trees

Keywords: HPC, routing, fat-tree, PGFT, Dmodk, Smodk, heterogeneity

High-Performance Computing (HPC) clusters are made up of a variety of node types (usually compute, I/O, service, and GPGPU nodes) and applications don't use nodes of a different type the same way. Resulting communication patterns reflect organization of groups of nodes, and current optimal routing algorithms for all-to-all patterns will not always maximize performance for group-specific communications. Since application communication patterns are rarely available beforehand, we choose to rely on node types as a good guess for node usage. We provide a description of node type heterogeneity and analyse performance degradation caused by unlucky repartition of nodes of the same type. We provide an extension to routing algorithms for Parallel Generalized Fat-Tree topologies (PGFTs) which balances load amongst groups of nodes of the same type. We show how it removes these performance issues by comparing results in a variety of situations against corresponding classical algorithms.

INTRODUCTION

Routing algorithms for HPC systems aim, for one thing, to avoid congestion during application execution. No perfect agnostic algorithm exists, and designing a good routing algorithm usually requires paying attention to the topology and communication patterns which will take place. As detailed by Vigneras & Quintin [START_REF] Vignéras | Fault-tolerant routing for exascale supercomputer: The bxi routing architecture[END_REF], we can consider that the topology of an HPC cluster never changes, so algorithms are usually designed for a given topology class (i.e. topology-aware algorithms). On the other hand, communication patterns are hard to observe (it is distributed information and can evolve rapidly), rarely known in advance (sometimes unpredictable, sometimes not predicted, sometimes classified), and in the case of multiple applications running concurrently it is potentially impossible to reroute the cluster on-the-fly for optimal performance of each application without causing deadlocks; indeed, there are few algorithms which rely on real communication patterns. Existing research instead focuses on common worst case scenarios: scatter, gather, n2pairs, all-to-all, hot-spots, etc.

We observe that when nodes are not all of the same type (compute, I/O, service, GPGPU, . . . ) communication patterns for applications will usually be subsets of worst-case scenarios with only one type of source nodes and one type of destination nodes. In the case of parallel generalized fat-trees (PGFTs), it is intuitive to observe how existing load-balancing algorithms (namely Dmodk and Smodk) can result in avoidable congestion during type-specific communication phases. The aim of this article is to propose new routing algorithms which will provide the same performance for type-specific patterns as existing ones do for type-unspecific patterns.

Section I describes the existing context in detail to improve understanding of the performance issues. Characteristics of fat-tree topologies and their routing algorithms are presented to ease analysis of routing algorithms' quality. A case-study to this effect is introduced alongside a description of node type heterogeneity in Section II. A corresponding communication pattern is chosen in Section III, alongside a statically-computed congestion metric; three routing algorithms are then analysed in detail to show how they under-utilize available network resources. Section IV provides a new technique to use these resources more efficiently without losing properties of the existing algorithms.

I. BACKGROUND A. Types of fat-tree topologies

Fat-tree topologies were introduced by Leiserson [START_REF] Charles E Leiserson | Fat-trees: universal networks for hardware-efficient supercomputing[END_REF] for their high capacity to represent any network for a given size. All fat-tree topologies are deadlock-free when routed with shortest paths; this property is one of the main advantages of fat-trees. K-ary n-trees were subsequently formalized by Petrini & Vanneschi [START_REF] Petrini | k-ary n-trees: High performance networks for massively parallel architectures[END_REF] and describe real-life implementations of fat-trees with low-radix switches while being rearrangeablynon-blocking for any n2pair pattern. Extended Generalized Fat-Trees (XGFTs), introduced by Ohring et al. [START_REF] Sabine R Ohring | On generalized fat trees[END_REF], describe a more general class of topologies which keep some properties of k-ary n-trees but allow building much smaller and cheaper networks with only partly reduced overall performance. These topologies are generally not capable of providing full crossbisectional bandwidth (CBB) for a given number of end-nodes and switch radix.

Zahavi introduced Parallel Generalized Fat-Trees which can provide slimmed topologies with full CBB [START_REF] Zahavi | D-mod-k routing providing non-blocking traffic for shift permutations on real life fat trees[END_REF]; they are also useful for their fast tolerance to faults on duplicated links. PGFTs are defined by their number of levels h, the upwards arity w, downwards arity m, and link parallelism p, each parameter for every level in the topology. (The corresponding function is P GF T (h; m 0 , . . . , m n-1 ; w 0 , . . . , w n-1 ; p 0 , . . . , p n-1 ).) They are built recursively with duplicated subgroups composed of smaller PGFTs (containing only interconnected switches of lower levels). Each switch is addressed with a tuple (l, a h , . . . , a l ) where l is its level and a is the vector describing the sub-trees the node is located at.

B. Vocabulary

Fat-trees are composed of levels consisting of switches connected above and below. As a result, elements related to a switch can be classified using an up or down prefix. For example up-switches are switches linked to the switch in question which are in the level above; the same logic applies to its ports and links.

Up and down-routes also relate to the direction levelwise. It is worth pointing out that this differs from existing topology-agnostic Up/Down routing algorithms, where up means "towards the root node" and conversely for down.

Top-switches are those in the highest level; leaf -switches are (as in all indirect topologies) those connected to end-nodes. For fat-trees we call all switches in the lowest level leaves.

Hereafter, L1 switches are those at the first level (leaves), followed by L2s, etc.

C. Side-note on adaptive routing

Adaptive routing can react to congestion by diverting communication towards alternative routes. In the case of network congestion, spreading congested traffic as much as possible is a right approach, because the congestion was caused by unnecessarily colliding traffic flows in the first place.

Congestion can, however, originate from end-nodes themselves (it can then be referred to as end-node congestion), in that case spreading congested traffic will not solve the situation and will instead further increase the problems arising from that traffic to the rest of the topology. In particular, more traffic flows will share paths with congested traffic, hence increasing the probability of the latter causing head-of-line blocking to the former [START_REF] Rocher-Gonzalez | On the impact of routing algorithms in the effectiveness of queuing schemes in high-performance interconnection networks[END_REF]. Furthermore, traffic that was routed adaptively loses the property of being transmitted in-order, potentially causing supplementary cost to the application or communication layer; for that reason the communication layer can mark packets to forbid them from being routed adaptively.

Since adaptive routing cannot differentiate between end-node congestion and network congestion, it does not undermine the need for high-quality deterministic routing. Instead, research focuses on techniques to either reduce the potentially harmful collateral impact of adaptive routing or reduce congestion from happening in the first place with injection-throttling [START_REF] Escudero-Sahuquillo | Combining congested-flow isolation and injection throttling in hpc interconnection networks[END_REF] or better deterministic routing. The latter is the aim of this article.

D. Overview of routing algorithms across fat-tree topologies

Pure fat-trees are never used in supercomputers, because they rely on very high-radix switches when there are many nodes. However if we were to route them, that would simply mean following the single shortest path available between any two nodes. Any pair of nodes is associated with a single switch at an equal and minimal distance from both, it is called the nearest common ancestor (NCA).

When routing k-ary n-trees, every pair of nodes has multiple NCAs. Optimal routing then comes down to distributing NCAs via which to route to avoid network-congestion from happening in the first place. For XGFTs and PGFTs, the problem is extended to take into account per-level arities and parallel links.

1) Random routing: When multiple NCAs are available in fat-tree topologies, one approach to balancing the load of deterministic routes is to randomly choose upwards routes. There is only one downward route from a switch to a node. However in PGFT topologies there is a choice among parallel links. This choice is made randomly too.

On average, the routes are randomly load-balanced: all-to-all traffic will not cause implicit bias towards any part of the topology. Deviations from the average will, however, cause routes to overlap and induce network congestion.

2) Dmodk routing: The regular structure of fat-tree topologies can be used to uniformly distribute routes and achieve load-balancing routing with a deterministic method based on packet destination ID, instead of random routing. Zahavi defines such a routing algorithm for PGFTs in a closed form with upwards routes P U leading to destination d for all switches in level l computed as follows [START_REF] Zahavi | D-mod-k routing providing non-blocking traffic for shift permutations on real life fat trees[END_REF]:

P U l (d) := d l k=1 w k mod (w l+1 p l+1 )
This formula assigns an index among the switch's up-ports, which must be indexed beforehand to match the topological addressing scheme. All switches in a level that are not in the same subgroup as the destination are assigned the same upwards route. (Those that are in the subgroup must be routed downwards.) This formula and its corresponding algorithm are called D-mod-k or Dmodk. This method can be simplified for fat-trees simpler than PGFTs and in all cases balances the load while concentrating routes to the same destination, thus concentrating the undesired effects of same-destination end-node congestion within a single-root subtree.

In the case of PGFTs, parallel links are indexed in a roundrobin manner so that all up-switches are assigned a route before multiple routes are assigned towards a single switch (via those multiple links). This, combined with the above formula, ensures a distribution similar to the one defined sequentially in Zahavi et al.'s previous work concerning fat-trees [START_REF] Zahavi | Optimized InfiniBand fat-tree routing for shift all-to-all communication patterns[END_REF].

Gomez et al. [START_REF] Gomez | Deterministic versus adaptive routing in fat-trees[END_REF] routes k-ary n-trees with a method which applies bitmasks to the destination number. This method is defined in detail for k = 2; a similar approach can be extended for higher values of k. This algorithm can be considered as a specialized version of Dmodk routing.

3) Smodk routing: If switches can determine the sources of messages, routing algorithms can use that information as well. From this an alternative to Dmodk can be defined: Smodk, which propagates messages similarly to Dmodk but based on source node ID rather than destination ID. This algorithm concentrates together routes from the same source, thus concentrating the undesired effects of same-source endnode congestion as much as possible.

In cases where communications are symmetrical between patterns with several destinations per source and those with several sources per destination, there is no reason for Dmodk or Smodk to be better than the other. Otherwise there isn't necessarily one choice which is always better, but choosing Smodk for multiple-destination heavy patterns (and Dmodk for multiple source heavy patterns) is a reasonable heuristic [START_REF] Rodriguez | Oblivious routing schemes in extended generalized fat tree networks[END_REF].

We refer to Dmodk and Smodk together as a class of algorithms as Xmodk for the rest of this article.

II. HETEROGENEOUS CLUSTERS

Supercomputers are often clusters made of several types of nodes, rather than the common description of a single type of computing nodes. Other types of nodes can include IO nodes for short and long-term data storage; service or management nodes for login, node reservation, deployment, monitoring, fault-tolerance; GPGPU and FPGA nodes for optimized computations There are various strategies to place secondary nodes (IO or service) in existing clusters, which are usually not described in research material. In the case of fat-trees, strategies can include:

• Placing a constant number of secondary nodes of each type at every leaf • Adding an irregular subgroup with secondary nodes connected to the top switches like the other regular subgroups (this generally breaks fat-tree properties) • Connecting the cluster to an external topology via routers.

For example if using a Lustre file system, Lustre routers can be nodes of the cluster leading to an array of IO servers of which the fabric management and routing algorithm are not aware. As a concrete example, BXI 1 switches have 48 ports. Some BXI switch have only copper ports, some others have three optical ports. The optical ports are placed identically on all switches and are dedicated to nodes physically far within the topology (i.e. management nodes and IO proxy nodes).

III. ANALYSIS OF A TYPE-BASED COMMUNICATION PATTERN

We will use a simplified case-study to show how nodetype-oblivious load-balancing routing can result in unnecessary network congestion. The topology for this case-study is a pruned 3-level PGFT with low-radix switches and nonfull crossbisectional bandwidth (CBB) (see figure 1). Nodes are indexed by port rank on their leaf and by leaf address comparison between leaves. The last port of every leaf is reserved for IO nodes; they have NIDs whose modulo by 8 is 7. We use a topology with nonfull CBB because otherwise there would be no possible congestion at any top-port. This case-study is based on a communication pattern commonly found in distributed applications: data collection from all compute nodes to IO nodes, each compute node sending to the IO node of its symmetrical leaf (e.g.: (0, 0, 1) is symmetrical to (0, 1, 1), so NIDs 8 to 14 send to NID 47). In this case all routes will have to go through a top-switch. This might be contained in a short time frame, following a barrier, or spread out through the application lifetime, it does not matter. For a given complete set of routes R, we call C2IO(R) the subset of routes affected by this pattern.

A. Static congestion metric

This study relies on a static metric to describe the potential sources of contention. The aim of this metric is to give a formal way to describe contention, which abstracts the fine-grain causes of latency to help build a general understanding of how to avoid contention. This contrasts with common techniques based on simulation or experimentation which do not link observations of contention with a corresponding explanation. This simple technique of estimation of contention is new; it is also used in concert with the architecture described by Vigneras & Quintin [START_REF] Vignéras | Fault-tolerant routing for exascale supercomputer: The bxi routing architecture[END_REF] with the goal of automating computation of that metric for potential integration into the fabric management's decision making. Analysis in terms of this metric is sufficient to prove and explain drawbacks and benefits of algorithms, but a simulation-based analysis would complement this work to give tangible results for real-life applications.

Worst-case scenario contention can be measured by the number of possible flows going through a port at the same time. Once the topology is routed, if a given port p is used as output for routes, we can count the number of distinct sources (src(R, p)) and destinations (dst(R, p)) for these routes:

• Both values are non-nil, since there are routes going through the port.

• If one of these values is equal to 1, this port will never be used for unrelated communications; the port is subjected to only one flow of communication. Any potential packet concurrency at the port means that there is a corresponding concurrency at the sending end-node or receiving endnode. That end-node will be the cause of unavoidable congestion of an order of magnitude more important, and no packet from another flow could be affected. For a given set of routes R, we call this metric C port :

C p (R) := min(src(R, p), dst(R, p))
This metric does not imply there will always be network congestion at ports with C port > 1, but it shows the worst case. Assuming all flows are similar, collisions will happen more frequently when more flows are involved. As a result we claim that in general port a will tend to be more congested than port b if C a > C b , even if it depends on the exact timing of communications. From this we can deduce a reasonable metric for the whole topology:

C topo (R) := max p∈topo (C p (R))
Routing in a balanced manner means minimizing that metric. Studying a communication pattern means applying this metric only to the routes affected by the pattern rather than all the routes computed.

For this metric we consider ports as output for the routes, but the same analysis can be made with ports as input. This does not cause C topo (R) to vary when the pattern has symmetrical communications between sources and destinations.

B. Dmodk performance

With Dmodk routing, destinations will be assigned one switch through which to route in every subgroup. More specifically, we will describe which up-port is routed as output for switches not directly above the destination, and which downport is routed as output for switches directly above, when there are several parallel ports available.

w 1 = 2, p 1 = 1: every destination is assigned the L2 switches corresponding to its index modulo two. (E.g.: 47 mod 2 = 1, thus destination 47 is assigned the second L2 switch of each subgroup.) The eight IO destinations are all assigned the same two L2 switches ((1, 0, 1) and (1, 1, 1)), and more specifically the last up-port of the L2 switch not in their subgroup.

w 2 = 1: there is only one L3 switch each L2 switch leads to. It still corresponds to the destination's index modulo 2. IO destinations are assigned the second L3 switch.

p 2 = 4: they are more specifically assigned the last port of the four leading to their subgroup. This leaves four destinations per top-port. Figure 4 shows this for (2, 0, 1).

(2,0,0)

(2,0,1) Furthermore, each destination has exactly one corresponding source: (2, 0, 1) : 7 is the last of (2, 0, 1)'s four ports leading to the left subgroup, and (2, 0, 1) : 8 is the last leading to the right subgroup.

(1,0,0) (1,0,1) (0,0,0) [0 -7] (0,0,1) [8-15] (0,0,2) [16-23] (0,0,3) [24-31] (1,1,0) (1,1,1) (0,1,0) [32-39] (0,
C (2,
There are 8 (leaves) times 7 (compute nodes per leaf) = 56 compute destinations, to which are assigned all top-ports except for the two ports of (2, 0, 1) assigned to IO nodes = 14 top-ports, in a balanced manner; this leaves four compute destinations per port. None of these routes are affected by C2IO, therefore,

∀p / ∈ (2, 0, 1), C p (C2IO(Dmodk)) = 0 C topo (C2IO(Dmodk)) = 4
To reformulate this result: for the given communication pattern most of the top-ports are unused while two top-ports have a strong risk of congestion. This can be seen for one of these ports on Figure 4: the routes shown by the red arrows concentrate around the top-port like those shown in Figure 3. This is sub-optimal, while spreading both subgroups of four IO destinations any disjoint way among the 8 ports leading to each in the top-switches would have lead to C topo (C2IO(R dst )) = 1. The object of Section IV will be to define such a set of routes R dst .

C. Smodk performance

With Smodk, routes from compute to IO nodes are spread per source. With the same process as Dmodk for compute nodes as destinations, we determine which ports are used with Smodk for computed nodes as sources. More specifically, we will describe which down-port is used as output for switches not directly above the source, and which up-port is used as output for switches directly above, when there are several parallel ports available.

There are 8 top-ports that lead to each subgroup, and 28 compute sources per subgroup; after every group of 7 sources, one NID is skipped, which corresponds to skipping the last considered port of (2, 0, 1). We conclude that two ports of (2, 0, 1) have no compute source, and every other top-port has four compute sources which are all connected to different leaves and as a result send to different IO destinations. This results in C p (C2IO(Smodk)) = 4 for each affected top-port p. This is shown in Figure 5.

This means that in this case there are fourteen top-ports with a high risk of congestion; The sets of routes depicted by red and light-blue arrows in Figure 5 also correspond to the situation shown in Figure 3 to show how high congestion risk for two of the fourteen concerned top-ports. For this communication pattern Smodk is less suited than Dmodk.

(2,0,0) ( Optimizing a source-based routing for this pattern and metric means coalescing routes to the same destination. This would be possible for a given pattern; however this article aims to route based on node-type only, therefore we cannot use specific distribution information. If we always have colliding routes lead to distinct destinations, the best we can reach in this situation is still

C topo (C2IO(R src )) = 4.
Since the pattern considered has few destinations and many sources, it is reasonable that a routing algorithm which concentrates routes from the same sources will be difficult to improve. The opposite will happen for the opposite pattern. Section IV will also define the set of routes R src .

D. Random routing performance

Dmodk was unable to reach C topo (Dmodk) = 1 because the modulo operation depends on NIDs and has no information about the communication pattern. Random routing does not depend on NID; it spreads every route uniformly over the available ports, and as a result every subset of routes is also spread uniformly. Therefore C2IO(Random) does not have particularly coalesced routes.

In practice, distributing each group of 28 routes into its corresponding 8 top-ports always causes collisions between routes that have different destinations. The probability of collision is very close to 1.2 Therefore, we can safely state that C topo (C2IO(Random)) is always greater than 1. Repeated computation of Random routing for the given topology and communication pattern resulted in C topo (C2IO(Random)) values of either 3 or 4: i.e. rarely better than Dmodk.

Random routing will usually give slightly better results than Dmodk or Smodk as soon as the communication patterns have a given bias, but they will always leave some ports with avoidable congestion. Just as Xmodk algorithms aim to compute perfect routes for the general worst-case scenario, we want to compute perfect routes for the type-specific worst-case scenario.

IV. GROUPED XMODK

In the previous section we show that the existing routing algorithms do not balance the load correctly when the topology has mixed node types.

To improve routing for type-specific communication patterns, we can use knowledge of node types and modify Xmodk algorithms. The aim is to optimize resource usage depending on node type. For example the optimization should achieve the best throughput for communications towards IO proxies or compute nodes.

We suggest balancing each group of nodes separately to improve load-balancing under worst-case type-specific patterns. This corresponds to the previously mentioned R dst and R src .

A. Description of indexing

Grouped Xmodk algorithms, or Gxmodk, consist of preprocessing NIDs. Knowing each node's type, the algorithms begin by updating the NIDs accordingly, as shown in algorithm 1. Xmodk is then applied as usual but with the updated NIDs.

B. Analysis for previous topology and communication pattern

We choose to call gNID a reindexed NID. Let's suppose that compute nodes are reindexed first: there are 56 so they are assigned gNIDs 0 to 55. IO nodes are assigned gNIDs 56 to 63. Now routing depends on whether Gdmodk or Gsmodk is used.

1) Gdmodk results: For Gdmodk, each IO destination is assigned a unique L2 switch in each subgroup (e.g.: gNID 61 is assigned (1, 0, 1) and (1, 1, 1)). Each L2 switch is assigned two IO destinations of the opposite subgroup, therefore the uproutes from L2 switches use only half of the available parallel ports in a balanced manner.

C p∈(1, * , * ) (C2IO(Gdmodk)) ≤ 1
Each L3 switch is shared by two IO destinations for each subgroup (e.g.: (2, 0, 1) is shared by NIDs 15, 31, 47 and 63; or gNIDs 57, 59, 61 and 63), which are assigned distinct output ports. Figure 6 shows how Gdmok distributes routes efficiently when considering type-based communication patterns. It can be interpreted by pointing out that each set of routes specified by a given color has only one destination (and matches the situation described in Figure 2), with no overlap on output ports in the two upper levels between two sets of routes.

(2,0,0) ( C p∈({1,2}, * , * ) (C2IO(Gdmodk)) = 1 leaves' up-ports have seven sources and two destinations. C p∈U p-ports((0, * , * )) (C2IO(Gdmodk)) = 2 as is shown with the overlapping dashed red and double-dotted green arrows in Figure 6. It is unavoidable for some of them to have more than one for the given pattern, so Gdmodk gives the best possible quality of routing tables.

C topo (C2IO(Gdmodk)) = 2
2) Gsmodk results: For Gsmodk, the 28 compute sources of each group are assigned all 8 up-ports of the two L2 switches of their subgroup in a balanced manner: there are 7 compute sources per up-port which are used to lead to 4 distinct IO destinations. The 7 top-ports leading to the other subgroup are used the same way. Gsmodk improves route distribution for this pattern compared with Smodk: Since an eighth up-port is now used in both L2 switches (1, * , 1), (and two down-ports of (2, 0, 1)), each port now has 7 sources. All of these ports that were used by Smodk had 8 sources. This improvement is comparatively minor, because few resources had been spared by Smodk on this pattern. This shows that type-awareness doesn't solve the existing asymmetry issue between optimizing routing to coalesce sources or destinations, but it does improve routing with regards to type-specific patterns any time Xmodk missed out on available resources.

On the symmetrical communication pattern we would see the same improvement as we do between Dmodk and Gdmodk for the considered communication pattern. In general, if pattern P is symmetrical to Q, we should always find:

CONCLUSIONS AND FUTURE WORKS

In this paper we have defined realistic communication patterns depending on node type which are present on our production cluster. From this real-life scenario we analyzed how existing solutions fare against these patterns. We have specified how type-based communications can result in unnecessary congestion. To counter this we have provided new algorithms to improve existing solutions. We have shown a realistic example with, in one case, a sevenfold decrease in congestion risk.

The congestion issue of Xmodk stems from nodes of a same type having the same NID, modulo arities. This also affects communications unrelated to node-type, but optimizing for these means knowing about application usage. Gxmodk aims only to improve the situation when node-type is known; having early knowledge of applications' communication matrices would warrant writing specific deterministic algorithms.

This article relies on a static flow metric from which we deduce probable congestion. A more thorough analysis of the relationship between this metric and actual congestion depending on fine-grain communication interaction would also be warranted. A corresponding study of the new algorithms based on simulation rather than only a static congestion metric would also provide results in terms of performance.

This work focuses on fat-trees, for which node indexing allows intuitive understanding of NCA distribution; from this we derive type-based pattern analysis and devise a new node indexing to solve corresponding issues. For other topologies (e.g. DragonFly, Generalized HyperCubes) a similar work could also be attempted. Furthermore, a procedural routing algorithm for fat-trees (which can be useful for routing degraded fat-trees or similar topologies) was omitted; a similar technique could be used to improve it.

Fig. 1 .

 1 Fig. 1. Case-study topology P GF T (3; 8, 4, 2; 1, 2, 1; 1, 1, 4) -IO nodes (in black) have the largest NID of every leaf (7, 15, 23, • • • ≡ 7 mod 8)

Fig. 2 .Fig. 3 .

 23 Fig. 2. Example sets of routes for which p is subjected only to one flow • If both values are greater than one, there are unrelated communications that might interact at this port. This can lead to potentially avoidable network congestion.

  0,1):7 (C2IO(Dmodk)) = C (2,0,1):8 (C2IO(Dmodk)) = min(56, 4) = 4

Fig. 5 .

 5 Fig. 5. Two subsets of C2IO(Smodk): red routes have source NID 0 mod 8, light blue routes have source NID 1 mod 8.

Algorithm 1

 1 Reindex NIDs by type n o d e t y p e s = s e t ( ( node . t y p e f o r node i n t o p o . n o d e s ) ) newnodes = l i s t ( ) f o r n o d e t y p e i n n o d e t y p e s : f o r n i d , node i n enumerate ( t o p o . n o d e s ) : i f node . t y p e == n o d e t y p e : newnodes . a p p e n d ( node ) t o p o . n o d e s = newnodes Re-indexing in the order of the original NIDs ensures that consecutive reindexed NIDs are topologically close.

Fig. 6 .

 6 Fig.6. Simplified representation of all routes going to IO nodes in the right subgroup, under Gdmodk routing. Arrows not displayed can be deduced by shortest paths to displayed ones.

C 4 Figure 7

 47 Figure7shows all routes of C2IO(Gsmodk) that use one example top-port as output.

Fig. 7 .

 7 Fig. 7. Subset of C2IO(Gsmodk) with source gNID 0 mod 8

C

  topo (P (Dmodk)) = C topo (Q(Smodk)) C topo (Q(Dmodk)) = C topo (P (Smodk)) C topo (P (Gdmodk)) = C topo (Q(Gsmodk)) C topo (Q(Gdmodk)) = C topo (P (Gsmodk))

BXI is the interconnect technology developed by Bull/Atos. It comprises hardware (switches, links) and software (firmware, low-level and high-level development environment on which are built the fabric management and routing algorithms).

Determining with what probability there will be a conflict between two of the 28 routes (leading to different destinations) spread through the 8 top-ports is an example of collision probability between sets of random variables[START_REF] Michael | Collision probability between sets of random variables[END_REF] (a generalization of the girl/boy birthday problem). However in this case the total number of variables is greater than the number of choices. In that situation, the article's formula for generalized number of sets has a term which always cancels out for part of the computation; it seemed possibly ill-adapted and was therefore discarded.

ACKNOWLEDGEMENTS

This BXI development has been undertaken under a cooperation between CEA and Atos. The goal of this cooperation is to co-design extreme computing solutions. Atos thanks CEA for all their inputs that were very valuable for this research.

This research was partly funded by a grant of Programme des Investissments d'Avenir. This work has been jointly supported by the Spanish MINECO and European Commission (FEDER funds) under the project TIN2015-66972-C5-2-R (MINECO/FEDER).

BXI development was also part of ELCI, the French FSN (Fond pour la Société Numérique) cooperative project that associates academic and industrial partners to design and provide software components for new generations of HPC datacenters.


John Gliksberg
email: john.gliksberg@uvsq.fr

Antoine Capra
email: antoine.capra@atos.net

Alexandre Louvet
email: alexandre.louvet@atos.net

Pedro Javier García
email: pedrojavier.garcia@uclm.es

Devan Sohier
email: devan.sohier@uvsq.fr

High-Quality Fault-Resiliency in Fat-Tree Networks (extended abstract)

Coupling regular topologies with optimized routing algorithms is key in pushing the performance of interconnection networks of HPC systems. In this paper we present Dmodc, a fast deterministic routing algorithm for Parallel Generalized Fat-Trees (PGFTs) which minimizes congestion risk even under massive topology degradation caused by equipment failure. It applies a modulo-based computation of forwarding tables among switches closer to the destination, using only knowledge of subtrees for pre-modulo division. Dmodc allows complete rerouting of topologies with tens of thousands of nodes in less than a second, which greatly helps centralized fabric management react to faults with high-quality routing tables and no impact to running applications in current and future very large-scale HPC clusters. We compare Dmodc against routing algorithms available in the InfiniBand control software (OpenSM) first for routing execution time to show feasibility at scale, and then for congestion risk under degradation to demonstrate robustness. The latter comparison is done using static analysis of routing tables under random permutation (RP), shift permutation (SP) and all-to-all (A2A) traffic patterns. Results for Dmodc show A2A and RP congestion risks similar under heavy degradation as the most stable algorithms compared, and near-optimal SP congestion risk up to 1% of random degradation.

Introduction

A majority of current leading network topologies for High Performance Computing (HPC) clusters are fat-tree variants. (The five most powerful clusters of the November 2018 Top500 list [START_REF] Strohmaier | Top500 list[END_REF] boasted fat-tree topologies.) It is sufficient for fat-tree-specific routing algorithms to be minimal to guarantee deadlock-free routing, and the regular nature of their target topology class should simplify load-balancing strategies. In general, oblivious routing (without knowledge of communication patterns) in fat-trees is deterministic and optimized for shift patterns [START_REF] Gómez | Deterministic versus adaptive routing in fat-trees[END_REF] [3] [START_REF] Zahavi | Quasi fat trees for hpc clouds and their fault-resilient closed-form routing[END_REF]. In particular, PGFTs [START_REF] Zahavi | D-mod-k routing providing non-blocking traffic for shift permutations on real life fat trees[END_REF] describe all regular fat-trees for which there is at most one downward switch-path from any switch to any node (as shown in Figure 1). The oblivious algorithm for non-degraded PGFTs (Dmodk) uses this property and their connection logic to provide load balance through an arithmetic rule.

Section 2 goes into detail about existing works for faultresilient fat-tree routing and their shortcomings. The proposed fault-resilient routing algorithm is presented in Section 3. Section 4 then presents results by comparing our implementation against routing engines of OpenSM [START_REF] Opensm | Opensm -infiniband subnet manager[END_REF] (those deemed appropriate for routing of degraded fat-trees), first for routing runtime and then for congestion risk under degradation. Section 5 summarizes pros and cons of the proposed technique.

Background

Some of the research regarding oblivious fault-resilient routing focuses on techniques that apply to any connected network [START_REF] Flich | A survey and evaluation of topology-agnostic deterministic routing algorithms[END_REF] [START_REF] Domke | Fail-in-place network design: interaction between topology, routing algorithm and failures[END_REF]; these topology-agnostic techniques require full re-routing on topology change. Some other research explicitly targets degradations to regular fat-trees [START_REF] Zahavi | Quasi fat trees for hpc clouds and their fault-resilient closed-form routing[END_REF] [START_REF] Quintin | Transitively deadlock-free routing algorithms[END_REF]; there are several re-routing strategies for these techniques. OpenSM's UPDN [START_REF] Opensm | Current OpenSM Routing § UPDN Routing Algorithm[END_REF] and Ftree [START_REF] Zahavi | Optimized InfiniBand™ fat-tree routing for shift all-to-all communication patterns[END_REF] routing engines can also be applied from scratch to a degraded fat-tree. PQFT [START_REF] Zahavi | Quasi fat trees for hpc clouds and their fault-resilient closed-form routing[END_REF] is similar, though it requires a complete list of faults. The combination of Dmodk + Ftrnd diff [START_REF] Vignéras | Fault-tolerant routing for exascale supercomputer: The bxi routing architecture[END_REF] available in BXI FM [START_REF]Bull exascale interconnect[END_REF] is applied in an offline/online manner (with an iterative list of topology changes and an up-to-date view of the topology), the goal being fast reaction to faults with minimal routing changes. Fabriscale [START_REF] Villanueva | Routing and faulttolerance capabilities of the fabriscale fm compared to opensm[END_REF] also provides fast centralized re-routing of fat-trees, by precomputing alternative routes.

The random operation chosen in Ftrnd diff results in progressive degradation of load balance and incapacity to return to the original routing in case of fault recovery. Ftrnd diff does manage to recover rapidly from minor failures; however large numbers of simultaneous changes (which happen for example when entire islets are rebooted) cause computation times to skyrocket in current implementations. The strategies of PQFT and Fabriscale which consist in moving only invalidated routes let one expect somewhat similar load-balancing issues as with Ftrnd diff. Studies show topology-agnostic routing outperforms fat-tree-specific routing under sufficient topology degradations [START_REF] Bogdanski | Discovery and routing of degraded fat-trees[END_REF] [START_REF] Domke | Fail-in-place network design: interaction between topology, routing algorithm and failures[END_REF].

Dmodc Description

The idea behind the fault-resilient algorithm that we propose in this paper is to rely on local information like Ftree (and no topological address), while using the same closed-form arithmetic operation as Dmodk. The aim is fast centralized computation of routing tables for degraded PGFTs, providing optimal or well-balanced deterministic routes even under heavy fabric degradation. The algorithm begins with a partly sequential preprocessing phase followed by a parallel computation phase. Links are bi-directional; notations used in the expressions below are defined in Table 1.

Preprocessing

Rank. Levels and link directions are determined based on leaf switches being equivalent to the lowest level.

Port Groups. Groups of ports linked to the same switch are prepared and sorted by universally unique identifier (UUID, defined at hardware fabrication) to help with same-destination route coalescing.

Cost. We define the cost c s,l of a switch s to a leaf switch l to be the minimum number of hops between one another under up-down restrictions according to rank, as defined in Algorithm 1.

Divider. Dmodc is based on the same arithmetic operation as Dmodk: it begins with an integer division by the product of upward arities (= #{s s}) of lower levels. To reflect the actual state of the topology, only local information must be considered; in turn this operation is based on the products of up-to-date counts of upswitches, as defined in Algorithm 1.

Algorithm 1: Compute costs and dividers.

foreach s ∈ S do foreach l ∈ L do c s,l ← ∞ Π s ← 1 foreach l ∈ L do c l,l ← 0 foreach s ∈ S going upwards do π ← Π s × #{s s} foreach s s do foreach l ∈ L | c s,l + 1 < c s ,l do c s ,l ← c s,l + 1 if π > Π s then Π s ← π (max reduction) foreach s ∈ S \ L going downwards do foreach s s do foreach l ∈ L | c s,l + 1 < c s ,l do c s ,l ← c s,l + 1
In a full PGFT, #{s s} values are constant throughout each level, and individual values are decreased following faults; the max reduction accordingly helps keep load repartition stable under few faults. This choice of reduction was only compared with one using the first downward path and showed little to no change in route quality under random degradation. S is the set of switches, L is the set of leaf switches (L ⊂ S), U (s) is the UUID of switch s, N is the set of nodes, λn is the (only) leaf switch connected to node n (λn ∈ L) , respectively denote downlinks and uplinks (according to rank), Gs is the ordered list of port groups of switch s, Ωg is the switch connected to port group g, # denotes cardinality, in number of port groups or of ports. c s,l is the cost of switch s to leaf switch l, Πs is the divider of switch s, tn is the topological node identifier (NID) of node n, Topological NID. The arithmetic nature of Dmodc guarantees load-balancing only if NIDs (on which the modulo operation is applied) are topologically contiguous. We explicitly determine each node's topological NID using previously computed costs in Algorithm 2.

Algorithm 2: Compute topological NIDs. t ← 0 X ← L sorted by UUIDs while X = Ø do l ← X 0 µ ← min l ∈X\{l} (c l,l ) foreach l ∈ X | c l,l ≤ µ do foreach n l in port rank order do t n ← t t ← t + 1 X ← X \ {l }
Dmodc can provide optimal results for shift permutation communication patterns which respect such an ordering, otherwise one could expect results similar to those of random permutation communication patterns.

Routes Computation

The deterministic output port p s,d and alternative output ports P s,d of every switch s for every destination d ∈ N (not directly linked to s) are selected with a closed-form operation based on the results previously determined. First, port groups leading closer to λ d are selected in (1), setting corresponding alternative output ports in (2):

C s,λ d ← g ∈ G s | c Ωg,λ d < c s,λ d (1) P s,d ← {p ∈ g | g ∈ C s,λ d } (2)
Selected port groups C s,λ d [i] ∀ i ∈ #C s,λ d are ordered by UUID of their remote switch. From this, the output port group is chosen in (3) and the port within that group in (4):

g s,d ← C s,λ d [ t d Π s mod #C s,λ d ] (3)
p s,d ← g s,d [ t d Π s × #C s,λ d mod #g s,d ] (4

Results

Validity

Routing is valid for degraded PGFTs if and only if the cost of every leaf switch to every other leaf switch is finite: this reflects every node pair having an up-down path. Our implementation includes a pass through all leaf switch pairs to verify this condition. The up-down path restriction is sufficient to guarantee deadlock-freedom within degraded PGFTs [START_REF] Quintin | Transitively deadlock-free routing algorithms[END_REF].

Congestion Risk

Random degradation is simulated using hundreds of throws for each considered routing algorithm and type of equipment to degrade (switches or links). The integer amount of equipment a ∈ [0, 2 m [ to remove at each throw is chosen using a shifted log-uniform distribution. This distribution is chosen to test degradation uniformly across multiple scales and include non-degraded tests; it is defined in the following formula using uniform number generator u() ∈ [0, 1]:

a ← 2 m×u() -1
The chosen amount of equipment is then randomly removed from the complete topology. The resulting degraded (or complete) topology is routed at this point, and linear forwarding tables are dumped for analysis.

Evaluation of these tables is performed using static analysis of metrics representing maximum congestion risk for three communication patterns: all-to-all (A2A), random permutation (RP), shift permutation (SP). The congestion risk metric consists of counting min(#srcs, #dsts) for all routes of the corresponding pattern; this approximates network-caused congestion risk [START_REF] Rodriguez | Exploring pattern-aware routing in generalized fat tree networks[END_REF]. For A2A, the maximum congestion risk (throughout all ports) is the only value kept. RP consists of computing the maximum congestion risk for 1000 random permutations and keeping the median value. (σ = 0,96 for 100 RP samples in the case of Figure 2 with 256 randomly removed switches routed with Ftree.) SP consists of computing the maximum congestion risk for all (#N -1) shift permutations and keeping the maximum value. (Shifts are based on the same node ordering which OpenSM's Ftree follows internally in order for quality comparison to be fair.) Such simplified performance models faithfully reflect comparative behaviour [START_REF] Faizian | Throughput models of interconnection networks: the good, the bad, and the ugly[END_REF], though the absolute values measured are not good estimators of real throughput. Note that virtual channels potentially required by other algorithms are not taken into account in this analysis.

Congestion risk results are shown in Figure 2. When considering existing routing algorithms, Ftree provides the best performance for complete PGFTs (especially regarding SP for which the maximum congestion risk approaches theoretical optimal), but SSSP provides better stability under massive degradation, confirming results of the studies mentioned in Section 2. UPDN and MinHop provide visually identical results in this analysis: in fact in a full PGFT they are equivalent and vary only slightly under degradation. They both provide comparatively poor results for SP and A2A throughout the observed scale, however for RP they surprisingly improve significantly under massive degradation.

Dmodc provides minimal congestion risk throughout the considered range of degradations when compared with existing oblivious algorithms. In particular, it is even more stable than Ftree for SP under minimal degradation and nearly as stable as SSSP for A2A and RP under massive degradation.

Runtime

On our production implementation coded in C99, computation of cost, divider, topological NIDs, and routes are spread over POSIX threads fetching work with a switch-level granularity. Figure 3 reports complete algorithm execution time alongside OpenSM (version 3.3.21) routing times (measured by adding timers in the source code) running on the same machine. Note that local erraticness is partly due to our RLFT construction process for which the number of resulting switches is not monotonic with the number of requested nodes.

For clusters ranging up to many tens of thousands of nodes, Dmodc provides fast enough re-routing for a centralized fabric manager to react to faults before applications are interrupted.

Conclusion

The simulation results in Section 4 show that Dmodc provides high-quality centralized fault-resilient routing for PGFTs at a fraction of the runtime of existing algorithms, without relying on partial re-routing. Dmodc is also applicable to non-PGFT fat-tree-like topologies but with lower quality load balancing. As defined here, no effort has been made to minimize size of updates to be uploaded to switches throughout the fabric.

This algorithm is implemented inside BXI FM and has been succesfully deployed to an 8490 node PGFT production topology in which it helps provide fault-resiliency even when faced with thousands of simultaneous changes.

Figure 1 .

 1 Figure 1. P GF T (3; 2,2,3; 1,2,2; 1,2,1) with leaf switches shown in grey.

TABLE 1 .

 1 NOTATIONS USED IN EXPRESSIONS.

  )

						UPDN						MinHop					Ftree					SSSP			Dmodc
	Maximum congestion risk (min(#src,#dst)) under pattern Maximum congestion risk (min(#src,#dst)) under pattern Maximum congestion risk (min(#src,#dst)) under pattern Maximum congestion risk (min(#src,#dst)) under pattern Maximum congestion risk (min(#src,#dst)) under pattern Maximum congestion risk (min(#src,#dst)) under pattern Maximum congestion risk (min(#src,#dst)) under pattern Maximum congestion risk (min(#src,#dst)) under pattern Maximum congestion risk (min(#src,#dst)) under pattern Maximum congestion risk (min(#src,#dst)) under pattern	4 8 16 32 64 128 256 4 8 16 32 64 128 256	0		2 random 8 all2all shift UPDN	32	128	0	2		8 MinHop 32	Number of removed switches 128 Number of removed switches 0 2 8 32 128 Number of removed switches Number of removed switches Number of removed switches Number of removed switches Number of removed switches Ftree Number of removed switches Number of removed switches Number of removed switches	0	2		8 SSSP	32	128	0	2	8 Dmodc	32	128
			0	2	8	32	128 512	0	2	8	32	128 512	0	2	8	32	128 512	0	2	8	32	128 512	0	2	8	32	128 512
														Number of removed links Number of removed links Number of removed links Number of removed links Number of removed links

Figure 2. Maximum congestion risk in a 8640 node PGFT (with blocking factor of 4) under random topology degradation (in log-log scale; lower is better).

Acknowledgements

This research has been undertaken under a cooperation between CEA and Atos. with the goal of co-designing extreme computing solutions. Atos thanks CEA for all their inputs that were very valuable for this research. This research was partly funded by a grant of Programme des Investissements d'Avenir. This work has been jointly supported by the Spanish Ministry of Science, Innovation and Universities under the project RTI2018-098156-B-C52 and by JCCM under project SBPLY/17/180501/000498. BXI development was also part of ELCI, the French FSN (Fond pour la Société Numérique) cooperative project that associates academic and industrial partners to design and provide software components for new generations of HPC datacenters.


Sarah Aboubakr
email: aboubakr.sarah@gmail.com

Mohamed Rguiti

Madiha Yessari

Abdessamad Elballouti

Christian Courtois

Abdelowahed Hajjaji
email: hajjaji.a@ucd.ac.ma

Dielectric characterization of lead zirconate-titane/polyurethane thin film composite: Volume fraction, frequency and temperature dependence

The Lead Zirconate-titane(PZT) ceramic is known by its piezoelectric characteristic, but also by its stiffness. The use of a composite based on a polyurethane (PU) matrix charged by a piezoelectric material, enable to generate a large deformation of the material, therefore harvesting more energy. This new material will provide a competitive alternative and low cost manufacturing technology of autonomous systems (smart clothes, car seat, boat sail, flag …). A thin film of the PZT/PU composite was prepared using up to 80 vol. % of ceramic. Due to the dielectric nature of the PZT,inclusions of this one in a PU matrix raise the permittivity of the composite. For the most of industrial applications, the composite will not be used at room temperature, and as the energy harvested from this new materials have a direct relation with their permittivity we have made a study about the variation of the permittivity at different temperature and frequencies.

Introduction

Nowadays there has been an increasing number of research about new materials used for multifunctional device, sensor and actuator applications [1], especially, piezoelectric ceramics procuring high mechanical coupling coefficients [2], high piezoelectric coefficients and low dielectric losses [START_REF] Jaffe | Piezoelectric Ceramics[END_REF], although, the polymers have an attractive properties too, with their flexibility, ease to fabricate and high breakdown strength [START_REF] Liu | [END_REF].

For those reasons, the researchers thought of the use of a new material, a composite ceramic/polymer. This type of composite has high capability of energy storage and can be used in capacitors and energy storage devices [5].

The connection between the composite phases controls the properties of the composite and also the process employed in the manufacture [6,7]. In other words the distribution and the grain size of the fillers should be controlled.

The piezoelectric ceramic particles most used in ceramic/polymer composites is lead zirconate-titanate, Pb(ZrxTi1 -x)O 3 or PZT [8].T h eu s eo fa ne l e c t r o s t r i c t i v ep o l y m e r had successfully demonstrated to be useful in piezoelectric, and during the last years many researchers have been interested into this material especially the Polyurethane (PU), which have very important properties such as: excellent mechanical properties, good biocompatibility, design flexibility, light weight and low cost, the variation of the hard and soft segment of this elastomer endows the mechanical and dielectric properties and due to which t h ed i e l e c t r i cc o n s t a n tc o u l dr e a c hh i g hv a l u e sa saf u n c t i o no ft h ee l e c t r i cfi e l da n dt e mperature, furthermore the PU have many application especially medical devices and automotive sensors and this makes the material very attractive for a lot of electromechanical applications.Many researcher works are interested on the enhancement of the energy harvested from this electrostrictive polymer [9,10] the combination of the PolyurethanePU and the Lead Zirconate-titane PZT appears as a good compromise between the two material's properties. This composites exhibit a high flexibility, a low density but also a high piezoelectric coefficient.

The need of using sensors and actuators in conditions with high temperature requires a large study of the temperature dependence of the composite characterization. In this work, composites with different percentage volume fraction of PZT were prepared. Indeed dielectric behavior was investigated at different temperature in order to build a mathematical model which can predict the dielectric constant at any temperature.

Experimental procedure

Fabrication of the PZT/PU composite films

Composites with different percentage volume fraction of PZT were prepared asthefollowing: Initially the PU pellets were dissolved in 15 mL of THF (tetrahydrofuran) under magnetic stirring at the room temperature. After the complete dissolution of the PU, the powder of PZT was added to the mixed under magnetic then ultrasound stirring. Finally the mixture was tape casted by Ductor Bade process and dried at room temperature. Samples were then metalized by gold evaporation. The electrode thickness is about 100nm.

Polarization process

Thesampleisheatedinsiliconeoiluntil60°C,inthesametimeabiasvoltageappliedincreases up to saturation. At this stage the external field is fixed at about 2000V/cm during the heatingandthenwemaintainthesamefieldduringthecoolingtoountilroomtemperature.In one hand high temperature helps to easily orient diploes and by the other hand, the cooling allows them to maintain their position fixed into the matrix. More the matrix contains dipoles oriented in the same direction the more we harvest energy from it.

The polarization is a dipole moment which is created when a dielectric material is placed in an electric field, there are many types of polarization that could be occur during the application of the field, this latest change with frequency and temperature [11].

Scanning electron microscopy (SEM)

InordertobeholdthePZTdispersionintothepolymermatrixwhichwaspreparedatfirstsection, we used the SEM technique (scanning electron microscopy); this one produces images of sample's sectional and surface views with very high resolution. The sample they should be conductiveandmustalsobeofanappropriatesizetofitinthespecimenchamber

The dielectric constant measurement

A perfect dielectric material is a non-conductive which can bepolarizedunder a biasing effect of an external electric field. These phenomena result macroscopically by the occurrence of charges at the surface of the material. It results from the movement of the different entities in the sample considered (electrons, ions, dipole …). However, it is not easy to predict the response of certain materials to an external applied field.The permittivity is the parameter that relates polarization to the applied field and it has a direct relationship with the recovered energy of the piezoelectric material as shown by the following equation:

W = 1/2ε 0 ε r E 2 (1)
Where E is the voltage between electrodes, the effective dielectric constant is obtained out eventually [12], εr is the relative permittivity and ε0i st h ep e r m i t t i v i t yo ff r e es p a c e .T h e magnitude of ε ′ (or the dielectric constant εr) indicates the ability of thematerial to store energy from the applied electric field. A parallel plate capacitor with area S andthickness e has acapacitancegivenby

ε r = C p * e/(S * ε 0 ) (2)
The capacity is measured rresponds to the measuring tape to the meter. The sample is a rectangular active areaof 400 mm.

Results and discussion

Scanning electron microscopy (SEM)

Figure 2 (a to d) illustrate the scanning electron microscopy (SEM) images of sectional view of ceramic/polymer composite with 50, 60, 70 and 80% respectively of PZT fillers bended in PU. The microstructure of PZT/PU composite illustrated by SEM images indicates clearly the presences of PZT grains in light region which are more dense and compacted while the dark regions are related to PU polymer with a smooth surface. Therefore more the PZT fraction increases the light region becomes more present. Besides the PZT/PU composite structure indicatesan uniformity of the white dots for which are homogenously dispersed within the PU matrix into the four compositions.

Mathematical models of dielectric constants

There are many theoretical studies on dielectric constant of composites which describe the dependence on the volume fraction of the filler particles, the dielectric constant of polymer andfillerandthepossibleinteractionbetweenbothconstituents.Inthepresentwork,thetheoretical dielectric constant was calculated according to various models and compared to the experimental resultswhich were made by an HP Agilent 4194A Impedance/Gain-Phase Analyzer and the basic measurement accuracy is about 0.17% (all the dielectric measurements in this work were made as the same way); Fig. 6 depicts the variation of experimental and theoretical dielectric constant for different volume fractions of PZT at room temperature and at 1KH. In this study the following equations were used to calculate the effective relative permittivity of the PZT/PU composites. In1892, Rayleigh developed an equation which describes the dispersion of homogeneous spheres in a continuum medium [13], This model consider the composite systems as polymer matrix where spherical conclusions are embedded, but it doesn't take into account the interactions between particles neither the size of the inclusions. Furukawa et al. [14] have concluded another model when the dielectric constant of the matrix is much low compared to that of the fillers, but not the morphology, the effective medium theory (EMT), include a ceramic morphology fitting factor"n. " The small value of n indicates the filler particles to be in near-spherically shape, while a high value of indicates largely non-spherically shaped particles. In our case we have taken n = 0.45. Yamada et al. [15] have described the theoretical effective dielectric constant also, by a model that contains a morphology form factor and the volume fraction of the PZT.

Based on Fig. 3 we can conclude that the model which describes the best the behavior of the composite's constant dielectric is the EMT model, in other hand there are many other parameters that influence the behavior of the composite dielectric constant, one of this parameters is temperature. We have made the same measurements as the last one for the composite which contain 80%Vol. of PZT the dielectric constant for different frequency but at different temperature, we have observed that this last parameter influence the dielectric constant behavior.

As seen before dielectric parameters were measured for each composition and it was fined that the high ones correspond to the composite which contain 80% of PZT fillers (Fig. 3). Therefore this study will be focused on the composition with 80 vol. % of PZT. Dielectric spectroscopy measurements were carried in 1 KHz at room temperature.The poling process was conducted at a field between 100 and 500 KV/cm, in 20Hz and at a room temperature.

The composite is a heterogeneous material, the determination of the apparent dielectric constant of this type of material is a little bit complicated, and so to simplify it, the system can be described by an apparent dielectric constant, which is based on the composite components, the volume fraction of the added particles and their spatial distribution on the matrix. According to Hashin and Shtrikman [16], the apparent permittivity is an essential property which characterizes the physical situation of the dielectric composite, generally we don't have any information about the material expect that itishomogenousandisotropic,sotherandomness and the connectedness properties of the structure inside the material should be extremely studied. In our case the material is made of monodisperse inhomogeneities of a permittivity ϵ1 which are randomly dispersed on a matrix of a permittivity ε2withavolumeV .

The dielectric constant increases by increasing the added PZTvolume fraction but according to Figure 4, the disadvantage of adding PZT grains is that the composite becomes more and morestiff,theY oungmodulusincreases,andtheelasticdomainofthecompositeisreduced, measurements were made by a Lhomargy DY 30 machine having an uncertainty about 0.5. Figure 6 describes the behavior of the two phases of the composite according to the frequency; the relative permittivity of the two components decreases with the increase frequency, thus we can explain the dependence of the composite with frequency (Figure 6).

Figure 6 shows the variation of the apparent dielectric constant of the composite according to frequency for compositions for different volume fraction of PZT particles from 50% up to 80%,basedonthisfigure,wecannotethatthedispersionincreasewiththeincreasingvolume fraction of the fillers, this could be caused by the space charge effects, indeed we remark that thedielectricconstantincreasewiththeincreaseoftheparticlespercentage,butitdecrease withtheincreasingfrequency.Obviouslyinthiseffectivemediumthecorrelationbetweenthe particlesincreaseswiththeincreaseoftheirpercentage,alsowecannotethatthepermittivity and the losses dependence with frequency is more important when their volume fraction increases, this is because of the increase of the two types of polarization, the interfacial charges polarization and the intrinsic dipoles polarization on the composite. This phenomenon generally happens on the heterogeneous systems like PZT/PU composite, this is because of the accumulation of the electric charges on the interface boundaries and the formation of large dipoles or cluster of ceramics, in this case the polarization degree increase with the increasing percentage of PZT into the composite, and by the way the dielectric constant increases as well.

Based on the same figure wecan note thatthe dielectric constant decreases with the increasing frequency and it is the same for the tow components also (Figure 5),this phenomenon could be originate from the dielectric relaxation of ceramic (PZT), and the interfaces in the composite. Concerningthe polymer matrix, the alternation of the elastic andthe movement of the domains walls [17,18,19], at high frequency region could be a reasonof the decrease of its dielectric constant with frequency, another reason is the relaxation process in the PU networks, its sensitivity is given by the chemical structure of the polyurethane chains and bythechemicalcross-linkingstructureoftheharddomain,thedependenceofthedielectric constant on frequency can be obtained from the Maxwell-Wagner model:

ε ′ = ε ∞ + (ε s -ε ∞ )/ 1 + ω 2 τ 2 (3)
where ε ′ is the dielectric constant, ε ∞ is the dielectric constant at infinitely high ε s frequency,is the dielectric constant at low frequency, ω is the frequency. τ is the relaxation time, it describes the time needed for dipoles to have the same orientation as the applied field, Or the time required for dipoles to be disoriented after removing the electric field.Studies showed that the relaxation time is temperature dependent because the movements become faster as the temperature increase.

As mentioned above, the relaxation time is temperature dependent, thus the permittivity is too; therefore it is more appropriate to writeequation (4)asDebye' smodeldoes:

ε r (ω, θ ) = ε ∞ (θ ) + (ε s (θ ) -ε ∞ (θ ))/(1 + jωτ (θ )) (4)
Figures 6 and7 depict the variation of the real and imaginarily (loss) permittivity, according to the temperature, from the ambient temperature up to 250°Catafrequencyof10KHz,itis clearly remarkable that the losses increase gradually with the increasing temperature, that can be explained by the increase of the interfacial polarization, because of the accumulation of the charges in the interfacial electrodes of the composite and/or amorphous crystalline interfaces of the polymer [20]. On other hand the mobility of molecules increases with temperature, so athighfrequencythemaximumlossisathightemperaturebecausethetimerequiredforthe molecules align in the direction of the electric field is not sufficient.

I ti sc l e a rt h a tt h et e m p e r a t u r ea ff e c tt h ed i e l e c t r i cp r o p e r t i e s ,c o n c e r n i n gt h ep o l y m e r matrix, at high temperature where the thermal agitation is enhanced, the intermolecular forces between the polymer chains is broken thus the polar groups (PZT particles and clusters) are more free to move and change their orientation, so they lose their polarization, on the other hand at low temperature, the polar groups are fixed inside the polymer matrix. During the permittivity measurements, the electronic and atomic polarizations are spontaneous, whereas the dipole polarization is directly affected by temperature; in fact the relaxation time (τ ) decreases with the increasing temperature, this is because the polymer segment couldfollow the oscillating electric field [START_REF] Tareev | Physics of dielectric materials[END_REF][START_REF] Young | Introduction to Polymers[END_REF].

Asaresultofwhatwehaveexplainedbefore,figure 6 depicts the variation of the dielectric constantofthewholecompositeaccordingtotemperature,wenotethattherelativepermittivity decreases with the increasing temperature; this could be explained by the fact that the molecules have more thermal energy and then the thermal motion is greater. This cause a deviation of the dipoles from the perfect alignment with the field to a random direction otherwise the molecules are less closely aligned with each other. Furthermore, at high temperature, the PZT grains could be changed, this fact can also be the origin of the modification ofthedielectricresponseofthecomposite.However,thisdoesnotmeanthat,atlowtemperature, the permittivity will necessarily increases, because the permittivity change especially with structure changes, that why it depends on the phase boundaries which change with temperature also [START_REF] Blythe | Electrical Proeprties of Polymers[END_REF].The relative permittivity of the composite has the same behavior as the host material (polyurethane) (Figure 8), but it is enhanced by the added ceramic particles. In other words, the behavior of the relative permittivity of the composite depends on the behavior of the two phases; the matrix and the fillers

Conclusions

A composite based on a polymer (PU) matrix charged by 50, 60, 70 and 80 vol. % of ceramic fillers (PZT) was prepared. The dielectric properties were examined, experimental results were compared to several theoretical predictions among various models, and they were comparable with the EMT model. It was demonstrated that the permittivity depends on many factors especially the volume fraction of the fillers, the frequency which have a direct effect on the polarization of the dipoles and the temperature which could change the macroscopic structureofthecompositeandthustheresultingpermittivity .W ehavefoundthattheeffective dielectric constant of the composite decreases with frequency, because the degree of polarization decreases at high frequencies. The effective permittivity decreases also with the increasing temperature because the structure of the composite changes especially the polymer matrix.

Figure  .

  Figure . Procedure of preparation of the composite.

Figure  .

  Figure . Scanning electron microscopy images of samples with different volume fraction of PZT (a): Dispersion of % ofP PZT into the matrix (b): Dispersion of % of PZT into the matrix (c): Dispersion of % of PZT into the matrix (d): Dispersion of % of PZT into the matrix.

Figure  .

  Figure . Concentration dependent dielectric constant of PZT/PU

Figure  .

  Figure . Young modulus for different compositions.

Figure  .

  Figure . The variation of the dielectric constant of the PZT (a) and PU (b) according to the frequency.

Figure  .

  Figure . The variation of the dielectric constant of the PZT/PU composite according to frequency.

Figure  .

  Figure . The variation of the dielectric constant of the PZT/PU composite according to temperature.

Figure  .

  Figure . The variation of the dielectric loss of the PZT/PU composite according to temperature.

Figure  .

  Figure . The variation of the dielectric constant of the PZT (a) and PU (b) according to temperature