Amaury Graillat
email: amaury.graillat@univ-grenoble-alpes.fr

Claire Maiza
email: claire.maiza@univ-grenoble-alpes.fr

Matthieu Moy
email: matthieu.moy@univ-lyon1.fr

Pascal Raymond
email: pascal.raymond@univ-grenoble-alpes.fr

Benoît

Response Time Analysis of Dataflow Applications on a Many-Core Processor with Shared-Memory and Network-on-Chip

Keywords: Computer systems organization → Embedded systems, Redundancy, Robotics, • Networks → Network reliability

We consider hard real-time applications running on many-core processor containing several clusters of cores linked by a Network-on-Chip (NoC). Communications are done via shared memory within a cluster and through the NoC for inter-cluster communication. We adopt the time-triggered paradigm, which is well-suited for hard real-time applications, and we consider data-flow applications, where communications are explicit.

We extend the AER (Acquisition/Execution/Restitution) execution model to account for all delays and interferences linked to communications, including the interference between the NoC interface and the memory. Indeed, for NoC communications, data is first read from the initiator's local memory, then sent over the NoC, and finally written to the local memory of the target cluster. Read and write accesses to transfer data between local memories may interfere with shared-memory communication inside a cluster, and, as far as we know, previous work did not take these interferences into account.

Building on previous work on deterministic network calculus and shared memory interference analysis, our method computes a static, time-triggered schedule for an application mapped on several clusters. This schedule guarantees that deadlines are met, and therefore provides a safe upper bound to the global worst-case response time.

INTRODUCTION

Time-critical systems are systems whose response time is part of the specification and for which a too long response time could have dramatic consequences.

Many-core platforms are based on a set of multi-core clusters connected through a Network-on-Chip (NoC). They offer more computational performances than single-core platforms, and offer interesting properties for real-time: partitioning cores into clusters allows spatial isolation, and individual cores can be simple enough to allow a precise worst-case execution time (WCET) analysis. In this paper, we consider Kalray's MPPA2 many-core processor, which is well-suited to hard real-time applications [START_REF] Saidi | The shift to multicores in real-time and safety-critical systems[END_REF]. Its architecture and implementation allow minimizing and bounding interferences, but not fully eliminating them. Hence, a global analysis of applications must be performed in order to ensure that their timing constraints are satisfied.

This paper deals with hard real-time applications, for which deadlines are strict, and provides safe upper bounds on the worstcase response time. We consider precisely a non-preemptive execution model where software is divided into a set of periodic tasks communicating through channels. Each task follows a variant of the Acquisition/Execution/Restitution (AER) execution model [START_REF] Durrieu | Predictable Flight Management System Implementation on a Multicore Processor[END_REF]: tasks start when their input data is ready in the local memory. The first phase is the execution itself. Then, data is transmitted directly to the target tasks. In other words, we follow a remote-write policy, and do not need the "Acquisition" phase of the AER model. When the target task is located in the same cluster, data is written directly to its input buffer in the local memory; when the target task is located on a different cluster, data is remotely written over the NoC. Such a set of tasks can be extracted automatically from a program written in a synchronous language such as Lustre [START_REF] Halbwachs | The synchronous dataflow programming language Lustre[END_REF] or its industrial variant Scade [START_REF] Berry | SCADE: Synchronous design and validation of embedded control software[END_REF], or other high-level languages such as Simulink [START_REF]Simulink: User's Guide[END_REF]. Note that this AER execution model is a phased execution model that is also referred to as read/execute/write in the literature [START_REF] Becker | Contention-Free Execution of Automotive Applications on a Clustered Many-Core Platform[END_REF].

Since we consider hard real-time applications, we optimize the application and analysis for the worst-case. Non-preemptive, static, time-triggered scheduling is therefore a well-suited execution model. Since we consider periodic applications, we need to check the schedulability of one period (or hyper-period in case we use hyperperiod expansion), and the rest of the execution will repeat the schedule of this period. For each task, a release date (arrival time) is computed, defined as the offset within a period where the task is allowed to start. Each release date is computed in such a way that the input data for the task are guaranteed to be available at this time. If the data is available earlier, the task still waits for the release date to start. This is not a limitation in a hard real-time context, since starting earlier would not improve the Worst-Case Response Time (WCRT) of the application. On the other hand, a static time-triggered schedule allows a finer analysis of the interference than a more dynamic schedule: the time interval when a task can execute is known statically. Tasks start at their release date, and execute without preemption no longer than their WCRT. This knowledge is exploited in the interference analysis: tasks whose execution intervals do not overlap cannot interfere. In other words, time-triggered schedules allow timing isolation of tasks within a period.

Prior work has been carried out to compute response-time analysis within a cluster [START_REF] Altmeyer | A generic and compositional framework for multicore response time analysis[END_REF][START_REF] Rihani | Response Time Analysis of Synchronous Data Flow Programs on a Many-Core Processor[END_REF] or a worst-case traversal time for the NoC [START_REF] Dupont De Dinechin | Network-on-chip service guarantees on the kalray mppa-256 bostan processor[END_REF]. However, there is little research on computing a worstcase response time that considers application mapped to more than one cluster with a complete model of the NoC interference on local memories (see Section5). Considering the interference on memory accesses and the latency due to NoC communications separately is not sufficient: we need to take into account the interference between NoC communications and memory accesses, since a NoC communication implies memory read accesses on the sending side and write accesses on the receiving side.

We model NoC transmissions by inserting additional endpoint tasks such that a global response-time analysis may be applied. This response-time analysis takes the interference on shared resources (shared bus and memory) into account, including both interference between software tasks and interference between software tasks and the NoC transmission (TX) and reception (RX) engines.

Contribution. The contribution of this paper is a global model to compute the task release date for applications with both sharedmemory and NoC transfers. We propose a new execution model where NoC communications are implemented with multiple tasks, each one having its own release date. We exploit hard-real time software properties and hardware mechanisms to guarantee the absence of interference on some tasks, and to avoid circular dependencies in the timing analysis. We consider a Remote Direct Memory Access (RDMA) NoC where a core can write to a remote memory address through the NoC. Furthermore, we integrate the worst-case NoC transmission delay in this model to satisfy data dependencies and tighten bounds on the memory interferences from the NoC. Section 2 presents the context of this work: the hard-real time software properties, the Kalray MPPA2 processor, a method to compute the task release dates and a method to compute the WCTT on the NoC. Section 3 explains the sources of interferences we focus on, and presents our new WCRT analysis for handling the NoC interferences. Section 4 gives the results of the experiments on the Kalray MPPA2 processor. Related work is discussed in Section 5.

CONTEXT 2.1 Hard Real-Time Application Model

We consider reactive systems, operating in interaction with their environment, which generally involves the physical world. They are used in domains of application like control engineering in industry (power plants) or transportation (avionics, train, automotive). These systems are hard-real time, meaning that each reaction must occur before a strict, fixed deadline.

Such applications may be developed directly in low-level languages (e.g. C), but more often, they are developed using modelbased design tools, like Scade Suite (avionics) or Simulink (automotive, industrial). In this case the task's code is generated automatically and the compilation process may give useful guarantees on the application execution. Code generation tools targeting sequential execution is available and deployed industrially, see KCG [START_REF] Berry | SCADE: Synchronous design and validation of embedded control software[END_REF]. The area of code generators targeting multi-core is more recent: an extension of KCG, the Multicore Code Generator (MCG) to generate parallel programs was proposed in [START_REF] Colaço | Scade 6: from a Kahn Semantics to a Kahn Implementation for Multicore[END_REF][START_REF] Pagano | A model based safety critical flow for the AURIX multi-core platform[END_REF]. MCG deals with the target-independent code generation, and requires a complementary integration tool to deal with the specificities of the target architecture like memory access interference and NoC communications. A research prototype of code generator from Lustre programs targeting Kalray's MPPA2 processor is proposed in [START_REF] Graillat | Parallel code generation of synchronous programs for a many-core architecture[END_REF]. We base the present work on this code generator; the same principles could apply to an integration tool for MCG.

We consider applications as sets of tasks generated from highlevel languages and implement them on many-core platforms; their characteristics influence our solution:

• They are hard real-time, thus only the worst-case execution/reaction time matters: enhancing the average or best case is irrelevant. • The communications between the tasks are statically known: each communication is oriented and described by a "channel" information that includes the type of the data, the producing and the consuming task. When the application comes from a high level data-flow design (Scade, Simulink), channel information is readily available. • Each functional task is a purely computational piece of code, that generally follows the AER (Acquisition/Execution/Restitution) policy. This is the case when the code is automatically generated from Scade or Simulink. This property is interesting since it is a starting point for implementing a synchronization mechanism: a task requires all its inputs before producing any output. At this point in the code generation flow, the application is therefore a tasks graph, with dependencies between tasks. Tasks follow a variant of the AER model where the Acquisition phase is not needed: tasks write directly to the input buffer of the receiving task. Data dependencies are annotated in the task graph with the amount of data transmitted. Classical WCET analysis techniques (e.g. OTAWA [START_REF] Ballabriga | OTAWA: an open toolbox for adaptive WCET analysis[END_REF]) are used to compute each task's WCET (not accounting for inter-tasks interferences).

W 3 W 2 W 1 W 0 E 3 E 2 E 1 E 0 N 0 N 1 N 2 N 3 S 0 S 1 S 2 S 3

The Kalray MPPA2 Processor

The MPPA2 is a many-core processor composed of 16 compute clusters and 4 I/O clusters, pictured in Figure 1. Each compute cluster is made of 16 cores and a shared memory. The shared memory is composed of 16 banks with independent arbiters. For a more comprehensive description, see [START_REF] Dupont De Dinechin | Time-critical Computing on a Single-chip Massively Parallel Processor[END_REF]. Clocks of the clusters are mesochronous, i.e. they have the same frequency but may have different phase. Each cluster contains a Debug Support Unit (DSU), containing a cycle counter register. This counter is initialized synchronously on the whole processor and can be used to synchronize all compute cores [START_REF] Graillat | Parallel Code Generation of Synchronous Programs for a Many-core Architecture[END_REF], making the MPPA a suitable platform for time-triggered processor-wide scheduling.

Fig. 2 shows a closer view of the path taken by a communication between two clusters. Data is transmitted from the memory of a source cluster to the memory of another cluster. This is the communication we focus on in this paper.

(1) Core 1 reads the data in the memory and copies this data to the buffer of a TX (transmission) engine. We call copy_noc(tx_engine, buffer, size) the piece of code executing on the core that takes care of this copy. In a cluster, accesses to TX engine buffers from the different cores are arbitrated on a single bus. Consequently, concurrent requests can be delayed due to interferences. Data is retained in the buffer.

(2) After the data is fully copied to the buffer of the TX engine, the communication is initiated and the packet is sent to the NoC. This is triggered by a core, that emits the end of transmission (EOT). The code executing on the core is a nonblocking procedure that ends the transmission on the sender side and initiates the transmission from the TX buffer to the NoC. We call it EOT_noc(tx_engine).

(3) Then, the packet traverses the NoC. The worst-case latency from the initiation to the destination cluster is called WCTT. Packets enter the destination cluster through the NoC local link. (4) The RX engine is responsible for copying the received data to the shared memory [START_REF] Berry | SCADE: Synchronous design and validation of embedded control software[END_REF]. Concurrent writes to the same memory bank from the NoC RX and from the cores are arbitrated with a fixed-priority policy. Writes from the NoC have the highest priority. Cores have lower priority and are arbitrated with each other in round robin. There is one arbiter per memory bank: this allows spatial isolation since an access to one bank does not interfere with accesses to other banks. A typical scenario is that writes from the NoC RX can interfere with accesses done during the Execute phase of a task running before the receiving task, on the same core hence accessing the same memory bank.

We analyze in details the possible interferences at each stage later in Section 3.1.

Multi-Core Interference Analysis (MIA)

We distinguish the WCET of a task in isolation, i.e. when there are no memory interferences, and the Worst Case Response Time (WCRT) of the task which accounts for interferences (there are no task preemptions to consider).

Memory interferences have an effect on the execution time of the tasks. Conversely, the execution time of each task may impact the execution time of the others, since it changes the set of tasks concurrently accessing the memory. Consequently, the whole application has to be analyzed globally and information about the release date and response time of each task is required to analyze the interferences. A time-triggered execution ensures that tasks execute between the statically known release date and deadline.

Rihani et al. [START_REF] Rihani | Response Time Analysis of Synchronous Data Flow Programs on a Many-Core Processor[END_REF] introduce an algorithm computing the release dates and WCRT of the tasks. The algorithm takes as input a task graph (tasks, dependencies between tasks, and optionally minimal release dates for some tasks). For each task, it needs the WCET in isolation and the worst-case memory demand (number of accesses to each memory bank). The mapping and execution order of tasks on each core is known. Mapping and scheduling are out of the scope of our work; an external tool is used as a black-box. Based upon this information, MIA computes a static time-triggered schedule, i.e. a release date and a WCRT, accounting for interference for each task.

The algorithm starts from the WCET in isolation of the tasks and iteratively adds the delays due to the interferences reconsidering each time the set of interfering tasks. It relies on the memory demand of each task and a model of the memory arbiter. This algorithm has been implemented in the MIA tool 1 . Our contribution is to integrate a NoC model in release dates and WCRT analysis performed by MIA. This allows analyzing applications mapped to multiple clusters, which rely on both shared-memory and NoC transmission.

NoC Worst-Case Traversal Time Bounds

When the traffic at the NoC input is known, the estimation of a WCTT bound can be simplified and the absence of buffer overflow can be checked. Several methods exist to bound latency of packets through the NoC. Deterministic Network Calculus (DNC) is a theory dedicated to the performance analysis of computer networks such as ATM and Internet. More recently, it has been used for Avionics Full Duplex Switched Ethernet (AFDX) networks certification [START_REF] Geyer | Network engineering for real-time networks: comparison of automotive and aeronautic industries approaches[END_REF][START_REF] Grieu | Analyse et évaluation de techniques de commutation Ethernet pour l'interconnexion des systèmes avioniques[END_REF]. DNC relies on an upper-bound on the input traffic called arrival curve. This arrival curve can be ensured by bandwidth limiter. Then, the methods gives service curve of the network's elements. Operation on these curves allows computing an upper-bound on the latency for each flow and an upper-bound of the buffer level.

Recursive Calculus [START_REF] Ferrandiz | A sensitivity analysis of two worst-case delay computation methods for spacewire networks[END_REF] (RC) is a method to bound the WCTT of best effort traffic. Ayed et al. [START_REF] Ayed | Towards a unified approach for worst-case analysis of Tilera-like and Kalray-like NoC architectures[END_REF] applied the RC theory to handle both the MPPA2 and the Tilera TILE64 many-core processor.

In this work, we use the method from [START_REF] Boyer | Computing Routes and Delay Bounds for the Network-on-Chip of the Kalray MPPA2 Processor[END_REF] which is based on the DNC framework, applied to the MPPA's NoC. It provides latency bounds from source to destination memory.

HANDLING NOC INTERFERENCES IN WCRT ANALYSIS 3.1 Possible Sources of Interference

In this section, we enumerate and focus on the sources of interferences along the transmission path detailed in Figure 2. For each source of interference, we explain how it will be handled in our analysis.

The first source of interference is encountered already at point (1) that is the transmission from a core to the NoC. In the MPPA2 architecture, the cluster's TX engines are accessed by the cores through a single bus. As a consequence, it may introduce interferences and delays between tasks of the cluster accessing the TX engines if accesses are done concurrently. Instead of analyzing these interferences, our solution is to avoid them: in our execution model we forbid copy_noc and EOT_noc from being executed at the same time in a cluster by adding artificial edges in the task graph. This way, we can guarantee that there is no concurrent access to the NoC TX, hence no interference between these accesses. This method to avoid interference is similar to the work of Melani et al. [START_REF] Melani | Memory-Processor Co-Scheduling in Fixed Priority Systems[END_REF], where tasks are scheduled in a way that forbids concurrent accesses of write tasks to avoid contention. We add artificial edges to the dependency graph to enforce a total order and no concurrence between tasks accessing the NoC TX, i.e. steps (1)+(2), before running the scheduling algorithm.

Interference between flows transmitted on the NoC (3) are dealt with by the DNC analysis. DNC is a very general approach, and can deal with interference with other task models including nonperiodic traffic. It does not need to make assumption about the execution model of other sources of traffic on the same chip. It only relies on configuration of hardware traffic limiters in the TX engines of each cluster. Since data being sent come from the TX's input buffer, the TX engine only interferes with other flows in the NoC during this stage, but no interference happen with other elements in the sending cluster.

The next source of interference is at point (4): the bus arbiter to reach a memory bank is shared by the cluster and the receiving task. At this point we partially avoid interferences by limiting the cores that are impacted by the reception of a NoC communication. The architecture allows attributing one memory bank per core. The data and code corresponding to a task are attributed to the bank of the core executing this task. NoC reception buffers are located in the memory bank of the destination task. Packet receptions trigger write access to the memory bank of the buffer. This write access may only interfere with the memory accesses of the destination task and other write phases of tasks on the same core. This limited interference scope avoids interfering with all tasks executed on all cores.

Furthermore, as in [START_REF] Graillat | Parallel Code Generation of Synchronous Programs for a Many-core Architecture[END_REF], the task execution is time-triggered and the implementation relies on a global clock synchronization protocol.

In summary, the only interference related to NoC communications happen when the receiving task is writing, to the memory bank of the destination task.

Motivational Example and Naive Approach

To illustrate our approach, consider the data-flow application depicted in Fig. 3. It is mapped on several clusters. Core 1 of Cluster 3 executes tasks C, D and E. Task E depends on outputs of task A. Task A runs on Core 1 of Cluster 1 and sends its output through the NoC as soon as possible. The transmission is represented with the hatched rectangles. The WCET and the memory demand are known for each task. The WCTT and the size of the transmission are known.

Our aim is to compute the WCRT and release date r for each task taking into account both memory interferences between the cores and from the NoC. In other words, we compute the first date when the inputs of the tasks are guaranteed to be available and the task can start. For instance, in Fig. 3, τ E starts after τ D has finished and the data from τ A has been received. Data transmitted through the NoC are written to the memory bank of τ E , hence possibly interfering the other tasks of the core. Our purpose is to compute the first and the last date when the transmission may write to the destination bank. The first and the last date are respectively the beginning and the end of the hatched rectangle of Fig. 3.

τ A executes three procedures in sequence: the computation, copy_noc and EOT_noc. The best-case execution time of the tasks and the best-case traversal time of the NoC transmission are not known. As a consequence, the first date when the NoC transmission may write to the memory is 0.

The last date when the NoC transmission writes to the remote memory is the last date when the sending task has finished, plus the WCTT. Consequently, the NoC transmission is represented with a task RX A starting at the same time as τ A of duration W CRT (τ A ) + W CTT .

The RX task appears in the model used for the analysis but does not correspond to any physical task in the implementation. It is an over approximation of the interval where the NoC reception may occur.

This method is quite simple but leads to a pessimistic computation since the duration of RX A is longer than required. In fact, RX A starts after the call to the EOT_noc procedure, hence at a date strictly greater than 0. Since the RX accesses have the highest priority in the shared-memory arbiter, an overapproximation of the execution interval of RX has important consequences: all memory accesses by concurrent tasks could be delayed by the number of accesses done by the RX task. It is therefore important to minimize the duration of RX A to limit the number of tasks that may interfere with RX and therefore minimize its impact on the analysis. This "naive" approach does not guarantee the mutual exclusion of accesses to the TX engine. However, in our experiments the computed schedules are such that no concurrent access occur, hence the comparison with our proposed solution (which does ensure mutual exclusion) is fair.

Proposed Solution

As stated previously, a NoC transmission is composed of a copy of the data to the TX engine's buffer (copy_noc) and the EOT_noc procedure to initiate the transfer. The packet is guaranteed to stay in the buffer until the communication is initiated with EOT_noc.

Our proposed method, illustrated in Fig. 4, improves the naive solution by splitting τ A into a computation task, and two extra tasks to implement the communication: the copy task and the EOT task, each one having its own release date. Compared to the AER phased model, we split the Restitution (R) phase into a phase to copy data (copy_noc) and one to initiate the NoC (EOT_noc). The release dates of these tasks are computed the same way as for other tasks by MIA. Note that in this model, EOT_noc has its own release date, which does not depend on the best case execution time of precedent tasks. The NoC transmission cannot start before this date. Without knowledge about the NoC's best case transmission time, the first date when the transmission can write to the remote memory can be set to the start of EOT_noc (i.e. the end date of copy_noc). Then, the duration of RX A is W CTT + W CRT (EOT_noc). This improvement makes the analysis less pessimistic than the naive approach since the duration of the RX task no longer includes the task computation.

To split the Restitution phase, we modified the code generator so that communication between nodes implying the NoC generate two tasks for copy_noc and EOT_noc. Extra care must be taken to avoid cyclic dependencies in the analysis, as explained in the next section.

Handling Communications Cyclic Dependencies

WCRT and cycle problem. This section presents the problem of cycle that can occur when the method is applied to a program where two clusters are sending data to each other through the NoC. The issue is that the duration of the RX tasks depends on the duration of the EOT, and when the EOT task performs memory accesses, its duration depends on the memory access from the NoC.

For example, in Fig. 5, Cluster 1 and Cluster 3 are communicating in both ways. The WCRT of RX 1 is WCTT 1→3 + WCRT(EOT 1 ). Since RX is arbitrated with the highest priority, we do not need to consider other SMEM accesses interfering with the reception of data. However, WCRT(EOT 1 ) depends on memory interferences, hence it depends on WCRT(RX 2 ) and the release date of RX 2 , may or may not allow the analysis to conclude that RX 2 and EOT 1 have no overlap hence no interference. Similarly, the WCRT of RX 2 depends itself on the WCRT of RX 1 and its release date. In other words, the duration of an RX task depends on the duration of the corresponding EOT task.

τ B τ D E O T E O T τ A τ C τ E Core 1
The difference with the usual task graphs analyzed by the MIA tool is that task RX 1 does not depend on EOT 1 , but its WCRT depends on WCRT(EOT 1 ). This kind of dependency is not supported by existing interference analysis.

Cycle Breaking Method. This method relies on an implementation of the TX and EOT tasks ensuring that EOT does not perform any data memory access. Furthermore, we guarantee that there is no concurrent task accessing the TX engine bus. This implementation ensures WCRT(EOT) = WCET(EOT) since there is no interference.

The duration of RXs is computed using the WCET of EOT tasks and the WCTT. Since we consider a response time for EOT which does not depend on interferences, only one instance of the release date computation tool is required even if there are cycles.

EOT is just a single store instruction writing in a hardware register. It does not perform memory access other than the fetch, and since the MPPA architecture has different arbiters for memory banks and TX, this register access cannot interfere with accesses to memory banks. Nevertheless, the fetch for this instruction can lead to an instruction cache miss. The implementation must ensure that this miss occurs in the copy_noc function instead of the EOT_noc function. There are several methods: either a __builtin_prefetch can be called to fetch the instruction into the cache at the end of the copy_noc task, or the code alignment can be chosen to make sure that the instruction cache line containing EOT has already been loaded when it executes. We use the latter in the experiments.

EXPERIMENTS

In this section, we evaluate our method concerning two aspects: the gain obtained compared to the naive method, and the efficiency of the guaranteed time-triggered execution.

Evaluation of the timing analysis model

In this section we show how much our method improves the naive version introduced in Section 3.2. For this purpose we implemented the naive method without our method to break the cycle: we overapproximate the duration of the calculation+Copy+EOT tasks instead. This duration is used to compute the duration of the RX task. Then we apply the release date computation procedure from Rihani et al. [START_REF] Rihani | Response Time Analysis of Synchronous Data Flow Programs on a Many-Core Processor[END_REF]. The estimated response time of EOT is then injected in the next iteration.

For this experiment, we consider an application composed of 10 tasks mapped on two clusters, using two cores per cluster. The WCTT is 120 cycles and each NoC transfer is 20 words long. For the improved version, the EOT task has a WCET of 20 cycles. Copy 1 and Copy 2 have a WCET of 100 cycles and 30 words of memory demand. Each task n 1 ... n 10 has WCET of 100 cycles and a memory demand of 30 words of 32-bits. For the naive version, we consider tasks including all stages: (n 1 +Copy 1 +EOT 1 ) and (n 2 +Copy 2 +EOT 2 ) have a WCET of 220 cycles and 60 words of memory demand.

In the case of the naive approach, the cyclic dependency requires to re-launch MIA with an updated duration for the RX tasks until convergence (2 iterations are needed for this example).

The naive and improved schedules are depicted respectively in Fig. 6 and Fig. 7. A detailed comparison is given in Table 1. To ease comparison, we show WCRT of Copy and EOT tasks which are normally included in n 1 and n 2 in the naive implementation, but n 1 + Copy 1 + EOT 1 is considered as a single task in the analysis (and likewise for n 2 + Copy 2 + EOT 2 ). The reduced WCRT's of the RX tasks and of n 3 lead to a reduced global WCRT and the one of task n 3 , and an earlier release date for 6 tasks. In the naive version, RX 1 interferes with n 2 + Copy 2 + EOT 1 and n 9 which run on the core associated with the target memory bank, and with n 6 , which writes to the target memory bank. Since RX 1 writes 20 words with a high priority, it delays tasks that may interfere by 20 cycles. In the proposed version, RX 1 is guaranteed to start later, and does not interact with n 2 , textCopy 2 nor n 6 , which are therefore 20 cycles faster.

This globally shows that our model is good when the NoC communication leads to memory interference.

Task

Release

Evaluation of our guaranteed Time-triggered execution

This experiment is performed on two applications: the ROSACE case study and a synthetic benchmark running on 64 cores. Our improved method with cycle breaking is used to implement them. We evaluate the Worst-case response time of our Time-Triggered (WCRT TT ) solution, and compare it to 2 different implementations:

(1) a single-core implementation, where all tasks are executed sequentially, gives a basic execution time to measure the speedup due to parallelization; (2) a best effort implementation, where each task starts as soon as possible, gives the Event Triggered execution time (measured ET ); this Measured ET does not offer any real-time guaranties, but gives a rough (and unreachable) upper-bound to the speedup due to parallelization.

To simplify the experimental setup, the WCET in isolation is evaluated using measurements on the Kalray MPPA2 running at 400 Mhz. Stronger guaranties would be obtained using a WCET analysis tool like OTAWA [START_REF] Ballabriga | OTAWA: an open toolbox for adaptive WCET analysis[END_REF]. This would not change the interference analysis step, hence would not change the conclusions of this experiment.

Note that, in these experiments, there is no computation in parallel with the NoC communications due to the structure of these benchmarks. [START_REF] Pagetti | The ROSACE case study: From simulink specification to multi/many-core execution[END_REF] is a case-study whose structure is inspired by true avionic control applications. Only altitude is controlled, hence it does not require heavy computation. It is composed of a controller and an aircraft simulator. We implement the whole application on the MPPA2. The simulator and the controller run on two different clusters communicating through the NoC. The solution relies on 2 cores of the environment cluster and 5 cores of the controller cluster. Five floating-point numbers are transmitted from the environment to the controller and 2 floating-point numbers are transmitted from the controller to the environment. Our implementation relies on hyper-period expansion similarly to [START_REF] Graillat | Parallel Code Generation of Synchronous Programs for a Many-core Architecture[END_REF] and [START_REF] Rihani | Response Time Analysis of Synchronous Data Flow Programs on a Many-Core Processor[END_REF].

ROSACE Case Study. ROSACE

In order to experiment the influence of computation load on the execution time, we created several versions of the application with different computation loads in each computing task of the controller. The "pure-ROSACE" version, the "ROSACE+100" where 100 cycles are added in each computing task of the controller, the "ROSACE+200" where artificial computations of 200 cycles are added to each node. We measure the latency of the computation as a duration between the beginning of the period and the reception by the environment of the data computed by the controller. Table 2 shows the timing obtained for each implementation. WCRT TT offers good speedups for ROSACE+100 and ROSACE+200. The difference with the speedups obtained with the best-effort execution (Measured ET ) gives an idea of the cost of timing guarantees.

ROSACE

The performance is reduced for pure-ROSACE since, the cost of computation is negligible compared to the one of NoC communication. Note that the performance loss is due to the time-triggered nature of the model, but not to the way we combine NoC and memory interference analyses.

Synthetic Benchmark on 64

Cores. We designed a synthetic benchmark running on 64 cores. The purpose is to apply our method on a highly parallel application with important data transfers and observe the time-triggered implementation. The application runs on 16 clusters and in each cluster, the program executes 4 tasks in parallel on 4 cores. Fig. 8 shows NoC communications involved in the application. Clusters are sorted so that clusters with direct links are represented adjacent to form a grid, but their number correspond to the physical layout. I/O clusters and their routers are not represented. The dispatch operation (Fig. 8a) follows a tree of nodes while the gather operation is composed of point to point communication to cluster 0.

As shown in Fig. 8c, in each cluster a split task receives the inputs from the NoC. The results are centralized by a join task and sent through the NoC by specific tasks (NoC_Copy and NoC_EOT). Tasks t1, t2, t3 and t4 are computation tasks.

The packets are 17-flit long, i.e. 17 words of 32 bits. In average the WCTT are 98 cycles for the flows of Fig. 8a and 1227 cycles for the flows of Fig. 8b. The difference is due to the highest number of concurrent flows of the gather operation compared to the dispatch operation. Table 3 shows the speedup obtained by each method. WCRT TT has a good speedup and is 38% slower than the non-guaranteed best-effort Measured ET method. Since WCRT TT offers strong real-time guarantees, this result is good.

Execution time

RELATED WORK

Skalistis et al. [START_REF] Skalistis | Worst-Case Execution Time Analysis for Many-Core Architectures with NoC[END_REF] present a method similar to Rihani et al. [START_REF] Rihani | Response Time Analysis of Synchronous Data Flow Programs on a Many-Core Processor[END_REF] to compute time-triggered schedules taking into account interferences. This method considers shared-memory communications and communication through the NoC. However, the architecture is different: they consider a Direct Memory Access (DMA) engine which is programmed by the core with an address and a size and this DMA copies data from the memory to the remote memory through the NoC. A NoC communication is modeled with 3 tasks: an initialization task to configure the DMA, a transfer task which performs both local memory accesses and remote memory accesses and the finalization task which ends when the DMA has finished. The duration of the transfer task corresponds to the WCTT plus the copy of the data. This is close to the model of Tendulkar et al. [START_REF] Tendulkar | Many-core scheduling of data parallel applications using SMT solvers[END_REF] where the transfer is in two phases and represented with an initialization task and a transfer task. At the opposite, in our model the core is responsible for copying the data from the memory to the NoC transmission buffer. Consequently, the duration of our reception task (RX) does not include the duration of the copy from the local memory.

If we focus only on the NoC model and aside from the hardware differences, our solution allows a finer analysis since we can decouple the copy from the NoC transmission. In other terms, their approach would lead to intermediate results between our naive and our improved method. Furthermore, our method relies on the MIA tool for interference analysis, which has been shown to lead to more precise results [START_REF] Rihani | Many-Core timing Analysis of Real-Time Systems[END_REF].

Note that there is extensive work on timing verification techniques for scheduling of the NoC, or considering that tasks on each core execute out of local memory with the only interaction with packet flows being through a consideration of release jitter (surveyed in [START_REF] Hesham | Survey on Real-Time Networks-on-Chip[END_REF][START_REF] Kiasari | Mathematical Formalisms for Performance Evaluation of Networks-on-chip[END_REF]). This complementary work could be combined to what we present in this paper. As said before, our paper is also orthogonal to work focusing on schedling and memory or task mapping. For instance, work by Giannopoulou et al. [START_REF] Giannopoulou | Mixed-criticality scheduling on clusterbased manycores with shared communication and storage resources[END_REF] uses network calculus to bound the worst-case traversal time over the NoC and introduces endpoint tasks. They focus on the problem of memory bank assignment to minimize interferences. As future work, it would be interesting to combine their work to what we present in this paper.

CONCLUSION AND FUTURE WORK

In this paper we present a method to compute a global, timetriggered schedule on a many-core platform. We focus on NoC communications between tasks running on different clusters, and their impact on memory access interferences. Our solution is integrated into an existing method focused on shared-memory communication in a single cluster. To fit the existing model, we model the NoC communication using virtual tasks. To avoid pessimism due to uncertainty on the possible execution time of the NoC reception, we split the replication phase in two tasks, and identify precisely the instant where the NoC transmission starts. To avoid cyclic dependency, we use the hardware mechanisms provided by the MPPA to avoid any memory access, hence any potential interference, during the transmission phases.

We introduce an implementation and modeling method that leads to tight response-time and an efficient scheduling (earlier release date) by splitting network access from task computation. We applied the method to a use-case inspired from avionic application and a synthetic benchmark to evaluate the time-triggered execution. The time-triggered implementation offers real-time guarantees and a parallelization speedup close to the best-effort execution.

We describe a problem due to cycles in the communications through the NoC. In the paper, we solved this problem by breaking the cycle using hardware mechanisms. As future work, this problem could be solved by a fixed-point computation, as used in section 4.1 for the naive approach. This would make the approach applicable to architecture where our hardware mechanisms does not exist. However, to be generalized, it would be necessary to prove that the fixed-point iteration terminates.

Figure 1 :

 1 Figure 1: Overall view of the MPPA processor. Cl i squares are clusters (containing 16 cores each), and {N,S,E,W} i (North/-South/East/West) squares are NoC routers part of the I/O clusters.

Figure 2 :

 2 Figure 2: NoC communication path from a core (1) to a remote memory bank (5). In each cluster, only one bank and one TX engine are represented. (4) is the memory bank arbiter.

Figure 3 :

 3 Figure 3: NoC Transmission from τ A to τ E on different clusters. RX A represents the possible interference from NoC to the memory of τ E .

Figure 4 :

 4 Figure 4: NoC Transmission from τ A to τ E on different clusters. The NoC communication is represented with two tasks: Copy and EOT.

2 Figure 5 :

 25 Figure 5: Cycle problem where two clusters are communicating in both ways.

2 Figure 6 : 2 Figure 7 :

 2627 Figure6: Schedule using the naive approach on an application mapped to two clusters.

  In each cluster, 4 cores execute tasks in parallel.

Figure 8 :

 8 Figure 8: Overview of the synthetic benchmark involving 16 clusters.

Table 1 :

 1 Comparison of WCRT and release dates with both methods (in bold where there is a difference).

			date		WCRT
		Naive Improved Naive Improved
	Application			550	540
	Copy 1	130	110	100	110
	Copy 2	130	110	100	110
	EOT 1	230	220	20	20
	EOT 2	230	220	20	20
	RX 1	0	220	450	220
	RX 2	0	220	450	220
	N 1	0	0	130	110
	N 2	0	0	130	110
	N 3	0	0	180	160
	N 4	180	160	100	100
	N 5	450	440	100	100
	N 6	0	0	180	160
	N 7	180	160	100	100
	N 8	450	440	100	100
	N 9	250	240	120	120
	N 10	250	240	120	120

Table 2 :

 2 ROSACE case study. Speedup of the parallel executions on the MPPA2.

	ROSACE+100 ROSACE+200

Table 3 :

 3 Synthetic benchmark running on 64 cores.

			Speedup
	Single-core	358 ms	x1
	Measured ET 31 ms	x11.46
	WCRT TT	51 ms	x7.08


Karim Belabas

Jean-François Jaulent

The logarithmic class

come

Introduction

Classically the class group and unit group of a number field F are defined using the canonical factorization of principal fractional ideals into prime ideals of the ring of integers Z F :

(x) = p p vp(x) , x ∈ F × .

The family of valuations (v p ) p determines a natural morphism from the multiplicative group F × into the free abelian group generated by the prime ideals I F = ⊕ p Z p whose kernel and cokernel are respectively the units E F = Z × F and the ideal class group Cl F attached to F ; this yields the standard exact sequence

1 ---→ E F ---→ F × div ---→ I F = ⊕ p Z p ---→ Cl F ---→ 1, 1
where div(x) = v p (x) p . Geometry of numbers then shows on the one hand that the ideal class group is finite and on the other hand that the unit group E F is the direct product of the cyclic subgroup µ F of roots of unity contained in F and a free Z-module of rank r F + c F -1, where r F are c F denote respectively the number of real and complex places of F .

The logarithmic class group and units are defined in an analogous way, by replacing the classical valuations (v p ) p by an ad hoc family ( v p ) p taking other arithmetic parameters into account. Before introducing them, let us fix an arbitrary prime number and tensor the above sequence by Z , which is flat over Z:

1 ---→ Z ⊗ Z E F ---→ Z ⊗ Z F × div ---→ ⊕ p Z p ---→ Z ⊗ Z Cl F ---→ 1,
where Z ⊗ Z Cl F is nothing else than the -Sylow subgroup of the class group and the kernel Z ⊗ E F is the direct product of the -group µ ( ) F of -primary roots of unity in F and a free Z -module of rank r F + c F -1.

We now define the -adic logarithmic valuations by keeping the ordinary definition v p = v p at places p , but we modify them at places p above [START_REF] Jaulent | Classes logarithmiques signées des corps de nombres[END_REF]:

v p (x) = - Log N Kp/Q (x) deg p ,
where Log is the Iwasawa logarithm, N Kp/Q is the norm operator attached to the local field extension K p /Q and deg p is a normalization factor chosen so as to yield the local Hilbert symbol [START_REF] Jaulent | Sur le noyau sauvage des corps de nombres[END_REF]:

ζ, x p = ζ vp(x) for ζ ∈ µ ( )
F and x ∈ F × , for all finite places p of F . (We shall give an explicit definition for deg p in the next section together with an algorithm to approximate it.) We finally replace in the last exact sequence the classical valuations v p and the div map by a new div = ( v p ) p , thereby defining the group of logarithmic units E F and the logarithmic class group Cl F for the prime :

1 ---→ E F ---→ Z ⊗ Z F × div ---→ ⊕ p Z p ---→ Cl F ---→ 1.
Just as the image P F = div(F × ) in I F yields the subgroup of principal ideals, the image P F of div defines the subgroup of principal logarithmic divisors.

At this point appears an essential difference compared to the classical case, akin to what happens in the function field case: if we define the degree of a logarithmic divisor d = p α p p in ⊕ p Z p additively, deg p α p p = p α p deg p, then the product formula for absolute values shows that principal logarithmic divisors have degree 0; in other words,

P F ⊂ {d ∈ ⊕ p Z p : deg d = 0} .
It is then natural to consider the quotient group, i.e. the subgroup Cl 0 F ⊂ Cl F formed by the classes of degree 0.

By -adic class field theory (cf. [START_REF] Jaulent | Théorie -adique globale du corps de classes[END_REF][START_REF] Gras | Class field theory[END_REF]), the group Cl 0 F appears as a canonical quotient of a standard Iwasawa module and the group of logarithmic units E F as the subgroup of norms in the cyclotomic Z -extension of F . It would follow from a conjecture of Kuz'min (also known as "generalized Gross conjecture") that the group Cl 0 F is finite, or equivalently that the group E F of logarithmic units is the direct product of the cyclic -group µ ( ) F and a free Z -module of rank r F + c F ; and the Gross-Kuz'min conjecture is equivalent to these statements. The Baker-Brumer independence theorem shows that those assertions are true when the number field F is abelian over Q. More generally, they hold when there exist a subfield K of F , abelian over Q, such that there is a single place p F of F above each -adic place p K of K, see [START_REF] Jaulent | Normes cyclotomiques naïves et unités logarithmiques[END_REF].

Moreover, as suggested by the explicit expression of the Hilbert symbol above, the group Cl 0 F is closely related to the wild kernels of K-theory. Precisely, if s 1 is such that the field F contains the 2 s -th roots of unity, then the finite group WK 2 (F ) and the quotient Cl 0 F ⊗ Z Z/ s Z have the same s -rank (cf. [START_REF] Jaulent | Sur le noyau sauvage des corps de nombres et le groupe des classes logarithmiques[END_REF]). A similar result holds for the higher étale kernels WK 2i (K), i 1 (cf. [START_REF] Jaulent | Approche logarithmique des noyaux étales sauvages des corps de nombres[END_REF]).

Last, as for ideals, transition morphisms (norm and extension) attached to a number field extension K/F lead to the definition of logarithmic inertia degrees f (p K /p F ) and ramification indices e(p K /p F ) for p K ⊂ Z K dividing p F ⊂ Z F , with formal properties analogous to the classical indices e(p K /p F ) and f (p K /p F ), without coinciding with them. These local indices are multiplicative and satisfy the product formula

e(p K /p F ) f (p K /p F ) = e(p K /p F )f (p K /p F ) = [K p : F p ].
They are introduced as follows: by multiplicativity, it suffices to define f (p

F /p) since f (p K /p F ) = f (p K /p) / f (p F /p). Now let F ab p be the maximal subextension of the local field F p which is abelian over Q p . The classical inertia degree f (p/p) is the degree [F ab p ∩ Q unr p : Q p ], where Q unr p denotes the unramified Ẑ-extension of Q p . The logarithmic inertia degree is the degree [F ab p ∩ Q c p : Q p ],
where Q c p is the cyclotomic Ẑ-extension of Q p . In particular the logarithmic indices do not depend on the choice of the prime .

One says that the extension K/F ramifies logarithmically at a finite prime p F whenever e(p K /p F ) > 1 for some p K | p F . As in the classical case, an extension of number fields is unramified (in the logarithmic sense) except at a finite number of primes. However a logarithmically unramified extension may ramify in the ordinary sense. Such extensions play a crucial role in the capitulation for the Bertrandias-Payan module studied in the present volume (cf. [START_REF] Gras | Sur le module de Bertrandias-Payan -Noyau de capitulation[END_REF][START_REF] Jaulent | Sur la capitulation pour le module de Bertrandias-Payan[END_REF][START_REF] Nguyen-Quang-Do | Descente galoisienne et capitulation pour le module de Bertrandias-Payan[END_REF]). This note presents our implementation in the PARI/GP system of the various arithmetic invariants attached to logarithmic classes and units. The algorithms do not depend on any conjecture: if the program stops, its output is correct, and it in fact proves that the Gross-Kuz'min conjecture holds for that particular prime and number field F .

Acknowledgements: we thank Sebastian Pauli for sharing his Magma implementation, José Villanueva-Gutiérrez for feedback and examples, and Bill Allombert for many useful discussions. This study has been carried out with financial support from the French State, managed by the French National Research Agency (ANR) in the frame of the "Investments for the future" Programme IdEx Bordeaux -CPU (ANR-10-IDEX-03-02). This research was partially funded by ERC Starting Grant ANTICS 278537.

Algorithmic preliminaries

We recall in this section well known facts from computational number theory, to fix notations. The next section will deal with the main algorithms, germane to the computation of logarithmic objects.

2.1. The Smith Normal Form. We say that a Z-module of finite type G is known if

• we have a Smith Normal Form description (SNF)

G = 1 i s Z/(d i ) • g i ,
for some generators g i , where

d s | • • • | d 1 are the elementary divisors of G; if G has a free part of rank r, then d 1 = • • • = d r = 0. If r = 0, then G is finite and its exponent e(G) is d 1 . • we can solve discrete logarithm problems in G, i.e. decompose elements x ∈ G as x = i s x i • g i , where x i ∈ Z/(d i ). More generally, let R be a matrix in M s×t (Z). A Z-module of finite type G is given by generators (g 1 , . . . , g s ) and relations R when (g 1 , . . . , g s ) • X = 0 G holds for some X ∈ Z s if and only if X = M Y for some Y ∈ Z t . In that case, there exist matrices U ∈ GL s (Z) and V ∈ GL t (Z) such that U M V is in Smith Normal Form (SNF), i.e. U M V = D | 0 when t s or D 0 when t s,
where D is the diagonal matrix diag(d 1 , . . . , d s ). In both cases, (g 1 , . . . , g s )

• U -1 are SNF generators of order d s | • • • | d 1 .
The SNF algorithm applied to R produces U and V in polynomial time (in s, t and log R 2 ).

The same technique allows to handle Z -modules: when R ∈ M s×t (Z ), there exist U ∈ GL s (Z ) and V ∈ GL t (Z ) such that U M V is in SNF. Given M N = M mod N , the above algorithm applied to (M N | N Id s ) produces U and V modulo N and the matrix U -1 modulo N describing SNF generators for G ⊗ Z Z/( N ), the running time is now polynomial in s, t and N log .

Computational algebraic number theory.

The number field F of degree n is given by the minimal polynomial T ∈ Z[X] of an integral generating element, in other words F = Q[X]/(T ). We write X for the class of X mod T ; an element α ∈ F is given by a rational polynomial A ∈ Q[X] such that α = A(X). For any α ∈ F we let α = v max(1, |α| v ) where v runs through all places of F and |α| v is the attached normalized absolute value. We assume given a Z-basis of its maximal order Z F . This is in general an expensive invariant, not necessary for all our algorithms, for instance Algorithm 1 and Corollary 3.5; on the other hand current algorithms to compute the class group of F and the unit group Z × F require it.

We further assume that the class group Cl F and unit group E F are known in the sense of 2.1. In the context of the class group Cl F , the discrete logarithm problem is solved in I F in the following extended sense. The generators classes are represented by integral ideals g i ; given a fractional ideal a in I F , we can find α ∈ F × so that our ideal decomposes as a product of the generators g i multiplied by the principal ideal (α). We refer to [START_REF] Cohen | A course in computational algebraic number theory[END_REF] for how to handle these standard tasks. Practical algorithms to compute Cl F and E F require assuming the truth of the Generalized Riemann Hypothesis for the unramified Hecke L-functions L F (χ, s), χ ∈ Cl F , and for the Riemann ζ function. But this assumption can be lifted provided the discriminant disc F is not too large. (The certification process requires time proportional to |disc F |.)

To each maximal ideal p ⊂ Z F above a rational prime p we attach the completed local field F p . There exist an irreducible monic divisor

T p ∈ Z p [X] of T , of degree n p = [K p : Q p ] = e(p/p)f (p/p), such that K p = Q p [X]/(T p ).
Given T and a prime p, and for any given p-adic accuracy k, we can produce in polynomial time

O(k log p • n log T ∞ ) C
• the prime ideals p i = pZ F + π i Z F dividing p, together with their ramification indices and residue degrees, where v p i (π i ) = 1 (this is automatic if e(p i /p) > 1 and one of π i or π i + p satisfy this condition in any case);

• for each p i , a p-adic approximation T p i ,k ∈ Z[X] such that T p i ,k ≡ T p i
(mod p k ); see for instance the Round 4 algorithm as finalized in [START_REF] Ford | A fast algorithm for polynomial factorization over Q p[END_REF]. The older (and much simpler) Round 2 algorithm and Buchmann-Lenstra factorization would also achieve this result, see [START_REF] Buchmann | Approximating rings of integers in number fields[END_REF].

Local norms.

We shall need to compute local norms and their Iwasawa logarithms. We can write any α ∈ F × as A(X)/a for a ∈ Z >0 and A ∈ Z[X] and the representation is unique if a and the content of A are coprime. Since N Fp/Qp (a) = a np , we may focus on α

∈ Z[X]. Lemma 2.1. Let α = A(X), α = 0, where A ∈ Z[X]. For each integer k > v p N Fp/Qp (α) , let N k = Res(A, T p,k ) mod p k ∈ Z then N Fp/Qp (α) ≡ N k (mod p k ).
In particular, v p (N k ) = v p N Fp/Qp (α) does not depend on k and

Log p N Fp/Qp (α) ≡ Log p N k (mod p k-vp(N k ) ). Note that if the size α of α is controlled, so is N F/Q (α) α n . Thus v p (N k ) v p N F/Q (α)
is controlled and finally, any k > v p N F/Q (α) satisfies the condition in the lemma. This allows to approximate v p (α) to any given accuracy from a sufficiently precise approximation T p,k of T p .

The main algorithm

We follow the general strategy of [START_REF] Diaz Y Diaz | A new algorithm for the computation of logarithmic l-class groups of number fields[END_REF], while introducing numerous improvements and simplifications along the way. Let be a fixed prime number and denote S = {p 1 , . . . , p l } the set of places of F above . We rely on the obvious exact sequence of pro-groups

0 ---→ Cl( ) ---→ Cl ψ ---→ Cl ---→ 0
where Cl( ) is the subgroup generated by the logarithmic classes of the p i , the group Cl is the -Sylow subgroup of the quotient of the ideal class group by the subgroup generated by the ideal classes of the p i , and where ψ :

p m p p -→ p p mp .
We shall compute the groups Cl( ) and Cl independently, by generators and relations, then build up Cl using the exact sequence. Remark 3.1. We depart here from [START_REF] Diaz Y Diaz | Approche algorithmique du groupe des classes logarithmiques[END_REF][START_REF] Diaz Y Diaz | A new algorithm for the computation of logarithmic l-class groups of number fields[END_REF] which use θ : p m p p → p p ( fp/fp)mp . The latter has good properties in extensions, which we will not need. When the field is fixed, it makes no difference: for p , the factor f p /f p belongs to Z × so the kernel and cokernel of θ and ψ are the same. More substantially, we do not restrict to degree 0 divisors Cl( ) 0 and Cl 0 at this stage, which would introduce a nontrivial cokernel (as some ideal classes might not be representable by degree 0 divisors). This avoids the technical difficulty of having to modify natural generators so that their degree become zero as in [START_REF] Diaz Y Diaz | A new algorithm for the computation of logarithmic l-class groups of number fields[END_REF]Corollary 18]. This is not obvious and Corollary 18 is incorrect as stated.

Computing e(p/p), f (p/p) and v p (•)

. We first explain how to compute the logarithmic inertia and residue degrees. The algorithm is a straightforward consequence of the following two lemmas: Lemma 3.2. Let p be a maximal ideal above a rational prime p. We write e, f , e, f respectively for e(p/p) f (p/p), e(p/p) and f (p/p).

(1) We have e f = n p = ef .

(2) The prime to p part of e and e coincide, i.e. v q (e) = v q ( e) for all primes q = p. (3) The logarithmic ramification index e and [h p (F × p ) : Z p ] have the same valuation at p, where

h p (α) = Log p N Fp/Qp (α) n p • (2p) . Note that h p (Q × p ) = Z p . (4) We have v p ( f ) v p (e).
In particular if p e, then v p ( e) = v p (f ) and v p ( f ) = 0.

Proof. The first three points are proved in [START_REF] Jaulent | Classes logarithmiques des corps de nombres[END_REF]. The final one follows from a direct calculation using h p or using the abstract definition where Q c p is the compositum of all cyclotomic Z q extensions of Q p on all prime numbers q. Thus the p-primary part of f is the degree over Q p of the intersection L of 3: Let g 0 ← π and let (g 1 , . . . , g s ) be independent generators for the finite abelian group (1 + p)/(1

f (p/p) = [F ab p ∩ Q c p : Q p ],
+ p k ); see [4, §4.2.3]. 4: Let v ← min 0 i s v p Log p N Fp/Qp (g i ) , computed using Lemma 2.1. 5: Let v ∞ = k + v p (D Fp/Qp ) /e . If v ∞ < v, let v ← v ∞ . 6: Let v ← v -v p (f • 2p). Set e ← e • p -v and f ← f • p v .
Proof. The problem boils down to computing the valuation at p of e(p/p). Using statement (3) in the lemma, this is the non-negative integer w such that h p (F × p ) = p -w Z p . We decompose F × p = π Z × µ Fp × (1 + pZ Fp ); since h p is additive and h p (µ Fp ) = 0, it is enough to determine the valuation of h p evaluated at π and on multiplicative generators of 1 + pZ Fp , i.e. on generators of (1 + p)/(1 + p k ) and 1 + p k ; the latter are handled by Lemma 3.3 yielding the v ∞ contribution. Remark 3.4. By Lemma 3.3, if generator g = g i of the p-group (1 + p)/(1 + p k ) has order d = d i , then Log p N(g d ) has valuation v ∞ . So, when we compute the minimum of the valuations incrementally for g 1 , g 2 , . . . , by decreasing order, we can stop as soon the lower bound v ∞ -v p (d i ) for the valuation of Log p N(g i ) becomes larger than the current minimum. We can also restrict to the generators of (1+p)/(1+p k ) modulo the p-primary roots of unity in F p . Finally, we compute

v p Log p N Fp/Qp (g i ) as v p N Fp/Qp (g i ) -1 for i > 0.
In comparison, the algorithms of [6, §3.1] need the full set of multiplicative generators of 1 + pZ Fp , whose description is complicated and uses the principal unit filtration up to k = pe/(p -1). Introducing v ∞ thus reduces the size of the generator system by a rough factor p; and we in fact expect to consider only g 0 and g 1 due to the a priori lower bound v ∞ -v p (d i ). The early abort when v p (e) = 0 also skips the non-trivial part of the algorithm unless p belongs to the tiny set of (wildly ramified) prime divisors of [F : Q]. Corollary 3.5. Let be our fixed prime and p be a maximal ideal above some prime p. Lemma 2.1 and Algorithm 1 allow to compute the following quantities to any desired -adic accuracy in time polynomial in log , log p, n, log T ∞ and log x

(1) deg p = f (p/p) deg p, where deg p =        Log p if p = , if p = = 2, 4 if p = = 2.
(

) For x ∈ F × , v p (x) =          v p (x) if p = , - Log p N Fp/Qp (x) deg p if p = . 2
Remark 3.6. The logarithmic degree deg may be multiplied by an -adic unit without changing the structure of Cl. In other contexts, defining respectively deg = Log (1 + ) and Log 2 (1 + 4) will be more convenient. Indeed, with the latter definition, the exponential of deg p would always be a natural number.

3.2. The group Cl . Let S be the set of places above . We compute the S-class group Cl F / S =

1 i s (Z/d i Z) • g i ,
where each g i has order d i and

d s | • • • | d 1 ,
using the obvious definition by generators (the g i generating the class group) and relations (the subgroup generated by the classes of elements of S) and computing the attached SNF, see [4, §7.4.2]. We obtain its -Sylow subgroup Cl by raising each SNF generator g i to the power

d i -v (d i )
. Alternatively, we can first read off the exponent e = v (d 1 ) of Cl from the SNF description of Cl F / S , then compute its -adic SNF by adding g e i = 1, i s, to the relations. The latter method is likely to yield smaller base change matrices, hence smaller generators. In any case, the generators of Cl are represented by integral ideals in Z F , which we may assume to be coprime to . Indeed, if g ⊂ Z F is an arbitrary generator and (g Z ) = g ∩ Z, we can replace g by

g + g Z • -v (g Z ) Z F = g • p| p -vp(g) .
Solving the discrete logarithm problem is a standard extension, see [4, §4.1.3]. The only thing to note is that as described the algorithm will produce huge generators, as the initial class group generators are raised to huge powers through the necessary linear algebra. We use the "group ring representation" from [1, §7] keeping principal ideals in factored form, i.e. as elements in Z[Z F ], and LLLreducing general ideals along the way; in this manner the principal parts, in class groups or S-class groups discrete logarithm decompositions, are obtained in the form α = i r α e i i , where the α i are small elements in F ( α i is controlled) and the e i are possibly large integers. Definition 3.7. For any α ∈ Z[Z F ] given in factored representation we write x ∈ Supp α when x belongs to the support of α, i.e. is one of the α i ∈ Z F occuring in the factored representation. This factored representation of elements is quite suitable to compute multiplicative or additive functions such as local norms and their -adic logarithms, or standard and logarithmic valuations v p and v p .

3.3. The group Cl( ). We describe Cl( ) by generators (the classes of the -adic places S = {p 1 , . . . , p l }) and relations (derived from div(u) = 0, u an S-unit). Thus the group is given by the -adic SNF of the matrix M = v p i (u j ) , where the (u j ), 1 j J = r F + c F + l -1, generate the free part of the S-unit group.

The (u j ) are computed as in [4, §7.4.2], again taking care to use factored representations. Let

δ(u 1 , . . . , u J ) = max i v (deg p i ) + max j, α∈Supp u j v (N Fp i /Q (α)) ,
where Supp u j was defined in the previous paragraph. This quantity accounts for the maximal loss of accuracy when approximating the v p i (u j ) by Lemma 2.1 and Corollary 3.5. For increasing N > log 2 δ, we approximate the v p i modulo 2 N > δ and compute the SNF of M modulo L N = 2 N -δ . We may stop as soon as the computed SNF has a single elementary divisor of largest valuation:

Lemma 3.8. If the computed SNF of the finite -group Cl( ) / Cl( ) L N = i s Z/( v i ) • g i has a single elementary divisor of largest valuation v 1 > v 2 ,
then the Gross-Kuz'min conjecture for the field F and the prime holds. Indeed, in this case, we have Cl(

) = Z • g 1 ⊕ Cl( ) 0 , where Cl( ) 0 = ⊕ i>1 (Z/ v i ) • g i has exponent v 2 .
Proof. Cl( ) has Z -rank bigger than 1 due to the product formula:

i l deg p i • v p i (x) = 0,
for any S-unit x. The Gross-Kuz'min conjecture states that this rank is exactly 1.

Concretely, we apply the SNF algorithm to obtain matrices U ∈ GL l (Z) and

V ∈ GL r F +c F +2l-1 (Z) such that U M mod L N | L N • Id l V = diag(d i ) | 0 is in rectangular Smith Normal Form, and stop when L N = v (d 1 ) > v (d 2 )
. The g i are given in terms of the logarithmic classes of the p i by (g 1 , . . . , g l ) = (p 1 , . . . , p l ) • U -1 .

We then delete the trivial g i , s < i l, such that d i = 1. Of course, the algorithm will not stop if the conjecture is false and rk Z Cl( ) > 1. Remark 3.9. This is the equivalent of Algorithm 14 and Theorem 16 in [START_REF] Diaz Y Diaz | A new algorithm for the computation of logarithmic l-class groups of number fields[END_REF], simplified by the fact that we do not need the generators to have degree 0. The system of -adic α j ∈ F × ⊗ Z Z such that v p i (α j ) = δ i,j are no longer needed. (Note that the construction given before [START_REF] Diaz Y Diaz | A new algorithm for the computation of logarithmic l-class groups of number fields[END_REF]Algorithm 19] must be modified so that it guarantees that (α j , ) = 1.) 3.4. The logarithmic class group. We use [4, §4.1.4] to describe Cl by generators and relations. The logarithmic classes of the -adic places {p 1 , . . . , p l } generate Cl( ), with relations computed above. Let ⊕ i s (Z/d i ) • a i be the SNF of Cl where we chose integral ideal representatives a i coprime to for the generating ideal classes. We now need to determine the matrix P . Lemma 3.10. For each 1 i s, write

a d i i = (α i ) j l p * i,j j
for some principal ideal (α i ) and integral exponents * i,j . Let P ∈ M s×l (Z ) be the matrix v p j (α i ) . In the group Cl, it holds Proof. Since the ideal a i is coprime to , it follows that p p vp(α i ) = a d i i and that, in Cl, we have

0 = div(α i ) = p v p (α i ) • p + j l v p j (α i ) • p j = d i • a i + j l v p j (α i ) • p j .
Concretely, the decomposition

a d i i = (α i ) j p * i,j j
is computed by solving a discrete logarithm problem in Cl F where, as usual, the (α i ) i s are given in factored representation. As in §3.3, we bound the loss of accuracy when estimating the v p j (α i ) and set L := max δ(α 1 , . . . , α l ), v (e(Cl )) + v (e( Cl( ))) + 1 .

Then we compute the SNF of M mod L L • Id l P mod L 0 0 diag(d 1 , . . . , d s ) .

Including the kernel and image exponents in the maximum guarantees that the SNF has a unique maximal elementary divisor, allowing to split off the rank 1 Z -free part and the finite Cl 0 F .

Lemma 3 . 3 .Algorithm 1 1 : 2 :

 33112 F ab p with the cyclotomic Z p -extension of Q p . The claim follows by multiplicativity of ramification indices in F p /L/Q p . Let p be a maximal ideal above the prime p with ramification index e = e(p/p). Let D = D Fp/Qp denote the local different and let k > e/(p -1). Then Log p N Fp/Qp (1 + p k ) = p v/e Z p , where v = k + v p (D). Proof. For k > e/(p -1), we have 1 + p k = exp(p k ) and Log p N Fp/Qp (1 + p k ) = Tr Fp/Qp (p k ). We then use the equivalence Tr Fp/Qp p k ⊂ a ⇔ p k D ⊂ a for any fractional ideal a ⊂ Q p . Compute e(p/p), f (p/p) Input: A maximal ideal p = pZ F + πZ F , v p (π) = 1 above some prime p of ramification index e = e(p/p) and residue degree f = f (p/p). Output: e = e(p/p) and f = f (p/p). If v p (e) = 0, set e ← e • p vp(f ) , f ← f • p -vp(f ) and stop. Let n p ← ef and let k ← 1 + e/(p -1) > 1.

(d 1 •

 1 a 1 , . . . , d s • a s ) = (p 1 , . . . , p l ) • (-P ).

  Those generators lift naturally to divisors, still denoted a i , in Cl via p ep → e p p. Then d i • a i belongs to Ker ψ, hence to Cl( ) and we can write(d 1 • a 1 , . . . , d s • a s ) = (p 1 , . . . , p l ) • (-P )in Cl for some matrix P ∈ M l×s (Z ), from which we derive the -adic matrix of relations between the generators (p 1 , . . . , p l , a 1 , . . . , a s ):M P 0 diag(d 1 , . . . , d s )

The bnflog package

4.1. The PARI/GP interface. In PARI/GP [START_REF][END_REF] version 2.8.1, the above algorithms are implemented as functions bnflogef and bnflog. All examples below are written in the GP scripting language.

• The function bnflogef takes as input a number field F and a prime ideal p and returns the logarithmic indices e(p/p) and f (p/p). This is an elementary function requiring only basic arithmetic invariants of F , hence the use of the simple nfinit to define the number field structure:

? T = x^6 -3*x^5 + 5*x^3 -3*x + 1; ? F = nfinit(T); \\ the number field Q[x]/(T) ? P2 = idealprimedec(F,2) [START_REF] Belabas | Topics in computational algebraic number theory[END_REF]; \\ a prime above 2 ? [P2.e, P2.f] \\ ramification index and residue degree %3 = [START_REF] Cohen | A course in computational algebraic number theory[END_REF][START_REF] Buchmann | Approximating rings of integers in number fields[END_REF] \\ e(P/p) = 3, f(P,p) = 2 ? bnflogef(F, P2) %4 = [START_REF] Diaz Y Diaz | A new algorithm for the computation of logarithmic l-class groups of number fields[END_REF][START_REF] Belabas | Topics in computational algebraic number theory[END_REF] \\ etilde(P/p) = 6, ftilde(P/p) = 1

• The function bnflog takes as input a prime and a number field F . It returns a vector of three group structures, given by their elementary divisors: ( Cl 0 F , Cl 0 F ( ), Cl ). This function requires the class group and units of F , hence the more involved initialization using bnfinit:

? \\ all 3 groups are trivial ? bnflog(F, 3) %5 [START_REF] Ford | A fast algorithm for polynomial factorization over Q p[END_REF]] \\ Cl^0 ~Cl' ~Z/(7)

Examples.

• [START_REF] Jaulent | Classes logarithmiques signées des corps de nombres[END_REF], [START_REF] Gras | Sur le module de Bertrandias-Payan -Noyau de capitulation[END_REF]]] [641, 769, [ [START_REF] Jaulent | Classes logarithmiques signées des corps de nombres[END_REF][START_REF] Buchmann | Approximating rings of integers in number fields[END_REF], [START_REF] Jaulent | Classes logarithmiques signées des corps de nombres[END_REF], [START_REF] Buchmann | Approximating rings of integers in number fields[END_REF]]] [1151, 1663, [ [START_REF] Jaulent | Classes logarithmiques signées des corps de nombres[END_REF], [START_REF] Jaulent | Classes logarithmiques signées des corps de nombres[END_REF]

, []]]

• We now give two examples with large 3-rank (and large class group); factored representations must be used throughout to avoid catastrophic cancellation: [START_REF] Cohen | A course in computational algebraic number theory[END_REF][START_REF] Cohen | A course in computational algebraic number theory[END_REF][START_REF] Cohen | A course in computational algebraic number theory[END_REF][START_REF] Cohen | A course in computational algebraic number theory[END_REF][START_REF] Cohen | A course in computational algebraic number theory[END_REF], [], [START_REF] Cohen | A course in computational algebraic number theory[END_REF][START_REF] Cohen | A course in computational algebraic number theory[END_REF][START_REF] Cohen | A course in computational algebraic number theory[END_REF][START_REF] Cohen | A course in computational algebraic number theory[END_REF][START_REF] Cohen | A course in computational algebraic number theory[END_REF]] \\ This assumes the truth of the GRH: ? F = bnfinit(x^2 + 14138863693162613823739799380212181908); ? F.cyc %4 = [693468857222922, [START_REF] Diaz Y Diaz | A new algorithm for the computation of logarithmic l-class groups of number fields[END_REF][START_REF] Diaz Y Diaz | A new algorithm for the computation of logarithmic l-class groups of number fields[END_REF][START_REF] Diaz Y Diaz | A new algorithm for the computation of logarithmic l-class groups of number fields[END_REF][START_REF] Cohen | A course in computational algebraic number theory[END_REF] ? bnflog(F, 3) %5 = [ [START_REF] Cohen | A course in computational algebraic number theory[END_REF][START_REF] Cohen | A course in computational algebraic number theory[END_REF][START_REF] Cohen | A course in computational algebraic number theory[END_REF][START_REF] Cohen | A course in computational algebraic number theory[END_REF][START_REF] Cohen | A course in computational algebraic number theory[END_REF], [START_REF] Gras | Class field theory[END_REF], [START_REF] Cohen | A course in computational algebraic number theory[END_REF][START_REF] Cohen | A course in computational algebraic number theory[END_REF][START_REF] Cohen | A course in computational algebraic number theory[END_REF][START_REF] Cohen | A course in computational algebraic number theory[END_REF]] The final computation is conditional on the truth of the GRH, since it is not practical to certify the class group of a field F with such a large discriminant. The total running time for all the above computations is about 4 minutes, 99% of which are spent in the final example.

• This program prints the smallest real quadratic field whose Cl 0 has 2-rank equal to 5 (and its locally cyclotomic 2-tower is infinite). This fixes a misprint in [START_REF] Jaulent | Sur les tours localement cyclotomiques[END_REF] which erroneously reports

as the real quadratic field with smallest discriminant with this property (but its 2-rank is 4). This computation requires about 5 hours.