# Generation of a Single-Cycle Acoustic Pulse:
A Scalable Solution for Transport in Single-Electron Circuits

Junliang Wang  These authors contributed equally to this work.  Univ. Grenoble
Alpes, CNRS, Grenoble INP, Institut Néel, 38000 Grenoble, France  Shunsuke Ota
These authors contributed equally to this work.  Department of Electrical and
Electronic Engineering, Tokyo Institute of Technology, Tokyo 152-8550, Japan
National Institute of Advanced Industrial Science and Technology (AIST),
National Metrology Institute of Japan (NMIJ), 1-1-1 Umezono, Tsukuba, Ibaraki
305-8563, Japan  Hermann Edlbauer  These authors contributed equally to this
work.  Univ. Grenoble Alpes, CNRS, Grenoble INP, Institut Néel, 38000
Grenoble, France  Baptiste Jadot  Univ. Grenoble Alpes, CNRS, Grenoble INP,
Institut Néel, 38000 Grenoble, France  Univ. Grenoble Alpes, CEA, Leti, 38000
Grenoble, France  Pierre-André Mortemousque  Univ. Grenoble Alpes, CNRS,
Grenoble INP, Institut Néel, 38000 Grenoble, France  Univ. Grenoble Alpes,
CEA, Leti, 38000 Grenoble, France  Aymeric Richard  Univ. Grenoble Alpes,
CNRS, Grenoble INP, Institut Néel, 38000 Grenoble, France  Yuma Okazaki
National Institute of Advanced Industrial Science and Technology (AIST),
National Metrology Institute of Japan (NMIJ), 1-1-1 Umezono, Tsukuba, Ibaraki
305-8563, Japan  Shuji Nakamura  National Institute of Advanced Industrial
Science and Technology (AIST), National Metrology Institute of Japan (NMIJ),
1-1-1 Umezono, Tsukuba, Ibaraki 305-8563, Japan  Arne Ludwig  Lehrstuhl für
Angewandte Festkörperphysik, Ruhr-Universität Bochum, Universitätsstraße 150,
44780 Bochum, Germany  Andreas D. Wieck  Lehrstuhl für Angewandte
Festkörperphysik, Ruhr-Universität Bochum, Universitätsstraße 150, 44780
Bochum, Germany  Matias Urdampilleta  Univ. Grenoble Alpes, CNRS, Grenoble
INP, Institut Néel, 38000 Grenoble, France  Tristan Meunier  Univ. Grenoble
Alpes, CNRS, Grenoble INP, Institut Néel, 38000 Grenoble, France  Tetsuo
Kodera  Department of Electrical and Electronic Engineering, Tokyo Institute
of Technology, Tokyo 152-8550, Japan  Nobu-Hisa Kaneko  National Institute of
Advanced Industrial Science and Technology (AIST), National Metrology
Institute of Japan (NMIJ), 1-1-1 Umezono, Tsukuba, Ibaraki 305-8563, Japan
Shintaro Takada  corresponding authors<EMAIL_ADDRESS>
<EMAIL_ADDRESS>National Institute of Advanced Industrial
Science and Technology (AIST), National Metrology Institute of Japan (NMIJ),
1-1-1 Umezono, Tsukuba, Ibaraki 305-8563, Japan  Christopher Bäuerle
corresponding authors<EMAIL_ADDRESS>
<EMAIL_ADDRESS>Univ. Grenoble Alpes, CNRS, Grenoble INP,
Institut Néel, 38000 Grenoble, France

###### Abstract

The synthesis of single-cycle, compressed optical and microwave pulses sparked
novel areas of fundamental research. In the field of acoustics, however, such
a generation has not been introduced yet. For numerous applications, the large
spatial extent of surface acoustic waves (SAW) causes unwanted perturbations
and limits the accuracy of physical manipulations. Particularly, this
restriction applies to SAW-driven quantum experiments with single flying
electrons, where extra modulation renders the exact position of the
transported electron ambiguous and leads to undesired spin mixing. Here, we
address this challenge by demonstrating single-shot chirp synthesis of a
strongly compressed acoustic pulse. Employing this solitary SAW pulse to
transport a single electron between distant quantum dots with an efficiency
exceeding 99%, we show that chirp synthesis is competitive with regular
transduction approaches. Performing a time-resolved investigation of the SAW-
driven sending process, we outline the potential of the chirped SAW pulse to
synchronize single-electron transport from many quantum-dot sources. By
superimposing multiple pulses, we further point out the capability of chirp
synthesis to generate arbitrary acoustic waveforms tailorable to a variety of
(opto)nanomechanical applications. Our results shift the paradigm of
compressed pulses to the field of acoustic phonons and pave the way for a SAW-
driven platform of single-electron transport that is precise, synchronized,
and scalable.

††preprint: APS/123-QED

##  I Introduction

The generation of a compressed pulse marked a paradigm shift in optics [1, 2,
3], enabling the realization of attosecond experiments [4, 5] as well as the
synthesis of arbitrary optical waveforms [6, 7] down to the limit of a single
cycle of light [8]. Similarly, shaped microwave pulses have been widely used
in nuclear magnetic resonance to dynamically control the state of a classical
[9] or a quantum state [10]. Extending this idea to the field of acoustics,
only periodic waveforms with arbitrary shapes have been realized so far [11].
However, to synthesize arbitrary phononic waveforms, it is necessary to
generate an on-demand acoustic pulse in the single-cycle limit.

Propagating phonons in the form of surface acoustic waves (SAWs) are massively
used in the telecommunication industry, and recently, they are finding more
and more impressive applications in quantum science [12, 13, 14, 15, 16]. A
particularly promising example are SAW-driven quantum experiments in solid-
state devices with single flying electrons [17, 18, 19, 20, 21, 22, 23]. Owing
to piezoelectric coupling, a SAW is accompanied by an electric potential that
allows single-shot transport of an electron between distant surface-gate-
defined quantum dots (QD) [17, 18]. The acousto-electric approach allows
highly efficient single-electron transfer along coupled quantum rails
approaching macroscopic scales [22] and in-flight preservation of spin
entanglement [23]. These properties make SAW-driven electron transport a
technique that is promising for proof-of-principle demonstrations of quantum-
computing implementations [24, 25, 15].

However, sound-driven single-electron transport has an intrinsic limitation
related to the large spatial extent of the SAW train. The quantum state of the
flying electron can be disturbed by SAW modulation during the dwell time in
the stationary QDs [21]. Because of the presence of many potential minima
accompanying the SAW (typically hundreds) it is furthermore difficult to
transport the flying electron with accurate timing. To overcome the latter
problem, a triggered SAW-driven sending process has been developed [22].
Requiring one radio-frequency line and one picosecond-voltage-pulse channel
per QD, this method is limited to a few electron sources and thus not
scalable. In addition, the triggering technique introduces unwanted
electromagnetic crosstalk and potential charge excitation. Alternatively,
replacing the periodic SAW train with a single-cycle acoustic pulse would
deliver an elegant sending approach that brings less perturbation and
naturally enables synchronized transport from a basically unlimited number of
sources.

Here, we present a chirp-synthesis technique to generate on demand a single,
strongly compressed acoustic pulse. To determine the shape of the engineered
SAW, we perform time-resolved measurements with a broadband interdigital
transducer (IDT) as SAW detector. By comparison of the experimental data with
numerical simulations based on an impulse-response model, we assess the
reliability of the synthesis method and outline a path toward maximum pulse
compression. We then employ the acousto-electric chirped pulse to transport a
single electron between distant quantum dots and evaluate the transport
efficiency. Triggering the SAW-driven sending process with a picosecond
voltage pulse, we then investigate if the electron is fully confined in the
central minimum of the chirped pulse. Finally, we apply a superposition of
phase-shifted chirp signals to demonstrate the emission of multiple pulses
with precise control on their time delay.

##  II Pulse compression via chirp synthesis

A SAW emitted by an IDT is uniquely determined by its electrode design [26,
27, 28, 29]. Changing the unit cell pattern allows, for instance, the
generation of higher SAW harmonics for the formation of periodic waveforms of
arbitrary shapes [11]. The conceptual generalization of this Fourier-synthesis
approach is the emission of a solitary SAW pulse. It can be achieved by the
so-called chirp IDT whose frequency response is determined by its gradually
changing cell periodicity $\lambda_{n}$. This nonuniform design has been
extensively used in analog electronic filters [30, 31] and in radar
technologies [32]. In quantum applications, this approach has so far been
mainly employed to broaden the IDT’s passband [33]. However, the chirp design
can also be employed in an inverse manner—similar to the formation of an
ultrashort laser pulse [1]—to superpose a quasi-continuum of many elementary
SAWs with gradually changing wavelength to a single, distinct, acoustic pulse.

In this work, we aim at the emission of a solitary SAW pulse approaching the
form of a Dirac $\delta$ function. Mathematically, it is approximated via the
superposition of a discrete set of frequencies $f_{n}$,

$\delta(t)\propto\int_{-\infty}^{\infty}e^{i\;2\pi\cdot f\cdot
t}df\approx\sum_{n=1}^{N}e^{i\;2\pi\cdot f_{n}\cdot t},$ (1)

which is mostly destructive, except around the timing $t=0$ where all
elementary waves are in phase and thus interfere constructively.

The central idea for synthesizing such a SAW pulse with a chirp-IDT design is
to subsequently drive this set of elementary waves with frequencies $f_{n}$
[see Eq. (1)] according to its gradually changing cell periodicity
$\lambda_{n}=v_{\textrm{SAW}}/f_{n}$ – where $v_{\textrm{SAW}}$ indicates the
SAW velocity. Applying an input signal

$V_{\rm S}(t)\propto\sin\left(2\pi\int_{0}^{t}f(\tau)d\tau+\phi_{0}\right),$
(2)

with properly chosen frequency modulation $f(t)$, the chirp transducer allows
us to excite the elementary waves with frequency $f_{n}$ at the right timing
to achieve the desired superposition. Owing to the widely linear SAW
dispersion—see Appendix A—the shape of the emitted pulse remains unchanged
during propagation.

The design of the chirp IDT is determined by the set of frequencies $f_{n}$. A
natural choice for $f_{n}$ is an evenly spaced set,

$f_{n}=f_{1}+(n-1)\cdot\Delta f,\hskip 28.45274pt\Delta
f=\frac{f_{N}-f_{1}}{N-1},$ (3)

leading to the following recurrence relation for the cell periodicity:

$\lambda_{n+1}=\frac{1}{\frac{1}{\lambda_{n}}+\frac{\Delta
f}{v_{\textrm{SAW}}}}$ (4)

With this chirp geometry, maximal pulse compression is achieved by applying an
input signal—see derivation in Appendix B—with frequency modulation that
follows an exponential course:

$f(t)=f_{1}\cdot e^{\Delta f\cdot t}$ (5)

Figure 1: Experimental setup. Schematic of chirp IDT launching a compressed
SAW towards a quantum rail and a subsequent broadband SAW detector. We show a
perspective view on the sample that is realized via metallic surface gates in
a GaAs/AlGaAs heterostructure. Inset: comparison between the periodic SAW
modulation from regular transduction (dotted gray line) with the ideal SAW
profile for electron transport consisting of a single propagating minimum (red
line).  Figure 2: SEM images of the chirp IDT with zooms (insets) in the
regions of large (left panel) and small (right panel) periodicity of the
interlocked electrodes.

##  III Experimental setup

To perform single-electron-transport measurements with the SAW pulse, we
employ the experimental setup sketched in Fig. 1. The sample consists of a
quantum rail that is sandwiched between a chirp IDT and a SAW detector. By
properly driving the chirp transducer with an input signal $V_{\rm{S}}$, a
single propagating SAW minimum is emitted. When the acoustic pulse passes the
quantum rail, the accompanying potential modulation forms a moving QD, which
we use to transport an electron in a single shot from one QD to the other. The
SAW detector that is placed after the quantum rail—see Appendix C—allows us to
time-resolve the SAW profile via the induced voltage $V_{\rm D}$, and thus to
verify its shape in situ.

The experiment is performed at a temperature of about 20 mK in a
${}^{3}\textrm{He}/^{4}\textrm{He}$ dilution refrigerator. We use a Si-
modulation-doped GaAs/AlGaAs heterostructure grown by molecular beam epitaxy
(MBE). The two-dimensional electron gas (2DEG) is located 110 nm below the
surface, with an electron density of $n\approx 2.8\times 10^{11}$ cm-2 and a
mobility of $\mu\approx 9\times 10^{5}$ cm2V-1s-1. Metallic surface gates (Ti
3 nm, Au 14 nm) define the nanostructures. We apply a voltage of 0.3 V on all
Schottky gates during cooldown. At low temperatures, the 2DEG below the
transport channel and the QDs is completely depleted via a set of negative
voltages applied on the surface gates.

The surface electrodes of the IDTs are fabricated using standard electron-beam
lithography with successive thin-film evaporation (metallization Ti 3 nm, Al
27 nm). A detailed fabrication recipe is provided in Appendix D. To reduce
internal reflections at resonance, we employ a double-electrode pattern for
the transducers. All IDTs have an aperture of 30 µm, with the SAW propagation
direction along $[1\bar{1}0]$. The IDTs are designed and simulated with the
homemade open-source Python library “idtpy” [34]. We verify the linearity of
SAW dispersion in the frequency range of 1 to 8 GHz by employing regular
transducers ($\lambda_{n}=\lambda_{0}$) on a GaAs substrate (see Appendix A).
From this investigation, we can deduce the SAW velocity $v_{\rm{SAW}}=(2.81\pm
0.01)$ µm/ns at ambient temperature.

To characterize the frequency response of the transducer, we measure the
transmission $S_{21}$ between two identical IDTs that are opposing each other
via a vector network analyzer (Keysight E5080A). In order to remove parasitic
signals from reflections at the sample boundaries, the transmission data are
cropped in the time domain after Fourier transform in the range of 300 to 600
ns (expected arrival of first transient around 310 ns) and then transformed
back in the frequency domain.

For the time-resolved measurements of the SAW profile, we employ an arbitrary
waveform generator (AWG, Keysight M8195A) to provide the input signal
$V_{\rm{S}}$ of the chirp IDT. We record the induced voltage $V_{\rm D}$ on
the detector IDT via a fast sampling oscilloscope (Keysight N1094B DCA-M). In
order to reinforce the input and detection signals, $V_{\rm S}$ and $V_{\rm
D}$, broadband amplifiers (SHF S126A) are placed along the transmission lines
that are connected to the respective IDT’s. As for the transmission data, we
apply a Fourier filter on the time-resolved data in the range of 0.4 to 3.5
GHz in order to suppress parasitic contributions from internal higher
harmonics of the AWG, the amplifier responses, airborne capacitive coupling,
and standing waves in the rf lines.

##  IV Generation of an acoustic chirped pulse

The synthesis of the strongly compressed acousto-electric pulse is performed
with a chirp transducer as shown via the scanning-electron-microscopy (SEM)
image in Fig. 2. It consists of $N=167$ cells ranging from $f_{1}=$ 0.5 GHz to
$f_{N}=$ 3 GHz with the cell periodicity gradually changing from
$\lambda_{1}\approx$ 5.56 µm to $\lambda_{N}\approx$ 0.92 µm according to Eq.
(4).

The transmission spectrum of the chirp IDT allows us to benchmark its quality
via the shape of the passband. Figure 3 shows transmission data from a
measurement at ambient temperature (black) and the expectation from a delta-
function model [35] (gray; see Appendix E). We observe a continuous spectrum
over a broad frequency range that is defined by the varying finger periodicity
$\lambda_{n}$. The flatness of the chirp IDT’s passband is mainly achieved by
the light electrode material (aluminium) mitigating resonance shifts from mass
loading [26]. The good agreement between experiment and simulation reflects
the well-controlled nanofabrication process.

Figure 3: Frequency response. Transmission measurement between opposing chirp
IDTs (black) with simulation via the delta-function model (gray) and
indications of the passband ranging from $f_{1}\approx$ 0.5 GHz to
$f_{N}\approx$ 3.0 GHz. Note that the transmission bandwidth of the radio-
frequency lines is not considered in the simulation.  Figure 4: Time-resolved
measurements. (a) Trace of detector response for the frequency-modulated input
signal applied on the chirp IDT with $t_{\textrm{S}}\approx 120$ ns. After
initial electromagnetic crosstalk ($t=0$ ns), SAW arrives at the expected
delay time $t_{\textrm{D}}$. (b) Zoom-in of the time window around
$t_{\textrm{D}}$, which shows the detected voltage pulse (black) with impulse-
response simulation (gray) and the corresponding SAW shape (red; with offset
and arbitrary units) derived via deconvolution of the detector response.

Having outlined the basic properties of the chirp IDT, let us now employ it
for single-shot pulse generation. For maximal pulse compression, we apply an
input signal that follows Eq. (2) and (5) with a duration $t_{\rm{S}}$
matching the SAW-propagation time along the transducer, $t_{N}\approx 120$
ns—see Appendix F. The measured time-resolved response on the SAW detector at
room temperature is shown in Fig. 4(a). We observe an initial electromagnetic
crosstalk (at time $t=0$ ns) followed by a SAW-related response that appears
at the expected delay $t_{\rm{D}}$. The clear contrast between the input
signal duration $t_{\rm{S}}$ and the narrow SAW signal confirms the successful
compression. Zooming in on the arrival window [see Fig. 4(b)], we observe the
narrow response which follows the shape expected from the impulse-response
model [36] (see Appendix G). A slight asymmetry occurs due to a phase offset
$\phi_{0}\approx\pi/2$ introduced by the amplifier. Because of the agreement
between experiment and simulation, we can extract the actual SAW shape (red
line with offset) via deconvolution of the detector-response function. We find
that the actual SAW profile has much flatter sidelobes than the signal $V_{\rm
D}$ on the broadband detector.

##  V Single-electron transport

Figure 5: Electron shuttling along quantum rail. (a) SEM image of the quantum
rail consisting of two surface-gate-defined quantum dots (QD) that are
connected via a depleted transport channel. We further show the quantum-point-
contact (QPC) electrometers that are placed next to each QD to sense the
presence of electrons. (b) Time-dependent measurement of the chirped pulse in
the cryogenic setup via the SAW detector (black). The offset red line shows
the corresponding SAW profile extracted via deconvolution of the detector’s
response function. (c) Histogram of jumps in the electrometer current $\Delta
I_{\rm QPC}$ at the receiver QD from 70 000 single-shot measurements after
launching the SAW pulse with (red) and without (gray) precedent loading of an
electron in the source QD. (d) Table of transfer and error probabilities with
QD-occupation code of the events (source before, source after, receiver
before, receiver after). (e) Successful (1001) and failed (1000) transfer
probabilities as a function of the trigger delay $\tau$ of the sending process
with respect to the SAW emission.

To demonstrate the ability of this highly compressed SAW pulse to transport an
electron, let us now employ the 8-µm-long quantum rail. Figure 5(a) shows a
SEM image of the nanoscale device. A QD is located at each end of the
transport channel, serving as a single-electron source and receiver. The
occupancy of the QD is monitored by the variation in the current through a
nearby QPC acting as a highly sensitive electrometer. For each transport
sequence, we first evacuate all electrons in the system and then load one
electron into the source QD (see red point). Second, the chirp IDT is excited
to emit the compressed SAW pulse which then propagates along the quantum rail.
If the SAW is capable of picking up the electron at the source and bringing it
to the receiver, related changes are detected in the electron occupancy of the
source and receiver QDs.

In order to optimize the SAW profile for single-electron transport in a single
moving potential minimum, we exploit the input signal’s phase offset
$\phi_{0}$ [see Eq. (2)] to form an asymmetric chirped pulse. Note that an
increased SAW velocity [37] has to be taken into account for the input signal
at a cryogenic condition. Analyzing the SAW profile with $\phi_{0}\approx
3\pi/2$, we observe a smooth ramp just before the first strongly pronounced
minimum ($t<0$ ns) as shown in Fig. 5(b). With this choice, electron transfer
is suppressed until the arrival of the leading SAW minimum. Employing this
chirped pulse to perform single-shot electron shuttling with many repetitions,
we observe a histogram of QPC-current jumps, $\Delta I_{\rm QPC}$, as shown in
Fig. 5(c). As a reference, we also perform each transport sequence without
loading an electron at the source QD (gray). The comparison of the
electrometer data at the receiver QD shows sufficient contrast to clearly
distinguish transport events. Moreover, the reference data allows us to
quantify the amount of undesired extra electrons injected into the system from
outside (inflow). Figure 5(d) summarizes the transfer probability and the
sources of error (loading, sending, catching and inflow) from 70 000 single-
shot measurements. The overall low error rates indicate a single-electron-
transfer efficiency of $(99.4\pm 0.4)$%, which is similar to the highest value
achieved with regular IDT design [22].

Let us now focus on the question of where exactly within the compressed SAW
pulse the electron is transferred. For this purpose, we employ a fast voltage
pulse injected via a bias tee on a gate of the source QD [see Fig. 5(a)] to
trigger the sending process with the SAW [22]. In this experiment, the
potential landscape of the source QD is set such that the initially loaded
electron is protected when the acoustic wave passes. By triggering a
picosecond voltage pulse, the potential is temporarily lifted to load the
electron into the moving SAW. Sweeping the time delay $\tau$ of this trigger,
we thus successively address each position along the SAW pulse in an attempt
to transfer the electron. Figure 5(e) shows transmission probability data of
such a measurement. We observe three transmission peaks that emerge in
congruence with the potential minima of the SAW profile. The highest transport
probability (code 1001) appears at the first peak ($\tau=0$ ns) that
corresponds to the deepest minimum of the SAW pulse. The extent of 97% sets a
lower limit to the probability that the electron is emitted on arrival of this
moving potential minimum at the source QD.

In order to investigate whether the electron stays within this position as it
propagates along the quantum rail, it is insightful to also look at the
unsuccessful transfer events (code 1000). The strongly increased error at the
third peak of more than 40% indicates that it plays a rather negligible role
since, without a sending trigger, this error is only 0.4%. Estimating an
amplitude of $(19\pm 3)$ meV of the first acoustic minimum—see Appendix H—the
currently employed SAW confinement is slightly below the 95%-confinement
threshold of approximately $24$ meV [38]. Therefore, we cannot exclude
transitions into the second minimum ($\tau\approx 0.4$ ns) during transport.
However, we anticipate reinforcement of single-minimum confinement via
increased input-signal power and enhanced transducer design. We further
evaluate the orbital level spacing by approximating the acoustic minimum to a
parabolic potential [39]. For instance, if the frequency range is raised up to
6 GHz, we find an increase of the energy spacing from 2 meV to 3 meV.
Accordingly, we expect that the reinforcement of the SAW confinement will also
enable the loading of a single electron into the ground state and transport
without excitation [40, 22, 41]—two conditions that are essential for the
realization of SAW-driven flying electron qubits.

##  VI SAW engineering

The wide-ranging linearity of the SAW dispersion opens up a flexible platform
to engineer any nanomechanical waveform using a single chirp IDT. Multiple
$\delta$ pulses can be superposed via overlaid input signals $V_{p}(t)$ with
deliberately chosen delay ($\Delta t_{p}$), phase ($\phi_{p}$), and amplitude
($A_{p}$):

$V(t)=\sum_{p=1}^{P}A_{p}\cdot V_{p}(t+\Delta t_{p},\phi_{p})$ (6)

Following this approach, a sawtooth shape can be achieved, for instance, by
superimposing uniformly delayed pulses with linearly decreasing amplitude. For
the sake of simplicity, let us demonstrate this wave-engineering method by
means of two pulses ($P=2$) with arbitrary delay. A relevant application of
such a synthesis is the sequential transport of a pair of entangled electrons
to observe spin interference patterns [23]. Figure 6 shows the SAW profile
from time-dependent measurements of such an engineered waveform. Two identical
pulses are apparent, and they are separated by the chosen delay $\Delta t$.
Note that the halving in pulse amplitude compared to the single-pulse case
($\Delta t=0$) is expected since the amplitude scales inversely with the
number of superposed signals $P$ (for $\Delta t<t_{N}$). In order to achieve
sufficient amplitude of the engineered waveform, it is thus crucial to
maximize the IDT length (via the number of cells $N$) and the bandwidth
($B=f_{N}-f_{1}$) to achieve maximal pulse compression—see Appendix I. Owing
to the linear SAW dispersion, the shape of the generated pulses is independent
of the delay of the input signals $V_{1}$ and $V_{2}$. The precise time
control of $\delta$ pulses lays the groundwork for on-demand emissions of
arbitrary nanomechanical waveforms.

Figure 6: Acousto-electric wave engineering. Time-resolved measurements from
the SAW detector for an input signal consisting of two superposed pulses with
different time delays $\Delta t=\Delta t_{2}-\Delta t_{1}\in[0,3,6]$ ns.

##  VII Summary and outlook

In conclusion, we have demonstrated an original SAW-engineering method to
generate in a single shot a solitary acousto-electric $\delta$ pulse. We
implemented the concept using a chirp transducer operating in the frequency
band of 0.5 to 3 GHz. Our investigations showed that chirp synthesis is a
highly controlled technique allowing reliable acoustic pulse shaping by
design. Demonstrating a single-electron transport efficiency exceeding 99%, we
confirmed robust potential confinement for SAW-driven quantum transport.
Confirming the confinement location during flight, this acoustic chirped
wavefront thus represents the scalable alternative for synchronized and
unambiguous SAW-driven single-electron transport from multiple sources. This
technique is compatible with all the essential building blocks developed for
SAW-driven flying electron qubits such as on-demand single-electron
partitioning [22], time-of-flight measurements [38] and electron-spin transfer
[21, 23]. The nonuniform IDT design enables the possibility to engineer
arbitrary combinations of superposed pulses having high relevance for
experiments where multiple charges are transferred successively [23].
Accordingly, we expect that the chirp approach opens up new routes for quantum
experiments on interference and entanglement exploiting spin and charge degree
of freedom with single flying electrons [15, 24, 25].

We highlighted that chirp synthesis is readily applicable to other
piezoelectric platforms such as LiNbO3 or ZnO. Further enhancement of the
power density is achievable by integrating the concept of unidirectional [27,
28] or focusing [29] designs in the chirp transducer. Additionally, the
frequency band and thus pulse compression is easily adjustable via the
electrode periodicity of the chirp IDT.

Finally, owing to the wide-ranging applications of propagating phonons in
fundamental research [12, 13, 14, 15, 16, 42, 43, 44, 45, 46], the
demonstrated acoustic pulse is not restricted to the field of quantum
information processing. In spintronics, for instance, our chirp synthesis
technique opens up the way for on-demand generation of spin-current pulses in
nonferromagnetic materials [44]. Employing two compressed acoustic pulses with
a controlled time delay and opposite phases, it further allows investigations
on the spin-current formation in the time domain. Moreover, since SAW can
create skyrmions in thin-film samples without Joule heating [45], a solitary
acoustic pulse could be the key to create a single skyrmion and to perform
manipulations at the single-shot level. In metrology applications, the
accuracy of SAW-driven electron pumps [47] is currently limited by the
overlapping between the electromagnetic crosstalk and the acoustic signal
[48]. Emitting compressed pulses with a controlled repetition rate, such
single-electron pumps can be significantly enhanced in performance and easily
operated in parallel without additional radio-frequency lines. Similarly,
phonons can also stimulate single-photon emission in a hybrid quantum-
dot–nanocavity system [49]. Since each SAW period contributes to the creation
of photons, our technique would allow on-demand single-photon emission with
precise timing. In summary, analogous to the advantages of using solitary
optical [1, 2, 3, 4, 5, 6, 7, 8] and microwave pulses [9, 10], we anticipate
that the presented compression technique will open new routes for fundamental
research employing nanoscale acoustics.

###### Acknowledgements.

J.W. acknowledges the European Union’s Horizon 2020 research and innovation
program under the Marie Skłodowska-Curie Grant Agreement No. 754303. A.R.
acknowledges financial support from ANR-21-CMAQ-0003, France 2030, Projet
QuantForm-UGA. T.K. and S.T. acknowledge financial support from JSPS KAKENHI
Grant No. 20H02559. C.B. acknowledges funding from the European Union’s H2020
research and innovation program under Grant Agreement No. 862683 and from the
French Agence Nationale de la Recherche (ANR), project QUABS
ANR-21-CE47-0013-01. A.D.W., and A.L. acknowledge support from TRR
160/2-Project B04, DFG 383065199, the German Federal Ministry of Education and
Research via QR.X Project 16KISQ009, and the DFH/UFA CDFA-05-06.

##  Appendix A LINEARITY OF SAW DISPERSION

Figure 7: SAW-dispersion relation for aluminium IDTs on a GaAs substrate. We
show the resonance frequency for IDTs having different periodicity—here
expressed as wave number $1/\lambda_{0}=k/2\pi$. The points are extracted from
Gaussian fits of distinct peaks in the transmission data (reflection data for
the case of 8 GHz) from a network analyzer measurement.

To test the linearity of the SAW dispersion for the frequency range of
interest, we investigate the resonant response of six regular aluminium IDTs
on a GaAs substrate in transmission measurements at room temperature. As a
starting point for the IDT designs, we consider the SAW velocity
$v_{\textrm{SAW}}^{\textrm{Au}}\approx 2.77$ µm/ns for gold transducers, WHICH
is well known from former SAW-driven charge transport experiments. For the
resonance frequencies, we target $f_{0}\in[1,2,2.77,3,4,8]$ GHz, giving a
periodicity of the respective IDTs of
$\lambda_{0}=v_{\textrm{SAW}}^{\textrm{Au}}/f_{0}$. Because of the reduced
mass loading of aluminium electrodes, we expect a slightly increased resonance
frequency of the respective transducers. Figure 7 shows a plot of the
resonance frequencies of the fabricated IDTs as a function of the wave number
$k=2\pi/\lambda_{0}$. The data show a linear dispersion in the investigated
frequency range of 1 to 8 GHz. Performing a linear least-squares fit of the
data (see dashed line), we can deduce the SAW velocity for aluminium IDTs on
GaAs via its slope as $v_{\textrm{SAW}}=(2.81\pm 0.01)$ µm/ns.

##  Appendix B DERIVATION OF EXPONENTIAL FREQUENCY MODULATION

In order to have in-phase interference of the $N$ elementary waves at the IDT
boundary, the frequency modulation $f(t)$ of the input signal must introduce
the $n$th elementary SAW with the right delay, $t_{n}$. For an evenly spaced
set of frequencies [Eq. (3)] with a single period per step $n$, we obtain the
excitation times:

$t_{n}=\sum_{m=1}^{n}\frac{1}{f_{m}}.$ (7)

The resulting sum can then be expressed in terms of the digamma function
$\Psi$:

$t_{n}=\sum_{m=1}^{n}\frac{1}{f_{1}+(m-1)\cdot\Delta
f}=\frac{\Psi\left(\frac{f_{1}}{\Delta
f}+n\right)-\Psi\left(\frac{f_{1}}{\Delta f}\right)}{\Delta f}.$ (8)

Since $f_{1}/\Delta f\gg 1$, this function approaches a logarithmic course:

$\Psi(x)\overset{x\gg 1}{\approx}\ln(x).$ (9)

Multiplying Eq. (8) by $\Delta f$ and additionally applying an exponential
function, we thus obtain

$e^{\Delta f\cdot t_{n}}=(\underbrace{f_{1}+(n-1)\cdot\Delta f}_{f_{n}}+\Delta
f)/f_{1}$ (10)

Which brings us to the desired frequency modulation of the input signal:

$f_{n}=f_{1}\cdot e^{\Delta f\cdot t_{n}}-\Delta f\overset{f_{1}\gg\Delta
f}{\approx}f_{1}\cdot e^{\Delta f\cdot t_{n}}$ (11)

as expressed in its continuous form $f(t)$ in Eq. (5).

##  Appendix C BROADBAND DETECTION

Owing to the inverse piezoelectric effect, when a SAW passes through another
IDT, an electric signal is induced that can be recorded by a fast sampling
oscilloscope. To optimize the response of the detector IDT, it is necessary to
design the transducer according to the expected bandwidth of the input signal.

Generally, the frequency response of a regular IDT with $N$ unit cells and
resonant frequency $f_{0}$ follows approximately a sinc function [26]:

$H(f)\propto\frac{\sin{(\pi N(f-f_{0})/f_{0})}}{\pi N(f-f_{0})/f_{0}}$ (12)

Then the full width at half maximum (FWHM) can be derived as $f_{0}/N$.
Because of the large bandwidth of the chirped pulse, we minimize the number of
detector electrodes to one, giving $N=1.5$ with a pair of neighboring grounded
fingers. Figure 8 shows the passband for this geometry as a function of
$f_{0}$. In order to reliably resolve the SAW response particularly at 3 GHz
and below, we have chosen a detector periodicity of $\lambda_{0}=1$ µm
($f_{0}\approx 2.81$ GHz).

Figure 8: Detection bandwidth. Pass band of a regular IDT with $N=1.5$. The
shaded area indicates the FWHM of the transmission peak. The vertical double-
headed arrow indicates the employed resonance frequency of the detector IDT,
$f_{0}\approx 2.81$ GHz.

##  Appendix D NANOFABRICATION RECIPE

The IDTs were fabricated according to the steps listed in Table 1. A
metallization ratio of 0.4–0.5 was chosen for all of the interlocked
transducer fingers. At electron-beam lithography, a proximity correction was
applied for all IDTs.

Table 1: Fabrication procedure Number | Method | Description
---|---|---
1 | Ultrasonic cleaning | 10 min in acetone + 10 min in isopropanol (IPA)
2 | Warming on hotplate | 115$\rm\;{{}^{\circ}C}$ for 2 min + wait 5 min to cool down
3 | Spin coating of resist | PMMA 3%, 4000 rpm, 4000 rpm/s, 60 s + bake at 180$\rm\;{{}^{\circ}C}$ for 5 min
4 | Electron-beam lithography | Writing of IDT structures. Equipment: Nanobeam nB5
5 | Development of resist | 35 s in MIBK:IPA 1:3 + 1 min in IPA
6 | Oxygen-plasma cleaning | With a power of 10 W for a duration of 10 s
7 | Metal deposition | Ti 3 nm at 0.05 nm/s + Al 27 nm at 0.10 nm/s
8 | Lift-off | N-methyl-2-pyrrolidone (NMP) at 80$\rm\;{{}^{\circ}C}$ for at least 1 h
9 | Ultrasonic cleaning | 20 s in acetone + 20 s in IPA
10 | Spin coating of resist | S1805, 6000 rpm, 6000 rpm/s, 30 s + bake at 115$\rm\;{{}^{\circ}C}$ for 1 min
11 | Laser lithography | Writing of contacts and ground plane
12 | Development of resist | 1 min in Microposit developer:DI H2O 1:1 + 1 min in DI H2O
13 | Metal deposition | Ti 20 nm at 0.10 nm/s + Au 80 nm at 0.15 nm/s
14 | Lift-off | At least 30 min in acetone

##  Appendix E DELTA-FUNCTION MODEL

The simplest way of modeling the IDT response is to approximate the output as
a superposition of elementary waves that are emitted with delay times $t_{n}$
at discrete point sources located at the finger positions $x_{n}$. In this
picture, the response function for a certain IDT geometry can be written in
the time domain as a sum of Dirac delta functions located at each finger
location:

$h(t)=\sum_{n=0}^{N}P_{n}\cdot\delta(t-t_{n})$ (13)

where $P_{n}\in\pm 1$ is the polarity of the $n$th finger that indicates
connection to the input electrode or to the ground. In general, the SAW
response $y(t)$ can be mathematically expressed as a convolution of an input
signal $V(t)$ with the IDT geometry $h(t)$ acting as a filter:

$y(t)=(V\ast h)(t).$ (14)

The IDT response in the frequency domain can then be calculated by the Fourier
transform of $y(t)$ via application of the convolution theorem as

$\hat{y}(\omega)=\hat{V}(\omega)\cdot\hat{h}(\omega),$ (15)

where $\hat{V}$ and $\hat{h}$ indicate, respectively, the Fourier transform of
$V$ and $h$. Considering a continuous input signal, $V(t)\propto
e^{i\;\omega_{0}\cdot t}$, we obtain

$\hat{V}(\omega)=\int_{-\infty}^{\infty}e^{i\;(\omega_{0}-\omega)\cdot
t}dt\propto\delta(\omega_{0}-\omega),$ (16)

Which brings us to

$\hat{y}(\omega)\propto\hat{h}(\omega).$ (17)

To obtain the frequency response of a certain IDT geometry within the delta-
function model, we can thus directly evaluate the Fourier transform of Eq.
(1):

$\displaystyle\hat{y}(\omega)\propto\sum_{n=0}^{N}P_{n}\int_{-\infty}^{\infty}\delta(t-t_{n})\cdot
e^{i\;\omega\cdot t}dt=\sum_{n=0}^{N}P_{n}\cdot e^{i\;\omega\cdot t_{n}},$
(18)

where $t_{n}=x_{n}/v_{\textrm{SAW}}$ is determined by the SAW velocity
$v_{\textrm{SAW}}$ and the IDT’s finger positions $x_{n}$.

##  Appendix F COMPENSATION WITH INPUT SIGNAL FOR PULSE COMPRESSION

For optimum acoustic chirped pulse compression, it is important that the input
signal matches the IDT response, $V_{\rm S}(t)=h(t)$. Typically, however, the
fabricated IDTs show slight deviations from the design, which leads to minor
changes in the IDT response. To compensate this irregularity for maximal pulse
compression, we exploit the input signal parameters such as $t_{\rm{S}}$ or
$f_{1}$ [see Eq. (5)]. Figure 9 shows the broadening effect for input signals
with duration $t_{\textrm{S}}$ deviating from the ideal parameter, $t_{N}$.
When employing a nonideal input signal [$V_{\rm{S}}(t)\neq h(t)$], each
frequency is excited with a certain phase delay between them, resulting in
broadening of the SAW pulse. Note that the impulse-response model is also able
to predict the influence of nonideal input signals. Owing to this compensation
method, chirp synthesis becomes more robust against small variations due to
the limits of precision in IDT fabrication.

Figure 9: Nonideal input signals. Time-resolved measurements of the SAW
response for an input signal with duration deviation of
$t_{\textrm{S}}-t_{N}\in[-10,-5,0,5,10]$ ns. The semitransparent line in the
background shows the course expected from an impulse-response model.

##  Appendix G IMPULSE RESPONSE-MODEL

Figure 10: Construction of the impulse response of IDTs. We show examples of
the response function $h(t)$ (vertical axis) in comparison to the finger
positions for (a) a regular IDT and (b) a chirp IDT.

A more accurate description of the IDT geometry can be achieved by the so-
called impulse-response model. Such precision is particularly important when
describing the time response of irregular IDT geometries. In contrast to the
aforementioned delta-function model, the time response of an IDT, $h(t)$, is
defined by a continuous frequency-modulated function:

$h(t)\propto\sin\left(2\pi\int_{0}^{t}f(\tau)d\tau\right).$ (19)

To construct $h(t)$ via the instantaneous frequency response $f(t)$, one-half
cycle of a sine wave is placed between two electrodes with opposite polarity
(half period). This construction rule is schematically shown in Fig. 10 via
the examples of a regular and a chirp IDT. For a regular IDT, each period is
the same, giving a constant frequency response $f(t)=f_{0}$. On the other
hand, for an irregular IDT geometry, $f(t)$ changes depending on the finger
positions. In the case of a chirp IDT, its response function $h(t)$ is
identical to the ideal input signal $V_{\rm S}(t)$ introduced in Eq. (2) and
(5).

In order to calculate the surface displacement by a SAW, $y(t)$, resulting
from a certain input signal $V_{\rm S}(t)$, one can now simply calculate the
convolution with the IDT response $h(t)$—compare Eq. (14). However, the
experimental data that is obtained in a time-resolved measurement also
contains information of the detector IDT response, $h_{\textrm{D}}(t)$. To
compare the time-resolved data to a simulation of an impulse-response model,
it is necessary to also convolve $y(t)$ with the detection filter
$h_{\textrm{D}}(t)$:

$V_{\textrm{D}}(t)\propto(y\ast h_{\textrm{D}})(t)=(V_{\textrm{S}}\ast h\ast
h_{\textrm{D}})(t)$ (20)

The amplitude of the piezoelectrically introduced voltage $V_{\textrm{D}}$
depends on several parameters such as the efficiency of the electromechanical
coupling or the circuit impedance network. In this work, we only take into
account the geometries of the input IDT and detector IDT, $h$ and
$h_{\textrm{D}}$, and the input signal $V_{\rm S}(t)$. In order to reproduce
the experimental data, we use the amplitude and the SAW velocity as fitting
parameters. The SAW shapes shown in Figs. 4(b) and 5(b) (red and offset)
correspond to the actual SAW profile $y(t)$, where the detector’s response is
not taken into account.

##  Appendix H AMPLITUDE COMPARISON OF CHIRPED PULSE TO SAW STEMMING FROM
REGULAR TRANSDUCER

Figure 11: Time-resolved measurements on regular IDT. (a) Trace of detector
response for resonant input signal that is applied for a duration
$t_{\textrm{S}}=40$ ns on the regular IDT. The SAW arrives with expected delay
$t_{\textrm{D}}$ after initial electromagnetic crosstalk. (b) Zoom in SAW
region at $t_{\textrm{D}}$.  Figure 12: Effect of design parameters. SAW
shapes of impulse-response model for changing IDT parameters. (a) Varying
maximal frequency $f_{N}$ with $f_{1}=0.5$ GHz and $t_{N}=40$ ns. (b)
Increasing IDT length $t_{N}$ with $f_{1}=0.5$ GHz and $f_{N}=3.5$ GHz. (c)
Reducing minimum frequency $f_{0}$ with $f_{N}=7$ GHz and $t_{N}=40$ ns.

Let us estimate the amplitude of the chirped pulse employed in this work with
the SAW stemming from the regular IDT employed in the time-of-flight
measurements reported in a previous work [38]. Such a comparison is valid
since the chirped pulse experiment was conducted under the same experimental
conditions of the flight-time measurement—same fabrication and measurement
setup. The regular IDT consists of $N=111$ cells of period $\lambda_{0}=1$ µm.
The resonance frequency that we expect for this reference IDT is
$f_{0}=v_{\rm{SAW}}/\lambda_{0}\approx 2.81$ GHz. Figure 11 shows time-
dependent measurements of a SAW train emitted from the regular transducer with
a resonant input signal of duration $t_{\rm{S}}\approx t_{N}$. This
measurement is executed under the same conditions at ambient temperature as
the chirp synthesis shown in Fig. 4. The data show that the chirp signal
reaches approximately 80% of the signal stemming from the SAW train of the
regular IDT. Comparing to the input power of 24.61 dBm sent from ambient
temperature to the cryogenic setup with the chirp IDT to the power-to-energy
conversion performed in the time-of-flight measurements, we estimate an
amplitude of $(19\pm 3)$ meV for the compressed SAW pulse.

##  Appendix I ANALYSIS OF DESIGN PARAMETERS

The agreement between a time-dependent SAW experiment and simulation enables
us to predict the shape of the acoustic pulse for different design parameters
of the chirp IDT. Figure 12 shows the evolution of the pulse shape for
variations of the maximal frequency $f_{N}$, the IDT length $t_{N}$, and the
minimum frequency $f_{1}$. The simulations allow us to formulate the following
design rules for acousto-electric pulse generation with a chirp IDT:

  1. 1.

The pulse narrows with increasing $f_{N}$ [see Fig. 12(a)].

  2. 2.

The amplitude scales with the number of unit cells $N$ [see Fig. 12(b)].

  3. 3.

Side lobes can be mitigated by reducing $f_{1}$ [see Fig. 12(c)]

To form a clean acousto-electric pulse with strong potential confinement, it
is thus important to design a chirp IDT with a maximized length and frequency
span. In this regard, we suspect that a single-finger design could be superior
to the double-finger pattern employed in this work, since the gain in pulse
compression will likely outweigh losses from internal reflections.

## References

  * Strickland and Mourou [1985] D. Strickland and G. Mourou, Compression of amplified chirped optical pulses, Optics Communications 56, 219 (1985).
  * Jones  _et al._ [2000] D. J. Jones, S. A. Diddams, J. K. Ranka, A. Stentz, R. S. Windeler, J. L. Hall, and S. T. Cundiff, Carrier-envelope phase control of femtosecond mode-locked lasers and direct optical frequency synthesis, Science 288, 635 (2000).
  * Udem  _et al._ [2002] T. Udem, R. Holzwarth, and T. W. Hänsch, Optical frequency metrology, Nature 416, 233 (2002).
  * Brabec and Krausz [2000] T. Brabec and F. Krausz, Intense few-cycle laser fields: Frontiers of nonlinear optics, Reviews of Modern Physics 72, 545 (2000).
  * Cavalieri  _et al._ [2007] A. L. Cavalieri, E. Goulielmakis, B. Horvath, W. Helml, M. Schultze, M. Fieß, V. Pervak, L. Veisz, V. S. Yakovlev, M. Uiberacker, A. Apolonski, F. Krausz, and R. Kienberger, Intense 1.5-cycle near infrared laser waveforms and their use for the generation of ultra-broadband soft-x-ray harmonic continua, New Journal of Physics 9, 242 (2007).
  * Shelton  _et al._ [2001] R. K. Shelton, L.-S. Ma, H. C. Kapteyn, M. M. Murnane, J. L. Hall, and J. Ye, Phase-coherent optical pulse synthesis from separate femtosecond lasers, Science 293, 1286 (2001).
  * Rausch  _et al._ [2008] S. Rausch, T. Binhammer, A. Harth, J. Kim, R. Ell, F. X. Kärtner, and U. Morgner, Controlled waveforms on the single-cycle scale from a femtosecond oscillator, Optics Express 16, 9739 (2008).
  * Krauss  _et al._ [2010] G. Krauss, S. Lohss, T. Hanke, A. Sell, S. Eggert, R. Huber, and A. Leitenstorfer, Synthesis of a single cycle of light with compact erbium-doped fibre technology, Nature Photonics 4, 33 (2010).
  * Freeman [1998] R. Freeman, Shaped radiofrequency pulses in high resolution NMR, Progress in Nuclear Magnetic Resonance Spectroscopy 32, 59 (1998).
  * Vandersypen and Chuang [2005] L. M. K. Vandersypen and I. L. Chuang, NMR techniques for quantum control and computation, Reviews of Modern Physics 76, 1037 (2005).
  * Schülein  _et al._ [2015] F. J. R. Schülein, E. Zallo, P. Atkinson, O. G. Schmidt, R. Trotta, A. Rastelli, A. Wixforth, and H. J. Krenner, Fourier synthesis of radiofrequency nanomechanical pulses with different shapes, Nature Nanotechnology 10, 512 (2015).
  * Delsing  _et al._ [2019] P. Delsing, A. N. Cleland, M. J. A. Schuetz, J. Knörzer, G. Giedke, J. I. Cirac, K. Srinivasan, M. Wu, K. C. Balram, C. Bäuerle, T. Meunier, C. J. B. Ford, P. V. Santos, E. Cerda-Méndez, H. Wang, H. J. Krenner, E. D. S. Nysten, M. Weiß, G. R. Nash, L. Thevenard, C. Gourdon, P. Rovillain, M. Marangolo, J.-Y. Duquesne, G. Fischerauer, W. Ruile, A. Reiner, B. Paschke, D. Denysenko, D. Volkmer, A. Wixforth, H. Bruus, M. Wiklund, J. Reboud, J. M. Cooper, Y. Fu, M. S. Brugger, F. Rehfeldt, and C. Westerhausen, The 2019 surface acoustic waves roadmap, Journal of Physics D: Applied Physics 52, 353001 (2019).
  * Gustafsson  _et al._ [2014] M. V. Gustafsson, T. Aref, A. F. Kockum, M. K. Ekström, G. Johansson, and P. Delsing, Propagating phonons coupled to an artificial atom, Science 346, 207 (2014).
  * Satzinger  _et al._ [2018] K. J. Satzinger, Y. P. Zhong, H.-S. Chang, G. A. Peairs, A. Bienfait, M.-H. Chou, A. Y. Cleland, C. R. Conner, É. Dumur, J. Grebel, I. Gutierrez, B. H. November, R. G. Povey, S. J. Whiteley, D. D. Awschalom, D. I. Schuster, and A. N. Cleland, Quantum control of surface acoustic-wave phonons, Nature 563, 661 (2018).
  * Bäuerle  _et al._ [2018] C. Bäuerle, D. C. Glattli, T. Meunier, F. Portier, P. Roche, P. Roulleau, S. Takada, and X. Waintal, Coherent control of single electrons: a review of current progress, Reports on Progress in Physics 81, 056503 (2018).
  * Hsiao  _et al._ [2020] T.-K. Hsiao, A. Rubino, Y. Chung, S.-K. Son, H. Hou, J. Pedrós, A. Nasir, G. Éthier-Majcher, M. J. Stanley, R. T. Phillips, T. A. Mitchell, J. P. Griffiths, I. Farrer, D. A. Ritchie, and C. J. B. Ford, Single-photon emission from single-electron transport in a SAW-driven lateral light-emitting diode, Nature Communications 11, 10.1038/s41467-020-14560-1 (2020).
  * Hermelin  _et al._ [2011] S. Hermelin, S. Takada, M. Yamamoto, S. Tarucha, A. D. Wieck, L. Saminadayar, C. Bäuerle, and T. Meunier, Electrons surfing on a sound wave as a platform for quantum optics with flying electrons, Nature 477, 435 (2011).
  * McNeil  _et al._ [2011] R. P. G. McNeil, M. Kataoka, C. J. B. Ford, C. H. W. Barnes, D. Anderson, G. A. C. Jones, I. Farrer, and D. A. Ritchie, On-demand single-electron transfer between distant quantum dots, Nature 477, 439 (2011).
  * Stotz  _et al._ [2005] J. A. H. Stotz, R. Hey, P. V. Santos, and K. H. Ploog, Coherent spin transport through dynamic quantum dots, Nature Materials 4, 585 (2005).
  * Sanada  _et al._ [2013] H. Sanada, Y. Kunihashi, H. Gotoh, K. Onomitsu, M. Kohda, J. Nitta, P. V. Santos, and T. Sogawa, Manipulation of mobile spin coherence using magnetic-field-free electron spin resonance, Nature Physics 9, 280 (2013).
  * Bertrand  _et al._ [2016] B. Bertrand, S. Hermelin, S. Takada, M. Yamamoto, S. Tarucha, A. Ludwig, A. D. Wieck, C. Bäuerle, and T. Meunier, Fast spin information transfer between distant quantum dots using individual electrons, Nature Nanotechnology 11, 672 (2016).
  * Takada  _et al._ [2019] S. Takada, H. Edlbauer, H. V. Lepage, J. Wang, P.-A. Mortemousque, G. Georgiou, C. H. W. Barnes, C. J. B. Ford, M. Yuan, P. V. Santos, X. Waintal, A. Ludwig, A. D. Wieck, M. Urdampilleta, T. Meunier, and C. Bäuerle, Sound-driven single-electron transfer in a circuit of coupled quantum rails, Nature Communications 10, 10.1038/s41467-019-12514-w (2019).
  * Jadot  _et al._ [2021] B. Jadot, P.-A. Mortemousque, E. Chanrion, V. Thiney, A. Ludwig, A. D. Wieck, M. Urdampilleta, C. Bäuerle, and T. Meunier, Distant spin entanglement via fast and coherent electron shuttling, Nature Nanotechnology 16, 570 (2021).
  * Barnes  _et al._ [2000] C. H. W. Barnes, J. M. Shilton, and A. M. Robinson, Quantum computation using electrons trapped by surface acoustic waves, Physical Review B 62, 8410 (2000).
  * Schuetz  _et al._ [2015] M. Schuetz, E. Kessler, G. Giedke, L. Vandersypen, M. Lukin, and J. Cirac, Universal quantum transducers based on surface acoustic waves, Physical Review X 5, 031031 (2015).
  * Morgan [2007] D. Morgan,  _Surface acoustic wave filters : with applications to electronic communications and signal processing_ (Academic Press, Amsterdam London, 2007).
  * Ekström  _et al._ [2017] M. K. Ekström, T. Aref, J. Runeson, J. Björck, I. Boström, and P. Delsing, Surface acoustic wave unidirectional transducers for quantum applications, Applied Physics Letters 110, 073105 (2017).
  * Dumur  _et al._ [2019] É. Dumur, K. J. Satzinger, G. A. Peairs, M.-H. Chou, A. Bienfait, H.-S. Chang, C. R. Conner, J. Grebel, R. G. Povey, Y. P. Zhong, and A. N. Cleland, Unidirectional distributed acoustic reflection transducers for quantum applications, Applied Physics Letters 114, 223501 (2019).
  * de Lima  _et al._ [2003] M. M. de Lima, F. Alsina, W. Seidel, and P. V. Santos, Focusing of surface-acoustic-wave fields on (100) GaAs surfaces, Journal of Applied Physics 94, 7848 (2003).
  * Court [1969] I. Court, Microwave acoustic devices for pulse compression filters, IEEE Transactions on Microwave Theory and Techniques 17, 968 (1969).
  * Atzeni  _et al._ [1975] C. Atzeni, G. Manes, and L. Masotti, Programmable signal processing by analog chirp-transformation using SAW devices, in  _1975 Ultrasonics Symposium_ (IEEE, 1975) pp. 371–376.
  * Klauder  _et al._ [1960] J. R. Klauder, A. C. Price, S. Darlington, and W. J. Albersheim, The theory and design of chirp radars, Bell System Technical Journal 39, 745 (1960).
  * Weiß  _et al._ [2018] M. Weiß, A. L. Hörner, E. Zallo, P. Atkinson, A. Rastelli, O. G. Schmidt, A. Wixforth, and H. J. Krenner, Multiharmonic frequency-chirped transducers for surface-acoustic-wave optomechanics, Physical Review Applied 9, 014004 (2018).
  * Junliang-Wang [2022] Junliang-Wang, Junliang-wang/idtpy: First release (2022).
  * Tancrell and Holland [1971] R. Tancrell and M. Holland, Acoustic surface wave filters, Proceedings of the IEEE 59, 393 (1971).
  * Hartmann and Abbott [1988] C. Hartmann and B. Abbott, A generalized impulse response model for SAW transducers including effects of electrode reflections, in  _IEEE 1988 Ultrasonics Symposium Proceedings._ (IEEE, 1988).
  * Powlowski  _et al._ [2019] M. Powlowski, F. Sfigakis, and N. Y. Kim, Temperature dependent angular dispersions of surface acoustic waves on GaAs, Japanese Journal of Applied Physics 58, 030907 (2019).
  * Edlbauer  _et al._ [2021] H. Edlbauer, J. Wang, S. Ota, A. Richard, B. Jadot, P.-A. Mortemousque, Y. Okazaki, S. Nakamura, T. Kodera, N.-H. Kaneko, A. Ludwig, A. D. Wieck, M. Urdampilleta, T. Meunier, C. Bäuerle, and S. Takada, In-flight distribution of an electron within a surface acoustic wave, Applied Physics Letters 119, 114004 (2021).
  * Ciftja [2009] O. Ciftja, Classical behavior of few-electron parabolic quantum dots, Physica B: Condensed Matter 404, 1629 (2009).
  * Kataoka  _et al._ [2009] M. Kataoka, M. R. Astley, A. L. Thorn, D. K. L. Oi, C. H. W. Barnes, C. J. B. Ford, D. Anderson, G. A. C. Jones, I. Farrer, D. A. Ritchie, and M. Pepper, Coherent time evolution of a single-electron wave function, Physical Review Letters 102, 156801 (2009).
  * Ito  _et al._ [2021] R. Ito, S. Takada, A. Ludwig, A. Wieck, S. Tarucha, and M. Yamamoto, Coherent beam splitting of flying electrons driven by a surface acoustic wave, Physical Review Letters 126, 070501 (2021).
  * Midolo  _et al._ [2018] L. Midolo, A. Schliesser, and A. Fiore, Nano-opto-electro-mechanical systems, Nature Nanotechnology 13, 11 (2018).
  * Yokoi  _et al._ [2020] M. Yokoi, S. Fujiwara, T. Kawamura, T. Arakawa, K. Aoyama, H. Fukuyama, K. Kobayashi, and Y. Niimi, Negative resistance state in superconducting NbSe 2 induced by surface acoustic waves, Science Advances 6, 10.1126/sciadv.aba1377 (2020).
  * Kobayashi  _et al._ [2017] D. Kobayashi, T. Yoshikawa, M. Matsuo, R. Iguchi, S. Maekawa, E. Saitoh, and Y. Nozaki, Spin current generation using a surface acoustic wave generated via spin-rotation coupling, Physical Review Letters 119, 077202 (2017).
  * Yokouchi  _et al._ [2020] T. Yokouchi, S. Sugimoto, B. Rana, S. Seki, N. Ogawa, S. Kasai, and Y. Otani, Creation of magnetic skyrmions by surface acoustic waves, Nature Nanotechnology 15, 361 (2020).
  * Chen  _et al._ [2021] F. Chen, X. Ge, W. Luo, R. Xing, S. Liang, X. Yang, L. You, R. Xiong, Y. Otani, and Y. Zhang, Strain-induced megahertz oscillation and stable velocity of an antiferromagnetic domain wall, Physical Review Applied 15, 014030 (2021).
  * Cunningham  _et al._ [2000] J. Cunningham, V. I. Talyanskii, J. M. Shilton, M. Pepper, A. Kristensen, and P. E. Lindelof, Journal of Low Temperature Physics 118, 555 (2000).
  * Kataoka  _et al._ [2006] M. Kataoka, C. J. B. Ford, C. H. W. Barnes, D. Anderson, G. A. C. Jones, H. E. Beere, D. A. Ritchie, and M. Pepper, The effect of pulse-modulated surface acoustic waves on acoustoelectric current quantization, Journal of Applied Physics 100, 063710 (2006).
  * Weiß  _et al._ [2016] M. Weiß, S. Kapfinger, T. Reichert, J. J. Finley, A. Wixforth, M. Kaniber, and H. J. Krenner, Surface acoustic wave regulated single photon emission from a coupled quantum dot–nanocavity system, Applied Physics Letters 109, 033105 (2016).


# Four Algorithms on the Swapped Dragonfly

###### Abstract

A Swapped Dragonfly with $M$ routers per group and $K$ global ports per router
is denoted $D3(K,M)$. A Swapped Dragonfly with $K$ and $M$ restricted is
studied in this paper. There are four cases. In each case the resulting
Swapped Dragonfly has a special utility:

  * •

If $K=L^{2}$, an $LM\times LM$ matrix product can be performed in $LM$ rounds.
An $n\times n$ matrix product may be performed in $n^{2}/LM$ rounds. Each
round takes four router hops.

  * •

If $K=ks$ and $M=ms$ an all-to-all exchange may be performed in $KM^{2}/s$
rounds. An all-to-all exchange of size $n\geq KM^{2}$ may be performed in
$n^{2}/KM^{2}s$ rounds.

  * •

If $K=2^{k}$ and $M=2^{m}$, a dilation three emulation of the $(k+2m)$
dimension Boolean hypercube exists. An ascend-descend algorithm may be
performed at twice the cost on the hypercube.

  * •

$D3(K,M)$ contains $M$ adjacent depth four edge-disjoint spanning trees.
Equipped with a synchronized source-vector packet header, it can perform $n$
broadcast in $3n/M$ rounds.

The rounds in these algorithms are free of link conflicts. These results are
compared with algorithms on a hypercube. Comparisons with the fully populated
Dragonfly are also made.These results are more applicable than the special
cases because $D3(K,M)$ contains emulations of every Swapped Dragonfly with
$J\leq K$ and/or $L\leq M$.

The Swapped Dragonfly is a new approach to the Dragonfly concept. It behaves
much like a three-dimensional mesh. The underlying graph is defined before the
network is defined. The underlying graph of a Dragonfly is not defined until
ports are identified on routers and links are defined by connections with
ports.

Richard Draper 111Center for Computing Sciences, Institute for Defense
Analyses, Bowie, MD

rndrape<EMAIL_ADDRESS>
Keywords: Swapped Interconnection Network, Matrix Product, All-to-all,
Universal Exchange, Boolean Hypercube, Ascend-descend algorithm, Broadcast,
Edge-disjoint spanning tree.

##  1 Introduction

This paper presents algorithms which can be performed on a Swapped Dragonfly
interconnection network more efficiently than they can be performed on a
fully-populated Dragonfly interconnection network. A knowledge of a Swapped
Dragonfly [5] and a fully populated Dragonfly [11] is assumed. (The term
”interconnection network” is elided hereafter.) A fully-populated Dragonfly
will be called a Maximal Dragonfly. The information about a Maximal Dragonfly
pertinent to this discussion is not generally available so explanations will
be given when necessary.

The Swapped Dragonfly [5] is an interconnection network having $KM^{2}$
routers. Routers have coordinates $(c\bmod K,d\bmod M,p\bmod M)$. Connectivity
is given by:

$\begin{array}[]{clclclcl}&&&&(c,d,p)&\stackrel{{\scriptstyle
l}}{{\longleftrightarrow}}&(c,d,p^{\prime})&\textrm{ and}\\\
&&&&(c,d,p)&\stackrel{{\scriptstyle
g}}{{\longleftrightarrow}}&(c^{\prime},p,d)\end{array}.$

Note the swap of $d$ and $p$. These are referred to as local and global
connections, respectively. Conceptually the network is made up of $K$ cabinets
containing $M$ drawers. Each drawer222A Dragonfly group is synonymous with a
drawer. has $M$ routers. There are $K$ global ports and $M-1$ local ports on
each router. Connections are bidirectional. The local connections connect the
routers in a drawer in a complete graph. The Swapped Dragonfly is denoted
$D3(K,M)$.

The routers of a Maximal Dragonfly and a Swapped Dragonfly are identical. A
Maximal Dragonfly has $KM^{2}+M$ routers. Routers have coordinates
$(g,p),0\leq g<KM+1$ and $1\leq p<M$. The network is constructed from groups
(a.k.a drawers) consisting of $M$ routers connected in a complete graph. The
$K$ global ports of the routers are used to connect groups to one-another such
that the groups are connected in a complete graph of order $KM+1$. The
underlying graph of the network is a graph called a replacement graph [8] of a
complete graph of order $M$ in a complete graph of order $KM+1$ . There are an
enormous number of ways to construct a replacement graph [6], but only one way
has been used in the design of an actual machine [1],[2]. This is the one to
which the term Maximal Dragonfly in this paper refers. It is denoted
$MDF(K,M)$.

$D3(K,M)$ is treated as a packet switching network using source-vector
routing. At $(c,d,p)$ a source-vector $(\gamma,\pi,\delta)$ produces the path

$\begin{array}[]{clclclclclcl}(c,d,p)&\stackrel{{\scriptstyle\delta}}{{\longrightarrow}}&(c,d,p+\delta)&\stackrel{{\scriptstyle\gamma}}{{\longrightarrow}}&(c+\gamma,p+\delta,d)&\stackrel{{\scriptstyle\pi}}{{\longrightarrow}}&(c+\gamma,p+\delta,d+\pi)\\\
\end{array}$

The following four properties of $D3(K,M)$ were established in [5] and will be
referred to in this paper.

  1. 1.

Simultaneously, every router can send a packet with header
$(\gamma,\pi,\delta)$ without link conflicts. The result is a permutation of
the routers.

  2. 2.

The routers of $D3(K,M)$ with $c$ in a set of size $J<K$ and $p$ in a set of
size $L<M$ are connected in a closed sub-network isomorphic333Isomorphism is
used here to mean dilation one emulation. to $D3(J,L)$.

  3. 3.

If $\gamma\neq\gamma^{\prime},\delta\neq\delta^{\prime}$,and
$\pi\neq\pi^{\prime}$ two routers can simultaneously send packets with headers
$(\gamma,\pi,\delta)$ and $(\gamma^{\prime},\pi^{\prime},\delta^{\prime})$
without link conflicts.

  4. 4.

$D3(K,M)$ scales linearly in $K$ and quadratically in $M$.

This paper examines four special cases of the Swapped Dragonfly;
$D3(K^{2},M),D3(ks,ms)$, $D3(2^{k},2^{m})$ and $D3(K,M)$ with synchronizing
header $[b;\gamma,\pi,\delta]$. Each is useful for a particular algorithm. On
$D3(K^{2},M)$ vector-matrix multiply takes one round of four hops with two
off-and-ons to calculate products and accumulate sums. The algorithm can be in
place or out of place. On $D3(ks,ms)$ an all-to-all exchange takes only
$KM^{2}/s$ rounds. $D3(2^{k},2^{m})$ emulates a $k+2m$ Boolean-hypercube with
maximal dilation three and average dilation two. $D3(K,M)$ with synchronizing
header can perform $M$-broadcasts in one round of five router hops.
$D3(2^{k},2^{m})$ with synchronizing header can emulate $(k+2m)$ Boolean
hypercube with uniform dilation four.

Property 2 of $(D3(K,M)$ makes it possible to use these special Swapped
Dragonflies ”inside” a general $D3(K,M)$ for a range of values of $K$ and $M$
at a cost of some of the algorithm’s performance.

##  2 $D3(K^{2},M)$

$D3(K^{2},M)$ may be viewed as a $K\times K$ array of $M\times M$ blocks. The
index set for such an array is $\\{(s,t,u,v),0\leq s,\ t<K\textrm{ and }0\leq
u,\ v<M\\}$. The index set $(s,t,u,v)$ is assigned to $(c,d,p)=(s+tK,u,v)$.
The arithmetic is done $\bmod\ K^{2}$ and canonical values are chosen as
representatives of equivalence classes. A $KM\times KM$ matrix stored in this
way can be transposed in a single global hop $\gamma=(s+th-(t+sK))$.

A row vector $(s,u)$ refers to $(s,*,u,*)$ where $*$ denotes all possible
values of the coordinate. The term vector will refer to the index set or to a
$KM$-vector stored at the index set. A column vector $(t,v)$ refers to
$(*,t,*,v)$. Note in $D3(K^{2},M)$ a row vector $(s,u)$ is stored at (nodes
attached to) $(s+*K,u,*)$ and a column vector $(t,v)$ is stored at
$(*+tK,*,v)$. Note that a vector is stored on $KM$ routers.

###### Theorem 1

On $D3(K^{2},M)$ a $KM\times KM$ matrix product takes $KM$ rounds. Each round
takes $4$ network hops and two off and ons.

Proof: To form the product, $VA$, of a row vector $V$ at $(s,u)$ and an
$RM\times RM$ matrix $A$ on $D3(K^{2},M)$ two phases are required. The first
is to bring the row vector into juxtaposition with the columns of $A$ so that
$V_{t,v}A_{t,t^{\prime},v,v^{\prime}}$ can be computed. The second phase is to
accumulate these values at the row vector $(s,u)$. The result is an in-place
algorithm.

The first phase is done by broadcasting element $(t,v)$ at row $(s,u)$ to all
locations in row (t,v,) of $A$:

$(s+tk,u,v)\stackrel{{\scriptstyle
G}}{{\longrightarrow}}(t+*K,v,u)\stackrel{{\scriptstyle
L}}{{\longrightarrow}}(t+*K,v,*)\ \forall(t,v).$ (2.1)

The first broadcast is over all global ports of $(s+tk,u,v)$. The second
broadcast is over all local ports of $(t+sK,v,u)\forall s$. If
$(t,v)\neq(t,v_{1})$, there are no link conflicts in 2.1 because the center
routers are all distinct. If $t\neq t_{1}$ the center routers are in different
cabinets. If $v\neq v_{1}$ the center routers are in different drawers.
Therefore, $KM$ broadcasts can occur simultaneously. The first phase is
completed in two network hops. That is, row $(s,u)$ can be brought into
juxtaposition with every column of $A$ in two network hops. The juxtaposed
pairs hop off, are multiplied, and the product hops on. A path in 2.1 has the
form:

$(s+tK,u,v)\stackrel{{\scriptstyle
g}}{{\longrightarrow}}(t+t^{\prime}K,v,u)\stackrel{{\scriptstyle
l}}{{\longrightarrow}}(t+t^{\prime}K,v,v^{\prime}).$ (2.2)

The accumulation phase of the algorithm requires $(t,t^{\prime},v,v^{\prime})$
to map to $(s,t,u,v)$ for all $(t^{\prime},v^{\prime})$. The path 2.3 reverses
path 2.2,

$(t+t^{\prime}K,v,v^{\prime})\stackrel{{\scriptstyle
l}}{{\longrightarrow}}(t+t^{\prime}K,v,u)\stackrel{{\scriptstyle
g}}{{\longrightarrow}}(s+tK,u,v)\ \forall(t^{\prime},v^{\prime}).$ (2.3)

If $(t_{1},v_{1})\neq(t,v)$ the path

$(t_{1}+t^{\prime}K,v_{1},v^{\prime}_{1})\stackrel{{\scriptstyle
l}}{{\longrightarrow}}(t_{1}+t^{\prime}K,v_{1},u)\stackrel{{\scriptstyle
g}}{{\longrightarrow}}(s+t_{1}K,u,v_{1})$

does not conflict with 2.3 because the center routers are distinct. Therefore,
the path can be followed simultaneously for all $(t,v)$. $M$ values arrive at
$(t+t^{\prime}K,v,u)$ after the local step. They hop off, are accumulated and
the partial sum hops on. $K$ partial sums arrive at $(s+tK,u,v)$ after the
global step. They hop off and are accumulated. The value is
$\sum_{t,v}V_{t,v}A_{t,t^{\prime},v,v^{\prime}}$ which is element
$(t^{\prime},v^{\prime})$ of the vector-matrix product. A matrix multiply
takes $KM$ rounds.

The vector-matrix multiply takes one round consisting of four network hops and
two off-and-ons to perform arithmetic. The time is $4t_{w}+2t_{s}$, where
$t_{w}$ denotes router latency and $t_{s}$ is time for the on-and-off. It is
presented as an in-place algorithm. By modifying $s$ and $u$ in the last two
hops, it can be converted to an out of place algorithm. $\Box$

The expected situation for this algorithm is an $n$-vector $V$ and a $n\times
n$ matrix $A$ with $n\geq KM$. Let $X=n/KM$. There is an $X$ subvector
$V_{s,t,u,v}$ and an $X\times X$ submatrix $A_{t,t^{\prime},v,v^{\prime}}$ for
all $(t,t^{\prime},v,v^{\prime});(s,u)$ is fixed. The broadcast path 2.1 is
used $X$ times to bring all $V_{t,v,i}$ into juxtaposition with the columns
$A_{t,t^{\prime},v,v^{\prime},i,i^{\prime}}$. The $X$ vector $V_{t,v,i}$ hops
off the network so that the vector-matrix product
$\sum_{i}V_{t,v,i}A_{t,t^{\prime},v,v^{\prime},i,i^{\prime}}$ can be computed.
(This was a scalar product when $n=KM$.) The result is
$(VA)_{t,t^{\prime},v,v^{\prime},i^{\prime}}$. For each
$(t,t^{\prime},v,v^{\prime})$ it is an $X$ vector. These are accumulated using
path 2.3 $X$ times for each $(t,t^{\prime},v,v^{\prime})$. The result is an
$X$ vector at $(s,t,u,v)$. The $n$ vector $(s,*,u,*)$ of these $X$ vectors is
$VA$. The vector multiply takes $n/KM$ rounds. The matrix multiply takes
$n^{2}/KM$ rounds because the vector multiply must be used $n$ times. There is
a cost for the $X\times X$ product which is independent of the network cost.

###### Theorem 2

On $D3(K^{2},M)$ an $n\times n$ matrix product with $n>>KM$ takes $n^{2}/KM$
rounds. Each round takes $(4t_{w}+2t_{s})$ time where $t_{w}$ is router
latency and $t_{s}$ is time for off-and-on.

It is possible to transfer this algorithm to a $KM\times KM$ matrix on
$D3(K,M)$. It requires storing $(s,t,u,v)$ at $(s,u,v)\ \forall t$. The memory
requirements are increased by a factor of $K$ at every router. A row vector
$(s,u)$ is stored as $K$-tuples at $(s,u,*)$ and a column vector $(t,v)$ is
stored at $(*,*,v)$ but only one entry of the vector is at each $(c,d,v)$. A
vector-matrix multiply takes $K$ rounds and a matrix multiply takes $K^{2}M$
rounds.

If $(L+1)^{2}>K>L^{2}$, it is faster to do a vector-matrix multiply on
$D3(L^{2},M)$ than on $D3(K,M)$ because a vector of length $KM$ takes $K/L$
rounds on $D3(L^{2},M)$ and $K$ rounds on $D3(K,M)$. This procedure is made
possible by property $2$ of the Swapped Dragonfly.

The following table presents the network cost of matrix multiplication
algorithms. The notation is $n\times n$ matrices with $P$ processors. The
Cannon algorithm[3] was originally done on a $\sqrt{P}\times\sqrt{P}$ mesh.
The other algorithms are on a Boolean hypercube with $P$ nodes. DNS refers to
Dekel, Nassimi, and Sahni [4]; HJE refers to Ho, Johnsson and Edleman [9]; and
GS refers to Gupta and Sudayappan[7]. A version of the DNS algorithm appears
in both HJE and GS. These algorithms divide the hypercube into
$\sqrt{P}\times\sqrt{P}$ mesh. The $\log{P}$ term in two of the algorithms
comes about by using an all-to-all algorithm due to Ho, Johnsson and
Edelman[9] which will be discussed in the last section. On $D3(L,M),P=LM^{2}$.
The table shows that the result on $D3(K^{2},M)$ is in keeping with results on
other topologies. Only network costs appear and $t_{w}$ represents network
latency.

$\begin{array}[]{llll}\vspace{.05in}&D3(K^{2},M)&&4t_{w}n^{2}/\sqrt{P}\\\
\vspace{.05in}&\textrm{Cannon}&&2t_{w}n^{2}/\sqrt{P}\\\
\vspace{.05in}&\textrm{HJE}&&2t_{w}n^{2}/\sqrt{P}\ \log{P}\\\
\vspace{.05in}&\textrm{DNS}&&2t_{w}n^{2}/\sqrt{P}\\\
\vspace{.05in}&\textrm{GS}&&3t_{w}n^{2}/P^{2/3}\log{P}\\\
\vspace{.05in}&\textrm{DNS}&&4t_{w}n^{2}/P^{2/3}\\\ \end{array}$

##  3 $D3(ks,ms)$

###### Theorem 3

On the Swapped Dragonfly, $D3(ks,ms)$, an all-to-all exchange among $n\geq
KM^{2}$ nodes can be performed in $n^{2}/KM^{2}s$ rounds.

Proof: In $\boldsymbol{Z}\bmod M,\ s$ generates a subgroup
$G=\\{0,s,\cdots,(m-1)s\\}$. $G$ has $s$ cosets. Denote them
$[0],\cdots,[s-1]$. An analogous statement applies to $K$. An example is
instructive. If $m=5\textrm{ and }s=3\textrm{ then }G=\\{0,3,6,9,12\\}\textrm{
and a coset }[t]\textrm{ is }t+G$;

$\begin{array}[]{llcc}$$&[0]&=&\\{0,3,6,\hskip 2.84526pt9,12\\}\\\
&[1]&=&\\{1,4,7,10,13\\}\\\ &[2]&=&\\{2,5,8,11,14\\}\end{array}$

Notice that the cosets partition $\boldsymbol{Z}\bmod M$ into three disjoint
sets and that the columns partition it into five disjoint sets. The second
partition is called a _dual_ partition.

Consider the following array which is called a _disagreeable array_ (DA).

$\begin{array}[]{ccccccc}i&&0&1&\cdots&s-1\\\ \gamma&&[0]&[1]&\cdots&[s-1]\\\
\pi&&[0]&[1]&\cdots&[s-1]\\\ \delta&&[0]&[1]&\cdots&[s-1]\end{array}$

Each column contains $km^{2}$ vectors $(\gamma,\pi,\delta);k\textrm{ values of
}\gamma,m\textrm{ values of }\pi,\textrm{and }m\textrm{ values of }\delta$. If
$i\neq j$ and $(\gamma,\pi,\delta)$ is a vector from column $i$ and
$(\gamma^{\prime},\pi^{\prime},\delta^{\prime})$ is a vector from column $j$
then $\gamma\neq\gamma^{\prime},\pi\neq\pi^{\prime},\textrm{ and
}\delta\neq\delta^{\prime}$. Therefore, every router can simultaneously send
packets on the vector paths $(\gamma,\pi,\delta)$ and
$(\gamma^{\prime},\pi^{\prime},\delta^{\prime})$ without link conflicts by
property 3. If one vector is taken from each column of the array, every router
can simultaneously send $s$ packets without link conflict. This is denoted
$(lgl)^{s}$ and is a round of the algorithm being developed here. It takes $3$
hops. There are $km^{2}$ vectors in each column of the DA. Therefore, there
are $km^{2}$ rounds $(lgl)^{s}$ delivering $km^{2}s$ packets. Note that each
vector is used only once in this process.

Cyclically shifting row $\pi$ one place to the left produces a new DA. No
vector in the new array appeared in the previous array. Suppose
$(\gamma,\pi,\delta)$ is in the original array and
$(\gamma^{\prime},\pi^{\prime},\delta^{\prime})$ is in this array. If
$\pi=\pi^{\prime},(\gamma,\delta)\neq(\gamma^{\prime},\delta^{\prime})$
because $\pi$ and $\pi^{\prime}$ are in the same coset so $(\gamma,\delta)$
and $(\gamma^{\prime},\delta^{\prime})$ are in different cosets. If
$(\gamma,\delta)=(\gamma^{\prime},\delta^{\prime})$ then $\pi$ and
$\pi^{\prime}$ are in different cosets. Therefore, this new array produces
$km^{2}$ rounds $(lgl)^{s}$ delivering $km^{2}s$ packets to a different set of
destinations. A series of $s^{2}$ left shifts of the bottom two rows produces
$s^{2}$ distinct DAs. Each yields $km^{2}s$ vectors in $km^{2}$ rounds
$(lgl)^{s}$. The entire set is $km^{2}s^{3}=KM^{2}$ in $KM^{2}/s$ rounds. If
$n=XKM^{2},K=ks$ and $M=ms$, an all-to-all exchange between $n$ nodes take
$X^{2}KM^{2}/s=n^{2}/KM^{2}s$ rounds. $\Box$

To convert this argument into an algorithm it is necessary to specify the
order in which elements are chosen from the cosets in a $DA$. A single column
of the first DA has the form:

$\begin{array}[]{clcccccc}&\gamma&[i]&i&i+s,&\cdots,&i+(k-1)s\bmod K\\\
&\pi&[j]&j&j+s,&\cdots,&j+(m-1)s\bmod M\\\
&\delta&[k]&k&k+s,&\cdots,&k+(m-1)s\bmod M\end{array}$

The left shifts are determined by $\phi=\mu+\nu s,0\leq\phi<s^{2}$. Row $\pi$
of the array is shifted left $\mu$ times and row $\delta$ is shifted left
$\nu$ times. Selecting the entries of a vector amounts to choosing an entry of
the partion/dual partition array. The choice made is in the same position fpr
each column of the DA. The following converts this observation to an
algorithm. The entries of a vector used in a round selected from a DA are
determined by $\lambda=a+bm+cm^{2},0\leq\lambda<km^{2}$. The vector
$(\gamma,\pi,\delta)$ is taken from location $c$ of the $\gamma$ row, $a$ of
the $\pi$ row and $b$ of the $\delta$ row. This algorithm is referred to as
the doubly-parallel all-to-all algorithm. It has $KM^{2}/s$ rounds. If $K$ and
$M$ are relatively prime it reduces to the all-to-all algorithm in [5] that
takes $KM^{2}$ rounds.

The doubly parallel algorithm can be employed even if $K$ and $M$ are
relatively prime by finding $J<K$ and $L<M$ for which $J$ and $L$ have a
common factor. As soon as an all-to-all involves $X>1$ items at every router,
the cost is multiplied by $X^{2}$. If $K$ and $M$ are relatively prime, going
from $D3(K,M)$ to $D3(ks,ms)$ for $K>ks$ and $M>ms$ will produce a doubly-
parallel algorithm with fewer than $KM^{2}$ rounds if $KM^{2}<sJL^{2}$ because

$\frac{JL^{2}}{s}\left(\frac{KM^{2}}{JL^{2}}\right)^{2}<KM^{2}\ \textrm{ iff
}\ \frac{KM^{2}}{s}\left(\frac{KM^{2}}{JL^{2}}\right)<KM^{2}\ \textrm{ iff }\
\frac{KM^{2}}{JL^{2}}<s.$

This generally works if $K-J$ and $M-L$ are small. For example, if $K=7$ and
$M=16$, $J=5$, $L=15$, and $s=5$ then $KM^{2}/JL^{2}=1.59$ so the doubly-
parallel algorithm on $KM^{2}$ objects run on $D3(J,L)$ has
$225\times(1.59)^{2}=569$ rounds which is far less than $1792$ rounds on
$D3(7,16)$.

Johnsson and Ho [10] developed an all-to-all on a Boolean hypercube of $P$
processors with network time $t_{w}P/2$. For a set of size $n\geq P$ the time
is $n^{2}/2P$. On $D3(ks,ms)$ the network time is $n^{2}/Ps.$

The doubly-parallel algorithm can be pipelined in several ways. The round
schedules are

$\begin{array}[]{lcccccccccccccccccc}&&&(l&g&l&)^{s}\\\ &1&&&(l&g&l&)^{s}\\\
&&&&&(l&g&l&)^{s}\\\ &&&&&&&&\ddots\\\ &&&(l&g&l&)^{s}\\\ &2&&&(l&g&l&)^{s}\\\
&&&&&&&(l&g&l&)^{s}\\\ &&&&&&&&&&\ddots\\\ \\\ &&&(l&g&l&)^{s}\\\
&3&&&&&(l&g&l&)^{s}\\\ &&&&&&&&&\ddots\end{array}$

The first is a cost one schedule, the second is cost 2, and the third is cost
$3$. It is obvious that Schedules $2$ and $3$ can be used without link
contention. Therefore, an all-to-all algorithm runs in time $2KM^{2}/s$ or
$3KM^{2}/s$ if $K=ks$ and $M=ms$.

Clearly, there is a potential for intraround conflicts between every other row
in schedule $1$. Schedule $1$ can be used because of the care with which $\pi$
and $\delta$ were chosen. Suppose row $\pi$ of the original DA is left-shifted
$\mu$ places. Let $t^{\prime}=t+\mu\bmod s$. Column $t$ of the new DA contains
$\\{t^{\prime}+0,t^{\prime}+s,\dots,t^{\prime}+(m-1)s\\}$ in row $\pi$.
Suppose $a$ determines which element is to be selected from each cell of row
$\pi$. After the shift $t^{\prime}+as$ is selected from column $t$. That is,
the set of $s$ values of $\pi$ being selected for a round of the all-to-all
algorithm is $\\{t^{\prime}+a,t^{\prime}+a+1,\dots,t^{\prime}+a+s-1\\}$. This
is a cell of the dual partition of the coset partition of $s$ in
$\boldsymbol{Z}\bmod M$. This is also true of the set of $\delta s$ in a
round. Therefore, a conflict of $\delta(i)$ with $\pi(i+2)$ in Schedule $1$
means that the set of $\pi^{\prime}s$ of round $i$ is equal to the set of
$\delta s$ of round $i+2$. A single delay eliminates the conflict.

Here is an example of what happens using the earlier example for $\pi$ and
$\delta$. $\gamma$ can be ignored because the only possible conflict does not
involve $\gamma$. Suppose $(\mu,\nu)=(0,2)$ and $(a,b)=(1,2)$. The DA is

$\begin{array}[]{lcccl}i&0&1&2\\\ \pi&\\{0,3,6,\hskip
4.2679pt9,12\\}&\\{1,4,7,10,13\\}&\\{2,5,8,11,14\\}\\\
\delta&\\{2,5,8,11,14\\}&\\{0,3,6,\hskip
5.69054pt9,12\\}&\\{1,4,7,10,13\\}\end{array}$

$\begin{array}[]{lcccccccc}(a,b)&&&3\textrm{ vectors in round
}(\mu,\nu,a,b)&\vspace{5mm}\hfil\\\ (1,2)&\left(\begin{matrix}\pi\\\
\delta\end{matrix}\right)=&\left(\begin{matrix}{3}\\\
{8}\end{matrix}\right)&\left(\begin{matrix}{4}\\\
{6}\end{matrix}\right)&\left(\begin{matrix}{5}\\\ {7}\end{matrix}\right)\\\
\\\ (2,2)&&\left(\begin{matrix}{6}\\\
{8}\end{matrix}\right)&\left(\begin{matrix}{7}\\\
{6}\end{matrix}\right)&\left(\begin{matrix}{8}\\\ {7}\end{matrix}\right)\\\
\\\ (3,2)&&\left(\begin{matrix}{9}\\\
{8}\end{matrix}\right)&\left(\begin{matrix}{10}\\\
{6}\end{matrix}\right)&\left(\begin{matrix}{11}\\\ {7}\end{matrix}\right)\\\
\\\ (4,2)&&\left(\begin{matrix}{12}\\\
{8}\end{matrix}\right)&\left(\begin{matrix}{13}\\\
{6}\end{matrix}\right)&\left(\begin{matrix}{14}\\\
{7}\end{matrix}\right)&&b=a+2\bmod M\end{array}$

Note that $\pi$ in row $(2,2)$ and $\delta$ in round $(4,2)$ take the same set
of values. In Schedule $1$ this causes a conflict, actually $3$ conflicts.
However, each row of vectors is sent simultaneously so a one hop delay
resolves the conflict. The condition $b=a+2\bmod m$ occurs $m$ times.
Therefore, for each DA a delay occurs $km$ times in $km^{2}$ rounds. There are
$s^{2}$ DA’s in the algorithm, so in $km^{2}s^{2}=KM^{2}/s$ rounds there are
$kms^{2}=KM$ delays. Some delays will be successive as rows $(1,2)$ and
$(3,2)$ demonstrate. Schedule $1$ can only be used if $s\leq M/2$ because
every round uses $2s$ local links.

The preceding discussion has proven the following: If $K=ks$ and $M=ms$, then

Using Schedule $1$, if $s\leq M/2$ the doubly-parallel algorithm takes time
$((KM^{2}/s+KM)/s)t_{w}$. Using Schedule $2$ the doubly-parallel algorithm
takes $(2KM^{2}/s)t_{w}$ and is conflict free. Using Schedule $3$, the doubly-
parallel algorithm takes time $3KM^{2}t_{w}/s$ and is conflict free.

A $MDF(K,M)$ has $(KM+1)M$ routers. $M$ and $(KM+1)$ are relatively prime so
an algorithm like this is not possible. A partially populated Dragonfly with
$KM^{2}$ groups may be able to exploit the idea.

If $s=1$ this theorem reduces to an algorithm originally occurring in [5]. The
algorithm can be implemented on a fully populated Dragonfly provided the
connectivity of groups in the Dragonfly is done properly [6].

##  4 $D3(2^{k},2^{m})$ and The Swapped Boolean Hypercube

The Abelian groups used to enumerate routers and ports do not have to be
cyclic groups. For example, if $M=16$ the group can be $\oplus\mathbb{Z}\bmod
2$ which is Boolean algebra on the $4$ bit quantities. If $c$ and $p$ do not
use the same kind of group, the condition that $M$ and $K$ have a common
factor is replaced by the condition that the group used for $c$ and the group
used for $p$ have subgroups of the same size.

The Swapped Boolean Hypercube, $SBH(k,m)$, is a graph with $2^{k+2m}$ nodes.
It’s address space is a set of $k+2m$ long bit strings that are partitioned
into three fields $(c,d,p)$. The field $c$ is the high order $k$ bits, $p$ is
the low order $m$ bits and $d$ is the middle $m$ bits. If $p$ and $p^{\prime}$
differ by one bit $i,(c,d,p)$ is connected to $(c,d,p^{\prime})$. This link is
denoted $\pi_{i}$ and is called a local link. If $c$ and $c^{\prime}$ differ
by bit $i$, there is a link denoted $\gamma_{i}$ connecting $(c,d,p)$ to
$(c^{\prime},p,d)$. Note the swap of $p$ and $d$. There is one additional link
which connects $(c,d,p)$ to $(c,p,d)$. It is denoted $Z$. If $p=d$ there is no
link $Z$. All links are bidirectional. The nodes of $SBH(k,m)$ are of degree
$k+m$.

The bit exchange between $(c,d,p)$ and another node depends upon the field the
bit is in. The table gives the bit exchanges.

$\begin{array}[]{llc}field&\\\
c&(c,d,p)\stackrel{{\scriptstyle\gamma_{i}}}{{\longrightarrow}}(c^{\prime},p,d)\stackrel{{\scriptstyle
Z}}{{\longrightarrow}}(c^{\prime},d,p)\\\ d&(c,d,p)\stackrel{{\scriptstyle
Z}}{{\longrightarrow}}(c,p,d)\stackrel{{\scriptstyle\pi_{i}}}{{\longrightarrow}}(c,p,d^{\prime})\stackrel{{\scriptstyle
Z}}{{\longrightarrow}}(c,d^{\prime},p)\\\
p&(c,d,p)\stackrel{{\scriptstyle\pi_{i}}}{{\longrightarrow}}(c,d,p^{\prime})\end{array}$

If $d=p,\gamma_{i}$ connects $(c,d,d)$ to $(c^{\prime},d,d)$ and
$Z\circ\pi_{i}$ connects $(c,d,d)$ to $(c,d^{\prime},d)$. $SBH(k,m)$ is a
dilation three emulation of the hypercube of dimension $k+m.$ It’s diameter is
$2k+m+3m=2k+4m$. It’s nodes are degree $k+2m$. The average dilation is less
than two. A node attached to $(c,d,p)$ translates a program designed for the
$(k+2m)$ Boolean hypercube into a program on the Swapped Hypercube using the
above paths.

If $D3(2^{k},2^{m})$ is constructed using Boolean arithmetic, it obviously
contains $SBH(k,m).\ \gamma_{i}=c\oplus c^{\prime},\pi_{i}=p\oplus p^{\prime}$
and $Z$ is the $0$ global port. On $SBH(k,m)$, these paths are used only for
pairs that differ by a single bit. Both directions can occur simultaneoursly.
All three exchanges are vector paths so can occur simultaneously because of
property 4 of Swapped Dragonflies. That is why $\pi_{i}$ is a $glg$ path
instead of an $lgl$ path. Therefore, an ascend-descent algorithm can be
performed at twice the cost of the algorithm on a $(k+2m)$ Boolean hypercube
because the average dilation of the emulation is two.

If $k$ is even, $2^{k}$ is a square so linear algebra can be performed
efficiently. If $k$ is not even, $k-1$ is and $D3(2^{k-1},2^{m})$ can be found
inside $D3(2^{k},2^{m})$.

Johnsson and Ho [10] developed an all-to-all algorithm on a Boolean hypercube
that takes network time $t_{w}n/2$. The algorithm is parallel over all
hypercube links. The algorithm can be run on $SBH(k,m)$ or on
$D3(2^{k},2^{m})$. On both a hypercube link is one, two, or three network
hops. The average is two. The algorithm takes $(2/3)(2^{k+2m}/2)t_{w}$ time on
$SBH(k,m)$.

The object of the following discussion is to prove that the doubly-parallel
all-to-all on $D3(2^{k},2^{m})$ is faster than the Johnson and Ho all-to-all
on $SBH(k,m)$. There is a constraint on the doubly-parallel all-to-all, $s\leq
M/2$, because paths on $D3(2^{k},2^{m})$ use two local hops. Therefore
$s=min(2^{k},2^{m-1})$ so the doubly-parallel algortithn takes

$2^{k+2m}/min(2^{k},2^{m-1})=max(2^{m},2^{k+m+1})t_{w}$

time on $D3(2^{k},2^{m})$. This is less than $(2^{k+2m}/3)t_{w}$ because $m$
and $k$ are not zero. Therefore, the doubly-parallel algorithm is superior.

##  5 The Broadcast Swapped Dragonfly

The $M$ routers on a drawer of $D3(K,M)$ contain $M$ depth four edge-disjoint
spanning trees

$(c,d,p)\stackrel{{\scriptstyle
G}}{{\longrightarrow}}(*,d,p)\stackrel{{\scriptstyle
L}}{{\longrightarrow}}(*,p,*)\stackrel{{\scriptstyle
0}}{{\longrightarrow}}(*,*,p)\stackrel{{\scriptstyle
L}}{{\longrightarrow}}(*,*,*).$ (5.1)

Replacing $p$ by $p^{\prime}$ leads to edge disjoint paths. This fact can be
used to do multiple broadcasts from source $(c,d,q)$ by starting with
$(c,d,q)\rightarrow(c,d,p)$ directing each $(c,d,p)$ to do a different
broadcast444This idea originated with Johnsson and Ho [9]. This requires five
router hops for each broadcast vs three router hops for the depth three
spanning tree

$(c,d,p)\longrightarrow(c,d,*)\longrightarrow(*,*,d)\longrightarrow(*,*,*)$

at $(c,d,p)$.

Implementation of this idea requires that routers can be equipped with a
program that does not depend upon their position in 5.1.The program proposed
here depends upon packets having a synchronizing header. A Swapped Dragonfly
using these headers is called a Broadcast Swapped Dragonfly. The header has
four entries $[b;\gamma,\pi,\delta];b$ is a counter , $\gamma$ is a global
port and $\delta$ and $\pi$ are local ports. A router interprets the header in
the following way.

  * •

if $b$ is odd, use local port $\delta$ and change $b$ to $b-1$, $\delta$ to
$\pi$ and $\pi$ to $0$,

  * •

if $b$ is even, use global port $\gamma$ and change $b$ to $b-1$ and $\gamma$
to $0$.

A packet has arrived at an edge router when $b=0$. This program is independent
of where the packet is in 5.1. If routers cannot duplicate packets, the header
becomes part of the packet. It is interpreted by a node attached to the router
at each hop of the path. Here are evolutions of paths when $b=3$ and $4$;

$\begin{array}[]{ccccccccccc}&(c,d,p)&\longrightarrow&(c,d,p+\delta)&\longrightarrow&(c+\gamma,p+\delta,d)&\longrightarrow&(c+\gamma,p+\delta,d+\pi)\\\
&[3;\gamma,\pi,\delta]&&[2;\gamma,0,\pi]&&[1;0,0,\pi]&&[0;0,0,0]\end{array}$
$\begin{array}[]{cccccccccc}&(c,d,p)&\longrightarrow&(c+\gamma,p,d)&\longrightarrow&(c+\gamma,p,d+\delta)&\stackrel{{\scriptstyle
0}}{{\longrightarrow}}&(c+\gamma,p+\delta,d+\pi)&\longrightarrow&(c+\gamma,d+\delta,p+\pi)\\\
&[4;\gamma,\pi,\delta]&&[3;0,\pi,\delta]&&[2;0,0,\pi]&&[1;0,0,\pi]&&[0;0,0,0]\end{array}$

The synchronized header is part of the packet header. It will be necessary for
the packet header to have a broadcast bit to distinguish the packet from a
point-to-poins packet.

If routers can duplicate packets, $M$ broadcast take time $t_{s}+5t_{w}$ where
$t_{s}$ is the time required to delegate broadcasts from $(c,d,p)$ to its
neighbors and $t_{w}$ is router latency. If routers cannot duplicate packets,
the time for $M$ broadcasts is $5t_{s}$. Using the level three spanning tree
at $(c,d,p)$, the time for $M$ broadcasts is proportional to $M$.

If a large number $X$ of broadcasts are needed the comparison is $5X/M$ to
$3X$ network hops which is clearly a win for the depth-four trees. However,
chaining may change the calculation. The following is an analysis of
performing $X>>M$ broadcasts using pipe-lining of the level three algorithm
and the level five algorithm.The depth three tree pipe-line.

$\begin{array}[]{ll}(c,d,p)\stackrel{{\scriptstyle
l}}{{\longrightarrow}}(c,d,*)\stackrel{{\scriptstyle
g}}{{\longrightarrow}}(*,*,d)\stackrel{{\scriptstyle
l}}{{\longrightarrow}}(*,*,*)\\\ \hskip
50.58878pt(c,d,p)\stackrel{{\scriptstyle
l}}{{\longrightarrow}}(c,d,*)\stackrel{{\scriptstyle
g}}{{\longrightarrow}}(*,*,d)\stackrel{{\scriptstyle
l}}{{\longrightarrow}}(*,*,*)\\\ \hskip
101.17755pt(c,d,p)\stackrel{{\scriptstyle
l}}{{\longrightarrow}}(c,d,*)\stackrel{{\scriptstyle
g}}{{\longrightarrow}}(*,*,d)\stackrel{{\scriptstyle
l}}{{\longrightarrow}}(*,*,*)\\\ \hskip
151.76744pt(c,d,p)\stackrel{{\scriptstyle
l}}{{\longrightarrow}}(c,d,*)\stackrel{{\scriptstyle
g}}{{\longrightarrow}}(*,*,d)\end{array}$

is free of conflict if $p\neq d$ so the cost is $X$ router hops.

Pipe-lining the $M$ depth-four spanning tree is more problematic; the first
local hop is the delegation step.

$\begin{array}[]{ll}(c,d,p)\stackrel{{\scriptstyle
l}}{{\longrightarrow}}(c,d,q)\stackrel{{\scriptstyle
g}}{{\longrightarrow}}(*,q,d)\stackrel{{\scriptstyle
l}}{{\longrightarrow}}(*,q,*)\stackrel{{\scriptstyle
0}}{{\longrightarrow}}(*,*,q)\stackrel{{\scriptstyle
l}}{{\longrightarrow}}(*,*,*)\\\ \hskip
50.58878pt(c,d,p)\stackrel{{\scriptstyle
l}}{{\longrightarrow}}(c,d,q)\stackrel{{\scriptstyle
g}}{{\longrightarrow}}(*,q,d)\stackrel{{\scriptstyle
l}}{{\longrightarrow}}(*,q,*)\stackrel{{\scriptstyle
o}}{{\longrightarrow}}(*,*,q)\longrightarrow(*,*,*)\\\ d\neq p\hskip
79.49744pt(c,d,p)\stackrel{{\scriptstyle
l}}{{\longrightarrow}}(c,d,q)\stackrel{{\scriptstyle
g}}{{\longrightarrow}}(*,q,d)\longrightarrow\\\ \hskip 191.51505pt\uparrow\\\
\hskip 180.67499pt\textrm{conflict}\end{array}$

So chaining in pairs gives the following:

$\begin{array}[]{l}(c,d,p)\stackrel{{\scriptstyle
l}}{{\longrightarrow}}(c,d,q)\stackrel{{\scriptstyle
g}}{{\longrightarrow}}(*,q,d)\stackrel{{\scriptstyle
l}}{{\longrightarrow}}(*,q,*)\stackrel{{\scriptstyle
0}}{{\longrightarrow}}(*,*,q)\stackrel{{\scriptstyle
l}}{{\longrightarrow}}(*,*,*)\\\ \hskip
50.58878pt(c,d,p)\stackrel{{\scriptstyle
l}}{{\longrightarrow}}(c,d,q)\stackrel{{\scriptstyle
g}}{{\longrightarrow}}(*,q,d)\stackrel{{\scriptstyle
l}}{{\longrightarrow}}(*,q,*)\stackrel{{\scriptstyle
0}}{{\longrightarrow}}(*,*,q)\stackrel{{\scriptstyle
l}}{{\longrightarrow}}(*,*,*)\end{array}$

delivers $2$ broadcasts every $6$ router hops for a cost of $3X/M$.

In broadcast mode the level three broadcast at $(c,d,p)$ has header
$[3;*,*,*]$ and the level four broadcast has header $[4;*,*,*]$. The evolution
of the headers in a broadcast is

$\begin{array}[]{ccccccccccc}&(c,d,p)&\longrightarrow&(c,d,*)&\longrightarrow&(*,*,d)&\longrightarrow&(*,*,*)\\\
&[3;*,*,*]&&[2;*,0,*]&&[1;0,0,*]&&[0;0,0,0]\end{array}$
$\begin{array}[]{cccccccccc}&(c,d,p)&\longrightarrow&(*,p,d)&\longrightarrow&(*,p,*)&\stackrel{{\scriptstyle
0}}{{\longrightarrow}}&(*,*,p)&\longrightarrow&(*,*,*)\\\
&[4;*,*,*]&&[3;0,*,*]&&[2;0,0,*]&&[1;0,0,*]&&[0;0,0,0]\end{array}$

respectively. In the level four path, the global port $0$ is used by $KM$
routers. Note that the header $[2;0,0,*]$ compels a router to send point-to-
point over global port $0$ and $[1;0,0,*]$ compels a local broadcast.

The Broadcast Swapped Dragonfly $D3(2^{k},2^{m})$ enables the emulation of the
$(k+2m)$-Boolean hypercube with uniform dilation four. The pathe $c,d,$ and
$p$ are given by

$\begin{array}[]{llc}c&[4;\gamma,0,0]\\\ d&[4:0,0,\delta]\\\
p&[4;0,\pi,0]\end{array}$

These are all four-path but they have the advantage that all paths of a given
type can be followed concurrently, and also paths of different type can be
followed concurrently without link conflict. The presence of a dilation four
hypercube in $D3(2^{k},2^{m})$ means that algorithms designed for hypercubes
may be compared with the algorithms designed here and the faster algorithm
used. If $K$ and $M$ are not powers of $2$, $D3(K,M)$ contains an emulation of
$D3(2^{k},2^{m})$ with $k=\log{K}$ and $m=\log{M}$.

##  6 Conclusion

It has been shown that there are three constraints on the parameters $K$ and
$M$ that lead to useful algorithms:

  1. 1.

On $D3(K^{2},M)$ an $n\times n$ matrix product can be computed in network time
$4(n^{2}/KM)t_{w}$.

  2. 2.

On $D3(ks,ms)$ an all-to-all exchange can be performed in network time
$(n^{2}/KM^{2}s)t_{w}$.

  3. 3.

$D3(2^{k},2^{m})$ contains a dilation three average two emulation of the
$(k+2m)$ Boolean hypercube.

  4. 4.

Additionally, it has been shown that equipping $D3(K,M)$ with a synchronizing
counter enables $n$ broadcasts in network time $(3n/M)t_{w}$.

Result 2 is the only algorithm to do an all-to-all on $P$ processors in less
than $P/2$ network time. Result 3 implies that an ascend-descend algorithm can
be done on $D3(K,M)$ at twice the cost of doing the algorithm on a Boolean
hypercube. The first three cases may apply to $D3(J,N)$ with $J\geq K$ and
$N\geq M$ because $D3(J,N)$ contains an emulaation of $D3(K,M)$.

Source-vector routing is used to define the algorithms in 1, 2, and 4. It
leads to algorithms devoid of interround conflicts. Source-vectors can be
defined on a Maximal Dragonfly. However, a vector $(\gamma,\pi,\delta)$
generally leads to a link conflict at the third hop when it is used by two
routers. This produces interround conflicts which lead to hotspots in an
application. On a Dragonfly, the algorithms studied here would be used in a
deflective routing environment. Vectors would be converted to destinations.

Note that $D3(2^{2k},2^{2m})$ is both a $D3(K^{2},M)$ and a $D3(ks,km)$. It
can do a $n\times n$ matrix product in $n/\sqrt{P}$ time, an all-to-all
exchange in time $n^{2}/\sqrt{P}\min(2^{k},2^{m})$ and an ascend-descend
algorithm at a factor two penalty over the cost on a hypercube of the same
size. Clearly, Swapped Dragonflies of the type $D3(2^{k},2^{m})$ or of type
$D3(K,2^{m})$ with $K$ only slightly larger than $2^{k}$ can be versatile
networks. The emulation of a $(k+2m)$ Boolean hypercube in $D3(2^{k},2^{m})$
means that algorithms designed for hypercubes may be compared with the
algorithms designed here and the faster algorithm used.

## References

  * [1] B. Alverson, E. Froese, L. Kaplan, and D. Roweth. _Cray $XC^{\copyright}$ Series_. www.cray.com.
  * [2] A. Ariimilli, V. Chung, W. Densel, B. Durup, T. Hoefler, J. Jones, J. Lewis, J. Li, N. Ni, and R. Rajamoni. The PERCS High Perormance Interconect. _18th Symposium on High Performance Interconnects_ DOI 10.1109.HOT1.10, 2010
  * [3] L.E. Cannon. A cellular computer to implement the Kalman Filter Algorithm, _Technical report, Ph.D. Thesis_ , Montana State University, 14 July 1969
  * [4] E. Dekel. Nassimi, D., and Sahni, S. Parallel Matrix and graphs algorithms SIAM _J. Computing_ 10:657 673. 1982
  * [5] R. Draper. The Swapped Dragonfly , ArXiv for Computer Science:2202.01843.
  * [6] R. Draper. The Fine Structure of Dragonflies<EMAIL_ADDRESS><EMAIL_ADDRESS>  * [7] H. Gupta, P. Sadayappan. Communication Efficient Matrix-Multiplication on Hypercubes, dbpubs.stanford.edu
  * [8] S. Hoory, N. Linial, A. Wigderson. Expander Graphs and Their Applications, Bulletin of the American Mathematical Society. 43 (4). 439-562. doi 10.1090/S0273-0979-06-01126-8, 2008
  * [9] C.T. Ho, S.L. Johnsson, and A. Edelman. Matrix multiplication on hypercubes using full bandwidth and constant storage, In _Procedings of the Sixth Distributed Memory Computing Conference_ (1991) 447-451.
  * [10] S.L. Johnsson and C.T. Ho. Optimum broadcasting and personalized communication in hyperubes, _IEEE Transactions on Computers_ , $\boldsymbol{38}$(9) (1989) 1249-1268.
  * [11] J. Kim, W.J. Dally, S. Scott, and D. Abts. Technology-Driven, Highly-Scalable Dragonfly Topology. _International Symposium on Computer Architecture_. 77-88, 2008.