Samuel Garcia
email: samuel.garcia@ensea.fr

Bertrand Granado
email: bertrand.granado@ensea.fr

OLLAF : a Fine Grained Dynamically Reconfigurable Architecture for OS Support

In the context of large versatile platform for embedded real time system on chip, a fine grained dynamically reconfigurable architecture could be used as one possible computational resource. In order to manage efficiently this resource we need a specific OS kernel able to manage such a hardware adaptable architecture. Both the history of micro-processor based system and our previous work based on currently available FPGA devices led us to think that not only an OS kernel must be defined to handle an FGDRA but a FGDRA must also be designed to handle this OS kernel. This article relate our original work in this direction. OLLAF 1 , an original FGDRA core that we have designed will be presented. A comparison with other methods used today using commercially available FPGA is also presented concerning the particular preemption service.

I. INTRODUCTION

This work takes place in the SMILE project. This project aims at provide a distributed middle layer to efficiently handle the complexity of a tomorrow's RSoC 2 . This system may contains several computing units of different types. It will embed at least one or more General Purpose Processor (GPP), but also dynamically reconfigurable architectures (DRA) at different granularities and especialy FGDRA 3 . Tomorrow's computing systems has to comply with lots of constraints. Those constraints may be time related, to meet real time requirements, but also power consumption constraints, as it is, and will be more and more, one of the primary concern of electronical devices.

By fine grained, we here means an architecture which is reconfigurable at the bit level. A dynamically reconfigurable architecture, using single bit LUT and flipflop, and providing a bit level reconfigurable interconnection matrix, as the one presented here, or basic logic fabric of most commercial FPGA, are examples of FGDRA. Those kind of architecture can be adapted to any application more optimally than a coarser grain DRA. This feature make them today the platform of choice when it comes to handle computational tasks in a highly constrained context.

In more general terms FGDRA can achieves much better efficiency than GPP does, while offering the same versatility and, potentially, a very close flexibility. The counterpart is that 1 Operating system enabled Low LAtency Fgdra 2 Reconfigurable System on Chip 3 Fine Grained Dynamically Reconfigurable Architecture Fig. 1. Basic view of a RSoC in SMILE it introduces a much greater complexity for application designers. This complexity could be lowered to an acceptable level in two ways. First by providing powerful CAD tool. Lots of research are thus led in the field of high level synthesis [START_REF] Coussy | High-level synthesis under i/o timing and memory constraints[END_REF]. The second way is to abstract the system complexity by providing a middle layer, e.g an operating system, that abstracts the lower level of the system [START_REF] Deng | A Reconfigurable RTOS with HW/SW Co-scheduling for SOPC[END_REF]. Moreover, an OS could manage new tasks at run time. This property is a feature of importance for DRA. For all those reasons, a specialized operating system is required for FGDRA.

In our work we make a difference between a FGDRA, which is a general term, and a FPGA which, for us, relate to an actual silicon device sold under this designation and which can be used as a FGDRA but is actually not designed especialy thor that purpose.

The SMILE project follows a distributed approach of the system. Each computing unit of a RSoC (GPP, DSP, DRA, ...) has its own real time kernel. This topology allows to use a specific custom made real time kernel for each computing unit. It then allows to take into account every specificities of each computing unit. A message passing communication scheme, based on MPI 4 , ensure a consistent operation of the whole system. In this frame of mind, we developed a dedicated real time kernel for a FGDRA.

This kernel is an adaptation to FGDRA of an abstract OS model which could be described as follow :

• it manages the execution of a set of task on a given versatile computational ressource. More concreatly it will run periodically a special algorithm to evaluate where and when to run each tasks. This period is called Tick and is a tradeoff between efficiency and flexibility, a typical value in classical OS is tens of milliseconds.

• it offers an abstracted view of the platform to the task designer. In other terms, each task can be designed without worrying about other tasks and sometimes even about the platform. It then offers a standardized set of services such as communications or synchronizations between tasks. This model slightly differs from most OS implementation proposed for FPGA management even if the overall idea remain the same.

Both the history of micro-processor based system and our previous work based on currently available FPGA devices led us to think that not only an OS kernel must be conceived to handle a FGDRA, but a FGDRA must also be designed to support efficiently this OS kernel. This article relate our original works in this direction. The FGDRA core that we have designed will be presented as well as a more general view of our approach of a FGDRA and its related OS kernel.

This paper is organized as follows. Section 2 discuss of related works in the field of OS for FGDRA. Section 3 explains our original FGDRA platform proposition named OLLAF. Section 4 discuss more precisely of the context management scheme and its extention to configuration management. Section 5 explains how our architecture can affect different OS services. Section 6 exposes an analytic comparison between OLLAF and other methods used todays in terms of preemption overhead and efficiency. Finally, conclusions are drawn in section 7.

II. RELATED WORK

A. OS for FGDRA Several research have been led in the field of OS for FGDRA [START_REF] Simmler | Multitasking on FPGA Coprocessors[END_REF], [START_REF] Chen | Configuration-Sensitive Process Scheduling for FPGA-Based Computing Platforms[END_REF], [START_REF] Walder | Reconfigurable Hardware Operating Systems: From Design Concepts to Realizations[END_REF], [START_REF] Wigley | Introducing reconfigme: An operating system for reconfigurable computing[END_REF]. All those studies present an OS more or less customized to enable specific FGDRA related services. Example of such services are : partial reconfiguration management, hardware task preemption or hardware task migration. They are all designed on top of a platform composed of a commercial FPGA and a micro-processor. This microprocessor may be a softcore processor, an embedded hardwired core or even an external processor.

In the 90's, some works have also been published about the design of a specific architecture for dynamical reconfiguration. In [START_REF] Ling | Wasmii : a data driven computer on virtuel hardware[END_REF] authors discuss about the first multi-context reconfigurable device. This concept as been implemented by NEC on the Dynamically Reconfigurable Logic Engine (DRLE) [START_REF] Shibata | A virtual hardware system on a dynamically reconfigurable logic device[END_REF]. At the same period, the concept of DPGA was introduced, it was also proposed in [START_REF] Dehon | Dpga-coupled microprocessors : Commodity ics for the early 21st century[END_REF] to implement a DPGA in the same die as a classic microprocessor to form one of the first SoC including dynamically reconfigurable logic. In 1995, Xilinx even applied a patent on multi-context programmable device proposed as an XC4000E FPGA with multiple configuration planes [START_REF] Xilinx | Time multiplexed programmable logic device[END_REF].

More recently, in [START_REF] Nollet | Designing an Operating System for a Heterogeneous Reconfigurable SoC[END_REF], authors propose to add special material to a DRA to support OS services, they worked on top of a classic FPGA.

The work presented in this paper try to take advantage of those previous work both about hardware reconfigurable platform and OS for FGDRA.

B. previous work

Our first work on OS for FGDRA was related to preemption of hardware task on FPGA [START_REF] Garcia | Hardware task context management for fine grained dynamically reconfigurable architecture[END_REF]. For that purpose we explored the use of a scanpath at the task level. In order to accelerate the context transfer we explore the possibility of using multiple parallels scanpaths. We also provided the Context Management Unit or CMU, which is a small IP capable to manage the whole process of saving and restoring tasks contexts.

In that study both the CMU and the scanpath were build to be implemented on top of any available commercial FPGA. This approach showed number of limitations. They could be summarized in this way: implementing this kind of OS related material on top of the existing DRA introduce unacceptable overhead on both the task and the OS service. Differently said, most of OS related material should be as much as possible hardwired into the platform's architecture.

III. OLLAF : GENERAL OVERVIEW

A. Specifications of a FGDRA with OS support

We have designed a FGDRA with OS support following those specifications.

It should first address the problem of the configuration speed of a task. This is one of the primary concerns because if the system spend more time configuring itself than actually running tasks, then its efficiency will be poor. The configuration speed will thus have a big impact on the scheduling strategy.

In order to enable more choice on scheduling scheme, and to match some real time requirement, our FGDRA platform must also include preemption facilities. For the same reasons than configuration, the speed of context saving and restoring process will be one of our primary concerns. On this particular point, previous work we have discussed in section 2 will be adapted and reused.

Scheduling on a single GPP system is just a matter of time. The problem is to distribute the computation time between different tasks. In the case of a DRA the system must distribute both computation time and computation resources. Scheduling in such a system is then no more a one dimensional problem, but a three dimensional one. One dimension is the time and the two others are the surface of reconfigurable resources. Performing such a scheduling at run time with real time constraints is at this stage not conceivable. But the FGDRA should help getting close to that goal. The primary concern on this subject is to ensure an easy task relocation. For that, the reconfigurable logic core should be splited into several equivalent blocks. This will allow to move a task from a block Fig. 2. Global view of the FGDRA to any another block or from a of blocks to another group of blocks of the same size and the same form factor without any change on the configuration data. The size of those blocks would be a tradeof between flexibility and scheduling efficiency.

Another aspect of an operating system is to provide inter task communication services. In our case we will distinguish two cases. First the case of a task running on top of our FGDRA and communicating with another task running on a different computing unit, for example a GPP. This case will not be covered here as this problem concern the whole heterogeneous platform, not only the particular FGDRA computing unit. The second case is when two, or more, tasks run on top of the same FGDRA communicate together. This communication channel should remain the same wherever the task is placed on the FGDRA reconfigurable core and whatever state those tasks are (running, pending, waiting, ...). That mean that the FGDRA platform must provide a rationalized communication medium including some sort of exchange memories.

The same arguments could also be applied to inputs/outputs. Here again two cases exist. First the case of I/O being a global resource of the whole platform. Secondly the case of special I/O directly bound to the FGDRA.

B. Proposed solutions

Figure 2 show a global view of OLLAF, our original FGDRA designed to support OS sevices as they have just been specified.

In the center stand the reconfigurable logic core of the FGDRA. This core is organized in columns, each column can be reconfigured separately and offer the same set of services. That means that a task uses an integer number of columns. This topology as been chosen for two reasons. First using a partial reconfiguration by column transforms the scheduling problem into a two dimensional problem (time + 1D space) which will be easier to handle in real time situations. Secondly as every columns is the same and offers the same set of services, tasks can be moved from one column to another without any change on the configuration data.

In the figure, at the bottom of each column you can notice two hardware blocks called CMU and HCM. The CMU as said earlier is an IP able to manage automatically task's context saving and restoring. The HCM standing for Hardware Configuration Manager is pretty much the same but to handle configuration data also called bitstream. On each column a local configuration/context memory is added. This memory can be seen as a first level of cache memory to store contexts and configurations close to the column where it might most probably be required. The internal architecture of the core provides adequate materials to work with CMU and HCM.

More about this will be discussed in the next section.

On the right of the figure stands a big block called "HW Sup + HW RTK + central memory". This block contain a classic microprocessor which serves as a hardware supervisor. It runs a custom real time kernel specially adapted to handle FGDRA related OS services and platform level communication services. Along with this hardware supervisor a central memory is provided for OS use only. Basically this memory will store configuration and eventual context of every task that may run on the FGDRA. This supervisor communicates with all columns using a dedicated control bus.

Finally, on top of the figure 2 you can see the application communication medium. This communication medium provides a communication port to each column. Those communications ports will be directly bound to the reconfigurable interconnection matrix of the core. If I/O had to be bound to the FGDRA they would be connected with this communication medium in the same way reconfigurable columns are.

C. Logic core overview

In order to make the description of the FGDRA core more understandable, we will here split its functionalities between two points of view. The first one is the functional point of view, it consists on the information that a task designer may have to know in order to design the architecture. The second point of view is the configuration point of view, it consists on information about reconfiguration plane. As one of the main goals of the OS is to abstract configuration management, this point of view could be seen as the OS point of view.

Internal architecture of a LE in the functional point of view can be seen on figure 3. This architecture integrates elements that compose a classic Logic Element of FGDRA. If we want to improve functional architecture, it should not change our conclusion on configuration point of view.

A multiplexor based interconnect as been choosen instead of the passing MOS transistor used in most commercial FPGA. In this way we can lower the number of configuration bit required to allow the same connection flexibility. In this last interconnection scheme, the number of configuration bit grow linearly with interconnection possibility while using multiplexor makes it grow as a log2 function.

At first, configuration memory points are modellized as a D flip-flop. This allow us to rapidly apply our works on context management to configuration management. However, configuration and context management remains two separate path, a context swap can be performed without any change in configuration. This can be interesting for checkpointing or when more than one instance of the same task runnning.

IV. CONTEXT MANAGEMENT SCHEME

In [START_REF] Garcia | Hardware task context management for fine grained dynamically reconfigurable architecture[END_REF] we proposed a context management scheme based on a scanpath, a local context memory and the CMU which is a small IP capable of managing automatically context transfer between the scanpath and the local memory. The context management scheme in OLLAF is slightly different in two ways. First, every context management related material is hard wired into the platform. Secondly, we added two more stage in order to even lower preemption overhead and to ensure the consistency of the system.

As context management materials are added at platform level and no more at task level, it needed to be splited differently. As the Programable Logic Core is column based, it was then natural to implement context management at columns level. A CMU and a local memory have then been added to each column, and one scanpath is provided for each column's set of flipflops.

In order to lower preemption overhead, our reconfigurable logic core use a double memory plane. Flipflops used in LE are thus replaced with two FF with switching material. Architecture of this double plane FF can be seen on figure 4. Run and scan are then no more two working modes but two parallel planes which can be swapped as will. With this topology, the context of a task can be shifted in while the previous task is still running and shifted out while the next one is already running. The effective task switching overhead is then taken down to one clock cycle as illustrated in figure 6.

Contexts are transfered by the CMU into Local Context Memories using this hidden scanpath. Because the context of every column can be transfered in parallel, Local Context Memories are placed at column level. It is particularly usefull when task use more than one column. Those memories can contain at this stage 10 contexts. They can be seen as local cache memories to optimize access to a bigger memory called the Central Context Repository. The Central Context Repository is a large memory space storing the context of each task instance run by the system. Local Context Memories should then store contexts of tasks who are most likely to be the next to be ran on the corresponding column.

After a preemption of the corresponding task, a context can be stored in more than one LCM in addition to the copy stored in the Central Context Repository. In such situation, care must be taken to ensure the consistency of the task execution. For that purpose, contexts are tagged by the CMU each time a context saving is performed with a version number. The operating system keep tracks of this version number and also increment it each time a context saving is performed. In this way the system can then check for the validity of a context before a context restoration. The system must also try to update the context copy in the CCR as short as possible after a context saving is performed.

Dual Plan Scanpath, Local Context Memory and Central Context Repository form a complex memory hierarchy specially designed to optimize preemption overhead. The same memory scheme is also used for configuration management except configuration do not change during execution so it does not need to be saved and then no versioning control is required here. The programmable logic core use a dual configuration plane equivalent to the Dual Plane Scanpath used for context.

Each column has a Hardware Configuration Manager which is a simplified version of the CMU (without saving mechanism). A Local Configuration Memory is provided besside Local

Context Memory, the name LCM is used as in figure 3 to relate to both those memories. In the same way, the CCR can refer to Central Context/Configuration Repository.

In best case, preemption overhead can then be bound to one clock cycle.

A scenario of a typical preemption is presented here. In this scenario we consider the case where context and configuration of both task are already stored into the right LCM. Let's consider that a task T1 is preempted to run another task T2, scenario of task preemption is then as follow :

• T1 is running and the scheduler decide to preempt it to run T2 instead • T2's configuration and eventually context is shifted on the second configuration plane Fig. 6. Typical preemption scenario

• once the transfer is completed the two configurations planes are switched

• now T2 is running and T1's context can be shifted out to be saved

• T1's context is updated as soon as possible in the CCR This scenario is illustrated in figure 6. This is the case when both context and configuration of T2 are already stored into LCM. That means that, in order to have this favorable case, we need an anticipated scheduling to manage our Context/Configuration Memories Hierarchy as a smart cache.

V. CONFIGURATION, PREEMPTION AND OS INTERACTION

In previous sections an architectural view of our FGDRA has been exposed. In this section, we discuss about the impact of this architecture on OS services. We will here consider the three services most specifically related to the FGDRA.

First, the configuration management service. On the hardware side, each column provides a hardware configuration manager and an associated local memory. As stated earlier that mean that configurations have to be placed in advance in the local configuration memory. The associated service running on the hardware supervisor micro-processor will thus need to take that into account. That imply that this service must manage an intelligent cache to prefetch task configuration on the columns where it might most probably be placed. In order to do so, an anticipated scheduling must be performed.

Secondly, the preemption service. The same principle must be applicable here as those applied for configuration management. Except that contexts also have to be saved. The context management service must ensure that it never exist more than one valid context for each task in the entire FGDRA. Context must thus be transferred as soon as possible from local context memory to the centralized global memory of the hardware supervisor. This service will also have a big impact on the scheduling service as the ability to perform preemption with a very low overhead allow the use of more flexible scheduling algorithms.

And last the scheduling service and in particular the space management part of the scheduling. It takes advantage of the column topology and of the centralized communication scheme. As stated, fewer computing power will be required to manage a one dimensional space at run time. The problem is here similar to memory management in classical GPP based system. The reconfigurable resource could then be managed as a virtual infinite space containing an undetermined number of columns. The job is then to dynamically map the required set of columns (task) into the real space (the actual reconfigurable logic core of the FGDRA).

VI. PREEMPTION COST COMPARISON

This section present an analytic comparison of preemption efficiency in OLLAF and other solution from past works or literature. We will here consider six methods :

• XIL a solution based on the xilinx XAPP290 [START_REF] Xilinx | Two flows for partial reconfiguration: Module based or difference based," Xilinx, Application Note, 2004, application Note: Virtex, Virtex-E, Virtex-II, Virtex-II Pro Families XAPP[END_REF] using ICAP to transfer both context and configuration and using the readback bitstream for context extraction.

• Scan a solution using a simple scanpath for context transfer as described in both [START_REF] Koch | Efficient hardware checkpointing -concepts, overhead analysis, and implementation[END_REF] and [START_REF] Garcia | Hardware task context management for fine grained dynamically reconfigurable architecture[END_REF], and using ICAP interface for configuration.

• PCS8 is similar to Scan solution but using 8 parallel scanpath as described in [START_REF] Garcia | Hardware task context management for fine grained dynamically reconfigurable architecture[END_REF].

• DPScan use a dual plane scanpath similar to the one used in OLLAF for context and ICAP for configuration. This method is also studied in [START_REF] Koch | Efficient hardware checkpointing -concepts, overhead analysis, and implementation[END_REF], referred as a shadow Scan Chain.

• MM use once again ICAP for configuration and the memory mapped solution proposed in [START_REF] Koch | Efficient hardware checkpointing -concepts, overhead analysis, and implementation[END_REF].

• OLLAF this last solution being the use of separate, column distributed, dual plane scanpath for configuration and context as proposed in this article. In this study we consider two parameter. The preemption overhead H is the cost of a preemption for the system in terms of time. The efficiency of preemption process λ is then λ = 1-H P with P is the minimum period at which preemption occurs so in our case P is the clock tick of the operating system. In this study we use a typical clock tick of 10ms. In order to focus on the architectural view only all times will be expressed and estimated in number of clock cycle. Assuming a typical clock frequency of 100MHz the OS tick is 10 6 tclk. Task sizes will be expressed as n, the number of flipflop used. The time cost of a preemption take into account two context transfers and one configuration transfer.

Analytic expression of H for each case are estimated as follow :

• XIL

In [START_REF] Koch | Efficient hardware checkpointing -concepts, overhead analysis, and implementation[END_REF]

• PCS8 Using 8 parallel scanpath it requires 1 clock cycle for 8 flipflops.

H = 21n 32 + 2n 8 ≃ 0.9n (3)
• DPScan Using a double plane scanpath, the context transfers can be hidden, the cost of those transfer is then always 1 clock cycle.

H = 21n 32 + 1 ≃ 0.66n + 1 (4)
• MM Using 32 bits memory access, this case is similar to the PCS8 but using 32 parallel paths instead of 8.

H = 21n 32 + 2n 32 ≃ 0.69n (5)
• OLLAF In OLLAF, both context and configuration transfer are hidden so the total cost of the preemption is always 1 clock cycle whatever the size of the task.

H = 1 (6)
In order to make a concrete case comparison, we will consider two task T1 and T2. We consider a DES56 cryptographic IP that requires 862 flipflops, and a 16tap FIR filter that requires 563 flipflop. Both of those IPs can be found in www.opencores.org. To ease the computation we will consider two task using the average number of flipflop of the two considered IP. So for T1 and T2 we got n = 862+563 2 ≃ 713. Table I show the overhead H and the efficiency λ for each method presented.

Those results show that in this case, using our method leads to a preemption overhead around 500 times smaller than the bests others cases.

If we now consider that not only one task is preempted but the whole FGDRA, assuming a 1 Million LE's logic core, estimation of overhead and efficiency for each method are shown in table II. Those results show clearly the benefit of OLLAF platform over actual FPGA concerning preemption. Using actual methods, preemption overhead is linearly dependant on the size of the task. In OLLAF, this overhead do not depends on the size of the task and is always of only one clock cycle.

In OLLAF, both context and configuration transfers are hidden due to the use of a dual configuration plane. The latency L between the moment a preemption is asked and the moment the new task effectively begin to run can also being studied. This latency only depends on the size of the columns. That means that for a given platform, it will be a constant. In the worst case this latency will be far shorter than the OS tick period. OS tick period being in any case the shortest time in which the system can respond to an event, we can consider that this latency will not affect the system at all.

VII. CONCLUSION AND PERSPECTIVES

A global view of OLLAF, a FGDRA that enhance OS service support has been presented, and in more details its reconfigurable logic core. We claim that OS and platform must be closely linked to each others in order to perform as optimally as possible.

In this paper we presented in more details our context management scheme and its extention to configuration management. It has been shown that this scheme permit a far better preemption efficiency than other methods in use today.

Today, the reconfigurable logic core have been designed and is being tested by several simulations. The rest of the FGDRA is also in progress. The dedicated custom OS services are written as an extension of µC/OS-II, a well proven real time OS. We are also working on the distributed management of the whole heterogeneous system including, at least, one of our FGDRA and its dedicated real time kernel, and one GPP.

Fig. 3 .Fig. 4 .

 34 Fig. 3. Functional, task designer point of view of LE

Fig. 5 .

 5 Fig. 5. Context memories hierarchy


Nathanaël Fijalkow

Florian Horn
email: florian.horn@liafa.jussieu.fr

The surprising complexity of generalized reachability games

Games on graphs provide a natural and powerful model for reactive systems. In this paper, we consider generalized reachability objectives, defined as conjunctions of reachability objectives. We first prove that deciding the winner in such games is PSPACE-complete, although it is fixed-parameter tractable with the number of reachability objectives as parameter. Moreover, we consider the memory requirements for both players and give matching upper and lower bounds on the size of winning strategies. In order to allow more efficient algorithms, we consider subclasses of generalized reachability games. We show that bounding the size of the reachability sets gives two natural subclasses where deciding the winner can be done efficiently.

Introduction

Graphs games. Our purpose is to study reactive systems by abstracting them into graphs games: a state of the system is represented by a vertex in a finite directed graph, and a transition corresponds to an edge. If in a given state, the controller can choose the evolution of the system, then the corresponding vertex is controlled by the first player, Eve. Otherwise, the system evolves in an uncertain way: we consider the worst-case scenario where a second player, Adam, controls those states. To a run of the system corresponds a play on the game: we put a pebble in the initial vertex, then Eve and Adam move this pebble along the edges, constructing an infinite sequence. The specification of the system gives an objective Eve tries to ensure on this sequence. In order to synthesize a controller, we are interested in two questions: whether Eve wins in the game, and what resources are needed to construct a winning strategy (see [START_REF] Grädel | Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar[END_REF] for more details). System specifications. To specify properties of a system, we construct a set of infinite sequences representing the correct behaviors of the system. From an infinite sequence we extract finite information to decide whether the run it represents meet the specification. For instance, considering the set of vertices visited infinitely often allows to specify the classical ω-regular properties, e.g Büchi, parity, Streett, Rabin and Müller objectives. Other informations can be carried out, as for instance the set of vertices visited with positive frequency [START_REF] Mathieu Tracol | Recurrence and transience for probabilistic automata[END_REF], or the order in which the vertices are visited for specifying LTL objectives [START_REF] Kupferman | From Liveness to Promptness[END_REF][START_REF] Horn | Optimal Strategy Synthesis in Request-Response Games[END_REF][START_REF] Zimmermann | Optimal bounds in parametric LTL games[END_REF]. In this work, we observe the set of vertices visited at least once, which allows to specify reachability objectives, also called weak objectives [NSW02,SW74,Mos91,KVW00] Generalized reachability objectives. The (simple) reachability objective requires, given a subset of vertices F , that a vertex from F is reached. Reachability objectives only specifies that one property (represented by F ) is satisfied along the run. We allow more properties to be specified by using generalized reachability objectives, defined as conjunctions of k reachability objectives. In this context, a reachability objective is often referred as a color: a generalized reachability objective is then to see each of the k colors at least once.

Definitions

The games we consider are played on an arena A = (V, (V • , V 2 ), E), which consists of a finite graph (V, E) and a partition (V • , V 2 ) of the vertex set V : a vertex is controlled by Eve if it belongs to V • and by Adam if it belongs to V 2 . Vertices from V • are depicted by a circle, and vertices from V 2 by a square. We denote by n the number of vertices and m the number of edges. Playing consists in moving a pebble along the edges: the pebble is placed on the initial vertex v 0 , then the player who controls the vertex chooses an edge and sends the pebble along this edge to the next vertex. From this infinite interaction results a play π, which is an infinite sequence of vertices v 0 , v 1 , . . . where for all i, we have (v i , v i+1 ) ∈ E, i.e π is an infinite path in the graph. We denote by Π the set of all plays, and define objectives for a player by giving a set of winning plays Φ ⊆ Π. The games are zero-sum, which means that if Eve has the objective Φ, then Adam has the objective Π \ Φ (the objectives are opposite). Formally, a game is given by a couple G = (A, Φ) where A is an arena and Φ an objective.

A strategy for a player is a function that prescribes, given a finite history of the play, the next move. Formally, a strategy for Eve is a function σ : V * • V • → V such that for a finite history w ∈ V * and a current position v ∈ V • , the prescribed move is legal, i.e along an edge: (v, σ(w • v)) ∈ E. Strategies for Adam are defined similarly, and usually denoted by τ . Once a game G = (A, Φ), a starting vertex v 0 and strategies σ for Eve and τ for Adam are fixed, there is a unique play denoted by π(v 0 , σ, τ ), which is said to be winning for Eve if it belongs to Φ. The sentence "Eve wins from v 0 " means that she has a winning strategy from v 0 , that is a strategy σ such that for all strategy τ for Adam, the play π(v 0 , σ, τ ) is winning. The first natural problem we consider is to "solve the game", that is given a game G and a starting vertex v 0 , to decide whether Eve wins from v 0 . We denote by W E (G) the winning positions of Eve, that is the set of vertices from where Eve wins (also referred as winning set), and analogously W A (G) for Adam. We can prove that in generalized reachability games, we have W E (A, Φ) ∪ W A (A, Φ) = V : from any vertex, either of the two players has a winning strategy. We say that the games are determined.

The strategies as defined in their full generality above are infinite objects. Indeed, in this general setting, to pick the next-move, Eve considers the whole history of the play, whose size grows arbitrarily. A nicer setting, giving rise to finitely-representable objects, is to define strategies relying on memory structures. Formally, a memory structure M = (M, m 0 , µ) for an arena A consists of a set M of memory states, an initial memory state m 0 ∈ M , and an update function µ : M × E → M . A memory structure is similar in fashion to an automaton synchronized with the arena: it starts from m 0 and reads the sequence of edges produced by the arena. Whenever an edge is taken, the current state is updated using the update function µ. A strategy relying on a memory structure M, whenever it picks the next move, considers only the current vertex and the current memory state: it is thus given by a next-move function ν : V • ×M → V . Formally, given a memory structure M and a next-move function ν, we can define a strategy σ for Eve by σ(w

• v) = ν(v, µ * (w • v)).
(The update function can be extended to a function µ * : V + → M by defining µ * (v) = m 0 and µ * (w • u • v) = µ(µ * (w • u), (u, v)).) A strategy with memory structure M has finite memory if M is a finite set. It is memoryless, or positional if M is a singleton: in this case, the choice for the next move only depends on the current vertex. Note that a memoryless strategy can be described as a function σ : V • → V .

We can make the synchronized product explicit: an arena A and a memory structure M for A induce the expanded arena A×M = (V ×M,

(V • ×M, V 2 × M ), E × µ) where E × µ is defined by: ((v, m), (v ′ , m ′ )) ∈ E ′ if (v, v ′ ) ∈ E and µ(m, (v, v ′ )) = m ′ .
There is a natural one-to-one mapping between plays in A and in A × M, and also from memoryless strategies in A × M to strategies in A using M as memory structure. It follows that if a player has a memoryless winning strategy for the arena A × M, then he has a winning strategy using M as memory structure for the arena A. This key property will be used later on.

A reachability objective requires that a vertex from a given subset of vertices F is reached:

Reach(F ) = {v 0 , v 1 , v 2 . . . | ∃p ∈ N, v p ∈ F } ⊆ Π.
Games in the form G = (A, Reach(F )) are called reachability games. To determine whether Eve wins a reachability game, we compute the reachability set attractor.

We define the sequence (Attr i (F )) i≥0 :

Attr 0 (F ) = F Attr i+1 (F ) = Attr i (F ) ∪ {u ∈ V • | ∃(u, v) ∈ E, v ∈ Attr i (F )} ∪ {u ∈ V 2 | ∀(u, v) ∈ E, v ∈ Attr i (F )}
Then Attr(F ) is the limit of the non-decreasing sequence (Attr i (F )) i≥0 . We can prove that W E (A, Reach(F )) is exactly Attr(F ).

Generalized reachability objectives.

A generalized reachability objective requires that each of the given k subsets of vertices F 1 , . . . , F k is reached:

GenReach(F 1 , . . . , F k ) = {π | ∀i, ∃p i ∈ N, v p i ∈ F i }.
Associating to each reachability objective a color, we can reformulate the generalized reachability objective: it requires to see each of the k colors at least once, in any order. Games in the form G = (A, GenReach(F 1 , . . . , F k )) are called generalized reachability games. The special cases where in A, V 2 (respectively V • ) is empty are called one-player (respectively opponent-player) generalized reachability games.

Example 1. We consider the arena drawn in Figure 1. A generalized reachability game is defined by the objective GenReach({1, 2}, {3}). The central vertex is the initial one. Eve tries to visit one of the two thick vertices and the dashed vertex. -We first prove that deciding the winner in generalized reachability games is PSPACE-complete. Using the same ideas, we also show that the oneplayer restriction, where all vertices belong to Eve, is NP-complete, and that the opponent-player restriction, where all vertices belong to Adam, can be solved in polynomial time. On the positive side, it is fixed-parameter tractable (FPT) with the number k of colors as parameter. -We study the size of the winning strategies for both players: we prove matching upper and lower bounds, i.e in any arena, if Eve has a winning strategy, then she has a winning strategy that uses 2 k -1 memory states, and there is an arena where Eve wins but there are no winning strategies with less than 2 k -1 memory states, and similarly for Adam with the bound k ⌊k/2⌋ . -We then consider the subclasses where we restrict the number of vertices sharing the same color (in other words, the size of reachability sets). This reveals a trichotomy: if three vertices are allowed to share the same color, then deciding the winner is, as in the general case, PSPACE-complete. However, if each color appears only once, then the problem is polynomial. If each color appears only twice, then the problem is polynomial for one-player games, where Eve controls all vertices.

Outline. In section 3, we first study the complexity of solving generalized reachability games, for two-player and one-player games, and then give matching upper and lower bounds for the memory required. In section 4, we consider the subclasses of games where the size of reachability set is restricted, in order to find tractable subclasses.

The complexity of generalized reachability games

In this section we prove that the winner problem in generalized reachability games is PSPACE-complete. Our PSPACE-hardness result follows from a reduction from QBF (evaluation of a quantified boolean formula in conjunctive normal form). However, we show that solving generalized reachability games with few colors is easy, as it is fixed-parameter tractable using the number of colors as parameter.

We then study one-player restrictions. We prove that the one-player generalized reachability games are NP-complete. The other one-player restriction, opponent-player generalized reachability games, can be solved in polynomial time.

The last subsection investigates memory requirements for both players. We present matching upper and lower bounds: Eve needs 2 k -1 memory states and Adam k ⌊k/2⌋ , where k is the number of colors.

PSPACE-completeness of solving generalized reachability games

As a first step we define a reduction from QBF to the winner problem of generalized reachability games. Consider a quantified boolean formula

Q 1 x 1 Q 2 x 2 . . . Q n x n φ ,
where φ is a propositional formula in conjunctive normal form, i.e

φ = i≤k ℓ i,1 ∨ ℓ i,2 ∨ . . . ∨ ℓ i,j i
and ℓ i,j is either x i or ¬x i for some i ≤ n. We construct a generalized reachability game where Eve wins if and only if the formula is true. Intuitively, the two players will sequentially choose to assign values to variables, following the quantification order and starting from the outermost variable. Eve chooses existential variables and Adam chooses universal variables. Formally, the game is as follows:

-for each variable x i , there are two vertices, x i and x i ; -for each variable x i , there is a choice vertex v i which leads to x i and x i . The choice vertex belongs to Eve if x i is existentially quantified, and to Adam if x i is universally quantified; -for each variable x i with i < n, there are two edges from x i and x i to the next choice vertex v i+1 ; -there is a sink s, and two edges from x n and x n to s; -for each clause {ℓ i,1 , . . . , ℓ i,j i }, there is a reachability objective F i which contains the corresponding vertices; -the generalized reachability objective is given by GenReach(F 1 , . . . , F k ).

The initial vertex is v 1 . There is a natural bijection between assignments of the variables and plays in this game; and an assignment satisfies the formula φ if and only if the play satisfies the generalized reachability objective. The evaluation order of the variables being the same in the formula and in the game, we conclude that Eve has a winning strategy if and only if the formula is true.

Example 2. We consider the following quantified boolean formula ∀x ∃y ∀z (x ∨ ¬y) ∧ (¬y ∨ z) .

Figure 2 shows the game built by the reduction. The generalized reachability objective is Reach({x, y}) ∧ Reach({y, z}). Thick vertices represent the first reachability objective and dashed vertices the second one. Theorem 1 (Complexity of generalized reachability games). Solving generalized reachability games is PSPACE-complete.

Proof. The previous reduction implies the PSPACE-hardness.

Let us first make a simple observation: if Eve has a winning strategy, then she has a winning strategy that visits each reachability set within n • k steps. Indeed, if she can enforce to visit a subset of vertices, then she can enforce it within n steps.

Relying on this remark, we can simulate the game for up to n • k steps using an alternating Turing machine: whenever a vertex belongs to Eve, the corresponding state is disjunctive, and it is conjunctive if the vertex belongs to Adam. A path of length n • k is accepted if it is winning, i.e if it contains one vertex from each reachability set F i . This machine accepts if and only if Eve wins, and works in polynomial time. Since APTIME = PSPACE, the result follows.

Parameterized complexity

Solving generalized reachability games with few colors is easy:

Theorem 2 (Generalized reachability games with k colors). Solving generalized reachability games is fixed-parameter tractable (FPT) with the number of colors as parameter.

Roughly speaking, the only information needed during a play is the subset of reachability sets already visited. We build a memory structure that keeps track of this information. By constructing the product with this memory structure, we turn a generalized reachability game into a (classical) reachability game.

Proof. We consider G = (G, GenReach(F 1 , . . . , F k )) a generalized reachability game, and v 0 a starting vertex. The memory structure M is defined by (2 {1,...,k} , m 0 , µ), where

m 0 is {i | v 0 ∈ F i }, and µ(S, (v, v ′ )) = S ∪ {i | v ′ ∈ F i }. Let F = {(_, S) | S = {1, .
. . , k}}: a play for the generalized reachability game G from v 0 is winning if and only if it is winning for the reachability game G × M = (G × M, Reach(F )) from (v 0 , m 0 ). Since deciding the winner in a reachability game can be done in linear time using an attractor computation, solving a generalized reachability game can be done in time 2 k × O(n + m).

Solving one-player restrictions Theorem 3 (One-player restrictions). Solving one-player generalized reachability games is NP-complete. Solving opponent-player generalized reachability games is polynomial.

Proof. We first deal with one-player generalized reachability games, where Eve controls all vertices. In our previous reduction, consider the case where all variables in the original formula are quantified existentially. Then the problem corresponds to SAT (satisfiability of a boolean formula in conjunctive normal form), which is NP-complete. Resulting games are one-player games, i.e all vertices belong to Eve, hence solving one-player generalized reachability games is NPhard.

We describe a non-deterministic algorithm to solve these games in polynomial time. As noted before, if Eve wins, then she has a winning strategy that wins within n • k steps. The algorithm guesses a path of length n • k and checks whether it is winning. It follows that solving one-player generalized reachability games is NP-complete.

We now consider opponent-player generalized reachability games, given by the objective GenReach(F 1 , . . . , F k ). The winning set for Adam is V \ i Attr(F i ), which can be computed in quadratic time.

Memory requirements

We first present upper bounds:

Lemma 1 (Memory upper bounds). For all generalized reachability games

G = (G, GenReach(F 1 , . . . , F k )),
-if Eve wins, then she wins using a strategy with memory 2 k -1; -if Adam wins, then he wins using a strategy with memory k ⌊k/2⌋ .

As in the proof for FPT membership, we make use of the memory structure M = (2 {1,...,k} , m 0 , µ), where

m 0 is {i | v 0 ∈ F i }, and µ(S, (v, v ′ )) = S ∪ {i | v ′ ∈ F i }.
Setting F as {(_, S) | S = {1, . . . , k}}, a play for the generalized reachability game G from v 0 is winning if and only if it is winning for the reachability game G × M = (G × M, Reach(F )) from (v 0 , m 0 ).

Proof. We consider G = (G, GenReach(F 1 , . . . , F k )) a generalized reachability game, and v 0 a starting vertex. Since in the reachability game G × M, each player has memoryless winning strategies, each player has in G a winning strategy using M as memory structure.

The memory set of M has size 2 k . In order to get the correct bounds for each player, we rely on two observations.

-Eve does not need a specific memory state to remember that all colors have been reached, as in this case, she has already won. Thus, she can always win with 2 k -1 memory states. -If Adam wins in G × M from (v, S) and S ′ ⊆ S, then he wins from (v, S ′ ) using the same strategy. Consider v ∈ V a vertex in G, and the set of subsets S such that (v, S) belongs to Adam's winning set. Its maximal (with respect to inclusion) elements are incomparable, so there are at most k ⌊k/2⌋ , we denote them by S 1 (v), . . . , S p (v). The idea is that from v, there are only p different options Adam has to consider, namely S 1 (v), . . . , S p (v). Indeed, for any S such that (v, S) is winning for Adam, there exists an i such that S ⊆ S i (v), so Adam can forget S and assume the current position is (v, S i (v)). We define a memory structure on the memory set {1, . . . , k ⌊k/2⌋ }. We aim at constructing a strategy that will ensure that after a finite play π • v, the memory state is an i such that S i (v) contains the set of visited colors. If the initial vertex is v 0 , the initial memory state is an i 0 such that S i 0 (v 0 ) contains m 0 . We define the update function:

µ(i, (v, v ′ )) is a j such that S j (v ′ ) contains µ(S i (v), v ′ ) = S i (v) ∪ {i | v ′ ∈ F i }.
Let us turn to the next-move function. Consider (v, S) in Adam's winning set, then there exists a transition to some (v ′ , S ′ ) also in Adam's winning set. Applying this to (v, S i (v)) such that S ⊆ S i (v), we get a vertex v ′ , and define ν(v, i) to v ′ . Playing this strategy, the above invariant is satisfied, and thus ensures to stay forever in Adam's winning set, so it is winning. The memory set contains k ⌊k/2⌋ memory states.

Lemma 2 (Memory lower bounds for both players). For all k,

-there exists G = (G, GenReach(F 1 , . . . , F k )) a generalized reachability game, where Eve needs 2 k -1 memory states to win; -there exists G = (G, GenReach(F 1 , . . . , F k )) a generalized reachability game, where Adam needs k ⌊k/2⌋ memory states to win. Proof. We first describe a generalized reachability game where Eve needs 2 k -1 memory states to win. This example was proposed in [START_REF] Chatterjee | The Complexity of Request-response Games[END_REF] in a similar framework. The arena is shown in Figure 3, for k = 5. A vertex labelled by i belongs to F i , and a vertex labelled by i has all colors but i. A play starts from the heart h; first Adam chooses a petal i, then Eve chooses either to reach color i before going back to the heart (the play goes on), or to reach every colors but i and to stop the play. Eve wins with the following strategy: the first time Adam chooses the petal i, she goes back to the heart; the second time, she stops the play. This strategy uses 2 k memory states. She can save one memory state by dropping the memory state corresponding to the case where she saw each petal, as it is winning for her. However, we show that there is no winning strategy for Eve with less than 2 k -1 memory states. Let σ a strategy using the memory structure M with less than 2 k -1 memory states, and ν its next-move function.

For each memory state m, we consider

S m = {i | ν(v i , µ(m, (h, v i ))) = i},
the set of petals where Eve would stop the play if Adam chose them. As there are less than 2 k -1 memory states, there is a strict subset X of {1, . . . , k} which is not the stopping set of any memory state. Adam can win against σ by choosing, at each step, a petal in the symmetric difference of X and S m , where m is Eve's current memory under σ. (Indeed, if Adam plays forever in X, then Eve will never stop the play and only colors from X will be reached, otherwise, whenever Eve stops the play, the last memory state from the heart was an m such that X ⊂ S m , and the petal chosen is an i that belongs to S m \ X, hence that has never been reached.)

We now describe a generalized reachability game won by Adam, where he needs k ⌊k/2⌋ memory states to win. Let k = 2p + 1. A play consists in three steps: first Eve chooses p colors, then Adam chooses p colors, and third Eve chooses p colors. In order to win, Adam must visit exactly the same colors Eve visited (which requires k ⌊k/2⌋ memory states), otherwise at least p + 1 colors have been visited when Eve plays for the second time, and she can choose and visit the remaining colors that have not yet been visited.

Restrictions on the size of reachability sets

The above section shows two different directions which make generalized reachability games hard: the first is the complexity of solving generalized reachability games (PSPACE-complete), and the second is the memory required to construct winning strategies for both players (exponential in the number of colors).

In this section, we restrict the size of the reachability sets in order to find tractable subclasses of generalized reachability games.

Notice that our reduction from QBF only implies PSPACE-hardness when reachability sets have size at least three. Indeed, note that in the reduction, the size of a reachability set in the generalized reachability game corresponds to the size of the corresponding clause of the formula. Since the problem of evaluating a quantified boolean formula is polynomial if the formula has two variables per clause, our reduction does not imply the PSPACE-hardness of solving generalized reachability games with reachability sets of size one or two. This remark motivates our study of the subclasses of generalized reachability games where each color appears once, and then where each color appears twice.

Reachability sets of size one

The case where reachability sets are singletons is polynomial: Theorem 4 (Generalized reachability games where reachability sets have size 1). Solving generalized reachability games where reachability sets are singletons is in PTIME.

Proof. We denote by v i the only vertex in F i , for all i. In this case, the generalized reachability objective can be expressed by i≤k Reach(v i ). We will see that Eve wins if and only if the preorder defined by v v ′ if v ∈ Attr(v ′ ) is total. Intuitively, it means that a winning strategy prescribes: "reach v f (1) , then v f (2) , and so on", where f is a permutation over {1, . . . , k}.

We consider two cases:

-If the preorder is total over {v i | 1 ≤ i ≤ k}, then we show that W E , set of winning positions for Eve, is ∩ i Attr(v i ). Let v ∈ ∩ i Attr(v i ) and f a permutation over {1, . . . , k} such that for all 1 ≤ i ≤ k -1, we have

v f (i) ∈ Attr(v f (i+1)
), we construct a winning strategy from v that reaches v f (1) , then v f (2) , and so on. Note that this strategy only needs k memory states. Conversely, if v / ∈ ∩ i Attr(v i ), then Eve cannot win, as Adam can prevent her from reaching some reachability set.

-If the preorder is not total, then there exist v i and v j such that v i / ∈ Attr(v j ) and v j / ∈ Attr(v i ). In this case Adam wins from everywhere, following the strategy "if v i or v j has been reached, then avoid the other". Note that this strategy only needs 2 memory states.

Checking that the preorder is total can be done in polynomial time.

Note that as a corollary, we get memory upper bounds in this case: Eve needs at most k memory states and Adam at most 2. It is not difficult to see that these bounds are tight.

Reachability sets of size two

Let us now turn to the case where reachability sets have size two. We first extend the technique used for the previous case: it was stated that "Eve wins if and only if there is a total order on colored vertices". A similar approach works for one-player arenas, through a reduction to the satisfiability problem of boolean formulas where clauses have size two. (This latter problem is known to be decidable in polynomial time.) Theorem 5 (Generalized reachability one-player games where color appears twice). Solving generalized reachability one-player games where reachability sets have size two is in PTIME.

Proof. As in the previous subsection, we consider the preorder defined by v v ′ if v ∈ Attr(v ′ ). Note that in the case of one-player arenas, v ∈ Attr(v ′ ) reduces to "there is a path from v to v ′ ".

Let F i = {x i , y i } be the reachability sets, and v 0 be a starting vertex. We assume without loss of generality that there is a path from v 0 to every F i (that is, either to x i or y i ), otherwise Eve cannot win. (This property is easily checked in deterministic polynomial time.) A first statement is as follows: Eve wins from v 0 if and only if there exist v 1 , . . . , v k colored vertices such that 1. for all 0 ≤ i ≤ k -1, v i v i+1 and 2. each color appears in {v 1 , . . . , v k }.

We turn this condition into a boolean formula where clauses have size 2. We consider the 2 • k variables X i and Y i , that correspond to vertices x i and y i . We define the formula φ:

{(¬X ∨ ¬Y ) | if x y and y x} (a) ∧ i (X i ∨ Y i ) (b)
, where x, y ranges over colored vertices (that is, vertices from F i for some i).

We argue that Eve wins from v 0 if and only if φ is satisfiable. Assume Eve wins from v 0 : let v 1 , . . . , v k as in the previous statement, and set the corresponding variables to true and the others to false, we claim that the formula φ is satisfied. Indeed, condition 2. ensures that the clauses under-braced (b) are satisfied, and for the clauses under-braced (a), let x, y such that x y and y x, if x is one of the v i 's, then y cannot be, so ¬X ∨ ¬Y holds. Conversely, assume that φ is satisfiable. The clauses under-braced (a) ensures that the order is total over vertices set to true. The clauses under-braced (b) ensures that at least one vertex from each reachability set is set to true. Combining those two statements, we reach the condition stated above.

The latter allows to decide in polynomial time whether Eve wins from v 0 by checking the formula φ for satisfiability.

We do not know the exact complexity of generalized reachability games where reachability sets have size 2. In the remaining of this subsection, we discuss this question, focusing on memory requirements for both players.

The memory required for Eve is still exponential, as shown in Figure 4 for k = 4. Specifically, it shows a generalized reachability game where reachability sets have size 2 won by Eve, where she needs 2 ⌊k/2⌋+1 -1 bits of memory to win. The arena is divided into two parts: the left hand side is a flower with ⌊k/2⌋ petals, and the right hand side a one-player arena. The game starts at the heart of the flower. First, Eve asks for each petal a color. Once this task is completed, she can move to the right hand side to reach the remaining colors. Eve needs to remember the ⌊k/2⌋ choices made by Adam (one for each petal), in order to reverse them: if Adam chose the color 1, then the color 2 has not been reached, so Eve has to choose color 2. Remembering those choices and asking for each petal requires 2 ⌊k/2⌋+1 -1 memory states. (This is the size of the complete binary tree of depth ⌊k/2⌋.)

On the other hand, the exact memory required for Adam remains open. The figure 5, following an idea of Christof Loeding, shows a generalized reachability game where reachability sets have size 2 won by Adam, where he needs 4 memory states to win. The game starts from the left hand side vertex. First Eve chooses and visits three of the four colors (two colors in the first column, 1 and 2 or 3 and 4, and then one in the second column), and sends the pebble -1 memory states to win to the right hand side vertex, controlled by Adam. There, he has four options, each allowing all colors but one. Remembering the four possibilities requires four memory states, and leads to a win. However, with less memory states, one of the four option will never be played, and Eve wins. Quite surprisingly, we could not generalize this example to obtain a better lower bound than 4. We do not know whether this bound is tight (in any arena, if Adam wins, then he has a winning strategy with 4 memory states), which is plausible. Note that this would imply a coNP NP algorithm: guess a winning strategy for Adam with 4 memory states, and compose this strategy with the game, then solve the resulting one-player game. Open problems. We were not able to give the exact complexity of generalized reachability games where reachability sets have size 2. The memory approach,

showing that Adam has winning strategy of constant size, seems promising towards this question.

Fig. 1 .

 1 Fig. 1. An example of a generalized reachability game

Fig. 2 .

 2 Fig. 2. An example of the reduction from QBF to generalized reachability games.

Fig. 3 .

 3 Fig. 3. A generalized reachability game where Eve needs 2 k -1 memory states to win

Fig. 4 .

 4 Fig. 4. A generalized reachability game where Eve needs 2 ⌊k/2⌋+1-1 memory states to win

Fig. 5 .

 5 Fig. 5. A generalized reachability game where Adam needs 4 memory states to win


Sixth Biennial International Colloquium on the Chadic Languages

Henry Tourneux, in his 2007 article "L'inversion tonale en kotoko" [START_REF] Tourneux | L'inversion tonale en kotoko. Comparative and Descriptive Studies[END_REF]) drew our attention on a phenomenon concerning systematic tone variations contrasting a Low and High final tone in the tone patterns of two dialects of Kotoko. A similar phenomenon was observed in our study of Geji, a Chadic language spoken in Bauchi State, Nigeria. This paper aims at documenting this variation and accounting systematically for it with a set of simple phonological rules. Geji belongs to the South-Bauchi-West (SBW) branch of Western Chadic languages. The internal classification of SBW languages in (Table 2) below is adapted from [START_REF] Shimizu | The Southern Bauchi Group of Chadic Languages. A survey report[END_REF][START_REF] Lewis | Ethnologue: Languages of the World, Sixteenth edition[END_REF]. Geji is a little documented language spoken north of the Bauchi-Jos road, on the eastern side of the Zaranda mountain. The map below shows the geographic situation of Geji in relationship with neighbouring SBW languages, and Zaar, their better-known SBW cousin.

Geji, Zaar and other SBW languages

Apart from a mention in [START_REF] Shimizu | The Southern Bauchi Group of Chadic Languages. A survey report[END_REF] and Ethnologue [START_REF] Lewis | Ethnologue: Languages of the World, Sixteenth edition[END_REF]) as a dialect of Geji, Pelu is not otherwise documented. A quick lexical survey shows that Geji and Pelu are very close dialects, with practically no lexical and little morphological variations. As an illustration of the lexical stability, see (Table 2) below 'we finished' This means that the absence of rising melodies is not the result of a general phonological constraint, but may have to do with some lexical particularity of Geji. In order to explore this hypothesis, let us look at what obtains when tones are elicited in the context "it is a___", equivalent to the Hausa so-called stabilizer ___ ne/ce.

The stabilizer and floating High tones

In Geji and Pelu, the stabilizer has the form and structure structure ___kən. Like Hausa ne/ce, Geji /kən/ has a variable tone. In a first approach, it was thought to bear a Mid lexical tone. In Geji, this Mid tone is replaced by copying the last tone of the noun it follows. This is congruent with the fact that in Geji, the Mid tone is replaced by any other tone in case of tone spreading or copying. In Pelu, the Mid tone of kən it is replaced by a tone that is polar with the one it follows: M after H and H after -H (i.e. M and L). The difference between Pelu and Geji tone patterns would be explained as a different treatment in rising melodies: Pelu has the whole melody linking on the pre-pausal form, whereas Geji has a floating Hi tone which links with the 1 st syllable that follows and is dropped in pre-pausal position, producing a monotonal noun.

Floating High tones and the indeterminate quantifier

An alternative to lexical floating tones

In order to reconsider the question, let us use the rules for the surface realization of tone combinations that were established in [START_REF] Caron | Depressor Consonants in Geji[END_REF]: It is worth mentioning here that the combination L+L > M (e.g. bə ̀lì gwōn < bə ̀lì + gwòn), however unexpected, is quite regular in Geji. However, the new lexical LH tone pattern adopted to replace the former LL H does not produce the expected result with the kə̄n stabilizer. If, as stated above, the Geji stabilizer has a Mid tone that copies the last tone of the noun it follows, we would expect to have *də ̀nzí kə ́n instead of what obtains, i.e. : də ̀nzì kə ́n. This can be accounted for if we state that kən is a clitic with no lexical tone, and the OCP applies on the domain N=clitic, də ̀nzì=kə ́n. The LL prepausal form is accounted for, whatever the other rules, by the action of intonational dowdrift (Cf. Schneeberg 1974 for an equivalent phenomenon in Zaar).

L H M L M H L H M H H M L H M

Conclusion

This paper has offered a unified account of the tonal inversion observed between two dialects of Geji, a Chadic South-Bauchi language spoken west of Bauchi in Nigeria. In Geji proper, in prepausal nominal forms, the rising melodies that are documented in the Pelu dialect are avoided and replaced by monotonal patterns. These prepausal form are accounted for by the action of intonational downdrift. The variation of the LL / LH tone patterns in certain nouns, together with that of the indeterminate quantifier gwòn/ʤwòn and the stabilizer =kən are explained by the use of simple rules of tone spreading and copying, which interact with surface rules of tone combinations. This presents a further limitation to the role of Depressor Consonants in Geji, as they do not act as barrier to H tones, but account in a limited way, for the diachronic explanation of the birth of a 3-tone system from an initial 2-tone situation (Cf. [START_REF] Caron | Depressor Consonants in Geji[END_REF]. Once again, we can but notice the need for distinctive features among close neighbours as a source for the development of dialects.

List of abbreviations

22- 23

 23 September 2011, LLACAN, Villejuif, France TONAL INVERSION IN GEJI AND PELU B. CARON *

Table 1 . Internal Classification of SBW LANGUAGE CLUSTERS LANGUAGES D IALECTS Sub-group North Geji Geji

 1

		Bolu
		Pelu
		Geji
	Zaranda	Zaranda
		Zul
	Dir	Baram
		Diir
	Polci	Buli
		Langas (Luri †)
	Polci	Lundur
		Polci
	Sub-group South
		Zeem †, Dyarum (?)
	Chaari	Tule †
	Zeem	Chaari
	Lushi	Lushi †
		Bàraza
	Baraza
		Dùr
	Dass	Zumbul
	Dott	Wangdày
		Zòɗì
		Zàkshì
	Zakshi	Boto
		Zari
	Saya	Sigidi (Guus)
	Zaar	Zaar of Kal
		Zaar of Marti
		Zaar of Ɓogoro

Table 2 . Pelu and Geji Lexical Stability

 2

		Pelu	Geji
	wasp ant sp.	kábə ̀lkàn 1 kábə ̀lkàn ʃyá̰ ː ʃya̰ ̄ː ʃyá̰ ː ʃya̰ ̄ː
	dog	kāɗī	k āɗī
	cat	kúlē	kúlē
	horn	no̰ ̄ː	no̰ ̄ː
	tree sp. (wild custard apple) mbwāːkī	mbwāːkī
	mahogany	lə̄nkā	lə̄nkā

. Tone inversion in pre-pausal forms However

  , despite this stability, tonal inversion is often observed in pre-pausal forms, where monotonal nouns in Geji correspond to rising tone patterns (R or MH) in Pelu

Table 3 . Pre-pausal Tonal Inversion

 3

		Pelu		Geji
	head	ga̰ ̌ː	R	ga̰ ̄ː	M
	guinea-fowl	ʤǒːn	R	ʤo̰ ̄	M
	baboon	ɦṵ ̌ː	R	ɦwōːmī	MM
	testicle	ndīːsí	MH ndíːsí	HH
	scorpion dove	yēndə ́l kūlú	MH yéndə ́l MH kúlú	HH HH
	tongue beans	lə̄ká ɓāːlí	MH lə ́ká MH ɓáːlí	HH HH
	millet sp.	swāːɲí	MH swá̰ ːgí	HH
	porcupine	gūsní	MH gùsnì	LL
	dirt fish	də̄skə ́n kwēːsí	MH də̄skə̄n MH kwēːsī	MM MM
	tree sp. (Bombax costatum)	ɓīːkí	MH ɓīːkī	MM

The word bird (G. yáːɮì; P. yāːɬí) even shows complete tonal inversion (G. HL; P. MH). This corresponds to the impossibility, in Geji pre-pausal nouns, to have a rising tone pattern. It should be noted, however, that this pattern is commonly found in verbs: Mə̄ pākí wī.

PL.AOR finish ACC

Table 4 . Geji & Pelu stabilizer

 4 This solution accounts for the lexical data listed in (Table5) below:

	Geji Pelu
	bedbug flea warthog də ̀nzì ɓúlí swāːsī kə̄n kə ́n kə ̀n	kə̄n kə ́n kə ́n

However, with some monotonal L or M Geji nouns, the stabilizer, instead of copying the last tone of the pre-pausal form, appears with a H tone : 'finger-millet'; dàːzì kə ́n, 'it is fingermillet'. A first solution to account for this change in the tone of the stabilizer is to posit a floating H tone (e.g. dàːzì, LL H ), linking with the particle:

Table 5 . Geji nouns with floating tones

 5

	finger-millet red sorrel blood speech donkey bark wild yam lungs lizard land monitor friend lie mucus hornbill tree sp. (Grewia bicolor) horse thorn citrus tree sp. (Detarium S.) pepper mosquito	Pelu dàːzí ʤìɗá hùlán gə ̀ɓá ʒàːkí gùɮɮə ́n gùlkí hūːhúː ɓàlkə ́ŋ də ̀kə ́l yēlə ́n lālí yēɬə ́l būrtú ɦōllí kāpsí jīːlí lēːmó gə ̀ŋə ́l tāttāːséj ɦūlə̄ndí	Geji dàːzì H ʤìɗà H ɦùlàn H gə ̀ɓà H ʤàːkì H gùbɮə ̀nH gùlkì H hūːhūː H ɓālkə̄ŋ H də̄kə̄l H yēlə̄n H lālī H yēɬə̄l H būrtū H ɦōllī H kāpsī H īːlī H lēːmō H gə̄ngə̄l H MMH tāttāːʃī H LH LH LH LH LH LH LH MH LH LH MH MH MH MH MH MH MH MH MH MMH ɦūlə̄ndī H	LL H LL H LL H LL H LL H LL H LL H MM H MM H MM H MM H MM H MM H MM H MM H MM H MM H MM H MM H MM H MMM H

  However, this explanation runs into a problem with the indeterminate quantifier /gwon/, pl. : /ʤon/, 'some…, another / other…', as in bə ̀lì gwōn, 'some/another monkey'. Let us assume that the quantifier, for the same reasons as for stabilizer /kən/, has a Mid lexical tone. Floating H tones, as in e.g. dàːzì H , instead of linking with the quantifier gwōn, (e.g. dàːzì *gwón), link with the last syllable of the noun thereby producing the very rising melody which is not attested in pre-pausal form: dàːzì (LL H ) + gwōn > dàːzí gwōn, 'some finger-millet' :[START_REF] Odden | The Unnatural Tonology of Zina Kotoko. Tones & Tunes Vol 1: Typological Studies in Word and Sentence Prosody[END_REF][START_REF] Caron | Depressor Consonants in Geji[END_REF]). If we follow this hypothesis, gwōn has a Mid tone pattern, and its initial D consonant acts as a barrier (is "opaque") to H tones. However, the tones of gwōn in other contexts vary in a way that is difficult to explain if it has a Mid tone. Let us compare the behaviour of gwōn with that of kə̄n:The L tone on /gwon/ʤwon/ following kāɗī (MM) and wáːɬə̂n (HF) is a problem if we consider that the lexical tone of /gwōn/ is M, since we would expect the following surface realizations: kāɗī / wáːɬə̂n *gwōn.

	kāɗī 'dog'		kāɗī kə̄n	kāɗī gwòn
	kúlú 'dove' bə ̀lì 'monkey' də ̀nzì H 'warthog' wá:ɬə̂n 'rain season'	kúlú gwōn bə ̀lì gwōn də ̀nzí gwōn wá:ɬə ́n kə̄n wá:ɬə ́n gwòn kúlú kə ́n bə ̀lì kə ̀n də ̀nzì kə ́n
	L	H	M	L	H	M
			>
	dàː	zì	gwōn	dàː	zí	gwōn

Since the quantifier gwōn/ʤwōn begins with a voiced obstruent, we can explain this by saying that H tones cannot link with syllables with an initial depressor consonant (D), in accordance with what obtains in other Chadic languages with consonant-tone interaction

[START_REF] Wolff | Consonant-tone interference in Chadic and its implications for a theory of tonogenesis in Afroasiatic. Langues et cultures dans le bassin du Lac Tchad[END_REF]

Geji and Pelu (resp. G. and P.) both have 3-tones. High tone (H) is noted by an acute accent on the vowel (á), Low tone (L) with a grave accent (à), and Mid tone (M) with a macron (ā). Falling tone (F) is noted by a circumflex accent (â), and Rising tone (R) by a caron (ǎ).


Samuel Garcia
email: samuel.garcia@ensea.fr

Bertrand Granado
email: bertrand.granado@ensea.fr

Design of a Fine Grained Dynamically Reconfigurable Architecture for OS Support

In the context of large versatile platform for embedded real time system on chip, a fine grained dynamically reconfigurable architecture (at a first approach an FPGA) can be used as one possible computational resource. In order to manage this resource in that kind of context we need an OS kernel able to manage such a resource. Both the history of micro-processor based system and our previous work based on currently available FPGA devices led us to think that not only an OS kernel must be defined to handle an FGDRA but a FGDRA must also be designed to handle this OS kernel. This article relate our original work in this direction. OLLAF 1 , an original FGDRA core that we have designed and modelized using VHDL will be presented as well as a more general view of our approach of a FGDRA and its related OS kernel.

I. INTRODUCTION

This work takes place in the SMILE project. This project aims at providing a distributed middle layer to efficiently handle the complexity of a tomorrow's RSoC 2 . This system may contain several computing units of different type. It will embed at less one or more General Purpose Processor (GPP), but also dynamically reconfigurable architectures (DRA) at different granularities. Tomorrow's computing systems has to comply with lots of constraints. Those constraints may be time related, to meet real time requirements, but also power consumption constraints, as it is, and will be more and more, one of the primary concern of electronical devices.

FGDRA 3 are today the platform of choice when it comes to handle tasks in a highly computational constrained context. In more general terms FGDRA can achieves much better efficiency than GPP does, while offering the same versatility and, potentially, a very close flexibility. The counterpart is that it introduces a much greater complexity for application designers. This complexity could be lowered to an acceptable level in two ways. First by providing powerful CAD tool. Lots of research are thus led in the field of high level synthesis [START_REF] Coussy | High-level synthesis under i/o timing and memory constraints[END_REF]. The second way is to abstract the system complexity by providing a middle layer, e.g an operating system, that abstracts the lower level of the system [START_REF] Deng | A Reconfigurable RTOS with HW/SW Co-scheduling for SOPC[END_REF]. Moreover, an OS could manage new tasks at run time. This property is a feature of importance for 1 Operating system enabled Low LAtency Fgdra 2 Reconfigurable System on Chip 3 Fine Grained Dynamically Reconfigurable Architecture, FPGA being a case of FGDRA Fig. 1. Basic view of a RSoC in SMILE DRA. For all those reasons, a specialized operating system is required for FGDRA.

In our work we make a difference between a FGDRA, which is a general term, and a FPGA which, for us, relate to an actual silicon device sold under this designation.

The SMILE project follows a distributed approach of the system. Each computing unit of a RSoC (GPP, DSP, DRA, ...) has its own real time kernel. This topology allows to use a specific custom made real time kernel for each computing unit. This enable to take into account every specificities of each computing unit. A message passing communication scheme, based on MPI 4 , ensure a consistent operation of the whole system. In this frame of mind, we developed a dedicated real time kernel for a FGDRA.

Both the history of micro-processor based system and our previous work based on currently available FPGA devices led us to think that not only an OS kernel must be conceived to handle a FGDRA, but a FGDRA must also be designed to support efficiently this OS kernel. This article relate our original works in this direction. The FGDRA core that we have designed will be presented as well as a more general view of our approach of a FGDRA and its related OS kernel.

The reminder of this paper is organized as follows. Section 2 discusses related work in the field of OS for FGDRA. Section 3 explains an original FGDRA platform proposition called OLLAF what we have designed and modelized using VHDL. Section 4 discuss more precisely of the basic reconfigurable core in the point of view of a task designer and more precisely on the reconfiguration point of view. Section 5 explain how our architecture can affect different OS services. Finally, conclusion are drawn in section 6.

II. RELATED WORK

A. OS for FGDRA Several research have been led in the field of OS for FGDRA [START_REF] Simmler | Multitasking on FPGA Coprocessors[END_REF], [START_REF] Chen | Configuration-Sensitive Process Scheduling for FPGA-Based Computing Platforms[END_REF], [START_REF] Walder | Reconfigurable Hardware Operating Systems: From Design Concepts to Realizations[END_REF], [START_REF] Wigley | Introducing reconfigme: An operating system for reconfigurable computing[END_REF]. All those studies present an OS more or less customized to enable specific FGDRA related services. Example of such services are : partial reconfiguration management, hardware task preemption or hardware task migration. They are all designed on top of a platform composed of a commercial FPGA and a micro-processor. This microprocessor may be a softcore processor, an embedded hardwired core or even an external processor.

In the 90's, some works have also been published about the design of a specific architecture for dynamical reconfiguration. In [START_REF] Ling | Wasmii : a data driven computer on virtuel hardware[END_REF] authors discuss about the first multi-context reconfigurable device. This concept as been implemented by NEC on the Dynamically Reconfigurable Logic Engine (DRLE) [START_REF] Shibata | A virtual hardware system on a dynamically reconfigurable logic device[END_REF]. At the same period, the concept of DPGA was introduced, it was also proposed in [START_REF] Dehon | Dpga-coupled microprocessors : Commodity ics for the early 21st century[END_REF] to implement a DPGA in the same die as a classic microprocessor to form one of the first SoC including dynamically reconfigurable logic. In 1995, Xilinx even applied a patent on multi-context programmable device proposed as an XC4000E FPGA with multiple configuration planes [START_REF] Xilinx | Time multiplexed programmable logic device[END_REF].

More recently, in [START_REF] Nollet | Designing an Operating System for a Heterogeneous Reconfigurable SoC[END_REF], authors propose to add special material to a DRA to support OS services, they worked on top of a classic FPGA. Some works as in [START_REF] Zhao | Tas-mram based non-volatile fpga logic circuit[END_REF] focus on technological improvement of FGDRA like using a MRAM based extra configuration plane. Other focus more on hight level generic modelization of a DRA of undetermined granularity [START_REF] Kupriyanov | Modeling of interconnection networks in massively parallel processor architectures[END_REF].

The work presented in this paper try to take advantage of those previous work both about hardware reconfigurable platform and OS for FGDRA.

B. previous work

Our first work on OS for FGDRA was related to preemption of hardware task on FPGA [START_REF] Garcia | Hardware task context management for fine grained dynamically reconfigurable architecture[END_REF]. For that purpose we explored the use of a scanpath at the task level. In order to accelerate the context transfer we explore the possibility of using multiple parallels scanpaths. We also provided the Context Management Unit or CMU, which is a small IP capable to manage the whole process of saving and restoring tasks contexts.

In that study both the CMU and the scanpath were build to be implemented on top of any available commercial FPGA. This approach showed number of limitations. They could be summarized in this way: implementing this kind of OS related material on top of the existing DRA introduce unacceptable overhead on both the task and the OS service. Differently said, most of OS related material should be as much as possible hardwired into the platform's architecture.

III. OLLAF : GENERAL OVERVIEW

A. Specifications of a FGDRA with OS support

We have designed a FGDRA with OS support following those specifications. This FGDRA called OLLAF has been designed as a synthesizable VHDL model.

It should first address the problem of the configuration speed of a task. This is one of the primary concerns because if the system spend more time configuring itself than actually running tasks, then its efficiency will be poor. The configuration speed will thus have a big impact on the scheduling strategy.

In order to enable more choice on scheduling scheme, and to match some real time requirement, our FGDRA platform must also include preemption facilities. For the same reasons than configuration, the speed of context saving and restoring process will be one of our primary concerns. On this particular point, previous work we have discussed in section 2 will be adapted and reused.

Scheduling on a single GPP system is just a matter of time. The problem is to distribute the computation time between different tasks. In the case of a DRA the system must distribute both computation time and computation resources. Scheduling in such a system is then no more a one dimensional problem, but a three dimensional one. One dimension is the time and the two others are the surface of reconfigurable resources. Performing such a scheduling at run time with real time constraints is at this stage not conceivable. But the FGDRA should help getting close to that goal. The primary concern on this subject is to ensure an easy task relocation. For that, the reconfigurable logic core should be splited into several equivalent blocs. This will allow to move a task from a bloc to any another bloc or from a group of blocs to another group of blocs of the same size and the same form factor without any change on the configuration data. The size of those blocs would be a tradeoff between flexibility and scheduling efficiency.

Another aspect of an operating system is to provide inter task communication services. In our case we will distinguish two cases. First the case of a task running on top of our FGDRA and communicating with another task running on a different computing unit, for example a GPP. This case will not be covered here as this problem concern the whole heterogeneous platform, not only the particular FGDRA computing unit. The second case is when two, or more, tasks run on top of the same FGDRA communicate together. This communication channel should remain the same wherever the task is placed on the FGDRA reconfigurable core and whatever state those tasks are (running, pending, waiting, ...). That mean that the FGDRA platform must provide a rationalized communication medium including some sort of exchange memories.

The same arguments could also be applied to inputs/outputs. Here again two cases exist. First the case of I/O being a global resource of the whole platform. Secondly the case of special I/O directly bound to the FGDRA. In the center stand the reconfigurable logic core of the FGDRA. This core is organized in columns, each column can be reconfigured separately and offer the same set of services. That means that a task use an integer number of columns. This topology as been chosen for two reasons. First using a partial reconfiguration by column transform the scheduling problem into a two dimensional problem (time + 1D space) which will be easier to handle in real time situations. Secondly as every columns is the same and offer the same set of services, tasks can be moved from one column to another without any change on the configuration data.

In the figure, at the bottom of each column you can notice two hardware blocs called CMU and HCM. The CMU as said earlier is an IP able to manage automatically task's context saving and restoring. The HCM standing for Hardware Configuration Manager is pretty much the same but to handle configuration data also called bitstream. On each column a local configuration/context memory is added. This memory can be seen as a first level of cache memory to store contexts and configurations close to the column where it might most probably be required. The internal architecture of the core provides adequate materials to work with CMU and HCM. More about this will be discussed in the next section.

On the right of the figure stand a big bloc called "HW Sup + HW RTK + central memory". This bloc contain a classic microprocessor which serve as a hardware supervisor. It runs a custom real time kernel specially adapted to handle FGDRA related OS services and platform level communication services. Along with this hardware supervisor a central memory is provided for OS use only. Basically this memory will store configuration and eventual context of every task that may run on the FGDRA. This supervisor communicates with all columns using a dedicated control bus.

Finally, on top of the figure 2 you can see the application communication medium. This communication medium provides a communication port to each column. Those com-Fig. 3. Basic reconfigurable tile Fig. 4. Functional, task designer point of view of LE munications ports will be directly bound to the reconfigurable interconnection matrix of the core. If I/O had to be bound to the FGDRA they would be connected with this communication medium in the same way reconfigurable columns are.

IV. RECONFIGURABLE LOGIC CORE

FGDRA core could be considered with two points of view. The first one is the functional point of view, it consists on the information that a task designer may have to know in order to design the task's architecture. The second point of view is the configuration point of view, it consists on information about reconfiguration plane. As one of the main goals of the OS is to abstract configuration management, this point of view could be seen as the OS point of view.

A. conceiver point of view

The FGDRA core is composed of several basic tiles (figure 3). Each tile consist on a classic Logic Element and a Switch Box. The switch box is in fact an elementary part of the reconfiguration matrix. In other words the reconfiguration matrix is build by connecting adjacent tile's switch box. This allow to easily generate a reconfigurable core of any desired size.

Internal architecture of a LE in the functional point of view can be seen on figure 4. This architecture integrates elements that compose a classic Logic Element of FGDRA. The OS point of view don't impact the functional point of view and if we want to modify the functional architecture, it should not change our conclusion on OS point of view.

B. configuration point of view

In the configuration point of view only the configuration plane will be discussed.

Each configuration memory point is at first modelized as a flip flop. In order to perform reconfiguration they are chained to form a scanpath. As configuration speed have to be increased as much as possible our reconfigurable logic Fig. 5. Configuration point of view of LE core will use multiple parallel scanpath. As an example the 18 configuration memory points of one of our LE will be each part of a different scanpath (16 for the 4bit LUT and 2 configurable inverter). That mean 18 parallel scanpaths for each LE columns and then a reconfiguration time 18 times shorter than with one unique scanpath. Those scanpaths are not independent, they all share the same clock and control signals. For that reason in the remaining of this section it will be referred as a unique configuration scanpath, the path being now a word, not a bit.

When a task is preempted, the context of this task must be saved. During this process only the information stored in the LE's flipflops are required. For this reason LE's flipflops are connected to another totally independent scanpath. This scanpath use a different clock and control signals.

Both configuration and context scanpath use equivalent signals. Signals for the configuration scanpath use the CfS prefix and context scanpath ones use the CS prefix. For each scanpath there is basically three signal, one clock signal clk, a mode selection signal rs, and the chain signal named in at the input of a flip flop or a bloc and out at the output.

In order to even lower the configuration and context managing overhead, our reconfigurable logic core use a double memory plane. A configuration memory point is not one flipflop but two flipflop with some switching material. Architecture of this memory point can be seen on figure 7. Run and scan are then no more two working mode but two parallel plane which can be swapped as will. With this topology, configuration and context of a task can be shifted while the previous task is still running. The effective task switching overhead is then taken downto one clock cycle.

Let's consider that a task T1 is preempted to run another task T2, scenario of task preemption is then as follow :

• T1 is running and the scheduler decide to preempt it to run T2 instead • T2's configuration and eventually context is shifted on the second configuration plane

• once the transfer is completed the two configurations planes are swiched

• now T2 is running and T1's context can be shifted out to be saved This scenario is illustrated in figure 6.

The only constraint of this system is that scheduling decision have to be taken in advance in order to take advantage of the dual configuration plane.

In OLLAF, both context and configuration transfers are hidden due to the use of a dual configuration plane. The latency L between the moment a preemption is asked and the moment the new task effectively begin to run can also being studied. This latency only depends on the size of the columns. That means that for a given platform, it will be a constant. In the worst case this latency will be far shorter than the OS tick period. OS tick period being the shortest time in which the system can respond to an event, we can consider that this latency will not affect the system at all under normal operation. In the case of an interruption, would then be perceptible. It hasn'tbeen measured yet but we can say that this latency will be fully determined for a given platform. In an extreme case, a task that should respond immediately to a specific event should be run as a critical section so that it will be always active.

C. Results

During our past works on preemption for FGDRA, we used a fixed coefficient seventh order FIR as test application. We then want to compare the estimated time overhead of a task preemption using our new FGDRA with the one obtained using our old context management scheme and a Xilinx ICAP interface. In order to make the comparison possible we will consider a 128x1 tiles column, our FIR architecture using 128 LEs. Each tile use 100bits of configuration memory. To reconfigure a 128 tiles column we thus need 12800bits. The context of the task is composed by 128bits. To perform the preemption we need to save the context of the preempted task and then to restore the one of the new task we want to run. We thus have to transfer 256 context bits. The Xilinx ICAP interface have a throughput of 32bits per clock cycle while using CSB for context transfer a throughput of one bit per clock cycle is performed. Using our FGDRA both operation can be performed at the same time and the switching time cost is always of one clock cycle. Using those estimated data, the comparison between those two solution are shown in the table I.

V. CONFIGURATION, PREEMPTION AND OS INTERACTION

In previous section an architectural view of our FGDRA has been exposed. In this section, impacts this architecture will have on OS services will be discussed. We will here consider the three service most specifically related to the FGDRA. First, the configuration management service. On the hardware side, each column provides a hardware configuration manager and an associated local memory. As stated earlier that mean that configurations have to be placed in advance in the local configuration memory. The associated service running on the hardware supervisor micro-processor will thus need to take that into account. That imply that this service must manage some sort of intelligent cache to prefetch task configuration on the columns where it might most probably be placed. In order to do so, some sort of anticipated scheduling must be performed.

Secondly, the preemption service. The same principle must be applicable here as those applied for configuration management. Except that contexts also have to be saved. The context management service must ensure that it never exist more than one context for each task in the entire FGDRA. Context must thus be transferred as soon as possible from local context memory to the centralized global memory of the hardware supervisor. This service will also have a big impact on the scheduling service as the ability to perform preemption with a very low overhead allow the use of more flexible scheduling algorithms.

And last the scheduling service and in particular the space management part of the scheduling. It takes advantage of the column topology and of the centralized communication scheme. As stated, fewer computing power will be required to manage a one dimensional space at run time. The problem is here similar to memory management in classical GPP based system. The reconfigurable resource could then be managed as a virtual infinite space containing an undetermined number of columns. The job is then to dynamically map the required set of columns (task) into the real space (the actual reconfigurable logic core of the FGDRA).

VI. CONCLUSION AND PERSPECTIVES

A global view of OLLAF, an original FGDRA that enhance OS service support has been presented, and in more details its reconfigurable logic core. We claim that OS and platform must be closely linked to each others in order to perform as optimally as possible.

We showed that this architecture can enhance the preemption efficiency and ease task relocation. Thanks to that, both time and space scheduling complexity can be drastically reduced. The operating system should then be able to run those services efficiently at run time under real time constraints.

Today, the reconfigurable logic core have been modelized using VHDL and is being tested by several simulations. The rest of the FGDRA is also in progress. The dedicated custom OS service are being written as an extension of µC/OS-II, a well proven real time OS. We are also working on the distributed management of the whole heterogeneous system including, at least, one of our FGDRA and its dedicated real time kernel, and one GPP.

Fig. 2 .

 2 Fig. 2. Global view of the FGDRA

Fig. 6 .

 6 Fig. 6. Typical preemption scenario

TABLE I ESTIMATED

 I COMPARISON OF TASK PREEMPTION OVERHEAD USING OUR NEW FGDRA OR A XILINX ICAP INTERFACE AND OUR OLD CSB CONTEXT TRANSFER METHOD. (GIVEN IN CLOCK CYCLE)

	Fig. 7. Dual plane memory point

Message Passing Interface