J.-Y Mignolet

V Nollet
email: nollet@imec.be

T Marescaux
email: marescau@imec.be

P Avasare
email: avasare@imec.be

D Verkest

Centralized Run-Time Resource Management in a Network

Introduction

Future platforms will contain a mixture of heterogeneous processing elements (PEs) [START_REF] Tessier | Reconfigurable Computing for Digital Signal Processing: A Survey[END_REF], also denoted as tiles. These programmable tiles will be interconnected by a configurable on-chip communications fabric or a Network-on-Chip (NoC) [START_REF] Benini | Networks on Chips: A new SOC paradigm?[END_REF][START_REF] Dally | Route packets, not wires: on-chip interconnection networks[END_REF]. Dynamically managing the computation and communication resources of such a platform is a challenging task, especially when the platform contains a special PE type such as fine-grain reconfigurable hardware (RH) [START_REF] Tessier | Reconfigurable Computing for Digital Signal Processing: A Survey[END_REF]. Compared to traditional PEs, RH operates in a different way, exhibiting its own distinct set of properties.

This paper details two important components of our runtime resource management scheme: the NoC resource management heuristic and the run-time task migration. An indepth discussion of other components such as our injection rate control mechanism and our hierarchical configuration mechanism is provided in respectively [START_REF] Nollet | Operating System controlled Network-on-Chip[END_REF] and [START_REF] Nollet | Hierarchical run-time reconfiguration managed by an operating system for reconfigurable systems[END_REF]. The main contribution of this paper is the description of a NoC resource management heuristic that makes efficient use of reconfigurable hardware tiles and that is closely linked to a run-time task migration mechanism. In addition, our task migration mechanisms are tailored to a NoC environment. It is the first time to our knowledge that the issues of run-time task migration are addressed in a NoC context.

The rest of the paper is organized as follows. Section 2 describes our emulated NoC system. Section 3 details and evaluates our RH enhanced resource management heuristic. Section 4 details our NoC run-time task migration mechanisms. Section 5 presents the conclusions. Related work [START_REF] Dally | Route packets, not wires: on-chip interconnection networks[END_REF][START_REF] Jin | Classification and Comparison of QoS Specification Languages for Distributed Multimedia Applications[END_REF][START_REF] Wiseman | Paired Gang Scheduling[END_REF][START_REF] Kim | Dynamic Mapping in a Heterogeneous Environment with Tasks Having Priorities and Multiple Dealines[END_REF][START_REF] Hu | Energy-Aware Communication and Task Scheduling for Network-on-Chip Architectures under Real-Time Constraints[END_REF][START_REF] Russ | Dynamic Communication Mechanism Switching in Hector[END_REF][START_REF] Steketee | Implementation of Process Migration in Amoeba[END_REF][START_REF] Smith | Heterogeneous Process Migration: The Tui System[END_REF][START_REF] Pradeep | Distributed operating systems: concepts and design[END_REF] is discussed throughout the paper.

System Description

Our multiprocessor NoC is emulated by linking the StrongARM processor of a PDA (further denoted as master PE) to an FPGA containing the slave PEs (S) (Figure 1a). All PEs are interconnected by a 3x3 packet-switched bidirectional mesh NoC clocked at 30 MHz.

The central OS executes on top of the master PE and is responsible for assigning resources (both computation and communication) to the different tasks. The OS keeps track of the computation resources by maintaining a list of PE descriptors. The communication resources are maintained by means of an injection slot table that indicates when a task is allowed to inject messages onto a link of the NoC (Figure 1b). Every tile contains a destination lookup table (DLT) that enables a task to resolve the location of its communication peers. The NoC provides the OS with a set of tools to monitor the resources and to enforce its decisions [START_REF] Nollet | Operating System controlled Network-on-Chip[END_REF].

In our current NoC configuration, tiles 1 and 5 expose the fine-grain reconfigurable hardware (i.e. FPGA fabric). These tiles are suited for computational intensive tasks, but can only accommodate a single task. The mapping heuristic will have to find the best fitting task for every reconfig-urable hardware tile, since some tasks can be too big for a certain RH tile (i.e. cannot be placed on that tile), while other tasks cause internal fragmentation (i.e. waste RH area because the task size is smaller than the tile size).

Resource Management Heuristic

The resource management heuristic consists of a basic algorithm completed with reconfigurable add-ons. The basic heuristic contains ideas from multiple resource management algorithms [START_REF] Wiseman | Paired Gang Scheduling[END_REF][START_REF] Kim | Dynamic Mapping in a Heterogeneous Environment with Tasks Having Priorities and Multiple Dealines[END_REF][START_REF] Hu | Energy-Aware Communication and Task Scheduling for Network-on-Chip Architectures under Real-Time Constraints[END_REF]. Here, our contribution lies in compiling these ideas into a suitable run-time management heuristic. In addition, we created a set of RH add-ons that allow the basic heuristic to deal with the specific properties of RH. These add-ons aim to improve the performance of the heuristic and to create extra management opportunities in the presence of RH.

Basic Heuristic

In order to assign resources to an application containing multiple communicating tasks, the heuristic requires the application specification, the user requirements and the current resource usage of the platform as input. The application is specified by means of a task graph that contains the properties of the different tasks (e.g. support for different PE types) and the specification of the inter-task communication. The user requirements are specified by means of a simple in-house QoS specification language (similar to the ones specified by [START_REF] Jin | Classification and Comparison of QoS Specification Languages for Distributed Multimedia Applications[END_REF]) The different steps to come to a complete resource assignment of an application are as follows.

1. Calculating requested resource load. Based on the task load specification function f i (x, y, . . .) provided by the application designer and the user requirements (specifying x, y, . . . ), the heuristic calculates the real computation and communication task load. In case of a video decoding task, for example, the framerate, resolution and decoding quality requested by the user will affect both the computation and communication resource requirements of the task.

2. Calculate task execution variance. For every task T i in the application, determine its execution time variance on the different supported PE types and normalize that value by the number of evaluated PE types (V Ni ).

Tasks with a high V Ni are very sensitive to which processing element they are assigned to. In addition, tasks that can only be mapped on one specific PE should be mapped before all other tasks. This way, the heuristic avoids a mapping failure, that would occur if this specific PE would be occupied by another task.

3. Calculate task communication weight. For every task T i in the application, determine its communication importance C i (both incoming and outgoing) with respect to the total inter-task communication of the application. This allows the algorithm to order the tasks based on their communication requirements.

4. Sort tasks according to mapping importance. The mapping priority of a task T i is equal to

V Ni x C i .
Tasks are sorted by descending priority.

5. Sort PEs for most important unmapped task. This step contains two phases. First, the allocation priority of the PEs for a task T i is determined based on the weighted product of the current PE load and the already used communication resources to the neighboring PEs. The weights are determined by the computation and communication requirements of the unmapped task. This allows the algorithm to match tasks that combine a high need for processing power and a low need for communication resources with their counterparts. Secondly, in order to map heavily communicating tasks close together, the allocation priority is also multiplied with the hop-bandwidth product (i.e. the product of the amount of assigned communication injection slots between two tasks and the hopdistance between them) of the current task and its already placed communication peers. PEs that lack the required computation resources (phase 1) or that do not provide enough communication resources to the already placed tasks (phase 2) have their allocation priority set to infinity, indicating that the PE is not fit to accommodate the unmapped task.

Mapping the task to the best computing resource.

The most important unmapped task is assigned to the best fitting PE. Consequently, the platform resource usage is updated to reflect this assignment. Steps 5 and 6 are repeated until all tasks are mapped.

Occasionally this greedy heuristic is unable to find a suitable mapping for a certain task. This usually occurs when mapping a resource-hungry application on a heavily loaded platform. Backtracking is the classic solution for this issue: it changes one or more previous task assignments in order to solve the mapping problem of the current task.

The backtracking algorithm starts by undoing N (start by N equals one) previous task resource allocations. Then, the PEs are sorted, but instead of choosing the best PE for a certain task, the second best PE is selected. If this does not solve the assignment issue for the current task, backtracking is repeated with N+1. Backtracking stops when either the number of allowed backtracking steps is exhausted or when backtracking reached the first task assignment of the application. In that case, the algorithm can (a) use runtime task migration (Section 4) to relocate a task of another application in order to free some resources, (b) use hierarchical configuration (Section 3.2) or (c) restart the heuristic with reduced user requirements.

Reconfigurable Hardware Add-ons

Incorporating RH tiles requires some additions to the basic mapping heuristic in order to take reconfigurable hardware properties into account.

The first set of additions are applied after step 5 of the basic mapping heuristic (i.e. after sorting all suitable PEs). There are two distinct RH properties that are taken into account. First, the internal fragmentation of reconfigurable area is considered. In case both the first and second priority tile are RH tiles. The heuristic will re-evaluate their priority using a fragmentation ratio in order to minimize the area fragmentation. Intuitively it is easy to understand that if placing the task on the highest priority tile causes 80% area fragmentation while the second priority tile only causes 5% area fragmentation, it might be better to place the task on the latter. Secondly, the binary state (i.e. either 0% load or 100% load) and the computational performance of RH tiles are considered. Due to the attempt at load-sharing of the heuristic algorithm RH tiles are often selected as best mapping candidates. Obviously, it would not be wise to sacrifice a RH tile when a regular PE could do a similar job. Therefore, if the highest priority tile for a certain task is a RH tile, while the second priority tile is a regular PE, the heuristic will use a load ratio to re-evaluate their priority to avoid wasting RH computing power.

The second set of additions involves hierarchical configuration [START_REF] Nollet | Hierarchical run-time reconfiguration managed by an operating system for reconfigurable systems[END_REF], i.e. the use of softcore PEs instantiated on RH tiles. There are two situations where this technique can improve mapping performance. First, when the task binaries are not supported by the platform PEs, a suitable softcore can be instantiated on a RH tile. This means the heuristic first needs to determine where to instantiate the softcore This is done by going over all softcores that are (1) supported by the task, (2) that fit on the available (i.e. free) RH tiles and (3) provide the required computing power. After finding a suitable location, the softcore is instantiated. From that moment on, the regular heuristic algorithm applies. Secondly, this technique can be used as an alternative to backtracking. Consider the mapping example (Figure 2a), where task T B still needs to be assigned. Since T B has no RH support (tile 1) and all other tiles are occupied or unsupported, T B can only be assigned to tile 8. Although tile 8 can provide the required computing resources, it lacks the required communication resources to support the communication between T B and T C . Without hierarchical configuration, the heuristic has no other option but to reconsider the mapping of T A and T C (i.e. perform backtracking). In case T A and T C are only supported on respectively tile 0 and tile 2, the heuristic will even need to reallocate resources of other applications (e.g. moving tasks from tile 4 to tile 8) in order to free resources. However, by means of hierarchical configuration, T B can be mapped on a softcore instantiated on RH tile 1 (Figure 2b). Also from a hopbandwidth point of view (i.e. mapping quality), it is better to map T B on a softcore on RH tile 1 than on tile 8.

Heuristic Performance Evaluation

The performance of the heuristic was assessed by comparing it to an algorithm that explores the full solution space. The performance experiments consist of mapping a typical test application (Figure 3) on our 3x3 NoC containing four PE types.

In order to include the current load of the platform and the user requirements into the mapping decision process, three types of load have been defined: LIGHT, MEDIUM and HEAVY. In case of platform load, they indicate that no platform resource (both computation and communication) is used for more than respectively 25%, 50% and 75%. A random function determines the actual resource usage for every resource. If the random function returns 50% or more usage on a single-task tile (e.g. RH tile), then this tile is considered as used (i.e.100% usage). Otherwise, it is con- sidered as free. In case of user requirements, these loads indicate that no task of the application uses more than respectively 25%, 50% and 75% of a certain resource. Placing a task on a single-task tile will result in 100% usage. Table 1 illustrates the success rate of the heuristic (with respect to searching the full mapping solution space) for LIGHT and MEDIUM loaded platforms and for varying application load. The amount of backtracking steps allowed is indicated by the BT value. On the StrongARM SA-1110 PE (206 MHz), the heuristic requires on average 893 µs (std. dev. 77 µs) to reach a full mapping without backtracking. With backtracking (BT=3), the algorithm requires on average 1.13ms (std. dev. 358 µs) to come to a conclusion (i.e. success or failure). Exploring the entire solution space requires about 378 ms. The experiment shows that, although backtracking clearly improves the success rate, the heuristic does not always find a suitable solution. In the experiments leading to the results of Table 1, all tasks with RH support (i.e. T 3 , T 4 and T 5 ) could be placed on any of the two RH tiles. However, when T 4 and T 5 only fit on tile 5, while T 3 fits on both RH tiles, the mapping success rate drops from 53.67% to 44.73% in case of a MEDIUM loaded 3x3 NoC (application HEAVY, without backtracking). The mapping success drops even further down to 36.84% in the absence of the reconfigurable hardware add-ons concerned with area fragmentation and gain. This means the RH add-ons significantly improve the mapping performance in case of different RH tile sizes.

NoC 3x3 LIGHT

By looking at the hop-bandwidth product (i.e. the product of the number of assigned injection slots between two tasks and the hop-distance between them), it is possible to estimate the mapping quality. Indeed, heavily communicating tasks should be mapped close together in order to minimize communication interference [START_REF] Nollet | Operating System controlled Network-on-Chip[END_REF]. Table 2 shows that the heuristic algorithm performs well under various load conditions. The main reason for the very low minimum hopbandwidth product of application LIGHT is that all tasks with heavy communication can be placed on a single tile. However, the heuristic tries to spread the communication and computation load among the PEs. In contrast to the related work [START_REF] Wiseman | Paired Gang Scheduling[END_REF][START_REF] Hu | Energy-Aware Communication and Task Scheduling for Network-on-Chip Architectures under Real-Time Constraints[END_REF], our heuristic does not consider the co-scheduling issue nor the real-time constraints of individual tasks, because currently our slave PEs (e.g. RH tiles) can only accommodate a single task (i.e. no co-scheduling or real-time issue on these PEs).

NoC 3x3 MEDIUM -HopBandwidth

Run-Time Task Migration

Whenever the user requirements change (e.g. switching to another resolution in a video application) or in case of a mapping failure, the resource management heuristic can use run-time task migration to re-allocate resources. Run-time task migration can be defined as relocation of an executing task from the source tile to the destination tile. In order to overcome the architectural differences between heterogeneous PEs, tasks can only migrate at pre-defined execution points in the code (further denoted as migration points) [START_REF] Smith | Heterogeneous Process Migration: The Tui System[END_REF]. How to handle task state when migrating between a regular PE and a RH tile is detailed in [START_REF] Mignolet | Infrastructure for Design and Management of Relocatable Tasks in a Heterogeneous Reconfigurable System-on-Chip[END_REF]. Another major issue in run-time task migration is assuring communication consistency during the migration process. This issue originates from the fact that, after receiving a migration request, the amount of time and input messages a task requires to reach its migration point is unknown. This means that the message producer tasks (i.e. the communication peers) have to keep sending messages until the migrating task signals that a migration point is reached and that it stopped consum-ing messages. However, at that time there might some unprocessed messages buffered in the communication path between message producer tasks and the migrating task.

The run-time task migration topic has been studied extensively for multicomputer systems since the beginning of the 1980s. However, due to the very specific NoC properties (e.g. a very limited amount of communication memory), the existing mechanisms are not directly applicable.

The message consistency mechanism described by Russ et al. [START_REF] Russ | Dynamic Communication Mechanism Switching in Hector[END_REF] collects all unprocessed messages into a special input queue when a migration point is reached. After the actual migration, all communication peers are notified and their task lookup table is updated to reflect the new location of the migrated task. Communication consistency is preserved by emptying the special input message queue before receiving any messages produced after completion of the migration process. This mechanism is not well-suited for a NoC: due to the very limited amount of message buffer space it is impossible to store all incoming messages after a task reached its migration point. Adding more buffer space is expensive and the maximum amount of required storage is very application dependent.

The message consistency mechanism of the Amoeba OS [START_REF] Steketee | Implementation of Process Migration in Amoeba[END_REF] drops the unprocessed messages (instead of queuing them) during task migration. The message producer is responsible for resending the message. After migration, any task that sends a message to the old location of the migrated task will receive a not here reply. This response triggers a mechanism to update the producer's task lookup table. A drawback of this technique is the loss of migration transparency (i.e. messages need to be resent to a new destination). In addition, dropping and re-transmitting packets reduces network performance, increases power dissipation [START_REF] Dally | Route packets, not wires: on-chip interconnection networks[END_REF] and leads to out-of-order message delivery. Getting messages back in-order in a task-transparent way requires (costly) additional re-order functionality and buffer space.

NoC Task Migration Mechanisms

This section details two task migration mechanisms that ensure message consistency in a task-transparent way, assuming a very limited amount of message buffer space per tile. In addition, both mechanisms ensure in-order message delivery without requiring message re-order functionality.

The first mechanism, further denoted as general mechanism is illustrated by Figure 4. When the OS issues a migration request (1), the task running on the source tile may require more input data from the producer tasks before it can reach a migration point. Neither the OS, nor the producer tasks know how many input messages are still required. When the task on the source tile reaches a migration point, it signals this event to the OS (1 to 2). In turn, the OS instructs the producers to send one last tagged message and then to stop sending [START_REF] Benini | Networks on Chips: A new SOC paradigm?[END_REF]. The OS consequently sets up, initializes and starts the migrating task on the destination tile [START_REF] Dally | Route packets, not wires: on-chip interconnection networks[END_REF]. The next step is to forward all buffered and unprocessed messages to the new location of the migrated task. To this end, the OS initializes a so-called forward-DLT (containing the new destination for the messages) on the source tile and instructs it to orderly forward all incoming messages (4). The destination tile informs the OS whenever it receives a tagged message. Consequently, the OS updates the DLT of the respective message producer tile to reflect the new location of the migrated task before instructing the producer to resume sending messages [START_REF] Wiseman | Paired Gang Scheduling[END_REF]. When all tagged messages have been received, the migration process is finished and the OS can free the resources of origin tile [START_REF] Kim | Dynamic Mapping in a Heterogeneous Environment with Tasks Having Priorities and Multiple Dealines[END_REF].

The second migration mechanism, further denoted as pipeline mechanism, is based on the assumption that many algorithms are pipelined (e.g. video decompression pipeline) and that they contain stateless points. Meaning that at certain moments, new and independent information is put into the pipeline. For example, an MPEG decoding pipeline periodically decodes an I-frame. This I-frame does not depend, in any way, on previously processed information. Hence, an I-frame could be decoded by a newly instantiated MPEG decoding pipeline. This assumption allows a migration mechanism to move multiple pipelined tasks at once without being concerned about transferring task state. This is useful when new QoS requirements affect a set of tasks within the application.

In this mechanism, the OS instructs the pipeline input task (Figure 3) to continue feeding data into the pipeline until a stateless point is reached. Then, the pipeline input task should flush the pipeline by sending a tagged message through the pipeline or by informing the pipeline output task. As soon as the pipeline is flushed, the pipeline output task notifies the OS. In contrast to the general mechanism, there are no unprocessed or buffered messages in the path between pipeline input and pipeline output. So the OS can re-instantiate every task of the pipeline with its respective DLT in a different location. After updating the DLT of the pipeline input task, normal operation can be resumed and the OS can free the resources of the original pipeline.

Migration Mechanism Benchmarking

The migration mechanism performance can be assessed by some typical benchmark parameters [START_REF] Pradeep | Distributed operating systems: concepts and design[END_REF]. The reaction time (i.e. time between migration request and the task actually reaching the migration point) of the pipeline mechanism will depend on the time required to reach a stateless pipeline migration point and the time required to empty the pipeline. For the general mechanism, the reaction time for migrating a single task is dependent on the amount of migration points implemented within that task.

The freeze time (i.e. the time during which a task is suspended) depends on the time required to set up DLT's (t DLT ≈ 90µs), issue OS commands (t CMD ≈ 60µs), etc. Consider a pipeline containing T tasks, C inter-task communication channels and S pipeline input tasks. It can be shown that the freeze time of the general mechanism (not considering task state extraction and initialization) is higher than that of the pipeline mechanism. The difference is: If the required PE resources are available upfront, setting up the new pipeline could be performed during the reaction time. In that case the freeze time would be independent of the amount of migrating pipeline tasks.

Once a migrated task has started executing on its new tile, it should no longer depend in any way on its previous tile. This is denoted as residual dependencies. These so-called residual dependencies are undesirable because they waste both communication and computing resources. The pipeline mechanism has no residual dependencies. The residual dependencies of the general mechanism (Figure 4) are caused by acknowledging the arrival of tagged messages and updating the producer DLT(s) before instructing every producer to resume sending messages. The time required to forward the unprocessed messages heavily depends on the NoC conditions (e.g. congestion, etc.).

In short, the pipeline mechanism is useful when simultaneously moving a set of tasks (e.g. due to changed user requirements). Otherwise, when moving a single task in order to e.g. resolve a mapping issue, the general mechanism is more appropriate (due to the prolonged reaction time of the pipeline mechanism). Both mechanisms require the application designer to explicitly introduce migration points.

Conclusion

This paper details two components of our overall resource management scheme for NoCs containing reconfigurable hardware tiles: the run-time resource assignment heuristic and the task migration mechanisms. We show that although the basic heuristic produces good results, specific support for the reconfigurable hardware tiles improves its performance. In addition to showing that the classic task migration mechanisms are not suitable for an NoC environment, we detail two task migration mechanisms tailored for our NoC emulation platform (i.e. with limited communication memory and to a simple communication protocol).

Figure 1 .

 1 Figure 1. (a) Our NoC emulation platform. (b) Communication resource management.

Figure 2 .

 2 Figure 2. Hierarchical configuration example.

1 Figure 3 .

 13 Figure 3. Example application containing a multimedia pipeline (e.g. video decoding).

Figure 4 .

 4 Figure 4. General task migration mechanism.

∆

  freeze time = (T -S).tDLT + (T + C -S).tCMD

Table 1 . Mapping success for varying number of backtracking steps (BT).

 1

	Application	BT=0	BT=1	BT=2	BT=3
	LIGHT	100%	100%	100%	100%
	MEDIUM	100%	100%	100%	100%
	HEAVY	78.5%	88.0%	90.0%	94.5%
		NoC 3x3 MEDIUM
	LIGHT	100%	100%	100%	100%
	MEDIUM	97.0%	99.0%	99.5%	100%
	HEAVY	53.67% 61.00% 67.79% 71.75%

Table 2 . Hop-bandwidth mapping quality.

 2

	Application Heuristic Max Min Mean
	LIGHT	315	825	75	466
	MEDIUM	570	1530 420	936
	HEAVY	945	1890 720	1275

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

* This work is partly funded by the European Commission (IST-AMDREL project IST-2001-34379) by the Flemish Government (GBOU-RESUME project IWT-020174-RESUME) and by Xilinx Labs, Xilinx Inc. R&D group.


David R Bickel
email: dbickel@uottawa.ca

Confidence intervals, significance values, maximum likelihood estimates, etc. sharpened into Occam's razors

Keywords: algorithmic probability, confidence distribution, differential entropy, fiducial inference, Kolmogorov complexity, probability matching prior distribution

Confidence intervals, significance values, maximum likelihood estimates, etc. sharpened into Occam's razors

David R.

Occam's razor is the principle that simpler theoretical formulations are preferred to more complex ones when other things are equal [START_REF] Baker | Simplicity[END_REF]. The principle has been invoked to support a wide variety of statistical methods. First, Bayesian (e.g., [START_REF] Wasserman | Bayesian model selection and model averaging[END_REF][START_REF] Ando | Bayesian Model Selection and Statistical Modeling[END_REF], frequentist (e.g., [START_REF] Burnham | Model Selection and Multimodel Inference: A Practical Information-Theoretic Approach[END_REF][START_REF] Claeskens | Model Selection and Model Averaging[END_REF], and information-theoretic methods of model selection such as that of minimum message length [START_REF] Wallace | Statistical And Inductive Inference By Minimum Message Length[END_REF][START_REF] Dowe | MML, Hybrid Bayesian Network Graphical Models, Statistical Consistency, Invariance and Uniqueness[END_REF] have been interpreted as ways of choosing the parametric complexity of a model to optimize predictive accuracy, where parametric complexity increases with the number of free parameters. Second, simpler models are often used to enhance understanding even at the expense of predictive accuracy when a more accurate model would require so many parameters that interpretation would be difficult or impossible (Lindley, 2000, discussion by D. R. Cox). Third, the intuitive appeal of invariance and other probabilistic symmetries in statistics (e.g., [START_REF] Eaton | Group Invariance Applications in Statistics[END_REF][START_REF] Helland | Steps Towards a Unified Basis for Scientific Models and Methods[END_REF] may be attributed to a different type of simplicity, that of mathematical elegance.

Another type of simplicity is that of a hypothesized distribution. Should simpler distributions of data have higher prior probabilities or prior probability densities, other things equal? If so, what is the effect on frequentist inference, especially in the form of p values, confidence intervals, and maximum likelihood estimates? This paper addresses the second question.

Assuming entropy as a measure of the complexity of sampling distributions should influence prior distributions as [START_REF] Bickel | Computable priors sharpened into Occam's razors, working paper[END_REF] suggests, the impact on credible sets such as 95% credible intervals can be calculated from the posterior distribution. When confidence sets such as 95% confidence intervals are approximately credible sets according to some prior distribution, the confidence sets may be adjusted for entropy by replacing them with the credible sets generated from that prior distribution after it has been adjusted to account for entropy.

Prior distributions generating credible sets that match confidence sets in that way are called matching prior distributions. Why restrict frequentist inference to methods that have a Bayesian interpretation using a matching prior? With a "synchronic coherence" condition, automating decisions on the basis of confidence levels and p values leads to minimizing expected loss with respect to coherent fiducial distributions such as a class of confidence distributions [START_REF] Bickel | A prior-free framework of coherent inference and its derivation of simple shrinkage estimators[END_REF]. If those decisions also satisfy a "diachronic coherence" condition regarding self-consistency as data arrive in time, then the decisions minimize expected 1 loss with respect to a posterior distribution corresponding to a matching prior. A related reason to consider matching priors is that frequentist methods compatible with them have desirable conditional inference properties (Datta and Sweeting, 2005, §2).

The statistical background for the proposed procedure is explained in Section 2. The method for adjusting a prior distribution for simplicity and then applying that to the adjustment of frequentist procedures using a matching prior is offered in Section 3. Section 4 proposes alternative procedures, covering ways to adjust statistical inference such as maximum likelihood estimation for the simplicity of distributions without requiring a matching prior distribution.

2 Background concepts

Approximate confidence distributions and probability matching priors

Consider sets Θ and Γ of real numbers or vectors, a parameter of interest θ ∈ Θ, and a nuisance parameter γ ∈ Γ. The observed sample x is modeled as a realization of X, a random vector of distribution P θ,γ , i.e., X ∼ P θ,γ . An approximate confidence curve is a function (θ, x) → p (θ; x) such that, to some order of approximation ( . =) , P θ,γ (p (θ; X) < α) . = α (1) for all α ∈ ]0, 1[, following the concept of confidence curves used in [START_REF] Birnbaum | Confidence curves: An omnibus technique for estimation and testing statistical hypotheses[END_REF] and [START_REF] Blaker | Confidence curves and improved exact confidence intervals for discrete distributions[END_REF].

Thus, p (θ 0 ; x) is an observed p value for testing the null hypothesis that θ = θ 0 . It follows from equation

(1) that the random set C (1 -α; X) defined by the function

α, x → C (1 -α; x) = {θ ∈ Θ : p (θ; x) ≥ α} (2)
is an approximate (1 -α) 100% confidence set for θ in the sense that

P θ,γ (θ ∈ C (1 -α; X)) . = 1 -α (3) P (ϑ ∈ C (1 -α; x) ; x) = P (C (1 -α; x) ; x) . = 1 -α (4)
for all α ∈ ]0, 1[, where ϑ ∼ P (•; x). Together, equations ( 3) and ( 4) say the probability that the random parameter ϑ is in an observed confidence set C (1 -α; x) is approximately equal to the probability that an approximate confidence set C (1 -α; X) covers the true value θ. An approximate confidence distribution is a special case of what Bickel and Padilla (2014) call a "confidence distribution" that is a Kolmogorov probability distribution as opposed to merely an incomplete probability distribution. Such confidence distributions are in turn special cases of "basic fiducial distributions" [START_REF] Bickel | A prior-free framework of coherent inference and its derivation of simple shrinkage estimators[END_REF].

The order of approximation ( . =) may be formalized in various ways. For example, if θ is a scalar and if equation ( 3) is understood to mean p (θ; X) weakly converges to U (0, 1), then the approximate confidence distribution is isomorphic to the "asymptotic confidence distribution" of [START_REF] Singh | Combining information from independent sources through confidence distributions[END_REF]. The definition of the order of approximation is left open herein in order to make the following connection to a wide variety of probability matching prior distributions.

Let P π0 (•|X = x) denote the posterior distribution of θ according to applying Bayes's theorem to a prior density π 0 , a function of θ and γ. Then π 0 is called a probability matching prior distribution if

P π0 (•|X = x)
is an approximate confidence distribution. Classes of probability matching priors thus correspond to different definitions of the order of approximation ( . =) such as the definitions found in [START_REF] Datta | Probability matching priors[END_REF] and Ghosh (2011).

Extended evidence values

The measure of evidence proposed in [START_REF] Pereira | Evidence and credibility: Full Bayesian significance test for precise hypotheses[END_REF] is extended by generalizing its highest density regions to regions of the form

(π 0 , α, x) → C π0 (1 -α; x) = {θ ∈ Θ : q π0 (θ; x) ≥ β (α)} (5)
evidence value at a fixed θ 0 ∈ Θ, with respect to a prior π 0 , by

p π0 (θ 0 ; x) = 1 - inf α∈]0,1[:θ0∈C(1-α;x) P π0 (θ ∈ C π0 (1 -α; x) |X = x) = sup {α ∈ ]0, 1[ : θ 0 ∈ C π0 (1 -α; x)} . (6)
If π 0 is a probability matching prior density function and

C π0 (1 -α; x) = C (1 -α; x), then equation (2)
implies that in this case the extended evidence value is a p value:

p π0 (θ 0 ; x) = sup {α ∈ ]0, 1[ : θ 0 ∈ C (1 -α; x)} = sup {α ∈ ]0, 1[ : p (θ 0 ; x) ≥ α} = p (θ 0 ; x) . ( 7
)
3 Sharpened priors, sharpened p values, and sharpened confidence sets As in Section 2, X ∼ P θ,γ . Let P

θ,γ signify the probability distribution of a scalar component of the vector X, a single observable random variable, or, more generally, of a partially exchangeable or conditionally independent random element. For example, if the components of X are independent and distributed as P

(1) θ,γ conditional on (θ, γ), then P θ,γ , the distribution of X, is P

(1) θ,γ 's n-product P (n) θ,γ .
A prior density function π 0 is considered blunt if its specification does not reflect the simplicity of P

(1) θ,γ as it varies with θ and γ. A prior density function π that is sharpened with respect to π 0 is defined by

(θ, γ) → π (θ, γ) ∝ π 0 (θ, γ) e -H (θ,γ) , (8)
where H (θ, γ) may be the Shannon entropy of P

θ,γ if θ and γ are discrete. Otherwise, letting ξ denote a measure that dominates P θ,γ and letting f θ,γ = dP (1) θ,γ /dξ define the relevant probability density function,

H (θ, γ) = -f θ,γ (x) ln f θ,γ (x) dξ (x) ,
commonly known as differential entropy when ξ is the Lebesgue measure. [START_REF] Bickel | Computable priors sharpened into Occam's razors, working paper[END_REF] argued on the basis of Kolmogorov complexity for applying equation ( 8) with H (θ, γ) as the entropy rate of a stochastic process.

Equation ( 8) may be generalized by replacing (θ, γ) → e -H (θ,γ) with (θ, γ) → e -κ H (θ,γ) for some κ > 0 or with some other function that monotonically increases with the simplicity of P

(1) θ,γ . The function (θ, γ) → e -κ H (θ,γ) with κ = 1 is used as the default in the rest of this paper, without loss of generality.

In analogy with the extended evidence value of equation ( 6), the sharpened evidence value at θ with respect to π is

p π (θ; x) = sup {α ∈ ]0, 1[ : θ 0 ∈ C π (1 -α; x)} ,
where (π, α, x) → C π (1 -α; x) is the function defined by equation ( 5). Thus, C π (1 -α; x) is the highest-

q π (•; x) (100%) (1 -α) credible set in the sense that P π (θ ∈ C π (1 -α; x) |X = x) = 1 -α for all α ∈ ]0, 1[.
For example, if q π0 (θ; x) is the posterior probability density when π 0 is the prior, then q π (θ; x) is the posterior probability density when π is the prior. Now assuming that π 0 is a probability matching prior density function and that C π0 (1 -α; x) = C (1 -α; x), the prior density function π that is sharpened with respect to π 0 is a sharpened matching prior distribution, and P π (•|X = x) , the corresponding posterior distribution, is a sharpened confidence distribution, the simplicity-informed counterpart to P π0 (•|X = x). Since equation ( 7) indicates that in this case the extended evidence value is a p value, the corresponding p π (θ; x) may be considered a sharpened p value and C π (1 -α; x) a sharpened confidence set of level (100%) (1 -α).

Example 1. Let X denote a sample of n independent draws from P

(1) θ,γ = N (θ, γ), the normal distribution of unknown mean θ, the parameter of interest, and unknown variance γ. The maximum likelihood estimates of θ and γ are denoted by θ and γ. According to the t test, the two-sided p value for testing the null hypothesis

that θ = θ 0 is p (θ 0 ; x) = 2 min Φ θ0, γn-1/n,n-1 θ/ γ n-1 /n , 1 -Φ θ0, γn-1/n,n-1 θ/ γ n-1 /n , (9)
where γ ν = γn/ν, and Φ µ,σ 2 ,ν is the cumulative distribution function (CDF) of the Student t distribution with location parameter µ, scale parameter σ, and ν degrees of freedom. The corresponding

(100%) (1 -α) confidence interval is C (1 -α; x) = {θ 0 ∈ Θ : p (θ 0 ; x) ≥ α} = Φ θ, γn-1/n,n-1 α 2 , Φ θ, γn-1/n,n-1 1 - α 2 . ( 10
)
In order to sharpen p (θ 0 ; x) to take into account the simplicity of N (θ, γ) as θ and γ vary, a matching prior distribution resulting in a (100%) (1 -α) credible set equal to C (1 -α; x) is required. Box and Tiao (1992, §2.4.6) considered improper priors of probability density π

as the highest-density (100%) (1 -α) credible set, that is, C (1 -α; x) = C π (0) 0 (1 -α; x). Using N (θ, γ)'s
differential entropy, H (θ, γ) = ln γ 1/2 plus a constant (Michalowicz et al., 2013, p. 127), the corresponding sharpened matching prior density is

π (0) (θ, γ) ∝ e -H (θ,γ) π (0) 0 (θ, γ) ∝ γ -1/2 γ -(0+1)/2 = γ -(1 + 1)/2 ∝ π (1) 0 (θ, γ) , which is π (δ) 0 (θ, γ) with δ = 1. It follows that the sharpened confidence distribution is of CDF Φ θ, γn/n,n ,
that the sharpened p value is

p π (0) (θ 0 ; x) = 2 min Φ θ0, γn/n,n θ/ γ/n , 1 -Φ θ0, γn/n,n θ/ γ/n , (11)
and that the sharpened (100%) (1 -α) confidence set is

C π (0) (1 -α; x) = θ 0 ∈ Θ : p π (0) (θ 0 ; x) ≥ α = Φ θ, γn/n,n α 2 , Φ θ, γn/n,n 1 - α 2 . ( 12
)
Figures 1 and2 indicate that while the sharpened confidence distributions and sharpened confidence intervals differ markedly from their blunt counterparts for n = 2 observations, they become closer by n = 4 observations but still with substantial differences.

The requirement of n ≥ 2 imposed by equations ( 9) and (10) prevents equations ( 11) and ( 12) from degenerating due to the fact that γ n = γ = 0 when n = 1. That is a safeguard that the frequentist aspect of the proposed method puts in place, a safeguard missing in this case from a purely Bayesian approach to 4 Sharpened statistical inference with prior likelihood instead of prior probability

Sharpened likelihood function

Equation ( 8) may be interpreted in terms of Bayes's theorem as updating the prior density function π 0 to a posterior density π according to a pre-x observation that induces the likelihood function θ,γ) , defined up to multiplication by a positive constant. Since that observation is conditionally independent of the sample X, L qualifies as a prior likelihood function [START_REF] Bickel | Computable priors sharpened into Occam's razors, working paper[END_REF].

(θ, γ) → L (θ, γ) = e -H (
That interpretation suggests dispensing with π 0 , replacing π with methods of inference based on likelihood functions without prior distributions. Those procedures are sharpened to account for simplicity by replacing each blunt likelihood function, (θ, γ) → f θ,γ (x), with the sharpened likelihood function, (θ, γ) → L (θ, γ) f θ,γ (x). Some special cases follow. 4.2 Sharpened likelihood asymptotics [START_REF] Schweder | Confidence and likelihood[END_REF] suggested accounting for pre-sample information by multiplying a likelihood function on which a confidence distribution is based by a prior likelihood function that encodes more subjective considerations. Likewise, first-order and higher-order asymptotic methods of deriving confidence sets and p values from the likelihood function (e.g., [START_REF] Severini | Likelihood Methods in Statistics[END_REF][START_REF] Brazzale | Applied Asymptotics: Case Studies in Small-sample Statistics[END_REF][START_REF] Butler | Saddlepoint Approximations with Applications, 1st Edition[END_REF] may take simplicity into account by using the sharpened likelihood function instead of the blunt likelihood function in quantities such as the score function, the Wald statistic, and Fisher information.

Example 2. For inference about θ as the normal mean in Example 1, a pseudo-likelihood function may be used to eliminate the nuisance parameter γ, the variance. For example, the profile likelihood function is

θ → L 0 (θ; x) = sup γ>0 f θ,γ (x) ,
and the likelihood ratio test (LRT) of the hypothesis that θ = θ 0 yields a p value equal to the probability that a χ 2 variate with 1 degree of freedom is greater than the observed LRT statistic, -2 ln L 0 (θ 0 ; x) /L 0 θ; x .

The p value based on the sharpened likelihood replaces the profile likelihood function with and replaces the LRT statistic with -2 ln L (θ 0 ; x) /L θ; x . While sharpening the likelihood function has a notable effect on inference (Figure 3), it is less pronounced than that under the matching prior approach (Figure 2).

θ → L (θ; x) = sup γ>0 e -H (θ,γ) f θ,γ (x) ∝ sup γ>0 γ -1/2 f θ,γ (x)

Sharpened estimation, model selection, and model averaging

Certain methods of model selection and model averaging, including the Bayesian information criterion (BIC) (Carlin and Louis, 2009, p. 53), the Akaike information criterion (AIC) [START_REF] Burnham | Model Selection and Multimodel Inference: A Practical Information-Theoretic Approach[END_REF], and the minimum description length (MDL) principle [START_REF] Rissanen | Information and Complexity in Statistical Modeling[END_REF][START_REF] Grünwald | The Minimum Description Length Principle[END_REF], are based on maximizing a product of the likelihood function and other factors, especially those reflecting the parametric complexity of each model, over the free parameters. (Methods assessing the evidence for a composite hypothesis may [START_REF] Bickel | Minimax-optimal strength of statistical evidence for a composite alternative hypothesis[END_REF] or may not [START_REF] Zhang | A likelihood paradigm for clinical trials (with discussion)[END_REF] e -H (θ,γ) f θ,γ (x) .

Alternatively, if θ → L 0 (θ; x) is a pseudo-likelihood function such as a marginal, conditional, estimated, or integrated likelihood function that is free of γ, then maximum sharpened pseudo-likelihood estimation results in the estimate arg sup θ∈Θ L (θ; x) , where θ → L (θ; x) is the sharpened pseudo-likelihood function, the same transform of (θ, γ) → e -H (θ,γ) f θ,γ (x)

that L 0 (θ; x) is of (θ, γ) → f θ,γ (x). Example 2 illustrates a special case of θ → L (θ; x).

  γ) ∝ γ -(δ+1)/2 for δ ≥ 0 and their posterior CDFs Φ θ, γ n+δ-1 /n,n+δ-1 . The δ = 0 case, π (0) 0 , is a probability matching prior since the resulting posterior distribution of θ, also a confidence distribution of θ, has CDF Φ θ, γn-1/n,n-1 , leading to C (1 -α; x)

Figure 1 :

 1 Figure 1: Probability density function of the normal mean for the blunt confidence distribution (gray) and the sharpened confidence distribution (black). The samples are x = (0, 1) on the left and x = (-1, 0, 1, 2) on the right.

Figure 2 :

 2 Figure 2: Observed p values for testing whether the normal mean is θ 0 for the blunt p value function (gray) and the sharpened p value function (black). Intersections with the horizontal line indicate the 95% confidence intervals. The samples are x = (0, 1) on the left and x = (-1, 0, 1, 2) on the right.

Figure 3 :

 3 Figure 3: Profile-likelihood p values for testing whether the normal mean is θ 0 based on the blunt likelihood function (gray) and on the sharpened likelihood function (black). Intersections with the horizontal line indicate the 95% confidence intervals. The samples are x = (0, 1) on the left and x = (-1, 0, 1, 2) on the right.

  include other factors in the product.) Such methods of model selection, model averaging, and evidence measurement may incorporate information about the simplicity of distributions by multiplying the product by e -H (θ,γ) before the maximization step. Example 3. Many methods of model selection, including BIC, AIC, and MDL, reduce to maximum likelihood estimation (MLE) when each model consists of a single distribution. MLE, however, fails to incorporate the simplicity of each distribution. By contrast, maximum sharpened likelihood estimation results in the es-timates arg sup θ∈Θ,γ∈Γ L (θ, γ) f θ,γ (x) = arg sup θ∈Θ,γ∈Γ

Acknowledgments

This research was partially supported by the Natural Sciences and Engineering Research Council of Canada (RGPIN/356018-2009) and by the Faculty of Medicine of the University of Ottawa.


Austin Hung
email: ahung@uwaterloo.cawdbishop@uwaterloo.caakennings@uwaterloo.ca

William Bishop

Andrew Kennings

Symmetric Multiprocessing on Programmable Chips Made Easy *

Vendor-provided softcore processors often support advanced features such as caching that work well in uniprocessor or uncoupled multiprocessor architectures. However, it is a challenge to implement Symmetric Multiprocessor on a Programmable Chip (SMPoPC) systems using such processors. This paper presents an implementation of a tightly-coupled, cache-coherent symmetric multiprocessing architecture using a vendor-provided softcore processor. Experimental results show that this implementation can be achieved without invasive changes to the vendor-provided softcore processor and without degradation of the performance of the memory system.

Introduction

Advances in Field-Programmable Gate Array (FPGA) technologies have led to programmable devices with greater density, speed and functionality. It is possible to implement a highly complex System-on-Programmable-Chip (SoPC) using on-chip FPGA resources (e.g., DSP blocks, PLLs, RAM blocks, etc.) and vendor-provided intellectual property (IP) cores. Furthermore, it is possible to build MPoPC systems, where the number of softcore processors (e.g., Altera Nios [START_REF]Nios 3.0 CPU. Data Sheet DS-NIOSCPU-2.1[END_REF] or Xilinx MicroBlaze [START_REF]MicroBlaze RISC 32-Bit Soft Processor. Product Brief[END_REF]) that can be used in a MPoPC system is only limited by device resources. Previous research [START_REF] Wang | Parallel Direct Solution of Linear Equations on FPGA-Based Machines[END_REF][START_REF] Hoare | An 88-Way Multiprocessor within an FPGA with Customizable Instructions[END_REF][START_REF] Collin | SoCrates -A Multiprocessor SoC in 40 days[END_REF] investigated application-specific MPoPC systems that did not require shared memory resources. This paper focuses on general-purpose MPoPC systems that utilize cache-coherent, symmetric multiprocessing.

We describe the design and use of general-purpose MPoPC systems based on vendor-provided IP. The systems use the familiar architecture of a shared-memory Symmetric Multiprocessing (SMP) system. The design goals are the following: (i) implementation with minimal user effort, (ii) no invasive alterations to vendor-provided IP, (iii) little if any performance penalties, and (iv) support for advanced features, namely caching.

Symmetric Multiprocessing on a Programmable Chip (SMPoPC) systems are suitable for a wide variety of embedded applications. The SMPoPC architecture offers several potential benefits including the following:

1. Enhanced embedded system performance: Processor cores may be added if device resources permit.

2. Simplified development: Time and effort can be spent on application development rather than on hardware specialization.

3. Performance improvements for computations: Many parallel algorithms exist for SMP architectures.

Our systems use 32-bit Altera Nios processors connected by an Altera Avalon Bus. This vendor-provided IP is supported by a suite of software development tools, optimized for the latest Altera FPGAs, and popular. A primary goal was to leverage the advanced features offered by softcore processors when implemented in leading-edge FPGAs. To this end, the Nios processor utilizes on-chip memory to serve as a cache to improve system performance. Unfortunately, the use of individual processor caches can introduce cache coherency problems -the Nios processor was not designed for use in tightly-coupled SMP architectures. This issue is addressed with a hybrid hardware/software solution that avoids invasive alterations to the Nios processor or the Avalon Bus. Thus, the solution serves as an "add-on" to existing Nios systems to facilitate cache coherency.

This paper is organized as follows. Section 2 provides an overview of SMP and cache coherency. Relevant details of the vendor-provided IP are provided in Section 3. A design for a cache-coherent SMPoPC system is described in Section 4. Section 5 describes the experimental results obtained using several cache-coherent SMPoPC systems. Conclusions and future work are presented in Section 6.

Symmetric Multiprocessing

SMP systems are a subset of multiple instruction, multiple data stream parallel computer architectures [START_REF] Flynn | Very High-Speed Computing Systems[END_REF]. Each processing element independently executes instructions on its own stream of data. SMP systems can function equally well as a single-user machine focusing on a single task with high efficiency, or as a multiprogrammed machine running multiple tasks [START_REF] Hennessy | Computer Architecture: A Quantitative Approach[END_REF]. SMP systems share memory resources using a shared bus as illustrated in Figure 1.

System Bus

Main memory I/O system

Processor 1 Cache

Processor 2 Cache

Processor N Cache

Figure 1. Typical SMP system architecture

The symmetry aspect is three-fold: (i) all processors are functionally identical and the hierarchy is flat with no master-slave or interprocessor communication relationships; (ii) all processors share the same address space; (iii) all processors share access to the same I/O subsystems with interrupts available to all processors. This symmetry helps to eliminate and reduce potential bottlenecks in critical subsystems and leads to software standardization in which system developers can produce systems with different numbers of processors that can execute the same binaries [11].

Processor Identification

SMP systems require a means to uniquely identify processors to permit selection of a bootstrap processor (BSP) for global initialization upon startup and to allow software (e.g., an operating system) to assign processes and threads to processors. Unique identification of processors is one issue addressed by our system.

Cache Coherency

Processor performance can be improved via one or more levels of cache located between the processor and main memory. A processor accessing cached data does not require any memory bus transactions, thereby reducing bus contention. Caches are designed to follow either a writethrough or write-back policy. A write-through policy specifies that a value to be stored is written into the cache and the next level of the memory hierarchy. A write-back policy only writes to the next level of the memory hierarchy when the written cache line is replaced.

The presence of multiple, independent processor caches in a SMPoPC system leads to a cache coherency problem. Put simply, the view of the shared memory by different processors may be different. Consider a system utilizing two processors (P 1 and P 2 ) with local write-through caches (C 1 and C 2 ). When processor P 1 reads memory location X, the value is stored in cache C 1 . If processor P 2 subsequently writes a different value to memory location X, cache C 1 will contain a stale value in memory location X. If processor P 1 subsequently reads location X, it will retrieve old data from the local cache. [START_REF] Hennessy | Computer Architecture: A Quantitative Approach[END_REF] Two classes of protocols are often used to enforce cache coherency: snooping and directory. Snooping protocols involve having processor caches monitor (snoop) the memory bus for writes by other processors. If the local cache contains the address being written, the cache either invalidates the cache line or updates its contents. Directory protocols use a central directory to track the status of blocks of shared memory. When a processor writes to a shared memory block, it secures exclusive-write access to the block. Messages are passed to ensure that no stale memory blocks exist in the local processor caches. Neither of these two methods are appropriate for the SMPoPC system described in this paper as shown in Section 3 and Section 4.

The Nios Processor and Avalon Bus

The SMPoPC system described in this paper is based on one or more Nios processors connected to an Avalon Bus. The Nios processor and the Avalon Bus are vendor-provided IP cores designed for rapid SoPC development.

Nios Embedded Softcore Processor

The Nios embedded softcore processor is designed specifically for SoPC design. It features a 5-stage pipeline architecture and comes in both 16-and 32-bit variants. The memory system uses a modified Harvard memory architecture with separate bus masters for data and instruction memory. Memory-mapped I/O is used to access memory and peripherals attached to an Avalon bus. The global address space is configurable at system generation time. The processor can implement up to four custom user instructions. Custom logic can be placed within the arithmetic logic unit to implement single or multiple cycle instructions. Further details are found in [START_REF]Nios 3.0 CPU. Data Sheet DS-NIOSCPU-2.1[END_REF].

The following Nios features are particularly relevant for this paper: (i) takes advantage of on-chip memory for caching, (ii) provides control registers for invalidating particular cache lines, (iii) supports of up to 64 vectored exceptions including interrupts generated by external hardware, and (iv) interfaces to an Avalon Bus. It is also important to note that the Nios was never intended for use in a cached SMP architecture.

Avalon Bus

The Avalon Bus is not a "traditional" bus, but rather a "switch fabric" used to interconnect processors and other devices in a Nios embedded processor system [START_REF]Avalon Bus Specification Reference Manual[END_REF]. The bus provides point-to-point connections and supports multiple, simultaneous bus masters [START_REF] Corp | Simultaneous Multi-Mastering with the Avalon Bus[END_REF] (i.e., there is a dedicated connection from each potential bus master to each slave device that it can master). Although each processor and device appears to connect to a shared bus, there are no shared lines in the system. This structure is illustrated in Figure 2. The Avalon Bus effectively prevents the use of bus snooping protocols and directory protocols to implement cache coherency. A non-trivial amount of invasive hardware re-development would be necessary after system generation to monitor every set of primary bus connections, denoted by ovals in Figure 2.

Design and Implementation

We now describe the design and implementation of a cache coherency module (CCM). The goal of the CCM is to enforce cache coherency with a minimum of alterations to existing vendor-provided IP. This requires a careful examination of the Nios and the Avalon Bus to understand which features facilitate and hinder cache coherency. It is also advantageous to make the process of instantiating a cache coherent SMPoPC as seamless and transparent as possible, with little if any deviation from the existing system generation procedure.

Processor Identification

The Nios processor has a CPU ID control register that stores the version number of the Nios processor. This register is read-only so it is not well-suited for processor identification. Several solutions exist: (i) changing the value of the CPU ID control register, (ii) adding a control register to the Nios, (iii) implementing a small ROM for each processor to store a unique processor ID (PID), and (iv) implementing a custom instruction in each Nios to return a unique value. The only non-invasive solution is (iii). In addition to being simple and non-invasive, this approach takes advantage of the Avalon Bus architecture to make each ROM accessible to its corresponding processor. This exclusivity also allows the ROMs to be assigned the same address to conserve address space.

Architecture

In the context of a SMP Nios system, traditional snooping or directory protocols are not suitable for ensuring cache coherency. A directory protocol would either require a dedicated bus or consume additional bandwidth on an already congested system bus. A directory protocol would require invasive changes to each Nios processor so that its cache could send, receive and understand directory protocol messages. Such a protocol would also incur a large hardware cost in the form of the central directory.

A snooping protocol would require snooping hardware to be added to monitor the caches. The Nios processor implements a pair of instruction and data caches with a writethrough policy [START_REF]Nios Embedded Processor 32-Bit Programmer's Reference Manual[END_REF]. Traditionally, cache coherency is enforced by creating a hardware module for each cache that monitors the processor's memory bus. This, unfortunately, is not feasible due to the point-to-point nature of the Avalon Bus. Thus, a traditional snooping protocol cannot be used.

Our solution involves adding a slave peripheral to the system module to inform processors of memory writes. Implementing cache coherency through a slave peripheral allows system developers to instantiate the peripheral using the standard system generation tools. This solution is easy to implement since the Avalon Bus is well-specified. This is, in reality, a hybrid snooping protocol, that uses a centralized peripheral module to snoop the bus and maintain a "directory" to enforce coherency. The module can access the relevant signals on the Avalon Bus. This solution works with standard interfaces to peripherals (e.g., on-chip RAM, memory controller, etc.) or with special interfaces (e.g., tristate bridge used to communicate with off-chip SRAM and flash memories).

Figure 3 shows the CCM in relation to a typical Nway SMP Nios system. The CCM must be able to detect writes as well as read the address bus. This allows the module to notify the processors of modified memory addresses, so that the appropriate cache line can be invalidated. The cache line must be invalidated, as opposed to updated, since the Nios only possesses the ability to invalidate particular cache lines. Invalidation is performed by writing the appropriate address to specific control registers implemented in each Nios processor. An update policy would require invasive changes to the system.

Figure 3. SMPoPC Nios system architecture

The implementation of cache clearing through processor control registers requires that software play a role in maintaining coherency. Due to the importance of maintaining coherency, the software component was written as a highpriority interrupt service routine (ISR). The CCM, a slave peripheral, raises an interrupt to enforce cache coherency.

Hardware Cache Coherency Module

The cache coherency module is divided into three components: a write detect component (one per memory device to be monitored), a central register bank component (one per system), and an Avalon slave port component (one per processor). The write detect component is responsible for snooping a single memory bus and detecting writes. For each write that is detected, the address is stored in a FIFO queue. If one or more FIFOs contain entries, then the 1-bit STATUS register is set, causing the Avalon slave ports to interrupt all of the processors. The 32-bit ADDRESS register stores the current address being processed. Once each processor in the system has read ADDRESS, the next address is processed. The STATUS register is cleared once all addresses have been processed allowing all processors to resume normal execution. Finally, a 1-bit CONTROL regis-ter allows the CCM module to be disabled to prevent the setting of the STATUS register. The CCM can be introduced into a system using the vendor-provided system generation tools without user intervention. Further details, including schematics and VHDL, can be found in [START_REF] Hung | Cache Coherency for Symmetric Multiprocessor Systems on Programmable Chips[END_REF]. This is a second-generation CCM design that improves performance and resolves a flaw in the original design [START_REF] Hung | Enabling Cache Coherency for N -Way SMP Systems on Programmable Chips[END_REF][START_REF] Hung | Cache Coherency for Symmetric Multiprocessor Systems on Programmable Chips[END_REF].

Interrupt Service Routine

The CCM ISR was written as a "system" ISR in Nios assembly language (as opposed to a "user" ISR based on vendor-provided C/C++ routines). The user ISR overhead (an additional 61 instructions, including 30 memory accesses) was avoided, drastically reducing ISR latency and run-time. Our ISR is 24 instructions long and works by disabling both caches, and then individually retrieving memory addresses to be invalidated from the CCM and invalidating them. It re-enables the cache and spin locks until the STATUS register is cleared (which occurs when all processors in the system have invalidated all relevant addresses). Details, including assembly code, can be found in [START_REF] Hung | Cache Coherency for Symmetric Multiprocessor Systems on Programmable Chips[END_REF].

We note three inefficiencies related to this configuration. The first is that all processors clear the specified cache line, whether it contains the data or not. This is a limitation of the Nios. The second is that the writing processor will clear its cache, even though it contains the true value, resulting in a cache miss on the next read, increasing latency. Finally, the system memory bus becomes a bottleneck when an interrupt is raised as all the processors in the system attempt to fetch the ISR code. This leads to ISR latency that scales with the number of processors since all processors must acknowledge the interrupt before normal execution can resume. This can be eliminated by duplicating ISR code in on-chip ROMs, one per processor.

The Nios supports sixty-four exception vectors. The first sixteen (0-15) vectors are unused or used for various highpriority system-level routines, including debugging and register window interrupts. Vector 16 is the highest priority exception vector available for the CCM to use. The choice of this vector is acceptable since the system-level routines do not execute under normal circumstances.

Software Requirements

The software requirements for maintaining cache coherency are simple. After initialization of each of the application processors (i.e., processors not designated as the bootstrap processor), barrier synchronization causes the application processors (APs) to wait until global initialization is complete. This is similar to the Intel SMP method of holding APs in a reset state until the bootstrap processor is finished [11]. In this case, global initialization involves installing the ISR and enabling the CCM. The application or operating system is responsible for ensuring that the perprocessor frame and stack pointers do not accidentally overwrite other processors' private memory spaces.

Memory Consistency

Memory consistency refers to the rules that a particular system follows with respect to the ordering of memory accesses (reads and writes). Defining a memory consistency model is critical to ensuring correct operation of parallel shared-memory programs.

A model in which any read to a memory location returns the value stored by the most recent write operation to that location is called the strict consistency model. The sequential consistency model relaxes the strict model, specifying that all memory accesses be serialized (they execute atomically), and that operations from a single processor appear to execute in program order [START_REF] Lamport | How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs[END_REF]. This model is simple and behaves as programmers expect.

The Nios is a scalar pipelined processor that statically schedules instructions. Thus, a single processor Nios system supports strict memory consistency. The same is not true for an SMP Nios system. The cache allows a processor to write a value, followed by a read to that new value, prior to write completion (i.e., prior to all other processors invalidating their cache). This relaxation is called read-ownwrite-early, and is allowed by sequential consistency.

An SMP Nios system follows strict program ordering since instructions are statically scheduled. Though the Nios does not execute the instruction following a write until the memory transaction is complete, this does not include any cache invalidations by other processors. The completion of the CCM ISR indicates the completion of a write, but processors continue to execute in-flight instructions while the CCM raises an interrupt. This can lead to the situation where a write to a data value occurs, followed by a write to a synchronizing variable S. If the data that is protected by S is cached and S is not, then a processor may read the new value of S, but operate on stale data in the cache.

The program ordering problem can be solved one of two ways. The first is by placing synchronizing writes three or more instructions after the data write (causing the synchronizing write to be located either as the last instruction prior to ISR execution, or after ISR execution, guaranteeing that the data cannot be accessed prior to being invalidated). The second solution is to force such data reads to bypass the cache by using the GCC volatile keyword or PFXIO assembly instruction.

An SMP Nios system also makes writes appear atomic. Write atomicity has two requirements: (i) all processors see writes to the same location in the same order (write serialization), and (ii) a written value cannot be read by another processor unless all processors read the same value. Both conditions are satisfied by the ISR, since all processors are forced to execute it at the same time, and no read can occur prior to invalidation.

Since writes appear atomic, if program order can be enforced, then the SMP Nios system appears to follow the sequential consistency model (though this has not been formally verified). Furthermore, such a system supports the read-own-write-early relaxation. Alternatively, since the solution to the program order problem is not necessarily a desirable solution, a relaxed write-after-write (WAW) ordering can be used instead of a sequential model. A programmer can choose to use either of the two models.

Experimental Results

All development and testing was performed using a Nios Development Kit, Stratix Professional Edition. This kit includes an EP1S40 FPGA with 41,250 logic elements (LEs) and 3,423,744 bits of on-chip RAM. The development board includes a 50 MHz clock, 1 MB of SRAM, 8 MB of flash and other resources. Software development was performed using the GCC toolset and hardware development was performed using Quartus II 3.2SP2. Testing was conducted using 1-, 2-, 4-and 8-way SMP systems.

Cache Coherency Tests

Two software tests were conducted to validate cache coherency. The first test performs the default start-up initialization which includes enabling interrupts and initializing the cache. A single processor is arbitrarily designated as the bootstrap processor (BSP). The BSP waits until all other processors have loaded the value of a shared variable synch into their cache and have begun a busy-wait loop on synch. The BSP then performs global initialization by installing the CCM ISR and enabling the CCM module. Finally, the BSP writes to synch allowing all other processors to begin normal execution. A system is cache coherent if the write to synch is propagated to all other processors and the other processors subsequently exit their busy-wait loops.

The second test performs consecutive writes to different addresses immediately following a write to the synch variable (executing before the ISR). This test ensures that pipelined writes are handled correctly. A system is cache coherent if all of the written addresses are invalidated.

Succinctly stated, the system with the CCM executed both tests correctly, whereas the system without the CCM failed both tests as expected.

Device Usage and Performance Analysis

Table 1 outlines the usage statistics for the different systems compiled into the EP1S40. Each Nios was configured with 1 kB of instruction and data cache. Additional slave peripherals (8-bit UART, CCM, and so forth) were also included. From Table 1, the EP1S40 can be populated with more than an 8-way system. Only 10% of the on-chip memory bits are used, thus there are sufficient resources to increase the cache sizes to 8 kB. Logic resources required for the CCM in each system were also computed; the CCM required 50, 73.5, 83.75 and 101.125 LEs per processor for the 1-, 2-, 4-and 8-way systems, respectively. In terms of memory bits, the CCM required 4 × 32 = 128 bits per memory interface per processor for a full-depth FIFO.

Table 1 indicates that the system clock frequency decreases as the number of processors increases. The critical paths for the 1-, 2-, 4-and 8-way systems were identified and all multiprocessor systems were found to have similar critical paths. These paths originated from the tri-state bus arbiters to the address lines on the tri-state bus. As the number of processors increases, the lower clock rates can be attributed to the additional arbitration logic and multiplexers for connecting to the Avalon Bus. This critical path analysis shows that the CCM is not responsible for the decrease in clock frequency [START_REF] Hung | Cache Coherency for Symmetric Multiprocessor Systems on Programmable Chips[END_REF]. Finally, comparing each N-way system with a CCM to those compiled without the CCM shows negligible differences in clock frequency; variations are -3.9% to +1.8%, further confirming that the CCM is not responsible for any decrease in clock frequency.

Conclusions and Future Work

We have presented the development of a generic, N -way SMP system with enforced cache coherency. With respect to our original goals, the system utilizes vendor-provided IP and leverages advanced features (i.e., caching). The resulting cache coherency module is an IP block, and therefore easy to use. Experimentation indicates that the CCM has no impact on the overall clock frequency of the systems. Our hardware/software solution to the cache coherency problem is scalable and efficient in terms of hardware. Finally, the solution is applicable to other vendor-provided IP with features similar to the Nios processor and the Avalon Bus.

Future work will focus on system efficiency. A second level cache can be added to the CCM to take further advantage of on-chip memory by reducing bus contention. The CCM can also be modified to raise individual interrupts for each processor, thus avoiding unnecessary cache clearing. Finally, simple test-and-set or fetch-and-increment hardware instructions can be added to the CCM to allow processors to perform atomic synchronization.

Figure 2 .

 2 Figure 2. Structure of an Avalon Bus module

Table 1 . Device usage for SMPoPC systems

 1

	Nios	Logic Elements On-Chip Memory	Fmax
	Cores Usage	%	Usage	%	(MHz)
	1	2,861	6%	46,480	1%	100.16
	2	5,790	14%	92,960	2%	83.44
	4	11,708	28%	185,920	5%	69.66
	8	24,302	58%	371,840	10%	61.74

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

* This work was supported in part by a Science and Engineering Research Canada (SERC) Discovery Grant (203763-03), a grant from Altera Corporation, and an Ontario Graduate Scholarship (OGS).


Sébastien Leriche

Stéphane Conversy

Celia Picard

Daniel Prun

Mathieu Magnaudet

Towards Handling Latency in Interactive Software

Usability of an interactive software can be highly impacted by the delays of propagation of data and events and by its variations, i.e. latency and jitter. The problem is striking for applications involving tactile interactions or augmented reality, where the shifts between interaction and representation can make the system unusable. For as much, latency is often taken into account only during the validation phase of the software by means of a value which constitutes an acceptable limit. In this short paper, we present and discuss an alternative approach: we want to handle the latency at all phases of the life cycle of the interactive software, from specification to runtime adaptation and formal validation for certification purposes. We plan to integrate and validate these ideas into Smala, our language dedicated to the development of highly interactive and visual user interfaces.

Introduction

An interactive software is a computer application which reacts, throughout its execution, to various sources of events. In particular, it produces a perceptible representation of its internal state [START_REF] Beaudouin-Lafon | Designing interaction, not interfaces[END_REF][START_REF] Myers | Survey on user interface programming[END_REF]. However, the usability of an interactive application can be appreciably impacted by the delays of propagation of data and events and by its variations, i.e. latency and jitter. The problem is striking for applications involving tactile interactions or augmented reality, where the shifts between interaction and representation can make the system unusable [START_REF] Mackenzie | Lag as a determinant of human performance in interactive systems[END_REF][START_REF] Ware | Reaching for objects in vr displays: Lag and frame rate[END_REF]. Yet, while latency constraints are expressed at specification, they are often taken into account only very late in the development processes, generally by experimental a posteriori measurements, when the system is fully implemented. For instance, in some air traffic control systems such as radar visualization or remote tower, latency in the visualization of aircrafts position (and the shifts between their real position) is evaluated during experiments. Instead of redesigning the software, this may conduct to dimension the spacing limits between aircrafts [START_REF] Cordeil | Immersive solutions for future air traffic control and management[END_REF], with direct consequences on the capacities of air traffic management.

More generally, when focusing on aeronautical software systems, the processes of certifications described in the DO-178C/ED-12C offer an important place to formal checking. We want to take the opportunity to use formal tools and techniques to handle latency in interactive software. We are particularly interested in the Smala language, dedicated to interactive systems. Smala1 is a language that has been designed to effectively support the development of reactive applications. Smala is built on the top of a set of C libraries named Djnn2 . Djnn provides a core library that implements the execution engine allowing to run a tree of components [START_REF] Chatty | Designing, developing and verifying interactive components iteratively with djnn[END_REF]. Once the tree is loaded and started, the core library starts an event loop that fairly manages the events coming from the environment. On arrival, events are dispatched to the tree components. The control structures contained in this tree specify an activation graph through which the events are propagated.

Djnn provides libraries with various components, ranging from components for arithmetic, logic, finite state machines to graphical shapes, style components, and geometric transformations. Three rendering engines are available, one based on the Qt toolkit, another one based on Cairo, and a third one based on OpenGL.

It is possible to build a tree of components by directly using these libraries and the C language. However the task is akin to those of writing an abstract syntax tree. Thus, we designed Smala so as to provide a dedicated syntax with specific symbols that helps to visualize the interaction between components. Smala comes with a compiler that transforms the Smala program into a program written in the C language.

Smala code for a chronometer is shown on Fig. 2 with an extract of generated code (C). Here, we load an SVG file containing graphical elements of the chronometer, that are associated to to dataflow elements. For instance, the graphical representation of the needle for the seconds is loaded from the SVG file, and composed with a rotation component. Then, the rotation angle is bound with the property containing the value of seconds from the chronometer. Thus, each time the value will vary, the needle will be redrawn with the corresponding angle. As an example, we completely developed the HMI of Volta, the first conventional all-electric helicopter [START_REF] Antoine | Volta: the first all-electric conventional helicopter[END_REF]. The HMI has been built concurrently by a programmer and a graphic designer, demonstrating another powerful aspect of our approach: the strict separation of concerns between the design of the visualization and the implementation of interactions.

3 Our approach to handle latency

Formal activities around Djnn/Smala

Although Smala is still under development, we already could experiment formal techniques for checking properties of Smala programs. For instance, we exploited the characteristics of the graph of activation [START_REF] Chatty | Verification of properties of interactive components from their executable code[END_REF]. This graph, deduced from the Smala code, provides all the possible activation relationships following the occurrence of an event.Thus, we managed to formally check attainability properties (i. e., an entry always ends up generating an expected exit or an alarm is always turned off in a certain configuration) or causal activation relationships (i. e., a displayed error message will never be covered by another).

In addition, with the experience gained from previous work on dedicated language and formal validation [START_REF] Matougui | Validation of cosmos dsl programs[END_REF], we experimented in [START_REF] Prun | Towards support for verification of adaptative systems with djnn[END_REF] the transformation of Smala code into Petri nets, with the idea to precisely define an operational semantics for Smala and to benefit from the associated formal tools and techniques. As a result, the semantics of Smala is currently under publication in a dedicated paper.

Our medium-term prospects concern the prolongation of the previous studies (based on the graph of activations) and the study of formal proof techniques applied to Smala code (translation into Caml and use of COQ, translation into Event-B)

Towards handling latency

We want to focus on software layers. Indeed, handling latency can be made at the hardware level with specific tools [START_REF] Zabolotny | Automatic latency balancing in vhdl-implemented complex pipelined systems[END_REF]. However, the end-to-end approaches existing today [START_REF] Casiez | Characterizing latency in touch and button-equipped interactive systems[END_REF] do not allow to understand the specific issues related to software architecture choices. They are only usable to measure the latency when the system is in its validation phase.

The classical formal approach to handle latency in software systems is to consider their Worst-Case Execution-Time (WCET) [START_REF] Puschner | Guest editorial: A review of worst-case execution-time analysis[END_REF]. WCET tools and techniques allow to verify timing properties. They are primarily made for real-time systems, and Smala programs are not. Nevertheless, since the control flow of Smala programs can be described as a tree, tree-based techniques for computing WCET could be applied. Moreover, the execution engine is being rewritten to comply with the last version of the operational semantics which is a good level to address latency issues [START_REF] Asavoae | Program Semantics in Model-Based WCET Analysis: A State of the Art Perspective[END_REF].

Relying on the operational semantics, we plan to add into Smala the reification of latency properties. This should allow the programmer to add runtime adaptations (e.g. simplification/enhancement of the visualization to comply with latency constraints) and to optimize the redrawing of the graphical scene.

At last, to limit the known impacts of the operating system on latency, we are experimenting some specific versions of Djnn that can be run on OS-less ('bare') systems. This approach should result in an autonomous and complete software platform to handle latency.

Future work

To achieve these goals, we aim at allowing the developer of interactive software to handle latency as a whole, during each phases of the software life cycle. Thus, this implies the conception of software tools for the measurement, visualization, specification, and formal checking of the different properties. These tools will make possible, during the design time, the objective evaluation of various software architecture solutions. At last, a methodology for designing interactive systems with latency constraints, based on these tools, should be designed.

Fig. 1 .

 1 Fig. 1. Tree of Djnn components for an interactive software

Fig. 2 .

 2 Fig. 2. Smala code, Djnn/C generated code, and execution result

http://smala.io

http://djnn.net


V Nollet
email: nollet@imec.be

P Avasare
email: avasare@imec.be

J-Y Mignolet

D Verkest

Low Cost Task Migration Initiation in a Heterogeneous MP-SoC *

Run-time task migration in a heterogeneous multiprocessor System-on-Chip (MP-SoC) is a challenge that requires cooperation between the task and the operating system. In task migration, minimization of the overhead during normal task execution (i.e when not migrating) and the minimization of the migration reaction time are important. We introduce a novel technique that reuses the processor's debug registers in order to minimize the overhead during normal execution. This paper explains our task migration proof-ofconcept setup and compares it to the state-of-the art. By reusing existing hardware and software functionality our approach reduces the run time overhead.

Introduction

Today's state-of-the-art MP-SoC platforms contain multiple heterogeneous processing elements (PEs). An operating system (OS) is responsible for allocating the computing resources in an optimal way. In order to react to varying run-time conditions, the OS requires heterogeneous task migration capabilities. Run-time task migration can be defined as the relocation of an executing task from its current location, the source PE, to a new location, the destination PE. This allows the OS to e.g. maximize energy savings of dynamic voltage and frequency scaling techniques. It also enables thermal chip management by moving tasks away from hot PEs. The architectural differences between the source PE and destination PE are masked by capturing and transferring the logical task state (i.e. PE-independent state), shown by Figure 1.

In order to relocate a task, the operating system notifies the task by means of a migration request signal [START_REF] Prashanth | An Approach to Heterogeneous Process State Capture/Recovery to Achieve Minimum Performance Overhead During Normal Execution[END_REF] . Whenever that signaled task reaches a migration point (M), it checks if there is a pending migration request. In case of such a request, all the relevant state information of that migration point is transferred to the operating system [START_REF] Smith | Heterogeneous Process Migration: The Tui System[END_REF] . Consequently, the OS will instantiate the same task on a different processing element. The new task instantiation will be initialized using the state information previously captured by the operating system [START_REF] Ferrari | Process Introspection: A Heterogeneous Checkpoint/Restart Mechanism Based on Automatic Code Modification[END_REF] . Finally, the task resumes execution at the corresponding migration point.

One of the main issues in heterogeneous task migration is the overhead incurred by checking for a pending migration request during normal execution (i.e. when there is no pending migration request). Especially since a task requires frequent migration points in order to reduce the reaction time. The reaction time (Figure 1) is the time elapsed between selecting a task for migration and the selected task reaching the next migration point. In order to minimize the checking overhead during normal execution, further denoted as migration initiation, we propose a novel technique targeted at embedded systems, that uses the debug registers present on most modern PEs.

The rest of the paper is organized as follows. Section 2 briefly discusses the related work. Section 3 gives an overview of our proof-of-concept task migration initiation implementation. Section 4 presents our conclusions.

Assessment of Existing Techniques

Since the 1980s, several multicomputer task migration mechanisms have been developed. Two distinctive migration initiation approaches can be identified. The first approach is based on polling [3, 4]. It introduces initiation polling points into the execution code at the location of the migration point. The amount of poll points and their placement in the code is critical for performance: too many poll points introduce a large run-time overhead, while not enough poll points increase the reaction time. The amount of work required for the OS to enable the migration request can be as little as setting a global variable. The second approach is based on dynamic modification of code. In this case, the execution code is altered at run-time to introduce the migration-initiation code after receiving a migration request. The Tui System [2] stops the concerning task and places a breakpoint instruction at every migration point. Then the task continues until a breakpoint trap occurs. In order to avoid overwriting other instructions when inserting these breakpoint instructions, extra space needs to be reserved. This can be done using dummy instructions, which introduce some performance overhead during normal execution. Prashanth et al. [1] introduce a technique that detects the fragment of code containing the next migration point and places migration initiation instructions in a copy of that code. This technique does not require any placeholder instructions. The amount of work to enable a migration point (for the second approach) is quite large in contrast to the first approach, which prolongs the reaction time. However, this mechanism can be reused as a poll-free migration initiation technique that does not require any copying or insertion of code to enable migration points. The setup of our proof-of-concept implementation is illustrated by Figure 2. After starting the task [START_REF] Prashanth | An Approach to Heterogeneous Process State Capture/Recovery to Achieve Minimum Performance Overhead During Normal Execution[END_REF] , a migration handler is registered with the operating system [START_REF] Smith | Heterogeneous Process Migration: The Tui System[END_REF] . This handler will be responsible for collecting the logical task state after the task reaches a migration point. In addition, all migration point addresses (mp) are registered with the OS [START_REF] Ferrari | Process Introspection: A Heterogeneous Checkpoint/Restart Mechanism Based on Automatic Code Modification[END_REF] . Then, the task starts executing. In the absence of a migration request, there is no run-time overhead [START_REF] Jiang | Compile/run-time support for thread migration[END_REF] . The OS maintains the migration point addresses in a task-specific data structure. With every context switch to another task the OS updates the IAC registers. When the resource manager decides to migrate a task, it activates the IAC registers (i.e. simply setting some register flags) (5) (6) . As soon as the task reaches the instruction on a migration point address (mp), a hardware interrupt is generated (7) , which activates the migration signal handler (8) . After gathering the logical task state, the task is ready for migration to the destination PE. This technique not only incurs zero overhead during normal execution (just like the poll-free solutions), it also requires just a minimal amount of OS effort in order to issue a migration request (just like the polling solutions). A drawback of this technique is the limited amount of debug registers. This means that, currently, a task cannot have more migration points than the number of available debug registers. Eventually, this drawback can be overcome by selecting the right subset of migration point addresses during the OS migration request. Another drawback is the potential interference with debuggers and the lack of compiler support for setting migration points.

Hardware Supported Migration Initiation

Conclusion

This papers details a novel task migration initiation technique for heterogeneous MP-SoC, based on the reuse of the debug registers present in most modern microprocessors. We show that our technique incurs no overhead during normal execution and minimizes the work of the operating system, which reduces the migration reaction time.

Figure 1 .

 1 Figure 1. Task migration sequence.

  Most contemporary microprocessors (PowerPC, ARM, i386, etc.) contain a set of debug registers. The PowerPC 405 [5], present in the Xilinx VirtexIIPro FPGA, contains four 32-bit Instruction Address Compare (IAC) registers. Whenever the program counter (PC) register reaches a value present in one of the activated IAC registers, an exception is generated.

Figure 2 .

 2 Figure 2. Migrating by using debug registers.

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

* This work was partly funded by Xilinx Labs, Xilinx Inc. R&D group.