# Nanocrystalline FeCr alloys synthesised by severe plastic deformation - a
potential material for exchange bias and enhanced magnetostriction

Lukas Weissitsch
Erich Schmid Institute of Materials Science, Austrian Academy of Sciences
Jahnstraße 12, 8700 Leoben, Austria
<EMAIL_ADDRESS>&Stefan Wurster
Erich Schmid Institute of Materials Science, Austrian Academy of Sciences
Jahnstraße 12, 8700 Leoben, Austria
&Alexander Paulischin
Erich Schmid Institute of Materials Science, Austrian Academy of Sciences
Jahnstraße 12, 8700 Leoben, Austria
&Martin Stückler
Erich Schmid Institute of Materials Science, Austrian Academy of Sciences
Jahnstraße 12, 8700 Leoben, Austria
&Reinhard Pippan
Erich Schmid Institute of Materials Science, Austrian Academy of Sciences
Jahnstraße 12, 8700 Leoben, Austria &Andrea Bachmaier
Erich Schmid Institute of Materials Science, Austrian Academy of Sciences
Jahnstraße 12, 8700 Leoben, Austria

###### Abstract

This work gives insights into processing and characterisation of bulk
nanocrystalline FeCr materials. The investigated FeCr alloys, consisting of
30, 50 and 70 at.% ferromagnetic Fe and remaining anti-ferromagnetic Cr, are
processed by arc melting and subsequent severe plastic deformation by high
pressure torsion. The physical similarities between elemental Fe and Cr in
combination with the nanocrystalline structure of the as-deformed alloys,
necessitates advanced characterisation techniques for the as-deformed state:
In-situ annealing synchrotron X-ray diffraction measurements as well as
electron microscopy experiments are linked to magnetostrictive measurements
and reveal a single phase microstructure. Surprisingly, the nanocrystalline
FeCr alloys remain supersaturated solid solutions upon annealing above 500 ∘C,
meaning a decomposition in a FeCr nanocomposite is suppressed. For the chosen
annealing conditions grain growth is faster than decomposition and enhanced
magnetostrictive values are found compared to materials in the as-deformed
state.

Keywords: magnetostriction; miscibility gap; severe plastic deformation;
nanocrystalline; FeCr alloy; supersaturated solid solution

##  1 Introduction

Tuning material properties by forming single phase alloys and varying chemical
composition is often impeded by the existence of large miscibility gaps at the
thermodynamic equilibrium of binary phase diagrams. Notwithstanding the
difficulties in fabrication, there is a strong interest in such metastable
phases created materials as they offer the opportunity to tune and enhance
physical properties. For quite some time, it is known to overcome these
processing limits by techniques such as vapour deposition [1], mechanical
alloying (MA) [2] or severe plastic deformation (SPD) generating metastable
phases [3, 4, 5]. The formation of supersaturated solid solutions by MA or SPD
is accompanied by a high defect density and decreased microstructural sizes.
This evinces characterisation challenges for the binary nanocrystalline FeCr
system: Due to the same crystal structure and similar lattice parameters of
elemental Fe and Cr, it is difficult to distinguish whether finely dispersed
elemental nanocrystalline grains or a (supersaturated) solid solution is
present [2]. Possible characterisation methods are magnetic measurements.
Apart from the tuneability of the saturation magnetostriction of
heterostructures [6, 7] Bormio-Nunes et. al [8] reported an increasing
saturation magnetostriction value for FeCr solid solutions. The aforementioned
heterostructure of coexisting ferromagnetic Fe and anti-ferromagnetic Cr
phases could give rise to an effect referred to as exchange bias.

The exchange bias features a shifted hysteresis loop, which originates from an
unidirectional anisotropy created at the interface of the two types of
magnetic materials. This occurs, when the ferro-antiferromagnetic phase
boundary is cooled through the Néel temperature (TN) while a magnetic field is
applied [9]. Since magnetic exchange interactions appear on the nanometre-
scale and the exchange bias effect is related to the phase boundaries, this
effect is typically observed in microstructures obtained by well controllable
synthetization techniques. Thin films or core-shell nanostructures [10] are
well controllable during processing and therefore, such material systems allow
a proper investigation of fundamental physical properties [11]. On the other
hand, it is difficult to investigate the same effects in bulk materials [12],
exhibiting dimensions of several millimetres or larger. The bottleneck
nowadays is the synthesis of a nanostructured bulk material exhibiting a high
homogeneity therefore, enabling an up-scaling of materials with improved
magnetic properties. Notwithstanding the above, the amount of interfaces is
thought to directly influence the intensity of the magnetic effect, which
makes magnetic nanostructured bulk materials necessary [9, 13].

Severe plastic deformation by high-pressure torsion (HPT) is a promising
approach to overcome processing limitations, for above mentioned miscibility
gaps of binary material systems [5] and furthermore a method of choice to
tailor magnetic properties [14, 15]. One big advantage of materials processed
by HPT is the sample size, as they exhibit bulk dimensions up to several
centimetres [16, 17]. The principal goal of this work is the production of a
bulk material consisting of alternating interfaces of elemental ferromagnetic
Fe and anti-ferromagnetic Cr. Therefore, the synthesis of a nanocrystalline
supersaturated solid solution of FeCr by HPT is aimed for a subsequent
annealing treatment. The increased total grain boundary area of
nanocrystalline materials is expected to favour a decomposition [18] of the
FeCr solid solution in separated phases and therefore, into a nanostructured
composite. A following magnetic field cooling is meant to induce an exchange
bias, as already reported for HPT-compacted Co-NiO heterostructures [19].
However, processing and the characterization of nanocrystalline HPT deformed
FeCr-alloys prior to field cooling is challenging. Evading processing
limitations due to a pronounced miscibility gap in the binary phase diagram
[20], we already reported an enormous increase in hardness during HPT-
deformation but also on the successful processing and formation of a
homogeneous nanocrystalline microstructure for a wide range of chemical
compositions [3]. In this work we clarify, if these materials exhibit a
supersaturated solid solution or if they are already in a nanocrystalline two
phase state. We report on in-situ high-energy X-ray diffraction (HEXRD)
experiments where a solid solution without any decomposition upon annealing is
presumed and verify these results by magnetostrictive measurements.

##  2 Experimental

Binary alloys consisting of nominal 30, 50 and 70 at.% Fe and 70, 50, and 30
at.% Cr, respectively, were processed by arc melting and subsequent HPT-
deformation. As starting materials, conventional flakes (Fe: 99.99+% $<$ 10
mm, Cr: 99.995% 1-25 mm, both from HMW Hauner GmbH & Co. KG) were used. All
materials were stored and handled in an Ar-filled glovebox to protect the high
purity materials against contamination.

For arc-melting (AM/0.5 device, Edmund Buehler GmbH), a Ti-gettered high
purity Ar atmosphere was used. To ensure chemical homogeneity the ingots were
turned around and remelted at least five times. From arc melted ingots,
cylinders with 8 mm diameter were prepared by electrical discharge machining
and cut in discs with 1 mm thickness, which were subsequently deformed by HPT.
A detailed description of the used HPT setup can be found in Ref. [21]. A
nominal pressure of 7.5 GPa with a rotational frequency of 0.6 min-1 was used
for the deformation process and 21 to 25 revolutions are applied
(corresponding to a shear strain $\upgamma$ of $\sim$450 at radius r = 3 mm
[22]). To avoid an increase of the processing temperature during deformation,
high pressure air cooling was conducted.

After deformation, the sample is cut for further investigations and all
measurements were performed at a radius $r\geqslant$ 2 mm. Respective
orientations are explained in detail in Reference [15]. Scanning electron
microscopy (SEM; LEO 1525, Carl Zeiss Microscopy GmbH) images were made in
tangential HPT-disc orientation in backscattered electron (BSE) detection
mode. The chemical composition was determined by energy dispersive X-ray
spectroscopy (EDX; XFlash 6$\mid$60 device, Bruker), using the Bruker software
package Esprit 2.2. The grain size of selected samples was quantitatively
evaluated by Transmission Kikuchi Diffraction (TKD) and electron backscatter
diffraction (EBSD) measurements using a Bruker e--FlashFS detector. Hardness
measurements (Micromet 5104, Buehler) were performed in tangential direction
on the polished sample along the diameter in steps of $\Delta~{}r$ = 0.25 mm
and were averaged for a radius 2 mm $\leqslant~{}r\leqslant$ 3.5 mm. For
annealing experiments, quarters or half discs of as-deformed samples were
exposed to 300 ∘C, 400 ∘C and 500 ∘C for 1 h in a conventional furnace. The
samples were wrapped in a protective foil before heat treatment and were
quenched with ethanol after the annealing process.

For magnetostrictive measurements, an electromagnet (Type B-E 30, Bruker) with
conical poles (diameter 176 mm), providing a constant air gap (50 mm) and a
maximal field of 2.25 T, was used. Within the air gap, the sample was placed
into an encapsulating sample chamber, protecting from rapid temperature
changes. The magnetostriction was measured using strain gauges (HBM,
1-LY11-0.6/120) applied with glue Z70 from HBM. As a reference a piece of W, a
very low magnetostrictive material is measured at the same time with a strain
gauge of the same batch. According to [23], the magnetostriction of W can be
expected to be below 0.005 ppm in a magnetic field of 2 T. The strain gauge on
the sample and the reference were placed parallel and on top of each other
within the sample chamber and conducted to a half-Wheatstone bridge. The
signal of the strain gauges was processed with an amplifier (HBM-Quantumx
MX410). Additionally, the constancy of the temperature was confirmed by a
temperature measurement within the sample holder and the applied magnetic
field was recorded, using a Hall-probe (Model 475 DSP, Lakeshore).

Synchrotron high-energy X-ray diffraction (HEXRD) experiments were carried out
at the beamline P21.2 at PETRA III (DESY, Hamburg, Germany). The specimens
were measured in transmission mode, while the spot size was set to 200 x 200
$\upmu$m2 and a photon energy of 60 keV was used. In-situ annealing HEXRD
experiments were performed using the following sequence: Heating to 520 ∘C,
holding the temperature for 1 h and cooling. A Varex XRD 4343 flat panel
detector captured diffraction patterns every 5 seconds. The experimental setup
was realised by a heating microscope stage (THMS600 Linkam, Tadworth, United
Kingdom), which was adapted to place the samples inside an Ar-flushed chamber
to suppress the formation of oxides. The custom made chamber is designed to
minimize the interaction of the beam with the furnace and allowed the
diffracted beam to exit the probe chamber while the temperature was measured
via a thermocouple. The temperature was calibrated by measuring a Cu sample
with the same settings and comparing the changing lattice parameter during
thermal expansion. For data processing, the pyFAI package [24] and further
analysing the Matlab voigt package [25] was used.

##  3 Results

###  3.1 Characterisation of the microstructure

Figure 1: BSE images of the microstructure of HPT-deformed FeCr alloys. The Fe
content increases from the top to the bottom row. The first column shows the
microstructure of as-deformed samples. The next columns depict microstructural
changes with increasing annealing temperatures (300 ∘C, 400 ∘C and 500 ∘C,
respectively). Averaged Vickers-hardness values are depicted in the
corresponding images as insets. The magnification is the same in all images.

The microstructures of room temperature (RT) HPT-deformed samples at r = 3 mm
with different chemical compositions are shown in Figure 1. The Fe-content
increases from the top to bottom row. In the first column, BSE images of as-
deformed FeCr alloys are depicted. Nanocrystalline and homogeneously deformed
microstructures are visible. To quantify the grain sizes of the alloys in the
as-deformed state, TKD is conducted exemplarily for one composition
(Fe50Cr50). In Figure 2 a) a crystal orientation map revealed by TKD is shown.
Recording several images and interpolating the data of 1256 grains with a log-
normal distribution reveal a median grain size of 101 nm (standard deviation =
86 nm; $\sigma$ = 0.579, $\mu$ = -2.288). Please note the different scale bar
in Figure 2 b), where an EBSD scan of the same alloy after annealing for 1h at
500 ∘C is shown. The obtained median grain size is 307 nm (1456 grains,
standard deviation = 160 nm; $\sigma$ = 0.449, $\mu$ = -1.180).

Figure 2: Crystal orientation maps of a) an as-deformed Fe50Cr50 alloy
recorded in axial HPT disc direction by TKD. b) EBSD scan of an Fe50Cr50 alloy
after annealing at 500 ∘C (1 h) measured in tangential direction but showing
the crystal orientation in axial direction. Note the different scale bars.

Results from Vickers-hardness testing are indicated as insets within each SEM
micrograph (Figure 1). The hardness measurements along the radius, display a
constant hardness, which indicates a homogeneously deformed state (denoted as
’as-deformed’ in the following). To induce decomposition, the as-deformed
samples are annealed for one hour at different temperatures (Figure 1). The
change in the microstructure strongly depends on the chemical composition.
Nearly no change in the SEM images for the Cr-rich sample (Fe30Cr70), depicted
in the first row of Figure 1, is visible, when annealing up to 400 ∘C.
However, the hardness increases, which is a common feature for nanocrystalline
materials [26, 27, 28], is covered. A slightly increased grain size,
accompanied by a hardness decrease, is seen for the 500 ∘C annealed sample.
The medium composition sample (Fe50Cr50) shows a slight contrast difference in
SEM images between the as-deformed and 300 ∘C annealed state. The
microstructure remains almost constant even when annealing at 400 ∘C (shown in
the 3rd column) until a significant grain growth is found for 500 ∘C
annealing. The hardness increases upon annealing at 300 ∘C but decreases for
higher annealing temperatures. Differences for every state are visible for the
Fe rich sample (Fe70Cr30). At 300 ∘C, a slight grain growth is observed
together with an increased hardness. Samples annealed at 400 ∘C and 500 ∘C
exhibit a significant increase in grain size as well as a decrease of
microhardness below the as-deformed state. Summarized, at intermediate
temperatures the hardness increases for all chemical compositions, whereby the
hardness peaks at higher temperatures for higher Cr content. Further,
microstructural changes and grain growth are stronger pronounced for FeCr
alloys containing a higher amount of Fe.

Figure 3: HEXRD synchrotron data of the [110] peak for HPT-deformed FeCr
samples consisting of a) Fe30Cr70, b) Fe50Cr50 and c) Fe70Cr30. Vertical lines
denote theoretical reference lines for Fe (solid, turquoise) and Cr (dashed,
brown). The selected patterns belong to in-situ annealing experiments and are
extracted at different times and temperatures, visualized d) by arrows in an
exemplarily temperature profile.

Laboratory XRD measurements of the as-deformed and annealed states (not shown)
revealed broad peaks. They can either result from the formation of a
supersaturated state or be due to the nanocrystalline state of individual Fe
and Cr phases present in the as-deformed condition. Additionally, a co-
existence of both configurations is conceivable. Thus, to clarify this point
and to further investigate the decomposition of FeCr alloys, which are
possibly in a non-equilibrium state, in-situ annealing experiments using
synchrotron XRD are performed. Due to the high brilliance of the beamline
[29], it was expected to resolve individual peaks for Fe or Cr phases, if
existent, and to precisely determine the phases of the as-deformed and
annealed states. Representatively, the most intense peak [110] of selected
patterns of the in-situ experiment is shown in Figure 3 for all three FeCr
compositions. The vertical lines indicate reference values for elemental Fe
(solid, turquoise) and Cr (dashed, brown) calculated with lattice constants
from [30]. The depicted peaks correspond to different temperatures during the
in-situ experiment. The top peaks (red) belong to the beginning of the
experiment, representing the as-deformed state. A significant peak broadening
is again found for all three chemical compositions. According to Vegard’s law
[31] the peak positions follow the trend of the chemical composition
determined by EDX measurements of the FeCr alloys. The Fe contents obtained
with EDX for the alloys depicted in Figure 3 a), b) and c) are 27.8$\pm$3.3
at.%, 48.7$\pm$0.8 at.% and 69.1$\pm$1.1 at.%, respectively. The blue peaks
are recorded at the end of the heating process, when a constant temperature of
520 ∘C is reached. Because of the thermal expansion of the lattice, a shift
towards a lower reciprocal lattice vector is visible. This is accompanied with
a significantly sharpened shape of the peak, indicating larger crystallite
sizes and/or diminishing crystallographic defects. The green peak is recorded
after 1 hour of isothermal annealing at 520 ∘C and shows almost no deviations
with respect to the blue pattern. The purple peaks at the bottom correspond to
an ex-situ measurement after the sample cooled down to room temperature and
can be directly compared with the red line.

Figure 4: [110] peak position for every pattern during heating (full symbols)
and cooling (empty symbols) for HPT-deformed FeCr alloys determined by fitting
the HEXRD in-situ data by a single Voigt profile. The cooling is not covered
experimentally for the Fe50Cr50 alloy.

The recorded patterns are fitted with Voigt-profiles. It should be mentioned,
that for every peak one single Voigt-profile is used. Although fitting by one
peak implies a solid solution, an overlapping of two peaks corresponding to
separated Fe and Cr is also possible. Unfortunately, the similar crystal
structures (both body centred cubic) and the similar lattice parameters with
less than 0.02 Å difference (see Reference [30]) lead to very similar peaks
for Fe and Cr, with almost no differences. Despite the high brilliance of the
synchrotron, a pattern fitting with two separated Voigt-peaks is ambiguous.
The shape, as well as intensity and position, strongly depend on the fitting
starting parameters which allows no clear statement. Nevertheless, using a
single Voigt peak profile, a high accordance is reached for the calculated
pattern with respect to the measured HEXRD data. The peak positions as a
function of the temperature process while heating (filled symbols) and cooling
(empty symbols) is shown in Figure 4. A difference between these processes is
recognised: While the peak position changes as expected linearly during
cooling, the heating curve is bended. Although, no peak separation is found
(see Figure 3) the varying slope indicates a superposition of processes, quite
likely dedicated to a change in the microstructure.

Therefore, the Voigt-profiles are analysed in more detail, as it is a
convolution of a Gauss and Cauchy (Lorentz) distribution. The full width half
maximum (FWHM) of a single Voigt profile can be parsed into the breadths of
its Cauchy and Gaussian components. Keijser et al. [32] linked the individual
peak widths to size (Cauchy) and strain (Gauss) broadening, respectively. The
evolution of peak widths for each composition is shown in the supplementary
data file. It is found that the Cauchy peak width decreases with increasing
annealing temperature. In contrast, the Gaussian FWHM barely changes until 250
∘C before it decays rapidly with increasing temperature, indicating a
reduction in internal stresses. The contribution of internal stresses to the
overall peak width observed in Figure 3 is strongly reduced, when the heating
process is finished. The remaining narrowing of the peaks, upon further
isothermal annealing, originates from size effects and therefore grain growth,
which is in accordance with SEM investigations of the annealed FeCr alloys
(see Figure 1). After annealing for one hour at 520 ∘C, no peak separation or
broadening of the peak due to a superposition of its elemental Fe and Cr peaks
is found. We therefore conclude, that all FeCr alloys exhibit a
nanocrystalline, supersaturated solid solution state before and after the
annealing treatment. To decompose these alloys, higher annealing temperatures
are necessary.

###  3.2 Magnetostrictive measurements

In principle, 3d-elements like Fe exhibit a low magnetostrictive response [33]
but when alloyed with Al, Si, Ge or Ga an increased value was found [34]. This
is explained by the substitution of an Fe atom by a non-magnetic metal. The
magnetostriction of arc melted FeCr alloys without subsequent plastic
deformation was measured by Bormio-Nunes et al. [8]. They processed FeCr solid
solutions, with a Cr content between 5.3 and 30.7 at.% and found an increased
saturation magnetostriction compared to the magnetostriction of the pure
elements. Besides the interesting question, if a higher Cr content further
increases the magnetostriction, an enhanced value confirms our results from
Section 3.1, as the increased magnetostriction is only present in the FeCr
solid solution. Therefore, we conducted magnetostrictive measurements on all
FeCr alloys in the as-deformed state as well as in one annealed state.

Assuming a perfectly isotropic material, the magnetostriction measured
parallel and perpendicular to the applied magnetic field [35], follows
$\lambda_{\parallel}$ = -2 $\lambda_{\perp}$. The anisotropy of
magnetostrictive behaviour is further influenced by the crystal structure and
crystallographic directions. Therefore, the effective saturation
magnetostriction $\lambda_{s}$ for polycrystalline materials is usually
described by

$\lambda_{s}=\frac{2}{3}(\lambda_{\parallel}-\lambda_{\perp})$ (1)

According to equation 1 the magnetostrictive behaviour of as-deformed FeCr
alloys as a function of the applied magnetic field is shown in Figure 5. The
saturation value increases with increasing Fe content. At a maximal applied
field $\upmu_{0}H$ = 2.25 T the signal is close to 0 ppm for the as-deformed
Fe30Cr70 sample, whereas the samples consisting of Fe50Cr50 and Fe70Cr30 reach
8 ppm and 17 ppm, respectively. To give a comparison, the magnetostriction of
elemental Cr is very small ($\lambda_{s}^{nm}<$ 1 ppm) [36] and elemental Fe
exhibits a crystallographic anisotropic magnetostriction, which results in a
negative value $\lambda_{s}^{m}$ = -9.3 ppm according to equation 1 [35, 37].
Preliminary SQUID magnetometry measurements conducted on the Fe30Cr70 sample,
exclude a paramagnetic state at room temperature but indicate the presence of
superparamagnetic particles, possible existing within the high amount of grain
boundaries of the nanocrystalline material [38].

Figure 5: Effective magnetostriction as a function of applied magnetic field
for three FeCr alloy after HPT-deformation at RT.

Applying these values and using the $\frac{Fe}{Cr}$ volume fraction f, the
volumetrically weighted balance between a magnetostrictive $\lambda_{s}^{m}$
and a non-magnetostrictive $\lambda_{s}^{nm}$ component for the effective
saturation magnetisation $\lambda_{s}^{eff}$

$\lambda_{s}^{eff}=f\lambda_{s}^{m}+(1-f)\lambda_{s}^{nm}$ (2)

gives deeper insights into the Fe based nanocrystalline alloys [39].
Obviously, this approximation does not hold for our presented alloys as
equation 2 yields an even smaller quantity in $\lambda_{s}$. We can either
conclude on an existing solid solution or must assume other mechanisms giving
a large positive contribution to the measured magnetostriction. If we assume
separated phases, equation 2 does not consider contributions of surface spins
and grain boundaries. Nevertheless it is known, that both, surface- and bulk-
magnetoelastic coupling contribute to the magnetoelastic tensor [6], which is
further important for nanocrystalline materials [40]. To describe the
magnetostrictive behaviour of nanocrystalline materials, Slawska-Waniewska et
al. [41] expanded equation 2 to

$\lambda_{s}^{eff}=f\lambda_{s}^{m}+(1-f)\lambda_{s}^{nm}(f)+f\lambda_{s}^{s}\frac{S}{V}$
(3)

where $\lambda_{s}^{s}$ describes the interface contribution such as surface
spins to the effective saturation magnetostriction. $\frac{S}{V}$ is the
surface to volume fraction, which can be rewritten in $\frac{3}{R}$ for
spherical grains with an effective grain radius R. For the FeCr system only
the third term contribute with a positive value to $\lambda_{s}^{eff}$ keeping
in mind, that the measured $\lambda_{s}$ values for Fe50Cr50 and Fe70Cr30
presented in Figure 5 are positive. If the second term is neglected and the
measured values for $\lambda_{s}^{eff}$ as well as a grain size radius of 50
nm (median grain diameter obtained by TKD measurements - see Figure 2) are
used, we can estimate a value for $\lambda_{s}^{s}$. For the Fe70Cr30
composition a $\lambda_{s}^{s}\approx$ 400$\cdot$10-6 nm is necessary to fit
our measurements. Comparing $\lambda_{s}^{s}$ values for FeCr alloys to other
Fe based nanocrystalline materials, they differ by one (Fe30Cr70) or two
(Fe50Cr50 and Fe70Cr30) orders of magnitude [40, 41]. Therefore, surface spin
contributions to the effective saturation magnetostriction are not excluded
but cannot be the main contribution of the increased $\lambda_{s}^{eff}$ and
consequently, Fe and Cr have to be present in the form of a solid solution.

Hall et al. [42] used etched single crystals of FeCr and found an increasing
magnetostriction ($\lambda_{[100]}$ = 51.7 ppm) when alloying Fe with Cr up to
21.1 at.% for the crystallographic [100] direction. But they also describe a
concurrently decreased value for the [111] direction ($\lambda_{[111]}$ = -2.7
ppm), if compared to elemental Fe [43]. According to the relation

$\lambda_{s}^{eff}=\frac{1}{5}(2\lambda_{100}+3\lambda_{111})$ (4)

$\lambda_{s}^{eff}$ results in 19 ppm, which is in excellent agreement with
results on Fe70Cr30, keeping in mind that it is an HPT-deformed sample
exhibiting a nanocrystalline microstructure. Furthermore, comparable results
are found in the work of Bormio-Nunes et al. [8]. For the identical chemical
composition of Fe70Cr30, they reported $\lambda_{s}$ values between 23 ppm and
47 ppm depending on the measured side of their cubic samples.

Figure 6: Effective magnetostriction as a function of applied magnetic field
for three FeCr alloys, HPT deformed at RT and subsequently annealed at 500 ∘C
for 1 h.

The results of magnetostrictive measurements of annealed samples (500 ∘C for
1h) are shown in Figure 6. For all samples, the saturation magnetostriction
increases compared to as-deformed samples. The signal for the Fe30Cr70 sample
is slightly positive, the Fe50Cr50 and Fe70Cr30 samples reach 12 ppm and 23
ppm, respectively. The increased magnetostriction with respect to the as-
deformed state is thought to originate from a decreased number of crystal
defects and a possible reduction of residual stresses [44] and further,
analysis of EBSD scans (see Figure 2) revealed a slightly stronger texture for
the annealed sample, which could also enhance magnetostriction values [7, 45,
46]. Due to the large, positive values, a solid solution is still present for
all FeCr compositions but no further improvement of $\lambda_{s}^{eff}$ by an
increasing Cr content is found as motivated by Bormio-Nunes et al. [8].

During this work, we successfully produced nanocrystalline FeCr supersaturated
solid solutions over a broad chemical composition and clarified that the
alloys do not exhibit a two-phase structure in the nanocrystalline regime and
confirmed the existence of a solid solution. Astonishingly a demixing into
separated Fe and Cr phases was suppressed by a remarkable temperature
stability of the solid solution up to 520 ∘C. As the principle aim was to
decompose the microstructure into a nanocrystalline two-phase material,
enabling the formation of an exchange biased material, a more complex
annealing treatment and HPT-processing route has to be found, which is part of
ongoing studies. Beforehand, adding substitutional elements could stabilise
the microstructure even further and hinder grain growth. This could preserve
the nanocrystalline structure during annealing, while a decomposition takes
place.

##  4 Conclusion

Nanocrystalline FeCr alloys consisting of Fe30Cr70, Fe50Cr50 and Fe70Cr30 are
processed by HPT-deformation at RT. Upon annealing, the microstructure starts
to coarsen between 300 ∘C and 500 ∘C, which is stronger pronounced for higher
Fe contents. All materials investigated exhibit a hardening effect upon
annealing with a peak between 300 ∘C and 400 ∘C followed by a softening at
elevated annealing temperatures. In-situ HEXRD annealing experiments point
towards a supersaturated solid solution of FeCr. However, concurrent finely
dispersed Fe and Cr phases cannot be completely ruled out by microstructural
investigations. Up to temperatures of 520 ∘C, no peak separation or broadening
due to phase decomposition is found in HEXRD experiments. To clarify the
ambiguous results from HEXRD experiments in regard of the prevailing phases,
magnetostrictive measurements were conducted for HPT-deformed as well as
subsequently annealed materials. Results show a clear deviation with respect
to elemental Fe or Cr. The saturation magnetostriction
$\lambda_{s}(\upmu_{0}H=2.25~{}T)$ is 0 ppm (1 ppm), 8 ppm (12 ppm) and 17 ppm
(23 ppm) for the as-deformed (500 ∘C annealed) alloys consisting of Fe30Cr70,
Fe50Cr50 and Fe70Cr30, respectively. After excluding a magnetostrictive
contribution from interfaces, these values are explained by the formation of a
supersaturated solid solution by HPT-deformation, which persists during
annealing and validates findings from the synchrotron HEXRD measurements. To
decompose these FeCr solid solutions and to enable exchange bias effects, more
complex processing routes are necessary.

Declaration of Competing Interest The authors declare, that they have no known
competing financial interests or personal relationships, that could have
appeared to influence the work reported in this paper.

Acknowledgements The synchrotron measurements leading to these results have
been performed at beamline P21.2 at PETRA III under proposal I-20190577. The
authors thank DESY (Hamburg, Germany), a member of the Helmholtz Association
HGF, for the provision of experimental facilities and gratefully acknowledge
the assistance by Timo Müller who provided a lot of help and commitment to our
experiments. They further thank F. Spieckermann and C. Gammer for their help
with XRD-data processing. This project has received funding from the European
Research Council (ERC) under the European Union’s Horizon 2020 research and
innovation programme (Grant No. 757333).

## References

  * [1] E. Ma, Alloys created between immiscible elements, Progress in materials science 50 (4) (2005) 413–509.  doi:10.1016/j.pmatsci.2004.07.001.
  * [2] T. Koyano, T. Takizawa, T. Fukunaga, U. Mizutani, S. Kamizuru, E. Kita, A. Tasaki, Mechanical alloying process of fe-cr powders studied by magnetic measurements, Journal of applied physics 73 (1) (1993) 429–433.  doi:10.1063/1.353867.
  * [3] L. Weissitsch, M. Stückler, S. Wurster, R. Pippan, A. Bachmaier, Processing of Nanostructured Bulk Fe-Cr Alloys by Severe Plastic Deformation, in: THERMEC 2021, Vol. 1016 of Materials Science Forum, Trans Tech Publications Ltd, 2021, pp. 1603–1610.
  * [4] A. Bachmaier, M. Kerber, D. Setman, R. Pippan, The formation of supersaturated solid solutions in fe–cu alloys deformed by high-pressure torsion, Acta materialia 60 (3) (2012) 860–871.  doi:10.1016/j.actamat.2011.10.044.
  * [5] K. S. Kormout, R. Pippan, A. Bachmaier, Deformation-Induced Supersaturation in Immiscible Material Systems during High-Pressure Torsion, Advanced Engineering Materials 19 (4) (2017) 1600675.
  * [6] H. Szymczak, R. Żuberek, J. Gonzalez, Mechanisms responsible for magnetostriction in heterogeneous magnetic systems, Journal of magnetism and magnetic materials 191 (1-2) (1999) 199–202.  doi:10.1016/S0304-8853(98)00335-7.
  * [7] Y. Han, H. Wang, T. Zhang, Y. He, J. Coey, C. Jiang, Tailoring the heterogeneous magnetostriction in fe-co alloys, Journal of Alloys and Compounds 699 (2017) 200–209.  doi:10.1016/j.jallcom.2016.12.223.
  * [8] C. Bormio-Nunes, J. P. Serra, F. S. Barbosa, M. B. Dias, R. S. Turtelli, M. Atif, R. Grössinger, Magnetostriction of Fe–Cr and Fe–Cr–B alloys, IEEE Transactions on Magnetics 52 (5) (2016) 1–4.  doi:10.1109/TMAG.2015.2512271.
  * [9] J. Nogués, I. K. Schuller, Exchange bias, Journal of Magnetism and Magnetic Materials 192 (2) (1999) 203–232.  doi:10.1016/S0304-8853(98)00266-2.
  * [10] C. Binns, M. T. Qureshi, D. Peddis, S. H. Baker, P. B. Howes, A. Boatwright, S. A. Cavill, S. S. Dhesi, L. Lari, R. Kröger, et al., Exchange bias in fecr core–shell nanoparticles, Nano letters 13 (7) (2013) 3334–3339.  doi:10.1021/nl40.1587t.
  * [11] S. Giri, M. Patra, S. Majumdar, Exchange bias effect in alloys and compounds, Journal of Physics: Condensed Matter 23 (7) (2011) 073201.  doi:10.1088/0953-8984/23/7/073201.
  * [12] I. McDonald, M. E. Jamer, K. L. Krycka, E. Anber, D. Foley, A. Lang, W. D. Ratcliff, D. Heiman, M. Taheri, J. A. Borchers, et al., Exchange bias in bulk $\alpha$-fe/$\gamma$-fe70mn30 nanocomposites for permanent magnet applications, ACS Applied Nano Materials 2 (4) (2019) 1940–1950.  doi:10.1021/acsanm.8b02319.
  * [13] S. Chung, A. Hoffmann, M. Grimsditch, Interplay between exchange bias and uniaxial anisotropy in a ferromagnetic/antiferromagnetic exchange-coupled system, Physical Review B 71 (21) (2005) 214430.  doi:10.1103/PhysRevB.71.214430.
  * [14] A. Bachmaier, H. Krenn, P. Knoll, H. Aboulfadl, R. Pippan, Tailoring the magnetic properties of nanocrystalline Cu-Co alloys prepared by high-pressure torsion and isothermal annealing, Journal of Alloys and Compounds 725 (2017) 744–749.
  * [15] L. Weissitsch, M. Stückler, S. Wurster, P. Knoll, H. Krenn, R. Pippan, A. Bachmaier, Strain Induced Anisotropic Magnetic Behaviour and Exchange Coupling Effect in Fe-SmCo5 Permanent Magnets Generated by High Pressure Torsion, Vol. 10, Multidisciplinary Digital Publishing Institute, 2020, p. 1026\.  doi:10.3390/cryst10111026.
  * [16] A. Hohenwarter, R. Pippan, Sample Size and Strain-Rate-Sensitivity Effects on the Homogeneity of High-Pressure Torsion Deformed Disks, Metallurgical and Materials Transactions A 50 (2) (2019) 601–608.  doi:10.1007/s11661-018-4989-1.
  * [17] Z. Horita, Y. Tang, T. Masuda, Y. Takizawa, Severe Plastic Deformation under High Pressure: Upsizing Sample Dimensions, MATERIALS TRANSACTIONS (2020) MT–M2020074doi:10.2320/matertrans.MT-M2020074.
  * [18] B. Schuh, F. Mendez-Martin, B. Völker, E. George, H. Clemens, R. Pippan, A. Hohenwarter, Mechanical properties, microstructure and thermal stability of a nanocrystalline CoCrFeMnNi high-entropy alloy after severe plastic deformation, Acta Materialia 96 (2015) 258 – 268.  doi:https://doi.org/10.1016/j.actamat.2015.06.025.
  * [19] E. Menéndez, J. Sort, V. Langlais, A. Zhilyaev, J. Muñoz, S. Suriñach, J. Nogués, M. Baró, Cold compaction of metal–ceramic (ferromagnetic–antiferromagnetic) composites using high pressure torsion, Journal of alloys and compounds 434 (2007) 505–508.  doi:10.1016/j.jallcom.2006.08.142.
  * [20] W. Xiong, M. Selleby, Q. Chen, J. Odqvist, Y. Du, Phase equilibria and thermodynamic properties in the Fe-Cr system, Critical Reviews in Solid State and Materials Sciences 35 (2) (2010) 125–152.
  * [21] A. Hohenwarter, A. Bachmaier, B. Gludovatz, S. Scheriau, R. Pippan, Technical parameters affecting grain refinement by high pressure torsion, International Journal of Materials Research 100 (12) (2009) 1653–1661.  doi:10.3139/146.110224.
  * [22] R. Valiev, I. Alexandrov, Nanostructured materials from severe plastic deformation, Nanostructured materials 12 (1-4) (1999) 35–40.  doi:10.1016/S0965-9773(99)00061-6.
  * [23] P. L. Kapitza, The study of the magnetic properties of matter in strong magnetic fields. part V.—experiments on magnetostriction in dia-and para-magnetic substances, Proceedings of the Royal Society of London. Series A, Containing Papers of a Mathematical and Physical Character 135 (828) (1932) 568–600.
  * [24] G. Ashiotis, A. Deschildre, Z. Nawaz, J. P. Wright, D. Karkoulis, F. E. Picca, J. Kieffer, The fast azimuthal integration python library: pyFAI, Journal of applied crystallography 48 (2) (2015) 510–519.  doi:10.1107/S1600576715004306.
  * [25] M. Ruzi, voigt line shape fit, website, MATLAB Central File Exchange, 57603-voigt-line-shape-fit (2020).
  * [26] O. Renk, A. Hohenwarter, K. Eder, K. Kormout, J. Cairney, R. Pippan, Increasing the strength of nanocrystalline steels by annealing: Is segregation necessary?, Scripta materialia 95 (2015) 27–30.  doi:10.1016/j.scriptamat.2014.09.023.
  * [27] X. Huang, N. Hansen, N. Tsuji, Hardening by annealing and softening by deformation in nanostructured metals, Science 312 (5771) (2006) 249–251.  doi:10.1126/science.1124268.
  * [28] R. Valiev, N. Enikeev, M. Y. Murashkin, V. Kazykhanov, X. Sauvage, On the origin of the extremely high strength of ultrafine-grained Al alloys produced by severe plastic deformation, Scripta Materialia 63 (9) (2010) 949–952.  doi:10.1016/j.scriptamat.2010.07.014.
  * [29] Z. Hegedüs, T. Müller, J. Hektor, E. Larsson, T. Bäcker, S. Haas, A. Conceiçao, S. Gutschmidt, U. Lienert, Imaging modalities at the Swedish Materials Science beamline at PETRA III, in: IOP Conference Series: Materials Science and Engineering, Vol. 580, IOP Publishing, 2019, p. 012032.  doi:10.1088/1757-899X/580/1/012032.
  * [30] G. Chiarotti, 1.6 Crystal structures and bulk lattice parameters of materials quoted in the volume: Datasheet from Landolt-Börnstein - Group III Condensed Matter, interaction of Charged Particles and Atoms with Surfaces - in SpringerMaterials.  doi:10.1007/10086066{\\_}6.
  * [31] L. Vegard, Die Konstitution der Mischkristalle und die Raumfüllung der Atome, Zeitschrift für Physik 5 (1) (1921) 17–26.  doi:10.1007/BF01349680.
  * [32] T. H. De Keijser, J. Langford, E. J. Mittemeijer, A. Vogels, Use of the voigt function in a single-line method for the analysis of X-ray diffraction line broadening, Journal of Applied Crystallography 15 (3) (1982) 308–314.
  * [33] P. James, O. Eriksson, O. Hjortstam, B. Johansson, L. Nordström, Calculated trends of the magnetostriction coefficient of 3d alloys from first principles, Applied Physics Letters 76 (7) (2000) 915–917.  doi:10.1063/1.125628.
  * [34] R. Grössinger, R. S. Turtelli, N. Mehmood, Materials with high magnetostriction, IOP Conference Series: Materials Science and Engineering 60 (2014) 012002.  doi:10.1088/1757-899x/60/1/012002.
  * [35] M. J. Dapino, et al., On magnetostrictive materials and their use in adaptive structures, Structural Engineering and Mechanics 17 (3-4) (2004) 303–330.
  * [36] E. Lee, M. Asgar, Magnetostriction and Anomalous Thermal Expansion of Chromium, Physical Review Letters 22 (26) (1969) 1436.  doi:10.1103/PhysRevLett.22.1436.
  * [37] A. Clark, Chapter 7 Magnetostrictive rare earth-Fe2 compounds, Vol. 1 of Handbook of Ferromagnetic Materials, Elsevier, 1980, pp. 531 – 589.  doi:10.1016/S1574-9304(05)80122-1.
  * [38] A. Mazilkin, B. Straumal, A. Kilmametov, T. Boll, B. Baretzky, O. Kogtenkova, A. Korneva, P. Zieba, Competition for impurity atoms between defects and solid solution during high pressure torsion, Scripta Materialia 173 (2019) 46–50.  doi:10.1016/j.scriptamat.2019.08.001.
  * [39] G. Herzer, Nanocrystalline soft magnetic materials, Physica Scripta 1993 (T49A) (1993) 307.  doi:10.1088/0031-8949/1993/T49A/054.
  * [40] P. G. Tello, J. Blanco, J. Gonzalez, Effective anisotropy and saturation magnetostriction of soft magnetic FeZrB (Cu) amorphous and nanocrystalline alloys, Nanotechnology 14 (2) (2003) 304.  doi:10.1088/0957-4484/14/2/339.
  * [41] A. Ślawska-Waniewska, R. Żuberek, P. Nowicki, Saturation magnetostriction of FeZrB (Cu) nanocrystalline alloys, Journal of magnetism and magnetic materials 157 (1996) 147–148.  doi:10.1016/0304-8853(95)01190-0.
  * [42] R. Hall, Single-Crystal Magnetic Anisotropy and Magnetostriction Studies in Iron-Base Alloys, Journal of Applied Physics 31 (6) (1960) 1037–1038.  doi:10.1063/1.1735741.
  * [43] K. H. J. Buschow, F. R. Boer, et al., Physics of magnetism and magnetic materials, Vol. 7, Springer, 2003.  doi:10.1007/b100503.
  * [44] J. Makar, D. Atherton, Effects of stress on the magnetostriction of 2% mn pipeline steel, IEEE transactions on magnetics 30 (4) (1994) 1388–1394.  doi:10.1109/20.305537.
  * [45] J. Li, X. Gao, J. Zhu, C. He, J. Qiao, M. Zhang, Texture evolution and magnetostriction in rolled (fe81ga19) 99nb1 alloy, Journal of alloys and compounds 476 (1-2) (2009) 529–533.  doi:10.1016/j.jallcom.2008.09.087.
  * [46] Y. He, J. Coey, R. Schaefer, C. Jiang, Determination of bulk domain structure and magnetization processes in bcc ferromagnetic alloys: Analysis of magnetostriction in f e 83 g a 17, Physical Review Materials 2 (1) (2018) 014412\.  doi:10.1103/PhysRevMaterials.2.014412.

Supplementary 1: The [110] peak of the in-situ synchrotron annealing
experiment is fitted by a single Voigt-peak. The FWHM is separated into a
Gaussian a) and Cauchy b) contribution and plotted against the increasing
temperature during heating.


#  GraphTango: A Hybrid Representation Format for Efficient Streaming Graph
Updates and Analysis

Alif Ahmed, Farzana Ahmed Siddique, Kevin Skadron  University of Virginia
<EMAIL_ADDRESS>
###### Abstract

Streaming graph processing involves performing batched updates and analytics
on a time-evolving graph. The underlying representation format largely
determines the throughputs of these updates and analytics phases. Existing
representation formats usually employ variations of hash tables or adjacency
lists. However, a recent study showed that the adjacency-list-based approaches
perform poorly on heavy-tailed graphs, and the hash-based approaches suffer on
short-tailed graphs. We propose GraphTango, a hybrid representation format
that provides excellent update and analytics throughput regardless of the
graph’s degree distribution. GraphTango dynamically switches among three
different formats based on a vertex’s degree: i) Low-degree vertices store the
edges directly with the neighborhood metadata, confining accesses to a single
cache line, ii) Medium-degree vertices use adjacency lists, and iii) High-
degree vertices use hash tables as well as adjacency lists. In this case, the
adjacency list provides fast traversal during the analytics phase, while the
hash table provides constant-time lookups during the update phase. We further
optimized the performance by designing an open-addressing-based hash table
that fully utilizes every fetched cache line. In addition, we developed a
thread-local lock-free memory pool that allows fast growing/shrinking of the
adjacency lists and hash tables in a multi-threaded environment. We evaluated
GraphTango with the help of the SAGA-Bench framework and compared it with four
other representation formats. On average, GraphTango provides 4.5x higher
insertion throughput, 3.2x higher deletion throughput, and 1.1x higher
analytics throughput over the next best format. Furthermore, we integrated
GraphTango with the state-of-the-art graph processing frameworks DZiG and
RisGraph. Compared to the vanilla DZiG and vanilla RisGraph, [GraphTango +
DZiG] and [GraphTango + RisGraph] reduces the average batch processing time by
2.3x and 1.5x, respectively.

##  I Introduction

Streaming graph processing involves performing batched updates and analytics
on a time-evolving graph. The update phase handles modifications to the graph
topology (e.g., insertion/deletion of edges and nodes), while the analytics
phase runs the necessary algorithms on the graph. This is a common scenario in
many real-world graph applications such as social network analysis [1, 2],
bioinformatics [3, 4], recommendation systems [5, 6], routing and navigation
[7], knowledge discovery [8], sensor networks [9], etc. The focus of streaming
graph processing is fundamentally different from static graph processing.
Static graphs are constructed only once, and the construction cost gets
amortized over time. Therefore, the overall performance of a static graph
processing framework is primarily determined by the analytics throughput. In
the case of streaming graphs, the graph topology can change very frequently.
Hence, both update and analytics throughput is critical for streaming graphs
[10].

The most common operation during the update phase is edge lookup. The lookup
is performed before insertion to avoid duplicate edges111In accordance with
the prior works [10, 11, 12, 13], edges are inserted only after a lookup to
avoid duplicate edges. and before deletion to find the location of the target
edge. On the other hand, the most common operation during the analytics phase
is the neighborhood traversal of a given vertex. The performance of a
streaming graph processing framework is critically dependent on how
efficiently the graph storage format can support these lookup and traversal
operations. Existing storage formats for streaming graphs usually employ
variations of adjacency lists or hash tables [13, 12, 10, 11, 14]. Approaches
based on adjacency lists [11, 10] provide high update throughput on short-
tailed graphs222Following prior work [10], we define heavy/short-tailed graph
with respect to an update batch: heavy-tailed graphs have high maximum degree
within a batch. Short-tail is the opposite. but suffer in heavy-tailed graphs
as it requires linear lookup through the edge array [10]. On the other hand,
hash-based approaches [13, 12] offer constant-time lookup, providing better
update throughput on heavy-tailed graphs. However, they perform poorly on
short-tailed graphs because the overhead of hash calculation and several
random accesses becomes more expensive than conducting a simple linear search.
Furthermore, edges are stored in hash tables relatively sparsely to mitigate
collisions. As a result, edge traversal becomes inefficient and negatively
impacts their analytics phase’s throughput. None of the existing approaches
can efficiently handle both short-tailed and heavy-tailed graphs.

This paper proposes GraphTango, a streaming graph representation format that
provides excellent performance regardless of the graph’s degree distribution.
Our key idea is to adaptively switch the underlying data structure based on
the vertex degree: i) Type1 vertex: Low-degree vertices where the edges are
stored within the same cache line as the neighborhood metadata. Update and
edge traversal thus requires only one cache line access, unlike other
approaches. ii) Type2 vertex: Medium-degree vertices that store edges as
adjacency lists. The degree is too high for this type to fit all edges in a
cache line, but small enough so that linear search performs better than
hashing. iii) Type3 vertex: High-degree vertices that store edges as adjacency
lists, along with hash tables storing indexes to the adjacency lists. In this
case, the adjacency list provides optimal edge traversal during the analytics
phase, while the hash table provides constant-time lookup during the update
phase. The hash tables are not accessed during the analytics phase, avoiding
any potential cache pollution. To improve the cache access pattern of the hash
table, we designed an open-addressing-based hash table with double hashing
that fully utilizes every fetched cache line. Our proposed hashing scheme
minimizes cache line fetches and is especially beneficial if the hash tables
do not fit into the last level cache (LLC), which is often the case for real-
world graph workloads333Even with our smallest dataset of 5M edges, the LLC
miss rate during the update phase is over 49%, indicating that the working set
size is larger than the LLC.. With this hashing scheme, updates for Type3
vertices are performed with only three cache line accesses for more than 99.2%
of the cases. In addition, we developed a thread-local lock-free memory pool
that allows fast growing and shrinking of the adjacency lists and hash tables
in a multi-threaded environment.

We evaluated GraphTango by integrating it with the SAGA-Bench [10]
benchmarking framework. SAGA-Bench integration ensures that all approaches use
the same algorithm implementations via a common API. Therefore, any
performance improvement comes purely from the data structure standpoint. SAGA-
Bench comes with four representation formats: AdListShared, AdListChunked,
Stinger [11], and DegAwareRHH [13], each of which is shown to excel in
different algorithm and dataset combinations [10]. Details of these formats
can be found in Section II. For update operations, GraphTango consistently
performed best across all datasets. On average (maximum), GraphTango
demonstrates 4.5x (6.6x) higher insertion throughput and 3.2x (5.0x) higher
deletion throughput over the next best approach. As for analytics, GraphTango
offers 1.1x (1.6x) higher throughput than the next best approach. Unlike prior
approaches, GraphTango provides excellent update and analytics throughput for
both short-tailed and heavy-tailed graphs.

Being a storage format, GraphTango is orthogonal to most full-fledged graph
processing frameworks and can easily replace the underlying storage formats of
those frameworks. To demonstrate, we integrated GraphTango with the state-of-
the-art graph processing frameworks DZiG [15] and RisGraph [16]. DZiG +
GraphTango reduced the overall batch processing runtime by 2.3x (5.2x) on
average (maximum) compared to the original DZiG. RisGraph + GraphTango reduced
the overall batch processing runtime by 1.5x (1.9x) on average (maximum)
compared to the original RisGraph.

GraphTango will be made available on GitHub, both as a standalone framework
and as an integration with SAGA-Bench, DZiG, and RisGraph.

##  II Existing Representation Formats

Figure 1: Example of different graph representation formats. Here, each edge
$e$ is an $\\{dst,prop\\}$ tuple. Figure 2: Proposed hybrid representation
format of GraphTango.

Figure 1 illustrates how various graph representation formats store vertices
and edges. While these examples store only the outgoing edges, the concept is
also applicable if storing incoming edges.

Compressed Sparse Row (CSR) is one of the most commonly used formats for
static graphs [17, 18, 19, 20]. As shown in Figure 1(b), CSR organizes data in
an edge array and an index array. Edges are stored in the edge array in
ascending order - all edges of vertex $v_{i}$ appear before any edge of
$v_{i+1}$. The index array stores the position of the first edge of every
vertex. CSR is widely used for static graphs because it provides a compact
representation, increasing spatial locality while traversing the graph.
However, inserting or deleting an edge requires reconstructing both the edge
array and the index array, making CSR unsuitable for dynamic graphs.

Adjacency List stores the edges of every vertex in separate arrays (Figure
1(c)). A vertex array stores the pointers to these edge arrays. These edge
arrays are assumed to be memory-contiguous (like std::vector), rather than a
linked list of edges. This important distinction is used throughout the paper.
As each edge array can grow/shrink independently, insertion and deletion
operations only modifies the edge array of the corresponding vertex. This
property makes adjacency lists a common choice for dynamic graph frameworks
[10, 14]. Another advantage of adjacency lists is that the edge traversal
during the analytics phase has a sequential access pattern, leading to
excellent analytics throughput for vertex-centric algorithms. The downside of
adjacency lists is that the edges are not stored in any particular order
within an edge array. Therefore, finding an edge requires a linear search
through the corresponding edge array, leading to poor update throughput on
high-degree vertices.

In adjacency-list-based approaches, parallel updates on multiple vertices are
realized in two ways. The first scheme is the shared style multithreading
(referred as AdListShared), where the vertex array additionally contains a
lock for every vertex. Any thread can process updates on any vertex by
acquiring the corresponding lock first. This approach provides fine-grained
parallelism. However, if most updates are targeted towards the same vertex, it
can cause lock contention and is often the case for heavy-tailed graphs. The
alternative scheme groups source vertices into chunks and assign each chunk to
a fixed thread (referred as AdListChunked). Chunked style multithreading is
lock-free. However, it is prone to workload imbalance if the chunks have a
high disparity in the number of edges they contain.

Stinger [11] is an adjacency-list-based representation format. As illustrated
in Figure 1(d), Stinger stores the edges as linked lists of edge blocks. Each
edge block can accommodate a fixed number of edges (default is 16).
Parallelism in Stinger is achieved by acquiring locks on the edge blocks. The
capacity of the edge blocks presents a trade-off between performance and
storage requirements. Using smaller capacity edge blocks increase parallelism
but makes graph traversal inefficient by increasing the amount of pointer-
chasing accesses. On the other hand, larger blocks lead to many unused slots
for low-degree vertices. Besides, like adjacency lists, Stinger also suffers
from linear lookups on high-degree vertices, stagnating the update throughput.

Degree-Aware Robin Hood Hashing (DegAwareRHH) [13] is a hash-based format. As
shown in Figure 1(e), DegAwareRHH maintains two types of hash tables based on
the vertex degree. Edges corresponding to low-degree vertices are stored in a
combined hash table to improve data locality. On the other hand, each high-
degree vertex maintains its own hash table. Both of these hash tables use
Robin Hood hashing [21], which minimizes probing distance. For parallelism,
DegAwareRHH leverages chunked-style multithreading similar to AdListChunked.
The constant time lookup enabled by the hash tables makes DegAwareRHH suitable
for the update phases on heavy-tailed graphs. However, the sparse storage of
edges in the hash table makes DegAwareRHH’s edge traversal inefficient,
negatively impacting the analytics throughput.

##  III GraphTango Data Structure

Figure 2 gives an overview of the GraphTango data structure444The description
assumes storing only outgoing edges for clarity. In our implementation, we
stored both incoming and outgoing edges for directed graphs.. GraphTango
organizes the vertex data in two arrays: one for storing the vertex properties
($vProp$) and the other for storing neighborhood metadata of the vertex
($edgeMeta$). These arrays are indexed using vertex id. Neighbors of each
vertex are stored as an $e_{x}=\\{dst,[prop]\\}$ tuple, where $e_{x}.dst$ is
the destination vertex id, and $e_{x}.prop$ is an optional edge property
(e.g., the weight of the edge).

The $edgeMeta$ array is aligned to a page boundary555To clarify, only the
$edgeMeta$ array itself is page boundary aligned, not the edge arrays or hash
tables it may point to., and each element of the array is of cache line size.
Therefore, accessing any field of $edgeMeta[i]$ will bring the rest of the
fields into the cache. The $deg$ field holds the current degree of the
corresponding vertex. Depending on the degree, a vertex will fall into one of
the following three categories:

Type1 Vertex: These are low-degree vertices with $deg\leq TH_{0}$. As
illustrated in Figure 2(b), we store the edges directly with the metadata for
Type1 vertices. The threshold $TH_{0}$ denotes the number of edges that can
fit inside the metadata and is defined as:

$TH_{0}=\left\lfloor{\frac{CACHE\\_LINE\\_SIZE-
sizeof(deg)}{sizeof(e)}}\right\rfloor$

For example, $TH_{0}=7$ for a typical cache line size of 64 bytes and edges of
8 bytes. The advantage of storing edges with metadata is that all edges are
brought into the cache as soon as we access the vertex during the update or
analytics phase. When searching for a specific edge, we need to do a linear
search. However, the search is extremely fast, as all accesses will be cache
hits.

Type2 Vertex: These are medium-degree vertices with $TH_{0}<deg\leq TH_{1}$,
where $TH_{1}$ is a user-configurable threshold. Edges for this type of
vertices are stored in adjacency lists, as shown in Figure 2(c). To support
adjacency lists, $edgeMeta$ additionally maintains the current capacity
($cap$) and a pointer to its edge array ($edgePtr$).

Like Type1 vertices, Type2 also requires a linear search when looking for a
specific edge. As the linear search on the edge array is prefetcher-friendly
and has good spatial locality, it offers better performance than hash-based
search up to a certain point (i.e., tuned using the $TH_{1}$ threshold).
However, the linear nature of the search becomes a performance bottleneck for
higher-degree vertices. Hash-based search is preferable in such cases, as
explained below.

Type3 Vertex: These are high-degree vertices with $deg>TH_{1}$. Figure 2(d)
illustrates this scenario. Here, we maintain both an adjacency list and a hash
table for each Type3 vertex. The hash table maps an edge’s destination vertex
id ($e_{x}.dst$) with its location in the corresponding adjacency list.
Maintaining both hash table and adjacency list comes with the following
benefits: i) The hash table enables constant-time lookups during the update
phase. ii) The adjacency list provides fast and efficient traversal during the
analytics phase. Prior hash-based approaches suffer from low analytics
throughput due to inefficient edge traversal [10]. GraphTango is free of this
issue because it uses only the adjacency lists for edge traversal and does not
require accessing the hash tables during the entirety of the analytics phase.

##  IV GraphTango Basic Operations

TABLE I: Vertex type switching steps for insertion/deletions

(a) Insertions triggering type switch or capacity doubling | Direction
---
New capacity |  | Alloc new
---
edge array
| Edge copy
---
size
| Dealloc old
---
edge array
Rehash
Type1 $\rightarrow$ Type2 |  nextPow2($TH_{0}$) | $\checkmark$ |  deg (=$TH_{0}$) | X | X
Type2 $\rightarrow$ Type2 | cap * 2 | $\checkmark$ | deg | $\checkmark$ | X
Type2 $\rightarrow$ Type3 | cap * 2 | $\checkmark$ |  deg (=$TH_{1}$) | $\checkmark$ | $\checkmark$
Type3 $\rightarrow$ Type3 | cap * 2 | $\checkmark$ | deg | $\checkmark$ | $\checkmark$

(b) Deletions triggering type switch or capacity halving | Direction
---
New capacity |  | Alloc new
---
edge array
| Edge copy
---
size
| Dealloc old
---
edge array
Rehash
Type3 $\rightarrow$ Type3 | cap / 2 | $\checkmark$ | deg | $\checkmark$ | $\checkmark$
Type3 $\rightarrow$ Type2 | cap / 2 | $\checkmark$ |  deg (=$TH_{1}$) | $\checkmark$ | X
Type2 $\rightarrow$ Type2 | cap / 2 | $\checkmark$ | deg | $\checkmark$ | X
Type2 $\rightarrow$ Type1 | $TH_{0}$ | X |  deg (=$TH_{0}$) | $\checkmark$ | X

###  IV-A Edge Insertion

The edge insertion procedure is as follows: (i) Retrieve the edge metadata -
$edgeMeta[srcId]$. (ii) If the current $deg$ reaches the current capacity , we
double the capacity. The exact steps for capacity doubling will depend upon
the current and new type, as demonstrated in Table I(a). In general, capacity
doubling involves allocating memory for the larger edge array, copying current
edges to the new edge array, and freeing the old array. For Type3, the hash
table is also rehashed. The amortized cost of capacity doubling is O(1) [22].
(iii) Search for a duplicate edge using $dst$. As mentioned earlier, for Type1
and Type2, it will involve doing a linear search, and for Type3, the search
will be performed using the hash table. (iv-A) If the edge is found, update
the property and return. (iv-B) If the edge is not found, add the edge at the
end of the edge array and increment $deg$. For Type3, we also create an entry
in the hash table pointing to the location.

###  IV-B Edge Deletion

The edge deletion procedure is as follows: (i) Retrieve the edge metadata -
$edgeMeta[srcId]$. (ii) Search for existing edge using $dst$. (iii-A) If the
edge is not found, return. (iii-B) If the edge is found, delete the entry from
the edge array and hash table (for Type3) and decrement $deg$. We do a
compaction step here to fill the gap. It involves moving the last entry of the
edge array to the deleted entry’s position and updating the corresponding hash
table record. The compaction step is simple and is of constant time
complexity. (iv) If the $deg$ becomes 1/4th of the capacity, we halve the
capacity. The steps for capacity halving is given in Table I(b). Similar to
the capacity doubling during insertion, the amortized cost of capacity halving
is also O(1) [22].

###  IV-C Edge Traversal

As we store the edges in consecutive memory for all three vertex types666Even
after deletions, our compaction step ensures that all valid edges of a vertex
are stored in consecutive memory., the edge traversal API simply returns a
cursor (i.e., position of the iterator) for indexing to the: i)
$edgeMeta[vid]$ for Type1 vertices, or ii) $edgeMeta[vid].edgePtr$ for
Type2/Type3 vertices. GraphTango’s traversal mechanism is essentially the same
as an adjacency list for Type2/Type3 vertices. As for Type1, GraphTango has a
better access pattern as it requires one less indirection.

##  V Optimizing GraphTango

###  V-A Cache-Friendly Hashing Scheme

The hash table used by the Type3 vertices can be realized in several ways. The
most convenient approach is to use std::unordered_map. Unfortunately, this
approach is not ideal for our purpose because the C++ standard [23]
effectively limits the collision resolution of std::unordered_map to separate
chaining777This constraint is a side effect of mandating pointer stability,
which means that an iterator must remain valid upon inserting or deleting
elements.. With separate chaining, the hash table is constructed as an array
of buckets. Each bucket points to a linked list of colliding elements (i.e.,
keys that hashed to the same bucket). The issue with separate chaining is that
it involves multiple random accesses - one to access the bucket and one or
more for traversing the linked list. Each of these random accesses is a
potential cache miss if the hash table does not fit into the cache. An
alternative to separate chaining is open addressing, where all elements are
stored in the hash table itself, eliminating the need for linked lists
traversals. Prior hash-based graph representation formats [13, 12] leveraged
open-addressing-based Robin Hood hashing [21] that minimizes probing distance.
For GraphTango, we designed a more cache-friendly open-addressing-based hash
table that minimizes the number of cache line accesses, making it especially
suitable for real-world graph workloads where the hash table is unlikely to
fit into the cache.

Figure 3: Proposed hashing scheme. (a) Hash function to determine the index to
the hash table. (b) An example probing sequence for $M=5$ and $N=4$.

The key idea of our hashing scheme is to limit the probes within a single
cache line until it is fully searched, before moving onto a different cache
line. Figure 3 illustrates this hashing scheme. The hash table itself is
composed of an array of $\\{key,value\\}$ pairs. The index of the $i$-th probe
to the hash table is given by the following hash function:

$h(key,i)=N\cdot
h_{1}\left(key,\left\lfloor\frac{i}{N}\right\rfloor\right)+h_{2}(key,i~{}mod~{}N)$

Here, $N$ is the number of $\\{key,value\\}$ pairs that can fit within a
single cache line. The purpose of
$h_{1}\left(key,\left\lfloor\frac{i}{N}\right\rfloor\right)$ is to select a
cache line for probing and returns the base index of that selected cache line.
Note that the $\left\lfloor\frac{i}{N}\right\rfloor$ parameter remains the
same for every $N$ consecutive probes, thereby selecting the same cache line.
As $h_{1}()$ should eventually explore all cache lines in the hash table, it
must be a permutation of $\\{0,1,...,M-1\\}$, where $M$ is the number of cache
lines in the hash table. On the other hand, $h_{2}(key,i~{}mod~{}N)$
determines the offset within the cache line and must be a permutation of
$\\{0,1,...,N-1\\}$. Any hash function conforming to this permutation
requirement can be used to implement $h_{1}()$ and $h_{2}()$. In GraphTango,
we used double hashing for $h_{1}()$ to avoid primary/secondary clustering.
$h_{2}()$ uses linear probing to make hash computation simpler. Our hash
function is very cheap to compute, with the reference implementation having
two multiplications and eight other simple arithmetic/logical instructions.
This is because we ensure that both $N$ and $M$ are powers-of-two, converting
expensive modulus and division operations to simple shifts. Further
optimization is possible by leveraging SIMD instructions to do a parallel
comparison on all entries mapped to the same cache line. However, as discussed
later, GraphTango demonstrates short probing distance, making iterative
comparison just as performant.

Insertions and deletions to the proposed hash table are similar to other open-
addressing-based hash tables. Each location of the hash table can contain
either: i) a valid $\\{key,value\\}$ pair, or ii) an empty marker, or iii) a
deleted marker (i.e., tombstone). We used two reserved values as the empty and
deleted marker instead of using dedicated tag storage. During both insertion
and deletion, the table is probed (using the hash function) until the $key$ or
an empty marker is found. If the $key$ is found: i) For insertion, the
corresponding $value$ is updated. ii) For deletion, the entry is marked as
deleted. Instead of $key$, if an empty marker is found: i) No action is
required for deletion. ii) For insertion, the $\\{key,value\\}$ pair is
inserted to the location of the first encountered delete marker, or to the
current location if no delete marker was encountered.

When using with GraphTango, the hash tables’ initial capacity is set to twice
the capacity of the corresponding adjacency lists. Upon inserting/deleting
edges, both the hash tables and the adjacency lists can grow/shrink in size
(see Section IV), but the capacity ratio always remains 2. This property sets
the maximum load factor ($\alpha$) of the hash table to $0.5$. Assuming
uniform hashing888Double hashing can demonstrate performance very close to the
ideal scenario of uniform hashing [22, 24]., the theoretical average probing
distance is: i) $\frac{1}{1-\alpha}=2$ for an unsuccessful search. This is
often the case for edge insertions in the absence of duplicates. ii)
$\frac{1}{\alpha}ln\frac{1}{1-\alpha}=1.39$ for a successful search (e.g.,
deleting existing edges). In GraphTango, we can fit eight $\\{key,value\\}$
pairs within a single cache line (i.e., $N=8$). As a result, the hash table
needs to access only one cache line as long as the probing distance remains
$\leq 8$, which provides a large slack over the theoretical average probing
distances. We empirically observed the same trend with our graph datasets,
where over 99.2% of the insertions had a probing distance $\leq 8$. Therefore,
almost all edge insertion operations for Type3 vertices require only three
cache line accesses: i) one for retrieving $edgeMeta[srcId]$ metadata that
contains hash table and adjacency list pointers, ii) one for searching the
hash table, and iii) one for indexing to the adjacency list.

###  V-B Memory Allocation Scheme

As discussed in Section IV, GraphTango requires frequent growing/shrinking of
adjacency lists and hash tables. Calling $malloc()$/$free()$ in every such
instance can cause high runtime overhead and memory fragmentation. We avoid
this issue by designing a fast thread-local lock-free memory pool that
supports O(1) allocation and deallocation.

Figure 4 illustrates the data structure of the memory pool. This memory pool
allocates chunks in power-of-two sizes. Individual linked lists of available
chunks are maintained for each valid size. The heads of the linked lists are
stored in the $freePtrs$ array. The first 8 bytes of each chunk (highlighted
green) hold the pointer to the next free chunk of the same size. This way, no
extra storage beside the $freePtrs$ array is required to hold the pointers.
However, it limits the minimum chunk size to 8 bytes in a 64-bit machine.

Figure 4: Allocation and deallocation on the memory pool. Deleted pointers are
shown by dashed lines and the modified pointers by red lines.

Allocation steps are shown in Figure 4(a). For an allocation request of $sz$
bytes, the pool will return a chunk of size $newSz=2^{k}$, where $k=\lceil
log_{2}(sz)\rceil$ (i.e., nearest power of two that is $\geq sz$). The
allocation proceeds as follows: i) Find the first available free chunk of
$newSz$. This is simply given by $ret=freePtrs[k]$. ii) If $ret$ is not a null
pointer, then it points to a free chunk. In this case, we update $freePtrs[k]$
to point to the next free chunk, and return $ret$. iii) If $ret$ is a null
pointer, this indicates no chunk of the requested size is available. In this
case, a large memory block is allocated (of size $max(4MB,newSz)$ and aligned
to the page boundary) and then split into a linked list of $newSz$ byte
chunks. $freePtrs[k]$ is set to point to the first chunk. At this point, we
have free chunks of $newSz$. Therefore, repeating step (ii) will complete the
allocation. Note that, once allocated, the full chunk can be used to store
data, including the space initially used to hold the pointer to the next
chunk.

Deallocation steps are shown in Figure 4(b). Unlike the standard $free(ptr)$,
we provide the size of the allocated chunk as an additional parameter -
$free(ptr,sz)$. Using the $sz$ parameter, we can directly index to the
$freePtrs$ array and add $ptr$ as a free chunk, as shown in Figure 4(b).

An advantage of the proposed memory pool is that the most recently deallocated
chunk will be allocated first, thereby being more likely to reside in the
cache. Furthermore, each thread maintains its own $freePtrs$ array. As a
result, no lock is required when multiple threads are trying to
allocate/deallocate simultaneously. A minor downside is that one thread cannot
allocate free chunks from another thread’s pool. We found it to be of little
consequence in practice because the maximum amount of unused space per thread
is O(blockSize). Also, note that the $\lceil log_{2}(sz)\rceil$ calculation
used to index $freePtrs$ is very cheap to perform. It only requires count
leading zero $(clz)$ and shift instructions.

###  V-C Parallelization

For GraphTango, we experimented with both shared and chunked style
multithreading. We decided to settle for chunked style multithreading as it
demonstrated slightly better throughput on our datasets. As we are using
chunked style multithreading, operations concerning any vertices within a
partition is mapped to a fixed worker thread. As discussed before, this method
eliminates the need of performing atomic operations and requires minimum
synchronization, but may suffer from workload imbalance. Exploring advanced
load-balancing techniques is left as a potential future work. Another related
concern is false sharing, which might occur when multiple threads
simultaneously modify a shared data structure. In the case of GraphTango,
false-sharing-prone data structures are the vertex property array and the
active frontier array. We avoid false sharing by using a partition size
multiple of the cache line size (e.g., 512). It ensures that no two
partitions’ data share the same cache line.

###  V-D Determining the $TH_{1}$ Threshold

Unlike the $TH_{0}$ threshold, which is fixed for a given cache line size and
edge element size, the $TH_{1}$ threshold is flexible and has a moderate
impact on performance and memory usage (Section VI-D). As mentioned before,
$TH_{1}$ should be set to a value for which $O(TH_{1})$ linear search through
the edge array is likely to perform better than $O(1)$ hash table lookup. The
following equation provides an estimate and can be used as a rule of thumb for
selecting $TH_{1}$:

$TH_{1}=2^{\lceil log_{2}(3\times edgesPerCacheLine)\rceil}$ (1)

This equation sets $TH_{1}$ to a value roughly corresponding to four cache
line accesses for Type2 vertices. This is slightly above the three cache line
accesses of Type3 vertices, as Type2 vertices have favorable sequential access
patterns and do not incur hash calculation overheads. As an alternative, we
provide a microbenchmark program (graph dataset agnostic) with GraphTango that
empirically finds a suitable $TH_{1}$ threshold.

##  VI Evaluation

###  VI-A Experimental Setup

Figure 5: Comparison of the analytics throughputs. Higher is better.

A) Platform: The experiments are conducted on an AMD Ryzen 3900x @ 3.8GHz
machine with 12 physical cores, 64MB of LLC, and 32GB of DDR4 DRAM. Hyper-
threading and turbo-boost were disabled for better reproducibility. All
experiments are performed with 12 cores.

B) Implementation: We evaluated GraphTango by integrating it with the SAGA-
Bench [10] benchmarking framework. SAGA-Bench comes with four representation
formats - AdListShared, AdListChunked, Stinger [11], and DegAwareRHH [13].
Details of these formats can be found in Section II. SAGA-Bench integration
facilitates fair comparison, because all approaches must use the exact same
algorithm implementations through a common API999We used the official
integration of SAGA-Bench from [25] even if the original author’s source code
is publicly available (e.g., Stinger [26]).. The source code is compiled with
gcc-9.3.0 and -03 flag.

Both vertex id and edge property are considered to be of 64-bits size.
Therefore, GraphTango has $TH_{0}=7$ for unweighted graphs and $TH_{0}=3$ for
weighted graphs. $TH_{1}$ is set to 32 following the tuning carried out in
Section VI-D. This $TH_{1}$ value also matches the value provided by Equation
1.

C) Profiling Methodology: Graph datasets are first randomly shuffled to break
any existing ordering of edges. This is done to reflect the realistic scenario
where edge updates are unlikely to occur in any pre-defined order. The
shuffled dataset is inserted in batches of 1M edges until the full graph is
built and then deleted101010The vanilla SAGA-Bench does not support edge
deletions. We added deletion support for all representation formats by closely
following the corresponding papers or from their source code if available. in
batches of 1M edges until no edges are left to delete. This batch size is
similar to prior works [12, 10]. Analytics is performed on the graph after
every batch of insertions and deletions. Reported throughputs are the
geometric mean of the per-batch throughputs. GraphTango dynamically switches
between vertex types as edges are inserted/deleted. As discussed in Section
IV, this switching may involve memory allocation/deallocation, copying, or
rehashing. This switching overhead is included in the reported results.

D) Datasets: We have used four real-world datasets in our experiments: Orkut,
LiveJournal, Wiki-topcats (referred as Wiki), and Wiki-talk (referred as
Talk). Orkut and LiveJournal are online social media networks, Wiki is a
dataset of Wikipedia hyperlinks, and Talk is the Wikipedia communications
network. These datasets are part of the SNAP dataset collection [27]. All
these datasets are directed except for Orkut. Properties of these datasets are
given in Table II. Orkut and LiveJournal have a much lower per-batch maximum
degree compared to Wiki and Talk. Consequently, Orkut and LiveJournal are
characterized as short-tailed graphs while Wiki and Talk are heavy-tailed
graphs.

TABLE II: Evaluated Datasets

Dataset | Vertices | Edges |  Max degree1 |  Vertex mapping2
---|---|---|---|---
(million) | (million) | in | out | Type1 | Type2 | Type3
Orkut | 3.0 | 117.2 | 329 | 329 | 27.2% | 38.6% | 34.2%
LiveJournal | 4.8 | 69.0 | 237 | 332 | 63.0% | 26.0% | 11.0%
Wiki | 1.8 | 28.5 | 8,504 | 154 | 57.8% | 33.9% | 8.3%
Talk | 2.4 | 5.0 | 665 | 20,088 | 98.3% | 1.2% | 0.5%

  * 1

Per-batch maximum degree with batch size of 1 million edges

  * 2

For $TH_{0}=7$ and $TH_{1}=32$

E) Algorithms: We used four algorithms in our experiments: i) Breath-First
Search (BFS), ii) Page Rank (PR), iii) Single-Source Shortest Path (SSSP), and
iv) Connected Components (CC). Vertex centric incremental compute model is
used for these algorithms, where the computation is constrained within the
region affected by the update phase instead of the whole graph. The
implementations of these algorithms are directly taken from SAGA-Bench without
any modification.

###  VI-B Analytics and Update Performance

A) Analytics Throughput: Figure 5 shows the analytics throughput of the
representation formats. As mentioned in Section VI-A(C), the analytics phase
is conducted multiple times as we gradually build the graph. Reported values
are the geometric mean of per-batch throughputs. GraphTango outperforms other
approaches in every dataset and algorithm combinations. Compared to the next
best approach (i.e., AdListShared for BFS, SSSP, CC and AdListChunked for PR),
GraphTango provides an avg (max) speedup of 1.1x (1.6x). As all these
approaches are using the exact same algorithm implementation, their relative
performance is primarily determined by their edge traversal efficiency.
Adjacency-list-based approaches perform well in this regard, because their
edge traversal consists of mostly sequential accesses. GraphTango also uses
adjacency lists for medium- and high-degree vertices (Type2 and Type3). For
low-degree vertices (Type1), GraphTango has a better access pattern, as it
requires one less indirection (i.e., does not need pointer chasing to find the
corresponding edge array), thereby offering higher throughput. Stinger,
despite using coarse-grained adjacency lists, suffers due to additional
pointer chasing between edge blocks. Overall, GraphTango provides an avg (max)
speedup of 1.8x (5.1x) over AdListShared, 1.3x (1.6x) over AdListChunked, 2.0x
(2.7x) over Stinger, and 5.2x (14.0x) over DegAwareRHH.

Figure 6: Comparison of update throughputs. Higher is better.

B) Update Throughput: Figure 6 shows the update (edge insertion and deletion)
throughput. Note that the updates are interleaved with analytics phases (see
Section VI-A.C). The algorithm choice of the analytics phase has little impact
on the update throughput, and the reported values are the average across the
four algorithms. Here, GraphTango outperforms other approaches by a large
margin. Adjacency-list-based approaches perform well on short-tailed graphs.
On these graphs, GraphTango provides an avg (max) speedup of 2.5x (2.7x) over
the next best approach AdListShared. On the other hand, hash-based DegAwareRHH
performs best on the heavy-tailed graphs. Interestingly, AdListShared
performed even worse than AdListChunked for heavy-tailed graphs. This is due
to the lock contention of shared-style multithreading on AdListShared. On
heavy-tailed graphs, GraphTango provides an avg (max) speedup of 6.5x (6.6x)
over the next best approach DegAwareRHH. Notably, other approaches are
suitable for either short- or heavy-tailed graphs. GraphTango’s hybrid nature
makes it consistently the best-performing irrespective of the graph’s degree
distribution.

TABLE III: Average Memory Usage (Bytes Per Edge) Dataset | AdList- | AdList- | Stinger | DegAware | GraphTango
---|---|---|---|---|---
Shared | Chunked | RHH
Orkut | 8.8 | 12.0 | 32.7 | 43.8 | 33.6
LiveJournal | 10.2 | 12.9 | 48.9 | 57.0 | 34.6
Wiki | 10.0 | 12.7 | 44.1 | 62.9 | 34.4
Talk | 23.3 | 21.9 | 230.2 | 74.6 | 116.9

###  VI-C Memory Usage

Table III shows the average memory usage per edge. The AdListShared and
AdListChunked are most efficient in terms of memory usage. Compared to
AdListShared - Stinger, DegAwareRHH, and GraphTango require 5.7x, 5.0x, and
3.9x more memory on average, respectively. For DegAwareRHH, the high memory
usage is caused by: i) Sparse storage of edges in hash tables (to reduce
collision), and ii) Robin Hood hashing mechanism that requires storing the
probe distance for each entry. On the other hand, Stinger and GraphTango have
a relatively high initial capacity (16 for Stinger and $TH_{0}$ for
GraphTango) that remains mostly unused for low-degree vertices. This scenario
is especially noticeable for the Talk dataset, where more than 96% of the
vertices have a degree $\leq 3$, leading to high memory usage. One way to
reduce memory usage of GraphTango is to increase the $TH_{1}$ threshold, as
described in Section VI-D.

Figure 7: Impact of $TH_{1}$ threshold on update throughput and memory usage.

###  VI-D Impact of $TH_{1}$ Threshold

Figure 7 shows the impact of the $TH_{1}$ threshold on update throughput and
memory usage. Analytics throughput is not shown because the choice of $TH_{1}$
does not impact the analytics performance. $TH_{1}$ of 16 and 32 provides the
best throughput on three out of the four datasets. We used $TH_{1}$ of 32 in
all other experiments, as it has lower memory usage.

The $TH_{1}$ threshold controls the ratio between Type2 and Type3 vertices.
Increasing $TH_{1}$ maps more higher-degree vertices to Type2 instead of
Type3. As Type2 vertices requires linear search during updates, it eventually
becomes a performance bottleneck for $TH_{1}>32$. On the other hand, Type2
vertices do not require maintaining a hash table and thus require less memory
than Type3. As a result, increasing $TH_{1}$ reduces the memory usage. On
average, increasing $TH_{1}$ from 8 to 512 reduces the memory usage by 1.9x.

The Talk dataset is an outlier showing negligible variation with $TH_{1}$.
This is because, for the Talk dataset, 98.3% of the vertices are mapped to
Type1 (refer to Table II), leaving only 1.7% of the vertices that can be
affected by changing $TH_{1}$.

###  VI-E Impact of Optimizations

TABLE IV: Impact of Optimizations on the Update Throughput (Baseline is the
proposed hybrid format without any optimizations applied)

Configuration | Format | Allocation | Hashing | Speedup
---|---|---|---|---
Scheme | Scheme | STail | HTail
baseline | Hybrid |  malloc2 |  std_map3 | 1.00 | 1.00
next best1 | - | - | - | 0.76 | 0.29
opt pool | Hybrid | proposed |  std_map3 | 1.12 | 1.14
opt hash | Hybrid |  malloc2 | proposed | 1.71 | 1.70
GT_Tessil | Hybrid | proposed |  Tessil4 | 1.40 | 1.60
GT_RHH | Hybrid | proposed |  RHH5 | 1.35 | 1.45
GT_Abseil | Hybrid | proposed |  Abseil6 | 1.34 | 1.43
GraphTango | Hybrid | proposed | proposed | 1.89 | 1.79
DegAwareRHH | DegAware |  malloc2 | RHH | 0.29 | 0.29
DegAwareCFH | DegAware |  malloc2 | proposed | 0.40 | 0.38

  * 1

AdListShared for STail and DegAwareRHH for HTail.

  * 2

glibc version 2.31.

  * 3

std::unordered_map with libstdc++ version 6.0.28.

  * 4

tsl::robin_map from [28], version 1.0.1.

  * 5

Robin Hood hashing implementation from [29], version 3.11.5.

  * 6

Google’s Abseil flat_hash_map version LTS 20211102 [30].

Figure 8: Batch processing time breakdown of DZiG and RisGraph integration.
Lower is better.

The purpose of this section is to isolate the contribution of the proposed
hybrid format as well as the memory allocation and hashing scheme
optimizations. Table IV shows our findings. In this table, the STail and HTail
columns show the normalized update throughput over the baseline configuration
for short-tailed and heavy-tailed graphs, respectively. We show only the
update throughput because the memory pool and hashing optimizations have a
negligible impact on the analytics throughput.

The baseline configuration implements our proposed hybrid format (i.e., Type1,
Type2, and Type3 mapping of vertices) but uses sub-optimal malloc for memory
allocation and std::unordered_map for hashing. We can observe that using only
the hybrid format is sufficient to provide a better performance than the next
best approach (AdListShared for STail and DegAwareRHH for HTail). Compared to
the next best approach, the baseline offers 1.3x (3.4x) higher speedup for
STail (HTail) graphs. The opt pool configuration shows the benefit of the
proposed memory allocation scheme. On average, the proposed pool provides
1.13x better performance over the baseline. On the other hand, the opt hash
configuration shows the benefit of the proposed cache-friendly hashing scheme,
offering 1.71x speedup over std::unordered_map. With both optimizations
enabled, GraphTango provides an average speedup of 1.84x over the baseline.

A valid concern at this point is whether we can combine other hashing schemes
with our hybrid format to get even better performance. To answer this
question, we tried three other open-addressing-based hash-table
implementations: i) GT_Tessil: The Robin Hood hashing variation of Tessil
(tsl::robin_map) [28]. This is the fastest hash table implementation according
to the benchmark results published in [31]. ii) GT_RHH: Another fast
implementation of Robin Hood hashing from [29, 31]. Although it is slightly
slower than Tessil, it consumes significantly less memory. iii) GT_Abseil:
Google’s Abseil flat_hash_map [30, 32]. The max load factors of these
approaches are set equal to ours $(=0.5)$ for a fair comparison. On STail
(HTail) graphs, the proposed hashing scheme provides 1.35x (1.12x) speedup
over GT_Tessil, 1.4x (1.23x) speedup over GT_RHH and 1.41x (1.25x) speedup
over GT_Abseil. Because our hashing scheme tries to minimize cache line
access, it is especially suitable for graph workloads where the hash table is
unlikely to reside in the cache.

Finally, we evaluate whether DegAwareRHH can leverage our hashing scheme to
outperform GraphTango. DegAwareCFH denotes this configuration. DegAwareCFH
provides 1.37x (1.31x) better throughput over the vanilla DegAwareRHH.
However, GraphTango still outperforms it by 4.7x for both STail and HTail
graphs.

###  VI-F Integration with DZiG and RisGraph

This section demonstrates that full-fledged graph processing frameworks can
leverage the GraphTango format to improve their performance further. We
selected two state-of-the-art graph processing frameworks DZiG [15] and
RisGraph [16] for this purpose. We modified their publicly available source
code [33, 34] and replaced their storage format with GraphTango. We run the
datasets on BFS, PR, and SSSP for DZiG. CC is omitted because its
implementation is unavailable in the framework’s repository. For the same
reason, PR is omitted in case of RisGraph.

Figure 8(a) shows the comparison results between DZiG and DZiG+GraphTango.
DZiG internally uses adjacency list as graph storage. For this reason,
analytics time for DZiG and DZiG+GraphTango is similar in most cases.
Interestingly, the insertion time is also comparable in some cases. For
example, LiveJournal and Wiki datasets for BFS. This is because the original
DZiG’s edge insertion does not check for duplicate edges. Therefore, the edge
insertion becomes as simple as adding an element to the end position of an
array 111111There is a flag to enable duplicate edge insertion checking. But
that checking is done by sorting the batch as a pre-processing step, thereby
incurring heavy overhead.. On average, GraphTango provides a 1.9x reduction in
insertion time even though it also checks for duplicate edges. For deletion,
unmodified DZiG performs 6x worse on average. We identified two reasons: i)
Unlike insertions in DZiG that do not search for duplicates, delete operations
require a linear search through the neighbor list, incurring higher runtime
cost, and ii) DZiG performs a quicksort on the batch based on the source and
destination vertex ids to distribute them among the threads. As we use fixed
mapping of vertices in GraphTango, sorting costs are avoided. Overall,
DZiG+GraphTango provides an average of 2.3x reduction in total batch
processing time compared to the original DZiG.

Figure 8(b) shows the comparison between RisGraph and RisGraph+GraphTango.
RisGraph uses a hybrid graph storage format that uses adjacency list for
low/medium degree vertices and adjacency list along with hash table for high
degree vertices. Unlike GraphTango, RisGraph does not differentiate between
low and medium degree vertices and uses the same data structure for both.
Furthermore, RisGraph uses Google’s dense hash map and does not attempt to
minimize the number of cache accesses as GraphTango does with its proposed
cache-friendly hashing scheme. Due to these differences, RisGraph+GraphTango
provides on average 1.5x reduction in total batch processing time compared to
the vanilla RisGraph.

##  VII Conclusions

Existing streaming graph representation formats can only support either short-
tailed or heavy-tailed workloads efficiently. This paper proposes GraphTango,
which aims to solve this issue by adaptively switching formats based on the
current degree of a vertex. We also propose a cache-efficient hashing scheme
and a fast memory pool. These optimizations work in synergy with GraphTango to
provide excellent update and analytics throughput regardless of the graph’s
degree distribution. Our evaluation on the SAGA-Bench showed that on average
(maximum), GraphTango provides 4.5x (6.6x) higher insertion throughput, 3.2x
(5.0x) higher deletion throughput, and 1.1x (1.6x) higher analytics throughput
over the next best approach.

## References

  * [1] Han et al.  Chronos: a graph engine for temporal graph analysis.  In EUROSYS, pages 1–14, 2014.
  * [2] Cheng et al.  Kineograph: taking the pulse of a fast-changing and connected world.  In EUROSYS, pages 85–98, 2012.
  * [3] Compeau et al.  How to apply de bruijn graphs to genome assembly.  Nature biotechnology, 29:987–991, 2011.
  * [4] Zerbino et al.  Velvet: algorithms for de novo short read assembly using de bruijn graphs.  Genome research, 18:821–829, 2008.
  * [5] Grewal et al.  Recservice: Distributed real-time graph processing at twitter.  In HotCloud, 2018.
  * [6] Eksombatchai et al.  Pixie: A system for recommending 3+ billion items to 200+ million users in real-time.  In WWW, pages 1775–1784, 2018.
  * [7] Jounsup Park and Klara Nahrstedt.  Navigation graph for tiled media streaming.  In ICME, pages 447–455, 2019.
  * [8] Braun et al.  Knowledge discovery from social graph data.  Procedia Computer Science, 96:682–691, 2016.
  * [9] Borgman et al.  Drowning in data: digital library architecture to support scientific use of embedded sensor networks.  In JCDL, pages 269–277, 2007.
  * [10] Basak et al.  Saga-bench: Software and hardware characterization of streaming graph analytics workloads.  In ISPASS, pages 12–23, 2020.
  * [11] Ediger et al.  Stinger: High performance data structure for streaming graphs.  In HPEC, 2012.
  * [12] Wole Jaiyeoba and Kevin Skadron.  Graphtinker: A high performance data structure for dynamic graph processing.  In IPDPS, pages 1030–1041, 2019.
  * [13] Iwabuchi et al.  Towards a distributed large-scale dynamic graph data store.  In IPDPSW, pages 892–901, 2016.
  * [14] Andrew McCrabb and Valeria Bertacco.  Optimizing vertex pressure dynamic graph partitioning in many-core systems.  IEEE Transactions on Computers, 70:936–949, 2021.
  * [15] Mariappan et al.  Dzig: Sparsity-aware incremental processing of streaming graphs.  In EUROSYS, pages 83–98, 2021.
  * [16] Feng et al.  Risgraph: A real-time streaming system for evolving graphs to support sub-millisecond per-update analysis at millions ops/s.  In SIGMOD, pages 513–527, 2021.
  * [17] Hu et al.  Graphlily: Accelerating graph linear algebra on hbm-equipped fpgas.  In ICCAD, pages 1–9, 2021.
  * [18] Ham et al.  Graphicionado: A high-performance and energy-efficient accelerator for graph analytics.  In MICRO, pages 1–13, 2016.
  * [19] Sundaram et al.  Graphmat: High performance graph analytics made productive.  arXiv:1503.07241, 2015.
  * [20] Gui et al.  A survey on graph processing accelerators: Challenges and opportunities.  JCS&T, 34:339–371, 2019.
  * [21] Celis et al.  Robin hood hashing.  In SFCS, pages 281–288, 1985.
  * [22] Cormen et al.  Introduction to algorithms.  MIT press, 2009.
  * [23] ISO/IEC JTC 1/SC 22 technical committee.  C++ standard.  https://www.iso.org/standard/79358.html, 2020.
  * [24] Donald E Knuth.  The art of computer programming, volume 3: Searching and sorting.  Addison-Westley Publishing, 1973.
  * [25] Basak et al.  Saga-bench github repository.  https://github.com/abasak24/SAGA-Bench, 2022.
  * [26] Ediger et al.  Stinger github repository.  https://github.com/stingergraph/stinger, 2022.
  * [27] Jure Leskovec and Andrej Krevl.  Snap datasets: Stanford large network dataset collection.  https://snap.stanford.edu/data/, 2014.
  * [28] Thibaut Planchon.  Tessil github repository.  https://github.com/Tessil/robin-map, 2022.
  * [29] Martin Ankerl.  Robin hood hashing github repository.  https://github.com/martinus/robin-hood-hashing, 2022.
  * [30] Google.  Abseil github repository.  https://github.com/abseil/abseil-cpp, 2022.
  * [31] Martin Ankerl.  Hashmap benchmarks.  https://martin.ankerl.com/2019/04/01/hashmap-benchmarks-01-overview/, 2019\.
  * [32] Matt Kulukundis.  Designing a fast, efficient, cache-friendly hash table, step by step.  CPPcon. Standard C++ Foundation, 2017.
  * [33] Mariappan et al.  Dzig: Sparsity-aware incremental processing of streaming graphs.  https://github.com/pdclab/graphbolt/tree/eurosys21-artifact, 2021.
  * [34] Feng et al.  Risgraph github repository.  https://github.com/thu-pacman/RisGraph, 2021.