Z G Tegegne

C Viana

J L Polleux

M Grzeskowiak

E Richalot

Improving the opto-microwave performance of SiGe/Si Phototransistor through edge illuminated structure

Keywords: Edge SiGe-HPT, Phototransistor, Microwave Photonics, Radio-over-Fiber, Si photonics, RoF

This paper demonstrates the experimental study of edge and top illuminated SiGe phototransistors (HPT) implemented using the existing industrial SiGe2RF Telefunken GmbH BiCMOS technology for opto-microwave (OM) applications using 850nm Multi-Mode Fibers (MMF). Its technology and structure are described. Two different optical window size HPTs with top illumination (5x5µm 2 , 10x10µm 2 ) and an edge illuminated HPTs having 5µm x5µm size are presented and compared. A two-step post fabrication process was used to create an optical access on the edge of the HPT for lateral illumination with a lensed MMF through simple polishing and dicing techniques. We perform Opto-microwave Scanning Near-field Optical Microscopy (OM-SNOM) analysis on edge and top illuminated HPTs in order to observe the fastest and the highest sensitive regions of the HPTs. This analysis also allows understanding the parasitic effect from the substrate, and thus draws a conclusion on the design aspect of SiGe/Si HPT. A low frequency OM responsivity of 0.45A/W and a cutoff frequency, f -3dB , of 890MHz were measured for edge illuminated HPT. Compared to the top illuminated HPT of the same size, the edge illuminated HPT improves the f -3dB by a factor of more than two and also improves the low frequency responsivity by a factor of more than four. These results demonstrate that a simple etched HPT is still enough to achieve performance improvements compared to the top illuminated HPT without requiring a complex coupling structure. Indeed, it also proves the potential of edge coupled SiGe HPT in the ultra-low-cost silicon based optoelectronics circuits with a new approach of the optical packaging and system integration to 850nm MMF.

INTRODUCTION

With the recent explosive growth of connected objects, for example in Home Area Networks, the wireless and optical communication technologies see more opportunity to merge with low cost Micro-Wave-Photonics (MWP) technologies [START_REF] Iezekiel | RF Engineering Meets Optoelectronics Progress in Integrated Microwave Photonics[END_REF]. Millimeter frequency band from 57GHz to 67GHz is used to accommodate the very high speed wireless data communication requirements [START_REF] Guillory | 60GHz Intermediate Frequency over Fiber using a passive Multipoint-to-Multipoint architecture[END_REF]. However, the coverage distance of these wireless systems is limited to few meters (10m). The propagation is then limiting to a single room mostly, due to both the high propagation attenuation of signals in this frequency range and to the wall absorption and reflections. Therefore, an infrastructure is needed to lead the signal to the distributed antennas configuration through MWP technology. Moreover, MWP technology has recently extended to address a considerable number of applications [START_REF] Iezekiel | RF Engineering Meets Optoelectronics Progress in Integrated Microwave Photonics[END_REF] including 5G mobile communication, biomedical analysis, Datacom, optical signal processing and for interconnections in vehicles and airplanes. Many of these novel application areas also demand high speed, bandwidth and dynamic range at the same time they require devices that are small, light and low power consuming. Furthermore, implementation cost is a key consideration for the deployment of such MWP systems in home environment and various integrated MWP applications. Thus, BiCMOS compatible SiGe heterojunction bipolar phototransistors (SiGe HPT) are potential candidates for high speed photoreception [START_REF] Viana | A hybrid photo-receiver based on SiGe Heterojunction Photo-Transistor for low cost 60GHz Intermediate-Frequency Radio-over-Fiber Applications[END_REF] that were proposed first in 2003 [START_REF] Polleux | A Strained SiGe layer Heterojunction Bipolar Phototransistor for Short-Range Opto-Microwave Applications[END_REF] [START_REF] Polleux | An SiGe/Si Heterojunction Phototransistor for Opto-Microwave Applications: Modeling and first Experimental Results[END_REF] to be integrated in standard SiGe HBT technology. Since then, several laboratories are working on SiGe HPTs using different SiGe BiCMOS industrial process technologies like TSMC [START_REF] Pei | Bandwidth Enhancement in an Integratable SiGe Phototransistor by Removal of Excess Carriers[END_REF], AMS [START_REF] Yin | Low-cost, high efficiency and high-speed SiGe phototransistors in commercial BiCMOS[END_REF] and IBM [START_REF] Egels | Design of an optically frequency or phase-controlled oscillator for hybrid fiber-radio LAN at 5.2 GHz[END_REF]. All these approaches have led to top illuminated structures. Moreover, microwave HPTs have the advantage to combine a PIN photodiode with HBT, thus avoiding the need in Trans-Impedance-Amplifier (TIA) due to their high internal gain [START_REF] Ng | High current InP/InGaAs evanescently coupled waveguide phototransistor[END_REF].

Vertically illuminated photodetectors are known for their ease of light coupling but suffer from a tradeoff between conversion efficiency and frequency performance, the latter being limited by the transit time and capacitances [START_REF] Ng | High current InP/InGaAs evanescently coupled waveguide phototransistor[END_REF] [START_REF] Wake | Optically biased, edge coupled InP/InGaAs heterojunction phototransistor[END_REF]. Edge-coupled devices overcome this problem as the optical signal enters through the side of the device and propagates orthogonally to the bias field. This gives the freedom to design longer devices to ensure a high proportion of the optical signal to be absorbed while maintaining a narrow absorption region to keep transit times low [START_REF] Ng | High current InP/InGaAs evanescently coupled waveguide phototransistor[END_REF] [START_REF] Rangel-Sharp | Physical Modeling of Traveling-Wave Heterojunction Phototransistors[END_REF]. Edge coupled HPTs based on InP-InGaAs technology have been intensively studied since 1993 [10] [11].

This paper presents and compares the performance of edge and top illuminated SiGe phototransistors based on the available commercial SiGe/Si BiCMOS technology.

SIGE/SI HPT STRUCTURE UNDER STUDY

The SiGe phototransistor (HPT) was fabricated using the existing SiGe2RF Telefunken GmbH SiGe Bipolar process technology as shown in Figure 1. This BiCMOS technology has a base profile thickness of 40-80nm with abrupt SiGe layer with Ge content in the range of 20-25% and high p doping in the range of 10 19 cm -3 . The collector is typically 300-400nm thick with low doping. The phototransistor fabrication does not modify the vertical stacks of layers that are used to define a standard technology SiGe2RF HBT. This ensures the compatibility with the process technology and the potential integration of complete opto-electronic radio-frequency (OE-RF) circuits. The basic HPT structure is designed by extending the emitter, base and collector layers of the reference HBT [START_REF] Tegegne | An 850nm SiGe/Si HPT with a 4.1GHz maximum Optical Transition Frequency and 0.805A/W Responsivity[END_REF] to provide an optical access as presented in Figure 2. This HPT is essentially one large HBT whose emitter metallization was put only on the side. For top illuminated HPTs structures [START_REF] Viana | A hybrid photo-receiver based on SiGe Heterojunction Photo-Transistor for low cost 60GHz Intermediate-Frequency Radio-over-Fiber Applications[END_REF][16] [START_REF] Rosales | Full Area Emitter SiGe Phototransistor for Opto-Microwave Circuit Applications[END_REF], the optical opening is made through the emitter. Thus, the injected light path goes through the oxide and polysilicon layers of the emitter before entering the Si emitter, For edge illuminated HPT structure [START_REF] Tegegne | Edge illuminated SiGe Heterojunction Phototransistor for RoF applications[END_REF], the optical access at the edge is obtained after the standard fabrication process through polishing and dicing close to the active area of the devices as shown in Figure 3 a). We polish 80µm down to the substrate to have smooth surface at the optical beam input and we then dice it to separate the processed chip from the wafer. We have designed a 4.5µm thick (where light is coupled through) and 5µm long (maximum absorption length) phototransistor as shown in Figure 3 b). The Si 1-x Ge base layer sandwiched between the collector and emitter, both made of Silicon, is used as an evanescent optical waveguide that detects light. In both top and edge illuminated structures, the substrate is grounded through a p+ guard ring.

ON-WAFER OPTO-MICROWAVE CHARACTERIZATION

On-wafer bench setup described in [START_REF] Tegegne | An 850nm SiGe/Si HPT with a 4.1GHz maximum Optical Transition Frequency and 0.805A/W Responsivity[END_REF] is used to measure the opto-microwave performances of top and edge side illuminated HPTs. An 850nm light source, which is directly modulated, illuminates the HPT through a lensed multimode fiber (MMF). This light source has a -3dB cutoff frequency of 12 GHz [START_REF] Viana | VCSEL characterizations at the circuit-and system-levels for lowcost RoF applications[END_REF]. A tilted mirror is used to monitor the alignment of the optical probe to the optical window of the HPT on the top and edge through the microscope as shown in Figure 4 and Figure 6 respectively. The distance is set at 50µm from the surface to align the optical window with the beam waist. We use a multimode light source and multimode optical probe to characterize our device as it is targeted to implement in Home Area Network (HAN) applications at 850nm where multimode sources and MMF are largely deployed [START_REF] Guillory | 60GHz Intermediate Frequency over Fiber using a passive Multipoint-to-Multipoint architecture[END_REF].

The HPTs are mounted in a common emitter configuration topology with 100µm-pitch GSG pads in order to perform on wafer opto-microwave measurements as shown in Figure 4 a). The base is biased through an external bias tee loaded to 50Ω which is the standard normalization load in microwave applications and which is required for the HPT characterization [19][20]. The collector is connected to the port 2 of the VNA and biased through the internal bias tee of the VNA. An Agilent B1500 semiconductor parametric analyzer is used to monitor and generate the biasing levels required for the HPT. The base contact is taken from the left side, collector contact is taken from the right side and the emitter contact is connected at its top and bottom sides to the ground. The layout is accordingly sketched in Figure 5 b) which defines the optical probe coordinates with its origin given at the center of the optical window. The 5x5µm 2 HPT has similar structure as in Figure 5 except the optical window size difference. We perform the experimental mapping on 5x5µm 2 and 10x10µm 2 HPTs at appropriate dc biasing conditions with top illumination. The phototransistor is studied at a fixed collector-emitter voltage of 3V and fixed base-emitter voltage of 0.857V. These biasing conditions are the optimum biasing conditions in terms of opto-microwave responsivity. Figure 6 shows the alignment of the optical probe for edge illuminated structure. The GSG probes are put on the GSG pads and the optical probe is positioned on the side of the HPT. One of the ground panels of the HPT is removed during dicing so that one of the GSG ground line is suspended on air. The center location of the HPT's optical window is determined by scanning the optical probe along x and y axes in the vicinity of the optical window.

a b

X (m) Z (m) -2 -1 0 1 2 x 10 -5 -2 -1 0 1 2 x 10 -5 a) b)

Base contact Collector contact

Emitter contact A proper de-embedding technique is required to extract the behavior of the HPT from the pads, interconnections, optical links and probes. We use T-matrix approach [START_REF] Schiellein | Analysis of opto-microwave paths into a InP/InGaAs UTC-HPT[END_REF] to remove all the parasitic from the measurement bench setup.

EXPERIMENTAL RESULTS

Top illumined HPTs

The responsivity at 50MHz of top illuminated HPT having an optical window size of 10x10µm 2 and 5x5µm 2 as a function of optical probe position is presented in Figure 7 a) and b) respectively. The optimum biasing conditions are Vce=3V and Vbe=0.857V that maximizes both the low frequency responsivity and cutoff frequency. In both HPT the peak of the responsivity appears inside the optical window. For smaller HPT, the peak of the responsivity is still visible outside the optical window. This is related to the effect of the substrate diode which is stronger for smaller size HPT [START_REF] Tegegne | Substrate diode effect on the performance of Silicon Germanium phototransistors[END_REF]. The maximum responsivity is higher for 10x10µm 2 optical window size HPT than 5x5µm 2 optical window size HPT. This is due to better coupling efficiency and higher internal current gain in larger size HPT. HPTs. The cutoff frequency is usually small in phototransistor mode as the HPT has a -20dB/dec slope response (related to its internal amplification processes). Figure 9 shows the slice curves of low frequency responsivity (a) and cutoff frequency (b) for 10x10µm 2 and 5x5µm 2 optical window size HPT at x=0. These curves can be decomposed into two different regions (A and B) as shown in Figure 9. Region A represents responsivity and cutoff frequency extracted mainly from the substrate diode. In region B the extracted responsivities and cutoff frequencies correspond to the frequency response of the phototransistor and hence the peak appears in this region. The peak responsivity of about 0.25A/W and 0.1A/W were measured for 10x10µm 2 and 5x5µm 2 optical window size HPTs respectively. We were also able to extract a cutoff frequency up to 420MHz for 10x10µm 2 and 350MHz for 5x5µm 2 HPT at x=z=0µm. Theoretically, the cutoff frequency of smaller surface area transistors has to be higher than larger surface area due to the RC limit. However, from our experimental result, the -3dB cutoff frequency of 5x5µm 2 optical window size HPT is smaller than the cutoff frequency of 10x10µm 2 optical window size HPT. This is due to the presence of excess substrate photocurrent in smallest size HPT. This excess substrate current is related to the weak coupling efficiency of 5x5µm 2 HPT [START_REF] Tegegne | Substrate diode effect on the performance of Silicon Germanium phototransistors[END_REF]. Thus 10x10µm 2 optical window size HPT is the optimal structure to improve both the cutoff frequency and responsivity compared to 5x5µm 2 optical window size HPT. As a result in discussion section we will focus on the experimental results of 10x10µm 2 optical window size HPT to compare with the edge illuminated one.

Edge illumined HPT

Figure 10 shows the SNOM view of the low frequency responsivity and cutoff frequency of an edge illuminated HPT under 50Ω condition at 50MHz in HPT obtained by setting Vbe=0.85V and Vce= 1.5V. At this biasing condition the low frequency responsivity reaches 0.26A/W and the cutoff frequency 798MHz as it is also shown in the cross section curve in Figure 11.

The maximum of the responsivity appears at x=y=0µm. However, the maximum of the cutoff frequency is shifted to the positive x axis as it is shown in Figure 10 b). The cutoff frequency increases when the optical probe moves towards the positive x axis (when it moves towards the base contact) and it drops to small value when the fiber moves towards the center of active region eventually towards negative x axis (when moving towards the collector contact). The main explanation considers the lateral distance that electrons and holes need to go across to reach the collector and base contacts respectively. Under illumination of the HPT structure, the holes and electrons generated in the base collector junction move towards the base and collector contacts respectively. However, the distance covered by electrons and holes to reach their respective contact depends on the position of the light illumination. When it is illuminated near the base contact the lateral distance to travel by electrons is larger, whereas the distance travelled by holes is shorter. When it is illuminated near the collector the lateral distance traveled by electrons is shorter and the distance travelled by holes is longer. However, the speed of electrons is much higher than the speed of holes. As a result, when the optical beam illuminates near to the collector contact, the photogenerated holes take a longer time to reach the base contact than electrons does to reach the collector contact when the optical beam illuminates close to the base. As a result the speed of the HPT becomes slower when light is injected farther than the base contact. We measure the opto-microwave response of the edge illuminated HPT with a very good and well optimized optical coupling under Vbe =0.85V and Vce =1.5V at the both peaks ((x=0µm, y=0µm) and (x=4µm, y=0µm)).

The low frequency responsivity and cutoff frequency are largely improved. Figure 12 a) presents the optomicrowave gain (Gom) versus frequency for an edge illuminated HPT at x=y=0µm (where the peak of responsivity appears) and x=4µm, y=0µm (where the peak of f -3dB appears). As shown in Figure 12 a), we observe a low frequency (50MHz) opto-microwave gain of -7dB (opto-microwave responsivity of 0.45A/W) at x=y=0µm.

Figure 12 b) shows the normalized Gom versus frequency of edge illuminated HPT at (x=4µm, y=0µm) and at (x=0µm, y=0µm). We observe the cutoff frequency can reach up to 890MHz. The cutoff frequency when the low frequency Gom is maximum (x=0µm, y=0µm) is only 150MHz. This clearly indicates the influence of the substrate diode on the cutoff frequency and responsivity [START_REF] Tegegne | Substrate diode effect on the performance of Silicon Germanium phototransistors[END_REF] (responsivity increases in the presence of substrate diode effect whereas cutoff frequency decreases). HPT having a 10x10µm 2 optical window. For a top illuminated SiGe HPT, a 10x10µm 2 optical window size leads to the best performances in terms of opto-microwave responsivity and cutoff frequency compared to 5x5µm 2 optical window sizes HPT. As shown in Figure 13 a), we observe a low frequency (50MHz) optomicrowave gain of -7dB (opto-microwave responsivity of 0.45A/W) and -10dB (opto-microwave responsivity of 0.32A/W) for edge and top side illuminated HPTs respectively.

DISCUSSION

The improvement in the responsivity for edge side illumination is related to the increase of the absorption length.

It can be up to 5µm long whereas for top illuminated HPT the absorption length is less than 1µm (which is the total thickness of the active area including emitter, base and collector).

Figure 13 b) shows the normalized Gom versus frequency for 10x10µm 2 HPT with top illumination and for edge illuminated HPT. We observe edge illuminated HPT can reach up to 890MHz cutoff frequency whereas the top illuminated one is limited to 420MHz. We measure higher cutoff frequency for lateral illuminated HPT as its surface area is smaller compared with 10x10µm 2 optical window size HPT. Compared with the top illuminated structure of about the same size (5x5µm 2 ), the speed of lateral illuminated HPT is much higher.

CONCLUSION

The lateral and edge illuminated SiGe/Si HPTs were designed and fabricated by using the existing SiGe BiCMOS technology. The optical opening is designed by extending the base, emitter and collector of the HBT technology. A two-step post fabrication process was used to create an optical access on the edge through polishing and dicing techniques. A low frequency opto-microwave responsivity of 0.45A/W and optomicrowave cutoff frequency of 890MHz was measured for edge illuminated structure. Compared to top illuminated HPT, edge illuminated HPT improves the cutoff frequency by more than a factor two and also improves the responsivity from 0.32A/W to 0.45A/W while using a simple lensed MMF fiber for the coupling. This phototransistor could be used in further opto-microwave applications whose operating frequency could lie in the 1-10GHz range where integration to Si Integrated Circuits (ICs) and costs are the main issues. Further optical coupling structures could improve the performances. However, these results demonstrate that a simple etched HPT is still enough to achieve improvements compared to the top illuminated HPT without the need of complex coupling structure, even when using MMF Further improvements of the edge SiGe-HPT performances could be achieved by extending the emitter metallization through the entire emitter contact region. Another way could be to use either smaller optical beam optical source with SMF at 850nm or use MMF with a proper optical coupling structure to characterize the HPTs. One could also take the advantage of the substrate diode to enhance the low frequency responsivity at low frequency.

Figure 1 :

 1 Figure 1: Schematic cross-section of SiGe2RF technology from Telefunken

Figure 2 :

 2 Figure 2: Simplified schematic cross section of an extended Emitter Base Collector HPT

Figure 3 :

 3 Figure 3: a) The microscopic picture of the edge illuminated HPT where the metal contacts, HPT and the edge of the HPT are shown clearly. b) The layout of the edge illuminated HPT along with its dimensions.

Figure 4 :

 4 Figure 4: a) Top view of the fiber probe spot illuminating the phototransistor, with RF probes and GSG access lines; b) Side view through the tilted mirror of the fiber probe illuminating the phototransistor from the top side.

Figure 5 a

 5 Figure 5 a) shows the microscope picture of the 10x10µm 2 phototransistor where the ground (top and bottom) and signal (left and right) lines are clearly visible.The base contact is taken from the left side, collector contact is taken from the right side and the emitter contact is connected at its top and bottom sides to the ground. The layout is accordingly sketched in Figure5 b) which defines the optical probe coordinates with its origin given at the center of the optical window. The 5x5µm 2 HPT has similar structure as in Figure5except the optical window size difference. We perform the experimental mapping on 5x5µm 2 and 10x10µm 2 HPTs at appropriate dc biasing conditions with top illumination. The phototransistor is studied at a fixed collector-emitter voltage of 3V and fixed base-emitter voltage of 0.857V. These biasing conditions are the optimum biasing conditions in terms of opto-microwave responsivity.

Figure 5 :

 5 Figure 5: a) Top view of the 10x10μm 2 phototransistor. b) The layout of the HPT with optical window at the center as a function of the optical probe position.

Figure 6 :

 6 Figure 6: a) Top view of the fiber probe illuminating the phototransistor on the edge, with RF probes on the side and GSG access lines; b) Front view through the tilted mirror of the fiber probe spot illuminating the phototransistor. The optical probe is scanned all over the HPT optical window surface on the top and edge side. For each position, S-parameters of the optical link are measured in the [50MHz-20GHz] frequency range using the VNA. A 2µm step (+/-20nm) is used to cover a 60µmx60µm surface over the top and edge of the HPT. It then provides a complete Opto-Microwave Scanning Near-field Optical Microscopy (OM-SNOM) view of the HPT frequency response.

Figure 7 :

 7 Figure 7: Low frequency responsivity (A/W) topological maps at Vce=3V and Vbe=0.857V a) 10x10µm 2 optical window HPT, b) 5x5µm 2 optical window HPT.

Figure 8 a

 8 Figure 8 a) and b) presents the topological map of the -3dB cutoff frequency of 10x10µm 2 and 5x5µm 2 optical window HPTs respectively. It is well centered and the peak appears at the center of the optical window in both

Figure 8 :

 8 Figure 8: -3dB cutoff frequency (in GHz) topological maps at Vce=3V and Vbe=0.857V a) 10x10µm 2 optical window HPT, b) 5x5µm 2 optical window HPT.

Figure 9 :

 9 Figure 9: The slice curve at x=0 of 10x10µm2 and 5x5µm2 optical window size HPTs at Vce=3V and Vbe=0.857V a) Responsivity, b) cutoff frequency.

Figure 10 :Figure 11 :

 1011 Figure 10: The edge map of lateral illuminated HPT at Vce=1.5V and Vbe=0.85V a) Responsivity, b) -3dB cutoff frequency (in GHz).

Figure 12 :

 12 Figure 12: The opto-microwave responsivity of edge HPT versus frequency at x=-4µm and y=0µm and x=y=0µm a) directly extracted. b) Normalized.

Figure 13

 13 Figure13compares the opto-microwave gain versus frequency for an edge illuminated HPT at x=y=0µm (where the peak of responsivity appears) and x=-4µm, y=0µm (where the peak of f -3dB appears) with a top illuminated

Figure 13 :

 13 Figure 13: a) The opto-microwave responsivity versus frequency of edge and top (10x10µm 2 ) illuminated HPT. b) The normalized opto-microwave responsivity versus frequency for edge illuminated HPT at x=-4µm and z=0µm and x=y=0µm, and top illuminated HPTs at its peak detection.

Substrate contact Collector contact Base contact Emitter contact

		poly Si
	TiSi & poly-SiGe SiO 2	Si n -	SiGe p + Si n	N+ sink	P+
			Si n ++ sub collector
	Si	p-Substrate

Optical window Substrate contact Collector contact Base contact Emitter contact

  SiGe base and Si collector regions. The designed optical openings of the top illuminated phototransistor are 5x5µm 2 and 10x10 μm 2 .

		poly Si
	TiSi & poly-SiGe SiO 2	Si n -	SiGe p +	Si n	N+ sink	P+
			Si n ++ sub collector
	Si	p-Substrate


Erwan Le Merrer
email: erwan.le-merrer@inria.fr

Gilles Trédan
email: gtredan@laas.fr

Application-aware adaptive partitioning for graph processing systems

Modern online applications value real-time queries over fresh data models. This is the case for graph-based applications, such as social networking or recommender systems, running on front-end servers in production. A core problem in graph processing systems is the efficient partitioning of the input graph over multiple workers. Recent advances over Bulk Synchronous Parallel processing systems (BSP) enabled computations over partitions on those workers, independently of global synchronization supersteps. A good objective partitioning makes the understanding of the load balancing and communication trade-off mandatory for performance improvement. This short paper addresses this trade-off through the proposal of an optimization problem, that is to be solved continuously to avoid performance degradation over time. Our simulations show that the design of the software module we propose yields significant performance improvements over the BSP processing model.

I. INTRODUCTION

Graph-based applications such as social networks [START_REF] Josep | The little engine(s) that could: scaling online social networks[END_REF], search engines or recommender systems [START_REF] Bahmani | Fast incremental and personalized pagerank[END_REF] have to deal with giant and constantly evolving networks of user or item interactions. Data-processing over those graphs include graphoriented operations, such as PageRank or shortest paths [START_REF] Malewicz | Pregel: a system for large-scale graph processing[END_REF]. More local vertex-oriented operations, where computations are centered on some particular vertices, are of particular interest for instance in the support of social networks. This includes users fetching their friends' profiles [START_REF] Josep | The little engine(s) that could: scaling online social networks[END_REF] (one hop retrieval), getting recommendations [START_REF] Bahmani | Fast incremental and personalized pagerank[END_REF], or being assigned an influence metric such as TunkRank [START_REF] Vaquero | Adaptive partitioning for large-scale dynamic graphs[END_REF], [START_REF] Cheng | Kineograph: Taking the pulse of a fast-changing and connected world[END_REF]. Such operations are attractive for front-end Internet applications, as query latency is low as compared to global operations, and as the graph can be updated in real time to reflect user interactions on the platform. This paper specifically values those vertexoriented computations.

In order to ensure scalability when running such applications on a set of workers, different execution models were considered by system designers. Due to it's widespread use in datacenters, the Bulk Synchronous Parallel (BSP) [START_REF] Leslie | A bridging model for parallel computation[END_REF] paradigm is the de-facto execution model for actual state-of-the-art graph processing systems [START_REF] Malewicz | Pregel: a system for large-scale graph processing[END_REF], [1]. Notably, Giraph++ [START_REF] Tian | From "think like a vertex" to "think like a graph[END_REF] introduced an alternative execution model, named BSP-hybrid. In a nutshell, this paradigm is as follows: like in BSP, BSP-hybrid workers each hold a partition (i.e. a sub-graph) of the graph; they process the requests related to this partition. Both BSP and BSP-hybrid are organized is supersteps, and inter-worker communication can only be made at the end of a superstep. Yet, unlike BSP where intra-worker communications are also delayed until the end of the current superstep, BSP-hybrid systems allow intra-worker communication to be done within the current superstep. In other words, the improvement made by BSP-hybrid is to allow algorithm steps to proceed between vertices belonging to the same partition, without being blocked by the global synchronization superstep. Therefore, requests can be processed in only one superstep provided they do not require inter-worker communication: the partitioning of the graph becomes a salient feature for fast request processing.

The quality of the partitioning method is thus at the core of BSP-hybrid efficiency: well balanced partitions cause equivalent completion times for the different workers, preventing the last-reducer curse [START_REF] Suri | Counting triangles and the curse of the last reducer[END_REF]. Simultaneously, avoiding too many graph edges in between workers allows most requests to be fulfilled locally by a worker within a superstep while reducing the network usage. These two objectives are commonly captured by the following metrics: load balancing (noted LB hereafter) and edge cut (noted C), and formalized as follows:

LB = min i∈[k] (|P (i)|) max i∈[k] (|P (i)|) , C = 1 -|{(a,b)∈E s.t. a∈P (i),b∈P (j),i =j}| |E| ,
where workers host and process over a partition of the G = (V, E) graph, P (i) denotes the partition number i, and |P (i)| its cardinality in terms of graph nodes.

The importance of a good partitioning method, for providing good values for LB and C metrics is highlighted in the paper introducing Giraph++ [START_REF] Tian | From "think like a vertex" to "think like a graph[END_REF]. Yet, the relationship between those two metrics and the performances of the BSP-hybrid processing model is unexplored. Secondly, for vertex-oriented applications, graph persistence in the processing system is mandatory for avoiding constant graph reloading (see e.g. [START_REF] Cheng | Kineograph: Taking the pulse of a fast-changing and connected world[END_REF], [START_REF] Josep | The little engine(s) that could: scaling online social networks[END_REF]). This questions the possibility to migrate vertices between workers at runtime, in the context of a constantly evolving graph; the relationship between LB and C thus becomes particularly important.

This paper addresses this unexplored relationship between LB and C in the context of a BSP-hybrid processing model, and proposes the design of a software module for further processing time improvement. Our contributions are: (i) to exhibit the graph-related tradeoff between LB and C in such a processing model. This tradeoff directly translates into the performance of applications exploiting that graph; we illustrate this principle through analysis in Section II. (ii)

Given the previous observation, to consider the problem of an adaptive partitioning method as an optimization problem, in Section III. In this problem, the optimization choices are either LB or C, and the metric to optimize is the application performance, measured by the average request processing time. (iii) Finally, to propose a blind hill climbing optimizer for adaptive partitioning, in sub-Section III-B. This module implements arguably the simplest heuristic solution to the aforementioned optimization problem. It monitors the average processing time, and leads partitioning towards LB or C improvement strategies. We finally show through simulations, in Section IV, that such module significantly improves the performance of a BSP-hybrid system.

II. IMPACT OF PARTITIONING IN THE BSP-HYBRID MODEL

In BSP systems, any vertex-to-vertex communication will be delayed until the end of the current superstep, be it intraworker or not. As a superstep ends when the last worker is done, a high stress is put on LB; C is thus taking a back seat as a network congestion consideration. In the BSP-hybrid model, dense sub-graphs on workers allow for in-worker computation between supersteps, and even partition sizes imply similar completion times and no straggler workers: both C and LB are simultaneously valuable. Yet, we show in this section that C and LB often cannot be improved simultaneously.

A. Load/Cut Trade-off Impact on Performance

We now propose a simple model, intended to capture the relationship between aforementioned concurrent objectives.

1) System Modeling: As a BSP distributed application, we assume k workers connected through synchronous equal links dedicated to an application running on top of a partitioned graph G. We hereafter coarsely model its environment. To fulfill a request r, we consider that this application only consumes two quantities: data m(r) and CPU cycles c(r). Every worker is able to provide CPU cycles at rate χ per time unit. If r is the only request on a single worker (k = 1), all the required data is available locally and instantly, therefore t r = c(r) χ . As a simple model for congestion, assume that every worker evenly splits its processor time to all the requests it has to handle (side effects such as context switches are neglected), and that the number of requests arriving at worker i is proportional to |P (i)|: a worker i provides CPU cycles to each request at rate χi |P (i)| . The data requirements of a request r are modeled as the -hop neighborhood of a node (i.e. a closed metric ball B): m(r) B(v, ) ⊂ G, where v is the center of request r. We define as a measure of requests' locality. Let us illustrate this concept: the request "get v's degree" [START_REF] Josep | The little engine(s) that could: scaling online social networks[END_REF] has a locality of 0 (every node knows its adjacency list), whereas the request "get v's graph eccentricity" (i.e. its greatest distance to any other vertex) has a locality of D, the graph diameter. A damped random walk (jump with a probability α < 1) can be modeled by an "expected" locality (e.g. = -1 log(α) ). Let p be the worker holding vertex v, center of a request r of locality . If B(v, ) ⊂ P (p), all the required information to process r is already available on p, the request processing time only depends on the CPU resources available on p: t r = c(r)|P (p)| χp . However, if ∃q, B(v, ) ∩ P (q) = ∅, then information will have to be fetched from worker q, and the duration of this fetch will add up to the request processing time. Let λ be the network latency induced by such a fetching operation. Remote fetches cannot be made parallel, mostly because the hop neighbors (and therefore the partitions holding them) are not known in advance beside direct neighbors. Therefore we model the processing time of request r when processed by p as:

tr = c(r)|P (p)| χp computing time + λ|{j = p, s. t. P (j) ∩ B(r, ) = ∅}| information fetching time . (1)
Observe that the computing time contribution depends on |P (p)| since the bigger the partition is, the more requests worker p will have to serve in parallel. The information fetching time also depends on P (p) since the bigger |P (p)| is, the higher the chances are that B(v, ) ⊂ P (p), therefore reducing the information fetching time to 0. This is the tradeoff that the partitioning strategy has to solve in order to minimize request processing time: computations over small partitions are processed faster (since the load on the machine holding the partition is low) at the cost of higher information fetching costs. On the other hand, computations over big partitions are slower, but requires on average less fetching. We now illustrate how the data requirements of the application impact this trade-off.

2) Trade-off Analysis Using a Pathological Graph: With the aforementioned tradeoff in mind, consider the graph depicted in Figure 1. This graph consists in four fully connected clusters of sizes N, N, n and n. Clusters of equal size are connected by L links, and two links connect one cluster of size N with one of size n. Assume that N > n and n > L > 1.

Two key observations are: (i) Any exactly balanced bisection (i.e. two partitions Assume LB is preferred:

G 1 , G 2 such that |G 1 | = |G 2 | = (N + n)) of the
E(tr|PLB) = φ(n + N ) χ + λ Pr(v ∈ B) = φ(n + N ) χ + λ 2C n + N . (2)
Now assume C is preferred:

E(tr|PC ) = Pr(v ∈ P1) φ|P1| χ + Pr(v ∈ P2) φ|P2| χ + λ Pr(v ∈ B) (3)
= 2φ(n 2 + N 2 ) χ(n + N ) + λ 2 n + N . (4)
If we compare those two quantities we have:

E(tr|PLB) ≤ E(tr|PC ) ⇔ (5) φ(n + N ) 2 + 2 λχC ≤ 2φ(n 2 + N 2 ) + 2 λχ ⇔ 2 λχ φ ≤ (n -N ) 2 C -1 . (6)
Therefore, in such a setting, one can draw two observations: the confirmation that if the problem is only local ( = 0), a partitioning providing a good LB is always faster (which corresponds to embarrassingly-parallel problems, as targeted by use-cases of the BSP model). On the contrary, a less local problem (e.g. users getting their influence rank) will benefit a lot from a low C. Second, final inequality (6)'s left hand side only contains application and hardware dependent variables, that are unlikely to change at runtime, even after graph updates. The inequality's right hand side only contains graph dependent variables: these are likely to evolve at runtime, as the graph evolves. A static partitioning strategy, that does not improve results of its past decisions, is thus likely to be suboptimal. This calls for the design of an adaptive partitioning module, that we now present.

III. AN OPTIMIZATION MODULE FOR ADAPTIVE PARTITIONING

A. Optimization Problem Statement

For navigating in this trade-off at runtime, a processing system has to employ a well defined function in order to choose one of the two concurrent directions for optimization (LB or C). Let E G be the general average processing time, i.e. for all requests centered on all nodes, during an arbitrary observation period. The optimization problem the graph processing system has to solve to maximize throughput in this model is therefore the minimization of:

min. E G 1/χ r∈R r ∈R c(r)δq r ,qr + λ r∈R j∈V mrj(1 -δq r ,p j ) , with 1 ≤ pi ≤ k, ∀i ∈ V, 1 ≤ qr ≤ k, ∀r ∈ R, ( 7
)
where R is the set of requests, M is the matrix of data requirements for the requests R: it is a |R| × n matrix where m ri = 1 if request r needs i's data to be processed, and 0 otherwise. Finally, c(r) if the computing cost of request r, χ is the power of each worker (in computing units per timestep), and λ is the network access latency (in timesteps), and δ is the Kronecker delta function. Vectors (p i ) i∈V and (q r ) r∈R respectively represent how the system allocates nodes and requests to workers. In practical contexts (c(r) is not too big) a good strategy is to allocate requests at their center node, leaving node allocations the only input of this problem.

In this notation, one can express the cut as:

C = 1 -1/m i,j∈V 2 aij(1 -δp i ,p j ),
with a ij being the values of the adjacency matrix associated to the graph G and m the total number of edges of the graph. Load balancing can be expressed as:

LB = min i∈1..k r∈R δi,q r max i∈1..k r∈R δi,q r .
With arbitrary input graphs and workloads, the impact of any partitioning algorithm is complex and does not permit to derive E G (t r ) from a closed-form formula. This could be observed from our example model with Eq 1, where LB and C do not appear directly in the equation. We thus have to observe the resulting evolution of this metric based on the changes of both LB and C with time. Specifically, one can observe that LB and C respectively contribute to the left and right parts of the function to minimize [START_REF] Khayyat | Mizan: a system for dynamic load balancing in large-scale graph processing[END_REF]; they therefore constitute natural optimization directions. In practice, as future requests cannot be predicted, an optimizer can 1) monitor E G and 2) change the node allocations (p i ) i∈V : migrate the nodes. The questions that remain are which nodes must be migrated, and where to migrate them. Heuristics exist for the second question [START_REF] Stanton | Streaming graph partitioning for large distributed graphs[END_REF], but are until now agnostic of current E G ; we hereafter present a simple heuristic to answer both questions at runtime.

B. An Optimizer Using Blind Hill Climbing

Given the state of the partitioning at a given time on workers, improving on either LB or C means re-configuring the system, by moving some nodes onto different workers. As finding a particular graph partitioning is a NP-complete problem (e.g. bisecting static graphs [START_REF] Garey | Computers and Intractability; A Guide to the Theory of NP-Completeness[END_REF]), we have to rely on local search optimization. Considering our computing time feedback E G , and two improvement criterions, we seek a configuration on the Pareto frontier for the optimal choice between LB and C. A classic optimization framework is hill climbing.

Among all possible optimization approaches, we choose to use hill climbing for two reasons. First, it is simple and provides a baseline for the approach: more elaborated approaches are likely to perform better for instance by leveraging previous runs to select the improvement direction. Secondly, the continuous updates of the graph perpetually prevent the system from converging to a stable state, therefore removing the local minima drawback of hill climbing.

Algorithm 1 presents the pseudo-code. The difference of our setup with a canonical hill climbing is that we cannot instantly evaluate both neighbors of current configuration, i.e. the new configuration after a step on LB and after a step on C. We thus make a random choice towards one criterion, and act as a function of resulting computing time, by committing or rollbacking changes made (an optional parameter can enforce improvement over previous configuration to be times better). We name this algorithm Blind Hill Climbing or BHC in the sequel. Methods OptimizeOnCut() and OptimizeOnBalancing() are for instance picking "bad" nodes having a large contribution to C; OptimizeOnCut() selects worst nodes on all workers, while OptimizeOnBalancing() only on the more unbalanced workers. They then allocate the selected nodes to the partitions containing the most of their neighbors (OptimizeOnCut()), or using the best heuristic from [START_REF] Stanton | Streaming graph partitioning for large distributed graphs[END_REF] (i.e. the weighted deterministic greedy strategy for OptimizeOnBalancing()). Method getComputeTime() returns current E G . Finally, method buffer() records all incoming events (vertices, requests) in a message queue, while flushBuffer() consumes those buffered events. This encapsulation ensures that no graph modification affects the system while optimization is being performed.

IV. PERFORMANCE EVALUATION BY SIMULATION

To validate our approach, we evaluate the performance of the BHC module through simulations on real-world network topologies for a panel of typical vertex-oriented graph applications. The worker model is patterned after Section II, and the system processes real graphs that are presented hereafter.

A. System Setup

We consider four applications, that are representative of different locality/computation trade-offs. Each operation is vertex-oriented, and run on the current graph partitioning: FETCH: get one-hop neighbors, to fetch and display information (e.g. on user's wall) [START_REF] Josep | The little engine(s) that could: scaling online social networks[END_REF]. RECOM: get a recommendation, for instance to propose new friends to connect to [START_REF] Bahmani | Fast incremental and personalized pagerank[END_REF]. This implementation uses random walks from the node to propose friends to. CENTRAL: get diameter 4 -hop neighbors, and compute centrality over this ego network, to identify key locations for data dissemination [START_REF] Gao | User-centric data dissemination in disruption tolerant networks[END_REF]. MIX: execute an equal load of the three previous operation.

The computational cost of the requests FETCH, RECOM, CENTRAL and MIX are respectively c(r) = 1, 2, 3 and 2.

We use different values of λ to simulate different network instantiations: one very slow with λ = 1000, one medium 1 with λ = 100 and one fast with λ = 10. The processing throughput χ of a machine is set to one, and to zero (i.e. no degradation allowed). Requests on the system are simulated as follows: 100 times per run, 1% of randomly selected nodes are the center of a request (either FETCH, RECOM, CENTRAL or MIX accordingly). We simulate various number of workers k ∈ {4, 8, 32} and migrations are up to 10% of workers' partition sizes at time of optimization. getComputeTime() is estimated by executing Eq 1 over nt 100 requests (with n t the size of the graph G at time t), randomly picking the start node. Finally, each experiment is reported as the average of 15 independent runs.

We simulate requests over growing graphs, that are real world interaction graphs available online 2 . As the information about the real growth of those graphs is not available (exact order of arrival of their vertices), we stream them by picking vertices in a random order (15 runs and then random seeds for each graph and each application). We run simulations on the following graphs: 4elt

B. Simulation Results

Figure 2 details a run of our system. In 2(a), curves represent the evolution of the request processing time E G , while the Gowalla graph is growing over time. Dashed curves represent E G 's evolution in a system with no optimization (i.e. no vertex migration), while plain curves a system implementing the BHC module. The most striking benefits of BHC are witnessed on less local applications such as CENTRAL and RECOM, e.g. with around 50% improvement for RECOM. On FETCH requests, no noticeable improvement occurs, as the state of the art algorithm from paper [START_REF] Stanton | Streaming graph partitioning for large distributed graphs[END_REF] achieves a very good static partitioning.

Figure 2(b) provides a more aggregate perspective of the results. It plots the endpoints (graphs fully streamed) with and without BHC optimization, averaged for all 45 different runs (15 for each cost ratio) on each graph, and for k = 4. First, one can observe that non-optimized results (triangles) have a worse C and LB than the results using BHC (except for RECOM, having a worse LB). Moreover, one can notice that all the non-optimized results are application-oblivious:

1 There is typically a factor 100 between a main memory based operation, and a network operation on a 1Gbps network (please refer to http://norvig.com/21-days.html).

2 http://konect.uni-koblenz.de/networks/ Fig. 2. Simulation of a graph processing system, with and without the BHC optimization module: results plotting evolution of processing time and improvement of load balancing and edge cut.

CENTRAL

E G -E G BHC E G
, where E G BHC and E G are respectively the optimized and non-optimized average request processing times). As observed before, since the original vertex assignment heuristic [START_REF] Stanton | Streaming graph partitioning for large distributed graphs[END_REF] optimizes cut, local applications like FETCH do not benefit much from BHC. Yet, all other less local applications see their runtime improved. Similarly, improvements are greater when the network latency is higher, with up to of 71% of improvement (RECOM on the escorts network, with λ = 1000). Note that degradations (red values) are possible in this simulation, as the reported numbers are averages of independent runs, where result variability may occur due to the random nature of vertex stream order for instance. On average (as seen line 31 of Figure 3), and more notably for less local applications (CENTRAL, RECOM and thus also MIX) in contexts of medium to slow networks, significant improvement results from the use of BHC. Results range from around 10%, up to 35% improvement.

As a conclusion of this evaluation Section, it appears that there is a clear gain in optimizing the processing system, based on the application runtime feedback. This is achieved by selecting and migrating vertices based on the direction (LB or C) privileged by the applications running on the system, at runtime.

V. RELATED WORK

Most of the distributed graph processing systems follow the Bulk Synchronous Parallel (BSP) model introduced by Pregel [START_REF] Malewicz | Pregel: a system for large-scale graph processing[END_REF], allowing iterative graph computations on distributed partitions of the graph. This includes systems as Giraph [1], Mizan [START_REF] Khayyat | Mizan: a system for dynamic load balancing in large-scale graph processing[END_REF], Powergraph [START_REF] Joseph E Gonzalez | Powergraph: Distributed graph-parallel computation on natural graphs[END_REF], GPS [START_REF] Salihoglu | Gps: A graph processing system[END_REF] and Kineograph [START_REF] Cheng | Kineograph: Taking the pulse of a fast-changing and connected world[END_REF]. Only recently, Giraph++ [START_REF] Tian | From "think like a vertex" to "think like a graph[END_REF] has shown significant improvement over this BSP model, by keeping global synchronization supersteps and by additionally allowing inworker computations between two of those supersteps. This is achieved by considering the vertex partitions on workers as sub-graphs. Good partitioning in Giraph++ can benefit from vertex locality. We precisely address this complex problem in this paper, to propose an additional software module for further performance improvement of BSP-hybrid systems.

Some previous works took specific steps for performance improvements, that can be classified in two categories. (i) Related works also stated that input graph characteristics are impacting the system processing time. Powergraph [START_REF] Joseph E Gonzalez | Powergraph: Distributed graph-parallel computation on natural graphs[END_REF] and GPS [START_REF] Salihoglu | Gps: A graph processing system[END_REF] improve the handling of graph with power law degree distributions, by distributing computations for highest degree vertices over the whole set of workers. (ii) Vaquero et al. [START_REF] Vaquero | Adaptive partitioning for large-scale dynamic graphs[END_REF] considered the the migration of vertices at runtime, to adapt to graph updates and preserve satisfying performances for the processing system. Some works target extreme graph VI. CONCLUSION Leveraging the recent advance proposed by Giraph++ over bulk synchronous parallel systems, this paper has studied the impact of the partitioning on processing performances of this new model. An optimization problem has been proposed to scales of billions of edges [START_REF] Martella | Spinner: Scalable graph partitioning in the cloud[END_REF]. Yet those adaptations are application agnostic or while our proposal is driven by average processing time of the applications. Those two classes of works only apply to BSP-systems; this paper addresses the adaptive graph improvement in BSP-hybrid systems. address the complex load balancing versus edge cut tradeoff. A solver for this problem, available as a generic software module for BSP-hybrid systems, has been detailed and simulated. It improves by an average of up to 35% the standard BSP-hybrid performances, by adapting the graph to the actual request workload on the system. Having exposed this partitioning trade-off and the benefits of considering it, futurework includes the deployment and testing of the optimization module in a tailored BSP-hybrid production system.

Fig. 1 .

 1 Fig. 1. Illustration of the load balancing (LB) versus edge cut (C) trade-off: contradictory decisions can be made, favoring one over the other.

  graph cuts at least 2L links. Let P LB such bisection, symbolized by Ls on Figure 1. (ii) The graph is 2-connex. The minimal cut is 2 and has a load balance min(|G1|,|G2|) max(|G1|,|G2|) of n N . Let P L such bisection, symbolized by 1s on Figure 1. Now let us compute the average processing time E(t r ) of a request centered on a node v. Since we have only two clusters, assuming ∈ {0, 1}, computing the information fetching cost is easy. Let B be the boundary of each cluster, and φ = c(r).

  (n = 15, 606, m = 91, 756), Brightkite (n = 58, 228, m = 214, 078), Digg (n = 30, 398, m = 87, 627), escorts (n = 16, 730, m = 50, 632), Facebook (n = 63, 731, m = 1, 269, 502), Gnutella (n = 62, 586, m = 147, 892), Gowalla (n = 196, 591, m = 950, 327), pgp (n = 10, 680, m = 24, 316), Slashdot (n = 79, 120, m = 515, 581) and Twitter (n = 465, 017, m = 834, 797).

  Runtime of the different applications over the Gowalla graph (λ = 100, and k = 4) along its streaming process, as a function of the number n of streamed vertices (emulating time). Mean and standard deviation computed over 15 independent runs. Aggregate load balancing (y-axis) and edge cut (x-axis) values produced with and without BHC optimization. Aggregation is made over the 10 datasets, for 15 independent runs. k = 4.

  Pseudo-code for the BHC adaptive Optimizer.

	while True do
	c bef ore ← getComputeTime();
	buffer();
	if Random(cut,balancing) == cut then
	changes ← OptimizeOnCut()
	else
	changes ← OptimizeOnBalancing()
	c af ter ← getComputeTime();
	if c af ter > c bef ore + * c bef ore then
	rollback(changes);
	else
	commit(changes);
	flushBuffer();
	Algorithm 1:

  Relative request processing time improvement (in %) of BHC for a variety of datasets, applications and system parameters. Improvements of processing time over 10% are in highlighted green, while degradations are in red.

							FETCH			MIX			RECOM
		Dataset	l=10	100	1000	l=10	100	1000	l=10	100	1000	l=10	100	1000
	w=4
	1	4elt	0.84	2.32	11.94	0.79	0.93	4.27	4.48	21.92	38.71	7.44	31.38	39.14
	2	brightkite	2.53	9.53	16.25	0.56	0.72	3.19	8.02	26.86	33.74	16.01	40.77	49.66
	3	digg	0.16	3.58	7.94	0.22	0.21	0.97	1.15	3.43	3.58	3.09	6.16	6.91
	4	escorts	0.01	0.43	4.40	0.41	2.11	15.22	23.69	57.05	68.04	43.63	67.45	71.31
	5	facebook	2.50	10.03	12.60	0.79	2.74	18.31	8.87	14.35	17.39	14.43	38.24	47.46
	6	gnutella	0.00	0.00	0.43	0.00	0.07	0.14	0.13	5.09	4.80	1.87	5.71	7.76
	7	gowalla	-2.99 9.25	7.83	0.38	0.53	1.95	3.64	14.81	33.32	7.13	35.51	60.55
	8	pgp	-0.60	13.55 8.74	0.07	0.85	5.94	7.59	32.43	28.63	17.50	37.85	39.81
	9	slashdot	0.03	4.46	1.04	0.31	0.70	4.51	4.75	6.62	5.80	8.15	23.90	28.29
	10	twitter	0.33	0.86	1.23	0.34	0.34	1.85	4.30	18.45	34.51	14.29	38.65	49.77
	w=8
	11	4elt	1.82	4.32	16.69	1.41	2.04	3.48	6.77	29.25	34.24	12.38	37.79	33.89
	12	brightkite	5.94	8.64	15.79	0.34	1.01	7.85	10.75	21.24	30.81	22.79	43.44	47.61
	13	digg	-0.31 5.20	9.00	0.20	0.37	2.56	3.29	2.77	5.21	4.32	4.83	4.83
	14	escorts	0.39	0.86	7.84	0.45	4.27	21.37	34.25	57.55	63.09	49.97	61.73	64.00
	15	facebook	9.78	11.90 5.26	1.29	5.49	27.27	13.53	19.14	21.05	20.97	39.43	42.24
	16	gnutella	0.01	0.22	0.52	0.01	0.07	1.36	0.70	1.28	0.12	2.38	5.14	3.83
	17	gowalla	6.20	15.22	18.49	0.12	0.41	3.52	2.24	24.29	24.71	10.99	38.59	51.69
	18	pgp	0.31	24.85 3.85	0.30	2.34	9.58	16.02	26.80	33.72	26.43	38.63	42.91
	19	slashdot	0.98	2.19	-4.12	0.40	1.14	3.28	4.79	10.60 2.18	11.08	20.19	23.06
	20	twitter	0.45	1.93	4.98	0.42	0.76	6.37	5.16	26.63	32.54	21.02	42.73	46.42
	w=32
	21	4elt	2.50	10.03	25.73	1.71	3.48	16.61	13.04	22.56	18.67	22.39	35.39	32.42
	22	brightkite	2.37	7.41	5.75	0.48	1.67	14.56	18.71	24.17	23.65	27.95	33.97	35.34
	23	digg	-0.63 8.12	-1.76	0.13	0.60	5.46	1.59	5.08	8.02	6.45	7.13	7.46
	24	escorts	0.68	3.81	16.56	0.93	11.41	38.83	35.81	48.19	46.24	46.47	46.86	47.59
	25	facebook	6.31	9.90	6.86	2.94	13.14	33.35	12.17	11.77	11.88	28.13	33.11	33.65
	26	gnutella	-0.12 0.65	3.25	0.03	0.14	1.58	2.56	3.19	5.67	2.31	3.31	3.87
	27	gowalla	4.34	9.41	9.30	0.28	1.41	4.38	8.89	10.23	13.05	20.85	36.89	40.06
	28	pgp	-7.45	10.89	17.67	0.94	5.57	24.45	29.17	36.76	38.70	37.58	39.59	40.43
	29	slashdot	8.97	0.26	5.70	0.29	0.08	5.64	1.65	1.83	11.96	14.42	17.48	16.81
	30	twitter	0.77	4.87	23.11	0.83	3.49	17.20	30.34	43.31	46.47	42.29	51.37	50.83
	Average
	31		1.53	6.48	8.76	0.57	2.26	10.16	10.6	20.92	24.68	18.82	32.1	35.65
	Fig. 3. all applications end up grouped at the same position. This is because the original BSP-hybrid systems does not target partitioning improvement based on the application feedback. On the contrary, results with BHC are clearly separated: optimizations are driven by E occur). CENTRAL sits in the middle. Figure finally 3 presents another aggregate results for all graphs: the relative runtime improvement (that is

G

, that lead the processing system in the best configuration for the current application. Intuitively, FETCH (green) favors LB (locality prevails), while RECOM favors C (more information fetching expected to


Antoine Diet
email: antoine.diet@u-psud.fr

Christophe Conessa

Yann Le Bihan

Francisco Alves Geeps

Marjorie Grzeskowiak

Megdouda Benamara

Gaelle Lissorgues

Detection tube for small HF RFID tags, based on mutual coupling with a coil resonator

Keywords: RFID, HF, mutual coupling, loop/coil antenna

This communication concerns the detection of 13.56 MHz (HF) RFID "small" tags. Herein, the term "small" refer to an effective area below 1 cm² and the detection principle is in volume, especially inside a tube of 9 cm in diameter and 2m in length. The ability to detect the "small" tags in the tube is achieved by using a coil resonator conformed on the tube surface, following a principle of multiple magnetic coupling, also referred as magnetic field guide. Theoretical considerations on mutual coupling formula and electrical model fit to CST simulations and VNA measurements concerning the evaluation of impedance and coupling factors range. Detection tests with an RFID reader (from IB technology) and NXP SLI-X chip confirm the possibility of detection by providing a first result of 2 cm range. This detection was impossible inside the tube without using the resonator. Perspectives of improvement evocated at the end of the paper are numerous for that structure.

I. RFID APPLICATION CONTEXT

Radio-Frequency Identification (RFID) is a well-known concept using a mature technology for traceability of objects and persons [1][2]. This technology can involve two main types of radio links: propagation backscattering for UHF (433/868 MHz) or SHF (2.45 GHz) and load modulation thanks to magnetic coupling for HF (13.56 MHz) and LF (125/134 kHz) [START_REF] Paret | Identification Radio-Fréquences et Cartes à puce sans contact[END_REF] [START_REF] Finkenzeller | RFID handbook, fundamentals and applications in contactless cards and identifications[END_REF].

RFID is used nowadays in a lot of applications, but it still exist some difficult cases in which the technological breakthrough are challenging and for which research and prototyping are still a difficult task. One of such context is, in our case, the traceability of small tags, in the range of 1 cm² , [START_REF] Qing | Proximity effects of Metallic Environments on HF RFID Reader Antenna: Study and Applications[END_REF] [START_REF] Arnaud-Cormos | Electromagnetic environment of RFID systems[END_REF] and especially metallic medical devices (mMDs). The term "small" refer to the size (ergonomic constraint) of the mMDs and the size of the RFID reader antenna/loop. MMDs are used at the hospital where the radio link of UHF RFID is difficult to deploy due to the presence of metal and many others communication systems. We investigated magnetic coupling solutions for that reason because HF and LF are less sensitive to the metal (magnetic coupling phenomenon) and are in a frequency band lower than communications systems (GPS, GSM, 3/4G, WiFi) and ISM (2.4/5GHz). Some low-cost LF prototypes were tested [START_REF] Wang | Detecting range and coupling coefficient tradeoff with a multiple loops reader antenna for small size RFID LF tags[END_REF][6] and the conclusion is that it is possible to use this technology but the penalty is the very high number of turns needed for realizing loops antennas for a sufficient reactance value. In this paper, we focused on the HF magnetic coupling solution and, for the prototypes, use the 13.56 MHz ICODE SLI-X long-range chips from NXP with a RFID reader from IB Technology.

Our goal is, more precisely, to detect mMDs with a minimum of manipulation by the hospital technical staff. The tag has also to be of minimum size, below 1 cm² for ergonomic considerations, and the control of tagged mMDs should be automatized. If possible, multiple detections ability is preferred. Consequently, we investigated the principle of detection in volume, for the tagged mMDs, driving us to consider a case study of magnetic coupling where the sizes of the tag and reader loops are very different [START_REF] Wang | Detecting range and coupling coefficient tradeoff with a multiple loops reader antenna for small size RFID LF tags[END_REF][6] [START_REF] Grzeskowiak | Pebbles Tracking Thanks to RFID LF Multi-loops Inductively Coupled Reader[END_REF]. Such problematic is presented in Figure 1 with additional consideration about tag orientations. Our work corresponds to a focus on case 2 and 3. The coupling phenomenon studied is based on the Neumann formula and drives to equation [START_REF] Paret | Identification Radio-Fréquences et Cartes à puce sans contact[END_REF], where E and K are elliptical Bessel integrals of first and second kinds, R 1 and R 2 the radii of the two (coaxial) coils, d the distance between the coils and µ 0 the vacuum permeability:

        1 d R R R R 2 ρ th wi ρ X R R μ ρ E ρ 2 ρ K ρ 2 ρ R R μ r dl . dl 4π μ M 2 2 2 1 2 1 2 1 0 2 1 0 Γ Γ 12 2 1 0 1 2                           (1)
It is possible to study the optimum size of the reader loop for maximizing the value of M, at different distances between the two loops. In Figure 2, these results are plotted for a coaxial configuration and show a shifting of the maximum value of M in function of the reader loop size (area) and the distance. Also, the value of M is highly decreasing with the distance and can be the reason of a non RFID tag detection if the limit for powering the chip is below the possible values for M. To counter this decrease in the mutual coupling effect, the case 3 in Figure 1 expressed the geometrical consideration of multiple loops possibilities. As studied in the literature and in past works at LF [START_REF] Wang | Detecting range and coupling coefficient tradeoff with a multiple loops reader antenna for small size RFID LF tags[END_REF][12], the geometrical criterion is highly efficient for magnetic coupling increasing if the reader loop/coil structure is optimized and more complex. In HF, the principle of "magnetic-field-guide" is preferred due to the electrical imperfections added by the connections (parasitic capacitance especially). This corresponds to study a multiple magnetic coupling whose parameters are dedicated to the maximization of RFID detection. A resonator will be used in order to relay the magnetic field from the reader loop to the tag loop. The transfer function will be globally maximized for power transfer (high quality factor Q) and also will present sufficient bandwidth for RF Identification (low Q) as it is usually the case in RFID (Q in the range of 20 to 40)

[1][2][8][5].

II. MUTUAL COUPLING WITH A RESONATOR

The operation principle can be theoretically schematized by the electrical circuit in Figure 3. The volume detection is performed by inserting mMDs in a tube (2 m long, 9 cm in diameter) for the control. This tube has an encircling loop along its length and its diameter and a resonator is added on the tube surface. We use a copper foil with 100 µm thickness and 6 mm width and the resonator has 2 turns and a square loop/coil shape of dimension 6x6 cm². In Figure 3, the tube reader/interrogator loop is the inductance L ant at the port 1, the resonator is the port 2 in which the loop/coil L res is loaded by a capacitance C res (Q factor represented by R res ) and the RFID tag the port 3, made of a tag loop/coil L tag loaded by the RFID chip (R chip // C chip ). As the electrical elements are all passive, the system is reciprocal: M 12 =M 21 =M a , M 32 =M 23 =M b and M 13 =M 31 . Moreover, the difference of size between the reader loop and the tag loop drives us to consider that the M 13/31 mutual coupling is quasi-null, at the origin of the problem for which adding a resonator is the proposed solution in this work. This schematic is in good agreement with our prototype, as is reported in Figure 4 where the size of the reader loop and the tag can be observed. Also, the simulation performed with CST shows the magnetic field strength around the resonator when the reader loop (tube loop/coil) is fed by its port. The CST simulation gives a theoretical value of L ant_CST = 3.1 uH for a tube of 2 meters length. Photography of the prototype and the RFID (NXP SLI-X) circular tags used in the next part (test of detection) is shown in Figure 4 (top right). Ports 2 and 3 are loaded by "RC" impedances driving to:

I 1 I 2 V 1 V 2 M 12/21 L ant L res                                                       
3 chip 3 chip chip 3 2 RC 2 res res 2 I Z I ω jC 1 // R V I Z I ω jC 1 // R V                         (2)
For RFID detection, it is important to consider the load variation seen by the reader (principle of the load modulation) expressed by equation ( 3

L L k M L L k M L jω Z M jω α α M L jω Z M jω β dZ L jω β M jω L jω I V Z               (3)
In order to maximize the detection performance, the variation dZ of Z in in equation ( 3) induced by the load variation (Z chip ) has to be maximized at the resonance frequency. The two-states AM modulation (load modulation principle, ideally ON/OFF keying modulation) is used in this standard. This implies dZ to present ideally a maximal resistive variation with no reactive part. Any reactive part acts as a mistuning of the resonance at the reader port. To reduce this penalty, the overall Q factor has not to be maximal because it increases the electrical sensitivity. This effect is also increased with strong coupling (M a and M b high). In our context, mutual coupling are weak due to the difference in size between the considered loops/coils. Preliminary observations drive us to consider coupling factor k a , see (3), of 1% in the case of M a and to evaluate a coupling factor k b , see [START_REF] Qing | Proximity effects of Metallic Environments on HF RFID Reader Antenna: Study and Applications[END_REF], between 1% and 5% for M b when the tag is near the resonator. A computation under MATLAB is done in order to evaluate the dZ with our realistic values (L int = 3 uH + a resonator with L res = 0.2 uH and a quality factor Q res =40) and is reported in Figure 5. As it can be seen in Figure 5, the real part variation (resistive load) is weak but in a sufficient range of 1  with our parameters. Moreover, a slight mistuning due to the imaginary part variation (reactive load) is observed in function of the coupling between the tag and the resonator, which can affect the load variation seen by the reader in AM mode.

Next part will report the loops/coils prototype measurements with the VNA (S and Z parameters) and the RFID detection test with the reader and real small tags.

III. TESTS OF DETECTION AND MEASUREMENTS

The prototype is built thanks to a Plexiglas tube of 2 m length with a diameter of 9 cm and a thickness of 2 mm. This material is magnetically transparent at 13.56 MHz. The copper used is the copper foil above mentioned (6 mm width / 100 µm) and the resonator is based on a 2 turns square (6x6 cm²) loop/coil with 4 mm inter-turns, as seen in Figure 6 (top left). The measured impedance of the 6x6 cm² loop/coil is 0.23+j24 Ω, i.e. 285 nH, as seen in Figure 6 (top right). In the presence (l cm distance) of an RFID SLI-X card tag (ISO standard) the coupling is strong and the impedance is highly affected (bottom left in Figure 6). To the contrary, the RFID SLI-X circular tags (below 1 cm of diameter) seen in Figure 4, weakly affect the impedance measured by the VNA, as reported in Figure 6 (bottom right).

We measured the impedance of the resonator in presence of the tag coil unloaded (without the chip) and shortened in order to evaluate experimentally the coupling coefficient k b . This gives Z coil-tag-unloaded = 0.1986 + j 21.939 and Z coil-tag-shortened = 0.1987 + j21.866, and drives us to evaluate M b around 73 nH and k b around 5.76%. In the same manner, we evaluate k a with the resonator coil impedance measurement when the tube loop is unloaded and shortened. This gives Z coil-tubeloop-unloaded = 0.1885 + j 22.256 and Z coil-tubeloop-shortened = 0.184 + j22.236, and drives us to evaluate M a around 27.9 nH and k a around 2.9%. M 13 was not evaluated in that manner due to the too high level of noise on the measurement, corresponding to the hypothesis of a too weak and neglectable value.

The resonance at 13.56 MHz is achieved with parallel capacitors (560 pF + variable 5/50 pF) and the measured Q res factor is 45.2. The tube is the support of a single turn loop (and same copper foil) whose measured impedance with the VNA is 7+j240 , i.e. 3,17 µH, in good agreement with the CST simulation. These steps (and the following ones) are reported in Figure 7.

When the resonator is fixed on the tube, the measured impedance is 13+j273 Ω, i.e. 3.2 µH. A parallel capacitor was used for tuning and variable resistance for reducing the global Q factor in the range of 30-40, see the impedance magnitude (dB) in Figure 7. It is important because the tuned tube, with the resonator fixed on it, was connected to the RFID reader as an external RFID antenna. Once the RFID reader is connected to the detection tube carrying its resonator, the small (below 1 cm²) circular tags used for our tests were detected at a distance below 2 cm from the resonator. These same tags were not detected at all without the resonators. As mMDs will go through the tube, the detection performances are encouraging and illustrate the potentiality of this original structure.

IV. CONCLUSION

In this paper, the work illustrates the potentiality of using coupled resonator for creating a magnetic field guide whose consequence is to enable a complex multiple mutual coupling between several small RFID tags, a resonator and the RFID reader/interrogator at 13.56 MHz. After theoretical consideration and CST numerical simulations, results of our first prototypes show that it is possible to detect some HF RFID tags whose effective area is below 1 cm². The potentiality of this structure is clearly encouraging because the tags are finally detected inside the tube at a distance of 2 cm from the resonator conformed on the tube surface. The focused application concerns metallic medical devices detection in hospital environment. Perspectives of this work, already in progress, are to study the impact of the different resonator parameters (geometry, turns, Q,,…) in order to improve the detection performances.

Figure 1 :

 1 Figure 1 : Magnetic coupling cases study. Orientation and dimension of the secondary loop (usually the tag) drives to difficult and weak magnetic coupling (i. e. cases 2 and 3)

Figure 2 :

 2 Figure 2 : Theoretical computing of "M" for a loop of 1 cm diameter and a reader loop whose area increases. Curves show a shifting of the maximum for "M" in function of the distance.

Figure 3 :

 3 Figure 3 : Principle of mutual coupling between the reader "tube loop", the coil resonator and the small tag. Harmonic equations are simplified in our context due to electrical reciprocity (passive) and M13 = M31 = 0 (due to the difference in loops sizes).

Figure 4 :

 4 Figure 4: RFID tags and the detection tube (top right), prototype principle and description (left) in agreement Figure 3. CST simulation (bottom right) of the magnetic field magnitude.

Figure 5 :

 5 Figure 5: dZ values computed with MATLAB for realistic values of Lint = 3 uH, Lres = 0.2 uH (Qres =40). The resonator coupling factor with reader loop is 1%. Rchip is varied from 5 to 50k Ohms (load modulation) and the coupling factor between the tag loop/coil and the resonator is from 1% to 5%.

Figure 6 :

 6 Figure 6: Loop/coil made with copper foil and evolution of the measured impedance in the presence (below 1cm distance) of card and small (circular, 1cm diameter) HF RFID SLI-X tags

Figure 7 :

 7 Figure 7: Evolution of the prototype and its measured impedance (VNA measurements), from single reader loop on the tube (top left) towards the addition of the resonator (top right) and its tuning (bottom left and right)

ACKNOWLEDGMENT

The authors thank the IUT de Cachan, from Université Paris-Sud, for providing the RFID equipment, and the students of the SYCO course (DUT GEII -S4) for their work.