extfieldsofstudy:
Computer Science
Mathematics

text:
Detection and Combining Techniques for Asynchronous Random Access with Time Diversity

Asynchronous random access (RA) protocols are particularly attractive for their simplicity and avoidance of tight synchronization requirements. Recent enhancements have shown that the use of successive interference cancellation (SIC) can largely boost the performance of these schemes. A further step forward in the performance can be attained when diversity combining techniques are applied. In order to enable combining, the detection and association of the packets to their transmitters has to be done prior decoding. We present a solution to this problem, that articulates into two phases. Non-coherent softcorrelation as well as interference-aware soft-correlation are used for packet detection. We evaluate the detection capabilities of both solutions via numerical simulations. We also evaluate numerically the spectral efficiency achieved by the proposed approach, highlighting its benefits.

I. INTRODUCTION
Sharing efficiently the resources among users that are required to access a common medium is of utmost importance in today's systems where bandwidth is scarce. Random access (RA) was proposed first [1], [2] to allow users to share a common medium without coordination. Recent advances in RA show that high efficiency can be achieved [3]- [6]. In these solutions, the transmitters send multiple copies of their packets (called replicas). Each replica contains information about the position of all its copies within a time slotted frame. At the receiver side, via successive interference cancellation (SIC), potential collisions are resolved taking advantage of the replicas position information. In [7] it has been shown that joint decoding on the collided packets can be attempted, resorting to multiuser detection (MUD) techniques. The authors of [8], [9] elaborate the concept of frameless slotted scheme, i.e. the duration of a frame is not a-priori fixed but the contention ends when the throughput is maximized. Further evolutions of RA include the extension to multiple receiver scenarios [10] and to all-to-all broadcast transmission [11]. Identification of replicas for slot synchronous RA schemes has been addressed in the works [12], [13], where a simple autocorrelation method has been adopted for identifying replicas of the same user.
Most of these schemes, although less complex at the transmitter side with respect to orthogonal schemes, still require synchronization at time slot level. It was recently observed that time synchronicity can be abandoned while keeping similar protocol operations. A first attempt in this direction has been done with the contention resolution ALOHA (CRA) protocol [14]. As in its slotted counterpart, contention resolution diversity slotted ALOHA (CRDSA) [3], the transmitters send replicas of their packets. However, while in CRDSA the replica transmission need to comply with a slotted frame structure, in CRA the slot alignment is abandoned. The replicas are transmitted with arbitrary delays within a window of fixed duration, and the relative delay among replicas is signaled in the replicas headers. The receiver seeks for decodable packets. Every time it is successful, the decoded packet is re-encoded, re-modulated and removed from all positions in the received signal, thanks to the position information stored in the replica header. Interference cancellation possibly allows further packets to be decoded. A similar scheme to CRA is proposed by the authors in [15], where the virtual frame (VF) concept is introduced. Users are synchronized to their local VF and are allowed to send their replicas only in discrete positions within the VF. The VFs of different users are asynchronous.
An evolution of CRA called enhanced contention resolution ALOHA (ECRA) has been presented first in [16]. Combining techniques are exploited in order to boost the performance. At the receiver, after SIC is carried out in a similar way as in CRA, the received signal samples associated with the replicas that cannot be decoded are combined and a new decoding attempt is performed. Selection combining (SC), equal gain combining (EGC) and maximal-ratio combining (MRC) can be used as combining technique. As shown in [16], remarkable gains can be obtained. The main drawback of ECRA is the requirement of perfect knowledge of the replicas position prior to decoding. A possible solution presented in [17] is to replicate this information in both header and trailer. Error protection can also be added increasing the probability of retrieving the replicas position information even in presence of collisions, but although viable, this solution increases the overhead.
In this paper with propose an alternative solution to the problem of localizing the replicas position that does not need any reserved field in the header.
The rest of the paper is organized as follows. Section II reviews the ECRA protocol and its features. In Section III we present the system model, the two phase detection technique and we derive the interference-aware soft-correlation detection rule. Section IV investigates ECRA adopting the derived detection techniques via Monte Carlo simulations and is followed by the conclusions in Section V. Collision Interference free Step 1 Step 2 Step 3 Step 4 Fig. 1. Example of collision pattern at the receiver in ECRA, and of the corresponding SIC steps. During the first step, user 3 second replica -the only one free from interference -is decoded and the information content as well as the pointer to its replica are retrieved. Users 1 and 4 replicas are now free from interference. In the second step second replica of user 1 can be decoded. Its interference contribution together with the one of its twin can be now removed from the received signal and first replica of user 2 is now freed from interference. In step 3, user 2 replicas can be decoded and removed from the received signal. Finally in step 4 user 4 replicas are decoded and removed from the received signal.

II. ENHANCED CONTENTION RESOLUTION ALOHA
We review next the ECRA [16] access protocol. For the sake of simplicity, in the following we assume each user attempting the transmission of one packet only. At the transmitter side each user sends 2 (or more) replicas of its packet within its local VF of duration T f seconds. We recall here that the concept of VF has been first introduced in [15] and was not present in the first version of ECRA [16]. The delay between replicas of the same user is chosen at random. An example of a possible received medium access control (MAC) signal is shown in Figure 1.
At the receiver side, the SIC procedure starts looking for decodable packets. In our example, the first to be found is the second replica of user 3. Once correctly decoded, all replica positions of the decoded user are retrieved from the pointer field in the header. The packet is re-encoded, re-modulated and his waveform is removed from all the identified positions. In this way, the interference caused on the second replica of user 1 is removed and this replica can be successfully decoded. Similarly, we are able to decode the packets of users 1 to 4, while users 5 and 6 cannot be decoded.
User 5 and 6 have both their replicas colliding with each other and SIC alone cannot resolve the collision, as emphasized in Figure 2. The approach proposed in [16] would use in this example, SC combining for choosing the interferencefree samples from the replicas of user 6, creating an enhanced observation of user 6 packet. On it, decoding is attempted and if successful, its interference contribution is removed from the received signal. This would allow the recovery of user 5 too.
Other combining techniques, such MRC and EGC can also be applied, leading to remarkable gains in terms of throughput as shown in [18]. There, it has been shown that ECRA with MRC is able to reach up to 1.8 b/s/Hz. A main challenge in the implementation of combining techniques is the need of performing the detection of the replicas and the identification of the user which they belong to, prior to decoding. A way to achieve this is to exploit the pointer field of the replicas, as proposed in [17], i.e. by • Duplicating the pointer field in the header and trailer of a replica; • Protecting the pointer field with a specific low rate forward error correction (FEC) code. Although viable, both options imply an increase in the protocol overhead, which can be particularly critical in applications where the message length is short. In the next Section, we propose a novel approach that allows detection and localization of replicas avoiding any protocol overhead.

III. SYSTEM MODEL
Each user arranges his transmission within a VF of duration T f seconds. Virtual frames are asynchronous among users. Each VF is divided in N s slots of duration ∆T , so that T f = N s ∆T . Users transmit d replicas of duration T p seconds within the VF. Each replica is transmitted over n p consecutive slots within the VF and we have that a replica duration is a multiple of the slot duration, T p = n p ∆T . Each replica is composed by n s modulated symbols and the symbol duration is T s . We have nT s = n p ∆T = T p . Each replica is transmitted starting from a slot index chosen uniformly at random in [0, N s − n p − 1], rejecting starting slot indexes which lead to self-interference among replicas of a user's packet.
We assume an infinite user population generating traffic following a Poisson process of intensity G. The channel load 1 G is measured in packet arrivals per packet duration or per T p seconds. In contrast to CRDSA [3], CRA [14] and the first version of ECRA [16], no pointer field is required in the header for localizing the replicas position. The first section of each replica is a sync word composed by n sw binary symbols s = (s 0 , ..., s nsw−1 ) common to all users, with The sync word is then appended to the BPSK modulated data part and sent through an additive white gaussian noise (AWGN) channel. The focus of this work is on satellite communication links where AWGN is a typical channel model extensively used. Extensions to other channel models that include fading are out of scope for the present contribution, although being a valuable future research direction. We assume the data part to carry the actual information and the redundancy introduced by a forward error correction code.
We will assume perfect power control, so that all packets are received with the same power. For a generic user's signal both frequency offset f and epoch ǫ are modeled as uniform The frequency offset and epoch are common to a user's packet, while they are independent across users. The random phase offset is uniformly distributed between 0 and 2π, i.e. ϕ ∼ U [0; 2π), and it is assumed to independent replica by replica.
Under the assumption that f max T s ≪ 1, the received signal y(t) after matched filtering can be approximated as 0 is the user u delay w.r.t. the common reference time; • f (u) is the frequency offset for user u; • ϕ (u,r) is the phase offset for the r-th replica of user u's packet. The signal for the u-th user x (u) is given by Here, a (u) i is the symbol sequence forming user u's packet and g(t) = F −1 {CR(f )} is the pulse shape, where CR(f ) is the frequency response of the raised cosine filter. The noise n(t) is given by n(t) ν(t) * h(t), being ν(t) a white Gaussian process with single-sided power spectral density N 0 and h(t) the matched filter (MF) impulse response,

A. Detection and Decoding
At the receiver side, the incoming signal y(t) is sampled and input to the frame start detector. The receiver will operate with a sliding window, similarly to [15], [19]. The decoder starts operating on the first W samples, with W the designed window size. First it detects candidate replicas. Then, for the candidate replicas, a subsequent processing is performed with the scope of matching the replicas transmitted by the same user. For the matched replicas, combining is performed and decoding via the channel decoder is attempted. The channel decoder is assumed to be capable of identifying unrecoverable errors with high probability. 2 If decoding is successful, SIC is performed: the interference contribution of all the replicas of the decoded packet is removed from the received signal. Once no more packets can be decoded within the window, the receiver window is shifted forward by ∆W samples and the procedure starts again. We detail now how candidate replicas are detected and matched. The procedure is performed in two phases, that we dub detection phase and matching phase.

1) Detection Phase:
In the first phase we use the noncoherent soft-correlation metric [20] for identifying candidates replicas (see Figure 4(a)). Within a receiver window, a threshold-based test is applied to each of the W − n sw sequences of n sw consecutive samples (referred in the following as test intervals) to detect the presence of a sync word. We denote in the following y = (y 0 , ..., y nsw−1 ) the sequence of n sw samples on which the threshold test is applied. Here, we are implicitly assuming that the epoch is estimated prior to frame synchronization. Under the hypothesis that the test interval is actually aligned to a sync word, the epoch estimation can be reliably performed using pilot-aided 3 techniques mutated from code synchronization algorithms used in spread-spectrum communications (see e.g. [21] and   references therein). If the test window is not aligned with the sync word of any user, we assume the epoch estimator returning a random sampling offset, uniformly-distributed in (0, T s ]. For each test interval, similarly to [20], the frame synchronizer has to decide among two hypothesis, i.e. H 0 : y = z + n H 1 : y = s e jϕ (u,r) + z + n where the first hypothesis refers to the case of no sync word, while the second one refers to the case of sync word present. Here n = (n 0 , ..., n sw−1 ) are samples of a discrete white Gaussian process with n i ∼ CN (0, 2σ 2 ) and z is the interference contribution over the n sw observed samples. We adopt the threshold test Where decision D 1 corresponds to hypothesis H 1 and decision D 0 corresponds to hypothesis H 0 . The threshold λ is the discriminant between the two decision regions. We call S = {τ 1 , τ 2 , ...} the set of candidate replica starting positions, i.e. the set containing the positions within the receiver window for which the test provided by (1) outputs D 1 . The set of candidate replica positions is the outcome of the first phase.
2) Replica Matching Phase: The second phase works as follows. Let us consider the first candidate replica identified in the first phase. We denote its starting position as τ 1 , with τ 1 ∈ S. We are interested now in finding a subset S 1 ⊆ S containing the initial positions of bursts that are likely replicas of the (hypothetical) burst starting in position τ 1 . To do so, we define the following compatibility criterion: Definition 1 (Compatibility Criterion). A start position τ i ∈ S is said to be compatible with τ 1 iff for some positive integer k, τ 1 < τ i < W T s − ∆T .
The set S 1 is hence formally defined as The subset S 1 contains the starting positions that are compatible (given the VF structure) with τ 1 , i.e., their associated burst are likely replicas of the burst starting at position τ 1 . Denote next y (i) = (y (i) 0 , ..., y (i) ns−1 ) as the n s samples of the received signal starting with sample in position τ i within the window. For each τ i ∈ S 1 , we compute the non-coherent correlation We order the Λ 1,i in descending order and we mark the first d − 1 as replicas of the same user.
On these replicas we apply combining techniques as selection combining (SC), MRC or EGC. If decoding is successful, all the replicas are removed from the received signal. Accordingly, S is updated by removing the starting positions of the cancelled replicas. The process is iterated until S is empty, or if decoding fails for all remaining candidates in S.
In the next Subsection, a refinement of the detection rule, when an estimate of the interference power is available at the receiver is presented.

B. Hypothesis Testing, Interference-Aware Rule
We derive here an advanced correlation rule, namedΛ (1) , which takes into consideration the presence of interference. To do so, we resort to a Gaussian approximation of the interference contribution. We hence model the interference term ν i as ν i ∼ CN (0, σ 2 I ). Furthermore, we assume σ 2 I to be constant for the entire test interval. The joint noise plus interference contribution is given by n ′ i = ν i + n i , so that n ′ i ∼ CN (0, σ 2 I + 2σ 2 ). The approximate likelihood ratio test (LRT) is then obtained by evaluating, For the H 0 hypothesis we can write For the H 1 hypothesis we can write We defineỹ i = y i / σ 2 I + 2σ 2 . Averaging (7) over ϕ we find, Substituting equations (8) and (6) in the expression of equation (5) we get Taking the natural logarithm of both sides we can write where λ = ln (λ ′ ). Making the use of the approximation ln(I 0 (x)) ∼ = |x|−ln 2π|x| ∼ = |x| [20], we can further rework equation (9) as With respect to the non-coherent soft-correlation rule of equation (1), we can observe that in (10) the correlation term is followed by a correction term that depends on the sync word length and on the interference level. See Figure 4(b) for the block diagram of the presented synchronizer. Observe that the interference-aware rule requires an estimate of the interference power.

IV. NUMERICAL RESULTS
In this section we present numerical results for the proposed approach. We first compare the two non-coherent softcorrelation rules presented in Sections III-A and III-B in terms of receiver operating characteristics (ROC). In the second part we show the performance of the ECRA receiver in terms of probability of correct detection of the replicas and probability of correct combining of replicas from the same user.

A. ROC Comparison
The performance of the two correlation rules Λ (1) andΛ (1) that can be adopted in the detection phase of the receiver operations are compared via Monte Carlo simulations. The comparison is done in terms of ROC. The false alarm probability P F is defined as P F = Pr{Λ > λ|H 0 }. The detection probability P D is defined as P D = Pr{Λ > λ|H 1 }. We assume f max = 0.01/T s . The aggregate signal is then summed with Gaussian noise. The selected E s /N 0 is E s /N 0 = 10 dB. A sync word of 32 bits of hexadecimal representation {1ACF F C1D} has been adopted, which results in n sw = 32 symbols.
Results for channel traffic values G = {0.5, 1.0, 1.5} are presented in Figure 5. As we can expect, the knowledge on the interference level exploited in the ruleΛ (1) leads to better ROC performance, regardless form the channel traffic conditions. Nevertheless, the gain compared to the non-coherent correlation rule Λ (1) is rather limited. In general, both rules show good performance, with P D > 0.99 for P F > 0.02 in the worst case (channel traffic G = 1.5) and for Λ (1) .

B. ECRA Detection and Replicas Coupling Performance
We present here the results for the detection and correct combining probabilities. We focus in the particular setting where d = 2 (i.e., users transmit 2 replicas of their packets). The detection probability P D has been defined in the previous subsection. We define the correct combining probability P CC as the probability that two replicas of a burst are correctly selected for combining after the two-phase procedure. Obviously, P CC ≤ P 2 D , i.e., a necessary condition for correct combination is the actual detection of the sync words associated with the two replicas, during the first phase. We select a fixed threshold λ * equal for all the channel traffic values and we use the noncoherent soft-correlation rule Λ (1) . The threshold λ * has been selected through numerical simulations. We show the results in Figure 6, for a signal-to-noise ratio (SNR) of E s /N 0 = 10 dB. The discretization interval equals to one physical layer packet duration, i.e. ∆T = T p . Each packet is composed by a sync word of n sw = 32 symbols (as the one already presented) and a total of n s = 1000 BPSK antipodal modulated symbols (including the sync word symbols), the VF duration as well as the window duration W T s are 100 times the packet duration, Observe that the detection probability remains above 95% for all the channel traffic G values, up to G = 1.5. The non-coherent soft-correlation rule Λ (1) is particularly robust to variations in the channel traffic, since the presented results are obtained for a single threshold value λ * which has been     Fig. 6. Detection probability P D for a fixed threshold λ * independent from the channel traffic using Λ (1) and correct combining probability P CC with Λ (2) .

C. Spectral Efficiency
We compare the simulation results in terms of both spectral efficiency achieved by ECRA with MRC, after the two-phase detection process described in Section III-A. The proposed two phase detection technique is compared against the idealized case in which all replicas positions are known to the receiver prior to decoding. We select ∆T = T p and again the window duration is T f = W T s = 100T p . Perfect channel state information (CSI) at the receiver is assumed for enabling MRC.
As before, we use the non-coherent soft-correlation rule Λ (1) and a fixed threshold has been selected and kept constant, regardless the channel load G. All replicas are received with equal power E S /N 0 = 2 dB. A capacity achieving code adopting a Gaussian codebook with rate R = 1 is assumed, so that if the mutual information at the output of the combiner exceeds the rate R, then the packet is considered to be successfully decoded. Further refinements of the decoding model can be adopted following a realistic packet loss rate (PLR) performance of a specific code for example. Nonetheless, for the present work such a model is sufficient to show the goodness of the detection and identification approach. The maximum number of SIC iterations is set to 10. SIC is assumed ideal. That is, if the position of both replicas of one user is known at the receiver, MRC is applied and if the packet can be decoded its interference contribution is completely removed from the received signal applying SIC.
In Figure 7, the spectral efficiency results for the proposed two phase detection and combining technique (called ECRA-MRC in the legend) and the ideal ECRA-MRC where all the replica positions is known at the receiver are presented. The proposed technique is close to the performance of the ideal case. The maximum spectral efficiency exceeds 1.4 b/s/Hz, which is only 8% less than the maximum spectral efficiency of the ideal case.

V. CONCLUSION
In this work we presented a solution for localizing candidate replicas and combine them prior to decoding, in the asynchronous random access protocol ECRA, enabling the exploitation of combining techniques as MRC. A two phase approach is proposed. First candidate replicas are identified using the known sync word. Non-coherent soft-correlation is adopted as baseline metric and an interference-aware softcorrelation rule is derived. The latter can be adopted when the interference power on the sync word can be estimated. Numerical results have shown that already the simple noncoherent soft-correlation metric is sufficient to guarantee the detection of most the replicas. Up to 99.5% of replicas can be detected for channel load up to G = 1. In the second phase, the entire candidate replica signal is exploited to compute the noncoherent soft-correlation metric against the other candidates.


text:
Multi-Objective Beamforming for Energy-Efficient SWIPT Systems

In this paper, we study the resource allocation algorithm design for energy-efficient simultaneous wireless information and power transfer (SWIPT) systems. The considered system comprises a transmitter, an information receiver, and multiple energy harvesting receivers equipped with multiple antennas. We propose a multi-objective optimization framework to study the trade-off between the maximization of the energy efficiency of information transmission and the maximization of wireless power transfer efficiency. The proposed problem formulation takes into account the per antenna circuit power consumption of the transmitter and the imperfect channel state information of the energy harvesting receivers. The adopted non-convex multi-objective optimization problem is transformed into an equivalent rank-constrained semidefinite program (SDP) and optimally solved by SDP relaxation. Numerical results unveil an interesting trade-off between the considered conflicting system design objectives and reveal the benefits of multiple transmit antennas for improving system energy efficiency.

I. INTRODUCTION
In recent years, the development of wireless communication networks worldwide has triggered an exponential growth in the number of wireless devices and sensors for applications such as e-health and environmental monitoring. The related tremendous increase in the number of transmitter(s) and receiver(s) has also led to a huge demand for energy and a better energy management. Hence, energy efficient system designs, which adopt energy efficiency (bit-per-Joule) as the performance metric, have been recently proposed [1]- [4]. In [2], energy-efficient power allocation schemes were proposed for cognitive radio systems. In [3], energy-efficient link adaptation was investigated for the maximization of energy efficiency in frequency-selective channels. In [4], the authors proposed a resource allocation algorithm design for energy-efficient communication in multicarrier communication systems with hybrid energy harvesting base stations. Although energyefficient resource allocation algorithm designs for traditional communication networks have been studied in the literature, mobile receivers are often powered by batteries with limited energy storage which remain the system performance bottlenecks in perpetuating the lifetime of wireless networks.
Energy harvesting (EH) based communication system design is a viable solution for prolonging the lifetime of energylimited devices. Conventional natural sources, such as wind, solar, and biomass, have been exploited as energy sources This work was supported in part by the AvH Professorship Program of the Alexander von Humboldt Foundation.
for fixed-location, outdoor transmitters. However, these natural energy sources are often location and weather dependent and may not be suitable for mobile receivers. On the other hand, wireless power transfer (WPT) via electromagnetic waves in radio frequency (RF) enables a comparatively controllable energy harvesting for mobile receivers. In fact, recent progress in the development of RF-EH circuitries has made RF-EH practical for low-power consumption devices [5]- [7], e.g. wireless sensors. Besides, WPT enables the dual use of the information carrier for simultaneous wireless information and power transfer (SWIPT) [8]- [10]. Different from traditional wireless communication systems, where data rate and energy efficiency are the most fundamental system performance metrics, in SWIPT systems, the wireless energy transfer efficiency is an equally important QoS metric. Thus, the design of resource allocation algorithms should take into account the emerging need for energy transfer efficiency. In [11], the authors studied the fundamental rate-energy trade-off region for optimal information beamforming. In [12], power allocation, user scheduling, and subcarrier allocation were jointly designed to enable an energy-efficient multicarrier SWIPT system. In [13], the authors proposed the use of large scale multiple-antenna systems for improving energy efficiency of SWIPT. Although energy-efficient data communication design and energy-efficient WPT have already been studied individually, the trade-off between these two system design paradigms is still unclear for SWIPT systems. In particular, these two design goals may conflict with each other but both are desirable to system designer. However, the single-objective resource allocation algorithms proposed in [2]- [4], [8]- [11], [13] may no longer be applicable in energy-efficient SWIPT networks.
In this paper, we address the above issues. To this end, we formulate the resource allocation algorithm design as a multi-objective optimization problem which strikes a balance between the maximization of energy efficiency of information transmission and the maximization of WPT efficiency. The resulting non-convex optimization problem is solved optimally by semidefinite programming (SDP) relaxation. Simulation results illustrate the trade-off between the conflicting system design objectives.

II. SYSTEM MODEL
In this section, we first define the adopted notations and then present the channel model for energy-efficient SWIPT Transmitter I n f o r m a t io n Energy signal E n e r g y s ig n a l Information receiver Energy harvesting receiver 1 Energy harvesting receiver 2  The distribution of a circularly symmetric complex Gaussian (CSCG) vector with mean vector x and covariance matrix Σ is denoted by CN (x, Σ), and ∼ means "distributed as". E{·} denotes statistical expectation. · and · F denote the Euclidean norm and the Frobenius norm of a vector/matrix, respectively. Re(·) extracts the real part of a complex-valued input.

B. Channel Model
We focus on a downlink SWIPT system. The system consists of a transmitter, a single-antenna information receiver (IR), and multiple energy harvesting receivers (ERs). The transmitter is equipped with N T antennas and each ER is equipped with N R receiving antennas. We assume that the ERs are roaming wireless terminals from other communication systems searching for additional power supply in the RF. The transmission is divided into time slots. In each time slot, the transmitter sends a precoded information signal and an energy signal simultaneously to facilitate information transmission to the IR and power transfer to the ERs, cf. Figure 1. The transmit signal is given by where s ∈ C is the information-bearing symbol with E |s| 2 = 1 and w I ∈ C NT×1 is the corresponding information beamforming vector. w E ∈ C NT×1 is the energy signal facilitating energy transfer to the ERs. The energy signal w E is a deterministic pseudo-random sequence with zero mean and covariance matrix W E . Since w E is generated at the transmitter by a pseudo-random sequence generator with a predefined seed, the energy signal is known to the IR. Thus, the interference caused by the energy signal can be completely cancelled at the IR. We assume a narrow-band slow fading channel between the transmitter and receivers. Then, the received signals at the IR and ER j are expressed as where h ∈ C NT×1 is the channel vector between the transmitter and the IR, and G j ∈ C NT×NR is the channel matrix between the transmitter and ER j. Variables h and G j capture the joint effect of multipath fading and path loss. n I ∈ C and n E j ∈ C NR×1 are additive white Gaussian noises (AWGNs) at the IR and ER j, respectively, and are distributed as CN (0, σ 2 I ) and CN (0, σ 2 E I NR ).

III. RESOURCE ALLOCATION ALGORITHM DESIGN
In this section, we present the adopted performance metrics and the problem formulation.

A. Achievable Rate, Harvested Energy, and Energy Efficiency
The achievable rate (bit-per-second) at the IR is given by where B is the system bandwidth and H = hh H . We note that the interference caused by the energy signal, i.e., Tr(w H E Hw E ), is removed from the IR via successive interference cancellation before the IR decodes the desired information since the energy signal w E is known to the receiver. On the other hand, both the information signal and the energy signal can act as RF energy sources for the ER due to the broadcast nature of wireless channels. As a result, the total harvested energy 1 at ER j is given by and η j is the energy conversion efficiency of ER j which is a constant with 0 ≤ η j ≤ 1 and models the energy loss of the process of converting the received RF energy to electrical energy for storage. We ignore the thermal noise at the receiving antenna for energy harvesting as it is relatively small compared to the received signal power. Energy efficiency is a fundamental system performance metric in modern communication networks. To design a resource allocation algorithm for energy-efficient communication, the total power consumption has to be included in the optimization objective function. Thus, we model the power dissipation (Joule-per-second) in the system as where P B = N T P ant + P c .
0 < ξ ≤ 1 is the constant power amplifier efficiency. The first term in (6) is the total power consumption in the power amplifier. N T P ant in (7) accounts for the dynamic circuit power consumption which is proportional to the number of transmit antennas. P ant denotes the power dissipation at each transmit antenna, including the dissipation in the transmit filter, mixer, frequency synthesizer, digital-to-analog converter (DAC), etc. P c denotes the fixed circuit power consumption for baseband signal processing. Therefore, the achievable rate energy efficiency (AR-EE) and the energy transfer energy efficiency (ET-EE) of the considered system are defined as respectively, where P harv j is given in (5).

B. Channel State Information (CSI)
In this paper, we focus on a Time Division Duplex (TDD) communication system with slowly time-varying channels. At the beginning of each time slot, handshaking is performed between the transmitter and the IR. As a result, the downlink CSI of the IR can be obtained by measuring the uplink training sequences embedded in the handshaking signals. Thus, we assume that the transmitter-to-IR fading gain, h, can be estimated perfectly at the transmitter. On the other hand, the ERs may not directly interact with the transmitter. Besides, the ERs may be silent for long periods of time. As a result, the CSI of the ERs can be obtained only occasionally at the transmitter when the ERs communicate with the transmitter. Hence, the CSI for the ERs may be outdated when the transmitter performs resource allocation. We adopt a deterministic model [14], [15] to characterize the impact of the CSI imperfection for resource allocation design. The CSI of the link between the transmitter and ER j is modeled as where G j ∈ C NT×NR is the matrix CSI estimate of the channel of ER j that is available at the transmitter. ∆G j represents the unknown channel uncertainty and the continuous set Ψ j in (11) defines a continuous space spanned by all possible channel uncertainties. Constant ε j represents the maximum value of the norm of the CSI estimation error matrix ∆G j for ER j.

A. Problem Formulation
In SWIPT systems, AR-EE maximization and ET-EE maximization are both desirable system design objectives. In this section, we first propose two problem formulations for singleobjective system design for SWIPT. Each single-objective problem describes one important aspect of the system design. Then, we consider both system design objectives jointly via the multi-objective problem formulation.
The first system design objective is the maximization of AR-EE without the consideration of energy harvesting. The corresponding optimization problem is formulated 2 as Problem 1: AR-EE Maximization: subject to C1 : w I 2 + Tr(W E ) ≤ P max , C2 : W E 0 P max in constraint C1 denotes the maximum transmit power budget. In addition, covariance matrix W E is a positive semidefinite Hermitian matrix as indicated by constraint C2.
The second system design objective is the maximization of the ET-EE. The corresponding problem formulation is given as subject to C1, C2.
For the sake of notational simplicity, we denote the objective functions in the above problems as F n , n = 1, 2. In practice, these two system design objectives are both desirable from the system operator perspective. However, it is expected that there is a non-trivial trade-off between these objectives. In order to meet these conflicting system design objectives systematically and simultaneously, we adopt the weighted Tchebycheff method for the multi-objective optimization [16] which can provide the complete Pareto optimal set by varying predefined preference parameters. To this end, we incorporate the two individual system design objectives into a multiobjective optimization problem (MOOP), which is formulated as where F * i is the optimal objective value with respect to Problem i. ω i is a weight imposed on objective function i subject to 0 ≤ ω i ≤ 1 and i ω i = 1, which indicates the preference of the system designer for the i-th objective function over the others. In the extreme case, when ω i = 1 and ω n = 0, ∀n = i, Problem 3 is equivalent to single-objective optimization problem i.

V. OPTIMIZATION SOLUTIONS
It can be observed that the objective functions of Problems 1-3 are non-convex functions. In general, there is no wellknown systematical approach for solving non-convex optimization problems. In order to obtain a tractable solution, we first transform the non-convex objective functions using the Charnes-Cooper transformation. Then, we use semidefinite programming relaxation (SDR) to obtain the resource allocation solution for the reformulated problem.
We first reformulate the aforementioned three optimization problems by defining a set of new optimization variables: subject to C1 − C6, where τ is an auxiliary optimization variable. Proposition 1: The Problems 4-6 are equivalent transformations of the original Problems 1-3, respectively.
Proof: The transformation is based on Charnes-Cooper transformation. Due to the space limitation, we refer to [16] for proof for a similar problem.
We note that Problem 6 is a generalization of Problems 4 and 5. If Problem 6 can be solved optimally by an algorithm, then the algorithm can also be used to solve Problems 4 and 5. Thus, we focus on the method for solving 3 Problem 6. It is evident that Problem 6 is non-convex due to the rankone beamforming matrix constraint C3 : Rank(W I ) ≤ 1. Besides, constraint C6 involves infinitely many constraints due to the continuous uncertainty set Ψ j . Next, we introduce a Lemma which allows us to transform constraint C6 into a finite number of linear matrix inequalities (LMIs) constraints. where provided that there exists a pointx such that f k (x) < 0. Now, we apply Lemma 1 to constraint C6. In particular, we define g j = vec( G j ), ∆g j = vec(∆G j ), W I = I NR ⊗ W I , and W E = I NR ⊗W E . By exploiting the fact that ∆G j if and only if there exists a ρ j ≥ 0 such that the following LMIs constraint holds: where U gj = I NRNT , g j . The new constraint C6 is not only an affine function with respect to the optimization variables, but also involves only a finite number of constraints. Then, we apply the SDP relaxation by removing constraint C3 from Problem 6. As a result, the SDP relaxed problem is given by which is a convex SDP problem and can be solved by numerical convex program solvers such as CVX [18]. In particular, if the obtained solution W * I of the SDP relaxed problem satisfies constraint C3, i.e., Rank(W * I ) ≤ 1, then it is the optimal solution. Now, we study the tightness of the SDP relaxation by the following theorem.
Theorem 1: Assuming that the channels, i.e., h and G j , are statistically independent and Problem 7 is feasible, the optimal beamforming matrix of Problem 7 is a rank-one matrix with probability one, i.e., Rank(W * I ) ≤ 1. Besides, for ω 1 > 0, the optimal energy signal is w * E = 0. Proof: Please refer to the Appendix. Therefore, the adopted SDP relaxation is tight. Besides, whenever AR-EE is considered, i.e., ω 1 > 0, no dedicated energy beam is needed. In fact, the optimal information beam, w I , serves as a dual purpose carrier for maximization of the energy efficiency of information transmission and WPT simultaneously. Furthermore, Problems 1-2 can be solved by SDP relaxation as solving Problem 7.

VI. RESULTS
In this section, we present simulation results to demonstrate the system performance of multi-objective SWIPT system design. The simulation parameters are summarized in Table I. The IR and J ERs are located 100 meters and 10 meters from the transmitter. In particular, the ERs are near the transmitter with line-of-sight communication channels to facilitate energy harvesting. Each ER is equipped with N R = 2 antennas for facilitating EH. We assume that the noise powers at each antenna of the IR and the ERs are identical, i.e., σ 2 I = σ 2 E = σ 2 . In the sequel, we define the normalized maximum channel estimation error of ER j as δ 2 j = ε 2 j Gj 2 F with δ 2 a = δ 2 b = 0.05, ∀a, b ∈ {1, . . . , J}. All simulation results are obtained by averaging the system performance over different multipath channel realizations. Figure 2 depicts the trade-off region for the average ET-EE and the average AR-EE achieved by the proposed optimal  scheme for different numbers of ERs. The maximum transmit power is set to P max = 40 dBm. The trade-off region in Figure  2 is obtained by solving Problem 7 via varying the values of 0 ≤ λ p ≤ 1, ∀p ∈ {1, 2}, uniformly for a step size of 0.01 such that p λ p = 1. It can be observed that the ET-EE is a monotonically decreasing function with respect to the AR-EE. The result indicates that AR-EE maximization and ET-EE maximization are conflicting system design objectives in general. In other words, a resource allocation algorithm maximizing the AR-EE cannot maximize the ET-EE simultaneously in the considered system. Besides, the trade-off region is enlarged for an increasing number of ERs. This is due to the fact that a larger portion of the radiated power can be harvested when there are more ERs in the system since more receivers participate in the energy harvesting process. For comparison, we also plot the trade-off region of a baseline power allocation scheme in Figure 2. For the baseline scheme, the covariance matrix of the energy signal W E is set to zero. Then, maximum ratio transmission (MRT) with respect to the IR is adopted for the information beamforming matrix W I . In other words, the beamforming direction of matrix W I is fixed. Then, we optimize the power of W I subject to the constraints in Problem 7. It can be observed that the baseline scheme achieves a significantly smaller trade-off region compared to the proposed optimal scheme. As a matter of fact, the degrees of freedom of the beamforming matrix W I are jointly optimized in our proposed optimal scheme via utilizing the CSI of all receivers. On the contrary, the information beamformer in the baseline scheme is restricted to the range space of the IR. Although the baseline scheme is optimal when AR-EE is the only system design objective, the information beamformer cannot be steered towards the direction of the ERs. Thus, compared to the proposed optimal scheme, the baseline scheme is less efficient when ET-EE is considered. Figures 3 and 4 illustrate the average AR-EE and the average ET-EE versus the total transmit power budget P max , respectively, for J = 10 ERs. The results in Figures 3 and 4 are obtained by solving Problem 7 with {ω 1 = 1, ω 2 = 0} and {ω 1 = 0, ω 2 = 1}, respectively. It can be observed from Figure 3 that the AR-EE of the proposed optimal scheme increases with respect to P max monotonically and reaches an upper limit where the EE gain due to a higher value of P max vanishes. This result indicates that once the maximum AR-EE is achieved by transmitting a sufficiently large power, any additional increase in the transmitted power will incur a loss in EE which is prevented by the optimal algorithm. On the other hand, it can be seen from Figure 4 that the average ET-EE increases slowly in the low transmit power regime but increases rapidly in the high transmit power regime. This is because for a small transmit power, the ET-EE is dominated by the fixed circuit power consumption, P B , leading to a slow increasing rate of ET-EE with respect to the transmit power. As the transmit power budget increases, the transmit power consumption in the RF becomes significant and the ET-EE becomes more sensitive to increases in transmit power budget, cf. (9). On the other hand, the number of transmit antennas N T affects the AR-EE and the ET-EE differently.
In fact, the maximum AR-EE does not necessarily increase with the number of transmit antennas when the per-antenna power consumption in considered, cf. Figure 3. This is because the AR scales logarithmically with respect to the number of transmit antennas. However, the AR gain due to extra transmit antennas is not sufficient to compensate the total increased energy cost since the circuit power consumption increases linearly with respect to N T . Thus, adopting exceedingly large numbers of transmit antennas may not be a viable solution for information transmission. In contrast, the maximum ET-EE increases with N T as shown in Figure 4. This is due to the fact that the ET-EE function in (9) is a quasi-linear function with respect to both W I and W E . Thus, a large number of transmit antennas is beneficial if ET-EE is the only system design objective.

VII. CONCLUSIONS
In this paper, we studied the resource allocation algorithm design for energy-efficient SWIPT networks. The algorithm design was formulated as a non-convex MOOP employing the weighted Tchebycheff method. The proposed problem aimed at the joint maximization of the energy efficiency of information transmission and WPT simultaneously. Besides, the imperfectness of the CSI of the ERs was also taken into account for designing a robust resource allocation algorithm. The proposed MOOP was solved optimally by SDP relaxation. Simulation results not only reveal the trade-off between the studied conflicting systems design objectives, but also shed some light on the use of multiple transmit antennas for improving system energy efficiency.
APPENDIX-PROOF OF THEOREM 1 Since Problem 7 satisfies Slater's constraint qualification and is jointly convex with respect to the optimization variables, strong duality holds. Thus, solving the dual problem is equivalent to solving the primal problem. Therefore, Theorem 1 can be proved by analyzing the dual problem of Problem 7. To this end, we define the Lagrangian function L = τ + α Tr(W I + W E ) − θP max − δθ


extfieldsofstudy:
Medicine
Computer Science
Psychology

text:
Brainhack: a collaborative workshop for the open neuroscience community

Brainhack events offer a novel workshop format with participant-generated content that caters to the rapidly growing open neuroscience community. Including components from hackathons and unconferences, as well as parallel educational sessions, Brainhack fosters novel collaborations around the interests of its attendees. Here we provide an overview of its structure, past events, and example projects. Additionally, we outline current innovations such as regional events and post-conference publications. Through introducing Brainhack to the wider neuroscience community, we hope to provide a unique conference format that promotes the features of collaborative, open science.

at unconferences is dynamically determined by attendees, while hackathons feature unstructured time during which teams of participants collaborate intensively on various projects. These meeting formats have enabled rapid advances in computing technologies since the late 1990s, but they have yet to be widely adopted in academic research. Now in their fourth year, international and regional Brainhack events bring together brain enthusiasts from a variety of backgrounds to build relationships, learn from one another, and collaborate on projects related to the neurosciences. Unlike traditional hackathons that tend to focus on computer programming, projects at Brainhacks can be completed using a much broader array of methods. Time is set aside for periodic unconference sessions whose content is determined on-site by the participants. The unconference sessions can feature different styles of presentations, including but not limited to: updates on ongoing projects, ideas that could seed future collaborations, panel discussions, or tutorials. In consideration of the ever expanding interest in the tools of open science, Brainhack has developed an educational component that runs in parallel with the hacking sessions in order to introduce the basic tools of open collaboration. This combined model encourages active participation and interaction between attendees, while also maximizing the topical relevance of the more formally presented content (see Fig. 1).
There is no ideal background, skill set, or experience level required for Brainhack attendees. Fully translating neuroscience data to knowledge requires expertise that spans biology, computer science, engineering, informatics, mathematics, neuroanatomy, philosophy, physics, psychiatry, psychology, statistics, art, and many others. The goal of a Brainhack event is to facilitate the crosspollination of ideas and knowledge across these various disciplines and communities to accelerate the development of a richer understanding of the brain. In addition to sharing data and tools, attendees can contribute in a variety of ways. Philosophical debates about the meanings of cognition, coordinated efforts to manually segment brain images from different species, curating neuroscience literature, or helping others to understand the subtleties of diagnosing a developmental disorder are all examples of valuable contributions that have emerged at Brainhacks in the past (for further examples, see Table 1).

Hackathons based on collaboration, not competition
The hackathon format gained prominence in the technology sector by providing a meeting model that targets specific project goals during intense time-limited collaborations. The competitive aspect of the traditional hackathon, while catalyzing rapid advances toward specific technology ends, is contrary to the founding principle of Brainhack, which is to encourage open, crossinstitutional, and inter-disciplinary collaboration. Rather than subdividing attendees into competitive factions, Brainhack attendees are encouraged to work together in collaborative teams to solve problems of their choosing. In this way, rather than obtaining many solutions to a single problem, we aim to produce various solutions to many problems. Most importantly, we encourage the building of new relationships that continue to be productive beyond the end of the event.

Brainhack projects
Rather than focusing on a specific problem or toolset, which is common in traditional hackathons, attendees are encouraged to generate their own project ideas around which they can self-assemble into teams. As a consequence, some projects may receive more limited interest, whereas one might attract the majority of attendees. In this way, the projects developed at Brainhacks are elected by participation, rather than being pre-specified by the event organizers. This model is more conducive to collaboration than the alternative of organizing a hackathon around a challenge or competition. There are many different models between these two extremes; we are currently working on building thematic Brainhack events that bring researchers together to focus on specific questions of neuroscientific interest.
To date, projects completed at Brainhack events have included students interacting with more experienced researchers to learn about a new data modality or analysis method, inter-disciplinary collaborations to improve data collection, the development or optimization of data analysis tools, and testing hypotheses about brain structure using openly shared data. See Table 1 for selected examples of projects that have previously been initiated at Brainhack events, and www.brainhack.org [1] for a full list of projects.

Event organization
Brainhack events span 1 to 4 days and include a variety of content to make them both accessible and fruitful for a wide range of attendees. The format of the events is not fixed, but varies based on the needs determined by the local organizing committee. At past events, the schedule has included various components aiming to quickly integrate the attendees and generate an environment conducive to productive collaboration. We have found the Table 1 Selected examples of Brainhack projects • A child psychiatrist and a 3D video artist initiated a collaboration at the 2012 Brainhack to develop a movie to be shown to participants during resting-state fMRI scans to reduce head motion in hyperkinetic populations [5,6].
• A collaboration started at the 2012 Brainhack performed an analysis to identify differences in cortical thickness and structural covariance between individuals with autism spectrum disorder and neurotypical controls [24].
• A project team at Brainhack 2013 amassed a dataset of 14,781 structural MRI scans to estimate the distribution of brain sizes across individuals for optimizing scan acquisition parameters [25].
• The development team of LORIS, an open source database system for neuroimaging and phenotypic data, have repeatedly used Brainhack as an opportunity to meet and collaborate on new features [26].
• An early version of the Daydreaming app [27], an Android application for real-time assessment of users' mind-wandering, was developed at Brainhack 2013.
• The Clubs of Science [28] project, founded at Brainhack MTL 2015, has built a web-based visualization of the social web underlying neuroimaging research.
• The linkRbrain [29] tool for integrating and querying neuroimaging data with activation peaks from the literature and gene expression data was partially developed and first tested at Brainhack 2013 in Paris [30].
Further projects can be found at www.brainhack.org [1] activity categories included in Table 2 to be valuable elements of creating a productive environment.

Practical considerations
To enable broad attendance by researchers, regardless of their resources, fees are kept as low as possible and many of the events are free. This has been made possible through generous financial support and meeting space provided by hosting institutions and corporate sponsors. When possible, lunch and dinner have been provided to encourage continued interaction between attendees throughout the duration of the event. We have also Table 2 Programming components of Brainhack events • Meet and greet: Brainhack events begin with a welcome to the hosting facility by the local organizing committee, along with a briefing about the event schedule, procedures, or other information that might be important for the attendees.
• Ice breaker: Interaction between attendees is the key to a successful Brainhack event. The ice breaker is an activity to introduce attendees and their interests to one another. One strategy that has been successful is for each attendee to give their name, their institution, and three words that describe their interests. Such ice breakers could take various forms, including a speed-dating paradigm in which attendees pair up for a brief conversation, after which attendees swap partners, and this continues until every pair has met.
• Ignite talks: Brainhack's equivalent of keynote sessions, Ignite talks are inspirational talks on the big picture of open brain science that are intended to invigorate the audience for the day ahead. These are ideally brief (a 10-minute presentation followed by 10 minutes of questions), of general relevance, and are provided by a luminary in the field.
• Hacking: The core of Brainhack is 'open hacking' sessions during which attendees collaborate together on projects of their choosing. Attendees who have specific project ideas or data that they would like to explore are encouraged to advertise their project at www.brainhack.org [1] prior to the event. At the opening of the Brainhack event, typically after the ice breaker, attendees pitch their ideas and afterwards mingle with others to organize a project team. Teams work together throughout the remainder of Brainhack and are given the opportunity to present their progress during the wrap-up session at the end of the event.
• Brainhacking 101: The educational track enables less experienced attendees to learn basic software and data analysis skills. Occurring in parallel so as not to interfere with the ongoing hacking sessions, this track begins with 'Installfest' sessions during which attendees receive help installing any required software. Afterwards there are several hands-on tutorials that cover topics like: using Github, Python programming, using Python to load and visualize neuroimaging data, and performing meta-analyses of scientific literature. The resources for educational sessions are made freely available online (e.g., [31]).
• Unconference: Sessions for attendees to present their research or other topics of current interest. Immediately prior to these sessions, the agenda is determined on-site. Attendees who are willing to present add their name to a sign-up sheet and in the event that there are more interested presenters than time, the group is polled to determine which presentations are given time or to extend the amount of time allotted. Instead of unconference sessions, some sites have incorporated 'data blitzes,' consisting of a pre-organized session where attendees have the opportunity to present their research. Brainhack Miami has had success with this model and has secured funding to award monetary prizes to the best presentations.
• Wrap-up and feedback: Brainhack events typically finish with a wrap-up session during which project teams describe the progress that they made or give a demo of their results in a brief (∼1-2-minute) presentation. Afterwards, the local organizers lead a discussion about what worked well with the event, and how it could be improved in the future.

Regional events
Brainhack began as international events that drew attendees from all over the world to work together in open collaboration. Early interest in transferring this model to the local level was tempered by fears that local events would not be able to provide enough content to attract attendees. Brainhack Eastern Daylight Time (Brainhack EDT) was developed to address these concerns by organizing several simultaneous events that are virtually linked to enable the real-time sharing of content across sites. Events were limited to sites in time zones within 1 hour of EDT to simplify scheduling. This innovative distributed model drew 242 attendees across seven sites located in three different countries, and has since been followed by Brainhack Americas, which extended this model to the entirety of North, South, and Central America (see Tables 3 and 4).

Conclusions
Brainhack promotes open neuroscience by offering unique opportunities to researchers from a variety of backgrounds to build collaborations and develop new skills. It is particularly valuable to junior researchers and those from developing economies who have limited opportunities to interact with peers and senior scientists outside their home institutions. Despite these successes, Brainhack is a nascent concept for scientific meetings, and there remains substantial room for innovation. To this end, we are excited to announce the Brainhack Proceedings and Brainhack Thematic Series for providing researchers with tangible scientific credit for their contributions to Brainhack events and open science. For the future, we will be working to expand the global audience of Brainhack by hosting events throughout Asia.


Adaptive Work-Efficient Connected Components on the GPU

This report presents an adaptive work-efficient approach for implementing the Connected Components algorithm on GPUs. The results show a considerable increase in performance (up to 6.8$\times$) over current state-of-the-art solutions.

I. INTRODUCTION
Finding the Connected Components (CC) of a graph is a fundamental algorithm, often used as a pre-processing step for other graph algorithms. Parallel CC algorithms exhibit finegrain parallelization opportunities, as have been explored in the literature [1], [2]. In particular, two parallel approaches are prominently used for CC, namely Label Propagation and "Hook-Shortcut". Soman et. al. [3] implemented a parallel GPU variant of Hook-Shortcut, showing that GPUs are beneficial for CC computation despite the inherent irregularity of the algorithm.
This report presents an adaptive variant of Hook-Shortcut CC, focusing on the two core operations of the algorithm and implementing them in a device-centric approach. By doing so, we improve the work-efficiency of the algorithm, increase its performance, and reduce CPU-GPU round-trips to minimum. We demonstrate that the algorithm is highly efficient on a wide variety of graph types.

II. EXISTING APPROACHES
In graph theory, a connected component of an undirected graph G = {V, E} is defined as a subset of vertices ν ⊆ V , in which each two vertices are connected via an edge path. Computing the connected components {ν i } N i=1 of a graph, where N is the number of components, is thus defined by assigning a unique component ID C i to each of the vertices v ∈ ν i . In practice, the component ID is determined by an index of some representative vertex in ν.
Straightforward sequential solutions for CC are based on graph traversal, propagating the unique component ID, called label, via neighboring vertices until the entire component is labeled. Label propagation can be parallelized by initializing each vertex with a unique ID, disseminating vertex labels in parallel according to a global rule, such as minimal/maximal vertex index.
Shiloach and Vishkin [2] introduced a different parallel algorithm for CC, based on two operations called "Hooking" and "Shortcutting". Rather than propagating values through the graph, this variant transforms the input graph into trees, iteratively connecting those trees and reducing their depth. The algorithm converges when the graph is converted into a forest of depth-one trees, each representing a different component. Specifically, this variant defines two core procedures: (i) Hook, which, given an edge (u, v) ∈ E, attempts to connect the two trees that u and v belong to (if not already connected); and (ii) Shortcut, which replaces the parent of each tree vertex with its grand-parent, reducing the tree depth. The process alternates between the Hook and Shortcut operations until convergence.
Soman et al. [3] propose a variant of the Hook-Shortcut CC, where the Shortcut operation is replaced by Compression, which consecutively performs Shortcutting (called "Jump" operations in this variant) until each tree is reduced into a single-level "star" (depth-one tree). Hence, the algorithm iteratively alternates between Hook and Compress operations, reducing the number of iterations until convergence.
procedure ConnectedComponents(G(V, E)): 1: let π : π(vertex) ← vertex 2: repeat 3: for all e in E do in parallel 4: Hook(e, π) until Jump performs no change in π 11: until Hook performs no change in π 12: return π The corresponding Hook-Compress GPU kernels are presented in Fig. 2. As seen in the figure, although parallel Hook calls may perform concurrent writes to the same memory locations (Hook procedure, line 3), its implementation is atomic-free (i.e., does not use atomic operations). This is supported by the overall algorithm logic, which assures every Hook operation will eventually succeed before converging. The Hook procedure also uses a global high-to-low hooking rule for avoiding possible tree cycles.

III. WORK-EFFICIENT CONNECTED COMPONENTS
This section proposes a work-efficient approach for implementing Hook-Compress CC on the GPU. This approach redefines the two core operations of the algorithm, Hook and Compress, moving the control-flow to the GPU. We show that the variant is scalable, minimizes CPU-GPU communication, adaptive with respect to graph properties (e.g., average degree), and converges faster than existing approaches. Below, we describe the algorithm and elaborate on its work-efficiency and adaptability properties.

A. Work-Efficiency
The proposed CC algorithm is composed of two GPU kernels: Multi-Jump and Atomic-Hook.
In Multi-Jump, instead of performing multiple single-level Jump operations, we fuse an entire Compress phase into a single kernel. This kernel, shown in the bottom portion of Fig. 3, replaces lines 6-10 in Fig. 1 with a single parallel invocation.
We note two important optimizations in our Multi-Jump procedure: (i) the procedure constantly writes an updated value to π(v) even though one final write would suffice; and (ii), the parallel kernel is scheduled with partial order, starting from the top-most vertices in the component trees (lower indices) and going down to the leaves (higher indices). The two optimizations decrease the number of iterations each device-thread must perform, hence reducing thread-divergence introduced by the irregular while loop.
The second kernel is an Atomic-Hook procedure. This kernel uses atomic Compare-And-Swap (CAS) operations to traverse the component trees until a hook operation can device procedure AtomicHook(edge(u, v), π): H ← max{π(u), π(v)}

3:
L ← min{π(u), π(v)} 4: lock π(H) (atomic CAS) 5: if π(H) = H : then 6: π(H) ← L 1: while π(π(v)) = π(v) do 2: π(v) ← π(π(v)) 3: end while The Atomic-Hook procedure, depicted in the top portion of Fig. 3, begins by finding the parents of both (u, v) and determining their high-low order for global consensus (lines 1-3). Then, with an atomic CAS operation, π(H) is locked and checked; if H is the root of a tree, then it can be used for hooking the entire tree without overriding any other pointer, hence the procedure assigns L to be its parent and exits successfully (lines 5-7). Otherwise, the procedure recursively considers (π(H), L) to be the new (u, v) edge to connect (lines 9-10) at the next iteration. The recursive logic continues until successfully acquiring a root (line 5), or if discovering the two component trees are already connected (line 1).

B. Adaptability
Using the above two kernels, one could possibly solve CC with only two kernel calls: a single Atomic-Hook (guaranteeing component tree connectivity), followed by a Multi-Jump operation for compressing all component trees into "stars".
Performing a single Atomic-Hook may be more efficient than several non-atomic Hooks, but it eliminates the ability to perform constant Compress operations between each Hook round, which may degrade the overall performance. For enabling intermediate tree compressions we introduce segmentation, i.e. splitting the input graph into distinct edgelist segments and performing Compress operations between atomic segment Hooks. Below we describe a heuristic method for selecting the optimal number of edge-list segments to split into.
We highlight two observations, both related to the ratio between the number of edges |E|, and the number of vertices |V | (i.e. the average vertex degree) of the input graph.
First, atomic operations within the Atomic-Hook procedure are performed on the component trees workspace, which has |V | memory size. As a result, the true parallelism of atomic operations is bounded by the number of vertices, creating a growing atomic contention as average degree increases.
Second, unlike the Hook step, which has O(|E|) complexity, the Compress step is performed over vertices and hence has O(|V |) complexity. As the number of edges grows compared to the number of vertices, the cost of Compress operations becomes a minor percentage of the overall run-time cost, and performing more intermediate compressions may be beneficial.
Based on these observations, we suggest a heuristic method to determine the best segmentation, is to split the graph into 2|E|/|V | segments (the average degree), effectively performing Atomic-Hook operations over edge-list segments of size ≈ |V | each followed by a full O(|V |) Compress.
This way, Hook operations are always performed over segments proportional to the |V | memory workspace, reducing atomic contention. Each such segment Hook, is followed by a Compress operation, flattening all component trees and minimizing atomic operations for the next segment Hook. As average degree increases, more Compress operations will be performed, but their O(|V |) cost becomes minor compared to the dominating O(|E|) complexity of the overall algorithm. for all e in E i do in parallel 6: AtomicHook(e, π)   Table I. Fig. 5 compares the baseline Soman [3] code with our approach, gradually adding Multi-Jump, Atomic-Hook, and Adaptability. The figure shows that the adaptive version consistently outperforms the other versions. Observe that Multi-Jump improves performance in all graph types, whereas Atomic-Hook exhibits improvement when adapting the number of segments based on the given input graph. For the best segmentation, we achieve consistent speedups over the current state-of-the-art [3] ranging from 4.15× to 6.76×. Also note that for graphs like kron-logn21 and soc-livejournal [7], [6] which have a relatively high average degree, the effect of the Multi-Jump optimization is minor (1.02× and 1.14× respectively) because it only affects Compress operations, which have a small O(|V |) complexity in these cases.  6 shows the segmentation speedup over the Atomic-Hook baseline (single segment) for various graphs on the average degree spectrum. For all tested graphs, the figure shows that the speedup is maximal when segmenting into 2|E|/|V | segments. These results coincide with the explanation behind the adaptive heuristic, as described in Section III-B.