Amir Fazlollahi

Fabrice Meriaudeau

Victor L Villemagne

Christopher C Rowe

Paul Yates

Olivier Salvado

Pierrick T Bourgeat

EFFICIENT MACHINE LEARNING FRAMEWORK FOR COMPUTER-AIDED DETECTION OF CEREBRAL MICROBLEEDS USING THE RADON TRANSFORM

Keywords: Cerebral Microbleeds, Susceptibility Weighted Imaging, Radon transform, multi-scale Laplacian of Gaussian, sphere detection

d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

I. INTRODUCTION

EREBRAL microbleeds (CMBs) are small deposits of hemosiderin, corresponding to prior microscopic hemorrhages [START_REF] Greenberg | Cerebral microbleeds: a guide to detection and interpretation[END_REF]. CMBs are spherical, relatively small with diameter size of 2 to 10mm [START_REF] Cordonnier | Spontaneous brain microbleeds: systematic review, subgroup analyses and standards for study design and reporting[END_REF], and hypointense on magnetic resonance images (MRI). CMBs with their anatomical prevalence are emerging as a new diagnostic marker of cognitive impairment and dementia [START_REF] Yates | Cerebral microhemorrhage and brain β-amyloid in aging and Alzheimer disease[END_REF], stroke and intracerebral haemorrhages (ICH) [START_REF] Fiehler | Cerebral microbleeds: old leaks and new haemorrhages[END_REF] and cerebral amyloid angiopathy (CAA) [START_REF] Nakata-Kudo | Microbleeds in Alzheimer disease are more related to cerebral amyloid angiopathy than cerebrovascular disease[END_REF].

Manual localization is the gold standard technique to assess incidence of CMBs. However, visual screening is time-consuming, subjective and has low reproducibility between observers [START_REF] Gregoire | The Microbleed Anatomical Rating Scale (MARS)[END_REF]. Moreover, it is prone to errors as small CMBs can be easily missed, or mistaken for vessel cross-sections, especially in MR Susceptibility Weighted Imaging (SWI) due to the high sensitivity of this sequence to magnetic susceptibility [START_REF] Ayaz | Imaging cerebral microbleeds using susceptibility weighted imaging: one step toward detecting vascular dementia[END_REF].

This study was co-sponsored by the Burgundy Regional Council.

Recently, there has been growing interest in Computer-Aided assessment of CMBs in MR images. Seghier et al. [START_REF] Seghier | Microbleed detection using automated segmentation (MIDAS): a new method applicable to standard clinical MR images[END_REF] developed a unified probabilistic normalizationsegmentation framework to mark CMBs as an extra prior class. A set of morphological constraints were also imposed on the extra tissue prior followed by another iteration of the probabilistic segmentation to limit false detections. The method achieved CMB detection sensitivity of 50% while no results were reported on false detection rate. Barnes et al. [START_REF] Barnes | Semiautomated detection of cerebral microbleeds in magnetic resonance images[END_REF] proposed a technique that first identifies hypointensities using local and global statistical thresholding algorithms. A supervised support vector machines classifier was then trained on a set of shape features to maximize the sensitivity. This method achieved sensitivity of 81.7% with 107 false CMBs per subject. Kuijf et al. [START_REF] Kuijf | Efficient detection of cerebral microbleeds on 7.0 T MR images using the radial symmetry transform[END_REF] identified spherical objects using the radial symmetry transform (RST) applied on both echoes of dual echo T2*w. Further anatomical and statistical constraints were then introduced to improve the detection rate and obtained sensitivity of 71.2% producing 17.2 false detections per subject. Bian et al. [START_REF] Bian | Computer-Aided Detection of Radiation-Induced Cerebral Microbleeds on Susceptibility-Weighted MR Images[END_REF] developed an algorithm based on 2D RST evaluated on patients suffering from brain tumors with CMBs due to external beam radiation therapy. A 3D region growing followed by geometric feature examination was used on top of RST to improve the detection rate. A sensitivity of 86.5% and an average 45 false CMBs per patients was achieved. In their method more than 10 constraints were empirically established using 5 independent patients. Most recently Kuijf et al. [START_REF] Kuijf | Semi-automated detection of cerebral microbleeds on 3.0 T MR images[END_REF] evaluated their approach on a larger cohort size by incorporating two parameters on RST responses in order to adjust for a desired sensitivity. They obtained sensitivities of 65%, 78% and 84% with 20, 49 and 96 average false detections per subject, respectively. Various characteristics of these studies are listed in Table 1.

This paper presents a flexible framework for computeraided detection of CMBs in SWI. This method utilizes a cascade of machine learning random forest (RF) classifiers that are trained on a set of robust Radon-based features. The training CMB samples are obtained from a multi-scale Laplacian of Gaussian (LoG) technique with respect to their geometric characteristics. The LoG approach significantly reduces the computational time required for analyzing 3D brain volume and also allows accurate bounding box estimation for the samples prior to feature extraction. (refer to Fig. 1)

Section II describes the dataset, candidate selection, feature extraction and classification pipeline. Section III presents results evaluated from sensitivity and false detection rates per subject. Finally, conclusion is described in Section IV.

II. MATERIAL AND METHOD

A. Dataset

This study included a data set of 7 subjects with Alzheimer's disease, 9 with mild cognitive impairment and 25 healthy controls from the Australian Imaging Biomarkers and Lifestyle study (AIBL) [START_REF] Greenberg | Cerebral microbleeds: a guide to detection and interpretation[END_REF]. The subjects included 17 females (age 77.8±7.4) and 24 males (age 76.8±6.6).

For each subject, anatomical T1w and SWI MR images were available. All MRIs were performed on a 3T Siemens TRIO scanner. 3D SWI was acquired with 0.93×0.93mm inplane resolution and 1.75mm slice thickness, repetition time/echo time of 27/20msec, and flip angle 20°. T1weighted images were acquired using a standard 3D magnetization-prepared rapid gradient echo sequence with in-plane resolution 1.0×1.0mm, slice thickness 1.2mm, repetition-time/echo-time/T1=2.300/2.98/900, flip angle 9°, field of view 240×256, and 160 slices.

The SWIs were manually labeled by two clinical experts using the Microbleed Anatomical Rating Scale (MARS) [START_REF] Gregoire | The Microbleed Anatomical Rating Scale (MARS)[END_REF]. A consensus was then attained for presence and number of lesions. For CMB presence, the inter-observer agreement was =0.65, p<0.001; reader 1 consensus =0.8, p<0.001; reader 2 consensus =0.83, p<0.001.

B. Pre-processing

The T1w image for each subject was first segmented into gray/white matter and CSF using the expectation maximization segmentation algorithm. The resulting segmentations were then combined to generate a skullstripping mask which was then rigidly aligned to the SWI image through block-matching. The SWI was also corrected for bias field using N4 [START_REF] Greenberg | Cerebral microbleeds: a guide to detection and interpretation[END_REF]. To enhance the contrast and normalize the intensity across subjects, the dynamic intensity range of the skull-stripped SWI was normalized to [0,1] after trimming the top 1% of intensity values. The image was then inverted so that CMBs and vessels appear hyperintense. To reduce noise and locally enhance the contrast, gradient based anisotropic diffusion and adaptive histogram equalization were applied on the SWIs.

C. Candidate Pre-screening

The analysis of image volumes to find all cubic regions-ofinterest (ROI) containing CMBs is a crucial step to spatially limit the high order analysis and computation time. We use a multi-scale LoG spherical/semi-spherical detection method with high sensitivity and low false detection rate [START_REF] Greenberg | Cerebral microbleeds: a guide to detection and interpretation[END_REF] Validation results in [START_REF] Greenberg | Cerebral microbleeds: a guide to detection and interpretation[END_REF] demonstrate that the current approach has higher performance in terms of sensitivity and specificity and is effective in detecting CMB candidates with invariance to intensity, orientation, translation and object scale. More importantly, it is capable of detecting CMBs adjacent to a neighboring vessel.

D. Candidate Bounding Box

To extract a set of shape features, a 3D bounding box needs to be defined per candidate proportional to its size. Radonbased features achieve a high response for spherical objects once it is placed at the center of the ROI. The bounding box should be centered on the target, be small enough to enclose the entire extent of target structure while preserving sufficient background information.

In the current dataset with an abundant presence of small CMBs with in-plane size of 2×2 pixels, an ideal bounding box as characterized above could not be defined.

To address this issue, the SWI was up-sampled by a factor of 2 in every direction through linear interpolation. The multi-scale LoG is again performed locally on the upsampled image to estimate the size of the nominated candidate from the previous step. To achieve intensity shift invariance, the top and bottom 5% of the intensity values are removed and the result rescaled to [0,1].

E. Feature Extraction

The Radon-based analysis has been shown to be effective in detecting Gaussian-like structures in the presence of noise or other structures in 2-dimensional images [START_REF] Greenberg | Cerebral microbleeds: a guide to detection and interpretation[END_REF]. The Radon transform is capable of representing significant shape characteristics through an object's directional property. This transform can be written mathematically as mapping an image f(x,y,z) to function Rf(). Let ⃗ =(sincos, sinsin, cos), =(x,y,z) a point on the image with image center as origin and ⃗ the equation of a plane for a given polar angle , then the 3D radon transform of a image volume f is defined as:

) . ( ) , , ( ) , (                n p z y x f Rf x x y y z z   (1)
where is the Dirac function. This projection is able to highlight geometric shapes described by the parameters () where  can be interpreted as the projection distance from the volume center.

Every image coordinate (x,y,z) is mapped to physical space by defining the center of the image as origin and including image spacing. Keeping the generality of the Radon projection outputs, the results are organized in 2dimensional fashion with axes of  and .

In [START_REF] Greenberg | Cerebral microbleeds: a guide to detection and interpretation[END_REF] a set of Radon-based features was proposed to detect round structures in a sliding window in the presence of noise or other structures. These features are mean and standard deviation profile computed across the Radon angledimension:

       N M mean x x Rf N M x F 1 | | ' 1 ), , ' ( 1 ) ' (    (2)          N M x mean std x F x Rf N M x F 1 2 1 ) ) ' ( ) , ' ( | | 1 ( 1

F. Classification

The capability of the proposed Radon features for identifying CMBs has been tested using binary RF classifier. High sensitivity of the candidate selection step to irregular and low contrast CMBs, adversely affects the training set to include several non-informative samples due to noise. This consequently results in an unbalanced training set with a class ratio greater than 277. The RF is able to handle large datasets with extremely unbalanced sample prevalence by incorporating class weights where misclassification of the minority class is penalized. However, the classification specificity is decreased due to the high presence of non-informative candidates in any randomly selected RF training set.

In the current work, a multi-layer classification cascade, composed of several RF classifiers, is proposed to progressively rule out non-informative samples and then train the final level on a relatively more balanced dataset. Binary RF posterior probabilities control classification performance and applying a low value in initial layers can reject obvious candidates. The leave-one-out validation scheme was extended for the classification pipeline to ensure that the subject's observation would not be part of the training sets. Fig. 3 shows the outline for a two-layer classification cascade approach.

III. EXPERIMENTS AND RESULTS

A total of 104 definite CMBs were identified from 41 SWIs with CMB prevalence of 2.36±3.09 per subject. One CMB was excluded due to its irregular shape (Fig. 5.a).

In the pre-screening step, in order to achieve sufficiently high sensitivity and specificity for candidates, the intensity and sphericalness parameters were empirically explored and set to 0.55. The multi-scale LoG smoothing kernels were assigned to [0.8:5.0] with a step size of 0.3 to comply with CMB diameter size of 2 to 10 mm. For the classification step, 2 cascades of RF classifiers were employed with leaveone subject-out validation scheme. For the first classifier, the threshold on the posterior probability was chosen as 0.1 to ensure removing a sufficient number of CMB mimics while preserving most of the true CMBs.

The pre-screening step has a very high sensitivity of ~98%, leaving 2 undetected CMBs out of 103 and produces on average 695 candidates per subject. Fig. 4 illustrates the FROC curve obtained from 1-and 2-layer classifiers. The best performance for the full process was achieved by 2layer cascade with an overall sensitivity of 92.04% producing on average 6.7 false-positives per true CMB and 16.84 false CMBs per subject. Fig. 5 shows few false negative examples resulting from the proposed method. The quantitative results of the proposed technique along with similar in the literature are summarized in Table 1. However, performance of published studies depends on the dataset and can be biased due to imaging parameters, CMB appearance, underlying disease and the manual identifications.

IV. CONCLUSION

This paper presented a flexible framework to automatically detect cerebral microbleeds on MR images with a high sensitivity and a low false detection rate. This method can therefore be used to speed up manual identification of CMBs. Furthermore, it improves reliability and minimizes the inter-rater variability that is widely reported in manual ratings. As future work, the proposed method can be further improved by including more CMBs in the training set and incorporating Hessian shape descriptors in the feature set.

  . The method has 3 steps:  Breaking down 3D sphere detection into multi-scale 1D line detection along the x, y and z dimensions.  Identifying the center of any geometric shape by combining normalized line responses obtained in the previous step.  Employing eigenvalues of the Hessian matrix of the extracted center points in order to determine spherical objects.

Fig. 1 .FmeanFig. 2 .

 12 Fig. 1. Overview of the proposed processing pipeline

2 )

 2 is the number of projection distances which is dependent on the ROI size, M and N are number of projection angles of polar coordinates θ and φ where here are assigned to: (θ, φ) [0:15:165]. (Fig. Feature descriptors extracted from the Radon should be scale, rotation and translation invariant. The proposed Radon descriptors are invariant to rotation by nature. Scale invariance is obtained by resizing F mean and F std to a fixed length. Translation invariance is enforced by placing the candidate CMBs at the center for the ROI prior to the Radon transform.

Fig. 3 .

 3 Fig. 3. Outline for a 2-layer classification cascade with leave-one-out scheme in subject level used in this paper.

Fig. 5 .

 5 Fig. 5. Slices of 3D ROIs containing CMBs are placed side by side for visualization. (a) Shows a CMB that was excluded due to irregular shape. (b)-(e) are examples of false negatives resulting from the proposed method.

Fig. 4 .

 4 Fig. 4. The FROC curve for the full process comparing one and two layer cascade classifier.

TABLE I

 I

			COMPARISON OF LITERATURE
	Method	[8]	[9]	[10]	[11]	[12]	Proposed method
	Year	2011	2011	2012	2013	2013	2013
	MRI modality	T2*	SWI	T2*		SWI	T2*	SWI
	Mag. Field	1.5T	1.5T	7.0T	3.0T	3.0T	3.0T
	Pathology	Stroke AD/MCI	CerV	1	Tumor	AD/MCI	AD/MCI
	# Subjects	30	6	18		10	38/72 2	41
	# CMBs	114	126	66		304	148	103
	Sensitivity	50%	81.7%	71.2%	86.5	78%	92.04%
	Avg. FPs	-	107	17.2		44.9	49	16.84
	1) Cerebrovascular Disease
	2) Number of pathological cases were 38 out of 72 patients where 71% of the
	CMBs were definite


Amir Fazlollahi

Fabrice Meriaudeau

Luca Giancardo

Christopher C Rowe

Victor L Villemagne

Paul Yates

Olivier Salvado

Pierrick Bourgeat

A Machine Learning Approach for Computer-Aided Detection of Cerebral Microbleed Using High-order Shape Features

Introduction:

The incidence of cerebral microbleeds (CMBs) which are small spherical lesions containing iron has come to attention as a potential biomarker for cerebrovascular disease 1 and dementia 2 . MR susceptibility-weighted imaging (SWI) has shown superior sensitivity than conventional T2*-GRE sequence for CMB detection, identifying more and smaller lesions. Visual rating, the current gold standard method for detecting CMBs, is time consuming, non-reproducible, subjective and prone to inter-reader variability as CMBs vary in size and contrast.

Several methods have been proposed for computer-aided detection of microbleeds using the Radial Symmetry Transform (RST) 3,4 , machine learning techniques 5 along with RST 6 or unified segmentation-normalization model 7 . All of these techniques suffer from low sensitivity, specificity and were mainly validated on small cohort sizes. The resulting performances (sensitivity, average false positives, total subjects) are (50%, NA, 30) 7 , (81.7%, 107, 6) 5 , (78%, 48, 72) 4 , (71.2%, 17.2, 18) 3 , (86.5%, 44.9, 15) 6 and (91%, 13.3, 30) 8 in our previous work.

This paper presents a novel machine learning approach for computer-aided detection of microbleeds in SWI. The major contributions are: identifying microbleed extent in order to extract proper cubic regions-of-interest (ROI) containing the structure, (2) extracting a set of robust 3dimensional (3D) Radon-and Hessian-based shape descriptors within the ROIs as well as 2D Radon features computed on intensity-projection images of the corresponding ROIs, and (3) incorporating a cascade of random forests (RF) classifiers to iteratively reduce false detection rates while maintaining a high sensitivity.

Method: A subset of 66 participants with CMBs comprised of 11 subjects classified as Alzheimer's disease (AD), 14 as mild cognitive impairment (MCI) and 41 healthy controls (HC) from the Australian Imaging Biomarkers and Lifestyle (AIBL) study were included. For each subject, anatomical T1w and SWI MR images were available. All MRIs were acquired on a 3-T Siemens TRIO scanner. The 3D SWI used 0.9×0.9mm in-plane resolution and 1.75mm slice thickness, repetition time/echo time of 27/20msec, and flip angle 20°. Two clinical experts had inspected the SWIs using the MARS rating method 9 and in total 231 CMBs were found. 123 CMBs were labeled as "possible" and 108 as "definite".

The T1W images were segmented using an expectation maximization algorithm to generate skullstripping masks and were then rigidly aligned to corresponding SWIs. The N4 bias field correction technique was performed to correct for intensity non-uniformity presents in SWIs. The dynamic intensity range of SWIs were then normalized to [0,1] after trimming the top 1% of intensities within the mask. To locally enhance the contrast and reduce noise, adaptive histogram equalization and gradient based anisotropic diffusion were carried out. The different processing steps of the proposed method are shown in Figure 1.

The aim in the screening phase is to identify and limit the analysis to potential regions containing CMB. We used a multi-scale spherical-like object detection approach for 3D brain images with a high sensitivity to small objects and a low false positive (FP) rate 10 . The multi-scale approach is capable of identifying the object extent along the x, y and z dimensions: R r ,r ,r . For each detected candidate, two patches with size .5 R and .5 R were considered. Within each patch, 3D Radon-and Hessian-based shape descriptors were computed: the mean (F ) and standard deviation profiles (F ) computed across the Radon angle-dimension, standard deviation along the Radon angle-dimension (f ) and the global Radon mean (f

). Using the eigenvalue decomposition of the Hessian matrix, the sphericalness (f ), largest cross-section (f ), fractional anisotropy (f ) and orientation (f ) were also computed. To address cross-sectional discontinuities due to anisotropic SWI acquisition, 2D Radon-based features were also computed over minimum-intensity projection (minIP) images of each major axis of ROIs. To achieve intensity shift invariance, the top and bottom 5% of the intensity values within the patches were removed and then rescaled to [0,1]. Radon descriptors are invariant to rotation and scale invariance is obtained by resizing the F and F profiles to a fixed length. Translation invariance is enforced when the candidate microbleeds are placed at the center of the ROI prior to Radon transform. The Hessian features are rotation, scale and shift invariace. High sensitivity of the candidate selection step to irregular and low contrast microbleeds leads to an unbalanced training set with samples without distinct geometrical structure. In the current work, a 3-layer cascade of RF classifiers is proposed to address this issue. By increasing the RF probability threshold and adding FPs to the negative training examples of the following layer, the method can progressively build a balanced dataset without non informative candidates. A leave-one-out validation scheme was used to train the cascade which has a relatively balanced and informative training set in the final layer.

Results: For validation purposes, two subsets of "definite" (D) and "possible & definite" (PD) CMBs were formed. For D set an overall sensitivity of 94.4% and an average 7.61 false positives per subject were produced. The best performance for PD set had a sensitivity of 87% with an average false-positive rate of 20.2 per subject. The results are summarized in Table 1. Discussion: In this work, a flexible machine learning framework is presented for detecting cerebral microbleeds on MR images. The proposed approach achieved higher performance and was validated on a larger number of subjects compare to previously published methods.

Table 1 .

 1 : 1. Y. Nakata-Kudo et al. Dementia and geriatric cognitive disorders, 8-14, 2006, 2. P. Yates et al.. Neurology, 77(1):48-54, 2011. 3. H.J. Kuijf et al. NeuroImage, 2011, 4. H. J. Kuijf et al. PLOS ONE, 8(6):e66610, 2013, 5. S.R.S. Barnes et al. Magnetic Resonance Imaging, 844-852, 2011, 6. W. Bian et al. NeuroImage: Clinical, Elsevier, 282-290, 2013, 7. M.L. Seghier et al. PloS one, 6(3):e17547, 2011, 8. A. Fazlollahi et al. ISMRM 2013, 9. S. Gregoire et al., 2009, 73, 1759-1766, 10. A. Fazlollahi et al., ICIP, 1158-1162, 2013,Figure 1. Overview of the proposed method Evaluation of the proposed method on "definite" and "possible and definite" set

	Step	Pre-screening	Overall results
	Data set	D	PD	D	PD
	# TP	105	231	102	201
	Avg. FPs	668	1372	7.61	20.2
	# FN	3	8	6	30
	Sensitivity	97.2%	96.5%	94.4%	87.0%

Proc. Intl. Soc. Mag. Reson.Med. 22 (2014) 1956.


Loïc Lagadec
email: loic.lagadec@ensta-bretagne.fr

FPGAs virtuels : enjeux et usages

Keywords: FPGA, virtualisation, prototypage virtuel ComPAS'2014 : Parallélisme/ Architecture / Système Neuchâtel, Suisse, du

Cet article de synthèse introduit la notion de virtualisation, appliquée aux architectures reconfigurables et en recense des cas d'usage significatifs. Ces usages balaient des préoccupations aussi diverses que la durabilité des produits (gestion de l'historique) ou le support à l'expérimentation de nouveau dispositifs (promotion de l'innovation matérielle) sans négliger la mise au point d'environnements logiciels.

Introduction

La croissance remarquable des technologies reconfigurables (FPGA) depuis leur introduction par Xilinx en 1984 s'explique par leur capacité à réaliser un traitement numérique efficace (car exécuté dans le matériel) sans totalement renoncer à une flexibilité de type « logiciel ». Cette caractéristique permet d'élargir sensiblement le champ d'usage de ces technologies, et par là même d'absorber les coûts de fabrication -non récurrents mais très élevés -sur un large volume de vente. Un point faible connu de ces technologies tient dans leur environnement de développement ; en effet les outils FPGA présentent certaines mauvaises caractéristiques, telles qu'un fort couplage à la technologie, ou encore une exigence trop élevée concernant les compétences attendues de l'utilisateur. Ainsi, l'utilisateur novice -ayant typiquement un profil d'ingénieur informatique, en poste dans une PME/PMI -est rebuté par la complexité des outils logiciels, tandis que l'utilisateur expert est, lui, potentiellement "captif", en ce sens que son expertise est intimement liée aux environnements logiciels propriétaires, mis à disposition par chaque fournisseur de solution. Ce constat pourrait être nuancé par les récentes orientations suivies par ces fournisseurs, et le glissement progressif du domaine du tout-circuit vers l'intégration de systèmes sur puce (par exemple illustré par la famille Zinq de Xilinx [START_REF]Zynq-7000 all programmable soc[END_REF]). Il peut en effet paraître naturel de penser que la composante logicielle des applications se renforçant (les SoC intègrent des c ?urs de type micro-processeurs), l'accessibilité de la technologie tend à s'accroitre. Cependant, la pleine exploitation des plateformes -qui motive souvent le choix de la technologie par opposition à une solution tout-logiciel-reste l'apanage d'une minorité d'usagers experts en micro-électronique.

Ces mêmes usagers subissent quant à eux une obsolescence de leurs développements antérieurs, puisque la compatibilité ascendante n'est pas assurée entre familles de FPGA au sein de l'offre d'un même fournisseur. Cela tient à l'usage de bibliothèques non portables ou dont les caractéristiques (débit, latence, ...) sont variables en fonction de la technologie ciblée. Ces mêmes usagers experts sont également les plus impactés par toute évolution ou refonte des outils constructeur, pourtant nécessaire à l'accompagnement de changements en profondeur dans l'offre matérielle. La suite de l'article expose une réponse à cet enjeu. La section 2 tente une analyse comparée entre l'évolution de l'ingénierie logicielle et la situation des environnements d'ESL, puis introduit la notion de FPGA virtuel, dont la section 3 recense quelques usages significatifs.

Un éclairage logiciel sur les FPGAs virtuels

Une telle situation (fort couplage entre l'environnement de développement et le support d'exécution, faible niveau d'abstraction, durabilité hypothétique des développements, etc.) n'est pas isolée. En particulier, elle a été constatée dans le domaine logiciel dans les années 1970. La situation de l'industrie du FPGA donc doit être analysée au regard de l'évolution des pratiques dans le domaine de l'ingénierie logicielle depuis les années 1970. En particulier, les quarante dernières années ont vu l'apparition de plusieurs niveaux de machines virtuelles.

Les machines virtuelles

La généralisation des compilateurs (par exemple GCC) a permis d'offrir un outillage commun aux différentes plateformes d'exécution, à la fois facile d'accès, et offrant un usage à la carte via un jeu d'options de compilation étendu. Les architectures de type processeur, ont favorisé un schéma RISC pour faciliter l'articulation avec les compilateurs et rendre les performances plus prévisibles, tout en offrant parfois des jeux d'instructions dédiées (par exemple le MMX d'Intel) pour accélérer des traitements bien identifiés et fréquemment utilisés. Les systèmes d'exploitation, ayant la charge de l'arbitrage de l'accès aux ressources, régulent les exécutions logicielles sous contraintes de parcimonie, de performance et d'équité d'accès entre processus. L'OS isole l'application des ressources manipulée (e.g. pseudo-devices et système de fichiers) ou de leur dimensionnement (e.g. mémoire virtuelle) de façon portable (e.g. POSIX). La large diffusion des machines virtuelles de niveau logiciel et des langages interprétés (Smalltalk, Java, ...) a permis d'élever le niveau d'abstraction du code en se détachant du modèle architectural sous-jacent du langage C. De nouveau, cet effort, en favorisant la modularité, la gestion en couches, et la prise en compte de l'hétérogénéité, a permis une portabilité et une durabilité du code applicatif accrues. L'effort de portage a été mutualisé en portant la machine virtuelle sur les différentes plateformes (OS + processeur). Ce portage étant maintenu dans le temps, la durabilité applicative est assurée. L'évolution matérielle ayant permis de faire collaborer plusieurs processeurs ou coeurs, les environnements logiciels se sont adaptés pour en permettre une pleine exploitation. En particulier, des environnements de programmation ont été conçus pour permettre une exploitation parallèle, homogène ou non en terme d'environnement (PVM, MPI), avec prise en compte de l'interopérabilité (CORBA, IDL). Cet effort de conception s'est structuré en couches pour permettre un ré-emploi de solutions bien caractérisées (par exemple CORBA couvre les couches 5/6/7 de l'OSI et repose sur la couche réseau). Enfin ces nouveaux développements ont été transposés dans les machines virtuelles (Smalltalk DST, Java RMI, etc.). L'évolution matérielle a donc conduit à une évolution en ouverture (au sens du principe de fermeture/ouverture [START_REF] Meyer | Object Oriented Software Construction[END_REF]) du logiciel avec une intégration verticale.

Enfin, plus récemment, est apparue une percée des machines virtuelles (Parallels, virtualBox, etc.) de niveau système, qui permettent de faire cohabiter plusieurs OS, l'un (l'hôte) hébergeant un ou plusieurs systèmes (dits invités) à qui on fournit l'illusion via un programme (la machine virtuelle) de s'exécuter sur une plateforme matérielle. Ces plateformes virtuelles sont aujourd'hui en phase de banalisation, et il existe par exemple des démonstrations de systèmes linux tournant dans un navigateur web [START_REF] Bellard | Un système linux dans un navigateur web[END_REF]. Ce qui caractérise cette évolution, c'est un mouvement constant visant à se détacher du matériel, en en offrant une vue simplifiée mais significative, manipulable, et évaluable en regard de métriques, c'est-à-dire un modèle. Le niveau d'abstraction de ces modèles s'est lui même élevé au cours du temps. Un deuxième point important tient dans la nature incrémentale de ces développements, structurés en couches -potentiellement opaques-mais dont l'interface est connue, pérenne et fiable. Cette démarche s'est fréquemment heurtée à une réticence de la part d'une partie des usagers, inquiets de la déperdition en performances brutes induite par chaque couche. Il apparait cependant que les ressources disponibles dans un système sont généralement bien supérieures au besoin réel de l'utilisateur. Ainsi ce dernier accepte volontiers d'utiliser un système invité sauf à vouloir une exploitation pleine de ses ressources (par exemple, via des applications fortement consommatrices comme les jeux vidéos). En revanche, tant le passage à l'échelle, que la capacité de remodelage -donc la productivité dans le temps -ne se sont jamais démenties.

Le prototypage virtuel

A un niveau inférieur, le prototypage virtuel consiste à développer des systèmes matériels / logiciels sans nécessiter de prototype matériel réel, c'est à dire sans qu'un circuit imprimé, un FPGA, ou un quelconque périphérique ne soit nécessaire. Cette notion de prototype virtuel connait actuellement un regain d'intérêt avec par exemple le développement de workshops dédiés tels que VIPES [START_REF] Goehringer | Workshop on virtual prototyping of parallel and embedded systems -vipes[END_REF]. L'avantage tient dans la possibilité d'échanger un élément pour un autre dans la configuration du système, avec des temps de mise à jour bien inférieurs à ceux atteignables avec le processus de développement traditionnel, qui requiert de re-concevoir le système dans sa globalité. De plus, la complexité croissante des systèmes embarqués, qui incluent de plus en plus de composantes cyber-physiques parallèles et distribuées, impose une phase d'exploration de l'espace de conception qui se révèlerait trop chronophage et coûteuse sans prototype virtuel.

Les FPGAs comme outils de prototypage

Ceci explique que, depuis quelques années, la communauté R&D cherchant à exploiter ces méthodes de prototypage a crû, en grande partie pour les industriels, sous la pression du timeto-market. Un des usages des FPGAs consiste ainsi à prototyper des circuits, avec à la clé, des cycles de développement raccourcis. Une fois le produit validé, il est ensuite soit réalisé sous la forme d'un ASIC si le volume de vente le justifie (coûts non récurrents élevés, coût marginal faible) ou déployé via des FPGAs, qui sont alors intégrés au système global. Cette seconde solution, présente bien sur l'intérêt de permettre par la suite une mise à jour in the field, c'est-àdire sans nécessiter de campagne de retour des produits. Pour les chercheurs en revanche, le prototypage permet en premier lieu de s'affranchir des contraintes de réalisation industrielle, et ouvre la porte à des domaines de recherche jusque là inaccessibles ; il est utilisé pour concevoir de futurs systèmes, et libère l'innovation car les hypothèses technologiques ne sont plus conditionnées par le réalisme contextuel d'un environnement industriel. Il est alors possible de concevoir en avance de phase des propositions pouvant déboucher à terme sur des produits.

Les IPs reconfigurables

Dans le domaine des semi-conducteurs, une société est dite fabless (sans usine, sans unité de fabrication) lorsqu'elle est spécialisée dans la conception et la vente de puces électroniques, mais qu'elle en soustraite la fabrication à des sociétés spécialisées (appelées fonderies), telles que le taïwanais TSMC. L'élévation constante des volumes de production nécessaires pour atteindre le seuil de rentabilité des équipements technologiques, explique le déséquilibre entre le nombre de sociétés fabless et le nombre de fonderies. Les sociétés fabless reposent sur un modèle économique de valorisation d'IP (Intellectual Property), c'est-à-dire le design d'une fonction électronique qu'elles protègent par des brevets ou vendent sous la forme de licences à d'autres fabricants de puces. Parmi ces IP, on retrouve des processeurs (par exemple, ARM) et des FPGAs embarqués, disponibles pour une intégration au sein de systèmes sur puce. Ainsi, un modèle de FPGA peut être disponible sans disposer de support physique de mise en oeuvre. La mise en oeuvre intervient par raffinement de ce modèle, dit Platform Independant Model (PIM) en fonction de la technologie cible ou Platform Description Model (PDM). On obtient alors une Platform Specific Model (PSM), qui constitue l'IP. Cette IP requiert des outils d'exploitation (placement routage, analyse de timing, etc.) décrits en appui sur le PIM mais paramétrés par le PDM. Aujourd'hui plusieurs fournisseurs de FPGAs sont des sociétés fabless. Ainsi, la plateforme du projet FP6 Morpheus [START_REF] Voros | Dynamic System Reconfiguration in Heterogeneous Platforms : The MORPHEUS Approach[END_REF] était elle basée sur l'intégration de telles IPs en provenance de trois fournisseurs : M2000 [START_REF] Pulini | Dynamic System Reconfiguration in Heterogeneous Platforms : The MORPHEUS Approach[END_REF], Pact XPP [START_REF] Baumgarte | PACT XPP : A self-reconfigurable data processing architecture[END_REF] et DREAM [START_REF] Lodi | A pipelined configurable gate array for embedded processors[END_REF]. Pour autant, tout changement technologique induit un coût important (à titre d'exemple de l'ordre de 3h.an pour la technologie M2000).

Les FPGA virtuels

Si en revanche, on ne souhaite pas réaliser ce portage matériel mais, à l'inverse, mettre en place une démarche réflexive (au sens de la programmation objet) d'implémentation de FPGA (invité) sur FPGA (hôte), le FPGA invité sera qualifié de FPGA virtuel ou VFPGA. Plusieurs publications adressent cette problématique depuis une dizaine d'années [START_REF] Lagadec | Placing, routing, and editing virtual FPGAs[END_REF] et l'on constate un regain d'intérêt depuis 2010. [START_REF] Kirchgessner | Virtualrc : a virtual FPGA platform for applications and tools portability[END_REF] présente VirtualRC et propose une couche système pour le portage d'application sur différentes cibles. Zuma [START_REF] Brant | Zuma : An open FPGA overlay architecture[END_REF] est une proposition de vFPGA, implémentable sur Xilinx et Altera, qui repose sur le framework VTR [START_REF] Rose | The VTR project : Architecture and CAD for FPGAs from verilog to routing[END_REF].

Cas d'usage de la virtualisation de FPGA

Plusieurs cas d'usage émergent d'une telle démarche. En premier lieu, le portage d'architectures reconfigurables plus simples que la plateforme hôte. En second lieu, l'émulation de tout ou partie de dispositifs novateurs. A l'articulation de ces usages, on retrouve les activités de mise au point d'environnements logiciels.

Exploiter des architectures existantes

Si le portage d'architectures plus simples que la cible physique peut sembler à première vue de peu d'intérêt, il convient cependant d'en considérer deux facettes très intéressantes.

Faire du vieux avec du neuf : l'émulation de dispositifs obsolètes

Le premier cas à considérer est ainsi l'émulation de dispositifs obsolètes, mais présentant de la valeur (legacy). Cette valeur est classiquement la conséquence des efforts portés sur cette technologie pour la mise en oeuvre d'applications. On cherche alors à accroître la durée de vie des Par ailleurs, certains domaines métier, présentent des durées de vie des produits bien supérieures à ce que l'on rencontre dans le domaine grand-public. En particulier les cycles de vies constatés dans les domaines aéronautique ou de défense sont classiquement 5 à 10 fois plus longs que dans le civil. Cette longévité engendre un coût important (conservation d'exemplaires de remplacement, etc.) qui peut ainsi être supprimé à la condition de valider/certifier la conformité de la solution de remplacement. A l'inverse, pour les produits ne nécessitant pas une reproduction à l'identique du comportement temporel, le portage sur une technologie plus avancée peut présenter des gains en performance pour peu que la différence de performances entre l'hôte et l'invité soit supérieure à la déperdition engendrée par le portage. Il est ainsi possible de disposer de soft-cores (processeur fourni sous forme d'IP et mis en oeuvre sur les ressources reconfigurables) plus performant que son modèle de référence.

Faire du complexe avec du simple : l'abstraction des ressources

De la même manière qu'une gestion de mémoire virtuelle permet aux systèmes d'exploitation de présenter des ressources plus abondantes que celles réellement présentes, en s'appuyant sur un étalement temporel de leur usage, certains travaux ont cherché à s'affranchir des limitations en ressources [START_REF] Fornaciari | Virtual FPGAs : Some steps behind the physical barriers[END_REF] des FPGA par une virtualisation.

Faire du neuf avec du vieux : l'ajout de fonctionnalités à des technologies

Un autre usage consiste à permettre une reconfiguration partielle dynamique sur des ressources ne disposant à priori pas de ce type de facilités. Enfin, il est possible de modifier l'équilibre entre performances (surface et temps de calcul à l'exécution) et temps de calcul de la configuration. Ce glissement permet de favoriser des architectures plus gros grain ou de pré-réserver des canaux de routage pour réduire la complexité de résorption des congestions dans le réseau d ?interconnexion. Un bénéfice critique est de faciliter la synthèse à la volée (en mode runtime). La notion de fabrique intermédiaire [START_REF] Stitt | Intermediate fabrics : Virtual architectures for near-instant FPGA compilation[END_REF] vise ainsi à permettre une compilation quasi-instantanée sur FPGA. A l'extrême, on retrouve un usage généralisé des soft-cores pour permettre une programmation sur un mode logiciel des applications.

Le support à l'innovation

A l'opposé de ces usages, centrés sur la préservation d'un existant -matériel ou savoir faire des utilisateurs -la virtualisation permet également de prototyper des dispositifs innovants et leurs environnements logiciels.

Conception de dispositifs matériels

On cherche alors schématiquement à accélérer une simulation de l'invité en tirant partie de la capacité d'accélération matérielle offerte par l'hôte. Cette accélération permet de renforcer les campagnes de tests en d'en réduire la durée. Dans un contexte industriel, la pression de mise à disposition sur le marché implique souvent de renoncer à certaines phases dans le processus de développement et cet arbitrage intervient le plus souvent au détriment des tests [START_REF] Gallagher | Keynote from Tim GALLAGHER, lockheed martin[END_REF] avec des coûts finaux potentiellent très élevés (un échec retentissant fut par exemple la mise en place du télescope Hubble, sans test de la lentille). Accélérer les tests revêt donc un caractère stratégique. Dans un contexte académique, les chercheurs ont besoin de mesurer l'intérêt de l'introduction d'une originalité dans la conception. Cette démonstration intervient en quantifiant un gain sur des scénarios de validation en vis à vis d'un sur-coût le plus souvent statique. A titre d'exemple, le projet ANR Ardyt [START_REF]The ARDyT project[END_REF] vise à identifier des alternatives au durcissement de la technologie, pour la réalisation de FPGAs destinés à un usage aéronautique ou spatial (donc soumis à un environnement agressif en terme de rayonnement). Pour cela l'intégration de dispositifs dédiés, destinés au diagnostic ou à la correction d'erreurs est étudiée. Cette intégration intervient en modifiant le prototype virtuel. Le sur-coût est établi lors de la synthèse du prototype étendu sur une technologie du commerce. Un autre cas, consiste à permettre la mise en place de bitstream relogeable sur une architecture quelconque, c'est-à-dire, sans qu'elle ait été conçue dans cette optique comme le sont par exemple les eFPGAs de la plateforme FlexTile [START_REF] Lemonnier | Towards future adaptive multiprocessor systems-on-chip : An innovative approach for flexible architectures[END_REF]. Un tel bitstream doit être perçu comme l'est une librairie .so par exemple, c'est à dire comme une portion d'application déplaçable dans l'espace d'exécution (mémoire, architecture) avec une capacité de ré-édition de liens.

Conception d'environnements logiciels

De la nature de l'architecture dépendent les besoins en terme d'outils. Or il apparait que les concepteurs d'architectures reconfigurables capitalisent naturellement sur des patrons architecturaux, ce qui laisse peu de place à des ruptures dans les outils. Le développement d'outils se focalise donc le plus souvent sur des couches supérieures du flot (par exemple la HLS [START_REF] Martin | Gaut : An architectural synthesis tool for dedicated signal processors[END_REF]) ou sur le contrôle de l'exécution (par exemple sur un mode système [START_REF] Muller | A flexible operating system for dynamic applications[END_REF]). A un niveau bas, l'information technologique est difficilement accessible sinon absente. Concevoir des outils est donc cantonnée à une activité de niche. Dans [START_REF] Paulsson | Implementation of a virtual internal configuration access port (JCAP) for enabling partial selfreconfiguration on xilinx Spartan III FPGAs[END_REF], Paulson et al. ont démontré un usage dynamique de spartan3, mais cette maitrise a été acquise au prix d'une rétro-ingénierie fastidieuse, destinée à isoler dans le binaire de configuration (à l'époque non crypté) l'ensemble des bits et leur signification, ressource par ressource. La prise en considération de FPGAs virtuels permet donc de favoriser la portabilité des outils [START_REF] Kirchgessner | Virtualrc : a virtual FPGA platform for applications and tools portability[END_REF] d'une part, mais également d'offrir un socle pérenne pour le développement d'outils innovants [START_REF] Brant | Zuma : An open FPGA overlay architecture[END_REF].

A bas niveau, les outils nécessaires à la programmation et l'exploitation des FPGAs (floorplanning, placement-routage, partitioner/packer, etc.) sont relativement peu nombreux [START_REF] Betz | VPR : A new packing, placement and routing tool for FPGA research[END_REF] [27] [START_REF] Sidiropoulos | JITPR : A framework for supporting fast application's implementation onto FPGAs[END_REF] et privilégient des modèles d'architectures simplifiés. La génération du prototype de VFPGA (incluant donc sa structuration de mémoire de configuration) permet de poser des hypothèses simplifiant considérablement la tâche aux outils d'exploitation. Une approche descendante -de type ingénierie dirigée par les modèles -permet une approche modulaire, en appui sur les raffinements (transformation de modèle à modèle) successifs. Chaque niveau peut alors constituer une pivot d'échange permettant de sortir du flot vers des outils tiers en aval ou, à l'inverse, de consommer la production d'outils tiers en amont. Émerge une infrastructure ouverte, permettant d ?aborder les étapes chronophages, et agissant en qualité de pierre angulaire pour une communauté de type open source.

Limitations

Tout ajout de couche de virtualisation induit une déperdition en performance, à la fois en terme de fréquence et de surface.

Prise en compte des comportement temporel

Dans un cadre de conception de type HPC, le comportement temporel attendu de l'application est généralement exprimé par le concepteur, mais des modifications itératives peuvent apparaitre pour garantir de façon implicite que ces contraintes sont remplies. La virtualisation altère le comportement temporel de l'exécution, l'effort de rafinement manuel est perdu, voire même peut dégrader les performances. En particulier, un des avantages de la virtualisation peut tenir dans l'assurance de disposer de bitstream relogeable. Il est cependant pratiquement impossible de garantir la constance des paramètres "technologiques virtuels" (en premier lieu les caractéristiques électrique et temporelles des ressources de la couche virtuelle). Le portage d'application et la relocation de bitstream sont donc possibles mais une prise en compte de contraintes temporelles nécessite de reconstituer le jeu de paramètres technologique et de re-synthétiser les applications en tenant compte de ces paramètres. Cette limitation n'est cependant pas pénalisante dans un cadre de synthèse de haut niveau, dans lequel le concepteur exprime des spécifications purement logicielles et donc dépourvues de notion temporelle. Le concept de FPGA virtuel ne convient donc pas à des usagers experts souhaitant tirer des performances optimales de la ressource, quitte pour cela à optimiser finement, et en grande partie manuellement, la spécification applicative. En revanche, elle présente de nombreux avantages pour un usager soucieux d'obtenir rapidement et facilement une réalisation matérielle. A l'image des VMs logicielles à ramasse miette qui ne sont pas adaptées à la programmation d'applications temps réel, l'introduction d'une couche virtuelle s'accommode bien de l'usage de synthèse de haut niveau, moins bien de la recherche de performances de pointe.

Prise en compte de la déperdition en surface

La déperdition en surface est importante (de 100x [START_REF] Lysecky | Firm-core virtual FPGA for just-in-time FPGA compilation[END_REF]

Prise en compte de l'effort logiciel

Le troisième volet des coûts de la couche virtuelle tient dans la nécessité de développer des outils d'exploitation adaptés. Cependant, de tels travaux existent [START_REF] Teodorov | FPGA physical-design automation using model-driven engineering[END_REF][START_REF] Betz | VPR : A new packing, placement and routing tool for FPGA research[END_REF] qui couvrent également la production du prototype [START_REF] Picard | Fast prototyping environment for embedded reconfigurable units[END_REF][START_REF] Padalia | Automatic transistor and physical design of FPGA tiles from an architectural specification[END_REF]. La flexibilité de ces outils permet de limiter l'effort de développement additionnel.

Conclusion

ComPAS' 2014 :

 2014 Parallélisme/ Architecture / Système Neuchâtel, Suisse, du 23 au 25 avril 2014

ComPAS' 2014 :

 2014 Parallélisme/ Architecture / Système Neuchâtel, Suisse, du 23 au 25 avril 2014 mises en o applicatives. Cet usage est classique dans le domaine du logiciel, avec par exemple la mouvance du retro-gaming sous-tendue par le développement d'émulateur de plateformes commercialisées dans les années 80.

3. 1 . 3 .

 13 Faire du simple avec du complexe : la conception orientée usage et/ou utilisateur A l'inverse, un second cas d'usage tient dans la concession d'une déperdition en ressources au profit d'une facilité d'usage accrue. Comme dans le cas des OS, le constat est fait que l'abondance de ressources permet de relâcher la contrainte d'un usage parcimonieux. Il est alors possible d'implémenter un support d'exécution adapté au besoins de l'utilisateur.Par exemple, la mise en place de matrices SIMD, bien adaptées à des traitements réguliers (traitement d'image), permet de disposer d'un modèle de calcul simplifiant la programmation de gammes d'applications. La prise en compte des architectures à plus gros grain (Coarse Grain Reconfigurable Architectures)[10] [13] s'inscrit dans la même mouvance.

ComPAS' 2014 :

 2014 Parallélisme/ Architecture / Système Neuchâtel, Suisse, du 23 au 25 avril 2014

ComPAS' 2014 :

 2014 Parallélisme/ Architecture / Système Neuchâtel, Suisse, du 23 au 25 avril 2014

FIGURE 1 -

 1 FIGURE 1 -Cycle de vie des produits et usages de la virtualisation

  à 40x[START_REF] Brant | Zuma : An open FPGA overlay architecture[END_REF]) mais peut être minorée par deux effets. Le premier est directement corrélé à la loi de Moore, et à la croissante exponentielle des ressources disponibles. Cette abondance a induit un glissement des enjeux, de l'usage parcimonieux, à un plein usage des ressources. La déperdition est donc moins problématique, d'autant que la facilité d'usage offerte par la virtualisation maximise l'usage de la couche virtuelle. Par analogie, si les machines virtuelles logicielles consomment une partie des ressources, les politiques de gestion de mémoire à base de ramasse miette permettent de réduire les fuites mémoires, et le déploiement d'applications distribuées sur plusieurs coeurs est simplifié, ce qui permet de gagner en performances. Dans le contexte VFPGA, la couche virtuelle est consommatrice mais le taux de remplissage de cette couche est plus important que celui d'une architecture généraliste. Le second effet tient dans la possibilité de spécialiser la couche virtuelle par domaine applicatif. Ainsi, certaines briques applicatives sont directement implémentées et proposées comme

	ComPAS'2014 : Parallélisme/ Architecture / Système
	Neuchâtel, Suisse, du 23 au 25 avril 2014

des primitives de l'architecture. Cette démarche renforce l'approche classique consistant à intégrer des blocs dédiés (mémoire, DSP, microprocesseur, etc.) dans les architectures. Dans le cas d'une couche virtuelle, ces ressources sont optimisées puisque implémentées sur l'hôte et ne contribuent donc pas à un sur-coût (modulo une fragmentation interne si elles ne sont pas utilisées).

ComPAS'2014 : Parallélisme/ Architecture / Système Neuchâtel, Suisse, du 23 au 25 avril 2014

Remerciements

Ce projet a partiellement été financé par le projet ARDyT (ANR-11-INSE-15).

Bibliographie